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

          Вернемся к системе (1). Пусть А₁ , A₂, ..., А_р — все вершины области . Множество <А_1,А₂, …А_р> — выпуклая оболочка системы точек А_1,А₂, …А_р —также принадлежит (т. к. — выпуклая область). Но тогда по лемме 1 и множество

<А_1, А₂, …, А_р>+

принадлежит . Покажем, что в действительности эта сумма совпадает с , т. е. что справедлива следующая

          Теорема. Если система неравенств нормальна, то

 

       = <А_1, А₂, …А_р>+ , 

 

где А_1,А₂, …А_р — все вершины области .

           Доказательство. Пусть Р — произвольная точка области , отличная от вершин области. И прямая A₁P пересекает выпуклую область по некоторому отрезку A₁A (рис. 2)

                                              

 

Рисунок 2 – Выпуклая область , которая пересекается по отрезку A₁A, с точкой А, лежащей на ограниченном ребре

Примечание – Источник: [1, с.37]

 

Так же можно рассмотреть  случай, когда A₁P пересекает выпуклую область по по лучу с началом в A₁ (рис. 3). Во втором случае Р - A₁ (лемма 2), следовательно, Р A₁+.

 

 

                                            

                                     

  Рисунок 3 – Выпуклая область , которая пересекается по лучу с началом в точке A₁

Примечание – Источник: [1, с.37]

 

          В первом же случае рассуждаем так: если точка А лежит на ограниченном ребре A_iA_j области , то Р принадлежит выпуклой оболочке точек  A₁, A_i, A_j, если же точка А лежит на неограниченном ребре с началом в вершине A_i (рис. 4), то по лемме 1 имеем А, в силу чего Р <A₁, A_i>+ . Таким образом, во всех случаях точка Р оказывается принадлежащей множеству <> + . Теорема доказана.

                                                    

            

Рисунок 4 – Выпуклая область , которая пересекается по отрезку A₁A, с точкой А, лежащей на неограниченном ребре

Примечание – Источник: [1, с.37]

 

           Для полного описания области не хватает только умения находить область Она представляет собой область решений однородной нормальной системы (2). К ее описанию мы и переходим.

            3. Однородная нормальная система неравенств (2).

Каждое из неравенств (2) определяет полуплоскость, граничная прямая которой  проходит через начало координат. Общая часть этих полуплоскостей и есть .

В данном случае среди граничных  прямых имеются по крайней мере две различные (система (2) нормальна). Следовательно, либо совпадает с началом координат (х = 0, у = 0), либо есть луч с вершиной в начале координат, либо представляет собой некоторый угол, меньший 180°, с вершиной в начале координат. Если мы будем знать две точки В₁ и В₂,лежащие на разных сторонах этого угла (рис. 5), то все точки угла запишутся в виде

B = t₁B₁+t₂В₂,                          

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

 

 

 

 

 

 

 

 

Рисунок 5 – Угол, меньший 180°, с вершиной в начале координат

Примечание – Источник: [1, с.38]

 

          Но отыскать точки В₁ и В₂ совсем нетрудно, если учесть, что каждая из них: а) принадлежит , т. е. удовлетворяет системе (2), и б) лежит на границе , т. е. удовлетворяет одному из уравнений (3). Если есть луч, то вместо (8) имеем

В = tВ₁,

 

где  B₁ — любая точка этого луча (отличная от начала), a t — произвольное неотрицательное число.

Пример 2. Найти область решений системы

 

 

а также область  решений системы примера 1.

           Решение. Система (10) нормальна: единственное решение соответствующей однородной системы уравнений

есть (0, 0).

           Выберем какую-либо точку, удовлетворяющую первому из уравнений (11) (но отличную от (0, 0)), например, точку С(—1, 1). Простой проверкой убеждаемся, что точка С удовлетворяет не всем неравенствам (10), следовательно, ни сама она, ни какая-либо точка луча ОС (отличная от начала О) не принадлежат . Рассмотрев точку — С (т.е. точку (1, —1)), находим, что она принадлежит Итак, В₁ =(1, —1). Второму уравнению удовлетворяет точка (2, 1); она тоже является решением системы (10), так что В₂ — (2, 1). Область состоит из точек

 

t₁B₁+t₂B₂=t₁(1, —1)+t₂(2, 1)=t₁+2t₂, —t₁+t₂,

 

 где t₁ и t₂ — произвольные неотрицательные числа. (рис. 6)

 

                                                   

Рисунок 6 – Область состоящая из точек В₁ =(1, —1) и В₂ — (2, 1)

Примечание – Источник: [1, с.39]

 

           Обращаясь к системе неравенств примера 1, мы замечаем, что соответствующая ей однородная система неравенств есть как раз (10). По доказанной выше теореме имеем     = <А₁, А₂>+ ,

где A₁(1, —2) и А₂(2, 0) — вершины области . Итак, состоит из точек

 

s(1, - 2)+(1- s)(2, 0)+(t₁+2t₂, -t₁+t₂)=(2-s+t₁+2t₂, -2s –t₁+t₂),

 

где s — любое число из промежутка [0, 1], а t₁, t₂ — любые неотрицательные числа. (рис. 7)

                                                  

Рисунок 7 – Область состоящая из точек А₁ =(1,-2) и А₂= (2,0)

Примечание – Источник: [1, с.39]

 4. Случай, когда система неравенств (1) не является нормальной. Это означает, что область решений однородной системы уравнений (3) содержит не только начало координат. Следовательно, все уравнения (3) определяют на

плоскости одну и ту же прямую, и эта прямая есть .

           Согласно лемме 1 область вместе с каждой своей точкой Р содержит прямую Р + (прямую, проходящую через Р параллельно ). Рассмотрим какую-нибудь прямую, не параллельную . Если мы будем знать, какие точки прямой принадлежат области , — множество этих точек обозначим , — то сможем найти и саму область , ибо тогда = + (рис. 8).

 

 

 

 

 

                                           

 

 

 

Рисунок 8 – Область ,где  = +

Примечание – Источник: [1, с.40]

 

           Уравнение прямой есть а₁x+b₁у = 0. В этом уравнении один из коэффициентов а₁ или b₁ отличен от нуля; пусть, например, b₁ ≠ 0. Тогда в качестве прямой , не параллельной , можно взять ось у (ее уравнение есть x = 0). В этом случае множество — будем теперь обозначать его — есть часть оси у, попавшая в . Чтобы найти это множество, следует положить в системе (1) х=0. Тогда получим систему неравенств

 

 

 

с одним неизвестным у. Заметим, что множество может быть или пустым множеством (тогда и пустое), или точкой, отрезком, лучом (но не всей осью у, ибо в противном случае есть вся плоскость, что невозможно). Найдя это множество, мы будем знать и область , ибо

=+

(если  не параллельна оси у).

 

 

1.2 Область решений системы неравенств с тремя неизвестными

 

  Наряду с системой

 

 

рассмотрим ещё 2 системы:

 

 

 

Область решений системы (1.1) обозначаем через , системы (1.2) – через , системы (1.3) – через . Можно сказать, что есть некоторая выпуклая многогранная область в пространстве, а – выпуклый многогранный конус.

1. Случай, когда система неравенств (1) нормальна. Тогда область не содержит прямых и, следовательно, имеет хотя бы одну вершину. В самом деле, если лежит в плоскости, то — выпуклая многоугольная область на плоскости, не содержащая прямых, и поэтому обязана иметь вершины. Если же область не лежит в плоскости, то рассмотрим ее границу. Она состоит из плоских граней, каждая из которых — как выпуклая многоугольная область, не содержащая прямых, — должна иметь вершины. Но легко видеть, что вершина любой грани является одновременно и вершиной области .

В каждой вершине А области сходятся по крайней мере три граничные плоскости, для которых точка А является единственной общей точкой. В самом деле, если бы это было не так, то все граничные плоскости, проходящие через А, или совпали бы, или имели бы общую прямую. Но тогда достаточно малый отрезок, проходящий через А и лежащий в общей граничной плоскости или на общей граничной прямой, принадлежал бы , что противоречит определению вершины.

Следуя сказанному выше внесём изменения в способ отыскания вершин. А именно, правильной подсистемой теперь следует называть подсистему не из двух, а из трех уравнений системы

 

 

при условии, что решение  (х, у, z) этой подсистемы единственно. При таком понимании правильной подсистемы способ отыскания вершин остается в точности тем же, что и раньше, а именно:

Чтобы найти все  вершины области , следует найти решения всех правильных подсистем системы (1.4) и отобрать среди них те, которые удовлетворяют исходной системе (1.1).

Пример 1. Найти вершины области , определенной с помощью системы неравенств

 

 

      В данном случае соответствующая однородная система уравнений имеет вид

 

                                             

 

Решая ее, убеждаемся, что  единственное решение есть (0, 0, 0) —  система (1.5) нормальна.

       Для нахождения вершин нам придется рассмотреть всевозможные подсистемы из трех уравнений системы (1.4):

 

 

 

 

 

      Проделав необходимые вычисления, найдем, что все подсистемы правильны, и их решениями являются точки

 

(), (0,0,1), (0,1,0), (1,0,0),

 

из которых первая не удовлетворяет системе (1.5), а остальные три удовлетворяют. Следовательно, вершины области :

 

A₁(1,0,0),   A₂ (0, 1,0),   A₃ (0,0, 1).

 

2. Нормальная  однородная система неравенств (1.2). Каждое из неравенств (1.2) определяет полупространство, граничная плоскость которого проходит через начало координат.

В данном случае пересечением граничных плоскостей является единственная точка — начало координат. Другими словами, множество — область решений системы (1.2) — есть выпуклый многогранный конус с единственной вершиной.  В нашем случае есть либо бесконечная выпуклая пирамида, либо плоский угол, либо луч, либо, наконец, одна точка (начало координат). Последний случай оставим пока в стороне. Во всех остальных случаях имеем

 

= (В₁, В₂, …, B_q),

 

где В₁ В₂, ..., B_q — какие-либо точки, выбранные по одной на каждом ребре конуса .  Найти такие точки можно, исходя из следующего соображения. Каждая из них: а) принадлежит , т. е. удовлетворяет системе (1.2), и б) принадлежит линии пересечения двух различных граней, т. е. удовлетворяет двум непропорциональным  уравнениям из системы (1.3).

Если окажется, что единственная точка, удовлетворяющая условиям а) и б), есть (0, 0, 0), то область совпадает с началом координат.

Пример 2. Найти область решений системы

 

 

и далее область  решений системы из примера 1.

      Прежде всего заметим, что система (1.6) связана с системой неравенств (1.5) из примера 1; именно, (1.6) есть однородная система, отвечающая (1.5). Следовательно, система (1.6) нормальна.

       В данном случае систему из двух непропорциональных уравнений можно составить шестью различными способами:

 

 

 

 

 

Для каждой из этих шести  систем выбираем два ненулевых решения: (х, у, z) и (-х, -у, -z). Например, для первой системы можно взять (3, —1, —1) и _(—3, 1, 1); неравенствам (6) удовлетворяет только первое из этих решений. Отсюда получаем точку B₁ = (3, —1, —1). Поступая аналогично с остальными пятью системами, находим точки В₂ = (—1, 3, —1) и В₃ = (—1, —1, 3). Итак, область состоит из точек вида

 

t₁B₁+t₂B₂+t₃B₃=(3t₁—t₂—t₃, —t₁+3t₂—t₃, —t₁—t₂+3t₃),

где t₁, t₂, t₃ — произвольные неотрицательные числа. Обратимся теперь к системе неравенств (1.5) из примера 1. Соответствующая ей однородная система, как уже отмечалось, есть как раз (1.6). Следовательно, область имеет вид

 

<A₁, A₂, A₃>+

 

и состоит из точек

 

s₁A₁+s₂A₂+s₃A₃+t₁B₁+t₂B₂+t₃B₃= s₁(1, 0, 0)+s₂(0, 1, 0)+s₃(0, 0, 1)+ t₁(3, -1, -1)+t₂(-1, 3, -1)+t₃(-1, -1, 3)=(s₁+3t₁-t₂-t₃, s₂-t₁+3t₂-t₃, s₃-t₁-t₂+3t₃),

 

где  числа  t₁, t₂, t₃  произвольные  неотрицательные, a s₁, s₂, s₃ неотрицательны и в сумме дают 1.

3°. Случай, когда система неравенств (1.1) не является нормальной. Это означает, что область решений однородной системы уравнений (1.3) содержит точки, отличные от начала координат. Так как представляет собой пересечение плоскостей, то возможны два случая:

1. есть прямая. Согласно лемме 1 область вместе с каждой своей точкой Р содержит прямую Р + . Рассмотрим какую-нибудь плоскость , непараллельную . Если мы будем знать, какие точки плоскости принадлежат области — множество этих точек обозначим , — то сможем найти и саму область , ибо тогда = +

Но, какова бы ни была прямая, в качестве непараллельной ей плоскости всегда можно выбрать одну из координатных плоскостей хОу, хОz или уОz. Допустим, например, что не параллельна плоскости yOz. Примем эту плоскость за . В этом случае множество — будем обозначать его теперь — есть часть плоскости yOz, попавшая в (рис. 9).