Математичне програмування в економіці (стр. 5 из 6)
Елементи симплексної строки нової таблиці дорівнюють елементам старої таблиці, поділеним на “ aij” – ключовий елемент (центр). Усі інші елементи вирішального стовпця прирівнюють до “0” (за виключенням ключового, якій дорівнює одиниці) шляхом жорданового перетворення; це стосується також цільової функції.
Можливі випадки розв’язку задачі лінійного програмування симплексним методом.
Нескінченна множина оптимальних планів можлива, якщо у строці цільової функції оптимального плану хоча б одна вільна змінна має нульову оцінку (обмеження паралельне цільовій функції). Оптимальне рішення у цьому випадку вирождене, тобто ранг системи рівнянь-обмежень більший за кількість ненульових координат вектора розв’язків.
Необмеженість задачі лінійного програмування виникає, як у якомусь стовпчику змінних у випадку мінімізації “сj” > 0 , а усі елементи таблиці “аij” £ 0; у випадку максимізації “сj” < 0, а усі “аij” £ 0. Це позначає, що область припустимих розв’язків задачі не обмежена знизу (мінімізація) або зверхне (максимізація).
Послідовність використання симплекс-методу:
- звести задачу лінійного програмування до задачі мінімізації у канонічній формі (обмеження-рівняння; bі ³ 0);
- поділити змінні на базисні та вільні і отримати базисне припустиме рішення (базисні змінні невід’ємні; вільні змінні дорівнюють нулеві);
- знайти вираз базисних змінних та цільової функції через вільні змінні;
- за знаком коефіцієнтів при невідомих (сj £ 0) у цільовій функції з’ясувати, чи є рішення оптимальне
Z = с0 + с1х1 + с2х2 + . . . + сnхn ; (cj ³ 0 – мінімізація); або яку вільну змінну можливо підвищити від нуля та перевести у базис і відповідно, яку базисну змінну перевести у вільні змінні;
- знайти мінімальне додатне співвідношення “bi” вільних членів рівнянь-обмежень до коефіцієнтів “aij” при новій вільній змінній, тобто з’ясувати, яку базисну змінну необхідно перевести у вільні змінні;
- перетворити умови-обмеження та цільову функцію у вираз в залежності від нових вільних змінних.
Приклад.
Розглянемо розв’язання задачі лінійного програмування, якщо у обмеженнях є нерівності двох напрямків. Потрібно максимізувати функцію
Z = 4х1 + 2х2 – х3,
за умов обмежень
х1 + х2 + х3 ³ 8;х2 + х3 £ 10;
х1 + х2 + 2х3 £ 30;
Перетворимо першу нерівність за допомогою змінної х4
х1 + х2 + х3 - х4 £ 8;
До цих трьох обмежень додамо штучні змінні у1, у2, у3 (х5, х6, х7). Цільова функція набуває вигляду
Z = 4х1 + 2х2 – х3 + 0 × х4;
обмеження:
х1 + х2 + х3 – х4 + у1 + 0 × у2 + 0 × у3 = 8;0 × х1 + х2 + х3 + 0 × х4 + 0 × у1 + у2 + 0 × у3 = 10;
х1 + х2 + 2х3 + 0 × х4 + 0 × у1 + 0 × у2 + у3 = 30;
Вектори у1 ( 0 ); у2 ( 1 ); у3 ( 0 ) утворюють базис
тримірний у загальному симівимірному просторі х1, х2, х3, х4, у1, у2, у3.
Кількість невідомих n = 7; обмежень m = 3; вільних змінних n – m = 7 – 3 = 4.
Базові змінні у1, у2, у3; вільні змінні х1, х2, х3, х4. Базове опорне рішення
х (0; 0; 0; 0; 1; 1; 1), Z (х) = 0.
Розв’язок задачі надамо у вигляді симплекс-таблиці.
Таблиця
| і | базисні змінні | х1 | х2 | х3 | х4 | у1 | у2 | у3 | bi | q=bi/fij |
| 1 | у1 | 1 | 1 | 1 | -1 | 1 | 0 | 0 | 8 | 8/1 |
| 2 | у2 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 10 | 10/1 |
| 3 | у3 | 1 | 1 | 2 | 0 | 0 | 0 | 1 | 30 | 30/1 |
| 4 | -Z | 4 | 2 | -1 | 0 | 0 | 0 | 0 | 0 | |
| 1 | х2 | 1 | 1 | 1 | -1 | 1 | 0 | 0 | 8 | -8/1 |
| 2 | у2 | -1 | 0 | 0 | 1 | -1 | 1 | 0 | 2 | 2/1 |
| 3 | у3 | 0 | 0 | 1 | 1 | -1 | 0 | 1 | 22 | 22/1 |
| 4 | -Z | 2 | 0 | -3 | 2 | -2 | 0 | 0 | -16 | |
| 1 | х2 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 10 | 10/1 |
| 2 | х4 | -1 | 0 | 0 | 1 | -1 | 1 | 0 | 2 | 2/-1 |
| 3 | у3 | 1 | 0 | 1 | 0 | 0 | -1 | 1 | 20 | 20/1 |
| 4 | -Z | 4 | 0 | -3 | 0 | 0 | -2 | 0 | -20 | |
| 1 | х2 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 10 | 10/1 |
| 2 | х4 | 0 | 0 | 1 | 1 | -1 | 0 | 1 | 22 | 22/0 |
| 3 | х1 | 1 | 0 | 1 | 0 | 0 | -1 | 1 | 20 | 20/-1 |
| 4 | -Z | 0 | 0 | -7 | 0 | 0 | 2 | -4 | -100 | |
| 1 | у2 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 10 | |
| 2 | х4 | 0 | 0 | 1 | 1 | -1 | 0 | 1 | 22 | |
| 3 | х1 | 1 | 1 | 2 | 0 | 0 | 0 | 1 | 30 | |
| 4 | -Z | 0 | -2 | -9 | 0 | 0 | 0 | -4 | -120 |
Х* (30; 0; 0; 22; 0; 10; 0); Z = 4х1 + 2х2 – х3 = 4 × 30 = 120.
Z* = 120 – 2х2 – 9х3 – 4у3 = 120.
Тема 4. Теорія двоїстості та двоїсті оцінки в аналізі розв’язків лінійних оптимізаційних моделей
Основна та двоїста задачі як пара взаємноспряжених задач лінійного програмування.
Дві задачі лінійного програмування називаються взаємно двоїстими, якщо виконуються такі умови:
1. матриці системи обмежень двох задач є транспонованим, одна відносно другої;
2. система обмежень складається з нерівностей, які в обох задачах направлені у протилежні боки;
3. коефіцієнти оптимізуючої форми однієї задачі є вільними членами системи обмежень другої задачі і навпаки;
4. форми в обох задачах оптимізуються протилежно – перша на максимум, друга на мінімум.
Зв’язок розв’язків взаємноспряжених задач лінійного програмування полягає у тому, що розв’язуючи симплексним методом одну з них, автоматично отримують розв’язок другої задачі. Оптимальні розв’язки двоїстих задач збігаються.
Економічна інтерпретація двоїстої задачі лінійного програмування
Розглянемо приклад виробничої задачі.
Виробництво може виготовляти при різновиди продукції. Обсяг ресурсів обмежений, вартість продукції та витрати на кожен з різновид продукції відомі і наведені у таблиці.
Таблиця
| Ресурси | Продукція, хj | Обсяг ресурсів | Варт. од. ресурсу, уі | ||
| х1 | х2 | х3 | |||
| Робоча сила, людино-год. | 15 а11 | 20 а12 | 25 а13 | 1200 b1 | у1(х4) |
| Сировина, m | 2 а21 | 3 а22 | 2,5 а23 | 150 b2 | у2(х5) |
| Енерговитрати, кВт – год. | 35 а31 | 60 а32 | 60 а33 | 3000 b3 | у3(х6) |
| Вартість одиниці продукції | 300 с1 | 250 с2 | 450 с3 | - | - |
(у4) (у5) (у6)
Потрібно знайти кількість кожного з різновидів продукції, які забезпечують найбільшу вартість загальної продукції. З економічної точки зору вартість ресурсів, використаних на виготовлення одиниці продукції, не може бути меншою, ніж вартість самої одиниці продукції, інакше це позначає, що вартість частини одиниці продукції виникає з повітря. Для якої завгодно виробничої програми вартість виробленої продукції не перевищує загальної вартістю наявних ресурсів. Проаналізуємо отримані результати. Розв’язок прямої задачі вказує на то, що необхідно виробити першої продукції х1 = 60 одиниць, третьої продукції х3 = 12 одиниць, другу продукцію виробляти непотрібно (х2 = 0). Використані повністю ресурси робочої сили (х4 = 0) та сировини (х5 = 0), залишок енерговитрат складає х6 = 180 кВт – год. Розв’язок двоїстої задачі вказує на те, що ресурси перший (у1 > 0) та другий (у2 > 0) використані повністю, третій ресурс надмірний (у3 = 0). Додаток першого обмеженого ресурсу на одиницю збільшує цільову функцію прямої задачі на 12 одиниць (зростає вартість, бо у1 = 12), другого обмеженого ресурсу на одиницю збільшує Z(x), цільову функцію, на 60 одиниць (у2 = 60). Збільшення третього ресурсу (необмеженого) – енерговитрату околиці оптимального плану не викликає змін цільової функції. Як уn = 0, у6 = 0, так це позначає, що виробництво продукції першої та третьої не є збитковим; у5 = 170 – це позначає, що виготовлення одиниці другої продукції викликає збиток у 170 грошових одиниць. перевіримо це таким чином: вартість ресурсів на другу продукцію складає