Pesquisa operacional/Introdução à Programação Linear: diferenças entre revisões

[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
Sem resumo de edição
Linha 34:
 
Em 1984, surge mais um método de se resolver problemas de pesquisa operacional: o Algoritmo do Ponto Interior, criado por Narendra Karmarkar. Assim como o Algoritmo Elipsóide, ele era polinomial. A diferença é que ele era bem mais rápido e conseguia competir com o Algoritmo Simplex.
 
 
==A Criação de Modelos==
 
O conceito de modelos é de importância fundamental ao estudarmos pesquisa operacional. Um modelo é uma representação simplificada da realidade. Para criarmos um modelo de programação linear, precisamos identificar em um problema qual é a '''função objetivo''', as '''restrições''' e o tipo de '''otimização''' que desejamos (queremos achar o máximo ou o mínimo da função-objetivo?). Veja o exemplo abaixo:
 
Uma empresa fabrica mesas e cadeiras. O quadro abaixo mostra os recursos consumidos por unidade de cada produto e os seus lucros.Quantas mesas e cadeiras podem ser fabricados para se maximizar o lucro?
 
{| border=2
|+ Unidades Necessárias
|-
| Recurso
| Mesa
| Cadeira
| Quantidade Disponível
|-
| Madeira
| 30
| 20
| 310
|-
| Metal
| 5
| 10
| 113
|-
| Lucro
| 6
| 8
| -
|}
 
A nossa função objetivo é o total de lucro da venda de mesas (M) e cadeiras (C). Queremos descobrir qual o valor máximo possível de lucro que podemos obter. Logo, nossa função objetivo é:
 
Máx <math>Z = 6M + 8C</math> (Função-Objetivo)
 
Agora precisamos analizar as restrições. Temos uma quantidade máxima de madeira disponível (310) e cada mesa e cada cadeira gastam uma certa quantidade deste material (30 e 20). Logo, temos uma restrição:
 
<math>30M + 20C \leq 310</math> (Restrição 1)
 
Da mesma forma, existe uma quantidade limitada de metais, o que nos dá a segunda restrição:
 
<math>5M + 10C \leq 113</math> (Restrição 2)
 
Além disso, sabemos que não podemos fabricar uma quantidade negativa de cadeiras ou mesas:
 
<math>M, C \geq 0</math>
 
Pronto! Terminamos de construir o nosso modelo!