7.5 Задания для самостоятельной работы
Решить ЗЦЛП методом ветвей и границ. Построить дерево подмножеств решений задачи. Для каждой задачи дана оптимальная симплекс-таблица соответствующей ослабленной задачи. Каждую из сформированных подзадач решить при помощи двойственного симплекс-метода (привести все симплекс-таблицы получаемые в процессе решения).
|
Б/П |
x1 |
x2 |
x3 |
x4 |
Решение |
|
Б/П |
x1 |
x2 |
x3 |
x4 |
Решение | ||
|
z |
0 |
0 |
-1/4 |
-5/6 |
21/2 |
|
z |
0 |
0 |
-1/3 |
-1/3 |
31/3 | ||
|
x1 |
1 |
0 |
-1/4 |
1/6 |
3/2 |
|
x1 |
1 |
0 |
-4/3 |
1/6 |
16/3 | ||
|
x2 |
0 |
1 |
1/4 |
-1/2 |
3/2 |
x2 |
0 |
1 |
1/3 |
-1/6 |
5/3 | |||
|
Б/П |
x1 |
x2 |
x3 |
x4 |
Решение |
|
Б/П |
x1 |
x2 |
x3 |
x4 |
Решение |
|
z |
0 |
0 |
-6/5 |
-2/5 |
48/5 |
|
z |
0 |
0 |
-4/9 |
-7/9 |
56/9 |
|
x1 |
1 |
0 |
-2/5 |
1/5 |
6/5 |
|
x1 |
1 |
0 |
-2/9 |
1/9 |
10/9 |
|
x2 |
0 |
1 |
1/5 |
-3/5 |
12/5 |
x2 |
0 |
1 |
1/9 |
-5/9 |
13/9 |
-
Б/П
x1
x2
x3
x4
Решение
Б/П
x1
x2
x3
x4
Решение
z
0
0
-2/5
-3/20
48/5
z
0
0
-13/45
-1/18
140/9
x1
1
0
-1/5
1/20
4/5
x2
0
1
-1/9
1/18
40/9
x2
0
1
1/10
-3/20
18/5
x1
1
0
1/45
-1/9
10/9
-
Б/П
x1
x2
x3
x4
Решение
Б/П
x1
x2
x3
x4
Решение
z
0
0
-1/4
-3/8
11
z
13/4
0
0
3/4
69/4
x1
1
0
-1/8
1/16
3/2
x2
7/4
1
0
1/4
23/4
x2
0
1
1/8
-5/16
5/2
x3
-11/4
0
1
-5/4
5/4
-
Б/П
x1
x2
x3
x4
Решение
Б/П
x1
x2
x3
x4
Решение
z
5/3
0
2/3
0
38/3
z
0
1/2
3/4
0
45/4
x2
4/3
1
1/3
0
19/3
x1
1
1/2
1/4
0
15/4
x4
7/3
0
1/3
1
25/3
x4
0
1/2
-1/4
1
17/4
-
Б/П
x1
x2
x3
x4
Решение
Б/П
x1
x2
x3
x4
Решение
z
0
1/3
2/3
0
28/3
z
5/3
0
4/3
0
68/3
x1
1
2/3
1/3
0
14/3
x2
2/3
1
1/3
0
17/3
x4
0
5/3
1/3
1
20/3
x4
2/3
0
-5/3
1
35/3
-
Б/П
x1
x2
x3
x4
Решение
Б/П
x1
x2
x3
x4
Решение
z
1/5
0
2/5
0
36/5
z
0
3/5
2/5
0
48/5
x2
3/5
1
1/5
0
18/5
x1
1
4/5
1/5
0
24/5
x4
2/5
0
-1/5
1
22/5
x4
0
1/5
-1/5
1
11/5
-
Б/П
x1
x2
x3
x4
Решение
Б/П
x1
x2
x3
x4
Решение
z
0
0
-5/2
-3
38
z
0
0
-7/5
-4/5
156/5
x2
0
1
-3/8
-1/4
9/2
x2
0
1
-1/5
-1/15
18/5
x1
1
0
-1/4
-1/2
5
x1
1
0
-1/10
-1/5
24/5
-
Б/П
x1
x2
x3
x4
Решение
Б/П
x1
x2
x3
x4
Решение
z
0
0
-81/10
-11/10
182/5
z
0
0
8/19
6/19
216/19
x2
0
1
-11/10
-1/10
22/5
x2
0
1
5/38
-1/38
20/19
x1
1
0
-1/10
-1/10
7/5
x1
1
0
-1/19
4/19
68/19
-
Б/П
x1
x2
x3
x4
Решение
Б/П
x1
x2
x3
x4
Решение
z
0
0
-5/2
-3
38
z
0
0
-7/5
-4/5
156/5
x2
0
1
-3/8
-1/4
9/2
x2
0
1
-1/5
-1/15
18/5
x1
1
0
-1/4
-1/2
5
x1
1
0
-1/10
-1/5
24/5
-
Б/П
x1
x2
x3
x4
Решение
Б/П
x1
x2
x3
x4
Решение
z
0
0
-81/10
-11/10
182/5
z
0
0
8/19
6/19
216/19
x2
0
1
-11/10
-1/10
22/5
x2
0
1
5/38
-1/38
20/19
x1
1
0
-1/10
-1/10
7/5
x1
1
0
-1/19
4/19
68/19
-
Б/П
x1
x2
x3
x4
Решение
Б/П
x1
x2
x3
x4
Решение
z
0
0
-1/4
-5/6
21/2
z
0
0
-1/3
-1/3
31/3
x1
1
0
-1/4
1/6
3/2
x1
1
0
-4/3
1/6
16/3
x2
0
1
1/4
-1/2
3/2
x2
0
1
1/3
-1/6
5/3
-
Б/П
x1
x2
x3
x4
Решение
Б/П
x1
x2
x3
x4
Решение
z
0
0
-6/5
-2/5
48/5
z
0
0
-4/9
-7/9
56/9
x1
1
0
-2/5
1/5
6/5
x1
1
0
-2/9
1/9
10/9
x2
0
1
1/5
-3/5
12/5
x2
0
1
1/9
-5/9
13/9
-
Б/П
x1
x2
x3
x4
Решение
Б/П
x1
x2
x3
x4
Решение
z
0
0
-2/5
-3/20
48/5
z
0
0
-13/45
-1/18
140/9
x1
1
0
-1/5
1/20
4/5
x2
0
1
-1/9
1/18
40/9
x2
0
1
1/10
-3/20
18/5
x1
1
0
1/45
-1/9
10/9
-
Б/П
x1
x2
x3
x4
Решение
Б/П
x1
x2
x3
x4
Решение
z
0
0
-1/4
-3/8
11
z
0
0
15/22
10/11
130/11
x1
1
0
-1/8
1/16
3/2
x1
1
0
2/11
-1/11
20/11
x2
0
1
1/8
-5/16
5/2
x2
0
1
-1/22
3/11
6/11