Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 66
Текст из файла (страница 66)
Отсюда видно, что функция 0 (Ь) периодична и имеет перИод ав, когда Ь достаточно велико. Функция 0 (Ь) определена и в случае, когда Ь рваДР1 — р,). Для функции 0 (Ь) можно получить рекуррентное соотношение следующим образом. Предположим, что в оптимальном целочисленном решении некоторое х>) О. Тогда 0 (Ь) = 0 (Ь вЂ” а>) + (р1 — р;) а;, где (р1 — р>) а> — потери за счет того, что вес а> «заполнен» не первмм, а у-м предметом. Так как в оптимально»1 решении какое-то х>» О, то 0 (Ь) получается следующим образом: 0 (Ь) = шш (О (Ь вЂ” а>) + (р, — р,) а>). ГЛ.
18. ЗАДАЧА О РЮКЗАКЕ 376 Выражение (4) является рекуррентным соотношением, в котором 0 (Ь) могут быть подсчитаны для любых Ь. Рассмотрим пример: с,=18, а, =-15, р,=1,2, сг =- 14 аг= 12 р, =1,100, с,=4, ал =4, ра = 1, сг = 8, а,=7, рг=1 142 с,=О, а,=1, рг=-О. Здесь 16 Р1 Г5 Р1 — Рг — 14 ° 15 = 540. Г5 12 Оценка 540 является достаточной, но пе являетсл необходимой.
Это значит, что для двух величин Ь и Ь', где Ь ) Ь'. ) 540 и Ь' = = Ь (той а,), оптимальные целочислепньге решения будут почти одинаковыми, отличаясь лишь тегг, что в оптимальном решении для величин Ь часть Ь вЂ” Ь' общего веса будет приходиться на первый предмет. Будем вычислять 0 (Ь) для последовательных значений Ь = О, 1, 2,.... Тогда можно убедиться, что 0 (Ь) является периодической функцией, а именно, 9 (Ь) = 0 (Ь + 15) при Ь ) ) 20 (см. табл. 18.3).
Таблица 18.З и х хах игяй а е й а. и а а л аи" > и ох Полностью заполнить табл. 18.3 предоставляется читателю. Изобразим теперь строки 15 — 29 табл. 18.3 в виде табл. 18.4. В третьем столбце указаны целочисленные решения х;, в четвер- 18,1, ЗАДАЧА О РЮКЗАКК 377 Таблица 1а.б том столбце — периодические решения (т. е. значения х7, определяющие 8Р„(Ь (шо1) а1))) соответственно при 6 = 15, 16,... ..., 29.
Посмотрим, как табл. 18.4 мол1ет быть использована для нахождения 8р„(6) при всех Ь. Возьмем Ь = 43; очевидно, 43 =— = 13 (шо11 15). В 13-й строке табл. 18.4 имеется периодическое решение х, = 1, х, = 1; это означает, что при Ь = 13 целочисленное решение следующее: х, = 2, х, = 1, х, = 1 общим весом 2 х 15+ 1 х 12 + 1 'х 1 = 43. Возьмем теперь 6 = 25; очевидно, 25 = 10 (шод 15). В 10-й строке имеется целочисленное решение х, =- 2, х, = 1 общим весом 25; это значит, что при 6 = = 25 дол1кно быть х1 = О, или, другими словами, периодическое решение не применимо.
Заметим, что при Ь = 40 (40 — 15 — = 25) имеем х, = 1, х, = 2, х, = 1. Можно перечислить все случаи, когда периодическое решение применимо и когда оно не применимо (последние случаи в приводимой ниже таблице обозначены нулями). ГЛАВА !9 О СООТНОШЕНИИ МЕЩДУ ЛИНЕЙНЫМ И ЦЕЛОЧИСЛЕННЫМ ПРОГРАММИРОВАНИЕМ ') 19.1.
Введение (Гомори [841, Кортанек и Ярослав 11331) В $13.1 для получения отсечения (9) мы использовали уравнение (4). При построении отсечения мы требовали, чтобы левая часть уравнения (4) была целой (необязательно неотрицательной), а переменные в правой части уравнения — целыми и неотрицательными.
Следовательно, в качестве производящей строки можно использовать любую целочисленную комбинацию уравнений, подобных (4), и отсечение Гомори можно получить из нее. Так как существует бесконечно много целочисленных комбинаций, то из данной таблицы можно получить бесконечно много производящих строк. Казалось бы, монено добавить сколь угодно много отсечений. Тем не менее будет показано, что имеет смысл добавлять только конечное число отсечений. Любое другов отсечение, полученное из таблицы, является следствием одного из них. Используем вектор-строку К, = (гс, гы..., г„) для обозначения производящей строки, вектор-стРоку Р; = (уо, у1 ° ° ' Л) для обозначения отсечения Гомори, а ф — для обозначения отображения, которое переводит производящую строку К; в отсечение Гомори Рь Тогда отображение ф переводит вектор-строку К; в ее дробнузо часть, причем ф (Кд = ф (Кг) если К, и Кг отличаются на вектор с целочисленными компонентами.
Далее, пусть К, и К, — любые две производящие строки и и — произвольное целое число. Тогда ф(К,+Кз)= — ф(К)+ф(К,)=Р,+Р, ф (пК,) — нф (К~) = нРм г) Многие иа результатов гл. 19 и 20 являются перефразировкой или непосредственным изложением статьи Гомори [86]. Читателю обязательно придется обращаться к подлиннику, так как многие теоремы и доказательства здесь пе приводятся. Автор благодарит Американское издательство К[лет[от и корпорацию 1ВМ за разрешение использовать в работе эти материалы. »9.1. Вввдкние 379 Таким образом, вектор-строки дробных частей, представляющих отсечения Гомори, образуют абелеву группу с операцией сложения по модулю 1.
Изучим подробно последовательность таблиц при решении задачи целочисленного программирования. Исходная таблица представляет собой целочисленную матрицу Аю следующая матрица А, получается яз А, с помощью алементарного преобразования. Элементарное преобразование эквивалентно умножению Аэ справа на матрицу В,', т. е. АэВ,,' = А,. В примере 1 из $ 13.2 Ао= 0 0 +1 0 — — 4 0 0 0 +1 0 0 О 0 +1 0 0 — 11/4 — 1/4 — 174 0 0 0 0 +1 В,~= В общем случае +1 +1 — '»» а атз — ~4гув ~гв В,'= где а„,— ведущий элемент. Это означает, что (»»е1Ва»=а„,.
Пусть а,' †стро из А, и а,' †стро из А,. Тогда а1й»» = а»» 0 — 4 0 — 1 0 0 0 0 10 3 11 13 3 О 0 0 +1 — 5 — 1 0 0 — 1 0 0 2 0 4' 0 3 1 Д8О ГЛ. 19. ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММЯРОВАНИЕ откуда а! = а,'В,. 9 Уравнение (1) можно рассматривать как систему уравнений, где неизвестными являются компоненты вектора а;'. По правилу Крамера каждая компонента вектора а,: есть отношение двух определителей, причем знаменателем является определитель матрицы В . Пусть ~ двС Вг ~ = )э. Тогда А9 равно абсолютной величине ведущего элемента, а каждан компонента вектора а,: имеет вид ЬЮ, где Ь вЂ” целое. Рассмотрим соотношепив между исходной матрицей Аг и текущей матрицей А1. Имеем АгВ,'В,'...
В!'! — — А1 Аг = А!В!-1В1-г ° ° ° Вг = А!В., или Так как деС В = деС В1, двС В1,... ЙеС В„то каждый алемент матрицы А! имеет вид ЬЮ, где Р теперь обозначает абсолютную величину произведения последовательно получающихся ведущих элементов, и Ь вЂ” целое. Если в циклическом алгоритме сохранять все отсечения Гомори, число строк будет возрастать.
Отсечения Гомори являются полностью целочисленными неравенствами, если они выражены черве исходные нвбааисные переменные. Таким образом, их можно представить как часть исходной полностью целочисленной матрицы Аг, а приведенные выше рассуждения мол!но использовать для доказательства следующей теоремы. Мы умножали полностью целочисленную матрицу А на обратную матрицу В ' и затем брали дробные части вектор-строк АВ-'. Рассмотрим теперь этот же процесс„но вместо дробных частей вектор-строк АВ ' будем использовать дробные части вектор- столбцов, В 'А.
Это связано с тем, что в нашем следующем алгоритме будут использоваться вектор-столбцы ф (В 'А) вместо вектор-строк ф (АВ '). Тем не менее результаты, полученные в одной формулировке, останутся справедливыми также и в другой. Рассмотрим вектор-столбцы с т компонентами. Эти вектор- столбцы с обычной операцией сложения образуют абелеву группу. Через В обозначим т-мерные векторы с действительными компонентами, а через Х соответственно т-мерныв векторы с целыми компонентами. Пусть (К) — абелева группа действительных Теоаемл 19.1.
Кагкдыйэлемент таблицы, используемой е циклическом алгоритме, имеет еид Ь)Р„где Ь вЂ” целое, а  — произведение ведущих элементов последовательно получаемых при переходе от исходной таблицы к данной. 19.1. ВВЕДЕНИЕ 381 т-мерных векторов, а (Х1) — абелева группа целочисленных ги-мерных векторов '). Ясно, что (Х) является подгруппой (К) и что любой т-мерный вектор с действительными компонентами принадлежит (В), а любой т-мерный вектор с целочисленными компонентами принадлежит (Х). Пусть А — (т Х и)-матрица с целочисленными вектор-столбцами А = 1а1,..., а„1. Череа (А) обозначим абелеву группу, порожденную вектор-столбцами из А. Любой вектор, который п можно пРедставить как ~', итаг с целыми ип бУдет пРинадлежать 1=! (А).
Воли матрица А содержит единичную матрицу размерности т Х т, то (А) = (Х); в общем случае (А) будет подгруппой группы (Х ). Предположим, что ранг матрицы А равен т, и что подматрица В = [Ь„..., Ь 1 матрицы А также имеет ранг т. Мы можем аналогично рассмотреть абелеву группу (В), порожденную вектор- столбцами В. Таким образом, элементы группы (В) имеют вид м и;Ь;, где и1 — целые. Так как А и В имеют одинаковый ранг, 1.=1 то любой вектор-столбец аг из А можно представить как линейную комбинацию векторов Ь, (1 = 1,..., ги) с действительными, но не обязательно целыми коэффициентами.
Таким образом, в общем случае (В) является подгруппой группы (А). Произведение В-'А, которое будет матрицей размерности т Х и, обозначим буквой а, а сивп9олом (а) обозначим абелеву группу, порожденную вектор-столбцами из а. Пусть К и а — дробные части соответственно В и а, так что В=К+Х, а=а+Хе). Тогда (а) — абелева группа, порожденная дробными частями вектор-столбцов из а с операцией сложения по модулю 1. Итак, используя В ', отобразим группу (А) в (а) и, далее, посредством р отобразим (а) в (а).
Символически это запишется так: (А) — ь (а) — ь (а). Легко проверить, что произведение отображений рВ ', 'которое переводит (А) в (а), является гомоморфизмом. г) Имеются в виду группы относительно операции обычного алгебранческого сложения векторов.— Прея. ред. з) В соотношеннн а = а + Е под Е понимается целочисленная матрица соответствующей размерности.— Прил. иерем 339 гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
