Exercícios de Otimização Combinatória

Prévia do material em texto

Universidade Federal do Rio Grande do Sul
Instituto de Informa´tica
Departamento de Informa´tica Teo´rica
INF05510 – Otimizac¸a˜o combinato´ria
2011/2
Prof. Marcus Ritt
Exerc´ıcios 3
Exerc´ıcio 1 (Me´todo Simplex)
Quais das seguintes afirmac¸o˜es sa˜o verdadeiras ou falsas em relac¸a˜o ao me´todo Simplex. Justifique a
resposta brevemente.
(a) Se o me´todo Simplex entra num ciclo, enta˜o uma soluc¸a˜o ba´sica degenerada se repete.
(b) Se um diciona´rio na˜o e´ degenerado, enta˜o a varia´vel entrante e a varia´vel sainte sa˜o determinados
univocamente.
(c) O nu´mero de soluc¸o˜es o´timas de um programa linear sempre e´ finito.
Exerc´ıcio 2 (Formulac¸a˜o)
A UFRGS tem um supercomputador para os professores, alunos de doutorado e mestrado. Nas horas
de trabalho, um operador tem que estar presente para operar a ma´quina e tambe´m para fazer algumas
implementac¸o˜es. O Lu´ıs Ota´vio gerencia toda operac¸a˜o. No comec¸o de cada semestre, ele tem a tarefa
da alocar as horas de trabalho a cada operador. Como todos operadores tambe´m sa˜o estudantes da
UFRGS, eles podem trabalhar somente um nu´mero limitado de horas por dia. A seguinte tabela mostra
a disponibilidade
Nome Sala´rio [R$/h] Seg Ter Qua Qui Sex
P.V. 10.00 6 0 6 0 6
K.O. 10.10 0 6 0 6 0
F.K. 9.90 4 8 4 0 4
S.C. 9.80 5 5 5 0 5
N.R. 10.80 3 0 3 8 0
F.T. 11.30 0 0 0 6 2
Cada operador recebe um valor diferente por hora, conforme a sua experieˆncia e capacidade de pro-
gramac¸a˜o. O Lu´ıs Ota´vio garante um nu´mero mı´nimo de horas por semana para cada aluno. Para os
primeiros quatro, que sa˜o alunos de graduac¸a˜o, ele garante 8 h/semana. Para os dois restantes, que sa˜o
alunos de mestrado 7 h/semana. O laborato´rio com o computador esta´ aberto de 8 da manha˜ ate´ 10
da noite de segunda ate´ sexta, com exatamente um operador dispon´ıvel nesse per´ıodo. O Lu´ıs Ota´vio
quer minimizar os gastos com os operadores. Quantas horas de trabalho ele deve atribuir para cada
operador em cada dia?
Exerc´ıcio 3 (Formulac¸a˜o)
Uma empresa esta´ interessada em maximizar o lucro mensal de quatro de seus produtos. Para fabricar
esses produtos ela utiliza dois tipos de ma´quinas (M1 e M2) e dois tipos de mate´ria prima que teˆm as
seguintes disponibilidades:
Ma´quinas Tempo Dispon´ıvel Mate´ria Disponibilidade
(ma´quina-hora/meˆs) Prima (unidades/meˆs)
M1 80 MP1 120
M2 20 MP2 160
O setor te´cnico da empresa fornece os seguintes quadros de produtividade:
Ma´quinas-hora necessa´rias para produzir uma unidade de cada produto e Mate´ria prima necessa´ria para
produzir uma unidade de cada produto:
Ma´quinas Produtos
P1 P2 P3 P4
M1 5 6 8 9
M2 2 4 0 8
Mate´ria prima Produtos
P1 P2 P3 P4
MP1 2 4 2 8
MP2 7 3 0 7
O setor comercial da empresa fornece os seguintes informac¸o˜es:
v3949 1 Licenc¸a Creative Commons
(Atribuic¸a˜o–Uso Na˜o-Comercial–Na˜o a obras derivadas 3.0 Brasil).
Universidade Federal do Rio Grande do Sul
Instituto de Informa´tica
Departamento de Informa´tica Teo´rica
INF05510 – Otimizac¸a˜o combinato´ria
2011/2
Prof. Marcus Ritt
Produtos Ma´ximo de vendas Lucro Unita´rio
(Unidades/Meˆs) (Reais/Unidade)
P1 70 10
P2 60 8
P3 40 9
P4 20 7
Deseja-se saber a produc¸a˜o mensal dos produtos para que o lucro mensal da empresa seja o ma´ximo.
Formule um modelo de programac¸a˜o linear.
Exerc´ıcio 4 (Formulac¸a˜o)
Um investidor tem treˆs alternativas de investimentos denominados A, B e C. As 3 alternativas sa˜o
exclusivas. qualquer dinheiro recebido de qualquer alternativa podera´ ser reinvestido, imediatamente,
em qualquer uma das treˆs alternativas. A alternativa A esta´ dispon´ıvel no comec¸o de cada um dos
A1 2 3 4 51
x
A1
x
A4
x
A3
x
A2
1.1x
A1
1.1x
A4
1.1x
A3
1.1x
A2
B1 2 3 4 51
x
B1
x
B2
1.2x
B1
1.2x
B2
C1 2 3 4 51
x
C1
1.4x
C1
quatro trimestres seguintes. Cada real investido em A no comec¸o de um trimestre lhe devolve 1.10 reais
no final daquele trimestre. A alternativa B esta´ dispon´ıvel no in´ıcio de cada um dos dois semestres
seguintes. Cada real investido em B no comec¸o de um semestre lhe devolve 1.20 no final daquele
semestre. A alternativa C so´ esta´ dispon´ıvel no comec¸o do primeiro ano. cada real investido em C lhe
devolve 1.40 reais um ano mais tarde.
O capital inicial do investidor e´ de 5000 reais. Sejam xi,j as quantidades investidas nas alternativas
i(i = A,B,C) nos comec¸os dos trimestres j(j = 1, 2, 3, 4) . Sejam Rj as quantidades na˜o investidas nos
comec¸os dos trimestres. Deseja-se formular um modelo de programac¸a˜o linear para fornecer o plano de
investimento que maximize a quantidade de dinheiro que o investidor pode acumular no final.
Exerc´ıcio 5 (Soluc¸a˜o de programas lineares)
Resolve graficamente.
max 500x1 + 300x2 max 5x1 + 7x2
s.a. 15x1 + 5x2 ≤ 300 s.a. 2x1 − x2 ≤ −1
10x1 + 6x2 ≤ 240 − x1 + 2x2 ≤ 1
8x1 + 12x2 ≤ 450 x1, x2 ≥ 0
x1, x2 ≥ 0
v3949 2 Licenc¸a Creative Commons
(Atribuic¸a˜o–Uso Na˜o-Comercial–Na˜o a obras derivadas 3.0 Brasil).
Universidade Federal do Rio Grande do Sul
Instituto de Informa´tica
Departamento de Informa´tica Teo´rica
INF05510 – Otimizac¸a˜o combinato´ria
2011/2
Prof. Marcus Ritt
Exerc´ıcio 6 (Soluc¸a˜o de programas lineares)
Resolva usando o me´todo Simplex com a regra do maior coeficiente.
max 2x1 − 2x2 + 3x3 max 5x1 + 4x2 − x3 + 3x4
s.a. − x1 + x2 + x3 ≤ 4 s.a. 3x1 + 2x2 − 3x3 + x4 ≤ 24
2x1 − x2 + x3 ≤ 2 3x1 + 3x2 + x3 + 3x4 ≤ 36
x1 + x2 + 3x3 ≤ 12 x1, x2, x3, x4 ≥ 0
x1, x2, x3 ≥ 0
Resolva usando a regra de Bland.
max − 2x1 + x2 − 4x3 + 3x4 max 3x1 + x2
s.a. x1 + x2 + 3x3 + 2x4 ≤ 4 s.a. x1 − x2 ≤ −1
x1 − x3 + x4 ≥ −1 − x1 − x2 ≤ −3
2x1 + x2 ≤ 2 2x1 + x2 ≤ 4
x1 + 2x2 + x3 + 2x4 = 2 x1, x2 ≥ 0
x2, x3, x4 ≥ 0
Resolva usando o me´todo lexicogra´fico.
max 2x1 + 3x2 − x3 − 12x4
s.a. − 2x1 − 9x2 + x3 + 9x4 ≤ 0
1/3x1 + x2 − 1/3x3 − 2x4 ≤ 0
x1, x2, x3, x4 ≥ 0
Exerc´ıcio 7 (Soluc¸a˜o de sistemas lineares)
Considere o programa linear
max x1 + x2
s.a tx1 + x2 ≤ 1
x1, x2 ≥ 0.
com paraˆmetro t ∈ R. Determine para quais valores de t o sistema (a) possui exatamente uma soluc¸a˜o
o´tima, (b) possui um nu´mero infinito de soluc¸o˜es o´timas, (c) e´ ilimitado, ou (d) na˜o possui soluc¸a˜o.
Justifique a resposta.
Exerc´ıcio 8 (Soluc¸a˜o de sistemas lineares)
Considere o programa linear
max sx1 + tx2
s.a − x1 + 2x2 ≤ 4
x1, x2 ≥ 0.
com paraˆmetros s, t ∈ R. Determine para qual valores de s e t o sistema (a) possui exatamente uma
soluc¸a˜o o´tima, (b) possui um nu´mero infinito de soluc¸o˜es o´timas, (c) e´ ilimitado, ou (d) na˜o possui
soluc¸a˜o. Justifique a resposta.
Exerc´ıcio 9 (Formulac¸a˜o)
Um fabricante de rac¸o˜es quer determinar a fo´rmula mais econoˆmica de uma certa rac¸a˜o. A composic¸a˜o
nutritiva dos ingredientes dispon´ıveis no mercado e os seus custos sa˜o os seguintes:
v3949 3 Licenc¸a Creative Commons
(Atribuic¸a˜o–Uso Na˜o-Comercial–Na˜o a obras derivadas 3.0 Brasil).
Universidade Federal do Rio Grande do Sul
Instituto de Informa´tica
Departamento de Informa´tica Teo´rica
INF05510 – Otimizac¸a˜o combinato´ria
2011/2
Prof. Marcus Ritt
Ingredientes
Nutrientes Soja Milho Cana
Ca´lcio 0,2% 1% 3%
Prote´ına 50% 9% 0%
Carbo-Hidratos 0,8% 2% 2%
Custo/quilo 15,00 20,00 8,00
O fabricante deve entregar 1000 quilos de rac¸a˜o por dia e garantir que esta contenha:
no ma´ximo no mı´nimo de
1,2% 0,8% Ca´lcio
- 22% Prote´ına
20% - Carbo-Hidratos
Exerc´ıcio 10 (Formulac¸a˜o)
Uma empresa possui dois produtos P1 e P2. O seu departamento de marketing estuda a forma mais
econoˆmica de aumentar em 30% a vendas de cada um dos produtos. As alternativas sa˜o:
• Investir em um programa institucional com outras empresas do mesmo ramo. Esse programa deve
proporcionar um aumento de 3% nas vendas de cada produto, para cada $ 1.000,00 investidos.
• Investir diretamente nadivulgac¸a˜o de cada produto:
– Cada $ 1.000,00 investidos em P1 retornam um aumento de 4% em sua venda.
– Cada $ 1.000,00 investidos em P2 retornam um aumento de 10% em sua venda.
A empresa dispo˜e de $ 10.000,00 para esse empreendimento. Quanto devera´ destinar a cada atividade?
Construa o modelo do sistema descrito.
Exerc´ıcio 11 (Formulac¸a˜o (Goldbarg, Luna))
Uma certa fa´brica de camisetas deseja aproveitar as finais de um campeonato de futebol para vender
camisetas dos times envolvidos. Os jogos va˜o durar quatro semanas. O custo de produc¸a˜o de cada
camiseta e´ de R$ 2,00 nas duas primeiras semanas e R$ 2,50 nas duas u´ltimas, quando a concorreˆncia
demandar por material no mercado. A demanda semanal de camisetas sera´ de 5.000, 10.000, 30.000
e 60.000. A capacidade ma´xima de produc¸a˜o da empresa e´ de 25.000 camisetas semanalmente. Na
primeira e na segunda semanas, a empresa podera´ contratar horas extras de servic¸o e fabricar mais
10.000 camisetas em cada semana. Nesse caso, o custo de produc¸a˜o sobe para R$ 2,80. O excesso de
produc¸a˜o pode ser estocado a um custo de R$ 0,20 por unidade por semana. Formular um modelo que
minimize os custos.
Exerc´ıcio 12 (Formulac¸a˜o)
Um investidor pode investir dinheiro em duas atividades A e B dispon´ıveis no in´ıcio dos pro´ximos 5
anos. Cada $1 investido em A no comec¸o de um ano retorna $1,40 (um lucro de $0,40) dois anos mais
tarde (a tempo de imediato reinvestimento). Cada $1 investido em B no in´ıcio de um ano retorna $1,70,
treˆs anos mais tarde. Existem ainda 2 atividades C e D que estara˜o dispon´ıveis no futuro. Cada $1
investido em C no in´ıcio do segundo ano retorna $2,00, quatro anos mais tarde. Cada $1 investido em
D no comec¸o do quinto ano, retorna $1,30 um ano mais tarde. O investidor tem $10.000. Ele deseja
conhecer como investir de maneira a maximizar a quantidade de dinheiro acumulado no in´ıcio do sexto
ano. Formule um modelo de P.Linear para este problema. Considere que na˜o ha´ inflac¸a˜o.
Exerc´ıcio 13 (Formulac¸a˜o (Campeˆlo Neto))
Um estudante, na ve´spera de seus exames finais, dispo˜e de 100 horas de estudo para dedicar a`s disciplinas
A, B e C. Cada um dos 3 exames e´ formado por 100 questo˜es cada uma valendo 1 ponto, e ele (aluno)
espera acertar, alternativamente, uma questa˜o em A, duas em B ou treˆs em C, por cada hora de estudo.
Suas notas nas provas anteriores foram 6, 7 e 10 respectivamente, e sua aprovac¸a˜o depende de atingir
uma me´dia mı´nima de 5 pontos em cada disciplina. O aluno deseja distribuir seu tempo de forma a
acertar o maior nu´mero de questo˜es e ser aprovado.
v3949 4 Licenc¸a Creative Commons
(Atribuic¸a˜o–Uso Na˜o-Comercial–Na˜o a obras derivadas 3.0 Brasil).