<< Содержание < Предыдущая
3.3.1. Перша теорема двоїстості
Теорема (перша теорема двоїстості). Якщо одна з пари спряжених задач має оптимальний план, то й друга задача також має розв’язок, причому для оптимальних розв’язків значення цільових функцій обох задач збігаються, тобто
.
Якщо цільова функція однієї із задач необмежена, то спряжена задача також не має розв’язку*1.
*1: {Зауважимо, що коли одна із задач не має допустимого розв’язку, то двоїста до неї задача також може не мати допустимого розв’язку, тобто зворотне твердження щодо другої частини теореми в загальному випадку не виконується.}
Доведення. Допустимо, що початкова задача (3.1)—(3.3) має оптимальний план, який отриманий симплексним методом. Не порушуючи загальності, можна вважати, що останній базис складається з перших m векторів . Остання симплексна таблиця має вигляд:
Таблиця 3.1
і |
Базис |
Сб |
План |
с1 |
с2 |
... |
сm |
cm + 1 |
... |
cn |
x1 |
x2 |
... |
xm |
xm + 1 |
... |
xn |
1 |
x1 |

|

|
1 |
0 |
... |
0 |

|
... |

|
2 |
x2 |

|

|
0 |
1 |
... |
0 |

|
... |

|
|
|
|
|
|
|
|
|
|
|
|
m |
xm |

|

|
0 |
0 |
... |
1 |

|
... |

|
m + 1 |

|
F0 |
0 |
0 |
... |
0 |

|
... |

|
Позначимо через D матрицю, що утворена з компонент векторів А1, А2,…, Аm останнього базису в першій симплексній таблиці.
Для оптимального плану отримаємо:
(3.12)
де , В — вектор, що складається з вільних членів системи обмежень.
Звідси:
(3.13)
Симплексна таблиця 3.1 містить коефіцієнти розкладу векторів початкової системи обмежень задачі за векторами базису, тобто кожному вектору з системи обмежень задачі (3.1)—(3.3) Аj відповідає в симплексній таблиці вектор , такий що
(3.14)
Позначимо через матрицю, що складається з коефіцієнтів розкладу векторів . Тоді буде справджуватися рівність:
,
звідки
. (3.15)
Враховуючи (3.13), значення оптимального плану даної задачі знаходиться у вигляді:

де , причому

,
тобто всі компоненти вектора є оцінками оптимального плану задачі (3.1)—(3.3), а тому
 . (3.16)
Оскільки оптимальний план початкової задачі подано у вигляді , то за правилами побудови двоїстої задачі можна допустити, що її оптимальний план матиме вигляд:
. (3.17)
Доведемо, що дійсно є оптимальним планом двоїстої задачі.
Система обмежень двоїстої задачі у векторно-матричній формі матиме вигляд:
.
Підставимо в цю нерівність значення . Тоді, враховуючи (3.15), (3.16) та (3.17), отримаємо:
.
Звідки: . Отже, задовольняє систему обмежень (3.5) двоїстої задачі, тому є допустимим планом задачі (3.4)—(3.6).
Для даного плану значення функціонала дорівнюватиме:
, (3.18)
де . Підставимо в (3.18) значення з (3.17) та, враховуючи (3.13), матимемо:
. (3.19)
Доведено, що збігається зі значенням оптимального плану початкової задачі.
Отже, за лемою 3.2 (достатня умова оптимальності плану задачі лінійного програмування) план є оптимальним планом двоїстої задачі (3.4)—(3.6).
Аналогічно доводиться, що коли двоїста задача має розв’язок, то початкова також має розв’язок і виконується рівність:
.
Для доведення другої частини теореми допустимо, що лінійна функція початкової задачі необмежена зверху. Тоді з нерівності маємо, що , що не має змісту. Отже, двоїста задача в даному разі не має розв’язків.
Доведена теорема дає змогу в процесі розв’язування однієї задачі водночас знаходити план другої.
Економічний зміст першої теореми двоїстості. Максимальний прибуток (Fmax) підприємство отримує за умови виробництва продукції згідно з оптимальним планом , однак таку саму суму грошей ( ) воно може мати, реалізувавши ресурси за оптимальними цінами . За умов використання інших планів на підставі основної нерівності теорії двоїстості можна стверджувати, що прибутки від реалізації продукції завжди менші, ніж витрати на її виробництво.
|