Оптимизация первоначального плана распределения

Потребители					Всего предложение
Поставщики	Vj
Ui
А
110
В	-3
С	-2				• 2
Всего спрос

Примечание. При построении связки можно пропускать свободные и занятые квадраты.

После образования связки свободному квадрату и связанным с ним занятым квадратам присваиваются поочередно знаки «плюс» и «минус», начиная со свободного квадрата.

Из квадратов со знаком «минус» перемещается соответствующее количество перевозок в квадраты со знаком «плюс». Чтобы не получить отрицательных перевозок, перемещается наименьшее количество груза, которое находится в квадратах связки со знаком «минус» (рис. 5.2).

Рис. 1.1. Оптимизация первоначального плана.

В данном примере связка образуется из свободного квадрата С-4, в который необходимо переместить перевозку из занятых квадратов С-1, А-1, А-4. Присваиваем квадрату С-4 знак «плюс», квадрату С-1 - знак «минус», квадрату А-4 - «плюс» и квадрату А-4 - «минус».

Наименьшая перевозка со знаком «минус» находится в квадрате С-4, она равна 20 ед. Это количество и перемещается. В результате в квадрате А-1 перевозка будет равна 130 ед., в квадрате А-4 - 40 ед., в квадрате С-4 - 20 ед., а квадрат С-1 станет свободным (рис. 1.2).

Примечание. Если план не является оптимальным одновременно для нескольких квадратов, в первую очередь производят перемещения перевозок в тот квадрат, в котором условие оптимальности нарушено больше, чем во всех остальных, т.е. в котором разность V_j-(C_ij+ U_i) максимальная.

Законченный цикл вычислений, приводящий к получению нового варианта прикрепления потребителей к поставщикам, называется итерацией.

Рис. 1.2. Размещение перевозок после оптимизации.

Для нового плана вычисляются новые значения потенциалов, и проверяется новый вариант на оптимальность, т.е. повторяютсяшаги 2 и 3.

Все расчеты новых перевозок приведены в табл. 1.5

Таблица 1.5

Дата добавления: 2014-11-29