Apostila de Programação Linear do Prof João Antonio Vasconcelos

Prévia do material em texto

Programação Linear 
© Prof. João Antônio de Vasconcelos 1 
 Universidade Federal de Minas Gerais 
 
Departamento de Engenharia Elétrica 
 
 
 
 
Apostila de Programação Linear 
 
 
Prof. João Antônio de Vasconcelos 
 
Fev 2005 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 2 
Programação Linear – 1ª. Aula 
 
1) Problemas de Programação Matemática como Problemas de Otimização 
 
O que são Problemas de Otimização? 
Os problemas de Otimização são problemas de maximização ou minimização de funções de 
variáveis num determinado domínio normalmente definido por um conjunto de restrições nas 
variáveis. 
 
O que são problemas de programação matemática? 
Os problemas de Programação Matemática são uma classe particular de Problemas de 
Otimização aplicados nos campos da organização e da gestão econômica, em que o objetivo 
e as restrições são dadas como funções matemáticas e relações funcionais. 
 
A terminologia Programação Matemática tem sua origem na relação: 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 3 
Programação ⇔ planejamento de atividades. 
Matemática ⇔ o problema é representado por um modelo matemático composto de 
funções objetivo(s) e restrições dependentes das variáveis de decisão.. 
 
O problema é representado matematicamente pelo modelo: 
 
 0 x ,…,x ,x
b} ,,{ )x,… ,x ,x (g
b} ,,{ )x,… ,x ,x (g
b} ,,{ )x,… ,x ,x (g :a sujeito
)imize(max
)x,… ,x ,x f( Minimize
n21
mn21m
2n212
1n211
n21
≥
≥=≤
≥=≤
≥=≤
L
 (1) 
 
em que n21 x ,…,x ,x são as n variáveis de decisão, )x,… ,x ,x f( n21 é a função objetivo, )x,… ,x ,x (g n21i , 
para i = 1, 2, ..., m são as m restrições do problema. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 4 
Os problemas de Programação Matemática podem ser classificados em lineares, se f (x1, x2, 
…, xn ) , gi (x1, x2, …, xn ), para i = 1, 2, ..., m são funções lineares e em não-lineares, se alguma 
das relações f (x1, x2, …, xn ) ou gi (x1, x2, …, xn ), para i = 1, 2, ..., m for uma função não-linear. 
 
Os problemas de Programação Matemática como Problemas de Otimização abrangem a 
análise e estudo de sistemas de forma a determinar o programa de ação mais adequado ao 
alcance de certo objetivo, tendo em conta as restrições que limitam o seu comportamento. 
 
2) Problemas de Programação Linear como classe particular dos problemas de 
Programação Matemática – Definições básicas 
 
Os problemas de Programação Linear são uma classe particular de problemas de 
Programação Matemática, onde a função objetivo e as restrições são representadas por 
funções lineares. 
 
A terminologia Programação Linear tem sua origem na relação: 
Programação Linear 
© Prof. João Antônio de Vasconcelos 5 
 
Programação ⇔ planejamento de atividades. 
Linear ⇔ o problema é representado matematicamente pelo modelo em que todas as 
funções f (x1, x2, …, xn ) , gi (x1, x2 , … , xn ), são lineares. 
 
Os problemas de Programação Linear determinam o planejamento ótimo de atividades, ou 
seja, um plano ótimo que representa a melhor solução entre todas as soluções possíveis. 
 
Um problema de programação linear corresponde a uma programação matemática no qual a 
função objetivo é linear e as restrições consistem de igualdades e/ou desigualdades lineares. 
A forma exata dessas restrições pode diferenciar de um problema para outro, mas, de uma 
forma geral, a programação linear pode se transformar na seguinte forma padrão: 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 6 
 0 x ,…,x ,x
b x a + … + x a + x a
b x a + … + x a + x a
b x a + … + x a + x a :a sujeito
x c +… + x c + x c =z Minimize
n21
mnn m2m21m1
2n2n222121
1n1n212111
nn2211
≥
=
=
=
L
 (2) 
 
onde c1x1 + c2 x2 + …+ cn xn é a função objetivo a ser minimizada e será referida pela letra z. 
Os coeficientes c1, c2, …, cn são coeficientes de custo conhecidos e x1, x2, …, xn são as 
variáveis de decisão cujos valores devem ser determinados. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 7 
A igualdade i
n
1j
jij bxa =∑
=
 designa a i-ésima restrição. Os coeficientes aij, para i=1, 2, ... , m, 
j=1, 2, ... ,n são chamados de coeficientes tecnológicos. Estes coeficientes formam a matriz de 
restrição A. 
 








=
mn2mm
n2221
n11211
aaa
aaa
aaa
A
L
MMMM
L
L
 (3) 
 
O vetor coluna, cujo i-ésimo elemento é bi, é referido como “vetor do lado direito”, “vetor 
independente”, que representa as exigências mínimas a serem satisfeitas. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 8 
As restrições x1, x2,…, xn ≥ 0 são as restrições de não-negatividade. Um conjunto de variáveis x1, 
x2,…, xn satisfazendo todas as restrições é chamado de “ponto viável”, “ponto factível” ou 
“ponto realizável”. 
 
O conjunto de todos os pontos viáveis constitui a região realizável ou espaço viável. 
 
Usando essa terminologia, o problema de programação linear pode ser estabelecido como 
segue: “dentre todos os pontos viáveis, encontre um que minimize (ou maximize) a função 
objetivo”. 
 
 
Exemplo1: Considere o problema seguinte: 
 
 0 x ,x
18 - 2x - -x
6 x + x :a sujeito
 x 5 + 2x =z Minimize
21
21
21
21
≥
≥
≥
 (4) 
Programação Linear 
© Prof. João Antônio de Vasconcelos 9 
 
Neste caso, temos duas variáveis de decisão x1 e x2. A função objetivo a ser minimizada é 2 
x1+ 5x2. As restrições e a região viável são ilustradas na figura a seguir. 
 
Fig. 1 Região viável e restrições – Exemplo 1. 
 
[0 9]T
[18 0]T[6 0]T
[0 6]T
0 
X2≥ 0
X1≥ 0
Região 
Viável
21
Programação Linear 
© Prof. João Antônio de Vasconcelos 10 
O problema de otimização é dessa maneira o problema de encontrar um ponto na região 
viável com o menor valor da função objetivo. 
 
Suposições da Programação Linear 
Para representar um problema de otimização como um problema de programação linear, 
várias suposições implícitas à formulação da programação linear discutida anteriormente são 
necessárias. Estas suposições são: 
 
1. Proporcionalidade: Dada uma variável jx , sua contribuição para formar o custo cjxj e 
sua contribuição para a i-ésima restrição é jij xa . Isto significa que se jx é aumentado de 
duas vezes, também o é a sua contribuição para o custo e para cada uma das restrições. 
2. Aditividade: Esta suposição garante que o custo total é a soma dos custos individuais, e 
que a contribuição total à i-ésima restrição é a soma das contribuições individuais das 
atividades individuais. Em outras palavras, não há substituição ou efeitos de interação 
entre atividades. 
Programação Linear 
© Prof. João Antônio de Vasconcelos 11 
3. Divisibilidade: Esta suposição assegura que as variáveis de decisão podem ser 
divididas em qualquer nível fracionário. Isto é, elas podem assumir valores não-inteiros. 
4. Determinístico: Os coeficientes jc , ija e jb são todos conhecidos deterministicamente. 
Qualquer elemento probabilístico, estocástico, inerente à demanda, aos custos, preços, 
disponibilidade de recursos, e assim por diante, são todos assumidos serem 
aproximados por um destes coeficientes através de algum procedimento determinístico. 
 
Manipulação do Problema – 2ª. Aula 
Quando as restrições de um modelo de Programação Linear são apresentadas na forma de 
inequações, diz-se que esse modelo está na forma canônica. Abaixo encontram-se alguns 
métodos de conversão forma canônica – forma padrão. 
 
1º Caso: Introdução de variáveis de folga 
Considere o problema formulado na forma canônica abaixo: 
Programação Linear 
© Prof. João Antônio de Vasconcelos 12 
 0 x ,…,x ,x
b x a + … + x a + x a
b x a + … + x a + x a
b x a + … + x a + x a :a sujeito
x c +… + x c + x c =z Maximize
n21
mnn m2m21m1
2n2n222121
1n1n212111
nn2211
≥
≤
≤
≤
L
 (5) 
 
 
Nesse caso, o conjunto de restrições é determinadointeiramente pelas desigualdades 
lineares. Mediante operações, é possível transformar o problema acima para a forma padrão. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 13 
 0 x ..., ,x ,…,x ,x
b xx a + … + x a + x a
b x x a + … + x a + x a
b xx a + … + x a + x a :a sujeito
x c +… + x c + x c =z Maximize
mnn21
mmnnn m2m21m1
22nn2n222121
11nn1n212111
nn2211
≥
=+
=+
=+
+
+
+
+
L
 (6) 
 
As novas variáveis positivas mn2n1n x,....,x,x +++ introduzidas para converter as 
desigualdades em igualdades são chamadas de variáveis de folga. O novo problema com n + 
m incógnitas se encontra na forma padrão. A matriz m x (m + n) que agora descreve as 
restrições de igualdade lineares é da forma especial [A, I] (ou seja, as colunas podem ser 
separadas em dois conjuntos; as primeiras n colunas se originam da matriz original A, e as 
últimas m colunas se originam de uma matriz identidade (m x m). 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 14 
2º caso: Variáveis ‘Surplus’ (Excesso) 
Considere o problema formulado na forma canônica abaixo: 
 
 0 x ,…,x ,x
b x a + … + x a + x a
b x a + … + x a + x a
b x a + … + x a + x a :a sujeito
x c +… + x c + x c =z Minimize
n21
mnn m2m21m1
2n2n222121
1n1n212111
nn2211
≥
≥
≥
≥
L
 (7) 
 
 
Essa forma é equivalente a: 
Programação Linear 
© Prof. João Antônio de Vasconcelos 15 
 0 x ..., ,x ,…,x ,x
b xx a + … + x a + x a
b x x a + … + x a + x a
b xx a + … + x a + x a :a sujeito
x c +… + x c + x c =z Maximize
mnn21
mmnnn m2m21m1
22nn2n222121
11nn1n212111
nn2211
≥
=−
=−
=−
+
+
+
+
L
 (8) 
 
3º Caso: Variáveis Livres 
 
Se um problema de programação linear é dado na forma padrão exceto que uma ou mais 
variáveis desconhecidas não são restringidas pela condição de não-negatividade, o problema 
poderá ser transformado na forma padrão utilizando-se duas técnicas. Para mostrarmos isto, 
considere o problema: 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 16 
 0 x,...,x,x ,…,x ,x
b x a + … + x a + x a
b x a + … + x a + x a
b x a + … + x a + x a :a sujeito
x c +… + x c + x c =z Minimize
n1j-1j21
mnn m2m21m1
2n2n222121
1n1n212111
nn2211
≥
=
=
=
+
L
 (9) 
 
1) Suponha que no problema anterior, a restrição xj ≥ 0 não esteja presente. Dessa forma, 
pode-se escrever: 
 
jjj xxx ′′−′= (10) 
Programação Linear 
© Prof. João Antônio de Vasconcelos 17 
em que se requer x´j ≥ 0 e x´´j ≥ 0. Se nós substituirmos xj por jj xx ′′−′ em todo o 
problema, a linearidade das restrições é preservada e todas as variáveis são agora não-
negativas. 
 
 
 
2) Uma segunda maneira para converter à forma padrão quando xj é livre, consiste em 
eliminar xj juntamente com uma das equações de restrição. Por exemplo, seja a i-ésima 
equação abaixo: 
 
ininjij2i21i1 b x a + … x a + …+ x a + x a = (11) 
 
onde aij ≠ 0. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 18 
Então xj pode ser expressa como uma combinação linear das outras variáveis mais uma 
constante. 
 
ijnin2i21i1ij a/)] x a + ……+ x a + x a([b x −= (12) 
 
Se essa expressão substituir xj em todas as equações, teremos um novo problema 
expresso em função de x2, x3, ..., xn. Como resultado, teremos agora um problema de 
programação linear com n – 1 variáveis e m – 1 equações de restrições. O valor de xj 
pode ser determinado a partir de (12). Este segundo procedimento é raramente utilizado 
devido às dificuldades de manipulação de dados e implementação numérica. 
 
4º Caso: Variáveis Limitadas Inferior ou Superiormente 
Se xj ≥ lj, então a nova variável x´j ≥ xj - lj é automaticamente não-negativo. Por outro lado, se 
xj ≤ uj , então a nova variável x´j ≥ uj - xj produz uma variável x´j não-negativa. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 19 
Transformação de Problemas de Minimização em Maximização 
É interessante notar que qualquer problema de maximização (minimização) pode converter-se 
num problema de minimização (maximização), pois: 
 = z) (- mínimo - z máximo (13) 
 = ∑∑
==
n
1j
jj
n
1j
jj xc- mínimo - xc máximo
 (14) 
Assim, um problema de maximização (minimização) pode ser convertido em um problema de 
minimização (maximização) através da multiplicação dos coeficientes da função objetivo por -
1. Depois de concluída a otimização do novo problema, a função objetivo do problema original 
é igual -1 vez o valor ótimo da função objetivo do novo problema. 
 
Forma Padrão e Forma Canônica 
Da discussão anterior, vemos que um dado problema linear pode ser colocado em diferentes 
formas equivalentes através de manipulações adequadas. Duas formas em particular serão 
Programação Linear 
© Prof. João Antônio de Vasconcelos 20 
úteis: forma padrão e forma canônica. Um problema é dito estar na forma padrão quando 
todas as restrições são de igualdade e todas as variáveis são não-negativas. O método 
simplex foi projetado para ser aplicado somente após o problema ser colocado na forma 
padrão. 
 
A forma canônica é também útil especialmente na exploração de relações de dualidade. Um 
problema de minimização se encontra na forma canônica se todas as variáveis são não-
negativas e todas as restrições são do tipo ≥. Um problema de maximização está na forma 
padrão se todas as variáveis são não-negativas e todas as restrições são do tipo ≤. A Tabela I 
a seguir faz um resumo destas discussões. 
 
 
Tabela I: Sumário da Manipulação do Problema de Programação Linear 
 
Forma Minimização Maximização 
Programação Linear 
© Prof. João Antônio de Vasconcelos 21 
Padrão 
n,...,1j 0 x 
m,...,1ib x a :a sujeito
x c =z Minimize
j
i
n
1j
jij
n
1j
jj
=≥
==∑
∑
=
=
n,...,1j 0 x 
m,...,1ib x a :a sujeito
x c =z Maximize
j
 i
n
1j
jij
n
1j
jj
=≥
==∑
∑
=
=
Canônica
n,...,1j 0 x 
m,...,1ib x a :a sujeito
x c =z Minimize
j
i
n
1j
jij
n
1j
jj
=≥
=≥∑
∑
=
=
 
n,...,1j 0 x 
m,...,1ib x a :a sujeito
x c =z Maximize
j
i
n
1j
jij
n
1j
jj
=≥
=≤∑
∑
=
=
 
 
 
 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 22 
Programação Linear em Notação Matricial 
O problema de programação linear pode ser escrito em uma forma mais conveniente usando 
notação matricial. Para ilustrar, considere o problema seguinte: 
 
 
n,...,1j 0 x 
m,...,1ib x a :a sujeito
x c =z Minimize
j
i
n
1j
jij
n
1j
jj
=≥
==∑
∑
=
=
 (15) 
 
Chamando o vetor linha (c1, c2, ..., cn) por c, e considerando os seguintes vetores x e b, e a 
matriz A de ordem mxn, 
 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 23 








=








=








=
mn2m1m
2n2221
1n2111
m
2
1
n
2
1
aaa
aaa
aaa
b
b
b
x
x
x
Abx
 (16) 
 
o problema pode ser escrito como segue: 
 
 
0x
bx
cx
 
A :a sujeito
 =z Minimize
≥
=
 (17) 
 
O problema pode também ser convenientemente representado via colunas da matriz A. 
Representando A por [a1, a2, ..., am], onde aj é a j-ésima coluna de A, o problema pode ser 
formulado como segue: 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 24 
 
n,...,1j 0 x 
 x :a sujeito
x c =z Minimize
j
n
1j
jj
n
1j
jj
=≥
=∑
∑
=
=
ba
 (18) 
 
 
 
Onde x é um vetor n-dimensional coluna, A é uma matriz m x n e b é um vetor m-dimensional 
coluna. O vetor desigualdade x ≥ 0 determina que cada componente de x é não-negativo. 
 
 
 
 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 25 
Modelagem de Problemas de Programação Linear e Exemplos – 3ª. Aula 
 
Exemplo I : Problema da Dieta 
Umnutricionista deve elaborar uma dieta contendo pelo menos 10 unidades de vitamina A, 30 
unidades de vitamina B e 18 unidades de vitamina C, contidas em 5 alimentos. O alimento S1 
contém 0 unidade de vitamina A, 2 unidades de vitamina B, 3 unidades de vitamina C e custa 
R$4,00 por quilograma. O alimento S2 contém 1 unidade de vitamina A, 1 unidade de vitamina 
B, 1 unidade de vitamina C e custa R$2,00 por quilograma. O alimento S3 contém 5 unidades 
de vitamina A, 0 unidade de vitaminas B e C, e custa R$1,00 por quilograma. O alimento S4 
contém 4 unidades de vitamina A, 3 unidades de vitamina B, 9 unidades de vitamina C e custa 
R$10,00 por quilograma. O alimento S5 contém 3 unidades de vitamina A, 2 unidades de 
vitamina B, 0 unidades de vitamina C e custa R$5,00 por quilograma. 
 
Qual é o custo mínimo para se atender à dieta estabelecida pelo nutricionista? 
 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 26 
Formulação do Problema: 
Os dados referentes aos alimentos S1, S2, S3, S4 e S5 podem ser convenientemente escritos 
em uma tabela. Veja Tabela II. 
 
Tabela II: Dados dos Alimentos S1, S2, S3, S4 e S5. 
 
Observando a Tabela II, podemos formular o problema considerando x1, x2, ..., x5 como sendo 
as variáveis de decisão, isto é, as quantidades dos alimentos S1, S2, ..., S5 que devem ser 
utilizados para compor a dieta de custo mínimo. 
Alim S1 S2 S3 S4 S5 
A 0 1 5 4 3 
B 2 1 0 3 2 
C 3 1 0 9 0 
Custo 4 2 1 10 5 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 27 
 
Assim, a formulação do problema pode ser escrita como: 
 
 0 x ,x ,x ,x ,x
18x 0x90x + x 1 + x 3
30x 2x30x + x 1 + x 2
10x 3x45x + x 1 + x 0 :a sujeito
x 5x 01x + x 2 + x 4 =z Minimize
54321
54321
54321
54321
54321
≥
≥++
≥++
≥++
++
 (19) 
 
 
 
Exemplo II : Problema do Transporte 
Quantidades a1, a2, ..., am, respectivamente, de um certo produto devem ser transportadas de 
cada uma das m localidades origem para n localidades destino nas quantidades b1, b2, ..., bn. 
O custo/unidade de produto transportado da localidade i para a localidade j é cij. Deseja-se 
Programação Linear 
© Prof. João Antônio de Vasconcelos 28 
determinar as quantidades xij a serem transportadas entre cada par origem-destino i = 1, 2, ..., 
m; j = 1,2, ..., n; de tal forma a satisfazer às exigências de transporte e minimizar o custo total 
associado. 
 
Formulação do Problema : Seja xij a quantidade do produto a ser transportado da cidade 
origem i para a cidade destino j. Assim, os dados do problema do transporte pode ser 
resumidamente escritos na Tabela III. 
 
Tabela III : Dados do problema do transporte de produtos entre m cidades origem para n 
cidades destino. 
 Destino 
Origem 1 2 ... n Soma 
1 X11 x12 ... X1n a1 
2 X21 X22 ... X2n a2 
... ... ... ... ... ... 
Programação Linear 
© Prof. João Antônio de Vasconcelos 29 
m Xm1 Xm1 ... Xmn am 
Soma b1 b2 ... bn 
 
 
Assim, a formulação do problema pode ser escrita como: 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 30 
.n,...,2,1j
;m,...,2,1i0x
ba
n,...,2,1jbx
m,...,2,1iax
:asujeito
xczimizemin
ij
n
1j
j
m
1i
i
j
m
1i
ij
i
n
1j
ij
m
1i
n
1j
ijij
=∀
=∀≥
=
=∀=
=∀=
=
∑∑
∑
∑
∑∑
==
=
=
= =
 (20) 
 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 31 
 
 
 
 
Exemplo III: Problema da Fábrica 
Uma empresa pode fabricar dois produtos (1 e 2). Na fabricação do produto 1, a empresa 
gasta 9 horas-homem e 3 horas-máquina. Na fabricação do produto 2, a empresa gasta 1 
hora-homem e 1 hora-máquina. Sendo x1 e x2 as quantidades fabricadas dos produtos 1 e 2 e 
sabendo-se que a empresa dispõe de 18 horas-homem e 12 horas-máquina e ainda que os 
lucros por unidade do produto x1 e x2 são R$4,00 e R$1,00, respectivamente, quanto deve a 
empresa fabricar de cada produto para obter o maior lucro possível? 
 
Formulação do Problema : As variáveis de decisão já foram dadas, x1 e x2. Os dados deste 
problema podem ser esquematicamente escritos na Tabela IV. 
 
 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 32 
Tabela IV : Dados do problema de produção para maximização dos lucros. 
 Produto 
Tempo x1 x2 Total disponível 
Horas-homem 9 1 18 
Horas-máquina 3 1 12 
Lucro/unid 4 1 
Este problema possui a seguinte representação matemática: 
0x,x
12xx3
18xx9:asujeito
xx4zMaximize
21
21
21
21
≥
≤+
≤+
+=
 (21) 
 
O desenvolvimento desse problema resulta no valor máximo da função objetivo x1* = 1, x2* = 9 
e z = R$13,00. Tente resolvê-lo. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 33 
Exemplo IV: Problema da Refinaria de Petróleo 
Uma refinaria de petróleo destila óleo cru, proveniente de duas fontes: Arábia Saudita e 
Venezuela, e produz três produtos: gasolina, querosene e lubrificantes. Os óleos têm 
diferentes composições químicas e fornecem diferentes quantidades de destilados por barril 
processado. Cada barril da Arábia dá 0,3 barril de gasolina, 0,4 de querosene e 0,2 de 
lubrificante. Para o barril proveniente da Venezuela estas quantidades são respectivamente: 
0,4, 0,2 e 0,3. Em ambos os casos há 10% de resíduos. Os óleos diferem em custo e 
disponibilidade. A refinaria pode comprar até 9000 barris da Arábia a $ 20,00 o barril e até 
6000 barris da Venezuela a $ 15,00 o barril. Contratos da refinaria com distribuidores exigem 
que ela produza 2000 barris por dia de gasolina, 1500 de querosene e 500 de lubrificantes. 
Como cumprir os contratos gastando o mínimo? 
 
Formulação do Problema : As variáveis de decisão são obviamente as quantidades de óleo 
cru a serem adquiridas da Arábia Saudita e Venezuela. Sejam estas variáveis x1 e x2 em 
número de mil-barris/dia, respectivamente. Os dados deste problema podem ser 
esquematicamente escritos na Tabela V. 
Programação Linear 
© Prof. João Antônio de Vasconcelos 34 
 
 
Tabela V : Dados do problema de produção para maximização dos lucros. 
 Quantidade de Óleo Cru 
 Arábia Saudita (X1) Venezuela (x2) 
Quantidade a ser 
produzida 
Gasolina 0,3 0,4 2000 
Querosene 0,4 0,2 1500 
Lubrificantes 0,2 0,3 500 
Compra 
Possível 9000 6000 
Custo 20 15 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 35 
( )
( )
( )
( )
( )
( )denegatividaNão0x,x
Venezuela6000x
SauditaArábia9000x
tesLubrifican500x3,0x2,0
Querosene1500x2,0x4,0
Gasolina2000x4,0x3,0:asujeito
x15x20zMinimize
21
2
1
21
21
21
21
−≥
≤
≤
≥+
≥+
≥+
+=
 (22) 
 
A solução ótima deste problema é x1* = 2000, x2* = 3500 a um custo mínimo de US92.500,00. 
Tente resolvê-lo. 
 
 
 
 
 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 36 
Solução Geométrica 
A solução geométrica é adequada para problemas pequenos, de duas ou no máximo três 
variáveis. A grande vantagem da solução geométrica é permitir a visualização do problema. 
 
Para apresentarmos este tema, considere o problema abaixo. 
 
 0 x
b xA :a sujeito
xc Minimize T
rr
rr
rr
≥
≥
 (23) 
Observe que a região viável é formada por todo vetor xrsatisfazendo ao sistema b xA
rr ≥ e 
0 x
rr ≥ . Dentre todos estes pontos, nos interessamos por determinar um que conduza ao 
mínimo valor para xcT
rr
. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 37 
Note que pontos cujo valor da função objetivo é z, satisfazem a xcT
rr
= z, ou zxc
n
1j
jj =∑
= . Uma 
vez que desejamos minimizar z, então o plano (linha em espaço 2D) zxc
n
1j
jj =∑
= deve ser 
deslocado paralelamente a ele próprio na direção que minimiza a função objetivo. Esta 
direção é c
r− . Veja a representação na figura abaixo. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 38 
 
Fig. 2 Solução geométrica do PPL. 
 
É fácil notar que o ponto ótimo [ ]T*2*1 x,x*x rrr = é um entre os cinco vértices, os quais são 
chamados de pontos extremos. 
cr 12211 zxcxc =+
22211 zxcxc =+
Região 
Viável32211 zxcxc =+
42211 zxcxc =+
Diminuição da 
função 
X2
X1
[X1*, X2*]T 
Programação Linear 
© Prof. João Antônio de Vasconcelos 39 
 
Mostraremos mais adiante que se um problema de programação linear na forma padrão ou 
canônica tem uma solução ótima finita, então ele possui um ponto ótimo no vértice ou ponto 
extremo ótimo. 
 
Exemplo 2: Considere o problema seguinte: 
 
 0 x ,x
8 2x -x
6 x + x :a sujeito
 x 3 - x- =z Minimize
21
21
21
21
≥
≤+
≤
 (24) 
Programação Linear 
© Prof. João Antônio de Vasconcelos 40 
‘ 
Fig. 3 Solução geométrica do PPL do Exemplo 2. 
 
A região viável é ilustrada na Fig. 3. Para construir esta região, considere a segunda restrição 
8 2x x- 21 ≤+ . A equação associada a esta restrição é 8 2x x- 21 =+ . O gradiente desta 
[4/3 14/3]T
[6 0]T 
[0 4]T
[0 
[0 
X2≥ 0
X1≥ 0
Região 
Viável
2
10x 3 - x- 21 =
3/46x 3 - x- 21 −=
Diminuição da 
função objetivo
T]3,1[c −−=r
Programação Linear 
© Prof. João Antônio de Vasconcelos 41 
função é [-1 2]T. Logo, a função 21 2x x- + aumenta nesta direção e diminui na direção 
contrária, isto é, na direção [1 -2]T. Consequentemente, a região viável a 8 2x x- 21 ≤+ 
relativa à equação 8 2x x- 21 =+ é mostrada na Fig. 2 e compreende pontos na região de 
diminuição de 21 2x x- + . As restrições de não-negatividade de x1 e x2 restringem a busca ao 
primeiro quadrante do sistema de coordenadas. As equações ctez x 3 - x- 21 == são 
denominadas de equipotenciais da função objetivo e são representadas pelas linhas 
tracejadas. A solução ótima deste problema é naturalmente o vértice definido pelo ponto [4/3 
14/3]T para o qual z* = -46/3. 
 
 
Classificação das Soluções 
O objetivo da PL é determinar entre as soluções viáveis uma que seja a “melhor” medida pelo 
valor da função objetivo do modelo. Por "melhor" entende-se o maior ou menor valor da 
função objetivo, dependendo se o modelo é de maximizar ou de minimizar. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 42 
Ao solucionar um problema de PL, podemos ter várias situações possíveis. No exemplo 
anterior tivemos uma única solução ótima. Outros casos possíveis são resumidos a seguir 
para problemas de minimização. 
 
Única solução ótima finita: se a solução ótima é finita e única então ela ocorre em um ponto 
extremo. 
Programação Linear 
© Prof. João Antônio de Vasconcelos 43 
 
Fig. 4.a - Solução ótima única e finita (região limitada). 
 
Região 
Viável
2 
1 
 
Diminuição da 
função objetivo
cr
 
0x2 ≥
0x1 ≥ Solução ótima finita 
Programação Linear 
© Prof. João Antônio de Vasconcelos 44 
 
 
Fig. 4.b - Solução ótima única e finita (região ilimitada). 
 
Região 
Viável
2
1
 
 
Diminuição da 
função objetivo
cr
0x2 ≥
0x1 ≥ Solução ótima finita 
Programação Linear 
© Prof. João Antônio de Vasconcelos 45 
Infinitas soluções ótimas finitas: Este é o caso ilustrado na Fig. 5. No caso (a), a região 
viável é limitada. Os dois vértices x1* e x2* são soluções ótimas, bem como qualquer outro 
ponto sobre o segmento unindo-os. 
 
Fig. 5.a – Infinitas soluções ótimas (região limitada). 
Região 
Viável
2 
1
 
Diminuição da 
função objetivo
cr
 
0x2 ≥
0x1 ≥
Solução ótima finita x1* 
3 Solução ótima finita 
x2* 
Programação Linear 
© Prof. João Antônio de Vasconcelos 46 
 
Fig. 5.b – Infinitas soluções ótimas (região ilimitada). 
 
Em 5.b, a região viável é ilimitada. O vértice indicado é ponto ótimo, bem como qualquer outro 
sobre a fronteira ótima. 
Região 
Viável
2
1
 
 
Diminuição da 
função objetivo
cr
0x2 ≥
0x1 ≥ Solução ótima finita Fronteira ótima 
Programação Linear 
© Prof. João Antônio de Vasconcelos 47 
 
Valor da função objetivo na solução ótima ilimitado: Este caso é ilustrado pela Fig. 6, 
onde a região e o ótimo são ilimitados. Para o problema de minimização, o plano xcT
rr
 = z 
pode ser deslocado na direção xcT
rr
 indefinidamente e sempre estará interceptando a região 
viável. O valor ótimo é z* = - ∞ e nenhuma solução ótima existe. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 48 
 
Fig. 6 – Valor da função objetivo no ótimo é ilimitado (região ilimitada). 
 
 
 
Região 
Viável
2
1
 
 
Diminuição da 
função objetivo 
cr
0x1 ≥
0x2 ≥
Programação Linear 
© Prof. João Antônio de Vasconcelos 49 
Região Viável Vazia: Neste caso o sistema de equações e ou inequações definindo a região 
viável é inconsistente. Para ilustrar isto, considere o problema a seguir: 
 
 0 x ,x
4 x
3 x 2x
2 2x + x- :a sujeito
 x 3 2x- =z Minimize
21
2
21
21
21
≥
≥
≤−
≤
+
 (25) 
 
Observando a Fig. 7, percebemos claramente que não há nenhum ponto viável, isto é, 
nenhum ponto (x1, x2) satisfaz ao conjunto de desigualdades. O problema é dito ser inviável, 
inconsistente, ou com uma região viável vazia. 
Programação Linear 
© Prof. João Antônio de Vasconcelos 50 
 
Fig. 7 – Região viável vazia. 
 
 
 
 
 
0x1 ≥ 
0x2 ≥ 
2x2x 21 ≤+−
4x2 ≥
3xx2 21 ≤−
[8/3 7/3]T 
[0 4]T 
[0 0]T 
Programação Linear 
© Prof. João Antônio de Vasconcelos 51 
Interpretação Espacial – 4ª. Aula 
O problema de programação linear pode ser geometricamente resolvido em outro espaço, 
como veremos a seguir. 
 
Interpretação de Viabilidade 
Considere o problema de programação linear na forma padrão: 
 
 0 x
b xA :a sujeito
xc Minimize T
rr
rr
rr
≥
=
 (26) 
onde A é uma matriz mxn cuja e-ésima coluna é ja
r . Este problema pode ser re-escrito como: 
Programação Linear 
© Prof. João Antônio de Vasconcelos 52 
 n ..., 1,2,j0 x
b xa :a sujeito
xc Minimize
j
n
1j
jj
n
1j
jj
=≥
=∑
∑
=
=
rr
 (27) 
 
Dado os vetores n21 a....,,a,a
rrr
, desejamos encontrar valores não-negativos n21 x....,,x,x 
tais que b xa
n
1j
jj
rr =∑
= e ainda que 
∑
=
n
1j
jj xc seja minimizado. Note que o conjunto de vetores 
da forma ∑=
n
1j
jj xa
r
, onde n21 x....,,x,x é o cone gerado por n21 a....,,a,a
rrr
. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 53 
 
Fig. 8.a – Região viável não vazia. Fig. 8.b – Região viável vazia. 
 
Assim, o problema possuirá uma solução viável somente se o vetor b
r
pertencer ao cone 
gerado pelo conjunto de vetores ja
r
. Desde que o vetor b
r
 usualmente representa exigências 
a serem satisfeitas, o espaço das figuras (a) e (b) acima é denominado de espaço das 
exigências. 
1a
r 
3a
r
4a
r
2a
r
b
r
1a
r
3a
r
4a
r
2a
r
b
r
Programação Linear 
© Prof. João Antônio de Vasconcelos 54 
 
Exemplo: Considere os dois sistemas dados a seguir: 
S1 S2 
 
 0 x ,x ,x ,x
3x 3x x-
2x x 2x
4321
421
321
≥
=++
=++
 0 x ,x ,x ,x
2x 3x x-
1x x 2x
4321
421
321
≥
=++
−=++
 (28) 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 55 
 
 
Fig. 9 (a) – Consistente ou região viável não-vazia, 
 9 (b) – Inconsistente ou região viável vazia. 
 
 
4a
r 2a
r
3a
r
b
r
1a
r
4a
r 2a
r
3a
r
b
r
1a
r
Programação Linear 
© Prof. João Antônio de Vasconcelos 56 
Conceitos Fundamentais 
A introdução dos conceitos fundamentais abaixo descritos é necessária para a compreensão 
do Método Simplex. Alguns destes conceitos já foram introduzidos. No entanto, a repetição de 
alguns deles contribui para a melhor compreensão do Método Simplex. 
 
Dado um problema de Programação Linear na forma padrão: 
 n ..., 1,2,j0 x
b xa :a sujeito
xc Minimize
j
n
1j
jj
n
1j
jj
=≥
=∑
∑
=
=
rr
 (29) 
A constante m é o número de restrições funcionais e n o número de variáveis de decisão. 
 
Supomos ainda que os termos independentes sejam não negativos: bi ≥ 0 (i = 1,2,…m), caso 
contrário pode-se sempre multiplicar por (-1) toda a equação. 
Programação Linear 
© Prof. João Antônio de Vasconcelos 57 
 
Definições: 
1. A função a minimizar, z = c1x1 + c2 x2 + …+ cn xn , designa-se por função objetivo. 
2. As equações (inequações) designam-se por restrições. 
3. As desigualdades x1 ≥ 0, x2 ≥ 0,…, xj ≥ 0,…, xn ≥ 0 designam-se por condições de 
não-negatividade. 
4. As variáveis (x1, x2,…, xj,…, xn ) designam-se por variáveis de decisão. 
5. Qualquer especificação de valores para as variáveis de decisão (x1, x2,…, xj,…, xn) 
que satisfaça as restrições do modelo e as condições de não-negatividade designa-se 
por solução viável. 
6. O conjunto de todas as soluções viáveis designa-se por conjunto de viabilidade ou 
região de viabilidade. 
7. Uma solução ótima minimiza (ou maximiza) a função objetivo sobre toda a região 
viável. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 58 
Definição 1. Qualquer conjunto de valores para as variáveis (x1, x2,…, xn) que satisfaça 
as restrições do modelo 
ba x 
n
1j
jj =∑
= (30) 
designa-se por solução. 
 
Definição 2. Se, além disso, a solução x = (x1, x2,…, xn) verificar as restrições de não-
negatividade, n,...,1j para 0 x j =≥ , designa-se por solução viável. 
 
O sistema (30) é constituído por m equações e n incógnitas, onde m ≤ n. Suponha-se que a 
característica1 da matriz A do sistema seja igual a m. Isto significa que existe uma sub-matriz 
quadrada de ordem m (Bmxm) com determinante não-nulo. Esta sub-matriz permite efetuar 
 
1 Chama-se característica de uma matriz Amxn ao número máximo de colunas que são linearmente independentes. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 59 
uma classificação das variáveis em básicas (as correspondentes às colunas da sub-matriz B) 
e não-básicas (as restantes n – m variáveis). Veja Eq. (31). 
[ ] b
b
b
b
x
x
IB
x
x
x
x
x
a
a
a
aaaa
aaaa
aaaa
Ax
m
2
1
N
B
n
1m
m
2
1
mn
n2
n1
1mmmm2m1m
1m2m22221
1m1m11211
=






=



=






















=
+
+
+
+
M
M
LL
MMMMMM
LL
LL
 (31) 
 Um sistema nestas condições é um sistema indeterminado de grau n-m, em que m variáveis 
podem ser escritas em termo das restantes n – m, e tem, por conseqüência, uma infinidade de 
soluções (correspondente à infinidade de valores que arbitrariamente podem ser atribuídos às 
n - m variáveis). 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 60 
Suponha-se então que x = (x1, x2,…, xm, xm+1, xm+2,…, xn ) seja uma solução do sistema de 
equações (31). 
 
Definição 3. Se uma sub-matriz Bmxm da matriz A do sistema (31) é não-singular, i.e., o 
seu determinante é não nulo, então designa-se por base a sub-matriz Bmxm. 
 
Para simplificar a notação suponha que a base B é composta pelas m primeiras colunas, i.e., 
B = {a1 , a2 ,..., am}. 
 
Definição 4. As m variáveis x1 , x2,…, xm correspondentes às colunas de Bmxm 
designam-se por variáveis básicas. Seja o vetor de variáveis básicas o vetor xB 
 
Definição 5. As restantes n-m variáveis xm+1 ,xm+2,…,xn designam-se por variáveis não 
básicas. Seja o vetor de variáveis não básicas o vetor xN. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 61 
 
Definição 6. Uma solução básica para o sistema (31) obtém-se atribuindo o valor 
zero às variáveis não básicas xm+1 , xm+2 ,…, xn , e determinando, depois, uma solução para as 
m variáveis básicas restantes x1 , x2,…, xm , i.e., x = (x1 , x2 ,… , xm , 0, …,0), onde xB =(x1 , x2 
,…, xm) é a única solução do sistema de equações BxB = b. 
 
Definição 7. Se todas as variáveis básicas x1 , x2 ,…, xm são não-nulas, a solução 
básica designa-se por solução básica não degenerada. 
 
Definição 8. Se alguma variável básica for igual a zero a solução básica designa-se 
por solução básica degenerada. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 62 
Definição 9. Se uma solução básica x verifica ainda as condições de não-negatividade 
n,...,1j para 0 x j =≥ - todas as variáveis da solução são não negativas - então esta 
solução é uma solução básica viável. 
 
Definição 10. Se uma solução básica viável é também uma solução básica degenerada, 
ela é dita ser uma solução básica viável degenerada. 
 
 
 
 
Teorema fundamental da Programação Linear 
 
Através do teorema fundamental da programação linear estabelece-se a importância das 
soluções viáveis básicas na resolução de problemas de programação linear. Este teorema 
estabelece que: 
Programação Linear 
© Prof. João Antônio de Vasconcelos 63 
 
1) Se existe uma solução viável para o problema de PL, definido pelas expressões 
ba x 
n
1j
jj =∑
= e 
n,...,1j para 0 x j =≥ , então existe uma solução básica viável. 
 
2) Se existe uma solução ótima viável então existe uma solução ótima básica viável. 
 
Do teorema fundamental da PL podemos concluir que não é necessário procurar a solução 
ótima entre todas as soluções viáveis, mas apenas entre as soluções básicas viáveis. 
 
O número máximo de soluções básicas num problema com m restrições e n variáveis, 
corresponde ao número máximo de bases distintas do sistema ba x 
n
1j
jj =∑
= que podem ser 
determinadas e esse número é dado pelo número de possíveis combinações de m números 
que podem ser obtidas usando n números: 
Programação Linear 
© Prof. João Antônio de Vasconcelos 64 
)!(!
!
mnm
n
m
n
−=



 (32) 
 
Embora este número possa ser muito grande, teoricamente a solução ótima poderia ser 
encontrada pela experimentação de todas as soluções básicas viáveis. Este método, porém, 
mostra-se ineficaz. 
 
O Método Simplex 
 
O método Simplex é um algoritmo que permite resolver problemas de Programação Linear. A 
idéia básica do método Simplex consiste em resolver repetidas vezes um sistema de 
equações lineares para obter uma sucessão de soluções básicas viáveis (que é um ponto 
extremo), cada uma ‘melhor’ que a anterior, até se chegar a uma solução básica viável ótima 
(ou seja, até que o mínimo/máximo na função objetivo seja alcançado). 
Programação Linear 
© Prof. João Antônio de Vasconcelos 65 
 
Algumas descrições necessárias ao método Simplex 
 
Pivôs 
Para obter uma compreensão do método Simplex, é necessário compreender o processo de 
pivotagem em um conjunto de equações lineares. Há para isso 2 interpretações: 
 
Primeira interpretação: 
 
Considere o conjunto de equações lineares abaixo: 
 b x a + … + x a + x a
b x a + … + x a + x a
b x a + … + x a + x a
mnn m2m21m1
2n2n222121
1n1n212111
=
=
=
L
 (33) 
Programação Linear 
© Prof. João Antônio de Vasconcelos 66 
 
onde m ≤ n. Na forma matricial escreve-se como: 
 
Ax = b (34) 
 
No espaço En pode-se interpretar as equações acima como um conjunto de m relações 
lineares que devem ser satisfeitas por um vetor x. Denotando por ai , a i-ésima linha da matriz 
A, temos: 
 
a1x = b1 
a2x = b2 
. 
. 
. 
amx = bm (35) 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 67 
Se m < n e as equações são linearmente independentes, então há uma variedade de 
soluções lineares. Uma única solução resulta se n – m equações lineares e independentes 
adicionais forem acrescentadas. 
 
Se as equações (35) são linearmente independentes (LI), pode-se substituir uma dada 
equação multiplicando-a por um número diferente de zero e somando à equação obtida 
alguma combinação linear de outras equações do sistema. Essa transformação, dita 
Gaussiana, é utilizada pra transformar um conjunto de equações para a forma triangular. Se 
as m primeiras colunas de A são LI, o sistema (5), pode, através de uma seqüência de 
multiplicações e subtrações ser reduzido à forma seguinte: 
 
 
x1 0 ... 0 + y1, m + 1xm + 1 + y1, m + 2xm + 2 + ... + y1, nxn = y10 
0 x2 ... 0 + y2, m + 1xm + 1 + y2, m + 2xm + 2 + ... + y2, nxn = y20 
 .... .... .... 
0 0 ... xm +ym, m + 1xm + 1 + ym, m + 2xm + 2 + ... + ym, nxn = ym0 (36) 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 68 
Para o sistema (36), as variáveis x1, x2, ..., xm são chamadas de básicas e as outras variáveis 
são não-básicas. A solução básica correspondente é: 
 
x1 = y10, x2 = y20, ..., xm = ym0, xm + 1 = 0, ..., xn = 0 (37) 
 
Ou, na forma vetorial 
 
x = (y0, 0) (38) 
 
O sistema (36) pode ser representado por uma matriz ou tabela (quadro Simplex): 
 
 
1 0 .... 0 y1, m + 1 y1, m + 2 y1n y10 
0 1 .... 0 y2, m + 1 y2, m + 2 y2n y20 
……………………………………………….……….. 
0 0 .... 1 ym, m + 1 ym, m + 2 ymn ym0 
 (39) 
Programação Linear 
© Prof. João Antônio de Vasconcelos 69 
Exemplo 1: 5ª. Aula 
Dado o problema abaixo, encontre uma solução básica através de pivotagem. 
 2 x - x 2 x + x 
3x + x 3 - x 2 + 2x
1 x + x + x + 3x
4321
4321
4321
=+
=
=
 







= 
21-211
313-22
11113
B
 
Solução: 
B(1,:)=B(1,:)/B(1,1) { B(1,1) – elemento pivô} 
 1.0000 0.3333 0.3333 0.3333 0.3333 
 2.0000 2.0000 -3.0000 1.0000 3.0000 
 1.0000 1.0000 2.0000 -1.0000 2.0000 
 
 
B(2,:)=B(2,:)-B(1,:)*B(2,1 { Zerando o elemento B(2,1) abaixo do elemento pivô} 
 1.0000 0.3333 0.3333 0.3333 0.3333 
 0 1.3333 -3.6667 0.3333 2.3333 
 1.0000 1.0000 2.0000 -1.0000 2.0000 
 
 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 70 
B(3,:)=B(3,:)-B(1,:)*B(3,1) { Zerando o elemento B(3,1) abaixo do elemento pivô} 
 1.0000 0.3333 0.3333 0.3333 0.3333 
 0 1.3333 -3.6667 0.3333 2.3333 
 0 0.6667 1.6667 -1.3333 1.6667 
 
B(2,:)=B(2,:)/B(2,2) { B(2,2) – elemento pivô} 
 1.0000 0.3333 0.3333 0.3333 0.3333 
 0 1.0000 -2.7500 0.2500 1.7500 
 0 0.6667 1.6667 -1.3333 1.6667 
 
B(1,:)=B(1,:)- B(2,:)*B(1,2 { Zerando o elemento B(1,2) acima do elemento pivô} 
 1.0000 0 1.2499 0.2500 -0.2500 
 0 1.0000 -2.7500 0.2500 1.7500 
 0 0.6667 1.6667 -1.3333 1.6667 
 
B(3,:)=B(3,:)- B(2,:)*B(3,2) { Zerando o elemento B(3,2) abaixo do elemento pivô} 
 1.0000 0 1.2499 0.2500 -0.2500 
 0 1.0000 -2.7500 0.2500 1.7500 
 0 0 3.5001 -1.5000 0.5000 
 
 
B(3,:)=B(3,:)/B(3,3) { B(3,3) – elemento pivô} 
 1.0000 0 1.2499 0.2500 -0.2500 
 0 1.0000 -2.7500 0.2500 1.7500 
Programação Linear 
© Prof. João Antônio de Vasconcelos 71 
 0 0 1.0000 -0.4285 0.1428 
 
B(1,:)=B(1,:)- B(3,:)*B(1,3) { Zerando o elemento B(1,3) acima do elemento pivô} 
 1.0000 0 0 0.7856 -0.4285 
 0 1.0000 -2.7500 0.2500 1.7500 
 0 0 1.0000 -0.4285 0.1428 
 
B(2,:)=B(2,:)- B(3,:)*B(2,3) { Zerando o elemento B(2,3) acima do elemento pivô} 
 1.0000 0 0 0.7856 -0.4285 
 0 1.0000 0 -0.9285 2.1428 
 0 0 1.0000 -0.4285 0.1428 
 
 
 
Exemplo 2: 
Dado o problema abaixo, determine uma solução básica através de pivotagem e coloque o 
problema na forma de tabela. 
Programação Linear 
© Prof. João Antônio de Vasconcelos 72 
 2 x - x 2 x + x 2
2x + x x - 2x
3 x - x + x 2 + x 
4321
4321
4321
=−
=+
=
 







= 
21-2-12
2111-2
31-121
B
 
Solução: 
B = 
 1.0000 0 0 0.0588 1.1176 
 0 1.0000 0 -0.6471 0.7059 
 0 0 1.0000 0.2353 0.4706 
 
 
 
Há, porém, uma questão a se resolver: Dado um sistema na forma acima, suponha que se 
deseje tornar uma variável básica em não-básica e uma variável não-básica em básica. Qual 
será a nova tabela correspondente a esse novo conjunto de variáveis básicas? 
 
Isso pode ser resolvido da seguinte forma, utilizando o método de redução Gauss-Jordan: 
Programação Linear 
© Prof. João Antônio de Vasconcelos 73 
 
1) Divida toda a linha correspondente à variável não-básica a entrar na base pelo valor do 
coeficiente correspondente à mesma, desde que diferente de zero, de forma que essa 
variável se torne unitária (ela deve ser não-negativa). 
 
2) Faça as operações necessárias para zerar todos os outros elementos relacionados à 
coluna da variável não-básica. Para isso, multiplique a nova linha da variável não-básica 
que deve entrar na base por um número de forma que ao somá-lo à linha cujo elemento 
se deseja zerar, esse se anule. 
 
Exemplo 3: 
Na tabela abaixo x1, x2 e x3 são as variáveis básicas e x4 é não básica. Entre com x4 na base 
no lugar de x3. 
Programação Linear 
© Prof. João Antônio de Vasconcelos 74 
24100
63010
22001
 
Solução: 
B(3,:)=B(3,:)/B(3,4) { B(3,4) – elemento pivô, isto é, coeficiente de x4 que deve entrar 
na base no lugar de x3} 
 1.0000 0 0 2.0000 2.0000 
 0 1.0000 0 3.0000 6.0000 
 0 0 0.2500 1.0000 0.5000 
B(1,:)=B(1,:)- B(3,:)*B(1,4) { Zerando o elemento B(1,4) acima do elemento pivô} 
 1.0000 0 -0.5000 0 1.0000 
 0 1.0000 0 3.0000 6.0000 
 0 0 0.2500 1.0000 0.5000 
B(2,:)=B(2,:)- B(3,:)*B(2,4) { Zerando o elemento B(2,4) acima do elemento pivô} 
 1.0000 0 -0.5000 0 1.0000 
 0 1.0000 -0.7500 0 4.5000 
 0 0 0.2500 1.0000 0.5000 
Segunda interpretação: 
Programação Linear 
© Prof. João Antônio de Vasconcelos 75 
O conjunto de equações simultâneas representadas por (35) e (36) pode ser interpretado em 
Em como uma equação vetorial. Denotando as colunas de A por a1, a2, ..., an, pode-se 
escrever (35) como: 
 
x1a1 + x2a2 + ... + xnan = b (40) 
 
Nessa interpretação, se expressa b como uma combinação linear de colunas ai’s. 
Se m < n e os vetores ai geram Em então encontramos uma família de soluções. A solução 
relacionada com o conjunto de n – m variáveis xi iguais a zero é a solução básica para (35). 
 
 
Suponha agora que nós iniciemos com o sistema na forma de tabela: 
 
 
 
1 0 .... 0 y1, m + 1 y1, m + 2 y1n y10 
Programação Linear 
© Prof. João Antônio de Vasconcelos 76 
0 1 .... 0 y2, m + 1 y2, m + 2 y2n y20 
……………………………………………….……….. 
0 0 .... 1 ym, m + 1 ym, m + 2 ymn ym0 
 (41) 
 
Nesse caso as primeiras m colunas formam a base. Além disso, qualquer vetor representado 
na tabela pode ser expresso como uma combinação linear dos outros vetores da base. 
Conseqüentemente: 
 
aj = y1ja1 + y2ja2 + ... + ymjam (42) 
 
A tabela pode ser interpretada como uma representação dos vetores ai em termos da base; a 
i-ésima coluna da tabela constitui a representação para o vetor ai. Em particular, a expressão 
para b em termos da base é dada na última coluna. 
 
Considere agora a operação de substituição de um membro da base por outro vetor não-
existente na base. Suponha que se deseje substituir o vetor da base ap, 1 ≤ p ≤ m, pelo vetor 
Programação Linear 
© Prof. João Antônio de Vasconcelos 77 
aq, m+1 ≤ q ≤ n. Conhecido que os m primeiros vetores ap são LI, esses vetores constituem a 
base e todo vetor pode ser expresso como uma combinação linear dessa nova base. Para 
encontrar uma nova representação desses novos vetores é preciso atualizar a base. Isso é 
feito de forma semelhante ao procedimento 1) descrito anteriormente. 
 
Pontos extremos adjacentes 
Discutiu-se anteriormente que é necessário apenas considerar as variáveis básicas viáveis na 
solução de problemas de programaçãolinear da forma 
 
Ax = b 
x ≥ 0 (43) 
 
Embora as operações de pivotagem transformem uma solução básica em outra, em geral, as 
condições de não negatividade das soluções não são preservadas. É possível, especificar 
então, qual variável não-básica se tornará básica e dessa forma determinar qual variável 
básica deverá se tornar não-básica? 
Programação Linear 
© Prof. João Antônio de Vasconcelos 78 
 
Suposição de Não-degeneraridade: Toda solução viável básica de (43) é uma solução 
viável básica não-degenerada. 
 
Determinação do vetor que deixa a base 
 
Suponha que nós tenhamos a solução viável básica x = (x1, x2, ..., xm, 0, 0, ..., 0), ou, 
equivalentemente a representação 
 
x1a1 + x2a2 + ..... + xmam = b (44) 
 
Utilizando a suposição de não-degeneraridade, isto é, xi > 0 para todo i = 1, 2, ..., m. 
Considere também a representação do vetor ak, k > m em termos da base: 
 
ak = y1ka1+ y2ka2 + … + ymkam (45) 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 79 
Multiplicando (45) pela variável ξ e subtraindo o resultado de (44) , isto é: 
 
x1 a1 + x2 a2 + ... + xmam = b 
ξy1ka1 + ξy2ka2 + ... + ξymkam - ξak = 0 
-------------------------------------------------------------------------- 
(x1 - ξy1k)a1 + (x2 - ξy2k)a2 + ... + (xm - ξymk)am + ξak = b (46) 
 
Para ξ ≥ 0, obtemos b como uma combinação linear de no máximo m + 1 vetores. Para ξ = 0, 
temos a tradicional solução básica viável. Se o valor de ξ é aumentado, o coeficiente de ak 
cresce e, para pequenos valores de ξ, (46) fornece uma solução viável, mas não-básica. Os 
coeficientes dos outros vetores podem aumentar ou diminuir linearmente quando ξ cresce. Se 
algum deles decresce, nós podemos escolher o menor valor ξ para o qual tal coeficiente 
assume o valor nulo, ou seja: 
 
ξ = min {xi / yik : yik > 0} , ∀ i = 1, 2, …, m. (47) 
Programação Linear 
© Prof. João Antônio de Vasconcelos 80 
 
Nesse caso nós temos uma nova solução viável básica, com o vetor ak ocupando o lugar do 
vetor ai, que corresponde ao mínimo em (47). 
 
Se o mínimo em (47) é obtido para mais de um índice i, teremos então uma nova solução 
básica que é degenerada e, qualquer um dos vetores com componentes iguais a zero poderá 
ser considerado aquele que deixará a base. 
 
Se nenhum dos yik’s é positivo, então todos os coeficientes na representação (47) crescem 
(ou permanecem constantes) quando ξ aumenta e, nenhuma nova solução viável básica é 
obtida. Observa-se, entretanto, que nesse caso, há soluções viáveis para (43) tendo grandes 
coeficientes. Isso significa que o conjunto K de soluções viáveis para (43) é ilimitado e 
corresponde a um caso especial do método Simplex. 
 
Em um quadro Simplex para determinar a variável básica que deixa a base deve-se 
prosseguir como: 
Programação Linear 
© Prof. João Antônio de Vasconcelos 81 
- A coluna pertencente à variável não-básica que entra na base é chamada de coluna 
pivô. Dividem-se todos os termos independentes (yi0) pelos correspondentes elementos 
pertencentes a essa coluna (desde que esses valores sejam positivos). 
- Escolhe-se o menor desses quocientes. A linha que atende a essa especificação, 
chamada de linha pivô, é associada à variável básica que deixará a base. 
 
Exemplo: Substitua a variável não-básica x4 por uma das variáveis básicas mantendo a 
condição de não-negatividade. 
 
24100
63010
22001
B =
 
Solução: Observe que para o problema, a solução básica viável é x = [2 6 2 0]T. 
Determinação de qual variável básica deve entrar na base: 
Programação Linear 
© Prof. João Antônio de Vasconcelos 82 
basedasairdevex
5,0
2
1
a/y
24100
63010
22001
34i0i ⇒=⇒
 
Substituindo x3 básica por x4 não-básica: 
 
B(3,:)=B(3,:)/B(3,4) { B(3,4) – elemento pivô, isto é, coeficiente de x4 que deve entrar 
na base no lugar de x3} 
 1.0000 0 0 2.0000 2.0000 
 0 1.0000 0 3.0000 6.0000 
 0 0 0.2500 1.0000 0.5000 
B(1,:)=B(1,:)- B(3,:)*B(1,4) { Zerando o elemento B(1,4) acima do elemento pivô} 
 1.0000 0 -0.5000 0 1.0000 
 0 1.0000 0 3.0000 6.0000 
 0 0 0.2500 1.0000 0.5000 
B(2,:)=B(2,:)- B(3,:)*B(2,4) { Zerando o elemento B(2,4) acima do elemento pivô} 
 1.0000 0 -0.5000 0 1.0000 
 0 1.0000 -0.7500 0 4.5000 
 0 0 0.2500 1.0000 0.5000 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 83 
A solução básica é x = [1 4.5 0 0.5] T. 
 
Determinação da solução Ótima 
 
De forma a tornar o método Simplex iterativo e reduzir o valor da função objetivo é necessário 
determinar agora qual variável não-básica entrará na base. 
 
Seja c
r
 o vetor linha correspondente aos coeficientes da função objetivo, com elementos ci, ∀ 
i =1,2,...,n. Seja Bc
r
 o vetor correspondente às variáveis básicas ix
r
, ∀ i =1,2,...,m e yij o 
componente i da coluna j do quadro Simplex. Tem-se que 
BB
m
1i
ii0 xcxcz
rr==∑
= (48) 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 84 
xcxcz
n
1i
ii
rr==∑
= (49) 
 
 
Embora seja natural usar a solução básica (xB, 0) quando temos o quadro Simplex, é claro 
que se valores arbitrários são associados a xm+1, xm+2, ... xn, nós podemos facilmente 
determinar as alterações nas variáveis básicas para acomodar estas variações, isto é: 
∑
+=
−=
n
1mj
jj1101 xyyx 
 
∑
+=
−=
n
1mj
jj2202 xyyx (50) 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 85 
M
M
 
∑
+=
−=
n
1mj
jmj0mm xyyx 
 
Usando (50), podemos eliminar as variáveis básicas da fórmula geral para o cálculo da função 
objetivo dada em (49). Fazendo-se isto, temos: 
nnn2m2m2m1m1m1m0 x)zc(x)zc(x)zc(zxcz −++−+−+== ++++++ Lrr
 (51) 
onde 
Programação Linear 
© Prof. João Antônio de Vasconcelos 86 
n,mmn,22n,11n
2m,mm2m,222m,112m
1m,mm1m,221m,111m
ycycycz
ycycycz
ycycycz
+++=
+++=
+++=
++++
++++
L
L
L
 (52) 
 
A expressão (51) é a relação fundamental requerida para determinar a coluna pivô, isto é, 
qual variável não-básica deve entrar na base. Por quê? 
 
Para a escolha da variável não básica a entrar na base é necessário determinar qual dos 
custos definidos como 
 
cj - zj , ∀ j=m+1,..., n 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 87 
é menor que zero. Se tiver pelo menos um, significa que a função objetivo z pode ser feita 
menor que z0 (Eq. 51). Assim, a variável não-básica a entrar na base deve ser tal que 
 
 
 
Para que o processamento possa ser feito de forma automática, isto é, para que a introdução 
de uma nova variável possa ser processada nas demais variáveis, consideramos o quadro 
Simplex anteriormente apresentado acrescentando uma nova linha correspondendo à função 
objetivo z: 
 
1 0 .... 0 y1, m + 1 y1, m + 2 y1n y10 
0 1 .... 0 y2, m + 1 y2, m + 2 y2n y20 
……………………………………………….……….. 
0 0 .... 1 ym, m + 1 ym, m + 2 ymn ym0 
0 0 .... 0 r m + 1 rm, + 2 rn -z0 
 (53) 
 
em que: 
Critério de entrada na 
base 
 
 
Min { cj - zj | cj - zj < 0 } 
 j 
Programação Linear 
© Prof. João Antônio de Vasconcelos 88 
 
 rm+1 = cm+1 – zm+1 (54) 
 
 
e 
 










…=
+
+
+
+
1mm,
1m2,
1m1,
m211m
y
y
y
] c . c [c z
M . (55) 
 
 
 
 
Teorema (melhoramento da solução básica viável): 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 89 
Considere dada uma solução básica viável não-degenerada com o correspondente valor zo. 
Suponha que para algum j tenha-se cj – zj < 0. Dessa forma há uma solução viável com valor 
z < z0. Se a coluna aj pode ser substituída por algum vetor na base original para constituir uma 
nova solução básica viável, então a nova solução contém z < z0. Se aj não pode ser 
substituída, o conjuntosolução K é ilimitado. 
 
Teorema da Condição de Otimalidade: 
 
Se para alguma solução básica viável cj ≥ zj , ∀ j, então essa solução é ótima. 
 
Exercício: 
Resolva via Simplex o problema abaixo: 
Programação Linear 
© Prof. João Antônio de Vasconcelos 90 
0x,x,x
6xx2x2
5x3x2x
2xxx2:asujeito
x3xx3imizemax
321
321
321
321
321
≥
≤++
≤++
≤++
++
 (56) 
Solução: 
O problema precisa ser colocado na forma padrão. Para isto, vamos transformar o problema em 
problema de minimização e acrescentar uma variável de folga para cada restrição: 
 
0000313
6100122
5010321
2001112
−−−
 (57) 
Programação Linear 
© Prof. João Antônio de Vasconcelos 91 
 
Observem que o problema já se encontra na forma adequada à utilização do Método Simplex. 
A solução básica viável é x = [0 0 0 2 5 6]T e a z = 0. Seja A a matriz dada em (57). 
 
 2 1 1 1 0 0 2 
 1 2 3 0 1 0 5 
 2 2 1 0 0 1 6 
-3 -1 -3 0 0 0 0 
Observando esta matriz, vimos que as variáveis não-básicas x1 e x3 ao entrarem na base 
conduzirão à maior diminuição na função objetivo. Escolhamos a variável x1 para entrar na 
base. Ao fazermos isto, precisamos agora escolher qual variável básica deixará a base com a 
condição de que a viabilidade da solução básica seja mantida. Isto pode ser feito tomando o 
menor valor do yi0/ai1, para i = 1, 2 ou 3. Efetuando as contas obtemos respectivamente os 
valores 2/2, 5/1 e 6/2. Logo, o menor resultado corresponde ao elemento a11 que conduz a 
retirar da base a variável x4. Assim, façamos então a introdução de x1 e retirada de x4. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 92 
A(1,:)=A(1,:)/A(1,1) 
 1.0000 0.5000 0.5000 0.5000 0 0 1.0000 
 1.0000 2.0000 3.0000 0 1.0000 0 5.0000 
 2.0000 2.0000 1.0000 0 0 1.0000 6.0000 
 -3.0000 -1.0000 -3.0000 0 0 0 0 
 
A(2,:)=A(2,:)-A(1,:)*A(2,1) 
 1.0000 0.5000 0.5000 0.5000 0 0 1.0000 
 0 1.5000 2.5000 -0.5000 1.0000 0 4.0000 
 2.0000 2.0000 1.0000 0 0 1.0000 6.0000 
-3.0000 -1.0000 -3.0000 0 0 0 0 
 
A(3,:)=A(3,:)-A(1,:)*A(3,1) 
 1.0000 0.5000 0.5000 0.5000 0 0 1.0000 
 0 1.5000 2.5000 -0.5000 1.0000 0 4.0000 
 0 1.0000 0 -1.0000 0 1.0000 4.0000 
-3.0000 -1.0000 -3.0000 0 0 0 0 
 
A(4,:)=A(4,:)-A(1,:)*A(4,1) 
1.0000 0.5000 0.5000 0.5000 0 0 1.0000 
 0 1.5000 2.5000 -0.5000 1.0000 0 4.0000 
Programação Linear 
© Prof. João Antônio de Vasconcelos 93 
 0 1.0000 0 -1.0000 0 1.0000 4.0000 
 0 0.5000 -1.5000 1.5000 0 0 3.0000 
 
Continuando o processo, verificamos que a variável x3 ao entrar na base ela provocará uma 
diminuição na função objetivo. Ao dividirmos 1/0.5 e 4/2.5, verificamos que o menor resultado 
é 4/2.5, o que corresponde a introduzir x3 na base e retirar x5. Façamos então as operações. 
A(2,:)=A(2,:)/A(2,3) 
1.0000 0.5000 0.5000 0.5000 0 0 1.0000 
 0 0.6000 1.0000 -0.2000 0.4000 0 1.6000 
 0 1.0000 0 -1.0000 0 1.0000 4.0000 
 0 0.5000 -1.5000 1.5000 0 0 3.0000 
 
 
A(1,:)=A(1,:)-A(2,:)*A(1,3) 
1.0000 0.2000 0 0.6000 -0.2000 0 0.2000 
 0 0.6000 1.0000 -0.2000 0.4000 0 1.6000 
 0 1.0000 0 -1.0000 0 1.0000 4.0000 
 0 0.5000 -1.5000 1.5000 0 0 3.0000 
 
 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 94 
A(4,:)=A(4,:)-A(2,:)*A(4,3) 
1.0000 0.2000 0 0.6000 -0.2000 0 0.2000 
 0 0.6000 1.0000 -0.2000 0.4000 0 1.6000 
 0 1.0000 0 -1.0000 0 1.0000 4.0000 
 0 1.4000 0 1.2000 0.6000 0 5.4000 
 
 
Como não há mais nenhum resíduo negativo, significa que é impossível reduzir a função 
objetivo dentro do espaço viável. Logo, a solução ótima é x = [0.2 0.0 1.6 0.0 0.0 4.0]T. Este 
valor corresponde ao valor da função objetivo original igual a z* = 3*0.2 + 1*0.0 + 3*1.6 = 5.4. 
 
 
 
 
Variáveis Artificiais – 21/03 
 
Para alguns tipos de problemas de programação linear, a solução básica viável inicial nem 
sempre é visível. Dessa forma são necessários procedimentos para determiná-la, uma vez 
que o método Simplex precisa desta condição para ser iniciado. Para isso recorre-se ao uso 
da técnica das variáveis artificiais. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 95 
A técnica das variáveis artificiais consiste em construir um problema auxiliar introduzindo uma 
nova variável, chamada variável artificial, em cada uma das restrições onde não foi possível 
adicionar uma variável de folga, sendo esta tomada como variável básica para essa equação. 
Desta forma fica garantida a existência de uma variável básica em cada equação e a 
possibilidade de identificar uma solução básica viável (SBV ) inicial. 
 
Considere o problema da forma 
 
Ax = b 
x ≥ 0 e b ≥ 0 (58) 
 
 
De forma a encontrar uma solução para (58) considere o problema de minimização (artificial) 
minimize ∑=
m
i
iy
1
 
sujeito a Ax + y = b 
Programação Linear 
© Prof. João Antônio de Vasconcelos 96 
x ≥ 0 
y ≥ 0 (59) 
 
onde y = (y1, y2, …, ym) é um vetor de variáveis artificiais. Se há uma solução viável para (58) 
o problema (59) tem um valor mínimo y = 0. Se (58) não tem uma solução viável, então o 
valor mínimo de (59) é maior que zero. 
O problema (59) está na forma adequada com a solução viável básica y = b. Usando as 
técnicas do método Simplex é possível obter uma solução viável básica em cada passo. Se o 
valor mínimo de (59) é zero, então a solução básica final terá todos os yi = 0 e não terá 
nenhuma variável básica yi. 
 
Método das duas fases 
 
Nesse método o problema de Programação Linear é resolvido em duas fases: 
1ª Fase: Constrói-se um novo problema auxiliar (introduzindo variáveis artificiais) com o 
objetivo de obter uma SBV inicial para o problema original (se isto é possível). 
Programação Linear 
© Prof. João Antônio de Vasconcelos 97 
2ª Fase: Tomando como SBV (Solução Básica Viável) inicial a solução obtida na 1ª Fase, 
aplica o algoritmo Simplex, para determinar a solução ótima. Durante essa fase, as 
variáveis artificiais e a função objetivo da 1ª Fase são omitidas. 
 
Par esse método tem-se: 
- Qualquer SBV do problema auxiliar é uma SBV do problema original se as variáveis 
artificiais da solução são nulas. 
- Obtém-se uma SBV com as variáveis artificiais iguais a zero se e só se o valor da f.o. 
artificial é igual a zero (z' = 0). 
- A aplicação do algoritmo Simplex eliminará da base os vetores artificiais (caso o 
problema não seja impossível), pois as variáveis iniciais (não artificiais) têm coeficientes 
nulos na f.o. que se pretende minimizar. 
 
No fim da 1ª fase, em que se atingiu a solução ótima do problema auxiliar, está-se perante 
uma das seguintes situações: 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 98 
1º. Todos os vetores artificiais foram eliminados da base (z' = 0). 
Neste caso, obtém-se uma SBV do problema original. Passa-se diretamente à 2ª fase do 
método Simplex. 
 
2º. Ainda subsistemvetores artificiais na base. 
Existem duas alternativas: 
z' > 0: existe pelo menos uma variável artificial básica com valor estritamente positivo → o 
conjunto K é vazio, o problema é impossível. 
z' = 0: todas as variáveis artificiais são nulas → Obtém-se ou uma SBV inicial degenerada ou 
uma restrição redundante. Veja o fluxograma a seguir. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 99 
 2º. Ainda subsistem vetores artificiais na base e z' = 0
Existe pelo menos um vetor não 
artificial fora da base que pode 
substituir um vetor artificial 
procede-se à sua substituição
obtém-se uma SBV inicial degenerada 
para o problema original 
Não existe nenhum vetor não 
artificial fora da base que pode 
substituir um vetor artificial 
existem restrições redundantes
Eliminam-se do quadro simplex as 
linhas correspondentes às variáveis 
artificiais básicas e obtém-se uma 
SBV inicial para o problema original
 
 
Figura 01: Aspectos de resolução do Método das 2 Fases 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 100 
PS: Geralmente, num problema que apresenta inequações cujas restrições são do tipo ≥ 
torna-se necessária a inclusão de variáveis artificiais. 
 
Exercícios: Resolva os seguintes problemas via método Simplex: 
 
Problema 1: 
0x,x,x
6xx2x2
5x2x2x3
6x3xx:asujeito
x4x2ximizemax
321
321
321
321
321
≥
≤+−
≤++
≤++
++
 (60) 
 
 
Problema 2: 
Programação Linear 
© Prof. João Antônio de Vasconcelos 101 
0x,x,x
2xx2x2
5x3x2x
6xxx2:asujeito
x3xx3imizemax
321
321
321
321
321
≥
≥++
=++
≤++
++
 (61) 
 
Problema 3: 
Programação Linear 
© Prof. João Antônio de Vasconcelos 102 
3x
1x
0x
6xx2x2
5x3x2x
2xxx2:asujeito
x3xx3imizemax
3
2
1
321
321
321
321
≤
≥
≥
≤++
≤++
≤++
++
 (62) 
 
 
Problema 4: 
Programação Linear 
© Prof. João Antônio de Vasconcelos 103 
0x,x
6xx2x2
5x3x2x
2xxx2:asujeito
x3xx3imizemin
31
321
321
321
321
≥
=++
≤++
≤++
++
 (63) 
 
 
Exercícios: Resolva os seguintes problemas via método Simplex: (AULA 28/03/2005) 
Problema 1: 
0x,x,x
6xx2x2
5x2x2x3
6x3xx:asujeito
x4x2ximizemax
321
321
321
321
321
≥
≤+−
≤++
≤++
++
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 104 
Solução: Para se aplicar o método Simplex, devemos: i) transformar o problema de 
maximização em minimização; ii) para cada equação de restrição com sinal de “menor ou 
igual”, acrescentar uma variável de folga. Isto nos permite escrever a seguinte tabela 
SIMPLEX: 
 
0000421
6100122
5010223
6001311
−−−
− 
 
b(1,:)=b(1,:)/b(1,3) ? Escolha do elemento pivô (6/3; 5/2; 6/1) ? elemento b(1,3) 
 0.3333 0.3333 1.0000 0.3333 0.0000 0.0000 2.0000 
 3.0000 2.0000 2.0000 0.0000 1.0000 0.0000 5.0000 
 2.0000 -2.0000 1.0000 0.0000 0.0000 1.0000 6.0000 
-1.0000 -2.0000 -4.0000 0.0000 0.0000 0.0000 0.0000 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 105 
 
b(2,:)=b(2,:)-b(1,:)*b(2,3)/b(1,3) 
 0.3333 0.3333 1.0000 0.3333 0.0000 0.0000 2.0000 
 2.3333 1.3333 0.0000 -0.6667 1.0000 0.0000 1.0000 
 2.0000 -2.0000 1.0000 0.0000 0.0000 1.0000 6.0000 
 -1.0000 -2.0000 -4.0000 0.0000 0.0000 0.0000 0.0000 
 
b(3,:)=b(3,:)-b(1,:)*b(3,3)/b(1,3) 
 0.3333 0.3333 1.0000 0.3333 0.0000 0.0000 2.0000 
 2.3333 1.3333 0.0000 -0.6667 1.0000 0.0000 1.0000 
 1.6667 -2.3333 0.0000 -0.3333 0.0000 1.0000 4.0000 
 -1.0000 -2.0000 -4.0000 0.0000 0.0000 0.0000 0.0000 
 
b(4,:)=b(4,:)-b(1,:)*b(4,3)/b(1,3) 
 0.3333 0.3333 1.0000 0.3333 0.0000 0.0000 2.0000 
 2.3333 1.3333 0.0000 -0.6667 1.0000 0.0000 1.0000 
Programação Linear 
© Prof. João Antônio de Vasconcelos 106 
 1.6667 -2.3333 0.0000 -0.3333 0.0000 1.0000 4.0000 
 0.3333 -0.6667 0.0000 1.3333 0.0000 0.0000 8.0000 
 
b(2,:)=b(2,:)/b(2,2) ? Escolha do elemento pivô (2/0.3333; 1/1.333) ? elemento b(2,2) 
 0.3333 0.3333 1.0000 0.3333 0.0000 0.0000 2.0000 
 1.7500 1.0000 0.0000 -0.5000 0.7500 0.0000 0.7500 
 1.6667 -2.3333 0.0000 -0.3333 0.0000 1.0000 4.0000 
 0.3333 -0.6667 0.0000 1.3333 0.0000 0.0000 8.0000 
 
b(1,:)=b(1,:)-b(2,:)*b(1,2)/b(2,2) 
 -0.2500 0.0000 1.0000 0.5000 -0.2500 0.0000 1.7500 
 1.7500 1.0000 0.0000 -0.5000 0.7500 0.0000 0.7500 
 1.6667 -2.3333 0.0000 -0.3333 0.0000 1.0000 4.0000 
 0.3333 -0.6667 0.0000 1.3333 0.0000 0.0000 8.0000 
 
b(3,:)=b(3,:)-b(2,:)*b(3,2)/b(2,2) 
Programação Linear 
© Prof. João Antônio de Vasconcelos 107 
 -0.2500 0.0000 1.0000 0.5000 -0.2500 0.0000 1.7500 
 1.7500 1.0000 0.0000 -0.5000 0.7500 0.0000 0.7500 
 5.7500 0.0000 0.0000 -1.5000 1.7500 1.0000 5.7500 
 0.3333 -0.6667 0.0000 1.3333 0.0000 0.0000 8.0000 
 
b(4,:)=b(4,:)-b(2,:)*b(4,2)/b(2,2) 
 -0.2500 0.0000 1.0000 0.5000 -0.2500 0.0000 1.7500 
 1.7500 1.0000 0.0000 -0.5000 0.7500 0.0000 0.7500 
 5.7500 0.0000 0.0000 -1.5000 1.7500 1.0000 5.7500 
 1.5000 0.0000 0.0000 1.0000 0.5000 0.0000 8.5000 
 
Logo, a solução é x = [0.0000, 0.7500, 1.7500]T com z* = 8.5000. 
Programação Linear 
© Prof. João Antônio de Vasconcelos 108 
Problema 2: 
0x,x,x
2xx2x2
5x3x2x
6xxx2:asujeito
x3xx3imizemax
321
321
321
321
321
≥
≥++
=++
≤++
++
 
 
Solução: Para o sinal de “menor ou igual” vamos acrescentar uma variável de folga e para o 
sinal de “maior ou igual” vamos acrescentar uma variável de excesso. Além disto, este 
problema não possui uma solução viável básica. Logo, teremos que resolve-lo usando o 
procedimento das duas etapas. Assim, a tabela para este problema na primeira etapa ficará: 
 
011100000
210010122
501000321
600101112
− 
Programação Linear 
© Prof. João Antônio de Vasconcelos 109 
 
b(4,:) = b(4,:)-b(1,:)-b(2,:) - b(3,:) 
 2 1 1 1 0 1 0 0 6 
 1 2 3 0 0 0 1 0 5 
 2 2 1 0 -1 0 0 1 2 
 -5 -5 -5 -1 1 0 0 0 -13 
 
>> b(3,:)=b(3,:)/b(3,1) 
 2.0000 1.0000 1.0000 1.0000 0.0000 1.0000 0.0000 0.0000 6.0000 
 1.0000 2.0000 3.0000 0.0000 0.0000 0.0000 1.0000 0.0000 5.0000 
 1.0000 1.0000 0.5000 0.0000 -0.5000 0.0000 0.0000 0.5000 1.0000 
-5.0000 -5.0000 -5.0000 -1.0000 1.0000 0.0000 0.0000 0.0000 -13.0000 
 
>> b(1,:)=b(1,:)-b(3,:)*b(1,1)/b(3,1) 
0.0000 -1.0000 0.0000 1.0000 1.0000 1.0000 0.0000 -1.0000 4.0000 
 1.0000 2.0000 3.0000 0.0000 0.0000 0.0000 1.0000 0.0000 5.0000 
 1.0000 1.0000 0.5000 0.0000 -0.5000 0.0000 0.0000 0.5000 1.0000 
-5.0000 -5.0000 -5.0000 -1.0000 1.0000 0.0000 0.0000 0.0000 -13.0000 
 
>> b(2,:)=b(2,:)-b(3,:)*b(2,1)/b(3,1) 
 
 0.0000 -1.0000 0.0000 1.0000 1.0000 1.0000 0.0000 -1.0000 4.0000 
 0.0000 1.0000 2.5000 0.0000 0.5000 0.0000 1.0000 -0.5000 4.0000 
Programação Linear 
© Prof. João Antônio de Vasconcelos 110 
 1.0000 1.0000 0.5000 0.0000 -0.5000 0.0000 0.0000 0.5000 1.0000 
-5.0000 -5.0000 -5.0000 -1.0000 1.0000 0.0000 0.0000 0.0000 -13.0000 
 
>> b(4,:)=b(4,:)-b(3,:)*b(4,1)/b(3,1) 
0.0000 -1.0000 0.0000 1.0000 1.0000 1.0000 0.0000 -1.0000 4.0000 
0.0000 1.0000 2.5000 0.0000 0.5000 0.0000 1.0000 -0.5000 4.0000 
1.0000 1.0000 0.5000 0.0000-0.5000 0.0000 0.0000 0.5000 1.0000 
0.0000 0.0000 -2.5000 -1.0000 -1.5000 0.0000 0.0000 2.5000 -8.0000 
 
>> b(3,:)=b(3,:)-b(2,:)*b(3,3)/b(2,3) 
0.0000 -1.0000 0.0000 1.0000 1.0000 1.0000 0.0000 -1.0000 4.0000 
0.0000 0.4000 1.0000 0.0000 0.2000 0.0000 0.4000 -0.2000 1.6000 
1.0000 0.8000 0.0000 0.0000 -0.6000 0.0000 -0.2000 0.6000 0.2000 
0.0000 0.0000 -2.5000 -1.0000 -1.5000 0.0000 0.0000 2.5000 -8.0000 
 
>> b(4,:)=b(4,:)-b(2,:)*b(4,3)/b(2,3) 
0.0000 -1.0000 0.0000 1.0000 1.0000 1.0000 0.0000 -1.0000 4.0000 
0.0000 0.4000 1.0000 0.0000 0.2000 0.0000 0.4000 -0.2000 1.6000 
1.0000 0.8000 0.0000 0.0000 -0.6000 0.0000 -0.2000 0.6000 0.2000 
0.0000 1.0000 0.0000 -1.0000 -1.0000 0.0000 1.0000 2.0000 -4.0000 
 
>> b(4,:)=b(4,:)-b(1,:)*b(4,4)/b(1,4) 
0.0000 -1.0000 0.0000 1.0000 1.0000 1.0000 0.0000 -1.0000 4.0000 
0.0000 0.4000 1.0000 0.0000 0.2000 0.0000 0.4000 -0.2000 1.6000 
Programação Linear 
© Prof. João Antônio de Vasconcelos 111 
1.0000 0.8000 0.0000 0.0000 -0.6000 0.0000 -0.2000 0.6000 0.2000 
0.0000 0.0000 0.0000 0.0000 0.0000 1.0000 1.0000 1.0000 0.0000 
 
Logo, a solução básica viável é x = [0.2 0.0 1.6 4.0 0.0]. Agora, o próximo passo é a 
construção da tabela Simplex para a etapa 2. Para isto, recuperamos os valores que nos 
interessam e acrescentamos no lugar da última linha os valores correspondentes ao vetor c= 
[-3 -1 -3 0 0] para o problema de minimização. 
 
 0.0000 -1.0000 0.0000 1.0000 1.0000 4.0000 
 0.0000 0.4000 1.0000 0.0000 0.2000 1.6000 
 1.0000 0.8000 0.0000 0.0000 -0.6000 0.2000 
-3.0000 -1.0000 -3.0000 0.0000 0.0000 0.0000 
 
Fazemos agora a eliminação dos termos da última linha abaixo das variáveis básicas: 
 
>> d(4,:)=d(4,:)-d(3,:)*d(4,1)/d(3,1) 
0.0000 -1.0000 0.0000 1.0000 1.0000 4.0000 
0.0000 0.4000 1.0000 0.0000 0.2000 1.6000 
1.0000 0.8000 0.0000 0.0000 -0.6000 0.2000 
0.0000 1.4000 -3.0000 0.0000 -1.8000 0.6000 
 
>> d(4,:)=d(4,:)-d(2,:)*d(4,3)/d(2,3) 
0.0000 -1.0000 0.0000 1.0000 1.0000 4.0000 
0.0000 0.4000 1.0000 0.0000 0.2000 1.6000 
Programação Linear 
© Prof. João Antônio de Vasconcelos 112 
1.0000 0.8000 0.0000 0.0000 -0.6000 0.2000 
0.0000 2.6000 0.0000 0.0000 -1.2000 5.4000 
 
>> d(2,:)=d(2,:)-d(1,:)*d(2,5)/d(1,5) 
0.0000 -1.0000 0.0000 1.0000 1.0000 4.0000 
0.0000 0.6000 1.0000 -0.2000 0.0000 0.8000 
1.0000 0.8000 0.0000 0.0000 -0.6000 0.2000 
0.0000 2.6000 0.0000 0.0000 -1.2000 5.4000 
 
>> d(3,:)=d(3,:)-d(1,:)*d(3,5)/d(1,5) 
0.0000 -1.0000 0.0000 1.0000 1.0000 4.0000 
0.0000 0.6000 1.0000 -0.2000 0.0000 0.8000 
1.0000 0.2000 0.0000 0.6000 0.0000 2.6000 
0.0000 2.6000 0.0000 0.0000 -1.2000 5.4000 
 
>> d(4,:)=d(4,:)-d(1,:)*d(4,5)/d(1,5) 
0.0000 -1.0000 0.0000 1.0000 1.0000 4.0000 
0.0000 0.6000 1.0000 -0.2000 0.0000 0.8000 
1.0000 0.2000 0.0000 0.6000 0.0000 2.6000 
0.0000 1.4000 0.0000 1.2000 0.0000 10.2000 
 
Logo, a solução para o problema original é x = [2.60 0.00 0.80], o que conduz a z = 10.20. 
 
Programação Linear 
© Prof. João Antônio de Vasconcelos 113 
O algoritmo do Método Simplex 
Como dito anteriormente, o método Simplex é um algoritmo que possibilita a resolução de 
problemas de programação linear. Está basicamente fundamentado na idéia de resolver 
repetidas vezes um sistema de equações lineares para obter uma sucessão de soluções 
básicas viáveis, cada uma ‘melhor’ que a anterior, até chegar numa solução viável básica 
ótima. 
 
 
 
 
 
 
 
 
 
Figura 02: Fluxograma do algoritmo Simplex 
Início 
Verifica o critério de parada? 
Passo Iterativo 
Não 
 
Sim
Programação Linear 
© Prof. João Antônio de Vasconcelos 114 
Cada nova solução básica viável é obtida substituindo uma variável básica por uma variável 
não-básica. Uma solução básica é ótima quando o valor da função objetivo a minimizar possui 
o menor valor. 
 Identificar uma Solução Básica Viável 
Existe uma 
solução básica 
viável melhor ? 
Move-se para a solução 
básica “melhor” 
Sim
Não FIM !!
A solução é ótima.
 
 
Figura 03: Fluxograma: Algoritmo Simplex 
Programação Linear 
© Prof. João Antônio de Vasconcelos 115 
 INÍCIO
Forma Padrão
Identificar uma Solução Básica Viável inicial 
Construir o quadro Simplex correspondente 
Calcular os custos reduzidos 
A solução é 
ótima? 
Critério de Otimalidade
FIM !!
A solução é ótima.
Identificar a variável não-básica que entra na base 
Critério de Entrada 
Ótimo não finito? 
Identificar a variável básica
que sai da base 
Critério de Saída 
Critério de Ótimo não finito
FIM !!
O problema não tem 
ótimo finito. 
Calcular nova Solução Básica Viável 
atualizando o quadro Simplex 
Sim 
Sim 
Não
Não
 
Figura 04: Fluxograma Iterativo do Método Simplex