APOSTILA 4 - PESQUISA OPERACIONAL

Prévia do material em texto

Universidade Federal de Viçosa 
Departamento de Informática 
 
Prof. Mauro Nacif Rocha 
Prof. Luiz Aurélio Raggi 
Prof. Heleno do Nascimento Santos 
 
 
Fevereiro de 2005 
INF-280 
Pesquisa Operacional I 
 
 
Conteúdo: 
Programação Linear 
Programação em Redes 
 ii 
 
ASPECTOS GERAIS DA PESQUISA OPERACIONAL ........................................................................................ 1 
EXEMPLOS DE ALGUNS PROBLEMAS COMUNS DA P.O............................................................................................... 5 
PARTE I – PROGRAMAÇÃO LINEAR ................................................................................................................. 8 
EXEMPLOS DE MODELOS PARA ALGUNS PROBLEMAS CLÁSSICOS DE PROGRAMAÇÃO LINEAR .................................. 13 
PROBLEMAS PARA MODELAGEM ............................................................................................................................ 17 
SOLUÇÃO DE UM PROBLEMA DE PROGRAMAÇÃO LINEAR – INTERPRETAÇÃO GEOMÉTRICA ...................................... 19 
CASOS ENCONTRADOS NA RESOLUÇÃO GRÁFICA ................................................................................................... 23 
O MÉTODO SIMPLEX.......................................................................................................................................... 27 
MODELO MATEMÁTICO E FORMA PADRÃO DE UM PPL............................................................................................. 27 
DEFINIÇÕES BÁSICAS ............................................................................................................................................. 30 
TEOREMAS FUNDAMENTAIS ................................................................................................................................... 35 
O ALGORITMO SIMPLEX ........................................................................................................................................ 37 
ALGORITMO SIMPLEX – MÉTODO DAS DUAS FASES ................................................................................................ 47 
ELEMENTOS DE PÓS-OTIMIZAÇÃO................................................................................................................ 53 
MUDANÇA NO VETOR C.......................................................................................................................................... 55 
MUDANÇA NO VETOR B.......................................................................................................................................... 56 
DUALIDADE .......................................................................................................................................................... 57 
PARTE II – PROGRAMAÇÃO EM REDES......................................................................................................... 63 
INTRODUÇÃO ........................................................................................................................................................ 63 
INTRODUÇÃO À TEORIA DE GRAFOS ............................................................................................................ 65 
UMA BREVE HISTÓRIA DA TEORIA DOS GRAFOS ..................................................................................................... 65 
CONCEITOS BÁSICOS DA TEORIA DE GRAFOS.......................................................................................................... 68 
FLUXOS EM REDE ............................................................................................................................................... 74 
FORMULAÇÃO GERAL (CLÁSSICA) PARA PROBLEMAS DE FLUXOS EM REDE ............................................................. 75 
O PROBLEMA DE FLUXO DE CUSTO MÍNIMO (PFCM).............................................................................................. 79 
O PROBLEMA DE TRANSPORTE (PT) ....................................................................................................................... 87 
O PROBLEMA DE DESIGNAÇÃO (PD) ...................................................................................................................... 94 
O PROBLEMA DO CAMINHO MAIS CURTO (PCMC) ............................................................................................... 100 
O PROBLEMA DE FLUXO MÁXIMO (PFM) ............................................................................................................. 104 
O PROBLEMA DA ÁRVORE GERADORA MÍNIMA (AGM) ........................................................................................ 111 
O PROBLEMA DE STEINER EM GRAFOS NÃO DIRECIONADOS .................................................................................. 115 
REDES PERT / CPM............................................................................................................................................ 117 
REDES PERT....................................................................................................................................................... 117 
REDES PERT/CPM.............................................................................................................................................. 121 
BIBLIOGRAFIA................................................................................................................................................... 125 
 
 1 
Aspectos Gerais da Pesquisa Operacional 
 
1. Introdução e Histórico 
 
Durante a II Guerra Mundial, líderes militares da Inglaterra e dos Estados Unidos requisita-
ram um grupo de cientistas de diversas áreas de conhecimento para analisarem alguns problemas 
militares. Entre esses problemas citam-se: desenvolvimento, operação e localização de radares, ge-
renciamento e controle de navios de apoio, planejamento de ataques aéreos, lançamento de bombas 
contra submarinos, defesa das comunidades européias contra ataques aéreos inimigos, abastecimen-
to de tropas com munições e alimentos, operações de mineração, etc. A aplicação de métodos ma-
temáticos e científicos para ajudar as operações militares foi chamada “Operational Research” ou 
“Operations Research”. 
 
1759 (Quesney), 
1874 (Walras) 
Modelos primitivos de programação matemática. 
1873 (Jordan), 
1896 (Minkowsky), 1903 (Farkas) 
Bases matemáticas para os modelos lineares. 
1920 (Markov) Modelos dinãmicos. 
192* (periódicos de negócios e en-
genharia industrial) 
Sugestões inovadoras para controle econômico de esto-
ques. 
1920 (Erlang) Estudos pioneiros dos fenômenos das filas de espera. 
1937 (Von Neumann), 1939 (Kan-
torovich) 
Modelos econômicos mais sofisticados. 
1938 (RAF – viabilidade dos siste-
mas de radar) 
Operational Research – RESEARCH into (military) 
OPERATIONS 
1940 (tomada da França pelos ale-
mães) 
Maior conquista da OR na II Guerra. 
1947 (Dantzig) Primeira formulação abstrata de um problema de progra-
mação linear. 
a partir de 1947 Aplicações na engenharia, economia, controle de estoque, 
análise de tráfego aéreo, agricultura, comunicação, plane-
jamento rural e urbano, distribuição de energia e outros 
 
Obs.: U.K. / Europa: Operational Research 
 E.U.A.: Operations Research 
 
 
 2 
2. Definição 
 
“Pesquisa Operacional é o uso do método científico com o objetivo de prover departamentos exe-
cutivos de elementos quantitativos para a tomada de decisões, com relação a operações sob seu 
controle” (Kittel, 1947). 
 
“A Pesquisa Operacional é a aplicação do método científico, por equipes multidisciplinares, a pro-
blemas envolvendo o controle de sistemas organizados de forma a fornecer soluções que melhor 
interessam a determinada organização” (Ackoff,1968). 
 
“Pesquisa Operacional é uma metodologia de estruturar processosaparentemente não estruturados 
por meio da construção de modelos. Utiliza um conjunto de técnicas quantitativas com o intuito de 
resolver os aspectos matemáticos dos modelos” (Ehrlich, 1991). 
 
Hoje, o termo operations research, ou pesquisa operacional, significa “um método científico 
para tomada de decisão, que busca determinar como melhor planejar e operar um sistema, usual-
mente sob condições que requerem alocação de recursos escassos”. 
 
 
3. A Metodologia da Pesquisa Operacional 
 
Geralmente a atividade de uma equipe de P.O. envolve as seguintes fases: 
 
• identificação do problema; 
• construção de um modelo; 
• obtenção da solução; 
• teste do modelo e avaliação da solução; 
• implantação e acompanhamento da solução. 
 
 Deve-se salientar que tais fases não são distintas, superpondo-se e interagindo entre si, na 
tentativa de se obter uma melhor identificação entre o modelo e o real. Quando a pesquisa opera-
cional é usada para resolver um problema de uma organização, o seguinte procedimento, poderá ser 
seguido: 
 
Passo 1 - Identificação e formulação do problema 
 
 Em primeiro lugar deve ser definido claramente o problema da organização, incluindo a es-
pecificação dos objetivos e as partes da organização que devem ser estudadas antes que o problema 
possa ser resolvido. 
 
Passo 2 - Observação do sistema 
 
 Dados devem ser coletados para estimar valores de parãmetros que afetam o problema da 
organização. Estes valores são usados para desenvolver e avaliar o modelo matemático para o pro-
blema. 
 
Passo 3 - Formulação do modelo matemático para o problema 
 
 Consiste no desenvolvimento do modelo matemático para o problema. Geralmente, existem 
várias técnicas que podem ser aplicadas na solução dos modelos matemáticos. A técnica adequada é 
selecionada em função das características do modelo representativo do problema. Algumas situa-
ções, no entanto, são tão complexas que não existem modelos analíticos tratáveis que possam repre-
 3 
sentá-las. Quando isso acontece é possível desenvolver modelos de simulação e usar a capacidade 
dos computadores para aproximar o comportamento desses sistemas. 
 
Passo 4 - Verificação do modelo e uso do modelo para predição 
 
 Verifica-se se o modelo matemático proposto para o problema é uma representação fidedig-
na da realidade. Os dados coletados durante a observação do problema podem ser usados para a va-
lidação do modelo na situação corrente. 
 
Passo 5 - Selecionar uma alternativa aceitável 
 
 Dado o modelo do problema e um conjunto de alternativas (soluções viáveis) deve-se esco-
lher aquela (se existir) que melhor atende aos objetivos da organização. Em alguns casos, a seleção 
da melhor alternativa possível é um problema de difícil solução e, nesses casos, aceita-se uma “boa” 
alternativa. 
 
Passo 6 - Apresentação dos resultados e conclusões 
 
 A partir da definição do modelo e das alternativas determinadas para o problema são feitas 
as recomendações para os gerentes das organizações para que eles possam tomar as decisões que 
melhor atendem os objetivos buscados. 
 
Passo 7 - Implementação e avaliação das recomendações 
 
 Se a organização aceita o estudo realizado e as recomendações feitas, parte-se para a fase de 
implementação da solução, a qual deve ser constantemente monitorada, e atualizada dinamicamen-
te, fazendo-se mudanças quando necessárias. 
 
 
4. Áreas de aplicação 
 
 Segundo trabalhos apresentados em reuniões da Sociedade Brasileira de Pesquisa Operacio-
nal (SOBRAPO), citam-se abaixo algumas áreas onde a P.O. foi aplicada com algum sucesso e on-
de se observa a grande variedade dessas aplicações: 
 
• administração 
• agropecuária 
• economia e planejamento econômico 
• educação e saúde 
• energia 
• engenharia 
• forças armadas 
• investimentos e finanças 
• localização-armazenamento-distribuição 
• planejamento e controle da produção 
• planejamento urbano e regional 
• recursos hídricos 
• siderurgia 
• telecomunicações 
• transporte 
 
 
 4 
5. Técnicas aplicadas 
 
 Os trabalhos de PO desenvolvidos e submetidos para apresentação em congressos e para pu-
blicação revistas científicas envolvem a utilização das seguintes técnicas: 
 
• Análise e previsão de séries temporais 
• Controle e qualidade 
• Estatística 
• Teoria dos grafos 
• Otimização 
• Programação matemática 
• Processos estocásticos e teorias das filas 
• Simulação 
• Teoria da decisão e teoria dos jogos 
 
 Estas técnicas permitem que se resolva uma variedade enorme de problemas, dentre os quais 
são típicos: 
 
• Alocação de recursos 
• Localização e distribuição da produção 
• Estoque 
• Substituição e reposição de equipamentos 
• Seqüenciamento e coordenação de tarefas 
• Determinação de caminhos em rede 
• Situações de competição (teoria dos jogos) 
• Busca de informação 
• Roteamento de veículos 
• Fluxos em rede 
• Problemas de características híbridas 
 
6. Surgimento e desenvolvimento da PO no Brasil 
 
 O início da P.O. no Brasil se deu aproximadamente uma década após sua implantação na 
Grã-Bretanha e nos Estados Unidos. Assim, já nos meados da década de 50, professores com for-
mação em Engenharia, Matemática e/ou Estatística, entusiasmados com as novas técnicas relacio-
nadas a P.O. que aqui chegavam pela difusão natural do conhecimento humano, começaram a for-
mar equipes de P.O. nas universidades e instituições de ensino (ITA, PUC, COPPE-UFRJ, UFPB, 
UNICAMP, UFSC, UFMG, UFV, etc.), reproduzindo-se e induzindo a formação de equipes em 
conjunto com as empresas (PETROBRÁS, ELETROBRÁS, USIMINAS, CSN, EMBRAPA, 
SOUZA CRUZ, TELEBRÁS, etc.), bem como a formação de consultorias nas grandes cidades. 
 Atualmente, vê-se com certo otimismo as perspectivas da P.O. no Brasil e, em particular, na 
Agricultura, Sistemas de Produção e Engenharia de Alimentos, baseando-se nos seguintes fatores: 
• A crise como elemento propulsor (escassez de recursos); 
• A explosão da informática; 
• Massa crítica existente de analistas de P.O.; 
• Integração universidade × empresa; 
• Seminários de P.O. aplicada à agropecuária; 
• Existência de cursos de P.O. nas universidades brasileiras; 
• Cursos e pesquisas em andamento na COPPE, UNICAMP, UFPb, UFSc, EMBRAPA, etc. 
 5 
Exemplos de Alguns Problemas Comuns da P.O. 
Problema do Caminho Mínimo (PCM) 
 
 
Objetivos: determinar a rota de menor caminho (distância, tempo 
ou custo) existente entre um ponto de origem (cidade, endereço, 
computador, objeto etc.) e um ponto de destino. 
 
 
 
 
 
 
 
 
Problemas de Localização de Facilidades 
 
 
Objetivos: determinar a localização e capacidade das faci-
lidades (restaurantes, depósitos, antenas de rádio etc.) de 
forma a suprir a demanda da região toda com um custo 
mínimo e/ou lucro máximo (considerando um determinado 
período). Cada facilidade possui normalmente um custo 
fixo de instalação e custos variáveis de operação. 
 
 
 
 
 
 
 
 
 
 
 
 
Problema da Mochila 
Rolando Caio da Rocha, um exuberante alpinista, está se preparando para uma longa escalada nos 
Alpes. Ele consegue levar até W quilos em sua mochila. Ele tem N diferentes tipos de itens que po-
de incluir em seu fardo, e cada unidade de item j pesa wj quilos. Para cada item j, ele calculou um 
valor numérico Rj representando o valor de sobrevivência de cada unidade do item. Como exemplo, 
se ele levar cinco unidades do item 3 e sete unidades do item 9, o “valor” para ele desta seleção na 
mochila é 5R3 + 7R9. O problema do Rolando é escolher o número de cada tipo para incluir em sua 
mochila. 
 6 
Escolha da Mistura para Rações 
 
 Grão 1 Grão 2 Grão 3 Necessidades mínimas 
Nutriente A 2 3 7 1250 
Nutriente B 1 1 0 250 
Nutriente C 5 3 0 900 
NutrienteD 0,6 0,25 1 232,5 
$/peso 41 35 96 
Objetivos: formular uma ração formada a partir da mistura dos grãos que atenda às necessidades 
mínimas e máximas de nutrientes e tenha um custo mínimo. 
 
Bin-packing / Cutting Stock 
 
Barra (bin) = 4100mm 
Demanda (mm) 
3100 
1930 
1850 
850 
850 
795 
639 
 
Fornecimento de Produtos através de uma Rede de Transportes 
 
 
Fornecimentos
disponíveis
Necessidades
de demanda
Usinas Depósitos
S1
S2
S3
Sm
Dn
D3
D2
D1
 
Objetivos: determinar a quantidade do produto que cada fornecedor deve enviar para cada depósito, 
de forma que o custo total do transporte seja mínimo, que cada depósito tenha sua demanda atendi-
da, e que nenhum depósito estoure sua capacidade de fornecimento. 
 
 
 
 
 
Objetivos: determinar a quantidade mínima possível de 
barras para que sejam cortados todos os pedaços neces-
sários para suprir a demanda. 
 7 
Problemas de Produção 
 Recursos Especificações Atividades 
INSUMOS PRODUTOS 
Máquinas 
Ferramentas 
Capital 
Matéria prima 
Mão-de-obra 
 
 
⇔ 
 
 
Decisões 
 
 
⇔ 
Produto 1 
Produto 2 
. 
. 
Produto n 
CUSTOS RECEITA 
Objetivos: determinar as atividades que devem ser realizadas ou produzidas de forma a maximizar o 
lucro ou minimizar o custo de produção, levando-se em conta a quantidade máxima disponível para 
cada insumo. 
 
O Problema de Designação (caso particular do problema de transporte) 
 
Indivíduos ou máqui-
nas (n) 
Custos cij Tarefas a serem execu-
tadas (n) 
 
1 1 
 
2 2 
 
3 3 
Objetivos: minimizar o custo total para executar um conjunto de tarefas, onde cada tarefa deve ser 
executada por uma única máquina, e cada máquina executa uma única tarefa. 
 
 8 
Parte I – Programação Linear 
 
1. O significado da expressão 
 
“PROGRAMAÇÃO” ⇒ alocação de itens ou entidades 
 
“LINEAR” ⇒ relativo a funções, equações ou inequações lineares 
 
 
2. O problema geral 
 
Recursos escassos de-
vem ser 
repartidos entre deman-
das competitivas 
 
 
⇔ 
Decisões 
são interligadas na 
tomada de decisão 
 
 
⇔ 
Demandas competem 
entre si na 
procura dos 
recursos escassos 
 
Objetivos: 
 
• Otimizar a distribuição dos recursos limitados no atendimento às demandas competitivas; 
• Maximizar lucros ou o uso dos recursos; 
• Minimizar custos, sobras, tempos ou distâncias. 
 
 
 9 
3. Fases na solução de um problema de pesquisa operacional 
 
FLUXOGRAMA 
 
 
 
 
 
 
 
 
 
FORMULAÇÃO 
DO 
PROBLEMA 
 
 
 
 
 
 
 
OBTENÇÃO 
DO 
MODELO 
 
 
 
 
 
 
 
DEFINIÇÃO 
DO MÉTODO 
DE SOLUÇÃO 
 
 
 
 
 
 
 
 
 
 
OBTENÇÃO 
E PREPARO 
DOS DADOS 
 
 
 
EXPERIÊNCIA 
 
 
 
 
RESOLUÇÃO 
DO 
PROBLEMA 
 
 
 
 
INTERPRETAÇÃO 
DOS 
RESULTADOS 
COMPARAÇÃO 
COM A 
REALIDADE 
 
 
 
IMPLEMENTAÇÃO 
DA 
SOLUÇÃO 
 
 
 
 
 10 
4. Modelagem de problemas 
 
MODELOS SÃO REPRESENTAÇÕES DA REALIDADE 
 
 
 
 
 
 
 
 
 
 
 
 
GRANDE NÚME-
RO DE VARIÁ-
VEIS 
 SELEÇÃO DAS VA-
RIÁVEIS 
PRINCIPAIS 
 SIMPLIFICAÇÃO 
DA 
REALIDADE 
 
SISTEMA INTER-
RELACIONAMENTO 
 MODELO 
 
 
5. Modelos matemáticos 
 
Os modelos matemáticos são modelos simbólicos - o sistema real é representado por EQUAÇÕES 
E EXPRESSÕES MATEMÁTICAS que descrevem suas propriedades relevantes. 
 
n DECISÕES QUE SÃO 
QUANTIFICÁVEIS E 
INTERRELACIONADAS 
 n VARIÁVEIS DE DECISÃO 
(x1, x2, … , xn) 
 
REPRESENTA A MEDIDA 
DE EFICIÊNCIA DO 
SISTEMA 
 FUNÇÃO OBJETIVO 
Z = f(x1, x2, … , xn) 
 
SÃO RESTRIÇÕES AOS 
VALORES DAS VARIÁVEIS 
DE DECISÃO 
 REPRESENTADAS POR EQUA-
ÇÕES OU INEQUAÇÕES MA-
TEMÁTICAS 
 
É A REALIDADE É UMA APROXIMAÇÃO 
 
 VALIDADE 
 
 ASSOCIADA AO 
GRAU DE COR-
RELAÇÃO 
 
 
 
 11 
6. Expressão matemática de um modelo de programação linear 
 
OBJETIVO 
 
Determinar os valores das variáveis x1, x2, … , xn que otimizam (maximizam ou minimizam) a fun-
ção linear 
 
Z = c1 x1 + c2 x2 + … + cn xn, 
 
obedecendo às seguintes RESTRIÇÕES: 
 
 
a11x1 + a12x2 + … + a1nxn ≤≤≤≤, =, ≥≥≥≥ b1 
a21x1 + a22x2 + … + a2nxn ≤≤≤≤, =, ≥≥≥≥ b2 
 … 
am1x1 + am2x2 + … + amnxn ≤≤≤≤, =, ≥≥≥≥ bm 
 
e de forma que as variáveis sejam NÃO NEGATIVAS, ou seja: 
 
xn ≥≥≥≥ 0, xn ≥≥≥≥ 0, … xn ≥≥≥≥ 0. 
 
Temos que cj, aij e bi são constantes conhecidas, para todo i e todo j. 
 
Os parãmetros e variáveis do modelo são: 
 
Z - Medida de eficiência do sistema (chamada de Função Objetivo ou F.O.); 
xj - Nível da atividade j (variável de decisão); 
cj - Taxa de contribuição unitária da atividade j; 
bi - Disponibilidade do recurso i; 
aij - Coeficiente tecnológico (quantidade i / consumido por j) 
n - Número de atividades no modelo; 
m - Número de restrições no modelo. 
 
 
7. Construção de um modelo de programação linear 
 
ETAPAS A SEGUIR PARA CONSTRUIR UM MODELO DE PL 
 
1. Definição das atividades 
 
Definir as atividades (xj) e escolher uma unidade de medida para o seu nível. 
 
2. Definição dos recursos 
 
Determinar os recursos consumidos e escolher a unidade de medida conveniente. 
 
3. Determinação das condições externas 
 
Determinar a quantidade de recurso disponível (bi). 
 
4. Cálculo dos coeficientes insumo/produção 
 
Determinar a relação entre atividades e recursos (aij). 
 12 
 
5. Construção do modelo 
 
Associar x1, x2, … , xn às n atividades; 
Escrever as equações de balanceamento por recurso; 
Indicar o uso dos recursos; 
Estabelecer a função objetivo como medida de eficiência. 
 
 13 
Exemplos de Modelos para Alguns Problemas Clássicos de Pro-
gramação Linear 
 
Escolha da Mistura para Rações 
 
 Grão 1 Grão 2 Grão 3 Necessidades mínimas 
Nutriente A 2 3 7 1250 
Nutriente B 1 1 0 250 
Nutriente C 5 3 0 900 
Nutriente D 0,6 0,25 1 232,5 
$/kg 41 35 96 
 
Seja: x1 = qtde. (kg) do Grão 1 usada na ração 
 x2 = qtde. (kg) do Grão 2 usada na ração 
 x3 = qtde. (kg) do Grão 3 usada na ração 
 
Custo total da ração: 41x1 + 35x2 + 96x3 
 
Para atender às necessidades mínimas para cada nutriente, devemos ter: 
 
2x1 + 3x2 + 7x3 ≥ 1250,0 (Nutriente A) 
x1 + x2 ≥ 250,0 (Nutriente B) 
5x1 + 3x2 ≥ 900,0 (Nutriente C) 
0,6x1 + 0,25x2 + x3 ≥ 232,5 (Nutriente D) 
 
Queremos obter uma ração que tenha um custo mínimo. Portanto, o modelo completo fica assim: 
 
Minimizar 41x1 + 35x2 + 96x3 (Função Objetivo ou F.O.) 
 
Sujeito a: (Restrições) 
 
2x1 + 3x2 + 7x3 ≥ 1250,0 (Nutriente A) 
x1 + x2 ≥ 250,0 (Nutriente B) 
5x1 + 3x2 ≥ 900,0 (Nutriente C) 
0,6x1 + 0,25x2 + x3 ≥ 232,5 (Nutriente D) 
 
e: x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 
 14 
Problema de Produção 
A empresa Nova Linha produz artigos de vidro de alta qualidade: janelas e portas, em três seções de 
produção: 
 
� Seção de Serralharia: para produzir as estruturas de alumínio 
� Seção de Carpintaria: para produzir as estruturas de madeira 
� Seção de Vidro e Montagem: para produzir vidro e montar as portas e janelas 
 
Devido à diminuição dos lucros, o gerente geral decidiu reorganizar a produção, e propõe produzir 
só 2 produtos que têm uma melhor aceitação entre os clientes. 
Estes produtos são: 
 
� Produto 1: uma porta de vidro com estrutura de alumínio 
� Produto 2: uma janela grande com estrutura de madeiraO Departamento de Marketing concluiu que a empresa pode vender tanto de qualquer dos dois 
produtos, tendo em conta a capacidade de produção disponível. Como ambos os produtos partilham 
a capacidade de produção da seção 3, o dono solicitou ao gerente de produção da empresa a 
resolução deste problema. 
 
O gerente então levantou os seguintes dados: 
 
� a capacidade de produção por minuto de cada seção, a ser utilizada para produzir uma 
unidade de cada produto 
� os lucros unitários para cada produto 
 
 
Capacidade por unidade 
de produção
5
2
2
0
Produto 2
1833
3
0
1
Produto 1
Lucro unitário
(em R$)
122
41
Capacidade 
disponível
Seção Nº
Capacidade por unidade 
de produção
5
2
2
0
Produto 2
1833
3
0
1
Produto 1
Lucro unitário
(em R$)
122
41
Capacidade 
disponível
Seção Nº
 
 
 
Modelo completo: 
 
 
Maximizar Z = 3x1 + 5x2, 
sujeito a
x 1 ≤≤≤≤ 4
2x 2 ≤≤≤≤ 12
3x1 + 2x 2 ≤≤≤≤ 18
x1 ≥≥≥≥ 0, x2 ≥≥≥≥ 0
 
 
 
 15 
Problema da Mochila 
 
Rolando Caio da Rocha, um exuberante alpinista, está se preparando para uma longa escalada nos 
Alpes. Ele consegue levar até W quilos em sua mochila. Ele tem N diferentes tipos de itens que po-
de incluir em seu fardo, e cada unidade de item j pesa wj quilos. Para cada item j, ele calculou um 
valor numérico Rj representando o valor de sobrevivência de cada unidade do item. O problema do 
Rolando é escolher o número de cada tipo para incluir em sua mochila. 
 
Modelo: 
F.O.: Max. R1x1 + R2x2 + ... + Rjxj + ... + RNxN 
s.a.: w1x1 + w2x2 + ... + wjxj + ... + wNxN ≤ W 
 xj ≥ 0 
 
ou: 
 
Max. ∑
=
N
j
jj xR
1
 
 
s.a.: 
0
1
≥
≤∑
=
j
N
j
jj
x
Wxw
 
 16 
Cutting Stock 
 
Tamanho (mm) Quantidade 
3100 26 
1530 71 
850 47 
Tamanho da Barra: 6000 mm 
 
Temos então as seguintes possibilidades de corte: 
 x1 x2 x3 x4 x5 x6 Demanda 
3100 1 1 0 0 0 0 26 
1530 1 0 3 2 1 0 71 
850 1 3 1 3 5 7 47 
Sobra: 520 350 560 390 220 50 
 
Sendo NB = No total de barras de 6000 mm que serão cortadas, 
 xj = No de barras de 6000 mm que serão cortadas 
 segundo o padrão de corte j, 
 
F.O.: Min. NB = x1 + x2 + x3 + x4 + x5 + x6 
s.a.: 
x1 + x2 ≥ 26 
x1 + 3x3 + 2x4 + x5 ≥ 71 
x1 + 3x2 + x3 + 3x4 + 5x5 + 7x6 ≥ 47 
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0 
 
Se: aij = No de pedaços de tamanho i que serão cortados no padrão j, 
 bi = demanda de pedaços i, 
 m = No de tamanhos diferentes (linhas), 
 n = No de padrões de corte diferentes (colunas). 
Min. NB = ∑
=
n
j
jx
1
 
s.a. i
n
j
jij bxa ≥∑
=1
, i = 1, 2, ..., m 
 xj ≥ 0 e inteiro, j = 1, 2, ..., n 
 
 17 
Problemas para Modelagem 
 
Problema de Produção e Alocação de Recursos 
Um fazendeiro deseja determinar que área de sua propriedade deve plantar milho e feijão para ma-
ximizar o seu lucro, e informa o seguinte: 
a) o fazendeiro dispõe de uma área máxima de 8 alqueires para o plantio das 2 culturas, 100 m3 de 
água para irrigação por semana, e a semente de feijão lhe permite um plantio de 4 alqueires no 
máximo; 
b) o lucro por alqueire plantado com milho é de R$200,00 e plantado com feijão é de R$150,00; 
c) cada alqueire plantado com milho requer 10m3 de água por semana, e com feijão 20m3; 
d) por questões pessoais, ele deseja plantar no máximo 2/3 da área total com milho. 
 
Formule o problema como um PPL. 
Problema de Alocação de Recursos 
Em uma determinada repartição, existem m máquinas disponíveis para realizar determinadas tarefas 
ou fabricar determinados produtos. Cada máquina, devido à idade e ao fabricante, pode ser mais ou 
menos adequada que as outras para fabricar um determinado produto, bem como ter um custo de 
operação próprio (consumo de energia, manutenção etc.). Seja: 
n o número de produtos que precisam ser fabricados nessas máquinas, 
dij o tempo necessário para fabricar o produto j na máquina i, 
xij o número de unidades de j produzido na máquina i, 
ai o tempo disponível para a máquina i, 
bj o número de unidades de j que precisam ser produzidos, e 
cij o custo para fabricar uma unidade do produto j na máquina i. 
 
Modele este PPL de forma a obter uma produção de custo mínimo. 
Problema de Alocação de Transportes 
O expedidor de vôos, Eli Cóptero, da companhia Frete Aéreo Cauda Alta Ltda., que opera de um 
terminal central, tem 8 aviões do Tipo 1, 15 aviões do Tipo 2 e 11 aviões do Tipo 3 disponíveis para 
os vôos de hoje. A capacidade de cada avião é de 45t, 7t e 5t, respectivamente. O Sr. Cóptero deve 
expedir aviões para as cidades A, B e C. A quantidade mínima de cada produto que deve ser envia-
da para cada cidade é de 20t, 28t e 30t, respectivamente. Cada avião pode voar somente uma vez 
por dia. 
 
O custo de enviar um avião do terminal a cada cidade é dado pelo seguinte quadro: 
 
 Tipo 1 Tipo 2 Tipo 3 
Cidade A 23 15 1,4 
Cidade B 58 20 3,8 
Cidade C 64 24 4,2 
 
Denote por xij o número de aviões do tipo i enviado para a Cidade j (x1A, x1B, x1C, x2A etc.). Formule 
um modelo de PL para esse problema. 
 18 
Problema de Planejamento de Tarefas 
Uma determinada região está sendo ameaçada pela ruptura de uma barragem e deve ser evacuada 
em, no máximo, 10 horas. São no total 8.000 homens, 7.900 mulheres e 1.850 crianças a transpor-
tar. Cada pessoa poderá levar até 10 quilos de bagagem pessoal, Toda a região foi isolada e só cir-
culam veículos autorizados para que se evitem acidentes e engarrafamentos. Para efetuar a evacua-
ção estão disponíveis os seguintes meios: 
 
 
Veículo de 
6 ton. do 
Exército 
Veículo de 
¼ ton. do 
Exército 
Helicóptero Ônibus Microônibus Veículo de Passeio 
Quantidade 
de Unidades 
Disponíveis 
10 20 15 10 5 60 
Capacidade de 
Transporte 20 pessoas 5 pessoas 10 pessoas 30 pessoas 15 pessoas 5 pessoas 
Capacidade 
para bagagem 1 ton. 20 kg 50 kg 1 ton. 500 kg 100 kg 
Custo por 
Viagem 10 u.m. 4 u.m. 75 u.m. 5 u.m. 3 u.m. 2 u.m. 
Tempo de 
Viagem 1 h 45 min. 10 min. 45 min. 30 min. 30 min. 
 
Para minimizar o pânico, as crianças deverão viajar acompanhadas por suas mães. Existem 10 famí-
lias com 5 filhos, 25 com 4 filhos, 150 com 3, 450 com 2 e 350 com 1. Os carros de passeio só po-
derão fazer uma viagem de evacuação, ficando, por segurança, retidos fora da área de perigo. 
 
Formular o programa de evacuação que minimize os custos finais da operação. 
 19 
Solução de um Problema de Programação Linear – 
Interpretação Geométrica 
 
Representação no espaço de soluções – duas dimensões (variáveis). 
 
Exemplo 1 
 
(1) maximizar 12x1 + 15x2 
sujeito a: 
(2) 4x1 + 3x2 ≤ 12 
(3) 2x1 + 5x2 ≤ 10 
(4) x1 ≥ 0 e x2 ≥ 0 
 
 
 
Solução Ótima: ponto b, onde x1 = 15/7, x2 = 8/7 e 12x1 + 15x2 = 300/7 
 
 20 
Exemplo 2 
 
Por determinação médica, um jovem precisa fazer algum tipo de atividade física em uma academia. 
Por questões pessoais, ele escolheu fazer natação e/ou pólo aquático. Ele sabe que: 
• Uma hora de aula de natação custa R$8,00; 
• Uma hora de aula de pólo custa R$5,00; 
• Seu orçamento lhe permite dispor de 100 reais mensais para as atividades de academia; 
• Seus afazeres escolares lhe dão liberdade de gastar mensalmente, no máximo, 18 horas e 40.000 
calorias de sua energia para essas atividades; 
• Cada hora de aula de pólo consome 3.300 calorias, e de natação consome 1.600 calorias; 
• Ele não tem preferência por nenhuma dessas duas atividades. 
Como ele deve planejar as suas atividades físicas para obter o número máximo de horas-aula, con-
siderando o limite dos recursos que tem? Modele o problema como um problema de programação 
linear (PPL). 
 
x1 � Horas-aula de natação; x2 � Horas-aula de pólo aquático 
 
 máx. x1+ x2 (1) 
s.a.: 
 x1 + x2 ≤ 18 (2) 
 8x1 + 5x2 ≤ 100 (3) 
 1600x1 + 3300x2 ≤ 40000 (4) 
 
 
 
(1) (2) 
(3) (4) 
 21 
Exemplo 3 
 
Um fazendeiro deseja determinar que área de sua propriedade deve plantar milho e feijão para ma-
ximizar o seu lucro, e informa o seguinte: 
a) o fazendeiro dispõe de uma área máxima de 8 alqueires para o plantio das 2 culturas, 100 m3 de 
água para irrigação por semana, e a semente de feijão lhe permite um plantio de 4 alqueires no 
máximo; 
b) o lucro por alqueire plantado com milho é de R$200,00 e plantado com feijão é de R$150,00; 
c) cada alqueire plantado com milho requer 10m3 de água por semana, e com feijão 20m3; 
d) por questões pessoais, ele deseja plantar no máximo 2/3 da área total com milho. 
 
x1 � Qtde. de alqueires plantados com milho 
x2 � Qtde. de alqueires plantados com feijão 
 
máx. 200x1 + 150x2 
s.a.: x1 + x2 = 8 (1) 
 x2 ≤ 4 (2) 
 x1 ≤ 16/3 (3) 
 10x1 + 20x2 ≤ 100 (4) 
 
 
 22 
Exemplo 4 
 
Suponha que, por motivos justificáveis, uma certa dieta alimentar esteja restrita a leite desnatado e 
uma salada de composição bem conhecida. Sabendo-se ainda que os requisitos nutricionais serão 
expressos em termos de vitamina A e cálcio e controlados por suas quantidades mínimas (em mili-
gramas). A tabela abaixo resume a quantidade de cada nutriente em disponibilidade nos alimentos e 
a sua necessidade diária para a boa saúde de uma pessoa. 
 
Nutriente Leite (copo) Salada (500g) Requisito Nutricional 
Mínimo 
Vit. A 2 mg 50 mg 11 mg 
Cálcio 50 mg 10 mg 70 mg 
Custo/unid. R$ 2,00 R$ 1,20 
 
 
sendo x1 = qtd. de leite (em copos) 
 x2 = qtd. de salada (em porções de 500g) 
 
min 2x1 + 1,2x2 ------ 
s.a. 
 2x1 + 50x2 ≥ 11 –––– 
 50x1 + 10x2 ≥ 70 –––– 
 
 
 
 23 
Casos Encontrados na Resolução Gráfica 
 
Continuaremos usando aqui modelos de duas variáveis, mantendo um espaço bidimensional (pla-
no), facilitando assim a visualização, para ilustrar todas as situações possíveis de ocorrer para um 
modelo de PL qualquer. 
 
1. Uma única solução ótima. 
 
Exemplo 1: 
 
 máx. x1 + x2 
s.a.: 
 8x1 + 5x2 ≤ 100 (1) 
 16x1 + 33x2 ≤ 400 (2) 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
F.O.
(1)
(2)
 
x1
x2
 
 
 24 
Exemplo 2: 
 
min 2x1 + 1,2x2 
s.a. 
 2x1 + 50x2 ≥ 11 (1) 
 50x1 + 10x2 ≥ 70 (2) 
 
 
2. Infinitas soluções ótimas. 
 
 máx. 16x1 + 10x2 
s.a.: 
 8x1 + 5x2 ≤ 100 (1) 
 16x1 + 33x2 ≤ 400 (2) 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
x1
x2
 
(1) 
(2) 
(1) 
(2) 
 25 
3. Solução ótima ilimitada. 
 
Exemplo 1: 
 
max 2x1 + 1,2x2 
s.a. 
 2x1 + 50x2 ≥ 11 (1) 
 50x1 + 10x2 ≥ 70 (2) 
 
 
Exemplo 2: 
 
max x1 – x2 
s.a. 
 2x1 – x2 ≥ 0 (1) 
 x2 ≤ 4 (2) 
 
 
 
x1 
x2 
(1) 
(2) 
(1) 
(2) 
 26 
Exemplo 3: 
 
min x1 – 2x2 
s.a. 
 2x1 – x2 ≥ 0 (1) 
 – x1 + 2x2 ≤ 4 (2) 
 
Neste caso, embora existam soluções ótimas finitas (qualquer ponto sobre a reta 2, incluindo 
e à direita do ponto de intercessão dessa reta com a reta 1), limitando o valor ótimo da F.O., 
o conjunto desses pontos não é limitado ou “fechado”. 
 
4. Problema inviável (nenhuma solução existente). 
 
min Z = f(x1, x2) (uma função-objetivo qualquer) 
s.a. 
 x1 + x2 ≤ 1 (1) 
 x1 + x2 ≥ 2 (2) 
 
Veja que, neste caso, não existe nenhum ponto (x1, x2) no plano euclidiano que satisfaça si-
multaneamente as expressões (1) e (2). 
x1 
x2 
(1) 
(2) 
x1 
x2 
(1) (2) 
 27 
O Método Simplex 
 
 O método Simplex, desenvolvido por DANTZIG em 1956, procura, a partir de uma deter-
minada partição da matriz A, resolver o sistema de equações Ax = b. Veremos a seguir como pode-
mos “preparar” um modelo de PL qualquer para que seja resolvido pelo Simplex, quais os funda-
mentos teóricos do algoritmo, e como ele podemos usá-lo para resolver os modelos estudados. 
 
Modelo matemático e forma padrão de um PPL 
Considere o seguinte problema de programação linear: 
 
Maximizar Z = c1x1 + c2x2 + … + cnxn 
Sujeito a: a11x1 + a12x2 + … + a1nxn ≤, =, ≥ b1 
 a21x1 + a22x2 + … + a2nxn ≤, =, ≥ b2 
 … 
 am1x1 + am2x2 + … + amnxn ≤, =, ≥ bm 
 
 xn≥0, xn≥0, … xn≥0 
 
A forma apresentada acima é a expandida. Outras formas de representar um problema de programa-
ção linear são as mostradas a seguir: 
 
a) Forma de Somatório: 
 
Maximizar Z = ∑
=
n
j
jj xc
1
 
 
Sujeito a: ∑
=
n
j
jij xa
1
 ≤, =, ≥ bi, i = 1, … , m; 
 xj ≥ 0, j = 1, … , n. 
 
b) Forma Matricial 
 
Maximizar Z = cx 
Sujeito a: Ax ≤, =, ≥ b 
 x ≥ 0 
 
onde A é uma matriz retangular de dimensões m × n; c é um vetor 1 × n, b é um vetor m × 1 e x é 
um vetor n × 1. O uso de uma ou outra forma depende da conveniência da aplicação. As formas ma-
tricial e somatório são mais usadas para provas e demonstrações diversas. A forma expandida é ne-
cessária quando se torna necessário explicitar os coeficientes aij, bi e cj. 
 28 
Forma Padrão de um Modelo de PL 
Antes de estabelecermos um algoritmo único para resolver os modelos matemáticos apresentados 
anteriormente, é necessário padronizar o formato desses modelos. Usaremos o formato padrão de 
maximização, que é adotado pela maioria dos livros de P.L.: 
 
Um modelo de PL na forma padrão é constituído apenas por equações lineares, e suas variáveis e 
termos independentes (bi) devem ser não negativas, como o modelo abaixo: 
 
Maximizar Z = ∑
=
n
j
jj xc
1
 
 
Sujeito a: ∑
=
n
j
jij xa
1
= bi, i = 1, … , m; 
 xj ≥ 0, j = 1, … , n; 
 bi ≥ 0, i = 1, … , m. 
 
É importante salientar que em um problema de programação linear qualquer podem aparecer vará-
veis que devem ser deixadas livres em sua formulação, ou seja, variáveis irrestritas em sinal. Além 
disso, outras varáveis podem representar grandezas que na prática não podem ser positivas. Para 
que um problema com variáveis dos tipos mencionados acima seja colocado na forma padrão tor-
nam-se necessários alguns recursos matemáticos, os quais serão discutidos a seguir. 
 
Recursos para se obter a forma padrão de um modelo de PL 
 
1) Função Objetivo 
 
Os problemas de programação linear consistem em maximizar ou minimizar uma função objetivo. 
Um problema de minimizar pode ser transformado em maximizar fazendo-se: 
 
 [ ] ∑∑∑ −−=−−= jjjjjj xcMáximoxcMáximoxcMínimo )( 
 
Então, se o problema é minimizar e deseja-se trabalhar como maximizar, multiplica-se os coeficien-
tes da função objetivo por (-1), resolve-se o problema de maximizar e toma-se o negativo do valor 
encontrado. Esse valor é o mínimo do problema original. 
 
2) Variáveis de Folga 
 
Considere a inequação linear do tipo "≤": 
 
 k
n
j
jkj bxa ≤∑
=1
 
 
Utiliza-se uma variável xk, chamada variável de folga, em que xk = bk – ∑j akj xj, de forma que 
 
 kk
n
j
jkj bxxa =+∑
=1
 
 
Para cada restrição do tipo "≤" deve-se utilizar uma variável de folga diferente que representa a 
“folga” do recurso disponível que não foi utilizado. 
 
 29 
3) Variáveis de Excesso 
 
Considere a inequação linear do tipo "≥": 
 
 s
n
j
jsj bxa ≥∑
=1
 
 
Utiliza-se uma variável xs, chamada variável de excesso, em que xs = ∑j asj xj, – bs, de forma que 
 
 ss
n
j
jsj bxxa =−∑
=1
 
 
Para cada restrição do tipo "≥" deve-se utilizar uma variável de excesso diferente que representa o 
“excesso”do recurso utilizado. 
 
4) Variáveis livres ou irrestritas em sinal 
 
Quando uma variável representa uma grandeza que pode assumir na prática valores positivos, nulos 
ou negativos, ou seja, a variável deve ser irrestrita em sinal, então na forma padrão essa variável é 
substituída pela diferença de duas outras não negativas, e, posteriormente, quando o problema for 
resolvido, seu valor real é resgatado. Assim, se xl é irrestrita em sinal, faz-se: xl = xl' - xl'', onde xl' ≥ 
0 e xl'' ≥ 0. Resolve-se o problema com xl' e xl'', e após a solução obtém-se xl. 
 
5) Variáveis com valores não positivos 
 
Quando uma variável xq representa uma grandeza que não deve assumir valores positivos no pro-
blema original, então, para construir a forma padrão do modelo de PL, substitui-se essa variável, fa-
zendo-se xq = - xq', onde xq' ≥ 0. Resolve-se o PPL com xq' e, posteriormente, recupera-se xq. 
 
6) Termos independentes com valores negativos 
 
Se algum bi tiver sinal negativo, basta multiplicar a linha toda por –1: 
 4x1 – 3x2 ≤ –2 ⇔ – 4x1 + 3x2 ≥ 2 
 
Exemplo: 
min. 2x1 + 1,2x2 
s.a. 2x1 + 50x2 ≥ 11 
 50x1 + 10x2 ≥ 70 
 
Forma padrão: 
max. – 2x1 – 1,2x2 
s.a. 2x1 + 50x2 – x3 = 11 
 50x1 + 10x2 – x4 = 70 
 
 
 30 
Definições básicas 
 
Considere o problema de programação linear na forma matricial e padrão: 
 
Maximizar Z = cx (1) 
Sujeito a: Ax = b (2) 
 x ≥ 0 (3) 
 
Define-se como solução de um PPL, um vetor x que satisfaz as restrições (2); solução viável de um 
PPL é um vetor x que satisfaz as restrições (2) e (3); e região viável ou conjunto de soluções viá-
veis de um PPL é o conjunto de vetores x que satisfazem (2) e (3). 
 
Considere o sistema Ax = b no problema acima e suponha que 
 
 posto [A | b] = posto [A] = m, 
 
o que significa que o sistema Ax = b é compatível, ou seja, tem solução. Uma permutação das colu-
nas de A pode ser feita de forma a obter 
 
 A = [B,N], 
 
onde B é uma matriz quadrada de dimensões m × m, e N é de dimensões m × (n-m). Se o posto (B) = 
m, então B é uma matriz inversível, e uma solução do sistema pode ser dado por: 
 
bBxB
1−
= 
0Nx = 
 
O vetor x = (xB | xN) é chamado uma solução básica do sistema de equações Ax = b. Se x ≥ 0, então 
x é chamado uma solução básica viável
 
do sistema. A matriz B é chamada matriz básica, ou sim-
plesmente base do sistema e a matriz N é chamada matriz não básica. No vetor x = (xB | xN), as 
componentes de xB são chamadas variáveis básicas e as componentes de xN são chamadas variá-
veis não básicas. Se todas as componentes de xB forem maiores que zero, então x é chamado solu-
ção básica viável não degenerada, e se pelo menos uma de suas componentes for nula, então x é 
chamado solução básica degenerada. 
 
Exemplo para ilustrar as definições básicas 
 
Seja o problema de programação linear com duas variáveis e duas restrições: 
 
Maximizar z = x1 + 3 x2 (1) 
sujeito a: x1 + x2 ≤ 6 (2) 
 x2 ≤ 3 (3) 
 xj ≥ 0 
 
A representação gráfica é a seguinte: 
 
 31 
 
 
Obtendo-se a forma padrão do PPL pela introdução das variáveis de folga x3 e x4 nas restrições (2) e 
(3), respectivamente, tem-se o seguinte sistema de equações lineares: 
 
x1 + x2 + x3 = 6 
 x2 + x4 = 3 
xj ≥ 0 
 
A matriz de coeficientes tecnológicos A e os vetores colunas correspondentes são os seguintes: 
 
 [ ]43211
0
0
1
1
1
0
1
aaaaA =





= 
 
Para se obter uma matriz básica B (2 × 2) a partir da matriz A, deve-se selecionar 2 vetores, ai e aj, 
linearmente independentes. Para uma matriz A (m × n), o número máximo possível de matrizes 
quadradas de dimensões m × m é dado por: 
 
 )!(!
!
mnm
n
−
 
 
No caso, n = 4 e m = 2, assim esse número máximo é 6. No entanto, como os vetores a1 e a3 são i-
guais, ou seja, não são linearmente independentes, o número de matrizes básicas fica reduzido a 5. 
A seguir são mostradas todas as matrizes básicas obtidas a partir do sistema dado, com as respecti-
vas soluções básicas xB e as não básicas xN. 
 
1) 
 
[ ]






=





=






=










 −
==





=






==
−
0
0
3
3
3
6
10
11
10
11
4
3
1
2
1
21
x
x
x
bB
x
x
x
aaB
N
B 
 32 
 
2) 
 
[ ]






=





=






=











==





=






==
−
0
0
3
6
3
6
10
01
10
01
3
2
1
4
1
41
x
x
x
bB
x
x
x
aaB
N
B 
 
3) 
 
[ ]






=





=






=











−
==





=






==
−
0
0
3
3
3
6
11
10
01
11
4
1
1
3
2
32
x
x
x
bB
x
x
x
aaB
N
B 
 
4) 
 
[ ]






=





=






−
=











−
==





=






==
−
0
0
3
6
3
6
11
01
11
01
3
1
1
4
2
42
x
x
x
bB
x
x
x
aaB
N
B 
 
5) 
 
[ ]






=





=






=











==





=






==
−
0
0
3
6
3
6
10
01
10
01
2
1
1
4
3
43
x
x
x
bB
x
x
x
aaB
N
B 
 
Das soluções básica obtidas, apenas a solução número 4 não é viável, visto que o componente x4 é 
negativo. Então são 4 soluções básicas viáveis para o PPL, a saber: 
 
 












=
0
0
3
3
1
x , 












=
3
0
0
6
2
x , 












=
0
3
3
0
3
x , 












=
3
6
0
0
4
x 
 
Estes pontos pertencem a R4 . Uma projeção em R2, ou seja, no plano gerado por x1 e x2, tem como 
resultante os seguintes pontos: 
 33 
 
 





=
3
31
x , 





=
0
62
x , 





=
3
03
x , 





=
0
04
x 
 
Estes pontos são identificados na solução gráfica do problema, mostrando que eles correspondem 
aos pontos extremos do polígono de restrições (figura seguinte). 
 
 
 
Solução básica degenerada 
Uma solução básica viável é dita degenerada se existir uma ou mais variáveis básicas nulas. A exis-
tência de uma solução degenerada afeta o comportamento do algoritmo Simplex, e daí a importân-
cia sobre desse tipo de solução. Um exemplo mostrando a ocorrência de uma solução degenerada é 
dado a seguir. 
 
Seja o seguinte conjunto de restrições de um PPL com duas variáveis e três restrições (assumiremos 
sempre todos os xj ≥ 0, a menos que se diga o contrário): 
 
x1 + x2 ≤ 6 
 x2 ≤ 3 
x1 + 2 x2 ≤ 9 
 
Sua representação gráfica é a seguinte: 
 
x1 
x2 
x3 
x4 
 34 
 
 
Usando variáveis de folga o sistema é transformado em igualdades, na forma: 
 
x1 + x2 + x3 = 6 
 x2 + x4 = 3 
x1 + 2 x2 + x5 = 9 
 
A matriz de coeficientes do sistema expandido é: 
 
 [ ]










==
1
0
0
0
1
0
0
0
1
2
1
1
1
0
1
4321 aaaaA 
 
Considere a matriz básica formada pelas três primeiras colunas de A, ou seja, B = [a1 a2 a3]. A so-
lução correspondente é dadapor: 
 
Variáveis básicas: 
 
 










=




















−
=




















==










=
−
−
0
3
3
9
3
6
111
010
120
9
3
6
021
010
111 1
1
3
2
1
bB
x
x
x
xB 
Variáveis não básicas: 
 
 





=





=
0
0
5
4
x
x
xN 
 
Tendo em vista que a variável básica x3 = 0, então a solução é degenerada. Veremos as implicações 
disso mais tarde. 
 
 35 
Teoremas fundamentais 
 
Considere o problema de programação linear na forma padrão: 
 
Maximizar Z = cx 
Sujeito a: Ax = b 
 x ≥ 0 
 
Relembraremos agora algumas definições básicas, ilustrando-as de forma um pouco diferente: 
 
Definição 1: Uma base de uma matriz A (m × n) é uma matriz quadrada de m vetores coluna line-
armente independentes em —m. As variáveis associadas a essas colunas são chamadas 
variáveis básicas. 
 
Ax = b 
x = (xB, xR), onde: 
xB representa o vetor das variáveis básicas de m componentes, e 
xR representa o vetor das restantes n – m variáveis não básicas. 
 
 
 
O sistema pode então ser reescrito assim: 
 
 BxB + RxR = b 
 
Como podemos solucionar o conjunto de equações somente em função das variáveis básicas, 
temos: 
 
 xR = 0 e BxB = b 
 
Definição 2: Seja B uma base associada a uma matriz A. O vetor composto de bBxB 1−= e xR = 0 
é chamado de solução básica. 
 
Definição 3: Uma solução básica sem componentes negativas é denominada solução básica viá-
vel. 
 
Definição 4: O conjunto C = {x | Ax = b, x ≥ 0} denomina-se conjunto de soluções viáveis. 
 
xB 
B
 
R
 
m 
x:
 
n – m m 
A:
 
 36 
Teorema 1 
 
O conjunto C das soluções viáveis de um modelo de programação linear é um conjunto convexo. 
 
Demonstração: 
bbbAxAxxxAAx
Cxxx
Cxx
=−+=−+=−+=



≤≤
∈−+=
⇒∈
)1()1(])1([
10
)1(},{
2121
21
21
αααααα
α
αα
 
 
Teorema 2 
 
Toda solução básica viável do sistema Ax = b é um ponto extremo do conjunto de soluções viáveis, 
ou seja, um ponto extremo do conjunto C 
 
Teorema 3 
 
Todo ponto extremo x de um conjunto de soluções viáveis de um sistema Ax = b é uma solução bá-
sica viável. 
 
Corolário 1: O conjunto de pontos extremos de um conjunto de soluções viáveis é finito e limitado 
em mnC . 
 
Corolário 2: Se existe uma solução viável, então existe uma solução básica viável. 
 
Teorema 4 
 
1. Se o PPL tem solução ótima (máximo ou mínimo de Z) finita, então pelo menos uma solução ó-
tima ocorre em um ponto extremo (vértice) do conjunto C; 
2. Se a solução ótima ocorre simultaneamente em mais de um ponto extremo, então qualquer com-
binação convexa desses pontos extremos também é solução ótima. 
 
 37 
O Algoritmo Simplex 
 
O algoritmo Simplex é um procedimento computacional desenvolvido para resolver problemas de 
programação linear. Podemos dividi-lo em duas fases distintas: 
 
Fase 1 - consiste em determinar uma solução básica viável do PPL ou, então, mostrar que tal solu-
ção não existe. Neste último caso, não havendo solução básica viável, não existe solução para o 
problema, ou seja, o conjunto de restrições é inconsistente. Quando uma solução básica viável pu-
der ser identificada facilmente, a Fase 1 não precisa ser usada; 
 
Fase 2 - consiste em determinar a solução ótima para o PPL ou, então, mostrar que a solução é ili-
mitada, ou seja, que o valor de Z pode crescer ou decrescer infinitamente. A Fase 2 inicia a partir de 
uma solução básica viável do PPL, que pode ser obtida usando-se a Fase 1. 
 
Ilustração 
 
Caso típico de problema em que é necessário o uso da Fase 1: 
 
Maximizar 1 x1 + 2 x2 
sujeito a: -1 x1 + 3 x2 ≤ 9 
 1 x1 - 2 x2 ≤ 0 
 2 x1 + 1 x2 ≤ 10 
 2 x1 + 1 x2 ≥ 5 
 
Solução gráfica 
 
 
 
Colocando o problema na forma padrão tem-se: 
 
Maximizar 1 x1 + 2 x2 
sujeito a: -1 x1 + 3 x2 + x3 = 9 
 1 x1 - 2 x2 + x4 = 0 
 2 x2 + 1 x2 + x5 = 10 
 2 x1 + 1 x2 - x6 = 5 
 38 
 
Tomando-se x1 e x2 como variáveis não básicas, tem-se x1 = 0 e x2 = 0. Os valores das variáveis bá-
sicas são obtidas de forma trivial, ou seja: x3 = 9, x4 = 0, x5 = 10 e x6 = -5. A solução básica corres-
pondente é x = (0, 0, 9, 0, 10, -5), que não é viável, pois existe uma componente negativa (x6 = -5). 
Neste caso, para se obter uma solução básica inicial é necessário usar a Fase 1 do Simplex. Vere-
mos como isso pode ser feito mais adiante. 
 
Caso de problema em que não é necessário usar a Fase 1: 
 
Maximizar 5 x1 + 2 x2 
sujeito a: 1 x1 ≤ 3 
 1 x2 ≤ 4 
 1 x1 + 2 x2 ≤ 9 
 
Solução gráfica 
 
 
 
Colocando o problema na forma padrão tem-se: 
 
Maximizar 5 x1 + 2 x2 
sujeito a: 1 x1 + x3 = 3 
 1 x2 + x4 = 4 
 1 x2 + 2 x2 + x5 = 9 
 
Tomando-se x1 e x2 como variáveis não básicas, tem-se x1 = 0 e x2 = 0. Os valores das variáveis bá-
sicas são obtidas de forma trivial, ou seja: x3 = 3, x4 = 4 e x5 = 9. A solução básica correspondente é 
x = (0, 0, 3, 4, 9), que é viável, pois todas componentes são não negativas. Neste caso, para se obter 
uma solução básica inicial não é necessário usar a Fase 1 do Simplex. 
 
 39 
O Algoritmo Simplex – Detalhamento 
 
Passo 1 
 
Determine uma solução básica viável (SBV) inicial. Se necessário usar a Fase 1; 
 
Passo 2 
 
Testar se a SBV corrente é ótima. Se sim, pare, o problema está resolvido; se não, vá ao pas-
so seguinte; 
 
Passo 3 
 
Fazer a mudança de base, ou seja: 
(i) Determinar a variável não básica que deve entrar na base – a variável não básica a 
entrar na base deve ser aquela que mais aumenta o valor da função objetivo no mo-
mento corrente, ou seja, aquela que tem o maior coeficiente; 
(ii) Determinar a variável básica que deve sair da base – a variável a sair da base deve 
ser aquela que primeiro assumirá valores negativos como conseqüência do aumento 
do valor da variável escolhida para entrar na base. O propósito é não permitir que al-
guma variável assuma valores negativos, tornando o problema inviável; 
(iii) Processar a mudança de base fazendo-se a operação de pivoteamento e retornar ao 
Passo 2. 
 
 
Podemos também descrever o algoritmo em forma de fluxograma, como mostra a figura seguinte: 
 40 
 
 
 41 
Exemplo 1 
 
Uma grande fábrica de móveis dispõe em estoque de 250m de tábuas, 600m de pranchas e 500m de 
painéis de conglomerado. A fábrica normalmente oferece uma linha de móveis composta por um 
modelo de escrivaninha, uma mesa de reunião, um armário e uma prateleira. Cada tipo de móvel 
consome uma certa quantidade de matéria prima, conforme a tabela abaixo. A escrivaninha é vendi-
da por R$100, a mesa por R$80, o armário por R$120 e a prateleira por R$20. Modele e resolva o 
problema pelo simplex, de forma a maximizar a receita com a venda dos móveis. 
 
 Quantidade de material em metros 
consumidos por unidade de produto 
Disponibilidade 
do Recurso (m) 
 
Escrivaninha Mesa Armário Prateleira 
Tábua 1 1 1 4 250 
Prancha 0 1 1 2 600 
Painéis 3 2 4 0 500 
Valor de 
Revenda (R$) 100 80 120 20 
 
 
Considerando as seguintes variáveis de decisão: 
 
xE = Nº de escrivaninhas a ser produzido; 
xM = Nº de mesas a ser produzido; 
xA = Nº de armários a ser produzido; 
xP = Nº de prateleiras a ser produzido. 
 
Podemos então escrever o modelo de PL: 
 
Max. Z = 100xE + 80xM + 120xA + 20xP 
s.a. 
xE + xM + xA + 4xP ≤ 250 
 xM + xA + 4xP ≤ 600 
3xE + 2xM + 4xA ≤ 500 
 
Passando para a formapadrão, temos: 
 
Max. Z = 100xE + 80xM + 120xA + 20xP 
s.a. 
xE + xM + xA + 4xP + x1 = 250 
 xM + xA + 4xP + x2 = 600 
3xE + 2xM + 4xA + x3 = 500 
 
A nossa solução básica viável inicial pode ser obtida, neste caso, de forma trivial: 
x1 = 250; x2 = 600; x3 = 500; xE = xM = xA = xP = 0. 
 
Podemos agora montar o quadro simplex. Para isso, trataremos a equação da F.O. como se 
fosse apenas mais uma equação do nosso sistema linear: 
 
– Z + 100xE + 80xM + 120xA + 20xP = 0 
 xE + xM + xA + 4xP + x1 = 250 
 xM + xA + 4xP + x2 = 600 
 3xE + 2xM + 4xA + x3 = 500 
 
 42 
Essa linha será destacada no quadro, e sua importância será vista no decorrer do algoritmo. 
Além disso, usaremos a 1ª coluna para fazer a numeração das linhas, somente para facilitar 
as explicações a seguir. A 2ª coluna serve para relacionarmos as variáveis básicas (V.B.): 
 
 V.B. xE xM xA xP x1 x2 x3 b 
L0 – Z 100 80 120 20 0 0 0 0 
L1 x1 1 1 1 4 1 0 0 250 
L2 x2 0 1 1 2 0 1 0 600 
L3 x3 3 2 4 0 0 0 1 500 
 
Para entrar na base, devemos escolher a variável que possui o maior coeficiente na linha L0. 
Esses coeficientes indicam a contribuição que cada variável dá à Função Objetivo. para cada 
unidade de aumento de seus respectivos valores. No quadro acima, vemos que cada unidade 
de aumento da variável xA resulta em um aumento de 120 unidade no valor da F.O. Essa é a 
variável que mais contribui localmente para o processo de maximização da F.O., e é portan-
to a escolhida para entrar na base. Esse processo de escolha é representado no fluxograma da 
seguinte maneira: 
 
 cj* = max(cj) 
 
onde j* representa a coluna correspondente à variável que deve entrar na base. 
 
Para que a variável xA entre na base, é preciso que uma variável básica saia da base (por 
que?). Para determinar isso, é só fazer com que o valor de xA cresça o máximo possível. Po-
demos ver pelos valores do quadro acima que, se xA for maior que 125 (ou 4xA > 500), então 
teremos para a ultima restrição o seguinte: 
 
4xA + x3 = 500 
x3 = 500 – 4xA 
 
e o valor de x3 seria negativo, o que seria inviável. Com isso, o maior valor que xA pode as-
sumir sem violar nenhuma das restrições é xA = 125. Nesse caso, o valor de x3 seria igual a 
zero, e ele então sai da base. Todo esse processo de escolha é representado no fluxograma da 
seguinte maneira: 
 
 Escolher i* | min(bi / aij*), aij* > 0 
 
onde i* representa a linha correspondente à variável que deve sair da base. 
 
O significado desse “procedimento” é bem simples: divida todos os bi pelos valores de aij* 
que forem maiores que zero, e pegue o menor valor dessa divisão, que corresponderá à linha 
i*. No caso acima, teríamos: 
 
L1: 250 / 1 = 250 
L2: 600 / 1 = 600 
L3: 500 / 4 = 125 → i* 
 
Agora podemos representar a mudança de base usando setas no quadro: 
 43 
 
 
 V.B. xE xM xA xP x1 x2 x3 b 
L0 – Z 100 80 120 20 0 0 0 0 
L1 x1 1 1 1 4 1 0 0 250 
L2 x2 0 1 1 2 0 1 0 600 
L3 x3 3 2 4 0 0 0 1 500 
 
O elemento destacado representa o nosso pivot. Observe que os vetores-coluna das variáveis 
básicas na matriz A formam uma matriz identidade, e seus coeficientes da linha L0 são nulos. 
Esse padrão será mantido durante todo o decorrer do algoritmo. Dessa forma, os valores das 
V.B. são obtidos diretamente na última coluna (b), e o valor de – Z é obtido na posição b0. 
 
O pivoteamento consiste então em transformar a coluna correspondente à variável que está 
entrando na base em um vetor canônico, substituindo o vetor canônico da variável que está 
saindo da base. Fazemos isso por meio das operações básicas de linha. 
 
Primeiro, fazemos 3L′ ← L3 ÷ 4: 
 
 V.B. xE xM xA xP x1 x2 x3 b 
L0 – Z 100 80 120 20 0 0 0 0 
L1 x1 1 1 1 4 1 0 0 250 
L2 x2 0 1 1 2 0 1 0 600 
3L′ xA ¾ ½ 1 0 0 0 ¼ 125 
 
Depois, fazemos: 
 
0L′ ← -120 × 3L′ + L0 
1L′ ← -1 × 3L′ + L1 
2L′ ← -1 × 3L′ + L2 
 
e obtemos o segundo quadro simplex: 
 
 
 V.B. xE xM xA xP x1 x2 x3 b 
0L′ – Z 10 20 0 20 0 0 -30 -15.000 
1L′ x1 ¼ ½ 0 4 1 0 -¼ 125 
2L′ x2 -¾ ½ 0 2 0 1 -¼ 475 
3L′ xA ¾ ½ 1 0 0 0 ¼ 125 
 
Temos agora a solução básica x1 = 125; x2 = 475; xA = 125; xE = xM = x3 = xP = 0. Passamos 
de um lucro igual a zero para um lucro de R$15.000, correspondente à produção de 125 ar-
mários. 
 
Observe que ainda existem variáveis que podem contribuir para o crescimento da F.O. Co-
mo existe um empate no maior valor, entre xM e xP, escolheremos xM para entrar na base. 
Nesse caso, haverá também um empate entre x1 e xA para sair da base. Escolheremos xA para 
sair da base (depois discutiremos as implicações desses empates). 
 
 44 
Executamos então o 2º pivoteamento: 
 
1L ′′ ← 1L′ ÷ ½ 
0L ′′ ← -20 × 1L ′′ + 0L′ 
2L ′′ ← -½ × 1L ′′ + 2L′ 
3L ′′ ← -½ × 1L ′′ + 3L′ 
 
e obtemos o terceiro quadro simplex: 
 
 V.B. xE xM xA xP x1 x2 x3 b 
0L ′′ – Z 0 0 0 -140 -40 0 -20 -20.000 
1L ′′ xM ½ 1 0 8 2 0 -½ 250 
2L ′′ x2 -1 0 0 -1 1 1 0 350 
3L ′′ xA ½ 0 1 -4 -1 0 ½ 0 
 
Temos agora a solução básica xM = 250; x2 = 350; xA = 0 (VB); xE = xP = x1 = x3 = 0 (VNB). 
O lucro agora aumentou para R$20.000, correspondente à produção de 250 mesas. Essa so-
lução é ótima, já que não existe VNB que possa contribuir para o crescimento da F.O. Todas 
elas possuem coeficiente nulo ou negativo na linha da F.O. A solução ótima pode ser repre-
sentada assim: 
 
x* = (0; 250; 0; 0; 0; 350; 0) Z* = 20.000 
 
A variável de folga x2 representa a folga do recurso “Pranchas”. A solução ótima para esse 
problema, consiste em fabricar somente 250 mesas, tendo uma sobra de 350m de pranchas, e 
obtendo um lucro máximo de R$20.000,00. 
 
Veja que, apesar da variável xA estar na base, seu valor é nulo, indicando que essa solução é 
degenerada. 
 
Degeneração (ou degenerescência) e Ciclagem 
Em casos esporádicos (alguns autores dizem que esses casos são raros ou muito difíceis de ocorrer 
na prática), o algoritmo simplex pode entrar “em loop”, ou em processo de “ciclagem”. Nesses ca-
sos, ocorrem mudanças de base, mas a cada pivoteamento, o algoritmo retorna ao mesmo ponto do 
espaço de soluções, representado por vetores diferentes, mas linearmente dependentes. Isso ocorre 
quando há empate nos critérios de entrada e de saída da base, normalmente devido a alguma VB 
possuir valor nulo. 
 
Para evitar o processo de ciclagem, normalmente recorre-se a uma das duas regras mais conhecidas: 
 
– Regra Lexicográfica. Veja detalhes em (Bazaraa, 1990). 
 
– Regra de Bland 
 
• Entre todas as candidatas a entrar na base, selecione a variável xk que possui o menor índice. 
• Entre todas as candidatas a sair na base, selecione a variável xr que possui o menor índice. 
 
 
 45 
Exemplo 2 
 
Uma sorveteria produz dois tipos de sorvete: no palito e no copinho. Na sorveteria, o único ponto 
crítico é a mão-de-obra disponível. O sorvete no copinho consome 50% a mais de mão-de-obra do 
que no palito. Sabe-se que se todo sorvete produzido fosse no palito a companhia poderia produzir 
400 toneladas por dia. No entanto, o mercado tem condições de absorver, diariamente, apenas 300 
toneladas de sorvete no palito e 150 toneladas de sorvete no copinho. 
 
1. Modele o problema de modo a maximizar a produção de sorvete. 
 
Considerando Xp igual à quantidade de sorvete em palito, e Xc igual à quantidade de sorve-
te em copinho produzido (em toneladas), temos: 
 
max. Xp + Xc 
s.a. 
Xp ≤ 300 
Xc ≤ 150 
Xp + 1,5Xc ≤ 400 
 
2. Resolva-o graficamente. 
 
Xp0
Xc
100
100
200
200
300
300
400
Solução ótima: (Xp=300; Xc=66,67; Z=366,67)
400
 
 
Pela inclinação e sentido de crescimento da F.O. (linha pontilhada), vemos que a solução ó-
tima é a interseção das retas Xp = 300 e Xp + 1,5Xc = 400. Isso nos dá as seguintescoorde-
nadas: 
 
Xp* = 300; 
Xc* = (400 – Xp) / 1,5 = 100 / 1,5 = 66,67; 
Z* = 366,67. 
 46 
3. Resolva-o pelo método simplex. 
 
Marcando os pivôs em negrito, temos os seguintes quadros do simplex (alguns valores apa-
recem arredondados no quadro): 
 
==================================================== 
 | Xp Xc X3 X4 X5| b 
---------------------------------------------------- 
-Z| 1.0 1.0 0.0 0.0 0.0| 0.0 
---------------------------------------------------- 
X3| 1.0 0.0 1.0 0.0 0.0| 300.0 
X4| 0.0 1.0 0.0 1.0 0.0| 150.0 
X5| 1.0 1.5 0.0 0.0 1.0| 400.0 
==================================================== 
-Z| 0.0 1.0 -1.0 0.0 0.0| -300.0 
---------------------------------------------------- 
Xp| 1.0 0.0 1.0 0.0 0.0| 300.0 
X4| 0.0 1.0 0.0 1.0 0.0| 150.0 
X5| 0.0 1.5 -1.0 0.0 1.0| 100.0 
==================================================== 
-Z| 0.0 0.0 -0.3 0.0 -0.7| -366.7 
---------------------------------------------------- 
Xp| 1.0 0.0 1.0 0.0 0.0| 300.0 
X4| 0.0 0.0 0.7 1.0 -0.7| 83.3 
Xc| 0.0 1.0 -0.7 0.0 0.7| 66.7 
==================================================== 
Solucao otima: 
Z* = 366.67 
x
*
 = (300; 66,67; 0; 83.33; 0; 0) 
 
Observe que a variável X4 representa a folga em termos de mercado para o sorvete em copi-
nho (ou seja, é o tanto que estamos produzindo abaixo do valor máximo permitido). 
 
4. Agora observe de novo a solução gráfica e observe o que acontece, graficamente, a cada itera-
ção do Simplex. 
 
 47 
Algoritmo Simplex – Método das Duas Fases 
 
Primeiro Exemplo (extraído de Goldbarg&Luna,2000): 
 
Considere o seguinte modelo de P.L.: 
 
 Minimizar Z = -3x1 - 5x2 
sujeito a: 
 x1 ≤ 4 
 x2 ≤ 6 
 3x1 + 2x2 ≥ 18 
 x1 ≥ 0 e x2 ≥ 0 
 
Passando para a forma padrão, temos: 
 
 Maximizar Z’ = 3x1 + 5x2 
s.a.: 
x1 + x3 = 4 
 
x2 + x4 = 6 
3x1 + 2x2 - x5 = 18 
 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0 
 
x10
x2
6
4
3
2
A B
C
 
 
Observe que, neste caso, não podemos considerar a solução inicial contendo somente as variáveis 
de folga, o que resultaria em uma solução inviável. Isso pode ser visto na representação gráfica do 
problema, mostrado acima. A solução trivial x1 = 0 e x2 = 0 não pertence ao espaço de soluções. 
 
Nessas situações, normalmente opta-se por usar um dos seguintes métodos para solucionar o mode-
lo de P.L.: 
 
• Método do grande M 
• Método das duas fases 
 
Veremos aqui o método das duas fases (o outro será discutido em sala de aula). 
 
 48 
Na FASE 1, utilizamos o simplex sobre o problema modificado, e tentamos encontrar uma solução 
básica viável inicial do problema original. 
 
Na FASE 2, de posse da base encontrada na 1a Fase, aplicamos o método simplex tradicional em 
busca da solução ótima do problema. 
 
FASE 1 
1. Introduzimos uma variável artificial ajx para cada restrição do problema, ou somente para as 
restrições que tiverem variável de folga com coeficiente negativo. 
 
2. Resolvemos o problema para a seguinte F.O. modificada: 
 Min. q = ∑ ajx 
3. Se q* = 0, então existe uma solução básica viável para o problema original. Neste caso, elimi-
namos as variáveis artificiais, substituímos a F.O. modificada pela original e prosseguimos com 
o simplex. 
 
Introduzindo uma variável artificial ax6 , e mudando a função objetivo de forma a conter somente as 
variáveis artificiais, temos: 
 
 Minimizar q = ax6 
s.a.: 
x1 + x3 = 4 
 
x2 + x4 = 6 
3x1 + 2x2 - x5 + ax6 = 18 
 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, ax6 ≥ 0 
 
V.B. x1 x2 x3 x4 x5 ax6 
q 0 0 0 0 0 -1 
x3 1 0 1 0 0 0 4 
x4 0 1 0 1 0 0 6 
ax6 3 2 0 0 -1 1 18 
 
Reduzindo a coluna 6 à forma canônica, temos: 
V.B. x1 x2 x3 x4 x5 ax6 
q 3 2 0 0 -1 0 18 
x3 1 0 1 0 0 0 4 
x4 0 1 0 1 0 0 6 
ax6 3 2 0 0 -1 1 18 
 
Iteração 1: 
V.B. x1 x2 x3 x4 x5 ax6 
q 3 2 0 0 -1 0 18 
x3 1 0 1 0 0 0 4 
x4 0 1 0 1 0 0 6 
ax6 3 2 0 0 -1 1 18 
 
 
 49 
 
 
 
 
Iteração 2: 
V.B. x1 x2 x3 x4 x5 ax6 
q 0 2 -3 0 -1 0 6 
x1 1 0 1 0 0 0 4 
x4 0 1 0 1 0 0 6 
ax6 0 2 -3 0 -1 1 6 
 
V.B. x1 x2 x3 x4 x5 ax6 
q 0 0 0 0 0 -1 0 
x1 1 0 1 0 0 0 4 
x4 0 0 3/2 1 1/2 -1/2 3 
x2 0 1 -3/2 0 -1/2 1/2 3 
 
Fim da Fase 1. Retirando as partes sombreadas acima, e re-introduzindo a função objetivo original, 
temos: 
 
FASE 2 
 
V.B. x1 x2 x3 x4 x5 
-Z’ 3 5 0 0 0 0 
x1 1 0 1 0 0 4 
x4 0 0 3/2 1 1/2 3 
x2 0 1 -3/2 0 -1/2 3 
 
Reduzindo as colunas 1 e 2 à forma canônica, temos: 
V.B. x1 x2 x3 x4 x5 
-Z’ 0 0 9/2 0 5/2 -27 
x1 1 0 1 0 0 4 
x4 0 0 3/2 1 1/2 3 
x2 0 1 -3/2 0 -1/2 3 
 
Iteração 3: 
V.B. x1 x2 x3 x4 x5 
-Z’ 0 0 9/2 0 5/2 -27 
x1 1 0 1 0 0 4 
x4 0 0 3/2 1 1/2 3 
x2 0 1 -3/2 0 -1/2 3 
 
Iteração 4: 
V.B. x1 x2 x3 x4 x5 
-Z’ 0 0 0 -3 1 -36 
x1 1 0 0 -2/3 -1/3 2 
x3 0 0 1 2/3 1/3 2 
x2 0 1 0 1 0 6 
 
 
 50 
Quadro final (ótimo): 
V.B. x1 x2 x3 x4 x5 
-Z’ 0 0 -3 -5 0 -42 
x1 1 0 1 0 0 4 
x5 0 0 3 2 1 6 
x2 0 1 0 1 0 6 
 
x10
x2
6
4
3
2
A B
C
q = 18 q = 6
q = 0
Z = -27
Z = -36
Z = -42
 
 
 
 
 
 
Segundo Exemplo: Escolha da Mistura para Rações 
 
 Grão 1 Grão 2 Necessidades mínimas 
Nutriente A 2 3 650 
Nutriente C 5 3 1050 
$/kg 32 35 
 
Seja: x1 = qtde. (kg) do Grão 1 usada na ração 
 x2 = qtde. (kg) do Grão 2 usada na ração 
 
Minimizar 32x1 + 35x2 
 
Sujeito a: 
 
2x1 + 3x2 ≥ 650 
5x1 + 3x2 ≥ 1050 
 x1 ≥ 0, x2 ≥ 0 
 
 
 
 
 51 
FASE 1 
Introduzindo as variáveis de folga e as variáveis artificiais, temos o seguinte modelo artificial, já na 
forma padrão: 
 
 Maximizar q = 5 6
a ax x− − 
s.a.: 
2x1 + 3x2 – x3 + 5
ax
 
 
= 650 
5x1 + 3x2 – x4 + ax6 = 1050 
 
 
V.B. x1 x2 x3 x4 5
ax ax6 
q 0 0 0 0 -1 -1 
5
ax 2 3 -1 0 1 0 650 
ax6 5 3 0 -1 0 1 1050 
 
Reduzindo as colunas 5 e 6 à forma canônica, temos: 
V.B. x1 x2 x3 x4 5
ax ax6 
q 7 6 -1 -1 0 0 1700 
5
ax 2 3 -1 0 1 0 650 
ax6 5 3 0 -1 0 1 1050 
 
Iteração 1: 
V.B. x1 x2 x3 x4 5
ax ax6 
q 7 6 -1 -1 0 0 1700 
5
ax 2 3 -1 0 1 0 650 
ax6 5 3 0 -1 0 1 1050 
 
Iteração 2: 
V.B. x1 x2 x3 x4 5
ax ax6 
q 0 1,8 -1 0,4 0 -1,4 230 
5
ax 0 1,8 -1 0,4 1 -0,4 230 
x1 1 0,6 0 -0,2 0 0,2 210 
 
V.B. x1 x2 x3 x4 5
ax 
ax6 
q 0 0 0 0 -1 -1 0 
x2 0 1 -0,56 0,22 0,56 -0,22 127,78 
x1 1 0 0,33 0,13 -0,33 -0,13 133,33 
 
Fim da Fase 1. Retirando as partes sombreadas acima, e re-introduzindo a função objetivo original, 
temos: 
 
 
 
 
 
 
 52 
FASE 2 
 
V.B. x1 x2 x3 x4 
-Z’ 32 35 0 0 0 
x2 0 1 -0,56 0,22 127,78 
x1 1 0 0,33 0,13 133,33 
 
Reduzindo as colunas 1 e 2 à forma canônica, temos: 
V.B. x1 x2 x3 x4 
-Z’ 0 0 -8,78 -12,04 -8.738.89 
x2 0 1 -0,56 0,22 127,78 
x1 1 0 0,33 0,13 133,33 
 
O quadro acima já contém a solução ótima: 
 
x1 = 133,33 kg 
x2 = 127,78 kg 
Custo mínimo = $ 8.738.89 
 
As iterações do algoritmo são representadas na figura abaixo: 
0 40 80 120 160 200 240 280 320 360 400
0
40
80
120
160
200
240
280
320
360
400
F.O.
Nutr.A
Nutr.C
Mistura de Ração
x1
x2
 
 
 
 
 53 
Elementos de Pós-Otimização 
 
Seja o PPL dado pela Forma Padrão: 
 
Max. Z = cx 
s.a. 
 Ax = b, 
 x ≥ 0 
 
e suponha que a aplicação do método Simplex encontrou uma solução ótima associada a uma matriz 
básica B.Podemos ter então as seguintes situações: 
 
1. Mudança no vetor c 
2. Mudança no vetor b 
3. Mudança na matriz A 
4. Adição de nova atividade 
5. Adição de uma nova restrição. 
 
Se a análise não permite mudança na base B, tem-se uma Análise de Sensibilidade. Caso contrário, 
uma Análise Paramétrica. Neste módulo, será feita uma abordagem da primeira situação. 
 
� Em que faixa podem variar os custos e os meus recursos de modo que a minha solução não 
mude? 
 
Max. Z = cx 
s.a. 
 Ax = b, 
 x ≥ 0 
 
é equivalente a: 
Max. Z = B B R Rc x c x+ 
s.a. 
 B RBx Rx b+ = , 
 0, 0B Rx x≥ ≥ 
 
 Como já foi visto anteriormente, o método Simplex procura, a partir de uma determinada 
partição da matriz A, resolver o sistema de equações Ax = b, sendo que a solução, para 0Rx = , é de-
nominada solução básica. Se esta solução atende a restrição x ≥ 0, ela é denominada de solução bá-
sica viável. Se ela minimiza a F.O. Z, ela é chamada de solução ótima do PPL. 
 
O Quadro Simplex na Forma Canônica: 
 Bx Rx 
-Z 0 cj – zj 1Bc B b− 
x
B
 I 1B R− 1B b− 
onde zj = 1B jc B a− 
 54 
Condição de Otimalidade (maximização): 
(cj – zj) ≤ 0 
para toda variável não básica. 
 
Um exemplo: 
Considere o modelo do PPL visto na página 45 (com Xp e Xc sendo substituídos por x1 e x2, respec-
tivamente): 
max. x1 + x2 
s.a. 
x1 + x3 = 300 
 x2 + x4 = 150 
x1 + 1,5x2 + x5 = 400 
xj ≥ 0 
sendo 
[ ]
1
2
3
4
5
1 0 1 0 0 300
0 1 0 1 0 150 1 1 0 0 0 
1 1,5 0 0 1 400
x
x
A b c x x
x
x
 
 
     
     = = = =     
        
  
 
Vimos que a solução ótima para este PPL é: 
 
Z* = 366.67 
x
*
 = (300; 66,67; 0; 83.33; 0; 0) 
 
Temos, portanto, que x1, x2 e x4 são atividades básicas, e x3, x5 são atividades não básicas. Expres-
sando isso em termos das equações matriciais vistas anteriormente, temos... 
 
1
1 0 0 1 0 1 0 0
0 1 1 0 0 0,67 0 0,67
1 1,5 0 0 1 0,67 1 0,67
B R B−
     
     
= = = −     
     
−     
 
 
[ ] [ ]
1
3
2
5
4
1 1 0 0 0 B R B R
x
x
c c x x x
x
x
 
  
= = = =   
   
 
[ ]1 0,333 0,667R Bc c B R−− = − −
 
[ ]1 300 66,67 83,33Bx B b−= =
 
366,67B Bc x =
 
 
...que é precisamente o resultado que obtivemos na resolução do PPL através do Simplex: 
 
 
 55 
==================================================== 
-Z| 0.0 0.0 -0.3 0.0 -0.7| -366.7 
---------------------------------------------------- 
Xp| 1.0 0.0 1.0 0.0 0.0| 300.0 
X4| 0.0 0.0 0.7 1.0 -0.7| 83.3 
Xc| 0.0 1.0 -0.7 0.0 0.7| 66.7 
==================================================== 
 
 
Mudança no vetor c 
 
A análise é feita considerando-se a variação no coeficiente de cada variável na função objetivo, exi-
gindo-se que as condições de otimalidade: 
 
 (cj – zj) ≤ 0 
sejam atendidas para toda VNB. Neste caso, se a variável em questão for não básica resolve-se uma 
desigualdade linear, enquanto que se ela for variável básica resolve-se um sistema de desigualdades 
lineares. 
 
Exemplo: 
 
Considere a VNB x3 no quadro SIMPLEX ótimo visto anteriormente. O coeficiente de x3 na F.O. é 
c3 = 0. 
 
Deve-se ter: 
 
[ ]
1
3 3 3 3( ) 0 ( ) 0
1 0 0 1
(0 ) 1 1 0 0,67 0 0,67 0 0
0,67 1 0,67 0
0,333 0
0,333
Bc z c c B aλ λ
λ
λ
λ
−+ − ≤ ⇒ + − ≤
   
   ⇒ + − − ≤   
   
−   
⇒ − ≤
⇒ ≤
 
 
Isso permite uma variação para c3 de –∞ até 0,333. Neste intervalo, x3 continuará sendo VNB. Mais 
ainda, os conjuntos de VB e de VNB não mudam. 
 
Para fazer a mesma análise considerando uma VB (e.g. x1), poderíamos fazer assim: 
 
[ ] [ ]
1 0
1 0 0 1 0
0 0 (1 ) 1 0 0,67 0 0,67 0 0 0
0,67 1 0,67 0 1
0,333
R Bc c B R
λ
λ
−
− ≤
   
   ⇒ − + − ≤   
   
−   
⇒ ≥ −
 
 
 
 
 56 
Mudança no vetor b 
 
Qualquer mudança no vetor b deve ser feita de modo que as VB continuem não negativas, ou seja: 
 
 B-1b ≥ 0 
 
Exemplo: 
 
Considere o elemento b1=300. Temos então que: 
 
1
1
2
3
1 0 0 300
0 0,67 0 0,67 150 0
0,67 1 0,67 400
300 0
66,67 0.67 0
83,33 0.67 0
125 100
b
B b
b
λ λ
λ
λ
λ
λ
−
+ +     
     ≥ ⇒ − ≥     
     
−     
+ ≥

⇒ − ≥
 + ≥
⇒ − ≤ ≤
 
 
o que permite uma variação para o elemento b1 de 175 a 400. 
 
 
 57 
Dualidade 
 
L
LC C
R
Re t( ) i t( )
i
e
 
 Circuito 1 Circuito 2 
 
Relacionamentos entre a corrente i e a tensão e: 
 
Circuito 1: )(1 teidt
C
Ri
dt
diL =++ ∫ 
Circuito 2: )(1 tiedt
L
Gi
dt
deC =++ ∫ 
 
onde RG 1= 
 
Forma geral: )(tyxdtcbx
dt
dx
a =++ ∫ 
 
Dizemos que os Circuitos 1 e 2 são duais. 
 
Circuito 1: primal 
Circuito 2: dual 
 
(ou vice-versa) 
 
Seja o modelo de PL: 
 
Max. ∑
=
n
j
jj xc
1
 (1) 
s.a. i
n
j
jij bxa ≤∑
=1
, para i = 1, 2, ..., m (2) 
 xj ≥ 0 para j = 1, 2, ..., n (3) 
 
 
Chamamos esse modelo de primal. O modelo dual relacionado a ele é: 
 
Min. ∑
=
m
i
iiub
1
 (4) 
s.a. j
m
i
iij cua ≥∑
=1
, para j = 1, 2, ..., n (5) 
 ui ≥ 0 para i = 1, 2, ..., m (6) 
 
Usando a notação matricial, temos: 
 58 
 
Primal (P) Dual (D) 
Max. cx Min. ub 
s.a. Ax ≤ b s.a. uA ≥ c 
 x ≥ 0 
x: (1× n) 
 u ≥ 0 
u: (m × 1) 
 
Exemplo: 
 
Primal (P) Dual (D) 
Max. 3x1 + 1x2 + 2x3 
s.a. 2x1 + 4x2 + 3x3 ≤ 6 
 3x1 + 3x2 + 1x3 ≤ 8 
 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 
Min. 6u1 + 8u2 
s.a. 2u1 + 3u2 ≥ 3 
 4u1 + 3u2 ≥ 1 
 3u1 + 1u2 ≥ 2 
 u1 ≥ 0, u2 ≥ 0 
 
Teorema 1: 
 
Se x e u são soluções viáveis dos problemas (P) e (D), respectivamente, então buxc ≤ 
 
Teorema 2: 
 
Se x e u são soluções viáveis dos problemas (P) e (D), respectivamente, e buxc = , então essas so-
luções são ótimas, ou seja, bucx ** = 
 
 
Teorema da Existência 
Para um par de problemas duais, uma e somente uma das alternativas abaixo é verdadeira: 
 
• Nenhum dos problemas tem solução. 
• Um deles não tem solução viável e o outro tem solução ótima ilimitada. 
• Ambos possuem solução ótima finita. 
 
Ex: 
 
(P) Max. –3x1 + 2x2 
s.a. x1 ≤ 3 
 x1 – x2 ≤ 0 
 x1 ≥ 0, x2 ≥ 0 
(D) Min. –3u1 + 0u2 
s.a. u1 + u2 ≥ –3 
 3u2 ≤ –2 
 u1 ≥ 0, u2 ≥ 0 
 
 
Teorema das Folgas Complementares 
Dado um par de problemas duais, uma condição necessária e suficiente para que as soluções x e u 
sejam ótimas é que se verifiquem as seguintes relações de complementaridade de folga: 
 
u(Ax – b) = 0 
(c – uA)x = 0 
 
 
Prova: 
 
 59 
 



≥−∴≥−∴≤
≥−∴≥−∴≥
0)(0
0)(0
xAucAuccAu
bxAubxAbxA
 
 
Fazendo 
 
 



−=
−=
xAuc
bxAu
)(
)(
β
α
 
 
Teremos: 
 
 0)()( ≥−=−+−=+ buxcxAucbxAuβα 
 
Se x e u forem soluções ótimas, teremos: 
 
 buxc = 
 
Logo, 
 
 0== βα 
 
Relacionamentos entre o Problema Primal e seu Dual 
Na prática, muitos modelos de PL contêm restrições do tipo “≤”, bem como outras restrições do tipo 
“≥” e outras ainda do tipo “=”. Podemos ainda ter variáveis irrestritas ou até mesmo negativas no 
modelo original (não padrão), como vimos anteriormente. A tabela abaixo mostra como podemos 
converter imediatamente esses modelos “mistos” em seus respectivos duais, sem que seja necessá-
rio passar fazer o modelo passar por transformações intermediárias. 
 
Problema de 
Maximização 
 Problema de 
Minimização