Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191)
Текст из файла
1МТЕОЕР РРООРАММ!МО АМО МЕТЧЧОРК В ОМ~5 т. с. ни 1'го1еввог, Л1агЬегпа11св 11еяеагс11 Сепгег апд Лерагггпеп1 о1 Соп1рп1ег Бс1епсев 1лйгегв1гу о1 РРЬсопвРп Л(ЫЬоп-*1рев1еу Рн Согпрапу 11еадп1а, Маввас1швойя Меп!о Раг1с, СаИогп1а 1.опдоп Поп У!1!Ь, ( 1070 Т. ХУ ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ И ПОТОКИ В СЕТЯХ Перевод с апглийского П. Л. Бузыцкого Б. Б. Левпера Б. Г. Литвака Под редакцией д.
Л. Фридмана ИЗДАТБ7П>БТБО «МИР» Москва 1974 УДК 51.38+ 519.9 Книга посвящоиа новым направлениям в целочисленном программировании в теории потоков в сетях. Ге автор — извссюиай специалист в области математического программирования. Изкагаются орвгииальпые результаты автора о реализуемости, анализе и синтезе л1погоиолюсиых потоков. Впервые развиваются поные аспекты целочисленного ирограммироватиш, связанные с тсорсюи'о-групповым подходом к анализу целочисленных задач.
Кинга содержит болыиой фактаческзи1 материал, написана хорошим языком и читается легко. Она представляет несомненные интерес для специалистов в области дискретной математики, математигоского программирования, теоретической кибернетики п математической зкопоши и. Кс можно использовать как учебное пособие для студентов и аспирантов указанных специальностей, Редакция литера>нури иа математическим иаука.к Х 32 — 74 © Перевод на русский язык, «Мнр», 1974 . 20204 — 032 041(01) — 74 ПРЕДИСЛОВИЕ РЕДАКТОРЛ ПЕРЕВОДА Книга Т.
Ху посвящена теории н методам решения дискретных условно экстремальных задач. В ней рассматриваются разнообразные аспекты проблемы пахо;кдения экстремума линейной функции, на переменные которой наложены линейные ограничения и требование целочислеппости. В лпторатуре эта проблематика известна под названием иелочиеленное программирование или диенрепзное программирование. Задачи такого типа весьма актуальны, так как к нх решению сводится анализ разнообразных ситуаций, возникающих в экономике, технике, военном деле и других областях. Эта проблематика шпореспа и с математической точки зрения. Она естественно связана с проблемазш комбинаторпой и дискретной математики— древпейппгни и пеувядшощимп фрагментами классической математики.
И там и тут явно или неявно многие вопросы связапы с перебором, перечислением (полпыз1 пли частичным) вариаптов— допустимых планов задачи. С появлением ЗВМ, ростом их производительности и расширением возможностей перебора повысился интерес к дискретным задачам и к дискретной (конечной) математике в целом. Целочисленное программирование исторически выросло из непрерывного линейного ирограммнровапия, сразу начало использовать его пдеп, аппарат и методы. По мере раавития в пем все чаще используются идеи и язык дискретной, конечной мателштики, и мы становимся свидетелями того, как сшвтез идей и средств непрерывной н дискретной математики дает новью побеги и плоды... Проблематнка дискретных экстремальных задач менее развита по сравпешпо с непрерывнымп, хотя число публикаций по дискретным задачам быстро растет.
До последнего вромони зто, в основнозь была журнальная литература. 11а русском языке указанные вопросы эатрагпвалпсь в книгах Л. Р. Форда и Д. Р. е1залкерсопа 167), Г. Г. Гольштейна и Д. Б. 10дина 13*] '), а нпига А. А. Корбута и 1О. Ю. Финкельштейна 19*) целиком посвящена этой тематике. Бедность литературы по дискретным экстремальным задачам с одной стороны и появление новых розультатов — с другой з) Звездочкой отмечены работы, добавленные прп коронадо. — Прим.
рва н!'Гдис:н>в!«к ггдАкто>>л т>кгкводА вызывают естественнух> потребность в книгах, отражающих современные достн кения в этой области. Предлагаемая читател>о книга Т. Ху, как нам кажется, с этой точки зрения весьма полезна. Опа имеет ряд несомненных достоинств. 1) анита построена автономно, в ней излагаютсн все основные факты, необходимые для ее понимания, 2) В пей весьма компактно и снстсматическн изложен болшпой фактический материал, в частности много свежего материала, ранее известного лишь по журнальным статьям.
«Старая проблематика» (например, теория потоков) излагается оригинально, с учетом последних научных результатов. 3) В книге впервые намечаа>тся интересные связи с такими разделами математики, как функциональный анализ н теория дискретных групп. 1(нига состоит иэ трех бол»,пнх частей н трех приложений. Лервая часть — «Линейное программирование» вЂ” содержит весь необходимый для дальнейшего чтении материал. Этот материал достаточно тралнционе>ц хотя и включает некоторые сведения, не нзлагазшнеся ранее в книгах (см., например, з 0>.1, 4 4.2).
Р>горан часть — «Потоки в сетях» — по содержали>о частично пересекается с упоминавшейся выше прекрасной книгой Л. Р. Форда и Д. Р. Фалкорсона и по существу является нродолжонием этой книги. Упомянем здесь новый и впервые систематически излагаемый в гл. 10, 11, 12 материал, посвящонный многопо:косным сетям, двух- н многонродуктовым потокам, потокам в непрерывной среде. Лрн наложении алгоритмов решения потоковь>х задач автор уделяет больпюс внимание теоретическим оценкам эффективности соответствующих алгоритмов. '1"ретья часть — «Цсс>очнсленпос программирование» вЂ” содержит весьма подробное изложение основных регулярных методов решении линейных це:>очислепных задач.
И гл. 13, 14, 15 рассматриваются известные алгорнтчь> Гоморп, основанные па ндес введения отсекающнх плоскостей. В гл. 17 (написанной специально Р.Д. 10нгом) впервь>с достаточно попо и подробно излагается прямой алгоритм решшшя линейных целочисленных задач. Если в алгоритмах Гоморн «дзи>кение» к оптимальному целочисленному решению происходит по нецелочпслсппым планам ц первый жс достигнутый при этом целочисленный нлап будег опти»>альных, то н прямом алгоритме мы движемся от одного цеточисленного плана задачи к другому, лучшему, пока пе достигнем оптимума. Особо хочется остановиться на содержании гл. 19 и 20, отражающих новые результаты, нринадле>кащне Р. 1'онори. Фактически здесс впервые систематически нз:>агаетсн теоретико-групповой подход к ре>нению линейных целочисленных задач.
Указан- мекд>исловик РкдлктогА пг>геводА ные связи с теорией групп нредставляк>тся плодотворнымн и заслуживают пристального внимания. В последнее время появилось доволю>о много работ, связанных с этим направлением, однако у пас эта тематика до сих пор была мало известна. В приложениях А, В, С рассматривается процесс приведения целочисленной матрицы к нормальной форме Смита (лежащий в основе ре>пения систем линейных уравнений в пространстве целочисле>нп>х векторов), приводится один пз вариантов доказательства теорем двойственности линейного программирования, н, паконшп кратко обсуждается схема типа упорядоченного перебора для решения целочнслоппых задач. В конце книги приводится обширная библиография (более 200 наименований) по затронутым в пой и смежным вопросам.
Мы сочли целесообразным несколько расширить список литературы, добавив ряд работ (в основном отечественных), либо вышедших позже, либо оказавшихся вне поля зрения автора, и дающих некотороо представление о новь>х результатах в этой области. Книга написана и читается достаточно легко, хотя в ряде случаев материал преподносятся довольно конспективно (гл. 12, 10, 20). 1(ак правило, наложение методов и а.>горитмов сопровождается нл,пострацней численных примеров, помогающих уяснить суть дела и вычислительные аспекты. Неудивительно, что при такой насыщенности фактическим материалом и болыпом обьеме книги в пей обнаружились недостатки и погрешности.
Ряд утверждений сформулирован неточно; некоторые теоремы доказаны при одних предположениях, а использу>отея в болео общих ситуациях; в ряде рассуждений (доказательств) обнаружены пробелы; имеется ломало опечаток. Порой автор, увлекпи>сь содержательной стороной алгоритмов, пе выделяет в виде отдельных утверждений условий сходимости соответствующих алгоритмов ь оптимуму, полагая, что внимательный читатель сам сможот их сформулировать.
Все погрешности, замеченные переводчика>>и и редактором книги, в русскол> тексте устранены — иногда нутом введения соответствующих приз>ечаний, я порой уточнением и:>н изиепопиои авторского токста. Внося соответствующие изменения, мы старались придерживаться оригинальных работ, которым (каь указывал автор книги) оп следовал при изложении тех или иных результатов.
1(мига предназначена для математиков, инженеров и специалистов, интересующихся проблемами теории управления, математической экономики, теоретической кибернетики, дискретной математики и пх прнлшкеппямп. Она будет полезна также аспирантам и студентам старших курсов соответствующих специальностей. 11пига Т. Ху отражает зпачителы>ый прогресс в развитии теории и методов решения лпскретпых условно экстремалы>ых пгвдисловнв гкдактовл пвеввода задач.
Внимательный читатель найдет в пей пе только систематическое изложение предмета, но и свеэкие идеи, подходы, открытые вопросы, стимулирующие и порождающие интерес к самостоятельной творческой работе в этой области. Ее появление будет, несомненно, способствовать интенсификации и расширению фронта работ в области дискретных экстремальных задач, привлечению к работе в этой области большого числа специалистов. В закл1очепие хочется выразить искреннюю благодарность Е. Г. Гольштейну, С.
Характеристики
Тип файла DJVU
Этот формат был создан для хранения отсканированных страниц книг в большом количестве. DJVU отлично справился с поставленной задачей, но увеличение места на всех устройствах позволили использовать вместо этого формата всё тот же PDF, хоть PDF занимает заметно больше места.
Даже здесь на студизбе мы конвертируем все файлы DJVU в PDF, чтобы Вам не пришлось думать о том, какой программой открыть ту или иную книгу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
