Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 63
Текст из файла (страница 63)
17.2. Пример Проиллюстрируем этот алгоритм при помощи примера. Производящая строка здесь будет выбираться при помощи правила 2, изложенного в з 17.1. Рассмотрим, задачу целочисленного программирования: максимизировать хо = хг + хз + хз прк условиях — 4х, -Р 5хз+ 2хз«4, — 2хе+ 5хз ~«5, — Зх, — 2хз+ 2х,(6, 2хг — дхз «( 1, х, О, целые.
г) Имеется в виду, что полагая в (15) хв — — е)о, а остальные переменные равными нулю, мы получаем возможность сделать эффективный шаг прямого алгоритма н получить лучшео целочнслевное базисное решение,— Прим. род. хв хо Хв х5 хв х7 х1 Хз хз хь хв хв хв х7 х1 хг хз хт хв 25 хв хт Х2 хз хь Таб ца 17.8 ( — Х1 — Хг — ХЗ )' (х1) —.— хо (строка хт) хв хэ хв .+- ПрОИЗВОдя- хт щая строка х, 22 хз хт. а- Отсочение и 22 ведущая строка Таблица 17.8 1 — 2, — 22 — ХЗ 2' (21) =-' хо = (строка хв) Хв Х5 — Производя- хв щая строка, х7 х1 Хз хз хь л- Отсечение и 21 ведув1ая строка Таблица 17.10 ( — 2З вЂ” 25 — ХЗ "'( з) хо .=-(строка хв) хв х5 а- П роизводи- 'хв щая строка х7 х1 22 хз хт л- Отсечение и 25 ведущая строка Таблица 17.7 1 — 21 — Хз — ХЗ а (хз) = — (строка хв) — Производящая строка л- Отсечение и ведущая строка Таблица 17.9 ( — 25 — 22 — хз У (22)-- †.(строка хз) а- Производящая ст(юка «- Отсечение и ведущая строка Таблица 17.11 22 21 25 " (зз) =- =(строка хв, строка хз) — Проиаводящая строка л- Отсечение и ведущая строка 17.2.
ПРИМВР 359 Введя слабые переменные х„хв, х, и х, и Ь-строку, получим табл. 17.6. Константа 10 в Ь-строке определена грубой оценкой задачи. В табл. 17.6 Р„С г„, (7' = 2, 3), поэтому ведущим столбцом становится столбец под х1. Проверка отношения для х, дает 2/2. строка х, является единственной, для которой ( — "'е1 ( —, откуда %'(х1) = (строка хт) и выбор производящей строки однозначен.
Теперь, разделив строку хт на аи, = 2 и выписав целые части полученных коэффициентов, получим отсечение (ведущую строку). Новая базисная переменная г, в строке отсечения является слабой переменной, соответствующей этому отсечению. После преобразования получим табл.
17.7. Задача решается за 7 циклов, которые приведены в табл. 17.8 — 17.13, справа от которых выписаны множества Р" (г). Заметим, что в табл. 17.11 использование строки х, приводит к оптимальйой таблице. Мы выбираем другую строку, чтобы лучнто показать действие правила выбора производящей строки. В табл. 17.12 строка х, должна быть выбрана в качестве производящей, потому что опа входила в У (гв) для предыдущей таблицы, а строка х, нет.
Таблица 11пв 88 85 85 Таблица 8Т.И вЂ” 8 — 87 1'(81) — (строка хв, строка хв) хе :80 8 — Производящая строка хв хв 87 х1 Х2 Хв х1 хв х5 хв х1 Х2 хв 81. 8 — Отсеесяие и ведущая строка Таблица 17ЛЗ является оптимальной. Чтобы показать, как действует 'правило выбора производящей строки, предположим, что эта таблица неоптимальна и гв подлея'ит вводу в базис. Тогда по правилу выбора производящей строки требуется, чтобы строка хв была выбрана вновь.
Оптимальное решение: х1 = 3, хх = — 2, ха =. О, хо = 5. Г;!. 17. пгнмой А.!Го!'итз! Збе 17.3. Доказательство конечности р'= —" г6 7. аьз (18) Тогда ро р! (19) х) В этой главе из-за большого числа порекрсстных ссылон между параграфами мы будем придери<иваться единой нумерации формул для всей главы в отлично от того, как зто делалось в предыдущих главах. з) Смысл парамотров р; и йу раею!сняотся и обсуждается в 1 17.4.
Доказательство конечности прях!ого алгоритма состоит из двух частей, связанных необходимым порядком следования. Сначала используя правило выбора ведущего столбца, докажем, 'что г, лексикографически возрастает от таблицы к таблице. Затем при помощи этого результата и свойств, которыми обладают допустимые правила выбора производящей строки, покажем, что условие г, ) 0 (условие оптимальности) должно иметь место после конечного числа преобразований.
При доказательстве будет удобно пользоваться следующими определепиями. Пусть 1х+Ах„=ао, или, иначе, 1х — ', ~ а;х;=ао без описывает текущую таблицу; и пусть 1х+ Ахь, =аз (17) описывает таблицу, которая получается в результате одного преобразования, примененного к (16). Все элементы из (17) обозначаются черточкой наверху, например, ар — ведущий столбец из (17), тогда как а; — столбец из (16), соответствующий переменной г, которая выбирается для введения в базис в таблице (17). Пусть ,7 обозначает множество индексов строк а (16) и (17); ,7 содернгит всего п + 2 индексов.
Время от времени в контексте. где не но!нет возникнуть педоразуменне, будем употреблять А для краткого обозначения табл, (16) и А — для обозначения табл. (17). Определим ') м.З. докьзлткльство конкчпости Далее, определим бы = — Р;агу+ аьи 16,7, (20) и (21) бку Эти определения вместе с формулами преобразования таблиц в прямом алгоритме дают следусощие соотношения для всех у к У: аьуг, = ау — Лу, (22) (23) (24) аьуг, = ау — Лу, 1 г~+ уь гл аку Лу — = Ьа (25) Лу = агу (гу — гу) пРи аьу Ф О.
(26) Вывод формул (22), (23), (24), (25) и, (26) приводится в з 17.4, На основании этих соотношений формулируются следующие три . теоремы. Тковкмл 17.2. Если г, (10 и Лу ) 0 для всех у'(~е)'кУ и А— неоптимальная таблица, то существует такой индекс у к У, что аьу-> 0 и г- ( О. ' Ткоккиь 17.3. Если. г, - 0 и Ьу ) 0 для всех у (~ е) к/ и А неоптимальна, то Лу) 0 для всех у (чьв) кУ. Ткогвмл 17.4.
Если г, (О и Ау ) 0 для всех у(~е)'~У и А неоптимальна, то гу ) г,. Основной результат содержится в заклгочении теоремы 17.4. Чтобы доказать факт, формулируемый как условие этой теоремы,.- мы рассуждаем по индукции. Покажем что в первой таблице г, ( 0 и Ау ) 0 для всех у (-Фп) к У. Тогда условие теоремы 17.4 всегда верно для последующих таблиц на основании теорем 17.2 и 17.3.
362 ГЛ. 17. ПРЯМОЙ АЛГОРИТМ В первой таблице аьу — — 1 для всех у с У. Поэтому гу = ау для всех у ~,У и ау =- гу >- г, = а,. Подставляя в (22) соответствующие величины, получим Лу =- ау — а, >- О. Заметим, что г, = — а„( ау = гу для всех у (Фз) ~ У. Поэтому если г, >- О, то ау >- О для всех у с Х, что является условием оптимальности исходной таблицы. Следовательно, если исходная таблица неоптимальна, то г, ( О и Лу >- 0 для всех у' (~з) б У. Доклэлткльство 7коввмы 17.2. Справедливость теорев1ы 17,2 следует из (23). Предположим, что теорема неверна из-за того, что а1л 0 для всех у(~з)сУ (очевидно, что а1,„(0). тогда левая часть в (23) лексикографически неотрицательна при лк7бом у ПосколькУ Лу >- О дла У (4=з) С,У (и А,=О, в то вРемЯ как а,,~О), то иэ г, (О следует ау >-О для всех у Е У. Но если ау >-0 для всех у, то А оптимальна, а зто противоречит условию теоремы.
Отсюда следует, что при некотором у аь;)О и можно найти соответствук1щие а- и гт. л з' Пусть теперь теорема 17.2 неверна из-за того, что г; ) О. В первой части доказательства было показано, что если аьу(0 1 то ау ь- О. Если г;- ) О, то длЯ всех У с аьу)0 имеем =ау= вьу =- гу >- г; >- О. Следовательно, аьу -~ 0 влечет за собой ау >- О. Итак, в случае г, ) О всегда ау > О для у рУ. Последнее означает, что А — оптимальна, что опять-таки противоречит условию теоремы. ° Доклзлткльство ткогкмы 17.3. Справедливость теоремы 17.3 следует непосредственно из (25) и (26).
Если аьу(0, то условие Лу >- О можно вывести из (25), поскольку Лу ~~ О, Л; ~- О и а — ) О. Если аьу)0, то из (26) получаем Лу >- О, поскольку из ага)0 следует г„-( гу по правилу выбора столбца гу. ° Доклзлткльство тковвмы 17.4. дта теорема непосредственно выводится из (24). Действительно, г; >- г,„поскольку а —, ) 0 и Лу) О. Следствием из теоремы 17.2 является тот факт, что первая таблица, для которой либо нельзя определить гз, либо г, >- О, будет оптимальной. Чтобы показать, что такая таблица обязательно будет получена, докажем следующие две теоремы.
° Тковвмл 17.5. Ясли используется допустимое пров яо выбора производяиуей строки, то через конечное число преобразований !7.3. доклзлткльстВО конкчности ЗбЗ появится пара последовательно идущих таблиц, для которых а азв зв — <= ат а И Тковкмл 17.6. Если используется допустимое правило выбора производящей строки, то после конечного числа преобразований будет получена таблица, удовлетворяющая условиям оптимальности. Прежде чем доказывать эти теоремы, полезно ввести простое определенне и вывести из него несколько заключений. Пусть авз — число, стоящее в строке 2 и нулевом столбце в первой таблице последовательности стационарных циклов.
Тогда для любой таблицы из этой последовательности ам=а;з для всех 2Е,У. Будем говорить, что з-я компонента —" вектора г, находитем в границах, если ам<а э=а!о и ' аьв<~аьа=аьз. вз а. азв Заметим теперь, что если — <= и аь,<аьз, то — пахоаьв "ьв — аь авв сро дится в границах. Аналогично, если — ь= в ам<ам, то аьв аааз — находится в границах. агв атл Наконец, если аы и аьв всегда целые и а,,-»О (как того требует правило выбора ведущего столбца), и если — ")г (г— аВв некоторая константа) и — находится в границах, то сущестасв вует лишь конечное число всзмох'ных аначений отпошепия —. аы аь, Доклзлткльство ткогвмы 17.5.
Так как г, ( г;, вектор г, лексикографичсски увеличится в результате преобразования. Предазв положим, что первая компонента — остается постояпнои в неаьв ограниченной последовательности Я таблиц стационарных циклов, а —" увеличивается через конечное число преобразований' ). аьв ') Такое лредположенве не нарушает общности рассуждений, поскольку далее будет показано, что нл одна комлонентз вектора г, не может бесконечное число раз увелвчвватыэб в то время как предыдущие компоненты этого вектора остаются с постоянным значением. Поэтому несущественно, рассмотрим лв мы в качестве первой увеличивающейся компоненты 2-нв илл в-ю.
Гл. Рп пРямОЙ алгогитм Тогда компонента —, должна увеличиваться неограниченное аы аьв число раз. Пусть г — значение —" в первой таблице. Тогда г( ( —" для всех последующих таблиц. Пусть Я, — те таблицы - аь, ав аво из Я, для которых г( — '(=, а Яо — таблицы, в котора,х аьв аьо — ") — . Тогда Я=вв|)Я,. аь аьо Согласно требованию к правилу выбора производящей строки, условие а ь, ( а ь, должно выполниться через конечное число преобразований.
Тогда перебрав в 8в конечное число таблиц мы дойдем до таблицы, в которой а„/аь, окажется в границах через конечное число таблиц из 8в и подпоследовательность из Яв, для которой — ' находится в границах, будет неограниченной, если аьв 8, — неограниченная последовательность. Но зта неограниченная подпоследовательность (для которой —" находится в границах) аьв должна давать неограниченное число увеличений компопепты — ", аь поскольку †" увеличивается через конечное число преобразовааьв ний. Последнее невозмононо из-за того, что существует только конечное число значений †" , если †'" находится в границах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
