ВУЗ:
Составители:
Рубрика:
23
решение оптимально ). Для ввода в базис выбирается та из небазисных пере-
менных
k
x , для которой 0
<
lk
a и отношение
||
lk
k
a
∆
минимально .
Пример. Решить задачу целочисленного линейного программирования.
max4)(
21
→
+
=
xxx
ϕ
2/15
102
21
21
≤+
≤
+
−
xx
xx
Ζ∈≥
≤
−
2121
21
,,0,
102
xxxx
xx
Решение. Приведем задачу к каноническому виду (предварительно умножив
второе ограничение на 2).
max4
21
→
+
xx
1522
102
421
321
=++
=
+
+
−
xxx
xxx
5,1,,0
102
521
=Ζ∈≥
=
+
−
jxx
xxx
jj
Оформим решение в виде симплекс- таблицы
1 4 0 0 0 0 0 0 B C
B
b
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
Θ
Коммен -
тарий
x
3
0 10 -1 2 1 0 0
10/2
x
4
0 15 2 2 0 1 0 15/2
x
5
0 10 -1 -1 0 0 1 -
∆
j
-1
-4
0 0 0
x
2
4 5 -1/2 1 1/2 0 0 -
x
4
0 5 3 0 -1 1 0
5/3
x
5
0 15 3/2 0 1/2 0 1 10
∆
j
-3
0 2 0 0
x
2
4 35/6 0 1 1/3 1/6 0 0
x
1
1 5/3 1 0 -1/3 1/3 0 0 Найдена
x
5
0 25/2 0 0 1 -1/2 1 0 точка
∆
j
0 0 1 1 0
x
1
!
x
6
0
-2/3
0 0
-2/3
-1/3 0 1
x
2
4 11/2 0 1 0 0 0 1/2 0
x
1
1 2 1 0 0 1/2 0 -1/2 0
x
5
0 23/2 0 0 0 -1 1 3/2 0 Найдена
x
3
0 1 0 0 1 1/2 0 -3/2 0 точка
∆
j
0 0 0 1/2 0 3/2
x
2
!
x
7
0
-1/2
0 0 0 0 0
-1/2
1
x
2
4 5 0 1 0 0 0 0 1 0
x
1
1 5/2 1 0 0 1/2 0 0 -1 0
x
5
0 10 0 0 0 -1 1 0 -6 0
x
3
0 5/2 0 0 1 1/2 0 0 6 0 Найдена
x
6
0 1 0 0 0 0 0 1 -2 0 точка
∆
j
0 0 0 1/2 0 0 3
x
3
!
23
решение оптимально). Для ввода в базис выбирается та из небазисных пере-
∆
менных xk , для которой alk <0 и отношение k минимально.
| alk |
Пример. Решить задачу целочисленного линейного программирования.
ϕ ( x) =x1 +4 x2 → max
−x1 +2 x2 ≤10
x1 +x2 ≤15 / 2
2 x1 −x2 ≤10
x1 , x2 ≥0, x1 , x2 ∈Ζ
Решение. Приведем задачу к каноническому виду (предварительно умножив
второе ограничение на 2).
x1 +4 x2 → max
−x1 +2 x2 +x3 =10
2 x1 +2 x2 +x4 =15
2 x1 −x2 +x5 =10
x j ≥0, x j ∈Ζ, j =1,5
Оформим решение в виде симплекс-таблицы
B CB b 1 4 0 0 0 0 0 0 Θ Коммен-
x1 x2 x3 x4 x5 x6 x7 x8 тарий
x3 0 10 -1 2 1 0 0 10/2
x4 0 15 2 2 0 1 0 15/2
x5 0 10 -1 -1 0 0 1 -
∆j -1 -4 0 0 0
x2 4 5 -1/2 1 1/2 0 0 -
x4 0 5 3 0 -1 1 0 5/3
x5 0 15 3/2 0 1/2 0 1 10
∆j -3 0 2 0 0
x2 4 35/6 0 1 1/3 1/6 0 0
x1 1 5/3 1 0 -1/3 1/3 0 0 Найдена
x5 0 25/2 0 0 1 -1/2 1 0 точка
∆j 0 0 1 1 0 x1 !
x6 0 -2/3 0 0 -2/3 -1/3 0 1
x2 4 11/2 0 1 0 0 0 1/2 0
x1 1 2 1 0 0 1/2 0 -1/2 0
x5 0 23/2 0 0 0 -1 1 3/2 0 Найдена
x3 0 1 0 0 1 1/2 0 -3/2 0 точка
∆j 0 0 0 1/2 0 3/2 x2 !
x7 0 -1/2 0 0 0 0 0 -1/2 1
x2 4 5 0 1 0 0 0 0 1 0
x1 1 5/2 1 0 0 1/2 0 0 -1 0
x5 0 10 0 0 0 -1 1 0 -6 0
x3 0 5/2 0 0 1 1/2 0 0 6 0 Найдена
x6 0 1 0 0 0 0 0 1 -2 0 точка
∆j 0 0 0 1/2 0 0 3 x3 !
