Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
«Омский государственный технический университет»
Исследование операций
Методические указания по выполнению типового расчета
Омск - 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 + x5 ® min |
3. f(x) = 2x1 + x2 + x3 - x4 - 2x5 + 12 ® min |
4. f(x) =2 x1 + 2x2 + 3x3 + x5 ® min |
5. f(x) = 2x1 + 4x2 + x3 - x4 - 5x5 + 15® min |
6. f(x) = x1 + 2x2 + 2x3 + x5 ® min |
7. f(x) = x1 + 4x2 + 2x3 + 4x4 - 5x5 ® min |
8. f(x) = 5x1 + 2x2 + 5x3 + x5 ® min |
9. f(x) = 10x1 + 4x2 + 2x3 + 4x4 - 5x5 ® min |
10. f(x) = 4x1 + 2x2 + 3x3 + 2x5 ® min |
11. f(x) = x1 + 4x2 + 2x3 - 2x4 - x5 - 10 ® min |
12. f(x) = 3x1 + 2x2 + 8x3 + x5 ® min |
13. f(x) = x1 + 4x2 + 2x3 + 2x4 + x5 + 2 ® min |
14. f(x) = 4x1 + 2x2 + 3x3 + 5x5 ® min |
15. f(x) = x1 + 7x2 + 2x3 + x4 + 4x5 - 5 ® min |
16. f(x) = 7x1 + 2x2 - 3x3 + 5x5 ® min |
17. f(x) = x1 + 2x2 + 2x3 + 9x4 + 4x5 ® min |
18. f(x) = x1 + 2x2 - 3x3 + x5 ® min |
19. f(x) = 5x1 + 7x2 + 9x3 + x4 + x5 + 1 ® min |
20. f(x) = 2x1 + 2x2 - 2x3 + x5 ® min |
21. f(x) = 3x1 + 2x2 + x3 + x4 + x5 + 4 ® min |
22. f(x) = 8x1 + 2x2 - 2x3 + 5x5 ® min |
23. f(x) = 4x1 + 2x2 + 3x3 + x4 + x5 + 1 ® min |
24. f(x) = 4x1 + 2x2 - 2x3 + 3x5 ® min |
25. f(x) = 9x1 + 2x2 + 3x3 + 2x4 + x5 ® min |
26. f(x) = - x1 + 2x2 - 2x3 + 3x5 ® min |
27. f(x) = 2x1 + 2x2 + 3x3 + 5x4 + x5 ® min |
28. f(x) = - 4x1 + 2x2 - 2x3 + 7x5 ® min |
29. f(x) = 21x1 + 2x2 + 30x3 + 5x4 + x5 ® min |
30. f(x) = - 5x1 + 7x2 - 5x3 + 8x5 ® 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 + 2x2 = const – линия уровня функции f(x), перпендикулярная вектору градиента . Шаг 4. Линия уровня 3x1 + 2x2 = 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.
Решаем специальную задачу линейного программирования симплекс
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.