Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 139
Скачиваний: 0
10 ИЗ ПРЕДИСЛОВИЯ АВТОРА
риваются те же вопросы, но с другой точки зрения. Таким обра зом. этот раздел может служить дополнением к их книге.
В главе 12 излагаются результаты, полученные доктором Р. Е. Гомори и автором. В ней предлагается совершенно новый подход к задачам, обычно рассматриваемым в функциональном анализе. Все результаты приводятся в очень сокращенной форме. Читателям, интересующимся этими вопросами, рекомендуется прочитать работу [92].
В главах 13, .14 и 15 подробно рассматриваются алгоритмы, основанные на методе отсекающей плоскости Гомори [79], [80], ~ [81], и алгоритм разбиения Вендерса [18]. В главе 16 разбирается
работа Витцгалла |
[215], посвященная |
целочисленным задачам |
с параболическими |
ограничениями. В |
главе 17, написанной |
Р. Д. Юнгом, излагается его прямой алгоритм целочисленного программирования [225] и алгоритм Гловера [76]. В главах 18—20 приводятся новые результаты д-ра Гомори [86],-некоторые из ко торых сообщены автору в личных беседах. К сожалению в книгу не вошли результаты Эдмондса и других о паросочетаниях [55], [56], [57], [6], [216] и результаты Фалкерсона [69], Минти [154],
Татта [194] и других о связи между теорией матроидов и сетями. Я был вынужден исключить эти вопросы в силу недостаточного знакомства с ними.
Здесь нужно сказать несколько слов о библиографии. В начале каждого параграфа обычно указывается работа, лежащая в его основе. Эта работа не обязательно является первой оригинальной статьей по рассматриваемому вопросу. Если имеется обзор, в кото ром материал представлен лучше, то ссылка делается и на него.
В библиографии указано более |
двухсот работ. Некоторые |
из них не имеют' к книге прямого |
отношения, и первоначально |
я намеревался опустить их, но работы, указанные в добавлениях к главам, сильно увеличили список литературы. Сюда же включе-
20
ИЗ ПРЕДИСЛОВИЯ АВТОРА |
И |
ны названия некоторых книг по математическому программи рованию.
Численные примеры рассматриваются обычно после описания алгоритмов. После глав 1—10 даны упражнения. Приводятся нерешенные задачи и добавления, в которых обсуждаются нерас смотренные в книге вопросы. Главы и параграфы, помеченные в оглавлении звездочкой, могут быть опущены при чтении без нарушения целостности книги. Порядок чтения глав указан на диаграмме. Первая часть книги может быть использована как односеместровый курс по линейному программированию. Вторая часть может служить учебником по теории потоков в сетях. Третью часть можно независимо использовать как учебник по целочисленному программированию.
ГЛАВА 1
ОСНОВНЫЕ ПОНЯТИЯ
1.1. Задачи линейного программирования
Приведем три задачи, которые можно сформулировать как задачи линейного программирования.
Задача 1. Представим себе домашнюю хозяйку, собирающую ся в магазин за продуктами. Предположим, что в рацион семьи входят т различных питательных веществ, в том числе не менее Ъt единиц первого вида веществ, Ъ2 единиц второго вида, . . ., Ът единиц m-го вещества. В магазине продается п различных про дуктов. Каждый продукт можно представить вектором aj, состоя щим из т компонент, причем t-я компонента вектора означает количество i-ro питательного вещества, содержащегося в единице данного продукта. Поэтому матрица А = (аи) размера т X п может быть использована для указания соотношения между произвольным продуктом и количеством содержащихся в нем питательных веществ. Каждый столбец матрицы соответствует одному виду продукта. Таким образом, a tj — количество г-го питательного вещества, содержащегося в единице /-го продукта. Пусть xi, ж2, . . ., хп — количества соответствующих продуктов, покупаемых хозяйкой. Для того чтобы рацион семьи содержал все необходимые питательные вещества, необходимо выполнение усло вия
Ах ^ |
b, |
(1) |
где А = (йц), х = [хи х2, . . ., |
хп], |
Ь = [Ъи . . ., Ът]. |
Условие (1) может выполняться при различных х, но домашнюю хозяйку интересует лишь то решение, которое минимизирует общую стоимость всех покупок. Если ct, с2, . . ., сп — цены соответствующих продуктов, то общая стоимость z записывается
в виде |
С\Х\ |
. . . -j—спхп, |
(2) |
z |
|||
Тот факт, что хозяйка может только покупать, но не продавать, |
|||
выражается дополнительными |
ограничениями: |
|
|
xi |
> 0 (j |
= 1, • • п). |
(3)' |
Задача состоит в минимизации функции (2) при условиях
(1) И(3).
14 |
ГЛ. 1. ОСНОВНЫЕ понятия |
Задача 2. Эта задача несколько более искусственная, чем |
|
первая. |
Представим себе продавца таблеток, содержащих пита |
тельные вещества в чистом виде. Продавец хотел бы извлечь из
продажи |
своего товара возможно |
большую |
прибыль. Пусть |
у 1 , у 2> • |
• ч Ут — цены таблеток, каждая из |
которых содержит |
|
единицу |
£-го питательного вещества. |
Предположим также, что |
|
продавцу таблеток известно содержание питательных веществ в каждом виде продукта, т. е. матрица (atj), выражающая связь между продуктами и количеством питательных веществ, содержа щихся в них. Для того чтобы выдержать конкуренцию в торговле,
цены у i должны быть установлены в |
соответствии с |
условием |
т |
|
|
2 yiaU ^Cj (для всех j = |
l, |
(4) |
г=1 |
|
|
Если условие (4) выполняется, то покупка таблеток домашней хозяйкой, составляющей меню для семьи, всегда обойдется ей дешевле, чем покупка продуктов. Общая сумма, затрачиваемая на покупку таблеток (для семьи, рацион которой содержит bt единиц г-го питательного вещества), тогда выразится как
W = У\Ь{ + • ■. + Ут^т- |
(5) |
Продавец таблеток желал бы установить цены у { таким обра зом, чтобы функция (5) принимала максимальное значение при выполнении условия (4). Естественно, все цены должны быть
неотрицательными, т. е. |
y t ^ 0 |
(i = 1, . |
т). Эта задача про |
давца опять является |
задачей |
линейного |
программирования, |
т. е. задачей нахождения максимума или минимума линейной функции при наличии линейных ограничений и условия неотри цательности переменных.
Задача 3. Рассмотрим химическое производство, которое должно производить hi единиц 1-го продукта, Ъ%единиц 2-го про дукта, . . ., Ът единиц т-то продукта. Эти продукты получаются в результате различных процессов. Каждый процесс может быть представлен вектором, показывающим, какое количество каждого продукта можно получить от данного процесса, используемого с единичной интенсивностью. Компоненты вектора могут прини мать и отрицательные значения, если в данном процессе продукт не производится, а потребляется. Пусть хи хг, • ■., хп — интен сивности использования процессов; аь а2, . . ., а„ — векторы, представляющие процессы) и пусть си с2, . . ., сп — эксплуата ционные расходы на единицу интенсивности соответствующих процессов. Тогда снова возникает задача отыскания минимума
функции
П
z = 2 cixi
з= 1
1.2. ЭКВИВАЛЕНТНЫЕ ФОРМУЛИРОВКИ |
15 |
при условиях
п
Ц а я = Ь, X j^O (7 = 1, . . п).
1=1
1.2. Эквивалентные формулировки
Задача линейного программирования состоит в нахождении минимума линейной функции, переменные которой удовлетворяют линейным неравенствам, т. е. мы хотим минимизировать
|
|
. |
Z = 2 |
C j X j |
|
|
|
i=i |
|
при условиях |
|
|
|
|
п |
|
|
|
(i = 1, |
Ys a t j X j ^ z b i |
||||
;=i |
|
|
|
|
|
н |
А |
О |
II |
Щ < п ) , |
(1 )
( 2 )
( 3 )
где Xj — переменные и bt, cj — заданные константы. Линейная функция z в (1), которую мы хотим минимизировать, называется
целевой функцией, а неравенства (2) и (3) — ограничениями.
Некоторые из условий (2) могут быть равенствами. В этом случае они также называются ограничениями.
Сразу можно заметить три особенности задачи линейного программирования: 1) ограничения представляют собой линейные неравенства (уравнения); 2) целевая функция, которую надо минимизировать, является линейной; 3) на некоторые (все) пере менные наложено требование неотрицательности. В большинстве классических методов оптимизации фундаментальным аппаратом является дифференцирование, поскольку в точках максимума или минимума производные обращаются в нуль. В нашем случае целевая функция линейна, поэтому максимум или минимум достигается в граничной точке области определения, в которой, вообще говоря, не все односторонние производные обязаны обра щаться в нуль. Требование неотрицательности переменных можно было бы заменить условием xj = и), где и} Sg 0, но это привело бы к нелинейным ограничениям, что не позволило бы решать задачу классическими методами оптимизации. Для решения задач линейного программирования (иногда называемых линейными прог раммами) требуется новый аппарат.
Ниже приводится несколько формулировок, эквивалентных условиям (1), (2) и (3). В дальнейшем мы будем использовать форму записи, наиболее целесообразную в каждом конкретном случае.
16 |
ГЛ. 1. ОСНОВНЫЕ ПОНЯТИЯ |
I. Нахождение минимума функции эквивалентно *) нахожде нию максимума этой функции, взятой с противоположным знаком. Поэтому можно заменить условие (1) на следующее:
найти максимум функции
П
z'=-5jCj Xj .
5=1
II. Ограничения в форме неравенств (2)
п
У I
3= 1
можно представить в виде равенств, использовав новые перемен ные st (st 0), называемые слабыми переменными:
|
|
|
п |
|
|
|
|
|
|
|
|
|
|
|
1 2 &ijx i |
Si — bi. |
|
|
|
|
|||
|
|
n |
5=1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Для неравенства |
2 |
aijxi ^ b i |
можно |
взять |
0 и заменить его |
||||||
равенством |
|
3= 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
п |
|
|
bt. |
|
|
|
|
|
|
|
|
2 |
^ijxj ~Ь |
|
|
|
|
|||
|
|
|
3 |
= 1 |
|
|
|
|
|
п |
|
|
|
|
|
|
|
|
|
|
|
|
|
III. |
Если |
ограничение |
записано |
в виде |
равенства |
Q'ijxj — bi) |
|||||
|
|
|
|
|
|
|
|
|
|
2 |
|
его можно |
заменить двумя |
неравенствами |
|
|
3=1 |
|
|||||
|
|
|
|
||||||||
|
|
п |
|
|
|
п |
|
|
|
|
|
|
|
2 |
atjXj^bi |
и' 2 aijXj^bi. |
|
|
|||||
|
|
з = 1 |
|
|
|
3= 1 |
|
|
|
|
|
|
|
|
|
|
71 |
|
|
|
|
|
|
Если имеется т равенств |
2 aijxj = bi |
(i = |
1, . . ., |
т), |
их можно |
||||||
заменить (т 1) |
|
|
|
3= 1 |
|
|
|
|
|
|
|
неравенствами |
|
|
|
|
|
|
|||||
п |
|
(i= l, ...,/») |
т |
?! |
|
|
|
||||
2 U i j X j ^ b i |
и |
2 |
( 2 a i j X j — |
b i ) ^ 0 . |
|||||||
3= 1 |
|
|
|
|
|
1=1 |
3=1 |
|
|
|
|
IV. Если на переменную Xj не наложено условия неотрицатель ности, ее можно заменить двумя неотрицательными переменными
Xj и xj, положив
X j = x \ — X j ,
x j^ O .
!) В том смысле, что точка минимума функции z совпадает с точкой максимума функции г', если z = — z'.— Прим, ред.