Trabalho de pesquisa operacional 1 Pronto

Prévia do material em texto

UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
Departamento de Matemática Aplicada - DMA
Pesquisa Operacional
Programação Linear
Programação Linear
Em um modelo de programação linear, devemos ter variáveis de decisão não negativas. Os 
critérios usados para selecionar os melhores valores para as variáveis de decisão, podem ser obtidos 
por uma função linear dessas variáveis, normalmente chamada: Função Objetivo.
As regras de operações que governam o processo (ex: recursos escassos), podem ser expressas 
como um conjunto de equações ou inequações lineares.
Formulação de um Modelo de Programação Linear
1. Identificar as incógnitas (variáveis de decisão);
2. Identificar todas as restrições;
3. Identificar a função objetivo;
Exemplo:
Uma companhia produz 3 modelos de acessórios para cozinha, que requerem 2 recurso: trabalho 
e material. Os dados são distribuídos da seguinte forma:
MODELOS
A B C
TRABALHO 7 3 6
MATERIAL 4 4 5
LUCRO 4 2 3
O fornecimento de matéria-prima é limitado a 200 kg/dia e a disponibilidade de trabalho é de 
150hs/dia. Desse modo, os passos a serem seguidos para formular o modelo, são:
1. (Identificando Variáveis de Decisão)
XA - Produção diária do modelo A.
XB - Produção diária do modelo B.
XC - Produção diária do modelo C. 
2. (Identificando as Restrições)
Trabalho:
7XA + 3XB + 6XC ≤ 150.
Material:
4XA + 4XB + 5XC ≤ 200.
3. (Função Objetivo)
Z = 4XA + 2XB + 3XC.
Problema linear Formulado
Maximizar Z = 4XA + 2XB + 3XC.
s.a
7XA + 3XB + 6XC ≤ 150
4XA + 4XB + 5XC ≤ 200
XA ≥ 0, XB ≥ 0, XC ≥ 0. 
Problema de Inspeção
Uma companhia possui inspetores de grau 1 e grau 2. Temos a seguinte tabela:
É requerida a inspeção de 1800 peças/dia (dia = 8 horas). Cada vez que um erro é cometido por um 
inspetor, o custo para a companhia é de 2 $. A companhia possui 8 inspetores de grau 1 e 10 
inspetores de grau 2. Determine a alocação ótima dos inspetores a fim de minimizar o custo da 
inspeção.
Inspetores Verificam cada preço Precisão Salário
Grau 1 25 peças/hora 98% 4 $
Grau 2 15 peças/hora 95% 3 $
Passos para Formulação do Modelo
1. (Identificando as Variáveis de Decisão) 
X1 – número de inspetores grau 1 atribuídos à inspeção.
X2 – número de inspetores grau 2 atribuídos à inspeção.
2. X1 ≤ 8 X2 ≤ 10.
(25∙8)X1 + (15∙8)X2 ≥ 1800 , OU
200X1 + 120X2 ≥ 1800.
Custo/ hora do inspetor de grau 1:
4 + (0,02) ∙ 25 ∙ 2 = 5 $ / hora
Custo / hora do inspetor de grau 2:
3 + (0,05) ∙ 15 ∙ 2 = 4,5 $ / hora.
A função objetivo se configura da seguinte forma:
Z = (5∙8)X1 + (4,5 ∙8)X2 , OU
Z = 40X1 + 36X2.
Problema Formulado
Minimizar Z = 40X1 + 36X2
s.a
5X1 + 3X2 ≥ 45
X1 ≤ 8
X2 ≤ 10
X1 ≥ 0, X2 ≥ 0.
Solução Gráfica
A solução gráfica para esse problema pode ser encontrada graficamente, analisando cada uma de 
suas restrições.
Z = 380 é o valor ótimo, onde (X1, X2) = (8, 5/3) é a solução ótima única.
1. Solução ótima única:
É o caso do exemplo anterior.
2. Soluções ótimas alternadas:
Exemplo:
Maximizar Z = X1 + X2
X1 + 2X2 ≤ 10
X1 + X2 ≥ 1 
X2 ≤ 4
X1 ≥ 0, X2 ≥ 0 
3. Solução Ilimitada:
Seria o caso se, no exemplo anterior, a restrição 
X1 + 2X2 ≤ 10 , 
não fosse dada.
Propriedade 1.
Se existir solução para um problema de programação linear, então pelo menos um dos vértices da 
região factível se qualificará como uma solução ótima.
Programa Linear na Forma Padrão
Minimizar / Maximizar Z = C1X1 + C2X2 + ∙∙∙+ CnXn
s.a
a11X1 + a12 X2+∙∙∙+ a1nXn = b1
∙ . . .
∙ . . .
∙ . . .
am1X1 + am2X2 +∙∙∙+ amnXn = bm
Características da Forma Padrão
1. Função objetivo é do tipo maximização ou minimização.
2. Todas as restrições são equações.
3. Todas as variáveis são não-negativas.
4. O lado direito das restrições é não negativo.
Em Forma Matricial, temos
Maximizar (Minimizar) Z = CX
s.a
AX = b
X ≥ 0
b ≥ 0.
Redução de um problema Linear à Forma Padrão
Desigualdades:
Introduzimos uma nova variável para representar a folga entre o lado direito e esquerdo da 
desigualdade.
A nova variável é chamada de variável de folga ou de excesso.
Exemplo: (exemplo dos inspetores)
X1 ≤ 8 
X1 + X3 = 8
Analogamente,
X2 ≤ 10
X2 + X4 = 10.
Exemplo: Variável de excesso (X5) 
200X1 + 120X2 ≥ 1800
200X1 + 120X2 – X5 = 1800
X5 ≥ 0.
Variável Irrestrita em sinal
X1 + S1 = 100
S1 = X5 – X6
X5 ≥ 0, X5 ≥ 0 , onde
X5 = Quantidade de (R$) investido.
X6 = Quantia disponível para investir.
Exemplo:
Passar o programa linear abaixo para a forma padrão.
Maximizar Z = X1 – 2X2 + 3X3
s.a
X1 + X2 + X3 ≤ 7
X1 – X2 + X3 ≥ 2
3X1 – X2 – 2X3 = -5
X1 ≥ 0, X2 ≥ 0,
X3 é irrestrita em sinal.
Procedimento:
1. Trocar X3 por X4 – X5, X4 ≥ 0; X5 ≥ 0.
2. Multiplicar ambos os membros da última restrição por -1;
3. Introduzir variável de folga na 1ª restrição: X6;
4. Introduzir variável de excesso na 2ª restrição: X7
Desse modo, temos
Maximizar Z = X1 – 2X2 + 3X4 – 3X5
s.a
X1 + X2 + X4 – X5 + X6 = 7
X1 – X2 + X4 – X5 - X7 = 2
-3X1 + X2 +2X4 – 2X5 = 5
Xi ≥ 0, com i= 1, 2, ..., 7.
Sistemas de Equações
Dois sistemas de equações são ditos equivalentes se ambos os sistemas possuem o mesmo 
conjunto solução.
Há dois tipos de operações elementares que podem ser usadas para obter sistemas equivalentes.
1. Multiplicar uma equação do sistema por um numero não-nulo.
2. Adicionar a qualquer equação um múltiplo constante (positivo, negativo ou nulo) de qualquer 
outra equação do sistema.
Exemplo:
(S1) X1 – 2X2 + X3 – 4X4 + 2X5 = 2 (1)
X1 – X2 – X3 – 3X4 – X5 = 4 (2)
Vamos multiplicar a eq.(1) por (-1) e adicionar à eq.(2).
(S2) X1 – 2X2 + X3 – 4X4 + 2X5 = 2 (3)
0X1 + X2 – 2X3 + X4 – 3X5 = 2 (4)
Vamos multiplicar a eq.(4) por 2 e adicionar à eq.(3).
(S3) X1 – 0X2 - 3X3 – 2X4 + 0X5 = 6 (5)
0X1 + X2 – 2X3 + X4 – 3X5 = 2 (6)
É fácil escrever todas as possíveis soluções para (S3).
Exemplo:
X3 = X4 = X5 = 0
X1 = 1
X2 = 2
Outras soluções para S3 podem ser obtidas escolhendo valores para X3, X4 e X5, e resolvendo para 
X1 e X2 .
Sistemas como S3, são chamados de sistemas canônicos. Aqui, as variáveis X1 e X2 são ditas 
variáveis básicas do sistema canônico S3.
Variável Básica
Uma variável Xi é dita básica em uma equação, se ela aparece com coeficiente unitário naquela 
equação e coeficiente nulo em todas as outras equações.
Aplicando operações elementares, uma dada variável pode ser tornada básica, o que é chamada 
de “operações de pivoteamento”.
Solução Básica
A solução básica é a solução do sistema canônico fazendo as variáveis não-básicas iguais a zero.
Exemplo: (sistema S3) 
X1 = 6; X2 = 2; X3 = X4 = X5 = 0.
Solução Básica Factível
É uma solução básica na qual os valores de todas as variáveis são não-negativos.
O número de soluções básicas possíveis no exemplo é:
5
2
= 10.
Em uma sistema com m equações e n incógnitas, o número máximo de soluções básicas é dado 
por:
𝑛
𝑚 .
O número de soluções factíveis é, também, limitado por esse valor.
Pode ser mostrado que todo vértice da região factível corresponde a uma solução básica factível 
do sistema de equações. Assim, uma solução ótima para um programa linear pode ser obtida 
meramente examinando-se suas soluções básicas factíveis. Esse processo é finito, já que o número 
de soluções básicas factíveis não excede
𝑛
𝑚 .
Princípio do Método Simplex
Exemplo 1:
Maximizar Z = 5X1 + 2X2 + 3X3 – X4 + X5
s.a
X1 + 2X2 + 2X3 + X4 = 8
3X1 + 4X2 + X3 + X5 = 7
Xi ≥ 0, para i =1, 2, ..., 5. 
Temos um sistema canônico com X4 e X5como variáveis básicas.
Solução Básica Correspondente:
X1 = X2 = X3 = 0 
X4 = 8
X5 = 7 
Valor da função objetivo:
Z = 5(0) + 2(0) + 3(0) – 1(8) + 1(7) = -1
Solução básica factível adjacente:
Uma solução básica factível adjacente difere da atual solução básica factível em exatamente uma 
variável.
O Método Simplex
Para obter uma solução básica factível adjacente, o método simplex faz uma variável não-básica 
se tornar básica e em seu lugar, uma variável básica é feita não-básica.
Vamos aumentar o valor de uma variável não-básica de 1 unidade e examinaremos a variação 
restante na função objetivo. Para ilustrar, considere X1.
X1 aumenta de zero para 1.
X2 e X3 permanecem em zero. Assim, temos
X1 + X4 = 8 (1)
3X1 + X5 = 7 (2).
A nova solução factível é:
X1 = 1; X2 = X3 = 0; X4 = 7; X5 = 4.
O novo Valor de Z é:
Z = 5(1) + 2(0) + 3(0) – 1(7) + 1(4) = 2.
Então, a variação líquida no valor de Z por aumento unitário em X1 é:
V. Líquida = (novo valor de Z) – (antigo valor de Z)
= (2) - (-1)
= 3 . 
Esse valor de 3 é chamado o lucro relativo à variável X1
X1 não pode ser aumentado indefinidamente.
Quando X1 aumenta, X4 e X5 diminuem, e seus valores precisam se manter não-negativos para a 
solução permanecer factível.
X4 < 0, se X1 for aumentado além de 8.
X5 < 0, se X1 for aumentado além de 
7
3
.
Portanto, o máximo aumento em X1 é: mínimo 8,
7
3
.
Quando X1 aumenta de zero para 1, Z aumenta de 3 unidade. Como X1 pode ser aumentado até 
7
3
, 
então Z aumenta de 
3
7
3
= 7.
Quando X1 aumenta para 
7
3
, X5 diminui para zero e se torna não básica.
A nova solução factível é:
X1 = 
7
3
; X2 = X3 = X5 = 0; X4 = 
17
3
, e
Z = 6.
O novo sistema canônico correspondente a essa solução básica factível é obtido através de 
operações de pivoteamento. São elas,
1. Dividir a 2ª eq. por 3.
2. Multiplicar a 2ª eq. Por 
− 1
3
e adicionar à 1ª eq. Para eliminar X1.
Condição de otimalidade
Em um problema de maximização, uma solução básica factível é ótima se os lucros relativos de 
suas variáveis não-básicas são menores do que ou iguais a zero ( ≤ 0).
Sumário do Método Simplex
Passo 1. Inicie com uma solução básica factível na forma canônica.
Passo 2. Verifique se a solução básica factível atual é ótima (lucros relativos das variáveis não-
básicas todos menores do que ou iguais a zero). Caso contrário, vá para o passo 3.
Passo 3. Selecione uma variável não-básica para se tornar básica. (uma regra geral é selecionar a 
variável não-básica com maior lucro relativo, de forma a obter o maior aumento do valor de Z).
Passo 4. Determine a variável básica que se tornará não-básica. Para isso, examine cada restrição 
para determinar o quanto a variável não-básica pode ser aumentada.
Para as restrições nas quais a variável não-básica possui um coeficiente positivo, o limite é dado 
pela razão entre a constante do lado direito e esse coeficiente positivo. Para outras restrições, o 
limite é feito ∞.
A restrição com menor limite é determinada e a variável básica naquela restrição se tornará não-
básica.
Passo 5. Encontrar um novo sistema canônico e a nova solução básica factível por meio de 
operações de pivoteamento. Retornar ao passo 2.
Tableau
O exemplo anterior em formato tabular:
Solução básica factível:
X4 = 8; X5 = 7; 
X1 = X2 = X3 = 0; 
CB Cj
BASE
5 
X1
2 
X2
3 
X3
-1 
X5
1 
X6
CONSTANTES
-1 X4 1 2 2 1 0 8
1 X5 3 4 1 0 1 7
Linha 𝐶j 3 0 4 0 0 Z = -1
Lucro relativo das variáveis não-básicas
O lucro relativo das variáveis não-básicas é dado pelo diferença entre a Cj e o produto 
interno de CB e a coluna correspondente.
 𝐶j = Cj -
𝑃𝑟𝑜𝑑𝑢𝑡 𝑖𝑛𝑡𝑒𝑟𝑛𝑜 𝑑𝑒 𝐶𝐵 𝑐𝑜𝑚 𝑎
𝑐𝑜𝑙𝑢𝑛𝑎 𝑐𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑒𝑛𝑡𝑒
Pelo exemplo anterior, temos:
 C1 = 5 – (-1 1) 13 = 3
 C2 = 2 - (-1 1) 24 = 0
 C3 = 2 - (-1 1) 21 = 4
Incluindo X3 na base
X3 entra na base (maior lucro relativo).
Para decidir qual variável sai da base, aplicamos a regra da mínima razão.
O menor limite é 4. Portanto, X4 sai da base. 
Linha Variável básica Limite superior 
sobre X3
1 X4 8/2 = 4
2 X5 7/1 = 7
O novo tableau se configura da seguinte forma:
Solução básica factível:
X3 = 4, X5 = 3 ;
X1 = X2 = X4 = 0.
Valor da função objetivo:
Z = (3 1) 4
3
= 15.
CB Cj
BASE
5 
X1
2 
X2
3 
X3
-1 
X5
1 
X6
CONSTANTES
3 X3 1/2 1 1 1/2 0 4
1 X5 5/2 3 0 0 1 3
Linha 𝐶j 1 -4 0 -2 0 Z = 15
Incluir X1 na base
X1 entra na base (maior lucro relativo).
Para decidir qual variável sai da base, aplicamos a regra da mínima razão.
O menor limite é . Portanto, X5 sai na base. 
Linha Variável básica Limite superior 
sobre X3
1 X3 4/(1/2) = 8
2 X5 3/(5/2) = 6/5
O novo tableau se configura da seguinte forma:
Solução básica factível:
X1 = 6/5, X3 = 17/5 ;
X4 = X5 = X2 = 0.
Valor da função objetivo:
Z = (3 5) 17/5
6/5
= 81/5.
OBS: Essa é a solução ótima pois não tem como melhorar. Os lucros relativas das variáveis não-
básicas são todos não-positivos.
CB Cj
BASE
5 
X1
2 
X2
3 
X3
-1 
X5
1 
X6
CONSTANTES
3 X3 0 2/5 1 3/5 -1/5 17/5
5 X1 1 6/5 0 -1/5 2/5 6/5
Linha 𝐶j 0 -26/5 0 -9/5 -2/5 Z = 81/5
Exemplo 2:
Maximizar Z = 3X1 + 2X2
s.a
-X1 + 2X2 ≤ 4 
3X1 + 2X2 ≤ 14
X1 – X2 ≤ 3
X1 ≥ 0; X2 ≥ 0.
O programa acima na forma padrão:
Maximizar Z = 3X1 + 2X2
s.a
-X1 + 2X2 + X3 = 4 
3X1 + 2X2 + X4 = 14
X1 – X2 + X5 = 3
X1 ≥ 0; X2 ≥ 0, X3 ≥ 0, X4 ≥ 0, X5 ≥ 0 .
Exemplo 2 na forma tabular
T-1 : Vértice A
X1 entra na base. Portanto, aplica-se a regra da mínima razão para ver quem sai da base.
CB Cj
BASE
3 
X1
2 
X2
0 
X3
0 
X4
0 
X5
CONSTANTES
0 X3 -1 2 1 0 0 4
0 X4 3 2 0 1 0 14
0 X5 1 -1 0 0 1 3
Linha 𝐶j 3 2 0 0 0 Z = 0
Linha Vaiável básica Limite superior 
sobre X3
1 X3 ∞
2 X4 14/3
3 X5 3
X5 sai da base
T-2
CB Cj
BASE
3 
X1
2 
X2
0 
X3
0 
X4
0 
X5
CONSTANTES
0 X3 0 1 1 0 1 7
0 X4 0 5 0 1 -3 5
3 X5 1 -1 0 0 1 3
Linha 𝐶j 0 5 0 0 -3 Z = 9
Análise gráfica dos vértices
T-1 : Vértice A
X1 ou X2 poderia entrar na base para aumentar Z.
Tendo decidido aumentar X1, fica claro que X1 não pode ser aumentado além de 3 
(vértice B).
Tableau 2 -> vértice B
X2 pode entrar na base para aumentar o valor de Z.
Aplicando a regra da mínima razão, achamos o mínimo entre 
(7/1, 5/5, ∞) .
Desse modo, X4 sai da base. 
T-3
No tableau 3, X5 pode entrar na base e a resultante solução factível básica terá Z = 14.
Qualquer solução factível cujo valor de Z seja igual ao valor ótimo é, também, uma solução ótima.
CB Cj
BASE
3 
X1
2 
X2
0 
X3
0 
X4
0 
X5
CONSTANTES
0 X3 0 0 1 -1/5 8/5 6
2 X2 0 1 0 1/5 -3/5 1
3 X1 1 0 0 1/5 2/5 4
Linha 𝐶j 0 0 0 -1 0 Z = 14
X5 entra na base
X3 sai da base.
T-4 CB Cj
BASE
3 
X1
2 
X2
0 
X3
0 
X4
0 
X5
CONSTANTES
0 X5 0 0 5/8 -1/8 1 15/4
2 X2 0 1 3/8 1/8 0 13/4
3 X1 1 0 -1/4 1/4 0 5/2
Linha 𝐶j 0 0 0 -1 0 Z = 14
Linha Vaiável básica Limite superior 
sobre X5
1 X3 6/(8/5) = 15/4
2 X2 ∞
3 X1 4/(2/5) = 10
A solução alternativa é:
X1 = 5/2; X2 = 13/4; X3 = 0, X4 = 0, X5 = 15/4.
Em geral, uma solução ótima alternativa é indicada quando existe umavariável não-básica cujo 
lucro relativo seja zero no tableau ótimo.
Ótimo Único
Os lucros relativos de todas as variáveis não-básicas têm valores negativos no tableau ótimo.
Problema de Minimização
Passo 4. Se todos os coeficientes da linha C são positivos ou zero, então a atual solução básica 
factível é ótima. Caso contrário, selecione a variável não-básica com menor valor (mais negativo) 
para entrar na base.
Abordagem Alternativa
Minimizar Z = 40X1 + 36X2
s.a
restrições.
Maximizar Z’ = -40X1 – 36X2 = -Z
s.a
restrições.
Assim, 
Minimizar valor de Z = (Maximizar valor de - Z). 
Empate na seleção da Variável Para Entrar Na Base
Selecione uma das variáveis empatadas arbitrariamente.
Empate na regra da mínima razão e degenerância. Vamos ilustrar esse caso.
CB Cj
BASE
0 
X1
0 
X2
0 
X3
2 
X4
0 
X5
3/2 
X6
CONSTANTES
0 X1 1 0 0 1 -1 0 2
0 X2 0 1 0 2 0 1 4
0 X3 0 0 1 1 1 1 3
Linha 𝐶j 0 0 0 2 0 3/2 Z = 0
X4 entra na base. Dessa maneira, a regra da mínima razão dirá quem sairá da base.
Como obtivemos empate na regra da mínima, faremos X1 sair da base arbitrariamente.
CB Cj
BASE
0 
X1
0 
X2
0 
X3
2 
X4
0 
X5
3/2 
X6
CONSTANTES
2 X4 1 0 0 1 -1 0 2
0 X2 -2 1 0 0 2 1 0
0 X3 -1 0 1 0 2 1 1
Linha 𝐶j -2 0 0 0 2 3/2 Z = 4
Linha Vaiável básica Limite superior 
sobre X4
1 X1 2/1 = 2
2 X2 4/2 = 2
3 X3 3/1 = 3
A nova solução básica é:
X1 = 0, X2 = 0, X3 = 1, X4 = 2, X5 = 0, X6 = 0 
Z = 4.
Degenerância
Uma solução básica factível na qual uma ou mais variáveis básicas são zero é chamada de solução 
degenerada.
Se todas as variáveis básicas forem positivas, então a solução é chamada de 
não-degenerativa. 
X5 entra na base. Dessa maneira, a regra da mínima razão dirá quem sairá da base.
X2 sai da base. Perceba que X5 não pode ser aumentado para uma valor positivo. Portanto, o valor 
de Z não vai aumentar na nova base.
CB Cj
BASE
0 
X1
0 
X2
0 
X3
2 
X4
0 
X5
3/2 
X6
CONSTANTES
2 X4 0 1/2 0 1 0 1/2 2
0 X5 -1 1/2 0 0 1 1/2 0
0 X3 1 -1 1 0 0 0 1
Linha 𝐶j 0 -1 0 0 0 1/2 Z = 4
Linha Vaiável básica Limite superior 
sobre X5
1 X4 ∞
2 X2 0/2 = 0
3 X3 1/2 = 1/2
Solução Ilimitada
Ocorre quando nenhum dos coeficientes da variável não-básica (que vai entrar na base) 
nas restrições é positivo. Pois nenhuma razão finita pode ser formada.
X2 entra na base e X4 sai.
CB Cj
BASE
2 
X1
3 
X2
0 
X3
0 
X4
CONSTANTES
0 X3 1 -1 1 0 2
0 X4 -3 1 0 1 4
Linha 𝐶j 2 3 0 0 Z = 0
X1 entra na base. Desse modo, a regra da razão mínima dirá quem sai da base. 
CB Cj
BASE
2 
X1
3 
X2
0 
X3
0 
X4
CONSTANTES
0 X3 -2 0 1 1 6
3 X2 -3 1 0 1 4
Linha 𝐶j 11 0 0 0 Z = 12
Linha Vaiável básica Limite superior 
sobre X1
1 X3 ∞
2 X2 ∞
Como Encontrar Uma base Factível
1. Tentativa e erro:
Escolhe-se as variáveis básicas arbitrariamente para cada restrição
1.1.
Reduzir o sistema à forma canônica com relação a esta base. Se o sistema canônico fornecer uma 
solução básica factível, então o SIMPLEX pode começar. Caso contrário, tente uma outra escolha de 
variável básica.
2. Usar variáveis artificiais:
Exemplo:
Minimizar Z = -3X1 + X2 + X3
s.a
X1 – 2X2 – X3 ≤ 11
-4X1 + X2 + 2X3 ≥ 3
2X1 - X3 = -1
Xi ≥ 0, i = 1, 2, 3. 
Colocar na forma padrão, temos
Minimizar Z = -3X1 + X2 + X3
s.a
X1 – 2X2 – X3 + X4 = 11
-4X1 + X2 + 2X3 - X5 = 3
-2X1 + X3 = 1
Xi ≥ 0, i = 1, 2, 3, 4, 5. 
Para obtermos uma base, acrescentamos variáveis artificiais de maneira a formar uma base. Assim, 
obtemos o seguinte modelo:
Minimizar Z = -3X1 + X2 + X3
s.a
X1 – 2X2 – X3 + X4 = 11
-4X1 + X2 +2X3 -X5 + X6 = 3
-2X1 + X3 + X7 = 1
Xi ≥ 0, i = 1, 2, ...,7. 
O Método Big M
Atribua um alto valor de custo às variáveis artificiais. Para ilustrar:
A função objetivo se torna:
Minimizar Z = -3X1 + X2 + X3 + MX6 + MX7 , 
Onde M é um número muito grande.
CB Cj 
BASE
-3 
X1
1 
X2
1 
X3
0 
X4
0 
X5
M 
X6
M 
X7
CONSTANTES
0 X4 1 -2 1 1 0 0 0 11
M X6 -4 1 2 0 -1 1 0 3
M X7 -2 0 1 0 0 0 1 1
Linha Cj -3 +6M 1 - M 1 – 3M 0 M 0 0 Z = 4M
X3 entra base ( C3 é o mais negativo) e X7 sai da base.
X2 entra na base e X6 sai da base.
CB Cj 
BASE
-3 
X1
1 
X2
1 
X3
0 
X4
0 
X5
M 
X6
M 
X7
CONSTANTES
0 X4 3 -2 0 1 0 0 -1 10
M X6 0 1 0 0 -1 1 -2 1
1 X3 -2 0 1 0 0 0 1 1
Linha Cj -1 1 – M 0 0 M 0 3M - 1 Z = M + 1
CB Cj 
BASE
-3 
X1
1 
X2
1 
X3
0 
X4
0 
X5
M 
X6
M 
X7
CONSTANTES
0 X4 3 0 0 1 -2 2 -5 12
1 X2 0 1 0 0 -1 1 -2 1
1 X3 -2 0 1 0 0 0 1 1
Linha Cj -1 0 0 0 1 M-1 M + 1 Z = 2
X1 entra na base e X4 sai da base.
Note que esse tableau é ótimo, pois a linha Cj é toda não negativa. Portanto, a solução ótima é:
X1 = 4, X2 = 1, X3 = 9; X4 = X5 = X6 = X7 = 0.
Z = -2.
CB Cj 
BASE
-3 
X1
1 
X2
1 
X3
0 
X4
0 
X5
M 
X6
M 
X7
CONSTANTES
-3 X1 1 0 0 1/3 -2/3 2/3 -5/3 4
1 X2 0 1 0 0 -1 1 -2 1
1 X3 0 0 1 2/3 -4/3 4/3 -7/3 9
Linha Cj 0 0 0 1/3 1/3 M–1/3 M-2/3 Z = -2
Método das Duas Fases
Fase 1. Achar uma solução básica factível para o problema original.
(remover as variáveis artificiais).
Cria-se a segunda função objetivo:
W = X6 + X7 (Função dada pela soma de todas as variáveis artificiais).
Fase 2. A solução básica factível encontrada na fase 1 é otimizada com relação à função objetivo 
original.
CB Cj 
BASE
-3 
X1
1 
X2
1 
X3
0 
X4
0 
X5
M 
X6
M 
X7
CONSTANTES
0 X4 1 -2 1 1 0 0 0 11
1 X6 -4 1 2 0 -1 1 0 3
1 X7 2 0 1 0 0 0 1 1
Linha Cj 6 -1 -3 0 1 0 0 Z = 4
Análise de Sensibilidade
É o estudo de como a solução ótima muda com certas mudanças nos coeficientes de 
entrada. Vamos considerar o seguinte exemplo
Max 10X1 + 6X2 + 4X3 
Sujeito a X1 + X2 + X3 ≤ 100 (Trabalho)
10X1 + 4X2 + 5X3 ≤ 600 (Material)
2X1 +2X2 + 6X3 ≤ 300 (Administração)
X1 ≥ 0, X2 ≥ 0, X3 ≥ 0
Uma fábrica produz 3 produtos que requerem 3 recursos, trabalho, material e 
administração. Os lucros relativos destes problemas são $10, $6 e $4 respectivamente. Há 
100 horas de trabalho, 600 Kg de material e 300 horas de administração disponíveis por dia. 
A fim de determinar o mix ótimo de produtos, ou seja, quais produtos deve-se produzir, 
obtemos os seguintes valores 
Análise de Sensibilidade
• Solução ótima: X1 = 33,33 X2 = 66,67 X3 = 0
• Valor ótimo: $ 733,33
• Preço sombra: 
• Custo de oportunidade 
Linha Preço Sombra
1 $ 3,33
2 $ 0,67
3 $ 0,00
Variável Custo de oportunidade
X1 0
X2 0
X3 2,67
• Limites nos coeficientes ou função objetivo
• Limites nas constantes do lado direito
Variável Limite Inferior Valor Presente Limite Superior
X1 6 10 15
X2 -4 6 10
X3 -∞ 4 6,67
Linha Limite Inferior Valor Presente Limite Superior
1 60 100 150
2 400 600 1000
3 200 300 ∞
• O preço sombra dá o impacto líquido no lucro máximo se unidades adicionais de recurso forem 
obtidas.Por exemplo, cada hora adicional de trabalho fornece um aumento de $3,33 no lucro máximo. 
Suponha que é possível aumentar as horas de trabalho em 25%, através do pagamento de hora 
extra cujo custo será de $50. 
Como o aumento no lucro máximo devido as 25 horas de hora extra é 
25 ∙ (3,33) = 83,25
Como esse valor é maior do que o custo de se obter a hora extra ( $50 ), então é interessante 
contratar a hora extra.
• Quando uma constante muda, a solução ótima muda. Entretanto o mix ótimo de produtos ficará 
inalterado (os produtos que iria produzir ainda serão produzidos), desde que a constante varie 
nos limites especificados. 
Os limites para os coeficientes da função objetivo indicam que a solução ótima não é afetada, desde 
que os coeficientes variem dentro desses limites. 
No nosso exemplo, a solução ótima não muda se C1 permanece entre 6 e 15.
• Suponha que o lucro unitário do produto 1 aumente de 10 para 12. A solução ótima continua a 
mesma, mas o valor ótimo aumenta para
$733,33 + (12-10)∙(33,33) = $799,99
• O custo de oportunidade indica o impacto negativo de se produzir o produto. Não é interessante 
produzir o produto 3. Então uma diminuição do lucro unitário do produto 3 (C3) não afetará a 
solução ótima. Para ser interessante produzir o produto 3, seu lucro unitário precisa aumentar 
para 
(Valor presente + Custo de oportunidade) = ( 4 + 2,67) = 6,67
Ou seja se C3 for aumentado para um valor acima de 6,67 será interessante produzir o produto 3
Variação Simultânea de Parâmetros
Quando ocorre variação simultânea dos parâmetros, podemos usar a “regra do 100%”.
 
𝛿𝐶𝑗
Δ𝐶𝑗
≤ 1. (1)
𝛿𝐶𝑗 é o aumento (diminuição) no coeficiente da função objetivo, Δ𝐶𝑗 é o máximo aumento 
(diminuição) permitido (a). Desde que a equação (1) seja satisfeita, a solução ótima do programa 
linear não muda.
Suponha que o lucro unitário do produto 1 diminua de R$ 1, mas aumente de R$ 1 para os produtos 
2 e 3.
Fazendo as devidas substituições, obtemos
Variação nos coeficientes da função objetivo
𝛿C1 = -1
𝛿C2 = 1
𝛿C3 = 1
Máxima variação permitida
ΔC1 = -4
ΔC2 = 4
ΔC3 = 2,67
Verificando para a equação (1), obtemos
 
𝛿𝐶𝑗
Δ𝐶𝑗
= −
1
−4
+
1
4
+
1
2,67
= 0,875 ≤ 1.
Desse modo, a solução não muda, mas o valor ótimo varia de 
(-1)(33,33) + 1(66,67) + 1(0) = R$ 33,34.
Regra 100% para as constantes
 
𝛿𝑏𝑖
Δ𝑏𝑖
≤ 1. (2)
𝛿bi: aumento (diminuição) na constante bi.
𝛥bi : máximo aumento (diminuição) permitido (a).
Se (2) for satisfeito, então o mix ótimo de produtos permanece o mesmo, mas a solução ótima e o 
valor ótimo vão mudar.
Exemplo:
Considere uma diminuição de 10 hs em disponibilidade de trabalho, 10 kg de aumento em 
material, e 50 hs de diminuição em administração.
Temos,
𝛿C1 = -10, 𝛿C2 = 100, 𝛿C3 = -50; ΔC1 = -40, ΔC2 = 400, ΔC3 = -100.
 
𝛿𝑏𝑖
Δ𝑏𝑖
=
−10
−40
+
100
400
+
−50
−100
= 1 .
Portanto, a base ótima e o mix ótimo de produtos não serão afetados.
A variação da solução ótima é dada por:
(3,33)(-10) + (0,67)(100) + (0)(-50) = R$ 33,70.
Método simplex revisado
CB BASE
5
X1 
2 
X2
3
X3
-1
X4
-1
X5
CONSTANTE
S
-1 X4 1 2 2 1 0 8
-1 X5 3 4 1 0 1 7
Linha 𝐶 3 0 4 0 0 Z = -1
3 X3 1/2 1 1 1/2 0 4
1 X5 5/2 3 0 -1/2 1 3
Linha 𝐶 1 -4 0 -2 0 Z = 15
3 X3 0 2/5 1 3/5 -1/5 17/5
5 X1 1 6/5 0 -1/5 2/5 6/5
Linha 𝐶 0 -28/5 0 -9/5 -2/5 Z = 81/15
TABLEAU
1
2
3
Para ir do tableau 2 para o 3 precisamos do valor de C1, da coluna correspondente a X1 e da coluna 
das constantes.
O método simplex revisado trabalha com o principio de que qualquer tableau correspondente a 
uma única solução básica factível pode ser gerado diretamente das equações originais realizando-se 
operações sobre matrizes.
Sejam as colunas originais P1,P2,...,P5 e as colunas das constantes b. 
P1=
1
3
P2=
2
4
P3=
2
1
P4=
1
0
P5=
0
1
e b= 8
7
O tableau 2 no qual X3 e X5 são variáveis básicas pode ser gerado diretamente como segue:
Defina a matriz B, cujo os elementos são as colunas originais correspondentes as variáveis básicas 
X3 e X5.
B = [P3 , P5] = 2 0
1 1
A inversa de B, denotada por 𝐵−1é:
𝐵−1=
1
2
0
−
1
2
1
Qualquer coluna do tableau 2 pode ser obtida como :
 𝑃j = 𝐵−1. b e 𝑏 = 𝐵−1.b
A seleção da variável não básica que vai entrar na base: 
 𝐶1 = C1 – CB. 𝑃1 = 5 – (3,1) . 
1
2
5
2
= 1
 𝐶2 = C2 – CB. 𝑃2 = 2 – (3,1). 1
3
= -4
 𝐶4 = C4 – CB. 𝑃4 = -1 – (3,1). 
1
2
−
1
2
= -2
Em geral seria 𝐶j = Cj – CB. 𝑃j
Mas sabemos que: 𝑃j =𝐵−1.Pj então, Cj = Cj – CB. 𝐵−1.Pj
Denote por CB.𝐵−1por 𝜋 (multiplicador simplex) 
 𝐶j= Cj- 𝜋 .Pj
Para o tableau 2 𝜋 = CB.𝐵−1 = (3,1). 
1
2
0
−
1
2
1
= (1,1) .
 𝐶1 = C1 – 𝜋.P1 = 5 - (1,1). 1
3
= 1
 𝐶2 = C2 – 𝜋 .P2 = 2 – (1,1). 2
4
= -4
 𝐶3= C3– 𝜋 .P4 = -1 – (1,1). 1
0
= -2
Desde que 𝐶1 >0, selecionamos X1 como variável para entrar na base, temos que encontrar a 
variável que sai da base, precisamos das constantes e da coluna referente a X1 relativas ao tableau
 𝑃1= 𝐵−1.P1 = 
1
2
0
−
1
2
1
.
1
3
= 
1
2
5
2
 𝑏 = 𝐵−1.b = 
1
2
0
−
1
2
1
. 8
7
= 4
3
Aplicando a regra a mínima razão X5 sai da base.
TABLEAU 3. base X3, X1 B = [P3, P1] = 
2 1
1 3
e 𝐵−1 = 
3
5
−
1
5
1
5
2
5
 𝑏 = 𝐵−1.b = 
3
5
−
1
5
−
1
5
1
. 8
7
= 
17
5
6
5
A solução básica factível no tableau 3 é X1 = 
6
5
X3 = 
17
5
e X2=X4=X5=0
𝜋 = CB.𝐵−1= (3, 5).
3
5
−
1
5
1
5
2
5
= ( 
4
5
, 
7
5
)
 𝐶2 = C2 – CB. 𝑃2 = 5 – ( 
4
5
, 
7
5
). 2
4
= -
26
5
 𝐶4 = C4 – CB. 𝑃4 = 2 – ( 
4
5
, 
7
5
). 1
0
= -
9
5
 𝐶5 = C5 – CB. 𝑃5 = -1 – ( 
4
5
, 
7
5
). 0
1
= -
2
5
Não vamos calcular a inversa da base explicitamente, mas por meio de pivoteamento sobre a matriz 
inversa anterior.
EXEMPLO: a solução básica factível inicial (tableau 1) tem X4 e X5 como variáveis básicas a matriz 
base inicial é:
B = [P4, P5] = 
1 0
0 1
= 𝐼 .Em qualquer tableau subsequente as novas colunas correspondentes a X4
e X5 são obtidas pré-multiplicando P4 e P5 pela inversa da base atual, isto é : 
 𝑃4= 𝐵−1.P4 e 𝑃5= 𝐵−1.P5, então [ 𝑃4, 𝑃5] = 𝐵−1.[P4,P5] = 𝐵−1.I =𝐵−1.
Em qualquer tableau as colunas relativas a X4 e X5 contém a inversa da base para aquele tableau.
Isto significa que a nova 𝐵−1 pode ser obtida levando adiante as colunas correspondentes à solução 
básica factível inicial, e atualizando –os por meio de pivoteamento.
Similarmente para a coluna das constantes de qualquer tableau levamos a coluna b adiante 
atualizando por pivoteamento.
O segundo tableau por exemplo seria representado como :
Tendo 𝐵−1, calculamos 𝜋 e os elementos, 𝐶1, 𝐶2 e 𝐶4 e determinamos que X1 vai entrar na base.
A coluna correspondente a X1:
 𝑃1= 𝐵−1.P1 =
1
2
0
−
1
2
1
.
4
3
= 
1
2
1
2
.
Usando 𝑃1 e 𝑏 vemos que X5 sai da base isto significa que a coluna 
1
2
5
2
deve ser reduzida a 0
1
.
BASE 𝐵−1 b
X3
X5
½ 0
- ½ 1 
4
3
1.Multiplicando a 2ª linha por −
1
5
e adicione a 1ª linha.
2.Divida 2ª linha por 
5
2
.
Essa operação de pivoteamentoé aplicada do tableau reduzido anterior
Usando a nova 𝐵−1 calculamos 𝜋 e os 𝐶j das variáveis não-básicas e verificar a otimalidade da 
solução.
BASE 𝐵−1 b
X3
X1
3
5
-
1
5
-
1
5
2
5
17
5
6
5
Teoria da dualidade
Exemplo: maximizar Z = X1 + 2X2 - 3X3 + 4X4
sujeito a X1 + 2X2 + 2X3 - 3X4 ≤ 25
2X1 + X2 - 3X3 + 2X4 ≤ 15
X1 ≥ 0,X2 ≥ 0 , X3 ≥ 0 ,X4 ≥0
O dual programa linear acima é:
minimizar W = 25Y1 + 15Y2
Y1 + 2Y2 ≥ 1
2Y1 + Y2 ≥ 2
2Y1 - 3Y2 ≥ -3
-3Y1 + 2Y2 ≥ 4
Y1 ≥ 0,Y2 ≥ 0
Definição: Um programa linear é dito estar na forma simétrica, se todas as variáveis são não-
negativas, e todas as restrições são inequações(em um problema de maximização as restrições 
precisam ser ≤ , enquanto em um problema de minimização precisam ser ≥).
Primal: maximizar Z = C1X1 + C2X2 + ⋯ ⋯ + CnXn
sujeito a a11X1 + a12X2 + ⋯ ⋯ + a1nXn ≤ b1
⋮ ⋮
⋮ ⋮
an1X1 + an2X2 + ⋯ ⋯ + amnXn ≤ bm
X1,X2, ⋯ ,Xn ≥ 0 .
Dual : minimizar W = b1Y1 + b2Y2 + ⋯ ⋯ + bmYm
sujeito a a11Y1 + a12Y2 + ⋯ ⋯ + am1Yn ≥ C1
⋮ ⋮ ⋮
⋮ ⋮ ⋮
a1nY1 + a2nY2 + ⋯ ⋯ + amnYn ≥Cn
Y1,Y2, ⋯ ,Ym≥ 0
Em notação matricial : maximizar Z = CX minimizar W = Yb
sujeito a AX ≤ b sujeito a YA ≥ C
Y ≥ 0; Y ≥ 0; 
Amxn, bmx1, C1xn, Xnx1, Y1xm.
Teorema da dualidade fraca
Considere os programas lineares primal-dual simétricos:
max Z = cx , Ax ≤ b, x ≥ 0
min W = Yb, yA ≥ C, y ≥ 0.
O valor da função objetivo do problema de minimização (dual) para qualquer solução factível é 
sempre maior ou igual que o valor de uma solução factível para o problema de maximização 
(primal).
PROVA: Sejam 𝑋0 e 𝑌0 soluções factíveis para os problemas primal e dual respectivamente, temos 
que provar que 𝑌0b ≥ c𝑋0 como 𝑋0é factível para o primal temos, A𝑋0 ≤ b, 𝑋0 ≥ 0 (1).
Similarmente 𝑌0é factível para o dual temos, 𝑌0 A ≥ C , 𝑌0 ≥ 0 (2).
Multiplicando (1) por 𝑌0: 𝑌0A𝑋0 ≤ 𝑌0b (3)
Multiplicando (2) por 𝑋0: 𝑌0 A𝑋0 ≥ C𝑋0 (4)
(3) e (4) implicam que 𝑌0b ≥ 𝑌0A𝑋0 ≥ C𝑋0.
COROLÁRIO 1. O problema da função objetivo para o problema de maximização é um limitante 
inferior para o problema de minimização .
COROLÁRIO 2. Similarmente o valor da função objetivo do problema de minimização é um limitante 
superior para o valor do problema de maximização.
COROLÁRIO 3. Se o problema primal é factível e seu objetivo é ilimitado (Z→ ∞), então o problema 
dual não pode ter uma solução factível .
COROLÁRIO 4. Similarmente se o problema dual é factível e seu objetivo é ilimitado (W→ −∞), 
então o primal é infactível.
COROLÁRIO 5. Se um problema primal é factível e o dual é infactível, então o primal é ilimitado.
COROLÁRIO 6. Se o primal é factível e o primal é infactível, então o dual é ilimitado.
TEOREMA 2.(Teorema do critério de otimalidade).Se existem soluções factíveis 𝑋0 e 𝑌0 para os 
programas lineares duais simétricos tais que os valores correspondentes as suas funções objetivos 
são iguais, então essas soluções são de fato ótimas para seus respectivos programas.
PROVA: Seja X qualquer solução factível do primal então pelo teorema 1 CX ≤ 𝑌0b, mas nos foi 
dado que C𝑋0 = 𝑌0b, então CX ≤ C𝑋0.Um argumento similar prova a otimalidade de 𝑌0. 
TEOREMA 3.(Principal da dualidade).Se ambos os problemas (primal e dual) são factíveis então 
ambos tem soluções ótimas, tais que seus valores ótimos são iguais . 
PROVA: Quando ambos os problemas são factíveis então pelos corolários 1 e 2 do teorema 1, temos 
um limitante inferior para o mínimo valor de W e um limitante superior para o máximo valor de Z 
(nem o primal nem o dual tem soluções ilimitadas).Então o primal e o dual tem soluções ótimas.
TEOREMA 4.(Teorema de folga complementar).
Considere os problemas:
Dual Primal
minimizar W = Yb maximizar Z = CX
sujeito a yA ≥ C sujeito a Ax ≤ b 
y≥ 0; x ≥ 0; 
Sejam 𝑋0 e 𝑌0 soluções factíveis para os problemas primal e dual respectivamente, então 𝑋0 e 
𝑌0são ótimas para seus respectivos problemas se, e somente se,
(yA - C) 𝑋0 + (b - Ax) 𝑌0 = 0 . 
onde, (yA - C): folga dual e (b – Ax):folga primal
PROVA: Seja o vetor coluna u = 
𝑢1
𝑢2
⋮
𝑢𝑚
, o vetor folga para o primal e V = (v1,v2,⋯,vn) o vetor folga para o 
dual com 𝑋0 e 𝑌0 são soluções factíveis, então:
A𝑋0 + 𝑈0 = b 𝑋0, 𝑈0 ≥ 0 (1)
𝑌0A - 𝑉0 = c 𝑌0, 𝑉0 ≥ 0 (2)
Multiplicando (1) por 𝑌0 e (2) por 𝑋0,temos:
𝑌0 A𝑋0 + 𝑌0𝑈0 = 𝑌0 b (3)
𝑌0A 𝑋0 - 𝑉0𝑋0 = c 𝑋0 (4)
Subtraindo (4) e (3).
𝑌0𝑈0 + 𝑉0𝑋0 = 𝑌0 b - c 𝑋0 (5).
Para provar o teorema o seguinte resultado deve ser provado:
𝑋0 e 𝑌0 ↔ 𝑌0𝑈0 + 𝑉0𝑋0= 0 (6)
Para provar o teorema, o seguinte resultado deve ser provado:
𝑋0 e 𝑌0 ↔ 𝑌0𝑈0 + 𝑉0𝑋0= 0 (6)
(→)Assume que 𝑋0 e 𝑌0 são ótimo e deste modo, pelo teorema 3, C𝑋0 = 𝑌0b
Perceba que a equação (5) se reduz a 𝑌0𝑈0 + 𝑉0𝑋0 = 0
(←)Assume que a equação (6) é verdadeira, deste modo a equação (5) se reduz a 𝑌0b = C𝑋0
Pelo teorema 2 segue que 𝑋0 e 𝑌0 são ótimos.
Condições de folga complementar
A equação (b) do teorema de folga complementar pode ser exemplificado da seguinte forma:
Vj.Xj = 0 ∀j = 1, ⋯ , 𝑛
Yj.Uj = 0 ∀j = 1, ⋯ , 𝑛
Considere as seguintes afirmações:
1 . Se uma variável primal (Xj) for positiva então a restrição dual correspondente será com a 
equação (Yj).
2 . Se a restrição primal é uma desigualdade restrita ótima ( isto é, 𝑈0 > 0), então a correspondente 
variável dual (𝑌𝑗
0) precisa ser zero não ótimo.
3 . Se uma variável dual (𝑌𝑗
0) é positiva então a correspondente restrição primal será satisfeita como 
uma equação no ótimo (isto é, 𝑈0= 0).
4. Se uma restrição dual é uma desigualdade estrita (Vj > 0), então a variável primal 
correspondente (𝑋𝑗
0) precisa ser zero no ótimo.
Problemas primal-dual assimétricos 
Considere um problema na forma assimétrica :
maximizar Z = 4X1 + 5X2
sujeito a 3X1 + 2X2 ≤ 20
- 4X1 + 3X2 ≥ 10
X1 + X2 = 5
X1≥ 0, X2 irrestrito em sinal.
Na forma simétrica teremos:
maximizar Z = 4X1 + 5X3 – 5X4
sujeito a 3X1 + 2X3 - 2X4 ≤ 20
-4X1 + 3X3 - 3X4 ≤ -10
-4X1 + 3X3 - 3X4 ≤ -10
X1 + X3 - X4 ≤ 5
-X1 - X3 + X4 ≤ -5
X1,X3,X4 ≥ 0.
Note que o dual seria: minimizar 20W1 – 10W2 + 5W3– 5W4
sujeito a 3W1 – 4W2 + W3 – W4 ≥ 4
2W1 +3W2 + W3 – W4 ≥5
-2W1 – 3W2 - W3 + W4 ≥0
W1,W2,W3,W4 ≥0.
A tabela abaixo resume a correspondência primal-dual para todos os programas lineares onde o 
primal é um problema de maximização.
PRIMAL (max) DUAL(min)
A: matriz dos coeficientes transposta de A
b: vetor das constantes vetor de custo
C: vetor lucro 
C: vetor lucro vetor das constantes 
i-ésima restrição é um equação j-ésima restrição dual é uma equação 
tipo ≥ Yi ≥ 0
tipo ≤ Yi ≤ 0 
Xj irrestrita em sinal a variável Yi é irrestrita em sinal 
Xj ≥ 0a j-ésima restrição dual é ≥
Xj ≤ 0 a j-ésima restrição dual é ≤
Exemplo:
minimizar 20Y1 + 10Y2 + 5Y3
sujeito a 3Y1 + 4Y2 + Y3 ≥ 4
2Y1 - 3Y2 + Y3 = 5
Y1 ≥ 0, Y2 ≤ 0, Y3 é irrestrito em sinal .
Método Dual Simplex
Minimizar Z = CX onde A =[P1,P2,⋯ ,Pn]
AX = b
X ≥ 0
a base B para o problema primal é uma matriz mxm, consistindo de m colunas independentes da 
matriz A variáveis básicas da correspondentes a matriz B.
BASE PRIMAL FACTÍVEL.
A base B é uma base primal factível se, e somente se, 𝐵−1.b ≥ 0.
Se B é primal factível, então os valores das variáveis básicas são dadas pelo vetor 𝐵−1.b , XN = 0, 
onde XN denota as variáveis não-básicas. O valor correspondente a essa solução factível é:
Z = CB. 𝐵−1.b .
Agora considere o dual do programa linear padrão:
minimizar W = Yb
sujeito a YA≤ C Y é irrestrito em sinal.
A restrição dual pode ser escrita como: 
Y(P1,P2,⋯,Pn) ≤ (C1,C2, ⋯,Cn)
Y.Pj ≤ Cj ∀j = 1, ⋯ , 𝑛
Y.Pj - Cj ≤ 0 ∀j = 1, ⋯ , 𝑛
Verificar as condições de otimalidade no método simplex revisado é nada mais que verificar se os 
multiplicadores simplex (𝜋 ) satisfazem as restrições duais.
Portanto se a base factível primal B é uma base ótima para o primal, então os multiplicadores 
simplex CB.𝐵−1= 𝜋 satisfazem Cj -𝜋 Pj ≥ 0 ∀j = 1, ⋯ , 𝑛.Isto implica que 𝜋 é factível para o 
problema dual.(satisfaz a restrição dual).
O valor objetivo dual é W = 𝜋.b = CB.𝐵−1.b, que é igual ao valor objetivo primal, pelo teorema 2 
segue que 𝜋 é ótimo para o dual.
Base Factível Dual 
Uma base B, para o problema primal 
Min Z = CX
S.a AX = b
X ≥ 0
é dual factível, se , e somente se 
C – Cb.𝐵−1. 𝐴 ≥ 0
Note que a definição de base factível dual é a mesma que nas equações
𝐶𝑗 = Cj – πPj
𝐶𝑗 ≥ 0 
Isto significa que quando a base B é factível para o primal e o dual, então B é ótimo
Simplex Primal
Vai de base primal factível, para outra base primal factível, até a base se tornar dual factível.
Dual Simplex
Vai de uma base dual factível para outra, até a base se tornar primal factível.
Seleção de uma variável básica para sair da base
Base X1 X2 . . . XR . . . Xm Xm+1 . . . Xs . . . Xn Constantes
X1 1 0 . . . 0 . . . 0 𝑏1
X2 0 1 . . . 0 . . . 0 𝑏2
⋮ ⋮ ⋮
XR 0 0 . . . 1 . . . 0 YRs 𝑏𝑅
⋮ ⋮ ⋮
Xm 0 0 . . . 0 . . . 1 𝑏𝑚
Linha 𝐶 0 0 . . . 0 . . . 0 𝐶𝑚 + 1 . . . 𝐶𝑠 . . . 𝐶𝑛
Seleção de uma variável básica para sair da base
Escolha uma variável básica cujo valor na solução seja o mais negativo. 
Seleção de uma variável não básica para entrar na base
1- Somente aquelas variáveis não básicas com coeficientes negativo na linha R são candidatas para 
entrar na base (YRj < 0).
2- O próximo tableau após pivoteamento precisa ser dual factível. Isso é garantido se a variável não 
básica para entrar na base for selecionada usando a regra:
Máximo 
𝐶𝑗
𝑌𝑅𝑗
YRj < 0
Os novos 𝐶𝑗 após o pivoteamento são 
Novo 𝐶𝑗 = Velho 𝐶𝑗 -
𝑌𝑅𝑗
𝑌𝑅𝑠
× (velho 𝐶𝑗 )
Novo 𝐶𝑗 = YRs ×
𝐶𝑗
𝑌𝑅𝑗
−
𝐶𝑠
𝑌𝑅𝑠
(1)
Caso 1- Para aqueles YRj ≥ 0 , temos 
𝐶𝑗
𝑌𝑅𝑗
≥ 0 uma vez que 𝐶𝑗 ≥ 0. Como YRs é o elemento pivô, 
YRs < 0 e 
𝐶𝑠
𝑌𝑅𝑠
≤ 0. Então o novo 𝐶𝑗 da equação (1) é positivo. 
Caso 2- Agora considere os YRj < 0, pela regra 
𝐶𝑠
𝑌𝑅𝑠
= Máx
𝐶𝑗
𝑌𝑅𝑗
onde YRj < 0.
Então o termo nos colchetes da equação (1) é negativo. Já que YRj < 0, o novo 𝐶𝑗 será positivo, e a 
regra garante que o novo tableau após o pivoteamento seja dual factível.
Exemplo 
Minimizar Z = X1 + 4X2 + 3X4
S.a X1 + 2X2 - X3 + X4 ≥ 3
-2X1 - X2 + 4X3 + X4 ≥ 2
X1 ≥ 0, X2 ≥ 0, X3 ≥ 0, X4 ≥ 0 
Na forma padrão temos
Minimizar Z = X1 + 4X2 + 3X4
S.a X1 + 2X2 - X3 + X4 - X5 = 3
-2X1 - X2 + 4X3 + X4 - X6 = 2
X1 ≥ 0, X2 ≥ 0, X3 ≥ 0, X4 ≥ 0, X5 ≥ 0, X6 ≥ 0. 
CB
CJ
BASE
1
X1
4 
X2
0
X3
3 
X4
0 
X5
0 
X6 CONSTANTES
0 X5 -1 -2 1 -1 1 0 -3
0 X6 2 1 -4 -1 0 1 -2
Linha 𝐶 1 4 0 3 0 0 Z = 0
TABLEAU 1
Solução básica X1 = X2 = X3 = X4 = 0 X5 = -3 X6 = -2
Assim, X5 sai da base pois tem o valor mais negativo dentre as variáveis básicas 
Variável não básica Yij 𝐶𝑗 Razão 
X1 -1 1 -1
X2 -2 4 -2
X4 -1 3 -3
Máxima razão, X1
entra na base
Pivoteamento 
1- Dividir a linha pivô por -1
2- Multiplicar a linha pivô por 2 e adicionar a linha dois
3- Multiplicar a linha pivô por 1 e adicionar a linha 𝐶.
Após o pivoteamento o novo tableau será 
TABLEAU 2
CB
CJ
BASE
1
X1
4 
X2
0
X3
3 
X4
0 
X5
0 
X6 CONSTANTES
1 X1 1 2 -1 1 -1 0 3
0 X6 0 -3 -2 -3 2 1 -8
Linha 𝐶 0 2 1 2 1 0 Z = 3
Solução básica X2 = X3 = X4 = X5 = 0; X1 = 3 , X6 = -8.
Pelo último tableau vemos que X6 sai da base, pois possui o valor mais negativo dentre as variáveis 
básicas. Para ver quem entra na base, temos 
Variável não básica Yij 𝐶𝑗 Razão 
X2 -3 2 −2
3
X3 -2 1 −1
2
X4 -3 2 −2
3
Máxima razão, X3
entra na base
Após o pivoteamento o novo tableau será
CB
CJ
BASE
1
X1
4 
X2
0
X3
3 
X4
0 
X5
0 
X6 CONSTANTES
1 X1 1 7
2
0 5
2
-2 −1
2
7
0 X3 0 3
2
1 3
2
-1 −1
2
4
Linha 𝐶 0 1
2
0 1
2
2 1
2
Z = 7
TABLEAU 3
A solução básica do último tableau é X1 = 7, X3 = 4, X2 = X4 = X5 = X6 =0 .
Observe que o tableau 3 é factível para o primal e para o dual, então a solução básica obtida é 
ótima. 
Uso do dual simplex para identificar que o primal é infactível
Quando a regra da razão falha (isto é todos os elementos da linha pivô são não negativos),
o método dual simplex termina com a conclusão de que o problema primal não tem uma solução 
factível.
Resolvendo um problema de maximização com o dual simplex
Elementos da linha 𝐶 são não positivos. Assuma que 𝑏𝑟 < 0 e então Xr deve deixar a base. A variável 
não básica para entrar na base é escolhida de forma que os elementos da linha 𝐶𝑗 permaneçam não 
positivos. Isso pode ser garantido usando a regra
Mínimo 
𝐶𝑗
𝑌𝑅𝑗
Yij < 0 .
Análise de Sensibilidade
Essa análise se trata de mudanças que ocorrem na solução ótima e no valor ótimo, devido a 
mudanças nos coeficientes de entrada. Vamos tratar dos seguintes casos 
1- Mudanças nos coeficientes da função objetivo (Cj)
2- Mudanças nas constantes (bj)
3- Mudanças nas restrições (coeficientes da matriz A)
3.1- Adicionar novas variáveis
3.2- Mudar colunas existentes
3.3- Adicionar novas restrições
Exemplo 
Considere o seguinte programa linear
Maximizar Z = 2X1 + 3X2 + X3 Onde X1, X2, X3 representam a quantidade
s.a
X1
3
+ 
X2
3
+ 
X3
3
≤ 1 dos produtos A, B, C respectivamente
X1
3
+ 
4X2
3
+ 
7X3
3
≤ 3
X1 ≥ 0, X2 ≥ 0, X3 ≥ 0
O tableau ótimo é 
CB
CJ
BASE
2
X1
3 
X2
1
X3
0 
X4
0 
X5 CONSTANTES
2 X1 1 0 -1 4 -1 1
3 X2 0 1 2 -1 1 2
Linha 𝐶 0 0 -3 -5 -1 Z = 8
Variação em Cj
Caso 1- Mudança do coeficiente de uma variável não básica na função objetivo
Se no exemplo anterior C3 diminuir, não haverá efeito na solução ótima.
Se C3 aumentar acima de um certo valor, o produto C pode se tornar interessante de se produzir.
O tableau dado é ótimo desde que 𝐶3 ≤ 0.
𝐶3 = C3 - 2 3 −1
2
= C3 – 4 para que o tableau dado seja ótimo, devemos ter
𝐶3 = C3 – 4 ≤0 , ou seja, C3 ≤ 4.
Por exemplo, suponha que C3 é aumentado para 6, então 𝐶3 = 2 e o mix de produtos não é mais 
ótimo (isto é X3 pode aumentar na base e aumentar Z). O novo tableau ótimo será:
CB
CJ
BASE
2
X1
3 
X2
6
X3
0 
X4
0 
X5 CONSTANTES
2 X1 1 1
2
0 7
2
−1
2
2
6 X3 0 1
2
1 −1
2
1
2
1L
Linha 𝐶 0 -1 0 -4 -2 Z = 10
Caso 2- Mudança do coeficiente da função objetivo de uma variável básica
Se no nosso exemplo C1 diminuir abaixo de um certo valor, não será mais interessante produzir o 
produto A. Então A sai do mix ótimo de produtos. Se C1 aumentar é possível que haja mudança do 
mix ótimo de produtos.
Determinaremos uma faixa de variação para C1, dentre a qual a solução ótima não é afetada. Uma 
mudança em C1 muda o vetor CB = (C1 C2). Note que os lucros relativos as variáveis básica (𝐶1 e 𝐶2) 
não são afetados e permanecem zero.
Entretanto o lucro relativo as variáveis não básicas ( 𝐶3, 𝐶4 e 𝐶5) vão mudar.
𝐶3= 1 - 𝐶1 3 −1
2
= C1 – 5
𝐶4 = 0 - 𝐶1 3 4
−1
= -4C1 + 3 
𝐶5 = 0 - 𝐶1 3 −1
1
= C1 – 3 .
Note que 𝐶3 ≤ 0, desde que C1 ≤ 5 , e também que 
𝐶4 ≤ 0 se C1 ≥
3
4
𝐶5 ≤ 0 se C1 ≤ 3
O tableau permanece ótimo desde que a variação de C1 esteja dentro dos limites impostos para 
todas as variáveis não básicas.
Se a faixa para C1 for escolhida como 
3
4
, 3 , então todo 𝐶𝑗 vai permanecer não positivo e 
consequentemente a solução presente 
X1 = 1, X2 = 2, X3 = 0 ainda é ótima. 
Caso 3- Mudança no coeficiente da função objetivo de variáveis básicas e não basicas
Suponha que no nosso exemplo a função objetivo mude para 
Z = X1 + 4X2 + 2X3
O efeito na solução ótima é verificado olhando se a linha 𝐶 permanece não positiva, temos 
𝐶1 = 𝐶2 = 0
𝐶3 = 2 - 1 4 −1
2
= -5 < 0
𝐶4 = 0 - 1 4 4
−1
= 0
𝐶5 = 0 - 1 4 −1
1
= -3 < 0
Então a solução ótima não muda, continua 
X1 = 1, X2 = 2, X3 = 0, mas o valor de Z se torna Z = 9
Mudança na constante (bi)
Suponha que o vetor de constantes muda de 1
3
para 2
3
. Esta mudança não afeta o tableau ótimo. 
A fim de estudar o efeito da variação do vetor de constantes é suficiente verificar se todas as 
constantes permanecem não negativas.
As colunas básicas correspondem as variáveis X1 e X2 no tableau inicial, então 
B = 
1
3
1
3
1
3
4
3
Como X4 e X5 são as variáveis básicas iniciais, 𝐵−1 possui as colunas correspondentes a estas 
variáveis no tableau ótimo, ou seja
𝐵−1 = 
4 −1
−1 1
O valor do novo vetor de constantes no tableau é 
 𝑏 = 
4 −1
−1 1
∙
2
3
= 
5
1
O novo valor do vetor de constantes no tableau passa a ser 
5
1
o qual é positivo. Então o tableau 
permanece ótimo, e o novo mix ótimo será 
X1 = 5, X2 = 1, X3 = 0 onde o max valor é Z = 13.
Observe que a solução ótima e o valor ótimo mudam, mas a base ótima não muda, isto é, ainda é 
interessante produzir somente os dois produtos A e B. 
Ainda analisando a mudança nas constantes, suponha agora que uma unidade extra de 
trabalho possa ser obtida permitindo hora extra que custa $4 para a companhia. A 
companhia quer saber se é interessante utilizar a hora extra.
Como o aumento no lucro é 13 − 8 = $5 que é maior que o custo da hora extra ($4), 
então é interessante usar a hora extra para se obter um aumento em uma unidade de 
trabalho. O aumento de $5 por unidade de aumento no recurso “trabalho” é chamado 
de “preço sombra da restrição de trabalho”.
• A solução dual ótima corresponde aos preços sombras das restrições do primal
No exemplo anterior, a solução dual ótima é dada por
𝑌10 𝑌20 = Multiplicadores simplex obtidos no tableau ótimo 
𝑌10 𝑌20 = 𝐶𝐵 ∙ 𝐵−1 = 2 3 ∙
4 −1
−1 1
=
5
1
Então a solução ótima dual é 𝑌10 = 5 e 𝑌20 = 1
O preço sombra reflete a variação líquida no valor de Z por unidade de aumento do recurso, desde 
que a variação no recurso não mude a base ótima. Então para usar o preço sombra de forma 
apropriada, temos que calcular a faixa de variação do recurso , de modo que a base ótima 
permaneça inalterada.
Seja b1 a quantidade de recurso disponível, e 𝑏∗ o novo vetor das constantes no tableau inicial, 
então 𝑏∗ = 
b1
3
. Para o tableau final permanecer ótimo, devemos ter 
𝐵−1 ∙ 𝑏∗ ≥ 0
4 −1
−1 1
∙
b1
3
≥ 0
4b1 − 3
−𝑏1 + 3
≥ 0
 
4𝑏1 − 3 ≥ 0
−𝑏1 + 3 ≥ 0
3
4
≤ 𝑏1 ≤ 3
X1 e X2 permanecem na base desde que o recurso trabalho varie entre 
3
4
e 3.
Note que a solução ótima e o valor ótimo mudam, a nova solução ótima será 
X1 = 4b1 - 3, X2 = −b1 +3, X3 = 0 e o lucro máximo 
Z = 2 4𝑏1 − 3 + 3 −𝑏1 + 3 = 5𝑏1 + 3
Ainda analisando o caso anterior, suponha agora que o trabalho seja aumentado para 4 unidades. 
Isso significa que os valores das constantes no tableau inicial serão 
4
3
. E consequentemente os 
novos valores das constantes no ultimo tableau serão 
13
−1
. Portanto , o último tableau não é mais 
ótimo. Temos
Note que o tableau anterior é infactível para o primal, mas é factível para o dual
CB
CJ
BASE
2
X1
3 
X2
1
X3
0 
X4
0 
X5 CONSTANTES
2 X1 1 0 -1 4 -1 13
3 X2 0 1 2 -1 1 -1
Linha 𝐶 0 0 -3 -5 -1 Z = 8
A nova solução ótima pode ser obtida pelo dual simplex, onde vemos que X2 sai da base e X4 entra 
na base. Após o pivoteamento, temos 
O tempo anterior é ótimo, já que as constantes são ≥ 0. O novo mix ótimo de produtos quando o 
trabalho é aumentado para 4 unidades é X1 = 9, X2 = X3 = 0 e o lucro máximo Z = 18.
CB
CJ
BASE
2
X1
3 
X2
1
X3
0 
X4
0 
X5 CONSTANTES
2 X1 1 4 7 0 3 9
0 X4 0 -1 -2 1 -1 1
Linha 𝐶 0 -5 -13 0 -6 Z = 8
Alteração nos elementos da matriz A
Caso 1- Adição de uma nova variável 
Suponha que a companhia avalia a possibilidade de produzir um novo produto D, que requer 1 
unidade de trabalho e 1 unidade de material. O novo produto pode ser vendido por $3. Vamos 
adicionar uma variável X6 e uma coluna 
1
1
no tableau inicial. O mix de produtos ótimos atual 
permanece ótimos desde que
C6 = C6 − 𝜋P6 ≤ 0
𝜋 = 𝐶𝐵 ∙ 𝐵−1 = 2 3 ∙
4 −1
−1 1
=
5
1
C6= 3 − 5 1 ∙ 1
1
= −3
Então o produzir D não melhora o valor atual do lucro, caso C6≥ 0 bastaria adicionar X6 na base e 
fazer 1 iteração do método simplex.
Caso 2- Variação nos requerimentos de recurso de uma atividade existente
• Quando os requerimentos de trabalho ou material de uma atividade não básica ( por exemplo X3
que corresponde a quantidade de produto C) mudam, o efeito pode ser estudado como no caso 1.
• Se os coeficientes das restrições de uma atividade básica mudam ( por exemplo X1 ou X2 referentes 
aos produtos A e B respectivamente), então a matriz base é afetada. Isso pode afetar todas as 
quantidades dadas no tableau ótimo atual. Nesse caso é melhor resolver o programa linear do 
zero.
Caso 3- Adição de uma nova variável 
Suponha que seja adicionada uma restrição de serviços administrativos ao problema, onde os 
produtos A, B e C requerem 1, 2 e 1 horas respectivamente. E suponha ainda que a quantidade de 
horas de serviços administrativos disponível seja de 10 horas, a nova restrição será
X1 + 2X2 + X3 ≤ 10
• Se a solução ótima atual satisfazer essa nova restrição, então essa solução continua ótima.
Observe que no nosso exemplo a solução ótima atual satisfaz a nova restrição e portanto o mix
ótimo de produtos não é alterado.
• Suponha que a nova restrição fosse 
X1 + 2X2 + X3 ≤ 4
A solução atual viola essa restrição, então o tableau atual não é mais ótimo. Usando X6 como a 
variável de folga para a restrição anterior, temos 
X1 + 2X2 + X3 + X6 = 4 . 
Após adicionada a ultima igualdade no tableau ótimo, teremos 
Observe que o tableau anterior não está naforma canônica, obtemos
CB
CJ
BASE
2
X1
3 
X2
1
X3
0 
X4
0 
X5
0
X6 CONSTANTES
2 X1 1 0 -1 4 -1 0 1
3 X2 0 1 2 -1 1 0 2
0 X6 1 2 1 0 0 1 4
Linha 𝐶 0 0 -3 -5 -1 0 Z = 8
CB
CJ
BASE
2
X1 
3 
X2
1
X3
0 
X4
0 
X5
0
X6 CONSTANTES
2 X1 1 0 -1 4 -1 0 1
3 X2 0 1 2 -1 1 0 2
0 X6 0 0 -2 -2 -1 1 -1
Linha 𝐶 0 0 -3 -5 -1 0
Aplicando o método do dual simplex, vemos que X6 sai da base e
Consequentemente X5 entra na base e, após o pivoteamento, temos
O novo mix ótimo de produtos é produzir 2 unidades de A e 1 unidade de B, e o lucro máximo foi 
reduzido de 8 para 7 devido a nova restrição.
Variáveis não básicas Yij 𝐶𝑗 Razão
X3 −2 −3 3
2
X4 −2 −5 5
2
X5 −1 −1 1
CB
CJ
BASE
2
X1
3 
X2
1
X3
0 
X4
0 
X5
0
X6 CONSTANTES
2 X1 1 0 1 6 0 -1 2
3 X2 0 1 0 -3 0 1 1
0 X5 0 0 2 2 1 -1 1
Linha 𝐶 0 0 -1 -3 0 -1 Z = 7
O princípio da decomposição de Dantizig-Wolfe
Considere o seguinte programa linear, onde X é um conjunto poliédrico não vazio e limitado.
Minimizar CX
Sujeito a AX = b
X ∈ X
Qualquer ponto X ∈ X pode ser representado como uma combinação convexa de um número finito 
de pontos extremos de X. Denotando esses pontos por X1, X2, . . . , Xt, qualquer X ∈ X pode ser 
representado como: 
𝑋 = 
𝑗=1
𝑡
𝜆𝑗 ∙ 𝑋𝑗
onde 
 
𝑗=1
𝑡
𝜆𝑗 = 1
𝜆𝑗 ≥ 0
𝑗 = 1, 2, . . . , 𝑡
Então o problema pode ser escrito como
Minimizar 𝑋 = 
𝑗=1
𝑡
(𝐶 ∙ 𝑋𝑗)𝜆𝑗
Sujeito a 
𝑗=1
𝑡
(𝐴 ∙ 𝑋𝑗)𝜆𝑗 = 𝑏
 
𝑗=1
𝑡
𝜆𝑗 = 1
𝜆𝑗 ≥ 0
𝑗 = 1, 2, . . . , 𝑡
Como X é um conjunto poliedral limitado, o valor máximo de qualquer programa linear sobre X
será atingido em um de seus pontos extremos. Portanto 
Máximo 𝑤𝐴 − 𝐶 𝑋𝑗 + α = Máximo 𝑤𝐴 − 𝐶 𝑋 + α
1 ≤ 𝑗 ≤ 𝑡 X ∈ X
Algoritmo de decomposição ( Problema de maximização)
Inicialização
Encontrar uma solução básica factível para o sistema definido por
 
𝑗=1
𝑡
(𝐴 ∙ 𝑋𝑗)𝜆𝑗 = 𝑏
 
𝑗=1
𝑡
𝜆𝑗 = 1
𝜆𝑗 ≥ 0
𝑗 = 1, 2, . . . , 𝑡
Seja B a base, forme o seguinte vetor 
𝑤 , α = 𝐶𝐵 ∙ 𝐵
−1
Definimos 𝐶𝑗 = 𝐶𝑋
𝑗 e 𝑏 = 𝐵−1
𝑏
1
.
𝐵−1 𝑏
(𝑤 , α) 𝐶𝐵 ∙ 𝑏
Passo principal
1- Resolva o problema 
Max 𝐶 − 𝑤𝐴 − α
Sujeito a X ∈ X
Seja 𝑋𝑘 a solução básica factível ótima com valor objetivo 𝐶𝑘. Se 𝐶𝑘 = 0 a solução básica factível do 
último problema mestre resolvido é ótima para o problema global. Caso contrário (𝐶𝑘 > 0), então 
vá para o passo 2.
2- Seja 𝑌𝑘 = 𝐵−1 𝐴𝑋
𝑘
1
Adicionamos 𝑌𝑘 ao tableau revisado. A variável 𝜆r que sai da base é determinada usando a regra da 
razão mínima. A matriz 𝐵−1, variáveis duais, vetor 𝑏 são atualizadas fazendo pivoteamento.
Exemplo numérico
Considere o seguinte exemplo
Minimizar Z = – 2X1 – X2 – X3 + X4 
X1 + X3 ≤ 2
X1 + X2 +2X4 ≤ 3
X1 ≤ 2
X1 + 2X2 ≤ 5 
– X3 + X4 ≤ 2
2X3 + X4 ≤ 6
X1≥0, X2 ≥0, X3 ≥0, X4 ≥0
Se considerarmos o X como o anterior, teremos
𝐴 =
1 0 1 0
1 1 0 2
e 𝑏 =
2
3
.
Consideremos 𝑆 ≥ 0 como o vetor de folga e 𝑋1, 𝑋2, . . . , 𝑋𝑡 como os pontos extremos de X, então 
 𝐶𝑗 = C ∙ 𝑋
𝑗 𝑗 = 1, 2, . . . , 𝑡
O problema reformulado será
𝑀𝑖𝑛 
𝑗=1
𝑡
 𝐶𝑗 ∙ 𝜆𝑗
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎 
𝑗=1
𝑡
(𝐴𝑋𝑗)𝜆𝑗 + 𝑆 = 𝑏
 
𝑗=1
𝑡
𝜆𝑗 = 1
𝜆𝑗 ≥ 0, 𝑗 = 1,2, . . . , 𝑡 𝑆 ≥ 0 .
Vamos começar com o ponto extremo 𝑋1 =
0
0
⋮
0
de X, então 
 𝐶1 = 𝐶 ∙ 𝑋1 = 0
Minimizar 0𝜆1
Sujeito a X1 + X3 + S1 = 2
X1 + X2 +2X4 + S2 = 3
𝜆1 = 1 .
Note que 𝐵 = 𝐼3, o vetor π , α = 𝐶𝐵 ∙ 𝐵
−1 = 0 ∙ 𝐵−1 = 01𝑥3 e 𝑏 = 𝐵
−1 𝑏
1
=
𝑏
1
Sub Problema 1
Min 𝐶 − 𝜋𝐴 𝑋 − α
s.a X ∈ X
ou seja
Min –2X1 –X2 –X3 + X4
s.a X ∈ X.
BASE 𝐵−1 𝑏
S1 1 0 0 2
S2 0 1 0 3
𝜆1 0 0 1 1
0 0 0 Z = 0
A solução ótima do sub problema 1 é 𝑋2 =
2
3
2
3
0
com valor ótimo −
17
2
. Então 𝑋2 é introduzido na 
base.
Novo problema mestre
𝐴𝑋2 =
1 0 1 0
1 1 0 2
∙
2
3
2
3
0
=
5
7
2
𝐴𝑋2
1
=
5
7
2
1
𝐵−1 ∙ 𝐴𝑋
2
1
=
5
7
2
1
.
Assim, como temos
Após o pivoteamento, teremos
BASE 𝐵−1 𝑏
S1 1 0 0 2
S2 0 1 0 3
𝜆1 0 0 1 1
0 0 0 Z = 0
𝜆2
5
7
2
1
BASE 𝐵−1 𝑏
𝜆2 1
5
0 0 2
5
S2 −7
10
1 0 8
5
𝜆1 −1
5
0 1 3
5
Consequentemente, a melhor solução factível até o momento é
𝑋 = 𝑋1𝜆1 +𝑋2𝜆2
𝑋 =
0
0
0
0
𝜆1 + 
2
3
2
3
0
𝜆2 =
4
5
3
5
6
5
0
.
Referências 
1- Hillier, F. S., and G. J. Lieberman, Introduction to Operations Research, 4th ed.,
Holden-Day, Inc., San Francisco, CA, 1986.
2- Bazaraa, M., Jarvis, J. and Sherali, H Linear Programming and Network Flows,
fourth edition, 2010, Wiley.