Basic Linear Programming Brian D Bunday, B.Sc., Ph.D., F.S.S., F.I.M.A. School of Mathematical Sciences. University of Bradford Edward Arnold / Б. Бонди ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Перевод с английского О. В. Шихеевой Под редакцией В. А. Волынского МОСКВА „РАДИО И СВЯЗЬ" 1989 ББК 32.973 Б23 УДК 519.852 (420) Редакция переводной литературы Банди Б. Б23 Основы линейного программирования: Пер. с англ. — М.: Радио и связь, 1989.- 176с.: ил. ISBN 5-256-00186-8. В книге английского автора освещены основные положения и методы линейного программирования. Рассмотрены симплекс-метод и его реали- зация на ЭВМ, проблема вырожденности, анализ чувствительности и двой- ственный симплекс-метод, транспортная задача, задача о назначении, двой- ственность в линейном программировании и др. Алгоритмы решения раз- личных задач линейного программирования реализованы на языке Бейсик, причем программы несложно перевести на такие языки, как Фортран или Паскаль. Для инженерно-технических работников, связанных с применением линейного программирования. ББК 32.973 Б 16020П000-042 141-89 046 (01)-89 Производственное издание БАНДИ БРАЙАН ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Заведующая редакцией О. В. Толкачева Редактор М.Г.Коробочкина Художественный редактор А. С. Широков Обложка художника В.Н.Забайрова Технический редактор О.А.Гришкина Корректор Г. Г. Казакова ИБ № 1643 Подписано в печать с оригинала-макета 11.01.89. Формат 60х88/16. Бумага Тип. № 2. Гарнитура "Пресс-роман". Печать офсетная. Усл. печ. л. 10,78. Усл. кр.-отт. 11,52. Уч.-изд.л. 10,51. Тираж 50 000 экз. (1 завод: 1—25 000 экз.). Изд. №22183. Заказ№ 6622. Цена 70 к. Издательство "Радио и связь". 101000 Москва, Почтамт, а/я 693 Ордена Октябрьской Революции и ордена Трудового Красного Знамени МПО "Первая Образцовая типография имени А. А. Жданова" Союзполиграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли.113054 Москва, Валовая,28 © В D Sunday 1984 ©Перевод на русский язык, предисловие и при- мечания редактора перевода, дополнительный ISBN 5-256-00186-8 (рус.) список литературы. Издательство "Радио и ISBN 0-7131-3509-3 (англ.) связь", 1989 Предисловие редактора перевода Линейное программирование как. раздел исследования операций имеет почти сорокалетнюю историю. Внедрение вычислительной техники дало значительный толчок исследованиям в этой области математики. Был разработан ряд алгоритмов решения задач линейного программи- рования, а в последующие годы были созданы программы и пакеты программ преимущественно для больших ЭВМ. Основная масса лите- ратуры по. линейному программированию в нашей стране выпущена в 60 -• 70-е годы. Исследования в этой области (как теоретические, так и прикладные) продолжаются и в настоящее время. Однако книг по приложениям линейного программирования, учитывающих появление новых алгоритмических языков, а также микроЭВМ и персональных ЭВМ, практически нет. Предлагаемая читателям книга восполнит этот пробел. Книга Б. Банди состоит из семи глав, в которых рассмотрены симп- лекс-метод и улучшенный симплекс-метод, решение транспортной задачи и задачи о назначениях. Кроме того, в ней обсуждаются вопросы устой- чивости и двойственности. Книга написана в расчете на читателя, не зна- комого с линейным программированием. Для ее понимания требуют- ся только знание языка Бейсик и знакомство с теорией матриц. Отличительной особенностью книги является ее прикладной харак- тер. Автор не только подробно описывает математический аппарат ре- шения задачи, но и предлагает строгий алгоритм решения, а затем приво- дит программу на языке Бейсик с описанием ее особенностей. Такая форма изложения удобна и для обучения, и для получения справочного материала. Все более широкое распространение персональных ЭВМ, для которых основным языком программирования является Бейсик, будет способствовать росту интереса к программам, приведенным в книге. Большое количество примеров значительно упрощает усвоение мате- риала. Приведенные в конце каждой главы упражнения дают возмож- ность самостоятельно опробовать программы, приведенные в книге, и получить практические навыки решения задач линейного програм- мирования. Результаты, полученные на разных ЭВМ, могут несколько отличаться от приведенных в книге из-за различий в разрядности машин и программном обеспечении. ДОПОЛНИТЕЛЬНЫЙ СПИСОК ЛИТЕРАТУРЫ 1. Юдин Д. Б., Гольдштейн Е. Г. Линейное программирование. Теория, методы и приложения. - М.: Наука, 1969. - 424 с. 2. Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого прог- раммирования. - М.: Наука, 1976. - 191 с. 3. Булавский В. А., Звягина Р. А., Яковлева М. А. Численные методы линейного программирования/ Под ред. Л. В. Канторовича. - М.: Наука, 1977. - 367 с. 4. Раскин Л. Г., Кириченко И. О. Многоиндексные задачи линейного программи- рования. Теория, методы, приложения.- М.: Радио и связь, 1982. - 239 с. ПРЕДИСЛОВИЕ Вниманию читателя предлагается курс линейного программирования, который может служить основой вузовских и специальных курсов. Книга будет полезна и своевременна для студентов, изучающих и тео- ретическую, и прикладную математику, а также для слушателей курсов численных методов. Специалисты, повышающие квалификацию на кур- сах исследования операций, также оценят этот материал. Математическая теория в предлагаемой книге рассматривается вполне корректно, хотя имеются и более строгие изложения. Недостаточная строгость изложения компенсируется обилием примеров. Основная задача книги — показать, каким образом теоретические идеи воплоща- ются в практические вычислительные процедуры, реализуемые на ЭВМ. Появление основных теоретических идей совпало по времени с появле- нием компьютеров, и это не случайно'. Без компьютеров невозможно использовать весь потенциал теории при решении практических задач. Программы в книге написаны на языке Бейсик (предполагается, что читатель с ним знаком), широко распространенном на большинстве микрокомпьютеров. На многих больших ЭВМ реализованы пакеты программ, основанные на методах, обсуждаемых в настоящей книге. Однако большие ЭВМ могут быть труднодоступны, а пакеты прикладных программ часто применяются вслепую. Интерактивный режим работы микрокомпьютеров позволяет студентам лучше понять, как работают программы. Не надо думать, что эти программы нельзя улучшить. Автор был бы рад получить от читателей соображения по улучшению программ. Предлагаемые программы просты и практичны. При желании можно применить их на других ЭВМ — они легко могут быть переведены на такие языки, как Фортран или Паскаль. Несколько замечаний о языке Бейсик и его применении в книге. Программы написаны с таким расчетом, чтобы они с минимальным количеством трудностей запускались на любом микрокомпьютере. В связи с этим в программах не предусмотрена графика высокого разрешения, не использованы цветовые и звуковые возможности. ' Это утверждение ошибочно, так как идеи линейного программирования были разработаны еще до появления ЭВМ (см., например, Канторович Л. В. Математичес- кие методы в организации и планировании производства — Л.: ЛГУ, 1939). — Прим. ред. В операторах присваивания команда LET опускается. На некоторых компьютерах эта команда обязательна и должна быть вставлена. Коман- да THEN включена в операторы IF ... THEN GOTO, хотя на некоторых компьютерах команды THEN или GOTO могут быть опущены. Не ис- пользовались конструкции IF ... THEN . . . ELSE и REPEAT ... UNTIL . . . . . . , поскольку они применимы не на всех компьютерах. Предполагает- ся, что нумерация массивов начинается с 0. Если нумерация массивов ЭВМ начинается с 1, необходимы некоторые изменения. В любом случае достаточно увеличить на 1 аргументы всех операторов DIM. Например, вместо DIM А (М) будет DIM А (М + 1), вместо В (К, L) - В (К + 1, L + 1) и т. д. Может быть, читатели найдут более элегантные изменения. Приводимые численные результаты получены на ЭВМ PET. На некоторых ЭВМ, работающих с числами другой точности, результаты могут не воспроизводиться идентично, однако различия должны возникать лишь в последних, несущественных знаках. Автор выражает благодарность друзьям, коллегам и студентам, внес- шим вклад в эту книгу. Многие задачи были решены студентами на экзаменах университета г. Брадфорда. Автор признателен за разрешение их использовать. Особенно хотелось бы упомянуть доктора Р. И. Скра- тона, который помимо сделанных им улучшений в численном анализе позволил автору использовать в некоторых программах его форматирую- щие процедуры. Автор благодарен К. Маку за полезные и содержатель- ные беседы о его методе решения задачи назначения и подходах к прог- раммированию этого метода. В заключение автор благодарит В. Хантер, . превратившую беспорядочную рукопись в аккуратно перепечатанный текст. Брайан Банди ОГЛАВЛЕНИЕ Предисловие редактора перевода ............................ 5 Дополнительный список литературы .......................... 5 Предисловие ........................................ .6 Глава 1. ОСНОВНЫЕ ИДЕИ. .............................. .8 1.1. Введение ...................................... 8 1.2. Графическое решение двухмерных задач. ................. 11 1.3. Стандартная форма задач линейного программирования . ....... 15 1.4. Обобщение на случай п переменных. .................... 17 1.5. Основные результаты линейного программирования .......... 18 1.6. Упражнения. ................................... 22 Глава 2. СИМПЛЕКС-МЕТОД. ............................. 25 2.1. Симплекс-метод при заданном начальном допустимом базисном решении...................................... 2 5 2.2. Реализация симплекс-метода на ЭВМ .................... 32 2.3. Порождение начального базисного допустимого решения ....... 38 2.4. Полное изложение симплекс-метода .................... 43 2.5. Проблемы вырождения ............................ 50 2.6. Упражнения. ................................... 55 Глава 3. АНАЛИЗ УСТОЙЧИВОСТИ РЕШЕНИЯ .................. 60 3.1. Обращение базиса и симплекс-множители ................. 60 3.2. Что получается при изменении задачи. ................... 64 3.3. Двойственный симплекс-метод. ....................... 70 3.4. Упражнения. ................................... 77 Глава 4. ТРАНСПОРТНАЯ ЗАДАЧА ......................... 82 4.1. Постановка задачи и ее решение ....................... 82 4.2. Алгоритм последовательного улучшения плана. ............. 88 4.3. Дисбаланс и вырожденность в транспортной задаче ........... 92 4.4. Постановка транспортной задачи на ЭВМ. ................. 97 4.5. Упражнения. .................................. 108 Глава 5.ЗАДАЧА О НАЗНАЧЕНИЯХ. ....................... 112 5.1. Введение .................................... 112 5.2. Метод решения Мака .............................113 5.3. Реализация метода Мака на ЭВМ ...................... 119 5.4. Упражнения. ..................................123 Глава 6. УЛУЧШЕННЫЙ СИМПЛЕКС-МЕТОД. .................. 126 6.1. Улучшенный симплекс-алгоритм. ..................... 126 6.2. Инициализация алгоритма. ......................... 133 6.3. Еще раз о вырожденности ..........................135 6.4. Программа для улучшенного симплекс-метода. ............ 139 6.5. Упражнения. .................................. 148 Глава 7. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ ... 152 7.1. Прямая и двойственная задачи ....................... 152 7.2. Теоремы двойственности .......................... 156 7.3. Анализ полученных результатов с точки зрения двойственности . . 162 7.4. Упражнения. .................................. 167 Рекомендации для дальнейшего чтения. ...................... 168 Список литературы ................................... 168 Приложение ....................................... 169 Ответы к упражнениям ................................ 170