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

Φ. Μ. ПРОГ Г Т Л /'""ЧГПТ Р. Габасов, Φ. Μ. Кириллова МЕТОДЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Часть 2 ТРАНСПОРТНЫЕ ЗАДАЧИ МИНСК ИЗДАТЕЛЬСТВО БГУ им. В. И. ЛЕНИНА 1978 517. 8 Γ 12 УДК 519. 82 Рецензент доктор физико-математических наук, профессор И. В. Романовский Scan AAW Методы линейного программирования. Ч. 2. Транспортные задачи. Габасов Р. , Кириллова Φ. Μ. Минск, Изд-во БГУ им. В. И. Ленина, 1978. Основные методы, изложенные в первой части для общей задачи линейного программирования, конкретизируются для транспортных задач, рассматриваются транспортные задачи в матричной и в сетевой формах, закрытые и открытые, однопродуктовые и многопродуктовые, сети и мультисети. При исследовании этих задач значительно больше внимания, чем в общем случае, уделяется безопорным методам. Показывается, что для решения производных задач эффективным методом является динамическое программирование, с помощью которого получается ряд известных методов (венгерский метод, метод контуров и др. ). Подробно изучаются вырожденные и квазивырожденные задачи. Анализ решений во второй части более тщателен, чем в первой. Отдельная глава посвящена обобщенной транспортной задаче, которая известна в литературе и как распределительная задача. Наряду с прямыми методами рассматриваются и двойственные, что позволяет эффективно использовать разнообразную априорную информацию. Табл. 35, рис. 31, библ. 5 назв. 30502-037 Г М317-78 49"™ q) Издательство БГУ им. В. И. Ленина, 1978 г. ОГЛАВЛЕНИЕ ПРЕДИСЛОВИЕ 5 ВВЕДЕНИЕ 7 Глава I. ПРЯМОЙ ОПОРНЫЙ МЕТОД 13 ■§ 1. Транспортная задача в матричной форме . . 13 § 2. Открытые транспортные задачи ... . 23 § 3. Задача с фиксированными перевозками ... 27 § 4. Транспортная задача в сетевой форме ... 29 § 5. Мультипоток минимальной стоимости ... 46 § 6. Поток минимальной стоимости на мультисети 53 Глава II. ДВОЙСТВЕННЫЙ ОПОРНЫЙ МЕТОД ... 56 § 1. Матричная транспортная задача ... . 56 § 2. Сетевая транспортная задача 67 Глава III. ПРЯМОЙ БЕЗОПОРНЫЙ МЕТОД ... . 74 § 1. Производная задача 74 § 2. Общая схема метода 79 § 3. Решение производной задачи 84 § 4. Построение приближенных решений ... 89 Глава IV. ДВОЙСТВЕННЫЙ БЕЗОПОРНЫЙ МЕТОД . . 91 § 1. Производная задача 92 § 3- Общая схема метода 103 § 3. Решение производной задачи 108 § 4. Построение субоптимальных решений . . . 120 Глава V. ВЫРОЖДЕННЫЕ ЗАДАЧИ 121 § 1. Улучшение вырожденных опорных планов перевозок и потоков 122 § 2. Улучшение вырожденных опорных копланов перевозок и копотоков ... ... . 129 3 § 3. Квазивырожденные опорные планы перевозок и потоки 133 § 4. Квазивырожденные опорные копланы перевозок и копотоки 137 Глава VI. АНАЛИЗ РЕШЕНИЯ 138 § 1. Множества оптимальных и субоптимальных планов 139 § 2. Вариация параметров стоимости ... . 148 § 3. Вариация параметров ограничений . . . . 153 § 4. Изменение размеров задачи 160 Глава VII. ОБОБЩЕННАЯ ТРАНСПОРТНАЯ ЗАДАЧА . . 163 § 1. Матричная модель 164 § 2. Задача о потоке минимальной стоимости на обобщенной сети 191 ДОПОЛНЕНИЯ 216 1. Нагруженная транспортная задача . . . . 216 2.