519_8_E92_2015_Efromeeva_E_V__Efromeev_N_M_Metody_issledovania_operatsiy_v_mashinostroenii_primery_zadachi_2-e_izdanie

а)	Проект		Ученый
		1	2	3	4	5
	Иванов И.И.	11	18	5	8	9
	Петров П.П.	5	10	6	13	6
	Александров А.А.	6	7	8	5	6
	Гришин Г.Г.	9	2	6	7	7
	Алексеев А.А.	4	11	14	9	8

.

б)	Проект		Ученый
		1	2	3	4	5
	Козлов К.К.	11	8	5	8	9
	Петров П.П.	2	10	6	7	6
	Александров А.А.	3	7	8	5	6
	Сидоров С.С.	9	11	6	7	7
	Алексеев А.А.	5	11	11	9	8

.

в)		Ученый
Проект	1	2	3	4	5
Иванов И.И.	11	8	9	8	9
Кузнецов К.К.	5	10	6	7	4
Сидоров С.С.	15	7	8	12	6
Соколов С.С.	9	11	6	7	3
Лебедев Л.Л.	5	13	9	9	8
.
г)		Ученый
Проект

		1	2	3	4	5
	Морозов М.М.	11	8	9	8	19
	Попов П.П.	19	10	26	7	20
	Соловьев С.С.	15	7	28	12	16
	Новиков Н.Н.	13	11	26	14	21
	Алексеев А.А.	16	13	15	9	14
		141

.

16.Некоторое предприятие продает товары в пяти различных городах. Покупательная способность жителей этих городов оценивается в 230, 250, 120, 320, 250 усл. ед. Для реализации товаров предприятие нанимает 5 торговых агентов, каждого из которых направляет в один из городов. Профессиональный уровень агентов различен; доли реализуемых товаров агентами представлены таблицей

		Доля реализуемых товаров торговым
	Города			агентом
		1	2	3	4	5
	1	0,22	0,2	0,3	0,1	0,2
	2	0,3	0,21	0,4	0,3	0,2
	3	0,2	0,3	0,3	0,3	0,4
	4	0,3	0,4	0,4	0,23	0,3
	5	0,4	0,2	0,4	0,1	0,24

Как следует распределить торговых агентов по городам, чтобы предприятие получило максимальную выручку от продаж?

142

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

9.1. Постановка задачи

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

В общем виде задача ЦЛП состоит в максимизации (или минимизации)

функции	• = !"! + #"# + + %"%
при условии, что переменные xi имеют ограничения вида
	&!!"! + &!#"# + + &!%"% ≤ (=, ≥)-!,
	&#!"! + &##"# + + &#%"% ≤ (=, ≥)-#,
	… … … … … … … … … … … … … … … …
	&.!"! + &.#"# + + &.%"% ≤ (=, ≥)-.,
	" ≥ 0, 1 = 1, … , 3,
	"// − целые числа.

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

Примерами задач целочисленного линейного программирования могут служить задача о назначениях (п. 8) и задача о коммивояжере.

9.2. Графический способ решения задачи ЦЛП

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

В системе координат "! "# по заданной системе ограничений строят область допустимых значений, нормальный вектор 3A , указывающий направление наискорейшего возрастания целевой функции, и перпендикулярную вектору 3A линию уровня целевой функции •, проходящей

143

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

Пример.

" = 4#$ + 2#% → '(#,#$ + 2#% ≤ 10, 2#$ − #% ≥ 1,

#$ − 3#% ≤ 2,

#$ ≥ 0,#% ≥ 0,#$, #% − целые.

Строим прямые на плоскости #$<#% , уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

	$	%			$	%			$	%
X1	0	10		X1	0	0,5		X1	0	2
X2	5	0		X2	-1	0		X2	-0,6	0

Находим полуплоскости, определяемые каждым из ограничений задачи.

АВСD – многоугольник решений (рис. 38), все точки которого

удовлетворяют системе ограничений и условию неотрицательности

переменных, но условию целочисленности удовлетворяют координаты лишь 13

точек (узлы целочисленной решетки). Такие точки, расположенные внутри

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

программирования.

144

X2

				=	1
		-	X	2
2	X	1

5

4В

→ N

С

1

А

D

3

7

-1

F

Рис. 38

			2
		=
	X2
-3
X1

10						X1
	X
	+
	1	2
			X
				=
				2	1
						0

Заменим многоугольник АВСD на многоугольник DEGHIKLMN (рис. 39),

содержащий все целочисленные точки с допустимыми координатами. Перемещение линии уровня в направлении • определит оптимальное решение – точку с целочисленными координатами L (6;2), тогда

"#$% = 4 ∙ 6 + 2 ∙ 2 = 24 + 4 = 28.

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

145

X2

5

4

2

1

E

				=	1
		-	X	2
2	X	1

В

HI

2

=

X2

-3

X1

G

→

L

N

K

С

N

M

X1

D

3

6

X

+

1

2

X

=

2

1

0

Рис. 39

9.3. Методы решения задач ЦЛП

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

Шаг 1. "Ослабление" пространства допустимых решений задачи целочисленного линейного программирования путем замены любой двоичной

переменной

у

непрерывным

ограничением

0 ≤ у ≤ 1 и отбрасывания

требования

целочисленности для

всех

остальных п ременных

(0 ≤ ! ≤ ";

"

#

$

$

+ 2

%

%

+

+

2

'

',

где

- −

наименьшее

целое число,

2

';$

2

#

#

#

получается

" +

;

'

–

двоичные

переменные). В результате

! = 2

#

− 1 ≤ ?

#

", … ,

обычная задача линейного программирования.

146

Шаг 2. Решение задачи линейного программирования и определение ее оптимального решения.

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

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

окоторых идет речь при реализации шага 3.

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

2.Метод отсекающих плоскостей.

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

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

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

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

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

147

Алгоритм метода ветвей и границ в общем случае:

Предположим, что рассматривается задача		максимизации. Зададим
	−	функции	•	задачи ЦЛП
нижнюю границу оптимального значения целевой
равной	∞. Положим " = 0.

Шаг 1 (Зондирование и определение границы).

Выбираем i-ю подзадачу линейного программирования ЛПi для исследования. Решаем ЛПi и зондируем ее, при этом возможна одна из трех ситуаций.

1.Оптимальное значение целевой функции задачи ЛПi не может улучшить текущей нижней границы.

2.ЛПi приводит к лучшему допустимому целочисленному решению, чем текущая нижняя граница.

3.ЛПi не имеет допустимых решений.

Возможны два случая.

&Если задача ЛПi прозондирована, нижняя граница изменяется только при условии, что найдено лучшее решение задачи ЦЛП. Если все подзадачи прозондированы, необходимо закончить вычисления: оптимальным решением задачи ЦЛП является то, которое соответствует текущей нижней границе, если такая существует. Иначе положить " = " + 1 и повторить шаг 1.

&Если задача ЛПi не прозондирована, переходим к шагу 2 для выполнения ветвления.

Шаг 2 (Ветвление).

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

Исключаем из пространства допустимых решений область [$% ] < $% < [$% ] + 1 (где [$] — наибольшее целое, не превосходящее $) путем формирования[ двух+ 1 подзадач ЛП, которые соответствуют ограничениям $% ≤ [$% ] и $% ≥ ! ] . Положим # = # + 1 и переходим к шагу 1.

Пример.

Решить задачу ЦЛП.	$ = 2				% +	& → () ,
		5		% + 4		& ≤ 20,
	*	40	%		+ 17	& ≤ 136,
			%		≥ 0,	& ≥ 0,
			%,		& −	целые.
					148

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

отбрасывания условий# =целочисленности7,04. . Ее оптимальным решением будет

• = 2,72, •! = 1,6 и

X2

8

4 0 X

1

+ 1 7 X

5

4

1

2 =

1 3 6

5X 1+ 4X 2= 20

Рис. 40

X1

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

Например, выбираем • = 2,72 – это равносильно замене задачи ЛП0 двумя новыми задачами ЛП1 и ЛП2 (в этом случае • – переменная ветвления).

# = 2• +5•! → %&•,		# = 2• + •! → %&•,
Задача ЛП1	+ 4•! ≤ 20,	Задача ЛП2	+ 4•! ≤ 20,
'40•		5•
	+•17•≤ !2,≤ 136,	'40•	+•17•≥ !3,≤ 136,
•	≥ 0,•! ≥ 0.		•! ≥ 0.
		149

На рис. 41 изображены пространства допустимых решений задач ЛП1 и ЛП2. Оба пространства содержат все допустимые решения исходной задачи ЦЛП. Оптимальное решение задачи ЦЛП находится в пространства допустимых решений либо задачи ЛП1, либо задачи ЛП2. Следовательно, обе должны быть решены.

X2

X1 ≤ 2

X1 ≥ 3

5

4

1

2	X1

Рис. 41

Оптимальным решением задачи ЛП1 (которое можно# = 6,5получить. графическим или симплекс-методом) является • = 2, •! = 2,5 и

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

ЛП≤1 исследуется2 ≥ 3 дальше. Рассматриваем подзадачи ЛП3 и ЛП4, используя ветви

•! и •! .

# = 2

• + •!

→

'(•,

# = 2

• + •!

→

'(•,

5•

!

5•

!

Задача ЛП3

≤ 20,

Задача ЛП4

+ 4• ≤ 20,

+ 4•

•

≤ 2,

136,

•

≤ 2,

136,

40• + 17•! ≤

40• + 17•! ≤

•!

≤ 2,

•

•

•!

≥ 0.

•! ≥ 3,

≥ 0,

≥ 0.

150