--PAGE_BREAK--↑
b
ξ1
x2
ξ4
x4
x5
x6
F
3
0
3
1
0
0
1
-3
0
-3/5
9/5
0
-3/5
9/5
x1
3
0
-1
1
0
0
1
1
0
1/5
-3/5
0
1/5
-3/5
ξ2
5
0
0
1
1
0
1
0
0
0
0
0
0
0
←
ξ3
5
0
5
-3
0
1
-3
1
1
0
1/5
-3/5
0
1/5
-3/5
x3
5
-1
-3
2
0
0
2
3
0
3/5
-9/5
0
3/5
-9/5
f
10
-1
5
-3
1
1
-2
-5
0
-1
3
0
-1
3
↑
b
ξ1
ξ3
ξ4
x4
x5
x6
F
0
0
-3/5
14/5
0
-3/5
14/5
-14
0
0
-14/5
-14/5
0
-14/5
x1
4
0
1/2
2/5
0
1/5
2/5
10
-2
0
0
-2/5
-2/5
0
-2/5
←
ξ2
5
0
0
1
1
0
1
5
5
0
0
1
1
0
1
x2
1
0
1/5
-3/5
0
1/5
-3/5
3
0
0
3/5
3/5
0
3/5
x3
8
-1
3/5
1/5
0
3/5
1/5
40
-1
0
0
-1/5
-1/5
0
-1/5
f
5
-1
-1
0
1
0
1
-5
0
0
-1
-1
0
-1
b
ξ1
ξ3
ξ4
x4
x5
ξ2
F
-14
0
-3/5
0
-14/5
-3/5
-14/5
x1
2
0
1/5
0
-2/5
1/5
-2/5
x6
5
0
0
1
1
0
1
x2
4
0
1/5
0
3/5
1/5
-3/5
x3
7
-1
3/5
0
-1/5
3/5
-1/5
f
0
-1
-1
-1
0
0
-1
b
x4
x5
F
-14
-14/5
-3/5
x6
5
1
0
x2
4
3/5
1/5
x3
7
-1/5
3/5
x1
2
-2/5
1/5
Допустимое базисное оптимальное решение:
X = (2, 4, 7, 0, 0, 5)
F = -14
2.1.7 Решение двойственной задачи
Прямая задача:
Двойственная задача:
Приводим к каноническому виду:
y1, y3 – базисные переменные, y2, y4, y5, y6 – свободные переменные
↑
b
y2
y4
y5
y6
←
y1
14
5
-5
2
-3
14/5
14/5
1/5
-1
2/5
-3/5
y3
9
3
-3
1
-2
3
-42/5
-3/5
3
-6/5
9/5
Ф’
112
35
-40
12
-25
-98
-7
35
-14
21
b
y2
y4
y5
y6
y1
14/5
1/5
-1
2/5
-3/5
y3
3/5
-3/5
0
-1/5
-1/5
Ф’
14
-7
-5
-2
-4
x1
x2
x3
x4
x5
x6
↕
↕
↕
↕
↕
↕
y5
y6
y1
y2
y3
y4
2
4
7
0
0
5
F’ = Ф’ = 14
X = (2,4,7,0,0,5)
F= -F’ = -14
2.2 Задача целочисленного линейного программирования
2.2.1 Постановка задачи целочисленного линейного программирования
Решить ЗЦЛП, при условии целочисленности всех переменных, входящих в задачу, методом ветвей и границ и методом отсекающих плоскостей (методом Гомори).
2.2.2 Метод Гомори
x3, x4 – базисные переменные, x1, x2 – свободные переменные
↑
b
x1
x2
x3
11
2
3
11/2
-5
-1/2
-1/2
←
x4
10
4
1
10/4
5/2
1/4
1/4
F’
0
2
1
-5
-1/2
-1/2
↑
b
x4
x2
←
x3
6
-1/2
5/2
12/5
12/5
-1/5
2/5
x1
5/2
1/4
1/4
10
-3/5
1/20
-1/10
F’
-5
-1/2
1/2
-6/5
1/10
-1/5
b
x1
x2
x3
12/5
-1/5
2/5
x4
19/10
3/10
-1/10
F’
-31/5
-2/5
-1/5
X = (19/10, 12/5, 0, 0)
F = -F’ = 31/5
Составляем неравенство Гомори:
↑
b
x4
x3
F’
-31/5
-2/5
-1/5
1/5
1/10
-1/2
x2
12/5
-1/5
2/5
-2/5
-1/5
1
x1
19/10
3/10
-1/10
1/10
-1/4
←
u2
-2/5
-1/5
-2/5
1
1/2
-5/2
b
x4
u2
F’
-6
-3/10
-1/2
x2
2
-2/5
1
x1
2
7/20
-1/4
x3
1
1/2
-5/2
X = (2, 2, 1, 0)
F = -F’ = 6
2.2.3 Метод ветвей и границ
b
x1
x2
x3
12/5
-1/5
2/5
x4
19/10
3/10
-1/10
F’
-31/5
-2/5
-1/5
Задача № 1
Приводим к каноническому виду:
x3, x4, x5 – базисные переменные, x1, x2 – свободные переменные
↑
b
x1
x2
x3
11
2
3
11/2
-5
-1/2
-1/2
←
x4
10
4
1
5/2
5/2
1/4
1/4
x5
2
0
1
0
0
0
F’
0
2
1
-5
-1/2
-1/2
↑
b
x4
x2
x3
6
-1/2
5/2
12/5
-5
0
-5/2
x1
5/2
1/4
1/4
10
-1/2
0
-1/4
←
x5
2
0
1
2
2
0
1
F’
-5
-1/2
1/2
-1
0
-1/2
b
x4
x5
x3
1
-1/2
-5/2
x1
2
1/4
-1/4
x2
2
0
1
F’
-6
-1/2
-1/2
продолжение
--PAGE_BREAK--