Документ: 5021, страницы 16-20 | База учебных материалов

3.	Z	5x1		3x2	min
	3x1			2x2	6,
	2x1			3x2	6,
	x1			x2	4,
	4x1			7x2	28,
	x1		0, x2		0.
5.	Z	7x1 2x2 min
	5x1			2x2	3,
		x1		x2	1,
		3x1		x2	3,
	2x1			x2	4,
	x1		0, x2		0.
7.	Z	2x1		x2	min
	7x1			5x2	28,
	5x1			4x2	7,
		x1		2x2	5,
	x1	0, x2			0.
9.	Z	7x1		x2	min max

x1 x2 3, 5x1 x2 5, x1 5x2 4, x1 4, x2 4.

11. Z x1	3x2	min
x1	x2	3,
4x1	x2	4,
3x1	2x2	24,
5x1	4x2	20,
	x2	6,
x1	0, x2	0.

16

4. Z	x1	2x2			min
2x1		x2	14,
3x1		2x2		9,
3x1		4x2		27,
x1	0, x2			0.
6. Z	x1	x2		max
x1		2x2		4,
5x1		2x2		10,
4x1		3x2		12,
7x1		4x2		28,
x1	0, x2			0.
8. Z	x1	x2		max
3x1		x2		8,
x1		2x2		6,
x1		x2		3,
x1	0, x2			0.
10. Z	2x1		2x2		max
3x1		2x2			6,
	x1	x2		3,
	x1			3,
		x2		5,
	x1	0, x2			0.
12. Z 7x1			2x2		max
	x1	x2		5,
2x1		3x2		6,
3x1		x2		3,
	x1	x2		2,
	x1	x2			3,
	x1	0, x2		0.

17

13. Z

4x1

3x2

x4

x5

max

14. Z

x1

2x3 x5

min

x1

x2

x3

x4

x5

5,

2x1

x2

x3

1,

x1

3x2

x4

13,

x2

x3

x4

x5

2,

4x1

x2

x5

26,

x3

x4

x5 1,

x1

3x2

x6 0,

x j

0,

j

1,...,5.

x j

0,

j

1,...,6.

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

Вид	Запас		Норма расхода
сырья	сырья	P1		P2
S1	120	3		2
S2	40	1		0
S3	30	0		1
Доход от реализации одного изделия		3		2

Составить план производства, обеспечивающий наибольшую прибыль.

16. Человек должен потреблять в сутки некоторое количество питательных веществ. Их содержание в разных видах пищи приведено в таблице:

		Виды пищи
Питательные	Норма
Питательные	Норма	А	Б
вещества		А	Б
вещества
Жиры	10	1	5
Белки	12	3	2
Углеводы	16	2	4
Стоимость 1 усл. ед. вида		2	3
пищи		2	3
пищи

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

4. СИМПЛЕКСНЫЙ МЕТОД

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

Пример 1. Решим задачу симплекс-методом:

	18
Z x1	6x2	max
x1	x2	6,
x1	2x2	4,
2x1	x2	4,
x1	0, x2	0.

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

Z x1	6x2		max
x1	x2		x3		6,
x1	2x2			x4	4,
2x1	x2			x5	4,

x j	0, j	1,5.

Получим каноническую задачу. Неизвестные x3 , x4 , x5 – базисные, x1 , x2 – свободные. Можно записать исходное опорное решение: X 0; 0; 6; 4; 4 .

Составим симплексную таблицу:

Cj	Базис	0	C1=1	C2=6	C3=0	C4=0	C5=0	θ
базиса	Базис	ai0	x1	x2	x3	x4	x5	θ
базиса		ai0	x1	x2	x3	x4	x5
0	x3	6	1	1	1	0	0	6
0	x4	4	1	-2	0	1	0	-
0	x5	4	-2	1	0	0	1	4

	Z =	0	-1	-6	0	0	0
0	x3	2	3	0	1	0	-1	2/3
0	x4	12	-3	0	0	1	2	-
6	x2	4	-2	1	0	0	1	-
	Z =	24	-13	0	0	0	6
1	x1	2/3	1	0	1/3	0	-1/3
0	x4	14	0	0	1	1	1
6	x2	16/3	0	1	2/3	0	1/3
	Z =	98/3	0	0	13/3	0	5/3

Cj – коэффициенты целевой функции. При х1 коэффициент C1=1, при х2 – C2=6, неизвестные х3, х4, х5 отсутствуют в целевой функции, следовательно их коэффициенты равны нулю. В первом столбце таблицы записываются коэффициенты целевой функции, соответствующие базисным неизвестным второго столбца таблицы.

19

Алгоритм симплекс-метода

1.Записываем данную задачу в исходную симплекс-таблицу.

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

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

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

С этой целью:

а) выбираем в исходной таблице разрешающий столбец. Это столбец, соответствующий наименьшей отрицательной оценке. Пусть это столбец, соответствующий переменной x p ;

б) выбираем разрешающую (q-тую) строку из условия

aq0	min	ai0	,	a		0,	(i 1,2,...,m);
aqp		aip			ip

в) элемент aqp – разрешающий;

г) элементы разрешающей строки делим на разрешающий элемент; д) элементы остальных строк вычисляем по правилу «прямоугольника»; е) элементы оценочной строки также вычисляются по правилу

нахождения оценок. Эту формулу можно использовать в качестве контроля вычислений.

Правило нахождения оценок

Оценка для хj равна сумме произведений элементов данного столбца на соответствующие элементы первого столбца (Сj-базисные) минус Сj данного столбца (коэффициент над хj).

Например, в первой части таблицы оценка при х2 равна:

10 2 0 10 6 6 ,

в третьей части таблицы оценка при х3 равна:

1/ 3 1 10 2 / 3 6 0 13 / 3.

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

2 / 3 1 14 0 16 / 3 6 0 98 / 3 .

При решении задачи на максимум опорный план будет оптимальным, если все оценки будут неотрицательными. Исходный опорный план

20

X 0; 0; 6; 4; 4 не будет оптимальным, т.к. оценки при х1 и х2 – отрицательные.

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

Разрешающую строку определяем по наименьшему θ, равному отношению свободных членов ( ai0 ) к соответствующим положительным

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

a10 : a12	6 :1 6,
a30 : a32	4 :1 4.
Наименьшим отношением является	отношение a30 : a32 , следовательно,

a32 =1 – разрешающий элемент. Неизвестное х2 входит в базис вместо х5. Т.о. посредством преобразования однократного замещения мы перешли к лучшему опорному плану X 0; 4; 2;12; 0 , при котором Z 24 . Но этот план также не является оптимальным, т.к. при х3 оценка отрицательная. В третьей части таблицы получен оптимальный план (нет отрицательных

оценок): X опт. 2 / 3;16/3; 0;14; 0 , Zmax 98 / 3.

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

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

( Z ).

Замечание 3. Если требуется найти минимум функции

Z	c1 x1	c2 x2	...	cn xn ,
то можно перейти к задаче максимизации функции
Z1	Z	c1 x1 c2 x2	...	cn xn max .

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

Материал: 5021

Смотрите также: