Вопрос 39. Транспортная задача: постановка, составление начального опорного плана, метод решения

1.1. Постановка и типы транспортных задач

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

Рассмотрим такую задачу.

Имеется m поставщиков Аi и n потребителей В_j. Количество груза, находящегося у потребителя А_i, будем обозначать через a_i(i= ). Количество груза, необходимое потребителю В_j – через b_j(j= ). Дана матрица тарифов (издержек или транспортных расходов).

где c_ij – стоимость перевозки единицы груза от i-го поставщика к j-му потребителю.

Планом транспортной задачи называется матрица

где x_ij обозначает количество груза, которое надо доставить от i-го поставщика к j-му потребителю.

Общие суммарные затраты, связанные с реали­зацией плана перевозок, можно представить целевой функцией:

F=c₁₁x₁₁+c₁₂x₁₂+…+c_1nx_1n+c₂₁x₂₁+c₂₂x₂₂+c_2nx_2n+…+c_m1x_m1+c_m2x_m2+…+c_mnx_mn (1)

Математическая модель задачи выглядит так:

(2)

при ограничениях:

(3)

Система ограничений (3) содержит m+n урав­нений с m • n переменными.

Если суммарный объем груза поставщиков равен суммарному спросу потребителей, то есть

(4)

то это транспортная задача с закрытой моделью.

А если или , то это транспортная задача с открытой моделью.

Равенство (4) является необходимым и доста­точным условием совместности ограничений задачи.

Для транспортной задачи важное значение имеет теорема о ранге матрицы.

Теорема

Ранг матрицы транспортной задачи на единицу меньше числа уравнений, то есть

г(А) = m+n-1. (5)

С учетом этой теоремы в каждой матрице перевозок опорный план должен содержать не более m+n-1 занятых клеток, а остальные – свободные.

1.2. Методы построения начального опорного решения

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

Существует ряд методов построения начального опорного решения, наиболее простым из которых яв­ляется метод северо-западного угла. В данном методе запасы очередного поставщика используются для обес­печения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего исполь­зуются запасы следующего по номеру поставщика.

Заполнение таблицы транспортной задачи начина­ется с левого верхнего угла и состоит из ряда одно­типных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потре­бителя, заполняется только одна клетка и, соответс­твенно, исключается из рассмотрения один поставщик или потребитель.

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

Метод минимальной стоимости прост, он позволяет построить опорное решение, достаточно близкое к оп­тимальному, так как использует матрицу стоимостей транспортной задачи С = (с_ij), i=1, 2, ..., m, j=1, 2, …, n. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых за­полняется только одна клетка таблицы, соответству­ющая минимальной стоимости , и исключает­ся из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую , заполняют по тем же пра­вилам, что и в методе северо-западного угла. Постав­щик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь затем пос­тавщик исключается из рассмотрения. Аналогично с потребителем.