Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А

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

соответствующие ограничениям (4.6.2), a vj , j 1, n - переменные

двойственной задачи, отвечающие ограничениям (4.6.3). В соответствии с данным видом двойственной задачи, оценки в транспортной задаче будут иметь вид

123

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

алгоритма симплексного метода, если существует вектор Ai0 j0 с

положительной оценкой, то вектор Ai0 j0 должен быть введен в

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

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

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

Пример цикла:

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

ставятся (*) в клетках из множества B и в клетке (i0 , j0 ) , которая

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

124

Оставшиеся элементы образуют цикл.

Когда цикл построен, можно следующим образом найти коэффициенты вводимого вектора: перенумеровать все элементы цикла, присвоив вводимому элементу 0, следующему 1 и т.д.;

коэффициенты разложения вектора Ai0 j0 равны +1 по векторам из

цикла с нечетными номерами, -1 - по элементам цикла с четными номерами и 0 по векторам, не входящим в цикл. Обозначим через

множество индексов (i, j) с четными номерами, через - множество индексов (i, j) с нечетными номерами .

Зная координаты вектора Ai0 j0 , его можно ввести в базис по правилам симплексного метода. Поскольку координаты вводимого

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

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

4.6.3. Алгоритм метода потенциалов

Итерация 0.

0.1.Определить исходная базисная точка с помощью любого из алгоритмов построения начального базиса.

125

0.2. Вычислить значение целевой функции

- множество базисных индексов.

0.3.Положить k 0 .

Итерация k 1.

Пусть на k -той итерации получена базисная точка xk со значением целевой функции z(xk ) .

126

Пример. 3

Итерация 0. Определяем начальный базис методом минимального элемента.:

L(x0 ) 0*12+1*8 +1*6 + 2*6 + 3* 0 + 3*2 + 8* 5 + 4*1 = 76

{(1,4), (2,1), (2,3), (2,5), (3,1), (4,2), (4,3), (4,4)}

Итерация 1.

1.1Помечаем звездочками места, занимаемые базисными элементами. Полагаем u1 0 .

127