Файл: Тема Задачи исследования операций с целочисленными переменными.doc

§3. Общая характеристика методов отсечения

Рассмотри задачу линейного целочисленного программирования (З.Л.Ц.П.):

(3.1)

(3.2)

x_j ≥ 0, _(3.3)



x_j –целые, (3.4)

где a_ij и b_i ( ) – целые числа.

Пусть условия (3.2) , (3.3) определяют некоторый многогранник D₁, а условия (3.2) – (3.4) – множество D_ц целочисленных точек решений исходной З.Л.Ц.П.

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

Пусть нам удалось построить выпуклую оболочку множества решений D_ц задачи целочисленного программирования, так называемый, целочисленный многогранник . Тогда задачу целочисленного программирования нахождения максимума целевой функции Z в области D_ц можно заменить задачей линейного программирования отыскания максимума целевой функции Z в области так как оптимальное решение этой последней задачи совпадает с оптимальным решением исходной задачи (2.1) – (2.4). Так как выпуклую оболочку построить сразу трудно, Данциг предложил итерационный метод решения этой задачи. На каждом k-ом шаге строится промежуточный многогранник D_k, являющийся приближением к целочисленному, и решается соответствующая задача линейного программирования. Многогранник

---

D_k получается отсечением от многогранника D_k-1 некоторой его части, не содержащей целочисленных точек. Отсечение осуществляется введением дополнительного ограничения. Это ограничение обладает двумя свойствами:

1. 
   ему удовлетворяют все целочисленные решения исходного З.Л.Ц.П.
   
2. 
   оптимальное нецелочисленное решение З.Л.П. не удовлетворяет этому ограничению.
   

Такое ограничение называется правильным отсечением.

На основе этой идеи американский математик Гомори предложил алгоритм решения задач целочисленного программирования, он обосновал правила построения дополнительных ограничений, т.е. многогранников D_k и доказал сходимость алгоритма.

§4. Алгоритм Гомори.

Первый шаг. Решим задачу максимизации функции Z на многограннике D₁, т.е. задачу линейного программирования. (3.1) – (3.3) симплексным методом, предварительно приведя ее к стандартному виду. Через конечное число шагов получим оптимальную таблицу:

СП БП	x1	x2	…	xn	xn+1	xn+2	…	xn+m	bi
xi1			…				…
xi2			…				…
…	…	…	…	…	…	…	…	…	…
xim			…				…
Z	q1	q2	…	qn	qn+1	qn+2	…	qn+m	Q

---

где x_i1, x_i2, …, x_im – базисные переменные множества всех переменных {x₁, x₂, …,x_n+m}. В этой таблице: q_j ≥ 0, . Оптимальные значения базисных переменных:

(4.1),

а свободные переменные равны нулю. Эти условия определяют оптимальное решение задачи (3.1) – (3.3), точку многогранника D⁽¹⁾. Если все – целые числа, то решение (4.1) является оптимальным решением задачи (3.1) – (3.4).

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

Пусть – не целое. Строим правильное отсечение по формуле:
, (4.2)

где (4.3)

где и - целые части чисел и соответственно.

Так как все ≥ 0, то β_i > 0. Значения α_ij, соответствующие целым значениям равны нулю.
Третий шаг. Ограничение (4.2) добавляем к системе (3.2), (3.3) и решаем новую З.Л.П.

(3.1)

(3.2)

(4.2)

x_j≥ 0,

---

<sub>(3.3)

Условия (3.2), (3.3), (4.2) определяют многогранник D2,которому принадлежат все целочисленные точки области D1, но не принадлежит оптимальная нецелочисленная точка многогранника D1.

Решаем задачу (3.1) – (3.3), (4.2) М-методом. Если полученное при этом оптимальное решение будет целочисленным, то оно и будет оптимальным решением исходной З.Л.Ц.П., если нет, то повторяем второй и третий шаги до тех пор, пока не будет получено оптимальное целочисленное решение, либо мы убедимся в неразрешимости задачи (3.1) – (3.4).

Если в симплексной таблице появится строка с нецелочисленным свободным членом, а остальные элементы этой – целые числа, то</sub> это означает, что соответствующее уравнение не имеет целочисленного решения и исходная З.Л.Ц.П. неразрешима.

Замечания:

1. 
   При решении каждой новой З.Л.П. ограничение типа (4.2) приведенное к эквивалентному уравнению можно вводить непосредственно в оптимальную таблицу решения предыдущей задачи.
   
2. 
   _{Студенты изучившие тему «Двойственный симплекс-метод», могут применять его для решения задач построенных на третьем шаге.}
   

<sub>Пример.

Решить З.Л.Ц.П. методом Гомори.

Z = 4x1 + 5x2 → max



1-й шаг. Приведем к стандартному виду исходную З.Л.П. и решим ее симплекс-методом.



(4.4)

Z = 4x1 + 5x2 + 0∙x3 + 0∙x4 + 0∙x5 → max</sub>

Cj		4	5	0	0	0	bi
Ci	xj xi	x1	x2	x3	x4	x5
0	x3	3	2	1	0	0	10	10/2
0	x4	1	4	0	1	0	11	11/4 min
0	x5	3	3	0	0	1	13	13/3
Z		- 4	-5↑	0	0	0	0
0	x3	10/4	0	1	-2/4	0	18/4	18/4:10/4=18/10 min
5	x2	1/4	1	0	1/4	0	11/4	11/4:1/4=11
0	x5	9/4	0	0	-3/4	1	19/4	19/4:9/4=19/9
Z		-11/4↑	0	0	5/4	0	55/4
4	x1	1	0	4/10	-2/10	0	18/10
5	x2	0	1	-1/10	3/10	0	23/10
0	x5	0	0	-9/10	-3/10	1	7/10
Z		0	0	11/10	7/10	0	187/10

---

Оптимальное решение:



Решение нецелочисленное, переходим ко второму шагу.

2-ой шаг. Строим правильное отсечение по любой из строк, соответствующих нецелочисленной переменной, например по 3-й строке, соответствующей базисной переменной x₃.

α₃₁x₁ + α₃₂x₂ + α₃₃x₃ + α₃₄x₄ + α₃₅x₅ ≥ β₃.

В этом неравенстве α₃₁, α₃₂ и α₃₅ равны нулю, они соответствуют значением .

,

,

.

Новое ограничение имеет вид:

(4.5)
3-й шаг. Вводим это ограничение в систему ограничений исходной З.Л.П. (4.4) и полученную задачу приводим к стандартному виду. Неравенство (4.5) эквивалентно уравнению

, где x₆ ≥ 0.

Новая З.Л.П. имеет вид:



<sub>(4.6)

Z = 4x1 + 5x2 + 0∙x3 + 0∙x4 + 0∙x5 + 0∙x6 → max



Первые 3 уравнения задачи эквивалентны уравнения приведенным к базисным переменным x1, x2, x5, которые выписываем из последней таблицы решения исходной З.Л.П.; с учетом этого задача (4.6) будет иметь вид:



(4.7)

Z = 4x1 + 5x2 + 0∙x3 + 0∙x4 + 0∙x5 + 0∙x6 → max</sub>
Так как в четвертом уравнении переменная

---