4. Проверка опорного плана на оптимальность.

Вновь находим потенциалы и проверяем условие (2).

Условие оптимальности выполнено.

Получен оптимальный план перевозок!

F_min = 20*4 + 80*2 + 100*4 + 50*6 + 50*4 + 150*2 + 50*5 = 1690

х₁₂ = 20

х₁₃ = 80

х₁₅ = 100

х₂₁ = 50

х₂₂ = 50

х₂₄ = 150

х₃₁= 50

Графическая иллюстрация.

Рис. 5. 2

Пример:

Шведская компания “ Стенлюкс“ имеет три основные центра сбыта - в Берлине, Лионе и Бирмингеме (потребители). Холодильники производятся на трех производствах в Стокгольме, Триесте и Руане (поставщики). Исходные данные приведены в таблице:

Табл. 1

Потребитель Поставщик	1 (Берлин)	2 (Лион)	3 (Бирмин.)	Запасы
1 (Стокгольм)	30	14	16	120
2 (Триест)	18	8	22	40
3 (Руан)	12	6	14	90
Спрос	100	80	70

В клетках таблицы указаны тарифы по перевозке одного холодильника потребителям (в ф. ст.).

Менеджменту компании требуется принять решение по маршрутам перевозок с целью минимизации затрат.

Следуем вышеприведенному алгоритму.

Транспортная задача закрытая.

1. Нахождение начального опорного плана (угловой точки).

Используем метод минимальной стоимости. Его суть:

а) находим клетку с минимальной стоимостью и в максимально возможной степени удовлетворяем спрос соответствующего потребителя. Результат записываем в левый нижний угол клетки. (табл. 2)

Табл. 2

Потребитель Поставщик	1 (Берлин)	2 (Лион)	3 (Бирмин.)	Запасы
1 (Стокгольм)	30 50	14	16 70	0
2 (Триест)	18 40	8	22	0
3 (Руан)	12 10	6 80	14	0
Спрос	0	0	0

б) правило: “там, где 0 вычеркиваем”

в) среди всех невычеркнутых клеток вновь находим клетку с минимальной стоимостью и вновь повторяем алгоритм.

г) контроль: общее число занятых клеток должно быть равно m + n – 1. У нас 3+ 3- 1= 5.

Начальный опорный план - в левом нижнем углу клеток.

2. Проверка опорного плана на оптимальность.

Проверка на оптимальность осуществляется с помощью потенциалов во вновь составленной таблице (табл. 3)

Табл. 3

Потребитель Поставщик	1 (Берлин)	2 (Лион)	3 (Бирмин.)	U
1 (Стокгольм)	30 50	14	16 70	0
2 (Триест)	18 40	8	22	-12
3 (Руан)	12 10	6 80	14	-18
V	30	24	16

ПРАВИЛО 1: для всех занятых клеток должно быть:

u _i + v _j = c _{i j} (1)

(сумма потенциалов равна стоимости). Это правило- для заполнения столбцов U, V.

ПРАВИЛО 2: для всех свободных клеток должно быть:

u _i + v _j ≤ c _{i j} (2)

Это правило проверки оптимальности. Условие оптимальности нарушено в наибольшей степени клетке (1, 2)!

Итак, полученный опорный план не оптимален!