Текущая версия |
Ваш текст |
Строка 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 y_2 \vee u).</math> | + | : <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, c_j (i=\bar{1,m}, j=\bar{1,n})</math>, а также само число n для последующего восстановления размерности матрицы. Кроме того, в кодировку необходимо добавить разделители между числами, или указать число бит, выделяемое на кодирование каждого числа, или ещё каким-либо способом предоставить возможность однозначной расшифровки чисел. В свою очередь, при кодировании самих чисел в общем случае необходимо закодировать их знак и дробную часть. Получается, что даже в простейшем случае, когда все числа являются целыми и неотрицательными (а битовая длина целого неотрицательного числа k есть число, не меньшее <math>\log_2 (k+1)</math>), длину входа озЛП можно оценить снизу следующим образом: | + | Таким образом, для кодирования входа озЛП в любом случае необходимо закодировать числа <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} \prod\limits_{j=1}^{n+1} ( d_{i,j} +1). </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} \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 = \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>\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: |
| | | |
| | | |
- | == Задача 9 ==
| + | == Построение двойственной задачи == |
- | | + | |
- | | + | |
- | '''Условие.''' Применить теорему Каруша-Куна-Таккера к озЛП; с помощью этой же теоремы доказать теорему двойственности для озЛП.
| + | |
- | | + | |
- | | + | |
- | '''Решение.''' Пусть дана прямая задача ЛП в основной форме и двойственная к ней:
| + | |
- | | + | |
- | <math>d^* = \langle c, x^* \rangle = \max\limits_{Ax \leqslant b, \; x \in \mathbb{R}^n} \langle c,x \rangle \quad (1);</math>
| + | |
- | <math>d^{**} = \langle y^*, b \rangle = \min\limits_{A^T y = c, \; y \geqslant \bar{0}} \langle y,b \rangle \quad (2).</math>
| + | |
- | | + | |
- | | + | |
- | Приведём их к виду, пригодному для применения теоремы Каруша-Куна-Таккера:
| + | |
- | | + | |
- | <math>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)</math>, где
| + | |
- | : <math> f(x) = - \langle c,x \rangle; \qquad X = \lbrace x \in \mathbb{R}^n | g_i(x) \leqslant 0 \; \forall i \in M \rbrace;</math>
| + | |
- | : <math>g_i(x) = (Ax-b)_i = \langle A_{i, \Box}, x \rangle - b_i.</math>
| + | |
- | | + | |
- | | + | |
- | <math>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)</math>, где
| + | |
- | : <math> f'(x) = \langle y,b \rangle; \qquad Y = \lbrace y \in \mathbb{R}^m | g'_i(y) \leqslant 0 \; \forall i \in M \rbrace;</math>
| + | |
- | : <math>g'_i(y) = (A^T y-c)_i = \langle y, A_{\Box, i} \rangle - c_i, \; i=\overline{1,n}</math>
| + | |
- | : <math> g'_{n+i}(y) = (- A^T y + c)_i = - \langle y, A_{\Box, i} \rangle + c_i, \; i=\overline{1,n} </math>
| + | |
- | : <math> g'_{2n+i}(y) = -y_i \; i=\overline{1,m}</math>
| + | |
- | | + | |
- | | + | |
- | В силу теоремы Каруша-Куна-Таккера
| + | |
- | | + | |
- | <math>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);</math>
| + | |
- | | + | |
- | | + | |
- | <math>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).</math>
| + | |
- | | + | |
- | | + | |
- | Докажем, что из условий <math>(3)</math> следуют условия <math>(4)</math>.
| + | |
- | | + | |
- | Пусть <math>\exists \lambda \in \mathbb{R}^m_+ : \begin{cases} grad_x L_1(x^*, \lambda) = 0 \\ \langle \lambda, g(x^*) \rangle = 0 \end{cases}.</math>
| + | |
- | | + | |
- | Тогда <math>\exists y^* = \lambda, \exists \lambda'_1 = |x^*| \in \mathbb{R}^n_+</math> (имеется в виду вектор из модулей элементов <math>x^*</math>), <math>\exists \lambda'_2 = |x^*| + x^* \in \mathbb{R}^n_+, \exists \lambda'_3 = b - A x^* \in \mathbb{R}^m_+ </math> такие, что
| + | |
- | | + | |
- | : <math>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 = </math>
| + | |
- | : <math>\langle c, x^* \rangle - \langle y^*, A x^* - b \rangle + \langle b-A x^*, -y^* \rangle = \langle c, x^* \rangle = - L_1(x^*, y^*),</math> так как
| + | |
- | : <math>L_1(x^*, y^*) = L_1(x^*, \lambda) = - \langle c, x^* \rangle + \langle \lambda, \underbrace{A x^* - b}_{0} \rangle = - \langle c, x^* \rangle.</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>\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> 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 \geqslant 0</math> в прямой задаче;
| + | |
- | #*<math>j</math>-ое ограничение двойственной задачи является неравенством, если <math>x_j \in \mathbb{R}</math>.
| + | |
- | # Опредить коэффициенты при неизвестных целевой функции двойственной задачи, равные соответствующим свободным числам системы ограничений исходной задачи.
| + | |
- | # Записать целевую функцию двойственной задачи, как "противоположную" целевой функции прямой задачи (например, <math>\max \rightarrow \min</math>).
| + | |
- | | + | |
- | === Пример ===
| + | |
- | | + | |
- | Пусть дана озЛП:
| + | |
- | | + | |
- | <math>
| + | |
- | f(x)= 5x_1 - 2x_2 + 7x_3 +4x_4 - 3x_5 = \langle c, x \rangle \rightarrow \max.
| + | |
- | </math>
| + | |
- | | + | |
- | <math>
| + | |
- | \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}
| + | |
- | </math>
| + | |
- | | + | |
- | | + | |
- | В матричных обозначениях:
| + | |
- | | + | |
- | <math>
| + | |
- | \max\limits_{x \in \mathbb{R}^{n},\ Ax \leqslant b} \langle c, x \rangle
| + | |
- | </math>
| + | |
- | | + | |
- | <math>
| + | |
- | A =
| + | |
- | \begin{pmatrix}
| + | |
- | 4 & 1 & -1 & 1 & 0 \\
| + | |
- | 0 & 5 & 1 & -6 & 2 \\
| + | |
- | 2 & 3 & 6 & 1 & -3 \\
| + | |
- | \end{pmatrix}
| + | |
- | </math>, <math>
| + | |
- | b =
| + | |
- | \begin{pmatrix}
| + | |
- | 2 \\
| + | |
- | 4 \\
| + | |
- | 5 \\
| + | |
- | \end{pmatrix}
| + | |
- | </math>, <math>
| + | |
- | c =
| + | |
- | \begin{pmatrix}
| + | |
- | 5 \\
| + | |
- | -2 \\
| + | |
- | 7 \\
| + | |
- | 4 \\
| + | |
- | -3 \\
| + | |
- | \end{pmatrix}</math>
| + | |
- | | + | |
- | | + | |
- | | + | |
- | Построим двойственную к ней задачу.
| + | |
- | | + | |
- | # Не требуется.
| + | |
- | # Введём <math>u_j, j = \overline{1 .. 3}</math>.
| + | |
- | # <math>
| + | |
- | A_r = A^T =
| + | |
- | \begin{pmatrix}
| + | |
- | 4 & 0 & 2 \\
| + | |
- | 1 & 5 & 3 \\
| + | |
- | -1 & 1 & 6 \\
| + | |
- | 1 & -6 & 1 \\
| + | |
- | 0 & 2 & -3 \\
| + | |
- | \end{pmatrix}</math>
| + | |
- | # <math>
| + | |
- | b_r =
| + | |
- | \begin{pmatrix}
| + | |
- | 5 \\
| + | |
- | -2 \\
| + | |
- | 7 \\
| + | |
- | 4 \\
| + | |
- | -3 \\
| + | |
- | \end{pmatrix}
| + | |
- | </math>, <math>
| + | |
- | c_r =
| + | |
- | \begin{pmatrix}
| + | |
- | 2 \\
| + | |
- | 4 \\
| + | |
- | 5 \\
| + | |
- | \end{pmatrix}</math>
| + | |
- | | + | |
- | | + | |
- | Окончательно имеем:
| + | |
- | | + | |
- | <math>
| + | |
- | g(u)= 2u_1 +4u_2 +5u_3 = \langle u, b \rangle \rightarrow \min
| + | |
- | </math>
| + | |
- | | + | |
- | <math>
| + | |
- | \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}
| + | |
- | </math>
| + | |
- | | + | |
| | | |
- | В матричных обозначениях: | |
| | | |
- | <math> | |
- | \min\limits_{u \in \mathbb{R}^{n},\ A_ru \geqslant b_r}\langle c_r, x \rangle | |
- | </math> | |
| | | |
| | | |
| {{Курс Методы оптимизации}} | | {{Курс Методы оптимизации}} |