Í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...



PiratasDoTietê 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...).



PiratasDoTietê 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...



PiratasDoTietê 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
rymaeda@yahoo.com
http://www.ioxio.com.br