Universidade da Beira Interior – Departamento de Matemática
INVESTIGAÇÃO OPERACIONAL
Ano lectivo: 2008/2009
Cursos: Economia
Ficha de exercícios nº1
Resolução Gráfica e Formulações em Programação Linear
1.
Resolva graficamente o seguinte problema em Programação Linear:
Minimizar
Z =
Sujeito a
40 x1 + 36 x2
x1
8
x2 10
5 x1 + 3 x2 45
x1, x2 0
2.
Resolva graficamente o seguinte problema em Programação Linear:
Maximizar
Z =
Sujeito a
x1 + 4 x2
x1 x2 1
x1 + x2 0
x1 + 2 x2 4
x1, x2 0
3.
Resolva graficamente o seguinte problema em Programação Linear :
Maximizar
Z =
Sujeito a
x1 +
x1 x2
x2 3
x1
x1 +
5
x2 3
x1, x2 0
4.
Resolva graficamente o seguinte problema em Programação Linear :
Maximizar
Z =
Sujeito a
10 x1 5 x2
20 x1 + 50 x2 200
50 x1 + 10 x2 150
30 x1 + 30 x2 210
x1, x2 0
5.
Resolva graficamente o seguinte problema em Programação Linear :
Maximizar
Sujeito a
Z =
10 x1 + 18 x2
15 x1 + 24 x2 9000
20 x1 + 36 x2 36000
12 x1 + 16 x2 19200
x1, x2 0
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
1
6.
Resolva graficamente o seguinte problema em Programação Linear :
Maximizar
Z =
Sujeito a
4 x1 3 x2
x1 + x2 1
x2 1
x 1 + 2 x2 1
x1, x2 0
7.
Resolva graficamente o seguinte problema em Programação Linear :
Minimizar
Z =
Sujeito a
x1 + 2 x 2
x 1 + x2 = 2
2 x1 x2 4
x1 +
x2 2
x1, x2 0
8.
Resolva graficamente o seguinte problema em Programação Linear :
Maximizar
Z =
Sujeito a
x1 3 x2
x 1 + x2 0
x1
8
x2 10
x1 +
x2 = 10
x1, x2 0
9.
Resolva graficamente o seguinte problema em Programação Linear :
Maximizar
Z =
Sujeito a
x1 + 3 x2
x1 + x2 8
4 x1 + x2 26
x1 +
x2 4
x1, x2 0
10.
(Época Especial 2003)
Considere o seguinte problema em Programação Linear:
Max
s.a.
Z= -x1+4x2
-3x1+x2 6
x1+2x2 4
x2 -3
a) Represente graficamente o espaço admissível.
b) Determine a solução óptima através do método gráfico.
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
2
11.
(Mini-Teste nº1, 2005/2006, ME+MI+MA+EPGI+EI)
Considere o seguinte problema em Programação Linear:
Min Z = 4x1 + 2x2
Sujeito a:
2x1 + x2 4
x1 - x2 -1
x1, x2 0.
Qual das seguintes proposições é verdadeira?
[ ] A solução óptima é ilimitada; não existe um valor finito para a função objectivo.
[ ] Existem soluções óptimas alternativas: x*=(0, 4) é uma solução óptima, com Z*=8.
[ ] A solução óptima única é x*=(1, 2), com Z*=8.
[ ] A solução óptima única é x*=(0, 4), com Z*=8.
12.
(Mini-Teste nº1, 2005/2006, EC)
Considere o seguinte problema em Programação Linear:
Min Z = 2x1 + 4x2
Sujeito a:
x1 + 2x2 4
x 1 - x2 1
x1, x2 0.
Qual das seguintes proposições é verdadeira?
[ ] Existem soluções óptimas alternativas: x*=(2, 1) é uma solução óptima, com Z*=8.
[ ] A solução óptima é ilimitada; não existe um valor finito para a função objectivo.
[ ] A solução óptima única é x*=(2, 1), com Z*=8.
[ ] A solução óptima única é x*=(4,0), com Z*=8.
13.
Um estabelecimento produz e comercializa 2 qualidades de gelados: de nozes (C) e
de frutas (P). A loja encontra-se localizada numa animada área turística de modo que toda a
produção é sempre vendida.
Um cone de tipo C é vendido a 75 u.m. e um cone de tipo P a 60 u.m.. Um cone C
necessita de 4 gr de mistura de frutas e de 2 gr de noz moída. Um cone P requer 6 gr de
mistura de frutas e 1 gr de noz moída.
Em cada hora de laboração, existe capacidade para serem utilizadas apenas 96 gr de
mistura de frutas e 24 gr de noz moída.
a) Formule o problema em Programação Linear de modo a maximizar a receita em
cada hora.
b) Encontre a solução óptima do problema graficamente.
14. Uma empresa electrónica fabrica 2 tipos de circuitos impressos: A e B. Os do tipo A
são vendidos por 4000 u.m. e os do tipo B por 5000 u.m.. No processo produtivo, ambos
os tipos de circuitos passam por 2 máquinas. Na 1ª, os circuitos do tipo A são trabalhados
durante 4 horas e os do tipo B durante 5 horas. Na outra, os circuitos passam 4 e 3 horas,
respectivamente. A 1ª máquina pode funcionar durante um máximo de 32 horas por
semana, enquanto a outra máquina não pode exceder as 24 horas de funcionamento
semanalmente.
A empresa pretende maximizar a receita. Formule matematicamente o problema e
resolva-o graficamente. Qual a receita máxima que a empresa pode obter ?
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
3
15. Devido a alterações de mercado, os preços dos produtos A e B referidos no
problema anterior, caíram ambos para 3 mil u.m.. Em simultâneo, modificações no
processo produtivo, requeridas por um mais rigoroso controlo de qualidade, levaram à
aquisição de uma nova máquina, onde tanto o produto A como o B sofrem alterações
durante 1 hora. No entanto, esta máquina não pode funcionar menos de 7 horas semanais.
a) Reformule o problema com as novas condições.
b) Resolva o problema graficamente.
c) Dados quaisquer preços de venda de A e B, a solução obtida em b) altera-se?
16. Uma empresa labora em dois processos produtivos, fabricando 2 produtos: P1 e P2.
No primeiro processo, 1 kg de matéria-prima dá origem a 2 unidades de P1 e 1 unidade de
P2, gerando 20 g de um resíduo altamente poluente. No segundo processo, com 1 kg de
matéria-prima obtêm-se 1 unidade de P1 e 3 unidades de P2, gerando 10 g do mesmo
resíduo.
A empresa dispõe de 3 toneladas de matéria-prima e deve satisfazer encomendas de
2000 unidades de P1 e 4000 unidades de P2.
Atendendo a que a empresa pretende minimizar a quantidade produzida de resíduo
poluente:
a) Formule matematicamente o problema.
b) Resolva o problema graficamente, indicando: as quantidades de P1 e P2 produzidas
em cada processo, a quantidade de matéria-prima não utilizada e a de resíduo
poluente produzido?
17.
Para suportar os elevados custos de exploração mineira, a Escavatudo necessita de
encontrar um mínimo de 22Kg de ouro e 36Kg de prata por mês. Há duas minas em que a
empresa pode operar: minas A e B. Por cada dia dedicado à exploração da mina A, estimase que as quantidades de ouro e prata encontradas são, respectivamente, 2Kg e 3Kg. Da
mesma forma, por cada dia na mina B a empresa espera encontrar 1Kg de ouro e 4Kg de
prata.
A empresa pretende encontrar as quantidades necessárias à sua subsistência passando o
menor número de dias possível nas minas.
a) Formule o problema em Programação Linear.
b) Resolva o problema graficamente.
18.
A Valor Global tem uma carteira de clientes no valor de 100.000. Investidores
exigentes que são, os seus clientes colocam a condição de só poder investir esse capital em
acções e/ou obrigações da BVL. Cada euro investido em acções tem um retorno esperado
de 10 cêntimos, enquanto que com cada euro de obrigações estima-se um lucro de 15
cêntimos.
Os clientes exigem ainda que pelo menos 20% do capital total investido seja em
acções e que um mínimo de 40.000 sejam investidos em obrigações.
a) Formule o problema por forma a maximizar o lucro dos clientes da Valor Global
em Programação Linear. Resolva graficamente.
b) Suponha que por cada acção transaccionada obtém uma comissão de 20% sobre os
lucros dos seus clientes e que por cada obrigação essa comissão é de 10%. Que
alterações sofre a formulação da alínea anterior se pretender agora maximizar os
seus lucros e não os dos seus clientes? Resolva graficamente.
19. Os produtos 1, 2 e 3 são manufacturados passando por 3 operações : A, B e C. Os
tempos (em minutos) requeridos por unidade de cada produto, a capacidade diária das
operações de fabrico (em minutos/dia) e o lucro por unidade vendida de cada produto
(numa dada unidade monetária) são :
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
4
Operação
Tempo por unidade
Capacidade Operativa
Produto 1 Produto 2 Produto 3
(min/dia)
A
1
2
1
430
B
3
0
2
460
C
1
4
0
420
Lucro unitário (u.m.)
3
2
5
Supondo que toda a produção é vendida, formule o problema, de modo a obter um
lucro máximo.
20. Um agricultor pode usar 2 tipos de cereais para alimentar as suas galinhas. Os valores
nutritivos de cada cereal e o seu custo encontram-se na seguinte tabela:
Tipo de
cereais
1
2
Unidades nutritivas (u.n./Kg)
Vitamina A Vitamina B
Vitamina C
5
4
2
7
2
1
Custo/kg cereal
()
60
350
O número mínimo de unidades nutritivas (u.n.) requeridas por dia é de 8, 15 e 3
para as vitaminas A, B e C, respectivamente.
Sabendo que se pretende minimizar o custo da alimentação das galinhas, formule o
problema em Programação Linear.
21. A empresa PUBI Lda., promove publicidade e propaganda. Dispõe de um
orçamento para a próxima semana de 8000. O dinheiro é para ser usado entre quatro
meios de publicidade: Televisão, Jornal e dois tipos de publicidade na rádio. O objectivo da
empresa é chegar ao máximo de potenciais clientes. A tabela seguinte mostra o número de
potenciais clientes alcançados por cada um dos meios de comunicação. Fornece também o
custo da publicidade e o número máximo de spots e anúncios que podem ser comprados
por semana.
Audiência por Custo por spot() Número máximo de spots
spot
por semana
Televisão(minuto)
5000
800
10
Jornal (página)
8500
925
6
Rádio (30 sg, hor. nobre)
2400
290
20
Rádio (minuto, durante a tarde)
2800
380
22
Média
Questões contratuais obrigam a que a empresa faça no mínimo 5 spots de rádio em
cada semana. De modo a assegurar uma campanha equilibrada a gestão da empresa exige
que o dinheiro despendido na rádio não seja superior a 1800 em cada semana.
22.
(Época Especial 2003)
Um avião de ataque a incêndios na floresta pode transportar bombas explosivas e
contentores químicos. As características destas armas estão indicadas no seguinte quadro:
Peso (kg)
Volume (l)
Área coberta (ha)
Custo por unidade ()
bombas
228
142
0,4
400
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
contentores
114
284
0,6
300
5
O avião não pode transportar mais de 1140kg de peso, nem mais que 1136 litros de
volume. Formule o problema de modo a determinar a carga mais barata para apagar um
fogo numa área de 2,4 hectares.
23.
(Frequência 2002/2003)
A Companhia Vinícola do Dão produz dois tipos de vinho: Dão Reserva e Vinho
de Mesa. Os vinhos são produzidos a partir de 64 toneladas de uvas que a empresa
comprou este Outono. Uma tina de 5000 litros de vinho de Mesa exige 8 toneladas de uvas
e uma tinha de vinho Reserva exige 4 toneladas. A empresa dispõe de um máximo de 50
metros cúbicos de espaço e de 120 horas de tempo de processamento. Uma tina ocupa 5m3
de espaço. O tempo de processamento de uma tina de vinho Reserva é de 15 horas,
enquanto que o tempo de processamento do vinho de Mesa é de 8 horas. A procura para
cada tipo de vinho está limitada a 7 tinas. O lucro de cada tina de vinho Reserva é de 9000
e o lucro de cada tina de vinho de Mesa é de 5000. A empresa pretende determinar as
quantidades de cada tipo de vinho a produzir. Formule o problema linear correspondente.
24.
(Época de Recurso 2002/2003)
A firma Motores Recreativos produz carrinhos de golfe e carrinhos para a neve nas
suas três fábricas. A fábrica A produz diariamente 40 carrinhos para golfe e 35 carrinhos
para a neve. A fábrica B apenas produz carrinhos para golfe – 65 unidades por dia. A
fábrica C apenas produz carrinhos para a neve – 53 unidades por dia. Os custos de
funcionamento diário das três fábricas A, B e C são, respectivamente, iguais a 210.000,
190.000 e 182.000. Quantos dias (incluindo sábados e domingos) deverá operar cada
fábrica no mês de Setembro para satisfazer um programa de produção de 1500 carrinhos
de golfe e 1100 carrinhos para a neve a um custo mínimo?
Formule o problema linear correspondente.
25.
(Época de Recurso 2003)
Uma fábrica produz três produtos distintos. Para produzir uma unidade de produto
A são necessários 5Kg de matéria-prima e são produzidas 8 gramas de um resíduo
poluente. Cada unidade de produto B necessita de 12Kg de matéria-prima e produz 6
gramas de resíduo. Uma unidade do produto C necessita de 7Kg de matéria-prima e
produz 7 gramas de resíduo. A fábrica dispõe de 3 toneladas de matéria prima e tem de
satisfazer uma encomendas de 80 unidades do produto A, 50 unidades do produto B e 60
unidades do produto C. Formule o problema de modo a minimizar a produção de resíduo
poluente.
26.
(Época de Recurso 2004)
Uma construtora possui um terreno de 9900m2 onde pretende construir um
conjunto de moradias. As moradias a construir são de três tipos (1, 2 ou 3), cada uma das
quais ocupa 170m2, 120m2 e 80m2, respectivamente. Os custos de construção (em milhares
de ) são de 150, 100 e 75, respectivamente para cada moradia do tipo 1, 2 ou 3. O
orçamento disponível é de 5 milhões de . A empresa sabe que o projecto de urbanização
será aprovado se e só se: a área ocupada pelas moradias dos tipos 1 e 2 não for superior a
5100m2; forem construídas pelo menos 20 moradias do tipo 3; forem reservados pelo
menos 2000m2 para espaços verdes.
Supondo que toda a área não aproveitada para construção é destinada a espaços
verdes, formule em Programação Linear o problema que maximiza a área verde.
27.
(Trabalho de avaliação nº1 2003/2004)
Uma instituição bancária pretende, através de um “spot” televisivo, atingir mulheres
e homens de classe média-alta.
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
6
Para tal, poderá comprar “tempo de antena” aos dois canais generalistas mais vistos
por esse estrato social, durante o intervalo dos respectivos telejornais da noite. A referida
instituição não poderá anunciar mais do que um “spot” por dia em cada um dos canais.
As audiências diárias (relativamente ao público alvo) das duas estações televisivas
no horário mencionado e os custos associados são dados na seguinte tabela:
sique
érre-tê-pê
mulheres
(milhares de pessoas)
400
275
homens
(milhares de pessoas)
300
350
custo
( por “spot”)
9000
8500
Durante o próximo mês de Novembro, existem 200 mil euros disponíveis para fins
publicitários e, para que a campanha tenha o efeito desejado, pretende-se que o anúncio
seja visto por pelo menos 7 milhões de mulheres e 6 milhões de homens da referida classe.
Assuma que, em cada um dos canais, há telejornal todos os dias do mês.
Por forma a minimizar os custos da campanha publicitária, formule o problema
exposto em Programação Linear.
28.
(Frequência 2004)
Uma editora discográfica pretende aproveitar a época natalícia para lançar no
mercado um novo álbum do reconhecido cantor José Carreteras, bem como um novo
trabalho de Plácido Sábado.
O novo disco de qualquer deles compreende temas individuais do próprio cantor,
podendo também incluir duetos gravados por ambos (em acções de beneficiência).
Para isso, a editora terá que comprar os respectivos direitos de autor, cujos custos
são encontrados na seguinte tabela:
Milhares de por tema
Temas disponíveis
José Carreteras
60
13
Plácido Sábado
50
15
Duetos
0
4
Qualquer dueto pode ser usado nos discos dos dois cantores.
O disco de José Carreteras terá que ter entre 12 e 16 músicas, enquanto que o de
Plácido Sábado deverá incluir 13 a 17 temas.
O orçamento total da empresa é de 1,3 milhões de euros.
Apesar dos temas gravados em conjunto, é conhecida a forte rivalidade que existe
entre os cantores. Assim, as quantias gastas com cada disco deverão ser o mais
aproximadas possível.
Formule este problema em Programação Linear.
29.
(Mini-teste nº1, 2004/2005)
Uma empresa gestora de capitais seleccionou quatro oportunidades de negócio.
Para os investimentos efectuados em cada um desses negócios, a empresa avaliou os
respectivos lucros esperados (l.e.) e lucros no pior caso (l.p.c.), cujos valores se encontram
na tabela seguinte:
negócios
1
2
3
4
l.e. l.p.c.
13% 6%
8%
8%
12% 10%
14% 9%
Formule em Programação Linear o problema que maximiza o lucro esperado da
empresa, sabendo que: a empresa dispõe de 1 milhão de euros; no mínimo, o lucro obtido
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
7
no pior caso deve ser 8% do investimento total realizado; a quantia investida num único
negócio não deve exceder 40% do montante total investido.
30.
O Sr. Motley Fol pretende investir 10000. Para isso, identificou seis opções de
investimento, cada qual com seu nível de retorno esperado e de risco, conforme a tabela :
Fundo
Preço (euros/título)
Retorno esperado (%)
Categoria do risco
A
20
30
Alto
B
45
20
Alto
C
60
15
Alto
D
24
12
Médio
E
34
10
Médio
F
8
7
Baixo
Dada a sua apetência ao risco, o Sr. Motley Fol rege-se pelos princípios:
• A quantia total investida em fundos de alto risco deve estar compreendida entre
60% e 75% do investimento total;
• A quantia total investida em fundos de médio risco deve estar compreendida
entre 10% e 20% do investimento total;
• A quantia investida em fundos de baixo risco deve ser pelo menos 15% do
investimento total;
• A quantia investida em fundos de alto risco deve respeitar a seguinte relação: o
fundo B deve ser o metade do fundo A, e o fundo C deve ser o dobro do fundo A;
• A quantia investida em fundos de médio risco deve respeitar a seguinte relação: o
fundo E deve ser o triplo do fundo D;
Formule o problema de Programação Linear que optimiza o investimento do Sr.
Motley Fol.
31.
Determinado investidor dispõe de um montante que pretende investir em produtos
financeiros, tendo à sua disposição: Obrigações (1), Títulos Dívida Pública (2), Dep.
Bancários (3) e Acções (4). Os rendimentos anuais obtidos através de cada uma das
hipóteses anteriores foram no último ano de 7, 6, 5.5 e 13%, respectivamente. O grau de
risco, medido numa escala de 1 a 10, foi durante o último ano de 5, 1, 1.5 e 8,
respectivamente.
• O investidor não aceita um rendimento anual inferior a 9.5% do valor disponível
para investir.
• Por razões de segurança o investimento em acções não deverá ser superior a 20%
do total.
• Pelo menos 40% do investimento deverá ser feito em Títulos Dívida Pública e
Obrigações.
• Restrições legais impedem um só investidor de adquirir Títulos Dívida Pública
num montante superior a 50 milhares de euros.
Formule o problema em Programação Linear (sugestão: converta o risco para uma
escala percentual 0 - 100%), de forma a:
a) Maximizar o rendimento.
b) Minimizar o risco.
32.
(Mini-Teste nº1, 2005/2006, EC)
A empresa Massas Finas & Grossas Lda produz dois tipos de betão: B1 e B2. A
produção de uma tonelada de B1 consome 200kg de cimento, 400kg de areia e 400 litros de
água. No caso de B2 são consumidos 100kg de cimento, 300kg de areia e 600 litros de
água. A empresa dispõe de 10 toneladas de cimento, 25 toneladas de areia e 500000 litros
de água. Sabendo que cada tonelada de B1 e B2 é vendida a 400 e 300 respectivamente, e
que, devido à seca prolongada, toda a água não utilizada é roubada pelas populações
vizinhas (cada litro custa 0.5), determine um programa linear que maximize a receita.
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
8
33.
(Mini-Teste nº1, 2005/2006, ME+MI+MA+EPGI+EI)
A empresa Nucleogal SA dispõe de duas fábricas para produz dois tipos de
combustíveis nucleares, pastilha A e pastilha B, utilizando como matéria-prima o urânio.
Na fábrica Um, a transformação de cada kg de urânio resulta em 4 pastilhas A e 7 pastilhas
B, implicando um custo de 6 em seguros de saúde. Na fábrica Dois, de cada kg de urânio
obtém-se 6 pastilhas A e 5 pastilhas B, implicando um custo de 8 em seguros de saúde.
Existem encomendas de 800 unidades de pastilhas A e 500 unidades de pastilhas B e
2500kg de urânio. Sabendo que por cada pastilha A não vendida a Nucleogal SA tem um
custo de 2 de armazenamento, formule o problema nos termos da programação linear de
forma a minimizar o custo total.
34.
(Mini-Teste nº1, 2005/2006, G+E)
Uma empresa gestora de capitais pretende fazer investimentos em 3 tipos de
aplicações, sendo que cada uma requer um montante mínimo de investimento. Conhecemse os lucros esperados (mínimo e máximo) associados a cada aplicação, conforme os dados
da seguinte tabela:
Aplicação
1
2
3
Montante mínimo
(milhares de )
100
250
200
Lucro
mínimo (%)
14
9
11
Lucro
máximo (%)
20
10
15
A empresa possui um orçamento de 10 milhões de euros e só considera a hipótese
de efectuar um plano de investimentos que garanta um lucro mínimo de 12%.
Adicionalmente, imposições do mercado de capitais obrigam que o investimento na
aplicação 2 seja não inferior a 20% do investimento na aplicação 1.
Formule, em Programação Linear, o problema que maximize o lucro máximo
esperado.
__________________________________
35. Uma empresa possui 3 fábricas onde existe capacidade de produção em excesso.
Todas as fábricas estão aptas a produzir um novo produto e a direcção decidiu usar desta
forma alguma da capacidade disponível. Este novo produto pode ser fabricado em 3
tamanhos : grande (G), médio (M) e pequeno (P). Estes dão um lucro unitário de 42, 36 e
30 u.m., respectivamente.
As fábricas 1, 2 e 3 têm capacidade em excesso para produzir diariamente 750, 900
e 450 unidades deste produto, respectivamente, independentemente dos tamanhos ou
combinações de tamanhos. O espaço de armazenamento disponível impõe uma limitação
na produção do novo produto. As fábricas 1, 2 e 3 têm, respectivamente, 13000, 12000 e
5000 m2 de espaço de armazenamento disponível por um dia de produção. Cada unidade
do novo produto de tamanhos G, M e P necessita de 20, 15 e 12 m2, respectivamente.
As previsões de vendas indicam que podem ser vendidas diariamente 900, 1 200 e
750 unidades de tamanhos G, M e P, respectivamente. Para manter uma força de trabalho
uniforme nas fábricas e dispor de alguma flexibilidade, a direcção decidiu que as fábricas
devem usar a mesma percentagem da sua capacidade em excesso para produzir o novo
produto. A direcção pretende saber quanto, de cada tamanho, deve ser produzido em cada
fábrica, de modo a maximizar o lucro total.
Construa um modelo matemático em Programação Linear para o problema.
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
9
36. Um industrial têxtil pode fabricar 2 tipos de tecido (A e B), para o que necessita de 4
tipos de fio (1, 2, 3 e 4). Assim, para fabricar 1 unidade de medida (u.m.) do tecido A, são
necessários 4 kg de fio 1, 3 kg de fio 2, 6 kg de fio 3 e 1 kg de fio 4. Para fabricar 1 u.m. de
tecido B, são necessários 2 kg de fio 1, 8 kg de fio 2, 1 kg de fio 3 e 3 kg de fio 4. O custo
(em unidades monetárias u.m.) por kg de fio, é dado na tabela seguinte:
Fio
Custo
1
10
2
12
3
11
4
13
O preço de venda por unidade de medida de tecido é de 250 para o tecido A e de
300 para o tecido B.
Sabendo que o industrial só dispõe de 200.000 para investir na compra de fio e
que o fornecedor de fio só pode garantir a entrega de 8 000 kg do fio 2, que quantidades
devem ser fabricadas de tecido A e de tecido B, de forma a maximizar o quantitativo
recebido pela venda (supõe-se garantida a venda total da produção) ? Formule (não resolva)
o problema como um de PL.
37.
(Época Especial 2003)
Uma empresa de produtos alimentares pretende produzir um certo preparado pela
mistura de três substâncias, A, B e C, devendo decidir acerca da sua composição de forma
que o preparado satisfaça alguns requisitos nutritivos. Assim, não deverá ter menos de 1800
cal/kg, contendo um mínimo de 7% de gorduras e não mais de 0,5% de açúcar. As três
substâncias têm as seguintes características:
cal/kg
gordura (%)
açúcar (%)
Custo por kg ()
A
1200
4
0,5
0,07
B
2000
8
0,6
0,15
C
2500
15
0,4
0,3
Formule o problema linear que optimiza a produção do preparado.
38.
(Época Normal 2003)
Uma fundição pretende produzir um nova liga metálica, contendo 40% de Estanho,
35% de Zinco e 25% de Chumbo, a partir de várias ligas com as seguintes propriedades:
Estanho (%)
Zinco (%)
Chumbo (%)
Custo (/kg)
1
60
10
30
22
2
25
15
60
20
3
45
45
10
25
4
20
50
30
24
5
50
40
10
27
O objectivo é determinar as quantidades das cinco ligas metálicas que devem ser
utilizadas na elaboração da nova liga, com custo mínimo.
Formule o problema em Programação Linear.
39.
(Frequência 2003)
Uma companhia petrolífera tem ao seu dispor dois tipos de crude – A e B – cujo
custo é de 31 e 29 por barril, respectivamente. No quadro seguinte são apresentados o
número de barris de gasolina, querosene e de jet-fuel que são produzidos por cada barril de
crude:
Gasolina
Querosene
Crude A
0,4
0,2
Crude B
0,4
0,4
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
Jet-fuel
0,4
0,2
10
Durante o processo de refinação perdem-se 5% e 8% do crude de tipo A e B,
respectivamente. A fim de satisfazer as encomendas, é necessário produzir 1 milhão de
barris de gasolina, 400.000 barris de querosene e 250.000 barris de jet-fuel. A companhia
pretende determinar as quantidades de cada tipo de crude a adquirir de forma a minimizar
os custos.
Formule o problema linear correspondente.
40.
(Mini-teste nº1, versão não publicada, 2004/2005)
Um intermediário compra e vende milho como modo de vida. No final deste ano
terá no seu armazém 50 toneladas de milho e 1000 na sua conta bancária. No primeiro dia
de cada mês do próximo ano poderá comprar milho aos seguintes preços por tonelada:
Janeiro, 300; Fevereiro, 350; Março, 400; e Abril, 500. No último dia de cada mês, o
intermediário poderá vender milho aos seguintes preços por tonelada: Janeiro, 250;
Fevereiro, 400; Março, 350; e Abril, 550. O milho é armazenado num celeiro com
capacidade de 100 toneladas. Formule, em Programação Linear, o problema que maximiza
o dinheiro que o intermediário terá disponível no fim de Abril.
41.
(Mini-teste nº1, 2006/2007)
Uma empresa fabrica três produtos em duas máquinas (A e B). Na tabela seguinte
encontram-se os dados relativos ao tempo (em minutos) que cada unidade de cada produto
demora a ser fabricado, ao lucro unitário de cada produto (em ) e à área ocupada em
armazém por cada produto (em m2):
máquina
produto A
B lucro área
1
10 27
10
0,1
2
12
12 19
0,15
3
17
13 33
0,5
O produto 1 tem que ser fabricado por ambas as máquinas, pelo que cada unidade
deste produto demora 37 minutos a ser fabricado (10 na máquina A e 27 na máquina B). Já
os produtos 2 e 3 podem ser produzidos por qualquer máquina.
O armazém da empresa tem uma área de 50m2.
Estudos de mercado indicam que, com uma margem de ±5%, o produto 2 deve ser
produzido no dobro da quantidade que o produto 3.
Numa semana de 35 horas, devido a trabalhos de manutenção, as máquinas A e B
estão inoperacionais 5% e 7% do tempo, respectivamente.
Formule em Programação Linear o problema que maximiza o lucro da produção
semanal.
42.
(Frequência, 2006/2007)
Um aluno da UBI decidiu fazer 3 exames na 2ª chamada das disciplinas A, B e C.
Decidiu também que só estuda até dois dias antes do primeiro dos mesmos. Até essa data,
descontando o tempo perdido com alimentação, playstation e pouco mais, o aluno tem 100
horas para estudar. As suas prioridades são:
• O tempo dispendido a estudar a disciplina A deve ser superior em 20% do tempo
dispendido com o estudo da disciplina B;
• A soma do tempo dispendido com o estudo das disciplinas A e B deve ser
sensivelmente igual ao tempo gasto no estudo da disciplina C, com uma margem de erro de
10%. .
A satisfação pessoal que o aluno obtém por cada hora dispendida a estudar as
disciplinas A, B e C é de, respectivamente, 3, 4 e 5 (valores em chocolates por hora).
Formule em Programação Linear o problema que maximiza a satisfação pessoal do aluno
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
11
sujeito às restrições mencionadas.
43.
(Exame de 1ªchamada, 2006/2007)
O já conhecido aluno da UBI decidiu fazer apenas dois dos três exames (das
disciplinas A, B e C) que ainda pode fazer na 2ª chamada. Até uma determinada data,
descontando o tempo perdido com alimentação e pouco mais (a playstation foi interdita), o
aluno tem 75 horas para estudar. As suas prioridades são:
• Se optar por estudar a disciplina A, não quer estudar mais que 30 horas;
• Se optar por estudar a disciplina B, tem que estudar um mínimo de 25 horas;
• O tempo dispendido com o estudo das disciplinas A e B deve ser sensivelmente o
mesmo, com uma margem de 10%, que o tempo gasto a estudar a disciplina C;
• Só se estudar a disciplina A é que estará em condições para estudar B, ou seja, se
não estudar A não poderá estudar B.
A satisfação pessoal que o aluno obtém por cada hora dispendida a estudar as
disciplinas A, B e C é de, respectivamente, 3, 4 e 5 (valores em chocolates por hora).
O aluno pretende saber que disciplinas deve estudar e durante quanto tempo deve
estudar cada uma dessas (naturalmente,à disciplina que ele não estudar não pretende
dedicar tempo). Formule em Programação Linear o problema que maximiza a satisfação
pessoal do aluno sujeito às restrições mencionadas.
__________________________________
44. Um estudante que toma as suas refeições diárias numa cantina universitária tem à sua
disposição, num determinado dia, 5 menus completos e variados (3 para o almoço e 2 para
o jantar) cujos preços (em ) são apresentados na tabela seguinte:
Menu 1
1,25
Almoço
Menu 2
1,5
Jantar
Menu 3
1,75
Menu 1
1
Menu 2
1,75
Após ter determinado o total de substâncias nutritivas (proteínas e vitaminas)
contido em cada um desses menus, obteve os valores seguintes:
Proteínas (gr)
Vitaminas (mg)
Menu 1
16
20
Almoço
Menu 2
20
15
Menu 3
25
12
Jantar
Menu 1
Menu 2
15
25
10
5
Por outro lado, os requerimentos totais (almoço e jantar) de proteínas e vitaminas
exigidos pelo estudante para a sua alimentação nesse dia são respectivamente 35g e 0.02g.
Qual o esquema de alimentação que o estudante deve adoptar de forma a obter um
custo mínimo de alimentação para esse dia específico ? (isto é, qual o menu que ele deve
escolher para o almoço e qual deve escolher para o jantar ?) Formule este problema em
Programação Linear.
45.
A cadeia de lojas Coronel Tijelada vai lançar um novo produto no mercado, tendo
que, para o efeito, abrir uma nova linha de produção. Diariamente, os trabalhadores da
empresa serão obrigados a fazer 2 turnos de 5 horas cada. Os turnos e as respectivas
quantidades necessárias de trabalhadores encontram-se na seguinte tabela:
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
12
turno 1
6h – 11h
15
turno 2
11h – 16h
5
turno 3
16h – 21h
12
turno 4
21h – 2h
6
Os trabalhadores que laborem 2 turnos consecutivos recebem 12 euros por hora, enquanto
que os que efectuarem turnos não consecutivamente ganham 18 euros por hora.
Formule o problema em Programação Linear que minimize o custo diário de mão de obra.
46.
A Sr.ª D. Ofélia tem duas netas, a Cátia e a Vanessa, a cada uma das quais pretende
oferecer uma carteiras de acções, podendo gastar no total 1.500.000 euros. Um analista
económico aconselhou à avó 3 títulos para possível investimento: B.C.P. (1), Sonae (2) e
P.T. (3). O custo unitário de cada um destes títulos é de 2, 3.5 e 3.25 euros,
respectivamente. É sabido que a Cátia não deseja mais do que 200.000 euros em acções do
B.C.P, enquanto que a Vanessa quer pelo menos 600.000 euros em títulos da Sonae.
a) A Sr.ª D. Ofélia não quer prejudicar nenhuma das netas, pelo que pretende que os
valores das carteiras sejam o mais aproximados possível. Formule o problema em
Programação Linear.
b) Escreva matematicamente a restrição que garanta a pretensão da avó em doar a
instituições de caridade pelo menos um terço do montante total não investido.
47.
Determinada empresa comercializa um produto cujo valor de encomendas (em
toneladas) nos próximos três meses é de:
Mês 1
100 t
Mês 2
120 t
Mês 3
150 t
O produto pode ser produzido por dois processos (I e II). Cada tonelada de
produto requer dois tipos de matéria-prima e mão-de-obra, conforme os valores
apresentados na tabela seguinte:
matéria-prima 1
matéria-prima 2
mão-de-obra
custo unitário
Processo I
10
15
2.5
500
Processo II
12
10
2.8
600
disponibilidade
no primeiro mês
2500
3000
600
Dado o período de franca expansão que a empresa atravessa, é possível aumentar as
disponibilidades em 20% de um mês para o mês seguinte.
Sabe-se que o produto não pode ser armazenado.
Pretende-se ainda que, em cada mês, a diferença entre as quantidades produzidas
pelos dois processos não seja superior a 10% do total produzido.
Formule em Programação Linear o problema que minimiza os custos.
48.
Uma empresa de papel tem máquinas capazes de produzir rolos de papel com uma
largura standard de 2 metros. Estes rolos são depois cortados em rolos com uma largura
menor, em função de encomendas previamente estabelecidas.
Num dado momento, existe uma encomenda de 500 rolos de 45cm de largura, 300
rolos com 24cm de largura e 200 rolos com 60cm de largura. Como é fácil constatar, há 12
possíveis formas de cortar um rolo de 2 metros para obter rolos com 45cm, 24cm e/ou
60cm:
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
13
nº de rolos com 45cm
nº de rolos com 24cm
nº de rolos com 60cm
desperdício (cm)
1
0
0
3
20
2
0
3
2
8
3
1
1
2
11
Padrões de corte
4
5
6
7
8
0
1
2
3
0
5
3
2
0
8
1
1
1
1
0
20 23 2
5
8
9
1
6
0
11
10
2
4
0
14
11
3
2
0
17
12
4
0
0
20
Exemplo: o padrão de corte 4 estabelece que um rolo de 2 metros é cortado em 5 rolos de
24cm e 1 rolo de 60cm, sendo o desperdício de 20cm.
Pretende-se estabelecer um plano de corte de rolos de 2 metros por forma a
satisfazer a encomenda minimizando o nº de rolos de 2 metros utilizado.
a) Formule o problema em Programação Linear.
b) Como alteraria a formulação anterior se o objectivo fosse minimizar o desperdício?
49.
(Época Especial 2004)
Uma fábrica de móveis dispõe em armazém de placas de MDF com 41dm de
comprimento. Para produzir uma nova linha de móveis a fábrica terá que cortar estas
placas em peças com 18, 15, 10 e 8dm de comprimento, cujas quantidades exigidas pelo seu
cliente são de 1000, 1800, 2700 e 6500, respectivamente. Formule, em Programação Linear,
o problema que minimiza a quantidade desperdiçada das placas de MDF.
50.
A Risco Calculado, uma empresa gestora de capitais, está a considerar cinco
oportunidades diferentes de investimento. A empresa pode comprar qualquer fracção de
cada negócio, podendo tomar as suas decisões em duas datas diferentes – data 0 e data 1.
Na data presente (data 0) existem 40 milhões de euros. Daqui a seis meses (data 1) a
empresa poderá completar investimentos nos mesmos 5 negócios, quando estarão
disponíveis mais 25 milhões de euros de novo capital e 7% do montante entretanto
investido na data 0.
Os montantes requeridos pelos diferentes negócios em cada data e o lucro esperado
de cada um dos mesmos são dados na seguinte tabela (valores em milhões de euros):
1
Data 0 11
Data 1 3
lucro 13
2
53
6
16
3
5
5
16
4
5
1
14
5
29
34
39
Formule o problema em Programação Linear por forma a maximizar o lucro da
Risco Calculado.
51.
A McRonald’s pretende determinar a localização de futuros restaurantes num
distrito com 6 centros populacionais importantes (Ci, i=1,...,6). A empresa pretende reduzir
ao mínimo o nº de restaurantes a abrir, devido aos elevados custos de investimento
necessário. No entanto, terá que se garantir que todos os centros populacionais ficarão, no
máximo, a 20 minutos de um centro populacional com McRonald’s. O quadro seguinte
apresenta os tempos estimados de deslocação entre qualquer par de centros populacionais:
C1
C2
C3
C4
C5
C6
C1
0
15
25
34
36
24
C2
15
0
30
40
27
14
C3
25
30
0
20
35
23
C4
34
40
20
0
18
29
C5
36
27
35
18
0
19
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
C6
24
14
23
29
19
0
14
Apresente o modelo em Programação Linear que minimiza o nº de centros populacionais
onde são construídos novos McRonald’s.
52.
(Época Normal 2004)
Uma empresa produz um certo artigo para venda. Os custos de produção (em )
em cada um dos 4 trimestres do corrente ano são 14, 16, 15 e 17 por unidade, e o preço
unitário de venda do artigo é de 25 (não varia ao longo do ano).
As capacidades de produção nos mesmos períodos são de 420, 380, 180 e 200
unidades e as encomendas são de 270, 200, 200 e 410 unidades.
As quantidades produzidas num período e que não forem vendidas no mesmo
período podem ser armazenadas para os períodos seguintes ao custo de 1 por unidade e
por período. No início do 1º trimestre há 20 unidades de produto em armazém e, no final
do 4º trimestre, este deve ficar vazio.
Formule em Programação Linear o problema que maximiza o lucro da empresa.
53.
(Época de Recurso 2004)
O Francisco dispõe de 2200 para investir nos próximos 5 anos. No princípio de
cada ano, ele pode subscrever depósitos a prazo de um ou de dois anos. Um banco (dos
menos somíticos do mercado) paga-lhe 4% de juros pelos depósitos anuais e 9% (no total)
de juros pelos depósitos a dois anos. Se o Francisco reinvestir o seu dinheiro anualmente,
formule, em Programação Linear, o problema que maximiza o dinheiro que poderá
movimentar ao fim de 5 anos.
54.
(Exame Normal 2004/2005)
Uma empresa fabrica três produtos (A, B e C), que vende (cada unidade) a 10, 56 e
100, respectivamente. Sabe-se que:
• Uma unidade de A requer 1 hora de mão-de-obra.
• Uma unidade de B requer 2 horas de mão-de-obra e 2 unidades de A.
• Uma unidade de C requer 3 horas de mão-de-obra e 1 unidades de B.
• A mão-de-obra está limitada a 40 horas.
Sabe-se ainda que:
• Qualquer unidade de A usada no fabrico de B não pode ser vendida.
• Qualquer unidade de B usada no fabrico de C também não pode ser vendida.
Formule em Programação Linear o problema que maximiza o lucro da empresa.
55.
Um gabinete de advogados tem quatro casos (fraude, corrupção, furto e estupro)
que quer atribuir a quatro advogados (A, B, C e D). Cada advogado deve tratar apenas de
um caso, e tem competências específicas em cada tipo de caso, indicadas sob a forma de
índice de proficiência na tabela:
Advogado
A
B
C
D
Caso
Fraude
15
18
8
10
Corrupção
14
15
8
12
Furto
15
16
16
14
Estupro
16
17
16
15
Formule o problema de optimização da distribuição dos casos pelos advogados em
Programação Linear.
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
15
56.
(Frequência 2005/2006, ME+MI+MA+EPGI+EI+EC)
Numa empresa existem n máquinas independentes que fabricam um dado tipo de
produto. Por dia são necessárias Q unidades desse produto, que pode ser produzido em
qualquer uma das máquinas. No entanto, para rentabilizar o tempo de utilização de cada
máquina j, se esta for posta em funcionamento existe uma quantidade mínima de produto,
mj, que deve ser produzido por essa máquina. De igual modo, qualquer máquina tem um
limite de capacidade de produção, Mj . Ao colocar em funcionamento a máquina j é
necessário pagar um custo, kj, associado à sua manutenção e por cada unidade produzida
na máquina j existe um custo de produção cj. Formule, em Programação Linear, o problema
que minimiza o custo total de produção.
57.
(Frequência 2005/2006, G+E)
Um empresário dispõe de três fundos de investimento, FI1, FI2 e FI3, onde pode
aplicar até 1 milhão de . As cotações de cada unidade de participação (UP) desses fundos
são de 10, 15 e 18, respectivamente.
Caso opte por investir no fundo FIj , existe um número mínimo de UP que terá que
adquirir, mj, como também um número máximo, Mj , com j=1, 2, 3. Se o empresário
investir no fundo FIj, terá um custo de subscrição de kj . Por cada UP de FIj adquirida,
terá ainda que pagar uma comissão de cj .
Formule em Programação Linear o problema que minimiza o custo de subscrição
dos fundos de investimento e as comissões associadas.
58. Um estudante tem de fazer exame em 3 disciplinas - A, B e C - tendo 3 dias para
estudar. Ele pensa que o melhor é dedicar um dia inteiro ao estudo duma mesma disciplina,
pelo que pode gastar no estudo de qualquer disciplina desde 0 a 3 dias. A estimativa das
notas que pode obter consoante o estudo é a seguinte:
Dias de
estudo
0
1
2
3
Disciplinas
A B C
0 4 0
4 4 4
4 12 12
12 16 12
O aluno pretende determinar como deve planear o estudo de modo a maximizar a
classificação total.
59. Três navios carregados de ferro pretendem descarregar e há 4 docas onde o podem
fazer. Devido às diferentes capacidades dos navios e das docas o tempo (em dias) de
descarga varia conforme os dados da seguinte tabela:
Doca
1
2
3
4
1
7
13
12
14
Navio
2 3
15 21
10 15
16 28
8 5
Sabendo que cada doca é utilizada no máximo por um navio:
a) Formule em Programação Linear o problema que minimiza o tempo total gasto
na descarga dos 3 navios.
b) Sabendo que o proprietário dos três navios pretende dispor da sua frota o mais
breve possível, formule o problema em Programação Linear.
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
16
60. É necessário dispor de uma máquina para executar uma certa tarefa durante os
próximos 4 anos, após os quais a tarefa e a máquina deixam de ser necessárias. O custo de
aquisição da máquina nos próximos 4 anos é: 25000 (agora), 30000 (daqui a um ano),
38000 (daqui a 2 anos) e 47000 (daqui a 3 anos).
Após ser utilizada, o valor de venda da máquina depende do número de anos que
serviu: 15000, 10000, 5000 e 1000 por 1, 2, 3 e 4 anos de serviço, respectivamente.
O custo anual de manutenção depende do tempo de utilização: 3000 (nova), 5000
(1 ano), 8000 (2 anos) e 15000 (3 anos).
Pretende-se determinar a política óptima de compra, venda e utilização das
máquinas.
61. Considere a rede seguinte onde se pretende transportar crude desde um poço de
petróleo (nodo 1) até à refinaria (nodo 5) através de oleodutos (arcos) com calibres (cij)
indicados junto a cada arco:
2
3
2
1
3
1
6
2
4
5
4
4
5
Entende-se por calibre de um oleoduto a quantidade máxima de crude, em Kl, que pode
fluir através do mesmo por hora. Formule o problema que maximiza a quantidade de crude
que pode chegar à refinaria por hora.
62. Considere o grafo seguinte onde se pretende transportar contentores existentes no
nodo 1, através da rede, até ao nodo 9.
2
3
9
1
4
6
5
7
8
Cada contentor será transportado por um camião que percorre um dos caminhos de 1 a 9
existentes na rede. Foi aberto um concurso para a realização do transporte e concorreram
várias empresas, cada uma com um camião. Pretende-se transportar os contentores o mais
rapidamente possível de 1 para 9. Como tal, serão aceites transportes realizados por várias
empresas. Devido às rivalidades entre estas, pretende-se estabelecer percursos diferentes
para cada uma das empresas de forma a garantir que camiões de diferentes empresas não se
encontram na estrada (nem em troços de estrada nem em cruzamentos). Assume-se que o
tempo de 1 a 9 em qualquer percurso é o mesmo.
Formule o problema que maximiza o número de empresas que é possível aceitar
para a realização do transporte nas condições acima descritas.
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
17
63. Suponha que está interessado em seleccionar investimentos {1,...,7}. Modele as
seguintes restrições:
a) Não pode investir em todos;
b) Tem que investir em pelo menos um;
c) O investimento 1 não pode ser seleccionado se o investimento 3 for escolhido;
d) O investimento 4 pode ser escolhido só se o investimento 2 for seleccionado;
e) Tem que escolher ou ambos os investimentos 1 e 5 ou nenhum;
f) Tem que seleccionar ou pelo menos um dos investimentos 1, 2, 3, ou pelo menos
dois dos investimentos 2,4,5,6.
64. Numa empresa existem n máquinas independentes que fabricam um dado tipo de
produto. Por dia são necessárias Q unidades desse produto, que pode ser produzido em
qualquer uma das máquinas. No entanto, para rentabilizar o tempo de utilização de cada
máquina j, se esta for posta em funcionamento existe uma quantidade mínima de produto,
mj, que deve ser produzido por essa máquina. De igual modo, qualquer máquina tem um
limite de capacidade de produção, Mj. Ao colocar em funcionamento a máquina j é
necessário pagar um custo, kj, associado à sua manutenção e por cada unidade produzida
na máquina j existe um custo de produção cj.
65. A delegação do Ministério da Saúde de um dado concelho pretende instalar k postos de
saúde na sua área por forma a servir toda a população do concelho. Para isso, poderá
construir em qualquer uma das m freguesias que constituem o concelho. Se a delegação
decidir construir um posto numa dada freguesia j, terá que adquirir o terreno por um custo
aj e, além disso, terá de pagar fj pela sua manutenção.
As m freguesias devem ser servidas na totalidade e cada uma só pode ser servida por
um único posto. Se a freguesia i for servida por um posto de saúde na freguesia em j, a
delegação de saúde terá de pagar um custo cij. O objectivo da delegação é então servir todas
as freguesias com custo mínimo.
a) Formule o problema apresentado;
b) Suponha agora que cada freguesia tem uma determinada população de pi habitantes,
i=1,...,m, e que se for instalado um posto em j apenas Dj habitantes poderão ser servidos
por esse posto. Como alteraria a formulação obtida em a)?
66. A Câmara Municipal de uma dada cidade prevê instalar brevemente em certos pontos
da cidade dois novos tipos de serviços. Em cada um dos n possíveis locais de instalação, se
optar pela instalação, poderá instalar um ou ambos os tipos de serviço. A capacidade
máxima de cada serviço estará condicionada ao local de instalação e será Q1j e Q2j (j=1,...,n)
respectivamente.
A urgência em criar estes serviços surgiu pela sua crescente necessidade. Assim, um
conjunto de m potenciais clientes expressou quantitativamente as suas necessidades p1i e p2i,
(i=1,...,m), respectivamente. Assume-se que todos os clientes necessitam de ambos os tipos
de serviço.
A Câmara está a estudar a forma de resolver a situação com custo mínimo, visto
existirem custos de instalação dos serviços consoante o local onde são instalados: fkj, k=1,2
e j=1,...,n. Além disso, a Câmara suportará também os custos de deslocação que dependem
directamente da distância entre o cliente e o local que o irá servir: dij, i=1,...,m e j=1,...,n.
a) Formule o problema apresentado;
b) Como alteraria a formulação no caso em que, se um dado cliente i for servido pelo
mesmo local no que diz respeito aos dois tipos de serviço, apenas será contabilizado uma
vez o custo de deslocação dij?
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
18
Soluções dos exercícios envolvendo resolução gráfica:
1.
x*=(8, 5/3); Z*=380
2.
x*=(2,3); Z*=14
3.
Não existe solução óptima, i.e., a solução óptima é ilimitada; não existe um valor máximo finito para
a função objectivo.
4.
x*=(2,5); Z*= - 45
5.
Soluções óptimas alternativas: todos os pontos do segmento de recta (sobre a recta associada à
restrição 20x1 +36x236000) que une os pontos (0,1000) a (1028.57; 428.57) são soluções óptimas, com
Z*=18000. Ou seja, qualquer ponto da forma (x1,x2)=(0,1000)+(1-)(1028,57;428,57), com [0,1], é
solução óptima com Z*=18000.
6.
O problema é impossível: a região admissível é vazia.
7.
x*=(0,2); Z*=4
8.
x*=(5,5); Z*= - 20
9.
x*=(2,6); Z*=20
10.b)
x*=(-8/7, 18/7); Z*=80/7
13.b)
x*=(6, 12); Z*=1170 u.m.
14.
Soluções óptimas alternativas: todos os pontos do segmento de recta (sobre a recta associada à
restrição 4x1 +5x232) que une os pontos (0,32/5) a (3,4) são soluções óptimas, com Z*=32000 u.m. Ou seja,
qualquer ponto da forma (x1,x2)=(0,32/5)+(1-)(3,4), com [0,1], é solução óptima com Z*=32000 u.m..
15.b)
x*=(3,4); Z*=21000u.m.
15.c)
Não, visto que a região admissível consiste em apenas um ponto.
16.
Soluções óptimas alternativas: todos os pontos do segmento de recta (sobre a recta associada à
restrição 2x1+x22000) que une os pontos (0,2000) a (400,1200) são soluções óptimas, com Z*=20000gr. Ou
seja, qualquer ponto da forma (x1,x2)=(0,2000)+(1-)(400,1200), com [0,1], é solução óptima com
Z*=20000gr.
Considerando uma solução óptima, por exemplo, x*=(0,2000), são produzidas 2000 unidades de P1
e 6000 unidades de P2, sobram 1000Kg de matéria prima e resultam 20Kg de resíduo.
17.b)
x*=(52/5, 6/5); Z*=58/5 dias.
18.a)
x*=(20000,80000); Z*=14000
18.b)
x*=(60000,40000); Z*=1800
INVESTIGAÇÃO O PERACIONAL 2008/2009 – Ficha de exercícios 1
19