Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Методы решения систем линейных неравенств
Раздел: Рефераты по математике
Тип: реферат Добавлен 12:35:31 14 августа 2005 Похожие работы
Просмотров: 4317 Комментариев: 11 Оценило: 10 человек Средний балл: 2.3 Оценка: 2     Скачать

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

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

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

на тему:

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

Выполнил студент группы МЭК 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)=+ ∞, либо min(f)= -∞.

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


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

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

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

Система (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(φ), решение исходной задачи уже известно. Остаётся только найти значения 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] Если есть несколько одинаковых отношений можно выбрать любую строку

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений22:22:55 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
11:53:44 24 ноября 2015
4a+59+4a
ольга14:21:25 20 сентября 2010
баран
722:25:59 06 августа 2010
12+4х>6х 2х
алгебра11:33:06 28 ноября 2009

Смотреть все комментарии (11)
Работы, похожие на Реферат: Методы решения систем линейных неравенств
Решения задачи планирования производства симплекс методом
Федеральное агентство по образованию Санкт-Петербургский Государственный Политехнический Университет Факультет технической кибернетики Кафедра ...
Приведение системы ограничений, заданных в форме неравенств, к канонической форме равенств осуществляется посредством соответствующего увеличения размерности вектора X=(x1, x2, x3 ...
В результате решения поставленной задачи симплекс-методом получили набор производимой продукции x=(x1, x2, x3, x4, x5)=( 15145/103, 8910/103, 0, 1250/103, 3255/103), который ...
Раздел: Рефераты по экономико-математическому моделированию
Тип: дипломная работа Просмотров: 6524 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Линейное программирование как метод оптимизации
Содержание Введение 1. Общая постановка задачи линейного программирования (ЛП) 2. Приведение задачи линейного программирования к стандартной форме 3 ...
Любая задача линейного программирования приводится к стандартной (канонической) форме основной задачи линейного программирования, которая формулируется следующим образом: найти ...
X1, X2, X3, X4 = 0
Раздел: Рефераты по экономико-математическому моделированию
Тип: курсовая работа Просмотров: 8568 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Графический метод и симплекс-метод решения задач линейного ...
СОДЕРЖАНИЕ ВВЕДЕНИЕ 1. Геометрический метод решения задач ЛП 2. Симплекс-метод 2.1 Идея симплекс-метода 2.2 Реализация симплекс-метода на примере 2.3 ...
Следовательно, выбирая в качестве базисных переменных x1, x3, x5, и полагая в системе уравнений x2 = x4 = 0 (небазисные переменные), немедленно находим x1 =10, x3 = 20, x5 = 8, так ...
f(x) = x1 + 2 x2 + 0 x3 + 0 x4 max
Раздел: Рефераты по экономико-математическому моделированию
Тип: реферат Просмотров: 7203 Комментариев: 2 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать
Математические методы исследования экономики
Всегда и во всех сферах своей деятельности человек принимал решения. Важная область принятия решений связана с производством. Чем больше объем ...
К = F(X1, X2, . . . , Xn) => MIN(MAX) Функция К является математическим выражением результата действия, направленного на достижение поставленной цели, и поэтому ее называют целевой ...
Так в нашем примере при q = 0. 1 относительная оценка переменной X3 равна нулю так что если коэффициент целевой функции переменной X2 увеличится на 0. 1 или более станет выгодно ...
Раздел: Рефераты по экономике
Тип: реферат Просмотров: 1668 Комментариев: 3 Похожие работы
Оценило: 2 человек Средний балл: 3.5 Оценка: неизвестно     Скачать
Матричные антагонистические игры с нулевой суммой в чистых стратегиях
Введение Реальные конфликтные ситуации приводят к различным видам игр. Игры различаются по целому ряду признаков: по количеству участвующих в них ...
min Z = x1 + x2 + x3
К настоящему времени в литературе выделяют следующую классификацию ЗЛП (общая задача линейного программирования; каноническая целевая функция задачи линейного программирования ...
Раздел: Рефераты по математике
Тип: курсовая работа Просмотров: 8223 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Табличный симплекс-метод
ИСПОЛЬЗОВАНИЕ ТАБЛИЧНОГО СИМПЛЕКС-МЕТОДА ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ОПТИМИЗАЦИИ ЭКОНОМИЧЕСКИХ ЗАДАЧ ВВЕДЕНИЕ Цель данного ...
Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных f ( x1, x2, ... , xn ) при ограничениях gi ( x1, x2 ...
Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 1254 Комментариев: 4 Похожие работы
Оценило: 3 человек Средний балл: 2 Оценка: неизвестно     Скачать
Решение задач линейного программирования симплекс-методом
Содержание Введение 1. Теоретический материал 1.1 Математическая формулировка задачи линейного программирования 1.2 Решение задач линейного ...
Приведем заданную модель к каноническому виду, введя свободные переменные x3, x4, x5, превращающие неравенства в равенства.
x3, x4, x5 - базисные переменные; x1, x2 - свободные переменные.
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Просмотров: 9502 Комментариев: 2 Похожие работы
Оценило: 2 человек Средний балл: 3.5 Оценка: неизвестно     Скачать

Все работы, похожие на Реферат: Методы решения систем линейных неравенств (3070)

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(151171)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru