Редактирование: Методы оптимизации, задачи
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 30 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 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]]), верно и обратное. Таким образом, теорема двойственности полностью доказана. | ||
- | ==Построение | + | == Построение двойственной задачи == |
- | ===Алгоритм === | + | |
+ | === Алгоритм === | ||
Пусть дана озЛП | Пусть дана озЛП | ||
Строка 275: | Строка 276: | ||
# Определить свободные числа системы ограничений двойственной задачи как равные коэффициентам при неизвестных в целевой функции прямой задачи. | # Определить свободные числа системы ограничений двойственной задачи как равные коэффициентам при неизвестных в целевой функции прямой задачи. | ||
# Записать систему ограничений двойственной задачи, определяя вид каждого ограничения на основании следующего правила: | # Записать систему ограничений двойственной задачи, определяя вид каждого ограничения на основании следующего правила: | ||
- | #*<math>j</math>-ое ограничение двойственной задачи является неравенством, если <math>x_j \ | + | #*<math>j</math>-ое ограничение двойственной задачи является неравенством, если <math>x_j \leqslant 0</math> в прямой задаче; |
#*<math>j</math>-ое ограничение двойственной задачи является неравенством, если <math>x_j \in \mathbb{R}</math>. | #*<math>j</math>-ое ограничение двойственной задачи является неравенством, если <math>x_j \in \mathbb{R}</math>. | ||
# Опредить коэффициенты при неизвестных целевой функции двойственной задачи, равные соответствующим свободным числам системы ограничений исходной задачи. | # Опредить коэффициенты при неизвестных целевой функции двойственной задачи, равные соответствующим свободным числам системы ограничений исходной задачи. | ||
Строка 301: | Строка 302: | ||
<math> | <math> | ||
- | \max\limits_{ | + | \max\limits_{z \in \mathbb{R}^{n}}: Ax \leqslant b |
</math> | </math> | ||
Строка 318: | Строка 319: | ||
5 \\ | 5 \\ | ||
\end{pmatrix} | \end{pmatrix} | ||
- | + | </math> | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
Строка 351: | Строка 344: | ||
4 \\ | 4 \\ | ||
-3 \\ | -3 \\ | ||
- | \end{pmatrix} | ||
- | </math>, <math> | ||
- | c_r = | ||
- | \begin{pmatrix} | ||
- | 2 \\ | ||
- | 4 \\ | ||
- | 5 \\ | ||
\end{pmatrix}</math> | \end{pmatrix}</math> | ||
- | + | # Окончательно имеем: | |
- | + | ||
- | Окончательно имеем: | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
<math> | <math> | ||
\begin{cases} | \begin{cases} | ||
Строка 377: | Строка 356: | ||
\end{cases} | \end{cases} | ||
</math> | </math> | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
{{Курс Методы оптимизации}} | {{Курс Методы оптимизации}} |