1 ШЕСТОЕ ИЗДАНИЕ >"''1 »v,, Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ ХЭМДИ А. ТАХА Университет Арканзаса, Фейетвилл Издательский дом "Вильяме" Москва • Санкт-Петербург • Киев 2001 SIXTH EDITION OPERATIONS RESEARCH An Introduction HAMDYA.TAHA University of Arkansas, Fayetteville PRENTICE HALL Upper Saddle River, New Jersey 07458 ББК 32.973.26-018.2.75 Т24 УДК 681.3.07 Издательский дом "Вильяме" Зав. редакцией С.Н. Тригуб Перевод с английского канд.физ.-мапг.наук В.И. Тюппш (главы 9-21), канд.физ.-мат.наук А.А. Минько (все остальное) По общим вопросам обращайтесь в Издательский дом "Вильяме" по адресу: info@williamspublishing.com, http://www.williamspublishing.com Таха, Хэмди, А. 124 Введение в исследование операций, 6-е издание. : Пер. с англ. — М. : Издательский дом "Вильяме", 2001. — 912с.: ил. — Парал. тит. англ. ISBN 5-8459-0180-4 (рус.) Исследование операций, как научная дисциплина и практические методы, ориентировано на решение практических задач, которые можно корректно описать с помощью той или иной математической модели с целью получения оптимального решения. Данная книга может слу- жить учебным пособием по теории и практическому применению методов исследования опе- раций. Каждая тема начинается с вводного материала, доступного студентам начальных кур- сов, далее уровень изложения постепенно повышается и рассчитан уже на студентов старших курсов. В конце каждой главы приводится набор комплексных задач, связанных излагаемой с темой, которые значительно углубляют и расширяют ее. Написанная без излишнего академизма, но достаточно строго, книга будет интересна ши- рокому кругу читателей: студентам, аспирантам и преподавателям высших учебных заведений, экономистам, инженерам, разработчикам программного обеспечения и др. ББК 32.973.26-018.2.75 Все названия программных продуктов являются зарегистрированными торговыми марками соответст- вующих фирм. Никакая часть настоящего издания ни в каких целях не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами, будь то электронные или механические, включая фотокопирова- ние и запись на магнитный носитель, если на это нет письменного разрешения издательства Prentice Hall, Inc. Authorized translation from the English language edition published by Prentice Hall, Inc., Copyright © 1997 All rights reserved. No p'art of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from the Publisher. Russian language edition published by Williams Publishing House according to the Agreement with R&l Enterprises International, Copyright 0 2000 ISBN 5-8459-0180-4 (рус.) О Издательский дом "Вильяме", 2001 ISBN 0-13-272915-6 (англ.) © Prentice Hall, Inc., 1997 Оглавление Предисловие 15 Глава 1. Исследование операций: обзор 17 ЧАСТЬ I. ДЕТЕРМИНИРОВАННЫЕ МОДЕЛИ 25 Глава 2. Введение в линейное программирование 26 Глава 3. Симплекс-метод 84 Глава 4. Двойственность и анализ чувствительности 127 Глава 5. Транспортные модели 179 Глава 6. Сетевые модели 223 Глава 7. Теория линейного программирования 286 Глава 8. Целевое программирование 354 Глава 9. Целочисленное линейное программирование 371 Глава 10. Детерминированные модели динамического программирования 412 Глава 11. Детерминированные модели управления запасами 439 ЧАСТЬ II. ВЕРОЯТНОСТНЫЕ МОДЕЛИ 475 Глава 12. Основы теории вероятностей 476 Глава 13. Методы прогнозирования 503 Глава 14. Теория игр и принятия решений 514 Глава 15. Вероятностное динамическое программирование 562 Глава 16. Вероятностные модели управления запасами 574 Глава 17. Системы массового обслуживания 596 Глава 18. Имитационное моделирование 667 Глава 19. Марковские процессы принятия решений 705 ЧАСТЬ III. НЕЛИНЕЙНЫЕ МОДЕЛИ 737 Глава 20. Классическая теория оптимизации 738 Глава 21. Алгоритмы нелинейного программирования 773 Приложение А. Краткий обзор теории матриц 807 Приложение Б. Введение в SIMNET II 820 Приложение В. Инсталляция и выполнение программ TORA и SIMNET II 864 Приложение Г. Статистические таблицы 865 Приложение Д. Ответы к упражнениям 869 Оглавление 5 Содержание Предисловие 15 Благодарности ]6 Глава 1. Исследование операций: обзор 17 1.1. Математические модели исследования операций 17 1.2. Методы исследования операций 19 1.3. Имитационное моделирование 20 1.4. Искусство моделирования 21 1.5. Об этой книге 22 Литература 23 Литература, добавленная при переводе 23 ЧАСТЬ I. ДЕТЕРМИНИРОВАННЫЕ МОДЕЛИ 25 Глава 2. Введение в линейное программирование 26 2.1. Введение 26 2.2. Ограничения в модели линейного программирования 26 2.3. Графическое решение задачи линейного программирования 30 2.3.1. Нахождение максимума целевой функции 30 2.3.2. Нахождение минимума целевой функции 34 2.3.3. Дополнительные переменные 36 2.4. Графический анализ чувствительности 3 8 2.4.1. Изменение коэффициентов целевой функции 39 2.4.2. Стоимость ресурсов 43 2.5. Компьютерное решение задач ЛП 48 2.6. Примеры моделей ЛП 56 2.7. Заключение 79 Литература 80 Литература, добавленная при переводе 80 Комплексные задачи 80 Глава 3. Симплекс-метод 84 3.1. Введение 84 3.2. Стандартная форма задачи ЛП и ее базисные решения 84 3.2.1. Стандартная форма задачи ЛП 84 3.2.2. Определение базисных решений 87 3.2.3. Свободные переменные и базисные решения 89 3.3. Алгоритм симплекс-метода 91 3.4. Искусственное начальное решение 103 6 Содержание 3.4.1.M-метод 103 3.4.2. Двухэтапный метод 109 3.5. Особые случаи применения симплекс-метода 114 3.5.1. Вырожденность 114 3.5.2. Альтернативные оптимальные решения 117 3.5.3. Неограниченные решения 120 3.5.4. Отсутствие допустимых решений 122 3.6. Заключение 124 Литература 124 Литература, добавленная при переводе 125 Комплексные задачи 125 Глава 4. Двойственность и анализ чувствительности 127 4.1. Введение 127 4.2. Определение двойственной задачи 12 7 4.3. Соотношения между оптимальными решениями прямой и двойственной задач 132 4.4. Экономическая интерпретация двойственности 137 4.4.1. Экономическая интерпретация переменных двойственной задачи 138 4.4.2. Экономическая интерпретация ограничений двойственной задачи 140 4.5. Двойственный симплекс-метод 143 4.6. Матричное представление симплексных вычислений 150 4.7. Анализ чувствительности оптимального решения 158 4.7.1. Изменения, влияющие на допустимость решения 159 4.7.2. Изменения, влияющие на оптимальность решения 170 4.8. Заключение 176 Литература 176 Литература, добавленная при переводе 177 Комплексные задачи 177 Глава 5. Транспортные модели 179 5.1. Определение транспортной модели 179 5.2. Нетрадиционные транспортные модели 187 5.3. Решение транспортной задачи 192 5.3.1. Определение начального решения 193 5.3.2. Итерационный алгоритм решения транспортной задачи 198 5.3.3. Интерпретация метода потенциалов как симплекс-метода 205 5.4. Задача о назначениях 206 5.4.1. Венгерский метод 207 5.4.2. Интерпретация венгерского метода как симплекс-метода 212 5.5. Транспортная модель с промежуточными пунктами 213 5.6. Заключение 218 Литература 218 Литература, добавленная при переводе 219 Комплексные задачи 219 Глава 6. Сетевые модели 223 6.1. Обзор применения сетевых моделей 223 Содержание 7 6.2. Основные определения 224 6.3. Алгоритм построения минимального остовного дерева 225 6.4. Задача нахождения кратчайшего пути 230 6.4.1. Практические примеры задачи нахождения кратчайшего пути 230 6.4.2. Алгоритм нахождения кратчайшего пути 234 6.5. Задача о максимальном потоке 243 6.5.1. Перебор разрезов 244 6.5.2. Алгоритм нахождения максимального потока 245 6.6. Нахождение потока наименьшей стоимости 254 6.6.1. Сетевая модель 255 6.6.2. Сетевая модель как задача линейного программирования 257 6.6.3. Симплексный алгоритм для сетей с ограниченной пропускной способностью 262 6.7. Методы сетевого планирования 269 6.7.1. Построение сети проекта 269 6.7.2. Метод критического пути 275 6.7.3. Построение временного графика 278 6.8. Заключение 283 Литература 283 Литература, добавленная при переводе 283 Комплексные задачи 283 Глава 7. Теория линейного программирования 286 7.1. Введение 286 7.2. Векторы и базисы 286 7.2.1. Матричное представление стандартной задачи ЛП 286 7.2.2. Векторное представление базисов 288 7.2.3. Базисные решения 290 7.3. Обоснование симплекс-метода 292 7.3.1. Выпуклые множества 292 7.3.2. Сходимость симплексного алгоритма к оптимальному решению 293 7.4. Матричное представление симплекс-таблиц 295 7.5. Эффективные вычислительные алгоритмы 302 7.5.1. Модифицированный симплекс-метод 303 7.5.2. Алгоритм решения задач с ограниченными переменными 311 7.5.3. Метод декомпозиции 318 7.6. Двойственность 329 7.6.1. Матричное представление двойственной задачи 329 7.6.2. Оптимальное решение двойственной задачи 329 7.7. Параметрическое линейное программирование 334 7.7.1. Параметрическое изменение коэффициентов целевой функции 334 7.7.2. Параметрическое изменение правых частей ограничений 337 7.8. Метод Кармаркара 341 7.8.1. Основная идея метода Кармаркара 341 7.8.2. Алгоритм Кармаркара 342 7.9. Заключение 351 Литература . 351 Литература, добавленная при переводе 351 Комплексные задачи 352 8 Содержание Глава 8. Целевое программирование 354 8.1. Несколько целевых функций 354 8.2. Формулировка задачи целевого программирования 354 8.3. Алгоритмы целевого программирования 359 8.3.1. Метод весовых коэффициентов 360 8.3.2. Метод приоритетов 363 8.4. Заключение 368 Литература 368 Литература, добавленная при переводе 368 Комплексные задачи 369 Глава 9. Целочисленное линейное программирование 371 9.1. Введение 371 9.2. Примеры задач целочисленного программирования 371 9.3. Методы решения задач целочисленного программирования 387 9.3.1. Метод ветвей и границ 388 9.3.2. Аддитивный алгоритм для задач с двоичными переменными 395 9.3.3. Метод отсекающих плоскостей 402 9.4. Заключение 408 Литература 408 Литература, добавленная при переводе 409 Комплексные задачи 409 Глава 10. Детерминированные модели динамического программирования 412 10.1. Введение 412 10.2. Рекуррентная природа вычислений в ДП 412 10.3. Рекуррентные алгоритмы прямой и обратной прогонки 416 10.4. Некоторые приложения динамического программирования 417 10.4.1. Задача о загрузке 418 10.4.2. Задача планирования рабочей силы 424 10.4.3. Задача замены оборудования 427 10.4.4. Задача инвестирования 431 10.4.5. Модели управления запасами 435 10.5. Проблема размерности 435 10.6. Заключение 438 Литература 438 Литература, добавленная при переводе 438 Комплексная задача 438 Глава 11. Детерминированные модели управления запасами 439 11.1. Введение 439 11.2. Обобщенная модель управления запасами 439 11.3. Статические модели управления запасами 440 11.3.1. Классическая задача экономичного размера заказа 440 11.3.2. Задача экономичного размера заказа с разрывами цен 446 Содержание 9 11.3.3. Многопродуктовая статическая модель с ограниченной вместимостью склада 450 11.4. Динамические задачи экономичного размера заказа 453 11.4.1. Модель при отсутствии затрат на оформление заказа 454 11.4.2. Модель с затратами на оформление заказа 459 11.5. Заключение 472 Литература 472 Литература, добавленная при переводе 472 Комплексные задачи 472 ЧАСТЬ II. ВЕРОЯТНОСТНЫЕ МОДЕЛИ 475 Глава 12. Основы теории вероятностей 476 12.1. Введение 476 12.2. Законы теории вероятностей 476 12.2.1. Закон сложения вероятностей 477 12.2.2. Условные вероятности 478 12.3. Случайные величины и распределения вероятностей 480 12.4. Математические ожидания и моменты случайной величины 482 12.4.1. Математическое ожидание и дисперсия случайной величины 483 12.4.2. Совместные распределения вероятностей 485 12.5. Некоторые распределения вероятностей 489 12.5.1. Биномиальное распределение 489 12.5.2. Распределение Пуассона 490 12.5.3. Отрицательное экспоненциальное распределение 492 12.5.4. Нормальное распределение 493 12.6. Эмпирические распределения 495 12.7. Заключение 502 Литература 502 Литература, добавленная при переводе 502 Глава 13. Методы прогнозирования 503 13.1. Введение 503 13.2. Прогнозирование с использованием скользящего среднего 503 13.3. Экспоненциальное сглаживание 507 13.4. Регрессионный анализ 509 13.5. Заключение 513 Литература 513 Литература, добавленная при переводе 513 Глава 14. Теория игр и принятия решений 514 14.1. Условия принятия решений 514 14.2. Принятие решений в условиях определенности 514 14.2.1. Метод анализа иерархий 515 14.3. Принятие решений в условиях риска 524 14.3.1. Критерий ожидаемого значения 525 10 Содержание 14.3.2. Другие критерии ожидаемого значения 533 14.4. Принятие решений в условиях неопределенности 542 14.5. Теория игр 547 14.5.1. Оптимальное решение игры двух лиц с нулевой суммой 547 14.5.2. Решение матричных игр в смешанных стратегиях 551 14.6. Заключение 558 Литература 558 Литература, добавленная при переводе 558 Комплексные задачи 559 Глава 15. Вероятностное динамическое программирование 562 15.1. Введение 562 15.2. Азартная игра 562 15.3. Задача инвестирования 565 15.4. Максимизация вероятности достижения цели 569 Литература 572 Литература, добавленная при переводе 573 Комплексные задачи 573 Глава 16. Вероятностные модели управления запасами 574 16.1. Введение 574 16.2. Модель с непрерывным контролем уровня запаса 574 16.2.1. "Рандомизированная" модель экономичного размера заказа 574 16.2.2. Стохастический вариант модели экономичного размера заказа 577 16.3. Одноэтапные модели 582 16.3.1. Модель при отсутствии затрат на оформление заказа 583 16.3.2. Модель при наличии затрат на оформление заказа 587 16.4. Многоэтапные модели 590 16.5. Заключение 592 Литература 593 Литература, добавленная при переводе 593 Комплексные задачи 593 Глава 17. Системы массового обслуживания 596 17.1. Введение 596 17.2. Основные компоненты моделей массового обслуживания 598 17.3. Экспоненциальное распределение в системах массового обслуживания 600 17.3.1. Свойство отсутствия последействия 601 17.3.2. Определение экспоненциального распределения 603 17.4. Модели рождения и гибели (связь между экспоненциальным и пуассоновским распределениями) 605 17.4.1. Модель чистого рождения 606 17.4.2. Модель чистой гибели 609 17.5. Обобщенная модель системы массового обслуживания 612 17.6. Специализированные системы обслуживания с пуассоновским распределением 618 17.6.1. Функциональные характеристики стационарных систем обслуживания 620 Содержание 11 17.6.2. Модели с одним сервисом 623 17.6.3. Модели с параллельными сервисами 635 17.6.4. Модель (M/M/R) : (GD/K/K) при R < К 646 17.7. Модель (M/G/1) : (GD/°°/°°). Формула Поллачека-Хинчина 650 17.8. Другие модели массового обслуживания 653 17.9. Модели принятия решений в теории массового обслуживания 653 17.9.1. Модель со стоимостными характеристиками 654 17.9.2. Модель предпочтительного уровня обслуживания 660 17.10. Заключение 662 Литература 662 Литература, добавленная при переводе 663 Комплексные задачи 663 Глава 18. Имитационное моделирование 667 18.1. Что такое имитационное моделирование 667 18.2. Метод Монте-Карло 668 18.3. Типы имитационных моделей 673 18.4. Элементы дискретного моделирования 674 18.4.1. Общее определение событий 674 18.4.2. Генерирование выборочных значений 676 18.5. Генерирование случайных чисел 687 18.6. Механика дискретной имитации 689 18.7. Методы сбора статистических данных 694 18.7.1. Метод подынтервалов 695 18.7.2. Метод повторения 697 18.7.3. Метод циклов 698 18.8. Языки имитационного моделирования 700 18.9. Заключение 704 Литература 704 Литература, добавленная при переводе 704 Глава 19. Марковские процессы принятия решений 705 19.1. Марковская задача принятия решений 705 19.2. Модель динамического программирования с конечным числом этапов 707 19.3. Модель с бесконечным числом этапов 712 19.3.1. Метод полного перебора 713 19.3.2. Метод итераций по стратегиям без дисконтирования 716 19.3.3. Метод итераций по стратегиям с дисконтированием 719 19.4. Применение методов линейного программирования 722 19.5. Заключение 726 19.6. Приложение: обзор теории цепей Маркова 726 19.6.1. Марковские процессы 727 19.6.2. Цепи Маркова 727 Литература 735 Литература, добавленная при переводе 735 12 Содержание ЧАСТЬ III. НЕЛИНЕЙНЫЕ МОДЕЛИ 737 Глава 20. Классическая теория оптимизации 738 20.1. Введение 738 20.2. Экстремальные задачи без ограничений 738 20.2.1. Необходимые и достаточные условия существования экстремума 739 20.2.2. Метод Ньютона-Рафсона 744 20.3. Задачи на экстремум при наличии ограничений 745 20.3.1. Ограничения в виде равенств 746 20.3.2. Ограничения в виде неравенств 764 20.4. Заключение 772 Литература 772 Литература, добавленная при переводе 772 Глава 21. Алгоритмы нелинейного программирования 773 21.1. Алгоритмы решения задач без ограничений 773 21.1.1. Методы прямого поиска 773 21.1.2. Градиентный метод 775 21.2. Алгоритмы решения задач с ограничениями 779 21.2.1. Сепарабельное программирование 779 21.2.2. Квадратичное программирование 789 21.2.3. Геометрическое программирование 793 21.2.4. Стохастическое программирование 798 21.2.5. Метод линейных комбинаций 802 21.2.6. Алгоритм последовательной безусловной максимизации 805 21.3. Заключение 806 Литература 806 Литература, добавленная при переводе 806 Приложение А. Краткий обзор теории матриц 807 A.I. Векторы 807 A.I.I. Определение вектора 807 А. 1.2. Сложение и вычитание векторов 807 А. 1.3. Умножение вектора на скаляр 807 A.I .4. Линейная независимость векторов 807 А.2. Матрицы 808 А.2.1. Определение матриц 808 А.2.2. Типы матриц 808 А.2.3. Арифметические операции над матрицами . 809 А.2.4. Определитель квадратной матрицы 810 А.2.5. Невырожденная матрица 812 А.2.6. Обратная матрица 812 А.2.7. Методы вычисления обратных матриц 813 А.3. Квадратичные формы 816 А.4. Выпуклые и вогнутые функции 817 Литература 817 Литература, добавленная при переводе 818 Задачи 818 Содержание 13 Приложение Б. Введение в SIMNET II 820 Б. 1. Сетевые модели 820 Б.2. Операторы SIMNET II 820 Б.2.1. Узел источника 821 Примеры 822 Б.2.2. Узел очереди 823 Примеры 824 Б.2.3. Узел средств обслуживания 824 Примеры 825 Б.2.4. Дополнительный узел 826 Пример ,827 Б.2.5. Основные правила работы с узлами 827 Б.З. Математические выражения в SIMNET II 829 Б.4. Пример модели, созданной в SIMNET II 831 Б.5. Маршрутизация транзакций 833 Б.5.1. Выбор маршрута 834 Примеры 834 Б.5.2. Маршрутизация с помощью поля *Т 836 Б.6. Задание дуг в сетевых моделях 839 Б.7. Статистические переменные 845 Б.8. Логические переключатели 847 Б.9. Специальные операторы присваивания 850 Б.9.1. Активизация и деактивизация источников 851 Б.9.2. Сбор значений статистических переменных 852 Б.9.3. Операторы управления транзакциями 852 Б. 10. Начальные данные 857 Б. 10.1. Начальное содержимое очередей и средств обслуживания 857 Б. 10.2. Задание плотностей вероятностей 858 Б. 10.3. Таблично-заданные функции 859 Б.10.4. Задание элементов массивов 860 Б. 11. Заключение 862 Литература 863 Приложение В. Инсталляция и выполнение программ ТОНА и SIMNET II 864 B.I. Инсталляция и выполнение 864 Приложение Г. Статистические таблицы 865 Приложение Д. Ответы к упражнениям 869 14 Содержание Предисловие Поскольку первое издание этой книги вышло в далеком 1971 году1, я вынужден был внести многочисленные изменения как в стиль изложения, так и в содержание шестого издания данной книги. Я пришел к выводу, что внесение отдельных изменений и исправ- лений может привести лишь к непреднамеренным искажениям и ошибкам. Я посчитал необходимым добавить новые упражнения и изменить многие "старые" упражнения. Та- ким образом, я пришел к заключению, что в этом издании надо существенно изменить как основной материал, так и упражнения. В данной книге первые 18 глав переписаны полностью. Оставшиеся три главы пере- смотрены и исправлены. Добавлено много нового материала, старый текст сокращен или вовсе удален. В этом издании существенно изменен уровень излагаемого материала, в частности о линейном программировании. Теперь каждая тема начинается с вводного материала, доступного студентам первых курсов, далее уровень изложения постепенно повышается, предлагая материал, доступный для студентов старших курсов. Я использовал многочисленные примеры и упражнения как средство для представле- ния основных идей и принципов, лежащих в основе различных методов теории исследо- вания операций. Каждый представленный в книге решенный пример состоит из ряда подзадач, которые охватывают в определенных пропорциях (надеюсь, сбалансирование) вопросы создания и формализации моделей, вычислительные аспекты и теоретические основы. В конце каждой главы приводится набор комплексных задач, связанных с темой, излагаемой в главе, и значительно углубляющих и расширяющих ее. Шестое издание со- держит более 1000 упражнений (60% из них появились только в этом издании). Книга разбита на три части. Часть Детерминированные модели включает темы ли- нейного программирования, сетевых моделей, многокритериальной оптимизации (це- левого программирования), динамического (детерминированного) программирования и моделей управления запасами. Тема линейного программирования изложена так, что на- чинающий студент получит здесь основы практического применения методов, включая теорию двойственности и анализ чувствительности. Глава, посвященная сетевым моде- лям, содержит обобщенные модели и алгоритмы, включая алгоритм нахождения крат- чайших путей (алгоритм Флойда), а также исследование потоков в сетях с помощью ме- тодов линейного программирования и показывает их связь с транспортными моделями. В отдельной главе собран углубленный материал по теории линейного программирова- ния. Отдельные главы посвящены целевому и целочисленному программированию. В главе о целочисленном программировании основной упор сделан на применении много- обещающего метода ветвей и границ. Новые приложения также включены в главу, по- священную динамическому программированию. Детерминированные модели управления запасами вынесены в отдельную главу. Часть Вероятностные модели начинается с глав, содержащих основы теории вероят- ностей и математической статистики. Материал о теории принятия решений охватывает аналитический иерархический подход и раскрывает роль функции полезности. В теории 1 Ранее на русский язык было переведено 3-е издание этой книги: Таха X. Введение в исследование опера- ций: В 2 кн. — М.: Мир, 1985. — Прим. ред. Предисловие 15 игр метод, основанный на линейном программировании, в настоящем издании, с одной стороны, упрощен, с другой стороны — усилен. Стохастическое динамическое програм- мирование представлено новой главой, за которой следует глава о вероятностных моде- лях управления запасами. Новое изложение теории массового обслуживания позволяет студентам изучить как ее практическое применение, так и саму теорию или, при жела- нии, сосредоточиться только на практических аспектах темы. В отдельную главу выне- сены основы и принципы дискретного имитационного моделирования, а введение в язык моделирования SIMMET II перенесено в Приложение Б. Материал о марковских процес- сах принятия решений переписан в соответствии с новой концепцией книги. Часть Нелинейные модели повторяет материал пятого издания, но она также подвер- глась значительным изменениям. Программное обеспечение, сопровождающее эту книгу, включает программу TORA и "студенческую" версию языка SIMMET II.' Программа TORA реализует различные ал- горитмы, описанные в книге, и может помочь в их изучении либо может просто исполь- зоваться для решения соответствующих задач. SIMMET II имеет все возможности и средства, присущие ее коммерческой версии, — различие заключается только в том, что данная версия имеет ограничения на размер решаемых задач. Книга имеет пять приложений. Приложение А содержит обзор теории матриц. При- ложение Б предлагает введение в язык имитационного моделирования SIMMET II. Ма- териал, посвященный инсталляции и использованию программного обеспечения TORA и SIMMET II, представлен в Приложении В. Приложение Г содержит таблицы нормально- го, Стьюдента и 5С2 распределений. Ответы к половине упражнений представлены в При- ложении Д. Благодарности Многие мои коллеги поддержали меня в работе над этой книгой своими советами и критическими замечаниями. Я глубоко благодарен им всем и выражаю надежду на наше дальнейшее взаимовыгодное сотрудничество. Особо хочу поблагодарить профессоров Гая Карри (Guy Curry) из Техасского университета, Дона Э. Дела (Don E. Deal) из уни- верситета Хьюстона, Ричарда Френсиса (Richard Francis) из университета Флориды, Яс- сера Хосни (Yasser Hosni) из Флоридского центрального университета, Аллена С. Шер- мана (Alien С. Schuermann) из университета шт. Оклахома и Эвангелоса Триантафиллу (Evangelos Triantaphyllou) из университета шт. Луизиана. Я также благодарен своему новому издателю Prentice Hall за мягкий и гладкий переход под его покровительство. Выражаю особую благодарность моим редакторам Бейни М. де Леон (Bayani М. de Leon), Алисе Дворкин (Alice Dworkin) и Редоре Пифиаренда (Rhodora Pefiaranda) за их профессиональную работу по подготовке шестого издания книги. ХэмдиА. Таха 1 Упомянутое программное обеспечение можно найти на Web-узле Издательского дома "Вильяме" по ад- ресу: www.williamspublishing.com. — Прим. ред. 16 Предисловие _________________________Глава 1 Исследование операций:обзор 1.1. Математические модели исследования операций Предположим, что в соответствии с деловыми обязательствами вам необходимо в те- чение пяти недель пять раз посетить город В (постоянное ваше пребывание — город А). Вы должны быть в городе В в понедельник первой недели и окончательно возвратиться в город А в среду пятой недели. Заказной билет из города А в город В и обратно стоит $400, однако вы можете получить 20% скидки от стоимости билетов, если вылет придет- ся на конец недели. Кроме того, следует учесть, что стоимость билета только в одну сто- рону равна 75% от стоимости заказного билета. Вы, естественно, хотите минимизировать стоимость перелетов. Как это сделать? Описанную ситуацию можно рассматривать как задачу принятия решений, где для нахождения оптимального решения требуется определить три основных компонента. ^0 \< 1. Что в данном случае считать альтернативными решениями? '\^ 2. Каким ограничениям должно удовлетворять возможное решение? ГГ) 3. По какому критерию должны отбираться альтернативные решения? '4 В нашей задаче возможны следующие альтернативы. •С" 1. Покупка пяти заказных билетов А-В-А (т.е. из города А в город В и обратно). 2. Покупка одного билета в одну сторону А-В, четырех билетов А-В-А, захватываю- щих конец недели, и одного "однонаправленного" билета В-А. 3. Покупка билета А-В-А для первой недели, причем между датами вылетов должен быть понедельник; для последней недели покупка билета А-В-А, между датами которого должна быть среда, причем первый и последний билеты должны захва- тывать последние дни недели; четыре билета А-В-А, между датами которых также есть последние дни недели. Ограничением в данной задаче являются дни прибытия: понедельник первой недели и среда пятой. В данном случае естественным критерием для оценивания возможных альтернатив является цена билетов. Альтернатива, обеспечивающая наименьшую стоимость билетов, будет наилучшей. В данном случае имеем следующие альтернативы. Альтернатива 1: стоимость билетов = 5 х 400 = $2000. Глава 1. Исследование операций: обзор 17 Альтернатива 2: стоимость билетов = 0.75 х 400 + 4 х 0.8 х 400 + 0.75 х 400 = $1800. Альтернатива 3: стоимость билетов = 5 х (0.8 х 400) = $1600. Очевидно, что наилучшей является третья альтернатива. Приведенный пример показывает основные принципиальные составляющие модели ис- следования операций (ИО), а именно альтернативы, ограничения и критерий отбора аль- тернатив. В общем случае в задачах принятия решений альтернативы зависят от опреде- ленного набора переменных, которые затем могут использоваться при формализации огра- ничений и критерия в виде подходящих математических функций. В результате формали- зации получаем математическую модель, содержащую изменяемые переменные, ограни- чения и функцию критерия, которая также называется целевой функцией. Решением ма- тематической модели будет такой набор значений переменных, который оптимизирует (максимизирует или минимизирует) функцию критерия и удовлетворяет всем ограниче- ниям. Такой набор переменных называется оптимальным допустимым решением. Типичную математическую модель ИО схематически можно представить следующим образом. Максимизация или минимизация целевой функции ______при условии выполнения ограничений.______ Пример 1.1—1 Рассмотрим следующую задачу. Среди всех прямоугольников с периметром фиксированной длины L необходимо найти прямоугольник максимальной площа- ди. Какую длину и ширину будет иметь такой прямоугольник? В этой задаче переменными будут длина / и ширина w прямоугольника. Пло- щадь прямоугольника А вычисляется по формуле А = lw. Таким образом, надо максимизировать величину А при условии, что длина периметра прямоугольника, вычисляемая по формуле 2(1 + w), равна заданной величине L. Математическая модель будет записана следующим образом. Максимизировать А •= lw при ограничении l+w=—. 2 Эту задачу можно решить, выразив из равенства / + w = L12 одну переменную (например, Г) через другую (w) и подставив ее в формулу целевой функции. В ре- зультате получим следующее. . (L } Lw , А= \—-w \w=——-w . [2 } 2 Как известно, функция А будет иметь экстремум при том значении w, при ко- тором производная по w этой функции будет обращаться в нуль. Другими слова- ми, надо решить уравнение dA L , - —=—-2w=0. dw 2 18 Глава 1 В результате получим решение w = L/4. Отрицательность второй производной при данном значении w доказывает, что эта точка действительно является точкой максимума функции А. Из равенства ограничения получаем, что / = L/4. Следова- тельно, оптимальным решением данной задачи будет w = L/4 и / = L/4, т.е. среди прямоугольников с фиксированным периметром максимальную площадь будет иметь квадрат. Хотя математические модели являются краеугольным камнем в изучении ИО, задача принятия решений не ограничивается построением и решением математических моде- лей. По большому счету, задача принятия решений содержит "нематериальные" факто- ры, которые трудно поддаются количественному определению, но, безусловно, значи- тельно влияют на качество получаемого решения. Среди них, конечно же, имеется и че- ловеческий фактор. Часто эффект от человеческого поведения может свести на "нет" са- мое оптимальное решение, полученное на основе любой математической модели. Иллю- страцией этого может служить широко известная проблема лифта. По многочисленным жалобам жильцов высотного дома на длительное ожидание лифта было оптимизировано время ожидания, рассчитанное на основе модели массового обслуживания. Но предло- женное решение не уменьшило поток жалоб. Дальнейшее изучение ситуации показало, что жильцам просто скучно ждать лифт. Проблема была решена, когда в холле возле лифтов повесили большие зеркала. Жалобы на длительное ожидание лифта прекрати- лись: теперь жильцы коротают время возле лифтов, разглядывая себя и других в зеркале, что, согласитесь, почти не надоедает. Математический аспект исследования операций обязательно должен рассматриваться в широком контексте всего процесса принятия решений. Это было осознано британски- ми учеными, которые стали "пионерами" в области ИО еще во время Второй мировой войны. Хотя их работы, в основном, были сосредоточены на оптимизации размещения ограниченных военных ресурсов, в команду разработчиков ИО входили также специали- сты по социологии, психологии и поведенческим наукам, что подчеркивало важность че- ' ловеческого фактора в процессе принятия решений. 1.2. Методы исследования операций В моделях исследования операций переменные, от которых зависят ограничения и целевая функция, могут быть дискретными (чаще всего целочисленными) и континуаль- ными (непрерывными). В свою очередь, ограничения и целевая функция делятся на ли- нейные и нелинейные. Задачи оптимизации, представленные этими моделями, дали тол- чок к разработке различных методов решения, которые должны учитывать соответст- вующие математические свойства этих моделей. Наиболее известными и эффективными из них являются методы линейного программирования, когда целевая функция и все ограничения будут линейными. Для решения математических моделей других типов предназначены методы динамического программирования, целочисленного про- граммирования, нелинейного программирования, многокритериальной оптимиза- ции и методы сетевых моделей. Практически все методы исследования операций порождают вычислительные алго- ритмы, которые являются итерационными по своей природе. Это подразумевает, что за- дача решается последовательно (итерационно), когда на каждом шаге (итерации) полу- Глава 1. Исследование операций: обзор I? чаем решения, постепенно сходящиеся к оптимальному решению. Итерационная приро- да алгоритмов обычно приводит к объемным однотипным вычислениям. В этом и за- ключается причина того, что эти алгоритмы разрабатываются, в основном, для реализа- ции с помощью вычислительной техники. Использование компьютера как неотъемлемого средства решения задач ИО порожда- ет определенные вычислительные сложности, а именно ошибки машинного округления. Такие ошибки особенно заметны при увеличении числа итераций. Проблема ошибок ок- ругления усугубляется, если переменные модели ИО должны принимать только целочис- ленные значения. Поскольку компьютер все вычисления выполняет в арифметике с пла- вающей запятой, точное представление некоторых целочисленных значений становится невозможным; в таком случае о решении можно только сказать, что оно принадлежит определенной области значений. Некоторые математические модели могут быть такими сложными, что их невозмож- но решить никакими доступными методами оптимизации. В этом случае остается только эвристический подход: поиск подходящего "хорошего" решения вместо оптимального. Эвристический подход предполагает наличие эмпирических правил, в соответствии с ко- торыми ведется поиск подходящего решения. Обычно эвристические алгоритмы выпол- няются значительно быстрее, чем алгоритмы нахождения точного решения. 1.3. Имитационное моделирование Несмотря на впечатляющие достижения математического моделирования, многие ре- альные ситуации невозможно адекватно представить с помощью соответствующих ма- тематических моделей. В одних случаях в этом "виновата" определенная "жесткость" математики как языка описания и представления событий и явлений. Кроме того, даже если есть возможность формализовать рассматриваемую жизненную ситуацию посред- ством построения математической модели, полученная на ее основе задача оптимизации может быть слишком сложной для современных алгоритмов решения задач этого класса. Альтернативой математическому моделированию сложных систем может служить имитационное моделирование. Этот вид моделирования часто является наилучшим (если не единственным) способом исследования реальных систем. Различие между мате- матической и имитационной моделями заключается в том, что в последней отношение между "входом" и "выходом" модели может быть явно не задано. Вместо явного матема- тического описания взаимоотношения между входными и выходными переменными ма- тематической модели, при имитационном моделировании реальная система разбивается на ряд достаточно малых (в функциональном отношении) элементов или модулей. Затем поведение исходной системы имитируется как поведение совокупности этих элементов, определенным образом связанных (путем установления соответствующих взаимосвязей между ними) в единое целое. Вычислительная реализация такой модели начинается с входного элемента, далее проходит по всем элементам, пока не будет достигнут выход- ной элемент модели. Вычислительные аспекты имитационных моделей обычно сравнительно несложные, но, как правило, очень трудоемкие. Поэтому реализация таких моделей подразумевает использование вычислительной техники. Имитационные модели значительно гибче в представлении реальных систем, чем их математические "конкуренты". Причина такой гибкости заключается в том, что при ими- 20 Глава 1 тационном моделировании исходная система рассматривается на элементном уровне, в то время как математические модели стремятся описать системы на глобальном, как можно более общем уровне. Но за гибкость имитационных моделей приходится платить высокими требованиями к потребляемым временным и вычислительным ресурсам. Поэтому реализация некото- рых имитационных моделей даже на современных быстрых и высокопроизводительных компьютерах может быть очень медленной. 1.4. Искусство моделирования Решения реальных задач исследования операций должны быть плодом коллективной работы, когда бок о бок работают аналитики ИО и клиент-заказчик задачи принятия ре- шений. Аналитикам ИО с их знаниями возможностей математического моделирования необходимы опыт и знание реальной ситуации, исходящие от клиента, для которого, собственно, и решается задача ИО. Исследование операций, как инструмент задачи принятия решения, можно рассматри- вать и как науку, и как искусство. Наука здесь представлена всей мощью математических методов, а искусство — тем обстоятельством, что успех на всех этапах, предшествующих получению оптимального решения математической модели, в большей степени зависит от творчества и опыта всей команды, занимающейся решением задачи ИО. Виллимейн (Willemain, [4]) утверждает, что "эффективная практика [ОИ] требует нечто большего, чем только знания и компетентность. Она также требует, среди прочего, "технической" мудро- сти (т.е. понимание того, когда и как применять тот или иной метод или алгоритм) и опре- деленного уровня коммуникабельности и организационных способностей". Из-за "неуловимого" человеческого фактора трудно дать точные предписания для реализации теории исследования операций на практике. Можно попытаться показать только общую направленность такой реализации. На практике реализация методов ИО должна включать следующие этапы. 1. Формализация исходной проблемы. 2. Построение математической модели. 3. Решение модели. 4. Проверка адекватности модели. 5. Реализация решения. Из всех пяти приведенных этапов только третий, решение модели, достаточно точно определен и наиболее прост для реализации в рамках методики ИО, поскольку действия на этом этапе основываются на точной математической теории. Выполнение остальных этапов в значительной мере является искусством, а не наукой. Поэтому мы не можем точно описать процедуры выполнения этих этапов. Формализация проблемы требует исследования той предметной области, где воз- никла рассматриваемая проблема. Это начальный этап работы любой команды аналити- ков ИО. В результате такого исследования должны быть получены следующие три прин- ципиальных элемента решаемой задачи: 1) описание возможных альтернативных реше- ний, 2) определение целевой функции, 3) построение системы ограничений, накладывае- мых на возможные решения. Глава 1. Исследование операций: обзор 21 Построение математической модели означает перевод формализованной задачи, опи- сание которой получено на предыдущем этапе, на четкий язык математических соотноше- ний. Если полученная модель является одной из стандартных математических моделей, та- ких как модель линейного программирования, то решение обычно достигается путем ис- пользования соответствующих существующих алгоритмов. Если же результирующая мо- дель очень сложная и не приводится к какому-либо стандартному типу моделей, то команда ИО может либо упростить модель, либо применить эвристический подход, либо использо- вать имитационное моделирование. В некоторых случаях комбинация математической, имитационной и эвристической моделей может привести к решению исходной проблемы. Решение модели, как уже упоминалось, — наиболее простой из всех этапов реализа- ции методов исследования операций, так как здесь используются известные алгоритмы оптимизации. Важным аспектом этого этапа является анализ чувствительности полу- ченного решения. Это подразумевает получение дополнительной информации о поведе- нии "оптимального" решения при изменении некоторых параметров модели. Анализ чувствительности особенно необходим, когда невозможно точно оценить параметры мо- дели. В этом случае важно изучить поведение оптимального решения в окрестности пер- воначальных оценок значений параметров модели. Проверка адекватности модели предполагает проверку правильности модели, т.е. определения того, соответствует ли поведение модели в определенных ситуациях пове- дению исходной реальной системы. Но сначала команда аналитиков ИО должна удосто- вериться, что модель не содержит "сюрпризов". Другими словами, надо убедиться, что решение, полученное в рамках построенной модели, имеет смысл и интуитивно прием- лемо. Формальным общепринятым методом проверки адекватности модели является сравнение полученного решения (поведение модели) с известными ранее решениями или поведением реальной системы. Модель считается адекватной, если при определенных начальных условиях ее поведение совпадает с поведением исходной системы при тех же начальных условиях. Конечно, это не гарантирует, что при других начальных условиях поведение модели будет совпадать с поведением реальной системы. В некоторых случа- ях в силу разных причин невозможно прямое сравнение модели с реальной системой или сравнение решений, полученных в рамках этой модели, с известными решениями (например, из-за отсутствия таких данных). В такой ситуации для проверки адекватности математической модели можно использовать имитационное моделирование, т.е. сравни- вать поведение математической и имитационной моделей. Реализация решения подразумевает перевод результатов решения модели в реко- мендации, представленные в форме, понятной для лиц, принимающих решения, т.е. за- казчиков решения исходной проблемы. Бремя этой непростой задачи ложится непосред- ственно на плечи команды аналитиков ИО. 1.5. Об этой книге Моррис (Morris, [3]) утверждает, что "изучение моделей не эквивалентно изучению моделирования". Автор постоянно держал эту важную мысль в голове во время подго- товки шестого издания данной книги. Он сознательно старался привнести искусство мо- делирования в теорию исследования операций. Эта книга, кроме описания математиче- ских моделей, содержит большое количество упражнений и задач, которые позволяют проникнуть в суть анализа практических ситуаций. 22 Глава 1 Автор надеется, что эта книга даст студентам не только фундаментальную основу для понимания математических методов исследования операций, но и понимание возможно- стей их применения. Такое понимание должно показать, что недостаточно сосредото- читься только на философских и "художественных" аспектах ИО. Необходимы фунда- ментальные знания математических методов исследования операций. Только на этой ос- нове студенты могут "взращивать" свой "художественный" потенциал в искусстве моде- лирования ИО. Хорошим подспорьем здесь может служить изучение публикаций и ста- тей в различных журналах. Автор настоятельно рекомендует журнал Interfaces (изда- тельство INFORMS Института управленческих наук и исследования операций) как бога- тый источник интересных приложений теории ИО. Литература 1. Evans J. Creative Thinking in the Decision and Management Sciences, South-Westem Pub- lishing, Cincinnati, Ohio, 1991. 2. Gass S. Model World: Danger, Beware the User as a Modeler, Interfaces, Vol. 20, No. 3, pp.60-64,1990. 3. Morris W. On the Art of Modeling, Management Science, Vol. 13, pp. B707-B717, 1967. 4. Willemain T.R. Insights on Modeling from a Dozen Experts, Operations Research, Vol. 42, No.2,pp.213-222,1994. Литература, добавленная при переводе1 Вагнер Г. Основы исследования операций. —М.: Мир, 1972. Вентцель Е.С. Исследование операций. — М.: Советское радио, 1972. Вилкас Э.Й., Майминас Е.З. Решения: теория, информация, моделирование. — М.: Ра- дио и связь, 1981. Гермейер Ю.Б. Введение в теорию исследования операций. — М.: Наука, 1971. Ларичев О.И. Наука и искусство принятия решений. — М.: Наука, 1979. Ларичев О.И. Объективные модели и субъективные решения. — М.: Наука, 1987. Кофман А. Методы и модели исследования операций. — М.: Мир, 1966. Краснощеков П.С., Петров А.А. Принципы построения моделей. — М.: Изд-во МГУ, 1983. Шеннон Р. Имитационное моделирование систем — искусство и наука. — М.: Мир, 1978. Литература по исследованию операций на русском языке очень обширна, но, к сожалению, в силу из- вестных причин в последнее десятилетие издание новых книг по этой тематике практически прекратилось (впрочем, как и другой научной литературы). Поэтому пусть извинит нас читатель, если добавленная литера- тура покажется ему устаревшей (утешением может служить то, что математика, как вечная наука и наука о вечном (с определенным допущением), не может устареть). Мы будем приводить, в основном, монографии, "устоявшиеся" в качестве учебных пособий для вузов. — Прим. ред. Глава 1. Исследование операций: обзор 23 Предметный указатель с СРМ, 269 F FIFO, 598 FORTRAN,701;829 G GPSS,701 L LIFO, 598 P PERT,269 S SIMAN, 701 SIMNETII,701;820 активизация и деактивизация источников, 851 дополнительный узел, 820; 826 дуги, 820 задание дуг, 839 задание плотностей вероятностей, 858 логические переключатели, 847 маршрутизация транзакций, 833 математические выражения, 829 начальные данные, 857 операторы, 820 операторы управления транзакциями, 852 правила работы с узлами, 827 сбор значений статистических переменных, 852 специальные операторы присваивания, 850 статистические переменные, 845 таблично-заданные функции, 859 узел источника, 820;821 узел очереди, 820; 823 узел средств обслуживания, 820; 824 SIMSCRIPT,701 SLAM, 701 А Алгебраическое дополнение, 811 Алгоритм аддитивный для задач с двоичными переменными, 395 Дейкстры, 235 динамического программирования для задачи с постоянными или невозрастающими предельными затратами, 463 динамического программирования с обшей функцией стоимости, 460 Кармаркара, 342 нахождения кратчайшего пути, 234 нахождения максимального потока, 245 обратной прогонки, 416 последовательной безусловной максимизации, 805 построения минимального остовного дерева, 225 прямой прогонки, 416 решения задач с ограниченными переменными, 311 симплекс-метода, 91; 293 Флойда, 235; 238 Алгоритмы нелинейного программирования, 773 решения задач без ограничений, 773 решения задач с ограничениями, 779 целевого программирования, 359 Анализ чувствительности, 22; 127; 152 графический, 38 добавление новых ограничений, 168 изменение коэффициентов целевой функции, 39;170 оптимального решения, 158 параметрическое программирование, 334 с помощью метода Якоби, 753 стоимость единицы ресурса, 43 Апостериорные вероятности Байеса, 533 904 Предметный указатель Б д Байеса теорема,479 Бокса-Мюллера метод, 683 В Ведущая строка, 94 Ведущий столбец, 94 Ведущий элемент, 94; 111 Вектор-столбец, 151 Вектор-строка, 151 Векторы линейно независимые, 807 определение, 807 Венгерский метод, 207 как симплекс-метод, 212 Вероятностные модели системы массового обслуживания, 596 управления запасами,574 Вероятностные модели управления запасами, 574 многоэтапные, 590 модель экономичного размера заказа, 574 одноэтапные, 582 при наличии затрат на оформление заказа, 587 при отсутствии затрат на оформление заказа, 583 с непрерывным контролем уровня запаса, 574 Вероятность переходная, 727 условная, 478 Выборка, 496 Выпуклая комбинация, 292 Вырожденность в симплекс-методе, 114 Г Генерирование выборочных значений, 676 метод Бокса-Мюллера, 683 метод обратных функций, 677 метод отбора, 684 метод сверток, 680 Генерирование случайных чисел, 687 мультипликативный метод сравнений, 688 Геометрическое программирование, 793 Гистограмма частот, 496 Гурвица критерий, 543 Двойственная задача, 127 ограничения,140 построение, 128 Двойственные цены, 51; 138 Двойственный симплекс-метод, 143 с искусственными ограничениями, 148 Двухэтапный метод, 109 Дейкстры алгоритм, 235 Дерево,224 остовное, 224 решений, 525 Диаграмма интенсивностей переходов, 613 Динамическое программирование, 412 алгоритм обратной прогонки, 416 алгоритм прямой прогонки, 416 вероятностное, 562 детерминированные модели, 412 принцип декомпозиции, 412 принцип оптимальности, 415 проблема размерности, 435 Дискретное моделирование, 673 генерирование выборочных значений, 676 определение события, 674 элементы,674 Дисциплина очереди, 598 Достаточное правило допустимости, 167 Достаточное правило оптимальности, 174 Дуга, 224 3 Задача замены оборудования,427 инвестирования, 431;565 коммивояжера, 377 нахождения кратчайшего пути, 217; 230 о загрузке, 418 о кратчайшем пути, 412 о максимальном потоке, 243 о назначениях, 206 о покрытии, 380 о рюкзаке, 418 о снаряжении, 418 планирования рабочей силы, 424 распределения оборудования, 187 распределения ресурсов, 421 с постоянными затратами, 376 управления запасами,187;439;711 Чебышева, 359 Предметный указатель 905 экономичного размера заказа, 440 Задача оптимизации без ограничений,738 метод множителей Лагранжа, 759 метод Ньютона-Рафсона, 744 метод приведенного градиента, 746 обобщенный метод множителей Лагранжа, 764 при наличии ограничений, 745 условия Куна-Таккера, 767 Задача принятия решений, 17; 706 с бесконечным числом этапов, 706 с конечным числом этапов, 706 Закон сложения вероятностей, 477 Запас времени, 280 общий, 280 свободный,280 И Имитационное моделирование, 20; 667 дискретные модели, 673 метод Монте-Карло, 668 методы сбора статистических данных, 694 непрерывные модели, 673 типы моделей, 673 элементы дискретного моделирования, 674 языки,700 Интервал неопределенности,773 оптимальности, 39 предсказания,510 Источник, 598 бесконечной мощности, 599 конечной мощности, 599 К Кармаркара метод, 341 Квадратичная форма, 816 неопределенная, 816 отрицательно определенная, 816 отрицательно полуопределенная, 816 положительно определенная, 816 положительно полуопределенная, 816 Квадратичное программирование, 789 Кендалла обозначения, 620 Классическая теория оптимизации, 738 Колмогорова-Чепмена уравнение, 729 Контур кратчайший, 377 Коэффициент корреляции,510 согласованности,520 согласованности стохастический, 520 чувствительности,754 Критерий Гурвица, 543 Лапласа, 542 максиминный, 542 ожидаемого значения, 524 предельного уровня, 532 согласия, 498 Сэвиджа, 543 Л Линейное программирование, 26 анализ чувствительности, 158 базисное решение, 84; 290 векторное представление базисов, 288 графическое решение, 30 двойственная задача, 127; 329 двойственная задача, матричное представление, 329 допустимое решение, 28 изменение модели, 175 интервальное,352 компьютерное решение, 48 матричное представление стандартной задачи, 286 метод Якоби, 754 ограничения,26 определение базисных решений, 87 оптимальное допустимое решение, 28 параметрическое, 334 примеры моделей, 56 прямая задача, 127 сетевые модели, 223; 257 соотношения двойственности, 132 стандартная форма задачи, 84; 127 теория, 286 теория двойственности, 329 транспортные модели,179 целочисленное, 371 м Марковская задача принятия решений, 705 применение методов линейного программирования, 722 Матрица, 151 блочная, 810 Гессе, 748 Гессе окаймленная, 760 дважды стохастическая, 734 906 Предметный указатель доходов, 705 единичная, 808 квадратная, 808 невырожденная, 288; 812 обратная, 152; 812 обратная, методы вычисления, 813 обратная, мультипликативное представление, 303 переходных вероятностей, 705; 728 присоединенная, 811 сравнений, 519 транспонированная, 808 управления, 748 Якоби,748 Метод анализа иерархий,515 блочных матриц, 814 Бокса-Мюллера, 683 венгерский, 207 весовых коэффициентов, 360 ветвей и границ, 388 Гаусса-Жордана, 94 градиентный, 744; 775 декомпозиции, 318 дихотомического поиска, 773 исключения переменных, 94 итераций по стратегиям без дисконтирования, 716 итераций по стратегиям с дисконтированием, 719 Кармаркара, 341 критического пути, 269; 275 линейных комбинаций, 802 множителей Лагранжа, 759 Монте-Карло, 668 наименьшей стоимости, 195 наименьших квадратов, 509 наискорейшего подъема, 775 Ньютона-Рафсона, 744 обобщенный множителей Лагранжа, 764 обратных функций, 677 отбора,684 отсекающих плоскостей, 402 повторения, 697 подынтервалов, 695 полного перебора стратегий, 713 последовательных исключений, 813 потенциалов, 198 потенциалов как симплекс-метод, 205 приведенного градиента, 746 приоритетов, 363 присоединенной матрицы, 813 сверток, 680 северо-западного угла, 193; 194 Фогеля,196 циклов, 698 экспоненциального сглаживания,507 Якоби,746 Методы вычисления обратных матриц, 813 исследования операций, 19 прогнозирования, 503 прямого поиска, 773 сетевого планирования, 269 Методы прогнозирования,503 интервал предсказания, 510 метод наименьших квадратов, 509 метод экспоненциального сглаживания, 507 регрессионный анализ, 509 с использованием скользящего среднего, 503 Методы сбора статистических данных, 694 метод повторения, 697 метод подынтервалов, 695 метод циклов, 698 Минор,811 М-метод, 103 Многокритериальная оптимизация, 354 Множители Лагранжа, 451; 759 Модели исследования операций, 17 построение, 22 проверка адекватности, 22 решение, 22 рождения и гибели, 605 сетевые,223;820 Модели управления запасами алгоритм динамического программирования, 463 алгоритм динамического программирования с общей функцией стоимости, 460 детерминированные, 439 динамические задачи экономичного размера заказа, 453 задача экономичного размера заказа с разрывами цен, 446 классическая задача экономичного размера заказа, 440 многопродуктовая статическая модель, 450 модель при отсутствии затрат на оформление заказа, 454 модель с затратами на оформление заказа, 459 обобщенные, 439 планирование потребностей ресурсов, 453 статические, 440 стратегии, 439 точка возобновления заказа, 440 эвристический подход Сильвера-Мила, 469 экономичный размер заказа, 439 Модель линейного программирования, 26 математическая, 18 чистого рождения, 606 чистой гибели, 609 Предметный указатель 907 Модель динамического программирования с бесконечным числом этапов, 712 с конечным числом этапов, 707 н Нелинейное программирование алгоритм последовательной безусловной максимизации, 805 градиентный метод, 775 метод дихотомического поиска, 773 метод линейных комбинаций, 802 метод наискорейшего подъема, 775 методы прямого поиска, 773 непрямые методы, 779 прямые методы, 779 условия Куна-Таккера, 767;789 О Обозначения Кендалла, 620 Ограничения вероятностные, 798 вторичные, 169 Оператор треугольный, 238 Определитель матрицы, 810 Отсечение, 402 дробное, 403 Очередь,598 принцип построения, 598 с приоритетом, 598 п Параметрическое программирование, 127 Переменные базисные, 87 ветвления, 389 вводимые в базис, 92 дополнительные, 36 избыточные, 36; 37 исключаемые, 94 искусственные, 103 небазисные, 87 остаточные, 36; 37 отклоняющие, 355 свободные,37;85;89 Позином, 793 Показатель оптимизма, 543 Поллачека-Хинчина формула, 650 Построение временного графика, 278 Правило исключения столбцов, 363 ограниченного ввода в базис, 782 Правило "красного флажка", 280 Преобразования проективные, 346 Приведенная стоимость, 141 Принцип недостаточного основания, 542 оптимальности динамического программирования, 415 Принятие решений, 514 в условиях неопределенности, 542 в условиях определенности, 514 в условиях риска, 524 дерево решений, 525 коэффициент согласованности, 520 критерий Гурвица, 543 критерий Лапласа, 542 критерий ожидаемого значения, 524 критерий предельного уровня, 532 критерий Сэвиджа, 543 максиминный критерий, 542 метод анализа иерархий, 515 согласованность матрицы сравнений, 519 функция полезности, 538 Проблема лифта, 19 размерности, 435 формализация, 21 Программирование геометрическое,793 интервальное,352 квадратичное, 789 параметрическое, 334 сепарабельное, 779 стохастическое, 798 Процесс марковский,727 стохастический, 726 Путь в сети, 224 Р Распределение бета-распределение, 685 биномиальное, 489 Вейбулла, 680 геометрическое,680 нормальное, 493; 682 отрицательное биномиальное, 684 отрицательное экспоненциальное, 492 908 Предметный указатель Пуассона,490;606;681;727 Пуассона усеченное, 610 равномерное, 678 стандартное нормальное, 494 треугольное, 679 экспоненциальное, 603; 678 экспоненциальное в системах массового обслуживания, 600 эмпирическое, 495 Эрланга, 681 Ребро,224 ориентированное, 224 Регрессионный анализ, 359; 509 Решение базисное, 84;290 базисное допустимое, 87 допустимое, 28 недопустимое, 87 оптимальное допустимое, 18; 28 эффективное, 361 Решения альтернативные оптимальные, 117 вырожденные, 114 неограниченные, 120 псевдооптимальные, 123 С Свойство марковское, 727 отсутствия последействия, 601 Сепарабельное программирование, 779 выпуклое, 785 Сервис, 598 Сетевые модели, 223; 255; 820 алгоритм нахождения кратчайшего пути, 234 алгоритм нахождения максимального потока, 245 алгоритм построения минимального остовного дерева, 225 алгоритмы решения, 223 " задача нахождения кратчайшего пути, 230 задача о максимальном потоке, 243 как задачи линейного программирования, 257 метод'критического пути, 275 методы планирования,269 нахождение потока наименьшей стоимости, 254 определения, 224 построение временного графика, 278 симплексный алгоритм, 262 Сеть. 224 ориентированная, 224 остаточная, 245 проекта, построение, 269 пропускная способность разреза, 244 разрез, 244 с нижними положительными границами пропускных способностей, 253 связная, 224 Симплекс, 346 Симплекс-метод, 84 алгоритм, 91 алгоритм решения задач с ограниченными переменными, 311 альтернативные оптимальные решения, 114; 117 вырожденность, 114 двойственный, 143 двойственный решения задач с ограниченными переменными, 318 двухэтапный метод, 109 зацикливание, 115 искусственное начальное решение, 103 матричные вычисления, 150 метод декомпозиции, 318 М-метод, 103 модифицированный, 303 модифицированный двойственный, 310 неограниченные рещения, 114; 120 обобщение, 149 отсутствие допустимых решений, 114; 122 сходимость, 293 условие допустимости, 297 условие оптимальности, 297 Симплексный мультипликатор, 51; 138 Симплексный алгоритм для сетей с ограниченной пропускной способностью, 262 Симплекс-таблица, 94; 96 матричное представление, 295 Система планирования и руководства программами разработок, 269 Системы массового обслуживания, 596 модели принятия решений, 653 модели с одним сервисом, 623 модели с параллельными сервисами, 635 модели самообслуживания, 644 модели со стоимостными характеристиками, 654 модель предпочтительного уровня обслуживания, 660 обобщенная модель, 612 основные компоненты, 598 переходной режим, 612 с пуассоновским распределением, 618 стационарные, 620 стационарный режим, 612 типы моделей, 619 формула Поллачека-Хинчина, 650 характеристики,598 Случайная величина дискретная, 480 непрерывная, 480 Предметный указатель 909 Соотношения двойственности, 132 Стоимость единицы ресурсов, 43; 51 Стохастическое программирование, 798 Стратегия, 705 оптимальная, 705 смешанная, 547 стационарная,707 управления запасами,439 чистая, 547 Сэвиджа критерий, 543 Т Теневая цена, 51; 138 Теорема Байеса, 479 двойственности об оптимальном решении, 330 двойственности, первая, 330 о горизонте планирования, 466 центральная предельная, 493 Теория вероятностей выборка, 496 дисперсия, 483 закон сложения вероятностей, 477 законы, 476 исход,476 ковариация,486 математическое ожидание, 482 объединение событий, 477 пересечение событий, 477 плотность распределения вероятностей, 480 пространство событий, 476 распределения вероятностей, 480 случайные величины, 480 событие, 476 события независимые, 478 события несовместные, 477 совместные распределения вероятностей, 485 теорема Байеса, 479 условные вероятности,478 функция распределения, 480 центральная предельная теорема, 493 эксперимент, 476 эмпирические распределения, 495 Теория двойственности, 127; 329 экономическая интерпретация, 137 Теория игр, 547 графическое решение, 551 игры двух лиц с нулевой суммой, 547 оптимальное решение, 547 решение матричных игр в смешанных стратегиях, 551 решение матричных игр методами линейного программирования, 554 смешанная стратегия, 547 стратегии, 547 цена игры, 548 чистая стратегия, 547 Точка допустимая, 802 крайняя, 292 перегиба, 739 седловая, 548;739 стационарная,740 Точки пространства решений крайние, 84 угловые, 84 Транспортная таблица, 180 Транспортные модели,179 венгерский метод, 207 метод наименьшей стоимости, 195 метод потенциалов, 198 метод северо-западного угла, 193; 194 метод Фогеля, 196 несбалансированные, 181 нетрадиционные,187 определение начального решения, 193 решение, 192 с промежуточными пунктами, 213 сбалансированные, 181 У Узел,224 Уравнение баланса, 614 Колмогорова-Чепмена, 729 обратное рекуррентное, 708 Условие допустимости, 98 допустимости двойственное, 1.44 допустимости симплекс-метода, 297 неотрицательности переменных, 28 нормировки, 794 оптимальности, 98 оптимальности двойственное, 144 оптимальности симплекс-метода, 297 ортогональности, 794 Условия Куна-Таккера, 767 Ф Флойда алгоритм, 235 Фогеля метод, 196 Формула Поллачека-Хинчина, 650 910 Предметный указатель Функция вогнутая, 817 вогнутая строго, 817 выпуклая, 817 выпуклая строго, 817 Лагранжа, 451; 759 мажорирующая, 685 одновершинная, 773 позином,793 полезности, 538 сепарабельная, 779 целевая, 18 целевая линейная, 29 Ц Целевое программирование, 354 метод весовых коэффициентов, 360 метод приоритетов, 363 Целочисленное линейное программирование, 371 аддитивный алгоритм для задач с двоичными переменными, 395 метод ветвей и границ, 388 метод отсекающих плоскостей, 402 Цепи Маркова, 705; 727 абсолютные вероятности, 728 классификация состояний, 730 матрица переходных вероятностей, 728 неприводимые, 730 неприводимые апериодические, 733 первое время возвращения, 731 переходные вероятности, 727 поглашающие состояния, 730 предельные распределения,733 теория,726 уравнение Колмогорова-Чепмена, 729 зргодические, 732 Цикл в сети,224 . ориентированный, 224 э Эвристический подход, 20 Экстремум глобальный, 738 локальный, 738 нестрогий,739 строгий,739 Я Языки имитационного моделирования, 700 Предметный указатель