Вычислительных систем
 Скачать 0.78 Mb.
|
|
32 Глава 3. Организация функционирования ВС учетом конкретных условий эксплуатации ВС. Будем считать, что если ??????, ?????? – чистые стратегии соответственно ВЦ и диспетчера, то элементы матрицы платежей ?????? ???????????? = ⎧ ⎨ ⎩ ???????????? 1 + (?????? − ??????)?????? 2 , при ?????? ≥ ??????, ???????????? 2 + (?????? − ??????)?????? 3 , при ?????? < ??????, где ?????? 1 – платеж за использование одной машины в течение единицы време- ни, ?????? 2 и ?????? 3 – штрафы в единицу времени соответственно за простой одной машины и при ?????? − ?????? = 1, ??????, ?????? ∈ ??????. Имеет место теорема [3, С. 187]. Теорема. Матрица ?????? ???????????? не имеет седловых точек тогда и только тогда, когда ?????? 1 < min{?????? 2 , ?????? 3 } 3.2.2. Итеративный метод Брауна Одним из методов решения матричных игр является итеративный ме- тод Брауна [3, С. 192]. Обозначим через C = ||?????? ???????????? || ?????? × ?????? -матрицу платежей; ?????? ?????? – ??????-я строка матрицы C, а ?????? ?????? – ее ??????-й столбец. Рассмотрим последовательности векторов: ??????(0), ??????(1), . . . , ??????(??????), . . . , ?????? (0), ?????? (1), . . . , ?????? (??????), . . . , где ??????(??????) = (?????? 0 (??????), ?????? 1 (??????), . . . , ?????? ?????? (??????)), ?????? (??????) = (?????? 0 (??????), ?????? 1 (??????), . . . , ?????? ?????? (??????)). Компонента ?????? ?????? (??????) , ?????? ∈ ?????? – это относительная оценка выигрыша ВЦ, если он в ??????-й итерации выбирает ??????-ю строку матрицы C; ?????? ?????? (??????) – относи- тельная оценка выигрыша диспетчера, если он в ??????-й итерации выбирает ?????? -й столбец матрицы C. На итерации ?????? ВЦ и диспетчер выбирают соответственно строку ?????? и столбец ?????? такие, что ?????? ?????? (??????) = max 0≤??????≤?????? ?????? ?????? (??????) = max ??????(??????), ?????? ?????? (??????) = max 0≤??????≤?????? ?????? ?????? (??????) = max ?????? (??????). Учитывая таким образом найденные ?????? и ??????, игроки пересматривают свои 3.2. Теоретико-игровой подход к обслуживанию потока задач 33 оценки значений строк и столбцов для следующей (?????? + 1)-й итерации: ??????(?????? + 1) = ??????(??????) + ?????? ·?????? , ?????? (?????? + 1) = ?????? (??????) + ?????? ??????· Нетрудно показать, что ??????(??????) = ??????(0) + ?????? ∑︁ ??????=0 ???????????? ?????? (??????)?????? ·?????? , ?????? (??????) = ?????? (0) + ?????? ∑︁ ??????=0 ???????????? ?????? (??????)?????? ??????· , где ???????????? ?????? равно числу выборов столбца ??????, а ???????????? ?????? (??????) – числу выборов строки ?????? в матрице C при реализации ??????-й итерации. Векторы ?????? (??????) = (?????? 0 , ?????? 1 , . . . , ?????? ?????? ) и П = (?????? 0 , ?????? 1 , . . . , ?????? ?????? ) будут оценками смешанных стратегий ВЦ и диспетчера, которые сходятся к оптимальным стратегиям ?????? * и П * . Итак, при больших ?????? ?????? * ≈ ?????? (??????), П * ≈ П(??????), ?????? ≈ max ??????(??????) − max ?????? (??????) 2?????? ≤ ?????? (??????), где ?????? (??????) – это значение цены игры после ??????-й итерации. Практически можно положить ??????(0) = ?????? (0) = 0. В качестве меры близости ?????? (??????) к ?????? можно взять max ??????(??????) − max ?????? (??????) ?????? ≤ ??????, где ?????? > 0. 3.2.3. Задание 1. Разработать программу решения методом Брауна игровой задачи «диспетчер-вычислительный центр». Входные данные ??????, ?????? 1 , ?????? 2 , ?????? 3 загружаются из файла или указываются как аргументы в командной строке. Для формирования матрицы платежей использовать подход, описанный в [3, С. 187]. Значения ?????? 1 , ?????? 2 , ?????? 3 выбирать следующим образом: |