Глава 4. Целочисленное линейное программирование.

Важное значение в ЛП имеет случай, когда неизвестные целочисленные.Задача ЛП с дополнительным условием целочисленности неизвестных исследуется в новойобласти математического программирования – целочисленном (дискретном) программировании (ЛЦП).

§1 Метод Гомори

К основной задаче ЛП добавим дополнительное условие – условие целочисленности неизвестных, в результате получим задачу ЛЦП. Можно, конечно, получить дробное оптимальное решение задачи ЛП и его округлить до ближайших целых значений. Но тогда может случиться, что мы будем либо близки к оптимальному плану задачи ЛЦП, либо далеки, либо вообще уйдем за пределы множества планов ЛЦП.Один из возможных методов решения задачи ЛЦП – метод Гомори.Идея метода базируется на представлении вещественного числа в виде суммы его целой и дробной частей.Как известно, целой частью вещественного числа «а» называется наибольшее целое число, не превосходящееОбозначение целой части[a].Разностьесть дробная часть числаОчевидно, например, чтоиНапример:

Рассмотрим метод Гомори на примере (общая задача ЛП):

Снимем условие целочисленности.

MaxZ= x₁ + 2 x₂

при условиях: x₁ - 2 x₂ + x₃ = 2

- 2x₁ + x₂ + x₄ =2

x₁ + x₂ + x₅ =3

.

Исходная симплексная таблица

Базисные переменные	Свободные члены ()	Коэффициенты при неизвестных
	2	1	-2	1
	2	-2	1		1
	3	1	1			1
Z	0	-1	-2

Итерация 1

Базисные переменные	Свободные члены ()	Коэффициенты при неизвестных
	6	-3		1	2
	2	-2	1		1
	1	3			-1	1
Z	4	-5			2

Итерация 2

Базисные переменные	Свободные члены ()	Коэффициенты при неизвестных
	7			1	1	1
			1
		1
Z	= 5

Задача ЛП решена. Решение нецелочиcленное.

Добавляем неравенство Гомори к итерации 2. Получим задачу ЦЛП:

Max Z = x₁ + 2 x₂

при условиях: x₃ + x₄ + x₅ = 7

x₂ + x₄ +x₅ =

x₁ - x₄ + x₅ =

- x₄ - x_{5 ≤}

.

.

Исходная симплексная таблица

Базисные переменные	Свободные члены ()	Коэффициенты при неизвестных
							S2
	7			1	1	1
			1
		1
S2							1
Z	= 5

Итерация 1

Базисные переменные	Свободные члены ()	Коэффициенты при неизвестных						S2
	5			1		-1	3
	2		1				1
	1	1					-1
S2	2				1	2	-3
Z	5					1	1

Получили оптимальное и целочисленное решение L(max) = 5. Дадим геометрическую интерпретацию решения данной задачи. Из рис. 1 видно, что максимально значение целевая функция принимает в точке , то есть решениеявляется оптимальным, но без учета требования целочисленности.

II

 

 Рис. 1

С учетом требования целочисленности решение не является оптимальным, поэтому используем дополнительное ограничение

или . Значения переменных x4 и x5 подставим из второго и третьего уравнений системы ограничений,. В результате получим. Этому неравенству на рис. 1 соответствует полуплоскость, ограниченная прямой, отсекающей от многоугольника допустимых решений треугольник АДА*. В новом многоугольнике допустимых решений ОДА*ВС найдем точку А*(1,2), в которой целевая функция принимает максимальное значение. Так как координаты точки А* – целые числа, то решениеявляется оптимальным планом исходной задачи.

Пример.

(1)

Отбросим пока условие целочисленности (*) и решим задачу ЛП

(2)

Задача ЛП – каноническая.

Исходная таблица

B	Свободный член	Коэффициенты при неизвестных
	15

Итерация 1

B	Свободный член	Коэффициенты при неизвестных

Итерация 2

B	Свободный член	Коэффициенты при неизвестных

План: оказался нецелочисленным.Для отыскания целочисленного плана применим метод Гомори (метод отсечений). С этой целью из завершающей симплексной таблицы выпишем каноническую систему (3) (эквивалентная системе (2)):

(3)

Свободные члены обоих уравнений дробные. Выбираем первое уравнение (с наибольшим дробным свободным членом):

Рассмотрим неравенство (т. н. неравенство Гомори)

(3)*

Запишем (с положительным свободным членом)

. (3)**

В [4, с. 173] показано, что любой целочисленный план задачи (2) удовлетворяет и неравенству (3)*. Оптимальный же (нецелочисленный) план задачи (2) не удовлетворяет неравенству (3)*. Добавим неравенство (3)** к условиям задачи (2), то есть:

,

а т.к. системы были эквивалентны, то задача ЛЦП запишется ((3) +(3)** ):

(4)

Задача (4) почти каноническая (=1,2,3….).

Решая задачу, получим оптимальный план

Замечание 1. Ясно, что всякое дополнительное ограничение сужает область допустимых значений и максимум может быть только меньше или равен, но никак не больше. Оптимальный нецелочисленный план при этом отсекается. Если бы при решении задачи (4) план получился бы нецелочисленным, то необходимо вновь выписать неравенство Гомори к канонической системе из последней симплексной таблицы (новой) и далее вновь решать задачу ЛП и т.д., пока план оптимальной не окажется целочисленным.

Замечание 2. Если левая часть уравнения системы имеет дробные часть равные 0, а правая часть дробная, то задача ЛЦП планов не имеет, например

. Здесь при целых значениях неизвестных никак не получится дробь , т.е. неизвестные нецелочисленны, поэтому для составления неравенства Гомори берем уравнения с дробной левой частью.

Замечание 3. Ранее, когда решали задачу ЛП оптимальный план был:

. Сейчас получили

. Если бы не применили для решения задачи ЛЦП метод Гомори, а просто округлили бы, глядя на решение задачи ЛП, например, ,; илиили,то эти планы вообще выходят за пределы множества планов, т.к. не удовлетворяют системе задачи (1), в частности, системе

Ну, а если округлить ,, то хотя это и план, ноf(x) = 39, а у нас, т.е. значенияf(x) значительно отличаются.