Лекции. Исследование операций и методы оптимизаций - файл n1.doc. Методы оптимизации и исследование операций
Методы оптимизации и исследование операций для бакалавров информатики. Часть 2
260 | Глава 14. Динамическое программирование |
В 1946 г. защитил диссертацию по теории дифференциальных уравнений в знаменитом Принстонском университете, где в это время сложилась выдающаяся математическая школа, включавшая известных нам Джона фон Неймана, Альберта Такера, Гарольда Куна и др.
Посетив в 1948 г. только что созданную в Калифорнии RAND Corporation (о ней мы говорили в кратком введении в историю исследования операций [9, с. 13]), Беллман был впечатлен свободной творческой атмосферой, которая царила в этой удивительной исследовательской компании, а также научным уровнем сотрудников, среди которых был, в частности, автор линейного программирования Джордж Данциг. В итоге Беллман предпочел прикладную математику академической и 13 лет проработал в RAND на штатной должности.
В1952 г. была опубликована первая статья, а 1957 г. — знаменитая монография по динамическому программированию [4], сразу завоевавшая мировую славу. По поводу необычного названия Беллман объяснял, что поскольку RAND финансировалась Министерством обороны, «теория многошаговых процессов» для военных звучала слишком абстрактно, тогда как слово «программирование» было вполне привычным армейским термином (см. [9, с. 41]). Кроме того, в новом названии содержался намек на превосходство перед линейным программированием Данцига.
Обладая прекрасными литературными данными, Беллман проявил удивительную творческую активность. Всего он опубликовал 619 статей и 39 книг, являясь одним из самых цитируемых математиков в мире. О широте его научных интересов говорит такой факт. Когда в 1965 г. Беллман вернулся к преподавательской работе в Университете южной Калифорнии в Лос-Анджелесе,он стал там профессором математики, электротехники и медицины.
В1973 г. в возрасте 53 лет, находясь на вершине своей научной деятельности, Беллман перенес операцию по удалению опухоли мозга, в результате осложнения потерял способность двигаться. Всю оставшуюся жизнь он был прикован к инвалидному креслу, сохранив при этом полную умственную работоспособность.
Литература
1.Ануфриев И. Е., Смирнов А. Б., Смирнова Е. Н. MATLAB 7.
—СПб.: БХВ-Петербург,2005. — 1104 с.
2.Аоки М. Введение в методы оптимизации: пер. с англ. — М.: Наука. Гл. ред.физ.-мат.лит., 1977. — 344 с.
3.Аттетков А. В., Галкин С. В., Зарубин В. С. Методы оптимизации: учеб. для вузов. — М.: Изд-во МГТУ им. Н. Э. Баумана, 2003. — 440 с. (Сер. Математика в техническом вузе. Вып. XIV).
4.Беллман Р. Динамическое программирование: пер. с англ.
—М.: ИЛ, 1960. — 400 с.
5.Бертсекас Д. Условная оптимизация и методы множителей Лагранжа: пер. с англ. — М.: Радио и связь, 1987. — 400 с.
6.Воробьев Н. Н. Числа Фибоначчи. — М.: Наука, 1978. — 144 с.
7.Гилл Ф., Мюррей У., Райт М. Практическая оптимизация: пер. с англ. — М.: Мир, 1985. — 509 с.
8. | Гельфанд И. М., Фомин С. В. Вариационное исчисление. — |
| М.: Физматгиз, 1961. |
9.Гладких Б. А. Методы оптимизации и исследование операций для бакалавров информатики. Ч. I. Введение в иссле-
дование операций. Линейное программирование: учеб. пособие. — Томск: Изд-воНТЛ, 2009. — 200 с.
10.Головина Л. И. Линейная алгебра и некоторые ее приложения: учеб. пособие. —2-еизд. — М.: Наука. Гл. ред.физ.-мат.лит., 1975. — 408 с.
11.Демьянов В. Ф., Васильев Л. В. Недифференцируемая оптимизация. — М.: Наука. Гл. ред. физ.-мат. лит., 1981. — 384 с.
12.Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М.: Физматлит, 2003. — 432 с.
13.Жилявский А. А., Жилинскас А. Г. Методы поиска глобального экстремума. — М.: Наука. Гл. ред. физ.-мат. лит., 1991. — 248 с.
14.Зойтендейк Г. Методы возможных направлений. — М.: ИЛ, 1963. — 176 с.
15.Змеев О. А., Терпугов А. Ф., Якупов Р. Т. Математический анализ. Ч. III. — Томск: Изд-во НТЛ, 2007. — 152 с.
16.Канатников А. Н., Крищенко А. П. Линейная алгебра: учеб. для вузов. — М.: Изд-во МГТУ им. Н. Э. Баумана, 2002. — 336 с. (Сер. Математика в техническом вузе. Вып. IV).
17. Карманов В. Г. Математическое программирование. —5-еизд. — М.: Физматлит, 2004. — 264 с.
18.Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М., 1974. — 832 с.
19.Мину М. Математическое программирование. Теория и алгоритмы: пер. с фр. — М.: Наука. Гл. ред.физ.-мат.лит., 1990. — 488 с.
20.Панченко Т. В. Генетические алгоритмы:учеб.-методич.пособие. — Астрахань: Изд. дом «Астраханский университет», 2007. — 87 с.
21.Пантелеев А. В., Летова Т. А. Методы оптимизации в примерах и задачах: учеб. пособие. — 2-е изд., испр. — М.: Высш. шк., 2005. — 544 с.
˙
22. Растригин Л.А. Статистические методы поиска. — М.: Наука. Гл. ред.физ.-мат.лит., 1968. — 376 с.
23. Реклейтис Г., Рейвиндран А., Рэгсдел К.Оптимизация в технике: в 2-х кн.: пер. с англ. — М.: Мир, 1986. — Кн. 1. — 349 с. — Кн. 2. — 320 с.
24. Сухарев А. Г., Тимохов А. В., Федоров В. В.Курс методов оптимизации. — 2-е изд. — М.: Физматлит, 2005. — 368 с.
25. Уайлд Д. Дж. Методы поиска экстремума: пер. с англ. — М.: Наука. Гл. ред.физ.-мат.лит., 1967. — 268 с.
26. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации: пер. с англ. — М.: Мир., 1972. — 240 с.
27. Химмельблау В. В. Прикладное нелинейное программирование). —2-еизд. — М.: Физматлит, 2005. — 534 с
28. Fletcher R. Practical Methods of Optimization. — Chichester– NewYork–Brisbane–Toronto:John Wiley & Sons. — V 1: Unconstrained optimization, 1980. — viii+120 p.; V 2: Constrained optimization, 1981. — ix+224 p.
29. GAMS — A User’s Guide. — Washington, DC: GAMS Development Corporation, 2006. — 251 p.
30. Conn A. R., Gould N. I. M. and Toint P. L.Trust-Region Methods. — Philadelphia, PA: SIAM, 2000. — xx+959 p.
Учебное пособие
ГЛАДКИХ Борис Афанасьевич
МЕТОДЫ ОПТИМИЗАЦИИ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
ДЛЯ БАКАЛАВРОВ ИНФОРМАТИКИ
Часть II. Нелинейное и динамическое программирование
Редактор Н. И. ШидловскаяВ¨ерстка Б. А. ГладкихДизайн Д. В. Фортеса
Изд. лиц. ИД № 04000 от 12.02.2001. Подписано к печати 23.06.11. Формат 60 × 841/16. Бумага офсетная. Печать офсетная. Гарнитура «Computer Modern Super». Усл. печ. л. 15,5.
Уч.-изд.л. 17,4. Тираж 200 экз.
ООО «Издательство научно-техническойлитературы» 634050, г. Томск, пл.Ново-Соборная,1, тел. (3822)533-335
Отпечатано в типографии ЗАО «М-Принт»,г. Томск, ул. Пролетарская, 38/1
«Исследование операций и методы оптимизации»
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ЧЕЧЕНСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ»«УТВЕРЖДАЮ»
Проректор
доцент С.М. Юшаев
______________________
«_____»__________201__г.
РАБОЧАЯ ПРОГРАММА
по дисциплине
«Исследование операций и методы оптимизации»
Направление подготовки
230700- «Прикладная информатика» Профиль подготовки
«Прикладная информатика в экономике»
Квалификация выпускника
Бакалавр
Форма обучения
Очная
Грозный 2010 г.
- Цель дисциплины
Процесс изучения дисциплины направлен на формирование следующих компетенций:
ПК-2 способен при решении профессиональных задач анализировать социально-экономические проблемы и процессы с применением методов системного анализа и математического моделирования;
ПК-21 способен применять системный подход и математические методы в формализации решения прикладных задач.3. В результате освоения дисциплины обучающийся должен
знать: общетеоретические основы математического программирования;
уметь: осуществлять постановку задач, решать и интерпретировать результаты решения задач математического программирования;
владеть: навыками работы с моделями математического программирования.
4. Место курса в системе наук
Для успешного овладения дисциплиной требуется предварительное изучение
следующих дисциплин: «Математический анализ», «Линейная алгебра», «Численные методы», «Теория вероятности». Является базовой для дисциплин «Теория систем и системный анализ», «Динамическая теория фирмы», «Модели финансовых рынков», «Математические методы социально-экономического прогнозирования», «Теория организации», «Теория экономической устойчивости», «Анализ инвестиционных проектов», «Международные финансы», «Модели социально-экономического развития региона», «Математические модели демографических процессов».
Предполагается изучение и использование в учебном процессе современных прикладных программных продуктов, позволяющих решать рассматриваемые задачи.5.Общая трудоемкость дисциплины составляет 324 часов, 9 зачетных единиц
| № п/п | Наименование раздела (темы) дисциплины | Трудоемкость в часах | |||||
| Всего в часах (324ч) | Аудиторная работа (158ч) | Внеауди- торная (самостоя- тельная) работа | |||||
| общая | Лекции 70 ч | Семинары и/или практические занятия (88ч) | |||||
| Общая (166ч) | |||||||
| 1 | Предмет исследования операций и его методология. Построение математических моделей | 19 | 9 | 4 | 5 | 9 | |
| 2 | Элементы выпуклого анализа | 19 | 9 | 4 | 5 | 10 | |
| 3 | Основная задача математического программирования. Основная задача выпуклого программирования | 19 | 9 | 4 | 5 | 9 | |
| 4 | Задача линейного программирования. Графическое решение ЗЛП. | 19 | 9 | 4 | 5 | 9 | |
| 5 | Симплекс-метод | 19 | 9 | 4 | 5 | 9 | |
| 6 | Метод искусственного базиса. Вырожденность. | 19 | 9 | 4 | 5 | 10 | |
| 7 | Теория двойственности. | 19 | 9 | 4 | 5 | 9 | |
| 8 | Двойственный симплекс-метод. | 19 | 9 | 4 | 5 | 9 | |
| 9 | Анализ устойчивости ЗЛП | 19 | 9 | 4 | 5 | 9 | |
| 11 | Задачи целочисленного линейного программирования | 20 | 10 | 5 | 5 | 9 | |
| 12 | Транспортная Задача | 20 | 9 | 4 | 5 | 9 | |
| 13 | Задачи стохастического программирования | 19 | 9 | 4 | 5 | 9 | |
| 14 | Задачи одномерной оптимизации | 19 | 9 | 4 | 5 | 9 | |
| 15 | Многомерная оптимизация без ограничений. | 19 | 9 | 4 | 5 | 9 | |
| 16 | Многомерная оптимизация с ограничениями. | 19 | 10 | 5 | 5 | 9 | |
| 17 | Многокритериальные задачи исследования операций | 19 | 9 | 4 | 5 | 9 | |
1. Разделы курса
Предмет исследования операций и его методология.
Элементы выпуклого анализа.
Основы математического программирования.
Задача линейного программирования.
Численные методы оптимизации.
Многокритериальные задачи исследования операций.2. Темы и краткое содержание
Тема 1. Предмет исследования операций и его методология. История и современный статус исследования операций (ИО). Основные понятия ИО. Основные особенности ИО. Основные этапы ИО. Математическое моделирование операций. Классификация экономико-математических моделей. Преимущества и недостатки использования моделей. Принципы моделирования. Проверка и корректировка модели. Подготовка модели к эксплуатации. Внедрение результатов операционного исследования.
Тема 2. Элементы выпуклого анализа.
Понятие отрезка в n-мерном пространстве. Понятие выпуклого множества. Выпуклость гиперплоскости и полупространства. Теорема о пересечении выпуклых множеств. Проекция точки на множество. Понятие крайней точки выпуклого множества. Теоремы отделимости. Выпуклые и вогнутые множества. Дифференцируемость по направлению.
Тема 3. Основы математического программирования.
Основная задача математического программирования. Основная задача выпуклого программирования. Возможные направления. Условие регулярности Слейтера. Функция
Лагранжа. Условия оптимальности. Теорема Куна-Таккера.
Тема 4. Задача линейного программирования.
Основная задача линейного программирования (ЗЛП). Свойства ЗЛП. Разрешимые и неразрешимые ЗЛП. Опорные решения. Базис опорного плана. Геометрическая интерпретация и графическое решение ЗЛП. Симплекс-метод. Метод искусственного базиса. Вырожденность. Теория двойственности. Определение двойственной ЗЛП. Общие правила построения двойственной задачи. Лемма о взаимной двойственности. 1-ая и 2-ая теоремы двойственности. Одновременное решение прямой и двойственной задач. Использование 2-ой теоремы двойственности для проверки на оптимальность решения ЗЛП. Экономические приложения. Двойственный симплекс-метод.
Анализ устойчивости ЗЛП. Транспортная задача и ее свойства. Метод потенциалов для решения транспортной задачи. Закрытые и открытые модели. Транспортные задачи с ограничениями.
Тема 5. Задачи целочисленного линейного программирования, экономические
приложения. Метод отсечения Гомори. Метод ветвей и границ.
Тема 6. Задачи стохастического программирования.
Тема 7. Численные методы оптимизации.
Задачи одномерной оптимизации. Методы дихотомии, Фибоначчи, «золотого сечения». Методы поиска с использованием квадратичной аппроксимации, метод кубической аппроксимации. Многомерная оптимизация без ограничений. Модели и условия сходимости численных методов. Градиентные и квазиньютоновские методы в Rn. Методы
сопряженных градиентов. Многомерная оптимизация с ограничениями. Метод проекции градиента. Метод условного градиента. Метод возможных направлений. Методы внешних штрафных функций, методы внутренних штрафных функций, комбинированные методы штрафных функций, модифицированные методы штрафных функций.
Тема 8. Многокритериальные задачи исследования операций.
Основные понятия и определения. Эффективные и слабоэффективные решения.
Построение множества эффективных решений и проверка эффективности выделенного
решения. Свертывание критериев.6. Перечень примерных контрольных вопросов и заданий для самостоятельной
работы
Тема 1
1. Что называется операцией?
2. Что составляет предмет исследования операций?
3. Назовите основные этапы операционного исследования и дайте их краткую
характеристику.
4. Классификация экономико-математических моделей.
5. Сформулируйте основные принципы моделирования.
Тема 2
1. Определение выпуклого множества.
2. Что называется проекцией точки на множество.
3. Что такое гиперплоскость?
4. Теорема о пересечении выпуклых множеств.
5. Понятие крайней точки выпуклого множества.
6. Теоремы отделимости.
7. Сформулируйте определения выпуклых и вогнутых множеств.
Тема 3
8. Сформулируйте основную задачу математического программирования.
9. Сформулируйте основную задачу выпуклого программирования.
10. Определение возможного направления.
11. Сформулируйте условие регулярности Слейтера.
12. Дайте определение седловой точки.
13. Сформулируйте достаточное условие оптимальности.
14. Теорема Куна-Таккера.
Тема 4
15. Сформулируйте основную задачу линейного программирования в канонической
форме.
16. Докажите эквивалентность различных форм записи ЗЛП.
17. Что такое опорные решения?
18. Как определяется базис опорного плана?
19. В чем состоит идея симплекс-метода?
20. Как осуществляется выбор переменной для вывода из базиса?
21. Как осуществляется выбор переменной для ввода в базис?
22. Сходимость симплекс-процедуры.
23. Признаки неразрешимости задачи линейного программирования.
24. В каких случаях применяется метод искусственного базиса?
25. Какой базисный план называется вырожденным?
26. Объясните экономический смысл двойственной задачи.
27. Какие существуют методы построения начального опорного плана транспортной
задачи?
Тема 5
28. Сформулируйте задачу целочисленного линейного программирования.
Тема 7
29. В чем состоит свойство унимодальности функции?
30. Являются ли методы исключения интервалов в целом более эффективными, чем
методы точечного оценивания?
31. Как принимается решение об окончании поиска при реализации поисковых методов?
32. Что понимается под принципиальным алгоритмом, реализуемым алгоритмом?
33. Какие точки называются желательными?
34. Сформулируйте условия сходимости градиентных и квазиньютоновских методов.
35. Какие методы одномерного поиска применяются в алгоритмах минимизации
выпуклых и невыпуклых функций?
36. Сформулируйте условия сходимости методов сопряженных градиентов.
37. Для чего и как осуществляется восстановление алгоритмов в методах сопряженных
градиентов?
38. Сформулируйте условия сходимости методов внешних и внутренних штрафных
функций.
39. Приведите примеры штрафных функций.
Тема 8
40. Какие решения задач многокритериальной оптимизации называются эффективными,
слабоэффективными.
41. Опишите метод последовательных уступок.
42. Поясните основные особенности процесса принятия решений в многокритериальных
операциях.
5. Примерная тематика рефератов, курсовых работ
1. Задачи линейного программирования с параметрами в функционале.
2. Задачи линейного программирования с параметрами в системе ограничений.
3. Алгоритмы решения сетевых задач.
4. Транспортная задача в матричной постановке. Венгерский метод.
5. Задачи геометрического программирования.
6. Задачи стохастического программирования.
7. Задачи дискретного программирования.
8. Задачи квадратичного программирования
9. Блочная задача линейного программирования. Метод декомпозиции Данцига-Вульфа.
10. Двойственные многокритериальные задачи.
6. Примерный перечень вопросов к зачету (экзамену) по всему курсу
1. Основные понятия исследования операций. Основные особенности ИО. Основные
этапы ИО.
2. Математическое моделирование операций. Классификация экономико-
математических моделей. Преимущества и недостатки использования моделей.
3. Принципы моделирования. Проверка и корректировка модели. Подготовка модели к
эксплуатации. Внедрение результатов операционного исследования.
4. Понятие отрезка в n-мерном пространстве. Понятие выпуклого множества.
5. Выпуклость гиперплоскости и полупространства. Теорема о пересечении выпуклых
множеств.
6. Проекция точки на множество. Понятие крайней точки выпуклого множества.
Теоремы отделимости.
7. Выпуклые и вогнутые множества. Дифференцируемость по направлению.
8. Постановка задачи математического программирования. Постановка задачи выпуклого
программирования.
9. Возможные направления. Условие регулярности Слейтера.
10. Функция Лагранжа. Условия оптимальности.
11. Теорема Куна-Таккера.
12. Постановка задачи линейного программирования. Свойства ЗЛП. Разрешимые и
неразрешимые ЗЛП.
13. Опорные решения. Базис опорного плана.
14. Геометрическая интерпретация и графическое решение ЗЛП.
15. Симплекс-метод.
16. Метод искусственного базиса.
17. Вырожденность ЗЛП.
18. Определение двойственной ЗЛП. Общие правила построения двойственной задачи.
19. Лемма о взаимной двойственности.
20. 1-ая и 2-ая теоремы двойственности.
21. Одновременное решение прямой и двойственной задач.
22. Двойственный симплекс-метод.
23. Транспортная задача и ее свойства. Закрытые и открытые модели.
24. Метод потенциалов для решения транспортной задачи.
25. Транспортные задачи с ограничениями.
26. Анализ устойчивости ЗЛП.
27. Задачи целочисленного линейного программирования, экономические приложения.
Метод отсечения Гомори. Метод ветвей и границ.
28. Постановка задачи одномерной оптимизации.
29. Метод дихотомии.
30. Метод Фибоначчи.
31. Метод «золотого сечения».
32. Методы поиска с использованием квадратичной аппроксимации.
33. Методы поиска с использованием кубической аппроксимации.
34. Задача многомерной оптимизации без ограничений.
35. Модели и условия сходимости численных методов.
36. Градиентные и квазиньютоновские методы в Rn.
37. Методы сопряженных градиентов.
38. Задача многомерной оптимизации с ограничениями.
39. Метод проекции градиента.
40. Метод условного градиента.
41. Метод возможных направлений.
42. Методы внешних штрафных функций.
43. Методы внутренних штрафных функций.
44. Комбинированные методы штрафных функций.
45. Модифицированные методы штрафных функций.
46. Многокритериальные задачи исследования операций. Основные понятия и
определения.
47. Эффективные и слабоэффективные решения. Построение множества эффективных
решений и проверка эффективности выделенного решения.7. Формы итогового контроля – 4 семестре- зачет, 5 семестре- экзамен8. Учебно-методическое обеспечение курса
1. Рекомендуемая литература (основная)
1. Акоф Р., Сасиени М. Основы исследования операций. М.:Мир,1971. -534 с.
2. Вагнер Г. Основы исследования операций. Т.1.- М.:Мир,1972; Т.2,3, 1973.
3. Вентцель Е.С. Исследование операций.-М.: Наука, 1980.
4. Исследование операций в экономике. По ред. Н.Ш. Кремера. – М.: Банки и биржи,
ЮНИТИ, 1997.
5. Конюховский П. Математические методы исследования операций в экономике. –
СПб.: Питер, 1999.
6. Конюховский П. Математические методы исследования операций. Пособие для
подготовки к экзамену. – СПб.: Питер, 2001.
7. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.-
488 с.
8. Полак Э. Численные методы. Единый подход. -М.:Мир,1974. 376 с.
9. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации.- М.: Наука,
1986.- 328 с.
2. Рекомендуемая литература (дополнительная)
1. Абрамов Л.Ф. Капустин В.Ф. Математическое программирование. Л., Изд-во Ленингр.
ун-та,1976. - 184 с.
2. Васильев Ф.П. Численные методы решения экстремальных задач.-М.: Наука, 1988.
3. Гермейер Ю.Б. Введение в теорию исследования операций.-М.: Наука, 1971.
4. Давыдов Э.Т. Исследование операций.- М.:Высш.шк., 1990.
5. Жуковский В.И., Молоствов В.С. Многокритериальное принятие решений в условиях
неопределенности.-М.:МНИИПУ.,1988.-131 с.
6. Зайченко Ю.П. Исследование операций.- Киев:Вища школа, 1975.
7. Интрилигатор М. Математические методы оптимизации и экономическая теория.-
М.:Прогресс, 1975.
8. Исследование операций: В 2-х томах. Под. ред. Дж. Моудера, С. Элмаграби.-
М.:Мир,1981.Т.1. 712 с.
9. Исследование операций: В 2-х томах. Под. ред. Дж. Моудера, С. Элмаграби.-
М.:Мир,1981.Т.2. 677 с.
10. Калихман И.Л. Сборник задач по математическому программированию.-М.:
Высш.школа, 1975.
11. Карлин С. Математические методы в теории игр, программировании и экономике. М.,
1964. 839 с.
12. Карманов В.Г. Математическое программирование.- М.:Наука, 1975.
13. Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и
замещения. Под__________. ред. И.Ф.Шахнова.-М.: Радио и связь,1981.-560 с.
14. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и
упражнениях: Учебное пособие для студентов вузов, обуч. по спец. «Прикладная
математика».-М.:Высш.шк.,1986.- 287с.
15. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных
задач.-М.: Наука, 1982, 256 с.
16. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике: В 2-х кн.-М.:Мир,
1986.
17. Современное состояние теории исследования операций/Под ред. Н.Н.Моисеева.-М.:
Наука, 1979.
18. Таха Х. Введение в исследование операций: В 2-х книгах. Кн. 1. -М.:Мир, 1985.- 496 с.
19. Таха Х. Введение в исследование операций: В 2-х книгах. Кн. 2. -М.:Мир, 1985.- 479 с.
20. Таха Х. Введение в исследование операций. – М.: Издательский дом “Вильямс”, 2001.
21. Ширяев В.И. Исследование операций и численные методы оптимизации: Учебное
пособие.- Челябинск: ЧГТУ, 1993.- 88 с.
22. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование (теория, методы и
приложения). М.,1969. 424 с.
6.Перечень обучающих, контролирующих компьютерных программ, кино- и телефильмов,
мультимедиа и т.п.
Пакеты прикладных программ – LINDO, LPP и др.
Разработчик: Доцент кафедры «Информатики» _________ /Якубов Т.В./
СОГЛАСОВАНО:
Зав.кафедрой «Информатики» ___________/Хатаева Р.С./
Эксперт от факультета __________ /_______________/
(Член рабочей группы ЧГПИ по ФГОС от факультета)
Начальник УМО __________/Идрисова Р.А./
100-bal.ru
Исследование операций
Лекции. Исследование операций и методы оптимизацийскачать (355 kb.)Доступные файлы (1):n1.doc
1 2 3 4 5 6 7 8 9 10 Исследование операцийОбобщенная формулировка задачи исследования операцийИсследование операций – научный метод, который дает в распоряжение инженера или руководителя количественные методы для принятия решений по управлению процессов оптимизации и видами человеческой деятельности. Операция – совокупность взаимосвязанных действий, направленных на достижение поставленной цели. Дискретное программирование – раздел математического программирования, в котором изучаются методы решения оптимизационных задач с не связанной областью допустимых решений. Эта область распадается на ряд несвязанных друг с другом подмножеств, и в частном случае являются отдельными точками подмножеств.Важность изучения таких задач определяется их актуальностью в различных сферах человеческой деятельности. К таким задачам относятся: задачи планирования, проектирования сложных систем.
Математическая формулировка задач дискретного программирования
Записываются целевая функция и условия ограничений в виде математических выражений. В общей форме математическая модель задачи имеет вид:Получить экстремальное значение целевой функции (F):
F: extrem z = f(x, w)
x,w
При ограничениях (D):
X є Rn, w є zp
D = gi(x,w)<=0
I=1,m
Где:
Z – целевая функция
X – вектор непрерывных оптимизационных переменных размерности n
W – вектор целочисленных оптимизационных переменных размерностью p
D - множество допустимых решений
Rn - n-мерное евклидовое пространство
Zp - p-мерное множество целых чисел.
gi - условие ограничения, накладываемое на оптимизационные переменные.
I - порядковый номер и, соответственно, общее количество оптимизационных переменных.Можно предположить, что ЗДП можно решить зная общие методы решения непрерывных оптимизационных задач, а именно:
- Сначала отбросить условия дискретности и решить обычную непрерывную задачу.
- Округлить полученное решение с целью обеспечения условия дискретности.
Графический метод. Основные понятия. Алгоритм методаГрафический метод решения задач всегда обладал для специалистов прикладников большой привлекательностью.Не смотря на большую погрешность результатов графический метод по сравнению с аналитическим остается полезным. И на это имеются веские причины:
Во 1-х их наглядность дает наилучшее представление о структуре задачи и ее решении.
Во 2-х эти методы, несмотря на ограниченную точность можно использовать для
предварительных выкладок, например, для поиска области решения, в которой
затем решают задачу более точными методами.
В 3-х часто в графике содержится значительная информация, которая позволяет
специалисту разобраться в сущности проблемы.Областью допустимых решений - называется область, каждая точка которой удовлетворяет одновременно всем ограничениям.Кроме условий ограничений в задаче задана целевая функция, поведение которой в рамках графика иллюстрации может быть охарактеризовано поведением уровня.Линией уровня функции называется множество точек из ее области определения в которых функция принимает одно и то же фиксированное значение.Градиентом функции f(x) называют вектор f(x),
f(x)=(∂f/∂x1; ∂f/∂x2;.. ∂f/∂xn) , который указывает направление наиболее быстрого возрастания функции, и следовательно ориентирован перпендикулярно линии уровня этой функции.Алгоритм решения задач графическим методом
- строят прямые, уравнение которых получают, заменяя в условиях ограничения
- определяют полуплоскости, обусловленные каждым из ограничений.
- определяют область допустимых нецелочисленных решений, Dнц.
- наносят координатную сетку с узлами точками имеющими целочисленные значения х1, х2.
- определяем область допустимых целочисленных решений.
- строят вектор с координатами (с1,с2).
- строят линию уровня целевой функции, приравняв выражение для целевой функции к нулю.
- перемещают линию уровня параллельно самой себе в направлении вектора из п. 6.
- В результате находят точку, в которой целевая функция принимает max значение.
- определяем координаты точки max целевой функции, вычисляют ее значение в этой точке.
Метод отсечений. Формулирование верного отсечения. Алгоритм методаСущность метода отсекающих плоскостей заключается в следующем:
- Вначале решается задача с отброшенным условием целочисленности.
- По полученным результатам делаются следующие выводы:
- если целевая функция задачи неограниченна на множестве Dнц, то делается вывод что она тоже неограниченна на множестве Dц. Объясняется это тем, что в области содержащей бесконечно удаленную точку всегда можно найти аналогичного рода точку принадлежащую Dц.
- Если оптимальное решение задачи на области Dнц является целочисленным, то оно одновременно является также оптимальным решением исходной задачи. Это также следует из того, что Dц є Dнц. При этом максимальное значение целевой функции задачи на области Dнц является всегда верхней границей для значения целевой исходной дискретной задачи.
- Если решение на области Dнц является нецелочисленным, то осуществляется переход к 3-му этапу.
- Составляется дополнительное ограничение , которое называется правильным
требованиям:
- быть линейным
- отсекать найденное оптимальное нецелочисленное решение задачи.
4. Осуществляется возращение к задачи линейного программирования с
отброшенным условием целочисленности, но с расширенной системой ограничений, в которую включено дополнительное ограничение полученное на 3-м этапе. Расширенная задача решается если найденное оптимальное решение
будет опять нецелым, то формируем новое дополнительное ограничение и процесс повторяем.
Окончание процесса происходит когда будет получено целочисленное решение задачи, либо установлено пустота области и ее допустимых решений. В этом случае на основании свойств правильного отсечения можно сделать следующие выводы:
- оптимальное решение задачи с расширенной системой ограничений является оптимальным решением исходной задачи.
- из пустоты допустимой области расширенной задачи следует пустота допустимой области исходной задачи. С геометрической точки зрения , каждому дополнительному ограничению в n-мерном пространстве соответствует определенная гиперплоскость отсекающая от многоугольника решений некоторую его часть , включая и оптимальную на данном этапе нецелочисленную вершину. При этом все точки с целочисленными координатами , в том числе и искомая оптимальная, находятся внутри этого многоугольника. Т. к. множество целых точек усеченного многогранника совпадает с множеством целых точек исходного многогранника – это значит , что если оптимальное решение задачи на усеченном многограннике удовлетворяет условию целочисленности, то оно и является оптимальным целочисленным решением исходной задачи. Через несколько операций отсечения искомая целочисленная точка оказывается сначала на границе области, а затем становится вершиной, неоднократно усеченного многогранника решений. В том случае если многогранник решений не содержит ни одной целочисленной точки, то сколько бы не вводили правильных отсечений целочисленное решение получить нельзя. Достоинства и недостатки алгоритма.Достоинством алгоритма является то, что он обладает свойством определенности за конечное число итераций.Недостатками алгоритма является:
- алгоритму присуща большая вычислительная сложность, даже для небольших по размерности задач число возможных правильных отсечений и соответственно больших итераций может быть весьма большей. Для многих задач их решение методом отсечений по вычислительной сложности не уступают полному перебору.
- отрицательной чертой алгоритма является также то, что первое допустимое решение исходной задачи в случае Dц=0 находится на последнем этапе ее решения.
- нельзя прервать работу алгоритма удовлетворившись некоторым ,промежуточным по точности допустимым решением.
Метод ветвей и границСущность метода заключается в направленном ветвлении области возможных решений оптимизационной задачи с целью локализации оптимального решения в одной из подобластей. При решении каждой задачи этим методом к ней должны быть применены следующие 2 процедуры:
1.Ветвление множества допустимых решений.
2.Определение нижних и верхних границ целевой функции.Формирование нижних и верхних оценок целевой функции
Общепринятым считается применение данного метода для задачи в которой направление оптимизации приведено к виду минимизации целевой функции.
Поэтому рассмотрим задачу следующего вида:
Min f(x)
x є D
В этой формуле х-вектор допустимых оптимизационных переменных , среди которых часть переменных действительные числа и часть - целочисленные переменные.Нижней оценки целевой функции в зависимости от выбранного способа ветвления могут определятся либо для подобластей Di є D либо для подобластей Di є Dٰ , где Di и Dٰ получены из соответствующих множеств Di и D путем снятия условия целочисленности на переменные. Нижней оценкой целевой функции f(x) на некотором множестве Di или Diٰ будем называть величину Σi=min Σij , где Σij – значение целевой функции f(x) на множестве Di для решений подзадачи j .Если при решении подзадачи установлено , Di – пустое множество , то нижнюю оценку принимают равной бесконечности.Нижние оценки имеют важное свойство.Их значение для образовавшихся при ветвлении подмножеств не могут быть меньше нижней оценки целевой функции на множестве которое подвергалось ветвлению.Для большинства задач вычисляют только одно значение верхней оценки на множестве Di. ŋ (Di).
Ее определяют как значение целевой функции для найденного допустимого_лучшего решения исходной задачи.Если для решаемой задачи можно просто и точно получить верхние оценки для отдельных множеств , образующихся при ветвлении, то их необходимо использовать для уменьшения вычислительной сложности процесса.На начальном этапе решения задачи значение верхней оценки обычно принимают равной бесконечности ŋ (Di) = ∞ .При нахождении первого допустимого решения , которое пренадлежит множеству D, xдоп є D, рассчитывают верхнюю оценку на множестве D , как значение целевой функции от найденного допустимого решения - ŋ (D) = f(xдоп).Затем при определении лучшего допустимого решения x ٰдоп (f(x ٰдоп )< f(xдоп)) ,
ŋ (D)= f(x ٰдоп ).Значение верхней оценки в процессе решения задачи может только уменьшаться.Алгоритм метода ветвей и границ.1 этап. Ветвлению в первую очередь подвергается подмножество S (S є I ), которому соответствует наименьшее значение нижней оценки целевой функции. I- это множество включающее номера всех подмножеств Di или Di’ , которые находятся на концах ветвления и ветвление которых не прекращено.2 этап. Если для некоторого подмножества i Σi≥ŋ(D) то ветвление его необходимо прекратить, т. к. потенциальные возможности нахождения лучшего решения в этом подмножестве оказывается хуже, чем значение целевой функции для найденного к данному моменту времени лучшего допустимого решения.3 этап. Ветвление подмножества Di’ прекращается, если найденное оптимальное решение Є D обосновывается это тем, что значение целевой функции от этого решения равно нижней границе на множестве Di. Следовательно, лучшего допустимого решения на данном множестве не существует. В этом случае рассматривают возможность корректировки верхней оценки целевой функции.4 этап. Если выполняется соотношение Σ≥ŋ(D), где Σ=min Σi, то выполняется условие i є I оптимальности для найденного допустимого решения.5 этап. После нахождения хотя-бы одного допустимого решения может быть рассмотрена возможность остановки работы алгоритма с их подсчетом погрешности найденного решения по отношению к оптимальному. ∆= Σ- ŋ(D) разница между нижней и верхней оценкой целевой функции.
Метод ветвей и границ относительно бинарных деревьев. Примеры задач, основные этапы, алгоритм нахождения оптимального решенияЭтот метод применяется для решения задач коммивояжера и по назначению.Задача коммивояжера:
Пусть задана матрица С=|| Cij || расстояний между городами. Если от некоторой строки i или некоторого столбца j вычесть минимальный из них, то получим матрицу, у которой в каждой строке и в каждом столбце будет хотя бы один нулевой элемент. Такая матрица называется приведенной, а процесс получения нулей – приведением. Сумма вычитаемых в процессе приведения элементов называется приводящей const обозначается hk, где к – порядковый номер приведения.
Для описания процедуры ветвления используем геометрическую интерпретацию метода. Разбиение множества всех циклов на не пересекаемые подмножества будет изображать дерево с вершинами, состоящими из пар допустимых(i,j) и запрещенных (i,j) городов.
Пара (i,j) содержит все маршруты, которые позволяют переход из города i в j(i,j) – все маршруты, запрещающие переход
из города i в j. Пара (к,l) – содержит все маршруты, в которых разрешен переход не только с к в l, но из i в j.Обозначим вершину, из которой осуществляется ветвление, k,l k,lчерез х. Вершину, которая наиболее вероятно принадлежит
перспективной ветви, обозначим через y, а запрещенную вершину через y. Поставим в соответствие вершине х сумму приводящих констант, которая представляет ее нижнюю
границу w(x). Процесс ветвления опишем следующим образом: процесс выбора пары городов для ветвления как игру 2-х лиц.
Игрок y имеет преимущество: он может выбирать любую еще не выбранную пару городов для ветвления. Стремясь построить цикл минимальной длины, он должен из исходной матрицы выбрать те пары городов, которым соответствуют минимальные элементы(в приведенной матрице это нулевые элементы).
Поскольку каждая строка и столбец приведенной матрицы содержат хотя бы один нулевой элемент, то претендентов на ветвление на 1-м шаге для множества y будет не меньше, чем n.
Неоднозначность выбора пары затрудняет процесс игрока y. Поэтому для выбора однозначной стратегии он накладывает ограничивающие факторы для игрока y : если y для объезда выбирает пару городов (i,j), то y должен выехать из любого города, но не в j и въехать в любой город, но не из i. Y ÷ (i,j).
Игрок y будет стремиться выбрать такой допустимый переезд, чтобы суммарный путь был минимальным. Поэтому в строке i приведенной матрицы он выбирает тот город (исключая j), которому соответствует минимальное расстояние. А в столбце j – город (исключая i), которому соответствует минимальный элемент.
Зная о стратегии y , игрок y выбирает из всех допустимых пар городов ту пару, у которой будет наибольшее расстояние.
1 2 3 4 5 6 7 8 9 10 Исследование операцийnashaucheba.ru
Методы оптимизации и исследование операций, Методы оптимизации
Пример готовой курсовой работы по предмету: Методы оптимизации
Введение 3
1. Анализ и выявления проблем объекта оптимизации 6
1.1. Описание авиационного предприятия 6
1.2. Комплексный анализ внешней и внутренней среды объекта управления. Построение SWOT-матрицы для принятия стратегических решений 17
1.3. Разработка моделей оптимизации (модели
2. для принятия тактических решений 21
2. Формирование математических моделей управления авиационным предприятием 28
2.1. Построение модели 1 с использованием частного случая модели целочисленного программирования — задачи о ранцах 28
2.2. Сравнительный анализ методом оптимизации и выбор наиболее подходящих методов 30
Решение математических моделей изучаемого объекта средства Excel 32
2.3. Принятые программы стратегических мероприятий по развитию предприятия 32
2.4. Результаты проведения расчетов по решению модели 2 и принятие оптимальных тактических решений 46
2.5. Оценка эффективности внедрения предлагаемых решений в управлении авиационным предприятием 47
Заключение 48
Список использованной литературы 49
Содержание
Выдержка из текста
Данная курсовая работа посвящена изучению вопросов совершенствования системы управления российской самолетостроительной корпорации «МиГ» путем количественного моделирования и оптимизации управленческих решений. Актуальность выбранной темы обусловлена тем, что в настоящее время для принятия управленческих решений необходимо принимать для учета множество факторов, а сильная конкуренция рынка требует принятий таких решений все чаще и чаще.
Данная курсовая работа посвящена изучению вопросов совершенствования системы управления ОАО «Корпорация «Иркут» путем количественного моделирования и оптимизации управленческих решений.
Актуальность выбранной темы обусловлена тем, что в настоящее время для принятия управленческих решений необходимо принимать для учета множество факторов, а сильная конкуренция рынка требует принятий таких решений все чаще и чаще.
Для оптимизации управленческих решений в рамках этой курсовой работы будут использоваться средства MS Office EXCEL и его функция «Поиск решения».
Быстрое развитие и усложнение техники, расширение масштабов проводимых мер и спектра их возможных последствий, внедрение автоматических систем управления во многие отрясли практики — все это делает необходимым анализ сложных целенаправленных процессов с рассмотрением их структуры и организации. Таким образом, можно сделать вывод, что «Исследование операций» — очень важная дисциплина, которая необходима для поиска лучших, оптимальных решений для задач, которые имеют несколько вариантов решения.
Формирование единого мирового информационно-коммуникационного пространства посредством развития международных интермодальных кори-доров обуславливает интеграционные процессы на транспорте. По результа-там оценки экспертов ВТО логистические издержки в России составляют в среднем 24%, а в Европейских странах 11%. Таким образом, логистиче-ская система РФ не соответствует международным требованиям. Этим вы-звана необходимость создания транспортно-логистических центров (ТЛЦ) в стратегически важных транспортных узлах, таких как Москва, Владивосток, Мурманск и Новороссийск.
Личный вклад автора заключается в разработке проекта оптимизации расходов на персонал при реализации портфеля ИТ-проектов в условиях нестабильной внешней среды, позволяющего обеспечить совместное решение задач определения приоритетности проектов при распределении трудовых ресурсов и оптимизации расходов на их содержание.
Оно стало одним из главных методов, применяемых в научных и практических исследованиях, т. По мере усложнения экономических явлений моде-лирование все чаще и чаще производится с помощью современных вычислительных систем.
Методы оптимизации рассматриваются в работах Волошина Г. Я., Гущи-ной Л.С., Гончарова В.А., Добрынина В.Н., Макшановой Л.М., Струченкова В.И., Щитова И.Н. и др.
Тем не менее, несмотря на наличие значительного количества концептуальных разработок по проблемам аналитического обоснования инвестиционных решений на фондовом рынке, на практике многие классические модели неприменимы или имеют существенные ограничения по причине наличия слишком огромного количества допущений, при которых результаты анализа становятся приблизительными.
Так, С. Джилфиллан, проанализировав более
20. важных изобретений за период 1787— 1935 гг., определил время от возникновения идеи до ее реализации. В среднем оно составляло от
3. до
3. лет. Исследованные им технологии разбиты на восемь уровней от возникновения первой идеи (уровень условно назван «Научные ресурсы») до ее широкой реализации в обществе (уровень условно именуемый «Общество»).
Список источников информации
1) Комарова Н.В. «Методические указания по выполнению курсовой работы по дисциплине „Методы оптимизации и исследования операций“ М.: Доброе слово, 2013»
2) Есипов Б.А.. «Методы оптимизации и исследования операций. Конспект лекций» Самара.: Изд-во Самарского государственного аэрокосмического университета, 2007
список литературы
referatbooks.ru
