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

                           −u1 − 2u2 = −5,
                           −2u1 − 3u2 = −8,
                           −3u1 − 4u2 = −11,
                           −4u1 − 5u2 = −14,
                           −3u1 − 2u2 ≥ −9,
                             u1 ≥ 0, u2 ≥ 0.

Вектор u T = (1,2) удовлетворяет         данной системе, следовательно,
избыточность неравенства − 5 x1 − 8 x2 − 11x3 − 14 x4 ≥ −9 по отношению к
исходной системе доказана.
      Можно воспользоваться и другими способами идентификации
ситуации избыточности условия (1) по отношению к системе (2) – на
основе поиска решения системы (7). Если будет найдено решение системы
(7), то неравенство (1) не является следствием системы (2). Если в
процессе поиска решения системы (7) будет установлено, что она не имеет
решения, т.е. ее условия противоречивы, то тем самым будут доказано, что
неравенство (1) является следствием системы неравенств (2).
      Проблему поиска решения системы (7) можно представить в виде
задачи линейного программирования относительно вектора переменных
 x ∈ Rn
                             (c, x) → min,                           (16)
при условии
                             Ax ≥ b.                                 (17)
      Не обязательно искать точное решение приведенной задачи линейного
программирования. Если в процессе ее решения будет получен вектор x ,
удовлетворяющий условию (17), при котором значение целевой функции
(16) меньше d , то тем самым будет найдено решение системы (7). Этим
будет доказано, что неравенство (1) не является следствием системы (2).
Данная ситуация возможна в двух случаях. Во-первых, если задача (16),
(17) имеет оптимальное решение и значение целевой функции в точке
оптимума меньше d . Во-вторых, если у нее целевая функция не
ограничена снизу на области допустимых по условию (17) векторов.
      В оставшихся двух случаях неравенство (1) является следствием
системы (2). Во-первых, это имеет место тривиальным образом (поскольку
пустое множество принадлежит любому множеству) в том случае, если в
процессе решения любым из методов задачи линейного программирования
(16), (17) выяснится, что ее ограничения (17) несовместны. Во-вторых, –
если для задачи (16), (17) будет найдено оптимальное решение и
оптимальное значение целевой функции окажется большим или равным d .




                                    67