Índice
Programação
Linear
Infelizmente Programação Linear é uma
teoria que, acredito (estudei numa escola técnica bastante
fraca, à noite), seja ministrada e difundida somente no meio
universitário, o que é um grandíssimo
erro...
O que é
Programação Linear?
O objetivo da programação matemática,
da qual a programação linear é apenas
um dos casos mais simples e muito útil, é
distribuir recursos de forma ótima, ou seja de modo a ter o
máximo lucro ou mínimo prejuízo, por
exemplo.
Ao contrário do que pode sugerir a palavra
programação não se refere a
computadores, e sim a alocação
(distribuição) de recursos (financeiro,
matérias primas, etc), apesar de que a
utilização de computadores em
programação linear é a regra.
Segue um exemplo prático, extraído do livro
citado abaixo, para uma maior clareza:
"2.5.1. Análise das Atividades (escolha da
procução)
Uma determinada empresa está interessada em maximizar o
lucro mensal proveniente de quatro de seus produtos, designados por I,
II, III e IV. Para fabricar esses quatro produtos, ela utiliza dois
tipos de máquinas (M1 e M2) e dois tipos de
mão-de-obra (MO1 e MO2) que têm as seguintes
disponibilidades:
| Máquinas |
Tempo disponível (maquina-hora/mês) |
| M1 |
800 |
| M2 |
200 |
| Mão-de-obra |
Tempo disponível (homem-hora/mês) |
| MO1 |
12.000 |
| MO2 |
16.000 |
O setor técnico da empresa fornece os seguintes quadros de
produtividades:
a) Número de máquina-hora para produzir uma
unidade de cada produto:
| Máquinas |
Produto I |
Produto II |
Produto III |
Produto IV |
| M1 |
5 |
4 |
8 |
9 |
| M2 |
2 |
6 |
- |
8 |
Então para se produzir uma unidade do produto I consme-se 5
máquinas-hora da máquina M1 e 2
máquinas-hora da máquina M2. O produto III
não necessita da máquina M2 e consome 8 horas da
máquina M1 para cada uma de suas unidades produzidas.
b) Número de homem-hora para produzir uma unidade de cada
produto:
| Máquinas |
Produto I |
Produto II |
Produto III |
Produto IV |
| MO1 |
2 |
4 |
2 |
8 |
| MO2 |
7 |
3 |
- |
7 |
Precisa-se então de 2 homens-hora da mão-de-obra
MO1 e de 7 homens-hora da mão-de-obra MO2 para fabricar uma
unidade do produto I.
O setor comercial da empresa fornece as seguintes
informações:
| Produtos |
Potencial de vendas (unidades/mês) |
Lucro unitário (Cr$/unidade) |
| I |
70 |
10,00 |
| II |
60 |
8,00 |
| III |
40 |
9,00 |
| IV |
20 |
7,00 |
Deseja-se saber a produção mensal dos produtos I,
II, III e IV para que o lucro mensal da empresa, proveniente desses
quatro produtos, seja máximo. Formule um modelo de
programação linear que expresse o objetivo e as
restrições dessa empresa.
Sejam x1, x2, x3, x4 as produções mensais dos
produtos I, II, III, IV, respectivamente. O modelo, então,
será:
Maximizar Z=10.x1+8.x2+9.x3+7.x4
sujeito a
x1<=70
x2<=60
x3<=40
x4<=20
5.x1+4.x2+8.x3+9.x4<=800
2.x1+6.x2+8.x4<=200
2.x1+4.x2+2.x3+8.x4<=12000
7.x1+3.x2+7.x4<=16000
x1>=0
x2>=0
x3>=0
x4>=0"
Resolvendo este problema com o programa freeware LpSolve, citado
abaixo, obtemos:
D:\Eng\Otimizacao>lps abelardo.lp
Value of objective function: 1140
x1 70
x2 10
x3 40
x4 0
Assim para que o lucro seja máximo deve-se fabricar 70
unidades do produto I, 10 unidades do produto II, 40 unidades do
produto III e nenhuma unidade do produto IV, gerando um lucro
(máximo) de $1140.
O método clássico para
resolução de problemas de
programação linear é um chamado
Simplex revisado. Cuja descrição é
facilmente encontrada em livros sobre o assunto e, talvez na Rede,
(não procurei...).
Um livro muito bom
Livro: Introdução à
Programação Linear
Autor: Puccini, Abelardo de Lima
Editora: LTC - Livros Técnicos e Científicos
Editora S.A.
Impressões: 1972, 1975, 1976 e 1977
É um livro muito bom, mas isso só é
válido pra quem tem facilidade e conhecimentos de
resoluções de sistemas lineares e matrizes.
Existe uma ou mais edições mais recentes mas
desconheço maiores informações...
LpSolve (DOS - Win32 Console)
Um programa para resolução de problemas de
programação linear
(otimização de problemas lineares), pode resolver
para variáveis inteiras. Tem código fonte aberto
em linguagem C.
Baixar
versão Windows 32 bits (41kb).
Baixar
versão DOS (89kb). (Dei uma atualizada na
interface)
Ir
para ftp.es.ele.tue.nl/pub/lp_solve (Arquivos "oficiais")
Índice