Анализ оптимального решения ТЗ. Рекуррентная формула расчета целевой функции

На первом шаге значение целевой функции определяется как сума произведений тарифов на соответствующие объёмы грузов (сума от j=1 до n Сума от i=1 до m Cij*Xij). На всех последующих шагах также можно пользоваться этой формулой. Однако гораздо меньше вычислений даёт рекуррентная формула. F(Xi)=F(X(i-1)) –(если min) + (если max) Гама*Дельтаij где Гама – величина перераспределяемого груза, Дельтаij – оценка свободной клетки с которой начинается построение цикла.

Анализ оптимального плана. 1. Необходимо указать от какого поставщика к какому потребителю и в каком количестве направляется груз. Если был введён фиктивный поставщик (т.е. <запасов) то необходимо указать кто и в каком количестве недополучил груз. Если вводится фиктивный потребитель, то указывают поставщика и количество у которого остался не вывезенный груз. 2. Необходимо сделать выводы о количестве оптимальных решений. Если среди оценок свободных клеток последнего оптимального плана есть хоть одна нулевая (Дельтаij=0) то оптимальный план не единственный. Будет существовать альтернативный оптимум. Его можно найти построив цикл для клетки с нулевой оценкой и перераспределить груз. Зн

45. Графическое решение матричной игры размерностью 2 × 2.

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

Рассмотрим платёжную матрицу 2*2,

НА координатной плоскости по оси абсцисс отмечаем единич. Отрезок и проводимчерез точку (1;0) прямую перпендикулярно данной оси.

На полученной прямой отмечаем выигрыш 1-го игрока при использовании им с.тратегии А1.

На оси ординат отмечаем выигрыш 1-го игрока, при использовании стратегии А2.

Соединим значения соответствующие проигрышам 2-го игрока при использовании им страт-ииВ1 (а11, а21), и стратегии В2 (а12, а22).

В результате получим прямые В1В1 и В2В2; N=В1В1 ÇВ2В2 . N=(р1;g).

Первая координата этой точки соответствует вероятности применения первым игроком стратегии А1, а вторая координата этой точки соответствует цене игры g.

46. Графическое решение матричных игр размерностью 2 × n и m × 2.

Это игра у которой 1-ый игрок обладает 2-мя стратегиями, а у второго игрока n возможных стратегий.

Для решения данной игры необходимо найти для 1-го ирока вероятности р1 и р2; для этого на координатной плоскости отмечаем т. (1;0) и проводим через неё перпендикуляр к оси абсцисс. Назовем этот перпендик-р А1А1 и отметим на нем все выигрышные стратегии А1.

Ось ординат обозначим А2А2 и отметим на ней все выигрышные стратегии А2 (а21, а22, .., а2n),. Соединим значения соответствующие проигрышам 2-го игрока при использовании стратегий В1 (а11, а21), В2 (а12, а22),…., Вn (a1n, a2n).

Выделим среди пересечений прямых В1В1, В2В2,…., ВnBn нижнюю огибающую.

На данной огибающей найдём т. MAX, и обозначим её N (р1; g).

Для матрицы m*2.

В данной игре 1-ый игрок имеет m-стратегий, а второй только 2.

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

Построение выполняется аналогично игре 2*n, но перпендикуляр , проходящий через т. (1;0) обозначается В1В1 и на нем откладывается проигрыш 2-го игрока при использовании стратегии В1 (а 11, а 21, …, аm1).

Ось ординат обозначается В2В2 и на ней откладываются соответствующие проигрыши стратегии В2 (а12, а22, аm2).

Соединяем значении соответствующей стратегии А1 (а11, а12), А2 (а21, а22), …., Аm (am1,am2).

Выделим верхнюю огибающую от пересечения прямых А1А1, А2А2, …, АmAm. Точка MIN этой огибающей обозначим через N (q1;g).

48)Игры с природой. Критерий максимального среднего выигрыша (критерий Байеса, критерий Лапласа).

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

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

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

Если вероятности состояния природы неизвестны, то говорят об игре с природой в условиях полной неопределенности. Тогда для определения оптимальных стратегий активного игрока применяют критерий Лапласа, Вальда, Сэвиджа, Гурвица.

КРИТЕРИЙ БАЙЕСА:

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

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

Ai= ai1* q1+ ai2*q2+…+ ain* qn

B= max Ai

Критерий Байеса можно рассматривать относительно средних рисков. РИСКОМ называют разность между макс выигрышем активного игрока и обозначаем max aik, который он мог бы получить достоверно зная, что природа примет состояние Пк, а также тем выигрышем, который он получит, используя стратегию Ai ( т.е., чтобы составить матрицу рисков необходимо по каждому столбцу платежной матрицы найти max элемента, а затем вычитать из него соответствующие выигрыши платежной матрицы.

rij= max aik- aik

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

Ri= ri1* q1 +ri2* q2+..+rin* qn .

Оптимальной будет считаться та стратегия, при которой достигается минимальный средний риск R= min Ri.

Критерий Лапласа аналогичен критерию Байеса, но вероятности состояния природы неизвестны, поэтому предполагается, что все состояния природы равновероятны, т.е. q1=q2=…=qn=1/n

Ai=1/n (ai1 +ai2+…+ain)

L= max Ai

Ri= 1/n( ri1+ri2+…+rin)