Исследование
<<  Планирование исследования Урок – исследование одного слова  >>
Исследование операций
Исследование операций
Правила игры
Правила игры
Литература
Литература
Немного истории…
Немного истории…
Эйлер: «Все явления в Мире подчинены оптимизации, и нет никаких
Эйлер: «Все явления в Мире подчинены оптимизации, и нет никаких
Мат
Мат
Принятие решений
Принятие решений
Мат
Мат
Алгоритм Гаусса для решения системы линейных уравнений The Nine
Алгоритм Гаусса для решения системы линейных уравнений The Nine
Мат
Мат
Булева задача о ранце (ЗР)
Булева задача о ранце (ЗР)
Задача коммивояжёра (КМ)
Задача коммивояжёра (КМ)
Пример КМ
Пример КМ
Задача производства и хранения продукции
Задача производства и хранения продукции
Задача производства и хранения продукции
Задача производства и хранения продукции

Презентация: «Исследование операций». Автор: Adil I. Erzin. Файл: «Исследование операций.ppt». Размер zip-архива: 98 КБ.

Исследование операций

содержание презентации «Исследование операций.ppt»
СлайдТекст
1 Исследование операций

Исследование операций

1 лекция в неделю (9-11) 1 практика в 2 недели (4-6) Лектор – проф. ЕРЗИН Адиль Ильясович Ком. 223 (Институт математики СО РАН) Тел. 3634-623 E-mail: adilerzin@math.nsc.ru Лекции - http://math.nsc.ru/LBRT/k4/LOR/ Практика - http://math.nsc.ru/LBRT/k4/or/ + Семинары – к.ф.-м.н. Тахонов И.И.

2 Правила игры

Правила игры

4 (домашние) задачи письменный экзамен (конец апреля – начало мая) устный (open book) экзамен (во время сессии) 3 попытки…

Вид деятельности

Количество баллов

Работа на семинаре у доски

0-5

Активная работа на семинаре

1-5

Домашние задачи

0-10

Письменный экзамен

0-10

Оценка

Необходимые условия

«Отлично»

(? 25 баллов) & (решены 4 задачи) & (п. Экз. ? 6 баллов)

«Хорошо»

(? 20 баллов) & (решены 4 задачи)

«Удовлетворительно»

Либо ? 15 баллов, либо ? 11 и ? 1 за работу на семинаре

3 Литература

Литература

Береснев В.Л., Дементьев В.Т. Исследование операций. Введение: Учеб. пособие, Новосибирск: Изд-во НГУ, 1979. Гимади Э.Х., Глебов Н.И. Экстремальные задачи принятия решений: Учеб. пособие, Новосибирск: Изд-во НГУ, 1982. Гимади Э.Х., Глебов Н.И. Дискретные экстремальные задачи принятия решений: Учеб. пособие, Новосибирск: Изд-во НГУ, 1991. Ерзин А.И. Введение в исследование операций: Учеб. пособие, Новосибирск: Изд-во НГУ, 2006. math.nsc.ru/LBRT/k4/LOR. Гончаров Е.Н., Ерзин А.И., Залюбовский В.В. Исследование операций. Примеры и задачи: Учеб. пособие, Новосибирск: Изд-во НГУ, 2005. math.nsc.ru/LBRT/k4/or. Карманов В.Г. Математическое программирование. М.: Физматлит, 2004. Форд Л., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966. Wolsey L.A. Integer Programming. New York: John Wiley & Sons, Inc, 1998.

4 Немного истории…

Немного истории…

1935 – Великобритания – ПВО 1938 – Operational Research США – Operations Research – дальнейшее развитие… Задачи ИО: целераспределения быстродействия упаковки о рюкзаке… В рамках ИО рассматриваются задачи: ЛП, ЦЛП, СЛП теории расписаний и сетевого планирования транспортные задачи и задачи о назначениях маршрутизации и построения оптимальных структур теории игр потоки в сетях управления запасами теории массового обслуживания …

5 Эйлер: «Все явления в Мире подчинены оптимизации, и нет никаких

Эйлер: «Все явления в Мире подчинены оптимизации, и нет никаких

сомнений, что всё рациональное может быть объяснено оптимизационными методами»

6 Мат

Мат

анализ и экстремальные задачи

f (x) – гладкая выпуклая/вогнутая ? f? (x) = 0… x ? D ? градиентный метод; метод множителей Лагранжа; метод штрафных функций… f (x) – линейная и мн. D задано линейными (не)равенствами… Симплекс метод… f (x) – строго унимодальная ф. одной переменной ? дихотомия, метод золотого сечения (метод Фибоначчи)…

7 Принятие решений

Принятие решений

Какое решение является наилучшим? Ответ можно искать на основе опыта и здравого смысла Но: решений много… трудно представить реакцию системы на управление из-за ее сложности Основной способ ИО – это переход от качественной модели к математической ? математическое моделирование – основной метод ИО Будем понимать под ИО науку о математических моделях и методах принятия оптимальных решений

8 Мат

Мат

моделирование

Математическая модель ? объективная схематизация основных аспектов решаемой задачи, или описание задачи в математических терминах. Общий вид математической модели:

Или

Или

задача ЛП:

задача ЦЛП:

задача булевого ЛП:

задача смешанного ЛП:

9 Алгоритм Гаусса для решения системы линейных уравнений The Nine

Алгоритм Гаусса для решения системы линейных уравнений The Nine

Chapters on the Mathematical Art. 2nd century BC, New York Times of November 7, 1979: “A surprise discovery by an obscure Soviet mathematician has rocked the world of mathematics”. Этот неизвестный математик – Л.Г. Хачиян. Он модифицировал метод эллипсоидов, который был разработан для нелинейного программирования Н.З. Шором и др., и доказал его полиномиальность. Это была сенсация! На практике метод эллипсоидов работал плохо… Karmarkar (1984)

10 Мат

Мат

моделирование

Если целевая функция или/и ограничения нелинейные, то такая модель называется нелинейной. Оптимизационные задачи, в которых переменные принимают значения из конечного множества, называют задачами дискретной (или комбинаторной) оптимизации. Комбинаторные постановки задач часто можно записать в виде:

Где ci ? R, i ? N и F – заданное множество подмножеств мн. N = {1, …, n}.

11 Булева задача о ранце (ЗР)

Булева задача о ранце (ЗР)

Дано: N – множество предметов; A – емкость ранца; cj ? 0 ценность предмета; aj ? 0 – объем (вес) предмета. Требуется выбрать подмножество предметов максимальной ценности, объем которых не превосходит A.

Мат. постановка:

Комбинаторная постановка:

12 Задача коммивояжёра (КМ)

Задача коммивояжёра (КМ)

Дано: N – множество городов; cij ? 0 – расстояние (стоимость переезда). Требуется найти гамильтонов цикл min длины.

Или

13 Пример КМ

Пример КМ

3

1

2

4

5

6

8

7

9

14 Задача производства и хранения продукции

Задача производства и хранения продукции

Дано: dt ? 0 – потребности; ft ? 0 – фиксированные затраты; pt ? 0 – стоимость производства единицы продукции; ht ? 0 – стоимость хранения единицы продукции. Требуется определить план: потребности удовлетворены, и суммарные затраты, связанные с производством и хранением, min Переменные: xt – объем продукции, выпущенной в течение дня t; st – количество продукции на складе к концу дня t; yt = 1, если в день t осуществляется производство и yt = 0 в противном случае.

15 Задача производства и хранения продукции

Задача производства и хранения продукции

Если доп. потребовать, что sn = 0, то

И справедливо равенство

Тогда пер. st можно исключить

«Исследование операций»
http://900igr.net/prezentacija/pedagogika/issledovanie-operatsij-185178.html
cсылка на страницу

Исследование

11 презентаций об исследовании
Урок

Педагогика

135 тем
Слайды