книги / Математические основы теории систем. Методы оптимизации

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

	1	2	3	4
5	1	1	1	1	7
6	–3	1	2	1	6
7	2	1	1	–1	2
	0	–3	–4	–1	–15

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

Новая симплекс-таблица имеет вид:

	1	2	4
5	–1	0	2	5
6	–7	–1	3	2
3	2	1	–1	2
	8	1	–5	–7

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

	1	2
5	11/3	2/3	11/3
4	–7/3	–1/3	2/3
3	–1/3	2/3	8/3
	–11/3	–2/3	–11/3

В результате всех преобразований получается таблица:

2

1 2/11 1

4 1/11 3

3 8/11 3

0 0

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

41

3. Переход к исходной целевой функции:

Q = − x1 + x2 + 2x3 − x4 .

Записываются ограничения, полученные из итоговой симплекс– таблицы:

		+	2					= 1,
	x1						x2
			11
			1
	x4	+					x2	= 3,
					11
		+	8					= 3.
	x3						x2
			11

Выражаются базисные переменные через свободные и подставляются эти выражения в целевую функцию:

Q = −1+	2	x2	+ x2	+ 6 −	16	x2	− 3 +	1	x2	= 2 −	2	x2 .
11				11			11			11

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

	2
1	2/11	1
4	1/11	3
3	8/11	3
	–2/11	–2

2.6.Алгоритм двойственного симплекс-метода

1.Составление симплекс-таблицы, как для обычного симплексметода.

2.Выбор разрешающей строки: среди отрицательных bi выбирается максимальный по модулю элемент.

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

42

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

5.Окончание решения, когда все bi неотрицательны.

Пример

x1	+ x3 ≥ 1,
x1 + x2 − x3 ≥ 4,
	, x2 , x3 ≥ 0.
x1
Q = 10x1 + 10x2 + 14x3 → min.

	Решение:
	1.		Вводим искусственные переменные:
							x1 + x3 − x4 = 1,
							x1 + x2 − x3 − x5 = 4.
	2.		Смена знака:
							− x1 − x3 + x4 = −1,
							− x1 − x2 + x3 + x5 = −4.
	3.		Симплекс-таблица:
					1	2	3
			4		–1	0	–1	–1		––– разрешающая строка
			5		–1	–1	1	–4
					10	10	14	0	разрешающий столбец
	4.		Новая симплекс-таблица:
								2	3
							5
						4	–1	1	0			3
						1	–1	1	1			4
							10	0	4			–40

Правые части ограничений положительны, следовательно, найдено оптимальное решение.

Ответ: x1 = 4, x2 = 0, x3 = 0, x4 = 3, x5 = 0, Qmin = 40.

43

Задания для самостоятельной работы

1. f(x) = –3x1 + 2x2 – 2x3 + 2x4 – x5 →min,	2. f(x) = –6x1 – 8x2 →min,
1 + x 2 – x3 = 1,	2x1 + 5x 2 + x3 = 20,
– x2 + x3 + x4 = 1,	12x1 + 6x2 + x4 = 72,
x2 + x3 + x5 = 2,	xj ≥ 0, j = 1,...4.

xj ≥ 0, j = 1,...5.
3. f(x) = –x1 – 4x4 → min,	4. f(x)= –34x1+x2+3x3–3x4→min,
–x1 – 2x 2 + 2x3 + x 4 + 5x5 = 13,	3x1 – 2x 2 + 3x3 +2 x 4 = 9,
– 2x1 + 2x2 + 4x4 + x5 = 5,	x1 + 2x2 – x3 + x4 = 0,
x1 – x 2 + x3 – x 4 + 2x5 = 5,	x1 – x 2 + 2x3 + x 4 = 6,
xj ≥ 0, j = 1,...5.	–xj ≥ 0, j = 1,...4.
5. f(x) = –x1 + x2 + 2x3 – x4 → min,	6. f(x) = –3x1 + x3 – 2x4 → min,
x1 + x 2 + x3 + x 4 = 7,	15x1 + 2x 2 – 3x3 – 7x 4 + x5 = 4,
–3x1 + x2 + 2x3 + x4 = 6,	2x1 + x2 + x3 – 2x4 = 3,
2x1 + x 2 + x3 – x 4 = 2,	x 3 + 5x4 + 2x5 = 7,
xj ≥ 0, j = 1,...4.	xj ≥ 0, j = 1,...5.
7. f(x) = –x2 → min,	8. f(x) = 3x1 – 2x2 + x3 → min,
x1 + x 2 ≥ 1,	3x1 + x 2 – 2x3 = 2,
–x1 + x2 ≥ –1,	4x1 + 3x2 + 2x3 = 1,
2x 1 – x2 ≥ 0,	x 3 + 5x4 + 2x5 = 7,
xj ≥ 0, j = 1, 2.	xj ≥ 0, j = 1, 2, 3.
9. f(x) = –2x1 + x2– x3 + x5→min,	10. f(x)= –8x1 –2x2+5x3–15x4→min,
– 2x2 + x 4 + x5 = –3,	–x1 + 3x 2 + x3 + 10x 4 ≤ 25,
x3 – 2x4 = 2,	2x1 + x2 + x3 + 5x4 ≤ 6,
x1 + 3x 2 – x 4 ≤ 5,	10x1 + 2x 2 + 2x3 – 5x 4 ≤ 26,
x1 + x2 ≥ –3,	xj ≥ 0, j = 1,...4.
	xj ≥ 0, j = 1,...5.

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

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

К задачам целочисленного линейного программирования относятся такие задачи линейного программирования, в которых имеется дополнительное ограничение на целочисленность переменных [3].

44

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

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

2.7.1. Метод сечения Гомори

Сущность метода:

1. Решается задача линейного программирования без требования целочисленности. Получаем решение:

x	= x* , i =	1,n	.
i	i

2. Проверка полученного решения на целочисленность.

Если xi – целые числа, то задача решена, если нет – выполняются следующие действия:

от допустимого многогранника отсекается часть площади. Точка с координатами xi должна попасть в отсекаемую область (рис. 2.4). Математически это отсечение обозначает введение дополнительного ограничения;

решается задача с количеством ограничений, увеличенным на единицу.

Рис. 2.4. Метод сечения Гомори

45

Получение дополнительного ограничения

Введем следующие обозначения: [Х] – целая часть Х, [Х] ≤ Х .

Например, [4,2] = 4, [–4,2] = –5.

{Х} – дробная часть Х, {Х} = Х – [Х], {Х}≥ 0.

Предположим, имеется задача линейного программирования, приведенная к каноническому виду (2.15):

Q = p1x1 + p2 x2 + ... + pn xn → min.

a	x + a		x + ... + a x + x			= b ,
11 1		12 2		1n n	n+1		1
a21x1 + a22 x2 + ... + a2n xn + xn+						2 = b2 ,
								(2.15)
...
a	x + a		x	+ ... + a x	+ x	+m	= b .
	m1 1		m2 2	mn n	n			m
xi ≥ 0
Выразим базисные переменные через свободные:
				n
	xn+i	= bi − ∑aij xj i = 1,...,m.						(2.16)

j=1

Вэтом выражении хi должны быть целыми. Преобразуем (2.16):

xn+i = [bi ]+ {bi }				n			n
			− ∑		aij	xj −∑{aij } xj =
				j=1			j=1
= [bi ]	n			xj	+ {bi }		n	(2.17)
	− ∑	aij					− ∑{aij } xj .
	j=						j=
1442443					1442443
	L1						L2

Если xn+i – целочисленные, то L1 – всегда целочисленное, L2 – в общем случае может быть нецелочисленным, но для данной задачи L2 должно принимать следующие значения: 0, –1, –2,…, т.е.

L2 ≤ 0,				(2.18)
n		xj	≤ 0.	(2.19)
{bi } − ∑ aij
j=1

46

Преобразуем ограничения-неравенства (2.19) в ограниченияравенства:

n
xl − ∑{aij } xj = −{bi }.	(2.20)

j=1

Последнее ограничение и является искомым дополнительным ограничением. В качестве l-й берется та строка симплекс-таблицы, которая имеет максимальную дробную часть коэффициента bi.

Алгоритм метода сечения Гомори

1.Задача линейного программирования приводится к каноническому виду и составляется симплекс-таблица.

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

3.Окончание решения в случае целочисленности.

4.Если решение не целочисленно, то в таблицу вводится строка,

имеющая коэффициенты –{aij}, –{bi} той строки таблицы, которая имеет максимальную дробную часть коэффициента правой части ограничений.

5. Решается задача линейного программирования двойственным симплекс-методом.

Пример 1

2x1 + x2 + x3 = 4,2x1 + 3x2 + x4 = 6,

Q = − x1 − x2 → min.

1. Задача уже приведена к каноническому виду. Составляем сим- плекс-таблицу и решаем задачу симплекс-методом:

	1	2
3	2	1	4
4	2	3	6
	–1	–1	0

47

	3	2
1	1/2	1/2	2
4	–1	2	2
	1/2	–1/2	2
		4
	3
1	3/4	–1/4		3/2
2	–1/2	1/2		1
	1/4	1/4		5/2

Полученооптимальноерешение, ноэторешениенецелочисленно. 2. Вводим дополнительную строку.

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

{3/4} = 1/4, {–1/4} = 3/4, {3/2} = 1/2:

	3	4
1	3/4	–1/4	3/2
2	–1/2	1/2	1
5	–1/4	–3/4	–1/2
	1/4	1/4	5/2

3. Далее решаем задачу двойственным симплекс-методом.

	3	5
1	1	–1/3	5/3
2	–1	2/3	2/3
4	1	–4/3	2/3
	0	1/3	7/3

4. Снова получено нецелочисленное решение. Вводим новое ограничение. При равенстве дробных частей выбирается любая строка (в данном примере рассмотрена последняя строка).

48

{1} = 0, {–4/3} = 2/3, {2/3} = 2/3

	3	5
1	1	–1/3	5/3
2	–1	2/3	2/3
4	1	–4/3	2/3
6	0	–2/3	–2/3
	0	1/3	7/3

Решаем полученную таблицу двойственным симплекс-методом:

	3	6
1	1	–1/2	2
2	–1	1	0
4	1	–2	2
5	0	–3/2	1
	0	1/2	2

Все переменные целочисленные, следовательно, получено искомое решение:

x1 = 2, x2 = 0, x3 = 0, x4 = 2, Qmin = –2.

Пример 2

− x1 + 10x2 + x3 = 40,4x1 + 2x2 + x4 = 29, Q = x1 − 20x2 → min.

Решение 1. Задача уже приведена к каноническому виду. Составляется

симплекс-таблица и решается задача симплекс-методом:

1 2

3	–1	10	40

4 4 2 29

1 –20 0

49

		1	3
	2	–1/10	1/10		4
	4	42/10	–2/10		21
		–1	2		80
		4	3
	2	1/42	4/42		9/2
	1	10/42	–2/42		5
		10/42	82/42		85

Полученооптимальноерешение, ноэторешениенецелочисленно. 2. Вводится дополнительная строка:

	4	3
2	1/42	4/42	9/2
1	10/42	–2/42	5
5	–1/42	–4/42	–1/2
	10/42	82/42	85

Для перехода к допустимому базисному решению находится разрешающий элемент и преобразуется симплекс-таблица:

	5	3
2	1	0	4
1	10	–1	0
4	–42	4	21
	10	1	80

Все переменные целочисленные, следовательно, получено искомое решение:

x1 = 0, x2 = 4, x3 = 0, x4 = 21, Qmin = –80.

2.8. Транспортная задача

Транспортная задача является разновидностью ЗЛП [4].

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

Дано:

n потребителей: 1...n. m складов: 1...m.

50