Исследование методов декомпозиции некоторых задач линейного и выпуклого программирования тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат физико-математических наук Медницкий, Юрий Владимирович

  • Медницкий, Юрий Владимирович
  • кандидат физико-математических науккандидат физико-математических наук
  • 1999, Москва
  • Специальность ВАК РФ05.13.16
  • Количество страниц 126
Медницкий, Юрий Владимирович. Исследование методов декомпозиции некоторых задач линейного и выпуклого программирования: дис. кандидат физико-математических наук: 05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук). Москва. 1999. 126 с.

Оглавление диссертации кандидат физико-математических наук Медницкий, Юрий Владимирович

Структура и объем: работы. Диссертация: состоит из введе. ния, трех глав, заключения и списка литературы. Содержание ра. боты изложено на 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), приведенные дальности

Ь}?т = перемещения продуктов (где .дальность, а щп. коэффициент приведения) и ограничения на объемы грузооборота по видам: средств перевозок кт. Пусть, кроме того, Щ.верхние границы объемов перевалок, <;],(].заданные объемы вывоза и ввоза продукта % для: пункта 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. Кроме того, переменные x\smf т Е Мц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 с перевалкой в некотором промежуточном пунк. те к„ Однако условиями (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, то в указанное решение войдут и перевозки: x\kmi > 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.С^™2, (1.25) в качестве следствия из указанных равенств.

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

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

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

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

Доказательство', Если х) > 0 и х\х), > 0, то должно выпол. питься равенство с-8™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¡ < v¡ несовместно с равенствам:!: w¡ = 1 и v\ .1, то должно вы. подняться одно из неравенств v¡ > -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 ф к должно быть €гк(?1 = 0, а так как е\ > 0, то $1 = 0. Аналогично е) = 0, поскольку £'\$l = 0, а ¿¡'j, > 0. Неравенство же е\ < тшЩ, (£} следует из (1.15) и (1.16) так как по лемме 1.6 х\ -.0. □

Рекомендованный список диссертаций по специальности «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», 05.13.16 шифр ВАК

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Медницкий, Юрий Владимирович

Заключение.

1. Построенная в главе 1 задала производственно.территориально. го комплекса (ПТЗ) является обобщением и, в частности, допус. кает существование решений таких типов, которые в известных постановках многопродуктовой производственно.транспортной задачи отсутствуют.

2. В. прикладном: аспекте эта за,дача, однако, информационно не за. мкнута, а ее оптимальные решения не адэкватны: оптимальным решениям задач экономических: систем:.

3. Классический метод двухуровневой декомпозиции неэффективен при: разложении задачи; ПТЗ как в пространстве исходных, так и двойственных переменных, поскольку в обоих случаях: создается небольшое количество блоков большой размерности (сравнимых с исходной задачей).

4. Метод одновременного разложения задачи по связующим переменным и ограничениям может быть эффективным средством: декомпозиции задал большой размерности, причем: не только линейного, но и, по крайней: мере, выпуклого программирования.

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

6. На основе этого метода могут создаваться корректные (декомпозиционные) процессы: согласования оптимальных решений, на первый взгляд, не связанных задач.

7. Метод совместим с классическими приемами решения: выпуклых задач, использующими для: приближения к оптимальным элементам выпуклых множеств системы отсекающих: полупространств, выпуклых комбинаций и: лучей. Поскольку оба представления ис. пользуются одновременно, то он может оказаться весьма эффек. тивным средством решения задач большой размерности.

Список литературы диссертационного исследования кандидат физико-математических наук Медницкий, Юрий Владимирович, 1999 год

1. А.вербах И.Л., Цурков В.И. Оптимизация в блочных задачахс целочисленными переменными.М.: Наука, 1995. 226 с.2j Алексеев В.М., Тихомиров В.М., Фпм ип С.В. Оптимальноеуправление.М.: Наука, 1979. 429 с.

2. Гейл Д. Замкнутая линейная модель производства. // Линейныенеравенства и смежные вопросы.М.: Изд.во иностр. лит,, 1959,с. 382.396.

3. Гейл Д. Теория линейных экономических моделей.М.: Изд.воиностр. лит,, 1963,.418 с.

4. Голдман А.Дж., Таккер А.У. Теория линейного программиро.вания. // Линейные неравенства, и смежные вопросы,.М.: Изд.во иностр. лит,, .1959, с. 172 207.

5. Гранберг А.Г. Применение межотраслевых моделей в анализе территориальных пропорций народного хозяйства, // Межотра.елевые балансы в анализе территориальных пропорций СССР.

6. Новосибирск: Наука,, СО, 1975, с. 1.1.67,

7. Дшщиг Дж. Линейное программирование, его применения иобобщения. М.: Прогресс, 1966. 600 с.

8. Данциг Дж.Б., Вулф Ф. Алгоритм разложения для задал ли.нейного программирования.Математика, т. 8, N 1,1964, с. 151.160.

9. Данциг Дж.Б., Форд Л.Р., Фулкерсон Д.Р. Алгорифм дляодновременного решения прямой и двойственной задач линей.ного программирования. // Линейные неравенства и смежные вопросы.М.: Изд.во иностр. лит., 1959, с. 277.283.

10. Канторович Л.В. Математические методы организации произ.водства.И.: ЛГУ, 1939. 68 с.13| Кгшторович Л.В. Об одном: эффективном методе решения некоторых классов экстремальных проблем.ДАН СССР, 1940, 28,1. N 3.

11. К ан т о р о в и: ч Л. В. Э кономический р асче т н аилу чшег о исполь.зования ресурсов.Мы Изд.во АН СССР, 1959.452 с.

12. Канторович Л.В., Гавурин М.К. Применение математиче.ских методов в вопросах анализа грузопотоков. // Проблемы повышения эффективности работы автотранспорта.М.: Изд.во АН СССР, 1949.

13. Кан т о р о в и: ч Л. 1:1», М акар о в В .Л, Оптимальные модели пер.спективного планирования. // Применение математики в эконо.мических исследованиях, т. III, М.: "Мысль", 1965.

14. Лэсдон Л.С. Оптимизация больших систем.М.: Наука, 1975,4:31 С.

15. Л юсов .А.,11, Цементная промышленность СССР.М.: Строй:.издат, 1974. 159 с.

16. Макаров В.Л., Рубинов А.М. Математическая теория эконо.мической динамики и равновесия,.М.: Наука, 1973. 335 с.

17. M е }\ «ш m h и и IÍ .1! \, I! ï у i о | ) и 11 11 II 11 II роизводственно.транспорт.ные задали большом ра шерпсм i и и: решение их на ЭВМ.

18. М,: Статистика, 1978. 95 с.

19. Медницкий Н.Г., Медницкий Ю.В. О двух новых программ.пых системах для: формирования и: анализа задал: линейного про.граммирования. // Экономика и мат. методы. 1994, т. 30, вып. 3, с. 142.154.

20. Медницкий В.Г., Медницкий: 1С),В., Коми ниш i i M., IKo ролев В.Г. Формы динамического равновесия замкнутой эконо.мики. // Экономика и матем. методы, 1998, т. 34, вып. 2, с. 105-.119.

21. Медницкий К) .В. О параллельном использовании метода де.композиции: в паре двойственных задал: линейного программирования. // Известия АН. Теория и системы управления. 1998, N 1, с. 107.112.

22. Медницкий 1С) .В. О декомпозиции задали: линейного програм.мирования со связующими ограничениями и переменными. // Из.вестия АН. Теория и: системы управления. 1998, N 4, с. 134.140.

23. Медницкий Ю.Н., Мрцнипьии I! 1 Об одной схеме деком.позиции. // В трудах: международного симпозиума "Экономико.математические методы в АПК: История и: перспективы" (Россия, г. Москва, 13.15 апреля 1999 г.)

24. Мир онов А. А., Цурков В,И, Минимакс в транспортных: задачах.М.: Наука,, 1997. 399 с.

25. Моисеев IIJBIL Элементы теории оптимальных систем:.М.: Наука, 1975. 526 с.31. .1:1 икай:до X, Выпуклые структуры и математическая экономи.ка.Ми Мир, 1972. 517 с.

26. Оре С. Теория графов.М.: Наука, 1.980. 336 с.33| Осипов В. Т. Применение ЭВМ. не железных дорогах.М.: Наука, 1984. 264 с,

27. По спело в Г.С., Hi ii Hi,Л!,, Салодол B.M., Шафран.ский 11,111,,, )р/шх А И". Проблемы программно.целевого пла.нирования и управления.М.: Наука, 1981. 461. с.

28. По спело в Г, С., Ириков В. А. Программно.целевое пл анирова.ние и управление.М.: Сов. радио, 1976. 440 с.

29. Реинфельд 13,, Фогель У. Математическое программирование.М.: Изд.во иностр. лит., 1960. 302 с.37| Рокафеллар Р. Выпуклый анализ.М.: Мир, 1973. 469 с.38. 1.1урков НИ, Декомпозиция в задачах большой размерности.м:.: Наука, 1981. 351 с.

30. Цурков В.И. Динамические задачи большой размерности.1. Мл: Наука, 1988. 287 с.

31. Цурков В.И., Литии и имев И «С, Декомпозиция в динамиче.ских задачах с перекрестными связями. М.: Наука, 1994. .176 с.

32. Юдин Д.Б., Голыптейн Е.Г. Задачи и методы линейного программирования.М.: Изд.во "Сов, радио", 1961. 491 с.

33. Янг Л. Лекции по вариационному исчислению и теории опта.мального управления.М.: Мир, 1974. 488 с.

34. Dan/ig (3JL, Wolfe P. Decomposition principle for linear pro.grams. // Oper. Res. 1960, v. 8, N 1, p. 101.112.

35. Geoffrion A.M. Relaxation and the dual method in mathematicalprogramming. // Working Paper 135.Western Management Scl.ence Institute.University of California at Los Angeles, 1968.

36. Hichcock FX. The distribution of a product from several soures to numerous localities. J. Math. Phys, v. 20, N 2, 1941.

37. Koopmans T.G. Optimum utilization of the transportation sys.terns. Econometrica, v. 17, 1940.

38. Mednitski Yu.V. On decomposition of the linear programming problem with binding consiraints and variables. // В трудах 2-ой

39. Московской международной конференции по исследованию one.раций (Россия, г. Москва, 17.20 ноября 1998 г.)

Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.