double arrow

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

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

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

(3.23)
x0= max;

(3.25)
(3.24)
= bj; i = 1, 2,..., m;

(3.26)
xj ³ 0; j = 1, 2,..., n;

xj – целое; j = 1, 2,..., nj.

При n1 = n задача (3.23) – (3.26) является полностью, а при n1 < n – частично целочисленной задачей линейного программирования. По аналогии с задачей линейного программирования введем ряд понятий. Множество наборов (х1, х2,..., xn), удовлетворяющих условиям (3.24) – (3.26), называется областью определения или допустимой областью задачи целочисленного программирования и обозначается через Lц. Для сокращенного обозначения задачи (3.23) – (3.26) применяется запись (Lц, c), где с – вектор-столбец, состоящий из элементов сi. Оптимальное решение или оптимальный план обозначается через х (Lц, c). Наряду с оптимальным планом x опт = = (x1опт, x2опт,..., xnопт) будет рассматриваться расширенный оптимальный план

xопт = (x0опт, x1опт,..., xnопт),

где

x0 =.

Сокращенно оптимальный расширенный план обозначается как

х ‘ (Lц, c).

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

Основная идея методов отсечения заключается в построении такой эквивалентной задачи линейного программирования (А, с), при которой исходная задача целочисленного программиро-вания (Lц, c) сводится к ее решению. Иногда это называют линейной аппроксимацией целочислен-ного программирования (Lц, c).

Введем понятие правильного отсечения, физически означающее выбор такой гиперплоскости, которая разделяет оптимальные решения целочисленной линейной задачи х (Lц, c) и задачи линей-ного программирования х (L, c), причем, последняя не удовлетворяет условию целочисленности

х (L, c) Ë Lц.

(3.27)
Математически правильное отсечение означает выбор такого числа β, при котором неравенство

∑ajxjβ

j

выполняется при условиях

(3.28)
ах (L, c) > β;

(3.29)
{ х (Lц, c)| ах Ј β } Ì Lц,

где а – вектор-строка, состоящая из элементов.

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

1. На k-м этапе решается вспомогательная задача линейного программирования (Lk, c), k = 0, 1, 2, где L0 = L.

2. Если на k-м этапе оптимальное решение x (Lk, c), удовлетворяет условию целочисленности, то оно будет также оптимальным решением x (L0ц, c) исходной задачи (L0ц, c), так как на всех этапах множества целочисленных точек совпадают, т.е.

L0ц = L1ц = L2ц =...,

что является специальным условием при отсечении.

3. Если на k-м этапе решение не удовлетворяет условиям целочисленности, то x (Lk, c) не является оптимальным решением исходной целочисленной задачи. В этом случае переходят от k-го этапа к (k + 1)-му, добавляя к линейным ограничениям задачи (Lk, c) условие правильного отсечения

(3.30)
a k xβ k,

которое превращает многогранник (множество) Lk в многогранник Lk+1. Каждый конкретный метод имеет свой способ задания отсечения, но в алгоритмах Гомори гарантируется конечное число процедур.

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

(3.31)
x0= max;

(3.32)
= bj; i = 1, 2,..., m;

(3.33)
(3.34)
xj ³ 0; j = 1, 2,..., n;

xj – целое.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: