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

величину u m+1 вектор u будет допустимым решением двойственной
задачи. Причем будет выполняться равенство (13) c Τ x = d = bT u . Это в
силу неравенства (12) означает, что u ∈U . Из (13) и (4), (5) имеем (14).
      Из теоремы 3.7 применительно к системам неравенств (16) – (18) и
(19) – (21) следует существование решений удовлетворяющих условию
(15).
      Теорема 1 доказана.
      Замечания. По введенной И.И. Ереминым классификации, первые
три ситуации называются несобственными задачами линейного
программирования III, I и II рода. Идея использования для этой
классификации множеств рецессивных направлений X% , U% получена на
основе статьи Астафьева [1].
      Соотношения (8) – (11) могут быть полезными для формирования
конструктивных критериев выявления случаев отсутствия оптимальных
решений у задач линейного программирования. Согласно приведенной
теореме у обеих задач (1), (2) либо имеется оптимальное решение, либо не
имеется. Случай, когда одна задача имеет оптимальное решение, а другая
не имеет невозможен. Причины отсутствия решений у взаимно-
двойственных задач линейного программирования могут быть разными. В
теореме выявлены три возможные причины этого: несовместность
ограничений задачи (1), задачи (2) и обеих задач (1) и (2). Согласно (9) –
(11) для того, чтобы констатировать отсутствие оптимальных решений
обеих задач (1), (2), достаточно найти либо вектор x ∈ X% , либо вектор
u ∈U% .
         5.2 Относительно внутренние точки оптимальных решений
      Согласно доказанной теореме, среди оптимальных решений задач (1),
(2) существуют особые решения, для которых справедливо не только
условие дополняющей нежесткости (14), но и соотношение (15). Это
означает, что для любого j = 1, ..., n либо x j = 0 и g j (u ) > 0 , либо g j (u ) = 0
и x j > 0 . Такие решения x , u имеют максимальные среди всех
оптимальных решений, нерасширяемые далее наборы неактивных
ограничений (т. е. условий-неравенств, выполняемых как строгие
неравенства).
     Решения   x , u , удовлетворяющие условиям дополняющей
нежесткости в строгой форме, будут относительно внутренними точками
множеств оптимальных решений задач (1), (2). Оптимальные решения из
ri X и riU имеют ряд преимуществ по сравнению с произвольными
оптимальными решениями из X и U . В частности, такие особые решения
полезны при анализе устойчивости решений задач (1), (2) к варьированию
коэффициентов матрицы A и векторов c и b.


                                         79