Apostila_Pesquisa Operacional_2013_Dr_Volpi

Prévia do material em texto

PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 1 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
 
 
APOSTILA DE PESQUISA 
OPERACIONAL 
 
 
 
 
 
 Prof. Dr. Almir Volpi 
 
 
 
2013 
 
 
 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 2 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
 
 
AA PP OO SS TT II LL AA EE MM AA TT EE RR II AA LL DD II DD ÁÁ TT II CC OO –– TT EE OO RR II AA EE EE XX EE RR CC ÍÍ CC II OO SS 
PPeessqquuiissaa OOppeerraacciioonnaall 
© Todos os direitos reservados 
PROIBIDA A REPRODUÇÃO E DISTRIBUIÇÃO SEM PRÉVIA AUTORIZAÇÃO DO AUTOR 
Prof. Dr. Almir Volpi - avolpi@terra.com.br 
 
 
 
 
 
 
 
 
22001133 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 3 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
ÍNDICE 
 
 
PESQUISA OPERACIONAL 
▪ Conceitos Centrais 
▪ Histórico da Pesquisa Operacional 
▪ Natureza da Pesquisa Operacional 
▪ Fases de Estudo da Pesquisa Operacional. 
▪ Técnicas Matemáticas na Pesquisa Operacional 
 
PROGRAMAÇÃO LINEAR 
▪ Introdução e Conceitos Centaris 
▪ Característica da Programação Linear 
▪ Formulação de Problemas 
▪ Modelagem 
▪ Exercícios Propostos 
▪ Teoremas da Programação Linear 
▪ Solução Gráfica 
▪ Solução Ótima 
▪ Exercícios Propostos 
 
REVISÃO DE MATRIZES 
▪ Tipos de Matrizes 
▪ Determinantes 
▪ Regra de SARRUS 
 
REVISÃO DE SISTEMA LINEAR 
▪ Regra de CRAMER 
▪ Algoritmo de GAUSS-JORDAN 
 
MÉTODO SIMPLEX 
▪ Conceitos Centrais 
▪ Variáveis 
▪ Roteiro do Método 
▪ Exercícios Propostos 
 
 
 
 
 
 
 
 
 
 
 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 4 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 5 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
PESQUISA OPERACIONAL 
 
CONCEITOS CENTRAIS 
 
A Pesquisa Operacional tem sua origem antes da II Guerra Mundial na Inglaterra com o objetivo de auxiliar a 
defesa do país e identificar oportunidades para Maximizar os resultados de suas ações. O desafio dos 
estrategistas da época estava centrado na distribuição de recursos escassos buscando uma solução ótima para o 
problema, que neste caso se destinava a avaliar e reposicionar os radares do sistema aéreo de defesa da Grã-
Bretanha em 1938 prestes ao início da guerra. Baseado em problemas matemáticos a Pesquisa Operacional se 
torna um modelo de tomada de decisão. 
 
Devido aos bons resultados alcançados pelos ingleses os EUA passam a utilizá-la em atividades semelhantes. 
Com o final da II GM a P.O. se popularizou e passou a ser aplicada no campo de gerenciamento de negócios e da 
administração da produção. Baseada em sofisticados conceitos da Matemática e da Estatística a P.O. apresenta 
grandes benefícios na resolução de problemas complexos de transportes, alocação de recursos, Maximização e 
minimização. Em 1947 George Dantzig desenvolveu o processo metodológico mais importante do período pós-
guerra intitulado "MÉTODO SIMPLEX" proporcionando um "roteiro" para a resolução de problemas de 
Programação Linear1. 
 
Para Marins (2011, p. 14) o rápido crescimento da PO no pós-guerra deve-se ao desenvolvimento de técnicas 
específicas, tais como o Método SIMPLEX para a Programação Linear, e ao grande progresso alcançado no 
desenvolvimento dos computadores eletrônicos. A expansão da PO no mundo acadêmico se deu inicialmente nos 
departamentos de Engenharia Industrial e de Engenharia de Produção, e nas escolas de Administração das 
Universidades norte-americanas. 
 
No Brasil, a P.O. iniciou na década de 1960. O primeiro Simpósio Brasileiro de Pesquisa Operacional (SBPO) foi 
realizado em 1968 no ITA e incluía alguns pesquisadores do país. Em seguida, foi criada a Sociedade Brasileira de 
Pesquisa Operacional (SOBRAPO) em 1969. 
 
A Pesquisa Operacional é uma ciência aplicada voltada para a resolução de problemas reais. TTeennddoo ccoommoo ffooccoo aa 
ttoommaaddaa ddee ddeecciissõõeess, aplica conceitos e métodos de várias áreas científicas na concepção, planejamento ou 
operação de sistemas. A Pesquisa Operacional é usada para avaliar linhas de ação alternativas e encontrar as 
soluções que melhor servem aos objetivos dos indivíduos ou organizações2. Para Silva (1998; p.12) a Pesquisa 
Operacional é um método científico de tomada de decisões que em linha gerais, consiste na descrição de um 
sistema organizado com o auxílio de um modelo, e através da experimentação com o modelo, na descoberta da 
melhor maneira de operar o sistema. 
 
 
A NATUREZA DA PESQUISA OPERACIONAL 
 
Um estudo de Pesquisa Operacional consiste em construir um "modelo" a partir de um sistema real existente com 
o objetivo de compreender o comportamento dessa situação, com o objetivo conforme resentar o resultado que se 
deseja. A complexidade de um sistema real resulta do fato de que seu comportamento é influenciado por um 
 
1 É uma ferramenta matemática que permite encontrar a solução ótima para certos tipos de problemas. O termo "linear" se refere a 
linearidade das equações do problema. Também pode ser considerada como uma série de operações matemáticas que são 
utilizadas para "alocar" recursos escassos em operações simultâneas na busca de solução ótima para um único objetivo. 
2 Disponível em: < http://www.sobrapo.org.br/o_que_e_po.php >. Acesso em 05/12/2012. 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL6 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
número muito grande de elementos variáveis, sendo estas "variáveis" influenciadas pelas "restrições" que são a 
parte comum em todos os problemas de P.O. 
 
Problemas de P.O. são normalmente apresentados na forma de uma função objetivo (por exemplo, Maximizar o 
lucro da empresa, minimizar o custo de produção, determinar quantidades mínimas e máximas em misturas, 
determinar rotas de transportes, etc.) e diversas restrições (associadas, por exemplo, à disponibilidade de 
matérias-primas, mão de obra, etc.) e possuem as seguintes características: 
 
▪ O problema possui um conjunto de variáveis manipuláveis no procedimento de busca pelo ótimo; essas 
são as variáveis de decisão do problema. 
▪ Uma função objetivo compõe o critério de otimalidade, sendo escrita em termos das variáveis de decisão 
do problema. A função objetivo é uma função linear das variáveis de decisão, devendo ser Maximizada ou 
minimizada. 
▪ Os valores assumidos pelas variáveis de decisão devem satisfazer um conjunto de restrições, que 
compõem a região de soluções viáveis do problema. 
▪ As variáveis de decisão podem assumir valores pré-estabelcidos no domínio dos números reais (isto é, 
valores positivos, negativos ou ambos). 
 
 
FASES DE ESTUDO DA P.O. 
 
Cinco fases num projeto de PO: 
 
▪ Formulação do problema (identificação do sistema) 
▪ Construção do modelo matemático 
▪ Obtenção da solução 
▪ Teste do modelo e avaliação da solução obtida 
▪ Estabelecimento de controles da solução 
▪ Implantação 
 
1- Formulação do Problema: Para se formular corretamente um problema é necessário que o mesmo seja bem 
identificado e seu sistema seja explanado, desta forma são necessárias algumas informações básicas, como qual 
é o objetivo do problema, quais os caminhos que definem suas restrições, quais as limitações técnicas do sistema 
e qual a medidas de eficiência para o sistema para "ordenar" as soluções encontradas concluindo o processo de 
decisão 
 
2- Construção do Modelo Matemático: Um modelo matemático de um problema real é uma representação 
através de expressões matemáticas que descrevem a essência do problema. Se existirem n decisões 
quantificáveis, elas serão representadas por n variáveis de decisão ou de controle. As relações e limitações a que 
estão sujeitas as variáveis de decisão são expressas por meio de equações e inequações, denominadas 
restrições. OO oobbjjeettiivvoo qquuee ssee pprreetteennddee aattiinnggiirr éé ffoorrmmuullaaddoo ccoommoo uummaa ffuunnççããoo ((oouu mmaaiiss ddee uummaa)),, ccoollooccaaddaa eemm 
tteerrmmooss ddaass vvaarriiáávveeiiss ddee ddeecciissããoo,, ddeennoommiinnaaddaa ffuunnççããoo oobbjjeettiivvoo.. Se o modelo elaborado tem a forma de um modelo 
conhecido, a solução pode ser obtida através de métodos matemáticos convencionais. Por outro lado, se as 
relações matemáticas são muito complexas, talvez se faça necessária a utilização de combinações de 
metodologias. 
 
3- Obter a solução: Uma vez construído o modelo matemático parte-se para a obtenção de uma solução. 
Diversos são os métodos matemáticos utilizados em P.O., associados às várias áreas que compõe a P.O. como 
Programação Linear, Teoria das Filas. A área de T.I. vem desenvolvendo diversos softwares, que disponibilizam 
métodos importantes da Pesquisa Operacional tornando viável e eficiente a solução de problemas complexos. 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 7 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
Podemos citar o SOLVER do Excel que atua com planilhas eletrônicas, o LINDO – Linear Discrete Optimizer 
(www.lindo.com). Ao contrário das outras fases, que não possuem regras fixas, a solução do modelo é baseada 
geralmente em técnicas matemáticas existentes. No caso de um modelo matemático, a solução é obtida pelo 
algoritmo mais adequado, em termos de rapidez de processamento e precisão da resposta. Isto exige um 
conhecimento profundo das principais técnicas existentes. A solução obtida, neste caso, é dita "ótima". 
 
4- Teste do Modelo e Avaliação da Solução: Dada a complexidade dos problemas existe a possibilidade de 
erros na elaboração do modelo. Essa distorção levará a soluções que não se ajustarão à realidade. Dessa forma, o 
modelo precisa ser testado. Em alguns casos o modelo pode ser testado através da reconstrução do passado (uso 
de dado históricos), verificando-se a adequação do modelo às informações disponíveis. Em cada situação 
especifica pode ser definida uma sistemática para testar o modelo e sua solução. Um modelo é válido se, levando-
se em conta sua inexatidão em representar o sistema, ele for capaz de fornecer uma previsão aceitável do 
comportamento do sistema. 
 
5- Estabelecimento de controles da solução: A construção e experimentação com o modelo identificam 
parâmetros fundamentais para a solução do problema. Qualquer mudança nesses parâmetros deve ser controlada 
para garantir a validade da solução. Caso ocorra qualquer modificação nestes parâmetros (além do permitido) uma 
nova solução ou até mesmo um novo modelo deverá ser considerado. 
 
6- Implementação: A última fase de um estudo de P.O. é implementar a solução final, uma vez que esta seja 
aprovada. É uma fase crítica, pois é neste momento que os cálculos serão efetivados e, portanto, aptos a gerar 
resultados sobre os objetivos desejados inicialmente. 
 
 
 
TÉCNICAS MATEMÁTICAS EM PESQUISA OPERACIONAL 
 
A formulação do modelo depende diretamente do sistema a ser representado. A função objetivo e as funções de 
restrições podem ser lineares ou não- lineares. As variáveis de decisão podem ser contínuas ou discretas (por 
exemplo, inteiras) e os parâmetros podem ser determinísticos ou probabilísticos. 
 
O resultado dessa diversidade de representações de sistemas é o desenvolvimento de diversas técnicas de 
otimização, de modo a resolver cada tipo de modelo existente. Estas técnicas incluem, principalmente: 
pprrooggrraammaaççããoo lliinneeaarr é utilizada para analisar modelos onde as restrições e a função objetivo são lineares; 
pprrooggrraammaaççããoo iinntteeiirraa se aplica a modelos que possuem variáveis inteiras (ou discretas),, pprrooggrraammaaççããoo ddiinnââmmiiccaa é 
utilizada em modelos onde o problema completo pode ser decomposto em subproblemas menores,, pprrooggrraammaaççããoo 
eessttooccáássttiiccaa é aplicada a uma classe especial de modelos onde os parâmetros são descritos por funções de 
probabilidade ee pprrooggrraammaaççããoo nnããoo-- lliinneeaarr é utilizada em modelos contendo funções não- lineares. 
 
Uma característica presente em quase todas as técnicas de programação matemática é que a solução ótima do 
problema não pode ser obtida em um único passo, devendo ser obtida iterativamente. É escolhida uma solução 
inicial (que geralmente não é a solução ótima). Um aallggoorriittmmoo3 é especificado para determinar, a partir desta, uma 
nova solução, que geralmente é superior à anterior. Este passo é repetido até que a solução ótima seja alcançada 
(supondo que ela existe). 
 
 
3 Algoritmo é uma sequência lógica e finita de instruções definidas e não ambíguas que devem ser seguidas para a realização de 
uma tarefa na busca de uma solução.Sequência finita de regras, raciocínios ou operações que, aplicada a um número finito de 
dados, permite solucionar classes semelhantes de problemas. 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 8 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
PROGRAMAÇÃO LINEAR 
 
INTRODUÇÃO - Definições e Conceitos 
 
A Programação Linear tem como objetivo encontrar a solução ótima para problemas que tenham seus modelos 
representados por expressões lineares. A sua simplicidade é apresentada devido a linearidade do modelo. A 
aplicabilidade da Programação Linear consiste na Maximização ou Minimização de uma função linear, denominada 
Função Objetivo, respeitando-se um sistema linear de igualdades ou desigualdades, que recebem o nome de 
Restrições do Modelo. 
 
Normalmente neste tipo de decisão os recursos disponíveis não são suficientes para que todas as atividades 
sejam executadas no nível mais elevado que se pretende, desta forma, a solução neste caso é encontrar a mmeellhhoorr 
distribuição dos recursos entre as diversas tarefas ou atividades de forma que seja possível aattiinnggiirr uumm vvaalloorr óóttiimmoo 
do objetivo estabelecido. Uma característica deste problema é que ele pode ser representado por um modelo de 
otimização onde as relações matemáticas são lineares. 
 
Função Objetivo: É uma função linear que se pretende otimizar, ou seja, será a função a ser Maximizada ou 
minimizada. 
 
Restrições: São as atividades e ou quantidades que devem ser respeitadas de acordo com os recursos 
disponíveis ou a serem utilizados. São normalmente escritos sob a forma de inequações4 ou equações lineares. 
 
▪ Restrições de não negatividade - quando as variáveis que entram na 
formulação não podem assumir valores negativos. 
▪ Restrições do Problema - lista ou "rol" de restrições que implique na possível 
solução do problema. As restrições do problema originam a chamada região da admissível de solução. 
 
Solução: Solução qualquer especificação de valores (dentro do domínio da função-objetivo, f) para as variáveis de 
decisão, independente de se tratar de uma escolha desejável ou permissível. 
 
Solução viável: Solução viável é uma solução em que todas as restrições são satisfeitas 
 
Solução Impossível: É aquela que não há qualquer valor que satisfaça ao conjunto de restrições. 
 
Solução ilimitada: É aquela que a função objetivo aceita valores indefinidamente, e estes atendem a todas as 
restrições do problema. 
 
Solução ótima: É a solução possível que faz com que os objetivos do problema sejam "mais favorável" ou seja, 
que otimiza a função objetivo. 
 
Variáveis de decisão: São as variáveis, ou seja, as incógnitas a serem determinadas pela solução do modelo. 
São as variáveis reais x1, x2, x3, x4 .... Xn. 
 
Variáveis de folga: É uma variável auxiliar, não negativa e de coeficiente unitário que se introduz no modelo para 
reduzir uma restrição na forma de igualdade as demais restrições. 
 
4 Inequação é toda a desigualdade literal que é apenas satisfeita por certos valores, as letras ou incógnitas que nela figuram, por 
outras palavras, apresentam os sinais de maior (>) ou menor (<) ao invés do sinal de igualdade que é o caracteriza as equações. 
Disponível em: < http://aprendermmatematica.blogspot.com.br/p/inequacoes.html >. Acesso em: 10/12/2012. 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 9 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
 
CARACTERÍSTICA DA PROGRAMAÇÃO LINEAR 
 
Para representar um problema de otimização como um programa linear, diversas características necessitam ser 
previamente discutidas e analisadas junto à formulação do problema de programação linear. Segundo 
Lechtermacher (2007, p. 20) todo problema de Programação Linear parte de algumas hipóteses que são 
assumidas quando tentamos resolvê-los: 
 
Proporcionalidade: O valor da função-objetivo é diretamente proporcional ao nível de atividade de cada variável 
de decisão. 
 
Aditividade: Considera as atividades (variáveis de decisão) do modelo como entidades totalmente independentes, 
não permitindo que haja interdependência entre as mesmas, isto é, não permitindo a existência de termos 
cruzados, tanto na função-objetivo como nas restrições. 
 
Divisibilidade: Assume que todas as unidades de atividade possam ser divididas em qualquer nível ffrraacciioonnaall, isto 
é, qualquer variável de decisão pode assumir qualquer valor fracionário. 
 
Certeza: Assume que todos os parâmetros do modelo são constantes conhecidas. Em problemas reais, a certeza 
quase nunca é satisfeita, provocando a necessidade de análise de sensibilidade dos resultados. 
 
 
FORMULAÇÃO DE PROBLEMAS DE PROGRAMAÇÃO LINEAR 
 
Não eXiste uma forma única para formular ou desenvolver um problema de P.L. porém, é possível estar atento aos 
seguintes aspectos: 
 
▪ Identificação das variáveis de decisão 
▪ Identificação da função objetivo 
▪ Identificação das Restrições 
▪ Formulação matemática 
 
De posse das informações acima se torna viável a solução do problema. O método de P.L. permite a solução 
gráfica e a solução algébrica que permite mais facilmente tomar decisões mais acertadas no domínio da gestão de 
aplicações como:Planejamento agregado, análise de produtividade de serviços, planejamento de produtos, 
otimização do fluxo de produção e de processos produtivos, e são também aplicadas em outros setores como: 
medicina, agricultura, campo militar, setor de transportes, política florestal etc.. 
 
 
ROTEIRO PARA MODELAGEM 
 
Os problemas de Programação Linear estão entre as aplicações mais bem-sucedidas comercialmente da 
Pesquisa Operacional; proporcionando considerável impacto econômico. Quando se estrutura problema sob a 
forma de um modelo matemático, tem-se como objetivo auxiliar o processo de decisão. Normalmente o problema 
resume-se na Maximização (ou minimização) de uma função linear, a função objetiva, sujeita a restrições também 
lineares. Não existe uma forma básica para modelar problemas de P.L., mas podemos estabelecer alguns passos 
capazes de "simplificar" a modelagem, sendo: 
 
Passo I. Quais as variáveis de decisão? 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 1 0 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
Identifique as variáveis desconhecidas a serem determinadas (elas são denominadas variáveis de decisão) e 
represente-as através de símbolos algébricos (por exemplo, x e y ou x1 e x2). 
Passo II. Qual é o objetivo? 
Identifique o objetivo ou critério de otimização do problema, representando-o como umafunção linear das variáveis 
de decisão. O objetivo pode ser do tipo Maximizar lucros ou minimizar custos e perdas. A função objetivo é a 
expressão que calcula o valor do objetivo (lucro, custo, receita, perda etc.), em função das variáveis de decisão. 
 
 
Passo III. Quais as restrições? 
Liste todas as restrições do problema e expresse-as como equações (=) ou inequações (≤, ≥) lineares em termos 
das variáveis de decisão definidas no passo anterior. Cada restrição imposta na descrição do sistema deve ser 
expressa como uma relação linear (igualdade ou desigualdade), montadas com as variáveis de decisão. 
 
Um modelo de Programação Linear é um modelo matemático de otimização no qual todas as funções são lineares. 
Estes modelos são compostos por uma função objetivo linear e por restrições técnicas representadas por um 
grupo de inequações também lineares. 
 
 
Exemplo 1: 
Uma empresa fabrica dois produtos P1 e P2. O lucro unitário de P1 é de 1.000 unidades monetárias; e o lucro de 
P2 é de 1.800 unidades monetárias. A empresa precisa de 20 horas para fabricar uma unidade de P1 e de 30 
horas para fabricar uma unidade de P2. O tempo anual de produção disponível para isso é de 1200 horas. A 
demanda esperada para cada produto é de 40 unidades anuais para P1 e 30 unidades anuais para P2. Qual é o 
plano de produção para que a empresa Maximize seu lucro nesses itens? Construa o modelo de programação 
linear para esse caso. (SILVA, 2010, p. 6). 
 
Solução: 
 
aa)) QQuuaaiiss aass vvaarriiáávveeiiss ddee ddeecciissããoo?? 
O que deve ser decidido é o plano de produção, isto é, quais as quantidades anuais que devem ser produzidas de 
P1 e P2. Portanto, as variáveis de decisão serão x1 e x2, onde: 
x1 → quantidade anual a produzir de P1. 
x2 → quantidade anual a produzir de P2. 
 
bb)) QQuuaall oo oobbjjeettiivvoo?? 
O objetivo é Maximizar o lucro, que pode ser calculado por: 
Lucro devido a P1: 1000.x1 (lucro de P1 multiplicado pela quantidade produzida de P1). 
Lucro devido a P2: 1800.x2 (lucro de P2 multiplicado pela quantidade produzida de P2). 
 
Os lucros acima são obtidos multiplicando-se o lucro unitário pela quantidade produzida (xi). Assim, o lucro total 
será dado por: 
Lucro total: L = 1000.x1 + 1800.x2 
 
PPoorrttaannttoo oo oobbjjeettiivvoo sseerráá MMaaxxiimmiizzaarr L = 1000.x1 + 1800.x2 
 
cc)) QQuuaaiiss aass rreessttrriiççõõeess?? 
As restrições impostas pelo sistema são: 
▪ Disponibilidade de horas para a produção: 1200 horas. 
horas ocupadas com P1: 20.x1 (uso por unidade multiplicado pela quantidade produzida de P1). 
horas ocupadas com P2: 30.x2 (uso por unidade multiplicado pela quantidade produzida de P2). 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 1 1 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
As horas acima são obtidas multiplicando-se o número de horas utilizadas na produção de uma unidade do 
produto (Pi) pela quantidade produzida xi. 
 
Assim, o total de horas utilizadas na produção será dada por: 20x1 + 30x2 
 
Como a disponibilidade é de 1200 horas, temos a primeira restrição: 20x1 + 30x2 ≤ 1200 
 
▪ Disponibilidade de mercado para os produtos (demanda): 
Disponibilidade de P1: 40 unidades e a quantidade a produzir de P1: x1 
Logo, temos a seguinte restrição: x1 ≤ 40 
 
Disponibilidade de P2: 30 unidades e a quantidade a produzir de P2: x2 
Logo, temos a seguinte restrição: x2 ≤ 30 
 
Resumindo, o modelo de Programação Linear para o problema proposto será: 
 
 Max L = 1000x1 + 1800x2 
 
Sujeito a: 
 20x1 + 30x2 ≤ 1.200 
 Restrições técnicas x1 ≤ 40 
 x2 ≤ 30 
 
 x1 ≥ 0 
 Restrições de não negatividade x2 ≥ 0 
 
 
Exemplo 2: 
Para uma boa alimentação, o corpo necessita de vitaminas e proteínas. A necessidade mínima de vitaminas é de 
32 unidades por dia e a de proteínas de 36 unidades por dia. Uma pessoa tem disponível carne e ovos para se 
alimentar. Cada unidade de carne contém 4 unidades de vitaminas e 6 unidades de proteínas. Cada unidade de 
ovo contém 8 unidades de vitaminas e 6 unidades de proteínas. Qual a quantidade diária de carne e ovos que 
deve ser consumida para suprir as necessidades de vitaminas e proteínas com o menor custo possível? Cada 
unidade 
de carne custa 3 unidades monetárias e cada unidade de ovo custa 2,5 unidades monetárias. 
 
Solução: 
 
aa)) QQuuaaiiss aass vvaarriiáávveeiiss ddee ddeecciissããoo?? 
Devemos decidir quais as quantidades de carne e ovos a pessoa deve consumir no dia. As variáveis de decisão 
serão, portanto: 
x1 → quantidade de carne a consumir no dia. 
x2 → quantidade de ovos a consumir no dia. 
 
bb)) QQuuaall oo oobbjjeettiivvoo?? 
O objetivo é minimizar o custo, que pode ser calculado por: 
Custo devido à carne: 3.x1 (custo por unidade multiplicado pela quantidade a consumir de carne). 
Custo devido aos ovos: 2,5.x2 (custo por unidade multiplicado pela quantidade a consumir de ovos). 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 1 2 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
Os custos acima são obtidos multiplicando-se o custo unitário de cada produto pela quantidade do produto a ser 
consumida (xi). Assim, o custo total será dado por: 
 
Custo total: C = 3x1 + 2,5x2 
 
PPoorrttaannttoo oo oobbjjeettiivvoo sseerráá mmiinniimmiizzaarr C = 3x1 + 2,5x2 
 
cc)) QQuuaaiiss aass rreessttrriiççõõeess?? 
As restrições impostas pelo sistema são: 
▪ Necessidade mínima de vitamina: 32 unidades 
Vitamina de carne: 4.x1 (quantidade por unidade multiplicado pela unidade de carnes a consumir). 
Vitamina de ovos: 8.x2 (quantidade por unidade multiplicado pela unidade de ovos a consumir). 
 
As quantidades de vitamina são obtidas multiplicando-se quantidade de vitamina fornecida por cada alimento pela 
quantidade a ser consumida (xi). Assim, o total de vitaminas consumido será dado por: 4x1 + 8x2 
 
Como a necessidade mínima é de 32 unidades, temos a primeira restrição: 4x1 + 8x2 ≥ 32 
 
▪ Necessidade mínima de proteína: 36 unidades 
proteína de carne: 6.x1 (quantidade por unidade multiplicado pela unidade de carnes a consumir). 
proteína de ovos: 6.x2 (quantidade por unidade multiplicado pela unidade de ovos a consumir). 
 
As quantidades de proteína são obtidas multiplicando-se quantidade de proteína fornecida por cada alimento pela 
quantidade a ser consumida (xi). Assim, o total de proteínas consumido será dado por: 6x1 + 6x2 
 
Como a necessidade mínima é de 36 unidades, temos a segunda restrição: 6x1 + 6x2 ≥ 36 
 
Resumindo, o modelo de Programação Linear para o problema proposto é: 
 
 Min C = 3x1 + 2,5x2 
 
Sujeito a: 
 4x1 + 8x2 ≥ 32 
 Restrições técnicas 6x1 + 6X2 ≥ 36 
 
 x1 ≥ 0 
 Restrições de não negatividade x2 ≥ 0 
 
 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL1 3 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
Exercícios Propostos: 
 
1) Um sapateiro faz 6 sapatos por hora, se fizer somente sapatos, e 5 cintos por hora, se fizer somente cintos. Ele 
gasta 2 unidades de couro para fabricar 1 unidade de sapato e 1 unidade de couro para fabricar uma unidade de 
cinto. Sabendo-se que o total disponível de couro é de 6 unidades e que o lucro unitário por sapato é de 5 
unidades monetárias e o cinto é de 2 unidades monetárias, pede-se: o modelo do sistema de produção do 
sapateiro, se o objetivo é Maximizar seu lucro por hora. 
 
 
2) Uma empresa fabrica 2 produtos P1 e P2. O lucro por unidade de P1 é de 100 u.m. e o lucro unitário de P2 é 
150 u.m. A empresa necessita de 2 horas para fabricar uma unidade de P1 e 3 horas para fabricar uma unidade de 
P2. O tempo mensal disponível para essa atividade é de 120 horas. As demandas esperadas para os 2 produtos 
levaram a empresa a determinar que os montantes produzidos de P1 e P2 não devem ultrapassar 40 unidades de 
P1 e 30 unidades de P2 por mês. Construa o modelo do sistema de produção mensal com o objetivo de Maximizar 
o lucro da empresa. 
 
 
3) Uma empresa produz 2 produtos em uma de suas fábricas. Na fabricação dos 2 produtos, 3 insumos são 
críticos em termos de restringir o número de unidades dos 2 produtos que podem ser produzidas: as quantidades 
de matéria prima (tipos A e B) disponíveis e a mão de obra disponível para a produção dos 2 produtos. Assim, o 
Departamento de Produção já sabe que, para o próximo mês, a fábrica terá disponível, para a fabricação dos 2 
produtos, 4.900 quilogramas da matéria prima A e 4.500 quilogramas da matéria prima B. Cada unidade do 
produto tipo I, para ser produzida consome 70 quilogramas da matéria prima A e 90 quilogramas da matéria prima 
B. Por sua vez, cada unidade do produto tipo II para ser produzida, utiliza 70 quilogramas da matéria prima tipo A e 
50 quilogramas da matéria prima tipo B. Como a produção dos 2 produtos utiliza processos diferentes, a mão de 
obra é especializada e diferente para cada tipo de produto, ou seja, não se pode utilizar a mão de obra disponível 
para a fabricação de um dos produtos para produzir o outro. Assim, para a produção do produto tipo I a empresa 
terá disponível, no próximo mês, 80 homens-hora. Já para o produto tipo II terá 180 homens-hora. Cada unidade 
do produto tipo I, para ser produzida, utiliza 2 homens-hora enquanto cada unidade do produto tipo II utiliza 3 
homens-hora. Reduzindo do preço unitário de venda todos os custos, chega-se a conclusão de que cada unidade 
do produto tipo I dá um lucro de $20 e cada unidade do produto tipo II dá um lucro de $60. Dada a grande procura, 
estima-se que todas as unidades a serem produzidas, dos 2 produtos, poderão ser vendidas. O objetivo da 
empresa é obter o maior lucro possível com a produção e a venda das unidades dos produtos tipo I e II. 
 
 
4) Um vendedor de frutas pode transportar 800 caixas de frutas para sua região de vendas. Ele necessita 
transportar 200 caixas de laranjas a R$ 20 de lucro por caixa, pelo menos 100 caixas de pêssego a R$ 10 de lucro 
por caixa, e no máximo 200 caixas de tangerinas a R$ 30 de lucro por caixa. De que forma deverá ele carregar o 
caminhão para obter o lucro máximo? Construa o modelo do problema. 
 
 
5) Uma rede de televisão local tem o seguinte problema: foi descoberto que o programa “A” com 20 minutos de 
música e 1 minuto de propaganda chama a atenção de 30.000 telespectadores, enquanto o programa “B” com 10 
minutos de música e 1 minuto de propaganda chama a atenção de 10.000 telespectadores. No decorrer de uma 
semana, o patrocinador insiste no uso de no mínimo, 5 minutos para sua propaganda e que na há verba para mais 
de 80 minutos de música. Quantas vezes por semana cada programa deve ser levado ao ar para obter o número 
máximo de telespectadores? Construa o modelo do sistema. 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 1 4 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
6) Uma empresa fabrica 2 modelos de cinto de couro. O modelo M1, de melhor qualidade, requer o dobro do 
tempo de fabricação em relação ao modelo M2. Se todos os cintos fossem do modelo M2, a empresa poderia 
produzir 1.000 unidades por dia. A disponibilidade de couro permite fabricar 800 cintos de ambos os modelos por 
dia. Os cintos empregam fivelas diferentes, cuja disponibilidade diária é de 400 para o modelo M1 e e 700 para o 
modelo M2. Os lucros unitários são de R$ 4 para M1 e R$ 3 para M2. Qual o programa ótimo de produção que 
Maximiza o lucro total diário da empresa? Construa o modelo do sistema descrito. 
 
 
7) Um fazendeiro está estudando a divisão de sua propriedade nas seguintes atividades produtivas: 
 
▪ A (Arrendamento): Destinar certa quantidade de alqueires para a plantação de 
cana-de-açúcar, a uma usina local, que se encarrega da atividade e paga aluguel da terra $ 300,00 por 
alqueire por ano. 
▪ P (Pecuária): Usar outra parte para a criação de gado de corte. A recuperação 
das pastagens requer adubação (100 kg/Alqueire) e irrigação (100.000 litros de água/Alqueire) por ano. O 
lucro estimado nessa atividade é de $ 400,00 por alqueire no ano. 
▪ S (Plantio de Soja): Usar uma terça parte para o plantio de soja. Essa cultura 
requer 200 kg por alqueire de adubos e 200.000 litros de água/alqueire para irrigação por ano. O lucro 
estimado nessa atividade é de $ 500,00 por alqueire no ano. 
Disponibilidade de recursos por ano: 
▪ 12.750.000 litros de água 
▪ 14.000 kg de adubo 
▪ 100 alqueires de terra. 
Quantos alqueires deverá destinar a cada atividade para proporcionar o melhor retorno? Construa o modelo de 
decisão. 
 
 
8) Um fábrica de fundição deseja Maximizar sua receita na venda de suas ligas. A tabela abaixo ilustra a 
composição dos materiais produzidos, seus preços e as disponibilidades de matéria prima: 
 
 Liga Tipo A Liga Tipo B MP disponível 
Cobre 2 1 16 
Zinco 1 2 11 
Chumbo 1 3 15 
Preço Venda Unitário $ 30,00 $ 50,00 
 
Construa o modelo para solução de forma que a empresa maximize sua receita 
 
 
9) Uma rede de depósitos de material de construção tem 4 lojas que devem ser abastecidas com 50 m3 (loja 1), 80 
m3 (loja 2), 40 m3 (loja 3) e 100 m3 (loja 4) de areia grossa. Essa areia pode ser carregada em 3 portos P1, P2 e 
P3, cujas distâncias estão no quadro (em km): 
 
 L1 L2 L3 L4 
P1 30 20 24 18 
P2 12 36 30 24 
P3 8 15 25 20 
Abastecer 50m3 80m3 40m3 100m3 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 1 5 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
O caminhão pode transportar 10 m3 por viagem. Os portos têm areia para suprir qualquer demanda. Estabelecer 
um plano de transporte que minimize a distância totalpercorrida entre os pontos e as lojas e supra as 
necessidades das lojas. Construa o modelo linear do problema. 
 
10) Uma marcenaria precisa estabelecer um programa de produção diária para seus 2 produtos "mesa" e "armário" 
ambos de 1 só modelo. A empresa deve se preocupar com dois insumos principais - madeira e mão de obra - cuja 
disponibilidade segue no quadro abaixo. Para fazer uma mesa a marcenaria gasta 2m2 de madeira e 2h/homem 
de trabalho; e para fazer o armário ela gasta 3m2 de madeira e 1h/homem para realizar o trabalho. A empresa 
sabe que a mesa proporciona um lucro de $ 40 e o armário proporciona um lucro de $ 10. Encontre o programa de 
produção que Maximize o lucro total de acordo com as disponibilidades. 
 
 Mesa Armário Disponib. 
Madeira 2 3 12 
MOD 2 1 8 
Lucro $ 40 $ 10 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 1 6 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
SOLUÇÃO GRÁFICA 
 
A técnica da solução gráfica de equações lineares com "duas" variáveis é uma "reta". A representação gráfica de 
uma inequação linear com duas variáveis é um dos semiplanos definidos pela reta correspondente à equação. 
Quando o problema se restringe a "apenas duas variáveis" de decisão a solução ótima pode ser encontrada 
graficamente. Se o problema envolver mais de duas variáveis não é possível elaborar uma solução gráfica, e 
assim, devemos formular e resolver os problemas apenas algebricamente. 
 
Exemplo 1 
 
Para definir uma "única" reta segundo o Axioma5 de Incidência nº 2 de Euclides6 temos que dados dois pontos 
distintos, existe uma única reta que contêm ambos os pontos. 
 
Vamos representar graficamente a inequação 2x1 + 3x2 ≥ 6 
Para x1 = 0 temos que: 3x2 = 6  x2 = 6/3  x2 = 2 
Para x2 = 0 temos que: 2x1 = 6  x1 = 6/2  x1 = 3 
 
 X2 
 
 
 2X1 + 3X2 
 Campo de permissividade 
 (3,2) 
 2 
 
 
 (0,0) X1 
 3 
 
Exemplo 2 
 
Represente graficamente a solução do seguinte sistema 
 
 x1 + 3x2 ≤12 
2x1 + x2 ≥ 16 
 x1 ≥ 0 
 x2 ≥ 0 
Solução: 
Vamos a representação das retas correspondentes: 
 
1ª) x1 + 3x2 =12  Se x1 = 0, logo X2 = 12/3 ou x2 = 4 
 Se x2 = 0, logo x1 = 12 
 
2ª) 2x1 + x2 =16  Se x1 = 0, logo x2 = 16 
 
5 Axioma é uma premissa cuja fundamentação empírica é dispensável, ou seja, premissa considerada necessariamente 
evidente e verdadeira; é o fundamento de uma demonstração. 
6 Euclides foi um grande matemático que em 300 a.C. escreveu o livro "Os Elementos" que baseava todos os conhecimentos gregos 
e com grande contribuição para a Matemática e principalmente na geometria. 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 1 7 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 Se x2 = 0, logo x1 = 16/2 ou x1 = 8 
 
 X2 
 
 16 (8, 16) 
 
 
 
 Campo de permissividade 
 
 
 
 4 
 
 
 (0,0) 8 12 X1 
 
 
 
Exemplo 3 
 
Represente graficamente a solução do seguinte sistema 
 
Max Z = x1 + x2 
 
– x1 + 3x2 ≤ 9 
 x1 – 2x2 ≤ 1 
 2x1 + x2 ≤ 10 
 2x1 + x2 ≥ 5 
 
1ª) – x1 + 3x2 = 9  Se –x1 = 0, logo x2 = 9/3 ou x2 = 3 
 Se x2 = 0, logo x1 = – 9 
 
2ª) x1 – 2x2 = 1  Se x1 = 0, logo x2 = – 1/2 
 Se x2 = 0, logo x1 = 1 
 
3ª) 2x1 + x2 = 10  Se x1 = 0, logo x2 = 10 
 Se x2 = 0, logo x1 = 10/2 = 5 
 
4ª) 2x1 + x2 = 5  Se x1 = 0, logo x2 = 5 
 Se x2 = 0, logo x1 = 5/2 = 2,5 
 
 
 
 
 
 
 
 
 
1ª 
2ª 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 1 8 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
 
Solução Gráfica 
 
 X2 
 10 
 
 
 
 Campo de permissividade 
 
 
 
 5 
 4 
 
 3 
 
 
 
 - 9 (0,0) 
 
 1 2,5 5 X1 
 - 1/2 3 
 
 
Solução Ótima 
 
Conforme alegado anteriormente se um problema apresenta apenas duas variáveis de decisão a solução ótima de 
um problema de programação linear pode ser encontrada graficamente. A solução ótima é encontra de forma 
simples, atribuindo-se valores a Z, tornando a função objetivo uma equação de uma reta. Se considerarmos x1 
como variável independente e x2 como variável dependente (pois é função de x1) a equação da reta é dada por: 
X2 = aX1 + b, onde a é o coeficiente angular da reta e b é o coeficiente linear. 
 
Exemplo 4 
 
Imagine o seguinte problema de programação linear: (Lachtermacher, p.28) 
 
Max Z = 5x1 + 2x2 
 
Sujeito a: 
 
x1 ≤ 3 
x2 ≤ 4 
x1 + 2x2 ≤ 9 
x1 ≥ 0 e x2 ≥ 0 
 
x1 + 2x2 ≤ 9  Se x1 = 0, logo x2 = 9/2 ou x2 ≤ 4,5 
 Se x2 = 0, logo x1 ≤ 9 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 1 9 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
 
Solução Gráfica 
 
 X2 
 x1 ≤ 3 
 5 
 4,5 D (1,4) 
E (0,4) x2 ≤ 4 
 
 C (3,3) 
 
 
 
 x1 + 2x2 ≤ 9 
 
 
x2 ≥ 0 
 
 
A (0,0) 2 B (3,0) 9 X1 
 x1 ≥ 0 21 = 5x1 + 2x2 
 
 
 20 = 5x1 + 2x2 
 10 = 5x1 + 2x2 
 
 
Por um processo de tteennttaattiivvaa ee eerrrroo, podemos chegar ao valor ótimo de Z verificando a existência e pontos da reta 
que fazem parte do conjunto de soluções viáveis. No caso de maximização, aaoo eennccoonnttrraarrmmooss oo MMAAIIOORR vvaalloorr ddee ZZ 
possível, eessttaarreemmooss eennccoonnttrraannddoo oo vvaalloorr mmááxxiimmoo ppaarraa aa ffuunnççããoo oobbjjeettiivvoo. 
Escolheremos um valor arbitrário para Z, por exemplo 10. 
 
Z = 10  10 = 5x1 + 2x2 Se x1 = 0, logo x2 = 5 
 Se x2 = 0, logo x1 ≤ 2 
 
Z = 20  20 = 5x1 + 2x2 Se x1 = 0, logo x2 = 10 
 Se x2 = 0, logo x1 ≤ 4 
 
Z = 21  21 = 5x1 + 2x2 (x1 = 3) e (x2 = 3)  (5.3) + (2.3) = 21 
 
 
Solução 
Viável 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL2 0 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
TEOREMAS - PROGRAMAÇÃO LINEAR 
 
Ao longo da aprendizagem da pesquisa operacional, conceitos matemáticos como matrizes e vetores são 
largamente utilizados. Os conceitos aqui discutidos têm como objetivo apresentar uma revisão desses 
fundamentos matemáticos, de modo que o curso possa ser compreendido. 
 
A área marcada como sendo uma região de permissividade indica que o conjunto de soluções possíveis estão 
contidos nesta situação, ou seja, ali encontram-se o "conjunto de soluções" que satisfaz as restrições. Esta região 
pode ser convexa ou não convexa. 
 
 
 
 Conjunto Convexo Conjunto Não-convexo 
 
O conjunto convexo é um conjunto de pontos em que todos os segmentos de reta que unem dois de seus pontos 
são internos ao conjunto, ou seja, todos os pontos de cada segmento de reta também pertencem ao conjunto 
original. Se pelo menos "uma" união de dois pontos não pertencerem ao conjunto ele é considerado não-convexo. 
 
 
 
 
 
 
 
 
 Polígono convexo limitado Polígono convexo limitado 
 
 
Obviamente que essa visualização é possível com duas variáveis. Se considerarmos a equação: 
 
a1x1 + a2x2 + a3x3 + ..... + anxn = b → Estamos nos referindo a sseemmii--eessppaaççooss. 
 
Uma solução como esta divide o espaço Rn de dimensão n em um hhiippeerrppllaannoo. Os semi-espaços são sempre 
convexos, ou seja, o segmento de reta que une os pontos de um semi-espaço pertencem inteiramente ao mesmo 
semi-espaço. 
 z 
 Poliedro Convexo 
 
 
 
 
 y 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 2 1 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
 x 
Teorema 1 
O conjunto de todas as soluções viáveis de um modelo de P.L. é um conjunto convexo. 
 
Teorema 2 
Toda solução compatível básica (solução óbvia) do sistema de equações lineares de um modelo de P.L. é um 
ponto extremo do conjunto de soluções viáveis, isto é, do conjunto convexo de soluções. 
 
Teorema 3 
Se uma função objetivo possui um único ponto ótimo finito, então este é um ponto extremo do conjunto convexo de 
soluções viáveis. 
 
Teorema 4 
Se a função objetivo assume o valor ótimo em mais de um ponto do conjunto de soluções viáveis (soluções 
múltiplas), então ela assume este valor para pelo menos dois pontos extremos, isto é, todos os pontos do 
segmento de reta unem estes dois extremos, ou seja, a aresta do polígono que contêm estes extremos. 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 2 2 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
Exercícios: Resolver graficamente o modelo de programação linear: 
 
1) (Max) Z = 3x1 + 5x2 
 
Sujeito a: 
x1 ≤ 4 
2x2 ≤ 12 
3x1 + 2x2 ≤ 18 
x1 ≥ 0 
x2 ≥ 0 
 
 
2) (Max) Z = 2x1 + x2 
 
Sujeito a: 
x2 ≤ 10 
2x1 + 5x2 ≤ 60 
x1 + x2 ≤ 18 
3x1 + x2 ≤ 44 
x1 ≥ 0 
x2 ≥ 0 
 
 
3) (Max) Z = −2x1 − 2x2 
 
Sujeito a: 
3x1 − 4x2 ≤ 18 
8x1 − 3x2 ≤ −24 
6x1 + 8x2 ≤ 24 
3x1 + 5x2 ≤ 21 
x1 ≤ 3 
x2 ≥ 0 
 
4) (Max) Z = −2x1 − 8x2 
 
Sujeito a: 
4x1 + 2x2 ≥ −8 
−3x1 + 6x2 ≥ −6 
−6x1 + 6x2 ≤ 18 
x2 ≥ −2 
x1 ≤ 2 
5x1 + 3x2 ≥ 15 
x1 ≥ 0 
 
 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 2 3 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
5) (Max) Z = −4x1 − 2x2 
 
Sujeito a: 
x1 + x2 ≤ 8 
8x1 + 3x2 ≥ −24 
−6x1 + 8x2 ≤ 48 
3x1 + 5x2 ≥ 15 
x1 ≤ 4 
x2 ≥ 0 
 
 
6) (Max) Z = −2x1 − 5x2 
 
Sujeito a: 
2x1 − 2x2 ≤ 10 
7x1 + 3x2 ≥ −21 
−2x1 + 3x2 ≥ −6 
3x1 + 9x2 ≤ 27 
x1 ≥ −1 
x2 ≥ −4 
 
 
7) (Min) Z = −4x1 − 2x2 
 
Sujeito.a: 
x1 + x2 ≤ 8 
8x1 + 3x2 ≥ −24 
−6x1 + 8x2 ≤ 48 
3x1 + 5x2 ≤ 15 
x1 ≤ 3 
x2 ≥ 0 
 
 
8) Max L = 2x1 + 3x2 
 
Sujeito a: 
–x1 + 2x2 ≤ 4 
 x1 + 2x2 ≤ 6 
 x1 + 3x2 ≤ 9 
 
 x1 ≥ 0 
 x2 ≥ 0 
 
 
 
 
 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 2 4 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
 
 
9) Min Z = 8x1 + 11x2 
 
Sujeito a: 
12x1 + 5x2 ≥ 60 
 x1 + x2 ≥ 10 
 x1 + x2 ≥ 12 
 
 
x1 ≥ 0 
x2 ≥ 0 
 
 
 
10) Min Z = 3x1 + 4x2 
 
Sujeito a: 
x1 + 2x2 ≤ 8 
 x1 – x2 ≤ 3 
x1 ≥ 1 
x2 ≥ 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 2 5 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
REVISÃO: MATRIZES 
 
Uma matriz pode ser definida como uma tabela com linhas e colunas usadas principalmente na resolução de 
sistemas de equações lineares e transformações lineares. As linhas são indicadas pela letra “m” e as colunas pela 
letra “n”, o que permite que a matriz seja representada pela forma m x n. Em álgebra linear podemos chamar 
matriz de um conjunto de vetores colocados lado a lado. 
 
Matriz m por n 
 
 aij = Colunas = j 
 
 a1,1 a1,2 a1,3 ... a1n 
 Linhas = i a2,1 a2,2 a2,3 ... a2n 
 
 
 am,1 am,2 am,3 ... amn 
 
 
 
Ao trabalhar matrizes é importante ter conhecimento das linhas horizontais (linhas) e verticais (colunas) e 
dominar a identificação dos mesmos. Observe que a matriz onde aparecem a11, a12, …. é o que chamamos de 
Matriz Genérica. Ela indica o conjunto, as linhas e colunas como aij onde a representa o conjunto, i o número da 
linha e j o da coluna. 
 
Para encontrar os valores de uma matriz é preciso ter a Regra de Formação e a Ordem. De posse da ordem é 
possível elaborar a matriz genérica e através da regra de formaçãoatribuir valores a cada um dos espaços. 
Observe os exemplos. 
 
Seja A2x2 onde aij = 2i + j 
 
  A= A= 
 
 
aij = 2i + j a1,1= 2(1)+1= 3 
 a1,2= 2(1)+2= 4 
 a2,1= 2(2)+1= 5 
 a2,2= 2(2)+2= 6 
 
 
Seja b2x2 onde aij = i – j2 
 
  B= B= 
 
 
bij = i + j2 b1,1= (1) – 12= 0 
 b1,2= (1) – 22= –3 
 b2,1= (2) – 12= 1 
 b2,2= (2) – 22= –2 
a1,1 a1,2 
a2,1 a2,2 
3 4 
5 6 
a1,1 a1,2 
a2,1 a2,2 
0 –3 
1 –2 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 2 6 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
 
TIPOS DE MATRIZES 
 
Matriz Quadrada: É uma matriz onde o número de linhas (m) é igual ao número de colunas (n). 
 
Matriz Identidade: É uma matriz quadrada na qual: (A) todos os elementos na diagonal principal são iguais a "1"; 
(B) todos os elementos fora da diagonal principal são iguais a "0". Exemplo: 
 
 1 0 0 
A= 0 1 0 
 0 0 1 
 
Matriz Transposta: AT ou A' é considerada transposta se o elemento aij de A for o elemento aji da Transposta AT; 
para todo o elemento "i" e "j". Exemplo 
 
 
 1 3 6 1 2 7 
 A= 2 5 -8 AT 3 5 -3 
 7 -3 0 6 -8 0 
 
 
Matriz Nula: Uma matriz é considerada nula quanto TODOS os elementos aij = 0 
 
Matrizes Iguais: Duas matrizes aij e bij serão iguais exclusivamente se: (1) A e B forem matrizes da mesma ordem 
(m x n) e (2) se todos os elementos de "A" forem obrigatoriamente iguais aos correspondentes de "B". Exemplo 
 
 2 x1 x1= 2 
 A = 3 X= x2  x2= 3 
 1 x3 x3= 1 
 
 
DETERMINANTE DE UMA MATRIZES 
 
O determinante de uma matriz é dado pelo valor numérico resultante da subtração do produto dos termos da 
diagonal principal ao somatório do produto dos termos da diagonal secundária. Para uma matriz de ordem 3 
podemos utilizar a regra de Sarrus7. 
 15 -4 0 
 - 4 
 2 -1 1 0 -3 1 0 -3 1 0 
A= B = 4 5 2 4 5 2 4 5 
 4 -5 -1 -2 0 -1 -2 0 1 -2 
 - 10 
 0 0 24 
Det. (A)= - 10 - (- 4) = D= - 6 Det. (B)= 24 – (15) + (- 4) = 
 24 – 15 + 4 = 13 
 
7 Pierre Frédéric Sarrus (1789-1861) foi responsável pela regra prática de resolução de determinantes de ordem 3. Essa regra diz 
que para encontrar o valor numérico de um determinante de ordem 3, basta repetir as duas primeiras colunas à direita do 
determinante e multiplicar os elementos do determinante. Disponível em: < http://www.mat.ufmg.br/~elaine/GAAL/matriz.pdf >. 
Acesso em 02/02/2013. 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 2 7 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
 
SISTEMAS LINEARES 
 
É um conjunto de m equações lineares de n incógnitas (x1, x2, x3, ... , xn) do tipo: 
 
a11x1 + a12x2 + a13x3 + ... + a1nxn = b1 
a21x1 + a22x2 + a23x3 + ... + a2nxn = b2 
a31x1 + a32x2 + a33x3 + ... + a3nxn = b3 
 
OBS 1: Dois sistemas lineares são EQUIVALENTES quando possuem as mesmas soluções. 
Exemplo: Os sistemas lineares são equivalentes, pois ambos admitem o par ordenado (3, 2) como solução. 
 
 2x + 3y = 12 5x - 2y = 11 
 S1 = e S2 = 
 3x - 2y = 5 6x + y = 20 
 
 
 
 
OBS 2: Se um sistema de equações possuir pelo mmeennooss uummaa ssoolluuççããoo, dizemos que ele é possível ou 
compatível. 
 
OBS 3: Se um sistema de equações nnããoo ppoossssuuiirr ssoolluuççããoo, dizemos que ele é impossível ou incompatível. 
 
OBS 4: Se o sistema de equações é compatível e possui aappeennaass uummaa ssoolluuççããoo, dizemos que ele é 
determinado. 
 
OBS 5: Se o sistema de equações é compatível e possui mmaaiiss ddee uummaa ssoolluuççããoo, dizemos que ele é 
indeterminado. 
 
OBS 6: Se os termos independentes de todas as equações de um sistema linear forem todos nulos, ou seja 
b1 = b2 = b3 = ... = bn = 0, dizemos que temos um sistema linear HOMOGÊNEO. 
 
Exemplo: 
 
 x + y + 2z = 0 
 S1= 2x - 3y + 5z = 0 
 5x - 2y + z = 0 
 
 
Quando os sistemas se apresentam de forma de uma matriz quadrada podemos utilizar a regra de Gabriel 
CCrraammeerr para sua solução. Veja que temos o sinal de igualdade no final de cada linha o que é diferente da P.O. 
Ao utilizar a regra de Cramer temos que estar atentos pois ela só é válida para sistemas em que o número de 
incógnitas é igual ao número de equações. Não é um método indicado para isso, pois imagine se tivermos um 
sistema de (20 x 20) seria um tédio a solução. 
 
Exemplo: Solucione o Sistema abaixo: 
 
 2x1 – 2x2 + 4x3 = 6 
 A= -3x1 + 2x2 + x3 = 1 
 x1 + 2x2 – 3x3 = 5 
http://www.paulomarques.com.br/arq12-3.htm
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 2 8 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
 
 8 4 -18 
 2 -2 4 2 -2 4 2 -2 
DA = -3 2 1 -3 2 1 -3 2 
 1 2 -3 1 2 -3 1 2 
 
 -12 -2 -24 
Det. (A)= (-12) +(-2) + (-24) – (8) + (4) + (-18)  -12 - 2 - 24 - 8 - 4 + 18 = Det. (A)= – 32 
 
 
 40 12 6 
 6 -2 4 6 -2 4 6 -2 
Dx1 = 1 2 1 1 2 1 1 2 
 5 2 -3 5 2 -3 5 2 
 
 -36 -10 8 
Det. (x1)= (- 36 - 10 + 8) – (40 + 12 + 6)  - 38 - 58 = Det. (x1)= – 96 
 
 
 4 10 54 
 2 6 4 2 6 4 2 6 
Dx2 = -3 1 1 -3 1 1 -3 1 
 1 5 -3 1 5 -3 1 5 
 
 -6 6 -60 
Det. (x2)= (-6 + 6 - 60) – (4 + 10 + 54)  - 60 - 68 = Det. (x2)= – 128 
 
 
 12 4 30 
 2 -2 6 2 -2 6 2 -2 
Dx3 = -3 2 1 -3 2 1 -3 2 
 1 2 5 1 2 5 1 2 
 
 20 -2 -36 
Det. (x3)= (20 - 2 - 36) – (12 + 4 + 30)  - 18 - 46 = Det. (x3)= – 64 
 
 
Determinando valores: 
 Dx1 
x1 =  x1 = (- 96 ÷ - 32)  x1 = 3 
 DA 
 
 
 Dx2 
x2 =  x2 = (- 128 ÷ - 32)  x2 = 4 
 DA 
 
 
 Dx3 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 2 9 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MMss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
x1 =  x1 = (- 64 ÷ - 32)  x1 = 2 
 DA 
ALGORITMO DE GAUSS JORDAN 
 
O algoritmo de Gauss-Jordan corresponde a sistematização da sequência de ações que permite reduzir uma 
matriz a forma escalonada reduzida. O Método de Gauss-Jordan é a parte principal de um procedimento para a 
resolução de sistemas de equações lineares. Seu objetivo é o de escalonar uma matriz para obter a sua forma 
escalonada reduzida por linhas. Por meio de operações elementares com matrizes aplica-se os passos 
repetidamente até que ele seja reduzido a uma forma elementar da matriz identidade. 
 
As operações elementares sobre as linhas de uma matriz compreendem: 
▪ L1. Troca entre si de duas linhas da matriz: Li ↔ Lk 
▪ L2. Multiplicação ou divisão de uma linha da matriz por um escalar não nulo: α Li → Li 
▪ L3. Substituição de uma linha pela sua soma com um múltiplo escalar de outra linha: Li + α. Lk → Li 
 
A determinação da matriz escalonada reduzida é relevante explicitamente para a resolução de sistemas de 
equações e inversão de matrizes, e está implicitamente na base de praticamente todos os algoritmos que 
envolvem processamento matricial. 
 
Definição: Uma matriz está na forma escalonada reduzida quando ela satisfaz as seguintes condições: 
 
▪ O primeiro elemento não-nulo de cada linha não-nula (chamado o pivô da linha) é igual a 1. 
▪ O pivô da linha i + 1 ocorre à direita do pivô da linha i. 
▪ Se uma coluna contém um pivô, então todas os outros elementos desta coluna são iguais a 0. 
▪ Todas as linhas nulas ocorrem abaixo das linhas não-nulas. 
 
 
PROCESSO ELIMINAÇÃO DE GAUSS-JORDAN: 
 
Passo 1: Dividir a linha do elemento que chamamos de pivô, cujo coeficiente se deseja unitário, pelo valor de seu 
coeficiente. 
 
Passo 2: Adicionar múltiplos adequados e apropriados a esta nova linha de modo seja possivel anular os 
coeficientes correspondentes (os outros elementos da coluna) em todas as outras linhas. 
 
Passo 3: Repita os passos 1 e 2 a todos os elementos da diagonal principal tomadas sucessivamente com os 
pivôs. 
 
Exemplo: Transformar a matriz abaixo em sua forma reduzida por linhas. 
Seja: 
 2x1 – 2x2 + 4x3 = 6 
 – 3x1 + 2x2 + x3 = 1 
 x1 + 2x2 – 3x3 = 5 
 
x1 x2 x3 b 
2 - 2 4 6 
- 3 2 1 1 
1 2 - 3 5 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 3 0 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
(A) Dividir a primeira linha por (2) transformando-a em pivô. 
 
x1 x2 x3 b 
1 - 1 2 3 
- 3 2 1 1 
1 2 - 3 5 
 
(B) Zerar coluna de x1: 
 
1ª Operação: Multiplicar a 1ª linha por (3) e somar com a 2ª linha. 
 
x1 x2 x3 b 
1 - 1 2 3 
0 -1 7 10 
1 2 - 3 5 
 
2ª Operação: Multiplicar a 1ª linha por (- 1) e somar com a 3ª linha. 
 
x1 x2 x3 b 
1 - 1 2 3 
0 -1 7 10 
0 3 - 5 2 
 
(C) Transformar elemento da 2ª linha de x2 em pivô, dividindo a 2ª linha por (- 1). 
 
x1 x2 x3 b 
1 - 1 2 3 
0 1 - 7 - 10 
0 3 - 5 2 
 
(D) Zerar coluna de x2 abaixo do pivô. 
 
1ª Operação: Multiplicar a 2ª linha por (- 3) e somar com a 3ª linha 
 
x1 x2 x3 b 
1 - 1 2 3 
0 1 - 7 - 10 
0 0 16 32 
 
(E) Transformar elemento da 3ª linha de x3 em pivô, dividindo a 3ª linha por (16). 
 
x1 x2 x3 b 
1 - 1 2 3 
0 1 - 7 - 10 
0 0 1 2 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 3 1 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
(F) Com o final das linhas já zeradas, devemos agora "zerar" os elementos acima dos pivôs, 
1ª Operação: Multiplicar a 3ª linha por (7) e somar com a 2ª linha. 
 
x1 x2 x3 b 
1 - 1 2 3 
0 1 0 4 
0 0 1 2 
 
2ª Operação: Multiplicar a 2ª linha por (-2 ) e somar com a 1ª linha. 
 
x1 x2 x3 b 
1 - 1 0 - 1 
0 1 0 4 
0 0 1 2 
 
(G) Transformar elemento da 2ª linha de x2 em pivô, zerando o elemento acima dele 
 
1ª Operação: Somar a 2ª linha com a 2ª linha. 
 
x1 x2 x3 b 
1 0 0 3 
0 1 0 4 
0 0 1 2 
 
Neta situação concluímos que a solução do sistema é: (x1 = 3); (x2 = 4) e (x3 = 2) 
 
 
Exercícios: Resolva por escalonamento 
 
Uma empresa de transportes tem três tipos de caminhão I, II, e III, que carregam cargas com três tipos de 
embalagens A, B e C também diferentes. O número de embalagens por caminhão é dado pelo quadro: 
 
Embalagem A B C 
Caminhão I 2 2 2 
Caminhão II 4 3 4 
Caminhão III 4 2 3 
 
Quantos Caminhões de cada tipo I, II e III, são necessários se a empresa necessita transportar 38 embalagens 
do tipo A, 24 do tipo B e 32 do tipo C? (x1= 2; x2 = 6; x3 = 3) 
 
Modelagem: 
x1 → quantidade de Caminhões I 
x2 → quantidade de Caminhões II 
x3 → quantidade de Caminhões III 
 
 2x1 + 4x2 + 4x3 = 38 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 3 2 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
S1 = 2x1 + 3x2 + 2x3 = 24 
 2x1 + 4x2 + 3x3 = 32 
 x1 – 2x2 + 3x3 = 0 
S2= – 2x1 + 5x2 – 3x3 = 1 
 – x1 + 3x2 – 2x3 = 5 
 
 
 
 – 2x1 + 4x2 – 2x3 = 2 
S3= 3x1 – 5x2 + x3 = – 7 
 2x1 – 5x3 = – 16 
 
 
 x1 – 2x2 + x3 = – 4 
S4= 2x1 + x2 – x3 = – 1 
 – x1 + 3x2 – 4x3 = 3 
 
 
 3x1 – x2 – x3 = 1 
S5= x1 + x3 = – 2 
 – 2x1 + x2 – x3 = 3 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 3 3 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
 
METODO SIMPLEX 
 
O Método Simplex é uma técnica utilizada para se determinar, numericamente, a solução ótima de um modelo de 
Programação O Método Simplex procura nos vértices da região de permissividade até encontrar uma solução 
ótima. A solução ótima pode não existir em dois casos: (1) quando não há nenhuma solução viável para o 
problema, devido a restrições incompatíveis; ou (2) quando não há máximo (ou mínimo), isto é, uma ou mais 
variáveis podem tender a infinito e as restrições continuarem sendo satisfeitas, o que fornece um valor sem limites 
para a função objetivo. 
 
 
VARIÁVEIS DE FOLGA 
 
É possível resolver osproblemas de Programação Linear por algum método de solução de sistemas de equações. 
Para tanto alguns métodos exigem que as desigualdades lineares das restrições sejam transformadas em 
equações lineares de modo que tais métodos possam ser aplicados. No problema da P.O. normalmente a 
disponibilidade está em descompasso com os recursos, fator esse que elege as restrições. Para Andrade (1998, p. 
39) as restrições apresentam a seguinte lógica: 
 
Utilização de recurso ≤ Disponibilidade 
 
Ao se introduzir o conceito de FOLGA de recurso é possível concluir que: 
 
Utilização + Folga = Disponibilidade 
 
Considerando a hipótese anterior temos que: 
Utilização  Disponibilidade  Folga  0 
Utilização = Disponibilidade  Folga = 0 
 
A folga de cada recurso pode ser representada por uma variável de forma exatamente igual à produção de cada 
produto, ou seja, para cada desigualdade. Para ser submetido ao método Simplex, o modelo não pode ter 
nenhuma das suas restrições com sinais de "≤" ou "≥", ssoommeennttee ssiinnaaiiss ddee iigguuaallddaaddee. Como na realidade isso é 
praticamente impossível devido a natureza dos problemas, algumas estratégias são adotadas. Desta forma, para 
que um modelo possa ser normalizado, são adicionados ao modelo algumas variáveis que auxiliam este processo. 
 
Variáveis de Folga: Para restrições com sinal de ≤, adiciona-se uma variável que será conhecida como variável 
de folga. Nas funções de restrições, esta variável é inserida com o coeficiente +1. Um detalhe que merece 
atenção, é que esta variável também deve ser inserida na função objetivo com o coeficiente 0; 
 
Variáveis de Excesso: Para restrições com sinal de ≥ adiciona-se uma variável que será conhecida como variável 
de excesso. Nas funções de restrições, esta variável é inserida com o coeficiente -1. Essa variável também deve 
ser inserida na função objetivo com o coeficiente 0; 
 
Variáveis de Artificiais: Após a análise da necessidade de variáveis de Folga ou de Excesso, adiciona-se a todas 
as restrições que não receberam variáveis de folga uma variável que será conhecida como variável artificial. Nas 
funções de restrições, esta variável é inserida com o coeficiente +1, já na função objetivo ela é inserida com o 
coeficiente M (+M para problemas de minimização e – M para problemas de maximização). 
 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 3 4 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
 
ROTEIRO DO MÉTODO SIMPLEX 
 
1) Introduzir as variáveis de folga, uma para cada desigualdade. 
 
2) Montar um quadro para os cálculos, colocando os coeficientes de TODAS as variáveis com os respectivos 
sinais e, na última linha incluir os coeficientes da função objetivo. 
 
3) Estabelecer uma solução básica inicial, usualmente atribuindo o valor "zero" as variáveis originais e achando 
valores positivos para as variáveis de folga. 
 
4) Como próxima variável a entrar base; escolher a variável não-básica que fornece na última linha, a maior 
contribuição para a função objetivo (ou seja, tem o maior valor negativo). 
 
▪ Se TODAS as variáveis que estão fora da base tiverem coeficientes nulos ou positivos nesta linha, a 
solução atual é ótima. 
▪ Se ALGUMAS destas variáveis tiverem coeficientes nulo, isto significa que ela pode ser introduzida na 
base sem aumentar o valor da função objetivo. Isso quer dizer que temos outra solução ótima, com o 
mesmo valor da função objetivo. 
 
5) Para escolher a variável que deve sair da base, deve-se realizar o seguinte procedimento: 
 
▪ Dividir os elementos da última coluna pelos correspondentes elementos positivos da coluna da variável 
que vai entrar na base. Caso não haja elemento algum positivo nessa coluna, o procedimento deve 
parar, já que a solução seria ilimitada. 
▪ O menor quociente indica a equação cuja respectiva variável básica deverá ser anulada, tornando-se 
variável não-básica. 
 
6) Usando operações validas com linhas da matriz, transforma o quadro de cálculos de forma a encontrar a 
nova solução básica. A coluna da nova variável básica deverá se tornar um vetor identidade, onde o elemento 1 
aparece na linha correspondente à variável que está sendo anulada. 
 
7) Retornar ao passo 4 para iniciar outra iteração. 
 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 3 5 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
Exemplo: 
 
Resolver utilizando o algoritmo Simplex. 
 
Max Z= 3x1 + 5x2 
 
Sujeito a: 
x1 ≤ 4 
x2 ≤ 16 
3x1 + 2x2 ≤ 18 
 
Passo 1: Inserir as variáveis de folga Variáveis de folga = "0" para não alterar "Z". 
 
 Z= 3x1 + 5x2 + 0x3 + 0x4 + 0x5 Transformou em igualdade 
 
 x1 + + 1x3 = 4 
 x2 + + 1x4 = 6 
 3x1 + 2x2 + + 1x5 = 18 
 Elemento neutro 
Passo 2: Montagem do quadro de cálculos, transformando Z = - Z (ver variáveis artificiais) 
 
Quadro 1 
Base x1 x2 x3 x4 x5 b 
x3 1 0 1 0 0 4 
x4 0 1 0 1 0 6 
x5 3 2 0 0 1 18 
Z - 3 - 5 0 0 0 0 
 
Passo 3: Estabelecer solução básica viável inicial 
 
 Variáveis não-básicas: x1 = x2 = 0 
 Variáveis básicas: 
 1ª linha: x3 = 4 
 2ª linha: x4 = 6 
 3ª linha: x5 = 18 
 Função Objetivo Z= 0 
 
 
Passo 4: Variável que deve entrar na base: 
 
Identificar o maior valor na última linha neste caso = (5) coeficiente de x2 na função objetivo, portanto; x2 deve 
entrar na base, pois fornece maior contribuição por unidade. 
 
 
Passo 5: Variável que deve sair da base: 
 
Fazer as divisões da coluna b pela coluna de x2 que entrou na base no passo anterior. 
PP EE SS QQ UU II SS AA OO PP EE RR AA CC II OO NN AA LL 3 6 
 
PP rr oo ff .. DD rr .. AA ll mm ii rr VV oo ll pp ii AA dd aa pp tt aa çç ãã oo PP rr oo ff .. MM ss .. CC aa rr ll oo ss AA ll bb ee rr tt oo SS oo uu zz aa CC aa bb ee ll ll oo 
 
 Divisões: 
 1ª linha: Não se efetua divisão o valor do coeficiente de x2 nessa linha é "0". 
 2ª linha: 6 ÷ 1 = 6 
 3ª linha: 18 ÷ 2 = 9 
 
Como o menor valor ocorreu na 2ª linha, a variável que deve sair da base é x4 . 
 
 
Base x1 x2 x3 x4 x5 b 
x3 1 0 1 0 0 4 
x4 0 1 0 1 0 6 
x5 3 2 0 0 1 18 
Z - 3 - 5 0 0 0 0 
 
Passo 6: Transformação da Matriz. 
 
Deverão ser realizadas operações com as linhas da matriz de forma que a coluna de x2 venha a se tornar um vetor 
identidade, com o elemento 1 na 2ª linha e os demais e coeficientes = 0. 
1ª Operação: Substituir a 3ª linha pela soma da 2ª linha multiplicada por (- 2). 
 
 
 
 
 ( - 2) 
 e soma 
 
 
 
Quadro 1A. 
 
 
 
 
 
 
 
 
2ª Operação: Substituir a 4ª linha do quadro 1A por sua soma com a 2ª linha multiplicada por 5. 
 
Quadro 2.