Решение транспортной задачи

1. Введение.

Распределительные задачи связаны с распределением ресурсов по работам, которые необходимо выполнить. Задачи этого класса возникают тогда, когда имеющихся в наличии ресурсов не хватает для выполнения каждой работы наиболее эффективным образом. Поэтому целью решения задачи, является отыскания такого распределения ресурсов по работам, при котором либо минимизируются общие затраты, связанные с выполнением работ, либо максимизируется получаемый в результате общий доход.

Типичная распределительная задача.

Таблица №1

Ресурсы	Работы, которые нужно выполнить						Объем имеющихся ресурсов
	j1	J2	…	Ji	…	Jn
R1	C1.1	C1.2	…	C1.j	…	C1.n	B1
R2	C2.1	C2.2	…	C2.j	…	C2.n	B2
…	…	…	…	…	…	…	…
Ri	Ci.1	Ci.2	…	Ci.j	…	Ci.n	Bi
…	…	…	…	…	…	…	…
Rm	Cm.1	Cm.2	…	Cm.j	…	Cm.n	Bm
Объём требуемых ресурсов	A1	A2	…	Ai	...	An

Большинство распределительных задач можно представить в виде матриц, приведенных в таблице №1. Элементы С_i,j стоящие в клетках матрицы, соответствуют затратим или доходу, отвечающим выделению, одной единицы ресурса R_i на работу J_j. Величины _С_i,j могут быть независимыми или зависимыми. Так например, затраты, обусловленные назначением одной автомашины на некоторый маршрут доставки грузов, не зависят от того какие машины назначены на обслуживание других маршрутов. В то же время при распределении средств между подразделениями фирмы доход от затрат определенного количества денег одним ее подразделением (скажем производством) обычно зависит от того, какие средства будут затрачены другими подразделениями (скажем отделом сбыта). В теории распределения рассматриваются преимущественно задачи с независимыми затратами и доходами. Это объясняется не тем, что такие задачи более важны, а лишь тем, что для них значительно легче строить модели и получать решения.

Если затраты (или доход), определяемые объемом Х_i,j ресурса I, выделенного на выполнение работы J_j, ровны X_i,j,. С_i,j, то имеем линейную распределительную задачу. Распределительные задачи с независимыми линейными функциями затрат (или дохода) стали объектом, наиболее интенсивных исследований, в виду того что для их решения были развитые эффективные, итеративные методы линейного программирования. Однако имеются также методы решения некоторых нелинейных распределительных задач, в том числе методы основанные на линейной аппроксимации.

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

Основные метода решения распределительных задач, в частности линейного программирования, построены на допущении, что объёмы, имеющихся в наличии ресурсов (B_i), требуемые объёмы (а_i) и затраты (С_i,j) точно известны.

Если общий объём наличных ресурсов Sb_i (i=l...m) равен общей потребности в них Sa_i(j=l...n), то имеет место сбалансированная (закрытая) распределительная задача: Если же Sа_j¹Sb_i, то задача называется несбалансированной (открытой). Если ресурсы можно разделить между работами, то некоторые работы можно выполнять с помощью различных комбинаций ресурсов. Если работы и ресурсы измеряются в единицах одной и той же шкалы, то такие задачи обычно называют транспортными или задачами разложения. Если же работы и ресурсы выражаются в различных единицах измерениях, то задача называется общей распределительной задачей. Таким образом транспортная задача является частным случаем общей распределительной задачи.

2.Транспортная задача как частный случай общей распределительной задачи.

Транспортная задача ставится следующим образом: имеется m пунктов отправления А₁, А₂, ..., A_m. B которых сосредоточены запасы каких-то однородных грузов в количестве соответственно a₁, а₂, ..., а_m единиц. Имеется n пунктов назначения B₁, В₂, …, В_n подавшие заявки соответственно на b₁, b₂, ..., b_n единиц груза. Известны стоимости С_i,j перевозки единицы груза от каждого пункта отправления A_i до каждого пункта назначения B_j. Все числа С_i,j, образующие прямоугольную таблицу заданы. Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна.

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

3. Решение транспортной задачи методом потенциалов.

Для того, чтобы некоторый допустимый план X={x_i,j}m.n транспортной задачи был оптимальным необходимо и достаточно, чтобы ему соответствовала система из m+n чисел U1, U2, ..., Um; V1, V2, ..., Vn, удовлетворяющих условиям Vj-Ui<=Cij (i=1,m; j=1,n) (1), а для всех Xij>0 имело бы место строгое равенство Vj-Ui=Cij (2).

Числа Ui, Vi называются потенциалами соответственно пунктов отправления, а условия (1) (2) называются условиями потенциальности системы.

Теорема.

Для оптимальности плана транспортной задачи необходимо и достаточно, чтобы он был потенциальным. Алгоритм метода потенциалов состоит из предварительного и повторяющегося общего шага.

Предварительный план состоит из следующих операций:

1.           составление первоначального ациклического плана перевозок;

2.           построение для полученного плана системы m+n чисел U1 ,U2, ..., Um; V1, V2, …, Vn таких, чтобы выполнялись условия Vj-Ui=Cij для всех базисных клеток;

3.           проверка построенной системы на потенциальность.

Если система нe потенциальна, т.е. план Х не оптимален, переходим к общему шагу.

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

1)           улучшение плана, т.е. замена плана Х новым планом X' со стоимостью перевозок, не превышающей стоимость плана X;

2)           построение для X' новой системы потенциалов U'i, V'j путем перестроения старой;

3)           проверка системы U'i, V'j на потенциальность.

Предложенный алгоритм сходится за конечное число шагов.

4. Транспортная задача с неправильным балансом.

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

Sa_i=Sb_j (где i=1, .., m; j=1, ...,n) (3)

Это классическая транспортная задача, иначе называемая, транспортной задачей с правильным балансом. Встречаются такие варианты транспортной задачи, где условие (3) нарушено. В этих случаях говорят о транспортной задаче с неправильным балансом.

Баланс транспортной задачи может нарушаться в 2-ух направлениях: