Перша теорема двоїстості. Економічне тлумачення

Перша теорема двоїстості

Теорема(перша теорема двоїстості)

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

Неможливо розібрати вираз (невідома помилка): \max\ F=\min\Z.

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

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

Доведення. Нехай початкова задача має оптимальний план, який отриманий симплексним методом. Не порушуючи загальності, можна вважати, що останній базис складається з перших m векторів Неможливо розібрати вираз (невідома помилка): A_{1} ,A_{2} ,\dots,A_{m}

. Остання симплексна таблиця має вигляд:

Таблиця 1

Позначимо через Неможливо розібрати вираз (невідома помилка): D~

матрицю, що утворена з компонент векторів Неможливо розібрати вираз (невідома помилка):  A_{1} ,A_{2} ,\dots ,A_{m}
останнього базису в першій симплексній таблиці.

Для оптимального плану отримаємо:

Неможливо розібрати вираз (невідома помилка): ~ B=DX^{*}~~~~~~~~(1)

де Неможливо розібрати вираз (невідома помилка): X^{*} =(x_{1}^{*} ,x_{2}^{*} ,...,x_{m}^{*} ) , Неможливо розібрати вираз (невідома помилка): \Beta ~

--- вектор, що складається з вільних членів системи обмежень.

Звідси:

Неможливо розібрати вираз (невідома помилка): ~ B=DX^{*} \Rightarrow X^{*} =D^{-1} B.~~~~~~~~(2)

Симплексна таблиця 1 містить коефіцієнти розкладу векторів Неможливо розібрати вираз (невідома помилка): ~A_{1} ,A_{2} ,...,A_{n}

початкової системи обмежень задачі за векторами базису, тобто кожному вектору з системи обмежень задачі Неможливо розібрати вираз (невідома помилка): ~A_{j}
відповідає в симплексній таблиці вектор Неможливо розібрати вираз (невідома помилка): ~A'_{j}

, такий що

Неможливо розібрати вираз (невідома помилка): A_{j} =DA'_{j} ,\, \, \, (j=\overline{1,n}).~~~~~~~~(3)

Позначимо через Неможливо розібрати вираз (невідома помилка): A'~

матрицю, що складається з коефіцієнтів розкладу векторів Неможливо розібрати вираз (невідома помилка): A_{j}~  \left(j=\overline{1,n}\right)
. Тоді буде справджуватися рівність:

Неможливо розібрати вираз (невідома помилка): A_{} =DA'_{},~

звідки

Неможливо розібрати вираз (невідома помилка): A'_{} =D^{-1} A~~~~~~~~(4)

Враховуючи Неможливо розібрати вираз (невідома помилка): ~(2) , значення оптимального плану даної задачі знаходиться у вигляді:

Неможливо розібрати вираз (невідома помилка): \max \, F=C^{*} X^{*} ,

де Неможливо розібрати вираз (невідома помилка): C^{*} =(c_{1}^{*} ,c_{2}^{*} ,...,c_{m}^{*} ),

причому 

Неможливо розібрати вираз (невідома помилка): \bar{F}=C^{*} A'-C=(c_{1}^{*} A'_{1} -c_{1} ;c_{2}^{*} A'_{2} -c_{2} ;...;c_{n}^{*} A'_{n} -c_{n} )= (F_{1} -c_{1} ;F_{2} -c_{2} ;...;F_{n} -c_{n} ),

тобто всі компоненти вектора Неможливо розібрати вираз (невідома помилка): \bar{F}

є оцінками оптимального плану задачі, а тому 

Неможливо розібрати вираз (невідома помилка): C^{*} A'-C=\left(F_{j} -c_{j} \right)\ge 0,\, \, \; \left(j=\overline{1,n}\right).~~~~~~~~(5)

Оскільки оптимальний план початкової задачі подано у вигляді Неможливо розібрати вираз (невідома помилка): X^{*} =D^{-1} B~ , то за правилами побудови двоїстої задачі можна допустити, що її оптимальний план матиме вигляд:

Неможливо розібрати вираз (невідома помилка): Y^{*} =C^{*} D^{-1}.~~~~~~~~(6)

Доведемо, що Неможливо розібрати вираз (невідома помилка): Y^{*} =C^{*} D^{-1}~

 дійсно є оптимальним планом двоїстої задачі.

Система обмежень двоїстої задачі у векторно-матричній формі матиме вигляд:

Неможливо розібрати вираз (невідома помилка): YA\ge C=YA-C\ge 0~.

Підставимо в цю нерівність значення Неможливо розібрати вираз (невідома помилка): Y^{*}.~

Тоді, враховуючи Неможливо розібрати вираз (невідома помилка): (4),(5)~
та Неможливо розібрати вираз (невідома помилка): (6)~
отримаємо:

Неможливо розібрати вираз (невідома помилка): Y^{*} A-C=C^{*} D^{-1} A-C=C^{*} A'-C\ge 0.

Звідки: Неможливо розібрати вираз (невідома помилка): Y^{*} A\ge C . Отже, Неможливо розібрати вираз (невідома помилка): Y^{*}~

задовольняє систему обмежень Неможливо розібрати вираз (невідома помилка): (4)~
двоїстої задачі, тому є допустимим планом задачі Неможливо розібрати вираз (невідома помилка): (3)-(5)~

. Для даного плану значення функціонала дорівнюватиме:

Неможливо розібрати вираз (невідома помилка): Z(Y^{*} )=Y^{*} B,~~~~~~~~(7)

де Неможливо розібрати вираз (невідома помилка): B=(b_{1} ,b_{2} ,...,b_{m}~ ).

Підставимо в Неможливо розібрати вираз (невідома помилка): (7)~
значення Неможливо розібрати вираз (невідома помилка): Y^{*}~
 з Неможливо розібрати вираз (невідома помилка): (6)~
та, враховуючи Неможливо розібрати вираз (невідома помилка): (2)~

, матимемо:

Неможливо розібрати вираз (невідома помилка): Z(Y^{*} )=Y^{*} B=C^{*} D^{-1} B=C^{*} X^{*} =\max \, F.~~~~~~~~(8)

Доведено, що Неможливо розібрати вираз (невідома помилка): Z(Y^{*}~ )

збігається зі значенням оптимального плану початкової задачі. Отже, за лемою (достатня умова оптимальності плану задачі лінійного програмування) план Неможливо розібрати вираз (невідома помилка): Y^{*}~
 є оптимальним планом двоїстої задачі.

Аналогічно доводиться, що коли двоїста задача має розв'язок, то початкова також має розв'язок і виконується рівність:

Неможливо розібрати вираз (невідома помилка): \min \, Z=\max \, F.

Для доведення другої частини теореми допустимо, що лінійна функція початкової задачі необмежена зверху. Тоді з нерівності Неможливо розібрати вираз (невідома помилка): F(X)\le Z(Y)

маємо, що Неможливо розібрати вираз (невідома помилка): Z(Y)\ge +\infty

, що не має змісту. Отже, двоїста задача в даному разі не має розв'язків.

Доведена теорема дає змогу в процесі розв'язування однієї задачі водночас знаходити план другої.

Економічний зміст першої теореми двоїстості.

Максимальний прибуток Неможливо розібрати вираз (невідома помилка): (F_{\max })~

підприємство отримує за умови виробництва продукції згідно з оптимальним планом Неможливо розібрати вираз (невідома помилка): X^{*} =(x_{1}^{*} ,x_{2}^{*} ,...,x_{n}^{*} ),
однак таку саму суму грошей Неможливо розібрати вираз (невідома помилка): (Z_{\min } =F_{\max })~
воно може мати, реалізувавши ресурси за оптимальними цінами Неможливо розібрати вираз (невідома помилка): Y^{*} =(y_{1}^{*} ,y_{2}^{*} ,...,y_{m}^{*} ).
За умов використання інших планів Неможливо розібрати вираз (невідома помилка): X\ne X_{opt} ,\,  Y\ne Y_{opt}
 на підставі основної нерівності теорії двоїстості можна стверджувати, що прибутки від реалізації продукції завжди менші, ніж витрати на її виробництво.

Література

1.Математичне програмування - Наконечний С.І.
2.Введення в теорію двоїстості (.doc)