Формирование оптимальных грузопотоков

 

Мы израсходовали  все запасы поставщиков и удовлетворили  все потребности потребителей

 Мы нашли начальное  решение

Стоимость доставки продукции   S = 400 * 4 + 100 * 4 + 100 * 4 + 300 * 4 + 250 * 3 + 150 * 3 + 150 * 6 + 150 * 7 =   6750 ден. ед.

Полученное начальное  решение является оптимальным?

Для того, чтобы иметь возможность ответить на этот вопрос, количество задействованных маршрутов должно равняться 5 + 4 - 1 = 8, где 5 - количество строк в таблице, 4 - количество столбцов в таблице.

Количество задействованных  маршрутов не может получиться больше 8, меньше - возможно.

 

Шаг 1

Каждому поставщику A _i ставим в соответствие некоторое число - u _i , называемое потенциалом поставщика.

Каждому потребителю B _j ставим в соответствие некоторое число - v _j , называемое потенциалом потребителя.

·  Найдем потенциалы поставщиков и покупателей

Для задействованного маршрута, сумма потенциала поставщика и потребителя равна тарифу задействованного маршрута.

Примем v₄ = 0

A2B4 :	v4 + u2 = 4	u2 = 4 - 0 = 4
A4B4 :	v4 + u4 = 3	u4 = 3 - 0 = 3
A5B4 :	v4 + u5 = 7	u5 = 7 - 0 = 7
A2B3 :	v3 + u2 = 4	v3 = 4 - 4 = 0
A3B3 :	v3 + u3 = 3	u3 = 3 - 0 = 3
A5B2 :	v2 + u5 = 6	v2 = 6 - 7 = -1
A1B2 :	v2 + u1 = 4	u1 = 4 - ( -1 ) = 5
A1B1 :	v1 + u1 = 4	v1 = 4 - 5 = -1

 

Поставщик	Потребитель				U j
	B 1	B 2	B 3	B 4
A 1	400   4	100   4	5	9	u 1 = 5
A 2	8	5	100   4	300   4	u 2 = 4
A 3	5	6	250   3	9	u 3 = 3
A 4	9	7	5	150   3	u 4 = 3
A 5	7	150   6	6	150   7	u 5 = 7
V i	v 1 = -1	v 2 = -1	v 3 = 0	v 4 = 0

 

·  Найдем оценки незадействованных маршрутов (в таблице они располагаются в нижнем левом углу ячейки).

Оценка незадействованного маршрута = тариф маршрута - ( потенциал поставщика + потенциал потребителя ).

A1B3 :          13 = 5 - ( 5 + 0 ) = 0

A1B4 :          14 = 9 - ( 5 + 0 ) = 4

A2B1 :          21 = 8 - ( 4 + ( -1 ) ) = 5

A2B2 :          22 = 5 - ( 4 + ( -1 ) ) = 2

A3B1 :          31 = 5 - ( 3 + ( -1 ) ) = 3

A3B2 :          32 = 6 - ( 3 + ( -1 ) ) = 4

A3B4 :          34 = 9 - ( 3 + 0 ) = 6

A4B1 :          41 = 9 - ( 3 + ( -1 ) ) = 7

A4B2 :          42 = 7 - ( 3 + ( -1 ) ) = 5

A4B3 :          43 = 5 - ( 3 + 0 ) = 2

A5B1 :          51 = 7 - ( 7 + ( -1 ) ) = 1

A5B3 :          53 = 6 - ( 7 + 0 ) = -1

 

Поставщик	Потребитель				U j
	B 1	B 2	B 3	B 4
A 1	400   4	100   4	0 5	4 9	u 1 = 5
A 2	5 8	2 5	100   4	300   4	u 2 = 4
A 3	3 5	4 6	250   3	6 9	u 3 = 3
A 4	7 9	5 7	2 5	150   3	u 4 = 3
A 5	1 7	150   6	-1 6	150   7	u 5 = 7
V i	v 1 = -1	v 2 = -1	v 3 = 0	v 4 = 0

 

1 незадействованный  маршрут имеют отрицательную  оценку.

Будем использовать новый маршрут доставки продукции  от поставщика A₅ к потребителю B₃. (ячейка A₅B₃)

Поставщик	Потребитель				Запас
	B 1	B 2	B 3	B 4
A 1	400   4	100   4	5	9	500
A 2	8	5	100   4	300   4	400
A 3	5	6	250   3	9	250
A 4	9	7	5	150   3	150
A 5	7	150   6	-1 6	150   7	300
Потребность	400	250	350	600

 

Пусть ячейка A₅B₃, для которой мы строили цикл, имеет порядковый номер один.

Среди ячеек цикла, номера которых четные, найдем ячейку обладающую наименьшим значением.

min = { 150, 100 } = 100.

Поставщик	Потребитель				Запас
	B 1	B 2	B 3	B 4
A 1	400   4	100   4	5	9	500
A 2	8	5	100   4	300   4	400
A 3	5	6	250   3	9	250
A 4	9	7	5	150   3	150
A 5	7	150   6	-1 6	150   7	300
Потребность	400	250	350	600

 

От ячеек цикла  с четными номерами отнимает 100. К  ячейкам с нечетными номерами прибавляем 100.

Поставщик	Потребитель				Запас
	B 1	B 2	B 3	B 4
A 1	400   4	100   4	5	9	500
A 2	8	5	100 - 100   4	300 + 100   4	400
A 3	5	6	250   3	9	250
A 4	9	7	5	150   3	150
A 5	7	150   6	+ 100 -1 6	150 - 100   7	300
Потребность	400	250	350	600