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

 

 

 

  

 

 

Рисунок 9 – Множество — часть плоскости yOz, попавшая в

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

 

Чтобы найти это множество, следует положить в системе (1.1) x = 0.  Тогда получим систему неравенств

 

 Найдя множество , сможем записать

 

 

(если прямая  не параллельна плоскости yOz), что и дает полное описание области .

Замечание. Если окажется, что множество пустое, то и пустое. Это означает, что система (1.1) несовместна.

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

 

                                                                                    (1.9)

 

    Рассмотрим соответствующую однородную систему уравнений 

 

 

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

 

и

 

    Выберем какую-нибудь точку В на прямой , отличную от начала координат. Для этого достаточно найти какие-нибудь три числа х, у, z (не равные од новременно нулю), удовлетворяющие первым двум уравнениям системы (1.10). Возьмем, например, 1, 1, 1. Итак, есть прямая ОВ, где В = (1, 1, 1).

Легко видеть, что прямая не параллельна, например, координатной плоскости yOz. Полагая в системе (1.9) х = 0, получим систему

                              

с двумя неизвестными у и z, которая нормальна. Проделав необходимые вычисления, найдем, что есть множество, состоящее из одной точки А() (в плоскости yOz). Следовательно, искомая область состоит из всех точек вида

A+tB=(0, )+t1(1, 1, 1)=(t, , ),                                 

где t — любое неотрицательное число (область - прямая, параллельная ).

2. есть плоскость. Тогда в качестве секущего множества берем какую-нибудь прямую, не параллельную этой плоскости; в частности, можно взять одну из координатных осей. Допустим, например, что ось z не параллельна ; примем ее за . Чтобы найти множество — часть оси z, попавшую в — следует положить в системе (1.1) х = 0, у = 0. Тогда получим систему неравенств:

 

Найдя множество сможем записать =+ (рис. 10).

 

 

 

 

 

 

 

Рисунок 10 – Множество =+

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

 

Замечание. Если множество   окажется пустым, то и пустое. В этом случае система (1.1) несовместна.

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

 

 

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

 

 

         Здесь второе уравнение есть следствие первого, поэтому область решений системы (1.14) есть плоскость , определяемая уравнением

 

 

 

        Легко видеть, что эта плоскость пересекает ось z в единственной точке и, следовательно, не параллельна оси z. Найдем множество .

    Полагая в системе (1.13) x=0, y=0, получим систему

 

           

 

из которой следует, что

 

 

Итак, есть множество + , состоящее из точек вида (0, 0, z) + (х, у, —x + y) = (x,y,z — x + y), где х и у произвольны, a z удовлетворяет неравенствам (1.15).

 

         1.3 Область решений системы неравенств с любым числом неизвестных

 

 В приложениях линейной алгебры чаще всего практический смысл имеют системы неравенств с числом неизвестных n > 3.

Для геометрического истолкования системы линейных неравенств с n неизвестными нам необходимо обратиться к так называемому n -мерному пространству.

Точка n-мерного пространства по определению задается упорядоченным набором из n чисел x₁, x₂, …, x_n, называемых координатами точки. Мотивом к подобному определению является тот основной для аналитической геометрии факт, что точка на плоскости характеризуется парой чисел, а в пространстве — тройкой чисел. В дальнейшем вместо того, чтобы говорить «точка М имеет координаты x₁, x₂, …, x_n», мы будем писать М = (x₁, x₂, …, x_n) или просто М(x₁, x₂, …, x_n). Точка (0, 0, ..., 0) называется началом   координат или просто началом.

Прежде всего укажем, что понимается под «отрезком» в n-мерном пространстве. В обычном пространстве отрезок M₁M₂ может быть охарактеризован как множество всех точек вида:               s₁M₁+ s₂M₂,

где s₁, s₂ — любые два неотрицательных числа, дающие в сумме 1. Переходя от трехмерного пространства к n-мерному, мы принимаем эту характеристику за определение отрезка. Точнее, пусть

 

M' (x'₁, x'₂, …, x'_n)   и    M" (x"₁, x"₂, …, x"_n)

 

— две произвольные точки n-мерного пространства. Тогда отрезком М'М" называется множество всех точек вида

s'M' + s"M" = (s'x'₁ + s"x"₁, s'x'₂ + s"x"₂, …, s'x'_n + s"x"_n),

 

где s', s" — любые два неотрицательных числа с суммой 1. При s' = 1, s" = 0 мы получаем точку М', при s' = 0, s" = 1 — точку М". Это — концы отрезка М'М". Остальные точки (они получаются при s' > 0, s" > 0) называются внутренними точками отрезка.

Из дальнейших понятий, относящихся  к n-мерному пространству, нам понадобится понятие гиперплоскости. Это — обобщение понятия плоскости в обычном трехмерном пространстве.

Гиперплоскостью в п-мерном пространстве называется совокупность точек М(x'₁, x'₂, …, x'_n), координаты которых удовлетворяют уравнению первой степени

                      a₁x₁+a₂x₂+…+a_nx_n+b=0,

 

где хотя бы одно из чисел a₁, а₂, ..., а_п (коэффициентов при неизвестных)  отлично от нуля. При n = 3 уравнение (1.1.2) принимает вид a₁x₁+a₂x₂+a₃x₃+b=0 — это есть не что иное, как уравнение плоскости в обычном пространстве (где координаты обозначены x₁, х₂, х₃, а не х, у, z).

По отношению к гиперплоскости (1.1.2) все n-мерное пространство разбивается на две части: область, в которой выполняется неравенство

 

                     a₁x₁+a₂x₂+…+a_nx_n+b ≥ 0,

и область, в которой

                     a₁x₁+a₂x₂+…+a_nx_n+b ≤ 0.

 

Эти области называются полупространствами. Таким образом, каждая гиперплоскость разбивает все пространство на два полупространства, для которых она является общей частью.

Понятие выпуклого тела также  обобщается на n-мерный случай. Множество точек в n-мерном пространстве называется выпуклым, если вместе с любыми двумя своими точками М' и М" оно содержит и весь отрезок М'М".

Нетрудно показать, что любое полупространство является выпуклым множеством. В самом деле, пусть точки M' (x'₁, x'₂, …, x'_n) и M" (x"₁, x"₂, …, x"_n)

принадлежат полупространству. Докажем, что и любая точка М отрезка М'М" также принадлежит этому полупространству.

Координаты точки М представляются в виде (1) или, что то же самое, в виде:                               

                                 x₁ = sx'₁ + (1 – s )x''₁ ,

 x₂ = sx'₂ + (1 – s )x''₂ ,                     (0 ≤ s ≤ 1)

                      …………………………

                      x_n = sx'_n + (1 – s )x''_n ,

 

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

 

a₁(sx'₁+(1 – s)x''₁)+ a₂(sx'₂+(1 – s)x''₂)+…+ a_n(sx'_n+(1 – s)x''_n)+b= s(a₁x'₁+a₂x'₂+…+a_nx'_n)+(1 - s)( a₁x''₁+a₂x''₂+…+a_nx''_n)+sb+(1 - s)b

 

(мы заменили число b суммой sb + (l—s) b), что равно

s[a₁x'₁+…+a_nx'_n+b] + (1 – s)[a₁x''₁+…+a_nx''_n+b].

Каждая из двух сумм, заключенных  в квадратные скобки, неотрицательна, поскольку обе точки М' и М" принадлежат полупространству. Следовательно, и все написанное выражение неотрицательно (ведь s ≥ 0 и (1 — s) ≥ 0). Этим доказано, что точка М принадлежит полупространству, т. е. что это полупространство выпукло.

Пусть дана система

 

Каждое из написанных неравенств определяет некоторое полупространство, а все написанные неравенства совместно — некоторую область в n-мерном пространстве, являющуюся пересечением конечного числа полупространств. Область является выпуклой, так как выпукло любое из образующих ее полупространств.

По аналогии с трехмерным случаем мы называем область в n-мерном пространстве, являющуюся пересечением конечного числа полупространств, выпуклой многогранной областью, а в случае, когда это пересечение является ограниченным множеством, — просто выпуклым многогранником. Здесь слова «ограниченное множество» следует понимать в том смысле, что координаты всех точек рассматриваемой области не превосходят по абсолютной величине некоторой постоянной с:   | x₁ | ≤ c, ..., | х_п | ≤ с для всех точек данной области.

Итак, совокупность точек n-мерного пространства, координаты которых удовлетворяют системе (1.1.3), есть выпуклая многогранная область , получающаяся в результате пересечения всех полупространств, отвечающих неравенствам данной системы.

Отметим еще раз, что если эта  область ограничена, то мы называем ее выпуклым многогранником.

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

       

 

 

 

 

 

 

 

 

2 Однородные и неоднородные системы линейных неравенств

 

2.1 Однородная система линейных неравенств. фундаментальный набор решений

 

   Ранее мы рассмотрели способ нахождения решений системы линейных неравенств. Но некоторые вопросы решить с его помощью нельзя; например, указанный способ не позволяет обозреть множество всех решений данной системы неравенств. Основные трудности связаны с рассмотрением однородных систем. Рассмотрим систему из любого числа неравенств с любым числом неизвестных. Для удобства разобьем изложение на ряд пунктов.

   1. Линейная функция от  п  аргументов.  Общий вид однородного  неравенства с п неизвестными есть

 

a₁x₁+a₂x₂+…+a_nx_n ≥ 0.

 

         Рассмотрим отдельно выражение

a₁x₁+a₂x₂+…+a_nx_n, 

 

стоящее в левой части неравенства: Это выражение называется линейной функцией. Роль аргументов играют п переменных x₁, x₂, …, x_n. Впрочем, можно считать, что функция (1') зависит не от п аргументов, а от одного: этим аргументом является точка

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

 n-мерного пространства.

   Условимся в дальнейшем функцию (1') обозначать кратко L(X):

 

                          L(X)= а₁х₁ + а₂х₂ + ... + а_пх_п,

 

если же задана не одна такая  функция, а несколько, то будем обозначать их L₁(X),  L₂(X) и т. д.

Установим   следующие   два    свойства   линейной функции.

1)                                              L(kX)=kL(X),

где X — любая точка, a k — любое число.

      2)                                   L(X+Y)=L(X) + L(Y),

где X и У — любые две точки.

   Свойство 1 очевидным образом следует из равенства

 

 а₁ (kx₁) + а_г(kx₂) +.... + а_n(kx_n) = k(a₁x₁ +  а₂x₂ +… + а_пх_п).

 

          Докажем теперь свойство 2. Пусть

X =(x₁, х₂, ..., х_п)    и    Y = (y₁, y₂, ..., y_п).

Тогда

 

L (X + У) = a₁(x₁+ y₁) + а₂ (x₂+ y₂) + ... + а_n (x_n+ y_n) =( a₁x₁+ a₂x₂+ ... + а_пх_п) +

+ (a₁y₁ + a₂y₂+ ... + a_ny_n) = L(X) + L(Y).

 

2. Некоторые свойства решений однородной системы линейных неравенств. Пусть дана однородная система m линейных неравенств с п неизвестными:

 

 

         Обозначив левые части неравенств соответственно L₁(X), L₂(X),…, L_m(X), перепишем данную систему в виде