Второй алгоритм Гомори

4. Второй алгоритм Гомори

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

Пусть в области, определенной условиями:

(20)

(21)

 – целые, (22)

требуется максимизировать функцию

(23)

Метод решения задачи (20–23) основывается на той же идее, что и метод решения полностью целочисленных задач. А именно: строится область £_k, которая при k = 0 определяется условиями (20–21); решается полученная при этом задача линейного программирования (20–21, 23). Если задача (20–21, 23) оказывается разрешимой, то полученное оптимальное решение ее анализируется на допустимость для исходной задачи целочисленного программирования (20–23). Если найденное решение оказывается целочисленным, то одновременно оно будет оптимальным для (20–23). Если оптимальное решение (£_k, C) – задачи оказывается недопустимым для исходной задачи (20–23), то осуществляется построение правильного отсечения и переход к решению новой задачи,

Второй алгоритм Р. Гомори формулируется в виде следующей теоремы:

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

(24)

 – целое, (25)

где

(26)

определяет правильное отсечение. Блок-схема второго алгоритма Р. Гомори аналогична блок-схеме первого алгоритма Р. Гомори и отличается лишь правилом построения коэффициентов правильного отсечения.

Правило построения правильного отсечения

Пусть x(£_k, C) не удовлетворяет условию целочисленности,  – элементы симплексной таблицы, соответствующей полученному оптимальному решению (£_k, C) – задачи. Выберем i₀=min {i | i Î (1, 2,…, n), x_i0^k – нецелое} и строим правильное отсечение по формулам (24 – 26).

Условия конечности второго алгоритма Гомори:

1) Целевая функция F(x) удовлетворяет условию целочисленности. Это учитывается при выборе строки k для построения правильного отсечения.

2) Выполнено по крайней мере одно из двух условий:

2') целевая функция ограничена снизу на многогранном множестве £= £₀;

2») задача (£₀^ц, C) имеет по крайней мере один план.

С помощью второго алгоритма Гомори можно (в случае n₁=n) решать и полностью целочисленную задачу линейного программирования. Однако в этом случае нет оснований для сравнения эффективности второго и первого алгоритмов Гомори.

5. Алгоритм Дальтона и Ллевелина

Второй алгоритм Гомори имеет дело с частично целочисленными задачами линейного программирования. Дальтон и Ллевелин рассматривают 0 олее широкий класс задач – частично дискретные задачи линейного программирования и применительно к ним модифицируют второй алгоритм Гомори.

Напомним, что решением задачи дискретного программирования будем называть вектор, координаты которого принадлежат £^ц области вида:

(27)

(28)

(29)

и максимизирует значение функции

(30)

Будем предполагать, что  проранжированы, т.е.  и являются наперед заданными числами.

Теорема. Пусть x(£_k, C) – оптимальное решение задачи (27–28, 30),  – элементы симплексной таблицы, соответствующей ему.

Если x(£_k, C) является недопустимым решением задачи (27–30) и , тогда, используя i-ю строку симплексной таблицы, можно построить отсечение, обладающее свойством правильности по формулам:

(31)

(32)

где

(33)

Доказательство. Проверим вначале условие отсечения. Пусть в оптимальном решении x(£_k, C) координата  не удовлетворяет условию (29). Покажем, что в этом случае вектор х(£_k, C) не удовлетворяет условиям (31, 32). Поскольку N_k – множество индексов небазисных переменных x_i, которые в оптимальном решении равны нулю, то равенство (31) принимает вид  и будет отрицательным согласно условию теоремы. Следовательно, , т.е. условие отсечения не выполняется.

Проверим условие правильности. Для этого покажем, что любое допустимое решение задачи (27–30) удовлетворяет условиям (31, 32).

Запишем разложение для координаты допустимого решения задачи (27–30) по небазисным переменным

(34)

и рассмотрим два случая: a) ; б) . Введем обозначения:

и представим (34) в виде

где

Очевидно,  так как .

Рассмотрим случай а): , или что все равно, .

Отсюда Но поэтому

(35)

Домножим обе части (35) на неотрицательную величину  и сложим с неотрицательной величиной :

(36)

Рассмотрим случай б):  или, что все равно,  Так как по определению , то  Умножим обе части неравенства  на неотрицательную величину  и на -1, получим . Прибавляя к полученному выражению неравенство , получим

(37)

Таким образом, в а) и в б) случаях пришли к одному и тому же неравенству (36) и (37). Пользуясь ранее введенными обозначениями, их можно записать

(38)

Формула (38) определяет правильные отсечения. Сравнивая ее с выражением (31–32), приходим к выводу, что коэффициенты определяются следующим образом:

Теорема доказана.

Алгоритм Дальтона – Ллевелина может быть описан следующим образом.

1. Решается (£_k, C) – задача (27–30) (вначале k = 0). Пусть x(£_k, C), k = 0, 1, 2,… оптимальное решение (£_k, C) – задачи,  – симплексная таблица.

2. Проверяется условие допустимости по всем координатам оптимального вектора решения х(£_k, C) (£_k, C) – задачи. Если условие допустимости выполняется, то полученное решение является оптимальным решением исходной задачи (27–30). Если условие допустимости не выполняется хотя бы по одной координате, осуществляется переход к 3.

3. Пусть  не удовлетворяет условию допустимости. Тогда выбирается

i₀ = min {i| 1<i<n₁, х_j0^k – не удовлетворяет (29)}.

4. Для выбранного номера i=i₀ строится правильное отсечение, т.е. вводится дополнительная переменная

где определяется формулой (33),

5. Добавляем линейное ограничение, определяющее правильное отсечение, к условиям (£_k, C) – задачи и получаем новую (£_k+1, C) – задачу. Полагая k = k + 1, переходим к п. 1.

Приведем без доказательства теорему о конечности алгоритма.

Теорема. Если: коэффициенты целевой функции дискретны; F(x) ограничена снизу на многогранном множестве £; задача (£, C) имеет по крайней мере одно решение; выбор строки для построения правильного отсечения производится по правилу минимального номера и (£_k, C) – задачи решаются методом последовательного уточнения оценок, то алгоритм Дальтона и Ллевелина сходится.