|
Содержание
Основные обозначения . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 14 Тема 7. Многокритериальная оптимизация . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 18 § 1. Многокритериальность и недоминируемые, или эффективные, решения . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 18 1.1. Допустимые решения и критерии (19). 1.2. Недоминируемые, или эффективные, решения (21). 1.3. Пример — распределение бюджета между двумя статьями расходов (25). 1.4. Пример — покупка автомобиля (25). 1.5. Игровая трактовка, сравнение с равновесием по Нэшу (27). 1.6. Трансформация эффективностей при расширении набора критериев (30). 1.7. Экспертно оцениваемые критерии и их шкалы (33). § 2. Выделение эффективных решений посредством однокритериальной оптимизации . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 36 2.1. Метод критериальных ограничений (36). 2.2. Метод линейной свертки критериев (39). 2.3. Эффективные решения в линейных задачах (41). § 3. Целевое программирование . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 44 3.1. Идея целевого программирования (44). 3.2. Метод идеальной точки (46). 3.3. Общая задача линейного целевого программирования (50). 3.4. Пример линейного целевого программирования (52). § 4. Интерактивные методы многокритериального выбора . .. .. .. .. .. .. .. .. . 58 4.1. Визуализация паретовских множеств (58). 4.2. Сравнительная важность критериев (62). 4.3. Уступки по критериям (67). § 5. Бескритериальная формализация предпочтений. .. .. .. .. .. .. .. .. .. .. .. .. . 69 5.1. Бинарные отношения (69). 5.2. Использование бинарных от- ношений в задачах выбора (73). 5.3. Функция полезности (76). 5.4. О представимости бинарных отношений векторным критери- ем (79). 5.5. О функциях выбора (79). Упражнения к теме 7. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 80 Приложение к теме 7. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 92 Список литературы к теме 7 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 966 Тема 8. Оптимизация в динамических системах — принцип макси- мума . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 98 § 1. Формулировка динамических задач оптимизации . .. .. .. .. .. .. .. .. .. .. . 99 1.1. Специфика динамических управляемых систем (99). 1.2. Диф- ференциальные системы, или системы в непрерывном време- ни (100). 1.3. Конечно-разностные системы, или системы в дискретном времени (106). 1.4. О существовании оптимальных решений в динамических задачах (108). § 2. Принцип максимума Понтрягина . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 112 2.1. Каноническая задача оптимального управления (112). 2.2. Идея принципа максимума (113). 2.3. Исключение диффе- ренциальных связей из канонической задачи (115). 2.4. Седловая точка лагранжиана — достаточное условие оптимальности (117). 2.5. Гамильтониан, его максимум и уравнения для множителей Лагранжа (118). 2.6. Вариационный смысл множителей Лагран- жа (123). 2.7. Принцип максимума и классическое вариационное исчисление (123). § 3. Теорема Понтрягина и ее использование . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 125 3.1. Формулировка теоремы (125). 3.2. Использование теоре- мы (127). 3.3. Еще один пример использования принципа максимума — решение задачи с закрепленными концами траектории (139). § 4. Условия трансверсальности для задач с незакрепленными концами траектории . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 161 4.1. Общая схема получения условий трансверсальности (161). 4.2. Примеры (166). 4.3. Условия трансверсальности и принцип максимума для функционала Больца (167). 4.4. Задачи с нефикси- рованным отрезком времени (169). § 5. Распространение принципа максимума на нестандартные задачи управления . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 175 5.1. Смешанные ограничения на управление и фазовые координа- ты (175). 5.2. Постоянные управляющие параметры (177). 5.3. Тре- бования к функциональному виду управления (179). 5.4. Ограни- ченное время действия управления (181). 5.5. Запаздывания в фа- зовых координатах (183). 5.6. Запаздывания в управлении (187). 5.7. Задачи в дискретном времени (189). § 6. Достаточные условия Кротова . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 192 6.1. Вводные замечания (192). 6.2. Обобщенная формулировка за- дачи оптимального управления (193). 6.3. Идея достаточных усло- вий и лемма о неулучшающем расширении (194). 6.4. Конструк- ция расширенного функционала и теорема о достаточности (195). 6.5. Построение производящей функции с использованием проце- дуры Понтрягина (198). 6.6. Построение производящей функции с использованием уравнения Беллмана (202). 6.7. Метод кратных максимумов (203). 6.8. Игровая идея численных методов построе- ния производящей функции (207). Упражнения к теме 8. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 208 Список литературы к теме 8 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 215 Тема 9. Динамическое программирование. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 217 § 1. Уравнение Беллмана для конечно-разностных систем. .. .. .. .. .. .. .. .. . 217 1.1. Принцип оптимальности (217). 1.2. Рекурсивная процедура для канонической задачи в дискретном времени (218). 1.3. Распро- странение процедуры на критерий Больца и пример (224). § 2. Обобщение беллмановской процедуры на задачи с фазовыми и смешанными ограничениями . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 229 2.1. О происхождении фазовых и смешанных ограничений (229). 2.2. Новые черты беллмановской процедуры на примере (230). 2.3. Общая схема (236). 2.4. Решение статических задач распреде- ления ресурсов методом динамического программирования (239). § 3. Уравнение Беллмана в непрерывном времени . .. .. .. .. .. .. .. .. .. .. .. .. .. . 243 3.1. Вывод уравнения Беллмана для канонической задачи (243). 3.2. Решение примера в непрерывном времени (248). 3.3. Уравнение Беллмана и принцип максимума Понтрягина (250). Упражнения к теме 9. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 253 Список литературы к теме 9 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 257 Тема 10. Гарантирующее, или игровое, управление . .. .. .. .. .. .. .. .. .. .. . 258 § 1. Формализация проблемы управления в условиях неопределенности 258 1.1. Основные понятия (259). 1.2. Принцип гарантированного ре- зультата (260). 1.3. Пример формализации и решения задачи о штатах фирмы по принципу гарантированного результата (262). § 2. Методы построения оптимальных гарантирующих планов. .. .. .. .. .. . 268 2.1. Сведение к задаче математического программирования (268). 2.2. Пример решения задачи линейного программирования с неопределенностями (270). 2.3. Сведение к макс-мину без ограничений методом Лагранжа (274). § 3. Сравнение с идеальным управлением . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 275 3.1. Максимизирующая стратегия (275). 3.2. Сопоставление по условиям разрешимости (276). 3.3. Сравнение по критерию каче- ства (277). 3.4. Игровая интерпретация (279). 3.5. Пример и до- статочное условие наличия седловой точки — задача уклонения от налогов (282). 3.6. Пример и новые причины отсутствия седловой точки (285). § 4. Другие способы выбора управлений в условиях неопределенности 288 4.1. Принцип близости к идеальному решению (288). 4.2. Прин- цип оптимизма–пессимизма (291). 4.3. Принцип наиболее вероят- ного возмущения (291). 4.4. Принцип равновероятных возмуще- ний (292). § 5. Гарантирующее планирование для динамических систем в непре- рывном времени. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 293 5.1. Конкретизация общей схемы на примере задачи управления запасами (293). 5.2. Сведение к задаче оптимального управления без возмущений (295). 5.3. Решение результирующей задачи (299). 5.4. Обобщающие замечания (303). 5.5. Численное построение до- пустимых гарантирующих планов (305). § 6. Гарантирующее пошаговое управление для динамических систем в дискретном времени. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 308 6.1. Общая схема (308). 6.2. Пример — управление мелкооптовой базой (311). Упражнения к теме 10 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 315 Список литературы к теме 10 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 332 Тема 11. Вероятностное планирование . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 333 § 1. Общие положения вероятностного планирования. .. .. .. .. .. .. .. .. .. .. .. . 333 1.1. Априорная информация о возмущениях (334). 1.2. Схема управления (334). 1.3. Оптимизация в среднем (стохастиче- ская) (334). 1.4. Вероятностно-гарантирующий подход к пла- нированию (336). 1.5. Вероятностно-гарантирующие решения дискретных задач с конечным множеством возмущений и пла- нов (338). § 2. Универсальная формулировка задачи о вероятностно-гарантирую- щем планировании . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 340 2.1. Подмножества благоприятных возмущений (340). 2.2. Доказа- тельство эквивалентности (341). 2.3. Жесткие и нежесткие ограни- чения на управление (342). § 3. Предельная тождественность вероятностно-гарантирующего и га- рантирующего планирования . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 347 3.1. Возможный диапазон наилучших вероятностно-гарантирующих оценок (348). 3.2. Достаточные условия предельной тождествен- ности (349). 3.3. Примеры отсутствия предельной тождественно- сти (354). 3.4. Характер сходимости вероятностного решения к га- рантирующему (359). § 4. Рандомизация выбора управления — смешанные стратегии . .. .. .. .. . 364 4.1. Условия применимости смешанных стратегий (365). 4.2. Чи- стые и смешанные стратегии для матричных антагонистических игр (367). 4.3. Пример — матричная игра об инспекции сокрытия доходов и ее смешанное расширение (370). 4.4. Существование седловой точки в смешанных стратегиях для матричных игр (377). § 5. Вероятностно-гарантирующее планирование в конечношаговой за- даче управления запасами . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 380 5.1. Модификация (380). 5.2. Формулировка задачи вероятностно- гарантирующего планирования (381). 5.3. Общие свойства (384). 5.4. Динамический пример (385). 5.5. Сравнение с идеальным и гарантирующим решениями (390). Упражнения к теме 11 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 393 Список литературы к теме 11 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 401 Заключение . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 402 Предметный указатель к тому 1 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 409 Предметный указатель к тому 2 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 414 Соколов А. В., Токарев В. В. Общие положения. Математическое программирование Предисловие . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 14 Основные обозначения . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 17 Тема 1. Формализация проблем управления в экономике. .. .. .. .. .. .. . 21 § 1. Цели и возможности применения математики и теории оптимизации в экономике . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 21 § 2. Математическое описание экономических объектов . .. .. .. .. .. .. .. .. .. . 23 2.1. Управляемые и прогнозные модели (23). 2.2. Управляемость и большая размерность (25). 2.3. Непрерывное и дискретное вре- мя (29). 2.4. Основные разделы описания: материальный, фи- нансовый и социальный (30). 2.5. Описание внешней среды (31). 2.6. Элементы экономики и элементы описания (31). 2.7. Продукты и выпуски (33). 2.8. Основные фонды и мощность (34). 2.9. Опе- ратор планирования и оператор функционирования (35). 2.10. Про- стейшая однопродуктовая схема (36). 2.11. Простейший оператор планирования (37). 2.12. Процедура объединения элементов (40). 2.13. Аппроксимация описаний (43). § 3. Схемы принятия управленческих решений . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 44 3.1. Теоретико-управленческие начала (44). 3.2. Стандартная фор- ма описания схем экономического управления (46). 3.3. Планиро- вание и оперативное управление (48). § 4. Примеры формализации . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 53 4.1. Задача о штатах фирмы (53). 4.2. Задача о кредите (55). § 5. Сводка этапов построения и эксплуатации математических моделей 59 § 6. Классификация математических задач управления. .. .. .. .. .. .. .. .. .. .. . 64 6.1. Классификация по схеме управления (64). 6.2. Классифи- кация по априорной информированности о возмущениях (64). 6.3. Классификация по динамическим свойствам задачи (65). 6.4. Классификация по мощности множества допустимых управлений (65). 6.5. Классификация по способу формализации предпочтений управлений (65). Упражнения к теме 1. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 66 Список литературы к теме 1 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 70 Тема 2. Оптимизация в детерминированном приближении . .. .. .. .. .. . 71 § 1. Формулировка оптимизационной проблемы. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 71 1.1. Детерминированное приближение как полезная абстрак- ция (71). 1.2. Общая запись и примеры задач оптимизации (72) § 2. Определение оптимальных решений и проблема их существования 74 2.1. Определение оптимального решения (74). 2.2. Пример (75). 2.3. Три причины отсутствия оптимальных решений (76). 2.4. О до- статочности и необходимости условий существования оптимальных решений (78). 2.5. Примеры отсутствия и существования опти- мальной цены продаж (80). § 3. Допустимые и оптимальные решения . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 91 3.1. Постановка задачи на допустимость (92). 3.2. Оптимальное решение как предел допустимых (93). § 4. Эквивалентные и взаимные задачи оптимизации . .. .. .. .. .. .. .. .. .. .. .. . 96 4.1. Монотонные преобразования критерия оптимальности (96). 4.2. Взаимная замена критерия оптимальности и ограничения допустимости (98). § 5. Параметрические задачи оптимизации . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 108 5.1. Цели и формулировка задачи параметрического анализа (108). 5.2. Схема последовательной оптимизации (109). 5.3. Пример по- следовательной оптимизации (116). § 6. Теоретико-множественный подход к оптимизации . .. .. .. .. .. .. .. .. .. .. . 125 6.1. Сведение проблемы оптимизации к поиску точной грани- цы между пустотой и непустотой множеств (125). 6.2. Техни- ка отыскания границы непустоты параметрически заданных мно- жеств (126). 6.3. Пример (128). Упражнения к теме 2. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 130 Приложения к теме 2. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 136 П.1. Элементы математической логики (136). П.2. Множества (149). П.3. Бинарные отношения, функции (отображения) (154). Список литературы к теме 2 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 158 Тема 3. Математическое программирование . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 159 § 1. Общие положения . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 159 1.1. Основные понятия (160). 1.2. Типы задач математического программирования (163). 1.3. Графический метод решения (170). 1.4. Последовательная оптимизация как способ решения задач ма- лой размерности (174). 1.5. Достаточные условия существования глобального экстремума (175). 1.6. Локальная оптимизация (183). § 2. Безусловная оптимизация . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 187 2.1. Постановка и схема решения задачи (187). 2.2. Признаки ло- кального экстремума (190). 2.3. Примеры решения задач (197). § 3. Классическая задача математического программирования . .. .. .. .. .. . 203 3.1. Постановка задачи (203). 3.2. Признаки условного локального экстремума (207). 3.3. Применение метода Лагранжа для отыска- ния условного локального экстремума (231). 3.4. Оценка чувстви- тельности экстремального значения целевой функции к изменению констант в условиях связи (242). Упражнения к теме 3. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 260 Приложения к теме 3. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 264 П.1. Топологические характеристики точек и множеств (264). П.2. Числовые (скалярные) функции многих переменных (269). П.3. Выпуклые множества и функции (276). П.4. Квадратичные формы (285). П.5. Квадратичные формы с линейными условиями связи (291). П.6. Вектор-функции (299). Список литературы к теме 3 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 301 Тема 4. Нелинейное программирование . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 302 § 1. Основные понятия . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 302 § 2. Необходимый признак локального максимума . .. .. .. .. .. .. .. .. .. .. .. .. .. . 307 2.1. Допустимые направления (308). 2.2. Идея вывода необходи- мого признака (312). 2.3. Условия Куна–Таккера в градиентной форме (318). 2.4. Необходимый признак условного локального мак- симума для задач с выпуклыми ограничениями (327). 2.5. Усло- вия Куна–Таккера в алгебраической форме (335). 2.6. Условия Куна–Таккера для задач на минимум (340). § 3. Достаточные признаки максимума . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 342 3.1. Достаточный признак для задач выпуклого программирова- ния (342). 3.2. Усиленные условия Куна–Таккера (344). § 4. Обзор результатов . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 349 § 5. Примеры решения задач . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 353 § 6. Оценка чувствительности экстремального значения целевой функ- ции к изменению констант в ограничениях задачи. .. .. .. .. .. .. .. .. .. .. . 373 § 7. Седловая точка функции Лагранжа. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 383 7.1. Определение седловой точки (383). 7.2. Теорема Куна–Таккера о седловой точке функции Лагранжа (387). 7.3. Двойственные задачи нелинейного программирования. Экономическая интерпре- тация (397). § 8. Численные методы решения задач нелинейного программирования 398 8.1. Градиентные методы (399). 8.2. Метод штрафных функ- ций (401). Упражнения к теме 4. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 404 Приложения к теме 4. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 418 П.1. Теорема о разделяющей гиперплоскости (418). П.2. Теорема Фаркаша (419). Список литературы к теме 4 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 420 Тема 5. Линейное программирование . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 422 § 1. Формы представления задач линейного программирования . .. .. .. .. . 422 § 2. Структура допустимого множества и типы решений. .. .. .. .. .. .. .. .. .. . 425 2.1. Структура допустимого множества (425). 2.2. Типы реше- ний (426). § 3. Прямая и двойственная задачи линейного программирования . .. .. . 428 3.1. Понятие двойственной задачи (428). 3.2. Теоремы двойствен- ности (429). 3.3. Экономическая интерпретация двойственных за- дач (433). § 4. Графический метод решения задач линейного программирования . . 436 4.1. Задачи с двумя переменными (436). 4.2. Задачи с двумя огра- ничениями (439). 4.3. Вырожденные случаи (444). § 5. Анализ чувствительности оптимального решения к параметрам задачи линейного программирования. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 446 5.1. Особенности проявления чувствительности в задачах линейно- го программирования (446). 5.2. Пример анализа чувствительно- сти (448). 5.3. Оценка диапазона постоянства параметра чувстви- тельности (453). 5.4. Теорема чувствительности (454). § 6. Принцип гарантированного результата в задачах линейного про- граммирования . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 460 § 7. Решение задач линейного программирования симплекс-методом. .. . 464 7.1. Идея симплекс-метода (464). 7.2. Понятие симплекса (466). 7.3. Пример решения задачи симплекс-методом (470). § 8. Транспортные задачи линейного программирования . .. .. .. .. .. .. .. .. .. . 478 8.1. Понятие транспортной задачи (479). 8.2. Определение началь- ного плана (482). 8.3. Нахождение оптимального плана (485). § 9. Компьютерная реализация решения задач линейного программиро- вания. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 489 9.1. Загрузка программы Microsoft Excel 2000 (490). 9.2. Запись исходных данных задачи (490). 9.3. Запись формул (492). 9.4. За- пуск программы поиска решения (494). 9.5. Ввод исходных данных задачи в программу поиска решения (494). 9.6. Запуск процедуры решения задачи (498). 9.7. Анализ результатов (498). Упражнения к теме 5. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 503 Список литературы к теме 5 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 511 Тема 6. Дискретная оптимизация. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 512 § 1. Типы задач целочисленного программирования . .. .. .. .. .. .. .. .. .. .. .. .. . 512 1.1. Понятие задачи целочисленного программирования (512). 1.2. Экономические примеры, формализуемые как задачи цело- численного программирования (516). 1.3. Классификация задач целочисленного программирования (525). § 2. Решение задач линейного целочисленного программирования мето- дом отсечения . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 527 2.1. Идея метода (527). 2.2. Алгоритм Гомори (528). 2.3. Пример решения задачи методом отсечения (531). § 3. Решение задач целочисленного программирования методом ветвей и границ . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 539 3.1. Идея метода (539). 3.2. Схема решения задач целочисленно- го линейного программирования методом ветвей и границ (542). 3.3. Пример решения задачи методом ветвей и границ (545). § 4. Сетевое планирование. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 547 4.1. Построение сетевого графика (548). 4.2. Расчет минимальной продолжительности разработки проекта (552). Упражнения к теме 6. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 553 Список литературы к теме 6 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 555 Предметный указатель к тому 1 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 556 Предметный указатель к тому 2 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 561
Об авторе
 Токарев Владислав Васильевич Доктор физико-математических наук, профессор, главный научный сотрудник Института системного анализа РАН. Заслуженный деятель науки Российской Федерации, заслуженный профессор Московского физико-технического института (МФТИ).
Один из ведущих специалистов по теории и методам оптимизации и ее приложениям к механике космического полета, по управлению экономическими объектами и математической экономике. Опубликовал 3 монографии и более 120 статей, многие из которых переведены на английский язык и изданы за рубежом. Автор трех популярных учебников для вузов по математическому моделированию и методам оптимальных решений. |