2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 симплекс метод разобраться и понять решение
Сообщение11.02.2014, 17:30 


29/11/10
107
Здравствуйте. Я пытаюсь разобрать пример из учебника Т. Ху "Целочисленное программирование и потоки в сетях" ,с 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