kupdf net_apostila-pesquisa-operacional

Prévia do material em texto

UNIVERSIDADE FEDERAL DE CAMPINA GRANDEUNIVERSIDADE FEDERAL DE CAMPINA GRANDE
UNIDADE ACADÊMICA DE MATEMÁTICA E ESTATÍSTICAUNIDADE ACADÊMICA DE MATEMÁTICA E ESTATÍSTICA
ApostilaApostila11
dede
Introdução à Pesquisa OperacionalIntrodução à Pesquisa Operacional
Prof. Dr. Gilberto S. MatosProf. Dr. Gilberto S. Matos
((http://sites.google.com/site/gilbertosmatos1http://sites.google.com/site/gilbertosmatos1))
Campina Grande - PBCampina Grande - PB
- Novembro / 2012 -- Novembro / 2012 -
11Esta apostila vem sendo desenvEsta apostila vem sendo desenvolvida desde de 2008.1 quando o olvida desde de 2008.1 quando o Prof. Prof. Gilberto S. Matos iniciouGilberto S. Matos iniciou
sua experiência em ministrar esta disciplina, desde então o mesmo está sempre em busca da melhoriasua experiência em ministrar esta disciplina, desde então o mesmo está sempre em busca da melhoria
deste deste materimaterial al didátididático.co.
22
SumárioSumário
1 1 AprApreseesentntaçaçãoão 55
1.1.1 1 EmEmenentata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.1.2 2 ObjeObjetitivvosos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.3 1.3 ConConteúteúdo do ProProgragramátmáticoico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
1.1.4 4 MéMétodtodo o de de EnEnsisinono . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
1.5 1.5 AAvvaliações aliações e Horáe Horários drios de Ae Atenditendimenmentoto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
1.51.5.1 .1 DatData daa das Ps Prorovvas e as e ConConteúteúdodo  .   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
1.51.5.2 .2 HorHoráriários os de de AtAtendendimeimentntoo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
1.1.6 6 BiBiblblioiogrgrafiaafia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
2 2 IntIntroducao roducao à Pà Pesquiesquisa Osa Operacioperacionalnal 99
2.1 2.1 ObjetObjetivivos os do do CapíCapítultuloo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
2.2 2.2 PePesqusquisa Opeisa Operacracionional: al: o que é, quo que é, quando e coando e como surmo surgiugiu?? . . . . . . . . . . . . . . . . . . 99
2.22.2.1 .1 O qO que ue é Pé Pesqesquisuisa Opea Operacracionaional?l? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
2.22.2.2 .2 QuaQuando e condo e como surmo surgiu a Pgiu a Pesqesquisuisa Operaa Operaciocionalnal?? . . . . . . . . . . . . . . . . . . 1100
2.22.2.3 .3 CieCientntististas.as..... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1100
2.3 2.3 Um pouUm pouco da co da TTeoreoria daia das Des Deciscisõesões   . . . .   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1100
2.2.3.3.1 1 DeDefinfiniçiçãoão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1100
2.3.2 2.3.2 CaracCaracteríterísticasticas s do do ProcesProcesso so de de DeciDecisãosão . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1100
2.32.3.3 .3 ClaClassissificaficação ção das das DecDecisõeisõess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1111
2.3.4 2.3.4 AlgumAlgumas téas técnicacnicas segs segundo o undo o grau dgrau de ese estrututruturação ração da decda decisãoisão . . . . 1122
2.32.3.5 .5 SobSobre re DecDecisãisão o RacRacionaionall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1133
2.4 2.4 A NatA Natureureza da Pza da Pesqesquisuisa Opera Operaciacionalonal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1144
2.5 2.5 FFases dases de um e um EstudEstudo de o de PePesquisa squisa OperaciOperacionalonal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1144
2.6 2.6 1a. Li1a. Lista sta de de ExeExercírcíciocioss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1177
33
44   SUMÁRIO   SUMÁRIO 
3 3 ProProgragramaçmação ão LinLinearear 1919
3.3.1 1 InIntrtroduoduçãçãoo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1199
3.2 3.2 ProblProblemas de emas de ProgrProgramação Lamação Linear (inear (PPL) PPL) e Modelage Modelagem Matem Matemátiemáticaca . . . . 1199
3.2.1 3.2.1 FFormormulação ulação MatemMatemáticática a do do PPLPPL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2200
3.23.2.2 .2 ExeExercírcíciocios s de de FixFixaçãaçãoo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2211
3.3 3.3 SoluçãSolução Gráfico Gráfica de um a de um ProblProblema de ema de ProgrProgramação Lamação Linear inear (PPL(PPL))   .   . . . . . . . 2244
3.3.3.3.1 1 InIntrtroduçoduçãoão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2244
3.3.3.3.2 2 ExExememplploo   . . . .   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2244
3.33.3.3 .3 ExeExercírcíciocios s de de FixFixaçãaçãoo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2288
3.33.3.4 .4 TipoTipos de Solus de Solução de um Pção de um PPL IlPL Ilustustradrados por Resos por Resoluolução Grção Gráficáficaa . . 2929
3.4 3.4 DifDifereerentntes Fes Formormas de uas de um PPm PPLL   . . .   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3311
3.3.4.4.1 1 InIntrtroduçoduçãoão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3311
3.4.2 3.4.2 TTransforransformação mação de PPde PPL’s pL’s para a ara a FForma Porma Padrãoadrão . . . . . . . . . . . . . . . . . . . . 3333
3.43.4.3 .3 ExeExercírcíciocios s de de FixFixaçãaçãoo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 3344
3.5 3.5 SolSoluçõeuções Básis Básicas de um Siscas de um Sistemtema de Equaça de Equações Lineões Linearearess mm×× n,n,mm ≤ ≤ nn e e
a Resolução de um PPL Utilizando Soluções Básicasa Resolução de um PPL Utilizando Soluções Básicas . . . . . . . . . . . . . . . . . . . . . . 3355
3.3.5.5.1 1 InIntrtroduçoduçãoão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3355
3.53.5.2 .2 SolSoluçãução Gerao Geral e Soluçl e Solução Básião Básica de um Sistca de um Sistema de Eqema de Equaçuações Li-ões Li-
nearesneares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3366
3.53.5.3 .3 AplAplicaicação doção dos Ress Resultultadosados: : Um méUm método de Stodo de Soluolução de Pção de PPLPL   .   . . . . . 3377
3.3.6 6 O O MéMétodtodo o SiSimplmplexex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3388
3.63.6.1 .1 PrPrincincípiípios os BásBásicoicoss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3388
3.63.6.2 .2 IdéIdéia Ria Resuesumidmida soba sobre o re o MétMétodo Siodo Simplmplexex . . . . . . . . . . . . . . . . . . . . . . . . . . 4422
3.6.3 3.6.3 Método Método SimplSimplex ex em em TTabelas abelas (T(Tabularabular)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4422
3.3.6.6.4 4 ExExerercícícicioo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4433
3.63.6.5 .5 SolSoluçãução o IniIniciacial l ArtArtificificialial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4444
3.63.6.6 .6 CasCasos Eos Especspeciaiiais do s do MétMétodo Sodo Simpimplexlex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4477
Capítulo 1
Apresentação
Nesta apostila/disciplina não temos a pretensão de apresentar tudo sobre Pesquisa
Operacional (P.O.) mas sim de introduzir algumas das principais técnicas de P.O.
bem como algumas idéias sobre outras não menos importantes para resolver problemas
práticos que podem surgir na vida profissional.
1.1 Ementa
Introdução à P.O.: a tomada de decisão, definição de P.O., fases de um estudo de P.O..
Problemas de Programação Linear (P.P.L.): modelagem e resoluções - Gráfica, pela
Solução Básica (algébrica) e Método Simplex. Uso de programas computacionais para
a resolução de P.P.L.s: ferramenta Solver do Excel, software TORA, etc. Análise de
Sensibilidade: preço dual e custo reduzido. Dualidade e Análise de Pós-otimização.
Problemas de Transporte e Designação e noções sobre outras técnicas de P.O.
1.2 Objetivos
•  Apresentar a Pesquisa Operacional como uma ciência que tem por objetivo au-
xiliar gerentes e administradores na tomada de decisões;
•  Estudar Programação Linear (P.L.) por ser uma das técnicas mais utilizadas na
prática;
•  Apresentar algumas tecnologias computacionais tais como a ferramenta Solver do
Excel, software TORA, etc., para a resolução de P.P.L.s;
• Estudar algoritmos para a resolução de Problemas de Transporte e Designação;
•  Apresentar noções sobre outras técnicas de P.O.
5
6 CAPÍTULO 1. APRESENTAÇÃO 
1.3 Conteúdo Programático
•  Unidade I
Introdução à P.O.: conceitos e definições sobre tomada de decisão, modelagem e
P.O.. Fases de um Estudo de P.O.. Modelagem de Problemas de P.L., resolução
de PPL gráfica e por solução básica(algébrica). O uso do software TORA.
•  Unidade II
Resolução de P.P.L.s pelo Método Simplex: Princípios, Simplex Tabular e Método
das duas fases. Análise de Sensibilidade: preço dual e custo reduzido. Dualidade
e Análise de Pós-otimização. O uso da ferramenta Solver do Excel e do software
TORA.
•  Unidade III
Problemas de Transporte e Designação e, possivelmente, de outra(s) técnica(s)
de P.O..
1.4 Método de Ensino
•   Exposição de problemas acompanhados de explicações intuitivas e teóricas de
alguma técnica de P.O. com o objetivo de resolver tais problemas;
•  Proposição de problemas para serem resolvidos pelos próprios alunos objetivando
a entrega de tais soluções no formato de relatório técnico e/ou seminário.
1.5 Avaliações e Horários de Atendimento
•  Três (3) provas com direito a uma (1) reposição. Exame final.
•   Trabalhos no formato de relatórios técnicos e/ou seminários desenvolvidos no
decorrer da disciplina também poderão, mas não necessariamente, serem consi-
derados na composição das notas de cada prova.
1.6. BIBLIOGRAFIA 7
1.5.1 Data das Provas e Conteúdo
Tabela 1.1: Data das provas e conteúdos.
Data Conteúdo Data Conteúdo
19 Dezembro Unidade I 29 Abril Reposição
13 Março Unidade II 06 Maio Exame Final
22 Abril Unidade III
1.5.2 Horários de Atendimento
Acessar:  http://sites.google.com/site/gilbertosmatos1
1.6 Bibliografia
Básica 
•  Hamdy A. Taha.  Pesquisa operacional . 8a. ed.. Pearson Book.
•   Andrade, Eduardo Leopoldino. 4a. ed.   Introdução à Pesquisa Operacional:
métodos e modelos para análise de decisões . gen / LTC.
•  Lachtermarcher, Gerson.   Pesquisa operacional na tomada de decisões . 4a. ed.
São Paulo: Pearson - Prentice Hall.
•   Render, Barry M.; Stair, Ralph M.; Hanna, Michael E..   Análise Quantitativa 
para Administração com Excel e POM-QM para Windows . 10a. ed.. Bookman.
Complementar 
•  Arenales, Marcos; Armentano, Vinícius Amaral; Morabito, Reinaldo; Yanasse,
Horacio Hideki (2006).  Pesquisa Operacional - Modelagem e Algoritmos .
•   Ermes Medeiros da Silva et. all (1998). Pesquisa Operacional: Programação
linear. Simulação. 3a. ed.. Ed. Atlas.
•  Yoshida, Luzia Kazuko (1987).  Programação Linear . São Paulo: Atual.
8 CAPÍTULO 1. APRESENTAÇÃO 
Capítulo 2
Introducao à Pesquisa Operacional
2.1 Objetivos do Capítulo
•  Definir PO;
•  Discutir e definir o conceito de decisão;
•  Discutir sobre o processo de decisão e suas classificações;
•  Discutir sobre decisão racional;
•  Discutir a Natureza da PO;
•  Conhecer as Fases de um Estudo de PO.
2.2 Pesquisa Operacional: o que é, quando e como
surgiu?
2.2.1 O que é Pesquisa Operacional?
Como o próprio nome sugere, Pesquisa  quer dizer Estudo  e  Operacional  quer dizer
das Operações/Atividades. Neste contexto, podemos dizer que:
Pesquisa Operacional - é uma ciência que se utiliza de um conjunto de técnicas
quantitativas que tem por objetivo estudar as atividades ou operações de uma organi-
zação com o intuito de auxiliar os gerentes e administradores na tomada de decisões.
9
10 CAPÍTULO 2. INTRODUCAO À PESQUISA OPERACIONAL
2.2.2 Quando e como surgiu a Pesquisa Operacional?
•  A PO apareceu pela a primeira vez durante a Segunda Guerra Mundial, quando
equipes de pesquisadores procuraram desenvolver métodos para resolver deter-
minados problemas de operãções militares.
• O sucesso das aplicações dos métodos desenvolvidos levou o mundo acadêmico e
empresarial a procurar utilizar as técnicas em problemas de administração.
2.2.3 Cientistas...
•  Em 1947, George Dantzig e outros cientistas do Departamento da Força Aérea
Americana apresentaram um método denominado Simplex para a resolução dos
Problemas de Programação Linear (PPL);
•  Outros cientistas que dedicaram os seus estudos à PO (à Pesquisa do Ótimo)
foram:
–  Na antiguidade:
∗  Euclides, Newton, Lagrange, dentre outros;
–  No século XX:
∗  Leontief, Von Neumann, Kantarovich, dentre outros.
2.3 Um pouco da Teoria das Decisões2.3.1 Definição
Dentre outras definições, uma delas diz:
Definição 2.3.1.   “Uma  decisão  é um curso de ação escolhido pela pessoa, como o
meio mais efetivo a sua disposição, para obter os objetivos procurados, ou seja, para 
resolver o problema que a incomoda.” 
2.3.2 Características do Processo de Decisão
O Processo de Decisão:
1.  É Seqüencial
•  É consequência de uma série de fatos anteriores que criaram as bases para
se chegar a decisão.
•  Uma decisão significativa é uma compilação de muitas decisões. Frequente-
mente requer um longo período de tempo.
2.3. UM POUCO DA TEORIA DAS DECISÕES  11
2.  É Complexo
•  Consiste de um inter-relacionamento entre pessoas, responsabilidades pelo
serviço, comunicação e sistemas de informações, códigos de ética e moral e,
às vezes, interesses e objetivos diferentes dos participantes.
3.  Envolve valores subjetivos
•  Muitas vezes é desejável que a maior parte de um processo de decisão seja
identificável e claro, podendo ser repetido por outras pessoas ou em outras
ocasiões;
•  No entanto, é impossível que inúmeros fatores intuitivos, provenientes de
experiência pessoal e personalidade não interfiram no processo decisório.
4.  Em ambiente institucional
•  O inter-relacionamento entre pessoas, a forma como se processa o fluxo de
informações, as características da organização e o sistema hierárquico são
fatores que afetam fundamentalmente o processo de tomada de decisão.
2.3.3 Classificação das Decisões
Uma classificação geral onde as decisões são vistas à luz do  nível  em que ocorrem  den-
tro de uma empresa  e do  grau de complexidade envolvido é dada e exemplificada
abaixo:
1.  Nível Estratégico
•  Diz respeito a sua importância e abrangência com relação à organização.
•  Quanto mais as atividades de uma organização forem afetadas pela decisão,
mais estratégica será.
2.  Grau de Estruturação (complexidade)
•  Uma decisão é tão mais estruturada quanto mais intimamente o processo
puder ser acompanhado ou mesmo repetido por outras pessoas, em outras
ocasiões.
12 CAPÍTULO 2. INTRODUCAO À PESQUISA OPERACIONAL
Grau de
Estruturação
alto Administração de Programação da Localização de
estoques produção uma nova fábrica
médio Financiamento do Programação Diversificação pela
capital de giro orçamentária aquisição de outra empresa
baixo Escolha de manchete Contratação de um Aprovação de um programa de
de jornal diretor de planejamento pesquisa e desenvolvimento
operacional gerencial corporativo
Nível Estratégico
2.3.4 Algumas técnicas segundo o grau de estruturação da de-
cisão
Para problemas com:
•  Alto grau de estruturação
–  Programação Linear (PL)
∗  Problemas de distribuição de recursos
∗  Problemas de transporte
∗ Problemas de planejamento da produção
∗ Problemas de corte de materias, etc.
–  Programação Não Linear (PNL)
–  Programação Inteira
–  Teoria das filas
∗  Organização do tráfego aéreo
∗  Construção de barragens, etc.
–  Teoria dos estoques
–  Programação dinâmica, etc.
•  Grau de estruturação médio
–  Análise estatística
–  Simulação
–  Análise de risco
–  teoria dos jogos
Observação: em todas as situações essas técnicas dependem de uma ferramenta
extremamente útil que é:
O Computador
2.3. UM POUCO DA TEORIA DAS DECISÕES  13
2.3.5 Sobre Decisão Racional
Definição 2.3.2 (Decisão racional).   é aquela que, de forma efetiva e eficiente,
garante a realização dos objetivos preestabelecidos, para os quais os meios e recursos 
 foram reservados.
Obstáculos a uma decisão racional
•  Limitações de caráter pessoal  - força do hábito, falta de memória e distração,
prejulgamentos e valores pessoais.
•  Limitações de caráter político  - necessidade de compromisso entre diferentes
posições e órgãos da empresa.
•  O fator tempo  - às vezes a urgência de uma solução leva a uma decisão com
conhecimento incompleto dos dados do problema.
Duas dificuldades inerentes ao problema
1.  Escolha do problema certo para resolver  - o primeiro passo para uma to-
mada de decisão racional é saber qual problema que requer solução e isto nem
sempre é fácil.
•  É necessário observar sintomas tais como: reclamações, atrasos, prejuízos,
etc.
•   Deve-se   identificar   claramente qual é o  problema que   causa aqueles
efeitos pertubadores.
2.  Conhecimento insuficiente
•  O ideal seria ter o  conhecimento completo  de todas as  alternativas e
consequências possíveis das  decisões.
•  Na prática as decisões são tomadas com base em  informações incomple-
tas ou parciais.
•   Informação tem custo   - quanto mais informações forem exigidas mais
tempo e dinheiro serão necessários.
•  Informação demais pode prejudicar  - a análise de muitas informações
exige tempo e habilidades extras.
•  No caso de pouca ou falta de informações - a  experiência pessoal
pode ser fundamental para a tomada de decisão racional.
14 CAPÍTULO 2. INTRODUCAO À PESQUISA OPERACIONAL
2.4 A Natureza da Pesquisa Operacional
•  Um estudo de Pesquisa Operacional consiste, basicamente, em construir um
modelo de um sistema real  como meio de analisar e compreender o compor-
tamento do mesmo.
– O sistema pode atualmente existir e neste caso o objetivo é analisá-lo e
escolher uma ação para aprimorá-lo.
– O  sistema  pode  ainda estar em concepção   e neste caso o objetivo é
identificar a melhor estrutura do sistema futuro.
•  A influência de um número muito grande de variáveis sobre o sistema real bem
como a relação entre elas contribuem para a complexidade do sistema.
–   Ainda que um sistema real seja complexo, o sistema muitas vezes pode
ter o comportamento fundamentalmente influenciado por uma quantidade
reduzida de variáveis principais.
∗  A simplificação do sistema real em termos de um modelo passa primei-
ramente pela  identificação dessas variáveis principais.
2.5 Fases de um Estudo de Pesquisa Operacional
Nesta seção procuramos descrever resumidamente sobre as principais fases/etapas ne-
cessárias para o desenvolvimento de um estudo ou projeto de Pesquisa Operacional.
De modo geral, podemos dizer que as principais fases são:
1.  Formulação/Definição do Problema
“É muito difícil procurar uma solução “certa” para um problema mal 
 formulado!!!” 
A frase acima resume muito bem a grande importância de se definir bem um
problema em um estudo de PO. Nesta fase, três (3) aspectos principais devem
ser discutidos:
•  Descrição exata dos objetivos do estudo;
•  Identificação das alternativas de decisão existentes;
• Reconhecimento das limitações, restrições e exigências do sistema(realidade).
2.  Construção do Modelo
Um modelo é uma representação simplificada de uma situação da vida real e
reflete a essência do problema formulado. Um  modelo matemático nesta fase
pode muitas vezes formalizar esta representação simplificada em termos de sím-
bolos e expressões matemáticas. Alguns aspectos fundamentais  para a construção
do modelo são:
2.5. FASES DE UM ESTUDO DE PESQUISA OPERACIONAL 15
•  Simplificar sem perder a essência do problema
A formulação matemática de um problema deve iniciar por um modelo mais
simples possível mas de tal forma que as soluções possam ser aplicadas na
vida real.
•  Processo em Espiral
A modelagem desenvolve-se em forma de espiral, começando por uma repre-
sentação simplificada do problema até se chegar, após vários ciclos, a uma
representação mais próxima da realidade.
•  Escolha do modelo certo
Por vezes o problema pode ser representado por modelos já desenvolvidos
pela Pesquisa Operacional, como, por exemplo: modelos de Programação
Linear, modelos de Programação Não-Linear, Programação dinâmica, Pro-
blema de transporte, etc.
3.  Solução do Modelo
Nesta etapa o analista de PO deve conhecer as principais técnicas de solução e al-
goritmos mais adequados em termos de rapidez de processamento computacional
e precisão da resposta. O uso de softwares adequados é de grande importância
nesta etapa.
4.  Validação do Modelo
Nesta fase é necessário avaliar se o modelo; apesar de sua inexatidão em re-
presentaro sistema real; ainda é capaz de fornecer uma previsão aceitável do
comportamento do sistema.
Um método utilizado para validar um modelo consiste em analisar o seu desem-
penho com o uso de dados passados do sistema, verificando se o modelo reproduz
bem o comportamento que o sistema manifestou. Dependendo das conclusões
desta avaliação, os seguintes passos são adotados:
•   Avaliação satisfatória - procede-se à tomada de decisão e busca-se a im-
plementação da solução no sistema real.
•  Avaliação não-satisfatória   - procede-se à reformulação, remodelação e
resolução do novo modelo.
É importante destacar que a validação de um modelo aplicado a sistemas ine-
xistentes pode ser feita pela verificação da correspondência entre os resultados
obtidos e algum comportamento esperado do novo sistema.
5.   Implementação da Solução
Uma vez validado o modelo e as soluções obtidas é necessário implementá-las no
sistema real e como esta é uma atividade que altera uma situação existente é
preciso envolver ativamente a administração e todas as componentes que atuam
no sistema em estudo.
16 CAPÍTULO 2. INTRODUCAO À PESQUISA OPERACIONAL
Nesta fase é necessário a existência de uma equipe que controle, supervisione e
esteja apta a reformular algumas partes do modelo mediante às novas situações-
problemas do sistema real. Se necessário, modelos mais complexos devem ser
considerados.
6.  Avaliação Final
A avaliação dos resultados obtidos em qualquer etapa do processo é de fundamen-
tal importância, pois isto garantirá melhor adequação das decisões às necessidades
do sistema e aceitação mais fácil dessas decisões por todos os setores envolvidos.
2.6. 1A. LISTA DE EXERCÍCIOS  17
2.6 1a. Lista de Exercícios
1) (Passagens aéreas) Imagine que você tenha um compromisso de trabalho de
cinco (5) semanas entre João Pessoa (JP) e Recife (Rec). Você pega um avião
em João Pessoa na segunda-feira e volta na quarta-feira. Uma passagem aérea
normal de ida e volta custa R$ 400,00, mas há um desconto de 20% se as datas
do bilhete abrangerem um final de semana. Uma passagem só de ida em qualquer
direção custa 75% do preço normal. Como seria mais conveniente você comprar
as passagens para o período de cinco semanas? Obs.: Considere três ou quatro
opções/alternativas viáveis e decida pela mais conveniente.
2) Considere a montagem de um retângulo de área máxima com um pedaço de fio
de comprimento L   centímetros. Qual deveria ser a largura(l) e a altura(a) do
retângulo?
a) Identifique duas soluções viáveis e determine qual delas é a melhor.
b) Determine a solução ótima para este problema. (Sugestão: use a restrição
para expressar a função objetivo em termos de uma só variável e a partir
daí utilize o cálculo diferencial.)
3) Certa vez, três amigos inseparáveis, em uma de suas viagens, tiveram que atra-
vessar um rio usando um barco mas o barco só suportava no máximo 150 Kg e
dois destes amigos pesavam 75 Kg, já o terceiro pesava 150 Kg. É claro que o
barco não podia nem ir e nem voltar sem ninguém dentro e assim o problema é:
como os três amigos, nestas condições, podem atravessar o rio de um lado para
o outro?
4) Amy, Jim, John, e Kelly estão em pé na margem leste de um rio e querem
atravessar para a margem oeste usando uma canoa. A canoa pode levar no
máximo duas pessoas por vez. Amy, que tem a constituição mais atlética, pode
atravessar o rio a remo em 1 minuto. Jim, John e Kelly levariam 2, 5 e 10 minutos,
respectivamente. Se houver duas pessoas na canoa, a mais lenta determinará o
tempo da travessia. O objetivo é que os quatro estejam do outro lado do rio no
menor tempo possível.
a) Identifique no mínimo dois planos viáveis para atravessar o rio (lembre-se de
que a canoa é o único meio de transporte, e não pode ir nem voltar vazia).
b) Defina o critério para avaliar as alternativas.
c) Qual é o menor tempo para transportar os quatro para o outro lado do rio?
(Obs.: a solução deste problema é dada no Apêndice C do livro de P.O. do
Taha)
18 CAPÍTULO 2. INTRODUCAO À PESQUISA OPERACIONAL
Capítulo 3
Programação Linear
3.1 Introdução
A programação linear pertence a uma classe de problemas chamada de otimização que
visa maximizar ou minimizar (otimizar) uma função de várias variáveis sujeita a certas
restrições.
A principal característica da programação linear consiste do fato de que tanto a
função (função objetivo) a ser maximizada (ou minimizada) como também as  restri-
ções podem ser representadas por  expressões lineares e devido a esta linearidade,
métodos numéricos simples e eficientes podem ser utilizados para resolver tais proble-
mas.
Veremos, agora, um exemplo simples de problema que pode ser formulado/modelado
como de programação linear.
3.2 Problemas de Programação Linear (PPL) e Mo-
delagem Matemática
Exemplo 3.2.1 (Fábrica 1).  Uma pequena indústria produz artigos  A1 e  A2 que 
são vendidos a 200 u.m. (unidades monetárias) e 300 u.m., respectivamente. Na sua 
produção são utilizados 3 tipos de matérias-primas, P 1, P 2 e  P 3, que são gastas da 
seguinte forma:
2 unidades de P 1  para fabricar 1 unidade de  A1,
4 unidades de P 2  para fabricar 1 unidade de  A1,
1 unidade de P 1  para fabricar 1 unidade de  A2,
1 unidade de P 3  para fabricar 1 unidade de  A2,
Por razões econômicas, as matérias-primas  P 1, P 2 e P 3  estão disponíveis no
máximo em 20, 32 e 10 unidades, respectivamente.
19
20 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
O dono da empresa deseja saber as quantidades dos produtos  A1 e A2  que devem 
ser produzidas para que a receita bruta seja a maior possível.
3.2.1 Formulação Matemática do PPL
Para resolver o  problema da Fábrica 1  vamos formular o problema como um pro-
blema de programação linear. Para isto, é necessário realizarmos algumas suposições,
definirmos algumas variáveis ditas de decisão e representar as informações do problema
em termos de expressões matemáticas. Vejamos:
Suposições para a modelagem matemática :
(a) Supor que a quantidade do produto a ser vendida é igual a quantidade do produto
a ser fabricada, isto é, não há estoque;
(b) Supor que a receita bruta é proporcional Ãă quantidade vendida;
(c) Supor que as matérias-primas gastas são proporcionais às quantidades produzi-
das, ou seja, não há desperdício de matéria-prima;
(d) Admitir que quantidades negativas dos produtos A1 e A2  não terão significado
algum.
Definição de variáveis de decisão:
Agora, observe que podemos considerar as seguintes variáveis ditas de decisão:
x1: quantidade a ser produzida dos produtos A1, e
x2: quantidade a ser produzida dos produtos A2
Definição da Função Objetivo (F.O.):
Após interpretar as hipóteses (a) e (b), verificamos que podemos exprimir a receita
bruta como função das variáveis x1 e x2, da seguinte forma:
f (x1, x2) = 200x1 + 300x2,
Esta função é denominada Função Objetivo (F.O.) e deverá ser maximizada com
relação às variáveis  x1 e  x2 de modo que a receita bruta será a maior possível, conforme
o dono da fábrica deseja.
Definir e escrever as restrições do problema em termos de inequações
lineares:
Observe que existe limite na disponibilidade das matérias-primas e isto requer
que restrições sejam consideradas no problema que estamos modelando. Portanto,
admitindo a hipótese (c), para cada matéria-prima temos uma restrição que pode ser
expressa da seguinte forma:
3.2. PROBLEMAS DE PROGRAMAÇÃO LINEAR (PPL) E MODELAGEM MATEMÁTICA21
- para a matéria-prima P 1: 2x1 + x2 ≤ 20
- para a matéria-prima P 2: 4x1 ≤ 32
- para a matéria-prima P 3: x2  ≤ 10.
Resumindo o Problema formulado:
Assim, é possível escrever, de forma sucinta, o problema do seguinte modo:
"Encontre, se existir, o par (x∗1, x
∗
2), tal que a função f (x1, x2) = 200x1 + 300x2,
sujeita às restrições
2x1 + x2 ≤ 20
4x1 ≤ 32
x2 ≤ 10
x1  ≥ 0, x2 ≥ 0 (hipótese d),
assuma o maior valor possível."
O Problema de Programação Linear (PPL) na Forma Matemática Ge-
ral :
Finalmente, o problema formulado pode ser escrito da seguinte forma matemática
geral:
Maximizar 200x1   + 300x2,Sujeito aă 2x1 + x2 ≤ 20
4x1 ≤ 32
x2 ≤ 10
x1  ≥ 0, x2  ≥ 0.
3.2.2 Exercícios de Fixação
Desenvolva e apresente os modelos de programação linear correspondentes aos seguintes
problemas:
1. (Marcenaria) Este exemplo nos ajudará a compreender os princípios básicos do
Método Simplex e foi extraído do livro: Andrade, Eduardo Leopoldino, 1990.
Formulação do problema:
O gerente de uma marcenaria deseja estabelecer uma programação diária de pro-
dução. Nesta marcenaria apenas dois produtos são fabricados: mesa e armário,
ambos de um só modelo. Por simplicidade consideramos que a marcenaria tem
limitações em somente dois recursos: madeira e mão-de-obra, cujas disponibili-
dades diárias são mostradas na seguinte tabela:
22 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
Tabela 3.1: Disponibilidades diária de recursos.
Recurso Disponibilidade
Madeira 12 m2
Mão-de-obra (horas/Unid.) 8 H.h. (Horas homem)
O processo de produção é tal que:
•  Para fazer 1 mesa, gasta-se:
– 2 m2 de madeira
–  2 H.h. de mão-de-obra
•  Para fazer 1 armário, gasta-se:
– 3 m2 de madeira
–  1 H.h. de mão-de-obra
Sabe-se, ainda, que:
•  O lucro de cada mesa é de 4 u.m. (unidades monetárias)
•  O lucro de cada armário é de 1 u.m. (unidade monetária)
O problema do fabricante é: encontrar o programa de produção que maximiza o
lucro total.
Este problema é extremamente simples e por isso é possível resolvêlo usando
apenas algumas considerações qualitativas, o que possibilita compreender os fun-
damentos do método Simplex que veremos posteriormente.
2. (Agricultura 1) Um agricultor precisa adubar a sua plantação e dispõe de dois
tipos de adubo. O primeiro tipo contém 3 g  de fósforo, 1 g  de nitrogênio e 8 g
de potássio, e custa 10 u.m. (unidades monetárias) por quilograma. O segundo
contém 2 g  de fósforo, 3 g  de nitrogênio e 2 g  de potássio, e custa 8 u.m. por
quilograma. O agricultor sabe que um quilograma de adubo dá para 10 m2 de
terra, e que o solo em que estão suas plantações necessita de pelo menos 3 g de
fósforo, 1,5 g  de nitrogênio e 4 g  de potássio a cada 10 m2. Nestas condições,
quanto o agricultor deve comprar de cada adubo, para cada 10 m2, de modo a
conseguir ter o mínimo custo?
3.2. PROBLEMAS DE PROGRAMAÇÃO LINEAR (PPL) E MODELAGEM MATEMÁTICA23
3. (Marketing 1) O departamento de marketing de uma empresa estuda a forma
mais econômica de aumentar em 30% as vendas de seus dois produtos P 1 e  P 2.
As alternativas são:
a) Investir em um programa institucional com outras empresas do mesmo ramo.
Esse programa requer um investimento mínimo de R$ 3.000,00 e deve propor-
cionar um aumento de 3% nas vendas de cada produto, para cada R$ 1.000,00
investidos.
b) Investir diretamente na divulgação dos produtos. Cada R$ 1.000,00 investidos
em P 1 retornam um aumento de 4% nas vendas, enquanto que para P 2 o retorno
é de 10%.
A empresa dispõe de R$ 10.000,00 para esse empreendimento. Quanto deverá
destinar a cada atividade?
24 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
3.3 Solução Gráfica de um Problema de Programação
Linear (PPL)
Observação:  Trazer régua, lápis e borracha para as aulas de solução gráfica, e, se
possível, notebook para o uso do software TORA disponibilizado no site do livro de
PO do autor Taha.
3.3.1 Introdução
Até o momento, apenas formulamos alguns problemas como sendo de programação
linear. Na verdade, o que fizemos foi transpor uma realidade existente em determinado
ambiente (e.g. indústria e terras agrículas) para um modelo matemático que procura
representá-lo da melhor forma possível. Este procedimento pode ser considerado como o
primeiro passo para a resolução de problemas de otimização. O próximo passo consiste
em buscar a melhor solução para o problema em questão.
Nesta seção, veremos como obter soluções, caso existam, através de gráficos. Em
particular, veremos como obter soluções gráficas para problemas de P.L. que envolvem
apenas 2 variáveis; pois, a solução gráfica para problemas que envolvem 3 variáveis,
em geral, não é fácil e para 4 ou mais variáveis, a resolução de um P.P.L só é possível
algebricamente.
Para ilustrar o método gráfico de solução de um P.P.L. continuaremos com a
resolução dos problemas de programação linear já formulados na seção anterior.
3.3.2 Exemplo
Exemplo 3.3.1 (Cont. Fábrica 1).  Para o problema da Fábrica 1, o seguinte P.P.L
 foi considerado:
Maximizar  200x1   + 300x2,
Sujeito àă  2x1 + x2 ≤ 20
4x1 ≤ 32
x2 ≤ 10
x1  ≥ 0, x2 ≥ 0.
Então, a solução gráfica consiste em desenvolver os seguintes passos:
1
0) Determinar o conjunto de pontos  (x1, x2) ∈ 2 que satisfazem as restrições do
problema de programação linear. Para isso, deve-se determinar os pontos do plano que
satisfazem cada uma das inequações das restrições, tais como:
(a) pontos que satisfazem a primeira inequação: .
(Esboçar a região do plano que satisfaz a primeira inequação)
3.3. SOLUÇÃO GRÁFICA DE UM PROBLEMA DE PROGRAMAÇÃO LINEAR (PPL)25
(b) pontos que satisfazem a segunda inequação: .
(Esboçar a região do plano que satisfaz a segunda inequação)
(c) pontos que satisfazem a terceira inequação: .
(Esboçar a região do plano que satisfaz a terceira inequação)
(d) pontos que satisfazem a condição de não-negatividade: .
(Esboçar a região do plano que satisfaz a condição de não-negatividade)
Antes de prosseguirmos à busca gráfica de uma solução ótima para o PPL, o
conhecimento da seguinte definição é de fundamental importância.
Definição 3.3.1 (Região Viável).  É o conjunto de pontos que satisfaz todas as 
restrições. Esta região também é conhecida por  conjunto de soluções (ou pontos)
viáveis.
Portanto, a região viável, ou seja, os pontos que satisfazem todas as restrições
estarão na intersecção das regiões encontradas em (a), (b), (c) e (d).
(Esboçar a região do plano que satisfaz todas as restrições)
26 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
Vejamos, agora, o próximo passo para a obtenção da solução ótima do P.P.L.
através do método gráfico.
2
0) Após identitificar no plano (gráfico) o conjunto de soluções viáveis, o problema
se torna o seguinte:
 “Determinar, se existir, um ponto (x∗1, x
∗
2) pertencente ao conjunto de pontos viá-
veis, de tal forma que a função f (x1, x2) = 200x1+300x2 assuma o maior valor possível.”
Uma das maneiras de obter a solução ótima, isto é, o ponto (x∗1, x
∗
2)  da região
viável que maximiza a função f (x1, x2) = 200x1 + 300x2, consiste em atribuir alguns
valores para a função, obtendo, assim, o que se chama de  Curvas de Nível. Para este
problema, em particular, alguns exemplos de curvas de nível são:
200x1 + 300x2  = 1200
200x1 + 300x2  = 2400
200x1 + 300x2  = 3600
E as curvas de nível representadas no sistema de eixo cartesiano serão da forma:
(Esboçar as curvas de nível no sistema de eixo cartesiano)
Observe que:
•  As curvas de nível são todas retas paralelas e
•  A função objetivo assume valor cada vez maior num determinado sentido.
É possível provar que as  curvas de nível são  perpendiculares ao  vetor gra-
diente da função; ou seja; as curvas de nível da função f (x1, x2) = 200x1 +300x2 são
3.3. SOLUÇÃO GRÁFICA DE UM PROBLEMA DE PROGRAMAÇÃO LINEAR (PPL)27
perpendiculares ao vetor

∂f (x1, x2)
∂x1
,
 ∂f (x1, x2)
∂x2

 = (200, 300).
Além disso, o vetor gradiente nos fornece o sentido de crescimento da função.
(Esboçar, no gráfico anterior, o vetor gradiente perpendicular às curvas de nível,
indicando o sentido de crescimento da função objetivo f (x1, x2) = 200x1 + 300x2)
Finalmente, diante destas informações, poderemos determinar uma solução ótima
para o problema, se existir. Para isto, observe o seguinte gráfico:
(Esboçar a região viável juntamente com o vetor gradiente e várias curvas de nível no
sentido de crescimento (máximo) da função objetivo cujo(s) ponto(s) ainda 
pertença(m) à região viável)
A partir deste gráfico, pode-se observar que a curva de nível de maior valor dentro
da região viável é a reta que passa pelo ponto de coordenadas (x1, x2) = (5, 10).
Portanto, o ponto (x∗1, x
∗
2) =(5, 10) é a solução do problema e o maior valor que a
função pode assumir é f (x∗1, x
∗
2) = 200x
∗
1 + 300x
∗
2 = 200.5 + 300.10 = 4000.
Dizemos que (x∗1, x
∗
2) = (5, 10) é uma solução ótima, e o valor da função f (x
∗
1, x
∗
2) =
4000 o  valor ótimo do problema.
Para finalizar, devemos descrever a solução do problema  da seguinte forma:
Sendo x1 e x2  a quantidade do produto A1 e A2  a ser produzida, respectivamente;
o dono da empresa deve produzir 5 unidades do produto A1  e 10 unidades do produto
A2  e a receita bruta máxima é de  4000 u.m.
28 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
3.3.3 Exercícios de Fixação
Resolva; se possível; pelo método da solução gráfica os PPLs modelados na Seção
anterior. Resolva-os manualmente e usando o software TORA.
3.3. SOLUÇÃO GRÁFICA DE UM PROBLEMA DE PROGRAMAÇÃO LINEAR (PPL)29
3.3.4 Tipos de Solução de um PPL Ilustrados por Resolução
Gráfica
Na seção anterior, foi ilustrado alguns problemas de PPL cujas soluções ótimas pu-
deram ser obtidas a partir de análises gráficas. Nestes exemplos, foi possível verificar
a existência de uma única solução ótima. Acontece que nem sempre isso ocorre, ou
seja, existem problemas em que existem   infinitas soluções ótimas  ou até mesmo
problemas em que a solução ótima seja impossível ou  inviável de ser obtida. Exis-
tem, ainda, problemas cujo valor da função pode crescer (ou decrescer) indefinidamente
dentro da região viável, e, nestes casos, dizemos que os  problemas são  ilimitados.
Para uma melhor compreensão deste assunto, obtenha a solução dos seguintes
problemas de programação linear através do método gráfico e classifique os problemas
segundo o tipo de solução obtido.
1 - Desenvolva, apresente e interprete a solução gráfica para os seguintes problemas
de programação linear:
a)
max 2h1 + 3h2
sujeito a h1 + h2 ≤ 50
2h1 + 3h2 ≥ 70
2h1 ≥ 20
3h2 ≥ 30
h1 ≥ 0, h2 ≥ 0.
b)
min 30x1 + 20x2
sujeito a 4x1 + x2 ≥ 20
x1 + 2x2 ≥ 10
x1 ≥ 2
x1 ≥ 0, x2  ≥ 0.
c)
max x1 + 2x2
sujeito a 4x1 + x2 ≥ 20
x1 + 2x2 ≥ 10
x1 ≥ 2
x1  ≥ 0, x2 ≥ 0.
d)
min x1 + x2
sujeito a −2x1 + x2 ≥ 2
x1 − 2x2 ≥ 2
x1  ≥ 0, x2 ≥ 0.
30 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
e)
max x1 + x2
sujeito a −2x1 + x2 ≤ 2
x1 − 2x2 ≤ 2
x1 + x2 ≤ 4
x1  ≥ 0, x2 ≥ 0.
f)
max x2
sujeito a −x1 + x2 ≤ 1
x2 ≤ 2
x1 ≥ 0, x2 ≥ 0.
3.4. DIFERENTES FORMAS DE UM PPL 31
3.4 Diferentes Formas de um PPL
3.4.1 Introdução
Qualquer problema de programação linear pode ser escrito na forma que chamaremos
geral, mas, por conveniência, qualquer PPL também pode ser escrito sob outras formas
e representações. A principal  forma  de um PPL que estudaremos é a  padrão e as
possíveis representações de um PPL   são:   cartesiana, matricial e vetorial . Vejamos,
agora, algumas definições e observações sobre este assunto.
Definição 3.4.1 (Forma Padrão). Dizemos que um problema de programação linear 
está na   forma padrão quando encontra-se na seguinte forma:
Observações:
a. As restrições de um PPL na forma padrão são todas escritas na forma de igual-
dades lineares (equações lineares).
b. Qualquer PPL pode ser escrito na forma padrão.
c. O PPL na  forma padrão  acima encontra-se   representado  por uma notação
cartesiana. Agora, de forma equivalente, o PPL pode ser representado por uma
notação matricial, dada por:   Notação matricial de um PPL na forma
padrão
Em que:
32 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
c

T  =
x

=
A =
d. Um PPL na forma padrão  também pode ser representado por uma  notação
vetorial, dada por:
Em que a
 j
=
Exemplo: Dado o seguinte PPL na forma padrão e representação cartesiana,
represente-o na forma matricial e vetorial:
Maximizar 5x1 − 3x2 − 4x3,
Sujeito Ãă x1 + 2x2 − x3 = 10
2x1 + x2 + 3x3 = 15
3x1 + 3x2 + 2x3 = 12
x1 ≥ 0, x2  ≥ 0, x3 ≥ 0.
Definição 3.4.2 (Solução Viável e Região Viável). Uma  solução x

= (x1, . . . , xn)T 
é dita  viável  se satisfaz todas as restrições (2) e as condições de não-negatividade (3)
do PPL na forma padrão. O conjunto de todas as soluções viáveis é chamado  região
viável .
Definição 3.4.3 (Solução Ótima). Uma  solução viável  que fornece o maior valor 
à função objetivo f  é chamada solução ótima, denotada por  x

∗ = (x∗1, . . . , x
∗
n)
T .
3.4. DIFERENTES FORMAS DE UM PPL 33
Observação 1.  Uma solução é ótima se:
f (x∗1, . . . , x
∗
n) ≥ f (x1, . . . , xn),  para qualquer solução viável  x
= (x1, . . . , xn)
T .
3.4.2 Transformação de PPL’s para a Forma Padrão
Foi dito anteriormente que qualquer PPL pode ser transformado para a forma padrão.
Para isto é importante saber que:
1. Minimizar f (x

) = f (x1, . . . , xn) é equivalente à maximizar −f (x
) = −f (x1, . . . , xn)
(Prove!).
2. A i−ésima restrição da forma:
pode ser transformada na seguinte igualdade:
em que xF i =
é conhecida por variável de folga.
3. A i−ésima restrição da forma:
pode ser transformada na seguinte igualdade:
em que xF i ≥ 0.
Neste caso xF i também é denominada variável de folga ou de forma mais adequada
variável de excesso.
4.  Variáveis negativas
Se na modelagem de um problema a variável  xi deve assumir um valor negativo,
esta variável pode ser substituída por uma não-negativa da seguinte forma:
Substituir no modelo matemático a variável
xi ≤ 0
pela variável
x

i = −xi ≥ 0
5.  Variáveis livres de sinal
Se xi é irrestrita de sinal, ou seja, pode ser positiva, negativa ou nula, a variável
é dita livre e a mesma pode ser substituída por duas outras não-negativas. Para
isto note que qualquer número xi  pode ser escrito como:
34 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
3.4.3 Exercícios de Fixação
1 - Obtenha a forma padrão dos seguintes problemas de programação linear:
a)
max 5x1 + 3x2
sujeito a 2x1 + x2 ≤ 8
x1 − 2x2 ≥ 3
x1  ≥ 0, x2 ≥ 0.
b)
max 5x1 + 3x2
sujeito a 2x1 + x2 = 8
x1 − 2x2 ≥ 3
x1  ≥ 0, x2 ≥ 0.
c)
max 5x1 + 3x2
sujeito a 2x1 + x2 ≤ 8
x1 − 2x2 ≤ 3
x1  ≥ 0, x2 ≤ 0.
d)
max 5x1 + 3x2
sujeito a 2x1 + x2 ≤ 8
x1 − 2x2 ≤ 3
x1 ≥ 0, x2  livre de sinal
e)
min 5x1 + 3x2 − x3
sujeito a 2x1 + x2 + 3x3 ≤ 15
x1 − 2x2 + x3 ≥ 10
3x1 − x2 + 2x3 = 8
x1  ≥ 0, x2 ≤ 0, x3  livre de sinal.
3.5. SOLUÇÕES BÁSICAS DE UM SISTEMA DE EQUAÇÕES LINEARES M ×N,M ≤ N  E A RES 
3.5 Soluções Básicas de um Sistema de Equações Li-
neares m × n,m ≤ n   e a Resolução de um PPL
Utilizando Soluções Básicas
3.5.1 Introdução
Já vimos que as restrições de um PPL na forma padrão formam um sistema de equações
lineares. Veremos, agora, um método para determinar algumas soluções de um sistema
linear retangular (cujo número de equações é menor ou igual ao número de incógnitas,
m × n,m ≤ n). Para iniciar, vejamos algumas definições importantes.
Definição 3.5.1 (Matriz Base ou Básica).  Dado um sistema de equações lineares 
m × n, m ≤ n, Ax

= b

, A ∈ m×n, x

∈ n, b

∈ m, dizemos que uma submatriz B
m×m da matriz  A, com  det(B) = 0 (determinante não-nulo e, portanto,  B  invertível)
é uma  matriz base ou básica .
Definição 3.5.2 (Partição Básica).  A partição básica é uma reorganização (parti-
ção) nas colunas da matriz de coeficientes  A de um sistema de equações lineares  Ax

= b
descrita da seguinte forma:
A = [ B | N ].
Onde:
• B  - é uma matriz m × m básica ( m colunas de A invertível).
• N  - é a matriz não-básica m × (n − m)  formada pelas  n − m  colunas de A que 
não estão na matriz básica B.
Observação 2.  Para cada partição básica tem-se associada uma partição no vetor  x

,
dada por:
x

=

x
Bx
N 

,
em que:
• x
B
 - é o vetor de variáveis (básicas) diretamente associadas às colunas da matriz 
básica B.
• x
N 
  - é o vetor de variáveis (não-básicas) diretamente associadas às colunas da 
matriz não-básica N .
Exemplo 3.5.1.  A partir do sistema de equações lineares abaixo, obtenha todas as 
partições básicas possíveis, identificando as variáveis básicas e não básicas:

x1 + x2 + x3 = 4
x2 + + x4 = 2
Solução:
36 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
3.5.2 Solução Geral e Solução Básica de um Sistema de Equa-
ções Lineares
Quando uma partição básicaA = [ B | N  ]   é considerada, o sistema Ax

= b
pode ser reescrito de forma equivalente como:
Bx
B
+ Nx
N 
= b
 ,
pois
Ax

= b

⇐⇒ A = [ B | N  ]

x
Bx
N 

 =  b

⇐⇒ Bx
B
 + Nx
N 
= b

.
Segue, portanto, que a solução dada por:
x
B
= B−1b

− B−1Nx
N 
  (3.1)
é denominada solução geral de um sistema de equações lineares.
Observação 3.  Para obter uma solução geral basta atribuir valores quaisquer às  n−m
variáveis não-básicas pertencentes ao vetor  x
N 
, obtendo-se assim, de forma única, os 
m valores das variáveis básicas pertencente ao vetor x
B
.
Definição 3.5.3 (Solução Básica).  Uma solução x

=

x
Bx
N 

 é chamada solução
básica quando as  n − m  variáveis não-básicas do vetor  x
N 
  da solução geral são todas 
iguais a zero. Desta forma, a solução básica assume a forma:
x

=

x
Bx
N 

 =

B−1b
0


.
Definição 3.5.4 (Solução Básica Viável).  Dizemos que uma solução   básica  é 
viável  quando x
B
≥ 0

. Neste caso, temos que:
x

=

x
Bx
N 

 =

B−1b
0


≥ 0

.
Propriedade 1  (2.1, pág. 73 de Arenales et al, 2006).  Considere uma região viável 
descrita como S = {x

∈  tal que Ax

= b

, x

≥ 0

}. Um ponto x

∈ S  é um  vértice de 
S  se e somente se x

 for uma  solução básica viável .
Consequência: Uma região viável S   tem um número finito de vértices pois há
um número finito de partições básicas, limitado por:

n
m

 =
n!
m!(n − m)!
,
em que n é o número de variáveis e m é a quantidade de equações.
3.5. SOLUÇÕES BÁSICAS DE UM SISTEMA DE EQUAÇÕES LINEARES M ×N, M  ≤ N  E A RES 
Propriedade 2   (ver Arenales et al, 2006). Se  um problema de programação linear 
tem solução ótima , então   existe um vértice ótimo.
Observação 4.   Provas das propriedades 1 e 2 podem ser encontradas, por exemplo,
em Bregalda et al. (1988).
3.5.3 Aplicação dos Resultados: Um método de Solução de
PPL
A partir dos resultados das sub-seções anteriores tornou-se possível obter um método
de solução de PPLs que não necessariamente possuem apenas duas (2) variáveis de
decisão mas sim duas (2) ou mais, como está descrito a seguir:
Consequência (Um método de Solução de PPL):
Se existe uma solução ótima para um PPL, basta que se procure o ótimo entre
todas as soluções básicas viáveis (vértices da região viável).
Exemplo 3.5.2.  Dado o seguinte PPL:
max  x1 + 2x2
sujeito a  x1 + x2 ≤ 4
x2 ≤ 2
x1  ≥ 0, x2 ≥ 0.
a) Obtenha a forma padrão deste PPL.
b) Determine quantas soluções básicas existem e obtenha-as.
c) Dentre as soluções básicas, obtenha as básicas viáveis e a solução ótima.
d) Desenvolva a solução gráfica do PPL e identifique graficamentes as soluções 
básicas, básicas viáveis e ótima obtidas no item anterior.
e) Qualquer solução básica é um vértice da região viável? Explique.
Resp.: Solução ótima: (x1, x2, x3, x4) = (2, 2, 0, 0). Valor ótimo = 6. ( x3, x4  são variáveis de folga).
Solução:
38 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
3.6 O Método Simplex
3.6.1 Princípios Básicos
O método Simplex é uma ferramenta utilizada normalmente para a resolução de pro-
blemas de alocação de recursos e pertence a um capítulo da Pesquisa Operacional
chamado de Programação Linear.
A partir deste momento, apresentamos a conceituação básica do método Simplex
através de um exemplo. Para isto devemos lembrar que  o problema da marcenaria
pode ser modelado segundo um problema de programação linear expresso da seguinte
forma:
Maximizar   Lucro ≡ L = 4x1 + x2,
Sujeito àă 2x1 + 3x2 ≤ 12
2x1 + x2 ≤ 8
x1 ≥ 0, x2 ≥ 0.
Neste momento, resolveremos o PPL acima através de um  raciocínio lógico que
se baseia nos princípios básicos do método simplex. Para isto resolveremos o PPL
respondendo à algumas questões, vejamos.
Solução do modelo:
Questão 1 : Observando o conjunto de restrições do PPL da marcenaria (e a
região viável, caso exista), quantas combinações de valores de x1 e x2   satisfazem tais
restrições?
Resposta :
Exemplos de soluções que satisfazem as restrições:
Note que muitas outras combinações podem ser testadas e muitas destas também
satisfazem as restrições do PPL.
Questão 2 : Qual das combinações x1 e  x2 que além de satisfazer as restrições do
PPL, levam a um maior lucro?
Resposta : para responder a esta questão desenvolveremos os seguintes passos:
1
0 Passo: Admita como solução inicial a mais pessimista, ou seja, não produzir
móvel algum na marcenaria. Neste caso, temos que:
3.6. O MÉTODO SIMPLEX  39
2
0 Passo: (10 Critério)
•   Analisando a função objetivo L = 4x1 + x2  qual sua sugestão com relação a
um primeiro produto a ser produzido? Você começaria a produzir uma certa
quantidade x1  de mesas ou uma certa quantidade x2  de armários? Por que?
•  Note que visando um maior lucro possível é razoável produzir uma quantidade de
mesas maior possível mas para isto é necessário observar que há uma quantidade
limitada de recursos (madeira e mão-de-obra). Deste modo, se não produzimos
armários, os seja, se x2 = 0, temos que as restrições dos rescursos disponíveis
ficam dadas por:
Deste modo:
– Se considerarmos só o recurso madeira, devemos produzir:
– Se considerarmos só o recurso mão-de-obra, devemos produzir:
– Mas para produzir as mesas percebemos que é necessário considerar os dois
recurso simultaneamente de modo que só podemos produzir:
Segue assim que nossa segunda solução para o problema é dada por:
Note que esta solução é viável pois de acordo com a solução desenvolvida todas as
restrições do problema são respeitadas. Veja:
Recapitulando:
1. Partimos de uma solução viável:
para outra que resultou em um lucro maior:
Mas para isto os seguintes critérios foram utilizados:
40 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
(a) Escolheu-se uma variável de decisão para tornar-se positiva tomando como
base aquela que possuía o maior coeficiente na função objetivo Lucro =  L.
(b) Uma vez escolhida a variável de decisão (produto), a produção foi estabele-
cida no maior valor possível, ou seja, à variável de decisão escolhida deu-se
o maior valor positivo sem que a restrições de recursos disponíveis fossem
violadas.
Neste momento é natural formularmos as seguintes questões:
•  A solução encontrada é a melhor de todas?
•  Que critérios lógicos podemos utilizar para responder a esta questão?
Resposta : para responder se a solução encontrada é a melhor de todas pode-
mos nos utilizar de critérios lógicos análogos ao 10 Critério, porém com pequenas
alterações.
3
0 Passo:
De acordo com a solução atual devemos produzir x1  = 4 mesas e nenhum armário
x2  = 0.
Questões :
1. Existe alguma vantagem em também produzir armários para que o lucro seja
ainda maior? Por exemplo, há vantagem em se produzir uma unidade de armário
(passar x1 = 0 para x1 = 1)?
2. Ainda existe recursos disponíveis para se produzir armários? Quais?
Precisamos perceber que havendo vantagem em se produzir armários, será neces-
sário reduzir a produção de mesas pois mesmo havendo madeira disponível para a
produção dos móveis, o recurso mão-de-obra é excasso; segundo a programação (solu-
ção) de produção atual (x1 = 4 mesas e nenhum armário x2 = 0).
Consequências ao Produzir Armários
Como consequência para produzir armários, duas alterações devem ser feitas no
programa de produção:
1. O número inicialmente encontrado para a produção de mesas deve diminuir e isso
diminui o lucro total.
3.6. O MÉTODO SIMPLEX  41
2. A produção de armários, inicialmente nula, pode então tornar-se positiva, provo-
cando assim um aumento do lucro total.
Com base nestas duas alterações simultâneas no lucro; uma redução e um aumento;
o 10 Critério pode ser adaptado como:
•  A variável  x2 (produção de armários) deverá se tornar positiva se o resultado no
lucro for positivo. Ou seja, se:
O  Aumento no lucro L provocado pelo aumento de x2  denotado por Ax2
for maior que
A Redução no lucro L provocado pela diminuição de x1  denotada por Rx1
De modo equivalente, devemos dizer que a variável x2  (produção de armários)
deverá se tornarpositiva se a contribuição líquida para o lucro dada por x2 for
positiva, ou seja, se:
Contribuição líquida dada por x2 = Ax2 −Rx1 > 0.
2
0 Critério (Adaptação do 10)
•  Ao invés de se fazer positiva a variável que tem o maior coeficiente positivo na
função objetivo, faz-se positiva se sua contribuição líquida for positiva.
Após calcular a contribuição líquida para o lucro total dada pela variável x2 quando
a mesma passa de x2 = 0  para x2 = 1 (e consequêntemente x1 = 4 para x1 = 3.5) é
possível verificar que a mesma é negativa em uma unidade, ou seja, que:
Contribuição líquida dada por x2 = 4.(redução em  x1 quando x2  = 1) + 1.(variação em x2)
= 4.(−0.5) + 1.(1) = −1.
Sendo assim, podemos concluir que não há vantagem em se produzir armários e a
solução ótima para o problema da marcenaria recomenda que sejam produzidas:
o que resulta num lucro máximo  L  =  f (x∗1, x
∗
2) = 4x
∗
1 + x
∗
2  = .
42 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
3.6.2 Idéia Resumida sobre o Método Simplex
O método simplex consiste de um procedimento matemático e computacional sistemá-
tico e eficiente para a resolução de problemas de programação linear (PPL). O processo
de solução de um PPL por este método basea-se na resolução de sistemas de equações
lineares considerando as seguintes idéias/questões:
1) Qual o sistema que deve ser resolvido?
2) Qual o próximo sistema a ser resolvido fornecerá uma solução melhor que a
anterior?
3) Como identificar uma solução ótima, uma vez que a tenhamos encontrado?
3.6.3 Método Simplex em Tabelas (Tabular)
As operações do método simplex podem ser organizadas em tabelas chamadas tabelas
simplex . Embora o método simplex tabular não seja a forma ideal de se implementar
em um computador, essa organização é interessante para manipular problemas peque-
nos e rapidamente compreender como o método funciona.
De modo geral, o método simplex pode ser resumido através dos seguintes passos:
Passo 1 : Para cada desigualdade, introduzir as variáveis de folga (obter a forma padrão
do PPL).
Passo 2 : Montar um quadro para os cálculos:
– Colocar na 1a. linha os valores simétricos dos coeficientes da função objetivo,
e
–  Colocar os coeficientes das variáveis (com os respectivos sinais) associados
às restrições do problema.
Passo 3 : Estabelecer uma solução básica inicial:
–  Usualmente atribui-se valor zero às variáveis originais e acha-se valores po-
sitivos para as variáveis de folga.
Passo 4 : Escolher a próxima variável a entrar na base:
–  Escolhe-se a variável não-básica que fornece a maior contribuição líquida
para o aumento da função-objetivo (a que tem maior valor negativo na 1a.
linha da tabela).
3.6. O MÉTODO SIMPLEX  43
Condição de otimalidade - se todas as variáveis que estão fora da base tiverem
coeficientes da função-objetivo nulos ou positivos, a  solução atual é ótima. Se
alguma dessas variáveis tiver coeficiente nulo, significa que ela pode ser introdu-
zida 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.
Passo 5 : (Condição de viabilidade) Escolher a variável que deve deixar a base, reali-
zando o seguinte procedimento:
–  Divide-se os elementos da última coluna pelos correspondentes elementos
positivos da coluna da variável que vai entrar na base.
Obs: Caso não haja elemento algum positivo nessa coluna, o processo 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.
Passo 6 : Usando operações elementares válidas com as linhas da matriz, transformar a
matrix representada na tabela simplex de modo a encontrar a nova solução básica
do problema. Para isto:
–  A coluna da variável básica deverá se tornar um vetor identidade onde o
elemento 1 aparece na linha correspondente à variável que está sendo anulada
(que está passando de básica para não-básica).
Passo 7 : Retornar ao  Passo 4  para iniciar outra iteração.
Exemplo 3.6.1. Resolva o  Problema da Marcenaria  (que produz mesa e armário)
pelo método simplex (tabular).
Exemplo 3.6.2.
Resolva o seguinte PPL pelo método simplex (tabular) e gráfico, observando que o
método simplex é eficiente no sentido de buscar a solução ótima através de um número
mínimo de iterações (percorrendo um número mínimo de vértices).
Maximizar  Z  = 3x1 + 5x2
sujeito a  x1 ≤ 4
x2 ≤ 6
3x1 + 2x2 ≤ 18
x1 ≥ 0, x2  ≥ 0.
Resposta: (x∗1, x
∗
2, x
∗
3, x
∗
4, x
∗
5) = (2, 6, 2, 0, 0). Valor ótimo Z  = 36.
3.6.4 Exercício
Resolva alguns dos PPLs até aqui apresentados através do método Simplex utilizando
o software TORA e a função SOLVER do Excel.
44 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
3.6.5 Solução Inicial Artificial
Como já é possível observar, problemas de PL nos quais todas as restrições são (≤) com
lados direitos não negativos oferecem uma  solução básica inicial viável  conveniente
na qual   todas as   variáveis são   de folga  mas isso não acontece com modelos que
envolvem restrições (=) e/ou (≥).
O procedimento para iniciar a resolução de problemas de PL ‘mal comportados‘
com restrições (=) e/ou (≥) é usar variáveis artificiais que desempenham o papel de
folgas na primeira iteração e então descartá-las legitimamente em iterações posteriores.
Dois métodos fortemente relacionados são apresentados aqui: o método do M-grande
e o   método das duas fases.
Método do M-grande
O método do M-grande começa com um problema de PL na forma de equações. Se
a equação i não tiver uma folga (ou uma variável que possa desempenhar o papel de
uma folga), uma variável artificial, Ri, é adicionada para formar uma solução inicial
semelhante à solução básica na qual todas as variáveis são de folga. Contudo, como as
variáveis artificiais não são parte do modelo original, recebem  punições  muito altas
na função objetivo, o que (a certa altura) as força a ter o valor igual a zero na solução
ótima. Isso sempre ocorrerá se o problema tiver uma solução viável. A regra a seguir
mostra como a punição é designada nos casos de maximização e minimização.
Regra de penalização das variáveis artificiais:
Dado M , um valor positivo suficientemente alto (em termos matemáticos, M  →
∞), o coeficiente na função objetivo de uma variável artificial representa uma  punição
adequada se:
Coeficiente na função objetivo da variável artificial  =

−M, em problemas de maximização
M, em problemas de minimização
Veja agora como funciona o método do M-grande através do modelo de PL abaixo
que não apresenta uma solução básica inicial conveniente:
Exemplo 3.6.3.
min  z  = 4x1 + x2
sujeito a  3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1  ≥ 0, x2  ≥ 0.
Resp.: (x∗1, x
∗
2) = (2/5, 9/5). Valor ótimo: z  = 17/5.
Comentário: A utilização da punição M  tem por objetivo forçar que os valores
das variáveis artificiais na solução ótima sejam nulos, no entanto, se ao menos uma das
3.6. O MÉTODO SIMPLEX  45
variáveis artificiais não for nula na solução ótima tem-se que a solução é inviável (isto
é, o PPL tem restrições inconsistentes).
Resolução do PPL do exemplo 3.6.3
46 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
Método das duas fases
No método do M-grande, a utilização da punição M , que, por definição, deve ser grande
em relação aos coeficientes da função objetivo, pode resultar em erros de arredonda-
mento que podem comprometer a precisão dos cálculos simplex. O método das duas
fases ameniza essa dificuldade eliminando totalmente a constante M . Como o nome
sugere, o método resolve o problema de PL em duas fases: a Fase I tenta achar uma
solução básica viável inicial e, se ela for encontrada, a Fase II é invocada para resolver
o problema original.
Resumo do método das duas fases
•  Fase I
Expresse o problema na forma de equações e adicione as variáveis artificiais ne-
cessárias às restrições (exatamente como no método do M-grande ) para garantir
uma solução básica viável inicial. Em seguida, ache uma solução básica com as
equações resultantes que, independentemente do problemade PL ser de maximi-
zação ou minimização,  sempre minimizará a soma das variáveis artificiais. Se o
valor mínimo da soma for positivo, o problema de PL não tem nenhuma solução
viável, o que encerra o processo (lembre-se de que uma variável artificial positiva
significa que uma restrição original não foi satisfeita). Caso contrário, passe para
a Fase II.
•  Fase II
Use a solução viável da Fase I como uma solução básica viável inicial para o
problema original.
Exemplo 3.6.4.  Resolva o PPL do exemplo 3.6.3  pelo método das duas fases.
3.6. O MÉTODO SIMPLEX  47
3.6.6 Casos Especiais do Método Simplex
Nesta sub-seção pretendemos descrever de forma sucinta sobre as  possíveis soluções
que podem surgir ao resolvermos um PPL pelo   Método Simplex, assim como foi
verificado os casos possíveis de solução  através do Método da Solução Gráfica.
Com este intuito consideraremos quatro casos especiais:
1. Degeneração
2. Soluções ótimas alternativas (ou múltiplas soluções ótimas)
3. Soluções ilimitadas
4. Soluções não existentes (ou inviáveis)
O interesse em estudar estes casos especiais tem duas intenções:
1) Apresentar uma explanação teórica  dessas situações e;
2) Dar uma interpretação  prática  do que esses resultados poderiam significar em
um problema na vida real.
Degeneração
Na aplicação da condição de viabilidade(condição que mantem a viabilidade simul-
tânea das restrições) do método simplex pode ocorrer um empate na razão mínima que
pode ser resolvido arbitrariamente. Quando isso acontece, no mínimo uma variável
básica será zero na iteração seguinte, e diz-se que a nova solução é  degenerada.
Não há nada de alarmante com uma solução degenerada, exceto uma pequena
inconveniência teórica denominada  ciclagem ou  retorno cíclico. A ciclagem pode
ocorrer pelo fato da possibilidade do método simplex entrar em uma sequência de ite-
rações sem nunca melhorar o valor da função objetivo e nunca satisfazer a condição de
otimalidade. Soluções existem para evitar a ciclagem mas são raramente implementa-
dos nos softwares por reduzir drasticamente a velocidade dos cálculos e contando com
o fato de sua ocorrência ser rara na prática.
Um segundo ponto teórico surge do fato da possibilidade de surgir em diferentes
iterações valores idênticos para o valor da função objetivo, apesar de diferenças entre a
categorização das váriáveis básicas e não-básicas. Sendo assim poderíamos perguntar
se poderíamos parar na primeira iteração em que a degeneração aparece ainda que não
seja ótima e a resposta é não porque a solução pode ser temporariamente  degenerada.
E agora, qual a implicação prática da degeneração? O que acontece é que alguns
recursos (restrições) são supérfluos e esta informação pode ser valiosa durante a imple-
mentação da solução. A informação também pode levar à descoberta de irregularidades
na construção do modelo mas infelizmente não há nenhuma técnica de cálculo eficiente
para identificar restrições redundantes diretamente da tabela.
48 CAPÍTULO 3. PROGRAMAÇÃO LINEAR 
Observemos todos estes comentários usando o software Tora para resolver (pelo
simplex tabular e gráfico) o seguinte PPL:
max z  = 3x1 + 9x2
sujeito a x1 + 4x2 ≤ 8
x1 + 2x2 ≤ 4
x1 ≥ 0, x2 ≥ 0.
Soluções ótimas alternativas (ou múltiplas soluções ótimas)
Quando a função objetivo tem direção paralela a uma   restrição vinculadora não
redundante (isto é, uma restrição que é satisfeita como uma equação na solução ótima),
a função objetivo pode assumir o mesmo valor ótimo em mais de um ponto de solução,
o que dá origem a soluções ótimas alternativas (ou múltiplas soluções ótimas). Na
solução gráfica do seguinte modelo de PPL
max z  = 2x1 + 4x2
sujeito a x1 + 2x2 ≤ 5
x1 + x2 ≤ 4
x1 ≥ 0, x2 ≥ 0.
,
é possível observar isto e, na solução Simplex tabular, é possível observar que em uma
certa iteração o valor do coeficiente de uma determinada variável não básica na linha
de z  é zero, o que significa que esta determinada variável não básica pode entrar na
solução básica sem alterar o valor de  z , mas apenas causando mudança nos valores das
variáveis.
O método Simplex apresenta apenas dois pontos extremos de todas as possíveis
soluções e, na prática, soluções ótimas alternativas permitem, por exemplo, escolhas
convenientes de acordo com o interesse atual do mercado. Por exemplo, na solução
ótima do PPL acima, uma das soluções aponta que apenas um dos produtos podem
ser produzidos e uma outra solução permite que dois produtos possam ser produzidos
sem alterar o valor ótimo. Neste último caso, numa situação de mix de produtos,
pode haver vantagem em produzir dois produtos em vez de um para poder enfrentar a
concorrência de mercado.
Solução ilimitada
Na resolução do seguinte PPL
max z  = 2x1 + x2
sujeito a x1 − x2 ≤ 10
2x1 ≤ 40
x1 ≥ 0, x2 ≥ 0.
é possível observar a possibilidade do valor de uma variável poder ser aumentado in-
definidamente sem violar nenhuma restrição, o que significa que a região de soluções é