ББК 22.18 Д 13 УДК 519.47 Рецензенты: кафедра математических основ управления Московского физико-технического института; д-р физ.-мат. наук В. В. Дикусар Давыдов Э. Г. Д13 Исследование операций: Учеб. пособие для студентов вузов.—М.: Высш. шк., 1990.—383 с.: ил. ISBN 5-06-001004-Х Пособие посвящено изложению методологических основ исследования операций, основ теории игр, математического программирования, управляе- мых марковских процессов. Большое внимание уделено построению моде- лей, обладающих высокой универсальностью применения. Д 1402050000(4309000000)—238 001(01)—90 -82—90 ББК 22.18 517.8 ISBN 5-06-001004-Х © Э. Г. Давыдов, 1990 ПРЕДИСЛОВИЕ Предлагаемое руководство написано на основе курса лекций, читавшегося автором в течение ряда лет на факультете вычисли- тельной математики и кибернетики МГУ им. М. В. Ломоносова. От уже имеющихся на аналогичную тему руководств книга отли- чается методологией (в основу принятия решений положен прин- цип наилучшего гарантированного результата) и набором рас- сматриваемых моделей и методов. В книге изложены основы теории антагонистических игр, ли- нейного и выпуклого программирования, излагаются задачи рас- пределения ресурсов на сетевых графиках и задачи синтеза ком- муникационных систем при наличии неопределенных факторов и без них. Излагается также метод моментов и его применение к различным прикладным задачам (нормальные решения систем линейных уравнений, интегральные уравнения Фредгольма пер- вого рода, линейные задачи теории управления). Завершает книгу рассмотрение теории управляемых марковских процессов и их применения к задачам экологии. Этот материал интересен сов- местным рассмотрением экологических и экономических задач и статистическим подходом к проблеме существования устойчивых экологических систем. В дополнения включен материал, представляющий интерес для ряда специальностей. Книга предназначена для студентов, обучающихся по специ- альностям «Прикладная математика» и «Экономическая кибер- нетика», а также полезна преподавателям и научным работни- кам ряда других специальностей. В заключение автор выражает благодарность сотрудникам кафедры исследования операций факультета вычислительной ма- тематики и кибернетики МГУ и Вычислительного центра АН СССР, которые участвовали в обсуждении материала книги. Автор ЛИТЕРАТУРА 1. Авондо-Бодино Дж. Применение в экономике теории графов.—М: Про- гресс, 1968. 2. Аоки М. Введение в методы оптимизации.—М.: Наука, 1977. 3. Ахнезер Н. И. Лекции по теории аппроксимации.—М.: Наука, 1965. 4. Ашманов С. А. Линейное программирование.—М.: Наука, 1981. 5. Базара М., Шетти К. Нелинейное программирование.—М.: Мир, 1982. 6. Гейл Д. Теория линейных экономических моделей.—М.: ИЛ, 1963. 7. Гермейер Ю. Б. Введение в теорию исследования операций.—М.: Наука, 1971. 8. Гермейер Ю. Б. Игры с непротивоположными интересами. — Н.: Наука, 1976. 9. Г урин. Л. С.. Дымарский Я. С., Меркулов А. Д. Задачи и методы опти- мального распределения ресурсов.—М.: Сов. радио, 1968. 10. Давыдов Э. Г. О применении стильтьесовских моментов//ЖВМ и МФ 7. 1967. № 5. 11. Давыдов Э. Г. О распределении ресурсов на сетях/Сб.: Системы рас- пределения ресурсов на графах.—М.: ВЦ АН СССР,, 1970. 12. Давыдов Э. Г. О решении интегральных уравнений Фредгольма 1-го рода//ДАН СССР. 1974. Т. 219. № 5. С. 1053—1056. 13. Давыдов Э. Г. Методы и модели теории антагонистических игр.—М.: МГУ, 1978. 14. Давыдов Э. Г. Игры, графы, ресурсы.—М.: Радио и связь, 1981. 15. Давыдов Э. Г., Злобина С. В. Применение геометрического программиро- вания к сетевому планированию.—М.: ВЦ АН СССР, 1981. 16. Давыдов Э. Г., Исиченко И. В. Некоторые дискретные задачи теории управления.—М.: ВЦ АН СССР, 1988. 17. Давыдов Э. Г., Ринго Н. И. Задачи оптимального управления в незамк- нутых динамических моделях производства/В сб.: Кибернетику на службу ком- мунизму—М.: Энергия, 1971. Т. 6. 18. Давыдов Э. Г., Ринго Н. И. Некоторые вопросы теории L-проблемы мо- ментов//Изв. АН СССР. Техническая кибернетика. 1981. № 2. С, 40—48. 19. Давыдов Э. Г., Ринго Н. И. Некоторые вопросы теории Z.-проблемы моментов//Изв. АН СССР. Техническая кибернетика. 1982. № 3. С. 205—208. 20. Давыдов Э. Г., Ринго Н. И. О решении L-проблемы моментов на симп- лексе и его применении//ДАН СССР. 1986. Т. 286. № 3. С. 569—573. 21. Давыдов Э. Г., Косорукое О. А. Некоторые вопросы нелинейного син- теза коммутационных сетей//Вести. МГУ. Сер- 15. Вычислительная матема- тика и кибернетика. 1986. № 2. С. 31—36. 22. Давыдов Э. Г., Большаков С. Ю. Теоретико-групповые методы агреги- рования в сетевых задачах.—М.: ВЦ АН СССР, 1986. 23. Давыдов Э. Г., Сигал И. X. О применении штрафных функций в зада- чах целочисленного программирования//Изв. АН СССР. Техническая киберне- тика. 197.2. № 1. С. 28—31. 24. Данскин. Дж. Теория максимина.—М.: Сов. радио, 1970. 25. Даффин Р., Питтерсон Э., Зенер К. Геометрическое программирова- ние.—М.: Мир, 1972. 380 26. Демьянов В. Ф., Малоземов В. Н. Введение в минимакс.—М.: Наука, 1972. г1. Дегтярев Ю. И. Исследование операций.—М.: Высшая школа, 1986. 28. Зуховицкий С. И; Авдеева Л. И. Линейное и выпуклое программирова- ние—М.: Наука, 1967. 29. Зуховицкий С. И., Радчик И. А. Математические методы сетевого пла- нирования.—М.: Наука, 1965. 30. Карлин С. Математические методы в теории игр, программировании и экономике.—М.: Мир, 1964. 31. Кемени Дж. Снелл Дж. Конечные цепи Маркова.—М.: Наука, 1970. 32. Колмогоров А. Н; Фомин С. В. Элементы теории функций и функцио- нального анализа.—М.: Наука, 1976. 33. Красовский Н. Н. Теория управления движением.—М.: Наука, 1968. 34. Крейн М. Г., Нудельман А. А. Проблема моментов Маркова и экстре- мальные задачи.—М.: Наука, 1973. 35. Майн X., Осаки С. Марковские процессы принятия решения.—М.: Нау- ка, 1977. 36. Мухачева Э. А., Рубинштейн Г. Ш. Математическое программирова- ние. — Новосибирск: Наука, 1977. 37. Романовский И. В. Магистральные теоремы для полумарковских процес- сов//Тр. МИАИ. 111. 1970. 38. Селигмен Б. Основные течения современной экономической мысли.—М.: Прогресс, 1968. 39. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач.— М.: Наука, 1986. 40. Фиакко А., Мак-Кормик Г. Нелинейное программирование.—М.: Мир, 1972. 41. форд Л., Фалкерсан Д. Потоки в сетях. — М.: Мир, 1966. 42. Ховард Р. А. Динамическое программирование и марковские процес- сы.—М.: Сов. радио, 1964. 43. Холл М. Теория групп.—М.: ИЛ, 1962. 44. Avrial M., Williams A. On the primal and dual constaint set in geometric programming. J. Math. Analisis and Applications. V. 32. 1970. Предисловие . . . . . . ..............••.••.••• Глава 1. Исследование операций и теория игр . . . .......... § 1.1. Методологические и математические основы исследования опе- раций . . . . . ...................... § 1.2. Платежная матрица игры, нахождение максимина и минимак- са. Седловые точки, смешанные стратегии. Основная теорема для игр с выпукло-вогнутыми платежными функциями .... § 1.3. Свойства оптимальных смешанных стратегий конечных игр, крайние оптимальные смешанные стратегии, игры с полной ин- формацией . . . . . . ................... § 1.4. Связь теории игр с линейным и выпуклым программированием § 1.5. Теорема об аппроксимации непрерыных игр конечными играми. Свойства решений непрерывных игр .............. § 1.6. Специальные задачи выпуклого программирования . ..... § 1.7. Доминирование стратегий ... . . ............. § 1.8. Прямые суммы и прямые произведения игр, симметризация игр § 1.9. Блочно-постоянные игры, инвариантные игры . ........ § 1.10. Игры с ограничениями . . . ............... § 1.11. Обслуживание дискретных объектов конечным числом спо- собов . . . . . ...................... § 1.12. Решение конкретных примеров игр с ресурсами . ...... § 1.13. Вогнутые игры одного переменного . . ........... § 1.14. Вогнутые и выпуклые игры векторного аргумента ...... § 1.15. Игры типа бабочки . . . ................. § 1.16. Конечные игры с выбором момента времени . . ...... Глава 2. Задачи оптимального распределения ресурсов на сетях ..... § 2.1. Необходимые сведения из теории графов . ......... § 2.2. Основы сетевого планирования . . . ............ § 2.3. Оптимальное распределение ресурсов на сетевых графиках . . § 2.4. Задача минимизации времени выполнения всех работ при на- личии неопределенных факторов . . . ............ § 2.5. Игровая задача распределения ресурсов на сетевых графиках при наличии неопределенных факторов ............ § 2.6. Задача минимизации стоимости выполнения комплекса работ при наличии неопределенных факторов и заданном директив- ном времени выполнения всех работ . . . ......... § 2.7. Применение сепарабельного программирования к задачам рас- пределения ресурсов на сетевых графиках . ......... § 2.8. Постановка задач распределения ресурсов на сетевых графи- ках как задач геометрического программирования ...... § 2.9. Теоретико-групповые методы агрегирования в задачах распре- деления ресурсов на сетевых графиках . ........... § 2.10. Потоки в сетях . . . . .................. § 2.1 Г. Задачи распределения ресурсов на транспортных сетях при отсутствии неопределенных факторов . . . ......... § 2.12. Задачи распределения ресурсов на транспортных сетях при наличии неопределенных факторов . . . .......... § 2.13. Игровая задача синтеза коммутационных сетей . . ..... § 2.14. Линейные задачи синтеза коммутационных сетей . ..... § 2.15. Задачи синтеза коммутационных сетей как задачи сепара- бельного программирования ................. § 2.16. Теоретико-групповые методы агрегирования в задачах синте- за коммутационных сетей ................... § 2.17. Элементарные задачи распределения ресурсов на сетевых графиках и транспортных сетях и их связь с классическими задачами распределения ресурсов. Лемма В. Гиббса и принцип уравнения Ю. М. Гермейера, их взаимосвязь .......... Глава 3. Метод моментов и его применения . . . ........... § 3.1. Необходимые сведения из функционального анализа и теории меры . . . . . . ..................... § 3.2. /.-проблема моментов в банаховых пространствах ...... § 3.3. Некоторые применения метода моментов . ......... Глава 4. Управляемые марковские процессы и их применение ...... § 4.1. Классификация сильно связных графов и ее приложение к тео- рии матриц . . ....................... § 4.2. Суммирование последовательностей по Абелю и Чезаро .... § 4.3. Эргодические марковские процессы и их свойства ...... § 4.4. Управляемые марковские процессы . . ........... § 4.5. Задача управления экологической системой ......... Дополнения. 1. О решении задач целочисленного программирования . . . 2. О незамкнутых моделях экономического развития .... 3. Теорема Хана — Банаха для пространств с несимметрич- ной нормой . . .................... Литература ... . ..........................