22.18 А 98 УДК 519.6 Линейное программирование. А ш м а н о в С. А.— М.: Наука. Главная редакция физико-математической литературы, 1981.— 340 с. В книге излагаются основные разделы теории и численные ме- тоды решения задач линейного программирования. Значительное место уделяется качественному исследованию свойств содержатель- ных моделей методами линейного программирования. Основной материал сопровождается упражнениями теоретического характера. Табл. 19. Илл. 35. Библ. 28 назв. Станислав Александрович Аш-чипов • ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Редакторы А. Д. Вай-чштейн, Е. Ю. Хован, Техн. редактор С. Я. Шкляр. Корректоры О. Н. Бутусова, О. М. Кривенко. ИБ № 11858 Сдано в набор 31.12.80. Подписано к печати 12.06.81. Формат 84Х108'/э2. Бу- мага тип. №' 3. Обыкновенная гарнитура. Высокая печать. Условн. печ. л. 15,96. Уч.-изд. л. 16,5. Тираж 44 000 экз. Заказ М 410. Цена 70 коп. Издательство «Наука» Главная редакция физико-математической литературы 117071, Москва, В-71, Ленинский проспект, 15 4-я типография изд-ва «Наука». 630077, Новосибирск, 77, Станиславского, 25. А 20204. 053(02)-81 1-81.1502000000. Издательство «Наука». Главная редакция физико-математической литературы, 1981 ОГЛАВЛЕНИЕ Предисловие .............. 5 Глава I. Линейные модели . ........ 9 § 1. Линейное программирование — инструмент исследо- вания линейных моделей ........ 9 § 2. Примеры линейных моделей ....... 10 § 3. Различные формы задач линейного программирова- ния и их эквивалентность ........ 28 § 4. Проблема отыскания численного решения задачи линейного программирования ....... 35 Глава II. Выпуклые многогранники и линейные неравейства 38 § 1. Геометрическая интерпретация задач линейного про- • граммирования ........... 38 § 2. Выпуклые множества и теоремы о разделяющей ги- перплоскости ............ 41 § 3. Многогранные выпуклые множества ..... 52 § 4. Структура допустимых множеств задач линейного программирования .......... 63 § 5. Эквивалентность двух определений выпуклого много- гранного множества .......... 74 § 6. Линейные неравенства ......... 78 Упражнения.............. 81 Глава III. Теория двойственности ....... 83 § 1. Двойственная задача линейного программирования 83 § 2. Теорема двойственности ......... 87 § 3. Короткое доказательство теоремы двойственности 95 § 4. Строение множества решений задачи линейного про- граммирования ........... 97 § 5. Интерпретация двойственных оценок и дифференци- альные свойства функции значений , . . . , 100 Упражнения.............. 113 Глава IV. Применения теории двойственности .... 116 § 1. Основная теорема о матричных играх ..... 116 § 2. О проблеме существования ядра в кооперативной иг- ре п лиц ............. 126 § 3. Свойства неотрицательных матриц ..... 136 § 4. Эффект замещения в обобщенной подели Леоптьева 141 § 5. Теорема о магистрали для динамической модели планирования ........... 146 § 6. Принцип максимума для дискретных линейных за- дач оптимального управления ....... 152 Упражнения. .....,.,.,.., 157 Глава V. Теория симплекс-метода . . . . . . . 158 § 1. Метод исключения Жордана — Гаусса для систем ли- нейных уравнений ......... i 158 § 2. Опорные планы . . . . . . . . . . 161 § 3. Симплекс-метод для невырожденной задачи линей- ного программирования ....... 167 § 4. Вырожденные задачи линейного программирования 178 § 5. Нахождение начального опорного плана .... 181 § 6. Иллюстративный пример численного решения задачи линейного программирования . ..... 186 § 7. Модифицированный симплекс-метод ..... 191 Упражнения. ............. 193 Глава VI. Двойственный симплекс-метод , . . . • 195 § 1. Псевдоплапы и правила двойственного симплекс-ме- , тода .............. 195 § 2. Применение двойственного симплекс-метода к задаче с дополнительным ограничением ...... 201 § 3. Симплексная таблица в координатной форме . . . 203 § 4. Двойственный симплекс-метод в координатной форме 207 § 5. Нахождение начального псевдоплана .... 209 § 6. Лексикографическая задача линейного проограмми- ровапия ............. 212 Глава VII. Специальные задачи линейного программиро- вания ............ 217 § 1. Транспортная задача и транспортные сети . . 217 § 2. Нахождение начального опорного плана транспорт ной задачи методом северо-западного угла . . 222 § 3. Опорные планы транспортной задачи и вырожден ность ... ... ...... 226 § 4. Метод потенциалов решения транспортной задачи 231 § 5. Целочисленные задачи линейного программирования 239 § 6. Метод отсечения для целочисленных задач линейного программирования .... . . 245 § 7. Первый алгоритм Гомори для целочисленных задач линейного программирования ....... .248 § 8. Блочное программирование ....... 264 Глава VIII. Метод регуляризации неустойчивых задач ли- нейного программирования . . . 271 § 1. Понятие устойчивости задач линейного программи- рования ..... . . . . 271 § 2. Параметрические системы линейных неравенств . 273 § 3. Необходимые и достаточные условия устойчивости задач линейного программирования ..... 278 § 4. Регуляризация неустойчивых задач . . . .284 Добавление О ноном методе решения задач линейного программирования . .......... 287 Разбор упражнений ............ 291 Литература ..'...•.......... 301 Предметный указатель ........... 303 ПРЕДИСЛОВИЕ Данная книга представляет собой учебное пособие по линейному программированию, рассчитанное на студентов и аспирантов высших учебных заведений по специально- стям математика, прикладная математика, экономическая кибернетика, а также на, инженеров, пользующихся мате- матическим моделированием как средством исследования реальных процессов. Изучение свойств систем линейных неравенств ведет- ся, по-видимому, очень давно. Выделение класса экстре- мальных задач, определяемых линейным . функционалом на множестве, задаваемом линейными ограничениями, сле- дует отнести к 30-м годам нашего столетия. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман, знаменитый математик и физик, доказавший основную теорему о мат- ричных играх и изучивший экономическую модель, нося- щую его имя; советский академик, _дауреат Нобелевской премии Л. В. Канторович, сформулировавший ряд задач линейного программирования и предложивший метод их, решения, незначительно отличающийся от симплекс-ме- тода. Публикации основных его работ помешала война, и книга вышла в свет только в 1959 г. Первая постановка транспортной задачи предложена п 1930 г. советским ученым А. Н. Толстым. М. К. Гаву- рин вместе с Л. В. Канторовичем разрабатывал методы решения задач линейного программирования. В годы вои- ны пробудился интерес к задачам линейного программи- рования в США. Симплекс-метод разработан Дж. Данци- 5 гом при дальнейшем участии А. Чарнса, Л. Форда а Д. Фалкерсона. Теорема двойственности доказана Д. Гей- лом, Г. У. Куном и А. У. Танкером на основе идей Дж. фон Неймана. Накопленный опыт применения линейного программи- рования показывает, что наряду с разработкой эффектив- ных вычислительных приемов решения линейных задач все большую роль приобретают качественные методы ис- следования свойств задач линейного программирования. В связи с этим в книге уделяется несколько большее вни- мание данному вопросу, чем обычно. Книга состоит из восьми глав. Глава I носит вводный характер. В ней обсуждаются некоторые общие вопросы моделирования, рассматрива- ются примеры содержательных проблем, приводящих к задачам линейного программирования. Поначалу на при- мерах подробно описывается методика формализации содержательных задач, что позволяет читателю освоиться с переходом к векторно-матричным обозначениям. При обсуждении формализованных моделей обращается -вни- мание не только на их достоинства, но и на ограничен- ность, что должно предостеречь читателя от абсолютиза- ции математических выводов и рекомендаций. Глава II посвящена теории выпуклых многогранных множеств. По этому поводу скажем, что хотя изложений двойственности и симплекс-метода при 'желании можно провести, не опираясь на указанную теорию, все же, по нашему мнению, глубокое понимание свойств задач ли- нейного программирования невозможно без знания струк- туры многогранных множеств. Автор приложил максимум усилий, чтобы сделать материал главы доступным. Основ- ные понятия п факты иллюстрируются примерами и ри- сунками, позволяющими осознать на геометрическом наглядном материале (в основном на плоскости, реже в трехмерном пространстве) основные идеи. Предваритель- ное обсуждение каждого факта делает его интуитивно очевидным, так что в ряде случаев (их немного) читатель, 6 не привыкший к абстрактным математическим доказатель- ствам, может опустить их без ущерба для понимания существа дела. В главе III формулируется и доказывается основной результат — теоремы двойственности в линейном програм- мировании. Глава IV представляет собой раздел, в котором прово- дится качественный анализ решений некоторых из содер- жательных моделей и указываются другие сферы приме- нения теории двойственности. Так, здесь доказывается теорема о магистрали в динамической модели Леонтьева с .обсуждением содержательного смысла этого важного результата, теорема о замещении в динамической модели межотраслевого баланса. Наряду с классическим приме- ром использования теории двойственности — доказатель- ством теоремы фон Неймана о матричных играх,— приве- дены факты о свойствах множества решений в играх п лиц, причем использование теории двойственности делает все доказательства здесь особенно простыми. Отметим также доказательство теоремы Фробениуса — Перрона о свойствах неотрицательных матриц. Доказывается дис- кретный принцип максимума для линейных задач. В главе V излагается симплекс-метод численного реше- ния задач линейного программирования. Глава VI преследует цель подготовить читателя к при- менению симплекс-метода для исследования целочислен- ных задач линейного программирования. Здесь описыва- ется иной способ организации числовой информации — та*{ называемая симплексная таблица в координатной форме, На этой основе излагается метод решения лексикографи- ческих задач линейного программирования, что затем также используется при обосновании алгоритма Гомори решения целочисленных задач. Глава VII предназначена продемонстрировать, как преобразуется основная вычислительная схема симплекс- метода при решении специфических классов задач. Основ- ным примером служит классическая транспортная задача. 7 После теоретического рассмотрения несложной теории транспортных сетей показано, как симплексный вычисли- тельный алгоритм в данном случае сводится к выполне- нию ряда логических операций по поиску циклов в сети. Большой раздел посвящен целочисленным задачам линей- ного программирования с изложением содержательных моделей (задача о коммивояжере, задача о ранце и т. п.). Последняя глава VIII дает понятие о трудностях, воз- никающих в связи с возможной некорректностью задачи линейного программирования. Обсуждается вопрос о важ- ности этого момента, ввиду приближенности любой стати- стической информации к реальной задаче. Приводятся методы регуляризации подобных задач, основанные на идеях А. П. Тихонова. Весь материал сопровождается упражнениями. Автор приносит благодарность всему коллективу ка- федры исследования операций Московского государствен- ного университета, принимавшему активное участие в работе над книгой. С. А. Ашманоз ГЛАВА I. ЛИНЕЙНЫЕ МОДЕЛИ § 1. Линейное программирование — инструмент исследования линейных'моделей Линейное программирование является составной ча- стью раздела математики, который изучает методы нахож- дения условного экстремума функций многих переменных и называется математическим программированием. В клас- сическом математическом анализе рассматривается задача отыскания условного экстремума функции. Тем не ме- нее, время показало, что для многих задач, возникающих под влиянием запросов практики, классические методы недостаточны. В связи с развитием техники, ростом про- мышленного производства и с появлением электронных вычислительных машин все большую роль начали играть задачи отыскания оптимальных решений в различных сферах человеческой деятельности. Основным инструмен- том при решении этих задач стало математическое моде- лирование — формальное описание изучаемого явления и исследование с помощью математического аппарата. Остановимся на некоторых основных проблемах моде- лирования. Всякая модель реального процесса предпола- гает идеализацию и абстракцию: следует в той или иной степени упростить постановку задачи и отвлечься от ее специфики. Когда в школьном учебнике рассматривается задача о том, как поезд движется из пункта А в пункт Б, то уже такая несложная модель иллюстрирует сказанное. В самом деле, если предполагается, что поезд движется с постоянной скоростью, то это есть идеализация; подоб- ного в жизни почти не бывает. Вместе с тем, решая зада- чу, школьник абстрагируется от ее содержания: если в следующий раз ему встретится не поезд, а автомобиль, он применит тот же способ решения, не смущаясь разницей между средствами передвижения. Идеализация и абстракция не должны уходить слиш- ком далеко от содержания задачи, чтобы построенная мо- Э 6. Вектор х = 0 допустил) для данной задачи. Поскольку двой- ственная задача имеет вод min<0, p> A'p SB с, то значение d прямой задачи равно нулю, но тогда • d = 0 = - <с, 0>. 7. В данной задаче,существует единственный допустимый век- тор (1, 0, 0), который и является оптимальным. Взяв в качестве базиса этого плана систему ((Л (1) ) столбцов матрицы ограни- чений, получаем следующую симплексную таблицу:- . AI А, Д.э <с, ж) 1 О о —1 3") 1 1 о —1 X, о о 1 1 в которой Дэ < 0. , 8. Пусть направление s допустимо в точке х". Тогда 1) х° +• + Ks > 0, 2) А (х° + Ks) == Ь. Из 1) получаем Ах° + Us = и -т- 4- KAs == 6, т. е. kAs == 0, откуда As == 0. Если х°. = 0, то из усло- вий К > 0 и 2) получаем, что s, == 0. Обратное утверждение оче- видно. 9. Пусть <с, s> sS 0 для любого направления s, допустимого в точке .г". Пусть х е Х — произвольная точка. .Точка х0 + •}-К(х—х") при любом A,, O^^^l, принадлежит К в силу его выпуклости. Следовательно, направление i == х—х° допустимо в точке ж". Тогда ОХс, х — г°> «= <с, г>—<с, г°>, т. е. <с, я-0) Ss ^ <с, ;г>. Обратное утверждение состоит в том, что глобальный максимум является локальным, и поэтому тривиально.. 10. Пусть s—произвольное направление, допустимое в точке ж0, о = [f ] х^ == 0} Как следуе! аэ упр. 8, 9, имеет место импли- кация: As sS 0, —/Is sS 0, $э О, J <с, s> 5$ 0. .Теорема 2.27 утверждает, что в таком случае существует неотри- цательное решение системы уравнений Аа—Аи—w = с, где Wj = 0, если /'9$ о. Обозначив р" == и — v, получаем требуемое утверждение. Наоборот, пусть р° и w S& 0 — векторы, для которых с == A'p'1— w, (х°, w) = 0. Нетрудно убедиться, что в таком случае имеет место имплика- -цпя: As == 0, ^ 0, т. е. по любому на- правлению, допустимому в точке .с0, значение целевой функции убывает. Согласно упр. 9 ^—оптимальный план аадачи (5.2). 11. Если Д ^ 0, то этот ректор можно нринять за w в упр. 10, „„„ л ^ . -.1) - -- 0 / •">-' " , . ^ '• ' так '0. как Д=^у-е, где, р°=(л^-1с„ и <д,д°> 300 ЛИТЕРАТУРА ОСНОВНАЯ ЛИТЕРАТУРА 1. К у р о ш А. Г. Кури высшей алгебры.— М.: Наука, 1971. Основы линейной алгебры,—М.: Наука, 2. М а л ь ц е в А. И. 1970. 3.Гольштеан Е. рование, теория, методы Г., Юдин Д. Б. Линейное программи- .„.-., ---г-.-, -----„- в приложения.—М.: Наука, 1969. 4. Г о л ып т ей в Б. Г., -Юдин Д. Б. Новые направления в линейном программировании.— М.: Советское радио, 1966. 5. Голыптейа Е. Г., Юдин Д. Б. Задача линейного про-. граммирования транспортного тина.— М.: Наука, 1969. 6. Линейные неравенства и смежные вопросы. Сб. статей под редакцией Г. У. Куна и А. У. Т а к к е р а,— М.: ИЛ, 1959. 7. Данциг Д. Линейное программирование, его обобщения и применение.— М.: Прогресс, 1966. 8. Г ас с С. Линейное программирование— М.: Физматгиз, 1961. 9. Г е и л Д. Теория лин&йпых экономических моделей.— М.: ИЛ, 1963. 10. Заславский Ю. Л. Сборник задач но линейному про- граммированию,— М.: Наука, 1969. ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА 11. Stigler G. J. The cost of subsistence, Journal of Farm Economics, 1945, № 27. 12. W a n g h F. V. The minimal-cost dairy feed, Journal of Farm Economics, August, 1951. 13. А л е ксан д р о в А., Лурье А., Олейник Ю. При- менение электронных вычислительных машин в оперативном пла- ниров.ании. Автомобильный транспорт, 1959, № 6. 14. Л е о н т ь е в В. В. Исследования структуры американской экономики.— М.: Госстатиздат, 1958. 15. К о с с о в В. В. Межотраслевой баланс.— М.: Экономика, 1966. 16. Г р е б ц о в Г. П., С м е х о в В. М., С м о л я р Л. И. Ос- новы разработки межотраслевого баланса.— М.: Экоиомиздат, 1961. 17. Моделирование народнохозяйственных процессов/Под ред. В. С. Дадаяна.— М.: Экономика, 1973. 18. К а п т о р о в и ч Л. В. Экономический расчет наилучшего использования ресурсов.— М.: Изд. АН СССР, 1960. 19. Д ж. фон Пойман, О, М о р г е п ш т е р н. Теория вгр и экономическое поведение,— М,; Наука, 1970, 301 20. О у э н Г. Теория игр.— М.: Наука, 1971. 21. Бондарева О. Н. Некоторые применения методов ли- нейного программирования и теории кооперативных игр.— Про- блемы кибернетики, 1963, № 10, стр. 121—139. 22. D о г f ю а п В., S а ш и е 1 s о п Р. A., S о 1 о w R. "М. Linear programming and economic analysis.—N.-Y., McGrow Hill, 1958. 23. A p p e 1 К., Н a k е п W. Every planar map is four colo- rable.— Bull Amer. Math. Soc., 1976, 82, № 5. 24. Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование.— М.: Наука, 1969. 25. Т и х о н о в А. Н., А р с е н л н В. Я. Методы решения некорректных задач.— М.: Наука, 1979. 26. А ш м а н о в С. А. Математические модели и методы в экономике.— М.: Изд-во МГУ, 1980. 27. Х а ч и я н Л. Г. Полиномиальный алгоритм в линейном программировании.— ДАН СССР, 1979, 244, № 5, с. 1093—1096. 28. X а ч и я н Л. Г. Полиномиальные алгоритмы в линейном программировании.— ЖВМ и МФ, 1980, 20, № 1, с. 51—68. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Алгоритм Гомори .248 Базис опорного вектора 186 — — плана t64 Базисная переменная 158 Вектор внутренний для конуса 278 — допустимый 33 — инциденций каолиций 131 — конечного спроса 23, 25 — крайний 60 — направляющий для прямой 41 — опорный 196 — полных трудовых затрат 145 — ресурсов 18 — Фробениуса 141 Возможное направление 114 Выпуклая линейная комбинация 52 — оболочка 53 Гиперплоскость 44 — опорная 46 — разделяющая 41, 44, 47 Градиент 34, 109 Двойственные оценки 100 Дележ игры 128 Дуга 218 Задача блочная 284 — возмущенная 272 — двойственная 83 — — к канонической 85 — — к общей 86 — — к стандартной 84 — двойственно невырожденная 200 — допустимая 33 — каноническая 29, 161 — лексикографическая 212 — линейного программирования 28 — невырожденная 165 — общая 29, 32 — о диете 11—15 — о коммивояжере 240 — о назначениях 239 — о ранце 239 — о четырех красках 242 — стандартная 28 — транспортная 15, 217 — устойчивая 271, 272, 281—283 — — по пешеншо 272. 281 — — по функционалу 272, 281 — целочисленная 239 Значения задачи 33, 87 — игры 120 — — верхнее 120 — — нижнее 120 Игра 116 — кооперативная 126 — матричная 117 — симметричная 129 Итерация симплекс-метода 177 — — большая 255 — — малая 255 Каолиция 127 Коническая оболочка 58 Конус выпуклый 49 — двойственный 50 '— заостренный 61 — многогранный 58 — телесный 278 Лексикографический порядок 179 Линейное многообразие 55 Маршрут 219 Матрица блочно-диагональная 266 — игры 117 — импримитивная 147 — неотрицательная 136 — неразложимая 137 — ограничений коэффициентов 28 32 — — транспортной задачи 218 — перехода к новому базису 170 — примитивная 147 — технологическая 17 Метод Жордана — Гаусса 158 — отсечения 245 — потенциалов 231 — регуляризации 271 — «северо-западного угла» 222 — эллипсоидов 288 Многогранник выпуклый 57 — целочисленный 247 Множество выпуклое 41—44 303 _ — многогранное 74, 75 — допустимых векторов 63, 87 — планов 87 — регулярное 69 — решений задачи 97 Модель Леонтьева 23 — — обобщенная 25, 141 Нормаль 44 Носитель граничной точки 65 План 33 — опорный 163 _ — начальный 168, 180, 181 — — — транспортной задачи 222 — — невырожденный 164 — оптимальный 33 — перевозок 15 — производства 136 Положительный ортант 48 Приведенная система уравнений 159, 203 Принцип максимума 152 Производная но направлению 34, 112 Псевдоплан 197 — начальный 209 — невырожденный 199 — строго допустимый 208 Размерность выпуклого множества 66 — линейного многообразия 55 Ранг матрицы 66 Решето Эратосфена 261 Симплекс-метод 158, 177 — модифицированный 191, 231 — двойственный 195, 201 Симплексная габлица 168, 204 . — — в координатной форме 203 207 Скалярное умножение системы не- равенств 88 Следствие системы неравенств 78 Собственное число Фробениуса 141 Стратегия игрока 116 — — гарантирующая 120 — — максиминная 120 — — минимаксная 121 — — смешанная 122 Схема межотраслевого баланса 19 Теорема двойственности 90, 95 — Минковского 82 — Неймана 7, 123 — о замещении (Самуэльсон) 142 — о магистрали 146, 148 — равновесия 90, 92 — эргодическая 147 Точка внутренняя 64 — граничная 55 — крайняя 55 — седловая игоы 120 — функции 123 Транспортная сеть 218 — — Связная 219 Условие отсечения 249 — правильности 249 Функция вогнутая 104 — выпуклая 103 — значений задачи 100 — положительно однородная 102 — характеристическая игры 127 — целевая 33, 87 Цикл 219 Элементарное преобразование сис- темы уравнений 158 Ядро кооперативной игры 126, 129, 136