Класифікація задач математичного програмування.
Існують досить прості математичні методи для розв’язання таких задач. Однак, перш ніж обрати метод для розв’язку задачі необхідно визначити, до якого класу вона відноситься. Умовно задачі математичного програмування можна розбити на такі:
1) Задачі лінійного і нелінійного програмування (в залежності від виду обмежень та цільової функції математичної моделі задачі).
В задачах лінійного програмування максимізується або мінімізується лінійна функція при наявності деяких обмежень, які виражаються у вигляді лінійних рівнянь або лінійних нерівностей.
В задачах нелінійного програмування нелінійною є цільова функція або в системі обмежень не лінійні рівняння або нерівності. Одним з окремих видів являється квадратичне програмування (квадратична функція).
2) Задачі динамічного програмування.
Задачі динамічного програмування є багатоетапними або багатокроковими. Знаходження розв’язку конкретних задач методами динамічного програмування включає декілька етапів, або кроків, на кожному з яких визначається розв’язок деякої часткової задачі, обумовленою вихідною.
3) Задачі детермінованого і стохастичного програмування (в залежності від характеру вихідних параметрів моделі).
В задачах детермінованого програмування вважаємо, що перехід від одного стану процесу до іншого цілковито залежить від обраного нами управління.
В задачах стохастичного програмування наступний стан процесу залежить не лише від вибраного нами управління, а ще й від деяких випадкових умов.
|
|
|
Історія розвитку математичного програмування.
Рання історія лінійного програмування тісно пов’язана з роботами за наступними напрямами:
1) математичні та фізичні підходи до проблеми віртуальних скоростей;
2) дослідження переміщення земляних мас для побудови французьких фортець;
3) процес математизації економічної науки.
Формулювання задач лінійного програмування і створення перших методів розв’язку стимулювали конкретні економічні задачі. Це, перш за все, необхідність вдосконалення перевезень на радянському транспорті в 30-ті роки, а також потреба в найкращий організації перевезень американського торгового флоту під час другої світової війни, також дослідження по балансуванню окремих галузей народного господарства. Саме вони дали перші результати в 20-30-ті роки ХХ століття. В цих перших роботах відбулася взаємодія різних наукових напрямів, що призвело до виникнення нової математичної дисципліни – “лінійного програмування”.
В цілому перша фаза виникнення лінійного програмування як самостійної математичної дисципліни охоплює біля 200 років (з середини XVIII сторіччя до 1939 року) в той час як період його затвердження тривав всього 10 років (з 1939 по 1949рр.)). Цей процес завершився проведенням першої спеціальної конференції по лінійному програмуванню в 1949 році в Чикаго. В той же час почався перехід до третьої фази – фази вдосконалення та розширення нової дисципліни.
|
|
|
Очевидно, вперше постановка задачі лінійного програмування у вигляді пропозиції по складанню оптимального плану перевезень, мінімізуючого загальний кілометраж (зараз подібні задачі отримали назву транспортних), зустрічається в роботах радянського економіста А.Н. Толстого (1930р.).
В 1931 році угорський математик Б. Егерварі розглянув в математичній постановці одну з окремих задач лінійного програмування, яка отримала в подальшому назву “проблеми вибору”. Він же й намітив метод її розв’язання, який був розвинений американським математиком Г. У. Куном стосовно загального класу транспортних задач і отримав назву угорського методу.
Систематичне дослідження задач лінійного програмування, перш за все як економічних задач, розробка загальних методів їх розв’язку розпочалися в 1939 році в роботах радянського математика Л.В. Канторовича та його учнів. Канторовичем був запропонований загальний метод розв’язання задач лінійного програмування, названий ним методом “розв'язуючих множників”, який лише в деталях відрізняється від загальноприйнятого зараз симплекс-методу.
|
|
|
Для розв’язку транспортних задач Л.В. Канторовичем та М.К. Гавуріним в 1949 році був запропонований метод потенціалів, що являє собою реалізацію методу “розв'язуючих множників” стосовно розв’язання транспортної задачі.
В наступних роботах Л.В. Канторовича, В.С. Немчинова, В.В. Новожилова, А.Л. Лур’є, А. Брудно, Г.Ш. Рубінштейна, Ц.Б. Юдіна, Б. Г. Гольдштейна, А.Г. Аганбегяна та багатьох інших радянських вчених-математиків та економістів отримали подальший розвиток як математична теорія лінійного та нелінійного програмування, так застосування її методів у дослідженні різних економічних проблем.
Одночасно з Канторовичем і, очевидно, не залежно від нього методи лінійного програмування розроблялися зарубіжними, перш за все американськими вченими. В американській літературі перша робота, яка містила постановку транспортної задачі, була опублікована в 1941 році Ф. Л. Хічкоком. Основний метод розв’язання задач лінійного програмування – симплексний метод – був опублікований в 1949 році Дж. Данцигом. Подальший розвиток методи лінійного і нелінійного програмування отримали в роботах Форда, Фулкерсона, Куна, Лемке (двоїстий симплекс-метод), Гасса (параметричне програмування), Чарнеса (проблема виродження), Біла, Данскіна, Раднера (опукле програмування) та інших.
Дата добавления: 2018-05-13; просмотров: 697; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!