П.1. Постановка задачи целочисленного линейного программирования

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

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

Найти минимальное (максимальное) значение линейной функции

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

(i = 1, 2, …, m),

x_j ³ 0 (j = 1, 2, …, n),

x_j – целые числа.

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

П.2. Методы отсечения.

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

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

Х2       Х1

Рис. 7.1.

С помощью методов линейного программирования находится решение X₁(x₁, …, x_n), при котором целевая функция достигает оптимального значения. Если вектор X₁ нецелочисленный, то вводится новое линейное ограничение, которое отсекает от многоугольника ограничений найденное решение, но оставляет все целочисленные решения. Вновь ищется оптимальное решение, если оно вновь оказывается целочисленным, то процесс продолжается далее.

Остановимся подробнее на методе, предложенном американским математиком Гомори. Рассмотрим его на примере.

 

П р и м е р 7.1. Методом Гомори решить следующую задачу. Для приобретения оборудования по переработке молока фермер выделяет 18 ден. ед. Оборудование должно быть размещено на территории, не превышающей 6 соток. Можно заказать оборудование двух видов А и В. Единица оборудования А стоит 4 ден. ед. и занимает площадь в 1 сотку. Ее использование приносит доход в 3 ден. ед. Единица оборудования В стоит 6 ден. ед., занимет площадь 2 сотки и приносит доход 2 ден. ед.

Фермер не может приобрести более 5 ед. оборудования А и более 4 ед. оборудования В.

Решение. Экономико-математическая модель сформулированной задачи имеет вид:

Z = 6 x₁ + 2 x₂ ® max,

(7.1)

где х₁, х₂ – число единиц оборудования А и В соответственно.

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

Таблица 7.1.

Базис	Сбазиса	А0	С1=6	С2=2	С3=0	С4=0	С5=0	С6=0
А1	А2	А3	А4	А5	А6
А3
А4
А5
А6
Zj – Cj		– 6	– 2
А1		4, 5		3/4	1/4
А4		1, 5		5/4	– 1/4
А5		0, 5		–3/4	– 1/4
А6				1/4
Zj – Cj			5/4	3/2

 

Обозначим [x_i] и [x_ij] целые части чисел x_i и x_ij соответственно. Величины

q_i = x_i – [x_i] и q_ij = x_ij – [x_ij]

неотрицательны.

Можно показать, что справедливо неравенство

q_i1 x₁ + q_i2 x₂ + … + q_in x_n – q_i ³ 0. (7.2)

В случае, если решение задачи не целочисленное, неравенство (7.2) используется в качестве дополнительного ограничения. Для этого неравенство (7.2) необходимо добавить вспомогательную переменную x_n+1.

В нашем случае [x₁] = [4, 5] = 4,

q₁ = x₁ – [x₁] = 0, 5;

q₁₁ = 0;

q₁₂ = 3/4;

q₁₃ = 1/4;

q₁₄ = q₁₅ = q₁₆ = 0.

Значит,

Замечание 7.1. Если в плане несколько дробных значений x_i, выбирают то, значение q_i для которого максимальное.

Условия новой задачи будут выглядеть следующим образом

Z = 6 x₁ + 2 x₂ ® max,

(7.3)

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

Таблица 7.2.

Базис	Сбазиса	А0	С1=6	С2=2	С3=0	С4=0	С5=0	С6=0	С7=0
А1	А2	А3	А4	А5	А6	А7
-	-
А4
А5
А6
-	-	1/2		3/4	1/4				– 1
-	-
А4
А5
А6
А3									– 4
А1
А4
А5
А6
А3									– 4
Zj – Cj			– 1
А1
А4		2/3			– 2/3				8/3
А5
А6		10/3							4/3
А2		2/3			1/3				– 4/3
Zj – Cj	25			1/3				10/3

 

Полученное решение задачи (7.3) Z_max = 12 и (4; 2/3; 0; 2/3; 1; 10/3; 0) не подходит, поскольку х₂ – дробное.

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

q₂ = 2/3, q₆₁ = q₆₂ = q₆₄ = q₆₅ = q₆₆ = 0, q₆₃ = 1/3, q₆₇ = 2/3.

Новое ограничение имеет вид

1/3 х₃ + 2/3 х₇ – х₈ = 2/3.

Сформулируем новую задачу

Z = 6 x₁ + 2 x₂ ® max,

(7.4)

Решая задачу (7.4) симплексным методом получим Z_max = 24, (4; 0; 2; 2; 1; 4; 0; 0). В плане нет дробных компонент.

Задача решена.

 

П.3. Комбинаторные методы

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

 

 

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

Z = 6 x₁ + 2 x₂ ® max,

(7.5)

Решение. Решая исходную задачу (7.5), получим

= 27 у.е.

Данная задача не обладает целочисленным планом, поскольку х₁ – дробное. Так как оптимальное целочисленное решение не должно содержать полосу 4 < x₁ < 5, исключаем ее. Получим две новые задачи:

II	III
Z(2) = 6 x1 + 2 x2 ® max,	Z(3) = 6 x1 + 2 x2 ® max,

 

Условия задачи III противоречивы, поэтому исключим ее из дальнейшего рассмотрения.

Решая задачу II, получим

у.е.

Разобьем задачу II на две задачи линейного программирования IV и V, исключив полосу 0 < x₂ < 1.

 

 

IV	V
Z(4) = 6 x1 + 2 x2 ® max,	Z(5) = 6 x1 + 2 x2 ® max,

 

Решая задачу IV, получим = 24 у.е., (4; 0).

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

Решаем задачу V. Получаем = 24, 5 у.е., (3, 75; 1). Решение нецелочисленное. Исключаем из рассмотрения полосу 3 < x₁ < 4. Получаем две новые задачи:

VI	VII
Z(4) = 6 x1 + 2 x2 ® max,	Z(5) = 6 x1 + 2 x2 ® max,

 

Условия задачи VII являются противоречивыми.

Решая задачу VI, получим = 21 у.е., (3; 1, 5). Несмотря на то, что решение задачи VI нецелочисленное, нет смысла продолжать ее решение, поскольку уже был получен результат = 24 > . Решение закончено.

Z_max (4; 0) = 24 у.е.

 

Примеры для самостоятельного решения

1. Для изготовления комплектов из трех брусьев имеются две партии бревен. Первая партия содержит 99 бревен длиной 6, 6 м каждое, вторая – 60 бревен по 4, 8 м каждое. Комплект состоит из двух брусьев длиной 2, 2 м и одного длиной 1, 3 м.

Составить план распила бревен, чтобы получить максимальное число комплектов.

 

2. Z = 3x₁ + 2x₂ ® max при ограничениях

 

3. Z = x₁ - x₂ - 3х₃ ® min при ограничениях

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться: