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

Министерство образования  Республики Беларусь

УО «Белорусский государственный  экономический университет»

 

 

Кафедра Прикладной математики и экономической кибернетики

 

 

 

 

КУРСОВАЯ РАБОТА

      по дисциплине: Линейная алгебра и аналитическая геометрия

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

 

 

 

 

 

Студентка

ФМ, 1-й курс, ДКК-1                                                              А.В.Жигар

 

Руководитель

ассистент                                                                                 О.Д.Юферева

 

 

 

 

 

                                       

 

                                              МИНСК 2012

реферат

 

Курсовая  работа: 33 с., 11 рис., 3 табл., 4 источника.

            выпуклое множество, n - мерное пространство, нормальная система неравенств, однородная система неравенств, полупространства, фундаментальный набор решений

 

Объект исследования – системы линейных неравенств.

Предмет исследования – решения систем линейных неравенств и их применение в экономике.

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

Методы исследования: экономико-математические, описания и моделирования, классификации.

Исследования  и разработки: изучены методы нахождения областей решений систем линейных неравенств, на примере экономической задачи показано их применение на практике.

Область возможного практического применения: все экономические задачи в которых возможно применение изученных методов.

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

Автор работы подтверждает, что приведенный  в ней расчётно-аналитический  материал объективно отражает состояние  исследуемого процесса, а все заимствованные из литературных и других источников теоретические, методологические и методические положения и концепции сопровождаются ссылками на их авторов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                                                                         ___________

содержание

 

введение……………………………………………………………………………..4

 

1 Области решений систем линейных неравенств с различным количеством неизвестных ………………………………………………….……………………5

1.1 Область решений системы неравенств с двумя неизвестными………...5

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

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

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

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

2.2 Неоднородная система линейных неравенств. Фундаментальный набор решений…………………………………………………………………………….27

3 Применение линейных неравенств в экономике

заключение………………………………………………………………………..32

список использованных источников……………………………………….33

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                     

введение

 

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

 

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

 

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

 

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

 

     Основным материалом для курсовой работы послужили учебное пособие «Системы линейных неравенств» Солодовникова А. С., где подробно изложены все свойства систем линейных неравенств, а также методическое пособие «Экономические задачи, приводящиеся к системам линейных уравнений и неравенств» и «Сборник задач и упражнений по высшей математике» Кузнецова А. В., Кузнецовой Д. С., где в доступной форме приведены примеры решений экономических задач с помощью линейных неравенств.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Области решений систем линейных неравенств с различным количеством неизвестных

 

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

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

1. Необходимые леммы. Пусть дана система неравенств

 

 

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

 

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

 

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

Лемма 1. Имеет место включение

 

                                                  ₀,

 

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

       Доказательство. Пусть А — произвольная точка из , В — произвольная точка из ₀. Тогда справедливы неравенства

 

                            a₁x_A + b₁y_A + c₁ ≥ 0,                a₁x_B + b₁y_B ≥ 0,

                            a₂x_A + b₂y_A + c₂≥ 0,        и      a₂x_B + b₂y_B ≥ 0,

                            ……………………                ………………..

                            a_mx_A + b_my_A + c_m ≥ 0,              a_mx_B + b_my_B  ≥ 0.

        Складывая каждое неравенство, написанное слева, с соответствующим неравенством, написанным справа, получим

 

a₁(x_A+x_B)+b₁(y_A+y_B)+c₁≥0,

a₂(x_A+x_B)+b₂(y_A+y_B)+c₂≥0,

………………………………

a_m(x_A+x_B)+b_m(y_A+y_B)+c_m≥0.

 

          Эти неравенства означают, что пара чисел  x_A+ х_{B  ,} y_A + y_B — координат

 точки А + В — является решением исходной системы (1), т. е. что A+В .

Лемма доказана.

Лемма 2. 1) Если некоторый луч с началом в точке А целиком принадлежит множеству и Р — произвольная точка этого луча, то Р — А ₀.

2) Если некоторая прямая целиком принадлежит множеству и А, Р — две произвольные точки этой прямой, то Р — А.

Доказательство 1). Обозначим  точку Р — А через В. Рассматриваемый нами луч состоит из точек следующего вида:

                                                          А + sB,                                                    (4)

где s — произвольное неотрицательное число (рис. 1).

 

 

 

 

 

 

    

 

 

 

 Любая из этих точек является по условию решением системы (1), т. е.

 

 

         Рассмотрим, например, первое из этих неравенств. Оно может быть записано в виде

(а₁х_А + b₁ y_A+ c₁) + s(а₁х_B + b₁y_B)≥ 0.

 

         Поскольку это неравенство справедливо при любом s ≥ 0, то коэффициент при s, как нетрудно видеть, должен быть неотрицательным числом:

 

^{a₁х_B + b₁у_B ≥ 0.}

 

        Аналогично из рассмотрения остальных неравенств (5) можно получить

 

а₂х_B +y₂у_B ≥0,

………………

a_mх_B +y_mу_B ≥0,

откуда видно, что точка В принадлежит множеству ₀.

         Доказательство 2) проводится аналогично. Рассматриваемая прямая состоит из точек вида (4), где s — произвольное число. Поэтому неравенства (5) справедливы при любом значении s. Отсюда вытекает, что в каждом из этих неравенств суммарный коэффициент при s должен равняться нулю, т. е.

 

                      a₁х_B +b₁y_B = 0,

                      a₂х_B +b₂y_B = 0,

                      ………………

                       a_mх_B +b_my_B = 0.

 

          Следовательно, В . Лемма доказана.

        Леммы 1 и 2 справедливы для систем с любым числом неизвестных.

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

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

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

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

Действительно, если система нормальна, т. е. множество содержит только начало координат, то область не содержит прямых — это сразу же следует из второго утверждения леммы 2. Если система не является нормальной, то множество содержит по крайней мере одну точку В, отличную от начала координат. Разумеется, все точки вида kB, где k — любое число, также принадлежат . Но в таком случае, какова бы ни была точка Р (а такая точка обязательно найдется, ибо система совместна и, следовательно, область не пуста), множество всех точек вида Р + kB (где k — любое число) по лемме 1 принадлежит . Указанное множество, как мы знаем, есть прямая линия. Значит, в случае, когда система не нормальна, область содержит прямую. Этим полностью доказано подчеркнутое выше предложение.

         Изучим область решений системы (1), предполагая, что эта система совместна (область не пуста) и нормальна.

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

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

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

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

a_ix+b_ly+c₁ = 0     (i=1, 2, … , m).

 

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

Условимся называть правильной любую подсистему из двух уравнений системы

 

 

при условии, что эта подсистема имеет единственное решение (х,у).

           Из данной выше характеристики вершины вытекает теперь следующий способ нахождения вершин области .

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

            Поскольку число правильных подсистем не превосходит — числа сочетаний из m по 2, — то и вершин области не может быть больше. Итак, число вершин конечно.

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

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

 

                                                     

 

            Решая подсистемы

 

                        

 

           (все они оказываются правильными), находим три точки:

 

(0, -1),    (1, -2),    (2, 0),

 

из которых только вторая и третья удовлетворяют всем заданным неравенствам. Значит, вершинами области являются точки A₁(1, -2) и A₂ (2, 0).