BRUCE A. MURTAGH Senior Lecturer in Operations Research University of New South Wales Australia Advanced Linear Programming: Computation and Practice McGRAW-HILL INTERNATIONAL BOOK COMPANY New York St Louis San Francisco Auckland Bogota Guatemala Hamburg Johannesburg Lisbon London Madrid Mexico Montreal New Delhi Panama Paris San Juan SSo Paulo Singapore Sydney Tokyo Toronto 1981 Б. МУРТАФ СОВРЕМЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ТЕОРИЯ И ПРАКТИКА Перевод с английского Н, К. Буровой под редакцией А.-И. А, Станевичюса Москва «Мир» 1984 ББК 22.18 МЭТ УДК 512.25+681.3 ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА М91 ББК 22.18 517.8 Муртаф Б. Современное линейное программирование: Пер. с англ.— М.: Мир, 1984.—224 с., ил. В книге известного австралийского специалиста обобщены и систематизированы последние достижения вычислительной практики линейного программирования. Изложение ведется на базе пакетов программ, которые могут быть использованы на машинах серии ЕС ЭВМ. Для математнков-прикладников, инженеров, экономистов, аспирантов и студен- тов институтов. ч. 1 1502000000-139, м 041(01)-84 "-"" Редакция литературы по математическим наукам Брюс Муртаф СОВРЕМЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Научн. ред. Л. Н. Бабынина Мл. научи, ред. Р. И. Пяткина Художник Н. Я. Вовк Художественный редактор В. И. Шаповалов Технический редактор Л. П. Ермакова Корректор С. А. Денисова ИБ № 3795 Сдано в набор 24.08.83. Подписано к печати 03.01.84, формат 60 X 90'/i«. Бумага типографская № 2. Гарнитура литературная. Печать высокая. Объем 7,00 бум. л. Усл. печ. л. 14. Усл. кр.-отт. 14,26. Уч.-изд. л. 15,97. Изд. № 1/2739. Тираж 26000 экз. Заказ № 94. Цена 1 р. 20 к. ИЗДАТЕЛЬСТВО <МИР» 129820, Москва, И-110, ГСП, 1-й Рижский пер., 2 l^PaCHUl-u ooariv-....-.,,--- - . Союзполиграфпрома при Государственном комигеи- и^^.- - издательств, полиграфии и книжной торговли. Москва, М-54, Валовая, 28 Отпечатано в Ленинградской типографии № 2 головном предприятии ордена Трудового Красного Знамени Ленинградского объединения техническая книга» им. Евгении Соколовой Союзполиграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли, 198052, г. Ленинград, Л-52, Измайловский про- спект, 29 с матриц ордена Октябрьской Революции и ордена Трудового Красного Знамени Первой Образцовой типографии имени А. А. Жданова Союзполиграфпрома при Государственном комитете СССР по делам "алатяльств. полиграфии и книжной торговли. Москва, М-54, Валовая, 28 © 1981 McGraw-Hill Inc. I © Перевод на русский язык, «Мир», 1984 Методы линейного программирования, как известно, нашли ши- рокое применение в задачах, возникающих в экономике, технике и других областях человеческой деятельности. Для решения практи- ческих задач линейного программирования на ЭВМ разработан це- лый ряд стандартных пакетов программ. Основу большинства таких пакетов составляет симплекс-метод, предложенный Дж. Данцигом более 30 лет тому назад. С тех пор создано множество весьма изощ- ренных алгоритмов метода. Основные усилия были направлены на сокращение времени решения, на повышение вычислительной устой- чивости и на разработку алгоритмов, позволяющих решать задачи больших размеров. Исследования по совершенствованию алгоритмов симплекс-ме- тода и созданию других методов линейного программирования про- должают интенсивно развиваться, однако результаты этих иссле- дований можно найти лишь в журнальных статьях или в материалах симпозиумов. Публикуемая книга Б. Муртафа достаточно' полно отражает современное состояние методов и алгоритмов, реализованных в основном в коммерческих пакетах линейного программирования; этому посвящена первая часть книги. В этой части систематизированы результаты многих авторов, свя- занные с методами представления обратной базисной матрицы в симплекс-методе. Способам построения и пересчета множителей, представляющих обратную базисную матрицу, обладающим раз- личными вычислительными преимуществами, уделяется большое внимание. Специальная глава посвящена основанным на симплекс- методе методам оптимизации для задач нелинейного и частично-це- лочисленного программирования. Следует отметить, что материал, касающийся расширений симплекс-метода, теории двойственности, чувствительности и устойчивости решений, достаточно полно осве- щен в литературе, опубликованной у нас в стране. Вторая часть книги посвящена вопросам формулирования и ре- шения практических задач при использовании стандартных пакетов программ. Эта часть представляет наибольший интерес для тех, кто приступает к анализу задач линейного программирования больших размеров с помощью ЭВМ. Здесь детально описывается процесс по- строения матрицы ограничений задачи, а также структура входных и выходных данных, единая для большинства коммерческих паке- тов. Весь процесс анализа задачи, начиная с формулирования и под- 6 Предисловие редактора перевода готовки исходных данных и кончая интерпретацией результатов ре- шения, иллюстрируется на примере задачи планирования производ- ства и распределения капиталовложений в нефтепереработке. Спо- соб формулирования и организация процесса решения этой специ- альной задачи являются достаточно общими и могут быть с успехом применены к другим задачам. В связи с тем, что большая часть библиографии к книге Б. Мур- тафа труднодоступна советскому читателю, а многие вопросы тео- рии и методов линейного программирования отражены в моногра- фиях, изданных у нас в стране, редактор и автор перевода сочли це- лесообразным привести дополнительную библиографию на русском языке. Приведенный список, однако, не претендует на полноту. Можно надеяться, что предлагаемая книга будет полезна спе- циалистам по прикладной математике и исследованию операций, инженерам и экономистам различных специальностей. А.-И. А. Станевичюо Посвящается Ким, Эндрю и Лсшзе ПРЕДИСЛОВИЕ Существует много учебников по линейному программированию (ЛП), в которых превосходно излагается математическая сторона предмета и соответствующие технические приемы. Однако этих . све- дений недостаточно для тех, кто приступает к решению практических задач с использованием коммерчески доступных пакетов ЛП. С дру- гой стороны, руководства для пользователей, которыми сопровож- даются коммерческие пакеты, являются прекрасными справочными. руководствами, но обычно не пригодны в качестве учебных пособий. Одна из целей настоящей книги — попытаться заполнить этот про- бел между теорией и практикой. Другая цель — описать достижения, полученные в вычислитель- ной практике ЛП за последние тридцать лет, т. е. со времени соз- дания Дж. Б. Данцигом симплекс-метода. Из библиографии видно, что большая часть этих материалов опубликована в технических журналах и трудах .конференций. ... . Чтобы ограничить размеры книги до разумных пределов, приш-. лось от многого отказаться. Например, я уклонился от слишком длинных обсуждений проблемы двойственности и двойственного симплекс-метода. Вообще, я сконцентрировал свое внимание на тех аспектах, которые относятся к основной части существующей вычис- лительной практики, так как именно они дали импульс многим пос- ледним исследованиям в этой области. Так, чтобы дать адекватное описание разработки модели, го- раздо полезнее глубоко и всесторонне рассмотреть один пример, чем коротко коснуться нескольких. В качестве такого примера я вы- брал задачу планирования производства и распределения капита- ловложений в нефтеперерабатывающей промышленности не только потому, что это одно из основных приложений ЛП, но и потому, что на этом примере удобно проследить развитие ряда идей в модели- ровании. Точно также в качестве языка генератора матриц я вы- брал язык GAMMA, хотя основные идеи и наш подход в равной сте- пени реализуются и на других доступных языках. При изложении материала я пытался сделать его удобо- читаемым, оставаясь, однако, в рамках достаточной строгости. Кни- га предназначена для тех, кто связан с разработкой и анализом мо- делей больших размеров в промышленности, торговле и управле- нии. Она рассчитана на научных сотрудников и инженеров, а также на студентов и аспирантов, которые прослушали курс линейной ал- гебры и вычислительной математики. Так как это относится к боль- 8 Предисловие шей части студентов многих специальностей, а область приложе- ний ЛП очень широка, то можно надеяться, что эта книга будет по- лезна многим читателям. Материал книги возник в результате обработки курсов лекций, читавшихся в течение ряда лет в университетах и для работников промышленности. Используемые источники, на которые я по воз- можности часто ссылался в книге, приведены в библиографии. Невозможно перечислить всех коллег, которым я обязан появле- нием этой книги; тем не менее мне хотелось бы отметить профессора Р. В. Г. Сарджента (Империал колледж), познакомившего меня с ма- тематическим программированием, Норма Хелмика (корпорация Флуор), приобщившего меня к искусству моделирования процессов, Майка Сондерса (Станфордский университет), который не только приятно и плодотворно сотрудничал со мной на протяжении многих лет, но и тщательно прочитал рукопись этой книги. Мне хотелось бы также выразить искреннюю признательность Крис Пейдж (Мак- Гиллский университет), чье детальное изучение материала, а также многочисленные замечания и предложения привели к существен- ному улучшению текста. Все ошибки, появившиеся после этого,— исключительно мои собственные. Я хотел бы поблагодарить Летицию Гордон-Виккинс за выдерж- ку и аккуратность при перепечатке рукописи и, наконец, мою семью, которой я посвящаю эту книгу, за терпение в течение долгого вре- мени ее написания. Б. Муртаф Часть I ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ Глава 1 НЕОБХОДИМЫЕ СВЕДЕНИЯ ИЗ ЛИНЕЙНОЙ АЛГЕБРЫ В этой главе мы коротко изложим ряд основных понятий и мето- дов линейной алгебры, которые будут использованы в последующих главах. Мы не намерены давать исчерпывающий обзор данного пред- мета, поскольку существуют прекрасные специальные учебники, освещающие его с большой глубиной. Ряд таких работ приведен в библиографии ([9], [12], [51], [52]). Матрица ij-и элемент /-то столбца Пример 1.1. Определение матрицы — это прямоугольная таблица действительных чисел. матрицы А, ац, находится на пересечении 1-тл строки и Г"п в12 Oi3 "14 А= flai "22 "23* "24 L"31 "82 "33 "34. (1.1) Матрица столбцов. У Матрица а.ц матрицы Пример размера (m X п} (или m X п-матрица) имеет m строк и п квадратной матрицы т==п. 4S 74 Э6]--^? П. L5 7 9J ^g 9J AT" называется транспонированной к А, если элемент А равен элементу ад матрицы А7 для всех i и /. Если Матрица А называется симметрической, если А=АТ. 1.2. Определение вектора Пусть xi, Хг, . . ., л:„ — какие-то п действительных чисел, а х — упорядоченное множество этих чисел, т. е. х= (1.2) 218 Приложение А списка таблиц (TABL). Как и в GAMMA, конструкция (ROWN/ ROWNAME) осуществляет выборку списка (ROWN) во время ин- дексирования списка (ROWNAME) (ср. с примером из разд. 8.4). Секция ROWS MPS-файла создается из информации, содержа- щейся в таблице ROW (см. табл. А.4). Команда COPY копирует последующий текст непосредственно в MPS-файл, например NAME, ROWS, COLUMNS. Секция COLUMNS формируется так же, как и в GAMMA, т. е. с использованием списков для данных таблиц, строк и столбцов. Отметим, что порядок выборки следующий (таблица, столбец, стро- ка). PDS/MAGEN подавляет генерирование части строчки, когда содержимое элемента ссылочной таблицы пусто, если нет других указаний. Вектор ограничений RHS генерируется как вектор-столбец с именем LIMTMAX из данных таблицы LIMT, столбца МАХ, строк (списка) (ROWNAME). В PDS/MAGEN есть также возможности для составления отче- тов, аналогичные возможностям языка GAMMA, и мы можем исполь- зовать команды, подобные тем, которые приведены в табл. 10.4, для генерирования отчета в виде, представленном в табл. 10.5. БИБЛИОГРАФИЯ 1. APEX III (1977) User manual, Control Data Corporation, Minneapolis. 2'. Bartels R. H., Golub G. H. (1969), The Simplex method of linear programming using LU decomposition, Communication of ACM, 12: 266—268. 3. Beal E. M. L. (1967), Numerical methods, in J. Abadie (ed.), Nonlinear Program- ming, North-Holland, Amsterdam, pp. 132—205. 4. Beal E. M. L. (1968), Mathematical Programming in Practice, Pitmans, London. 5. Beal E. M. L. (1970), Advanced algorithmic features for general mathematical programming systems, inJ. Abadie (ed.), Integer and Nonlinear-Programming, North-Holland, Amsterdam, pp. 119—137. 6. Beal E. M. L. (1971), Sparseness in linear programming, in J.K. Reid (ed.), Large Sparse Sets of Linear Equations, Academic Press, London, -pp. 1—16. 7. Beal E.M. L. (1976), Optimization techniques based on linear programming, in L. C. W. Dixon (ed.), Optimization in Action, Academic Press, London, pp. 447—466. 8. Bea! E. M. L., Tomlin J. A. (1970), Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables, in J. Lawrence (ed.), Proceedings of the Fifth International Conference on Ope- rational Research, Tavistock, London, pp. 447—454. 9. Bodewig E. (1959), Matrix Calculus, North-Holland, Amsterdam. 10. Brearley A. L., Mitra G., Williams H. P. (1975), Analysis of mathematical programming problems prior to applying the simplex method, Mathematical Programming, 8: 54—83. 11. Buzby В. R. (1974), Techniques and experience solving really big nonlinear programmes, in R. Cottle and J. Krarup (eds.), Optimization Methods for Resource Allocation, English Universities Press, London, pp. 229—236. 12. Dahlquist G., Bjork A. (1974), Numerical Methods, Prentice-Hall, New Jersey. 13. DantzigG. B. (1963), Linear Programming and Extensions, Princeton Universi- ty Press, New Jersey. (Имеется перевод: Данциг Дж. Линейное программиро- вание, его обобщение и применение.— M.: Прогресс, 1966.) 14. Dantzig G. В., Harvey R. P., McKnight R. D., Smith S. T. (1969), Sparse matrix techniques in two mathematical programming codes, in R. A. Willou- ghby (ed.), Sparse. Matrix Proceedings, Report RA1, IBM Corporation, New York. 15. Dantzig G. В., Van Slyke R. M. (1967), Generalized upper bounding techniques, Journal of Computer and System Science, 1: 213—216. 16. Dantzig G. В., WolfeP. (1960), Decomposition principle for linear programmes, Operations Research, 8: 101—110. 17. de Buchet J. (1971). How to take into account the low density of matrices to design a mathematical programming package, in J. K. Reid (ed.), Large Sparse Sets of Linear Equations, Academic Press, London, pp. 211—218. 18. Driebeek N. J. (1966), An algorithm for t-he solution of mixed-integer program- ming problems, Management Science, 12: 576—587. 19. Duff I. S. (1976), A survey of sparse matrix research, AERE Report G.S.S. 28, Harwell, England. 20. Fieldhouse M. (1974), Checking large scale LP model, in R. Cottle and J. Krarup (eds), Optimization Methods for Resource Allocation, English Universities Press, London, pp. 165—175. 21. Forrest J. J. H., Tomlin J. A. (1972), Updating triangular factors of the basis to maintain sparsity in the product-form simplex method, Mathematical Program- ming, 2: 263—278, 220 Библиография 22. Forrest J. J. H., Hirst J. P. H., Tomlin J. A. (1974), Practical solution of large and complex integer programming problems with UMPIRE, Management Science, 20: 736—773. 23. Gal Т. (1979), Postoptimal Analyses, Parametric Programming and Related Topics, McGraw-Hill, New York. 24. Garfinkel R.S., Nemhauser G. L. (1972), Integer Programming, Wiley, New York. 25. Gill P. E., Golub G. H., Murray W., Saunders M. A. (1974), Methods for modifying matrix factorizations, Mathematics of Computation, 28: 505—535. 26. Gill P. E., Murray W. (1973), A numerically stable form of the simplex algorithm, J. Linear Algebra Applies., 7: 99—138. 27. Gill P. E., Murray W., Saunders M. A. (1975), Methods for computing and modifying the LDV factors of a matrix, Mathematics of Computation, 29: 1051— 1077. 28. Goldfarb D., Reid J. K. (1977), A practicable steepest-edge simplex algorithm, Mathematical Programming, 12: 361—371. .29. Griffith R. E., Stewart R. A. (1961), A nonlinear programming technique for the optimization continuous processing systems, Management Science, 7: 379— 392. ..30. Hamming R. W. (1971), Introduction to Applied Numerical Analysis, McGraw- Hill, New York. 31. Harris P. M. J. (1973), Pivot selection methods of the Devex LP code, Mathema- tical Programming, 5: 1—28. 32. Hellerman E., Rarick D. С. (1971), Reinversion with the preassigned pivot procedure. Mathematical Programming, 1: 195—216. 33. Hellerman E., Rarick D. C. (1972), The partitioned preassigned pivot procedu- re, in D. J. Rose and R. A. Willoughby (eds.), Sparse Matrices and their Appli- cations, Plenum Press, New York, pp. 68—76. 34. Kalari J. E. (1971), Aspects of large-scale in-core linear programming. Pro- ceedings of ACM Conference, Chicago, 304—313. 35. Markowitz H. M. (1957), The elimination form of the inverse and its applications to linear programming. Management Science, 3: 255—269. 36. Miller С. E. (1963), The simplex method for local separable programming, in R. L. Graves and P. Wolfe (eds.), Recent Advances in Mathematical Program- ming, McGraw-Hill, New York, pp. 89—100. .37. Murtagh В. A., Saunders M. A. (1978), Large scale linearly constrained optimi- zation, Mathematical Programming, 14: 41—72. .38. Murtagh В. A., Saunders M. A. (1980), The implementation of a Lagrangian- based algorithm for spase nonlinear constrains, Systems Optimization Labora- tory Report SOL 80—1, Stanford University, California. .39. Orchard-Hays W. (1974), On the proper use of a powerful MPS, in R. Cottle and J. Kraup (eds.). Optimization Methods for Resource Allocation, English Univer- sities Press, London, 229—236. •40. Rarick D. C. (1975), An improved pivot row selection procedure, implemented in the mathematical programming sistem MPS III, Management Science Systems, Rockville, Maryland. •41. Robinson S. M. (1972), A quadratically convergent algorithm for general prog- ramming problems, Mathematical Programming, 3: 145—156. 42. Salkin G., Kornbluth J. (1973), Linear Programming in Financial Planning, Accountancy Age, London. 43. Sargent R. W. H., Murtagh B. A. (1973), Projection methods for nonlinear programming. Mathematical Programming, 4: 245—268. 44. Saunders M. A. (1972), Large-scale linear programming using the Cholesky factorization. Report STAN-CS-72-252, Stanford University, California. 45. Saunders M. A. (1976), A fast', stable implementation of the simplex method using Bartels—Golub updating, in J.R. Bunch and D.J. Rose (eds.), Sparse Matrix Computations, Academic Press, New York and London, pp. 213—226. 46. Sherman J„ Morrison W. J, (1949J, Adjustment of an inverse matrix correspon- Библиография 221 ding to changes in the elements of a given column or a given row of the original matrix, Ann. Math. Stat., 20: 621. 47. Simonnard M. (1966), Linear Programming, translated by W. S. Jewell, Prenti- ce-Hall, New Jersey. 48. Smith B. R., Lucas P. D., Murtagh B. A. (1967a), The development of a New Zealand energy model, N. Z. Operational Research, 4: 101—117. 49. Smith В. R., Lucas P. D., Murtagh B. A. (1976b), Some aspects of modelling New Zealand's electricity sector, N. Z. Energy Journal, 49: 100—103. 50. Stephenson G G (1970), A hierarchy of models for planning in a division of ICI, Operational Research Quarterly, 21(2): 221—245. 51. Stewart G. W. (1973), Introduction to Matrix Computations, Academic Press, New York. 52. Strang G. (1976), Linear Algebra and Its Applications, Academic Press, New York. 53. Tomlin J. A. (1970), Branch and bound methods for integer and non-convex programming, in J. Abadie (ed.), Integer and Nonlinear Programming, North- Holland, Amsterdam, pp. 437—450. 54. Williams H. P. (1978), Model Building in Mathematical Programming, Wiley, Chichester. 55. Wolfe P. (1969), Trends in linear programming computation, in R. A. Willough- by (ed.). Sparse Matrix Proceedings, Report RA1, IBM Corporation, New York. Дополнение к библиографии 1. Ашманов С. А. Линейное программирование.—M.: Наука, 1981. 2. Булавский В. А., Звягина Р. А., Яковлева M. А. Численные методы ли- нейного программирования.— M.: Наука, 1977. 3. Габасов Р., Кириллова Ф. M. Методы линейного программирования, ч. I. Общие задачи.— Минск: Издательство БГУ, 1977. 4. Гасс С. Линейное программирование.—M.: Физматгиз, 1961. 5. Гейл Д. Теория линейных экономических моделей.— M.: ИЛ, 1963. 6. Гольштейн E. Г., Юдин Д. Б. Новые направления в линейном программи- ровании.— M.: Советское радио, 1966. 7. Гольштейн E. Г., Юдин Д. Б. Линейное программирование (теория, методы и приложения).—M.: Наука, 1969. 8. Гольштейн E. Г., Юдин Д. Б. Задача линейного программирования транс- портного типа.— M.: Наука, 1969. 9. Еремин И. И., Астафьев H. H. Введение в теорию линейного и выпукло- го программирования.— M.: Наука, 1976. 10. Карманов В. Г. Математическое программирование.—M.; Наука, 1980. 11. Курош А. Г. Курс высшей алгебры.—M.: Наука, 1971. 12. Лэсдон Л. С. Оптимизация больших систем.— M.: Наука, 1975, 13. Малков У. X. Обзор путей повышения эффективности мультипликативного алгоритма симплекс-метода.— В кн.: Математические методы решения эко- номических задач. M.: Наука, 1977, вып. 7, с. 30—51. 14. Моисеев H. H. (ред.) Современное состояние теории исследования операций.— M.: Наука, 1979. 15. Романовский И. В. Алгоритмы решения экстремальных задач.— M.: Наука, 1977. 16. Тьюарсон Р. Разреженные матрицы.— M.: Мир, 1977, ОГЛАВЛЕНИЕ Предисловие редактора перевода ....... Предисловие ........ ЧАСТЬ I. ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ............ 9 ГЛАВА 1. НЕОБХОДИМЫЕ СВЕДЕНИЯ ИЗ ЛИНЕЙНОЙ АЛГЕБРЫ 1.1. Определение матрицы .. ..... 9 1.2. Определение вектора . . ••••••••••••••• 1.3. Арифметические операции над матрицами и векторами ; ' ' Ю I.J.I. Сложение ......... ,п 1.3.2. Умножение матриц . . . '•••••••••••• 1'3'3' ^""^"ие на скаляр •••••••••••••• 1.4. Единичная матрица ...... ' ' ••••••• и 1.5. Обращение матрицы . . ^ ••••••••••••••• 1^ 1.6. Линейно независимые векторы •••••••••••••• 1 1.7. Неособенные матрицы . . •••••••..... i^ 1.8. Матричное представление линейных у равнении •••••• ,. 1.9. Блочные матрицы .... ..... it 1.10. Элементарные преобразования'.'.' •••••••••••• .1. Матричное-тождество Шермана - Моррисона :;"'''' и IIQ •''^"'«'""ые и плотные матрицы • . • . i 1.13. Решение линейных уравнений •••••••••... 1.13.1. Исключение . . .....'.'.''. '. ''•••• 10 1.13.2. Обратная подстановка . '. '"••'••••••• 1.13.3. Перестановка строк . . . •••••••••••• 1.13.4. LU-разложение . . ......."'..'..''''' w ГЛАВА 2. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД ...... 25. 2.1. Формулировка задачи ....... 95. 2.2. Допустимое базисное решение . ....'.''' w 2.3. Преобразованная задача . . ^ ••••••••••••• о 2.4. Условия оптимальности . . . '. ••••••••••••• ^' 2.5. Элементарные преобразования' базиса' •••••••••• 2.6. Шаги модифицированного симплекс-метода '..'''"'' 32 ^•t. Начальное допустимое решение . .........'''"' 34 ГЛАВА 3. МЕТОДЫ РАЗРЕЖЕННЫХ МАТРИЦ .......... 38 3.1. Введение ..... „о 3.2. Хранение. . ....'.'.'.'.'''''''''''••• "8 3.3. Ошибки округления . . . '. '. . . •••••••••••• °9 3.3.1. Определение . . . . ', '. ...'"'''' л\ 3.3.2. Масштабирование . . ......''' л\ 3.3.3. Контроль роста ошибок ''••••••••••• 3.3.4. Допуски на ошибку . ••.•••..... ^ ^"""ликативная и факторизованная формы обратной'мат^ 3.4.1. Мультипликативная форма .' .......... 43 у. Оглавление 223 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 ГЛАВА 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. Вырожденность . . ................... 81 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. Краткое изложение метода ............. 117 6.3.2. Распространение метода на нелинейные ограничения . 120 6.4. Целочисленное программирование . . ........... 122 6.4.1. Метод ветвей и границ .............. 122 6.4.2. Формулирование задач целочисленного программирова- чия . . .'........................ 127 ^.З, Специально упорядоченные множества ..,.,,,. 129 224 Оглавление ЧАСТЬ II. ВЫЧИСЛИТЕЛЬНАЯ ПРАКТИКА ............ 131 ГЛАВА 7. ФОРМУЛИРОВАНИЕ ЗАДАЧИ . . ........... 13! 7.1. Введение . . ...................... 131 7.2. Определение границ: широта охвата и детализация ..... 131 7.3. Использование блок-схем .... ............ 138 7.4. Описательные ограничения . . .............. 140 7.5. Ограничения на ресурсы и конечное потребление ...... 143 7.6. Условия, налагаемые извне . . .............. 146 7.7. Определение целевой функции . ............. 147 ГЛАВА 8. ПОСТРОЕНИЕ МАТРИЦЫ БОЛЬШОГО РАЗМЕРА .... 156 8.1. Введение . . ......'................ 156 8.2. Составление таблиц данных . . .............. 156 8.3. Обработка списков и таблиц ............... 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. Свободные строки. Интервальные строки ...... 177 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 9.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