Курсовая: Методы решения систем линейных неравенств - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

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

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Архив Zip, 141 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!

Узнайте стоимость написания уникальной работы



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



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














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

на тему:

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



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

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

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

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




Москва 2002г


Оглавление


Вступление 2

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

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

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

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

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







Вступление


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


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


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


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



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

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


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


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



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



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


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





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

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


  1. Теперь можно перейти к непосредственному нахождению максимума функции 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.



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


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



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


Система (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


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


  1. Для того чтобы найти максимум функции 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)-?


  1. В первом уравнении нет базисных неизвестных. Введём искусственную базисную неизвестную 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(?), решение исходной задачи уже известно. Остаётся только найти значения X1, X2, X3, при которых это значение достигается. Здесь мы применим вторую теорему двойственности, которая устанавливает следующее соответствие:



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



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


Функция f достигает максимума при X1=0, X=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 Если есть несколько одинаковых отношений можно выбрать любую строку

1Авиация и космонавтика
2Архитектура и строительство
3Астрономия
 
4Безопасность жизнедеятельности
5Биология
 
6Военная кафедра, гражданская оборона
 
7География, экономическая география
8Геология и геодезия
9Государственное регулирование и налоги
 
10Естествознание
 
11Журналистика
 
12Законодательство и право
13Адвокатура
14Административное право
15Арбитражное процессуальное право
16Банковское право
17Государство и право
18Гражданское право и процесс
19Жилищное право
20Законодательство зарубежных стран
21Земельное право
22Конституционное право
23Конституционное право зарубежных стран
24Международное право
25Муниципальное право
26Налоговое право
27Римское право
28Семейное право
29Таможенное право
30Трудовое право
31Уголовное право и процесс
32Финансовое право
33Хозяйственное право
34Экологическое право
35Юриспруденция
36Иностранные языки
37Информатика, информационные технологии
38Базы данных
39Компьютерные сети
40Программирование
41Искусство и культура
42Краеведение
43Культурология
44Музыка
45История
46Биографии
47Историческая личность
 
48Литература
 
49Маркетинг и реклама
50Математика
51Медицина и здоровье
52Менеджмент
53Антикризисное управление
54Делопроизводство и документооборот
55Логистика
 
56Педагогика
57Политология
58Правоохранительные органы
59Криминалистика и криминология
60Прочее
61Психология
62Юридическая психология
 
63Радиоэлектроника
64Религия
 
65Сельское хозяйство и землепользование
66Социология
67Страхование
 
68Технологии
69Материаловедение
70Машиностроение
71Металлургия
72Транспорт
73Туризм
 
74Физика
75Физкультура и спорт
76Философия
 
77Химия
 
78Экология, охрана природы
79Экономика и финансы
80Анализ хозяйственной деятельности
81Банковское дело и кредитование
82Биржевое дело
83Бухгалтерский учет и аудит
84История экономических учений
85Международные отношения
86Предпринимательство, бизнес, микроэкономика
87Финансы
88Ценные бумаги и фондовый рынок
89Экономика предприятия
90Экономико-математическое моделирование
91Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Заказала российская фирма микросхемы в Японии. Десять тысяч. И в контракте особо оговорили, что на каждую тысячу должно быть не более пяти бракованных. Ну как у нас положено, процент брака. Японцы на этом пункте несколько тормознулись, почесали репу, но приняли. В результате наши получили десять тысяч микросхем и отдельно, в кулечке, еще пятьдесят. Аккуратно просверленных посередине дрелью.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

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

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2017
Рейтинг@Mail.ru