UNIVERSIDADE DA BEIRA INTERIOR
Investigação Operacional
Frequência
1º Semestre
2 horas + 30 min
06/01/98
NOTA : Sempre que possível justifique convenientemente as respostas.
1. O quadro seguinte refere-se a um problema de maximização :
XB
x1
x2
x3
x4
x5
2º m.
x3
β
−1
1
0
0
4
x4
−4
φ
0
1
0
1
x5
3
δ
0
0
1
α
zj − cj
2
ε
0
0
0
10
A que condições devem obedecer α, β, φ, δ e ε para que sejam verdadeiras as seguintes afirmações :
a) A solução é óptima.
b) Existem soluções óptimas alternativas.
c) A solução é não limitada.
d) A solução é degenerada.
e) A solução é não admissível.
f) Admitindo que α ≥ 0 e que a solução não é óptima, indique qual a variável que entra na base, a
que sai e qual a variação na FO para as várias hipóteses de mudança de base.
2. Considere o seguinte problema de PL :
Maximizar
Sujeito a
Z=
8 x1 + 4 x2
+
x4
x1 + 2 x2 + 4 x3 + 2 x4 ≤ 30
x3 + 2 x4 ≤ 20
4 x1 + 2 x2 +
x1 , x2 , x3 , x4 ≥ 0
cujo plano óptimo (quadro de Simplex óptimo) é o seguinte :
(recurso 1)
(recurso 2)
XB
x1
x2
x3
x4
x5
x6
2º m.
x5
0
3/2
15/4
3/2
1
−1/4
25
x1
1
1/2
1/4
1/2
0
1/4
5
zj − cj
0
0
2
3
0
2
40
a) Em relação ao plano óptimo :
Qual a quantidade de produto a fabricar ?
Qual a quantidade não usada de cada um dos recursos ?
b) Será que a solução óptima é única ? Se existem óptimos alternativos, determine-os todos.
c) Supondo que o coeficiente de x4 na função objectivo, c4, sofreu alteração de 1 para 5, verifique se a
solução se mantém óptima. Se deixou de o ser, indique :
Que processo utilizar no sentido de determinar a solução óptima deste novo problema.
Que variável vai entrar na base e qual vai deixar a base.
d) Supondo que a disponibilidade do recurso 2 foi alterado de 20 para 140, verifique se a solução se
mantém óptima. Se deixou de o ser, determine a solução óptima do novo problema.
1
e) Qual a gama dentro da qual pode variar o coeficiente de x1 na função objectivo, de modo que a
solução se mantenha óptima. Qual a variação correspondente do valor da função objectivo ?
f) Pretende-se avaliar a viabilidade da introdução de um novo produto, representado pela variável
de decisão x7. Os coeficientes de x7 nas restrições são (5, 8) e na função objectivo é c7. Qual a gama
admissível para c7 de modo a ser rentável iniciar a produção do novo produto ?
3.
Uma empresa decidiu iniciar a produção de 2 novos produtos, usando 3 fábricas que normalmente
produzem em excesso. A capacidade de produção de cada fábrica é medida pela quantidade de
produtos fabricados por dia (última coluna da tabela). A última linha da tabela dá-nos a quantidade
média vendida de cada produto por dia. Cada fábrica produz qualquer um dos produtos, com excepção
da fábrica 1 que não produz o produto 1. Por outro lado, os custos por unidade de cada produto diferem
de fábrica para fábrica, como mostra a tabela :
Custo por unidade
Produto 1
Produto 2
Capacidade
de Produção
Fábrica 1
Fábrica 2
Fábrica 3
-8
7
4
3
1
75
45
75
Quantidade média
50
70
Determine o plano óptimo (menor custo) de produção dos 2 produtos pelas 3 fábricas, tendo em conta
que o mesmo produto pode ser produzido em várias fábricas.
4. Seja G = (N, A, C), com N = {1, 2, ..., 10}, uma rede dirigida. Sabe-se que o caminho mais curto entre
os nós 1 e 10, e respectivo comprimento, são : p = [1, 3, 5, 7, 8, 10] e C(p) = 45.
Atendendo a que o comprimento do arco (8, 10) é 5 (C8,10 = 5), qual o caminho mais curto entre os nós 1
e 8 ? E qual o seu comprimento ? Justifique as suas respostas.
5. Na rede da figura, a cada arco (i, j) está associado a sua capacidade, bij, e também o fluxo nele
existente actualmente, xij.
a) Determine o fluxo que actualmente pode ser enviado do nó 1 para o nó 6.
b) Determine o fluxo máximo que pode ser enviado do nó 1 para o nó 6.
c) Determine o corte mínimo da rede.
6. Caso pretenda determinar o caminho com o menor número de arcos entre dois nós numa rede
dirigida qualquer, G = (N, A, C), como resolveria o problema.
2
7. Uma fundição recebeu uma encomenda de 2 000 kgs de uma liga metálica que deve possuir as
seguintes características : pelo menos 60% do seu peso em cobre e não mais de 30% do seu peso em
níquel. A liga pode ser obtida directamente a partir de cobre e níquel adquiridos no mercado ou a partir
de sucatas provenientes da produção de outras ligas que contêm aqueles metais. Os dados técnicoeconómicos relevantes são os seguintes :
Composição dos materiais (%)
Materiais a utilizar
Sucatas
Liga A
Liga B
Puros
Níquel
Cobre
Miscelânea
Níquel
Cobre
Outros
Disponibilidades
kgs
25
40
70
50
5
10
1 000
1 500
30
24
100
ilimitada
ilimitada
ilimitada
10
48
4
100
100
Preço
u.m./kg
Sabendo que a fundição pretende minimizar o custo da liga metálica, construa um modelo matemático
de PL para o problema, explicitando o significado das variáveis de decisão, restrições e função objectivo.
3
4