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

UptoLike

ВУЗ: 

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

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

Рубрика: 

9
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
5
4
3
2
1
x
x
x
x
x
X
~
,
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
3
3
9
B
,
)0,0,0,2,1(C
~
=
,
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−=
1
1
1
A
1
,
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
=
1
1
1
A
2
,
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
0
0
1
A
3
,
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
0
1
0
A
4
,
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
1
0
0
A
5
.
Заполняем первую симплексную таблицу.
Таблица 3
C
~
1 2 0 0 0
Базис C
Б
B A
1
A
2
A
3
A
4
A
5
x
3
x
4
x
5
0
0
0
9
3
3
1
-1
1
1
1
-1
1
0
0
0
1
0
0
0
1
Z=0 -1 -2 0 0 0
Переменные x
3
, x
4
, x
5
образуют базис. Свободные переменные
х
1
, х
2
выбираем равными нулю. Тогда системе ограничений задачи
(18) удовлетворяет вектор
1
X
~
= (0,0,9,3,3)
T
(сравните значение базисных переменных с
вектором В в симплексной таблице).
1
X
~
- первая крайняя точка.
Так как x
3
, x
4
, x
5
– базисные переменные, то
C
Б
= (
543
c
~
,c
~
,c
~
) = (0,0,0).
Умножая скалярно вектор C
Б
и А
1
и вычитая из произведения
1
c
~
, находим симплексную разность Δ
1
. Аналогично, вычисляем ос-
тальные симплексные разности Δ
k
(
m,2k =
) в первой крайней точке.
Полученные значения записываем в последнюю строку таблицы.
Вычислим значение целевой функции в первой крайней точке:
)X
~
(Z
~
1
= С
Б
В = 0
Так как для первой крайней точки имеются отрицательные сим-
плексные разности, то она не является оптимальной. Ищем вторую
крайнюю точку. По формуле
0
k
kk
0
min
Δ
=
Δ
<Δ
находим переменную, вво-
димую в базис.
{}{}
2
0
21
0
22,1min,min
kk
Δ
=
−=
−
−
=
ΔΔ
<Δ<Δ
, т.е. в базис надо ввести х
2
.
Т.о. направляющий столбец с номером – 2.
Определим переменную, выводимую из базиса
00
0
k
0
ki
i
0
ik
i
b
b
min
α
=
α
>Δ
, 
          ⎛ x1 ⎞
      ~ ⎜x2 ⎟             ⎛9⎞ ~
      X = ⎜ x 3 ⎟ , B = ⎜⎜ 3 ⎟⎟ , C = (1,2,0,0,0) ,
          ⎜x4 ⎟           ⎝3⎠
          ⎝x5 ⎠
            ⎛1 ⎞             ⎛1 ⎞           ⎛1 ⎞            ⎛ 0⎞           ⎛ 0⎞
      A1 = ⎜⎜ − 1⎟⎟ , A 2 = ⎜⎜1 ⎟⎟ , A 3 = ⎜⎜ 0 ⎟⎟ , A 4 = ⎜⎜1 ⎟⎟ , A 5 = ⎜⎜ 0 ⎟⎟ .
            ⎝1 ⎠             ⎝ − 1⎠         ⎝ 0⎠            ⎝ 0⎠           ⎝1 ⎠
      Заполняем первую симплексную таблицу.
                                                                                      Таблица 3
                              ~         1             2   0         0        0
       Базис        CБ        C
                              B        A1            A2   A3        A4       A5
          x3         0        9         1             1   1         0        0
          x4         0        3        -1             1   0         1        0
          x5         0        3         1            -1   0         0        1
                             Z=0       -1            -2   0         0        0

       Переменные x3, x4, x5 образуют базис. Свободные переменные
х1, х2 выбираем равными нулю. Тогда системе ограничений задачи
(18) удовлетворяет вектор
       ~
       X1 = (0,0,9,3,3)T (сравните значение базисных переменных с
вектором В в симплексной таблице).
       ~
       X1 - первая крайняя точка.
       Так как x3, x4, x5 – базисные переменные, то
       CБ = ( ~c3 , ~c4 , ~c5 ) = (0,0,0).
       Умножая скалярно вектор CБ и А1 и вычитая из произведения
~c , находим симплексную разность Δ . Аналогично, вычисляем ос-
  1                                        1

тальные симплексные разности Δk ( k = 2, m ) в первой крайней точке.
Полученные значения записываем в последнюю строку таблицы.
     Вычислим значение целевой функции в первой крайней точке:
      ~ ~
      Z(X1 ) = СБ В = 0
     Так как для первой крайней точки имеются отрицательные сим-
плексные разности, то она не является оптимальной. Ищем вторую
крайнюю точку. По формуле min Δ k = Δ k 0 находим переменную, вво-
                                        Δ k <0
димую в базис.
     min{Δ 1 , Δ 2 } = min{− 1,−2} = −2 = Δ 2 , т.е. в базис надо ввести х2.
      Δ k <0             Δ k <0
Т.о. направляющий столбец с номером – 2.
      Определим переменную, выводимую из базиса
           b      b i0
       min i =            ,
          α ik 0 α i 0k 0
         Δ k >0




                                                 9

Страницы