Транспортная задача является задачей наиболее рационального прикрепления пунктов назначения к пунктам отправления, чтобы транспортные издержки были минимальными.
Пример транспортной задачи рассматривался во введении. В общей постановке она выглядит следующим образом.
Имеется m пунктов отправления с запасами ai единиц груза в каждом. Имеется n пунктов назначения с потребностями в грузах bj. Стоимость перевозки одной единицы груза по соответствующему маршруту равна cij.
Матрица (cij)mxn называется матрицей тарифов (транспортных расходов).
Планом транспортной задачи называется матрица X = (x ij)mxn, где каждое число xij обозначает количество единиц груза, которое надо доставить из i -го пункта отправления в j -й пункт назначения. Матрица X называется еще матрицей перевозок. Чаще всего матрицы тарифов и перевозок совмещают в одну двойную матрицу (табл. 2).
Таблица 2.
Матрица стоимости и перевозок общий вид
Пункты назначения Пункты отправления | B1 | B2 | … | Bj | … | Bn | Запасы груза |
A1 | с11 х11 | с12 х12 | … | с1j х1j | … | с1n х1n | a1 |
А2 | с21 х21 | с22 х22 | … | с2j х2j | … | с2n х2n | a2 |
… | … | … | … | … | … | … | … |
Аi | сi1 хi1 | сi2 хi2 | … | сij хij | … | сin хin | ai |
… | … | … | … | … | … | … | … |
Аm | сm1 хm1 | сm2 хm2 | … | сmj хmj | … | сmn хmn | am |
Потребности в грузе | b1 | b2 | … | bj | … | bn |
Стоимость перевозок z можно записать в виде двойной суммы
|
|
. (1)
Это и будет функционалом задачи, для которого надо отыскать минимум.
На искомые перевозки xij по смыслу задачи необходимо наложить следующие условия:
1) условия вывоза всех грузов из пунктов отправления (m уравнений):
(2)
2) условия доставки потребителям необходимого количества грузов (n уравнений):
(3)
3) условия неотрицательности переменных, исключающие обратные перевозки:
(4)
Эти условия образуют систему ограничений. Любой план, компоненты которого удовлетворяют этой системе, будет допустимым.
Равенство запасов потребностям есть необходимое и достаточное условие совместности и, следовательно, разрешимости транспортной задачи.
Транспортная задача, в которой выполнено указанное условие, называется сбалансированной (закрытой).
Однако может случиться, что в рассматриваемых пунктах запасы не равны потребностям: или , т. е. запасы превосходят потребности, или же — запасы не обеспечивают потребностей.
Такая модель задачи называется несбалансированной (открытой). Для нее тоже можно отыскать план с минимумом транспортных расходов, но не будут удовлетворены потребности или не будет вывезен весь груз, так как нельзя подобрать такую систему чисел, которая при суммировании по строкам давала бы один результат, а при суммировании по столбцам — другой.
|
|
Для решения задачи поступаем следующим образом.
Первый случай. . В математическую модель транспортной задачи введем фиктивный (n + 1)-й пункт назначения. Для этого в матрице задачи предусмотрим один столбец (табл. 3), для которого потребность будет равна излишку груза:
.
Таблица 3
Добавление фиктивного пункта назначения
Пункты назначения Пункты отправления | B1 | B2 | … | Bn | Bn+1 | Запасы груза |
A1 | с11 х11 | с12 х12 | … | с1n х1n | 0 х1,n+1 | a1 |
А2 | с21 х21 | с22 х22 | … | с2n х2n | 0 х2,n+1 | a2 |
… | … | … | … | … | … | … |
Аm | сm1 хm1 | сm2 хm2 | … | сmn хmn | 0 хm,n+1 | am |
Потребности в грузе | b1 | b2 | … | bn | bn+1 |
Все тарифы на доставку груза в этот пункт будем считать равными нулю. Получим новую задачу, причем для старой и новой задачи функционал будет один и тот же, так как цены на дополнительные перевозки равны нулю:
Фиктивный потребитель обеспечивает совместность системы ограничений, не внося искажений в решение.
Второй случай. Если запасов не хватает для удовлетворения потребностей, т. е. , то вводим фиктивный (m + 1)-й пункт отправления, которому приписываем запас груза, равный
,
тарифы на доставку грузов из этого фиктивного склада опять, полагаем нулевыми. В матрице добавится одна строка (табл. 4)
Таблица 4.
Добавление фиктивного склада
Пункты назначения Пункты отправления | B1 | B2 | … | Bn | Запасы груза |
A1 | с11 х11 | с12 х12 | … | с1n х1n | a1 |
А2 | с21 х21 | с22 х22 | … | с2n х2n | a2 |
… | … | … | … | … | … |
Аm | сm1 хm1 | сm2 хm2 | … | сmn хmn | am |
Аm+1 | 0 хm+1,1 | 0 хm+1,2 | … | 0 хm+1,n | am+1 |
Потребности в грузе | b1 | b2 | … | bn |
на функционале это не отразится, а система ограничений задачи станет совместной, т. е. станет возможным отыскание оптимального плана на минимум стоимости перевозок.
Транспортная задача имеет такую специфику.
1. Ограничения заданы уравнениями (всего m+n уравнений).
2. Каждое неизвестное плана входит только в два уравнения. Неизвестное xij входит в уравнение с правой частью ai и в уравнение с правой частью bj.
3. Коэффициентами в уравнениях являются единицы.