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

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

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

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

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

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

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

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

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

Омск - 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) = 2x1 + 4x2 ® max

2. f(x) = x1 + x2 ® max

3. f(x) = 3x1 + 2x2 ® max

4. f(x) = 2x1 + 5x2 ® max

5. f(x) = 4x1 + 5x2 ® max

6. f(x) = 2x1 - 3x2 ® max

7. f(x) = x1 - x2 ® max

8. f(x) = 6x1 + 5x2 ® max

9. f(x) = 2x1 + 4x2 ® max

10. f(x) = 5x1 + 4x2 ® max

11. f(x) = 2x1 + x2 ® max

12. f(x) = x1 + 3x2 ® max

13. f(x) = 7x1 + 4x2 ® max

14. f(x) = 2x1 - x2 ® max

15. f(x) = 2x1 - x2 ® max

16. f(x) = 3x1 + 4x2 ® max

17. f(x) = x1 - x2 ® max

18. f(x) = 5x1 + 6x2 ® max

19. f(x) = 3x1 - x2 ® max

20. f(x) = x1 + x2 ® max

21. f(x) = 4x1 + x2 ® max

22. f(x) = 2x1 - x2 ® max

23. f(x) = 2x1 +3x2 ® max

24. f(x) = x1 - x2 ® max

25. f(x) = 3x1 - 2x2 ® max

26. f(x) = 5x1 + 3x2 ® max

27. f(x) = 2x1 + 7x2 ® max

28. f(x) = 3x1 + 5x2 ® max

29. f(x) = 4x1 + 3x2 ® max

30. f(x) = 2x1 + 6x2 ® max

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

1. f(x) = x1 + x2 + x3 - x4 - 2x5  - 7 ® min

2. f(x) =21 x1 + 2x2 + 30x3  + x ® min

3. f(x) = 2x1 + x2 + x3 - x4 - 2x+ 12 ® min

4. f(x) =2 x1 + 2x2 + 3x3  + x ® min

5. f(x) = 2x1 + 4x2 + x3 - x4 - 5x+ 15® min

6. f(x) = x1 + 2x2 + 2x3  + x ® min

7. f(x) = x1 + 4x2 + 2x3 + 4x4 - 5x® min

8. f(x) = 5x1 + 2x2 + 5x3  + x ® min

9. f(x) = 10x1 + 4x2 + 2x3 + 4x4 - 5x ® min

10. f(x) = 4x1 + 2x2 + 3x3  + 2x ® min

11. f(x) = x1 + 4x2 + 2x3 - 2x4 - x- 10 ® min

12. f(x) = 3x1 + 2x2 + 8x3  + x ® min

13. f(x) = x1 + 4x2 + 2x3 + 2x4 + x+ 2 ® min

14. f(x) = 4x1 + 2x2 + 3x3  + 5x ® min

15. f(x) = x1 + 7x2 + 2x3 + x4 + 4x- 5 ® min

16. f(x) = 7x1 + 2x2 - 3x3  + 5x ® min

17. f(x) = x1 + 2x2 + 2x3 + 9x4 + 4x ® min

18. f(x) = x1 + 2x2 - 3x3  + x ® min

19. f(x) = 5x1 + 7x2 + 9x3 + x4 + x+ 1 ® min

20. f(x) = 2x1 + 2x2 - 2x3  + x ® min

21. f(x) = 3x1 + 2x2 + x3 + x4 + x+ 4 ® min

22. f(x) = 8x1 + 2x2 - 2x3  + 5x ® min

23. f(x) = 4x1 + 2x2 + 3x3 + x4 + x+ 1 ® min

24. f(x) = 4x1 + 2x2 - 2x3  + 3x ® min

25. f(x) = 9x1 + 2x2 + 3x3 + 2x4 + x® min

26. f(x) = - x1 + 2x2 - 2x3  + 3x ® min

27. f(x) = 2x1 + 2x2 + 3x3 + 5x4 + x5  ® min

28. f(x) = - 4x1 + 2x2 - 2x3  + 7x ® min

29. f(x) = 21x1 + 2x2 + 30x3 + 5x4 + x® min

30. f(x) = - 5x1 + 7x2 - 5x3  + 8x ® min

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

1. f(x) = 5x1 + 3x2 + 2x3  ® mах

2. f(x) = 4x1 + 5x2 + 4x3  ® mах

3. f(x) = 6x1 + 4x2 + x3 ® mах

4. f(x) = 6x1 - 5x2 + 4x3  ® mах

5 f(x) = 2x1 + 4x2 - x3 ® mах

6. f(x) = 3x1 - 5x2 + 4x3  ® mах

7. f(x) = 5x1 + 4x2 - 2x3 ® mах

8. f(x) = 5x1 - 5x2 + 6x3  ® mах

9. f(x) = x1 - 2x2 + 2x3 ® mах

10. f(x) = 9x1 - 5x2 + 8x3  ® mах

11. f(x) = 5x1 - 5x2 + 6x3 ® mах

12. f(x) = x1 - 5x2 + x3  ® mах

13. f(x) = -5x1 + 7x2 + 6x3 ® mах

14. f(x) = x2 + x3  ® mах

15. f(x) = -3x1 + 5x2 + 6x3 ® mах

16. f(x) = 10x1 - 3x2 + 2x3  ® mах

17. f(x) = - x1 + x2 + 2x3 ® mах

18. f(x) = x1 - 3x2 + 2x3  ® mах

19. f(x) = - x1 + 3x2 + 2x3 ® mах

20. f(x) = 7x1 - 3x2 + 8x3  ® mах

21. f(x) = - 7x1 + 8x2 + 7x3 ® mах

22. f(x) = 4x1 - x2 + 4x3  ® mах

23. f(x) = - 9x1 + 5x2 + 4x3 ® mах

24. f(x) = 2x1 - x2 + 5x3  ® mах

25. f(x) = - 4x1 + 8x2 + 7x3 ® mах

26. f(x) = 2x1 - 5x2 + 3x3  ® mах

27.  f(x) = 4x1 + 5x2 + 7x3 ® mах

28. f(x) = 2x1 + 8x2 + 3x3  ® mах

29. f(x) = 5x1 + 5x2 + 6x3 ® mах

30. f(x) = 5x1 + 4x2 + 3x3  ® mах

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

1. f(x) = 3x1 + 4x2 ® max

2. f(x) = 7x1 + x2 ® max

3. f(x) = 3x1 + 2x2 ® max

4. f(x) = 2x1 + 15x2 ® max

5. f(x) = 4x1 + 5x2 ® max

6. f(x) = 2x1 - 3x2 ® max

7. f(x) = 9x1 + 7x2 ® max

8. f(x) = 7x1 + 10x2 ® max

9. f(x) = x1 + 3x2 ® max

10. f(x) = 5x1 + 4x2 ® max

11. f(x) = x1 + 2x2 ® max

12. f(x) = 2x1 - x2 ® max

13. f(x) = 3x1 + 2x2 ® max

14. f(x) = x1 - x2 ® max

15. f(x) = 7x1 + 6x2 ® max

16. f(x) = 3x1 - x2 ® max

17. f(x) = 2x1 + x2 ® max

18. f(x) = 4x1 + x2 ® max

19. f(x) = 4x1 - x2 ® max

20. f(x) = 2x1 +9x2 ® max

21. f(x) = x1 - x2 ® max

22. f(x) = 3x1 - 2x2 ® max

23. f(x) = 5x1 + 3x2 ® max

24. f(x) = 11x1 + 7x2 ® max

25. f(x) = 3x1 + 5x2 ® max

26. f(x) = 4x1 + 3x2 ® max

27. f(x) = 2x1 + 6x2 ® max

28. f(x) = 9x1 + 5x2 ® max

29. f(x) = 9x1 + 5x2 ® max

30. f(x) = 5x1 + 4x2 ® 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) = 3x1 + 2x2 ® max

x1 + x2 £ 4,

 2x1 + x2 £ 6,

   x1 ³ 0, x2 ³ 0,

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

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

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

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

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

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

f *(2; 2) = 3x1 + 2x2 = 3 × 2 + 2 × 2 = 10.

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

         f(x) = 3x1 + 2x2 ® max

x1 + x2 + x3 = 4,

2x1+ x2 + x4 = 6,

    xj ³ 0,

Переменные x3 и x4 входят в первое и второе уравнения соответственно с коэффициентами единица, тогда х3 , х4  – начальный базис,  x1 , x2  – свободные переменные, b  – вектор ограничений.

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

базис

свободные

Отноше-

ние

x1

x2

b

x3

1

1

4

4

x4

2

1

6

3 Ü min

f(x)

-3

-2

0

Ýmin

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

f(x) = с0 - åci хi = 0 × 2 + 0 × 6 = 0.

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

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

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

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

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

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

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

свободные

q

базис

х4

х2

b

х3

- 0,5

0,5

1

0,5 / 1Ü min

х1

0,5

0,5

3

0,5 / 3

f(x)

1,5

- 0,5

9

Ýmin 

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

б\с

x4

x3

b

x2

2

x1

2

f(x)

1

1

10

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

Ответ:  f *(x) =10; x1* = 0; x2*= 6

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

         f(Х) = х1 - 2х2 - 2x3 ® max

x1 + 4x2 + x3 = 5,

x1 - 2x2 - x3 = -1,          

xj ³ 0,

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

h(Х) = – ( t1+ t2) =  – 6 + 6 x2 + 2 x3 ® max

x1 + 4x2 + x3 + t1 = 5,

 x1 - 2x2 - x3 + t2 = -1, все  xj  ≥ 0, ti  ≥ 0.

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

Похожие материалы

Информация о работе

Предмет:
Математика
Тип:
Методические указания и пособия
Размер файла:
2 Mb
Скачали:
0