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

Між прямою та двоїстою задачами лінійного програмування іс­нує тісний взаємозв'язок, який випливає з наведених далі теорем.

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

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

Якщо пряма задача лінійного програмування має оптимальний план X*, визначений симплекс-методом, то оптимальний план двоїстої задачі Y^* визначається зі співвідношення

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

За допомогою зазначеного співвідношення під час визначення оптимального плану однієї з пари двоїстих задач лінійного програмування знаходять розв'язок іншої задачі.

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

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

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

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

30. Постановка транспортної задачі. Транспортна задача. Постановка, методи розв’язування та аналізу.

5.1. Економічна і математична постановка тз. Умови існування розв’язку тз.

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

Математична модель транспортної задачі має такий вигляд:

(5.1)

за обмежень

	(5.2)
	(5.3)
	(5.4)

де — кількість продукції, що перевозиться від і-го постачальника до j-го споживача; — вартість перевезення одиниці продукції від i-го постачальника до j-го споживача; — запаси продукції i-го постачальника; — попит на продукцію j-го споживача.

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

(5.5)

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

Планом транспортної задачі називають будь-який невід'ємний розв'язок системи обмежень (5.2)—(5.4) транспортної задачі, який позначають матрицею .

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

! Теорема (умова існування розв'язку транспортної задачі). Необхідною і достатньою умовою існування розв'язку транспортної задачі є її збалансованість, тобто .