2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему
 
 Метод Гомори
Сообщение23.07.2012, 19:11 
Аватара пользователя


17/12/10
538
Решить задачу целочисленного линейного программирования используя
1) метод Гомори
2) метод ветвей и границ

$\min f=-x_1-x_2 \\
x_1+2x_2+x_3=6 \\
3x_1+2x_2+x_4=9 \\
x\geqslant 0, x_j - \text{целые}, j=1,2,3,4.$

$\begin{tabular}{c|c|c|c|c|c||c}
\\
\text{базисные} & \text{свободные} & (x_1)&x_2&x_3&x_4 \\
\hline
x_3&6&1&2&1&0&6 \\
\hline
(x_4)&9&3&2&0&1&3 \\
\hline
f&0&1&1&0&0& \\
\end{tabular}$

$\begin{tabular}{c|c|c|c|c|c||c}
\\
\text{базисные} & \text{свободные} & x_1&(x_2)&x_3&x_4 \\
\hline
(x_3)&3&0&4/3&1&-1/3&2,25 \\
\hline
x_1&3&1&2/3&0&1/3&4,5 \\
\hline
f&-3&0&1/3&0&-1/3& \\
\end{tabular}$

$\begin{tabular}{c|c|c|c|c|c||c}
\\
\text{базисные} & \text{свободные} & x_1&x_2&x_3&x_4 \\
\hline
x_2&9/4&0&1&3/4&-1/4& \\
\hline
x_1&3/2&1&0&-1/2&1/2& \\
\hline
f&-15/4&0&0&-1/4&-1/4& \\
\end{tabular}$

у $ \frac32 $ наименьшая дробная часть

$-\frac12 x_3+ \frac12 x_4 = \frac32$

$\frac12 x_3+\frac12 x_4 \geqslant \frac12$

$x_3+x_4 \geqslant 1$

$x_3+x_4-u_1=1$

$\begin{tabular}{c|c|c|c|c|c||c}
\\
\text{базисные} & \text{свободные} & x_1&x_2&x_3&x_4&u \\
\hline
x_2&9/4&0&1&3/4&-1/4&0 \\
\hline
x_1&3/2&1&0&-1/2&1/2&0 \\
\hline
&1&0&0&1&1&-1 \\
\hline
f&-15/4&0&0&-1/4&-1/4& \\
\end{tabular}$

в таком случае, что дальше делать?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group