3.3. Определение начального плана транспортировок. Методы "северо-западного" угла, минимального элемента, Фогеля

Рассмотрим три метода нахождения начального решения транспортной задачи: метод "северо-западного" угла, метод минимального элемента и метод Фогеля.

Метод "северо-западного" угла

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

Шаг 2. Транспортную таблицу начинают заполнять с левого верхнего (северо-западного) угла. При заполнении двигаются по строке вправо и по столбцу вниз. В клетку, находящуюся на пересечении первой строки и первого столбца, помещается максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос: . Если , то и предложение первого поставщика полностью исчерпано. Первая строка вычеркивается, и двигаются по столбцу вниз. В клетку, находящуюся на пересечении первого столбца и второй строки, помещается максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос: . Если , то . Спрос первого потребителя удовлетворен. Первый столбец вычеркивают и двигаются по второй строке вправо. Заполнив клетку, стоящую на пересечении второй строки и второго столбца, переходят к заполнению следующей третьей клетки второй строки, либо второго столбца. Процесс продолжают до тех пор, пока не исчерпается предложение и не удовлетворится спрос. Последняя заполненная клетка находится в последнем -м столбце и последней-й строке.

Пример 3.3.1

Определить начальное решение по методу "северо-западного" угла для транспортной задачи из примера 3.1.1.

Решение.

Транспортная таблица имеет следующий вид (табл. 3.3.1):

Таблица 3.3.1

В первую клетку помещают: . Спрос первого потребителя полностью удовлетворен, первый столбец вычеркивают. Остаток сырья в первом пункте составляет: 160–120=40 усл. ед. Двигаемся по первой строке вправо. Предложение поставщика исчерпано, первая строка вычеркивается. Второму потребителю не хватает 50–40=10 усл. ед. Двигаемся по второму столбцу вниз; Второй столбец вычеркивается. Двигаемся по второй строке вправо. Вторая строка вычеркивается. Двигаемся по третьему столбцу вниз. Спрос третьего потребителя удовлетворен. Двигаемся по третьей строке вправо. Таблица заполнена. Число ненулевых значений ,; равно 6. Число базисных переменных задачи 3+4–1=6. Остальные 3*4–6=6 переменных являются свободными, их значения равны нулю.

Начальный план перевозок имеет вид

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

.

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

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

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

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

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

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

Пример 3.3.2

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

Таблица 3.3.2

Минимальный тариф ,. Первую строку вычеркивают. Минимальный тариф для оставшихся клеток, . Второй столбец вычеркивают.

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

, . Третий столбец вычеркивают.

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

, . Первый столбец вычеркивают.

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

, . Для одной оставшейся клетки .

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

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

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

Метод Фогеля

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

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

ШаеЗ. В строке или в столбце, которым соответствует наибольшая разность, выбирают клетку с наименьшим тарифом. Переход к шагу 4.

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

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

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

Пример 3.3.3

Определим начальное решение по методу Фогеля для транспортной задачи из примера 3.1.1 (табл. 3.3.3).

Решение.

Таблица 3.3.3

Разности по строкам будем записывать в правой части табл. 3.3.3, разности по столбцам – внизу табл. 3.3.3. Максимальную разность будем отмечать кружком. Наименьший тариф в первой строке равен 1. Ближайший к нему равен 2. Разность равна 1. Наименьший тариф во второй строке 4. Ближайшее к нему значение 5. В третьей строке 2 и 3, соответственно. Разности по всем строкам равны 1.

В первом столбце наименьший тариф . Ближайшее значение,. Во втором столбце наименьшее значение. Ближайшее значение,.

Третий столбец: ,,.

Четвертый столбец: ,, .

Максимальная из всех разностей 4 находится в четвертом столбце. В этом столбце клетка с наименьшим тарифом находится в первой строке. В эту клетку помещаем максимально возможное значе­ние:. Четвертый потребитель полностью удов­летворил свой спрос, и четвертый столбец вычеркиваем.

Повторяем предыдущие действия без учета вычеркнутых и запол­ненных клеток.

Первая строка: минимальный тариф . Ближайшее значение, .

Вторая строка: минимальный тариф . Ближайшее значение,.

Третья строка: , , .

Первый столбец: минимальный тариф . Ближайшее значе­ние, .

Второй столбец: , , .

Третий столбец: , , .

Максимальная разность равна 6 и стоит в первой строке. Минимальный тариф в первой строке . В эту клетку помещаем. Вычеркиваем первую строку.

Повторяем все действия без учета первой строки и четвертого столбца.

Вторая строка: , , .

Третья строка: , , .

Первый столбец: , , .

Второй столбец: , , .

Третий столбец: , , .

Максимальная разность равна 6 и стоит в третьем столбце. Мини­мальный из оставшихся тарифов в этом столбце ,. Спрос третьего потребителя удовлетво­рен, третий столбец вычеркиваем.

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

Вторая строка: , , .

Третья строка: , , .

Первый столбец: , , .

Второй столбец: , , .

Максимальная разность стоит в третьей строке. Минимальный та­риф в этой строке , .

Предложение поставщика исчерпано, и третью строку вычеркиваем.

Осталась одна строка транспортной таблицы. Это вторая строка. В этой строке сначала заполняем клетку с наименьшим тарифом ,. Оставшееся предложение вто­рого поставщика записываем в единственную свободную клетку.

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

Затраты на перевозку по этому плану составляют

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

Изложенные методы нахождения начального решения не един­ственные. В качестве начального решения может быть взят любой набор чисел, удовлетворяющих ограничениям (3.2.9)—(3.2.12) (на­пример, полученный по методу "юго-восточного" угла). Читатель может придумать свой собственный метод получения начального решения.