Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

СТЕРЛИТАМАКСКАЯ ГОСУДАРСТВЕННАЯ ПЕДАГОГИЧЕСКАЯ АКАДЕМИЯ ИМЕНИ ЗАЙНАБ БИИШЕВОЙ

`Кафедра алгебры и геометрии

и методики преподавания математики

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

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

Садыкова Ляйсан Фаиловна

Стерлитамак 2011

ОГЛАВЛЕНИЕ

• ВВЕДЕНИЕ
• ГЛАВА I. ИСТОРИЯ ВОЗНИКНОВЕНИЯ
• ГЛАВА II. ОБЛАСТЬ РЕШЕНИЯ СИСТЕМЫ НЕРАВЕНСТВ С ДВУМЯ НЕИЗВЕСТНЫМИ
• 2.1 Решение системы линейных неравенств путем последовательного уменьшения числа неизвестных
• ГЛАВА III. ОДНОРОДНЫЕ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ. ФУНДАМЕНТАЛЬНЫЙ НАБОР РЕШЕНИЙ
• 3.1 Построение фундаментального набора решений для системы, состоящей из одного неравенства
• 3.2 Существование и способ построения фундаментального набора решений
• ГЛАВА IV. РЕШЕНИЕ НЕОДНОРОДНОЙ СИСТЕМЫ НЕРАВЕНСТВА
• ЗАКЛЮЧЕНИЕ
• СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

Актуальность проблемы:

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

Цель работы:

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

Задачи исследования:

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

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

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-мерного евклидова пространства Rⁿ, граничная плоскость которых определяется граничным уравнением содержащимся в выбранном неравенстве. Если все коэффициенты при неизвестных в некотором неравенстве системы (1) равны нулю, то множество его решений либо пусто, либо геометрически представляется всем пространством Rⁿ.

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

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

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

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

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

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

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

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

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

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

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

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

(Т)

где P₁,…,P_p, Q₁,…,Q_q, R₁,…R_r суть выражения . Систему Т можно записать короче:

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

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

(S')

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

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

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

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

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

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

1.Найдены все допустимые значения неизвестного x₁ из системы 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)

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

(4)

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

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

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

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

1⁰: если некоторые точки X₁, X₂,…, X_n являются решением системы (4), то и любая точка вида

(5)

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

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

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

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

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

X= (6)

где k₁,…,k_n - неотрицательные числа.

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

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

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

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

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

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

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

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

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

(9)

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

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

X₁=(1,0,2)

X₂=(0,1,4)

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

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

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

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

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

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

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

или:

x₁=k₁-k₃

x₂=k₂-k₃

x₃=2k₁+4k₂-6k₃+k₄

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

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

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

(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).

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

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

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

Рассмотрим пример. Для системы:

(16)

Требуется найти все неотрицательные решения, т.е. все решения, удовлетворяющие условиям:

(17)

Нетрудно видеть, что для системы (17) фундаментальным набором решений будет являться набор из точек:

Присоединим к системе(17) первое неравенство (16) и для полученной таким образом системы получим фундаментальный набор решений. Для удобства вычислений составим таблицу:

					L1(X)
X1	1	0	0	0	-3
X2	0	1	0	0	-4
X3	0	0	1	0	5
X4	0	0	0	1	-6

В каждой строке таблицы указана одна из фундаментальных точек системы (17), а также значение точки L₁(X) для этой точки. Находим точки типа

.

Точку X₃ обозначим Y₃. Точки Y₃, Y₁, Y₂, Y₄ образуют фундаментальный набор решений для системы, состоящей из (17) и первого неравенства (16).

Присоединяем к этой системе второе неравенство из (16) и получаем:

					L2(Y)
Y1	0	0	1	0	-3
Y2	5	0	3	0	1
Y3	0	5	4	0	3
Y4	0	0	6	5	-13

Находим точки типа :

Все эти точки образуют фундаментальный набор решений систем (16), (17).

Общее решение имеет вид:

ГЛАВА IV. РЕШЕНИЕ НЕОДНОРОДНОЙ СИСТЕМЫ НЕРАВЕНСТВ

Теперь не составляет труда решить аналогичную задачу для произвольной, т.е. неоднородной системы неравенств.

Пусть

(1)

- произвольная система линейных неравенств. Рассмотрим наряду с ней однородную систему неравенств:

(2)

Между решениями (1) и (2) имеется определенная связь. А именно, если решение - какое -либо решение системы (2),причем t>0, то числа

(3)

будут составлять решение системы (1).

В самом деле, рассмотрим, например,первое из неравенств (2). Оно выполняется для чисел , т.е.



Разделив обе части неравенства на t получим:

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

Нетрудно видеть, что любое решение системы (1) может быть получено выше указанным способом. Действительно, если - какое - либо решение системы (1), то числа удовлетворяют системе (2) и при этом справедливы равенства (3).

Итак, чтобы отыскать все решения системы (1), следует найти все решения системы (2), и преобразовать каждое из них по формулам (3).

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

(4)

Добавляя к этой системе неравенство t?0, получаем систему (16), (17) (пункт 3.2.) с той лишь разницей, что вместо x₄ написано t. Множество решений этой системы описывается формулами:



где k₁,…,k_n - неотрицательные числа.

Теперь находим решение системы (4) по формулам:

(5)

ЗАКЛЮЧЕНИЕ

В данной работе описано построение и решение фундаментального набора решений для систем, состоящих из одного или нескольких неравенств. Показан один из основных методов решения систем линейных неравенств - последовательное уменьшение числа неизвестных. Доказано существование фундаментального набора решений систем линейных неравенств и показан способ его построения. Рассмотрены системы однородных и произвольных линейных неравенств.

Таким образом, в данной курсовой работе развита теория системы линейных неравенств.

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ:

1. А.Д. Александров, Выпуклые многогранники, М.--Л., Гостехиздат, 1950;

2. Н.Н. Астафьев Линейные неравенства и выпуклость. - М.: Наука,

1982. - 152 c.

3. В.И. Зоркальцев, М.А. Киселева СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ Учебное пособие. Иркутск 2007

4. А.С. Солодовников. Системы линейных неравенств. М.: Наука, 1977 г.

5. Г. X арди, Д. Литтльву д и Г. Полна, Неравенства, М., ИИЛ, 1948.

6. С.Н. Черников, Обобщение теоремы Кронекера- Капелли о системе линейных уравнений, Матем. сб., 15 (57), 3 (1944), 437--448.

7. А.Г. Школьник, Линейные неравенства, Учёные зап. физ.-мат. фак. МГТШ, 16 (1951), 127--174.

8. А.Г. Школьник, О системах линейных неравенств, Учёные зап. физ.

мат. фак. (Московский городской педагогический институт) 1; Труды кафедры математики, вып. 1 (1940), 235--250.

Размещено на Allbest.ru