Перераспределение поставок

(по правилу контура)

Если план не является оптимальным, необходимо сделать перераспределение поставок в потенциальные клетки (где U _ij <0) по правилу контура.

Примечание: если имеется несколько потенциальных связей, где U _ij <0, в первую очередь следует перераспределить поставку в клетку с наименьшимотрицательным значением U _ij как в наиболее потенциальную.

Перераспределение поставок в потенциальные клетки осуществляется по т.н. правилу "контура";, которое позволяет сохранять баланс по строкам и столбцам: когда из одной клетки строки какая-либо часть груза вычитается, то в другую клетку строки это значение прибавляется, аналогичное соблюдается и по столбцам.

Что является контуром и как его отыскать в плане? Контур представляет собой замкнутую фигуру, образованную прямыми отрезками, углы между которыми всегда равны 90⁰.

 

Отличительные особенности контура:

1) он состоит из четного количества вершин, которыми являются:

- загруженные поставками связи (нечетное количество);

- связь с отрицательным оценочным параметром (U_ij < 0);

2) возможные варианты контуров:

- четырехугольные: B C

B C

 

A D A D

- шестиугольные:

B C C D

 

 

E D B E

A F A F

- восьмиугольные и т.д.

Итак, используя примеры возможных контуров, определим контур в данной задаче, учитывая что одной из его вершин является связь с отрицательным оценочным параметром, а остальные вершины - загруженные поставками связи. В данном базисном плане 2 связи с отрицательным оценочным параметром - A ₂ B ₄ и A ₂ B ₄. В первую очередь должна рассматриваться связь с наименьшим оценочным параметром как наиболее потенциальная. Но в данном плане две потенциальные связи (A ₃ B ₁ и A ₂ B ₄), у которых оценочные параметры одинаковы. Они образуют два контура. Один из контуров - это четырехугольник, вершинами которого являются загруженные поставками связи A ₁ B ₁, A ₁ B ₄, A ₃ B ₄ и связь с отрицательным оценочным параметром A ₃ B ₁. Второй контур - это шестиугольник, вершинами которого являются загруженные поставками связи A ₁ B ₁, A ₁ B ₄, A ₂ B ₃, A ₄ B ₃, A ₂ B ₁ и связь с отрицательным оценочным параметром A ₂ B ₄. Для перераспределения поставок выбираем любой контур, например, второй.

Ai\Bj	B1		В2		В3		В4		Qi	Ui
А1
							-1
А2
	-1
А3
А4 доп
Qj
Uj

Вынесем контур отдельно для того, чтобы произвести перераспределение поставок:

А1В1 0 15 А1В4   25 А2В3 А2В4 (U ij <0)   А4В1 10 5 А4В3

Далее осуществляется перераспределение поставок по контуру: вершина с отрицательным значением оценочного параметра U _ij считается нечетной (в контуре она условно обозначается нулем - А ₂ В ₄), рядом с ней ставится знак (+), следующая за ней вершина (по часовой стрелке или против нее) принимается четной, возле нее ставится знак (-), за четной вершиной следует нечетная и т.д.:

неч.+ 0 15 чет. -   25 чет - (0) неч.+ (U ij <0)   чет.- 10 5 неч.+

Затем необходимо среди четных вершин выбрать вершину с минимальным значением объема поставки. Это значение следует вычесть из четных вершин (-) и прибавить к нечетным (+). В данном контуре:

Чет.min=10 (А₄В₁).

Это значение вычитаем из всех четных связей и прибавляем ко всем нечетным. В результате получится:

неч.+ 0+10= 10 15-10= 5 чет. -   25 -10= 15 0+10= 10 неч.+ (U i j<0) чет - чет.- 10-10= 0 5+10= 15 неч.+

Далее проверяем количество поставок: до перераспределения их было в контуре 5, значит, и после перераспределения должно остаться 5 (поэтому поставку, равную нулю (А₄В₁), из плана исключаем. Если бы оказалось несколько поставок, равных нулю, то следовало бы оставить такое их количество, при котором суммарное число поставок должно было равняться 5 и можно было бы на следующем этапе вычислить потенциалы U _i и U _j. При этом предпочтение должно отдаваться связям с наименьшими расстояниями.

Таким образом было осуществлено перераспределение поставок по контуру. С учетом этого перераспределения составим новый план закрепления постребителей за поставщиками:

Ai\Bj	B1		В2		В3		В4		Qi	Ui
А1
А2
А3
А4 доп
Qj
Uj

Далее новый план закрепления потребителей за поставщиками по аналогии проверяем на оптимальность по условию:

U _ij >=0

где U _ij - оценочный параметр или критерий оптимальности базисного плана.

Точно так же, как описывалось выше, рассчитываем потенциалы поставщиков и потребителей для загруженных связей и оценочные параметры для незагруженных связей:

Ai\Bj	B1		В2		В3		В4		Qi	Ui
А1
А2
	-1				-1
А3
А4 доп
Qj
Uj

Поскольку имеются связи, где U _ij <0, новый план закрепления потребителей за поставщиками снова признается неоптимальным:

U _ij <0: U ₃₁ = -1, U ₃₃ = -1.

Это говорит о том, что cледует еще раз произвести перераспределение поставок по контуру. Этот процесс будет осуществляться до тех пор, пока все оценочные параметры не станут положительными либо равными нулю: U _ij >=0.

Поскольку имеются две одинаково потенциальные связи с одинаковым оценочным параметром (U _ij = -1), то можно построить контур, начать рассматривать любую из них. Например, построим контур, отталкиваясь от связи А ₃ В ₁. Она образует четырехугольный контур, вершинами которого являются загруженные поставками связи - А ₁ В ₁, А ₁ В ₄, А ₃ В ₄ и связь с отрицательным оценочным параметром А ₃ В ₁ (см. таблицу выше):

чет. - 10 5 неч. +

 

неч. + 0 10 чет. -

(U _ij <0)

Чет.min=10.

Это значение необходимо вычесть из всех четных клеток и прибавить ко всем нечетным:

чет. - 10-10=0 5+10=15 неч. +

 

неч. + 0+10=10 10-10=0 чет. -

 

 

••••••••••••••••••••••

Далее проверяем количество поставок: до перераспределения их было в контуре 3, значит, и после перераспределения должно остаться 3 (поэтому поставку, равную нулю (А₄В₁), из плана исключаем. Если бы оказалось несколько поставок, равных нулю, то следовало бы оставить такое их количество, при котором суммарное число поставок должно было равняться 5 и можно было бы на следующем этапе вычислить потенциалы U _i и U _j. При этом предпочтение должно отдаваться связям с наименьшими расстояниями.

 

В соответствии с перераспределением поставок по контуру составляем новый план закрепления потребителей за поставщиками:

 

Ai\Bj	B1		В2		В3		В4		Qi	Ui
А1
А2
					-1
А3
А4 доп
Qj
Uj

 

Рассчитываем необходимое количество поставок по формуле:

N=m+n-1=4+4-1=7

В данной задаче количество поставок по количеству загруженных клеток:

N=8.

По этой причине одну из условных поставок, равных по объему нулю, следует исключить из плана, например, Q ₁₁.

Далее новый план закрепления потребителей за поставщиками по аналогии проверяем на оптимальность по условию:

U _ij >=0

Точно так же, как описывалось выше, рассчитываем потенциалы поставщиков и потребителей для загруженных связей и оценочные параметры для незагруженных связей:

Ai\Bj	B1		В2		В3		В4		Qi	Ui
А1
А2
А3
А4доп
Qj
Uj

Полученный план закрепления потребителей за поставщиками оптимален, поскольку все оценочные параметры U _ij >=0.

6) В заключении после того, как план закрепления потребителей за поставщиками признан оптимальным, следует рассчитать оптимальные, т.е. минимальные затраты на перевозку грузов от потребителей до поставщиков по формуле:

Z = (C _ij •Q _ij),

где C _ij - расстояние от i-го поставщика до j-го потребителя;

Q _ij - объем поставки от i-го поставщика к j-му потребителю.

Иными словами, чтобы рассчитать минимальные затраты на перевозку, объем поставки по каждой загруженной клетке - Q _ij необходимо умножить на соответствующее расстояние C _ij, и просуммировать все полученные произведения для всех загруженных связей (см.последнюю таблицу):

 

Z=15•6 + 15•10 +10•8 + 10•7 +20•6 + 0•8 = 510 у.е.

 

Вывод: оптимальные затраты на перевозку грузов от потребителей к поставщикам - 510 у.е.