 |
Постановка транспортной задачи
|
|
|
|
Одной из задач линейного программирования является транспортная задача, которая формулируется следующим образом.
Имеется т пунктов хранения (баз) A1, A2,..., Am, на которых сосредоточены запасы некоторого товара в количествах соответственно a1, a2,..., am условных единиц. Кроме того, имеется п пунктов потребления (магазинов) B1, B2,..., Bn, подавших заявки соответственно на b1, b2,..., bn единиц товара. Стоимость перевозки единицы товара из пункта Ai (i = 1, 2, …, m) в пункт Bk (k = 1, 2, …, n) составляет cik денежных единиц). Предполагается, что общая стоимость перевозки партии товара пропорциональна количеству товара в этой партии.
Условия транспортной задачи могут быть представлены с помощью матрицы транспортной задачи:
Если суммарное предложение товара равно суммарному спросу на него
то мы имеем транспортную задачу закрытого типа. В случае, если сумма запасов не равна сумме заявок, имеем задачу открытого типа. Ее легко свести к задаче закрытого типа. Если сумма заявок превышает сумму запасов, вводится фиктивный поставщик, «запас» которого равен разности между суммой заявок и суммой запасов. В случае, когда сумма запасов превышает сумму заявок, вводится фиктивный потребитель, «заявка» которого равна разности между суммой запасов и суммой заявок. Стоимости всех фиктивных перевозок полагают равными нулю. Таким образом, задача открытого типа сводится к задаче закрытого типа.
Рассмотрим транспортную задачу закрытого типа. В этой задаче требуется составить такой план перевозок товара, чтобы вывезти весь хранящийся на базах запас товара, удовлетворить заявки всех магазинов, добиться минимальной суммарной стоимости всех перевозок.
|
|
|
Построим математическую модель транспортной задачи.
Укажем переменные, подлежащие определению в результате решения задачи, и введем понятие плана.
Обозначим через xik количество товара, направляемого из пункта Ai в пункт Bk (i = 1, 2, …, m; k = 1, 2, …, n). Таким образом, в задаче имеется m´n оптимизируемых переменных, и план в транспортной задаче имеет вид x=(x11, x12, …, xmn).
План перевозок в транспортной задаче удобно представить в виде матрицы
получая наглядное представление о том, какое количество товара перевозится от определенной базы к определенному магазину.
Составим уравнения и неравенства, определяющие множество допустимых планов.
План x=(x11, x12, …, xmn) является допустимым, если он обеспечивает вывоз всего хранящегося на базах товара:
он удовлетворяет заявки всех магазинов:
все оптимизируемые переменные неотрицательны: x³0.
Построим целевую (критериальную) функцию
Из двух допустимых планов транспортной задачи лучшим считается тот, которому соответствуют меньшие транспортные издержки (общая стоимость перевозки товаров из мест хранения в места потребления). Таким образом, критериальной функцией в транспортной задаче является функция, сопоставляющая плану x соответствующие транспортные издержки:
E(x) = c11 x11 + c12 x12 + … + cmn xmn
Выпишем получившуюся задачу математического программирования
Поскольку транспортная задача является задачей линейного программирования, она может быть решена симплекс-методом. В силу специфики задачи можно вместо симплекс-таблиц пользоваться таблицами более простого вида (так называемыми транспортными таблицами):
Таблица 9
| Базы | Магазины | Запас | ||||||||
| B1 | B2 | … | Bn | |||||||
| A1 | c11 | c12 | … | c1n | a1 | |||||
| x11 | x12 | x1n | ||||||||
| A2 | c21 | c22 | … | c2n | a2 | |||||
| x21 | x22 | x2n | ||||||||
| … | …
| … | … | … | ... | |||||
| Am | cm1 | cm2 | … | cmn | am | |||||
| xm1 | xm2 | xmn | ||||||||
| Спрос | b1 | b2 | ... | bn | ||||||
Решение транспортной задачи может быть получено путем некоторых преобразований транспортной таблицы. Как и в общем случае, оптимальное решение ищется среди опорных решений. В системе ограничений-равенств транспортной задачи можно выделить т + п - 1 базисных переменных, выразив их через остальные (свободные). В опорном решении свободные переменные равны нулю. Эти нули в таблицу не записываются, а соответствующие (пустые) клетки таблицы называются свободными клетками. Заполненные клетки таблицы соответствуют базисным переменным и называются базисными клетками. Таким образом, в транспортной таблице, представляющей опорный план, имеется т + п - 1 заполненных клеток.
|
|
|
