Динамическое программирование

Динамическое программирование позволяет находить оптимальное решение задачи путем ее декомпозиции на несколько этапов. Эта декомпозиция осуществляется по различным принципам. В некоторых задачах по временным периодам, в других — по объектам управления. Иногда разбиение производится искусственно. Фундаментальным принципом динамического программирования, составляющим основу декомпозиции задачи на этапы, является оптимальность.

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

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

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

Пример задачи №26

Определить оптимальный маршрут из пункта 1 в пункт 10 по схеме маршрутов движения (рис. 4.1).

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

Требуется определить такой путь из пункта 1 в пункт 10, общая стоимость которого является минимальной.

Решение:

Используем формулу рекуррентных соотношений Беллмана:

где — количество этапов в решении;

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

Начинаем поиск оптимального маршрута от конечного пункта, положив

Таким образом, определен оптимальный путь: 1-3-7-9-10, затраты по которому составляют

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

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

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

Пример задачи №27

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

где — объем производства; — запасы на конец отрезка планирования, — затраты на хранение единицы продукции, .

Считаем, что и — целые, причем .

Решение:

Используем рекуррентные соотношения:

где — количество этапов в решении;

— множество значений переменной ;

— затраты, соответствующие оптимальной стратегии, если до конца планируемого периода остается этапов;

— объем производства, обеспечивающий оптимальную стратегию. Начинаем формирование оптимального плана от последнего этапа, положив .

Так как по условию задачи, то на этом этапе получаем следующие возможные значения функции :

Для удобства занесем эти данные в таблицу.

Положим

Тогда для

следовательно

Аналогично

Таблица имеет вид.

Положив , получим следующую таблицу.

Наконец, для таблица примет вид.

Таким образом, получим два варианта оптимального плана работы с затратами, равными 49 единицам: 3;4;5;0и4;5;0;3.

Теория игр

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

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

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

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

Пример задачи №28

В игре участвуют первый и второй игроки, каждый из них может записать независимо от другого цифры 1, 2 и 3. Если разность между цифрами, записанными игроками, положительна, то первый игрок выигрывает количество очков, равное разности между цифрами, и, наоборот, если разность отрицательна, то выигрывает второй игрок. Если разность равна нулю, то игра заканчивается вничью.

У первого игрока три стратегии (варианта действия): (записать 1), (записать 2) и (записать 3); у второго игрока также три стратегии: .

Задача первого игрока — максимизировать свой выигрыш, задача второго игрока — минимизировать свой проигрыш.

Матрица игры, или платежная матрица, имеет вид

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

Соответственно при выборе стратегии —

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

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

Аналогично определяется наилучшая стратегия второго игрока. Второй игрок при выборе стратегии в худшем случае получит проигрыш

При выборе стратегий и проигрыш составит, соответственно,

Он выбирает стратегию, при которой его проигрыш будет минимальным и составит

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

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

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

В игре, матрица которой имеет размерность , стратегии первого игрока задаются наборами вероятностей , с которыми игрок применяет свои чистые стратегии. Эти наборы можно рассматривать как -мерные векторы, для которых выполняются условия

Аналогично для второго игрока наборы вероятностей определяют -мерные векторы

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

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

Пример задачи №29

Рассмотрим игру, представленную платежной матрицей

Решение:

Элементы стратегий и одинаковы, одну из них можно исключить. Все элементы стратегии меньше элементов стратегии , следовательно, можно исключить. Все элементы меньше , исключаем .

Для второго игрока, сравнивая и , исключаем сравнивая и , исключаем .

В результате преобразований получим матрицу

Графический метод решения матричных игр

Графический метод применим к играм, в которых хотя бы один игрок имеет только две стратегии.

Пример задачи №30

Найти решение игры, заданной матрицей

Решение:

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

По формулам

находим оптимальные стратегии и цену игры

Ответ. Оптимальные смешанные стратегии игроков

цена игры составляет .

Данный ответ означает следующее:

— если первый игрок с вероятностью будет применять первую стратегию и с вероятностью вторую, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее ;

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

Пример задачи №31

Найти решение игры, заданной матрицей

Решение:

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

Нижней границей выигрыша для игрока является ломаная . Стратегии и являются активными стратегиями игрока . Точка их пересечения определяет оптимальные стратегии игроков и цену игры. Второму игроку не выгодно применять стратегии и , поэтому вероятность их применения равна 0, т.е. .

Решение игры сводится к решению игры с матрицей 2×2

По формулам находим оптимальные стратегии и цену игры:

Ответ. Оптимальные смешанные стратегии игроков

цена игры составляет .

V 3 3) 3

Данный ответ означает следующее:

— если первый игрок с вероятностью будет применять первую стратегию и с вероятностью вторую, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее ;

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

Пример задачи №32

Найти решение игры, заданной матрицей

Решение:

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

Верхней границей проигрыша для игрока является ломаная . Стратегии и являются активными стратегиями игрока А. Точка их пересечения К определяет оптимальные стратегии игроков и цену игры. Первому игроку не выгодно применять стратегии и , поэтому вероятность их применения равна 0, т.е. .

Решение игры сводится к решению игры с матрицей 2×2:

Решение матричных игр сведением к задаче линейного программирования

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

Рассмотрим игру двух лиц с нулевой суммой, заданную платежной матрицей

Применение первым игроком оптимальной стратегии должно обеспечить ему при любых действиях второго игрока выигрыш не меньше цены игры.

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

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

По условию

Разделим обе части этого равенства на

Оптимальная стратегия игрока должна максимизировать величину , следовательно, функция

должна принимать минимальное значение.

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

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

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

Преобразуем систему ограничений, разделив все члены неравенств на .

По условию

Разделим обе части этого равенства на

Оптимальная стратегия игрока В должна минимизировать величину , следовательно, функция

должна принимать максимальное значение.

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

Пример задачи №33

Найти решение игры, заданной матрицей

Решение:

Игра не имеет седловой точки. Оптимальное решение следует искать в области смешанных стратегий.

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

Для оптимальной стратегии имеет следующую задачу линейного программирования:

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

Учитывая соотношения между

а также равенство

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

Игры с природой

В некоторых задачах, приводящихся к играм, имеется неопределенность, вызванная отсутствием информации об условиях, в которых осуществляется действие (погода, покупательский спрос и т.д.). Эти условия зависят не от сознательных действий другого игрока, а от объективной действительности. Такие игры называются играми с природой. Человек в играх с природой старается действовать осмотрительно, второй игрок (природа, покупательский спрос) действует случайно.

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

· Критерий Вальда. Рекомендуется применять максиминную стратегию. Она выбирается из условия

и совпадает с нижней ценой игры. Критерий является пессимистическим, считается, что природа будет действовать наихудшим для человека способом.

· Критерий максимума. Он выбирается из условия

Критерий является оптимистическим, считается, что природа будет наиболее благоприятна для человека.

· Критерий Гурвица. Критерий рекомендует стратегию, определяемую по формуле

где — степень оптимизма и изменяется в диапазоне [0, 1 ].

Критерий придерживается некоторой промежуточной позиции, учитывающей возможность как наихудшего, так и наилучшего поведения природы. При = 1 критерий превращается в критерий Вальда, при = 0 — в критерий максимума. На оказывает влияние степень ответственности лица, принимающего решение по выбору стратегии. Чем больше последствия ошибочных решений, больше желания застраховаться, тем а ближе к единице.

· Критерий Сэвиджа. Суть критерия состоит в выборе такой стратегии, чтобы не допустить чрезмерно высоких потерь, к которым она может привести. Находится матрица рисков, элементы которой показывают, какой убыток понесет человек (фирма), если для каждого состояния природы он не выберет наилучшей стратегии.

Элементы матрицы рисков находятся по формуле

где — максимальный элемент в столбце исходной матрицы.

Оптимальная стратегия определяется выражением

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

Пример задачи №34

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

Платежная матрица в тысячах рублей оценивается следующим образом:

Что должен посеять Иванов?

Решение:

· Согласно критерию Вальда рекомендуется применять максимальную стратегию.

Следует сеять пшеницу.

· Воспользуемся критерием Сэвиджа. Составим матрицу рисков, элементы которой находим по формуле

Оптимальная стратегия определяется выражением

Найдем

В соответствии с этим критерием следует сеять пшеницу. 3. Воспользуемся критерием Гурвица. Оптимальная стратегия определяется по формуле

где — степень оптимума и изменяется в диапазоне [0; 1], предположим

т.е. следует принять решение о посеве пшеницы.

· Если принять известным распределение вероятностей для различных состояний природы, например считать эти состояния равновероятными

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

так как максимальное значение имеет , то следует сеять пшеницу.

Теория графов

Непустое множество и множество отношений называется графом и обозначается . Граф называется конечным, если множество конечно.

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

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

Матрицей смежности называется матрица у которой элемент равен количеству ребер, соединяющих вершины и .

Матрицей инцидентности называется матрица , у которой элемент равен 1, если вершинах, инцидентна ребру , и равен 0 в противном случае.

Графы можно задавать списками пар вершин, соединенных ребрами или заданием для каждой вершины множества смежных вершин.

Характеристики графа

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

Степенью вершины графа называется число равное количеству ребер графа, инцидентных этой вершине. Вершина называется четной (нечетной), если ее степень — четное (нечетное) число.

Теорема 1. Если конечный граф (без петель) имеет вершин и ребер, то

Теорема 2. Число нечетных вершин любого графа четно.

Теорема 3. Во всяком графе с вершинами ( > 2) всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.

Теорема 4. Если в графе с вершинами ( > 2) в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени — 1.

Путь и цикл в графе

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

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

Теорема 5. Если у графа все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.

Связность графа, деревья

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

Теорема 6. Связный граф представляет собой простой цикл тогда и только тогда, когда каждая его вершина имеет степень 2.

Ребро называется мостом, если в графе , полученном после удаления ребра вершины и несвязны.

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

Плоские графы

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

Плоское представление имеет только плоский граф, и обратно: у всякого плоского графа всегда найдется плоское представление.

Гранью в плоском представлении графа называют-часть плоскости, ограниченную простым циклом и не содержащую внутри других циклов. Часть плоскости, расположенная вне плоского представления графа и ограниченная изнутри простым циклом, называется бесконечной гранью. Две грани называются соседними, если и[ границы имеют хотя бы одно общее ребро. Мост, соединяющий два цикла, называется перегородкой.

В плоском представлении дерева за грань принимают всю плоскость чертежа.

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

которое называется формулой Эйлера.

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

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

Теорема 7. Для любого плоского графа существует плоское представление, в котором все ребра — прямолинейные отрезки.

Эйлеровы графы

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

Теорема 8. Эйлеров граф является связным, и все его вершины — четными.

Теорема 9. Если граф связный и все его вершины четны, то он обладает эйлеровым циклом.

Теорема 10. Если граф обладает эйлеровым путем с концами и , то граф связный и А и В его единственные нечетные вершины.