Составление дополнительного ограничения (сечения Гомори). Целочисленные задачи линейного программирования. Метод Гомори

Метод Гомори используют для нахождения целочисленного решения в задачах линейного программирования.
Пусть найдено решение задачи ЛП: . Решение L i будет целым числом, если т.е. . {β i } - дробная часть нецелочисленного оптимального решения x i , {d i } - дробная часть не базисных переменных. Данное соотношение определяет (см. рисунок).

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

Инструкция . Выберите количество переменных и количество строк (количество ограничений), нажмите Далее. Полученное решение сохраняется в файле Word (см. пример решения методом Гомори). Дополнительно создается шаблон решения в формате Excel .

Количество переменных 2 3 4 5 6 7 8 9 10
Количество строк (количество ограничений) 2 3 4 5 6 7 8 9 10

При этом ограничения типа x i ≥ 0 не учитывайте.

Виды алгоритма Гомори

1. Первый алгоритм Гомори решения полностью целочисленных задач.
2. Второй алгоритм Гомори для частично целочисленных задач линейного программирования .

Алгоритм Гомори для полностью целочисленных задач включает в себя следующие этапы:

1. Решается задача линейного программирования без учета целочисленности.
2. Среди дробных чисел выбирается элемент с наибольшей дробной частью и составляется дополнительное ограничение.
3. Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной.
4. Полученная задача решается двойственным симплекс-методом .

Если в процессе решения в симплексной таблице появится уравнение с нецелым свободным членов b i и целыми коэффициентами a ij , то данная задача не имеет целочисленного оптимального решения.

Пример . Научно-производственное объединение «Стрела» занимается изготовлением комплектующих изделий для предприятий ВПК. При изготовлении изделий типа А и типа В используются сталь и цветные металлы. Технологический процесс также включает обработку изделий на токарных и фрезерных станках. По технологическим нормам на производство одного изделия типа А и одного изделия типа В требуется определенное количество сырья и некоторый объем станко-часов для обработки на станках в цеху. Технологические данные производственного процесса приведены в таблице.
В течение месяца цеха НПО «Стрела» располагает ограниченными ресурсами по сырью и по времени работы в производственных цехах (см. таблицу). Прибыль от реализации одного изделия типа А составляет 100 руб., а от единицы изделия типа В - 250 руб.

	Сырье		Работа в цеху, станко-час		Прибыль от реализации, руб.
	Цветные металлы	Сталь	Токарные работы	Фрезерные работы
Изделие А	10	25	41	90	100
Изделие В	30	25	90	50	250
Ресурсы	4500	6250	14100	18000

Найти оптимальный план производства для НПО «Стрела» (количество изделия типа А и типа В - целые числа), дающий наибольшую прибыль.

Решение.
Экономико-математическая модель задачи.
x 1 - план производства изделий типа А, x 2 - план производства изделий типа В,
x 1, x 2 - целые числа.
Ограничения по ресурсам
10x 1 + 30x 2 ≤ 4500
25x 1 + 25x 2 ≤ 6250
41x 1 + 90x 2 ≤ 14100
90x 1 + 50x 2 ≤ 18000
Целевая функция
100x 1 + 250x 2 → max

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

Базис	B	x 1	x 2	x 3	x 4	x 5	x 6
x 2	1450 / 11	0	1	41 / 330	0	-1 / 33	0
x 4	17500 / 11	0	0	245 / 66	1	-50 / 33	0
x 1	600 / 11	1	0	-3 / 11	0	1 / 11	0
x 6	6500	0	0	55 / 3	0	-20 / 3	1
F(X3)	422500 / 11	0	0	125 / 33	0	50 / 33	0

x 1 = 54 6 / 11 , x 2 = 131 9 / 11
F(X) = 250 131 9 / 11 + 100 54 6 / 11 = 38409 1 / 11

Полученный оптимальный план не является целочисленным, поэтому применяем метод Гомори . Наибольшая дробная часть находится во втором уравнении у переменной x 4 (10 / 11). Составляем дополнительное ограничение:
q 2 - q 21 x 1 - q 22 x 2 - q 23 x 3 - q 24 x 4 - q 25 x 5 - q 26 x 6 ≤0
q 2 = b 2 - = 1590 10 / 11 - 1590 = 10 / 11
q 2 1 = a 2 1 - = 0 - 0 = 0
q 2 2 = a 2 2 - = 0 - 0 = 0
q 2 3 = a 2 3 - = 3 47 / 66 - 3 = 47 / 66
q 2 4 = a 2 4 - = 1 - 1 = 0
q 2 5 = a 2 5 - = -1 17 / 33 + 2 = 16 / 33
q 2 6 = a 2 6 - = 0 - 0 = 0

10 / 11 - 47 / 66 x 3 - 16 / 33 x 5 ≤ 0

10 / 11 - 47 / 66 x 3 - 16 / 33 x 5 + x 7 = 0

Поскольку двойственный симплекс-метод используется для поиска минимума целевой функции, делаем преобразование F(x) = -F(X).

Базис	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	1450 / 11	0	1	41 / 330	0	-1 / 33	0	0
x 4	17500 / 11	0	0	245 / 66	1	-50 / 33	0	0
x 1	600 / 11	1	0	-3 / 11	0	1 / 11	0	0
x 6	6500	0	0	55 / 3	0	-20 / 3	1	0
x 7	-10 / 11	0	0	-47 / 66	0	-16 / 33	0	1
F(X0)	-422500 / 11	0	0	-125 / 33	0	-50 / 33	0	0

Первая итерация Гомори. 1. Проверка критерия оптимальности. План в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных выбираем наибольшее по модулю. Ведущей будет пятая строка, а переменную x 7 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует пятому столбцу, т.е. переменную x 5 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-16 / 33).

Базис	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	131 9 / 11	0	1	41 / 330	0	-1 / 33	0	0
x 4	1590 10 / 11	0	0	3 47 / 66	1	-1 17 / 33	0	0
x 1	54 6 / 11	1	0	-3 / 11	0	1 / 11	0	0
x 6	6500	0	0	18 1 / 3	0	-6 2 / 3	1	0
x 7	-10 / 11	0	0	-47 / 66	0	-16 / 33	0	1
F(X0)	-38409 1 / 11	0	0	-3 26 / 33	0	-1 17 / 33	0	0
θ		-	-	-3 26 / 33: (-47 / 66) = 5 15 / 47	-	-1 17 / 33: (-16 / 33) = 3 1 / 8	-	-

4. Пересчет симплекс-таблицы выполняем с помощью метода Жордано-Гаусса.

Базис	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 2	1055 / 8	0	1	27 / 160	0	0	0	-1 / 16
x 4	6375 / 4	0	0	95 / 16	1	0	0	-25 / 8
x 1	435 / 8	1	0	-13 / 32	0	0	0	3 / 16
x 6	13025 / 2	0	0	225 / 8	0	0	1	-55 / 4
x 5	15 / 8	0	0	47 / 32	0	1	0	-33 / 16
F(X0)	-153625 / 4	0	0	-25 / 16	0	0	0	-25 / 8

В полученном оптимальном плане присутствуют дробные числа. По первому уравнению с переменной x 2 , получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 7 / 8 , составляем дополнительное ограничение:
q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 ≤0
q 1 = b 1 - = 131 7 / 8 - 131 = 7 / 8


q 1 3 = a 1 3 - = 27 / 160 - 0 = 27 / 160



q 1 7 = a 1 7 - = -1 / 16 + 1 = 15 / 16
Дополнительное ограничение имеет вид:
7 / 8 - 27 / 160 x 3 - 15 / 16 x 7 ≤ 0
Преобразуем полученное неравенство в уравнение:
7 / 8 - 27 / 160 x 3 - 15 / 16 x 7 + x 8 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	1055 / 8	0	1	27 / 160	0	0	0	-1 / 16	0
x 4	6375 / 4	0	0	95 / 16	1	0	0	-25 / 8	0
x 1	435 / 8	1	0	-13 / 32	0	0	0	3 / 16	0
x 6	13025 / 2	0	0	225 / 8	0	0	1	-55 / 4	0
x 5	15 / 8	0	0	47 / 32	0	1	0	-33 / 16	0
x 8	-7 / 8	0	0	-27 / 160	0	0	0	-15 / 16	1
F(X0)	-153625 / 4	0	0	-25 / 16	0	0	0	-25 / 8	0

Вторая итерация Гомрои. 1. Проверка критерия оптимальности. План в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных наибольшей по модулю является переменная x 8 . Ее следует вывести из базиса.
3. Минимальное значение θ соответствует седьмому столбцу, т.е. переменную x 7 необходимо ввести в базис.

Базис	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	131 7 / 8	0	1	27 / 160	0	0	0	-1 / 16	0
x 4	1593 3 / 4	0	0	5 15 / 16	1	0	0	-3 1 / 8	0
x 1	54 3 / 8	1	0	-13 / 32	0	0	0	3 / 16	0
x 6	6512 1 / 2	0	0	28 1 / 8	0	0	1	-13 3 / 4	0
x 5	1 7 / 8	0	0	1 15 / 32	0	1	0	-2 1 / 16	0
x 8	-7 / 8	0	0	-27 / 160	0	0	0	-15 / 16	1
F(X0)	-38406 1 / 4	0	0	-1 9 / 16	0	0	0	-3 1 / 8	0
θ		-	-	-1 9 / 16: (-27 / 160) = 9 7 / 27	-	-	-	-3 1 / 8: (-15 / 16) = 3 1 / 3	-

4. Выполняем преобразование Новых отсечений Гомори.

Базис	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
x 2	1979 / 15	0	1	9 / 50	0	0	0	0	-1 / 15
x 4	4790 / 3	0	0	13 / 2	1	0	0	0	-10 / 3
x 1	271 / 5	1	0	-11 / 25	0	0	0	0	1 / 5
x 6	19576 / 3	0	0	153 / 5	0	0	1	0	-44 / 3
x 5	19 / 5	0	0	46 / 25	0	1	0	0	-11 / 5
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-16 / 15
F(X0)	-115210 / 3	0	0	-1	0	0	0	0	-10 / 3

В оптимальном плане присутствуют дробные числа. Наибольшая дробная часть у переменной x 2 (14 / 15). Составляем дополнительное ограничение: q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 - q 18 x 8 ≤0
q 1 = b 1 - = 131 14 / 15 - 131 = 14 / 15
q 1 1 = a 1 1 - = 0 - 0 = 0
q 1 2 = a 1 2 - = 1 - 1 = 0
q 1 3 = a 1 3 - = 9 / 50 - 0 = 9 / 50
q 1 4 = a 1 4 - = 0 - 0 = 0
q 1 5 = a 1 5 - = 0 - 0 = 0
q 1 6 = a 1 6 - = 0 - 0 = 0
q 1 7 = a 1 7 - = 0 - 0 = 0
q 1 8 = a 1 8 - = -1 / 15 + 1 = 14 / 15
Дополнительное ограничение имеет вид:
14 / 15 - 9 / 50 x 3 - 14 / 15 x 8 ≤ 0
Преобразуем полученное неравенство в уравнение:
14 / 15 - 9 / 50 x 3 - 14 / 15 x 8 + x 9 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	1979 / 15	0	1	9 / 50	0	0	0	0	-1 / 15	0
x 4	4790 / 3	0	0	13 / 2	1	0	0	0	-10 / 3	0
x 1	271 / 5	1	0	-11 / 25	0	0	0	0	1 / 5	0
x 6	19576 / 3	0	0	153 / 5	0	0	1	0	-44 / 3	0
x 5	19 / 5	0	0	46 / 25	0	1	0	0	-11 / 5	0
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-16 / 15	0
x 9	-14 / 15	0	0	-9 / 50	0	0	0	0	-14 / 15	1
F(X0)	-115210 / 3	0	0	-1	0	0	0	0	-10 / 3	0

Третья итерация методом Гомори. Переменную x 9 следует вывести из базиса. Минимальное значение θ соответствует восьмому столбцу, т.е. переменную x 8 необходимо ввести в базис.

Базис	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	131 14 / 15	0	1	9 / 50	0	0	0	0	-1 / 15	0
x 4	1596 2 / 3	0	0	6 1 / 2	1	0	0	0	-3 1 / 3	0
x 1	54 1 / 5	1	0	-11 / 25	0	0	0	0	1 / 5	0
x 6	6525 1 / 3	0	0	30 3 / 5	0	0	1	0	-14 2 / 3	0
x 5	3 4 / 5	0	0	1 21 / 25	0	1	0	0	-2 1 / 5	0
x 7	14 / 15	0	0	9 / 50	0	0	0	1	-1 1 / 15	0
x 9	-14 / 15	0	0	-9 / 50	0	0	0	0	-14 / 15	1
F(X0)	-38403 1 / 3	0	0	-1	0	0	0	0	-3 1 / 3	0
θ		-	-	-1: (-9 / 50) = 5 5 / 9	-	-	-	-	-3 1 / 3: (-14 / 15) = 3 4 / 7	-

4. Выполняем преобразование.

Базис	B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9
x 2	132	0	1	27 / 140	0	0	0	0	0	-1 / 14
x 4	1600	0	0	50 / 7	1	0	0	0	0	-25 / 7
x 1	54	1	0	-67 / 140	0	0	0	0	0	3 / 14
x 6	6540	0	0	234 / 7	0	0	1	0	0	-110 / 7
x 5	6	0	0	317 / 140	0	1	0	0	0	-33 / 14
x 7	2	0	0	27 / 70	0	0	0	1	0	-8 / 7
x 8	1	0	0	27 / 140	0	0	0	0	1	-15 / 14
F(X0)	-38400	0	0	-5 / 14	0	0	0	0	0	-25 / 7

Решение получилось целочисленным. Оптимальный целочисленный план можно записать так: x 1 = 54, x 2 = 132. F(X) = 38400

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

Задача линейного целочисленного программирования формулируется следующим образом: найти такое решение (план) i, при котором линейная функция

принимает максимальное или минимальное значение при ограничениях

(8.2)

(8.3)

– целые числа. (8.4)

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

Для решения задач линейного целочисленного программирования используется ряд методов. Самый простой из них – обычный метод линейного программирования. В случае если компоненты оптимального решения оказываются нецелочисленными, их округляют до ближайших целых чисел. Этот метод применяют тогда, когда отдельная единица совокупности составляет малую часть объема всей совокупности. В противном случае округление может привести к далекому от оптимального целочисленному решению, поэтому используют специально разработанные методы.

Методы целочисленной оптимизации можно разделить на три основные группы: а) методы отсечения; б) комбинаторные методы; в) приближенные методы. Остановимся подробнее на методах отсечения.

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

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

• оно должно быть линейным;
• должно отсекать найденный оптимальный нецелочисленный план;
• не должно отсекать ни одного целочисленного плана.

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

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

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

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

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

(8.5)

так что оптимальным решением задачи (8.1)-(8.3) является i, в котором, например, β; – нецелая компонента. В этом случае можно доказать, что неравенство, сформированное по i- му уравнению системы (8.5), обладает всеми свойствами правильного отсечения.

Для решения задачи целочисленного линейного программирования (8.1)-(8.4) методом Гомори используется следующий алгоритм.

• 1. Симплексным методом решить задачу (8.1)-(8.3) без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования (8.1)-(8.4). Если первая задача (8.1)-(8.3) неразрешима (т.е. нс имеет конечного оптимума или условия ее противоречивы), то и вторая задача (8.1)-(8.4) также неразрешима.
• 2. Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и по соответствующему уравнению системы (8.5) сформировать правильное отсечение (8.6).
• 3. Неравенство (8.6) введением дополнительной неотрицательной целочисленной переменной преобразовать в равносильное уравнение и включить его в систему ограничений (8.2).
• 4. Полученную расширенную задачу решить симплексным методом. Если найденный оптимальный план будет целочисленным, то задача целочисленного программирования (8.1)–(8.4) решена. В противном случае вернуться к п. 2 алгоритма.

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

1 В неравенстве (8.6) присутствует символ { }, означающий дробную часть числа. Целой частью числа а называется наибольшее целое число [в], не превосходящее а, дробной частью числа – число {а}, равное разности между этим числом и его целой частью, т.е. {а} = а-[в].

Например, для (обратите внимание, именно -3, а не -2) и

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

8.1. Для приобретения оборудования по сортировке зерна фермер выделяет 34 ден. ед. Оборудование должно быть размещено на площади, не превышающей 60 кв. м. Фермер может заказать оборудование двух видов: менее мощные машины типа А стоимостью 3 ден. ед., требующие производственную площадь 3 кв. м (с учетом проходов), и производительностью за смену 2 т зерна, и более мощные машины типа В стоимостью 4 ден. ед., занимающие площадь 5 кв. м, и производительностью за смену 3 т сортового зерна.

Требуется составить оптимальный план приобретения оборудования, обеспечивающий максимальную общую производительность при условии, что фермер может приобрести не более 8 машин типа В.

Решение. Обозначим черезколичество машин соответственно типа А и В, через Z – общую производительность. Тогда математическая модель задачи примет вид

(!!!8.8)

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

(8.2)

– целые числа. (8.4)

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

(8.5)

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

На рис. 8.2 OKLM – область допустимых решений задачи (8.Г)–(8.3"), ограниченная прямыми (1), (2), (3) и осями координат; L (2/3; 8) – точка оптимального, но нецелочисленного решения задачи (8.1")–(8.3"); (4) – прямая, отсекающая это нецелочисленное решение; OKNM – область допустимых решений расширенной задачи (8.1")–(8.3"), (8.6"); N(2; 7) – точка оптимального целочисленного решения.

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

Первое базисное решение– допусти

мое. Соответствующее значение линейной функции

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

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

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

II шаг. Основные переменные х 2, х 3, х 4.

Неосновные переменные.г, ху

После преобразований получим

Переводим в основные переменнуюа в неосновные х4.

III шаг. Основные переменные х, х 2, х 3.

Неосновные переменные х4, х5.

После преобразований получим

Базисное решение X., оптимально для задачи (8.1")–(8.3") (), так как в выражении линейной функции

отсутствуют неосновные переменные с положительными коэффициентами.

Однако решение Х 3 не удовлетворяет условию целочисленности (8.4") По первому уравнению с переменной х, получившей нецелочисленное значение в оптимальном решении (2/3), составляем дополнительное ограничение (8.6):

Обращаем внимание на то, что согласно (8.5) и (8.6) берем дробную часть свободного члена с тем же знаком, который он имеет в уравнении, а дробные части коэффициентов при неосновных переменных х 4 и х- – с противоположными знаками.

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

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

(8.6")

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

(8.7")

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

IV шаг. Основные переменные x v х 2, х3, χβ.

Неосновные переменные х4, х5.

Базисное решение – недопусти

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

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

V шаг. Основные переменные х, х2, х3, х5.

Неосновные переменные х4, х6.

Получим после преобразований

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

Итак, Zmax = 25 при оптимальном целочисленном решении X* = Х 5 = (2; 7; 19; 0; 1; 0), т.е. максимальную производительность 25 т сортового зерна за смену можно получить приобретением 2 машин типа Л и 7 машин типа В при этом незанятая площадь помещения составит 19 кв. м, остатки денежных средств из выделенных равны нулю, в резерве для покупки – 1 машина типа В (шестая компонента содержательного смысла не имеет).

Замечание. Для геометрической интерпретации на плоскости Ох,х2 (см. рис. 8.2) отсечения (8.6") необходимо входящие в него переменные х 4 и х- выразить через переменные х, и х2. Получим (см. 2-е и 3-е уравнения системы ограничений (8.5"))

• (см. отсечение прямой (4) на рис. 8.2).
• 8.2. Имеется достаточно большое количество бревен длиной 3 м. Бревна следует распилить на заготовки двух видов: длиной 1,2 и 0,9 м, причем заготовок каждого вида должно быть получено не менее 50 и 81 шт. соответственно. Каждое бревно можно распилить на указанные заготовки несколькими способами: 1) на 2 заготовки но 1,2 м; 2) па 1 заготовку 1,2 м и 2 заготовки по 0,9 м; 3) на 3 заготовки по 0,9 м. Найти число бревен, распиливаемых каждым способом, с тем чтобы заготовок любого вида было получено из наименьшего числа бревен.

Решение. Обозначим через х {} х2, х3 число бревен, распиливаемых соответственно 1, 2 и 3-м способами. Из них можно получить 2xj +х2 заготовок по 1,2 м и 2х х +3х2 заготовок по 0,9 м. Общее количество бревен обозначим Z. Тогда математическая модель задачи примет вид

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

Введя дополнительные переменныепри

ведем систему неравенств к равносильной системе уравнений:

(8.5")

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

III шаг. Основные переменные x v х 2.

Неосновные переменные х у х А, х 5.

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

Получилось, что две компоненты оптимального решения не удовлетворяют условию целочисленности (8.4"), причем бо́льшую целую часть имеет компонента х 2. В соответствии с ∏. 2 алгоритма решения задачи целочисленного программирования (см. с. 166) по второму уравнению, содержащему эту переменную х 2, составляем дополнительное ограничение (8.6):

Найдем дробные части

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

(8.6")

Введя дополнительную переменнуюполучим

равносильное неравенству (8.6") уравнение:

(8.7")

Выразим из (8.7") дополнительную переменную х6 и полученное уравнение введем в систему ограничений, которую мы имели на последнем, III, шаге решения задачи (8.1")– (8.3") (без условия целочисленности).

IV шаг. Основные переменные х {, х у х 6.

Неосновные переменные х 3, х4, х 5.

Решая эту расширенную задачу симплексным методом (предлагаем студентам выполнить самостоятельно), получим следующее.

V шаг. Основные переменные х); х 2, х3.

Неосновные переменные х4, х5, хб.

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

Полученное оптимальное решение расширенной задачи (8.1")–(8.3"), (8.6") вновь не удовлетворяет условию целочисленности (8.4"). По первому уравнению с переменной Xj, получившей нецелочисленное значение в оптимальном

решении (), еоставляем второе дополнительное ограни

чение (8.6):

которое приводим к виду

С помощью дополнительной переменнойприво

дим это неравенство к равносильному уравнению, которое включаем в систему ограничений, полученную на последнем, V, шаге решения расширенной задачи (8. Г")–(8.3"), (8.6") симплексным методом.

VI шаг. Основные переменные x v х 2, х у х т

Неосновные переменные х 4, X-, х 6.

Опуская дальнейшее решение задачи симплексным методом (предлагаем сделать это самим студентам), на заключительном, VII, шаге получим.

VII шаг. Основные переменные x v х т х3, х г

Неосновные переменные x v х 6, х т

Так как в выражении линейной функции нет неосновных переменных с отрицательными коэффициентами, то Х 7 – оптимальное целочисленное решение исходной задачи.

Следует обратить внимание на то, что в полученном выражении линейной функции Z отсутствуют неосновные переменные х Г) и х 6. Это означает, что, вообще говоря, существует бесконечное множество оптимальных решений (любых, не обязательно целочисленных), при которых Z" = Zmjn = 46. Эти решения получаются при значении неосновной переменной х 7 (входящей в выражение для Z), равной нулю (т.е. при х 7 = 0), и при любых значениях неосновных переменных ж5 и х 6 (не входящих в выражение для Z), которые "позволяет" принять система ограничений: 0<лг5 х 5 ≤ 1 и 0 < x (i ≤ 1. Но в силу условия целочисленности переменные х- и х (> могут принять только значения 0 или 1. Поэтому задача будет иметь четыре целочисленных оптимальных решения, когда х. и *6 в любой комбинации принимают значения 0 или 1, а х 7 = 0. Подставляя эти значения в систему ограничений на VII шаге, найдем эти оптимальные решения:

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

Итак, Zmin=46 при оптимальных целочисленных решениях (5; 41; 0), (6; 39; 1), (7; 36; 3), (6; 38; 2). При записи оптимальных решений мы оставили лишь первые три компоненты, выражающие число бревен, распиливаемых соответственно 1, 2 и 3-м способами, и исключили последние четыре компоненты, не имеющие смыслового значения.

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

• Можно убедиться, что при этом решение задачи короче.

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

В некоторых случаях допускается округление результатов. Например, если в оптимальном плане предусмотрено, что следует произвести 499683,3 автомашины, то экономически обосновано округление результата до 499683 или даже до 500000.

Существуют однако задачи, в которых подобное округление может создать большую ошибку. Например, если в оптимальном плане предусмотрено, что следует построить 0,67 заводов, то формальное округление до 0 или 1 недопустимо.

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

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

найти максимум функции цели (линейной формы)

при системе ограничений

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

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

Метод Гомори решения задач целочисленного программирования

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

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

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

Теперь о том, как составлять упомянутое дополнительное условие. Оно, дополнительное условие, получается из одного из уравений системы ограничений из коэффициентов при неизвестных и самих неизвестных по формуле

, где в фигурных скобках - дробные части соответственно свободного члена и коэффициентов при неизвестных.

Например, из симплексной таблицы получаем такое уравнение:

.

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

Аналогично получаем дробные части коэффициентов при неизвестных:

(при x 3 ),

(при x 4 ).

А общее правило нахождения дробных частей таково: целой частью вещественного числа a называется самое большое целое число [a ] , не превыщающее a ; дробной частью вещественного числа a называется разность {a } = a - [a ] самого числа a и его целой части [a ] .

.

В нашем примере по приведённой выше формуле получается следующее уравнение:

.

Пример 1. Решить методом Гомори следующую задачу целочисленного программирования. Найти максимум целевой функции

при системе ограничений

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

Дополнительные неизвестные x 3 и x 4 примем за базисные. Выразим базисные неизвестные и функцию цели через неосновные переменные:

Из коэффициентов составим симплексную таблицу:

Составляем следующие таблицы до получения оптимального плана:

Таблица 3
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
С	65/7	10/7	1/7	1/2

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

Первое уравнение на основании таблицы запишется так:

.

Определив дробные части коэффициентов при неизвестных и свободных членов, получаем следующее дополнительное условие:

или, введя добавочную переменную ,

.

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

Таблица 4
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
X5	-5/7	-4/7	-6/7
С	65/7	10/7	1/7	1/2

Совершаем шаг симплекс-метода и получаем таблицу:

Таблица 5
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
С	55/6	4/3	1/6	-1/7

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

.

Составляем следующую таблицу:

Таблица 6
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
X6	-5/6	-2/3	-5/6
С	55/6	4/3	1/6	-1/7

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

Таблица 7
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X3	X6
X1	3	4/5	-1/5	1/6
X2	0	-3/5	2/5	-1/3
X4	2	8/5	-7/5	7/6
X5	1	4/5	-6/5
С	9	6/5	1/5	-1/6

Так как найденный оптимальный план удовлетворяет условию целочисленности, задача целочисленного программирования решена. Координаты x 5 и x 6 можно не учитывать, так как начальные условия задачи содержит лишь четыре неизвестные. Поэтому окончательный оптимальный план запишется так:

,

а максимум функции цели равен 9.

Метод ветвей и границ решения задач целочисленного программирования

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

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

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

Как метод ветвей и границ позволяет уточнить границы допустимых значений неизвестных?

Сначала решается, допустим, симплекс-методом задача линейного программирования, соответствующая задаче целочисленного программирования. Пусть найден оптимальный план в этой задаче и значением какой-либо его координаты является дробное число. Тогда потребуется составить две новые задачи линейного программирования. Как это сделать?

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

.

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

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

• оптимальный план не является целочисленным,
• оптимальный план является целочисленным,
• задача не имеет решений.

Лишь в первом случае возможно "ответвление" новых задач способом, показанным выше. Во втором и третьем случае "ветвление" прекращается.

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

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

Согласно алгоритму решения задачи целочисленного программирования методом ветвей и границ, на каждой p -й итерации требуется сделать 4 шага.

Пример 2. Решить методом ветвей и границ следующую задачу целочисленного программирования. Найти максимум целевой функции

при системе ограничений

Решение. Допустим, что заданы или определены следующие границы оптимальных значений неизвестных:

.

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

В списке решаемых задач - 1-я задача:

Итерация 1.

Шаг 1. С помощью симплекс-метода получено решение 1-й задачи:

Так как найденный план не является целочисленным, следует шаг 4.

Шаг 4. Так как оптимальный план имеет дробную координату 1,2, то и . Применяя границы значений неизвестных 1-й задачи, получаем новые задачи. Во 2-й задаче нижней границей для является , а в 3-й задаче верхней границей для является .

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

КУЗБАССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра вычислительной техники и информационных технологий

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ГОМОРИ

Методические указания и задания к практическим занятиям по курсу

«Экономико-математические методы» для студентов экономических специальностей

Составитель Н.Ю.Коломарова

Утверждены на заседании кафедры Протокол № 5 от 30.11.99

Электронная копия находится в библиотеке главного корпуса КузГТУ

Кемерово 2000

1. ПОСТАНОВКА ЗАДАЧИ

Существует ряд задач оптимального планирования, в которых переменные могут принимать лишь целочисленные значения. Такие задачи связаны с определением количества единиц неделимой продукции, числа станков при загрузке оборудования, численности работников в структурных подразделениях предприятия и т.д. Достаточно часто возникают задачи с так называемыми булевыми переменными, решениями которых являются суждения типа «да-нет». Если функция и ограничения в таких задачах линейны, то мы говорим о задаче линейного целочисленного программирования.

Задача линейного целочисленного программирования формулиру-

ется следующим образом: найти такое решение (план)

Х = (x1 , x2 , ..., xn ),

принимает максимальное или минимальное значение при ограничениях

2. МЕТОД ГОМОРИ

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

Рассмотрим алгоритм решения задачи линейного целочисленного программирования этим методом.

1. Решаем задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования.

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

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

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

Для построения ограничения выбираем компоненту оптимального плана с наибольшей дробной частью и по соответствующей этой компоненте k -й строке симплексной таблицы записываем ограничение Гомори.

		f k = ∑	f kj x j − S * ,S * ≥ 0 ,
где f k	Xj - ;
	Zkj - ;
		Новая переменная;
Ближайшее целое, не превосходящееx j иz kj соответст-
		Составленное ограничение добавляем к имеющимся в сим-

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

	вектор, для которого величина				∆ j		минимальна. И если для этого век-
					f kj
	тора величина θ = min		получается по дополнительной строке, то в
	z ij> 0

следующей симплексной таблице будет получен опорный план. Если же величина θ не соответствует дополнительной строке, то необходимо

переходить к М-задаче (вводить искусственную переменную в ограничение Гомори).

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

Замечания:

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

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

3. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ МЕТОДОМ ГОМОРИ

Задача: Для приобретения нового оборудования предприятие выделяет 19 ден.ед. Оборудование должно быть размещено на площади, не превышающей 16 кв.м. Предприятие может заказать оборудование двух видов: машины типа «А» стоимостью 2 ден.ед., требующие производственную площадь 4 кв.м и обеспечивающие производительность за смену 8 т продукции, и машины типа «В» стоимостью 5 ден.ед., занимающие площадь 1 кв.м и обеспечивающие производительность за смену 6 т продукции.

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

Решение: Обозначим черезx 1 ,x 2 количество машин соответственно типа «А» и «В», черезL - их общую производительность. Тогда математическая модель задачи:

max L = 8 x1 +6 x2

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

2x 1	5x 2
4x 1
x 1≥		0, x2 ≥ 0

x1 , x2 - целые числа

Решаем задачу симплексным методом без учета целочисленности.

	∆ j
	∆ j
	∆ j

Получен оптимальный нецелочисленный план Х опт = (61/18;22/9).

L max = 376/9.

Т.к. у компоненты плана х 2 максимальная дробная часть: max(4/9;7/18) = 4/9, то дополнительное ограничение записываем по первой строке.

22/9 - = (2/9 - )x 3 + (-1/9 - [-1/9])x 4 -S 1 , S 1 ≥0 22/9 - 2 = (2/9 - 0)x 3 + (-1/9 - (-1))x 4 -S 1 , S 1 ≥0

4/9 = 2/9x3 + 8/9x4 - S1 , S1 ≥ 0 - первое ограничение Гомори

Составленное ограничение дописываем к имеющимся в симплексной таблице.

После построения дополнительного ограничения имеем новую задачу линейного программирования, в которой 3 ограничения. Для получения опорного плана этой задачи необходимо найти третий базис-

ный вектор. Для этого определяем: min
	f kj

базис вводим вектор х 4 .							4 / 9
Рассчитываем величину θ =
	z ij> 0						8 / 9

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

	∆ j

Найденный план оптимален, но нецелочисленный. Строим новое ограничение Гомори.

Т.к. максимальная дробная часть среди компонент плана равна 1/2, записываем дополнительное ограничение по первой строке (можно и по третьей).

5/2 - = (1/4 - )x 3 + (-1/8 - [-1/8])S 1 -S 2 , S 2 ≥0

1/2 = 1/4x3 + 7/8S1 - S2 , S2 ≥ 0 - второе ограничение Гомори

Это ограничение добавляем в последнюю симплексную таблицу.

Получили задачу, в которой 4 ограничения, следовательно, в базисе должно быть 4 единичных вектора.

								2 . Можно

ввести либо x 3 , либоS 1 . Введем векторS 1 .

1/ 2

4 / 7

соответствует дополнительному

7 / 8

ограничению.

∆ j

Получаем новый оптимальный нецелочисленный план. Учитывая замечание 1, вычеркиваем строку и столбец, соответствующие пере-

менной S 1 .

В полученном плане максимальную дробную часть имеет компонента х 2 , поэтому записываем дополнительное ограничение по первой строке.

	4/7 = 2/7x3 + 6/7S2 - S3 , S3 ≥ 0	Третье ограничение Гомори.
	Определяем вектор, вводимый в базис:

вектор х 3 . Минимальное значениеθ = 2, что соответствует дополнительной строке.

После проведения очередных симплексных преобразований получили:

	∆ j

План Х 5 - оптимальный нецелочисленный. Дополнительное ограничение запишем по второй строке:

1/2 = 1/4S3 - S4 , S4 ≥ 0

Четвертое ограничение Гомори.

Т.к. базисной компонентой может быть S 3 , определяем величину

0. Минимальное значение θ получилось по 3

строке, а не по строке Гомори, следовательно, переходим к М-задаче:

введем дополнительную переменную х 5							в ограничение Гомори.
С5 ’	Б5 ’	Х5 ’
	∆ j

∆ j

∆ j

Дробная часть = max(1/3; 2/3) = 2/3

дополнительное ограниче-

ние записываем по второй строке.

2/3 = 1/3х4 + 2/3S4 - S5

S5 ≥

Пятое ограничение Гомори.

16 / 3

2 вводим х 4 .

Вектор, вводимый в базис: min

2 / 3

θ =

соответствует строке Гомори.

∆ j

План Х 8 = (3; 2; 3; 2) - оптимальный целочисленный.L max = 36.

Экономическая интерпретация: согласно полученному решению предприятию необходимо закупить 3 машины типа «А» и 2 машины типа «В». При этом будет достигнута максимальная производительность работы оборудования, равная 36 т продукции за смену. Полученную экономию денежных средств в размере 3 ден.ед. можно будет направить на какие-либо иные цели, например, на премирование рабочих, которые будут заниматься отладкой полученного оборудования. На излишнюю площадь в 2 кв.м можно поставить ящик с цветами.

Геометрическая интерпретация метода Гомори: строим множе-

ство планов (см. рисунок). В точке 1 - оптимальный нецелочисленный план.

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

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

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

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

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

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

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

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

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

(6.56)

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

сформированное по 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.53).

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

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

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

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

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

не приводит, вообще говоря, к полностью целочисленной задаче в каноническом виде, так как в преобразованных ограничениях (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.19).

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

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

I шаг

	х 1	х 2
х 3
х 4
х 5

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

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

,

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

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

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

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

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

	х 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

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

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

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

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

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

Введя дополнительную целочисленную переменную х 6 ≥ 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

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

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

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

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

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

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

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

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