Математичне програмування в економіці (стр. 4 из 6)
Як буде виготовлено 100 чоловічих костюмів, так х2 = 100 і з першого рівняння-обмеження отримаємо (х1 = 0)
у1 = 350 – 3,5х2 – х1; (1)у2 = 240 – 0,5х2 – 2х1; (2)
у3 = 150 – х2 – х1; (3)
що у1 = 0, тобто ресурсів шерстяної тканини не буде; з другого рівняння-обмеження отримаємо у2 = 240 – 0,5 × 100 – 2 × 0 = = 190 м шовкової тканини у запасах; з третього рівняння-обмеження отримаємо у3 = 150 – 100 – 0 = 50 людино - тижнів трудомісткості у запасах.
Прибуток складає Z = 10 × 0 + 20 × 100 = 2000 грн.; - Z = - 2000.
Цільова функція Z = 10 × х1 + 20 × х2 через нові вільні змінні (х1 = 0; у2 = 0) має вираз
40 40 40 30
Z = 10 х1 + 20 х2 = 10 × х1 + 2000 - ¾ у1 - ¾ х1 = 2000 - ¾ у1 + ¾ х1,
7 7 7 7
бо (з першого рівняння-обмеження) маємо:
х2 = 100 – у1 / 3,5 – х1 / 3,5.
Перетворимо систему рівнянь-обмежень, замінюючи х2 на його вираз:
х1 + 3,5 (100 – у1 / 3,5 – х1 / 3,5) + у1 = 350; (1¢)2 х1 + 0,5 (100 – у1 / 3,5 – х1 / 3,50) + у2 = 240; (2¢)
х1 + (100 – у1 / 3,5 – х1 / 3,50) + у3 = 150; (3¢)
х2 + у1 / 3,5 + х1 / 3,5 = 100 (4¢)
Другий опорний план задачи таким чином складає
х(2) = (0; 100; 0; 190; 50; 100); Z (х(2) ) = 2000;
де: х1 = 0; у1= 0 – вільні змінні, відповідає розв’язку задачі, якщо виробляються виключно чоловічі костюми (х2 = 100). Знов надамо цю інформацію у вигляді симплекс-таблиці.
Таблиця
| х1 | у1 | bі | |
| 13 ¾ 7 | 1 - ¾ 7 | 190 | у2 – залишки шовкової тканини |
| 5 ¾ 7 | 2 - ¾ 7 | 50 | у3 – залишки ресурсів праці |
| 2 ¾ 7 | 2 ¾ 7 | 100 | х2 – виробництво чоловічих костюмів |
| 30 ¾ 7 | 40 - ¾ 7 | - 2000 | - Z – цільова функція |
Кожен з елементів симплекс-таблиці має своє значення:
– у першому стовпці (х1) 13 / 7 – потрібна кількість шовкової тканини, потрібної на один жіночий костюм; 5 / 7 – потрібна кількість праці на один жіночий костюм; 30 / 7 – прибуток від одного жіночого костюма;
Дивлячись на цільову функцію
30 40
Z = 2000 + ¾ × х1 - ¾ × у1 ,
7 7
бачимо, що збільшення виготовлення жіночих костюмів може збільшити прибуток, бо х1 ³ 0 , а також 30 / 7 > 0.
Пригадуючи, що у1 = 0, знайдемо значення нової вільної змінної, яка задовольняє систему рівнянь-обмежень (2¢), (3¢), (1¢¢), а також у2 ³ 0 , у3 ³ 0 , х2 ³ 0 .
(2¢) дає, якщо у2 = 0, х1 » 102;
(3¢) дає, якщо у3 = 0, х1 = 70;
(1¢¢) дає, якщо х2 = 0, х1 =350;
Визначальними є обмеження на ресурси праці: , х1 = 70, у3 = 0 з рівняння (3¢).
Визначальний елемент симплекс-таблиці – це коефіцієнт у рівнянні (3¢), якій дорівнює (5/7), та відіграє роль нового центру, або ключового елементу.
Як буде виготовлено 70 жіночих костюмів, так х1 = 70 з рівняння (3¢) отримаємо у3 = 0 (нова базова змінна);
Третій опорний план задачі складає:
Х (3) = (70; 80; 0; 60; 0;); Z (3) = 2300 грн.;
Z (3) > Z (1);
де: у1 = 0; у3 = 0 - вільні змінні, відповідає розв’язку задачі, якщо виробляється 70 жіночих та 80 чоловічих костюмів. Надамо цю інформацію у вигляді симплекс-таблиці.
Таблиця
| у3 | у1 | Опорний розв’язок b1 | |
| 13 ¾ 5 | 21 - ¾ 35 | 60 | у2 – залишки шовкової тканини |
| 2 ¾ 5 | 14 - ¾ 5 | 80 | х2 – кількість чоловічих костюмів |
| 5 - ¾ 7 | 2 ¾ 5 | 70 | х1 – кількість жіночих костюмів |
| - 6 | 28 - ¾ 7 | -2300 | - Z – цільова функція |
Збільшити прибуток неможливо у зв’язку з тим, що вільні змінні (уі > 0), що наявні у цільовій функції мають від’ємні коефіцієнти у той же час, як самі вони додатні. Опорний план Х (3) є оптимальним.
Х* = ( х1* = 70? х2* = 80; у1 = 0; у2* = 60; у3 = 0);
залишки шовкової тканини складають 60 метрів, прибуток складає 2300 грн., як буде виготовлено 70 жіночих та 80 чоловічих костюмів.
Надамо звичайний вигляд симплекс-таблиці розв’язку задачі.
Таблиця 1 ітерація
| і | Базисні зміни | х1 | х2 | х3 | х4 | х5 | bі | Симплекс q = bі / аij | Контроль | |
| 1 | х3 | 1 а11 | 3,5 а12 | 1 а13 | 0 а14 | 0 а15 | 350 | 350/3,5=100 | 355,5 | |
| 2 | х4 | 2 а21 | 0,5 а22 | 0 а23 | 1 а24 | 0 а16 | 240 | 240/0,5=480 | 143,5 | |
| 3 | х5 | 1 а31 | 1 а32 | 0 а33 | 0 а34 | 1 а17 | 150 | 150/1=150 | 153 | |
| 4 | Z (х) | +10 с1 | +20 с2 | 0 ас3 | 0 с4 | 0 с5 | 0 | - | +30 | |
Z (х) = ( -Z); Z (х) – С0 – С1Х1 – С2Х2 – С3Х3 – С4Х4 – С5Х5 = 0;
Z = С0 + С1Х1 + С2Х2 + С3Х3 + С4Х4 + С5Х5 = 0 + 10Х1 + 10Х2 + 0 × Х3 + 0 × Х4+ 0 × Х5 = 0 × Х1 + 2 × Х2 ;
( -Z) = - 10 Х1 – 20 х2; ® min
Таблиця 2 ітерація
| j | Базисні змінні | х1 | х2 | х3 | х4 | х5 | bi | q = bi / aij | Контроль |
| 1 | х2 | 2 / 7 | 1 | 2/ 7 | 0 | 0 | 100 | 100/(2/7)=350 | 101 4/7 |
| 2 | х4 | 13 / 7 | 0 | -1/ 7 | 1 | 0 | 190 | 190/(13/7)»102 | 192 5/7 |
| 3 | х5 | 5 / 7 | 0 | -2/ 7 | 0 | 1 | 50 | 50/(5/7)=70 | 51 3/7 |
| 4 | Z (x) | 30 / 7 | 0 | -40/ 7 | 0 | 0 | -2000 | - | -2001 3/7 |
х2 = 100 – (2/7) х1 – (2/7)х3; Z (x) + (30/7) х1 – (40/7)х3 = -2000 ;
Z = 10х1 + 20 × (100 – (2/7)х1 – (2/7)х3 ) = 2000 + (30/7)х1 – (40/7)х3;
- Z = - 2000 + (40/7)х3 - (30/7)х1 = - 2000;
Таблиця 3 ітерація
| j | Базисні змінні | х1 | х2 | х3 | х4 | х5 | bi | q = bi / aij | Конт-роль |
| 1 | х2 | 0 | 1 | 14/ 35 | 0 | -2/5 | 80 | - | 81 |
| 2 | х4 | 0 | 0 | 21/35 | 1 | -13/5 | 60 | - | 59 |
| 3 | х1 | 1 | 0 | -2/ 5 | 0 | 7/5 | 70 | - | 72 |
| 4 | Z (x) | 0 | 0 | -28/ 7 | 0 | -6 | -2300 | - |
х1 = 70 + (2/5) х3 – (7/5)х5; Z (x) - (28/7) х3 – 6 × х5 = -2300 ;
Z = 2000 + (30/7) (70 + (2/5)х3 – (7/5)х5 ) – (40/7) х3= 2300 - 6х5 – (28/7)х3;
- Z = - 2300 + 6х5 + (28/7)х3 = - 2300; х3 = х5 = 0.
У цільовій функції усі вільні змінні від’ємні – опорний план Х* = (70; 80; 0; 60; 0) є оптимальним. Задача розв’язана.
Z*max = (-Z*)min = +2300.
Стереометрично ідея методу полягає у тому, що:
- знаходять будь-яку вершину багатогранника розв’язків;
- рухаються вздовж того з ребер, по якому функція зменшується (збільшується) до іншої вершини багатогранника розв’язків;
- як потрапляють у вершину, з якої у всі боки функція зростає (спадає), так знаходять мінімум (максимум).
Нагадаємо ще раз:
- якщо вектор розв’язків задовольняє усім обмеженням, так він має назву плану;
- якщо план відповідає вершині багатогранника розв’язків (усі вільні змінні дорівнюють нулеві), так він має назву опорного плану;
- якщо опорний план відповідає екстремальному значенню цільової функції, так він має назву оптимального плану.
Критерій оптимальності за симплекс-таблицею.
Якщо форма мінімізується (максимізується) і у рідку цільової функції відсутні додатні числа (від’ємні числа), за винятком стовпчика опорний розв’язок (b1), так опорний план є оптимальним.
Коефіцієнти рядка цільової функції інтерпретують як приріст цільової функції при збільшенні вільної невідомої на одиницю. Приріст додатній, якщо коефіцієнт від’ємний, і навпаки від’ємний, якщо коефіцієнт додатній.
Стовпець “j” є вирішальним, як у цьому стовпцю, оцінка коефіцієнта при невідомій у цільовій функції найбільша за модулем, тобто
½ Сj½ = max.
Змінну “xj” у вирішальному стовпцю знаходять за співвідношенням
bi
min ¾ = q, (fij > 0; bi ³ 0);
aij
яке має назву симплекса , що і дає у свою чергу назву методу. Відповідний елемент aij назву ключового елемента, або центру таблиці.
Вільну змінну, яка відповідає вирішальному стовпчику, залучають до базисних змінних, а базисну змінну, яка відповідає мінімальному симплексу, відповідно перетворюють на вільну змінну.