ФИНАНСОВАЯ АКАДЕМИЯПРИ ПРАВИТЕЛЬСТВЕ РФКафедраматематики и финансовых приложенийКурсовая работана тему Методырешения систем линейных неравенств Выполнил студент группы МЭК 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 соответствует значениясвободных неизвестных.
Если после подготовки ЗЛПк специальному виду для решения симплекс мето... Для того чтобы показать, как. Рассмотрим следующийпример min f В первом уравнении нет базисных неизв... Суть метода довольнопроста К строкам, в которых отсутствует базисная п... Б 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 mi...
Пропустим процесс решениядвойственной ЗЛП, записав только результаты Y... 2 при нахождении минимума выбираем положительныекоэффициенты 3 Если по... может упростить процесс решения приведем следующийпример max f min 966... Сборник задач по курсу математики под редакцией А.С. Оста тся только найти значения X1, X2, X3, при которых это значение до...