21. Лемма 2. Базисный план перевозок.

Определение. Цепью транспортной таблицы будем называть такую последовательность ее клеток, что:

1. соседние клетки стоят в одной строке либо в одном столбце и

2. ни в одной строке и ни в одном столбце транспортной таблицы не входит более двух клеток цепи (т.е. либо две, либо одна, либо ни одной).

Определение. Циклом транспортной таблицы называется такая ее цепь, для которой первая и последняя клетки стоят либо в одном столбце, либо в одной строке.

Лемма 2. Цепь тогда и только тогда является циклом, когда столбцы матрицы , соответствующие ее клеткам, линейно-зависимы.

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

1) (количество базисных клеток);

2) из клеток нельзя составить цикла (линейная независимость);

3) (небазисные перевозки нулевые).

22. Базисный план. Метод минимального элемента.

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

1) (количество базисных клеток);

2) из клеток нельзя составить цикла (линейная независимость);

3) (небазисные перевозки нулевые).

Существует несколько способов построения базисного плана. Один из самых удобных – метод минимального элемента: выбираем в транспортной таблице клетку с минимальными транспортными издержками – . Полагаем ее базисной и для нее . Возможны три случая:

а) . Тогда строку исключаем из дальнейшего рассмотрения и корректируем объем в столбце : .

б) . Столбец исключаем из рассмотрения и изменяем объем .

в) . Исключаем строку (либо столбец ); полагаем (либо ).

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

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

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

23. Метод потенциалов транспортной задачи.

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

1) (количество базисных клеток);

2) из клеток нельзя составить цикла (линейная независимость);

3) (небазисные перевозки нулевые).

Метод потенциалов: Пусть – начальный базисный план задачи (1)-(4). , . Вспоминаем определение вектора оценок и вектора потенциалов:

или (7)

(8)

Вводя обозначение и учтя строение столбцов матрицы получим для (7) и (8) (покомпонентно)

(7^*)

(8^*)

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

Система позволяет для базисного плана вычислить оценки (однозначно). Из симплекс-метода (вместо максимизации в транспортной задаче рассматривается задача минимизации) вытекает утверждение: условие

(9)

достаточно, а в случае невырожденности базисного плана ( ) и необходимо для его оптимальности.

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

(10)

(можно в качестве взять и любую положительную).

Добавим клетку к базисным клеткам. При этом возникнет цикл (леммы 1,2), причем единственный. Положим перевозку . Чтобы построить новый план, нужно в соседних с клетках цикла по строке и столбцу от базисных перевозок отнять число (должно выполняться условие баланса по строкам и столбцам: сумма перевозок в -той строке равно , а в -том столбце – . Далее в соседних к следующим базисным клеткам по циклу нужно прибавить и т.д. Число клеток в цикле четно и обычно для совершения итерации (определения и построения нового базисного плана) клетки цикла начиная с поочередно помечают знаками «+» и «–». Выбирают , – базисные клетки цикла, помеченные знаком «–». Прибавляем к перевозкам цикла в клетках, помеченных знаком «+», отнимаем от перевозок в клетках, помеченных знаком «–». Перевозки, не входящие в цикл, оставляют неизменными. Если из базиса убрать клетку , то построенный план с базисным множеством будет новым базисным планом транспортной задачи (после исключения цикл разорвется, а других циклов в быть не может). При этом целевая функция уменьшится на величину .

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

и вычислены минимальные расходы: .