APOSTILA INTRODUÇÃO A PESQUISA OPERACIONAL

Prévia do material em texto

__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
UNIVERSIDADE ESTADUAL DO PARANÁ - CAMPUS DE CAMPO MOURÀO 
DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO 
PROFESSORA: MÁRCIA DE FÁTIMA MORAIS 
 
 
 
 
 
 
 
 
APOSTILA 
INTRODUÇÃO À PESQUISA OPERACIONAL 
 
 
 
 
 
 
 
 
CAMPO MOURÃO 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
SUMÁRIO 
1. A PESQUISA OPERACIONAL E A ANÁLISE DE DECISÕES ........................................ 1 
1.1. O Enfoque Gerencial da Pesquisa Operacional ................................................................... 3 
1.2. A Natureza da Pesquisa Operacional................................................................................... 4 
1.2.1. Fases de um Estudo de Pesquisa Operacional .................................................................. 5 
1.3. Tipos de Modelos .............................................................................................................. 11 
1.3.1. Modelos Descritivos ....................................................................................................... 12 
1.3.2. Modelos Prescritivos ...................................................................................................... 13 
2. PROGRAMAÇÃO LINEAR/OTIMIZAÇÃO LINEAR ................................................. 15 
2.1. Modelos de Programação Linear ....................................................................................... 15 
2.2. Técnicas de Solução .......................................................................................................... 26 
2.2.1. Técnicas de Solução para Sistemas de Equações Lineares ............................................ 27 
2.2.2. Técnicas de Solução para Sistemas de Equações e Inequações Lineares....................... 29 
2.2.2.1. Método Gráfico ........................................................................................................... 29 
2.2.2.2. Método Simplex .......................................................................................................... 39 
2.2.2.2.1. Casos Especiais do Simplex ..................................................................................... 47 
2.2.2.3. Método da Função-Objetivo Auxiliar/Artificial .......................................................... 52 
2.2.3. Interpretação Econômica do Simplex ............................................................................. 53 
2.3 Exercícios ........................................................................................................................... 61 
3. DUALIDADE ....................................................................................................................... 74 
3.1. Teoremas da Dualidade ..................................................................................................... 77 
3.2. Método Dual-Simplex ....................................................................................................... 80 
3.3. Analogia entre as Soluções Primal e Dual......................................................................... 82 
3.4. Interpretação Econômica do Dual ..................................................................................... 86 
3.5. Exercícios .......................................................................................................................... 89 
4. PROGRAMAÇÃO INTEIRA .............................................................................................. 94 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
2 
4.1. Método Branch-and-Bound (Algoritmo de Bifurcação e Limite) ..................................... 97 
4.1.1. Bifurcação ....................................................................................................................... 97 
4.1.2. Limite ............................................................................................................................. 98 
4.2. Exercícios ........................................................................................................................ 101 
5. RESOLVENDO PROBLEMAS DE PROGRAMAÇÃO LINEAR NO EXCEL .............. 104 
5.1 Instalando o Solver ........................................................................................................... 104 
5.2. Definindo e Resolvendo um Problema de Programação Linear no Excel ...................... 106 
5.3. Análise de Sensibilidade .................................................................................................. 108 
5.3.1. Relatório de Respostas ................................................................................................. 110 
5.3.2. Relatório de Limites ..................................................................................................... 112 
5.3.3. Relatório de Sensibilidade ............................................................................................ 114 
5.4. Exercícios ........................................................................................................................ 117 
REFERÊNCIAS BIBLIOGRÁFICAS ................................................................................... 120 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
1. A PESQUISA OPERACIONAL E A ANÁLISE DE DECISÕES 
 
O nome "Pesquisa Operacional" apareceu pela primeira vez durante a Segunda Grande 
Guerra Mundial, quando equipes de pesquisadores procuraram desenvolver métodos para 
resolver determinados problemas de operações militares. O sucesso dessas aplicações levou o 
mundo acadêmico e empresarial a procurar utilizar as técnicas criadas em problemas de 
administração. 
A Pesquisa Operacional (PO) é uma ciência que objetiva fornecer ferramentas 
quantitativas ao processo de análise e tomada de decisões. De uma maneira geral, todas as 
disciplinas que constituem a Pesquisa Operacional se apóiam em quatro ciências 
fundamentais: Economia, Matemática, Estatística e Informática. 
A Pesquisa Operacional, de acordo com Andrade (2002) é, portanto, um ramo da 
ciência administrativa que fornece instrumentos para a análise de decisões, possuindo um 
conjunto de técnicas quantitativas para auxiliar a gerência na preparação e na tomada de 
decisão. 
Em outras palavras, “Pesquisa Operacional é a aplicação do método científico, por 
equipes multidisciplinares, a problemas que dizem respeito ao controle de sistemas 
organizacionais com a finalidade de obter as soluções que melhor satisfaçam aos objetivos da 
organização como um todo”. (ACKOFF, 1979 apud BATALHA, 1997: 18). 
Desde seu nascimento, esse novo campo de análise de decisão caracterizou-se pelo uso 
de conhecimentos científicos por equipes interdisciplinares, no esforço de determinar a 
melhor utilização de recursos limitados. Essa característica multidisciplinar das aplicações de 
Pesquisa Operacional deu um novo enfoque - o enfoque sistêmico - aos problemas de decisão 
das empresas, pois ultrapassou as fronteiras da especialidade. O especialista tem tendência 
natural a enquadrar todos os problemas dentro dos limites de sua cultura, mesmo porque é 
nesse campo que ele se sente mais confortável. 
Porém a natureza e o ambiente de negócios, mesmo que possam ser logicamente 
explicados pelo raciocínio lógico do especialista, são muito mais complexos e abrangentese, 
por isto, exigem abordagem mais aberta que permita reconhecer os múltiplos aspectos 
envolvidos. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
2 
Outra característica importante que a Pesquisa Operacional possui e que facilita muito 
o processo de análise de decisão é a utilização de modelos. Isto permite a "experimentação", o 
que significa que uma decisão pode ser mais bem avaliada e testada antes de ser efetivamente 
implementada. A economia de recursos e a experiência adquirida, advindas da 
experimentação, por si só, justificam o conhecimento e a utilização da Pesquisa Operacional 
como instrumento de administração de empresas. 
O imenso progresso da Pesquisa Operacional se deve também, em grande parte, ao 
desenvolvimento dos computadores digitais, em face de sua velocidade de processamento e 
capacidade de armazenamento e recuperação das informações. Outro fato que atualmente 
muito contribui para o uso intensivo de modelos em análise de decisões é a disseminação dos 
microcomputadores, que se tornaram unidades de processamento descentralizadas dentro das 
empresas. Isto está levando os profissionais de Pesquisa Operacional a desenvolverem 
modelos mais versáteis, mais rápidos e, principalmente, interativos, que permitem maior 
participação do homem no desenrolar dos cálculos. 
Entre as várias categorias de problemas de Pesquisa Operacional existentes, destacam-se: 
 Problema de alocação: melhor maneira de alocar tarefas aos recursos disponíveis: 
 Problema de estoques: melhor dimensionamento e controle dos estoques; 
 Scheduling: melhor programação dos trabalhos que competem por recursos comuns; 
 Roteamento: caminhos que racionalizem as tarefas de distribuição de bens e serviços; 
 Filas: minimizar tempos de espera nos setores produtivos ou nas estações prestadoras 
de serviço; 
 Substituição: melhores opções de substituição ou manutenção de equipamentos. 
 
 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
3 
1.1. O Enfoque Gerencial da Pesquisa Operacional 
 
 
A Pesquisa Operacional pode ser vista segundo dois ângulos diferentes, dois enfoques 
contrários na abordagem, mas coerentes e complementares na aplicação prática no campo da 
administração. 
O enfoque tradicional é o conceito quantitativo da Pesquisa Operacional. Aqui a 
Pesquisa Operacional é definida como uma ciência que visa a aplicar métodos matemáticos e 
estatísticos à solução de problemas de decisão, através de uma abordagem sistêmica, pela 
utilização de modelos. 
Outra visão decorre de um conceito qualitativo da Pesquisa Operacional. Nesse caso, a 
importância dos métodos matemáticos desenvolvidos pelo esforço dos pesquisadores está 
menos na solução dos problemas e mais nas suas formulações. 
A importância da PO estaria, então, na sua influência sobre o modo pelo qual os 
administradores abordam os problemas, na maneira como os formulam, na avaliação que 
fazem do relacionamento com outros problemas e na forma usada para sua comunicação a 
outras pessoas. 
Nessa abordagem qualitativa, o enfoque central é deslocado do método de solução 
(geralmente um algoritmo matemático complexo) para a formulação e para a modelagem, ou 
seja, para o diagnóstico do problema. 
Perde importância o rigor matemático da solução, e ganham relevância o espírito 
crítico e a sensibilidade para descobrir o problema correto e analisar quais informações são 
fundamentais para a decisão e quais são acessórias, apenas completando, sem, no entanto, 
afetar os resultados. 
O enfoque qualitativo da Pesquisa Operacional é o reconhecimento de que a 
abordagem quantitativa dos problemas fornece uma estrutura de raciocínio e análise que 
permite descobrir qual é a informação necessária. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
4 
A abundância de informação atrapalha tanto quanto a falta de informação. E, como 
toda informação tem um custo, o problema principal torna-se avaliar o potencial da 
informação com relação a seu custo. 
Podemos considerar que a finalidade de toda informação é reduzir o grau de incerteza 
envolvida na decisão. Assim, a informação só tem valor no contexto de uma situação 
específica, e sua importância para o administrador reside na possibilidade de poder alterar a 
decisão. 
É nesse aspecto do problema de decisão que a Pesquisa Operacional cumpre uma 
função importante. Na ausência de uma abordagem quantitativa, para avaliar o potencial da 
nova informação, a decisão de compará-la é mais governada pelo temor do desconhecido do 
que por uma análise racional de custos e benefícios. 
O conhecimento de disciplinas exatas e o treinamento em abordagem quantitativa de 
problemas levam o administrador a pensar nos problemas em termos precisos e a usar técnicas 
elaboradas de análise, procurando enfocar a estrutura básica dos problemas ao invés de suas 
características particulares. O resultado, em muitos casos, não é uma nova ferramenta de 
administração, mas uma nova estrutura conceitual de trabalho para o administrador, uma nova 
maneira de pensar. 
 
1.2. A Natureza da Pesquisa Operacional 
 
Um estudo de Pesquisa Operacional consiste, basicamente, em construir um modelo 
de um sistema real existente como meio de analisar e compreender o comportamento dessa 
situação. 
Este sistema pode existir atualmente ou pode ainda estar em concepção. No primeiro 
caso, o objetivo do estudo é analisa o desempenho do sistema para escolher uma ação no 
sentido de aprimorá-lo. No segundo caso, o objetivo é identificar a melhor estrutura do 
sistema futuro. 
A complexidade de um sistema real resulta do fato de que seu comportamento é 
influenciado por um número muito grande de elementos ou variáveis. Esta é a razão que leva 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
5 
à principal dificuldade em recomendar ações específicas de acompanhamento para cada 
variável. 
No entanto, mesmo uma situação real que envolva um número muito grande de 
variáveis, tem seu comportamento fundamentalmente influenciado por uma quantidade 
reduzida de variáveis principais. Dessa forma, a simplificação do sistema real em termos de 
um modelo passa primeiramente pela identificação dessas variáveis principais. 
O sistema real reduzido é o núcleo do sistema existente que basicamente dita o 
comportamento deste e que pode ser modelado, para efeito de análise, por uma estrutura 
conhecida, conforme pode ser visualizado na figura 1 a seguir. 
Figura 1 – Simplificação do sistema real em termos de modelagem 
Fonte: Andrade (2002) 
1.2.1. Fases de um Estudo de Pesquisa Operacional 
 
De uma forma geral, um trabalho de Pesquisa Operacional deve desenvolver-se 
segundo as fases indicadas a seguir: 
 
Definição do problema 
 É a fase mais crítica do processo de análise quantitativa, exigindo imaginação, 
trabalho de equipe e um grande esforço no sentido de transformar descrições em um problema 
bem estruturado que possa ser atacado quantitativamente. É preciso conhecer bem a situação 
em que se pretende atuar. É necessário ter bem claro qual é realmente o problema, para que 
seja possível solucionar de forma correta o problema certo. Um bom levantamento dos dados 
é imprescindível, tanto os objetivos que se pretende com a solução, comoas restrições que 
cercam o problema têm que ser definidos de uma forma clara e precisa. 
Sistema Real Existente 
 
Sistema reduzido às 
variáveis principais 
 
Modelo 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
6 
 
Construção do modelo 
 A modelagem é uma arte. Desenvolver um modelo que representa um sistema real é 
uma tarefa que requer muito cuidada e muita experiência. Um modelo deve ter duas 
qualidades: (1) ser descritivo, fornecendo explicações que facilitem a compreensão do sistema 
estudado; e (2) ser prescritivo, representado um conselheiro que orienta sobre situações 
futuras. 
 A modelagem envolve duas situações de conflito que exigem que o modelo seja 
simples o suficiente para permitir sua construção e manipulação e, ao mesmo tempo, seja 
complexo o bastante para envolver todas as variáveis relevantes e suas relações. Uma forma 
de contornar esse conflito é construir modelos simples e sofisticá-los à medida que novas 
exigências forem surgindo. A complexidade do modelo também deve aumentar de acordo 
com o conhecimento adquirido pelo modelista durante o processo de modelagem. 
Os modelos são representações freqüentemente simplificadas (já que é difícil captar a 
realidade em todos os seus aspectos) de objetos e situações reais. Podem ser de três tipos: 
 Icônicos – são réplicas físicas de um objeto real (como a maquete de um prédio, por 
exemplo) em tamanho diferente ou não; 
 Analógicos – também são modelos físicos, como os icônicos, mas não guardam a 
forma do objeto que está sendo representado. O velocímetro de um automóvel, onde a 
posição do ponteiro indica a velocidade, ou um termômetro, onde a altura do líquido 
indica a temperatura, são exemplos típicos de tais modelos. 
 Matemáticos – são aqueles em que a situação problema ou as propriedades de um 
objeto são representadas por um sistema de símbolos e relações matemáticas, como 
equações e inequações, passíveis de manipulação na busca de uma solução (valores 
desconhecidos de certas variáveis) ou no estudo do comportamento do objeto sob 
certas condições. 
Inegavelmente, os modelos apresentam algumas vantagens. A primeira delas é que se 
pode tirar conclusões válidas para a situação real por meio do modelo. Em segundo lugar, a 
experimentação com o modelo requer menos tempo e custa menos do que trabalhar com o 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
7 
objeto ou situação real. Finalmente, os modelos reduzem o risco associado à experimentação 
em situações reais. 
 Em um modelo matemático, há dois grandes tipos de variáveis: 
 Variáveis não controladas pelo analista do problema: são as variáveis que estão 
definidas pela situação, pela estrutura do problema, pelas características da 
organização ou pelas restrições. Assumem valores que não podem ser controlados, 
mas dos quais se conhece (ou se pode assumir como hipótese) o valor, conjunto de 
valores ou distribuição de probabilidades. Alguns exemplos são: o tempo que uma 
máquina leva para fazer certa operação, o lucro unitário de um produto, a capacidade 
produtiva de uma empresa ou departamento a curto prazo, etc. 
 Variáveis de decisão: são aquelas cujo valor deve ser determinado pelo analista, 
através do modelo, constituindo-se assim em solução ao problema colocado. 
Os dados requeridos por um modelo são, portanto, valores das variáveis não 
controladas pelo analista do problema. Esses dados têm que ser conhecidos antes que se possa 
analisar o modelo e recomendar uma solução. O que se faz normalmente é representar as 
variáveis por um sistema de notações, ou seja, letras e símbolos, e desenvolver o modelo. 
Após isso pode-se em separado buscar os dados necessários, o que talvez seja uma tarefa 
árdua se o problema apresentar muitas variáveis. 
 
Solução do modelo 
 Depois de desenvolvido o modelo e colhidos os dados, podemos proceder à solução do 
problema, tentado especificar os valores das variáveis que forneçam a melhor saída do 
modelo, segundo critérios pré-definidos. Esses valores das variáveis de decisão são chamados 
de solução ótima. 
Geralmente, a determinação dos valores das variáveis de decisão está sujeita às 
restrições, que nada mais são do que uma redução do espaço possível das soluções, dado um 
conjunto de variáveis não controladas. Essas variáveis não controladas, ao impor restrições 
sobre as soluções podem até mesmo fazer com que seja impossível se chegar à solução ótima. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
8 
No caso de modelos matemáticos, a solução é obtida pelo algoritmo mais adequado, 
em termos de rapidez de processamento e precisão da resposta, o que exige um conhecimento 
profundo das principais técnicas, por parte do analista. Se os modelos de simulação são 
utilizados, o conceito de otimalidade não é bem definido, e solução obtida consiste numa 
avaliação aproximada do sistema ou objetivo a ser atingido. 
 
Validação do Modelo 
 Sempre que possível todos os modelos de PO devem ser verificados e validade. 
Verificar um modelo consiste em estabelecer uma bateria de testes e aplica-los, concentrando 
as atenções na sensibilidade das variáveis críticas do modelo. Através destes testes é 
verificada a precisão do modelo, comparando-se os resultados obtidos com valores esperados. 
 Validar um modelo significa testa-lo com dados reais, analisando se o mesmo se 
comportou como o sistema real. Um modelo validado facilita muito as experimentações que o 
usuário deseja fazer num sistema real, pois é muito mais fácil, prático e barato realizar as 
modificações no modelo antes de implementar qualquer mudança. 
 A validação de um modelo nem sempre é possível, pois pode ser inviável testar o 
modelo com dados reais (pode ocorrer de o sistema real ainda não existir; estar sendo criado), 
ou mesmo não ser interessante, em termos de tempo e dinheiro, tentar validar um modelo. 
Nesse caso, um trabalho de verificação bem-feito, tratando das situações consideradas mais 
críticas e passíveis de ocorrer, é suficiente para tornar o modelo utilizável. 
 
Implementação da Solução 
 Atingido o grau de confiança no modelo desejado, roda-se o mesmo, obtendo-se os 
resultados que, após análise, servirão para orientar nas linhas de ação a serem seguidas. É 
sempre bom lembrar que a PO é uma ferramenta de apoio à tomada de decisão e, como tal, 
sugere alternativas de solução para os responsáveis pelas decisões. 
Avaliação Final 
 É o passo final do processo de análise quantitativa. Os resultados obtidos, junto com as 
considerações de ordem qualitativa (fatores imponderáveis) que não entram no modelo, serão 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
9 
enviados ao tomador de decisão para a decisão final. A avaliação dos resultados obtidos em 
qualquer etapa do processo é de fundamental importância, pois 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. 
Nesta avaliação, um fator que tem papel primordial é a experiência do pessoal 
envolvido no estudo. Não se deve esquecer que um modelo é apenas uma representação 
simplificada, não conseguindo captar todas as características e nuanças da realidade. O 
relatório deve conter a solução recomendadae quaisquer outras informações úteis sobre o 
modelo (como as restrições que formam observadas, por exemplo) em uma linguagem o 
menos técnico possível, para tornar-se inteligível a pessoas que não têm contato estreito com 
as técnicas matemáticas. Assim, é com experiência e visão crítica que conseguimos avaliar e 
determinar a aplicabilidade da decisão. Futuramente, a implementação da solução na prática 
pode levar à necessidade de adaptações ou extensões do modelo utilizado. 
Logicamente que essa seqüência de passos não é rígida, mas indica as principais 
etapas que devem ser vencidas. Exceto a fase de Solução do Modelo que se baseia em 
métodos e técnicas bem desenvolvidos, as demais fases não seguem regras fixas e definidas. 
Os procedimentos necessários para essas fases dependem do tipo do problema em análise e do 
ambiente que o envolve. 
A figura 2 a seguir ilustra as fases de um estudo de Pesquisa Operacional. 
 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
10 
PERCEPÇÃO OU DEMANDA POR SOLUÇÃO 
Figura 2 - Fases de um Estudo de Pesquisa Operacional 
 
DEFINIÇÃO DO PROBLEMA 
 
CONSTRUÇÃO DO MODELO 
 
SOLUÇÃO DO MODELO 
 
IMPLEMENTAÇÃO DOS 
RESULTADOS 
 
VALIDAÇÃO DO MODELO 
AVALIAÇÃO 
EXPERIÊNCIA 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
11 
Fonte: Andrade (2002) 
1.3. Tipos de Modelos 
 
O relacionamento entre variáveis em um modelo é, na maioria das vezes, escrito em 
termos matemáticos. A modelagem matemática é uma técnica de representação de processos e 
problemas reais. 
O modelo mais apropriado para um dado contexto ou problema depende de vários 
fatores como: natureza matemática das relações entre as variáveis; objetivos do tomador de 
decisões; e extensão do controle sobre as variáveis de decisão nível de incerteza associado 
com o ambiente de decisão. 
Usualmente os modelos matemáticos são classificados em descritivos e prescritivos. 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 3 – Classificação dos Modelos Matemáticos 
 
 
 
 
 
MODELO 
MATEMÁTICO 
MODELOS 
DESCRITIVOS 
MODELOS 
PRESCRITIVOS 
 
SIMULAÇÃO 
 
HEURÍSTICOS 
 
EXATOS 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
12 
1.3.1. Modelos Descritivos 
 
Modelos descritivos são utilizados na representação de sistemas reais (ou propostos) e 
a experimentação de diferentes cenários e políticas de ação nos mesmos. A grande motivação 
para seu uso é a flexibilidade na representação de sistemas complexos e a facilidade de 
aplicação, possibilitando prever o comportamento de um sistema modelado em um horizonte 
de planejamento escolhido. Os resultados dos experimentos apresentam uma visão futura do 
sistema, auxiliando no processo de tomada de decisões no momento presente. 
Os modelos descritivos são utilizados para comparar políticas de ações já escolhidas 
pelo tomador de decisão, não esperando que o modelo indique a melhor solução possível. 
Modelos de Simulação enquadram-se na categoria de modelos descritivos, pois são 
modelos que procuram oferecer uma representação do mundo real com o objetivo de permitir 
a geração e a análise de alternativas, antes da implementação de qualquer uma delas. Por isso, 
dão ao executivo um grau de liberdade e flexibilidade considerável, com relação à escolha da 
ação mais conveniente. 
 Isso significa que o administrador pode criar ambientes futuros possíveis e testar 
alternativas, procurando responder a questões do tipo "que acontecerá se?". Os passos básicos 
são: 
 Definição do problema; 
 Identificação das variáveis relevantes; 
 Formalização das equações do modelo; 
 Codificação do modelo; 
 Teste do modelo; e 
 Aplicação do modelo. 
 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
13 
 
 
 
 
 
 
 
 
 
Figura 4- Processo de decisão com modelos de Simulação 
Fonte: Andrade (2002) 
 
 
 
1.3.2. Modelos Prescritivos 
 
Os modelos prescritivos baseiam-se na representação dos objetivos e restrições de um 
processo para o qual se deseja descobrir soluções otimizadas, ou seja, o modelo é escrito 
segundo uma técnica que permite encontrar a melhor solução ou política de ação para os 
condicionantes representados. Os modelos prescritivos podem ser subdivididos em: modelos 
exatos ou modelos de otimização; e modelos heurísticos ou modelos aproximados. 
Ao contrário dos modelos descritivos, os modelos prescritivos não permitem 
flexibilidade na escolha da alternativa, já que é estruturado para selecionar uma única, que 
será considerada ótima, segundo algum critério. Esse critério de otimização (função-objetivo) 
é escolhido pelo administrador e o modelo encontra a melhor alternativa através de uma 
análise matemática. Essa análise é processada por métodos sistemáticos de solução, que são 
chamados algoritmos. 
Nos modelos de otimização a solução obtida é a melhor solução, dentre todas as 
possíveis, dados os condicionantes do problema modelado. A solução otimiza (maximiza ou 
minimiza) uma função-objetivo (por exemplo, lucro total ou custo de produção) e ao mesmo 
 
MODELO DE 
SIMULAÇÃO 
PROCESSO DE 
ESCOLHA DA 
MELHOR 
ALTENATIVA 
SOLUÇÃO 1 
SOLUÇÃO 2 
SOLUÇÃO 3 
SOLUÇÃO 
ESCOLHIDA 
CRITÉRIO DE 
ESCOLHA 
HIPÓTESE 1 
HIPÓTESE 2 
HIPÓTESE 3 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
14 
tempo respeita (não viola) todas as restrições do problema (por exemplo, satisfazer a 
demanda). 
Os passos que devem ser seguidos para o desenvolvimento e solução de modelos de 
otimização são: 
Definição do problema; 
Identificação das variáveis relevantes; 
Formulação da função-objetivo; 
Formulação das restrições; 
Escolha do método de solução; 
Aplicação do método de solução; e 
Avaliação da Solução. 
 
Figura 5 - Processo de decisão com modelos de Otimização 
Fonte: Andrade (2002) 
 
 
 Dependendo do tipo de problema a ser resolvido, pode ser extremamente caro, em 
termos computacionais, tentar resolve-lo por meio de modelos exatos. Neste caso, lançamos 
mão de modelos heurísticos ou aproximados. 
 Os modelos heurísticos ou aproximados não garantem que a solução ótima (melhor 
solução) seja obtida em todos os cenários resolvidos por ele, no entanto, garantem soluções de 
boa qualidade com baixo custo computacional. 
 
DADOS E 
INFORMAÇÃO DO 
SISTEMA 
 
MODELO DE OTIMIZAÇÃO: 
 
- Representação do sistema 
- Critério de seleção da 
alternativa 
SOLUÇÃO 
ÓTIMA 
DECISÃO 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
2. PROGRAMAÇÃO LINEAR/OTIMIZAÇÃO LINEAR 
 
A Programação Linear foi desenvolvida conceitualmente após a Segunda Guerra 
Mundial, pelo soviético Kolmogorov, com o objetivo de resolver problemas militares de 
logística. A primeira aplicação da Programação Linear foi feita em 1945, por Stigler em um 
problema referente à composição de uma mistura. 
O grandemarco na evolução dos estudos de Programação Linear, contudo, ocorreu em 
1947 com o desenvolvimento pelo jovem matemático Dantizig do método que denominou 
“Método Simplex”. Dantizig, matemático da força aérea e em contato com questões 
relacionadas à logística, percebeu que problemas que envolviam limitação de recursos podiam 
ser resolvidos por meio de uma sistemática busca de solução ótima entre um conjunto de 
possíveis soluções. 
O rápido avanço dos computadores fez com que a Programação Linear passasse a ser 
utilizada como ferramenta de gestão empresarial. Diversas decisões tomadas no dia-a-dia das 
empresas dizem respeito a qual combinação de recursos produz ótimo resultado. As empresas 
utilizam recursos para produzir bens e serviços. Os recursos são escassos. Deste modo, torna-
se necessário buscar a melhor maneira de alocar os recursos, visando produzir o melhor 
resultado, levando em consideração as limitação ou restrições existentes. 
De acordo com Arenales et al. (2007) exemplos de problemas que podem ser 
formulados como um problema de otimização linear aparecem nas mais variadas áreas. Neste 
contexto, Arenales at al. (2007) destacam: problemas de mistura, problemas de transporte, 
transbordo e designação, problemas de planejamento da produção, problemas de gestão 
financeira (fluxo de caixa), problemas de meio ambiente, problemas de corte e 
empacotamento, entre outros. 
 
 
2.1. Modelos de Programação Linear 
 
Como o próprio nome indica, as relações matemáticas dos modelos de Programação 
Linear devem ser lineares, ou seja, um modelo de programação linear é um modelo de 
matemático de otimização no qual todas as funções são lineares, conforme afirma Goldbarg e 
Luna (2000). Embora muitos dos problemas do mundo de negócios tenham um 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
16 
comportamento de não-linearidade, é certo afirmar que muitos deles podem ser tratados com 
o emprego da Programação Linear, com razoável nível de aproximação. 
O modelo matemático de programação linear é composto de uma função-objetivo 
linear, e de restrições técnicas representadas por um grupo de equações e inequações também 
lineares. A construção do modelo matemático, no caso de um modelo linear é a parte mais 
complicada de um estudo de Programação Linear. 
Os problemas de programação linear caracterizam-se por apresentar três elementos 
fundamentais: as variáveis de decisão, a função-objetivo e as restrições do problema. 
As variáveis de decisão referem-se às decisões a serem tomadas, visando encontrar a 
solução do problema, elas constituem as variáveis controladas. A função-objetivo é uma 
expressão matemática por meio da qual relacionamos as variáveis de decisão e o objetivo a 
ser atingido, ela mede o desempenho do sistema para cada solução apresentada. As restrições 
são as limitações impostas sobre os possíveis valores que podem ser assumidos pelas 
variáveis de decisão, elas garantem que as soluções serão obtidas de acordo com as limitações 
técnicas impostas pelo sistema. 
Não há regra fixa para a construção de modelos matemáticos em programação linear, 
todavia, segundo Goldbarg e Luna (2000) podemos decompor o processo de organização de 
um modelo de programação linear nas seguintes etapas: 
 Definição das atividades: após a análise do problema, as atividades que o compõem 
são definidas. Normalmente, associada a cada atividade uma unidade de medida deve 
ser adotada; 
 Definição dos recursos: considerando os insumos disponíveis dentro de cada atividade, 
determina-se os recursos que estão sendo usados e produzidos em cada uma; 
 Cálculo dos coeficientes de insumo/produção: é indispensável estabelecer claramente 
como as atividades e os recursos estão relacionados em termos de recursos necessários 
por unidade de atividade produzida; 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
17 
 Determinação as condições externas: considerando que os recursos são limitados, 
cumpre determinar a quantidade de cada recurso disponível para o processo modelado. 
Essas são denominadas condições externas do modelo; 
 Formalização do modelo: consiste em associar quantidades não negativas X1, X2, ..., 
Xn a cada uma das atividades, escrever as equações de balanceamento e indicar o uso 
de cada recurso, em outras palavras, deve-se identificar quais as variáveis de decisão, 
qual o objetivo e quais as restrições, e escrever as relações matemáticas do problema 
modelado. 
É importante destacar, no entanto, que a formulação do modelo é uma etapa 
fundamental para a resolução de problemas, qualquer que seja o tipo de solução empregada. 
Podemos mesmo, afirmar que, com as facilidades processamento computacionais, a cuidadosa 
definição do modelo é o maior desafio para a correta solução dos problemas de Programação 
Linear. 
Segundo Goldbarg e Luna (2000) os modelos de programação linear são um tipo 
especial de modelos de otimização. Para que um determinado sistema possa ser representado 
por meio de um modelo de programação linear, de acordo com Goldbarg e Luna (2000), 
Hillier e Lieberman (2006) e Arenales et al. (2007) ele deve possuir as seguintes 
características (hipóteses): 
 Aditividade: pressupõe que o todo é igual à soma das partes, por exemplo, o custo 
total é a soma das parcelas associadas a cada atividade; 
 Proporcionalidade: pressupõe que a quantidade de recurso consumido por uma dada 
atividade deve ser proporcional ao nível desta atividade na solução final do problema. 
Além disso, o custo de cada atividade é proporcional ao nível de operação da 
atividade; 
 Fracionamento: valores fracionários para as variáveis são aceitáveis, por exemplo, 
podemos utilizar um 1Kg de um ingrediente em uma mistura, como também 0,25Kg 
desse ingrediente; 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
18 
 Separabilidade: pode-se identificar de forma separada o custo (ou consumo de 
recursos) específico das operações de cada atividade; 
 Não Negatividade: deve ser sempre possível desenvolver dada atividade em qualquer 
nível não negativo e qualquer proporção de um dado recurso deve sempre poder ser 
utilizado; 
 Certeza: o valor atribuído a cada parâmetro de um modelo de programação linear é 
assumido como uma constante conhecida. 
De acordo com Hillier e Lieberman (2006) certos símbolos são comumente utilizados 
para representar os diversos componentes de um modelo de programação linear. Esses 
símbolos, bem como suas respectivas interpretações, para o caso de um problema de alocação 
de recursos, são a seguir apresentados: 
 Z – valor da medida de desempenho global (objetivo do problema); 
 Xj – nível de atividade j (para j = 1, 2, ..., n); 
 Cj – incremento em Z que resultaria de cada incremento unitário no nível de atividade 
j; 
 bi – quantidade do recurso i que se encontra disponível para alocação em atividades 
(para i = 1, 2, ..., m); e 
 aij – quantidade do recurso i consumido por unidade de atividade j. 
O modelo formula o problema em termos de tomar decisões em relação aos níveis de 
atividade, de forma que X1, X2, ..., Xn são denominados variáveis de decisão. Os valor de Ci, 
bi e aij (para i = 1, 2, ..., m e j = 1, 2, ..., n) são as constantes de entrada para o modelo e 
também são conhecidos como parâmetros do modelo (HILLIER e LIEBERMAN, 2006). 
De acordo com Goldbarg e Luna (2000), Hillier e Lieberman(2006) e Arenales et al. 
(2007) e um problema de otimização linear na forma padrão pode ser formulado da seguinte 
maneira: 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
19 
 
 
 
 
 
 
 
 
 
A função linear f, a ser otimizada, é chamada função objetivo, o sistema de inequações 
e equações lineares definem as restrições do problema, juntamente com as condições de não 
negatividade das variáveis (ARENALES et al., 2007). 
Segundo Hillier e Lieberman (2006) a terminologia comum para o modelo de 
programação linear pode agora sintetizada. A função que está sendo otimizada 
nn
xcxcxc  ...
2211
, é chamada de função objetivo. As limitações são normalmente 
denominadas restrições. As primeiras m restrições (aquelas com uma função de todas as 
variáveis 
nmnmm
xaxaxa  ...
2211
do lado esquerdo) são algumas vezes chamadas de 
restrições funcionais (ou restrições estruturais). De forma similar 
0
j
x
, as restrições são 
conhecidas como restrições de não-negatividade (ou condições não-negativas). 
A tabela a seguir, extraída de Hillier e Lieberman (2006), ilustra os diferentes tipos de 
dados necessários para a formulação de um modelo de programação linear envolvendo a 
alocação de recursos para atividades. 
 
 
 
 
 
 
0...,,0,0
...
.
.
.
...
...
...),...,,(
21
2211
22222121
11212111
221121





n
mnmnmm
nn
nn
nnn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
xcxcxcZouxxxfOtimizar
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
20 
 
Recurso 
Uso de Recursos por Unidade de Atividade Quantidade 
de Recursos 
Disponíveis 
Atividade 
1 2 ... n 
1 a11 a12 ... a1n b1 
2 a21 a22 ... a2n b2 
. 
. 
. 
 
... 
 
... 
 
... 
 
... 
. 
. 
. 
M am1 am2 ... amn bm 
Contribuição 
a Z por 
unidade de 
atividade 
 
C1 
 
C2 
 
... 
 
Cn 
 
 
Exemplo 1: 
Certa empresa fabrica dois produtos P1 e P2. O lucro unitário do produto P1 é de 1000 
unidades monetárias e o lucro unitário de P2 é de 1800 unidades monetárias. A empresa 
precisa de 20 horas para fabricar uma unidade de P1 e de 30 horas para fabricar uma unidade 
de P2. O tempo anual de produção disponível para isso é de 1200 horas. A demanda esperada 
para cada produto é de 40 unidades anuais de P1 e 30 unidades de P2. Qual é o plano de 
produção para que a empresa maximize seu lucro nesses itens? Construa o modelo de 
programação linear para este caso. 
 
Definição das variáveis: Nesta fase o trabalho consiste em explicitar as decisões que devem 
ser tomadas e representar as possíveis decisões através de variáveis, chamadas variáveis de 
decisão. 
O problema consiste em encontrar o programa de produção, ou seja, deve ser decidido 
quais as quantidades anuais de P1 e P2 devem ser produzidas. 
Sabendo que Xj - Quantidade anual a produzir do produto j, j = 1, 2, as variáveis de 
decisão serão: X1 - Quantidade anual a produzir de P1 e X2 - Quantidade anual a produzir de 
P2. 
 
Definição da função-objetivo: Nesta fase devemos identificar o objetivo da tomada de 
decisão. Eles aparecem geralmente na forma de maximização de lucros ou receitas, 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
21 
minimização de custos, perdas, etc. A função-objetivo é a expressão que calcula o valor do 
objetivo (lucro, receita, custo, perda, etc.) em função das variáveis de decisão. 
O objetivo do problema é maximizar o lucro (Z), que pode ser calculado: Maximizar 
Lucro (Z) = 
j
n
j
j
XC
. 
 Sabendo que: Lucro devido a P1 (C1)= 1000X1 (lucro por unidade de P1 x quantidade 
de P1) e Lucro devido a P2 (C2) = 1800X2 (lucro por unidade de P2 x quantidade de P2). 
 A função objetivo é dada por: Maximizar Lucro = 1000X1 + 1800X2 
 
Definição das restrições: Nesta fase devem ser identificadas e representadas as restrições de 
produção, que devem refletir as condições impostas ao planejamento. Cada restrição imposta 
na descrição do sistema deve ser expressa como uma relação linear (igualdade ou 
desigualdade) montadas com as variáveis de decisão, ou seja, 
j
m
i
jij
bXa 
. 
No problema em questão, as restrições impostas pelo sistema são: 
 Disponibilidade de horas para produção: 1200 horas. 
Horas ocupadas com P1 = 20X1 (uso por unidade de P1 x quantidade de P1). 
Horas ocupadas com P2 = 30X2 (uso por unidade de P2 x quantidade de P2). 
Total em horas ocupadas na produção = 20X1 + 30X2 
Restrição descritiva da situação: 20X1 + 30X2  1200 
 Disponibilidade de marcado para os produtos P1 e P2 (Demanda) 
Disponibilidade para P1 = 40 unidades 
Quantidade a produzir de P1 = X1 
Restrição descritiva da situação: X1  40 
Disponibilidade para P2 = 30 unidades 
Quantidade a produzir de P2 = X2 
Restrição descritiva da situação: X2  30 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
22 
 Outra restrição que deve ser escrita é a restrição de não-negatividade das variáveis, ou 
seja: X1  0 e X2  0 
Para finalizar, podemos escrever o modelo completo da seguinte maneira: 
 
Maximizar Lucro = 1000X1 + 1800X2 
Sujeito a: 
 
 
 
 
Exemplo 2: 
Para uma boa alimentação, o corpo necessita de vitaminas e proteínas. A necessidade 
mínima de vitaminas é de 32 unidades por dia e a de proteínas de 36 unidades por dia. Uma 
pessoa tem disponível carne e ovos para se alimentar. Cada unidade de carne contém 4 
unidades de vitaminas e 6 unidades de proteínas. Cada unidade de ovo contém 8 unidades de 
vitaminas e 6 unidades de proteínas. Qual a quantidade diária de carne e ovos que deve ser 
consumida para suprir as necessidades de vitaminas e proteínas com o menor custo possível? 
Cada unidade de carne custa 3 unidades monetárias e cada unidade de ovo custo 2,5 unidades 
montarias. 
 
Exemplo 3: 
A Windor Glass Co. fabrica produtos de vidro de alta qualidade, entre os quais janelas 
e portas de vidro. A empresa produz três fábricas industriais. As esquadrias de alumínio e 
ferragens são feitas na fábrica 1, as esquadrias de madeira são produzidas na fabrica 2 e, 
finalmente, a fábrica 3 produz o vidro e monta os produtos. 
Em consequência da queda nos ganhos, a direção decidiu modernizar a linha de 
produtos da empresa. Produtos não rentáveis estão sendo descontinuados, liberando 
capacidade produtiva para o lançamento de dois novos produtos com grande potencial de 
20X1 + 30X2  1200 
X1  40 
X2  30 
X1  0 e X2  0 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
23 
vendas: Produto 1: Uma porta de vidro de 2,5m com esquadria de alumínio; Produto 2: Uma 
janela duplamente adornada com esquadrias de madeira de 1,20 x 1,80m. 
O produto 1 requer parte da capacidade produtiva das fábricas 1 e 3, mas nenhuma da 
fábrica 2. O produto 2 precisa apenas das fábricas 2 e 3. A divisão de marketing conclui que a 
empresa poderia vender tanto quanto fosse possível produzir desses produtos por essas 
fábricas. Entretanto, pelo fato de ambos os produtos estarem competindo pela mesmacapacidade produtiva na fábrica 3, não está claro qual mix dos dois produtos seria o mais 
lucrativo. Portanto, foi constituída uma equipe de PO para estudar esta questão. 
A equipe de PO começou promovendo discussões com a alta direção para identificar 
os objetivos da diretoria para tal estudo. Essas discussões levaram à seguinte definição do 
problema: Determinar quais devem ser as taxas de produção para ambos os produtos de modo 
a maximizar o lucro total sujeito às restrições impostas pelas capacidades produtivas limitadas 
disponíveis nas três fábricas. (Cada produto será fabricado em lotes de 20, de forma que a 
taxa de produção é definida como o número de lotes produzidos por semana). É permitida 
qualquer combinação de taxas de produção que satisfaça essas restrições, inclusive não 
produzir nada de um produto e o máximo possível do outro. 
A equipe e PO também identificou os dados que precisavam ser coletados: 
1. Número de horas de tempo de produção disponível por semana em cada fábrica para 
esses novos produtos. (A maior parte do tempo nessas fábricas já está comprometida 
com os produtos atuais, de modo que a capacidade disponível para os novos produtos 
é bastante limitada). 
2. Número de horas de tempo de produção usado em cada fábrica para cada lote 
produzido de cada novo produto. 
3. Lucro por lote produzido de cada novo produto. Foi escolhido o lucro por lote 
produzido como uma medida apropriada após a equipe de PO ter concluído que o 
incremento de lucro de cada lote adicional produzido ser aproximadamente constante 
independentemente do número total de lotes produzidos. Pelo fato de nenhum custo 
adicional incorrer para o início da produção e a comercialização de tais produtos, o 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
24 
lucro total de cada um deles é aproximadamente esse lucro por lote vezes o número de 
lotes produzidos. 
Obter estimativas razoáveis dessas quantidades exigia conseguir apoio de pessoal-
chave em várias unidades da empresa. O pessoal da divisão de manufatura forneceu os dados 
da primeira categoria citada anteriormente. Desenvolver estimativas para a segunda categoria 
de dados exigia alguma análise por parte dos engenheiros de produção envolvidos no 
desenvolvimento de processos de produção para os novos produtos. Analisando-se os dados 
de custos obtidos desses mesmos engenheiros e da divisão de marketing, o departamento de 
contabilidade desenvolveu estimativas da terceira categoria. A tabela a seguir sintetiza os 
dados reunidos. 
Tabela – Dados para o problema da Wyndor Glass Co. 
 
Fábrica 
Tempo de produção por Lote (em horas) Tempo de Produção 
Disponível por 
Semana (em horas) 
1 2 
1 1 0 4 
2 0 2 12 
3 3 2 18 
Lucro por 
Lote 
 
U$3000 
 
U$5000 
 
 
A equipe de PO reconheceu imediatamente que se tratava de um problema de 
programação linear o clássico tipo mix de produtos. Pode-se: empreender a formulação do 
modelo matemático correspondente. 
Segundo com Arenales et al. (2007) e Goldbarg e Luna (2000) o problema de 
programação linear pode ser escrito em notação matricial como: 
,0
)(















x
bAX
XCxfOtimizar T
 
em que 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
25 





















mnmm
n
n
aaa
aaa
aaa
A
...
...
...
...
...
...
21
22221
11211
 
 
é uma matriz m x n, chamada matriz dos coeficientes (ou matriz tecnológica): 
 CT = (C1,C2,...,Cn) é vetor de custos; 
 XT = (X1, X2, ..., Xn) é o vetor das variáveis ou incógnitas; 
 bT = (b1, b2, ..., bm) é o vetor dos termos independentes; 
 0T = (0, 0, ...,0) é o vetor cujos elementos são todos iguais a 0. 
OBS: Denotamos por X
T
 o transposto do vetor X. Em geral, supomos que um vetor é 
do tipo coluna, isto é, um vetor de n coordenadas é uma matriz n x 1. Por comodidade, 
utilizaremos também a notação (X1, X2, ..., Xn) para o vetor X (ARENALES et al., 2007). 
 
Exemplo 4: 
Escreva em notação matricial o problema de otimização linear dado por: 
.
0,0,0
42
332
4.2),.,(
321
32
321
321321




xxx
xx
xxx
xxxxxxfMinimizar
 
Exemplo 5: 
 Dado um problema de minimização dos custos, em que os recursos disponíveis 
deverão ser totalmente utilizados. Sabendo que: 
 X
T
 = (X1, X2, X3, X4); 
C
T 
= (7, 3, 5, 6); 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
26 
b
T
 = (10, 8, 13); e 











1123
1211
3121
A
 
Pede-se: Escrever o modelo de programação linear na forma padrão. 
 
 
2.2. Técnicas de Solução 
 
Em problemas de programação linear, uma solução (X1, X2, ..., Xn) é dita factível ou 
viável se satisfaz todas as restrições e as condições de não negatividade. O conjunto de todas 
as soluções factíveis /viáveis é chamado região factível ou região viável (ARENALES et al., 
2007). 
Uma solução factível ou viável que fornece o menor/maior valor à função objetivo f é 
chamada de solução ótima, denotada por
)...,,,( **
2
*
1 n
xxxf
, por exemplo, se a função objetivo f 
for de minimização, uma solução factível/viável é ótima se 
),...,,()...,,,(
21
**
2
*
1 nn
xxxfxxxf 
, 
para qualquer solução factível/viável
),...,,(
21 n
xxxf
. Resolver um problema de otimização 
consiste em determinar uma solução ótima, isto é, determinar uma solução que satisfaça todas 
as restrições do problema e que atribua o melhor valor à função objetivo (ARENALES et al., 
2007). 
Dos modelos anteriormente formulados, pode-se percebe que a maioria deles diz 
respeito a sistemas de EQUAÇÕES e/ou INEQUAÇÕES lineares, a partir dos quais deve ser 
obtida a solução ótima (máximo ou mínimo) para o problema. 
 Portanto, é de fundamental importância que tais sistemas de equações ou inequações, 
possam ser resolvidos pelo modelador. Veremos a seguir as principais técnicas de solução 
para Problemas de Programação Linear. 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
27 
2.2.1. Técnicas de Solução para Sistemas de Equações Lineares 
 
 Para sistemas de equações lineares, podemos utilizar técnicas bem conhecidas de 
álgebra linear, tais como: 
 Método Algébrico por Adição; 
 Método Algébrico por Substituição; 
 Método Gráfico; e 
 Regra de Cramer. 
 
 
Método Algébrico por Adição 
 
Pelo menos uma das equações deve ser multiplicada por um escalar real, de tal forma 
que, após a soma das duas equações, apenas uma das variáveis seja efetivamente a incógnita 
do problema. 
 
Método Algébrico por Substituição 
 
Isola-se uma das variáveis em uma das equações, substituindo-se a relação obtida na 
outra equação. 
 
Método Gráfico 
 
Sendo todas as restrições equações lineares, com duas incógnitas, elas podem ser 
representadas geometricamente por retas. A interseção entre elas dará a solução ao problema. 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
28Regra de Cramer 
 
Quando D0, o sistema é possível e determinado, isto é, admite solução. O valor de 
cada incógnita, nesse caso, pode ser obtido pela chamada Regra de Cramer. 
O valor da incógnita Xi, i =1,2,3,...,n é igual à fração DXi/D, onde DXi é o 
determinante relativo à incógnita Xi e D é o determinante do sistema. 
Assim temos: 
X1 = DX1/D; X2 = DX2/D; ... ; Xn = DXn/D 
 
Exemplo 6: 
 Para ilustrar os métodos anteriormente citados, tomemos como referência a seguinte 
situação: “Um determinado produtor rural possui duas fazendas, Morro Branco e Riacho 
Seco, onde deseja plantar soja e trigo. Devido às condições de solo específicas, o lucro anual 
esperado para a soja é de $4/ha na Morro Branco e de $6/ha na riacho Seco; e o lucro anual 
previsto para o trigo é de $8/ha na Morro Branco e de $4/ha na Riacho Seco. Sabe-se ainda 
que: a área de soja a ser plantada na Morro Branco deve ter a mesma dimensão da área de soja 
plantada na Riacho Seco; a área de trigo plantada na Riacho Seco deve ter a mesma dimensão 
da área plantada na Morro Branco. O lucro anual deve ser $160 e $120, respectivamente; as 
fazendas têm área suficiente para atender aos anseios do produtor”. Para determinar as áreas 
de soja e trigo a serem cultivadas em cada umas das fazendas, tal situação pode ser facilmente 
apresentada por um sistema de equações lineares, onde: 
 
Variáveis de decisão 
X1 – número de hectares de soja a serem plantados em cada fazenda. 
X2 – número de hectares de trigo a serem plantados em cada fazenda. 
 
Objetivo: Maximizar lucro 
Lucro soja: $4/ha - Morro Branco; $6/ha – Riacho Seco 
Lucro trigo: $8/ha – Morro Branco; $4/ha – Riacho Seco 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
29 
Função- Objetivo 
Maximizar Lucro = (4X1 + 6X1) + (8X2 + 4X2) ou 
Maximizar Lucro = 10X1 + 12X2 
 
Restrições 
4X1 + 8X2 = 160 (Lucro da Fazenda Morro Branco) 
6X1 + 4X2 = 120 (Lucro da Fazenda Riacho Seco) 
X1  0; X2  0 
 
 Percebe-se então que o problema pode ser representado simplesmente por um sistema 
de equações lineares. Assim sendo, serão descritos a seguir alguns dos métodos que se 
encontram disponíveis para a resolução de sistemas de Equações Lineares. 
 
 
 
2.2.2. Técnicas de Solução para Sistemas de Equações e Inequações Lineares 
 
2.2.2.1. Método Gráfico 
 
 O emprego da solução gráfica restringe-se aos casos que envolvem duas variáveis, 
porque os problemas com três ou mais variáveis são difíceis de ser representados 
graficamente
1
. O estudo do método gráfico é muito importante, contudo, por permitir a 
visualização do processo de solução dos problemas. 
Essa técnica consiste em representar num sistema de eixos ortogonais o conjunto das 
possíveis soluções do problema, isto é, o conjunto de pontos (X1, X2) que obedecem ao grupo 
de restrições impostas pelo sistema em estudo. O desempenho do modelo é avaliado através 
da representação gráfica da função-objetivo. As soluções são classificadas de acordo com sua 
posição no gráfico. 
 
1
 Problemas com três ou mais variáveis são representados por gráficos multidimensionais. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
30 
O primeiro passo consiste em representar graficamente cada restrição do problema. 
Para isso devemos fazer uma conversão simples das inequações em equações, apenas 
transformando as desigualdades em igualdades. A representação gráfica de uma equação 
linear com duas variáveis é uma reta. A representação gráfica de uma inequação linear com 
duas variáveis é um dos semiplanos definidos pela reta correspondente à equação. 
A maneira mais fácil de traçar a reta correspondente é identificando os pontos em que 
ela toca os eixos do gráfico. Para identificar esses pontos, igualamos na equação, 
seguidamente, cada variável a zero. Cada reta de restrição define uma área, que denominamos 
área de soluções viáveis, que contém infinitos pontos, que satisfazem às restrições do 
problema. Como as restrições geralmente, são originalmente representadas por inequações, 
podemos afirmar que todos os pontos (abaixo quando a restrição for  ou acima quando a 
restrição for ) satisfazem à restrição. 
Para resolvermos os problemas de Programação Linear, precisamos encontrar uma 
solução que satisfaça a todas as restrições simultaneamente. No método gráfico, o 
procedimento utilizado para esse fim é o de sobrepor as áreas de soluções viáveis das diversas 
restrições. A partir daí, passam a ser consideradas válidas as soluções cujos pontos estão 
contidos na intersecção das áreas viáveis de todas as restrições. De acordo com Colin (2007) 
as restrições de não-negatividade estabelecem que a solução ótima deve estar apenas na região 
onde as variáveis assumem valores positivos. 
Obtida uma área de soluções viáveis ou factível (região viável ou factível) que 
satisfaça a todas as restrições, o próximo passo é identificar a solução ótima do problema. 
Para esse propósito utilizamos as curvas de nível (retas) da função-objetivo. 
É necessário identificar a inclinação da função-objetivo. Isso pode ser conseguido com 
base em quaisquer das retas possíveis de ser obtidas da equação; afinal, a inclinação de todas 
essas retas é a mesma. Para traçar uma primeira reta, atribuímos um valor aleatório para a 
função-objetivo, obtendo deste modo uma expressão. Resolvendo a equação, da forma antes 
explicada para as restrições, obtemos dois pares ordenados, que são os pontos onde a reta toca 
os eixos. Traçamos uma reta inicial e seguimos traçando restas paralelas à primeira, já que 
todas possuem a mesma inclinação, até que o último ponto da região de solução viável seja 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
31 
tocado, encontrando deste modo, a solução ótima para o problema. A solução ótima é, 
portanto, a que se situa no ponto extremo da área de soluções viáveis, onde obtemos o valor 
máximo/mínimo da função-objetivo, sem que sejam violadas as restrições. 
Um aspecto fundamental deve ser ressaltado: podemos afirmar quem em qualquer 
problema de Programação Linear, a solução ótima estará sempre em um dos vértices da 
figura. Seja o vértice representado pela interseção de duas (ou mais) retas das restrições e a 
reta da função-objetivo; seja o vértice correspondente à interseção da reta de uma restrição e 
um dos eixos do gráfico. 
O ponto de solução ótima pode também ser identificado facilmente por meio de 
procedimento algébrico, substituindo os pontos na função-objetivo e adotando como solução a 
que otimiza o valor da função-objetivo. 
 
 
 
 
Figura 6 – Região Viável da Restrição X1 + X2 ≤ 4 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
32 
 
Figura 7 – Região Viável da Restrição X1 ≤ 2 
 
Figura 8 – Região Viável da Restrição X2 ≤ 3 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
33 
 
Figura 9 - Região Viável para o Modelo 
 
 
 
 
 
 
 
 
 
 
 
Figura 10 – Identificação da Solução Ótima 
 
 
 
 
 
 A solução ótima x* é chamada de ponto extremo ou vértice... 
Os pontos extremos ou vértices são determinados pela 
intersecção de pelo menos duas retas (plano). 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
34 
 
Se um problema de otimização/programção linear tem uma solução ótima, então existe 
um vértice ótimo. 
 
 
Figura 11 – Vértice Ótimoi 
 
Algumas situações que podem ocorrer quando o método gráfico é utilizado para 
resolução de problemas de programação linear são ilustradas nas figuras 12, 13, 14, 15, 16 e 
17 a seguir. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
35 
 
Figura 12 - Região factível ilimitada e solução ótima única (Minimização) 
 
 
Figura 13 - Região factível ilimitada e não existe solução ótima (Minimização) 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
36 
 
Figura 14 – Múltiplas Soluções 
 
 
Figura 15 - Região factível ilimitada e infinitas soluções ótimas (Maximização) 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
37 
 
Figura 16 – Não Existe Região Factível 
 
 
Figura 17 – Solução Ótima Degenerada 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
38 
 
 
Exemplo 7: 
 
Resolver os problemas de programação linear utilizando o método gráfico. 
 
7.a) Minimizar Z = 2X1 + 3X2 
Sujeito a: 
 
 
7.b) Maximizar Z = 2X1 + 5X2 
Sujeito a: 
X1 + X2  5 
5X1 + X2  10 
X1  8 
X1  0 e X2  0 
 
3X1 + 4X2  24 
4X1 + X2  16 
X1  0 e X2  0 
Exemplo: Solução Degenerada 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
39 
2.2.2.2. Método Simplex 
 
 O Método Simplex é a ferramenta que em geral se utiliza para a resolução de 
problemas de Programação Linear. O método simplex combina conceitos de álgebra matricial 
com um conjunto de regras básicas que conduzem à identificação dos problemas de 
Programação Linear. 
 A lógica do método também se baseia em buscar a solução ótima do problema na 
interseção de duas ou mais linhas ou planos. O processo utilizado consiste em uma sistemática 
específica de resolução de equações simultâneas. Na literatura são encontradas diversas 
variantes do método simplex. 
 De acordo com Colin (2007) depois de formulado o modelo matemático do problema, 
o mesmo deve ser colocado na forma padrão, para só então ser solucionado pelo algoritmo 
simplex. 
 A forma padrão de problemas de programação linear garante que as entradas do 
algoritmo simplex tenham a mesma estrutura. Segundo Colin (2007) para o algoritmo de 
maximização, a forma padrão pode ser definida como: 
 
 
 
 
 
 
 
 
em que cj, bj e aij (i = 1, 2, ..., m; j = 1, 2, ...,n) são parâmetros conhecidos, bj ≥ 0 e xj são as 
variáveis de decisão. 
 De acordo com Colin (2007) as características do problema na forma padrão são as 
seguintes: 
 A função-objetivo é do tipo maximização; 
0...,,0,0
...
.
.
.
...
...
...),...,,(
21
2211
22222121
11212111
221121





n
mnmnmm
nn
nn
nnn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
xcxcxcxxxfMaximizar
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
40 
 Todos os lados direitos das restrições são não-negativos; 
 Todas as variáveis são do tipo “igualdade”; 
 Todas as variáveis de decisão são não-negativas. 
Uma forma padrão também pode ser criada para o problema de minimização 
(denominada forma padrão minimização), cuja estrutura exatamente a mesma, com a única 
diferença na minimização da função-objetivo (COLIN, 2007). 
 Para que o problema possa ser utilizado em qualquer problema (de minimização, com 
restrições de desigualdade, etc.), precisamos transformar problemas fora da forma padrão para 
a forma padrão. 
O algoritmo simplex utiliza diversos conceitos e definições, conforme segue: 
 Solução Básica Inicial – Uma solução básica inicial para um problema linear na forma 
padrão é obtida atribuindo-se o valor zero a n – m variáveis e resolvendo-se o sistema 
de equações para as demais m variáveis (que é exatamente o número de equações, ou 
restrições, excluindo-se as de não-negatividade). Obs: Um sistema de m equações com 
m variáveis tem solução única e pode ser resolvido por métodos algébricos. 
 Variáveis Não-Básicas – São as n – m variáveis às quais foi atribuído o valor zero 
numa solução básica inicial, ao passo que as variáveis básicas são as outras m 
variáveis. Obs: Se uma variável tem o valor zero, ela pode ou não ser uma variável 
não-básica. Em outras palavras, todas as variáveis não-básicas tem valor zero, mas 
nem todas as variáveis que tem valor zero são variáveis não-básicas. 
 Solução Básica Viável – É uma solução básica em que todas as m variáveis básicas 
são não-negativas ( ≥ 0). Obs: Uma solução viável é uma solução que pode ser 
implementada tendo em vista que os valores das variáveis de decisão estão de acordo 
com as restrições. 
Segundo Colin (2007) para um problema colocado na forma padrão, o algoritmo 
simplex caminha de uma solução viável para outra, de modo que o ponto ótimo seja 
alcançado. De acordo com Passos (2008) o método Simplex fundamenta-se em determinar 
pontos extremos, e consiste em mover-se de um ponto qualquer para outro ponto (um ponto 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
41 
adjacente) que seja melhor, transformando uma variável não básica em uma variável básica. O 
ponto encontrado será ótimo se não for possível levantar outros pontos extremos factíveis (ou 
viáveis) melhores (PASSOS, 2008). 
O algoritmo pode ser definido como contendo três partes básicas: inicialização (o 
algoritmo prepara os dados de entrada), iteração (o algoritmo repete diversas vezes o 
procedimento e faz com que a otimização do modelo seja alcançada) e regra de parada (o 
algoritmo avalia se a solução ótima foi obtida, ou se é impossível obtê-la) (COLIN, 2007). 
 Esquematicamente, para a resolução de modelos matemáticos, o quadro inicial do 
Simplex apresenta o seguinte aspecto: 
 
Variáveis 
Básicas 
X1 ... Xn Xn+1 ... Xn+m bj 
Z -c1 ... -cn 0 ... 0 0 
Xn+1 a11 ... a1n 1 ... 0 b1 
... ... ... ... ... ... ... ... 
Xn+m am1 ... amn 0 ... 1 bm 
 
 
 
 Extraído de Passos (2008) consideraremos a título de exemplo ilustrativo do método 
simplex o problema de programação linear a seguir: 
 
Maximizar Lucro (L) = 5X1 + 2X2 
Sujeito a: 
 
 
 Em primeiro lugar, verificamos que o modelo foi dado na forma canônica, pois as 
restrições são de inequações (desigualdades). No Método Simplex trabalha-se com sistemas 
10X1 + 12X2 60 
2X1 + X2  6 
X1  0 e X2  0 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
42 
de equações e, em consequência,torna-se necessário transformar o modelo na forma padrão 
(transformar as inequações em equações). 
 Para isso, torna-se necessário inserir em cada uma das inequações (restrições do 
modelo) outra variável, variável de folga (XFn) se o sinal for ≤. 
Na primeira desigualdade, é inserida a variável XF1 ou X3 e, na segunda, a variável 
XF2 ou X4. 
 
10 X1 + 12X2 + XF1(X3) = 60 
 2X2 + X2 + XF2(X4) = 6 
Deste modo, as inequações tornaram-se equações, pois X3 e X4 receberam valores que 
completaram a igualdade (no mínimo receberam o valor zero). 
Inserindo a função-objetivo no sistema anterior e, concomitantemente, colocando 
todas as variáveis do modelo do lado esquerdo das equações, temos o sistema completo para 
ser inserido no tableau (quadro). Agora o conjunto de equações fica com o seguinte aspecto. 
L – 5X1 - 2X2 = 0 
 10 X1 + 12X2 + X3 = 60 
 2X2 + X2 + X4 = 6 
O modelo ficou composto de quatro variáveis: as variáveis de folga que foram 
inseridas no sistema (X3 e X4) e que serão chamadas de variáveis básicas (VB), pois formam a 
base inicial do sistema, e as variáveis originais (X1 e X2) e que serão chamadas de variáveis 
não-básicas (VNB). As variáveis X3 e X4, inicialmente, assumem valores correspondentes ao 
total dos recursos disponíveis, pois ainda não há produção de bens, e X1 e X2 recebem valor 
zero. 
O quadro para as iterações será preenchido com os dados iniciais do problema 
(coeficiente das variáveis). Portanto, o quadro inicial do problema em questão será então 
assim composto: 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
43 
Variáveis 
Básicas 
X1 X2 X3 X4 bj (Termos 
Indepententes) 
L -5 -2 0 0 0 
X3 10 12 1 0 60 
X4 2 1 0 1 6 
 
Solução Básica Inicial 
 Após a inserção dos dados no quadro, aflui a primeira solução viável (factível ou 
admissível) do problema, que é a solução básica inicial viável ou solução básica inicial (SBI). 
Neste caso, consideramos X1 = 0, X2 = 0, X3 = 60, X4 = 6 e Z = 0. Esta solução representa a 
solução quando a empresa ainda não começou a produzir (estágio inicial). Note que a 
empresa, mesmo não produzindo os produtos referentes a X1 e X2, já tem em estoque 60 
unidades de um dos recursos e 6 unidade do outro. 
 A leitura dos valores da solução viável é feita da seguinte maneira: verifica-se na 
coluna das variáveis básicas quais são as variáveis existentes e, em seguida, lê-se na coluna do 
termo independente (ou constante ou valor da variável básica) os seus valores. As variáveis 
que não estão na coluna das variáveis básicas recebem o valor zero. A partir desse primeiro 
resultado (solução básica inicial), vão sendo melhoradas as soluções até que seja alcançada a 
solução ótima. 
 Na solução do problema, enquanto existir um valor negativo na linha da função-
objetivo (linha de L), não se chegou a solução ótima. 
 
Pivoteamento 
 Verificamos em seguida, qual a variável que vai entrar na base e qual a variável que 
vai sair da base. 
 Entra na base a variável que dá a maior contribuição para o lucro (a de maior valor 
negativo na linha da função-objetivo – a variável continua ≥ 0 e o sinal do coeficiente mudou 
porque passou para o lado esquerdo da equação). Neste caso, é a variável X1 (o seu 
coeficiente é -5). Logo, essa variável é a que deve entrar na base. A coluna em que X1 está 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
44 
localizada é denominada coluna pivô. Isto quer dizer que a coluna pivô indica a variável que 
entrará na base. Vejamos que escolhemos o valor mais negativo porque estamos utilizando a 
função-objetivo modificada (lembre-se que passamos todas as variáveis para o lado esquerdo 
da equação). Na realidade, esse valor está representando a maior contribuição para o lucro. 
 Para verificar a variável que sai da base, escolhemos a linha da seguinte maneira: 
dividimos o valor do termo independente pelo coeficiente que está na coluna, desde que ele 
não seja negativo e que seja diferente de zero. O menor valor será aquele que indicará a 
variável que sai da base. No exemplo em questão, a variável X4 é a que apresenta o menor 
quociente, ou seja, razão é igual a 3. A linha da variável que sai da base é denominada linha 
pivô. 
 A célula resultante do encontro da coluna pivô com a linha pivô determina um número 
que recebe a denominação de número (elemento) pivô. No exemplo, 2 é o número pivô. 
 
 
 
VB X1 X2 X3 X4 TI Razão 
L -5 -2 0 0 0 - 
X3 10 12 1 0 60 6 
X4 2 1 0 1 6 3 
 
 
 
Iterações 
 Como dito anteriormente, devemos melhorar a solução iterativamente. Para isso, 
calculamos, primeiramente, a nova linha pivô e, posteriormente, as outras linhas que 
comporão o novo quadro (as linhas de L e de X3 que dependem da linha pivô). 
 
 
Coluna Pivô 
Linha Pivô 
Pivô 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
45 
 Cálculo da nova linha pivô: 
Os coeficientes da nova linha pivô são calculados dividindo-se os coeficientes da linha 
pivô do quadro inicial pelo número pivô. 
 
VB X1 X2 X3 X4 TI 
L 
X3 
X1 1 0,5 0 0,5 3 
 
 Cálculo das outras linhas: 
Tomando como base a linha pivô, através de uma operação elementar, transformamos 
todos os coeficientes da coluna pivô em zero, com exceção do número pivô, que ficará com 
valor 1 (lembrando que o número pivô divide todos os coeficientes da antiga linha pivô, 
transformando-a na nova linha pivô). Os coeficientes das outras colunas tomarão os valores 
resultantes das divisões. Este método denomina Método de Eliminação de Gauss. Devido aos 
valores que deverão ser assumidos pelas outras linhas, será necessário determinar uma nova 
equação para cada linha. 
O modo prático de calcular as novas linhas é o seguinte. Como o valor da nova linha 
pivô (no caso do exemplo, X1) terá que ser 0 nas demais linhas (recorde que só o número 
pivô ficará com valor 1) faça o seguinte para montar a equação das novas linhas: Multiplique 
a linha pivô pelo elemento da coluna pivô referente a linha que está sendo calculada com sinal 
invertido, some esta equação resultante com a equação do quadro de solução atual, obtendo 
assim a nova linha. 
 
VB X1 X2 X3 X4 TI 
L 0 0,5 0 2,5 15 
X3 0 7 1 -5 30 
X1 1 0,5 0 0,5 3 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
46 
A solução ótima para o problema foi obtida, pois não existem mais coeficientes 
negativos na linha da função-objetivo (Linha de L), bem como não aparecem na coluna básica 
as variáveis X2 e X4, o levará a considerar que seus valores são iguais a 0. Os valores das 
variáveis básicas podem ser facilmente obtidos, bastando para isso uma leitura na coluna dos 
termos independentes. 
 O resultado da maximização é: 
X1 = 3, X2 = 0, X3 = 30, X4 = 0 e L* = 15 ou (3, 0, 30, 0) e L* =15. 
 Quando os valores de X1 e X2 são substituídos na equação da função-objetivo temos a 
confirmação dos resultados: L = 5X1 + 2X2 → L = 5.(3) + 2.(0) → L* = 15. 
 
Resumo do Método Simplex (Problemas de maximização com restrições do tipo ≤) 
Passo 1 – Igualar a função-objetivo da zero e transformar as inequações do problema em 
equações,inserindo variáveis de folga para cada uma das restrições e logo após construir o 
tableau. 
Passo 2 – Na linha da função-objetivo escolhe-se o maior número absoluto, porém com sinal 
negativo. A variável onde se encontra este número é candidata a entrar na base. Marca-se com 
um retângulo em toda a coluna que contém este número. 
Passo 3 – Acha-se a razão, isto é, a divisão do termo independente com a coluna analisada. 
Passo 4 – Onde se encontra a menor razão marca-se com um retângulo esta linha (menor  0). 
Passo 5 – A coluna marcada chama-se coluna pivô e a linha marcada chama-se linha pivô. 
Obs: O pivô (elemento de interseção entre a coluna pivô e a linha pivô) deve ser igual a 1, 
caso não seja igual a 1, transforma-se a linha pivô, dividindo-se toda a linha pelo número que 
está no pivô. 
Passo 6 – Troca-se a variável da base por outra variável. 
Passo 7 – Transforma-se o tableau. Verifica-se na linha da função-objetivo (Z), o número da 
coluna pivô, então multiplica-se pelo mesmo número com sinal inverso e soma-se com Z 
atual, obtendo uma nova linha Z. Verifica-se na outras linhas: Onde o cruzamento conter zero 
repete-se a linha. Se o cruzamento contiver outro número diferente de zero, multiplica-se a 
linha pelo mesmo número com sinal inverso, obtendo uma nova linha. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
47 
Passo 8 – Verifica-se no tableau, na linha da função-objetivo (Z) se existe algum número 
negativo. Se existir, volta-se para o segundo passo e segue-se em seqüência até não encontrar 
mais número negativo. Se não existir então se encontra a solução ótima. 
 
Exemplo 8: Resolver o problema a seguir utilizando o método simplex. 
Maximizar Z = 3X1 + 5X2 
Sujeito a: 
 
 
 
2.2.2.2.1. Casos Especiais do Simplex 
 
 Os modelos de programação linear para serem resolvidos pelo Método Simplex devem 
apresentar as seguintes características: 
 A função-objetivo deve ser maximizada. 
 Todas as variáveis de decisão devem ser não negativas. 
 O problema deve apresentar uma solução básica inicial. 
Caso isso não ocorra, devemos procurar um modelo equivalente que possua essas três 
características, para então usar o simplex. O procedimento algorítmico de solução do Método 
Simplex para problemas de maximização encontra-se descrito anteriormente. 
 
 
a) O problema da minimização 
 
Se a função-objetivo for de minimização, devemos multiplicá-la por (-1), obtendo uma 
função equivalente para maximização. 
 
 
 
2X1 + 4X2 10 
6X1 + X2  20 
X1 - X2  30 
X1  0 e X2  0 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
48 
Exemplo 9: 
Minimizar Z = 3X1 – 4X2 + X3 
Sujeito a: 
 X1 + X2 + X3  10 
 2X1 + X2 – X3  20 
 X1 0; X2  0; X3  0 
Multiplicando a função-objetivo por (-1) obtemos o modelo equivalente: 
Minimizar Z = -3X1 + 4X2 - X3 
Sujeito a: 
 X1 + X2 + X3  10 
 2X1 + X2 – X3  20 
 X1 0; X2  0; X3  0 
Resolvendo o modelo equivalente, teremos a solução do modelo original com a troca do sinal 
de Z. 
 
b) O problema da variável livre 
 
 Se alguma variável do modelo não possuir a condição de não negatividade, podemos 
substituí-la pela diferença de duas outras variáveis não negativas, pois um número qualquer 
sempre pode ser escrito como a diferença de dois números positivos. 
 
Exemplo 10: 
Maximizar Z = X1 + 2X2 + X3 
Sujeito a: 
 X1 + X2 + X3  10 
 2X1 + 3X2  20 
 X1 0; X2 = livre; X3  0 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
49 
Fazendo X2 = X4 – X5, com X4  0 e X5  0 e substituindo no modelo anterior, teremos o 
modelo equivalente: 
Maximizar Z = X1 + 2(X4 – X5) + X3 
Sujeito a: 
 X1 + (X4 – X5) + X3  10 
 2X1 + 3 (X4 – X5)  20 
 X1 0; X3  0; X4  0; X5  0 
 
Com todas as variáveis não negativas, a solução deste modelo resolve o modelo anterior. 
 
c) O problema da solução ilimitada: 
 
Isto ocorre quando a variável que entra na base não possui em sua coluna nenhum 
coeficiente positivo. (todas as razões são negativas) 
 
 
d) O problema de múltiplas soluções: 
 
Se na solução ótima o coeficiente de uma variável não básica é zero, ele poderá entrar 
na base sem alterar o valor do objetivo, gerando outra solução ótima. (variáveis básicas com 
valor zero na solução ótima) 
 
e) O problema da degeneração 
 
No desenvolvimento do simplex, a linha pivô é a restrição que apresenta o menor 
quociente não negativo, na divisão dos termos independentes pelos coeficientes positivos da 
variável que entra. Pode ocorrer que haja mais de um resultado nessas condições. (existe 
empate nas menores razões). 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
50 
 Devemos escolher arbitrariamente um deles para calcular a solução. Entretanto, essa 
solução apresentará variáveis básicas com valor nulo. A saída de uma variável básica nula 
provoca o aparecimento de outra variável básica nula na solução seguinte, sem alteração do 
valor do objetivo. Neste caso, a solução é chamada degenerada. Se os coeficientes da função-
objetivo retornam não negativos em alguma iteração, o caso não apresenta dificuldade. O 
problema aparece quando as iterações levam a circuitos, sem caracterizar a solução ótima. 
 
f) O problema da solução básica inicial 
 
 A solução pelo método simplex sempre exige uma solução básica para iniciar a busca 
da solução ótima. 
 Quando as restrições são do tipo , obtemos a solução básica inicial acrescentando as 
variáveis de folga (+Xi) a cada uma das restrições do problema. Quando as restrições são do 
tipo  ou =, não existe uma solução básica inicia natural. Teremos, então: 
1) Para restrições do tipo  acrescentamos variáveis de excesso (-Xi) a cada uma das 
restrições, isto é, a variável de folga é subtraída e seu valor é negativo, quando se 
anulam as variáveis de decisão. 
2) Para restrições do tipo = não acrescentamos a variável de folga à restrição 
correspondente. 
3) Introduzidas as variáveis de folga ou de excesso, para as restrições do tipo  ou  
respectivamente, devem ser introduzidas variáveis artificiais para todas as 
restrições do tipo  ou =. 
 
 
 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
51 
Exemplo 11: 
Maximizar Z = X1 + X2 + X3 
Sujeito a: 
 2X1 + X2 - X3  10 
 X1 + X2 + 2X3  20 
 2X1 + X2 + 3X3 = 60 
 X1 0; X2  0; X3  0 
Acrescentando as variáveis de folga e de excesso: 
2X1 + X2 - X3 + X4 = 10 
X1 + X2 + 2X3 - X5 = 20 
2X1 + X2 + 3X3 = 60 
 
Não temos uma solução básica inicial devido a segunda e a terceira restrições. 
 
Acrescentando na segunda e na terceira restrições as variáveis auxiliares: 
2X1 + X2 - X3 + X4 = 10 
X1 + X2 + 2X3 - X5 + Xa1 = 20 
2X1 + X2 + 3X3 + Xa2 = 60 
 
Temos então uma solução básica inicial. Devemos agora retornar ao modelo original, o que 
deve ser feito com a eliminação das variáveis auxiliares e a manutenção da solução básica. 
Isto pode ser feito utilizando o método simplex em duas fases (Método dafunção-objetivo 
auxiliar). 
 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
52 
2.2.2.3. Método da Função-Objetivo Auxiliar/Artificial 
 
 Introduzidas as variáveis de folga ou de excesso, para as restrições do  ou  
respectivamente, devem ser introduzidas variáveis artificiais para todas as restrições do tipo = 
ou . 
 Em seguida cria-se uma nova função-objetivo auxiliar/artificial, formada da seguinte 
maneira: 
a) Para todas as variáveis reais e de folga, o coeficiente da função objetivo artificial 
serra a soma dos coeficientes destas variáveis. 
d = - (aij + aij + ...+ amn)
* 
* Somente são incluídos os coeficientes das linhas com variáveis artificiais. 
b) Zero para as variáveis artificiais. 
c) O valor inicial da função-objetivo artificial é a soma dos termos independentes das 
restrições. 
Monta-se o quadro de solução de forma exatamente igual à estudada anteriormente 
para aplicação do método simplex, colocando a função-objetivo artificial na primeira linha. 
Aplica-se o método simples normalmente, usando como função-objetivo a primeira 
linha. Quando a solução ótima for atingida, dois casos podem ocorrer. 
Z
a
 = 0 – Neste caso foi obtida uma solução básica do problema original e o processo 
de solução deve continuar, desprezando-se as variáveis artificiais e os elementos da primeira 
linha, e prossegue-se com a aplicação do método simplex até obter a solução ótima. 
Z
a
  0 – Neste caso o problema original não tem solução viável, o que significa que as 
restrições devem ser inconsistentes. 
 
 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
53 
Exemplo 12: 
Maximizar Z = X1 + X2 + X3 
Sujeito a: 
 2X1 + X2 - X3  10 
 X1 + X2 + 2X3  20 
 2X1 + X2 + 3X3 = 60 
 X1 0; X2  0; X3  0 
 
Maximizar Z = X1 + X2 + X3 
2X1 + X2 - X3 + X4 = 10 
X1 + X2 + 2X3 - X5 + Xa1 = 20 
2X1 + X2 + 3X3 + Xa2 = 60 
 
Função-objetivo artificial 
X1 + X2 + 2X3 - X5 + Xa1 = 20 
2X1 + X2 + 3X3 + Xa2 = 60 
 Z
a
 = - ( 3X1 + 2X2 + 5X3 -X5 + Xa1+ Xa2 = 80) 
 
 Z
a
 = - 3X1 - 2X2 - 5X3 + 0X4+X5 + 0Xa1+ 0Xa2 = -80 
 
 
2.2.3. Interpretação Econômica do Simplex 
 
A análise econômica baseia-se nos coeficientes das variáveis na função-objetivo, sendo que: 
1. O quadro final de um modelo de programação linear apresenta variáveis básicas 
(variáveis presentes na solução ótima) e não básicas (variáveis que apresentam 
valor zero na solução ótima). 
2. A função-objetivo está escrita em termos das variáveis não-básicas. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
54 
3. Os valores das variáveis básicas estão na coluna b (termo independente). O valor 
das variáveis não básicas é zero. 
4. O coeficiente da variável não básica na função-objetivo mede a tendência do 
objetivo com aquela variável. É um valor marginal, indica a variação proporcional 
no objetivo para pequenos aumentos ou diminuições na variável. Para simplificar o 
raciocínio, vamos supor sempre variações (aumentos ou diminuições) unitárias na 
variável. 
* Posteriormente, em análise de sensibilidade podemos verificar até quantas unidades 
podemos aumentar ou diminuir da variável, sem alterar a informação contida em seu 
coeficiente. Esses coeficientes (coeficientes das variáveis na linha da função-objetivo) 
são chamados preços de oportunidade (preços relativos ao programa desenvolvido). 
5. No quadro a solução é ótima. Um aumento de zero para 1 na variável não básica 
prejudica o objetivo (lucros diminuem, custos aumentam, etc.) 
6. Alterações no lucro podem significar alterações em duas outras variáveis: receita e 
custo. 
 
Exemplo 13: 
Considerando o problema de programação linear a seguir, procederemos com a interpretação 
econômica dos resultados obtidos com a aplicação do método simplex. 
Maximizar Z = 3X1 + 5X2 
Sujeito a: 
 X1  4 (Recurso A – Horas Máquina A) 
X2  6 (Recurso B – Horas Máquina B) 
 3X1 + 2X2  18 (Recurso C – Horas Mão-de-Obra) 
 X1 0; X2  0 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
55 
O sistema de equações correspondentes é: 
Z -3X1 -5X2 = 0 
 X1 +X3 = 4 
 X2 +X4 = 6 
 3X1 +2X2 +X5 = 18 
 
Variáveis de folga: 
X3/XF1 – Sobra de recurso A - horas máquina A 
X4/XF2 – Sobra de recurso B - horas máquina B 
X5/XF3 – Sobra de recurso C - horas mão-de-obra 
Quadro inicial do método simplex 
V.B. Z X1 X2 X3 X4 X5 T.I 
Z 1 -3 -5 0 0 0 0 
X3 0 1 0 1 0 0 4 
X4 0 0 1 0 1 0 6 
X5 0 3 2 0 0 1 18 
 
Quadro final do método simplex 
V.B. Z X1 X2 X3 X4 X5 T.I 
Z 1 0 0 0 3 1 36 
 0 0 0 1 0.66 -0.33 2 
 0 0 1 0 1 0 6 
 0 1 0 0 -0.66 0.33 2 
 
SOLUÇÃO ÓTIMA: A solução ótima do problema representa um plano de produção para os 
produtos P1 e P2, bem como a utilização dos recursos empregados na produção. 
X1 = produzir 2 unidade de P1 
X2 = produzir 6 unidade de P2 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
56 
X3 = 2 – sobra do recurso A – horas máquina A 
X4 = 0 - não haverá sobra do recurso B - horas máquina B 
X5 = 0 – não haverá sobra do recurso C - horas mão-de-obra 
Z = 36 
 Na linha da função-objetivo teremos as utilidades marginais das variáveis (utilidade 
marginal/preços/preço de oportunidade). 
 
Utilidade marginal das variáveis 
X1 = 0; X2 = 0; X3 = 0; X4 = 3; X5 = 1 
 
Recursos Não-Escassos: 
No caso dos produtos P1 e P2 que tem utilidade marginal X1 = 0 e X2 = 0 (coeficientes na 
função-objetivo), qualquer unidade produzida adicionalmente não trará nenhum lucro extra. 
O recurso A não é um recurso escasso, pois apresenta folga de 2 unidades (X3 = 2). A adição 
de mais uma unidade adicional no recurso A também não trará nenhum lucro extra. Por outro 
lado, se retirarmos até 2 unidades do recurso A (X3 = 2, que é a folga disponível desse 
recurso), nenhum prejuízo será observado, ou seja, a solução ótima não será alterada 
 
Recursos Escassos: 
- A utilidade marginal (preço de oportunidade) do recurso B (coeficiente de X4 no quadro = 3) 
indica que: 
Se conseguirmos mais uma hora na máquina B aos custos correntes poderemos aumentar o 
lucro em 3 unidades monetárias. 
Se uma hora a mais da máquina B acarreta o pagamento de adicional extra (exemplo, aluguel 
hora/máquina), o valor 3 indica o limite máximo desse adicional. Qualquer valor pago pela 
hora adicional da máquina B acima de 3 unidades monetárias implica uma redução no lucro. 
Se houver falta de uma hora na máquina B (por exemplo, quebra), o lucro fica diminuído em 
3 unidades monetárias, caso não haja alteração no custo. 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
57 
- A utilidade marginal (preço de oportunidade) do recurso C (coeficiente de X5 no quadro = 1) 
indica que: 
Uma hora a menos de mão-de-obra, acarreta uma diminuição no lucro em 1 u.m, se essa hora 
a menos, for provocada pela falta de umfuncionário que não terá hora descontada. 
Contratar mais uma hora de mão-de-obra aos custos correntes significa um acréscimo de 1 
unidade monetária no lucro. 
 
Exemplo 14: 
No programa de produção para o próximo período, a empresa Beta Ltda, escolheu três 
produtos P1, P2 e P3. O quadro abaixo mostra os montantes solicitados por unidade na 
produção. 
 
Produto Lucro por Unidade Horas de Trabalho Horas de Máquina Demanda Máxima 
P1 2100 6 12 800 
P2 1200 4 6 600 
P3 600 6 2 600 
 
Os preços de venda foram fixados por decisão política e as demandas foram estimadas 
tem em vista esses preços. A firma pode obter um suprimento de 4800 horas de trabalho 
durante o período de processamento e pressupõe-se usar três máquinas que podem prover 
7200 horas de trabalho. Estabelecer um programa ótimo de produção para o período. 
 
 
Solução: 
O modelo para o problema de programação linear fica resumido a: 
X1 – Quantidade a produzir de P1 
X2 – Quantidade a produzir de P2 
X3 – Quantidade a produzir de P3 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
58 
Maximizar Z = 2100X1 + 1200X2 + 600X3 
Sujeito a: 
6X1 + 4X2 +6X3  4800 (Horas de trabalho) 
12X1 +6X2 +2X3  7200 (Horas de máquina) 
X1  800 (Demanda de P1) 
X2  600 (Demanda de P2) 
X3  600 (Demanda de P3) 
X1 0; X2  0; X3  0 
 
O sistema de equações correspondentes é: 
Z -2100X1 -1200X2 -600X3 = 0 
 6X1 +4X2 +6X3 +X4 = 4800 
 12X1 +6X2 +2X3 +X5 = 7200 
 X1 +X6 = 800 
 X2 +X7 = 600 
 X3 +X8 = 600 
 
Variáveis de folga: 
X4/XF1 – Sobra de recurso horas de trabalho 
X5/XF2 – Sobra de recurso horas de máquina 
X6/XF3 – Sobra de recurso mercado de P1 
X7/XF4 – Sobra de recurso mercado de P2 
X8/XF5 – Sobra de recurso mercado de P3 
 
 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
59 
O quadro final obtido pelo método simplex é: 
V.B. Z X1 X2 X3 X4 X5 X6 X7 X8 T.I 
Z 1 0 0 0 50 150 0 100 0 1380000 
 0 0 0 1 0.2 -0.1 0 -0.2 0 120 
 0 1 0 0 -0.03 0.1 0 -0.47 0 280 
 0 0 0 0 0.03 -0.1 1 0.47 0 520 
 0 0 1 0 0 0 0 1 0 600 
 0 0 0 0 0.2 0.1 0 0.2 1 480 
 
SOLUÇÃO ÓTIMA: A solução ótima do problema representa um plano de produção para os 
produtos P1, P2 e P3, bem como a utilização dos recursos empregados na produção. 
X1 = produzir 280 unidades de P1 
X2 = produzir 600 unidade de P2 
X3 = produzir 120 unidade de P3 
X4 = 0 - não haverá sobra do recurso horas de trabalho. 
X5 = 0 – não haverá sobra do recurso horas de máquina. 
X6 = 520 – deixarão de ser vendidas 520 unidades de P1 
X7 = 0 – toda a demanda de P2 será atendida 
X8 = 120 - deixarão de ser vendidas 120 unidades de P3 
Z = 1380000 
 
 Na linha da função-objetivo teremos as utilidades marginais das variáveis (utilidade 
marginal/preços/preço de oportunidade). 
 
Recursos Escassos: 
- A utilidade marginal (preço de oportunidade = preço sombra) do recurso HORAS DE 
TRABALHO (coeficiente de X4 no quadro = 50) indica que: 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
60 
Se conseguirmos mais uma hora de trabalho aos custos correntes poderemos aumentar nosso 
lucro em 50 unidades monetárias; Se uma hora a mais de trabalho acarreta o pagamento de 
adicional extra, o valor 50 indica o limite máximo desse adicional; Se houver falta de uma 
hora de trabalho, o lucro fica diminuído em 50, casa não haja alteração no custo (Se essa falta 
for, por exemplo, pela ausência de um funcionário que não terá hora descontada, acrescentar 
esse valor ao prejuízo causado pela ausência do funcionário). A mesma análise de aplica ao 
RECURSO HORAS DE MÁQUINA 
- A utilidade marginal de uma unidade do recurso MERCADO DE P2 (coeficiente X7 no 
quadro = 100) indica que: 
O aumento de uma unidade nesse mercado, aos custos correntes, acarreta um aumento de 100 
unidades monetárias no lucro; Da mesma forma, o cancelamento de uma unidade na compra 
de um cliente implica um prejuízo de 100, além do custo normal da unidade desse recurso; Se 
o departamento de marketing da empresa estimar em 80 o investimento adicional para 
aumentar em uma unidade o mercado de P2, esse investimento nos traria um retorno líquido 
de 100 – 80 = 20 (Por investimento adicional entendemos o valor além do custo de vendas por 
unidade nesse mercado) 
 
Recursos Não-Escassos: 
- A utilidade marginal do recurso MERCADO DE P1 (coeficiente de X6 no quadro = 0) indica 
que esse recurso não é escasso. O mesmo ocorre com o preço de oportunidade do recurso 
MERCADO DE P3. 
Isso pode nos levar a rever o investimento no mercado desses dois produtos. Uma diminuição 
desses investimentos com conseqüente diminuição do mercado não afetará as vendas, 
causando um aumento nos lucros; Outra maneira de aumentar o lucro neste caso é aumentar o 
preço de venda dos produtos P1 e P2. Isto diminui os mercados correspondentes sem afetar as 
vendas, desde que o mercado não diminua aquém da produção. 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
2.3 Exercícios 
 
1) Uma empresa que trabalha com mármores e granitos fabrica soleiras e peitoris. Ela repassa 
para os revendedores tendo um lucro de R$ 7,00 por soleira e R$ 8,50 por peitoril. Cada 
soleira tem 0,6 m
2
 de área e cada peitoril tem área de 0,8 m
2
. A empresa dispõe de 16 m
2
 de 
granito diariamente para fazer a peças e tem 5 funcionários que trabalham 6 horas por dia. Na 
confecção de uma soleira gastam-se 24 minutos e na confecção de um peitoril 20 minutos. 
Sabendo que toda a produção da empresa é absorvida pelo mercado, construa o modelo 
matemático de produção diária que maximiza o lucro da empresa. 
 
2) A empresa Ciclo S.A. faz a montagem de dois tipos de bicicletas: a do tipo Padrão e a do 
tipo Clássico. Ela recebe as peças de outras empresas e a montagem passa por duas oficinas. 
A montagem de uma bicicleta tipo padrão requer uma hora na oficina I e duas horas na oficina 
II. A montagem de uma bicicleta modelo Clássico requer uma hora e meia na oficina I e duas 
horas e meia na oficina II. A oficina I tem disponibilidade de 20 funcionários que trabalham 
oito horas por dia, e a oficina II tem a disponibilidade de 32 funcionários que trabalham, 
também, as mesmas oito horas diariamente cada um. A demanda diária de bicicleta tipo 
Clássico é de 40 peças. Sabendo que a bicicleta modelo Padrão dá uma contribuição para o 
lucro de R$ 38,00 e a modelo Clássico dá R$ 49,00, construa o modelo de programação linear 
que maximiza o lucro da empresa. 
 
3) Uma fábrica de brinquedos vai produzir três novos tipos de jogos para crianças: Plim, Plam 
e Plum. Esses brinquedos são montados a partir de peças de encaixes fabricados por outra 
empresa, nos modelos A, B e C. Na montagem do modelo Plim, são utilizadas duas peças do 
modelo A e três peças do modelo C; na montagem do modelo Plam são utilizadas quatro 
peças do modelo B e três peças do modelo C e na montagem do modelo Plum, duas peças do 
modelo A, duas peças do modelo B e quatro peças do modelo C. Na montagem do modelo 
Plim gastam-se três minutos, do modelo Plam três minutos e meio e do modelo Plum cinco 
minutos. A empresa dispõe, diariamente, de 3000 peças do modelo A, 5400 do modelo B e 
8100 do modelo C. Nodepartamento de montagem existem 16 empregados que trabalham 
seis horas por dia. A fábrica comercializa, diretamente, esses jogos em sua loja aos preços de 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
62 
R$ 4,80, R$ 5,10 e R$ 6,00 os modelos Plim, Plam e Plum respectivamente. Construa o 
modelo para esse problema de programação linear. 
 
4) Uma loja representante de uma grande empresa de tintas faz misturas de tintas, a pedido, 
para seus clientes, na cor azul em três tonalidades diferentes. Como está na moda tom-sobre-
tom, a procura tem sido muito grande e o dono da loja quer saber se a produção vai lhe 
proporcionar maior lucro. A loja dispõe, para a composição das três tonalidades, 55,5 
unidades de tinta azul escura, 16 unidades de solventes, 35,5 unidades de tinta branca e 23 
unidades de base. Sabe-se que o material gasto para se fazer uma unidade de cada tonalidade é 
o apresentado na tabela abaixo: 
Composição das tonalidades de tintas 
Material Tonalidade I Tonalidade II Tonalidade III 
Tinta Azul-escura 0,40 0,45 0,50 
Tinta Branca 0,30 0,25 0,15 
Solvente 0,15 0,10 0,10 
Base 0,15 0,20 0,25 
Para cada unidade de tinta vendida o lucro para as tonalidades I, II e III é de R$ 12,00, 
R$ 13,80 e R$ 14,50, respectivamente. Faça a modelagem do problema, onde se deve calcular 
a quantidade de tinta de cada tonalidade que deve ser produzida para que a loja obtenha o 
lucro máximo. 
 
5) Uma fábrica de móveis produz estantes e mesas para computadores. Cada estante gasta 2,5 
m
2
 de madeira, 14 parafusos, 0,40 Kg de cola, 8 puxadores e 6 dobradiças e cada mesa para 
computador gasta 2 m
2
 de madeira, 18 parafusos, 0,22 Kg de cola, 2 puxadores e 4 
dobradiças. A empresa tem 18 empregados que trabalham oito horas por dia e sabe-se que 
uma estante gasta entre o corte da madeira e o seu término quatro horas e meia e a mesa para 
computador, três horas. A loja dispõe, diariamente, de 90 m
2
 de madeira, 7 caixas de 
parafusos, cada uma com 100 parafusos, 12 quilos de cola, 15 caixas de puxadores, cada uma 
contendo 12 peças, e 17 caixas de dobradiças, cada uma contendo 12 peças. No mercado a 
empresa obtém um lucro de R$ 45,00 por cada estante vendida e R$ 36,00 por cada mesa para 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
63 
computadores. O mercado impõe uma demanda diária máxima de 16 estantes e 25 mesas para 
computadores. Determine o modelo matemático que maximiza o lucro para esse problema. 
 
6) Uma fábrica de confecções produz camisetas, bonés e calções. Cada camiseta gera um 
lucro de R$ 4,56, cada boné R$ 3,50 e cada calção R$ 4,60. na confecção de uma camiseta 
gastam-se 1,10 m de tecido, em cada boné 0,45 m e em cada calção 1,20 m. A fábrica conta 
com 25 costureiras que trabalham 6 horas por dia na confecção desses artigos, Cada camiseta 
leva 14 minutos para ser confecciona, um boné 11 minutos e um calção 10 minutos. O 
mercado demanda até 500 camisetas, não mais que 100 calções e no mínimo 60 bonés. 
Sabendo que a fábrica dispõe de 748 metros de tecido, diariamente, monte o modelo de 
produção que maximiza o lucro da empresa. 
 
7) Uma fábrica produz carros e caminhões. Cada veículo necessita passar pelas seções de 
pintura e montagem. Se a seção de pintura trabalhar somente com caminhões, 40 unidades 
podem ser pintadas por dia, e se for carro, 60 unidades por dia. Se a seção de montagem 
trabalhar somente com carros, 50 unidades podem ser montadas por dia e se for caminhões 50 
unidades por dia. Cada caminhão vendido propicia um lucro de R$300,00 e cada carro R$ 
200,00. Formule um modelo de programação linear. 
 
 8) Suponha, para o exercício anterior (exercício 7), que as revendas imponham à fábrica as 
seguintes restrições: 
 a) produção mínima de caminhões, 30 unidades; e 
 b) produção mínima de carros, 20 unidades. 
 Construa o modelo de programação linear adicionando as novas restrições. 
 
9) Uma liga especial constituída de ferro, carvão, silício e níquel pode ser obtida usando a 
mistura desses minerais puros além de 2 tipos de materiais recuperados: 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
64 
 Material Recuperado 1 – MR1 
Custo por Kg: R$ 0,20 
Composição: 
Ferro – 60% 
Carvão – 20% 
Silício – 20% 
 
 Material Recuperado 2 – MR2 
Custo por Kg: R$ 0,25 
Composição: 
Ferro – 70% 
Carvão – 20% 
Silício – 5% 
Níquel – 5% 
 
A liga deve ter a seguinte composição final: 
Matéria - Prima % mínima % máxima 
Ferro 60 65 
Carvão 15 20 
Silício 15 20 
Níquel 5 8 
 
 Os custos dos materiais puros são (por Kg): ferro: R$ 0,30; carvão: R$ 0,20; silício: 
R$ 0,28; níquel: R$ 0,50. Qual deverá ser a composição da mistura em termos dos materiais 
disponíveis, com menor custo por Kg? Construa o modelo de decisão. 
 
10) Considere um grupo de quatro propriedades agrícolas que pretendem compartilhar um 
serviço técnico comum de irrigação. A produção agrícola de cada propriedade é limitada por 
sua quantidade de terra irrigável e pela quantidade de água alocada para irrigação da 
propriedade, pelo prestador de serviço (dados apresentados na tabela abaixo): 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
65 
Propriedade Qtde terra irrigável (há) Qtde água (m
3
/ha) 
1 125 44 
2 240 80 
3 150 60 
4 300 98 
 
Existem três culturas utilizadas na região: A, B e C. O retorno líquido depende do tipo de 
cultura e do consumo de água. O prestador de serviço, por questões de política agrícola, 
estabeleceu limites máximos de produção para cada cultura. A tabela seguinte apresenta estes 
números: 
 
Cultura Retorno Líquido (ha) Limite Produção (ha) Consumo água 
(m
3
/há) 
A 400 300 10 
B 550 250 8 
C 800 350 12 
 
Existe restrição adicional de que as terras a serem plantadas devem ser proporcionais às 
disponíveis em cada propriedade. O objetivo do problema é planejar quantos hectares destinar 
a cada cultura em cada propriedade, respeitando as restrições apresentadas e maximizando o 
retorno líquido total. Construa o modelo linear do problema 
 
11) Para o problema a seguir, Calcule a solução ótima utilizando o método Gráfico e a regra 
de Cramer. 
Maximizar RECEITA = 0,3X1 + 0,5X2 
Sujeito a: 
2X1 + X2 = 2 
X1 + 3X2 = 3 
X1 0; X2  0 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
66 
12) Calcule a solução ótima utilizando o método gráfico. 
Min. Custo = 1000X1 + 2000X2 
Sujeito a: 
 8X1 + 2X2 = 16 
 1X1 + 1X2 = 6 
 2X1 + 7X2 = 28 
X1 0; X2  0 
 
 
13) Calcule a solução ótima usando a Regra de Cramer. 
Max. Lucro = X1 + X2 + X3 
Sujeito a: 
2X1 – 2X2 + 4X3 = 6 
 -3X1 + 2X2 + X3 = 1 
 X1 + 2X2 – 3X3 = 5 
X1 0; X2  0; X3  0 
 
 
14) Uma companhia de transporte tem dois tipos de caminhões: o tipo “A” tem 2 m3 de 
espaço refrigerado e 3 m
3
 de espaço não-refrigerado; o tipo “B” tem 2 m3 de espaço 
refrigerado e 1 m
3
 de não-refrigerado. O cliente quer transportar um produto que necessitará 
16 m
3 
de área refrigerada e 12 m
3
 de área não-refrigerada. A companhia calcula em 1.100litros o combustível para uma viagem com o caminhão “A” e 750 litros para o caminhão “B”. 
Quantos caminhões de cada tipo deverão ser usados no transporte do produto, com o menor 
custo de combustível? Calcule a solução ótima através dos métodos: Algébrico por adição, 
algébrico por substituição, gráfico e regra de Cramer. 
 
15) Resolva os problemas de programação linear a seguir através do método gráfico: 
 
 
15.a) Maximizar Z = X1 + X2 
Sujeito a: 
 
 
4X1 + 2X2 7 
3X1 + 5X2  15 
X1  0 e X2  0 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
67 
15.b) Minimizar Z = 3X1 + 2X2 
Sujeito a: 
2X1 + X2  10 
X1 + 5X2  15 
 X1 0; X2  0 
 
15.c) Maximizar Z = 5X1 + 6X2 
Sujeito a: 
3X1 + 4X2 ≤ 24 
2X1 + X2 ≤ 10 
X2 ≤ 5 
 X1 0; X2  0 
 
 
 
15.d) Minimizar Z = 5X1 + 6X2 
Sujeito a: 
9X1 + 8X2 ≤ 72 
3X1 + 11X2 ≥ 33 
X1 ≥ 2 
 X1 0; X2  0 
 
15.e) Um sapateiro faz 6 sapatos por hora, se fizer somente sapatos, e 5 cintos por hora, se 
fizer somente cintos. Ele gasta 2 unidades de couro para fabricar 1 unidade de sapato e 1 
unidade de couro para fabricar 1 unidade de cinto. Sabendo-se que o total disponível de couro 
é de 6 unidades e que o lucro unitário por sapato é de 5 unidades monetárias e o do cinto é de 
2 unidades monetárias, pede-se: o modelo do sistema de produção do sapateiro, se o objetivo 
é maximizar seu lucro por hora e determinar através do método gráfico quantas unidades de 
sapatos e cintos deverão ser feitas para que o lucro obtido seja máximo. 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
68 
16) Resolva os problemas a seguir empregando o método simplex: 
 
16.a) Maximizar Z = 4X1 + 5X2 
Sujeito a: 
 
 
 
 
16.b) Maximizar Z = 4X1 + 7X2 
Sujeito a: 
 
 
 
 
16.c) Maximizar Z = 4X1 + 3X2 
Sujeito a: 
 
 
 
 
16.d) Maximizar Z = 5X1 + 6X2 
Sujeito a: 
 
 
 
 
 
 
 
 
4X1 + 7X2  336 
6X1 + 3X2  252 
X1  0 e X2  0 
 
4X1 + 8X2 384 
5X1 + 7X2  420 
X1  0 e X2  0 
 
3X1 + 2X2 15 
2X1 + X2  8 
X2  6 
X1  0 e X2  0 
 
6X1 + 4X2 9 
X1 + 2X2  6 
X1  3 
X1  0 e X2  0 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
69 
16.e) O problema consiste em programar a produção de dois itens P1 e P2 a partir dos 
recursos produtivos R1, R2 e R3. Os dados colhidos nos vários setores da empresa são os 
seguintes: 
PRODUTOS R1 por unidade R2 por unidade R3 por unidade 
P1 2 4 1 
P2 3 2 5 
Disponibilidade mensal 3000 4000 4500 
PRODUTOS Custo unitário Custo de venda Preço de venda 
P1 20 20% do PV 50 
P2 30 20% do PV 70 
Demanda conjunta dos produtos não deve exceder 1000 unidades/mês. O objetivo é 
maximizar o lucro. 
 Construa o modelo de programação linear e obtenha a solução ótima através do 
método simplex. 
 
 
17) Resolva os problemas abaixo através do método da Za Artificial 
 
17.a) Minimizar Z = 3X1 + 4X2 
Sujeito a: 
5X1 +3 X2  14 
2X1 + 7X2  11 
 X1 0; X2  0 
 
17.b) Minimizar C = 2X1 + 5X2 
Sujeito a: 
2X1 +3 X2  12 
7X1 + 4X2 ≤ 28 
 X1 0; X2  0 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
70 
17.c) Maximizar Z = 2X1 - 3X2 + 5X3 
Sujeito a: 
2X1 - 1X2 +3X3  4 
3X1 - X2 + 2X3  7 
X1 + 2X2  6 
X1 0; X2  0; X3  0 
 
17.d) Em uma dieta, quatro tipos de alimentos são utilizados, e estes necessitam vir de um 
grupo básico de alimentos (bolo de chocolate, sorvete, refrigerante e pão-de-queijo). Para a 
situação presente quatro tipos de alimentos podem ser consumidos: panetone, sorvete de 
chocolate, coca-cola e pão-de-queijo com recheio de abacaxi. Cada panetone custa 50 
centavos, cada sorvete de chocolate custa 20 centavos, cada unidade de coca-cola custa 30 
centavos e cada pão-de-queijo com recheio de abacaxi custa 50 centavos. É necessário ingerir 
no mínimo 500 calorias por dia, 6 onças
*
 de chocolate, 10 onças de açúcar e 8 onças de 
gordura. O conteúdo nutricional de cada alimento é apresentado na tabela abaixo. 
Alimento Calorias Chocolate 
(onças) 
Açúcar (onças) Gordura 
(onças) 
Panetone 400 3 2 2 
Sorvete 200 2 2 4 
Coca-cola 150 0 4 1 
Pão-de-queijo 500 0 4 5 
Formule o modelo de programação linear, e determine quantas unidades de panetone, 
sorvete, coca-cola e pão-de-queijo recheado de abacaxi devem ser consumidos por dia ao 
menor custo possível? *Cada onça equivale a 28,35g 
 
 
 
 
 
 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
71 
18) Dado o problema de programação linear a seguir: 
 
Maximizar Z = 2100X1 + 1200X2 + 600X3 
Sujeito a: 
6X1 + 4X2 +6X3  3760 (Horas de Máquina) 
12X1 +16X2 +2X3 9520 (Horas de Mão-de-obra) 
X1  380 (Demanda de P1) 
X2  400 (Demanda de P2) 
X3  480 (Demanda de P3) 
X1 0; X2  0; X3  0 
 
a) Calcule a solução ótima do problema utilizando o método simplex.. 
b) Qual a utilização dos recursos horas de máquina e horas de mão-de-obra? 
c) A demanda dos produtos P1, P2 e P3 é completamente atendida? Justifique sua 
resposta. 
d) Se houver falta de uma hora de mão-de-obra quanto teremos de prejuízo? 
e) Qual a importância de conhecermos as utilidades marginais (preço de 
oportunidade/preço sombra de cada recurso produtivo? Quais são as utilidades 
marginais dos recursos produtivos (máquinas e mão-de-obra) e das demandas (P1, P2 
e P3)? 
f) Caso pudéssemos produzir mais uma unidade de produto (P1, P2 e P3), qual seria a 
melhor opção? Por quê? 
g) Caso pudéssemos acrescentar mais uma hora em algumas das seções (máquina/mão-
de-obra), qual seria a melhor alternativa? Por quê? 
h) Quais são os recursos escassos do processo produtivo? 
i) Verifica-se que a demanda de alguns produtos não é completamente atendida. 
Identifique esses produtos e explique o que poderia ser feito nesse caso para minimizar 
os custos. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
72 
j) Para um engenheiro de produção qual é a importância de se fazer as interpretações 
econômicas dos resultados obtidos através do simplex? 
 
 
19) Dado o seguinte modelo: 
Maximizar Z = 1X1 + 1X2 
Sujeito a: 
4X1 + 2X2  8 (Recurso 1) 
3X1 + 5X2  15 (Recurso 2) 
X1 0; X2  0 
 
a) Achar a solução ótima pelo método simplex. 
b) Caso o Recurso 1 tenha uma redução de 8 para 7 unidades, quais as variações no valor 
ótimo de Z das variáveis X1 e X2? 
 
20) Uma empresa fabricante de móveis produz três modelos α, β e γ, cuja produção semanal 
deseja programar. As margens unitárias do lucro dos modelos são, respectivamente, $20, $8 e 
$3. Ambos os modelos passam por 3 seções da fábrica ( seção 1, seção 2 e seção 3), 
conforme os coeficientes unitários de utilização mostrados no modelo abaixo. As seções 
dispõem das seguintes capacidades semanais de trabalho, respectivamente: 240 homens-hora, 
320homens-hora e 480 homens-hora. 
 
Maximizar Z = 20X1 + 8X2 + 3X3 
Sujeito a: 
4X1 + X3  240 (seção 1) 
4X1 +2X2 +2X3  320 (seção 2) 
3X1 +4X2  480 (seção 3) 
X1 0; X2  0; X3  0 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
73 
 O quadro abaixo mostra os resultados do processo de solução do método simplex. 
V.B. Z X1 X2 X3 X4 X5 X6 T.I 
Z 1 0 0 6 1 4 0 1520 
 0 1 0 0.25 0.25 0 0 60 
 0 0 1 0.5 0.5 0.5 0 40 
 0 0 0 -2.75 1.25 -2 1 140 
 
 
Pede-se: 
a) Identifique as variáveis do problema. 
b) Complete o quadro indicando as variáveis que estão na base. 
c) Escreva a solução ótima que o quadro acima indica. 
d) Na solução ótima do problema, identificar as utilidades marginais das três seções 
utilizadas no processo de produção da empresa. 
e) Caso a empresa possa acrescentar mais 60 homens-hora em alguma seção qual seria a 
escolhida? Por quê? 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
3. DUALIDADE 
 
Em determinadas situações, a quantidade de cálculos necessária para resolver um 
modelo linear pelo método Simplex pode ser reduzida. O modelo inicial chamado Primal 
pode ser substituído por outro modelo chamado Dual, cuja solução é mais rápida. Uma vez 
conhecida a solução do Dual, conhece-se em conseqüência a solução do Primal, o que resolve 
o problema. 
 Todo problema de programação linear, chamado Primal, possui um segundo problema 
associado chamado Dual. Ambos são completamente inter-relacionados, de forma que a 
solução ótima de um fornece informações completas sobre o outro. 
 A cada modelo de programação linear contendo coeficiente aij, bj e cj corresponde um 
outro modelo denominado Dual, formado por esses mesmos coeficientes, porém dispostos de 
maneira diferente. 
 O problema Dual, para modelos de programação linear na forma padrão (todas as 
restrições são desigualdades do tipo ), é construído a partir do Primal da seguinte forma: 
a) A função-objetivo do dual é de minimização, ao passo que a do primal é de 
maximização. 
b) Os termos constantes das restrições do dual são coeficientes da função-objetivo do 
primal. 
c) Os coeficientes da função-objetivo do dual são os temos constantes das restrições 
do primal. 
d) As restrições do dual são do tipo , ao passo que as restrições do primal são do 
tipo . 
e) O número de incógnitas (variáveis) do dual (m valores de yi) é igual ao número de 
restrições do primal. 
f) O número de restrições do dual é igual ao número de incógnitas (variáveis) do 
primal (n valores de xj). 
g) A matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do 
primal. 
h) As variáveis de ambos os problemas são não-negativas. 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
75 
Seja o problema Primal assim definido: 
 
nnxcxcxcZMax  .... 2211
 
Sujeito a: 
),...,2,1(0
...
...
...
...
...
2211
222222121
111212111
njx
ybxaxaxa
ybxaxaxa
ybxaxaxa
j
mmnmnmm
nn
nn







 
 
Onde: 
i – número de linhas (m – número de linhas) 
j – número de colunas (n – número de colunas) 
 
 Associando-se a cada restrição i do primal uma variável yi, o problema dual é assim 
definido: 
 
mmybybybDMin  .... 2211
 
Sujeito a: 
),...,2,1(0
...
...
...
...
...
2211
22222112
11221111
miy
cyayaya
cyayaya
cyayaya
i
nmmnnn
mm
mm




 
 
 
 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
76 
Exemplo 1: 
Seja o seguinte problema, que será chamado de Primal: 
Max Z = 2X1 + 3X2 + X3 
Sujeito a: 3X1 + 4X2 + 2X3  10 
 2X1 + 6X2 + X3  20 
 X1 – X2 – X3  30 
 X1 0; X2 0; X3  0 
 
A obtenção do Dual se processa da seguinte maneira: para cada restrição será atribuída 
uma variável de decisão (yi). A função objetivo do Dual será de minimização e cada uma de 
suas parcelas será o produto da variável yi pelo termo da direita da restrição correspondente. 
Cada variável de decisão do Primal gera uma restrição no Dual. Neste caso o sinal será 
, e o termo da direita será o coeficiente da variável Primal na função objetivo. Todas as 
variáveis do Dual serão não negativas. Assim, o Dual será formulado da seguinte maneira: 
 
Min D = 10Y1 + 20Y2 + 30Y3 
Sujeito a: 3Y1 + 2Y2 + Y3  2 
 4Y1 + 6Y2 - Y3  3 
 2Y1 + Y2 – Y3  1 
 Y1 0; Y2 0; Y3  0 
 
 Devido a grande interligação existente entre os problemas dual e primal é de se esperar 
que seja grande a relação entre as soluções ótimas. 
 Existem algumas razões para o estudo dos problemas duais. A primeira e mais 
importante são as interpretações econômicas que podemos obter dos valores das variáveis do 
Dual na solução ótima, tais como variações marginais. A segunda está ligada ao número de 
restrições. O problema dual apresenta um número menor de restrições. Computacionalmente 
falando é, algumas vezes, mais eficiente resolver o problema dual (dependendo do número de 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
77 
restrições e de variáveis) do que o primal correspondente, já que obtendo a solução ótima de 
um estaremos obtendo a do outro. 
 ** Como a solução de um problema pode ser obtida pela solução do outro, em alguns 
casos torna-se mais eficiente resolver o dual, já que grande parte da dificuldade 
computacional do Método Simplex é dependente do número de restrições, e não do número de 
variáveis. 
 
3.1. Teoremas da Dualidade 
 
Teorema I – O dual do dual é o primal. 
 
21 25. xxZMax 
 
Sujeito a: 
0;0
)(92
)(4
)(3
21
321
22
11




xx
yxx
yx
yx
 Primal 
 
321 943. yyyDMin 
 
Sujeito a: 
0;0;0
)(22
)(5
321
232
131



yyy
xyy
xyy
 Dual 
 
Calculando o dual do dual, teremos novamente o primal. 
 
21 25. xxZMax 
 
Sujeito a: 
0;0
92
4
3
21
21
2
1




xx
xx
x
x
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
78 
 
Logo, o dual do dual é o primal. 
 
 
Teorema II - Se a restrição K do primal é uma igualdade, então a variável yK do dual é sem 
restrição de sinal (yK será uma variável livre). A restrição do tipo igualdade pode também ser 
substituída por duas outras variáveis com sinais contrários. 
 
 
 
21 25. xxZMax 
 
Sujeito a: 
0;0
)(142
)(92
21
321
321



xx
yxx
yxx
 Primal 
 
Para o cálculo do dual y1 será uma variável livre. 
 
21 149. yyDMin 
 
Sujeito a: 
0;
222
5
21
21
21



ylivrey
yy
yy
 Dual 
 
 
Teorema III – Se a variável p do primal é sem restrição de sinal (variável livre), então a 
restrição p do dualserá uma igualdade. 
 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
79 
321 2. xxxZMax 
 
Sujeito a: 
0;;0
)(2043
)(102
321
3321
321



xlivrexx
yxxx
yxx
 Primal 
 
Para o cálculo do dual, como x2 é uma variável livre, a restrição correspondente será uma 
igualdade. 
 
21 2010. yyDMin 
 
Sujeito a: 
0;0
2
142
13
21
2
21
21




yy
y
yy
yy
 Dual 
 
 
OBSERVAÇÕES: 
* Se o objetivo de um problema é maximizar, o do outro será minimizar, e vice-versa. 
* O problema de maximização tem restrições do tipo  e o problema de minimização 
tem restrições do tipo . 
 Existem duas maneiras de preparar o primal para se poder obter o dual: 
1) Transformando a função-objetivo em maximização e as restrições  em  (isto é, 
inverter o sinal da restrição multiplicando toda a inequação por -1). Em outras 
palavras, deixar o problema primal com função-objetivo de maximização e não 
permitir que nenhuma de suas restrições seja do tipo . 
2) Deixar o problema primal com função-objetivo de minimização, e não permitir que 
nenhuma restrição seja do tipo . Em outras palavras, inverter o sinal da restrição 
 multiplicando a inequação por –1. 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
80 
Exemplo 2: 
Seja o seguinte problema primal. 
321 25. xxxZMin 
 
Sujeito a: 
0;0;0
8423
9
4
321
321
32
1




xxx
xxx
xx
x
 
 
3.2. Método Dual-Simplex 
 
 Em alguns caso pode-se resolver diretamente o Dual introduzindo as variáveis de 
excesso e as variáveis artificiais ao modelo de programação linear, e então, aplicar o método 
da Função-Objetivo Auxiliar/Artificial. 
 
Max Z = 2X1 + X2 
Sujeito a: X1 + 5X2 + 2X3  10 
 X1 + 3X2  6 
 2X1 + 2X2 – X3  30 
 X1 0; X2 0 
Min D = 10Y1 + 6Y2 + 8Y3 
Sujeito a: Y1 + Y2 + 2Y3  2 
 5Y1 + 3Y2 + 20Y3  1 
 Y1 0; Y2 0; Y3  0 
 
 O método Dual-Simplex trata diretamente com soluções compatíveis básicas do primal 
e piores que a solução ótima, procurando otimizá-lo. Ele está ao mesmo tempo tratando 
indiretamente com soluções básicas incompatíveis do dual porém “melhores que a sua 
solução ótima”, procurando compatibilizá-lo. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
81 
 O método Dual-Simplex lida diretamente com soluções básicas incompatíveis porém 
“melhores que a ótima”, e procura achar a compatibilidade do problema. Ele lida com um 
problema exatamente como se o método simplex estivesse sendo, simultaneamente, aplicado 
ao seu problema dual. 
 O método Dual-Simplex é bastante empregado em análise de sensibilidade, quando 
são feitas pequenas modificações no modelo. Além disso, algumas vezes é mais fácil começar 
com uma solução básica incompatível, porém “melhor que a ótima” e procurar a 
compatibilidade, do que obter uma solução compatível básica inicial e depois otimizá-la como 
e faz no método Simplex. 
 
Resumo do Método 
 Assumindo que a função-objetivo é de maximização, o método Dual-Simplex 
envolverá as seguintes etapas: 
 a) Introduzir as variáveis de folga e achar uma solução básica inicial tal que todos os 
coeficientes da linha da função-objetivo (Z/D) do quadro inicial, estando a função-objetivo 
somente em função das variáveis não básicas, sejam  0. Se esta solução for compatível então 
ela já é a solução ótima. 
 b) Retirar da base aquela variável que for mais incompatível, isto é, aquela que tiver o 
menor valor negativo (maior valor absoluto com sinal negativo). 
 c) Introduzir na base aquela variável cujo coeficiente na linha da função-objetivo 
atingir zero mais rapidamente (menor valor absoluto) quanto um múltiplo da equação 
contendo a variável que sai for somado à linha da função-objetivo. 
 d) Achar uma nova solução básica e colocar a função-objetivo somente em função das 
variáveis não-básicas. Se esta solução for compatível, isto é, se todos os valore bi (termo 
independente) forem  0, ela é a solução ótima. Caso contrário, volte ao passo (b). 
 As diferenças com relação ao método Simplex se resumem nas regras de entrada e 
saída de variáveis da base, que são as seguintes: 
a) Variável que sai: é a variável básica com o valor mais negativo. Se todas as 
variáveis básicas tiverem valores positivos, a solução é ótima. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
82 
b) Variável que entra: é escolhida entre as variáveis fora da base, da seguinte forma. 
b1) Dividir os coeficientes do lado esquerdo da equação Z-transformada pelos 
correspondentes coeficientes negativos da equação da variável que sai; 
b2) A variável que entra é a que tem o menor valor entre os quocientes 
encontrados (problemas de minimização) ou o menos valor absoluto 
(problemas de maximização). 
 Quando, em ambos os casos, não houver coeficientes negativos na linha da variável 
que sai da base, o problema não tem solução viável. 
 
Exemplo 3: 
Resolver o problema abaixo usando o método Dual-Simplex 
Min D = 3Y1 + 4Y2 + 9Y3 
Sujeito a: Y1 + Y3  5 
 Y2 + 2Y3  2 
 Y1 0; Y2 0; Y3  0 
 
 
3.3. Analogia entre as Soluções Primal e Dual 
 
 a) A cada solução viável básica primal não ótima corresponde uma solução básica 
inviável dual. 
 b) A cada solução ótima primal corresponde à solução ótima dual com Z = D. 
 c) O coeficiente da variável de decisão na função-objetivo primal é o valor da variável 
de folga correspondente na solução dual. 
 d) O coeficiente da variável de folga da função-objetivo primal é o valor da variável de 
decisão correspondente na solução dual. (Coeficiente de XFi = Valor de Yi). 
 Como o primal é o dual do próprio dual, vale o raciocínio no sentido dual → primal: 
 Coeficiente de Yi = Valor de XFi 
 Coeficiente de XFi = Valor de Xi 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
83 
 
Exemplo 4: 
Max Z = X1 + 2X2 + 3X3 
Sujeito a: X1 + X2 + X3 ≤ 10 
 2X1 + X2 + 4X3 ≤ 12 
 X1 + 3X2 - X3 ≤ 9 
 X1 0; X2 0; X3  0 
 Dado um problema de programação linear, podemos escolher entre solucionar o 
modelo primal ou o modelo dual correspondente. A escolha leva em consideração o esforço 
computacional, que depende do número de restrições, variáveis artificiais, etc. 
 O modelo dual correspondente é: 
Min D = 10Y1 + 12Y2 + 9Y3 
Sujeito a: Y1 + 2Y2 + Y3  1 
 Y1 + Y2 + 3Y3  2 
 Y1 + 4Y2 - Y3  3 
 Y1 0; Y2 0; Y3  0 
 
 Colocando as variáveis de folga no primal, temos: 
Z -X1 -2X2 -3X3 = 0 
 X1 +X2 +X3 +X4 (XF1) = 10 
 2X1 +X2 +4X3 +X5(XF2) = 12 
 X1 +3X2 -X3 +X6(XF3) = 9 
 
 Solução Básica Inicial – Viável 
V.B. Z X1 X2 X3 X4 X5 X6 T.I 
Z 1 -1 -2 -3 0 0 0 0 
X4 0 1 1 1 1 0 0 10 
X5 0 2 1 4 0 1 0 12 
X6 0 1 3 -1 0 0 1 9 
 
 
 
 
__________________________________________________________________________Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
84 
Solução Básica Inicial: 
Z = 0 
X1 = 0 
X2 = 0 
X3 = 0 
X4 = 10 
X5 = 12 
X6 = 9 
Colocando as variáveis de folga no dual temos: 
 
Max (-D )= -10Y1 - 12Y2 - 9Y3 
Sujeito a: -Y1 - 2Y2 - Y3 ≤ -1 
 - Y1 - Y2 - 3Y3 ≤ -2 
 - Y1 - 4Y2 + Y3 ≤ -3 
 Y1 0; Y2 0; Y3  0 
 
-D +10Y1 +12Y2 +9Y3 = 0 
 -Y1 -2Y2 -Y3 +Y4 (YF1) = -1 
 -Y1 -Y2 -3Y3 +Y5(YF2) = -2 
 -Y1 -4Y2 +Y3 +Y6(YF3) = -3 
 
 Solução Básica Inicial – Viável 
V.B. D Y1 Y2 Y3 Y4 Y5 Y6 T.I 
D -1 10 12 9 0 0 0 0 
Y4 0 -1 -2 -1 1 0 0 -1 
Y5 0 -1 -1 -3 0 1 0 -2 
Y6 0 -1 -4 1 0 0 1 -3 
 
Solução Básica Inicial: 
D = 0 
Y1 = 0 
Y2 = 0 
Y3 = 0 
Y4 = -1 
Y5 = -2 
Y6 = -3 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
85 
 Correspondência Primal → Dual 
PRIMAL DUAL 
Coeficiente de X1 = -1 
Coeficiente de X2 = -2 
Coeficiente de X3 = -3 
Coeficiente de X4 = 0 (XF1) 
Coeficiente de X5 = 0 (XF2) 
Coeficiente de X6 = 0 (XF3) 
 
Valor de Y4 = -1 (YF1) 
Valor de Y5 = -2 (YF2) 
Valor de Y6 = -3 (YF1) 
Valor de Y1 = 0 
Valor de Y2 = 0 
Valor de Y3 = 0 
COEFICIENTE NA FUNÇÃO-OBJETIVO TERMO INDEPENDENTE 
Valor de X1= 0 
Valor de X2 = 0 
Valor de X3 = 0 
Valor de X4 =10 (XF1) 
Valor de X5 = 12 (XF2) 
Valor de X6 = 9 (XF3) 
Coeficiente de Y4 = 0 (YF1) 
Coeficiente de Y5 = 0 (YF2) 
Coeficiente de Y6 = 0 (YF3) 
Coeficiente de Y1 = 10 
Coeficiente de Y2 = 12 
Coeficiente de Y3 = 9 
TERMO INDEPENDENTE COEFICIENTE NA FUNÇÃO-OBJETIVO 
Z = 0 D = 0 
 
 O quadro a seguir fornece a solução ótima do modelo primal. 
V.B. Z X1 X2 X3 X4 X5 X6 T.I 
Z 1 1,077 0 0 0 0,846 0,385 13,615 
X4 0 0,154 0 0 1 -0,308 -0,231 4,231 
X3 0 0,385 0, 1 0 0,231 -0,077 2,077 
X2 0 0,461 1 0 0 0,077 0,308 3,692 
 Solução ótima do modelo primal: 
 
Variáveis Básicas Variáveis Não-Básicas Valor de Z 
X2 = 3,692 (Y5) X1 = 0 (Y4) Z = 13,615 
X3 = 2,077 (Y6) X5 = 0 (Y2) 
X4 = 4,231 (Y1) X6 = 0 (Y3) 
 
 Relembrando: 
 - Cada variável de decisão primal equivale a uma variável de folga dual; e 
 - Cada variável de folga primal equivale a uma variável de decisão dual. 
 
X1 = Y4 X4 = Y1 Z = D 
X2 = Y5 X5 = Y2 
X3 = Y6 X6 = Y3 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
86 
 
 Usando a correspondência descrita anteriormente, podemos montar o quadro de 
solução ótima do dual. 
 
V.B. D Y1 Y2 Y3 Y4 Y5 Y6 T.I 
D -1 4,231 0 0 0 3,692 2,077 -13,615 
Y4 0 0 0 1 1,077 
Y2 0 1 0 0 0,846 
Y3 0 0 1 0 0,385 
 
 Solução ótima do modelo dual: 
 
Variáveis Básicas Variáveis Não-Básicas Valor de D 
Y4 = 1,077 Y1 = 0 D = -13,615 
Y2 = 0,846 Y5 = 0 
Y3 = 0,385 Y6 = 0 
 
 
 
3.4. Interpretação Econômica do Dual 
 
 Vamos considerar o caso da programação da produção de dois itens P1 e P2, a partir 
dos recursos R1 e R2. O quadro a seguir resume os dados: 
 
Produtos R1/Unidade R2/Unidade Lucro/Unidade 
P1 2 10 50 
P2 3 5 90 
Disponibilidade 300 1000 - 
 
 O modelo, onde X1 e X2 são as variáveis de decisão é: 
Max Lucro = 50X1 + 90X2 
Sujeito a: 2 X1 + 3X2 ≤ 300 
 10X1 +5 X2 ≤ 1000 
 X1 0; X2 0 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
87 
 O quadro final de resolução pelo método simplex, onde X4 e X5 são as sobras dos 
recursos R1 e R2 é: 
V.B. Z X1 X2 X3 X4 T.I 
Z 1 10 0 30 0 9000 
X2 0 0,67 1 0,33 0 100 
X4 0 6,65 0 -1,65 1 500 
 
 
Solução ótima: 
X1 = 0 
X2 = 100 
X3 = 0 
X4 = 500 
Z = 9000 
 
 O modelo dual correspondente á: 
Min D = 300Y1 + 1000Y2 
Sujeito a: 2Y1 + 10Y2  50 
 3Y1 + 5Y2  90 
 Y1 0; Y2 0 
 
 O quadro final de solução, derivado da solução primal é: 
V.B. D Y1 Y2 Y3 Y4 T.I 
D -1 0 500 0 100 -9000 
Y1 0 1 0 30 
Y3 0 0 1 10 
 
Solução ótima: 
Y1 = 30 
Y2 = 0 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
88 
Y3 = 10 
Y4 = 0 
D = -9000 
 
Interpretação Econômica 
 O valor Y1 (Y1=30) foi obtido do coeficiente de X3, e representa, portanto, o valor da 
oportunidade do recurso R1, isto é, cada unidade do recurso R1 tem capacidade de gerar um 
lucro de 30. 
 O valor de Y2 (Y2=0) foi obtido do coeficiente de X4, indicando o valor de 
oportunidade do recurso R2. O resultado é coerente, já que o recurso R2 não é escasso (X4 = 
500). 
 O valor de Y1 é, portanto, o valor de oportunidade por unidade do recurso R1, isto é, a 
capacidade da unidade do recurso gerar lucro, neste programa. 
 Na função-objetivo dual, cada parcela mede, então, o valor de oportunidade dos 
recursos envolvidos na produção (estoque x valor de oportunidade unitário do recurso). A 
função-objetivo dual mede, portanto, a capacidade de o estoque de recursos gerar lucro. 
 Na solução ótima, este valor coincide com o lucro atribuído aos produtos pelo 
mercado, isto é, o valor de oportunidade dos produtos no mercado. 
 Cada uma das restrições compara o valor de oportunidade atribuído aos produtos pelos 
recursos, com o valor de oportunidade atribuído aos produtos pelo mercado. 
 Na primeira restrição, por exemplo, 2y1 + 10y2 está indicando que o produto P1, que 
usa 2 unidades de R1 e 10 de R2, tem esse valor de oportunidade calculado em termos desses 
produtos. O lado esquerdo, 50, indica o valor de oportunidade atribuído pelo mercado. Esse 
valor é também chamado de valor externo, em contraposição ao valor atribuído pelos 
recursos, chamado valor inteiro. 
 Quando a remuneração do mercado (valor externo) cobre o valor interno, o produto é 
fabricado (a diferença XFi = 0, portanto Xi é básico). Se o valor de mercado for menor que o 
valor interno, o produto não será fabricado. Isto quer dizer que existe uso alternativo para os 
recursos no programa, que é capaz de gerar lucro e equivalente o seu valor de oportunidade. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
89 
3.5. Exercícios 
 
1) Construa o modelo dual para os problemas de programação linear a seguir: 
 
1.a) Max L = 12X1 + 30X2 + 3X3 
Sujeito a: 3X1 + 5X2 + X3 ≤ 14 
 2X1 + 6X2 ≤ 10 
 X1 0; X2 0; X3  0 
 
1.b) Max Z = 4X1 + 6X2 + 5X3 
Sujeito a: 2X1 + 5X2 + 3X3 ≤ 23 
 X1 + 3X2 + 4X3 ≤ 19 
 X1 0; X2 0; X3  0 
 
1.c) Min C = 13X1 + 12X2 + 11X3 
Sujeito a: 3X1 + 5X2 + 4X3 ≤ 33 
 4X1 + 2X2 + 3X3 ≤ 28 
 X1 0; X2 0; X3  0 
 
1.d) Max Z = 13X1 + 14X2 + 3X3 
Sujeito a: 2X1 + 3X2 + 3X3 = 31 
 4X1 + X2 + 3X3 = 21 
 X1 + 5X2 = 22 
 X1 0; X2 0; X3  0 
 
1.e) Min Z = 15x1 + 10x2 + 8x3 
Sujeito a: X1 + 3X2 + 7X3 = 24 
 6X1 + 4X2 + 3X3 = 22 
 3X1 + 5X2 + 4X3 = 26 
 X1 0; X2 0; X3  
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
901.f) Maximizar Z = X1 + X2 + X3 + X4 + X5 
Sujeito a: X1 + X2  2 
 X2 + X4  3 
 X1 + X4 + X5  5 
 X2 + 3X4  3 
 X1 – 2X3 –X5  4 
 X1 0; X2 0; X3 0; X4 0; X5 0; 
 
 
2) A Óleos Unidos S.A é uma empresa no ramo de derivados de petróleo que manufatura três 
combustíveis especiais a partir da mistura de dois insumos: um extrato mineral e um solvente. 
A proporção da mistura está descrita na tabela a seguir. 
 Combustível A Combustível B Combustível C 
Extrato Mineral 8 litros 5 litros 4 litros 
Solvente 5 litros 4 litros 2 litros 
 
 A Óleos Unidos tem disponível 120 litros/dia de extrato mineral e 200 litros/dia de 
solvente, e que a demanda total dos três combustíveis não supera as disponibilidades dos 
recursos produtivos e os lucros líquidos esperados para os três combustíveis são de 
respectivamente, R$ 20,00, R$ 22,00 e R$ 18,00. A Óleos Unidos S/A deseja saber qual a 
quantidade diária a ser produzida dos três tipos de combustíveis. 
 Pede-se: Construa o modelo de programação linear (Primal), escreva o Dual e encontre 
a solução ótima do Dual, utilizando o Método Dual-Simplex. 
 
 
3) Para os problemas a seguir construa o modelo dual e resolva utilizando o método 
Dual-Simplex: 
 
3.a) Max Z = 4X1 + 5X2 
Sujeito a: 4X1 + 7X2 ≤ 336 
 6X1 + 3X2 ≤ 252 
 X1 0; X2 0 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
91 
3.b) Max L = 6X1 + 11X2 
Sujeito a: 4X1 + 10X2 ≤ 150 
 7X1 + 9X2 ≤ 200 
 X1 0; X2 0 
3.c) Min C = 9X1 + 8X2 
Sujeito a: 4X1 + 2X2 ≥ 14 
 2X1 + 6X2 ≥ 22 
 X2 ≥ 3 
 X1 0; X2 0 
 
 
4) Dado modelo dual a seguir: 
 
Max D = 600Y1 + 500Y2 + 800Y3 
Sujeito a: 50Y1 + 20Y2 +10 Y3 ≤ 200 
 20Y1 + 30Y2 +30 Y3 ≤ 150 
 10Y1 + 20Y2 + 50Y3 ≤ 240 
 Y1 0; Y2 0; Y3  0 
 
 O quadro a seguir representa a solução ótima dual, obtida através do método simplex: 
 
V.B. D Y1 Y2 Y3 Y4 Y5 Y6 T.I 
D 1 0 315,38 0 1,54 26,15 0 4230,77 
Y4 0 1 0,23 0 0,02 -0,01 0 3,46 
Y2 0 0 0,85 1 -0,02 0,04 0 2,69 
Y3 0 0 -24,62 0 0,54 -1,85 1 70,70 
 
 Usando a correspondência entre as soluções primal → dual (dual → primal) monte o 
quadro de solução ótima do primal. 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
92 
5) O quadro a seguir representa a solução ótima primal de um determinado problema de 
programação linear. 
 
V.B. Z X1 X2 X3 X4 X5 T.I 
Z 1 240 0 30 30 0 3.000.000 
X2 0 10 1 5 1 0 100.000 
X5 0 -660 0 -150 -60 1 2.100.000 
 
 Use a correspondência primal → dual (dual → primal) para montar o quadro de 
solução ótima do modelo dual. 
6) Um distribuidor dispõe de um armazém com 100.000 m
3
 para estocar produtos para venda 
futura. Ele dispõe de 30.000.000 u.m para a compra, e pretende adquirir três produtos de 
modo a maximizar seus lucros. Os dados estão na tabela seguinte: 
 
Produtos Custo Unitário Preço Unitário de Venda Espaço para estocagem 
em m
3
 
P1 240 300 10 
P2 90 120 1 
P3 300 420 5 
Pede-se: 
 a) Construa o modelo de programação linear do problema, em que, Xi, representa as 
decisões de compra dos produtos Pi, XF1 folga do capital e XF2 folga do espaço para 
estocagem. 
 b) Construa o modelo dual correspondente. 
 c) Resolva pelo método simplex o modelo primal e construa o quadro de solução 
ótima do modelo dual. 
 d) Qual a composição de compra que melhor serve ao distribuidor? 
 e) O que significa a função-objetivo dual? 
 f) O que significam as variáveis de decisão dual? 
 g) O que significam as variáveis de folga duais? 
 h) Considere a primeira restrição primal: o que mede seu lado esquerdo? E o lado 
direito? 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
93 
 i) Considere a segunda restrição dual: o que mede seu lado esquerdo? E o lado direito? 
 j) Qual a conseqüência para o plano ótimo se tivéssemos mais 1 m
3
 de espaço de 
estocagem, a um custo de 20 u.m? Por quê? 
 k) O que ocorre com a solução ótima, se dispuséssemos de mais 100 u.m a um custo 
de 10%? Por quê? 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
4. PROGRAMAÇÃO INTEIRA 
 
Um problema de programação inteira é um problema de programação linear com o 
requisito adicional de que o valor de uma ou mais variáveis de decisão sejam números 
inteiros. Esses problemas podem apresentar dois tipos básicos: 
 Programação Inteira Total – todas as variáveis de decisão são do tipo inteiro. 
 Programação Inteira Mista – apenas uma parte das variáveis são do tipo inteiro, 
enquanto outras são do tipo real. 
A todo problema de programação linear inteira está associado um problema com a 
mesma função-objetivo e as mesmas restrições, com exceção da condição de variáveis 
inteiras. A este problema se dá o nome de Problema Relaxado. 
 
Maximizar Z = 3X1 + 3X2 
Sujeito a: 
 2X1 + 4X2  12 
 6X1 + 4X2  24 
 X1 0; X2  0 
 X1 e X2 inteiros 
Programação Linear Inteira 
 
Maximizar Z = 3X1 + 3X2 
Sujeito a: 
 2X1 + 4X2  12 
 6X1 + 4X2  24 
 X1 0; X2  0 
Problema Relaxado/Programação Linear 
 
 
 A primeira idéia que pode vir à mente é a de resolver o problema como se fosse um 
problema de programação linear e truncar os valores ótimos encontrados para cada uma das 
variáveis de decisão. Para problemas de grande porte, isso geralmente resultará numa solução 
aceitável (próxima ao ótimo real) sem a violação de nenhuma restrição. Para problemas 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
95 
menores, este tipo de procedimento geralmente nos levará a soluções inaceitáveis, às vezes 
longe do valor ótimo. 
Em consequência, a primeira aproximação da solução de qualquer problema de 
programação inteira pode ser obtida ignorando-se o requisito de valores inteiros e resolvendo-
se o problema de programação linear resultante por meio de uma das técnicas de programação 
linear já conhecidas. 
 Se acontecer da solução ótima ao problema de programação linear ser inteira, então 
esta solução é também solução ótima ao problema de programação inteira original. Caso 
contrário, e esta é a situação usual, pode-se arredondar os componentes da primeira 
aproximação aos valores inteiros viáveis mais próximos e obter uma segunda aproximação. 
Este procedimento é frequentemente posto em prática, especialmente quando a primeira 
aproximação envolve grandes números, mas pode ser impreciso quando os números são 
pequenos. 
 Diversos são os problemas que podem ocorrer pela utilização da técnica de 
arredondamento da solução do problema de programação linear. Entre eles podemos citar: 
 Nenhum ponto inteiro vizinho ao ponto ótimo é necessariamente viável. 
 Mesmo que um dos vizinhos seja viável ele pode não ser necessariamente o 
ponto ótimo inteiro. 
 A programação linear inteira possibilita resolver problemas que não seriam 
adequadamente resolvidos pela Programação Linear, visto exigirem valores inteiros como 
resposta. 
 Uma idéia que pode resultar em uma solução para um problema de programaçãointeira é o de se enumerar todas as possíveis soluções. De forma exaustiva todos os valores 
possíveis para a função-objetivo são calculados e é escolhido aquilo que apresenta o maior 
valor, no caso de maximização, ou o menor valor, no caso de minimização. 
 O problema está no fato de que ela só consegue ser aplicada a problemas pequenos. O 
número de combinações possíveis cresce de forma exponencial, isto é, de forma muito rápida. 
 Em um problema de MAXIMIZAÇÃO, o valor ótimo da função-objetivo do problema 
relaxado sempre representa um limite superior ao respectivo valor do problema inteiro. Em 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
96 
um problema de MINIMIZAÇÃO, o valor ótimo da função-objetivo de um problema relaxado 
sempre representa um limite inferior ao respectivo problema inteiro. 
 Uma outra observação importante está no fato de que cada solução viável resulta num 
problema de maximização, em um limite inferior para o valor ótimo da função-objetivo. Em 
um problema de minimização cada solução viável resulta num limite superior para o valor 
ótimo da função-objetivo. 
Por exemplo, em um modelo de aquisição de equipamentos (máquinas, caminhões, 
navios, etc.) o resultado somente pode ser inteiro e a alternativa de se resolver o problema 
pela programação linear com posterior arredondamento não produz um resultado ótimo, caso 
os valores ótimos das variáveis sejam pequenos. Assim, se o resultado de um modelo implicar 
a aquisição de 2,6 tratores, 1,6 caminhões e 3,2 máquinas de beneficiamento, o 
arredondamento pode levar a uma solução não ótima. O mesmo problema, se resolvido pela 
técnica de programação linear inteira, pode levar a resultados bastante diferentes do 
arredondamento. Por outro lado, se o resultado de um problema de programação linear 
implicar valores grandes, o arredondamento pode ser feito sem nenhum receio. Assim, se um 
modelo mostrar como solução que uma empresa deve fabricar 254,8 caixas por semana, o 
arredondamento para 255 certamente é o resultado ótimo, mesmo se o problema for resolvido 
por programação linear inteira. 
 De maneira geral, o problema passível de solução por programação inteira deve 
apresentar as seguintes características: 
a) Função-objetivo linear; 
b) Restrições lineares; 
c) Variáveis positivas; 
d) Algumas (ou todas) variáveis inteiras. 
Quando o problema envolve apenas duas variáveis de decisão, a solução ótima de um 
problema de programação linear inteira pode ser encontrada graficamente. Diversos 
algoritmos são utilizados para a solução de problemas de programação linear inteira, dentre 
eles podemos citar: o algoritmo Branch-and-Bound (algoritmo da bifurcação e limite), o 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
97 
algoritmo de Gomory (algoritmo de corte), o algoritmo de transportes, os modelos de 
designação, entre outros. 
 
4.1. Método Branch-and-Bound (Algoritmo de Bifurcação e Limite) 
 
 O método denominado de Branch-and-Bound baseia-se na idéia de desenvolver uma 
enumeração inteligente dos pontos candidatos à solução ótima inteira de um problema. O 
termo Branch refere-se ao fato de que o método efetua partições no espaço das soluções. O 
termo Bound ressalta que a prova de otimalidade da solução utiliza-se de limites calculados ao 
longo da enumeração. 
 
4.1.1. Bifurcação 
 
 Se a primeira aproximação contém uma variável não inteira, por exemplo, xj então i1  
xj  i2, onde i1 e i2 são inteiros consecutivos e não negativos. Dois novos modelos de 
programação inteira são então criados aumentando o problema de programação inteira 
original com a restrição xj  i1 ou com a restrição xj  i2. Este processo chama-se 
BIFURCAÇÃO, e tem o efeito de contrair a região viável de um modo que elimina de 
considerações posteriores a solução corrente não inteira para xj preservando ainda todas as 
possíveis soluções inteiras do problema original. 
 Obtêm-se as primeiras aproximações dos dois modelos de programação inteira gerados 
pelo processo de bifurcação, ignorando-se novamente os requisitos sobre valores inteiros, e 
resolvendo-se os modelos de programação linear resultantes. Se alguma das primeiras 
aproximações continua a ser não inteira, então o problema de programação inteira originado 
por esta primeira aproximação torna-se candidato a uma bifurcação adicional. 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
98 
4.1.2. Limite 
 
 Admita-se que a função-objetivo deva ser maximizada. A bifurcação continua até ser 
obtida uma primeira aproximação inteira (que é uma solução ao problema de programação 
inteira). O valor da função objetivo referente a esta primeira aproximação inteira torna-se um 
limite inferior para o problema e, todos os modelos, cujas primeiras aproximações, inteiras ou 
não, conduzam a valores da função objetivo menores que o limite inferior, são descartados. 
 O processo de bifurcação prossegue a partir dos modelos de programação com 
primeiras aproximações não inteiras que produzam valores da função-objetivo maiores que o 
limite inferior. Se durante o processo, for descoberta uma nova solução inteira dando à 
função-objetivo um valor superior ao limite inferior corrente, então esse valor da função 
objetivo torna-se o novo limite inferior. O modelo de programação que conduziu ao antigo 
limite inferior é eliminado, bem como o são todos os modelos de programação cujas primeiras 
aproximações dêem à função objetivo valores menores que o novo limite inferior. O processo 
de bifurcação prossegue até que não haja mais modelos com primeira aproximação não inteira 
a considerar. Neste ponto, a solução correspondente ao limite inferior corrente é a solução 
ótima do problema de programação inteira original. 
 Se a função-objetivo deve ser minimizada, o procedimento permanece o mesmo, 
exceto que serão utilizados limites superiores. Assim, o valor da primeira solução inteira 
torna-se o limite superior do problema e os modelos de programação são eliminados quando 
os valores de Z de suas primeiras aproximações são maiores que o limite superior corrente. 
 
Exemplo: 
Maximizar Z = 10X1 + X2 
Sujeito a 2X1 + 5X2  11 
 X1 e X2 não negativos e inteiros 
Utilizando o método gráfico para calcular o Modelo (1) obtemos como solução X1 = 
5,5 e X2 = 0 com Z = 55. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
99 
Como não obtemos uma variável inteira na primeira aproximação (X1 = 5,5), então 
partimos para o processo de bifurcação. Tendo em vista que 5  X1  6, a bifurcação origina 
dois novos modelos de programação inteira. 
Modelo 2 
 
Maximizar Z = 10X1 + X2 
Sujeito a 2X1 + 5X2  11 
X1  5 
 X1 e X2 não negativos e inteiros 
Modelo 3 
 
Maximizar Z = 10X1 + X2 
Sujeito a 2X1 + 5X2  11 
 X1  6 
X1 e X2 não negativos e inteiros 
 
Utilizando o método gráfico para calcular os modelos (2) e (3) verificamos que não 
podemos obter no modelo (2) uma variável inteira (X2 = 0,2) e o modelo (3) não apresenta 
região viável de solução. Logo o modelo (2) é candidato a nova bifurcação. 
Como X2 = 0,2 temos: 
0  X2  1 
Acrescentamos então duas novas restrições (X2  0 e X2  1) nos dois novos modelos 
de programação inteira. 
Modelo4 
 
Maximizar Z = 10X1 + X2 
Sujeito a 2X1 + 5X2  11 
X1  5 
X2  0 
 X1 e X2 não negativos e inteiros 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
100 
Modelo 5 
 
Maximizar Z = 10X1 + X2 
Sujeito a 2X1 + 5X2  11 
 X1  6 
X2  1 
X1 e X2 não negativos e inteiros 
Utilizando o método gráfico para calcular os modelos (4) e (5) obtemos as seguintes 
soluções: 
Modelo (4): X1 = 5; X2 = 0 e Z = 50 
Modelo (5): X1 = 3; X2 = 1 e Z = 31 
Ambas as soluções apresentam todas as variáveis inteiras. De acordo com a teoria, 
quando obtemos uma primeira aproximação inteira (que é uma solução ao problema de 
programação inteira), o valor da função objetivo desta primeira aproximação torna-se um 
limite inferior para o problema, devendo ser descartados todos os modelos que conduzam a 
valores da função objetivo menores que o limite inferior. Logo o modelo 5 foi eliminado por 
causa do limite inferior. 
 
Diagrama esquemático dos resultados 
1 
Z = 55 
(5,5;0) 
3 
Não é 
viável 
 
2 
Z =50,2 
(5;0,2) 
5 
Z = 31 
(3;1) 
4 
Z = 50 
(5;0) 
X1  5 
X2  0 
 X1  6 
 X2  1 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
101 
O problema de programação inteira original está designado por um 1 no interior de um 
circulo e todos os demais modelos de programação formados por bifurcações são designados, 
por ordem de sua criação, por meio de números inteiros no interior dos círculos. Assim, os 
modelos de programação são designados, respectivamente, pelos números 2 a 5 no interior 
dos círculos. A solução de primeira aproximação de cada um dos modelos de programação 
está escrita ao pé do círculo que designa o modelo. Cada círculo (modelo de programação) é 
então conectado por uma reta ao círculo (modelo de programação) que o gerou pelo processo 
de bifurcação. A nova restrição que definiu a bifurcação é escrita acima da reta. Finalmente, 
assinala-se o círculo com uma cruz se o modelo de programação correspondente deva ser 
eliminado de considerações posteriores. Assim, o ramo 3 foi eliminado por não ser viável. O 
ramo 5, foi eliminado por causa do limite inferior. Tendo em vista que não se deixou de 
considerar nenhum ramo com solução inteira, o diagrama esquemático indica que o modelo 
de programação 1 foi resolvido com X1 = 5, X2 = 0 e Z = 50 
 
4.2. Exercícios 
 
1) Calcule a solução ótima do problema de programação inteira e esboce o diagrama 
esquemático (árvore) retratando os resultados. 
 
1.a) Maximizar Z = 3X1 + 4X2 
Sujeito a: 2X1 + X2  6 
 2X1 + 3X2  9 
 X1 e X2 não negativos e inteiros 
 
1.b) Minimizar Z = 4X1 + 3X2 
Sujeito a: 8X1 + 3X2 ≥ 24 
 5X1 + 6X2 ≥ 30 
 X1 + 2X2 ≥ 8 
 X1 e X2 não negativos e X1 inteiro 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
102 
2) A Empresa Divisão & Artes Ltda produz dois tipos de vasos de cerâmica: pequenos para 
arranjos de mesa e grandes vasos de chão. A capacidade de produção de vasos pequenos é de 
7 unidades por dia. Cada vaso grande necessita de 4 horas de secagem em estufa e um total de 
22 horas diárias de estufa está disponível. Além disso, cada vaso pequeno necessita de 2 horas 
de polimento e cada vaso grande necessita de 3 horas. Um total de 19 horas está disponível 
diariamente. Sabendo que cada vaso pequeno é vendido com um lucro de R$ 10,00 e que cada 
vaso grande é vendido com um lucro de R$ 30,00. Pede-se: 
a) Encontre a programação ótima da produção utilizando o método simplex. 
b) Encontre a programação ótima da produção utilizando o algoritmo da Bifurcação e 
Limite, definindo todas as variáveis de decisão como inteiras. 
c) Encontre a solução inteira arredondando os valores da solução encontrada no item a. 
d) Quanto de lucro a Divisão & Arte Ltda poderia perder se adotasse a solução 
encontrada no item c? 
 
3) Uma empresa industrial está planejando colocar no mercado nos próximos meses um 
sistema de ar-condicionado que ela desenvolveu. O produto será distribuído por grandes lojas 
de departamentos localizadas em São Paulo, no Rio de Janeiro e em Belo Horizonte. 
Devido à existência de custos diferentes de promoção e de distribuição, a receita realizada 
pela empresa varia em função do distribuidor. A tabela a seguir apresenta os dados relevantes 
para o problema: 
Distribuidores Receita por unidade 
vendida 
Custo estimado de 
propaganda por 
unidade vendida 
Esforço do grupo de 
vendas por unidade 
vendida (em horas) 
Loja Depto. RJ 100 10,5 2,5 
Loja Depto. BH 85 8,7 3,3 
Loja Depto. SP 70 15,3 2,2 
Sabe-se também que a empresa tem um orçamento semanal de propaganda no valor de R$ 
5000,00, além de um grupo de 20 vendedores com jornada de 40 horas por semana. A 
capacidade produtiva é de 500 unidades do produto por semana. É importante acrescentar que 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
103 
um acordo realizado com a loja de departamentos de São Paulo permite que esta receba, no 
mínimo 20% da produção realizada. 
A empresa deseja saber como realizar a colocação deste produto no mercado em termos de 
distribuição ótima semanal para cada um dos distribuidores. Pede-se: 
a) Encontre a programação ótima de produção utilizando a solução relaxada. 
b) Encontre a programação ótima de produção definindo as variáveis como inteiras. 
c) Encontre uma solução inteira arredondando os valores da solução encontrada no 
problema relaxado (item a) para a sua parte inteira. Esta solução é viável? 
 
 
4) Resolva o problema abaixo utilizando o algoritmo da bifurcação e limite e construa a 
árvore de resultados. 
Maximizar Z = X1+ 2X2 + 3X3 + X4 
Sujeito a: 
 3X1 + 2X2 + X3 + 4X4  10 
 5X1 + 3X2 + 2X3 + 5X4  5 
 X1, X2, X3 e X4  0 
X1 e X2 inteiros 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
104 
 
5. RESOLVENDO PROBLEMAS DE PROGRAMAÇÃO LINEAR NO EXCEL 
 
 
5.1 Instalando o Solver 
 
Caso a opção Solver não esteja presente no menu Ferramentas, isto é porque a ferramenta 
Solver não foi instalada. Para instalá-la proceda da seguinte maneira: No menu Arquivo, 
Seleciona Opções. Em seguida selecione Suplementos, Suplementos do Excel (ir) e marque a 
opção Solver. 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
105 
 
 
 
Os suplementos que você selecionar na caixa de diálogo permanecerão ativos até que você 
os remova. 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
106 
5.2. Definindo e Resolvendo um Problema de Programação Linear no Excel 
 
 Inicialmente, devemos definir o problema na planilha do Excel. A mágica da 
modelagem de um problema de programação linear em uma planilha eletrônica está na 
maneira como arrumamos as células. 
 Primeiramente devemos designar uma célula para representar cada uma das seguintesentidades: 
- Função-Objetivo (Expressão a ser Maximizada ou Minimizada) 
- Variáveis de Decisão (Variáveis que o modelador pode alterar seu valor) 
- Para cada restrição: 
- Uma para o lado esquerdo da restrição – LHS (Left Land Side) 
- Uma para o lado direito da restrição – RHS (Right Land Side) 
 Para que possamos definir cada uma das células necessitamos inserir uma série de 
parâmetros do problema, tais como todos os coeficientes das restrições e da função-objetivo. 
 Para lembrar o que cada célula representa é aconselhável a colocação de títulos que 
especifiquem o conteúdo de cada célula (célula com texto). 
 Precisamos agora avisar ao Excel quais são as células que representam a nossa função-
objetivo, as variáveis de decisão, as restrições do modelo e, finalmente, mandar o Excel 
resolver para nós. Isto é feito utilizando-se a Ferramenta (Solver) do Excel. 
 Para tal, clique com o botão esquerdo do mouse sobre o nome Ferramentas na barra de 
menu e clique em Solver. 
 Após este procedimento aparecerá na tela uma janela, onde deverão ser informadas ao 
software as células que representarão a função-objetivo, as variáveis de decisão e as 
restrições. 
 Na parte superior da janela aparece um campo para a entrada de dados chamado 
Célula-Alvo (Target Cell) que deve representar o valor da função-objetivo. Existem duas 
maneiras para designar esta célula: 
- A primeira é clicar sobre o ícone que está do lado direito do campo; 
- A segunda é digitar o nome da célula no campo. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
107 
Na linha seguinte são apresentadas as opções de maximizar, minimizar e atingir valor. 
Dependendo do problema devemos clicar o mouse sobre uma das três. 
Na próxima linha há um campo denominado Células Variáveis (Changing Cells). 
Neste campo serão inseridas as células que representarão as variáveis de decisão. 
Os valores podem ser inseridos da mesma maneira como no caso da função-objetivo, 
isto é, clicando sobre o ícone à direita do campo e marcando as células escolhidas ou 
simplesmente digitando seus nomes utilizando as regras do Excel para tal. 
O próximo passo é designar as restrições do problema. Devemos inserir uma restrição 
de cada vez. 
Para inserir a primeira restrição devemos clicar no botão Add (Adicionar) para 
aparecer uma janela de entrada de restrições. 
A janela de restrições tem três campos, que representam o LHS – Cell Reference (à 
esquerda), o sinal da restrição (ao centro) e o RHS – Constraint (à direita). 
Não é necessária a introdução de variáveis de folga/excesso, já que o Excel fará isto de 
uma forma automática. 
 Uma vez inserido o modelo e suas características, devemos efetivamente resolve-lo. 
Para tanto, deve-se selecionar a opção LPSimplex e clicar no botão Solver (Resolver) da 
ferramenta Solver do Excel. 
 
Exemplo 
Maximizar Z = 2X1 + 3X2 
Sujeito a: 
 X1 + 5X2  15 
 X1 + 3X2  7 
 2X1 + 2X2  9 
 X1 0; X2 0 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
108 
 
5.3. Análise de Sensibilidade 
 
 Uma das hipóteses dos problemas de programação linear é a consideração de certeza 
nos coeficientes e constantes. Isto é, a solução otimizada é dependente dos coeficientes da 
função-objetivo (geralmente lucro, receita ou custo unitário) e dos coeficientes e constantes 
das restrições (geralmente necessidades por produto e disponibilidade de um recurso). 
 No mundo real, quase nunca temos certeza destes valores; portanto, devemos saber o 
quanto a solução otimizada está dependente de uma determinada constante ou coeficiente. Se 
observarmos uma alta dependência, devemos tomar um grande cuidado na determinação da 
mesma. 
 Para amenizar essa hipótese realizamos uma análise pós-otimização verificando as 
possíveis variações, para cima e para baixo, dos valores dos coeficientes da função-objetivo, 
dos coeficientes e das constantes das restrições, sem que a solução ótima (X1, X2... Xn) seja 
alterada. Este estudo é denominado Análise de Sensibilidade. 
 Em uma análise de sensibilidade deveremos responder basicamente a três perguntas: 
 Qual o efeito de uma mudança num coeficiente da função-objetivo? 
 Qual o efeito de uma mudança numa constante de uma restrição? 
 Qual o efeito de uma mudança num coeficiente de uma restrição? 
Existem dois tipos básicos de análise de sensibilidade. O primeiro estabelece limites 
inferiores e superiores para todos os coeficientes da função-objetivo e para as constantes das 
restrições. Este estudo é efetuado automaticamente pelo Excel, considerando a hipótese de 
apenas uma alteração a cada momento. O segundo verifica se mais de uma mudança 
simultânea em um problema altera a sua solução ótima. Neste caso, este estudo não é 
realizado automaticamente pelo Excel por se um estudo mais complexo. A maneira mais 
simples para se realizar este estudo, em problemas de pequeno e médio porte, é o de se 
realizar alterações na modelagem do problema e encontrar sua nova solução realizando uma 
nova otimização. 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
109 
Maximizar Z = 5X1 + 2X2 
Sujeito a: 
4X1 + X2  10 
X1 + 2X2  9 
X1 0; X2  0 
 
 Onde X1 e X2 representam as quantidades dos produtos P1 e P2. Os recursos R1 e R2 
têm disponibilidade de 10 e 9 unidades respectivamente. Os lucros unitários são 5 e 2 
respectivamente para P1 e P2. Os coeficientes de X1 e X2 nas restrições representam os usos 
dos recursos R1 e R2 por unidade dos produtos P1 e P2. Vamos verificar as conseqüências das 
variações desses dados. 
 Considerando o problema acima, sua modelagem no Excel e os parâmetros e opções 
do Solver utilizado para resolvê-lo. Após o comando de otimização ter sido dado, ou seja, 
clicamos no botão OK de maneira que a solução otimizada seja inserida automaticamente na 
planilha. Os resultados serão inseridos automaticamente na planilha utilizada na modelagem. 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
110 
 
Para obtermos os relatórios, devemos marcá-los, clicando com o mouse nos três 
relatórios disponíveis. Vale notar o aparecimento de diversas planilhas, uma para cada 
relatório pedido. 
 Existem três relatórios gerados pelo Excel. São eles: Relatório de Respostas;Relatório 
de Sensibilidade; e Relatório de Limites. 
 
 
 
 
5.3.1. Relatório de Respostas 
 
Devemos salientar que algumas legendas são automaticamente inseridas pelo Excel. 
Estas legendas podem ser alteradas facilmente pelo modelador, bastando editar a célula 
desejada. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
111 
A figura a seguir mostra o Relatório de Respostas do problema que acabamos de 
modelar. 
 
 
 
 Este primeiro relatório é o de mais simples compreensão. O relatório tem três partes 
distintas. A primeira parte, denominada Célula-Alvo (Célula de Destino), indica o tipo de 
problema de otimização tratado (maximização ou minimização) e o valor original (valor 
inicial) e final da função-objetivo, bem como a célula que foi utilizada para representá-la. 
 A segunda parte do relatório é relativo às variáveis de decisão, denominada CélulasAjustáveis Esta parte é análoga a primeira parte. Ela apresenta os valores iniciais e finais das 
variáveis de decisão e as células utilizadas para defini-las. 
 A terceira parte diz respeito às restrições. A coluna das células indica as células 
utilizadas pelo LHS (Left Hand Side) de cada uma das restrições. A coluna de valores das 
células indica os valores das constantes (RHS) de cada uma das restrições. A coluna Fórmulas 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
112 
indica cada uma das fórmulas utilizadas nas restrições. As colunas de Status e de Transigência 
são as que não são de compreensão direta. 
 A coluna Status pode apresentam dois valores: Agrupar e Sem Agrupar. Quando o 
valor desta coluna relativo a uma restrição apresentar o valor Agrupar significa que o LHS 
tem o mesmo valor do RHS quando são substituídos os valores da solução ótima no lado 
esquerdo da restrição.Quando esta igualdade não acontecer, o valor apresentado será de Sem 
Agrupar. 
 O mais importante está na interpretação desta igualdade. Quando a igualdade existe, o 
lado direito e esquerdo da restrição são iguais na solução ótima, significando que todo o 
recurso disponível (RHS) foi consumido, isto é, a variável de folga ou excesso (Transigência) 
tem valor zero. 
 A coluna Transigência indica a diferença entre o LHS e o RHS de cada uma das 
restrições. Por definição, restrições que tenha o status Agrupar dever apresentar valor na 
coluna Transigência igual a zero. As restrições com valor Sem Agrupar apresentam algum 
valor positivo, que é a diferença entre a disponibilidade do recurso e o que será efetivamente 
utilizado caso a solução ótima seja implantada. 
 
5.3.2. Relatório de Limites 
 
O relatório de limites do problema em estudo é apresentado a seguir. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
113 
 
Este relatório apresenta duas partes. A primeira na parte superior, relativa à função-
objetivo, e a outra na parte inferior, relativa às variáveis de decisão. A parte superior é de 
interpretação direta e apresenta a célula utilizada para representar a função-objetivo e o seu 
valor na solução ótima. 
 A parte inferior do relatório necessita de esclarecimentos. O lado esquerdo apresenta 
as células utilizadas para representar as variáveis de decisão e seus valores na solução ótima. 
O lado direito (4 últimas colunas) diz respeito à variação possível dos valores das variáveis de 
decisão. Os limites inferiores significam os menores valores que estas variáveis de decisão 
podem assumir (mantidas todas as outras como constantes) sem que nenhuma restrição deixe 
de ser satisfeita. A coluna seguinte indica o valor da função-objetivo, caso cada variável de 
decisão em questão assuma o limite inferior e todas as outras permaneçam constantes. As 
duas colunas seguintes são de interpretação análoga. A única diferença é que ao invés de 
encontrarmos os menores valores, encontraremos os maiores valores. 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
114 
5.3.3. Relatório de Sensibilidade 
 
 A figura a seguir apresenta o relatório de análise de sensibilidade do problema em 
estudo. 
 
 Este relatório é divido em duas partes. A primeira refere-se às mudanças que possam 
ocorrer nos coeficientes das variáveis de decisão da função-objetivo. A outra parte mostra as 
possíveis alterações que as constantes das restrições podem sofrer. 
 Na primeira coluna são apresentadas as células que representam as variáveis de 
decisão e os LHS das restrições, enquanto na terceira coluna são apresentados os valores após 
a otimização. A quarta coluna contém os valores das variáveis de decisão e de folga/excesso 
do problema dual (Custo Reduzido e Preço-Sombra). 
 
 
 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
115 
Preço-Sombra 
- A quantidade pela qual a função-objetivo altera dado um incremento de uma unidade 
na constante da restrição, assumindo que todos os outros coeficientes permaneçam 
constantes. 
- A interpretação econômica seria até quanto estaríamos dispostos a pagar por uma 
unidade adicional de um recurso. 
 O Excel reporta o valor do preço-sombra como um valor positivo ou zero ou negativo. 
 Se o preço-sombra for positivo, um incremento de uma unidade na constante da 
restrição resulta num aumento do valor de função-objetivo. Se o preço-sombra for negativo, 
um incremento de uma unidade na constante da restrição resulta na diminuição do valor da 
função-objetivo. Como comentado anteriormente, o valor do preço-sombra permanecerá 
constante desde que o valor da constante fique no intervalo descrito pelas duas últimas 
colunas (Permissível Acréscimo e Permissível Decréscimo). 
 Enquanto o valor da constante (RHS) permanecer no intervalo de variação, o conjunto 
de variáveis básicas não se altera, isto é, as variáveis com valores diferentes de zero (as 
variáveis básicas geralmente tem valor diferentes de zero) continuam com um valor diferentes 
de zero. 
 O preço-sombra de uma restrição do tipo Sem Agrupar tem que ser zero, uma vez que 
existem recursos disponíveis não sendo utilizados; portanto, sem valor marginal. 
 Devemos observar que uma restrição do tipo menor ou igual é abrandada pelo 
incremento de uma unidade, enquanto restrições do tipo maior ou igual o é pelo decremento 
de uma unidade. Analogamente, uma restrição do tipo menor ou igual se torna mais restritiva 
pelo decremento de uma unidade, e a do tipo maior ou igual pelo incremento de uma unidade. 
 O valor absoluto do preço-sombra pode então ser visto como o valor que a função-
objetivo é melhorada no caso de um abrandamento na restrição, isto é, um incremento de uma 
unidade na restrição do tipo menor ou igual ou um decremento de uma unidade na restrição 
do tipo maior ou igual. 
 Analogamente, o valor absoluto do preço-sombra pode então ser visto como o valor da 
função-objetivo que é piorado no caso de uma restrição se tornar mais restritiva, isto é, um 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
116 
incremento de uma unidade na restrição do tipo maior ou igual, ou um decremento de uma 
unidade na restrição do tipo menor ou igual. 
 
Custo Reduzido 
 Existem duas interpretações básicas para o Custo Reduzido: 
- A quantidade que o coeficiente da função-objetivo de uma variável original deve 
melhorar antes desta variável se tornar básica. 
- A penalização que deverá ser paga para tornar uma variável básica. 
 Os Custos Reduzidos são as variáveis de folga ou excesso do problema dual. Portanto, 
se uma variável do problema original for maior que zero, o valor da variável do dual 
relacionada será zero, isto é, o valor do custo reduzido será zero. 
 Como os valores do Custo Reduzido estão ligados aos coeficientes da função-objetivo 
(lembrando que os coeficientes da função-objetivo do problema Primal se tornam as 
constantes das restrições do problema Dual), as colunas Permissível Acréscimo e Permissível 
Decréscimo dos coeficientes formam um intervalo no qual os coeficientes podem sofrer 
alterações (desde que apenas um dos coeficientes se altere) sem que a solução ótima seja 
alterada.__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
117 
5.4. Exercícios 
 
1) Uma pequena empresa produz pôsteres de bandas de Rock. Ela fabrica quatro tipos de 
pôsteres, que diferem em tamanho e nas cores utilizadas. A empresa conseguiu uma 
impressora para produzir os pôsteres. Cada pôster deve ser impresso, cortado e dobrado. O 
tempo (em minutos) para fazer isso para os quatro tipos de pôsteres e o lucro unitário é de: 
 
Tipo de Pôster Impressão Corte Dobragem Lucro 
A 1 2 3 1 
B 2 4 2 1 
C 3 1 5 1 
D 3 3 3 1 
Disponível 15000 20000 20000 
 
Pede-se: 
a) Construir o modelo matemático para o problema de programação linear. 
b) Determinar as quantidades ótimas produzidas e o lucro projeto utilizando a ferramenta 
Solver do Excel. 
c) Com base no relatório de sensibilidade, determine quanto a empresa está disposta a 
pagar por tempo extra de impressão, de corte e de dobragem? 
 
 
2) As Indústrias Barbieri fabricam os Produtos 1 e 2. As empresas conseguem vender todos os 
produtos. Cada produto passa por três departamentos e os tempos de fabricação requeridos 
encontram-se na tabela a seguir: 
Tempo de fabricação em horas por unidade 
 Departamento A Departamento B Departamento C 
Produto 1 2 1 4 
Produto 2 2 2 2 
 
 Cada departamento, entretanto, tem uma capacidade fixa de homens-hora por mês, 
como mostra a tabela a seguir. 
 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
118 
Departamento Capacidade máxima em homens-hora 
A 160 
B 120 
C 280 
 
 A margem de contribuição do Produto 1 é de $1,00 por unidade e a do Produto 2 é de 
$1,50 por unidade. 
 O problema consiste em determinar quanto fabricar de cada produto com o objetivo de 
maximizar a margem de contribuição total (MCT). 
 Pede-se: 
1) Elaborar o modelo do problema. 
2) Resolver o problema utilizando a Ferramenta Solver do Excel. 
3) Analisar os relatórios de reposta, limites e sensibilidade e responder as seguintes 
questões: 
3.1) Qual a quantidade dos produtos deve ser produzida na solução ótima? Qual a 
MCT obtida nessa solução? 
3.2) Em que departamentos produtivos existe ociosidade e de quantas horas? 
3.3) Considerando a solução ótima, se o Produto 1 passar a ser produzido em seu 
limite mínimo, qual a margem de contribuição total? 
3.4) A partir da solução ótima, qual o reflexo na MCT de cada nova unidade do 
Produto 2 que a empresa produzir? Isto é válido para que intervalo? 
3.5) Considerar que a empresa deseja ampliar a capacidade produtiva do 
Departamento B. 
3.5.1) Determinar qual o impacto na margem de contribuição que seria 
provocado pelo aumento de cada nova unidade na capacidade total do 
departamento. 
3.5.2) Considerar que o custo com a ampliação da capacidade produtiva de 40 
unidades no departamento é de $500,00. Calcular quantos meses seriam 
necessários para, com o ganho adicional na margem de contribuição da 
empresa, cobrir os custos decorrentes da ampliação. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
119 
3) Dado o modelo de Programação Linear. 
 
Maximizar Z = 2100X1 + 1200X2 + 600X3 
Sujeito a: 
6X1 + 4X2 +6X3  3760 (Horas de Máquina) 
12X1 +16X2 +2X3 9520 (Horas de Mão-de-obra) 
X1  380 (Demanda de P1) 
X2  400 (Demanda de P2) 
X3  480 (Demanda de P3) 
X1 0; X2  0; X3  0 
 
a) Construir o modelo matemático para o problema de programação linear. 
b) Determinar as quantidades ótimas produzidas e o lucro projeto utilizando a ferramenta 
Solver do Excel. 
c) Qual a utilização dos recursos horas de máquina e horas de mão-de-obra? 
d) A demanda dos produtos P1, P2 e P3 é completamente atendida? Justifique sua 
resposta. 
e) Quais são as utilidades marginais (preço sombra) dos recursos produtivos (máquinas e 
mão-de-obra) e das demandas (P1, P2 e P3)? 
f) Caso pudéssemos produzir mais uma unidade de produto (P1, P2 e P3), qual seria a 
melhor opção? Porque? 
g) Caso pudéssemos acrescentar mais uma hora em algumas das seções (máquina/mão-
de-obra), qual seria a melhor alternativa? Por quê? 
h) Quais são os recursos escassos do processo produtivo? 
i) Verifica-se que a demanda de alguns produtos não é completamente atendida. 
Identifique esses produtos. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
REFERÊNCIAS BIBLIOGRÁFICAS 
 
ACKOFF, R. L.; SASIENI, M. W. Pesquisa Operacional. Rio de janeiro: LTC – Livros 
Técnicos e Científicos, 1971. 
ANDRADE, E. L. Introdução à Pesquisa Operacional: métodos e modelos para a análise 
de decisão. 2
a
. edição. Rio de Janeiro: LTC – Livros Técnicos e Científicos, 1998. 
ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H. Pesquisa 
Operacional. Rio de Janeiro: Elsevier, 2007. 
BATALHA, M. O. Gestão Agroindustrial. Volume 2. 1
a
. edição. São Paulo: Atlas, 1997. 
BRONSON, R. Pesquisa Operacional. 5
a
. edição. São Paulo: McGraw-Hill do Brasil, 1985. 
CAIXETA-FILHO, J. V. Pesquisa Operacional: técnicas de otimização aplicadas a sistemas 
agroindustriais. São Paulo: Atlas, 2001. 
COLIN, E. C. Pesquisa Operacional. Rio de Janeiro: LTC, 2007. 
CORRAR, L. J.; THEÓPHILO, C. R. Pesquisa Operacional para Decisão em Contabilidade 
e Administração. São Paulo: Atlas, 2004. 
ELLENRIEDER, A. V. Pesquisa Operacional. Rio de Janeiro: Almeida Neves Editores Ltda, 
1971. 
ERHLICH, P. J. Pesquisa Operacional: curso introdutório. 5
a
. edição. São Paulo: Atlas, 
1985. 
HILLER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 8ª. edição. São 
Paulo: mcGraw-Hill, 2006. 
LACHTERMACHER, G. Pesquisa Operacional na Tomada de Decisões: modelagem em 
excel. Rio de Janeiro: Campus, 2002. 
LOESCH, C. Pesquisa Operacional: fundamentos e modelos. São Paulo: Saraiva, 2009. 
GOLDBARG, M. C.; LUNA, H. P. L. Otimização Combinatória e Programação Linear: 
modelos e algoritmos. Rio de Janeiro: Campus, 2000. 
MOREIRA, D. A. Pesquisa Operacional: Curso Introdutório. São Paulo: Thomson 
Learning, 2007. 
PASSOS, E. J. P. F. Programação Linear como Instrumento de Pesquisa Operacional. São 
Paulo: Atlas, 2008. 
PRADO, D. S. Programação Linear. Belo Horizonte: Editora de Desenvolvimento Gerencial, 
1999. Série Pesquisa Operacional Volume 1. 
 
__________________________________________________________________________ 
Apostila – Introdução à Pesquisa Operacional 
Profa. Márcia de Fátima Morais 
 
121 
PUCCINI, A. L. Introdução à Programação Linear. Rio de janeiro: LTC – Livros Técnicos 
e Científicos, 1981. 
SILVA, Ermes Medeiros da. [et al]. Pesquisa Operacional. 3
a
. edição. São Paulo: Atlas, 
1998. 
VIEIRA, G. Pesquisa Operacional. Lavras: Escola Superior de Agricultura de Lavras, 1990.