Задачи ЛП и методы их решения
.pdf
|
|
|
|
|
239 |
|
Вариант 21 |
|
|
|
|
|
|
Cij |
j=2 |
j=3 |
j=4 |
j=5 |
j=6 |
j=7 |
|
|
|
|
|
|
|
i=1 |
41 |
78 |
114 |
150 |
193 |
230 |
i=2 |
– |
38 |
76 |
116 |
154 |
191 |
i=3 |
– |
– |
39 |
73 |
114 |
151 |
i=4 |
– |
– |
– |
38 |
76 |
113 |
i=5 |
– |
– |
– |
– |
39 |
77 |
i=6 |
– |
– |
– |
– |
– |
42 |
Вариант 22 |
|
|
|
|
|
|
Cij |
j=2 |
j=3 |
j=4 |
j=5 |
j=6 |
j=7 |
|
|
|
|
|
|
|
i=1 |
40 |
71 |
108 |
136 |
170 |
205 |
i=2 |
– |
33 |
66 |
99 |
132 |
164 |
i=3 |
– |
– |
32 |
64 |
98 |
133 |
i=4 |
– |
– |
– |
33 |
65 |
100 |
i=5 |
– |
– |
– |
– |
34 |
68 |
i=6 |
– |
– |
– |
– |
– |
37 |
Вариант 23 |
|
|
|
|
|
|
Cij |
j=2 |
j=3 |
j=4 |
j=5 |
j=6 |
j=7 |
|
|
|
|
|
|
|
i=1 |
27 |
50 |
72 |
94 |
123 |
143 |
i=2 |
– |
24 |
48 |
74 |
98 |
118 |
i=3 |
– |
– |
25 |
46 |
72 |
92 |
i=4 |
– |
– |
– |
24 |
48 |
68 |
i=5 |
– |
– |
– |
– |
25 |
46 |
i=6 |
– |
– |
– |
– |
– |
25 |
Вариант |
24 |
|
|
|
|
|
Cij |
j=2 |
j=3 |
j=4 |
j=5 |
j=6 |
j=7 |
|
|
|
|
|
|
|
i=1 |
38 |
68 |
102 |
131 |
164 |
198 |
i=2 |
– |
32 |
64 |
96 |
128 |
159 |
i=3 |
– |
– |
31 |
62 |
95 |
129 |
i=4 |
– |
– |
– |
32 |
63 |
97 |
i=5 |
– |
– |
– |
– |
33 |
66 |
i=6 |
– |
– |
– |
– |
– |
36 |
Вариант 25 |
|
|
|
|
|
|
Cij |
j=2 |
j=3 |
j=4 |
j=5 |
j=6 |
j=7 |
|
|
|
|
|
|
|
i=1 |
43 |
82 |
120 |
158 |
203 |
240 |
i=2 |
– |
40 |
80 |
122 |
162 |
199 |
i=3 |
– |
– |
41 |
78 |
120 |
157 |
i=4 |
– |
– |
– |
40 |
80 |
117 |
i=5 |
– |
– |
– |
– |
41 |
79 |
i=6 |
– |
– |
– |
– |
– |
41 |
|
|
|
|
|
240 |
|
Вариант 26 |
|
|
|
|
|
|
Cij |
j=2 |
j=3 |
j=4 |
j=5 |
j=6 |
j=7 |
|
|
|
|
|
|
|
i=1 |
30 |
54 |
77 |
100 |
130 |
155 |
i=2 |
– |
25 |
50 |
77 |
102 |
127 |
|
|
|
|
|
|
|
i=3 |
– |
– |
26 |
48 |
75 |
100 |
i=4 |
– |
– |
– |
25 |
50 |
75 |
i=5 |
– |
– |
– |
– |
26 |
52 |
i=6 |
– |
– |
– |
– |
– |
30 |
Вариант 27 |
|
|
|
|
|
|
Cij |
j=2 |
j=3 |
j=4 |
j=5 |
j=6 |
j=7 |
|
|
|
|
|
|
|
i=1 |
40 |
75 |
114 |
148 |
186 |
227 |
i=2 |
– |
37 |
74 |
111 |
148 |
186 |
i=3 |
– |
– |
36 |
72 |
110 |
151 |
i=4 |
– |
– |
– |
37 |
73 |
114 |
i=5 |
– |
– |
– |
– |
38 |
78 |
i=6 |
– |
– |
– |
– |
– |
42 |
Вариант 28 |
|
|
|
|
|
|
Cij |
j=2 |
j=3 |
j=4 |
j=5 |
j=6 |
j=7 |
|
|
|
|
|
|
|
i=1 |
49 |
98 |
144 |
196 |
243 |
295 |
i=2 |
– |
50 |
96 |
146 |
198 |
247 |
i=3 |
– |
– |
48 |
95 |
147 |
189 |
i=4 |
– |
– |
– |
49 |
98 |
148 |
i=5 |
– |
– |
– |
– |
51 |
101 |
i=6 |
– |
– |
– |
– |
– |
53 |
Вариант 29 |
|
|
|
|
|
|
Cij |
j=2 |
j=3 |
j=4 |
j=5 |
j=6 |
j=7 |
|
|
|
|
|
|
|
i=1 |
30 |
65 |
104 |
138 |
176 |
214 |
i=2 |
– |
33 |
62 |
101 |
138 |
173 |
i=3 |
– |
– |
30 |
66 |
104 |
141 |
i=4 |
– |
– |
– |
31 |
67 |
105 |
i=5 |
– |
– |
– |
– |
32 |
69 |
i=6 |
– |
– |
– |
– |
– |
34 |
Вариант 30
Cij |
j=2 |
j=3 |
j=4 |
j=5 |
j=6 |
j=7 |
|
|
|
|
|
|
|
i=1 |
49 |
99 |
147 |
199 |
248 |
298 |
i=2 |
– |
51 |
97 |
149 |
201 |
252 |
i=3 |
– |
– |
49 |
97 |
150 |
203 |
i=4 |
– |
– |
– |
50 |
100 |
151 |
i=5 |
– |
– |
– |
– |
52 |
103 |
i=6 |
– |
– |
– |
– |
– |
54 |
241
Задание 4. Сетевое планирование
Дан список предшествования работ некоторого проекта и проектное время Tпр . Требуется
1)построить сетевой график проекта.;
2)найти критический путь, критические работы, критическое время;
3)найти временные параметры событий и работ;
4)построить диаграмму Гантта по ранним срокам
|
Вариант 1 |
|
|
Вариант 2 |
|
|
|
|
|
|
|
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
та |
ие работы |
|
|
ие работы |
|
Р1 |
Р2 Р3 Р5 Р6 |
8 |
Р1 |
Р6 |
7 |
Р2 |
— |
10 |
Р2 |
— |
8 |
Р3 |
Р6 |
4 |
Р3 |
Р2 |
16 |
Р4 |
Р2 Р3 Р6 |
5 |
Р4 |
Р1 Р2 Р6 Р7 |
2 |
Р5 |
— |
8 |
Р5 |
Р2 |
2 |
Р6 |
— |
5 |
Р6 |
— |
16 |
Р7 |
Р3 Р6 |
3 |
Р7 |
Р2 Р5 Р6 |
8 |
|
|
|
|
|
|
|
Tпр= 20 |
|
|
Tпр= 32 |
|
|
|
|
|
|
|
|
Вариант 3 |
|
|
Вариант 4 |
|
|
|
|
|
|
|
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
та |
ие работы |
|
|
ие работы |
|
|
|
|
|
|
|
Р1 |
Р6 |
10 |
Р1 |
Р2 Р6 |
4 |
Р2 |
Р1 Р3 Р5 Р6 |
3 |
Р2 |
— |
13 |
Р3 |
Р6 |
12 |
Р3 |
Р1 Р4 Р6 |
2 |
Р4 |
— |
16 |
Р4 |
Р2 |
5 |
Р5 |
Р3 Р4 |
2 |
Р5 |
Р2 |
6 |
Р6 |
— |
1 |
Р6 |
— |
10 |
Р7 |
Р4 |
8 |
Р7 |
Р2 Р6 |
8 |
|
|
|
|
|
|
|
Tпр= 27 |
|
|
Tпр= 24 |
|
|
|
|
|
|
|
|
|
|
242 |
|
|
|
|
Вариант 5 |
|
|
|
Вариант 6 |
|
|
|
|
|
|
|
|
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
|
та |
ие работы |
|
|
|
ие работы |
|
Р1 |
Р3 |
12 |
|
Р1 |
— |
2 |
Р2 |
Р3 Р5 Р7 |
8 |
|
Р2 |
Р4 |
12 |
Р3 |
— |
7 |
|
Р3 |
Р1 Р4 Р6 |
8 |
Р4 |
Р7 |
10 |
|
Р4 |
— |
9 |
Р5 |
Р7 |
6 |
|
Р5 |
Р1 |
10 |
Р6 |
Р3 Р4 Р5 |
6 |
|
Р6 |
Р1 |
6 |
Р7 |
— |
2 |
|
Р7 |
Р4 Р5 Р6 |
6 |
|
Tпр= 22 |
|
|
|
Tпр= 23 |
|
|
|
|
|
|
|
|
|
Вариант 7 |
|
|
|
Вариант 8 |
|
|
|
|
|
|||
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
|
та |
ие работы |
|
|
|
ие работы |
|
Р1 |
Р3 |
6 |
|
Р1 |
Р3 Р4 Р5 Р6 |
7 |
Р2 |
Р1 Р6 Р7 |
6 |
|
Р2 |
Р3 |
3 |
Р3 |
— |
2 |
|
Р3 |
— |
10 |
Р4 |
Р6 |
13 |
|
Р4 |
— |
8 |
Р5 |
Р1 Р3 Р6 |
8 |
|
Р5 |
Р3 Р4 |
7 |
Р6 |
— |
8 |
|
Р6 |
— |
16 |
Р7 |
Р3 |
10 |
|
Р7 |
Р2 Р3 Р4 |
9 |
|
Tпр= 23 |
|
|
|
Tпр= 26 |
|
|
|
|
|
|
|
|
|
Вариант 9 |
|
|
|
Вариант 10 |
|
|
|
|
|
|||
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
|
та |
ие работы |
|
|
|
ие работы |
|
Р1 |
— |
5 |
|
Р1 |
Р3 Р7 |
8 |
Р2 |
Р1 Р5 |
3 |
|
Р2 |
Р3 Р7 |
4 |
Р3 |
Р1 Р2 Р5 Р6 |
8 |
|
Р3 |
— |
12 |
Р4 |
— |
10 |
|
Р4 |
Р2 Р5 Р7 |
2 |
Р5 |
Р1 |
4 |
|
Р5 |
Р3 |
5 |
Р6 |
Р1 Р4 |
5 |
|
Р6 |
Р3 |
6 |
Р7 |
— |
8 |
|
Р7 |
— |
10 |
|
Tпр= 25 |
|
|
|
Tпр= 23 |
|
|
|
|
|
|
|
|
|
|
|
243 |
|
|
|
|
Вариант 11 |
|
|
|
Вариант 12 |
|
|
|
|
|
|
|
|
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
|
та |
ие работы |
|
|
|
ие работы |
|
Р1 |
Р6 Р7 |
9 |
|
Р1 |
— |
4 |
Р2 |
Р5 |
3 |
|
Р2 |
Р1 Р3 Р4 Р5 |
13 |
Р3 |
Р2 Р4 Р5 Р7 |
7 |
|
Р3 |
Р1 Р6 |
2 |
Р4 |
— |
6 |
|
Р4 |
Р1 Р6 |
5 |
Р5 |
— |
2 |
|
Р5 |
Р1 |
6 |
Р6 |
Р2 Р4 Р5 |
4 |
|
Р6 |
— |
10 |
Р7 |
— |
12 |
|
Р7 |
Р1 Р3 Р5 Р6 |
8 |
|
Tпр= 23 |
|
|
|
Tпр= 31 |
|
|
|
|
|
|
|
|
|
Вариант 13 |
|
|
|
Вариант 14 |
|
|
|
|
|
|||
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
|
та |
ие работы |
|
|
|
ие работы |
|
Р1 |
— |
10 |
|
Р1 |
— |
7 |
Р2 |
Р4 Р5 Р6 |
3 |
|
Р2 |
— |
8 |
Р3 |
Р1 Р5 Р6 Р7 |
12 |
|
Р3 |
Р2 Р4 Р6 |
5 |
Р4 |
Р5 |
16 |
|
Р4 |
Р6 |
2 |
Р5 |
— |
2 |
|
Р5 |
Р2 Р4 Р6 |
3 |
Р6 |
— |
1 |
|
Р6 |
— |
3 |
Р7 |
Р5 Р6 |
8 |
|
Р7 |
Р1 Р2 Р4 Р6 |
10 |
|
Tпр= 29 |
|
|
|
Tпр= 20 |
|
|
|
|
|
|
|
|
|
Вариант 15 |
|
|
|
Вариант 16 |
|
|
|
|
|
|||
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
|
та |
ие работы |
|
|
|
ие работы |
|
Р1 |
Р3 Р4 Р5 |
9 |
|
Р1 |
— |
10 |
Р2 |
Р4 Р5 Р6 Р7 |
8 |
|
Р2 |
Р1 Р3 Р4 Р5 |
8 |
Р3 |
Р4 |
3 |
|
Р3 |
Р1 Р6 |
3 |
Р4 |
— |
10 |
|
Р4 |
Р1 Р6 |
3 |
Р5 |
— |
8 |
|
Р5 |
Р1 |
7 |
Р6 |
Р4 Р5 |
7 |
|
Р6 |
— |
9 |
Р7 |
— |
15 |
|
Р7 |
Р1 Р3 Р5 Р6 |
6 |
|
Tпр= 27 |
|
|
|
Tпр= 28 |
|
|
|
|
|
|
|
|
|
|
|
244 |
|
|
|
|
Вариант 17 |
|
|
|
Вариант 18 |
|
|
|
|
|
|
|
|
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
|
та |
ие работы |
|
|
|
ие работы |
|
Р1 |
Р2 Р3 Р4 Р7 |
8 |
|
Р1 |
Р4 |
8 |
Р2 |
Р5 Р7 |
3 |
|
Р2 |
— |
11 |
Р3 |
Р5 Р7 |
4 |
|
Р3 |
Р1 Р2 Р4 Р6 |
7 |
Р4 |
Р7 |
6 |
|
Р4 |
— |
10 |
Р5 |
— |
10 |
|
Р5 |
Р1 Р4 Р6 Р7 |
8 |
Р6 |
Р2 Р4 Р5 Р7 |
6 |
|
Р6 |
Р2 Р4 |
3 |
Р7 |
— |
10 |
|
Р7 |
Р2 Р4 |
4 |
|
Tпр= 27 |
|
|
|
Tпр= 28 |
|
|
|
|
|
|
|
|
|
Вариант 19 |
|
|
Вариант 20 |
|
|
|
|
|
|
|
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
та |
ие работы |
|
|
ие работы |
|
Р1 |
Р3 Р5 |
4 |
Р1 |
Р4 Р6 |
5 |
Р2 |
Р5 |
6 |
Р2 |
Р4 Р6 |
3 |
Р3 |
— |
11 |
Р3 |
Р6 |
6 |
Р4 |
Р2 Р3 Р5 Р7 |
6 |
Р4 |
— |
11 |
Р5 |
— |
10 |
Р5 |
Р1 Р3 Р4 Р6 |
6 |
Р6 |
Р1 Р2 Р5 Р7 |
8 |
Р6 |
— |
11 |
Р7 |
Р3 Р5 |
3 |
Р7 |
Р1 Р2 Р3 Р6 |
8 |
|
Tпр= 28 |
|
|
Tпр= 27 |
|
|
|
|
|
|
|
|
Вариант 21 |
|
|
Вариант 22 |
|
|
|
|
|
||
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
та |
ие работы |
|
|
ие работы |
|
Р1 |
Р2 |
3 |
Р1 |
Р2 Р4 Р5 Р6 |
6 |
Р2 |
— |
10 |
Р2 |
— |
10 |
Р3 |
— |
8 |
Р3 |
Р2 Р5 Р7 |
9 |
Р4 |
Р2 Р3 |
7 |
Р4 |
Р2 Р7 |
3 |
Р5 |
— |
15 |
Р5 |
Р2 Р7 |
4 |
Р6 |
Р1 Р2 Р3 |
9 |
Р6 |
Р2 |
7 |
Р7 |
Р2 Р3 Р4 Р5 |
7 |
Р7 |
— |
11 |
|
Tпр= 27 |
|
|
Tпр= 29 |
|
|
|
|
|
|
|
245
|
Вариант 23 |
|
|
Вариант 24 |
|
|
|
|
|
|
|
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
та |
ие работы |
|
|
ие работы |
|
Р1 |
Р4 |
6 |
Р1 |
— |
8 |
Р2 |
— |
11 |
Р2 |
Р1 Р7 |
8 |
Р3 |
Р1 Р2 Р4 Р6 |
6 |
Р3 |
— |
15 |
Р4 |
— |
10 |
Р4 |
Р1 Р6 Р7 |
9 |
Р5 |
Р1 Р4 Р7 |
10 |
Р5 |
Р1 Р2 Р3 Р7 |
6 |
Р6 |
Р2 Р4 |
5 |
Р6 |
Р7 |
3 |
Р7 |
Р2 Р4 |
4 |
Р7 |
— |
10 |
|
Tпр= 30 |
|
|
Tпр= 27 |
|
|
|
|
|
|
|
|
Вариант 25 |
|
|
Вариант 26 |
|
|
|
|
|
|
|
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
та |
ие работы |
|
|
ие работы |
|
Р1 |
— |
10 |
Р1 |
— |
11 |
Р2 |
— |
8 |
Р2 |
Р1 Р3 Р5 Р7 |
6 |
Р3 |
Р1 Р2 |
9 |
Р3 |
— |
10 |
Р4 |
— |
16 |
Р4 |
Р3 Р6 Р7 |
10 |
Р5 |
Р1 Р2 Р7 |
9 |
Р5 |
Р1 Р3 |
3 |
Р6 |
Р1 Р2 Р3 Р4 |
6 |
Р6 |
Р1 Р3 |
3 |
Р7 |
Р1 |
3 |
Р7 |
Р3 |
6 |
|
Tпр= 29 |
|
|
Tпр= 29 |
|
|
|
|
|
|
|
|
Вариант 27 |
|
|
Вариант 28 |
|
|
|
|
|
|
|
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
та |
ие работы |
|
|
ие работы |
|
Р1 |
Р4 Р7 |
3 |
Р1 |
— |
12 |
Р2 |
Р3 Р4 Р6 Р7 |
8 |
Р2 |
Р1 Р7 |
9 |
Р3 |
— |
10 |
Р3 |
Р6 |
3 |
Р4 |
Р7 |
4 |
Р4 |
Р1 Р3 Р5 Р6 |
7 |
Р5 |
Р3 Р4 Р7 |
5 |
Р5 |
— |
6 |
Р6 |
— |
8 |
Р6 |
— |
2 |
Р7 |
— |
5 |
Р7 |
Р3 Р5 Р6 |
4 |
|
Tпр= 21 |
|
|
Tпр= 24 |
|
|
|
|
|
|
|
|
|
|
246 |
|
|
|
|
Вариант 29 |
|
|
|
Вариант 30 |
|
|
|
|
|
|
|
|
Рабо |
Предшествующ |
Время |
Работа |
Предшествующ |
Время |
|
та |
ие работы |
|
|
|
ие работы |
|
Р1 |
Р2 Р3 Р5 Р7 |
11 |
|
Р1 |
— |
9 |
|
Р2 |
Р1 Р4 |
9 |
|||
Р2 |
— |
7 |
|
|||
|
Р3 |
Р1 Р6 |
3 |
|||
Р3 |
— |
8 |
|
|||
|
Р4 |
Р1 Р6 |
5 |
|||
Р4 |
Р3 Р5 Р6 |
5 |
|
|||
|
Р5 |
Р1 |
7 |
|||
Р5 |
Р7 |
2 |
|
|||
|
Р6 |
— |
10 |
|||
Р6 |
Р3 Р5 Р7 |
2 |
|
|||
|
Р7 |
Р3 Р4 Р5 Р6 |
6 |
|||
Р7 |
— |
3 |
|
|||
|
|
|
|
|||
|
Tпр= 21 |
|
|
|
Tпр= 29 |
|
|
|
|
|
|
|
|
247
2. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНЫХ ЗАДАНИЙ
Задача о выпуске продукции при ограниченных ресурсах.
Необходимый теоретический материал для выполнения есть в пособии В.Л.Никитенкова [1], а также в любой литературе по линейному программированию.
Объемы выпуска продукций могут быть произвольными, не обязательно целыми
неотрицательными числами, поэтому полученные оптимальные решения не следует округлять до целых чисел.
При постановке задачи линейного программирования (ЗЛП) обязательно указать смысл вводимых переменных (например, так: "Пусть x1 означает объем…").
Масштабы на осях при решении ЗЛП графическим методом должен быть одинаковыми.
Необходимо четко указать формальное решение рассматриваемой ЗЛП, например, так: "Ответ ЗЛП:
x |
max |
= |
K |
|
|
1 |
|
|
" |
x |
2max |
= |
K |
|
f |
max |
= |
K |
При экономической трактовке полученного решения необходимо указать в числах 1) объемы выпускаемой продукции, 2) прибыль, 3) остатки сырья всех трех типов.
Все численные расчеты при построении прямых и решении системы линейных уравнений можно опустить. Числа рекомендуется писать в виде дробей, не теряя точность, а округлять лишь в окончательном ответе.
Классическая транспортная задача.
Необходимый теоретический материал для решения транспортной задачи также есть в пособии В.Л.Никитенкова [1], смотри также [4].
Задачу нужно решить табличным методом потенциалов. Следует обратить внимание на то, что предлагаемые задачи являются, как правило, открытыми транспортными задачами, поэтому их предварительно требуется закрыть, добавив по необходимости фиктивного поставщика или фиктивного потребителя.
В качестве начального плана перевозок можно взять план, полученный методом северозападного угла или методом минимальной стоимости. Не следует думать, что последний метод приведет к меньшему числу таблиц при решении.
При оформлении решения необходимо выписать только последовательность таблиц с необходимыми элементами: потенциалами, значками '+' '-', значения стоимостей очередных планов перевозок. Все остальные выкладки (расчеты потенциалов и др.) необязательны.
Ответ состоит из последней таблицы (с потенциалами и ценами !!), числа Сmin– стоимости оптимального плана и графа оптимального плана
со значениями перевозок на дугах.
Задача об аренде оборудования.
О задачах об аренде оборудования можно прочитать в [3], также в учебниках по исследованию операций. К сожалению, эта литература стала труднодоступной, поэтому постановка задачи и два метода ее решения приводятся в разделе 3.
248
Задачу достаточно решить одним из предложенных способов (при этом студентам-заочникам следует знать оба метода).
Рекомендуется табличный метод как более простой. Решение при этом собственно будет состоять из таблицы исходных стоимостей, дополненной столбцом потенциалов YI , набора выделенных клеток (в каждой строке таблицы должна быть хотя одна выделенная клетка!) и выписанных из таблицы по выделенным клеткам ответов задачи – оптимальных планов аренды. Планы следует писать как в виде путей, то есть возрастающей последовательности номеров, так и в виде набора сроков очередной аренды. Искать планы аренды методом перебора не разрешается!