Е. Корныхин - Задачи по курсу Методы оптимизации (1125258), страница 3
Текст из файла (страница 3)
Для этого докажем следующие два утверждения:1. для любого x - решения задачи (2.1) конструктивным образом найдется(α, β) - решение задачи (2.4)2. для любого (α, β) - решения задачи (2.4) конструктивным образом найдется x - решение задачи (2.1)Доказательство второго утверждения очевидно: в качестве x достаточновзять разность β − α.Впрочем и доказать первое утверждение не составит для нас большого труда: достаточно научиться подбирать такие значения α и β, чтобыих разность β − α равнялась x, а сами эти вектора состояли бы из неотрицательных чисел.
То есть в качестве α можно взять любой вектор изнеотрицательных чисел, а тогда β = x + α и тоже должен состоять из неотрицательных чисел. Для удовлетворения этих условий можно, например,в качестве α взять |x| (то есть вектор, состоящий из модулей элементоввектора x, тогда в качестве β - взять x + |x|. При этом β будет состоятьиз неотрицательных чисел (по определению модуля) и на такой паре (α, β)будет достигаться максимум скалярного произведения, так как фактическиГлава 2. Основы линейного программирования18максимизируемое скалярное произведение зависит от β − α, а оно равноx, то есть такому вектору, на котором достигается максимум; а на тех парах (α, β), разность которых не равна x, максимум достигаться не будет,потому как не достигается максимум на их разности.2.5 задача №8Постановка задачи.
Доказать, что основная задача линейного программирования (ОЗЛП) эквивалентна решению некоторой системы линейных уравнений P z = q, причем z 0.Доказательство. В лекциях была доказана эквивалентность ОЗЛПmaxn (c, x) = (c, x∗)x∈RAxbсистеме линейных уравнений и неравенств⎧⎪Ax∗ b⎪⎪⎪⎨AT y ∗ = c⎪y∗ 0⎪⎪⎪⎩(b, y ∗) = (c, x∗)Эта система следует из теоремы о двойственности линейного программирования: x∗ - это решение прямой задачи линейного программирования(это - первое неравенство), y ∗ - это решение двойственной ей задачи (второе равенство и третье неравенство) - на них должно совпадать значениеоптимизируемых скалярных произведений (четвертое равенство). Разрешимость этой системы означает существование x∗ - решения ОЗЛП, т.е. еёразрешимость - и наоборот. Далее для простоты обсуждения звездочкибудут опущены.Преобразуем эту систему уравнений-неравенств к виду системы уравнений, в которой все переменные должны принимать неотрицательные значения.
Пусть z = b − Ax 0. Пусть x = α − β, α 0, β 0. Например, вГлава 2. Основы линейного программирования19качестве α можно взять вектор x + |x|, а в качестве β взять |x| (вектор подмодулем означает вектор из модулей компонент). Аналогично, y = γ − δ,γ 0, δ 0. В результате получаем такую систему уравнений-неравенств:⎧⎪Aα − Aβ + z = b⎪⎪⎪⎨ AT γ − AT δ = c⎪cT α − cT β − bT γ + bT δ = 0⎪⎪⎪⎩z, α, β, γ, δ 0или в виде P z = q, z 0:⎛Em A −A 0m,m⎝ 0n 0n,n 0n,n AT0 cT −cT −bT⎛ ⎞⎞ z⎛ ⎞⎟0m,m ⎜αb⎜ ⎟T⎠ ⎜ ⎟⎝ ⎠−A⎜β ⎟ = c⎝γ ⎠bT0δ0m,m - матрица m × m из нулей,Em - матрица m×m, у которой на диагонали стоят единицы, а на остальныхместах - нули,A ∈ Rm,n - матрица вещественных чисел m × n,b ∈ Rm , c ∈ Rn - вектора-столбцы вещественных чисел соответствующейразмерности,z - вещественное число (скаляр)Глава 3Элементы математическогопрограммирования3.1 задача №9Постановка задачи.
Доказать Go (x) = ∅ ⇒ Go (x) = G(x) для любойточки x ∈ X ⊂ Rn в задаче минимизации некоторой функции f (x) намножестве X, гдеX = {x ∈ Rn | ∀i = 1, m(gi(x) 0)},Go (x) = {y ∈ Rm | ∀i ∈ J (x)((∇gi(x), y) < 0)},G(x) = {y ∈ Rm | ∀i ∈ J (x)((∇gi(x), y) 0)},J (x) = {i∗ = 1, m | gi∗ (x) = 0}Доказательство. 1. Докажем, что Go (x) = ∅ ⇒ Go (x) ⊆ G(x), т.е. все предельные точки Go (x) лежат в G(x). Выберем произвольно предельную точку множества Go (x). Пусть это будет некоторая точка y.
Тогда по определению предельной точки, существует целая последовательность yn ∈ Go (x),сходящаяся к y.Заметим, что yn ∈ Go (x) ⊆ G(x), т.е. yn ∈ G(x). Т.к. G(x) - это пересечение замкнутых множеств (полупространств), а значит оно само замкнуто.А значит, из yn ∈ G(x) будет следовать, что lim yn ∈ G(x), т.е y ∈ G(x).n→∞Первая часть доказательства сделана.20Глава 3. Элементы математического программирования212. Докажем, что Go (x) = ∅ ⇒ Go (x) ⊇ G(x), т.е. для любого элементаξ ∈ G(x) найдется последовательность {ξn } ⊆ Go (x), сходящаяся к ξ.Зафиксируем x ∈ X. Очевидно, что Go (x) ⊆ G(x).Если ξ ∈ Go (x), то в качестве ξn достаточно взять ξn = ξ.
И все требования будут соблюдены.В противном случае заметим, что так как Go (x) = ∅, то обязательнонайдется точка ξ ∗ ∈ Go (x). Так как Go (x) - есть пересечение открытыхполупространств, то Go (x) - открытый многогранник, а, значит, Go (x) - выпуклое множество. Тогда в качестве ξn возьмем такую последовательностьточек, которая вся лежит на отрезке из ξ ∗ в ξ, причем вся лежит в Go (x).Для этого достаточно взять ξn так: ξn = n1 ξ ∗ + (1 − n1 )ξ. Покажем формально, что ξn ∈ Go (x): для любого i ∈ J (x) (∇gi, ξn ) = (∇gi, n1 ξ ∗ + (1 − n1 )ξ) =11∗n (∇gi, ξ ) + (1 − n )(∇gi , ξ).
Так как ξ ∈ G(x), то (∇gi , ξ) 0, а, значит,(∇gi, ξn) n1 (∇gi, ξ ∗) < 0, так как (∇gi, ξ ∗) < 0, что следует из того, чтоξ ∗ ∈ Go (x).Вторая часть доказана, а вместе с ней и вся теорема.3.2 задача №10Постановка задачи. Доказать теорему двойственности в линейном программировании с использованием теоремы Куна-Таккера.Теорема (двойственность в линейном программировании).
Прямая задачаразрешима ⇔ разрешима двойственная ей задача, и при этом результаты этих задач совпадают.Определение. Прямая задача линейного программирования - найтиd∗ = maxn (c, x) = (c, x∗)x∈RAxbОпределение. Задача линейного программирования, двойственная зада-Глава 3.
Элементы математического программирования22че из определения 3.2 - найтиd∗∗ = minm (b, y) = (b, y ∗)y∈RAT y=cy0mТеорема (Куна-Таккера). Пусть решается следующая задача математического программирования: ищется min f (x), где X = {x ∈ Rn |∀i =X1, m(gi(x) 0)}. Тогда если f, gi ∈ C (R ), выпуклы, а X регулярно, тосправедливо следующее:1nx∗−точка min f (x) ⇔ ∃λ 0m : ∇x L(x, λ) |x=x∗ = 0n &(gi (x∗), λ) = 0, i = 1, mгде L(x, λ) = f (x) +mλi gi (x) - функция Лагранжа.i=1Лемма 5 (самодвойственность задачи линейного программирования). ПустьПр - прямая задача линейного программирования. Будем далее обозначать её двойственную задачу приписыванием звездочки, т.е.
Пр* - задача, двойственная задаче Пр. Тогда Пр** = Пр.Доказательство леммы 5. см. домашнюю работу №6, задачу №7.Лемма 6 (наследование разрешимости двойственной задачей). Пусть Пр прямая задача линейного программирования. Тогда если Пр разрешима,то Пр* тоже разрешима, причем ответы в этих задачах совпадают.Доказательство леммы 6. Введем следующие соглашения:1.
Пусть A ∈ Rm,n . Тогда ai - i-я строка матрицы , а ai - i-й столбецматрицы2. Аргументами скалярного произведения могут быть только вектора-столбцыПриведем прямую задачу линейного программирования Пр в обозначениях определения 3.2 к виду задачи математического программирования,пригодному для применения теоремы Куна-Таккера. Пусть f (x) = (−c, x),Глава 3. Элементы математического программирования23gi (x) = ((ai)T , x) − bi. Так как скалярное произведение - линейная функция,то f (x) и g(x) непрерывно дифференцируемы и выпуклы на Rn .Пусть Пр разрешима.
Тогда по теореме Куна-Таккера, найдется векторλ ∈ Rm из неотрицательных компонент такой, какой описан в теоремеmКуна-Таккера. Посчитаем функцию Лагранжа: L(x, λ) = f (x) + λi gi (x) =(−c, x) +∗mi=1λ∗i ((ai)T , x) −mi=1i=1λ∗i bi = −(c, x) + (AT λ∗ , x) − (λ∗, b) = (AT λ∗ −c, x) − (λ , b). Так как ∇x(c, x) = c, то ∇xL(x, λ∗) = AT λ∗ − c = 0n (по теореm∗∗ме Куна-Таккера). И второе условие: (gi(x ), λ ) =λ∗i (((ai)T , x∗) − bi ) =T ∗∗∗∗i=1∗(A λ , x ) − (b, λ ) = (c, x ) − (b, λ ) = 0 (используя только что доказанноесвойство)Итак, по причине разрешимости исходной задачи Пр (точка, на которойдостигается решение, есть x∗) нашелся вектор λ∗ ∈ Rm такой, что λ∗ 0m ,AT λ∗ = c и d∗ = (c, x∗) = (b, λ∗).Пусть α∗ = |x∗| 0n (это вектор-столбец из модулей компонент вектораx∗), β ∗ = x∗ + |x∗ | 0n , γ ∗ = b − Ax∗ 0m.∗Пусть μ =α∗β∗γ∗∗ 02n+m.∗= c.
Пусть y ∗ = λ . Тогда y ∗ 0m, AT y −c ATTx + −0c , x ∈ R2n+m.Пусть f (x) = (b, x). Пусть g (x) = −A−EmmСоставим функцию Лагранжа для такой задачи:min f(y)(3.1)y∈R2n+mg(y)02n+m2n+mnmiμi gi (x) = (b, x) + (αi − βi )((a , x) − ci ) −γi x i =L(x, μ) = f (x) +i=1i=1i=1(b, x) + (A(α − β), x) − (α − β, c) − (γ, x) = (A(α − β) + b − γ, x) − (α − β, c)И посчитаем градиент по x: LGr(μ) = ∇xL(x, μ) = A(α − β) + b − γ.Посчитаем LGr(μ∗) = A(α∗ −β ∗ )+b−γ ∗ = A(|x∗|−(x+|x∗ |))+b−(b−Ax∗ ) =Глава 3. Элементы математического программирования02n+m.g(y ∗ ), μ∗) = (Теперь посчитаем (∗∗∗∗∗∗AT y ∗ −c−AT y ∗ +c−y ∗∗24 ∗α, β∗∗ ) = (AT y ∗ , α∗ − β ∗) −γ∗(c, α − β ) − (y , γ ) = (A(α − β ), y ) − (c, α − β ∗) − (y ∗ , γ ∗) = (A(α∗ −β ∗) − γ ∗, y ∗) − (c, α∗ − β ∗) = (A(α∗ − β ∗) − (b + A(α∗ − β ∗)), y ∗) − (c, α∗ − β ∗ ) =−(b, y ∗) + (c, β ∗ − α∗ ) = −(b, λ∗) + (c, x∗ + |x∗| − |x∗|) = (c, x∗) − (b, λ∗) = 0.Итак, получили, что нашелся такой вектор μ∗ 02n+m, что ∇x L(x, μ∗) =g (y ∗ ), μ∗) = 0.
Значит, по теореме Куна-Таккера существует решение0 и (задачи (3.1), которое реализуется в точке y ∗ . Причем d∗ = (c, x∗) = (b, λ∗) =(b, y ∗) = d∗∗, т.е. есть совпадение результатов. Лемма доказанаДоказательство теоремы. Пусть Пр - исходная задача линейного программирования. Тогда из лемм 6 и 5 следует, что если (Пр*)* = Пр разрешима, то Пр* - тоже разрешима. Но по той же лемме 5 Пр* - есть некотораяпрямая задача. Назовём её ПДр.
Применяя лемму 6 для ПДр, получаем:если ПДр разрешима, то ПДр* - тоже разрешима.Объединяя последнее следствие с леммой 6 для Пр, получаем: Пр разрешима ⇔ Пр* разрешима (в одну сторону - это лемма 6 для Пр, в другую- лемма 6 для ПДр, т.е. для Пр*), причем результаты решения задач совпадают. Теорема доказанаГлава 4Экзаменационные задачи4.1 Построение двойственной задачи линейного программированияПостановка задачи. Дана прямая задача линейного программирования.Построить по ней двойственную задачу и проверить теорему двойственности линейного программирования.Решение. Покажем задачу на примере.
Пусть дана такая задача линейногопрограммирования:max(2 − x)x1Строим двойственную ей задачу: max(2 − x) = 2 + max (−x). A = (−1),x1−x−1b = (−1), c = (−1). Тогда двойственная имеет вид: 2 +2 + min(−y) = min(2 − y).y=1y=1min(−y) =(−1)T y=−1y0Проверим теорему двойственности. Очевидно, двойственная задача разрешима с результатом: y ∗ = 1, d∗∗ = 1. Решим прямую задачу. В ней надонайти максимум убывающей функции. Значит, максимум будет достигатьсяна левой границе, т.е. при x = 1. Таким образом, x∗ = 1, d∗ = 1. Получили, что прямая и двойственная задача разрешимы одновременно, причемоптимумы совпадают: d∗ = d∗∗ = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
