Методы оптимизации
 | |||
 |
Математическая модель
Математическая модель — описание решаемой задачи в математических терминах.
Математическая модель описывает исследуемую систему и позволяет выразить ее эффективность в виде целевой функции
W = f (X, Y),
где X = (x 1,…, xn) — управляемые переменные,
Y = (y 1,…, y m) — неуправляемые переменные(исходные данные).
Связь между переменными X и исходными данными Y выражается с помощью ограничений
j (X, Y) £ 0.
Виды моделей
· детерминированные;
· вероятностные;
· игровые;
· неполные (задачи в условиях неопределенности).
Исследованием детерминированных моделей занимается математическое программирование (МП).
Термин «программирование» означает «поиск наилучших планов» (programming – планирование – составление плана или программы действий).
Задача оптимизации
(
)
Задача математического программирования
Оптимальным решением задачи (минимизации) называют допустимое решение, минимизирующее f (x) на множестве всех допустимых решений.
Задачи математического программирования
 | |||
 |
История математического программирования
Б.Т. Поляк, Институт проблем управления, Москва
История математического программирования в СССР: попытка анализа
История математического программирования
1. Леонард Эйлер, 1707-1783, первый ученый, занимавшийся оптимизацией в России
2. Чебышев П.Л., 1821-1894, основы выпуклой оптимизации, решал практические оптимизационные задачи: построение наименее искаженной географической карты, оптимальный раскрой, наилучший выбор параметров механических устройств
3. А.А. Марков, 1856-1922, известны работы в теории чисел и теории вероятностей (Марковские цепи, Марковские процессы)
4. А.М. Ляпунов, 1857-1918, разработал теорию устойчивости для дифференциальных обыкновенных уравнений, тем самым внес огромный вклад в развитие непрерывной оптимизации, предложил инструмент для проверки сходимости численных методов оптимизации
История математического программирования
5. Л.В. Канторович, 1912-1986, в 1975г. получил Нобелевскую премию в области экономики, один из основателей численного анализа в нашей стране, одним из первых признал информатику как новую ветвь в математике.
Отец новой науки ОПТИМИЗАЦИИ, которая включает стандартное математическое программирование.
С именем Канторовича Л.В.связаны следующие достижения:
Линейное программирование, 1939:
Опубликована книга (67 стр.), в которой рассматривался новый тип оптимизационных задач. Формы записи этих задач были иными, чем стандартная формулировка задачи ЛП, причем модель, рассматриваемая в западной литературе - частный случай модели Канторовича.
Общие условия оптимальности, 1940
Техника функционального анализа, 1939-1948
История математического программирования
6. Г.Ш. Рубинштейн, ученик Канторовича Л.В., учитель д.т.н., проф. УГАТУ Мухачевой Э.А.
В 1961г. вышла книга Канторовича Л.В. и Рубинштейна Г.Ш., в которой давались математические формулировки задачи ЛП и приводились численные методы ее решения, были введены понятия двойственных переменных, которые назывались «объектно-обусловленными оценками».
7. В 50-е годы – интенсивные исследования в области ЛП.
Стали известны работы западных ученых: Дж. Данцига, Г.Куна, А. Таккера и др. по ЛП.
Выпущен первый учебник на русском языке по ЛП Юдиным Д.Б., Гольштейном Е.Г.
8. 60-е годы
Появилась общая теория двойственности для задач выпуклой оптимизации (Гольштейн Е.Г.), появились труды по стохастической оптимизации.