Метод минимального элемента

Шаг 1.Составляют транспортную таблицу.

Шаг 2.Выбирают клетку таблицы, которой соответствует минимальное значение тарифа, и переходят на шаг 3.

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

Если все клетки заполнены или вычеркнуты, то план перевозок построен. В противном случае переходят к шагу 2 без учета заполненных и вычеркнутых клеток.

Пример 4.3

Определить начальное решение по методу минимального элемента для транспортной задачи из примера 4.1. Решение записано в табл. 4.3.

Таблица 4.3

№					Предложение
	7	8	160 1	2
	120 4	5	9	20 8
	9	50 2	30 3	90 6
Спрос

 

Минимальный тариф с ₁₃ = 1, x ₁₃ = min(160,190) = 160. Первую строку вычеркивают. Минимальный тариф для оставшихся клеток c ₃₂= 2, x ₃₂ = min(170,50) = 50. Второй столбец вычеркивают.

Для оставшихся клеток минимальный тариф:

с ₃₃ = 3, х ₃₃ = min(170 – 50,190 -160) = 30. Третий столбец вычеркивают.

Для оставшихся клеток минимальный тариф:

c ₂₁ ⁼ 4, х ₂₁ = min(140,120) = 120. Первый столбец вычеркивают.

Для оставшихся клеток минимальный тариф:

с ₃₄ = 6, х ₃₄ = min(170 – 50 – 30,110) = 90. Для одной оставшейся клетки

х ₂₄ = min(140 -120,110 – 90) = 20.

План перевозок, полученный по методу минимального элемента, имеет вид

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

S₁ =160*1+120*4+20*8+50*2+30*З+90*6=1530.

Стоимость перевозок, полученных по методу минимального элемента, обычно бывает меньше стоимости перевозок, полученных по методу "северо-западного" угла.