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

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

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

Доказательство. Опорное решение занимает N = m + n -1 клеток таблицы, которым соответствуют линейно независимые векторы условий. Согласно теореме 6.3 никакая часть занятых клеток не образует цикл. Если же к занятым клеткам присоединить одну свободную, то соответствующие им m + n векторы – линейно зависимые, и по той же теореме существует цикл, очевидно, содержащий эту клетку. Предположим, что таких циклов два и . Тогда, объединив клетки обоих циклов без свободной клетки , получим последовательность клеток

, ,

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

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

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

Рис 6.2

Сдвигом по циклу на величину q называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком "+", на q и уменьшение объемов перевозок во всех четных клетках, отмеченных знаком "-", на q.

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

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

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

Если оставить свободной одну из клеток с нулевым объемом перевозки, соответствующих , то число занятых клеток будет равно N = m + n -1.

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

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

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

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

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

,

где – сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком "+"; – сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком "-".

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

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

. (6.11)

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

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

Пример 6.4. Решить распределительным методом транспортную задачу, исходные данные которой приведены в табл. 6.7.

Т а б л и ц а 6.7

Решение. Строим начальное опорное решение методом минимальной стоимости (табл. 6.8).

Т а б л и ц а 6.8

Затем вычисляем значение целевой функции на нем

= 20×1 + 30×5 + 10×8 + 40×15 = 850.

Т а б л и ц а 6.9

Находим цикл для свободной клетки (1, 2) таблицы (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) (см. табл. 6.8). Оценка = (4 + 2 + 8) - (1 + 15 + 5) = 14 - 21 = -7. Так как = -7 < 0, определяем величину груза, перераспределяемого по циклу . Приращение целевой функции DZ = -7 × 20 = -140. Получаем новое опорное решение (табл. 6.9).

Значение целевой функции на нем = 20 × 2 + 20 × 4 +
10 × 5 + 30 × 8 + 20 × 15 = 710.

Вычисляем = (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) на величину . Приращение целевой функции DZ = -5×10 = -50. Получаем третье опорное решение (табл. 6.10).

Т а б л и ц а 6.10

Значение целевой функции на нем = 20 × 2 + 20 × 4 +
10 × 7 + 40 × 8 + 10 × 15 = 660.

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

= (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) на величину . Приращение целевой функции DZ = -6 × 10 = -60. Получаем четвертое опорное решение (табл. 6.11).

Т а б л и ц а 6.11

Значение целевой функции на нем = 20 × 2 + 10 × 4 +
20 × 7 + 10 × 6 + 40 × 8 = 600.

Вычисляем оценки для свободных клеток = (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) на величину . Приращение целевой функции DZ = -1×10 = -10. Получаем пятое опорное решение (табл. 6.12).

Т а б л и ц а 6.12

Значение целевой функции на нем = 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 Z(X) = 590 при .