Алгоритм решения транспортной задачи методом потенциалов

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

Основной задачей линейного программирования, решаемой методом потенциалов, является транспортная задача. Следует заметить, что название транспортных задач обусловлено тем, что вышеперечисленные методы вначале были разработаны к организации перевозки грузов. В настоящее время этим методом решаются многие другие задачи, не связанные с грузоперевозками. Например, распределение машинно-тракторного парка по видам работ, распределение посевных площадей сельскохозяйственных культур по наилучшим предшественникам или по группам почв и т.д.

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

· i - номер пункта отправления груза;

· j - номер пункта потребления груза;

· m - количество пунктов отправления;

· n - количество пунктов потребления груза;

· A_i - наименование i-го пункта отправления груза;

· a_i - наличие груза в i-м пункте отправления;

· B_j - наименование j-го пункта потребления груза;

· b_j - потребность j-го пункта в грузе;

· X_j - количество перевозимого груза из i-го пункта отправления в j-й пункт назначения;

· C_ij - оценка переменных в целевой функции;

· Z_min - значение целевой функции.

Приняв условия обозначения, постановку транспортной задачи в общем виде можно сформулировать следующим образом. Имеется m пунктов отправления А₁, А₂,…А_m, на которых сосредоточено определенное количество груза а₁, а₂,…а_m, и имеется n пунктов потребления груза В₁, В₂,…В_n с потребностью в этом грузе b₁, b₂…b_n. Требуется определить такие маршруты перевозок, которые бы при всех неотрицательных переменных х_ij обеспечивали минимальное значение целевой функции Z_min.

В транспортных задачах различают ограничения (условия) по наличию груза в пунктах отправления и ограничение по потребностям в данном грузе пунктов назначения (потребления).

Математически ограничения по наличию груза в пунктах отправления запишутся следующим образом:

X₁₁+X₁₂+ …+X_1n =a₁
X₂₁+X₂₂+ …+X_2n =a_{2
……………………………………}
X_m1+X_m2+ …+X_mn=a_m

Если в данной группе ограничений трансформировать столбцы в строки, то получим ограничения по удовлетворению потребности пунктов потребления в грузе.

X₁₁+X₂₁+ …+X_m1 =b₁
X₁₂+X₂₂+ …+X_m2 =b_{2
……………………………………}
X_1n+X_2n+ …+ _mn = b_n

Целевая функция будет представлена выражением

Z_min = C₁₁ X₁₁ + C₁₂ X₁₂ + … + C_1n X_1n +C₂₁ X₂₁+C₂₂X₂₂ + … + C_mn X_mn.

Структурная форма записи транспортной задачи выглядит следующим образом:

Найти минимум функции

при условиях:

1) наличия груза в пунктах отправления
( i = 1,2,…,m);

2) потребности в грузе в пунктах назначения
(j = 1,2,…,n);

3) неотрицательности переменных

.

В транспортных задачах встречаются модели открытого и закрытого типа. Если общая сумма груза во всех пунктах отправления равна потребности в нем всех пунктов назначения, то такая модель называется закрытой. Закрытая модель транспортной задачи в структурной форме имеет следующий вид:

.

Если же такого равенства не наблюдается, то модель называется открытой. Открытая модель задачи описывается формулой

.

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

Алгоритм решения транспортных задач методом потенциалов разберем на конкретном примере.

Условие задачи:

В хозяйстве грубые корма заготовлены на трех участках в следующем объеме: на первом участке – 500 т (А₁), на втором – 850 т (А₂), на третьем – 600 т (А₃). Заготовленные корма предстоит развезти по четырем фермам. Первой ферме требуется 400 т (В₁), второй- 550 т (В₂), третьей- 700 т (В₃), четвертой – 300 т (В₄). Расстояние от участков до ферм приведено в таблице 8. Себестоимость 1 тонно-километра в среднем по хозяйству составляет 10 рублей. Требуется определить такие маршруты перевозок грубых кормов, чтобы общие затраты на их перевозку с участков до ферм были бы минимальными.

Таблица 8. Расстояние от мест складирования корма до ферм, км

Так как в задаче себестоимость тонно-километра приведена как средняя величина, то можно найти минимальное значение грузооборота, а потом полученное количество тонно-километров умножить на его среднюю себестоимость. Таким образом будет найдена минимальная сумма затрат на перевозку грубых кормов с участков на фермы.

Запишем данную задачу в виде системы уравнений, приняв за неизвестные возможное количество перевозимого груза с i-го участка на j-ую ферму:

Ограничения по количеству заготовленного грубого корма на участках:

X₁₁+X₁₂+X₁₃+X₁₄=500

X₂₁+X₂₂+X₂₃+X₂₄=850

X₃₁+X₃₂+X₃₃+X₃₄=600

Всего заготовлено грубых кормов 1950 т.

Ограничения по потребности ферм в грубых кормах:

X₁₁+X₂₁+X₃₁=400

X₁₂+X₂₂+X₃₂=550

X₁₃+X₂₃+X₃₃=700

X₁₄+X₂₄+X₃₄=300

Всего потребность ферм в грубых кормах равна 1950 т.

Целевая функция принимает следующий вид:

Z_min=3X₁₁+4X₁₂+2X₁₃₊9X₁₄+8X₂₁+5X₂₂+7X₂₃+8X₂₄+5X₃₁+6X₃₂+4X₃₃+4X₃₄

Так как сумма количества заготавливаемых грубых кормов на всех участках и потребность ферм в этих кормах равны, то задача считается закрытой.

Решение транспортных задач методом потенциалов осуществляется в таблицах следующего вида.

Таблица 9. Форма таблицы для решения транспортной задачи

Строка V_j и столбец U_i в данной таблице предназначены для записи значений потенциалов занятых клеток по столбцу и по строке. В правом верхнем углу каждой клетки записывается оценка целевой функции.

Существует несколько способов построения первого опорного плана: способ северо-западного угла, способ предпочтение наименьшей (при решении на минимум целевой функции) или наибольшей (при решении на максимум целевой функции) оценки по строке; способ двойного предпочтения и т.д. Наиболее часто применяется способ северо-западного угла. Он предполагает начало построения первого опорного плана с заполнения левой верхней клетки таблицы без учета величины оценки. В данной задаче количество грубых кормов на первом участке составляет 500 т, а первой ферме требуется 400 т (таблица 10). Следовательно, потребность первой фермы будет удовлетворена за счет кормов, имеющихся на первом участке.

Таблица 10. Первый опорный план (оценки L)

Оставшиеся 100 т корма будут перевезены на вторую ферму. Итак, наличие кормов на первом участке распределено полностью. Приступаем к распределению кормов, заготовленных на втором участке, где имеется 850 т. Второй ферме для полного удовлетворения в кормах недостает 450 т. Этот недостаток покрывается за счет кормов второго участка. Оставшиеся 400 т кормов на втором участке отдаем третей ферме, так как ее потребность больше остатка, но третьей ферме до полного покрытия потребности недостает 300 т кормов. Недостаток потребности третьей фермы покрывается за счет кормов, заготовленных на третьем участке. Оставшиеся 300 т кормов на третьем участке будут переданы на четвертую ферму. Итак, все заготовленные корма на участках распределены в соответствии с их потребностями.

Значение целевой функции в первом опорном плане равно 9050 т/км.

Z_min=3·400+4·100+5·450+7·400+4·300+4·300=9050 т/км.

В построенном опорном плане количество занятых клеток должно быть не менее чем m+n-1, где m - количество строк, n - количество столбцов. Если количество занятых клеток меньше, чем сумма строк и столбцов без единицы, то план является вырожденным, т.е. не имеющим решения. Для устранения вырожденности одну из свободных клеток принимают за условно занятую. В условно занятую клетку записывают ноль грузоперевозок и считают эту клетку занятой.

Полученный опорный план проверяют на оптимальность. При решении задачи на минимум план будет оптимальным тогда, когда все характеристики свободных клеток, рассчитанные по формуле L_ij=C_ij ‑ (V_i+U_i), будут положительными или равными нулю. В данной формуле L_ij - характеристика свободной клетки, которая указывает, как изменяется значение целевой функции при перемещении одной единицы груза в данную свободную клетку. Положительная характеристика указывает на увеличение значения целевой функции, отрицательная − на ее уменьшение, а наличие нулевых характеристик свидетельствует о наличии маршрутов перевозки грузов, при которых значение целевой функции остается неизменной. C_ij - оценка занятой клетки, V_j - потенциал занятой клетки по j-му столбцу, U_i - потенциал занятой клетки по i-ой строке. Потенциалы занятых клеток рассчитываются по формуле C_ij=V_j+U_i.

Рассчитаем потенциалы занятых клеток для первого опорного плана по данной формуле, приняв значение U₁=0:

C₁₁=V₁+U₁; 3=V₁+0; V₁= 3

C₁₂=V₂+U₁; 4=V₂+0; V₂= 4

C₂₂=V₂+U₂; 5=4+U₂; U₂= 1

C₂₃=V₃+U₂; 7=V₃+1; V₃= 6

C₃₃=V₃+U₃; 4=6+U₃; U₃=-2

C₃₄=V₄+U₃; 4=V₄+(-2); V₄= 6

Значения рассчитанных потенциалов записывают в соответствующие строку и столбец таблицы.

Подставляя найденные параметры в формулу L_ij=C_ij-(V_i+U_i), рассчитаем характеристики свободных клеток для первого опорного плана:

L₁₃=C₁₃-(V₃+U₁)=2-(6+0)=-4 L₂₄= C₂₄-(V₄+U₂)=8-(6+1)= 1

L₁₄= C₁₄-(V₄+U₁)=9-(6+0)= 3 L₃₁= C₃₁-(V₄+U₃)=5-(3-2) = 4

L₂₁= C₂₁-(V₁+U₂)=8-(3+1)= 4 L₃₂= C₃₂-(V₂+U₃)=6-(4-2) = 4

Полученный опорный план не является оптимальным, так как данная задача решается на минимум и одна из характеристик имеет отрицательное значение (L₁₃=-4). Следовательно, полученный план необходимо улучшать. Улучшение плана осуществляется путем построения замкнутого контура и перемещения объема грузоперевозок по его вершинам.

Чтобы начать построение контура, просматривают значения характеристик свободных клеток и среди них выбирают наибольшую по модулю, при решении на минимум − среди отрицательных, а при решении на максимум − среди положительных характеристик. В свободной клетке, соответствующей выбранной характеристике, ставят знак (+) и из нее начинают построение прямоугольного замкнутого контура. Ведут прямую линию до занятой клетки. В занятой клетке ее поворачивают на 90^о и ведут прямую линию к следующей занятой клетке. В ней также ее поворачивают на 90^о с тем расчетом, чтобы вернуться к свободной клетке, из которой начинали построение прямоугольного контура. Проходить через занятую клетку, не поворачивая в ней линию на 90⁰, можно только в том случае, если не представляется возможности вернуться к свободной клетке, из которой начиналось построение контура.

К построению контура предъявляются следующие требования:

· все вершины контура (кроме одной, из которой контур начинал строиться) должны лежать в занятых клетках);

· все углы контура должны быть прямыми;

· количество вершин контура должно быть четным.

После построения замкнутого контура его вершины, чередуя, обозначают знаками (+) и (-). Среди отрицательных вершин контура находят наименьшее количество груза, и эту величину перемещают по контуру, прибавляя его к объемам грузоперевозок, стоящим при вершинах со знаком (+), и вычитают из чисел при отрицательных вершинах контура. В первом опорном плане наименьшее количество груза при отрицательных вершинах равно 100 т (с₁₂). Следовательно, это число перемещаем по вершинам контура. Таким образом, получаем второй опорный план. Числа, которые не принадлежат вершинам контура, в новый опорный план переписываются без изменения.

Грузооборот во втором опорном плане по сравнению с первым уменьшился на 400 т/км. Правильность расчета значения целевой функции можно проверить, если вычесть из значения целевой функции предыдущего плана произведение характеристики свободной клетки, из которой начинали строить прямоугольный контур (L₁₃=-4) на величину перемещаемого груза (X₁₃=100), при этом получим значение целевой функции второго опорного плана: 9050-(4×100)=8650.

Таблица 11. Второй опорный план

Значение целевой функции во втором опорном плане равно:

Z_min=3·400+2·100+5·550+7·300+4·300+4·300=8650 т/км.

Исследуем новый опорный план на оптимальность. Потенциалы занятых клеток в новом опорном плане примут значения:

C₁₁=V₁+U₁ 3=V₁+0 V₁=3 C₂₂=V₂+U₂ 5=V₂+5 V₂=0

C₁₃=V₃+U₁ 2=V₃+0 V₃=2 C₃₃=V₃+U₃ 4=2+U₃ U₃=2

C₂₃=V₃+U₂ 7=2+U₂ U₂=5 C₃₄=V₄+U₃ 4=V₄+2 V₄=2

Рассчитаем характеристики свободных клеток:

L₁₂=C₁₂ ‑ (V₂+U₁)=4‑(0+0)=4 L₂₄=C₂₄ ‑ (V₄+U₂)=8‑(2+5)=1

L₁₄=C₁₄ ‑ (V₄+U₁)=9‑(2+0)=7 L₃₁=C₃₁ ‑ (V₁+U₃)=5‑(3+2)=0

L₂₁=C₂₁ ‑ (V₁+U₂)=8‑(3+5)=0 L₃₂=C₃₂ ‑ (V₂+U₃)=6‑(0+2)=4

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

Если план не оптимальный, то вновь строят замкнутый контур, находят наименьшее число среди отрицательных вершин контура и перемещают это число по контуру. Таким образом, получают новый опорный план. Улучшение опорного плана ведут до тех пор, пока не получат оптимальный план.

В соответствии с оптимальным планом грубые корма с первого участка будут перевезены 400 т на первую ферму и 100 т на третью ферму, со второго участка 550 т будут перевезены на вторую ферму и 300 т на третью. С третьего участка корма в равных долях будут распределены между третьей и четвертой фермами.

Наличие в оптимальном плане нулевых характеристик свободных клеток (L₂₁=0; L₃₁=0) свидетельствует о наличии других маршрутов перевозки грубых кормов с участков на фермы, при которых значение целевой функции остается неизменной. В данном случае возможны перевозки кормов со второго и третьего участков на первую ферму. Если предположить возможную перевозку грубого корма с третьего участка на первую ферму, то получим новый опорный план

Таблица 12. Третий опорный план

Потенциалы занятых клеток в новом опорном плане примут значения:

C₁₁=V₁+U₁ 3=V₁+0 V₁=3 C₂₂=V₂+U₂ 5=V₂+5 V₂=0

C₁₃=V₃+U₁ 2=V₃+0 V₃=2 C₃₁=V₁+U₃ 5=3+U₃ U₃=2

C₂₃=V₃+U₂ 7=2+U₂ U₂=5 C₃₄=V₄+U₃ 4=V₄+2 V₄=2

Характеристики свободных клеток L_ij в третьем опорном плане примут следующие значения:

L₁₂ = C₁₂ ‑ (V₂+U₁)=4-(0+0)=4 L₂₄ = C₂₄ ‑ (V₄+U₂)=8-(2+5)=1

L₁₄ = C₁₄ ‑ (V₄+U₁)=9-(2+0)=7 L₃₂ = C₃₂ ‑ (V₂+U₃)=6-(0+2)=4

L₂₁ = C₂₁ ‑ (V₁+U₂)=8-(3+5)=0 L₃₃ = C₃₃ ‑ (V₃+U₃)=4-(2+2)=0

Все характеристики свободных клеток в третьем опорном плане положительные, следовательно, план является оптимальным. Значение целевой функции данного опорного плана равно 8650 т/км

Z_min = 3·100+2·400+5·550+7·300+5·300+4·300=8650 т/км.

Оптимальный план третьего опорного плана альтернативен оптимальному плану второго опорного плана.