Читать онлайн «Прикладные задачи математического программирования: учеб. пособие для студентов высш. техн. учеб. заведений»

1 /, И V А. А. ГРЕШИЛОВ V4^ / \ \ s - " к V. ^ЗАДАЧИ ' МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ и 1 • - . ^у *■* • 1 * t, A " . . ' и * УЧЕБНОЕ ПОСОБИЕ A. A. Грешилов ПРИКЛАДНЫЕ ЗАДАЧИ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ Издание второе, дополненное Допущено Министерством образования Российской Федерации в качестве учебного пособия для студентов высших технических учебных заведений И Москва • «Логос» • 2006 УДК 004. 4 ББК22. 18 Г81 Рецензенты: Л. В. Маркин, кандидат технических наук, А. В. Тимохов, кандидат физико-математических наук Грешилов А. А. Г 81 Прикладные задачи математического программирования: Учебное пособие. - 2-е изд. - М. : Логос, 2006. - 288 с: ил. ISBN 5-98704-077-9 Рассмотрен широкий круг задач математического программирования в различных областях производства, экономики и менеджмента, повседневной жизни, а также в сфере разработки компьютерных игр. Представлены линейное программирование, сетевые (поточные) задачи, основы динамического программирования и теории игр. Изложены современные подходы к развитию методов решения задач математического программирования. Даны краткий математический словарь и перечень математических терминов. Для студентов высших учебных заведений, получающих образование по направлениям и специальностям техники и технологии, экономики и менеджмента. Представляет интерес для широкого круга читателей, изучающих, разрабатывающих и использующих современные методы оптимизации, исследования операций и системного анализа. ББК22. 18 ISBN 5-98704-077-9 © А. А. Грешилов, 2005 © «Университетская книга», 2005 © «Логос», 2006 ОГЛАВЛЕНИЕ Предисловие ко второму изданию 5 Введение 7 Глава 1. Введение в математическое программирование 9 1. 1. Общие положения математического программирования 9 1. 2. Обшая запись задачи математического программирования и ее виды 20 1. 3. Некоторые сведения об экстремуме функции, частных производных, градиенте и производной по направлению 22 1. 4. Особенности нахождения оптимальных решений в задачах математического программирования 26 1. 5. Необходимые и достаточные условия оптимума в задачах математического программирования 30 1. 6. Теория двойственности и недифференциальные условия оптимальности в задаче выпуклого программирования 34 1. 7. Графическое решение задач математического программирования 38 1. 8. Простейшая оптимизационная задача 41 Глава 2. Линейное программирование 43 2. 1. Математическая постановка задачи линейного программирования 43 2. 2. Симплекс-метод — основной метод решения задач линейного программирования 46 2. 3. Метод полного исключения Жордана для решения систем линейных алгебраических уравнений 51 2. 4. Как спланировать выпуск продукции пошивочному предприятию 53 2. 5. Двойственность в задачах линейного программирования 59 2. 6. Как оптимально организовать поставку грузов от поставщиков к потребителям (транспортная задача) 66 2. 7. Задача о перевозках с перегрузкой 73 2. 8. Целочисленное линейное программирование 75 2. 9. Постановка задачи об оптимальном раскрое материалов (о минимизации отходов) 82 2. 10.