ВУЗ:
Составители:
Рубрика:
14
Для выбора вектора, вводимого в базис, сравниваем положительные элементы (m +2)строки (ко-
эффициенты при ω в z
j
− c
j
, ω>0). Максимальный элемент отмечен ”∗”, следовательно, в ба-
зис вводится вектор A
1
. Для выбора вектора, выводимого из базиса, находим min
x
6
x
61
,
x
7
x
71
=
4
2
,
6
1
=
x
6
x
61
=2. Таким образом, искусственный вектор A
6
заменяется на вектор A
1
, искусствен-
ная переменная x
6
заменяется в опорном плане на x
1
. Проводится пересчет таблицы по правилу
исключения x
1
из первого и третьего уравнений. Таблица 1.
b
0
c
0
x
1
x
2
x
3
x
4
x
5
x
7
x
1
211−1/20−1 −10
x
3
10 −20 3/210−10
x
7
4 ω 0 −3/20 3 4
∗
0
−18 0 −1/20−20 0
−40−3/20 3 4
∗
0
В последней строке выбираем максимальную величину среди положительных. Она соответствует
столбцу A
5
, следовательно, вектор A
5
включается в базис вместо A
7
(в столбце x
5
единственный
положительный элемент). Вообще говоря, в базис можно было ввести и A
4
. Таблица 2.
b
0
c
0
x
1
x
2
x
3
x
4
x
5
x
1
311−7/80−1/40
x
3
11 −20 9/813/40
x
5
110−3/80 3/40
−18 0 −1/20 −20
Все искусственные векторы (переменные) исключены, получен исходный опорный план x
0
=
(3, 0, 11, 0, 5), при этом все величины z
j
− c
j
≤ 0, значит, полученный опорный план будет опти-
мальным. Значение формы равно −18. Задача решена.
Рассмотрим еще один пример:
x
4
+x
5
−max
2x
2
−x
3
−x
4
+x
5
≥0
−2x
1
+2x
3
−x
4
+x
5
≥0
x
1
−2x
2
−x
4
+x
5
≥0
x
1
+x
2
+x
3
=1
x
j
≥ 0,j= 1, 5
Приведем задачу к каноническому виду, для этого от левых частей первых трех неравенств отнимем
дополнительные переменные x
6
,x
7
,x
8
соответственно. Задача примет вид
x
4
+x
5
−max
2x
2
−x
3
−x
4
+x
5
−x
6
≥ 0
−2x
1
+2x
3
−x
4
+x
5
−x
7
≥ 0
x
1
−2x
2
−x
4
+x
5
−x
8
≥ 0
x
1
+x
2
+x
3
=1
x
j
≥ 0,j= 1, 8
Уже видно из условий задачи, единичные вектора-столбцы отсутствуют. Однако единичный ба-
зис можно получить, умножив первые три уравнения на −1, а в последнее ввести искусственную
переменную x
9
. После этих простейших преобразований имеем расширенную задачу
x
4
+x
5
+10x
9
−max
−2x
2
+x
3
+x
4
−x
5
+x
6
=0
2x
1
−2x
3
+x
4
−x
5
+x
7
=0
−x
1
+2x
2
+x
4
−x
5
+x
8
=0
x
1
+x
2
+x
3
=1
x
j
≥ 0,j= 1, 9
14
Для выбора вектора, вводимого в базис, сравниваем положительные элементы (m + 2) строки (ко-
эффициенты при ω в zj − cj , ω > 0). Максимальный элемент отмечен ”∗”, следовательно,
вба-
x6 x7
зис вводится вектор A1 . Для выбора вектора, выводимого из базиса, находим min , =
x61 x71
4 6 x6
, = = 2. Таким образом, искусственный вектор A6 заменяется на вектор A1 , искусствен-
2 1 x61
ная переменная x6 заменяется в опорном плане на x1 . Проводится пересчет таблицы по правилу
исключения x1 из первого и третьего уравнений. Таблица 1.
b0 c0 x1 x2 x3 x4 x5 x7
x1 2 1 1 −1/2 0 −1 −1 0
x3 10 −2 0 3/2 1 0 −1 0
x7 4 ω 0 −3/2 0 3 4∗ 0
−18 0 −1/2 0 −2 0 0
−4 0 −3/2 0 3 4∗ 0
В последней строке выбираем максимальную величину среди положительных. Она соответствует
столбцу A5 , следовательно, вектор A5 включается в базис вместо A7 (в столбце x5 единственный
положительный элемент). Вообще говоря, в базис можно было ввести и A4 . Таблица 2.
b0 c0 x1 x2 x3 x4 x5
x1 3 1 1 −7/8 0 −1/4 0
x3 11 −2 0 9/8 1 3/4 0
x5 1 1 0 −3/8 0 3/4 0
−18 0 −1/2 0 −2 0
Все искусственные векторы (переменные) исключены, получен исходный опорный план x0 =
(3, 0, 11, 0, 5), при этом все величины zj − cj ≤ 0, значит, полученный опорный план будет опти-
мальным. Значение формы равно −18. Задача решена.
Рассмотрим еще один пример:
x4 +x5 − max
2x2 −x3 −x4 +x5 ≥ 0
−2x1 +2x3 −x4 +x5 ≥ 0
x1 −2x2 −x4 +x5 ≥ 0
x1 +x2 +x3 =1
xj ≥ 0, j = 1, 5
Приведем задачу к каноническому виду, для этого от левых частей первых трех неравенств отнимем
дополнительные переменные x6 , x7 , x8 соответственно. Задача примет вид
x4 +x5 − max
2x2 −x3 −x4 +x5 −x6 ≥ 0
−2x1 +2x3 −x4 +x5 −x7 ≥ 0
x1 −2x2 −x4 +x5 −x8 ≥ 0
x1 +x2 +x3 = 1
xj ≥ 0, j = 1, 8
Уже видно из условий задачи, единичные вектора-столбцы отсутствуют. Однако единичный ба-
зис можно получить, умножив первые три уравнения на −1, а в последнее ввести искусственную
переменную x9 . После этих простейших преобразований имеем расширенную задачу
x4 +x5 +10x9 − max
−2x2 +x3 +x4 −x5 +x6 =0
2x1 −2x3 +x4 −x5 +x7 =0
−x1 +2x2 +x4 −x5 +x8 =0
x1 +x2 +x3 =1
xj ≥ 0, j = 1, 9
