| Текущая версия |
Ваш текст |
| Строка 1: |
Строка 1: |
| - | == Задача 1 == | + | == [[Методы оптимизации, 01 лекция (от 08 февраля)|Лекция 1]] == |
| | | | |
| | + | '''Задача 1'''. Предложить (неизбыточную) кодировку для задачи коммивояжёра и оценить длину входа. |
| | | | |
| - | '''Условие.''' Предложить неизбыточную кодировку задачи коммивояжёра. Дать оценку длины входа и сравнить её с <math>m + \lceil\log_2 B \rceil + \max\limits_{i,j} \lceil\log_2 d_{i,j}\rceil</math>. | + | '''Задача 2'''. Дать алгоритм распознавания простоты числа, оценить временную сложность алгоритма. Что такое задача распознавания простоты числа — есть N, на выходе должны получить «да» — N простое, «нет» — N составное. |
| - | | + | |
| - | | + | |
| - | '''Решение.''' Пусть 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 =
| + | |
| - | \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>
| + | |
| - | | + | |
| | | | |
| | {{Курс Методы оптимизации}} | | {{Курс Методы оптимизации}} |
