Оптимізація (математика)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Графік параболоїду, заданого як z = f(x, y) = −(x² + y²) + 4. Глобальний максимум в точці (x, y, z) = (0, 0, 4) позначено синьою точкою.

Задачею оптимізації в математиці називається задача про знаходження екстремума (мінімума або максимума) дійсної функції у деякій області. Як правило, розглядаються області, що належать і задані набором рівностей і нерівностей.

Математичне програмування — математична дисципліна, що вивчає теорію й методи розв'язання задач про знаходження екстремумів функцій на множинах скінченновимірного векторного простору, обумовлених лінійними й нелінійними обмеженнями (рівностями і нерівностями).

Постановка задачі оптимізації[ред.ред. код]

У процесі проектування ставиться, звичайно, задача визначення найкращих, у деякому значенні, структури або значення параметрів об'єктів. Така задача називається оптимізаційною. Якщо оптимізація пов'язана з розрахунком оптимальних значень параметрів при заданій структурі об'єкта, то вона називається параметричною. Задача вибору оптимальної структури є структурною оптимізацією.

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

  1. Допустиму множину — множину ;
  2. Цільову функцію — відображення ;
  3. Критерій пошуку (max або min).

Тоді вирішити задачу означає одне з:

  1. Показати, що .
  2. Показати, що цільова функція не обмежена знизу.
  3. Знайти .
  4. Якщо , то знайти .

Якщо мінімізована функція не є опуклою, то часто обмежуються пошуком локальних мінімумів і максимумів: точок таких, що всюди в деякому їхньому околі для мінімуму й для максимуму.

Якщо допустима множина , то така задача називається задачею безумовної оптимізації, в іншому разі — задачею умовної оптимізації.

Функцію f в різних галузях називають по різному, цільовою функцією (англ. objective function), функцією втрат (англ. loss function) чи функцією витрат (англ. cost function) (при мінімізації),[1] або функцією корисності (англ. utility function) чи функцією пристосованості (англ. fitness function) (максимізація), функцією енергії (англ. energy function) або функціоналом енергії (англ. energy functional).

Класифікація методів оптимізації[ред.ред. код]

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

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

Існуючі в цей час методи пошуку можна розбити на три великі групи:

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

За критерієм вимірності допустимої множини, методи оптимізації поділяють на методи одномірної оптимізації і методи багатомірної оптимізації.

За видом цільової функції й допустимої множини, задачі оптимізації й методи їхнього розв'язання можна розділити на такі класи:

За вимогами до гладкості й наявності в цільової функції частинних похідних, їх також можна розділити на:

  • прямі методи, що вимагають тільки обчислень цільової функції в точках наближень;
  • методи першого порядку[ru]: вимагають обчислення перших частинних похідних функції, тобто якобіана цільової функції;
  • методи другого порядку: вимагають обчислення других частинних похідних, тобто гессіана цільової функції.

Крім того, оптимізаційні методи поділяються на такі групи:

Залежно від природи множини X задачі математичного програмування класифікуються так:

Крім того, розділами математичного програмування є параметричне програмування, динамічне програмування і стохастичне програмування[en]. Математичне програмування використовується при розв'язанні оптимізаційних задач дослідження операцій.

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

  • Визначення меж системи оптимізації
    • Відкидаємо ті зв'язки об'єкта оптимізації із зовнішнім світом, які не можуть сильно вплинути на результат оптимізації, а, точніше, ті, без яких розв'язання спрощується
  • Вибір змінних проектування (керованих змінних)
    • «Заморожуємо» значення деяких змінних (некеровані змінні). Інші залишаємо приймати будь-які значення з області допустимих рішень (керовані змінні)
  • Визначення обмежень на керовані змінні
    • … (рівності й\або нерівності)
  • Вибір числового критерію оптимізації
    • Створюємо цільову функцію

Історія[ред.ред. код]

Задачі лінійного програмування були першими, докладно вивченими задачами пошуку екстремума функцій при наявності обмежень типу нерівностей. В 1820 р. Ж. Фур'є і потім в 1947 р. Дж. Данціг запропонував метод направленого перебору суміжних вершин у напрямку зростання цільової функції — симплекс-метод, що став основним при розв'язанні задач лінійного програмування.

Присутність у назві дисципліни терміна «програмування» пояснюється тим, що перші дослідження й перші застосування лінійних оптимізаційних задач були в сфері економіки, тому що в англійській мові слово «programming» означає планування, складання планів або програм. Цілком природно, що термінологія відображає тісний зв'язок, що існує між математичною постановкою задачі і її економічною інтерпретацією (вивчення оптимальної економічної програми). Термін «лінійне програмування» був запропонований Дж. Данцігом в 1949 г. для вивчення теоретичних і алгоритмічних задач, пов'язаних з оптимізацією лінійних функцій при лінійних обмеженнях. Тому найменування «Математичне програмування» пов'язане з тим, що метою розв'язання задач є вибір оптимальної програми дій.

Виділення класу екстремальних задач, обумовлених лінійним функціоналом на множині, що задається лінійними обмеженнями, варто віднести до 30-х років XX сторіччя. Одними з перших, що досліджували в загальній формі задачі лінійного програмування, були: Джон фон Нейман, знаменитий математик і фізик, що довів основну теорему про матричні ігри й вивчив економічну модель, що носить його ім'я; радянський академік, лауреат нобелівської премії (1975 р.) Л. В. Канторович, що сформулював ряд задач лінійного програмування й запропонував (1939 р.) метод їхнього розв'язання (метод розв'язних множників), що незначно відрізняється від симплекс-методу.

В 1931 р. угорський математик Б. Егерварі розглянув математичну постановку й вирішив задачу лінійного програмування, що має назва «проблема вибору», метод розв'язання одержав назву «угорського методу».

Л. В. Канторовичем разом із М. К. Гавуриним в 1949 р. розроблено метод потенціалів[ru], що застосовується при розв'язанні транспортних задач. У наступних роботах Л. В. Канторовича, В. С. Немчинова, В. В. Новожилова, А. Л. Лур'є, А. Брудно, А. Г. Аганбегяна[ru], Д. Б. Юдіна, Е. Г. Гольштейна й інших математиків і економістів отримали подальший розвиток як математична теорія лінійного і нелінійного програмування, так і застосування її методів до дослідження різних економічних проблем. Методам лінійного програмування присвячено багато робіт зарубіжних учених. В 1941 р. Ф. Л. Хітчкок[en] поставив транспортну задачу. Основний метод розв'язання задач лінійного програмування — симплекс-метод — був опублікований в 1949 р. Дж. Данцігом. Подальший розвиток методи лінійного і нелінійного програмування отримали в роботах Г. Куна[en], А. Таккера[en], Гасса (Gass S. I.), Чарнеса (Charnes A.), Біла (Beale E. M.) та інших.

Одночасно з розвитком лінійного програмування велика увага приділялася задачам нелінійного програмування, у яких або цільова функція, або обмеження, або те й те нелінійні. В 1951 р. була опублікована робота Куна й Таккера, у якій наведені необхідні й достатні умови оптимальності для розв'язання задач нелінійного програмування. Ця робота послужила основою для наступних досліджень у цій галузі.

Починаючи з 1955 р., опубліковано багато робіт з квадратичного програмування (роботи Била, Е. Баранкіна (Barankin E.) і Дорфмана (Dorfman R.), Франка (Frank M.) і Вольфа (Wolfe P.), Г. Марковіца та інших). У роботах Денніса (Dennis J. B.), Розена (Rosen J. B.) і Зонтендейка (Zontendijk G.) розроблено градієнтні методи розв'язання задач нелінійного програмування.

У даний час для ефективного застосування методів математичного програмування й розв'язання задач на комп'ютерах розроблені мови алгебраїчного моделювання, представниками якими є AMPL і LANGO.

Див. також[ред.ред. код]

Література[ред.ред. код]

  1. Абакаров А.Ш., Сушков Ю.А. Статистическое исследование одного алгоритма глобальной оптимизации. — Труды ФОРА, 2004.
  2. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. пец. вузов. — М. : Высшая школа, 1986.
  3. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М. : Мир, 1985.
  4. Жиглявский А.А., Жилинкас А.Г. Методы поиска глобального экстремума. — М. : Наука, Физматлит, 1991.
  5. Карманов В.Г. Математическое программирование = Математическое программирование. — Изд-во физ.-мат. литературы, 2004.
  6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М. : Наука, 1970. — С. 575-576.
  7. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М. : Энергоатомиздат, 1972.
  8. Максимов Ю.А., Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М. : МИФИ, 1982.
  9. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М. : МИФИ, 1980.
  10. Плотников А.Д. Математическое программирование = экспресс-курс. — 2006. — С. 171. — ISBN 985-475-186-4.
  11. Растригин Л.А. Статистические методы поиска. — М., 1968.
  12. Хемди А. Таха Введение в исследование операций = Operations Research: An Introduction. — 8 изд.. — М. : «Вильямс», 2007. — С. 912. — ISBN 0-13-032374-8.


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.


  1. W. Erwin Diewert (2008). "cost functions," The New Palgrave Dictionary of Economics, 2nd Edition Contents.