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

Курсовая

Решение оптимизационной задачи линейного программирования

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

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

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Архив Zip, 65 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

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

38 Белорусский государственный университет информатики и радиоэлектрон ики Факультет информационных технологий и управления Кафедра информационных технологий автоматизированных систем «К защите допускаю» ______________Н.В . Батин “ ___” ______________2001г. КУРСОВАЯ РАБОТА по дисциплине «Системный анализ и исследование опер аций» на тему : «Решение оптимизационной задачи линейного программирования» Выполнил студент гр . 920603 Журавкин А.В. Руководитель работы Батин Н.В. Минск , 2001 СОДЕРЖАН ИЕ : ВВЕДЕНИЕ…….……………………………………………………………… ...3 1. Постановка задачи оптимизации……………………………………….… 8 2. Построение аналитической модели…………………………………….… 9 3. Обоснование и описание вычислительной процедуры……………… ..11 3.1. Приведение задачи линейного программировани я к стандартной форме………………..………………………………………………… .11 3.2. Основная идея симлекс-метода…………………………………… ..12 3.3. Двухэтапный симплекс-метод……………………………………… 12 4. Решение задачи оптимизации на основе симплекс-таблиц…………… 14 4.1. Приведение задачи к стандартной форме………..……………… ..14 4.2. Определение начального допустимого решения………………… 14 4.3. Построение искусственного базиса………...……………………… 15 4.4. Первый этап двухэтапного симплекс-метода…………………… .16 4.5. Второй этап двухэтапного метода……………………… ………… .19 5. Анализ модели на чувствительность…………………………………… ..22 5.1. Статус ресурсов……….……………………………………………… 22 5.2. Ценность ресурсов…………………………………………………… 22 5.3. Анализ на чувствительность к изменениям правых частей ограничений………………………………………………………. … ..23 5.4. Анализ на чувствительность к изменениям коэффициентов целевой функции……………………………………………...……… 25 6. Определение оптимального целочисленного решения………………… 26 6.1. Метод Гомори для частично целочисленных задач……..……… .26 ЗАКЛЮЧЕНИЕ……… …………………………………………………...…… 33 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ………………….…… ..34 УСЛОВНЫЕ СОКРАЩЕНИЯ………………………….…………………… 35 ПРИЛОЖЕНИЕ…………………………………………………………….… ..36 ВВЕДЕНИЕ В настоящее время оптимизация находит применение в науке , технике и в любой другой области человеческой деятельности . Оптимизация - целенаправленная деятельность , заключающаяся в получении наилучших результатов при соответствующих условиях . Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были з аложены математические основы оптимизации (вариационное исчисление , численные методы и др ). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко , поскольку практическое использование математически х методов оптимизации требовало огромной вычислительной работы , которую без ЭВМ реализовать было крайне трудно , а в ряде случаев - невозможно . Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса , например : количество продукции - расход сырья количество продукции - качество продукции Выбор компроми c ного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи . При поста новке задачи оптимизации необходимо : 1 . Наличие объекта оптимизации и цели оптимизации . При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины , т.е . одновременно системе не должно приписываться два и бо лее критериев оптимизации , т.к . практически всегда экстремум одного критерия не соответствует экстремуму другого . Приведем примеры . Типичный пример неправильной постановки задачи оптимизации : «Получить максимальную производительность при минимальной себе стоимости» . Ошибка заключается в том , что ставится задача поиска оптимальности 2-х величин , противоречащих друг другу по своей сути . Правильная постановка задачи могла быть следующая : а ) получить максимальную производительность при заданной себестоимост и ; б ) получить минимальную себестоимость при заданной производительности ; В первом случае критерий оптимизации - производительность а во втором - себестоимость. 2 . Наличие ресурсов оптимизации , под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта . 3 . Возможность количественной оценки оптимизируемой величины , поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий . 4. Учет ограничений . Обычно оптимизируемая величин а связана с экономичностью работы рассматриваемого объекта (аппарат , цех , завод ). Оптимизируемый вариант работы объекта должен оцениваться какой-то количественной мерой - критерием оптимальности. Критерием оптимальности называется количественная оценка оп тимизируемого качества объекта. На основании выбранного критерия оптимальности составляется целевая функция , представляющая собой зависимость критерия оптимальности от параметров , влияющих на ее значение . Вид критерия оптимальности или целевой функции опре деляется конкретной задачей оптимизации . Таким образом , задача оптимизации сводится к нахождению экстремума целевой функции . В зависимости от своей постановки , любая из задач оптимизации может решаться различными методами , и наоборот – любой метод может применяться для решения многих задач . Методы оптимизации могут быть скалярными (оптимизация проводится по одному критерию ), векторными (оптимизация проводится по многим критериям ), поисковыми (включают методы регулярного и методы случайного поиска ), анал и тическими (методы дифференциального исчисления , методы вариационного исчисления и др .), вычислительными (основаны на математическом программировании , которое может быть линейным , нелинейным , дискретным , динамическим , стохастическим , эвристическим и т.д .), теоретико-вероятностными , теоретико-игровыми и др . Подвергаться оптимизации могут задачи как с ограничениями , так и без них. Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования . Име нно линейное программирование явилось тем разделом , с которого начала развиваться сама дисциплина «математическое программирование» . Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е . составление программ ) для ЭВМ» не имеет , так как дисциплина «линейное программирование» возникла еще до того времени , когда ЭВМ стали широко применяться при решении математических , инженерных , экономических и др . задач . Термин «линейное программирование» возник в результате неточн о го перевода английского « line a r programming» . Одно из значений слова « programming» - составление планов , планирование . Следовательно , правильным переводом « line a r programming» было бы не «линейное программирование» , а «линейное планирование» , что более точ но отражает содержание дисциплины . Однако , термин линейное программирование , нелинейное программирование и т.д . в нашей литературе стали общепринятыми. Итак , линейное программирование возникло после Второй Мировой Войны и стал быстро развивать с я , привлекая внимание математиков , экономистов и инженеров благодаря возможности широкого практического применения , а так же математической «стройности» . Можно сказать , что линейное программирование применимо для построения математических мод е лей тех процессов , в основу которых может быть положена гипотеза линейного представления реального мира : экономических задач , задач управления и планирования , оптимального размещения оборудования и пр. Задачами линейного программирования называются задачи , в которых линейны как целевая функция , так и ограничения в виде равенств и неравенств . Кратко задачу линейного программирования можно сформулировать следующим образом : найти вектор значений переменных , доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств. Линейное программирование представляет собой наиболее часто используемый метод оптимизации . К числу задач линейного программирования можно отнести задачи : · рационального использования сырья и матер иалов ; задачи оптимизации раскроя ; · оптимизации производственной программы предприятий ; · оптимального размещения и концентрации производства ; · составления оптимального плана перевозок , работы транспорта ; · управления производственными запасами ; · и многие другие , принадлежащие сфере оптимального планирования . Так , по оценкам американских экспертов , около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование . Около четверти машинного времени , затраченно го в последние годы на проведение научных исследований , было отведено решению задач линейного программирования и их многочисленных модификаций. Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канто ровичем , которому за эти работы была присуждена Нобелевская премия по экономике . Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж . Данцингом симплекс-метода. В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения . Для решения задач линейного программирования разработано сложное програмное обе спечение , дающее возможность эффективно и надежно решать практические задачи больших объемов . Эти программы и системы снабжены развитыми системами подготовки исходных данных , средствами их анализа и представления полученных результатов . В развитие и совер шенствование этих систем вложен труд и талант многих матеметиков , аккумулирован опыт решения тысяч задач . Владение аппаратом линейного программирования необходимо каждому специалисту в области математического программирования . Линейное программирование те с но связано с другими методами математического программирования (например , нелинейного программирования , где целевая функция нелинейна ). Задачи с нелинейной целевой функцией и линейными ограничениями называют задачами нелинейного программирования с линейны ми ограничениями . Оптимизационные задачи такого рода можно классифицировать на основе структурных особенностей нелинейных целевых функций . Если целевая функция Е - квадратичная функция , то мы имеем дело с задачей квадратичного программирования ; если Е – э т о отношение линейных функций , то соответствующая задача носит название задачи дробно-линейного программирования , и т.д . Деление оптимизационных задач на эти классы представляет значительный интерес , поскольку специфические особенности тех или иных задач и грают важную роль при разработке методов их решения. Современные методы линейного программирования достаточно надежно решают задачи общего вида с несколькими тысячами ограничений и десятками тысяч переменных . Для решения сверхбольших задач используются уже , как правило , специализированные методы . 1. ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ Вариант 80. В цехе имеется токарный станок и станок-автомат . Цех выпускает детали 1,2 и 3 в комплекте : на каждую деталь 1 – по 2 детали 2 и 3. Часовая производ ительность станков по каждой из деталей приведена в таблице : Станки Детали 1 2 3 1.Токарный 5 5 10 2.Автомат 15 15 10 Таблица 1 . Часовая производительность станков Составить программу работы станков , при которой в течение смены (8 часов ) будет выпускаться максимальное количество комплектов деталей. 2. ПОСТРОЕНИЕ АНАЛИТИЧЕСКОЙ МОДЕЛИ Составим аналитическую модель задачи . Для этого сначала введем переменные , которые требуется определить : X 1 – время , которое работал токарный с танок над деталями типа 1 в течение рабочей смены ; X 2 – время , которое работал токарный станок над деталями типа 2 в течение рабочей смены ; X 3 – время , которое работал токарный станок над деталями типа 3 в течение рабочей смены ; X 4 – время , которое работал станок-автомат над деталями типа 1 в течение рабочей смены ; X 5 – время , которое работал станок-автомат над деталями типа 2 в течение рабочей смены ; X 6 – время , которое работал станок-автомат над деталями типа 3 в течение рабочей смены. Система ограничений состоит из двух групп . Первая группа устанавливает , что каждый из станков может работать не более 8 часов в смену. Ограничение времени работы токарного станка : X 1 + X 2 + X 3 8 ; Ограничение времени работы станка-автомата : X 4 + X 5 + X 6 8 . Вторая группа ограничений направлена на выполнение требования о комплектации деталей : на каждую деталь 1 должно приходиться по 2 детали 2 и 3. Но перед тем , как вводить это ограничение , определим , сколько детале й каждого типа у нас будет производиться за смену : 5 X 1 + 15 X 4 - будет произведено за смену деталей типа 1; 5 X 2 + 15 X 5 - будет произведено за смену деталей типа 2; 10 X 3 + 10 X 6 - будет произведено за смену деталей типа 3. Теперь введем сами ограничения : 2(5 X 1 + 15 X 4 ) = 5 X 2 + 15 X 5 ; 2(5 X 1 + 15 X 4 ) = 10 X 3 + 10 X 6 . Очевидно , что все переменные в задаче неотрицательные (объем продукции не может быть отрицательным ): X 1 , X 2 , X 3 , X 4 , X 5 , X 6
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Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
- О, сколько нам открытий чудных готовит отодвинутый диван!
Anekdot.ru

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

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

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


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