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

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

(Различия между версиями)

Версия 05:45, 6 июня 2014

Содержание

1 Задача 1
2 Задача 2
3 Задача 3
4 Задача 4
5 Задача 5
6 Задача 6
7 Задача 7
8 Задача 8
9 Задача 9
- 9.1 Алгоритм
- 9.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 \leqslant 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_r = \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}$

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

$\min\limits_{u \in \mathbb{R}^{n},\ A_ru \geqslant b_r}\langle c_r, x \rangle$

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

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15

Календарь

	пт	пт	пт	пт	пт
Февраль		08	15	22	29
Март	06	13	20	27
Апрель	04	11	18	25
Май	02		16	23

Материалы
Упражнения || Задачи | Определения | Утверждения | Теоремы || Теормин | Обозначения

Получено с http://esyr.org/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

@@ Строка 257: / Строка 257: @@
 Таким образом, из разрешимости прямой задачи ЛП следует разрешимость задачи, двойственной к ней, причём <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 \leqslant 0</math> в прямой задаче;
+#*<math>j</math>-ое ограничение двойственной задачи является неравенством, если <math>x_j \in \mathbb{R}</math>.
+# Опредить коэффициенты при неизвестных целевой функции двойственной задачи, равные соответствующим свободным числам системы ограничений исходной задачи.
+# Записать целевую функцию двойственной задачи, как "противоположную" целевой функции прямой задачи (например, <math>\max \rightarrow \min</math>).
 === Пример ===

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

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

Версия 05:45, 6 июня 2014

Содержание

Задача 1

Задача 2

Задача 3

Задача 4

Задача 5

Задача 6

Задача 7

Задача 8

Задача 9

Алгоритм

Пример

Просмотры

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

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты