Редактирование: Методы оптимизации, задачи
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 30 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 257: | Строка 257: | ||
Таким образом, из разрешимости прямой задачи ЛП следует разрешимость задачи, двойственной к ней, причём <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: | Строка 273: | ||
# Определить свободные числа системы ограничений двойственной задачи как равные коэффициентам при неизвестных в целевой функции прямой задачи. | # Определить свободные числа системы ограничений двойственной задачи как равные коэффициентам при неизвестных в целевой функции прямой задачи. | ||
# Записать систему ограничений двойственной задачи, определяя вид каждого ограничения на основании следующего правила: | # Записать систему ограничений двойственной задачи, определяя вид каждого ограничения на основании следующего правила: | ||
- | #*<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>. | ||
# Опредить коэффициенты при неизвестных целевой функции двойственной задачи, равные соответствующим свободным числам системы ограничений исходной задачи. | # Опредить коэффициенты при неизвестных целевой функции двойственной задачи, равные соответствующим свободным числам системы ограничений исходной задачи. | ||
# Записать целевую функцию двойственной задачи, как "противоположную" целевой функции прямой задачи (например, <math>\max \rightarrow \min</math>). | # Записать целевую функцию двойственной задачи, как "противоположную" целевой функции прямой задачи (например, <math>\max \rightarrow \min</math>). | ||
+ | |||
+ | |||
=== Пример === | === Пример === | ||
Строка 319: | Строка 319: | ||
\end{pmatrix} | \end{pmatrix} | ||
</math>, <math> | </math>, <math> | ||
- | + | c_r = | |
\begin{pmatrix} | \begin{pmatrix} | ||
5 \\ | 5 \\ |