Материал: 5021

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

опорные оптимальные планы X 1 , X 2 , ..., X k и записать оптимальное решение в виде выпуклой линейной комбинации этих планов:

	k
X опт. t1 X 1 t2 X 2 ... tk X k , где t j 0,		t j 1.
	j	1

Решить симплексным методом:

1.	Z	x1	max
		4x1	3x2	12,
		x1	x2	2,
		x1	x2	2,
		x1,2	0 .
3.	Z	x1	2x2	max

x1 x2 5, 2x1 6, x2 5,

x1,2 0.

5.	Z	x2	x3		max
	x1	x2		x3		1,
		x2		2x3	x4	2,
	x j	0,	j	1,...,4.
7.	Z	2x1		3x2	5x3	min
	2x1	x2		x3		4,
	x1	2x2			x4	12,
	x j	0 , j 1,...,4.
9.	Z	x1	2x2		2x3	x4	max
	x1	x3		0.5x4		1,
	x2 x3				x4	1,
	x j	0,	j	1,...,4.

2. Z	2x1		x2	3x3 2x4			x5	max
	x1	x2	x3			1,
	x1	x2		x4		1,
	x1	x2			x5	1,
	x j	0 , j		1,...,5.
4. Z	4x1		2x2		max
2x1		x2	14,
	x1	x2	10,
	x1		5,
	x1,2	0 .
6. Z	2x1		3x2		5x3	max
x1		x3	1,
	x2	x3		6,
x j		0,	j	1, 2, 3.
8. Z	x1	2x2		x3	2x4	x5		min
x1		2x2		x3		2,
2x1		x2		x4		0,
x1		3x2			x5	6,
x j		0 , j		1,...,5 .
10. Z		x1	2x2		3x3	x4	2x5	min
	x1	3x2		4x3		6,
		2x2		5x3	x4		4,
		x2		2x3	x5		1,
	x j	0,	j	1,...,5.

11. Z

max

12. Z

2x1 2x2

max

2x1

2x2

2x1

2x2

x1,2

13. Z

2x1

3x2

5x3

max

14. Z

2x1

3x2 6x3 3x4

max

2x1

3x2

2x1

2x2

3x3

4x2

2x3

2x4

x j

1, 2, 3.

x j

1,...,4.

15. Z

2x3 2x5

min

16. Z

max

3x2

2x5

2x2

4x3

2x4

4x2

3x3

8x5 x6

3x4

x j

1,...,6.

x j

1,...,5.

5. МЕТОД ИСКУССТВЕННОГО БАЗИСА (М-задача)

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

Рассмотрим задачу в общем виде:

n
	aij x j	ai0	i 1, m ,		(1)
j 1

x j	0( j	1,n),		ai0	0.
	n
Z	c j x j		max.		(2)
	j 1

Пусть система (1) не является системой с базисом. Прибавим к левой части каждого уравнения системы (1) переменную уi ≥ 0, которую назовем искусственной. Система примет вид:

			(3)
aij x j yi ai0 i 1, m .

(3)– система с базисом.

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

n	m
T	c j x j M yi	max.	(4)
j 1	i 1

Задача нахождения максимума функции (4) при ограничениях (3) называется М-задачей.

Замечание 1. Если исходная задача решается на минимум, то целевая функция М-задачи составляется так:

n	m
T	c j x j M yi min.
j 1	i 1

В обоих случаях М может принимать сколь угодно большое положительное значение.

Замечание 2. Искусственные неизвестные следует вводить только в те ограничения, которые не содержат базисных неизвестных.

Связь между решениями исходной и М-задачей устанавливается следующими теоремами.

Теорема 1. Если в оптимальном плане Y 1 , 2 ,..., n , 0,...,0 М-задачи все искусственные переменные равны нулю, то соответствующее решение X 1 , 2 ,..., n исходной задачи также является оптимальным.

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

Алгоритм метода искусственного базиса имеет свои особенности:

1)симплексная таблица имеет две оценочные строки: М-строку и Z- строку. Оценка в М-задаче имеет вид: а + bМ, где М > 0 сколь угодно большое число. Следовательно, знак оценки определяется знаком коэффициента b. Число а записываем в Z-строку (первую строку оценки), а коэффициент b – в М-строку (вторую строку);

2)разрешающий столбец выбирается по оценкам М-строки;

3)если все искусственные переменные вышли из базиса, задача решается дальше обычным симплекс-методом;

4)если М-задача решена, но искусственные переменные не вышли из базиса, то исходная задача решения не имеет.

Пример 1.

Z 5x1		2x2 x3		max
2x1	x2		x3	5,
3x1	2x2		x3	6,
5x1	3x2		4x3	1,
x j	0,	j	1, 2, 3.

Преобразуем систему ограничений к системе уравнений:

2x1	x2	x3 x4	5,
3x1	2x2	x3	6,
5x1	3x2	4x3	x5 1.

Второе и третье ограничения не содержат базисных неизвестных, поэтому мы добавляем искусственные переменные именно в эти уравнения:

2x1	x2	x3 x4		5,
3x1	2x2	x3	y1	6,
5x1	3x2	4x3	x5	y2 1.

Целевая функция М-задачи:

		T 5x1	x2	x3 M y1 y2		max.
Составляем симплексную таблицу:

Сj	Б	0	5		2	-1	0	0	θ
Сj	Б	ai0	x1		x2	x3	x4	x5	θ
		ai0	x1		x2	x3	x4	x5
0	x4	5	2		1	1	1	0	5/2
M	y1	6	3		2	1	0	0	2
M	y2	1	5		3	4	0	-1	1/5
	Z	0	-5		-2	1	0	0
	M	-7	-8		-5	-5	0	1
0	x4	23/5	0		-1/5	-3/5	1	2/5	23/2
M	y1	27/5	0		1/5	-7/5	0	3/5	27/3
5	x1	1/5	1		3/5	4/5	0	-1/5	-
	Z	1	0		1	5	0	-1
	M	-27/5	0		-1/5	7/5	0	-3/5
0	x4	1	0		-1/3	1/5	1	0
0	x5	9	0		1/3	-7/5	0	1
5	x1	2	1		2/3	1/3	0	0
	Z	10	0		4/3	8/3	0	0

		25

Оптимальный план:	X îïò .	2, 0, 0 ,
Оптимальный план:	Z max	10.
	Z max	10.

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

Пример 2.

Z 2x1 3x2 max x1 x2 1,

3x1 2x2 6,

x1,2 0.

Вводим балансовые переменные:

x1	x2 x3	1,
3x1	2x2	x4 6.

Система не каноническая. Составляем М-задачу:

T 2x1		3x2 My		max
x1	x2		x3	1,
3x1	2x2		x4	y 6,
x j	0,	j	1,...,4,
y	0.

Решаем М-задачу симплексным методом:

Сj	Б	ai0	2	3	0	0	θ
Сj	Б	ai0	x1	x2	x3	x4	θ
			x1	x2	x3	x4
0	x3	1	1	1	1	0	1
M	y	6	3	2	0	-1	2
	Z	0	-2	-3	0	0
	M	-6	-3	-2	0	1
2	x1	1	1	1	1	0
M	y	3	0	-1	-3	-1
	Z	2	0	-1	2	0
	M	-3	0	1	3	1

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

Источник: https://studfile.net/preview/16710681/

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





Изложение содержания дела, по которому приняты судебные постановления
_1-тема-СтрМетал
_1966(~1
_files_materials_5053_prog.ntr
_Антонян Ю.М., Сексуальные преступления. Чикатило и другие
_РГР № 1 (2)

Сj	Б	ai0	2	3	0	0	θ
Сj	Б	ai0	x1	x2	x3	x4	θ
			x1	x2	x3	x4
0	x3	1	1	1	1	0	1
M	y	6	3	2	0	-1	2
	Z	0	-2	-3	0	0
	M	-6	-3	-2	0	1
2	x1	1	1	1	1	0
M	y	3	0	-1	-3	-1
	Z	2	0	-1	2	0
	M	-3	0	1	3	1

Сj	Б	ai0	2	3	0	0	θ
Сj	Б	ai0	x1	x2	x3	x4	θ
			x1	x2	x3	x4
0	x3	1	1	1	1	0	1
M	y	6	3	2	0	-1	2
	Z	0	-2	-3	0	0
	M	-6	-3	-2	0	1
2	x1	1	1	1	1	0
M	y	3	0	-1	-3	-1
	Z	2	0	-1	2	0
	M	-3	0	1	3	1

Сj	Б	ai0	2	3	0	0	θ
Сj	Б	ai0	x1	x2	x3	x4	θ
			x1	x2	x3	x4
0	x3	1	1	1	1	0	1
M	y	6	3	2	0	-1	2
	Z	0	-2	-3	0	0
	M	-6	-3	-2	0	1
2	x1	1	1	1	1	0
M	y	3	0	-1	-3	-1
	Z	2	0	-1	2	0
	M	-3	0	1	3	1