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

Материал из 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 =
\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:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

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

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

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

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

Получено с http://esyr.us/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8%2C_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8

Текущая версия		Ваш текст
Строка 35:		Строка 35:
	Следовательно, деление «столбиком» имеет сложность <math>O(n^2)</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>	+	Итого, сложность всего алгоритма равна <math>T(n) = (N - 2) \cdot O(n^2) = O(2^N) \cdot O(n^2) = O(n^2 \cdot 2^n).</math>
		+
		+

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

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

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты