Е. Корныхин - Задачи по курсу Методы оптимизации (1125258), страница 2
Текст из файла (страница 2)
Доказать полиномиальную сводимость задачи 3ВЫПОЛНИМОСТЬ к задаче ВЫПОЛНИМОСТЬ.Доказательство (конструктивное). Рассмотрим задачу ВЫПОЛНИМОСТЬ.Будем преобразовывать каждый дизъюнкт, входящий в исходную КНФ,в конъюнкцию дизъюнктов длины 3. Такии образом, из КНФ будет получена 3-КНФ, обладающая тем свойством, что проекция выполняющегонабор 3-КНФ на переменные, входящие в КНФ, будет выполняющим набором КНФ. И наоборот, для любого выполняющего набора КНФ найдетсявыполняющий набор 3-КНФ, проекция которого будет совпадать с выполняющий набором КНФ.Преобразование дизъюнктов длины не меньшей 2 описано в лекциях.Докажем следующее простое утверждение: для любых булевых x и yвыполнено: x ≡ (x∨y)(x∨y).
Докажем его следующей последовательностьюГлава 1. Введение в теорию сложности10эквивалентных преобразований: (x ∨ y)(x ∨ y) ≡ xx ∨ xy ∨ xy ∨ yy ≡x ∨ x(y ∨ y) ∨ 0 ≡ x ∨ x1 ≡ x.Преобразование дизъюнктов длины 2 будем выполнять следующим образом: y1 ∨ y2 ≡ (y1 ∨ y2 ∨ u)(y1 ∨ y2 ∨ u), где u - новая булева переменная.Преобразование дизъюнктов длины 1: x ≡ (x ∨ y)(x ∨ y) ≡ (x ∨ y ∨ u)(x ∨y ∨ u)(x ∨ y ∨ u)(x ∨ y ∨ u), где y, u - новые булевы переменные.Глава 2Основы линейного программированияОпределение. Основная задача линейного программирования ( ОЗЛП): при начальных данных A ∈ Rn,m , b ∈ Rm , c ∈ Rn найти η ∈ Rn такой, что (c, η) = max (c, x),где (x, y) =ni=1Axbxi yi .Определение.
Каноническая задача линейного программирования ( КЗЛП): при начальных данных A ∈ Rn,m , b ∈ Rm , c ∈ Rn найти ξ ∈ Rn такой, что (c, ξ) =nmax(c, x), где (x, y) =xi yi .Ax=b, x0ni=12.1 задача №5Постановка задачи. Свести каноническую задачу линейного программирования ( КЗЛП) к основной задаче линейного программирования ( ОЗЛП).Решение (конструктивное). Покажем сведение КЗЛП к ОЗЛП:maxAxb, Axb, x0n(c, x) =maxAxb, (−A)x−b, −x0n(c, x) = maxmax b A−A x −b−En0n(c, x) = max (c, x),⎞⎛ ⎞bA⎠⎝⎝где A = −A (En - единичная матрица порядка n) и b = −b⎠.0n−En⎛11(c, x) =Ax=b, x0n bAxГлава 2.
Основы линейного программирования122.2 задача №6Постановка задачи. Доказать, что L O(ln n), где L - длина входаОЗЛП D (входом ОЗЛП считается 3 матрицы: A ∈ Rm,n , b ∈ Rm , c ∈ Rn ),а = (A) = max| det A |.A ⊆AДоказательство (от противного). Первым делом хочу заметить, что условие задачи допускает несколько интерпретаций (причина этого в том, чтосимвол О нельзя использовать для сравнения на "больше-меньше").ПЕРВАЯ ИНТЕРПРЕТАЦИЯ: доказать, что L f (n) для некоторой функцииf (n) = O(ln n), т.е.
по определению О существует такая константа (дляn) C > 0 и номер N такие, что f (n) C ln n для всех n N . Но я недумаю, что имелось именно это, потому как доказывается слишком просто:в качестве f можно взять константу 0.ВТОРАЯ ИНТЕРПРЕТАЦИЯ: доказать, что L = Ω(ln n), т.е.
по определению Ω найдется такая константа (для n) C > 0 и номер N такие, чтоL C ln n. Но тогда противное утверждение (о том, что в общем случаетакого конечного N может не найтись и L = o(ln n) будет выполненона целой последовательности различных задач Dn ) будет иметь такое подтверждение. Возьмем кодировку, которая задачи со входом Dn (где n - естьстепень двойки, а сама Dn , как матрица, состоит из одних единиц) переводила в строку, являющуюся двоичной записью показателя степени вn, а входы всех остальных задач переводила каким-то определенным, ноне регламентируемым здесь, способом так, чтобы не нарушались свойстваоднозначности, полиномиальной кодируемости и декодируемости и неизбыточности.
Тогда в качестве Dn возьмем ту самую последовательность задач,размерность которых есть степень двойки. Тогда задачи Dn будут кодироваться словами длиной L = O(log log n), т.к. размерность задачи n в данномслучае равна 2n1 , а нужно получить двоичную запись числа n1 = log n, чтодобавляет ещё один логарифм. Итак, вторая интерпретация привела нас кконтрпримеру к своей формулировке.Глава 2. Основы линейного программирования13И, наконец, ТРЕТЬЯ ИНТЕРПРЕТАЦИЯ: доказать, что L ln n, т.е. всегдапорядок роста L не может быть ниже, чем ln n.
Вот это утверждениепопытаемся доказать от противного. Предположим, что нашлась такая кодировка e , что |e (Dn)| имеет меньший порядок роста, чем ln n, т.е. что|e (Dn )| = o(ln n)Докажем тогда, что такая кодировка не будет однозначной (слишком онаумудряется ужать D). Предположим противное, т.е. что кодировка e однозначна. Рассмотрим задачи Dn порядков n, матрицы которых содержаттолько единицы. Пусть An - матрица коэффициентов задач Dn . Тогда(An ) = 1. Отсюда получаем, что|e (Dn)| = o(ln n)Таким образом, кодировка e кодирует единичную матрицу порядка n словом длины o(ln n). Покажем, что такой кодировки существовать не может.Пусть F (n) = max |e (Dk )|.
Так как |e (Dk )| = o(ln k), то F (n) = o(ln n).1knТак как e однозначна и {Dk }nk=1 различны, то различны будут и {e (Dk )}nk=1и их ровно n штук.Найдем число кодировок единичных матриц порядка n словами изконечного алфавита Σ. Их не больше, чемF (n)k=1|Σ|(|Σ|F (n) − 1)∼ |Σ|F (n) = |Σ|o(ln n)|Σ| =|Σ| − 1k(это число слов длины не большей, чем F (n) в алфавите Σ). Докажем, что|Σ|o(ln n) = o(n).Пусть f (n) = o(ln n). Тогда по определению символа o lim fln(n)= 0.nf (n)f (n) ln |Σ|Тогда lim |Σ|n = lim e nn→∞n→∞ln n(ln |Σ|·0 − 1)= lim e− ln nlim en→∞n→∞f (n) ln |Σ|−ln n= lim e=n→∞lim 1n→∞ nn→∞ln n·(ln |Σ| fln(n)n − 1)= lim en→∞= 0.=Глава 2.
Основы линейного программирования14Итак, получили, что n o(n), что на самом деле неправда. Осталосьвспомнить все допущения, которые мы делали и удостовериться, что всеони приводят к противоречиям. Что и доказывает поставленную перед намизадачу в третьей формулировке.2.3 задача №6.1Постановка задачи. Доказать, что L > O(ln n), где L - битовая длинавхода ОЗЛП D.Лемма 2. Для любого целого неотрицательного числа n длина его двоичной записи числа log 1 (n + 1).Доказательство. Пусть n = 0. Тогда длина двоичной записи числа n равна1 = log(0 + 1).
То есть для n = 0 неравенство выполнено.Пусть длина двоичной записи n равна k. Тогда 2k−1 n < 2k ⇒ n + 1 2k ⇒ log(n + 1) k.Лемма 3. Для любых неотрицательных чисел x1, x2, · · · , xn 0 выполнено неравенство x1 + x2 + · · · + xn (x1 + 1)(x2 + 1) · · · (xn + 1).Доказательство.
Раскрытием скобок, получаем такое равенство: (x1+1)(x2+1) · · · (xn + 1) = x1 + x2 + · · · + xn + A, причем A 0, т.к. есть сумма произведений неотрицательных чисел.Лемма 4. Для любой квадратной матрицы A выполнено неравенство| det A| |ai,j |.ijДоказательство.По определению определителя | det A| = | | ai1 ai2 · · · ain |.1 далеелогарифмы без основания - двоичные(−1)a(x) ai1 ai2 · · · ain | Глава 2. Основы линейного программированияРаскроем скобки в произведении сумм15i|ai,j |.
В полученной суммеjбудут все произведения из полученной только что оценки модуля определителя плюс ещё некоторая сумма произведений модулей элементов матрицыA.Доказательство (нашей задачи). Доказательство проведем для матриц D,состоящих из неотрицательных целых чисел. Для остальных чисел неравенство тоже будет доказано, т.к. длина двоичного представления отрицательного числа больше на единицу (знак «минус»), а рационального числа- на длину знаменателя.L=(blen(ai,j ) + 1) +i,j(blen(bi) + 1) +(blen(cj ) + 1) + blen(n)ij(blen(x) - это длина двоичной записи x) (здесь использовано двоичноекодирование элементов матрицы + разделители + надо закодировать n,чтобы однозначно восстановить положение элементов матрицы).По лемме 1 L log(2ai,j + 2) + log(2bi + 2) + log(2cj + 2) + log(n) =ij i,j log( (ai,j +1) (bi +1) (cj +1))+(n+1)(m+1)+log n log (ai,j +1)+log n,т.к.
bi 0, cj 0.Пусть A1 - та квадратная подматрица матрицы A, на которой достигаетсямаксимум модуля определителя. Тогда по леммам 2 и 3 = | det A1| |ai,j | (ai,j + 1), т.к. ai,j 0.i ji jТаким образом L log (ai,j + 1) + log n log + log n = log(n) =O(ln(n)).2.4 задача №7Постановка задачи. Доказать, что двойственная задача к двойственной задаче линейного программирования есть прямая задача линейногоГлава 2. Основы линейного программирования16программирования.Доказательство.
Пусть дана следующая прямая задача линейного программирования в основной форме:найти d = maxn (c, x) = (c, x∗)(2.1)x∈RAxbгде A ∈ Rm,n , b ∈ Rm , c ∈ Rn . Здесь и далее элементы пространства Rkбудем представлять столбцами из k вещественных чисел.Тогда по определению двойственная задача для неё будет выглядеть так:найти d∗ = minm (b, y) = (b, y ∗)(2.2)y∈RAT y=cy0mПриведем двойственную задачу к виду прямой: min(b, y) = − max(−b, y) =TTA y=cy0m−max AT−AT−EmA yc−AT y−c−y0m(−b, y).c y −c0mПостроим двойственную задачу к полученной задаче: c −min( 0−c , z)2n+mz∈Rz02n+m(A|−A|−Em )z=−bαПредставим z = βγ , где α, β ∈ Rn , γ ∈ Rm .Тогда задача (2.3) запишется так: −(2.3)mmin(α 0 nβ 0nγ0mα(A|−A|−Em ) β =−bγc−c0m α, βγ ) =Глава 2.
Основы линейного программированияmax −c α ( 0c , βγ ) =α 0 nβ 0nγ0mα(A|−A|−Em ) β =−bγm17max(c, β−α) =α0nβ0nγ0mAα−Aβ−γ=−bmaxα0nβ0nγ=b−A(β−α)0m(c, β − α) =max (c, β − α).α0nβ0nA(β−α)bИтак, двойственная задача к двойственной (2.1) задаче имеет вид:max (c, β − α)α0nβ0nA(β−α)b(2.4)Осталось доказать эквивалентность задач (2.1) и (2.4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
