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

Пример

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

f= 2 x ₁+ x ₂→ min,

Приведем задачу к каноническому виду в части ограничений. Для этого вычтем из левой части неравенств фиктивные переменные х ₃ и х ₄.

Полученные в результате преобразования ограничения имеют непредпочтительный вид. Воспользуемся М-методом. Прибавим к левым частям уравнений ограничений переменные ω ₁ и ω ₂.

Целевая функция примет вид:

F=M (ω ₁+ ω ₂)→min.

Приведем целевую функцию к каноническому виду:

F ' = – M (ω ₁+ ω ₂)→mах, то есть

F ' = – Mω ₁ – M ω ₂→mах.

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

F ' = – Mω ₁ – M ω ₂→mах,

 

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

Составим симплекс-таблицу.

Таблица 6.1.

Базисные переменные	Коэффициенты при переменных	Свободные члены
				– M	– M
х 1	х 2	х 3	х 4	ω 1	ω 2
– M	ω 1			-1
– M	ω 2				-1
d	-2 М	-4 М	М	М			F '=-18 М

 

Начальное решение Х ₀={ х ₁=0, х ₂=0, х ₃=0, х ₄=0, ω ₁=6, ω ₂=12} не является оптимальным, так как среди оценок в d -строке есть отрицательные, значит решение Х ₀ можно улучшить.

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

max{|-2 M |, |-4 M |}= 4 M.

Значит, разрешающим будет второй столбец, а в базис войдет переменная х ₂.

Таблица 6.2.

Базисные переменные	Коэффициенты при переменных	Свободные члены
				– M	– M
х 1	х 2	х 3	х 4	ω 1	ω 2
– M	ω 1			-1
– M	ω 2				-1
d	-2 М	-4 М	М	М			F '=-18 М

 

 

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

.

Значит разрешающей строкой будет вторая, из базиса выйдет переменная ω ₂ и разрешающий элемент а ₂₂=3.

 

Таблица 6.3.

Базисные переменные	Коэффициенты при переменных	Свободные члены
				– M	– M
х 1	х 2	х 3	х 4	ω 1	ω 2
– M	ω 1			-1
– M	ω 2				-1
d	-2 М	-4 М	М	М			F '=-18 М

 

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

Для этого элементы разрешающей строки поделим на разрешающий элемент 3.

Таблица 6.4.

Базисные переменные	Коэффициенты при переменных	Свободные члены
				– M	– M
х 1	х 2	х 3	х 4	ω 1	ω 2
– M	ω 1			-1
– M	ω 2				-
d	-2 М	-4 М	М	М			F '=-18 М

 

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

Таблица 6.5.

Базисные переменные	Коэффициенты при переменных	Свободные члены
				– M	– M
х 1	х 2	х 3	х 4	ω 1	ω 2
– M	ω 1			-1			-
– M	ω 2				-
d	-2 М	-4 М	М	М			F '=-18 М

 

Теперь в базисе вместо переменной ω ₂ переменная х ₂ и d -оценки надо пересчитать.

Таблица 6.6.

Базисные переменные	Коэффициенты при переменных	Свободные члены
				– M	– M
х 1	х 2	х 3	х 4	ω 1	ω 2
– M	ω 1			-1			-
	x 2				-
d	–		M	–			F '=-2 М

 

Полученное решение Х ₁={ х ₁=0, х ₂=4, х ₃=0, х ₄=0, ω ₁=2, ω ₂=0} не является оптимальным, так как среди оценок в d -строке есть отрицательные, значит решение Х ₁ можно улучшить.

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

.

Значит, разрешающим будет первый столбец, а в базис войдет переменная х ₁.

 

Таблица 6.7.

Базисные переменные	Коэффициенты при переменных	Свободные члены
				– M	– M
х 1	х 2	х 3	х 4	ω 1	ω 2
– M	ω 1			-1			-
	x 2				-
d	–		M	–			F '=-2 М

 

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

min{3, 12}=3.

Значит разрешающей строкой будет первая, из базиса выйдет переменная ω ₁ и разрешающий элемент а ₁₁= .

Таблица 6.8.

Базисные переменные	Коэффициенты при переменных	Свободные члены
				– M	– M
х 1	х 2	х 3	х 4	ω 1	ω 2
– M	ω 1			-1			-
	x 2				-
d	–		M	–			F '=-2 М

 

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

Для этого элементы разрешающей строки поделим на разрешающий элемент .

Таблица 6.9.

Базисные переменные	Коэффициенты при переменных	Свободные члены
				– M	– M
х 1	х 2	х 3	х 4	ω 1	ω 2
– M	ω 1			-1,5	0,5	1,5	-0,5
	x 2				-
d	–		M	–			F '=-2 М

 

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

Таблица 6.10.

Базисные переменные	Коэффициенты при переменных	Свободные члены
				– M	– M
х 1	х 2	х 3	х 4	ω 1	ω 2
– M	ω 1			-1,5	0,5	1,5	-0,5
	x 2			0,5	-0,5	-0,5	0,5
d	–		M	–			F '=-2 М

 

В списке базисных переменных вместо ω ₁ теперь х ₁ и d -оценки также изменятся.

Таблица 6.11.

Базисные переменные	Коэффициенты при переменных	Свободные члены
				– M	– M
х 1	х 2	х 3	х 4	ω 1	ω 2
	х 1			-1,5	0,5	1,5	-0,5
	x 2			0,5	-0,5	-0,5	0,5
d					М	М	F '=0

 

Полученное решение Х ₂={ х ₁=3, х ₂=2, х ₃=0, х ₄=0, ω ₁=0, ω ₂=0} оптимально, так как среди оценок в d -строке нет отрицательных.

Подставим полученные значения переменных в изначальную целевую функцию f:

f= 2·3+2=8.

Минимальное значение целевой функции f= 8 достигается при х ₁=3, х ₂=2.

 

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

 

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

(7.1)

(7.2)

Здесь Z – множество целых чисел.

Задачи целочисленного линейного программирования решаются при помощи различных методов. Рассмотрим два из них: метод Гомори (метод отсечений) и метод ветвей и границ.

Метод Гомори (метод отсечений)

Данный метод содержит два этапа.

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

2 этап: составление дополнительного ограничения (сечения) и решение расширенной задачи симплекс-методом. Дополнительное ограничение отсекает нецелочисленные решения задачи. После решения новой расширенной задачи симплекс-методом, переходим к этапу 1 и т.д.

 

Сечение обладает следующими свойствами:

1) любое целочисленное решение удовлетворяет ему;

2) любое нецелочисленное решение задачи не удовлетворяет ему.

 

Составление сечения.

 

Пусть после 1 этапа получено решение:

X= { x ₁= b ₁, x ₂= b ₂, …, x_i = b_i, …, x_m = b_m, x_{m +1}=0, …, x_n =0},

где b_i – дробное число. Так как в решении задачи присутствует дробное число, значит переходим к этапу 2 и составляем дополнительное ограничение.

Новое ограничение (сечение) составляется на основе строки, которой соответствует дробное число b_i и будет иметь вид:

. (7.3)

Здесь α_{i j} - это дробная часть коэффициентов а_ij: α_{i j} ={ а_ij }, j = ;

β_i - это дробная часть числа b_i: β_i ={ b_i }.

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

{ а }= а – [ а ].

Например, {2,3}=2,3 – [2,3]=2,3 – 2 =0,3.

{-5,6}=-5.6 – [-5,6]=-5,6 – (-6) = 0,4.

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

Для того, чтобы привести вновь составленную систему ограничений к каноническому виду, требуется преобразовать неравенство в равенство. Введем фиктивную переменную x_{n +1}.

α_{i m +1} x _{m +1} + α_{i m +2} x _{m +2} +…+ α_{i n} x _n – x_{n +1}= β_i,

x_{n +1}≥0.

 

Замечание: Если в результате решения задачи получилось несколько дробных чисел в ответе, то требуется выбрать одно из них. Для составления отсечения выбирается число, у которого максимальна дробная часть.

 

Пример

Решить задачу:

f= 3 x ₁+2 x ₂→max

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

Базисные переменные	Коэффициенты при переменных	Свободные члены
х 1	х 2	х 3	х 4
	х 3
	х 4
d	-3	-2			f =0
	х 1		0,4	0,2
	х 4		0,6	-0,2
d		-0,8	0,6		f =12
	х 1
	х 2
d					f =

В результате решения получился следующий ответ: х ₁= , х ₂= , f = . Как видно, в ответе присутствуют два дробных числа: и . Применим метод Гомори для получения целочисленного решения.

Во-первых, выберем число с максимальной дробной частью:

{ }= и { }={ }, max{ }= .

Это означает, что сечение будет составлено на основе строки, соответствующей числу .

Во-вторых, составим ограничение. Для этого выпишем линейную комбинацию чисел из строки, соответствующей числу , и переменных х ₁, х ₂, х ₃ и х ₄:

0 х ₁+1 х ₁ х ₃ + х ₄= .

Воспользуемся формулой (7.3) и получим:

Упростим полученное отсечение, сократив на множитель:

х ₃+ х ₄≥1.

Приведем новое ограничение к каноническому виду:

– х ₃– х ₄ ≤– 1,

– х ₃– х ₄+ х ₅ =– 1, х ₅≥0.

Добавим новое сечение к системе ограничений задачи:

f= 3 x ₁+2 x ₂→max

Решив новую задачу симплекс-методом, получим целочисленное решение: х ₁=3; х ₂=2; f =13.

 

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

Метод «ветвей и границ» - это метод направленного перебора множества вариантов решений задачи.

Алгоритм метода «ветвей и границ»

1. Строятся вершины первого уровня. Для каждой вершины подсчитывается оценка нижней (верхней) границы. Ветвится вершина, которой соответствует лучшая (минимальная или максимальная) оценка.

2. Для всех вершин i -го уровня (i ≥2) подсчитывается оценка. Ветвится та из висячих вершин уровня i, i –1, i –2, …, 1, которой соответствует лучшая (минимальная или максимальная) оценка.

3. Действие п.2 повторяется до тех пор, пока не будет получено точное решение на последнем уровне, дающее значение целевой функции f*.
Если это значение f* не хуже оценок оставшихся висячих вершин, то найдено оптимальное решение.
Если это значение f* строго лучше, то оптимальное решение единственно.
Если значение целевой функции f* для последнего уровня не лучше значения оценок оставшихся висячих вершин, то переходят к п.2.

 

Рассмотрим задачу целочисленного линейного программирования (7.1) – (7.2). Пусть в результате решения задачи получили ответ

X= { x ₁= b ₁, x ₂= b ₂, …, x_i = b_i, …, x_m = b_m, x_{m +1}=0, …, x_n =0},

где b_i – дробное число.

Введем два дополнительных условия:

x_i ≤ z_i и x_i ≥ z_i +1,

где [ x_i ]= z_i.

 

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

 

Рисунок 7.1. Схематическое изображение решения метода «ветвей и границ».

 

Пример

Рассмотрим задачу из предыдущего примера, решенную методом Гомори.

f= 3 x ₁+2 x ₂→max

В результате решения получился следующий ответ: х ₁= , х ₂= , f = . Как и в методе Гомори, требуется выбрать число с максимальной дробной частью. Ранее было показано, что это х ₂. Значит ветвление будет осуществляться по переменной х ₂. Для этого определим целую часть числа Тогда

х ₂ ≤ 1 и х ₂ ≥ 2.

На основе ветвления получим две новые задачи:

Задача 1 f= 3 x 1+2 x 2→max

Задача 2 f= 3 x 1+2 x 2→max

В результате решения задач 1 и 2 получим следующие ответы:

Задача 1 х 1=3,6, х 2=1, f 1= 12,8.

Задача 2 х 1=3, х 2=2, f 2=13.

Изобразим схематически ветвление в решенной задаче.

Рисунок 7.2. Ветвление задачи.

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