Pesquisa Operacional Unid III LIVRO

Prévia do material em texto

60
Unidade III
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Unidade III
7 Problemas envolvendo minimização da Função objetivo
7.1 algoritmo simplex
O problema de minimização, ao contrário do problema de maximização, tem pelo menos umas de suas 
restrições do tipo ≥. Assim sendo, se no problema de maximização é necessário utilizarem‑se variáveis de 
folga, nos casos de minimização devemos introduzir variáveis de excesso nas restrições do tipo ≥.
Como foi mencionado anteriormente, variável de excesso é uma variável não negativa, subtraída do 
lado esquerdo da desigualdade, e é numericamente igual à diferença entre o valor do termo independente 
e o valor das variáveis que estão à esquerda da desigualdade.
Por outro lado, variável artificial é uma variável adicionada à esquerda em todas as restrições que 
não contenham uma variável de folga, sendo utilizada nas restrições que têm originalmente o sinal ≥. 
Em um problema de minimização, sempre aparecerão algumas variáveis artificiais.
Como a solução básica inicial do Simplex é obtida igualando a zero todas as variáveis de entrada, 
a variável artificial torna‑se necessária para que a solução básica inicial não seja constituída pelas 
variáveis de excesso, que, como é subtraída na equação, acarretaria solução básica de valores negativos, 
o que contraria a lógica do Simplex. Esse procedimento corresponde a fazer, na solução básica inicial, as 
variáveis de entrada e de excesso iguais a zero e, consequentemente, as variáveis de folga e as artificiais 
iguais ao valor do termo independente da equação.
Observe, no entanto, que, na solução ótima, as variáveis artificiais devem ser iguais a zero. Para que 
isso ocorra, atribui‑se, na Função Objetivo, um coeficiente M. Esse valor é altíssimo em relação a essas 
variáveis (por exemplo, um custo altíssimo), e dessa forma o Simplex irá, na solução ótima, imputar zero 
às variáveis artificiais.
Contador (1998) relaciona as alterações necessárias no algoritmo Simplex de maximização para se 
resolver um problema de minimização. São elas:
•	 introduzir	as	variáveis	de	excesso	e	artificial;
•	 transformar	a	Função	Objetivo	de	minimizar	para	maximizar	e	trocar	o	seu	sinal,	pois	minimizar	
uma	função	equivale	a	maximizar	sua	simétrica;
•	 mudar	a	maneira	de	calcular	a	linha	de	controle	da	primeira	solução	básica	(isso	será	explicado	no	
próximo	exemplo);
61
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Pesquisa OPeraciOnal
•	 a	variável	que	entrará	na	base	seguinte	é	aquela	da	coluna	que	apresentar	maior	valor	positivo	na	
linha	de	controle	(perceba	que	é	o	procedimento	oposto	ao	problema	de	maximização);
•	 a	 variável	que	 sairá	da	base	é	aquela	que	apresentar	o	menor	 valor	não	negativo	na	 coluna	 termo	
independente dividido pela coluna de trabalho (outra alteração em relação ao problema de maximização).
Explicaremos esse cálculo utilizando um exemplo apresentado pelo professor José Celso Contador (1998):
Um fabricante de ração deseja produzir um determinado tipo de ração, conforme especificação do 
Ministério da Agricultura, e pelo mínimo custo. O Ministério especifica apenas quatro nutrientes A, B, C 
e D, exigindo que um quilo de ração contenha:
•	 no	mínimo,	120g	do	nutriente	A;
•	 no	mínimo,	360g	do	nutriente	B;
•	 no	máximo,	360g	do	nutriente	C;
•	 exatamente	180g	do	nutriente	D.
O fabricante dispõe de três alimentos: milho, alfafa e silagem. E cada quilo desses alimentos contém 
os seguintes pesos em quilos dos nutrientes:
Tabela 21
Nutriente Milho Alfafa Silagem
A 0,1 0,2 0,1
B 0,4 0,4 0,3
C 0,2 0,2 0,1
D 0,1 0,2 0,1
Outros 0,2 0,4
Total 1,0 1,0 1,0
Sabendo‑se	que	o	quilo	do	milho	custa	$	0,50,	o	da	alfafa	$	0,20	e	o	da	silagem	$	0,10,	determinar	
qual a mistura que proporciona mínimo custo da ração especificada.
a) Modelagem do problema
Representaremos as quantidades num quilo de ração de milho, alfafa e silagem, respectivamente, 
pelas letras x, y e z.
A Função Objetivo, portanto, será:
Custo	da	ração	=	0,5x	+	0,2y	+	0,1z
62
Unidade III
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
É	evidente	que	nosso	objetivo	é	minimizar	o	valor	do	custo	da	ração;	portanto,	devemos	determinar	
os valores de x, y e z que resultem no menor custo possível (a solução ótima).
Esse cálculo, no entanto, só tem sentido à luz das restrições, que são as seguintes:
Para	o	nutriente	A:	0,1x	+	0,2y	+	0,1z	≥	0,12	kg
Para	o	nutriente	B:	0,4x	+	0,4y	+	0,3z	≥	0,36	kg
Para	o	nutriente	C:	0,2x	+	0,2y	+	0,1z	≤	0,36	kg
Para	o	nutriente	D:	0,1x	+	0,2y	+	0,1z	=	0,18	kg
Os nutrientes que não são especificados não constituem restrição física, mas precisam ser mostrados 
numa equação para manter a lógica do sistema matemático. São as restrições lógicas:
Outros	nutrientes:	0,2x	+	0y	+	0,4z	≥	0	kg
Por último, é necessário que os três alimentos juntos (milho, alfafa e silagem) perfaçam um quilo:
x	+	y	+	z	=	1kg
Nesse ponto, precisamos fazer uma consideração. Trabalhar no Simplex com números fracionários 
não	é	recomendável.	Por	isso,	vamos	fazer	um	artifício	matemático:	multiplicar	as	inequações	por	10	(o	
que	não	as	altera)	e	posteriormente	os	termos	independentes	e	a	Função	Objetivo	por	10	também.	Esse	
último artifício afeta o resultado final, ou seja, quando chegarmos ao resultado, deveremos dividi‑lo por 
10,	voltando	à	situação	original.
Portanto, as inequações ficarão com os seguintes formatos:
Para	o	nutriente	A:	1x	+	2y	+	1z	≥	12	kg
Para	o	nutriente	B:	4x	+	4y	+	3z	≥	36	kg
Para	o	nutriente	C:	2x	+	2y	+	1z	≤	36	kg
Para	o	nutriente	D:	1x	+	2y	+	1z	=	18	kg
Outros	nutrientes:	2x	+	0y	+	4z	≥	0	kg
x	+	y	+	z	=	10kg
Perceba que existem algumas redundâncias que permitem eliminar inequações, o que é muito bom, 
porque simplificará os cálculos. As inequações para o nutriente A e para o nutriente D são redundantes. 
63
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Pesquisa OPeraciOnal
Ficaremos com a mais restritiva, ou seja, a inequação do nutriente D (se a inequação for igual a 18 será 
automaticamente	maior	do	que	12,	daí	a	redundância).
Outra redundância é a inequação para outros nutrientes. Também pode ser eliminada, pois se os 
valores de x, y e z têm que ser positivos, a inequação será automaticamente positiva.
Ficamos, assim, com quatro inequações:
Para	o	nutriente	B:	4x	+	4y	+	3z	≥	36	kg
Para	o	nutriente	C:	2x	+	2y	+	1z	≤	36	kg
Para	o	nutriente	D:	1x	+	2y	+	1z	=	18	kg
x	+	y	+	z	=	10kg	
b) Modelo formal
Lembre‑se de que para transformar uma inequação do tipo ≤ em equações, é necessário introduzir 
uma variável de folga. Como já definido anteriormente, variável de folga ou residual é uma variável não 
negativa somada ao lado esquerdo da desigualdade e numericamente igual à diferença entre o termo 
independente e os valores à esquerda da desigualdade. Corresponde, numa determinada solução, à 
parcela não aproveitada dos recursos. Simbolizaremos essas variáveis como Ri.
Já para transformar as inequações do tipo ≥ em equações, é necessário introduzir uma variável de 
excesso. Como já definido anteriormente, variável de excesso é uma variável não negativa, subtraída do 
lado esquerdo da desigualdade e numericamente igual à diferença entre o valor do termo independente 
e o valor das variáveis que estão à esquerda da desigualdade. Simbolizaremos essas variáveis como Ei.
Além dessas duas variáveis, é necessário introduzir variáveis artificiais, que são variáveis adicionadas 
à esquerda em todas as restrições que não contenham uma variável de folga, sendo utilizadas,portanto, 
nas restrições que têm originalmente o sinal ≥ ou =. Como vimos, a variável artificial é necessária 
porque, na solução inicial do Simplex, são igualadas a zero todas as variáveis de entrada e de excesso, o 
que corresponde a fazer as variáveis de folga e as artificiais iguais ao termo independente, em cada uma 
das equações na qual a variável aparece. Simbolizaremos as variáveis artificiais como Ai.
Feitas essas considerações, teremos as seguintes equações para serem trabalhadas no Simplex:
Para	o	nutriente	B:	4x	+	4y+	3	z	–E1	+	A1	=	36	kg
Para	o	nutriente	C:	2x	+	2y	+	1z	+	R2	=	36	kg
Para	o	nutriente	D:	1x	+	2y	+	1z	+	A3	=	18	kg
x	+	y	+	z	+	A4	=	10kg
64
Unidade III
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Usando o problema, vamos tentar entender o significado da variável de excesso. A especificação 
da	 ração	 estabelece	que	 ela	 deve	 conter	no	mínimo	360	gramas	do	nutriente	B	por	 quilo.	 Como	o	
fabricante pode oferecer um valor maior, a variável de excesso representa a quantidade de nutriente B 
que	exceder	os	360	gramas.
A	Função	Objetivo	passa	a	ter	a	seguinte	forma,	considerando	a	multiplicação	por	10,	como	orientado	
anteriormente:
min⁡(5x	+	2y	+	1z	+	0R2	+	0E1	+	MA1	+	MA2	+	MA3) 
Da forma como foi apresentado, o Simplex é um algoritmo de maximização. Como o exemplo é de 
minimização, utilizaremos o mesmo procedimento, mas trocaremos o sinal da Função Objetivo, pois 
minimizar uma função corresponde a maximizar a função simétrica dela:
max⁡(–	5x	–	2y	–	1z	–	0R2	–	⁡0E1	–	MA1	–	MA2	–	MA3)
Resumindo, o modelo formal desse problema de ração é:
max⁡(–	5x	–	2y	–	1z	–	0R2	–	⁡0E1	–	MA1	–	MA2	–	MA3)
Submetido às restrições:
4x	+	4y	+	3z	–	1E1	+	0R2	+	1A1	+	0A3	+	0A4	=	36	kg
2x	+	2y	+	1z	+	0E1	+	1R2	+	0A1	+	0A3	+	0A4	=	36	kg
1x	+	2y	+	1z	+	0E1	+	0R2	+	0A1	+	1A3	+	0A4	=	18	kg
1x	+	1y	+	1z	+	0E1	+	0R2	+	0A1	+	0A3	+	1A4	=	10	kg
Vemos, então, que todas as variáveis são não negativas (positivas ou zero).
c) Montagem do Simplex
Estabelecidas as equações, podemos montar o Simplex passo a passo:
O simplex terá as seguintes colunas:
Tabela 22
Base
Função 
objetivo
Variável de 
entrada
Variável 
Residual/
Excesso
Variável 
artificial Termo 
independente
Controle
Termo 
indepen-
dente 
dividido 
pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
–5 –2 –1 0 0 –M –M –M Coeficiente 
da função 
objetivo
Valor da 
função 
objetivox y z E1 R2 A1 A2 A4 b
65
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Pesquisa OPeraciOnal
1º passo: variáveis da primeira base
A primeira base (primeira tentativa) é constituída pelas variáveis residuais e pelas artificiais, e seu 
valor é igual ao respectivo termo independente. Os coeficientes das equações são colocados nos locais 
adequados, conforme já fizemos anteriormente.
Tabela 23
Base
Função 
objetivo
Variável de 
entrada
Variável 
Residual/
Excesso
Variável 
artificial Termo 
independente
Controle Termo indepen-
dente 
dividido 
pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
–5 –2 –1 0 0 –M –M –M Coeficiente 
da função 
objetivo
Valor da 
função 
objetivox y z E1 R2 A1 A2 A4 b
A1 4 4 3 –1 0 1 0 0 36 –M
R2 2 2 1 0 1 0 0 0 36 –O
A3 1 2 1 0 0 0 1 0 18 –M
A4 1 1 1 0 0 0 0 1 10 –M
Controle
2º passo: linha de controle
A linha de controle da primeira base é obtida pela soma dos produtos dos coeficientes da 
respectiva coluna pelos valores da coluna Função Objetivo, menos o valor do coeficiente da 
variável da coluna na Função Objetivo (isso é um produto matricial, cujos detalhes matemáticos 
não fazem parte do nosso programa). Veja a seguir:
na	coluna	da	variável	x:	[4(–	M)	+	2(0)	+	1(–	M)	+	1(–	M)]	–	(–	5)	=	(5	–	6M)
na	coluna	da	variável	y:	[4(–	M)	+	2(0)	+	2(–	M)	+	1(–	M)]	–	(–	2)	=	(2	–	7M)
na	coluna	da	variável	z:	[3(–	M)	+	1(0)	+	1(–	M)	+	1(–	M)]	–	(–	1)	=	(1	–	5M)
na coluna da variável E1:	[	–	1(–	M)	+	0(0)	+	0(–	M)	+	0(–	M)]	–	(0)	=	(M)
Nas demais colunas, esses cálculos resultarão zero. Veja a seguir:
66
Unidade III
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Tabela 24
Base
Função 
objetivo
Variável de entrada
Variável 
Residual/
Excesso
Variável 
artificial
Termo 
indepen-
dente
Controle
Termo 
indepen-
dente 
dividido 
pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
–5 –2 –1 0 0 –M –M –M Coeficiente 
da função 
objetivo
Valor da 
função 
objetivox y z E1 R2 A1 A2 A4 b
A1 4 4 3 –1 0 1 0 0 36 –M
R2 2 2 1 0 1 0 0 0 36 –O
A3 1 2 1 0 0 0 1 0 18 –M
A4 1 1 1 0 0 0 0 1 10 –M
Controle 5‑6M 2‑7M 1‑5M M 0 0 0 0
A coluna Valor da FO (Função Objetivo) é obtida pela multiplicação da coluna Termo 
Independente pela coluna Coeficiente da Função Objetivo. O valor na linha de controle é a soma 
desses produtos.
36(–M)	+	36(0)	+	18(–M)	+	10(–M)=	–	64M
Em outras palavras, esse valor é aquele da primeira solução básica, obtida diretamente na 
Função Objetivo. Como, numa solução básica, as variáveis que não estão na base são iguais 
a zero e as outras são iguais aos respectivos termos independentes, a Função Objetivo acaba 
reduzida à expressão anterior. Veja a seguir se fizéssemos pela Função Objetivo, como o 
resultado seria idêntico:
–	5(0)	–	2(0)	–	1(0)	–	0RA	–	0E1	–	36M	–	18M	–	10M=	–64M
Nesse momento do cálculo, a planilha do Simplex estará assim:
Tabela 25
Base
Função 
objetivo
Variável de entrada
Variável 
Residual/
Excesso
Variável 
artificial
Termo 
indepen-
dente
Controle
Termo 
indepen-
dente 
dividido 
pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
–5 –2 –1 0 0 –M –M –M Coeficiente 
da função 
objetivo
Valor da 
função 
objetivox y z E1 R2 A1 A2 A4 b
A1 4 4 3 –1 0 1 0 0 36 –M –36M Entra
R2 2 2 1 0 1 0 0 0 36 –O –0
A3 1 2 1 0 0 0 1 0 18 –M –18M Sai
A4 1 1 1 0 0 0 0 1 10 –M –10M
Controle 5‑6M 2‑7M 1‑5M M 0 0 0 0 –64M –64M
67
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Pesquisa OPeraciOnal
3º passo: variável que entrará na base seguinte
É aquela da coluna que apresentar o maior valor negativo na linha de controle. No nosso exemplo, 
será a variável Y.
Tabela 26
Base
Função 
objetivo
Variável de entrada
Variável 
Residual/
Excesso
Variável 
artificial
Termo 
indepen-
dente
Controle
Termo 
indepen-
dente 
dividido 
pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
–5 –2 –1 0 0 –M –M –M Coeficiente 
da função 
objetivo
Valor da 
função 
objetivox y z E1 R2 A1 A2 A4 b
A1 4 4 3 –1 0 1 0 0 36 –M –36M Entra
R2 2 2 1 0 1 0 0 0 36 –O –0 y
A3 1 2 1 0 0 0 1 0 18 –M –18M Sai
A4 1 1 1 0 0 0 0 1 10 –M –10M
Controle 5‑6M 2‑7M 1‑5M M 0 0 0 0 –64M –64M
4º passo: variável que vai sair da base
Será a que apresentar o menor valor não negativo na coluna termo independente dividido pela 
coluna de trabalho. Vale lembrar que é necessário calcular a coluna de trabalho, que é aquela coluna de 
divisão correspondente à variável que entrará.
Tabela 27
Base
Função 
objetivo
Variável de entrada
Variável 
Residual/
Excesso
Variável 
artificial
Termo 
indepen-
dente
Controle
Termo 
indepen-
dente 
dividido 
pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
–5 –2 –1 0 0 –M –M –M Coeficiente 
da função 
objetivo
Valor da 
função 
objetivox y z E1 R2 A1 A2 A4 b
A1 4 4 3 –1 0 1 0 0 36 –M–36M Entra
R2 2 2 1 0 1 0 0 0 36 –O –0 y
A3 1 2 1 0 0 0 1 0 18 –M –18M Sai
A4 1 1 1 0 0 0 0 1 10 –M –10M
Controle 5‑6M 2‑7M 1‑5M M 0 0 0 0 –64M –64M
Está encerrada a primeira base. Como fizemos no exercício das CPUs, repetiremos as tentativas 
(bases) até que só restem números não negativos na linha de controle. Veja como ficaram os cálculos 
nesse exemplo:
68
Unidade III
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Tabela 28
Base
Função 
objetivo
Variável de entrada
Variável 
Residual/
Excesso
Variável artificial
Termo 
inde-
pen-
dente
Controle
Termo 
indepen-
dente 
dividido 
pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
–5 –2 –1 0 0 –M –M –M Coeficiente 
da função 
objetivo
Valor da 
função 
objetivox y z E1 R2 A1 A2 A4 b
A1 4 4 3 –1 0 1 0 0 36 –M –36M Entra
R2 2 2 1 0 1 0 0 0 36 –0 –0 y
A3 1 2 1 0 0 0 1 0 18 –M –18M Sai
A4 1 1 1 0 0 0 0 1 10 –M –10M
Controle 5‑6M 2‑7M 1‑5M M 0 0 0 0 –64M –64M
Y 1 1 3/4 –1/4 0 1/4 0 0 9 –2 –18 –36 Entra 
R2 0 0 –1/2 –1/2 1 –1/2 0 0 18 –0 0 36 E1
A3 –1 0 –1/2 1/2 0 –1/2 1 0 0 –M 0 0 Sai
A4 0 0 1/4 1/4 0 –1/4 0 1 1 –M –M 4 A3
Controle 3+M 0 (M‑2)/4 (2‑3M)/4 0 (7M–2)/4 0 0 –18–M
Y 1/2 1 1/2 0 0 0 1/2 0 9 –2 –18 18 Entra
R2 1 0 0 0 1 0 –1 0 18 0 0 ∞ Z
E1 –2 0 –1 1 0 –1 2 0 0 0 0 –0 Sai
A4 0 0 1/2 0 0 0 –1/2 1 1 –M –M 2 A3
Controle (8+M)+2 0 –M/2 0 0 M –1+1,5M 0 –18–M –18–M
Y 0 1 0 0 0 0 1 –1 8 –2 –16
R2 1 0 0 0 1 0 –1 0 18 0 0
E1 –1 0 0 1 0 –1 1 2 2 0 0
A4 1 0 1 0 0 0 –1 2 2 –1 –2
Controle 4 0 0 0 0 M M–1 M –18 –18
Dessa forma, a solução do problema é a seguinte:
FO	=	18	(custo	mínimo	=	5	x	0	+	2	x	8	+1	x	2	=18),	considerando	que	x	=	0;	y	=	8	e	z	=	2.	A	variável	de	
folga E1	será	igual	a	2	(sobra	2);	a	variável	de	excesso,	igual	a	18,	e	as	artificiais,	logicamente	iguais	a	zero.
Observe, no entanto, que a solução anterior é matemática. Para trabalharmos com números inteiros, 
multiplicamos	os	termos	independentes	e	a	Função	Objetivo	por	10;	agora,	para	voltarmos	ao	original,	
devemos	dividir	por	10:
69
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Pesquisa OPeraciOnal
A ração será, por quilo, composta de:
x	=	0	kg	de	milho;
y	=	0,8	kg	de	alfafa;
z	=	0,2	kg	de	silagem.
E	o	custo	da	ração	será	de:	(0,8	kg	de	alfafa	a	$	0,20	por	kg)	=	(0,2	kg	de	silagem	a	$0,10	por	kg)	=	
1,8	por	kg	de	ração.
7.2 solução computacional
No exemplo das CPUs, vimos a resolução computacional de um problema de maximização da Função 
Objetivo. Muitos casos práticos envolvem um problema de minimização, ou seja, uma situação em que 
queremos que a Função Objetivo assuma o menor valor possível. Nesses casos, pelo menos uma das 
restrições é do tipo ≥.
Como anteriormente, vamos usar um exemplo para explicar os cálculos envolvidos, mas desta vez 
vamos nos concentrar na solução computacional, hoje em dia muito mais adequada e amplamente 
utilizada.
Vamos imaginar a seguinte situação:
Um	investidor	tem	R$	850.000,00	para	aplicar	no	mercado	financeiro,	podendo	escolher	entre	duas	
opções: um fundo de ações e um fundo de renda fixa.
Cada	quota	do	fundo	de	ações	custa	R$	160,00	e	proporciona	uma	taxa	de	retorno	de	9%.	
Por	outro	ladro,	cada	quota	do	fundo	de	renda	fixa	custa	R$	215,00	e	proporciona	uma	taxa	de	
retorno	de	5%.
O	objetivo	do	cliente	é	minimizar	o	risco,	mas	pretende	obter	o	retorno	de	pelo	menos	R$	48.000,00.
Para	aquisição	de	uma	quota,	o	fundo	de	ações	apresenta	um	índice	de	risco	igual	a	5,	enquanto	
uma	quota	do	fundo	de	renda	fixa	apresenta	um	índice	de	risco	igual	a	2.
O	último	desejo	do	cliente	é	que	pelo	menos	650	quotas	do	fundo	de	renda	fixa	sejam	adquiridas.
O que se deseja é determinar quantas quotas de cada um dos investimentos disponíveis devem ser 
adquiridas, para que se atinja o objetivo de minimizar o índice de risco total da carteira desse investidor.
Perceba que o processo de cálculo é semelhante aos casos de maximização. A grande diferença 
está no equacionamento matemático de uma e da outra situação. Quando utilizamos os recursos 
computacionais, essa diferença fica muito mais minimizada.
70
Unidade III
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
As variáveis de entrada ou variáveis de decisão são:
x1	=	quantidade	de	quotas	do	fundo	de	ações;
x2 = quantidade de quotas do fundo de renda fixa.
Desse modo, a Função Objetivo fica sendo:
Risco	total	da	carteira	=	5x1	+	2x2
Essa Função Objetivo deve ser evidentemente minimizada.
As restrições são as seguintes:
Os	recursos	disponíveis	para	aplicação	são	de	R$	850.000,00.	Considerando	o	valor	das	quotas	de,	
respectivamente,	R$	160,00	e	R$	215,00,	a	primeira	restrição	do	problema	será:
160x1	+	215x2	=	850.000
O	cliente	espera	um	retorno	de	no	mínimo	R$	48.000,00.	Como	as	taxas	de	retorno	são	9%	e	5%,	
sobre	cotas	de	valor,	respectivamente,	de	R$	160,00	e	R$	215,00,	a	segunda	restrição	do	problema	será:
(0,09×160)x1	+	(0,05×215)x2 ≥	25.000
O	cliente	deseja	que	sejam	adquiridas	no	mínimo	650	quotas	de	renda	fixa.	Isso	define	mais	uma	
restrição:
x2 ≥	650
Estabelecido o equacionamento matemático, podemos montar no Excel a planilha com os dados 
necessários para utilizar o Solver. A planilha ficaria com o seguinte aspecto:
Figura	24
71
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Pesquisa OPeraciOnal
As fórmulas são as seguintes:
Tabela 29
Células Fórmulas
B6 =B4*B5
C6 =C4*C5
D6 =SOMA(B6:C6)
B10 =B5*B9
C10 =C5*C9
D10 =SOMA(B10:C10)
B12 =B5*B9*B11
C12 =C5*C9*C11
D12 =SOMA(B12:C12)
C13 =C5
Observe	que	as	células	B5	a	C5,	que	receberão	as	quantidades	a	serem	adquiridas	de	quotas,	são	
inicialmente preenchidas com zeros.
Montada a planilha com as informações de entrada e as restrições, podemos acessar o Solver, 
informando os dados necessários. Observe que, nesse caso, no parâmetro Igual a: optamos pela opção 
Mín, mostrada no quadro Parâmetros do Solver.
Não nos esqueçamos também de, em Opções, selecionarmos: Presumir modelo linear, Presumir não 
negativos e Usar escala automática.
As figuras a seguir mostram as seleções feitas:
Figura	25
72
Unidade III
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Figura	26
Clicando OK na tela de Opções do Solver e em seguida Resolver na tela de Parâmetros do Solver, 
obteremos a solução proposta pela ferramenta:
Figura	27
Ao aceitar a solução do Solver clicando OK, teremos os três relatórios já conhecidos:
Microsoft	Excel	12.0	–	Relatório	de	Resposta:
73
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Pesquisa OPeraciOnal
Figura	28
Microsoft	Excel	12.0	–	Relatório	de	Sensibilidade:
Figura	29
Microsoft	Excel	12.0	–	Relatório	de	Limites:
Figura	30
74
Unidade III
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
8 aPlicações tíPicas
Segundo Contador (1998), as aplicações da PL são diversas em todos os campos da Administração. 
Ele mostra, na lista a seguir, as principais aplicações descrevendo‑as em termos gerais:
•	 Planejamento da produção: determinar o plano de produção de mínimo custo ou de máximo 
lucro, partindo da previsão de vendas, da capacidade produtiva e de fatores reais de custos ou 
de lucro. É o caso do problema das CPUs. Importante mencionar que a PL só é aplicada nos casos 
emque a capacidade produtiva é menor que a demanda: se uma fábrica pode aumentar sua 
capacidade produtiva rapidamente, obviamente atenderá toda a demanda, e daí não precisará 
lançar mão da PL.
 saiba mais
Veja o valor do planejamento em logística, transporte e deslocamentos 
assistindo ao filme O Resgate do Soldado Ryan, que apresenta aspectos 
práticos interessantes desse processo.
•	 Dosagem; mistura e dieta: aplicada à preparação de produtos a partir da mistura de 
ingredientes, objetivando minimizar o custo para uma demanda específica do produto 
final. É célebre o estudo feito nos Estados Unidos sobre mistura de diversos componentes 
para obter, ao mínimo custo, gasolina com determinada especificação. É o caso também da 
fabricação de ligas metálicas a partir de minérios, levando em consideração, além dos custos, 
certas restrições relativas ao percentual de impurezas. Problema de dieta de mínimo custo 
para seres humanos e animais é outra aplicação: conhecendo as quantidades necessárias de 
nutriente, a composição nutritiva de cada alimento e os custos respectivos, determina‑se a 
dieta de menor custo.
•	 Alocação de recursos: como organizar a distribuição de recursos (materiais, mão de obra, 
equipamentos, capitais) para maximizar a produção ou o lucro. Aplicação característica é a da 
produção agrícola: em quais tipos de cultura (milho, soja, cana‑de‑açúcar) aplicar os recursos 
limitados de terra, máquinas agrícolas, homens, dinheiro para obter máximo lucro, podendo levar 
em consideração limitações na capacidade de comercializar safras e incluir rotações de cultura 
durante o ano.
•	 Armazenamento:	 para	 produto	 de	 demanda	 sazonal	 (cerveja,	 por	 exemplo);	 quanto	 produzir	
para estocar em armazém de capacidade limitada durante o período de baixa demanda e quanto 
produzir em horas extras no período de alta demanda, para minimizar o custo ou maximizar o 
lucro.
•	 Análise posicional: é possível determinar a melhor dentre as várias localizações possíveis para 
depósitos, fábricas ou distribuidores, com base nos vários fatores relativos a cada localização.
75
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Pesquisa OPeraciOnal
•	 Avaliação de cargos e salários: pode‑se utilizar a programação linear em substituição à análise 
de regressão múltipla para determinar os pesos relativos dos fatores considerados na avaliação de 
salários e de cargos. Análise semelhante pode ser aplicada a qualquer situação experimental para 
obter melhor avaliação em suas linhas gerais.
•	 Transporte: foi o problema que primeiro motivou o desenvolvimento da PL. Conhecida a demanda 
de certo produto distribuído em vários locais e conhecidas a disponibilidade de vários depósitos, 
a capacidade e os custos dos diversos modais de transporte (trem, navio, caminhão, avião), é 
possível determinar qual depósito deverá atender cada um dos destinos e qual a quantidade a 
ser transportada, de modo a minimizar custos. Aplicam‑se também nos casos de transbordos em 
armazéns intermediários, abastecidos por meios de transporte de longa distância e que abastecem 
lojas ou armazéns urbanos por meio de caminhões leves. Esse problema, apesar de poder ser resolvido 
pelo Simplex, possui métodos especiais de solução conhecidos por métodos de transporte.
•	 Designação e atribuição de tarefas: nas situações em que um grande número de tarefas precisa 
ser executado por um grupo de máquinas ou pessoas diferentes, é possível determinar qual a 
melhor	atribuição	de	tarefas	entre	as	máquinas	e/ou	pessoas,	de	modo	a	minimizar	o	tempo	total	
para produzir uma mesma quantidade.
 resumo
Um estudo de PO consiste em construir um modelo da situação física. 
Um modelo de PO é definido como uma representação idealizada de um 
sistema organizacional. Esse sistema pode já ser existente ou ainda ser 
uma ideia à espera de execução. No primeiro caso, o objetivo do modelo 
é analisar as operações do sistema para verificar sua performance. No 
segundo, o objetivo é identificar a melhor estrutura do futuro sistema.
A complexidade de um sistema real resulta do grande número de 
variáveis que comandam as operações do sistema, embora um sistema 
real possa envolver um número substancial de variáveis, geralmente 
uma pequena fração dessas variáveis domina as operações do sistema. 
Então, a simplificação do sistema real, em termos de um modelo 
condensado, identificando apenas as variáveis dominantes e as relações 
entre elas, é o empregado.
 exercícios
Questão 1. O modelo matemático utilizado na programação linear é um sistema de equações e 
inequações. As inequações podem ser transformadas em equações por meio da introdução de variáveis 
diversas. Sobre isso, foram feitas as afirmações:
76
Unidade III
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
I	–	Um	sistema	de	equações	só	é	determinado	quando	a	quantidade	de	incógnitas	é	igual	à	quantidade	
de equações.
II	–	Uma	variável	de	folga	ou	residual	é	utilizada	quando	a	desigualdade	for	do	tipo	≤;	é	uma	variável	
não	negativa	somada	ao	lado	esquerdo	da	desigualdade;	é	numericamente	igual	à	diferença	entre	o	
termo independente e os valores à esquerda da desigualdade.
III	–	A	solução	de	um	sistema	indeterminado	é	obtida	atribuindo‑se	valor	zero	para	(n‑m)	incógnitas	
sendo m o número de equações e n o de incógnitas, em sucessivas tentativas de obter a solução ótima.
IV	–	No	Simplex,	a	primeira	solução	básica	é	obtida	igualando	a	zero	todas	as	variáveis	de	entrada.
São corretas as afirmativas:
A) I, II e III.
B) I, II e IV.
C) I, III e IV.
D) II, III e IV.
E) Todas são corretas.
Resposta correta: alternativa A.
Análise da alternativa
Justificativa: no Simplex, a primeira solução básica é obtida igualando a zero não somente as variáveis 
de entrada, mas, sim, a quantidade de variáveis decorrentes da subtração do número de incógnitas pelo 
número de equações.
77
REFERêNCiAS BiBliogRáFiCAS
Audiovisuais
GÊNIO	indomável.	Dir.	Gus	Van	Sant.	USA:	Miramax	Films,	1997.	126	minutos.
NÁUFRAGO.	Dir.	Robert	Zemeckis.	USA:	Twentieth	Century	Fox	Film	Corporation,	2000.	143	minutos.
O	RESGATE	do	soldado	Ryan.	Dir.	Steven	Spielberg.	USA:	DreamWorks	SKG,	1998.	169	minutos.
Textuais
ANDRADE, E. L. Introdução à pesquisa operacional: métodos e modelos para análise de decisões. São 
Paulo:	LTC,	2009.
BARBOSA,	M.	A.;	ZANARDINI,	R.	A.	D.	Iniciação à pesquisa operacional no ambiente de gestão. 
Curitiba:	IBPEX,	2010.
BRONSON, R. Pesquisa operacional e estatística.	São	Paulo:	McGraw‑Hill,	1995.
CONTADOR, J. C. Alguns modelos da pesquisa operacional. São Paulo: UNIP, 1998.
CORRAR,	L.	J.;	THEÓPHILO,	C.	R.	Pesquisa operacional para decisão em contabilidade e administração. 
São	Paulo:	Atlas,	2011.
EHRLICH,	P.	J.	Pesquisa operacional: curso	introdutório.	7.	ed.	São	Paulo:	Atlas,	1991.
HILLIER,	F.	S.;	LIEBERMAN,	G.	J.	Introdução à pesquisa operacional.	Porto	Alegre:	AMGB,	2013.
LACHTERMACHER,	G.	Pesquisa operacional na tomada de decisões.	São	Paulo:	Pearson	Prentice	Hall,	
2009.
MENDES,	H.	Modelagem e formas de representação de problemas.	2013.	Disponível	em:	<http://prezi.
com/71sowsklb6gp/modelagem‑e‑formas‑de‑representacao‑de‑problemas/>.	Acesso	em:	2	abr.	
2013.
SILVA, E. M. et al. Pesquisa operacional para os cursos de administração e engenharia.	4.	ed.	São	Paulo:	
Atlas,	2010.
SOCIEDADE BRASILEIRA DE PESQUISA OPERACIONAL. Pesquisa operacional.	2010.	Disponível	em:	
<http://www.sobrapo.org.br/o_que_e_po.php>.	Acesso	em:	2	abr.	2013.
TAHA,	H.	A.	Pesquisa operacional.	8.	ed.	São	Paulo:	Pearson	Prentice	Hall,	2008.
78
79
80
Informações:
www.sepi.unip.br ou 0800 010 9000