double arrow

Постановка транспортной задачи

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

Приведем простейшую формулировку транспортной задачи. Пусть имеется m пунктов производства однородного продукта с объемами производства и n пунктов потребления с объемами потребления , причем предполагается, что

(4.1)

Обозначим через - количество груза перевозимого из i -го пункта производства в j -й пункт потребления, и через - стоимость транспортировки одного изделия (единицы груза) из пункта производства i в пункт потребления j.

Задача состоит в том, чтобы найти план перевозок , минимизирующий суммарные затраты на перевозки:

(4.2)

Переменные должны удовлетворять ограничениям по запасам и потребностям, а также условиям неотрицательности:

(4.3)

³0; i=1,2,…, m, j=1,2,…,n (4.4)

Условия (4.3) и (4.4) образуют систему ограничений: первая группа ограничений (4.3) указывает, что суммарный объем перевозок из некоторого исходного пункта равен произведенному количеству этой продукции; вторая группа ограничений (4.3) требует, чтобы суммарные перевозки продукции в некоторый пункт потребления полностью удовлетворили спрос на эту продукцию. Условия баланса (4.1) означают, что суммарный объем производства равен суммарному спросу.

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

Теорема 4.1 Для разрешимости транспортной задачи необходимо и достаточно, чтобы ее модель была закрытой.

В реальных задачах это выполняется не всегда. Однако транспортную задачу всегда можно сбалансировать, введя фиктивный пункт- производитель или фиктивный пункт потребления (склад).

В случае, если , тогда вводится фиктивный (n+1)-й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю: сin+1 = 0 ().

Если , вводится фиктивный (m+1)-й пункт отправления с запасом груза , а cm+1, j = 0,

С помощью этих преобразований открытая транспортная задача сводится к закрытой.

Любой план перевозок , удовлетворяющий системе ограничений (4.3) и (4.4), называется допустимым.

Опорный невырожденный план транспортной задачи должен иметь ровно n+m-1 отличных от нуля неизвестных.

Итак, транспортную задачу можно сформулировать следующим образом.

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



Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: