XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 60
Текст из файла (страница 60)
Если В (й ) — величина суммарного дохода, обусловленная реализацией проекта, а Д(у ) — максимальный доход на этапе у при заданном у., то, согласно (П2.4), (П2.5) и примеру П2.4, Д(У ) = шах 1 гс (й') + Д+г(У вЂ” с (й )))~, У = 1, 3, 425 Таблица ПЯ,В Таблица ПВ.Я (2, 3, 2) (2, 4, 1) (3, 2, 2) Рис. П2.10 Таблица ПВ.4 424 ПРИЛОЖЕНИЕ 2.
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ где ш — множество номеров й тех проектов, для которых с)(й) < уу, а (4(у4) = 0 для всех значений уз = 0,5. Процесс вычислений начинаем при у = 3, а результаты вычислений представим в табл. П2.2-П2.4. Чтобы найти оптимальное решение, проведем анализ полученных результатов, начиная с этапа 1. При у1 = 5 оптимальные проекты имеют номера к,* = 2 и й*, = 3 (см. табл. П2.4). Сначала рассмотрим случай й*, = 2. С учетом данных, представленных в табл. П2.1, имеем с1(2) = 1 и на этапах 2 и 3 уз = у1 — с1 (2) = 5 — 1 = 4. Таким образом (см. табл.
П2.3 при уз = 4), )зз = 3 или Ц = 4. Если йз = 3, то (см. табл. П2.1) сз(3) = 3 и уз = уз — сз(3) = 4 — 3 = 1. Поэтому (см. табл. П2.1 при уз = 1) йз — — 2. Найдем оптимальный набор проектов й1 —— = 2, й'= 3, кз —— 2, что соответствует суммарному доходу (см. табл. П2.1) в объеме 5+9+3 = 17 условных денежных единиц и следующему распределению капиталовложений: для предприятия Аз — 1; для предприятия Аз — 3; для предприятия Аз — 1. Схема нахождения всех различных оптимальных наборов проектов представлена на рис.
П2.10. и з )е1 уз )ет уз )ез А йз )ез) Завершая рассмотрение метода дискретного динамического программирования, заметим, что материал этого приложения предназначен лишь для первого знакомства как с самим методом, так н а динамическим программированием в целом. Для более деталцного изучения этих важных разделов исследования операций рекомендуем обратиться к специальной литературе*. 'Смх Ваенер Г., тт. 1 — 3; Таха Х., т.
1. 427 СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ Учебники и учебные пособил Ашмамов С.А. Линейное программирование: Учеб. пособ. Мс Наука, 1981. 304 с. Воробьев Н.Н. Теория игр. Лекции для экономистов-кибернетиков. Л с Изд-во Ленингр, ун-та, 1974. 160 с. Карманов В Г. Математическое программирование: Учеб. пособ. Мс Наука, 1975. 272 с. Кузнецов Ю.Н., Куэубов В.И., Волощемко А.Б.
Математическое программирование: Учеб. пособ. Мс Высш. шк., 1976. 352 с. . Моисеев Н.Н., Ивамилов Ю.П., Столярова Е.М. Методы оптимизащии: Учеб. пособ. Мс Наука, 1978. 350 с. Теория прогнозирования и принятия решений: Учеб. пособ. / Под ред. С.А. Саркисвма. Мс Высш. шк., 1977. 304 с. Задачники Акулич И.Л.
Математическое программирование в примерах и задачах: Учеб. пособ. Мс Высш. шк., 1986. 319 с. Калихлам И.Л. Сборник задач по математическому программированию. Мс Высш. нпс., 1975. 270 с. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в примерах и задачах: Учеб. пособ. Мг Высш.
шк., 1986. 287 с. Моиогра1рии Айэекс Р. Дифференциальные игры / Пер. с англ. под ред. М.И. Зели- кима. Мс Мир, 1967. 480 с. Акоф Р., Сасиеми М, Основы исследования операций / Пер. с англ. под ред. И.А. Ушаково. Мс Мир, 1971. 536 с. Армс Р. Дискретное динамическое программирование / Пер, с англ. под ред. Б.Т. Поляка. Мс Мир, 1969. 172 с. Бамди Б, Основы линейного программирования / Пер. с англ.
под ред. О.В. Шахеевой, Мх Радио и связь, 1989. 176 с. Вагмер Г. Основы исследования операций / Пер. с англ. под ред. Б. Т. Вавилова: В 3 т. Т.1. Мс Мир, 1972. 336 сл Т.2. Мс Мир, 1973. 488 сд Т.З. Мс Мир, 1973. 504 с. Вемтцель Е.С. Исследование операпнй.
Мс Советское радио, 1972. 552 с. Герлейер Ю.Б. Введение в теорию исследования операций. Мх Наука, 1971. 384 с. Гремь Е. Статистические игры и их применение / Пер. с польск, под ред. Г.Г. Пирогова и СД. Горшенина. Мс Статистика, 1975. 176 с. Ерлольев Ю.М. Методы стохастнческого программирования.
Мс Наука, 1976. 240 с. Имтрилигатор М. Математические методы оптимизации и экономическая теория / Пер. с англ, под ред. А.А. Конюса. Мс Прогресс, 1975. 608 с. Исследование операций: модели и применение / Под ред. Д. Моудера и С. Эллаграбш В 2 т. Т. 1. / Пер. с англ. И.М. Макарова и И.М. Бескровного. Мл Мир, 1981. 677 с. Карр Ч., Хоув Ч. Количественные методы принятия решений в управлении и экономике / Пер. с англ. под ред. Н.Н. Воробьева.
Мл Мир, 1966. 463 с. Льюис Р., Райфо Х. Игры и решения / Пер. с англ. под ред. Д.Б. Юдима. Мс Изд-во иностр. лит., 1961. 644 с. Нейман Д., Моргенштерн О. Теория игр и зкономическое поведение / Пер. с англ. под ред. Н.Н. Воробьева. Мг Наука, 1970. 708 с. Раскин Л.Г. Анализ сложных систем и элементы теории оптимального управления. Мс Советское радио, 1976, 344 с. Растригим Л.А. Системы экстремального управления.
Мс Наука, 1974. 632 с. ° Таха Х. Введение в исследование операций / Пер. с англ. В.Я. Алтаева, Б.Т. Вавилова, В.С. Дамилима и В.И. Моторина: В 2 т. Мс Мир, 1985. Т. 1. 479 с.; Т. 2. 496 с. Флемимг У., Ришел Р. Оптимальное управление детерминированными и стохастическнми системами / Пер. с англ. под ред. А.Н. Ширяева. М.: Мир, 1978. 318 с.
429 Запас чистый 203 Значение целевой функции оптимам нос 153 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ресурсов 69 Игра 315 — антагонистическая 315 — бесконечная 315 — в нормальной форме 318 — — развернутой форме 316 265 пути 411 Альтернатива 180 — скрытый 141 Дробь правильная 1-133, 159 179 Базис задачи линейного программирования 93 — — — — оптимальный 122 -- полной информацией 318 -- постоянной разностью 316 — — седловой точкой 325 — распределительного типа 52 — с и участниками 315 — решающая 297 — случайная 297 — стабильнав 324 -- — в стандартной форме 60 --- двойственная 129 --- прямая 129 способности 194 Горизонт планирования бесконечный 244 математического 200 — — конечный 244 Граница 171 Гр ф Х1Х, 174 — транспортного типа 214 -- частично 147 некорректная 34 неопределенная 27 о замене оборудования 213 294 комплекса работ 71 — — назначениях 206 -- априорный 293 — максиминный 305 Алгоритм дробный 159 — нахождения наиболее длинного Вектор вероятностей состояний системы ХЧ1П, 941 — — — — начальных ХУП1, 241 — решений 242 Вероятность стационарная ХУ1П, 954 Вершина дерева решений Х1Х, 1 74 — оптимальная 57 Гипотеза статистическая ХЧП, Дерево игры 316 — решений Х1Х, 174 Дисконтирование 250 Длина пути 408 Доход ожидаемый 243 Доход ожидаемый оптимальный 245 — приведенный дисконтированный Единица полезности денег 282 Задача вариационного исчисления ХЧ, 38 выбора кратчайюего пути 211 выпуклого программирования 31 детерминированная 27 динамическая 25 имитационного моделирования 356 исследования операций 20 квадратичного программирования 31 линейного программирования 31 программирования 31 многокритериальиой (векторной) оптимизации 31 -- календарном планировании Задача о пищевом рационе 69 — оптимального управленил ХЧ, 39 — о распределении ограниченных — организационного управления 355 — ослаблениае 152 — параметрическая 28 — планирования производства с постоянными элементами затрат — порожденная исходной задачей — принятия решений в условиях неопределенности 27 — ---- определенности 281 -- — — риска 27, 281 --- марковская 239 --- многошаговая 27 — — — одношаговая 27 — с ослабленными ограничениями — статическав 25 — стохастическвя 27 — транспортная 69, 189 — — классическая 190 — — с ограничениями по пропускной — — — промежуточными пунктами — целочисленнае полностью 147 Задача-исток 152 Закон баль!бих чисел ХУ1, 375 — распределбпияапостериарный — — зкс генсивной форме 316 — конечная 315 — кооперативная 316 — матричная 320 — находящаяся в состоянии равновесия 324 — некооперативна» 316 — позиционная 316 — с неполной информацией 318 — — нулевой суммой 315 Игрок 314 Изменение допустимое 122 Испытание случайное ХЧ1, 353 Исследование операций 20 Источник 189 Коалиция 315 Комбинация векторов вмпуклая 86 Кооперация 315 Коэффициент весовой 46 — дисконтирования годовой 250 Критерий Гурвица 308 — Лапласа 303 430 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 431 114 — игры 326 — оптимальное 20 Мииимакс 32 325 Максимии 32 239 Стратегия 239 — активная 331 задачи 167 — модели 50 — — базисное.82 Критерий мииимаксиый 304 — наиболее вероятного исхода 292 — ожидаемого значения 282 — „ожидаемое зиачеиие— дисперсия" 287 — оптимальности 20 — предельиога уровня 290 — скаяярный глобаяьиый 43 — — нормированный 45 — Сзвиджа 306 „Лицо, принимающее решения" 22 Матрица дохода 30 — затрат 302 — переменных модели 191 — переходных вероятностей ХЧ1И, — платежная 318 — потерь 302 — сожалений 306 — стоимости 208 -- эквивалентная 394 Метод венгерский 394 ветвей н границ 151 возврата 178 геометрический 53 Гомори 153 дополнения 389 итераций по стратегиям 250 -- — - с дисконтированием 265 комбииаторный 150 компромиссов 41 минимальной стоимости 220 Моите-Карло ХНП, 585 мультипликативиых коигруэнций 368 Метод округления 148 — отсекающнх плоскостей 153 — отсечений 149 — погружения 419 — полного перебора 253 — потенциалов 215 — симплексиый 215 Методы исследования операций математические 33 Многогранник выпуклый 31 Множество выпуклое 86 — компромисса 38 — Парето 38 Моделирование имитационное в широком смысле 356 -- компьютерное 357 Модель математическая П, уб — принятия решений марковская -- — стохвстическая 293 Мощность источника 189 — стока 189 Неизвестное независимое П1, 985 Ограничение активное 56 — альтернативное 180 — пассивное 56 Оптимизация поэтапная 417 Отношение порядка 1-82, УУ Отсечение Гомори 159 — — для чаагнчио целочисленной Партия игры 316 Переменное булево 152 Переменное модели искусственное — — неограниченное в знаке 53 — — свободное 83 — состояния 417 — управляемое 50 Переменные двойственные 141 Перестановка 1, Ш, 38 Период переходный 253 — плановый 357 Плоскость отсекающая 156 Поведение асимптотическое 259 Падпуть 413 Показатель оптимизма 308 Правило северо-западного угла 217 Прибыль удельная 52 Принцип компромисса 35 — недостаточного обоснования 302 — оптимальности Веллмаиа ХН, 418 Прогон имитационной модели 385 Программирование булеза 32 — динамическое ХЧ, 454 — дискретное 32 — линейное 49 — стохвстическое 32 — целочисленное 32 Процесс ветвления 170 — марковский однородный ХЧП1, Пункт промежуточный 199 Путь 176 Ранг скалярного критерия 39 Ресурс дефицитный 57 — иедефицитиый 57 Решение базисное 83 — — допустимое 83 — — — вырожденное 98 — — начальное 93 Решение допустимое 20 — задачи миогокритериальиой оптимизации обобщенное 39 — — альтернативное 110 -- неограниченное 9Т вЂ” строго более предпочтительное Решения эквивалентные 37 Свойство устойчивости стратегий С х1Х, 188 — ациклическая 214 Симплекс-метод 82 Симплекс-множитель 225 Симплекс-разность 95 Симплекс-таблица 103 — оптимальная 155 Синтез глобального скалярного критерия 43 Система лииейиыхалгебраических уравнений бвзисиая 60 -- — — треугольная 222 — независимых нулей 394 Состояние информационное „лица, принимающего решеиил" 22 — начальное ХНП, 857 — равновесия игры 349 — установившееся 253 Сток 189 — максимиииая 321 — мииимаксиая 322 — оптимальная 239 — смешанная 328 — стационарная 244 432 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Функция полезности дохода 286 — целевая 31 Стратегия чистая 327 Строка симплекс-таблицы ведущая 165 Ход 316 ОГЛАВЛЕНИЕ Лаблицатранспортная 191 Теорема центральная предельная ХЧ1, 971 Цена игры верхняя 322 -- нижняя321 Предисловие Основные обозначения Введение 10 Теория игр 314 Точка множества крайняя 86 — — ожидаемая 331 -- чистав 325 — теневая 141 15 — равиовесил игры 349 20 20 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
