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

ФИНАНСОВАЯ АКАДЕМИЯПРИ ПРАВИТЕЛЬСТВЕ РФ

Кафедра математики ифинансовых приложений

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

на тему:

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

Выполнил студент группы МЭК 1-2

Чанкин Пётр Алексеевич

Научный руководитель:

Профессор Александр Самуилович Солодовников

Москва 2002г

Оглавление

/>/>/>Вступление… 2

Графический метод… 3

Симплекс-метод… 6

Метод искусственного базиса… 8

Принцип двойственности… 10

Список использованной литературы… 12

/>Вступление

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

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

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

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

/>Графический метод

           

Графический метод заключается в построении множествадопустимых решений ЗЛП, и нахождении в данном множестве точки, соответствующейmax/min целевой функции.

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

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

/>

           

/>

На первом этапе надо построить область допустимых решений. Для данного примера удобнее всего выбрать X2 за абсциссу, а X1 за ординату и записать неравенства в следующем виде:

/>

Так как /> и /> графикии область допустимых решении находятся в первой четверти.

Для того чтобы найти граничные точки решаем уравнения(1)=(2), (1)=(3) и (2)=(3).

/>

           

Как видно из иллюстрации многогранник ABCDE образует область допустимых решений.

Если область допустимых решений не является замкнутой, толибо max(f)=+ ∞, либо min(f)= -∞.

Теперь можно перейти к непосредственному нахождению максимума функции f.

Поочерёдно подставляя координаты вершин многогранника вфункцию f и сравнивать значения, находим что

f(C)=f(4;1)=19 – максимум функции.

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

В таком случае удобнее рассмотреть линию уровня вида f=a. При монотонном увеличении числа a от -∞ до +∞ прямые f=a смещаютсяпо вектору нормали[1].Если при таком перемещении линии уровня существует некоторая точка X – первая общая точка областидопустимых решений (многогранник ABCDE) и линии уровня,то f(X)- минимум f на множестве ABCDE.Если X- последняя точка пересечения линии уровня имножества ABCDE то f(X)- максимум на множестве допустимых решений. Если приа→-∞ прямая f=a пересекает множество допустимых решений, то min(f)= -∞. Если это происходитпри а→+∞, то

max(f)=+ ∞.

/>

В нашем примере прямая f=a пересевает область ABCDE в точке С(4;1). Поскольку этопоследняя точка пересечения, max(f)=f(C)=f(4;1)=19.

/>/>/>/>/>Симплекс-метод

Реальные задачи линейного программирования содержат оченьбольшое число ограничений и неизвестных и выполняются на ЭВМ. Симплекс-метод –наиболее общий алгоритм, использующийся для решения таких задач. Суть методазаключается в том, что после некоторого числа специальных симплекс-преобразований ЗЛП, приведенная к специальному виду, разрешается. Для того,чтобы продемонстрировать симплекс-метод в действии решим, с попутнымикомментариями следующую задачу:

/>

Для того, чтобы приступить к решению ЗЛП симплекс методом, надо привести ЗЛП к специальному виду и заполнить симплекс таблицу.

Система (4) – естественные ограничения и в таблицу невписываются. Уравнения (1), (2), (3) образуют область допустимых решений.Выражение (5) – целевая функция. Свободные члены в системе ограничений и областидопустимых решений должны быть неотрицательны.

В данном примере X3, X4, X5 – базисные неизвестные. Ихнадо выразить через свободные неизвестные и произвести их замену в целевойфункции.

/>

 

Теперь можно приступить к заполнению симплекс-таблицы:

Б. X1 X2 X3 X4 X5 C X3 -1 1 1 1 X4 1 -1 1 1 X5 1 1 1 2 f -6 7 3

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

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

/> 

Б X1 X2 X3 X4 X5 C

/>X3

-1 1 1 1 X4 1 -1 1 1 X5 1 1 1 2 f -6 7 3

Для этого выбираем столбец с отрицательным коэффициентом впоследней строке[2](столбец 3) и составляем для положительных элементов данного столбца отношениясвободный  член/коэффициент (1/1; 2/1)[3].Из данных отношений выбираем наименьшее и помечаем соответствующую строку[4].

Нами выбран элемент в ячейке (3;3). Теперь с помощью методаГаусса обнуляем другие коэффициенты в данном столбце, это приводит к сменебазиса и мы на один шаг приближаемся к оптимальному решению.

Б X1 X2 X3 X4 X5 C X3 1 1 2 X1 1 -1 1 1 X5 2 -1 1 1 f 1 6 9

 

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

/> 

/>/>/>/>/>Методискусственного базиса

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

Суть метода довольно проста:

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

Рассмотрим следующий пример:

/>

  min(f)-?

В первом уравнении нет базисных неизвестных. Введём искусственную базисную неизвестную Y1 и заполним первую симплекс-таблицу

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

F=Y1→min

Выражая базисную неизвестную Y1через свободные получаем:

/>F+4X1+X2=4 →min

Б X1 X2 X3 X4 Y1 С

/>Y1

4 1 1 4 X4 11 3 -5 -1 12 F 4 1 4

Выбираем элемент в ячейке (3;2) и делаем шаг.

Б X1 X2 X3 X4 Y1 С X2 4 1 1 4 X4 -1 -5 -1 -3 F -1

min(f)=0, всекоэффициенты в последней строке меньше или равны нулю, следовательно мы перешлик новому естественному базису. Теперь можно решать основную задачу.

/>/>/>/>/>Принципдвойственности

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

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

/>

max(f)-?                                                       min(φ)-?                         

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

Введя в рассмотрение следующие элементы:

/>

Эту связь можно обозначить следующим образом:

/>

max(f)-?                                                       min(φ)-? 

В двойственной задаче всего 2 переменных. Её можно легкорешить графическим методом и, используя вторую теорему двойственности, найтирешение исходной.

Пропустим процесс решения двойственной ЗЛП, записав толькорезультаты:

Y1=2      Y2=4          min(φ)=150

Т.к max(f)=min(φ), решение исходной задачиуже известно. Остаётся только найти значения X1, X2, X3, при которых это значениедостигается. Здесь мы применим вторую теорему двойственности, котораяустанавливает следующее соответствие:

/>

В нашем примере получается следующая вполне тривиальнаясистема линейных уравнений:

/>

Решение данной системы легко находится методом Гаусса иокончательный ответ таков:

Функция f достигаетмаксимума при X1=0, X2­=5,X3=10 и max(f)=150

/>/>/>/>/>Списокиспользованной литературыУчебник: «Математика в экономике»; А.С. Солодовников, В.А. Бабайцев, А.В. Браилов: Финансы и статистика 1999г. Сборник задач по курсу математики; под редакцией А.С. Солодовникова и А.В. Браилова; ФА 2001г. «Линейные неравенства»; С.Н. Черников; Наука 1968 «Краткий очерк развития математики»; Д.Я. Стройк; Наука 1984.