Похожие презентации:
Методы оптимизации. Теория принятия решений ИУС
1.
Выбор вариантовЧасть 1. Методы оптимизации
Часть 2. Теория принятия решений
ИУС
2. Целенаправленная деятельность – это деятельность, направленная на достижение определенной цели или целей (пример с заводом)
Целенаправленнаядеятельность – это
деятельность, направленная
ИУС
на достижение определенной
цели или целей (пример с заводом)
3. Схема целенаправленной деятельности
Шаг 2Шаг 1
Шаг 3
ИУС
Многоэтапный процесс принятия
решений (выбора вариантов)
4. Современные информационные технологии (IT) и программные системы (PS) являются средством реализации различных видов и этапов
целенаправленнойдеятельности
ИУС
5. Примеры целенаправленной деятельности в области разработки программных систем и информационных технологий
Примерыцеленаправленной
деятельности в области
разработки программных
систем
ИУСи информационных
технологий
6. 1. Выбор наилучшего варианта распределения ресурсов Распределение финансовых , людских и иных ресурсов между отдельными
работами,составляющими программный
проект, с целью минимизации
ИУС
затрат и времени разработки –
основная задача менеджера
программного проекта
7.
Пример 1…
SW Project
1. Необходимо выполнить N работ или задач,
составляющих проект
2. Каждая работа может быть начата при условии
завершения
каких-то других работ (см. рис.)
ИУС
3. Время выполнения каждой работы определяется
выделяемыми для ее выполнения средствами
(ресурсами)
8. Пример сетевого графика разработки программного проекта
Пример сетевого графикаПример 1
разработки программного проекта
Показан критический путь
2
5
3
0
10
1
20
30
4
8
6
40
10
50
60
70
80
7
1. В кружках
показаны номера работ проекта
ИУС
2. Полное время завершения проекта определяется
критическими работами
3. Хорошо известная система Microsoft Project дает
возможность найти критический путь (анализ)
t
дни
9
9.
Пример 11. Оптимизируемый объект:
сетевой график разработки программного
проекта
2. Целевые (выходные) характеристики:
y1- время завершения проекта
y2- стоимость выполнения проекта
3. Выбираемые параметры:
xi – средства,
выделяемые для выполнения
ИУС
i - ой работы
Сумма xi = y2
10. Основная проблема: Как выбрать общий ресурс проекта y2, и затем распределить его между отдельными работами, чтобы выполнить
Пример 1Основная проблема: Как выбрать
общий ресурс проекта y2, и затем
распределить его между отдельными
работами, чтобы выполнить
следующие требования
y1 < 80 дней
ИУСy < $100,000
2
11. Альтернативная формулировка основной проблемы
Имеем систему неравенств:yi < ti
yi = Fi (X)
или:
zi > 0
ИУС
Здесь:
z i = ti – y i > 0
12. Соответствующая задача оптимизации:
J(x) = min zimax
i
Требования к выходным
характеристикам не выполнены
z4
z3
ИУС
Выбор X
x
Требования к выходным
характеристикам выполнены
0
z1
z
z2 z5
Здесь z4 = min zi
i
13. Стандартная задача оптимизации (однокритериальная конечномерная оптимизация)
x1x2
Объект
оптимизации
xn
J(x)
ИУС
min
x
Если имеем K(x)
max ,
то полагаем J(x) = - K(x)
и опять: J(x)
min
J(x)
14. 2. Задача оптимального проектирования Программный модуль (PM) и сама PS имеет характеристики, определяющие их качество и
соответствие спецификациям.Предполагается, что мы можем влиять
на эти характеристики, изменяя
внутренние параметры модулей и PS.
ИУС
Требуется произвести оптимальный
выбор этих параметров.
15.
Пример 2x1
x2
PS, PM
xn
Внутренние
(управляемые)
параметры PS (PM)
ИУС
Спецификации:
Опять неравенства !
yi < t i
y1
y2
ym
Выходные
(целевые)
характеристики,
определяющие
соответствие
спецификациям
16. 3. Выбор оптимального варианта инвестиций Заказчик требует разработать советующую программную систему, осуществляющую расчет
оптимальных инвестиций по годамс целью
получения максимальной
ИУС
прибыли через заданный
промежуток времени
17. 4. Вообще очень часто заказчики требуют разработки программных систем, решающих определенные прикладные задачи оптимальным
образом. И из всех возможныхвариантов подобных систем и
вариантов
ИУС реализаций требуется
выбрать наилучшие (по крайней
мере, по стоимости!)
18. Состав современной информационной технологии (IT) и программной системы (PS)
IT, PSИУС
HW
SW
BW
19. Вы – создатели и конструкторы современных информационных технологий и программных систем
Вы – создатели иконструкторы
современных
информационных
технологий
и
ИУС
программных систем
20. Три составляющие учебного плана:
BW – brainware: теоретическая подготовкав области алгоритмики, математические методы,
моделирование и исследование операций
SW – software : современные технологии,
среды и средства разработки программных
проектов ИУС
HW – hardware: основы моделирования и
использования современной IT - аппаратуры
21. Аналогия с процессом приготовления пищи
IT или PS – блюдо, которое выготовите как повар
HW - кухонное оборудование
ИУС
SW- продукты
(мясо, молоко, овощи)
и средства их производства
BW- рецепт приготовления блюда
22. Учебный план – BW
• Численный анализ, исследование операций• Системный анализ, моделирование,
идентификация, имитационное
моделирование
• Методы синтеза, управления и
оптимизации в теории систем,
компьютерное проектирование
• СистемыИУС
поддержки решений, системы
основанные на знаниях, экспертные
системы
• Обработка сигналов, фильтрация и т.д.
23. ЧАСТЬ 1 МЕТОДЫ ОПТИМИЗАЦИИ
ИУС24. Основные определения
1. Оператор, отображение, функцияОднозначность
f
f
A
A
B
B
2. Функционал – частный случай функции
ИУС
A
R -множество вещественных
чисел
A
f
R
25. Постановка задачи
Задача 1.Найти u* (минимизатор) :
u* U, J(u*) J(u), u U
J
J
min
min
ИУС
U
u
U
u
26.
Задача 2. Найти минимизирующуюпоследовательность {u k },
uk U :
lim J(u ) = inf J(u), k
k
J
ПРИМЕР.
ИУС
J = exp(u)
u
а) МИНИМИЗАТОР НЕ СУЩЕСТВУЕТ (задача 1 не
имеет смысла)
б) inf J(U) СУЩЕСТВУЕТ И РАВЕН НУЛЮ
27. Сходимость и некорректность
Сходимость по аргументу: lim u = u*, k(если u* существует)
Сходимость по функционалу: lim J( uk ) = inf J(u),
J
ПРИМЕР.
u*=0
k
Из 1 следует 2
но не наоборот
ИУС
k
k
u
{u = k}- сходится по функционалу
и расходится по аргументу
28. Когда нужна сходимость по аргументу?
1. Задачи аппроксимацииПРИМЕР : задача оптимального проектирования
x1
x2
xn
Объект
проектирования
ИУС
J(x)
min
x
J(x)
x D
29.
Точки X1 X2 одинаковохороши по критерию J
J
J(x)
X1
X2
min
x
D
ИУС
Во множестве D выполняются все функциональные
ограничения (спецификации)
Достаточно сходимости по функционалу !
30. 2. Задачи идентификации
• Возникают, когда нас интересует именно u*, азначение J(u) лишь косвенно отражает степень
приближения к минимизатору
• Основная цель – хорошая оценка u*
• Обычно полученная оценка u* используется далее в
других математических моделях, не связанных с
функционалом J(u)
• ПРИМЕР : оптимизация процесса полимеризации
• ЗАДАЧИИУС
ИДЕНТИФИКАЦИИ НА ПРАКТИКЕ
ВОЗНИКАЮТ ЗНАЧИТЕЛЬНО РЕЖЕ ЧЕМ
ЗАДАЧИ АППРОКСИМАЦИИ , И НАС ОБЫЧНО
ИНТЕРЕСУЕТ СХОДИМОСТЬ ПО
ФУНКЦИОНАЛУ !