Re: [obm-l] Problema

["Artur Costa Steiner" <artur@xxxxxxxxxxxxx>]

De: obm-l@mat.puc-rio.br
Para: "obm-l@mat.puc-rio.br" <obm-l@mat.puc-rio.br>
Assunto: Re: [obm-l] Problema
Data: 24/10/03 11:51


Uvas dao mais lucro que maças (60 quilos de uvas dao lucro de 3 reais; 60
quilos de maças dao lucro de 1 real). Logo, transporte todas as uvas que
puder. Se sobrar espaço, complete com maças. Mas nao sobra. Dah para
transportar 75 caixas de uvas.
Morgado

Este eh o principio que orientou o famoso Metodo Simplex, para problemas de
programacao linear, desenvolvido por George Dantzig (creio que hoje jah
falecido), na decada de 60. Sao os conceitos de custo reduzido e preco
sombra (de shadow price, do Ingles). Eu tenho o livro original dele, Linear
Programming and Extensions, que adquiri em 1974. Conforme acontece com
alguma frequencia, o pai ou mae de uma tecnica ou algoritmo nem sempre eh a
pessoa mais indicada para escrever livros didaticos sobre os mesmos. O
grande Dantzig nao eh uma excecao a esta regra. O seu livro, um classico, eh
um tanto pesado. Sob o ponto de vista didatico, surgiram livros mais
acessiveis, baseados em Algebra Linear. Dentre estes, destaca-se o livro do
Hadley, realmente um primor de didatica e de clareza.

Atualmente existem outros algoritmos usados para problemas de PL,
destacando-se os do tipo Ponto Interior (os quais, alias, prestam-se tambem
a problemas nao lineares). O Metodo Simplex trabalha na fronteira do
conjunto viavel, explorando o fato, descoberto e demonstrado pela primeira
vez por Dantzig, que a solucao otima (ou pelo menos uma delas, caso haja
infinitas) de um problema de PL sempre eh um ponto extremo do conjunto
viavel (eh o que, na terminologia da PL, chama-se de solucao basica). Os
algoritmos do ponto interior parece serem mais adequados para problemas de
grande porte, por exemplo, 200 restricoes e 300 variaveis. O Metodo Simplex,
entretanto, continua vivo e saudavel. Eh utilizado, por exemplo, em alguns
modelos ligados aa operacao e expansao otima de sistemas eletricos do
Brasil. No Solver, da planilha Excel, o Simplex eh implementado quando o
usuario informa que o problema eh linear.

Artur






Em Fri, 24 Oct 2003 11:42:51 -0200, Tiago Carvalho de Matos Marques
<tiago@focusnetworks.com.br> disse:

Um caminhao pode levar ate 1500kg.
Temos disponiveis 80 caixas de uva e 80 de maca.
Caixa de uva vale 1real, de maca 0,25.
Caixa de uva pesa 20kg de maca pesa 15.
Quantas caixas de cada levar para receber o maximo possivel?
=========================================================================
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
=========================================================================

________________________________________________
OPEN
Internet
@ Primeiro provedor do DF com anti-vírus no servidor de e-mails @

=========================================================================
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
=========================================================================