Грешилов А.А. Прикладные задачи математического программирования: Учебное пособие. - 2-е изд. - М., 2006. - 288 с: ил.
Рассмотрен широкий круг задач математического программирования в различных областях производства, экономики и менеджмента, повседневной жизни, а также в сфере разработки компьютерных игр. Представлены линейное программирование, сетевые (поточные) задачи, основы динамического программирования и теории игр. Изложены современные подходы к развитию методов решения задач математического программирования. Даны краткий математический словарь и перечень математических терминов.
Для студентов высших учебных заведений, получающих образование по направлениям и специальностям техники и технологии, экономики и менеджмента. Представляет интерес для широкого круга читателей, изучающих, разрабатывающих и использующих современные методы оптимизации, исследования операций и системного анализа.
ОГЛАВЛЕНИЕ
Предисловие ко второму изданию.....................................................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. Задача о наилучшем использовании посевной площади...............83
2.11. Задача о закреплении самолетов за воздушными линиями...........84
2.12. Задача о назначениях (проблема выбора)........................................87
2.13. Задача об оптимальном распределении самолетов между войсками и учебными полигонами.................................................90
2.14. Задача о рациональном соотношении между различными типами бронебойных снарядов.......................................................92
2.15. Задача о покрытии множества..........................................................93
2.16. Дробно-линейное программирование.............................................96
2.17. Анализ устойчивости оптимального решения задачи линейного программирования........................................................99
Глава 3. Сетевые (потоковые) задачи...................................................109
3.1. Основные определения и приложения потоковых моделей..........109
3.2. Задача о покупке автомобиля........................................................... 116
3.3. Задача о многополюсной кратчайшей цепи.................................... 120
3.4. Анализ сложности алгоритмов поиска кратчайших путей............. 126
3.5. Задача о назначениях (венгерский алгоритм)................................. 127
3.6. Задача размещения производства.................................................... 131
3.7. Задача о максимальном потоке........................................................ 133
3.8. Задача о многополюсном максимальном потоке............................138
3.9. Задача коммивояжера (метод ветвей и границ).............................. 143
3.10. Задача о многополюсной цепи с максимальной пропускной способностью..................................................................................152
Глава 4. Основы динамического программирования и теории игр ..156
4.1. Условия применимости динамического
программирования............................................................................ 156
4.2. Задача об оптимальной загрузке транспортного средства неделимыми предметами.................................................................. 159
4.3. Задача о вкладе средств в производство.......................................... 164
4.4. Задача о распределении средств поражения................................... 168
4.5. Вычислительные аспекты решения задач методом динамического программирования................................................ 173
4.6. Игры в чистых стратегиях................................................................. 174
4.7. Поиск оптимальной смешанной стратегии..................................... 181
Глава 5. О развитии методов решения задач математического
программирования........................................................193
5.1. Основные направления развития методов решения задач математического программирования............................................. 193
5.2. Понятие о параметрическом программировании........................... 194
5.3. Многопродуктовые потоки в сетях..................................................203
5.4. Специальный класс целочисленных задач
о многопродуктовом потоке............................................................207
5.5. Приближенное решение многопродуктовой транспортной
задачи методом агрегирования........................................................210
5.6. Приложения задач о многопродуктовом потоке ............................212
5.7. Эвристический алгоритм решения задачи синтеза сети
связи..................................................................................................217
5.8. Методы внутренней точки для задачи математического программирования...........................................................................233
5.9. Методы внешней точки для задачи математического программирования...........................................................................236
5.10. Комбинированный метод внутренней и внешней точек..............238
5.11. Метод проекции фадиента.............................................................240
5.12. Многокритериальные задачи линейного программирования.........................................................................243
5.13. Метод взвешенных сумм с точечным оцениванием весов...........247
5.14. Сжатие множества допустимых решений......................................250
5.15. Минимальные значения критериев на множестве эффективных точек........................................................................252
5.16. Параметризация целевой функции................................................254
5.17. Целевое программирование...........................................................260
Краткий математический словарь.............................................266
Список математических символов.............................................284
Список литературы..................................................................285
