Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

УДК 51.38 + 519.9

’ЭКЗЕМПЛЯР

iЧИТАЛЬНОГО ЗАЛА

Щ- d W U

Книга посвящена новым,направлениям в целочисленном Программиро­ вании и теории потоков в сетях. Ее автор — известный специалист в области математического программирования. Излагаются оригинальные результаты автора о реализуемости, анализе и синтезе многополюсных потоков. Впервые развиваются новые аспекты целочисленного программирования, связанные с/ теоретико-групповым подходом к анализу целочисленных задач.

Книга содержит большой фактический материал, написана хорошим языком и читается легко. Она представляет несомненный интерес для спе­ циалистов в области дискретной математики, математического программи­ рования, теоретической кибернетики и математической экономики. Ее можно использовать как учебное пособие для студентов и аспирантов указанных специальностей.

о ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА

вызывают естественную потребность в книгах, отражающих совре­ менные достижения в этой области.

Предлагаемая читателю книга Т. Ху, как нам кажется, с этой точки зрения весьма полезна. Она имеет ряд несомненных дос­ тоинств.

1) Книга построена автономно, в пей излагаются все основные факты, необходимые для ее понимания.

2) В ней весьма компактно и систематически изложен большой фактический материал, в частности много свежего материала, ранее известного лишь по журнальным статьям. «Старая пробле­ матика» (например, теория потоков) излагается оригинально,

сучетом последних научных результатов.

3)В книге впервые намечаются интересные связи с такими разделами математики, как функциональный анализ и теория дискретных групп.

Книга состоит из трех больших частей и трех приложений. Первая часть —«Линейное программирование»— содержит весь необходимый для дальнейшего чтения материал. Этот материал

достаточно традиционен, хотя и включает некоторые сведения, не излагавшиеся ранее в книгах (см., например, § 6.1, § 4.2).

Вторая часть —«Потоки в сетях»— по содержанию частично пересекается с упоминавшейся выше прекрасной книгой Л. Р. Фор­ да и Д. Р. Фалкерсона и по существу является продолжением этой книги. Упомянем здесь новый и впервые систематически излагае­ мых! в гл. 10, 11, 12 материал, посвященный многополюсным сетям, двух- и многопродуктовым потокам, потокам в непрерыв­ ной среде. При изложении алгоритмов решения потоковых задач автор уделяет большое внимание теоретическим оценкам эффек­ тивности соответствующих алгоритмов.

Третья часть —«Целочисленное программирование»— содержит весьма подробное изложение основных регулярных методов реше­ ния линейных целочисленных задач. В гл. 13, 14, 15 рассматри­ ваются известные алгоритмы Гомори, основанные на идее введе­ ния отсекающих плоскостей. В гл. 17 (написанной специально Р.Д. Юнгом) впервые достаточно ясно и подробно излагается пря­ мой алгоритм решения линейных целочисленных задач. Если в алгоритмах Гомори «движение» к оптимальному целочисленно­ му решению происходит по нецелочисленным планам и первый же достигнутый при этом целочисленный план будет оптималь­ ным, то в прямом алгоритме мы движемся от одного целочислен­ ного плана задачи к другому, лучшему, пока не достигнем опти­ мума.

Особо хочется остановиться на содержании гл. 19 и 20, отра­ жающих новые результаты, принадлежащие Р. Гомори. Факти­ чески здесь впервые систематически излагается теоретико-группо­ вой подход к решепию линейных целочисленных задач. Указан­

ные связи с теорией групп представляются плодотворными и за­ служивают пристального внимания. В последнее время появилось

в основе решения систем линейных уравнений в пространстве целочисленных векторов), приводится один из вариантов дока­ зательства теорем двойственности линейного программирования, и, наконец, кратко обсуждается схема типа упорядоченного пере­ бора для решения целочисленных задач.

В конце книги приводится обширная библиография (более. 2Q0 наименований) по затронутым в пей и смежным вопросам. Мы сочли целесообразным несколько расширить список литера­ туры, добавив ряд работ (в основном отечественных), либо вышед­ ших позже, либо оказавшихся вне поля зрения автора, и дающих некоторое представление о новых результатах в этой области.

Книга написана и читается достаточно легко, хотя в ряде слу­ чаев материал преподносится довольно конспективно (гл. 12, 16, 20). Как правило, изложение методов и алгоритмов сопровождает­ ся иллюстрацией численных примеров, помогающих уяснить суть дела и вычислительные аспекты.

Неудивительно, что при такой насыщенности фактическим материалом и большом объеме книги в пей обнаружились недо­ статки и погрешности. Ряд утверждений сформулирован неточно; некоторые теоремы доказаны при одних предположениях, а ис­ пользуются в более общих ситуациях; в ряде рассуждений (дока­ зательств) обнаружены пробелы; имеется немало опечаток. Порой автор, увлекшись содержательной стороной алгоритмов, не выде­ ляет в виде отдельных утверждений условий сходимости соответ­ ствующих алгоритмов к оптимуму, полагая, что внимательный читатель сам сможет их сформулировать. Все погрешности, заме­ ченные переводчиками и редактором книги, в русском тексте устранены — иногда путем введения соответствующих примеча­ ний, а порой уточнением или изменением авторского текста. Внося соответствующие изменения, мы старались придерживаться ори­ гинальных работ, которым (как указывал автор книги) он следо­ вал при изложении тех или иных результатов.

Книга предназначена для математиков, инженеров и специали­ стов, интересующихся проблемами теории управления, матема­ тической экономики, теоретической кибернетики, дискретной математики и их приложениями. Она будет полезна также аспи­ рантам и студентам старших курсов соответствующих специаль­ ностей.

Книга Т. Ху отражает значительный прогресс в развитии теории и методов решения дискретных условно экстремальных

ческое изложение предмета, но и свежие идеи, подходы, откры­ тые вопросы, стимулирующие и порождающие интерес к самостоя­ тельной творческой работе в этой области. Ее появление будет, несомненно, способствовать интенсификации и расширению фрон­ та работ в области дискретных экстремальных задач, привлече­

Е. Г. Гольштейну, С. С. Лебедеву, А. А. Вотякову, Ю. К. Солн­ цеву, Б. В. Черкасскому, А. В. Найвельту, содействовавшим работе над переводом книги и прочитавшим отдельные ее разделы. Их советы и замечания помогли устранить ряд недостатков и по­ грешностей в оригинале и способствовали улучшению качества перевода.

А. А. Фридман

ИЗ ПРЕДИСЛОВИЯ АВТОРА

Эта книга содержит три раздела: линейное программирование, теорию потоков в сетях и целочисленное программирование. Основ­ ное внимание в ней уделяется методам решения задач и их теоре­ тическому обоснованию. Отбирая материал для книги, я обращал внимание главным образом на следующие три группы вопросов: 1) вопросы, которые представлялись мне наиболее важными, 2) вопросы, которые были мне хорошо знакомы, 3) вопросы, кото­ рые не излагались подробно в других книгах.

Раздел, посвященный линейному программированию, доста­ точно стандартен, в него включен весь материал, необходимый для понимания остальных разделов. В § 6.1 описан взаимный метод решения прямой и двойственной задачи Балинского и Гомори [7], который ранее не излагался в книгах по линейному программированию. В этом же разделе, § 4.2, вводится процедура исключения по столбцам, используемая в алгоритмах целочислен­ ного программирования (в отличие от процедуры исключения по строкам, используемой в обычном симплекс-методе).

Второй раздел, посвященный потокам в сетях, содержит мно­ го нового материала, отсутствующего в других книгах. В главе 8 приводится новое доказательство Вейнотта и Данцига [199] свойств абсолютно унимодулярных матриц. В этой же главе рассматривается полученная Эдмондсом и Карпом [58] оценка сверху количества действий для нахождения максимального потока. В главе 9 предлагается новая схема анализа многополюс­ ных потоков в сетях. Главы 10 и 11 целиком содержат новые результаты, полученные главным образом после 1962 года. Изла­ гаются методы решения задачи о кратчайшем пути (Флойд [63], Дийкстра [49], Ху и Торрес [ИЗ]), задачи о многопродуктовых потоках (Форд и Фалкерсон [66], Гомори и Ху [91], Ху [107]). Здесь не рассматривается метод дефекта Форда — Фалкерсона, так как он прекрасно описан в их книге [67]. Поскольку главное внимание в книге уделяется алгоритмам, а не приложениям, то в нее не включено описание системы ПЕРТ, которую можно рассматривать как специальное приложение теории потоков в сетях. В основном во втором разделе либо содержится материал, отсутствующий в книге Форда и Фалкерсона [67], либо рассмат-