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

Поточна версія на 11:31, 4 травня 2012

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

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

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

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

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

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

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

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

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

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

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

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

Звідси:

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

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

, такий що

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

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

звідки

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

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

причому 

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

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

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

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

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

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

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

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

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

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

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

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

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

, матимемо:

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

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

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

Для доведення другої частини теореми допустимо, що лінійна функція початкової задачі необмежена зверху. Тоді з нерівності Неможливо розібрати вираз (невідома помилка): 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)