RE: [obm-l] Problema do Camelo - solucao (errata)

["Rogerio Ponce" <rogerio_ponce@xxxxxxxxxxx>]

Olá João Gilberto,

no exemplo que enviei , usei os fatores errados .
Refazendo as contas vem:

SUA POLÍTICA  ( N+2 partidas) , para carregar N*100 L :
Total de 2N+3 viagens , que, partindo de tanque cheio para o melhor 
rendimento , possibilita percorrer a distância máxima de 200/(2N+3) km .

MINHA POLÍTICA :
O ponto intermediário estará a 100/(2N+1) km do final , e com (N+1)*100 L .
O custo para o transporte do primeiro trecho será (2N+3) * [200/(2N+3) - 
100/(2N+1)]
Portanto , o gasto total será:
(N+1)*100 + 200 - 100*(2N+3)/(2N+1) , que vale
(N+2)*100 - 200/(2N+1)

Ou seja,
houve uma economia de 200/(2N+1) Litros .

[]'s
Rogério.



----------------------------------------------------------------------





Olá João Gilberto,

repare que em nenhum momento eu disse que minha solução é "a solução ótima" 
, mas apenas "uma solução ótima" . Deve ter ficado claro , pela liberdade de 
segmentação que podemos aplicar a qualquer trecho , que existe uma 
infinidade de soluções ótimas.

É claro também que o transporte de toda a água pelo primeiro trecho ( o de 3 
nanômetros ) também pode ser executado de várias formas diferentes , com o 
mesmo custo. Não somente porque pode ser segmentado , mas também porque as 
partidas do ponto inicial não necessitam de que a carga seja de 100 L, 
conforme você mesmo apontou.

Entretanto, qualquer das soluções para este trecho apresenta, no mínimo,  o 
mesmo custo que a minha, que tem apenas a vantagem de ser a mais simples.


Bem, com relação a não fazer o número mínimo de viagens para carregar 100* N 
litros , podemos considerar algumas coisas. Uma delas é que a água 
"desperdiçada" no final , se reflete em aumento astronômico de custo no 
início. E não existe forma mais barata de se tranportar a água do que aquela 
forma apresentada ( ou qualquer derivação dela , por meio de segmentação da 
mesma ), que é "número mínimo exigido de viagens para totalizar os N*100L , 
e então fazer todas as partidas relacionadas a este trecho com tanque cheio" 
. É a única maneira de "jogarmos mais para o início" o ponto de partida 
dessas 2N+1 viagens . Quaquer ponto mais distante , exigiria uma quantidade 
maior de viagens, e um maior "desperdício" associado . Senão, vejamos um 
exemplo :

Façamos o transporte de N*100 L , do ponto A para o ponto B , usando a sua 
política (N+2 partidas) :

Fazendo as N+2 partidas de A com tanque cheio (para minimizar o custo) , 
podemos percorrer o máximo de 200/(2N+5) km , de forma a totalizar os N*100 
L em B .
Ou seja, precisamos de (N+2)*100 L , para percorrermos uma distância total 
de 200/(2N+5) km .

------------------------------------

Façamos o transporte de N*100L , do ponto A para o ponto B , distantes dos 
mesmos 200/(2N+5) km , usando a minha política :

1- Há um ponto P , intermediário , a partir do qual eu farei apenas N+1 
partidas. Esse ponto estará , no máximo, a 100/(2N+1) km de B , e precisará 
de (N+1) * 100 L .

2- O transporte de A para P envolve a distância de  200/(2N+5) - 100/(2N+1) 
km , que será percorrida 2N+5 vezes , isto é , somente neste trecho é que 
usarei as N+2 partidas ( e com algum desperdício, pois não estarei de 
"tanque cheio" em todas elas).

Multiplicando-se os fatores, chegamos ao  custo de :
200 - 100*(2N+5)/(2N+1) Litros , que deverá ser somado aos (N+1)*100 L de 
água que deixaremos em P.
Portanto , para percorrermos A MESMA DISTÂNCIA , gastaremos um total de
(N+2) * 100 - 400/(2N+1) Litros .
-----------------------------------------

Economizamos 400/(2N+1) Litros, certo ?


[]'s
Rogério





>From: João Gilberto Ponciano Pereira <jopereira@vesper.com.br>
>
>Olá, pessoal
>
>Bem, Rogério, eu, como o prof. Nicolau, também tenho minhas dúvidas se 
>ficou
>provado que esta é a solução ótima. Acho que o principal motivo para isto é
>o simples fato que no primeiro trecho, o dos 3 nanômetros, a última viagem 
>é
>feita sem que o camelo esteja 100% carregado. Ou seja, existe uma "folga"
>onde podemos imaginar algumas soluções alternativas. (Se numa viagem, o
>camelo vai com menos que 100% de carga, é possível provar que todas as
>viagens daquele trecho podem ir com menos de 100% de carga).
>
>Outra coisa que não fico confortável é com o fato de usarmos apenas N+1
>viagens para 100 * N litros. Fiz algumas contas, e a degradação no
>rendimento entre fazer N+1 e N+2 viagens é pequena, se formos considerar o
>ganho em distância. Acho que, principalmente nos últimos trechos, podemos
>jogar com estes números, de forma a conseguirmos distâncias finais mais
>próximas aos exatos 10km.

>
>
>
>-----Original Message-----
>From: Rogerio Ponce [mailto:rogerio_ponce@hotmail.com]
>Sent: Wednesday, November 19, 2003 7:24 PM
>To: obm-l@mat.puc-rio.br
>Subject: Re: [obm-l] Problema do Camelo - solucao
>
>
>Não gostei , e alterei "associado a este trecho" por "associado a este
>último trecho" :
>------------------------
>Olá Nicolau,
>repare que partimos de uma condição de contorno , que era ter 1000L
>no final.
>
>O mínimo para isso , seriam 11 viagens de ida a partir da última
>base . Temos que adotar isso, pois só desperdiçaríamos água se
>aumentássemos o número de viagens para transportar a mesma
>quantidade de água entre a ultima base e o ponto final.
>
>Ao escolhermos que as 11 partidas seriam "com tanque cheio" (100L) ,
>estamos minimizando o caminho que falta percorrer do ponto inicial
>até essa última base , ao mesmo tempo em que também minimizamos o
>custo do transporte da água associado a este último trecho do caminho .
>
>O mesmo raciocínio se aplica sucessivamente a todos os trechos.
>[]´s
>Rogério.
>
>
>
> >From: "Nicolau C. Saldanha" <nicolau@sucuri.mat.puc-rio.br>
> >...
> >
> >Mas também não demonstrou que a resposta é mínima, pelo menos não de 
>forma
> >clara e explícita.
> >
> >[]s, N.
>
>_________________________________________________________________

_________________________________________________________________
MSN Messenger: converse com os seus amigos online.  
http://messenger.msn.com.br

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================