Приложение 2

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

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

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

Основные методы решения задач целочисленного программирования – метод ветвей и границ и метод Гомори.

Замечания:

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

2. оптимальное целочисленное решение может существенно отличаться от оптимального непрерывного решения задачи.

Основные методы целочисленной оптимизации:

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

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

Метод Гомори

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

Шаг 1. Задачи оптимизации решаются симплекс-методом, причем в исходной задаче условие целочисленности не учитывается.

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

Шаг 3. На основе симплекс-таблицы для оптимального решения находится базисная переменная с наибольшей дробной частью и строится дополнительное ограничение («отсечение Гомори»).

, где и - это дробные части чисел а_ij и b_j.

Дробная часть числа = данное число – ближайшее целое число, не превосходящее данное.

Шаг 4. Дополнительное ограничение вводится в систему ограничений и осуществляется переход к шагу №1.

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

Некоторые особенности двойственного симплекс-метода.

1. При добавлении нового ограничения оптимальное решение становится недопустимым, так как в столбце решений появляется отрицательный элемент;

2. Ведущая строка определяется максимальным по модулю отрицательным элементом столбца решения;

3. Ведущий столбец определяется минимальным по модулю отношением элементов Е-строки к отрицательным элементам ведущей строки;

4. Ведущая строка и ведущий столбец определяют ведущий элемент и, следовательно, исключаемую и включаемую переменную;

5. Пересчет симплекс-таблиц осуществляется на основе стандартных процедур симплекс-метода.

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

Пример реализации целочисленной оптимизации на основе метода Гомори.

Формальная модель задачи:

Е=7х₁+9х₂→max

-х₁+3х₂≤6

7х₁+х₂≤35

х₁, х₂≥0

х₁, х₂ – целые числа.

Приведем задачу к ОЗЛП в базисной форме:

Е=7х₁+9х₂→max

-х₁+3х₂+х₃=6

7х₁+х₂+х₄=35

х₁, х₂, х₃, х₄≥0

х₁, х₂ – целые числа.

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

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

Базис	Х1	Х2	Х3	Х4	Решение
Е	0	0	28/11	15/11	63
Х2	0	1	7/22	1/22	7/2
Х1	1	0	-1/22	3/22	9/2

Оптимальное решение без учета условия целочисленности (х₁; х₂) = (9/2; 7/2), Е=63.

Введем дополнительные ограничения, соответствующие переменной х₂ (в данном случае – всё равно какой, т.к. ½ - дробная часть для обеих переменных).

7/22х₃+1/22х₄≥1/2

-7/22х₃-1/22х₄+х₅=-1/2

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

Базис	Х1	Х2	Х3	Х4	Х5	Решение
Е	0	0	28/11	15/11	0	63
Х2	0	1	7/22	1/22	0	7/2
Х1	1	0	-1/22	3/22	0	9/2
Х5	0	0	-7/22	-1/22	1	-1/2

Выбираем ведущую строку, столбец и элемент по правилу двойственного симплекс-метода:

а) ведущая строка определяется максимальным по модулю отрицательным элементом столбца «Решение» (-1/2);

б) ведущий столбец определяется минимальным по модулю отношением элементов Е-строки к отрицательным элементам ведущей строки (8 и 30 соотв.);

в) ведущая строка и ведущий столбец определяют ведущий элемент, исключаемую и включаемую переменную;

Пересчитываем симплекс-таблицу:

Базис	Х1	Х2	Х3	Х4	Х5	Решение
Е	0	0	0	1	8	59
Х2	0	1	0	0	1	3
Х1	1	0	0	1/7	-1/7	32/7
Х3	0	0	1	1/7	-22/7	11/7

Введем дополнительное ограничение, соответствующее переменной х₁.

1/7х₄+6/7₄≥4/7

-1/7х₄-6/7х₅+х₆=-4/7

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

Базис	Х1	Х2	Х3	Х4	Х5	Х6	Решение
Е	0	0	0	1	8	0	59
Х2	0	1	0	0	1	0	3
Х1	1	0	0	1/7	-1/7	0	32/7
Х3	0	0	1	1/7	-22/7	0	11/7
Х6	0	0	0	-1/7	-6/7	1	-4/7

Пересчитываем таблицу по правилам симплекс-метода:

Базис	Х1	Х2	Х3	Х4	Х5	Х6	Решение
Е	0	0	0	0	2	7	55
Х2	0	1	0	0	1	0	3
Х1	1	0	0	0	-4	1	4
Х3	0	0	1	0	-4	1	1
Х4	0	0	0	1	6	-7	4

Полученное оптимальное целочисленное решение: Х1=4; Х2=3; Х3=1; Х4=4. Е=55.

Метод ветвей и границ

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

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

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

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

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

а) задача не имеет допустимых решений;

б) в задаче получено целочисленное решение;

в) оценка задачи хуже, чем значение целевой функции в одном из полученных ранее целочисленных решений.

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

Пример.

Формальная модель задачи:

Е=1,2х₁+1,4х₂→max

40х₁+25х₂≤1000

35х₁+28х₂≤980

25х₁+35х₂≤875

х₁, х₂≥0

х₁, х₂ – целые числа.

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

		1
		X1 = 16,94; X2 = 12,9; E = 38,39
2										3
X2 ≤ 12 X1 = 17,5; X2 = 12; E = 37,8						X2 ≥ 13 X1 = 16,8; X2 = 13; E = 38,36
не перспективно				4					5
				X2 ≥ 13; X1 ≤ 16 X1 = 16; X2 = 13,57; E = 38,2					X2 ≥ 13; X1 ≥ 17 нет решений
	6						7
	X2 ≥ 13; X1 ≤ 16; X2 ≤ 13 X1 = 16; X2 = 13; E = 37,4						X2 ≥ 13; X1 ≤ 16; X2 ≥ 14 X1 = 15,4; X2 = 14; E = 38,08
			8					9
			X2 ≥ 13; X1 ≤ 16; X2 ≥ 14; X1 ≤ 15 X1 = 15; X2 = 14,29; E = 38,01					X2 ≥ 13; X1 ≤ 16; X2 ≥ 14; X1 ≥ 16 нет решений
10					11
X2 ≥ 13; X1 ≤ 16; X2 ≥ 14; X1 ≤ 15; X2 ≤ 14 X1 = 15; X2 = 14; E = 37,6					X2 ≥ 13; X1 ≤ 16; X2 ≥ 14; X1 ≤ 15; X2 ≥ 15 X1 = 14; X2 = 15; E = 37,8