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

курсовая работа

3. Существование и способ построения фундаментального набора решений;

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

ГЛАВА I. ИСТОРИЯ ВОЗНИКНОВЕНИЯ

Неравенства первой степени, или, как принято их называть, линейные неравенства, - это неравенства вида

ax+by+c?0

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

(1)

где и - заданные действительные числа, хk - неизвестные, а j пробегает то или иное множество значений.

Теория систем линейных неравенств возникла под влиянием работ М. В. Остроградского по аналитической механике, работ П. Л. Чебышева по теории приближения функций и работ Г. Ф. Вороного по теории чисел. Именно, М.В. Остроградский [5] показал, что исследование равновесия системы материальных точек с освобождающими связями сводится к изучению системы вида (1). Работы М. В. Остроградского были затем продолжены специалистами по аналитической механике, которые установили ряд основных свойств систем линейных неравенств.

Далее, задача о наилучшем приближении функции, заданной таблицей, посредством многочленов вида

Где -- заданные функции, тоже сводится к исследованию конечных систем вида (1). Если же допускать, что индекс j может пробегать континуум различных значений, то и классическая задача о наилучшем приближений функции, заданной на отрезке, редуцируется к изучению системы (1). В этом направлении идеи Чебышева развивались Кирхбергером [19, 20], Е.Я. Ремезом [6], В.К. Ивановым [4] и др. Наконец, Г.Ф. Вороной пришёл к задачам, связанным с системами линейных неравенств, исследуя свойства положительных квадратичных форм с целочисленными переменными, и получил в теории систем линейных неравенств весьма глубокие результаты ([2], [3]).

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

Теория систем линейных неравенств довольно резко делится на два направления. Одно направление, которое можно назвать геометрическим, ведёт своё начало от Остроградского и Вороного и посвящено изучению геометрических свойств того выпуклого многогранника n-мерного пространства, который представляет собою решение системы (1). Здесь рассматриваются вопросы совместности системы, зависимости между составляющими её неравенствами, вопросы геометрического строения решения: размерность решения, его ограниченность или неограниченность, расположение его вершин, рёбер и граней произвольной размерности. Результаты, относящиеся к этому направлению, тесно соприкасаются с теорией систем линейных уравнений, с теорией выпуклых тел в n-мерном пространстве и с некоторыми вопросами функционального анализа ([1, 8]).

Другое направление теории систем линейных неравенств можно охарактеризовать как экстремальное. Оно ведёт своё начало от идей П. Л. Чебышева и посвящено рассмотрению различного рода экстремальных задач, относящихся к системам (1). Это направление соприкасается с общей теорией приближения функций, задачами минимакса, теорией моментов и т. д. (см. [4, 6]).

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

где неотрицательны. В действительности вопрос о независимости неравенств системы рассматривался уже Г. Минковским [21] в 1896 г. (правда, для простейших случаев), а метод параметризации -- Г. Фаркасом в 1901 г.

Геометрически каждое неравенство системы (1), в левой части которого встречается хотя бы один отличный от нуля коэффициент, определяет одно из двух полупространств n-мерного евклидова пространства Rn, граничная плоскость которых определяется граничным уравнением содержащимся в выбранном неравенстве. Если все коэффициенты при неизвестных в некотором неравенстве системы (1) равны нулю, то множество его решений либо пусто, либо геометрически представляется всем пространством Rn.

Считая пространство Rn и его пустое подмножество взаимно дополнительными (несобственными) полупространствами в Rn, можно говорить без всяких исключений, что каждое неравенство системы (1) определяет некоторое полупространство в Rn (собственное или несобственное), причём в случае несобственного полупространства множество его граничных точек, очевидно, пусто; поэтому под граничной плоскостью несобственного полупространства понимается просто пустое подмножество.

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

Приведённые здесь простые геометрические соображения позволяют каждую задачу о системе (1) формулировать как геометрическую задачу о её многограннике и, наоборот, каждую задачу о многограннике, определяемом пересечением полупространств пространства Rn, рассматривать как задачу о системе линейных неравенств, определяющих эти полупространства.

ГЛАВА II. ОБЛАСТЬ РЕШЕНИЯ СИСТЕМЫ НЕРАВЕНСТВ С ДВУМЯ НЕИЗВЕСТНЫМИ

Решение любой системы линейных неравенств сводится к решению ряда систем линейных уравнений.

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

(1)

Окажется целесообразным наряду с ней рассмотреть соответствующую систему однородных неравенств

(2)

А также соответствующую систему линейных уравнений

(3)

Область решений системы (1) на координатной плоскости xOyобозначим через , системы (2) - через , системы (3) - через . Очевидно, .

Рассмотрим систему (3). Она имеет очевидное решение x=0, y=0. Это решение называется нулевым. Для исследования системы (1) важно знать, имеет ли система (3) также и ненулевые решения. Система линейных неравенств называется нормальной, если соответствующая система линейных однородных уравнений имеет только нулевое решение.

Совместная система неравенств нормальна тогда и только тогда, когда область ее решений не содержит ни одной прямой.

2.1 Решение системы линейных неравенств путем последовательного уменьшения числа неизвестных

Из курса алгебры известен метод решения системы линейных уравнений путем последовательного уменьшения числа неизвестных. Для системы, содержащих три неизвестных x, y, z сущность этого метода можно описать следующим образом.

Из каждого уравнения выражаем z через x и y. Затем, полученные выражения приравниваем друг к другу. Получаем новую систему - с двумя неизвестными.

То же самое можно проделать и с системой линейных неравенств. Решение системы неравенств с n неизвестными x1, x2,…,xn сводится таким образом к решению системы неравенств с n-1 неизвестными. Затем система может быть сведена к системе n-2 и т.д., пока не придем к системе неравенств с одним неизвестным x1. А решение системы неравенств с одним неизвестным - задача элементарная. Таким путем мы получаем возможность найти любое решение исходной системы неравенств.

Пусть дана система линейных неравенств с n неизвестными x1, x2,…,xn - в дальнейшем будем называть ее системой S для удобства. Рассмотрим любое из неравенств системы S. Оно имеет вид:

Очень полезным оказывается связать неравенство с другим неравенством, в котором число неизвестных на единицу меньше.

Если аn=0, то неравенство оставляем без изменений. Если аn<0, то переносим член anxn переносим в правую часть и разделим обе части неравенства на аn. Получим неравенство вида:

В случае, если аn>0, то переносим в правую часть неравенства все слагаемые, кроме anxn, и разделим неравенство на аn. Получим неравенство:

Итак, умножив каждое из неравенств исходной системы на подходящее положительное число, получим равносильную ей систему:

(Т)

где P1,…,Pp, Q1,…,Qq, R1,…Rr суть выражения . Систему Т можно записать короче:

где б - любое из чисел 1,2,…,p; в - любое из чисел 1,2,…,q; г - любое из чисел 1,2,…,r.

Рассмотрим наряду с системой Т систему:

(S)

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

Следствия из теоремы:

10: система S линейных неравенств совместна тогда, и только тогда, когда совместна сопутствующая ей система S.

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

Итак, для произвольной системы S мы построили сопутствующую систему S. Но для системы S можно так же построить сопутствующую систему S. Продолжая, мы придем к системе неравенств S(n-1), состоящую из неравенств с одним неизвестным x1. Из указанного выше вытекает, что система S совместна тогда, и только тогда, когда совместна система S(n-1).

Допустим, что система совместна. Тогда возникает задача - решить систему. Система решена, если:

1.Найдены все допустимые значения неизвестного x1 из системы S(n-1). Набор значений первых k неизвестных называется допустимым, если его можно продолжить до решения исходной системы S, т.е. существуют такие числа , что набор является решением системы S;

2.Для любого конкретного допустимого значения найдены все совместные с ним значения неизвестного ;

3.Для любого конкретного допустимого набора , найдены все совместные с ним значения неизвестного .

ГЛАВА III. ОДНОРОДНЫЕ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ. ФУНДАМЕНТАЛЬНЫЙ НАБОР РЕШЕНИЙ

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

Рассмотрим систему из любого числа линейных неравенств, с любым числом неизвестных.

Общий вид однородного неравенства имеет вид:

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

Это выражение называется линейной функцией. Роль аргументов играют n переменных . Но можно считать, что функция зависит не от n переменных, а от одного: этим аргументом является точка X=(). Обозначим L(X)=

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

1. L(kX) = kL(X), где X - любая точка, k - любое число;

2. L(X+Y) = L(X)+L(Y);

Теперь пусть дана однородная система m линейных неравенств c n неизвестными.

(3)

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

(4)

Установим следующие два свойства системы линейных неравенств:

1. Если X есть решение системы (4) и k - любое неотрицательное число, то точка kX есть снова решение системы (4);

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

Из данных свойств непосредственно вытекает следствие:

10: если некоторые точки X1, X2,…, Xn являются решением системы (4), то и любая точка вида

(5)

где k1,…,kn - неотрицательные числа, тоже является решением системы (4).

Условимся называть любую точку вида (5) неотрицательной комбинацией точек X1, X2,…, Xn. Тогда указанное выше следствие будет допускать такую формулировку:

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

Введем определение:

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

X= (6)

где k1,…,kn - неотрицательные числа.

В этом случае формула (5) дает обозрение всех решений системы. Отсюда ясно, что нахождение фундаментальной системы решений является первостепенной задачей при исследовании системы неравенств.

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

Построим фундаментальный набор для системы

Для этой цели рассмотрим наряду с этим неравенством уравнение

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

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

2. Если X и Y - два решения уравнения (8), то X+Y есть снова решение уравнения (8).

Набор точек X1, X2,…,Xn, Xn+1 является фундаментальным набором решений для неравенства (7).

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

(9)

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

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

X1=(1,0,2)

X2=(0,1,4)

Далее в качестве X3 берем точку:

X3=-( X1+ X2)=(-1,-1,-6)

И в качестве X4 принимаем одно из решений уравнения:

-2x1-4x2+x3=1

Например, X4=(0,0,1).

Точки X1, X2, X3, X4 образуют фундаментальный набор решений для неравенства (9). Общее решение имеет вид:

X=k1X1+k2X2+k3X3+k4X4=k1(1,0,2)+k2(0,1,4)+k3(-1,-1,-6)+k4(0,0,1).

или:

x1=k1-k3

x2=k2-k3

x3=2k1+4k2-6k3+k4

где k1, k2, k3, k4 - произвольные неотрицательные числа.

Можно перестроить фундаментальный набор решений при добавлении к системе еще одного неравенства. Рассмотрим такую задачу.

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

(10)

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

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

L(X) ? 0 (11)

Решения системы (10) - это все неотрицательные комбинации точек . Среди этих комбинаций нужно выбрать такие, которые удовлетворяли бы неравенству (11) и, более того, составили бы фундаментальный набор решений для системы (10), (11).

По отношению к функции L(X) все точки можно разбить на три группы: точки, для которых L(X)>0, точки, для которых L(X)<0, точки, для которых L(X) = 0.

Точки первой группы обозначим:

(12)

Точки второй группы:

(13)

Точки третьей группы:

(14)

Таким образом, эти точки то же самое, что и точки , но только расположенные, может быть, в другом порядке. Разумеется, все точки (12), (14)

удовлетворяют неравенству (11). Что же касается точек (13), то ни одна из них не является решением неравенства (11). Однако из каждой пары можно образовать неотрицательную комбинацию

(15)

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

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

Теорема: точки (12) - (14) образуют фундаментальный набор решений для системы (10), (11).

Делись добром ;)