capítulo 2

Prévia do material em texto

Métodos Quantitativos Aplicados 
Capítulo 2: Programação Linear 
Profª Márcia Machado. 
8 
2. A Programação Linear 
 
Muitas pessoas colocam o desenvolvimento da Programação Linear (PL) como um dos avanços 
científicos mais importantes do século XX. Seu impacto desde 1950 tem sido extraordinário. Hoje em dia é 
uma ferramenta padrão que tem possibilitado o ganho de milhares ou milhões de dólares para a maioria 
das companhias nos países industrializados. Além disso, seu uso em outros setores da sociedade vem 
crescendo rapidamente. 
 
O tipo mais comum de aplicação envolve o problema geral de distribuição de recursos limitados entre 
atividades que estão competindo por aqueles recursos, da melhor maneira possível (isto é, da maneira 
ótima). 
 
A Programação Linear usa um modelo matemático para descrever o problema. O termo linear significa 
que todas as funções matemáticas do modelo são obrigatoriamente, funções lineares. A palavra 
programação não se refere à programação de computadores, mas é um sinônimo de planejamento. A PL 
envolve o planejamento de atividades para obter um resultado ótimo, isto é, um resultado que atenda, da 
melhor forma possível, um determinado objetivo. 
 
Embora a alocação de recursos para atividades seja o tipo mais comum de aplicação, a Programação 
Linear tem numerosas outras aplicações. De fato, qualquer problema cujo modelo matemático se 
enquadre na forma geral de um modelo de PL, é Problema de Programação Linear (PPL). 
 
Para a formulação de um modelo matemático de programação linear, deve-se: 
 Definir claramente as variáveis de decisão; 
 Determinar a equação da função objetivo (FO) e o sentido da otimização 
desejado (maximizar ou minimizar); 
 Determinar as restrições impostas ao problema. 
 
A FO e as restrições devem ser expressas em termos das variáveis de decisão. 
 
As restrições para problemas de minimização, normalmente, são as necessidades que devem ser 
atendidas; para os problemas de maximização são as disponibilidades dos recursos existentes. 
 
Um procedimento extremamente eficiente, chamado Método Simplex, está disponível para resolver 
problemas de PL, mesmo aqueles com milhares variáveis. Desde 1947 até o final da década de 70, o 
Método Simplex foi o único algoritmo prático para a resolução de modelos de PL. Todos os programas-
pacote, profissionais, para a resolução de modelos de PL o utilizavam, apenas incorporando rotinas e 
artifícios visando diminuir o tempo de processamento e reduzir os erros de arredondamento inerentes aos 
cálculos efetuados em computador. 
 
Em 1979, o matemático russo L.G. Khachian publicou um artigo (Khachian, L. G. 1979. "A Polynomial 
Algorithm in Linear Programming." Soviet Mathematics Doklacly, Vol. 20: 191-194), apresentando um 
algoritmo alternativo para o Simplex. Embora tenha tido grande repercussão (a notícia, na época, saiu nos 
principais jornais do mundo, inclusive no Brasil) o algoritmo, embora de grande significado teórico, não 
teve equivalente repercussão prática, pois as soluções ótimas demoram muito mais tempo para serem 
encontradas do que se usando o Simplex. 
 
O trabalho de Khachian levou numerosos pesquisadores a tentarem caminhos alternativos ao seu 
método. Em 1984, Karmarkar publicou um artigo apresentando um novo algoritmo que, para determinados 
tipos de modelos, onde o Simplex é lento, tem apresentado resultados superiores. Como não poderia 
Métodos Quantitativos Aplicados 
Capítulo 2: Programação Linear 
Profª Márcia Machado. 
9 
deixar de ser, existe muita pesquisa em relação ao assunto e é possível que esta nova variante de 
resolução de modelos de PL venha a ser cada vez mais popular. 
 
2.1Modelos de Programação Linear 
2.1.1. Forma Padrão de um PPL 
 
O desenvolvimento de um algoritmo que determine a solução de um PPL muitas vezes torna necessária a 
redução deste problema a uma forma tal que permita a aplicação direta deste algoritmo. No caso da PL, o 
algoritmo mais utilizado é o Simplex. Para que o Simplex possa ser utilizado é preciso que o PPL 
encontre-se no seguinte formato: 
 
Forma Padrão: 
Max 
1
n
j j
j
z c x


 
 
 
1
, 0, ( 1,..., )
n
ij j i i
j
a x b b i m

  
 
 
0,( 1,..., )jx j n 
 
ou 
Max z= c1 x1 + c2 x2 + …+ cN xN 
sujeito a 
a11 x1 + a12 x2 + …+ a1N xN = b1 
a21 x1 + a22 x2 + …+ a2N xN = b2 
 … 
aM 1 x1 + aM 2 x2 + …+ aM N xN = bM 
x1, x2,…, xj,…, xN 0 
Sendo: 
 A função a maximizar (minimizar), Z= c1 x1 + c2 x2 + …+ cN xN , designa-se por função objetivo 
(FO). 
 As equações (inequações) designam-se por restrições. 
 As desigualdades x1 0, x2 0,…, xj 0,…, xN 0 designam-se por condições de não 
negatividade. 
 As variáveis (x1, x2,…, xj,…, xN ) designam-se por variáveis de decisão. 
 As constantes aij, bi, cj designam-se, respectivamente, por coeficientes tecnológicos, 
termos independentes e coeficientes da função objetivo. 
 
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 admissível (ou 
viável). 
O conjunto de todas as soluções admissíveis designa-se por conjunto de admissibilidade ou região de 
admissibilidade. 
Uma solução ótima maximiza (minimiza) a função objetivo em toda a região admissível. 
 
 
Métodos Quantitativos Aplicados 
Capítulo 2: Programação Linear 
Profª Márcia Machado. 
10 
2.1.2. Variações do Modelo Geral 
 
Mediante as operações a seguir indicadas, é sempre possível dar a qualquer problema a forma padrão, 
sem que o conjunto de soluções se altere. 
 
 FO de minimização 
Qualquer problema de maximização pode converter-se num problema de minimização, pois: 
máximo Z = - mínimo (-Z) 
 
 Algumas restrições do tipo ,  
Qualquer restrição de desigualdade pode ser convertida numa restrição de igualdade, através da 
introdução duma nova variável (variável de excesso ou folga) xN+1, de valor não negativo: 
  
ai 1 x1 + ai 2 x2 + …+ ai N xN  bi  bi - ai 1 x1 - ai 2 x2 - …- ai N xN  0 
  xN+1 = bi - ai 1 x1 - ai 2 x2- …- ai N xN  0, 
 Acrescentando-se a variável de folga xN+1, obtém-se: 
 ai 1 x1 + ai 2 x2 + …+ ai N xN + xN+1 = bi , x N+1  0 
 
  
Analogamente, se 
ai 1 x1 + ai 2 x2 + …+ ai N xN ≥ bi 
devemos acrescentar a variável de excesso xN+1, tal que; 
 ai 1 x1 + ai 2 x2 + …+ ai N xN - xN+1 = bi , x N+1  0 
 
 Ocorrência de bi < 0 
Qualquer -bi pode ser convertido, multiplicando-se por (-1) ambos os membros da restrição: 
 
 - ai 1 x1 - ai 2 x2 - …- ai N xN  - bi  ai 1 x1 + ai 2 x2 + …+ ai N xN  bI 
 
 
 Algumas das variáveis de decisão podem assumir qualquer valor, inclusive negativo. Neste 
caso são chamadas de irrestritas de sinal ou variáveis livres 
 
Qualquer variável livre (não restringida pela condição de não negatividade) xj, pode ser substituída por um 
par de variáveis não negativas xj
' 
 0 e xj
'' 
 0, fazendo xj = xj
' 
 - xj
'' 
e deste modo formulando de novo o 
problema em função destas duas novas variáveis. 
 
 
 
2.1.3. Hipóteses do modelo de PL 
Em qualquer modelo de Programação Linear encontram-se implícitas as seguintes hipóteses: 
ii.. PPrrooppoorrcciioonnaalliiddaaddee 
Esta consideração implica em que o nível da contribuição de uma variável qualquer é sempre 
proporcional ao seu valor. 
 
 
Métodos Quantitativos Aplicados 
Capítulo 2: Programação Linear 
Profª MárciaMachado. 
11 
iiii.. AAddiittiivviiddaaddee 
Implica em que não há interação entre as diversas variáveis do modelo, ou seja, a contribuição do total de 
variáveis é a soma das contribuições individuais de cada uma das variáveis. 
iiiiii.. DDiivviissiibbiilliiddaaddee 
A solução de um modelo de PL admite como solução ótima valores fracionários. 
iivv.. CCeerrtteezzaa 
Todos os parâmetros do sistema são constantes conhecidas não se aceitando nenhuma incerteza de 
qualquer tipo. 
 
 
2.1.4. Exemplos de Modelos de Problemas de Programação Linear 
 
EExxeemmpplloo 11:: 
Uma determinada companhia é grande fabricante de componentes de computadores, produzindo um 
grande número de componentes. Após uma pesquisa de mercado, o Departamento de Vendas concluiu 
que 2 novos produtos terão grande aceitação e todas as unidades produzidas serão vendidas. Os novos 
produtos serão designados por componente A e componente B. O processo produtivo desta companhia 
apresenta 3 importantes etapas. Na primeira, são cortados os elementos a serem utilizados. Na 2ª etapa, 
os elementos são classificados e, finalmente, na 3ª, os produtos são montados por um grupo de 
empregados. 
As informações disponíveis, por dia, para a produção destes 2 novos produtos estão mostradas na tabela 
abaixo: 
 
Etapa 
N
o
 de horas usadas por 
unidade produzida 
 
N
o
 de horas 
disponíveis na 
Produção Componente 
A 
Componente 
B 
1 1 - 4 
2 - 2 12 
3 3 2 18 
Lucro 
Unitário ($) 
3 5 
 
 
O objetivo da companhia é maximizar o seu lucro com a produção e venda desses dois produtos. 
SSoolluuççããoo ddee MMooddeellaaggeemm:: 
 
Para construir um modelo de PL temos que começar identificando o que se deseja saber ou conhecer no 
problema. A isto se dá o nome de variável de decisão. No nosso problema temos: 
x1 nº de unidades do componente A a ser produzida por dia 
x2 nº de unidades do componente B a ser produzida por dia 
Ou seja, xi (i = 1, 2) é a quantidade do componente i a ser produzida por dia. 
Em seguida, temos que identificar o objetivo que se deseja alcançar e traduzi-lo por uma função linear 
contendo as variáveis de decisão. Neste exemplo, o objetivo é maximizar o lucro total obtido com a 
produção dos 2 componentes. Esta função é chamada função objetivo e é representada , pela maioria dos 
autores, como uma função de uma variável z, apresentando o sentido de otimização, que neste caso, 
como o lucro é algo favorável, é de maximização. 
Métodos Quantitativos Aplicados 
Capítulo 2: Programação Linear 
Profª Márcia Machado. 
12 
FO: Max z = 3 x1 + 5 x2 
Os valores que x1 e x2 podem assumir estão restritos pelas limitações da empresa que, são as horas 
disponíveis em cada uma das 3 etapas.Temos que representar cada restrição física por uma expressão 
linear contendo as variáveis de decisão do modelo. 
A 1ª restrição diz que o nº de horas disponíveis na etapa 1 é de 4 horas. Matematicamente temos: x1  4. 
As restrições semelhantes para as etapas 2 e 3 são: 2x2  12 e 3x1 + 2 x2  18. 
Para finalizar o modelo, temos que lembrar que x1 e x2 representam unidades de componentes a serem 
produzidos e não podem assumir valores menores que zero. Isto é, x1  0, x2  0. 
Assim, 
 
Max z = 3 x1 + 5 x2 função objetivo 
 x1  4 
 2x2  12 restrições do modelo 
 3x1 + 2x2  18 
 x1  0, x2  0 restrições de não negatividade 
 
EExxeemmpplloo 22:: 
Um jovem atleta sente-se atraído pela prática de dois esportes: natação e ciclismo. Sabe-se por 
experiência que: 
A natação exige um gasto em mensalidade do clube e deslocamento até a piscina que pode ser expresso 
em um custo médio de R$13,00 por seção de treinamento (duas horas cada). 
O ciclismo, que exige equipamentos mais sofisticados, acaba custando cerca de R$ 22,00 pelo mesmo 
tempo de prática. 
O orçamento do rapaz dispõe de R$170,00 para seu treinamento. 
Seus afazeres de aluno de graduação na universidade lhe dão liberdade para empregar, no máximo, 36 
horas mensais e 80.000 calorias para os esforços físicos. 
Cada seção de natação consome 1.500 calorias, enquanto em cada etapa ciclística ele despende 2.000 
calorias. Considerando que o rapaz goste igualmente de ambos os esportes, o problema consiste em 
planejar seu treinamento de forma a maximizar o número de seções de treinamento. 
SSoolluuççããoo ddee MMooddeellaaggeemm:: 
As variáveis de decisão são: 
 x1 nº de seções de treinamento no esporte 1 - natação 
 x2 nº de seções de treinamento no esporte 2 – ciclismo 
 
 
Métodos Quantitativos Aplicados 
Capítulo 2: Programação Linear 
Profª Márcia Machado. 
13 
MATRIZ TECNOLÓGICA: 
Sempre que possível, deve-se elaborar a Matriz Tecnológica, um quadro resumo do problema, onde as 
variáveis de decisão são colocadas em coluna e as restrições listadas em linha, a fim de facilitar a 
elaboração do modelo matemático correspondente. 
 N
o
 de seções de treinamento 
Disponibilidade 
Natação Ciclismo 
Gastos 13 22 170 
Calorias 1500 2000 80.000 
Tempo 2 2 36 
Lucro Unitário ($) 1 1 
 
A função objetivo é de maximização (maior número possível de seções de treinamento) e como o 
esportista gosta igualmente das duas atividades: 
FO: Max z = x1 + x2 
Os valores que x1 e x2 podem assumir estão restritos pelas limitações do esportista em termos financeiros 
(gastos), de tempo e de capacidade física (calorias). Temos que representar cada restrição por uma 
expressão linear contendo as variáveis de decisão do modelo. 
A 1ª restrição indica a capacidade de gastos que o esportista é capaz de reservar para tais atividades, ou 
seja, cada seção de natação requer R$ 13,00, enquanto cada seção de ciclismo R$ 22,00, sendo que o 
rapaz não pode gastar mais do que R$ 170,00 por mês. Matematicamente: 13 x1 + 22 x2  170. 
As restrições semelhantes para as limitações de calorias e de tempo são: 1500 x1 + 2000 x2  80000 e 
x1 + x2  18. 
Para finalizar o modelo, temos que lembrar que x1 e x2 representam o nº de seções de cada esporte que o 
desportista irá praticar, não podendo, então, assumir valores menores que zero. Isto é, x1  0, x2  0 
Assim, 
Max z = x1 + x2 Função Objetivo 
 
 13 x1 + 22 x2  170 
1500 x1 + 2000 x2  80000 Restrições do Modelo 
 x1 + x2  18 
 
 x1  0, x2  0 Restrições de não Negatividade 
 
Métodos Quantitativos Aplicados 
Capítulo 2: Programação Linear 
Profª Márcia Machado. 
14 
2.1.5. Problemas Propostos: 
EExxeemmpplloo 33:: 
Uma companhia produz dois tipos de camisas: manga longa e manga curta. O único ponto crítico da 
empresa é a mão-de-obra disponível. 
A camisa de manga longa consome 50% a mais de mão-de-obra do que a de manga curta. Sabe-se que 
se toda a produção fosse concentrada na disponibilidade de camisas de manga curta, a companhia 
poderia entregar 400 camisas de manga curta por dia. 
O mercado limita a produção diária das camisas em 150 de mangas longas e 300 de mangas curtas. O 
lucro bruto por camisa de manga longa é de 5 u.m. e por camisa de manga curta 3,5 u.m. . 
Formular o problema de modo a permitir a determinação das quantidades de camisas a produzir de forma 
a otimizar o lucro. 
EExxeemmpplloo 44:: 
Uma fábrica de bolsas de plástico compra o plástico em rolos de uma certa largura. Em seguida corta o 
plástico em larguras menores, conforme o tipo de bolsa a ser produzida: tipo A, B e C. Em cada um dos 
cortes é possível produzir mais de uma bolsa, havendo também perda de material. 
A tabela dada a seguir apresentaas bolsas produzidas, conforme o tipo de corte: 
Bolsa Método de corte 
 1 2 3 4 5 
A 1 1 - - - 
B 1 - 2 1 - 
C - 2 1 3 5 
Perda 0,3 0,2 0,25 0,15 0,05 
 
Num determinado dia os pedidos de plástico para confecção das bolsas são 30 metros para a bolsa tipo 
A, 40 m para a bolsa tipo B e 50 m para a bolsa C. 
Como cortar o plástico para atender tais pedidos e minimizar a perda de material. 
EExxeemmpplloo 55:: 
Um investidor tem três alternativas de investimento , denominadas A, B e C, disponíveis no próximo ano. 
Essas alternativas não são mutuamente exclusivas. Qualquer dinheiro recebido de qualquer alternativa 
poderá ser reinvestido, imediatamente, em qualquer uma das três opções. 
A alternativa A está disponível no início de cada trimestre do ano. Cada real investido em A no princípio 
de um trimestre lhe devolve R$1,10 no final daquele trimestre. 
A alternativa B está disponível no início de cada semestre. Cada real investido em A no princípio de um 
semestre lhe devolve R$1,20 no final daquele semestre. 
A alternativa C só está disponível no princípio do primeiro ano. Cada real investido em C lhe devolve 
R$1,40 um ano mais tarde. 
O capital inicial do investidor é de R$ 10.000,00 e ele deseja maximizar seu capital ao final de um ano. Ele 
deseja diversificar suas aplicações e não deseja concentrar mais de R$5000,00 em um único 
investimento. 
Métodos Quantitativos Aplicados 
Capítulo 2: Programação Linear 
Profª Márcia Machado. 
15 
2.2 Soluções do modelo 
 
O objetivo da PL é determinar de entre as soluções admissí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. 
Ao resolver um problema de PL pode ocorrer uma das seguintes 
situações: 
 O problema tem uma única solução ótima 
Exemplo: 
 
No exemplo 1 temos uma só solução ótima: x1 = 2, x2 = 6 onde a 
função objetivo alcança o seu valor máximo: 36 
 
 
 
 O problema tem múltiplas soluções ótimas (uma infinidade) 
 
 
 
 
 
 
 
 
 
No exemplo 1, se o lucro unitário do produto 2 é mudado de 5 para 2, obtém-se como função objetivo: Z 
= 3x1 + 2x2. Neste caso, como as retas da função objetivo são paralelas à reta da 3ª restrição (3x1 + 2x2 
=18), todos os pontos do segmento de reta AB que une (2,6) com (4,3) são soluções ótimas (Z= 18), pois 
todas alcançam o melhor valor da F.O. (Z = 18). Como num segmento de reta existe um número infinito de 
pontos, o número de soluções ótimas neste caso é infinito. 
 
 O problema não tem ótimo finito 
A região de admissibilidade é não limitada e o valor da função objetivo Z cresce indefinidamente no 
sentido favorável (positivo ou negativo). 
Exemplo: 
 
 
 
 
 
 
No exemplo 1, eliminando as restrições: 2x 2  12, 3x1 + 2x 2  18, a região de admissibilidade fica não 
limitada e o valor da função objetivo pode crescer indefinidamente nesta região. 
642 x1
2
4
6
8
x2
Região das
soluções
admissíveis
(2,6) é a solução
Z =36= 3x
1 + 5x
2
Z =20= 3x
1 + 5x
2
Z =10= 3x
1 + 5x
2
642 x1
2
4
6
8
x2
x 1 = 4
Região das
soluções
admissíveis
 Z= 5x1 + 2x2
4 62
2
4
6
8
x1
x2
 3x1 + 2x2 = 18
Infinitas soluçõesInfinitas soluções
AA
BB
Métodos Quantitativos Aplicados 
Capítulo 2: Programação Linear 
Profª Márcia Machado. 
16 
 
 O problema é impossível, não tem nenhuma solução 
Isto acontece quando não existem soluções admissíveis, isto é, o conjunto de soluções admissíveis é 
vazio. 
2.2.1 Métodos de Solução 
 
aa)) PPrroobblleemmaass ccoomm dduuaass vvaarriiáávveeiiss 
Admitem resolução através: 
 Método Gráfico 
 Análise matemática 
 Algoritmo (Método Simplex). 
 
bb)) PPrroobblleemmaass ccoomm uumm nnúúmmeerroo qquuaallqquueerr ddee vvaarriiáávveeiiss 
Admitem resolução através: 
 Análise matemática 
 Algoritmo (Método Simplex) 
 
Por questão prática, sempre procuramos uma resolução dos problemas com o uso de aplicativos 
computacionais. 
 
2.2.1.1 RESOLUÇÃO GRÁFICA 
O Método Gráfico é uma forma para resolver modelos de PL limitado a problemas com duas ou 3 
variáveis. De fato, para modelos com 3 ou mais variáveis o método gráfico ou é impraticável ou é 
impossível. Contudo, o conhecimento desta ferramenta é de grande ajuda para a compreensão do 
processo de otimização e da ferramenta analítica de solução. 
 S = { x / A x = b e x > 0 } 
Métodos Quantitativos Aplicados 
Capítulo 2: Programação Linear 
Profª Márcia Machado. 
17 
A essência do Método consiste em montar, num mesmo plano cartesiano, as retas representativas de 
cada uma das restrições do problema. A seguir, deve-se delimitar a região de viabilidade – aquela que 
atende a todas as restrições existentes, e, finalmente, utilizar a reta da Função Objetivo (e o conjunto de 
retas a ela paralelas) para identificar a solução ótima. 
 
Quando existe uma solução ótima (finita) de um P.L., então existe um ponto extremo do conjunto de 
soluções factíveis (S) que é ÓTIMO. Isso leva a uma CONSEQUÊNCIA IMPORTANTE: o conjunto das 
soluções candidatas a ótimo de um P.L. fica restrito aos pontos extremos de S. 
 
EExxeemmpplloo 11:: 
Um fazendeiro deseja otimizar as plantações de arroz e milho na sua fazenda. O fazendeiro quer 
saber as áreas de arroz (x1) e milho (x2) que devem ser plantadas para que o seu lucro nas plantações 
seja máximo. O seu lucro por unidade de área plantada de arroz é 5 u.m., e por unidade de área plantada 
de milho é 2 u.m. 
As áreas plantadas de arroz e milho não devem ser maiores que 3 e 4, respectivamente. Cada 
unidade de área plantada de arroz consome 1 homem-hora. Cada unidade de área plantada de milho 
consome 2 homens-hora. O consumo total de homens-hora nas duas plantações não deve ser maior que 
9. 
 
SSoolluuççããoo ddee MMooddeellaaggeemm ee RReessoolluuççããoo GGrrááffiiccaa:: 
Sejam: 
x1 a área a ser plantada de arroz e 
x2 a área a ser plantada de milho. 
 
Do enunciado concluímos as restrições: 
 
x1  3 (I) 
x2  4 (II) sendo a função objetivo: Max Z = 5x1 + 2x2 
x1 + 2x2  9 (III) 
 
Como o problema tem apenas duas variáveis (x1 e x2), podemos resolvê-lo graficamente, conforme a Fig. 
1. 
 
A Fig. 1 é o resultado da alocação, num mesmo plano 
cartesiano, das retas (I), (II) e (III). Considerando-se a 
região de viabilidade estabelecida, determinamos os 
pontos vértices A(0,0), B(3,0), C(3,3), D(1,4) e E(0,4) 
como candidatos a ótimos. 
 
A função objetivo é Max Z = 5x1 + 2x2, que aplicada em 
cada vértice do polígono restritivo nos fornece os 
seguintes valores: 
ZA(0,0) = 0 
ZB(3,0) = 15 
ZC(3,3) = 21 
ZD(1,4) = 13 
ZE(0,4) = 8 
 
 
Verifica-se que o ponto “C” é o que fornece o maior valor para a função objetivo (Zmáx = 21). 
Assim, pode-se concluir que o lucro máximo do fazendeiro de 21 unidades monetárias, decorrerá da 
plantação de 3 unidades de área de arroz e 3 unidades de área de milho. 
 
 
 
 
 
Métodos Quantitativos Aplicados 
Capítulo 2: Programação Linear 
Profª Márcia Machado. 
18 
2.2.1.2 Resolução Algébrica 
Seja o Problema Linear: 
Max z = c x 
s.a. 
A x = b 
x > 0 
 
Considerando-se Am x n , n > m e tomando-se como BASE (conjunto de vetores linearmente 
independentes) uma matriz AI, onde I é um conjunto de índices ordenados, teremos: 
 
AI xI + AJ xJ = b 
Resolvendo o sistema de equações, teremos como solução: 
xI = ( A
I
 )
-1
 ( b – A
J
 xJ ) 
Na solução acima, x I é dependente do valor de xJ. 
Na resolução de um problema de P.L., obteremos a soluçãobásica x I, forçando as variáveis NÃO 
BÁSICAS a assumirem valor nulo (xJ = 0) e calculando x I = ( A
I
 )
–1
 b. Se a solução obtida for não 
negativa (isto é, x I >= 0), então ela é uma SOLUÇÃO BÁSICA FACTÍVEL DO PROBLEMA LINEAR. 
Exemplo : 
Max z = x1 + x2 
s.a. 
2 x1 + x2 < 8 
 x1 + 2x2 < 7 
 x2 < 3 
x1, x2 > 0 
 
Passando para a FORMA PADRÃO, temos: 
Max z = x1 + x2 
s.a. 
2 x1 + x2 + x3 = 8 
 x1 + 2x2 + x4 = 7 
 x2 + x5 = 3 
xi > 0, i = 1, 2, 3, 4, 5 
A tabela abaixo mostra os valores das variáveis xi obtidos para as diferentes bases: 
 
I J x1 x2 x3 x4 x5 z 
[3,4,5] [1,2] 0 0 8 7 3 0 Básica factível 
[1,4,5] [2,3] 4 0 0 3 3 4 Básica factível 
[1,2.5] [3,4] 3 2 0 0 1 5 Básica factível 
[1,2,3] [4,5] 1 3 3 0 0 4 Básica factível 
[4,2,3] [1,5] 0 3 5 1 0 3 Básica factível 
[5,2,3] [1,4] 0 7/2 9/2 0 -1/2 7/2 
BÁSICA 
INFACTÍVEL 
 
 
A figura abaixo mostra graficamente a região de soluções factíveis, bem como os pontos extremos dessa 
região. Esses pontos são candidatos ao ótimo da solução e são, necessariamente, soluções básicas. 
Métodos Quantitativos Aplicados 
Capítulo 2: Programação Linear 
Profª Márcia Machado. 
19 
 
 
Um método simplista que se poderia pensar como suficiente para resolver um P.L. seria: 
· Listar todas as soluções básicas 
· Avaliar a função objetivo sobre elas e escolher a de maior valor 
Uma das desvantagens (e, em alguns casos, limitações) da utilização desse método simplista é que o 
número de combinações possíveis para os conjuntos I e J pode ser muito grande, Cnm. 
 
Uma outra desvantagem da utilização desse método é a impossibilidade de se encontrar a solução ótima, 
quando essa for ilimitada, e a dificuldade de se detectar a inconsistência do Problema Linear, quando não 
existe solução factível. Utilizando-se esse método, seria necessário testar TODAS as combinações 
possíveis para os conjuntos I e J e se não fosse encontrada nenhuma solução possível, então poder-se-ia 
afirmar que o problema é inconsistente. 
 
A utilização de um método mais eficaz e inteligente se faz necessária. O Método SIMPLEX será o método 
utilizado para resolver os Problemas de Programação Linear.