Livro texto pesquisa operacional unid_2

Prévia do material em texto

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
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;
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
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
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
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
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
 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:
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
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.
31
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
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+ ≤ = → + ≤ → ≤ → ≤;
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
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.
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
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.
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
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
35
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
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.
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
É uma planilhade 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
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
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:
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 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:
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
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
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
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 
grande x3 1 0 1 0 0 0 6
Gabinete 
pequeno x4 0 1 0 1 0 0 15
Placa‑mãex5 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
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
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:
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 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:
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 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:
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
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
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
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
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
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 1 0
CPU 
pequena x2 0 1 –3 0 1 0 6
Placa de 
vídeo x6 0 0 0 1Controle/lucro 0 0 0 0
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
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
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
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
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
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
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
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
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
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:
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
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:
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
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.
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
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:
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 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.
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 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.
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 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.
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
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
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
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êm as mesmas características em ambas as situações.
7 ProbLemas envoLvendo minimização da Função objeTivo
7.1 algoritmo simplex
O problema de minimização, ao contráriodo 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 ≥.
60
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
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);
• 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;
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
• 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
É 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
62
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
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. 
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
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
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 doSimplex, 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
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) 
64
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
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
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.
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
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:
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
66
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 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
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.
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
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 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 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 II
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 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 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 II
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 
em que 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
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 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.
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 
76
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
é 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. 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.
77
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
Questão 2. 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:
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 à