GAB_Lista2_POI

Prévia do material em texto

PUC – Engenharia Industrial
Pesquisa Operacional I – Lista de Exercícios II 
� PAGE �3�/� NUMPAGES �3�
1. O quadro abaixo representa uma das iterações do método simplex para o problema padrão.
	EQ
	VB
	x1
	x2
	x3
	x4
	x5
	x6
	B
	z
	-
	0
	0
	-4
	5
	0
	0
	1280
	1
	
	1
	0
	1
	0
	0
	0
	80
	2
	
	0
	1
	0
	½
	0
	0
	40
	3
	
	0
	0
	2
	-1
	0
	1
	20
a) Identifique as VB’s.
x1, x2, x6 
b) Escreva as equações correspondentes
c) Identifique a solução correspondente
x1 = 80 ; x2 = 40 ; x6 = 20 ; z = 1280
c) A solução é ótima? Por quê?
Não, ainda há coeficiente negativo na linha de Z.
2) Cada um dos quadros abaixo representa o final de uma iteração de um problema de maximização. Analise cada um deles quanto às soluções.
a) ótima, múltipla, não compatível
b) ótima, única e degenerada
3) O quadro seguinte representa a solução de um problema standard de maximização. Os valores das constantes A, B, C, D, E são desconhecidos. Estabeleça condições para estas constantes para que:
a) a solução seja ótima e única A, B > 0
b) a solução seja ótima e múltipla A = 0 e B >= 0 ou A >= 0 e B = 0
c) a solução não seja compatível E < 0
d) a solução seja degenerada E = 0
e) a solução seja compatível, mas o problema ilimitado. E >= 0, B <=0, B < A, C <= 0
f) a solução compatível, mas não é ótima; a solução pode ser melhorada substituindo-se a variável x5 da base por x2 E >= 0, A <=0, A < B, C <= 0 , D > 0, E/D < 8/2
	EQ
	VB
	x1
	x2
	x3
	x4
	x5
	x6
	B
	Z
	-
	0
	A
	0
	3
	0
	B
	-
	1
	x1
	1
	0
	0
	2
	0
	0
	2
	2
	x5
	0
	D
	0
	-2
	1
	C
	E
	3
	x3
	0
	2
	1
	1
	0
	-1
	8
4) Após resolver um PPL empregando o algoritmo simplex, chegou-se ao seguinte quadro final:
	Eq
	Vb
	X0
	X1
	X2
	X3
	X4
	X5
	X6
	B
	Z
	-
	1
	0
	0
	0
	1
	-3
	2
	56
	1
	X1
	0
	1
	0
	-1/3
	0
	2
	1/3
	4
	2
	X4
	0
	0
	0
	2
	1
	1/3
	2/3
	-1
	3
	X2
	0
	0
	1
	½
	0
	-1/2
	3/2
	2
Está confirmado que z = 56 é o resultado correto. A solução ótima única foi encontrada e a seqüência básica é S = (1, 4, 2). Mas alguns erros ocorrem neste quadro final. Identifique-os, justificando.
coef. x3 na FO não pode ser 0 (sol. é única)
coef. x4 na FO tem que ser 0 (a variável é básica)
coef. x5 na FO tem que ser positivo (a solução é ótima)
o valor x2 não pode ser negativo
5) Há uma e só uma alternativa certa para cada item:
5.1) Uma condição indispensável para um problema de decisão é:
existir mais de uma alternativa de decisão
existirem vários objetivos definidos pelo agente de decisão
o agente de decisão ser analista de PO
existirem exatamente duas alternativas de decisão
Sobre a metodologia da PO
Cada problema exige uma adequação da metodologia adotada
As fases de construção do modelo e de obtenção de uma solução são, em certos casos, prescindíveis.
todas as fases têm de ser aplicadas seguindo uma ordem pré-estabelecida, começando uma fase, quando a anterior acabou.
Há problemas de decisão estratégicos em que o agente de decisão é irrelevante
Uma das seguintes afirmações é falsa:
Um PPl tem sempre , pelo menos, uma solução viável: a solução em que todas as variáveis de decisão têm valor nulo
Um PPL pode ter um número infinito de soluções ótimas
Um PPL pode não ter solução ótima
Um PPL pode ter soluções viáveis, mas não ter nenhuma solução ótima com valor finito.
Uma das seguintes afirmações é falsa:
Se um PPL tiver uma e apenas uma solução ótima
geometricamente, esta pode não corresponder a um ponto extremo
geometricamente, esta corresponde a um ponto extremo
algebricamente, esta corresponde a uma base viável
algebricamente, esta é necessariamente uma solução básica sem variáveis com valor negativo.
Considere que todas as restrições redundantes de um modelo de PL foram removidas e que, em seguida, esse modelo foi resolvido. No máximo, quantas variáveis de decisão podem ter um valor positivo numa solução ótima?
Este valor será no máximo igual ao número de restrições do modelo.
Um problema de maximização:
só pode ter restrições do tipo “≥ “
só pode ter restrições do tipo “ = “
pode ter qualquer tipo de restrições 
só pode ter restrições do tipo “≤ “ ou “ = “
 Considere a representação gráfica da região viável de um PPL.
Qualquer que seja a FO o problema não tem solução ótima finita FALSO
existe pelo menos uma FO para o qual o problema é impossível FALSO
existem várias funções objetivo para as quais o problema tem uma e somente uma solução ótima
se o problema for de minimização, o ponto (0,0) é necessariamente uma solução ótima, podendo ou não haver soluções ótimas alternativas. FALSO