ВУЗ:
Составители:
Рубрика:
15
Решение задачи проводится в последовательности таблиц. Таблица 0.
b
0
c
0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
6
00 0−21 1−11000
x
7
002
∗
0 −21−10100
x
8
00−12 0 1−10010
x
9
1 ω 1 1 1 0 0 0001
00 0 0−11 0000
11
∗
1 1 0 0 0000
Коэффициент ω — отрицательная, достаточно большая по абсолютной величине величина. Как
видно из m +2 строки, на ввод в базис претендуют вектора A
1
,A
2
,A
3
, мы выберем A
1
. Вектор,
исключаемый из базиса, определяется min
x
7
x
71
,
x
8
x
81
= {0, 1} =
x
7
x
71
=0. Таблица 1.
b
0
c
0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
6
000−21
∗
1 −11000
x
1
000 0−11/2 −1/20 1/200
x
8
000 2−13/23/201/210
x
9
1 ω 01 2−1/21/20−1/20 1
00 0 0 −1 10000
00 1 2−1/21/201/200
Отметим, что дополнительные переменные в случае их исключения из опорного плана остаются в
таблице. Таблица 2.
b
0
c
0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
3
000−21 1 −11000
x
1
001−20 3/2 −3/51 1/200
x
8
000005/2 −5/21 1/210
x
9
1 ω 05
∗
0 −5/25/22−1/20 1
В базис вводим A
2
вместо A
9
. Таблица по-прежнему содержит искусственный вектор (переменную).
На очередной итерации он исключается. Таблица 3.
b
0
c
0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
3
2/50001 0 01/51/50
x
1
2/501001/2
∗
1/21/58/10 0
x
8
0 0000 5/25/21 1/21
x
2
1/50010−1/21/22/51/10 0
0000−1
∗
10 00
В базис вводится вектор A
4
вместо вектора A
1
. Таблица 4.
b
0
c
0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
3
2/50 0 010 0 1/51/50
x
4
2/51 2 001−12/53/50
x
8
2/50−1000 0−4/5 −9/51
x
2
3/50 1 100 0 0 2/10 0
2/52 000 0 2/53/50
Элементы последней строки свидетельствую об оптимальности опорного плана. Выпишем его x
опт
=
(0, 3/5, 2/5, 2/5, 0), (c, x
опт
)=2/5.
В качестве упражнений предлагаем решить следующие задачи:
−3x
1
+ x
2
+3x
3
+ x
4
− min
x
1
+2x
2
− x
3
+ x
4
=0
2x
1
− 2x
2
+3x
3
+3x
4
=9
x
1
− x
2
+2x
3
− x
4
=6
x
j
≥ 0,j=1, 2, 3, 4
−2x
1
+ x
2
− x
3
− x
4
− min
x
1
− x
2
+2x
3
− x
4
=2
2x
1
+ x
2
− 3x
3
+3x
4
=6
x
1
+ x
2
+ x
3
+ x
4
=7
x
j
≥ 0,j=1, 2, 3, 4
Ответ x =(1, 1, 3, 0) Ответ x =(3, 0, 1, 3)
15
Решение задачи проводится в последовательности таблиц. Таблица 0.
b0 c0 x1 x2 x3 x4 x5 x6 x7 x8 x9
x6 0 0 0 −2 1 1 −1 1 0 0 0
x7 0 0 2∗ 0 −2 1 −1 0 1 0 0
x8 0 0 −1 2 0 1 −1 0 0 1 0
x9 1 ω 1 1 1 0 0 0 0 0 1
0 0 0 0 −1 1 0 0 0 0
1 1∗ 1 1 0 0 0 0 0 0
Коэффициент ω — отрицательная, достаточно большая по абсолютной величине величина. Как
видно из m + 2 строки, на ввод в базис претендуют
вектора A1 , A2 , A3 , мы выберем A1 . Вектор,
x7 x8 x7
исключаемый из базиса, определяется min , = {0, 1} = = 0. Таблица 1.
x71 x81 x71
b0 c0 x1 x2 x3 x4 x5 x6 x7 x8 x9
x6 0 0 0 −2 1∗ 1 −1 1 0 0 0
x1 0 0 0 0 −1 1/2 −1/2 0 1/2 0 0
x8 0 0 0 2 −1 3/2 3/2 0 1/2 1 0
x9 1 ω 0 1 2 −1/2 1/2 0 −1/2 0 1
0 0 0 0 −1 1 0 0 0 0
0 0 1 2 −1/2 1/2 0 1/2 0 0
Отметим, что дополнительные переменные в случае их исключения из опорного плана остаются в
таблице. Таблица 2.
b0 c0 x1 x2 x3 x4 x5 x6 x7 x8 x9
x3 0 0 0 −2 1 1 −1 1 0 0 0
x1 0 0 1 −2 0 3/2 −3/5 1 1/2 0 0
x8 0 0 0 0 0 5/2 −5/2 1 1/2 1 0
x9 1 ω 0 5∗ 0 −5/2 5/2 2 −1/2 0 1
В базис вводим A2 вместо A9 . Таблица по-прежнему содержит искусственный вектор (переменную).
На очередной итерации он исключается. Таблица 3.
b0 c0 x1 x2 x3 x4 x5 x6 x7 x8
x3 2/5 0 0 0 1 0 0 1/5 1/5 0
∗
x1 2/5 0 1 0 0 1/2 1/2 1/5 8/10 0
x8 0 0 0 0 0 5/2 5/2 1 1/2 1
x2 1/5 0 0 1 0 −1/2 1/2 2/5 1/10 0
0 0 0 0 −1∗ 1 0 0 0
В базис вводится вектор A4 вместо вектора A1 . Таблица 4.
b0 c0 x1 x2 x3 x4 x5 x6 x7 x8
x3 2/5 0 0 0 1 0 0 1/5 1/5 0
x4 2/5 1 2 0 0 1 −1 2/5 3/5 0
x8 2/5 0 −1 0 0 0 0 −4/5 −9/5 1
x2 3/5 0 1 1 0 0 0 0 2/10 0
2/5 2 0 0 0 0 2/5 3/5 0
Элементы последней строки свидетельствую об оптимальности опорного плана. Выпишем его xопт =
(0, 3/5, 2/5, 2/5, 0), (c, xопт ) = 2/5.
В качестве упражнений предлагаем решить следующие задачи:
−3x1 + x2 + 3x3 + x4 − min −2x1 + x2 − x3 − x4 − min
x1 + 2x2 − x3 + x4 = 0 x1 − x2 + 2x3 − x4 = 2
2x1 − 2x2 + 3x3 + 3x4 = 9 2x1 + x2 − 3x3 + 3x4 = 6
x1 − x2 + 2x3 − x4 = 6 x1 + x2 + x3 + x4 = 7
xj ≥ 0, j = 1, 2, 3, 4 xj ≥ 0, j = 1, 2, 3, 4
Ответ x = (1, 1, 3, 0) Ответ x = (3, 0, 1, 3)
