Задача линейного программирования. Горячев Л.В. - 9 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

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

Рубрика: 

9
Из (18) с очевидностью вытекает признак оптимальности опорного плана.
Теорема: Если для некоторого опорного плана x
∗
=(x
∗
1
,x
∗
2
,...,x
∗
n
) справедливо z
j
− c
j
≤ 0,
j =
1,n,тоx
∗
— оптимальный опорный план.
Доказательство теоремы дается в лекциях. Нетрудно показать при решении задачи канониче-
ского вида на максимум, критерием оптимальности будут условия z
j
− c
j
≥ 0, j = 1,n.
При решении практической задачи, как правило, заранее неизвестно разрешима она или нет.
Это может быть обнаружено в ходе решения. В симплекс-методе достаточно просто может быть
обнаружена неограниченность линейной формы на множестве допустимых планов. Из условия (7)
вытекает, если для данного вектора A
p
: z
p
− c
p
> 0 и всех x
ip
≤ 0, то величина Θ сверху неограни-
чена. При любом Θ > 0 вектор X с отличными от нуля компонентами, вычисляемыми по (8), будет
планом. Тогда значение линейной формы на этом плане будет
(c, x)=(c, x
∗
) − Θ(z
p
− c
p
)
откуда с очевидностью следует, что (c, x) →∞при Θ →∞. Таким образом, если среди внебазисных
векторов A
j
, для которых ∆
j
= z
j
− c
j
> 0, найдется вектор, для которого вектор коэффициентов
разложения x
j
неположителен, то линейная форма задачи (10)–(13) неограниченна сверху.
Упражнение: сформулировать аналогичное утверждение для случая максимизации целевой
функции.
Схема симплекс-метода
шаги 0. Построение начального опорного плана.
1. Вычисление величин ∆
j
= z
j
− c
j
,j=1, 2,...,n.
2. Проверка опорного плана на оптимальность: если ∆
j
= z
j
− c
j
≤ 0, j =1, 2,...,n, то переход
к пункту 7, в противном случае к пункту 3.
3. Находим вектор A
l
0
, подлежащий исключению из базиса:
Θ
0
= min
i
x
i
x
ik
,x
ik
> 0
если min достигается для нескольких i, то выберем наименьшее из них.
4. Пересчитаем коэффициенты опорного плана по формулам
x
i
= x
∗
i
−
x
∗
i
x
lk
x
ik
x
k
=
x
∗
l
x
lk
Пересчитаем вектора коэффициентов разложения для всех базисных векторов A
j
:
x
ij
= x
ij
−
x
lj
x
lk
x
ij
,i= k
x
kj
=
x
lj
x
lk
5. Переход к шагу 1.
6. Оформление окончательного результата, конец.
Реализовать симплекс-метод удобно в виде последовательности таблиц, первая из которых имеет
                                                                                                       9

     Из (18) с очевидностью вытекает признак оптимальности опорного плана.
     Теорема: Если для некоторого опорного плана x∗ = (x∗1 , x∗2 , . . . , x∗n ) справедливо zj − cj ≤ 0,
  j = 1, n, то x∗ — оптимальный опорный план.
     Доказательство теоремы дается в лекциях. Нетрудно показать при решении задачи канониче-
  ского вида на максимум, критерием оптимальности будут условия zj − cj ≥ 0, j = 1, n.
     При решении практической задачи, как правило, заранее неизвестно разрешима она или нет.
  Это может быть обнаружено в ходе решения. В симплекс-методе достаточно просто может быть
  обнаружена неограниченность линейной формы на множестве допустимых планов. Из условия (7)
  вытекает, если для данного вектора Ap : zp − cp > 0 и всех xip ≤ 0, то величина Θ сверху неограни-
  чена. При любом Θ > 0 вектор X с отличными от нуля компонентами, вычисляемыми по (8), будет
  планом. Тогда значение линейной формы на этом плане будет

                                       (c, x) = (c, x∗ ) − Θ(zp − cp )

  откуда с очевидностью следует, что (c, x) → ∞ при Θ → ∞. Таким образом, если среди внебазисных
  векторов Aj , для которых ∆j = zj − cj > 0, найдется вектор, для которого вектор коэффициентов
  разложения xj неположителен, то линейная форма задачи (10)–(13) неограниченна сверху.
     Упражнение: сформулировать аналогичное утверждение для случая максимизации целевой
  функции.

                                       Схема симплекс-метода

шаги 0. Построение начального опорного плана.

     1. Вычисление величин ∆j = zj − cj ,    j = 1, 2, . . . , n.

     2. Проверка опорного плана на оптимальность: если ∆j = zj − cj ≤ 0, j = 1, 2, . . . , n, то переход
        к пункту 7, в противном случае к пункту 3.

     3. Находим вектор Al0 , подлежащий исключению из базиса:

                                                       xi
                                           Θ0 = min        ,        xik > 0
                                                   i   xik

       если min достигается для нескольких i, то выберем наименьшее из них.

     4. Пересчитаем коэффициенты опорного плана по формулам
                                             
                                                         x∗
                                              xi = x∗i − i xik
                                                          xlk
                                                     x∗l
                                              xk =
                                                 
                                                     xlk

       Пересчитаем вектора коэффициентов разложения для всех базисных векторов Aj :
                                                    x
                                        xij = xij − lj xij ,          i = k
                                                     xlk
                                        xkj = xlj
                                                xlk

     5. Переход к шагу 1.

     6. Оформление окончательного результата, конец.

     Реализовать симплекс-метод удобно в виде последовательности таблиц, первая из которых имеет

Страницы