2014 dxdy logo

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

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




 
 Задача линейного программирования с дробной целевой функцией
Сообщение06.05.2010, 15:14 
Имеется следующая задача
$$ \frac{x_1-x_2-3 x_4}{3x_1+2x_2+x_3}\to min $$
при ограничениях
$$x_i \geqslant0$$
$$
\left\{  
\begin{array}{rcr} 
x_1+x_2+x_3&=&6 \\  
3x_1-2x_2+x_4&=&9 \\  
-x_1+2x_2+x_5&=&10 \\
\end{array}   
\right.  
$$
Подскажите, как ее решать. Мне кажется, что это симплекс-метод, но я не знаю, что делать в таком случае с целевой функцией.

 
 
 
 Re: Задача линейного программирования с дробной целевой функцией
Сообщение06.05.2010, 18:32 
Аватара пользователя
Задача сводится к линейной.
Положим, что знак знаменателя известен и для определённости примем положительным (для отрицательного изменения очевидны; если определить знак из имеющихся условий задачи или из дополнительных сведений не представляется возможным, решать придётся дважды для обоих случаев)
Обозначим
$$ t=\frac{1}{3x_1+2x_2+x_3} $$
и
$$ y_i=tx_i\ $$

и домножим все ограничения на t.

Кроме того, домножим на t знаменатель (очевидно, получив единицу)

Тогда задача сведётся к
$$ y_1-y_2-3 y_4\to min $$
при ограничениях
$$y_i \geqslant0$$
$$
\left\{  
\begin{array} {rcr}
   y_1+y_2+y_3-6t&=&0 \\  
3y_1-2y_2+y_4-9t&=&0 \\  
-y_1+2y_2+y_5-10t&=&0 \\
3y_1+2y_2+y_3&=&1\\
\end{array}   
\right.  
$$

 
 
 
 Re: Задача линейного программирования с дробной целевой функцией
Сообщение06.05.2010, 19:12 
Честно говоря не представляю, каким методом решать эту задачу. Похоже вроде на симплекс-метод, но "мешается" t

 
 
 
 Re: Задача линейного программирования с дробной целевой функцией
Сообщение06.05.2010, 19:42 
ttrun в сообщении #316292 писал(а):
Честно говоря не представляю, каким методом решать эту задачу. Похоже вроде на симплекс-метод, но "мешается" t
В каком смысле мешается? Такая же неизвестная как и все остальные.

 
 
 
 Re: Задача линейного программирования с дробной целевой функцией
Сообщение06.05.2010, 19:55 
т.е. мы ее грубо говоря считаем за y_6?

 
 
 
 Re: Задача линейного программирования с дробной целевой функцией
Сообщение06.05.2010, 19:56 
ttrun в сообщении #316324 писал(а):
т.е. мы ее грубо говоря считаем за y_6?
Да, можете назвать так.

 
 
 
 Re: Задача линейного программирования с дробной целевой функцией
Сообщение06.05.2010, 19:56 
Аватара пользователя
Задача, к которой сводится дробно-линейная, есть обычная задача ЛП. Обозначение t взамен y сделано исключительно для простоты объяснения. С точки зрения решения задачи t - такая же линейная переменная. Её, при желании, можно переобозначить, как y с соответствующим индексом.
После решения, получив значение t и y, переходят к значениям x.

 
 
 
 Re: Задача линейного программирования с дробной целевой функцией
Сообщение06.05.2010, 20:00 
большое спасибо!! просто сбила с толку буква t, сейчас проверил - все правильно) Еще раз спасибо

 
 
 
 Re: Задача линейного программирования с дробной целевой функцией
Сообщение15.04.2011, 18:58 
Здравствуйте, а то что $t>0$, а не $t\geqslant 0$ играет значение?

 
 
 
 Re: Задача линейного программирования с дробной целевой функцией
Сообщение25.10.2011, 15:34 
Аватара пользователя
А что произойдёт при t=0?

 
 
 [ Сообщений: 10 ] 


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