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