Диссертация (1137390), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

[1]) состоит в том, что мно­Π() компактно в топологии слабой сходимости. Очевидно, что Π ={ : | = 0} замкнуто в такой топологии. Следовательно, множество Π ()жествокомпактно. Чтобы получить утверждение о существовании, нам нужно дока­зать непрерывность следующего функционала: →∫︀ℎ .К счастью, этотфакт напрямую следует из только что доказанной леммы.Следствие 1.5.

Функционал →вен для любой функции∫︀ℎ ,действующий изΠ()вRнепреры­ℎ ∈ ().Доказательство. Необходимо проверить, что для любой последовательности∫︀∫︀( ), такой что lim = для любого ∈ ∫︀∫︀верно, что limℎ = ℎ . Так как плотно в , существует последо­вательность → ℎ в ‖ · ‖ топологии, ∈ для любого ∈ N. Заметим,что → ℎ в ‖ · ‖ означает, что последовательность сходится к пределу рав­транспортных плановномерно на множестве всех транспортных планов.

Этот факт вместе с фактомо существовании пределовбольшихиlim∫︀ иlim∫︀ для любых достаточнопозволяет нам изменить порядок повторного перехода к преде­лу в следующем рассуждении:∫︁lim∫︁ℎ = lim lim∫︁ = lim lim∫︁ = lim =∫︁ℎ.Следствием компактности и непрерывности является следующий крите­рий существования.Предложение 1.6. Задача Монжа—Канторовича с дополнительными линей­ными ограничениями имеет решение, если и только если множество вероят­ностных распределенийΠ := { : | = 0}не пусто.Замечание 1.7.Заметим, что для рассматриваемой нами задачи ограниче­| = 0| = 0,ниеможно всегда заменить нагде— замыканиев‖ · ‖ -топологии. Действительно, из определения такой топологии очевидно,что | = 0 ⇐⇒ | = 0, а, значит, такая замена не влияет на решениеоптимизационной задачи.201.2Двойственность КанторовичаОдним из важнейших достижений Леонида Канторовича в теории линей­ного программирования было открытие им принципа двойственности. Так кактранспортная задача является примером бесконечномерной задачи линейнойоптимизации, этот принцип верен и здесь.

Стоит заметить, что в момент опуб­ликования Канторовичем своей работы [11] в 1940 г. теория двойственности длябесконечномерных задач еще только начинала свое развитие.В своей классической версии принцип гласит, что минимизация по множе­ству планов в транспортной задаче эквивалентна максимизации двойственногофункционала в специальном классе случайных величин:∫︁∫︁min∈Π(,)где ∈ 1 (),а∫︁(,) = sup +≤× ∈ 1 (). +,(1.7)Равенство оказывается верным при некоторыхпредположениях о функции стоимости(,).Ослаблению этих предположе­ний посвящено множество недавних работ различных авторов: [1], [25], [20],[56].

Обобщения данного результата также покрывают и случай мультимарги­нальной задачи.Мы сформулируем и докажем принцип двойственности для задачи с до­полнительными ограничениями. В основной версии нашей теоремы мы бу­дем предполагать принадлежность функции стоимости к классу(1 , . . . , ). (), :=Также будет сформулирована отдельная версия теоремы для огра­ниченной непрерывной функции стоимости. Доказательство результата исполь­зует теорему о минимаксе и утверждение о двойственности в классической за­даче. При этом для утверждения о классической двойственности в предполо­жении ∈ ()нами приведено самостоятельное доказательство, основанноена идеях C. Т.

Рачева и Л. Рюшендорфа [56], но не встречающееся ранее влитературе.211.2.1Двойственность для задачи Канторовича с ограничениямиСледующая теорема обобщает известное утверждение двойственностиКанторовича на случай дополнительных линейных ограничений.Теорема 1.8.1 ,..., , = 1 × · · · × — польские пространства, = (1 , . . . , ), ∈ ( ), — подпространство (), ∈ ().

ТогдаПусть∫︁inf = sup∈Πгде ∈ = +≤⨁︀=1 ( ), = ∫︁∑︁=1∑︀=1 ( ), ( ) , ∈ .Чтобы доказать эту теорему, нам потребуются некоторые дополнительныерезультаты. Во-первых, нам нужна подходящая версия теоремы двойственностиКанторовича для задачи без дополнительных ограничений:Теорема 1.9.1 ,..., , = 1 × · · · × = (1 , . . . , ), ∈ ( ), ∈ (). ТогдаПусть∫︁inf = sup∈Πгде ∈ = ≤ ∫︁∑︁=1— польские пространства, ( ) ,⨁︀=1 ( ).Доказательство похожей версии теоремы может быть найдено в [56] или[45].

Впараграфе 1.2.2мы приводим полное доказательство данной форму­лировки теоремы.В доказательстве будет использована следующая версия теоремы о мини­максе ([15], теорема 2.4.1).Теорема 1.10.Пусть — компактноевыпуклое подмножество хаусдорфавекторного топологического пространства,— выпуклое подмножество про­ℎ : × → R ∪ {+∞} полу­ , выпукла на , и вогнута наизвольного векторного пространства, функциянепрерывна по.для каждого фиксированногоТогдаmin sup ℎ(,) = sup min ℎ(,).∈ ∈∈ ∈22Теперь мы готовы доказать анонсированный результат.Доказательство теоремы двойственности 1.8. Неравенство∫︁ ≥ supinf∈Π +≤ ∫︁∑︁=1 является почти очевидным:∫︁inf∈Π∫︁ ≥ infsup( + ) =∈Π +≤= infsup ∫︁∑︁∈Π +≤=1 = sup ∫︁∑︁ . +≤ =1Докажем обратное неравенство.sup +≤ ∫︁∑︁ = supsup ∫︁∑︁∫︁ = sup inf∈ ∈Π∈ ∈, ≤(−)=1=1Здесь мы используем теорему 1.9 для функции стоимости( − ).( − ) ∈ ().По­кажем, что с помощью теоремы о минимаксе 1.10 впоследнем равенстве можнопоменять местами инфимум и супремум.

Действительно, положим = Π(),∫︀ = , ℎ(,) = ( − ) . Заметим, что ℎ(,) линеен по обоим аргументами непрерывен по для каждого фиксированного (это уже было доказано на­ми, см. следствие 1.5). Следовательно, все предположения теоремы выполнены,и мы получаем, что∫︁sup inf∈ ∈Π∫︁( − ) = inf sup∈Π ∈( − ).∫︀ ∈/ Π , то существует 1 ∈ такое, что 1 < 0.

Выбор = 1 ,∫︀ → +∞ показывает, что супремум sup∈ ( − ) равен +∞. Следова­Еслительно, можно заключить, что верно следующее:∫︁inf sup∈Π ∈∫︁( − ) = inf∈Π.И это в точности то, что было нам нужно для завершения доказательства.23Замечание 1.11.Заметим, что утверждение теоремы остается вернымдаже для случая пустого множестваΠ (), если мы положим inf(∅) = +∞.Используя в точности такое же рассуждение, докажем следующую версиютеоремы двойственности, сформулированную в терминах пространства непре­рывных ограниченных функций.Теорема 1.12. Пусть 1 ,..., , = 1 × · · · × — польские пространства, = (1 , . .

. , ), ∈ ( ), — подпространство∫︁inf∈Πгде ∈ = = sup +≤⨁︀=1 ( ), = ∫︁∑︁=1 ( ),Тогда ( ) .=1∑︀ (), ∈ (). ∈ .Единственное, что нужно заменить в представленном выше доказатель­стве — использовать вместо 1.9 версию классической теоремы двойственностиКанторовича для ограниченных непрерывных функций (например, теорему5.10 из [59]).1.2.2Двойственность в классической задаче КанторовичаЦель этого параграфа — доказать следующее утверждение:Теорема 1.13. Пусть 1 ,..., , = 1 × · · · × — польские пространства, = (1 , .

. . , ), ∈ ( ), ∈ ().∫︁inf∈Πгде ∈ = = sup ≤Тогда ∫︁∑︁=1 ( ) ,⨁︀=1 ( ).Мы будем использовать подход, близкий к предложенному C. Т. Рачевыми Л. Рюшендорфом в книге [56]. Альтернативные подходы к доказательствудвойственности в классической задаче Канторовича можно найти, например, вработах В. Л. Левина и А. А. Милютина [12], [13].24Доказательство.

Зададим линейный функционал ( ) = ∫︁∑︁ : →Rформулой .=1Он положителен и непрерывен относительно полунормы‖ · ‖ .Пусть (ℎ) = inf { ( ) : ≥ ℎ}— функционал, заданный на ().Можно доказать, чтосубаддитивен: (ℎ + ) = inf { ( ) : ≥ (ℎ + )} ≤ ∈≤ inf { ( ) : ≥ ℎ} + inf { ( ) : ≥ } = (ℎ) + (),так как для любого1 > ℎ, 2 > положительно однороден: для любоговерно, что1 + 2 > ℎ + .Также ∈ R+ (ℎ) = inf { ( ) : ≥ (ℎ)} = ∈= inf { ( ) : ≥ ℎ} = inf { ( ) : ≥ ℎ} = (ℎ).

∈Таким образом, ∈ — сублинейный функционал, к которому применима теоремаХана-Банаха.Также нам пригодится следующее свойство:для любого∈R ( · ℎ) ≥ · (ℎ).Действительно, (−ℎ) = inf { ( ) : ≥ −ℎ} = inf { ( ) : − ≤ ℎ} = ∈ ∈= inf { (− ) : ≤ ℎ} = − sup { ( ) : ≤ ℎ} ≥ ∈ ∈≥ − inf { ( ) : ≥ ℎ} = − (ℎ). ∈25Комбинируя этот результат с положительной однородностью, мы получаем же­лаемое неравенство. Соотношение− sup{ ( ) : ≤ ℎ} ≥ − inf { ( ) : ≥ ℎ} ∈ ∈следует из положительности функционала.Так как он положителен, он со­{ : ≤ ℎ} при отоб­множества { : ≥ ℎ}храняет порядок.

Следовательно, любой элемент образаражениине превосходит любой из элементов образапри том же отображении. Получаем, чтоsup{ ( ) : ≤ ℎ} ≤ inf { ( ) : ≥ ℎ}. ∈ ∈Это ровно то, что нам нужно с точностью до умножения на ≤−1. , мы можем применить теорему Хана­Банаха о продолжении, чтобы продолжить функционал с подпространства на все пространство ().

Обозначим такое продолжение через и докажем,что свойство ≤ влечет положительность .Предположим, что — не положительный функционал. Следовательносуществует функция ℎ ∈ , такая, что ℎ ≥ 0 и (ℎ) < 0. Но это приводит кИспользуя тот факт, чтонапротиворечию:0 < (−ℎ) ≤ (−ℎ) = inf { ( ) : ≥ −ℎ} ≤ 0.Определим еще один линейный оператор: : { + : ∈ R, ∈ } → R, : | = и совпадал с в точке −. Излинейности и свойств следует, что (·) = · () ≤ (·). Получаем, что ≤ всюду на его области определения, и, используя теорему Хана-Банаха,можно продолжить до линейного функционала : () → R, так что | = , (−) = (−), ≤ .так, чтобы он совпадал снаИз построения линейных продолжений следует, чтоsup (−) ≤ inf { ( ) : ≥ −} , ∈26где супремум (и инфимум) берутся по множеству всех возможных линейныхпродолжений, удовлетворяющих сформулированным выше условиям (а имен­линейность но: продолжающихи мажорируемыхпользуяи, ).Умножая неравенство на−1и ис­−1и ли­получаемinf () ≥ sup { ( ) : ≤ } .

Характеристики

Список файлов диссертации