Об условиях применимости разновидностей симплекс-метода.

[eugrita]

На тему симплекс метода и его разновидностей много ссылок в интернете.
Есть т.н. каноническая форма уравнений в виде
max F $Ax\leqslant b$
$ x \leqslant 0 $

При этом «Если ограничения исходной задачи содержат единичную матрицу порядка М, то при неотрицательности правых частей уравнения определяется первоначальный план, из которого с помощью преобразований Жордана над симплекс-таблицами находим оптимальный план.”
т.е если дополнительно $ b \geqslant 0 $
то система ограничений содержит единичную матрицу всегда и первоначальный план имеет вид
$ X_1=X_2=...X_n=0, S_1=b_1,...S_m=b_m $
(при этом предполагается неотрицательность решений).
Логично предположить, что нарушение любого из перечисленных условий
А) неотрицательность переменных, неотрицательности вектора B или замена неравенства
<= на >= хотя бы в одном уравнении приведут к отсутствию нахождения простого начального плана и как следствие применять другие разновидности метода – т.н. двухфазный или M-метод
При котором хотя бы в одно уравнение добавляется не 1 базисная а 2 переменные т.н искусственная переменная,
А в качестве критерия вспомогательный критерий, т.е в симплекс таблице становится на 1 строку больше чем обычно и дальше решается в 2 этапа….
Вроде все так. Да вот только подал я своей программе симплекс метода на вход Систему
Max F=X1+X2 При условиях
$2X_1+X_2 \leqslant 6 $
$X_1+2X_2 \leqslant 6 $
$X_1+X_2 \geqslant 2 $ /* нарушение знака*/
$X_1,X_2 \geqslant 0 $
Думал – не сработает, а она преспокойно выплюнула верное оптимальное решение
Fmax=4 при X1=X2=2 почему?
Действительно ли важна неотрицательность вектора правых частей b?
(иначе можно было бы лихо изменив знак всей строки матрицы добиться <=)
Тогда как видоизменить критерий выбора по виду матрицы и ограничений. альтернативного симплекс-метода?

[Alexey1]

Обычно симплекс-метод приводится для задачи
$\max c_1x_1+c_2x_2+...+c_nx_n$
$Ax=b$
$x \geq 0$.
То есть мы знаем как решить эту задачу симплекс-методом ($A$ - $m \times n$).
Для того, чтобы начать симплекс-метод, нам необходимо начальное решение, которое не всегда легко найти. Для этого, рассматривается вспомогательная задача
$\max y_1+y_2+...+y_m$
$Ax+y=b$
$x \geq 0$
$y \geq 0$.
И эту задачу мы тоже знаем как решать, так как она ничем не отличается от предыдущей. Однако, первоначальное решение легко найти если все компонеты вектора $b$ неотрицательны (первоначальное решение это $x=0,y=b$). Отсюда следует необходимость неотрицательности вектора $b$ в общем случае.

[eugrita]

1) извините описка. дожно быть x>=0
Cогласен , и я также думал. Но еще раз вопрос - значит ли это что это необходимо и достаточно, т.е. отрицание любого из требований канонической задачи - означает невозможность получения начального базиса и как следствие невозможность решения классическим способом? У меня получилось, что нет.
Другими словами, я пишу "всеядную" программу, рассчитывающую все виды ограничениий, вводимые пользователем. Наверно можно внутрь заложить только 2-фазный метод, а я хочу ,чтобы было 2 метода и программа сама принимала решение когда можно и применяла бы классический, а когда по необходимости двухфазный

[Alexey1]

eugrita в сообщении #312702 писал(а):

Но еще раз вопрос - значит ли это что это необходимо и достаточно, т.е. отрицание любого из требований канонической задачи - означает невозможность получения начального базиса и как следствие невозможность решения классическим способом? У меня получилось, что нет.

Вы же понимаете, что двух-фазный метод с неотрицательными $b$ это универсальный способ получения начального решения. Вы пишете "означает невозможность получения начального базиса". Да означает, если для его получения используется двух-фазный метод ($x=0, y=b$ в моём первом сообщении), так как нарушение условия $b \geq 0$ уже означает, что решение $x=0, y=b$ не является начальным, так как не удовлетворяет условию $y \geq 0$ вспомогательной задачи.
В общем же случае, делайте $b$ любыми, но тогда придётся описывать способ которым будете получать начальное решение.

[eugrita]

"двухфазный с неотрицательным b" - это неточно,
хотите видно сказать "двухфазный с любым b - универсален в поиске начальн решения" ?

Т.е. B>=0 важно и фишка с изменением >= на <= в рамках классического не проходит, так как после этого Bi становится отрицательным.
Кроме того, случай отсутствия ограничений Xi >=0 вообще - тоже
Интересно, что задача поиска min вместо max проходит и при классическом
если хотя бы один из Ci < 0
А в таком случае может вообще забыть про классический метод.
И решать все задачи двухфазным или M -методом?
------------------------------------------------------------------------------
А как все-таки с ответом на мой пример?
Он решался классическим способом но условия применимости классического
не были выполнены, тем не менее он решен. Можете сами проверить на бумаге

[Alexey1]

eugrita в сообщении #312712 писал(а):

А в таком случае может вообще забыть про классический метод.
И решать все задачи двухфазным или M -методом?

Почему Вы разделяете классический (симплекс-метод) и двух-фазный методы? Двух-фазный метод это применение классического, сначала к вспомогательной задаче, а потом к первоначальной задаче после того, как найдено допустимое решение.
Что касается $M$-метода, то это просто альтернатива двух-фазному.

[eugrita]

В конечном счете все разновидности методов применяют симплекс-алгоритм, т.е. преобразование Жордана над матрицей. Различия лишь в том, что подается на вход 1 итерации, и в том сколько раз применяется симплекс-алгоритм.
когда я говорю классический я понимаю формирование неотрицательных базисн переменных, т.е приписывание справа к исходной матрице единичной.
Так вот ,как вы объясняете что мой пример при изменении знака последнего неравенства на >= и тем самым B3=-2 <0 все таки решен обычным симплес-алгоритмом???

[Alexey1]

eugrita в сообщении #312712 писал(а):

"двухфазный с неотрицательным b" - это неточно,
хотите видно сказать "двухфазный с любым b - универсален в поиске начальн решения" ?

Сначала, задача линейного программирования приводится к виду
$\max c_1x_1+c_2x_2+...+c_nx_n$
$Ax=b$
$x \geq 0$.
где сделать $b$ неотрицательными не составляет сложности, поэтому без потери общности $b$ при использовании двух-фазового метода можно считать неотрицательными.

eugrita в сообщении #312720 писал(а):

Так вот ,как вы объясняете что мой пример при изменении знака последнего неравенства на >= и тем самым B3=-2 <0 все таки решен обычным симплес-алгоритмом???

Может совпадение? Вы сами все вычисления вручную делали или программа решала? Если задача решалась симплекс-методом, то это не правильно, так как симплекс-метод должен начинаться с допустимого решения.

[eugrita]

Смотрите сами - вот решение этой задачи без компа только в симплекс таблицах
Начальное решение как видите:
X1=X2=X3=0, S1=S2=6, S3=-2 (т.е есть отрицательный элемент!!!)
Тем не менее метод доработал и дал правильный результат (проверить легко геометрически)
Какой это метод? Полагаю классический, хотя и начальный вектор отрицателен
Ведь я же не вводил в последнем уравнении 2 переменные s3 и w3 вместо только s3

[Alexey1]

Во-первых, ссылка не работает. Во-вторых, в симплекс-таблицах решается симплекс-методом. Теперь о Вашей задаче. Вы знаете, как работает симплекс-алгоритм? Он переходит из одной вершины многогранника в другую. То есть алгоритм начинает работу в какой-либо вершине многранника (допустимое начальное базисное решение). Может Вы имеете ввиду двойственный симплекс-метод, там начальная точка может иметь отрицательные координаты.

[eugrita]

Вот вам еще ссылка. А что тег img или url не работает, так это не моя проблема, а админа данного форума. Я делаю все правильно. Такой сайт видимо
Те же проблемы и на www.exponenta.ru
[img]foto.mail.ru/mail/eugrita/_myphoto/4.html[/img]
[url]foto.mail.ru/mail/eugrita/_myphoto/4.html[/url]

[Alexey1]

Ну просто совпало так. У Вас и на втором шаге, полученное решение $s_1=3, x_1=3, s_3=1$ тоже не является допустимым (не удовлетворяет системе ограничений).

[eugrita]

исходный вопрос так и остался нераскрытым:
Можно ли глядя на входную систему ограничений и целевую функцию
придумать несложное правило по которому можно однозначно принять
решение будет ли обычный (однофазный) алгоритм находить или не находить верное оптимальное решение и заложить это правило в программу.

[Alexey1]

eugrita в сообщении #312999 писал(а):

исходный вопрос так и остался нераскрытым:
Можно ли глядя на входную систему ограничений и целевую функцию
придумать несложное правило по которому можно однозначно принять
решение будет ли обычный (однофазный) алгоритм находить или не находить верное оптимальное решение и заложить это правило в программу.

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

[eugrita]

Спасибо конечно. Куда вы ткнули меня в википедию, я конечно смотрел,
но там описание неполное.
Уже повторял, повторю еще раз.
С формальной точки зрения мой приведенный пример не попадает в область применимости классического симплекс метода, описанную в разных источниках.
А фактически - симплекс метод работает на нем. Тем самым понятие "область применимости" сформулированы не чётко а расплывчато - вне области может сработает может не сработает.
Математика - строгая наука