Материал: 5021

31

Получим:

Первое неравенство выполняется как строгое неравенство, следовательно, соответствующая переменная x1 исходной задачи равна 0. Последние два неравенства обращаются в равенства, следовательно, соответствующие им переменные > 0.

Решая систему:

x1 0, x2 x3 1, 2x2 x3 1,

получим ответ для исходной задачи: X 0;10;16 , Z max 26 .

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

32

7. ТРАНСПОРТНАЯ ЗАДАЧА

Классическая транспортная задача – задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов отправления в пункты назначения.

На m станциях отправления A1 , A2 ,...,Am сосредоточенно соответственно a1 , a2 ,...,am единиц некоторого однородного груза. Этот груз следует перевезти в n пунктов назначения B1 , B2 ,...,Bn , причем в каждый из них надлежит завезти соответственно b1 ,b2 ,...,bn единиц этого груза.

33

Известны транспортные издержки cij , связанные с перевозкой единицы груза из пункта Ai в пункт Bj .

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

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

Транспортную задачу решают методом потенциалов, но применить его можно только в том случае, когда найден какой-то план задачи. Существует несколько методов нахождения исходного допустимого решения (плана): метод «северо-западного» угла, метод минимального тарифа.

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

Не учитывая стоимости перевозки единицы груза, начинаем заполнение таблицы с удовлетворения потребностей первого потребителя B1 за счет запаса поставщика A1 . Затем удовлетворяем потребности потребителя B2 , и так далее, пока все потребители не будут удовлетворены, а поставщики разгружены.

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

Выбираем клетку с наименьшим тарифом cij ; записываем в клетку

максимально возможную поставку.

При этом могут встретиться три случая:

34

Во втором исключаем строку Ai , записав в клетку Ai Bj груз ai .

В третьем принимаем xij ai . Затем записываем ноль в следующую по строке или столбцу клетку и исключаем и пункт Ai и Bj .

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

Замечание 1. В транспортной таблице занятые клетки соответствуют базисным неизвестным, а пустые клетки свободным неизвестным. Число базисных неизвестных в системе ограничений транспортной задачи равно m+n-1, где m – число поставщиков, n – число потребителей.

Алгоритм решения транспортной задачи методом потенциалов

1.Составляем исходный опорный план.

2.Находим потенциалы потребителей и поставщиков. Для этого составляем систему уравнений

ui v j cij ,

где cij – тарифы занятых клеток. Уравнений в системе будет столько,

сколько заполнено клеток, т. е. m+n-1. Потенциалов m+n. Поэтому, положим u1 0 , остальные неизвестные находим из уравнений.

3.Для каждой свободной клетки находим сумму потенциалов, соответствующих этой клетке. Назовем ее косвенным тарифом и

обозначим cij ui v j .

4. Определим разности между тарифами и косвенными тарифами

Eij cij cij .

Эти разности называются характеристиками свободных клеток. Если все характеристики неотрицательны, то план оптимален.

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

5.Для улучшения плана занесем поставку в ту клетку, которая соответствует наименьшей отрицательной характеристике. Для

определения величины поставки отметим выбранную клетку знаком «+» и построим для нее «контур».

Для контура характерно следующее:

1)контур является замкнутой ломаной, состоящей из горизонтальных

ивертикальных отрезков;

2)вершины контура лежат в занятых клетках, за исключением клетки, для которой строится контур;

3)отрезки контура могут пересекать занятые клетки, не являющиеся вершинами данного контура;

4)каждой свободной клетке соответствует только один контур.

35

Некоторые разновидности контуров показаны на рисунке.

Двигаясь по контуру от клетки, отмеченной знаком «+», поочередно проставляем в вершинах контура знаки «–» и «+».

Затем находим Q min xij , где xij – величина грузов в клетках,

отмеченных знаком «–». Q и определяет величину груза, который надо занести в свободную клетку. Далее, двигаясь по контуру, прибавляем Q к величинам поставок, находящихся в «положительных» клетках, и вычитаем Q из величин поставок, находящихся в «отрицательных» клетках. Получаем новый опорный план. Проверяем его на оптимальность.

Процесс продолжается до тех пор, пока все характеристики свободных клеток не станут неотрицательными.

Замечание 2. Часто приходится решать задачи, в которых нарушено в ту или иную сторону условие равновесия, т. е.

Такие задачи называются открытыми. Чтобы привести задачу к закрытой задаче, в первом случае вводится дополнительный столбец так называемого фиктивного потребителя со спросом, равным избытку продукции

Все тарифы этого столбца полагаем равными нулю.

Во втором случае приведение к закрытой задаче достигается введением фиктивного поставщика с объемом возможных поставок, равным недостатку продукции

Стоимости перевозок от фиктивного поставщика ко всем потребителям также равны нулю.