Д. Б. Юдин, Е. Г. Гольштейн. Задачи и методы линейного программирования . - М., 1961. - 492 с.
Книга является первым в отечественной литературе систематическим изложением теоретических основ, методов и приложений новой математической дисциплины — линейного программирования. Основное внимание здесь обращено на обоснование и описание вычислительных алгоритмов, которые доводятся до расчетных схем и иллюстрируются примерами.
Книга предназначена для широкого круга специалистов — математиков, инженеров и экономистов с повышенной математической подготовкой.
ОГЛАВЛЕНИЕ
Предисловие............................3
Глава 1. Основные понятия линейного программирования . 7
§ 1. Предмет линейного программирования ... 7
§ 2. Задачи линейного программирования ........ 11
п. 2.1. Организация снабжения..............11
п. 2.2. Выбор системы вооружения..............18
п. 2.3. Размещение заказов и загрузка оборудования . 20
§ 3. Каноническая форма задач линейного программирования ................23
§ 4. Геометрический смысл простейших задач линейного программирования..................27
§ 5. Выпуклые многогранники и линейное программирование ........................38
§ 6. Векторы условий и вектор ограничений ... 48
§ 7. Геометрические интерпретации общей задачи линейного программирования..............52
§ 8. Экономическая интерпретация и терминология задачи линейного программирования ..... 59
§ 9. Общая характеристика методов линейного программирования ...........63
§ 10. Краткая историческая справка ......
Глава 2. Практические задачи линейного программирования 75
§ 1. Задача о смеси....................78
§ 2. Об оптимальном раскрое материалов .... 78
§ 3. Распределение самолетов между воздушными линиями........................83
§ 4. Сельскохозяйственные задачи............84
§ 5. Задачи о размещении оборудования .... 88
§ 6. Общая планово-производственная задача ... 91
§ 7. Проблема составления графиков..........95
§ 8. Дилемма: быстро, но дорого, или медленно, но дешево............100
§ 9. Выбор рациональной системы допусков . . . 103
§ 10. Планирование производства и перевозок .....110
§ 11. Военные приложения методов линейного программирования (по материалам зарубежной печати) .....119
§ 12. Проблема узких мест . ....... 120
§ 13. Задача целераспределения .......125
§ 14. Теоретико-игровые модели задач линейного программирования ..........131
Глава 3. Метод последовательного улучшения плана . . 136
§ 1. Основы метода . 137
§ 2. Выбор начального опорного плана . . ...... 147
§ 3. Связь между параметрами последовательных приближений ........... 151
§ 4. Алгоритм метода последовательного улучшения плана .............160
§ 5. Вторая форма критерия оптимальности .... 178
§ 6. II алгоритм 182
§ 7. Вырожденность..........204
§ 8. Исследование общих проблем линейного программирования с помощью метода последовательного улучшения плана . ..........214
Глава 4. Общие методы линейного программирования, основанные на принципе двойственности ... 217
§ 1. Основы теории двойственности......217
п. 1.1. Постановка вопроса.......217
п. 1.2. Теоремы двойственности..... . 222
п. 1.3. Задачи линейного программирования со смешанными условиями........228
п. 1.4. Задачи линейного программирования в канонической форме.........234
п. 1.5. Критерии оптимальности......237
п. 1.6. Геометрическая интерпретация задач двойственной пары.........242
§ 2. Метод последовательного уточнения оценок . . 246
п. 2.1. Предварительные замечания .... 246
п. 2.2. Основы метода....................248
п. 2.3. Геометрическая интерпретация метода . . 258
п. 2.4. Алгоритм метода........259
п. 2.5. Способы отыскания первого приближения . 266
п. 2.6. Случай вырожденности......276
п 2.7. Методы улучшения плана и уточнения оценок..... 285
п. 2.8. Пример...........290
§ 3. Метод последовательного сокращения невязок ...... 300
п. 3.1. Предварительные замечания ........ . 300
п. 3.2. Описание метода ........ 303
п. 3.3. Алгоритм метода . 310
п. 3.4. Пример...........317
п. 3.5. Об оценках быстроты сходимости метода сокращения невязок ........ 323
Глава 5. Транспортная задача 326
§ 1. Постановка вопроса и предварительные замечания 327
п. 1.1. Постановка задачи . . . . . . . 327
п. 1.2. О разрешимости транспортной проблемы . . 333
п. 1.3. Алгоритм построения плана.....335
п. 1.4. Транспортная задача с нарушенным балансом
производства и потребления . . . . 338
п. 1.5. Свойства решений транспортной задачи . . 340
п. 1.6. Условия невырожденности транспортной задачи 343
п. 1.7. О задачах, сводящихся к транспортной ...... . 346
§ 2. Метод потенциалов....... 349
п. 2.1. Предварительные замечания ...........349
п. 2.2. Описание метода потенциалов .... 350
п. 2.3. Описание алгоритма ......... 356
п. 2.4. Метод минимального элемента .... 365
п. 2.5. Распространение метода на вырожденные задачи . ... 369
§ 3. Венгерский метод.........377
п. 3.1. Предварительные замечания.....377
п. 3.2. Проблема выбора.........379
п. 3.3. Алгоритм решения проблемы выбора . . . 380
п. 3.4. Обоснование алгоритма решения проблемы выбора ............383
п. 3.5. Общая транспортная задача, алгоритм . . 393
п. 3.6. Обоснование алгоритма решения общей транспортной задачи..........398
п. 3.7. Пример...........402
п. 3.8. Особенности венгерского метода .... 404
Глава 6. Математические основы линейного программирования 408
§ 1. Конечномерные пространства и выпуклые множества 408
п. 1.1. Конечномерное векторное пространство . . 408
п. 1.2. Выпуклые множества.......415
п. 1.3. Крайние точки множества и их свойства . . 420
п. 1.4. Выпуклые конусы . . ......426
§ 2. Доказательства теорем двойственности .... 434
§ 3. Обоснование некоторых утверждений главы 5 ..... 441
Глава 7. Заключение . ........459
§ 1. Некоторые специальные вопросы линейного программирования ...........461
п. 1.1. Выпуклое программирование.....461
п. 1.2. Целочисленное программирование .... 464
п. 1.3. Учет специфики задач......465
§ 2. Линейное программирование и теория игр . . . 467
§ 3. Перспективные вопросы линейного программирования ..............477
п. 3.1. Параметрическое программирование . . . 477
п. 3.2. Линейное программирование в условиях неопределенности .........480
Литература ...... .......484
