SCAN QUESTOES PO PROGR LINEAR

Prévia do material em texto

30 Capítulo 2
§xercício§ 2"3
t: Obtenha a solução ótima para o problema abaixo pelo
método analítico apresentado nesta seção. (Compare
o resultado com a solução encontrada para a questão
1 dos Exercícios 2.1 .)
lvlaxZ=4xt+3xt
x, + 3xr< 7
2x, + 2xr< 8
x,+ xr<3
xr< 2
x,, xr> o
2. Solucione o problema de programação linear abaixo
utilizando o método analítico visto nesta seçáo. (Com-
pare o resultado com a solução encontrada na questáo
3 dos Exercícios 2.1 .)
ltlaxZ= 4xt+Bxt
s.r.
3x, + 2xr< 18
v +v <5"1 ' ") - "
x,<4
x,, xr> 0
3" Resolva pelo método analítico'(dicionário) o seguinte
problema de programaÇão linear.
ÍVlaxZ=2xt+6xz
4x, + 3xr( 12
2x, + xr38
x,, xr) 0
4. Encontre a solução otima do problema de programação
linear abaixo por meio do método analítico (dicionário):
lvlaxZ-2r,*x2+x3
3x,+xr+xr<60
xt-x2+xr<10
x1+x2-xr<20
x,, xy xr) 0
§. Determine, usando o metodo analítico (dicionário), a
solução otima do seguinte PPL:
It4axZ = 8xr + 6xr+6xr+8xo
x, + 2xr+ 3xr+ xoa 15
x1 + x)+ 2xr+ 3xo< 13
x,, xy xy xo) 0
&, Um agricultor tem uma fazenda com 200 km2onde pla-
neja cultivar Írigo, arroz e milho. A produção esperada
e de 1.800 kg por km2 plantado de trigo, 2.100 kg por
km2 plantado de arroz e 2.900 kg por km2 plantado
de milho. Ele tem condiçóes de armazenar no máximo
700 000 kg de qualquer um dos produtos. Sabendo
que o trigo dá um lucro de R$ 1,20 por kg, o arroz,
R$ 0,60 por kg, e o milho, R$ 0,28 por kg, usando o
metodo analítrco (dicionário), determine quantos km2
de cada produto devem ser plantados para maximizar
o lucro do agricultor.
7. A Capitão Caverna S.4., localizada em Pedra Lascada,
aluga três tipos de barcos para passeios marítimos: jan-
gadas, supercanoas e arcas com cabines. A companhia
fornece com o barco um capitão para navegá-lo e uma
tripulação, que varia de acordo com a embarcação: 1
funcionário para jangadas,2 para supercanoas e 3 para
arcas. A companhia tem 4 jangadas, 8 supercanoas e 3
arcas, e, em seu corpo de funcionários, 10 capitães e 1B
tripulantes. O aluguel e por diárias e a Capitão Caverna
S.A. lucra 50 marÍins por jangada, 70 marfins por super-
canoas e 100 marfins por arca. Quantos barcos de cada
tipo devem ser alugados para que a empresa tenha o
maior lucro possível? De quanto é esse lucro? (Resolva
pelo metodo analítico visto nesta seÇão.)
§, A empresa de artigos de couro Pele tVimosa Ltda.
fabrica dois tipos de produtos: malas e mochilas.
As malas são vendidas com um lucro de R$ 50,00
por unidade e o lucro unitário por mochila e igual a
R$ 40,00. A quantidade de horas necessária para con-
feccionar cada produto, assim como o número total de
horas disponíveis em cada departamento, sào apresen-
tados na tabela a seguir.
Horas necessárias
Mala Mochila
20
03
22
6/\ 3/2
1 . Corte
l. lrnqrmento
3. Costura
4. Embalagem
300
540
440
300
a. Sabendo que há uma demanda excedente tanto de
malas quanto de mochilas, determine quantas uni-
dades de cada produto a Pele Mimosa Ltda. deve
fabricar diariamente para maximizar o seu lucro.
(Resolva pelo método analítico.)
b. Se temos a informação de que a empresa produz
diariamente 120 unidades de malas e 30 unidades
de mochilas, em quanto o planejamento otimo au-
menta o lucro em relaçáo ao existente?
Departamento
§" A Picolé Lelé é a marca local preferida pelos habitantes
das llhas Calorândicas, que consomem todos os picolés
cremosos que a empresa consegue Íabricar. No entan-
to, por se localizar no meio'do oceano, a Picolé Lele
Ltda. tem algumas restriçÕes de fabricação, devido à
escassez de materia-prima fresca. Preocupados em ma-
ximizar o lucro da Íirma, seus dirigentes elaboraram o
seguinte quadro informativo, para que possamos aju-
dá-los, por meio do método analítico estudado nesta
seção. a descobrir quantos picolés de cada sabor devem
produzir diariamente de forma a maximizar o lucro da
companhia.
Lucro
Sabor por
picolé
l,zlorango R$ 1,00
Uva R$ 0,90
Limão R$ 0,95
lVláximo
disponível
Programação linear 31
1{}. A empresa Serra Serra Serrador fabrica três tipos de
madeiras compensadas.(placas de aglomerados). Os
dados a seguir resumem a produção em horas por
unidade em cada uma das três operaçóes de produ-
ção, o tempo máximo disponível em cada operação e
o lucro unitário de cada placa.
Aglomerado operações ern horas Lucro por
I tt g11 unidade
Placa A
Placa B
Placa C
Tempo máximo
disponível
2
5
10
900
2
)
3
400
4
2
2
600
R$ 40,00
R$ 30,00
R$ 20,00
Quantas unidades de cada placa de aglomerado
0,45
0,50
0,40
200
0,50
0,40
0,40
150
0,10
0,1 5
nrn
60
vem ser produzidas, de maneira a otimizar o lfgúu
serraria? Resolva pelo método analítico (Oicion\
\
ProgramaÇão linear e seus
teoremas
Vamos agora apresentar alguns teoremas a respeito das
soluçÕes de um problema de programação linear. Para tal,
necessitamos da deÍinição de um conjunto convexo. Em
vez de tentarmos deÍini-lo com o rigor matemático, utili-
zaremos uma definição intuitiva. Um conjunto convexo
e um conjunto de pontos em que todos os seqmentos de
reta que unem dois de seus pontos são internos ao con-
junto, isto é, todos os pontos de cada segmento também
pertencem ao conjunto original. Graficamente, um exem-
plo de conjunto convexo e não convexo é representado na
Figu ra 2. 1 9.
Naturalmente, só podemos visualizar essa definição
graficamente quando existem apenas duas variáveis no
PPL. Passemos, então, a definição de alguns teoremas
pertinentes ao estudo de programação linear. Foge do
escopo deste texto a demonstração desses teoremas. Su-
gerimos aos leitores interessados em suas demostraçóes
alguns textos mais avançados, como Hiller & Liberman
(1 ees)
Teorema í
O conjunto de todas as so/uçôes viáveis de um modelo de
programação linear é um conjunto convexo.
lâ'*nrexl;r ãâ
Toda soluçao compatível basíca (solução obvia) do sistema
de equaçoes lineares (dícíonario) de um modelo de progra-
mação linear é um ponto extremo do conjunto de so/uçoes
viáveis, isto e, do conjunto convexo de soluçoes.
'ísrlrene;l §l§
Se uma função-objetivo possui um unico ponto otimo finito,
então esse é um ponto extremo do conjunto convexo de
so/uçoes viaveis.
tH
Conjunto Conjunto
não convexoconvexo
Figura 2.19 Representação gráfica de coniuntos convexos
e não convexos.
Quantidade
de leite em
cada picolé
(litros)
Quantidade
de açúcar em
cada picolé
Polpa de
Íruta em
cada picolé
ipor 100 gramas) (litros)
4. Encontre a solução ótima do seguinte problema de
programação linear testando o valor da função-obje-
tivo em cada um dos pontos extremos do conjunto de
soluçoes viáveis:
ItlaxZ -80x, +75x,
s. r.
x, + 3xr< 4
2x,+5xr<150
x1' x2> 0
5. Resolva o problema de programaçáo linear abaixo tes-
tando o valor da função-objetivo em cada um dos pon-
tos extremos do conjunto de soluçóes viáveis:
lVlinZ=4x,+8x,
s. r.
3x, + 2xr< 18
x,+xr>5
xr<4
x1' x2> o
6. As indústrias Saracura Produtos Farmacêuticos desejam
produzir dois medicamentos, um analgésico e um an-
tibiotico, que dependem de duas matérias-primas Á e
B, disponÍveis em quantidades de B e 5 toneladas, res-
pectivamente. Na fabricação de 1 t de analgésico são
empregadas 1 t da matéria A e 1 t da matéria B, e na
fabricação de 1 t de antibiotico são empregadas 4 t de A
e 1 t de B. Sabendo que cada tonelada de antibiotico é
vendida a R$ 8,00 e de analgésico a R$ 5,00, encontre,
por meio da determinação dos pontos extremos do con-
junto de soluçÕes viáveis, a quantidade de toneladas de
medicamentos a ser produzida pelas indústrias Saracura,
de maneira a maximizar sua receita.
7, Uma pequena malharia produz dois tipos de camisas: de
manga curta e de manga comprida. Toda a produção é
Íeita e vendida para um distribuidor, que compra tudo o
que é produzido. A confecção de cada camisa passa por
três seçóes de trabalho: corte, costura e acabamento. A
Tabela I mostra os tempos necessários em cada seção:
'l';rL*l;r i Tempo de fabricação de
seção de trabalho
Tempo de
Produto
uma camisa em cada
fabricação (em horas)
Programação Iinear 33
'l';illrlr;2 Limites de capacidade de fabricação
Seção de trabalho Homens/hora por semâna
Corte 214
Costura 1 B0
Acabamento 330
Utilize os teoremas apresentados na Seção 2.3 para de-
terminar a quantidade de cada tipo de camisa que deve
ser Íabricada de maneira a maximizar o lucro da em-
presa, sabendo que o lucro unitário proporcionado pela
camisa de manga curta é de R$ 2,00 e o proporcionado
pela camisa de manga comprida e de R$ 3,00.
{*. A indústria Bonecas Sinistras S.A. produz dois tipos de
boneca. a Vampiresca e a Lobimulher. O processo de
montagem de cada uma dessas bonecas requer duas
pessoas. Os tempos de montagem são os seguintes:
Modelo
Vamprresca
Lobimulher
lrláximo de horas disponíveis
Montador 1 Montador 2
6 mrn 2 min
3 min 4 mrn
BB
A quantidade de horas por semana disponíveis em
cada seção de trabalho é apresentada na Tabela 2:
A política da companhia e a de balancear toda a mão de
obra em todos os processos de montagem. Na verdade,
a gerência deseja programar o trabalho de modo que
nenhum montador tenha mais de 30 minutos de traba-
lho por dia do que o outro. lsso quer dizer que, em um
período regular de oito horas, os dois montadores de-
verão ter um mínimo de sete horas e meia de trabalho.
Considerando que o mercado está disposto a comprar
toda a produçáo da Bonecas Sinistras S.A. e que a Íirma
tem um lucro de R$ 2,00 por unidade de Vampiresca
e R$ 1,00 por Lobimulher, quantas unidades de cada
boneca devem ser produzidas por dia? Quanto tempo
trabalhará cada montador por dia? (Resolva por meio
da determinação dos pontos extremos do conjunto de
soluçÕes viáveis.)
11" Um jovem está saindo com duas namoradas: Sheila e Ana
Paula. Ele sabe, por experiência, que:
. Ana Paula, elegante, gosta de Írequentar lugares so-
fisticados, mais caros, de modo que uma saída de três
horas custará R$ 240,00.
. Sheila, mais simples. prefere um divertimento mais
popular, de modo que uma saída de três horas lhe
custará R$ 160,00.
r Seu orçamento permite-lhe dispor de R$ 960,00
mensais para diversão.
I\langa curta
li4anga comprida
Corte
)
3
Acabamento
5
3
Costura
34 Capítulo z
r Seus afazeres escolares lhe dão liberdade de' no má-
ximo. 18 horas e 40.000 calorias de sua energia para
atividades sociais.
. Cada saída com Ana Paula consome 5 000 calorias'
mas com Sheila, mais alegre e extrovertida' ele gasta
o dobro"
. Ele gosta das duas com a mesma intensidade'
Como o jovem deve planejar a sua vida social para ob-
ter o número máximo de saídas? (Encontre a solução
otima determinando os pontos extremos do conjunto
de soluçoes viáveis.)
1*. A Cat Without Fat S.A. é uma empresa fabricante de
comida enlatada para gatos, cuio principal diÍerencial
competitivo é o baixo nível de gordura de seus produtos'
A presa utiliza prod Ução ma mistura deem na
(75 proteína e 2 % de go rdura) UE custa RS
u
Yo de 5 q
por quilo e/ou uma m istura de pe ixe (e0
o/o de prote
por qu o aue0% gord ura)de que custa R$ 005,
nação matérias-Primas empresa eve utilizab a
de prepa rar ma COmida para gatos m,
m;rCO
5 % de ra ao menor CUSTO possÍvel
d de
onu
gord
a" Ir,4odele o problema. Dica: as variáveis de de:
deste problema representam os percentua s
matérias-primas utilizados para preparar o
tado, devendo, portanto, ter valores entre C :
(ou entre 0% e 100%).
h. Encontre a solução otima por meio da determi
do valor da função-objetivo em cada ponto
do conjunto de soluçoes viáveis'
efetuar essa modificação, devemos trocar de lado tu{
variáveis do problema (nesse rol estão incluídas as ve-
originais, as de folga e Z), isto é, levar todas as variáve s
o lado esquerdo das equaçÕes Dessa maneira' podemcs
seguir o dicionário inicial modiÍicado para o problema :
Dicionário inicial modificado
Z-5x,-2xr:g
x,*xr:3
- L- -À
^ 
| A- - a24
xr* 2xrt xr: 9
Vale notar que, no dicionário inicial modificado' "
riáveis da equação que representam a f unção-objetit:
caram de lado, isto e, quando querÍamos aumentar c
Z, p roc ta VA mos AS vafl áveis a eq U aÇã qu
por qu lc
U
Programação linear e a forma
tabular
- -?-v
^ -J3
x:4-x-"4 t
\/ 
- 
U 
- 
V 
- 
/YA, - J5L
x1, x2,x3' xo, xr> 0
coef entes pos itivos. AS VA riáveis m ramom
agor roc a q te ha
O procedimento que relatamos na Seção 2 2 e chamado
de metodo simplex analítico Quando estivermos resolven-
do um problema de programação linear manualmente' será
conveniente utilizar a forma tabular do método simplex'
Em vez de utilizar os dicionários, devemos usar o quadro
simplex para registrar apenas as informaçÕes essenciais: os
coeficientes das variáveis, as constantes das restriçÕes e as
variáveis básicas e não básicas
Devemos, portanto, simplificar a Íorma de um di-
cionário, estabelecendo um quadro equivalente' Depois'
devemos verificar como cada operação analítica realizada
pode ser automatizada por meio de regras de comando'
Por Íim, devemos verificar como tomar a decisão de parada
do algoritmo
Voltemos ao nosso primeiro exemplo e ao seu respectlvo
dicionário inicial, já com a introdução das variáveis de folga'
Problema forma-padrão Dicionário inicial
ft/laxZ:5x,12x, Z:5x,+ 2x,
s. r.
de d o eU
C o d eudaC
eq çá deve mo a uraU o S p S eu
n mna
eg tivos A de sã o de rar rerapa cor q U do não tiven a naC o
mais variáveis com coeficientes negativos, ou sela' qt
todos os coeÍicientes tiverem sinal náo negativo 
(pc
ou zero).
Agora, a transformaçáo do dicionário inicial moc
do paã o quadro inicial e direta Primeiro, vamos de'x <31-
x <4'') -
x -f 2x-<91 2-
x >0.x->0
formato do quadro, de maneira a facilitar sua comp
O quadro terá, do lado esquerdo, as variáveis básicas
lado direito, as constantes das equaçÕes No meio Í
Lembre-se de que as variáveis originais do problema são
as não básicas e as variáveis de Íolga são as básicas (lado
esquerdo das equaçoes) O proximo passo para a obtenÇáo
do quadro inicial é a modificação do dicionário inicial para
obter o dicionário inicial modificado, que servirá como ponto
de partida para a formação do quadro simplex inicial Para
todos os coeficientes das restriÇÕes e da funçáo-ob,:
Para pad ronização, colocaremos na primeira linha a e
çáo (zero) que representa a funçáo-objetivo lsso 
t^
obrigatorio, mas facilita a explanaçáo e a compreensã:
método.
A Tabela 2.1 representa o quadro inicial do nossc
blema.
3, Obtenha a solução otima para o problema a seguir
utilizando o método simplex apresentado nesta seção.
(Compare o resultado com o encontrado na questão
3 dos Exercícios 2.1, que apenas difere deste exercício
pelo sinalda primeira restrição.)
l\,/laxZ:4x,+8x,
s. r.
3xr-f 2xr= 18
x.+ x-<51 Z-
x-<4
l-
x, xr> 0
4. Obtenha a solução ótima para o problema abaixo utilizan-
do o método simplex apresentado nesta seção. (Compare
o resultado com o encontrado na questão 4 dos ExercÍcios
21.)
ltlin Z:8x,* 10x,
s. r.
-x-* x^ < 2
4x-+ 5x^> 20
x,<6
xr> 4
x1' x2> 0
5" Obtenha a solução otima para o problema abaixo utilizan-
do o método simplex apresentado nesta seção. (Compare
o resultado com o encontrado na questão 5 dos Exercícios
2.1.)
MaxZ:xr*3x,
s. r.
4x.* x >30I Z-
10x*2x-<101 Z-
x-. x^> 0
§. Uma firma faz três produtos e tem três máquinas dis-
poníveis para a produção. Para resolver sua escala de
produção, modele o seguinte PPL:
Max Z : xr* 4xr* 7x"
s. r.
60 < x, * 7xr* 4x, < 1 00 (horas na máquina 1)
60<2x,* x"! 7x"S 100 (horas na máquina 2)
60 < 8x,+ 4xr* xr< 100 (horas na máquina 3)
x, x, x") 0
Resolva o problema pelo método simplex tabular.
7. Um trem tem dois compartimentos de carga: um
dianteiro e um traseiro. O compartimento de carga
dianteiro tem uma capacidade de peso de 75.000 kg
e uma capacidade de volume de 40.000 m3. O com-
partimento traseiro tem uma capacidade de peso de
Programação linear 45
80.000 kg e uma capacidade de volume de 30.000
m3. A empresa dona do trem foi contratada para levar
cargas de arroz e feijão empacotados. O peso total
da carga de arroz disponível é de 85.000 kg; o peso
total da carga de feijão disponÍvel é de 100.000 kg.O volume por massa do arroz é 0,2 m3 pcr quilo, e o
volume por massa do Íeijão é 0,4 nr3 por quilo. Por
uma questão técnica, o compartimento traseiro deve
ter uma carga (em peso) no mínimo 20% superior ao
dianteiro. O lucro para transporiar arroz é de R$ 0,35
por quilo, e o lucro para transportar feilão é de R$
0,12 por quilo. A empresa dona do trem é livre para
aceitar toda ou parte da carga disponível. Ela quer
saber quantos quilos de arroz e de feijáo deve trans-
portar para maximizar o lucro. Resolva pelo método
simplex tabular.
I Óleos Unidos S.A. é uma empresa do ramo de deriva-
dos de petroleo que manufatura três combustíveis espe-
ciais com base na mistura de dois insumos: um extrato
mineral e um solvente. No processo de produçâo não
existe perda de material, de forma que a quantidade de
Iitros de extrato mineral somada à quantidade de litros
de solvente utilizada para a fabricação de um tipo de
combustível resulta no total de litros daquele combus-
tível fabricado. A proporção da mistura está descrita na
tabela a seguir:
Combustível Combustível Combustível
ABC
Extrato
mineral
{,
Solvente
B litros
5 lrtros
5 litros
4 litros
4 litros
2litros
1,§. Um pequeno entregador pode transportar madeira
ou Írutas em seu caminhão. Ele cobra R$ 20,00 para
cada fardo de madeira e R$ 35,00 por saco de frutas.
Os fardos pesam 1 kg e ocupam 2 dm3 de espaço. Os
sacos de fruta pesam 1 kg e ocupam 3 dms de espaço.
Por uma questão de marketing pessoal, o entregador
desela entregar sempre os dois produtos. No mínimo
l7
1 Suponha que a Óleos Unidos tenha disponíveis dia-
riamente 120 litros de extrato mineral e 200 litros
de solvente. Por uma característica técnica, o solven-
te evapora com muita facilidade e, para viabilizar os
custos da empresa. pelo menos 70% do seu estoque
deve ser utilizado no mesmo dia. Os lucros liquidos
esperados para os três combustíveis são de R$ 20,00,
R$ 22,00 e R$ 18,00, respectivamente. Resolva pelo
método simplex tabular com o objetivo de maximizar
o lucro da Óleos Unidos.
46 Capítulo 2
20 kg de fardos e 30 kg de frutas devem ser entre-
gues em cada viagem. O caminhão tem capacidade
para transportar 12.000 kg e 10.000 dms. Formule
um problema de programação linear para determinar
quantos sacos de fruta e quantos Íardos de madeira
devem ser transportados para que o entregador ga-
nhe o máximo possÍvel. Resolva o problema pelo me-
todo simplex tabular e determine qual será o lucro do
entregador e como ele deve encher o seu caminhão'
1&. Uma indústria vende dois produtos em conserva, er-
vilha e milho, ao preço por tonelada de R$ 70,00 e
R$ 60,00, respectivamente. A fabricação dos produ-
tos e feita em toneladas e utiliza duas células de pro-
dução: limpeza e mistura. As duas células de produ-
ção estão disponíveis diariamente. Devido a c-3lü
eventuais, o tempo disponÍvel varia diariame':= rml
meio de um levantamento de dados passados : in*
partamento de produção determinou que ;< lr,t
células estivessem operacionais em no mínirr: 'I t
no máximo 16 horas por dia. A produção de I ::'-§r
lada de ervilha consome 5 horas de limpeza e - -tp
ras de mistura, e a produção de 1 tonelada de - ltü
consome 4 horas de limpeza e 5 horas de mis:--=
Formule um problema de programação linear = x
termine quantas toneladas de cada produto c:,sil
ser Íabricadas diariamente para se obter o -.,rÚ
Íaturamento possÍvel. Resolva o problema po'-':i{0
do método simplex tabular.