Методы построения решений системы линейных неравенств

 

где

     X = (x₁, x₂, ..., x_n).

 

         Установим следующие два предложения.

1. Если тонка X есть решение системы (2') и k — любое неотрицательное число, то точка кХ есть снова решение системы (2').

2. Если X и У — два решения системы (2'), то X + У есть снова решение системы (2').

       Оба предложения легко следуют из доказанных в п. 1° свойств линейной функции. Действительно, пусть i — любой из номеров 1, 2, ..., m. Имеем

  L_i(kX) = kL_i(X) ≥ 0

(т. к. k ≥ 0 и L_i(X) ≥ 0), а также

 

                              L_i(X + Y) = L_t(X) + L_i(Y) ≥ 0

(т. к. L_i(X)≥ 0 и L_i(Y) ≥ 0).

       Из предложений 1 и 2 непосредственно вытекает такое следствие.

       Если некоторые точки Х₁, Х₂,…, Х_р являются решениями системы (2'), то и любая точка вида

 

                               k₁X₁ + k₂X₂ + ... + k_pX_p,

 

где k₁, k₂,...,k_p - неотрицательные числа, тоже является решением системы (2').

       Действительно, каждая из точек k₁X₁ + k₂X₂ + ... + k_pX_p в силу предложения 1 является решением системы (2'), но тогда и сумма этих точек в силу предложения 2 будет решением системы (2').

      Условимся называть любую точку вида (3'), где 
k₁, k₂, ..., k_p — неотрицательные числа, неотрицательной комбинацией точек X₁, X₂,..., X_p. Тогда указанное выше следствие будет допускать такую формулировку.

      Неотрицательная комбинация любого числа решений однородной системы (2) есть снова решение этой системы.

      3. Фундаментальный набор решений. Введем такое определение.

           Набор из конечного числа решений  X₁, X₂,..., X_p  однородной системы (2') называется фундаментальным набором решений, если любое решение X этой системы может быть задано формулой

 

                          X = k₁X₁ + k₂X₂ + ... + k_pX_p,                                        (4')

 

где k₁, k₂, ..., k_p — неотрицательные числа. В этом случае, следовательно, формула (4), в которой k₁, k₂, ..., k_p — любые неотрицательные числа, дает обозрение всех решений системы (2'). Отсюда ясно, что нахождение фундаментального набора решений есть задача первостепенной важности при исследовании системы (2'). Конечной целью наших построений и будет как раз являться выработка алгоритма, позволяющего с помощью весьма простых операций находить фундаментальный набор решений для любой системы  (2').

     4. Построение фундаментального набора для системы, состоящей из одного неравенства. Построим фундаментальный набор решений для неравенства

       

                   

где числа а₁, а₂, ..., не равны одновременно нулю. Для этой цели рассмотрим наряду с неравенством (5') уравнение

 

 

          Из свойств линейной функции, доказанных в п. 1, легко вытекают следующие два предложения:

1. Если X — какое-нибудь решение уравнения (6') и k — любое число, то kX — снова решение уравнения  (6').
2. Если X и У— два решения уравнения (6'), то X + У есть снова решение уравнения (6).

       По условию, среди чисел а₁, а₂, ..., имеются не равные нулю. Положим, например, что а_п ≠ 0. Тогда уравнение можно записать в виде

x_n = — ().

Полагая = l, = 0, ..., = 0, найдем из последнего уравнения x_n = - .  

           Таким образом, точка

 

X₁ = (1, 0, …, 0, - ),

 

является решением уравнения (6'). Аналогичным образом можно получить решения

 

X₂ = (0, 1, …, 0, - ),

………………………

    X_n-1 = (0, 0, …, 1, - ).

 

        Пусть теперь

                              Х = ()

 

— любое решение уравнения (6'). Имеем, согласно (6''),

а_п = — + … + = +(— )+ … +(— ).

            Рассматривая точку

 X₁ + X₂+ ... + = (1, 0, …, 0, )+ (0, 1, …, 0, ) + …           + (0, 0, …, 1, ),

убеждаемся, что ее координаты совпадают  с координатами точки X. Поэтому справедливо равенство

Х =Х₁ + Х₂ + ... + .

 

         Добавим теперь к построенным ранее точкам X₁, X₂,..., X_n-1, X_n  еще одну:

 

                                                X_n = (X₁+X₂+…+X_n-1).                                          (9')

 

           Из указанных в начале этого пункта свойств решений уравнения (6') следует, что точка Х_п тоже является решением. Теперь нетрудно доказать следующий факт: любое решение X уравнения (6') является неотрицательной комбинацией решений Х₁, Х₂,…, X_n-1, X_n.

В самом деле, пусть  — положительное число, превосходящее любое из чисел ||, ||, …, ||. Из (8') и (9') следует

Х =() Х₁ + ()Х₂ + ... +()Х_п-1 + Х_п,

что и служит доказательством  нашего утверждения.

           Для краткости дальнейших записей обозначим левую часть уравнения (6') через L(X). Выберем какое-нибудь решение уравнения L(X)=1 и обозначим это решение X_n+1. Мы утверждаем, что набор точек

                              Х₁, Х₂,…, X_n-1, X_n, Х_п+1

является фундаментальным  набором решений для неравенства (5'),

            В самом деле, каждая из указанных точек удовлетворяет неравенству (5'). Пусть теперь X'— любое решение этого неравенства; следовательно, L(X')=a, где        а ≥ 0. Тогда точка

 

X = X' — аХ_п+1

 

удовлетворяет уравнению (6'), т. к.

 

L(X) = L(X')-aL(X_n+l) = a-a·1=0.

 

        Если теперь записать

Х' = Х + аХ_n+1

и учесть, что точка X является неотрицательной комбинацией точек Х₁, ..., X_n-1, Х_п, то станет ясно, что X' представима в виде неотрицательной комбинации точек (10').

      Рассмотрим конкретный пример. Пусть требуется построить фундаментальный набор решений для неравенства

                       - 2 х₁ - 4х₂ + х₃ ≥ 0

с тремя неизвестными х₁, х₂, х₃.

          Прежде всего записываем уравнение

 

- 2 х₁ - 4х₂ + х₃ = 0

и разрешаем его относительно одного из неизвестных, например, Х₃:

                        х₃ = 2 х₁ + 4 х₂.

 

            Теперь последовательно полагаем одно из неизвестных х₁ , х₂ (входящих в правую часть уравнения) равным 1, а остальные нулю. Получаем такие решения:

Х₁ = (1,0,2),      Х₂ = (0, 1, 4).

            Далее, в качестве Х₃ берем точку

                              Х₃ = - ( Х₁+ Х₂) = (-1, -1, -6)

и, наконец, за X₄ принимаем одно из решений уравнения

                           - 2 х₁ - 4x₂ + x₃= 1,

например, Х₄, = (0, 0, 1).

             Точки Х₁, Х₂ , Х₃, Х₄  образуют фундаментальный набор решений для неравенства (11'). Общее решение имеет вид

 

X = k₁Х₁ + k₂X₂ +k₃X₃ + k₄X₄ = k₁(1,0,2) + k₂(0, 1.4) + k₃(-1,-1.-6) + k₄(0, 0, 1)

или

                                     х₁ = k₁ — k₃,

                                     x₂ = k₂ — k₃,

х₃ = 2k₁ + 4 k₂ — 6 k₃ + k₄,

где k₁,k₂,k₃,k₄ — произвольные неотрицательные числа.

5. Перестройка фундаментального набора решений при добавлении к системе еще одного неравенства. Чтобы научиться строить фундаментальные наборы решений, рассмотрим вначале такую задачу.

Пусть дана однородная система

 

 

линейных неравенств. Пусть, далее, известен фундаментальный набор решений

Х₁, Х₂, ..., Х_р

для этой системы. Требуется построить фундаментальный набор решений для системы, полученной добавлением к (12') еще одного неравенства

.

          Решения системы (12')—это в точности все неотрицательные комбинации точек Х₁, Х₂, ..., Х_р. Среди этих комбинаций нам нужно выбрать такие, которые удовлетворяли бы неравенству (13') и, более того, составили бы фундаментальный набор решений для системы (12'), (13').

     По отношению к функции L(X) —левой части неравенства (13')— все точки Х₁, Х₂, ..., Х_р можно разбить на три группы: точки, для которых , точки, для которых L(X) < 0 и, наконец, точки, для которых L (X) = 0.  Точки первой группы обозначим , , ..., , точки второй группы — , , ..., ,  точки   третьей   группы — , , ..., .

        Таким образом,

, ..., , , ..., ,  ..., .

— это те же самые точки Х₁, Х₂, ..., Х_р, но только расположенные в другом порядке.

     Разумеется, все точки = 1, …, k) удовлетворяют неравенству (13'). То же самое относится и к ( = 1, ..., s). Что же касается точек ( = 1, ..., l), то из них ни одна не является решением неравенства (13'). Однако, из каждой пары

,

(одна точка «плюсовая» и одна  «минусовая») можно образовать  неотрицательную комбинацию

,

так, чтобы она удовлетворяла  условию L(X) = 0. Для этого следует взять

 

                                 a= - L), b= L().

 

         Действительно, числа а и b положительны и, кроме того,

L+b)=aL()+bL()= - L) L() + L)=0.

           Обозначим точку (14'), где а и b имеют указанные выше значения, через :

  = -L() + L.

Ответ к поставленной задаче даёт следующая

           Теорема:   Точки            , ..., ,, ...,

 

(всего здесь записано k + s + kl точек) образуют фундаментальный набор решений для системы (12'), (13').

          Чтобы доказать теорему, установим сначала такую лемму.

      Лемма. Любая неотрицательная комбинация точек и может быть представлена как неотрицательная комбинация точек , или же как неотрицательная комбинация точек .

      Доказательство теоремы. Прежде всего заметим, что каждая из точек (17') удовлетворяет системе (12'), (13'). Поэтому, чтобы доказать теорему, нам остается лишь проверить следующее: если какая-то точка X является решением системы (12'), (13'), то она представима в виде неотрицательной комбинации точек (17').

      Будучи решением системы (12'), точка X представляется в виде неотрицательной комбинации ее фундаментальных точек Х₁, Х₂, ..., Х_р:

X=_+…+ + +…+ ++…+,

 

где все коэффициенты а₁, ..., a_k, b₁ ,…, b_l , с₁, ..., с_s неотрицательны.

        Если все числа b₁, …, b_l равны нулю, то, очевидно, доказывать нечего. Предположим поэтому, что среди указанных чисел имеются строго положительные. Заметим, что тогда среди чисел a₁, …, a_k тоже имеются строго положительные: в противном случае получилось бы

 

L(X) = b₁L()+ ... + b_lL() + c_lL) + ... + c_sL),

 

что невозможно, так как X удовлетворяет неравенству (13').

        Допустим, для определенности, что а₁ > 0 и b₁ > 0. Пользуясь леммой, можно заменить сумму неотрицательной комбинацией точек или же точек _. Если в выражении для точки X произвести  такую  замену, то общее число отличных от нуля  коэффициентов   при  _,  уменьшится по крайней мере на 1. Если при этом окажется, что во вновь полученном выражении для X не все коэффициенты при равны нулю, то снова заменим одну из сумм вида неотрицательной комбинацией точек или же точек в результате число отличных от нуля коэффициентов при _{, ..., ,} уменьшится еще по крайней мере на 1. Так будет продолжаться до тех пор, пока для точки X не получится выражение, в котором все коэффициенты при будут равны нулю. Мы придем тогда к равенству вида

 

X = _+…++ + _+…+,

 

где все коэффициенты справа больше либо равны нулю. Но это и  есть требуемое представление для X. Теорема доказана.

        6. Существование и способ построения фундаментального набора решений. Рассмотрим произвольную систему однородных линейных неравенств. Для первого неравенства системы можно (способом, описанным в п. 4°) построить фундаментальный набор решений. Присоединив к первому неравенству второе, можно, опираясь на теорему п. 5°, построить фундаментальный набор решений для системы, состоящей из первых двух неравенств. Далее присоединяем третье неравенство и т. д., пока не получим фундаментальный набор решений для всей исходной системы неравенств. Этим доказано существование и одновременно указан способ построения фундаментального набора решений.