Cимплекс-метод: Для нахождения первого плана задачи использовать метод искусственного базиса...

Уважаемые математики! Мне такая задача не под силу... но очень надо решить, помогите!

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

$L(X) = -10x_1 + 3x_2 \to \min$

$L(X)=-10x_1+3x_2 \to \min$

$3x_1+x_2 \le 1 3x_1+x_2 \le 5 -8x_1+3x_2 \le 4$

$x_1, x_2 \ge 0$

как там составлять эти симплекс=таблицы вообще не поняла... в общем, заранее спасибо!
Буду очень благодарна за помощь!!!



Редактировалось 3 раз(а). Последний 09.09.2010 23:58.

Ох, не получается у меня писать в вашем страном техе!....
что делать-то?

Девочка, по крайней мере, старалась записать все в ТеХе.
В мире и в и-нете много пособий по линейному программированию, и в любой районной, а то и в сельской, библиотеке можно что-нибудь найти. Я вот недавно обрел книжку Шикиных "Исследование операций" - славная книжечка и примитивная до радости.
Теперь изобразим Вашу задачку грамотно:
$\left\{\begin{array}{c}3x_1+x_2\le13\\x_1+x_2\le5\\-8x_1+3x_2\le4\\L(\vecx)=-10x_1+3x_2 \to \min\end{array}$
Считается (по умолчанию), что все значения неотрицательны, хотя можно и выписать в сторонке дополнительно это условие.
Это начальная формулировка. Теперь мы будем приводить ее к стандартному виду. Т.е. заменим ограничения неравенства ограничениями равенствами. Для чего для каждого неравенства вводим новую переменную (номер новой переменной равен $2+i$, где $i$ - номер уравнения для которого добавили переменную. И записываем задачу в новом виде:
$\left\{\begin{array}{c}3x_1+x_2+x_3=13\\x_1+x_2+x_4=5\\-8x_1+3x_2=4\\L(\vecx)=-10x_1+3x_2 \to \min \end{array}$
К этой задаче Вы и примените симплекс-метод, который описывается во всех пособиях и пр. В интернете, кажется, на www.exponenta.ru имеются коротенькие и очень ясные описания с примерами.
Можно обратиться к "Единому окну доступа к образовательным ресурсам" (в поисковике ищите по ключу ЕДИНОЕ ОКНО) есть куча пособий и их можно скачать. и т.д.

Для получения двойственной задачи придется сменить "оптимизируемую функцию", чтобы искать не минимум , а максимум (для ограничений "меньше или равно" берут форму, для которой ищем максимум), т.е. это будет $L*(\vecx)=10x_1-3x_2\to\;max$
Двойственная задача получается так: каждому ограничению (в начальной формулировке, но с максимизируемой формой) с номером $i$ ставится в соответствие основная переменная $y_i$, а каждой основной переменной $x_j$ начальной формулировки ставится ограничение с номером $j$. Это ограничение строится из коэффициентов при $x_j$ во всех ограничениях начальной задачи, которые умножаются на $у$ с номером ограничения, и полученная сумма БОЛЬШЕ или равна коэффициенту при $x_j$ в выражении для $L(x)$. Двойственная задача состоит в нахождении минимума формы $M(\vecy)$ коэффициенты которой при игреках равны правым частям старых ограничений, соответствующих этим игрекам. Ваша задача такова:
$\left\{\begin{array}{c}3y_1+y_2-8y_3\ge10\\y_1+y_2+3y_3\ge-3\\M(\vecy)=13y_1+5y_2+4y_3 \to \min \end{array}$.
Чтобы привести эту задачу к каноническому виду, также добавляем новые переменные $y_4,\;y_5$ - по числу ограничений. Получаем задачу:
$\left{\begin{array}{c}3y_1+y_2-8y_3-y_4=-10\\y_1+y_2+3y_3-y_5=3\\M(\vecy)=13y_1+5y_2+4y_3\to \min \end{array}$.
Соответствие переменных такое:основным переменным первой задачи соответствуют добавленные переменные двойственной задачи в том же порядке (в порядке возратания):
$х_1\;\leftrightarrow\,y_4$,
$х_2\;\leftrightarrow\,y_5$.
Аналогичное соответсвие для основных переменных двойственной задачи и дополнительных первой задачи:
$х_3\;\leftrightarrow\,y_1$
$х_4\;\leftrightarrow\,y_2$
$х_5\;\leftrightarrow\,y_3$
Если Вы решили первую задачу (я ее решил , разумеется, не сиплекс-методом, а графически, т.к. переменных только две), то узнали, что искомый минимум равен $-\frac{130}{3}$, а макcимум формы $L*(\vecx)$ равен $+\frac{130}{3}$ и достигаются при $x_2=0,\;x_1=\frac{13}{3}$. Из этого следует, что в двойственной задаче искомый минимум равен тому же значению: $\frac{130}{3}$. Чтобы найти значения переменных. нужно решить систему из трех уравнений. Т.к. значения добавленных переменных равны нулю, то ограничения дают два уравнения с тремя искомыми переменными, а выражение для $M(\vecy)$ дает третье:
$\left\{\begin{array}{c}3y_1+y_2-8y_3=-10\\y_1+y_2+3y_3=3\\13y_1+5y_2+4y_3=\frac{130}{3}\end{array}$ .
Вот и все.



Редактировалось 7 раз(а). Последний 10.09.2010 02:38.

Приношу глубочайшую благодарность уважаемому Даниилу Кальченко за терпеливый труд по устранению моих ошибок. Прошу нижайше прощения за свою дремучесть.

Прежде всего прошу прощения за дикий ляп. Я написал, что $у_5=0$, что НЕ ВЕРНО. Т.к. $у_5$ соответствует $х_2=0$, а нулевым решениям первой задачи соответствуют не обязательно нулеве двойственной задачи. Поэтому у Вас $у_5$ - еще одна неизвестная (которая заведомо не меньше 3!!!). Но систеиа совместна, хотя и имеет не единственное решение.
Что касается

Цитата

только вот ну ничего, кроме русских слов не разобрала... Видимо на мех-мате в ТГУ этим техам очень зря не учат....

, то тут уж следует воспользоваться рекомендацией профессионала-преподавателя г. Brukvaluba, он знает, что говорит. И я уверен, что у Вас все плучится. Во всяком случае симплекс-метод Вы осилите, а я дьявольски ленив.

Цитата
Даниил Кальченко

Цитата
zzzetka
Я конечно искренне благодарна за помощь... только вот ну ничего, кроме русских слов не разобрала...

Я вам уже давал ссылку на пост с информацией по использованию теха в форуме. Текст содержит предельно понятные инструкции для IE, FF и Opera - по корректному отображению тех-формул. Если они вызывают у вас затруднения, то уж извините...

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