INVESTIGACAO OPERACIONAL

Páginas: 12 (2866 palavras) Publicado: 11 de agosto de 2013
CAPÍTULO 2

Introdução à Programação Linear

1. Definição
Um problema de PL consiste em determinar valores não negativos para as variáveis de decisão,
de forma que satisfaçam as restrições impostas e que optimizem (minimizem ou maximizem) uma
função (real) linear dessas variáveis.

2. Formalização e modelação matemática de problemas de PL
Existem 2 formas diferentes de apresentar omodelo, conforme se pretenda maximizar ou
minimizar, que são as seguintes :

Maximizar (Minimizar)

Z = c 1 x 1 + c 2 x 2 +L+ c n x n

(1.1)

Sujeito a

a 11 x 1 + a 12 x 2 +L+ a 1n x n

{ ≤, =, ≥ }

b1

a 21 x 1 + a 22 x 2 +L+ a 2n x n

{ ≤, =, ≥ }

b2

(1.2)

...
a m1 x 1 + a m2 x 2 +L+ a mn x n

{ ≤, =, ≥ }

bm

x 1 , x 2 , L, x n ≥ 0

(1.3)

onde,
aij (i = 1,...,m; j = 1, ...,n) → coeficientes técnicos ou tecnológicos,
b1, b2, ..., bm → termos independentes (constantes de restrição ou segundos membros),
c1 , c2, . . . , cn → coeficientes da função objectivo (coeficientes de custo),

14

Formalização e modelação matemática de problemas de PL

x1 , x2, . . . , xn → variáveis de decisão (principais ou controláveis),
(1.1) → função objectivo(económica ou critério),
(1.2) → restrições (restrições funcionais), em que apenas se verifica uma das relações,
(1.3) → condições de não negatividade.
No entanto, o modelo é frequentemente apresentado nas seguintes formas típicas :
Maximizar (Minimizar)

Z = c 1 x 1 + c 2 x 2 +L+ c n x n

(2.1)

Sujeito a

a 11 x 1 + a 12 x 2 +L+ a 1n x n ≤ ( ≥ ) b 1
a 21 x 1 + a 22 x 2 +L+ a 2n x n ≤ (≥ ) b 2

(2.2)

...
a m1 x 1 + a m2 x 2 +L+ a mn x n ≤ ( ≥ ) b m
x 1 , x 2 ,L, x n ≥ 0

(2.3)

Estas duas formas são tão gerais quanto (1.1), (1.2) e (1.3), pois, mediante operações
convenientes, é sempre possível dar a qualquer problema uma daquelas formas. Com efeito, qualquer
problema pode ser reduzido a uma destas formas, da seguinte maneira :
qualquer problema de minimização podeconverter-se num de maximização, pois
Minimizar Z = − Maximizar (− Z)
restrições do tipo (≥) pode ser convertida em restrições do tipo (≤), mediante a multiplicação por (1) de ambos os membros,

a i1 x 1 + a i2 x 2 + L + a in x n ≥ b i ⇔ − a i1 x 1 − a i2 x 2 − L − a in x n ≤ − b i
restrições do tipo (=) pode ser convertida em 2 do tipo (≤) equivalentes, em conjunto, àquela,



a i1 x 1+ a i2 x 2 + L + a in x n ≤ b i


a i1 x 1 + a i2 x 2 + L + a in x n ≥ b i




a i1 x 1 + a i2 x 2 + L + a in x n = b i

a i1 x 1 + a i2 x 2 + L + a in x n ≤ b i


− a i1 x 1 − a i2 x 2 − L − a in x n ≤ − b i




variável livre (sem restrição de sinal) pode ser substituída pela diferença de variáveis não
negativas1 ( x j = x 'j − x 'j'

com x 'j , x 'j' ≥ 0 ),formulando-se de novo o problema em termos

destas variáveis.

1

Qualquer número pode ser obtido como a diferença de dois números não negativos.

Introdução à Programação Linear

Formalização e modelação de alguns problemas de PL

15

3. Formalização e modelação de alguns problemas de PL
Problema 1 :

Uma empresa de mobiliário de escritório pretende lançar um modelo de secretárias eestantes.
Pensa-se que o mercado pode absorver toda a produção de estantes, mas aconselha-se que a
produção mensal de secretárias não ultrapasse as 160 unidades.
Ambos os produtos são processados nas unidades de estampagem (UE) e de montagem e
acabamento (UMA).
A disponibilidade mensal em cada uma destas unidades é de 720 horas−máquina (h−m) na UE
e 880 horas−homem (h−h) na UMA.
Cadasecretária necessita de 2h−m na UE e de 4 h−h na UMA.
Cada estante necessita de 4 h−m na UE e de 4 h−h na UMA.
As margens de lucro unitárias estimadas são de 6 contos para as secretárias e de 3 contos para
as estantes.
Qual o plano de produção mensal para as secretárias e estantes que maximiza a margem de
lucro.
Formalização do problema :
Variáveis de decisão :
• quantidade de secretárias a...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Investigação operacional
  • Investigação operacional
  • Investigação Operacional
  • Investigação operacional
  • Investigacao Operacional
  • Investigação operacional
  • Investigação operacional
  • Investigação Operacional

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!