Re: Heurísticas!!??? (EP3)

["Ellen Hidemi" <ellenhidemi@terra.com.br>]

Oi,

N�o sei se entendi isso direito, mas antes de arredondar as vari�veis -
x(i), n�o seria melhor vermos o respectivo c(i) ?
Seja c o vetor de custos, c = (c(1) c(2) ... c(n))
Para 1 <= i <= n,
Se c(i) >= 0, x(i) = 0 ou 1
Se c(i) < 0, x(i) = 0
Ou seja, se o custo � positivo, tudo bem... truncamos o valor das vari�veis.
Mas se o custo � negativo, sempre valer� zero.

Um exemplo simples:
c = (1 2 3 -2)
Quero maximizar  c^Tx =  x1 + 2*x2 + 2*x3 -x4,
sujeito a *algo* x1 e x1, x2, x3, x4 = 0 ou 1
Suponhamos que em PL, x = (0.7 0.4 1 1), ent�o c^Tx = 2.5 => limitante
superior
Apenas truncando as vari�veis temos: x = (0 0 1 1), ent�o c^Tx = 1
Mas, se x4=0, temos: x = (0 0 1 0), ent�o c^Tx = 2 => que seria o limitante
inferior

� assim que devemos pensar??

Ellen Hidemi


----- Original Message -----
From: "Rubens Altimari" <rubens@bcc2000.net>
To: "Lista - Mac315" <egbirgin-mac315@ime.usp.br>
Sent: Monday, June 24, 2002 10:54 PM
Subject: Re: Heur�sticas!!??? (EP3)


>>Mas, o resultado da relaxa��o linear deve indicar um bom caminho. Por
>>exemplo, que tal usar o valor trucado das vari�veis. Isso n�o d� uma
>>solu��o vi�vel?

>Nem sempre, certo?  Como estamos lidando com vari�veis bin�rias, poder�amos
>tentar arrendond�-las... Mas pode ocorrer de as restri��es de igualdade
>deixarem de ser satisfeitas, n�o pode?

Para ser sincero, ainda n�o implementei este neg�cio, mas n�o sei se entendi
o problema (pra variar): porque truncar (isto �, "arredondar para baixo")
_as var�aveis bin�rias_ fugiria das restri��es de igualdade? Elas j� n�o
satisfazem 0 <= xi <= 1?

>S� para esclarecer... (J� se falou tanta coisa nessa lista que fiquei
>confusa... ;-)

Lamento pela minha contribui��o � confus�o... Mas acho que minhas perguntas
foram t�picas de quem ainda n�o tinha come�ado a fazer/pensar direito no
problema. Na verdade, qualquer das op��es tem mais ou menos o mesmo grau de
dificuldade, eu acho. Mesmo o enunciado original...

Rubens