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

 

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

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

6 * 100 - 7 * 100 + 4 * 100 - 4 * 100 = ( 6 - 7 + 4 - 4 ) * 100 = -1 * 100 =  ₅₃ * 100.

Выражение стоящее в скобках равно оценке нового маршрута

Поэтому новая стоимость  доставки вычисляется именно так:

S = 6750 +  ₅₃ * 100 = 6750 - 1 * 100 =   6650 ден. ед.

Один маршрут  из построенного цикла, по которому ничего не доставляется, мы должны исключить.

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

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

 

Шаг 2

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

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

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

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

Примем v4 = 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
A5B2 :	v2 + u5 = 6	v2 = 6 - 7 = -1
A5B3 :	v3 + u5 = 6	v3 = 6 - 7 = -1
A1B2 :	v2 + u1 = 4	u1 = 4 - ( -1 ) = 5
A3B3 :	v3 + u3 = 3	u3 = 3 - ( -1 ) = 4
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	4	400   4	u 2 = 4
A 3	5	6	250   3	9	u 3 = 4
A 4	9	7	5	150   3	u 4 = 3
A 5	7	150   6	100   6	50   7	u 5 = 7
V i	v 1 = -1	v 2 = -1	v 3 = -1	v 4 = 0

 

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

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

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

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

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

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

A2B3 :          23 = 4 - ( 4 + ( -1 ) ) = 1

A3B1 :          31 = 5 - ( 4 + ( -1 ) ) = 2

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

A3B4 :          34 = 9 - ( 4 + 0 ) = 5

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

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

A4B3 :          43 = 5 - ( 3 + ( -1 ) ) = 3

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

 

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

 

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

Ответ:

X опт =		400	100	0	0
		0	0	0	400
		0	0	250	0
		0	0	0	150
		0	150	100	50

 

 

S = 6650 ден. ед.

 

 

 

 

Заключение.

Мне была поставлена задача найти оптимальный план перевозок  обеспечивающий минимальные транспортные затраты перевозки древесины  по всему лесопромышленному холдингу.

Задача была решена методом  минимального элемента. Этот метод  был выбран как приближенный к  оптимальному. Результат соответствует тому, который был получен при расчетах  с использование программы в Excel.

Таким образом , поставленная задача выполнена –оптимальный план перевозки древесины составлен.