ВУЗ:
Составители:
Рубрика:
13
которые отличаются от аналогичных таблиц в первом случае тем, что z
j
− c
j
приписывается в двух
строках (m +1)и (m +2).
Для каждого j в (m +1) и (m +2) строки помещаются соответственно коэффициенты z
j
− c
j
при 1 и ω. Вектор, вводимый в базис, определяется наибольшим положительным элементом (m +2)
строки. Это же правило действует и в задачах на максимизацию. Очевидно, что на первой итерации
в базис вводится вектор, соответствующий max
j
i
x
ij
. Элементы (m +1) и (m +2) строк также
преобразуются по правилу исключения Гаусса.
Искусственный вектор, исключенный из базиса на некоторой итерации, вычеркивается из таб-
лицы. Следует заметить, что возможна ситуация, на которой на текущей итерации ни один из
искусственных векторов базиса не исключается.
Руководствуясь элементами (m +2) строки как критерием, продолжают отбирать вектора для
введения в базис до тех пор, пока либо все искусственные векторы не будут исключены из базиса,
либо (m +2) строка не будет больше содержать положительных элементов в столбцах, отвечающих
переменным.
В первом случае все элементы (m +2) строки равны нулю и соответствующий базис отвечает
некоторому опорному плану исходной задачи. После этого решение продолжается до получения оп-
тимального плана. Во втором случае. искусственные векторы находятся в базисе, и, следовательно,
искусственные переменные присутствуют в опорном плане.
Если при этом хотя бы одна из искусственных переменных отлична от нуля, то исходная зада-
ча не имеет допустимых планов, то есть условия несовместимые. Если уже во втором случае все
искусственные переменные опорного плана равны нулю, то при последующих итерациях в базис
вводится вектор, соответствующий максимальному положительному элементу, находящемуся под
нулевым элементом (m +2) строки. Этот процесс заставляет искусственные переменные, все еще
находящиеся в опорном плане, оставаться равными нулю и ведет к уменьшению значения линей-
ной формы. Применять это правило следует до получения оптимального плана, то есть пока среди
элементов (m +1) строки, расположенных над нулевыми элементами (m +2) строки, больше не
останется положительных, при этом элементы (m +2)строки преобразовывать не следует.
Как в первом, так и во втором случае, все элементы (m +2) строки неположительны, за исклю-
чением элемента (m +2, 0), где находится значение линейной формы на данном опорном плане.
Если исходная задача содержит несколько единичных векторов, то они должны быть включены
в базис, и число искусственных векторов будет меньше. Рассмотрим пример
x
1
+2x
2
− 3x
3
+ x
4
+ x
5
− min
при ограничениях
2x
1
− x
2
− 2x
4
− 2x
5
=4
−x
1
+2x
2
+ x
3
+ x
4
=8
x
1
− 2x
2
+2x
4
+3x
5
=6
x
j
≥ 0,j= 1, 5
Среди вектор-столбцов матрицы ограничений есть единичный вектор A
3
=(0, 1, 0)
T
, поэтому вво-
дим только два искусственных вектора A
6
=(1, 0, 0)
T
и A
7
=(0, 0, 1)
T
с искусственными перемен-
ными x
6
, x
7
. Расширенная задача имеет вид:
x
1
+2x
2
−2x
3
+x
4
+x
5
+ωx
6
+ωx
7
−min
2x
1
−x
2
−2x
4
−2x
5
+x
6
=4
−x
1
+2x
2
+x
3
+x
4
=8
x
1
−2x
2
+2x
4
+3x
5
+x
7
=6
x
j
≥ 0,j= 1, 7
Исходная таблица задачи. Таблица 0.
b
0
c
0
x
1
1
x
2
2
x
−2
3
x
1
4
x
1
5
x
ω
6
x
ω
7
x
6
4 ω 2 −10−2 −11 0
x
3
8 −2 −12 1 1 0 0 0
x
7
6 ω 1 −20 2 3 01
−16 1 −60−3 −3
−10 3
∗
−30 0 1
13
которые отличаются от аналогичных таблиц в первом случае тем, что zj − cj приписывается в двух
строках (m + 1) и (m + 2).
Для каждого j в (m + 1) и (m + 2) строки помещаются соответственно коэффициенты zj − cj
при 1 и ω. Вектор, вводимый в базис, определяется наибольшим положительным элементом (m + 2)
строки. Это же правило действует и в задачах на максимизацию.
Очевидно, что на первой итерации
в базис вводится вектор, соответствующий max xij . Элементы (m + 1) и (m + 2) строк также
j i
преобразуются по правилу исключения Гаусса.
Искусственный вектор, исключенный из базиса на некоторой итерации, вычеркивается из таб-
лицы. Следует заметить, что возможна ситуация, на которой на текущей итерации ни один из
искусственных векторов базиса не исключается.
Руководствуясь элементами (m + 2) строки как критерием, продолжают отбирать вектора для
введения в базис до тех пор, пока либо все искусственные векторы не будут исключены из базиса,
либо (m + 2) строка не будет больше содержать положительных элементов в столбцах, отвечающих
переменным.
В первом случае все элементы (m + 2) строки равны нулю и соответствующий базис отвечает
некоторому опорному плану исходной задачи. После этого решение продолжается до получения оп-
тимального плана. Во втором случае. искусственные векторы находятся в базисе, и, следовательно,
искусственные переменные присутствуют в опорном плане.
Если при этом хотя бы одна из искусственных переменных отлична от нуля, то исходная зада-
ча не имеет допустимых планов, то есть условия несовместимые. Если уже во втором случае все
искусственные переменные опорного плана равны нулю, то при последующих итерациях в базис
вводится вектор, соответствующий максимальному положительному элементу, находящемуся под
нулевым элементом (m + 2) строки. Этот процесс заставляет искусственные переменные, все еще
находящиеся в опорном плане, оставаться равными нулю и ведет к уменьшению значения линей-
ной формы. Применять это правило следует до получения оптимального плана, то есть пока среди
элементов (m + 1) строки, расположенных над нулевыми элементами (m + 2) строки, больше не
останется положительных, при этом элементы (m + 2) строки преобразовывать не следует.
Как в первом, так и во втором случае, все элементы (m + 2) строки неположительны, за исклю-
чением элемента (m + 2, 0), где находится значение линейной формы на данном опорном плане.
Если исходная задача содержит несколько единичных векторов, то они должны быть включены
в базис, и число искусственных векторов будет меньше. Рассмотрим пример
x1 + 2x2 − 3x3 + x4 + x5 − min
при ограничениях
2x1 − x2 − 2x4 − 2x5 = 4
−x1 + 2x2 + x3 + x4 = 8
x1 − 2x2 + 2x4 + 3x5 = 6
xj ≥ 0, j = 1, 5
Среди вектор-столбцов матрицы ограничений есть единичный вектор A3 = (0, 1, 0)T , поэтому вво-
дим только два искусственных вектора A6 = (1, 0, 0)T и A7 = (0, 0, 1)T с искусственными перемен-
ными x6 , x7 . Расширенная задача имеет вид:
x1 +2x2 −2x3 +x4 +x5 +ωx6 +ωx7 − min
2x1 −x2 −2x4 −2x5 +x6 =4
−x1 +2x2 +x3 +x4 =8
x1 −2x2 +2x4 +3x5 +x7 = 6
xj ≥ 0, j = 1, 7
Исходная таблица задачи. Таблица 0.
b0 c0 x11 x22 x−2
3 x14 x15 xω
6 xω
7
x6 4 ω 2 −1 0 −2 −1 1 0
x3 8 −2 −1 2 1 1 0 0 0
x7 6 ω 1 −2 0 2 3 0 1
−16 1 −6 0 −3 −3
−10 3∗ −3 0 0 1
