Лекції з методів оптимізації

n1.doc (8 стор.)
Оригінал


  1   2   3   4   5   6   7   8

Методи оптимізації


Побудова математичної моделі


Пошук оптимальних рішень


Коригування

моделі


Реальна задача


Видача рекомендацій


Схема дослідження


Математична модель

Математична модель - опис розв'язуваної задачі в математичних термінах.

Математична модель описує досліджувану систему і дозволяє виразити її ефективність у вигляді цільової функції

W = f (X, Y),

де X = (x 1,..., x n) - керовані змінні,

Y = (y 1,..., y m) - некеровані змінні (Вихідні дані).

Зв'язок між змінними X і вихідними даними Y виражається за допомогою обмежень

(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-і роки

З'явилася загальна теорія двоїстості для задач опуклої оптимізації (Гольштейн Є.Г.), з'явилися праці з стохастичної оптимізації.

Історія математичного програмування
Велися розробки ПЗ для реалізації симплекс - методу для вирішення задачі ЛП (І.В. Романовський, О.О. Станевічус, та ін, доцент УГАТУ А.П. Мартинов).

З'явилися чисельні методи вирішення спеціальних класів задач ЛП:

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

Практичне застосування ЛП для соціалістичної економіки.

9. 70-80-ті роки

Вводиться нове поняття складності оптимізаційної задачі: встановлені нижні межі для різних класів оптимізаційних задач (Юдін Д.Б. та ін.)

Було встановлено: якщо метод має складність, збігається з нижньою межею, то він оптимальний, тобто не існує методів, які вирішують всі задачі класу швидше (відносно порядку).

Побудований ітеративний метод розв'язування задачі ЛП, для якої була доведена поліноміальна збіжність (Хачіян Л.Г.)
Література
1.Канторовіч Л.В. Математичні методи організації і планування виробництва. Л.: Вид-во Ленінградського університету, 1939, 64с.

2. Юдін Д.Б., Гольштейн Є.Г. Завдання і методи лінійного програмування. М.: Радянське радіо. 1964, 491с.

3. Карманов В.Г. Математичне програмування. М.: Наука, 1975, 272с.

4. Мухачева Е.А., Рубінштейн Г.Ш. Математичне програмування. Новосибірськ: Изд-во «Наука», Сибірське відділення, 1987, 272с.

5. Мухачева Е.А. Раціональний розкрій промислових матеріалів. Застосування АСУ. М.: Машинобудування, 1984,174 с.

6. Мухачева Е.А., Верхотуров М.А., Мартинов В.В. Моделі та методи розрахунку розкрою-упаковки геометричних об'єктів. Уфа: УГАТУ, 1998, 217с.

7. Мухачева Е.А., Валєєва А.Ф., Картак В.М. Завдання двомірної упаковки в контейнери: нові підходи до розробки методів локального пошуку оптимуму. Москва: Изд-во МАІ, 2004, 192с.

Головні наукові центри з математичного програмування
Москва: МГУ, Центральний економіко-математичний інститут, Обчислювальний центр
Київ: Інститут кібернетики ім. В.М. Глушкова
Новосибірськ: Інститут математики ім. С.Л. Соболєва Сибірського відділення РАН, Новосибірський державний університет
Ленінград: Ленінградський державний університет

Завдання планування виробництва

Вид

сировини



Норми витрати сировини (кг) на один виріб



Загальна кількість сировини на складі (кг)

А

В



I

II

III


12

4

13


4

4

12


300

120

252

Прибуток від
реалізації

одного

вироби (у.о.)


30


40



Навчальний матеріал
© ukrdoc.com.ua
При копіюванні вкажіть посилання.
звернутися до адміністрації