Автор работы: Пользователь скрыл имя, 12 Декабря 2011 в 17:56, курс лекций
Тема №3: «Решение задач теории игр ».
1. Область применения и основные понятия теории игр.
2. Общая постановка задач теории игр.
3. Решение игр, имеющих седловую точку.
4. Решение игр при помощи определения смешанных стратегий.
Решение многоэтапных задач осуществляется на основе принципа оптимальности - важнейшего принципа теории динамического программирования. Принцип оптимальности принято характеризовать формулировкой, которая принадлежит Р. Беллману: «Оптимальное поведение обладает тем свойством, что, каковы бы ни были первоначальное состояние и решение в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения».
Для пояснения этой формулировки используем рассмотренный нами пример. Предположим, что на первом этапе решения принято *4=1. Это, как известно, означает, что дополнительная прибыль, полученная от обновленного оборудования в течение 4-го года, полностью используется для замены оборудования в 5-м году пятилетки. В результате этого на данном и на последующих этапах будут получены следующие решения:
Суммарная прибыль за планируемый период F5 = 30005/1500 = 25.
Это на 35,2 % (2,352—2,0) ниже, чем по оптимальному плану реконструкции. Именно на столько процентов будет получено дополнительной прибыли от оборудования, обновленного за счет прибыли первых двух лет.
Из изложенного следует, что отличительной особенностью задач динамического программирования является то, что в них отражается динамика изучаемых процессов, их развитие и многоэтапный характер. При решении задач о замене оборудования рассматривалась динамика суммарной прибыли, на кото-
F=, — F3 + 1200n4—360%*4 = F3 + 840% (при x4 — 1),
(7.34)
F5 = F2 + 1440n3—260%*3 = F2 + 1440% (при xs = 0),
F5 =- f! + 2040n2 — 24п2л;2 = fi + 2040% (при xz = 0),
F5 == 2640л! + 216/11*1 = 2856% (при *!=-!).
В этом случае оптимальный план реконструкции будет характеризоваться значениями переменных: х\ = 1, х2 = 0, х3 = 0, Xt=\ и величиной суммарной прибыли
F = 2856n1S/l500 = 1,9045.
Итак, нами получена оптимальная стратегия (план) реконструкции оборудования, по которой обеспечивается суммарная
прибыль в размере 1,904 S. Эта сумма на 0,448 (2,352 5— —1,904 S) ниже, чем по первоначальному оптимальному плану. Снижение прибыли произошло за счет ошибочного решения, принятого на первом этапе. Принимая это ошибочное решение в качестве отправного момента на всех последующих этапах, можно получить решения, обеспечивающие оптимальный результат по отношению к принятому первому решению.
Задач с многоэтапными процессами в практике производственного планирования и управления много, однако для их решения методы динамического программирования используются еще недостаточно широко. Это объясняется в значительной степени тем, что при решении многоэтапных задач с учетом реальных производственных условий в ряде случаев возникают вычислительные сложности, которые преодолеваются только с помощью электронно-вычислительных машин. Но это нисколько не умаляет значения динамического программирования в решении большого круга задач, представляющих практический интерес.