Métodos de Apoio à Decisão
João Pedro PEDROSO
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade de Porto
Ano lectivo de 2014/2015
• O comprimento não pode exceder 42 cm, e a
soma do comprimento com a largura não pode
exceder 72 cm.
Aula número 1
1. Um comerciante pretende obter uma quantidade não
superior a 5 toneladas de certo produto que pode ser
encomendada a duas fábricas A e B. A fábrica A garante um lucro de 4 contos por tonelada, mas não
pode fornecer mais de 3 toneladas. A fábrica B garante um lucro de 3.5 contos por tonelada, e pode
fornecer qualquer quantidade.
• A altura tem de ser inferior ou igual à largura,
e esta não pode exceder o comprimento.
Qual será o maior volume de sementes que pode ser
enviado numa única encomenda postal que obedeça
a estes regulamentos?
Admitindo que o comerciante pretende obter o lucro
máximo, formule o seu problema em programação
matemática.
4. Uma fábrica produz dois tipos de tecido usando 3
cores diferentes de lã. Para cada metro de tecido,
são necessárias as seguintes quantidades de lã (em
gramas):
2. Uma companhia especializada no fabrico de vı́deos
produz dois tipos de aparelhos: com duas cabeças
e com quatro cabeças de leitura. A montagem dos
aparelhos de duas cabeças é efetuada na linha de
produção 1, e requer 5 componentes. Os de quatro cabeças são montados na linha 2, requerendo 6
componentes.
Lã
amarela
verde
preta
Os componentes são fornecidos por outro fabricante,
em quantidade limitada a 600 componentes por dia.
Tecido B
500
200
800
A fábrica dispõe apenas de 100 kg de lã amarela,
100 kg de lã verde e 120 kg de lã preta. O gestor desta fábrica pretende determinar como estabelecer a produção, supondo que lucra 500$00/m no
tecido A e 200$00/m no tecido B. Formule o seu
problema.
A companhia tem 160 empregados, sendo necessário
1 homem durante um dia para montar um vı́deo com
duas cabeças e 2 homens durante um dia para montar um vı́deo com quatro cabeças. Equacionados os
custos de mão de obra e material, a receita obtida é
uma função do número de vı́deos de cada tipo produzidos:
f (x, y) = 32x + 8y + xy −
Tecido A
400
500
300
5. Uma fábrica de aços tem que decidir como utilizar o
tempo da semana seguinte num moinho. O moinho
utiliza restos de aço, podendo produzir fitas ou bobinas. As fitas podem ser produzidas à razão de 200
toneladas por hora, e as bobinas à razão de 140 toneladas por hora. Os lucros obtidos são de 25 contos
por tonelada com as fitas e de 30 contos por tonelada
com as bobinas. Atendendo à carteira de encomendas, a produção máxima na semana seguinte é de
6000 toneladas para fitas e de 4000 toneladas para
bobinas.
x2
− y2
2
em que x e y são os números de vı́deos com duas
e quatro cabeças produzidos diariamente, respetivamente.
Tendo em atenção que esta companhia quer encontrar um plano de produção diária de vı́deos que maximize a receita, traduza matematicamente este problema.
Se nessa semana se dispuser de 40 horas de
produção, quantas toneladas de cada um dos produtos deverão ser produzidas de forma a maximizar
o lucro? Formule o problema.
3. Uma firma de exportação de sementes pretende satisfazer a sua carteira de encomendas. Em alguns
casos, é conveniente enviar as encomendas por correio. Os CTT exigem que as caixas utilizadas tenham formato de um paralelepı́pedo retângulo, obedecendo às seguintes regras:
6. Exercı́cio a apresentar: Considere o problema
da escolha de comida, de forma a satisfazer certas
exigências nutricionais. Os pratos disponı́veis são
os seguintes, com preços indicados em escudos:
1
1
2
3
4
5
6
7
8
Prato
Bife
Frango
Peixe
Hamburger
Macarrão
Empada
Esparguete
Peru
Preço
319
259
229
289
189
199
199
249
Este pratos fornecem as seguintes percentagens (por
prato) dos mı́nimos diários necessários em vitaminas A, C, B1, e B2:
Bife
Frango
Peixe
Hamburger
Macarrão
Empada
Esparguete
Peru
A
60
8
8
40
15
70
25
60
C
20
0
10
40
35
30
50
20
B1
10
20
15
35
15
15
25
15
B2
15
20
10
10
15
15
15
10
O problema é encontrar a combinação de pratos que
satisfaça as exigências alimentares de uma semana
(700% do mı́nimo diário) com o custo mı́nimo.
Formule-o em programação matemática.
7. Há três fábricas localizadas junto ao rio Leça (1, 2 e
3), cada uma das quais emitindo dois tipos de poluentes (1 e 2) para o rio. Se houver um processamento
dos resı́duos emitidos, a poluição no rio poderá ser
reduzida.
O processamento dos resı́duos da fábrica 1 custa 15
euro por tonelada, e cada tonelada processada reduz a quantidade de poluente 1 em 0.1 toneladas, e
a quantidade de poluente 2 em 0.45 toneladas.
Quanto ao processamento dos resı́duos da fábrica 2,
o seu custo é de 10 euro por tonelada, e cada tonelada processada reduz a quantidade de poluente 1
em 0.2 toneladas, e a quantidade de poluente 2 em
0.25 toneladas.
Para a fábrica 3, o processamento dos resı́duos custa
20 euro por tonelada, e a cada tonelada processada
corresponde uma redução da quantidade de poluente 1 de 0.4 toneladas, e da quantidade de poluente 2 de 0.3 toneladas.
O estado pretende reduzir a quantidade de poluente 1 no rio em pelo menos 30 toneladas, e a quantidade de poluente 2 em pelo menos 40 toneladas.
Formule o programa linear que permite minimizar
o custo de reduzir a poluição nos montantes desejados. Indique se as hipóteses da programação linear
se verificam neste caso.
8. Formule em programação matemática e resolva graficamente o seguinte problema:
A companhia DEG fabrica dois tipos
de computadores: portáteis e desktops.
Cada computador deverá passar por uma
linha de montagem e por um controlo de
qualidade. O perı́odo de trabalho é de oito
horas diárias, e cinco dias semanais.
Se a linha de montagem fosse completamente dedicada aos portáteis, poder-se-ia
montar até 9 computadores por dia. Com
desktops este limite é de 1 computador
por hora.
Se o controlo de qualidade fosse completamente dedicado aos portáteis, poder-se-ia
verificar 10 unidades por dia; com desktops o limite horário de verificação é de 2
computadores.
Por decisão do departamento de marketing, deve-se produzir mais portáteis do
que desktops.
Cada portátil contribui para o lucro em
250 contos, e cada desktop em 150 contos.
9. Um agricultor deve determinar quantos acres de milho e quantos acres de trigo deverá semear. Um
acre de trigo rende 25 galões e requer 10 horas de
trabalho por semana. Um acre de milho rende 10
galões e requer 4 horas de trabalho por semana.
Toda a produção poderá ser vendida, o trigo a 4
euros/galão, e o milho a 3 euros/galão. Estão disponı́veis 7 acres de terra e 40 horas de trabalho por
semana. Por imposição governamental, dever-se-á
produzir pelo menos 30 galões de milho durante o
ano corrente.
(a) Utilizando como variáveis de decisão o número
de acres de milho (x1 ) e de trigo (x2 ) semeados,
formule o problema linear cuja solução dará a
receita máxima a este agricultor.
(b) Indique quais das seguintes soluções são admissı́veis:
i.
ii.
iii.
iv.
(x1 = 2, x2 = 3)
(4, 3)
(2, −1)
(3, 2)
(c) Utilizando como variáveis de decisão o número
de galões de milho (x1 ) e de trigo (x2 ) produzidos, reformule o problema.
(d) Resolva graficamente este problema.
10. Identifique os problemas de programação linear
desta folha. Resolva-o escrevendo um programa
na linguagem AMPL/GnuMathProg e utilizando o
software glpsol.
11. Identifique os problemas de programação não linear
desta folha. Resolva-o escrevendo um programa na
linguagem AMPL e utilizando o software ampl.