Нахождение оптимального плана методом потенциалов

На каждом шаге этого метода выполняются следующие действия:

1. вычисляются потенциалы, согласованные с построенным опорным планом;

2. производится проверка оптимальности текущего опорного плана;

3. если план оказывается неоптимальным, то строится новый опорный план с меньшим или, по крайней мере, таким же значением целевой функции.

Шаг 1. Ниже описывается первый шаг метода потенциалов.

1. Вычисление потенциалов

Вычислим потенциалы поставщиков U_i и потребителей V_j, согласованные с найденным опорным планом. Для этого используем условие (3.7) критерия оптимальности плана транспортной задачи для задачи (3.8) – (3.18). Потенциалы поставщиков U_i и потребителей V_j находятся путем решения системы уравнений:

V_j – U_i = C_ij, (3.19)

которые составляются для всех занятых клеток:

Занятая клетка	Уравнение
(1, 1)	V1 – U1 = 15
(1, 2)	V2 – U1 = 16
(2, 2)	V2 – U2 = 16
(2, 3)	V3 – U2 = 13
(3, 3)	V3 – U3 = 16
(3, 4)	V4 – U3 = 16
(4, 4)	V4 – U4 = 0
(4, 5)	V5 – U4 = 0

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

Например, положим U₁ = 10, а затем последовательной подстановкой вычислим значения остальных потенциалов для опорного плана из таблицы 3.2.

V₁ = U₁ + C₁₁ = 10 + 15 = 25,

V₂ = U₁ + C₁₂ = 10 + 16 = 26,

U₂ = V₂ – C₂₂ = 26 – 16 = 10,

V₃ = U₂ + C₃₃ = 10 + 13 = 23,

U₃ = V₃ – C₃₃ = 23 – 16 = 7,

V₄ = U₃ + C₃₄ = 7 + 16 = 23,

U₄ = V₄ – C₄₄ = 23 – 0 = 23,

V₅ = U₄ + C₄₅ = 23 + 0 = 23.

Итак, найдены потенциалы, согласованные с начальным опорным планом Х₀. Значения потенциалов V_j и U_i представлены соответственно в нижней строке и последнем столбце таблицы 3.3.

Таблица 3.3

bj ai	68	68	90	31	87	Ui
118	15 68	16 50	14	11	17	U1=10
18	15	16 18 –	13 0 +	11	14	U2=10
98	21	22	16 90 –	16 8 +	23	U3=7
110	0	0 +	0	0 23 –	0 87	U4=23
Vj	V1=25	V2=26	V3=23	V4=23	V5=23	S0 = 3891

Расчет потенциалов можно проводить, не решая систему уравнений (3.19), а непосредственно в таблице. Так, если известен потенциал пункта отправления U_i, то для вычисления потенциала пункта назначения V_j, соответствующего занятой клетке (i, j), следует использовать уравнение

V_j = U_i + C_ij.

Таким способом можно определить потенциалы всех пунктов назначения, которым соответствуют занятые клетки в i-й строке. Например, если известно, что U₁ = 10, то можно найти значения потенциалов первого и второго пунктов назначения, которым соответствуют занятые клетки в первой строке:

V₁ = U₁ + C₁₁ = 10 + 15 = 25, V₂ = U₁ + C₁₂ = 10 + 16 = 26.

Если известен потенциал пункта назначения V_j, то для вычисления потенциала пункта отправления U_i, соответствующего занятой клетке (i, j), следует использовать уравнение

U_i = V_j – C_ij.

Таким способом можно определить потенциалы всех пунктов назначения, которым соответствуют занятые клетки в j-м столбце. Например, если известно, что V₂ = 26, то можно найти значение потенциала второго пункта потребления, которому соответствует занятая клетка (2, 2):

U₂ = V₂ – C₂₂ = 26 – 16 = 10.

2. Проверка оптимальности опорного плана

Условие (3.7) критерия оптимальности для занятых клеток плана выполнено по построению. Поэтому для проверки оптимальности плана нужно выяснить, выполняется ли условие (3.6). Это равносильно проверке условий V_j – U_i ≤ С_ij для всех свободных клеток.

Для каждой свободной клетки (i, j) определим число ∆_ij = V_j – U_i – С_ij. Тогда ясно, что если ∆_ij ≤ 0 для всех свободных клеток, то текущий опорный план является оптимальным. В противном случае этот план не оптимален.

По своему экономическому смыслу величина ∆_ij характеризует то изменение в затратах на перевозки, которое произойдет, если будет осуществлена перевозка единицы груза из i-го пункта отправления в j-й пункт назначения. Если ∆_ij > 0, то единичная поставка приведет к экономии транспортных затрат на ∆_ij; если же ∆_ij < 0, то — к их увеличению на ∆_ij. Поэтому, если найдется ∆_ij > 0, то это означает, что существует свободное направление перевозки груза, экономящее затраты, т.е. текущий план перевозок не оптимален. Если же все ∆_ij ≤ 0, то это означает, что нет свободных направлений перевозок, экономящих затраты, т.е. план перевозок оптимален.

Вычислим ∆_ij для всех свободных клеток:

∆₂₁ = V₁ – U₂ – С₂₁ = 25 – 10 – 15 = 0,

∆₃₁ = V₁ – U₃ – С₃₁ = 25 – 7 – 21 = -3,

∆₄₁ = V₁ – U₄ – С₄₁ = 25 – 23 – 0 = +2,

∆₃₂ = V₂ – U₃ – С₃₂ = 26 – 7 – 22 =-3,

∆₄₂ = V₂ – U₄ – С₄₂ = 26 – 23 – 0 = +3 ,

∆₁₃ = V₃ – U₁ – С₁₃ = 23 – 10 – 14 = -1,

∆₄₃ = V₃ – U₄ – С₄₃ = 23 – 23 – 0 = 0,

∆₁₄ = V₄ – U₁ – С₁₄ = 23 – 10 – 11 = +2,

∆₂₄ = V₄ – U₂ – С₂₄ = 23 – 10 – 11 = +2,

∆₁₅ = V₅ – U₁ – С₁₅ = 23 – 10 – 17 = -4,

∆₂₅ = V₅ – U₂ – С₂₅ = 23 – 10 – 14 = -1,

∆₃₅ = V₅ – U₃ – С₃₅ = 23 – 7 – 23 = -1.

Анализ значений ∆_ij показывает, что данный опорный план не оптимален, т.к. среди ∆_ij имеются положительные значения. План может быть улучшен за счет перераспределения перевозок.

3. Построение нового плана

Из всех положительных значений ∆_ij выбираем максимальное. В нашем случае оно соответствует свободной клетке (4, 2). В новом плане эта клетка будет занятой (введена в базис), т.е. будет осуществлена перевозка из пункта i в пункт j. Так как число занятых клеток меняться не должно, то одна из ранее занятых клеток освобождается. Освобождаемая (выводимая из базиса) клетка и новые объемы перевозок в занятых клетках определяются с помощью цикла.

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

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

В построенном цикле, начиная с выбранной клетки, помечаются вершины: нечетные («плюсовые») — знаком "+", а четные («минусовые») — знаком "–". Знаком "+" помечаются те клетки, в которых объемы перевозок должны увеличиться. Такой, в частности, является вводимая в базис клетка. Знаком "–" помечаются клетки, в которых объемы перевозок должны уменьшиться, чтобы сохранился баланс перевозок.

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

Значения перевозок в помеченных клетках пересчитываются по такому правилу: к объемам перевозок, содержащихся в плюсовых клетках, добавляется величина перевозки θ, а из объемов перевозок, содержащихся в минусовых клетках, вычитается величина перевозки θ. Остальные занятые клетки не изменяются.

Если в результате этой операции только одна из минусовых клеток содержит нулевое значение, то она освобождается (выводится из базиса). Если же таких клеток несколько, то освобождается та из них, которая имеет максимальный тариф перевозок, а остальные остаются занятыми. В этом случае новый опорный план будет вырожденным. Значение целевой функции на новом плане уменьшается по сравнению со старым значением на величину, равную θ·∆_ij.

В нашей таблице цикл начинается в свободной клетке (4, 2) и проходит по занятым клеткам (2, 2), (2, 3), (3, 3), (3, 4), (4, 4). Покажем этот цикл отдельно, вне таблицы:

–кл.(2,2) кл.(2,3) +

кл.(3,3) –

кл.(3,4) +

+ кл.(4,2) кл.(4,4) –

В этом цикле θ = min{x₂₂, x₃₃, x₄₄} = min{18, 90, 23} = 18. Клетка (2, 2), поставка в которой соответствует θ, становится свободной. Таким образом, получается новый опорный план Х₁, представленный в таблице 3.4. Транспортные затраты S₁ на этом плане рассчитываются по формуле:

S₁ = S₀ – ∆₄₂ ×θ = 3676 – 3 × 18 = 3622.

68 50 – – –

X₁ = – – 18 – – , S₁ = 3622.

– – 72 26 –

– 18 – 5 87

Шаг 2. Продолжим решение транспортной задачи методом потенциалов. Новый опорный план X₁ проверяется на оптимальность. Для него снова рассчитываются потенциалы поставщиков U_i и потенциалы потребителей V_j (см. табл. 3.4). Пусть опять исходное значение U₁ = 10.

Таблица 3.4

bj ai	68	68	90	31	87	Ui
118	15 68	16 50 –	14	11 +	17	10
18	15	16	13 18	11	14	13
98	21	22	16 72	16 26	23	10
110	0	0 18 +	0	0 5 –	0 87	26
Vj	25	26	26	26	26	S1 = 3622

Определяется клетка, для которой ∆_ij имеет максимальное положительное значение. Это клетка (1, 4) и ∆₁₄ = 5. Затем строится цикл, включающий клетки (1, 4), (4, 4), (4, 2), (1, 2). В его минусовых клетках, выбирается значение θ = min{x₄₄, x₁₂} = min{5, 50} = 5.

Таблица 3.5

bj ai	68	68	90	31	87	Ui
118	15 68	16 45 –	14	11 5 +	17	10
18	15	16	13 18 –	11	14 +	8
98	21	22	16 72 +	16 26 –	23	5
110	0	0 23 +	0	0	0 87 –	26
Vj	25	26	21	21	26	S2 = 3597

Производится перераспределение поставок по циклу: клетка (1, 4) становится занятой поставкой в 5 единиц, а клетка (4, 4) становится свободной. К поставкам в плюсовых клетках прибавляется величина θ, равная 5, а от поставок в минусовых клетках отнимается эта величина. В результате в таблице 3.5 получен новый опорный план X₂:

68 45 – 5 –

X₂ = – – 18 – – , S₂ = S₁ – ∆₁₄×θ = 3622 – 5×5 = 3597.

– – 72 26 87

– 23 – –

Шаг 3. Проведем анализ нового опорного плана X₂. Для нового опорного плана рассчитываем потенциалы U_i и V_j. Максимальные положительные значения ∆_ij = 4 соответствуют двум клеткам: (3, 2) и (2, 5). Выбираем клетку с минимальным значением тарифа, т.е. клетку (2,5). К ней составляется цикл, по которому происходит пересчет поставок. Он включает клетки (2,5), (4, 5), (4, 2), (1, 2), (1, 4), (3, 4), (3, 3) и (2, 3). Выберем θ = min{x₄₅, x₁₂, x₃₄, x₂₃} = min{87, 45, 26, 18} = 18.

В результате корректировки получен новый опорный план Х₃ (см. табл. 3.6).

68 27 – 23 –

X₃ = – – – – 18 , S₃ = S₂ – ∆₂₅×θ = 3597 – 4×18 = 3525.

– – 90 8 –

– 41 – – 69

Таблица 3.6

bj ai	68	68	90	31	87	Ui
118	15 68	16 27	14	11 23	17	10
18	15	16	13	11	14 18	12
98	21	22	16 90	16 8	23	5
110	0	0 41	0	0	0 69	26
Vj	25	26	21	21	26	S3 = 3525

Шаг 4. Проведем анализ нового опорного плана X3. Для этого плана рассчитаем потенциалы Ui и Vj и значения ∆ij. Все значения ∆ij<0, следовательно, в таблице 3.6 получен оптимальный план.

Ответ:

68 27 – 23 –

X ^* = – – – – 18 , S ^* = 3525.

– – 90 8 –

– 41 – – 69

Экономическая интерпретация оптимального плана поставок продукции

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

1. от первого поставщика отправить три поставки: первому потребителю поставку в размере 68 единиц, второму – 27 единиц и четвертому – 23 единицы;

2. от второго поставщика отправить пятому потребителю поставку в размере 18 единиц;

3. от третьего поставщика направить третьему потребителю 90 единиц и четвертому – 8 единиц.

Транспортные затраты S^* на этом плане равны 3525 денежных единиц.

Замечание.Поставок от четвертого поставщика фактически не существует, поскольку четвертый поставщик является фиктивным. Однако их наличие означает, что второй потребитель недополучит 41 единицу, а спрос пятого потребителя не будет удовлетворен на 69 единиц.