Читать онлайн «Численные методы линейного программирования, специальные задачи»

Экономикса МАТЕМАТИЧЕСКАЯ БИБЛИОТЕКА В. А. БУЛАВСКИЙ, Р. А. ЗВЯГИНА, М. А. ЯКОВЛЕВА ЧИСЛЕННЫЕ МЕТОДЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (СПЕЦИАЛЬНЫЕ ЗАДАЧИ) _Под редакцией Л. В. КАНТОРОВИЧА щ ИЗДАТЕЛЬСТВО сНАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 518 Б 90 УДК 519. 95 Численные методы линейного программирования. В. А. Б у- лавский, Р. А. Звягина, М. А. Яковлева. Под редакцией Л. В. Канторовича. Главная редакция физико-математической литературы изд-ва «Наука», М. , 1977. Книга посвящена численным методам решения задач линейного программирования. Основное внимание уделяется задачам, дополнительная специфика которых позволяет разработать более сложный в логическом плане, но менее трудоемкий метод решения. Сюда относятся двухкомпонентные задачи линейного программирования (в частности, транспортная задача), задачи с окаймлением и задачи с разветвленной блочной структурой. Для этих задач излагаются методы, являющиеся конкретизацией одного общего метода последовательного улучшения, что позволило сделать их изложение в достаточной степени единообразным. В этом отношении книгу можно рассматривать как пакет методов, органически друг с другом связанных и друг на друга опирающихся. Книга рассчитана на математиков, вычислителей-программистов, инженеров, работающих в области математического обеспечения ЭВМ, а также экономистов, имеющих достаточный опыт чтения математической литературы. В монографии 32 рис. , 119 библиографических назв. 20204—102 _ __ © Главная редакция псо/лоч 77 Ь1-77, физико-математической литературы \J0o\\jZ)-U издательства сНаука», 1977 ОГЛАВЛЕНИЕ Предисловие 7 Предисловие редактора 10 Введение , 11 § 1. Постановка задачи линейного программирования # # 11 § 2. Двойственные задачи 15 § 3. Экономическая интерпретация ... ... ... ... . 20 § 4. Принятые обозначения ... ... ... ... ... . . 26 Глава 1. Основы линейного программирования ... ... . . 30 § 1. Строение допустимого множества и соотношения двойственности 30 1. 1. Основные определения (30). 1. 2. Строение многогранного множества (32). 1. 3. Решение задачи линейного программирования в параметрической форме (38). 1. 4. Теорема Минковского — Фар каша (40). 1. 5. Соотношения двойственности (43). § 2. Общая схема метода последовательного улучшения 44 2. 1. Основные предположения и определения (44). 2. 2. Описание одного шага метода (47). 2. 3. Применение к задаче на максимум (51). 2. 4. Обоснование метода (53). 2. 5. Нахождение исходной базисной пары (55). § 3. Варианты метода последовательного улучшения ... / 59 3. 1. Предварительные замечания (59). 3. 2. Прямой метод (59). 3. 3. Двойственный метод (62). 3. 4. Учет ограничений сверху на неизвестные (64). 3. 5. Учет ограничений сверху на неизвестные (прямой метод) (67). 3. 6. Учет ограничений сверху на неизвестные (двойственный метод) (68). 3. 7. Начало счета в двойственном методе (70). § 4. Ситуация вырождения 71 4. 1. Предварительные замечания (71). 4. 2. Лексикографическое упорядочение (74). 4. 3. Борьба с зацикливанием (76). § 5. Дополнительные вопросы . . . 81 5. 1.