ВУЗ:
Составители:
Рубрика:
24
x
8
0
-1/2
0 0 0
-1/2
0 0 0 1
x
2
4 5 0 1 0 0 0 0 1 0
x
1
1 2 1 0 0 0 0 0 -1 1
x
5
0 11 0 0 0 0 1 0 -6 -2
x
3
0 2 0 0 1 0 0 0 6 1 Найдено
x
6
0 1 0 0 0 0 0 1 -2 0 целочисл.
x
4
0 1 0 0 0 1 0 0 0 -2 решение!
∆
j
0 0 0 0 0 0 3 1
На 3-й итерации симплекс- метода найдено нецелочисленное решение
)
2
25
,0,0,
6
35
,
3
5
(
1
=x . Выбираем , например,
3
5
1
1
=x - дробную базисную коорди -
нату и по соответствующей строке таблицы формируем новое ограничение:
}{}{}{
3
5
64
3
1
3
3
1
−=+− xxx . Или :
3
2
64
3
1
3
3
1
−
=
+
−
xxx . Добавляем это ограничение в
таблицу и осуществляем одну итерацию двойственного симплекс- метода. В ре-
зультате получаем точку
)0,
2
23
,0,1,
2
11
,2(
2
=x
. Выбираем дробную координату
2
11
2
2
=x и добавляем ограничение
2
1
76
2
1
−
=
+
−
xx и т . д .
На последней итерации получена точка )0,0,1,11,1,2,5,2(
4
=x , которая является
целочисленной. Останов.
Ответ : )5,2(
*
=x , .22)(
*
=xϕ
УПРАЖНЕНИЯ
1. Решить ЦЗЛП методом отсечений :
Ζ∈≥
≤+−
≤
≤−
→
+
2
1
2
1
21
1
21
21
,,0,
,0117
,112
,2/7
max43)
xxxx
xx
x
xx
xxa
Ζ∈≥
≤+
≤+−
≤+−
→
+
2
1
2
1
21
21
21
21
,,0,
,486
,405
,42
max2)
xxxx
xx
xx
xx
xxb
Ζ∈≥
≤−
≤+
≤+−
→
+
2121
21
2
1
21
21
21
,,0,
,102
,7
,102
max4)
xxxx
xx
xx
xx
xxc
Ответ:
max
x
=(5,3) Ответ:
max
x
=(6,9) Ответ:
max
x
=(2,5)
24
x8 0 -1/2 0 0 0 -1/2 0 0 0 1
x2 4 5 0 1 0 0 0 0 1 0
x1 1 2 1 0 0 0 0 0 -1 1
x5 0 11 0 0 0 0 1 0 -6 -2
x3 0 2 0 0 1 0 0 0 6 1 Найдено
x6 0 1 0 0 0 0 0 1 -2 0 целочисл.
x4 0 1 0 0 0 1 0 0 0 -2 решение!
∆j 0 0 0 0 0 0 3 1
На 3-й итерации симплекс-метода найдено нецелочисленное решение
5 35 25 5
x1 =( , ,0,0, ) . Выбираем, например, x11 = - дробную базисную коорди-
3 6 2 3
нату и по соответствующей строке таблицы формируем новое ограничение:
{13}x3 −{13}x4 +x6 =−{53} . Или: 13 x3 −13 x4 +x6 =−23 . Добавляем это ограничение в
таблицу и осуществляем одну итерацию двойственного симплекс-метода. В ре-
11 23
зультате получаем точку x 2 =( 2, ,1,0, ,0) . Выбираем дробную координату
2 2
11
x22 = и добавляем ограничение −12 x6 +x7 =−12 и т.д.
2
На последней итерации получена точка x 4 =(2, 5, 2,1,11,1,0, 0) , которая является
целочисленной. Останов.
Ответ: x* =( 2, 5) , ϕ ( x* ) =22.
УПРАЖНЕНИЯ
1. Решить ЦЗЛП методом отсечений:
a) 3x1 +4 x2 → max b) x1 +2 x2 → max c) x1 +4 x2 → max
x1 −x2 ≤7 / 2, −2 x1 +x2 ≤4, −x1 +2 x2 ≤10,
2 x1 ≤11, −x1 +5 x2 ≤40, x1 +x2 ≤7 12 ,
−7 x1 +11x2 ≤0, 6 x1 +x2 ≤48, 2 x1 −x2 ≤10,
x1 , x2 ≥0, x1 , x2 ∈Ζ x1 , x2 ≥0, x1 , x2 ∈Ζ x1 , x2 ≥0, x1 , x2 ∈Ζ
Ответ: x max =(5,3) Ответ: x max =(6,9) Ответ: x max =(2,5)
