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

UptoLike

ВУЗ: 

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

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

Рубрика: 

10
22
2
22
2
12
1
b
3
1
3
,
1
9
min
b
,
b
min
α
==
⎭
⎬
⎫
⎩
⎨
⎧
=
⎭
⎬
⎫
⎩
⎨
⎧
αα
, т.е. i
0
= 2.
Значит, направляющая строка имеет номер 2.
Обратите внимание, что отношение
32
3
b
α
не принималось во
внимание при нахождении значения индекса i
0
, так как значение ко-
эффициента α
32
< 0. Переменная, выводимая из базиса х
4
. Т.о. направ-
ляющий элемент α
22
= 1.
Используя один шаг метода Гаусса, введем в базис переменную
х
2
вместо переменной х
4
, применяя соотношение (12)-(16). Тем самым
найдем координаты второй крайней точки.
Заполняем вторую симплексную таблицу.
Таблица 4
C
~
1 2 0 0 0
Базис C
Б
B A
1
A
2
A
3
A
4
A
5
x
3
x
2
x
5
0
2
0
6
3
6
2
-1
0
0
1
0
1
0
0
-1
1
1
0
0
1
Z
~
=6
-3 0 0 2 0
Сейчас в базисе переменные x
3
, x
2
, x
5
(порядок именно такой).
Свободные переменные х
1
=0 и х
4
=0. Тогда базисные переменные при-
нимают значения x
3
=6, x
2
=3, x
5
=6. Вторая крайняя точка
2
X
~
=(0,3,6,0,6)
Т
. Вектор С
Б
для этой точки имеет вид:
C
Б
= (
523
c
~
,c
~
,c
~
) = (0,2,0).
Строку симплексных разностей вычисляем по формуле:
Δ
k
= C
Б
A
k
-
k
С
~
, mn,1k +=
Δ
1
= -3, Δ
2
= 0, Δ
3
= 0, Δ
4
= 2, Δ
5
= 0.
Значение целевой функции во второй крайней точке
)X
~
(Z
~
2
= С
Б
В =0⋅6 + 2⋅3 + 0⋅6 = 6.
Для второй крайней точки одна из симплексных разностей от-
рицательна, поэтому эта точка еще не является оптимальной.
Находим очередную крайнюю точку. Переменную х
1
вводим в
базис, так как
{}
11k
0
minmin
k
Δ
=
Δ
=
Δ
<Δ
, т.е. направляющий столбец имеет номер
1.
11
1
11
1
1i
i
0
bb
min
b
min
1i
α
=
⎭
⎬
⎫
⎩
⎨
⎧
α
=
⎭
⎬
⎫
⎩
⎨
⎧
α
>α
, т.е. i
0
=1, т.е. направляющая строка
имеет номер 1. 
          ⎧b     b ⎫        ⎧9 3⎫     b
      min ⎨ 1 , 2 ⎬ = min ⎨ , ⎬ = 3 = 2 , т.е. i0 = 2.
          ⎩ α 12 α 22 ⎭     ⎩1 1 ⎭    α 22
      Значит, направляющая строка имеет номер 2.
                                             b3
      Обратите внимание, что отношение            не принималось во
                                            α 32
внимание при нахождении значения индекса i0, так как значение ко-
эффициента α32 < 0. Переменная, выводимая из базиса х4. Т.о. направ-
ляющий элемент α22 = 1.
      Используя один шаг метода Гаусса, введем в базис переменную
х2 вместо переменной х4, применяя соотношение (12)-(16). Тем самым
найдем координаты второй крайней точки.
      Заполняем вторую симплексную таблицу.
                                                          Таблица 4
                         ~     1    2      0      0     0
        Базис     CБ     C
                         B     A1  A2      A3     A4   A5
         x3        0      6    2    0      1      -1    0
         x2        2      3    -1   1      0       1    0
         x5        0      6    0    0      0       1    1
                        ~
                        Z =6 -3     0      0       2    0

      Сейчас в базисе переменные x3, x2, x5 (порядок именно такой).
Свободные переменные х1=0 и х4=0. Тогда базисные переменные при-
нимают значения x3=6, x2=3, x5=6. Вторая крайняя точка
~
X 2 =(0,3,6,0,6)Т. Вектор СБ для этой точки имеет вид:
      CБ = ( ~c3 , ~c2 , ~c5 ) = (0,2,0).
      Строку симплексных разностей вычисляем по формуле:
                         ~
      Δk = CБAk - С k , k = 1, n + m
      Δ1 = -3, Δ2 = 0, Δ3 = 0, Δ4 = 2, Δ5 = 0.
      Значение целевой функции во второй крайней точке
       ~ ~
       Z(X 2 ) = СБ В =0⋅6 + 2⋅3 + 0⋅6 = 6.
      Для второй крайней точки одна из симплексных разностей от-
рицательна, поэтому эта точка еще не является оптимальной.
      Находим очередную крайнюю точку. Переменную х1 вводим в
базис, так как
       min Δ k = min{Δ1 } = Δ1 , т.е. направляющий столбец имеет номер
      Δ k <0
1.
              ⎧b ⎫    ⎧b ⎫ b
      min ⎨ i ⎬ = min ⎨ 1 ⎬ = 1 , т.е. i0=1, т.е. направляющая строка
      α i1 > 0 α
              ⎩ i1 ⎭  ⎩ α 11 ⎭ α11
имеет номер 1.


                                  10

Страницы