Universidade Catlica Dom Bosco

Curso de Engenharia de Computao

Disciplina: Tpicos Avanados em Sistemas de Computao PO
Prof. Dr. Ricardo R. Santos
Entrega: 14/04/2009
1 Lista de Exerccios
(Programao Linear: Modelagem, Mtodo Grfico e Mtodo Simplex)
1) Uma determinada confeco opera com dois produtos calas e camisas. Como tratam-se de
produtos semelhantes,possuem uma produtividade comparvel e compartilham os mesmos recursos
.A programao da produo realizada por lotes do produto.
O departamento de produo informa que so necessrios 10 homens x hora para um lote de calas
e 20 homens x hora

para um lote de camisas .Sabe-se que no necessria mo de obra

especializada para a produo de calas ,mas so necessria 10 homens hora desse tipo de mo
de obra para produzir um lote um lote de camisas .O departamento pessoal informa que a fora
mxima de trabalho disponvel de 30 homens hora de operrios especializados e de 50 homens
hora no especializados .
Da planta de produo, sabemos que existem duas mquinas com capacidade para produzir os
dois tipos de produto; sendo que a mquina 1 pode produzir um lote da calas a cada 20 horas e
um lote de camisas a cada 10 horas, no podendo ser utilizada por mais de 80 horas no perodo
considerado.
So necessrios dois tipos de matria prima para produzir calas e camisas. Na produo de um
lote da calas so utilizados 12 quilos da matria prima A e 10 da B. Na produo de um lote de
camisas so utilizados 8 quilos da matria prima A e 15 da B.
O almoxarifado informa que por imposies de espao, s pode fornecer 120 quilos de A e 100
quilos de B no perodo considerado.
Sabendo-se que o lucro pela venda de 800 reais nos lotes das camisas e de 500 nos lotes das
calas. Formule o problema e maximizar o lucro da operao produtiva em pauta.
2) Uma empresa administradora agrcola deve decidir o quanto vai plantar de cana-de-acar e
algodo. Os lucros so de R$ 2.000,00 por alqueire de cana-de-acar e de R$ 1.000,00 por
alqueire de algodo. Suponha que suas limitaes sejam: terra disponvel de 8 alqueires e gua
disponvel para irrigao de 80.000 litros sendo que deseja-se plantar no mximo 4 alqueires de
cana-de-acar. Cada alqueire de cana-de-acar requerer 10.000 litros de gua para irrigao e
cada alqueire de algodo requerer 20.000 litros de gua. Modele e resolva o problema.
3) Resolva novamente o problema anterior supondo que seja requerido que mais de 50% do total
cultivado sejam plantados com algodo.

4) Uma companhia de armazns tem 1200 dlares para alocar a um de seus armazns. Trs
produtos 1, 2 e 3 exigem 30, 3 e 15 m2 de espao por unidade, respectivamente. H 1500 m2 de
espao disponvel. O produto 1 custa 12 dlares, o produto 2 custa 4,50 dlares e o produto 3 custa
17 dlares. Quanto de cada produto deve ser comprado se os preos de venda dos produtos 1, 2 e 3
so, respectivamente, de 15, 6 e 21 dlares, de modo a maximizar o lucro? Formule o resolva
problema.
5) A administrao de uma fazenda est estudando a diviso de sua propriedade nas seguintes
atividades produtivas:
a) Arrendamento - Destinar certa quantidade de alqueires Para a plantao de cana de acar, a
uma usina local, que se encarrega da atividade e paga pelo aluguel da terra R$ 300,00 por alqueire
por ano;
b) Pecuria - Usar outra parte para a criao de gado de corte. A recuperao das pastagens
requer adubao (100 kg/alqueire) e irrigao (100.000 litros de gua/alqueire) por ano. O lucro
estimado nessa atividade de R$400,00 por alqueire por ano.
c) Plantio de Milho - Usar uma terceira parte para o plantio de milho. Essa cultura requer 200 kg por
alqueire de adubos e 200.000 litros de gua por alqueire para irrigao por ano. O lucro estimado
nessa

atividade

de

R$

500,00

por

alqueire

por

ano.

A disponibilidade de recursos por ano de 12.750.000 litros de gua, 14.000 kg de adubo e 100
alqueires de terra. Quantos alqueires dever destinar a cada atividade para proporcionar o melhor
retorno?

6) Trs produtos qumicos derivados do petrleo P1, P2 e P3 so utilizados na produo de dois

tipos de leo para motor M1 e M2. Conhecemos as composies percentuais das misturas (tabela
Q1), a disponibilidade de P1, P2 e P3 (tabela Q2) e os lucros unitrios da venda de cada um dos
dois tipos de leo para motor (tabela Q3). Deseja-se saber como planejar a produo de modo a
maximizar o lucro total. Pode-se imaginar aqui que se trata do planejamento mensal da firma, em
funo de um fornecimento conhecido e dos preos e custos estabelecidos (ou previstos) para o
perodo. Admite-se que o mercado tem capacidade para absorver toda a produo.
Quadro Q1 -

Quadro

P1

P2

P3

M1 30

50

20

M2 60

15

25

Q2

Estoque

em

gales

Quadro Q3 - Lucro
em R$ por galo

P1

P2

9000 7500

P3

M1

M2

4000

12

10

7) Uma pequena fbrica de papel toalha manufatura trs tipos de produtos A, B e C. A fbrica
recebe o papel em grandes rolos. O papel cortado, dobrado e empacotado. Dada a pequena
escala da fbrica, o mercado absorver qualquer produo a um preo constante. O lucro unitrio de
cada produto respectivamente R$ 1,00, R$ 1,50, e R$ 2,00. O quadro abaixo identifica o tempo
requerido para operao (em horas) em cada seo da fbrica, bem como a quantidade de
mquinas disponveis, que trabalham 40 horas por semana. Planeje a produo semanal da fbrica.
Seo
Corte
Dobra
Empacotamento

Produto A
8
5
0,7

Produto B
5
10
1

Produto C
2
4
2

Qde. Mquina
3
10
2

8) Um fundo de investimentos tem at R$ 300.000,00 para aplicar em duas aes. A empresa D

diversificada (tem 40% do seu capital aplicado em cerveja e o restante aplicado em refrigerantes) e
espera-se que fornea bonificaes de 12%. A empresa N no diversifica (produz apenas cerveja)
e espera-se que distribua bonificaes de 20%. Para este investimento, considerando a legislao
governamental aplicvel, o fundo est sujeito s seguintes restries:
a) O investimento na empresa diversifica pode atingir R$ 270.000,00.
b) O investimento na empresa no-diversificada pode atingir R$ 150.000,00.
c) O investimento em cada produto (cerveja ou refrigerante) pode atingir R$ 180.000,00.
Pede-se: Qual o esquema de investimento que maximiza o lucro?

9) Um criador de animais de pequeno porte alimenta os animais com cinco tipos de rao, cuja
composio de nutrientes (unidades/Kg) est mostrada abaixo:
Nutrientes
Protenas
Carboidratos
Gordura
Custo/Kg

Rao A
30
60
5
0,20

Rao B
20
20
10
0,30

Rao C
15
60
5
0,40

Rao D
80
20
3
0,50

Rao E
20
20
2
0,25

O criador calculou as necessidades dirias de alimentao de cada animal em, pelo menos, 80
unidades de protena, 120 unidades de carboidratos e 30 unidades de gordura. Qual deve ser a
mistura das raes acima a custo mnimo?

10) Uma fbrica de computadores produz dois modelos de microcomputadores A e B. O modelo A

fornece um lucro de R$ 180,00 e B, de R$ 300,00. O modelo A requer, na sua produo, um

gabinete pequeno e uma unidade de disco. O modelo B requer 1 gabinete grande e 2 unidades de
disco. Existem no estoque 60 do gabinete pequeno, 50 do gabinete grande e 120 unidades de disco.
Pergunta-se: Qual deve ser o esquema de produo que maximiza o lucro?

11) Uma empresa produz televiso em 3 fbricas: So Paulo, Joo Pessoa e Manaus. Os pontos
principais de revenda, com as respectivas encomendas mensais so:
Rio de Janeiro
Salvador
Aracaj
Macei
Recife

6.000 unidades
5.000 unidades
2.000 unidades
1.000 unidades
3.000 unidades

A produo mxima mensal em cada fbrica :

So Paulo
Joo Pessoa
Manaus

10.000 unidades
5.000 unidades
6.000 unidades

O custo de transportes das fbricas at as revendas dado pelo quadro abaixo:

R$ por 1.000 unidades de TV
De/Para
(1) So Paulo
(2) Joo Pessoa
(3) Manaus

Rio de Janeiro (1)

1.000
4.000
6.000

Salvador (2)
2.000
2.000
4.000

Aracaju (3)
3.000
1.500
3.500

Macei (4)
3.500
1.200
3.000

Recife (5)
4.000
1.000
2.000

Determinar o nmero de unidades produzidas em cada fbrica e entregues a cada revenda, a fim de
minimizar o custo de transporte.

12) Uma central industrial de reciclagem usa dois tipos de sucada de alumnio, A e B, para produzir
uma liga especial. A sucata A contm 6% de alumnio, 3% de silcio e 4% de carbono. A sucata B
tem 3% de alumnio, 6% de silcio e 3% de carbono. Os custos por tonelada das suctas A e B so
R$ 100,00 e R$ 80,00, respectivamente. As especificaes da liga especial requerem que 1) o teor
de alumnio deve ser no mnimo 3% e no mximo 6%; 2) o teor de silcio deve ficar entre 3% e 5%; e
3) o teor de carbono deve ficar entre 3% e 7%. Determine o mix timo (de mnimo custo) de sucatas
que deve ser usado para produzir 1000 toneladas da liga.

13) Resolver graficamente e fornecer os valores timos para as variveis dos problemas a seguir:
a) Maximizar 4x1+6x2

s.a

8x1+7x2<=56
x2<=5
x1<=4
x1, x2>=0

b) Minimizar 2x1+x2
s.a

x1+x2>=10
2x1+3x2>=14
x1, x2>=0

c) Maximizar 3x1+x2
s.a

2x1+x2<=30
x1+4x2<=40
x1,x2>=0

d) Maximizar 3x1 + 5x2

s.a

x1 <= 4
2x2 <= 12
3x1 + 2x2 <= 18
x1 >= 0
x2 >= 0

e) Maximizar -2x1 - 2x2

s.a

3x1 - 4x2 <= 18

8x1 - 3x2 <= -24
6x1 + 8x2 <= 24
3x1 + 5x2 <= 21
x1 <= 3
x2 >= 0

f) Maximizar -2x1 - 5x2

s.a

2x1 - 2x2 <= 10

7x1 + 3x2 >= -21
-2x1 + 3x2 >= -6
3x1 + 9x2 <= 27
x1 >= -1

x2 >= -4
14) Na fabricao de dois de seus produtos, uma empresa utiliza dois equipamentos que limitam a
produo. Em um dado perodo de tempo, esto disponveis 30h do equipamento 1 e 80h do
equipamento 2. Para a fabricao de uma unidade do produto A, usa-se 1 hora do equipamento 1 e
2 horas do equipamento 2. J para uma unidade do produto B, so gastas 2 horas do equipamento
2. O equipamento 1 no toma parte na produo do produto B. Uma unidade do produto A produz
um lucro de R$ 150,00, enquanto que cada unidade do produto B gera um lucro de R$ 50,00.
a) Formular o problema de PL que maximiza o lucro
b) Resolver graficamente.
15) Na fabricao de dois produtos, X e Y, as seguintes restries so vlidas quanto aos dois
recursos escassos que so utilizados:
x + 2y <= 80
2x + 2y <=120
x= nmero de unidades produzidas do produto X
y= nmero de unidades produzidas do produto Y
Sabe-se tambm que cada unidade do produto X fornece um lucro de R$ 20,00 e cada unidade do
produto Y leva a um lucro de R$ 30,00.
a) Formular o modelo de PL que maximiza o lucro
b) Resolver o problema graficamente.

16) Usando a funo linprog do Matlab resolve os seguintes problemas de PL. Caso exista soluo
tima, fornea o valor timo e o valor avaliado nos pontos. Caso no existe uma soluo tima,
justifique.
a) Maximizar 2x1+5x2+2x3
s.a

3x1+10x2+2x3<=600
x1+2x2<=162
2x1+5x3<=700
x1, x2, x3>=0

b) Maximizar 2x1+3x2
s.a

x1+x2<=100
x1+2x2<=120
x1, x2>=0

c) Minimizar x1+4x2
s.a

x1+2x2<=75
x1<=20
x1, x2>=0

17) No problema a seguir (j visto em sala):

Maximizar f(xluxo, xbsico)=100xluxo +50 xbsico
s.a.

10xluxo + 8 xbsico <=25.000

xluxo + xbsico <=4.500
0<=xluxo <=1.500 e 0<= xbsico <=6.000

a) Represente a regio factvel com um plano cartesiano e determine a soluo tima

b) Escreva o problema na forma padro
c) Aplique o mtodo simplex, considerando a base inicial (partio B para a 1. Iterao) formada
pelas colunas das variveis de folga e determine a soluo tima.
d) Calcule o vetor multiplicador simplex T=cTBB-1 para cada iterao do mtodo simplex. Utilize o
MatLab para realizao dos clculos (Utilize C (linha) para calcular a transposta da matriz C e inv(C)
para calcular a inversa de C). Obs: Note que: cTB so as constantes das variveis que pertencem
partio bsica na funo objetivo e que B-1 a inversa da matriz formada pelos coeficientes das
variveis que esto na partio bsica. Como exemplo:
Minimizar f(x1,x2, x3, x4, x5)= -2 x1- x2+0 x3+0 x4+0 x5
s.a

x1+ x2+ x3
x1

=4
+ x4

x2

=3
+ x5 = 7/2

Considerando que a partio inicial formada por B=[a1 a2 a5] e N=[a3 a4] ou seja:

1 0
1 1 0
N = 0 1
B = 1 0 0
0 0
0 1 1 e

Nesse caso, observe que as variveis x1, x2 e x5 foram escolhidas como bsicas. Assim:
T

= ( 2

1 0 ) que, como pode ser observado, so os coeficientes das variveis da partio

bsica na funo objetivo.

18) Uma cooperativa de latcnios fabrica trs produtos: leite pasteurizado, queijo fresco e iogurte. A
cooperativa recebe diariamente 100 mil litros de leite, os quais devem ser processados no mesmo
dia. H um compromisso de abastecer o mercado dirio de no mnimo 50 mil litros de leite

pasteurizado, cuja contribuio ao lucro de R$ 0,07/litro. Um kg de queijo fresco consome 10 litros

de leite, enquanto um litro de iogurte consome 2,5 litros de leite. As contribuies ao lucro so:
queijo R$ 1,04/kg de queijo e iogurte R$ 0,20/litro de iogurte. O mximo que o mercado assimila
diariamente de cada produto de 60 mil litros de leite pasteurizado, 3500 kg de queijo e 20 mil litros
de iogurte. Determinar as quantidades ideais de cada produto de modo a maximizar o lucro.
19) Considere uma fbrica de pr-moldados que produz dois tipos de vigas cujas demandas para os
prximos 3 perodos de venda so dados:

Demanda de vigas

Perodo 1

Perodo 2

Perodo 3

Item 1

100

90

120

Item 2

40

50

80

Os produtos utilizam os mesmos tipos de recursos, porm em quantidades diferentes. Um centro de

trabalho est disponvel para a produo dos dois itens e cuja disponibilidade de 40h por perodo e
que cada unidade do item 1 utiliza 15 minutos e cada unidade do item 2 necessita de 20 minutos. Os
custos de produo por perodo so dados na tabela:

Custos de produo

Perodo 1

Perodo 2

Perodo 3

Item 1

20

20

30

Item 2

20

20

30

Admite-se que a produo possa ser antecipada e estocada para ser utilizada nos perodos
seguintes. Os custos de estocagem so dados a seguir (por exemplo, uma unidade do item 1 pode
ser produzida no perodo 2 e guardada em estoque para atender a demanda do perodo 3 por R$
3,00/unidade).

Custos

de Perodo 1

Perodo 2

estocagem
Item 1

Item 2

2,5

3,5

O objetivo definir um plano de produo de modo que os pedidos sejam atendidos ao menor custo
de produo e estocagem. Os estoques iniciais so nulos e, ao final do horizonte de planejamento
(perodo 3), tambm sejam nulos.
20) Uma indstria de papel produz bobinas-jumbo de L=400cm de largura e cada uma pesa T=1
tonelada. Os jumbos devem ser cortados em bobinas menores nas larguras e quantidades

apresentadas na tabela a seguir, conforme solicitao de diversos clientes. O objetivo ento

minimizar o nmero de bobinas cortadas em cada padro de corte.

Dados da Demanda
Larguras

Quantidades

40cm

5 toneladas

45cm

3,5 toneladas

55cm

4 toneladas

60cm

5 toneladas