Необходимо решить задачу симплекс методом

[banzaec]

Я первый раз решаю задачу симплекс методом, поправте меня, если что...

Условие:
$Z=2x_1 +x_2 + x_3 \to max$
$x_1+x_2+x_3=3$
$x_1-x_2+x_3\ge 1$
$x_2+x_3\le 1$
$x_1, x_2, x_3 \ge 0 $


Решение:
Решаю задачу от min и привожу уравнения к каноническому виду
$Z=-2x_1 -x_2 - x_3 + Mx_6+Mx_7\to min$
$x_1+x_2+x_3+x_6=3$
$x_1-x_2+x_3-x_4+x_7=1$
$x_2+x_3+x_5=1$
$x_1, x_2, x_3, x_4, x_5, x_6 \ge 0 $
За базис принимаю $x_5, x_6, x_7$

Правильно выбрал базис и каноническому виду пришел ?

[Viktor_2]

онлайн-считалка при задании в нее текста

Maximize p = 2x + y + z subject to
x + y + z = 3
x - y + z >= 1
y + z <= 1
x >= 0
y >= 0
z >= 0

говорит, что

Optimal Solution: p = 6; x = 3, y = 0, z = 0

и выдает следующее:


Tableau #1
x y z s1 s2 s3 s4 s5 s6 s7 p
1 1 1 1 0 0 0 0 0 0 0 3
1 -1 1 0 -1 0 0 0 0 0 0 1
0 1 1 0 0 1 0 0 0 0 0 1
1 0 0 0 0 0 -1 0 0 0 0 0
0 1 0 0 0 0 0 -1 0 0 0 0
0 0 1 0 0 0 0 0 -1 0 0 0
1 1 1 0 0 0 0 0 0 -1 0 3
-2 -1 -1 0 0 0 0 0 0 0 1 0

Tableau #2
x y z s1 s2 s3 s4 s5 s6 s7 p
0 1 1 1 0 0 1 0 0 0 0 3
0 -1 1 0 -1 0 1 0 0 0 0 1
0 1 1 0 0 1 0 0 0 0 0 1
1 0 0 0 0 0 -1 0 0 0 0 0
0 1 0 0 0 0 0 -1 0 0 0 0
0 0 1 0 0 0 0 0 -1 0 0 0
0 1 1 0 0 0 1 0 0 -1 0 3
0 -1 -1 0 0 0 -2 0 0 0 1 0

Tableau #3
x y z s1 s2 s3 s4 s5 s6 s7 p
0 1 0 1 0 0 1 0 1 0 0 3
0 -1 0 0 -1 0 1 0 1 0 0 1
0 1 0 0 0 1 0 0 1 0 0 1
1 0 0 0 0 0 -1 0 0 0 0 0
0 1 0 0 0 0 0 -1 0 0 0 0
0 0 1 0 0 0 0 0 -1 0 0 0
0 1 0 0 0 0 1 0 1 -1 0 3
0 -1 0 0 0 0 -2 0 -1 0 1 0

Tableau #4
x y z s1 s2 s3 s4 s5 s6 s7 p
0 2 0 1 1 0 0 0 0 0 0 2
0 -1 0 0 -1 0 1 0 1 0 0 1
0 1 0 0 0 1 0 0 1 0 0 1
1 -1 0 0 -1 0 0 0 1 0 0 1
0 1 0 0 0 0 0 -1 0 0 0 0
0 0 1 0 0 0 0 0 -1 0 0 0
0 2 0 0 1 0 0 0 0 -1 0 2
0 -3 0 0 -2 0 0 0 1 0 1 2

Tableau #5
x y z s1 s2 s3 s4 s5 s6 s7 p
0 2 0 1 1 0 0 0 0 0 0 2
0 -1 0 0 -1 0 1 0 1 0 0 1
0 1 0 0 0 1 0 0 1 0 0 1
1 -1 0 0 -1 0 0 0 1 0 0 1
0 -1 0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 -1 0 0 0
0 2 0 0 1 0 0 0 0 -1 0 2
0 -3 0 0 -2 0 0 0 1 0 1 2

Tableau #6
x y z s1 s2 s3 s4 s5 s6 s7 p
0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 0 -0.5 0 1 0 1 -0.5 0 2
0 0 0 0 -0.5 1 0 0 1 0.5 0 0
1 0 0 0 -0.5 0 0 0 1 -0.5 0 2
0 0 0 0 0.5 0 0 1 0 -0.5 0 1
0 0 1 0 0 0 0 0 -1 0 0 0
0 1 0 0 0.5 0 0 0 0 -0.5 0 1
0 0 0 0 -0.5 0 0 0 1 -1.5 1 5

Tableau #7
x y z s1 s2 s3 s4 s5 s6 s7 p
0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 0.5 -0.5 0 1 0 1 0 0 2
0 0 0 -0.5 -0.5 1 0 0 1 0 0 0
1 0 0 0.5 -0.5 0 0 0 1 0 0 2
0 0 0 0.5 0.5 0 0 1 0 0 0 1
0 0 1 0 0 0 0 0 -1 0 0 0
0 1 0 0.5 0.5 0 0 0 0 0 0 1
0 0 0 1.5 -0.5 0 0 0 1 0 1 5

Tableau #8
x y z s1 s2 s3 s4 s5 s6 s7 p
0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 1 1 1 0 0 3
0 0 0 0 0 1 0 1 1 0 0 1
1 0 0 1 0 0 0 1 1 0 0 3
0 0 0 1 1 0 0 2 0 0 0 2
0 0 1 0 0 0 0 0 -1 0 0 0
0 1 0 0 0 0 0 -1 0 0 0 0
0 0 0 2 0 0 0 1 1 0 1 6

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

[banzaec]

Это всё очень интересно, спасибо Вам Viktor_2. Только мне надо самому научиться решать такие задачи, подскажите правильно я выбрал базис и каноническому виду пришел ?

[Viktor_2]

banzaec в сообщении #396800 писал(а):

Это всё очень интересно, спасибо Вам Viktor_2. Только мне надо самому научиться решать такие задачи, подскажите правильно я выбрал базис и каноническому виду пришел ?

Не знаю , забыл этот метод, а может никогда и не знал.. Такая тяга к знаниям! Вот Вам литература: http://zalil.ru/30289456
там в районе 20-й страницы и далее смотрите.

[banzaec]

banzaec в сообщении #396724 писал(а):

Я первый раз решаю задачу симплекс методом, поправте меня, если что...

Условие:
$Z=2x_1 +x_2 + x_3 \to max$
$x_1+x_2+x_3=3$
$x_1-x_2+x_3\ge 1$
$x_2+x_3\le 1$
$x_1, x_2, x_3 \ge 0 $


Решение:
Решаю задачу от min и привожу уравнения к каноническому виду
$Z=-2x_1 -x_2 - x_3 + Mx_6+Mx_7\to min$
$x_1+x_2+x_3+x_6=3$
$x_1-x_2+x_3-x_4+x_7=1$
$x_2+x_3+x_5=1$
$x_1, x_2, x_3, x_4, x_5, x_6 \ge 0 $
За базис принимаю $x_5, x_6, x_7$

Правильно выбрал базис и каноническому виду пришел ?

Ребята, подскажите правильно я выбрал базис?

[Alfucio]

Мне кажется, что да.

Сначала Вы привели задачу к канонической форме, добавив $-X_4$ и $X_5$, затем перешли к расширенной задаче, добавив $X_6$ и $X_7$.

Правда, я не совсем понимаю, зачем переходить к минимуму, задача может решаться и в рамках поиска максимума, но и в Вашем решении (через минимум) она должна успешно решиться, если все выкладки будут проделаны правильно. (Я просто решал через максимум с помощью программы, написанной мною давно :).)

[banzaec]

Не могу понять, один момент, подскажите...
Условие примера в учебнике
$Z=-5x_1 +x_2 + x_3 \to min$
$x_1+x_2\ge 4$
$5x_1+x_2+x_3=14$
Перевод к каноническому виду
$Z=-5x_1 +x_2 + x_3 \to min$
$x_1+x_2-x_4=4$
$5x_1+x_2+x_3=14$
Построение расширенной задачи

$Z=-5x_1 +x_2 + x_3+Mx_5 \to min$
$x_1+x_2-x_4+x_5=4$
$5x_1+x_2+x_3=14$
Дальше идет таблица

В таблице есть строка М, и в учебнике написано, там пишуться коэффициенты с уравнения, где есть искусственная переменная, т.е. отсюда$x_1+x_2-x_4+x_5=4$

Вопрос. У меня два таких уравнения с искусственными переменными, как быть, что писать в моей строке М
$Z=-2x_1 -x_2 - x_3 + Mx_6+Mx_7\to min$
первое $x_1+x_2+x_3+x_6=3$
второе $x_1-x_2+x_3-x_4+x_7=1$
$x_2+x_3+x_5=1$
$x_1, x_2, x_3, x_4, x_5, x_6 \ge 0 $

[Alfucio]

1) Как мне кажется, в Вашей верхней картинке на последнем (третьем) этапе «горизонтальный» коэффициент $C_B$ у «вертикального» $A_1$ должен быть равен $-5$, а у $A_2$ — $1$.
2) Для каждого $\[{\Delta _{\rm{j}}} = {Z_j} - {C_j}\]$ оценки вычисляются следующим образом: $\[{Z_j} - {C_j} = \sum\limits_{i = 1}^m {{c_i}{a_{ij}} - {c_j}} \]$. Для $Z_0$ — это $\[\sum\limits_{i = 1}^m {{c_i}{a_{ij}}} \]$. Так как у нас базис частично состоит из искусственных векторов, $\[{\Delta _{\rm{j}}}\]$ будет являться многочленом $\[{\Delta _{\rm{j}}} = a + {\rm{M}} \times {\rm{b}}\]$. В процессе решения расширенной задачи будем составлять симплекс-таблицу, в которой после обычной (m+1)-й строки оценок, где записываются слагаемые, не содержащие M (то есть a), помещают (m+2)-ю строку, где записывают коэффициенты при M (то есть b).
3) Ваше уже решенное задание из учебника я пересчитал с помощью программы. Программу можно посмотреть здесь. Алгоритм симплекс-метода еще с одной решенной задачей можно посмотреть здесь (стр. 11—15). Обратите внимание, что там алгоритм нацелен на нахождение максимума, но это не сильно меняет дело.
4) В Вашем случае во второй таблице в последнем сообщении коэффициенты в предпоследней строке должны иметь все противоположный знак (см. формулу).
5) Коэффициент $M/A_1$, например, будет в Вашем случае (при поиске минимума) равен 2.

(Я не часто пишу здесь, надеюсь, что размещать ссылки на другие ресурсы с теоретическими материалами и вспомогательными программами (не пиратскими) разрешается. Если я ошибаюсь, прошу модераторов подсказать это.)

[banzaec]

По первому вопросу, да это я ошибся, когда с книжки переписывал на последнем (третьем) этапе «горизонтальный» коэффициент $C_B$ у «вертикального» $A_1$ должен быть равен $-5$, а у $A_2$ — $1$. Все так как Вы написали
Спасибо Вам за совет :)