Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 2
Текст из файла (страница 2)
С. Лебедеву, Л. Л. вотякову, Ю. К. Солнцеву, Б. В. Черкасскому, А. В. Найвельту, содействовавшим работе над переводом книги и прочитавшим отдельные ее рааделы. Их советы и замечания помогли устранить ряд недостатков и погрептпостей в оригинале и способствовали улучшению качества перевода.
А. А. Фридман ИЗ ПРЕДИСЛОВИЯ АВТОРА Зта книга содержит три раздела: линейное программирование, теорию потоков в сетях и целочисленное программирование. Основное внимание в пей уделяотся методам решения задач и их теоретическому обоснованию. Отбирая материал для книги, я обращал внимание главным образом на следующие три группы вопросов: 1) вопросы, которые представлялись мне наиболее важными, 2) вопросы, которые были мне хоров~о знакомы, 3) вопросы, которые не излагались подробно в других книгах.
Раздел, посвященный линейному программированию, достаточно стандартен, в него включен весь материал, необходимый для понимания остальных разделов. В з 6.1 описан взаихпгый метод решения прямой н двойственной задачи Балинского и Гомори [7[, который ранее не излагался в книгах по линейному программированию. В этом же разделе, $ 4.2, вводится процедура исключения по столбцам, используемая в алгоритмах целочисленного программирования (в отличие от процедуры исключения по строкам, используемой в обычном симплскс-методе). Второй раздел, посвященный потокам в сетях, содержит много нового материала, отсутствующего в других книгах. В главе 8 приводится новое доказательство Вейпотта и Данцига [199[ свойств абсолютно унимодулярных матриц.
В этой же главе рассматривается полученная Здмопдсом и Карпом [58) оценка сверху количества действий для нахождения максимального потока. В главе 9 предлагается новая схема анализа многополюсных потоков в сетях. Главы 10 и 11 целиком содержат новые результаты, получоппые главным образом после 1962 года. Излагаются методы решения задачи о кратчайшем пути (Флойд [63[, Дийкстра [49), Ху и Торрес [113)), задачи о мпогопродуктовых потоках (Форд и Фалкерсоп [66[, Гомори н Ху [91[, Ху [107)). Здесь не рассматривается метод дефекта Форда — Фалксрсона, так как он прекрасно описан в их книге [67[. 1!оскольку главное внимание в книге уделяется алгоритмам, а пс приложениям, то в нее не включено описание системы ПЕРТ, которую можно рассматривать как специальное приложение теории потоков в сетях.
В основном во втором разделе либо содержится материал, отсутствующий в книге Форда и Фалкерсопа [67[, либо рассмат- из пгздисловия лвтОРА риваются те же вопросы, по с другой точки зрения. Таким образом, этот раздел может служить дополнением к их книге. В главе 42 излагаются результаты, полученные доктором Р. Е. Гомори и автором. В пей предлагается совершенно новый подход к задачам, обычно рассматриваемым в функциональном анализе. Все результаты приводятся в очень сокращенной форме. Читателям, интересующимся этими вопросами, рекомендуется прочитать работу (921. В главах 43, 44 и 45 подробно рассматриваются алгоритмы, основанные на методе отсекающей плоскости Гомори (79], [801, (841, и алгоритм разбиения Вендерса И8).
В главе 16 разбирается работа Витцгалла [2451, посвященная целочисленным задачам с параболическими ограничепкями. В главе 47, написанной Р. ][. Юнгом, излагается его прямой алгоритм целочисленного программирования (2251 и алгоритм Гловера [761. В главах 48 — 20 приводятся новые результаты д-ра Гомори (86], некоторые из которых сообщены автору в личных беседах. К сожалению в книгу не вошли результаты Вдмопдса и других о паросочетаниях (551, [56], 1571, 161, (2461 и результаты Фалкерсона (691, Мипти (454), Татта [1941 н других о связи между теорией матроидоп и сетями. Я был вынужден исключить эти вопросы в силу недостаточного знакомства с ними. Здесь нужно сказать несколько слов о библиографии. В начале каждого параграфа обычно указывается работа, лежащая в его основе.
Эта работа пе обязательно является первой оригинальной статьей по рассматриваемому вопросу. Если имеется обзор, в котором материал представлен лучше, то ссылка делается и на пего. В библиографии указано более двухсот работ. Некоторые из пих но имеют к книге прямого отношения, и первоначально я намеревался опустить их, по работы, указанные в добавлениях к главам, сильно увеличили список литературы. Сюда же вклх>че- из певдисловия АВТОРА ны названия некоторых книг по математическому программировашпо. Численные примеры рассматриваются обычно после описания алгоритмов.
После глав 1 — 10 даны упражнения. Приводятся нерешешпзе задачи и добавления, в которых обсуждаются нерассмотренные в книге вопросы. Главы и параграфы, помеченные в оглавлении звездочкой, могут быть опущены при чтении без нарушения целостпости книги. Порядок чтения глав указан на диаграмме. Первая часть книги может быть использована как односеместровый курс по линейному программированию. Вторая часть может служить учебником по теории потоков в сетях. Третью часть можно независимо использовать как учебпик по целочисленному программированию. ГЛАВА г основные понятия 1Л. Задачи линейного программирования Приведем три задачи, которые можно сфорлтулировать как задачи линейного программирования.
Задача 1. Представим себе доиатппюю хозяйку, собиратощутося в магазин за продуктами. Предполотким, что в рацион семьи входят т различных питателытых веществ, в том числе не менее Ь, единиц первого вида веществ, Ьл единиц второго вида,..., Ь единиц ил-го вещества. В магазине продается и различных продуктов. Каткдый продукт можно представить вектором аи состоящилт из ил компонент, причем ття компонента вектора озпачает количество т-го питательного вещества, содержащегося в единице данного продукта. Поэтому матрица А = (а;;) размера ти х и может быть использована для указания соотношения между произвольным продуктом и количеством содержащихся в неп питательных веществ.
Наждый столбец матрицы соответствует одному виду продут<та. Таким образом, ам — количество т-го питательного вещества, содержащегося в единице (-го продукта. Пусть х,, х„..., х„— количества соответствующих продуктов, покупаемых хозяйкой. Для того чтобы рацион семьи содержал все необходимые питательные вещества, необходимо выполнение условия Ах > Ь, где А=(ац), х=[х,, х,„..., х), Ь=[Ь„..., Ьм[. Условие (1) может выполняться прн различных х, но домашнюю хозяйку интересует лишь то решение, которое минимизирует общую стоимость всех покупок. Если с„сл,..., с„— цены соответствующих продуктов, то общая стоимость г записывается в виде г == стхт + ... + с х (2) Тот факт, что хозяйка может только покупать, но не продавать, выражается дополнительными ограничениями': хт)0 ([.=1,..., и).
(3) Задача состоит в минилтизации фупкцин (2) при условиях (1) и (3). гл. ь основнык понятия Задача 2. Зта задача несколько более искусственная, чем первая. Представим себе продавца таблеток, содержащих питательные вещества в чистом виде. Продавец хотел бы извлечь из продажи своего товара возможно большую прибыль. Пусть уп у„..., у — цены таблеток, каждая из которых содеризиг единицу 1-го питательного вещества. Предположим тагоке, что продавцу таблеток известно содержание питательных веществ в каждом виде продукта, т.
е. матрица (агт), выражающая связь между продуктами и количеством питательйых веществ, салери ащихся в них. Для того чтобы выдержать конкуренцию в торговле, цепы у; должны быть установлены в соответствии с условием ~~~ р;аы <с; (для всех 1=1, ..., и). (4) а=1 Если условие (4) выполняется, то покупка таблеток домашней хозяйкой, составляющей меню для семьи, всегда обойдется ей де~зезле, чем покупка продуктов. Общая сумма, аатрачиваемая на покупку таблеток (для семьи, рацион которой содер'кит Ь; единиц 1-го питательного вещества), тогда выразится как ш=уЬ,+...
+у Ь (5) Продавец таблеток желал бы установить цепы у; таким образом, чтобы функция (5) принимала максимальное значение при выполнении условия (4). Естественно, все цепы должны быть неотрицательными, т. е. у; ) 0 (1 = 1,..., т). Эта задача продавца опять является задачей линейного программирования, т. е. задачей нахождения максимума или минимума линейной функции при наличии линейных ограничений и условия пеотрицательностп переменных. Задача 3.
Рассмотрим химическое производство, которое должно производить Ь~ единиц 1-го продукта, Ь, единиц 2-го продукта,..., Ь единиц т-го продукта. Эти продукты получаются в результате различных процессов. 11аждый процесс может быть представлен вектором, показывающим, какое количество каждого продукта можно получить от данного процесса, используемого с единичной интенсивностью. 1(оппоненты вектора могут принимать и отрицательные значения, если в данном процессе продукт не производится, а потребляется.
Пусть хп хз,..., х„— интенсивности использования процессов; а„а.„..., а„— векторы, представляюгцие процессы, и пусть с„с,,..., с, — эксплуатационные расходы па единицу интенсивности соответствующих процессов. Тогда снова возникает задача отыскания минимума функции х=- ~ с,х~ у=! !.2. эквивлякптнык Фо!'муг!иговки при условиях н агх;= — Ь, хг)0 (! =1, ° °, п). 1.2. Эквивалентные формулировки Задача линейного программирования состоит в нахождении минимума линейной функции,переменные которой удовлетворяют пинейным неравенствам, т, е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
