Данциг Д. Линейное программирование, его применения и обобщения ОНЛАЙН


ОГЛАВЛЕНИЕ
Предисловие……………………………………………………..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
Глава 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
БИБЛИОГРАФИЯ
Часть 1

Часть 2



Читать онлайн
скачать бесплатно


Теги:
линейное программирование, Данциг, обобщения линейного программирования, применения линейного программирования

Коментарі до Данциг Д. Линейное программирование, его применения и обобщения ОНЛАЙН