2 Этап: формирование исключаемой области.

По переменной сформируем исключаемую область:

3 Этап: формирование и решение задач с дополнительными ограничениями.

На основе исходной задачи с ослабленными ограничениями сформируем две самостоятельные задачи:

(1.1):

(1.2):

Решим задачу (1.1):

Рис. 6.2. Решение задачи (1.1)

Оптимальное решение является целочисленным. Для рассматриваемой задачи , то .

Решим задачу (1.2):

Рис. 6.3. Решение задачи (1.2)

Оптимальное решение не удовлетворяет условию целочисленности.

II итерация

1 Этап: формирование исключаемой области.

По переменной сформируем исключаемую область:

2 Этап: формирование и решение задач с дополнительными ограничениями.

На основе задачи (1.2) сформируем две самостоятельные задачи:

(1.2.1):

(1.2.2):

Решим задачу (1.2.1):

Рис. 6.4. Решение задачи (1.2.1)

Оптимальное решение удовлетворяет условию целочисленности исходной задачи. Для рассматриваемой задачи (27 > 26), то .

Решим задачу (1.2.2):

Рис. 6.5. Решение задачи (1.2.2)

Задача (1.2.2) не имеет решения, вычеркиваем ее из общего списка.

Список задач исчерпан, о чем свидетельствует дерево задач (рис. 6.6).

Рис. 6.6. Дерево задач

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

Ответ: оптимальное целочисленное решение: , .

7. Теория игр

7.1. Основные понятия и определения

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

Цель игры выигрыш одного из игроков.

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

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

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

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

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

1) варианты действий игроков;

2) объем информации каждого игрока о поведении партнеров;

3) выигрыш, к которому приводит каждая совокупность действий.

Как правило, выигрыш (или проигрыш) может быть задан количественно: к примеру, проигрыш – 0, выигрыш – 1, ничья – ½.

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

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

Если обозначить a – выигрыш одного из игроков, b – выигрыш другого, то для игры с нулевой суммой , в связи с этим достаточно рассматривать только выигрыш одного из игроков.

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

Личный ход – это сознательный выбор игроком одного из возможных действий.

Случайный ход – это случайно выбранное действие.

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

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

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

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

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

Целью теории игр является определение оптимальной стратегии для каждого игрока.

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

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