Задачи для самостоятельного решения

 

1. Найдите оптимальную стратегию 1-го игрока для игры двух участников с нулевой суммой путем сведения ее к задаче линейного программирования, если задана платежная матрица:

2. Найдите оптимальную стратегию 2-го игрока для игры двух участников с нулевой суммой путем сведения ее к задаче линейного программирования, если задана платежная матрица:

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

4. Найдите оптимальные стратегии игроков в известной игре «камень, ножницы, бумага».

Динамическое программирование

Построение модели динамического программирования (ДП) и применение метода ДП для решения сводится к следующим моментам:

1) выбирают способ деления процесса управления на шаги;

2) определяют параметры состояния S_k и переменные управления X_k на каждом шаге;

3) записывают уравнения состояний;

4) вводят целевые функции k-го шага и суммарную целевую функцию;

5) вводят в рассмотрение условные максимумы (минимумы) Z_k^*(S_k-1) и условное оптимальное управление на k-м шаге: X_k^*(S_k-1), k= .

6) записывают основные для вычислительной схемы ДП уравнения Беллмана для Z_n^*(S_n-1) и Z_k^*(S_k-1), k=

,

7) решают последовательно уравнения Беллмана (условная оптимизация) и получают две последовательности функций: { Z_k^*(S_k-1) } и {X_k^*(S_k-1) }.

8) после выполнения условной оптимизации получают оптимальное решение для конкретного состояния S₀: а)Z_max= Z₁^*(S₀) и б) по цепочке S₀ÞX₁^*® S₁^*ÞX₂^*® S₂^*Þ...ÞX_n-1^*® S_n-1^*Þ X_n^*® S_n^* оптимальное управление: X^*(X₁^*, X₁^*,..., X₁^*).

Пример задачи динамического программирования

 

Задача. Планируется деятельность четырех промышленных предприятий (системы) на очередной год. Начальные средства: S ₀=5 условных единиц. Размеры вложения в каждое предприятие кратны 1 условной единице. Средства Х, выделенные k –му предприятию (k =1, 2, 3, 4), приносит в конце года прибыль f_k (X). Функции f_k (X) заданы таблично:

Х	f 1(X)	f 2(X)	f 3(X)	f 4(X)

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

Решение.

Обозначим через X_k количество средств, выделенных k -му предприятию. Суммарная прибыль равна . Переменные X удовлетворяют ограничениям: Требуется найти переменные X ₁, X ₂, X ₃, X ₄, удовлетворяющие данным ограничениям и обращающие в максимум функцию Z.

Рассмотрим особенности модели. Ограничения линейные, но переменные целочисленные, а функции f_k (X_k) заданы таблично, поэтому нельзя применить методы целочисленного линейного программирования.

Схема решения задачи методом ДП имеет следующий вид: процесс решения распределения средств S ₀=5 можно рассматривать как 4-шаговый, номер шага совпадает с номером предприятия; выбор переменных X ₁, X ₂, X ₃, X ₄ – уравнения соответственно на I, II, III, IV шагах; Ŝ - конечное состояние процесса распределения – равно нулю, так как все средства должны быть вложены в производство, Ŝ =0. Покажем схему распределения:

Уравнения состояний в данной задаче имеют вид:

S_k = S_{k -1}- X, (k= ),

где S_k -параметр состояния – количество средств, оставшихся после k -го шага, т.е. средства, которые остается распределить между оставшимися (4- k) предприятиями.

Введем в рассмотрение функцию Z_k ^* (S_{k -1}) – условно оптимальную прибыль, полученную от k -го, (k +1)-го,..., 4-го предприятий, если между ними распределялись оптимальным образом средства S_{k -1} (0 £ S_{k -1} £ 5). уравнения на k -ом шаге удовлетворяют условию: 0 £ X_k £ S_{k -1} (либо k -му предприятию ничего не выделяем, X_k =0, либо не больше того, что имеем к k -му шагу, X_k £ S_{k -1} ).

Последовательно решаем уравнения

проводя последовательную оптимизацию каждого шага. Для этого поступим следующим образом.

1. Создадим тексто­вую форму – таблицу для ввода условий задачи. Введем исходные данные задачи в созданную форму-таблицу:

2. В ячейку E15 введем формулу

=ИНДЕКС($B$3:$F$8; ПОИСКПОЗ($C15;$B$3:$B$8); G$12+1), скопируем формулу с ячейки E15 до ячейки Е35.

3. В ячейку F15 введем формулу

=ИНДЕКС($B$3:$F$8;ПОИСКПОЗ($D15;$B$3:$B$8);5), скопируем формулу с ячейки F15 до ячейки F35.

4. В ячейку G15 введем формулу =E15+F15, скопируем формулу с ячейки G15 до ячейки G35.

5. Находим максимальное значение для каждого состояния от 0 до 5, для этого в ячейку Н15 введем формулу =МАКС(G15), после копирования формулы в ячейку H16, необходимо изменить диапазон с G16 на G16:G17, для этого стоя в строке формул необходимо растянуть выделенный прямоугольник на одну ячейку вниз. Затем копируем формулу из H16 в ячейку H18 и проводим такие же операции по увеличению диапазона, и т.д. до ячейки H30.

6. Находим значение управления Х_k, которому соответствует максимальное значение функции Z _k, для этого в ячейку I15 введем формулу =ИНДЕКС($C15:G15;ПОИСКПОЗ(H15;G15;0);1), скопируем формулу в ячейки I16, I18, I21, I25, I30 постепенно увеличивая диапазон, аналогично тому, как это делалось в пункте 5. В результате получим следующую таблицу:

7. Выделяем диапазон ячеек E15:I35 выполняем команду Копировать, устанавливаем курсор в ячейку J15 выполняем команду Вставить.

8. Изменим формулу функции Z ₃*(S ₂). В ячейки K15, K16, K18, K21, K25, K30, введем соответственно максимальные значения предыдущего шага, находящиеся в ячейках H15, H16, H18, H21, H25, H30. В остальные ячейки поместим значения, стоящие в этом же столбце и соответствующие предыдущим S_k. В ячейку K17 копируем значение ячейки K15; в ячейки K19 и K20 – значения K16 и K17; в K22:K24 – K18:K20 и т. д. до ячейки K35. В результате получим:

9. Выделяем диапазон ячеек J15:N35 выполняем команду Копировать, устанавливаем курсор в ячейку O15 выполняем команду Вставить. В результате получаем заполненную таблицу:

10. Сравнивая полученные значения, получим Z ₁^*(5)=24 усл. ед. = Z_max при X ₁^*= X ₁^*(5)=1. Вычисляя, получим S ₁^* = 5 - 1 = 4, а по таблице в столбце 12 находим X ₂^* = X ₂^* (4) = 2. Далее находим S ₂^* = 4-2 = 2, а в столбце 6 X ₃^* = X ₃^*(2) = 1. Наконец, S ₃^* = 2-1 = 1 и X ₄^* = X ₄^*(1) = 1, т. е. X ^*(1; 2; 1; 1).

Максимум суммарной прибыли равен 24 усл. ед. средств при условии, что 1-му предприятию выделено 1 усл. ед.; 2-му предприятию – 2 усл. ед.; 3-му предприятию – 1 усл. ед.; 4-му предприятию – 1 усл. ед.

 

12345

Поделиться:

Воспользуйтесь поиском по сайту: