Системы линейных неравенст

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

s1M1+ s2M2,

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

M' (x'1, x'2, …, x'n)   и    M" (x"1, x"2, …, x"n)

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

s'M' + s"M" = (s'x'1 + s"x"1, s'x'2 + s"x"2, …, s'x'n + s"x"n),

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

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

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

                      a1x1+a2x2+…+anxn+b=0,

где хотя бы одно из чисел a1, а2, ..., ап (коэффициентов при неизвестных)  отлично от нуля. При n = 3 уравнение (2) принимает вид a1x1+a2x2+a3x3+b=0 — это есть не что иное, как уравнение плоскости в обычном пространстве (где координаты обозначены x1, х2, х3, а не х, у, z).

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

                     a1x1+a2x2+…+anxn+b ≥ 0,

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

                     a1x1+a2x2+…+anxn+b ≤ 0.

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

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

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

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

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

                    

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

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

                      …………………………

                      xn = sx'n + (1 – s )x''n ,

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

a1(sx'1+(1 – s)x''1)+ a2(sx'2+(1 – s)x''2)+…+ an(sx'n+(1 – s)x''n)+b= s(a1x'1+a2x'2+…+anx'n)+(1 - s)( a1x''1+a2x''2+…+anx''n)+sb+(1 - s)b

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

s[a1x'1+…+anx'n+b] + (1 – s)[a1x''1+…+anx''n+b].

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

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

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

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

| x1 | ≤ c, ..., | хп | ≤ с для всех точек данной области.

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

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

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

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

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

набор решений

 

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

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

a1x1+a2x2+…+anxn ≥ 0.

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

a1x1+a2x2+…+anxn, 

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

X= (x1, x2, …, xn)

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

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

                          L(X)= а1х1 + а2х2 + ... + апхп;

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

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

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

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

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

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

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

a1(kx1) + аг(kx2) +.... + аn(kxn) = k(a1x1 +  а2x2 +… + апхп).

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

X =(x1, х2, ..., хп)    и    Y = (y1, y2, ..., yп).

Тогда

L (X + У) = a1(x1+ y1) + а2 (x2+ y2) + ... + аn (xn+ yn) =( a1x1+ a2x2+ ... + апхп) +

+ (a1y1 + a2y2+ ... + anyn) = L(X) + L(Y).

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

 

 

Обозначив левые части неравенств соответственно L1(X), L2(X),…, Lm(X), перепишем данную систему в виде

где

     X = (x1, x2, ..., xn).

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

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

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

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

  Li(kX) = kLi(X) ≥ 0

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

                              Li(X + Y) = Lt(X) + Li(Y) ≥ 0

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

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

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

                               k1X1 + k2X2 + ... + kpXp,

где k1, k2, ..., kp — неотрицательные числа, тоже является решением системы (2).

Действительно, каждая из точек k1X1 + k2X2 + ... + kpXp в силу предложения 1 является решением системы (2), но тогда и сумма этих точек в силу предложения 2 будет решением системы (2).

Условимся называть любую точку вида (3), где 
k1, k2, ..., kp — неотрицательные числа, неотрицательной комбинацией точек X1, X2,..., Xp. Тогда указанное выше следствие будет допускать такую формулировку.

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

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

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

                          X = k1X1 + k2X2 + ... + kpXp, 

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

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

                           

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

 

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

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

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

xn = — ().

Полагая = l, = 0, ..., = 0, найдем из последнего уравнения xn = - .   Таким образом, точка

X1 = (1, 0, …, 0, - ),

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

X2 = (0, 1, …, 0, - ),

………………………

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

Пусть теперь

                              Х = ()

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

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

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

 X1 + X2+ ... + = (1, 0, …, 0, )+ (0, 1, …, 0, ) + …           + (0, 0, …, 1, ),

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

Х =Х1 + Х2 + ... + .

Добавим теперь к построенным ранее точкам X1, X2,..., Xn-1, Xn  еще одну:

                                  Xn = (X1+X2+…+Xn-1).

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

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

Х =() Х1 + ()Х2 + ... +()Хп-1 + Хп,

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

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

                              Х1, Х2,…, Xn-1, Xn, Хп+1

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

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

X = X' — аХп+1

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

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

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

Х' = Х + аХn+1

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

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

                       - 2 х1 - 4х2 + х3 ≥ 0

с тремя неизвестными х1, х2, х3.

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

- 2 х1 - 4х2 + х3 = 0

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