Математика \ Математика

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

Страницы работы

32 страницы (Word-файл)

Скачать файл

Фрагмент текста работы

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Омский государственный технический университет»

Исследование операций

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

Омск - 2005

Составитель: Чурашева Надежда Георгиевна, ст. преподаватель

Печатается по решению редакционно-издательского совета Омского

государственного технического университета

Редактор Н. Н. Пацула

ИД 06039 от 12.10.01

Сводный темплан 2005 г.

Подписано в печать 18.06.05 . Формат 60х84 1/16. Бумага офсетная.

Отпечатано на дупликаторе. Усл. печ. л. 2,0. Уч.–изд. л. 2,0.

Тираж 300 экз. Заказ

Издательство ОмГТУ. 644050, Омск, пр-т Мира, 11

Типография ОмГТУ

Типовой расчет

Задание 1. Решить задачу линейного программирования: a) графически, b) симплекс-методом.

1. f(x) = 2x₁+ 4x₂® max

2. f(x) = x₁+ x₂® max

3. f(x) = 3x₁+ 2x₂® max

4. f(x) = 2x₁+ 5x₂® max

5. f(x) = 4x₁+ 5x₂® max

6. f(x) = 2x₁- 3x₂® max

7. f(x) = x₁- x₂® max

8. f(x) = 6x₁+ 5x₂® max

9. f(x) = 2x₁+ 4x₂® max

10. f(x) = 5x₁+ 4x₂® max

11. f(x) = 2x₁+ x₂® max

12. f(x) = x₁+ 3x₂® max

13. f(x) = 7x₁+ 4x₂® max

14. f(x) = 2x₁- x₂® max

15. f(x) = 2x₁- x₂® max

16. f(x) = 3x₁+ 4x₂® max

17. f(x) = x₁- x₂® max

18. f(x) = 5x₁+ 6x₂® max

19. f(x) = 3x₁- x₂® max

20. f(x) = x₁+ x₂® max

21. f(x) = 4x₁+ x₂® max

22. f(x) = 2x₁- x₂® max

23. f(x) = 2x₁+3x₂® max

24. f(x) = x₁- x₂® max

25. f(x) = 3x₁- 2x₂® max

26. f(x) = 5x₁+ 3x₂® max

27. f(x) = 2x₁+ 7x₂® max

28. f(x) = 3x₁+ 5x₂® max

29. f(x) = 4x₁+ 3x₂® max

30. f(x) = 2x₁+ 6x₂® max

Задание 2. Решить задачу линейного программирования симплекс-методом.

1. f(x) = x₁+ x₂+ x₃ - x₄ - 2x₅- 7 ® min

2. f(x) =21 x₁+ 2x₂+ 30x₃ + x₅ ® min

3. f(x) = 2x₁+ x₂+ x₃ - x₄ - 2x₅+ 12 ® min

4. f(x) =2 x₁+ 2x₂+ 3x₃ + x₅ ® min

5. f(x) = 2x₁+ 4x₂+ x₃ - x₄ - 5x₅+ 15® min

6. f(x) = x₁+ 2x₂+ 2x₃ + x₅ ® min

7. f(x) = x₁+ 4x₂+ 2x₃ + 4x₄ - 5x₅® min

8. f(x) = 5x₁+ 2x₂+ 5x₃ + x₅ ® min

9. f(x) = 10x₁+ 4x₂+ 2x₃ + 4x₄ - 5x₅ ® min

10. f(x) = 4x₁+ 2x₂+ 3x₃ + 2x₅ ® min

11. f(x) = x₁+ 4x₂+ 2x₃ - 2x₄ - x₅- 10 ® min

12. f(x) = 3x₁+ 2x₂+ 8x₃ + x₅ ® min

13. f(x) = x₁+ 4x₂+ 2x₃ + 2x₄ + x₅+ 2 ® min

14. f(x) = 4x₁+ 2x₂+ 3x₃ + 5x₅ ® min

15. f(x) = x₁+ 7x₂+ 2x₃ + x₄ + 4x₅- 5 ® min

16. f(x) = 7x₁+ 2x₂- 3x₃ + 5x₅ ® min

17. f(x) = x₁+ 2x₂+ 2x₃ + 9x₄ + 4x₅ ® min

18. f(x) = x₁+ 2x₂- 3x₃ + x₅ ® min

19. f(x) = 5x₁+ 7x₂+ 9x₃ + x₄ + x₅+ 1 ® min

20. f(x) = 2x₁+ 2x₂- 2x₃ + x₅ ® min

21. f(x) = 3x₁+ 2x₂+ x₃ + x₄ + x₅+ 4 ® min

22. f(x) = 8x₁+ 2x₂- 2x₃ + 5x₅ ® min

23. f(x) = 4x₁+ 2x₂+ 3x₃ + x₄ + x₅+ 1 ® min

24. f(x) = 4x₁+ 2x₂- 2x₃ + 3x₅ ® min

25. f(x) = 9x₁+ 2x₂+ 3x₃ + 2x₄ + x₅® min

26. f(x) = - x₁+ 2x₂- 2x₃ + 3x₅ ® min

27. f(x) = 2x₁+ 2x₂+ 3x₃ + 5x₄ + x₅ ® min

28. f(x) = - 4x₁+ 2x₂- 2x₃ + 7x₅ ® min

29. f(x) = 21x₁+ 2x₂+ 30x₃ + 5x₄ + x₅® min

30. f(x) = - 5x₁+ 7x₂- 5x₃ + 8x₅ ® min

Задание 3. Решить задачу линейного программирования симплекс-методом, составить двойственную задачу и найти ее решение.

1. f(x) = 5x₁+ 3x₂+ 2x₃ ® mах

2. f(x) = 4x₁+ 5x₂+ 4x₃ ® mах

3. f(x) = 6x₁+ 4x₂+ x₃ ® mах

4. f(x) = 6x₁- 5x₂+ 4x₃ ® mах

5 f(x) = 2x₁+ 4x₂- x₃ ® mах

6. f(x) = 3x₁- 5x₂+ 4x₃ ® mах

7. f(x) = 5x₁+ 4x₂- 2x₃ ® mах

8. f(x) = 5x₁- 5x₂+ 6x₃ ® mах

9. f(x) = x₁- 2x₂+ 2x₃ ® mах

10. f(x) = 9x₁- 5x₂+ 8x₃ ® mах

11. f(x) = 5x₁- 5x₂+ 6x₃ ® mах

12. f(x) = x₁- 5x₂+ x₃ ® mах

13. f(x) = -5x₁+ 7x₂+ 6x₃ ® mах

14. f(x) = x₂+ x₃ ® mах

15. f(x) = -3x₁+ 5x₂+ 6x₃ ® mах

16. f(x) = 10x₁ - 3x₂+ 2x₃ ® mах

17. f(x) = - x₁+ x₂+ 2x₃ ® mах

18. f(x) = x₁ - 3x₂+ 2x₃ ® mах

19. f(x) = - x₁+ 3x₂+ 2x₃ ® mах

20. f(x) = 7x₁ - 3x₂+ 8x₃ ® mах

21. f(x) = - 7x₁+ 8x₂+ 7x₃ ® mах

22. f(x) = 4x₁ - x₂+ 4x₃ ® mах

23. f(x) = - 9x₁+ 5x₂+ 4x₃ ® mах

24. f(x) = 2x₁ - x₂+ 5x₃ ® mах

25. f(x) = - 4x₁+ 8x₂+ 7x₃ ® mах

26. f(x) = 2x₁ - 5x₂+ 3x₃ ® mах

27. f(x) = 4x₁+ 5x₂+ 7x₃ ® mах

28. f(x) = 2x₁ + 8x₂+ 3x₃ ® mах

29. f(x) = 5x₁+ 5x₂+ 6x₃ ® mах

30. f(x) = 5x₁ + 4x₂+ 3x₃ ® mах

Задание 4. Решить целочисленную задачу методом Гомори.

1. f(x) = 3x₁+ 4x₂® max

2. f(x) = 7x₁+ x₂® max

3. f(x) = 3x₁+ 2x₂® max

4. f(x) = 2x₁+ 15x₂® max

5. f(x) = 4x₁+ 5x₂® max

6. f(x) = 2x₁- 3x₂® max

7. f(x) = 9x₁+ 7x₂® max

8. f(x) = 7x₁+ 10x₂® max

9. f(x) = x₁+ 3x₂® max

10. f(x) = 5x₁+ 4x₂® max

11. f(x) = x₁+ 2x₂® max

12. f(x) = 2x₁- x₂® max

13. f(x) = 3x₁+ 2x₂® max

14. f(x) = x₁- x₂® max

15. f(x) = 7x₁+ 6x₂® max

16. f(x) = 3x₁- x₂® max

17. f(x) = 2x₁+ x₂® max

18. f(x) = 4x₁+ x₂® max

19. f(x) = 4x₁- x₂® max

20. f(x) = 2x₁+9x₂® max

21. f(x) = x₁- x₂® max

22. f(x) = 3x₁- 2x₂® max

23. f(x) = 5x₁+ 3x₂® max

24. f(x) = 11x₁+ 7x₂® max

25. f(x) = 3x₁+ 5x₂® max

26. f(x) = 4x₁+ 3x₂® max

27. f(x) = 2x₁+ 6x₂® max

28. f(x) = 9x₁+ 5x₂® max

29. f(x) = 9x₁+ 5x₂® max

30. f(x) = 5x₁+ 4x₂® max

Задание 5. Решить транспортную задачу.

		В 1						В 2
	B1	B2	B3	B4			B1	B2	B3	B4
A1	1	8	2	10	190	A1	2	2	5	1	140
A2	20	21	7	8	120	A2	1	8	11	1	190
A3	7	11	5	9	240	A3	9	8	7	2	230
	210	120	170	50			120	210	190	40
		В 3						В 4
	B1	B2	B3	B4			B1	B2	B3	B4
A1	3	3	3	2	200	A1	4	3	2	5	250
A2	1	7	5	11	180	A2	22	2	5	8	130
A3	4	3	9	3	190	A3	10	16	22	3	230
	130	230	80	130			70	230	240	70
		В 5						В 6
	B1	B2	B3	B4			B1	B2	B3	B4
A1	5	1	1	2	25	A1	6	3	14	10	25
A2	7	2	4	3	13	A2	3	15	4	5	13
A3	4	7	2	4	23	A3	8	11	5	2	25
	7	23	24	7			16	20	20	7
		В 7						В 8
	B1	B2	B3	B4			B1	B2	B3	B4
A1	7	12	5	9	50	A1	8	10	5	11	10
A2	4	2	9	21	30	A2	7	6	4	5	30
A3	12	3	4	7	35	A3	7	2	8	2	35
	15	25	25	50			5	30	20	20
		В 9						В 10
	B1	B2	B3	B4			B1	B2	B3	B4
A1	9	15	10	1	10	A1	10	8	12	18	20
A2	3	8	3	2	30	A2	23	1	4	25	20
A3	6	2	5	8	25	A3	25	18	4	6	25
	15	10	15	25			15	20	10	20
		В 11						В 12
	B1	B2	B3	B4			B1	B2	B3	B4
A1	11	9	4	4	30	A1	12	18	23	14	15
A2	5	7	10	5	10	A2	4	5	3	16	25
A3	3	5	4	6	65	A3	11	8	17	4	35
	30	10	5	60			25	20	15	15
		В 13						В 14
	B1	B2	B3	B4			B1	B2	B3	B4
A1	13	8	20	10	10	A1	14	10	25	10	45
A2	22	2	7	8	12	A2	12	8	11	15	95
A3	7	11	5	9	24	A3	9	8	7	12	23
	21	5	15	5			33	50	35	45
		В 15						В 16
	B1	B2	B3	B4			B1	B2	B3	B4
A1	15	11	3	22	20	A1	10	3	2	5	45
A2	10	10	5	11	80	A2	2	2	5	8	100
A3	14	22	11	22	90	A3	10	6	2	3	55
	35	20	85	50			45	60	50	45
		В 17						В 18
	B1	B2	B3	B4			B1	B2	B3	B4
A1	17	15	10	11	10	A1	18	8	12	18	20
A2	9	8	14	12	30	A2	9	16	4	5	20
A3	6	12	15	8	25	A3	25	18	14	6	25
	15	10	15	25			15	20	10	20
		В 19						В 20
	B1	B2	B3	B4			B1	B2	B3	B4
A1	19	9	6	7	30	A1	20	18	23	14	25
A2	5	7	10	9	20	A2	14	5	12	16	25
A3	8	5	8	6	65	A3	11	8	17	14	35
	30	10	15	60			25	20	25	15
		В 21						В 22
	B1	B2	B3	B4			B1	B2	B3	B4
A1	21	8	9	10	30	A1	22	10	15	10	45
A2	11	2	7	8	12	A2	12	8	11	15	95
A3	7	12	5	9	24	A3	9	8	17	12	50
	21	15	15	15			40	60	35	55
		В 23						В 24
	B1	B2	B3	B4			B1	B2	B3	B4
A1	23	11	14	22	50	A1	24	3	12	5	40
A2	10	10	15	11	80	A2	2	12	5	8	100
A3	14	22	11	12	90	A3	10	6	2	3	60
	35	50	85	50			40	60	50	50
		В 25						В 26
	B1	B2	B3	B4			B1	B2	B3	B4
A1	25	15	10	1	30	A1	26	8	12	18	40
A2	3	8	3	2	30	A2	23	12	4	25	20
A3	6	2	5	8	25	A3	25	18	4	6	25
	15	20	25	25			25	20	20	20
		В 27						В 28
	B1	B2	B3	B4			B1	B2	B3	B4
A1	27	9	4	4	30	A1	28	8	23	4	45
A2	5	7	10	5	30	A2	4	5	3	6	25
A3	3	5	4	6	65	A3	11	8	7	4	35
	30	10	25	60			25	20	25	35
		В 29						В 30
	B1	B2	B3	B4			B1	B2	B3	B4
A1	29	8	10	10	30	A1	30	10	5	10	45
A2	12	2	7	8	42	A2	12	8	11	5	85
A3	7	11	5	9	24	A3	9	8	7	12	23
	21	25	15	35			33	40	35	45

Задание 6. Дана платежная матрица игры. Найти седловые точки и оптимальные стратегии игроков.

1.	9	8	10	10	2.	2	8	10	10
	12	2	7	8		1	2	7	8
	7	7	5	9		0	1	5	9
3.	12	8	8	10	4.	9	8	10	5
	12	2	7	8		12	2	7	4
	7	11	5	9		7	11	5	0
5.	4	6	0	3	6.	9	8	1	6
	1	7	7	8		2	2	7	5
	7	7	8	9		7	11	8	6
7.	6	8	5	10	8.	19	18	10	10
	12	7	7	8		12	2	7	8
	7	11	5	9		7	11	5	9
9.	5	7	1	1	10.	20	8	6	8
	12	7	7	8		12	2	3	8
	7	1	5	9		7	11	5	9
11.	6	8	4	9	12.	21	8	9	5
	12	2	3	8		12	2	7	5
	7	11	3	9		7	7	5	4
13.	7	8	9	10	14.	22	18	17	10
	7	9	7	8		12	2	27	8
	7	11	5	9		17	11	5	9
15.	8	8	10	10	16.	23	18	10	10
	12	8	7	8		12	12	1	18
	7	6	5	9		7	11	5	9
17.	9	8	6	5	18.	24	8	3	2
	2	2	7	4		12	2	3	8
	7	1	5	0		12	14	3	3
19.	10	10	10	10	20.	25	28	100	10
	12	10	17	18		12	2	10	8
	17	11	15	19		70	10	5	9
21.	11	8	11	11	22.	26	18	16	9
	12	2	7	8		12	2	7	8
	17	11	15	11		10	11	12	9
23.	12	18	18	12	24.	27	12	14	10
	12	2	7	8		12	12	17	18
	7	11	12	9		7	11	5	12
25.	13	8	5	4	26.	28	7	4	5
	4	2	3	2		12	2	4	8
	7	4	5	3		7	11	5	9
27.	14	10	10	12	28.	29	28	20	20
	12	2	1	8		12	20	7	8
	7	11	5	10		20	11	5	9
29.	15	7	1	1	30.	30	15	5	40
	12	6	6	8		12	9	7	8
	17	1	5	6		10	11	9	9

Задание 7. Дана платежная матрица игры. Решить графически игру.

1.	2.	3.
4.	5.	6.
7.	8.	9.
10.	11.	12.
13.	14.	15.
16.	17.	18.
19.	20.	21.
22.	23.	24.
25.	26.	27.
28.	29.	30.

Задание 8. Дана платежная матрица игры. Найти решение игры путем сведения ее к задаче линейного программирования.

1.	2.	3.
4.	5.	6.
7.	8.	9.
10.	11.	12.
13.	14.	15.
16.	17.	18.
19.	20.	21.
22.	23.	24.
25.	26.	27.
27.	29.	30.

Примеры решения заданий

Задачи линейного программирования

Пример 1. Решить ЗЛП f(x) = 3x₁+ 2x₂® max

x₁+ x₂£ 4,

2x₁+ x₂£ 6,

x₁³ 0, x₂³ 0,

a) графически, b) симплекс-методом.

a) Шаг 1. Строится множество D допустимых решений задачи, оно представляет собой четырехугольник ОABC на плоскости x₁Оx₂ с вершинами в точках О, А, В, С, с координатами (0; 0), (0; 4), (2; 2), (3; 0), соответственно.

Шаг 2. Из начала координат откладывается вектор-градиент функции f(x), указывающий направления ее возрастания.

Шаг 3. Строится прямая 3x₁+ 2x₂= const– линия уровня функции f(x), перпендикулярная вектору градиента .

Шаг 4. Линия уровня 3x₁+ 2x₂= constпередвигается в направлении вектора до тех пор, пока она не покинет область D. Крайняя точка области, в которой линия уровня покидает допустимую область, и является решением задачи. В данном случае – это точка В(2; 2).

Шаг 5.Находится оптимальное значение функции.

f ^*(2; 2) = 3x₁+ 2x₂ = 3 × 2+ 2 × 2 = 10.

b) Шаг 1. Задача приводится к специальному виду, для этого к левым частям неравенств прибавляются дополнительные переменные x₃ и x₄, превращающие неравенства в равенства.

f(x) = 3x₁+ 2x₂® max

x₁+ x₂+ x₃= 4,

2x₁+ x₂+ x₄= 6,

x_j³ 0,

Переменные x₃и x₄входят в первое и второе уравнения соответственно с коэффициентами единица, тогда х₃, х₄– начальный базис, x₁ , x₂– свободные переменные, b– вектор ограничений.

Шаг 2. Составляется соответствующая симплекс - таблица:

базис	свободные			Отноше- ние
	x₁	x₂	b
x₃	1	1	4	4
x₄	2	1	6	3 Ü min
f(x)	-3	-2	0
	Ýmin

Так как свободные переменные всегда равны нулю, то для данного начального базиса f(x) будет равна нулю:

f(x) = с₀- åc_iх_i= 0 × 2 + 0 × 6 = 0.

Так как имеются с_j< 0, приступаем к улучшению плана.

Шаг 3. Выбирается разрешающий j-й столбец, соответствующий наименьшему отрицательному с_j.

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

Шаг 5. Находится разрешающий элемент, он расположен на пересечении разрешающей строки и разрешающего столбца (в нашем случае он равен 2).

Шаг 6. Определяются переменные, которые будут исключены из базиса и включены в него. Переменную, которой соответствует разрешающий столбец, включаются в базис вместо переменной, которой соответствует разрешающая строка. В базис вводим переменную x₁, которому соответствует минимальное значение c_j. Из базиса выводится x₄, так как минимальное q достигается в этой строке формулой .

Таким образом, элемент a₄₁будет разрешающим (в таблице выделен серым цветом).

Шаг 7. Заполняем таблицу, соответствующую новому базисному решению.

		*свободные*			q
	*базис*	х₄	х₂	b	q
	х₃	- 0,5	0,5	1	0,5 / 1Ü min
	х₁	0,5	0,5	3	0,5 / 3
f(x)		1,5	- 0,5	9
			Ýmin

Шаг 8. Так как в строке f(x) оценок полученного нового плана имеется отрицательное значение с_j, приступаем к следующей итерации, продолжая улучшать план.

б\с	x₄	x₃	b
x₂			2
x₁			2
f(x)	1	1	10

Поскольку все с_j³ 0, то план, представленный в данной таблице, будет оптимальным.

Ответ: f ^*(x) =10; x₁^*= 0; x₂^*= 6

Пример 2. Решить каноническую задачу линейного программирования:

f(Х) = х₁- 2х₂- 2x₃® max

x₁ + 4x₂ + x₃ = 5,

x₁ - 2x₂ - x₃ = -1,

x_j³ 0,

Данная каноническая задача линейного программирования (КЗЛП) не является специальной (СЗЛП), поэтому применяем метод искусственного базиса. Строим вспомогательную задачу линейного программирования и приводим ее к специальному виду, выражая целевую функцию через небазисные переменныеx_j, j=1,…,3. Эта задача имеет вид:

h(Х) = – ( t₁+ t₂) = – 6 + 6 x₂+ 2 x₃® max

x₁ + 4x₂ + x₃+ t₁ = 5,

x₁ - 2x₂ - x₃+ t₂ = -1, все x_j ≥ 0, t_i ≥ 0.

Решаем специальную задачу линейного программирования симплекс