7. Транспортная задача
Классическая транспортная задача – задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов отправления в пункты назначения.
На m
станциях отправления
сосредоточенно соответственно
единиц некоторого однородного груза.
Этот груз следует перевезти в n
пунктов назначения
,
причем в каждый из них надлежит завезти
соответственно
единиц этого груза.
Известны транспортные
издержки
,
связанные с перевозкой единицы груза
из пункта
.
Требуется составить такой план перевозок, при котором сумма транспортных издержек окажется минимальной.
Рассмотрим закрытую модель, т. е. будем рассматривать задачи в которых суммарные запасы грузов у поставщиков равны суммарным потребностям потребителей:
.
Составим математическую модель задачи.
Ограничения по ресурсам:
Ограничения по потребителям:
Условия неотрицательности:
Целевая функция:
Транспортную задачу решают методом потенциалов, но применить его можно только в том случае, когда найден какой-то план задачи. Существует несколько методов нахождения исходного допустимого решения (плана): метод «северо-западного» угла, метод минимального тарифа.
Метод «северо-западного» угла
Не учитывая
стоимости перевозки единицы груза,
начинаем заполнение таблицы с
удовлетворения потребностей первого
потребителя
за счет запаса поставщика
.
Затем удовлетворяем потребности
потребителя
,
и так далее, пока все потребители не
будут удовлетворены, а поставщики
разгружены.
Метод минимального тарифа
Выбираем клетку с наименьшим тарифом ; записываем в клетку максимально возможную поставку.
При этом могут встретиться три случая:
В первом случае
потребности
удовлетворятся полностью запасами
поставщика
.
Столбец
исключаем из рассмотрения.
Во втором исключаем
строку
,
записав в клетку
.
В третьем принимаем
.
Затем записываем ноль в следующую по
строке или столбцу клетку и исключаем
и пункт
.
На каждом шаге таблица сокращается, и в итоге получим допустимый план задачи.
Замечание 1. В транспортной таблице занятые клетки соответствуют базисным неизвестным, а пустые клетки свободным неизвестным. Число базисных неизвестных в системе ограничений транспортной задачи равно m+n-1, где m – число поставщиков, n – число потребителей.
Алгоритм решения транспортной задачи методом потенциалов
Составляем исходный опорный план.
Находим потенциалы потребителей и поставщиков. Для этого составляем систему уравнений
,
где
– тарифы занятых клеток. Уравнений в
системе будет столько, сколько заполнено
клеток, т. е. m+n-1.
Потенциалов m+n.
Поэтому, положим
,
остальные неизвестные находим из
уравнений.
Для каждой свободной клетки находим сумму потенциалов, соответствующих этой клетке. Назовем ее косвенным тарифом и обозначим
.Определим разности между тарифами и косвенными тарифами
.
Эти разности называются характеристиками свободных клеток.
Если все характеристики неотрицательны, то план оптимален.
Если среди характеристик есть хотя бы одна отрицательная, то план можно улучшить. Отрицательные характеристики записывают в нижний левый угол клетки.
Для улучшения плана занесем поставку в ту клетку, которая соответствует наименьшей отрицательной характеристике. Для определения величины поставки отметим выбранную клетку знаком «+» и построим для нее «контур».
Для контура характерно следующее:
1) контур является замкнутой ломаной, состоящей из горизонтальных и вертикальных отрезков;
2) вершины контура лежат в занятых клетках, за исключением клетки, для которой строится контур;
3) отрезки контура могут пересекать занятые клетки, не являющиеся вершинами данного контура;
4) каждой свободной клетке соответствует только один контур.
Некоторые разновидности контуров показаны на рисунке.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Двигаясь по контуру от клетки, отмеченной знаком «+», поочередно проставляем в вершинах контура знаки «–» и «+».
Затем находим
–
величина грузов в клетках, отмеченных
знаком «–». Q
и определяет величину груза, который
надо занести в свободную клетку. Далее,
двигаясь по контуру, прибавляем Q
к величинам поставок, находящихся в
«положительных» клетках, и вычитаем Q
из величин поставок, находящихся в
«отрицательных» клетках. Получаем
новый опорный план. Проверяем его на
оптимальность.
Процесс продолжается до тех пор, пока все характеристики свободных клеток не станут неотрицательными.
Замечание 2. Часто приходится решать задачи, в которых нарушено в ту или иную сторону условие равновесия, т. е.
.
Такие задачи называются открытыми. Чтобы привести задачу к закрытой задаче, в первом случае вводится дополнительный столбец так называемого фиктивного потребителя со спросом, равным избытку продукции
.
Все тарифы этого столбца полагаем равными нулю.
Во втором случае приведение к закрытой задаче достигается введением фиктивного поставщика с объемом возможных поставок, равным недостатку продукции
.
Стоимости перевозок от фиктивного поставщика ко всем потребителям также равны нулю.
Пример 1.
Рассмотрим задачу: имеется три поставщика
с определенными запасами однородного
груза
и четыре потребителя с известными
потребностями в этом грузе
.
Кроме того, задана матрица тарифов:
.
Модель задачи
открытая, так как
:
.
Поэтому вводим фиктивного потребителя с потребностью в 20 единиц груза и нулевыми тарифами.
Составляем таблицу и первоначальное распределение поставок производим по методу «северо-западного» угла:
|
10 |
20 |
20 |
50 |
20 |
|
30 |
10
|
2
- |
+ |
|
|
0 |
40 |
|
+ |
2
- |
20
|
|
1 |
50 |
|
|
|
30 |
20 |
-1 |
|
3 |
4 |
1 |
2 |
1 |
|
Число занятых клеток должно быть равно 3+5–1=7, у нас получилось 6. Это получилось потому, что при заполнении клетки (1,2) мы одновременно вычеркнули первую строку и второй столбец. Надо занести нулевую поставку в одну из клеток, расположенных рядом по строке или столбцу то клетки (1,2), т.е. или в (1,3), или в (2,2). Займем клетку (1,3). При таком расположении поставок затраты на перевозку груза составят:
.
Вычислим потенциалы
,
исходя
из того, что для занятых клеток должно
выполняться равенство
.
Полагаем, что один из потенциалов равен
нулю, например
.
Далее вычислим
характеристики для свободных клеток:
.
Отрицательные характеристики заносятся
в левый нижний угол клетки.
Выбираем клетку с наименьшей отрицательной характеристикой, т.е. (2,2). Строим контур с вершиной в этой клетке. Свободную клетку помечаем знаком «+», следующую по контуру – знаком «–» и т.д., меняя знаки. В свободную клетку заносится минимальная поставка из клеток, помеченных знаком «–». В нашем случае обе поставки равны 20 единицам. Поэтому мы вычитаем 20 единиц груза из поставок, стоящих в «отрицательных клетках» и прибавляем 20 единиц груза к поставкам, стоящим в « положительных клетках». Так как в «отрицательных клетках» было по 20 единиц груза, то после перераспределения поставок, в одну из них запишем нулевую поставку, а другую оставим пустой. Получим следующее (лучшее) распределение:
|
10 |
20 |
20 |
50 |
20 |
|
30 |
10 |
|
20 |
|
|
0 |
40 |
|
20 |
0 |
2
- |
+ |
1 |
50 |
|
|
|
3
+ |
2
- |
-1 |
|
3 |
0 |
1 |
2 |
1 |
|
При таком
распределении поставка в 20 ед. попала
в клетку с характеристикой равной –4,
следовательно функция затрат улучшилась
на
ед.
Т.о.
.
Снова полагаем
и вычисляем потенциалы. Далее, как и
прежде, вычисляем характеристики для
свободных клеток"ободную
клетку заносится минимальная поставка
из клеток, помеченных знаком "лбцу
то клетки (1,2), т.е. олбец.
|
10 |
20 |
20 |
50 |
20 |
|
30 |
1
- |
|
2
+ |
|
|
0 |
40 |
+ |
20 |
0
- |
|
20 |
1 |
50 |
|
|
|
50 |
0 |
1 |
|
3 |
0 |
1 |
0 |
-1 |
|
При таком
распределении
.
Находим потенциалы, характеристики для незанятых клеток и строим контур для клетки (2,1). Поставку, равную min (10,0) =0, перераспределяем по контуру. Получаем следующее распределение:
|
10 |
20 |
20 |
50 |
20 |
|
30 |
1
- |
|
20 |
|
+ |
0 |
40 |
0
+ |
20 |
|
|
2
- |
-1 |
50 |
|
|
|
50 |
0 |
-1 |
|
3 |
2 |
1 |
2 |
1 |
|
Продолжая вышеописанный процесс нахождения потенциалов, характеристик для пустых клеток и построение контура, приходим к следующему распределению:
|
10 |
20 |
20 |
50 |
20 |
|
30 |
|
|
20 |
|
10 |
0 |
40 |
10 |
20 |
|
|
10 |
0 |
50 |
|
|
|
50 |
0 |
0 |
|
2 |
1 |
1 |
1 |
0 |
|
Найдя для этого распределения характеристики незанятых клеток, видим, что среди них нет отрицательных характеристик, и, следовательно, мы нашли оптимальное решение, при котором функция затрат на перевозку груза достигла своего минимального значения:
.
Чтобы оптимальный план получить за меньшее число итераций, надо первоначальное распределение поставок проводить по методу «наименьшего тарифа», т.е. сначала заполнить клетки соответствующие минимальным тарифам.
Попробуйте для следующей задачи составить первоначальный опорный план по методу «наименьшего тарифа».
Решить следующие задачи:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
ОТВЕТЫ
3. Графический метод
1.
2.
3.
4.
5.
6.
7.
8.
.
9.а)
б)
10.
11.
12.
13.
14.
15.
16.
4. Симплексный метод
1.
2.
3.
4.
5. .
6.
7.
8.
9. .
10.
11.
12.
13.
14.
15.
16.
5. Метод искусственного базиса
1.
2.
3.
4. Нет решения.
5. Нет решения.
6.
7.
8. Нет решения.
9.
10.
11.
12.
13.
14.
15.
16.
6. Двойственность
1.
2.
3.
4.
5.
6.
7.
8. Нет решения.
9.
10. Нет решения.
11.
12.
13.
14.
15. Нет решения.
16.
