Симплекс-метод решения задачи линейного программирования. Исенбаева Е.Н. - 6 стр.

UptoLike

ВУЗ: 

ИжГТУ им. Калашникова | Ижевск

Составители: 

Рубрика: 

6
Y = (x
n+1
, x
n+2
, . . .,x
n+m
)
T
. Вектор Y называют балансовым, а x
n+1
,
x
n+2
, . . .,x
n+m
– балансовыми переменными.
Тогда систему ограничений (2) задачи ЛП можно записать:
α
11
х
1
+ α
12
х
2
+ …+α
1n
x
n
+х
n+1
= b
1
α
21
х
1
+ α
22
х
2
+ …+α
2n
x
n
+х
n+2
= b
2
. . . (6)
α
m1
х
1
+ α
m2
х
2
+ …+α
mn
x
n
+х
n+m
= b
m
причем x
j
≥ 0, mn,1j += (7)
Таким образом, задачу ЛП (1)-(3) привели от нормальной фор-
мы к канонической.
В целевую функцию балансовые переменные входят с нулевы-
ми коэффициентами, т.е.
Z
~
=c
1
x
1
+ c
2
x
2
+…+ c
n
x
n
+ 0x
n+1
+…+ 0⋅x
n+m
или
X
~
C
~
Z
~
⋅=
, где
C
~
,
X
~
∈ R
n+m
. (8)
Итак, вместо задачи (1)-(3) будем искать решение задачи (8), (6),
(7).
2. Положим j = 1. Взяв переменные х,…,х
n
за свободные и по-
ложив их равными нулю, а х
n+1
,…,х
n+m
– за базисные, находим первую
крайнюю точку.
1
X
~
= (0,…,0,b
1
,b
2
,...,b
m
).
n
3. Обозначим через А
k
вектор, вектор составленный из коэффи-
циентов при переменной х
k
, через С
Б
- вектор, составленный из коор-
динат, соответствующих базисным переменным.
Вычислим симплексные разности Δ
k
в j-той крайней точке по
формуле
Δ
k
= A
k
C
Б
-
C
~
k
,
mn,1k +=
. (9)
Заполняется симплекс-таблица (таблица 2) по указанным выше
правилам.
Таблица 2
C
~
c
~
1
c
~
2
…
c
~
n
c
~
n+1
…
c
~
n+m
Базис С
Б
B A
1
A
2
… A
n
A
n+1
… A
n+m
x
n+1
x
n+2
.
.
.
x
n+m
C
~
n+1
C
~
n+2
.
.
.
C
~
n+m
b
1
b
2
.
.
.
b
m
α
11
α
21
.
.
.
α
m1
α
12
α
22
.
.
.
α
m2
…
…
.
.
.
…
α
1n
α
2n
.
.
.
α
mn
1
0
.
.
.
0
…
…
.
.
.
…
0
0
.
.
.
1
Z
~
Δ
1
Δ
2
…
Δ
n
Δ
n+1
…
Δ
n+m
        Y = (xn+1, xn+2, . . .,xn+m)T. Вектор Y называют балансовым, а xn+1,
xn+2, . . .,xn+m – балансовыми переменными.
        Тогда систему ограничений (2) задачи ЛП можно записать:
                       α11х1 + α12 х2 + …+α1n xn +хn+1 = b1
                       α21х1 + α22 х2 + …+α2n xn +хn+2 = b2
                                            ...                           (6)
                      αm1х1 + αm2 х2 + …+αmn xn +хn+m = bm

                         причем xj ≥ 0, j = 1, n + m                (7)
      Таким образом, задачу ЛП (1)-(3) привели от нормальной фор-
мы к канонической.
      В целевую функцию балансовые переменные входят с нулевы-
ми коэффициентами, т.е.
                  ~
                  Z =c1x1 + c2x2 +…+ cnxn + 0xn+1 +…+ 0⋅xn+m
                                         или
                           ~ ~ ~           ~ ~
                           Z = C ⋅ X , где C , X ∈ Rn+m.            (8)
      Итак, вместо задачи (1)-(3) будем искать решение задачи (8), (6),
(7).
      2. Положим j = 1. Взяв переменные х,…,хn за свободные и по-
ложив их равными нулю, а хn+1,…,хn+m – за базисные, находим первую
крайнюю точку.
      ~
      X1 = (0,…,0,b1,b2,...,bm).
             n
     3. Обозначим через Аk вектор, вектор составленный из коэффи-
циентов при переменной хk, через СБ - вектор, составленный из коор-
динат, соответствующих базисным переменным.
     Вычислим симплексные разности Δk в j-той крайней точке по
формуле
                                  ~
                     Δk = Ak CБ - C k, k = 1, n + m .           (9)
     Заполняется симплекс-таблица (таблица 2) по указанным выше
правилам.
                                                         Таблица 2
                      ~      ~c     ~c     …       ~c     ~c       …   ~c
   Базис       СБ     C         1      2              n      n+1          n+m
                      B      A1     A2     …       An     An+1     …   An+m
              ~
    xn+1      C n+1   b1     α11    α12    …      α1n       1      …     0
    xn+2
              ~       b2     α21    α22    …      α2n       0      …     0
              C n+2
      .         .      .      .      .      .       .       .      .     .
      .         .      .      .      .      .       .       .      .     .
      .         .      .      .      .      .       .       .      .     .
    xn+m      ~       bm     αm1    αm2    …      αmn       0      …     1
              C n+m
                      ~
                      Z      Δ1     Δ2     …      Δn      Δn+1     …   Δn+m


                                      6

Страницы