Apostila - Pesquisa Operacional

Prévia do material em texto

PESQUISA OPERACIONAL 
 
 
NOTAS DE AULA 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Professor: Leandro Magatão 
 
 
Curitiba 
2016 
Pesquisa Operacional – Prof. Leandro Magatão 2
PREFÁCIO 
 
 
O presente material contém notas de aula destinadas à disciplina de Pesquisa Operacional do DAMEC/UTFPR. O material encontra-
se permanentemente em fase de construção e aprimoramentos e, portanto, está sujeito a alterações. Assim, gostaria de contar com a 
colaboração de todos para apontarem correções e/ou melhorias a serem efetuadas. Desde já agradeço. 
 
 
Atenciosamente, 
 
Prof. Leandro Magatão 
magatao@utfpr.edu.br 
Pesquisa Operacional – Prof. Leandro Magatão 3
SUMÁRIO 
 
FICHA DE ACOMPANHAMENTO, PLANEJAMENTO E AVALIAÇÕES − UTFPR / DAMEC ............................ 5 
1. INTRODUÇÃO À PESQUISA OPERACIONAL ......................................................................................................... 7 
1.1 – O Desenvolvimento da Pesquisa Operacional (PO) .................................................................................. 7 
1.2 – O Uso de Modelos em PO ......................................................................................................................... 7 
1.3 – Algumas Vertentes e Aplicações da Pesquisa Operacional .................................................................... 10 
1.4 – Sociedades Profissionais de PO............................................................................................................... 11 
1.5 – A Programação Matemática em PO ........................................................................................................ 12 
1.5.1 – Programação Linear (PL) ................................................................................................................. 13 
1.5.2 – Hipóteses da Programação Linear .................................................................................................... 14 
1.5.3 – Programação Linear Inteira Mista, Inteira e Binária ........................................................................ 14 
1.5.4 – Equivalências em Programação Matemática .................................................................................... 15 
2. O MÉTODO GRÁFICO PARA RESOLUÇÃO DE MODELOS DE PROGRAMAÇÃO LINEAR ..................... 16 
2.1 – Programação Linear: Introdução ............................................................................................................. 16 
2.2 – O Método Gráfico.................................................................................................................................... 17 
2.2.1 – Método Gráfico: Exemplo com 3 Variáveis ..................................................................................... 19 
3. EXEMPLOS INICIAIS DE MODELOS DE PL ......................................................................................................... 20 
4. O MÉTODO SIMPLEX PARA RESOLUÇÃO DE MODELOS DE PROGRAMAÇÃO LINEAR ...................... 26 
4.1 – O Método SIMPLEX: Introdução ........................................................................................................... 26 
4.2 – O Método SIMPLEX: Etapas .................................................................................................................. 27 
4.3 – Particularidades na Aplicação do Método SIMPLEX ............................................................................. 35 
5. DUALIDADE EM PROGRAMAÇÃO LINEAR ........................................................................................................ 40 
5.1 – Dualidade: Introdução ............................................................................................................................. 40 
5.2 – Dualidade: Método Dual Simplex ........................................................................................................... 41 
5.3 – Dualidade: Teorema da Folga Complementar ......................................................................................... 42 
5.4 – Dualidade: Interpretação Econômica ...................................................................................................... 43 
6. NOÇÕES DE ANÁLISE DE SENSIBILIDADE OU PÓS-OTIMIZAÇÃO EM PL ................................................ 45 
6.1 – Introdução ................................................................................................................................................ 45 
6.2 – Análise de Alterações na Lucratividade dos Componentes .................................................................... 46 
6.3 – Uma Interpretação de Custo Reduzido em Solvers ................................................................................. 47 
7. MODELOS DE PL ......................................................................................................................................................... 49 
7.1 – Modelagem Matemática: O Problema de Transporte .............................................................................. 49 
7.2 – Problema de Transporte com Estações Intermediárias ............................................................................ 50 
7.3 – Problemas de Programação Estruturada .................................................................................................. 54 
7.3.1 O Modelo Multi-Fábrica...................................................................................................................... 54 
7.3.2 O Modelo Multi-Período ..................................................................................................................... 55 
7.3.3 O Modelo Multi-Produto ..................................................................................................................... 56 
8. MODELOS QUE UTILIZAM GRANDEZAS DISCRETAS ..................................................................................... 57 
8.1 – O Método Branch-and-Bound ................................................................................................................. 58 
8.1.1 O Número de Variáveis Inteiras .......................................................................................................... 59 
8.1.2 O Número de Restrições ...................................................................................................................... 60 
8.1.3 Resolvendo-se um Modelo de Programação Inteira com o Branch-and-Bound ................................. 61 
8.2 – Modelos com Variáveis Binárias (0/1) .................................................................................................... 63 
8.3 – Condições Lógicas com Variáveis Binárias ............................................................................................ 65 
8.4 – Formulação Big-M ................................................................................................................................... 67 
8.5 – Formulação Big-M: Restrições If-Then e If-Then-Else ........................................................................... 67 
8.6 – A Envoltória Convexa (Convex Hull) em Modelos com Variáveis Discretas. ....................................... 69 
8.7 – Abordagem PLIM para Linearização de Curvas. .................................................................................... 71 
8.8 – Notação de Conjuntos para a Elaboração de Modelos de PO. ................................................................ 72 
9. EXEMPLOS DE MODELOS COM GRANDEZAS DISCRETAS ........................................................................... 74 
Pesquisa Operacional – Prof. Leandro Magatão 4
9.1 – Problema de Designação de Pessoas ....................................................................................................... 74 
9.2 – Problema de Designação de Tarefas ........................................................................................................75 
9.3 – Problema de Determinação de Investimentos ......................................................................................... 75 
9.4 – Problemas de Corte.................................................................................................................................. 76 
9.4.1 Problema de Corte de Barras ............................................................................................................... 76 
9.4.2 Problema de Corte de Chapas.............................................................................................................. 77 
9.5 – Problemas de Designação de Funcionários em Máquinas ...................................................................... 79 
9.6 – Problemas de Sequenciamento de Tarefas em um Recurso Gargalo ...................................................... 81 
9.7 – Sequenciamento de Tarefas com Considerações de Set-Up. ................................................................... 84 
9.8 – Problemas de Sequenciamento: Flow-Shop Scheduling.......................................................................... 86 
9.8.1 – Terminologia Usada em Análise de Linhas de Produção ................................................................. 87 
9.8.2 – Exemplo Didático de Flow Shop Scheduling ................................................................................... 88 
9.9 – Problemas de Sequenciamento: Job-Shop Scheduling ............................................................................ 90 
9.10 – Problemas de Balanceamento de Linha de Montagem .......................................................................... 93 
9.11 – Redes PERT/CPM via PLI .................................................................................................................... 95 
10. NOÇÕES DE PROGRAMAÇÃO DINÂMICA ......................................................................................................... 97 
10.1 – Introdução .............................................................................................................................................. 97 
10.2 – Conceitos de Base.................................................................................................................................. 99 
REFERÊNCIAS BIBLIOGRÁFICAS ............................................................................................................................ 103 
Pesquisa Operacional – Prof. Leandro Magatão 5
 
FICHA DE ACOMPANHAMENTO, PLANEJAMENTO E AVALIAÇÕES − UTFPR / DAMEC 
Disciplina: Pesquisa Operacional 
 
Competência a ser construída: Aplicar os princípios básicos da Pesquisa Operacional (PO), seus fundamentos lógicos e matemáticos e seu relacionamento com a Logística Industrial e a 
Otimização da Manufatura através das principais técnicas de otimização utilizadas em PO como suporte ao processo decisório.1 
 
Objetivos Finais 
(Resultados de 
Aprendizagem) 
Indicadores de Desempenho da 
Disciplina 
Estratégias e Ações da 
Disciplina Plano de Ensino
2
 
Métodos e 
Métricas de 
Avaliação 
Avaliação da 
Disciplina 
Processo de 
Realimentação da 
Disciplina 
Competências -
Diretrizes 
Curriculares3, 4 
Aplicar o 
Método Simplex 
na Resolução de 
Problemas de 
Pesquisa 
Operacional 
1) Os estudantes deverão conhecer 
a abordagem básica da PO 
(modelagem matemática) e ter 
noções das principais técnicas por 
ela utilizadas para a solução de 
problemas. 
2) Os estudantes deverão 
compreender o conceito de modelo 
matemático aplicado à PO. 
3) Os estudantes deverão conhecer 
o conceito de Programação Linear e 
Método Simplex e ser aprovado em 
prova sobre o assunto. 
 
1) Aulas expositivas. 
2) Listas de exercícios. 
1) Fundamentos da PO. 
1.1) Origem/evolução da PO. 
1.2) Conceito de modelagem. 
1.3) Principais abordagens/técnicas da PO. 
2) Fundamentos de programação linear (PL). 
2.1) Formato padrão (minimização x maximização). 
2.2) Formulação e interpretação gráfica. 
3) O método Simplex. 
3.1) Algoritmo(s) do método Simplex. 
3.2) Solução de exemplos clássicos. 
4) Dualidade em PL. 
5) Noções de Análise de Sensibilidade. 
 
1) Avaliação 
Parcial de 
Desempenho de 
Aluno 
(70%) 
 
2) Lista de 
Exercícios e/ou 
Atividades 
Realizadas em 
Sala 
(30%) 
1) Montagem de 
planilha com os 
resultados de 
avaliação e 
anotações da 
disciplina. 
 
2) Análise dos 
resultados de 
avaliação dos 
alunos 
 
3) Análise do 
histórico das 
avaliações. 
 
4) Revisão das 
métricas de 
avaliação e 
ponderações 
utilizadas. 
1) Avaliação da 
disciplina pelos 
alunos ao término do 
semestre letivo. 
 
2) Avaliação junto 
aos professores de 
disciplinas que 
utilizem os conceitos 
dados sobre a 
adequabilidade do 
conteúdo ministrado. 
 
3) Avaliação junto a 
alunos de períodos 
finais sobre a 
adequação e/ou 
aplicabilidade da 
disciplina durante o 
curso e, 
principalmente, no 
contexto de mercado 
de trabalho que 
vivenciam. 
A – Domínio do 
conhecimento, 
técnicas e 
ferramentas 
modernas que 
envolvem a 
disciplina. 
Relacionar a 
Pesquisa 
Operacional 
com a Logística 
Industrial 
1) Os estudantes devem ser capazes 
de identificar modelos de PO 
aplicáveis à Logística Industrial, 
implementar tais modelos em 
contextos clássicos e analisar os 
resultados obtidos. Os estudantes 
deverão ser aprovados em prova 
sobre o assunto. 
1) Aulas expositivas sobre modelos 
para problemas clássicos de 
Logística. 
2) Uso de um solver comercial (e.g. 
Xpress) para implementar, solucionar 
e interpretar os resultados de 
modelos de PO aplicados ao contexto 
logístico. 
3) Listas de Exercícios. 
4) Especificação de estudos de casos 
que envolvam modelagem, 
implementação e resolução de 
problemas de PO no contexto 
logístico (desenvolvimento 
individual ou em dupla, conforme 
disponibilidade de laboratório). 
1) Simulação de sistemas logísticos em ferramenta 
computacional. 
1.1) Emprego de ferramenta (e.g. Xpress) para 
implementação de modelos. 
1.2) Exemplos introdutórios. 
2) Problemas logísticos de transporte, armazenagem e 
distribuição. 
2.1) Problemas de transporte: balanceado, com 
excesso de oferta/demanda. 
2.2) Problemas de transporte com estações 
intermediárias (transbordo). 
3) Problemas de programação estruturada. 
3.1) Modelos multi-fábrica, multi-período, multi-
produto (noções de supply-chain). 
4) Problemas que utilizam grandezas discretas. 
4.1) Noções de branch-and-bound. 
4.2) Uso de variáveis discretas. 
4.3) Problemas de designação (pessoas, tarefas, 
investimentos). 
4.4) Problemas de corte. 
5) Problemas de localização industrial. 
 
1) Avaliação 
Parcial de 
Desempenho de 
Aluno 
(70%) 
 
2) Lista de 
Exercícios e/ou 
Atividades 
Realizadas em 
Sala 
(30%) 
A 
 
B – Aplicar o 
conhecimento atual e 
adaptá-lo para uso na 
matemática, ciência e 
tecnologia. 
 
C – Conduzir, 
analisar, interpretar 
experimentos e 
aplicar resultados 
experimentais para 
melhorar processos. 
 
F – Identificar, 
analisar e resolver 
problemas técnicos. 
 
1
 Foi considerado que, a partir da concretização dos objetivos finais do curso a competência desejada seria alcançada. 
2
 Disciplina de caráter teórico-prático, a ser ministrada em laboratório. 
3
 As competências foram referenciadas a partir dos critérios específicos da ABET para Engineering Technology Programs. 
4
 As competências foram selecionadas de acordo com o objetivo geral do curso e o perfil profissional dos egressos, conforme plano de ensino da disciplina. 
 
Pesquisa Operacional – Prof. Leandro Magatão 6
Solucionar 
Problemas de 
Otimização da 
Manufatura 
Usando 
ProgramaçãoLinear 
1) Os estudantes devem ser capazes 
de identificar modelos de PO 
aplicáveis à Otimização da 
Manufatura, implementar tais 
modelos em contextos clássicos e 
analisar os resultados obtidos. Os 
estudantes deverão ser aprovados em 
prova sobre o assunto. 
2) Os estudantes deverão elaborar 
um modelo de PO para um estudo de 
caso, implementar tal modelo em 
um solver comercial, resolvê-lo e 
interpretar os resultados obtidos 
diante das hipóteses simplificadoras 
de modelagem. 
1) Aulas Expositivas sobre modelos 
para problemas clássicos de 
Otimização da Manufatura. 
2) Uso de um solver comercial (e.g. 
Xpress) para implementar, solucionar 
e interpretar os resultados de 
modelos de PO aplicados ao contexto 
de Otimização da Manufatura. 
3) Listas de Exercícios. 
4) Especificação de um estudo de 
caso que envolva modelagem, 
implementação, resolução e análise 
de um problema real (a ser 
desenvolvido/apresentado em 
equipes). 
1) Simulação de sistemas de Otimização da 
Manufatura em ferramenta computacional. 
1.1) Exemplos introdutórios. 
2) Problemas de designação de funcionários em 
máquinas. 
2.1) Máquinas trabalhando em paralelo. 
2.2) Máquinas trabalhando em série. 
3) Problemas sequenciamento de tarefas. 
3.1) Sequenciamento em um recurso “gargalo”. 
3.2) Sequenciamento com considerações de set-up. 
4) Estudo e implementação de exemplos clássicos, 
observando-se critérios de sensibilidade. 
4.1) Problemas de planejamento. 
4.2) Problemas de scheduling. 
4.3) Problemas de balanceamento de linha. 
4.4) Redes PERT/CPM. 
 
1) Avaliação 
Parcial de 
Desempenho de 
Aluno 
(50%-70%) 
 
2) Lista de 
Exercícios e/ou 
Atividades 
Realizadas em 
Sala 
(0%-30%) 
 
3) Apresentação 
do e análise de 
resultados 
obtidos para um 
estudo de caso 
(0%-30%) 
A, B, C, F 
 
D – Aplicar 
criatividade no 
projeto de sistemas, 
componentes ou 
processos. 
 
E – Atuar 
efetivamente em 
equipes. 
 
G – Comunicar-se 
efetivamente. 
 
Bibliografia Básica 
Título/Periódico Autor Edição Local Editora Ano 
Introdução à Pesquisa Operacional Eduardo Leopoldino de Andrade 2ª Rio de Janeiro - RJ LTC 1998 
Programação Linear Darci Prado 4ª Nova Lima –MG INDG 2004 
Otimização Combinatória e Programação Linear Marco Goldbarg & Henrique Luna 2ª Rio de Janeiro - RJ CAMPUS 2005 
Pesquisa Operacional Harvey M. Wagner 2ª Rio de Janeiro - RJ Prentice Hall 1986 
Applications of Optimization with XpressMP Susanne Heipcke 1ª Blisworth -United Kingdom Dash Optimization 2000 
Model Building in Mathematical Programming Paul H. Williams 4ª São Paulo - SP John Wiley & Sons 1999 
Notas de Aula da Disciplina de PO Leandro Magatão versão 
2016/1 
Disponível no Moodle, UTFPR, Área de 
Automação, Prof. Leandro Magatão. 
 2016 
 
1ª Avaliação 2ª Avaliação Avaliação de Recuperação* 
 
(__/__/__) 
Média Final 
Prova 
(__/__/__) Trabalho(s) Média 1 
Prova 
(__/__/__) Trabalho(s) Média 2 
 
 
 
 
 
Média Final = (Média 1 + Média 2)/2. 
*Envolverá todo o conteúdo ministrado. 
 
Pesquisa Operacional – Prof. Leandro Magatão 7
1. INTRODUÇÃO À PESQUISA OPERACIONAL 
 
1.1 – O Desenvolvimento da Pesquisa Operacional (PO) 
 
Durante a Segunda Guerra Mundial, um grupo de cientistas foi convocado na Inglaterra para estudar problemas de estratégia e de 
tática associados com a defesa do país. O objetivo era decidir sobre a utilização mais eficaz de recursos militares limitados. A 
convocação deste grupo marcou a primeira atividade formal de “Pesquisa Operacional” (Lisboa, 2002). 
 
Os resultados positivos conseguidos pela equipe de Pesquisa Operacional inglesa motivaram os Estados Unidos a iniciarem atividades 
semelhantes. Apesar de ser creditada à Inglaterra a origem da Pesquisa Operacional, sua propagação deve-se principalmente à equipe 
de cientistas convocada durante a Segunda Guerra Mundial e liderada pelo americano George B. Dantzig (1914-2005). A um dos 
resultados deste esforço de pesquisa, concluído em 1947, deu-se o nome de Método Simplex (Dantzig, 1963 apud Lisboa, 2002). 
 
Contudo, há alguma controvérsia em relação ao trabalho seminal do método Simplex. Em 1939, um matemático da URSS chamado 
Leonid Vitaliyevich Kantorovich (1912-1986) publicou uma monografia relacionada à Programação Linear (PL) e que ficou 
desconhecida por décadas no Ocidente, especialmente pela “guerra ideológica” entre comunistas e capitalistas. O hoje conhecido 
Método Simplex já era formalizado neste trabalho. Em 1975, Kantorovich (juntamente com Tjalling C. Koopmas) ganhou um Nobel 
de economia pelo desenvolvimento da “Teoria da Alocação Ótima de Recursos”, a qual englobava técnicas de PL. Curiosamente, 
Dantzig nunca ganhou um Nobel. Aparentemente, por seus trabalhos não serem aderentes às exigências da Real Academia Sueca de 
Ciências, que preza que as descobertas sejam originalmente propostas para o bem da humanidade (Colin, 2007). 
 
Com o fim da guerra, a utilização de técnicas de Pesquisa Operacional (PO) atraiu o interesse de diversas outras áreas. A natureza dos 
problemas encontrados é bastante abrangente e complexa exigindo, portanto, uma abordagem que permita reconhecer os múltiplos 
aspectos envolvidos. Uma característica importante da Pesquisa Operacional e que facilita o processo de análise e de decisão é a 
utilização de modelos. Eles permitem a experimentação da solução proposta. Isto significa que uma decisão pode ser melhor avaliada 
e testada antes de ser efetivamente implementada. A economia obtida e a experiência adquirida pela experimentação justificam a 
utilização das técnicas de Pesquisa Operacional (Lisboa, 2002). 
 
Com o aumento da velocidade de processamento e quantidade de memória dos computadores, houve um grande progresso na 
Pesquisa Operacional. Este progresso é devido também à larga utilização de microcomputadores, que se tornaram unidades isoladas 
dentro de empresas. Isso faz com que os modelos desenvolvidos pelos profissionais de Pesquisa Operacional sejam mais rápidos e 
versáteis, além de serem também interativos, possibilitando a participação do usuário ao longo do processo de cálculo (Lisboa, 2002). 
 
1.2 – O Uso de Modelos em PO 
 
A diminuição de custos de produção e a melhoria em produtos e serviços são objetivos comuns a diversos setores industriais. 
Contudo, o processo de tomada de decisões operacionais ainda é conduzido pelo emprego de critérios experimentais. A 
complexidade do planejamento (planning) e programação (scheduling) da produção é contornada pela adoção de políticas 
operacionais conservativas, que não utilizam a capacidade máxima de operação do sistema produtivo (Magatão, 2001). 
 
Motivado pela necessidade industrial, o desenvolvimento de modelos, em especial os que empregam técnicas de otimização, tem 
possibilitado que procedimentos operacionais complexos sejam avaliados de forma criteriosa, fazendo com que recursos críticos 
possam ser utilizados da melhor maneira possível. Neste contexto, um campo da análise de decisão denominado Pesquisa Operacional 
tem alcançado evolução notória. O uso de técnicas da Pesquisa Operacional na modelagem das estratégias de planejamento e 
programação da produção tem se mostrado como um fator decisivo para o desenvolvimento de políticas otimizadas de operação 
industrial. Em particular, o mercado nacional vem despertando para o grande potencial econômico apresentado por este tipo de 
modelagem. A razão para o interesse é simples: os modelos obtidos evidenciam procedimentos que levam a diminuição dos custos 
produtivos (Magatão, 2001). 
 
Um modelo é uma representação de um sistema real, que pode já existir ou ser um projeto aguardando execução. No primeiro caso, o 
modelo pretende reproduzir o funcionamento do sistema, de modo a aumentar sua produtividade. No segundo caso, o modeloé 
utilizado para definir a estrutura ideal do sistema. A confiabilidade da solução obtida através do modelo depende de sua validação 
para a representação do sistema real. A validação do modelo é a confirmação de que ele realmente representa o sistema real. A 
diferença entre a solução real e a solução proposta pelo modelo depende diretamente da precisão do modelo em descrever o 
comportamento original do sistema. Um problema simples pode ser representado por modelos também simples e de fácil solução. Já 
problemas mais complexos requerem modelos mais elaborados, cuja solução pode vir a ser bastante complicada (Lisboa, 2002). 
 
Segundo Williams (1999) há três motivos principais para a elaboração de modelos em PO: 
(i) O procedimento de construção de um modelo geralmente revela relacionamentos que não são evidentes para um 
grande número de pessoas, propiciando um melhor entendimento do objeto que está sendo modelado; 
(ii) É usualmente possível analisar matematicamente um modelo, sugerindo novas tendências e procedimentos que, de 
outra forma, podem não ser aparentes; 
(iii) Um modelo permite a realização de experimentos. Este é geralmente um procedimento não possível ou não desejável 
no objeto que está sendo modelado. 
O papel dos modelos é configurar uma importante ferramenta de auxílio ao processo de tomada de decisões, ampliando a 
capacidade de percepção dos especialistas envolvidos, objetivando o melhor aproveitamento possível das estruturas componentes do 
Pesquisa Operacional – Prof. Leandro Magatão 8
processo industrial. Vários são os fatores que influenciam a formulação de um modelo. Suntherland (1975) definiu as três dimensões 
básicas a serem observadas para a formulação de um modelo: o meio ambiente no qual o modelo está inserido, o domínio do 
problema em relação ao número de variáveis envolvidas e a dinâmica dos processos envolvidos. 
 
A Figura 1.1, originalmente apresentada por Goldbarg e Luna (2000), ilustra o relacionamento entre as três dimensões básicas para a 
formulação de um modelo. O plano interior define modelos determinísticos tratáveis e de pequeno porte. O plano exterior define 
modelos tratáveis que apresentam uma dinâmica estocástica com um número médio de variáveis. Um espaço viável para a concepção 
e aplicação de modelos de otimização pode ser definido entre os planos interior e exterior. A Figura 1.1 evidencia também que a 
complexidade das situações reais impossibilita a concepção de modelos em um grande espaço definido pelo trinômio meio ambiente, 
domínio de atuação e dinâmica do processo. A definição do escopo de aplicação e da capacidade de previsão esperada de um modelo 
é de fundamental importância. 
 
Intratável
Dinâmica do Processo
Domínio
Meio Ambiente
Determinística
Estocástica
Indeterminada
Tratável
Poucas Variáveis
Muitas Variáveis
N° Médio de Variáveis
 
Figura 1.1 – Espaço Viável para a Concepção e Aplicação de Modelos. 
O procedimento para a construção de modelos pode ser baseado em diferentes abordagens ou arquiteturas. A Figura 1.2, adaptada de 
Goldbarg e Luna (2000), ilustra um diagrama básico utilizado no processo de modelagem, evidenciando as diferentes etapas deste 
processo. 
 
 
 
Definição do Problema 
Formulação e Construção 
do Modelo Inicial 
 
Validação do Modelo 
 
Reformulação do Modelo 
 
Aplicação do Modelo 
 
Simulação do Modelo 
 
Figura 1.2 – O Processo de Modelagem: Diagrama Básico. 
 
Definição do Problema: Na definição do problema são estabelecidas as hipóteses de representação. Ficam caracterizados os 
objetivos a serem atingidos com a formulação proposta e o detalhamento que se deseja. Baseia-se em três aspectos principais: 
(i) Descrição exata dos objetivos do estudo; 
(ii) Identificação das alternativas de decisão existentes; 
(iii) Reconhecimento das limitações, restrições e exigências do sistema. 
 
Pesquisa Operacional – Prof. Leandro Magatão 9
A descrição dos objetivos é uma das atividades mais importantes em todo o estudo, pois a partir dela é que o modelo é concebido. Da 
mesma forma, é essencial que as alternativas de decisão e as limitações existentes sejam todas explicitadas, para que as soluções 
obtidas ao final do processo sejam válidas e aceitáveis. 
 
Formulação e Construção do Modelo Inicial: A fase denominada formulação e construção do modelo inicial constitui um ponto 
crítico, pois ela depende, em grande parte, do conhecimento a priori que o projetista possui sobre o problema a ser modelado. O rigor 
da tradução matemático-simbólica do modelo é obtido através de processos que envolvem o poder de síntese e a experiência. Nesta 
etapa são definidos os tipos de variáveis a serem empregadas e as restrições do problema a serem consideradas. A escolha apropriada 
do modelo é fundamental para a qualidade da solução fornecida. Se o modelo elaborado tem a forma de um modelo conhecido, a 
solução pode ser obtida através de métodos matemáticos convencionais. Por outro lado, se as relações matemáticas são muito 
complexas, talvez se faça necessária a utilização de combinações de metodologias. A Figura 1.3, originalmente apresentada por 
Prado (2004), ilustra os principais fatores que influenciam o processo criativo de geração de um modelo. 
 
 
 
Figura 1.3 – Alguns Fatores que Influenciam o Processo de Modelagem. 
 
Simulação/Solução, Reformulação e Validação do Modelo: As fases de simulação e posterior reformulação do modelo são 
destinadas à verificação das respostas obtidas através da abordagem empregada. Para certos casos, somente a aplicação do modelo 
poderá fornecer subsídios para uma avaliação eficiente de seu desempenho. Ao contrário das outras fases, que não possuem regras 
fixas, a solução do modelo é baseada geralmente em técnicas matemáticas existentes. No caso de um modelo matemático, a solução é 
obtida pelo algoritmo mais adequado, em termos de rapidez de processamento e precisão de resposta. Isto exige um conhecimento 
profundo das principais técnicas existentes. O processo de validação do modelo ou verificação da sua representatividade é uma etapa 
indispensável em qualquer procedimento científico ou industrial (Goldbarg e Luna, 2000). Um modelo é válido se, levando-se em 
conta sua inexatidão em representar o sistema, ele for capaz de fornecer uma previsão aceitável do comportamento do sistema. Um 
método comum para testar a validade de um sistema é analisar seu desempenho com dados passados e verificar se ele consegue 
reproduzir o comportamento que o sistema apresentou. É importante observar que este processo de validação não é facilmente 
aplicável em projetos. Nesse caso, a validação é feita pela verificação da correspondência entre os resultados obtidos e algum 
comportamento esperado do novo sistema. 
 
Aplicação do Modelo ou Implementação da Solução: Avaliadas as vantagens obtidas com a elaboração do modelo e “obtendo-se” a 
validação da solução, esta deve ser convertida em regras operacionais. A implementação, por ser uma atividade que, via de regra, 
altera uma situação existente, é uma das etapas críticas do estudo. É conveniente que seja controlada pela equipe responsável, pois, 
eventualmente, os valores da nova solução, quando levados à prática, podem demonstrar a necessidade de correções nas relações 
funcionais do modelo, exigindo a reformulação/aprimoramento de algumas de suas partes. 
 
Na grande maioria dos casos, o modelo em questão deverá ser “transparente” ao usuário final do sistema. Além disto, o uso de 
ferramentas computacionais no estabelecimento e solução de modelos é uma realidade. Ou seja, há necessidade do estabelecimento de 
uma interface ser humano – computador, conforme ilustrado na figura 1.4. 
 
 
Figura 1.4 – Interfaces de Entradas e Saídas de um Modelo de Otimização. 
PROCESSO 
CRIATIVO 
Experiência 
Prática Prévia 
ConhecimentosTeóricos 
Conhecimento 
de Cenário 
Semelhante 
Consulta à 
Literatura 
Nível de 
Inteligência 
Desejado 
Consulta a 
Profissionais 
Experientes 
MODELO 
Interface de 
ENTRADA 
Interface de 
SAÍDA 
MODELO 
Pesquisa Operacional – Prof. Leandro Magatão 10
O conceito de modelo é essencial nos estudos de Pesquisa Operacional. Em tal contexto, modelo é uma idealização, ou uma visão 
simplificada da realidade, conforme ilustrado na figura 1.5. Nesta figura, ressalta-se que o especialista do sistema pode, a partir de um 
Problema Real, empregar uma Abordagem Direta ou Intuitiva e obter uma solução (subótima) para o problema. Em PO, o caminho 
para obtenção de uma resposta ao Problema Real passa pela criação e solução de um Modelo. Contudo, como será visto a posteriori, 
uma correta Formulação e Interpretação dos resultados dos modelos podem evidenciar respostas melhores que a usualmente adotadas 
para a Solução do Problema. Ou seja, o caminho é um pouco mais oneroso, mas pode trazer recompensas. 
 
Problema 
Real
Solução do 
Problema
Abordagem 
Direta / 
Intuitiva
Abordagem 
Direta / 
Intuitiva
Modelo
Solução do 
Modelo
Resolução 
do Modelo
Resolução 
do Modelo
FormulaçãoFormulação
InterpretaçãoInterpretação
Hipóteses 
Simplifi-
cadoras
Sistema Real Modelo do Sistema Real
Resposta do Modelo 
é uma “Estimativa”
p/ a Solução do 
Sistema Real
Hipóteses 
Simplifi-
cadoras
Sistema Real Modelo do Sistema Real
Resposta do Modelo 
é uma “Estimativa”
p/ a Solução do 
Sistema Real
 
 
Figura 1.5 – Conceitos Essenciais de Modelos. 
 
 
1.3 – Algumas Vertentes e Aplicações da Pesquisa Operacional 
 
Conforme Passos (2008), a PO atua em diversos segmentos e para cada um apresenta um conjunto de técnicas diferentes para a sua 
solução e orientação na tomada de decisão. Há divergências entre autores com relação à classificação das diferentes subáreas da PO. 
Na sequência, de maneira informal, elencam-se algumas das vertentes mais conhecidas da PO para a Otimização de Sistemas. 
 
� Programação Matemática (MP – Mathematical Programming) 
o Programação Linear (LP – Linear Programming) 
o Programação Binária (BP – Binary Programming) 
o Programação Inteira (IP – Integer Programming) 
o Programação Linear Inteira Mista (MILP – Mixed Integer Linear Programming) 
o Programação Não Linear (NLP – Non Linear Programming) 
� Otimização de Redes (Network Models) 
o Via MILP 
o Via Teoria de Grafos 
� Programação Dinâmica (DP – Dynamic Programming) 
o Programação Dinâmica Determinística (DDP – Deteministic Dynamic Programming) 
o Programação Dinâmica Estocástica (SDP – Stochastic Dynamic Programming) 
� Teoria de Jogos (Game Theory) 
� Teoria de Filas 
� Simulação 
o Baseada em Eventos Discretos 
o Métodos Heurísticos 
� Análise por Envoltória de Dados (DEA – Data Envelopment Analysis) 
� Logística / Gerenciamento da Cadeia de Suprimentos (SCM – Supply Chain Management) 
 
Vale ressaltar que um novo paradigma para a resolução de problemas combinatoriais tem evoluído dos campos da Ciência da 
Computação e da Inteligência Artificial (IA). Este paradigma recebe o nome de Programação Lógica por Restrições (Constraint Logic 
Programming – CLP). Um crescente número de pesquisadores vem investigando a possibilidade de integrar métodos de CLP e MILP 
na solução de problemas combinatoriais. De fato, as técnicas de CLP e MILP possuem similaridades, são utilizadas para a resolução 
Pesquisa Operacional – Prof. Leandro Magatão 11
dos mesmos problemas e, sobretudo possuem características complementares. A sinergia entre estas duas técnicas origina uma 
terceira (CLP-MILP) que pode endereçar problemas combinatoriais até então intratáveis ou de difícil resolução (Hooker, 2000). 
A partir das subáreas da PO, diferentes problemas vêm sendo tratados, conforme a seguir exemplificado: 
 
• Sistemas de Transporte, Armazenagem e Distribuição 
– Problemas de Estocagem e Misturas 
– Roteamento de veículos (Vehicle Routing Problem) 
– Otimização de horários de ônibus/trens 
– Programação de tripulações (Crew Scheduling) 
– Determinação de caminhos mínimos 
– Programação da Logística de Sistemas Dutoviários 
• Manufatura 
– Dimensionamento de lotes (Lot-Sizing Problem) 
– Otimização de layouts (Facility Layout Problem) 
– Formação de células (Cell Formation Problem) 
– Programação da Produção (Production Planning) 
• Instituições de Ensino / Hospitais 
– Programação de Horários (Timetabling, Nurse scheduling) 
– Alocação de Salas (Room Assignment) 
• Construção 
– Otimização de estruturas (Truss structure design) 
• Finanças 
– Análise de riscos/investimentos 
• Agricultura 
– Planejamento de produção agrícola 
– Planejamento florestal 
• Comunicação e Transmissão 
– Localização de estações 
• Controle 
– Aplicações em Controle Ótimo 
 
 
1.4 – Sociedades Profissionais de PO 
 
De acordo com Moreira (2010), atualmente existem diversas sociedades profissionais que têm como objetivo o crescimento e a 
difusão da PO. Por exemplo, EURO – Association of European Operational Research Societies; IFORS – International Federation of 
Operational Research Societies; APDIO – Associação Portuguesa de Investigação Operacional; ALIO - Asociación Latino-Ibero-
Americana de Investigación Operativa. Provavelmente, a maior destas sociedades profissionais em atuação hoje é o INFORMS 
(Institute for Operations Research and the Management Science), fundado em 1995 (www.informs.org). De fato, os termos 
Operational Research (britânico) / Operations Research (norte americano) são, na prática, sinônimos a Management Science. 
 
No Brasil, há a SOBRAPO (Sociedade Brasileira de Pesquisa Operacional – www.sobrapo.org.br), fundada em 1969. Anualmente 
esta sociedade baliza a realização do SBPO (Simpósio Brasileiro de Pesquisa Operacional). A SOBRAPO edita desde 1981 a revista 
Pesquisa Operacional. Há outros periódicos de impacto na área de PO, conforme a seguir exemplificado: 
 
� EJOR (European Journal of Operational Research) 
� JORS (Journal of the Operational Research Society) 
� Omega – The International Journal of Management Science 
� Annals of Operations Research 
� INFORMS Journal on Computing 
� Decision Support Systems 
� Journal of Scheduling 
� Computers & Operations Research 
� International Journal of Operations Research 
� International Journal of Production Economics 
� International Journal of Production Research 
� Industrial & Engineering Chemistry Research 
� Computers & Chemical Engineering 
� Periódicos da SIAM (Society for Industrial and Applied Mathematics), por exemplo: 
o SIAM Journal on Discrete Mathematics 
o SIAM Journal on Computing 
o SIAM Journal on Optimization 
Pesquisa Operacional – Prof. Leandro Magatão 12
1.5 – A Programação Matemática em PO 
 
A subárea de PO denominada Programação Matemática emprega “símbolos matemáticos” para, a partir da idealização da realidade, 
representar as variáveis do sistema real (Puccini e Pizzolato, 1990), conforme ilustrado na figura 1.5 anteriormente apresentada. De 
forma alternativa, pode-se dizer que a programação matemática engloba técnicas e algoritmos para elaborar e solucionar modelos 
expressos matematicamente. É necessário esclarecer que o termo programação é utilizado no sentido de planejamento e não deve ser 
confundido com a expressão correlata presente na área computacional. 
 
Os modelos de Programação Matemática podem ser entendidos como um conjunto de equações, inequações e dependências lógicas, 
que correspondem a relacionamentos apresentados por estruturas reais. Em um modelo de programação matemática, são incluídos três 
conjuntos principais de elementos (adaptado de Lisboa, 2002): 
 
(i) Variáveis de decisão e parâmetros: variáveis de decisão são as incógnitas a serem determinadaspela solução do modelo. 
Parâmetros são valores fixos no modelo (entradas); 
(ii) Restrições: de modo a levar em conta as limitações físicas do sistema, o modelo deve incluir restrições que limitam os 
valores possíveis (ou viáveis) das variáveis; 
(iii) Função objetivo: é uma função matemática que define a qualidade da solução obtida em função das variáveis de decisão 
empregadas. Via de regra, engloba considerações de “maximização” (e.g., de lucros, produção) ou “minimização” (e.g., de 
custos, tempos, material, trajetórias). 
 
Para ilustrar o acima exposto, considere o seguinte exemplo, adaptado de Lisboa (2002): 
 
Uma empresa produz dois tipos de ração: Ração 1 e Ração 2. Para a elaboração das rações são utilizados cereais e carne. Deseja-se 
saber qual a quantidade de cada ração a produzir de modo a maximizar o lucro. Sabe-se que: 
• A Ração 1 utiliza 5 kg de cereais e 1 kg de carne, e a Ração 2 utiliza 4 kg de carne e 2 kg de cereais; 
• O preço de venda do pacote de Ração 1 (com 6 kg) é de 20 unidades monetárias (20 $); 
• O preço de venda do pacote de Ração 2 (com 6 kg) é de 30 unidades monetárias (30 $); 
• O kg de carne custa 4 $ e o kg de cereais custa 1 $; 
• Estão disponíveis por mês 10 000 kg de carne e 30 000 kg de cereais. 
 
Neste caso, as variáveis de decisão são as quantidades de ração de cada tipo a serem produzidas. Os parâmetros fornecidos são os 
preços unitários de compra e venda, além das quantidades de carne e cereais utilizadas em cada tipo de ração. As restrições são os 
limites de carne e cereais e a função objetivo é uma função matemática que determina o lucro em função das variáveis de decisão. No 
caso, a função objetivo deve ser maximizada. A figura 1.6 ilustra a conexão entre variáveis, restrições e função objetivo. 
 
 
Figura 1.6 – Conexão entre Variáveis, Restrições e Função Objetivo. 
 
A formulação do modelo depende diretamente do sistema a ser representado. A função objetivo e as funções de restrições podem ser 
lineares ou não-lineares. As variáveis de decisão podem ser contínuas ou discretas (por exemplo, inteiras) e os parâmetros podem ser 
determinísticos ou probabilísticos. 
 
O resultado dessa diversidade de representações de sistemas é o desenvolvimento de várias técnicas de otimização, de modo a 
resolver cada tipo de modelo existente. Uma característica presente em quase todas as técnicas de programação matemática é que a 
solução “ótima” (ou melhor, solução possível) do modelo “não pode” ser obtida em um único passo, devendo ser obtida 
iterativamente. Desta forma, é escolhida uma solução inicial (que geralmente não é a solução ótima). Na sequência, um algoritmo é 
especificado para determinar, a partir desta, uma nova solução, que geralmente é superior (melhor) à anterior. Este passo é repetido 
até que a solução “ótima” seja alcançada (supondo que ela existe). 
 
A aplicabilidade da programação matemática em problemas de otimização é vasta, e em virtude das várias peculiaridades de seu uso, 
os métodos de solução sofreram especializações e particularizações, dando origem a diferentes subáreas de estudo, como, por 
exemplo: 
 
(i) Programação Linear (PL); 
(ii) Programação Não Linear (PNL); 
(iii) Programação Inteira (PI) e Programação Linear Inteira Mista (PLIM). 
 
Função 
Objetivo 
Variáveis 
Restrições 
Pesquisa Operacional – Prof. Leandro Magatão 13
1.5.1 – Programação Linear (PL) 
 
Segundo Goldbarg e Luna (2000), a programação linear é um caso particular dos modelos de programação matemática em que as 
variáveis são contínuas e apresentam comportamento linear, tanto nas restrições quanto na função objetivo. Bradley et al. (1977), 
define a programação linear através da formulação (1.1). 
 
0 
 
 
≥
=
x
bAx
cxmax
 (1.1)
onde, x é um vetor coluna n dimensional de variáveis do modelo, c é um vetor linha n dimensional de fatores de ponderação 
(pesos), b é um vetor coluna m dimensional ( m define o número de equações do modelo) e A é uma matriz m por n . A restrição 
x ≥ 0 indica a não-negatividade dos valores de x . 
 
Alternativamente à formulação (1.1), um modelo de programação linear, pode ser representado conforme a formulação (1.1b). Neste 
caso temos “m” restrições e “n” variáveis que foram explicitadas. A formulação apresenta a função objetivo z, os coeficientes ai,j, 
bi (lado direito das inequações ou parâmetros) e cj. 
 
0,02,01
21
221
121
2211max
21
22221
11211
≥≥≥
=⋅++⋅+⋅
=⋅++⋅+⋅
=⋅++⋅+⋅
⋅++⋅+⋅=
xnxx
bmxnaxaxa
bxnaxaxa
bxnaxaxa
xncnxcxc
mnmm
n
n
K
K
MMMM
K
K
K
s.a.
z
 (1.1b) 
 
De forma equivalente, a (1.1b) pode ser expressa conforme a (1.1c): 
 
njx
mibxa
xcz
j
i
n
j
jij
n
j
jj
,,1 0
,,1
1
1
K
K
=∀≥
=∀=
=
∑
∑
=
=
s.a.
max
 
(1.1c)
 
Ou, ainda, conforme a (1.1d) ou (1.1e): 
 
[ ]












≥
























=




































=
0
0
0
2
1
2
1
2
1
21
22221
11211
2
1
21
MMMM
L
MOMM
L
L
M
L
nmnmnmm
n
n
n
n
x
x
x
b
b
b
x
x
x
aaa
aaa
aaa
x
x
x
cccz
es.a.
max
 (1.1d)
 
0≥
=
=
x
bAx
xcz T
 s.a.
max
 
(1.1e)
onde, 












=












=












=












=
mnmm
n
n
mnn aaa
aaa
aaa
A
b
b
b
b
x
x
x
x
c
c
c
c
L
MOMM
L
L
MMM
21
22221
11211
2
1
2
1
2
1
 
 
 
Pesquisa Operacional – Prof. Leandro Magatão 14
1.5.2 – Hipóteses da Programação Linear 
 
As hipóteses (ou limitações) fundamentais de PL são a seguir elencadas (adaptado de Puccini e Pizzolato, 1990) 
 
� Proporcionalidade: todos os retornos/custos e recursos utilizados variam proporcionalmente ao valor da variável do 
modelo. Ou seja, não há “economia de escala”. Por exemplo, custos e quantidades de recursos consumidos em um sistema 
produtivo são proporcionais às quantidades produzidas. Neste contexto, por vezes, é necessário considerar-se intervalos de 
produção onde não existem as economias de escala. 
 
� Aditividade: o efeito total de quaisquer duas variáveis é a soma dos efeitos individuais. Ou seja, não há sinergia ou efeito de 
substituição. Exemplo: o custo total é a soma dos custos individuais. A Proporcionalidade e a Aditividade estabelecem a 
linearidade da função objetivo e das restrições. 
 
� Divisibilidade: as variáveis do modelo podem assumir valores fracionados. Se essas variáveis só puderem assumir valores 
inteiros o problema é de programação inteira (PI), o qual será explorado a posteriori (capítulo 8). 
 
� Certeza (Determinístico): todos os parâmetros do modelo são constantes conhecidas. Por exemplo, não são variáveis 
aleatórias. Os estudos sobre Análise de Sensibilidade ou Pós-Otimização (capítulo 6) podem auxiliar no entendimento das 
flutuações de resposta causadas nos modelos pelas mudanças em coeficientes (ou parâmetros). 
 
Existe a possibilidade de que nem todas estas hipóteses sejam verdadeiras no contexto de modelagem considerado. Cabe ao 
modelador ponderar acerca do tema, entendendo as limitações da abordagem de modelagem proposta. 
 
 
1.5.3 – Programação Linear Inteira Mista, Inteira e Binária 
 
Considerando-se que certas variáveis devam assumir valores inteiros,a formulação (1.2) define um modelo de programação linear 
inteira mista. As variáveis que somente assumem valores inteiros são empregadas para representar condições de indivisibilidade. Por 
exemplo, em um modelo que fosse destinado a determinar a aquisição de equipamentos (máquinas, caminhões, navios, etc.) o 
resultado esperado é um número inteiro. Assim, se postulássemos um modelo que sugerisse a aquisição de 2,6 tratores ou 1,4 
caminhões, esta, certamente, não seria uma resposta adequada. Faz-se necessário que, em alguns casos, as variáveis do modelo 
somente assumam valores indivisíveis. 
 
+∈
≥
=+
+
Zy
x
bGyAx
hycx
 
0 
 
 max
 (1.2)
onde y é um vetor coluna p dimensional de variáveis que devem assumir valores inteiros, h é um vetor linha p dimensional de 
pesos e G é uma matriz m por p . 
 
Classicamente, a diferença entre o número de variáveis )( pn + e o número de equações )(m presentes no modelo é conhecido por 
graus de liberdade apresentados pelo sistema. 
 
Se todas as variáveis na formulação (1.2) assumirem valores inteiros, simplifica-se o sistema para um modelo de programação linear 
inteira, definido segundo a formulação (1.3). 
 
+∈
=
Zy
bGy
hy
 
 
 max
 (1.3)
 
Outro caso particular ocorre quando todas as variáveis assumem valores binários (0/1), sendo configurado um modelo de 
programação linear binária, conforme a formulação (1.4). As variáveis binárias são tipicamente utilizadas nos processos de 
tomada de decisão. Por exemplo, produzo (variável = 1) ou não produzo (variável = 0) este item; compro (variável = 1) ou não 
compro (variável = 0) este produto; contrato (variável = 1) ou não contrato (variável = 0) este funcionário, etc. 
 
{ } 1 0 
 
 
,
max
∈
=
y
bGy
hy
 (1.4) 
 
Pesquisa Operacional – Prof. Leandro Magatão 15
Um modelo pertence à classe de programação não linear se exibir qualquer tipo de não linearidade, seja na função objetivo ou em 
qualquer restrição. Luenberger (1984) realiza uma revisão bibliográfica sobre este tema. O estudo desta classe de modelos está além 
do escopo do presente trabalho. 
 
 
1.5.4 – Equivalências em Programação Matemática 
 
Uma importante observação pode ser realizada em relação à equivalência entre funções de maximização e minimização de modelos, 
conforme segue (Puccini e Pizzolato, 1990): 
 
( ) ( )
( ) ( )∑∑
∑∑
==
==
−=−≡=
−=−≡=
n
j
jj
n
j
jj
n
j
jj
n
j
jj
xczxcz
xczxcz
11
11
maxmin
minmax
 (1.5)
 
Há também a possibilidade de se observar uma relação entre inequações e equações com o uso de variáveis adicionais de folga (F) ou 
excesso (E), conforme segue: 
 





∞≤≤
=−
≡≥





∞≤≤
=+
≡≤
∑
∑
∑
∑
=
=
=
=
i
ii
n
j
jij
i
n
j
jij
i
ii
n
j
jij
i
n
j
jij
E
bExa
bxa
F
bFxa
bxa
0
0
1
1
1
1
 (1.6)
 
Uma grande variedade de problemas práticos podem ser formulados e resolvidos através de uma abordagem baseada em programação 
linear (LP – Linear Programming) e programação linear inteira mista (MILP – Mixed Integer Linear Programming). Dentre os 
problemas clássicos que encontram uma abordagem baseada em MILP temos: problemas de alocação de pessoal, o problema da 
mochila (knapsack problem), problemas de fluxo em rede, problemas de roteamento, problemas de cobertura, particionamento e 
localização, o problema do caixeiro viajante, e todas as variantes e combinações destas formulações clássicas. Segundo Wolsey 
(1998), algumas áreas de aplicação incluem, por exemplo, problemas em biologia molecular. Uma coletânea completa com 
formulações clássicas pode ser encontrada em (Nemhauser e Wolsey, 1988). 
 
A bibliografia em programação inteira (mista) é vasta e cobre diferentes abordagens. Papadimitriou e Stieglitz (1982) enfatizam 
algoritmos e complexidade computacional de um ponto de vista de cientistas da computação. Gondran e Minoux (1984) também 
tratam de algoritmos e apresentam uma abordagem baseada na teoria de grafos. Em (Lawler et al., 1995) é realizado um estudo 
restrito do problema do caixeiro viajante, conhecido por sua natureza combinatória de difícil resolução. Em (Schrijver, 1986) é 
apresentado um tratamento da teoria de programação linear e inteira baseado em poliedros. Sherali e Driscoll (2000) apresentam um 
breve estado da arte sobre teoria de poliedros, algoritmos híbridos, técnicas de reformulação e linearização, programação disjuntiva, 
programação inteira estocástica, meta-heurísticas e processamento paralelo. É importante ressaltar que cada subárea de estudo 
desenvolve técnicas e modelos específicos para a resolução de famílias de problemas. 
 
No próximo capítulo iniciaremos o emprego de Programação Linear na representação de problemas. Serão ressaltados aspectos de sua 
aplicabilidade, métodos de solução e limitações. Este será um passo inicial e primordial para o entendimento do uso de modelos de 
programação matemática na resolução de problemas práticos. 
 
 
Pesquisa Operacional – Prof. Leandro Magatão 16
2. O MÉTODO GRÁFICO PARA RESOLUÇÃO DE MODELOS DE PROGRAMAÇÃO LINEAR 
 
1 
2.1 – Programação Linear: Introdução 
 
O problema geral de programação linear (PL) é utilizado para otimizar (maximizar ou minimizar) uma função linear de variáveis, 
chamada de “função objetivo” (z), sujeita a uma série de equações ou inequações lineares, as restrições. Ou seja, de forma 
simplificada tem-se: 
Modelo do Restrições
(z) Objetivo Função
)s.a.( 
(min)
(max)
asujeito
Minimizar
ou
Maximizar
 
 
A formulação do modelo a ser resolvido por programação linear segue alguns passos fundamentais (Lisboa, 2002). 
• Deve ser definido o objetivo básico do estudo, ou seja, a otimização a ser alcançada. Por exemplo, maximização de lucros, ou de 
desempenhos; minimização de custos, de perdas, de tempo. Tal objetivo será representado por uma função objetivo, a ser 
maximizada ou minimizada; 
• Para que esta função objetivo seja matematicamente especificada, devem ser definidas as variáveis de decisão envolvidas. Por 
exemplo, o número de máquinas a serem utilizadas, a área a ser explorada, as classes de investimento à disposição, etc. 
Normalmente, assume-se que todas estas variáveis devam possuir somente valores positivos (restrições de não-negatividade); 
• Estas variáveis normalmente estão sujeitas a uma série de restrições, normalmente representadas por inequações. Por exemplo, 
quantidade de equipamento disponível, tamanho da área a ser explorada, capacidade de um reservatório, exigências nutricionais 
para determinada dieta, etc. 
 
Todas essas expressões, entretanto, devem estar de acordo com a hipótese principal da programação linear, ou seja, todas as relações 
entre as variáveis devem ser lineares. Isto implica proporcionalidade das quantidades envolvidas. Esta característica de linearidade 
pode ser interessante no tocante à simplificação da estrutura matemática envolvida, mas prejudicial na representação de fenômenos 
não lineares, por exemplo, funções de custo com comportamento quadrático. 
 
Para melhor ilustrar o acima exposto, retomemos o exemplo de formulação de rações: 
Uma empresa produz dois tipos de ração: Ração 1 e Ração 2. Para a elaboração das rações são utilizados cereais e carne. Sabe-se que: 
• A Ração 1 utiliza 1 kg de carne e 5 kg de cereais, e a Ração 2 utiliza 4 kg de carne e 2 kg de cereais; 
• O preço de venda do pacote de Ração 1 (com 6 kg) custa 20 $; 
• O preço de venda do pacote de Ração 2 (com 6 kg) custa 30 $; 
• O kg de carne custa 4 $ e o kg de cereais custa 1 $; 
• Estão disponíveis por mês 10 000 kg de carne e 30 000 kg de cereais. 
Deseja-sesaber qual a quantidade de cada ração a produzir de modo a maximizar o lucro. 
 
No caso, as quantidades de Ração 1 e de Ração 2 produzidas influenciam diretamente o lucro obtido. A Tabela 2.1 apresenta o cálculo 
do lucro unitário de cada tipo de ração. 
 
Tabela 2.1 - Cálculo do Lucro Unitário de Cada Ração 
 Ração 1 Ração 2 
Custo de carne 4 $ (1 kg x 4 $/kg) 16 $ (4 kg x 4 $/kg) 
Custo de cereais 5 $ (5 kg x 1 $/kg) 2 $ (2 kg x 1 $/kg) 
Custo total 9 $ (4+5) 18 $ (16+2) 
Preço (por pacote) 20 $ 30 $ 
Lucro (por pacote) 11 $ (20-9) 12 $ (30-18) 
 
O cenário descrito é representado pelo modelo de programação linear a seguir exposto. No caso, considera-se que as variáveis x1 e x2 
representam as quantidades de pacotes de Ração 1 e Ração 2 produzidos e o lucro obtido é simbolizado pela variável z. Logo, z é 
uma função da quantidade de pacotes de Ração 1 e Ração 2 produzidos. Obviamente, se considerarmos que o mercado absorve a 
produção, quanto maior o número de pacotes produzidos, maior o lucro obtido. Contudo, as quantidades de carne e cereais disponíveis 
são limitadas a, respectivamente, 10 000 kg e 30 000 kg por mês. O modelo também considera estas restrições, levando em conta que 
cada pacote de x1 produzido utiliza 1 kg de carne e 5 kg de cereais e cada pacote de x2 utiliza 4 kg de carne e 2 kg de cereais. Há 
ainda restrições de não-negatividade expressando que a quantidade de pacotes produzidos deve ser igual ou superior a zero. 
 
de)negativida-não de (restrição
de)negativida-não de (restrição
cereais) de quantidade de (restrição
)carne de quantidade de restrição(.).( 
)Objetivo Função((max)
02
01
300002215
100002411
212111
≥
≥
≤⋅+⋅
≤⋅+⋅
⋅+⋅=
x
x
xx
xxasasujeito
xxMaximizar z
 
Pesquisa Operacional – Prof. Leandro Magatão 17
2.2 – O Método Gráfico 
 
Uma vez elaborado o modelo de otimização, no caso, o modelo de programação linear, há necessidade de solucioná-lo. Existe a 
possibilidade de solução gráfica para modelos de PL, contudo, tal solução pode ser empregada em modelos com, no máximo, 
3 variáveis. Portanto seu uso é limitado em situações reais, onde o número de variáveis pode chegar a dezenas de milhares. Contudo, 
o Método Gráfico é uma ferramenta “didática” que permite a compreensão de alguns conceitos de PL, particularmente a natureza 
algébrica/geométrica deste tipo de modelo. 
 
Representação do Espaço de Soluções de Modo Gráfico 
 
Para esta análise será utilizado o exemplo anterior que possui somente duas variáveis (x1 e x2). Logo, a representação terá duas 
dimensões. Inicialmente traça-se um gráfico com os eixos sendo as duas variáveis em análise, x1 e x2. A partir daí, traçam-se as 
“retas limítrofes” referentes às restrições do modelo, ou seja, “ 100002411 =⋅+⋅ xx ” e “ 300002215 =⋅+⋅ xx ” (note o sinal = nas 
restrições e não ≤ como originalmente apresentado). A partir das retas limítrofes, e considerando-se os sinais das inequações, 
delimita-se a região viável (Região Factível), conforme figura 2.1. Vale notar que as restrições de não-negatividade (x1 ≥ 0 e x2 ≥ 0) 
também são consideradas na delimitação da região de soluções válidas. Ou seja, somente os valores que estão contidos na região 
destacada da figura satisfazem a todas às restrições do modelo simultaneamente. 
 
x2 (103) 
 
15 
 
 
 
14 
 
 
 
13 
 
 
 
12 
 
 
 
11 
 
 
 
10 
 
 
 
9 
 
 
 
8 
 
 
 
7 
 
 
 
6 
 
 
 
5 
 
 
 
4 
 
 
 
3 
 
 
 
2 
 
 
 
1 
 
 
 
 
 
 
0 1 2 3 4 5 6 7 8 9 10 11 12 x1 (103) 
 
 
Figura 2.1 – Método Gráfico: Ilustração de Região Factível. 
 
Encontrada a região factível, deve-se agora, buscar o ponto (ou pontos) dentro deste espaço de soluções válidas que apresenta o maior 
lucro (modelo de maximização) ou o menor custo (modelo de minimização). Ou seja, deve-se determinar a combinação de valores de 
x1 e x2 (compreendidos na região factível) que devolvem o melhor resultado (resultado “ótimo”) para a função de avaliação ou 
função objetivo. 
 
Dentro do procedimento gráfico, traça-se uma reta com a inclinação da função objetivo. Para isto, arbitra-se um valor para z, por 
exemplo z1, encontrando-se os valores de x1 e x2 que geram o valor de z imposto (e.g. z1). Conforme ilustrado na figura 2.2, no caso 
em análise, arbitrou-se z1 = 13200, obtendo-se a reta z1. São então traçadas diversas paralelas a esta reta no sentido de z crescente 
(maximização da função), ou seja, z1 < z2 < z3 <...< zmax. O ponto ótimo é o ponto onde a reta de maior valor possível para z corta a 
região viável, normalmente num vértice do polígono em análise. No caso, o vértice x1 ≈ 5500 e x2 ≈ 1100 determina o ponto de 
máximo valor possível para a função objetivo (zmax), não violando nenhuma das restrições do modelo. Ou seja, é o ponto de máximo 
procurado para a função de avaliação (z). 
 
Vale ressaltar que se os coeficientes da função objetivo forem alterados, a orientação (angulação) das retas z1 < z2 < z3 <...< zmax 
será alterada. Existe, inclusive, a possibilidade matemática de que a reta que define o valor de zmax esteja exatamente paralela à 
“aresta mais afastada” do polígono (maximização). Neste caso, teremos diferentes combinações de valores de x1 e x2 que geram o 
mesmo valor de z. Ou seja, teremos uma região de máximos (segmento de reta) e não somente um ponto de máximo da função. Por 
exemplo, no modelo em análise, se somente a função objetivo fosse alterada para 2411 xx ⋅+⋅=z permanecendo todas as restrições 
do sistema, configurar-se-ía o caso de uma região de máximos ao invés de um ponto de máximo. 
10000102/
2500201/100002411
6000102/
15000201/300002215
:Limítrofes Retas
=∴=
=∴==⋅+⋅
=∴=
=∴==⋅+⋅
xxp
xxpxx
xxp
xxpxx
Região Factível 
Pesquisa Operacional – Prof. Leandro Magatão 18
x2 (103) 
 
15 
 
 
 
14 
 
 
 
13 
 
 
 
12 
 
 
 
11 
 
 
 
10 
 
 
 
9 
 
 
 
8 
 
 
 
7 
 
 
 
6 
 
 
 
5 
 
 
 
4 
 
 
 
3 
 
 
 
2 
 
 
 
1 
 
 
 
 
 
 
0 1 2 3 4 5 6 7 8 9 10 11 12 x1 (103) 
 
 
Figura 2.2 – Método Gráfico: Ilustração de Ponto Ótimo. 
 
Exemplo 2: Para o modelo de programação linear a seguir expresso, determine a região de soluções válidas para x1 e x2 (Região 
Factível) e o valor máximo de z. Utilize o Método Gráfico previamente discutido. 
 
02,1
162
241
402211.).( 
240130(max)
≥
≤
≤
≤⋅+⋅
⋅+⋅=
xx
x
x
xxasasujeito
xxMaximizar z
 
 
 
x2 
 
 
 
 
 
 
 
25 
 
 
 
 
 
20 
 
 
 
 
 
15 
 
 
 
 
 
10 
 
 
 
 
 
5 
 
 
 
 
 
 
 
 
 
0 5 10 15 20 2530 35 40 x1 
 
1200102/
1100201/
132001 supondo212111
=∴=
=∴=
=⋅+⋅=
xxp
xxp
xx z z
Ponto de zmax 
x1 ≈ 5500 
x2 ≈ 1100 z1 = 13200 
z1 < z2 
z2 < z3 
z3 < zmax 
Pesquisa Operacional – Prof. Leandro Magatão 19
 
2.2.1 – Método Gráfico: Exemplo com 3 Variáveis 
 
Considere-se o modelo de PL a seguir apresentado (adaptado de Williams, 2009): 
 
+∈
≤⋅++
≤−+−
⋅+⋅+⋅−=
Rxxx
xxx
xxxas
xxx
3,2,1
33221
2321.).(
332514(max) z
 
 
A Figura 2.3 ilustra o espaço de soluções válidas do modelo LP de 3 variáveis apresentado. É possível observar na figura a existência 
de 6 vértices: O (0;0;0), A (0;0;3/2), B (3;0;0), C (0;7/3;1/3), D (1/2;5/2;0) e E (0;2;0). A orientação do plano da função objetivo 
conduz ao vértice C como sendo o de solução ótima. Neste caso, o valor da função objetivo no ponto de máximo é 38/3. No exemplo 
evidencia-se que o método gráfico possui escopo didático e sua aplicação é limitada a modelos de PL com, no máximo, 3 variáveis. 
 
 
Figura 2.3 – Método Gráfico: Ilustração de LP com 3 Variáveis. 
 
 
 
x1 
x3 
x2 
Plano da 
função 
objetivo 
D (1/2;5/2;0) 
B (3;0;0) 
O (0;0;0) 
E (0; 2;0) 
C (0;7/3;1/3) 
A (0;0;3/2) 
Pesquisa Operacional – Prof. Leandro Magatão 20
3. EXEMPLOS INICIAIS DE MODELOS DE PL 
 
O objetivo deste capítulo é apresentar alguns exemplos de formulação de modelos de PL. Tais exemplos são, via de regra, exercícios 
adaptados de livros clássicos de Pesquisa Operacional, conforme referências bibliográficas. 
 
Problema 1: Uma determinada empresa produz álcool anidro e álcool hidratado, a partir de uma usina que está organizada em três 
setores de produção. O processo de produção pode ser resumido da seguinte forma: o álcool anidro (AA) passa pelos setores I e III, 
sendo que cada tonelada desse produto consome 1/2 hora do setor I e 1/3 hora do setor III, diariamente. Por outro lado, a produção de 
uma tonelada do álcool hidratado (AH) demanda 1 hora do setor II e 2/3 hora do setor III, também diariamente, conforme ilustrado na 
figura. 
 
 
Admitindo que cada setor esteja em operação 8 horas por turno, e que as receitas líquidas a serem obtidas para o álcool anidro e álcool 
hidratado sejam $ 40 e $ 30 por tonelada, respectivamente, qual deve ser a combinação ótima de produção dos diferentes tipos de 
álcool? (adaptado de Lisboa, 2002). 
 
Definição de Variáveis: 
1x : Quantidade de álcool anidro a ser produzida por setor. Valor dado em toneladas. 
2x : Quantidade de álcool hidratado a ser produzida por setor. Valor dado em toneladas. 
 
Modelo: 
III)setor no ntoprocessame de tempode idadedisponibil de (restrição8
3
2
3
1
II)setor no hidratado álcool do ntoprocessame de tempode idadedisponibil de (restrição81
I)setor no anidro álcool do ntoprocessame de tempode idadedisponibil de (restrição8
2
1
a sujeito
objetivo) (função3040maximizar
21
2
1
21
≤+
≤
≤
+=
xx
x
x
xxz
 
 
Resolução Gráfica: (Solução: 760416 21 === zxx ) 
 
 
 
 
Problema 2: Uma determinada empresa quer utilizar do melhor modo possível os recursos de madeira de uma de suas regiões 
florestais. Dentro dessa região, há uma serraria e uma fábrica de compensados, o que possibilita que as toras possam ser convertidas 
em madeira beneficiada ou compensada. A produção de uma mistura comercializável de 1 m³ de produtos beneficiados requer 1 m³ de 
pinho e 4 m³ de canela. Produzir 100 m² de madeira compensada requer 2 m³ de pinho e 4 m³ de canela. A região em questão dispõe 
de 32 m³ de pinho e 72 m³ de canela. Compromissos de vendas exigem que sejam produzidos, durante o período em planejamento, 
pelo menos 5 m³ de madeira beneficiada e 800 m² de madeira compensada. As contribuições ao lucro são de $ 45 por 1 m³ de 
produtos beneficiados e $ 60 por 100 m² de madeira compensada. Determine as quantidades (em m³) de madeira beneficiada e de 
madeira compensada (em 100 m²) a serem produzidas (adaptado de WAGNER, 1986). 
 
Definição de Variáveis: 
1x : Quantidade de madeira beneficiada a ser produzida. Valor dado em m³. 
2x : Quantidade de madeira compensada a ser produzida. Valor dado em 100 m². 
 
Modelo: 
)compensada madeira de mínima (produção8
a)beneficiad madeira de mínima (produção5
canela) de idadedisponibil de (restrição7244
pinho) de idadedisponibil de (restrição3221a sujeito
objetivo) (função6045maximizar
2
1
21
21
21
≥
≥
≤+
≤+
+=
x
x
xx
xx
xxz
 
Resolução Gráfica: (Solução: 1005135 21 === zxx ) 
 
Setor I Setor II Setor III AA 
AH 
AA 
AH 
Pesquisa Operacional – Prof. Leandro Magatão 21
 
 
 
Problema 3: Uma empresa deseja produzir ração para aves a um custo mínimo pela mistura de dois produtos. O produto “A” 
apresenta um custo de $0,03 por kg gasto e o produto “B” $0,04 por kg gasto. Sabe-se que as aves necessitam de quantidades mínimas 
de nutrientes (vitaminas) por semana, dado ilustrado no quadro a seguir. Os nutrientes serão obtidos a partir dos produtos A e B, que 
farão parte da mistura. Tais produtos possuem composições diferenciadas, também ilustradas no quadro a seguir. Baseado nestes 
fatos, determine a mistura ideal dos componentes “A e B” que minimiza os custos de produção da ração (adaptado de PRADO, 2004). 
 
Nutriente Mínimo Semanal (em unidades) 
Composição 
(unidades de nutrientes por kg de produto) 
Produto A Produto B 
1 50 5 25 
2 100 25 10 
3 60 10 10 
 
Definição de Variáveis: 
A : Quantidade do componente “A” que deve ser adicionada à mistura. Valor dado em kg. 
B : Quantidade do componente “B” que deve ser adicionado à mistura. Valor dado em kg. 
 
Modelo: 
3) nutriente do semanal mínimo de (restrição601010
2) nutriente do semanal mínimo de (restrição1001025
1) nutriente do semanal mínimo de (restrição50255a sujeito
objetivo) (função040030
≥+
≥+
≥+
+=
BA
BA
BA
BA ,,minimizar z
 
 
Resolução Gráfica: (Solução: 19,015 === zBA ) 
 
 
 
 
Observação: Segundo Puccini e Pizzolato (1990), numa empresa típica de produção de ração cada produto final envolve o uso de 
aproximadamente trinta possíveis ingredientes e considera-se cerca de doze restrições de nutrientes mínimos/máximos. Se a empresa 
produzir vinte e cinco tipos de rações ela teria 25 modelos com 12 restrições e 30 variáveis. Entretanto, como muitos ingredientes 
costumam ter fornecimento limitado, os 25 modelos devem ser “agrupados” e resolvidos simultaneamente, incluindo-se restrições de 
oferta. Em síntese, o modelo final ultrapassa 300 linhas de restrições. Por outro lado, devido às variações de preços, ofertas de 
produtos e demanda por rações, o modelo deve ser resolvido, pelo menos, duas vezes ao mês. Ou seja, diante do cenário apresentado, 
o uso de um modelo como ferramenta de auxílio ao processo de decisão de produção pode ser de grande valia. 
 
 
 
Problema 4: Uma fábrica produz os modelos A, B e C de um certo produto, que proporcionam lucros unitários da ordem de $ 16, 
$ 30 e $ 50, respectivamente. As exigências de produção mínimas mensais são de 20 unidades (un.) para o modelo A, 120 un. para o 
modelo B e 60 un. para o modelo C. Cada produto requer certa quantidade de tempo para a fabricação das partes componentes, para a 
montagem e para testes de qualidade. Especificamente, um lote do modelo A, que contém 12 unidades, requer três horas para fabricar, 
quatro horas para montar e uma para testar. Os números correspondentes para um lote (12 un.) do modelo B são 3,5, 5 e 1,5; e para 
um lote (12 un.) do modelo C, são 5, 8 e 3. Durante o próximo mês, a fábrica tem disponíveis 120 horas de tempo de fabricação, 160 
horas de montagem e 48 horas de testes de qualidade. Formule e resolva este problema de programação de produção como um modelode programação linear (adaptado de WAGNER, 1986). 
 
Pesquisa Operacional – Prof. Leandro Magatão 22
 
Modelos Lucro unitário ($) 
Tempo para fabricação dos componentes (h) 
(por unidade) Produção mínima mensal (unidades) Fabricação Montagem Teste 
A 16 3/12 4/12 1/12 20 
B 30 3,5/12 5/12 1,5/12 120 
C 50 5/12 8/12 3/12 60 
Tempo disponível (h) 120 160 48 
 
 
 
Definição de Variáveis: 
1x : Número de unidades produzidas do produto A. 
2x : Número de unidades produzidas do produto B. 
3x : Número de unidades produzidas do produto C. 
 
Modelo: 
C) produto do mínima (produção60
B) produto do mínima (produção120
A) produto do mínima (produção20
qualidade) de ão verificaçde tempode idadedisponibil de (restrição124835,11
montagem) de tempode idadedisponibil de (restrição12160854
)fabricação de tempode idadedisponibil de (restrição1212055,33a sujeito
objetivo) (função503016maximizar
3
2
1
321
321
321
321
≥
≥
≥
⋅≤++
⋅≤++
⋅≤++
++=
x
x
x
xxx
xxx
xxx
xxxz
 
 
Solução obtida: 108406067,25020 321 ==≈= zxxx 
 
Obs. 1: Notar que a disponibilidade dos tempos de fabricação, montagem e testes de qualidade foram inicialmente expressos para um 
lote (12 unidades produzidas), conforme dados do enunciado do problema. Alternativamente, a definição de variáveis poderia ter sido 
feita em função do número de lotes produzidos, ficando, obviamente, modificada a forma de expressar o modelo. 
 
Obs. 2: As variáveis que queremos determinar indicam o número de unidades produzidas por produto (A, B ou C). A resposta do 
modelo sugere que sejam fabricadas 250,67 unidades do produto B. Neste caso, o valor obtido deveria ser inteiro. Adiante veremos 
como resolver problemas que requerem respostas utilizando variáveis inteiras e/ou binárias (0/1, falso/verdadeiro). 
 
Problema 5: Uma refinaria produz três tipos de gasolina: verde, azul e comum. Cada tipo requer gasolina pura, octana e aditivo, que 
são disponíveis nas quantidades de 9.000.000, 4.800.000 e 2.200.000 litros por semana, respectivamente. As especificações de cada 
tipo de gasolina são sumarizadas a seguir: 
• um litro de gasolina verde requer 0,22 litro de gasolina pura, 0,50 litro de octana e 0,28 litro de aditivo; 
• um litro de gasolina azul requer 0,52 litro de gasolina pura, 0,34 litro de octana e 0,14 litro de aditivo; 
• um litro de gasolina comum requer 0,74 litro de gasolina pura, 0,20 litro de octana e 0,06 litro de aditivo. 
Como regra de produção, baseada em demanda de mercado, o planejamento da refinaria estipulou que a quantidade de gasolina 
comum deve ser no mínimo igual a 16 vezes a quantidade de gasolina verde e que a quantidade de gasolina azul seja no máximo igual 
a 600.000 litros por semana. A empresa sabe que cada litro de gasolina verde, azul e comum dá uma margem de contribuição para o 
lucro de $ 0,30, $ 0,25 e $ 0,20 respectivamente. O objetivo da refinaria é determinar o programa de produção que maximiza a 
margem total de contribuição para o lucro (adaptado de ANDRADE, 2000). 
 
Definição de Variáveis: 
1x : Quantidade de gasolina verde a ser produzida. Valor dado em litros. 
2x : Quantidade de gasolina azul a ser produzida. Valor dado em litros. 
3x : Quantidade de gasolina comum a ser produzida. Valor dado em litros. 
 
Modelo: 
azul) gasolina de máxima (produção600000
gas.verde) de a quemaior vezesmenos16 ao comum gas. de (produção16
aditivo) de idadedisponibil de (restrição220000006,014,028,0
octana) de idadedisponibil de (restrição480000020,034,050,0
pura) gasolina de idadedisponibil de (restrição900000074,052,022,0a sujeito
objetivo) (função20,025,030,0maximizar
2
31
321
321
321
321
≤
≤
≤++
≤++
≤++
++=
x
xx
xxx
xxx
xxx
xxxz
 
 
Solução obtida: 267139011526400600000398,720 321 ==≈≈ zxxx 
 
 
Pesquisa Operacional – Prof. Leandro Magatão 23
Problema 6: Uma companhia petroquímica deseja encontrar a combinação ótima de dois possíveis processos de mistura. Para o 
processo l, uma entrada unitária de um barril de óleo cru A e três barris de óleo cru B produz uma saída de 50 galões de gasolina X e 
20 galões de gasolina Y. Para o processo 2, uma entrada unitária de quatro barris de óleo cru A e dois barris de óleo cru B produz uma 
saída de 30 galões de gasolina X e 80 galões de gasolina Y. A quantidade máxima de óleo cru A disponível é de 120 barris, e de óleo 
cru B, 180 barris. Compromissos de vendas exigem que pelo menos 2800 galões de gasolina X e 2200 galões de gasolina Y sejam 
produzidos. Os lucros unitários do processo 1 e do processo 2 são p1 e p2, respectivamente. Formule este problema como um modelo 
de programação linear (adaptado de WAGNER, 1986). 
 
Definição de Variáveis: 
1x : Número de unidades de entrada que a companhia decide realizar do processo 1. 
2x : Número de unidades de entrada que a companhia decide realizar do processo 2. 
 
Modelo: 
Y) gasolina mínima (produção22008020
X) gasolina mínima (produção28003050
B)cru óleo de idadedisponibil de (restrição18023
A)cru óleo de idadedisponibil de (restrição12041a sujeito
objetivo) (funçãomaximizar
21
21
21
21
2211
≥+
≥+
≤+
≤+
⋅+⋅=
xx
xx
xx
xx
xpxpz
 
 
 
Problema 7: O processo de fabricação de cimento pode ser representado por um fluxo de materiais, conforme a figura a seguir 
apresentada. Basicamente, dois produtos são fabricados: cimento portland 320: CP320 e cimento alto-forno 250: AF250. As fórmulas 
convencionais de fabricação dos dois tipos de cimento são resumidas no quadro que segue. A produção de clínquer é limitada a um 
máximo de 1.100.000 toneladas por ano (capacidade do forno). Da mesma forma, a produção dos dois tipos de cimento também é 
limitada a 1.100.000 toneladas por ano (capacidade do moinho). As seguintes limitações adicionais são conhecidas: 
• venda de clínquer a outros fabricantes de cimento: máximo de 200.000 ton/ano; 
• compra de escória de usinas siderúrgicas: máximo de 180.000 ton/ano; 
• compra de gesso e aditivo (cada um): máximo de 50.000 ton/ano. 
Por outro lado, os seguintes dados de lucros e custos são conhecidos: 
• contribuição marginal do CP320: $ 41,00/ton; 
• contribuição marginal do AF250: $ 37,80/ton; 
• contribuição marginal do clínquer: $ 34,40/ton; 
• preço da escória de siderúrgica: $ 22,10/ton; 
• preço do gesso: $ 34,20/ton; 
• preço do aditivo: $ 1,90/ton. 
A contribuição marginal é calculada como a receita líquida menos os custos fixos e variáveis, exceto escória, gesso e aditivo. O 
objetivo da empresa é calcular a produção total anual que maximiza o lucro total (adaptado de Lisboa, 2002). 
 
 
Componentes CP320 AF250 
Clínquer 85% 50% 
Escória de alto-
forno 
7% 45% 
Gesso 3% 3% 
Aditivo 5% 2% 
 
 
 
 
 
 
Definição de Variáveis: 
1x : Quantidade de cimento CP320. Valor dado em toneladas. 
2x : Quantidade de cimento AF250. Valor dado em toneladas. 
3x : Quantidade de clínquer vendida. Valor dado em toneladas. 
 
Modelo: 
Pesquisa Operacional – Prof. Leandro Magatão 24
aditivo) de utilização de (restrição5000002,005,0
gesso) de utilização de (restrição5000003,003,0
escória) de utilização de (restrição18000045,007,0
clínquer) de consumo de (restrição1100000150,085,0
clínquer) de vendade (restrição200000
cimento) de máxima produção de (restrição1100000a sujeito
objetivo) (função40,3479,2633,38maximizar
21
21
21
321
3
21
321
≤+
≤+
≤+
≤++
≤
≤+
++=
xx
xx
xx
xxx
x
xx
xxxz
 
 
Obs.: Notar que os coeficientes da função objetivo foram obtidos a partir dos dados do enunciado do problema, através da seguinte 
expressão: )02,005,0(90,1)03,003,0(2,34)45,007,0(1,224,348,3741 212121321 xxxxxxxxx +⋅−+⋅−+⋅−++=z . 
 
Solução obtida: 47119700200000166667933333