Лабораторная работа 2

Cрок сдачи лабораторной работы: 01.11.2010

Задание

Имеется вычислительный центр (ВЦ), эксплуатирующий распределенную вычислительную систему (ВС) из n элементарных машин (ЭМ). Считается, что в очереди диспетчера присутствуют задачи всех рангов. В рамках лабораторной работы требуется выполнить нижеследующие задания.

1. Разработать программу решения теоретико-игровой задачи "Диспетчер-вычислительный центр" (задача I) [1, с. 185].

Входные данные (:latex:) $n$ (:latexend:), (:latex:)$c_{1}$(:latexend:), (:latex:)$c_{2}$(:latexend:), (:latex:)$c_{3}$(:latexend:) загружаются из файла. Для формирования матрицы платежей использовать подход, описанный в [1, с. 187]. Значения (:latex:)$c_{1}$(:latexend:), (:latex:)$c_{2}$(:latexend:), (:latex:)$c_{3}$(:latexend:) выбирать следующим образом: (:latex:)$c_{1} \in \left\{{1, 2, 3}\right\}$(:latexend:), (:latex:)$c_{2}, c_{3} \in \left\{{4, 5, 6}\right\}$(:latexend:). Приближенное решение игры строить итеративным методом Брауна [1, с. 192].

2. Построить график зависимости времени работы алгоритма от количества n ЭМ в системе.

3. Объяснить функционирование ВЦ и диспетчера в соответствии с найденными оптимальными смешанными стратегиями.

Пример работы

Входные данные: ($ n = 10, c_1 = 1.0, c_2 = 2.0, c_3 = 3.0, e = 0.01. $)

Матрица платежей C:

  0.00  3.00  6.00  9.00 12.00 15.00 18.00 21.00 24.00 27.00 30.00
  2.00  1.00  5.00  8.00 11.00 14.00 17.00 20.00 23.00 26.00 29.00
  4.00  3.00  2.00  7.00 10.00 13.00 16.00 19.00 22.00 25.00 28.00
  6.00  5.00  4.00  3.00  9.00 12.00 15.00 18.00 21.00 24.00 27.00
  8.00  7.00  6.00  5.00  4.00 11.00 14.00 17.00 20.00 23.00 26.00
 10.00  9.00  8.00  7.00  6.00  5.00 13.00 16.00 19.00 22.00 25.00
 12.00 11.00 10.00  9.00  8.00  7.00  6.00 15.00 18.00 21.00 24.00
 14.00 13.00 12.00 11.00 10.00  9.00  8.00  7.00 17.00 20.00 23.00
 16.00 15.00 14.00 13.00 12.00 11.00 10.00  9.00  8.00 19.00 22.00
 18.00 17.00 16.00 15.00 14.00 13.00 12.00 11.00 10.00  9.00 21.00
 20.00 19.00 18.00 17.00 16.00 15.00 14.00 13.00 12.00 11.00 10.00

Количество итераций: ($l = 1253901$)

Цена игры ($V = 0.005$)

Оптимальные смешанные стратегии ВЦ: 0.25 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.75

Оптимальные смешанные стратегии диспетчера: 0.31 0.00 0.00 0.03 0.03 0.00 0.24 0.01 0.18 0.14 0.06

Литература

  1. Евреинов Э.В., Хорошевский В.Г. Новосибирск: Наука, 1978. – 319 с. (/home/public/dcsft/doc/cs/evr-khor78-ovs)
  2. Матричные игры
  3. М.А.Тынкевич. ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ