View
235
Download
0
Category
Preview:
Citation preview
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
1
Universidade da Beira Interior – Departamento de Matemática INVESTIGAÇÃO OPERACIONAL
Ano lectivo: 2008/2009 Cursos: Economia Ficha de exercícios nº2: Algoritmo Simplex Primal.
1. Considere o seguinte conjunto de soluções admissíveis: { }0,1023010220:),( 2121212121
2
21 +++= xxxxxxxxxxxxS
a) Determine, indicando graficamente, as regiões de S onde as variáveis de folga são nulas.
b) Indique todas as soluções básicas admissíveis, as respectivas matrizes básicas associadas e classifique-as quanto à degenerescência. 2. Considere o seguinte conjunto de soluções admissíveis: { }0,353:),( 2121121
2
21 += xxxxxxxxxS .
Relativamente a este conjunto, indique: a) Três soluções básicas não admissíveis. b) Todas as soluções básicas admissíveis e as respectivas matrizes básicas. c) Uma solução básica degenerada. d) Uma solução admissível não básica.
3. Seja S um conjunto de soluções admissíveis definido da seguinte forma: { }+= ,0,4441:),( 2121221
2
21 xxxxxxxxxS a) Determine os valores de por forma que:
i) =S ii) { })4,3(=S
iii) { }0,41:),( 21221
2
21= xxxxxxxS
b) Determine, caso seja possível, expressões para Z=f(x1,x2), por forma que o problema em Programação Linear Max Z= f(x1,x2) s.a: x S , com =1
i) tenha uma única solução óptima degenerada. Indique essa solução. ii) tenha uma infinidade de soluções óptimas: indique três expressões
diferentes de Z=f(x1,x2) que dão origem a este tipo de soluções. iii) não tenha solução óptima finita.
c) Considere o problema em Programação Linear: Max Z= x1 - x2 s.a: x S , com =1
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
2
i) Resolva graficamente o problema. ii) Indique, caso existam:
• duas soluções básicas não admissíveis; • todas as soluções básicas admissíveis e respectivas matrizes básicas, classificando-as quanto à degenerescência; • uma solução não básica admissível; • uma solução básica óptima; • uma solução óptima não básica.
4. Considere o seguinte problema em Programação Linear:
Maximizar Z = 25 x1 + 20 x2
Sujeito a: x1 + x2 50
m x1 + x2 80
2 x1 + 5 x2 220
x1, x2 0
a) Para que valores de m reais pode =
052
11
011
mB constituir uma matriz
associada a uma solução básica admissível? b) Tome m=5. Determine a solução associada a B e classifique-a.
5. (Exame Época Normal 2004)
Considere o seguinte problema linear, cuja região admissível se encontra esboçada no gráfico ao lado:
Maximizar Z = 2 x1 x2
Sujeito a x1 + x2 4
2x1 + x2 6
x1 + 2x2 6
x1, x2 0
a) Indique e classifique três soluções básicas admissíveis associadas ao vértice A. b) Indique uma solução admissível não básica.
6. Considere os seguintes problemas:
a) Min Z = 2 x1 + 3x2 + 5 x3
Sujeito a x1 + x2 - x3 -5
-6x1 + 7x2 - 9x3 = 15
|8x1 - 7x2 + 5x3| 13
x1, x2 0, - < x3<
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
3
b) Max Z = min(7x1-8x2, 5 x1+9 x2+4 x3)
Sujeito a 6x1 + 9x2 + 8x3 200
-8x1 - 5x2 - 3x3 -100
x1, x2,x3 0 Escreva os problemas em Programação Linear e simultaneamente na forma padrão. 7. Considere o seguinte problema de PL:
Maximizar Z = 4 x1 + x2
Sujeito a 3 x1 + x2 30 (recurso 1)
x1 + x2 20 (recurso 2) x1 8 (recurso 3)
x1 , x2 0
a) Represente graficamente o espaço das soluções. b) Indique todas as soluções básicas admissíveis (SBA) do problema e respectivos
valores da função objectivo (f.o.). c) Determine a solução óptima e o respectivo valor da f.o. através do Algoritmo
Simplex. 8. Resolva o seguinte problema utilizando o Algoritmo Simplex:
Maximizar Z = 3 x1 + 2 x2 + 4 x3 + 5 x5 + x6
Sujeito a 2 x1 + 6 x2 + 3 x3 + 2 x4 + 5 x5 + 4 x6 600 xi 0 , i = 1, ..., 6
9. Resolva o seguinte problema utilizando o Algoritmo Simplex:
Maximizar Z = 3 x1 + 2 x2
Sujeito a 2 x1 3 x2 3
x1 + x2 5 x1, x2 0
10. Uma empresa deseja realizar um “show” na televisão para publicitar os seus produtos. O “show” durará exactamente 30 minutos e nele actuarão um actor cómico e um grupo musical. A empresa deseja que sejam consagrados a anúncios pelo menos 4 minutos. A estação de televisão exige que o tempo dedicado aos anúncios não exceda 8 minutos, não podendo, além disso, em caso algum ser superior ao tempo atribuído ao actor cómico. Este, por sua vez, não está disposto a actuar durante mais de 15 minutos. Ao grupo musical caberá o tempo restante. O custo de actuação do actor é de 1000 /min e o do grupo musical é 5.000 /min. Sondagens recentes mostram que: • por cada minuto de exibição do actor, 4000 espectadores sintonizam essa estação; • por cada minuto de exibição do grupo musical, espera-se 2000 novos espectadores; • por cada minuto de anúncios 1.000 pessoas desligam o aparelho ou sintonizam outra estação.
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
4
A empresa pretende determinar a constituição ideal do referido “show”, de modo a: a) Maximizar o número de espectadores; b) Minimizar o custo do “show”.
Formule matematicamente ambos os problemas e resolva-os usando o Algoritmo Simplex. 11. Uma fábrica produz dois tipos de pneus: radiais sem câmara-de-ar e radiais com câmara-de-ar. Ambos os tipos passam pelas seguintes fases de fabrico: Moldagem, Vulcanização e Acabamento. A matriz tecnológica, as margens brutas por centena de pneus e as disponibilidades diárias em horas das secções da fábrica, são as seguintes:
Pneus (Operários/100 pneus) Disponibilidades Secções sem câmara com câmara (Operários/dia) Moldagem 2 2 12 Vulcanização 2 1 9 Acabamento 1 3 16 Margem bruta ( ) 8 8
Pretende-se determinar o programa de produção diária, sabendo que não existem dificuldades de mercado nem compromissos assumidos. Resolva este problema através do Algoritmo Simplex. Verifique a existência de óptimos alternativos.
12. Considere o seguinte problema de P.L. :
Maximizar Z = x1 + x2 + x3
Sujeito a x1 + x3 1
2 x1 + x2 + x3 8 x1 + x2 x3 2
x1, x2, x3 0
Sabe-se que no quadro óptimo do Simplex para este problema as variáveis x3, x5 e
x2 são (por esta ordem) básicas e x5 é a variável folga associada à 2ª restrição (x4 e x6 são
as variáveis de folga para a 1ª e 3ª, respectivamente). Conhece-se ainda a inversa da base óptima (B):
a) Sem aplicar o algoritmo Simplex, construa o quadro Simplex óptimo associado à matriz básica B.
b) Utilizando o quadro óptimo, determine as quantidades não utilizadas de cada recurso.
=
101
112
001
1B
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
5
13. Resolva, utilizando o Método do M Grande (Penalidades), o seguinte problema:
Maximizar Z = x1 + 2 x2 + x3
Sujeito a x1 + x2 + x3 = 6
2 x1 + 3 x2 + 3 x4 = 1 2 x1 + x2 + x3 + x4 = 1
x1, x2, x3, x4 0
14. Resolva, utilizando o Algoritmo Simplex, o seguinte problema de PL :
Maximizar Z = 2 x1 + 3 x2 Sujeito a 2 x1 + 2 x2 6
x1 + x2 1
x2 3 x1, x2 0
15. Resolva, utilizando o Algoritmo Simplex, o seguinte problema:
Minimizar Z = 100 x1 + 200 x2 + 50 x3
Sujeito a 5 x1 + 5 x2 + 10 x3 + x4 1000
10 x1 + 8 x2 + 5 x3 2000 10 x1 + 5 x2 500
xi 0 , i = 1,...,4
16. Resolva, utilizando o Algoritmo Simplex, o seguinte problema:
Maximizar Z = x1 + 2 x2 + 3 x3 + 4 x4 Sujeito a 3 x1 + 2 x2 + 3 x3 x4 25
2 x1 + x2 2 x3 + x4 5
2 x1 + 2 x2 + x3 + x4 = 2 xi 0 , i = 1,...,4
17. Resolva, utilizando o Método das Duas Fases, o seguinte problema:
Maximizar Z = 6 x1 + 5 x2
Sujeito a 0.2 x1 + 0.1 x2 9 0.3 x1 + 0.1 x2 6
0.3 x1 + 0.6 x2 18
0.2 x1 + 0.2 x2 14 x1, x2, x3, x4 0
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
6
18. Resolva, utilizando o Método das Duas Fases ou do M Grande, o seguinte problema:
Maximizar Z = 2 x1 x2 + x3
Sujeito a 2 x1 + x2 + 3 x3 9
x1 x2 = 6 x2 2 x3 4
xi 0 , i = 1,...,3
19. Resolva, utilizando o Método das Duas Fases ou do M Grande, o seguinte problema:
Maximizar Z = x1 + 2 x2 + 3 x3
Sujeito a 2 x1 + x2 + 2 x3 3
x1 + x2 + x3 5
3x1 2 x3 = 8 xi 0 , i = 1,...,3
20. Resolva, utilizando o Algoritmo Simplex, o seguinte problema:
Minimizar Z = 3 x1 2 x2 + x3 + x4
Sujeito a 2 x1 4 x2 x3 + x4 8 x1 + x2 + 2 x3 3 x4 10
x1 x2 4 x3 + x4 3 xi 0 , i = 1,...,4
21. Considere o Problema Linear:
Minimizar Z = 5x1 – 2x2 + x3 Sujeito a 2x1 + 4x2 + x3 6 2x1 + x2 + 3x3 2 x1, x2, x3 0
a) Calcule uma solução básica admissível. b) Obtenha a solução óptima deste problema através do Algoritmo Simplex,
indicando a base óptima. 22. Considere o problema seguinte: Minimizar Z = 5x1 + 2x2 + 3x3 Sujeito a x1 + 5x2 + 2 x3 b1 x1 - 5x2 - 6x3 b2 x1, x2, x3 0 em que b1 e b2 são constantes não negativas. O quadro Simplex óptimo deste problema é:
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
7
xB x1 x2 x3 x4 x5 b x1 1 a 2 1 0 30 x5 0 b -8 -1 1 10
zj-cj 0 c 7 d e 150
a) Calcule os valores de b1e b2 que dão origem ao quadro Simplex apresentado. b) Calcule os valore de a a e do quadro óptimo.
23. Considere o seguinte problema de Programação Linear:
Maximizar Z = 2 x1 x2 + x3
Sujeito a 3 x1 + x2 + x3 6
x1 x2 + 2 x3 1 x1 + x2 x3 2
x1, x2, x3 0
Sabe-se que no quadro óptimo do Simplex para este problema as variáveis x4, x1 e
x2 (por esta ordem) são básicas e x4 é a variável folga associada à 1ª restrição (x5 e x6 são
as variáveis de folga para a 2ª e 3ª, respectivamente). Sabendo que a inversa da base óptima (B) é: Construa o quadro óptimo de Simplex associado a B, sem aplicar o algoritmo de Simplex. (Frequência 2004/2005) 24. Considere a seguinte formulação em Programação Linear:
Maximizar Z = x1 - x2
Sujeito a: 4x1 + x2 4
x1 + x2 3
x1, x2 0.
a) Encontre a solução óptima deste problema através do Algoritmo Simplex b) Classifique a solução encontrada em a) quanto à degenerescência e unicidade.
(Ex. Recurso 2004/2005) 25. Considere o seguinte quadro Simplex inicial de um problema de maximização com todas as restrições de “ ”:
xB x1 x2 x3 x4 b x3 1 1 1 0 2 x4 3 1 0 1 3
zj-cj -1 -2 0 0 0
=
21
21
21
211
0
0
211
B
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
8
a) Interprete economicamente o custo reduzido de x1. b) Fazendo x2 entrar para a base, justifique por que razão a variável que se torna
não básica se identifica determinando o min{1
2,1
3}.
(Mini-Teste nº2, 2005/2006, EC) 26. Considere o seguinte problema em Programação Linear:
Min Z = –2x1 + 2x2 s.a: x1 – x2 b1
a21x1 + x2 b2 xi 0, i=1,2
em que b1 e b2 são constantes não negativas. Considere o seguinte quadro Simplex referente a uma SBA do problema, onde as variáveis x3 e x4 são as variáveis de folga das primeira e segunda restrições, respectivamente:
xB x1 x2 x3 x4 b x1 1 –1 1 0 1 x4 0 2 –1 1 3
zj–cj 0 0 –2 0 –2 Quadro 1
a) Fazendo x2 entrar para a base, preencha o quadro consequente:
xB x1 x2 x3 x4 b
zj–cj
Quadro 2
b) Indique a matriz básica associada à SBA do quadro 1:
[ ] =11
11B [ ] =
11
01B [ ] =
10
01B [ ] =
01
11B
c) Classifique como verdadeira (V) ou falsa (F) cada uma das seguintes afirmações:
[ ] O problema tem solução óptima única. [ ] No quadro 1, z3–c3=–2, significa que é vantajoso fazer x3 entrar para a base. [ ] A SBA associada ao quadro 1 é degenerada.
[ ] O vector dos termos independentes é =4
1b .
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
9
(Exame P1, 2005/2006, ME+MI+MA+EPGI+EI+EC) 27. Considere a seguinte região de admissibilidade de um PL e indique quais os pontos assinalados que correspondem a:
a) Soluções admissíveis; b) Soluções básicas admissíveis; c) Soluções não admissíveis; d) Soluções básicas não admissíveis;
e) SBA degeneradas.
(Exame P2, 2005/2006, ME+MI+MA+EPGI+EI+EC+E) 28. Uma empresa pretende maximizar o seu lucro, expresso em milhares de , através da determinação da solução optima do seguinte problema (já na forma padrão):
Max Z = 10x1 – 10x2 (milhares de ) s.a: 4x1 + 2x2 – x3 = 8
x1 – x2 + x4 = 2 xi 0, i=1,…,4
a) Determine a solução óptima deste problema através do Algoritmo Simplex. b) Classifique a solução óptima obtida na alínea anterior quanto à degenerescência e
unicidade. c) Com base na solução óptima determinada em a), complete as seguintes
afirmações: i. Ao fazer x4 entrar para a base, a variação do valor da f.o. será de _______ mil . A solução que se obtém é ___________ (quanto à degenerescência). ii. Ao fazer x2 entrar para a base, esta variável poderá tomar o valor _________, e a variação do valor da f.o. será de _________ mil .
(MT1, 2006/2007, Economia e Gestão) 29. Uma empresa de construção civil pretende maximizar o seu lucro, expresso em milhares de , através da determinação da solução óptima do seguinte problema:
Max Z = –2x1 + 4x2 (milhares de ) s.a: 2x1 + x2 8 (área disponível)
x1 – x2 1 (procura) xi 0, i=1,2
a) Determine a solução óptima deste problema através do Algoritmo Simplex. b) A solução óptima obtida na alínea anterior é _____________ (quanto à
degenerescência) e ____________ (quanto à unicidade). c) Com base na solução óptima determinada em a), suponha que se pretende que:
ou a variável de folga da restrição relativa à área disponível seja básica; ou a variável de folga da restrição relativa à procura seja básica. Desta forma, a variável cuja entrada forçada para a base prejudica menos o valor da f.o. será ______, pois a variação do valor da f.o. será de _______ mil (quando essa variável entra para a base) ao invés de _______ mil (quando a outra variável entra para a base). A solução que se obtém é ___________ (quanto à degenerescência) e é uma _________ (SBA, SNBA, SBNA ou SNBNA).
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
10
(Frequência, 2006/2007, Gestão e Economia) 30. Considere o seguinte Programa Linear e as soluções propostas.
Max Z = 0x1 + 2x2 + x3 s.a: x1 + 2x2 + x3 2
2x1 + x2 + 2x3 2 xi 0, i=1,2,3
A=(1, 1, 1); B=(1/3, 2/3, 1/3); C=(2/3, 2/3, 0); D=(0, 0, 0), E=(1, 0, 1); F=(1, 0, 0); G=(0, 1, 0); H=(1/2, 0, 1/2)
a) Indique quais as soluções propostas que correspondem a: (i) Soluções básicas admissíveis (ii) Soluções básicas não admissíveis (iii) Soluções admissíveis não básicas (iv) Soluções não admissíveis não básicas
b) Indique a base associada às soluções básicas. c) Uma solução óptima é: (Sugestão: Como SBA inicial utilize a que está associada
à solução x = (0, 0, 1), cuja inversa da base respectiva é B 1 = A4 A3[ ]1
=1
12
01
2
onde
A4 é a coluna da variável de folga da 1ª restrição.)
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
11
Soluções de alguns exercícios da Ficha 2: 1.b) Existem 7 SBA’s:
1) ==
5
4
3
2
6
1
x
x
x
x
xex
xx
BN; )0,25,20,15,5,0(=x ; =
0002
1001
0102
0011
B ; não degenerada.
2) ==
5
4
3
1
6
2
x
x
x
x
xex
xx
BN; )0,20,0,30,0,10(=x ; =
0001
1001
0101
0011
B ; degenerada.
3) ==
6
5
3
1
4
2
x
x
x
x
xex
xx
BN; )0,20,0,30,0,10(=x ; =
1001
0101
0001
0011
B ; degenerada.
4) ==
5
3
2
1
6
4
x
x
x
x
xex
xx
BN; )0,20,0,30,0,10(=x ; =
0021
1011
0021
0111
B ; degenerada.
5) ==
6
3
2
1
5
4
x
x
x
x
xex
xx
BN; )
3
80,0,0,
3
110,
3
20,
3
70(=x ; =
1021
0011
0021
0111
B ; não deg.
6) ==
6
4
2
1
5
3
x
x
x
x
xex
xx
BN; )45,0,55,0,25,5(=x ; =
1021
0011
0121
0011
B ; não deg.
7) ==
6
5
4
2
3
1
x
x
x
x
xex
xx
BN; )30,10,50,0,20,0(=x ; =
1002
0101
0012
0001
B ; não deg.
Nota: Repare que as SBA’s 2, 3 e 4 correspondem ao mesmo ponto )0,20,0,30,0,10(=x .
De facto, sabemos que a cada ponto extremo (existem 5) da região admissível está associada pelo
menos uma SBA.
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
12
2.a) Existem 3 SBNA’s:
1) ==
5
4
3
2
1
x
x
x
xex
xx
BN; )3,5,3,0,0(=x .
2) ==
5
4
2
3
1
x
x
x
xex
xx
BN; )6,5,0,3,0(=x .
3) ==
5
3
1
4
2
x
x
x
xex
xx
BN; )2,0,2,0,5(=x .
2.b) Existem 5 SBA’s:
1) ==
4
3
2
5
1
x
x
x
xex
xx
BN; )0,5,6,3,0(=x ; =
001
100
011
B ; SBA não degenerada.
2) ==
5
4
1
3
2
x
x
x
xex
xx
BN; )0,2,0,0,3(=x ; =
101
011
001
B ; SBA degenerada.
3) ==
4
3
1
5
2
x
x
x
xex
xx
BN; )0,2,0,0,3(=x ; =
001
101
011
B ; SBA degenerada.
4) ==
4
2
1
5
3
x
x
x
xex
xx
BN; )0,2,0,0,3(=x ; =
011
101
011
B ; SBA degenerada.
5) ==
5
2
1
4
3
x
x
x
xex
xx
BN; )4,0,0,2,5(=x ; =
111
001
011
B ; SBA não degenerada.
Nota: Repare que as SBA’s 2, 3 e 4 correspondem ao mesmo ponto )0,2,0,0,3(=x . De
facto, sabemos que a cada ponto extremo (existem 3) da região admissível está associada pelo
menos uma SBA.
2.c) Qualquer uma das soluções 2, 3 ou 4 da alínea anterior.
2.d) Qualquer ponto de S, à excepção dos pontos extremos.
3.a)i) >4 3.a)ii) =4 3.a)iii) 1/4
3.b)i) f(x1,x2)= -x1+x2 ou f(x1,x2)= -4x1+x2, por exemplo.
3.b)ii) f(x1,x2)= x1-x2, ou f(x1,x2)= x2 ou f(x1,x2)= -4x1-x2.
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
13
3.b)iii) Não é possível, pois a região admissível é limitada e, por isso, a solução óptima será sempre
finita.
3.c)i) Soluções óptimas alternativas: todos os pontos do segmento de recta (sobre a recta
associada à restrição 4x1+x2 4) que une os pontos (3/5,8/5) a (3,4) são soluções óptimas, com
Z*=-1.
3.c)ii) Duas SBNA’s são, por exemplo:
1) ==
5
4
2
3
1
x
x
x
xex
xx
BN; )3,3,0,1,0(=x ; 2) ==
4
3
1
5
2
x
x
x
xex
xx
BN; )0,4,2,0,1(=x ;
Existem 5 SBA’s:
1) ==
5
3
2
4
1
x
x
x
xex
xx
BN; )0,0,3,4,0(=x ; =
101
001
011
B ; SBA degenerada.
2) ==
4
3
2
5
1
x
x
x
xex
xx
BN; )0,0,3,4,0(=x ; =
001
101
011
B ; SBA degenerada.
3) ==
3
2
1
5
4
x
x
x
xex
xx
BN; )0,0,3,4,0(=x ; =
014
010
111
B ; SBA degenerada.
4) ==
5
2
1
4
3
x
x
x
xex
xx
BN; )12,0,0,4,3(=x ; =
114
010
011
B ; SBA não degenerada.
5) ==
4
2
1
5
3
x
x
x
xex
xx
BN; )0,,
5
12,0,
5
8,
5
3(=x ; =
014
110
011
B ; SBA não degenerada.
Nota: Repare que as SBA’s 1, 2 e 3 correspondem ao mesmo ponto )0,0,3,4,0(=x . De facto,
sabemos que a cada ponto extremo (existem 3) da região admissível está associada pelo menos
uma SBA.
Uma solução não básica admissível: qualquer ponto de S à excepção dos pontos
extremos.
Uma solução básica óptima: )12,0,0,4,3(=x
Uma solução óptima não básica: qualquer ponto da forma (x1,x2)=a(3,4)+(1-a)(3/5,8/5),
com a ]0,1[.
4.a) m 4 4.b) )0,10,0,40,10(=x solução básica não admissível.
7.b) Existem 5 SBA’s:
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
14
1) ==
5
4
3
2
1
x
x
x
xex
xx
BN; )8,20,30,0,0(=x ; =
100
010
001
B ; Z=0.
2) ==
5
3
2
4
1
x
x
x
xex
xx
BN; )8,0,10,20,0(=x ; =
100
001
011
B ; Z=20.
3) ==
5
2
1
4
3
x
x
x
xex
xx
BN; )3,0,0,15,5(=x ; =
101
011
013
B ; Z=35.
4) ==
4
2
1
5
3
x
x
x
xex
xx
BN; )0,6,0,6,8(=x ; =
001
111
013
B ; Z=38.
5) ==
4
3
1
5
2
x
x
x
xex
xx
BN; )0,12,6,0,8(=x ; =
001
101
013
B ; Z=32.
7.c) x*=(8,6,0,6,0) e Z*=38.
8. x*=(0,0,200,0,0,0,0) e Z*=800.
9. A solução óptima é ilimitada, i.e., não existe solução óptima; não existe um valor máximo
finito para a função objectivo.
10.a) x*=(15,7,8,0,4,0,0,7,0), em minutos, e Z*=66000 espectadores.
10.b) x*=(8,14,8,0,4,0,0,0,7), em minutos, e Z*=78000 .
11. x*=(3,3,0,0,4) ou x*=(1,5,0,2,0), em pacotes de centenas de pneus, pois existem soluções
óptimas alternativas (verifique graficamente que estas SBA’s são duas das soluções óptimas
alternativas), e Z*=48 .
12.a)
xB x1 x2 x3 x4 x5 x6 b
x3 1 0 1 1 0 0 1
x5 -1 0 0 -2 1 -1 4
x2 2 1 0 1 0 1 3
zj-cj 2 0 0 2 0 1 4
INVESTIGAÇÃO OPERACIONAL 2008/2009 – Ficha de exercícios 2
15
12.b) Sobram 0, 4 e 0 unidades dos recursos 1, 2 e 3, respectivamente (sendo a i-ésima restrição
respeitante ao recurso i, com i=1, 2, 3).
13. Problema impossível (região admissível vazia).
14. Solução óptima ilimitada.
15. Problema impossível (região admissível vazia).
16. Problema impossível (região admissível vazia).
17. x*=(40,10,0,7,0,0) e Z*=290.
18. Problema impossível (região admissível vazia).
19. Solução óptima ilimitada.
20. Solução óptima ilimitada.
21.a) x=(0,0,2/3,16/3,0,0)
21.b) x*=(0,16/11,6/33,0,0) e Z*= - 30/11.
22.a) b1=30 e b2=40.
22.b) a=5, b=-10, c=23, d=5, e=0
23.
xB x1 x2 x3 x4 x5 x6 b
x4 0 0 1 1 -1 -2 1
x1 1 0 1/2 0 1/2 1/2 3/2
x2 0 1 -3/2 0 -1/2 1/2 1/2
zj-cj 0 0 3/2 0 3/2 1/2 5/2
24.a) x*=(3,0,8,0); Z*=3
24.b) Não degenerada (justificar!...); única (justificar!...) 26.a)
xB x1 x2 x3 x4 b x1 1 0 1/2 1/2 5/2
x2 0 1 -1/2 1/2 3/2
zj–cj 0 0 -2 0 -2
26.b) =11
01B
26.c) F; F; F; V 27.a) B,C,D,G,H b) C,D,G c) A,E,F d) F e) Não existem 28.a) x*=(2,0,0,0) é uma solução óptima (porquê?...), com Z*=20 mil 28.b) Degenerada (justificar!...); não única (justificar!...) 28.c)i) Zero; degenerada 28.c)ii) + ; Zero
Recommended