Редактирование: Методы оптимизации, задачи

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 30 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

== Задача 1 == '''Условие.''' Предложить неизбыточную кодировку задачи коммивояжёра. Дать оценку длины входа и сравнить её с <math>m + \lceil\log_2 B \rceil + \max\limits_{i,j} \lceil\log_2 d_{i,j}\rceil</math>. '''Решение.''' Пусть m — число городов, B — максимальная длина маршрута, <math>D = \lbrace d_{i,j}\rbrace</math> — матрица расстояний между городами. Будем кодировать m, B и <math>d_{i,j}</math> в двоичном виде. Кроме того, включим в алфавит символ-разделитель #. Таким образом, кодировка будет состоять из двоичных записей чисел m, B и элементов <math>d_{i,j}</math>, между которыми находятся разделители #. При этом можно включать в кодировку не все элементы <math>d_{i,j}</math>, а только те, которые лежат выше главной диагонали матрицы D (поскольку в силу равенств <math>d_{i,j} = d_{j,i}</math> и <math>d_{i,i} = 0</math> матрица D симметрична и имеет нулевую главную диагональ). Кроме того, можно не кодировать и число m, поскольку оно однозначно определяется по числу разделителей между элементами матрицы. Для того чтобы осуществить двоичное кодирование некоторого числа N, необходимо <math>\lfloor \log_2 N \rfloor + 1</math> символов. Таким образом, длина входа задачи коммивояжёра будет равна <math>(\lfloor \log_2 B \rfloor + 1) + 1 + \sum_{1 \leqslant i < j \leqslant m} (\lfloor \log_2 d_{i,j} \rfloor + 1) + \bigl( (m-1) + (m-2) + \ldots + 2 \bigr) \; \leqslant \; \lceil \log_2 B \rceil + \frac{m(m-1)}{2} \max\limits_{1 \leqslant i < j \leqslant m} (\lceil \log_2 d_{i,j} \rceil) + \frac{m(m-1)}{2} + 1.</math> Кодировать число B и верхнюю часть матрицы D надо в любом случае; двоичное кодирование неизбыточно; разделителей мы добавили лишь полиномиальное число (порядка <math>\frac{m^2}{2}</math>). Поэтому кодировка является неизбыточной. Оценка <math>m + \lceil\log_2 B \rceil + \max\limits_{i,j} \lceil\log_2 d_{i,j}\rceil</math> лучше предложенной, но вряд ли достижима. == Задача 2 == '''Условие.''' Дать алгоритм распознавания простоты числа и оценить его временную сложность. '''Решение.''' Будем считать, что исходное число N вводится в двоичном виде. Для того, чтобы проверить его на простоту, будем делить его поочерёдно на 2, 3, ..., N-1 и рассматривать остатки от делений. Если на очередном шаге остаток получился равным нулю, то процесс можно не продолжать — рассматриваемое число не являеся простым; если же мы произвели все деления и не получили ни одного нулевого остатка, то число является простым. Таким образом, в худшем случае (когда рассматриваемое число — простое) получаем N-2 деления. Деление будем производить «столбиком». Пусть мы делим некоторое число a на некоторое число b (с соответствующими битовыми длинами <math>m_a</math> и <math>m_b</math>). Тогда на каждое вычитание двоичных строк потребуется, грубо говоря, <math>2(m_b + 1)</math> битовых операций (непосредственно вычитания плюс проверки); всего же таких итераций будет не больше, чем <math>m_a - m_b + 1.</math> Получаем, что <math>t(m_a, m_b) \leqslant 2(m_b + 1)(m_a - m_b + 1).</math> : <math>2(m_b + 1)(m_a - m_b + 1) \leqslant 2(m+1)m = 2m^2 + 2m.</math> Следовательно, деление «столбиком» имеет сложность <math>O(n^2)</math>. Итого, сложность всего алгоритма равна <math>T(n) = (N - 2) \cdot O(n^2) = O(2^n) \cdot O(n^2) = O(n^2 \cdot 2^n).</math> Замечание: нет смысла искать делители до N-1, достаточно рассматривать делители до целой части sqrt(N) Замечание к замечанию: на вычисление sqrt(n) тоже требуется время, которое нужно учитывать. Если лень, то смело можно ограничить [N/2] == Задача 3 == '''Условие.''' Завершить доказательство утверждения 9 (§3 методички) для случая k = 1, 2. '''Решение.''' В том случае, когда дизъюнктивные функции, входящие в КНФ задачи о выполнимости, зависят от одной или двух переменных, их можно представить в виде конъюнкции дизъюнктивных функций трёх переменных следующим образом: # При k = 1: : <math>y_1 = (y_1 \vee \bar{u}{}_1) \wedge (y_1 \vee u_1) = (y_1 \vee \bar{u}{}_1 \vee \bar{u}{}_2) \wedge (y_1 \vee \bar{u}{}_1 \vee u_2) \wedge (y_1 \vee u_1 \vee \bar{u}{}_2) \wedge (y_1 \vee u_1 \vee u_2).</math> # При k = 2: : <math>y_1 \vee y_2 = (y_1 \vee y_2 \vee \bar{u}) \wedge (y_1 \vee y_2 \vee u).</math> При этом переменные <math>u</math> являются фиктивными, то есть такая замена является эквивалентной (в отличие от замены для случая k = 3). Таким образом, эти три преобразования позволяют полиномиально свести задачу ВЫП к задаче 3-ВЫП. == Задача 4 == '''Условие.''' Доказать, что задача ПЧ<math>\in co-\mathbb{NP}</math>. '''Решение.''' Согласно определению, задача ПЧ будет принадлежать классу <math>co-\mathbb{NP}</math>, если дополнительная к ней задача будет принадлежать классу <math>\mathbb{NP}.</math> Дополнительной к задаче ПЧ является задача распознавания того, является ли число (назовём его N, с битовой длиной n) составным. Для проверки этого будем использовать детерминированные машины Тьюринга, которые «столбиком» делят N на числа, соответственно, от 2 до N-1 и находят остатки от этих делений. Если хотя бы одна из ДМТ выдаст нулевой остаток, вся НДМТ останавливается — число N является составным. Если же все остатки отличны от нуля, N — простое число. Деление «столбиком» имеет сложность порядка <math>O(n^2)</math> (см. [[Методы оптимизации, задачи#Задача 2|Задачу 2]]); длина каждого из слов-подсказок не превышает n, поэтому время их прочтения не больше k*n, где k — некоторый коэффициент. Следовательно, временная сложность всей НДМТ, решающей задачу о том, является ли число составным, также полиномиальна. Таким образом, эта задача принадлежит классу <math>\mathbb{NP}</math>, а задача ПЧ принадлежит классу <math>co-\mathbb{NP}.</math> == Задача 5 == '''Условие.''' Свести задачу ЛП с ограничениями в канонической форме к основной задаче ЛП. '''Решение.''' Другими словами, необходимо задачу <math>\max\limits_{\tilde{A} x = \tilde{b}, \; x \in \mathbb{R}^n, \ x \geqslant \bar{0}} \langle c,x \rangle</math> свести к задаче <math>\max\limits_{Ax \leqslant b, \; x \in \mathbb{R}^n} \langle c,x \rangle.</math> Применим к ограничениям в канонической форме равносильные преобразования: : <math>\tilde{A} x = \tilde{b} \Leftrightarrow \begin{cases} \tilde{A} x \geqslant \tilde{b} \\ \tilde{A} x \leqslant \tilde{b} \end{cases} \Leftrightarrow \begin{cases} - \tilde{A} x \leqslant - \tilde{b} \\ \tilde{A} x \leqslant \tilde{b} \end{cases} \Leftrightarrow \begin{pmatrix} - \tilde{A} \\ \tilde{A} \end{pmatrix} x \leqslant \begin{pmatrix} - \tilde{b} \\ \tilde{b} \end{pmatrix}.</math> Учитывая равносильность условий <math>x \geqslant \bar{0}</math> и <math>- x \leqslant \bar{0}</math>, получаем: : <math>\begin{pmatrix} - \tilde{A} \\ \tilde{A} \\ - E \end{pmatrix} x \leqslant \begin{pmatrix} - \tilde{b} \\ \tilde{b} \\ \bar{0} \end{pmatrix}.</math> Получаем, что <math>\max\limits_{\tilde{A} x = \tilde{b}, \; x \in \mathbb{R}^n, \ x \geqslant \bar{0}} \langle c,x \rangle \; = \;\max\limits_{Ax \leqslant b, \; x \in \mathbb{R}^n} \langle c,x \rangle</math>, где <math>A = \begin{pmatrix} - \tilde{A} \\ \tilde{A} \\ - E \end{pmatrix}, \; b = \begin{pmatrix} - \tilde{b} \\ \tilde{b} \\ \bar{0} \end{pmatrix},</math> то есть мы свели задачу ЛП с ограничениями в канонической форме к основной задаче ЛП. == Задача 6 == '''Условие.''' Оценить по порядку битовую длину L входа озЛП. А именно, доказать, что <math>L > O(\ln(n\Delta))</math>, где <math>\Delta = \max|det D'|</math>, <math>D'</math> — квадратная подматрица D, D — симплекс-матрица озЛП. '''Решение.''' Входом озЛП является симплекс-матрица D, имеющая вид <math> D = \begin{pmatrix} c_1 & \cdots & c_n & 0 \\ a_{1,1} & \cdots & a_{1,n} & b_1 \\ a_{2,1} & \cdots & a_{2,n} & b_2 \\ \vdots & \ddots & \vdots & \vdots \\ a_{m,1} & \cdots & a_{m,n} & b_m \end{pmatrix}.</math> Таким образом, для кодирования входа озЛП в любом случае необходимо закодировать числа <math>a_{i,j}, b_i, c_j (i=\bar{1,m}, j=\bar{1,n})</math>, а также само число n для последующего восстановления размерности матрицы. Кроме того, в кодировку необходимо добавить разделители между числами, или указать число бит, выделяемое на кодирование каждого числа, или ещё каким-либо способом предоставить возможность однозначной расшифровки чисел. В свою очередь, при кодировании самих чисел в общем случае необходимо закодировать их знак и дробную часть. Получается, что даже в простейшем случае, когда все числа являются целыми и неотрицательными (а битовая длина целого неотрицательного числа k есть число, не меньшее <math>\log_2 (k+1)</math>), длину входа озЛП можно оценить снизу следующим образом: : <math>L \geqslant \sum\limits_{i=1}^m \sum\limits_{j=1}^n \log_2(a_{i,j}+1) + \sum\limits_{i=1}^m \log_2(b_i+1) + \sum\limits_{j=1}^n \log_2(c_j+1) + \log_2(n+1) > // \log_2 a + \log_2 b = \log_2 ab // > </math> : <math> > \log_2 \prod\limits_{i=1}^m \prod\limits_{j=1}^n (a_{i,j}+1) + \log_2 \prod\limits_{i=1}^m (b_i+1) + \log_2 \prod\limits_{j=1}^n (c_j+1) + \log_2 n = </math> : <math>= \log_2 \left( \prod\limits_{i=1}^m \prod\limits_{j=1}^n (a_{i,j}+1) \cdot \prod\limits_{i=1}^m (b_i+1) \cdot \prod\limits_{j=1}^n (c_j+1) \right) + \log_2 n = \log_2 \left( \prod\limits_{i=1}^{m+1} \prod\limits_{j=1}^{n+1} (d_{i,j}+1) \right) +\log_2 n,</math> где <math>d_{i,j}</math> — элементы матрицы D. Далее, <math>\Delta = \max\limits_{D' \subseteq D} |det D'| = |det \tilde{D}|</math>, где <math>\tilde{D}</math> — некоторая квадратная подматрица D размерности k x k. Получаем, что : <math>\Delta = |det \tilde{D}| =_{def} \left| \sum\limits_{\alpha=(\alpha_1, \ldots , \alpha_k)} (-1)^{\sigma(\alpha)} \tilde{d}{}_{1,\alpha_1} \cdot \ldots \cdot \tilde{d}{}_{k,\alpha_k} \right| </math>, где <math>\alpha=(\alpha_1, \ldots , \alpha_k)</math> — перестановки чисел 1, ..., k, а <math>\sigma(\alpha) = \begin{cases} 0, \mbox{if } \alpha \mbox{ is even;} \\ 1, \mbox{if } \alpha \mbox{ is odd.} \end{cases}</math>. Следовательно, <math>\Delta \leqslant \sum\limits_{\alpha=(\alpha_1, \ldots , \alpha_k)} \left| (-1)^{\sigma(\alpha)} \tilde{d}{}_{1,\alpha_1} \cdot \ldots \cdot \tilde{d}{}_{k,\alpha_k} \right| = \sum\limits_{\alpha=(\alpha_1, \ldots , \alpha_k)} \tilde{d}{}_{1,\alpha_1} \cdot \ldots \cdot \tilde{d}{}_{k,\alpha_k}.</math> Эту сумму можно оценить сверху величиной <math>\prod\limits_{i=1}^k \sum\limits_{j=1}^k \tilde{d}{}_{i,j},</math> так как если раскрыть в ней скобки, то мы получим все необходимые произведения плюс некоторую неотрицательную часть. Таким образом, <math>\Delta \leqslant \sum\limits_{\alpha=(\alpha_1, \ldots , \alpha_k)} \tilde{d}{}_{1,\alpha_1} \cdot \ldots \cdot \tilde{d}{}_{k,\alpha_k} \leqslant \prod\limits_{i=1}^k \sum\limits_{j=1}^k \tilde{d}{}_{i,j} < // x_1+ \ldots +x_n+1 \leqslant (x_1+1) \cdot \ldots \cdot (x_n+1) // < \prod\limits_{i=1}^k \prod\limits_{j=1}^k ( \tilde{d}{}_{i,j} +1) \leqslant \prod\limits_{i=1}^{m+1} \prod\limits_{j=1}^{n+1} ( d_{i,j} +1). </math> Итак, <math>L > \log_2 \left( \prod\limits_{i=1}^{m+1} \prod\limits_{j=1}^{n+1} (d_{i,j}+1) \right) +\log_2 n > \log_2 \Delta + \log_2 n = \log_2 (n \Delta) = O(\ln(n \Delta)),</math> ч.т.д. == Задача 7 == '''Условие.''' Доказать, что двойственная задача к двойственной совпадает с прямой задачей для озЛП. '''Решение.''' Пусть дана прямая задача ЛП в основной форме: <math>\max\limits_{Ax \leqslant b} \langle c,x \rangle. \qquad (1)</math> Запишем для неё двойственную задачу: <math>\min\limits_{\lambda A = c, \lambda \geqslant \bar{0}} \langle \lambda, b \rangle.</math> Приведём эту задачу к основной форме. <math>\min\limits_{\lambda A = c, \lambda \geqslant \bar{0}} \langle \lambda, b \rangle = - \max\limits_{\lambda A = c, \lambda \geqslant \bar{0}} \langle - b^T, \lambda^T \rangle.</math> Далее, <math>\lambda A = c \Leftrightarrow \begin{cases} \lambda A \leqslant c \\ \lambda A \geqslant c \end{cases} \Leftrightarrow \begin{cases} \lambda A \leqslant c \\ - \lambda A \leqslant - c \end{cases} \Leftrightarrow \begin{cases} A^T \lambda^T \leqslant c^T \\ - A^T \lambda^T \leqslant - c^T \end{cases}</math>. Получаем, что <math>\min\limits_{\lambda A = c, \lambda \geqslant \bar{0}} \langle \lambda, b \rangle = - \max\limits_{A^T \lambda^T \leqslant c^T, - A^T \lambda^T \leqslant - c^T, (-E) \lambda^T \leqslant \bar{0}} \langle - b^T, \lambda^T \rangle = - \max\limits_{A' \delta \leqslant c'} \langle - b^T, \delta \rangle,</math> где <math>\delta = \lambda^T, \; A' = \begin{pmatrix} A^T \\ -A^T \\ - E \end{pmatrix}, c' = \begin{pmatrix} c^T \\ -c^T \\ \bar{0} \end{pmatrix}. \qquad (2) </math> Запишем задачу, двойственную к <math>(2)</math>: <math>- \min\limits_{x' A' = - b^T, x' \geqslant \bar{0}} \langle x', c' \rangle = \max\limits_{x' A' = - b^T, x' \geqslant \bar{0}} \langle -c', x' \rangle. \qquad (3)</math> Представим <math>x'</math> в виде <math>x' = (x'_1, x'_2, x'_3); x'_1, x'_2 \in \mathbb{R}{}^n, x'_3 \in \mathbb{R}{}^m.</math> Тогда <math>\max\limits_{x' A' = - b^T, x' \geqslant \bar{0}} \langle -c', x' \rangle = \max\limits_{x'_1 A^T - x'_2 A^T - x'_3 E = - b^T, \; x' \geqslant \bar{0}} ( \langle -c^T, x'_1 \rangle + \langle c^T, x'_2 \rangle ) </math> = <math> \max\limits_{(x'_1 - x'_2) A^T - x'_3 = - b^T, \; x' \geqslant \bar{0}} \langle c^T, x'_2 - x'_1 \rangle = </math> <math> = \max\limits_{A(x'_1 - x'_2)^T - x^{'T}_3 = - b, \; x' \geqslant \bar{0}} \langle c, x_2^{'T} - x_1^{'T} \rangle = \max\limits_{x^{'T}_3 = A(x'_1 - x'_2)^T + b, \; x' \geqslant \bar{0}} \langle c, x_2^{'T} - x_1^{'T} \rangle = \max\limits_{A(x'_1 - x'_2)^T \leqslant b, \; x^{'T}_1, x^{'T}_2 \geqslant \bar{0}} \langle c, x_2^{'T} - x_1^{'T} \rangle. \qquad (4)</math> Для любого <math>x: \; Ax \leqslant b</math> положим <math>x_1^{'T} = \frac{|x|-x}{2}, \; x_2^{'T} = \frac{|x|+x}{2}:</math> <math>\max\limits_{Ax \leqslant b} \langle c,x \rangle \leqslant \max\limits_{A(x'_1 - x'_2)^T \leqslant b, \; x^{'T}_1, x^{'T}_2 \geqslant \bar{0}} \langle c, x_2^{'T} - x_1^{'T} \rangle.</math> Для любых <math>x_1^{'T}, x_2^{'T} \geqslant \bar{0}</math> положим <math>x = x_2^{'T} - x_1^{'T}:</math> <math>\max\limits_{A(x'_1 - x'_2)^T \leqslant b, \; x^{'T}_1, x^{'T}_2 \geqslant \bar{0}} \langle c, x_2^{'T} - x_1^{'T} \rangle \leqslant \max\limits_{Ax \leqslant b} \langle c,x \rangle.</math> В итоге получаем, что <math>\max\limits_{Ax \leqslant b} \langle c,x \rangle = \max\limits_{A(x'_1 - x'_2)^T = b, \; x^{'T}_1, x^{'T}_2 \geqslant \bar{0}} \langle c, x_2^{'T} - x_1^{'T} \rangle.</math> Следовательно, задачи <math>(1)</math> и <math>(4)</math> совпадают, ч.т.д. == Задача 8 == '''Условие.''' Доказать, что задача ЛП эквивалентна задаче <math>\hat{P}y = \hat{q}, \; y \geqslant \bar{0}.</math> '''Решение.''' Любая задача ЛП может быть представлена в форме озЛП: <math>\max\limits_{Ax \leqslant b, \; x \in \mathbb{R}^n} \langle c,x \rangle.</math> В свою очередь, в силу утверждения 4 §7 озЛП наряду с двойственной задачей <math>\min\limits_{\lambda A = c, \lambda \geqslant \bar{0}} \langle \lambda, b \rangle</math> эквивалентна следующей системе ЛН: <math>\begin{cases} Ax \leqslant b \\ \lambda A = c \\ \lambda \geqslant \bar{0} \\ \langle c,x \rangle = \langle \lambda, b \rangle \end{cases}, \quad (x,\lambda) \in \mathbb{R}^{n+m}.</math> Представим <math>x</math> в виде <math>x = x_2 - x_1; \; x_1, x_2 \in \mathbb{R}^n, \; x_1, x_2 \geqslant \bar{0}.</math> Получим систему <math>\begin{cases} A(x_2-x_1) \leqslant b \\ A^T \lambda^T = c^T \\ \langle c,x_2-x_1 \rangle - \langle b^T, \lambda^T \rangle = 0 \\ \lambda \geqslant \bar{0} \\ x_1 \geqslant \bar{0} \\ x_2 \geqslant \bar{0} \end{cases} \Leftrightarrow \begin{cases} A(x_2-x_1) = b - Ez \\ A^T \lambda^T = c^T \\ \langle c,x_2-x_1 \rangle - \langle b^T, \lambda^T \rangle = 0 \\ z \geqslant \bar{0}, \quad z \in \mathbb{R}^m \\ \lambda \geqslant \bar{0}, \quad \lambda \in \mathbb{R}^m \\ x_1 \geqslant \bar{0}, \quad x_1 \in \mathbb{R}^n \\ x_2 \geqslant \bar{0}, \quad x_2 \in \mathbb{R}^n \end{cases} \quad (1)</math> Положим <math>\begin{pmatrix} x_1 \\ x_2 \\ \lambda^T \\ z \end{pmatrix} = y</math>. Тогда система <math>(1)</math> эквивалентна системе <math>\hat{P}y = \hat{q}, \; y \geqslant \bar{0}, \; \hat{P} = \begin{pmatrix} -A & A & \bar{0} & E \\ \bar{0} & \bar{0} & A^T & \bar{0} \\ -c & c & -b^T & \bar{0} \end{pmatrix}, \; \hat{q} = \begin{pmatrix} b \\ c^T \\ \bar{0}\end{pmatrix}, </math> ч.т.д. == Задача 9 == '''Условие.''' Применить теорему Каруша-Куна-Таккера к озЛП; с помощью этой же теоремы доказать теорему двойственности для озЛП. '''Решение.''' Пусть дана прямая задача ЛП в основной форме и двойственная к ней: <math>d^* = \langle c, x^* \rangle = \max\limits_{Ax \leqslant b, \; x \in \mathbb{R}^n} \langle c,x \rangle \quad (1);</math> <math>d^{**} = \langle y^*, b \rangle = \min\limits_{A^T y = c, \; y \geqslant \bar{0}} \langle y,b \rangle \quad (2).</math> Приведём их к виду, пригодному для применения теоремы Каруша-Куна-Таккера: <math>d^* = \langle c, x^* \rangle = \max\limits_{Ax \leqslant b, \; x \in \mathbb{R}^n} \langle c,x \rangle = \min\limits_{Ax \leqslant b, \; x \in \mathbb{R}^n} ( - \langle c,x \rangle ) = \min\limits_{x \in X} f(x)</math>, где : <math> f(x) = - \langle c,x \rangle; \qquad X = \lbrace x \in \mathbb{R}^n | g_i(x) \leqslant 0 \; \forall i \in M \rbrace;</math> : <math>g_i(x) = (Ax-b)_i = \langle A_{i, \Box}, x \rangle - b_i.</math> <math>d^{**} = \langle y^*, b \rangle = \min\limits_{A^T y = c, \; y \geqslant \bar{0}} \langle y,b \rangle = \min\limits_{A^T y - c \leqslant 0, \; -A^T y + c \leqslant 0, \; -y \leqslant \bar{0}} \langle y,b \rangle = \min\limits_{y \in Y} f'(x)</math>, где : <math> f'(x) = \langle y,b \rangle; \qquad Y = \lbrace y \in \mathbb{R}^m | g'_i(y) \leqslant 0 \; \forall i \in M \rbrace;</math> : <math>g'_i(y) = (A^T y-c)_i = \langle y, A_{\Box, i} \rangle - c_i, \; i=\overline{1,n}</math> : <math> g'_{n+i}(y) = (- A^T y + c)_i = - \langle y, A_{\Box, i} \rangle + c_i, \; i=\overline{1,n} </math> : <math> g'_{2n+i}(y) = -y_i \; i=\overline{1,m}</math> В силу теоремы Каруша-Куна-Таккера <math>d^* = \langle c, x^* \rangle = \max\limits_{Ax \leqslant b, \; x \in \mathbb{R}^n} \langle c,x \rangle \quad \Leftrightarrow \quad \exists \lambda \in \mathbb{R}^m_+ : \begin{cases} grad_x L_1(x^*, \lambda) = 0 \\ \langle \lambda, g(x^*) \rangle = 0 \end{cases} \quad (3);</math> <math>d^{**} = \langle y^*, b \rangle = \min\limits_{A^T y = c, \; y \geqslant \bar{0}} \langle y,b \rangle \quad \Leftrightarrow \quad \underbrace{\exists \lambda'_1, \lambda'_2 \in \mathbb{R}^n_+, \exists \lambda'_3 \in \mathbb{R}^m_+}_{\lambda' = (\lambda'_1, \lambda'_2, \lambda'_3)} : \begin{cases} grad_y L_2(y^*, \lambda') = 0 \\ \langle \lambda', g'(y^*) \rangle = 0 \end{cases} \quad (4).</math> Докажем, что из условий <math>(3)</math> следуют условия <math>(4)</math>. Пусть <math>\exists \lambda \in \mathbb{R}^m_+ : \begin{cases} grad_x L_1(x^*, \lambda) = 0 \\ \langle \lambda, g(x^*) \rangle = 0 \end{cases}.</math> Тогда <math>\exists y^* = \lambda, \exists \lambda'_1 = |x^*| \in \mathbb{R}^n_+</math> (имеется в виду вектор из модулей элементов <math>x^*</math>), <math>\exists \lambda'_2 = |x^*| + x^* \in \mathbb{R}^n_+, \exists \lambda'_3 = b - A x^* \in \mathbb{R}^m_+ </math> такие, что : <math>L_2(y^*, \lambda') = \langle y^*, b \rangle + \langle |x^*|, A^T y^* -c \rangle + \langle |x^*| + x^*, c- A^T y^* \rangle + \langle b-A x^*, -y^* \rangle = \langle y^*, b \rangle + \langle x^*, c- A^T y^* \rangle + \langle b-A x^*, -y^* \rangle = </math> : <math>\langle c, x^* \rangle - \langle y^*, A x^* - b \rangle + \langle b-A x^*, -y^* \rangle = \langle c, x^* \rangle = - L_1(x^*, y^*),</math> так как : <math>L_1(x^*, y^*) = L_1(x^*, \lambda) = - \langle c, x^* \rangle + \langle \lambda, \underbrace{A x^* - b}_{0} \rangle = - \langle c, x^* \rangle.</math> Получаем, что <math>grad_y L_2(y^*, \lambda') = grad_x (- L_1(x^*, y^*)) = - grad_x L_1(x^*, \lambda) = 0.</math> - из равенства значений функции в точке не следует равенство градиентов, это неверно Следовательно, <math>grad_x L_1(x^*, \lambda) = -c + A^T y^* = 0.</math> Учитывая условие <math>\langle \lambda, g(x^*) \rangle = 0</math>, получим равенство <math>\langle \lambda', g'(y^*) \rangle = 0.</math> С другой стороны, <math>\langle \lambda', g'(y^*) \rangle = \langle x^*, c \rangle - \langle b, y^* \rangle</math>. Поэтому из равенства <math>\langle \lambda', g'(y^*) \rangle = 0</math> следует, что <math>\langle x^*, c \rangle = \langle b, y^* \rangle</math> Таким образом, из разрешимости прямой задачи ЛП следует разрешимость задачи, двойственной к ней, причём <math> d^* = \langle x^*, c \rangle = \langle b, y^* \rangle = d^{**}.</math> С учётом того, что задача, двойственная к двойственной, совпадает с прямой (см. [[Методы оптимизации, задачи#Задача 7|Задачу 7]]), верно и обратное. Таким образом, теорема двойственности полностью доказана. ==Построение задачи, двойственной к озЛП== ===Алгоритм === Пусть дана озЛП <math>\max\limits_{z \in \mathbb{R}^{n}}: Ax \leqslant b</math>. Для построения двойственной задачи необходимо выполнить следующие шаги. # Привести знаки неравенств в системе ограничений прямой задачи в соответствии с целевой функцией. # Ввести новые переменные: <math>u_{j}, j = \overline{0 .. m},\ m </math> — число ограничений в прямой задаче. # Определить область допустимых значений каждой из переменных двойственной задачи, исходя из следующего правила: #*<math>u_{j} \geqslant 0</math>, если <math>i</math>-ое ограничение прямой задачи является неравенством; #*<math>u_{j} \in \mathbb{R}</math>, если <math>i</math>-ое ограничение прямой задачи является равенством. # Определить матрицу коэффициентов системы ограничений двойственной задачи путем транспонирования матрицы коэффициентов системы ограничений прямой задачи: <math>A_r = A^T</math>. # Определить свободные числа системы ограничений двойственной задачи как равные коэффициентам при неизвестных в целевой функции прямой задачи. # Записать систему ограничений двойственной задачи, определяя вид каждого ограничения на основании следующего правила: #*<math>j</math>-ое ограничение двойственной задачи является неравенством, если <math>x_j \geqslant 0</math> в прямой задаче; #*<math>j</math>-ое ограничение двойственной задачи является неравенством, если <math>x_j \in \mathbb{R}</math>. # Опредить коэффициенты при неизвестных целевой функции двойственной задачи, равные соответствующим свободным числам системы ограничений исходной задачи. # Записать целевую функцию двойственной задачи, как "противоположную" целевой функции прямой задачи (например, <math>\max \rightarrow \min</math>). === Пример === Пусть дана озЛП: <math> f(x)= 5x_1 - 2x_2 + 7x_3 +4x_4 - 3x_5 = \langle c, x \rangle \rightarrow \max. </math> <math> \begin{cases} 4x_1 + x_2 - x_3 + x_4 \leqslant 2 \\ 5x_2 + x_3 - 6x_4 +2x_5 = 4\\ 2x_1 +3x_2 +6x_3 +x_4 -3x_5 \leqslant 5 \\ x_2, x_5 \geqslant 0 \\ \end{cases} </math> В матричных обозначениях: <math> \max\limits_{x \in \mathbb{R}^{n},\ Ax \leqslant b} \langle c, x \rangle </math> <math> A = \begin{pmatrix} 4 & 1 & -1 & 1 & 0 \\ 0 & 5 & 1 & -6 & 2 \\ 2 & 3 & 6 & 1 & -3 \\ \end{pmatrix} </math>, <math> b = \begin{pmatrix} 2 \\ 4 \\ 5 \\ \end{pmatrix} </math>, <math> c_r = \begin{pmatrix} 5 \\ -2 \\ 7 \\ 4 \\ -3 \\ \end{pmatrix}</math> Построим двойственную к ней задачу. # Не требуется. # Введём <math>u_j, j = \overline{1 .. 3}</math>. # <math> A_r = A^T = \begin{pmatrix} 4 & 0 & 2 \\ 1 & 5 & 3 \\ -1 & 1 & 6 \\ 1 & -6 & 1 \\ 0 & 2 & -3 \\ \end{pmatrix}</math> # <math> b_r = \begin{pmatrix} 5 \\ -2 \\ 7 \\ 4 \\ -3 \\ \end{pmatrix} </math>, <math> c_r = \begin{pmatrix} 2 \\ 4 \\ 5 \\ \end{pmatrix}</math> Окончательно имеем: <math> g(u)= 2u_1 +4u_2 +5u_3 = \langle u, b \rangle \rightarrow \min </math> <math> \begin{cases} 4u_1+2u_3=5 \\ u_1 +5u_2 +3u_3 \geqslant -2 \\ -u_1 + u_2 + 6u_3=7\\ u_1 -6u_2 + u_3=4 \\ 2u_2 - 3u_3 \geqslant -3 \\ u_1, u_3 \geqslant 0 \\ \end{cases} </math> В матричных обозначениях: <math> \min\limits_{u \in \mathbb{R}^{n},\ A_ru \geqslant b_r}\langle c_r, x \rangle </math> {{Курс Методы оптимизации}}

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

• Шаблон:Курс Методы оптимизации