Introdução à Pesquisa Operacional

Prévia do material em texto

Pesquisa 
Operacional 
(Programação Linear) 
 
EPR05 – Pesquisa 
Operacional II 
 
 
Prof. José Arnaldo Barra Montevechi 
 
 
 
 
 
Escola Federal de Engenharia de Itajubá 
 
2000 
Curso de Pesquisa Operacional 2 
1 - PESQUISA OPERACIONAL: HISTÓRIA E 
CONCEITOS 
 
1.1 Introdução 
O objetivo do curso é apresentar alguns MÉTODOS MATEMÁTICOS essenciais à Pesquisa 
Operacional (PO). Este capítulo pretende dar a origem e as idéias fundamentais da PO. 
Infelizmente, um curso introdutório de PO não pode responder completamente as perguntas: 
 
a) O que deve (o aluno) aprender sobre PO se pretende ser um economista (dirigente, 
gerente, administrador) mais que um especialista? 
b) O que deve (o aluno) aprender sobre PO tendo em vista que deseja aplicá-la a problemas 
reais? 
 
No contexto destas duas perguntas o objetivo principal do curso é: 
 
1) Introduzir as idéias mais importantes em PO, as quais são fundamentais e permanentes. 
2) Dar o curso em nível que o aluno possa entender e apreciar a força e as limitações 
inerentes a PO. 
3) Preparar e motivar futuros especialistas em PO. 
4) Apresentar e aplicar alguns métodos de PO (METODOLOGIA). 
 
1.2 Notas Históricas 
Desde o advento da primeira revolução industrial o mundo tem apresentado um notável 
desenvolvimento e crescimento em tamanho e complexidade de suas organizações. 
Os caminhos da PO podem ser traçados a muitas décadas atrás, quando foi aplicada a 
administração cientifica às organizações. 
Como a tendência natural é aumentar a complexidade e a especialização das organizações, 
torna-se mais e mais difícil alocar seus recursos disponíveis pelas suas várias atividades de 
maneira a obter a melhor eficiência para a organização. 
Entretanto, o termo PO é geralmente atribuído aos serviços militares durante a Segunda 
Grande Guerra Mundial (1939). Os dirigentes militares chamaram equipes de cientistas para 
estudar problemas estratégicos e táticos associados com a defesa aérea e terrestre do país. Seu 
objetivo era determinar a melhor utilização efetiva dos recursos militares limitados. 
Curso de Pesquisa Operacional 3 
 
l .3 conceitos 
Conceito 1: PO é a aplicação do método científico, por equipes interdisciplinares, a 
problemas que dizem respeito ao controle de sistemas organizados (homem-máquina) com a 
finalidade de obter as soluções que melhor satisfazem aos objetivos da organização, como 
UM TODO. 
 
Conceito 2: A PO se esforça ao máximo para compensar a incerteza, mas não a pode 
eliminar. (Pois é importante assinalar que como estão implicados fatores humanos e 
máquinas, é fornecida uma estimativa da incerteza no resultado previsto e nos valores, nas 
eficiências e nos custos da ação proposta). 
 
Conceito 3: A PO firmou-se como uma atividade que pode colocar a serviço da gerência - e 
realmente o faz - novas atitudes, novos conceitos e novas técnicas; ajudando-a a resolver 
problemas complexos e tomar decisões importantes. 
 
ESTRATÉGIA - significa o dispositivo básico de recursos disponíveis ao dirigente. 
TÁTICA - exprime a maneira de utilizar os recursos confiados a uma atividade determinada. 
TECNOLOGIA - é o termo que se aplica às coisas físicas envolvidas na transformação de 
"INPUTS" em "OUTPUTS" da atividade. 
ORGANIZAÇÃO - quer dizer virtualmente qualquer complexo identificável de homens e 
máquinas trabalhando no sentido de um objetivo determinado, quer o complexo seja militar 
ou civil, industrial ou comercial, governamental ou privado. 
 
Conceito 4: PO é a aplicação de análises quantitativas dos problemas gerenciais. O objetivo 
da análise é encontrar as melhores soluções dos problemas, isto é, escolher as boas decisões. 
 
Conceito 5: Pesquisa Operacional é a preparação científica das decisões, visando a 
modificação do binômio "Experiência - Intuição" pela "Informação - Racionalidade". 
 
Conceito 6: A PO é o conjunto de métodos que depois de haver analisado, recorrendo as 
diversas disciplinas cientificas envolvidas, as relações que unem os fatores de ordem técnica 
ou psicológica que concorrem na formação de um fenômeno econômico ou humano se 
Curso de Pesquisa Operacional 4 
propõem, com a finalidade de preparar as decisões que se devem tomar, determinar 
racionalmente as soluções mais eficientes (eficazes) ou as mais econômicas, recorrendo a 
procedimentos estatísticos e/ou matemáticos cuja aplicação exige na maioria das vezes o 
emprego de computadores. 
Em resumo, podemos concluir da PO: 
 
1) Pesquisa sobre operações; 
2) Aplicação de método cientifico por equipes interdiciplinares; 
3) Apresenta novas atitudes, novos conceitos e novas técnicas; 
4) Aplicação de analises quantitativas aos problemas gerenciais; 
5) Resolver problemas complexos; 
6) Tomar decisões importantes (ou escolher as boas decisões); 
7) A problemas que dizem respeito ao controle de sistemas organizados; 
8) Compensar a incerteza. 
 
 
Curso de Pesquisa Operacional 5 
2 - MÉTODO DA PESQUISA OPERACIONAL 
 
2.1 Introdução 
Um estudo de PO consiste em construir um modelo da situação física. Um modelo de PO é 
definido como uma representação idealizada de um sistema organizacional. Este sistema pode 
já ser existente ou pode ainda ser uma idéia a espera de execução. 
No primeiro caso, o objetivo do modelo é analisar as operações do sistema para verificar sua 
performance. No segundo, o objetivo e identificar a melhor estrutura do futuro sistema. 
A complexidade de um sistema real resulta do grande número de variáveis que comandam as 
operações do sistema, embora um sistema real possa envolver um número substancial de 
variáveis, geralmente uma pequena fração destas variáveis domina as operações do sistema. 
Então, a simplificação do sistema real em termos de um modelo condensado, identificando 
apenas as variáveis dominantes e as relações entre elas, é o empregado. 
 
Exemplo 1: A fabricação de um produto experimenta um certo número de operações desde o 
tempo de sua concepção pelo projetista, até chegar às mãos do consumidor. Após a aprovação 
do projeto, a ordem de produção é transmitida ao Departamento de Produção (DP), o qual 
requisita o material necessário do Departamento de Material (DM). 
 
O Departamento de Material satisfaz a requisição do seu estoque ou entra em ligação com o 
Departamento de Compras (DC) para comprar o material necessário para atender à requisição 
do DP. Após a fabricação do produto, o Departamento de Vendas (DV), em conjunção com o 
Departamento de Marketing (DMK), assumem a responsabilidade para distribui-lo para os 
consumidores. 
Suponha que o objetivo é determinar o nível de PRODUÇÃO DA INDÚSTRIA. Observando 
o sistema vê-se que um grande número de variáveis influem diretamente no nível de 
produção. Segue alguns exemplos destas variáveis: 
 
a) DEPARTAMENTO DE PRODUÇÃO: Avaliar máquinas - horas, homens - hora, 
especificar a seqüência de operações nas máquinas, números de itens defeituosos, razão de 
inspeção, etc. 
b) DEPARTAMENTO DE MATERIAL: Avaliar o estoque de material, taxa média de 
saída e entrada de material, limitações de armazenagem. 
Curso de Pesquisa Operacional 6 
c) DEPARTAMENTO DE MARKETING: Calcular as vendas, intensificar as campanhas 
promocionais, capacidade de distribuição de produtos, efeito dos produtos competitivos. 
 
Cada uma das variáveis acima afeta (direta ou indiretamente) o nível da produção. É uma 
tarefa ingrata tentar estabelecer relações explicitas entre estas variáveis e o nível de produção. 
Definindo o sistema em função de suas variáveis dominantes, ele pode ser representado por 
duas variáveis: 
 
1a - Uma, representando a taxa de produção do item; 
2a - Uma, representando sua razão de consumo. 
 
Para se determinar a taxa de produção, variáveis tais como avaliação máquina - hora, homem-
hora, sequenciamento e avaliação do material devem ser considerados no cálculo da taxa de 
produção. 
A razãode consumo é determinada em termos das variáveis associadas com o Departamento 
de Marketing. 
É fácil agora pensar em termos do sistema real adotado. Para a taxa de produção e consumo, 
pode-se estabelecer medidas para o excesso ou falta em estoque para um dado nível de 
produção. 
Um modelo abstrato do sistema pode então ser construído para balancear os custos do excesso 
ou falta de estoque. Por exemplo, pode-se estar interessado em determinar o nível de 
produção para um máximo de itens em estoque abaixo de um certo limite. 
Em geral, não há regras fixas para determinar o nível de abstração citado. A validade do 
modelo representando o sistema depende principalmente da criatividade, insight, e 
imaginação dos analistas de PO e a equipe de trabalho no projeto. 
Embora não seja possível fixar regras acerca de como um modelo é construído, pode-se 
socorrer das presentes idéias sob os possíveis tipos de modelos de PO, suas estruturas e 
características gerais. 
Em um estudo de PO ocorrem normalmente as seguintes fases: 
 
1. Formulação (ou definição) do problema; 
2. Construção do modelo matemático; 
3. Obtenção de uma solução a partir do modelo; 
4. Teste do modelo e avaliação da solução obtida; 
Curso de Pesquisa Operacional 7 
5. Estabelecimento de controle sobre a solução; 
6. Implantação da solução. 
 
2.2 Formulação do Problema 
Para se obter a solução de um problema, necessitasse antes formulá-lo de modo a tornar 
possível a pesquisa. 
Ao contrario dos exemplos que serão apresentados no decorrer do curso, a maioria dos 
problemas práticas são trazidos a uma equipe de pesquisa operacional de uma maneira vaga e 
imprecisa. 
Em conseqüência, o primeiro passo consiste em estudar o sistema e estabelecer de uma 
maneira bem definida o problema a ser considerado. Para isto vários elementos devem ser 
determinados exatamente tais como, os objetivos a atingir, as restrições que devem ser 
consideradas, o inter-relacionamento entre o setor a ser estudado e outros setores da 
organização, as possíveis linhas de ação alternativas, etc. 
Como todas as conclusões serão obtidas a partir desta formulação, esta fase tem importância 
capital para o estudo e a formulação inicial deve ser continuamente revista à luz dos novos 
dados obtidos durante as fases posteriores. 
Para determinação dos objetivos apropriados é necessário identificar a pessoa (ou pessoas) 
que toma as decisões relativas ao sistema em estudo, investigar seus objetivos e analisá-los a 
fim de estabelecer precisamente os principais objetivos a atingir a fim de que não sejam 
eliminadas metas ou alternativas de valor. 
Por sua natureza a pesquisa operacional preocupa-se em resolver os problemas da organização 
considerada como um todo e não somente os de alguns de seus setores. 
Por isto, os objetivos formulados devem ser aqueles de toda a organização, não significando 
entretanto que cada problema deva ser resolvido em um estudo de toda organização. Na 
realidade os objetivos fixados devem ser tão específicos quanto possíveis, desde que 
englobem as principais metas de tomada de decisão e mantenham um grau razoável de 
consistência com os objetivos de nível mais elevado da organização. Os efeitos laterais em 
outros setores da organização devem, então, ser considerados somente para verificar se estão 
coerentes com estes objetivos nível mais elevado. 
Para formular um problema precisa-se, pois, examinar os seguintes aspectos: 
1 - Quem toma a decisão? 
2 - Quais os objetivos? 
Curso de Pesquisa Operacional 8 
(A partir destas informações e de outros dados estabelecemos uma medida de desempenho, 
para avaliar as alternativas de ação). 
3 - Quais aspectos da situação estão sujeitos ao controle de quem toma a decisão (as variáveis 
controladas) e dentro de que limites essas variáveis podem ser controladas (restrições). 
4 - Que outros aspectos do meio ambiente, envolvam ou não seres humanos, podem afetar os 
resultados das escolhas disponíveis (as variáveis não controladas) 
 
Portanto, formular um problema para pesquisa consiste em identificar, definir e especificar as 
medidas dos componentes de um modelo de decisão. A determinação da relação entre estes 
componentes (a função f) é o objetivo da fase da pesquisa denominada construção do modelo. 
Nesta primeira fase do estudo, portanto, requer a definição do problema. Do ponto de vista da 
PO, isto indica três aspectos principais: 
 
a) uma exata descrição dos objetivos do estudo; 
b) uma identificação das variáveis de decisão do sistema; 
c) reconhecimento das limitações, restrições, as possíveis linhas de ação alternativas, o inter-
relacionamento entre o setor a ser estudado e outros setores da organização. 
 
É impossível extrair respostas certas de um problema errado. Não se deve esquecer as 
principais partes que afetam os negócios de uma firma: 
 
a) o proprietário (acionistas) que deseja lucros (dividendos, ações, bonificações, valorização 
do capital, etc.). 
b) os empregados, que desejam emprego estável com razoável salário. 
c) os clientes, que desejam um produto confiável a um preço módico (razoável). 
d) os vendedores, que desejam integridade e uma boa remuneração pelas boas qualidades de 
vendedor. 
e) o governo e, consequentemente, a nação, que deseja o pagamento de taxas justas e 
considerações de interesses nacionais. 
 
2.3 Construção do Modelo Matemático 
Conforme o exemplo dado, os modelos são representação idealizada (abstrata) dos problemas; 
geralmente faz-se aproximações e hipóteses simplificadoras para que sejam resolvíveis. Nesta 
Curso de Pesquisa Operacional 9 
fase do estudo faz-se a construção do modelo. Um modelo deve especificar as expressões 
quantitativas para o objetivo e as restrições do problema em termos de suas variáveis de 
decisão. Existem vários tipos básicos de modelo. O modelo matemático é o modelo universal 
da PO. Sua 1inguagem são as equações. Na formulação destes tipos admite-se que todas as 
variáveis relevantes são quantificáveis. 
Então, os símbolos matemáticos são usados para representar as variáveis, as quais são então 
representadas por funções matemáticas apropriadas para descrever as operações do sistema. 
A solução do modelo é então procurada pela manipulação matemática apropriada. 
Em complementação dos modelos matemáticos, modelos de simulação e heurísticos são 
usados. 
 
A estrutura básica dos modelos de PO assumem a forma: 
 
Z = f (x1, x2, x3, ......, xn; y1, y2, y3, ......, yn) 
 
Onde: 
 
Z = função objetivo (medida de eficiência do sistema) 
x1, x2, x3, ......, xn = sistemas de variáveis que são sujeitas ao controle 
y1, y2, y3, ......, yn = sistemas de variáveis que não são sujeitas ao controle 
 
Os modelos simulados e heurísticos não tem nenhuma estrutura fixada, um modelo 
matemático incluí três conjuntos fundamentais de elementos, sendo eles: 
 
a) VARIAVEIS DE DECISÃO E PARÂMETROS: As variáveis de decisão são as 
incógnitas para serem determinadas da solução do modelo. Os parâmetros representam os 
variáveis controladas do sistema. No exemplo, o nível de produção representa a variável 
de decisão; os parâmetros, neste exemplo, são a taxa de produção e consumo. Os 
parâmetros podem ser determinísticos ou probabilísticos. 
 
b) LIMITAÇÕES OU RESTRIÇÕES: Para considerar as limitações físicas do sistema, o 
modelo deve incluir restrições que limitam os valores possíveis das variáveis de decisão. 
Isto é, usualmente, expresso em forma de equações e/ou inequações matemáticas. Por 
exemplo, seja x1 e x2 o número de unidades produzidas de dois produtos (variáveis de 
Curso de Pesquisa Operacional 10 
decisão) e seja a1 e a2 a matéria prima (recursos) por unidade (parâmetros). Se o total dos 
recursos disponíveis (MP) é A, a Função restritiva é dada por a1x1+a2x2 = A. 
 
c) FUNÇÃO OBJETIVO (FO): Define a medida de efetividade do sistema como uma 
função matemática de suasvariáveis de decisão. Por exemplo, se o objetivo do sistema é 
maximizar o lucro total, a função objetiva deve especificar o lucro em termos das 
variáveis de decisão. Em geral, a solução ótima do modelo é obtida quando os melhores 
valores correspondentes das variáveis de decisão são substituídos na PO, enquanto 
satisfazem as restrições. Os modelos matemáticos, em PO, podem ser especificados, 
geralmente, como determinar os valores das variáveis de decisão xj , j= 1,2,...,n a qual 
otimiza Z = f (x1,x2,...,xn) sujeito a uma série de restrições. Na maioria dos sistemas reais, 
as restrições de não - negatividade aparecem como condição natural. 
 
Antes da construção de um modelo matemático deve-se responder a 4 perguntas: 
 
1) Qual é a medida de efetividade do objetivo? Isto é, como será expressa a solução do 
problema (em reais economizados, unidades vendidas, itens produzidos, etc.) 
2) Quais são os fatores sob controle (variáveis controladas)? Isto é, quais aspectos do 
problema pode-se fazer alguma coisa? 
3) Quais são os fatores não controlados (as variáveis não controladas)? Isto é, quais aspectos 
do problema tem-se de aceitar como dados? 
4) Quais são as relações entre estes fatores e os objetivos? Isto é, pode esta relação ser 
expressa em forma de relações matemáticas que constituirão um modelo do problema? 
 
Otimização é geralmente tomada para significar a maximização ou minimização da FO. 
Analistas trabalhando no mesmo problema independentemente podem chegar a modelos 
diferentes e também a funções objetivo (FO) também diferentes. Por exemplo, o analista A 
pode preferir maximizar os lucros, enquanto o analista B pode preferir minimizar os custos. 
Os dois critérios não são equivalentes no sentido que com as mesmas restrições os dois 
modelos não devem produzir a mesma solução ótima. Isto pode ser mostrado claramente, 
enquanto o custo deve estar sob o controle imediato da organização no qual o estudo é feito, 
o lucro deve ser efetuado por fatores incontroláveis, tais como a situação de mercado ditada 
pelos competidores. 
Curso de Pesquisa Operacional 11 
Não se deve pensar que a solução ótima do modelo é a melhor solução do problema. Ela é a 
melhor somente se o critério adotado pode ser justificado como verdadeiro para toda 
organização. 
Na prática, torna-se muito difícil incluir todos os objetivos (possibilidades conflitantes) num 
critério simples (singular) pois isto pode resultar numa função matemática complexa para a 
qual nenhuma solução técnica pode ser prontamente obtida, porque alguns objetivos são 
também inatingíveis para serem quantificados. 
Por exemplo, na determinação da política do nível ótimo de estoque, o verdadeiro objetivo 
deve incluir os objetivos (metas) conflitantes dos departamentos de produção, material, 
vendas e finanças. 
Quando o critério objetivo do modelo representa algum, mas não todos os aspectos 
conflitantes, chamamos de uma solução sub - ótima, e que pode não ser a melhor para a 
organização como um todo. 
Após o modelo matemático ser construído, pode ser necessário simplificá-lo para ser tratado 
analiticamente. Algumas simplificações comuns incluem: 
 
a) Transformar variáveis discretas em contínuas; 
b) Linearizar funções não lineares; 
c) Eliminar algumas das restrições. 
 
2.4 Obtenção de uma Solução a partir do Modelo 
Em modelos matemáticos, isto e, feito usando técnicas de otimização bem definidas, o 
modelo é dito de solução ótima. 
Se modelos de simulação ou heurísticos são usados, o conceito de solução ótima não é bem 
definido e a solução neste caso é usada para obter soluções aproximadas do sistema. 
Como um modelo é mais uma representação ideal do que exata, só pode-se afirmar que a 
solução ótima para o modelo será provavelmente a melhor possível para o problema real, 
devido aos fatores imponderáveis e as incertezas associadas ao problema. 
 
2.5 Teste do Modelo e avaliação da Solução obtida 
Uma das primeiras lições da PO, é que não é geralmente suficiente confiar somente na 
intuição. Isto aplica-se não somente na obtenção da solução de um problema, como também 
na avaliação do modelo que foi formulado para representar este problema. 
Curso de Pesquisa Operacional 12 
O critério indicado para julgar a validade de um modelo é verificar se ele prediz ou não os 
efeitos relativos das linhas de ação alternativas com suficiente precisão de maneira a permitir 
uma satisfatória decisão. Devido à dificuldade de comunicar e relacionar todos os aspectos e 
sutilezas de um problema operacional complexo, existe a possibilidade que a equipe de 
pesquisas operacionais ou não tenha considerado todos os aspectos relevantes da situação ou 
não os tenha interpretado apropriadamente. 
Antes de aplicar testes mais elaborados é conveniente verificar se o modelo não apresenta 
erro. Um novo exame na formulação do problema e sua comparação com o modelo pode 
revelar alguns desses erros. Outra verificação muito usada consiste em verificar se todas as 
expressões matemáticas estão dimensionalmente corretas. 
Finalmente, ou a equipe de PO, ou o pessoal que deverá tomar decisões podem observar 
detalhes na solução obtida que surgiram particulares omissões ou erros no modelo. Outros 
procedimentos mais sistemáticos podem ainda ser empregados. 
 
2.6 Estabelecimento de controle sobre a Solução 
Quando uma solução for usada repetidamente, esta solução só permanecerá válida para o 
problema real enquanto o modelo respectivo permanecer válido. Entretanto, as condições 
variam constantemente no caso real. Em conseqüência, se essas variações invalidarem o 
modelo, é vital que isto seja verificado tão cedo quanto possível de maneira que o modelo, sua 
solução e resultante linha de ação possa ser convenientemente modificada. Assim sendo, 
sempre que uma solução e resultante estratégia para um ação futura são aplicadas 
repetidamente, esta solução deve ser mantida sob controle. 
Este controle é feito identificando-se os parâmetros críticos, determinando-se estatisticamente 
as variações relevantes nesses parâmetros e finalmente ajustando a solução e conseqüente 
linha de ação sempre que uma variação é observada. 
 
2.7 Implantação da solução 
A última fase de um estudo de pesquisa operacional consiste em implantar a solução final. 
Esta fase é critica porque aqui, porque aqui, os benefícios do estudo são obtidos. Em 
conseqüência é importante para a equipe de PO participar do desenvolvimento desta fase, não 
só para assegurar-se que a solução é corretamente transformada em um procedimento 
operacional como também para corrigir qualquer imperfeição descoberto na solução. 
 
Curso de Pesquisa Operacional 13 
2.8 Conclusão 
Os problemas de PO tem as seguintes características: 
1) Compilação de dados anteriores, relativos a operações de produção, vendas ou outros 
setores da empresa; 
2) Análise dos dados colhidos através de técnicas estatísticas; 
3) Criação do modelo matemático destinado a previsão e decisão no tocante as mesmas 
operações no futuro. 
 
O curso baseia-se na aplicação da PO a uma grande variedade de problemas que podem ser 
representados por um pequeno número de problemas típicos. 
 
2.9 Métodos e Modelos da PO: 
Os métodos mais comuns que são usados no âmbito da PO são: 
1. Teoria da decisão; 
2. Modelos seqüenciais (seqüência e coordenação); 
3. Modelos de alocação; 
4. Modelos de designação; 
5. Modelos de competição; 
6. Técnicas clássicas de otimização; 
7. Modelos de substituição (reposição); 
8. Modelos de estoque (teoria dos estoques); 
9. Modelos de filas; 
10. Técnicas de simulação; 
11. Modelos de programação dinâmica; 
12. Modelos de rotas; 
13. Métodos – heurísticos. 
 
Curso de Pesquisa Operacional 14 
3 - TIPOS BÁSICOS DE MODELO DE PO 
3.1 Teoria da Decisão 
A característica essencial da Teoria da Decisão é que as conseqüências dos cursos de ação são 
geralmente desconhecidas. Nestesexemplos (casos), probabilidades são associadas com os 
vários estados do sistema. Dependendo das informações que se sabe dos estados do sistema, 
não pode-se referir à decisão fazendo-a sob certeza, risco, ou incerteza. A maioria dos 
problemas de negócios trata com a última condição. Um caminho adicional de predizer o 
futuro, embora somente um mínimo de informações são estimadas é através da estatística 
Bayesiana. 
 
3.2 Modelo de Sequenciamento 
Modelos sequenciais envolvem a determinação da seqüência ótima para um conjunto de 
tarefas ou eventos ou a melhor seqüência para atendimento de clientes com o objetivo de 
minimizar o tempo total e custos. Esta técnica é aplicada à pesquisa e desenvolvimento, 
construção, planejamento de novos produtos. Por exemplo, o procedimento para uma rede de 
análise de PERT. Outros problemas sequenciais tais como programação de máquinas são 
resolvidos pela aplicação de técnicas de simulação e heurísticas. 
 
3.3 Modelos de Alocação 
Quando existe um número de atividades para serem realizadas, caminhos alternativos de fazê-
las, e recursos limitados ou meios para executar cada atividade na melhor linha eficaz, há um 
problema de alocação destes recursos escassos. O problema é combinar as atividades e os 
recursos de uma maneira ótima para que toda eficiência seja maximizada, isto é, o lucro é 
máximo e os custos são mínimos. Isto é conhecido como "programação matemática". 
Quando as restrições são expressas como equações lineares, é chamada "programação linear". 
Se uma das restrições não é linear é denominada "programação não linear". A Teoria da 
Dualidade da programação linear estabelece a relação entre duas diferentes formulações do 
mesmo problema. Em adição aos programas lineares e não lineares, existem outros tipos de 
programações - inteira, quadrática, convexa, estocástica, decisão, paramétrica e dinâmica. 
Elas diferem na espécie dos dados e podem ser manipulados de acordo com as suposições 
feitas. 
 
Curso de Pesquisa Operacional 15 
3.4 Modelos de Designação 
O mais simples tipo de modelo de alocação envolve a distribuição de um numero de tarefas 
para o mesmo numero de recursos (homens). Isto é chamado um problema de designação 
(atribuição). 
Este tipo de problema torna-se mais complexo se alguma das tarefas requer mais que um 
recurso e se os recursos podem ser usados para mais de uma tarefa. Um exemplo disto é o 
problema de transportes. 
 
3.5 Modelos de Competição 
A teoria dos jogos dá um conceito estrutural dentro do qual a maioria dos problemas de 
competição podem ser formulados. Ela tem sido usada efetivamente pelos negócios 
(transações comerciais) para desenvolver estratégias de publicidade, políticas de preços, e 
escolha do momento oportuno (senso de oportunidade, timming) para introdução de novos 
produtos. A teoria estatística da decisão e simulação tem sido empregadas com sucesso nos 
jogos. 
O processo de Markov é um método de predizer variações competitivas no tempo de clientes 
fieis a uma marca (determinado produto) e cotas atuais de mercado são conhecidas. 
 
3.6 Técnicas de Otimização Clássicas 
Às técnicas de otimização clássica ou tradicional são associadas com o procedimento de 
cálculo do máximo ou mínimo. Resumidamente, quando uma característica pode ser 
representada por uma equação a uma variável que pode ser representada graficamente como 
uma curva continua uniforme, os valores de máximo e mínimo da curva podem ser obtidos 
pelo conjunto das primeiras derivadas iguais a zero. Então, o sinal algébrico da segunda 
derivada daquele conjunto de pontos são examinados para a obtenção de solução do 
problema. Quando dois parâmetros estão envolvidos, por exemplo, x e y para determinar a 
variável z, o máximo e mínimo podem ser encontrados pela aplicação de derivadas parciais 
num processo similar ao empregado para uma variável. As áreas de cálculo necessárias sao: 
diferenciação, integração, derivadas parciais, e os multiplicadores de Lagrange. Estas técnicas 
matemáticas as quais são aplicadas para otimização de problemas são capazes de diretamente 
selecionar a melhor decisão sem a necessidade de muitos passos interativos. 
 
Curso de Pesquisa Operacional 16 
3.7 Modelos de Reposição 
Problemas de reposição são geralmente de dois tipos: aqueles envolvendo itens que 
degeneram num período de tempo e aqueles que falham após um certo tempo de uso. 
O primeiro grupo refere-se ao ativo fixo das empresas - máquinas, caminhões e equipamentos 
- os quais são itens altamente custosos. Aqueles no segundo tipo são relativamente baratos – 
tubos de vácuo, pneumáticos, válvulas, tubos e itens semelhantes. 
A programação dinâmica é usada para obtenção das soluções do primeiro tipo. A teoria 
estatística amostral e probabilidade pode ser empregada na solução do segundo tipo. 
 
 
3.8 Modelos de Estoques 
Modelos de estoques são os que dizem respeito com duas decisões: quanto ordenar num 
determinado tempo e quando ordenar esta quantidade para minimizar o custo total. Custo de 
movimentação, custos de ordens de armazenamento (estocagens), e custo de deficits são 
determinados assim como uma medida de efetividade dos custos (modelo) podendo ser 
usados pelos gerentes para selecionar um balanço apropriado entre custos e deficits. À decisão 
pelo critério do mínimo custo pode também ser obtida pelo cálculo, teoria de probabilidades, 
programação dinâmica e simulação pelo computador. 
 
3.9 Modelos de Filas 
Filas, algumas vezes referida como teoria das linhas de espera, trata (diz respeito) com 
chegadas uniformes ou aleatórias num serviço ou meios de processamento de capacidade 
limitada. 
O objetivo deste modelo é permitir determinar se o número ótimo de pessoas ou meios 
necessários para servir clientes quando considerando o custo do serviço e o custo de espera. 
Um problema de estoque pode ser visto como um problema de filas. Itens em estoque podem 
ser considerados como um meio de serviço ocioso esperando por clientes. À demanda pelo 
estoque é uma chegada para serviço e a saída do estoque pode ser considerada como uma fila 
de clientes A teoria das filas faz uso da teoria das probabilidades e cálculo. 
 
 
 
Curso de Pesquisa Operacional 17 
3.10 Técnicas de Simulação 
Simulação presta-se ao emprego dos computadores, gera fatores como potencial de vendas ou 
atrasos na expedição pelo exame de tabelas de números aleatórios que são essenciais aos 
programas. 
O computador mostra a saída de resultados que (poderiam) teriam sido obtidos se o critério de 
decisão tivesse sido usado. Números aleatórios são usados para simular chegadas e tempo de 
serviços. 
 
3.11 Modelos de Programação Dinâmica 
A maioria dos problemas de programação dinâmica requer o uso de um computador para 
manipular a grande quantidade de dados (informações). Os modelos de programação 
dinâmica são extremamente usados para processo que se estende por vários períodos de tempo 
ou eventos. Ao invés de otimizar cada decisão como ela ocorre a programação dinâmica leva 
em consideração os efeitos da decisão de hoje nos futuros períodos de tempo. 
 
3.12 Modelos de Rotas 
Um dos mais famosos problemas de rota é o do "Caixeiro Viajante". O objetivo é selecionar o 
caminho (itinerário que parte de sua própria cidade, passa através de cidades apenas uma vez, 
e retorna para sua cidade, pela menor distância em termos de tempo ou dinheiro. O modelo de 
rotas tem sido aplicado à produção onde o número de produtos ou itens produzidos 
(fabricados) é análogo ao de cidades. Troca-se os custos de produção correspondentes aos 
custos de viagens entre cidades. 
 
3.13 Métodos heurísticos 
Métodos heurísticos indicam aprendizado ou avaliação de sistemas. Os métodos heurísticos 
usam regras de manusear e avaliar, instruídos para explorar o caminho mais provável para se 
chegar a uma conclusão. Isto recoloca em check todas as alternativas (também para muitasquantidades aproximadas) para encontrar a melhor solução. 
 
Curso de Pesquisa Operacional 18 
4 - INTRODUÇÃO A PROGRAMAÇÃO LINEAR 
4.1 GENERALIDADES 
Sem dúvida nenhuma a Programação Linear é uma das técnicas da Pesquisa Operacional das 
mais utilizadas em se tratando de problemas de otimização. 
Os problemas de Programação Linear (PL) buscam a distribuição eficiente de recursos 
limitados para atender um determinado objetivo, em geral, maximizar lucros ou minimizar 
custos. Em se tratando de PL, esse objetivo é expresso através de uma função linear, 
denominada de "Função Objetivo". 
É necessário também que se defina quais as atividades que consomem recursos e em que 
proporções os mesmos são consumidos. Essas informações são apresentadas em forma de 
equações as inequações lineares, uma para cada recurso. Ao conjunto dessas equações e/ou 
inequações, denomina-se "Restrições do Modelo". 
Normalmente se tem inúmeras maneiras de distribuir os recursos escassos entre as diversas 
atividades em estudo, bastando para com isso que essas distribuições estejam coerentes com 
as restrições do modelo. No entanto, o que se busca, num problema PL é a função objetivo, 
isto é, a maximização do lucro ou a minimização dos custos. A essa solução dá-se o nome de 
solução ótima. 
Assim, a Programação linear se incube de achar a solução ótima de um problema, uma vez 
definida o modelo linear, ou seja, a função objetivo e as restrições lineares. 
 
4.2 PROBLEMAS DE PROGRAMAÇÃO LINEAR 
Como foi dito anteriormente, está-se diante de um problema de PL quando os problemas 
práticos que se pretende resolver pode ser escrito de forma de maximização (ou minimização) 
de uma função objetivo linear, sujeita a um conjunto de restrições que podem ser expressos 
sob a forma de inequações ou equações lineares. 
 
Exemplos de problemas que podem ser resolvidos por 
programação linear: 
a) Um fabricante está iniciando a última semana de produção de quatro diferentes modelos de 
consoles em madeira para aparelhos de televisão, designados respectivamente, I, II, III e IV. 
Cada um deles deve ser montado e em seguida decorado. Os modelos necessitam, 
respectivamente de 4, 5, 3 e 5 horas para montagem e de 2, 1, 5, 3 e 3 horas para decoração. 
Os lucros sobre as vendas dos modelos são respectivamente 7, 7, 6 e 9 reais. O fabricante 
Curso de Pesquisa Operacional 19 
dispõe de 30.000 horas para a montagem destes produtos (750 montadores trabalhando 40 
horas por semana) e de 20.000 horas para decoração (500 decoradores trabalhando 40 horas 
por semana). Quanto de cada um dos modelos deve ser produzido durante esta última semana 
a fim de maximizar o lucro? Admita que todas as unidades possam ser vendidas. 
 
b) Seja o caso de um investidor que, dispondo de $6000 esteja contemplando a possibilidade 
de compra de dois seguintes tipos de ações: 
 
Tipo 1 - preço unitário de compra de $ 5,00 e rentabilidade anual esperada de 30%. 
Tipo 2 - preço unitário de compra de $ 3,00 e rentabilidade anual estimada em 35%. 
 
Supondo que o investidor não deseje adquirir mais do que 1750 ações, e que seu corretor só 
possa conseguir 1000 ações do tipo 1 e 1500 ações do tipo 2, que quantidades deve comprar 
de cada tipo de ação, na hipótese de que seja seu objetivo maximizar o total de capital no fim 
de um ano? 
 
c) Uma empresa esta analisando um conjunto de alternativas de projetos de investimentos 
disponíveis e apresentados na tabela seguir. 
 
Projeto Investimento no 
ano 1 
Investimento no 
ano 2 
Vida útil Economia anual 
nos próximos 3 
anos 
1 12 3 5 anos 9.29 
2 54 7 5 anos 26.85 
3 6 6 5 anos 9.88 
4 6 2 5 anos 7.92 
5 30 35 5 anos 35.33 
6 6 6 5 anos 8.14 
7 48 4 5 anos 22.78 
8 36 3 5 anos 16.91 
9 18 2 5 anos 11.04 
 
O orçamento para investimento é de 50 para o primeiro ano e 20 para o segundo. Sabendo-se 
que a TMA da empresa é de 10% a.a., qual a combinação ótima desses projetos. 
 
 
 
Curso de Pesquisa Operacional 20 
4.3 OBTENDO FUNÇÃO OBJETIVO E AS RESTRIÇÕES 
Antes de discutir as técnicas possíveis para obtenção de resultados, através de um problema 
será discutido como obter a função objetivo e as restrições. 
 
4.3.1 Exemplo para discutir a obtenção da função objetivo e 
as restrições: 
Giapetto fabrica dois tipos de brinquedos de madeira: soldados e trens. Um soldado é vendido 
por $27 e usa $10 de matéria prima. Cada soldado que é fabricado tem um custo adicional de 
$14 relativo a mão de obra. Um trem é vendido por $21 e gasta $9 de matéria prima. O custo 
de mão de obra adicional para cada trem é de $10. A fabricação destes brinquedos requer dois 
tipos de mão de obra: carpintaria e acabamento. Um soldado necessita de 2 horas para 
acabamento e 1 de carpintaria. Um trem necessita de 1 hora para acabamento e 1 hora de 
carpintaria. Cada semana, Giapetto pode obter qualquer quantidade de matéria prima, mas tem 
a disposição até 100 horas de acabamento e 80 de carpintaria. A demanda por trens é 
ilimitada, mas a venda de soldados é de no máximo 40 por semana. Giapetto quer maximizar 
seu lucro diário (receitas-custos). Formular o modelo matemático que poderá ser usado por 
Giapetto para maximizar seu lucro semanal. 
Solução: 
Sabendo que a matéria prima
necessária é obtida sem problemas,
Giapetto tem como objetivo
maximizar o lucro semanal (receitas -
custos).
Vamos então formular
matematicamente a situação de
Giapetto com o objetivo de maximizar
o lucro semanal.
 
 
 
Curso de Pesquisa Operacional 21 
Primeiro ponto importante:
Variáveis de decisão
Em qualquer modelo de PL, as variáveis
de decisão devem descrever
completamente as decisões a serem
feitas.
Caso de Giapetto: quantos soldados e trens
devem ser feitos na semana.
 
 
Variáveis de decisão
• X1 = número de soldados produzidos
cada semana;
• X2 = número de trens produzidos a cada
semana.
 
 
Segundo ponto importante:
Função objetivo
Em qualquer modelo de PL, o decisor
quer maximizar ou minimizar alguma
função das variáveis de decisão.
Caso de Giapetto: custos fixos (aluguel,
seguro) não depende dos valores de X1
e X2, assim ele pode se concentrar em
maximizar a venda da semana.
 
Curso de Pesquisa Operacional 22 
Receitas e custos: podem ser expressos em
termos das variáveis X1 e X2. Seria tolice
Giapetto produzir mais soldados que ele possa
vender, assim assumimos que todos
brinquedos produzidos podem ser vendidos.
Assim:
Receita da semana = receita dos soldados +
receita dos trens
Receita da semana = $/soldado * soldado/semana + $/trem * trem/semana
Receita por semana = 27*X1 + 21*X2
 
 
Também podemos escrever:
• Custos de M.P. = 10*X1 + 9*X2
• Custos de M.O. = 14*X1 + 10*X2
Então Giapetto quer maximizar:
(27X1 + 21X2) - (10X1 + 9X2) - (14X1 + 10 X2) = 3X1 + 2X2
Assim o objetivo de Giapetto é escolher X1 e X2 para 
maximizar 3X1 + 2X2
 
Objetivo:
maximizar Z = 3X1 + 2X2
ou
max Z = 3X1 + 2X2
Variável
usualmente
utilizada
 
Curso de Pesquisa Operacional 23 
Terceiro ponto importante:
restrições
Se X1 e X2 aumentam, a função objetivo de
Giapetto será sempre maior. Mas infelizmente X1
e X2 são limitados pelas seguintes restrições:
• 1 - cada semana, não mais que 100 horas de
acabamento;
• 2 - cada semana, não mais de 80 horas de
carpintaria;
• 3 - limitação de demanda, não mais de 40
soldados por semana.
 
 
M.P. ilimitada, portanto não há
restrições. Como, próximo
passo, é necessário expressar as
restrições 1, 2 e 3, em termo das
variáveis de decisão: X1 eX2.
 
 
Restrição 1:
não mais de 100 h de acabamento
Total de h de acab./semana = horas de aca./sold. * sold. feitos/semana + 
horas de acab./trem * trens feitos/semana
Total de h de acab./semana = 2*X1 + 1*X2
Restrição 1 - 2X1 + X2 <= 100
 
Curso de Pesquisa Operacional 24 
Restrição 2:
não mais de 80 h de carpintaria
Total de h de carp./semana = horas de carp./sold. * sold. feitos/semana + 
horas de carp./trem * trens feitos/semanaTotal de h de carp./semana = 1*X1 + 1*X2
Restrição 2 - 1X1 + X2 <= 80
 
 
Restrição 3:
venda máxima de soldados: 40
Restrição 3 - X1 <= 40
 
 
Restrições:Restrições:
• 1 - 2X1 + X2 <= 100
• 2 - X1 + X2 <= 80
• 3 - X1 <= 40
Restrições para o
problema de PL
de Giapetto
Usualmente
representam a
quantidade de
recursos
disponíveis.
Coeficientes 
tecnológicos:
refletem a quantia
usada para
diferentes produtos.
 
Curso de Pesquisa Operacional 25 
Quarto ponto importante:
Restrições adicionais
Para completar a formulação do problema:
• X1 >= 0
• X2 >= 0
 
 
Resumindo
• max Z = 3X1 + 2X2 (1)
sujeito a:
• 2X1 + X2 <= 100 (2)
• X1 + X2 <= 80 (3)
• X1<= 40 (4)
• X1 >= 0 (5)
• X2 >= 0 (6)
Significa que
X1 e X2 
precisam satisfazer
todas as restrições P.L. - todos os
termos X são de
expoente 1 e as
restrições são
inequações
lineares
O problema de Giapetto
é tipico de muitos outros,
onde precisa-se
maximizar lucros
sujeitos a recursos
limitados
 
 
 
4.3.2 EXEMPLOS - Obter a formulação matemática 
para alguns casos 
1) Uma determinada empresa automobilística fabrica carros de luxos e caminhonetes. A 
empresa acredita que os mais prováveis clientes são homens e mulheres com altos 
rendimentos. Para abordar estes grupos, a empresa decidiu por uma campanha de propagandas 
na TV, e comprou 1 minuto do tempo de comercial de 2 tipos de programa: comédia e 
transmissão de futebol. Cada comercial durante o programa de comédias é visto por 7 milhões 
de mulheres e 2 milhões de homens com grande poder aquisitivo. Cada comercial durante a 
transmissão de futebol é visto por 2 milhões de mulheres e 12 milhões de homens com grande 
poder aquisitivo. Um minuto de comercial durante o programa de comédias custa $50000, e 
Curso de Pesquisa Operacional 26 
durante a transmissão de futebol $100000. A empresa gostaria que pelo menos 28 milhões de 
mulheres e 24 milhões de homens de grande poder aquisitivo assistissem sua propaganda. 
Obter a programação matemática que irá permitir a empresa atender as suas necessidades de 
propaganda a um mínimo custo. 
 
2) Uma empresa fabrica carros e caminhonetes. Cada veículo precisa ser trabalhado nas 
seções de pintura e montagem. Se a seção de pinturas trabalhar só com caminhonetes, 40 por 
dia podem ser pintados. Se estiver trabalhando só com carros, 60 por dia é sua capacidade. Se 
a seção de montagem estiver trabalhando só com caminhonetes, 50 podem ser montados por 
dia. O mesmo número é possível para carros se este for o único produto na linha. Cada 
caminhonete contribui $300 para o lucro, e cada carro $200. Obter a formulação matemática 
que determinará a programação de produção que maximizará o lucro da empresa. 
 
3) Supondo que a empresa do exemplo anterior, por necessidades dos vendedores, tem de 
produzir pelo menos 30 caminhonetes e 20 carros diariamente, qual será a nova formulação 
do problema? 
 
4.4 SOLUÇÃO DE UM PROBLEMA DE P.L. - MÉTODO 
GRÁFICO 
Um problema de P.L. só pode ser resolvido graficamente desde que o modelo, em estudo, 
apresentar duas variáveis. 
O fato de que a função objetivo
para um PL precisar ser uma
função linear de variáveis tem
2 implicações:
• 1 - A contribuição para a função objetivo
de cada variável de decisão é proporcinal
ao valor da variável de decisão;
• 2 - A contribuição para a função objetivo
para cada variável é independente dos
valores de outras variáveis de decisão.
 
Curso de Pesquisa Operacional 27 
Definição: região de solução
- para um problema de PL é
o conjunto de todos os
pontos que satisfazem todas
as restrições do problema.
 
 
Restrições:
• 2X1 + X2 <= 100 (2), ok 2*40+20<=100
• X1 + X2 <= 80 (3), ok 40+20<=80
• X1<= 40 (4), ok 40<=40
• X1 >= 0 (5), ok 40>=0
• X2 >= 0 (6), ok 20>=0
Giapetto: X1 = 40 X2 = 20 região de solução
 
 
Giapetto: X1 = 15 X2 = 70 não é região de solução
Restrições:
• 2X1 + X2 <= 100 (2), ok 2*15+70<=100
• X1 + X2 <= 80 (3), não ok 15+70> 80
• X1<= 40 (4), ok 15<=40
• X1 >= 0 (5), ok 15>=0
• X2 >= 0 (6), ok 70>=0
 
 
 
Curso de Pesquisa Operacional 28 
região de solução
Pontos que atendem e onde será procurada
a solução ótima
Solução ótima
Ponto da região de solução, que leva ao maior
valor da função objetivo.
 
 
• A maioria dos problemas de PL, tem
somente uma solução ótima;
• Alguns não tem solução ótima;
• Alguns tem infinitas soluções.
Para o problema de Giapetto, solução ótima:
X1=20 e X2 = 60
Z = 3*20 +2*60 = 180
lucro = 180 - 100 = 80/semana
 
 
Solução gráfica para o
problema de 2 variáveis
Um PL com 2 variáveis
pode ser resolvido
graficamente. Nós sempre
nomeamos as variáveis X1
e X2 e os eixos
coordenados por X1 e X2.
 
 
 
Curso de Pesquisa Operacional 29 
Se nós queremos delimitar em
um gráfico o conjunto de
pontos que satisfaça a:
2X1+3X2 <= 6 (1)
3X2 <= 6 - 2X1
X2<=1/3*(6 - 2X1) = 2 - 2/3X1 (2)
 
 
 
O conjunto de pontos que satisfaz (1) e
(2) cai sobre a reta ou abaixo dela
X2
X11
2
3
4
5
6
1 2 3 4 5 6
X2 = 2 - 2/3X1
Região onde:
2X1+3X2<=60
Região onde:
2X1+3X2>=60
 
 
A solução gráfica para o problema de Giapetto é a seguinte: 
Encontrando a região de solução
do problema de Giapetto:
• 2X1 + X2 <= 100 (2)
• X1 + X2 <= 80 (3)
• X1<= 40 (4)
• X1 >= 0 (5)
• X2 >= 0 (6)
Para um 
ponto (X1, X2)
pertencer a região de
solução é preciso
satisfazer todas
estas inequações.
(5) e (6) indicam o primeiro quadrante
 
Curso de Pesquisa Operacional 30 
X2
X120
40
60
80
100
120
20 40 60 80 100 120
(2)
(3)
(4)
A
B
C
D
E
F
G
H
Poligono DGFEH - região de solução
 
 
Encontrando a solução ótima
Após a identificação da região de
solução, nós devemos procurar a
solução ótima, que será o ponto da
região que levar ao maior valor de
Z = 3X1+2X2
 
 
Para encontrar a solução ótima, nós
precisamos desenhar uma linha sobra
a qual todos os pontos levem ao mesmo
valor de Z.
Escolhe-se qualquer ponto da região de
solução:
(20, 0) - Z = 3X1+2X2 = 60
Assim (20, 0) cai sobre a reta:
Z = 3X1 + 2X2 = 60
X2 = 30 - 3/2X1
 
 
Curso de Pesquisa Operacional 31 
3X1 + 2X2 = 60
tem coeficiente angular = -3/2
Assim todas as retas 3X1+2X2 =
constante terão o mesmo coeficiente
angular.
Importante: uma vez desenhada a reta, 
podemos encontrar
todas as outras pelo movimento paralelo da reta
que desenhamos.
 
 
X2
X120
40
60
80
100
120
20 40 60 80 100 120
(4)(2)
(3)
A
B
C
D
E
F
G
H
X2 = 30 - 3/2 X1
Indica o ponto ótimo - G (20, 60)
 
 
Ponto ótimo:
Z = 3*20 + 2*60 = 180
 
 
 
 
Curso de Pesquisa Operacional 32 
Resolver graficamente os exercícios 1, 2 e 3, formulados anteriormente no item 4.3, e as 
seguintes formulações: 
1) max Z = 5X1 +2X2 
sujeito a: 
X1 ≤ 3 
X2 ≤ 4 
X1 + 2X2 ≤ 9 
X1 ≥ 0 
X2 ≥ 0 
2) max Z = 2X1 -1X2 
sujeito a: 
X1 – X2 ≤ 1 
2X1 + X2 ≥ 6 
X1 ≥ 0 
X2 ≥ 0 
 
 
Pela discussão apresentada neste item, foi visto que um problema de PL com duas variáveis, 
necessariamente cairá em um dos 4 casos possíveis, sendo eles: 
 
1) Caso 1: a formulação tem solução única; 
2) Caso 2: a formulação tem múltiplas soluções; 
3) Caso 3: a formulação não tem solução; 
4) Caso 4: a formulação não tem fronteira, a região de solução permite arbitrários valores 
para Z (grandes valores de Z, para problemas de max, e pequenos valores de Z, para 
problemas de min). 
 
E qualquer outra formulação, com maior número de variáveis, também sempre se enquadrará 
em um destes casos. 
 
 
 
 
Curso de Pesquisa Operacional 33 
4.5 PROBLEMAS INTERESSANTES QUE PODEM SER 
FORMULADOS PARA SEREM RESOLVIDOS POR 
PROGRAMAÇÃO LINEAR 
 
O que será visto a seguir é a formulação devários problemas complicados da Programação 
Linear. O passo mais importante na formulação de um modelo é a escolha apropriada das 
variáveis de decisão. Se as variáveis de decisão forem selecionadas adequadamente, a função 
objetivo e as restrições devem ser obtidas sem muita dificuldade. Problemas na determinação 
da função objetivo e restrições normalmente é devido a uma escolha incorreta das variáveis de 
decisão. 
 
4.5.1 Exemplo 1: Problema de programação do trabalho 
Muitas aplicações de programação linear envolvem determinar o mínimo custo e satisfazer as 
necessidades de número de trabalhadores necessários. O exemplo a seguir ilustra as 
características comuns para muitas destas aplicações. 
 
Uma empresa de entregas necessita de diferentes números de funcionários durante os 
diferentes dias da semana. Os números de funcionários necessários é mostrado na tabela a 
seguir. 
 Número de funcionários necessários 
Dia 1 = Segunda-feira 17 
Dia 2 = Terça-feira 13 
Dia 3 = Quarta-feira 15 
Dia 4 = Quinta-feira 19 
Dia 5 = Sexta-feira 14 
Dia 6 = Sábado 16 
Dia 7 = Domingo 11 
 
As leis do sindicado asseguram que os funcionários devem trabalhar 5 dias consecutivos e 2 
de folga. Por exemplo, um funcionário que trabalhou de Segunda a Sexta folga Sábado e 
Domingo. O escritório quer funcionar apenas com funcionários de tempo integral. Formular o 
problema de tal modo que a empresa possa minimizar o número de empregados de tempo 
integral que precisam ser contratados. 
 
4.5.2 Exemplo 2: Problema de orçamento de capital 
Uma empresa de petróleo esta considerando 5 diferentes oportunidades de investimento. O 
fluxo de caixa e valor presente (em milhões de reais) são dados na tabela a seguir. 
Curso de Pesquisa Operacional 34 
 
 Inv. 1 Inv. 2 Inv. 3 Inv. 4 Inv. 5 
Desembolso 
instante 0 
11 53 5 5 29 
Desembolso 
instante 1 
3 6 5 1 34 
Valor 
presente 
13 16 16 14 39 
 
A empresa tem no momento $ 40 milhões para investir; e estima-se que no primeiro ano 
estarão disponíveis $ 20 milhões para investimento. A empresa pode comprar qualquer fração 
de cada investimento. Neste caso, o fluxo de caixa e valor presente são ajustados de acordo 
com a proporção do investimento realizado. Por exemplo, se a empresa comprar 1/5 do 
investimento 3, então o pagamento necessário será de 1/5 ($5) = $1 nos tempos 0 e 1. O valor 
presente do investimento 3 será de 1/5 (16) = $3.2 milhões. A empresa quer maximizar o 
valor presente que pode ser obtido pelos investimentos realizados entre as opções 1 a 5. 
Formular o problema para atingir este objetivo. Assumir que qualquer fundo não usado no 
instante 0 não poderá ser usado no primeiro ano (instante 1). 
 
4.5.3 Exemplo 3: planejamento financeiro de curto prazo 
Uma empresa eletrônica que fabrica gravadores e rádios, tem seus custos de mão de obra, 
matéria prima e preço de venda de cada produto discriminados na tabela a seguir. 
 
 Gravador Rádio 
Preço de venda 100 90 
Mão de obra 50 35 
Custo matéria prima 30 40 
 
Em primeiro de dezembro de 98, a empresa terá matéria prima que é suficiente para fabricar 
100 gravadores e 100 rádios. Na mesma data, o balancete previsto da empresa é o mostrado a 
seguir, e a razão entre ativo circulante e as suas obrigações (dívida com banco) será 2 
(20000/10000). 
 
Curso de Pesquisa Operacional 35 
 Ativo circulante Obrigações 
Caixa 10000 
Contas a receber 3000 
Estoques 7000 
Dívidas em bancos 10000 
 
A empresa precisa determinar quantos gravadores e rádios deverão produzidos em Dezembro. 
A demanda é alta o suficiente para garantir que todos os produtos fabricados serão vendidos. 
Todas as vendas são feitas a crédito, pagamentos por produtos fabricados em Dezembro não 
serão recebidos até primeiro de Fevereiro de 99. Durante Dezembro, a empresa irá receber 
$2000 e precisará pagar $1000 devido ao empréstimo bancário e $1000 referente ao seu 
aluguel. Em primeiro de janeiro de 99, a empresa receberá um carregamento de matéria prima 
no valor de $2000, que será pago em Fevereiro de 99. A gerência decidiu que em primeiro de 
janeiro de 99 precisa ter pelo menos $4000 em caixa. Também o banco exige que a razão 
entre dinheiro disponível e financiamento seja de pelo menos 2. Para maximizar o lucro da 
produção em Dezembro, o que deveria empresa produzir durante este mês? 
 
4.5.4 Exemplo 4: problema de Blending (mistura) 
Uma refinaria produz 3 tipos de gasolina (gasolina 1, gasolina 2 e gasolina 3). Cada tipo é 
produzida pela mistura de 3 tipos de petróleo (petróleo 1, petróleo 2 e petróleo 3). Os preços 
de venda por barril da gasolina e da compra de petróleo são: 
 
 Preço de venda por 
barril 
 Preço de compra por 
barril 
Gasolina 1 70 Petróleo 1 45 
Gasolina 2 60 Petróleo 2 35 
Gasolina 3 50 Petróleo 3 25 
 
A refinaria pode comprar até 5000 barris de cada tipo de petróleo por dia. Os 3 tipos de 
gasolina se diferem na octanagem e no enxofre presente. O petróleo misturado para fabricar a 
gasolina 1 precisa ter uma octanagem média de pelo menos 10 e conter quando muito 1% de 
enxofre. O petróleo misturado para fabricar a gasolina 2 precisa ter uma octanagem média de 
pelo menos 8 e conter quando muito 2% de enxofre. O petróleo misturado para fabricar a 
gasolina 3 precisa ter uma octanagem média de pelo menos 6 e conter quando muito 1% de 
enxofre. A taxa de octanagem e de enxofre que contém os 3 tipos de petróleo são as seguintes: 
 
 
Curso de Pesquisa Operacional 36 
 Octanagem Enxofre 
Petróleo 1 12 0.5% 
Petróleo 2 6 2% 
Petróleo 3 8 3% 
 
Custa $4 para transformar 1 barril de petróleo em 1 barril de gasolina, e a refinaria pode 
produzir até 14000 barris por dia. Os clientes da refinaria necessitam das seguintes quantias 
de cada tipo de gasolina: gasolina 1 – 3000 barris por dia; gasolina 2 – 2000 barris por dia; 
gasolina 3 – 1000 barris por dia. A empresa considera sua obrigação atender a estas 
demandas. A empresa também tem a opção de propagandas para estimular a demanda por 
seus produtos. Cada 1$ gasto diariamente em propaganda de um tipo particular de gasolina 
incrementa a demanda diária desta gasolina em 10 barris. Por exemplo, se a refinaria decide 
gastar $20 diariamente para divulgar a gasolina 2, o aumento da demanda diária desta 
gasolina será de 200 barris. Formular o problema para que a refinaria maximize seu lucro 
diário. 
 
Usando Programação Linear para resolver problemas 
de decisão multi períodos 
Até aqui, todas as formulações discutidas são exemplos estáticos, ou modelos de 1 período. 
Nos modelos estáticos, se assume que todas as decisões são feitas em um simples instante do 
tempo. Nos exemplos a seguir será mostrado como a Programação Linear pode ser usada para 
determinar decisões ótimas em multi períodos, ou modelos dinâmicos. Modelos dinâmicos 
aparecem quando o decisor toma decisões em mais de um ponto do tempo. Em um modelo 
dinâmico, decisões tomadas durante o período de tempo corrente influem em decisões de 
períodos futuros. Por exemplo, considere uma empresa que precisa determinar quantas 
unidades de um produto devem ser fabricadas cada mês. Se ele produzir uma quantidade 
grande no mês corrente, poderia reduzir o número de unidades a produzir nos meses futuros. 
Os 3 próximos exemplos ilustram como decisões iniciais afetam decisões posteriores. 
 
4.5.5 Exemplo 5: Um modelo de estoques 
Uma empresa de barcos precisa determinar quantos veleiros devem ser produzidos durante 
cada um dos 4 próximos trimestres. A demanda de cada um dos trimestres é: primeiro 
trimestre, 40 veleiros; segundo trimestre, 60 veleiros; terceiro trimestre, 75 veleiros; quarto 
trimestre, 25 veleiros. A empresa quer atender a demanda prontamente. No início do primeiro 
trimestre, a empresa tem 10 veleiros em estoque. No início de cada trimestre, a empresa 
Curso de Pesquisa Operacional 37 
precisa decidir quantos veleiros devem ser produzidos durante o trimestre.Por simplicidade, 
assume-se que os veleiros fabricados durante um trimestre podem ser usados para atender a 
demanda deste trimestre. Durante cada trimestre, a empresa pode produzir até 40 veleiros com 
sua mão de obra regular a um custo de $ 400 por veleiro. Tendo de trabalhar com horas extras 
durante o trimestre, a empresa pode produzir veleiros a mais a um custo total de $ 450 por 
barco. 
No final de cada trimestre (após ter ocorrido a produção e a demanda do trimestre ter sido 
atendida), um custo de transporte ou armazenagem de $ 20 por barco ocorre. Usar a 
programação linear para determinar a seqüência de produção para minimizar a soma dos 
custos de produção e estoques durante os 4 próximos trimestres. 
 
4.5.6 Exemplo 6: Modelos de financiamento multi período 
O exemplo a seguir ilustra como a programação linear pode ser usada para problemas de 
gerenciamento de fluxo de caixa. A chave é determinar as relações de dinheiro nas mãos 
durante diferentes períodos. 
 
Uma empresa de investimentos precisa determinar a estratégia de investimento para os 
próximos 3 anos. Atualmente a empresa tem $100.000 disponível para investir. Os 
investimentos A, B, C, D e E estão disponíveis. O fluxo de caixa associado com investir $1 
em cada opção é dado na tabela a seguir. 
 
 
 
 0 1 2 3 
A -$1 $0.50 $1 $0 
B $0 -$1 $0.50 $1 
C -$1 $1.2 $0 $0 
D -$1 $0 $0 $1.9 
E $0 $0 -$1 $1.5 
 
Por exemplo, 1$ investido na opção B requer um pagamento de $1 no ano 1 e retorna $0.50 
no ano 2 e $1 no ano 3. Para assegurar que o portifólio da empresa seja diversificado, a 
política da empresa é a de aplicar até $ 75.000 em um único investimento. Adicionalmente 
aos investimentos A-E, a empresa pode obter taxas de 8% ao ano mantendo o dinheiro não 
investido em fundos do mercado. Ganhos dos investimentos podem ser imediatamente 
Curso de Pesquisa Operacional 38 
reinvestidos. Por exemplo, o dinheiro recebido no ano 1 do investimento C pode ser 
imediatamente reinvestido na opção B. A empresa tem como diretriz não emprestar dinheiro 
de fundos, assim o dinheiro disponível para investimento a qualquer tempo é limitado ao 
disponível. Formular a programação linear que maximiza o dinheiro em mãos no ano 3. 
 
4.5.7 Exemplo 7: Programação de trabalho multi período 
Em exemplo anterior foi visto que a programação linear poderia ser usada para programar 
funcionários em um ambiente estático onde a demanda não se altera. O exemplo a seguir, 
mostra como a programação linear pode ser usada para programar treinamento para 
funcionários quando a empresa se depara com uma demanda que se altera. 
 
CLS é uma cadeia de lojas de serviços voltados para computadores. O número de horas de 
trabalho especializado que a CLS necessitará nos próximos 5 meses será: 
• Mês 1 (janeiro): 6000 horas; 
• Mês 2 (fevereiro): 7000 horas; 
• Mês 3 (março): 8000 horas; 
• Mês 4 (abril): 9500 horas; 
• Mês 5 (maio): 11000 horas. 
 
No início de Janeiro, 50 técnicos farão parte do quadro de funcionários da CLS. Cada técnico 
pode trabalhar até 160 horas por mês. Para atender futuras demandas, novos técnicos precisam 
ser treinados. É necessário um mês para se treinar um novo técnico. Durante o mês de 
treinamento, o novo funcionário precisa de ser supervisionado por um técnico experiente por 
50 horas. Cada técnico com experiência recebe $ 2000 por mês (mesmo se ele não trabalhar as 
160 horas). Durante o mês de treinamento, o novo funcionário recebe $ 1000 por mês. No 
final de cada mês, 5% dos técnicos experientes saem para se juntar a outra empresa de 
computadores. Formular o problema de tal modo que sua solução permitirá a CLS minimizar 
os custos relativos a pagamento de salários atendendo a programação prevista para os 
próximos 5 meses. 
 
 
 
Curso de Pesquisa Operacional 39 
4.6 SOLUÇÃO DE PROBLEMAS DE P.L. - MÉTODO 
SIMPLEX 
Nas formulações anteriores, problemas com mais de 2 variáveis não poderiam ser 
solucionados com o método gráfico. Desta forma é necessário o estudo de outro procedimento 
para a busca de soluções. 
Agora, será apresentado mais um procedimento geral para resolução de problemas de 
programação linear, denominado "Método Simplex" e que foi desenvolvido em1947 por 
George B. Dantzig. 
O método simplex é um método interativo (algoritmo) utilizado para achar, algebricamente, a 
solução ótima de um problema de P.L. . 
 
4.6.1 Teoremas Básicos 
Teorema 1 - O conjunto de todas as soluções compatíveis do modelo de programação linear é 
um conjunto convexo cujos vértices (pontos extremos) correspondem a soluções básicas 
viáveis. 
Teorema 2 - Se a função objetiva possui um máximo (mínimo) finito, então pelo menos uma 
solução ótima é um ponto extremo do conjunto convexo do teorema 1. 
 
4.6.2 Procedimentos do Método Simplex 
Supondo o seguinte problema para maximização: 
Max z = 5X1 + 2X2 
Sujeito a: 
X1 ≤ 3 
X2 ≤ 4 
X1 + 2X2 ≤ 9 
X1, X2 ≥ 0 
 
A solução gráfica do problema é a seguinte: 
 
 
 
 
 
 
Curso de Pesquisa Operacional 40 
 
 
 
 
 
 
 
 
 
 
 
 
Sabe-se que a solução ótima do modelo é uma solução compatível básica do sistema, ou seja, 
um ponto extremo do polígono ABCDE. 
O método simplex, para ser iniciado, necessita conhecer uma solução compatível básica 
(solução inicial) do sistema, isto é, um dos pontos A, B, C, D ou E do trapézio. Suponha-se 
que essa solução seja o ponto A. 
O método simplex verifica se a presente solução é ótima. Se for o processo está encerrado. Se 
não for ótima, é porque um dos pontos adjacentes fornece um valor maior que o ponto A. 
Neste caso, o método simplex faz então a mudança do ponto A para o ponto extremo 
adjacente que mais aumente o valor da função objetivo. No caso o ponto B. 
Agora, tudo que foi feito para o ponto extremo A é feito para o ponto extremo B. O processo 
finaliza quando se obtém um ponto extremo onde todos os pontos extremos a ele adjacentes, 
fornecem valores menores que a função objetivo. 
Como fazer, algebricamente, a mudança de um ponto extremo para outro, a ele adjacente? 
Achar, portanto, a próxima solução básica (ponto extremo adjacente) exige a escolha de uma 
variável básica para deixar a base atual, tornando-se não básica, e a escolha de uma variável 
não básica para entrar na base em sua substituição. 
 
O método simplex compreenderá, portanto, os seguintes passos: 
 
1. Achar uma solução compatível básica inicial. 
2. Verificar se o solução atual é ótima. Se for, pare. Caso contrário, siga para o passo III. 
3. Determinar a variável não-básica que deve entrar na base. 
4. Determinar a variável básica que deve sair da base. 
5. Achar a nova solução compatível básica, e voltar ao passo II 
Pontos extremos 
X2 
X1 
E(0, 4) 
D(1, 4) 
C(3, 3) 
A(0, 0) 
B(3, 0) A B C D E 
Z 
ZB = 15 
ZE = 8 
ZD = 13 
ZC = 24 
Curso de Pesquisa Operacional 41 
 
4.6.3 O Método Simplex 
A seguir será mostrado passo a passo o método simplex. 
 
Definição Geral de Programação Linear: 
Maximizar ou Minimizar Z = C 1X 1 + C2 X2 + .... + Cn Xn 
sujeito a: 
a11X1 + a12X1 + ..........+ a1nXn (≤ ou = ou ≥) b1 
a21X1 + a22X1 + ..........+ a2nXn (≤ ou = ou ≥) b2 
a31X1 + a32X1 + ..........+ a3nXn (≤ ou = ou ≥) b3 
 
am1X1 + am2X1 + ..........+ amnXn (≤ ou = ou ≥) bm 
 
X1, X2, X3, Xn ≥ 0 
 
O Método Simplex é aplicado diretamente quando: 
 
1. todas as restrições são ≤ bi 
2. todos os bi ≥ 0 
3. se quer maximizar Z 
 
Quando uma dessas condições não é atendida estamos em presença de um caso particular. 
O Método Simplex será estudado, acompanhando a seguinte formulação: 
 
 
Maximizar Z = 3x1 + 2x2 + 5x3 
Sujeito a 
x1+ 2x2 + x3 ≤ 430 
3x1 + 2x3 ≤ 460 
xl + 4x2 ≤ 420 
x1, x2, x3 ≥ 0 
 
Curso de Pesquisa Operacional 42 
Primeiro passo: Transformar o sistema de M desigualdades lineares restritivas em um 
sistema de M equações lineares. 
Para issoadiciona-se a cada uma das desigualdades uma variável não-negativa chamada 
“Variável de Folga". 
Obs: Tem-se tantas variáveis de folga quantos forem as restrições. 
 
Representação das Folgas = xn+1 , xn+2 , ... , xn+m. 
Assim temos: 
x1+ 2x2 + x3 + x4 = 430 
3x1 + 2x3 + x5 = 460 
xl + 4x2 + x6 = 420 
 
Segundo passo: Colocar as equações em forma de tabela 
Z - 3x1 - 2x2 - 5x3 = 0 
 x1+ 2x2 + x3 + x4 = 430 
 3x1 +2x3 + x5 = 460 
 xl + 4x2 + x6 = 420 
 
Terceiro passo: Determinar uma solução inicial viável. 
Pode ser demonstrado que a solução ótima de um problema de programação linear é uma 
solução básica. Uma solução básica para um sistema de M equações e N incógnitas. 
Possui M variáveis diferentes de O (zero) e (N - M) variáveis iguais a 0 (zero). As variáveis 
diferentes de 0 (zero) são chamadas "Variáveis Básicas" e aquelas iguais a 0 (zero) são as 
"Variáveis Não Básicas". 
No Método Simplex escolhe-se como variáveis básicas aquelas em cuja coluna aparece um 
valor igual a 1 e os demais iguais a 0 (zero). 
 
Quarto passo: verificar se a solução é ótima. 
Examinar os valores dos coeficientes das Variáveis não básicas na la linha (no exemplo, linha 
de Z) e concluir: 
a. Se todos os valores forem positivos a solução é ótima e única. 
b. Se aparecerem valores positivos e alguns nulos a solução é ótima mas não única. 
c. Se aparecer algum valor negativo a solução não é ótima. Deve-se, então executar o 5o 
passo. 
Curso de Pesquisa Operacional 43 
Como pode se verificar na tabela a seguir, existem números negativos na primeira linha, 
assim a solução não é ótima, e precisa-se continuar os passos do método. 
 
Base z X1 X2 X3 X4 X5 X6 b bi/aie equac. 
Z 1 -3 -2 -5 0 0 0 0 0 
X4 0 1 2 1 1 0 0 430 430 1 
X5 0 3 0 2 0 1 0 460 230 2 
X6 0 1 4 0 0 0 1 420 ind. 3 
 
 
Quinto passo: Determinar a variável que entra (xe ) 
A variável que entra deve satisfazer as seguintes condições: 
- ser igual a 0 (zero) na solução atual (ou seja deve ser não básica) 
- ter coeficiente menor ou igual a 0 (zero) na linha de Z (na la linha) 
- possuir em sua coluna, pelo menos um coeficiente positivo. Escolher para entrar na base 
aquela que apresentar, na linha de Z, o coeficiente negativo de maior valor absoluto. Marcar a 
coluna na tabela. 
 
Sexto passo: Determinar a variável que sai (xs). 
Calcula-se o valor de bi/aie para cada linha da tabela e escolhe-se para sair a variável para a 
qual o quociente tiver o menor valor não negativo. 
Marcar na matriz a linha de xs. O quinto e sexto passos podem ser vistos nesta tabela: 
 
 
 
 
 
Base z X1 X2 X3 X4 X5 X6 b bi/aie equac. 
Z 1 -3 -2 -5 0 0 0 0 0 
X4 0 1 2 1 1 0 0 430 430 1 
X5 0 3 0 2 0 1 0 460 230 2 
X6 0 1 4 0 0 0 1 420 ind. 3 
 
 
 
Sétimo passo: Calcular a nova matriz de coeficientes, executando as operações convenientes 
nas linhas da matriz. 
Os coeficientes da nova matriz podem ser calculados da seguinte maneira: 
 
10 - Dividir todos os elementos da linha marcada pelo pivô (esta linha não muda mais). 
entra 
sai Pivô 
Curso de Pesquisa Operacional 44 
20 - Multiplicar a linha marcada pelo fator Fi= aie / ase 
Subtrair a linha i da matriz, da linha marcada e multiplicada pelo fator Fi. 
30 - Substituir na coluna base a variável que sai pela variável que entra. 
O resultado destas operações na tabela anterior resulta em: 
 
 
 
Base z X1 X2 X3 X4 X5 X6 b bi/aie equac. 
Z 1 4.5 -2 0 0 2.5 0 1150 0 
X4 0 -0.5 2 0 1 -0.5 0 200 100 1 
X3 0 1.5 0 1 0 0.5 0 230 ind. 2 
X6 0 1 4 0 0 0 1 420 105 3 
 
 
Como na primeira linha da coluna de X2 aparece um número negativo, a solução ainda não é a 
ótima. 
 
Oitavo passo: Repetir todos os passos, do 40 ao 70, tantas vezes quanto forem necessárias, até 
que a solução ótima seja encontrada. O resultado final da tabela anterior aparece na próxima 
iteração, e como não existem mais números negativos na primeira linha a solução é ótima. O 
resultado é mostrado a seguir. 
 
 
Base z X1 X2 X3 X4 X5 X6 b bi/aie equac. 
Z 1 4 0 0 1 2 0 1350 0 
X2 0 -0.25 1 0 0.5 -0.25 0 100 1 
X3 0 1.5 0 1 0 0.5 0 230 2 
X6 0 2 0 0 -2 1 1 20 3 
 
O máximo Z é 1350, para X2 = 100, X3 = 230 e X6 = 20. 
 
 
4.6.4 EXEMPLO - Resolver o problema do GIAPETTO pelo 
simplex. 
Curso de Pesquisa Operacional 45 
Resolvendo o problema de
Giapetto pelo simplex
• max Z = 3X1 + 2X2 (1)
sujeito a:
• 2X1 + X2 <= 100 (2)
• X1 + X2 <= 80 (3)
• X1<= 40 (4)
• X1 >= 0 (5)
• X2 >= 0 (6)
 
 
Primeiro passo importante:
converter o problema de PL na
forma canônica
• max Z = 3X1 + 2X2 (1)
sujeito a:
• 2X1 + X2 + X3 = 100 (2)
• X1 + X2 + X4 = 80 (3)
• X1 + X5 = 40 (4)
• X1, X2, X3, X4 e X5 >=0
 
 
• max Z = 3X1 + 2X2 (1)
sujeito a:
• 2X1 + X2 + X3 = 100 (2)
• X1 + X2 + X4 = 80 (3)
• X1 + X5 = 40 (4)
• X1, X2, X3, X4 e X5 >=0
Variáveis não básicas: X1 = X2 = 0
Variáveis básicas: X3 = 100 X4 = 80 X5 = 40
 
 
Curso de Pesquisa Operacional 46 
O problema pode ser representado assim:
Z X1 X2 X3 X4 X5 b Razão
Base 1 -3 -2 0 0 0 0 (1)
X3 0 2 1 1 0 0 100 (2)
X4 0 1 1 0 1 0 80 (3)
X5 0 1 0 0 0 1 40 (4)
Pivo
100/2=50
80/1=80
40/1=40
Indica que 
X1 entra no
lugar de X5
Solução parcial: (0, 0, 100, 80, 40)
Próximo quadro - Base: X3, X4 e X1
Devem se colocadas na forma canônica
 
 
Pivo
Z X1 X2 X3 X4 X5 b Razão
Base 1 0 -2 0 0 3 120 (1)+3(4) (1)
X3 0 0 1 1 0 -2 20 (2)-2(4) (2)
X4 0 0 1 0 1 -1 40 (3)-(4) (3)
X1 0 1 0 0 0 1 40 (4) (4)
Ainda não é a 
solução ótima
20/1=20
40/1=40
40/0
Indica que 
X2 entra no
lugar de X3
Solução parcial: (40, 0, 20, 40, 0)
Próximo quadro - Base: X2, X4 e X1
Devem se colocadas na forma canônica
 
 
Ainda não é a 
solução ótima Pivo
-10
20
40
Indica que 
X5 entra no
lugar de X4
Solução parcial: (40, 20, 0, 20, 0)
Próximo quadro - Base: X2, X5 e X1
Devem se colocadas na forma canônica
Z X1 X2 X3 X4 X5 b Razão
Base 1 0 0 2 0 -1 160 (1)+2(2) (1)
X2 0 0 1 1 0 -2 20 (2) (2)
X4 0 0 0 -1 1 1 20 (3)-(2) (3)
X1 0 1 0 0 0 1 40 (4) (4)
 
 
Curso de Pesquisa Operacional 47 
solução é ótima
Z X1 X2 X3 X4 X5 b Razão
Base 1 0 0 1 1 0 180 (1)+(3) (1)
X2 0 0 1 -1 2 0 60 (2)+2(3) (2)
X5 0 0 0 -1 1 1 20 (3) (3)
X1 0 1 0 1 -1 0 20 (4)-(3) (4)
Valor máximo possível
para a função objetivo
Solução ótima: (20, 60, 0, 0, 20)
A restrição 4 tem um folga de 20
 
 
• max Z = 3X1 + 2X2 (1)
sujeito a:
• 2X1 + X2 + X3 = 100 (2)
• X1 + X2 + X4 = 80 (3)
• X1 + X5 = 40 (4)
• X1, X2, X3, X4 e X5 >=0
Solução do problema de
Giapetto pelo simplex
Solução ótima: (20, 60, 0, 0, 20) Z = 3*20 + 2*60 = 180
A restrição 4 tem um folga de 20
 
 
Resolver pelo Simplex a seguinte formulação: 
max Z = 5X1 +2X2 
sujeito a: 
X1 ≤ 3 
X2 ≤ 4 
X1 + 2X2 ≤ 9 
X1 ≥ 0 
X2 ≥ 0 
 
 
4.6.5 Procedimento para minimizar Z 
Se as variáveis de decisão forem os custos, por exemplo, nosso objetivo será minimizá-lo. 
Curso de Pesquisa Operacional 48 
O método empregado na minimização é converter o problema em um equivalente, envolvendo 
maximização, procedendo-se, então da maneira usual do simplex. Esta conversão consiste em 
maximizar, negativamente, a função objetivo original. Então, se função objetivo (FO) tratar 
de minimizar Z, resolve-se o problema para máximo (-Z); isto é, troca-se o sinal da FO e 
mantém-se inalteradas as inequações (e/ou equações) resolvendo-se o problema de modo 
convencional. Determinado (-Z), troca-se seu sinal. 
Resolver pelo Simplex as seguintes formulações: 
1) min Z = 2X1 - 3X2 
sujeito a: 
X1 +X2 ≤ 4 
X1 - X2 ≤ 6 
X1 ≥ 0 
X2 ≥ 0 
2) min Z = 4X1 - X2 
sujeito a: 
2X1 + X2 ≤ 8 
X2 ≤ 5 
X1 - X2 ≤ 4 
X1 ≥ 0 
X2 ≥ 0 
 
4.7 O MÉTODO BIG M 
O Método simplex é explicado diretamente quando: 
1. Todas as restrições são ≤ bi 
2. Todos os bi ≥ 0 
3. Se quer maximizar Z 
 
Quando uma dessas condições não é satisfeita estamos em presença de um caso particular. 
 
4.7.1 Procedimento a aplicar quando as restrições são (≥≥≥≥) ou 
(=) bi, sendo todos os bi ≥≥≥≥ 0 
Obs: Sempre que os bi de alguma restrição for negativo, multiplicar a respectiva restrição por 
(-1). Exemplo: 
Curso de Pesquisa Operacional 49 
x1 - 4x2 + 2x3 ≤ - 23 ⇒ -x1 + 4x2 – 2x3 ≥ 23 
 
Quando as restrições são (≥) ou (=) a bi, não temos uma base, isto é, uma solução inicial, 
conforme mostrado Simplex. Neste caso, usa-se as técnicas (ou métodos): 
a) Método "Big M" ou "Método das penalidades"; 
b) Método das duas fases ou Método da função objetivo artificial. 
 
4.7.2 O método “Big M” 
Para empregar o método “Big M”, procede-se da seguinte maneira: 
1. Acrescenta-se as variáveis de folga as restrições do tipo (≥) ou (≤) para torná-las 
equações. No caso (≤ ) soma-se, no (≥) subtraí-se a variável de folga. 
2. No caso de restrições (≥) ou (=) a bi, bi ≥ 0; adiciona-se às restrições mais uma variável 
não negativa, chamada variável de artificial (X1a), uma para cada restrição que for 
necessária. A adição das variáveis artificiais às equações causa uma violação das 
respectivas restrições. Esta violação é contornada, assegurando-se que estas variáveis 
artificiais sejam iguais a zero na solução final. Isto é feito atribuindo-se uma penalidade 
muito grande para estas variáveis artificiais na função objetivo. Tal penalidade será 
designada por (-M) para os problemas de maximização, sendo M > 0. 
3. Substitui-se as variáveis artificiais da FO, pelo seu valor tirado das equações restritivas 
onde aparecem. 
4. Procede-se da maneira usual do Simplex. 
 
Obs: Se a variável artificial for diferente de zero na solução final, o problema não tem 
solução. 
Resolver as seguintes formulações: 
1) min Z = 2X1 +3X2 
sujeito a: 
1/2X1 + 1/4X2 ≤ 4 
X1 + 3X2 ≥ 20 
X1 + X2 = 10 
X1 ≥ 0 
X2 ≥ 0 
2) min Z = 2X1 +3X2 
Curso de Pesquisa Operacional 50 
sujeito a: 
2X1 + X2 ≥ 4 
X1 - X2 ≥ -1 
X1 ≥ 0 
X2 ≥ 0 
 
4.7.3 O Método das duas fases 
Primeira fase: formular um novo problema, trocando a função objetivo original por uma 
artificial, representada pela soma das variáveis artificiais. Como o objetivo é tornar nulas 
todas as variáveis devemos minimizar, primeiramente, a função objetivo artificial W, 
levando-se em conta os seguintes fatos, no algoritmo simplex: 
a. A FO é W; 
b. A FO Z do problema principal é tratada como qualquer outra variável durante a operação 
de pivotagem; 
c. A decisão a respeito da variável que sai da base não inclui a linha correspondente a Z. 
 
Resolvido o simplex para o problema artificial e obtida a solução ótima, W = W , encerra-se a 
primeira fase do processo. 
 
Neste caso, tem-se duas hipóteses: 
1a) W > O : neste caso o problema principal não tem solução; 
2a) W = O : existe uma solução inicial para o problema principal. Passa-se a segunda fase. 
 
Segunda Fase: Inicia-se a segunda fase tomando-se as seguintes providências: 
a. suprime-se todas as variáveis artificiais; 
b. suprime-se a função objetivo artificial e trabalha-se com a função objetivo do problema 
principal. 
 
Resolver as formulações do item anterior, e a proposta a seguir pelo método das duas fases. 
 
max Z = -1X1 +2X2 
sujeito a: 
X1 + X2 ≥ 2 
Curso de Pesquisa Operacional 51 
-1X1 + X2 ≥ 1 
X2 ≤ 3 
X1 ≥ 0 
X2 ≥ 0 
Curso de Pesquisa Operacional 52 
5 - SOFTWARES COMPUTACIONAIS 
 
A utilização de programação linear é recomendada para problemas de maior porte, em que 
muitas variáveis e restrições devem ser consideradas. Por isso, o desenvolvimento de 
algoritmos computacionais eficientes e precisos têm sido a maior preocupação entre os 
pesquisadores. Programas adequados existem, virtualmente, para cada sistema computacional 
comercial desenvolvido nos últimos 20 anos. 
Problemas de grande porte requerem sistemas computacionais potentes e, portanto, sistemas 
paralelos têm sido utilizados nos últimos anos. Entretanto, problemas menores podem ser 
resolvidos em um computador pessoal utilizando um dos softwares desenvolvidos para 
resolução de problemas de programação linear, como por exemplo XPress-MP LINDO e 
MINOS. 
Para problemas considerados médios, é recomendável a utilização de planilhas eletrônicas 
com recursos para resolução de problemas. Exemplos destas planilhas são o "What's Best?" 
(LINDO Systems) para Lotus 1-2-3, o Microsoft Excel e Borland Quattro e ainda o solver 
para microsoft Excel. Todos eles são ferramentas poderosas, apesar de sua aparência simples. 
O Solver do Excel será utilizado em alguns exemplos apresentados. Outro programa que 
também será visto é o LINDO. 
O instituto de pesquisa operacional e ciências administrativas (INFOR-MS) publica, 
eventualmente, pesquisas sobre os softwares de programação matemática em seu periódico 
OR/MS Today. O relatório de 1995 apresenta softwares que rodam em computadores pessoais 
e destaca softwares capazes de atacar problemas maiores tanto quanto extensões de planilhas 
eletrônicas. 
 
5.1 Uma introdução ao uso do LINDO 
LINDO (Linear Interactive and Discrete Optimizer) foi desenvolvido por Linus Schrage 
(1986). Ele é um programa de computador que pode ser usado para resolver problemas de 
programação linear, inteira e quadrática. Para ilustrar seu uso, vamos usar o exemplo de 
Giapetto, discutido anteriormente, e que foi sintetizado na seguinte formulação: 
 
 
 
 
 
 
Curso de Pesquisa Operacional 53 
 
 
 
 
 
 
 
 
 
 
O programa executável tem o nome LINDO.EXE, apesar dele ser originalmente desenvolvido 
para o ambiente DOS, pode-se executá-lo pelo WINDOWS. O LINDO assume que todas as 
variáveis são não negativas, e as restrições adicionais não precisam ser fornecidas. 
 
5.1.1 Comandos do LINDO 
São os seguintes os comandos do LINDO: 
MAX – entrada inicial para o problema de maximização; 
MIN – entrada inicial para o problema de minimização; 
END – finalização da formulação, deixando o LINDO pronto para aceitar outros comandos; 
GO – resolve a formulação corrente e apresenta a solução; 
LOOK – mostra seleção estabelecida da atual formulação; 
ALTER – altera um elemento da formulação corrente; 
EXT – soma uma ou mais restrições ao modelo; 
DEL – retira uma ou mais restrições do modelo; 
DIVERT – saída para um arquivo, de tal forma que possa ser impresso; 
RVRT – finaliza o comando DIVERT; 
SAVE – salva uma formulação, de tal forma que possa ser recuperada para uso futuro; 
RETRIEVE – recupera um arquivo anteriormente salvo; 
EDIT – chama o editor do programa; 
SOLU – mostra a solução da formulação (usar o comando GO antes do SOLU); 
TABLEAU – mostra a tabela da formulação pelo simplex; 
TAKE – habilita o LINDO a trabalhar com arquivos gerados por outros editores. 
 
Uma lista completa dos comandos pode ser obtida através do comando COMMAND. 
 
• max Z = 3X1 + 2X2 (1) 
 sujeito a: 
• 2X1 + X2 <= 100 (2) 
• X1 + X2 <= 80 (3) 
• X1<= 40 (4) 
• X1 >= 0 (5) 
• X2 >= 0 (6) 
Curso de Pesquisa Operacional 54 
5.1.2 Usando o LINDO 
O programa assume que todas as variáveis precisam ser não negativas. Assim, usando o 
programa não é necessário digitar as variáveis de não negatividade. Para entrar com ≥ ou ≤, 
basta digitar > ou <. O problema de Giapetto no programa fica da maneira ilustrada na figura 
abaixo. 
 
 
Depois de inserida a formulação no programa, pode-se usar qualquer dos comandos 
mostrados anteriormente. Para problemas com muitas variáveis, a função objetivo ou as 
restrições