Исследование методов декомпозиции некоторых задач линейного и выпуклого программирования

Содержание

• Структура и объем: работы. Диссертация: состоит из введе. ния, трех глав, заключения и списка литературы. Содержание ра. боты изложено на 125 страницах

Список литературы содержит 47 наименований. В работе имеется 12 таблиц и: 4 рисунка. ii «1111,1 I (математи согласов н е к о1 г* > 11) ы х н м и и:» 1 с- 1 ш- I ии 1 ш 1 л л. ¡-а, 11 а ы я «ческой экономики и прещессах пия их ромюпий.

В зтои паве изучаются связи между некоторыми, в общем:.то, известными в математической экономике экстремальными: задачами, которые обычно рассматриваются как математические модели: саг мостоятелъных, существующих независимо друг от друга объектов, Однако по смыслу входящих в эти модели соотношений и переменных: они должны быть взаимосвязаны друг с другом, а при их объединении возникает математическая структура блочной задачи со связующими ограничениями и переменными, исследование которой и является од. ной: из целей настоящей работы, Таким: образом, отбор следующих ниже задач произведен, скорее, в соответствии с целями настоящего исследования и не претендует на полноту. Более полные и систематизированные их обзоры можно найти в фундаментальных монографиях [1, 18, 30, 34, 35, 38, 39, 40].

1 .1. Две классические задали,

Как известно, изучение задачи: линейного программирования началось с постановки и анализа двух экстремальных задан: о максимизации выпуска продукции: в комплекте |12, 1.4| к.> шах (1. ь?.Ума <�°> д >°> С1−2)

1 /./ *

У>-<1, «i> 0, (1.3)

0, Vj. Pi? y > 0, (1.4)

К =1, (1.5) ^Vj." min. (1.6) и: транспортной задачи-, посвященном оптимизации перевозок однородных грузов [1.3, 15, 45, 46] к ('ijXij.> min,

5.>.k, ^.]хч > fib (L7) i «Жу > 0.

Матрица, формирующая условия: задачи (1.7), имеет замечатель. ную особенность. каждый ее столбец содержит всего два ненуле. вых: элемента (+1,-1). Как известно |9, 13, 15, 17, 29, 41, 45, 46], именно это позволяет предложить для ее решения эффективные специализированные алгоритмы и порождает ряд весьма тонких свойств многогранника условий, которые являются: предметом новейших исследований [29]. Пара двойственных задач: (LI).(1.6) обладает почти аналогичным свойством, поскольку все ее переменные, кроме h, связаны: с двухкомпонентной структурой [1.7] столбца вида (.1.1,.а,-.,), причем исходя: из физического смысла а,-/ > 0. Но так как матрица содержит при переменной h один: столбец общего вида, то прямо использовать «хорошие» структурные особенности: остальной ее части для построения: какого. либо специализировалного алгоритма не удается.

Однако для решения задачи (1.1).(1.5) можно предложить такой ва. риант метода Данцига Форда Фулкерсона [9): устанавливая каким-либо образом: начальные значения: р-1 > 0 двойственных переменных в (1.2), можно доопределить их значения в (1.3), полагая: uj = maxp-ajj,

J i «' ' а затем: оценить сверху значение h в (1.1) по допустимому решению двойственной задачи, так как h < /го:

Далее, пусть I]1 = {г: v{- = р-Ч,?} и Jf = {j: и- = р-Ч?}- Рассмо. трим пару вспомогательных двойственных задач ® hoX°h

Ь > 0, > 0, e" > 0,

Wij.tj < 0,

Si < 1,

1,/i

1.8) (1.9)

1.10)

1.11) (1.12) (1.13)

Если минимум в (1.8) достигает нулевого значения, то, как легко видеть, решение, оптимальное в первой из указанной: пары двойственных задач, будет оптимальным и в (1.1) (1.5). 'Если же значение минимума окажется положительным, то, комбинируя решение tj двойственной в (1.8).(1.13) задачи с исходным набором: р] = р{-.I.ersj, v. v- .(Tij, можно, во. первых, в силу двойственных: условий: в

1.9).(1.12) получить при: некотором: W > 0 допустимое решение задачи (1.2)—(1.6), двойственной к (1.1).(1.5), с лучшей: оценкой: значения функционала (1.1) h < hi < ho и, во. вторых, добавить к мно. жеству пар (?, j), на котором: ищется оптимальное решение задачи:

1.8).(1.12), по крайней мере, один новый элемент. Иначе говоря, воз. никает монотонный (по Л, д, п = 0,1,.) процесс, во внутреннем: цикле которого решается: задача с двухкомпонентной структурой матрицы ограничений.

По.видимому, это наиболее простой приме]:), показывающий как осложняется' решение задачи: с блочной подструктурой ограничений при появлении хотя бы одной связующей переменной (ибо в структур. ном: отношении задачи: (1.1).(1.6) и: (1.7) только этим: и отличаются друг от друга). Кроме того, можно предположить, как: отмечалось также в [20, 38, 44], что при решении такого типа задач должны: быть эффективны методы, использующие одновременное движение в про. странствах исходных и двойственных переменных.

1.2. Обобщенная транспортная задача.

Как самостоятельная, прикладная задача модель (1.7) довольно бы. стро утратила актуальность, но в качестве элемента, формирующего блочные подструктуры, входила в ограничения весьма разнообразных задал: отраслевой оптимизации, построенных на использовании: модели многопродуктовой производственно-транспортной задали |23|,

Для: дальнейшего представляет интерес обобщенная версия: транс. портной задачи, разработанная для оптимизации: портфеля торговых контрактов [24], Суть обобщения заключается в том, что для органа:. зации перевозок некоторого набора продуктов используется: несколько видов транспорта с ограничениями на объемы грузооборота и с учетом: ряда дополнительных факторов, например, таких: как: затра. ты и потери при проведении не только транспортных, но и различных других операций, возникающих в этом процессе. Здесь, впрочем, нам' понадобится лишь упрощенная версия этой модели в форме близкой к той, как она представлена в [19].

Пусть множеством г Е I определен набор продуктов, перевозки которых между совокупностью пунктов 1, з € I/, I ф з некоторой рераспределение нагрузки между ними может происходить, вообще говоря, лишь в некоторых пунктах сети в результате специальных процессов, моделирующих происходящие в реальности операции по перевалке грузов. Соответственно, в набор исходных данных, кроме традиционно используемых в таких задачах коэффициентов транспортных затрат (на перемещение единицы продукта % из пункта I в пункт 5 видом: транспорта т), входят коэффициенты затрат с- (на перевалку единицы продукта г в пункте I), приведенные дальности

Ь}?т = перемещения продуктов (где .дальность, а щп. коэффициент приведения) и ограничения на объемы грузооборота по видам: средств перевозок кт. Пусть, кроме того, Щ. верхние границы объемов перевалок, &larr,(]. заданные объемы вывоза и ввоза продукта % для: пункта I), а переменными х8т и: х устанавливаются объемы перевозок и перевалок, которые должны: быть определены при решении оптимизационной задачи. Тогда модель. в форме канонической пары [5] двойственных: задач: линейного программирования. будет включать соотношения сети осуществляются различными видами транспорта т Е М. Пе

1.14)

1.15)

L-*i= С. <<> (i.i6) m WjI

P> 0. (1−17)

— E > -Л". Г > 0, (1.18)

L>o, (i.i9) a? j>0, vj.wj.Pi < c[, (1.20)

X>kr.v!ti-p!xi)-Er, mkm^max. (1.21)

При отбрасывании условий (LI8) эти задали распадаются на блоки по индексу г, а разделение по видам транспорта становится несущественным. В самом деле, зафиксируем некоторую тройку г, 1,5 и положим Mus. {т: c-3m. mine-*"1}. Тогда двойственные огранит нения (1.19), принимающие вид w. и- < c'"sm, выполняются строго для всех т? Мцй и, следовательно, по дополняющей нежесткости х) вт = 0. Кроме того, переменные xsmf т Е Мц8, входят в ограничения (1.15),(1.16) и функционал (1.14) только в составе суммы по ш, которая может быть заменена одной переменной Таким: образом, задача оказывается эквивалентна классической однопродуктовой транспортной задаче с одним: видом транспорта (1.7).

Ограничения по верхним границам объемов перевалки в (1.17) существенны так как с их помощью, полагая Щ = 0 или Щ > 0, можно отделить фиктивные перевалки от реальных, рассматривая, когда, это удобно, каждый пункт сети как пункт с перевалками всех проходящих через него продуктов. По своему содержательному смыслу коэффициенты затрат 48 т и с должны быть неотрицательны, а значит, как видно из (1.15).(1.20), двойственная задала имеет допустимое peine. ние v- = w = р = 0 для всех ?, 1- цт = 0 для всех т. Соответственно, по основной теореме линейного программирования [5, 411 обе задали (1.14).(1.21) имеют оптимальные решения тогда и только тогда, когда существует допустимое решение у первой из них. Предполагая существование этого решения и складывая (1.15) с (1.16) (для некото. рого фиксированного I -. 1, s = 1), а затем: суммируя по I (и переобозначая I на I), получаем систему равенств, аналогичную известному равенству [36, 41] для однопродуктовой транспортной задали (1.7)

Vi) ]((} - Ф = 0. (1.22) jmnnimnnflllm i

Выполнение условий (1.22), таким образом, необходимо (но недостаточно) для существования оптимальных решений. Заметим, что в силу содержательной интерпретации величин Q, (?, должны выполняться условия ??, 1 (J > 0, Q > 0, и если: выполнено: М: VI Q = 0, то VI Q = 0, в силу (1.22), а значит оптимальное решение для такого продукта будет тривиально нулевым. Подобные продукты, даже если: они встречаются: в какой-либо конкретной задаче, можно исключить из нее заранее и, соответственно, предположить, что ii|piiflf?jif-iiM[o 1.1. Наборы {??] > 0,(J > 0,1 (Е L}, определенные при фиксированном i и удовлетворяющие условиям (1.22) и: (1.23), будем: называть сбалансированными.

Конфигурация сети, показана на рис, I.I. I Пункт в ней, вообще говоря, представляется двумя: вершинами, В одной из них: (в дальней:. шем 1+) могут находиться источники, а в другой (обозначаемой I.). стоки продуктов (и те, и другие представлены на рис

1.1 фиктивны. ми точкой () и вспомогательной дугой, указывающей направление потока). Таким: образом, на языке теории: графов [32] рассматривав. мая в работе сеть перевозок. дихроматический, ориентированный граф!, с той особенностью', что в некоторых случаях возможна допол. нительная и тоже ориентированная связь от I. к 1+, а определенные на ней потоки: интерпретируются как объемы перевалок продуктов, следующих через пункт I. г «. > h .> ж1т:1. .* 5. .* С

I * <.L <.xL3 <.<. s

Pic. 1.1.

Поскольку поток, возникающий при перевалке, можно рассматри. вать как транзит через соответствующий пункт, то в допустимое решение наряду с перевозками: х > 0,1 ф s (единственно возможными в (1.7)) могут входить и некоторые комбинации потоков, например, х) к > 0, х > 0, х .0, где I, fe, s попарно различны. Из этих потоков можно составлять ориентированные маршруты с обходом: некото. рых совокупностей пунктов, входящих в соответствующие компоненты связности графа перевозок: продукта i. Заметим, однако, что если в указа! иной мемоп гарной цепочке mi ф m?, то она получает вполне естественную интерпретацию- продукт i доставляется из пункта I в пункт s в комбинированной перевозке двумя различными: видами транспорта т и: m2 с перевалкой в некотором промежуточном пунк. те к&bdquo- Однако условиями (1.15) и (1.16) очевидно не исключается: и возможность гщ =¦ «'?2 .ги, что выглядит не очень естественно, так как в этом: случае, по. видимому, следовало бы использовать прямую перевозку xllsm. Чтобы сформулировать соответствующее утвержде. ние, которое можно рассматривать как лемму о корректности модели, нам: понадобятся некоторые определения.

Определение 1.2. Сеть будем: называть полной если: для любых: i, m и попарно различных наличие в ней коммуникаций и г, s, т влечет существование коммуникации г, I, з, т.

Определение

1.3. Полную сеть будем называть эвклидовой если: име. ют место неравенства- <:-sm < cfm + c-sm, < 7^.f- 7^.

Определение

1.4. Величины

Ism. Jam. rrjniJs -I. J, J /1 o/h ci .Ci .1.Ц ('i.q.P0 (1.24J входящие в двойственные соотношения (1.19) и: (1.20), будем: называть коэффициентами полных: затрат (транспортных: и перевалки).

Имеет место следующее утверждение.

Лемма 1.1. Если в модели (1.14).(1.21) коэффициенты затрат с-, ¿¡-т и: приведенные дальности неотрицательны, сеть полна и эвклидова, а в оптимальное решение для: некоторых i, k таких, что с* > 0, входит перевалка, т. е. х > 0, то в указанное решение войдут и перевозки: xkmi > 0, х > 0. При этом: если I ф s, то mi ф т^ а если I = з, то перевалка продукта г в пункте I будет запрещена в следствие выполнения неравенства vj. w- < с-.

Доказательство', Если х > 0, то из (1.15) и (1.16) следует суще. ствование х) к > 0 и х > 0 для некоторых 1,5 и т^т2 (по обяза. тельно попарно различных). По дополняющей нежесткости соответ. ствующих пар неравенств в (1.20) и (1.19) получаем-, что vf.= cf, w’i .vf. С?""2, wf. vj = if™1 И

1″! .= .|. С? .I.С^&trade-2, (1.25) в качестве следствия из указанных равенств.

Пусть I ф 5 и предположим, что т — чщ, = т. Тогда в полной сети должна существовать прямая коммуникация (для перевозки продукта % видом: транспорта т из пункта I в пункт з), а значит из (1.19) с-8т > т*.г>{ = с1¹¹.Ь с?.I.с-ш'2 (иначе говоря, .1.с?"*3.I.с? < 0).

Однако, поскольку сеть эвклидова, то с'*™1.!.с^™2.сш' > 0, а по условию теоремы с-1 > 0 и значит, в силу полученного противоречия, гщ ф т2. Если же I = 5 и х > 0, то и-.и) = с-. Складывая: последнее равенство с (1.25), при любых Ш]., т2 получим:. .с-. .с = 0, что, опять. таки, не возможно в виду с]кг)Ч > 0, с1?3&trade-2 > 0, с- > 0 и: с| > 0. ?

Отметим сразу же одно довольно интересное следствие.

Следствие 1.1.1. Если в оптимальном решении для пунктов перевалки I ф з, некоторого % и прои-лшьныл тщ, т% выполняется ы: е| венство %}ш/81щ > 0, а с.I.с- > 0, (1.26) то хх = 0, т. е. при появлении встречных перевозок в оптимальное решение может войти перевалка продукта, но только в одном из двух возможных пунктов.

Доказательство', Если х) > 0 и хх), > 0, то должно выпол. питься равенство с-8&trade-1 4. с-.с-1"12 + с- = 0, несовместимое с (1.26), ибо

VI с[ > с[. Е]

Таким образом, показанным на рис

1.1 цикл, при выполнении уело. вия (1.26), невозможен в оптимальном: решении и: хотя: бы один: из четырех потоков будет нулевым.

При: решении задачи (1.14)-(1.20) традиционным методом декомпозиции Данцига. Вулфа 18, 20) исходные значения коэффициентов

4!>т ^ 0 в критерии блочной задачи заменяются суммами с|'т.{- г}тк1*т т. е. коэффициентами полных: затрат) и, поскольку г) т > 0, > 0, то и: трансформированные значения > 0 (это неравенство уже использовалось выше при доказательстве леммы: 1.1). Соответствен. но, блочные задачи опчимитации иеренозок одною продукта имеют оптимальные решения если, и только если, у каждой из них существует допустимое решение.

Определение

1.5. Такое допустимое решение в дальнейшем: будем называть допустимой: системой перевозок: продукта.

Вопрос о ее существовании, отнюдь, не тривиален и остаток настоящего раздела посвящен его анализу. Заметим, что в методе северо. западного угла |36|, с помощью которого доказывается достаточность условия (1.22) для существования допустимых: решений в (1.7), неявно содержится предположение о возможности перевозки продукта в произвольном объеме и от любого поставщика к любому потреби. телю, иначе говоря, что в матрице потоков ||ж?-?'|| нет запрещенных клеток или ограничений на величину потока. Если это условие не выполняется, т о д аже в о д нопр оду к товой т р анспор тной з ад аче и: для: сбалансированного набора (в данном: случае > допустимо. го решения: может не существовать. В связи с этим: введем: следующее определение.

Определение

1.6. Пункт I будем: называть реальным: поставщиком (потребителем) продукта % если выполняется неравенство > 0 ((] > 0) и фиктивным, когда $ = 0 ((] = 0).

Теорема

1.2. Пусть 8{.подмножества всех реальных поставщиков и потребителей продукта ?. Если (.1 = 0 и для каждой пары пунктов I? 5? $ существует коммуникация х8т хотя бы: одним: видом: транспорта т с неограниченной: пропускной способностью, то допустимая система перевозок продукта г существует в том и только в том: случае, когда набор сбалансирован.

Докачатрлы’тио. Достаточно использовать метод северо. западного угла. ?

Однако в модели (1,14).(1.20) любой пункт, в принципе, может быть одновременно и: поставщиком и потребителем: продукта,. В этом: случае Ц П 5, — ф 0 и вопрос о существовании допустимой системы пе. ревозок уже не имеет простого решения.

Определение 1.7. Сеть перевозок (продукта ?) будем: называть вполне связной, если для любой пары пунктов 1,8 & Ь (в том числе и для

I = 5) существует ориентированный: маршрут (I.|., з.), соединяющий вершины л. одним: видом: транспорта или: различными через неко. торую последовательность пунктов перевалки.

Для: вполне связной сети выполняются следующие утверждения.

Теорема I Л, Сеть (>удо, г шюлпе елшпой тогда, и только тогда, когда содержит конфигурацию, состоящую из двух пунктов перевалки I ф з, между которыми разрешены встречные перевозки (возможно различ. ными видами транспорта, как показано на рис. 1.1), и для каждого пункта несовпадающего с I и з, в нее входят один из маршрутов (&+,/.) или (&-+, з.) и один из маршрутов (1+, к.) или (5.^к.).

Докшштпльство. Во вполне связной сети- для любых попарно раз. личных к, I и: 5 должны существовать все четыре маршрута, указанных в формулировке теоремы. Однако если в сети нет пунктов перевалки, то она не будет вполне связной, так. как для: любого к запрещены маршруты вида Если же существует только один пункт перевалки (скажем 1'), то запрещенным окажется: маршрут (1+, I.). Таким образом, указанная на рис, 1.1 конфигурация из двух пунктов, перевалки- во вполне связной сети должна существовать.

Покажем теперь, что условия теоремы достаточны-. Рассмотрим произвольную пару пунктов к, п 6 где возможно к = п. По условию теоремы существует один из пары: маршрутов (к+)1.), (?+, 5.).

Пусть, для определенности, это будет (к+, 1.). Дополнив этот путь перевалкой: (I., 1+) и, если это необходимо, маршрутом (I.) с перевалкой (з., з+), а также воспользовавшись тем, что по условию теоре. мы должен сущестшшч, хотя бы один из путей (/,(, п) или (, Ч|), получим: искомый маршрут (к+^п.). ?

Те орем: а 1.4. Если сеть вполне связная, нагрузка сбалансирована, а пропускные способности перевалок и коммуникаций не ограничены, то допустимая: система перевозок ¿-го продукта существует,.

Доказательство. Для: доказательства можно сослаться на возмож. ность использования: метода северо. западного угла, но более наглядно такое рассуждение. Пусть I. произвольно выбранный фиксирован. ный пункт перевалки. Сначала для всех к ф I потоки fjk направляем: в вершину I. Остаток, который может образоваться: после удовле. творения: определенной в этой вершине потребности Q, передаем: в вершину i+, а затем: весь сформировавшийся в 1+ объем продукта распределяем между вершинами к. ф I., причем так, чтобы в каждой из них удовлетворялась потребность (]. Легко видеть, что неудовлетво. ренной при этом: может оказаться: лишь часть потребности: в верши. не I. и только при выполнении неравенства, А = Q.- Y, i] > 0* Но в этом случае, поскольку набор сбалансирован, в вершине 1+ возникает, причем: в том: же объеме А, нераспределенный остаток продукта и построение допустимого решения можно завершить, направляя поток, А по маршруту (?+, 5.), (л., fi+), (

Конечно при решении: задач (1,14).(1.21) на реальных: данных могут накладываться ограничения на пропускные способности: не только перевалок, но и: транспортных коммуникаций, в частности, запреты на использование некоторые из них, что обычно осуществляется удалением из-за, дали соответствующих переменных, а при канони. ческом представлении: модели:.в форме верхних: границ с нулевыми значениями, Поэтому в общем случае простых критериев существования допустимых систем перевозок продукта, по-видимому, нет. Покажем, что для произвольного и даже несбалансированного набора Ш > 0"{? М € L} этот вопрос можно решить в специально построенной задаче

I.ij).Kiiiiii, (1.27)

ЛшпшишиЛШГ

1,28) х1т ~ ха + ^ = С х) > 0,

А > о. Щ > о, > О, й' - V- < О, $.р < О,

4 < 1,

1>й.ш

1.29)

1.30)

1.31)

1.32)

1.33)

1.34) тах. (1.35)

Теорема 1. Б

Для любого набора {?} > 0,(] > 0,1 Е Ь} обе задали: в (1.27).(1.35) имеют оптимальные решения. Допустимая же система, перевозок продукта г существует тогда и только тогда, когда линейные формы (1.27) и (1.35) принимают на оптимальных решениях: соответствующих задач нулевое значение.

Доказательство. Для доказательства достаточно заметить, что условия (1.28).(1.34) в первой: из этих задач будут удовлетворяться е} = Ц, ?? = (! (1.36) и нулевых значениях всех остальных переменных. Значение линейной формы в (1.27) ограничены снизу нулем. Таким образом, оптимальное решение существует всегда. Однако если функционалы в обеих задачах: не достигают нулевого значения, то допустимой системна не. ревозок продукта очевидно не существует, ?

Оирс !, с дс шл 1 С Набор {(-{ > 0,(] > 0,1 (Е1} будем называть допу. стимым, если он позволяет построить допустимую систему перевозок.

Если оптимальное значение функционалов (1.27) и (1.35) для набора

I положительно, то этот набор отделяется от совокупности всех допустимых наборов > 0,0 > 0,1 (/,} нсранснстном

1−37) где и-', р берутся из оптимального решения (1.28).(1.Л5) для В самом деле, как легко видеть, (1.37) выполняется для любого допустимого набора. С другой стороны, для набора (?, в силу оптимальности решений в (1.27).(1.35), имеет место противоречащие

1.37) неравенство юМГ /иит 0[](1Р

В следующих ниже утверждениях описываются некоторые свойства оптимальных решений задач (1.27).(1.35).

Лемма 1.6. Для любых I ф 5, связанных коммуникацией (т.е. когда переменная х) ят определена, хотя: бы для одного значения т), выпол. няется условие ?$] = 0. Если же I. пункт перевалки и: > 0, то х] = 0 (а значит при: выполнении: условия ж] > 0 должно иметь место р = 0). Кроме того, если: набор' (?' сбалансирован, то имеет место равенство

Докпаптсльство. Равенство ^.е!) = 1Ж?.из которо. го для сбалансированных: наборов, в соответствии с (1.22), следует

1.38), легко получить, складывая (1.28) с (1.29) и суммируя по I. Если?? S? > 0 в некотором пункте перевалки, то v? =.1, a w = 1 по дополняющей нежесткости в (1.33) и (1.34). Но тогда в (1.32), поскольку р > 0, имеет место строгое неравенство.1 <1.1.р и по дополняющей нежесткости х). 0, а значит если, кроме того, Щ> 0, то по дополня. ющей нежесткости в (1.30) должно быть р = 0. Так как неравенство w? -1 или: w? < L По дополняющей нежесткости в (1.33) и: (1.34) е5%3 = 0. ?

Следствии" lili, Мели между некоторым! и пунктами I ф s такими, что ej 0, существует маршрут (l+1s.), то он проходит через некоторые пункты перевалки: несовпадающие с ?, s и, по крайней мере, для одного из них выполняется условие р. > 0.

Доказательство. По лемме 1.6 между вершинами не может быть прямой коммуникации, но поскольку маршрут (1+, з.) существу. ет, то он должен: проходить через какую. то совокупность ориентированных дуг графа перевозок продукта (Lhbi.), (к., &i+), (&i+, ?2.), (fcn+, s), все нечетные члены которой:.коммуникации, а четные. перевалки, т. е. в указанную' совокупность входит, по крайней мере, один пункт перевалки fe, но могут быть и: другие. Поскольку вдоль указанного маршрута должны выполняться двойственные уело. вия, то.1 = v? > w-1 > vfL. pf- > wf2.$ > щк2.$.pf2 >. >

П к: п к¦ П к w’i .: E Pi .1.E Pi, a значит Л p?3 > 2.? j:! j = l j = l

Определение

1.9. Модель (1.27).(1.35) будем называть дискретной, если между любыми: пунктами I ф s не существует коммуникации ни при: каком т.

Если модель дискретна, то все переменные вида из задачи исключены, а неравенства гу' <тем: самым, не входят в двойственные условия для: всех I', з. Оптимальными в этом случае, как легко видеть, будут решения: (1.36) и и)[ = 1, у = -1 в двойственной за,даче. Перевалки: с пропускным:! способностям!:: Щ> 0 при этом: могут быть разрешены в каждом пункте, но потоки через них = 0, а соответ. ственно, р ¦. 0.

Таким: образом, хотя все свойства оптимального решения, перечисленные в лемме 1.6, выполнены, задача из. за отсутствия комму. никаций вырождается, а в случае, когда какое. то их подмножество запрещено, граф перевозок продукта может оказаться (ориентировано) несвязным: (в обычном: смысле [32)). Модель, в некотором: смысле противоположная дискретной, вводится следующим определением.

Определение 1.10. IIпловом сеть компактной если: для каждого % и любых пунктов I ф л существует коммуникация х) хотя бы одним видом: трал спор та т.

Следствие 1.6.2. Если набор (},(] сбалансирован и недопустим, то на компактной сети существует единственный пункт перевалки к 6 I/, для которого е1к = > 0. Для: всех же остальных I ф к выполняются равенства е] = = 0. Кроме того, е1к < ш.1п{(|,(]}.

Доказательство. По лемме 1.6 неравенство > 0 не может иметь места в компактной сети: ни для каких пар I ф з, но так как набор сбалансирован: и недопустим, то выполняется равенство (1.38) и обе его части должны быть положительны. Другими словами, нера. венство е'

§ 1 > 0 выполняется для некоторых: к € I. Покажем, что указанное к единственно. Действительно, для: произвольного I ф к должно быть &euro-гк (?1 = 0, а так как е > 0, то $ 1 = 0. Аналогично е) = 0, поскольку ?'$l = 0, а ??'j, > 0. Неравенство же е < тшЩ, (?} следует из (1.15) и (1.16) так как по лемме 1.6 х -.0. ?