6.3. Оценка опорного плана транспортной задачи на оптимальность

и нахождение очередного плана

Для нахождения оптимального плана применяется тот же общий принцип, что и при решении производственной задачи: первоначально находится опорный план, а затем методом последовательного его улучшения получают оптимальный план. Оценку и улучшение опорного плана проводят, пользуясь различными методами. Мы рассмотрим наиболее простой и часто применяемый – метод потенциалов. Но прежде чем рассмотреть его более подробно, заметим следующее. Если анализируемый опорный план вырожденный, то его следует превратить в невырожденный, включив в базис любой свободный маршрут (или несколько), назначив объем транспортируемого по нему груза в пренебрежимо малом объеме. В дальнейшем этот маршрут также должен участвовать во всех аналитических процедурах, но в матрицу оптимального плана он не включается.

Метод потенциалов. Первоначально ознакомимся со следующей теоремой.

Т е о р е м а. Если для некоторого опорного плана , (i=1…m; j=1…n) транспортной задачи для каждого базисного маршрута существуют такие числа α₁, α₂, … , α_m ; β₁, β₂, …, β_n, при которых

при х_ij >0

и при

для всех i=1…m и j=1…n, тогда - оптимальный план задачи.

О п р е д е л е н и е . Числа α_i и β_j называются потенциалами соответственно пунктов отправления и пунктов потребления.

Сформулированная теорема позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем.

Пусть одним из ранее рассмотренных методов найден опорный план. Следует предположение, что полученный план оптимален. Тогда для каждого из закрытых маршрутов можно определить потенциалы α_i и β_j (i=1…m , j=1…n). Эти числа находят, решая систему уравнений (полагаем, что х_ij >0):

, (24)

где с_ij – тариф соответствующего маршрута.

Так как количество определенных (базисных) маршрутов (n+m-1), а число неизвестных α,β равно (n+m), т.е. на единицу больше, то одно из неизвестных (обычно α₁ или β₁ ) приравнивают нулю, тогда легко считаются остальные по заполненным маршрутам опорного плана. После нахождения α_i и β_j для всех свободных маршрутов определяют числа

. (25)

Если среди этих чисел нет положительных (хотя бы одного), то такой план считается оптимальным. В противном случае предположение относительно оптимальности анализируемого плана недействительно и его можно улучшить. Маршруты-претенденты на включение в базис будут иметь ∆_ij >0. Но перевести в базис можно только один маршрут, для которого ∆_ij>0 и max.

Заполнение такого маршрута неизбежно повлечет за собой изменение объемов поставок по другим маршрутам (естественно, так как любой опорный план всегда сбалансирован). Эта процедура выполняется на базе графического алгоритма, называемого циклом.

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

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

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

1. Считая первым тот маршрут, который вносится в базис, присвоить ему знак «+» и далее, перемещаясь по циклу, следующему маршруту присваивается знак «-», далее опять знак «+» и так далее, т.е. всем нечетным маршрутам присваивается знак «+», а нечетным – знак «-» (только по концам линий цикла).

2. Среди маршрутов со знаком «-» выбирают маршрут с минимальным объемом перевозки.

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

4. Проверяют новый опорный план на оптимальность.

На рис.10 представлены некоторые варианты схем циклов при формировании очередного опорного плана транспортной задачи.

Рис. 10. Варианты схем циклов

З а д а ч а 15.В качестве примера проанализируем опорный план выше рассмотренной задачи, полученный методом северо-западного угла. Для этого составим таблицу 20, где взамен обозначений поставщика А_i и потребителя B_j вписаны обозначения потенциалов α_i и β_j.

Таблица 20

Расчет потенциалов

	β1 = 2	β2 = 3	β3 = 4	β4 = 7	β5 = 2
α1 = 0	2 60	3 70	4 10	2	4
α2 = 3	8	4	1 110	4 70	1
α3 = 0	9	7	3	7 60	2 100

Первоначально рассчитаем потенциалы, воспользовавшись заполненными маршрутами. Составим систему из семи уравнений типа (24):

; ; ;

; ; .

;

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

; ; ; ; ;

; ; .

Полученные значения потенциалов внесем в табл.20. Теперь для каждого свободного маршрута рассчитаем значения ∆_ij , согласно уравнения (25) и впишем их в таблицу (в квадратных скобках). Видим, что ∆_ij>0 по двум маршрутам: А₁В₄ (∆_ij=+5) и А₃В₃ (∆_ij=+1). По всем остальным маршрутам этот параметр отрицательный. Очевидно, что маршрут А₁В₄ должен быть переведен из свободных в базисные.

Строим цикл. Он пройдет через следующие узловые маршруты:

А₁В₄→А₂В₄→А₂В₃→А₁В₃→А₁В₄ .

Это единственный вариант построения ломаной, у которой в вершинах находятся заполненные (базисные) маршруты. Соответственно маршруты приобретают знаки:

А₁В₄→(+); А₂В₄→(-); А₂В₃→(+); А₁В₃→(-) .

В цикле надо перемещать минимальное число, соответствующее транспортируемому грузу по маршруту со знаком «минус». Таковым будет число 10 по маршруту А₁В₃. Получим новый опорный план, представленный в табл.21.

Таблица 21

Первый улучшенный план

	β1 = 2	β2 = 3	β3 = -1	β4 = 2	β5 = -3
α1 = 0	2 60	3 70	4	2 10	4
α2 = -2	8	4	1 120	4 60	1
α3 = -5	9	7	3	7 60	2 100

Повторим относительно и этого плана описанные выше процедуры, получим значения потенциалов по всем маршрутам и видим, что и этот план неоптимален, так как имеет три маршрута с положительными потенциалами, равными (+1). С целью его улучшения введем в базис маршрут А₃В₃ (у него минимальная тарифная ставка) и строим цикл:

А₃В₃→А₃В₄→А₂В₄→А₂В₃→А₃В₃.

С учетом знаков по маршрутам объем перемещаемого по узловым точкам цикла груза в объеме 60 ед получаем очередной опорный план (табл.22).

Этот план также не может быть признан оптимальным, так как есть один маршрут (а именно А₂В₂), имеющий положительный потенциал. Приняв его

Таблица 22

Второй улучшенный план

	β1 = 2	β2 = 3	β3 = -1	β4 = 2	β5 = -2
α1 = 0	2 60	3 70	4	2 10	4
α2 = -2	8	4	1 60	4 120	1
α3 = -4	9	7	3 60	7	2 100

за план, перемещаемый в базис, и построив от него цикл

А₂В₂→А₂В₄→А₁В₄→А₁В₂→А₂В₂

с объемом перемещаемого груза в 70 ед, получим третий улучшенный опорный план, который представлен в табл.23.

Таблица 23

Третий улучшенный план

	β1 = 2	β2 = 2	β3 = -1	β4 = 2	β5 = -2
α1 = 0	2 60	3	4	2 80	4
α2 = -2	8	4 70	1 60	4 50	1
α3 = -4	9	7	3 60	7	2 100

Этот план по всем незаполненным маршрутам имеет только отрицательные потенциалы. Следовательно, он оптимальный:

.

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

; ; ; ,

т.е. по сравнению с первоначальным вариантом оптимальный план улучшен примерно на 15%. Для этого выполнены четыре итерационных цикла оптимизации.