Классические критерии принятия решений

_· минимакс c* =max_i min_j c_ij

_· азартного игрока c* =max_i max_j c_ij

_· Байеса-Лапласса c* = max_i summ(j=1,n) q_je_ij

· Сэвиджа c* = min_imax_j (max_ia_j — a_j); a_ij = c_i^*-c_ij ; c_i^* - макс значение в столбце

Производные критерии принятия решений

· Критерий Гурвица C* = max_i (alpha min_j C_ij + (1-alpha) max_j C_ij ); alpha — коэфф оптимизма/пессимизма

· Критерий Лемона C* = max_i (v summ(j=1,n) C_ijq_j + (1-v) min_j C_ij); v — весовой множитель

· Критерий произведений С* = max_i (П(j=1,n) C_ij ), const = x₁x₂; х могу включаться в формулу с разными степенями

Транспортная модель. Основные требования.

Исходно эти модели описывали перемещение или перевозку груза из пунктов отправления в пункты назначения. В задаче считаются известными:

1) емкость пункта отправления

2) потребность в пунктах назначения

3) Стоимость перевозки груза из пункта отравления в пункт назначения

Стоимость приведена к единице груза.

Надо найти такой объем перевозки, который приводит к минимальным суммарным затратам на перевозки. Исходные данные удобно представить в таблице, строки которой соответствуют пунктам отправления, а столбцы – пунктам назначения.

Основное требование – сбалансированность спроса и предложения, т.е. summ(i) a_i = summ(j) b_j

Если не выполняется, то вводим фиктивный пункт отпр/назнач, которому припис разница a_i и b_j

Ограничения: summ(j=1,n) Xij <= a_i; summ(j=1,n) Xij >= b_j;

Основные понятия сетевых моделей.

Путь — непрерывная последовательность ребер, соединяющая две вершины

Цикл — путь, у которого начальная и конечная вершины совпадают

Дерево – граф, в котором нет циклов.

Остовное дерево — дерево, в котором участвуют все вершины исходного графа

Разрез на графе — это такой набор ребер, удаление которых приводит к разделению графа на два несвязных подграфа

Рассматриваются следующие виды задач:

1) построение сети газопроводов с минимальной стоимостью

2) проложение кратчайшего маршрута между двумя узлами по существующей сети, по существующей метрике.

3) определение макс. пропускной способности сети трубопроводов заданной конфигурации.

4) определение потока максимальной пропускной способности и наименьшей стоимости.

5) составление временного графика выполнения работ.

Алгоритм нахождения минимального остовного дерева.

В графе с нагруженными дугами можно выделить минимальное остовное дерево как остовное дерево с минимальным суммарным значением нагруженных величин.

шаг 0: С0 = Ø, неС0=N

шаг 1: выбираем любой i узел из множества неС0, переносим в множество С1.

С1 ={1}, С1=N-{i}; k=2

шаг k:неCk-1выберем узел j*, который соединен самой короткой дугой с множеством узлов: Ск-1.

Ск = Ск-1 + {j*}; неСк = неСк-1 - {j*}; если неСк!= Ø, то k=k+1 (повтор осн шаг k)

16 Алгоритм Дейкстры нахождения кратчайшего пути.

Позволяет найти путь между 2 заданными узлами.

Ш0 Исходный узел присваев метка [0,-]. i=1

Шi Вычислить временные метки [ui+dij,i] для всех узлов j, которые можно достичь из узла i и котор не имеют постоянных меток. Если узел j уже имеет временную метку, полученную от другого узла k и если ui+dij<uj, то заменить метку [uj,k] на [ui+dij,i]

Если все узлы имеют постоянные метки то конец. Иначе выбираем метку [u_r, S] с мин растоянием среди временных меток. Полагаем i=r. Повтор шага i.

Алгоритм Флойда нахождения кратчайшего пути

Позволяет нати путо между любыми 2 узлами одновременно.

D — м-ца расстояний, S — м-ца узлов

М-ца D строится: В строке i, столбце j пишется dij, кот-ый приписывается ребру i, если это ребро есть в графе

Ш0. D0, S0, k=1;

Шk. Задается k как ведущая строка и столбец. Для всех эл-в м-цы, не входящих в эту строку и столбец проверяем условие dik+dkj < dij (i!=j; j!=k; i!=k)

Если выполняется, то

а) формир м-цу Dk из Dk-1 путем замены dij на сумму dik+dkj

б) Sk из Sk-1; Sij=k; k=k+1; Если k<n, то повторяем шаг k

Такая схема исп-ся в маршрутизаторах, IP-сетях, при маршрутизации источника.

18. Задача о максимальном потоке.

Задана сеть опред-й конфигурации. Для каждого участка известны пропускные способности. Решением такой задачи является опред-е максимального потока, который можно передать м/у 2 заданными узлами. Требования: один источник и один сток.

Для реш-я предложено множество алг-в, которые делятся на 2 группы:

1) Базируются на построении и переборе разрезов

2) Основан на выдел путей с положит пропускной способностью от истока к стоку

Разрезом считается такой набор ребер, который полностью прекращ поток от истока к стоку.

Алгоритмы перебора разрезов не эффективны с вычисл точки зрения

Метод Форда-Фалкерсона.

Перебор сквозных путей от истока к стоку с вычислением пропускных способностей этих путей.

(С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, u_i(m_i) = r_im_i;

Максимизиров 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) x_i-1 — кол-во реально работавших на предыдущем этапе

5) три вида затрат:

а) C₁(xi-bi) — затраты, связанные с избытком рабочей силы

б) C₂(x_i-x_i-1) — затраты на найм рабочих

в) C₃(x_i-1-x_i) — затраты при увольнении

C₂ и С₃ не могут быть одновременно ненулевыми

u_i(x_i) = C₁(xi-bi) + C₂(x_i-x_i-1) + C₃(x_i-1-x_i)

6) f_i(x_i-1) = max {u_i(x_i)+f_i+1(x_i)}, 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+f_i+1(t+1), ПЭ

fi(t)=ui+f_i+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 этапе предпол пропорц величине x_i+1=xi+zi–Di,котор представ собой объем запаса, переходо из этапа i в этап i + 1.

Применяется метод прямой прогонки.

В качестве состояния берем x_i+1, такое что 0<x_i+1<Di+1+...+Dn.

Это неравенство означает, что в предельном случае запас x_i+1 может удовлетворить спрос на всех последующих этапах.

Пусть fi(xi+l) — мин общие затраты на этапах при заданной велич запаса x_i+l на конец этапа i.

Тогда fi(xi+1)=min{Ci(zi)+hix(i+1)+f(i-1)(xi+1+Di-zi)} при 0<=Zi<=Di+x_i+1

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: