- •Міністерство освіти і науки, молоді та спорту україни
- •ЕкономіКо-математиЧні моделі та методи: оптимізаційні моделі та методи
- •Класифікація оптимізаційних методів та моделей
- •1.1. Постановка задачі лінійного програмування
- •Алгоритм графічного методу розв’язання злп
- •1.3. Симплекс-метод розв’язання задачі лінійного програмування
- •Алгоритм симплекс-метода розв’язання злп
- •Критерій оптимальності опорного плану:
- •Правила переходу до наступної симплекс-таблиці
- •1.4. Цілочислове програмування
- •Контрольні питання до змістового модуля і
- •2.1. Двоїста задача лінійного програмування
- •2.2. Елементи теорії матричних ігор
- •Алгоритм принципу максиміну (мінімаксу)
- •Розв’язання. Ця матрична гра має розмірність (3х4), тобто гравець а має три стратегії, а гравець в – чотири. Запишемо її в нормальній формі.
- •Послідовність дій при розв’язанні гри
- •Контрольні питання до змістового модуля іі
- •3.1. Дробово-лінійне програмування
- •Правила розв’язання задачі дробово-лінійного програмування графічним методом
- •3.2. Параметричне програмування
- •Алгоритм розв’язання задачі параметричного програмування
- •3.3. Динамічне програмування
- •Алгоритм розв’язання задачі динамічного програмування
- •Контрольні питання до змістового модуля ііі
- •4.1. Транспортна задача
- •Алгоритм методу потенціалів:
- •Критерій оптимальності плану перевезень
- •4.2. Ускладнена транспортна задача
- •4.3. Задача про призначення
- •Алгоритм методу Фогеля
- •Алгоритм угорського методу розв’язання задачі про призначення
- •Контрольні питання до змістового модуля іv
- •Індивідуальні завдання для самостійної роботи зі змістового модулю і
- •Індивідуальні завдання для самостійної роботи зі змістового модулю іі
- •Індивідуальні завдання для самостійної роботи зі змістового модулю ііі
- •Індивідуальні завдання для самостійної роботи зі змістового модулю іv
- •Література
- •Предметний покажчик
Класифікація оптимізаційних методів та моделей
Умовно оптимізаційні методи та моделі, які полягають в дослідженні функції на екстремум, на змінні якої накладені певні обмеження, можна розділити на завдання:
детермінованого і стохастичного програмування (залежно від ймовірнісного характеру початкових параметрів моделі);
динамічного і статичного програмування (залежно від обліку чинника часу);
лінійного і нелінійного програмування (залежно від виду цільової функції і обмежень).
Задачі, в яких критерій оптимальності не є випадковою функцією параметрів, а параметри також не є випадковими величинами, називають детермінованими. Наприклад, якщо в економіко-математичній моделі величини задані своїми математичними очікуваннями, то така задача є детермінованою.
Задачі, в яких критерій оптимальності є випадковою функцією параметрів, тобто включають невизначеність, називають стохастичними. Задачі, в яких знаходження оптимального рішення можна розглядати як миттєвий акт, називають статичними.
Задачі, в яких знаходження оптимального рішення економіко-математичної моделі можна розглядати не як застигле завдання, а в динаміці, знаходячи рішення на декілька періодів часу, називають динамічними. У динамічному програмуванні розглядають методи, що дозволяють шляхом багатокрокової оптимізації отримати загальний оптимум. Наприклад, якщо суб’єкт в ході ухвалення рішення змінює свій інформаційний стан, отримуючи або втрачаючи інформацію, то в цьому випадку рішення доцільно ухвалювати поетапно (багатокрокове рішення). Наприклад, якщо розглядається план розвитку підприємства до 2020 р. повинні бути обґрунтовані значення відповідних мікроекономічних показників не тільки на 2020 р., а і на всі проміжні роки, тобто врахована динаміка розвитку господарської діяльності даного підприємства.
Задачі, в яких критерій оптимальності (цільова функція) і система обмежень є лінійними, називають задачами лінійного програмування (ЗЛП). Інакше виникає задача нелінійного програмування. Важливою перевагою задач лінійного програмування є те, що для їх рішення розроблено універсальний метод – симплекс-метод. Для деяких класів ЗЛП розроблено ефективніші методи рішення. Наприклад, розподільчі задачі можна розв’язати симплекс-методом, проте ефективнішим для їх розв’язання є метод потенціалів.
Лінійні моделі часто є неадекватними природі модельованого об’єкту або процесу, тому доводиться будувати нелінійні моделі. Розв’язувати нелінійні завдання складніше, ніж лінійні, оскільки немає універсальних методів вирішення таких завдань. Для деяких видів нелінійних завдань розроблено чисельні спеціальні ефективні методи рішення, такі як метод більш швидкого спуску, метод дроблення кроку. Проте, на практиці частіше використовують лінійні економіко-математичні моделі. Часто нелінійні залежності апроксимують лінійними. Моделі лінійного програмування знаходять широке застосування при рішенні планових завдань в різних сферах господарської діяльності.
Задачі, в яких критерій оптимальності є сумою функцій, кожна з яких залежить тільки від однієї змінної, називають задачами сепарабельного програмування.
Задачі, в яких на змінні накладена умова цілочисловості, називають задачами цілочислового програмування. Багато економічних завдань характеризуються тим, що обсяги керованих ресурсів можуть приймати тільки цілі значення, такі як автомобілі, побутова техніка і інші об’єкти.
Задачі, в яких критерій оптимальності є опуклою функцією, називають задачами опуклого програмування. Для таких задач існує ряд ефективних і обґрунтованих методів їх рішення. ЗЛП є окремим випадком задач опуклого програмування.
Задачі, в яких критерій оптимальності є квадратичною функцією і система обмежень лінійна, називають задачами квадратичного програмування.
Розглядають так само окремі класи задачі лінійно-дробового програмування, коли система обмежень є лінійною, а цільова функція – лінійно-дробовою; задачі параметричного програмування, коли система обмежень є лінійною, а цільова функція містить параметр.
Особливий клас представляють задачі теорії ігор, які широко застосовуються в ринковій економіці. Серед них найбільш вивчені матричні парні ігри.
Змістовий модуль І |
Лінійне програмування |