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

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

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

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

на тему:

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

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

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

Научный управляющий:

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

Москва 2002г

Оглавление

Вступление.. 2

Графический способ.. 3

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

Способ искусственного базиса.. 8

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

Перечень использованной литературы... 12

Вступление

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

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

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

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

Графический способ

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

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

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

    На первом шаге нужно выстроить область допустимых решений. Для данного примера удобнее всего избрать 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– 1-ая общая точка области допустимых решений (полиэдр 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 0 -1 1 1 0 1
X4 0 1 -1 0 1 1
X5 1 1 1 0 0 2
f 0 -6 7 0 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), то для решения данной ЗЛП нужно пользоваться способом искусственного базиса.

Сущность способа достаточно ординарна:

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

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

min(f)-?

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

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

F=Y1→min

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

F+4X1+X2=4 →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(φ)-?

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

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

Эту связь можно обозначить последующим образом Методы решения систем линейных неравенств - реферат:

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

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

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

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

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

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

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

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

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

[1] Вектор нормали имеет Методы решения систем линейных неравенств - реферат координаты (С1;С2), где C1 и C2 коэффициенты при неведомых в мотивированной функции f=C1◦X1+C2◦X2+C0.

[2] при нахождении минимума избираем положительные коэффициенты

[3] Если положительных частей не оказалось то данная ЗЛП не имеет решения, т.е max(f)=+∞ (при задачке на нахождение максимума) либо min(f)=- ∞ (нахождение Методы решения систем линейных неравенств - реферат минимума)

[4] Если есть несколько схожих отношений можно избрать всякую строчку



metodi-svarki-referat.html
metodi-tehnologii-obucheniya.html
metodi-teoreticheskogo-issledovaniya-metodicheskoe-posobie-dlya-pedagogov-po-podgotovke-uchashihsya-k-nauchno-prakticheskoj-konferencii.html