Данциг Д. Линейное программирование, его применения и обобщения. - М., 1966. - 600 с.
На Западе Данцига считают основоположником линейного программирования. так как развитие этой дисциплины в США фактически началось с разработки им в конце 40-х годов знаменитого симплекс-метода для численного решения основной задачи линейного программирования. Монография Данцига удачно сочетает в себе предельно элементарное изложение основных, исходных вопросов линейного программирования, которое будет доступно даже совсем неискушенному в математике читателю, с главами, посвященными таким глубокий и математически тонким теориям, как принцип разложения или дискретное (целочисленное) программирование. Эту книгу можно, с известным основанием, считать своего рода энциклопедией линейного программирования (на год издания), в которой содержится в той или иной форме описание большинства основных вопросов, относящихся к этой дисциплине.
ОГЛАВЛЕНИЕ
Предисловие..............................................................5
От автора ..................................................................7
Глава 1. ПОНЯТИЕ О ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
1-1. Введение........................................................9
1-2. Задача программирования ...............................9
1-3. Определение линейного программирования ......................13
1-4. Классификация задач программирования ........................14
1-5. Математическое программирование и автоматизация..............17
Глава 2. ИСТОКИ И СВЯЗИ
2-1. Влияние второй мировой войны........................19
2-2. Экономические модели и линейное программирование..............23
2-3. Математические истоки и развитие................................27
2-4. Применение линейного программирования в промышленности ... 34
Глава 3. ФОРМУЛИРОВКА МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
3-1. Основные понятия..............................................37
3-2. Построение модели..............................................39
3-3. Транспортная задача............................................40
3-4. Примеры смешивания............................................47
3-5. Задача о смеси продукции......................................54
3-6. Простая задача о складе........................................59
3-7. Обучение на работе ............................................61
3-8. Основная математическая задача ................................64
3-9. Задачи..........................................................66
Глава 4. СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ И НЕРАВЕНСТВ
4-1. Системы уравнений с одинаковыми множествами решений..........73
4-2. Канонические системы .............................78
4-3. Линейные неравенства ..........................................85
4-4. Метод исключения Фурье — Моцкина............................87
4-5. Задачи линейного программирования в виде неравенств............88
4-6. Задачи..........................................................91
Глава 5. СИМПЛЕКС-МЕТОД
5-1. Симплекс-алгоритм..............................................%
5-2. Два этапа симплекс-метода......................................ЮЗ
5-3. Задачи..........................................................116
Глава 5. ОБОСНОВАНИЕ СИМПЛЕКС-АЛГОРИТМА И ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ ДВОЙСТВЕННОСТИ
6-1. Индуктивное обоснование симплекс-алгоритма ................123
6-2. Эквивалентные двойственные формы..............................126
6-3. Доказательство теоремы двойственности..........................131
6-4. Основные теоремы о двойственности..............................137
6-5. Множители Лагранжа ..........................................143
6-6. Задачи..........................................................147
Глава 1
ГЕОМЕТРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
7-1. Выпуклые области..............................................150
7-2. Симплекс-метод как метод наискорейшего спуска вдоль ребер . . . 158
7-3. Симплексная интерпретация симплекс-метода ....................162
7-4. Задачи..........................................................166
Глава 8. МЕТОД ВЕДУЩИХ ЭЛЕМЕНТОВ. ВЕКТОРНЫЕ ПРОСТРАНСТВА, МАТРИЦЫ И ОБРАТНЫЕ МАТРИЦЫ
8-1. Теория ведущих операций ......................................173
8-2. Векторные пространства ........................................177
8-3. Матрицы ......................................................183
8-4. Обратная матрица......................188
8-5. Симплекс-алгоритм в матричной форме............................194
8-6. Задачи..........................................................200
Глава 9. СИМПЛЕКС-МЕТОД, ИСПОЛЬЗУЮЩИЙ! МНОЖИТЕЛИ. (МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД)
9-1. Пример использования множителей..............................208
9-2. Общее описание модифицированного симплекс-метода..............214
9-3. Вычислительные правила использования множителей..............217
9-4. Задачи............................................223
Глава 10. КОНЕЧНОСТЬ СИМПЛЕКС-МЕТОДА С ВОЗМУЩЕНИЯМИ
10-1. Возможность зацикливания в симплекс-алгоритме................225
10-2. Возмущающие параметры для избежания вырождения..............229
10-3. Задачи..........................................................234
Глава 11. ВАРИАНТЫ СИМПЛЕКС-АЛГОРИТМА
11-1. Дополнительные прямой и двойственный базисы..................237
11-2. Двойственный симплекс-метод....................................239
11-3. Самосопряженный (двойственный себе) параметрический алгоритм 241
11-4. Алгоритм одновременного решения прямой и двойственной задач 243
11-5. Другой критерий для этапа I....................................249
11-6. Задачи..........................................................250
Часть 1
Глава 12. ПОНЯТИЕ ЦЕНЫ в ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
12-1. Механизм цен симплекс-метода..................................251
12-2. Примеры двойственных задач....................................257
12-3. Соглашение о знаках цен................................261
12-4. Иллюстрация анализа устойчивости........... . . . 262
12-5. Задачи..........................................................271
Глава 13. ИГРЫ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
13-1. Матричные игры................................................273
13-2. Эквивалентность матричных игр и задач линейного программирования; теорема о минимаксе ......................................282
13-3. Конструктивное решение матричной игры (другое доказательство
теоремы о минимаксе)............................................287
13-4. Задачи..........................................................293
Глава 14. КЛАССИЧЕСКАЯ ТРАНСПОРТНАЯ ЗАДАЧА
14-1. Исторический обзор...................... 295
14-2. Элементарная теория транспортировки ............. 296
14-3. Вычислительный алгоритм для транспортной задачи....... 303
14-4. Задачи............................. 308
Глава 15. ОПТИМАЛЬНОЕ НАЗНАЧЕНИЕ И ДРУГИЕ РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ
15-1. Задача об оптимальном назначении..............................310
15-2. Задачи с нарушенным балансом ................................316
15-3. Фиксированные значения и запрещенные клетки....................323
15-4. Задачи..........................................................325
Глава 16. ЗАДАЧА О ПЕРЕВОЗКАХ С ПРОМЕЖУТОЧНЫМИ ПУНКТАМИ
16-1. Формулировка модели ..................... 328
16-2. Эквивалентность транспортной задачи и задачи с промежуточными
пунктами ........................... 335
16-3. Решение задачи с промежуточными пунктами симплекс-методом . . 337
16-4. Задачи............................. 340
Глава 17. СЕТИ и ЗАДАЧА С ПРОМЕЖУТОЧНЫМИ ПУНКТАМИ
17-1. Графы и деревья .......................342
17-2. Интерпретация симплекс-метода на сети............. 346
17-3. Задача о кратчайшем пути................... 349
17-4. Задачи............................. 354
Глава 18. ОГРАНИЧЕННЫЕ СВЕРХУ ПЕРЕМЕННЫЕ
18-1. Общий случай......................... 355
18-2. Транспортная задача с ограниченными пропускными способностями
и ее обобщения ........................ 364
18-3. Задачи............................ 370
Глава 19. МАКСИМАЛЬНЫЕ ПОТОКИ В СЕТЯХ
19-1. Теория Форда — Фулкерсона.................. 372
19-2. Решение задачи о максимальном потоке методом деревьев..... 382
19-3. Задачи............................. 386
Глава 20. ПРИМЕНЕНИЕ МЕТОДА ОДНОВРЕМЕННОГО РЕШЕНИЯ ПРЯМОЙ И ДВОЙСТВЕННОЙ ЗАДАЧ К ТРАНСПОРТНОЙ ЗАДАЧЕ
20-1. Введение ........................... 387
20-2. Алгоритм Форда — Фулкерсона................. 388
20-3. Задачи............................. 393
Глава 21. ЗАДАЧА О ВЗВЕШЕННОМ РАСПРЕДЕЛЕНИИ
21-1. Почти треугольный базис ......................................395
21-2. Структура базиса с точки зрения графов..........................402
21-3. Подкласс задач с треугольными оптимальніїми базисами..........405
21-4. Задачи ............................................................411
Глава 22. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПЕРЕМЕННЫМИ КОЭФФИЦИЕНТАМИ '
22-1. Обобщенная задача Вулфа................... 413
22-2. Замечания о частных случаях.................. 419
22-3. Задачи............................. 425
Глава 23. ПРИНЦИП РАЗЛОЖЕНИЯ ДЛЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
23-1. Общий принцип................................................427
23-2. Принцип разложения, беллетризованное изложение..............433
23-3. Централизованное планирование без полной информации в центре 439
23-4. Разложение многошаговых задач линейного программирования . . 443
23-5. Задачи..........................................................446
Глава 24. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ
24-1. Общая теория..................................................447
24-2. Однородные целевые функции и задача химического равновесия . . 454
24-3. Вырожденные выпуклые целевые функции........................458
24-4. Квадратичное программирование ................................465
24-5. Задачи............................. 472
Глава 25. НЕОПРЕДЕЛЕННОСТЬ
25-1. Составление планов в случае переменных издержек........ 473
25-2. Планирование при неопределенном спросе........................477
25-3. О многошаговых задачах........................................481
25-4. Задачи..........................................................484
Глава 26. ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ С ДИСКРЕТНЫМИ ПЕРЕМЕННЫМИ
26-1. Обзор методов '......................... 487
26-2. Метод целочисленных форм Гомори .............. 493
26-3. О значении решения задач линейного программирования, в которых некоторые переменные целочисленные ............. 508
Глава 27. МОДЕЛЬ ДИЕТЫ ШТИГЛЕРА; ПРИМЕР ФОРМУЛИРОВКИ И РЕШЕНИЕ.......
27-1. Задачи при формулировании модели............... 521
27-2. Численное решение задачи о диете............... 527
27-3. Задачи............................. 536
Глава 28. РАСПРЕДЕЛЕНИЕ САМОЛЕТОВ ПО ЛИНИЯМ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОГО СПРОСА
28-1. Постановка задачи и математическая формулировка....... 539
28-2. Численное решение задачи распределения самолетов по линиям . . 551
БИБЛИОГРАФИЯ
Часть 2
