Метод минимального элемента
Шаг 1.Составляют транспортную таблицу. Шаг 2.Выбирают клетку таблицы, которой соответствует минимальное значение тарифа, и переходят на шаг 3. Шаг 3.В выбранную клетку аналогично методу "северо-западного" угла помещают максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос. После этого, если предложение производителя исчерпано, вычеркивают соответствующую строку; если спрос удовлетворен, вычеркивают соответствующий столбец. Если все клетки заполнены или вычеркнуты, то план перевозок построен. В противном случае переходят к шагу 2 без учета заполненных и вычеркнутых клеток. Пример 4.3 Определить начальное решение по методу минимального элемента для транспортной задачи из примера 4.1. Решение записано в табл. 4.3. Таблица 4.3
Минимальный тариф с 13 = 1, x 13 = min(160,190) = 160. Первую строку вычеркивают. Минимальный тариф для оставшихся клеток c 32= 2, x 32 = min(170,50) = 50. Второй столбец вычеркивают. Для оставшихся клеток минимальный тариф: с 33 = 3, х 33 = min(170 – 50,190 -160) = 30. Третий столбец вычеркивают. Для оставшихся клеток минимальный тариф: c 21 = 4, х 21 = min(140,120) = 120. Первый столбец вычеркивают. Для оставшихся клеток минимальный тариф: с 34 = 6, х 34 = min(170 – 50 – 30,110) = 90. Для одной оставшейся клетки х 24 = min(140 -120,110 – 90) = 20. План перевозок, полученный по методу минимального элемента, имеет вид Стоимость перевозок по этому плану составляет S1 =160*1+120*4+20*8+50*2+30*З+90*6=1530. Стоимость перевозок, полученных по методу минимального элемента, обычно бывает меньше стоимости перевозок, полученных по методу "северо-западного" угла.
|
