<< Пред.           стр. 13 (из 13)           След. >>

Список литературы по разделу

 
 
 удовлетворяющих условиям (6.24)-(6.25) и минимизирующих функцию
 
  (6.26)
 
  6.2.2. Простейшая задача оптимального управления.
  Один из приемов, применяемых для решения экстремальных задач, состоит в выделении некоторой проблемы, допускающей относительно несложное решение, к которой в дальнейшем могут быть сведены остальные задачи.
  Рассмотрим так называемую простейшую задачу управления. Она имеет вид
 
  (6.27)
 
  (6.28)
 
  (6.29)
  Специфика условий задачи (6.27)-(6.29) состоит в том, что функции качества управления (6.27) и ограничения (6.28) являются линейными относительно , в то же время функция g(t, хt), входящая в (6.28), может быть произвольной. Последнее свойство делает задачу нелинейной даже при t = 1 , т. е. в статическом варианте.
  Общая идея решения задачи (6.27)-(6.29) сводится к ее "расщеплению" на подзадачи для каждого отдельно взятого момента времени, в предположении, что они успешно разрешимы. Построим для задачи (6.27)-(6.29) функцию Лагранжа
 
  (6.30)
 
 где - вектора множителей Лагранжа (t ? 0 : T). Ограничения (6.29), носящие общий характер, в функцию (6.30) в данном случае не включены. Запишем ее в несколько иной форме
 
  (6.31)
  Необходимые условия экстремума функции Ф (х, z,?) по совокупности векторов zt задаются системой уравнений
 
 
  (6.32)
 
 которая называется системой для сопряженных переменных. Как можно заметить, процесс нахождения параметров в системе (6.32) осуществляется рекуррентным образом в обратном порядке.
  Необходимые условия экстремума функции Лагранжа по переменным будут эквивалентны ограничениям (6.28), и, наконец, условия ее экстремума по совокупности векторов , должны быть найдены как результат решения задачи
 
  (6.33)
 
  Таким образом, задача поиска оптимального управления сводится к поиску управлений, подозрительных на оптимальность, т. е. таких, для которых выполняется необходимое условие оптимальности. Это, свою очередь, сводится к нахождению таких , удовлетворяющих системе условий (6.28), (6.32), (6.33), которая называется дискретным принципом максимума Понтрягина.
  Справедлива теорема.
 
  Теорема 6.2. Совокупность векторов , удовлетворяющих системе (6.28), (6.32), (6.33), образует седловую точку функции Ф (х, z, ?) (6.30), т. е. при любых допустимых x, z, ?, выполняются неравенства
 
 
  Доказательство.
  Пусть удовлетворяют системе (6.28), (6.32), (6.33). Тогда из (6.31) и (6.32) следует, что
 
 
 и поскольку удовлетворяет (6.33), то
 
 
 
  С другой стороны, в силу (6.28) из (6.30) следует, что при любом векторе
 
 
 
  Следовательно,
 
  ^
 
  Применяя теорему (6.2), а также положения теории нелинейного программирования, касающиеся связи между решением экстремальной задачи и существованием седловой точки (см. п. 2.2.2), приходим к выводу о том, что векторы , являются решением простейшей задачи оптимального управления (6.27М6.29).
  В результате мы получили логически простую схему решения данной задачи: из соотношений (6.32) определяются сопряженные переменные , затем в ходе решения задачи (6.33) находятся управления и далее из (6.28) - оптимальная траектория состояний .
  Предложенный метод относится к фундаментальным результатам теории оптимального управления и, как уже это упоминалось выше, имеет важное значение для решения многих более сложных задач, которые, так или иначе, сводятся к простейшей. В то же время очевидны и пределы его эффективного использования, которые целиком зависят от возможности решения задачи (6.33).
 
 
  КЛЮЧЕВЫЕ ПОНЯТИЯ
 
  > Игра, игрок, стратегия.
  > Игры с нулевой суммой.
  > Матричные игры.
  > Антагонистические игры.
  > Принципы максимина и минимакса.
  > Седловая точка игры.
  > Цена игры.
  > Смешанная стратегия.
  > Основная теорема матричных игр.
  > Динамическая транспортная задача.
  > Простейшая динамическая модель макроэкономики.
  > Простейшая задача оптимального управления.
  > Дискретный принцип максимума Понтрягина.
 
  КОНТРОЛЬНЫЕ ВОПРОСЫ
 
 6.1. Кратко сформулируйте предмет теории игр как научной дисциплины.
 6.2. Какой смысл вкладывается в понятие "игра"?
 6.3. Для описания каких экономических ситуаций может быть применен аппарат теории игр?
 6.4. Какая игра называется антагонистической?
 6.5. Чем однозначно определяются матричные игры?
 6.6. В чем заключаются принципы максимина и минимакса?
 6.7. При каких условиях можно говорить о том, что игра имеет седловую точку?
 6.8. Приведите примеры игр, которые имеют седловую точку и в которых она отсутствует.
 6.9. Какие подходы существуют к определению оптимальных стратегий?
 6.10. Что называют "ценой игры"?
 6.11. Дайте определение понятию "смешанная стратегия".
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  СПИСОК ЛИТЕРАТУРЫ
 
  1. Абрамов Л. М., Капустин В. Ф. Математическое программирование. Л., 1981.
  2. Ашманов С. А. Линейное программирование: Учеб. пособие. М., 1981.
  3. Ашманов С. А., Тихонов А. В. Теория оптимизации в задачах и упражнениях. М., 1991.
  4. Беллман Р. Динамическое программирование. М., 1960.
  5. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М., 1965.
  6. Гавурин М. К., Малоземов В. Н. Экстремальные задачи с линейными ограничениями. Л., 1984.
  7. Гасс С. Линейное программирование (методы и приложения). М., 1961.
  8. Гейл Д. Теория линейных экономических моделей М 1963.
  9. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация/ Пер. с англ. М., 1985.
  10. Давыдов Э. Г. Исследование операций: Учеб. пособие для студентов вузов. М., 1990.
  11. Данциг Дж. Линейное программирование, его обобщения и применения. М., 1966.
  12. Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. М., 1976.
  13. Ермольев Ю. М., Ляшко И. И., Михалевич В. С., Тюптя В. И. Математические методы исследования операций: Учеб. пособие для вузов. Киев, 1979.
  14. Зайченко Ю. П. Исследование операций, 2-е изд Киев 1979.
  15. Зангвилл У. И. Нелинейное программирование. Единый подход. М., 1973.
  16. ЗойтендейкГ. Методы возможных направлений М 1963.
  17. Карлин С. Математические методы в теории игр, программировании и экономике. М., 1964.
  18. Карманов В. Г. Математическое программирование: .учеб. пособие. М., 1986.
  19. Корбут А. А., Финкельштейн Ю. Ю. Дискретное про-раммирование. М., 1968.
  20. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. М., 1977.
  21. Кюнце Г.П., Крелле В. Нелинейное программирование. М., 1965.
  22. Ляшенко И. Н., Карагодова Е.А., Черникова Н. В., Шор Н.З. Линейное и нелинейное программирование. Киев, 1975.
  23. Мак-Кинси Дж. Введение в теорию игр. М., 1960.
  24. Мухачева Э. А., Рубинштейн Г. Ш. Математическое программирование. Новосибирск, 1977.
  25. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М, 1970.
  26. Оре О. Теория графов. М., 1968.
  27. Таха X. Введение в исследование операций/ Пер. с англ. М., 1985.
  28. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. М., 1972.
  29. Хедли Дж. Нелинейное и динамическое программирование. М., 1967.
  30. Юдин Д. Б., Гольштейн Е. Г. Линейное программирование (теория, методы и приложения). М., 1969.
  31. Юдин Д. Б., Гольштейн Е. Г. Линейное программирование. Теория и конечные методы. М., 1963.
  32. Lapin L. Quantitative methods for business decisions with cases. Fourth edition. HBJ, 1988.
  33. Little I. D. C., Murty K.G., Sweeney D.W., Karel C. An algorithm for traveling for the traveling salesman problem. - Operation Research, 1963, vol.11, No. 6, p. 972-989/ Русск. пер.: Литл Дж., Мурти К., СуиниД., Керел К. Алгоритм для решения задачи о коммивояжере. - В кн.: Экономика и математические методы, 1965, т. 1, № 1, с. 94-107.
 1 Напомним, что l - номер столбца, вводимого в базис, а r - номер строки в симплекс-таблице, определяющей номер столбца, выводимого из базиса.
 2 Аффинной оболочкой множества называют наименьшее аффинное множество, в котором содержится данное множество.
 3 Настоящая структура, симплекс-таблиц строится на идеях и принципах их организации, предложенных в [1].
 4 В данном пункте используется та же система обозначений, что и в п. 1.4.1.
 5 Здесь следует подчеркнуть, что двойственный симплекс-метод непосредственно нацелен на нахождение решения прямой задачи.
 6 Очевидно, что для определения пустоты множества допустимых планов достаточно найти полностью неотрицательную строку , соответствующую
 7 Так как в данных методах при переходе к очередной рассматриваемой точке происходит улучшение значения целевой функции (в частности, для задачи минимизации - уменьшение), их также называют релаксационными методами.
 8 Напомним, что примерами счетных множеств являются множества натуральных, целых и рациональных чисел.
 9 Впервые был предложен Р. Гомори в 1957-1958 гг.
 10 Динамическое программирование как научное направление возникло и сформировалось в 1951 - 1953 гг. благодаря работам Р. Беллмана и его сотрудников.
 11 Напомним, что при многократном повторении игры средний выигрыш близок к математическому ожиданию.
 12 Функционалом называется числовая функция, аргументами которой, как правило, служат другие функции.
 ??
 
 ??
 
 ??
 
 ??
 
 
 
 
 2
 
 
 

<< Пред.           стр. 13 (из 13)           След. >>

Список литературы по разделу