Курс, 2 семестр Лектор: Кочетов Юрий Андреевич icon

Курс, 2 семестр Лектор: Кочетов Юрий Андреевич


Смотрите также:
Дискретная математика Часть 2 Кочетов Юрий Андреевич...
Спецкурс 1 Интегрированные информационные системы (специальность: прикладная математика и...
Программа курса физики для студентов геологического факультета (вечернее отделение)...
Программа курса Политология (пятый семестр) Лектор : Валерий Георгиевич Ледяев Преподаватель...
Программа курса История экономической мысли (6 семестр)  Лектор:  академик Энтов Револьд...
Программа курса Экономическая история (Шестой семестр) Лектор: Рустем Махмутович Нуреев...
Юрий Андреевич Андреев Исцеление человека....
Календарный план учебных занятий по дисциплине «Аналитическая геометрия» (НМ), II семестр...
Программа курса Экономическая история (Шестой семестр) Лектор: Рустем Махмутович Нуреев...
Зоологии возглавил профессор Виктор Андреевич Фаусек. Кроме него в штате кафедры были лаборант...
Учебная программа рассмотрена и рекомендована к утверждению на заседании департамента Философии...
Программа спецкурса “Динамика излучающей плазмы” 5 курс, 523 группа...



Загрузка...
скачать


Теория принятия решений

НГУ

Факультет информационных технологий

3 курс, 2 семестр


Лектор: Кочетов Юрий Андреевич


http://www.math.nsc.ru/LBRT/k5/or.html

Теория принятия решений

Исследование операций — теория математических моделей и методов принятия решений.

  1. Наличие некоторого процесса

  2. Наличие управляющих воздействий

  3. Наличие цели, ради которой проводится операция

  4. Выбор наилучшего (оптимального) управления, при котором достигается цель

Операция — система действий, объединенная единым замыслом и направленная на достижение определенной цели.

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



Построение математической модели


Поиск оптимальных решений


Корректировка

модели


^ Реальная задача

Выдача рекомендаций


Схема исследования


Математическая модель

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

Математическая модель описывает исследуемую систему и позволяет выразить ее эффективность в виде целевой функции

W = f(X,Y),

где X = (x1,…, xn) — управляемые переменные,

Y = (y1,…, ym) — неуправляемые переменные (исходные данные).

Связь между переменными X и исходными данными Y выражается с помощью ограничений

 (X, Y)  0.

Модели принятия решений



  1. Долгосрочное стратегическое планирования:

задачи размещения производства, развитие нефтяной и газовой промышленности

  1. Среднесрочное планирование:

транспортные задачи, задачи маршрутизации, задачи календарного планирования с ограниченными ресурсами

  1. Оперативное управление:

задачи теории расписаний, задачи раскроя и упаковки


Задачи размещения производства


Системы сотовой связи, филиалы банков, производство продукции


Транспортные задачи


Потребители





Транспортные затраты









Предприятия






Минимизировать затраты на перевозку продукции


^ Задачи маршрутизации












Найти маршрут минимальной длины


^ Задачи теории расписаний


Графики движения поездов, рабочие бригады, ремонт составов


^ Задачи раскроя и упаковки








Раскрой пиломатериала, листового железа, станки с ЧПУ


Матричные игры


Pij

вероятность поражения


Системы поддержки решений


Интерфейс пользователя

Лицо, принимающее решение


Распределительная задача

Имеем

n — число предприятий;

Y — количество единиц некоторого ресурса;

fk(x) — количество продукции, которое будет произведено на k-м предприятии, если в него будет вложено x единиц ресурса (монотонно неубывающая функция).

Требуется: максимизировать объем продукции

f1(x1) +…+ fn(xn)  max

(1)

x1 +…+ xn Y

(2)

xi  0, целые, i = 1,…n.

(3)



Идея динамического программирования (ДП)



Метод ДП (Р. Беллман, В.С. Михалевич, Н.З. Шор ) можно трактовать как алгоритмическую версию рассуждений по индукции.

Пусть sk(y), 1 £ k £ n, 0 £ y £ Y, — оптимальное значение целевой функции задачи (1) – (3), где n заменено на k, Y заменено на y.

Требуется найти sn(Y) и набор переменных, на котором достигается это значение.

ТЕОРЕМА 1. Пусть f1, … , fn ­— монотонно неубывающие функции. Тогда справедливы следующие рекуррентные соотношения:

s1(y) = f1(y), 0 £ y £ Y;

(4)

sk(y) = max {sk-1(y - x) + fk(x) | 0 £ x £ y}, 2 £ k £ n, 0 £ y £ Y,

(5)



Доказательство: Соотношение (4) очевидно. По определению

sk(y) ³ max {sk-1(y - x) + fk(x) | 0 £ x £ y}.

Пусть теперь — такой вектор, что и

.

Поскольку имеем

.

Алгоритм ДП вычисляет множество Sk = {sk(y) | 0  y  Y}, k =1,…,n с помощью соотношений (4) и (5), где на каждом шаге оптимизируется ровно одна переменная.



Процесс вычисления S1,…,Sn называется прямым ходом алгоритма.

Число операций  Y 2n

Память  Y n .




y

S1(y)

S2(y)



Sn(y)

0













1













2




























Y










Sn(Y)



При обратном ходе алгоритма вычисляются значения , с учетом того, что уже известны Sk(y). Например, определяется из уравнения и так далее.

Число операций  Y n. Память  Y n.

Характеристики алгоритмов


Для оценки качества алгоритмов будем использовать два параметра:

TA трудоемкость (число элементарных операций алгоритма A);

ПА — требуемый объем памяти.

Элементарная операция — одна из арифметических операций: сложение, вычитание, умножение, деление или логическая операция сравнение двух чисел.

Нас будет интересовать зависимость параметров алгоритма от длины записи исходных данных задачи с точностью до порядка величин.


Пример: При Т = 3/2 n2 , будем писать T = O(n2) или T n2.


Полиномиальные алгоритмы


Определение. Алгоритм A называют полиномиальным, если его трудоемкость TA ограничена полиномом от длины записи исходных данных, то есть существует константа c > 0 и натуральное число k такие, что TA c Lk, где L — длина записи исходных данных.


Пример: Пусть fi (xi) = ai  xi, тогда ,

но TДП = O(Y2n), то есть алгоритм ДП не является полиномиальным.


Обобщим задачу (1)–(3):

f1(x1) +…+ fn(xn)  max

(1)

h1(x1) +…+ hn(xn) Y

(2)

aixi  0, целые, i = 1,…n.

(3)

Если hi(x) — целочисленные монотонно неубывающие функции,
то вместо (4)–(5) можно использовать следующие
рекуррентные соотношения:



s1(y) = f1(x* ), где x* = max{xa1 | h1(x)  y}, 0 £ y £ Y;

(4)

sk(y) = { fk(x) + sk-1(y - hk(x))}, 2 £ k £ n, 0 £ y £ Y.

(5)

Упражнение 1. Доказать справедливость соотношений (4)–(5).


Обратная задача — поиск наименьших затрат на получение заданного количества продукции:



h1(x1) +…+ hn(xn)  min

(6)

f1(x1) +…+ fn(xn)  D

(7)

aixi  0, целые, i = 1,…n.

(8)



Если fk(x) — целочисленные монотонно неубывающие функции, то для решения задачи (6)–(8) можно использовать идеи динамического программирования.


Пусть

Для 1 kn, 0  dD обозначим через tk(d) — оптимальное решение задачи (6)–(8), в которой n заменено на k, а D заменено на d.

Требуется найти tn(D).

Рекуррентные соотношения

0  dD,

(9)

tk(d) = min{tk–1(dfk(x)) + hk(x)| 0  xak, x},

k  2, 0  dD.

(10)

Упражнение 2. Доказать справедливость соотношений (9)–(10).

ТЕОРЕМА 2: Предположим, что D — наибольшее число, для которого оптимальное значение целевой функции задачи (6)–(8) не превосходит Y. Тогда оптимальное значение целевой функции задачи (1)–(3) равно D.

Доказательство: Пусть D удовлетворяет условию теоремы

и — соответствующее решение задачи (6)–(8).

Значит

и


Следовательно, D не превосходит оптимального решения D1 задачи
(1)–(3). Если бы D1 было больше D, то решение задачи (6)–(8), в которой D заменено на D1, тоже не превышало бы Y, что противоречит максимальности D.





Скачать 127.94 Kb.
оставить комментарий
Дата23.01.2012
Размер127.94 Kb.
ТипИсследование, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх