APOSTILA DE PESQUISA OPERACIONAL

Prévia do material em texto

Pesquisa Operacional I 
1 
Pesquisa Operacional I 
Alexander Cascardo Carneiro 
Edison Alves Portela Junior 
1ª
 e
di
çã
o 
Pesquisa Operacional I 
2 
 
DIREÇÃO SUPERIOR 
Chanceler Joaquim de Oliveira 
Reitora Marlene Salgado de Oliveira 
Presidente da Mantenedora Wellington Salgado de Oliveira 
Pró-Reitor de Planejamento e Finanças Wellington Salgado de Oliveira 
Pró-Reitor de Organização e Desenvolvimento Jefferson Salgado de Oliveira 
Pró-Reitor Administrativo Wallace Salgado de Oliveira 
Pró-Reitora Acadêmica Jaina dos Santos Mello Ferreira 
Pró-Reitor de Extensão Manuel de Souza Esteves 
 
DEPARTAMENTO DE ENSINO A DISTÂNCIA 
Gerência Nacional do EAD Bruno Mello Ferreira 
Gestor Acadêmico Diogo Pereira da Silva 
 
FICHA TÉCNICA 
Texto: Alexander Cascardo Carneiro e Edison Alves Portela Junior 
Revisão Ortográfica: Rafael Dias de Carvalho Moraes 
Projeto Gráfico e Editoração: Antonia Machado, Eduardo Bordoni, Fabrício Ramos e Victor Narciso 
Supervisão de Materiais Instrucionais: Antonia Machado 
Ilustração: Eduardo Bordoni e Fabrício Ramos 
Capa: Eduardo Bordoni e Fabrício Ramos 
 
COORDENAÇÃO GERAL: 
Departamento de Ensino a Distância 
Rua Marechal Deodoro 217, Centro, Niterói, RJ, CEP 24020-420 www.universo.edu.br 
 
Ficha catalográfica elaborada pela Biblioteca Universo – Campus Niterói 
 
C289p Carneiro, Alexander Cascardo. 
Pesquisa operacional I / Alexander Cascardo Carneiro e Edison 
Alves Portela Junior ; revisão de Rafael Dias de Carvalho Moraes. – 
1. ed. – Niterói, RJ: UNIVERSO: Departamento de Ensino à 
Distância, 2018. 
233 p. : il. 
 
1. Pesquisa operacional. 2. Programação linear. 3. Método 
Simplex. 4. Dualidade (Matemática). 5. Análise de sensibilidade. 6. 
Problema de localização - alocação. 7. Transporte de mercadorias 
- Programação linear. 8. Administração de pessoal - Programação 
linear. 9. Ensino à distância. I. Portela Junior, Edison Alves. II. 
Moraes, Rafael Dias de Carvalho. III. Título. 
CDD 658.4034 
 
Bibliotecária responsável: Elizabeth Franco Martins CRB 7/4990 
 
Informamos que é de única e exclusiva responsabilidade do autor a originalidade desta obra, não se r esponsabilizando a ASOEC 
pelo conteúdo do texto formulado. 
© Departamento de Ensi no a Dist ância - Universidade Salgado de Oliveira 
Todos os direitos reservados. Nenhuma parte desta publicação pode ser reproduzida, arquivada ou transmitida de nenhuma forma 
ou por nenhum meio sem permissão expressa e por escrito da Associação Salgado de Oliveira de Educação e Cultura, mantenedora 
da Univer sidade Salgado de Oliveira (UNIVERSO). 
Pesquisa Operacional I 
3 
 
Palavra da Reitora 
 
Acompanhando as necessidades de um mundo cada vez mais complexo, 
exigente e necessitado de aprendizagem contínua, a Universidade Salgado de 
Oliveira (UNIVERSO) apresenta a UNIVERSOEAD, que reúne os diferentes 
segmentos do ensino a distância na universidade. Nosso programa foi 
desenvolvido segundo as diretrizes do MEC e baseado em experiências do gênero 
bem-sucedidas mundialmente. 
São inúmeras as vantagens de se estudar a distância e somente por meio 
dessa modalidade de ensino são sanadas as dificuldades de tempo e espaço 
presentes nos dias de hoje. O aluno tem a possibilidade de administrar seu próprio 
tempo e gerenciar seu estudo de acordo com sua disponibilidade, tornando-se 
responsável pela própria aprendizagem. 
O ensino a distância complementa os estudos presenciais à medida que 
permite que alunos e professores, fisicamente distanciados, possam estar a todo o 
momento, ligados por ferramentas de interação presentes na Internet através de 
nossa plataforma. 
Além disso, nosso material didático foi desenvolvido por professores 
especializados nessa modalidade de ensino, em que a clareza e objetividade são 
fundamentais para a perfeita compreensão dos conteúdos. 
A UNIVERSO tem uma história de sucesso no que diz respeito à educação a 
distância. Nossa experiência nos remete ao final da década de 80, com o bem-
sucedido projeto Novo Saber. Hoje, oferece uma estrutura em constante processo 
de atualização, ampliando as possibilidades de acesso a cursos de atualização, 
graduação ou pós-graduação. 
Reafirmando seu compromisso com a excelência no ensino e compartilhando 
as novas tendências em educação, a UNIVERSO convida seu alunado a conhecer o 
programa e usufruir das vantagens que o estudar a distância proporciona. 
Seja bem-vindo à UNIVERSOEAD! 
Professora Marlene Salgado de Oliveira 
Reitora. 
Pesquisa Operacional I 
4 
 
Pesquisa Operacional I 
5 
 
Sumário 
 
Apresentação da disciplina ............................................................................................. 07 
Plano da disciplina ............................................................................................................ 09 
Unidade 1 – Programação Matemática ........................................................................ 11 
Unidade 2 – Programação Linear .................................................................................. 31 
Unidade 3 – O Método Simplex ..................................................................................... 45 
Unidade 4 – Dualidade..................................................................................................... 73 
Unidade 5 – Análise de Sensibilidade........................................................................... 93 
Unidade 6 – O Problema de Transporte....................................................................... 107 
Unidade 7 – O Problema de Designação ..................................................................... 131 
Considerações finais ......................................................................................................... 151 
Conhecendo o autor ......................................................................................................... 152 
Referências .......................................................................................................................... 153 
Anexos.................................................................................................................................. 155 
 
Pesquisa Operacional I 
6 
 
Pesquisa Operacional I 
7 
 
 
Apresentação da Disciplina 
 
Sejam bem-vindos a disciplina: Pesquisa Operacional I! 
Ao início de cada unidade de estudo, você encontrará uma apresentação dos 
temas que serão desenvolvidos, os aspectos mais relevantes, além dos objetivos a 
serem alcançados. Além disso, há também uma série de referências bibliográficas 
sobre os assuntos abordados. 
As unidades foram redigidas de forma a facilitar o entendimento do seu 
conteúdo, que compreende uma parte conceitual, sempre com aplicações dos 
conceitos, seguida de exercícios práticos. 
Estamos certos de que a leitura dos conteúdos será uma atividade prazerosa. 
Porque a profissão de engenheiro requer muito estudo e aprimoramento que 
dependem diretamente dela. 
A disciplina em questão é uma ferramenta poderosa para os engenheiros, 
preferencialmente os de produção, na sua aplicação em otimização dos processos 
de manufatura ou de serviço. 
Utilize o seu tempo e imprima o seu próprio ritmo de aprendizagem. Lembre-
se, você tem total autonomia na condução do seu processo de estudo, mas sempre 
que possível procure seguir o cronograma da disciplina. 
É importante que você faça todas as atividades e reflita sobre os respectivos 
padrões de respostas. Além disso, você poderá complementar o conteúdo de cada 
unidade através da leitura complementar e, por sua própria iniciativa, buscar nos 
jornais e revistas casos práticos que envolvam empresas, objeto da aplicação das 
teorias e modelos analisados nas aulas. 
 
Pesquisa Operacional I 
8 
 
Pesquisa Operacional I 
9 
Plano da Disciplina 
 
A disciplina tem como objetivo principal desenvolver, no estudante de 
engenharia,a capacidade de analisar qualquer problema de uma maneira simples 
e lógica e de aplicar, à sua solução, uns poucos e bem compreendidos princípios 
básicos. 
E ainda, compreender e entender fenômenos e funções da Pesquisa 
Operacional como uma ferramenta no auxilio das tomadas de decisões, suas 
ênfases, campo de atuação e responsabilidades, bem como sua interação com as 
outras ferramentas das engenharias e outros segmentos de trabalho. 
Para isso, a disciplina foi dividida em sete unidades para maior compreensão 
dos assuntos abordados. Com a finalidade de facilitar a compreensão segue uma 
síntese de cada unidade, ressaltando seus objetivos específicos para que você 
possa ter uma visão ampla do conteúdo que irá estudar. 
Unidade 1 – Programação Matemática 
Nesta unidade, faremos uma análise do contexto sócio histórico que propiciou 
o seu surgimento: O que é pesquisa operacional? A partir daí poderemos entender 
melhor o seu conceito e o seu objeto de estudo. 
Objetivos da unidade: 
Analisar a condição da pesquisa operacional como ferramenta na tomada de 
decisão e o uso da programação linear como solução. 
Unidade 2 – Programação Linear 
Nesta unidade, será apresentada uma forma de solução ou possíveis soluções 
de um P.P.L. usando o método gráfico e o método analítico. 
Objetivos da unidade: 
Mostrar ao leitor formas matemáticas para solucionar um P.P.L., usando 
métodos matemáticos simples. Como e quando aplicar essas soluções. 
Unidade 3 - O Método Simplex 
Nesta unidade, será apresentada a forma de solução ou possíveis soluções de 
um P.P.L. usando o método tabular Simplex. 
 
Pesquisa Operacional I 
10 
Objetivos da unidade: 
Mostrar ao leitor formas matemáticas para solucionar um P.P.L. usando 
métodos matemáticos tabulares simples. Como e quando aplicar essas soluções. 
Unidade 4 - Dualidade 
Nesta unidade, será apresentada forma de solução ou possíveis soluções de 
um P.P.L. usando a dualidade. 
Objetivos da unidade: 
Mostrar ao leitor que a quantidade de cálculo necessária para resolver um 
modelo linear pelo Simplex pode ser reduzida, substituindo o modelo chamado 
primal pelo modelo dual. 
Unidade 5 - Análise de Sensibilidade 
Nesta unidade, serão discutidos alterações no P.P.L., na função objetivo, nas 
restrições e nas variáveis de decisão e o impacto nas suas soluções. 
Objetivos da unidade: 
Mostrar ao leitor que os dados podem sofrer variações com o decorrer do 
tempo ou com a inclusão de novas informações que surgem com o progresso das 
tecnologias. 
Unidade 6 – O Problema de Transporte 
Nesta Unidade, aprenderemos de forma mais ampla algumas das 
aplicabilidades de um P.P.L. em problemas de transporte. 
Objetivos da unidade: 
Mostrar ao leitor o método tabular simplex na solução de problemas de 
transporte. Determinar a solução otimizada para o transporte de mercadorias entre 
as origens e os destinos. Apresentar a solução para problemas não balanceados. 
Unidade 7 – O Problema de Designação 
Nesta unidade, aprenderemos algumas das aplicabilidades de um P.P.L. em 
problemas de designação. 
Objetivos da unidade: 
Mostrar ao leitor o método tabular simplex na solução de problemas de 
designação. Determinar a solução otimizada para a designação a partir do método 
húngaro. 
Pesquisa Operacional I 
11 
Programação Matemática 1 
Pesquisa Operacional I 
 
12 
 
Nesta unidade, faremos uma análise do contexto sócio histórico que propiciou 
o seu surgimento: O que é pesquisa operacional? A partir daí poderemos entender 
melhor o seu conceito e o seu objeto de estudo. 
 
Objetivos da unidade: 
Analisar a condição da pesquisa operacional como ferramenta na tomada de 
decisão e o uso da programação linear como solução. 
 
Plano da unidade: 
 O que é a Pesquisa Operacional? 
 Problemas de otimização. Exemplos. 
 Programação Linear. 
 Formulação do problema 
 Convenção da solução 
 
Bons estudos! 
 
Pesquisa Operacional I 
 
13 
 
O que é a Pesquisa Operacional? 
 
A origem histórica da Pesquisa Operacional (PO) foi realizada por indivíduos 
como Charle Baggage. Sua pesquisa foi sobre o custo de transporte e triagem do 
correio para a "Penny Post" da Inglaterra universal em 1840, e estudos sobre o 
comportamento dinâmico de veículos ferroviários em defesa de bitola larga do 
GWR. Percy Bridgman trouxe a pesquisa operacional para dar suporte sobre 
problemas em física na década de 1920 e, mais tarde, tentar estender estes para as 
ciências sociais. 
A Pesquisa Operacional moderna teve origem na Estação de Pesquisa Bawdsey 
no Reino Unido em 1937 e foi o resultado de uma iniciativa do superintendente da 
estação, AP Rowe. Rowe concebeu a ideia como um meio para analisar e melhorar 
o funcionamento do sistema de radar de alerta, nos seus primórdios, no Reino 
Unido, Chain Home (CH). Inicialmente, ele analisou o funcionamento do 
equipamento de radar e de suas redes de comunicação, expandindo 
posteriormente para incluir o comportamento do pessoal de operação. Isto revelou 
limitações não reconhecidas da rede CH e permitiu medidas corretivas a tomar. 
O termo “pesquisa operacional” foi atribuído a algumas iniciativas militares na 
Segunda Guerra Mundial. Por conta do esforço requerido pela guerra na alocação de 
recursos escassos às várias operações militares e às atividades dentro de cada 
operação de uma maneira efetiva, várias seções de pesquisa operacional foram 
estabelecidas nas forças armadas britânicas. Logo depois, esses esforços similares 
foram empreendidos nos Estados Unidos. Muitos cientistas foram reunidos para 
aplicar uma abordagem científica a problemas estratégicos e táticos. Esses cientistas 
foram chamados a realizar “pesquisas operacionais militares”, daí vem o nome. 
Um passo natural tomado foi estender o sucesso da Pesquisa Operacional nos 
esforços de guerra para as organizações civis. A indústria pós-guerra havia crescido 
muito e se deparava com os problemas causados pela crescente complexidade das 
organizações. Vale lembrar que após a guerra houve inúmeros movimentos para a 
reconstrução dos países arrasados. Os problemas que apareceram durante a guerra 
e a complexidade das organizações na reconstrução dos países eram muito 
Pesquisa Operacional I 
 
14 
semelhantes, porém em um contexto diferente. Em 1948, o Massachusetts Institute 
of Tecnology (MIT) instituiu o primeiro programa formal de estudos em Pesquisa 
Operacional para campos não militares. A “idade de ouro” da PO vai de 1945 até 
meados da década de 1970, devida à rápida expansão. 
Dois fatores foram cruciais para o crescimento da PO naquele período: O 
primeiro foi o avanço na melhoria nas técnicas de PO e na formulação dos 
problemas - Ex. o método simplex para resolver problemas de programação linear. 
O segundo foi a popularização dos computadores. 
 
Problemas de otimização 
 
A construção de modelos. 
O desafio da PO é transformar um problema real de produção ou de processo 
em um modelo matemático que reproduza fielmente essa realidade; destacar as 
variáveis que se queira controlar - variáveis essas que estão sujeitas a restrições de 
ordem técnica; validar o modelo matemático e implementá-lo. Para facilitar nosso 
estudo vamos dividir esse problema em etapas: 
 Definição da situação-problema; 
 Formulação de um modelo quantitativo; 
 Resolução do modelo e encontro da melhor solução; 
 Consideração de fatores imponderáveis; 
 Implementação da solução. 
 
Agora vamos ver cada uma destas etapas. 
Definição da situação-problema 
Nessa fase os gerentes do projeto deverão discutir o problema de forma mais 
clara e coerente, definir o escopo do projeto, definir os objetivos a serem 
alcançados e quais são os possíveis caminhos a seguir. 
Pesquisa Operacional I 
 
15 
As limitações técnicas devem ser levantadas e as relações deste sistema com 
os demais da empresa ou do ambiente externo. Sejam micro clientes ou micro 
fornecedores internos da corporaçãoe stakeholders de outras organizações, com a 
finalidade de validar esse modelo. 
 
Formulação de um modelo quantitativo 
Em PO os modelos quantitativos são modelos matemáticos formados por um 
conjunto de equações e inequações. 
A eficiência do modelo é medida pela função objetivo, que pode ser de 
maximização ou de minimização. Por exemplo, maximizar o lucro ou minimizar o 
custo. Quanto melhor o valor obtido na função objetivo para cada solução 
proposta, melhor a eficiência do modelo: A solução ótima. 
 
Resolução do modelo e encontro da melhor solução 
Variáveis controladas ou de decisão: são aquelas cujo valor está sob o controle 
do administrador. Cabe a ele decidir um particular valor a cada uma dessas 
variáveis. Numa programação de produção uma possível variável a ser controlada 
pode ser a quantidade a ser produzida em um período de tempo, o que é 
competência do administrador. 
Variáveis não controladas: são aquelas cujos valores são arbitrados por 
sistemas fora do controle do administrador. Custos de produtos ou insumos, 
demanda de produtos, preços de mercado, são alguns exemplos desse tipo de 
variável. 
Podemos afirmar que um bom modelo é aquele que tem desempenho que 
mais chega próximo da realidade. O modelo deve ser rodado sempre, comparado 
com a realidade e revisado a fim de chegar o mais próximo possível dessa 
realidade. O modelo se torna mais fiel à realidade, incorporando características, 
com a adição de variáveis. 
 
 
Pesquisa Operacional I 
 
16 
Consideração de fatores imponderáveis 
Por outro lado, existem fatores que podem ser importantes, mas são difíceis de 
quantificar. O comportamento humano é um deles. A interação homem-máquina 
também. Faz-se necessário estimar o impacto desses fatores na solução que foi 
gerada pelo modelo matemático. Providências preliminares devem ser tomadas 
visando esses fatores. 
Implementação da solução 
Essa é a fase final. Deve ser apresentado ao administrador. A implantação deve 
ser acompanhada observando o comportamento do sistema com a solução 
adotada. Novos ajustes serão requeridos. É desejável que nessa fase do processo as 
pessoas que serão atingidas pelas mudanças estejam envolvidas. 
Figura 1.1 – Processo de solução de um problema de Pesquisa Operacional. 
 
Fonte: Adaptado de Moreira (2004 apud Moreira, 2010). 
Figura 1.1 – Processo de solução de um problema de Pesquisa Operacional. 
Pesquisa Operacional I 
 
17 
 
Programação Linear 
 
A programação linear é um dos mais populares modelos matemáticos 
estruturados utilizados para resolver problemas que apresentam variáveis que 
podem ser medidas e cujos relacionamentos podem ser expressos por meio de 
equações e/ou inequações lineares. As aplicações podem ser em vários campos das 
áreas científicas ou sociais, tais como administração da produção, análise de 
investimento, controle de estoque, economia, logística e etc. 
O modelo matemático de programações linear, que de agora em diante 
denominaremos de Problema de Programação Linear (PPL) é constituído de uma 
função objetivo linear; de restrições técnicas representadas por um grupo de 
equações e/ou inequações também lineares; e da restrição matemática de não 
negatividade (não pode ser negativa). 
Otimizar: 
),,,()( 21 nxxxfXf  – Função objetivo 
Sujeito a: 

















mnm
n
n
b
b
b
xxxg
xxxg
xxxg





2
1
21
212
211
),,,(
),,,(
),,,(
 
 
Onde: 
nnn xcxcxcxxxfXf   221121 ),,,()( 
),,1(
),,,( 33221121
mi
xaxaxaxaxxxg niniiini




 
 
Pesquisa Operacional I 
 
18 
 
n é o número de variáveis do problema 
m é o número de restrições do problema 
i é o índice de determinada restrição ),,1( mi  
j é o índice de determinada variável ),,1( nj  
jc é o coeficiente (constante) da variável jx , da função objetivo 
ija é o coeficiente (constante) na i-ésima restrição e da variável jx 
ib é constante da i-ésima restrição 
Um problema de programação linear está na sua forma padrão, quando o 
problema de otimização linear tiver as seguintes características: 
 A função objetivo deve ser minimizada ou maximizada; 
 As restrições do problema são definidas por um sistema de equações e/ou 
inequações lineares; 
 As condições de não negatividade de todas as variáveis de decisão 
complementam as restrições do problema. 
 
Matematicamente, podemos representar um problema na forma-padrão por: 
nnxcxcxcMaxZ  2211 
S.R. (Segundo as Restrições) 
11212111 bxaxaxa nn   
0,,, 21
2211
22222121







xx
bmxaxaxa
bxaxaxa
nmnmm
nn
 
 
Pesquisa Operacional I 
 
19 
Ou na forma reduzida: 
j
n
j j
xcMaxZ   1 
S.R. 
ij
n
j ij
bxa  1 ),,1( mipara  
0,,, 21 nxxx  
 
Agora iremos introduzir alguns termos: 
 Solução: qualquer valor obtido dentro do domínio da função objetivo, 
)(Xf , para as variáveis de decisão; 
 Solução viável: são soluções que satisfaçam todas as restrições; 
 Solução ótima: uma solução viável que tenha o melhor valor da função 
objetivo, )(Xf , isto é, que maximiza ou minimiza a função objetivo, 
podendo ser única ou múltipla; 
 Proporcionalidade: o valor da função objetivo é diretamente proporcional 
ao valor de cada variável de decisão. 
 
Formulação do Problema 
 
Não há uma regra fixa para a construção do modelo matemático. Mas a 
maioria dos problemas de programação linear (PPL) segue um roteiro que norteia o 
raciocínio. Veremos a seguir um roteiro básico em quatro etapas: 
1.Definir as variáveis de decisão ),,1( njxj  . Se estivermos estudando 
uma programação da produção, as variáveis de decisão podem representar as 
quantidades produzidas de produtos; se for uma programação de investimento, as 
variáveis representarão o tipo de portfólio escolhido. 
Pesquisa Operacional I 
 
20 
2.Definir a função objetivo da tomada de decisão. Que pode ser maximizar 
lucro, minimizar custos e etc. Ela é uma expressão formada por uma combinação 
linear das variáveis de decisão. 
3.Definir as restrições técnicas as quais estará sujeito. Como por exemplo, 
quantidade em estoque; homem-hora disponível na produção; 
4.A não negatividade. Sempre. 0,,, 21 nxxx  
Exemplo 1.1: 
Na fábrica de Brinquedos Eletrônicos X-Playhouse, são produzidos dois tipos 
de brinquedos: B1 e B2. O setor de contabilidade e custos informa que o lucro 
unitário do brinquedo B1 é de R$ 20,00 e do brinquedo B2 é de R$ 35,00. Na linha de 
produção o brinquedo B1 consome 2 horas e o brinquedo B2 consome 4 horas de 
trabalho. Essa linha de montagem tem 24 horas de trabalho disponíveis por dia. 
Sabe-se ainda que a demanda esperada pelo brinquedo B1 é de 8 unidades e de B2 
é de 4 unidades por dia. Como o engenheiro de produção da fábrica Brinquedos 
Eletrônicos X-Playhouse, monte o plano de produção de forma que o lucro seja 
maximizado. 
Solução: 
1. Comece definindo as variáveis de decisão, ou seja, as quantidades a 
serem produzidas de cada brinquedo. 
1x = quantidade de B1 a produzir; 
2x = quantidade de B2 a produzir; 
2. Formule a função objetivo que irá maximizar o lucro da empresa. 
O objetivo é maximizar o lucro, que pode ser calculado da seguinte 
forma: 
Lucro auferido com a venda de B1: 20 x 1x (lucro por unidade de B1 
vezes quantidade produzida de B1). 
 
Pesquisa Operacional I 
 
21 
Lucro auferido com a venda de B2: 35 x 2x (lucro por unidade de B2 x 
quantidade produzida de B2). 
Então o lucro total obtido será: 2121 3520);( xxxxL  
Objetivo: 2121 3520);( xxxxLMax  
 
3. Sujeito às restrições técnicas: 
4
8
2442
2
1
21



x
x
xx
 
4. A não negatividade. 
0, 21 xx 
 
Convenção da solução 
 
A solução de um problema de programação linear, P.P.L., pode ter uma única 
solução ótima ou pode ter infinitas soluções ótimas, como veremos nos próximos 
capítulos. 
A função objetivo pode ser de maximização, por exemplo,maximizar o lucro 
de uma empresa; como pode ser de minimização, minimizar custos. 
As restrições técnicas podem ser =,  ou : se um insumo será utilizado em 
sua totalidade, a restrição será de igualdade (=); se um insumo que está estocado, 
então, esta restrição será ( ), porque ele vai até a quantidade que está disponível 
no estoque; se há a necessidade desse insumo ser pelo menos, então, esta restrição 
será ( ). 
 
 
Pesquisa Operacional I 
 
22 
Estamos encerrando a unidade. Sempre que tiver uma dúvida entre em 
contato com seu tutor virtual através do ambiente virtual de aprendizagem e 
consulte sempre a biblioteca do seu polo. 
 
É hora de se avaliar 
Lembre-se de realizar as atividades desta unidade de estudo. Elas irão 
ajudá-lo a fixar o conteúdo, além de proporcionar sua autonomia no processo de 
ensino-aprendizagem. 
 
 
Pesquisa Operacional I 
 
23 
 
Exercícios – Unidade 1 
 
1) Sobre a origem da Pesquisa Operacional, é correto afirmar que: 
a) Sua origem histórica foi realizada por indivíduos como Charle Baggage. 
b) Baggage pesquisou o custo de transporte e triagem do correio. 
c) Percy Bridgman trouxe a pesquisa operacional para dar suporte sobre 
problemas em física na década de 1920. 
d) TODAS as alternativas acima estão CORRETAS. 
e) TODAS as alternativas acima estão INCORRETAS. 
 
2) Considere as seguintes afirmações sobre a Pesquisa Operacional na era 
moderna: 
I- O termo “pesquisa operacional” foi atribuído a algumas iniciativas militares 
na Segunda Guerra Mundial. 
II- Até hoje a Pesquisa Operacional é utilizada apenas nas pesquisas militares. 
III- Dois fatores foram fundamentais para o crescimento da Pesquisa 
Operacional: o primeiro foi o avanço na melhoria nas técnicas de PO e na 
formulação dos, e o segundo foi a popularização dos computadores. 
 
São corretas as afirmações: 
a) I, apenas. 
b) I e II, apenas. 
c) I e III, apenas. 
d) TODAS as afirmações estão CORRETAS. 
e) TODAS as afirmações estão INCORRETAS. 
Pesquisa Operacional I 
 
24 
3) São etapas para a resolução de problemas de Pesquisa Operacional, 
EXCETO: 
a) Definição da situação-problema. 
b) Formulação de um modelo qualitativo. 
c) Formulação de um modelo quantitativo. 
d) Implementação da solução. 
e) Consideração de fatores imponderáveis. 
 
4) Sobre as etapas para a resolução de problemas de Pesquisa Operacional 
(PO), é INCORRETO afirmar que: 
a) Em PO os modelos quantitativos são modelos matemáticos formados por 
um conjunto composto tanto por equações, quanto por inequações. 
b) A eficiência do modelo é medida pela função objetivo, que pode ser de 
maximização ou de minimização. 
c) As variáveis controladas ou de decisão são aquelas cujo valor está sob o 
controle do administrador. 
d) Numa programação de produção uma possível variável a ser controlada 
pode ser a quantidade a ser produzida em um período de tempo. 
e) Custos de produtos ou insumos, demanda de produtos, preços de mercado, 
são alguns exemplos de variáveis controladas. 
 
5) Sobre a Programação Linear, é correto afirmar que: 
a) A função objetivo deve ser minimizada ou maximizada. 
b) A solução viável é aquela que maximiza ou minimiza a função objetivo. 
c) Uma solução ótima não precisa ser uma solução viável. 
d) TODAS as alternativas acima estão CORRETAS. 
e) TODAS as alternativas acima estão INCORRETAS. 
Pesquisa Operacional I 
 
25 
 
6) Certa fabrica produz dois produtos P1 e P2. O lucro unitário do produto P1 é 
de R$ 100,00, enquanto o lucro do produto P2 é de R$ 180,00. A empresa precisa de 
20 horas para fabricar uma unidade de P1 e de 30 horas para fabricar uma unidade 
de P2. O tempo de produção disponível para isso é de 1.200 horas. A demanda 
esperada para cada produto é de 40 unidades para P1 e 30 unidades para P2. Qual é 
o plano de produção para que a empresa maximize o seu lucro nesses itens? 
Considere: 
1x = quantidade de P1 a produzir; 2x = quantidade de P2 a produzir; 
a) 2121 180100);( xxxxLMax  
Restrições técnicas 
30
40
200.13020
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
b) 2121 180100);( xxxxLMax  
Restrições técnicas 
60
50
200.13020
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
c) 2121 3020);( xxxxLMax  
Restrições técnicas 
30
40
200.1180100
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
d) 2121 180100);( xxxxLMax  
Pesquisa Operacional I 
 
26 
 
Restrições técnicas 
30
40
200.13020
2
1
21



x
x
xx
 
e) 2121 180100);( xxxxLMax  
Restrições de não negatividade 0, 21 xx 
 
7) Um vendedor de legumes pode transportar 800 caixas de legumes para sua 
região de vendas. Ele necessita transportar 200 caixas de cenouras a R$ 20,00 de 
lucro por caixa, pelo menos 100 caixas de batata a R$ 10,00 de lucro por caixa, e no 
máximo 200 caixas de mandioca a R$ 30,00 por caixa. De que forma deverá ele 
carregar o caminhão para obter o lucro máximo? Considere: 
1x = quantidade de caixas de batata; 2x = quantidade de caixas de mandioca; 
a) 40003010);( 2121  xxxxLMax 
Restrições técnicas 
200
100
600
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
b) 40003010);( 2121  xxxxLMax 
Restrições técnicas 
200
100
600
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
c) 4000200100);( 2121  xxxxLMax 
Pesquisa Operacional I 
 
27 
Restrições técnicas 
30
10
600
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
d) 2121 3010);( xxxxLMax  
Restrições técnicas 
200
100
800
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
e) 40003010);( 2121  xxxxLMax 
Restrições técnicas 
200
100
800
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
 
8) Na fabricação de dois de seus produtos, uma empresa utiliza dois 
equipamentos que limitam a produção. Em um dado período de tempo, estão 
disponíveis 30 horas do equipamento 1 e 60 horas do equipamento 2. Para a 
fabricação de uma unidade do produto A, usa-se 1 hora do equipamento 1 e 2 
horas do equipamento 2. Já para uma unidade do produto B, são gastas 2 horas do 
equipamento 2. O equipamento 1 não toma parte na produção do produto B. Por 
outro lado, uma unidade do produto A leva a um lucro de R$120,00, enquanto cada 
unidade do produto B gera um lucro de R$ 52,00. Formule o modelo de 
programação linear para maximizar o lucro da empresa. Considere: 
1x = quantidade do produto A; 2x = quantidade do produto B; 
 
Pesquisa Operacional I 
 
28 
a) 2121 3060);( xxxxLMax  
Restrições técnicas 
30
12022
1
21


x
xx
 
Restrições de não negatividade 0, 21 xx 
b) 2121 52120);( xxxxLMax  
Restrições técnica s 
60
60
2
21


x
xx
 
Restrições de não negatividade 0, 21 xx 
c) 2121 3060);( xxxxLMax  
Restrições técnicas 
30
60
1
21


x
xx
 
Restrições de não negatividade 0, 21 xx 
d) 2121 52120);( xxxxLMax  
Restrições técnicas 
30
6022
1
21


x
xx
 
Restrições de não negatividade 0, 21 xx 
e) 2121 52120);( xxxxLMax  
Restrições técnicas 
30
12022
1
21


x
xx
 
Restrições de não negatividade 0, 21 xx 
 
 
Pesquisa Operacional I 
 
29 
9) Uma alfaiataria está considerando quanto deve produzir de seus dois 
modelos de terno, denominados de Executivo e Despojado, de forma a maximizar 
o lucro. Será impossível fabricar quanto se queira de cada um dos modelos, porque 
existem limitações nas horas disponíveis para a operação de costura e a operação 
de acabamento, as duas operações são básicas na fabricação. No caso da costura, 
existem 160 horas-máquinas disponíveis, enquanto para o acabamento, que é feito 
manualmente, haverá, no máximo, 220 homens-horas. Em termos de lucro unitário 
e produção, osdois modelos apresentam as seguintes características: 
a. Executivo: 
I. Lucro unitário: R$ 105,00 
II. Horas-máquina de costura por unidade: 2 
III. Homens-hora de acabamento por unidade: 1 
 
b. Despojado: 
I. Lucro unitário: R$ 70,00 
II. Horas-máquina de costura por unidade: 1 
III. Homens-hora de acabamento por unidade: 4 
 
Formule o modelo de programação linear para maximizar o lucro da 
alfaiataria. Considere: 
1x = quantidade do terno Executivo; 2x = quantidade do terno Despojado; 
 
Pesquisa Operacional I 
 
30 
10) Uma rádio FM local tem o seguinte problema: foi descoberto que o 
programa de sertanejo com 20 minutos de música e 1 minuto de propaganda 
chama a atenção de 30.000 ouvintes, enquanto o programa de MPB, com 10 
minutos de musica e 1 minuto de propaganda chama a atenção de 10.000 
ouvintes. No decorrer de uma semana, o patrocinador insiste no uso mínimo, 5 
minutos pra sua propaganda e que não há verba para mais de 80 minutos de 
música. Quantas vezes por semana cada programa deve ser levado ao ar para obter 
o número máximo de telespectadores: Construa o modelo do PPL. 
 
 
Pesquisa Operacional I 
 
31 
 
2Programação Linear 
Pesquisa Operacional I 
 
32 
 
Nesta unidade, será apresentada uma forma de solução ou possíveis soluções 
de um P.P.L. usando o método gráfico e o método analítico. 
 
Objetivos da unidade: 
Mostrar ao leitor formas matemáticas para solucionar um P.P.L., usando 
métodos matemáticos simples. Como e quando aplicar essas soluções. 
 
Plano da unidade: 
 Introdução. Formas padrão e normal 
 Exemplos de aplicação 
 Definição geral de programação linear. Conjunto convexo 
 Solução gráfica de um PPL 
 
Bons estudos! 
 
Pesquisa Operacional I 
 
33 
 
Introdução. Formas padrão e normal 
 
Como já foi introduzido na unidade 1, dizemos que um P.P.L. está em sua 
forma padrão se for proposto nela uma maximização da função objetiva e se todas 
as restrições forem do tipo menor ou igual, bem como se os termos constantes ( ib ) 
e as variáveis de decisão assumirem valores não negativos. 
Matematicamente, podemos representar um P.P.L. na forma padrão assim: 
nnxcxcxcMaxZ  2211 
S.R. 
11212111 bxaxaxa nn   
0,,, 21
2211
22222121







xx
bmxaxaxa
bxaxaxa
nmnmm
nn
 
 
Ou na forma reduzida: 
j
n
j j
xcMaxZ   1 
S.R. 
ij
n
j ij
bxa  1 ),,1( mipara  
0,,, 21 nxxx  
 
 
Pesquisa Operacional I 
 
34 
Quando resolvemos o modelo matemático na forma padrão, chegamos à 
solução. Que pode ser definhada assim: 
 Solução: quaisquer valores dentro do domínio da função objetivo, 
)(Xf , para as variáveis de decisão, independentemente de se tratar de 
uma escolha desejável ou permissível. 
 Solução viável: uma solução é dita viável quando todas as restrições são 
satisfeitas. 
 Solução ótima: é a solução viável que tem o valor mais favorável da 
função objetivo, )(Xf , isto é, maximiza ou minimiza a função objetivo, 
podendo ser única ou múltipla, como veremos adiante. 
 
Exemplos de aplicação 
 
A programação linear pode ser empregada de várias formas em vários setores 
e campos da ciência, por exemplo: 
 Administração da produção; 
 Análise de investimento; 
 Alocação de recursos limitados; 
 Planejamento regional e urbano; 
 Logística; 
 Custo de transporte; 
 Localização da rede de distribuição; 
 Alocação de recursos energéticos. 
 
Pesquisa Operacional I 
 
35 
 
Definição geral de programação linear. Conjunto convexo 
 
A definição geral já foi ministrada na unidade um, que repito agora para 
relembrar. 
Otimizar: ),,,()( 21 nxxxfXf  – Função objetivo 
Sujeito a: 

















mnm
n
n
b
b
b
xxxg
xxxg
xxxg





2
1
21
212
211
),,,(
),,,(
),,,(
 
Onde: 
nnn xcxcxcxxxfXf   221121 ),,,()( 
),,1(
),,,( 33221121
mi
xaxaxaxaxxxg niniiini




 
n é o número de variáveis do problema 
m é o número de restrições do problema 
i é o índice de determinada restrição ),,1( mi  
j é o índice de determinada variável ),,1( nj  
jc é o coeficiente (constante) da variável jx , da função objetivo 
ija é o coeficiente (constante) na i-ésima restrição e da variável jx 
ib é constante da i-ésima restrição 
 
 
Pesquisa Operacional I 
 
36 
Agora vamos apresentar alguns teoremas a respeito das soluções de um P.P.L. 
Porém, antes vamos definir o que representa um conjunto convexo. Vamos fazê-lo 
de forma intuitiva. Um conjunto convexo é um conjunto de pontos em que todos 
os segmentos de reta que unem dois de seus pontos que são internos ao conjunto, 
isto é, todos os pontos de cada segmento também pertencem ao conjunto original. 
Graficamente, um exemplo de conjunto convexo e não convexo é representado na 
figura abaixo. 
 
 
 
Solução gráfica de um PPL 
 
Em problemas de programação linear que envolvam 02 (duas) variáveis de 
decisão, a solução que pode ser viável e/ou ótima, pode ser encontrada 
graficamente. 
Vamos considerar o P.P.L. abaixo: 
2121 95);( xxxxLMax  
Sujeito a 
)(3
)(4
)(1642
2
1
21
IIIx
IIx
Ixx



 
0, 21 xx 
 
Pesquisa Operacional I 
 
37 
A solução óbvia para );( 21 xxL se dá em 01 x e 02 x , então 
substituindo na função objetivo, )0;0(L = 0 – Solução óbvia. 
Usaremos o par de eixos cartesianos para representar as quantidades 1x e 2x . 
Agora vamos traçar as retas que representam as restrições técnicas de função 
constantes (II) e (III), figura abaixo: 
 
A restrição (I) é dada pela inequação 1642 21  xx que iremos 
representar no gráfico por uma reta. Como vamos trabalhar em R2, convém 
representar a inequação acima na sua forma canônica, que mostraremos a seguir: 
2
4
4
216
2164
1642
1
2
1
2
12
21
x
x
x
x
xx
xx





 
Pesquisa Operacional I 
 
38 
Graficamente, podemos representar o conjunto ou região de soluções viáveis 
por meio da figura abaixo. Todas as possíveis soluções de 1x e 2x estão presentes 
na região destacada do gráfico. 
 
 
Para encontrarmos o valor que melhor atende nosso P.P.L. proposto, vamos 
usar o processo de tentativa e erro. Podendo chegar ao valor ótimo verificando a 
existência de pontos da reta que fazem parte do conjunto de soluções viáveis. 
Traçamos a reta da função objetivo no ponto da solução óbvia (ponto A(0;0)) e a 
partir dela traçamos as paralelas a essa, passando pelos pontos críticos da região de 
solução viável até o ponto extremo (é o ponto ótimo, que maximiza ou minimiza a 
função objetivo, que nesse caso é o ponto C(4;2)), pois estamos maximizando a 
função objetivo (devemos observar todas as “quinas” da região que contém as 
soluções viáveis, que chamamos de “pontos críticos” até encontrar o ponto que 
maximiza a função objetivo, que chamamos de ponto extremo). No ponto extremo, 
será dado o valor máximo da função objetivo L. Que no exemplo usado L = 38. Esse 
processo está mostrado na figura abaixo: 
Pesquisa Operacional I 
 
39 
 
 
Estamos encerrando a unidade. Sempre que tiver uma dúvida entre em 
contato com seu tutor virtual através do ambiente virtual de aprendizagem e 
consulte sempre a biblioteca do seu polo. 
 
É hora de se avaliar 
Lembre-se de realizar as atividades desta unidade de estudo. Elas irão 
ajudá-lo a fixar o conteúdo, além de proporcionar sua autonomia no processo de 
ensino-aprendizagem. 
 
Pesquisa Operacional I 
 
40 
 
Exercícios – Unidade 2 
 
1) São campos de aplicações da programação linear, EXCETO: 
a) Análise de investimento. 
b) Logística. 
c) Custo de transporte. 
d) Redes envolvendo arcos. 
e) Alocação de recursos energéticos. 
Considere o seguinte enunciado para as questões 2, 3 e 4: 
2121 32);( xxxxLimizarMax  
Sujeito a 
62
42
21
21


xx
xx
 
0, 21 xx 
2) Marque a alternativa que representa corretamente cada uma das restrições 
(inequações)na forma canônica (isto é, isolando 2x ): 
a) 
2
2 12
x
x  e 
2
4 12
x
x  
b) 
2
4 12
x
x  e 
2
2 12
x
x  
c) 
2
2 12
x
x  e 
2
3 12
x
x  
d) 
2
4 12
x
x  e 
2
4 12
x
x  
e) 42 x e 32 x 
Pesquisa Operacional I 
 
41 
3) Assinale a alternativa que apresente a solução óbvia e os pontos críticos. 
Dica: Esboce os gráficos das inequações na forma canônica da questão 2. 
a) (0;0), (6;0), (1;5/2) e (0;2). 
b) (0;0), (3;0) e (0;3). 
c) (0;0), (6;0) e (0;2) 
d) (3;0) e (0;2) 
e) (6;0) e (0;3) 
 
4) Marque a alternativa que maximiza a função objetivo L, e os respectivos 
valores de 1x e 2x , que compõe o ponto extremo. 
a) 01 x ; 02 x e Lucro = 12 
b) 11 x ; 52 x e Lucro = 17 
c) 01 x ; 22 x e Lucro = 10 
d) 11 x ; 2/52 x e Lucro = 13 
e) 61 x ; 02 x e Lucro = 12 
 
Considere o seguinte enunciado para as questões 5, 6 e 7: 
2121 5,03,0);( xxxxLimizarMax  
Sujeito a 
33
22
21
21


xx
xx
 
0, 21 xx 
 
 
Pesquisa Operacional I 
 
42 
5) Marque a alternativa que representa corretamente cada uma das restrições 
(inequações) na forma canônica (isto é, isolando 2x ): 
a) 12 1 xx  e 2
2 12
x
x  
b) 12 22 xx  e 3
1 12
x
x  
c) 12 22 xx  e 3
2 12
x
x  
d) 
2
1 12
x
x  e 
3
1 12
x
x  
e) 
3
3 12
x
x  e 
2
2 12
x
x  
 
6) Assinale a alternativa que apresente a solução óbvia e os pontos críticos. 
Dica: Esboce os gráficos das inequações na forma canônica da questão 5. 
a) (0;0), (1;0) e (0;1). 
b) (0;0), (1;0), (0,7;0,7) e (0,5;1). 
c) (0;0), (1;0), (0,6;0,8) e (0;1). 
d) (1;0) e (0;1). 
e) (0,7;0) e (0,7;0). 
 
7) Marque a alternativa que maximiza a função objetivo L, e os respectivos 
valores de 1x e 2x , que compõe o ponto extremo. 
a) 01 x ; 12 x e Lucro = 0,5 
b) 11 x ; 02 x e Lucro = 0,3 
c) 01 x ; 02 x e Lucro = 2 
Pesquisa Operacional I 
 
43 
d) 6,01 x ; 8,02 x e Lucro = 0,58 
e) 7,01 x ; 7,02 x e Lucro = 0,65 
 
8) Considere o seguinte enunciado: 
2121 32);( xxxxLimizarMax  
Sujeito a 
6
42
93
21
21
21



xx
xx
xx
 
0, 21 xx 
 
Marque a alternativa que maximiza a função objetivo L, e os respectivos 
valores de 1x e 2x , que compõe o ponto extremo. 
a) 01 x ; 12 x e Lucro = 3 
b) 01 x ; 62 x e Lucro = 18 
c) 61 x ; 02 x e Lucro = 12 
d) 5,41 x ; 5,12 x e Lucro = 13,5 
e) 51 x ; 22 x e Lucro = 16 
 
Pesquisa Operacional I 
 
44 
 
9) Considere o seguinte enunciado: 
2121 1210);( xxxxCMinimizar  
Sujeito a 
10
202
21
21


xx
xx
 
 0, 21 xx 
Encontre os pontos críticos. 
 
 
 
 
 
 
10) Considere a questão anterior: encontre o valor que minimiza a função 
objetivo de custos C, e os respectivos valores de 1x e 2x , que compõe o ponto 
extremo. 
 
 
Pesquisa Operacional I 
 
45 
 
3O Método Simplex 
Pesquisa Operacional I 
 
46 
 
Nesta unidade, será apresentada forma de solução ou possíveis soluções de 
um P.P.L. usando o método tabular Simplex. 
 
Objetivos da unidade: 
Mostrar ao leitor formas matemáticas para solucionar um P.P.L. usando 
métodos matemáticos tabulares simples. Como e quando aplicar essas soluções. 
 
Plano da unidade: 
 Desenvolvimento do Método Simplex 
 Resumo de procedimentos de solução do Método Simplex 
 Técnica de variáveis artificiais 
 Variação das aplicações do Método Simplex 
 
 
Bons estudos! 
 
 
Pesquisa Operacional I 
 
47 
 
Desenvolvimento do Método Simplex 
 
O método gráfico para a solução de um P.P.L., que aprendemos na Unidade 
anterior, só pode ser empregado quando existir duas ou, no máximo, três variáveis 
(neste caso de difícil visualização). Quando tiver três ou mais variáveis é 
aconselhável usar a solução tabular chamada de método Simplex. 
Utilizando esse método é possível incrementar as variáveis básicas trocando 
pelas varáveis não básicas até chegar à solução teste de otimalidade. Ou seja, as 
soluções básicas por não básicas, gerando novas soluções. 
Os critérios de escolha de vetores e consequentemente das variáveis que 
entram e saem para a formação da nova base constituem o centro do Simplex. 
Vamos tomar o modelo que apresenta uma solução básica inicial. 
Suponhamos que a função objetivo seja de maximização, que os modelos possuam 
restrições  (menor ou igual) e os termos da direita sejam não negativos 
(positivos ou iguais a zero), então existe uma solução básica formada pelas 
variáveis de folga. 
Exemplo: 
2121 53);( xxxxLimizarMax  
Sujeito a 
30
206
1042
21
21
21



xx
xx
xx
 
 0, 21 xx 
Primeiro vamos transformar o sistema de inequações em um sistema de 
equações com variáveis não negativas. Para isso, introduziremos em cada uma das 
inequações as variáveis F1, F2 e F3, que representam as folgas das inequações 1, 2 e 
3, isto é, a diferença entre o segundo e o primeiro membro dessas inequações. 
Isso tem como resultado o sistema de equações com variáveis não negativas: 
Pesquisa Operacional I 
 
48 
30
206
1042
321
221
121



Fxx
Fxx
Fxx
 
0,,,, 32121 FFFxx 
1º Passo: Teste de otimalidade para a solução. 
Este teste consiste em avaliar o efeito da permuta da uma variável básica por 
outra não básica, com a consequente formação de uma nova solução. Se a entrada 
de uma variável não básica puder melhorar o desempenho do sistema, a solução 
testada não é ótima. 
Essa avaliação é possível quando a função objetivo está escrita somente em 
termos das variáveis não básicas. 
Voltemos ao exemplo, a função objetivo está escrita na forma: 
2121 53);( xxxxLMax  
Fazendo 0,0 21  xx , uma solução básica inicial formada pelas variáveis 
de folga F1=10, F2=20 e F3=30. 
Neste caso, as variáveis básicas são F1, F2 e F3 e as variáveis não básicas 1x e 2x 
Portanto, a função objetivo está escrita com as variáveis não básicas. 
Examinando a função objetivo e a solução inicial 0,0 21  xx e L = 0, com 
2121 53);( xxxxL  , temos: 
Se 1x entra na base com valor 1, o valor de L passa de L=0 para L=3, 
aumentando 3 unidades, exatamente o valor do coeficiente de 1x . 
Se 2x entra na base com valor 1, o valor de L passa de L=0 para L=5, 
aumentando 5 unidades, exatamente o valor do coeficiente de 2x . 
Por outro lado, se o coeficiente 1x ou 2x fosse negativo, a entrada dessa 
variável diminuiria o valor de L, de acordo com seu coeficiente. Podemos concluir 
Pesquisa Operacional I 
 
49 
que enquanto a função objetivo apresentar variáveis não básicas com coeficientes 
positivos, ela poderá ser aumentada, não sendo, portanto a solução ótima. 
Vamos reescrever agora, a função objetivo com todas as variáveis à esquerda: 
2121 53);( xxxxL  
053 21  xxL 
Os coeficientes positivos à direita se tornam negativos quando passamos para 
a esquerda, portanto, coeficientes à esquerda indicam que o valor de L pode ser 
aumentado com a entrada da variável na base, e na proporção de seu coeficiente. 
Escrito dessa forma, a solução testada só será ótima quando as variáveis não 
básicas apresentam somente coeficientes positivos. 
2º Passo: Cálculo da nova solução básica. 
a) Variável que entra na base: entra na base a variável com coeficiente 
negativo de maior valor absoluto. A ideia é incrementar o valor de L. 
Examinando a função objetivo do exemplo: 
053 21  xxL ou 2121 53);( xxxxL  
Entra a variável 2x , pois cada unidade a mais de 2x aumenta L em 5 
unidades. 
b) Variável que sai: sai a variável que primeiro se anula com a entrada da 
variável escolhida no item anterior, no caso 2x , que entra com maior valor 
possível. 
Ela pode ser descoberta dividindo-se os termos da direita das restrições pelos 
coeficientes positivos da variável que entra. O menor valor indica que a variável 
básica dessa linha é a que primeiro se anula e sairá da base. 
No nosso exemplo: 
 
30
206
1042
321
221
121



Fxx
FxxFxx
 
Entra 
10/4=2,5 → Sai a variável dessa linha (F1) 
20/1=20 
30/(-1) = - 30 
Pesquisa Operacional I 
 
50 
A última divisão (30/(-1)) não pode ser considerada, pois daria valor negativo 
para a variável na próxima base, o que não é possível. Portanto, sai a variável da 
primeira linha, no caso F1. 
c) Elemento pivô: 
A coluna da variável que entra e a linha da variável que sai identificam um 
elemento comum chamado pivô. 
A linha variável que sai é também linha pivô. No caso, a primeira linha é a pivô 
e o coeficiente 4 de 2x é o elemento pivô. 
d) Calculando a nova solução: 
Vamos organizar a função objetivo e restrições em uma tabela com colunas 
formadas pelos coeficientes de cada variável e outra dos termos independentes. 
 L X1 X2 F1 F2 F3 b 
Tabela 1 1 -3 -5 0 0 0 0 
L1 F1 0 2 4 1 0 0 10 
L2 F2 0 6 1 0 1 0 20 
L3 F3 0 1 -1 0 0 1 30 
 
 L X1 X2 F1 F2 F3 b 
Tabela 1 1 -3 -5 0 0 0 0 
L1 F1 0 2 4 1 0 0 10 Sai (Linha pivô) 
L2 F2 0 6 1 0 1 0 20 
L3 F3 0 1 -1 0 0 1 30 
 Entra na base 
 
Dividimos a linha pivô pelo valor do elemento pivô, que em nosso exemplo 
tem valor 4,obtendo uma nova linha com o pivô unitário. 
Linha pivô 0 2 4 1 0 0 10 
Dividido por 4 0 0,5 1 0,25 0 0 2,5 Nova linha pivô 
 
Vamos reescrever cada uma das outras linhas da seguinte maneira: 
1º Multiplicar os elementos da nova linha pivô pelo coeficiente da variável que 
entra da outra linha, com sinal trocado. 
Pesquisa Operacional I 
 
51 
2º Somar termo a termo com os elementos da outra linha. 
Voltando ao exemplo: Coeficiente da variável que entra (X2) na primeira linha é -5. 
Então: 
Nova linha pivô 0 0,5 1 0,25 0 0 2,5 
Multiplicar por 5 0 2,5 5 1,25 0 0 12,5 
 (+) 
linha da função objetivo 1 -3 -5 0 0 0 0 
Nova linha da função objetivo 1 -0,5 0 1,25 0 0 12,5 
 
Coeficiente da variável que entra (X2) na linha 2 é 1. Então: 
Nova linha pivô 0 0,5 1 0,25 0 0 2,5 
Multiplicar por (-1) 0 -0,5 -1 -0,25 0 0 -2,5 
 (+) 
linha 2 0 6 1 0 1 0 20 
Nova linha 2 0 5,5 0 -0,25 1 0 17,5 
Coeficiente da variável que entra (X2) na linha 3 é -1. 
Nova linha pivô 0 0,5 1 0,25 0 0 2,5 
Multiplicar por (1) 0 0,5 1 0,25 0 0 2,5 
 (+) 
linha 3 0 1 -1 0 0 1 30 
Nova linha 3 0 1,5 0 0,25 0 1 32,5 
Reescrevendo a nova tabela com os resultados obtidos teremos: 
 L X1 X2 F1 F2 F3 b 
Tabela 2 1 -0,5 0 1,25 0 0 12,5 
L1 X2 0 0,5 1 0,25 0 0 2,5 
L2 F2 0 5,5 0 -0,25 1 0 17,5 
L3 F3 0 1,5 0 0,25 0 1 32,5 
De onde concluímos a nova solução: 
Variáveis Não básicas: X1 = 0 e F1 = 0 (termos presentes na primeira linha); 
Variáveis básicas: X2 = 2,5, F2 = 17,5 e F3 = 32,5 (obtido das demais linhas, 
fazendo X1 = 0 e F1 = 0) e 
Valor de L: L = 12,5 (obtido da primeira linha fazendo X1 = 0 e F1 = 0) 
A função objetivo na nova solução está escrita em termos das variáveis não 
básicas X1 e F1. As variáveis básicas têm coeficientes nulos. 
A solução obtida tem L = 12,5, contra um L = 0 da solução inicial. É melhor, 
mas não é ótima, pois o coeficiente de X1 na nova função objetivo é negativo. 
Pesquisa Operacional I 
 
52 
Cálculo da nova solução: 
 L X1 X2 F1 F2 F3 b b/X1 
Tabela 2 1 -0,5 0 1,25 0 0 12,5 
L1 X2 0 0,5 1 0,25 0 0 2,5 5,0 
L2 F2 0 5,5 0 -0,25 1 0 17,5 3,18 Sai 
L3 F3 0 1,5 0 0,25 0 1 32,5 21,67 
 Entra 
Variável que entra na base: X1 (coeficiente negativo de maior valor absoluto 
na nova função – tabela 2). 
Variável que sai: vamos dividir os termos independentes (constantes, isto é, b) 
pelos coeficientes positivos de X1 (o resultado já aparece na última coluna da 
tabela anterior): 
2,5/0,5 = 5 
17,5/5,5 = 3,18 menor valor: sai a variável dessa linha, no caso F2 
Nova linha pivô – L 
Elemento pivô: 5,5 
Nona linha pivô = linha pivô dividido por 5,5. 
Nova linha pivô 0 5,5 0 -0,25 1 0 17,5 
Dividido por 5,5 0 1 0 -0,045 0,18 0 3,18 
 
O coeficiente da variável que entra (X1) na nova linha é -0,5. Então: 
Nova linha pivô 0 1 0 -0,045 0,18 0 3,18 
Multiplicar por 0,5 0 0,5 0 -0,02 0,091 0 1,59 
 (+) 
linha da função objetivo 1 -0,5 0 1,25 0 0 12,5 
Nova linha da função objetivo 1 0 0 1,227 0,09 0 14,09 
 
O coeficiente da variável que entra (X1) na nova linha L1 é 0,5. Então: 
Nova linha pivô 0 1 0 -0,045 0,18 0 3,18 
Multiplicar por -0,5 0 -0,5 0 0,0227 -0,09 0 -1,59 
 (+) 
Linha 1 0 0,5 1 0,25 0 0 2,5 
Nova linha 1 0 0 1 0,273 -0,09 0 0,91 
 
Pesquisa Operacional I 
 
53 
O coeficiente da variável que entra (X1) na nova linha L3 é 1,5. Então: 
Nova linha pivô 0 1 0 -0,045 0,18 0 3,18 
Multiplicar por -1,5 0 -1,5 0 0,068 -0,27 0 -4,77 
 (+) 
linha 3 0 1,5 0 0,25 0 1 32,5 
Nova linha 3 0 0 0 0,318 -0,27 1 27,73 
 
Reescrevendo a nova tabela com os resultados obtidos teremos: 
 L X1 X2 F1 F2 F3 b 
Tabela 3 1 0 0 1,227 0,09 0 14,09 
L1 X2 0 0 1 0,273 -0,09 0 0,91 
L2 X1 0 1 0 -0,045 0,18 0 3,18 
L3 F3 0 0 0 0,318 -0,27 1 27,73 
A nova solução será, portanto: 
Variáveis Não básicas: F1 = 0 e F2 = 0; 
Variáveis básicas: X1 =3,18; X2 = 0,91 e F3 = 27,73 e 
Valor de L: L = 14,09 
A função objetivo está escrita em termos das variáveis não básicas F1 e F2, pois 
os coeficientes das variáveis básicas são nulos. O valor de L passou de L = 12,5 para 
L = 14,09. Essa solução é ótima, pois os coeficientes das variáveis não básicas na 
função objetivo são positivos. Se F1 ou F2 entrar na base, o valor de L diminui, 
contrariando o objetivo. Além disso, temos os valores de X1 =3,18 e X2 = 0,91. 
 
Pesquisa Operacional I 
 
54 
 
Resumo de procedimentos de solução do Método Simplex 
 
Este tópico será apresentado através de um exemplo, como segue abaixo: 
321321 32);;( xxxxxxZimizarMax  
Sujeito a 
3023
202
40
321
321
321



xxx
xxx
xxx
 
 0,, 321 xxx 
Note que agora nosso sistema tem três variáveis. 
a. Vamos agora colocar as variáveis de folga e as variáveis de função objetivo à 
esquerda e transformar as inequações em equações, introduzindo as variáveis 
de folga. 
032 321  xxxZimizarMax 
Sujeito a 
3023
202
40
3321
2321
1321



Fxxx
Fxxx
Fxxx
 
0,,,,, 321321 FFFxxx 
Montamos o quadro agora: 
 Z X1 X2 X3 F1 F2 F3 b b/X2 
Tabela 1 1 -2 -3 -1 0 0 0 0 
L1 F1 0 1 1 1 1 0 0 40 40 
L2 F2 0 2 1 -1 0 1 0 20 20 
L3 F3 0 3 2 -1 0 0 1 30 15 Sai 
 Entra 
 
Pesquisa Operacional I 
 
55 
b. Solução básica inicial: 
Variáveis Não básicas: X1 = 0; X2 = 0 e X3 = 0 
Variáveis básicas: F1 =40; F2 = 20 e F3 = 30 
Valor de Z: Z = 0 
c. Teste da solução: A solução não é ótima, pois tem coeficientes negativos na 
função objetivo. 
d. Cálculo da nova solução: 
 Variável que entra: X2 (coeficiente negativo da função objetivo de maior valor 
absoluto) 
 Variável que sai (termos independentes b divididos pelos coeficientes de X2 – 
variável que entra na base): 
 
Da coluna b/X2, 
40/1 = 40; 20/1 = 20 e 30/2 = 15 
Sai o de menor valor: 15 Sai a variável da linha 3 (F3) 
Linha pivô: linha 3 
Elemento pivô: 2 
 Dividindo a linha pivô por 2, temos: 
Nova linha pivô: 
Linha pivô 0 3 2 -1 0 0 1 30 
Dividido por 2 0 1,5 1 -0,5 0 0 0,5 15 
 
Cálculo da nova linha de Z (coeficiente da variável que entra = -3) 
Nova linha pivô 0 1,5 1 -0,5 0 0 0,5 15 
X (3) 0 4,5 3 -1,5 0 0 1,5 45 (+) 
linha Z 1 -2 -3 -1 0 0 0 0 
Nova linha Z 1 2,5 0 -2,5 0 0 1,5 45 
 
Pesquisa Operacional I 
 
56 
Cálculo da nova linha L1 (coeficiente da variável que entra = 1) 
Nova linha pivô 0 1,5 1 -0,5 0 0 0,5 15 
X (-1) 0 -1,5 -1 0,5 0 0 -0,5 -15 
 (+) 
linha 1 0 1 1 1 1 0 0 40 
Nova linha 1 0 -0,5 0 1,5 1 0 -0,5 25 
 
Cálculo da nova linha L2 (coeficiente da variável que entra = 1) 
Nova linha pivô 0 1,5 1 -0,5 0 0 0,5 15 
X (-1) 0 -1,5 -1 0,5 0 0 -0,5 -15 
 (+) 
linha 2 0 2 1 -1 0 1 0 20 
Nova linha 2 0 -0,5 0 -0,5 0 1 -0,5 5 
 
Reescrevendo a nova tabela teremos: 
 Z X1 X2 X3 F1 F2 F3 b b/X1 
Tabela 2 1 2,5 0 -2,5 0 0 1,5 45 
L1 F1 0 -0,5 0 1,5 1 0 -0,5 25 16,67 Sai 
L2 F2 0 0,5 0 -0,5 0 1 -0,5 5 -10L3 X2 0 1,5 1 -0,5 0 0 0,5 15 -30 
 Entra 
Nova solução: 
Variáveis Não básicas: X1 = 0; X3 = 0 e F3 = 0 
Variáveis básicas: X2 = 15; F1 = 25 e F2 = 5 
Valor de Z: Z = 45 
Essa solução não é ótima, pois o coeficiente de X3 na nova função objetivo tem 
valor negativo (-2,5). 
Vamos calcular uma nova iteração: 
 Variável que entra: X3 (coeficiente negativo da função objetivo de maior 
valor absoluto) 
 Variável que sai (termos independentes b divididos pelos coeficientes de X3 
– variável que entra na base): 
Da coluna b/X3 
25/1,5 = 16,67; 5/(-0,5) = -10 e 1,5/(-0,5) = -30 
Pesquisa Operacional I 
 
57 
Sai o de menor valor: desconsidere os valores negativos, pois dariam valores 
negativos para as variáveis na próxima solução. Sai, portanto, a variável da linha L1: 
F1 
Linha pivô: linha 1 
Elemento pivô: 1,5 
 Dividindo a linha pivô por 1,5, temos: 
 
Nova linha pivô: 
Linha pivô 0 -0,5 0 1,5 1 0 -0,5 25 
Dividido por 1,5 0 -0,33 0 1 0,67 0 -0,33 16,67 
Cálculo da nova linha de Z (coeficiente da variável que entra = -2,5) 
Nova linha pivô 0 -0,33 0 1 0,67 0 -0,33 16,67 
X (2,5) 0 -0,83 0 2,5 1,68 0 -0,83 41,68 
 (+) 
linha Z 1 2,5 0 -2,5 0 0 1,5 45 
Nova linha Z 1 1,68 0 0 1,68 0 0,68 86,68 
 
Cálculo da nova linha L2 (coeficiente da variável que entra = -0,5) 
Nova linha pivô 0 -0,33 0 1 0,67 0 -0,33 16,67 
X (0,5) 0 -0,17 0 0,5 0,34 0 -0,17 8,34 
 (+) 
linha 2 0 0,5 0 -0,5 0 1 -0,5 5 
Nova linha 2 0 0,34 0 0 0,34 1 -0,67 13,34 
 
Cálculo da nova linha L3 (coeficiente da variável que entra = -0,5) 
Nova linha pivô 0 -0,33 0 1 0,67 0 -0,33 16,67 
X (0,5) 0 -0,17 0 0,5 0,34 0 -0,17 8,34 
 (+) 
linha 3 0 1,5 1 -0,5 0 0 0,5 15 
Nova linha 3 0 1,34 1 0 0,34 0 0,34 23,34 
 
 
Pesquisa Operacional I 
 
58 
Reescrevendo a nova tabela teremos: 
 Z X1 X2 X3 F1 F2 F3 b 
Tabela 3 1 1,68 0 0 1,68 0 0,68 86,68 
L1 X3 0 -0,33 0 1 0,67 0 -0,33 16,67 
L2 F2 0 0,34 0 0 0,34 1 -0,67 13,34 
L3 X2 0 1,34 1 0 0,34 0 0,34 23,34 
 
Nova solução: 
Variáveis Não básicas: X1 = 0; F1 = 0 e F3 = 0 
Variáveis básicas: X2 = 23,34; X3 = 16,67e F2 = 13,34 
Valor de Z: Z = 86,68 
Essa nova solução é ótima, pois todos os coeficientes das variáveis na função 
objetivo são positivos. Temos o valor máximo de Z = 86,68, obtido com X1 = 0, X2 = 
23,34 e X3 = 16,67. 
 
Técnica de variáveis artificiais 
 
Nos exemplos que foram resolvidos até agora pelo método tabular Simplex, as 
restrições eram todas do tipo  com os termos da direita positivos. O acréscimo 
das variáveis de folga fornece nesse caso uma solução básica inicial. 
Veremos agora os demais tipos: 
1º a restrição é do tipo  : a variável de folga é subtraída e seu valor é 
negativo, quando se anulam as variáveis de decisão. 
2º a restrição é do tipo =:não receba a variável de folga. 
Quando estes tipos de estrições acima ocorrem, acrescentamos variáveis 
auxiliares ai com formação de um novo modelo. A solução básica inicial do novo 
modelo é formada pelas variáveis de folga das restrições do tipo  e pelas 
variáveis auxiliares ai. 
 
Pesquisa Operacional I 
 
59 
Exemplo: 
321321 );;( xxxxxxZimizarMax  
Sujeito a 
6032
202
102
321
321
321



xxx
xxx
xxx
 
0,, 321 xxx 
a) Acrescentar as variáveis de folga: 
2X1 + X2 - X3 + F1 = 10 
X1 + X2 + 2X3 - F2 = 20 
2X1 + X2 + 3X3 = 60 
 
Nestes termos, não há uma solução básica inicial devido a segunda e a terceira 
restrições. Pois F2 = -20 é inviável segundo a não negatividade e 0 = 60 é 
matematicamente falso. 
b) Acrescentar nas segunda e terceira restrições as variáveis auxiliares ou 
artificiais a2 e a3: 
2X1 + X2 - X3 + F1 = 10 
X1 + X2 + 2X3 - F2 + a2 = 10 
2X1 + X2 + 3X3 + a3 = 60 
 
Agora temos uma solução básica inicial: F1 = 10; a2 = 20 e a3 = 60 com todas as 
outras variáveis nulas. 
 
Pesquisa Operacional I 
 
60 
 
Variação das aplicações do Método Simplex 
 
O problema da minimização. 
No caso da função objetivo ser de minimização, então, devemos multiplicá-la 
por (-1). Obtendo uma função equivalente para a maximização. 
Exemplo: 
321321 43);;( xxxxxxZrMinimimiza  
Sujeito a 
202
10
321
321


xxx
xxx
 
 0,, 321 xxx 
 
O modelo equivalente será então: 
321 43)( xxxZimizarMax  
Sujeito a 
202
10
321
321


xxx
xxx
 
 0,, 321 xxx 
Resolvido o modelo equivalente, teremos a solução do modelo original com a 
troca do sinal de Z. 
O método de a função objetivo auxiliar 
Esse método foi desenvolvido para atender as equações e inequações dos 
tipos = e  , acrescentando as variáveis auxiliares, para compor com as folga das 
inequações do tipo  , a solução básica necessária à aplicação do Simplex. 
Começaremos a estudar esse método, construindo uma função objetivo 
auxiliar W, formada pela soma das variáveis auxiliares. 
W = a1 + a2 + , ..., + an 
Pesquisa Operacional I 
 
61 
A função W deve ser escrita em termos das variáveis originais e comporá o 
novo objetivo a ser minimizado. Minimizar W porque o objetivo desse método é 
fazer as variáveis auxiliares iguais à zero. 
Quando as variáveis auxiliares forem não básicas, teremos: 
a1 = a2 = ... = an = 0 e W = 0 
As variáveis e funções auxiliares podem ser abandonadas, como diz o próprio 
nome: auxiliares. O novo objetivo será dado pela função objetivo original. 
Então teremos o modelo original com a solução básica inicial procurada. 
Exemplo: 
321321 );;( xxxxxxZimizarMax  
Sujeito a 
6032
202
102
321
321
321



xxx
xxx
xxx
 
0,, 321 xxx 
 
1.Começamos acrescentando as variáveis de folga e as variáveis auxiliares, 
conforme já fizemos anteriormente, teremos então: 
6032
202
102
3321
22321
1321



axxx
aFxxx
Fxxx
 
2.Fazemos a função auxiliar W = a2+a3 
Da segunda restrição: a2 = -X1-X2-2X3+F2+20 
Da terceira restrição: a3 = -2X1-X2-3X3+60 
W = a2+a3 = -3X1-2X2-5X3+F2+80 
Mini W = Max (-W) = 3X1+2X2+5X3-F2-80 
Logo, -W -3X1-2X2-5X3+F2 = -80 
Pesquisa Operacional I 
 
62 
O quadro com a função auxiliar fica: 
 Z W X1 X2 X3 F1 F2 a2 a3 b b/X3 
Tabela 1 1 -1 -1 -1 0 0 0 0 0 
L1 F1 0 2 1 -1 1 0 0 0 10 -10 
L2 a2 0 1 1 2 0 -1 1 0 20 10 Sai 
L3 a3 0 2 1 3 0 0 0 1 60 20 
 -w -1 -3 -2 -5 0 1 0 0 -80 
 Entra 
 
Solução da tabela 1 
Variáveis Não básicas: X1 = 0; X2 = 0; X3 = 0 e F2 = 0 
Variáveis básicas: F1 = 10; a2 = 20 e a3 = 60 
Valor de W: W = 80 
 
A função objetivo a ser minimizada é W. Observando seus coeficientes, verificamos 
que a resolução do quadro não é ótima. 
Cálculo da nova solução: 
 Variável que entra: X3 (coeficiente negativo da função objetivo de maior 
valor absoluto: -5) 
 Variável que sai (termos independentes b divididos pelos coeficientes de 
X3 – variável que entra na base): 
Da coluna b/X3 
10/(-1) = -10; 20/2 = 10 e 60/3 = 20 
Sai o de menor valor, não negativo: 10. Sai a variável da linha 2 (a2) 
Linha pivô: linha 2 
Elemento pivô: 2 
 Dividindo a linha pivô por 2, temos: 
 
Pesquisa Operacional I 
 
63 
 
Nova linha pivô: 
Cálculo da nova linha de Z (coeficiente = -1) 
Nova linha pivô 0 0,5 0,5 1 0 -0,5 0,5 0 10 
X (1) 0 0,5 0,5 1 0 -0,5 0,5 0 10 
 (+) 
linha Z 1 -1 -1 -1 0 0 0 0 0 
Nova linha Z 1 -0,5 -0,5 0 0 -0,5 0,5 0 10 
 
Cálculo da nova linha L1 (coeficiente = -1) 
Nova linha pivô 0 0,5 0,5 1 0 -0,5 0,5 0 10 
X (1) 0 0,5 0,5 1 0 -0,5 0,5 0 10 
 (+) 
linha 1 0 2 1 -1 1 0 0 0 10 
Nova linha 1 0 2,5 1,5 0 1 -0,5 0,5 0 20 
 
Cálculo da nova linha L3 (coeficiente = 3) 
Nova linha pivô 0 0,5 0,5 1 0 -0,5 0,5 0 10 
X (-3) 0 -1,5 -1,5 -3 0 1,5 -1,5 0 -30 
 (+) 
linha 3 0 2 1 3 0 0 0 1 60 
Nova linha 3 0 0,5 -0,5 0 0 1,5 -1,5 1 30 
 
Cálculo da nova linha W (coeficiente = -5) 
Nova linha pivô 0 0,5 0,5 1 0 -0,5 0,5 0 10 
X (5) 0 2,5 2,5 5 0 -2,5 2,5 0 50 
(+) 
linha w -1 -3 -2 -5 0 1 0 0 -80 
Nova linha w -1 -0,5 0,5 0 0 -1,5 2,5 0 -30 
 
Pesquisa Operacional I 
 
64Reescrevendo a nova tabela teremos: 
 Z W X1 X2 X3 F1 F2 a2 a3 b b/X1 
Tabela 2 1 -0,5 -0,5 0 0 -0,5 0,5 0 10 
L1 F1 0 2,5 1,5 0 1 -0,5 0,5 0 20 -40 
L2 X3 0 0,5 0,5 1 0 -0,5 0,5 0 10 -20 
L3 a3 0 0,5 -0,5 0 0 1,5 -1,5 1 30 20 Sai 
 -w -1 -0,5 0,5 0 0 -1,5 2,5 0 -30 
 Entra 
Nova solução: 
Variáveis Não básicas: X1 = 0; X2 = 0, F2 = 0 e a2 = 0 
Variáveis básicas: X3 = 10; F1 = 20 e a3 = 30 
Valor de W: W = 30 
 
Cálculo da nova solução: 
 Variável que entra: F2 (coeficiente -1,5) 
 Variável que sai (termos independentes b divididos pelos coeficientes de F2 
– variável que entra na base): 
Da coluna b/F2, 
20/(-0,5) = -40; 10/(-0,5) = -20 e 30/1,5 = 20 
Sai o de menor valor, não negativo: 20 Sai a variável da linha 3 (a3) 
Linha pivô: linha 3 
Elemento pivô: 1,5 
 Dividindo a linha pivô por 1,5, temos: 
 
Pesquisa Operacional I 
 
65 
Nova linha pivô: 
Linha pivô 0 0,5 -0,5 0 0 1,5 -1,5 1 30 
Dividido por 1,5 0 0,33 -0,33 0 0 1 -1 0,67 20 
 
Cálculo da nova linha de Z (coeficiente = -0,5) 
Nova linha pivô 0 0,33 -0,33 0 0 1 -1 0,67 20 
X (0,5) 0 0,167 -0,17 0 0 0,5 -0,5 0,33 10 
 (+) 
linha Z 1 -0,5 -0,5 0 0 -0,5 0,5 0 10 
Nova linha Z 1 -0,333 -0,667 0 0 0 0 0,333 20 
 
Cálculo da nova linha L1 (coeficiente = -0,5) 
Nova linha pivô 0 0,333 -0,33 0 0 1 -1 0,67 20 
X (0,5) 0 0,167 -0,17 0 0 0,5 -0,5 0,33 10 
 (+) 
linha 1 0 2,5 1,5 0 1 -0,5 0,5 0 20 
Nova linha 1 0 2,667 1,333 0 1 0 0 0,333 30 
 
Cálculo da nova linha L2 (coeficiente = -0,5) 
Nova linha pivô 0 0,333 -0,33 0 0 1 -1 0,67 20 
X (0,5) 0 0,167 -0,17 0 0 0,5 -0,5 0,33 10 
 (+) 
linha 2 0 0,5 0,5 1 0 -0,5 0,5 0 10 
Nova linha 2 0 0,667 0,333 1 0 0 0 0,333 20 
 
Cálculo da nova linha W (coeficiente = -1,5) 
Nova linha pivô 0 0,333 -0,33 0 0 1 -1 0,67 20 
X (1,5) 0 0,5 -0,5 0 0 1,5 -1,5 1 30 
 (+) 
linha w -1 -0,5 0,5 0 0 -1,5 2,5 0 -30 
Nova linha w -1 0 0 0 0 0 1 1 0 
 
Pesquisa Operacional I 
 
66 
Nova tabela: 
 Z X1 X2 X3 F1 F2 a2 a3 b 
Tabela 3 1 -0,333 -0,667 0 0 0 0 0,333 20 
L1 F1 0 2,667 1,333 0 1 0 0 0,333 30 
L2 X3 0 0,667 0,333 1 0 0 0 0,333 20 
L3 F2 0 0,333 -0,333 0 0 1 -1 0,667 20 
 -w -1 0 0 0 0 0 1 1 0 
 
Nova solução: 
Variáveis Não básicas: X1 = 0; X2 = 0; a2 = 0 e a3 = 0 
Variáveis básicas: X3 = 20; F1 = 30 e F3 = 20 
Valor de W: W = 0 
O problema apresenta agora uma solução básica formada pelas variáveis 
originais. As variáveis auxiliares e a função objetivo auxiliar são nulas. Devemos 
abandoná-las e continuar a solução do problema com a função objetivo original 
em Z. 
 
A tabela será, portanto: 
 Z X1 X2 X3 F1 F2 b 
 1 -0,333 -0,667 0 0 0 20 
L1 F1 0 2,667 1,333 0 1 0 30 
L2 X3 0 0,667 0,333 1 0 0 20 
L3 F2 0 0,333 -0,333 0 0 1 20 
 
Nesse quadro original em Z será aplicado o método Simplex para a solução 
ótima de Z. Após aplicar o método Simplex chegaremos a seguinte solução: 
Solução: 
Variáveis Não básicas: X1 = 0 e F1 = 0 
Variáveis básicas: X2 = 22,5; X3 = 12,5 e F2 = 27,5 
Valor de Z: Z = 35 
 
Pesquisa Operacional I 
 
67 
Caso a função auxiliar W represente solução ótima e valor não nulo, as 
variáveis auxiliares não serão todas nulas e o modelo original não representará 
então uma solução básica. Nesse caso, o problema não tem solução. 
Estamos encerrando a unidade. Sempre que tiver uma dúvida entre em 
contato com seu tutor virtual através do ambiente virtual de aprendizagem e 
consulte sempre a biblioteca do seu polo. 
 
É hora de se avaliar 
Lembre-se de realizar as atividades desta unidade de estudo. Elas irão 
ajudá-lo a fixar o conteúdo, além de proporcionar sua autonomia no processo de 
ensino-aprendizagem. 
 
 
Pesquisa Operacional I 
 
68 
 
Exercícios – Unidade 3 
 
1. Considere o seguinte enunciado: 
2121 1210);( xxxxRimizarMax  
Sujeito a 
27032
100
21
21


xx
xx
 
0, 21 xx 
Assinale a alternativa que apresente o elemento pivô da primeira tabela do 
método Simplex. 
a) 1 
b) 2 
c) 3 
d) 5 
e) 10 
 
2. Considere o seguinte enunciado: 
321321 432);;( xxxxxxLimizarMax  
Sujeito a 
80
2102
100
1
21
321



x
xx
xxx
 
0,, 321 xxx 
 
 
Pesquisa Operacional I 
 
69 
Assinale a alternativa que apresente o elemento pivô da primeira tabela do 
método Simplex. 
a) 1 
b) 2 
c) 3 
d) 5 
e) 10 
 
Considere o seguinte enunciado para as questões 3, 4 e 5: 
321321 422,0);;( xxxxxxZimizarMax  
Sujeito a 
15
503
202
321
31
21



xxx
xx
xx
 
0,, 321 xxx 
3. Assinale a alternativa que apresente o elemento pivô da primeira tabela do 
método Simplex. 
a) 1 
b) 2 
c) 3 
d) 5 
e) 10 
 
4. Assinale a alternativa que apresente as variáveis básicas e não básicas da 
segunda tabela do método Simplex. 
a) Básicas: X1 = 0; X2 = 0 e X3 = 0; não básicas: F1 =20; F2 = 50 e F3 = 15 
Pesquisa Operacional I 
 
70 
b) Básicas: X1 = 0; X2 = 0 e F2 = 0; não básicas: F1 =20; X3 = 50 e F3 = 15 
c) Básicas: X1 = 0; X2 = 0 e X3 = 0; não básicas: F1 =20; F2 = -15 e F3 = 50 
d) Básicas: X1 = 0; X2 = 0 e F2 = 0; não básicas: F1 =20; X3 = 50 e F3 = 65 
e) Básicas: X1 = 0; X2 = 0 e X3 = 0; não básicas: F1 =0; F2 = 50 e F3 = -15 
 
5. O valor ótimo de Z é igual a: 
a) 200 
b) 220 
c) 240 
d) 260 
e) 280 
 
Considere o seguinte enunciado para as questões 6, 7 e 8: 
321321 435);;( xxxxxxZimizarMax  
Sujeito a 
1505
2802
600
32
31
321



xx
xx
xxx
 
0,, 321 xxx 
6. Assinale a alternativa que apresente o elemento pivô da primeira tabela do 
método Simplex. 
a) 1 
b) 2 
c) 3 
d) 5 
e) 10 
Pesquisa Operacional I 
 
71 
 
7. Assinale a alternativa que apresente as variáveis básicas e não básicas da 
segunda tabela do método Simplex. 
a) Básicas: X1 = 0 e X3 = 0; não básicas: F1 = 500, F2 = 50 e X2 = 280 
b) Básicas: X1 = 0; X2 = 0 e F2 = 0; não básicas: F1 =280; X3 = 50 
c) Básicas: X1 = 0; X2 = 0 e X3 = 0; não básicas: F1 =500; F2 = -30 
d) Básicas: X1 = 0; X2 = 0 e F2 = 0; não básicas: F1 =500 e X3 = 50 
e) Básicas: X1 = 0 e X3 = 0; não básicas: F1 = 570, F2 = 280 e X2 = 30 
 
8. O valor ótimo de Z é igual a: 
a) 90 
b) 610 
c) 862 
d) 915 
e) 1120 
 
Considere o seguinte enunciado para as questões 9 e 10: 
321321 23);;( xxxxxxZMinimizar  
Sujeito a 
1
623
633
21
21
321



xx
xx
xxx
 
0,, 321 xxx 
 
 
Pesquisa Operacional I 
 
72 
9) Encontre as variáveis básicas e não básicas quando o valor da função 
objetivo auxiliar é igual a zero (W = 0). 
 
 
 
 
 
 
 
 
10) Encontre o valor de Z que minimiza a função objetivo e os respectivos 
valores de X1, X2 e X3. 
 
 
 
Pesquisa Operacional I 
 
73 
 
4 Dualidade 
Pesquisa Operacional I 
 
74 
 
Nesta unidade, será apresentada forma de solução ou possíveis soluções de 
um P.P.L. usando a dualidade. 
 
Objetivos da unidade: 
Mostrar ao leitor que a quantidade de cálculo as necessária para resolver um 
modelo linear pelo Simplex pode ser reduzida, substituindo o modelo chamado 
primal pelo modelo dual. 
 
Plano da unidade: 
 Introdução. Como obter? Interpretação. 
 Tabela de conversão Dual-Primal. Exemplos. 
 Propriedades importantes Primal-Dual. 
 
Bons estudos! 
 
Pesquisa Operacional I 
 
75 
 
Introdução. Como obter? Interpretação. 
 
O modelo inicial de um problema de programação linear, chamado de primal, 
pode ser substituído por um outro modelo que chamamos de Dual. Isso será 
possível em determinadas situações onde a quantidade de cálculos necessária para 
solucionar um modelo linear pelo método Simplex pode ser reduzida. 
Considere o modelo de programações linear que tem a função objetivo de 
maximização, as restrições são do tipo  e as variáveis são não negativas. 
Chamamos esse modelo de primal ao qual podemos associar outro modelo que 
chamamos de dual, que será construído da seguinte maneira: 
1. Variáveis de decisão do dual: a cada restrição do primal, faremoscorresponder uma variável yi; 
2. Objetivo: a função objetivo será de minimização. Cada uma das parcelas 
será o produto da variável yi pelo termo da direita da restrição 
correspondente; 
3. Restrições: Cada variável de decisão primal gera uma restrição no dual. 
Termos da esquerda: Cada termo é o produto da variável dual yi pelo 
coeficiente respectivo da variável de decisão primal. 
Sinal: Sinal do tipo  . 
Termo da direita: é o coeficiente da variável primal na função objetivo. 
Exemplo: 
Primal: 
321321 32);;( xxxxxxZimizarMax  Variáveis duais 
Sujeito a 
30
2062
10243
321
321
321



xxx
xxx
xxx
 
0,, 321 xxx 
y1 
y2 
y3 
Pesquisa Operacional I 
 
76 
Dual: 
321321 302010);;( yyyyyyDMinimizar  
Sujeito a 
12
364
223
321
321
321



yyy
yyy
yyy
 
0,, 321 yyy 
 
Tabela de conversão Dual-Primal. 
 
Exemplos. 
Consideremos agora o seguinte modelo primal: 
a) Função objetivo de minimização; 
b) Restrições do tipo  ; 
c) Variáveis todas não negativas. 
Seu dual será então: 
a) Função objetivo de maximização; 
b) Restrições do tipo  ; 
c) Variáveis todas não negativas. 
Exemplo: 
Votemos ao exemplo anterior e tomemos o seu dual como o primal de agora. 
 
 
 
 
 
Coeficientes de x1 
Coeficientes de x2 
Coeficientes de x3 
(Termos da direita) 
Pesquisa Operacional I 
 
77 
Primal: 
321321 302010);;( xxxxxxZMinimizar  
Sujeito a 
12
364
223
321
321
321



xxx
xxx
xxx
 
0,, 321 xxx 
Dual: 
321321 32);;( yyyyyyDimizarMax  
Sujeito a 
30
2062
10243
321
321
321



yyy
yyy
yyy
 
0,, 321 yyy 
Deste exemplo, podemos concluir: 
a) Que o dual de um dual é o modelo primal; 
b) Se uma restrição primal é do tipo =, a variável dual correspondente será 
sem restrição de sinal; 
c) Se uma variável primal for sem restrição de sinal, as restrições do dual 
correspondente será do tipo =. 
Exemplo: 
Primal: 
321321 32);;( xxxxxxZimizarMax  
Sujeito a 
2042
10
321
21


xxx
xx
 
0,, 321 xxx 
Variáveis 
duais 
 y1 
y2 
y3 
(Termos da direita) 
Coeficientes de x1 
Coeficientes de x2 
Coeficientes de x3 
y1 
y2 
Pesquisa Operacional I 
 
78 
Dual: 
2121 2010);( yyyyDMinimizar  
Sujeito a 
1
34
22
2
21
21



y
yy
yy
 
21 ,0 yy  Livre 
 
Podemos resumir essas regras na seguinte tabela: 
Problema de 
Maximização 
 Problema de 
Minimização 
Restrições Variáveis 
≥ ⇔ ≤ 0 
≤ ⇔ ≥ 0 
= ⇔ Irrestrita 
Variáveis Restrições 
≥ 0 ⇔ ≥ 
≤ 0 ⇔ ≤ 
Irrestrita ⇔ = 
 
Observe que a tabela não utiliza a notação primal e dual. O que importa 
aqui é o sentido da otimização (se o primal for de maximização, então o dual 
será de minimização e vice-versa). É importante observar que ser irrestrita é 
sinônimo de ser livre. 
 
(Termos da direita) 
Pesquisa Operacional I 
 
79 
 
Propriedades importantes Primal-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 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 – (coeficiente de xi = 
valor de yFi); 
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= yi); 
Como o primal é dual do próprio dual, vale o raciocínio no sentido dual 
primal. – (coeficiente yi = valor de xFi) e (coeficiente yFi = valor de xi). 
Exemplo: 
Primal: 
321321 32);;( xxxxxxZimizarMax  
Sujeito a 
93
1242
10
321
321
321



xxx
xxx
xxx
 
0,, 321 xxx 
Dual: 
321321 91210);;( yyyyyyDMinimizar  
Sujeito a 
34
23
12
321
321
321



yyy
yyy
yyy
 
Pesquisa Operacional I 
 
80 
0,,
321
yyy 
Colocando as variáveis de folga no primal e no dual, temos: 
Primal: 
321321 32);;( xxxxxxZimizarMax  
Sujeito a 
93
1242
10
3321
2321
1321



Fxxx
Fxxx
Fxxx
 
 
Transpondo para o quadro do simplex: 
Primal Z X1 X2 X3 F1 F2 F3 b 
Tabela 1 1 -1 -2 -3 0 0 0 0 
L1 F1 0 1 1 1 1 0 0 10 
L2 F2 0 2 1 4 0 1 0 12 
L3 F3 0 1 3 -1 0 0 1 9 
 
Solução: 
Variáveis Não básicas: F1 = 10; F2 = 10 e F3 = 9 
Variáveis básicas: X1 = 0; X2 = 0 e X3 = 0 
Valor de Z: Z = 0 
Dual: 
321321 91210);;( yyyyyyDMinimizar  
Como já vimos minimizar D é igual a maximizar –D, então: 
091210
91210);;)((
321
321321


yyyD
yyyyyyDMaximizar
 
Pesquisa Operacional I 
 
81 
Sujeito a 
34
23
12
3321
2321
1321



Fyyy
Fyyy
Fyyy
 
 
Transpondo para o quadro do simplex: 
Dual D Y1 Y2 Y3 F1 F2 F3 c 
Tabela 1 -1 10 12 9 0 0 0 0 
L1 F1 0 1 2 1 -1 0 0 1 
L2 F2 0 1 1 3 0 -1 0 2 
L3 F3 0 1 4 -1 0 0 -1 3 
 
Solução: 
Variáveis Não básicas: F1 = -1; F2 = -2 e F3 = -3 
Variáveis básicas: Y1 = 0; Y2 = 0 e Y3 = 0 
Valor de D: D = 0 
 
Observe a correspondência entre o primal e o dual: 
Coeficiente de x1 = -1 => Valor de F1 (de y) = -1 
Coeficiente de x2 = -2 => Valor de F2 (de y) = -2 
Coeficiente de x3 = -3 => Valor de F3 (de y) = -3 
Coeficiente de F1 (de x) = 0 => Valor de y1 = 0 
Coeficiente de F2 (de x) = 0 => Valor de y2 = 0 
Coeficiente de F3 (de x) = 0 => Valor de y3 = 0 
Valor de x1 = 0 => coeficiente de F1 (de y) = 0 
Valor de x2 = 0 => coeficiente de F2 (de y) = 0 
Valor de x3 = 0 => coeficiente de F3 (de y) = 0 
Valor de F1 = 10 (de x) => coeficiente de y1 = 10 
Pesquisa Operacional I 
 
82 
Valor de F2 = 12 (de x) => coeficiente de y2 = 12 
Valor de F3 = 9 (de x) => coeficiente de y3 = 9 
Valor de Z = 0 => Valor de D = 0 
Continuando a solução do primal, com a entrada da variável x3 (pois seu 
coeficiente -3) e a saída da variável F2 (12/4=3), após o pivotamento, será: 
 
Primal Z X1 X2 X3 F1 F2 F3 b 
Tabela 2 1 0,5 -1,25 0 0 0,75 0 9 
L1 F1 0 0,5 0,75 0 1 -0,25 0 7 
L2 X3 0 0,5 0,25 1 0 0,25 0 3 
L3 F3 0 1,5 3,25 0 0 0,25 1 12 
 
Solução: 
Variáveis Não básicas: F1 = 7; F3 = 12 e X3 = 3 
Variáveis básicas: X1 = 0; X2 = 0 e F2 = 0 
Valor de Z: Z = 9 
Usando a correspondência descrita acima, vamos montar o quadro dual 
correspondente (considerando a Tabela 2 do Primal e sua solução): 
Coeficientes xi (linha de Z) => valores de yfi (coluna de c) 
Coeficientes xfi (linha de Z) => valores de yi (coluna de c) 
Valores de xi (solução acima) => coeficientes yfi (linha de D) 
Valores de xfi (solução acima) => coeficientes yi (linha de D) 
 
Temos então o quadro abaixo: 
Dual D Y1 Y2 Y3 F1 F2 F3 c 
Tabela 2 -1 7 0 12 0 0 3 -9 
L1 F1 0 1 0 0,5 
L2 F2 0 0 1 -1,25 
L3 Y2 1 0 0 0,75 
Solução: 
Pesquisa Operacional I 
 
83 
Variáveis Não básicas: F1 = 0,5; F2 = -1,25 e Y2 = 0,75 
Variáveis básicas: Y1 = 0; Y3 = 0 e F3 = 0 
Valor de D: D = 9 
 
 
 
Vamos ao terceiro quadro primal: 
Primal Z X1 X2 X3 F1 F2 F3 b 
Tabela 3 1 1,077 0 0 0 0,846 0,385 13,615 
L1 F1 0 0,154 0 0 1 -0,308 -0,231 4,231 
L2 X3 0 0,385 0 1 0 0,231 -0,077 2,077 
L3 X2 0 0,461 1 0 0 0,077 0,308 3,692 
 
Solução: 
Variáveis Não básicas: X2 = 3,692; X3 = 2,077 e F1 = 4,231 
Variáveis básicas: X1 = 0; F2 = 0 e F3 = 0 
Valor de Z: Z = 13,615 
 
Usando a correspondência descrita, podemos montar o terceiro quadro dual: 
Dual D Y1 Y2 Y3 F1 F2 F3 c 
Tabela 3 -1 4,321 0 0 0 3,962 2,077 -13,615 
L1 F1 0 0 0 1 0 1,077 
L2 Y2 0 1 0 0 -1 0,846 
L3 Y3 0 0 1 0 0 0,385 
 
Solução: 
Variáveis Não básicas: Y2 = 0,846; Y3 = 0,385 e F1 = 1,077 
Variáveis básicas: Y1 = 0; F2 = 0 e F3 = 0 
Valor de D: D = 13,615 
Pesquisa Operacional I 
 
84 
 
 
 
Conclusão: as soluções matemáticas do primal e do dual são pontos ótimos de 
mesmo valor (ou seja, Z=D). A escolha entre um e outro se dará levando em conta 
o menor esforço computacional, que depende do número de restrições, das 
variáveis artificiais