Редактирование: Методы оптимизации, задачи
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 39: | Строка 39: | ||
Замечание: нет смысла искать делители до N-1, достаточно рассматривать делители до целой части sqrt(N) | Замечание: нет смысла искать делители до N-1, достаточно рассматривать делители до целой части sqrt(N) | ||
- | |||
- | Замечание к замечанию: на вычисление sqrt(n) тоже требуется время, которое нужно учитывать. Если лень, то смело можно ограничить [N/2] | ||
== Задача 3 == | == Задача 3 == | ||
Строка 55: | Строка 53: | ||
# При k = 2: | # При k = 2: | ||
- | : <math>y_1 \vee y_2 = (y_1 \vee y_2 \vee \bar{u}) \wedge (y_1 \vee | + | : <math>y_1 \vee y_2 = (y_1 \vee y_2 \vee \bar{u}) \wedge (y_1 \vee u_1 \vee u).</math> |
При этом переменные <math>u</math> являются фиктивными, то есть такая замена является эквивалентной (в отличие от замены для случая k = 3). Таким образом, эти три преобразования позволяют полиномиально свести задачу ВЫП к задаче 3-ВЫП. | При этом переменные <math>u</math> являются фиктивными, то есть такая замена является эквивалентной (в отличие от замены для случая k = 3). Таким образом, эти три преобразования позволяют полиномиально свести задачу ВЫП к задаче 3-ВЫП. | ||
+ | |||
+ | |||
== Задача 4 == | == Задача 4 == | ||
Строка 109: | Строка 109: | ||
\end{pmatrix}.</math> | \end{pmatrix}.</math> | ||
- | Таким образом, для кодирования входа озЛП в любом случае необходимо закодировать числа <math>a_{i,j}, b_i, | + | Таким образом, для кодирования входа озЛП в любом случае необходимо закодировать числа <math>a_{i,j}, b_i, _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>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> | ||
Строка 123: | Строка 123: | ||
Эту сумму можно оценить сверху величиной <math>\prod\limits_{i=1}^k \sum\limits_{j=1}^k \tilde{d}{}_{i,j},</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} \ | + | <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} \sum\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> ч.т.д. | Итак, <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 == | == Задача 7 == | ||
Строка 247: | Строка 249: | ||
- | Получаем, что <math>grad_y L_2(y^*, \lambda') = grad_x (- L_1(x^*, y^*)) = - grad_x L_1(x^*, \lambda) = 0.</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>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(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>\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> | ||
Строка 258: | Строка 260: | ||
Таким образом, из разрешимости прямой задачи ЛП следует разрешимость задачи, двойственной к ней, причём <math> d^* = \langle x^*, c \rangle = \langle b, y^* \rangle = d^{**}.</math> С учётом того, что задача, двойственная к двойственной, совпадает с прямой (см. [[Методы оптимизации, задачи#Задача 7|Задачу 7]]), верно и обратное. Таким образом, теорема двойственности полностью доказана. | Таким образом, из разрешимости прямой задачи ЛП следует разрешимость задачи, двойственной к ней, причём <math> d^* = \langle x^*, c \rangle = \langle b, y^* \rangle = d^{**}.</math> С учётом того, что задача, двойственная к двойственной, совпадает с прямой (см. [[Методы оптимизации, задачи#Задача 7|Задачу 7]]), верно и обратное. Таким образом, теорема двойственности полностью доказана. | ||
- | ==Построение задачи | + | == Построение двойственной задачи == |
- | + | ''пример взят [http://first.boom.ru/Products/Theory/twiced.htm отсюда]'' | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
+ | Пусть дана озЛП: <math>f(x)= 5x_1 - 2x_2 + 7x_3 +4x_4 - 3x_5 = \langle c, x \rangle</math>, требуется найти ее максимум <math>\max f(x)</math> при условиях: | ||
<math> | <math> | ||
\begin{cases} | \begin{cases} | ||
Строка 293: | Строка 269: | ||
5x_2 + x_3 - 6x_4 +2x_5 = 4\\ | 5x_2 + x_3 - 6x_4 +2x_5 = 4\\ | ||
2x_1 +3x_2 +6x_3 +x_4 -3x_5 \leqslant 5 \\ | 2x_1 +3x_2 +6x_3 +x_4 -3x_5 \leqslant 5 \\ | ||
- | x_2, x_5 \geqslant 0 \\ | + | x_2, x_5 \geqslant 0\\ |
\end{cases} | \end{cases} | ||
- | </math> | ||
- | |||
- | |||
- | В матричных обозначениях: | ||
- | |||
- | <math> | ||
- | \max\limits_{x \in \mathbb{R}^{n},\ Ax \leqslant b} \langle c, x \rangle | ||
- | </math> | ||
- | <math> | ||
A = | A = | ||
\begin{pmatrix} | \begin{pmatrix} | ||
Строка 311: | Строка 278: | ||
2 & 3 & 6 & 1 & -3 \\ | 2 & 3 & 6 & 1 & -3 \\ | ||
\end{pmatrix} | \end{pmatrix} | ||
- | + | ||
b = | b = | ||
\begin{pmatrix} | \begin{pmatrix} | ||
Строка 318: | Строка 285: | ||
5 \\ | 5 \\ | ||
\end{pmatrix} | \end{pmatrix} | ||
- | + | </math> | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
+ | Построим двойственную задачу: | ||
- | + | # ставим задачу минимизации: берем новые переменны (<math>u</math>), в качестве коэффициентов выступает столбец <math>b</math> из основной задачи: <math>g(u)= 2u_1 +4u_2 +5u_3 = \langle u, b \rangle</math>, находим минимум <math>\min g(u)</math> | |
- | + | # теперь надо записать условия в виде <math>A^T u = c</math> | |
- | + | # условия получаем путем транспонирования исходной матрицы, при этом знаки неравенства смотрятся исходя из последнего уравнения в исходной матрице. в качестве столбца значений берутся коэффициенты из <math>f(x)</math>: | |
- | # | + | |
- | + | ||
- | + | ||
- | + | ||
- | \ | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | \ | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | </math> | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | <math> | + | |
- | + | ||
- | </math> | + | |
- | + | ||
<math> | <math> | ||
\begin{cases} | \begin{cases} | ||
Строка 377: | Строка 302: | ||
\end{cases} | \end{cases} | ||
</math> | </math> | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
{{Курс Методы оптимизации}} | {{Курс Методы оптимизации}} |