<< предыдущая страница   следующая страница >>
birmaga.ru
добавить свой файл

  1 2 3 4
Раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений. В основе метода динамического программирования (метод последовательной максимизации) лежит принцип оптимальности Беллмана.


53

ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ДП

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

Пусть также выполняются два условия:

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


, где .

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

54

ПРИНЦИП ОПТИМАЛЬНОСТИ Беллмана

В общем виде принцип оптимальности формулируется следующим образом:

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


ЭЛЕМЕНТЫ ТЕОРИИ ИГР


55

ТЕОРИЯ ИГР

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

56

ИГРА

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

В игре участвует некоторое количество (множество) сторон, которые обычно называются игроками.


57

СТРАТЕГИЯ игрока

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

Интересы сторон представлены для каждого из игроков функциями выигрыша (платежа).

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

58

ОПТИМАЛЬНАЯ СТРАТЕГИЯ игрока

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

59

КОАЛИЦИЯ

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

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

60

КОНЕЧНАЯ (БЕСКОНЕЧНАЯ) ИГРА

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


В бесконечных играх игроки обладают бесконечным числом возможных стратегий.


61

АНТАГОНИСТИЧЕСКАЯ ИГРА (ИГРА С НУЛЕВОЙ СУММОЙ)

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

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

62

ИГРА С ПОСТОЯННОЙ РАЗНОСТЬЮ

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

63

ИГРА С НЕНУЛЕВОЙ СУММОЙ

Игра, в которой имеются и конфликты, и согласованные действия игроков.

64

КООПЕРАТИВНЫЕ (НЕКООПЕРАТИВНЫЕ) ИГРЫ

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

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

65

ПОЗИЦИОННАЯ ИГРА

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

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


К позиционным многошаговым играм относятся, например, шашки и шахматы.


66

ПЛАТЕЖНАЯ МАТРИЦА (МАТРИЦА ВЫИГРЫШЕЙ)

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

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

67

НИЖНЯЯ (ВЕРХНЯЯ) ЦЕНА ИГРЫ

Пусть парная игра с нулевой суммой задана платежной матрицей

,

в которой строки – стратегии первого игрока, столбцы – стратегии второго игрока, а элементы матрицы – выигрыши первого игрока.

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

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

.

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

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

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


68

ПРИНЦИП МИНИМАКСА

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

69

ИГРЫ С «ПРИРОДОЙ»

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

Человек в играх с «природой» старается действовать осмотрительно, второй игрок (природа, покупательский спрос) действует случайно.

70


КРИТЕРИИ ВЫБОРА ОПТИМАЛЬНОЙ СТРАТЕГИИ в играх с «природой»

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



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

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


.

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

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

,

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

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

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

.

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

.


СЕТЕВЫЕ МЕТОДЫ И МОДЕЛИ ОРГАНИЗАЦИИ И ПЛАНИРОВАНИЯ


71

ГРАФ


Граф математически определяется как совокупность двух множеств: множества элементов (вершин графа) и множества соответствий, отношений между этими элементами (множество ребер графа).

Обозначение: .

Две вершины, соединенные ребром, называются смежными вершинами графа.

Наглядно граф представляется в виде совокупности точек или кружков (вершин), соединенных линиями (ребрами) – см. рис.

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

72

ОРИЕНТИРОВАННЫЙ ГРАФ

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

Ребра ориентированного графа называют дугами.

73

СЕТЬ

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

74

СЕТЕВАЯ МОДЕЛЬ

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

Три основных элемента сетевой модели – работа, событие и путь.

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


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

Фиктивная работа – связь между событиями без затрат ресурсов.

Ожидание – работа, расходующая время как ресурс.

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

Завершающее событие – событие, не имеющее последующих событий.

Путь – любая непрерывная последовательность (цепь) работ и событий.


75