Dthxb

  • 27 мая 2012 г.
  • 552 Слова
Метод минимальной стоимости
Метод минимальной стоимости прост и позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачиC=(cij).
Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости:

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

Решение:
1. Запишемотдельно матрицу стоимостей для того, чтобы было удобнее выбирать минимальные стоимости.

2. Среди элементов матрицы стоимостей выбираем наименьшую стоимость C11=1, отмечаем ее кружочком. Данная стоимостьимеет место при перевозке груза от 1-го поставщика 1-му потребителю. В соответствующую клетку записываем максимально возможный объем перевозки:
x11 = min {a1; b1} = min {60; 40} =40 т.е. минимум между запасами1-го поставщика и запросами 1-го потребителя.
2.1. Запасы 1-го поставщика уменьшаем на 40.
2.2. Исключаем из рассмотрения 1-го потребителя, так как его запросы полностью удовлетворены. В матрице Cвычеркиваем 1-ый столбец.
3. В оставшейся части матрицы C минимальной стоимостью является стоимость C14=2. Максимально возможная перевозка, которую можно осуществить от...
tracking img