Метод минимального элемента (минимальной стоимости)

Метод минимальной стоимости прост, он позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи Как и метод северо-западного угла, он состоит из ряда однотипних шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости , и исключаетсч из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую , заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запасы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулюЮ то на том шаге, корда от данного постащика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лиш затем поставщик исключается из рассмотрения. Аналогично с потребителем.

Пример:

Имеется три поставщика А₁,А₂ и А₃, а так же четыре потребителя В₁,В₂,В₃ и В₄. Количество груза, находящегося у поставщика, равно соответственно: Количество груза, необходимого потребителю В_j, равно соответственно: Данаматрица тарифов (издержек или транспортных расходов):

Решение:

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

1. Способ северо-западного угла

Таблица 4.7

	В1	В2	В3	В4
A1
		-	-	60,20,0
A2
-				40,35,15
A3
-	-	-		35,0
bj	40,0	25,5,0	20,0	50,35.0

X=

F=5*40+4*20+2*5+6*20+3*15+4*35=595(y.d.e)

2. Способ минимального элемента.

Таблица 4.8

	В1	В2	В3	В4
A1
-	-			60,40,0
A2
		-		40,15,5
A3
	-	-	-	35,0
bj	40,35,0	25,0	20,0	50,10,0

X=

F=1*20+2*40+4*5+2*25+3*10+7*35=445(y.d.e)

Таким образом, опорный план, найденный способом минимального элемента, ближе к оптимальному, чем план, найденный способом северо-западного угла.

Дата добавления: 2014-01-04