Основні теореми двоїстості та їх економічний зміст

Зв’язок між оптимальними розв’язками прямої та двоїстої задач встановлюють леми та теореми двоїстості. Розглянемо задачі (1.1)—(1.3) та (1.4)—(1.6) з економічною інтерпретацією, наведеною в § 1.1.

Теорема Канторовича. Якщо для допустимих планів.

Та пари двоїстих задач виконується умова.

(1.12).

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

Доведення. Згідно з основною нерівністю теорії двоїстості.

Однак.

(умова (1.12)).

Тому.

.

Це означає, що.

— оптимальний план прямої задачі.

Аналогічно справедливо.

Оскільки.

.

То.

— оптимальний план двоїстої задачі. Теорема Канторовича доведена.

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

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

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

Доведення. Допустимо, що початкова задача (1.1) — (1.3) має оптимальний план, який отриманий симплексним методом. Не порушуючи загальності, можна вважати, що останній базис складається з перших m векторів. Остання симплексна таблиця має вигляд.

Таблиця 1.1 Остання симплексна таблиця.

і	Базис.	Сб	План.	с1	с2		сm	cm + 1		cn
	x1	x2		xm	xm + 1		xn
	x1
	x2
m	xm
m + 1.		F0

Позначимо через D матрицю, що утворена з компонент векторів А₁, А₂,…, А_m останнього базису в першій симплексній таблиці.

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

(1.13).

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

.

Звідси:

(1.14).

Симплексна таблиця 1.1 містить коефіцієнти розкладу векторів початкової системи обмежень задачі за векторами базису, тобто кожному вектору з системи обмежень задачі (1.1)—(1.3) А_j відповідає в симплексній таблиці вектор, такий що.

(1.15).

Позначимо через матрицю, що складається з коефіцієнтів розкладу векторів,. Тоді буде справджуватися рівність:

.

звідки.

.(1.16).

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

Де.

.

причому.

.

тобто всі компоненти вектора є оцінками оптимального плану задачі (1.1) -(1.3), а тому.

. (1.17).

Оскільки оптимальний план початкової задачі подано у вигляді.

.

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

. (1.18).

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

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

.

Підставимо в цю нерівність значення. Тоді, враховуючи (1.16), (1.17) та (1.1), отримаємо:

.

Звідки:

.

Отже, задовольняє систему обмежень (1.5) двоїстої задачі, тому є допустимим планом задачі (1.4)—(1.6).

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

(1.19).

Де.

.

Підставимо в (1.19) значення з (1.18) та, враховуючи (1.14), матимемо:

.(1.20).

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

Отже, за теоремою Канторовича (достатня умова оптимальності плану задачі лінійного програмування) план є оптимальним планом двоїстої задачі (1.4)—(1.6).

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

.

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

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

Економічний зміст першої теореми двоїстості. Максимальний прибуток (F_max) підприємство отримує за умови виробництва продукції згідно з оптимальним планом.

.

однак таку саму суму грошей () воно може мати, реалізувавши ресурси за оптимальними цінами.

.

За умов використання інших планів.

на підставі основної нерівності теорії двоїстості можна стверджувати, що прибутки від реалізації продукції завжди менші, ніж витрати на її виробництво.