Методы отсечения. Метод Гомори

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

· оно должно быть линейным;

· должно отсекать найденный оптимальный нецелочисленный план;

· не должно отсекать ни одного целочисленного плана.

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

Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограничение и т.д.

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

Один из алгоритмов решения задачи линейного целочисленного программирования (6.59)…(6.62), предложенный Гомори, основан на симплексном методе и использует достаточно простой способ построения правильного отсечения.

Рис. 6.18. Графическая иллюстрация целочисленного решения

Пусть задача линейного программирования (6.52)…(6.55) имеет конечный оптимум и на последнем шаге ее решения симплексным методом получены следующие уравнения, выражающие основные переменные через неосновные переменные оптимального решения

(6.56)

так, что оптимальным решением задачи (6.52)…(6.55) является , в котором, например β _i − нецелая компонента. В этом случае можно доказать, что неравенство

, (6.57)

сформированное по i -му уравнению системы (6.56), обладает всеми свойствами правильного отсечения.

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

Целой частью числа а называется наибольшее целое число , не превосходящее а. Дробная часть числа определяется как разность между этим числом и его целой частью, т.е. . Например, для = 2, ; для = -3 и .

Для решения задачи целочисленного линейного программирования (6.52)…(6.55) методом Гомори используется следующий алгоритм:

1. Симплексным методом решить задачу (6.52)…(6.55) без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования (6.52)…(6.55). Если первая задача (6.52)…(6.54) неразрешима (т.е. не имеет конечного оптимума или условия ее противоречивы), то вторая задача (6.52)…(6.55) также неразрешима.

2. Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и по соответствующему уравнению системы (6.56) сформировать правильное отсечение (6.57).

3. Неравенство (6.57) введением дополнительной неотрицательной целочисленной переменной преобразовать в равносильное уравнение

(6.58)

и включить его в систему ограничений (6.53).

4. Полученную расширенную задачу решить симплексным методом. Если найденный оптимальный план будет целочисленным, то задача целочисленного программирования (6.52)…(6.55) решена. В противном случае вернуться к п. 2 алгоритма.

Если задача разрешима в целых числах, то после конечного числа шагов (итераций) оптимальный целочисленный план будет найден.

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

Недостатком метода Гомори является требование целочисленности для всех переменных − как основных (выражающих, например, в задаче об использовании ресурсов единицы продукции), так и дополнительных переменных (выражающих величину неиспользованных ресурсов, которые могут быть и дробными).

Отметим, что переход к каноническому виду в полностью целочисленной задаче линейного программирования, содержащей ограничения − неравенства

, (6.59)

не приводит, вообще говоря, к полностью целочисленной задаче в каноническом виде, так как в преобразованных ограничениях (6.59)

вспомогательные переменные x_n+i не подчинены требованию целочисленности.

Однако если все коэффициенты a_ij, b_i в (6.59) − целые числа, то условие целочисленности можно распространить и на x_n+i, как это сделано при решении примера 6.10.

Полностью целочисленную задачу в каноническом виде можно получить также, если в (6.59) a_ij, b_i − рациональные числа. Для этого следует умножить (6.59) на общее кратное знаменателей коэффициентов − a_ij, b_i (т.е. перейти к целым коэффициентам в (6.59)) и лишь после этого ввести вспомогательные переменные .

Пример 6.20. Решить задачу полностью целочисленного программирования

(6.52')

при ограничениях

Решение. Приведем задачу к каноническому виду, введя дополнительные неотрицательные переменные . Получим систему ограничений:

Решаем задачу симплексным методом. Для наглядности решение иллюстрируем графически (рис. 6.19).

Рис. 6.19. Графическая иллюстрация решения задачи

На рис. 6.19 0 KLM – область допустимых решений задачи ограниченная прямыми (1), (2), (3) и осями координат; L (2/3;8) – точка оптимального, но нецелочисленного решения задачи ; (4) – прямая, отсекающая это нецелочисленное решение; 0 KNM – область допустимых решений расширенной задачи (6.64') N (2; 7) – точка оптимального целочисленного решения.

I шаг. Основные переменные ; неосновные переменные .

	х 1	х 2
х 3
х 4
х 5

↑

Первое базисное решение Х ₁ = (0;0;60;34;8) – допустимое. Соответствующее значение линейной функции f ₁ = 0.

Переводим в основные переменные переменную х ₂, которая входит в выражение линейной функции с наибольшим положительным коэффициентом. Находим максимально возможное значение переменной х ₂, которое позволяет принять система ограничений, из условия минимума соответствующих отношений:

,

т.е. разрешающим (выделенным) является третье уравнение. При х ₂ = 8 в этом уравнении х ₅ = 0, и в неосновные переменные переходит х ₅.

II шаг. Основные переменные ; неосновные переменные .

	х 1	х 5
х 3		-5
х 4		-4
х 2
		-3	-24

Х ₂ = (0;8;20;2;0); f = 24. Переводим в основные переменные х ₁, , а в неосновные х ₄.

Ш шаг. Основные переменные ; неосновные переменные . После преобразований получим:

	х 4	х 5				х 4	х 5
х 3	-3	-3		х 3	-1	-1
х 1		-4		х 1	1/3	-4/3	2/3
х 2				х 2
	-2	-1	-76		-2/3	-1/3	-76/3

Базисное решение Х ₃ оптимально для задачи , так как в выражении линейной функции отсутствуют неосновные переменные с положительными коэффициентами.

Однако решение Х ₃ не удовлетворяет условию целочисленности (6.55'). По первому уравнению с переменной х ₁, получившей нецелочисленное значение в оптимальном решении (2/3), составляем дополнительное ограничение (6.57):

Обращаем внимание на то, что согласно (6.56) и (6.57) берем дробную часть свободного члена с тем же знаком, который он имеет в уравнении, а дробные части коэффициентов при неосновных переменных х ₄ и х ₅ − с противоположными знаками.

Так как дробные части

то последнее неравенство запишем в виде

Введя дополнительную целочисленную переменную х ₆ ≥ 0, получим равносильное неравенству (6.57') уравнение

Уравнение (6.58) необходимо включить в систему ограничений (6.56') исходной канонической задачи, после чего повторить процесс решения задачи симплексным методом применительно к расширенной задаче. При этом для сокращения числа шагов (итераций) рекомендуется вводить дополнительное уравнение (6.58') в систему, полученную на последнем шаге решения задачи (без условия целочисленности).

IV шаг. Основные переменные ; неосновные переменные .

	х 4	х 5
х 1	1/3	-4/3	2/3
х 2
х 3	-1	-1
х 6	-1/3	-2/3	-2/3
	-2/3	-1/3	-76/3

Базисное решение − недопустимое. Заметим, что после включения в систему ограничений дополнительного уравнения, соответствующего правильному отсечению, всегда будет получаться недопустимое базисное решение.

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

V шаг. Основные переменные ; неосновные переменные . Получим после преобразований:

	х 4	х 6				х 4	х 6
х 1	-6/9	4/3	-12/9	х 1		-2
х 2	1/3	-1	-14/3	х 2	-1/2	3/2
х 3	1/3		38/3	х 3	-1/2	-3/2
х 5	-1/3		-2/3	х 5	1/2	-3/2
	3/9	1/3	150/9		-1/2	-1/2	-25

Х ₅ = (2;7;19;0;1;0); f ₅ = 25.

Так как в выражении линейной функции нет основных переменных с положительными коэффициентами, то Х ₅ − оптимальное решение.

Итак, f _max = 25 при оптимальном целочисленном решении Шестая компонента содержательного смысла не имеет.

Для геометрической интерпретации на плоскости 0 х ₁ х ₂ (см. рис. 6.19) отсечения (6.57') необходимо входящие в него переменные х ₄ и х ₅ выразить через переменные х ₁ и х ₂. Получим (см. 2-е и 3-е уравнения системы ограничений (6.56'):

(см. отсечение прямой (4) на рис. 6.19).