Вопрос№53 Симплекс метод. Постановка задачи. Способы решения Каноническая форма:

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

1. Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X₁, ..., X_n), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X₁, ..., X_m), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1:

X₁ + a_1,m+1*X_m+1 + ... + a_1,n*X_n = b₁

.

. . . . . . . . . . . . . . . .

.

X_i + a_i,m+1*X_m+1 + ... + a_i,n*X_n = b_i

.

. . . . . . . . . . . . . . . .

.

X_m + a_m,m+1*X_m+1 + ... + a_m,n*X_n = b_m

Cоставляем начальный опорный план:

- базисные вектора

- базисные переменные

2. Составляем первую симплекс таблицу.

3. Считаем значение целевой функции, - коэффициенты целевой функции.

4. Считаем оценку плана:

. Смотрим , то данный опорный план минимален, если нет, то смотрим на столбцы положит., если и задача на макс, то план оптимален.

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

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

, для >0, вычисляем , max ( , (

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

Вопрос№54_1 Матричные игры. Решение игры в смешанных стратегиях.

Рассмотрим игру с двумя игроками. Причем каждый из них имеет конечное число стратегий. Пусть A-первый игрок, B-второй игрок. Предположим что игрок A имеет m стратегий, а игрок B имеет n стратегий: . Пусть игрок A выбрал стратегию, а игрок B - B стратегию. Будем считать, что выбор этих стратегий однозначно определяет исход игры.

- выигрыш игрока A

- выигрыш игрока B

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

…. ….

=A

Матрица игры m*n или платежная матрица игрока A.

Данная игра называется матричной игрой m*n. Антогонистической называют игру, в которой интересы игроков прямо противоположны => матричные игры антогонистические игры.

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

Алгоритм определения равновесной ситуации.

A: 1) Действие игрока А. В каждой строке матрицы А находится миним. элемент

…..

2) Среди чисел выберем макс. число

Действия игрока В:

1. В каждом столбце ищется макс. элемент .

2. Среди чисел выбираем минимум

Число называется верхней ценой игры, число - нижней ценой игры. Если = , то ситуация { называется равновесной и не один из игроков не заинтересован, чтобы ее нарушить.

Смешанные стратегии.

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

Рассмотрим игру m*n, заданную матрицей А= . Пусть - набор описывающий m смешанных стратегий игрока А. .

- набор описывающий смешанные стратегии игрока В.

То ситуация PQ – ситуация смешанных стратегий