Навигация по сайту

Популярные статьи

Аптымізацыя (матэматыка)

  1. Пастаноўка задачы аптымізацыі
  2. Відэа па тэме
  3. гісторыя
  4. Гл. Таксама

У гэтага паняцця ёсць і іншыя значэнні, гл. аптымізацыя .

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

Тэорыю і метады рашэння задачы аптымізацыі вывучае матэматычнае праграмаванне.

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

Пастаноўка задачы аптымізацыі

У працэсе праектавання ставіцца звычайна задача вызначэння найлепшых, у пэўным сэнсе, структуры або значэнняў параметраў аб'ектаў. Такая задача завецца аптымізацыйных. Калі аптымізацыя звязаная з разлікам аптымальных значэнняў параметраў пры зададзенай структуры аб'екта, то яна называецца параметрычнай аптымізацыяй. Задача выбару аптымальнай структуры з'яўляецца структурнай аптымізацыяй.

Стандартная матэматычная задача аптымізацыі фармулюецца такім чынам. Сярод элементаў χ, якія ўтвараюць мноства Χ, знайсці такі элемент χ *, які дастаўляе мінімальнае значэнне f (χ *) зададзенай функцыі f (χ). Для таго, каб карэктна паставіць задачу аптымізацыі, неабходна задаць:

  1. Дапушчальнае мноства - мноства X = {x → | gi (x →) ≤ 0, i = 1, ..., m} ⊂ R n {\ displaystyle \ mathbb {X} = \ {{\ vec {x}} | \; g_ {i} ({\ vec {x }}) \ leq 0, \; i = 1, \ ldots, m \} \ subset \ mathbb {R} ^ {n}} У гэтага паняцця ёсць і іншыя значэнні, гл ;
  2. Мэтавую функцыю - адлюстраванне f: X → R {\ displaystyle f: \; \ mathbb {X} \ to \ mathbb {R}} ;
  3. крытэр пошуку (Max або min).

Тады вырашыць задачу f (x) → min x → ∈ X {\ displaystyle f (x) \ to \ min _ {{\ vec {x}} \ in \ mathrm {X}}} Тады вырашыць задачу f (x) → min x → ∈ X {\ displaystyle f (x) \ to \ min _ {{\ vec {x}} \ in \ mathrm {X}}}   азначае адно з: азначае адно з:

  1. Паказаць, што X = ∅ {\ displaystyle \ mathbb {X} = \ varnothing} .
  2. Паказаць, што мэтавая функцыя f (x →) {\ displaystyle f ({\ vec {x}})} не абмежавана знізу.
  3. Знайсці x → * ∈ X: f (x → *) = min x → ∈ X f (x →) {\ displaystyle {\ vec {x}} ^ {*} \ in \ mathbb {X}: \; f ( {\ vec {x}} ^ {*}) = \ min _ {{\ vec {x}} \ in \ mathbb {X}} f ({\ vec {x}})} .
  4. Калі ∄ x → * {\ displaystyle \ nexists {\ vec {x}} ^ {*}} , То знайсці inf x → ∈ X f (x →) {\ displaystyle \ inf _ {{\ vec {x}} \ in \ mathbb {X}} f ({\ vec {x}})} .

Калі минимизируемая функцыя не з'яўляецца выпуклай , То часта абмяжоўваюцца пошукам лакальных мінімумаў і максімумаў: кропак x 0 {\ displaystyle x_ {0}} Калі минимизируемая функцыя не з'яўляецца   выпуклай   , То часта абмяжоўваюцца пошукам лакальных мінімумаў і максімумаў: кропак x 0 {\ displaystyle x_ {0}}   такіх, што ўсюды ў некаторай іх наваколлі f (x) ≥ f (x 0) {\ displaystyle f (x) \ geq f (x_ {0})}   для мінімуму і f (x) ≤ f (x 0) {\ displaystyle f (x) \ leq f (x_ {0})}   для максімуму такіх, што ўсюды ў некаторай іх наваколлі f (x) ≥ f (x 0) {\ displaystyle f (x) \ geq f (x_ {0})} для мінімуму і f (x) ≤ f (x 0) {\ displaystyle f (x) \ leq f (x_ {0})} для максімуму.

Калі дапушчальнае мноства X = R n {\ displaystyle \ mathbb {X} = \ mathbb {R} ^ {n}} Калі дапушчальнае мноства X = R n {\ displaystyle \ mathbb {X} = \ mathbb {R} ^ {n}}   , То такая задача называецца задачай безумоўнай аптымізацыі, у адваротным выпадку - задачай ўмоўнай аптымізацыі , То такая задача называецца задачай безумоўнай аптымізацыі, у адваротным выпадку - задачай ўмоўнай аптымізацыі.

Відэа па тэме

Класіфікацыя метадаў аптымізацыі

Агульная запіс задач аптымізацыі задае вялікая разнастайнасць іх класаў. Ад класа задачы залежыць падбор метаду (эфектыўнасць яе рашэння). Класіфікацыю задач вызначаюць: мэтавая функцыя і дапушчальная вобласць (задаецца сістэмай няроўнасцей і роўнасцяў ці больш складаным алгарытмам). [2]

Метады аптымізацыі класіфікуюць ў адпаведнасці з задачамі аптымізацыі:

  • Лакальныя метады: сыходзяцца да якога-небудзь лакальнаму экстрэмуму мэтавай функцыі. У выпадку унимодальной мэтавай функцыі, гэты экстрэмуму Адзінае, і будзе глабальным максімумам / мінімумам.
  • Глабальныя метады: маюць справу з многоэкстремальными мэтавымі функцыямі. Пры глабальным пошуку асноўнай задачай з'яўляецца выяўленне тэндэнцый глабальнага паводзінаў мэтавай функцыі.

Якія існуюць у цяперашні час метады пошуку можна разбіць на тры вялікія групы:

  1. дэтэрмінаваных;
  2. выпадковыя (стахастычныя);
  3. камбінаваныя.

Па крытэры памернасці дапушчальнага мноства, метады аптымізацыі дзеляць на метады аднамернай аптымізацыі і метады шматмернай аптымізацыі.

Па выглядзе мэтавай функцыі і дапушчальнага мноства, задачы аптымізацыі і метады іх рашэння можна падзяліць на наступныя класы:

Па патрабаванням да гладкасці і наяўнасці ў мэтавай функцыі прыватных вытворных, іх таксама можна падзяліць на:

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

Акрамя таго, аптымізацыйных метады дзеляцца на наступныя групы:

У залежнасці ад прыроды мноства X задачы матэматычнага праграмавання класіфікуюцца як:

Акрамя таго, часткамі матэматычнага праграмавання з'яўляюцца параметрычнае праграмаванне , дынамічнае праграмаванне і стахастычнага праграмаванне .

Матэматычнае праграмаванне выкарыстоўваецца пры вырашэнні аптымізацыйных задач даследаванні аперацый .

Спосаб знаходжання экстрэмуму цалкам вызначаецца класам задачы. Але перад тым, як атрымаць матэматычную мадэль, трэба выканаць 4 этапы мадэлявання:

  • Вызначэнне межаў сістэмы аптымізацыі
    • Адкідаем тыя сувязі аб'екта аптымізацыі са знешнім светам, якія не могуць моцна паўплываць на вынік аптымізацыі, а, дакладней, тыя, без якіх рашэнне спрашчаецца
  • Выбар кіраваных зменных
    • «Замарожваем» значэння некаторых зменных (некіравальныя зменныя). Іншыя пакідаем прымаць любыя значэнні з вобласці дапушчальных рашэнняў (якія кіруюцца зменныя)
  • Вызначэнне абмежаванняў на кіраваныя зменныя
    • ... (роўнасці і / або няроўнасці)
  • Выбар лікавага крытэра аптымізацыі (напрыклад, паказчыка эфектыўнасці )
    • Ствараем мэтавую функцыю

гісторыя

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

Прысутнасць у назве дысцыпліны тэрміна «праграмаванне» тлумачыцца тым, што першыя даследаванні і першыя прыкладання лінейных аптымізацыйных задач былі ў сферы эканомікі, так як у ангельскай мове слова «programming» азначае планаванне , Складанне планаў або праграм. Цалкам натуральна, што тэрміналогія адлюстроўвае цесную сувязь, існуючую паміж матэматычнай пастаноўкай задачы і яе эканамічнай інтэрпрэтацыяй (вывучэнне аптымальнай эканамічнай праграмы). тэрмін « лінейнае праграмаванне »Быў прапанаваны Дж. Данцыгам ў 1949 годзе для вывучэння тэарэтычных і алгарытмічных задач, звязаных з аптымізацыяй лінейных функцый пры лінейных абмежаваннях.

Таму найменне «матэматычнае праграмаванне» звязана з тым, што мэтай вырашэння задач з'яўляецца выбар аптымальнай праграмы дзеянняў.

Вылучэнне класа экстрэмальных задач, якiя вызначаюцца лінейным функцыяналам на мностве, зададзеным лінейнымі абмежаваннямі, варта аднесці да 1930-м гадам. Аднымі з першых, даследаваў у агульнай форме задачы лінейнага праграмавання, былі: Джон фон Нэйман - матэматык і фізік, які даказаў асноўную тэарэму аб матрычных гульнях і які вывучыў эканамічную мадэль , Якая носіць яго імя, і Л. В. Канторович - савецкі акадэмік, лаўрэат Нобелеўскай прэміі (1975), які сфармуляваў шэраг задач лінейнага праграмавання і які прапанаваў ў 1939 годзе метад іх вырашэння ( метад дазвалялых множнікаў ), Нязначна адрозніваецца ад сімплекс-метаду.

У 1931 годзе венгерская матэматык Б. Эгервари разгледзеў матэматычную пастаноўку і вырашыў задачу лінейнага праграмавання, якая мае назву «праблема выбару», метад рашэння атрымаў назву « вугорскага метаду ».

Л. В. Канторовичем сумесна з М. К. Гавуриным ў 1949 годзе распрацаваны метад патэнцыялаў , Які ўжываецца пры вырашэнні транспартных задач . У наступных працах Л. В. Канторовича, В. С. Нямчынава , В. В. Наважылава , А. Л. Лур'е , А. Брудно , А. Г. Аганбегян , Д. Б. Юдзіна , Е. Г. Гальштэйна і іншых матэматыкаў і эканамістаў атрымалі далейшае развіццё як матэматычная тэорыя лінейнага і нелінейнага праграмавання , Так і дадатак яе метадаў да даследаванню розных эканамічных праблем.

Метадам лінейнага праграмавання прысвечана шмат работ замежных навукоўцаў. У 1941 годзе Ф. Л. Хитчкок паставіў транспартную задачу . Асноўны метад рашэння задач лінейнага праграмавання - сімплекс-метад - быў апублікаваны ў 1949 годзе Дж. Данцыгам. Далейшае развіццё метады лінейнага і нелінейнага праграмавання атрымалі ў працах Г. Куна , А. Таккер , Гаса (Saul. I. Gass), Чарнеса (A. Charnes), біла (EM Beale) і інш.

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

Пачынаючы з 1955 году апублікаваў шмат прац, прысвечаных квадратическому праграмаванні (Работы Біла, Баранкина і Р. Дорфмана , Франка (M. Frank) і Ф. Вулфа [En] , Г. Марковица і інш.). У працах Дэніса (JB Dennis), Розена (JB Rosen) і Зонтендейка (G. Zontendijk) распрацаваны градыентныя метады рашэння задач нелінейнага праграмавання.

У цяперашні час для эфектыўнага прымянення метадаў матэматычнага праграмавання і рашэнні задач на кампутарах распрацаваны Алгебраічныя мовы мадэлявання , Прадстаўнікамі якімі з'яўляюцца AMPL і LINGO .

Гл. Таксама

нататкі

літаратура

  • Абакаров А. Ш., Сушкоў Ю. А. Статыстычнае даследаванне аднаго алгарытму глабальнай аптымізацыі . - Працы Фора, 2004.
  • Акуліч І. Л. Матэматычнае праграмаванне ў прыкладах і задачах: Вучэб. дапаможнік для студэнтаў эканом. спец. ВНУ. - М.: Вышэйшая школа 1986.
  • Гіл Ф., Мюрэй У., Райт М. Практычная аптымізацыя. Пер. з англ. - М.: Свет, 1985.
  • Гирсанов І. В. Лекцыі па матэматычнай тэорыі экстрэмальных задач. - М.; Іжэўск : НДЦ «Рэгулярная і хаатычная дынаміка», 2003. - 118 с. - ISBN 5-93972-272-5 .
  • Жиглявский А. А., Жилинкас А. Г. Метады пошуку глабальнага экстрэмуму. - М.: Навука, Физматлит 1991.
  • Кішэняў В. Г. Матэматычнае праграмаванне. - І. ць фіз.-мат. літаратуры, 2004.
  • Корн Г., корн Т. Даведнік па матэматыцы для навуковых работнікаў і інжынераў. - М.: Навука, 1970. - С. 575-576.
  • Каршуноў Ю. М., каршуноў Ю. М. Матэматычныя асновы кібернетыкі. - М.: Энергоатомиздат, 1972 г..
  • Максімаў Ю. А., Филлиповская Е. А. Алгарытмы рашэння задач нелінейнага праграмавання. - М.: МІФІ, 1982.
  • Максімаў Ю. А. Алгарытмы лінейнага і дыскрэтнай праграмавання. - М.: МІФІ, 1980.
  • Цесляроў А. Д. Матэматычнае праграмаванне = экспрэс-курс. - 2006. - С. 171. - ISBN 985-475-186-4 .
  • Растригин Л. А. Статыстычныя метады пошуку. - М., 1968.
  • Дыяганальныя метады глабальнай аптымізацыі (Электронны рэсурс) / Сяргееў Я.Д., квас Д.Я. - М.: ФИЗМАТЛИТ, 2008. 341с.
  • Хемди А. Таха. Ўвядзенне ў даследаванне аперацый = Operations Research: An Introduction. - 8 выд. - М.: Вільямс , 2007. - С. 912. - ISBN 0-13-032374-8 .
  • Кіні Р. Л., райфа Х. Прыняцце рашэнняў пры шматлікіх крытэрах: перавагі і замяшчэння. - М.: Радыё і сувязь, 1981. - 560 с.
  • С.И.Зуховицкий , Л.И.Авдеева. Лінейнае і выпуклае праграмаванне. - 2-е выд., Перапрац. і доп .. - М.: Выдавецтва "Навука", 1967 г..
  • Мінаяў Ю. Н. Стабільнасць эканоміка-матэматычных мадэляў аптымізацыі. - М.: Статыстыка, 1980.
  • Майсееў Н. Н. Лікавыя метады ў тэорыі аптымальных сістэм. - М: Навука, 1971. - 424 с.
  • Майсееў Н. Н. Элементы тэорыі аптымальных сістэм. - М: Навука, 1975. - 528 с.
  • Майсееў Н. Н. , Иванилов Ю. П., Сталярова Е. М. Метады аптымізацыі. - М: Навука, 1978. - 352 с.
  • Дзегцяроў Ю. І. Метады аптымізацыі. - М: Савецкае радыё, 1980. - 272 с.
  • Реклейтис Г., Рейвиндран А., Рэгсдел К. Аптымізацыя ў тэхніцы. - М.: Свет, 1986. - 400 с.

спасылкі