Методы оптимизации, задачи

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

Содержание

1 Задача 1
2 Задача 2
3 Задача 3
4 Задача 4
5 Задача 5
6 Задача 6
7 Задача 7
8 Задача 8
9 Задача 9
10 Построение задачи, двойственной к озЛП
- 10.1 Алгоритм
- 10.2 Пример

[править] Задача 1

Условие. Предложить неизбыточную кодировку задачи коммивояжёра. Дать оценку длины входа и сравнить её с $m + \lceil\log_2 B \rceil + \max\limits_{i,j} \lceil\log_2 d_{i,j}\rceil$ .

Решение. Пусть m — число городов, B — максимальная длина маршрута, $D = {d i, j}$ — матрица расстояний между городами. Будем кодировать m, B и $d i, j$ в двоичном виде. Кроме того, включим в алфавит символ-разделитель #. Таким образом, кодировка будет состоять из двоичных записей чисел m, B и элементов $d i, j$ , между которыми находятся разделители #. При этом можно включать в кодировку не все элементы $d i, j$ , а только те, которые лежат выше главной диагонали матрицы D (поскольку в силу равенств $d i, j = d j, i$ и $d i, i = 0$ матрица D симметрична и имеет нулевую главную диагональ). Кроме того, можно не кодировать и число m, поскольку оно однозначно определяется по числу разделителей между элементами матрицы.

Для того чтобы осуществить двоичное кодирование некоторого числа N, необходимо $\lfloor \log_2 N \rfloor + 1$ символов. Таким образом, длина входа задачи коммивояжёра будет равна

$(\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.$

Кодировать число B и верхнюю часть матрицы D надо в любом случае; двоичное кодирование неизбыточно; разделителей мы добавили лишь полиномиальное число (порядка $\frac{m^2}{2}$ ). Поэтому кодировка является неизбыточной.

Оценка $m + \lceil\log_2 B \rceil + \max\limits_{i,j} \lceil\log_2 d_{i,j}\rceil$ лучше предложенной, но вряд ли достижима.

[править] Задача 2

Условие. Дать алгоритм распознавания простоты числа и оценить его временную сложность.

Решение. Будем считать, что исходное число N вводится в двоичном виде. Для того, чтобы проверить его на простоту, будем делить его поочерёдно на 2, 3, ..., N-1 и рассматривать остатки от делений. Если на очередном шаге остаток получился равным нулю, то процесс можно не продолжать — рассматриваемое число не являеся простым; если же мы произвели все деления и не получили ни одного нулевого остатка, то число является простым.

Таким образом, в худшем случае (когда рассматриваемое число — простое) получаем N-2 деления.

Деление будем производить «столбиком». Пусть мы делим некоторое число a на некоторое число b (с соответствующими битовыми длинами $m a$ и $m b$ ). Тогда на каждое вычитание двоичных строк потребуется, грубо говоря, $2(m b + 1)$ битовых операций (непосредственно вычитания плюс проверки); всего же таких итераций будет не больше, чем $m a - m b + 1.$

Получаем, что $t(m_a, m_b) \leqslant 2(m_b + 1)(m_a - m_b + 1).$

$2(m_b + 1)(m_a - m_b + 1) \leqslant 2(m+1)m = 2m^2 + 2m.$

Следовательно, деление «столбиком» имеет сложность $O (n 2)$ .

Итого, сложность всего алгоритма равна $T(n) = (N - 2) \cdot O(n^2) = O(2^n) \cdot O(n^2) = O(n^2 \cdot 2^n).$

Замечание: нет смысла искать делители до N-1, достаточно рассматривать делители до целой части sqrt(N)

Замечание к замечанию: на вычисление sqrt(n) тоже требуется время, которое нужно учитывать. Если лень, то смело можно ограничить [N/2]

[править] Задача 3

Условие. Завершить доказательство утверждения 9 (§3 методички) для случая k = 1, 2.

Решение. В том случае, когда дизъюнктивные функции, входящие в КНФ задачи о выполнимости, зависят от одной или двух переменных, их можно представить в виде конъюнкции дизъюнктивных функций трёх переменных следующим образом:

При k = 1:

$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).$

При k = 2:

$y_1 \vee y_2 = (y_1 \vee y_2 \vee \bar{u}) \wedge (y_1 \vee y_2 \vee u).$

При этом переменные $u$ являются фиктивными, то есть такая замена является эквивалентной (в отличие от замены для случая k = 3). Таким образом, эти три преобразования позволяют полиномиально свести задачу ВЫП к задаче 3-ВЫП.

[править] Задача 4

Условие. Доказать, что задача ПЧ $\in co-\mathbb{NP}$ .

Решение. Согласно определению, задача ПЧ будет принадлежать классу $co-\mathbb{NP}$ , если дополнительная к ней задача будет принадлежать классу $\mathbb{NP}.$

Дополнительной к задаче ПЧ является задача распознавания того, является ли число (назовём его N, с битовой длиной n) составным. Для проверки этого будем использовать детерминированные машины Тьюринга, которые «столбиком» делят N на числа, соответственно, от 2 до N-1 и находят остатки от этих делений. Если хотя бы одна из ДМТ выдаст нулевой остаток, вся НДМТ останавливается — число N является составным. Если же все остатки отличны от нуля, N — простое число.

Деление «столбиком» имеет сложность порядка $O (n 2)$ (см. Задачу 2); длина каждого из слов-подсказок не превышает n, поэтому время их прочтения не больше k*n, где k — некоторый коэффициент. Следовательно, временная сложность всей НДМТ, решающей задачу о том, является ли число составным, также полиномиальна. Таким образом, эта задача принадлежит классу $\mathbb{NP}$ , а задача ПЧ принадлежит классу $co-\mathbb{NP}.$

[править] Задача 5

Условие. Свести задачу ЛП с ограничениями в канонической форме к основной задаче ЛП.

Решение. Другими словами, необходимо задачу $\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.$

Применим к ограничениям в канонической форме равносильные преобразования:

$\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}.$

Учитывая равносильность условий $x \geqslant \bar{0}$ и $- x \leqslant \bar{0}$ , получаем:

$\begin{pmatrix} - \tilde{A} \\ \tilde{A} \\ - E \end{pmatrix} x \leqslant \begin{pmatrix} - \tilde{b} \\ \tilde{b} \\ \bar{0} \end{pmatrix}.$

Получаем, что $\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$ , где $A = \begin{pmatrix} - \tilde{A} \\ \tilde{A} \\ - E \end{pmatrix}, \; b = \begin{pmatrix} - \tilde{b} \\ \tilde{b} \\ \bar{0} \end{pmatrix},$ то есть мы свели задачу ЛП с ограничениями в канонической форме к основной задаче ЛП.

[править] Задача 6

Условие. Оценить по порядку битовую длину L входа озЛП. А именно, доказать, что $L > O (ln(n Δ))$ , где $Δ = max | d e t D' |$ , $D'$ — квадратная подматрица D, D — симплекс-матрица озЛП.

Решение. Входом озЛП является симплекс-матрица D, имеющая вид

$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}.$

Таким образом, для кодирования входа озЛП в любом случае необходимо закодировать числа $a_{i,j}, b_i, c_j (i=\bar{1,m}, j=\bar{1,n})$ , а также само число n для последующего восстановления размерности матрицы. Кроме того, в кодировку необходимо добавить разделители между числами, или указать число бит, выделяемое на кодирование каждого числа, или ещё каким-либо способом предоставить возможность однозначной расшифровки чисел. В свою очередь, при кодировании самих чисел в общем случае необходимо закодировать их знак и дробную часть. Получается, что даже в простейшем случае, когда все числа являются целыми и неотрицательными (а битовая длина целого неотрицательного числа k есть число, не меньшее $log 2 (k + 1)$ ), длину входа озЛП можно оценить снизу следующим образом:

$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 // >$

$> \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 =$

$= \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,$ где

d i, j

— элементы матрицы D.

Далее, $\Delta = \max\limits_{D' \subseteq D} |det D'| = |det \tilde{D}|$ , где $\tilde{D}$ — некоторая квадратная подматрица D размерности k x k. Получаем, что

$\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|$ , где $\alpha=(\alpha_1, \ldots , \alpha_k)$ — перестановки чисел 1, ..., k, а $\sigma(\alpha) = \begin{cases} 0, \mbox{if } \alpha \mbox{ is even;} \\ 1, \mbox{if } \alpha \mbox{ is odd.} \end{cases}$ .

Следовательно, $\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}.$

Эту сумму можно оценить сверху величиной $\prod\limits_{i=1}^k \sum\limits_{j=1}^k \tilde{d}{}_{i,j},$ так как если раскрыть в ней скобки, то мы получим все необходимые произведения плюс некоторую неотрицательную часть. Таким образом,

$\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).$

Итак, $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)),$ ч.т.д.

[править] Задача 7

Условие. Доказать, что двойственная задача к двойственной совпадает с прямой задачей для озЛП.

Решение. Пусть дана прямая задача ЛП в основной форме: $\max\limits_{Ax \leqslant b} \langle c,x \rangle. \qquad (1)$

Запишем для неё двойственную задачу: $\min\limits_{\lambda A = c, \lambda \geqslant \bar{0}} \langle \lambda, b \rangle.$

Приведём эту задачу к основной форме.

$\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.$

Далее, $\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}$ .

Получаем, что

$\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,$ где $\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)$

Запишем задачу, двойственную к $(2)$ :

$- \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)$

Представим $x'$ в виде $x' = (x'_1, x'_2, x'_3); x'_1, x'_2 \in \mathbb{R}{}^n, x'_3 \in \mathbb{R}{}^m.$ Тогда

$\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 )$ = $\max\limits_{(x'_1 - x'_2) A^T - x'_3 = - b^T, \; x' \geqslant \bar{0}} \langle c^T, x'_2 - x'_1 \rangle =$

$= \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)$

Для любого $x: \; Ax \leqslant b$ положим $x_1^{'T} = \frac{|x|-x}{2}, \; x_2^{'T} = \frac{|x|+x}{2}:$

$\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.$

Для любых $x_1^{'T}, x_2^{'T} \geqslant \bar{0}$ положим $x = x_2^{'T} - x_1^{'T}:$

$\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.$

В итоге получаем, что

$\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.$

Следовательно, задачи $(1)$ и $(4)$ совпадают, ч.т.д.

[править] Задача 8

Условие. Доказать, что задача ЛП эквивалентна задаче $\hat{P}y = \hat{q}, \; y \geqslant \bar{0}.$

Решение. Любая задача ЛП может быть представлена в форме озЛП: $\max\limits_{Ax \leqslant b, \; x \in \mathbb{R}^n} \langle c,x \rangle.$

В свою очередь, в силу утверждения 4 §7 озЛП наряду с двойственной задачей $\min\limits_{\lambda A = c, \lambda \geqslant \bar{0}} \langle \lambda, b \rangle$ эквивалентна следующей системе ЛН:

$\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}.$

Представим $x$ в виде $x = x_2 - x_1; \; x_1, x_2 \in \mathbb{R}^n, \; x_1, x_2 \geqslant \bar{0}.$ Получим систему

$\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)$

Положим $\begin{pmatrix} x_1 \\ x_2 \\ \lambda^T \\ z \end{pmatrix} = y$ . Тогда система $(1)$ эквивалентна системе

$\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},$ ч.т.д.

[править] Задача 9

Условие. Применить теорему Каруша-Куна-Таккера к озЛП; с помощью этой же теоремы доказать теорему двойственности для озЛП.

Решение. Пусть дана прямая задача ЛП в основной форме и двойственная к ней:

$d^* = \langle c, x^* \rangle = \max\limits_{Ax \leqslant b, \; x \in \mathbb{R}^n} \langle c,x \rangle \quad (1);$ $d^{**} = \langle y^*, b \rangle = \min\limits_{A^T y = c, \; y \geqslant \bar{0}} \langle y,b \rangle \quad (2).$

Приведём их к виду, пригодному для применения теоремы Каруша-Куна-Таккера:

$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)$ , где

$f(x) = - \langle c,x \rangle; \qquad X = \lbrace x \in \mathbb{R}^n | g_i(x) \leqslant 0 \; \forall i \in M \rbrace;$

$g_i(x) = (Ax-b)_i = \langle A_{i, \Box}, x \rangle - b_i.$

$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)$ , где

$f'(x) = \langle y,b \rangle; \qquad Y = \lbrace y \in \mathbb{R}^m | g'_i(y) \leqslant 0 \; \forall i \in M \rbrace;$

$g'_i(y) = (A^T y-c)_i = \langle y, A_{\Box, i} \rangle - c_i, \; i=\overline{1,n}$

$g'_{n+i}(y) = (- A^T y + c)_i = - \langle y, A_{\Box, i} \rangle + c_i, \; i=\overline{1,n}$

$g'_{2n+i}(y) = -y_i \; i=\overline{1,m}$

В силу теоремы Каруша-Куна-Таккера

$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);$

$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).$

Докажем, что из условий $(3)$ следуют условия $(4)$ .

Пусть $\exists \lambda \in \mathbb{R}^m_+ : \begin{cases} grad_x L_1(x^*, \lambda) = 0 \\ \langle \lambda, g(x^*) \rangle = 0 \end{cases}.$

Тогда $\exists y^* = \lambda, \exists \lambda'_1 = |x^*| \in \mathbb{R}^n_+$ (имеется в виду вектор из модулей элементов $x *$ ), $\exists \lambda'_2 = |x^*| + x^* \in \mathbb{R}^n_+, \exists \lambda'_3 = b - A x^* \in \mathbb{R}^m_+$ такие, что

$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 =$

$\langle c, x^* \rangle - \langle y^*, A x^* - b \rangle + \langle b-A x^*, -y^* \rangle = \langle c, x^* \rangle = - L_1(x^*, y^*),$ так как

$L_1(x^*, y^*) = L_1(x^*, \lambda) = - \langle c, x^* \rangle + \langle \lambda, \underbrace{A x^* - b}_{0} \rangle = - \langle c, x^* \rangle.$

Получаем, что $g r a d y L 2 (y *,λ') = g r a d x ( - L 1 (x *, y *)) = - g r a d x L 1 (x *,λ) = 0.$ - из равенства значений функции в точке не следует равенство градиентов, это неверно

Следовательно, $g r a d x L 1 (x *,λ) = - c + A T y * = 0.$

Учитывая условие $\langle \lambda, g(x^*) \rangle = 0$ , получим равенство $\langle \lambda', g'(y^*) \rangle = 0.$

С другой стороны, $\langle \lambda', g'(y^*) \rangle = \langle x^*, c \rangle - \langle b, y^* \rangle$ . Поэтому из равенства $\langle \lambda', g'(y^*) \rangle = 0$ следует, что $\langle x^*, c \rangle = \langle b, y^* \rangle$

Таким образом, из разрешимости прямой задачи ЛП следует разрешимость задачи, двойственной к ней, причём $d^* = \langle x^*, c \rangle = \langle b, y^* \rangle = d^{**}.$ С учётом того, что задача, двойственная к двойственной, совпадает с прямой (см. Задачу 7), верно и обратное. Таким образом, теорема двойственности полностью доказана.

[править] Построение задачи, двойственной к озЛП

[править] Алгоритм

Пусть дана озЛП

$\max\limits_{z \in \mathbb{R}^{n}}: Ax \leqslant b$ .

Для построения двойственной задачи необходимо выполнить следующие шаги.

Привести знаки неравенств в системе ограничений прямой задачи в соответствии с целевой функцией.
Ввести новые переменные: $u_{j}, j = \overline{0 .. m},\ m$ — число ограничений в прямой задаче.
Определить область допустимых значений каждой из переменных двойственной задачи, исходя из следующего правила:
- $u_{j} \geqslant 0$ , если $i$ -ое ограничение прямой задачи является неравенством;
- $u_{j} \in \mathbb{R}$ , если $i$ -ое ограничение прямой задачи является равенством.
Определить матрицу коэффициентов системы ограничений двойственной задачи путем транспонирования матрицы коэффициентов системы ограничений прямой задачи: $A r = A T$ .
Определить свободные числа системы ограничений двойственной задачи как равные коэффициентам при неизвестных в целевой функции прямой задачи.
Записать систему ограничений двойственной задачи, определяя вид каждого ограничения на основании следующего правила:
- $j$ -ое ограничение двойственной задачи является неравенством, если $x_j \geqslant 0$ в прямой задаче;
- $j$ -ое ограничение двойственной задачи является неравенством, если $x_j \in \mathbb{R}$ .
Опредить коэффициенты при неизвестных целевой функции двойственной задачи, равные соответствующим свободным числам системы ограничений исходной задачи.
Записать целевую функцию двойственной задачи, как "противоположную" целевой функции прямой задачи (например, $\max \rightarrow \min$ ).

[править] Пример

Пусть дана озЛП:

$f(x)= 5x_1 - 2x_2 + 7x_3 +4x_4 - 3x_5 = \langle c, x \rangle \rightarrow \max.$

$\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}$

В матричных обозначениях:

$\max\limits_{x \in \mathbb{R}^{n},\ Ax \leqslant b} \langle c, x \rangle$

$A = \begin{pmatrix} 4 & 1 & -1 & 1 & 0 \\ 0 & 5 & 1 & -6 & 2 \\ 2 & 3 & 6 & 1 & -3 \\ \end{pmatrix}$ , $b = \begin{pmatrix} 2 \\ 4 \\ 5 \\ \end{pmatrix}$ , $c = \begin{pmatrix} 5 \\ -2 \\ 7 \\ 4 \\ -3 \\ \end{pmatrix}$

Построим двойственную к ней задачу.

Не требуется.
Введём $u_j, j = \overline{1 .. 3}$ .
$A_r = A^T = \begin{pmatrix} 4 & 0 & 2 \\ 1 & 5 & 3 \\ -1 & 1 & 6 \\ 1 & -6 & 1 \\ 0 & 2 & -3 \\ \end{pmatrix}$
$b_r = \begin{pmatrix} 5 \\ -2 \\ 7 \\ 4 \\ -3 \\ \end{pmatrix}$ , $c_r = \begin{pmatrix} 2 \\ 4 \\ 5 \\ \end{pmatrix}$

Окончательно имеем:

$g(u)= 2u_1 +4u_2 +5u_3 = \langle u, b \rangle \rightarrow \min$

$\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}$