Пример 3.4.1

Рассмотрим игру с матрицей выигрышей игрока I

Для игрока Iобозначимp₁вероятность выбора первой строки,

p₂– вероятность выбора второй строки,

p₃–вероятность выбора третьей строки,

p₄– вероятность выбора четвертой строки.

Для игрока IIобозначимq₁вероятность выбора первого столбца,

q₂– вероятность выбора второго столбца,

q₃ – вероятность выбора третьего столбца,

q₄ – вероятность выбора четвертого столбца.

Определение значения игры и оптимальной стратегии игрока IIпо задаче (3.4.12) – (3.4.16):

найти переменные v, q₁, q₂, q₃, q₄, которые максимизируют выигрыш -v игрока II

max – v

при ограничениях

q₁+q₂,+q₃+q₄=1,

11q₁+12q₂,+12q₃+16q₄-v≤ 0, (3.4.17)

9q₁+14q₂,+9q₃+8q₄-v≤ 0, (3.4.18)

15q₁+12q₂,+02q₃+10q₄-v≤ 0, (3.4.19)

10q₁+12q₂,+10q₃+13q₄-v≤ 0, (3.4.20)

q₁≥ 0q₂≥ 0q₃≥ 0q₄≥ 0,

vне имеет ограничения на знак.

Оптимальные стратегии игрока Iравны значениям двойственных переменных этой задачи линейного программирования.

Смысл неравенств (3.4.17) – (3.4.20) состоит в следующем. Если игрок IIиспользует свои оптимальные стратегии, а игрокIиспользует свои чистые стратегии, выбирая строки матрицы выигрышей, то его выигрыш в среднем будет не больше значения игрыv.

Вопросы для самопроверки

1.Дать определение смешанных стратегий игроков IиII.

2. Как определяется выигрыш игрока Iв смешанных стратегиях?

3. Дать определение ситуации равновесия в смешанных стратегиях.

4. Всегда ли существует ситуация равновесия в смешанных стратегиях?

Допустим, что матрица выигрышей игрока Iимеет вид

4. Чему равен выигрыш игрока II, если игрокIвсегда выбирает вторую строки?

5. Проверить равенство

(max)_i (min)_j a (i,j) = (min)_j (max)_i a (i,j)

Существует ли решение игры в чистых стратегиях?

6. Найти выигрыш игрока I, если игрокIвыбирает смешанную стратегию

, а игрок II выбирает смешанную стратегию .

Раздел 4. Целочисленное и нелинейное программирование

При изучении данного раздела Вам предстоит: Изучить две темы: Задача о назначениях; Нелинейное программирование. Ответить на вопросы рубежного теста к разделу 5. Если Вы будете испытывать затруднения в ответах, обратитесь к Учебному пособию (Глава 6) или к Глоссарию – краткому словарю основных терминов и положений.

4.1. Задача о назначениях

Изучаемые вопросы:

• Формулировка задачи о назначениях;

• Реализация задачи о назначениях в Excel.

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

Предположим, что nработников необходимо назначить наnработ. Обозначим черезc_ijстоимость выполнения работникомiработыj. Требуется найти оптимальное распределение работников по всем работам. Заметим, что число работников и число работ одинаково. Поэтому каждый работник может быть назначен только на одну работу. Обозначим черезx_ijпеременную, которая принимает значение 1,если работникiназначен на работуjи 0 – в противном случае. Тогда ограничение

означает, что каждый работник может быть назначен только на одну работу.

Аналогично, ограничение

означает, что каждая работа может быть выполнена только одним работником.

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

Таким образом, математически задача о назначениях состоит в определении переменных x_ij, которые минимизируют стоимость выполнения всех работ

при ограничениях

,

,

x_ijпринимает значения 0 и 1.

Задача о назначениях является частным случаем транспортной задачи, в которой работники – пункты отправления, а работы – пункты назначения. Объемы производства и потребления равны 1, а стоимость перевозки равна стоимости выполнения работы. Поэтому задачу о назначениях можно решить в Поиске решения.