18 Условие дополняющей нежесткости для транспортной задачи

1) если i-й ресурс расходует не весь (с остатком) ==> оценка i-ресурса ≥0 (a₁₁x₁+ …+a_1nx_n<b₁)

2) если оценка > 0 ==> ресурс тратится весь

3) если x_j^*>0 , тогда оценка всех ресурсов = цене реализации

A₁₁U₁+….+A_m1U_m=C₁

4) если суммарная оценка вложенных ресурсов > цены реализации, то x_j=0 производство невыгодно.

19 Условия при которых задача относится к динамическому программированию

1 сепарабельность (разделимость)

Мультипликативная (функция зависит он n элементов) f(x₁…x_n)=f₁(x₁)*f₂(x₂)…….*f_n(x_n)

Аддитивная (функция зависит он n элементов) f(x₁…x_n)= f₁(x₁)+……+f_n(x_n)

2 Структурные ограничения простые, их количество не большое (1,2)

20 Уравнение состояния Беллмана

принципа оптимальности Беллмана: каково бы ни было состояние системы перед очередным шагом, необходимо выбирать управление на этом шаге так, чтобы доход на данном шаге вместе с оптимальным доходом на всех последующих шагах был максимальным.

состоит в том что оптимальное управление строится постепенно. На каждом шаге оптимизируется управление только этого шага. Вместе с тем на каждом шаге управление выбирается с учётом последствий, так как управление, оптимизирующее целевую функцию только для данного шага, может привести к неоптимальному эффекту всего процесса.

21 Общий вид Уравнения Бэллмана

22 Уравнение состояния Беллмана

Состояние на определенном шаге будет зависеть от состояния системы в предыдущий момент времени и выбранного управления X_k

23 Уравнение Бэллмана для задачи распределение ресурсов

N – количество потребителей

Q – начальное количество ресурсов распред между n потребителями, каждый дает эффективность Fk в зависимости от выделенных средств Xk

Распределить средства с максимальной эффективностью

24 Уравнение Бэллмана для задачи о рюкзаке

N – предметов

Q – вместимость рюкзака

d_i – вес предмета i-го типа

c_i – эффективность предмета i-го типа

i=1….n

x_i – количество экземпляров i-го вида

альтернатив модель x=1 ,берем x=0 не берем

L= c₁x₁+…..+ c_nx_n → max

d₁x₁+….+d_nx_n ≤ Q

x_i≥0 , целые

X_k- количество предметов к-го типа

25 Уравнение Бэллмана для задачи о пожаре

N – предметов

c_i – эффективность(ценность) предмета i-го типа

i=1….n

x_i –i-й предмет

x=1 ,берем

x = 0 не берем

L= c1x1+…..+ cnxn -> max

x₁+….+x_n ≤N

x_i≥0 , целые

27 Уравнение Бэллмана для задачи о замене оборудования

N – периодов эксплуатации оборудования

R_i – затрата на эксплуатации оборудования возраста i

C_i – эффективность оборудования возраста i

P₀ – стоимость нового оборудования

Ѱ_i – ликвидная стоимость оборудования возраста i

i=1….n

Принять в конце каждого из периодов эксплуатации n менять или не менять оборудование, чтобы суммарная эффективность была максимальной.

Решение о замене принимается в начале К этапа

В начала эксплуатации оборудование новоге (t=0)

28 Определение смешанной стратегии (чистой стратегии) при решении матричной игры

Седловая точка должна отсутствовать.

Седловая точка – это пара оптимальных стратегий (A_i, B_j). В этом случае число a=b называется (чистой) ценой игры (нижняя и верхняя цена игры совпадают). Это означает, что матрица содержит такой элемент, который является минимальным в своей строке и одновременно максимальным в своем столбце.

Вкратце: Смешанной стратегией игрока называются случайные величины, возможные значения которых являются чистые стратегии.

Смешанная стратегия состоит из чистых стратегий и соответствующих им вероятностей. Сумма вероятностей для игрока равна 1. Применение игроком чистой стратегии – частный случай смешанной стратегии.

Смешанная стратегия игрока - это полный набор применения его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями.

• игроки используют случайную смесь чистых стратегий с заданными вероятностями;

• игра многократно повторяется в сходных условиях;

• при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком;

• допускается осреднение результатов игр.