Редактирование: Методы оптимизации, задачи
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 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]]), верно и обратное. Таким образом, теорема двойственности полностью доказана. | ||
- | |||
- | ==Построение задачи, двойственной к озЛП== | ||
- | |||
- | ===Алгоритм === | ||
- | Пусть дана озЛП | ||
- | |||
- | <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>). | ||
=== Пример === | === Пример === | ||
Строка 319: | Строка 297: | ||
\end{pmatrix} | \end{pmatrix} | ||
</math>, <math> | </math>, <math> | ||
- | + | c_r = | |
\begin{pmatrix} | \begin{pmatrix} | ||
5 \\ | 5 \\ |