Транспортная задача

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления в п пунктов назначения . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через – запасы груза в i-м пункте отправления, через – потребности в грузе в j–м пункте назначения, а через – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

(63)

при условиях

(64)

(65)

(66)

Поскольку переменные удовлетворяют системам уравнений (64) и (65) и условию неотрицательности (66), обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.

Определение 15.

Всякое неотрицательное решение систем линейных уравнений (64) и (65), определяемое матрицей , называется планом транспортной задачи.

Определение 16.

План , при котором функция (63) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывают в виде таблицы 21.

Таблица 21

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.

(67)

то модель такой транспортной задачи называется закрытой. Если же указанное условие не выполняется, то модель транспортной задачи называется открытой.

Теорема 13.

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

В случае превышения запаса над потребностью, т. е. вводится фиктивный (n+1)–й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю: Полученная задача является транспортной задачей, для которой выполняется равенство (67).

Аналогично, при вводится фиктивный (m+1)–й пункт отправления с запасом груза и тарифы полагаются равными нулю: Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. В дальнейшем будем рассматривать закрытую модель транспортной задачи. Если же модель конкретной задачи является открытой, то, исходя из сказанного выше, перепишем таблицу условий задачи так, чтобы выполнялось равенство (67).

Число переменных в транспортной задаче с т пунктами отправления и п пунктами назначения равно пт, а число уравнений в системах (64) и (65) равно п+т. Так как мы предполагаем, что выполняется условие (67), то число линейно независимых уравнений равно п+т–1. Следовательно, опорный план транспортной задачи может иметь не более п + т–1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности п+т–1, то план является невырожденным, а если меньше – то вырожденным.

Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.

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

Пример 19.

Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Решение. Обозначим через количество единиц сырья, перевозимого из i–го пункта его получения на j–е предприятие. Тогда условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:

(68)

При данном плане перевозок общая стоимость перевозок составит

(69)

Таким образом, математическая постановка данной транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений (68), при котором целевая функция (69) принимает минимальное значение.