Вариант 4: 4 задачи. Некто может поехать на автобусе, электричке или маршрутном такси. Цена билета соответственно

  • ID: 19407 
  • 5 страниц

Фрагмент работы:

Вариант 4: 4 задачи. Некто может поехать на автобусе, электричке и…

Задача №1.

Некто может поехать на автобусе, электричке или маршрутном такси. Цена билета соответственно 3, 6 и 8 рублей. Если водители автобусов объявили забастовку, решивший ехать на автобусе, опаздывает и несет потери, равные 8 руб. В случае забастовки билеты на маршрутное такси дешевеют до 5 руб. Сформулировать задачу как задачу теории игр. Найдите решение или укажите алгоритм нахождения решения

Решение:

Данную задачу можно рассматривать как игру, в которой у 1 игрока (пассажир) есть три стратегии:

I: 1={поехать на автобусе}

2={поехать на электричке}

3={поехать на маршрутном такси}

У второго игрока (транспорт) есть 2 стратегии:

II: 1={водители автобусов объявили забастовку}

2={водители автобусов не объявили забастовку}

Определим потери 1 игрока в каждом случае. Если забастовки нет, то 1 игрок теряет 3, 6 и 8 рублей соответственно. Если же есть забастовка, то в случае, если он решит поехать на автобусе, его потери составят 8 руб., если поедет на электричке – 6 руб., а если на маршрутном такси – то 5 руб.

Запишем матрицу потерь:

Для нахождения решения игры определим, имеет ли матрица потерь седловую точку:

1 2

1 8 3 3

2 6 6 6

3 5 8 5

…8 8

…=6

…=8

Т.к., то игра не имеет седловой точки и неразрешима в чистых стратегиях.

Укажем алгоритм решения игры.

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

Строим эти прямые на графике на отрезке 0..1 и находим нижнюю огибающую этих прямых. Самая высокая точка этой огибающей будет решением игры.

Задача №2.

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

Решение:

а) для ответа на вопрос определим верхнюю и нижнюю цену игры:

1 2 3 4

1 -6 2 0 1 2

2 -3 3 0 2 3

3 -3 0 -3 4 4

4 0 6 0 3 6

…-6 0 -3 1

…2

…1

Т.к., то игра не имеет седловой точки и неразрешима в чистых стратегиях.

б) составим системы уравнений для нахождения решения этой игры. Не все элементы матрицы A неотрицательны, поэтому прибавим ко всем элементам матрица число 6, чтобы все элементы стали неотрицательны. Получим матрицу :

На основе полученной матрицы составляем системы уравнений для прямой и двойственной задач линейного программирования

прямая задача:

двойственная задача:

Задача №3.

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

Показатели Номер участка

Цена перевозки 1 т. щебня (руб.) 1 2 3 4

От установки 1 4 3 8 5

От установки 2 9 7 5 4

От установки 3 3 6 2 8

Потребность в щебне (т.) 50 50 70 70

Недостающее количество щебня можно обеспечить за счет увеличения производительности дробильной установки, что вызывает дополнительные затраты на выработку 1 т. Щебня в размере 3 руб. Построить модель и сформулировать на ее основе задачу, анализ которых позволит определить и обосновать оптимальный план закрепления стройплощадок за дробильными установками с учетом перечисленных возможностей увеличения производства щебня

Решение:

Пусть xij - количество тонн щебня, перевозимое от i-ой дробильной установки к j-му участку, тогда по условию задачи можно составить следующую систему ограничений по потребности щебня

Задача №4.

Рассматривается транспортная задача со следующей таблицей стоимостей перевозок:

1

2

3

1 0 21 12 30

2 21 18 13 12

3 6 9 3 16

15 21 22

1). Найти начальный план методами: а) северо-западного угла и б) наименьшей стоимости.

2). Проверить, является ли начальное решение, найденное методом наименьшей стоимости оптимальным.

Решение: