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

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

(1)

При условиях

(2)

(3)

(4)

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

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

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

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

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

(5)

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

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

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

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

Число переменных в транспортной задаче с Т пунктами отправления и П пунктами назначения равно Пт, а число уравнений в системах (2) и (3) равно П+т. Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно П+т-1. Следовательно, опорный план транспортной задачи может иметь не более П+Т-1 отличных от нуля неизвестных.

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

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

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

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

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

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

(6)

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

(7)

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

< Предыдущая		Следующая >