MMP_5

x		9 3x x
	2	1		4
x3		21 8x1 3x4			(33)
x		64 23x	8x		4
5		1

Получили систему ограничений,

имеющую допустимый вид: x2 , x3

и

x5 – базисные неизвестные, x1

и

x4

– свободные неизвестные. Перейдем к

процедуре шагов.

Шаг 1: положим

в (33) x1 0

и

x4 0, тогда

получим

базисное

решение 0, 9, 21, 0, 64 , для которого целевая функция

f 8x1 16x2 8x1

16 9 3x1

x4 144 40x1 16x4 (34)

примет значение f

144 .

В (5.15) коэффициент

при x4

положительный и

для дальнейшего

уменьшения значения f надо положить x4 0 и наращивать x1 .

Шаг 2: положим в (33)

x4 0,

а x1

начнем наращивать так,

чтобы x2 ,

x3

и x5 оставались неотрицательными, т. е.

x2 9 3x1 0,

x3 21 8x1 0,

x5 64 23x1 0 .

Откуда находим x1 min

9

21

64

21

0 . Объявив x3

;

;

. Тогда x3

и

3

8

23

8

x4

свободными неизвестными, приведем (33) к допустимому виду:

x

21

1

x

3

x

4

1

8

8

3

8

9

3

1

(35)

x2

x3

x4

8

8

8

29

23

5

x5

x3

x4

8

8

8

30

	21		9		29
Из (35) получим базисное решение		;		; 0; 0;		. Для него
8			8		8

	21			1				3
f 144 40						x				x		16x			39	5x x		(36)
	8			8 3				8			4			4		3	4
примет значение f	39 .
В (36) коэффициенты при свободных неизвестных положительны и
дальнейшее уменьшение значения f										невозможно:						fmin 39		при x3 x4 0 .
Задача решена.
Учитывая экономический смысл неизвестных, приходим к выводу.
Ежесуточная диета, обеспечивающая необходимое количество
питательных веществ, состоит из							x1 2,625						единиц продукта P1 , x2 1,125

единиц продукта P2 и ее минимальная стоимость F 39 единиц. При этом потребности организма в питательных веществах A и B отвечают требуемым минимальным объемам V 6 единиц и V 9 единиц соответственно (т.к. x3 0 и x4 0 ), а потребности в питательном веществе С больше требуемого минимального объема V 8 единиц на x5 3,625 единиц.

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

Ответ утвердительный и содержится в следующей теореме.

Теорема. Если существует оптимальное решение ЗЛП, то существует и базисное оптимальное решение. Последнее всегда может быть получено с помощью симплекс-метода.

Симплекс-таблицы для решения ЗЛП. Метод искусственного базиса (М-метод).

Описанный процесс решения ЗЛП симплекс-методом довольно трудоемкий и требует выполнения однообразных преобразований. Причем с возрастанием числа неизвестных растет и число шагов.

31

Оказывается, эти преобразования можно записать в виде последовательности однотипно заполненных таблиц, называемых симплекс-

таблицами.

Изложим способ составления и преобразования таких таблиц на

примерах первой и второй основных задач .

I. Первая основная задача.

Для заполнения первой симплекс-таблицы необходимо переписать

целевую функцию F и систему ограничений в виде:

		F 25x1 34x2 0
		x	x	2		x		42
		1					3
		x1 2x2 x4 48
		x	4x			2	x	72
		1						5
Заполним таблицу
Базисные	Свободные	x1					x2			x3	x4	x5
неизвестные	члены
x3	42	1					1			1	0	0
x4	48	1					2			0	1	0
x5	72	1					4			0	0	1
F	0	–25					–34			0	0	0

В выражении для F выясняем, имеются ли в последней строке таблицы,

кроме столбца «свободные члены», отрицательные числа. Если таковых нет,

то задача решена. Если же есть, то выполняем преобразование: в столбце x1

имеем 25 0 (из двух отрицательных чисел –25 и –34 выбирают меньшее по модулю), над этим элементом ищем положительные числа. Если таковых нет, то задача не имеет решения. В нашем случае над –25 есть три положительных числа: 1; 1 и 1.

Найдем

	42		48		72			42	42
min		,		,
	1		1		1			1

32

Элемент, стоящий на пересечении строки ( x3 ) и столбца ( x1 ), называем разрешающим. В нашем случае он равен 1. (Если разрешающий элемент равен числу m 1, то всю строку делят на разрешающий элемент m, чтобы получить 1). Неизвестная x1 вводится в базис, а неизвестная x3 выводится из него.

Заполняем вторую симплекс-таблицу. Строка ( x3 ) из первой таблицы становится в ней строкой ( x1 ). Далее преобразуем строки ( x4 ), ( x5 ) и (F)

первой таблицы так, чтобы их элементы, стоящие в столбце ( x1 ), обратились

в0. С этой целью

1)вычтем элементы строки ( x1 ) из соответствующих элементов

строки ( x4 ), и запишем полученные результаты в строку ( x4 ) второй таблицы;

2) вычтем элементы строки ( x1 ) из соответствующих элементов строки ( x5 ), и запишем полученные результаты в строку ( x5 ) второй таблицы;

3)умножим элементы строки ( x1 ) на 25, сложим с соответствующими

элементами строки (F), и запишем полученные результаты в строку (F)

второй таблицы.

В результате получим следующую симплекс-таблицу

	Базисные	Свободные	x1	x2	x3	x4	x5
	неизвестные	члены
	x1	42	1	1	1	0	0
	x4	6	0	1	–1	1	0
	x5	30	0	3	–1	0	1
	F	1050	0	–9	25	0	0

В строке (F) есть отрицательное число –9. Поэтому продолжим поиск

оптимального решения. Над –9 есть три положительных числа: 1; 1 и 3.

Найдем

33

	42		6		30			6	6
min		,		,
1			1		3			1

Элемент, стоящий на пересечении строки ( x4 ) и столбца ( x2 )

разрешающий и равен 1. Неизвестная x2 вводится в базис, а неизвестная x4

выводится из него.

Заполняем третью симплекс-таблицу. Строка ( x4 ) из второй таблицы становится в ней строкой ( x2 ). Далее преобразуем строки ( x1 ), ( x5 ) и (F)

второй таблицы так, чтобы их элементы, стоящие в столбце ( x2 ), обратились

в0. С этой целью

1)вычтем элементы строки ( x2 ) из соответствующих элементов

строки ( x1 ), и запишем полученные результаты в строку ( x1 ) третьей таблицы;

2) умножим элементы строки ( x2 ) на 3, вычтем из соответствующих элементов строки ( x5 ), и запишем полученные результаты в строку ( x5 )

третьей таблицы;

3)умножим элементы строки ( x2 ) на 9, сложим с соответствующими

элементами строки (F), и запишем полученные результаты в строку (F)

третьей таблицы.

В результате получим следующую симплекс-таблицу

	Базисные	Свободные	x1	x2	x3	x4	x5
	неизвестные	члены
	x1	36	1	0	2	–1	0
	x2	6	0	1	–1	1	0
	x5	12	0	0	2	–3	1
	F	1104	0	0	16	9	0

В строке (F) нет отрицательных чисел. Получили оптимальное

решение:

34

Fmax 1104

при x1 36, x2 6, x3 x4 0 , x5 12 .

Замечание. Симплекс-таблицы удобнее «пристыковывать» друг к другу по вертикали, что позволяет не писать многократно заглавную строку

II. Вторая основная задача.

Для заполнения первой симплекс-таблицы перепишем целевую функцию F и систему ограничений (6.14), имеющую допустимый вид,

следующим образом:

F 40x1 16x4 144

3x1 x2 x4 98x1 x3 3x4 21

23x1 8x4 x5 64

Заполним таблицу

	Базисные	Свободные	x1	x2	x3	x4	x5
	неизвестные	члены
	x2	9	3	1	0	–1	0
	x3	21	8	0	1	–3	0
	x5	64	23	0	0	–8	1
	F	144	40	0	0	–16	0
	x2	1,125	0	1	–0,375	0,125	0
	x1	2,625	1	0	0,125	–0,375	0
	x5	3,625	0	0	–2,875	0,625	0
	F	39	0	0	–5	–1	0

В выражении для F выясняем, имеются ли в последней строке таблицы,

кроме столбца «свободные члены», положительные числа. Если таковых нет,

то задача решена. Если же есть, то выполняем преобразование: в столбце x1

имеем 40 0 . Над этим элементом ищем положительные числа. Если таковых нет, то задача не имеет решения. В нашем случае над 40 есть три положительных числа: 3; 8 и 23.

35

Найдем

9			21		64			21		2,625
min		,		,
	3		8		23			8

Элемент, стоящий на пересечении строки ( x3 ) и столбца ( x1 )

разрешающий и равен 8. Неизвестная x1 вводится в базис, а неизвестная x3

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

Преобразуем строки ( x2 ), ( x5 ) и (F) первой таблицы так, чтобы их элементы, стоящие в столбце ( x1 ), обратились в 0. С этой целью

1) умножим элементы строки ( x1 ) на 3, вычтем из соответствующих элементов строки ( x2 ), и запишем полученные результаты в строку ( x1 )

второй таблицы;

2) умножим элементы строки ( x1 ) на 23, вычтем из соответствующих элементов строки ( x5 ), и запишем полученные результаты в строку ( x5 )

второй таблицы;

3) умножим элементы строки ( x1 ) на 40, вычтем из соответствующих элементов строки (F), и запишем полученные результаты в строку (F) второй таблицы.

В строке (F) нет положительных чисел. Получили оптимальное решение: Fmin 39

при x1 2,625 , x2 1,125 , x3 x4 0 , x5 3,625.

Замечание. Первая симплекс-таблица второй основной задачи была заполнена с учетом того, что система ограничений (6.11) была предварительно сведена к допустимому виду (6.14), т.е. был найден допустимый базис. Зачастую поиск такого базиса довольно затруднителен.

36

Рассмотрим следующий метод нахождения допустимого базиса, который называют методом искусственного базиса или М-методом.

Метод искусственного базиса (М-метод).

Применительно к рассматриваемой задаче М-метод заключается в следующем. В каждое уравнение системы ограничений (6.11), введем свою новую искусственную неизвестную: y1 0 , y2 0 и y3 0. Включим их в число базисных неизвестных и составим новую функцию цели

G F M y1 y2 y3 ,

где М – произвольно большое положительное число.

В результате получили следующую ЗЛП, приведенную к допустимому

виду

G 8x1 16x2 M y1 y2 y3 min

y1 6 x1 3x2 x3y2 9 3x1 x2 x4y3 8 x1 8x2 x5

xi 0, i 1, 5, y j 0, y 1, 3 .

Эту задачу называют М-задачей.

Сформулируем утверждения, устанавливающие связь между

решениями исходной задачи и М-задачи.

1. Если в оптимальном решении М-задачи все искусственные

переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи (т.е. Gmin Fmin , если y1 y2 y3 0 ).

2. Если имеется оптимальное решение М-задачи, в котором хотя бы одна из искусственных переменных отлична от 0, то исходная задача не имеет допустимого решения.

37

3. Если М-задача не имеет оптимального решения, то исходная задача неразрешима (т.е. если Gmin , то либо Fmin , либо нет ни одного допустимого решения).

Из этих утверждений следует следующее правило решения M-задачи симплекс-методом:

а) Необходимо выбирать последовательность шагов таким образом,

чтобы все искусственные неизвестные y1 , y2 , y3 вышли из базиса, т.е. стали свободными.

б) В симплекс-таблице отбросив столбцы для этих неизвестных,

получим симплекс-таблицу, дающую оптимальное решение исходной задачи.

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

переменная yi		входит в базис, причем в строке для													yi свободный член
положителен, то исходная задача не имеет ни одного допустимого решения.
Составим симплекс-таблицы решаемой задачи.
Базис	Свобод
ные	ные
неизв	члены			x1			x2	x3	x4			x5				y1	y2			y3
ест
ные
y1	6	1					3	–1	0	0						1	0		0
y2	9	3					1	0	–1	0						0	1		0
y3	8	1					8	0	0			–1				0	0		1
G	23M	5M 8					12M 16	M	M			M				0	0		0
y1	3	5 8					0	–1	0	3 8						1	0		3 8
y2	8			23 8			0	0	–1	1 8						0	1		1 8
x2	1	1 8					1	0	0			1 8				0	0		1 8
			7M																	3M
G	11M 16				6		0	M	M		M		2			0	0				2
			2																	2
										2
y1	29 23	0					0	–1	5 23			8 23				1	5 23	8 23
x1	64 23	1					0	0	8 23	1 23						0	8 23	1 23

38

x2		15 23		0	1	0		1 23			3 23		0	1 23			3 23
		29M 752						5M 48			8M 40				4 7M 12		31M 40
G		23		0	0	M		23		23			0	23
																	23
x5		29 8		0	0	23 8		5 8		1			23 8		5 8		–1
x1		21 8		1	0	1 8		3 8		0			1 8	3 8			0
x2		9 8		0	1	3 8		1 8		0			3 8		1 8		0
G		39		0	0	–5		–1		0			M	5 M 1			M

39