Целочисленное

10

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

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

Из первого условия задачи: х3 = 19 - 2х1 - 5х2 Из второго : х4 = 16 - 4х1 - х2

11

Подставляем эти выражения в первое ограничение Гомори

2/9x3 + 8/9x4 - S1 = 4/9, S1 0

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

S1 =18 - 4х1 - 2х2 0.

Отсюда имеем: 4х1 + 2х2 18. Это ограничение отсекает от множества планов область, содержащую точку 1. Новый оптимальный нецелочисленный план - точка 2.

Подставляя выражения х3 = 19 - 2х1 - 5х2 и: S1 = 18 - 4х1 - 2х2 во второе ограничение Гомори :

1/4x3 + 7/8S1 - S2 = 1/2, S2 0,

Получаем

S2 = 20 - 4х1 - 3х2 0

или 4х1 + 3х2 20. Это ограничение отсекает от множества планов область, содержащую точку 2. Новый оптимальный нецелочисленный план - точка 3.

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

2/7x3 + 6/7S2 - S3 = 4/7, S3 0

дают S3 = 22 - 4х1 - 4х2 0. На рисунке видим, что условие 4х1 + 4х2 22 отсекает от множества планов область, содержащую точку 3. Но-

вый оптимальный нецелочисленный план - точка 4.
Подстановки в четвертое ограничение Гомори :
	1/4S3 - S4 = 1/2, S4 0	х1 + х2 5 дела-
дают S4 = 5 - х1 - х2	0 и наблюдаем, как условие
ет недопустимой	точку 4. Новый оптимальный нецелочисленный
план - точка 5.
Наконец, пятое ограничение Гомори :
	1/3x4 + 2/3S4 - S5 = 2/3, S5 0
преобразуется к эквивалентному виду S5 = 8 - 2х1 - х2		0 и наблюда-

ем как условие 2х1 + х2 8 отсекает от множества планов область, содержащую точку 5.

В итоге устанавливаем оптимальность и целочисленность плана – точки 6 с координатами (3;2).

4. МЕТОД ВЕТВЕЙ И ГРАНИЦ

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

12

Получив нецелочисленный оптимальный план задачи, в котором какая-то составляющая xk оказалась нецелочисленной (xk =А), мы ставим две задачи на основе ограничений решенной задачи и дополнительных условий xk [A] и xk [A]+1 соответственно. Например, если в найденном оптимальном плане х3 =4.7, то в новых задачах будут условия х3 4 и х3 5 (недопустимость найденного плана в будущем очевидна). Каждую из полученных задач решаем до получения оптимального плана и нового разветвления.

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

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

Для иллюстрации метода возьмем пример из предыдущего раз-

дела:

max L = 8x1 + 6x2

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

2x1 + 5x2 19

4x1 + x2 16

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

Решая эту задачу симплексным методом, мы получили оптимальный план Хопт = (61/18; 22/9). Lmax = 376/9.= 41 7/9/

Если вам не по душе нецелочисленность x1,, ставим две задачи:

А1	А2
max L = 8x1 + 6x2	max L = 8x1 + 6x2
при ограничениях:	при ограничениях:
2x1 + 5x2 19	2x1 + 5x2 19
4x1 + x2 16	4x1 + x2 16
x1 3	x1 4
x1 0, x2 0	x1 0, x2 0
x1, x2 - целые числа	x1, x2 - целые числа

Задача А2 обладает (повезло !) единственным планом (4,0), для которого Lmax = 32. Задача А1 решается до получения оптимального плана (3, 13/5) и появляются две ветви

А11

А12

	13
max L = 8x1 + 6x2		max L = 8x1 + 6x2
при ограничениях:		при ограничениях:
2x1 + 5x2 19		2x1 + 5x2 19
4x1 + x2 16		4x1 + x2 16
x1 3, x2 2		x1 3, x2 3
x1 0, x2 0 - целые числа		x1 0, x2 0 - целые числа

На приведенном рисунке точка 1 определяет решение исходной задачи, точки 3 и 2 соответственно - решение задач А1 и А2, точки 4 и 5 – решение задач А11 и А12.

Заметим, что существует много задач, где требование целочисленности накладывается не на все переменные. В этом случае ограничение Гомори чуть-чуть модифицируется [1]

f k f kj x j S* ,	S * 0	( 3 )
j Б

где

14

	Ak		j
	- f	k	/(1 f	k	) A
					k j
f kj =	f k		j

, j Y , Akj

0

,j Y , Akj < 0

, j Y ,

f kj f k

	j Y , f kj > f k
f k /(1 f k ) (1 - f k j ) ,

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

5.КОНТРОЛЬНЫЕ ВОПРОСЫ

1.Может ли задача линейного целочисленного программирования иметь несколько решений?

2.Может ли ограничение Гомори иметь вид: 1/5x5 - 7/8x6 1/3?

3.Может ли ограничение Гомори иметь вид: 1/5x5 + 7/8x6

1/3?

4.Как можно убедиться, что целочисленная программа не имеет ни одного плана?

5.Как проверить, что найденный оптимальный план становится недопустимым после ввода дополнительного ограничения Гомори?

6.Может ли целевая функция задачи линейного целочисленного программирования оказаться неограниченной?

7.В некоторой задаче линейного целочисленного программирования переменные принимают лишь значения: 0 или 1. Какой экономический смысл данного решения? Приведите примеры.

8.Может ли оптимальное значение целевой функции целочисленной линейной программы оказаться нецелочисленным?

9*. Оцените максимальный размер симплексных таблиц при использовании метода Гомори, если не хранить информацию о переменных Гомори, входящих в базис?

10*. Отвечает ли требованиям, предъявляемым к ограничениям

Гомори, дополнительное ограничение в виде		x j 1?
	j базису

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

12.Как известно старым поклонникам бардовской песни, »из ливер-

пульской гавани всегда по четвергам корабль уходит в плаванье к далеким

15

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

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

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

6.ЗАДАНИЯ

Решить задачу линейного целочисленного программирования при xj 0 (j = 1, 2, ..., n).

В вариантах, где n = 2, дать геометрическую интерпретацию метода Гомори (по крайней мере, одно-два отсечения). Можете попробовать с использованием графических представлений оценить трудоемкость метода ветвей и границ.

1. min L = 3x1 + x2		2. min L = 5x1 + 7x2
при ограничениях		при ограничениях
-4х1 + х2 29		-3х1 + 14х2 78
3х1	- х2 15	5х1	- 6х2 26
5х1	+ 2х2 38	х1	+ 4х2 25
3. max L = 2x1 + x2		4. max L = 3x1 + 2x2
при ограничениях		при ограничениях

		16
6х1 + 4х2 24		х1 + х2 13
3х1 - 3х2 9		х1 - х2 6
-х1 + 3х2 3		-3х1 + х2 9
5. max L = 7x1 + x2		6. max L = 3x1 - x2
при ограничениях		при ограничениях
9х1 + 4х2 110		3х1 - 2х2 3
11х1 - 3х2 24		-5х1 - 4х2 -10
2х1 - 7х2 15		2х1 + х2 5
7. max L = 2x1 + 3x2		8. max L = x1 + x2
при ограничениях		при ограничениях
6х1 + 7х2 57		3х1 + 5х2 45
3х1 + 11х2 47		13х1 + 10х2 130
9. max L = 4x1 + 5x2 + x3		10. max L = -x1 + 3x2 + 6x3
при ограничениях		при ограничениях
3х1 + 2х2	10	3х1 + 5х2 - 2x3 16
х1 + 4х2	11	3х1 + 17х2	33
3х1 + 3х2 + x3 13		-6х2 + 13x3 43
11. max L = 2x1 + 7x2		12. max L = 8x1 + 11x2
при ограничениях		при ограничениях
3х1 + 8х2 23		11х1 + 2х2 25
3х1 + 11х2 31		3х1 + 8х2 12
13. max L = 4x1 + 3x2		14. min L = 5x1 - 3x2
при ограничениях		при ограничениях
-6х1 + 5х2 14		-6х1 + 8х2 11
3х1 + х2 17		-7х1 + х2 5
-7х1 + 3х2 -44		7х1 - 3х2 13
15. max L = 5x1 - 3x2		16. min L = 2x1 - 9x2
при ограничениях		при ограничениях
-6х1 + 8х2 11		-3х1 + 7х2 10
-7х1 + х2 5		3х1 + х2 5
7х1 - 3х2 13		5х1 - 7х2 13
17. max L = 2x1 + 4x2 - 4x3		18. min L = -3x1 + 2x2 + 5x3
при ограничениях		при ограничениях

			17
2х1 + 7х2 + 5x3 9			9х1 - 4х2 + x3 16
7х1 + х2 + 3x3 11			-5х1 + х2 + 3x3 9
19. max L = x1 - 3x2 - x3 + 2x4			20. max L = 2x1 - x2 + 6x4
при ограничениях			при ограничениях
2х1	+ x3 - 3x4 12		3х1 + 2x2 +	3x4 16
3х1 - х2 +		x4 20	-2х2 + 4х3 + 7x4 18

21. max L = x1 + 10x2		22. min L = -7x1 - x2
при ограничениях		при ограничениях
3х1 + 4х2 23		5х1 + 2х2 24
-х1 + 2х2 = 4		12х1 - 7х2 15
2х1 + 3х2 14		6х1 + 8х2 9
23. max L = 3x1 + 2x2 + 2x3		24. max L = -4x1 + x2
при ограничениях		при ограничениях
4х2 + 3x3 7		-7х1 + 13х2 + 3x3 7
6х1 + 5х2 + x3 = 12		х1 - 6х2 + 7x3 -9
25. max L = -10x1 - 14x2 - 21x3		26. max L = 4x1 + 3x2 + 8x3
при ограничениях		при ограничениях
2х1 + 2х2 + 7x3 14		21х1 - 17х2 + 19x3 77
8х1 + 11х2 + 9x3 12		6х1 + 4х2 + 3x3 29
9х1 + 6х2 + 3x3 10		10х1	+ 11x3 65
27. max L = 2x1 + 3x2 + 4x3		28. max L = x1 - 5x2 + x3
при ограничениях		при ограничениях
х1 + 5х2 + 13x3 = 37		4х1 + х2 - 6x3 41
-9х1 + 7х2 + 4x3 20		-2х1	- x3 2
-х1 + 8х2	8	3х1 + 2х2 + 7x3 = 34
29. max L = 5x1 + 8x2		30. max L = x1 + 8x2
при ограничениях		при ограничениях
-8х1 + 12x2 40		4х1 - 3х2 12
13х1 - 9х2 37		-5х1 + 7х2 34
31. min L = 19x1 + 21x2		32. max L = 2x1 + 5x2
при ограничениях		при ограничениях

	18
2х1 + 5x2 20	х1 + х2 6
4х1 + х2 20	4х1 + 11х2 44
33. min L = 10x1 - 111x2	34. max L = 8x1 + 19x2 + 7x3
при ограничениях	при ограничениях
-х1 + 10x2 40	х1 + 3х2 + 3x3 50
х1 + х2 20	3х1 + 4х2 + x3 25

35. min L = -4x1 - 5x2 - 9x3 - 11x4	36. max L = 3x1 + 2x2 + 8x3 + 7x4
при ограничениях	при ограничениях
х1 + х2 + x3 + x4 15	2х1 + х2 + 5x3 + 8x4 10
7х1 + 5х2 + 3x3 + 2x4 120	9х1 + 3х2 + 4x3 + 2x4 21
3х1 + 5x2 + 10x3 + 15x4 100	3х1 + 8x2 + 4x3 + 11x4 46
37. max L = 2x1 + 3x2	38. max L = -2x1 + 3x2
при ограничениях	при ограничениях
х1 + 19х2 30	4х1 + х2 8
2х1 + х2 20	-5х1 + 6х2 7
39. min L = 6x1 - 2x2	40. min L = 3x1 + 4x2
при ограничениях	при ограничениях
2х1 - 6х2 -39	2х1 + 19х2 24
7х1 + 3х2 24	13х1 + 12х2 50
-2х1 + 5x2 33	х1 - 5x2 1
41. min L = 6x1 + x2	42. max L = x1 + 32x2
при ограничениях	при ограничениях
3х1 - х2 = 9	2х1 - 3х2 10
-х1 + 4х2 18	5х1 - 9х2 16
2х1 + 3x2 31	-х1 + 6x2 42

43.max L = 4,4x1 + 2,7x2 + 3,2x3 + 2,8x4 + 3,5x5 + 3,9x6

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

80х1	+ 62х2	+ 92x3	+ 82x4 + 65x5 + 90x6 800
95х1	+ 90х2	+ 96x3	+ 110x4 + 120x5 + 80x6 600

44.max L = 5x1 + 2x2 - 3x3 + 2x4 + 3x5 - 3x6

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

5х1 + 6х2 + 4x3 + 2x4 - 3x5 + 5x6 = 11

		19
5х1 + 5х2 + 7x3 +	3x5 + 5x6 = 10
2х1 + 2х2 + 2x3 +	3x5	= 4

45.max L = 4x1 + 7x2 - x3 + 2x4

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

х1 + х2 + x3 + x4 = 15

4х1 - х2 + 8x3	14
3х2 + 4x3	9

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

1.Тынкевич М. А. Экономико-математические методы (исследование операций); КузГТУ. – Кемерово, 2000. - 176 с.

2.Вагнер Г. Основы исследования операций: в 3 т. Т. 2. Глава

13.– М.: Мир, 1973. – 488 с.

3.Таха Х. А. Введение в исследование операций: в 2 кн. Кн.1. Глава 8. – М.: Мир, 1985. – 479 с. (более позднее издание: – М.: Вильямс, 2005).

Рассмотрение задач целочисленного программирования и методов их решения можно найти в любом учебнике по математическому программированию и в десятках тысяч ссылок в Интернете, но ничего нового в сравнении с великолепными монографиями [2] и [3], написанными доступно для любого заинтересованного читателя, вы там не обнаружите.

При составлении данного методического руководства использован пример из предыдущего его варианта (2000 г.), решение которого выполнено Н. Ю. Коломаровой.