Методы линейного программирования, как известно, нашли широкое применение в задачах, возникающих в экономике, технике и других областях человеческой деятельности. Для решения практических задач линейного программирования на ЭВМ разработан целый ряд стандартных пакетов программ. Основу большинства таких пакетов составляет симплекс-метод, предложенный Дж. Данцигом более 30 лет тому назад. С тех пор создано множество весьма изощренных алгоритмов метода. Основные усилия были направлены на сокращение времени решения, на повышение вычислительной устойчивости и на разработку алгоритмов, позволяющих решать задачи больших размеров.
Исследования по совершенствованию алгоритмов симплекс-метода и созданию других методов линейного программирования продолжают интенсивно развиваться, однако результаты этих исследований можно найти лишь в журнальных статьях или в материалах симпозиумов.
Публикуемая книга Б. Муртафа достаточно полно отражает современное состояние методов и алгоритмов, реализованных в основном в коммерческих пакетах линейного программирования; этому посвящена первая часть книги.
В этой части систематизированы результаты многих авторов, связанные с методами представления обратной базисной матрицы в симплеке-методе. Способам построения и пересчета множителей, представляющих обратную базисную матрицу, обладающим различными вычислительными преимуществами, уделяется большое внимание. Специальная глава посвящена основанным на симплекс-методе методам оптимизации для задач нелинейного и частично-целочисленного программирования. Следует отметить, что материал, касающийся расширений симплекс-метода, теории двойственности, чувствительности и устойчивости решений, достаточно полно освещен в литературе, опубликованной у нас в стране.
Вторая часть книги посвящена вопросам формулирования и решения практических задач при использовании стандартных пакетов программ. Эта часть представляет наибольший интерес для тех, кто приступает к анализу задач линейного программирования больших размеров с помощью ЭВМ. Здесь детально описывается процесс построения матрицы ограничений задачи, а также структура входных и выходных данных, единая для большинства коммерческих пакетов.
ОГЛАВЛЕНИЕ
Предисловие редактора перевода . ,................, . 5
Предисловие............................ 7
ЧАСТЬ I. ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ............... 9
ГЛАВА 1. НЕОБХОДИМЫЕ СВЕДЕНИЯ ИЗ ЛИНЕЙНОЙ АЛГЕБРЫ
1.1. Определение матрицы................... 9
1.2. Определение вектора................... 9
1.3. Арифметические операции над матрицами и векторами ... Ю
1.3.1. Сложение..................... Ю
1.3.2. Умножение матриц................ 10
1.3.3. Умножение на скаляр............... И
1.4. Единичная матрица................... 12
1.5. Обращение матрицы................... 12
1.6. Линейно независимые векторы.............. 12
1.7. Неособенные матрицы.................. 13
1.8. Матричное представление линейных уравнений...... 14
1.9. Блочные матрицы.................... 15
1.10. Элементарные преобразования.............. 15
1.11. Матричное тождество Шермана — Моррисона....... 17
1.12. Разреженные и плотные матрицы............. 17
1.13. Решение линейных уравнений.............. 18
1.13.1. Исключение................... 19
1.13.2. Обратная подстановка............... 21
1.13.3. Перестановка строк................ 21
1.13.4. LU-разложение.................. 22
ГЛАВА 2. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД...... 25
2.1. Формулировка задачи.................. 25
2.2. Допустимое базисное решение........,...... 26
2.3. Преобразованная задача ................. 27
2.4. Условия оптимальности................. 27
2.5. Элементарные преобразования базиса.......... 30
2.6. Шаги модифицированного симплекс-метода......... 32
2.7. Начальное допустимое решение.............. 34
ГЛАВА 3. МЕТОДЫ РАЗРЕЖЕННЫХ МАТРИЦ.......... 38
3.1. Введение........................ 38
3.2. Хранение........................ 39
3.3. Ошибки округления................... 41
3.3.1. Определение.................... 41
3.3.2. Масштабирование . ................ 41
3.3.3. Контроль роста ошибок.............. 42
3.3.4. Допуски на ошибку................ 43-|
3.4. Мультипликативная ч факторизованная формы обратной мат-
РИДЫ........................ 43'
3.4,1, Мультипликативная форма . ..,.,..,.*.• 4Jl
3.4.2. LU-разложение базиса............... 45
3.4.3. Метод Форреста и Томлина............. 50
3.4.4. Другие методы разложения............. 52
3.5. Перепостроение обратной матрицы............ 53
3.5.1. Процедура предварительного выбора ведущих элементов
с использованием разбиения (Р4) ............ 55
3.6. Методы оценивания................... 60
3.6.1. Введение..................... 60
3.6.2. Частичное оценивание............... 61
3.6.3. Многократное оценивание............. 61
3.6.4. Метод оценивания в системе DEVEX........ 62
3.6.5. Метод оценивания с поиском наиболее крутого ребра 63
У1АВА 4. ДВОЙСТВЕННОСТЬ И ПОСТОПТИМАЛЬНЫЙ АНАЛИЗ ' 67
4.1. Каноническая форма................... 67
4.1.1. Теорема двойственности............... 67
4.2. Оценки ресурсов: экономическая интерпретация...... 70
4.3. Маргикальные оценки.................. 73
4.4. Диапазоны устойчивости......'........... 74
4.4.1. Изменения коэффициентов целевой функции..... 75
4.4.2. Изменения компонент вектора ограничений ..... 78
4.4.3. Изменение коэффициентов матрицы ограничений ... 81
4.5. Вырожденность..................... 8!
4.5.1. Вырожденность прямой задачи........... 81
4.5.2. Вырожденность двойственной задачи........ 82
4.6. Пример: предприятие по переработке руды........ 83
4.6.1. Оценки ресурсов................. 85
4.6.2. Маргинальная оценка............... 85
4.6.3. Изменения коэффициентов целевой функции..... 86
4.6.4. Изменения компонент вектора ограничений ..... 87
4.7. Двойственный симплекс-метод............... 88
ЛАВА 5. СПЕЦИАЛЬНЫЕ ВАРИАНТЫ СИМПЛЕКС-МЕТОДА . . 91
5.1. Учет двусторонних ограничений............. 91
5.1.1. Расчет маргинальных оценок............ 95
5.2. Учет обобщенных двусторонних ограничений....... 95
5.2.1. Шаги алгоритма................., 99
5.3. Параметрическое программирование........... 101
5.3.1. Параметрическое изменение вектора коэффициентов целевой функции . . ................... 101
5.3.2. Параметрическое изменение вектора ограничений . . 103
5.4. Декомпозиция...................... 105
ЛАВА 6. НЕЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ, БАЗИРУЮЩЕЕСЯ НА СИМПЛЕКС-МЕТОДЕ ... 109
6.1. Сепарабельное программирование............. 109
6.2. Метод аппроксимирующего программирования (МАП) . , , 112
6.3. MINOS......................... 114
6.3.1. Краткое изложение метода............. П7
6.3.2. Распространение метода на нелинейные ограничения . 120
6.4. Целочисленное программирование............. J22
6.4.1. Метод ветвей и границ.............. 122
6.4.2. Формулирование задач целочисленного программирования ........................... 127
6.4.3. Специально упорядоченные множества ,..,,... 12-9
ЧАСТЬ II. ВЫЧИСЛИТЕЛЬНАЯ ПРАКТИКА............ 131
ГЛАВА 7. ФОРМУЛИРОВАНИЕ ЗАДАЧИ............. 13L
7.1. Введение........................ 131
72. Определение границ: широта охвата и детализация..... 131
7.3. Использование блок-схем................ 138
7.4. Описательные ограничения............... 140
7.5. Ограничения на ресурсы и конечное потребление...... 143
7.6. Условия, налагаемы? извне................ 146
7.7. Определение целевой функции.............. 147
ГЛАВА 8. ПОСТРОЕНИЕ МАТРИЦЫ БОЛЬШОГО РАЗМЕРА .... 156
8.1. Введение........................ 156
8.2. Составление таблиц данных................ 156
83. Обработка списков и таблиц............... 164
8.4. Языки генераторов матриц................ 166
8.5. Контроль ошибок.................... 171
8.6. Советы и приемы.................... 173
8.6.1. Вектор изменения жесткости задания условий .... 173
8.6.2. Суммирующие строки............... 174
8 6.3. Условия неотрицательности переменных....... 175
8.6.4. Переменные, неограниченные по знаку (свободные переменные) ......................... 176
8.6.5. Свободные строки. Интервальные строки...... \П
8.6.6. Фиксированные переменные............. 177
8.6.7. Оценивание дополнительных переменных...... 177
8.6.8. Нелинейные характеристики............ 177
ГЛАВА 9. КОММЕРЧЕСКИЕ СИСТЕМЫ: ОРГАНИЗАЦИЯ ДАННЫХ 181
9.1. Введение........................ 181
9.2. MPS-формат входных данных............... 181
9 3. Команды управления................... 188
9 4. Допуски на ошибки................... 189
9.5. Процедуры запоминания базиса (GETOFF) и возобновления
счета (RESTART).................... 190
-* 6. Расширения....................... 192
9.6.1. Учет обобщенных двусторонних ограничений .... 192
9.6.2. Параметрическое программирование......... 193
9.6.3. Сепарабельное программирование.......... 194
9.6.4. Частично-целочисленное программирование..... 195
9.6.5. Специально упорядоченные множества........ 195
ГЛАВА 10. КОММЕРЧЕСКИЕ СИСТЕМЫ: ИНТЕРПРЕТАЦИЯ ВЫХОДНЫХ ДАННЫХ.................. 196
10.1. Введение........................ 196
10.2. MPS-формат выходных данных............., 196
10.3. Вариация параметров. Процедура RANGE........ 199
10.4. Языки для составления отчетов.............. 210
Приложение А. Программа PDS/MAGEN............... 215
Библиография , , , ......., , , ,.......,....., 219
