Выдержка из текста работы
ФИНАНСОВАЯ АКАДЕМИЯПРИ ПРАВИТЕЛЬСТВЕ РФКафедраматематики и финансовых приложенийКурсовая работана тему Методырешения систем линейных неравенств Выполнил студент группы МЭК 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 8734 , либо min f — 8734 . Теперь можно перейти к непосредственному нахождению максимума функции f. Поочер дно подставляякоординаты вершин многогранника в функцию f и сравнивать значения, находим чтоf C f 4 1 19 максимумфункции. Такой подход вполневыгоден при малом количестве вершин.
Но данная процедура может затянуться есливершин довольно много. В таком случае удобнеерассмотреть линию уровня вида f a. При монотонном увеличении числа a от — 8734 до 8734 прямые f a смещаются по векторунормали 1 .Если при таком перемещении линии уровня существует некоторая точка X первая общая точка областидопустимых решений многогранник ABCDE и линии уровня, то f X — минимум f на множестве ABCDE. Если X- последняя точка пересечения линии уровня имножества ABCDE то f X — максимум на множестведопустимых решений.
Если при а 8594 — 8734 прямая f a пересекает множество допустимых решений, то min f — 8734 . Если этопроисходит при а 8594 8734 , то max f 8734 .В нашем примере прямая f a пересевает область ABCDE в точке С 4 1 . Поскольку это последняя точкапересечения, max f f C f 19.Симплекс-методРеальные задачи линейногопрограммирования содержат очень большое число ограничений и неизвестных ивыполняются на ЭВМ. Симплекс-метод наиболее общий алгоритм, использующийсядля решения таких задач.
Суть метода заключается в том, что после некоторогочисла специальных симплекс- преобразований ЗЛП, приведенная к специальномувиду, разрешается. Для того, чтобы продемонстрировать симплекс-метод в действиирешим, с попутными комментариями следующую задачу Для того, чтобы приступить к решению ЗЛП симплекс методом, надо привести ЗЛП к специальному виду и заполнить симплекс таблицу.
Система 4 естественные ограничения и в таблицу не вписываются. Уравнения 1 , 2 , 3 образуют область допустимых решений. Выражение 5 целевая функция. Свободныечлены в системе ограничений и области допустимых решений должны бытьнеотрицательны. В данном примере X3, X4, X5 базисные неизвестные. Их надо выразить через свободные неизвестные и произвести их замену в целевойфункции. Теперь можно приступить кзаполнению симплекс-таблицы Б. X1 X2 X3 X4 X5 C X3 0 -1 1 1 0 1 X4 0 1 -1 0 1 1 X5 1 1 1 0 0 2 f 0 -3 В первом столбце даннойтаблицы обозначены базисные неизвестные, в последнем значения свободныхнеизвестных, в остальных коэффициенты при неизвестных.
Для того чтобы найти максимум функции f надо с помощью преобразований методом Гаусса сделать так, чтобы все коэффициенты при неизвестных в последней строке были неотрицательными для нахождения минимума, сделать так, чтобы все коэффициенты были меньше или равны нулю. Б X1 X2 X3 X4 X5 C X3 -1 1 1 0 0 1 X4 1 -1 0 1 0 1 X5 1 1 0 0 1 2 f -6 7 0 0 0 3 Для этого выбираемстолбец с отрицательным коэффициентом в последней строке 2 столбец 3 и составляем для положительных элементов данного столбца отношениясвободный член коэффициент 1 1 2 1 3 .Из данных отношений выбираем наименьшее и помечаем соответствующую строку 4 .Нами выбран элемент вячейке 3 3 . Теперь с помощью метода Гаусса обнуляем другие коэффициенты в данномстолбце, это приводит к смене базиса и мы на один шаг приближаемся коптимальному решению.
Б X1 X2 X3 X4 X5 C X3 0 0 1 1 0 2 X1 1 -1 0 1 0 1 X5 0 2 0 -1 1 1 f 0 1 0 6 0 9 Как видно из таблицытеперь все коэффициенты в последней строке больше либо равны нулю. Этоозначает, что нами найдено оптимальное значение.
Свободные неизвестные равнынулю, значению базисных неизвестных и максимуму функции f соответствует значениясвободных неизвестных.
Методискусственного базиса
Если после подготовки ЗЛПк специальному виду для решения симплекс методом, не в каждой строке системыограничений есть базисная переменная входящая в данную строку с коэффициентом1, а в остальные строки с коэффициентом 0 , то для решения данной ЗЛП надовоспользоваться методом искусственного базиса. Суть метода довольнопроста К строкам, в которых отсутствует базисная переменная добавляется по одной искусственной базисной переменной. Новая задача решается Симплекс-методом, причем все искусственные базисные переменные должны стать свободными выйти из базиса и их сумма должна равняться нулю, в обратном случае в данной системе невозможно выделить допустимый базис. Рассмотрим следующийпример min f В первом уравнении нет базисных неизвестных.
Введ м искусственную базисную неизвестную Y1 и заполним первую симплекс-таблицуДля того, чтобы избавитсяот искусственной базисной неизвестной нам предстоит решить вспомогательнуюзадачу F Y1 8594 minВыражая базиснуюнеизвестную Y1 через свободные получаем F 4X1 X2 4 8594 min Б X1 X2 X3 X4 Y1 С Y1 4 1 0 0 1 4 X4 11 3 -5 -1 0 12 F 4 1 0 0 0 4 Выбираем элемент в ячейке 3 2 и делаем шаг. Б X1 X2 X3 X4 Y1 С X2 4 1 0 0 1 4 X4 -1 0 -5 -1 -3 0 F 0 0 0 0 -1 0 min f 0,все коэффициенты в последней строке меньше или равны нулю, следовательно мыперешли к новому естественному базису.
Теперь можно решать основную задачу. ПринципдвойственностиВ реальной практикевстречаются задачи в которых число неизвестных больше числа ограничений.
Такиезадачи решать в их первозданном виде довольно трудно, но, применяя принципдвойственности можно заметно упростить решение, поскольку в двойственной задачебудет, наоборот, больше ограничений, чем переменных. Для того чтобы показать, как
Принцип двойственности
может упростить процесс решения приведем следующийпример max f min 966 Из данного примера легкопросматривается взаимосвязь между исходной и двойственной задачами. Введя в рассмотрениеследующие элементы Эту связь можнообозначить следующим образом max f min 966 В двойственной задачевсего 2 переменных.
Е можно легко решить графическим методом и, используявторую теорему двойственности, найти решение исходной. Пропустим процесс решениядвойственной ЗЛП, записав только результаты Y1 2 Y2 4 min 966 150Т.к max f min 966 , решение исходнойзадачи уже известно. Оста тся только найти значения X1, X2, X3, при которых это значение достигается. Здесь мыприменим вторую теорему двойственности, которая устанавливает следующеесоответствие В нашем примереполучается следующая вполне тривиальная система линейных уравнений Решение данной системылегко находится методом Гаусса и окончательный ответ таков Функция f достигает максимума при X1 0, X2 5, X3 10 и max f 150 Списокиспользованной литературы Учебник Математика в экономике А.С. Солодовников, В.А. Бабайцев, А.В. Браилов Финансы и статистика 1999г. Сборник задач по курсу математики под редакцией А.С. Солодовникова и А.В. Браилова ФА 2001г. Линейные неравенства С.Н. Черников Наука 1968 Краткий очерк развития математики Д.Я. Стройк Наука 1984. 1 Вектор нормали имеет координаты С1 С2 , где C1 и C2 коэффициенты принеизвестных в целевой функции f C1 9702 X1 C2 9702 X2 C0. 2 при нахождении минимума выбираем положительныекоэффициенты 3 Если положительных элементов не оказалось тоданная ЗЛП не имеет решения, т.е max f 8734 при задаче на нахождение максимума или min f — 8734 нахождениеминимума 4 Если есть несколько одинаковых отношений можновыбрать любую строку.
