Математичне програмування в економіці
Методическое пособие - Математика и статистика
Другие методички по предмету Математика и статистика
ільки функціональні обмеження ресурсів.
х1 + 3,5 х2 350;
2 х1 + 0,5 х2 240;
х1 + х2 150;
х1 0;
х2 0.
Z = f (x) = 10 x1 + 20 x2 ; Z max;
( -Z = - f (x) = - 10 x1 - 20 x2 - 0 x4 - 0 x5; min ).
Розвязок задачі. Перетворимо функціональні обмеження-нерівності на обмеження-рівності шляхом введення у обмеження-нерівності невідємних вільних невідомих y1, y2, y3 (хоча можливо було б і х3, х4, х5 ).
х1 + 3,5 х2 + у1 = 350; (1)
2 х1 + 0,5 х2 + у2 = 240; (2)
х1 + х2 + у3 = 150; (3)
х1 0; х2 0; у1 0; у2 0; у3 0.
Перед початком виробництва х1 = х2 = 0 , тоді
у1 = 350; наявність ресурсу шерсть;
у2 = 240; наявність ресурсу шовк;
у3 = 150; наявність ресурсу трудомісткість.
Прибуток на початок справи Z = 10 0 + 20 0 = 0;
Кількість рівнянь-обмежень m = 3; кількість невідомих х1, х2, у1, у2, у3 n = 5; кількість вільних змінних (n m) = 5 3 = 2;
базисне припустиме рішення задачі це таке, у якому усі вільні змінні дорівнюють нулеві (вершина або грань многокутника розвязків). Тому початковий опорний план складає
х (1) = (0; 0; 350; 240; 150) ; Z ( х(1) ) = 0;
де : х1 = 0; х2 = 0 вільні змінні, відповідає рішенню задачі, коли продукція не виробляється. Надамо цю інформацію у вигляді симплекс-таблиці
Таблиця
х1х2х31
2
13,5
0,5
1350
240
150у1 шерстяна тканина
у2 шовкова тканина
у3 наявність ресурсів праці10200- Z = - дохід від виробництва
Z = 10х1 + 20х2 = 10 0 + 20 0 = 0; - Z = 0;
Виробництво чоловічих костюмів х2 дає більший дохід, так почнемо його збільшувати, залишаючи х1 = 0, але існують обмеження. З першої строки симплекс-таблиці (першого рівняння-обмеження на наявність шерстяної тканини) чоловічих костюмів можливо виготовити 350 / 3,5 = 100; з другої строки симплекс-таблиці (другого рівняння-обмеження на наявність шовкової тканини) чоловічих костюмів можливо виготовити 240 / 0,5 = 480 штук; з третьої строки симплекс-таблиці (третього рівняння-обмеження на наявність ресурсів праці) чоловічих костюмів можливо виготовити 150 / 1 = 150 одиниць. Визначальним є обмеження на шерстяну тканину, тобто найбільша кількість чоловічих костюмів (за умов відсутності жіночих х1 = 0) дорівнює найменшому з трьох значень 100; 480; 150; х2 = 110. Визначальний елемент симплекс-таблиці коефіцієнт у першому рівнянні при другій вільній змінній (х2), який дорівнює3,5; та має назву центру (ключового елемента).
Як буде виготовлено 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у1bі13
71
-
7
190
у2 залишки шовкової тканини5
72
-
7
50
у3 залишки ресурсів праці2
72
7
100
х2 виробництво чоловічих костюмів30
740
-
7
- 2000
- Z цільова функція
Кожен з елементів симплекс-таблиці має своє значення:
- у першому стовпці (х1) 13 / 7 потрібна кількість шовкової тканини, потрібної на один жіночий костюм; 5 / 7 потрібна кількість праці на один жіночий костюм; 30 / 7 прибуток від одного жіночого костюма;
Дивлячись на цільову функцію
30 40
Z = 2000 + х1 - у1 ,
- 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Опорний розвязок b113
521
-
35
60
у2 залишки шовкової тканини2
514
-
5
80
х2 кількість чоловічих костюмів5
-
72
5
70
х1 кількість жіночих костюмів
- 628
-
7
-2300
- Z цільова функція
Збільшити прибуток неможливо у звязку з тим, що вільні змінні (уі 0), що наявні у цільовій функції мають відємні коефіцієнти у той же час, як самі вони додатні. Опорний план Х (3) є оптимальним.
Х* = ( х1* = 70? х2* = 80; у1 = 0; у2* = 60; у3