Задачи по курсу (1125232), страница 3

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

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

Разрешимость этой системы означает существование 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. Теорема двойственности выполнена.25Глава 4. Экзаменационные задачи26Для самостоятельного решения:1. max (3x + 5).2x42. min(2 − x). Указание: min x = − max(−x).x13. min(2 − x).x1x34.5.max (x + y + 2). Указание: для решения системы линейных неравенств использовать симплекс-метод2x−3y1xyx+y−4min (x + y + 2).2x−3y1xyx+y−4Ответы: 17, ∞, -1, 0, -2.4.2 Применение градиентного методаПостановка задачи. Записать градиентный метод решения задачиmin(x2 + y 2 )a) с постоянным шагом α =14б) наискорейшим спускомВыписать несколько итераций с начальным приближением x1 = 1, y1 =1.Решение. Градиентный метод:zt+1 = zt − αt · (∇f )(zt)⎛∂ 2⎛ ⎞⎛ ⎞2 ⎞(x+y)xt2x∂x22⎠ = ⎝ ⎠, zt = ⎝ ⎠f = (x + y ), ∇f = ⎝∂22(x + y )yt2y∂yГлава 4.

Экзаменационные задачи27⎛⎞ ⎛ ⎞⎛ ⎞xt+1xt2xt⎠ = ⎝ ⎠ − αt ⎝ ⎠ или в виде системы:Тогда ⎝yt+1yt2ytxt+1 = xt − αt 2xt = (1 − 2αt )xtyt+1 = yt − αt 2yt = (1 − 2αt )ytДля постоянного шага: αt = 14 . Тогдаxt+1 = (1 − 2 14 )xt = 12 xtt = 1, 2, ...yt+1 = (1 − 2 14 )yt = 12 ytВыпишем несколько итераций:txtyt111234121214141818Видно, что сходимость происходит со скоростью геометрической прогрессии с q = 12 , что подтверждается соответствующим устверждением оскорости сходимости градиентного метода из лекций.Наискорейшийt : f (zt+1 ) → min.

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

Список файлов курсовой работы