Метады аптымізацыі і планавання.

  1. Кіраўнік 10 Метады аптымізацыі і планавання.
  2. 10.1 Класічная пастаноўка задачы аптымізацыі
  3. 10.2. Класіфікацыя задач аптымізацыі
  4. 10.3 Многокритериальная аптымізацыя

Кіраўнік 10 Метады аптымізацыі і планавання.

Метады аптымізацыі шырока прымяняюцца для вырашэння задач тэорыі аптымальных працэсаў, аптымальнага рэгулявання, выпрацоўкі да е рувальних абурэнняў на аб'екты. Без распрацоўкі і прымянення метадаў аптымізацыі немагчыма кіравання рэктыфікацыйнай калоны ў спіртавы прамысловасці, ўстаноўкамі крэкінгу нафты, канвертар пры вытворчасці сталі і інш. Да транспартных задач і задачы коміваяжора зводзяцца многія задачы эканамічнай кібернетыкі (сеткавае планаванне, кіраванне запасамі, перавозкамі і інш.), Упраўленне арганізацыяй вытворчасці (размеркаванне задач, апрацоўка дэталяў, канвеерная вытворчасць) і задачы аптымальнага праграмавання. Асобная група задач тэорыі аптымізацыі - гэта задачы аптымальнага праектавання. Напрыклад, задачы праектавання радыёэлектронных сродкаў з зададзенымі абмежаваннямі на ўзровень шуму і паласу прапускання або паказчыкамі надзейнасці ва ўмовах старэння.

10.1 Класічная пастаноўка задачы аптымізацыі

Звычайная пастаноўка задачы аптымізацыі такая: у некаторым прасторы тым ці іншым спосабам вылучаецца некаторы непустым мноства кропак гэтай прасторы, якую называюць дапушчальнай мноствам. Далей фіксуецца некаторая сапраўдная функцыя , Задаюць ва ўсіх кропках дапушчальнага мноства. Яна называецца мэтавай функцыяй. Задача аптымізацыі заключаецца ў тым, каб знайсці кропку ў множным ліку , Для якой функцыя прымае экстрэмальнае (максімальнае або мінімальнае) значэнне. У першым выпадку для ўсіх кропак мноства задавальняецца няроўнасць , У другім выпадку - няроўнасць .

У практычных задачах магчымыя дзве асноўныя пастаноўкі аптымізацыйных задач. У першым выпадку задача разглядаецца ў звычайным (эўклідавай) прасторы канчатковай памернасці. кропкамі дапушчальнага мноства будуць картэжы сапраўдных лікаў, мэтавай жа функцыяй будзе звычайная сапраўдная функцыя ад сапраўдных аргументаў ( у - памернасць прасторы). Такую задачу мы будзем называць у далейшым задачай аптымізацыі функцый. У другім выпадку пастаноўкі аптымізацыйных задачы ў якасці дапушчальнай мноства выступае некаторы мноства функцый сапраўдных зменных , А мэтавай функцыяй з'яўляецца некаторы функцыянал , Які ставіць у адпаведнасць кожнай функцыі некаторы сапраўдны лік . Гэтую задачу мы будзем называць задачай аптымізацыі функцыяналаў або варыяцыйнай задачай.

10.2. Класіфікацыя задач аптымізацыі

Перш за ўсё трэба падзяляць задачы параметрычнай і структурнай аптымізацыі.

Параметрычная аптымізацыя з'яўляецца прадметам разгляданага ў гэтым раздзеле, дзе прыведзены пастаноўка такой задачы і метады яе вырашэння. Структурная аптымізацыя - гэта задача сінтэзу аптымальнай структуры сістэмы, прычым змена структур і пераўтварэння адной структуры ў іншую ажыццяўляецца па спецыяльным алгарытму сінтэзу. Параметрычная аптымізацыя аб'ядноўвае шмат розных задач, маюць свае ўласныя асаблівасці і метады рашэння.

Класіфікацыю задач прыведзены на малюнку 5.1.

Да гэтага трэба дадаць некаторы каментар:

1. Калі існуе некалькі мэтавых функцый, то мае месца задача вектарнай аптымізацыі.

2. Калі колькасць параметраў , Кіраваныя, больш чым адзін, то вырашаецца задача шматмернай аптымізацыі.

3. Калі існуюць абмежаванні і ўмовы, якія злучаюць параметры , То ўзнікае задача аптымізацыі з умовамі, якая ў кібернетыцы атрымала назву матэматычнага праграмавання.

4. Матэматычнае праграмаванне аб'ядноўвае задачы нелінейнага праграмавання (мэтавая функцыя ў агульным выпадку нелінейная), стахастычнага праграмавання (параметры - выпадковая велічыня, а мэтавая функцыя - выпадковая функцыя), дынамічнага праграмавання (аптымізацыя шматкрокавая працэсаў пошуку рашэння).

5. Калі параметры, кіруюцца, прымаюць толькі дыскрэтныя значэння, то ўзнікае задача дыскрэтнай аптымізацыі, а калі - цэлыя лікі, то - задача цэлалікавага праграмавання.

6. У выпадку, калі мэтавая функцыя выпуклая, тая вобласць, дзе зададзеныя Таксама выпуклая, то мае месца задача выпуклага праграмавання. Калі мэтавая функцыя і ўмовы лінейныя-лінейнага (кавалкава-лінейнай) праграмавання; мэтавая функцыя квадратычнай, а ўмовы лінейныя-квадратычнага праграмавання; мэтавая функцыя і ўмовы - лінейныя камбінацыі функцый адной зменнай - сепарабельного праграмавання; мэтавая функцыя і ўмовы прадстаўлены ў выглядзе полиномов - геаметрычнага праграмавання.

10.3 Многокритериальная аптымізацыя

На практыцы часта ўзнікае выпадак, калі замест адной мэтавай функцыі зададзена некалькі мэтавых функцый . Такая задача многокритериальной аптымізацыі мае некалькі пастановак. У адной з іх трэба аптымізаваць адзін з крытэраў, дапусцім, , Прычым астатнія крытэрыяў утрымліваюць у зададзеных межах: . У гэтым выпадку фактычна гаворка ідзе пра звычайную многокритериальную аптымізацыю. Што тычыцца няроўнасцяў, якія абмяжоўваюць іншыя крытэрыі, то іх можна разглядаць як дадатковыя абмежаванні на дапушчальную вобласць .

Малюнак 5.1 - Класіфікацыя задач аптымізацыі

У другім выпадку пастаноўка заключаецца ў складанні зададзенага мноства крытэраў і паслядоўнай аптымізацыі па кожным з іх. Інакш, калі праводзяць аптымізацыю па першым крытэру , То атрымліваюць некаторы мноства , На якой функцыя прымае аптымальнае (экстрэмальнае) значэння. Прыняўшы яго за новую дапушчальную мноства, праводзяць аптымізацыю па другім крытэру і атрымліваюць у выніку новую дапушчальную мноства . Калі працягнуць гэты працэс, то можна пасля аптымізацыі па апошнім крытэру мноства , Якая і будзе канчатковым вынікам многокритериальной аптымізацыі. Адсюль, калі на некаторай кроку мноства звядзецца да адной кропцы, працэс аптымізацыі можна будзе скончыць, паколькі . Зразумела, што як і ў выпадку звычайнай однокритериальной аптымізацыі, задача можа наогул не мець развязку.

Трэцяя пастаноўка прымяняе працэс ўзвядзення многіх крытэрыяў да аднаго за кошт увядзення апрыёрных вагавых каэфіцыентаў для кожнага з крытэраў . У якасці такіх каэфіцыентаў могуць быць выбраны любыя сапраўдныя лікі. Іх значэнне выбіраюць, зыходзячы з інтуітыўнага прадстаўлення ступені важнасці розных крытэрыяў: больш важныя крытэрыі атрымліваюць вагі з вялікімі абсалютнымі значэннямі. Пасля ўстаноўкі вагаў многокритериальная задача зводзіцца да однокритериальной з мэтавай функцыяй

Замест простай лінейнай камбінацыі ўваходных крытэрыяў могуць выкарыстоўвацца і больш складаныя сродкі фарміравання з іх новага крытэра.