Пряма задача Двоїста задача

Симетричні

Несиметричні

Наприклад:

Симетричні

Початкова задача Двоїста задача

F_max=3x₁+5x₂-7x₃+x₄ Z_min=15y₁+17y₂+12y₃

2x₁-5x₂+8x₃-x₄15; 2y₁+4y₂+y₃3;

4x₁+2x₂-x₃+9x₄17; -5y₁+2y₂+7y₃5;

x₁+7x₂-6x₃-4x₄12; 8y₁-y₂-6y₃-7;

x_j0, j=1,4 -y₁+9y₂-4y₃1;

y_i0, i=1,3

Несиметричні

Початкова задача Двоїста задача

Z_min=2x₁+x₂-x₃+x₄ F_max=12y₁+4y₂

x₁+2x₂+3x₃+4x₄=12; y₁+2y₂2;

2x₁-x₂+x₃-x₄=4; 2y₁-y₂1;

x_j0, j=1,4 3y₁+y₂-1;

4y₁-y₂1;

y_іє(-;+)

4.2 Теореми двоїстості

Теорема 1. Якщо одна з пари двоїстих задач має оптимальний план, то інша задача також має оптимальний план, причому значення цільових функцій дорівнюють, тобто F_max=Z_min, і навпаки.

Якщо цільова функція однієї з пари двоїстих задач не обмежена, то друга задача не має розв’язків.

Якщо пряма задача лінійного програмування має оптимальний план Х^, визначений симплекс-методом, то оптимальний план двоїстої задачі Y^ визначається зі співвідношення Y^=CB^-1, де С- вектор-рядок, що складається з коефіцієнтів цільової функції прямої задачі при змінних, які є базисними в оптимальному плані; D^-1- матриця, обернена до матриці D, складеної з базисних векторів оптимального плану, компоненти яких узято з початкового опорного плану задачі. Обернена матриця D^-1 завжди міститься в останній симплекс-таблиці в тих стовпчиках, де в першій таблиці містилася одинична матриця.

Теорема 2. Якщо в результаті підстановки оптимального плану прямої задачі в систему обмежень цієї задачі і-те обмеження виконується як строга нерівність, то відповідний і-й компонент оптимального плану двоїстої задачі дорівнює нулю.

Якщо і-й компонент оптимального плану двоїстої задачі додатний, то відповідне і-те обмеження прямої задачі виконується для оптимального плану як рівняння.

Теорема 3. Двоїста оцінка характеризує приріст цільової функції, який зумовлений малими змінами вільного члена відповідного обмеження.

Економічний зміст третьої теореми двоїстості полягає в тому, що відповідна додатна оцінка показує зростання значення цільової функції прямої задачі, якщо запас відповідного дефіцитного ресурсу збільшується на одну одиницю.

Наприклад:

1. До даної задачі скласти двоїсту, розв’язати пряму задачу симплекс-методом та за першою теоремою двоїстості знайти розв’язок двоїстої задачі.

Z_min=2x₁+8x₂+x₃-2x₄

x₁+x₃=3,

x₂-x₃+x₄=5,

6x₂+x₃+x₅=9,

x_j0, j=1,5.

Розв’язування:

Так як початкова задача записана в канонічній формі - двоїста несиметрична, отже двоїсті змінні

y_іє(-;+),і=1,3.

F_max=3y₁+5y₂+9y₃

y₁2,

y₂+6y₃8,

y₁-y₂+y₃1,

y₂-2,

y₃0.

Розв’яжемо початкову задачу за допомогою симплекс-методу:

	2	8	1	-2	0
Сбаз	х1	х2	х3	х4	х5	bi	хбаз
2 -2 0	1 0 0	0 1 6	1 -1 1	0 1 0	0 0 1	3 5 9	х1х3 х4 х5
zj	2	-2	4	-2	0	-4
j=zj-cj	0	-10	3	0	0	-4
1 -2 0	1 1 -1	0 1 6	1 0 0	0 1 0	0 0 1	3 8 6	х3 х4 х5
zj	-1	-2	1	-2	0	-13
j=zj-cj	-3	-10	0	0	0	-13

Отже оптимальний план початкової задачі Z_min=-13,X^=(0;0;3;8;6). За першою теоремою двоїстості оптимальний план двоїстої задачі знаходиться в останній симплекс-таблиці у рядку z_j, в тих стовпчиках, де в першій таблиці містилася одинична матриця. Тобто F_max=-13,Y^=(-1;-2;0)

Відповідь: Z_min= F_max =-13, X^=(0;0;3;8;6), Y^=(-1;-2;0).

2. До даної задачі скласти двоїсту, розв’язати двоїсту задачу за допомогою графічного методу, та за другою теоремою двоїстості знайти оптимальний план початкової задачі:

Z_min=2x₁+3x₂+x₃+2x₄+x₅

6x₁+3x₂+x₃+4x₄+x₅1,

4x₁+12x₂-x₃+x₄1,

x_j0, j=1,5

Двоїста задача:

F_max=y₁+y₂

6y₁+4y₂2,

3y₁+12y₂3,

y₁-y₂1,

4y₁+y₂2,

y₁1,

y₁,y₂0

Розв’яжемо двоїсту задачу за допомогою графічного методу, тобто побудуємо многокутник розв’язків та знайдемо його вершину, в якій буде досягатися максимум цільової функції.

l₁: y₂=1/2 - 3y₁/2, (0;1/2),(1;-1);

l₂: y₂=1/4 - y₁/4, (0;1/4), (1;0);

l₃: y₂=y₁-1, (0;-1), (1;0);

l₄: y₂=2-4y₁, (0;2), (1;-1);

l₅: y₁=1.

Рис. 7

Многокутник розв’язків ОАВС, максимальне значення цільова функція буде досягати у вершині В многокутника розв’язків. В=l₁∩l₂,Розв’яжемо систему рівнянь:

6y₁+4y₂=2 |:2 3y₁+2y₂=1 y₁=1/5

3y₁+12y₂=3  3y₁+12y₂=3  y₂=1/5

Таким чином розв’язок двоїстої задачі F_max=1/5 +1/5 =2/5,Y^=(1/5;1/5). Для знаходження оптимального плану початкової задачі підставимо значення двоїстих змінних в обмеження двоїстої задачі та визначимо які із початкових змінних більше нуля, та які дорівнюють нулю.

6/5 +4/5=10/5=2, 2=2  x₁>0;

3/5 +12/5 =15/5=3, 3=3  x₂>0;

1/5 -1/5=0, 0<1  x₃=0;

4/5 +1/5=1, 1<2  x₄=0;

1/5<1  x₅=0.

До системи рівнянь початкової задачі підставимо х₃=х₄=х₅=0, в результаті одержимо систему:

6х₁+3х₂=1, 6х₁+3х₂=1 х₁=3/20

4х₁+12х₂=1  х₁+3х₂=1/4  х₂=1/30

Z_min=6/20 +3/30=2/5

Відповідь: Z_min= F_max=2/5,Х^=(3/20;1/30;0;0;0), Y^=(1/5;1/5).