Ашманов С. А. Линейное программирование. — М: Главная редакция физико-математической литературы, 1981.— 340 с.
В книге излагаются основные разделы теории и численные методы решения задач линейного программирования. Значительное место уделяется качественному исследованию свойств содержательных моделей методами линейного программирования. Основной материал сопровождается упражнениями теоретического характера.
ОГЛАВЛЕНИЕ
Предисловие ..................5
Глава I. Линейные модели ..................9
§ 1. Линейное программирование — инструмент исследования линейных моделей.........9
§ 2. Примеры линейных моделей.......10
§ 3. Различные формы задач линейного программирования и их эквивалентность........28
§ 4. Проблема отыскания численного решения задачи
линейного программирования................35
Глава II. Выпуклые многогранники и линейные неравенства 38
§ 1. Геометрическая интерпретация задач линейного программирования ...........38
§ 2. Выпуклые множества и теоремы о разделяющей гиперплоскости ............41
§ 3. Многогранные выпуклые множества.....52
§ 4. Структура допустимых множеств задач линейного программирования ..........63
§ 5. Эквивалентность двух определений выпуклого многогранного множества....................74
§ 6. Линейные неравенства.........78
Упражнения. ..............81
Глава III. Теория двойственности.......83
§ 1. Двойственная задача линейного программирования..........83
§ 2. Теорема двойственности.........87
§ 3. Короткое доказательство теоремы двойственности...... 95
§ 4. Строение множества решений задачи линейного программирования ...........97
§ 5. Интерпретация двойственных оценок и дифференциальные свойства функции значений.....100
Упражнения..............ИЗ
Глава IV. Применения теории двойственности . .... . 116
§ 1. Основная теорема о матричных играх.....116
§ 2. О проблеме существования ядра в кооперативной игре n лиц.............126
§ 3. Свойства неотрицательных матриц . . . . 136
§ 4. Эффект замещения в обобщенной модели Леонтьева 141
§ 5. Теорема о магистрали для динамической модели планирования . ..........146
§ 6. Принцип максимума для дискретных линейных задач оптимального управления.......152
Упражнения.......... 157
Глава V. Теория симплекс-метода 158
§ 1. Метод исключения Жордана — Гаусса для систем линейных уравнений...........158
§ 2. Опорные планы ..........161
§ 3. Симплекс-метол для невырожденной задачи линейного программирования ........167
§ 4. Вырожденные задачи линейного программирования ........178
§ 5. Нахождение начального опорного плана .... 181
§ 6. Иллюстративный пример численного решения задачи
линейного программирования . .....186
§ 7. Модифицированный симплекс-метод.....191
Упражнения............. 193
Глава VI. Двойственный симплекс-метод ..... 195
§ 1. Псевдопланы и правила двойственного симплекс-метода ..... .......,195
§ 2. Применение двойственного симплекс-метода к задаче
с дополнительным ограничением . . . . . 201
§ 3. Симплексная таблица в координатной форме ... 203
§ 4. Двойственный симплекс-метод в координатной форме 207
§ 5. Нахождение начального псевдоплана .... 209
§ 6. Лексикографическая задача линейного программирования.............212
Глава VII. Специальные задачи линейного программирования ............217
§ 1. Транспортная задача и транспортные сети . . . 217
§ 2. Нахождение начального опорного плана транспортной задачи методом северо-западного угла . . . 222
§ 3. Опорные планы транспортной задачи и вырожденность ... . ... 226
§ 4. Метод потенциалов решения транспортной задачи 231
§ 5. Целочисленные задачи линейного программирования 239
§ 6. Метод отсечения для целочисленных задач линейного программирования . . . . . . 245
§ 7. Первый алгоритм Гомори для целочисленных задач линейного программирования.......248
§ 8. Блочное программирование.......264
Глава VIII. Метод регуляризации неустойчивых задач линейного программирования . . 271
§ 1. Понятие устойчивости задач линейного программирования . . . . . 271
§ 2. Параметрические системы линейных неравенств ...... 273
§ 3. Необходимые и достаточные условия устойчивости
задач линейного программирования.....278
§ 4. Регуляризация неустойчивых задач.....284
Добавление О новом методе решения задач линейного программирования ...............287
Разбор упражнений............291
Литература...............301
Предметный указатель............303
