Динамическое программирование (стр. 7 из 10)

Формируем подмножество дуг, составляющих промежуточные маршруты по ветвям r 1, r 2 . 3) Итерация K

При очередном включении дуги ⁱ₀ , ^j₀ ^k в искомый ГК не исключено появление подциклов, т.к. требование замкнутости маршрута отсутствует.

Проанализируем ситуацию, в которой возможно появление подциклов с учетом того, что подцикл i, i формализован априори заданием ^C_ii , а подцикл ⁱ₀ ⁱ₀ запрещен правилом формирования мат-

рицы Ci0 j0 .

Пусть из элементов ^P_r после включения в него ⁱ₀, ^j₀ ^{( k)} можно составить маршрут ⁱ₀ ^j₀ ^u₁ ⁱ₀. Тогда возникает подцикл из ^u₁ â ⁱ₀ . По соответствующей матрице смотрим, является ли элемент ^C_ui0 нулевым. Если не является, то цикла не будет, если является, то цикл возможен и нужно запретить переход u, ⁱ₀ на этот шаг, положив ^C_ui0 : .

Аналогично, анализируются другие цепочки маршрутов.

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

Если множесто ^P_r состоит ровно из n 1 элемента, то ГК задан однозначно из и нижняя граница на этом подмножестве равна длине единственного цикла минимальной длины. В этом случае ГК является рекордом (претендентом на решение задачи).

4) Существуют 3 варианта последовательности разбиения ветвей дерева ветвления:

-

ветвление «полным фронтом», когда на каждом шаге K вычисляются и сравниваются оценки всех множеств X rk , X rk , r 1, rk ;

- ветвление «побегами», при котором разбиение некоторой ветви ведется до момента, когда ее оценка превышает оценку оборванной ветви. Затем развивается оборванная ветвь до момента, когда ее оценка станет хуже;

-

односторонний обход дерева, когда левая ветвь развивается до момента первого рекорда, затем его длина сравнивается с оборванными ветвями и если будет найдена ветвь с наименьшей оценкой, то она развивается до получения 2-го рекорда или до момента, когда m( ^X_r^k ) или m( ^X _r^k ) станет не лучше текущего значения рекорда.

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

1.4 МЕТОДЫ ОТСЕЧЕНИЯ. ПЕРВЫЙ АЛГОРИТМ ГОМОРИ

1.4.1 Первый алгоритм Гомори

Алгоритм Гомори предназначен для решения полностью ЦЗЛП. Алгоритм Гомори реализует пошаговый процесс. Планом на шаге k0 является решение ЗЛП на допустимой области X, которая получается из исходной ОДР X исключением условий целочисленности.

План на шаге k 1,2,... является решение ЗЛП x ^k на области X, которая строится на основе ОДР предыдущего шага k 1 X ^{k 1} и с учетом дополнительного ограничения ^l_k ; причем ограничение ^l_k вводится не прямо в допустимую область X ^k , а опосредованно через введение дополнительной базисной переменной в план предыдущего шага x ^{k 1} .

Пусть получен план шага k 1 и в нем ^x_j* - не целочисленная переменная. По переменной ^x_j* строится так называемое правильное отсечение ^l_k таким образом: в базис шага k 1 вводится новая переменная

x . Известно, что любая базисная переменная может быть выражена через свободные по формуле:

xá a xj , xi*

I aij' xj . (1)

Здесь ^b_i^' - численное значение базисной переменной ^x_i^á на шаге k 1 , ^a_ij^' - коэффициенты в столбцах замещения при свободных переменных на шаге k 1 , J ^ñâ, I ^á - множество индексов свободных и базисных переменных.

Для вновь вводимой базисной переменной ^x_n m _k в правой части соотношения берутся ^b_i^' , aij' .

Тогда (1) запишется в виде lk xn m k bi' j* aij' j* x j . (2) j Jñâ

Соотношение (2) задает условие правильного отсечения:

А) условие отсечения – оптимальный план предыдущего шага x^{( k 1)} не удовлетворяет (2);

Б) условие правильности – искомый оптимальный план исходной задачи x^* удовлетворяет (2).

Можно сказать, что переменная ^x_n m _k , введенная в базис таким способом является целой и положительной, т.е. находится в ОДР исходной задачи ЦП.

В тоже время, базис, включающий xn m k является недопустимым, т.к. xn m k { bi' } j* 0 . Для нахождения плана на k -ом шаге следующего шага нужно использовать алгоритм двойственного симплексметода.

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

Доказательство конечности первого алгоритма Гомори включает в качестве условия требование целочисленности целевой функции и возможность использования строки целевой функции при выборе строки для построения правильного отсечения. Таким образом, для решения задачи методом Гомори следует сделать C _j j 1, n целыми, это можно сделать, выбрав другие единицы измерения.

Критерием оптимальности плана является отсутствие отрицательных значений базисных переменных x _i^á 0, i I ^áê. Здесь I ^áê - множество индексов базисных переменных на шаге k , включая индекс ^x_n m k .