рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Работа сделанна в 2002 году

Методы решения систем линейных неравенств - Курсовая Работа, раздел Математика, - 2002 год - Финансовая Академияпри Правительстве Рфкафедраматематики И Финансовых Приложе...

ФИНАНСОВАЯ АКАДЕМИЯПРИ ПРАВИТЕЛЬСТВЕ РФКафедраматематики и финансовых приложенийКурсовая работана тему Методырешения систем линейных неравенств Выполнил студент группы МЭК 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, при которых это значение до...

– Конец работы –

Используемые теги: Методы, решения, систем, ных, неравенств0.084

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

Системы линейных неравенств и их решение. Геометрическая интерпретация систем линейных неравенств
Линейные неравенства Строгие неравенства Нестрогие неравенства Какой геометрический... Далее приведем простой пример задачи такого класса... Компания специализируется на выпуске хоккейных клюшек и наборов шахмат Каждая клюшка приносит компании прибыль в...

Математическая модель. Решение нелинейных уравнений. Решение систем линейных алгебраических уравнений
Погрешность математической модели связана с ее приближенным описанием реального объекта Например если при моделировании экономической системы не... Исходные данные... Исходные данные как правило содержат погрешности так как они либо неточно измерены либо являются результатом...

Решение систем линейных алгебраических уравнений методом простых итераций и методом Зейделя
При использовании итерационных процессов, сверх того, добавляется погрешность метода. Заметим, что эффективное применение итерационных методов существенно зависит… Сейчас разберем несколько определений которые будем использовать в этой работе.Система линейных уравнений с n…

Методы решения жестких краевых задач, включая новые методы и программы на С++ для реализации приведенных методов
Стр. 8. Второй алгоритм для начала счета методом прогонки С.К.Годунова.Стр. 9. Замена метода численного интегрирования Рунге-Кутта в методе прогонки… Стр. 10. Метод половины констант. Стр. 11. Применяемые формулы… Стр. 62. 18. Вычисление вектора частного решения неоднородной системы дифференциальных уравнений. Стр. 19. Авторство.…

ЛЕКЦИЯ № 2 / 3 2. Решение систем линейных уравнений методом Гаусса
Кафедра Автоматизации управления войсками... Только для преподавателей...

Лекция 1. Тема: Операционная система. Определение. Уровни операционной системы. Функции операционных систем. 1. Понятие операционной системы
Понятие операционной системы... Причиной появления операционных систем была необходимость создания удобных в... Операционная система ОС это программное обеспечение которое реализует связь между прикладными программами и...

Решение систем линейных алгебраических уравнений методом Гаусса и Зейделя
Хотя задача решения системы линейных уравнений сравнительно редко представляет самостоятельный интерес для приложений, от умения эффективно решать… В значительной степени ограничения на размерность решаемых систем можно снять,… Поэтому при создании вычислительных алгоритмов линейной алгебры большое внимание уделяют способам компактного…

Решение систем линейных дифференциальных уравнений пятиточечным методом Адамса – Башфорта
Решение систем линейных дифференциальных уравнений мы описываем отдельной процедурой , что облегчает дальнейшую алгоритмизацию . Далее составляем…

ТЕКСТЫ ЛЕКЦИЙ ЛЕКЦИЯ 1. СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ. 1. Системы линейных уравнений
ЛЕКЦИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ... Системы линейных уравнений Равносильные системы линейных уравнений...

0.041
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам