Транспортная задача. Постановка задачи . Есть однотипная продукция, которая находится на складах А1, А2, А3 и А4

 

Постановка задачи. Есть однотипная продукция, которая находится на складах А₁, А₂, А₃ и А₄. Запасы на каждом складе составляют а₁=200, а₂=350, а₃=300 и а₄=150. Это можно записать виде матрицы: . Есть потребители этой продукции В₁, В₂, В₃ и В₄. Их потребности составляют в₁=170; в₂=240; в₃=410 и в₄=180. Это можно записать виде матрицы: . Известна матрица стоимости перевозки единицы груза от каждого поставщика каждому потребителю:

.

Составить план перевозок таким образом, чтобы:

1) все товары были вывезены;

2) все потребители были удовлетворены;

3) общая стоимость перевозок была бы минимальной.

 

Решение. Проверим, выполняется ли балансовое условие, т.е. равен ли спрос и предложение.

1) предложение составляет: 200+350+300+150=1 000;

2) спрос равен: 170+240+410+180=1 000;

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

 

Метод минимальной стоимости. Выбираем клетки с минимальной стоимостью, сравниваем потребности и возможности по данной клетке и делаем в нее поставку в размере: и так далее до тех пор, пока мы заполним всю таблицу.

Таблица перевозок

 

	В1	В2	В3	В4
А1	170	- - -	- - -
А2	- - -			- - -
А3	- -+ -		- - -
А4	- - -	- - -		- - -

 

1. Наименьшая стоимость =1. На складе есть 150, а нужно 410. Поэтому поставляем 150, и тогда на складе А₄ ничего не осталось, его вычеркиваем.

2. следующая цена =2. Сравниваем: у А₁ есть 200, но В₁ нужно 170. берем 170 и потребителя В₁ вычеркиваем, т.е. ему уже ничего не нужно. Аналогично сравниваем В₃ (ему еще нужно 260) и склад А₂ (там есть 350). Берем 260 и вычеркиваем потребителя В₃, т. к. он все уже получил.

3. следующая стоимость =3. У А₁ еще осталось 200-170=30, которые отдаем В₄, и А₁ вычеркиваем. Аналогично для В₂ мы можем взять 90, которые остались у А₂. Т.к. у А₂ уже ничего нет, то его вычеркиваем.

4. Клетки с ценами =4 и =5 уже вычеркнуты. Следующая стоимость =6. В₂ нужно еще 150, которые есть у А₃ – берем их.

5. Осталась клетка со стоимостью =7. Нужно 150 и есть 150, т.к. задача закрытая.

План составлен.

Проверяем его на оптимальность по методу потенциалов.

Исходному плану отвечала стоимость перевозок:

Таблица потенциалов (начало)

 

	V1=2	V2=2	V3=1	V4=3
U1=0
U2=1
U3=4
U4=0

 

В те клетки, куда были сделаны поставки, проставляем стоимость перевозки. Это сумма потенциалов по заполненным клеткам.

Пусть U1= 0, тогда U1+ V1=2, следовательно, V1= 2.

Так как U1=0, а U1+ V4=3, то V4= 3.

Так как U3+ V4=7, то U3= 4

Так как U3+ V2=6, то V2= 2.

Так как U2+ V2=3, то U2= 1.

Так как U2+ V3=2, то V3= 1.

Так как U4+ V3=1, то U4= 0.

Потенциалы расставлены, теперь проверяем оценки для свободных клеток:

.

Сумму потенциалов записываем в левом нижнем углы ячейки, а стоимость – в правом верхнем.

 

Таблица потенциалов (окончание)

 

	V1=2	V2=2	V3=1	V4=3
U1=0
U2=1
U3=4
U4=0

 

Т.к. есть положительная оценка, то план не оптимальный: .

Делаем поставку в клетку с положительной оценкой. Контур перераспределения начинаем с той клетки, куда делаем поставку, и затем поворачиваем под прямым углом только в заполненных клетках (контур показан пунктиром). Ставим по очереди знаки «+» и «-». Отрицательным углам отвечают поставки 170 и 150. Выбираем меньшее: =150.

Выигрыш функции цели:

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

 

	В1	В2	В3	В4
А1
А2		90
А3
А4		+

 

Стоимость перевозок по этому плану:

Ему соответствует таблица потенциалов:

 

	V1=2	V2=4	V3=3	V4=3
U1=0
U2= -1
U3=2
U4= -2

 

Положительных оценок нет, значит, план оптимальный. Запишем в виде матрицы:

Этому плану отвечала стоимость перевозок:

.

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

. Получим:

 

	В1	В2	В3	В4
А1
А2
А3
А4