Pesquisa Operacional Unid II

Prévia do material em texto

25
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
Unidade II
Programação Linear
A Programação Linear (PL) é, segundo Contador (1998), um dos mais nobres modelos da Pesquisa 
Operacional. Dos modelos da Pesquisa Operacional aos problemas organizacionais, a Programação 
Matemática é responsável por cerca de 60%. Desse percentual, grande parte deve‑se à PL.
O objetivo desta unidade, portanto, é apresentar a PL, de maneira prática e utilitária, evitando 
conceituações matemáticas mais elaboradas. Contador (1998) estima que um curso de PL medianamente 
avançado cumpre um total de 45 horas efetivas de aula, ou seja, um semestre de três horas‑aulas 
semanais, o que não nos é disponibilizado, motivo pelo qual não nos aprofundaremos nas considerações 
matemáticas mais complexas.
5 modeLagem do ProbLema
Para apresentar os conceitos da Programação Linear, utilizaremos um exercício adaptado, apresentado 
originalmente pelo professor Contador (1998), a partir dos trabalhos do professor Zaccarelli, cujo 
enunciado é o seguinte:
Uma fábrica produz CPUs de dois tamanhos diferentes, grandes e pequenas, que apresentam lucros 
unitários de respectivamente $500 e $200. Ela deseja saber quantas unidades de cada um desses 
aparelhos deverá fazer para que o lucro obtido pela operação seja máximo.
As capacidades de produção da fábrica são as seguintes:
•	 6	gabinetes	grandes	por	hora;
•	 15	gabinetes	pequenos	por	hora;
•	 24	placas‑mãe	por	hora;
•	 20	placas	de	vídeo	por	hora;
Cada CPU grande é composta por:
•	 1	gabinete	grande;
•	 3	placas‑mãe;
•	 2	placas	de	vídeo;
26
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Cada CPU pequena é composta por:
•	 1	gabinete	pequeno;
•	 1	placa‑mãe;
•	 1	placa	de	vídeo;
Podemos resumir esses dados na seguinte tabela:
Tabela 1
Componentes Cpu grande Cpu pequena produção horária
Gabinete grande 1 6
Gabinete pequeno 1 15
Placa‑mãe 3 1 24
Placa de vídeo 2 1 20
Modelar o problema significa definir:
•	 as	variáveis	de	entrada;
•	 a	Função	Objetivo;
•	 as	restrições,	para,	a	partir	delas,	montar	um	sistema	de	equações	e	inequações.
No nosso caso temos:
Variáveis de entrada = o número de CPUs a serem produzidas, ou seja:
x1 = número de CPUs grandes a serem montadas.
x2 = número de CPUs pequenas a serem produzidas.
O	objetivo	é	maximizar	o	lucro,	portanto	a	Função	Objetivo	é:
FO	=	lucro	=	500x1 + 200x2
As restrições são relativas à capacidade produtiva de cada componente:
gabinete grande: x1 ≤ 6
gabinete pequeno: x2 ≤ 15
placas‑mãe:	3x1 + x2 ≤ 24
placas de vídeo: 2x1 + x2 ≤ 20
27
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
Evidentemente, o modelo de PL impõe outra restrição lógica, pois não se pode produzir uma 
quantidade negativa de CPUs;	portanto:
x1 ≥ 0 e x2 ≥ 0
Os valores de x1 e x2 que maximizam o lucro dessa operação serão obtidos pela resolução desse 
sistema de equações e inequações, ou seja, os valores que atendem simultaneamente a todas elas.
Existem alguns métodos de solução:
•	 Método	Gráfico,	aplicável	a	problemas	com	duas	variáveis	de	entrada;
•	 Método	Simplex,	método	geral,	aplicável	a	problemas	com	qualquer	quantidade	de	variáveis	de	
entrada;
•	 Método	Computacional,	aplicável	a	um	tipo	específico	de	problema,	mas	com	qualquer	quantidade	
de variáveis de entrada.
6 TiPos de soLução
6.1 solução gráfica
A solução gráfica consiste em plotar todas as restrições em um único diagrama ortogonal no qual o 
eixo horizontal representará as quantidades produzidas de CPUs grandes e o eixo vertical, as quantidades 
produzidas de CPUs pequenas:
x2 = CPUs pequenas
x1 = CPUs grandes
121086420
10
5
15
20
25
Figura	1
28
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
 Lembrete
Sistema	de	Coordenadas	no	plano	cartesiano	ou	espaço	cartesiano	
é um esquema reticulado necessário para especificar pontos num 
determinado “espaço” com dimensões. Cartesiano é um adjetivo 
que se refere ao matemático francês e filósofo Descartes que, entre 
outras coisas, desenvolveu uma síntese da álgebra com a geometria 
euclidiana.
O plano cartesiano contém dois eixos perpendiculares entre si. A 
localização de um ponto P no plano cartesiano é feita pelas coordenadas 
do plano (abscissa e ordenada – x e y).
Nos quadrantes I e III, os sinas de x, y são os mesmos (+,+) e (‑,‑), 
respectivamente, já nos quadrantes II e IV, os sinas de x, y são opostos (‑,+) 
e (+,‑), respectivamente.
Observe que utilizaremos o primeiro quadrante do sistema cartesiano, ou seja, valores de 
ambos os eixos positivos. Isso porque não teria sentido a produção de uma quantidade negativa 
de CPUs. Assim, teoricamente, qualquer ponto nesse diagrama ortogonal seria solução para o 
nosso problema. No entanto, veremos que, devido às restrições, pouco a pouco reduziremos os 
resultados possíveis.
A primeira restrição é a dos gabinetes grandes: não é possível a produção de mais do que seis 
gabinetes por hora nem a produção de uma quantidade negativa de gabinetes, ou seja:
0 ≤ x1 ≤ 6
Graficamente, teríamos:
29
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
x2 = CPUs pequenas
gabinete grande: 
x1 > 0 e x1 < 6
x1 = CPUs grandes
121086420
10
5
15
20
25
Figura	2
Perceba que só podem ser aceitos como soluções para esse problema os pontos coordenados à 
esquerda da reta desenhada.
Restrição semelhante ocorre com os gabinetes pequenos:
0 ≤ x2 ≤ 15
x2 = CPUs pequenas
gabinete grande: 
x1 > 0 e x1 < 6
gabinete pequeno: 
x2 > 0 e x2 < 15
x1 = CPUs grandes
121086420
10
5
15
20
25
Figura	3
Perceba que só podem ser aceitos como soluções para esse problema os pontos coordenados abaixo 
da reta desenhada.
30
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Até esse momento, as restrições já reduziram as soluções possíveis aos pontos coordenados 
circunscritos pelos eixos e pelas duas retas desenhadas.
Em sequência, temos as restrições da quantidade de placas‑mãe produzidas, ou seja:
3x1 + x2 ≤ 24
Observe que, se x1 for igual a zero, x2 deverá ser menor ou igual a 24 para manter a inequação e, se 
x2 for igual a zero, x1 deverá ser menor ou igual a 8. Note as resoluções a seguir:
Em	3x1 + x2 ≤ 24, se x1	=	0,		tem‑se		3	×	0	+	x2 ≤ 24 → x2 ≤ 24
Em 3 24 0 3 0 24
24
3
81 2 2 1 1 1x x se x tem se x x x+ ≤ = − + ≤ → ≤ → ≤, ,
Portanto, a inequação tem dois pontos característicos pelos quais podemos traçar a reta que a 
caracteriza:	(0;	24)	e	(8;	0).	Graficamente	temos:
x2 = CPUs pequenas
gabinete grande: 
x1 > 0 e x1 < 6
gabinete pequeno: 
x2 > 0 e x2 < 15
3x1 + x2 < 24
x1 = CPUs grandes
121086420
10
5
15
20
25
Figura	4
Perceba que qualquer ponto coordenado à direita desta reta não é permitido, pois desobedeceria a 
inequação. Retiramos mais um “pedaço” do campo de soluções permitidas.
A	última	restrição	é	a	da	placa	de	vídeo.	Seguindo	o	mesmo	raciocínio	das	placas‑mãe,	determinamos	
a reta característica:
2x1 + x2 ≤	20;		se		x1 = 0 →	2	×	0	+	x2 ≤ 20→x2 → ≤ 20
2 20 0 2 0 20
20
2
101 2 2 1 2 2x x se x x x x+ ≤ = → + ≤ → ≤ → ≤;
31
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-05-
20
13
Pesquisa OPeraciOnal
Os	pontos	característicos	que	definem	a	reta	são	(0;20)	e	(10;8),	e	graficamente:
x2 = CPUs pequenas
gabinete grande: 
x1 > 0 e x1 < 6
gabinete pequeno: 
x2 > 0 e x2 < 15
2x1 + x2 < 20
3x1 + x2 < 24
x1 = CPUs grandes
121086420
10
5
15
20
25
Figura	5
Mais uma parte das soluções possíveis foi retirada, restando um polígono de soluções possíveis. Veja a seguir:
x2 = CPUs pequenas
gabinete grande: 
x1 > 0 e x1 < 6
gabinete pequeno: 
x2 > 0 e x2 < 15
2x1 + x2 < 20
3x1 + x2 < 24
x1 = CPUs grandes
121086420
10
5
15
20
25
A
B C
D
E
Figura	6
Qualquer ponto desta área sombreada (em amarelo) é solução para o problema, continuando a 
existir, portanto, infinitas soluções, mas somente uma delas apresenta lucro máximo.
É fácil entender qual é a solução ótima. Em cada lado do polígono, há um recurso que é utilizado ao 
máximo. Como num vértice há dois recursos utilizados ao máximo simultaneamente, a solução ótima 
estará num dos vértices do polígono. Este é o teorema fundamental da Programação Linear.
32
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Para ficar mais claro: no lado (aresta) definido pelos pontos BC, estamos produzindo o máximo 
possível de gabinetes. Já no ponto C, além de estarmos produzindo o máximo de gabinetes possíveis, 
estamos também produzindo o máximo possível de placas de vídeo.
Antes tínhamos infinitas soluções possíveis, mas com esse teorema restaram apenas seis soluções 
que podem ser ótimas e, por tentativas, podemos definir qual é essa solução ótima. Veja a tabela a 
seguir:
Tabela 2
VÉRTICE Cpu GRANDE Cpu pEQuENA LuCRO
x1 x2 500x1+200x2
A 0 0 0 + 0 = 0
B 0 15 0	+	3.000	=	3.000
C 2,5 15 1.250	+	3.000	=	4.250
D 4 12 200 + 2.400 = 4.400
E 5 6 3.000	+	1.200	=	4.200
F 5 0 3.000	+	0	=	3.000
Portanto, o ponto de máximo lucro é o ponto D. Consequentemente, deve‑se montar quatro CPUs 
grandes por hora e doze pequenas por hora, o que gerará um lucro de $ 4.400,00 por hora.
Para se atingir esse lucro máximo, serão produzidos:
•	 4	gabinetes	grandes	por	hora;
•	 12	gabinetes	pequenos	por	hora;
•	 24	placas‑mãe	por	hora;
•	 20	placas	de	vídeo	por	hora.
 observação
Sobrarão,	por	hora,	dois	gabinetes	grandes	e	três	pequenos.	Não	haverá	
sobras de placas‑mãe e placas de vídeo.
6.2 solução pelo algoritmo simplex
Perceba que esse processo gráfico tem muitas limitações, a começar pelo fato de que só pode ser 
usado	para	duas	variáveis	de	entrada.	Foi	necessário	o	desenvolvimento	de	um	método	mais	completo	
para	realizar	esses	cálculos,	que	é	conhecido	como	Simplex.
33
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
O	Método	Simplex,	ao	contrário	do	Método	Gráfico,	trabalha	com	equações,	e	não	com	inequações.	
Desse modo, as inequações devem ser transformadas em equações, e isso é feito com a adição de 
variáveis. Vamos, portanto, determinar as variáveis que podem aparecer em um problema desse tipo. 
Utilizaremos as definições estabelecidas por Contador (1998):
•	 Variável de entrada é a aquela que deve ser otimizada e surge naturalmente do enunciado do 
problema. No caso do exercício das CPUs, que continuaremos usar como exemplo, as variáveis de 
entrada são o número de CPUs grandes (x1) e o número de CPUs pequenas (x2).
•	 Termo independente é o valor numérico de uma restrição e, por convenção, é colocado à direita 
do sinal da inequação. No nosso exemplo, são as quantidade limitantes produzidas para cada 
componente.
•	 Variável de folga ou residual, utilizada quando a desigualdade for do tipo ≤, é uma variável não 
negativa, somado 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 de recursos. No nosso exemplo, são as eventuais sobras de 
componentes (gabinetes ou placas)
•	 Variável de excesso, utilizada quando a desigualdade for do tipo ≥, é uma variável 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. No nosso 
exemplo, não existirão valores desse tipo, pois é um problema de maximização.
•	 Variável artificial é uma variável adicionada à esquerda em todas as restrições que não contenham 
uma variável de folga, sendo utilizada, portanto, nas restrições que se apresentam originalmente 
com sinal ≥ ou =. A variável artificial é necessária porque a solução inicial	do	Simplex	é	obtida	
igualando a zero todas as variáveis de entrada e todas as de excesso, o que corresponde a fazer 
cada variável de folga e cada variável artificial igual ao valor do termo independente da equação 
da qual a variável em questão aparece. No nosso exemplo, não existem variáveis desse tipo, visto 
serem inequações do tipo ≤.
Dessa forma, no nosso exemplo, as inequações seriam transformadas em equações, da seguinte 
forma:
Inequações:
gabinete grande: x1 ≤ 6
gabinete pequeno: x2 ≤ 15
placas‑mãe:	3x1 + x2 ≤ 24
placas de vídeo: 2x1 + x2 ≤ 20
34
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Equações:
gabinete grande: 1x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 = 6
gabinete pequeno: 0x1 + 1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 15
placas‑mãe:	3x1 + 1x2 + 0x3 + 0x4 + 1x5 + 0x6 = 24
placas de video: 2x1 + 1x2 + 0x3 + 0x4 + 0x5 + 1x6 = 20
Importante notar que na frente de cada variável colocamos seu coeficiente correspondente, mesmo 
quando	não	há	necessidade,	por	ser	zero	ou	um.	Fizemos	isso,	para	evidenciar	os	coeficientes	que	serão	
utilizados	no	algoritmo	Simplex.
Esse equacionamento tem seis valores desconhecido (as incógnitas x1;	 x2;	 x3;	 x4;	 x5;	 x6) e apenas 
quatro equações (as relacionadas anteriormente). Logo, o sistema de equações é indeterminado, tem 
infinitas soluções viáveis, e não apenas uma. Lembre‑se de que, em Matemática, só conseguimos resolver 
um sistema de equações quando o número delas for igual ao número de incógnitas.
Nesse caso, portanto, temos infinitas soluções viáveis (as soluções mostradas na área hachurada do 
gráfico mostrado anteriormente).
A solução ótima será pesquisada atribuindo valores arbitrários a um número de incógnitas igual 
ao número total delas subtraído pelo número de equações. No nosso exemplo, atribuiremos valores 
arbitrários a duas incógnitas (resultado da subtração de seis incógnitas por duas equações).
Essa resolução exige conhecimentos matemáticos que de modo geral não são do domínio de alunos 
da	graduação	de	Administração;	por	conseguinte,	iremos	apresentá‑la	de	forma	descritiva,	utilizando	o	
problema das CPUs como ilustração e apresentando o método passo a passo.
1º passo: estabelecer a planilha do algoritmo
 Lembrete
Um algoritmo é uma sequência finita de instruções bem definidas e 
não	ambíguas;	cada	uma	delas	pode	ser	executada	mecanicamente	num	
período de tempo finito e com uma quantidade de esforço finita.
O conceito de algoritmo é frequentemente ilustrado pelo exemplo de 
uma receita culinária, embora muitos algoritmos sejam mais complexos. 
Eles podem repetir passos (fazer iterações) ou necessitar de decisões 
(tais como comparações ou lógica) até que a tarefa seja completada. Um 
algoritmo corretamente executado não resolverá um problema se estiver 
implementado incorretamente ou se não for apropriado ao problema.
35
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13Pesquisa OPeraciOnal
É uma planilha de diversas linhas e colunas, na qual é reservada uma coluna para cada variável e mais 
quatro colunas de cálculos. Acompanhe a planilha para o nosso exemplo e o significado de cada coluna:
Tabela 3
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
A coluna base contém as variáveis que estão sendo consideradas numa determinada tentativa. No 
nosso caso, teremos quatro variáveis em cada tentativa. Para as outras duas será atribuído o valor zero.
As seis colunas seguintes são reservadas para cada uma das variáveis envolvidas. No nosso caso as 
duas variáveis de entrada (x1 e x2) e as quatro variáveis residuais (x3, x4, x5 e x6).
A antepenúltima coluna é reservada para os termos independentes das equações (no nosso exercício 
as restrições de produção).
A penúltima coluna é destinada a receber uma divisão entre as variáveis independentes, e a coluna 
de trabalho (veremos essa coluna mais adiante, durante a descrição do processo).
A última coluna relacionará a variável que entrará e a que sairá na próxima tentativa.
Existe um conjunto de linhas reservadas para cada tentativa: uma linha para cada equação e uma 
linha de controle (no caso, denominada lucro, nosso objetivo).
Tabela 4
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
Gabinete 
grande x3
Gabinete 
pequeno x4
Placa‑mãe x5
Placa de 
vídeo x6
Controle/lucro
36
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
A planilha mostrada anteriormente está preparada para se atribuir o valor zero para as variáveis 
x1 e x2. É nossa primeira tentativa. Ao igualar as variáveis de entrada a zero, automaticamente 
igualamos as variáveis residuais ou de folga ao termo independente. Veja como exemplo a 
primeira equação:
Em x1 + x3 = 6, se x1 = 0, então x3 = 6
O mesmo ocorre nas demais equações e variáveis.
2ª passo: início do preenchimento da planilha
Colocamos em cada uma das linhas os coeficientes das equações citadas anteriormente. A tabela 
fica da seguinte forma:
Tabela 5
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
Gabinete 
grande x3 1 0 1 0 0 0 6
Gabinete 
pequeno x4 0 1 0 1 0 0 15
Placa‑mãe x5 3 1 0 0 1 0 24
Placa de 
vídeo x6 2 1 0 0 0 1 20
Controle/lucro
Na linha de controle, colocamos o lucro respectivo com sinal trocado, ou seja ‑500 para CPU grande, 
– 200 para CPU pequena e zero para as demais colunas:
37
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
Tabela 6
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
Gabinete 
grande x3 1 0 1 0 0 0 6
Gabinete 
pequeno x4 0 1 0 1 0 0 15
Placa‑mãe x5 3 1 0 0 1 0 24
Placa de 
vídeo x6 2 1 0 0 0 1 20
Controle/lucro –500 –200 0 0 0 0 0
Como dissemos, nessa primeira tentativa atribuímos valor zero às variáveis x1 e x2. Na segunda 
tentativa, entraremos na tabela com uma delas e sair com uma das que fizeram parte na primeira 
tentativa (x3, x4, x5 e x6). Isso é feito da seguinte maneira:
•	 localizar	 a	 coluna	 que	 apresentar	 o	maior	 valor	 negativo	 na	 linha	 de	 controle,	 no	 nosso	
caso a coluna x1, que apresenta o valor ‑500. Essa coluna passa a ser denominada coluna de 
trabalho (ela irá variar de tentativa para tentativa). Costuma‑se assinalar a coluna por um 
retângulo. Essa variável é a que entrará na próxima tentativa. Colocamos essa informação na 
última	coluna;
•	 dividir	 o	 termo	 independente	 pelo	 valor	 correspondente	 na	 coluna	 de	 trabalho.	 Na	 linha	 de	
gabinete grande, por exemplo, dividiremos 6 por 1, obtendo o valor 6 que será colocado na 
penúltima	coluna;
•	 a	variável	que	sairá	na	tentativa	seguinte	é	aquela	que	corresponder	à	linha	que	apresentar	
menor	valor	positivo	na	coluna	de	termo	independente;	no	exemplo,	o	valor	6	correspondente	
à variável x3;
•	 O	coeficiente	que	estiver	no	cruzamento	da	linha	que	sairá	com	a	coluna	de	trabalho	chama‑se	
pivô ou elemento pivotal e vai nos servir para os cálculos seguintes.
Veja como deve ficar a planilha:
38
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Tabela 7
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
Gabinete 
grande x3 1 0 1 0 0 0 6
Gabinete 
pequeno x4 0 1 0 1 0 0 15
Placa‑mãe x5 3 1 0 0 1 0 24
Placa de 
vídeo x6 2 1 0 0 0 1 20
Controle/lucro –500 –200 0 0 0 0 0
Coluna de 
trabalho
pivô
3º passo: determinação da tentativa seguinte
Para a segunda tentativa, substituiremos a linha x3 na base, dando lugar à linha x1 que deve entrar. 
Todas as outras linhas, inclusive a de controle, devem permanecer com a base inalterada.
Os valores da linha que entra são obtidos pela divisão dos valores da linha que sai pelo valor do pivô. 
Nesse caso, como o valor do pivô é 1, os valores permanecerão os mesmos.
Tabela 8
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
Gabinete 
grande x3 1 0 1 0 0 0 6 6 entra
Gabinete 
pequeno x4 0 1 0 1 0 0 15 ∞ x1
Placa‑mãe x5 3 1 0 0 1 0 24 8 sai
Placa de 
vídeo x6 2 1 0 0 0 1 20 10 x3
39
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
Controle/lucro –500 –200 0 0 0 0 0
CPU 
grande x1 1 0 1 0 0 0 6
Gabinete 
pequeno x4
Placa‑mãe x5
Placa de 
vídeo x6
Controle/lucro
Os valores das demais linhas, inclusive do termo independente, é obtido pela chamada regra do 
retângulo.
Antes de aprendermos a usar a regra do retângulo, notemos que nas colunas que também são 
linhas (no nosso exemplo, no momento, as colunas x1, x4, x5 e x6) aparecerão apenas números zero ou 
um. Quando uma coluna cruza com uma linha correspondente à mesma variável, o valor será um. Veja 
a seguir:
Tabela 9
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
Gabinete 
grandex3 1 0 1 0 0 0 6
Gabinete 
pequeno x4 0 1 0 1 0 0 15
Placa‑mãe x5 3 1 0 0 1 0 24
Placa de 
vídeo x6 2 1 0 0 0 1 20
Controle/lucro –500 –200 0 0 0 0 0
CPU 
grande x1 1 0 1 0 0 0 6
Gabinete 
pequeno x4 1
Placa‑mãe x5 1
Placa de 
vídeo x6 1
Controle/lucro
40
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
E, quando uma coluna cruza com uma linha correspondente a outra variável, o valor será zero. Veja 
novamente:
Tabela 10
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
Gabinete 
grande x3 1 0 1 0 0 0 6
Gabinete 
pequeno x4 0 1 0 1 0 0 15
Placa‑mãe x5 3 1 0 0 1 0 24
Placa de 
vídeo x6 2 1 0 0 0 1 20
Controle/lucro –500 –200 0 0 0 0 0
CPU 
grande x1 1 0 1 0 0 0 6
Gabinete 
pequeno x4 0 1 0 0
Placa‑mãe x5 0 0 1 0
Placa de 
vídeo x6 0 0 0 1
Controle/lucro 0 0 0 0
Apenas os valores das colunas referentes às variáveis que estão assumindo valor zero (que estão 
“fora”) e da coluna do termo independente é que deverão ser calculados pela regra do retângulo.
Para entendermos a regra do retângulo, utilizaremos o quadro a seguir, com as linhas e colunas 
numeradas à semelhança do Excel:
41
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
Tabela 11
A B C D E F G H I J K
1
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
2 Cpu grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
3 x1 x2 x3 x4 x5 x6 b
4
5 Gabinete grande x3 1 0 1 0 0 0 6
6 Gabinete pequeno x4 0 1 0 1 0 0 15
7 Placa‑mãe x5 3 1 0 0 1 0 24
8 Placa de vídeo x6 2 1 0 0 0 1 20
9 Controle/lucro –500 –200 0 0 0 0 0
10
11 CPU grande x1 1 0 1 0 0 0 6
12 Gabinete pequeno x4 0 1 0 0
13 Placa‑mãe x5 0 0 1 0
14 Placa de vídeo x6 0 0 0 1
15 Controle/lucro 0 0 0 0
Queremos calcular o valor da célula D12. Para isso, usaremos o retângulo definido pelo pivô 
(célula C5) e pelo valor correspondente anterior (célula D6). O valor pedido será obtido pela 
formulação:
Novo valor = Valor anterior – (produtos dos elementos da diagonal oposta) ÷ pivô
No nosso exemplo, seria:
D12	=	D6	–	(C6	×	D5)	÷	C5,	ou	seja,	1	–	(0	×	0)	÷	1	=	1
Para fixar esse conceito, façamos agora o cálculo do termo independente correspondente à 
placa‑mãe. Veja a tabela a seguir:
42
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Tabela 12
A B C D E F G H I J K
1
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
2 Cpu grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
3 x1 x2 x3 x4 x5 x6 b
4
5 Gabinete grande x3 1 0 1 0 0 0 6
6 Gabinete pequeno x4 0 1 0 1 0 0 15
7 Placa‑mãe x5 3 1 0 0 1 0 24
8 Placa de vídeo x6 2 1 0 0 0 1 20
9 Controle/lucro –500 –200 0 0 0 0 0
10
11 CPU grande x1 1 0 1 0 0 0 6
12 Gabinete pequeno x4 0 1 1 0 0
13 Placa‑mãe x5 0 0 1 0
14 Placa de vídeo x6 0 0 0 1
15 Controle/lucro 0 0 0 0
Observe, em amarelo, o retângulo definido, valor correspondente ao desejado na base anterior e o 
pivô. O cálculo é feito utilizando‑se a formulação vista, ou seja:
I13	=	I7	–	(C7	×	I5)	÷	C5,	ou		seja,	24	–	(3	×	6)	÷	1	=	6
Os demais valores são calculados de modo idêntico, ficando a planilha do seguinte modo:
43
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
Tabela 13
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
Gabinete 
grande x3 1 0 1 0 0 0 6 6 Entra
Gabinete 
pequeno x4 0 1 0 1 0 0 15 ∞ x1
Placa‑mãe x5 3 1 0 0 1 0 24 8 Sai
Placa de 
vídeo x6 2 1 0 0 0 1 20 10 x3
Controle/lucro –500 –200 0 0 0 0 0
CPU 
grande x1 1 0 1 0 0 0 6
Gabinete 
pequeno x4 0 1 0 1 0 0 15
Placa‑mãe x5 0 1 –3 0 1 0 6
Placa de 
vídeo x6 0 1 –2 0 0 1 8
Controle/lucro 0 –200 500 0 0 0 3.000
Repetimos então os cálculos feitos na tentativa anterior, passo a passo. O resultado será:
Tabela 14
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
Gabinete 
grande x3 1 0 1 0 0 0 6 6 Entra
Gabinete 
pequeno x4 0 1 0 1 0 0 15 ∞ x1
Placa‑mãe x5 3 1 0 0 1 0 24 8 Sai
Placa de 
vídeo x6 2 1 0 0 0 1 20 10 x3
Controle/lucro –500 –200 0 0 0 0 0
44
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
CPU 
grande x1 1 0 1 0 0 0 6 ∞ Entra
Gabinete 
pequeno x4 0 1 0 1 0 0 15 15 x2
Placa‑mãe x5 0 1 –3 0 1 0 6 6 Sai
Placa de 
vídeo x6 0 1 –2 0 0 1 8 8 x3
Controle/lucro 0 –200 500 0 0 0 3.000
Podemos partir então para a terceira tentativa, substituindo primeiro a linha de x5 por x2:
Tabela 15
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
Gabinete 
grande x3 1 0 1 0 0 0 6 6 Entra
Gabinete 
pequeno x4 0 1 0 1 0 0 15 ∞ x1
Placa‑mãe x5 3 1 0 0 1 0 24 8 Sai
Placa de 
vídeo x6 2 1 0 0 0 1 20 10 x3
Controle/lucro –500 –200 0 0 0 0 0
CPU 
grande x1 1 0 1 0 0 0 6 ∞ Entra
Gabinete 
pequeno x4 0 1 0 1 0 0 15 15 x2
Placa‑mãe x5 0 1 –3 0 1 0 6 6 Sai
Placa de 
vídeo x6 0 1 –2 0 0 1 8 8 x5
Controle/lucro 0 –200 500 0 0 0 3.000
CPU 
grande x1
Gabinete 
pequeno x4
CPU 
pequena x2 0 1 –3 0 1 0 6
Placa de 
vídeo x6
Controle/lucro
45
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
Em seguida, preenchemos os valores das colunas que não estão zeradas na tentativa:
Tabela 16
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
Gabinete 
grande x3 1 0 1 0 0 0 6 6 Entra
Gabinete 
pequeno x4 0 1 0 1 0 0 15 ∞ x1
Placa‑mãe x5 3 1 0 0 1 0 24 8 Sai
Placa de 
vídeo x6 2 1 0 0 0 1 20 10 x3
Controle/lucro –500 –200 0 0 0 0 0
CPU 
grande x1 1 0 1 0 0 0 6 ∞ Entra
Gabinete 
pequeno x4 0 1 0 1 0 0 15 15 x2
Placa‑mãe x5 0 1 –3 0 1 0 6 6 Sai
Placa de 
vídeo x6 0 1 –2 0 0 1 8 8 x5
Controle/lucro 0 –200 500 0 0 0 3.000
CPU 
grande x1 1 0 0 0
Gabinete 
pequeno x4 0 0 10
CPU 
pequena x2 0 1 –3 0 1 0 6
Placa de 
vídeo x6 0 0 0 1
Controle/lucro 0 0 0 0
46
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Calculemos, então, pela regra do retângulo, os valores correspondentes às três colunas restantes:
Tabela 17
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
Gabinete 
grande x3 1 0 1 0 0 0 6 6 Entra
Gabinete 
pequeno x4 0 1 0 1 0 0 15 ∞ x1
Placa‑mãe x5 3 1 0 0 1 0 24 8 Sai
Placa de 
vídeo x6 2 1 0 0 0 1 20 10 x3
Controle/lucro –500 –200 0 0 0 0 0
CPU 
grande x1 1 0 1 0 0 0 6 ∞ Entra
Gabinete 
pequeno x4 0 1 0 1 0 0 15 15 x2
Placa‑mãe x5 0 1 –3 0 1 0 6 6 Sai
Placa de 
vídeo x6 0 1 –2 0 0 1 8 8 x5
Controle/lucro 0 –200 500 0 0 0 3.000
CPU 
grande x1 1 0 1 0 0 0 6
Gabinete 
pequeno x4 0 0 3 1 –1 0 9
CPU 
pequena x2 0 1 –3 0 1 0 6
Placa de 
vídeo x6 0 0 1 0 –1 1 2
Controle/lucro 0 0 –100 0 200 0 4.200
47
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
Por fim, calculemos quem entra e quem sai para a próxima tentativa:
Tabela 18
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
Gabinete 
grande x3 1 0 1 0 0 0 6 6 Entra
Gabinete 
pequeno x4 0 1 0 1 0 0 15 ∞ x1
Placa‑mãe x5 3 1 0 0 1 0 24 8 Sai
Placa de 
vídeo x6 2 1 0 0 0 1 20 10 x3
Controle/lucro –500 –200 0 0 0 0 0
CPU 
grande x1 1 0 1 0 0 0 6 ∞ Entra
Gabinete 
pequeno x4 0 1 0 1 0 0 15 15 x2
Placa‑mãe x5 0 1 –3 0 1 0 6 6 Sai
Placa de 
vídeo x6 0 1 –2 0 0 1 8 8 x5
Controle/lucro 0 –200 500 0 0 0 3.000
CPU 
grande x1 1 0 1 0 0 0 6 6 Entra
Gabinete 
pequeno x4 0 0 3 1 –1 0 9 3 x2
CPU 
pequena x2 0 1 –3 0 1 0 6 –2 Sai
Placa de 
vídeo x6 0 0 1 0 –1 1 2 2 x6
Controle/lucro 0 0 –100 0 200 0 4.200
48
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Essas tentativas serão repetidas sucessivamente e tantas vezes quantas necessárias até que, na linha de 
controle, todos os números sejam positivos ou nulos. No nosso exemplo, só será necessária mais uma tentativa:
Tabela 19
Base
Variável de 
entrada Variável residual Termo 
indepen-
dente
Termo 
independente 
dividido pela 
coluna de 
trabalho
Variável 
a 
incluir 
ou a 
excluir
Cpu 
grande
Cpu 
pequena
Gabinete 
grande
Gabinete 
pequeno placa-mãe
placa 
de 
vídeo
x1 x2 x3 x4 x5 x6 b
Gabinete 
grande x3 1 0 1 0 0 0 6 6 Entra
Gabinete 
pequeno x4 0 1 0 1 0 0 15 ∞ x1
Placa‑mãe x5 3 1 0 0 1 0 24 8 Sai
Placa de 
vídeo x6 2 1 0 0 0 1 20 10 x3
Controle/lucro –500 –200 0 0 0 0 0
CPU 
grande x1 1 0 1 0 0 0 6 ∞ Entra
Gabinete 
pequeno x4 0 1 0 1 0 0 15 15 x2
Placa‑mãe x5 0 1 –3 0 1 0 6 6 Sai
Placa de 
vídeo x6 0 1 –2 0 0 1 8 8 x5
Controle/lucro 0 –200 500 0 0 0 3.000
CPU 
grande x1 1 0 1 0 0 0 6 6 Entra
Gabinete 
pequeno x4 0 0 3 1 –1 0 9 3 x3
CPU 
pequena x2 0 1 –3 0 1 0 6 –2 Sai
Placa de 
vídeo x6 0 0 1 0 –1 1 2 2 x6
Controle/lucro 0 0 –100 0 200 0 4.200
CPU 
grande x1 1 0 0 0 1 –1 4
Gabinete 
pequeno x4 0 0 0 1 2 –3 3
CPU 
pequena x2 0 1 0 0 –2 3 12
Gabinete 
grande x3 0 0 1 0 –1 1 2
Controle/lucro 0 0 0 0 100 100 4.400
49
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
Observe a última coluna da última tentativa. Ela nos oferece a alternativa ótima para esse problema 
de programação linear:
Tabela 20
Variável Item Qtd.
Programa de produção: x1 CPUs grandes. 4
x2 CPUs pequenas. 12
Sobras	(recursos	residuais) x3 Gabinetes grandes 2
x4 Gabinetes pequenos 3
x5 Placas‑mãe 0
x6 Placas de vídeo 0
6.3 solução computacional – utilizando ferramenta solver do ms excel®
O problema envolvendo a produção de CPUs é de maximização: queremos o máximo lucro. 
Vamos aproveitá‑lo mais uma vez como exemplo para apresentarmos a resolução pelo Método 
Computacional.
Você	deve	ter	percebido	que	o	algoritmo	Simplex,	como	seria	de	se	esperar,	é	uma	sequência	repetitiva	
de	cálculos,	situação	ideal	para	as	chamadas	planilhas	eletrônicas,	como	o	MS	Excel®.	Vamos,	portanto	
tornar a resolver o exemplo das CPUs, utilizando o referido programa da Microsoft.
Antes	 de	 iniciarmos	 o	 cálculo,	 observe	 que	muitas	 vezes	 o	 pacote	 Solver	 (necessário	 para	 esses	
cálculos) não está disponível na planilha. Caso isso ocorra na sua máquina, siga os seguintes passos.
Clique no botão do símbolo Office:
Figura	7
Na tela que aparecerá escolha Opções do Excel:
Figura	8
50
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Opte então pela opção Suplementos, disponível do lado esquerdo da tela que se abriu.
Figura	9
Essa	 opção	 disponibilizará	 vários	 suplementos,	 entre	 eles	 o	 Solver.	 Ative‑o	 e	 terá	 a	 ferramenta	
disponível.
Figura	10
 observação
Caso	 você	não	 tenha	 conseguido	a	 ativação	do	Solver	por	meio	dos	
passos	acima,	será	necessária	a	reinstalação	do	MS	Excel®,	utilizando‑se	a	
opção Instalação completa.
Estando	 com	 a	 ferramenta	 Solver	 disponível,	 podemos	 iniciar	 o	 processo	 de	 programação	
linear. Para tanto, o primeiro passo será a elaboração de uma planilha inicial com os dados 
fundamentais do problema. Acompanhe, na imagem a seguir, a montagem da planilha necessária 
para o nosso exemplo:
51
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	11
Nas	células	B3	e	C3,	aparecerão	as	variáveis	de	entrada,	ou	seja,	as	respostas	solicitadas	(quantidade	
de CPUs grandes e pequenas a serem produzidas). Inicialmente, elas são preenchidas com zeros. Nas 
demais células, colocamos os dados iniciais do problema:
•	 nas	células	B4	e	C4,	são	colocados	os	lucros	unitários,	respectivamente	da	CPU grande e da CPU 
pequena;
•	 nas	células	B7	a	C8,	são	colocadas	as	composições	dos	produtos,	ou	seja,	o	número	de	componentes	
máximos de cada umas das CPUs;
•	 nas	células	E8	a	E10,	são	colocadas	as	restrições,	ou	seja,	a	quantidade	máxima	de	unidades	que	
podem ser produzidas por hora de cada componente.
Nas células sombreadas, são colocadas as fórmulas de cálculo, conforme a seguir.
Na	célula	D5,	é	colocada	a	Função	Objetivo:
FO	=	lucro	=	500x1 + 200x2,
que	nessa	planilha	de	Excel,	ficará	assim:	B4*B3	+	C4*C3
Nas células D7 a D10, serão colocadas as quantidades a serem utilizadas de cada componente, ou 
seja, a quantidade de CPUs a serem produzidas (célula B4 para CPU grande e C4 para CPU pequena), 
multiplicada pela quantidade de componentes utilizados em cada CPU. A seguir, mostram‑se as fórmulas 
e como elas devem ser estabelecidas no Excel:
52
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
gabinete	grande	(célula	D7):	1	×	x1 → no Excel → B7	*	B3
gabinete	pequeno	(célula	D8):	1	×	x2 → no Excel →	C8	*	C3
placas‑mãe	(célula	D9):	3x1 + x2 → no Excel →	B9*B3	+	C9*	C3
placas de vídeo (célula D10): 2x1 + x2 → no Excel →	B10	*	B03	+	C10*C3
Montada a planilha, podemos resolver o problema por meio da utilização da ferramenta computacional. 
No	MS	Excel,	 essa	 ferramenta	é	o	Solver,	que	deve	 ser	acessado	pelos	 seguintes	comandos:	Dados/
Solver.
Figura	12
O	quadro	Parâmetros	do	Solver	abrirá.	Nele,	deveremos	preencher	as	seguintes	informações:
•	 No	quadro	 correspondente	a	Definir célula de destino:, colocar o endereço da célula na 
qual	 está	 a	 Função	 Objetivo.	 No	 nosso	 caso,	 é	 a	 celular	 D4.	 Faça	 isso	 clicando	 sobre	 o	
quadro e em seguida clicando com o botão da esquerda do mouse pressionado sobre a 
célula escolhida.
•	 Na	linha	de	baixo	do	quadro,	escolha	a	opção	Máx, pois esse é um problema no qual queremos 
maximizar o lucro. Existem outros casos nos quais as opções serão Min ou Valor de.
•	 Descendo	no	 quadro	mais	 uma	 linha,	 encontramos	 o	 quadro	Células Variáveis. Nesse quadro, 
apresentaremos as células nas quais estão as variáveis de decisão. No nosso exemplo, as células 
B4	e	C4.	 Faça	 isso	 clicando	e	 arrastando	o	mouse sobre as células, com o botão da esquerda 
pressionado.
53
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
O quadro ficaria assim:
Figura	13
O próximo passo é adicionar as restrições. Isso será feito clicando no botão Adicionar do quadro 
Parâmetros	do	Solver. Quando fizermos isso, aparecerá o quadro a seguir:
Figura	14
Nesse quadro, devemos indicar três aspectos:
•	 Referência	de	célula.	É	a	célula	que	contém	a	fórmula	da	respectiva	restrição.	No	nosso	caso,	são	
as células de D7 a D10.
•	 Escolher	o	sinal	adequado.	O	sinal	padrão	(default) que aparece é o <=. Clicando na seta ao lado 
podemos alterar o sinal, de acordo com o desejado. No nosso caso, desejamos o sinal <=, portanto 
não é necessária a alteração.
•	 Na	caixa	Restrição, setar a célula na qual está a restrição.
Observe como fica o quadro para a restrição dos gabinetes grandes:
54
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Figura	15
Clique então no botão Adicionar e coloque as demais restrições, uma a uma, de modo análogo.
Após adicionar a última restrição, clique no botão OK. O quadro Parâmetros	 do	Solve tornará a 
aparecer e terá o seguinte aspecto:
Figura	16
Nesse ponto, temos todas as informações para o Excel efetuar os cálculos, evidentemente, como já 
vimos antes, por tentativas. Para se iniciar os cálculos, devemos estabelecer algumas opções de cálculo. 
Isso é feito clicando‑se sobre o botão Opções no quadro de Parâmetros, o que fará surgir o quadro 
Opções	do	Solver, mostrado a seguir. Nesse nosso exemplo, manteremos todas as definições‑padrão, 
acrescentando apenas as opções:
•	 Presumir	modelo	linear:	estamos	diante	de	um	caso	de	Programação	Linear,	portanto	o	modelo	
matemático deve ser linear.
•	 Presumir	não	negativos:	o	Excel	assume	nessa	opção	a	presunção	de	que	os	valores	das	células	são	
no	mínimo	zero,	ou	seja,	de	não	existem	números	negativos	(o	que	é	óbvio;	não	há	nesse	exemplo	
a possibilidade da produção de uma quantidade negativa de peças).
•	 Usar	escala	automática:	essa	opção	será	sempre	selecionada	nos	casos	de	Programação	Linear.	
Com isso, dispensam‑se preocupações com a diferença entre as grandezas de entrada e os valores 
de saída do problema.
55
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	17
Feitas	as	opções,	clicamos	no	botão	OK, retornando ao quadro Parâmetros	do	Solve. Devemos conferir 
as diversas informações introduzidas e em seguinda pressionar o botão Resolver.
O	Solver	 fará	 as	 tentativas	 de	 resolução	 e,	 após	 encerrado	o	processo	de	 cálculo,	 apresentará	 o	
quadro Resultados	do	Solver.	Veja	que,	no	nosso	caso,	o	Solver	encontrou	uma	solução	para	o	problema	
que atende a todas as condições e restrições fixadas.
Figura	18
Observe que a planilha montada inicialmente agora apresenta valores nas células que estavam 
zeradas, apresentando o número de CPUs grandes a serem montadas (4), o número de CPUs pequenas a 
serem montadas (12) e o lucro total R$ 4.400,00.
56
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Figura	19
Já no quadro Resultados	do	Solver,	no	lado	direito,	existem	três	opções	de	relatórios.	Selecionamos	
os três, clicando com o botão esquerdo do mouse sobre cada um deles. Além disso, mantivemos a opção 
Manter	solução	do	Solver e aí clicamos em OK.
A planilha fica, então, com o seguinte aspecto:
Figura	20
Observe que, na barra inferior, apareceram os três relatórios mencionados. Vamos analisar cada um deles.
Relatório de respostas
O relatório (vide cópia a seguir) apresenta como valor final a solução ótima para o lucro auferido total, no 
valor de R$ 4.400,00, que será obtido com a montagem de 4 CPUs grandes e 12 CPUs pequenas, conforme 
mostram as células ajustáveis. No campo Valor original, aparecem os zeros inicialmente assumidos.
As restrições apresentas sob o nome Transigência mostram as sobras que ocorrerão. O status Agrupar 
siginifica que não apresentaram sobras. Na coluna Fórmula, aparecem as restrições informadas.
57
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	21
Relatório de limites
Nesse	relatório,	a	primeira	informação	é	uma	repetição	do	valor	máximo	obtido	na	Função	Objetivo,	
que, nesse exemplo, é o lucro auferido total.
Já o grupo de informações nomeado como Ajustável,	simula	o	que	ocorreria	com	a	Função	Objetivo	
caso as quantidades produzidas fossem produzidas na quantidade inferior possível. Perceba que se 
fossem produzidas zero CPUs grandes, o lucro seria de R$ 2.400,00 e caso fossem produzidas zero CPUs 
pequenas,	o	lucro	seria	de	R$	2.000,00;	resultados	estes	óbvios.
Esse	 problema	 é	 de	maximização;	 logo,	 os	 limites	 superiores	 são	 os	 limites	 ótimos.	 Isso	 sempre	
ocorre	em	problemas	de	maximização.	Nos	problemas	de	minimização,	a	situação	será	oposta;	os	limites	
mínimos serão os ótimos.
Figura	22
58
Unidade II
Re
vi
sã
o:
 C
ris
tin
a 
- 
Di
ag
ra
m
aç
ão
: M
ár
ci
o 
- 
02
-0
5-
20
13
Observe que esse relatório apresenta grande importância quando aumentamos o número de 
variáveis do problema. Imagine por exemplo que a empresa tivesse vinte produtos diferentes e quisesse 
descontinuar um deles. Qual seria a consequência para o lucro total? Isso poderia ser respondido por 
um relatório desse tipo.
Relatório de sensibilidade
Quando queremos observar os impactos de determinada alteração nos parâmetros de um problema, 
podemos usar o relatório de sensibilidade.
Note que esse relatório tem dois campos. O primeiro campo, Células ajustáveis, nos informa quais as 
variações toleráveis nos objetivos individuais para que não se altere a solução. Assim podemos notar que 
se o lucro unitário de uma CPU grande variar entre R$ 400,00 e R$ 600,00 (cem reais para mais ou para 
menos) a solução ótima não se alterará. Da mesma forma, é tolerável uma variação no lucro unitário das 
CPUs pequenas entre R$ 167,67 e R$ 250,00.
Figura	23
O segundo campo, Restrições, nos informa, no campo Sombra	Preço,	quanto	perdemos	na	Função	
Objetivo por não ter uma unidade a mais de determinada variável restritiva. Assim, se tivéssemos uma 
placa‑mãe a mais, poderíamos aumentar o lucro em R$ 100,00. Observe, que a as colunas Permissível 
Acréscimo e Permissível Decréscimo têmas mesmas características em ambas as situações.
 resumo
A Programação Linear (PL) é um dos mais nobres modelos da Pesquisa 
Operacional. Dos modelos da Pesquisa Operacional aos problemas 
organizacionais, a Programação Matemática é responsável por cerca de 60%. 
Desse percentual, grande parte deve‑se à PL. O conceito de programação 
59
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
linear é: programação que utiliza uma técnica de otimização (maximização 
e minimização) e pode ser usada em diversos setores. Um dos exemplos 
mais comuns é o uso dessa técnica para a maximização do lucro, levando 
em conta as restrições do ambiente interno (capacidade) externa (mercado)
Geralmente, utiliza‑se a PL quando existe a necessidade de efetuar uma 
distribuição eficiente de recursos limitados, ou seja, maximizando lucros 
e/ou	minimizando	 os	 custos.	 O	 objetivo	 na	 PL	 é	 definido	 como	 Função	
Objetivo.	Esses	cálculos	podem	ser	feitos	pelo	método	do	Simplex,	de	forma	
manual, ou em planilhas eletrônicas, como o Excel, ou ainda pelo método 
gráfico, até duas variáveis. 
 exercícios
Questão 1. Dentro da Pesquisa Operacional, um dos mais nobres modelos é o da Programação 
Linear. José Celso Contador afirma que a Programação Matemática, a linear inclusa, é responsável por 
cerca de 60% dos problemas de Pesquisa Operacional. Modelar um problema, na Programação Linear, 
consiste	em	definir	as	variáveis	de	entrada,	definir	a	Função	Objetivo	e	montar	o	sistema	de	equações	
e inequações referentes às restrições. Entre os métodos de solução na Programação Linear, temos o 
método gráfico aplicável a problemas com duas variáveis de entrada. Com relação a esse modelo, é 
incorreto afirmar que:
A) Em princípio, qualquer ponto do plano ortogonal é solução do problema.
B) Cada restrição divide o espaço ortogonal em dois campos: um com as soluções mais recomendáveis 
e outro com as que não são tão recomendáveis.
C) A sucessiva colocação de restrições produz um polígono de soluções possíveis.
D) A solução ótima está num dos vértices do polígono, porque são os pontos em que dois recursos 
são utilizados ao máximo.
E) A maneira de definir o valor ótimo entre os vários pontos possíveis é por meio de tentativas 
sucessivas.
Resposta correta: alternativa B.
Análise da alternativa
Justificativa: a questão pede o que é incorreto afirmar. Realmente uma restrição divide o espaço 
ortogonal em dois campos. Em um deles, estão as infinitas soluções possíveis ou permitidas, e não 
as recomendáveis. No outro campo, estão as infinitas soluções que não são permitidas ou não são 
possíveis;	nunca	as	não	recomendáveis.	O	próprio	termo	recomendável	é	inapropriado	para	descrever	as	
restrições nessa acepção.