Двойственный симплекс-метод

[Annette]

Помогите разобраться (не смогла найти более или менее внятного примера, поэтому спрашиваю):
Если поставлена след. задача:
max cx
$ Ax\leqslant 1$
$ x\geqslant 0$
нужно ли вводить искусственный базис для решения этой задачи двойственным симплекс-методом? Если да, то переход от вспомогательной задачи к основной будет такой же как и в прямом симплекс-методе? И как из симплекс-таблицы можно сделать вывод о решении двойственной задачи (к данной)?
Спасибо заранее.

[AKM]

Пожалуйста, исправьте написание формул в соответствии с Правилами.
Здесь рассказано, как набирать формулы. Используйте кнопку для редактирования своего сообщения.

Тема перемещена из "Помогите решить (М)" в карантин. В теме Что такое карантин, и что нужно делать, чтобы там оказаться также описано, как исправлять ситуацию.

$ x \ge 0$:
$ x \ge 0$.

Возвращено.

[Alexey1]

Annette в сообщении #346930 писал(а):

нужно ли вводить искусственный базис для решения этой задачи двойственным симплекс-методом?

Двойственный симплекс-метод основывается на определённых предположениях о задаче. Например, для задачи
$\max c^Tx$
$Ax=b$
$x \geq 0$
должно выполнятся условие $c_{B}^{T}B^{-1}A \leq c^T$, где $c_{B}^{T}$ вектор составленный из компонент вектора $c$ соответствующих базисным переменным. При использовании прямого симплекс-метода, искусственные переменные вводятся для того, чтобы получить начальное допустимое решение $x=B^{-1}b \geq 0$. При использовании двойственного симплекс-метода условие неотрицательности не обязательно, но должно выполняться $c_{B}^{T}B^{-1}A \leq c^T$ из которого, не совсем видно, что даст введение искусственных переменных.
Двойственный симплекс-метод в основном используется тогда, когда есть допустимое решение для двойственной задачи. Например, для уже решённой обычным симплекс-методом задачи, меняется вектор $b$ так, что некоторые компоненты вектора $B^{-1}b$ отрицательны (базисное, но не допустимое решение прямой задачи). Здесь прямой симплекс-метод неприменим, а вот двойственный может начинаться с уже имеющейся симплекс-таблицы.

Annette в сообщении #346930 писал(а):

Если да, то переход от вспомогательной задачи к основной будет такой же как и в прямом симплекс-методе?

Даже если у Вас есть искусственные переменные и после решения двойственным симплекс-методом они находятся в базисе, то уже можно найти оптимальное решение для прямой задачи, то есть двойственный симплекс-метод уже не нужен и от них можно избавиться как и при прямом симплекс-методе.

Annette в сообщении #346930 писал(а):

И как из симплекс-таблицы можно сделать вывод о решении двойственной задачи (к данной)?

Если обычный симплекс-метод нашёл оптимальное решение, то это значит, что и двойственная задача решена.

[Annette]

Ok(хоть это и не прояснило алгоритм), допустим я решаю двойственную задачу прямым симплекс-методом, njulf решение прямой задачи находится из условий дополняющий нежесткости??
PS : И еще решение задачи ЛП мне нужно для решения матричной игры, мб это прояснит как-нибудь ситуацию по поводу того, какой алгоритм мне лучше всего запрограммировать

[Alexey1]

А почему Вы вообще начали говорить о двойственном симплекс-методе?
Из Вашего второго сообщения, Вам нужно просто решить задачу линейного программирования.
Если известно допустимое базисное решение, то используйте симплекс-метод (прямой).
Если допустимое базисное решение не известно, то составляйте вспомогательную задачу с $m$ ($A$ матрица размерности $m \times n$) искусственными переменными $y$:
$\min \ y_1+...+y_m$
$Ax+y=1$
$x \geq 0$
$y \geq 0$.
Решив эту задачу получите допустимое базисное решение (после того как избавитесь от искусственных переменных в базисе) для первоначальной задачи. Затем решайте задачу простым симплекс-методом.

[Annette]

Ну, вообще надо решить две взаимно двойственные задачи, решения которых как раз и будут оптимальными стратегиями; поэтому по логике вещей мне показалось, что именно этот метод и надо использовать.....

[Annette]

Значит в моем случае мне нужно решить задачу ЛП прямым симплекс-методом и из условий дополняющей нежесткости найти решение двойственной к ней (т.к. мне нужно знать оба решения), так, я правильно поняла?

[Alexey1]

Да, если Вы решите задачу линейного программирования, то решать двойственную к ней не надо. Решение двойственной задачи можно получить из решения прямой задачи.