Редактирование: Методы оптимизации, задачи
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 258: | Строка 258: | ||
Таким образом, из разрешимости прямой задачи ЛП следует разрешимость задачи, двойственной к ней, причём <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: | Строка 267: | ||
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: | Строка 276: | ||
2 & 3 & 6 & 1 & -3 \\ | 2 & 3 & 6 & 1 & -3 \\ | ||
\end{pmatrix} | \end{pmatrix} | ||
- | + | ||
b = | b = | ||
\begin{pmatrix} | \begin{pmatrix} | ||
Строка 318: | Строка 283: | ||
5 \\ | 5 \\ | ||
\end{pmatrix} | \end{pmatrix} | ||
- | </math> | + | </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> | ||
\begin{cases} | \begin{cases} | ||
Строка 377: | Строка 300: | ||
\end{cases} | \end{cases} | ||
</math> | </math> | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
{{Курс Методы оптимизации}} | {{Курс Методы оптимизации}} |