Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 45
Текст из файла (страница 45)
[111)). Итак, двойственный алгоритм решения задачи (5) состоит из двух частей. В основной части используется модифицированный двойственный симплекс-метод для решения следующей задачи: минимизировать з = су при условиях я,'у)1 Г=-1 ... 1' 1=1 ..., д(С) у-»О, гл. 11. МНОГОпгог[уктОВыв пОтОки где коэффициенты неравенств я'у » )1 получены либо из вспоьшгательной части, либо иа некоторых других соображений (например, из того факта, что сумма пропускных способностей дуг, инцидентных некоторому узлу, должна быть не меньше, чем сумма требований к потоку в этом узле).
После выполнения некоторого конечного числа итераций двойственного симплекс-метода находят вектор у, являющийся и прямо допустимым и двойственно допустимым по отношению к имеющемуся множеству неравенств; этот вектор у далее используется во вспомогательной части, Во вспомогательной части применяется модифицированный прямой симплекс-метод для решения аадачи (10), где у — вектор, (а> г и с. тт.12. полученный в основной части.
Чтобы получить столбец Р11, кото- « рый следует ввести в базис для увеличения 9, используется алгоритм решения многополюсной задачи о кратчайшем пути, прячем относительные оцепки, найденные с помощью модифицированного прямого симплекс-метода, служат длинами дуг. Если 9 ) 1 для всех периодов времени г = — 1,..., Т, то найденная сеть у является оптимальной.
Если после конечного числа итераций модифицированного симплекс-метода получится, что я«у = 8 < 1 и я«М,". ») ) 1 для всех г11, то неравенство я«у ) 1 следует ввести в основную часть. Это неравенство надо скорректировать перед тем, как его записывать в таблицу основной части. Рассмотрим численный пример. На рис. 11 12 (а) представлена нумерация дуг сети, на рис.
11.12 (б) заданы стоимости дуг единичной пропускной способности. Требования к потоку в течение двух периодов времени указаны на рис. 11.13. Основная масть. Вычисления начипа1отся с табл. Д1, в которой у = (О, О, О, О, 0). Воспольауемся неравенством у1+ у«+ у«») ) 8, получа1ощимся нз того факта, что сумма требований к потоку в уале 1«'1 в 1-й период времени равна 3 + 1 + 4 = 8. Это неравенство записано в ниягней строке таблицы. Ведущий элемент помечен «*». В результате итерации симплекс-метода получается м.з. сиптвз комму никлпионных свтви 255 табл. Д2 (за исключением пижней строки).
Затем добавим неравенство — 8 + уа + уз т уа — га » )О, полученное из рассмотрения потоковых требований в узле Ха. Чтобы выразить это неравенство через текущие небазисные переменные — см — уа, — уа, — у„— уа, ааменим верхнюю строку таблицы Д2 на (1, О, О, О, О, О), Р а с.
И.13. а затем умпожим матрицу, записанную в табл. Д2, слева на ( — 8, О, 1, 1, О, 1). Получается перавенство — 8 + уа + цз + уа = = са ) О, которое записывается в нижнюю строку табл. Д2. Таблица Д1 Таблица Д2 — у1 — Уа - Уа 'Уа Уа и1 Уа УЗ Уа У5 У~ У Уа У4 Уа У~ Уа Уа Уа Уа (Заметим, что в этом частном случае скорректированное неравенство имеет тот ике вид, что и исходное.
Не следует оя<идать, что так будет и в общем случае.) Продолжим вычисления. Рассмотрим потоковые требования к узлам Л'а и Л'~, что даст иаи неравенства уа + уа — 7 = оа ~) 0 и уа + у, — 7 = — и, )~ О. Затем получим табл. ДЗ (за исключением пил<ней строки). Теперь все неравепства, получаемые из рассмотрения потоковых требований к узлам, оказываются использованными. Чтобы получить дополнительные неравенства, следует перейти к вспомогательной части. Гл.
г!. многопРОдуктовыв пОтОки 256 таблица дз — У" — Гг Уг Уг Уз Уа Уг О 4 1 О О О 7 — 7/4 О О О О 1 1 О О О [/4 ΠΠΠΠΠΠ— 1/4 О О О 1 О -9«9 1>'4 Π— 5/4 1 В табл. Вй получается вектор относительных оценок [О, 1/9, 0 1/9, 1/9]. При таких оценках не существует вектора Х>, чтобы выполнялось я[>], '( 1', а яу = [О, 1/9, О, 1/9, 1/9] [7, О, 7, О, 1] = = О .= 1/9. Следовательно неравенство 1 1 . 1 ЯУ = — Уг — Уа — — Уг та 1 9 ' 9 ' 9 Вспомогательная часть начинается с использования табл. В1, где из слаб>лх переменных формируется исходный базис.
В самом начале все относительные оценки (которые появля>отея в верхней строке таблицы под слабыми переменными е„,, а,) равны нулю. Поэтому любая допустимая сеть может служить улучшающим столбцом. В частности, можно ваять сеть, обозначенную в табл. В1 через Хг. После выполнения итерации симплекс-метода получа>отся ненулевые относительные оценки, которые записыва>отся в верхней строке табл.
В2. Используя полученный вектор относительных оценок [О, 1/4, О, О, 0], мон;ио пойти самую дешевую сеть [7, О, 3, 4, 5], которая выражается через текущие переменные и записывается в крайнем правом столбце табл. В2. Далее выполпяк>тся следу>ощие итерации симплекс-метода и находятся еще две улуч>па>ощих О допустимых сети, которые представлены в табл. ВЗ и В4.
Заметим, что столбец Ц был скорректирован перед добавлением в табл. ВЗ. ГЛ. 1!. МНОГОПРОДУКТОВЫЕ ПОТОКИ 25з не выполняется при текущем значении у. Зто неравенство представляется в следующем виде: о, = — 9 + уз + уь + ув:=: О, затем оно корректируется и записывается в ни>вней строке табл. ДЗ. После выполнения итерации симплекс-метода получаем табл. Д4. Сеть [3, 4, 3, 4, 1[, представленная в табл. Д4, удовлетворяет потоковым требованиям в 1-и периоде. Это следует из вычислений, проведенных во вспомогательной части.
Теперь нужно проверить, удовлетворяет ли ова потоковым требованиям во 2-и периоде. Заметим, что зту сеть [3, 4, 3, 4, 1[, удовлетворяющую потоковым требованиям в 1-и периоде, легко можно было бы получить, если использовать стоимости, заданные па рис. 11.12 (б) и решать многополюспую задачу о кратчайшем пути. По для того, чтобы удовлетворить потоковым требованиям в течение нескольких периодов времени, требуется иметь табл. Д4, Используя вектор у = — [3, 4, 3, 4, 1[, теперь снова переходим к вспомогательной части и проводим вычисления, аналогичные представленпым в табл.
В1— В5. В результате получаем вектор и = [1/10, О, 1!О, О, 1/10) и 9 =. 7/10. Затем неравенство ов = — 10 + у1 + уз т уь Р:О корректируется и записывается в нилвнюю строку табл. Д4. Применяя итерацию симплекс-метода к табл. Д4, получаем табл. Д5. В табл. Д5 у = — [9!2, 5!2, 3, 4, 5!2[. Используя зтот вектор, снова переходим к вспомогательной части, проводим вычисления для 1-го и 2-го периода и получаем 9 ) 1.
Таким образом, у является оптимальной сетью общей стоимости.85,5, как показано в табл. Д5. Рассмотренный выше метод синтеза коммуникационной сети является двойственным, допустимая сеть получается только после окончания вычислений. Теперь мы перейдем к рассмотрению прямого метода. В начале вычислений требуется иметь исходный базис и прямо допустимую сеть.
Прямой метод состоит из следующих шагов. Ш а г 1. Выбрать столбец, который приводит к улучшению общей стоиьюсти. Ш а г 2. Выбрать строку как в прямом симплекс-методе. Ш а г 3. Вьтолнить преобразования Гаусса нрименительно к обратной матрице. Шаги 1 и 3 выполпя|отся обычпым образом. Шаг 2 является более трудным, поскольку здесь требуется найти, какое из огромного числа неравенств (9) будет нарушено первым, когда некоторая текущая пебазисная переменная возрастает от нуля. Н,З. СИНТЕЗ КОММУНИКАЦИОННЫХ СЕТКИ 259 Положим, что ур — некоторая прямо допустимая сеть, у,— столбец, который улучшит двойственную недопустимость, если его ввести в бааис.
Если значение 1-й небазксной переменной увеличивается от 9 до О, то текущее значение уз увеличивается па 9у,. Выбор строки заключается в нахождении максимального значения 0 и неравенства (9), таких, что: а) Ух .. О~зххУ~ УДовлетвоРЯет всем неРазенствам (9) Дла 0<0<Ос„х,' б) я~ (ух ';-Оуе 1) (9 дчя всех 0) О,„. Для нахождения О и я для каждого момента времени г ре- 1 шается задача линейного программирования: максимизировать О при условиях у.+Оу,>Х) 19[[, 1 1 < ~ А,'. Эта задача может быть переписана в следующем виде: макскмиаировать О при условиях — Оу1+ 2'.) Л1 ~~уо, ХХ';< — 1. (12) (нм Н0) [ум 1[= Овах Ф (13) н, кроме того, произведение (я„я',) на любой столбец в левой части (12) будет пе меньше коэффициента при перемекяой, соответствующей этому столбцу.
В частности, для 1-го столбца (л„я,) [ун 9) ~1. (14) Умножая (14) на 0 и вычитая из (13), получаем (Я 1 Я ) [!Ую 1[ ['О[Ум 9)[~~Омах О Заметим, прежде всего, что задача (12) всегда имеет ограниченный максимум, поскольку неограниченность 0 привела бы к существованию допустимой сети с отрицательной общей стоимостью. Решив задачу (12) для некоторого заданного 1, получим 0',„. Тогда относительные оценки строк (я,', я,') будут удовлетворять следующему условию: 260 гл. м. многошодхктовык потоки нли, по-другому, (пс ~ сса) 1уа + Оус — 11( Овсах 9.
(15) Если величина О~ах получена из (12), то сеть уа+ Оу, является с прямо. допустимой для О<040асах. Следователыю, если величина Овсах найдена из (12) при рассмотрении потоковых требовас ний в 8-м периоде, то максимальное значение О, конечно, равно с Осаах = ш сп 9саах с С другой стороны, пам нужно показать, что существует вектор относительных оценок и, такой, что и [уз + Оус, — 11( О прн 0 ) О, . Так как мы выяспилн в (7)„что для всех допустимых сетей и [Мс, — 11 » )О, то зто означает, что и [у, — 11 ) О является связываюсцнм неравенством для текущего решения, Из (15) видно, что (и„', лас) — искомый вектор относительных оценок, так как правая часть (15) отрицательна при О ) О „. В прямом методе ренсения задачи синтеза сети вычисления состоят из двух частей.
В основной части используется модифицированная прямая таблица, в которую ааписываются неравенства, получаемые во вспомогательной часта. Вспомогательная часть решает задачу (12), где у, и ус задасотся основной частью, В результате вычислений во вспомогательной части получаем 0 „и вектор относительных оценок пс. Если вспомогательная часть выполнена для всех периодов времени, то получаем 9 а, и вектор относительных оценок и. Затем связывающее неравенство и [у, — 11 ) О добавляется в основную часть. Алгоритм заканчивается, когда в основной части больше пет улучшающих столбцов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
