Редактирование: Методы оптимизации, задачи
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 36: | Строка 36: | ||
Итого, сложность всего алгоритма равна <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> | ||
- | |||
- | |||
- | Замечание: нет смысла искать делители до N-1, достаточно рассматривать делители до целой части sqrt(N) | ||
- | |||
- | Замечание к замечанию: на вычисление sqrt(n) тоже требуется время, которое нужно учитывать. Если лень, то смело можно ограничить [N/2] | ||
== Задача 3 == | == Задача 3 == | ||
Строка 55: | Строка 50: | ||
# При 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: | Строка 106: | ||
\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: | Строка 120: | ||
Эту сумму можно оценить сверху величиной <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 == | ||
Строка 171: | Строка 170: | ||
В итоге получаем, что | В итоге получаем, что | ||
- | <math>\max\limits_{Ax \leqslant b} \langle c,x \rangle | + | <math>\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.</math> |
Следовательно, задачи <math>(1)</math> и <math>(4)</math> совпадают, ч.т.д. | Следовательно, задачи <math>(1)</math> и <math>(4)</math> совпадают, ч.т.д. | ||
+ | |||
+ | |||
== Задача 8 == | == Задача 8 == | ||
Строка 202: | Строка 203: | ||
- | == | + | == Построение двойственной задачи == |
- | + | ''пример взят [http://first.boom.ru/Products/Theory/twiced.htm отсюда]'' | |
- | + | ||
- | '' | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
+ | Пусть дана озЛП: <math>f(x)= 5x_1 - 2x_2 + 7x_3 +4x_4 - 3x_5</math>, требуется найти ее максимум <math>\max f(x)</math> при условиях: | ||
<math> | <math> | ||
\begin{cases} | \begin{cases} | ||
Строка 293: | Строка 212: | ||
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: | Строка 221: | ||
2 & 3 & 6 & 1 & -3 \\ | 2 & 3 & 6 & 1 & -3 \\ | ||
\end{pmatrix} | \end{pmatrix} | ||
- | + | ||
b = | b = | ||
\begin{pmatrix} | \begin{pmatrix} | ||
Строка 318: | Строка 228: | ||
5 \\ | 5 \\ | ||
\end{pmatrix} | \end{pmatrix} | ||
- | + | </math> | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
+ | Построим двойственную задачу: | ||
- | + | # ставим задачу минимизации: берем новые переменны (<math>u</math>), в качестве коэффициентов выступает столбец <math>b</math> из основной задачи: <math>g(u)= 2u_1 +4u_2 +5u_3</math>, находим минимум <math>\min g(u)</math> | |
- | + | # условия получаем путем транспонирования исходной матрицы, при этом знаки неравенства смотрятся исходя из последнего уравнения в исходной матрице. в качестве столбца значений берутся коэффициенты из <math>f(x)</math>: | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | </math>, <math> | + | |
- | + | ||
- | \ | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | <math> | + | |
- | + | ||
- | </math> | + | |
- | + | ||
<math> | <math> | ||
\begin{cases} | \begin{cases} | ||
Строка 377: | Строка 244: | ||
\end{cases} | \end{cases} | ||
</math> | </math> | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
{{Курс Методы оптимизации}} | {{Курс Методы оптимизации}} |