Кузнецов Ю. Н., Кузубов В. И., Волощенко А. Б.
Математическое программирование: Учеб. пособие. 2-е изд., перераб, и доп. — М.: Высш. школа, 1980 — 300 «|
ил. - :,;|
В пер.: 70 к. 1
В книге изложен курс математического программирования — линейное, нелинейна
S динамическое программирование. Основной теоретический материал вллюстриров»1 римерами, упражнениями и задачами экономического характера.
Во второе издание включены основы параметрического линейного програ» вания, более подробно освещены градиентные методы решения задач иелине программирования.
Предназначается для студентов экономических специальностей вузов,
ПРЕДИСЛОВИЕ
В данной книге авторы стремились и§л<н жить в доступной форме основные разделы математического программирования, основываясь при этом на ныне действующих программах для студентов экономических специальностей вузов. Однако книга может быть использована не только студентами, но и теми лицл-ми, которые самостоятельно изучают данный курс или сталкиваются в своей нрот{зводствен-ной деятельности'с математическим программированием. Этому способствует значительное количество приведенных в книге примеров и задач, в том числе с экономическим содержанием. В некоторых из них был использован многолетний опыт авторов в разработке и внедрении методов математического программирования в народном хозяйстве.
Второе издание (первое-вышло в 1976 г.)
расширено по сравнению с первым за счет
включения основ параметрического лк;ич":,ч-,го
программирования. Уточнены некоторые ci>
" ределения и устранены замеченные опечатки.
Авторы благодарны за полезные советы
рецензенту проф. В. Д. Андрееву, а также
всем лицам, приславшим свои пожелания и
замечания по первому изданию книги.
Авторы
ОГЛАВЛЕНИЕ
Предисловие ..... ..... ,....., J
Введение . ....... .......... 'i
Глава I Линейное программирование
§ 1. Общие понятия ....... . . . i « i i § ''
1. Построение математических моделей простейших экономических задач (8). 2. Замена неравенств уравнениями (11)
§ 2. Линейные векторные пространства ...... , . . i 1-
1. Понятие n-мерного пространства (14). 2. Линейная зависимость векторов (16). 3. Базис n-мерного векторного пространства (21).. 4. Система единичных векторов n-мерного векторного пространства (22).. 5. Решение системы линейных уравнений методом Жордана— •> Гаусса (24). 6. Разложение векторов по базису, переход от одного базиса к другому (30) . , '
§ 3. Общая задача линейного программирования .,..,.» 8 1. Формулировка задачи (33). 2. Выпуклые множества (34). 3. Гео« метрическая интерпретация задачи линейного программирования (38). 4. Свойства решений задачи линейного программирования (40)
§ 4. Графический метод решения задачи линейного программирования ' 4 1. Область применения (44), 2. Примеры задач, решаемых графическим методом (46)
§ 5. Симплексный метод решения задачи линейного программирования 8 1. Построение опорных планов (52). 2. Отыскание оптимального плат на. Условия оптимальности (56). 3. Алгоритм симплексного мето« да (57). 4. Метод искусственногб базиса (об). 5. Задача do смешад* ными ограничениями (72) . 6. Геометрическая интерпретация симплекс» v ного метода (74)
§ в. Применение общей задачи линейного программирования к решению . некоторых экономических задач .,.,.,,...-. * 1. Задача использования ресурсов (76). 2. Задача составления диеты (78)
§ 7. Двойственность в линейном программировании , ( t .«»,'•' ~ двойственности (84). 2. Несимметричные двойственные за-
- ? ^ - -' /ЛЛ\ Л 't9.tr.TT ПЛЯТО-
1. Понятие «и~..~,—..-- „-,. -. ------г , ..
дачи (85). 3. Симметричные Двойственные задачи (90). 4.'Виды математических моделей двойственных задач (92), 5. Двойственный симп-^, лексный метод (93) / -----•----.--
§ 8. Целочисленное программирование "*" . . ; . . .- , ; i 97, 1. Постановка задачи и метод решения (98). 2. Составление дополнительного ограничения (99). 3. Некоторые экономические задачи целочисленного программирования (101)
§ 9. Транспортная задача линейного программирования . . . . . 106 1. Постановка задачи и ее математическая модель (106). 2. Построение первоначального опорного плана (108). 3. Метод, потенциалов (113). 4. Открытая модель транспортной задачи (121). б. Дельта-метод решения транспортной задачи (124)
§ 10. Приложения транспортной задачи к решению некоторых экономических задач............, 133
1.,Увеличение производительности автомобильного транспорту за счет минимизации порожнего пробега (134). 2. Оптимальное закрепление за станком Операций по обработке, деталей (136). 3. Оптимальные назначения, или проблема выбора (138). 4. Задачи размещения с учетом транспортных и производственных затрат (141). б. Решение задач „с пемощью метода запрещения перевозок (145)
§ 11. Параметрическое линейное программирование . . , \ • • 150 1. Задача с параметром в целевой функции (150). 2. Задача с параметром в свободных членах системы ограничений (156).
' Г л а в а II
Нелинейное программирование
§ 1. Общая задача нелинейного программирования ,.,...,, 163
•§ 2. Метод множителей Лагранжа........... 166
§ 3. Выпуклые и вогнутые функции........... 172
§ 4. Приближенные методы решения задач с сепарабельными функциями 175
§ 5. Теорема Куна — Таккера............, 183
§ 6. Квадратичное программирование.......... 185
1. Метод Била (191). 2. Метод Баранкина — Дорфмана (199). 3. Метод Франка — Вольфа (204). 4. Двойственность в квадратичном программировании (209)
§ 7. Градиентные методы решения задач нелинейного программирования 211 1. Метод проектируемых градиентов Розена (212). 2. Метод допустимых направлений Зойтендейка (220)
Глава III Динамическое программирование
§ 1. Основные понятия и постановка задачи динамического программирования .................231,
1. Понятие динамического программирования (231). 2. Общая постановка задачи динамического программирования (234). 3. Геометрическая интерпретация задачи динамического программирования (234). 4. Принцип поэтапного построения оптимального управления (235) *
§ 2. Простейшие экономические задачи, решаемые методом динамического
программирования.............. 235
1. Задача о минимизации расхода горючего самолетом при наборе высоты и скорости. Постановка задачи (238). 2. Задача определения кратчайших расстояний по заданной сети (243)
§ 3. Метод функциональных уравнений .....,..,; 248
§ 4. Экономические задачи, решаемые методом функциональных уравнения 252
1. Задача распределения ресурсов (252). 2. Задачи замены оборудования (259),
299
§ 5. Детерминированные процессы ...'.• * . • • '• , s ". 270 § 6. Простейшие стохастические задачи. динамического программирования 271
1. Задача распределения ресурсов в стохастическом варианте (273).
2. Задача добычи полезного ископаемого (274)
•
Глава IV 'Элементы теории матричных игр
§ 1. Предмет теории игр, основные понятия . ...'•. . . , s . 278
§ 2. Сведение матричной игры к задаче линейного программирования 287
§ 3. Игры с природой............... 290
Литература . .-.-•; ... . ........ . 294
Предметный указатель.............. 295
