|
|
Предмет и основные подходы ТПРСтр 1 из 3Следующая ⇒ Предмет и основные подходы ТПР Подходы: 1) Дескриптивный — выявл-е ограничений и возможностей людей в ходе прин решений 2) Нормативный — выявление самого рационального решения(сложн расчеты) 3) Прескриптивный — не гарантир нахожд наилучш. решения, но наход реш-е без противор-й.
Этапы процесса ПР 1)Предварительный анализ проблем: 1) Определение цели 2) Уровень рассмотрения задачи 3) Элементы и структура 4) Используемые ресурсы и критерии качества функционирования 5) Основные ограничения и противоречия 2) Постановка задачи принятия решения 1) Формулирование задачи 2) Определение типа задачи 3) Определение множества вариантов 4) Определение критериев выбора 5) Определение метода решения задачи 3) Получение исходных данных 1) Определение способа измерения вариантов 2) В качестве источников информации могут выступать: - статистические данные - результаты имитационного или матем. моделирования - результаты экспертного оценивания 4) Решение задачи с использованием выбранных методов, ВТ, экспертов 5) Анализ и интерпретация полученных результатов.
Классификация ЗПР <W,A,K,X,F,G,D,T> W – постановка задачи с точностью до модели решения A – множество допустимых вариантов или альтернатив (может быть закрытым или открытым) К – множество критериев выбора Х – множество методов измерения предпочтения F – отображение множества допустимых альтернатив на множестве критериев G – система предпочтения эксперта Т – резерв времени на принятие решений Традиционные классификации: 1) По виду отображения: Отображения: детерминированное, вероятностное, нечеткое в условиях определенности,в условиях риска, в условиях неопределенности. 2) По мощности множества К: К может содержать 1 элемент или несколько, соответственно задачи однокритериевые и многокритериевые. 3) По типу системы G задачи индивидуального и коллективного принятия решений.
В рамках этих классификаций выделяют: 1) ЗПР в условиях определенности 2) ЗПР в условиях риска
4 Принцип Парето (принцип единогласия). Оптимальным по Парето решением является такое решение X, что для решения Z, если кто-либо (хотя бы один участник коллектива) считает, что Z лучше X, то обязательно найдется кто-то другой, считающий, что X лучше Z. Принцип Парето означает, что поиск решения надо вести до тех пор, пока все единогласно не скажут, что X – оптимально. Для любого другого решения Z будет хотя бы один голос против. 5 Принцип равновесия Нэша. Определение принципа: существует ситуация, при которой принятие решения индивидуально отдельным ЛПР неэффективно для любого участника коллектива или сложившейся ситуации. Распределение соответствует принципу равенства, а само решение носит характер компромисса.
6 Принцип гарантированного результата (принцип минимакса). Принцип, используемый участниками, которые не хотят рисковать, а желают получить гарантированный результат. Т.е. при любом ходе, при любом варианте надо получить гарантированный результат независимо от действий другого игрока. Оптимальное решение(ния): e* =maxi minj eij Сначала для гарантии соглашаемся с наименьшим результатом, но затем от части компенсируем это, выбирая решение, для которого гарантированный результат максимален. Применение минимаксного критерия будет оправдано, если: 1) о возможности появления внешних состояний ничего не известно 2) приходится считаться с появл-м разл внешних сост-й 3) реш-е реализуется лишь один раз 4) необходимо исключить какой бы то ни было риск
7 Принцип Байеса предполагает, что игроку известно распределение вероятностей появления реакций системы. Знание распределения должно приводить к более объективному критерию выбора для данных условий. Наиболее объективной оценкой значения выигрыша для каждого варианта действий будет мат. ожидание. Применив это действие ко всем строкам, получим набор значений мат ожиданий, выбираем наибольшее из них: е = maxi ∑j eijqj. Геометрическое представление:
УТ – утопическая точка, РТ – рассматриваемая точка Все точки, лежащие в III квадрате хуже чем РТ, все точки, лежащие в I квадрате лучше РТ, хотя бы по одной координате. II и IV зоны неопределенности и выбор зависит от лица, принимающего решение. Uiг = P1Ui1 + P2Ui2 Решением будет ломаная линия. Ситуации применения: 1) Вероятности появл-я событий известны и не зависят от времени 2) Решение реализ-ся бесконечно много раз 3) Для малого числа реализаций допускается некоторый риск
Классические критерии принятия решений · минимакс c* =maxi minj cij · азартного игрока c* =maxi maxj cij · Байеса-Лапласса c* = maxi summ(j=1,n) qjeij · Сэвиджа c* = minimaxj (maxiaj — aj); aij = ci*-cij ; ci* - макс значение в столбце
Основные понятия сетевых моделей. Путь — непрерывная последовательность ребер, соединяющая две вершины Цикл — путь, у которого начальная и конечная вершины совпадают Дерево – граф, в котором нет циклов. Остовное дерево — дерево, в котором участвуют все вершины исходного графа Разрез на графе — это такой набор ребер, удаление которых приводит к разделению графа на два несвязных подграфа Рассматриваются следующие виды задач: 1) построение сети газопроводов с минимальной стоимостью 2) проложение кратчайшего маршрута между двумя узлами по существующей сети, по существующей метрике. 3) определение макс. пропускной способности сети трубопроводов заданной конфигурации. 4) определение потока максимальной пропускной способности и наименьшей стоимости. 5) составление временного графика выполнения работ.
Метод Форда-Фалкерсона. Перебор сквозных путей от истока к стоку с вычислением пропускных способностей этих путей. (Сij, Cji) – текущая или остаточная пропускная способность; (неСij, неCji) - начальная Шаг 1: Для всех ребер положим остаточную пропускную способность равной первоначальной пропускной способности. (Сij, Cji) = (неСij, неCji). Для начального узла: [∞, -]; i=1 Шаг2: Определяем множество Si, как множество узлов j, в который можно будет перейти из узла i с положительной остаточной пропускной способностью, т.е. Cij>0 Если Si ≠ Ø, то выполняем ш3, иначе переходим к ш4. Шаг 3: на множ-ве Si выбираем k, такое, что Cik=max{Cij}
Если k=n, то сквозной путь найден, переходим к ш5, иначе присваиваем i=k и переходим к ш2. Шаг 4: (откат назад) Если i=1, то сквозной путь невозможен → Шаг 6 Если i!=1, то вводим узел r (узел, предшеств i).Удаляем узел i из множ-ва Sr, полагаем i=r и →ш2 Шаг 5: (Определение остаточной сети) Np={ 1,k1,k2,…, n } исток сток Np – множество узлов, входящих в p-ый сквозной путь от истока к стоку n. Тогда максимальный поток, проходящий по этому пути определяется:
Остаточные пропускные способности ребер, составляющих сквозной путь уменьшаются на величину fp в направлении движения потока и увеличения на эту же величину в обратном направлении. Полагаем i=1 → ш2 Шаг 6: Решение При m найденных сквозных путях макс поток определяется следующим образом: Оптимальный поток через ребро (i,j) определяется: а) m б)
20 Динамическое программирование. Рекуррентные алгоритмы прямой и обратной прогонки. ДП находит оптим решение n-мерной задачи путем декомпозиции на n этапов, каждый из котор представ собой задачу от 1 переменной. Эти задачи должны быть связаны между собой общим условием. Вычисления выполняются рекурентно. Решение одной подзадачи явл исходными данными для другой. Решив последнюю получим оптим решение. Для решения задач динамического программирования необходимо сформулировать следующие основные элементы задачи: 1. Этапы и подзадачи 2. Множество вариантов решений для каждого этапа 3. Состояние для каждого этапа и его возможное значение 4. Управляющая функция 5. Рекуррентное выражение
Два метода: прямой и обрат прогонки. Рекурентные вычисления производятся от начальной вершины до конечной, а выписывание оптимального решения проиходит в обратном порядке. Как правило в задачах ДП используется алгоритм обратной погонки.
21 Задача о загрузке. W-вместимость,m-количество,r-прибыль,w-вес. Xi-суммарный вес грузов, загруж на этапах i..n xi=0..W, ui(mi) = rimi; Максимизиров z=sum(i)r(i)m(i), sum(i)w(i)m(i)<W, m>=0 и целые 1. Этап - предмет i наименования 2. Варианты решения описываются количеством mi в диапазоне [0,W/wi] 3. Состояние - суммарный вес. 4. fi(xi)=max{rimi+f(i+1)(xi-wimi)}
22 Задача планирования рабочей силы Осн-ые эл-ты: 1) n — количество периодов 2) bi — минимальное кол-во исполнителей, требующихся на i этапе 3) xi — кол-во исполнителей; xi >= b 4) xi-1 — кол-во реально работавших на предыдущем этапе 5) три вида затрат: а) C1(xi-bi) — затраты, связанные с избытком рабочей силы б) C2(xi-xi-1) — затраты на найм рабочих в) C3(xi-1-xi) — затраты при увольнении C2 и С3 не могут быть одновременно ненулевыми ui(xi) = C1(xi-bi) + C2(xi-xi-1) + C3(xi-1-xi) 6) fi(xi-1) = max {ui(xi)+fi+1(xi)}, i = 1..n В данном случае сложной явл-ся ф-ия управления
23 Задача замены оборудования n лет, r(t) прибыль, c(t) затраты на обслуж, s(t) стоимость аппарата t летнего, I стоимость нового. 1.Этап - год 2.Варианты - заменить, продолжить эксплуатацию 3.Состояние - t(возраст) механизма 4. ui=r(t)-c(t), если ПЭ ui=S(t)-I+r(0)-c(0), если З 5.fi(t)=ui+fi+1(t+1), ПЭ fi(t)=ui+fi+1(1), З Сложная ф-ия управления
24. Обобщённая модель управления запасами. Природа задчи управ запас определяется неоднократным размещением и получением завасов заданного объема продукции, которая при поступлении носит название хранимый запас. И размещение заказов проход в определенный момент времени. С этой точки зрения стратегия упраления запасами сводится к вопросам: 1. Какое количество заказывать 2. Когда заказывать. Экономический размер заказа явл ответом путм минимиз функции затрат: Сумарные затраты: -затраты на приобретение (цена может ыть простой и со скидкой) -затраты на оформление заказа(не завистя от объема заказа - постоянные расходы) -затраты на хранение -потери от дефицита(потенциальные потери, субьектив факторы) Система управления запасами: с непрер и период контролем. Непрер — момент заказа совпадает с началом или оконч цикла. Период — момент заказа определяется заранее заданным уровнем. 25 Классическая задача управления запасами. -спрос постояный -мгновенное пополнение заказа и в полном объеме -отсутсвие дефецита y - объем заказа D - объем спроса t0 - продолжительность цикла заказа Заказ объема у единиц размещается и по-полняется мгновенно, когда уровень запаса равен нулю. Затем запас равномерно расходу-ется с постоянной интенсивностью спроса D. Продолжительность цикла заказа для этого примера равна t0=y/D Средний уровень запаса определяется соотношением y/2 Оптимальная стратегия: Заказывать y*=Sqrt(2KD/h) через каждые t*=y*/D
Пополнение может быть не мгновенно.Срок выполнения заказа - L. Пополение, когда уровень опускается до R=LD единиц. Если L>t0, то вычисл Le=L-nt0; R=LeD;
26. Задача экономичного размера заказа с разрывами цен. В данном случае продукция может быть приобретена со скидкой. с - стоимость еденицы продукции. с=с1, если y<=q и c2 если y>q (с1>c2) Затраы на приобретение в еден времени - c1y/t0=c1y/(y/D)=Dc1, при y<=q и Dc2 при y>q Общие затраты в единицу време-ни TCU(y)=Dc1+KD/y+hy/2 при y<q и Dc2+KD/y+hy/2 при y>q Q — такой объем заказа, при котором выигрыш от скидки компенсир избыточн затратами на хранение.Вычисл ym=Sqrt(2KD/h) 1) Если q<=ym или q>=Q, то выгодно заказывать y*=ym, Иначе Ш2 2) Если ym < q < Q, то y*=q
27. Многопродуктовая статическая модель управления запасами с ограничением вместимости h различных товаров, котор хранятся на складе ограниченной вместимости. Предполагаем, что дефицит отсутствует. Поплнение запаса производится мгновенно Товары конкурируют между собой за ограниченное складское пространство. Di — интенсивность спроса Ki — стоимость размещения заказа hi — стоимость хранения единицы товара в единицу времени уi — объем заказа ai — необходимое пространство для хранения единицы товара А — максимальное складское пространство для хранения товаров п видов. Минимиз TCU=Sum(i)(KiDi/yi + hiyi/2) при ограничен Sum(i)aiyi<=A
Ш1 Вычислить без учета вместимости ym=Sqrt(2KiDi/hi) Ш2 Проверить на ограничение вместимочти, если не удовл Ш3 Ш3 Использется метод мн-на Лагранжа L=TCU(y1,y2,..yn)-lamda(Sum(i)aiyi-A); lambda<0 Т.к. ф-ция Лагр выпукл, то ищем экстремум по производ dL/dyi=-KiDi/(y^2)+hi/2-lamda*ai=0 dL/dlambda=-Sum(i)(aiyi)+A=0
y*=Sqrt(2KD/(h-2lamda*ai)) Дискретно уменьшая lambda получем решение (знач-я переменных должны удовл ограничениям)
28. Динамическая модель управления запасами при отсутствии затрат на оформление Типичный пример - задача календарного планирования производства, расчитанного на n равных периодов. При ограничении на возможности производства на каждом из периодов, т.е. производство может включать несколько уровней: -выпуск основной продукции -допол вр. -заказ на стороне. Осн-ые положения модели: 1. Осутсвуют затраты на оформление 2. Отсутсвует дефецит 3. Стоимость произвоства ед. продукции либо постоянно либо имеет возрастающий характер. 4. Стоимость хранения постоянна Рассматривая задачу n этапного планирования можно сформулироваь в виде траспортной задачи с kn пунктами производства и n потрибителей. k - число уровней на протяжении перода. Производственные возможности каждого из уровней определяют объем поставок. Объем потребляения определяется спросом. Стоимость перевозки от n производителя до n пункта назначения определяется как сумма затрат на производство и стоимость хранения. Оптимальным решением такой транспортной задачи будет объем производства продукции для каждого уровня каждого периода min сумарных затрат на производство и хранение.
29. Динамическая модель управления запасами с затратами на оформление заказа. Дефицита нет Спрос переменный, но известный Затраты на оформление заказа учитываются всякий раз, когда начинается производство новой партии продукции zi — количество заказанной продукции (объем заказа), Di — потребность в продукции (спрос), xi — объем запаса на начало этапа i Кi — затраты на оформление заказа, hi — затраты на хранение единицы продукции, переходящей из этапа i в этап i + 1. Ф-ция производ затрат для этапа i: Ci(zi)=(0, если zi=0 и Ki+ci(zi) если zi>0), где ci(zi)-ф-ция предель производ затарат Т.к. дефицита нет, задача сводится к нахождению значений zi, мин-щих суммарные затраты, связанные с размещением заказов, закупкой и хран продукции на протяжении п этапов. Затраты на хран на i этапе предпол пропорц величине xi+1=xi+zi–Di,котор представ собой объем запаса, переходо из этапа i в этап i + 1. Применяется метод прямой прогонки. В качестве состояния берем xi+1, такое что 0<xi+1<Di+1+...+Dn. Это неравенство означает, что в предельном случае запас xi+1 может удовлетворить спрос на всех последующих этапах. Пусть fi(xi+l) — мин общие затраты на этапах при заданной велич запаса xi+l на конец этапа i. Тогда fi(xi+1)=min{Ci(zi)+hix(i+1)+f(i-1)(xi+1+Di-zi)} при 0<=Zi<=Di+xi+1
Медиана Кемени Медиана Кемени — такое ранжирование, которое обладает минимальным суммарным расстоянием до всех индивид-х ранжировнаий. Для опред-я расстояния воспользуемся след представлением Rк = [rij] rij=(2, если ai>aj; 1, если ai~aj; 0, если aj>ai) При этом должно выполняться условие транзитивности Различие в матрицах можно представить в колич форму и такую разность можно считать веществ ф-ей расстояний. Такая ф-ия должна обл-ть однозн и неотриц знач-ми для любой пары Rk Rc d (Rk, Rc) R* summ(k=1,m) d(Rk, R*) = min sum(k=1,m) d(Rk, R); d(Rk, Rc) = sum(i<j, m) |rijk-rijC| (*) Сов-ть нек-го мно-ва эл-тов и расст-я м/у ними — метрич пространство. Три аксиомы для составл-я метр простр: 1) d(Rk, Rc) >=0 2) d(Rk, Rc) = d(Rc, Rk) 3) d(Rk, Rc) <= d(Rk, Rs) + d(Rs, Rc) 4) d(Rk', Rc') = d(Rk, Rc) 5) Если 2 ранжи-я отлич друг от друга только на части объектов, то расст-я м/у исх ранжир-ми равно расст-ю м/у этими объектами 6) Миним-е расст-е м/у двумя несовпад ранжир-ми равно 1 Доказано, что расст-е (*) явл-ся единств, которое удовл-ет всем шести аксиомам.
Построение медианы Кемени Рассм алг-м вычисл-я медианы Кемени на основе матрицы потерь [Cij] размера nxn Cij=summ(k=1,m) | rijk — rij^ |; rij^=(1, если i!=j; 0, иначе) Расст-е м/у двумя ранжир-ми опр-ся как сумма наддиагональных эл-в всех ранжир-й summ(i<j)Cij = summ(k=1,m)summ(i<j,n) | rijk — rij^ | Переход к другому порядку приводит к изменению порядка следования и к перестановке строк и столбцов в матр потерь => получаем другую сумму наддиаг эл-тов, т.е. др расстояние. Общая идея алгоритма:: Строится исходная матрица потерь. Вычисл. суммы эл-в строк этой матрицы, на I место ставится эл-т с наименьш суммой. Строка и столбец этого эл-та удаляются из матрцы. Процедура повтор для след эл-та вплоть до исчерпания матрицы. Cikik+1 <= Cik+1ik; ik,ik+1- сосед эл-ты в ранжир-ии Если для какой-то пары это усл-е не выполняется, то объекты меняются местами.
Предмет и основные подходы ТПР Подходы: 1) Дескриптивный — выявл-е ограничений и возможностей людей в ходе прин решений 2) Нормативный — выявление самого рационального решения(сложн расчеты) 3) Прескриптивный — не гарантир нахожд наилучш. решения, но наход реш-е без противор-й.
Этапы процесса ПР 1)Предварительный анализ проблем: 1) Определение цели 2) Уровень рассмотрения задачи 3) Элементы и структура 4) Используемые ресурсы и критерии качества функционирования 5) Основные ограничения и противоречия 2) Постановка задачи принятия решения 1) Формулирование задачи 2) Определение типа задачи 3) Определение множества вариантов 4) Определение критериев выбора 5) Определение метода решения задачи 3) Получение исходных данных 1) Определение способа измерения вариантов 2) В качестве источников информации могут выступать: - статистические данные - результаты имитационного или матем. моделирования - результаты экспертного оценивания 4) Решение задачи с использованием выбранных методов, ВТ, экспертов 5) Анализ и интерпретация полученных результатов.
Классификация ЗПР <W,A,K,X,F,G,D,T> W – постановка задачи с точностью до модели решения A – множество допустимых вариантов или альтернатив (может быть закрытым или открытым) К – множество критериев выбора Х – множество методов измерения предпочтения F – отображение множества допустимых альтернатив на множестве критериев G – система предпочтения эксперта Т – резерв времени на принятие решений Традиционные классификации: 1) По виду отображения: Отображения: детерминированное, вероятностное, нечеткое в условиях определенности,в условиях риска, в условиях неопределенности. 2) По мощности множества К: К может содержать 1 элемент или несколько, соответственно задачи однокритериевые и многокритериевые. 3) По типу системы G задачи индивидуального и коллективного принятия решений.
В рамках этих классификаций выделяют: 1) ЗПР в условиях определенности 2) ЗПР в условиях риска
4 Принцип Парето (принцип единогласия). Оптимальным по Парето решением является такое решение X, что для решения Z, если кто-либо (хотя бы один участник коллектива) считает, что Z лучше X, то обязательно найдется кто-то другой, считающий, что X лучше Z. Принцип Парето означает, что поиск решения надо вести до тех пор, пока все единогласно не скажут, что X – оптимально. Для любого другого решения Z будет хотя бы один голос против. 5 Принцип равновесия Нэша. Определение принципа: существует ситуация, при которой принятие решения индивидуально отдельным ЛПР неэффективно для любого участника коллектива или сложившейся ситуации. Распределение соответствует принципу равенства, а само решение носит характер компромисса.
6 Принцип гарантированного результата (принцип минимакса). Принцип, используемый участниками, которые не хотят рисковать, а желают получить гарантированный результат. Т.е. при любом ходе, при любом варианте надо получить гарантированный результат независимо от действий другого игрока. Оптимальное решение(ния): e* =maxi minj eij Сначала для гарантии соглашаемся с наименьшим результатом, но затем от части компенсируем это, выбирая решение, для которого гарантированный результат максимален. Применение минимаксного критерия будет оправдано, если: 1) о возможности появления внешних состояний ничего не известно 2) приходится считаться с появл-м разл внешних сост-й 3) реш-е реализуется лишь один раз 4) необходимо исключить какой бы то ни было риск
7 Принцип Байеса предполагает, что игроку известно распределение вероятностей появления реакций системы. Знание распределения должно приводить к более объективному критерию выбора для данных условий. Наиболее объективной оценкой значения выигрыша для каждого варианта действий будет мат. ожидание. Применив это действие ко всем строкам, получим набор значений мат ожиданий, выбираем наибольшее из них: е = maxi ∑j eijqj. Геометрическое представление:
УТ – утопическая точка, РТ – рассматриваемая точка Все точки, лежащие в III квадрате хуже чем РТ, все точки, лежащие в I квадрате лучше РТ, хотя бы по одной координате. II и IV зоны неопределенности и выбор зависит от лица, принимающего решение. Uiг = P1Ui1 + P2Ui2 Решением будет ломаная линия. Ситуации применения: 1) Вероятности появл-я событий известны и не зависят от времени 2) Решение реализ-ся бесконечно много раз 3) Для малого числа реализаций допускается некоторый риск
  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...  Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
.
Эти разности дожны быть одинаковы по модулю. Напр-е потока определяет положительная разность
