Apostila PO

Prévia do material em texto

�Notas de Aulas
Pesquisa Operacional I -UVV
Flavia Giacomin Pimentel de Almeida
Centro Universitário Vila Velha
NOTAS DE AULA
PESQUISA OPERACIONAL I
Profª MSc. Flavia Giacomin Pimentel de Almeida
2016
�
Prefácio
Esta apostila foi desenvolvida a fim de auxiliar o curso de Pesquisa Operacional.
A apostila é uma compilação de diversas fontes: livros, notas de aula, citações, pesquisa e buscas na internet; entre outros. As fontes são referenciadas no último capitulo.
O intuito desta apostila é de agilizar o processo de otimização de sistemas com a união de ideia de diversos autores com produções utilizadas ao longo de período de aprendizado dessa fantástica missão de ensinar e deixar um “legado” que tem o professor.
Por se tratar de um professor universitário, essa tarefa torna-se cada vez mais difícil e fascinante, o desafio dessas trocas de informações, visto que o nível do estudante de 3º grau tem um grande embasamento para acompanhar o raciocínio lógico e as variáveis que acompanham essa longa trajetória.
Espero que possamos “trocar” muitas informações e que vocês saiam daqui com uma bagagem mais lapidada.
O curso aqui apresentado, de maneira introdutória, traz algumas das principais técnicas da Pesquisa Operacional.
Procurou-se com o mínimo de teoria e exclusão de assuntos que não possam ser aplicados de imediato, enfocar as aplicações desses métodos.
Não se tem a pretensão de apresentar algo original, mas sim estabelecer um roteiro de assuntos que julgamos construir o mínimo necessário para quem se inicia na área. Além disso, em função do tempo disponível, algumas técnicas e métodos de pesquisa operacional não serão aqui estudados.
Espera-se que seja útil aos alunos, mas não custa lembrar que a apostila não substitui a aula e sim a complementa, sendo necessárias anotações, atenção e assiduidade.
E ainda que a eficiência do curso seja função da participação ativa dos alunos, com o objetivo facilitar a vida dos alunos, desejo um total empenho por parte de vocês.
As sugestões serão muito úteis para o andamento dos trabalhos.
Um bom curso para nós!!!
Ultima atualização 27/07/2016
Versão 4.0
Flavia Giacomin P. de Almeida
Notas de Aulas da Disciplina de Pesquisa Operacional
�
Sumário
61	INTRODUÇÃO À PESQUISA OPERACIONAL	�
61.1	Para que estudar Pesquisa Operacional	�
61.2	O Surgimento da Pesquisa Operacional	�
81.3	O Impacto da Pesquisa Operacional	�
81.4	Modelagem em Pesquisa Operacional	�
81.4.1	Conceito de modelo	�
91.4.2	Tipos de Modelos	�
91.5	Fases de um estudo de Pesquisa Operacional	�
101.5.1	Definição detalhada do problema	�
101.5.2	Formulação do Problema	�
111.5.3	Solução do Modelo Definido	�
111.5.4	Verificação e Validação do Modelo Definido	�
111.5.5	Implementação dos resultados obtidos	�
122	PROGRAMAÇÃO LINEAR	�
122.1	Modelagem Matemática em Programação Linear - PPL	�
132.1.1	Definição – Problema de Programação Linear – PPL	�
142.2	Modelagem da Programação Linear	�
152.3	Forma canônica:	�
152.4	Forma Geral de um PPL	�
162.5	Exemplo de aplicação de Modelagem Matemática	�
162.5.1	Exemplo 01: O problema do Fazendeiro	�
162.5.2	Exemplo 02: Empresa de Ração	�
172.5.3	Exemplo 03: Empresa de Móveis	�
182.5.4	Exemplo 04: Empresa produtora de P1 e P2	�
202.6	Lista de Exercícios Capitulo 2 - Modelagem	�
213	soluções para problemas de Programação Linear	�
213.1	Opções de Solução	�
213.2	Tipos de Soluções para PPL	�
224	Solução do Problema pelo Método Gráfico	�
224.1	Aplicação do Modelo de Solução pelo Método Gráfico	�
224.1.1	Exemplo 01: O problema do Fazendeiro	�
244.1.2	Exemplo 02: Empresa de Ração	�
265	SOLUÇÃO PELO MÉTODO SIMPLEX	�
265.1	Estabelecimento do Método Simplex	�
265.1.1	MÉTODO SIMPLEX - CONDIÇÕES DE PREPARAÇÃO	�
285.1.2	Estruturação do TABLEAU	�
285.2	ALGORITMO SIMPLEX	�
285.2.1	PASSO 1 - Colocar o problema na Forma Padrão	�
295.2.2	PASSO 2 – Preparar o quadro de resolução do Tableau	�
295.2.3	PASSO 3 – REGRA DE PARADA	�
295.2.4	PASSO 4 - Escolha da Variável que entra na Base	�
295.2.5	PASSO 5 - Escolha da Variável que sai da Base	�
295.2.6	PASSO 6 – Elemento Pivô	�
305.2.7	PASSO 7 – Linha Pivô	�
305.2.8	PASSO 8 – Processo de Iteração	�
305.2.9	PASSO 9 – Verificação do Processo	�
305.2.10	PASSO 10 – Solução Ótima	�
305.3	CASOS DE DIFICULDADES NA APLICAÇÃO DO MÉTODO SIMPLEX	�
315.4	MÉTODO SIMPLEX DE UMA FASE	�
315.4.1	Exemplo 01: O problema do Fazendeiro	�
335.4.2	Exemplo 02: SIMPLEX	�
355.5	Método Simplex com Duas Fases	�
396	DUALIDADE	�
427	ANALISE DE SENSIBILIDADE	�
427.1	Interpretação de resultados de um problema de Programação Linear	�
447.2	A Análise Econômica	�
467.3	Análise de Sensibilidade	�
518	PROBLEMA DO TRANSPORTE	�
518.1	Introdução	�
518.2	Concepção do Problema	�
528.2.1	Sistema Equilibrado	�
528.2.2	Sistema não Equilibrado	�
528.3	FORMULAÇÃO GERAL DO PROBLEMA DE TRANSPORTE	�
538.4	Forma Canônica	�
538.5	Exemplo de Modelagem de um Problema de Transportes	�
548.5.1	Fase 1 - Definição do problema:	�
548.5.2	Fase 2 - Identificação das variáveis relevantes:	�
548.5.3	Fase 3 - Formulação da Função Objetivo:	�
548.5.4	Fase 4 - Formulação das restrições:	�
548.6	Preparação do Quadro para um Problema de Transportes	�
558.6.1	Soluções para o Quadro de Transportes	�
558.6.2	MÉTODO DE SOLUÇÃO	�
568.7	SOLUÇÃO INICIAL PELO METODO DO CANTO NOROESTE	�
568.7.1	Algoritmo de solução do Método do Canto Noroeste	�
578.7.2	Exemplo de aplicação do Método do Canto Noroeste	�
588.8	SOLUÇÃO INICIAL PELO MÉTODO DO VOGEL OU MÉTODO DAS PENALIDADES	�
598.8.1	Exemplo de aplicação do Método do Vogel	�
608.9	CRITÉRIO DE OTIMALIDADE OU MÉTODO U-V	�
618.9.1	Teste da solução – Método u-v	�
638.9.2	Particularidades do Método u-v	�
648.10	DEGENERAÇÃO	�
669	O PROBLEMA DA DESIGNAÇÃO	�
669.1	ALGORITMO DA DESIGNAÇÃO	�
679.2	ALGORITMO DA DESIGNAÇÃO – nova opção	�
679.2.1	Aplicação do problema de Designação - Minimização	�
699.2.2	PROCESSO DE DESIGNAÇÃO:	�
7110	EXERCÍCIO	�
7411	REDES	�
7411.1	Conceitos Básicos – Teoria dos Grafos	�
7411.2	Análise de Redes – Aplicações	�
7812	Algoritmo para o Problema da Rota Mais Curta	�
8013	O PROBLEMA DA ÁRVORE GERADORA MÍNIMA	�
8114	O PROBLEMA DO FLUXO MÁXIMO	�
8315	REFERENCIAS BIBLIOGRAFICAS	�
�
�
INTRODUÇÃO À PESQUISA OPERACIONAL
Para que estudar Pesquisa Operacional 
Antes de saber para que estudar Pesquisa Operacional é importante saber o que significa o termo.
Pois bem, a Pesquisa Operacional é um conjunto de técnicas matemáticas que visa fornecer soluções para problemas específicos, problema de alocação de recursos, transporte e movimentação, visa aplicação mais eficiente de recursos limitados na obtenção de resultados “ótimos” para objetivos a serem atingidos.
Clareou?
Ainda não?
Então vamos trocar em miúdos. A pesquisa Operacional vem para “otimizar” processos, isto é, tornar os processos ótimos. Para tanto, melhoramos o lucro ou diminuímos os custos do processo. Seja ele de: produção, transportes, movimentação. Todo este trabalho de otimização é feito por meio de modelagem matemática.
A sobrevivência e crescimento de uma empresa dependem da busca de vantagens competitivas em relação às suas concorrentes, para que se criem atividades diferenciadas com maior eficiência e menor custo, tendo como fio condutor da atuação voltada para o mercado e da agregação de valor aos acionistas, orientada pelo crescimento com lucro. Nesse sentido a Pesquisa Operacional serve de ferramenta para estudar as operações envolvidas nas atividades empresariais com o objetivo de oferecer aos gestores resultados quantitativos que auxiliem a tomada de decisões, a partir da criação de modelos que permitem a simulação e avaliação de alternativas de ação que possam ser implantadas de modo a alcançar vantagens competitivas. (Gouveia, 2008)
O Surgimento da Pesquisa Operacional
A Pesquisa Operacional, que trataremos por PO a partir deste momento, teve oseu nascimento oficial durante a Segunda Guerra Mundial com o objetivo de resolver problemas de operações militares, um grupo de cientistas foi convocado na Inglaterra para estudar problemas de estratégia e de tática associados com a defesa do país. O objetivo era decidir sobre a utilização mais eficaz de recursos militares limitados. A convocação deste grupo marcou a primeira atividade formal de pesquisa operacional. A ideia era fazer pesquisas em operações militares - daí o nome: Pesquisa Operacional – e seus esforços foram considerados decisivos em várias operações de guerra.
Pode-se dizer que ser nascimento oficial deve-se a iniciativas dos serviços militares e ingleses no início da segunda guerra mundial; por causa do esforço de guerra, cientistas e pesquisadores ingleses prestaram apoio ao seu governo na solução de importantes problemas de natureza tática e estratégica, na tentativa de, em conjunto com os militares usar adequadamente os poucos meios disponíveis para fazer frente a um inimigo mais poderoso.
Deste modo, alguns problemas foram solucionados, como por exemplo:
- a distribuição e localização dos meios de defesa antiaéreos, ao longo da ilha;
- a determinação do número mínimo de aviões ingleses a serem mantidos em condições de fazer frente aos ataques alemães, visando liberar outros aviões para realizar incursões às instalações e áreas inimigas no continente europeu.
Após a guerra, com o retorno destes cientistas à vida civil (universidades, centros de pesquisas e industrias) inúmeras outras aplicações foram desenvolvidas, e equações puderam ser solucionadas.
Os resultados positivos conseguidos pela equipe de pesquisa operacional inglesa motivaram os Estados Unidos a iniciarem atividades semelhantes. Apesar de ser creditada à Inglaterra a origem da Pesquisa Operacional, sua propagação deve-se principalmente à equipe de cientistas liderada por George B. Dantzig, dos Estados Unidos, convocada durante a Segunda Guerra Mundial. Ao resultado deste esforço de pesquisa, concluído em 1947, deu-se o nome de Método Simplex.
Com o fim da guerra, a utilização de técnicas de pesquisa operacional atraiu o interesse de diversas outras áreas. A natureza dos problemas encontrados é bastante abrangente e complexa, exigindo portanto uma abordagem que permita reconhecer os múltiplos aspectos envolvidos. 
Uma característica importante da pesquisa operacional e que facilita o processo de análise e de decisão é a utilização de modelos. Eles permitem a experimentação da solução proposta. Isto significa que uma decisão pode ser mais bem avaliada e testada antes de ser efetivamente implementada. A economia obtida e a experiência adquirida pela experimentação justificam a utilização da Pesquisa Operacional. Com o aumento da velocidade de processamento e quantidade de memória dos computadores atuais, houve um grande progresso na Pesquisa Operacional. Este progresso é devido também à larga utilização de microcomputadores, que se tornaram unidades isoladas dentro de empresas. Isso faz com que os modelos desenvolvidos pelos profissionais de Pesquisa Operacional sejam mais rápidos e versáteis, além de serem também interativos, possibilitando a participação do usuário ao longo do processo de cálculo. A partir de então, a pesquisa operacional se difundiu, saindo da área militar e indo para a área civil, sendo hoje um ramo da ciência administrativa. 
Aplicações de pesquisa operacional na mineração começaram a surgir no final da década de 50 e início da década de 60. Apesar disso, as aplicações na mineração, são ainda hoje, relativamente tímidas se comparadas a outros tipos de indústria. Enquanto o mundo tem mostrado um crescente interesse na aplicação de pesquisa operacional, na área mineral este crescimento ainda pode ser considerado um tanto quanto tímido.
No Brasil, o uso de P.O. é ainda muito pequeno se comparado ao potencial que essas técnicas têm a oferecer. Mesmo nas grandes empresas problemas de tomada de decisão ainda são solucionados com base no bom senso e em experiências passadas. As decisões tomadas dessa forma, apesar de serem consideradas viáveis, não garantem uma decisão ótima sob determinado aspecto.
O Impacto da Pesquisa Operacional
A Pesquisa Operacional tem tido um grande impacto crescente na administração de empresas nos anos recentes. Tanto o número quanto a variedade de suas aplicações continuam a crescer rapidamente. Algumas de suas técnicas envolvem ideias bastante sofisticada em ciências políticas, matemática, economia, teoria da probabilidade e estatística. Como também sendo usada amplamente em outros tipos de organizações, inclusive negócios e indústria. 
Segundo Lisboa (2005) quase todas as doze maiores empresas do mundo, e uma considerável proporção das organizações industriais pequenas, têm grupos de pesquisa operacional bem estabelecidos. Muitas indústrias, inclusive a de aviação e mísseis, automóveis, comunicações, computadores, energia elétrica, eletrônica, alimentos, metalúrgica, mineração, papel, petróleo e transporte, têm feito uso extensivo da pesquisa operacional. Mesmo instituições financeiras, agências governamentais e hospitais têm aumentado rapidamente o uso que fazem da pesquisa operacional.
Modelagem em Pesquisa Operacional
Conceito de modelo
Um modelo nada mais é que um conjunto de suposições sobre a operação de um sistema. Em outras palavras, um modelo pode ser visto como uma imitação da realidade. Pidd (1998) apresenta as seguintes evoluções das definições de modelo:
1 - Um modelo é uma representação da realidade.
2 - Um modelo é uma representação da realidade projetado para algum propósito definido.
3 - Um modelo é uma representação da realidade que é planejado para ser usada por alguém responsável pelo gerenciamento ou entendimento da realidade.
4 - Um modelo é uma representação da realidade que é planejado para ser usado por alguém no entendimento, mudança, gerenciamento e controle desta realidade.
5 - Um modelo é a representação de parte da realidade vista pelas pessoas que desejam usá-lo para entender, mudar, gerenciar e controlar aquela parte da realidade.
6 - Um modelo é a representação externa e explícita de parte da realidade vista pelas pessoas que desejam usá-lo para entender, mudar, gerenciar e controlar aquela parte da realidade.
Tipos de Modelos
Vejamos alguns dos problemas que têm sido resolvidos por técnicas particulares de pesquisa operacional:
- PROGRAMAÇÃO LINEAR: tem sido usada com sucesso na solução de problemas relativos à alocação de pessoal, mistura de materiais, distribuição, transporte, carteira de investimento.
- PROGRAMAÇÃO DINÂMICA: tem sido aplicada também com sucesso a áreas como planejamento de despesas de publicidade, distribuição do esforço de vendas e programação de produção.
- TEORIA DAS FILAS: tem tido aplicação na solução de problemas relativos a congestionamento de tráfego, máquinas de serviços sujeitas a quebra, determinação do nível de uma força de serviço, programação do tráfego aéreo, projetos de represas, programação de produção e operação de hospitais.
- Simulação: tem tido aplicação quando as situações de incerteza ou a própria complexidade do sistema dificultam o esforço de compreensão para o exato equacionamento do sistema.
Outras técnicas de pesquisa operacional, tais como programação não-linear, teoria de estoque, teoria dos jogos e simulação, também têm sido aplicadas com sucesso a diversos contextos.
Fases de um estudo de Pesquisa Operacional
Um estudo de pesquisa operacional engloba, basicamente, as seguintes etapas:
1 - Definição detalhada do problema a ser resolvido;
2 - Formulação do Problema, construção do modelo representativo do sistema;
3 - Solução do modelo, Cálculo da Solução;
4 - Verificação e validação do modelo;
5 - Implementação dos resultados obtidos.
Como pode ser observada através das etapas de um estudo de PO, a base do estudo se concentra num modelo querepresenta o sistema a ser estudado. Por isso, o conhecimento de modelagem de sistemas é fundamental. 
Definição detalhada do problema 
Nesta fase, o administrador do sistema e o responsável pelo estudo da PO devem detalhar a que nível o trabalho deve ser apresentado.
A definição do problema baseia-se em três aspectos principais:
descrição exata dos objetivos do estudo;
identificação das alternativas de decisão existentes;
reconhecimento das limitações, restrições e exigências do sistema.
A descrição dos objetivos é uma das atividades mais importantes em todo o processo do estudo, pois a partir dela é que o modelo é concebido. Da mesma forma, é essencial que as alternativas de decisão e as limitações existentes sejam todas explicitadas, para que as soluções obtidas ao final do processo sejam válidas e aceitáveis.
Formulação do Problema
Nesta fase, o administrador do sistema e o responsável pelo estudo da PO deverão discutir, no sentido de colocar o problema de maneira clara e coerente, definindo os objetivos a alcançar e quais os possíveis caminhos alternativos para que isso ocorra.
Além disso, serão levantadas as limitações técnicas de sistema e as relações desses sistemas com outros da empresa ou do ambiente externo, com a finalidade de criticar a validade de possíveis soluções em face destes obstáculos.
Os modelos de PO são modelos matemáticos, isto é, modelos formados por um conjunto de equações e inequações.
Uma das equações do conjunto, a função objetivo, seve para medir a eficiência do sistema para cada uma das soluções propostas. A escolha apropriada do modelo é fundamental para a qualidade da solução fornecida. Se o modelo elaborado tem a forma de um modelo conhecido, a solução pode ser obtida através de métodos matemáticos convencionais. Por outro lado, se as relações matemáticas são muito complexas, talvez se faça necessária a utilização de combinações de metodologias.
Solução do Modelo Definido 
A solução é feita através de técnicas matemáticas específicas. A construção do modelo deve levar em consideração a disponibilidade de uma técnica para o cálculo da solução.
O objetivo desta fase é encontrar uma solução para o modelo proposto. Ao contrário das outras fases, que não possuem regras fixas, a solução do modelo é baseada geralmente em técnicas matemáticas existentes. No caso de um modelo matemático, a solução é obtida pelo algoritmo mais adequado, em termos de rapidez de processamento e precisão da resposta. Isto exige um conhecimento profundo das principais técnicas existentes. A solução obtida, neste caso, é dita "ótima".
Verificação e Validação do Modelo Definido 
Este teste é realizado com os dados empíricos do sistema. Se houverem dados históricos, eles serão aplicados no sistema, gerando um desempenho que pode ser comparado ao desempenho observado no sistema.
Nessa altura do processo de solução do problema, é necessário verificar a validade do modelo. Um modelo é válido se, levando-se em conta sua inexatidão em representar o sistema, ele for capaz de fornecer uma previsão aceitável do comportamento do sistema. 
Avaliadas as vantagens e a validação da solução obtida, esta deve ser convertida em regras operacionais. A implementação, por ser uma atividade que altera uma situação existente, é uma das etapas críticas do estudo. 
Implementação dos resultados obtidos
Nesta fase, a solução será apresentada ao administrador, evitando-se o uso da linguagem técnica do modelo. O uso da linguagem do sistema em estudo facilita a compreensão e gera boa vontade para a implementação que está sendo sugerida, com alguns ajustes necessários.
�
PROGRAMAÇÃO LINEAR
Para empresas, organizações ou sistemas resolverem problemas, é usual apresentar estes problemas em forma de modelo. O modelo procura então representar o sistema em estudo e sobre tal modelo, aplica-se alguma técnica ou método de solução, testar alternativas, visando obter a melhor solução para o problema. Uma vez testado o modelo, procura-se implementar esta solução no sistema real.
Modelagem Matemática em Programação Linear - PPL
A Pesquisa Operacional é um conjunto de técnicas matemáticas que visa fornecer soluções para problemas em que existam restrições (recursos limitados ou necessidades a serem atingidas) com o objetivo de obter “resultados ótimos” (por exemplo, obter máxima eficiência, máximo lucro, mínimo custo, etc.)
Para análise e formulação de um problema é fundamental que este esteja claramente definido. (é quase impossível obter-se respostas certas para problemas errados ou mal formulados).
Os objetivos, as diversas alternativas, as restrições e o efeito do sistema estudado sobre outros sistemas relacionados a ele devem estar perfeitamente definidos. Pode-se dizer, inclusive, que a essência das atividades de pesquisa operacional está na construção e utilização de modelos.
Em PO o modelo empregado é o Modelo Matemático, que descreve o sistema. Normalmente tem dois tipos de operações:
- Função objetivo -expressão matemática do objetivo a ser otimizado (por exemplo: lucro, custo, eficiência, etc.)
- Restrições- limitações existentes (por exemplo: disponibilidade de recursos ou necessidades a serem atingidas.)
Há dois tipos de variáveis:
- Controláveis - as que podem ser diretamente controladas por quem decide. O objetivo é então determinar os valores destas variáveis que conduzem à solução ótima.
- Sem controle - variáveis que não estão sob controle direto de quem decide.
Um modelo é uma simplificação (aproximação) do sistema real. O sistema real é normalmente bastante complexo. O modelo matemático representa o sistema simplificado, consequentemente todas as variáveis não podem ser incluídas no modelo.
As soluções de um modelo não são infalíveis, quando aplicadas ao sistema real. Sempre haverá erros. O objetivo é tornar tais erros tão pequenos quanto possíveis.
A descrição de um sistema por um modelo torna possível analisá-lo e testar várias alternativas, sem interromper o funcionamento. 
Outra vantagem é que o modelo torna, normalmente, o problema mais inteligível e pode esclarecer importantes relações entre as variáveis.
Um modelo é uma simplificação (aproximação) do sistema real. O sistema real é normalmente bastante complexo. O modelo matemático representa o sistema simplificado, consequentemente todas as variáveis não podem ser incluídas no modelo.
As soluções de um modelo não são infalíveis, quando aplicadas ao sistema real. Sempre haverá erros. O objetivo é tornar tais erros tão pequenos quanto possíveis.
A descrição de um sistema por um modelo torna possível analisá-lo e testar várias alternativas, sem interromper o funcionamento.
Outra vantagem é que o modelo torna, normalmente, o problema mais inteligível e pode esclarecer importantes relações entre as variáveis.
Um modelo define as variáveis importantes e quais os dados necessários para a análise do sistema. A coleta de dados é, pois, de extrema importância para dar confiabilidade ao modelo e sua solução.
Definição – Problema de Programação Linear – PPL
O problema geral de programação linear é utilizado para otimizar (maximizar ou minimizar) uma função linear de variáveis, chamada de "função objetivo", sujeita a uma série de equações ou inequações lineares, chamadas restrições. A formulação do problema a ser resolvido por programação linear segue alguns passos básicos.
deve ser definido o objetivo básico do problema, ou seja, a otimização a ser alcançada. Por exemplo, maximização de lucros, ou de desempenhos, ou de bem-estar social; minimização de custos, de perdas, de tempo. Tal objetivo será representado por uma função objetivo, a ser maximizada ou minimizada;
para que esta função objetivo seja matematicamente especificada, devem ser definidas as variáveis de decisão envolvidas. Por exemplo, número de máquinas, a área a ser explorada, as classes de investimento à disposição etc. Normalmente, assume-seque todas estas variáveis possam assumir somente valores positivos;
estas variáveis normalmente estão sujeitas a uma série de restrições, normalmente representadas por inequações. Por exemplo, quantidade de equipamento disponível, tamanho da área a ser explorada, capacidade de um reservatório, exigências nutricionais para determinada dieta etc.
Todas essas expressões, entretanto, devem estar de acordo com a hipótese principal da programação linear, ou seja, todas as relações entre as variáveis deve ser lineares. Isto implica proporcionalidade das quantidades envolvidas. Esta característica de linearidade pode ser interessante no tocante à simplificação da estrutura matemática envolvida, mas prejudicial na representação de fenômenos não lineares (por exemplo, funções de custo tipicamente quadráticas).
Programação Linear é uma técnica de otimização bastante utilizada na resolução de problemas que tenham seus modelos representado por expressões lineares. Pela sua simplicidade e a possibilidade de aplicação em uma considerável diversidade de problemas, tornou-se um recurso bastante difundido.
Podemos assim resumir a técnica de Programação Linear:
A função objetivo é obtida com as mesmas variáveis das restrições, com o objetivo de ser maximizada ou minimizada, com a resolução do sistema restritivo.
Chamamos de restrições, as expressões contornais do problema, ou seja, todas as disponibilidades e limitações levantadas do problema, numa linguagem matemática comparativa: desigualdades ou igualdades ((, ( ou (). 
Modelagem da Programação Linear
Um modelo é uma representação de um sistema real, que pode já existir ou ser um projeto aguardando execução. No primeiro caso, o modelo pretende reproduzir o funcionamento do sistema, de modo a aumentar sua produtividade. No segundo caso, o modelo é utilizado para definir a estrutura ideal do sistema.
A confiabilidade da solução obtida através do modelo depende da validação do modelo na representação do sistema real. A validação do modelo é a confirmação de que ele realmente representa o sistema real. A diferença entre a solução real e a solução proposta pelo modelo depende diretamente da precisão do modelo em descrever o comportamento original do sistema.
Um problema simples pode ser representado por modelos também simples e de fácil solução. Já problemas mais complexos requerem modelos mais elaborados, cuja solução pode vir a ser bastante complicada.
Em um modelo matemático, são incluídos três conjuntos principais de elementos:
(1) variáveis de decisão e parâmetros: variáveis de decisão são as incógnitas a serem determinadas pela solução do modelo. Parâmetros são valores fixos no problema;
(2) função objetivo: é uma função matemática que define a qualidade da solução em função das variáveis de decisão.
(3) restrições: de modo a levar em conta as limitações físicas do sistema, o modelo deve incluir restrições que limitam as variáveis de decisão a seus valores possíveis (ou viáveis);
Forma canônica:
Quando as restrições de um modelo de Programação Linear são apresentadas na forma de inequações, diz-se que esse modelo está na forma canônica. O problema de programação linear pode ser definido por
Maximizar (ou minimizar) Z= c1 x1 + c2 x2 + …+ cN xN
sujeito a 
a11 x1 + a12 x2 + …+ a1N xN ( b1 (ou ≥, ou =)
a21 x1 + a22 x2 + …+ a2N xN ( b2 (ou ≥, ou =)
 … 
aM 1 x1 + aM 2 x2 + …+ aM N xN ( bM (ou ≥, ou =)
x1, x2,…, xj,…, xN (0
Forma Geral de um PPL
A apresentação de um PPL é da seguinte forma:
Max Z = 
			
	FO
s.a.	
 
 
 bi	 
i=1,2,...,m	
	Restrições
 xj 
 0			
	Condição não negatividade
Onde:
Cj = vetor dos custos (ou lucros)				
 xj = variáveis de decisão			
aij = coeficientes tecnológicos (quanto cada atividade requer do recurso j)
 bi = limites ou RHS-Right Hand Side (quanto se dispõe de cada recurso)
m, n = limite dos índices i, j
aij, bi, Cj = parâmetros conhecidos
i = 1, 2, ..., m
j = 1, 2, ..., n
Exemplo de aplicação de Modelagem Matemática
Para melhor ilustrar o conjunto de definições apresentadas, considere o seguinte exemplo:
Exemplo 01: O problema do Fazendeiro
Um fazendeiro deseja otimizar as plantações de arroz e milho na sua fazenda. O fazendeiro quer saber as áreas de arroz e milho que devem ser plantadas para que o seu lucro nas plantações sejam o máximo. O seu lucro por unidade de área plantada de arroz é 5 u.m., e por unidade de área plantada de milho é 2 u.m.
As áreas plantadas de arroz e milho não devem ser maiores que 3 e 4 respectivamente. Cada unidade de área plantada de arroz consome 1 H.h. Cada unidade de área plantada de milho consome 2 H.h. O consumo total de homens-hora nas duas plantações não deve ser maior que 9.
*u.m. (unidades monetárias)
H.h – homem-hora
SOLUÇÃO:
Variáveis de Decisão
x1: quantidade de arroz a produzir
x2: quantidade de milho a produzir
FO
Max Z = 5 x1 + 2 x2
s.a
x1 ( 3		(Restrição quanto a área de plantio do arroz)
x2 ( 4		(Restrição quanto a área de plantio do milho)
x1 + 2x2 	( 9	(Restrição quanto a H.h)
x1, x2 ( 0 	(Restrição de não negatividade)
Exemplo 02: Empresa de Ração
Uma empresa de comida canina produz dois tipos de rações: Tobi e Rex. Para a manufatura das rações são utilizados cereais e carne. Sabe-se que:
a ração Tobi utiliza 5 kg de cereais e 1 kg de carne, e a ração Rex utiliza 4 kg de carne e 2 kg de cereais;
o pacote de ração Tobi custa $ 20 e o pacote de ração Rex custa $ 30;
o kg de carne custa $ 4 e o kg de cereais custa $ 1;
estão disponíveis por mês 10 000 kg de carne e 30 000 kg de cereais.
Deseja-se saber qual a quantidade de cada ração a produzir de modo a maximizar o lucro. Neste problema as variáveis de decisão são as quantidades de ração de cada tipo a serem produzidas.
Os parâmetros fornecidos são os preços unitários de compra e venda, além das quantidades de carne e cereais utilizadas em cada tipo de ração. As restrições são os limites de carne e cereais e a função objetivo é uma função matemática que determine o lucro em função das variáveis de decisão e que deve ser maximizada.(Lisboa, 2005)
SOLUÇÃO:
a) As variáveis de decisão envolvidas no problema são:
x1: quantidade de ração Tobi a produzir
x2: quantidade de ração Rex a produzir
A formulação ficará da seguinte maneira:
Max Z = 11 x1 + 12 x2
sujeito a:
1 x1 + 4 x2 ( 10000 			(restrição de carne)
5 x1 + 2 x2 ( 30000 			(restrição de cereais)
x1, x2 ( 0 				(restrição de não negatividade)
Exemplo 03: Empresa de Móveis
Uma marcenaria deseja estabelecer uma programação diária de produção. Atualmente, a oficina faz apenas dois produtos: mesa e armário, ambos de um só modelo. Para efeito de simplificação, vamos considerar que a marcenaria tem limitações em somente dois recursos: madeira e mão-de-obra, cujas disponibilidades diárias são mostradas na tabela a seguir:
	Recurso
	Disponibilidade
	Madeira
	12 m²
	Mão-de-obra
	8 H.h
O processo de produção é tal que, para fazer uma mesa a fábrica gasta 2 m2 de madeira e 2 H.h de mão-de-obra. Para fazer um armário, a fábrica gasta 3 m2 de madeira e 1 H.h de mão de obra. Além disso, o fabricante sabe que cada mesa dá uma margem de contribuição para o lucro de $ 4 e cada armário de $ 1. O problema é encontrar o programa de produção que maximize a margem de contribuição total para o lucro."
SOLUÇÃO:
Montagem do Modelo
a) As variáveis de decisão envolvidas no problema são:
x1: quantidade de mesas a serem produzidas por dia
x2: quantidade de armários a serem produzidos por dia
b) A função objetivo é (FO):
O problema é de maximizar lucro, portanto:
Maximizar Z = 4 x1 + x2
c) Para as restrições, a relação lógica existente é:
Utilização de recurso ( DisponibilidadeAssim temos:
2 x1 + 3 x2 (12	Restrição quanto à quantidade de Madeira: 
2 x1 + x2 (8 	Restrição quanto à quantidade de Mão-de-obra: 
x1;x2 (0		Condição de não negatividade
d) O modelo completo é:
Maximizar: z = 4 x1 + x2
Sujeito a 
2 x1 + 3 x2 (12
2 x1 + x2 (8
x1, x2 (0
Exemplo 04: Empresa produtora de P1 e P2
Certa empresa fabrica dois produtos, P1 e P2. O lucro unitário de P1 é de 1000 unidades monetárias e o lucro unitário de P2 é de 1800 unidades monetárias. A empresa precisa de 20 horas para fabricar uma unidade de P1 e de 30 horas para fabricar uma unidade de P2. O tempo anual de produção disponível para isso é de 1200 horas. A demanda esperada para cada produto é de 40 unidades anuais para o produto P1 e de 30 unidades anuais para P2. Construa o modelo de programação linear para este caso. (SILVA at all, 1998)
SOLUÇÃO:
a) As variáveis de decisão envolvidas no problema são:
x1: quantidade de P1a serem produzidas anualmente
x2: quantidade de P2 a serem produzidos anualmente
b) A função objetivo é (FO):
O problema é de maximizar lucro, portanto:
Max Z = 1000x1 + 1800x2
c) Para as restrições, a relação lógica existente é:
Utilização de recurso ( Disponibilidade
Assim temos:
20 x1 + 30 x2 ( 1200	Restrição quanto à disponibilidade para produção 
x1 ( 40 			Restrição quanto à demanda de P1
x2 ( 30 			Restrição quanto à demanda de P2
x1;x2 (0		Condição de não negatividade
d) O modelo completo é:
Max: Z = 1000x1 + 1800x2
Sujeito a 
20 x1 + 30 x2 ( 1200
x1 ( 40 	
x2 ( 30 	
x1;x2 (0	
�
Lista de Exercícios Capitulo 2 - Modelagem
Para uma boa alimentação, o corpo necessita de vitaminas e proteínas. A necessidade mínima de vitaminas é de 32 unidades por dia e a de proteínas de 36 unidades por dia. Uma pessoa tem disponível carne e ovos para se alimentar. Cada unidade de carne contém 4 unidades de vitaminas e 6 unidades de proteínas. Cada unidade de ovo contém 8 unidades de vitaminas e 6 unidades de proteínas. Qual a quantidade diária de carne e ovos que deve ser consumida para suprir as necessidades de vitaminas e proteínas com o menor custo possível? Cada unidade de carne custa 3 unidades monetárias e cada unidade de ovo custa 2,5 unidades monetárias (Silva at all, 1998)
Uma empresa fabrica 2 produtos, copos e pratos. O lucro unitário de um copo é de R$5,00 reais e o lucro de um prato é de R$7,00 reais. A empresa precisa de 2 horas para fabricar um copo e de 3 horas para fabricar um prato. O tempo semanal de produção disponível para fabricação dos objetos é de 580 horas. A demanda semanal esperada é 40 unidades de copos e de 30 unidades de pratos. Apresente o PPL para o problema.
�
soluções para problemas de Programação Linear 
Opções de Solução
Solução pelo método gráfico
Solução pelo método simplex
Tipos de Soluções para PPL 
Solução ótima: Solução viável que fornece o valor ótimo da função objetivo.
Solução Tipo Vértice: corresponde a um vértice do polígono.
Solução adjacente: duas soluções tipo vértice são adjacentes se o segmento que as une é um dos lados do polígono (Ex: os pontos A e B são adjacentes)
Considerações
Nos problemas de programação linear pode ocorrer que:
(1) Haja uma solução ótima (no exemplo, é o ponto C)
(2) Haja mais de uma solução- soluções múltiplas- basta a reta da função objetivo Z ser paralela a um dos lados do polígono. Se no exemplo tivéssemos Z=3x1+2x², então C e B forneceriam ambos o valor máximo de Z; assim, tanto para C(2, 6) e B(4, 3) Z seria igual a 18; além disso, qualquer outro ponto do segmento BC também seria solução ótima.
Na pratica, isto significa que o problema teria uma infinidade de soluções ótimas. Quando acontece tal fato, deve-se desconfiar do modelo, pois encontrar um problema REAL com infinitas soluções ótimas é ideal.
(3) Não existe solução ótima
Isto ocorre:
a) quando não existe solução variável ou quando 
b) as restrições não impedem o crescimento de Z infinitamente (região viável aberta)
Propriedades
Demonstra-se matematicamente que
(1) Se existir uma única solução ótima ela corresponde a um vértice.
(2) O número de soluções tipo vértice é finito
(3) Se um vértice fornece um valor para Z melhor que os valores obtidos pelos vértices que lhe são adjacentes, então ela é ótima
- O método a ser desenvolvido consiste em pesquisar os vértices do polígono; indo de um vértice para o ser adjacente, e até encontrar aquele que forneça o valor ótimo para Z.
�
Solução do Problema pelo Método Gráfico
A Solução pelo método gráfico é possível para problemas que apresentam duas variáveis de decisão. O plano cartesiano é utilizado para auxiliar a formação da região viável e das inequações que definem esta região. O ponto ótimo será sempre o ponto mínimo ou máximo que a “reta” da Função Objetivo toca dependendo do caso.
Aplicação do Modelo de Solução pelo Método Gráfico
Os problemas com apenas duas variáveis podem ser resolvidos graficamente. Traça-se um gráfico com os seus eixos sendo as duas variáveis x1 e x2. A partir daí, traçam-se as retas referentes às restrições do problema e delimita-se a região viável 
Encontrada a região viável, deve-se traçar uma reta com a inclinação da função objetivo. Para isso, arbitra-se um valor para a função objetivo com o intuito de desenhar a inclinação da reta. Desliza-se esta reta até encontrar o ponto ótimo; que pode ser o ponto mínimo ou o ponto máximo.
O ponto ótimo será sempre um vértice do polígono, isto é interseção de duas retas.
É importante frisar que as soluções para PPL são as mais diversas
Solução Viável – É a solução ótima
Infinitas Soluções – É quando a equação da FO está sobre alguma das restrições ou quando 
Sem Solução – Quando não há região viável
Solução Infinita – Um valor muito alto sem ponto definido
Para melhor ilustrar o conjunto de definições apresentadas, continuemos os exemplos:
Exemplo 01: O problema do Fazendeiro
Equação da Modelagem
Max Z = 5x1 + 2x2
Sujeito a
x1 		( 3 (I)
x2 		( 4 (II)
x1 + 2x2 	( 9 (III)
x1, x2 		( 0 
Como o problema tem apenas duas variáveis (x1 e x2), podemos resolve-lo graficamente, conforme a Figura 4.1.
�Figura 4.1 - Região Viável
Uma outra maneira de encontrar a Solução Ótima do problema é testar todos os vértices como descrito a seguir.
A Figura 4.1 é o resultado do lançamento gráfico das retas (I), (II) e (III); Consequentemente determinamos os pontos vértices A(00), B(3,0), C(3,3), D(1,4) e E(0,4).
Como a função objetivo é Z = 5x1 + 2x2, que aplicada em cada vértice do polígono restritivo nos fornece os seguintes valores:
ZA(0,0) = 0
ZB (3,0) = 15
ZC(3,3) = 21 Verifica-se que o ponto “C” é o que fornece o maior valor para a função objetivo (Zmáx = 21).
ZD(1,4) = 13
ZE(0,4) = 8
Concluímos que o lucro máximo do fazendeiro de 21 unidades monetárias, desde que plante 3 unidades de área de arroz e 3 unidades de área de milho.
Porém, se traçarmos a reta da função objetivo, esse resultado é obtido de maneira mais rápida. 
Basta deslocar a reta da FO sobre o gráfico da região viável (região apresentada em cinza). Mas como fazer para representar a reta da função objetivo?
Atribui-se um valor para Z (sendo ele máximo ou mínimo) 
Figura 4.2 - Solução
 Máx L = 5x1 + 2x2
 
5x1 + 2x2 = 10 (o número 10 foi escolhido por ser um número múltiplo de 2 e 5 e por ficar mais simples representá-lo nos pontos (0,5) e (2,0))
A reta da FO desliza paralelamente passando pela região viável até chegar ao ponto de solução ótima!
O ponto de solução ótima será um vértice da região viável!
 Ponto de Solução Ótima!!!!!
Exemplo 02: Empresa de Ração
Max Z = 11 x1 + 12 x2
sujeito a:
1 x1 + 4 x2 ( 10000 
5 x1 + 2 x2 ( 30000 
x1, x2 ( 0 
A Figura 4.3 apresenta as retas das restrições e a região viável. Para encontrar a o ponto ótimo, deve-se traçaruma reta com a inclinação da função objetivo. 
São então traçadas diversas paralelas a ela no sentido de Z crescente (maximização da função), como na Figura 4.4. O ponto ótimo é o ponto onde a reta de maior valor possível corta a região viável (em um vértice).
Figura 4.3 - Região Viável para o problema das rações
Figura 4.4 - Busca da solução ótima para o problema das rações
Atentar para o fato de que o ponto ótimo é determinado pela intersecção das retas que compõem o ponto.
Para calcular o ponto ótimo, podemos fazer:
1 x1 + 4 x2 ( 10000 
5 x1 + 2 x2 ( 30000 (multiplicar a equação por (-2))
 1 x1 + 4 x2 = 10000
-10 x1 - 4 x2 = - 60000
- 9 x1 = - 50000		x1 = 5555,55			x2 = 1111,12
Cálculo de Z
Z = 11 x1 + 12 x2
Z= 11 (5555,55) + 12 (1111,12) = 61111,05 + 13333,44 = 74444,49
Z= 74444,49
Solução:
Z= 74444,49
x1 = 5555,55
x2 = 1111,12
�
SOLUÇÃO PELO MÉTODO SIMPLEX
Estabelecimento do Método Simplex
O Método Simplex é um procedimento geral para a resolução de problemas de programação linear, na verdade, trata-se de um algoritmo, ou seja, um processo onde um procedimento sistemático repetido (iterado) seguidamente até que o resultado desejado seja obtido.
O Método Simplex caminha pelos vértices da região viável até encontrar uma solução que não possua soluções vizinhas melhores que ela. Esta é a solução ótima. A solução ótima pode não existir em dois casos: quando não há nenhuma solução viável para o problema, devido a restrições incompatíveis; ou quando não há máximo (ou mínimo), isto é, uma ou mais variáveis podem tender a infinito e as restrições continuarem sendo satisfeitas, o que fornece um valor sem limites para a função objetivo.
Passo de Inicialização
É muito mais conveniente lidar com equações do que com desigualdades. Por isso, o primeiro passo para estabelecermos o método Simplex é reverter às restrições funcionais de desigualdade em restrições equivalentes de igualdade.
MÉTODO SIMPLEX - CONDIÇÕES DE PREPARAÇÃO
I) - Todos bis devem ser maiores ou iguais a zero, no caso se haver bi negativo, dever transformar a inequação
		 x1 + 3x2 ( - 7 bi negativo
		- x1 - 3x2 ( 7 bi positivo
II) - Todas restrições devem ser transformadas em igualdade (necessário uma base óbvia):
Para colocar as restrições em forma de igualdade; algumas premissas devem ser cumpridas
Se a restrição é do tipo MENOR OU IGUAL (( ), com bi positivo, introduz-se variável de folga:
Por exemplo:
		3x1 + x2 	( 5 desigualdade
		3x1 + x2 + x3 	= 5 igualdade
		sempre x1, x2 e x3 ( 0
Usualmente as restrições de um problema de PO tem a seguinte estrutura lógica:
Utilização de recurso ( Disponibilidade
Se introduzirmos o conceito de “Folga de recurso” podemos escrever a relação acima da seguinte forma:
Utilização + Folga = Disponibilidade
Considere a restrição funcional,
x1 ( 4
A variável de folga para esta restrição é:
x3 = 4 - x1
a qual é exatamente a folga entre os dois lados da desigualdade. Portanto,
x1 + x3 = 4
A constante original x1 ( 4 se mantém sempre que x3 ( 0. Conseqüentemente, x1 ( 4 é inteiramente equivalente ao conjunto de restrições:
x1 + x3 = 4 e
x3 ( 0,
assim, estas restrições mais convenientes são usadas em seu lugar.
b) Se a restrição é do tipo MAIOR OU IGUAL ( ( ), com bi positivo, introduzem-se uma variável de folga (com sinal negativo) e uma variável artificial:
		 x1 + 3x2 		( 5 desigualdade
		 x1 + 3x2 - x3 + x4	= 5 igualdade
							 variável de artificial
							 variável de folga
		Da mesma forma, x1, x2, x3 e x4 ( 0
c) Se a restrição é do tipo IGUAL ( = ), com bi positivo, introduz-se uma variável artificial:
		 2x1 + 7x2 		= 10
		 2x1 + 7x2 + x3	= 10 igualdade com variável artificial
		 Sendo, x1, x2 e x3 ( 0
III) - Toda minimização poderá ser transformada em maximização. Minimizar uma função Z é equivalente a maximizar o simétrico dessa função:
		Min Z = 2x1 - 3x2, equivale a Max (-Z) = -2x1 + 3x2
OBSERVAÇÕES ADICIONAIS: 
a) A informação de varáveis artificiais sempre implica no surgimento da função objetivo artificial, sendo o problema resolvido em duas fases.
b) Por questão de ordenação, deve-se primeiro introduzir todas variáveis de folga em todas restrições, para depois introduzir as variáveis artificiais.
c) O quadro estruturado mostra explicitamente uma solução básica inicial. As variáveis básicas formam, com seus coeficientes, uma matriz identidade.
O método Simplex usa o zero para este valor arbitrário.
As variáveis consideradas “zero” são chamadas de variáveis não-básicas, e as outras são chamadas de variáveis básicas. A solução resultante é chamada de solução básica. Se todas as variáveis básicas forem não-negativas tratar-se-á de uma solução básica viável.
O sistema de equações é resolvido repetidamente para uma seqüência de soluções básicas viáveis, cada uma melhor que a sua predecessora, até que seja alcançada uma solução (básica viável) ótima. Cada solução básica viável é obtida a partir de sua predecessora, transformando uma variável não-básica em uma variável básica (a variável básica entrando) e transformando uma variável básica numa variável não-básica (a variável básica saindo). Duas destas soluções básicas viáveis diferindo apenas por uma única troca de variáveis básica e não-básica são chamadas de adjacentes. A estas operações tem o nome de Método Simplex.
Estruturação do TABLEAU
Para aplicação do Algoritmo Simplex é necessário a estruturação do quadro (tableau), obedecendo as condições:
- bis não negativos.
- Restrições transformadas em igualdades, pela introdução de variáveis de folga e/ou artificiais.
- Função objetivo sujeita `a maximização (não obrigatório).
O quadro genérico explicito tem a forma:
		Base	
	
	x1
	x2
	. . .
	xn
	xn+1
	xn+2
	. . .
	xn+m
	bi
	xn+1 
	a11
	a12
	. . .
	a1n
	1
	0
	. . .
	0
	b1
	xn+2
	a21
	a22
	. . .
	a2n
	0
	1
	. . .
	0
	b2
	. . . 
	. . . 
	. . . 
	. . .
	. . . 
	. . . 
	. . . 
	. . .
	. . . 
	. . . 
	xn+m
	am1
	am2
	. . .
	amn
	0
	0
	. . .
	1
	bm
	Z
	c1
	c2
	. . . 
	cn 
	0
	0
	. . . 
	0 
	0 
ALGORITMO SIMPLEX
PASSO 1 - Colocar o problema na Forma Padrão
Para resolver um problema pelo método simplex, primeiro deve-se passar o modelo para o formato padrão, isto é, transformar as inequações em equações.
PASSO 2 – Preparar o quadro de resolução do Tableau
Preparar o quadro de solução tableau. O quadro deve apresentar a seguinte forma:
	Número Auxiliar
	Variável da Base
	Coeficiente das Variáveis
	Termo Independente
	Divisão
	Equação da Linha
	EQ
	VB
	X1, X2, X3...
	Bi
	Bi/aj
	
	0
	V. folga
	aj
	
	
	
No primeiro quadro as variáveis da base, são as variáveis de folga
Observar que as variáveis de folga devem formar com os seus coeficientes uma matriz identidade, essas variáveis de folga estão no primeiro momento na base.
PASSO 3 – REGRA DE PARADA
Observar os coeficientes da linha Z se existe algum número negativo. Caso não exista a solução ótima foi encontrada, do contrário vá para o passo 4.
PASSO 4 - Escolha da Variável que entra na Base
Verificar se os coeficientes Cjs da função objetivo Z são maiores ou iguais a zero, caso afirmativo, pare, a solução é ótima. Caso contrário, escolha a variável que tem o menor coeficiente para entrar na base. A variável que apresentar o número mais negativo será a que entra na base.
PASSO 5 - Escolha da Variável que sai da Base 
Verificar os coeficientes das da variável que vai entrar na base. Se todos os coeficientes forem menores ou iguais a zero, pare, Z = infinito. Caso contrário, divida cada bi pelo respectivo ais > 0. O menor quociente bi/ais, ais > 0, indica a variável de índice r que sai da base.
Escolher a variável que sai da base. Para queentre uma variável na base, é importante que uma saia também. Para isso tomam-se os valores de B e divide-se pelos coeficientes da variável que entra correspondente. O menor valor encontrado será a linha pivô, e a variável sairá da base. (Divide-se apenas por valores maiores que zero, não se divide a linha Z)
PASSO 6 – Elemento Pivô
É como chamamos o termo de interseção entre a linha e a coluna pivô.
PASSO 7 – Linha Pivô
Inicia-se o processo de iteração. A nova linha pivô surgirá da linha pivô, dividida pelo elemento pivô. O elemento pivô será 1.
L Pivô Nova = L Pivô Antiga / Elemento Pivô
PASSO 8 – Processo de Iteração
Reescrever cada uma das linhas restantes da seguinte maneira:
Lz¹ = L Pivô Nova x (C) + Lz
C = Coeficiente da linha em questão com a coluna da variável que entra com o sinal trocado.
PASSO 9 – Verificação do Processo
Verificar se existe algum coeficiente negativo na linha Z. Caso não haja a solução é ótima.
PASSO 10 – Solução Ótima
Caso contrário volte para o passo 4
CASOS DE DIFICULDADES NA APLICAÇÃO DO MÉTODO SIMPLEX
I) Empate na variável que entra na base, isto é, mais de uma variável não básica com o mesmo valor para seus respectivos Cjs.:. A escolha da variável que entra na base é aleatória.
II) Empate na variável que sai da base, isto é, dois ou mais quocientes bi /ais com mesmo valor.
- Neste caso caracteriza-se a presença de uma solução degenerada, isto é, uma variável básica com valor igual a zero. A escolha da variável que sai da base é aleatória.
III) Variáveis sem restrição de sinal, sem a condição de não negatividade.
- A solução alternativa para a questão específica: as variáveis sem restrição de sinal são substituídas pela diferença entre duas novas variáveis maiores ou iguais a zero.
IV) Ausência de soluções:
- A dificuldade caracteriza-se por não se conseguir zerar o valor de W ( função objetivo artificial) e por conseguinte as variáveis artificiais.
V) Ausência de soluções:
- A dificuldade caracteriza-se quando o problema atinge o ótimo (todos Cjs ( 0) e o coeficiente Cj de uma das variáveis não básicas, na função objetivo é zero.
- Para se encontrar o outro extremo, introduz-se na base a variável não básica que tem Cj igual a zero; calcula-se o novo quadro e	verifica-se que o valor de Z não se altera, indicando um novo ponto ótimo. Como solução geral, temos a combinação convexa dos dois extremos.
VI) Problema com minimização, neste caso, temos:
	Min Z = Máx (-Z)
VII) Problema com solução Z = infinito:
- Este problema caracteriza-se quando existe uma variável xs em condições de entrar na base de forma a provocar um aumento no valor de Z e todos seus coeficientes ais são menores ou iguais a zero. Não permitindo, assim, encontrar a variável que sairia da base.
MÉTODO SIMPLEX DE UMA FASE
O método simplex de uma fase é caracterizado pela ocorrência de restrições apenas do tipo menor ou igual ≤. Para ilustrar o método simplex, vamos iniciar resolvendo um problema antes aqui modelado e resolvido pelo método gráfico.
Exemplo 01: O problema do Fazendeiro
Máx Z = 5x1 +2x2
�sa:
x1 ( 3
x2 ( 4
x1 + 2x2 ( 9
Sempre em qualquer problema, temos como solução x1 e x2 ( 0
PASSO 1: Inicialmente transformemos o sistema de restrições em igualdades com introdução das variáveis de folga, ficando o sistema na forma padrão:
 x1 + x3 = 3
 x2 + x4 = 4
x1 + 2x2+ x5 = 9
 Z -5x1 -2x2 = 0
 Sendo as variáveis x3, x4 e x5, as variáveis de folga.
PASSO 2: Agora preparamos o QUADRO TABLEAU. Considerando o sistema já com a inclusão das variáveis de folga, temos:
PASSO 3: Existem coeficientes negativos 
	QUADRO 1
	EQ
	Q1
	X1
	x2
	x3
	x4
	x5
	B
	Bi/aj
	
	
	1
	x3
	1
	0
	1
	0
	0
	3
	3/1 =.3
	Menor quociente, variável que sai da base (x3)
	
	2
	x4
	0
	1
	0
	1
	0
	4
	XXXX
	Zero
	
	3
	x5
	1
	2
	0
	0
	1
	9
	9/1=9
	9/1 = 9
	
	4
	Z
	-5
	-2
	0
	0
	0
	0
	XXXX
	NEGATIVO
 		 	O elemento a11 = 1 é exatamente o PIVOT
 			 Coeficiente menor, indica a variável que entra na base (x1)
PASSO 4: Escolha da Variável que entra na base – x1
PASSO 5: Escolha da Variável que sai na base – x3
PASSO 6: Calculo da Linha Pivô nova:
PASSO 7: Calculo da demais linhas do quadro
PASSO 8: Processo Iterativo.... quadros 1, 2, 3 
PASSO 9: Regra de Parada 
PASSO 10 : Solução Ótima 
	QUADRO 1
	EQ
	Q1
	X1
	x2
	x3
	x4
	x5
	B
	Bi/aj
	Equação das Linhas
	
	1
	x3
	1
	0
	1
	0
	0
	3
	3/1 =.3
	Linha Pivô 
	
	2
	x4
	0
	1
	0
	1
	0
	4
	XXXX
	
	
	3
	x5
	1
	2
	0
	0
	1
	9
	9/1=9
	
	
	4
	Z
	-5
	-2
	0
	0
	0
	0
	XXXX
	
	QUADRO 2
	EQ
	Q2
	X1
	x2
	x3
	x4
	x5
	b
	Bi/aj
	Equação das Linhas 
	
	1
	x1
	1
	0
	1
	0
	0
	3
	XXX
	Linha Pivô nova LPN=LP/Elemento Pivô
	
	2
	x4
	0
	1
	0
	1
	0
	4
	4/1= 4
	L2’ = LPN(0) + L2
	
	3
	x5
	0
	2
	 -1
	0
	1
	6
	6/2= 3
	L3’ = LPN(-1) + L3
	
	4
	Z
	0
	-2
	5
	0
	0
	15
	XXXX
	L4’ = LPN(5) + L4
	QUADRO 3
	EQ
	Q3
	x1
	x2
	x3
	x4
	x5
	b
	Bi/aj
	
	
	1
	x1
	1
	0
	1
	0
	0
	3
	
	L1’ = LPN(0) + L1
	
	2
	x4
	0
	0
	1/2
	1
	-1/2
	1
	
	L2’ = LPN(-1) + L2
	
	3
	x2
	0
	1
	-1/2
	0
	1/2
	3
	
	Linha Pivô nova LPN=LP/Elemento Pivô
	
	4
	Z
	2
	0
	7
	0
	1
	21
	
	L4’ = LPN(2) + L4
O quadro 3 é solução ótima porque todos os coeficientes da linha Z ou são nulos ou positivos (Cjs ( 0). Temos: x1 = 3 e x2 = 3. Como Zmáx = 5x1 + 2x2, concluímos que o maior valor para Z é 21.
Obtenção das linhas do quadro Quadro 2:
LPN= LP/EP=	L2’ = LPN(0) + L2=		L3’ = LPN(-1) + L3=			L4’ = LPN(5) + L4=
a11 = 1/1 = 1	a21 = 1x0 + 0 = 0		a31 = 1x(-1) + 1 = 0		a41 = 1(5) + (-5) = 0
a12 = 0/1 = 0	a22 = 0x0 +1 = 1		a32 = 0x(-1) + 2 = 2		a42 = 0(5) +(-2) = -2
a13 = 1/1 = 1	a23 = 1x0 + 0 = 0		a33 = 1x(-1) + 0 = -1		a43 = 1(5) + 0 = 5
a14 = 0/1 = 0 	a24 = 0x0 + 1 = 1		a34 = 0x(-1) + 0 = 0		a44 = (5) + 0 = 0
a15 = 0/1 = 0	a25 = 0x0 + 0 = 0		a35 = 0x(-1) + 1 = 1		a45 = 0(5) + 0 = 0
a16 = 3/1 = 3	a26 = 3x0 + 4 = 4		a36 = 3x(-1) + 9 = 6		a46 = 3(5) + 0 = 15
Com esses valores na função objetivo temos Z = 15
Mas como ainda existem coeficientes negativos na linha Z a solução ainda não é ótima.
Obtenção das linhas do quadro Quadro 3:
LPN= LP/EP=	L1’ = LPN(0) + L1=		L2’ = LPN(-1) + L2		L4’ = LPN(2) + L4
a11 = 0/2 = 0	a11 = 1x0 + 0 = 0		a21 = 1x(-1) + 0 = 0	a41 = 1x(2) + 0 = 0
a12 = 2/2 = 1	a12 = 0x0 +1 = 1		a22 = 0x(-1) + 1 = 0	a42 = 0x(2) +(-2) = -2
a13 = -1/2 = -1/2	a13 = -1/2x0 + 0 = 0	a23 = -1/2x(-1) + 0 = 1/2	a43 = -1/2x(2)+ 5 = -1
a14 = 0/2 = 0 	a14 = 0x0 + 1 = 1		a24 = 0x(-1) + 1 = 1	a44 = 0x(2) + 0 = 0
a15 = 1/2 = 1/2	a15 = 1/2x0 + 0 = 0	a25 = 1/2x(-1) + 0 =-1/2	a45 = 1/2x(2) + 0 = 1
a16 = 6/2 = 3	a16 = 3x0 + 4 = 4		a26 = 3x(-1) + 4 = 1	a46 = 3x(2) + 15 = 21
Com esses valores na função objetivo temos Z = 21
Como todos os coeficientes da linha Z são positivos a solução é ótima. 
Solução:
x1 = 3
x2 = 3
Zmáx = 21
Exemplo 02: SIMPLEX 
Máx Z = 3x1 + 5x2
�sa:
	x1
	
	
	(
	4
	(1)
	
	
	2x2
	(
	12
	(2)
	3x1
	+
	2x2
	(
	18
	(3)
Considere o modelo de programação linear abaixo:
Max Z = 3x1 + 5x2,			(0)
Sujeito a
	x1
	
	
	(
	4
	(1)
	
	
	2x2
	(
	12
	(2)
	3x1
	+
	2x2
	(
	18
	(3)
e
xj ( 0, para j = 1 e 2.
Pela introdução de variáveis de folga de maneira idêntica para as outras variáveis funcionais, o modelo de programação linear original pode ser substituído pelo equivalente.
Maximizar Z
	Z
	-
	3x1
	-
	5 x2
	
	
	
	
	
	
	=
	0
	(0)
	
	
	x1
	
	
	+
	x3
	
	
	
	
	(
	4
	(1)
	
	
	
	
	2x2
	
	
	+
	x4
	
	
	(
	12
	(2)
	
	
	3x1
	+
	2x2
	
	
	
	
	+
	x5
	(
	18
	(3)
exj ( 0, para j = 1, 2, 3, ..., 5.
É como se a Eq. (0) de fato fosse uma das restrições originais, mas como ela já está em forma de igualdade, não é necessária nenhuma variável de folga.
Note-se que o sistema de restrições funcionais equações de (1) a (3) tem duas variáveis a mais que equações. Isto nos dá dois graus de liberdade na solução do sistema, uma vez que quaisquer duas variáveis podem ser escolhidas para serem consideradas iguais a qualquer valor arbitrário a fim de resolver as três equações em termos das três variáveis restantes (excetuando-se as redundâncias). O método Simplex usa o zero para este valor arbitrário.
As variáveis consideradas “zero” são chamadas de variáveis não-básicas, e as outras são chamadas de variáveis básicas. A solução resultante é chamada de solução básica. Se todas as variáveis básicas forem não-negativas tratar-se-á de uma solução básica viável.
O sistema de equações é resolvido repetidamente para uma seqüência de soluções básicas viáveis, cada uma melhor que a sua predecessora, até que seja alcançada uma solução (básica viável) ótima. Cada solução básica viável é obtida a partir de sua predecessora, transformando uma variável não-básica em uma variável básica (a variável básica entrando) e transformando uma variável básica numa variável não-básica (a variável básica saindo). Duas destas soluções básicas viáveis diferindo apenas por uma única troca de variáveis básica e não-básica são chamadas de adjacentes.
Método Simplex com Duas Fases
Consideremos o sistema:
Max Z = 5X1 + 2X2
 X1 ( 3
 X2 ( 4
 X1 + 2X2 ( 9
-X1 + 3X2 ( 3
 X1 + 3X2 ( 6
Como em todas as questões, X1 e X2 ( 0
Como o exemplo também envolve restrições do tipo (, caracteriza um problema de duas fases, além das varáveis de folga, introduziremos também variáveis artificiais e a respectiva função objetivo artificial.
1º Passo: Colocar a introdução das variáveis de folga, excesso e artificiais:
Z – 5X1 – 2X2 = 0
X1 + X3 = 3 (variável de folga)
X2 + X4 = 4 (variável de folga)
X1 + 2X2 + X5 = 9 (variável de folga)
-X1 + 3X2 - X6 +X8 = 3 (variável de excesso e variável artificial)
X1 + 3X2 - X7 + X9 = 6 (variável de excesso e variável artificial)
2º Passo: Introdução da função objetivo artificial:
- Para todas as variáveis reais e de folga, o coeficiente da função artificial será a soma dos coeficientes destas variáveis, ou seja:
dj = a1j + a2j + ... + amj
- Zero para as variáveis artificiais.
O valor inicial da função-objetivo artificial é a soma dos termos independentes das restrições.
Em nosso exemplo:
Restrições:
-X1 + 3X2 +X8 - X6 = 3 ( X8= X1-3X2+X6+3
X1 + 3X2 +X9 - X7 = 6 ( X9= -X1-3X2+X7+6
Função objetivo artificial:
W= X8 + X9
W = -6X2 + X6 + X7 + 9 ( -6X2 + X6 + X7 = -9 
A partir daí, podemos montar o quadro inicial e desenvolver o algoritmo:
	 
	W
	Z
	X1
	X2
	X3
	X4
	X5
	X6
	X7
	X8
	X9
	b
	Cálculo
	W
	-1
	0
	0
	-6
	0
	0
	0
	1
	1
	0
	0
	-9
	
	Z
	0
	1
	-5
	-2
	0
	0
	0
	0
	0
	0
	0
	0
	
	X3
	0
	0
	1
	0
	1
	0
	0
	0
	0
	0
	0
	3
	
	X4
	0
	0
	0
	1
	0
	1
	0
	0
	0
	0
	0
	4
	4
	X5
	0
	0
	1
	2
	0
	0
	1
	0
	0
	0
	0
	9
	4,5
	X8
	0
	0
	-1
	3
	0
	0
	0
	-1
	0
	1
	0
	3
	1
	X9
	0
	0
	1
	3
	0
	0
	0
	0
	-1
	0
	1
	6
	2
Observações:
A variável X2 é a que entra na base pelo fato de corresponder na linha –W ao menor coeficiente (-6), não levando em consideração à coluna “b”.
A variável X8 sai da base para ser substituída por X2 pelo fato de ter a menor divisão bi/ais (menor divisão positiva).
Constate que as variáveis artificiais iniciam na base. A 1ª fase do Simplex buscará deixá-las como não-básicas.
Continuando o Método Simplex:
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	W
	Z
	X1
	X2
	X3
	X4
	X5
	X6
	X7
	X8
	X9
	b
	Cálculo
	
	W
	-1
	0
	-2
	0
	0
	0
	0
	-1
	1
	2
	0
	-3
	
	
	Z
	0
	1
	-5 2/3
	0
	0
	0
	0
	- 2/3
	0
	2/3
	0
	2
	
	
	X3
	0
	0
	1
	0
	1
	0
	0
	0
	0
	0
	0
	3
	3
	
	X4
	0
	0
	1/3
	0
	0
	1
	0
	1/3
	0
	- 1/3
	0
	3
	9
	
	X5
	0
	0
	1 2/3
	0
	0
	0
	1
	2/3
	0
	- 2/3
	0
	7
	4,2
	
	X2
	0
	0
	- 1/3
	1
	0
	0
	0
	- 1/3
	0
	1/3
	0
	1
	
	
	X9
	0
	0
	2
	0
	0
	0
	0
	1
	-1
	-1
	1
	3
	1,5
	 
	W
	Z
	X1
	X2
	X3
	X4
	X5
	X6
	X7
	X8
	X9
	b
	W
	-1 
	0 
	0 
	0 
	0 
	0 
	0 
	0 
	0 
	1 
	1 
	0 
	Z
	0 
	1 
	0 
	0 
	0 
	0 
	0 
	2 1/6
	-2 5/6
	-2 1/6
	2 5/6
	10 1/2
	X3
	0 
	0 
	0 
	0 
	1 
	0 
	0 
	- 1/2
	 1/2
	 1/2
	- 1/2
	1 1/2
	X4
	0 
	0 
	0 
	0 
	0 
	1 
	0 
	 1/6
	 1/6
	- 1/6
	- 1/6
	2 1/2
	X5
	0 
	0 
	0 
	0 
	0 
	0 
	1 
	- 1/6
	 5/6
	 1/6
	- 5/6
	4 1/2
	X2
	0 
	0 
	0 
	1 
	0 
	0 
	0 
	- 1/6
	- 1/6
	 1/6
	 1/6
	1 1/2
	X1
	0 
	0 
	1 
	0 
	0 
	0 
	0 
	 1/2
	- 1/2
	- 1/2
	 1/2
	1 1/2
FIM DA 1ª FASE, pois: todas as variáveis artificiais estão fora da base e o valor de W é ZERO.
No quadro acima todos os coeficientes da FUNÇÃO OBJETIVO ARTIFICIAL são maiores ou iguais a zero, fim da fase I, e damos continuidade resolutiva com o problema na Fase II.
Abandonar a função objetivo artificial e as variáveis artificiais.
	
	
	
	
	
	
	
	
	
	
	
	
	
	 
	Z
	X1
	X2
	X3
	X4
	X5
	X6
	X7
	b
	Cálculo
	
	Z
	1 
	0 
	0 
	0 
	0 
	0 
	2 1/6
	-2 5/6
	10 1/2
	
	
	X3
	0 
	0 
	0 
	1 
	0 
	0 
	- 1/2
	 1/2
	1 1/2
	3 
	
	X4
	0 
	0 
	0 
	0 
	1 
	0 
	 1/6
	 1/6
	2 1/2
	15 
	
	X5
	0 
	0 
	0 
	0 
	0 
	1 
	- 1/6
	 5/6
	4 1/2
	5 2/5
	
	X2
	0 
	0 
	1 
	0 
	0 
	0 
	- 1/6
	- 1/6
	1 1/2
	
	
	X1
	0 
	1 
	0 
	0 
	0 
	0 
	 1/2
	- 1/2
	1 1/2
	
Observações:
A variável X7 é a que entra na base pelo fato de corresponder na linha Z ao menor coeficiente (-2 5/6);
A variável X3 sai da base para ser substituída por X7 pelo fato de ter a menor divisão bi/ais (menor divisão positiva).
	
	
	
	
	
	
	
	
	
	
	
	
	
	 
	Z
	X1
	X2
	X3
	X4
	X5
	X6
	X7
	b
	Cálculo
	
	Z
	1 
	0 
	0 
	5 2/3
	0 
	0 
	- 2/3
	0 
	19 
	
	
	X7
	0 
	0 
	0 
	2 
	0 
	0 
	-1 
	1 
	3 
	
	
	X4
	0 
	0 
	0 
	- 1/3
	1 
	0 
	 1/3
	0 
	2 
	6 
	
	X5
	0 
	0 
	0 
	-1 2/3
	0 
	1 
	 2/3
	0 
	2 
	3 
	
	X2
	0 
	0 
	1 
	 1/3
	0 
	0 
	- 1/3
	0 
	2 
	
	
	X1
	0 
	1 
	0 
	1 
	0 
	0 
	0 
	0 
	3 
	
	 
	Z
	X1
	X2
	X3
	X4
	X5
	X6
	X7
	b
	Z
	1 
	0 
	0 
	4 
	0 
	1 
	0 
	0 
	21 
	X7
	0 
	0 
	0 
	- 1/2
	0 
	1 1/2
	0 
	1 
	6 
	X4
	0 
	0 
	0 
	 1/2
	1 
	- 1/2
	0 
	0 
	1 
	X6
	0 
	0 
	0 
	-2 1/2
	0 
	1 1/2
	1 
	0 
	3 
	X2
	0 
	0 
	1 
	- 1/2
	0 
	 1/2
	0 
	0 
	3 
	X1
	0 
	1 
	0 
	1 
	0 
	0 
	0 
	0 
	3 
	
	
	
	
	
	
	
	
	
	
	
	Resultado:
	Z= 21
	
	X4=1
	
	
	
	
	
	
	
	X1=3
	
	X5=0
	
	
	
	
	
	
	
	X2=3
	
	X6=3
	
	
	
	
	
	
	
	X3=0
	
	X7=6
	
	
	
	
	
Quadro com solução ótima: todos os coeficientes na linha “Z” (função objetivo) são ( 0.
�
DUALIDADE
O Problema Dual
Todo problema de maximização ou minimização em programação linear tem um problema correspondentede minimização ou maximização associado;
O problema original é chamado PRIMAL e o correspondente é chamado DUAL.
Exemplo:
O PRIMAL
Max Z = c1x1 + c2x2+ ... + cnxn
S.a. 
CORRESPONDE AO DUAL
Min W = b1y1 + b2y2+ ... + bmym
S.a. 
Onde as regras para passar do PRIMAL para o DUAL são as seguintes:
A direção de otimização é invertida. Se o PRIMAL é maximização o seu DUAL será minimização;
Os coeficientes da função objetivo no PRIMAL (c1, c2, c3, ..., cn) correspondem às constantes dos segundos membros das equações de restrição do DUAL;
Os segundos membros das restrições do PRIMAL (b1, b2, b3, .., bm) correspondem aos coeficientes da função objetivo do DUAL;
A matriz A dos coeficientes no PRIMAL é transposta para construir a matriz dos coef. do DUAL, isto é, se a matriz dos coeficientes do PRIMAL é A, a do DUAL será At
Exemplo: determine o DUAL
 O dual será 
 
Obs. Se existem 2 variáveis (x1 e x2) e 3 restrições no primal, teremos 3 variáveis (y1 , y2 e y3) e 2 restrições no dual.
Obs:
	PRIMAL
	DUAL
	Max
	Min
	Restrição (
	Variável de decisão ( 0
	Variável de decisão ( 0
	Restrição ( 
	Variável livre
	Restrição =
	Restrição =
	Variável livre
A solução de um problema DUAL fornece também a solução do PRIMAL e vice-versa;
As variáveis de decisão do PRIMAL correspondem às de folga do DUAL, as de folga do DUAL correspondem às de decisão do PRIMAL;
Os valores ótimos das variáveis de decisão do DUAL, correspondem aos valores dos coef. das variáveis de folga (excesso) do PRIMAL, na equação Z do quadro final do simplex;
Para encontrar o DUAL de um problema PRIMAL temos que antes passar o problema para a forma standard (todas as restrições ( e o problema ser de max);
�
ANALISE DE SENSIBILIDADE
Interpretação de resultados de um problema de Programação Linear
A análise econômica baseia-se nos coeficientes das variáveis e na função objetivo final. Vamos lembrar que: 
O quadro final de um modelo de programação linear apresenta variáveis básicas e não básicas.
A função objetivo está escrita em termos das variáveis não básicas.
Os valores das variáveis básicas estão na coluna b. O valor das variáveis não básicas é zero.
O coeficiente da variável não básica na função objetivo mede a tendência do objetivo com aquela variável. É um valor marginal, indica a variação proporcional no objetivo para pequenos aumentos ou diminuições na variável. 
Posteriormente, em análise de sensibilidade podemos verificar até quantas unidades podemos aumentar ou diminuir da variável, sem alterar a informação contida no seu coeficiente. Esses coeficientes são chamados preços de oportunidade (preços relativos ao programa desenvolvido).
No quadro final, a solução é ótima. Um aumento de zero para um na variável não básica prejudica o objetivo. (lucros diminuem, custos aumentam, etc).
Alterações no lucro podem significar alterações em duas outras variáveis: receita e custo.
Exemplo 1:
No programa de produção para o próximo período, a empresa Beta Ltda., escolheu três produtos P1, P2 e P3. O quadro abaixo mostra os montantes solicitados por unidade de produção.
	Produto
	Contribuição
(lucro/unid.)
	Horas de trabalho
	Horas de uso de máquinas
	Demanda máxima
	P1
	2100
	6
	12
	800
	P2
	1200
	4
	6
	600
	P3
	600
	6
	2
	600
Os preços de venda foram afixados por decisão política e as demandas foram estimadas tendo em vista esses preços. A firma pode obter um suprimento de 4800 horas de trabalho durante o período de processamento e pressupõe-se usar três máquinas que podem prover 7200 horas de trabalho. Estabelecer um programa ótimo de produção para o período.
Solução:
a) Variáveis de decisão:
X1= Quantidade a produzir de P1
X2= Quantidade a produzir de P2
X3= Quantidade a produzir de P3
b) Função Objetivo: Max L= 2100X1 + 1200X2 + 600X3
c) Restrições:
6X1 + 4X2 + 6X3 ≤ 4800
12X1 + 6X2 + 2X3 ≤ 7200
X1 ≤ 800
X2 ≤ 600
X3 ≤ 600
X1; X2; X3 ≥ 0
Resultados do Problema:
a) Pelo SIMPLEX:
O quadro final do simplex é o seguinte:
	
	Z
	X1
	X2
	X3
	Xf1
	Xf2
	Xf3
	Xf4
	Xf5
	b
	
	1
	0
	0
	0
	50
	150
	0
	100
	0
	1.380.000
	X3
	0
	0
	0
	1
	0,2
	-0,1
	0
	-0,2
	0
	120
	X1
	0
	1
	0
	0
	-0,03
	0,1
	0
	-0,47
	0
	280
	Xf3
	0
	0
	0
	0
	0,03
	-0,1
	1
	0,47
	0
	520
	X2
	0
	0
	1
	0
	0
	0
	0
	1
	0
	600
	Xf5
	0
	0
	0
	0
	0,2
	0,1
	0
	0,2
	1
	480
b) Pelo LINDO:
O resultado no relatório do LINDO é:
 LP OPTIMUM FOUND AT STEP 3
 OBJECTIVE FUNCTION VALUE
 1) 1380000.
 VARIABLE VALUE REDUCED COST
 X1 280.000000 0.000000
 X2 600.000000 0.000000
 X3 120.000000 0.000000
 ROW SLACK OR SURPLUS DUAL PRICES
 2) 0.000000 50.000000
 3) 0.000000 150.000000
 4) 520.000000 0.000000
 5) 0.000000 100.000000
 6) 480.000000 0.000000
 NO. ITERATIONS= 3
Interpretação dos resultados do programa:
A resposta do problema é a mesma indiferente do método utilizado para sua resolução:
Lucro máximo: R$ 1.380.000,00
Produzir no período:
280 unidades de P1.
600 unidades de P2.
120 unidades de P3.
Recursos disponíveis após o programa:
520 unidades do mercado de P1.
480 unidades do mercado de P3.
Preços de oportunidade para os recursos:
R$50,00 para “hora de trabalho”.
R$150,00 para “hora de máquina”.
R$100 para “P2”.
A Análise Econômica
A análise econômica é feita sobre os preços de oportunidade dos resultados do problema. Apresentam-se abaixo as análises econômicas do Exemplo 1:
a) O preço de oportunidade do recurso “horas de trabalho” (coeficiente Xf1 no quadro=50) indica que:
Se conseguirmos mais uma hora de trabalho aos custos correntes, poderemos aumentar nosso lucro em R$ 50,00, isto é, poderemos obter nova solução ótima com lucro de R$1.380.050,00.
Se uma hora a mais de trabalho acarreta o pagamento de adicional extra, o valor R$ 50,00 indica o limite máximo desse adicional.
Por exemplo: se o adicional for de R$ 20,00, a nova hora de trabalho implicará uma nova solução com lucro de R$ 30,00 a mais que o anterior, portanto o lucro de R$ 1.380.030,00.
Se houver falta de uma hora de trabalho, o lucro fica diminuído em R$50,00, caso não haja alteração no custo. Se essa alta for, por exemplo, pela ausência de um funcionário que não terá hora descontada, acrescentar esse valor ao prejuízo causado pela ausência do funcionário.
b) O preço de oportunidade do recurso “horas de máquina” (coeficiente de Xf2 no quadro=150), indica que:
Uma hora a menos de máquina, o que equivale a fazer Xf2=1, acarreta uma diminuição no lucro de 150. A nova solução ótima nesse caso teria lucro de R$1.379.850,00 desde que não haja alteração nos custos correntes.
Contratar mais uma hora de máquina aos custos correntes significa um acréscimo de 150 no lucro. Se esse contrato implica adicional extra, ele deve ser descontado. No caso de aluguel de hora de máquina de terceiros para o programa, o preço de oportunidade R$150,00 indica o máximo que podemos pagar pelo aluguel além de nosso custo corrente. Por exemplo, se nosso custo corrente for R$500,00, alugar uma hora de máquina por menos de R$650,00 aumenta nosso lucro. Esse aumento corresponde à diferença entre R$650,00 e o valor do aluguel.
Em termos de manutenção e substituição de máquinas, o preço de oportunidade oferece informação para o cálculo do prejuízo devido à quebra e manutenção de uma máquina operando no programa. Sehá uma probabilidade de 80% de que uma máquina necessite de uma hora para conserto durante o programa, então, há uma expectativa de: 150 X 0,8 = 120 de prejuízo com esse evento (quebra da máquina) no programa, além dos custos pela manutenção.
c) O preço de oportunidade do recurso “mercado de P1” (coeficiente Xf3 no quadro=0) indica que esse recurso não é escasso. O mesmo ocorre com o preço de oportunidade do recurso “mercado de P3”. Isto pode nos levar a rever o investimento no mercado desses dois produtos. Uma diminuição desses investimentos com conseqüente diminuição do mercado, não afetará nossas vendas, causando um aumento no lucro. Outra maneira de aumentar o lucro neste caso é aumentar o preço de venda dos produtos P1 e P3. Isto diminui os mercados correspondentes sem afetar as vendas, desde que o mercado não diminua aquém da produção.
d) O preço de oportunidade do recurso “mercado de P2” (coeficiente Xf4 no quadro=100) indica que:
O aumento de uma unidade nesse mercado, aos custos correntes, acarreta um aumento de R$100,00 no lucro, isto é, a nova solução teria lucro de R$1.380.100.
Da mesma forma, o cancelamento de uma unidade na compra de um cliente implica um prejuízo de R$100,00, além do custo normal da unidade desse recurso.
Se o departamento de marketing da empresa estimar em R$80,00 o investimento adicional para aumentar em uma unidade o mercado do produto P2, esse investimento nos traria um retorno líquido de R$100-R$80=R$20, passando o lucro para R$1.380.020. Por investimento adicional entendemos o valor além do custo normal de vendas por unidade nesse mercado.
Análise de Sensibilidade
Ao construirmos um modelo de PL, são incluídas restrições cujos valores dependem do mercado e do processo utilizado na elaboração dos produtos. Estas restrições podem variar com o tempo ou com a inclusão de novas informações. É importante pesquisar a estabilidade da solução adotada, em face dessas variações. Ou seja, análise de sensibilidade é uma análise de como seria modificada a solução do problema pela alteração de algumas restrições. 
Após a solução deste problema, poderíamos perguntar, por exemplo: 
– O que aconteceria com a solução se o lucro unitário dos produtos variasse? 
 
O LINDO é capaz de efetuar o estudo da sensibilidade e ainda outros. Para isso, basta responder YES após a pergunta “Do Range (Sensitivity) Analysis?”, durante a resolução de um problema.
Caso decida estudar a sensibilidade num momento posterior à resolução do problema, basta seguir os seguintes passos: 
a) No menu principal, clique em “Reports”; 
b) Clique em Range 
 
Então aparecerá um relatório com o formato mostrado a seguir: 
RANGES IN WHICH THE BASIS IS UNCHANGED:
 OBJ COEFFICIENT RANGES
 VARIABLE CURRENT ALLOWABLE ALLOWABLE
 COEF INCREASE DECREASE
 X1 2100.000000 214.285721 1500.000000
 X2 1200.000000 INFINITY 100.000000
 X3 600.000000 500.000000 250.000000
 RIGHTHAND SIDE RANGES
 ROW CURRENT ALLOWABLE ALLOWABLE
 RHS INCREASE DECREASE
 2 4800.000000 2400.000000 600.000000
 3 7200.000000 1200.000000 2800.000000
 4 800.000000 INFINITY 520.000000
 5 600.000000 600.000000 600.000000
 6 600.000000 INFINITY 480.000000
Este relatório contempla intervalos nos quais a base do problema não sofrerá modificações.
RANGES IN WICH THE BASIS IS UNCHANGED
(Intervalo no qual a base não é modificada)
Nesta seção, temos uma análise de validade da solução para: 
Coeficientes das variáveis da função objetivo; 
Limites das restrições. 
a) Coeficientes das variáveis da função objetivo (OBJ COEFFICIENT RANGES):
Nesta seção serão analisados os coeficientes da função objetivo, que no nosso Exemplo 1 são 2100 (P1), 1200 (P2) e 600 (P3). 
VARIABLE CURRENT ALLOWABLE ALLOWABLE
 COEF INCREASE DECREASE
 X1 2100.000000 214.285721 1500.000000
 X2 1200.000000 INFINITY 100.000000
 X3 600.000000 500.000000 250.000000
Podemos observar que: 
Pela linha de X1, o coeficiente, ou seja, o lucro unitário de P1 foi R$2100,00 e que este coeficiente pode variar entre R$ 600,00 (2100–1500) e R$ 2314,29 (2100+214,29), que manteremos a mesma solução (X1 =280; X2=600 e X3 =120). 
Pela linha de X2, o coeficiente foi R$ 1200,00 e que este coeficiente pode variar entre R$ 1100,00 (1200–100) e infinito, que manteremos a mesma solução (X1 =280; X2=600 e X3 =120).
pela linha de X3, o coeficiente, ou seja, o lucro unitário de P3 foi R$600,00 e que este coeficiente pode variar entre R$ 350,00 (600–250) e R$ 1100,00 (600+500), que manteremos a mesma solução (X1 =280; X2=600 e X3 =120). 
b) Limites das restrições (RIGHTHAND SIDE RANGES):
 Nesta seção obteremos uma análise dos limites das restrições, também conhecidos como RHS (Right Hand Side). 
O resultado do exemplo 1 é:
 RIGHTHAND SIDE RANGES
 ROW CURRENT ALLOWABLE ALLOWABLE
 RHS INCREASE DECREASE
 2 4800.000000 2400.000000 600.000000
 3 7200.000000 1200.000000 2800.000000
 4 800.000000 INFINITY 520.000000
 5 600.000000 600.000000 600.000000
 6 600.000000 INFINITY 480.000000
Vamos a seguir ver o significado de cada coluna: 
CURRENT RHS: Significa o limite corrente, ou atual, desta restrição; 
ALLOWABLE INCREASE: Significa de quantas unidades o limite pode ser aumentado, ou seja, quantas unidades adicionais podem ser incorporadas ao problema para que o lucro tenha um aumento constante por unidade. Este aumento está mostrado na coluna DUAL PRICES da resposta principal. 
ALLOWABLE DECREASE: Significa de quantas unidades o limite pode ser diminuído, ou seja, quantas unidades podem ser retiradas do problema para que o lucro tenha um decréscimo constante por unidade. Este decréscimo é o mesmo valor mostrado na coluna DUAL PRICES da resposta principal. 
Então, faz-se a análise de sensibilidade por linha, ou seja, para cada restrição. Pode-se começar por qualquer linha ou restrição. Neste exemplo, optou-se por iniciar pelas linhas 2,3 e 5 por não terem folga (XF1=XF2=XF4=0).
Linha 2)
CURRENT RHS: Limite atual desta restrição é 4800; 
ALLOWABLE INCREASE: O limite pode ser aumentado em 2400 horas, ou seja, passando de 4800 para 7200 horas, tendo um aumento no lucro de R$ 50,00 por unidade acrescentada. 
ALLOWABLE DECREASE: O limite pode ser diminuído em 600 unidades, ou seja, passando de 4800 para 7200 horas, tendo uma diminuição no lucro de R$ 50,00 por unidade diminuída. 
Linha 3) 
CURRENT RHS: Limite atual desta restrição  7200; 
ALLOWABLE INCREASE: O limite pode ser aumentado em 1200 horas, ou seja, passando de 7200 para 8400 horas, tendo um aumento no lucro de R$ 150,00 por hora acrescentada. 
ALLOWABLE DECREASE: O limite pode ser diminuído em 4800 unidades, ou seja, passando de 7200 para 2400 horas, tendo uma diminuição no lucro de R$ 150,00 por unidade diminuída. 
Linha 5)
CURRENT RHS: Limite atual desta restrição  600; 
ALLOWABLE INCREASE: O limite pode ser aumentado em 600 unidades, ou seja, passando de 600 para 1200 unidades de P2, tendo um