Читать онлайн «Линейное программирование»

ш LINEAR PROGRAMMING METHODS AND APPLICATIONS SAUL I. OASS APPLIED SCIENCE DEPARTMENT INTERNATIONAL BUSINESS MACHINES, INC. GRADUATE SCHOOL U. S. DEPARTMENT OF AGRICULTURE McGraw-Hill Book Company, Inc. New York Toronto London 1958 ФИЗИКО-МАТЕМАТИЧЕСКАЯ БИБЛИОТЕКА ИНЖЕНЕРА ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (МЕТОДЫ И ПРИЛОЖЕНИЯ) Перевод с английского ГОЛЬШТЕЙНА Е. Г. и СУШКЕВИЧА М. И. Под редакцией ЮДИНА Д. Б. ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1561 Саул И. Гасс Линейное программирование (методы и приложения). Редактор Μ. Μ. Горячая Техн. редактор Л. Ю Плакше. Корректор С. Н. Емельянова. Сдано в набор 6/1II 1961 г. Подписано к печати 20/VI 1961 г. Бумага 84X108732. Физ. печ. л. 9,5. Условн. печ. л. 15,58. Уч. -изд. л. 14,40. Тираж 25 150 экз. Цена книги 87 коп. Заказ № 1927. Государственное издательство физико-математической литературы. Москва, В-71, Ленинский проспект, 15. Ленинградский Совет народного хозяйства. Управление полиграфической промышленности. Типография № 1 «Печатный Двор» имени А. М. Горького. Ленинград, Гатчинская, 26. ОГЛАВЛЕНИЕ Предисловие редактора 7 Предисловие автора к американскому изданию 11 часть ι ВВЕДЕНИЕ Глава 1. Введение 17 § 1. Задачи линейного программирования 17 § 2. Примеры задач линейного программирования 21 Глава 2. Математические основы 28 § 1. Матрицы и определители 28 § 2. Векторы и векторные пространства 33 § 3. Выпуклые множества 37 § 4. Линейные неравенства 41 § 5. Решение систем линейных уравнений 47 часть н МЕТОДЫ (ТЕОРЕТИЧЕСКИЙ И ВЫЧИСЛИТЕЛЬНЫЙ АСПЕКТЫ) Глава 3. Общая задача линейного программирования . . 55 § 1. Задачи линейного программирования 55 § 2. Свойства решений задачи линейного программирования 56 § 3. Построение опорных планов 65 Глава 4. Симплексный метод 73 § 1. Отыскание оптимального плана 73 § 2. Алгоритм симплексного метода 78 § 3. Метод искусственного базиса 89 § 4. Геометрическая интерпретация симплексного метода 96 Глава 5. Проблема двойственности в линейном программировании 103 § 1. Несимметричные двойственные задачи 103 § 2. Симметричные двойственные задачи Ш β ОГЛАВЛЕНИЕ Глава 6. Модифицированный симплексный метод 119 § 1. Использование обычной формы обратной матрицы . . 119 § 2. Использование мультипликативного представления обратной матрицы 136 Глава 7. Вырожденные задачи 141 § 1. Способы устранения зацикливания 142 § 2. Примеры зацикливания 146 Глава 8. Параметрическое линейное программирование 152 § 1. Линейная форма с коэффициентами, зависящими от параметра 152 § 2. Параметрическая двойственная задача 160 Глава 9. Дополнительные вычислительные приемы. ... 165 § 1. Определение исходного плана 167 § 2. Двойственный симплексный метод 173 § 3. Применение вычислительных машин для решения задач линейного программирования 179 ЧАСТЬ III ПРИЛОЖЕНИЯ Глава 10. Транспортная задача 184 § 1. Общая транспортная задача . . . 184 § 2. Метод решения транспортной задачи 196 § 3. Видоизменения транспортной задачи 207 Глава 11. Общие приложения линейного программирования 214 § 1.