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

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

Версия от 20:01, 8 июня 2009; StepLg (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Задача 1
2 Задача 2
3 Задача 3
4 Задача 4
5 Задача 5
6 Задача 6
7 Задача 7
8 Задача 8
9 Построение двойственной задачи

Задача 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).$

Задача 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 u_1 \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, _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} \sum\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 \leqslant \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},$ ч.т.д.

Построение двойственной задачи

пример взят отсюда

Пусть дана озЛП: $f(x)= 5x_1 - 2x_2 + 7x_3 +4x_4 - 3x_5 = \langle c, x \rangle$ , требуется найти ее максимум $max f (x)$ при условиях: $\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} 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}$

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

ставим задачу минимизации: берем новые переменны ( $u$ ), в качестве коэффициентов выступает столбец $b$ из основной задачи: $g(u)= 2u_1 +4u_2 +5u_3 = \langle u, b \rangle$ , находим минимум $min g (u)$
теперь надо записать условия в виде $A T u = c$
условия получаем путем транспонирования исходной матрицы, при этом знаки неравенства смотрятся исходя из последнего уравнения в исходной матрице. в качестве столбца значений берутся коэффициенты из $f (x)$ :

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