Методы отсечения для решения задач дискретного программирования.

Наиболее изучены целочисленные задачи линейного программирования.

Задача полностью целочисленного программирования, если наложено требование x_j — целые для j = 1, 2, …, n и частично целочисленного программирования, когда x_j — целые для j = 1, 2, …, n ₁, причём n ₁ < n.

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

Дискретные задачи математического программирования

образуют обширный класс нерегулярных задач.

Задача называется регулярной, если она отвечает следующим условиям:

1. Для каждой точки Î D можно определить некоторым образом понятие непустой окрестности Ì D.

2. Можно указать достаточно эффективно проверяемые необходимые и достаточные условия локальной оптимальности. На основе этих условий локальный оптимум целевой функции на множестве D может быть найден при помощи конечного (или бесконечно сходящегося) процесса.

3. Локальный оптимум целевой функции совпадает с глобальным.

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

Прямой перебор для задач с конечным множеством решений не может быть реализован, т.к. число точек удовлетворяющих допустимым условиям ³ 2 ⁿ.

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

А вообще, регуляризация лежит в основе методов “отсечения”.

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

1. Задачи с неделимостями.

2. Экстремальные комбинаторные задачи.

3. Задачи с неоднородной разрывной целевой функцией.

4. Задачи на неклассических областях.

5. Некоторые многоэкстремальные задачи.

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

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

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

1) полученный нецелочисленный план ему не удовлетворяет.

2) любой целочисленный план ему заведомо удовлетворяет.

Затем решается полученная расширенная задача, в случае необходимости добавляется ещё одно ограничение, и т.д.. Процесс продолжается до получения решения, удовлетворяющего условиям целочисленности.

Геометрически добавление каждого неравенства отвечает проведению гиперплоскости, отсекающей от многогранника решений ”регуляризованной” задачи старую оптимальную точку с дробными координатами, но не затрагивающей не одной целочисленной точки /Метод отсечения/

Вопрос только:

1) Как формировать дополнительные ограничения;

2) Необходимо доказать конечность соответствующего процесса отсечения;

3) Как бороться с чрезмерным увеличением размерности задачи.

II. Комбинаторные методы. Метод ветвей и границ.

III. Метод случайного поиска и другие приближённые методы.

Некоторые определения.

Метод отсечения.

В дальнейшем будут необходимы следующие понятия.

Лексикография.

1°. Говорят, что вектор = (x₁, …, x_n) лексикографически положителен , если

и x_k > 0, где k = min{ j | x_j ¹ 0}

1°°. Говорят, что вектор лексикографически неотрицателен, если , или

1°°°. Говорят, что вектор = (x₁, …, x_n) лексикографически больше вектора , , если

.

Лексикографически не меньше, , если .

Лексикографически отрицателен, , если .

Пусть имеем задачу линейного программирования

, i = 1, 2, …, m (1)

x_j ³ 0, j = 1, 2, …, n.

Под расширенным планом задачи линейного программирования понимают план

Определение План (расширенный план ) ЗЛП называется лексикографически оптимальным (или лексикографическим оптимумом), если для всех расширенных планов имеет место соотношение .

/ l — оптимальный план/

Теорема 1. Если множество оптимальных планов задачи ЛП (1) не пусто и ограничено, то существует лексикографическим оптимумом задачи (1).

(6, 3, 4, 5) ³ (6, 2, 5, 5)

Теорема 2. Если лексикографический оптимальный план задачи (1), то — опорный план.

Пусть вектора условий

— базис опорного плана X.

B = { j ₁, …, j_k } — индексы базисных переменных.

N = {1, …, n } – B — индексы небазисных переменных.

Qⁿ = {0, 1, 2, …, n }

N ° = {0}È N — множество индексов всех небазисных переменных + 0.

Опр. Симплексная таблица

|| x_ij ||, i Î Qⁿ, j Î N °

называется лексикографически нормальной, если

, " j Î N.

/ l — нормальная симплексная таблица/

Теорема 3. Для того, чтобы опорный план задачи (1) был l‑оптимальным, необходимо и достаточно, чтобы нашёлся такой базис B, что симплексная таблица

|| x_ij ||, i Î Qⁿ, j Î N °

является l‑нормальной.

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

Лексикографическая модификация метода последовательного уточнения оценок

Здесь вместо исходной задачи (1) , i =1,2… m, x_j ³ 0, j =1,2… n.

решается её лексикографический вариант. Требуется найти лексикографический максимум расширенного плана при , i = 1, 2, …, m, x_j ³ 0, j = 1, 2, …, n.

Система ограничений определяет допустимый многогранник L. Задачу (1) будем обозначать, как (L, C), где C — вектор целевой функции. (не скал. умн.). А задачу лексикографической максимизации или l ‑задачу . Соответствующая модификация метода последовательного уточнения оценок — l‑метод.

Общая итерация l‑метода описывается следующим образом. Пусть имеется l‑псевдоплан . Ему соответствуют:

B_r — множество индексов базисных переменных;

N_r — множество индексов небазисных переменных;

T_r — симплексная таблица.

			…	– xl	…	–
x0	x00		…	x0 l	…
x1	x10	…	…	…	…	…
X2	x20	…	…	…	…	…
…	…	…	…	…	…	…
xk	xk0	…	…	xkl	…	Xk
…	…	…	…	…	…	…
xn	xn0	…	…	Xnl	…

{ j ₁, …, l, …, j_k } = N_r. Все , j_k Î N_r.

Столбцы таблицы T_r обозначим через , .

Проверяем, является ли таблица T_r допустимой, т.е. выполнено ли условие , i = 1, 2, …, n.

Если является, то — l ‑оптимальный план. Если нет, то ищем переменную x_k, выводимую из базиса, по правилу

Затем отыскивается переменная x_l, вводимая в базис, по правилу

Если среди чисел нет отрицательных, то задача неразрешима. Если такие числа есть, то переходим к новому l‑псевдоплану , которому соответствует B_r+1 = (B_r È{l}) ‑ {k},

N_r+1 = (N_r È{k}) ‑ {l}.

Элементы новой таблицы T_r+1 получаются по следующим формулам:

, i = 0, 1, 2, …, n, (столбец делится)

, " j Î(N_r – { l }) È {0}; i = 0, 1, 2, …, n.

Другими словами, столбец, в котором находится поправляющий элемент , делится на этот элемент и умножается на (‑1). Чтобы получить любой другой столбец новой таблицы, надо к соответствующему старому столбцу прибавить вновь полученный, умноженный на элемент стоящий на пересечении направляющей строки и искомого столбца. Затем повторяется общая итерация. Способ получения l‑нормальной таблицы.

Ищется такое число

вводят x_{n +1}³ 0; , добавляют к таблице. Из базиса выводят x_k, k = n +1,

выводят x_l, R_l = lex min{ R_j | j ÎN}

производят пересчёт и получают l‑нормальную таблицу.