ЗАГАЛЬНА ПОСТАНОВКА ЗАДАЧІ
АНАЛІТИЧНІ МЕТОДИ розв’язування ЗДЛП
ГРАФІЧНИМ МЕТОДОМ
ДЕЯКІ ОСОБЛИВОСТІ Розв’язування ЗДЛП
Розв’язування задачі в середовищі Mathcad
|
Given
1. ОПР обмежена знизу й зверху
 |
2. Багатогранник розв’язків необмежений, однак на ньому існують точки, у яких цільова функція досягає свого оптимуму
 |
3. Багатогранник розв’язків необмежений, однак один з экстремумов існує
 |
Задача має так званий асимптотичнтй максимум, тобто 
.
4. Багатогранник розв’язків необмежений, задача має асимптотичні оптимуми
 |
Необхідно знайти оптимум наступної функції:
(3.10)
Задача вирішується при обмеженнях виду:
(3.10)
. (3.11)
Задача (3.10)–(3.11) може бути зведена до задачі лінійного програмування. Для цього необхідно ввести нові змінні, при цьому 
. У такому випадку здійснюється перехід в область нових змінних, на підставі співвідношень виду:
. (3.12)
З використанням нових змінних, задача (3.10)-(3.11) зводиться до наступної ЗЛП:
(3.12)
при обмеженнях виду:
(3.13)
і рівняннях зв'язків виду
(3.14)
Задача вирішується при умовах невід’ємності, що накладають на n змінних
;
. (3.15)
.
Задача (3.12)-(3.15) є задачею лінійного програмування, отже, розв’язуючи її відомими методами можна знайти відповідні розв’язки. При цьому, одержавши оптимальний план такої задачі, на підставі співвідношень (3.12) можна знайти оптимальний план вихідної задачі (3.10)-(3.11). Таким чином, можна вказати наступний алгоритм розв’язування ЗДЛП.
I. Вихідну ЗДЛП (3.10)-(3.11) зводять до ЗЛП (3.12)-(3.15).
II. Знаходять оптимальний план ЗЛП відомими методами.
III. Використовуючи співвідношення (3.12) знаходять оптимальний план вихідної задачі.
IV. Підставляючи значення xj, при у вираз для функції (3.10) отримують оптимальне значення цільової функції вихідної задачі.
Приклад. Знайти максимальне значення функції:
; (3.16)
(3.17)
. (3.18)
Зведемо дану задачу до ЗЛП, при цьому
. (3.19)
Далі вводимо нові змінні:
(3.20)
Тоді вихідна задача (3.16)-(3.18) зводиться до наступної ЗЛП
. (3.19)
Задача вирішується в рамках обмежень виду:
(3.20)
; (3.21)
; (3.22)
.
Задача (3.19)-(3.22) є ЗЛП і розв’язок її можна знайти методом штучного базису. Для цього формулюють наступну розширену задачу
;
;
;
.
Далі розширену задачу заносять у первісну симплексну таблицю
| з1 | з2 | з3 | з4 | з5 | з0 | |||||
| x1 | –1 | –11 | ||||||||
| x2 | –8 | |||||||||
| x3 | –1 | –9 | Þ | |||||||
| x4 | ||||||||||
| F | –2 | –1 | ||||||||
| f | –1 | –28 | ||||||||
| з2 | з3 | з4 | з5 | з0 | |||
| в1 | –1 | –11 | |||||
| x2 | –3 | ||||||
| x3 | –1 | –20 | Þ | ||||
| x4 | –1 | ||||||
| +3 | –2 | –22 | ||||
| f | –6 |
| з2 | з3 | з4 | з0 | |||
| в1 | –1 | –11 | ||||
| x2 | –3 | |||||
| в5 | –1 | –20 | Þ | |||
| x4 | –1 | |||||
|
| –2 | –22 | ||||
| f | –4 |
| з2 | з3 | з4 | ||||
| в1 | –27 | |||||
| в0 | –3 | |||||
| в5 | –45 | :(3) | Þ | |||
| x4 | –8 | –11 | ||||
|
| –57 | |||||
| f | –8 | –11 |
| з2 | з3 | з4 | |||||
| в1 | –9 | 8/3 | 11/3 | ||||
| в0 | –1 | 1/3 | 1/3 | ||||
| в5 | –15 | 17/3 | 20/3 | Þ | |||
| x4 | –8/3 | –11/3 | |||||
|
| –19 | 16/3 | 22/3 | ||||
| f | –8/3 | –11/3 | |||||
| з3 | з4 | |||
| в1 | ||||
| в0 | ||||
| в5 | Þ | |||
| в2 | –8/3 | –11/3 | ||
|
| 8/3 | 11/3 | ||
| f |
Далі розділивши останню таблицю на 10, одержують оптимальний план ЗЛП
| з3 | з4 | ||
| в1 | 9/10 | ||
| в0 | 1/10 | ||
| в5 | 15/10 | ||
| в2 | 1/10 | –8/30 | –11/30 |
|
| 19/10 | 8/30 | 11/30 |
Висновок: у процесі визначення первісного опорного плану робоча точка пошуку экстремума вийшла в ту вершину опуклого багатогранника, що є точкою максимуму.
.
З урахуванням того, що 
, знаходять оптимальний план ЗДЛП
.
розв’язування задачі в середовищі Mathcad: