2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Задача линейного программирования. Симплекс метод
Сообщение12.07.2012, 11:54 
Аватара пользователя
Для задачи линейного программирования найти исходное опорное решение, используя симплексные преобразования

$f(x)=cx \to \max$
$Ax=b$
$x \ge 0$

$c=(6, 1, -1, -2, 0)$
$b=(4, 1, 9)^T$
$\displaystyle A=\begin{pmatrix} 1 & 2 & 1 & 6 & 1\\ 3 & -1 & -1 & 1 &0 \\ 1& 3 &5 & 0 & 0 \end{pmatrix}$

функция:
$f(x)=6x_1+ x_2 -x_3 -2x_4$


$\left\{\begin{matrix} x_1+ 2x_2+ x_3+ 6x_4 + x_5=4\\ 3x_1 -x_2 -x_3 + x_4=1 \\ x_1 +3x_2+ 5x_3 =9 \end{matrix}\right.$

Какой ход действий?

 
 
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение12.07.2012, 13:24 
Аватара пользователя
Найти базисные переменные, подставить в целевую функцию, выразить целевую функцию через свободные переменные и заполнить Симплексную таблицу.

 
 
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение12.07.2012, 20:45 
Аватара пользователя
Базисные это: $x_1, x_2, x_3, x_4,x_5$ ?

 
 
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение12.07.2012, 21:39 
Аватара пользователя
Нет. У Вас в системе ограничений - три независимых уравнения и 5 переменных. Следовательно, базисных переменных должно быть 3. А свободных переменных должно быть 2. Возмите матрицу $A$. Видно, что в последнем столбце два нуля и одна единица. Значит $x_5$ можно взять за базисную. В предпоследнем столбце - есть уже один нуль. Методом Гаусса получите и второй нуль в первой строке. Ну, и возмите к примеру, третий столбец с конца и методом Гаусса получите два нуля в первой и второй строке. А потом сделайте так (поделите или умножте) чтобы в этих базисных стобцах - ненулевые элементы были бы равны 1 или -1.
Вот и будут у Вас $x_3, x_4, x_5$ - базисными переменными.

 
 
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 12:40 
Аватара пользователя
Shtorm в сообщении #594776 писал(а):
Следовательно, базисных переменных должно быть 3. А свободных переменных должно быть 2.

Как это определили?

Методом Гаусса — Жордана можно?
вот так получилось:

$\[\left|\hskip -\arraycolsep \begin{array}{*{5}{c}|c}
1&0&0&\frac{19}{24}&\frac{1}{12}&1\\
& & & & & \\
0&1&0&3\frac{5}{6}&\frac{2}{3}&1\\
& & & & & \\
0&0&1&-2\frac{11}{24}&-\frac{5}{12}&1
\end{array}\hskip -\arraycolsep \right|\]$

 
 
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 12:50 
Аватара пользователя
Честно говоря, лень проверять всю эту арифметику (ещё и при проверке могу сам ошибиться). Но если у Вас всё верно, то тогда базисными переменными будут $x_1, x_2, x_3$. Надеюсь Вы столбцы не переставляли?

 
 
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 12:53 
Аватара пользователя
Shtorm в сообщении #594886 писал(а):
Честно говоря, лень проверять всю эту арифметику (ещё и при проверке могу сам ошибиться). Но если у Вас всё верно, то тогда базисными переменными будут $x_1, x_2, x_3$. Надеюсь Вы столбцы не переставляли?


Там должно быть все верно, я графическим методом его решал еще, просто пытаюсь разобраться с симплекс методом

 
 
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 12:56 
Аватара пользователя
Ну тогда перепишите преобразованную систему ограничений. Выражайте базисные через свободные и подставляйте в целевую функцию, чтоб она была выражена только через свободные.

 
 
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 13:19 
Аватара пользователя
$x_1=- 0,79x_4 - 0,0833x_5+1 \\
x_2 =- 3,83x_4-0,67x_5+1 \\
x_3=2,46x_4+0,42x_5 +1$

$f(x)=-5 \frac{3}{8}x_4-1\frac{7}{12}x_5+6$

 
 
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 14:00 
Аватара пользователя
Теперь можно заполнять симплексную таблицу и не забывайте, что в последнюю строчку коэффициенты из целевой функции идут с противпоположным знаком.

 
 
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 14:21 
Аватара пользователя
\begin{tabular}{c|c|c|c|c|c|c}
\\
\text{базисные} & \text{свободные} & x_1&x_2&x_3&x_4&x_5 \\
\hline
x_1&-1&1&0&0&$\frac{19}{24}$&$\frac{1}{12}$& \\
\hline
\\
x_2&-1&0&1&0&$3\frac{5}{6}$&$\frac{2}{3}$ \\
\hline
\\
x_3&-1&0&0&1&-2$\frac{11}{24}$&$-\frac{5}{12}$

\end{tabular}

так правильно?
а целевую функцию куда?

 
 
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 14:31 
Аватара пользователя
Ну, во-первых, у Вас там в матрице свободные члены - единички, были со знаком плюс, а тут вы их записали со знаком минус. Надо знак плюс. И во-вторых, в симплексную таблицу необходимо добавить ещё одну строчку (последнюю), где будет отражена целевая функция и вот там уже знаки менять - только в коэффициентах, а не в свободных членах.

 
 
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 14:39 
Аватара пользователя
\begin{tabular}{c|c|c|c|c|c|c} 
\\
 \text{базисные} & \text{свободные} & x_1&x_2&x_3&x_4&x_5 \\ 
\hline 
x_1&1&1&0&0&$\frac{19}{24}$&$\frac{1}{12}$& \\ 
\hline 
\\
 x_2&1&0&1&0&$3\frac{5}{6}$&$\frac{2}{3}$ \\ 
\hline
 \\
 x_3&1&0&0&1&-2$\frac{11}{24}$&$-\frac{5}{12}$\\
\hline
 \\
f &-6&0&0&0&5 $\frac{3}{8}$&$1\frac{7}{12}$\\

 \end{tabular}
Вот так?

 
 
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 14:42 
Аватара пользователя
перед цифрой 6 должен быть "+". Знаки меняются только перед коэффициентами. Перед свободным членом не меняются. Ну и арифметику я не проверял.

 
 
 
 Re: Задача линейного программирования. Симплекс метод
Сообщение13.07.2012, 14:48 
Аватара пользователя
Так это надо было просто вот эту матрицу в таблицу записать?
Как теперь найти исходное опорное решение?

$\[\left|\hskip -\arraycolsep \begin{array}{*{5}{c}|c} 1&0&0&\frac{19}{24}&\frac{1}{12}&1\\ & & & & & \\ 0&1&0&3\frac{5}{6}&\frac{2}{3}&1\\ & & & & & \\ 0&0&1&-2\frac{11}{24}&-\frac{5}{12}&1 \end{array}\hskip -\arraycolsep \right|\]$

\begin{tabular}{c|c|c|c|c|c|c} 
\\
 \text{базисные} & \text{свободные} & x_1&x_2&x_3&x_4&x_5 \\ 
\hline 
x_1&1&1&0&0&$\frac{19}{24}$&$\frac{1}{12}$& \\ 
\hline 
\\
 x_2&1&0&1&0&$3\frac{5}{6}$&$\frac{2}{3}$ \\ 
\hline
 \\
 x_3&1&0&0&1&-2$\frac{11}{24}$&$-\frac{5}{12}$\\
\hline
 \\
f &6&0&0&0&5 $\frac{3}{8}$&$1\frac{7}{12}$\\

 \end{tabular}

 
 
 [ Сообщений: 25 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group