Контрольні питання:

1. Що таке припустимий план перевезень?

2. Яким чином заповнюють клітини рядку та стовпця різниць методу Фогеля?

3. Що таке "сідлова" клітина?

4. Як визначається додаткова різниця у методі Фогеля?

Література [1,7]

Практична робота 10. Зняття виродженності транспортної задачі

Мета: навчитись використовувати Епсілон-прийом та нуль-підстановку.

Задача

Дані пр. роботи №8 (скореговані викладачем).

Завдання

1. Знайти припустимий план закріплення споживачів за постачальниками двома способами.

2. Знайти транспортну роботу за результатами кожного з методів.

Методичні вказівки

На жаль, при рішенні транспортних задач, особливо тоді, коли і  цілі числа, часто приходиться зіштовхуватися з виродженними опорними планами, тобто з планами, число позитивних компонентів яких менше . Це буває тоді, коли, яка-небудь підмножина складів задовольняє потреби якої-небудь підмножини пунктів споживання.

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

Епсілон-прийом.

Він полягає в наступному: нехай запаси продукту є ,

а

потреби пунктів споживання є

.

Розглянемо нову задачу з тими ж самими , для якої

с деяким ε>0. Можна взяти ε конкретним, але досить малим числом, а можна просто залишити в алгебраїчному виді як букву. Потім транспортна задача зважується звичайним шляхом, а у відповіді просто покладається ε=0, (чи отриманий результат округляється, якщо ε було взято конкретним малим числом).

0-підстановка.

Розглянемо задачу

4	5	7	8	5
9	3	6	2	8
7	8	4	5	7
5	5	5	5

План, складений методом північно-західного кута має вид:

5
	5	3
		2	5

План є виродженним.

Розглянемо таблицю, у якій зазначені ціни на перевезення, за винятком базисних компонентів.

	5	7	8	5
9			2	8
7	8			7
5	5	5	5

Видалимо з розгляду клітки, при постановці в який деяких одиниць виникає цикл.

	5	7	8	5
9				8
7				7
5	5	5	5

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

Виберемо мінімальну вартість і поставимо нульове перевезення .

Тепер план придбає вид.

5	0
	5	3
		2	5