- •Розділ 1. Предмет, особливості та сфери застосування математичного програмування в економіці. Класифікація задач
- •1.1. Предмет курсу «математичне програмування»
- •1.2. Найпростіша класифікація задач математичного програмування
- •1.3. Програма дисципліни «Оптимізаційні методи та моделі»
- •Тема 9. Задачі динамічного програмування
- •Тема 10. Моделі та методи стохастичного програмування
- •Тема 11. Елементи теорії ігор
- •Розділ 2. Загальна задача лінійного програмування та методи її розв’язування
- •2.1. Загальна математична модель лінійного програмування
- •2.2. Форми запису задач лп
- •2.3. Геометрична інтерпретація злп
- •2.4. Основні аналітичні властивості розв’язків задач лінійного програмування
- •2.5. Графічний метод розв’язування задач лінійного програмування
- •2.5.1. Основи графічного методу
- •2.5.2. Навчальні завдання. Розв’язування задач графічним методом
- •2.6. Симплексний метод розв’язування задач лп
- •2.6.1. Теоретичні відомості
- •2.6.2. Навчальні завдання розв’язування задач симплекс-методом
- •Розділ 3. Двоїстість у лінійному програмуванні
- •3.1. Поняття двоїстості. Правила побудови двоїстих задач
- •3.2. Теорема двоїстості
- •3.3. Навчальні завдання
- •Розділ 4. Економічна інтерпретація двоїстих задач. Аналіз оптимальних планів лінійних економіко-математичних моделей
- •4.1. Економічна інтерпретація двоїстої задачі
- •4.2. Навчальні завдання
- •Розділ 5. Транспортна задача
- •5.1. Постановка транспортної задачі
- •5.2. Метод потенціалів
- •5.3. Навчальні завдання
- •Розділ 6. Вибрані розділи математичного програмування
- •6.1. Цілочислове програмування
- •6.1.1. Постановка задачі
- •6.1.2. Метод Гоморі
- •6.1.3. Метод «віток і меж»
- •6.1.4. Приклади цілочислових економічних задач
- •6.2. Дробово-лінійне програмування
- •6.2.1. Постановка задачі та алгоритм розв’язування
- •6.2.2. Приклади дробово-лінійних задач
- •6.3. Нелінійне програмування
- •6.3.1. Постановка задачі
- •6.3.2. Труднощі розв’язування задач нелінійного програмування
- •6.3.3. Метод множників Лагранжа
- •6.3.4. Приклади задач нелінійного програмування
- •6.4. Динамічне програмування
- •6.4.1. Сутність динамічного програмування. Принципи оптимальності
- •6.4.2.Методикарозв’язування динамічних задач
- •6.4.3. Приклади розв’язування динамічних задач
- •6.5 Теорія ігор
- •6.5.1. Основні поняття теорії ігор
- •6.5.2. Зведення матричної гри до задачі лінійного програмування
- •6.6. Стохастичне програмування
- •6.6.1 Постановка задач і методи розв’язування
- •6.6.2. Приклади стохастичних економічних задач
6.2. Дробово-лінійне програмування
6.2.1. Постановка задачі та алгоритм розв’язування
Розв’язуючи економічні задачі, часто за критерій оптимальності беруть показники рентабельності, продуктивності праці тощо, які математично подаються дробово-лінійними функціями. Загальну економіко-математичну модель у цьому разі записують так:
за умов
,
.
Припускають, що знаменник цільової функції в області допустимих розв’язків системи обмежень не дорівнює нулю.
Алгоритм розв’язування задачі дробово-лінійного програмування передбачає зведення її до задачі лінійного програмування. Щоб виконати таке зведення, позначимо
,
зробимо заміну змінних
.
і запишемо економіко-математичну модель:
за умов
,
,
.
Дістали задачу лінійного програмування, яку можна розв’язати симплексним методом. Нехай оптимальний план
Оптимальні значення x0j знайдемо за формулою
.
6.2.2. Приклади дробово-лінійних задач
Задача 6.14.
Показник |
Діяльність з вирощування |
Ресурс | ||||||
озимої пшениці, га |
цукрових буряків, га |
корів продуктивністю, кг |
кормових культур, га | |||||
5000 |
4500 |
4000 |
3500 | |||||
Урожайність, т/га |
4 |
35 |
— |
— |
— |
— |
6 |
— |
Собівартість, грн./т |
600 |
250 |
600 |
700 |
800 |
9000 |
200 |
— |
Ціна, грн./т |
800 |
300 |
1000 |
1000 |
1000 |
1000 |
— |
— |
Вихід кормів, тон кормових одиниць/га |
0,8 |
2,0 |
— |
— |
— |
— |
6 |
— |
Витрати живої праці, людино-днів/га |
4 |
25 |
6 |
6 |
6 |
6 |
3 |
26 000 |
Витрати механізованої праці, людино-днів/га |
2 |
8 |
3 |
3 |
3 |
3 |
2 |
11 000 |
Частка корів у стаді |
— |
— |
0,1 |
0,2 |
0,3 |
0,4 |
— |
|
Потреба в кормах, т/гол |
— |
— |
5 |
4,7 |
4,4 |
4,1 |
— |
— |
Акціонерне товариство має 2500 га ріллі.
Записати економіко-математичну модель і знайти оптимальну структуру виробництва.
Розв’язання.Введемо позначення:
х1 — площа посіву озимої пшениці, га;
х2 — площа посіву цукрового буряка, га;
х3 — площа посіву кормових культур, га;
х4 — кількість корів продуктивністю 5000 кг;
х5 — кількість корів продуктивністю 4500 кг;
х6 — кількість корів продуктивністю 4000 кг;
х7 — кількість корів продуктивністю 3500 кг.
Запишемо критерій оптимальності:
за розглянутих далі умов.
1. Обмеження за ресурсами.
1) Ріллі:
.
2) Живої праці:
.
3) Механізованої праці:
.
2. Обмеження сівозміни.
1) Посівна площа кормових має бути більша або дорівнювати площі під озимою пшеницею:
.
2) Посівна площа озимої пшениці має бути більша або дорівнювати площі під цукровими буряками:
.
3. Структура корів за продуктивністю.
1) Балансове рівняння щодо корів:
,
де — загальна кількість корів.
2) Частка корів продуктивністю 5000 кг:
.
3) Частка корів продуктивністю 4500 кг:
.
4) Частка корів продуктивністю 4000 кг:
.
5) Частка корів продуктивністю 3500 кг:
.
4. Забезпеченість корів кормами:
.
Невід’ємність змінних:
.
Щоб знайти розв’язок за цією моделлю, зробимо відповідну заміну й скористаємося симплексним методом:
.
Отже, маємо таку лінійну економіко-математичну модель:
за розглянутих далі умов.
1. ,
,
.
2. , або,
, або .
3. ,
,
,
,
.
4. .
5. .
Задача 6.15.
за умов
Розв’язання. Побудуємо на площині область допустимих розв’язків задачі — трикутник АВС.
Цільова функція задачі являє собою пряму, яка обертатиметься навколо початку системи координат залежно від змінюваних параметрів х1, х2 так, що точки А і С будуть точками максимуму і мінімуму функції. Виразимо х2 із цільової функції:
.
Кутовий коефіцієнт цільової функції
.
Розглянемо похідну
.
Оскільки при будь-якому значенні Z вона від’ємна, то функція RZ є спадною (зі зростанням Z кутовий коефіцієнт RZ зменшується), а графік цільової функції обертатиметься навколо початку координат за годинниковою стрілкою. Отже, точка С є точкою максимуму, а точка А — мінімуму досліджуваної задачі.
Знайдемо координати цих точок.
Точка А:
Звідси
Точка А має координати (6/7; 24/7).
Точка С:
Звідси
Точка С має координати (9/2; 1).
Знайдемо значення цільової функції в цих точках:
Результати (ZC > ZA) підтверджують, що оптимуми знайдено правильно: максимум досягається в точці С, а мінімум — у точці А.
Задача 6.16.
за умов
Розв’язування. Зведемо початкову задачу до задачі лінійного програмування згідно з розглянутими раніше правилами.
Позначимо .
Введемо нові змінні:
, .
Дістанемо задачу лінійного програмування:
за умов
Розв’яжемо задачу симплексним методом. У перше та останнє обмеження введемо штучні змінні y6, та y7.
Маємо оптимальний розв’язок перетвореної задачі:
, ,,.
Знайдемо оптимальний розв’язок початкової задачі, враховуючи, що :
; ;;
; .
Отже, ,
.