Системы линейных неравенств. Зоркальцев В.И - 82 стр.

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

82
{
}
{}
1
1
min : ,
:,0.
T
n
FcxxX
XxRAxbx
=∈
=∈ = ≥
Если получим, что оптимальное по этой задаче решение
x
находится во
множестве
riX , то имеем
0
{: ,0,() 0,()}
n
j
j
XxRAxbx jJxи xjJx=∈ = ≥ ∈ = ∈
– множество оптимальных решений данной задачи и допустимых решений
последующей задачи. Отсюда очевидно, что нулевые компоненты данного
вектора
x
останутся таковыми при всех остальных критериях,
следовательно, эти переменные при решении задачи минимизации по
следующему критерию можно просто исключить из рассмотрения. Это
способствует сильному упрощению такого класса задач, так как
аналогичную процедуру можно проделывать на последующих этапах
решения задачи, используя информацию о том, что полученное на
предыдущем шаге решение принадлежит
множеству относительно
внутренних точек допустимой области задачи линейного
программирования следующего этапа.
5. 3 Ограниченность и неограниченность переменных взаимно
двойственных задач ЛП
На основе теорем об альтернативных системах линейных неравенств
можно доказать ряд других полезных и интересных фактов о соотношении
взаимно двойственных задач линейного программирования. В частности,
можно прояснить вопрос, какие переменные прямой и двойственной задач
ограничены и не ограничены на множествах допустимых решений прямой
и двойственной задач.
Пусть в определениях (2.2), (2.3) линейных
подпространств
S
и
⊥
S
используется та же матрица A, что и в задачах (1), (2). Пусть
)(
+
SJ и
)(
⊥
+
SJ – введенные в доказательстве теоремы 3.5 множества индексов, для
которых, согласно этой теореме,
0>
j
x , 0
=
j
y при
)(
+
∈
SJj
,
0=
j
x , 0>
j
y при
)(
⊥
+
∈ SJj
для
+
∈riSx
,
⊥
+
∈riSy
. Отсюда следует, что справедлива
Теорема 2. Пусть
∅
≠X,
∅
≠
U
. Тогда при всех X
∈ и при всех
U
u ∈ :
– компонента
j
x ограничена сверху, компонента )(ug
j
не
ограничена сверху для любого )(
⊥
+
∈ SJj;
– компонента
j
x не ограничена сверху, компонента )(ug
j
ограничена сверху для любого )(
+
∈
SJj. 
                                     {
                           F 1 = min c1T x : x ∈ X ,}
                                {
                           X = x ∈ R n : Ax = b, x ≥ 0 .  }
Если получим, что оптимальное по этой задаче решение x находится во
множестве riX , то имеем
          X = {x ∈ R n : Ax = b, x j ≥ 0, j ∈ J ( x) и x j = 0, j ∈ J 0 ( x)}
– множество оптимальных решений данной задачи и допустимых решений
последующей задачи. Отсюда очевидно, что нулевые компоненты данного
вектора x останутся таковыми при всех остальных критериях,
следовательно, эти переменные при решении задачи минимизации по
следующему критерию можно просто исключить из рассмотрения. Это
способствует сильному упрощению такого класса задач, так как
аналогичную процедуру можно проделывать на последующих этапах
решения задачи, используя информацию о том, что полученное на
предыдущем шаге решение принадлежит множеству относительно
внутренних      точек       допустимой          области      задачи          линейного
программирования следующего этапа.
      5. 3 Ограниченность и неограниченность переменных взаимно
                           двойственных задач ЛП
     На основе теорем об альтернативных системах линейных неравенств
можно доказать ряд других полезных и интересных фактов о соотношении
взаимно двойственных задач линейного программирования. В частности,
можно прояснить вопрос, какие переменные прямой и двойственной задач
ограничены и не ограничены на множествах допустимых решений прямой
и двойственной задач.
     Пусть в определениях (2.2), (2.3) линейных подпространств S и S ⊥
используется та же матрица A, что и в задачах (1), (2). Пусть J ( S + ) и
J ( S +⊥ ) – введенные в доказательстве теоремы 3.5 множества индексов, для
которых, согласно этой теореме,
                              x j > 0 , y j = 0 при j ∈ J ( S + ) ,

                              x j = 0 , y j > 0 при j ∈ J ( S +⊥ )

для x ∈ riS+ , y ∈ riS+⊥ . Отсюда следует, что справедлива
    Теорема 2. Пусть X ≠ ∅ , U ≠ ∅ . Тогда при всех x ∈ X и при всех
u ∈U :
      – компонента x j ограничена сверху, компонента g j (u ) не
ограничена сверху для любого j ∈ J ( S +⊥ ) ;
     – компонента x j не ограничена сверху, компонента                         g j (u )
ограничена сверху для любого j ∈ J ( S + ) .

                                           82

Страницы