ВУЗ:
Составители:
Рубрика:
12
Мы видим, что критерий оптимальности опорного плана не выполняется, так как z
1
− c
1
< 0.
Следовательно, вектор A
1
вводится, а вектор A
4
выводится из базиса. Переменная x
4
меняется на
x
1
. Таблица 2.
c
0
x
1
1
x
2
2
x
1
3
x
0
4
x
2
67 0 1 1/52/5
x
1
22 1 0−1/53/5
40 0 0 1 4
опорный план x
2
=(2, 6, 0, 0)
Так как все z
j
− c
j
≥ 0, j =1, 2, 3, 4, то полученный опорный план оптимален.
Искусственный базис
Как мы уже убедились, удобно начинать решение задачи, когда она имеет базис, составленный
из m единичных векторов. В этом случае в исходной таблице x
j
=
x
ij
.
.
.
x
mj
=
2
ij
.
.
.
2
mj
= A
j
,
j =
1,n. Однако многие задали ЛП либо не содержат единичных векторов, либо содержат, но их
меньше m. В этом случае пользуются искусственным базисом. Допустим, что имеем задачу ЛП
канонического вида:
c
1
x
1
+ c
2
x
2
+ ···+ c
n
x
n
− min
a
11
x
1
+ a
12
x
2
+ ···+ a
1n
x
n
= b
1
a
21
x
1
+ a
22
x
2
+ ···+ a
2n
x
n
= b
2
.
.
.
.
.
.
.
.
.
a
m1
x
1
+ a
m2
x
2
+ ···+ a
mn
x
n
= b
m
x
j
≥ 0,j=1, 2,...,n
Если среди векторов-столбцов матрицы A нет единичных, мы вводим в каждое i – е уравнение
искусственную переменную x
n+i
с коэффициентом ω>0 в линейной форме, который можно не
фиксировать, считая его очень большим.
Таким образом, приходим к расширенной задаче
c
1
x
1
+ c
2
x
2
+ ···+ c
n
x
n
+ ωx
n+1
+ ···+ ωx
n+m
− min
при ограничениях
a
11
x
1
+ a
12
x
2
+ ···+ a
1n
x
n
+ x
n+1
= b
1
a
21
x
1
+ a
22
x
2
+ ···+ a
2n
x
n
+ x
n+2
= b
2
... ...
a
m1
x
1
+ a
m2
x
2
+ ···+ a
mn
x
n
+ x
n+m
= b
m
x
j
≥ 0,j=1, 2,...,n,n+1,...,n+ m
Векторы A
n+1
,A
n+2
,...,A
n
m
при искусственных переменных образуют единичный базис, называе-
мый искусственным. Если исходиная задача имеет допустимые планы, то применение симплексного
метода к расширенной задаче обеспечит построение опорного плана, то есть в ним все искусствен-
ные переменные будут равны нулю и в дальнейшем будут исключены из процесса решения. Если
же исходная задача не имеет допустимых планов (то есть условия задачи несовместны), то решение
расширенной задачи будет содержать по крайней мере одну искусственную переменную, отличную
от нуля.
Начальным опорным планом будет расширенный вектор
x
0
=(0, 0,...,0,b
1
,b
2
,...,b
m
)
Значение линейной формы z
0
= ω
b
i
,аz
j
− c
j
= ω
m
i=1
x
ij
− c
j
, j =1, 2,...,n.
Всякий раз, когда в базисе будут содержать искусственные векторы, разности z
j
− c
j
будут
линейными функциями ω. Каждая из разностей z
j
−c
j
состоит из двух слагаемых, одно из который
зависит от ω, а другое — нет. Решение расширенной части задачи осуществляется с помощью таблиц,
12
Мы видим, что критерий оптимальности опорного плана не выполняется, так как z1 − c1 < 0.
Следовательно, вектор A1 вводится, а вектор A4 выводится из базиса. Переменная x4 меняется на
x1 . Таблица 2.
c0 x11 x22 x13 x04
x2 6 7 0 1 1/5 2/5
x1 2 2 1 0 −1/5 3/5
40 0 0 1 4
опорный план x2 = (2, 6, 0, 0)
Так как все zj − cj ≥ 0, j = 1, 2, 3, 4, то полученный опорный план оптимален.
Искусственный базис
Как мы уже убедились, удобно начинать решение задачи, когда она имеетбазис,
составленный
xij 2ij
из m единичных векторов. В этом случае в исходной таблице xj = ... = ... = Aj ,
xmj 2mj
j = 1, n. Однако многие задали ЛП либо не содержат единичных векторов, либо содержат, но их
меньше m. В этом случае пользуются искусственным базисом. Допустим, что имеем задачу ЛП
канонического вида:
c1 x1 + c2 x2 + · · · + cn xn − min
a11 x1 + a12 x2 + · · · + a1n xn = b1
a21 x1 + a22 x2 + · · · + a2n xn = b2
.. .. ..
. . .
am1 x1 + am2 x2 + · · · + amn xn = bm
xj ≥ 0, j = 1, 2, . . . , n
Если среди векторов-столбцов матрицы A нет единичных, мы вводим в каждое i – е уравнение
искусственную переменную xn+i с коэффициентом ω > 0 в линейной форме, который можно не
фиксировать, считая его очень большим.
Таким образом, приходим к расширенной задаче
c1 x1 + c2 x2 + · · · + cn xn + ωxn+1 + · · · + ωxn+m − min
при ограничениях
a11 x1 + a12 x2 + · · · + a1n xn + xn+1 = b1
a21 x1 + a22 x2 + · · · + a2n xn + xn+2 = b2
... ...
am1 x1 + am2 x2 + · · · + amn xn + xn+m = bm
xj ≥ 0, j = 1, 2, . . . , n, n + 1, . . . , n + m
Векторы An+1 , An+2 , . . . , Anm при искусственных переменных образуют единичный базис, называе-
мый искусственным. Если исходиная задача имеет допустимые планы, то применение симплексного
метода к расширенной задаче обеспечит построение опорного плана, то есть в ним все искусствен-
ные переменные будут равны нулю и в дальнейшем будут исключены из процесса решения. Если
же исходная задача не имеет допустимых планов (то есть условия задачи несовместны), то решение
расширенной задачи будет содержать по крайней мере одну искусственную переменную, отличную
от нуля.
Начальным опорным планом будет расширенный вектор
x0 = (0, 0, . . . , 0, b1 , b2 , . . . , bm )
m
Значение линейной формы z0 = ω bi , а zj − cj = ω i=1 xij − cj , j = 1, 2, . . . , n.
Всякий раз, когда в базисе будут содержать искусственные векторы, разности zj − cj будут
линейными функциями ω. Каждая из разностей zj − cj состоит из двух слагаемых, одно из который
зависит от ω, а другое — нет. Решение расширенной части задачи осуществляется с помощью таблиц,
Страницы
- « первая
- ‹ предыдущая
- …
- 10
- 11
- 12
- 13
- 14
- …
- следующая ›
- последняя »
