Редактирование: Методы оптимизации, задачи
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 55: | Строка 55: | ||
# При 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 == | ||
Строка 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> | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
{{Курс Методы оптимизации}} | {{Курс Методы оптимизации}} |