2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 двойственные переменные
Сообщение30.06.2018, 18:34 


07/10/15

2400
Помогите пожалуйста разобраться с задачей линейного программирования. Возникает какая то путаница, и не могу понять в чём дело.
Есть следующая ЗЛП:
$$\left\{
\begin{array}{rcl}
 X\cdot b + I\cdot e^+ -I \cdot e^-=u& \\
 c'\cdot b + 1'\cdot e^+\to min& \\
b\geqslant 0, e^+\geqslant0, e^-\geqslant 0\\
\end{array}
\right.$$

где $b$, $e^+$, $e^-$ - векторы, с положительными элементами, $c$ - вектор произвольных вещественных коэффициентов, $I$ - единичная матрица, $1'$ - строка из единиц.

Двойственная ей задача имеет вид:
$$\left\{
\begin{array}{rcl}
 X'\cdot a \leqslant c  \\
 a\leqslant 1 \\
 a\geqslant 0 \\
u'a\to max \\
\end{array}
\right.$$

После решения основной задачи, не совсем понятно, где в решении находятся двойственные переменные $a$.
Казалось бы, в строке функционала, под переменными $e^-$, там где в исходной таблице были нули.
Но $e^-$ нельзя рассматривать как дополнительные переменные задачи, на месте которых получается двойственное решение, так как в исходной задаче перед ними стоят коэффициенты "-1", а не "1".

Можно всё привести в соответствие и всю матрицу ограничений домножить на "-1". Тогда исходная задача
$$\left\{
\begin{array}{rcl}
 -X\cdot b - I\cdot e^++I \cdot e^-=-u& \\
 c'\cdot b + 1'\cdot e^+\to min& \\
b\geqslant 0, e^+\geqslant0, e^-\geqslant 0\\
\end{array}
\right.$$
двойственная ей задача
$$\left\{
\begin{array}{rcl}
 -X'\cdot a^* \leqslant c  \\
 -a^*\leqslant 1 \to a^*\geqslant -1\\
 a^*\leqslant 0 \\
-u'a^*\to max \\
\end{array}
\right.$$

где $a^*$- это уже другие двойственные переменные, причём $a^*=-a$.

Теперь всё как положено. Получается, что на месте переменных $e^-$ после оптимизации симплекс-таблицы будут значения двойственных переменных $a^*$.

Но, при достижении оптимального решения, в задаче на минимум, все элементы строки функционала будут положительными, это собственно и есть признак достижения оптимального решения. В то время как $a^*$ ограничены, $-1\leqslant a^* \leqslant 0$, и они не могут быть положительными. Равно как $a$ не могут быть отрицательными.

В чём здесь ошибка?

 Профиль  
                  
 
 Re: двойственные переменные
Сообщение01.07.2018, 00:16 


07/10/15

2400
Сейчас всё перепроверил, посмотрел в литературе, получается - двойственная задача составлена правильно.
Смотрел примеры в сети, правда для других задач, в них двойственные переменные почему то получаются как я и думал, на месте дополнительных переменных.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group