Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 21
Текст из файла (страница 21)
Необходимость умножения на В ' вытекает из того, что вектор (и, я) был получен умножением матрицы условий задачи (5) на В '. Поскольку вектор [1ц, е1) входит в условия задачи (5), он должен быть умножен слева па матрицу В ', такх1, как все остальные вектор-столбцы условий (5). Операция умножения вектор-столбца 1) хц — оптимальное решение задачи (6).
т.2. Пгимкг исходной таблицы на обращение текущего базиса называется коррекцией. Если после решения р линейных программ |вш (с, — яЬ7) хы — я, > 0 (для ) = 1, ..., р), то текущее решение является оптимальным. 7.2. Пример Рассмотрим линейную программу: минимизировать х1 + Зхг + 5х]+ Ох~ +х] при условиях 1 ... о х~+ 4хз+ — х' —,' 2х'+ — х" = 7, 2х1+ Зхз .=5, 5х1 -,' хз =6, Зх,'-:,-4х,'+ Зх,'=12, х„хю х,', х,', х,'.:О.
Заметим, что в задаче (1) 1.,=(1, 4), 1е=( —, 2, — ), [п=1чхя —— (1, з) [1, 1) =5, ся = (1, 8) [1, 1) = 9, ]1з — — Ьзх1з — — ('/„2, а~4) [4, О, 0]=1, с,з=(5, 6, 1)[4, О, 0]=20, 4з = 1чхзз = ('/„2, '1,) [О, 3, 0) = 6, ез, = (5, 6, 1) [О, 3, 0] = 18. Следовательно, задача приобретает вид: минимизировать 9Лп -'; 20Л„-,'— 18Лзз+ 9 т. хт Ь,=7, Ь,=[5, 6], Ьз=12, А,=] 5 11, Аз=-[3, 4, 3), с,=(1, 8), се=(5, 6, 1). Выпуклое множество Я~ состоит лишь из одной точки х,1 = = [1, 1). Выпуклое множество Бз — треугольник с вершинами х,а= [4, О, 0), х„=[0, 3, 0], хзз — — [О, О, 4).
Для того чтобы получить исходное базисное решение, необходимо т, + р =- 1 + 2 векторов. Позтому предположим, что в качестве начальпых выбираются векторы х„, х,ю хаа (заметим, что хзз акать не обязательно): гл. т. Пгинцин дккомпознцпк 18О при условиях 5)и11л! Ли, !!422 ° .= 7, 111 -1, ~12 ! Х22-г... --1. (2) Задача (2) являотся канонической задачой лннойного программирования с поизвест~ымн Х;,. Если воспользоваться методом штрафа (см. '8 2.3), то с каждой искусственной переменной долл на быть связана достаточно большая положительная оценка. В нашем случае поступим иначе.
В табл. 7.1 искусственш!м переменным отвеча!от нулевые оценки, н какие бы на их месте нн появлялись в дальней!Пем значения относительных оценок, положительные Таблица гл аг г,, !11 г1г Хгг константы а г или отрицательные, онн пе будут влиять на окончание работы алгоритма. Точки в табл. 7.1 показывают, что существуют другно столбцы, не вкл!оченпые в таблицу.
Таблица 7.2 Л Лг константы 1 аа аа 1 г Х!1 агг агг После введения Х„, 112, 1.22 в базис получается табл. 7.2. Из нее видно, что (и, л„пг) -- ( — 2!5, 11, 20,4), 7 48 (с,— п1п)х1 —.-((1, 8) — ( 2 !)(1, 4))(хп хг) — — —.г, -- —,тт. Следовательно, длн Яг имеем: минимизировать 7, 48 Х! Хт 5 ' 5 151 7.2.
ПРПМЕГ при условиях 2х1.1 Зхг =,1, 5х1+ хг: — 6, х1, хг(0. Решением является: з', = — 1, хг.=- 1 при — 7 45 (с1 — я! 1)х1 — я1 — — 1 )- — ° 1 — 11=..0. 5 5 Подобным же ооразом для 82. (ег — и1-г) иг = ( (.1, 6, 1) — ( — — -) ( 4, 2, — ' ) ) (х'„хг', х'] .—.-- 1, (6 2»' х1' Соотвотствеппо липейпаи программа имеет вид: минимизировать 5,1х', —:-6.8х,' —, 1,5х', при условиях Зх',— , '4хг'4 Зх,'=12, Решениом является: х,'.=О, х,' — О, х,'=.-4; 102 (сг — и1~)иг — из=э,1 О. 6,8 О+1,;1 4 — — = = 6 — 20,4 = — 14,4 О, /1 51 (м=!'гхзг — ' ( 1, 2, 4 ) (О, О, 41] = 5. Таким образом, Пгг, ег] =-!5, О, 1].
Пре кде чем добавить этот вектор в табл. 7.2, необходимо умножить его на обращение текущего базиса В '. 0 ! Полученный вектор вместо с его относительпой оценкой ( — 14,4) записывается в табл. 7.2. Результатом является табл. 7.3.
После итерации получается оптимальная табл. 7.4 с 1 211 1 ~ 212 '1 622 4 гл. г. пгинцип дккомпознции 132 Таблица 1.3 1 х» х„х., 2» ьгг 222 ггзг кскстакты Хг! гг !2 гггг Таблица 7.4 1 х" 1 ха ха л» гг!г лгг гзг г з л 2!г лзг Итак. х, = 2» [1, 1[ = [1, 1), 4[ ~ [+ Для проверки убедимся, что ограничения (1) удовлетворяются и 2 = 1 + 8.1 + 5 3 + 6.0 + 1 1 =- 25. Упражнения Решить задачу: минимизировать х = 5Х, + хз + хз + бх,' + 2х,,' -!- х, прн условиях х! — х2+ хз+ х!.[-хг+хз= б, х!+ хз Х2+ 2'хз =- 3, 2х', [-х,'-рх,.'=4, х!)О, х,')О (! =1, 2, 3) при помощи алгоритма декомпозиции Данцига — Вулфа. Использовать )г» (соответствующее х! — — 1, хг —— 3) и 2!2, 222 (соответствующие х', = 2, х', = 4) в качестве исходных базисных переменпыл.
дополнение Дополнение В этой главе большая задача линейного программнровапия, показанная на рис. 7.1 (имеющая большое число строк и столбцов), преобразовывалась в задачу линейного программирования, показанную па рис. 7.2, с большим числом столбцов. Для того чтобы решить задачу, показанную ла рис. 7.2, не требуется выписывать все столбцы. Мы используем несколько столбцов в качестве начального базиса и выписываем столбец, который должен войти в базис. Задача определения «наилучшего» столбца есть другая задача линейного программирования. В общем случае большая задача линейного программирования решается разбиением задачи на две части (главную часть и вспо»югательпую часть).
Главной частью является задача линейного програ»ышровапня, содершащая много строк или столбцов. Однако нн строки, пн столбцы не выписываются полностью. Вместо этого во всномогатольной части решается другая оптимизационная задача, которая дает «наилучшую» строку или столбец для главной части. В гл. 11 приведено много примеров, укладывающихся в эту схему. Читатель мол«ет также прочитать Гомори [82). ГЛАВА 8 МАКСИМАЛЬНЫЙ ПОТОК 8.1. Введение В этой главе мы будем изучать так пазываему>о теоршо ш>то~йиль>>«>. г "" "" * " " "* "' "' Ф Рву"">"" как задачи линейного программирования.
Но благодаря специальной структуре потоковых задач для пих было получено большое число эффектна>ььтх алгоритлк>в и пзя>цпых теорем, чем п объясняется особое внимание и этим задачам. В большинстве из нпх оптимальные реп>ения всегда целочиг сленпы, чего нельзя сказать о решении общей задачи линейного программирования. Введем сначала понятие сети. >=в Сеть состоит из множества узлов (называемых тагыке вершинами илн точками соединения) и множества 3 дуг (иазываемых также звепьямп, или ребрами), которые связывак>т р .вл.
эти узлы. В этой книге мы будем везде считать, что число узлов и дуг коне пю. Если дуга пмеот определенпу>о ориептаци>о (направление), то опа называется ориентирова>«ной, или иааравленной, дугой, в противном случае опа называется неориентироваииой' дугой. Для изображения узлов, ориентированных и пеориептироваппылх дуг пспользу>отса соответственно кружки, линии со стрелками и линии без стрелок. Па рпс.
8.1 взобра кена сеть из четырех узлов и шести орпептпрованпь>х дуг. Г>удем попользовать символ У> дли обозначения узла ь и символ Л» для обозпачоппя ориентированной дуги, ведущеи пз >У> в ь>:">. Гслп дуга между узла«и»т > и Ю; пеориептпровапная, то ее можно обозначать как символом Л», так и Лм.
Сеть называется евлглой, ес;и при ьпобом разбиении множества узлов сети па подмножества Х и Х найдется дуга Л»пли дуга Л>ы где у> Е Х и ь>'> Е Х. В этой книге всюду терман «сеты> обозначает связную сеть. Для удобства будем счььтать, что между эпобымп двумя узлами А>> и ь>"; имеется либо не больше одной ориептпро- в.г. ввкдкник гзз ванной дуги Л гг и одной ориентированной дуги Ап, либо только одна пеориеитировапиая дуга Аы. В болыпипстве случаев можно заменить одну пеориеитироваппую дугу двумя ориентированными. Л1ы исклгочаем возможность существования петель, т. е. дуг, ведущих пз некоторого узла в этот же узел.
Рассмотрим последовательность узлов и дуг сети: Л>г, Л,з, Л з А гз Л>з, Л з-г 1>-г, » Льг>о Таку>о последоватсльэость узлов и дуг иазовгн цепью пли ориенпгироеаннои цепью, ведущей из узла Л', в узел Л'з. Если гг'г — Л>„, то такая последовательность называется ориентиросанным циклом. Например, па рпс. 8.1 посгюдовательцость Л'„Л „, Л'„А „, Л>г является цепью, водущей из >Уь в Л>г; последовательность >У„Л>з, Лз, Лез Лгз Лзг Л з Л з,, >гг'> также яв.гяется цепью, ведущей из Л', и Лгг. Последовательность Л',, А.„, Л'„Л„, Л>, является циклом. Цепь пааывается простои', осли оиа ие содержит циклов.
В дальиейшем под термином «цепь» мы будем понимать иростую цепь. Пу>пем будем называть последовательность Лы Л,м Л>з, Лы, Л>з,..., >г>г г. Лз г >„Л>ю где Л>„Л>з,..., Л>„— узлы соти, и либо Л;,, либо Л;», г (при г =- 1, 2,..., 1« — 1) является дугой сети. Таким образом, путь отличается от цепи тем, что при движении ио пути от Л>г и Л>„гго>ггио пройти дугу соти и в направлении, противоположном ее ориеитации. Для пеориоитировапиых сетей понятии цепи и пути совпада>от. Например, па рис.
8.1 последовательность Лг„А»з, Л>з, Л„, Л>з, Лзг, Л>г является путем. Если дугу Л „за>>е>гить дугой А „, то этот путь превратится в цепь. Пока. как мы видим, определение сети совпадает с определением графа. Л1»> используем термин «сеть», так как с каждой дугой будет сопоставлено несколько чисел, тогда как в теории графов дуга;ппиь указывает па то, что узлы соединены. Пусть с каждой дугой Лы сопоставлено положительное число Ь», называемое >Рро>гусиной' тгособ>костью дуги. (11спользуется также термин «пропускная способность ребра».) Б соти выдели>от два специальных узла. Одпп пз иих называется источ>ьиноль и обозначается Лгз; другой называется спгоком и обозначается Л и Сеть можно рассматривать как водопроводную систему, в которой трубы соответствуьот дугам, источник воды соответствует источнику Л». сток воды — стоку Л>„а соединения меяьду трубами — остальным узлам сети.
Пропускная способность дуги здесь соответствует поперечному сечению трубьг, 11адо найти, какой максимальный поток воды можьго пропустить пз источника в сток в этой водопроводной системе. Чтобы сформулировать эту задачу более точно, введем сначала понятие потока в сета. Потоком пз источника Л> в стог« Л>г в сети называется множество неотрицательных чисел хЫ (кагкдое из которых поставлено в соответствие некоторой дуге сети), если эти ГЛ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
