Перелік питань для самоперевірки

1. Теорія двоїстості для випадку симетричної пари взаємодвоїстих задач: означення прямої задачі та двоїстої до неї у симетричному випадку, взаємозв’язок між ними; співвідношення між допустимими значеннями цільових функцій прямої та двоїстої задач.

2. Перша та друга теореми двоїстості. Знаходження розв’язку однієї з пар симетричних взаємно двоїстих задач за відомим розв’язком іншої задачі.

3. Економічна інтерпретація теорем двоїстості (оптимальні значення двоїстих змінних як оптимальні оцінки ресурсів у задачах оптимізації плану виробництва).

Лекція 5

Тема 5. Методика розв’язування транспортної задачі

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

Схема розв’язання транспортної задачі:

1. Подати задачу в замкненій формі (всі обмеження математичної моделі, крім умов невід’ємності, мають бути у виді рівностей).

2. Знайти вихідний опорний план – початковий базисний розподіл постачань. Розподіл постачань називається базисним, якщо число заповнених клітин таблиці постачань дорівнює числу базисних змінних транспортної задачі, тобто дорівнює , деm – число постачальників, n – число споживачів.

3. З’ясувати, чи є вихідний опорний план оптимальним.

4. Якщо опорний план не є оптимальним, треба побудувати новий, “ближчий” до оптимального (з меншими витратами на перевезення).

5.1. Приведення задачі до замкненої форми

Якщо в транспортній задачі попит дорівнює пропозиції , то задача вже подана в замкненій формі.

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

Задача 5.1. Привести транспортну задачу 1.3 (с. 10) до замкненої форми.

Рішення

В цій задачі попит більший за пропозицію . Для того, щоб привести цю задачу до замкненої форми, введемо фіктивного постачальника і в таблицю постачань додамо ще один рядок. Запас товару у фіктивного постачальника дорівнює, а вартість перевезення одиниці товару від нього до кожного зі споживачів – нулю. В результаті одержимо табл. 5.1 (для зручності подальшого розгляду розв’язання задачі вартість перевезення запишемо в лівому верхньому куті клітини).

														Таблиця 5.1
	bj ai		45			35			55			65
40		4			1			2			5
60		3			2			3			7
90		4			4			5			2
10		0			0			0			0