2014 dxdy logo

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

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




 
 симплекс метод разобраться и понять решение
Сообщение11.02.2014, 17:30 
Здравствуйте. Я пытаюсь разобрать пример из учебника Т. Ху "Целочисленное программирование и потоки в сетях" ,с 50, Пример 1,
Задача:
$z = 11 - x_{3} - x_{4} - x_{5} \mapsto \min $
При условиях
$\left\{\begin{matrix}
x_{1} & +x_{3} & -x_{4} & +2x_{5} & = 2\\ 
x_{2} & -x_{3} &  +2x_{4} & -x_{5} & = 1\\ 
x_{j} \geqslant 0, &  &  & (j = 1, ... , 5) &
\end{matrix}\right.$
Решение:
Перепишем задачу в следующем виде:
$-z - x_{3}- x_{4} -x_{5} = -11$
$x_{1} + x_{3}-x_{4}+2x_{5} = 2$
$x_{2} - x_{3} + 2x_{4} - x_{5} = 1$
Полученная запись является диагональной формой относительно $-z, x_{1}, x_{2}$. Запишем $x_{1}, x_{2}$ слева от таблицы:
$\begin{matrix}
  & 1   & x_{1} &  x_{2} &  x_{3} &  x_{4} & x_{5} \\
 -z    & -11 &  0    &  0     &  -1    &  -1    & -1 \\
 x_{1} &  2  &  1    &  0     &  1     &  -1    & 2 \\
 x_{2} &  1  &  0    &  -1    &  1     &   2    & -1
\end{matrix}$
Произвольно в качестве ведущего выберем столбец при x4. Ведущий элемент $a_{2,4}$ равный 2. Разделим уравнение 2 на $a_{2,4}$ и применив процедуру исключения Гаусса чтобы получить все $a_{i,4}$ равными 0 получим следующую таблицу:
$\begin{matrix}      & 1   & x_{1} &  x_{2} &  x_{3} &  x_{4} & x_{5} \\-z  & -2\frac{1}{2} & 0 & \frac{1}{2} & -\frac{3}{2} & 0 & -\frac{3}{2} \\x_{1} & \frac{5}{2} & 1 & \frac{1}{2} & \frac{1}{2}  & 0 & \frac{3}{2} \\x_{4} & \frac{1}{2} & 0 & \frac{1}{2} & -\frac{1}{2} & 1 & -\frac{1}{2}\end{matrix}$
ОТКУДА? взялся коэффициент $a_{0,0} = -2 \frac{1}{2}$ По моим подсчетам он равняется -10.5. Остальные коэффициенты сошлись с книгой.
Среди отрицательных элементов нулевой строки можно выбрать либо $x_{3}$, либо $x_{5}$. Произвольно выберем в качестве ведущего третий столбец и элемент $a_{1,3}$ в качестве ведущего. Результат соответствующего преобразования показан в таблице:
$\begin{matrix}
  & 1   & x_{1} &  x_{2} &  x_{3} &  x_{4} & x_{5} \\
 -z    & -3 & 3    &  2     &  0    &  0    & 3 \\
 x_{3} &  5  &  2    &  1     &  1     &  0    & 3 \\
 x_{4} &  3  &  1    &  1    &  0     &   1    & 1
\end{matrix}$
И опять коэффициент $a_{0,0}$ равен -3, вместо положенных 5. Как вычисляется коэффициент $a_{0,0}$?

 
 
 [ 1 сообщение ] 


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