Читать онлайн «Методы линейного программирования 1»

Р. Габасов, Φ. ДА. Кириллова МЕТОДЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ЧАСТЬ Р. Габасов, Φ. Μ. Кириллова МЕТОДЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Часть 1 ОБЩИЕ ЗАДАЧИ МИНСК ИЗДАТЕЛЬСТВО БГУ им. В. И. ЛЕНИНА 1977 517. 8 Γ 12 УДК 330. 115: 62-50 Рецензент доктор физико-математических наук, профессор И. В. Романовский Методы линейного программирования. Ч. 1. Общие задачи. Г а б а- сов Р. , Кириллова Ф. М. Минск, Изд-во БГУ им. В. И. Ленина, 1977. Излагаются методы решения разнообразных задач линейного программирования. Рассматриваются задачи, множество параметров которых не имеет специальной структуры. Обосновываются три группы методов: прямые, двойственные и комбинированные. В первой группе выделяются опорные и безопорные методы. Приведены модификации основных методов. Предложены новые методы решения вырожденных и квазивырожденных задач, методы анализа решений общих задач линейного программирования. При изложении основное внимание уделяется эффективному использованию всей информации, доступной специалистам, занятым исследованием физических прототипов рассматриваемых в книге математических моделей. Преложенные методы допускают останов после получения субоптимальных планов, с заданной точностью приближающихся к оптимальным. Табл. 33, библ. 7. 30502-058 Μ 317-77 0iW/ ScanAAW © Издательство БГУ им. В. И. Ленина, 1977 г. ОГЛАВЛЕНИЕ ПРЕДИСЛОВИЕ 5 ВВЕДЕНИЕ 7 Глава I. ПРЯМОЙ ОПОРНЫЙ МЕТОД 13 § 1. Задача с односторонними ограничениями 13 § 2. Задача без ограничений на часть переменных 36 § 3. Задача с двухсторонними ограничениями 42 Глава II. ДВОЙСТВЕННЫЙ ОПОРНЫЙ МЕТОД . 51 § 1. Задача с односторонними ограничениями 52 § 2. Задача с двухсторонними ограничениями 66 Глава III. НЕКОТОРЫЕ МОДИФИКАЦИИ ... . 71 § 1. Первая модификация 73 § 2. Вторая модификация 85 § 3. Третья модификация 89 Глава IV. БЕЗОПОРНЫЕ МЕТОДЫ 91 § 1. Метод одновременного решения прямой и двойственной задач 92 § 2. Двойственный метод 102 § 3. Прямой метод 107 Глава V. КОМБИНИРОВАННЫЕ МЕТОДЫ ... . 112 § 1. Метод двухсторонних оценок 112 § 2. Комбинированный опорный метод . . . 119 § 3. Опорно-безопорный метод 121 § 4. Безопорно-опорный метод 124 § 5. Комбинированный безопорный метод . . 125 3 Глава VI. ВЫРОЖДЕННЫЕ ЗАДАЧИ 126 § 1. Прямой метод 127 § 2. Двойственный метод 134 § 3. Другой подход к исследованию вырожденных задач 138 Глава VII. АНАЛИЗ РЕШЕНИЯ 142 § 1. Вариация вектора стоимости 143 § 2. Изменение вектора ограничений . . . . 151 § 3. Вариация матрицы условий 158 § 4. Измерение размеров задачи 162 ЛИТЕРАТУРА 172 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 173 ПРЕДИСЛОВИЕ Модели и методы линейного программирования имеют огромное прикладное значение и поэтому включаются в программы многих учебных заведений. Существует ряд монографий и пособий по линейному программированию, рассчитанных на аудиторию с самыми разными интересами. Появление в этой ситуации еще одной книги не может не вызвать определенных вопросов и поэтому требует соответствующего обоснования. Идея написания книги возникла у авторов после чтения студентам факультета прикладной математики БГУ лекций по избранным главам линейного программирования в дополнение к тем сведениям, которые были известны им из общих курсов.