Найти оптимальное решение симплексным методом

[Student2007]

$z=-8x_1 + 10x_2 + 4x_3 - 1 \to min$
при следующих ограничениях:
$6x_1-4x_2-3x_3 \leqslant 9$
$-x_1+x_2+x_3 \leqslant 0$
$x_2-x_3 \geqslant 3$
$x_{1,2,3} \geqslant 0$

я так думаю, что поскольку функция стремится к минимуму, то данную задачу следует решать построив сперва двойственную задачу.
Саму таблицу тут заполнять не буду, потому что с ней все мне ясно. У меня не получается построить двойственную задачу (такой вывод я делаю потому, что задача решаема, система ограничений совместна, но полученая мною двойственная задача для решения не годится).
Опишу как я делал двойственную задачу (где я ошибся?):
1. Привел неравенства задачи к знаку ≥, умножая первое и второе ограничения на (-1):
$z=8x_1 - 10x_2 + 4x_3 -1 \to min$
при следующих ограничениях:
$-6x_1+4x_2+3x_3 \geqslant 9$
$x_1-x_2-x_3 \geqslant 0$
$x_2-x_3 \geqslant 3$
$x_{1,2,3} \geqslant 0$
2. получил следующую двойственную задачу:
$w=9u_1 + 3u_3 - 1 \to max$
при следующих ограничениях:
$-6u_1+u_2 \leqslant 8$
$4u_1-u_2+u_3 \leqslant -10$
$3u_1-u_2-u_3 \leqslant 4$
$u_{1,2,3} \geqslant 0$
Решая ее симплексным методом не получаю нужное решение :(
Помогите пожалуйста.

[Vassil]

Наверное Вас так учили и поэтому Вы естественно исходите из какого-то конкретнего начального вида постановки задачи ЛП. Мы ее не знаем точно. Независимо от этого, следуя Ваших рассуждений, можно спросить Вас:

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

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

Если вам нужно еще изменить направления неравенств, Вы показываете, что можете это делать.

[Student2007]

Vassil, тоесть проще сделать так?:
$z=8x_1 - 10x_2 - 4x_3 + 1 \to max$
при следующих ограничениях (не затронул):
$6x_1-4x_2-3x_3 \leqslant 9$
$-x_1+x_2+x_3 \leqslant 0$
$x_2-x_3 \geqslant 3$
$x_{1,2,3} \geqslant 0$

При решении данной задачи получается, что минимум равен единице, что в принципе верно, но это при всех трех иксах равных нулю (однако, это должно выполняться при $x_1=3,5; x_2=3; x_3=0$ [в функции, стремящейся к минимуму])

Цитата:

Не кажется ли Вам, что знаки первых двух членов в целевой функции прямой задачи (уже преобразованная Вами) перевернуты без основания?

кажется :). Сейчас исправлю и проверю на решаемость.

ну а так я заочник, поэтому учусь самостоятельно. Знания черпаю или из книжек, или с интернета :)

[Student2007]

такая двойственная задача тоже не имеет решения (опять я где-то ошибся наверное; но не в жордановых исключениях точно, дважды пересчитал):
$w = 9u_1 + 3u_3 - 1 \to max$
при следующих ограничениях:
$-6u_1+u_2 \leqslant -8$
$4u_1-u_2+u_3 \leqslant 10$
$3u_1-u_2-u_3 \leqslant 4$
$u_{1,2,3} \geqslant 0$

я снова ошибся при получении двойственной задачи?

[Student2007]

в таком виде тоже не смог решить:

$z + 8x_1 - 10x_2 - 4x_3 = - 1
при следующих ограничениях:
$6x_1-4x_2-3x_3+x_4=9$
$-x_1+x_2+x_3=0$
$-x_2+x_3+x_6=-3$

Но исходная задача решаема 100%. Методом программного перебора я получил х1=3,5; х2=3; х3=0.

[Student2007]

Кажется что-то получил. Подскажите, такой порядок действий правильный?:
1. Функцию Z домножил на -1
2. Третье ограничение так же умножил на -1
3. Заполнил Симплекс-Таблицу.
В ходе ее решения получил:
$x_1=7/2$
$x_2=3$
$z=-1$

Поскольку в самом начале я функцию домножил на -1 нужно ли ее сейчас умножить на -1, для получения минимума функции?

[Alexey1]

Приведённая Вами двойственная задача почти правильная, только целевая функция должна быть $-9u_1+3u_3-1$ (кстати $-1$ можете спокойно выбросить из целевой функции как прямой, так и двойственной задачи).
А зачем Вы решаете двойственную задачу если её решение не проще прямой?
Объясните что Вы делаете с задачей перед тем, как составляете симплекс-таблицу? К какой форме вы её приводите?
$\min \sum_{i=1}^{n} c_ix_i$
$Ax=b$
$b \geq 0$.
Это форма к которой Вы хотите привести задачу?

[Student2007]

Alexey1
мне главное как проще решить, просто казалось, что функцию стремящуюся к минимуму нужно решать получив двойственную задачу :). Заблуждение :)

К какой форме хочу привести задачу я не знаю, немного не понимаю этот момент.
Вобщем сначала я целевую функцию и третье ограничение умножил на -1:

$z=8x_1 - 10x_2 - 4x_3 + 1 \to min$
при следующих ограничениях:
$6x_1-4x_2-3x_3 \leqslant 9$
$-x_1+x_2+x_3 \leqslant 0$
$-x_2+x_3 \leqslant - 3$
$x_{1,2,3} \geqslant 0$

потом ввел 3 базисные переменные, что бы привести неравенства к канонической форме:
$6x_1-4x_2-3x_3+y_1= 9$
$-x_1+x_2+x_3 +y_2 = 0$
$-x_2+x_3 +y_3 = - 3$

После перенес y'ки в левую часть равенства:
$y_1=-(6x_1-4x_2-3x_3)+ 9$
$y_2=-(-x_1+x_2+x_3) + 0$
$y_3=-(-x_2+x_3) - 3$

Раскрыл скобки (тут не пишу как) и заполнил таблицу (не нашел как тут таблицу рисовать, поэтому напишу так):
____$x_1$__$x_2$__$ x_3$__$1$
$y_1$ __6__-4__-3__ 9
$y_2$ __-1__1__ 1__ 0
$y_3$ __0__-1__ 1__-3
$z=$ -8__10__4__ 1

решая эту таблицу, получил, что $x_1=7/2$; $x_2=3$; $y_2=1/2$ (в ответ не пошел); все остальные переменные равны нулю. $z_min=-1$ (тут интересно, действительно ли минимальное значение функции? Не надо ли функцию еще раз умножить -1, что бы вернуть знаки как были в исходной задаче?

[Alexey1]

Student2007 в сообщении #313208 писал(а):

К какой форме хочу привести задачу я не знаю, немного не понимаю этот момент.

Ну как же Вы можете решить задачу, если Вы не знаете что с ней делать?
Задачу Вы будете решать симплекс-метдом. В Ваших лекциях (или в учебнике) перед объяснением симплекс-метода должна указываться задача, для которой этот метод может использоваться. Например,
$\min c^Tx$
$Ax=b$
$b \geq 0$.
Вот к этому виду и надо привести задачу. Также возможно, что симплекс-метод был объяснён для $\max$, тогда задачу необходимо привести к задаче на $\max$. В другом случае на $\min$.
После того, как привели к необходимому виду, используйте симплекс-метод.
Для какой задачи у Вас объяснён симплекс-метод?

[Student2007]

Alexey1
симплекс метод был объяснен для max. Про функцию, стремящуюся к минимуму - вообще ни слова.
такой функция была, на которой объясняли:
$z = 2x_1 - 4x_2 + 3x_3 + 2 \to max;$
все ограничения вида меньше или равно ($\leqslant$). Для решения ни чего кроме ее перевода в каноническую форму - не говорилось.

-- Вс апр 25, 2010 20:54:29 --

Alexey1 в сообщении #313292 писал(а):

Ну как же
$\min c^Tx$

не понятно, что есть c^T

[Alexey1]

Теперь становится понятнее. Если симплекс-метод был объяснён для задачи
$\max c^Tx$ ($c$ это вектор-столбец, поэтому скалярное произведение $c^Tx=\sum_{i=1}^{n} c_ix_i$)
$Ax \leq b$
$x \geq 0$.
Теперь приводите задачу которую Вы хотите решить к данной форме, то есть
$\max 8x_1-10x_2-4x_3+1$ (умножение на $-1$)
$6x_1-4x_2-3x_3 \leq 9$
$-x_1+x_2+x_3 \leq 0$
$-x_2+x_3 \leq -3$ (умножение на $-1$)
$x_1,x_2,x_3 \geq 0$
А как использовать симплекс-метод для этой задачи Вы знаете. Решение этой задачи будет решением первоначальной задачи.

[Student2007]

Alexey1
аа, понял :).. Ну в принципе задачу решил, спасибо за помощь :)