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

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

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

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

Цикл- это замкнутая ломаная линия, состоящая из горизонтальных и вертикальных отрезков, соединяющих некоторые занятые клетки и поворачивающих в каждой из них на 90 градусов.

Находим клетку, в которой условие оптимальности нарушено в наибольшей степени. В нашем случае это клетка (1, 2). Далее

С другой стороны, перевозчик, установив оптимальный план, хочет получить максимум, т.е. весь тариф полностью (формула (1)).

Формула (2) означает, что при оптимальном плане перевозок стороны не хотят переплачивать сверх установленного тарифа.

3. Переход к новому опорному плану, лучшему, чем предыдущему.

а) помечаем эту клетку знаком + и строим цикл, начинающийся и заканчивающийся в этой же клетке.

Такой цикл всегда существует и только один!

б) размечаем вершины цикла знаками - + - … считая от исходной клетки.

в) находим, по всем клеткам, помеченным знаком - наименьшую перевозку. Обозначим ее α. У нас α = 20.

г) двигаясь по циклу, прибавляем α к клеткам со знаком + и вычитаем ее из клеток со знаком -.

Получающийся “лишний нуль” стираем.

Результаты записываем в новую таблицу. (табл. 4)

Табл. 4

Потребитель						U
Поставщик
						-1
V

Не забываем проверять условие: число занятых клеток = m+n -1.

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

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

Потребитель Поставщик	(Берлин)	(Лион)	(Бирмин.)	Запасы
(Стокгольм)
(Триест)
(Руан)
Спрос

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

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

Дата добавления: 2015-06-04