Решение задач линейного программирования транспортного типа: Методические указания к выполнению индивидуальных домашних заданий, страница 5

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

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

∆₁₅ = V₅ – U₁ – С₁₅ = 23 – 10 – 13 = 0,

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

∆₃₅ = V₅ – U₃ – С₃₅ = 23 –  7 – 17 = -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), поставка в которой соответствует θ, становится свободной. Таким образом, получается новый опорный план Х₁, представленный в таблице 1.3. Транспортные затраты S₁ на этом плане рассчитываются по формуле:

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

                                             68   50    –    –    –                   

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

                                         –     –    72  26   –

                                         –    18    –    5   87      

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

Таблица 1.3

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.

Таблица 1.4

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