Переход от одного опорного решения к другому

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

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

Доказательство. Опорное решение занимает N=т+п— 1 клеток таблицы, которым соответствуют линейно независимые векторы-условия. Согласно теореме (о взаимосвязи линейной зависимости векторов-условий и возможности образования цикла) ни одна часть занятых клеток не образует цикл. Если же к занятым клеткам присоединить одну свободную, то соответствующие им т + п векторов линейно зависимы, и по той же теореме существует цикл, содержащий эту клетку. Предположим, что таких циклов два (i ₁, j ₁), (i ₁, j ₂), …, (i_к, j ₁) и

(i ₁, j ₁), (i ₂, j ₁), …, (i ₁, j_l). Тогда, объединив клетки обоих циклов без свободной клетки (i ₁ , j ₁), получим последовательность клеток (i ₁, j ₂), …, (i_к, j ₁), (i ₂, j ₁), …, (i ₁, j_l), которые образуют цикл. Это противоречит линейной независимости векторов-условий, образующих базис опорного решения. Следовательно, такой цикл единственный. Ч.т.д.

Означенный цикл

Цикл называется означенным, если его угловые клетки пронумерованы по порядку и нечетным клеткам приписан знак «+», а четным — знак «-» (рис. 6.2).

Рис. 6.2.

Сдвигом по циклу на величину θ называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», на θ и уменьшение объемов пере­возок во всех четных клетках, отмеченных знаком «—», на θ.

Теорема. Если таблица транспортной задачи содержит опорное решение, то при сдвиге по любому циклу, содержащему одну свободную клетку, на величину θ = получится опорное решение.

6.6. Распределительный метод

Один из наиболее простых методов решения транспортных задач ― распределительный метод.

Пусть для транспортной задачи найдено начальное опорное решение Х ₁ и вычислено значение целевой функции на этом решении F (X ₁). По теореме (о существовании и единственности решения) для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Означив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину θ = , можно получить новое опорное решение Х ₂.

Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l, k), приращение целевой функции Δ _lk равно разности двух сумм:

Δ _lk = -,

где — сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком «+»;

— сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком «—».

В клетках, отмеченных знаком «+», величины груза прибавляются, что приводит к увеличению значения целевой функции F (X), а в клетках, отмеченных знаком «—», величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

Если разность сумм для свободной клетки (l, k) меньше нуля, т.е. Δ _lk <0, то перераспределение величины θ по соответствующему циклу приведет к уменьшению значения F (X) на величину θ·Δ _lk, т.е. опорное решение можно улучшить. Если же величины Δ _lk, называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие Δ _lk ≥0 х_lk =0.

Для решения транспортной задачи распределительным методом необходимо найти начальное опорное решение. Затем для очередной опорной клетки (l, k) построить цикл и вычислить оценку Δ _lk. Если оценка неотрицательная, переходят к следующей свободной клетке. Если же оценка отрицательная, следует осуществить сдвиг по циклу на величину θ = . В результате получится новое опорное решение.

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

Пример. Решить распределительным методом транспортную задачу:

bj ai

Решение. Строим начальное опорное решение:

.

Затем вычисляем значение целевой функции на нем: F (X ₁)=20·1+ +30·5+10·8 + 40·15 = 850.

bj ai

Находим цикл для свободной клетки (1,2) таблицы, он включает клетки (1, 2), (1, 3), (3, 3), (3, 2). Вычисляем оценку Δ₁₂ = (3+15)-(2+8)=8. Так как Δ₁₂=8> 0, переходим к следующей свободной клетке (2, 1). Для нее цикл таков: (2, 1), (1, 1), (1, 3), (3, 3), (3, 2), (2, 2). Оценка Δ₂₁=(4+2+8)-(1+15+5)=14-21=-7. Так как Δ₂₁ = -7 < 0, определяем величину груза, перераспределяемого по циклу, θ = {20, 40, 30} = 20. Приращение целевой функции Δ F = -7 · 20 = -140. Получаем новое опорное решение Х ₂. Значение целевой функции на нем

F (X ₂) = 20 · 2 + 20 · 4 + 10 · 5 + 30 · 8 + 20 · 15 = 710.

bj ai

Вычисляем Δ₁₁ = (1 + 15 + 5) - (2 + 8 + 4) = 7 > 0, Δ₁₂ = (3+15)-(2+8)=8> 0, Δ₂₃ = (7 + 8) - (5 + 15) = -5 < 0, Δ₃₁ = (6 + 5)—(4 + 8) = -1 < 0. Оценки можно вычислять до первой отрицательной. Так как Δ₂₃ = -5 < 0, осуществляем сдвиг по циклу (2, 3), (3, 3), (3, 2), (2, 2) на величину θ = {10, 20} = 10. Приращение целевой функции Δ F = -5 · 10 = -50. Получаем третье опорное решение Х ₃. Значение целевой функции на нем

F (X ₃) = 20 · 2 + 20 · 4 + 10 · 7 + 40 · 8 + 10 · 15 = 660.

bj ai

Вычисляем оценки для свободных клеток: Δ₁₁= (1 + 7) — (2 + 4) = 2 > 0, Δ₁₂ = (3 + 15) - (2 + 8) = 8 > 0, Δ₂₂=(5+15)-(7+8)=5>0, Δ₃₁=(6+7)—(4+15)=-6 < 0. Так как Δ₃₁ = -6 < 0, осуществляем сдвиг по циклу (3, 1), (2, 1), (2, 3), (3, 3) на величину θ = {20, 10} = 10. Приращение целевой функции Δ F = -6 · 10 = -60. Получаем четверки опорное решение Х ₄. Значение целевой функции на нем

F (X ₄) = 20 · 2 + 10 · 4 + 20 · 7 + 10 · 6 + 40 · 8 = 600.

bj ai

Вычисляем оценки для свободных клеток Δ₁₁ = (1 + 7) — (2 + 4) =2 > 0, Δ₁₂ = (3 + 7 + 6) - (2 + 4 + 8) = 2 > 0, Δ₂₂ = (5 + 6)-(4 + 8)=-1<0. Так как Δ₂₂=-1< 0, осуществляем сдвиг по циклу (2,2), (3,2), (3,1), (2,1) на величину θ={10,40}=10. Приращение целевой функции Δ F = -1 · 10 = -10. Получаем пятое опорное решение Х ₅.

bj ai

Значение целевой функции на нем

F (X ₅) = 20 · 2 + 10 · 5 + 20 · 7 + 20 · 6 + 30 · 8 = 590.

Вычисляем оценки для свободных клеток: Δ₁₁= (1 + 7) — (2 + 4) =2 > 0, Δ₁₂ = (3 + 7) - (2 + 5) = 3 > 0, Δ₃₃ = (15 + 5) - (7 + 8) = 5 > 0. Все оценки для свободных клеток положительные, следовательно, реше­ние оптимально.

Ответ: min F (X) = 590 при .

Дата добавления: 2014-01-04