Лекция 4–6
8. Транспортная задача
Рассмотрим одну из важнейших задач линейного программирования - транспортную задачу. Это задача наиболее рационального прикрепления пунктов отправления грузов к пунктам их назначения, чтобы общая стоимость перевозок была минимальной. Являясь одной из задач линейного программирования, транспортная задача, конечно, может быть принципиально решена алгоритмом симплекс-метода.
Но непосредственное применение симплекс-метода к транспортной задаче обычно не целесообразно, так как , являясь универсальным методом решения любой задачи линейного программирования, он не учитывает специфики условий транспортной задачи, и применение симплекс-метода к ее решению оказывается слишком громоздким.
Один из наиболее распространенных методов решения транспортной задачи – метод потенциалов, полностью использующий особенности условий этой задачи и приводящий к цели значительно быстрее и проще, симплекс-метод.
Транспортная задача формулируется так:
В данных пунктах производится некоторый однородный продукт в количествах соответственноединиц. Этот продукт следует доставить взаданных пунктов назначения, потребляющих его соответственно в количествах. Пусть стоимость перевозки единицы продукта изго пункта производства вй пункт назначения (потребления) равна, а соответствующее количество единиц перевозимого продукта равно(;) Условия задачи запишем компактно в виде следующей таблицы (двойной матрицы):
|
b1 |
b2 |
… |
… |
bn |
a1
|
c11
x11 |
c12
x12 |
… |
… |
c1n
x1n |
a2
|
c21
x21 |
c22
x22 |
… |
… |
c2n
x2n |
…
|
… |
… |
… |
… |
… |
…
|
… |
… |
… |
… |
… |
am
|
cm1
xm1 |
cm2
xm2 |
… |
… |
cmn
xmn |
(1.4.1)
Совокупность чисел, т.е. матрицу, будем называтьпланом перевозок, а матрицу матрицей транспортных издержек.
План называется допустимым, если числа удовлетворяют следующим естественным ограничениям:
(1.4.2)
(),
(),
в которых первые равенств означают, что из каждого пункта производства вывозится весь продукт, а последниеравенств означают, что каждый пункт потребления полностью удовлетворяется.
Транспортная задача заключается в отыскании среди допустимых планов оптимального, т.е. такого, по которому общая стоимость перевозок
(1.4.3)
минимальна.
Если система (1.4.2) совместна,
,
таким образом, условие
(1.4.4)
необходимо для совместности (1.4.2). Условие (1.4.4) является и достаточным для совместности (1.4.2). В самом деле, при выполнении условия (1.4.4) значения
(;),
как легко проверить, удовлетворяют системе (1.4.2) (нетрудно проверить, что любое из уравнений (1.4.2) является следствием остальных, образующих линейно независимую систему).
Таким образом, транспортная задача относится к задачам линейного программирования и решается алгоритмом симплекс-метода. Однако ввиду исключительной практической важности и специфики ограничений (1.4.2):
а) ограничения заданы в виде уравнений,
б) каждая неизвестная входит лишь в два уравнения,
в) коэффициенты при неизвестных – единицы, для ее решения созданы специальные алгоритмы, значительно менее громоздкие, чем алгоритм симплекс-метода. Один из них – м е т о д п о т е н ц и а л о в – представляет собой приспособление общего метода Л,В, Канторовича для решения транспортной задачи.
Другой, так называемый в е н г е р с к и й м е т о д усовершенствован для решения частного случая транспортной задачи – задачи о назначениях (или о выборе).