2014 dxdy logo

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

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




 
 Преобразовать задачу ЛП к стандартному виду
Сообщение06.03.2010, 11:36 
Здравствуйте. Как преобразовать задачу линейного программирования к стандартному виду?
Задача:
$Z=\sum \limits _{i=1}^{5} {c_ix_i}\to max$
$\sum \limits _{j=1}^{5} {a_i_jx_j}\leqslant b_i$, $i=1,2$
$\sum \limits _{j=1}^{5} {a_i_jx_j}\geqslant b_i$, $i=3,...,8$
$\sum \limits _{j=1}^{5} {a_i_jx_j}= b_i$, $i=9,10$
$x_j\geqslant 0$, $j=1,2$
Стандартный вид:
$Z=-c_1x_1-c_2x_2-c_3(x_3'-x_3'')-c_4(x_4'-x_4'')-c_5(x_5'-x_5'')\to min$
$a_1_1x_1+a_1_2x_2+a_1_3(x_3'-x_3'')+a_1_4(x_4'-x_4'')+a_1_5(x_5'-x_5'')\leqslant b_1$
$a_2_1x_1+a_2_2x_2+a_2_3(x_3'-x_3'')+a_2_4(x_4'-x_4'')+a_2_5(x_5'-x_5'')\leqslant b_2$
$-a_3_1x_1-a_3_2x_2-a_3_3(x_3'-x_3'')-a_3_4(x_4'-x_4'')-a_3_5(x_5'-x_5'')\leqslant -b_3$
$-a_4_1x_1-a_4_2x_2-a_4_3(x_3'-x_3'')-a_4_4(x_4'-x_4'')-a_4_5(x_5'-x_5'')\leqslant -b_4$
$-a_5_1x_1-a_5_2x_2-a_5_3(x_3'-x_3'')-a_5_4(x_4'-x_4'')-a_5_5(x_5'-x_5'')\leqslant -b_5$
$-a_6_1x_1-a_6_2x_2-a_6_3(x_3'-x_3'')-a_6_4(x_4'-x_4'')-a_6_5(x_5'-x_5'')\leqslant -b_6$
$-a_7_1x_1-a_7_2x_2-a_7_3(x_3'-x_3'')-a_7_4(x_4'-x_4'')-a_7_5(x_5'-x_5'')\leqslant -b_9$
$-a_8_1x_1-a_8_2x_2-a_8_3(x_3'-x_3'')-a_8_4(x_4'-x_4'')-a_8_5(x_5'-x_5'')\leqslant -b_8$
$x_1,x_2,x_3',x_3'',x_4',x_4'',x_5',x_5'',\geqslant 0$
А что делать с ограничением $\sum \limits _{j=1}^{5} {a_i_jx_j}= b_i$, $i=9,10$? Прибавить что-нибудь к правой части?

 
 
 
 Re: Преобразовать задачу ЛП к стандартному виду
Сообщение06.03.2010, 12:33 
Самое простое : всякое равенство эквивалентно дум нестрогим неравенствам с противоположными знаками.

 
 
 
 Re: Преобразовать задачу ЛП к стандартному виду
Сообщение06.03.2010, 13:36 
Стандартный вид у Вас неправильный. Если задача на максимум, то стандартное ограничение должно быть сверху, то есть $\leqslant$. Если хотите на минимум, то надо ограничивать снизу: $\geqslant$. Вам надо понять, какой из двух стандартных видов Вы хотите: на минимум или на максимум. А по поводу знака $=$ Вам правильно сказали, это надо заменить на пару $\leqslant$ и $\geqslant$. Что-то прибавлять к левой и правой части нельзя, так как это может нарушить равенство, задача будет не эквивалентной.

 
 
 
 Re: Преобразовать задачу ЛП к стандартному виду
Сообщение06.03.2010, 13:38 
Т. е. из $\sum \limits _{j=1}^{5} {a_i_jx_j}= b_i$, $i=9,10$ получится
$a_9_1x_1+a_9_2x_2+a_9_3(x_3'-x_3'')+a_9_4(x_4'-x_4'')+a_9_5(x_5'-x_5'')\leqslant b_9$
$a_9_1x_1+a_9_2x_2+a_9_3(x_3'-x_3'')+a_9_4(x_4'-x_4'')+a_9_5(x_5'-x_5'')\geqslant b_9$
$a_1_0_,_1x_1+a_1_0_,_2x_2+a_1_0_,_3(x_3'-x_3'')+a_1_0_,_4(x_4'-x_4'')+a_1_0_,_5(x_5'-x_5'')\leqslant b_1_0$
$a_1_0_,_1x_1+a_1_0_,_2x_2+a_1_0_,_3(x_3'-x_3'')+a_1_0_,_4(x_4'-x_4'')+a_1_0_,_5(x_5'-x_5'')\geqslant b_1_0$,
а из этого
$a_9_1x_1+a_9_2x_2+a_9_3(x_3'-x_3'')+a_9_4(x_4'-x_4'')+a_9_5(x_5'-x_5'')\leqslant b_9$
$-a_9_1x_1-a_9_2x_2-a_9_3(x_3'-x_3'')-a_9_4(x_4'-x_4'')-a_9_5(x_5'-x_5'')\leqslant -b_9$
$a_1_0_,_1x_1+a_1_0_,_2x_2+a_1_0_,_3(x_3'-x_3'')+a_1_0_,_4(x_4'-x_4'')+a_1_0_,_5(x_5'-x_5'')\leqslant b_1_0$
$-a_1_0_,_1x_1-a_1_0_,_2x_2-a_1_0_,_3(x_3'-x_3'')-a_1_0_,_4(x_4'-x_4'')-a_1_0_,_5(x_5'-x_5'')\leqslant -b_1_0$?

-- Сб мар 06, 2010 14:44:16 --

Так?
$Z=c_1x_1+c_2x_2+c_3(x_3'-x_3'')+c_4(x_4'-x_4'')+c_5(x_5'-x_5'')\to max$
$a_1_1x_1+a_1_2x_2+a_1_3(x_3'-x_3'')+a_1_4(x_4'-x_4'')+a_1_5(x_5'-x_5'')\leqslant b_1$
$a_2_1x_1+a_2_2x_2+a_2_3(x_3'-x_3'')+a_2_4(x_4'-x_4'')+a_2_5(x_5'-x_5'')\leqslant b_2$
$-a_3_1x_1-a_3_2x_2-a_3_3(x_3'-x_3'')-a_3_4(x_4'-x_4'')-a_3_5(x_5'-x_5'')\leqslant -b_3$
$-a_4_1x_1-a_4_2x_2-a_4_3(x_3'-x_3'')-a_4_4(x_4'-x_4'')-a_4_5(x_5'-x_5'')\leqslant -b_4$
$-a_5_1x_1-a_5_2x_2-a_5_3(x_3'-x_3'')-a_5_4(x_4'-x_4'')-a_5_5(x_5'-x_5'')\leqslant -b_5$
$-a_6_1x_1-a_6_2x_2-a_6_3(x_3'-x_3'')-a_6_4(x_4'-x_4'')-a_6_5(x_5'-x_5'')\leqslant -b_6$
$-a_7_1x_1-a_7_2x_2-a_7_3(x_3'-x_3'')-a_7_4(x_4'-x_4'')-a_7_5(x_5'-x_5'')\leqslant -b_9$
$-a_8_1x_1-a_8_2x_2-a_8_3(x_3'-x_3'')-a_8_4(x_4'-x_4'')-a_8_5(x_5'-x_5'')\leqslant -b_8$
$a_9_1x_1+a_9_2x_2+a_9_3(x_3'-x_3'')+a_9_4(x_4'-x_4'')+a_9_5(x_5'-x_5'')\leqslant b_9$
$-a_9_1x_1-a_9_2x_2-a_9_3(x_3'-x_3'')-a_9_4(x_4'-x_4'')-a_9_5(x_5'-x_5'')\leqslant -b_9$
$a_1_0_,_1x_1+a_1_0_,_2x_2+a_1_0_,_3(x_3'-x_3'')+a_1_0_,_4(x_4'-x_4'')+a_1_0_,_5(x_5'-x_5'')\leqslant b_1_0$
$-a_1_0_,_1x_1-a_1_0_,_2x_2-a_1_0_,_3(x_3'-x_3'')-a_1_0_,_4(x_4'-x_4'')-a_1_0_,_5(x_5'-x_5'')\leqslant -b_1_0$
$x_1,x_2,x_3',x_3'',x_4',x_4'',x_5',x_5'',\geqslant 0$
А правильно ли я ограничения $\geqslant$ перевел в ограничения $\leqslant$?

 
 
 
 Re: Преобразовать задачу ЛП к стандартному виду
Сообщение06.03.2010, 14:08 
Ну, если не всматриваться в каждый символ, то все правильно. Знаки преобразовали правильно. Смотря для чего Вы это делаете. Если для сдачи зачета, то далее оформление зависит о самого преподавателя. Вам надо понять, что именно он хочет увидеть в качестве ответа. Например, я бы захотел, чтобы в записях не было ни одной скобки, а переменные $x'$ и $x''$ обозначались бы через $x^{+}$ и $x^{-}$ (так становится понятной их интерпретация). Но все это СИЛЬНО отличается у других преподавателей.

 
 
 
 Re: Преобразовать задачу ЛП к стандартному виду
Сообщение06.03.2010, 16:27 
Нет, это не для зачета. В лабораторной работе задание преобразовать задачу линейного программирования к каноническому и стандартному видам.
Спасибо всем за помощь.

 
 
 
 Re: Преобразовать задачу ЛП к стандартному виду
Сообщение08.03.2010, 04:30 

(Оффтоп)

А лабораторную для собственного удовольствия выполняете:)

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


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