методичка МО часть 1

Министерство образования Республики Беларусь

Учреждение образования «Гомельский государственный университет

имени Франциска Скорины»

Т. П. Бышик, В. Л. Мережа

МЕТОДЫ ОПТИМИЗАЦИИ: ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Гомель 2015

Министерство образования Республики Беларусь

Учреждение образования «Гомельский государственный университет

имени Франциска Скорины»

Т. П. Бышик, В. Л. Мережа

МЕТОДЫ ОПТИМИЗАЦИИ: ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Практическое руководство для лабораторных занятий

для студентов специальности 1-31 03 03 Прикладная математика (по направлениям),

1-31 03 06-01 Экономическая кибернетика

Гомель ГГУ им. Ф. Скорины

2015

2

доцент кафедры прикладной математики УО

УДК

ББК

С

Рецензенты:

заведующий кафедрой вычислительной математики и программирования учреждения образования «Гомельский государственный университет имени Франциска Скорины», кандидат физико-математических наук, доцент Д.С. Кузьменков; кандидат технических наук, «БелГУТ» С.И. Жогаль.

Рекомендовано к изданию учебно-методическим советом учреждения образования «Гомельский государственный университет имени Франциска Скорины»

Бышик Т. П.

Методы оптимизации: Линейное программирование. Практ. рукво / В. Л. Мережа; М–во образования РБ, Гомельский гос. ун-т им. Ф. Скорины. – Гомель: ГГУ им. Ф. Скорины, 2015. – с.

ISBN XXX-XXX-XXX-XXX-X

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

Целью руководства является оказание помощи студентам специальности 1-31 03 03-01 «Прикладная математика (по направлениям и 1-31 03 03-06 Экономическая кибернетика в выполнении лабораторных работ.

УДК

ББК

ISBN XXX-XXX-XXX-XXX-X

© Бышик Т. П., Мережа В. Л.; 2015 © УО «Гомельский государственный университет имени Франциска Скорины», 2015

3

Лабораторная работа 1

Графический метод решения задач линейного программирования

Вопросы:

1.Постановка задачи оптимизации.

2.Определение оптимального плана.

3.Определение локального оптимального плана.

4.Определение минимизирующей последовательности.

5.Постановка производственной задачи.

Метод применим к задачам линейного программирования с двумя переменными:

z c x c														x	2	max(min)
				1	1							2
a		x		a		21		x			2			b ,
11			1													1
a	21	x		a		22			x			2		b ,
			1													2
..........................
a	m1		x	a			m 2			x			2		b
			1													m

(1.1)

(1.2)

Алгоритм

1. В декартовой системе координат на плоскости строим множество Х планов задачи как пересечение m полуплоскостей, задаваемых линейными неравенствами системы (1.2). При этом возможен один из случаев:

а) Х – пустое множество; б) Х – выпуклый многоугольник;

в) Х – выпуклая неограниченная многоугольная область.

Если а), то задача не имеет решения; если б) или в) – переходим к п.2.

2. По целевой функции Z строим вектор

c
c	1
c2

(градиент целевой

функции), через начало координат проводим прямую Z0			(линию нулевого
уровня целевой функции):	c1 x1 c2 x2 0.
3. При решении задачи максимизации (минимизации) прямую Z0
перемещаем параллельно	в направлении вектора	c	(вектора – c ) в

наиболее отдалённую точку А (точку В) множества планов Х. Координаты точки А (точки В) и составляют оптимальный план задачи максимизации (минимизации) функции Z на множестве Х.

Если множество Х – ограничено, то задача всегда имеет решение. Если же Х – неограниченная многоугольная область, то задача может не

4

иметь решения в случае, когда не существует наиболее удалённой точки, т.е. целевая функция неограниченно возрастает (убывает) на Х.

Если задача имеет оптимальный план, то он достигается либо в одной из вершин границы множества Х, либо на одной из её сторон (альтернативный оптимум).

Замечание

Некоторые задачи линейного программирования с числом переменных n>2 могут быть сведены к эквивалентным линейным задачам с двумя переменными. Для этого систему ограничений-равенств исходной задачи приводим к единичному базису. Определяем из неё базисные переменные (эти выражения называют уравнениями связи). Подставляем их в целевую функцию и ограничения-неравенства задачи. После решения полученной эквивалентной задачи с двумя переменными, решение исходной задачи (базисные переменные) находят из уравнений связи.

Пример. Решить графическим методом задачу:

z 2x				x			2		x				3	3x	4	max(min)
			1
x	x	2	x			x					4		1,
1					3
x	5x		2	x		3		x				4		3,
1
6x 2x				2	x				3			1,
	1
x	0, i 1,4.
i

Решение

1. Приводим систему ограничений-неравенств к единичному базису

1	1	1 1	1	1		1	1	1	1		0		3 1	0	1
											
	5	1 1			2	4	0	2	4			1	2 0	1	2
1			3

Уравнения связи имеют вид:

x3 1 3x2 , x4 2 2x2 x1

2. Исключаем базисные переменные х3, х4 из задачи (1.3):

(1.3)

(1.4)

5

z 2x						x			2	( 1 3x		) 3(2 2x	2	x ) x		2x	2	5,
					1						2			1	1
6x			2x				2	( 1 3x			) 1,
	1									2
6x			x			2	2,
	1
1 3x2 0,
x				1	,
	2			3
2 2x					2	x				0,
								1
x	2x					2	2.
1

3. Обозначив u=z–5, получаем задачу (1.5) эквивалентную задаче (1.3):

u x							2x	2	max(min)
					1
6x			x			2	2,
		1
x		2x				2	2,
1
x			0,
1
x				1	.
	2			3

(1.5)

4. На плоскости х1Ох2 строим множество Х планов задачи (1.5), вектор

		1
c				, линию нулевого уровня u=0 и линии уровней u=umax, u=umin,
		2

(см. Рисунок):

6

Рисунок – Графическое решение задачи (1.5)

5. Анализ. Область Х – четырёхугольник ABCD. В точке А (0,

	функция u имеет максимальное значение umax = u (0,	1	) = –	2
		3		3

1 3

.

) целевая

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

	Имеем точки с координатами: В (0, 1) и С ( 2			,		10	).
					11
			11
	~	~	произвольной точки отрезка ВС можно записать в виде:
	Координаты x 1	, x2

		2		2	,
		11		11

	~		x1B
	x1
	~		x2 B
	x2
1				10
11				11

(1 )x1C 112 112 ,

(1 )x2C 111 1011 ,

–общее решение задачи минимизации функции u.

Используя решение задачи (1.5) и уравнения (1.4), получаем решение исходной задачи (1.3):

	х1=0, х2=	1	,	х3=0, х4=	4	– оптимальный план задачи максимизации.
		3			3
						7

~			2		2	,	~			1			10	,	~			3		19	,	~		0,	[0, 1]
x							x	2							x							x	4
1		11			11					11			11		3			11		11
оптимальный план задачи минимизации.
Ответ:			Zmax= 4,				Xmax= (0,					1	, 0,		4	),			Zmin= 3 на отрезке.
												3			3

–

Задание. Графическим методом решить следующие задачи:

1. z x1 x2 x3 max(min) 4x1 x2 x3 6,

3x1 x2 x4 2, x2 2x3 x4 1, xi 0, i 1, 4

3. z x						3x		2	4x 2x				4	max(min)
				1								3
x	2x			2		3x			x	4		1,
1							3
3x			2x		2		x		x	4		1,
	1						3
2x		2	3x			3	x		x		4	1,
							3
x	0, i 1, 4
i

5. z x	x	2	x	3	x	4	max(min)
1

2x1 x2 3x3 2x4 2,

3x1 2x2 x3 x4 3, xi 0, i 1, 3, 4

7. z x1 2x2 3x4 max(min)

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

2x1 x2 3x3 2, xi 0, i 1, 4

2. z 2x									x					2		x			4			max(min)
							1
2x				x		2	x						x					4	2,
		1									3
3x x								2	x						4		1,
				1
2x			2	x			x					4		3,
						3
x	i	0, i 1, 4
4. z 2x											x						2	x				3	max(min)
									1
2x				2x			2		x				3			3x				4			20,
		1
x	2		x			2,
					5
x	2		3x				x					4	8,
						3
x	i	0, i 1, 5
6. z x							2x							2		3x					4		max(min)
						1
x		2x				2	x					4	4,
1
x		x			2	x				3		5,
1
2x				x		2	x					4	7,
		1
x	i	0, i 1, 4
8. z x									x						2		x					x		4	max(min)
								1											3
2x				x		2	x					3	x					4	4,
		1
3x				2x			2		4x							3	x			4			1,
		1
x	i	0, i 1, 3, 4

8

9. z 2x					3x			2	x	4	max(min)
				1
x	x	2	x			4	2,
1
2x 5x				2	x 10,
	1						3
2x		5x				2	x		10,
	1							5
x	0, i 1, 5
i

10. z x	x	2	3x	4	3x	4	max(min)
1

2x1 3x2 2x4 6,

4x1 x3 4x4 4, x1 x2 x3 1,

x	i	0, i 1, 4

11. z 4x							2x			2	x				x	4	max(min)
						1									3
x x			2	11x				2x				4		2,
1							3
3x	2x				2	x		4x					4		3,
1							3
x		2x				2	x	4	2,
1

x	i	0, i 1, 4
13. z 4x										3x					2	x			4
								1
2x			x			2	x		3		1,
		1
x		3x			2		x		4		13,
1
4x			x			2	x				26,
		1							5
x		3x			2		x		6		0,
1
x	i	0, i 1, 6
15. z x x											2	x				3	x			4
							1
2x			x			2	x				x			4		3,
		1							3
x		x		2		5x			4		2,
1
x		2x				2	x		4		1,
1
x	i	0, i 1, 5
17. z 5x								x				2	x				3
							1
x		x		3		x		4		8,
1
x	2	2x					5x				4	3,
						3
2x			x			2	x				1,
		1							3
x	i	0, i 1, 4

x	5	max(min)

max(min)

max(min)

9

12. z x 2x								2	4x			max(min)
				1								3
2x		x	2	x		4	1,
	1
3x		x		2x			4	2,
1		3
4x		x	2	x		4	2,
	1
x	0,			i 1, 4
i
14. z x 2x								2	x		3	max(min)
				1
x	2x		2	3x			3	x		4	20,
1
x	x		3x		4		8,
1		3
x	x		2,
1		5
x	0, i 1, 5
i

16. z 3x						2x						2		x		4	max(min)
					1
x		2x		2	x		4	4,
1
x	2	x		x		4	5,
			3
x 2x x									4		2,
		1			3
x	i	0, i 1, 4
18. z x 3x										2		x			3	max(min)
					1
x		2x		3	x		4	1,
1
x		x	2	x			x				4		2,
1					3
x		x	3	2x			4	1,
1
x	i	0, i 1, 4

19. z 3x 2x								2	x	3	max(min)
					1
x		x	2		x		2,
1					3
5x	2x			2	x	4	10,
1
5x	2x				x	5	10,
1			3
x 0, i 1, 5
i

21. z
x	2x		2
1
x	2x		2
1
2x		x	2
	1
x	0, i
i

x	x	2	2x	3	max(min)
1

x3 10,

x4 2,

x4 13,

1, 4

20. z x							x			2		2x					x	4	max(min)
					1											3
x		2x				2		x					x		4	2,
	1									3
x	3x				1,
1			3
x	x		2	x				3	4,
1
x	0, i 1, 4
i
22. z x							3x					2		x		3	x	4	max(min)
					1
3x		5x			2		x				15,
1									3
5x		2x			2		2x				4			10,
1
x		2x				2		x						3,
	1									5
x	2x			2	1,
1
x	0, i 1, 5
i

23. z 2x	4x	2	3
1

x1 3x2 2x3 x4

x1 x2 2x3 3x4 x1 x2 3x3 2x4

x	i	0, i 1, 4

x	3	x	4	max(min)

1,

1,

1,

24. z x	x	3	x	4	max(min)
1

x1 4x3 x4 6, x2 9x3 8x4 72,

3x1 11x4 x5 16,

x	i	0, i 1, 5

25. z 5x						3x			2	x	2x	4	max(min)
				1						3
2x		3x			2	x				3,
	1							3
x	7x		2	2x			4			4,
1
x	x	2	x			1,
1					3
x	0, i 1, 4
i

10

26. z x					x					2	x	4	x	5	max(min)
				1
2x	x		2	x		3		2,
1
3x	x	2		x	5			5,
1
3x	x	3		4x			6		6,
1
4x	x		2	4x				6	3,
1
x 0, i				1, 6
i