Сущность динамического программирования.

Динамическое программирование — раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений.

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

Сущность состоит в том, что строится такая вычислительная схема, когда вместо одной задачи со многими переменными строится много задач с малым числом переменных (обычно даже одной) в каждой. Это значительно сокращает объем вычислений.

Однако такое преимущество достигается лишь при двух условиях: когда критерий оптимальности аддитивен, т. е. общее оптимальное решение является суммой оптимальных решений каждого шага, и когда будущие результаты не зависят от предыстории того состояния системы, при котором принимается решение.

Это вытекает из принципа оптимальности Беллмана, лежащего в основе теории динамического программирования. Из него же вытекает основной прием — нахождение правил доминирования, на основе которого на каждом шаге производится сравнение вариантов будущего развития и заблаговременное отсеивание заведомо бесперспективных вариантов. Когда эти правила обращаются в формулы, однозначно определяющие элементы последовательности один из других, их называют разрешающими правилами. Несмотря на выигрыш в сокращении вычислений, их объем остается очень большим.

 

С-ядро.

С-ядро — принцип оптимальности в теории кооперативных игр, представляющий собой множество эффективных распределений выигрыша, устойчивых к отклонениям любой коалиции игроков, то есть множество векторов таких, что:

и для любой коалиции выполнено:

где v — характеристическая функция игры.

Свойства:

Эквивалентным является определение С-ядра кооперативной игры в терминах блокирования распределений выигрыша коалициями. Говорят, что коалиция K блокирует распределение выигрыша x, если найдётся другое распределение выигрыша y, такое, что

и для любого участника выполнено

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

 

41.Теорема Неймана. Решение игры 2*2 в смешанных стратегиях.

Предположим, что в не полностью определенной игре, заданной платежной матрицей m*n, найдено оптимальное решение, состоящее из двух оптимальных стратегий Р*=(р , р ,…, р ) и Q*=(q , q ,…, q ), где некоторые из компонент векторов р , р ,…, р и q , q ,…, q равны нулю, что означает, что не все стратегии, которые используются первым и вторым игроком, входят в его оптимальную стратегию.

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

Пример. Пусть задана смешанная стратегия:

Р=(р₁=0, р₂=0,5; р₃=0,2; р₄=0, р₅=0; р₆=0,7; p₇=0,3),

в этом случае активными являются вторая, третья и седьмая стратегии.

В теории игр большое практическое значение для нахождения оптимальных стратегий в не полностью определенных играх имеет следующая теорема об активных стратегиях: «Если один из игроков придерживается своей оптимальной стратегии, то его выигрыш остается неизменным и равным цене игры V, независимо от того, что делает другой игрок, если он не выходит за рамки своих активных стратегий».

Рассмотрим не вполне определенную игру 2*2.

Пусть задана платежная матрица игры Н

H=

В соответствии с теоремой Неймана данная игра должна иметь решение в смешанных стратегиях. (Поскольку в данном случае мы анализируем игру, размерность платежной матрицы которой 2*2, то обе чистые стратегии каждого из игроков будут являться активными, т.е. их вероятности будут отличны от нуля.)

Воспользуемся теоремой об активных стратегиях для нахождения решения этой игры, т.е. для нахождения оптимальных смешанных стратегий Р* и Q* и цены игры V. В соответствии с этой теоремой, если первый игрок придерживается своей оптимальной стратегии Р*, то математическое ожидание его выигрыша будет равно цене игры, какой бы активной стратегией при этом не пользовался второй игрок. Следовательно, математическое ожидание выигрыша первого игрока при применении им оптимальной стратегии Р*=(р , p ) будет равно цене игры и в том случае, когда второй игрок применяет свою первую чистую стратегию, и в том случае, когда второй игрок применяет свою вторую чистую стратегию, т.е. должны выполняться следующие соотношения:

h₁₁р +h₂₁p =V

h₁₂р +h₂₂p =V

р + p =1

Из данной системы уравнений определим р и p :

• приравнивая левые и правые части первых двух уравнений, получим:

h₁₁р +h₂₁p =h₁₂р +h₂₂p ; (2.5.4)

• преобразуя уравнение (2.5.4), получим:

р (h₁₁-h₁₂)= p (h₂₂-h₂₁); (2.5.5)

• используя третье уравнение (2.5.3), получим:

р =1-p

тогда

(1- p ) (h₁₁-h₁₂)= p (h₂₂-h_2l); (2.5.6)

• преобразуя уравнение (2.5.6), получим:

(h₁₁-h₁₂)-p (h₁₁-h₁₂)=p (h₂₂-h_2l),

(h₁₁-h₁₂)= p [(h₂₂-h_2l)+(h₁₁-h₁₂)],

p = (2.5.7)

Из соотношения (2.5.5) получаем:

р =

Цена игры будет равна:

V=

Транспортная задача.

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.[1][2] Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки.

Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной.