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

UptoLike

ВУЗ: 

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

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

Рубрика: 

5
CX → max
AX ≤ B, x ≥ 0, где C = (c
1
, c
2,
…,c
n
),
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
n
2
1
x
...
x
x
X
,
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
m
2
1
b
...
b
b
B
,
A=(α
ij
),
m,1i =
,
n,1j =
– матрица коэффициентов,
С - вектор коэффициентов целевой функции.
Область
{
}
0X,BAX,RXD
n
≥≤∈= называется областью до-
пустимых значений (ОДЗ) задач линейного программирования.
Соотношения (2), (3) называются системами ограничений зада-
чи ЛП.
Так как
DxDx
))x(fmin()x(fmax
∈∈
−−=
, то можно ограничиться изуче-
нием задачи одного типа.
Решением задачи ЛП называется вектор, удовлетворяющий сис-
теме ограничений задачи и оптимизирующий целевую функцию.
Другая форма представления задачи ЛП – каноническая. Она
имеет вид:
CX → max
AX = B, X ≥ 0.
Наряду с задачей ЛП в нормальной форме (1)-(3) рассмотрим
задачу
BU → min (4)
A
T
U ≥ C, U ≥ 0, (5)
где
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
m
2
1
u
...
u
u
U
- переменные двойственной задачи.
Задача (4), (5) называется двойственной по отношению к задаче
(1)-(3).
2. АЛГОРИТМ СИМПЛЕКС-МЕТОДА
Симплекс метод является наиболее распространенным вычис-
лительным методом, который может быть применен для решения лю-
бых задач ЛП как вручную, так и с помощью ЭВМ.
Этот метод позволяет переходить от одного допустимого реше-
ния к другому, причем так, что значения целевой функции непрерыв-
но возрастают. В результате оптимальное решение находят
за конеч-
ное число шагов. Алгоритм симплекс-метода позволяет также устано-
вить является ли задача ЛП разрешимой.
1. Рассмотрим задачу ЛП в нормальной форме (1)-(3). Сделаем
допущения: В ≥ 0.
Введем вектор Y такой, что Y = B - AX, Y∈R
m
, Y ≥ 0, 
                                   CX → max
                                              ⎛ x1 ⎞     ⎛ b1 ⎞
AX ≤ B, x ≥ 0, где C = (c1, c2,…,cn), X = ⎜ ... ⎟ , B = ⎜⎜ ...
                                              ⎜ x 2
                                                    ⎟      b2 ⎟,
                                              ⎜x ⎟       ⎜ b ⎟⎟
                                              ⎝ n⎠       ⎝ m⎠
A=(αij), i = 1, m , j = 1, n – матрица коэффициентов,
С - вектор коэффициентов целевой функции.
                    {                       }
      Область D = X ∈ R n , AX ≤ B, X ≥ 0 называется областью до-
пустимых значений (ОДЗ) задач линейного программирования.
      Соотношения (2), (3) называются системами ограничений зада-
чи ЛП.
      Так как max f ( x ) = − min(−f ( x )) , то можно ограничиться изуче-
                  x∈D          x∈D
нием задачи одного типа.
       Решением задачи ЛП называется вектор, удовлетворяющий сис-
теме ограничений задачи и оптимизирующий целевую функцию.
       Другая форма представления задачи ЛП – каноническая. Она
имеет вид:
                                CX → max
       AX = B, X ≥ 0.
       Наряду с задачей ЛП в нормальной форме (1)-(3) рассмотрим
задачу
                                  BU → min                        (4)
                                T
                               A U ≥ C, U ≥ 0,                    (5)
         ⎛ 1 ⎞
           u
где U = ⎜⎜ ...
           u 2 ⎟ - переменные двойственной задачи.
         ⎜ u ⎟⎟
         ⎝ m⎠
       Задача (4), (5) называется двойственной по отношению к задаче
(1)-(3).

      2. АЛГОРИТМ СИМПЛЕКС-МЕТОДА

      Симплекс метод является наиболее распространенным вычис-
лительным методом, который может быть применен для решения лю-
бых задач ЛП как вручную, так и с помощью ЭВМ.
      Этот метод позволяет переходить от одного допустимого реше-
ния к другому, причем так, что значения целевой функции непрерыв-
но возрастают. В результате оптимальное решение находят за конеч-
ное число шагов. Алгоритм симплекс-метода позволяет также устано-
вить является ли задача ЛП разрешимой.
      1. Рассмотрим задачу ЛП в нормальной форме (1)-(3). Сделаем
допущения: В ≥ 0.
      Введем вектор Y такой, что Y = B - AX, Y∈Rm, Y ≥ 0,


                                     5

Страницы