USF_EAD_U3_Pesquisa_e_modelagem_operacional

Prévia do material em texto

Livro - Texto 
 
Título do Livro: Pesquisa Operacional 
Autor: Washington Lemos 
Unidade n.º EV50624: Análise dos resultados 
 
Introdução 
Em uma manhã de 1939, um jovem estudante de 25 anos chega atrasado 
à aula e observa no quadro negro algumas anotações e dois problemas de 
estatística, ele presume ser um dever de casa e os copia em seu caderno. Nos 
dias seguintes, ao sentar-se para resolver o “dever de casa”, ele sente uma 
dificuldade acima do normal, demora mais do que previa, mas finalmente 
encontra as soluções. Supondo estar atrasado para entregar o “dever de casa”, 
ele não espera a próxima aula e deixa as resoluções na sala do professor. 
Aqueles papéis continham a solução de dois famosos problemas até então não 
resolvidos na estatística. O jovem só soube disso quando recebeu a visita do seu 
professor algumas semanas depois. O professor desejava conhecer quem tinha 
escrito aqueles papéis. Anos depois, quando o jovem estudante estava 
começando a escrever sua tese de doutorado o professor lhe interrompeu e 
disse: “Grampeie a solução daqueles dois problemas que você resolveu em um 
volume único e me entregue, isso será sua tese.” O jovem em questão era 
George Dantzig, o criador do método Simplex (ALBERS et al, 1990, p. 62). 
Segundo o próprio Dantzig, o Método Simplex é capaz de fornecer uma 
solução ótima para uma grande variedade de problemas complexos. Concebido 
em 1947 para solucionar problemas militares, o método simplex acumulou desde 
então uma série de publicações e artigos relatando sua aplicação nas mais 
diferentes áreas (DANTZIG, 1982, p.43). Atualmente o Método Simplex é 
amplamente implementado em sistemas de computadores (como o Microsoft 
Solver), usado para resolver problemas de Programação Linear 
consideravelmente grandes, chegando a ter centenas de milhares de restrições 
e milhões de variáveis de decisão (sim, milhões!). Vários fatores influenciam 
quanto tempo será necessário para se resolver um problema usando o Método 
Simplex, sendo que o mais importante é o número de restrições. De modo 
empírico, diz-se que o tempo de processamento tende a ser proporcional ao 
cubo do número de restrições, isso nos leva à assustadora constatação de que 
 
Livro - Texto 
 
caso o número de restrições seja dobrado, o tempo de processamento será 
multiplicado por oito! Já o número de variáveis costuma não afetar tanto o 
processamento, de tal forma que dobrar as variáveis de decisão possivelmente 
não irá dobrar o tempo de resolução. 
É importante lembrar que quando o problema a ser analisado for muito 
grande, será inevitável que sejam tomadas decisões errôneas na formulação dos 
modelos. Não é exceção quando a equipe envolvida na sua resolução considere 
uma longa série de variações no modelo inicial e na criação de cenários 
alternativos, podendo chegar a milhares de variações. A escolha destas 
variações passo por compreender como as soluções são encontradas. Por tudo 
isso, é fundamental conhecer como o Método Simplex funciona e quais as suas 
etapas. Apenas conhecendo bem sua base procedimental, a pessoa 
responsável pelo processo de resolução computacional poderá intuir os 
melhores cenários. 
 
1. Método Simplex 
 
Exceto por problemas muito simples ou com fins pedagógicos, o Método 
Simplex é sempre executado com uso de computadores e pacotes de softwares 
sofisticados que se encontram largamente disponíveis. 
A sua resolução manual tem o fim de levar o estudante ou gestor, de 
compreender a dinâmica do processo de busca de soluções viáveis e 
consequentemente permitir insights nas interpretações de soluções propostas 
por softwares. 
O simplex é um algoritmo e isso é muito importante. Algoritmo é uma 
sucessão de procedimentos logísticos em uma sequência finita de regras, 
raciocínios ou operações que, aplicada a um número finito de dados, permite 
solucionar classes semelhantes de problemas. É um processo no qual um 
procedimento sistemático é repetido (iterado) seguidamente até que o resultado 
desejado seja obtido. Cada percurso do procedimento sistemático é chamado de 
iteração. Além das iterações, os algoritmos também incluem um procedimento 
de dar início e um critério para determinar quando parar. 
 
 
Livro - Texto 
 
 
Pode parecer difícil, mas é exatamente o oposto: um algoritmo substitui 
um problema difícil por uma série de outros fáceis. Sempre que temos um 
algoritmo significa que sabemos exatamente o que fazer, basta seguir o 
procedimento com atenção e cuidados para então chegar aos resultados, como 
mostra o esquema da Figura 1. No caso do Método Simplex, o algoritmo consiste 
em uma sequência de operações fundamentais em matemática, como somar e 
multiplicar, que podem ser feitas com tranquilidade com o uso de uma 
calculadora simples. Aí está justamente a genialidade de Dantzig (o mesmo 
jovem cuja história contamos na abertura desta unidade). Dantzig, que é o 
criador do Método Simplex, foi capaz de transformar um problema algébrico 
extremamente complexo e de difícil resolução em uma sequência de contas 
elementares que podem ser feitas por qualquer pessoa sem conhecimentos 
matemáticos profundos. Deste modo, ele deu aos gestores e militares (que não 
são matemáticos) uma ferramenta para otimizar seus processos produtivos e 
consumo de recursos. 
 
Figura 1 | Estrutura dos Algoritmos 
 
Fonte: Adaptado de (HILLIER e LIEBERMAN, 2010, p. 105) 
 
No caso do Método Simplex, podemos definir alguns conceitos-chave, 
como descrito por Hillier e Lieberman (2010, p. 104). 
 
Livro - Texto 
 
 O método simplex consiste em testar solução viáveis na função 
objetivo. Aqui vale definir que Solução Viáveis são aquelas que 
atendem todas as restrições do modelo matemático proposto. 
Como a Solução Ótima (aquele conjunto de valores das variáveis 
de decisão que proporcionam o melhor valor da função objetivo, ou 
seja, os valores de 𝑥 que fazem o valor de Z ser o máximo ou 
mínimo de acordo com o problema) é justamente o momento no 
qual uma ou mais restrições limitam o problema, o Simplex testa 
exclusivamente estas soluções limítrofes, sabendo eu uma delas é 
a solução ótima. 
 O Método Simplex é um algoritmo interativo, exigindo que a cada 
interação seja observada se a regra de início e a regra de parada 
foram atendidas. 
 Uma Solução Básica é aquela que configura os valores das 
variáveis de decisão em um dado momento. Uma Solução Básica 
inicial é aquela usada para começar o algoritmo Simplex. Sempre 
inicialmente testamos aquela na qual todas as variáveis de decisão 
assumem o valor zero. 
 Sempre que o Simplex testa novas opções para a solução ótima, 
ele faz isso usando soluções viáveis “vizinhas”, ou seja, próximas 
da Solução Básica atual. 
 A decisão de qual “nova solução” será escolhida para o próximo 
passo é sempre definida pela taxa de crescimento da função 
objetivo. Quanto mais Z cresce, melhor é a solução para o Simplex. 
 Em seguida o Simplex testa se há algum “vizinho” que proporciona 
um Z (função objetivo) melhor, se não houver, significa que a 
solução encontrada é ótima. 
 
A melhor forma de compreender o Método Simplex e entender como ele 
funciona, é por meio de um exemplo. Vamos apresentar um exemplo e o passo 
a passo do Simplex no próximo tópico. 
 
 
 
Livro - Texto 
 
1. 1 Aplicando o Simplex 
 
Para demostrarmos a solução de um problema usando o Método Simplex 
é muito conveniente apresentarmos um exemplo. 
 
Exemplo 1 – Uma empresa clássica. 
Um artesão confecciona cadeiras e bancos de madeira para fins de 
decoração em casas rústicas. Na produção de cadeiras e bancos do tipo 
comercializado pelo artesão é necessário o uso de dois tipos de insumos 
principais: lâminas de compensados e folhas de madeira maciça. Para a 
fabricação de cadeiras são necessárias 2 lâminas de compensados e 8 
folhas de madeira maciça. Para a fabricação de bancos, por sua vez, 
utilizam-se2 lâminas de compensados e 2 folhas de madeira maciça. 
A disponibilidade mensal destes dois insumos é de 400 lâminas de 
compensados e 500 folhas de madeira maciça. 
O artesão vende estes produtos para uma revendedora que o monetiza nos 
valores de R$ 300 para cada cadeira e R$ 500 para cada banco. A 
revendedora tem o acordo de comprar toda a produção do artesão, 
independente de qual seja ela. 
Neste caso, qual deve ser o mix produtivo (quantidade a ser produzida de 
cadeiras e bancos) que o sábio artesão deve estipular de modo que seu 
faturamento seja o melhor possível? 
 
Vamos, antes de qualquer coisa, modelar este problema tal como fizemos 
nas unidades anteriores. Começaremos definindo as variáveis de decisão: 
𝑥1 = 𝑄𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑎 𝑠𝑒𝑟 𝑝𝑟𝑜𝑑𝑢𝑧𝑖𝑑𝑎 𝑑𝑒 𝐶𝑎𝑑𝑒𝑖𝑟𝑎𝑠 
𝑥2 = 𝑄𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑎 𝑠𝑒𝑟 𝑝𝑟𝑜𝑑𝑢𝑧𝑖𝑑𝑎 𝑑𝑒 𝐵𝑎𝑛𝑐𝑜𝑠 
 
Uma vez definidas as variáveis de decisão, vamos escrever a função 
objetivo, que neste caso refere-se ao valor total que o artesão irá ganhar quando 
vender todos seus produtos: 
𝑍𝑚á𝑥 = 300𝑥1 + 500𝑥2 
 
Eq. 1 
 
Livro - Texto 
 
Da mesma forma, precisamos escrever as restrições para cada um dos 
recursos principais. 
2𝑥1 + 2𝑥2 ≤ 400 (referente às lâminas de compensados) 
8𝑥1 + 2𝑥2 ≤ 500 (referente às folhas de madeira maciça) 
 
Além destas restrições, temos as restrições de não-negatividade: 
𝑥1 ≥ 0 𝑒 𝑥2 ≥ 0. De tal forma que o modelo todo é: 
 
𝑍𝑚á𝑥 = 300𝑥1 + 500𝑥2 
 Sujeito a: 
2𝑥1 + 2𝑥2 ≤ 400 
8𝑥1 + 2𝑥2 ≤ 500 
𝑥1 ≥ 0 𝑒 𝑥2 ≥ 0. 
 
Este é o que o modelo na forma como vimos nas unidades anteriores. A partir 
de agora o denominaremos Modelo de Programação Linear na forma-padrão. 
Para ser assim chamado, ele precisa ser um problema de maximizar e que tenha 
todas a suas restrições como sendo do tipo ≤ e com todas as variáveis de 
decisão obedecendo a não-negatividade. Se o problema não for deste tipo, 
iremos apresentar nas próximas unidades mecanismos matemáticos para 
transformá-lo em um problema na forma-padrão. 
Agora iniciaremos a resolução do problema usando o Método Simplex, 
passo a passo. 
O procedimento algébrico do Método Simplex consiste em sistemas de 
equações, de tal forma que a o 1º passo para iniciarmos a resolução de um 
modelo matemático de programação linear usando o Simplex, será transformar 
as restrições funcionais de desigualdades (as inequações) em restrições de 
igualdade equivalentes (equações). Para fazer isso, necessitaremos criar um 
conjunto de novas variáveis chamadas de Variáveis de Folga. 
Vamos fazer uma série de raciocínios e se você se perder, não tem 
problema, volte e reflita um pouco. Considere a primeira restrição: 2𝑥1 + 2𝑥2 ≤
400. Precisamos transformar esta desigualdade (inequação) em uma igualdade. 
Claro que temos que fazer isso sem incorrer em nenhuma inverdade matemática. 
Eq. 2 
Eq. 3 
 
Livro - Texto 
 
A inequação diz que o termo 2𝑥1 + 2𝑥2 é um número menor ou igual a 400. 
Então, temos CERTEZA de que 2𝑥1 + 2𝑥2 é um número no MÁXIMO igual a 400. 
Vamos então adiante e podemos dizer que 2𝑥1 + 2𝑥2 é um número tal que se for 
somado com um outro número (chamaremos de variável de folga este outro 
número) será igual a 400. Ou seja, 2𝑥1 + 2𝑥2 + (uma variável de folga) = 400. 
Podemos reescrever dando um símbolo para a Variável de Folga, vamos chamar 
(de modo pouco criativo, assumo) de 𝑥3. Sendo assim dizemos que: 
 
2𝑥1 + 2𝑥2 + 𝑥3 = 400 
 
Perceba que a variável de folga (𝑥3) é um número necessário para “tampar 
o buraco” que fica quando tiramos a desigualdade. Por isso seu nome é Variável 
de Folga. Como 2𝑥1 + 2𝑥2 ≤ 400, a simples substituição do sinal ≤ por = seria 
uma inverdade pois não podemos garantir que 2𝑥1 + 2𝑥2 seja 400, o que 
garantimos é que 2𝑥1 + 2𝑥2 pode ser 400 ou qualquer outro número MENOR 
que 400. Por isso a adição da variável de folga resolve, pois caso 2𝑥1 + 2𝑥2 seja 
igual a 400, então a variável de folga (𝑥3) será zero, porém se 2𝑥1 + 2𝑥2 for 
menor que 400, então a variável de folga (𝑥3) assumirá algum número entre zero 
e 400. 
 Vamos proceder da mesma forma com a segunda restrição, referente às 
folhas de madeira maciça. Para tirarmos a desigualdade, precisaremos adicionar 
uma variável de Folga, mas atenção: não podemos garantir que a variável de 
folga aqui será a mesma da restrição anterior, pois são restrições diferentes e 
nada sabemos delas ainda. Então o que podemos dizer sem incorrer em uma 
inverdade é que 8𝑥1 + 2𝑥2 mais um número será igual a 500. Este número será 
uma outra variável de folga, que chamaremos de 𝑥4. 
 
8𝑥1 + 2𝑥2 + 𝑥4 = 500 
 
Assim, este é o 1º passo para começar a resolver um problema no modelo 
simplex: Transformar o modelo-padrão adicionando as variáveis de folga. 
Para o exemplo 1 teremos: 
Eq. 4 
Eq. 5 
 
Livro - Texto 
 
𝑍𝑚á𝑥 = 300𝑥1 + 500𝑥2 
 Sujeito a: 
2𝑥1 + 2𝑥2 + 𝑥3 = 400 
8𝑥1 + 2𝑥2 + 𝑥4 = 500 
𝑥1 ≥ 0 𝑥2 ≥ 0 𝑥3 ≥ 0 𝑥4 ≥ 0 
 
Perceba que adicionamos as variáveis de folga (𝑥3 𝑒 𝑥4) nas restrições de 
não-negatividade, pois se elas assumissem números negativos, não poderíamos 
mais garantir as igualdades. Bem, como regra geral deste 1º passo, podemos 
dizer: deve-se substituir ≤ por = e sempre somar uma variável de folga diferente 
para cada restrição do problema. 
Agora podemos seguir para o 2º passo que será organizar a função 
objetivo para que não haja variável de decisão do lado direito da igualdade. A 
Função Objetivo do Exemplo 1 é dada por 𝑍𝑚á𝑥 = 300𝑥1 + 500𝑥2. Atente que o 
termo 300𝑥1 + 500𝑥2 está do lado direito da igualdade, e é isso que precisamos 
eliminar. Para isso basta jogar os números que estão do lado direito da igualdade 
para o lado esquerdo, porém trocando seus sinais, de tal forma que teremos: 
 
𝑍𝑚á𝑥 − 300𝑥1 − 500𝑥2 = 0 
 
Este procedimento sempre será desta forma, basta trocar os sinais dos termos 
que estão multiplicando as variáveis de decisão (𝑥1 𝑒 𝑥2). Agora temos o modelo 
no seguinte formato: 
 
𝑍𝑚á𝑥 − 300𝑥1 − 500𝑥2 = 0 
2𝑥1 + 2𝑥2 + 𝑥3 = 400 
8𝑥1 + 2𝑥2 + 𝑥4 = 500 
𝑥1 ≥ 0 𝑥2 ≥ 0 𝑥3 ≥ 0 𝑥4 ≥ 0 
 
Este é o modelo na forma adequada ao Simplex. Vamos organizar apenas 
para fins didáticos colocando todos os termos iguais um embaixo do outro e 
identificando um nome para cada linha. 
 
Eq. 6 
 
Livro - Texto 
 
Linha 0 𝑍𝑚á𝑥 − 300𝑥1 − 500𝑥2 = 0 
Linha I 2𝑥1 + 2𝑥2 + 𝑥3 = 400 
Linha II 8𝑥1 + 2𝑥2 + 𝑥4 = 500 
 
𝑥1 ≥ 0 𝑥2 ≥ 0 𝑥3 ≥ 0 𝑥4 ≥ 0 
 Uma vez que tenhamos o problema nesta forma (somente com 
igualdades, maximização da função objetivo e com restrições de não-
negatividade) podemos colocar no Quadro Simplex. Este será o 3º passo. Para 
isso, cada linha será uma das equações e nas colunas teremos todas as 
variáveis, tanto as variáveis de decisão (𝑥1 𝑒 𝑥2 ) como as variáveis de folga 
(𝑥3 𝑒 𝑥4), além da constante (número que está do lado direito da igualdade de 
todas as equações), como indicado na figura 2. 
 
Figura 2 | Quadro inicial do Simplex – Exemplo 1 
 
Fonte: Autor 
 
Observe que na figura 2 existe uma coluna chamada Variável Básica. Esta 
coluna possui inicialmente as variáveis de folga referente a cada restrição, 
observe que na linha I existe 𝑥3 que é justamente a variável de folga criada 
para esta restrição (veja a Eq. 4). Matematicamente existe uma definição mais 
técnica para a Variável Básica, perceba que ela é aquela variável em cuja coluna 
há apenas zeros e 1, e que o 1 está na interseção entre a linha e a coluna 𝑥3 . 
Ou seja, dizemos que as variáveis básicas estão sempre na Matriz Identidade. 
Observe a Figura 3. 
 
 
 
 
 
 
Livro - Texto 
 
 
 
Figura 3 | Matriz Identidade do quadro inicial do Simplex– Exemplo 1 
 
Fonte: Autor 
 
 Esta informação de que as variáveis básicas estão na matriz identidade 
vai nos servir apenas para possamos identificas facilmente as variáveis básicas 
caso tenhamos um quadro simplex sem as informações de que linha se refere a 
quais restrições e/ou sem indicar quais são as variáveis básicas. 
 Mas uma coisa você não pode esquecer nunca, vamos dizer agora e é 
aqui onde está a grande genialidade do Simplex. TODO quadro simplex indica 
uma Solução Viável, ou seja, aquela solução que atende a TODAS as restrições. 
Na figura 4 podemos identificar a solução inicial que está chamaremos de 
Solução Básica, pois é dada pelas variáveis que estão na “base” (linhas do 
quadro Simplex) e é a primeira solução (inicial). Observe como interpretamos 
este quadro: 
 As linhas indicam o valor de cada variável 
𝑥3 = 400 
𝑥4 = 500 
𝑍 = 𝑧𝑒𝑟𝑜 
 Os valores das variáveis de decisão podem ser deduzidos: 
 
Sendo Eq. 4: 2𝑥1 + 2𝑥2 + 𝑥3 = 400 
Se 𝑥3 = 400 
Então: 
2𝑥1 + 2𝑥2 + 400 = 400 
 
Livro - Texto 
 
2𝑥1 + 2𝑥2 = 400 − 400 
2𝑥1 + 2𝑥2 = 0 
 
Fazendo o mesmo com a Eq. 5. 
 
Sendo Eq. 5: 8𝑥1 + 2𝑥2 + 𝑥4 = 500 
Se 𝑥4 = 500 
Então: 
8𝑥1 + 2𝑥2 + 500 = 500 
8𝑥1 + 2𝑥2 = 500 − 500 
8𝑥1 + 2𝑥2 = 0 
 
Resolvendo o sistema linear entre Eq. 7 e 8: 
 
2𝑥1 + 2𝑥2 = 0 
8𝑥1 + 2𝑥2 = 0 
 
A solução deste sistema será 𝑥1 = 0 e 𝑥2 = 0. 
Logo, se jogarmos estes valores na Função Objetiva (Eq. 6): 
𝑍𝑚á𝑥 − 300𝑥1 − 500𝑥2 = 0 
𝑍𝑚á𝑥 − 300 (0) − 500(0) = 0 
𝑍𝑚á𝑥 = 0 
 
Este valor de Z confirma o quadro Simplex. De tal forma que podemos 
definir uma regra geral para ler o quadro Simplex: Todas as variáveis que estão 
na base (dando nome às linhas) podem ter seus valores retirados da coluna 
“constante” (última coluna do quadro) e TODAS as variáveis que não estão na 
base (variáveis não-básicas) assume o valor zero (simples assim!). 
 No quadro indicado na figura 4 podemos ver que as variáveis básicas no 
quadro inicial são 𝑥3 = 400 e 𝑥4 = 500. As variáveis não-básicas são 𝑥1 = 𝑧𝑒𝑟𝑜 
e 𝑥2 = 𝑧𝑒𝑟𝑜. 
 
Eq. 7 
Eq. 8 
 
Livro - Texto 
 
 
 
Figura 4 | Solução Básica Inicial no quadro inicial do Simplex – Exemplo 1 
 
Fonte: Autor 
 
Agora que entendemos o quadro Simplex inicial, podemos começar as 
interações o algoritmo. Na figura 1 indicamos que todo algoritmo tem uma regra 
de inicialização. Pois bem, a regra de inicialização do simplex é que, SEMPRE 
que existir na linha de Z (linha zero) um número negativo, significa que a Solução 
apresentada no quadro não é ótima e que uma interação deve ser feita. Então 
vamos para o 4º passo: definição da coluna pivô. A coluna pivô indicará a 
variável que “entrará na base”. A escolha deve ser feita da seguinte forma: 
observe na linha Z qual é o número negativo de maior módulo (qual é o número 
“mais negativo”). No nosso exemplo 1, trata-se do “−500”, o que indica que a 
variável que “entrará na base” será o 𝑥2 pois é a variável que está no topo desta 
coluna. Tradicionalmente, indicamos esta coluna fazendo algum tipo de 
destaque, como na figura 5. 
 
Figura 5 | Coluna pivô do quadro inicial do Simplex – Exemplo 1 
 
Fonte: Autor 
 
Livro - Texto 
 
 
 Uma vez que tenhamos definida a coluna pivô, devemos agora dar o 5º 
passo: definir a linha pivô. A linha pivô indicará a variável que “sairá da base”. 
Para definir qual será esta linha pivô, deve-se dividir os valores indicados na 
coluna “constante” (a última coluna do quadro Simplex) pelo valor da coluna pivô 
correspondente à mesma linha. Veja na figura 6 como é feita esta conta para o 
exemplo 1. 
 
Figura 6 | Escolha da linha pivô do quadro inicial do Simplex – Exemplo 1 
 
Fonte: Autor 
 
Na linha I (onde temos o 𝑥3) temos 400 na coluna “constante” e temos “2” 
na coluna pivô, de modo que 400/2 (
400
2
) será igual a 200. Já na linha II (onde 
temos o 𝑥4), 500 está na coluna “constante” e novamente 2 (ser novamente o 
mesmo valor é apenas coincidência) está na coluna pivô referente a esta linha, 
sendo que 500/2 (
500
2
) será igual a 250. Agora que temos todos os valores de 
todas as linhas (não faça esta conta com a linha Z, ela nunca pode ser escolhida 
como linha pivô), escolhemos o menor valor de sinal positivo, ou seja, números 
negativos não podem indicar linha pivô e devem ser ignorados apenas. Desta 
forma, para o nosso exemplo 1 temos que o menor número positivo é “200”, o 
que significa que a linha pivô será a linha I e que 𝑥3 será a variável a sair da 
base, como indica a figura 7. 
 
Figura 7 | Indicada a linha pivô do quadro inicial do Simplex – Exemplo 1 
 
Livro - Texto 
 
 
Fonte: Autor 
 
Neste momento sabemos que na interação que acontecerá 𝑥2 irá entrar 
na base. Lembre-se que entrar na base significa que haverá um valor atribuído 
para esta variável. E sabemos também que 𝑥3 irá sair da base, isso significa que 
seu valor passará a ser zero. Mas, como é esta interação? Veremos em breve, 
mas antes precisamos do 6º passo: definição do número pivô. Este passo é 
simples, veja que a linha pivô e a coluna pivô vão sempre se cruzar em algum 
lugar, neste lugar estará aquele que chamaremos de número pivô. Na figura 8 
temos indicado que o número pivô é 2. 
 
Figura 8 | Indicada a número pivô do quadro inicial do Simplex – Exemplo 1 
 
Fonte: Autor 
 
Agora que temos coluna pivô, linha pivô e número pivô definidos, 
podemos começar a interação. A interação consiste sempre em refazer o quadro, 
em uma solução melhor que a anterior. Para isso é preciso então iniciar o 7º 
passo: desenhar o novo quadro simplex, com as novas variáveis na base. Na 
figura 9 é apresentado o novo quadro, no qual 𝑥3 não está na base, mas sim 𝑥2. 
 
Figura 9 | Indicada o novo quadro Simplex – Exemplo 1 
Número pivô 
 
Livro - Texto 
 
 
Fonte: Autor 
 
Agora vamos começar a preencher o novo quadro e sempre se inicia 
preenchendo aquela que era a linha pivô no quadro anterior, vamos chamá-la de 
“nova linha pivô”. Então o 8º passo: calcular a nova linha pivô. O cálculo a ser 
feito é simples, consistindo em dividira a linha pivô do quadro anterior (linha pivô 
antiga) pelo número pivô. Veja a seguir a conta executada. 
 
2
2
 
2
2
 
1
2
 
0
2
 
400
2
 
 𝟏 𝟏 𝟎, 𝟓 𝟎 𝟐𝟎𝟎 
 
Esta “nova linha pivô” deve ser adicionada no lugar onde estava a antiga 
linha pivô, no novo quadro, ou seja, onde no novo quadro agora está 𝑥2. Veja a 
figura 10. 
 
Figura 10 | Novo quadro Simplex com nova linha pivô – Exemplo 1 
 
Fonte: Autor 
 
Uma vez definida a nova linha pivô, fique atente que vamos usar esta linha 
para calcular todas as outras, sempre com o mesmo procedimento descrito no 
9º passo: calcular todas as outras linhas do quadro. Para calcular as outras 
linhas necessitaremos de mais operações, mas são todas simples. Vamos 
começar por calcular a nova linha Z. Vamos fazer o seguinte, em um lugar 
Linha pivô antiga: 
Número pivô: 
Nova linha pivô: 
 
Livro - Texto 
 
reservado repita a linha Z antiga, agora, abaixo dela coloque a nova linha pivô. 
Em seguida identifique no quadro simplex inicial (figura 8) o número que está na 
coluna pivô da linha que está sendo calculada (neste caso o número que está na 
coluna pivô da linha Z é −500). Agora este número (−500) deve ter seu sinal 
trocado e todos os números da linha pivô serão multiplicados por ele. Para 
calcular linha Z temos que fazer as seguintes contas indicadas na figura 
 
Figura 11 | Procedimento para calcular novas linhas do simplex 
 
Fonte: Autor 
 
Vamos colocar em um esquema que tenha todas as colunas para a linha 
Z. 
 
 −𝟑𝟎𝟎 − 𝟓𝟎𝟎 𝟎 𝟎 𝟎 
 −(−𝟓𝟎𝟎) × ( 𝟏 𝟏 𝟎, 𝟓 𝟎 𝟐𝟎𝟎 )𝟐𝟎𝟎 𝟎 𝟐𝟓𝟎 𝟎 𝟏𝟎𝟎𝟎𝟎𝟎 
 
Apresentando os detalhes de cada conta feita para que você possa 
identificar, fica: 
−(−500) × 1 + (−300) = 200 
−(−500) × 1 + (−500) = 0 
−(−500) × 0,5 + (0) = 250 
−(−500) × 0 + (0) = 0 
−(−500) × 200 + (0) = 100.000 
 
Os dados obtidos devem ser colocados no novo quadro simplex como 
indica a figura 12. 
 
Figura 12 | Novo quadro com os valores calculados da linha Z – Exemplo 1 
Linha Z antiga 
Nova linha pivô 
Nova linha X4 
+ 
 
Livro - Texto 
 
 
 As contas feitas para obter a linha Z estão esquematizadas na figura 13. 
Serão sempre as mesmas. Para parecer complexo à primeira vista, mas tudo é 
somente uma questão de você identificar de onde sai cada número e efetuar as 
contas com auxílio de uma calculadora se preferir. 
 
Figura 13 | Procedimento para calcular novas linhas do simplex 
 
Fonte: Autor 
 
Este mesmo procedimento deve ser feito para calcular a linha 𝑥4. 
Observando a figura 8 podemos ver que o número que está na coluna pivô da 
linha 𝑥4 é 2. A nova linha pivô é a mesma vista na figura 10. Então podemos 
organizar: 
 
 𝟖 𝟐 𝟎 𝟏 𝟓𝟎𝟎 
 −(𝟐) × ( 𝟏 𝟏 𝟎, 𝟓 𝟎 𝟐𝟎𝟎 ) 
 𝟔 𝟎 − 𝟏 𝟏 𝟏𝟎𝟎 
 
Vamos transcrever cada uma das contas feitas para você acompanhar: 
−(2) × 1 + (8) = 6 
−(2) × 1 + (2) = 0 
−(2) × 0,5 + (0) = −1 
−(2) × 0 + (1) = 1 
−(2) × 200 + (500) = 100 
 
Com estes dados podemos completar o quadro simplex. 
Linha X4 antiga 
Nova linha pivô 
Nova linha X4 
+ 
 
Livro - Texto 
 
 
Figura 14 | Quadro final Simplex – Exemplo 1 
 
Fonte: Autor 
 
Agora que o quadro está completo, devemos proceder o último e 10º 
passo: analisar a necessidade de novas interações. Esta análise consiste em 
verificar se existe na linha Z algum número negativo. A ausência de número 
negativo indica que a solução encontra é ótima e que não é necessário fazer 
novas interação, porém, caso haja números negativos, uma nova interação é 
necessária, e devemos voltara para o 4º passo: definir coluna pivô e reiniciar 
todos os procedimentos. 
Isso que acabamos de fazer foi uma interação, agora vamos analisar o 
quadro final. Observe que na linha Z temos, na coluna “constante” o número 
100.000, o que representa que o Lucro Máximo na empresa será de R$100.000 
por mês. Além disso, vê-se que 𝑥2 tem na coluna “constante” o valor de 200, o 
que significa que o valor de 𝑥2 na solução ótima é de 200 (lembre-se que 𝑥2 é a 
quantidade de bancos a ser produzida), notamos que 𝑥1 não está listada na base 
(nas linhas), o que significa que o valor de 𝑥1 é zero. Procedendo o mesmo 
raciocínio vemos que 𝑥4 é 100 e 𝑥3 é zero (pois também não está na base). Estas 
variáveis de folga representam o quanto está sobrando de cada um dos recursos. 
Para o problema isso significa que: 
 
 A solução ótima para empresa é produzir 200 bancos e nenhuma cadeira. 
(𝑥1 = 𝑧𝑒𝑟𝑜 𝑒 𝑥2 = 200) 
 O lucro máximo mensal será de R$ 100.000 (𝑍𝑚á𝑥 = 100.000) 
 Não existe quantidade sobrando de lâminas de compensados (𝑥3), mas 
existem 100 folhas de madeira maciça sobrando (𝑥4). (𝑥3 = 𝑧𝑒𝑟𝑜 𝑒 𝑥4 =
100) 
 
Livro - Texto 
 
 
1. 2 Passo a passo do Simplex 
 
Para resolvermos o exemplo 1, precisamos aplicar o algoritmo Simplex, 
que é um conjunto de procedimentos para que a solução ótima seja obtida. E 
aqui apresentamos os dez (10) passos utilizados para aplicar o simplex. Vai ser 
sempre a mesma coisa. Siga sempre estes passos. 
 
1º passo – Verificar se o problema está no modelo-padrão (somente com 
restrições do tipo ≤, maximização da função objetivo e com restrições de não-
negatividade) e estando, criar um conjunto de novas variáveis chamadas de 
Variáveis de Folga eliminando as inequações e transformando-as em 
equações. 
 
2º passo – organizar a função objetivo para que não haja variável de 
decisão do lado direito da igualdade. 
 
3º passo – colocar o modelo no formato de Quadro Simplex. 
 
4º passo – definição da coluna pivô. A coluna pivô indicará a variável que 
“entrará na base”. 
 
5º passo – definir a linha pivô. A linha pivô indicará a variável que “sairá 
da base”. 
 
6º passo – definição do número pivô. 
 
7º passo – desenhar o novo quadro simplex, com as novas variáveis na 
base 
8º passo – calcular a nova linha pivô. 
 
9º passo – calcular todas as outras linhas do quadro. 
 
 
Livro - Texto 
 
10º passo – analisar se na linha Z ainda existem números negativos, caso 
isso aconteça, então há necessidade de novas interações e deve-se retornar ao 
4º passo. 
 
 Entretanto é conveniente apresenta algumas dúvidas frequentes quando 
se aplica o Simplex ou casos especiais. 
 
 Empate na escolha da coluna pivô – Pode acontecer de duas colunas 
terem o mesmo valor no 4º passo. Se isso acontecer, escolha qualquer 
uma delas de modo arbitrário para ser a coluna pivô. A solução final nos 
dois casos será a mesma, o que pode acontecer é um caminho exigir mais 
interações do que outro. Não existe nenhum método algébrico para 
determinar qual é o melhor caminho. 
 
 Empate na escolha da linha pivô – No 5º passo, se houver empate em 
qual deve ser a variável a sair da base, então esta escolha também é feita 
no dia-a-dia de modo arbitrário. Existem métodos para identificar qual 
seria a melhor opção, mas por sua complexidade acabam sendo 
ignorados (HILLIER; LIEBERMAN, 2010, p. 118). 
 
 Nenhuma linha pivô pode ser escolhida - No 5º passo pode acontecer 
de nenhuma linha poder ser escolhida como linha pivô. Para que isso 
aconteça basta eu todos os números da coluna pivô sejam ou negativos 
ou zero. Neste caso, ao fazer a divisão da coluna “constante” pela coluna 
pivô, o resultado seriam números negativos ou indeterminação (dividir por 
zero é um número indeterminado, que não existe). Este evento tem um 
significado prático, representa que não há limites para crescimento de Z. 
Ou seja, as restrições não impedem o crescimento de Z. Apesar de 
matematicamente isso ser possível, para quem está resolvendo um 
problema real nas empresas isso possivelmente significa que algum erro 
foi cometido na modelagem, pois não faz sentido no mundo real haver um 
crescimento indefinido de lucro, por exemplo. (HILLIER; LIEBERMAN, 
2010, p. 120). 
 
Livro - Texto 
 
 
 Solução múltiplas – Sempre que no quadro final ótimo do Simplex 
houver, na linha Z, uma variável não-básica (não está na base do simplex, 
não está dando nome às colunas) tiver valor zero, isso representa que 
existem outras soluções ótimas. Lembrando que outras soluções ótimas 
significam outro conjunto para as variáveis de decisão que vão resultar no 
mesmo valor ótimo da função objetivo. Caso deseje-se descobrir estas 
outras soluções, basta fazer nova interação, escolhendo como coluna 
pivô esta variável que possui valor zero na linha Z. Caso, ao fazer isso, 
não haja uma linha pivô disponível, então representa que a solução é 
ilimitada. (HILLIER; LIEBERMAN, 2010, p. 121). 
 
2. Custo Reduzido e Preço Sombra no Simplex 
 
O algoritmo Simplex é uma ferramenta versátil. Além de fornecer as 
informações imprescindíveis sobre a solução ótima e o valor máximo da função 
objetivo, o Simplex indica o preço sombra e o custo reduzido. Na figura 15 pode-
se identificar onde estas informações são encontradas para o caso do exemplo 
1. O Custo Reduzido de cada variável de decisão estará na linha Z na coluna 
correspondente à variável de decisão a qual se refere, sendo assim, o custo 
reduzido da variável de decisão 𝑥1 é 200 e o custo reduzido da variável de 
decisão 𝑥2 é zero. Convém relembrar o conceito de custo reduzido. 
O custo reduzido (LAWRENCE; PASTERNACK, 2002, p. 6) pode ser 
entendido de duas formas: 
 
a) O quanto é necessário aumentar o lucro unitário referente a um 
produto(coeficiente da função objetivo) para que a solução ótima 
indicada apresente um valor diferente de zero para a variável ao qual 
se refere. 
b) A taxa de redução da função objetivo caso seja produzido um 
produto que, segundo a solução ótima, não deve ser produzido. 
 
 
Livro - Texto 
 
Assim podemos interpretar que no Exemplo 1, para que a empresa possa 
vender cadeiras (𝑥1 é 𝑎 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑑𝑒 𝑐𝑎𝑑𝑒𝑖𝑟𝑎𝑠 𝑎 𝑠𝑒𝑟 𝑝𝑟𝑜𝑑𝑢𝑧𝑖𝑑𝑎), o valor deve 
ser R$ 200 acima do que é atualmente. Como o valor comercializado da cadeira 
é de R$ 300, isso significa que para a empresa não ter perda ao produzir cadeira, 
ela deve ser comercializada por 200+300= R$500. Já para o produto 𝑥2 (bancos), 
o custo reduzido é zero, o que faz sentido, pois a solução ótima já contempla a 
produção de bancos (𝑥1 = 200) e, portanto, a empresa não precisa alterar seu 
valor de venda do banco para que ele seja economicamente viável, pois já é 
viável. 
 
Figura 15 | Preço Sombra e Custo Reduzido – Exemplo 1 
 
 
Fonte: Autor 
 
Sabemos da unidade anterior que o preço sombra é a taxa de variação 
da função objetivo quando uma restrição sofre uma variação marginal, isto é, 
trata-se de quanto a função objetivo vai alterar para cada unidade adicional ou 
reduzida de um determinado recurso. “O preço-sombra para o recurso mede o 
valor marginal deste recurso, isto é, a taxa na qual Z poderia ser aumentado, 
elevando-se ligeiramente a quantidade do recurso que está sendo 
disponibilizado” (HILLIER; LIEBERMAN, 2010, p. 140). 
 
Analisando as informações referentes aos insumos percebemos que não 
existe quantidade sobrando de lâminas de compensados, pois 𝑥3 = 𝑧𝑒𝑟𝑜, mas 
existem 100 folhas de madeira maciça sobrando, pois 𝑥4 = 100. Isso tem 
impacto no preço sombra. Observe na linha Z, na coluna X3 que o preço sombra 
de lâminas de compensados é 250. Isso significa que, caso a empresa obtenha 
uma unidade adicional de disponibilidade deste recurso (lâminas de 
Custo Reduzido Preço Sombra 
 
Livro - Texto 
 
compensados) o lucro adicional será de R$ 250. De modo análogo identifica-se 
que o preço sombra referente a folhas de madeira maciça é zero (linha Z, na 
coluna X4), o que significa que a existência de quantidade adicional deste insumo 
não influenciará a função objetivo, o que é bem coerente pois existem 100 
unidades deste recuso disponíveis e não utilizados (𝑥4 = 100). 
 
3. Dualidade 
 
O conceito de dualidade é uma ferramenta fundamental para tratamentos 
de dados em programação linear, e de modo prático, uma de suas aplicações 
imediatas é para resolver problemas que envolvam minimizações. Relembre o 
1º passo do Simplex e vai identificar que este algoritmo só pode ser aplicado em 
caso de problemas de maximização. Você deveria estar se perguntando o que 
faremos quando no mundo real houver um problema de minimização. Uma das 
possibilidades será usar a Teoria da Dualidade. Nesta teoria revela que todo 
problema de programação linear tem uma associação com outro problema 
denominado Dual que revela sua solução. O valor da função objetivo do Dual e 
do Primal será exatamente o mesmo. Já o preço sombra encontradas no Dual 
serão iguais ao valor das variáveis de decisão do Primal, e vice-versa. 
A figura 16 apresenta esquematicamente um exemplo de dois problemas, 
é importante que fique claro que a escolha de qual chamar de Dual e qual chamar 
de Primal é absolutamente indiferente, tradicionalmente chamamos de Primal o 
problema original a ser resolvido e de Dual o problema criado pelo analista. 
 
Figura 16 | Dual e Primal 
 
 
 
 
 
 
 
 
Problema Primal 
𝑍𝑚á𝑥 = ∑ 𝑐𝑗𝑥𝑗
𝑛
𝑗=1
 
Sujeito a: 
 
 
∑ 𝑎𝑖𝑗𝑥𝑗
𝑛
𝑗=1
≤ 𝑏𝑖 
𝑥𝑗 ≥ 0 
 
𝑖 = 1, 2, … , 𝑚 
𝑗 = 1, 2, … , 𝑛 
 
 
Problema Dual 
𝑊𝑚í𝑛 = ∑ 𝑏𝑖𝑦𝑖
𝑚
𝑖=1
 
Sujeito a: 
 
 
∑ 𝑎𝑖𝑗𝑦𝑖
𝑚
𝑖=1
≥ 𝑐𝑗 
𝑦𝑖 ≥ 0 
 
𝑖 = 1, 2, … , 𝑚 
𝑗 = 1, 2, … , 𝑛 
 
 
Livro - Texto 
 
 
Fonte: Adaptado de (HILLIER e LIEBERMAN, 2010, p. 204) 
 
 Apesar de aparentemente ser complicado devido às notações 
matemáticas usadas, pode-se dizer, de forma coloquial que o Dual é o “contrário” 
do Primal. Ou seja, caso o Primal seja um problema de maximizar e com todas 
as restrições do tipo ≤, então seu Dual será um problema de minimizar com 
todas as restrições do tipo ≥. Vamos reapresentar na figura 17 a relação entre 
Dual e Primal com uma outra notação para um modelo primal de duas variáveis 
de decisão e duas restrições. 
 
Figura 17 | Dual e Primal (notação algébrica) 
 
 
 
 
 
 
 
 
Fonte: Autor 
 
 Observe atenciosamente para identificar alguns detalhes. Repare que a 
primeira coisa para criar o problema dual e transformar o Zmáx e um Wmín ou um 
Zmín em um Wmáx. A escolha de W no lugar de Z é arbitraria e tem objetivo só de 
identifica quem era o primal e quem será o dual. Observe que as variáveis de 
decisão também mudam, no Dual você deve criar um número de variáveis de 
decisão igual ao número de restrições. Os coeficientes da função objetivo do 
Primal se tornam constantes das restrições do Dual, e as constantes do Primal 
assumem papel de coeficientes da função objetivo do Dual. 
Para visualizar como transformar um problema Primal em um problema 
Dual, pode ser mais conveniente apresentar os modelos matemáticos na forma 
matricial. Faremos isso exclusivamente para buscar visualizar de forma didática 
Problema Primal 
(forma algébrica) 
 
𝑍𝑚á𝑥 = 𝑐1𝑥1 + 𝑐2𝑥2 
 Sujeito a: 
𝑎11𝑥1 + 𝑎12𝑥2 ≤ 𝑏1 
𝑎21𝑥1 + 𝑎22𝑥2 ≤ 𝑏2 
𝑥1 ≥ 0 𝑒 𝑥2 ≥ 0. 
 
Problema Dual 
(forma algébrica) 
 
𝑊𝑚í𝑛 = 𝑏1𝑦1 + 𝑏2𝑦2 
 Sujeito a: 
𝑎11𝑦1 + 𝑎21𝑦2 ≥ 𝑐1 
𝑎12𝑦1 + 𝑎22𝑦2 ≥ 𝑐2 
𝑦1 ≥ 0 𝑒 𝑦2 ≥ 0. 
 
 
Livro - Texto 
 
a transformação, portanto não se assuste com o termo matricial. Na figura 18 
apresentamos a relação entre Dual e Primal na forma matricial. 
 
 
Figura 18 | Dual e Primal (notação matricial) 
 
 
 
 
 
 
 
 
 
 
Fonte: Autor 
 
Para compreender de forma numérica, vamos ver como ficaria o exemplo 
1 caso desejássemos saber qual é o modelo Dual daquele problema. Vamos 
partir do modelo primal, ou seja, o modelo original proposto pelo problema e 
construir o Dual. Na figura 19 podemos ver os dois modelos. 
 
Figura 19 | Dual e Primal (notação algébrica) – Exemplo 1 
 
 
 
 
 
 
 
 
Fonte: Autor 
 
Problema Primal 
(forma matricial) 
 
𝑍𝑚á𝑥 = [𝑐1 𝑐2] [
𝑥1
𝑥2
] 
 Sujeito a: 
[
𝑎11 𝑎12
𝑎21 𝑎22
] [
𝑥1
𝑥2
] ≤ [
𝑏1
𝑏2
] 
[
𝑥1
𝑥2
] ≥ [
0
0
] 
Problema Primal 
(forma matricial) 
 
𝑍𝑚í𝑛 = [𝑦1 𝑦2] [
𝑏1
𝑏2
] 
 Sujeito a: 
[𝑦1 𝑦2] [
𝑎11 𝑎12
𝑎21 𝑎22
] ≥ [
𝑏1
𝑏2
] 
[
𝑦1
𝑦2
] ≥ [
0
0
] 
Problema Primal 
(forma algébrica) 
 
𝑍𝑚á𝑥 = 300𝑥1 + 500𝑥2 
 Sujeito a: 
2𝑥1 + 2𝑥2 ≤ 400 
8𝑥1 + 2𝑥2 ≤ 500 
𝑥1 ≥ 0 𝑒 𝑥2 ≥ 0. 
 
Problema Dual 
(forma algébrica) 
 
𝑊𝑚í𝑛 = 400𝑦1 + 500𝑦2 
 Sujeito a: 
2𝑦1 + 8𝑦2 ≥ 300 
2𝑦1 + 2𝑦2 ≥ 500 
𝑦1 ≥ 0 𝑒 𝑦2 ≥ 0. 
 
 
Livro - Texto 
 
Vamos apresentar um exemplo no qual possamos aplicar os conceitos do 
Dual e do Simplex simultaneamente para resolver uma questão de otimização. 
 
Exemplo 2 – Aplicando Dual e Simplex 
O cenário de recessão econômica muitas vezes exige das empresas 
decisões difíceis. Considere uma empresa que necessite minimizar seus 
custos produtivos. Ela possui três máquinas e cada uma destas máquinas 
tem um custo de operação por hora de modo que sejam: Máquina A, R$ 
50/hora, Máquina B, R$ 60/horas e Máquina C, R$ 70/horas. 
Esta empresa tem compromissos já assumidos para abastecer alguns 
clientes com dois produtos Alfa e Beta, e por isso precisa disponibilizar 
semanalmente no mínimo 10 produtos Alfa e 15 produtos Beta. 
Estes dois produtos podem ser fabricados usando qualquer uma das 
máquinas mas as máquinas possuem processo diferentes de modo que 
cada unidadedo produto Alfa quando produzido na máquina A necessita de 
1 horas de produção, quando fabricado na máquina B ele necessita de 3 
horas de produção e já quando é usada a máquina C são necessárias 5 
horas para ser produzido. Já para o produto Beta, quando produzido na 
máquina A necessita de 2 horas de produção, quando fabricado na máquina 
B ele necessita de 4 horas de produção e já quando é usada a máquina C 
são necessárias 6 horas para ser produzido. Determine qual é a solução 
ótima desta empresa. 
 
Vamos, antes de qualquer coisa, modelar este problema tal como fizemos 
nas unidades anteriores. Começaremos definindo as variáveis de decisão: 
 
𝑥1 = 𝑄𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑒𝑚 ℎ𝑜𝑟𝑎𝑠 𝑎 𝑠𝑒𝑟 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑛𝑎 𝑚á𝑞𝑢𝑖𝑛𝑎 𝐴 
𝑥2 = 𝑄𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑒𝑚 ℎ𝑜𝑟𝑎𝑠 𝑎 𝑠𝑒𝑟 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑛𝑎 𝑚á𝑞𝑢𝑖𝑛𝑎 𝐵 
𝑥3 = 𝑄𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑒𝑚 ℎ𝑜𝑟𝑎𝑠 𝑎 𝑠𝑒𝑟 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑛𝑎 𝑚á𝑞𝑢𝑖𝑛𝑎 𝐶 
 
Uma vez definidas as variáveis de decisão, vamos escrever a modelagem 
completa deste problema. Atente que se trate de um problema cuja otimização 
é reduzir custos, logo será um problema de minimização e as restrições exigem 
 
Livro - Texto 
 
uma produção mínima (pode ser maios, mas não pode ser menor), logo são do 
tipo ≥. 
𝑍𝑚í𝑛 = 50𝑥1 + 60𝑥2 + 70𝑥3 
Sujeito a: 
𝑥1 + 3𝑥2 + 5𝑥3 ≥ 10 
2𝑥1 + 4𝑥2 + 6𝑥3 ≥ 15 
𝑥1 ≥ 0 𝑥2 ≥ 0 𝑥3 ≥ 0 
 
Caso desejemos solucionar este problema usando o Simplex, o 1º passo 
exige verificar se o problema está no modelo-padrão (somente com restrições 
do tipo ≤, maximização da função objetivo e com restrições de não-
negatividade). Ao fazermos isso identificamos que não podemos seguir, pois o 
problema é de minimizar e as restrições são do tipo ≥. Como proceder? Fazendo 
o Dual. Na figura 20 indicamos qual é o problema Dual associado ao problema 
Primal. 
 
Figura 20 | Dual e Primal (notação algébrica) – Exemplo 2 
 
 
 
 
 
 
 
 
 
 
Fonte: Autor 
 
Queremos as respostas para o problema Primal, o que de fato representa 
a empresa, mas como estamos impossibilitados de aplicar o Simplex para ele, 
então vamos aplicar o Simplex no problema Dual e dali extrair as respostas para 
o Primal. Então vamos seguir os passos do Simplex. 
Problema Primal 
(forma algébrica) 
 
𝑍𝑚í𝑛 = 50𝑥1 + 60𝑥2 + 70𝑥3 
 Sujeito a: 
𝑥1 + 3𝑥2 + 5𝑥3 ≥ 10 
2𝑥1 + 4𝑥2 + 6𝑥3 ≥ 15 
 
𝑥1 ≥ 0 𝑥2 ≥ 0 𝑥3 ≥ 0 
 
Problema Dual 
(forma algébrica) 
 
𝑊𝑚í𝑛 = 10𝑦1 + 15𝑦2 
 Sujeito a: 
𝑦1 + 2𝑦2 ≤ 50 
3𝑦1 + 4𝑦2 ≤ 60 
5𝑦1 + 6𝑦2 ≤ 70 
 
𝑦1 ≥ 0 𝑒 𝑦2 ≥ 0. 
 
 
Livro - Texto 
 
 
1º passo – Verificamos que o problema Dual está no modelo-padrão (somente 
com restrições do tipo ≤, maximização da função objetivo e com restrições de 
não-negatividade), então vamos criar as Variáveis de Folga eliminando as 
inequações e transformando-as em equações. 
 
𝑊𝑚í𝑛 = 10𝑦1 + 15𝑦2 
 Sujeito a: 
𝑦1 + 2𝑦2 + 𝑦3 = 50 
3𝑦1 + 4𝑦2 + 𝑦4 = 60 
5𝑦1 + 6𝑦2 + 𝑦5 = 70 
 
𝑦1 ≥ 0 𝑒 𝑦2 ≥ 0 
𝑦3 ≥ 0 𝑦4 ≥ 0 𝑦5 ≥ 0 
 
2º passo – organizar a função objetivo para que não haja variável de decisão do 
lado direito da igualdade. 
 
𝑊𝑚í𝑛 − 10𝑦1 − 15𝑦2 = 0 
 Sujeito a: 
𝑦1 + 2𝑦2 + 𝑦3 = 50 
3𝑦1 + 4𝑦2 + 𝑦4 = 60 
5𝑦1 + 6𝑦2 + 𝑦5 = 70 
 
𝑦1 ≥ 0 𝑒 𝑦2 ≥ 0 
𝑦3 ≥ 0 𝑦4 ≥ 0 𝑦5 ≥ 0 
 
3º passo – colocar o modelo no formato de Quadro Simplex. 
 
 
 
Livro - Texto 
 
 
 
4º passo – definição da coluna pivô. A coluna pivô indicará a variável que 
“entrará na base”. 
 
 
 
5º passo – definir a linha pivô. A linha pivô indicará a variável que “sairá da base”. 
 
 
 
 
6º passo – definição do número pivô. 
 
 
 
7º passo – desenhar o novo quadro simplex, com as novas variáveis na base. 
No nosso caso 𝑦2 entra na base e 𝑦5 sai da base. 
 
 
Coluna Pivô: o número mais negativo 
50
2
= 25 
60
4
= 15 
70
6
= 11,66 
Linha Pivô: o número menor 
Número Pivô: está na linha e na coluna pivô 
 
Livro - Texto 
 
8º passo – calcular a nova linha pivô. Basta dividir a linha pivô antiga pelo 
número pivô, ou seja, a linha III por 6. 
 
9º passo – calcular todas as outras linhas do quadro. Seguiremos o esquema 
apresentado na figura 13, para cada uma das linhas. 
 
Linha 0: 
 −𝟏𝟎 − 𝟏𝟓 𝟎 𝟎 𝟎 𝟎 
 −(−𝟏𝟓) × ( 𝟎, 𝟖𝟑𝟑 𝟏 𝟎 𝟎 𝟏, 𝟏𝟔𝟕 𝟏𝟏, 𝟔𝟔𝟕 ) 
 𝟐, 𝟓 𝟎 𝟎 𝟎 𝟐, 𝟓 𝟏, 𝟕𝟓 
 
Linha I: 
 𝟏 𝟐 𝟏 𝟎 𝟎 𝟓𝟎 
 −(𝟐) × ( 𝟎, 𝟖𝟑𝟑 𝟏 𝟎 𝟎 𝟏, 𝟏𝟔𝟕 𝟏𝟏, 𝟔𝟔𝟕 ) 
 −𝟎, 𝟔𝟔𝟕 𝟎 𝟏 𝟎 𝟎, 𝟑𝟑𝟑 𝟐𝟔, 𝟔𝟔𝟕 
 
Linha II: 
 𝟑 𝟒 𝟎 𝟏 𝟎 𝟔𝟎 
 −(𝟒) × ( 𝟎, 𝟖𝟑𝟑 𝟏 𝟎 𝟎 𝟏, 𝟏𝟔𝟕 𝟏𝟏, 𝟔𝟔𝟕 ) 
 −𝟎, 𝟑𝟑𝟑 𝟎 𝟎 𝟏 − 𝟎, 𝟔𝟔𝟕 𝟏𝟑, 𝟑𝟑𝟑 
 
Desta forma, o novo quadro simplex com todas as linhas preenchidas fica assim. 
 
 
+ 
Linha W antiga 
Nova linha pivô 
Nova linha W 
+ 
Linha Y3 antiga 
Nova linha pivô 
Nova linha Y3 
+ 
Linha Y4 antiga 
Nova linha pivô 
Nova linha Y4 
 
Livro - Texto 
 
10º passo – Agora devemos analisar se na linha W ainda existem números 
negativos, neste caso não há, o que significa que temos já a solução ótima, não 
sendo necessário fazer outra interação. 
 
Uma vez que tenhamos efetuado o Simplex, podemos tirar do quadro as 
soluções. O quadro Simplex nos indica: 
 
- Solução que otimiza a função objetivo, são os valores que se encontram na 
coluna “constante”, na linha das variáveis de decisão. Lembrando que quando a 
variável não está nas linhas (não está na base), o valor que esta variável assume 
é zero. 
 
𝑦1 = 𝑧𝑒𝑟𝑜 
𝑦2 = 11,67 
𝑦3 = 26,67 
𝑦4 = 13,33 
𝑦5 = 𝑧𝑒𝑟𝑜 
 
- Valor da Função Objetivo é obtido na linha W, na coluna “constante”. 
𝑊𝑚í𝑛 = 175 
 
- Preço Sombra é encontrado na linha W, embaixo das variáveis de Folga. 
𝑅𝑒𝑓𝑒𝑟𝑒𝑛𝑡𝑒 𝑎 𝑦3 = 𝑧𝑒𝑟𝑜 
𝑅𝑒𝑓𝑒𝑟𝑒𝑛𝑡𝑒 𝑎 𝑦4 = 𝑧𝑒𝑟𝑜 
𝑅𝑒𝑓𝑒𝑟𝑒𝑛𝑡𝑒 𝑎 𝑦5 = 2,5 
 
- Custo Reduzido é encontrado na linha W, embaixo das variáveis de decisão. 
𝑅𝑒𝑓𝑒𝑟𝑒𝑛𝑡𝑒 𝑎 𝑦1 = 2,5 
𝑅𝑒𝑓𝑒𝑟𝑒𝑛𝑡𝑒 𝑎 𝑦2 = 𝑧𝑒𝑟𝑜 
 
Estas são as informações do problema Dual, entretanto o que nos 
interessa são as respostas do Primal, que é o problema real apresentado pela 
empresa. Vamos responder utilizando as informações do Dual. 
 
Livro - Texto 
 
 
- Função Objetivo: O valor ótimo da função objetivo do problema Primal e Dual 
serão sempre idênticos. Sendo assim, o valor ótimo de Zmín = Wmáx = 175. Ou 
seja, a empresa terá um custo mínimo semanal de R$ 175. 
- Solução ótima (valor das variáveis de decisão): O valor do preço sombra de 
cada uma das restrições do problema Dual é ao valor assumido pelas variáveis 
de decisão do problema Primal. Desta forma: 
 
𝑄𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑒𝑚 ℎ𝑜𝑟𝑎𝑠 𝑎 𝑠𝑒𝑟 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑛𝑎 𝑚á𝑞𝑢𝑖𝑛𝑎 𝐴 = 𝑥1 = 𝑝𝑟𝑒ç𝑜 𝑠𝑜𝑚𝑏𝑟𝑎 𝑟𝑒𝑓𝑒𝑟𝑒𝑛𝑡𝑒 𝑎 𝑦3 = 𝑧𝑒𝑟𝑜 
𝑄𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑒𝑚 ℎ𝑜𝑟𝑎𝑠 𝑎 𝑠𝑒𝑟 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑛𝑎 𝑚á𝑞𝑢𝑖𝑛𝑎 𝐵 = 𝑥2 = 𝑝𝑟𝑒ç𝑜 𝑠𝑜𝑚𝑏𝑟𝑎 𝑟𝑒𝑓𝑒𝑟𝑒𝑛𝑡𝑒 𝑎 𝑦4 = 𝑧𝑒𝑟𝑜 
𝑄𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑒𝑚 ℎ𝑜𝑟𝑎𝑠 𝑎 𝑠𝑒𝑟 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑛𝑎 𝑚á𝑞𝑢𝑖𝑛𝑎 𝐶 = 𝑥3 = 𝑝𝑟𝑒ç𝑜 𝑠𝑜𝑚𝑏𝑟𝑎 𝑟𝑒𝑓𝑒𝑟𝑒𝑛𝑡𝑒 𝑎 𝑦5 = 2,5 
 
Isso significa que a empresa precisa utilizar 2,5 horas da máquina C para 
ter o menor custo possível sem deixar de atender os compromissos já assumidos 
com os clientes. Se substituirmos osvalores nas variáveis de decisão nas 
restrições do modelo, poderemos saber quantos produtos foram feitos. 
 
Modelo do problema: 
𝑍𝑚í𝑛 = 50𝑥1 + 60𝑥2 + 70𝑥3 
Sujeito a: 
𝑥1 + 3𝑥2 + 5𝑥3 ≥ 10 
2𝑥1 + 4𝑥2 + 6𝑥3 ≥ 15 
𝑥1 ≥ 0 𝑥2 ≥ 0 𝑥3 ≥ 0 
 
Se 
𝑥1 = 𝑄𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑒𝑚 ℎ𝑜𝑟𝑎𝑠 𝑎 𝑠𝑒𝑟 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑛𝑎 𝑚á𝑞𝑢𝑖𝑛𝑎 𝐴 = 𝑧𝑒𝑟𝑜 
𝑥2 = 𝑄𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑒𝑚 ℎ𝑜𝑟𝑎𝑠 𝑎 𝑠𝑒𝑟 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑛𝑎 𝑚á𝑞𝑢𝑖𝑛𝑎 𝐵 = 𝑧𝑒𝑟𝑜 
𝑥3 = 𝑄𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑒𝑚 ℎ𝑜𝑟𝑎𝑠 𝑎 𝑠𝑒𝑟 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑑𝑎 𝑛𝑎 𝑚á𝑞𝑢𝑖𝑛𝑎 𝐶 = 2,5 
 
Então para a restrição referente ao produto Alfa: 
𝑥1 + 3𝑥2 + 5𝑥3 ≥ 10 
0 + 3(0) + 5(2,5) ≥ 10 
12,5 ≥ 10 
 
Livro - Texto 
 
 
Isso significa que serão produzidos 12,5 produtos Alfa. Lembre-se que o 
problema exigia que fossem produzidos no mínimo 10, logo a quantidade a ser 
produzida atende à exigência do problema. 
 
Fazendo o mesmo para a restrição referente ao produto Beta. 
2𝑥1 + 4𝑥2 + 6𝑥3 ≥ 15 
2(0) + 4(0) + 6(2,5) ≥ 15 
15 ≥ 15 
 
De modo análogo, este resultado significa que serão produzidos 15 
produtos Beta. O problema exigia que fossem produzidos no mínimo 15, logo a 
quantidade a ser produzida atende à exigência do problema. 
 
- Preço Sombra: O valor do preço sombra de cada uma das restrições do 
problema Primal é ao valor assumido pelas variáveis de decisão do problema 
Dual. Desta forma: 
𝑦1 = 𝑧𝑒𝑟𝑜 = 𝑃𝑟𝑒ç𝑜 𝑠𝑜𝑚𝑏𝑟𝑎 𝑒𝑚 𝑟𝑒𝑙𝑎çã𝑜 𝑎 𝑟𝑒𝑠𝑡𝑟𝑖çã𝑜 𝑑𝑜 𝑝𝑟𝑜𝑑𝑢𝑡𝑜 𝐴𝑙𝑓𝑎 = 𝑧𝑒𝑟𝑜 
𝑦2 = 11,667 = 𝑃𝑟𝑒ç𝑜 𝑠𝑜𝑚𝑏𝑟𝑎 𝑒𝑚 𝑟𝑒𝑙𝑎çã𝑜 𝑎 𝑟𝑒𝑠𝑡𝑟𝑖çã𝑜 𝑑𝑜 𝑝𝑟𝑜𝑑𝑢𝑡𝑜 𝐵𝑒𝑡𝑎 = 11,667 
 
Desta forma podemos interpretar que, caso a exigência de se produzir no 
mínimo 10 unidades do produto Alfa seja alterada em uma unidade, isso não irá 
afetar o valor ótimo da função objetivo, ou seja, os custos da empresa, pois seu 
Preço Sombra é zero. Isso faz sentido, pois na solução ótima já se produz mais 
produtos Alfa do que o problema necessita (produz 12,5). 
 Já para o produto Beta, se houver uma necessidade de se produzir uma 
unidade a mais, a solução ótima será piorada (terá maior custo) em uma taxa de 
R$ 11,667 para cada unidade adicional. Da mesma forma, se o problema 
flexibilizar e permitir que sejam produzidos menos unidades deste produto, a 
empresa consegue reduzir seus custos a uma taxa de R$ 11,667 para cada 
unidade reduzida. 
 Perceba a importância desta análise no mundo real. Se o gestor desta 
empresa está empenhado em reduzir seus custos de modo emergencial, uma 
 
Livro - Texto 
 
possibilidade seria conversar com os clientes que desejam o produto Beta, pois 
cada unidade a menos produzida de Beta irá reduzir o custo operacional da 
empresa. O mesmo não acontece com o produto Alfa. Claro que no mundo real, 
com estas informações, o gestor faria outras perguntas, como por exemplo qual 
é o valor de venda de cada unidade vendida, e possivelmente ele iria modelar 
um outro problema para maximizar a receita e tentaria atender os dois modelos: 
um de maximizar receita e um de minimizar custos. Este é o poder da 
programação linear. 
 
 
Exemplo 3 – Uma segunda aplicação do Dual 
Considere o modelo indicado a seguir. Determine a solução ótima e o valor 
ótimo da função objetivo, utilizando o método simplex. 
 
𝑍𝑚í𝑛 = 360𝑥1 + 250𝑥2 
Sujeito a: 
6𝑥1 + 16𝑥2 ≥ 10 
9𝑥1 + 20𝑥2 ≥ 25 
𝑥1 ≥ 0 𝑥2 ≥ 0 
 
 
Neste exemplo, já temos um modelo matemático definido e o objetivo 
trata-se de responder quais variáveis otimizam o modelo. Para fazer isso usando 
o simplex, podemos seguir os passos definidos anteriormente. 
 
1º passo – Verificamos que o problema não está no modelo-padrão. Então 
precisamos que haja somente com restrições do tipo ≤, maximização da função 
objetivo e com restrições de não-negatividade. Como não podemos usar o 
Simplex com este modelo apresentado, vamos tentar fazer isso usando o 
conceito de dualidade. O Modelo Dual para o problema ficará como indicado na 
figura 21. 
 
 
 
Livro - Texto 
 
Figura 21 | Dual e Primal (notação algébrica) – Exemplo 3 
 
 
 
 
 
 
 
 
 
 
Fonte: Autor 
 
Agora que temos um problema com restrições do tipo ≤, maximização da 
função objetivo e com restrições de não-negatividade, podemos resolver. 
Sabendo que todas as respostas para o problema Primal poderão ser obtidas do 
Dual. Então vamos criar as Variáveis de Folga eliminando as inequações e 
transformando-as em equações. 
 
𝑊𝑚í𝑛 = 10𝑦1 + 25𝑦2 
Sujeito a: 
6𝑦1 + 9𝑦2 + 𝑦3 = 360 
16𝑦1 + 20𝑦2 + 𝑦4 = 250 
𝑦1 ≥ 0 𝑦2 ≥ 0 
𝑦3 ≥ 0 𝑦4 ≥ 0 
 
2º passo – organizar a função objetivo para que não haja variável de decisão do 
lado direito da igualdade. 
 
𝑊𝑚í𝑛 − 10𝑦1 − 25𝑦2 = 02 
Sujeito a: 
6𝑦1 + 9𝑦2 + 𝑦3 = 360 
16𝑦1 + 20𝑦2 + 𝑦4 = 250 
Problema Primal 
(forma algébrica) 
 
𝑍𝑚í𝑛 = 360𝑥1 + 250𝑥2 
Sujeito a: 
6𝑥1 + 16𝑥2 ≥ 10 
9𝑥1 + 20𝑥2 ≥ 25 
𝑥1 ≥ 0 𝑥2 ≥ 0 
Problema Dual 
(forma algébrica) 
 
𝑊𝑚í𝑛 = 10𝑦1 + 25𝑦2 
Sujeito a: 
6𝑦1 + 9𝑦2 ≤ 360 
16𝑦1 + 20𝑦2 ≤ 250 
𝑦1 ≥ 0 𝑦2 ≥ 0 
 
Livro - Texto 
 
𝑦1 ≥ 0 𝑦2 ≥ 0 
𝑦3 ≥ 0 𝑦4 ≥ 0 
 
3º passo – colocar o modelo no formato de Quadro Simplex. 
 
 
4º passo – definição da coluna pivô. A coluna pivô indicará a variável que 
“entrará na base”. 
 
 
5º passo – definir a linha pivô. A linha pivô indicará a variável que “sairá da base”. 
 
 
 
6º passo – definição do número pivô. 
 
 
 
 
Coluna Pivô: o número mais negativo 
360
9
= 40 
250
20
= 12,5 
Linha Pivô: o número menor 
Número Pivô: está na linha e na coluna pivô 
 
Livro - Texto 
 
7º passo – desenhar o novo quadro simplex, com as novas variáveis na base. 
No nosso caso 𝑦2 entra na base e 𝑦4 sai da base. 
 
 
8º passo – calcular a nova linha pivô. Basta dividir a linha pivô antiga pelo 
número pivô, ou seja, a linha II por 20 (edifico no 6º passo). 
 
 
9º passo – calcular todas as outras linhas do quadro. Seguiremos o esquema 
apresentado na figura 13, para cada uma das linhas. 
 
Linha 0: 
 −𝟏𝟎 − 𝟐𝟓 𝟎 𝟎 𝟎 
 −(−𝟐𝟓) × ( 𝟎, 𝟖𝟎 𝟏 𝟎 𝟎, 𝟎𝟓 𝟏𝟐, 𝟓 ) 
 𝟏𝟎 𝟎 𝟎 𝟏, 𝟐𝟓 𝟑𝟏𝟐, 𝟓 
 
Linha I: 
 
 𝟔 𝟗 𝟏 𝟎 𝟑𝟔𝟎 
 −(𝟗) × ( 𝟎, 𝟖𝟎 𝟏 𝟎 𝟎, 𝟎𝟓 𝟏𝟐, 𝟓 ) 
 𝟏, 𝟐 𝟎 𝟏 𝟎, 𝟒𝟓 𝟐𝟒𝟕, 𝟓 
 
Desta forma, o novo quadro simplex com todas as linhas preenchidas fica assim. 
+ 
Linha W antiga 
Nova linha pivô 
Nova linha W 
+ 
Nova linha Y3 
Linha Y3 antiga 
Nova linha pivô 
 
Livro - Texto 
 
 
 
10º passo – Agora devemos analisar se na linha W ainda existem números 
negativos, neste caso não há, o que significa que temos já a solução ótima, não 
sendo necessário fazer outra interação. 
 
Podemos agora retirar do quadro simplex final as respostas para o 
problema Dual. 
 
Variáveis de decisão, aquelas que estão no modelo matemático antes de iniciar 
o Simplex: 
𝑦1 = 𝑧𝑒𝑟𝑜 (𝑎𝑡𝑒𝑛𝑡𝑒 𝑞𝑢𝑒 𝑎 𝑣𝑎𝑟𝑖á𝑣𝑒𝑙 𝑛ò𝑎 𝑒𝑠𝑡á 𝑛𝑎 𝑏𝑎𝑠𝑒, 𝑙𝑜𝑔𝑜 𝑣𝑎𝑙𝑒 𝑧𝑒𝑟𝑜) 
𝑦2 = 12,5 
 
Variáveis de folga, criadas para fazer o Simples: 
𝑦3 = 247,5 
𝑦4 = 𝑧𝑒𝑟𝑜 (𝑎𝑡𝑒𝑛𝑡𝑒 𝑞𝑢𝑒 𝑡𝑎𝑚𝑏é𝑚 𝑛ã𝑜 𝑒𝑠𝑡á 𝑛𝑎 𝑏𝑎𝑠𝑒, 𝑙𝑜𝑔𝑜 𝑣𝑎𝑙𝑒 𝑧𝑒𝑟𝑜) 
 
Função objetivo: 𝑊𝑚á𝑥 = 312,5. 
 
 
Preço Sombra: Na linha W podemos encontrar os preços sombras referentes à 
cada uma das restrições. Basta ver os valores que se encontro logo abaixo da 
Variável de Folga criada para a restrição. 
 
Primeira Restrição - 𝑟𝑒𝑓𝑒𝑟𝑒𝑛𝑡𝑒 𝑎 𝑦3 = 𝑧𝑒𝑟𝑜 
Segunda Restrição - 𝑟𝑒𝑓𝑒𝑟𝑒𝑛𝑡𝑒 𝑎 𝑦4 = 1,25 
 
Livro - TextoMas, vamos nos lembrar de que fizemos o simplex com o modelo do Dual, 
agora nos interessa definir as respostas para o problema original que chamamos 
de Primal. Vamos então obter estes valores do Dual. 
 
 
Variáveis de decisão do Primal é igual ao preço sombra do Dual. 
 𝑥1 = 𝑧𝑒𝑟𝑜 
 𝑥2 = 1,25 
 
Função objetivo do Primal é igual à do Dual: 𝑍𝑚í𝑛 = 𝑊𝑚á𝑥 = 312,5. 
 
Preço Sombra do Primal é igual às variáveis de decisão do Dual: 
Primeira Restrição - 𝑦1 = 𝑧𝑒𝑟𝑜 
Segunda Restrição - 𝑦2 = 12,5 
 
 Desta forma podemos obter todas as informações relevantes do problema 
original proposta no Exemplo 3, mesmo ele sendo um problema de minimizar, 
que não pode ser resolvido diretamente pelo Simplex, sendo necessário usar os 
conceitos de Dualidade. 
 
Considerações finais 
 
 O método Simplex é a ferramenta de otimização que inaugura a 
programação linear. Com este algoritmo passou a ser possível proceder 
complexas tomadas de decisão de modo rápido e simples. Os mecanismos de 
tomada de decisão, antes baseados em processos algébricos longos ou em 
intuição, puderam receber o apoio de mecanismos possíveis de serem aplicados 
no cotidiano das empresas e fundamentado em dados. 
 O simplex está na base da maior parte dos programas de otimização linear 
existentes e ele fornece ao gestor uma quantidade muito grande de informações 
a serem usadas nas empresas. 
 
 
 
Livro - Texto 
 
 
Referências Bibliográficas 
 
 
HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introdução à Pesquisa 
Operacional, 8a ed., New York: McGrawHill, 2010. 
 
LACHTERMACHER, Gerson. Pesquisa Operacional na Tomada de Decisões, 
3ª ed., Amsterdã: Editora Elsevier, 2007. 
 
LAWRENCE, John A.; PASTERNACK, Barry A. Applied Management Science: 
Modeling, Spreadsheet Analysis, and Communication for Decision Making, 2ª ed. 
Hoboken: Wiley, 2002. 
 
PASSOS, Eduardo José Pedreira Franco. Programação Linear como 
instrumento de Pesquisa Operacional, São Paulo: Editora Atlas, 2008. 
 
TAHA, Hamdy A. Pesquisa Operacional. 8º Edição. Londres: Editora Pearson, 
2008. 
 
ALBERS, Donald J.; ALEXANDERSON, Gerald L.; REID, Constance, eds. 
"George B. Dantzig". More Mathematical People. Harcourt Brace Jovanovich. 
1990 
 
DANTZIG, G. B. Reminiscences about the origins of linear programming. 
Operations Research Letters, v. 1, n. 2, p. 43–48, abr. 1982.