PESQUISA OPERACIONAL matéria

Prévia do material em texto

PESQUISA OPERACIONAL
AULA 1 – INTRODUÇÃO À PESQUISA OPERACIONAL
O Que é Pesquisa Operacional?
A Pesquisa Operacional, como o próprio nome já diz, abrange a pesquisa sobre operações, atividades ou ainda é utilizada em problemas para se resolver como coordenar e conduzir as operações, as atividades em uma organização. A Pesquisa Operacional (Operational Research) é considerada uma ciência aplicada, um método científico para se tratar modelos matemáticos complexos, preocupando-se em orientar na tomada de decisões.
Qual a Origem da Pesquisa Operacional?
A origem da Pesquisa Operacional deu-se em torno de 1939 na Inglaterra, durante a Segunda Guerra Mundial. O aparecimento da Pesquisa Operacional é creditado a estudos feitos por cientistas contratados para criar e aperfeiçoar estratégias e táticas militares, na época, limitadas. Ravindran (1986), em seu livro Operations Research, Principles and Practice, esclarece que os problemas de Pesquisa Operacional existem há muito tempo, no entanto, somente a partir da Segunda Grande Guerra passou a ser tratados sob uma abordagem organizada, em uma disciplina ou área do conhecimento.
(RAVINDRAN, A. PHILLIPS, D.T. & Solberg, J.J.Operations research, principles and practice. 2. Ed. New York: John Wiley, 1987.)
Sabe-se que os primeiros casos de aplicação da Pesquisa Operacional reportados foram de caráter militar (TREFETHEN, 1954). Após o final da Segunda Grande Guerra somente, a Pequisa Operacional começou a estudar problemas ditos civis. (TREFETHEN, F.N. A history of operations research. In: J.F. MCCLOSKEY & F.N. Operations Research for Management, Trefethen EdsJohns Hopkins Press, 1954)
Trefethen (1954), em seu livro nos traz detalhes sobre a origem da Pesquisa Operacional.
Na verdade, durante muitos anos, a Pesquisa Operacional foi estudada e usada somente nas organizações militares. Por conta do sucesso atingido por essa ciência, no que diz respeito a atingir objetivos e metas, as grandes empresas começaram a utilizá-la. A propagação da Pesquisa Operacional nos Estados Unidos durante e após a guerra pode ser creditada principalmente à equipe de cientistas liderada por George B. Dantzig, equipe esta que foi convocada durante a guerra. No Brasil, a Pesquisa Operacional só surgiu no início da década de 60. Em 1969, foi fundada a Sociedade Brasileira de Pesquisa Operacional (SOBRAPO).
Podemos dizer que um modelo é uma representação de um sistema real. Se o sistema já existir, o modelo deve pretender reproduzir o funcionamento do sistema, de modo a aumentar sua produtividade. No caso de se tratar de um projeto a ser executado, o modelo é utilizado para definir a estrutura ideal do sistema. Um modelo matemático é composto por três conjuntos principais de elementos:
As variáveis de decisão e parâmetros - As variáveis de decisão são as incógnitas a serem determinadas pela solução do modelo, enquanto que os parâmetros são valores fixos no problema.
As restrições - Utilizadas para levar em conta as limitações físicas do sistema, as restrições limitam as variáveis de decisão a seus valores possíveis ou viáveis.
Função – objetivo - É uma função matemática que define o objetivo da solução em função das variáveis de decisão.
A formulação do modelo depende diretamente do sistema que precisa ser representado do problema em questão. A função-objetivo e as funções de restrições podem ser lineares ou não lineares. As variáveis de decisão podem ser contínuas ou discretas, como, por exemplo, variáveis inteiras ou mesmo binárias, e os parâmetros podem ser determinísticos ou probabilísticos. 
Exemplos de Modelagem – Problema do Alfaiate
Vamos ver alguns exemplos de modelagem que encontramos na literatura.
Um alfaiate tem disponíveis os seguintes tecidos: 16 metros de algodão, 11 metros de seda e 15 metros de lã. Para um terno, são necessários 2 metros de algodão, 1 metro de seda e 1 metro de lã. Para um vestido, é necessário 1 metro de algodão, 2 metros de seda e 3 metros de lã. Se um terno é vendido por $300,00 e um vestido por $500,00, modele este problema de forma a determinar quantas peças de cada tipo o alfaiate deve fazer de modo a maximizar o seu lucro.
Resolvendo: 
Exemplos de Modelagem – Problema dos Caminhões
Uma companhia de aluguel de caminhões possuía dois tipos de caminhões: o tipo A, com 2 metros cúbicos de espaço refrigerado e 4 metros cúbicos de espaço não refrigerado, e o tipo B, com 3 metros cúbicos refrigerados e 3 não refrigerados. Uma fábrica precisou transportar 90 metros cúbicos de produto refrigerado e 120 metros cúbicos de produto não refrigerado. Quantos caminhões de cada tipo ela deve alugar, de modo a minimizar o custo, se o aluguel do caminhão A era $0,30 por km e o do B, $0,40 por km? Elabore o modelo de programação linear que represente esta situação.
Exemplos de Modelagem – Problema da Fábrica de Vidro
Uma determinada companhia é grande fabricante de vidros de alta qualidade, produzindo um grande número de portas e janelas de vidro. A companhia possui 3 fábricas, sendo que na fábrica 1 são feitas as esquadrias de alumínio, na fábrica 2 são feitas as esquadrias de madeira e na 3 os produtos (portas e janelas) são montados. Como os lucros estão caindo, a diretoria resolveu parar a produção de alguns produtos que não estão vendendo bem. Para aproveitar a ociosidade que irá surgir no parque de produção, dois novos produtos serão lançados no mercado. Um desses produtos (produto1) é uma porta de vidro com esquadrias de alumínio e o outro (produto 2) é uma janela com esquadrias de madeira. Após uma pesquisa de mercado, o Departamento de Vendas concluiu que esses 2 novos produtos terão grande aceitação e todas as unidades produzidas serão vendidas. As informações disponíveis, por dia, para a produção desses 2 novos produtos estão mostrados na tabela a seguir. 
 O objetivo da companhia é maximizar o seu lucro com a produção e venda desses dois produtos. 
Exemplos de Modelagem – Problema da Confecção
A programação da produção é realizada por lotes de produto. O Departamento de Produção informa que são necessários 10 homens/hora para um lote de calças e 20 homens/hora para um lote de camisas. Sabe-se que não é necessária a mão de obra especializada para a produção de calças, mas são necessários 10 homens/hora desse tipo de mão de obra para produzir um lote de camisas. O Departamento De Pessoal informa que a força máxima de trabalho disponível é de 30 homens/hora de operários especializados e de 50 homens/hora de não especializados. Da planta de produção, sabemos que existem apenas duas máquinas com capacidade de produzir os dois tipos de produto, sendo que a máquina 1 pode produzir um lote de calças a cada 20 horas, e um lote de camisas a cada 10 horas, não podendo ser utilizada por mais de 80 horas no período considerado. A máquina 2 pode produzir um lote de calças a cada 30 horas e um lote de camisas a cada 35 horas, não podendo ser utilizada por mais de 130 horas no período considerado. São necessários dois tipos de matéria-prima para produzir calças e camisas. Na produção de um lote de calças, são utilizados 12 quilos de matéria-prima A e 10 da B. Na produção de um lote de camisas, são utilizados 8 quilos da matéria-prima A e 15 da B. 
As fases do Estudo de Pesquisa Operacional
Um estudo de pesquisa operacional geralmente envolve as seguintes fases: Ainda que a sequência acima não seja rígida, ela nos indica as principais etapas a serem vencidas.
 Definição do Problema - A definição do problema baseia-se em três aspectos principais:
Descrição exata dos objetivos do estudo;
Identificaçãodas alternativas de decisão existentes;
Reconhecimento das limitações, restrições e exigências do sistema.
A descrição dos objetivos é muito importante em todo o processo, pois, a partir desta definição, o modelo é concebido. É essencial também 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.
Construção do Modelo - É preciso se escolher bem o modelo para que a solução tenha qualidade. Se o modelo que se elaborou tem a forma de um modelo conhecido, podemos obter a solução através de métodos matemáticos convencionais. Se o modelo tiver relações matemáticas muito complexas, precisaremos utilizar combinações de metodologias.
Solução do Modelo - Nesta fase de procurar e encontrar uma solução para o modelo proposto, geralmente utilizamos técnicas matemáticas existentes. Se isso não for possível, cria-se um novo algoritmo, mais adequado, no que diz respeito a tempo e precisão de resposta. Tanto a utilização de técnicas existentes quanto a criação de algoritmos exige um conhecimento profundo das técnicas existentes.
Validação do Modelo - Um modelo é válido se ele for capaz de fornecer uma previsão aceitável do comportamento do sistema. Um método comum de validação do modelo é analisar seu desempenho com dados antigos e verificar se os resultados conseguem reproduzir o comportamento que o sistema apresentou anteriormente.
Implementação da Solução - Agora é o momento de se investir em regras operacionais. Eventualmente, os valores da nova solução, quando levados à prática, podem demonstrar a necessidade de correções, exigindo a reformulação do modelo em algumas de suas partes.
AULA 2 – INTRODUÇÃO À PESQUISA OPERACIONAL
O QUE A PROGRAMAÇÃO LINEAR PROCURA FAZER?
A Programação Linear se propõe a maximizar ou minimizar uma função linear, dita FUNÇÃO OBJETIVO, respeitando um sistema de igualdades ou desigualdades, de funções lineares. Estas funções lineares são as RESTRIÇÕES do modelo ou do problema.
SAIBA MAIS: De maneira geral, as restrições podem representar limitações de recursos disponíveis, como capital, mão de obra, recursos minerais, ou fatores de produção, ou mesmo condições, exigências ou necessidades que devem ser obedecidas no problema. No modelo, essas restrições determinam uma região, região esta que dizemos ser o CONJUNTO VIÁVEL para as soluções.
Que técnicas existem para encontrarmos uma solução ótima?  
Dentre as várias técnicas existentes para a determinação da solução, podemos citar:
Programa Linear - A Programação Linear é usada para analisar modelos onde as restrições e a Função Objetivo são lineares.
Programação Inteira - A Programação Inteira se aplica a modelos que possuem variáveis inteiras ou discretas.
Programação Dinâmica - A Programação Dinâmica é utilizada em modelos onde o problema completo pode ser decomposto em subproblemas.
Programação Estocástica - A Programação Estocástica é aplicada a modelos onde os parâmetros são descritos por funções de probabilidade.
Programação Não Linear - A Programação Não Linear é utilizada em modelos contendo funções não lineares.
A Formulação do Modelo de Programação Linear
Para se resolver um problema de Programação Linear, devemos formulá-lo definindo a Função Objetivo e as restrições e, para isso, precisamos definir as variáveis de decisão envolvidas. Definimos, a princípio, o objetivo do problema. Como exemplos de Função Objetivo, podemos ter os casos de maximizar lucros ou desempenhos, minimizar custos, perdas, ou tempo. Com relação às variáveis de decisão, de maneira geral, estas variáveis são não negativas, já que quase sempre são representativas de questões positivas. As variáveis de decisão e a Função Objetivo estão sujeitas a uma série de restrições, representadas por equações ou, na maioria das vezes, inequações.
Em um problema de Programação Linear, todas as funções envolvidas são lineares, em outras palavras, todas as relações entre as variáveis devem ser lineares, significando que as quantidades envolvidas são proporcionais de alguma forma. A linearidade pode ser uma característica determinante no que se refere à simplificação da estrutura matemática envolvida, no entanto pode ser problemática para se representar fenômenos não lineares. Considerando todas as decisões possíveis que satisfazem as restrições, as chamadas decisões viáveis, procuramos determinar aquela decisão que é a “melhor”, a solução ótima, àquela que proporciona maior contribuição total do lucro, menor custo, maior retorno: uma decisão ótima.
O Modelo de Problema de Programação Linear
Como sabemos então, o Problema de Programação Linear (PPL) é um problema de programação matemática em que a Função Objetivo e as restrições são funções lineares. 
Exemplo:
Certa empresa fabrica dois produtos P1 e P2. O lucro unitário do produto P1 é de 1000 unidades monetárias e o lucro unitário de P2 é de 1800 unidades monetárias. A empresa precisa de 20 horas para fabricar uma unidade de P1 e de 30 horas para fabricar uma unidade de P2. O tempo anual de produção disponível para isso é de 1200 horas. A demanda esperada para cada produto é de 40 unidades anuais para P1 e 30 unidades anuais para P2. Qual é o plano de produção para que a empresa maximize seu lucro nesses itens? Construa o modelo de Programação Linear para esse caso. Navegue na tela e veja como modelar o problema: 
Teoremas Importantes
A ideia do estudo de Programação Linear é encontrarmos a solução ótima dos problemas. Para isso, devemos atender aos teoremas cujos enunciados extraímos do livro Programação Linear como instrumento da pesquisa operacional, de Eduardo Jose Franco dos Passos. 
Resolução Gráfica
Quando temos somente duas variáveis de decisão, podemos encontrar a solução ótima graficamente. 
Vamos considerar a reta 2x1+x2=6 representada abaixo. Os pontos pertencentes a reta atendem à igualdade. Como determinar se os pontos (x1, x2) da região acima da reta são pontos de tal forma que 2x1+x2≤6 ou 2x1+x2≥6?
Uma sugestão é que você escolha um ponto, de preferência o (0,0) e substitua na equação 2x1+x2, verificando se este valor é maior ou menor que 6, no nosso caso.  Note que você precisa observar que a região que você encontrar (acima ou abaixo da reta) é aquela no qual o ponto (0,0) se localiza.
 No nosso exemplo, o ponto (0,0) está abaixo da reta. Substituindo (0,0) em 2x1+x2, obtemos 0, que é menor que 6. Assim, a região abaixo da reta 2x1+x2=6 é a região 2x1+x2≤6, pois o ponto (0,0) precisa atender à inequação.
 A região sinalizada em vermelho é a região 2x1+x2≤6.
Como resolver graficamente?
Primeiro, devemos estabelecer os eixos que irão representar as variáveis de decisão. Devemos construir um eixo com as dimensões x1 e x2. Encontrar o conjunto de soluções viáveis: a região viável. Precisamos identificar os valores (x1, x2) que são permitidos pelas restrições. Depois de traçarmos as inequações (que representam as restrições do problema), um poliedro convexo é formado. Este poliedro contém todas as soluções do problema, uma vez que qualquer ponto dentro desta região ou na aresta do poliedro atende às restrições do problema. Escolher o ponto da região viável que maximiza o valor da Função Objetivo. Esta escolha pode ser feita dando valores a z, a Função Objetivo, e observar o quanto podemos “melhorar” o valor de z, sem sair da região viável, clique no PDF.
Podemos também utilizar o vetor gradiente, que é formado pelos coeficientes da Função Objetivo (c1, c2). Este vetor tem a origem na origem dos eixos e, traçando perpendiculares a este vetor, podemos procurar o ponto utilizando estas perpendiculares. Clique no PDF.
Como resolvergraficamente um PPL?
AULA 3 – MÉTODO SIMPLEX
O Método Simplex foi desenvolvido em 1947 por George B. Dantzig. 
Vamos relembrar os teoremas que foram enunciados na última aula:
Teorema 1 - Se o problema de programação linear tem solução ótima, então esta solução está em, pelo menos, um ponto extremo do poliedro de soluções viáveis.
Teorema 2 - Se a região de soluções viáveis de um problema de programação linear é não vazia, então existe uma solução ótima.
Teorema 3 - O conjunto de soluções viáveis de um problema de programação linear é um conjunto convexo.
Teorema 4 - O conjunto de soluções viáveis de um problema de programação linear tem um número finito de pontos extremos (vértices).
Sabemos então que o conjunto de todas as soluções do problema de programação linear é um conjunto convexo cujos vértices, ou seja, cujos pontos extremos correspondem a soluções ditas básicas viáveis. Sabemos ainda que, se a função objetivo possui um máximo finito, então, pelo menos uma solução ótima é um ponto extremo do conjunto convexo.
Uma pequena metalúrgica deseja maximizar sua receita com a venda de dois tipos de finas fitas de aço que se diferenciam em qualidade no acabamento de corte. As fitas são produzidas a partir do corte de bobinas de grande largura. Existem duas máquinas em operação. Uma das máquinas é mais antiga e permite o corte diário de 4.000 m de fita. A outra, mais nova, corta até 6.000 m. A venda das chapas no mercado varia de acordo com a qualidade de cada uma. Fitas produzidas na máquina antiga permitem um lucro de 3 u.m por mil metros de produção. Fitas cortadas na máquina mais moderna produzem um lucro de 5 u.m por mil metros de produção. Cada mil metros de fita cortada na máquina antiga consome 3 homens x hora de mão de obra. Na máquina moderna são gastos apenas 2 homens x hora. Diariamente, são disponíveis 18 homens x hora para a operação de ambas as máquinas. Determine a produção que otimiza o lucro da metalúrgica.
 Incialmente, passe o modelo para a forma padrão. A forma padrão deverá ser passada para o quadro – tableau.
Q.1 
O quadro Q.1 não é ótimo, pois temos na linha da função objetivo – linha 1 - dois valores negativos: -3 e -5.  O quadro é ótimo quando todos os valores, nessa linha, são positivos. 
Variável que entra na coluna da base: X2 (procure o menor valor numérico)
Variável que sai da coluna da base: X4 (menor valor encontrado na divisão)
Avance a tela e monte o próximo quadro realizando a troca do anterior.
Q.2 
Localize no quadro anterior – na linha da variável que foi selecionada para sair da coluna da base (linha 3)  – o elemento pivô. O elemento pivô está localizado na coluna da variável selecionada para entrar na coluna da base. O pivô deverá ser 1 para facilitar os cálculos. Quando ele é 1 basta transferir a linha da variável selecionada para sair da coluna da base toda para o próximo quadro na mesma posição. O pivô localizado no Q.1  é 1, logo a linha 3 foi toda transferida para o Q.2. A linha 3 é a linha do pivô. Agora devemos zerar a coluna do pivô, isto é, zerar os quadrados acima e abaixo do pivô.
Zerar o -5 na linha 1 Zerar o 2 na linha 4 
O quadro Q.2 não é ótimo, pois ainda temos um valor negativo na linha da função objetivo – linha 1.
 Variável que entra na coluna da base: X1 (procure o menor valor numérico  - na linha 1: -3)
Variável que sai da coluna da base: X5 (menor valor encontrado na divisão)
Avance a tela e monte o próximo quadro – Q.3 - realizando a troca acima.
Q.3 
Localize no quadro anterior – Q.2 - na linha da variável que foi selecionada para sair da coluna da base (linha 4)  – o elemento pivô. 
O elemento pivô está localizado na coluna da variável selecionada para entrar na coluna da base. 
O pivô deverá ser 1 para facilitar os cálculos. Nesse caso, o pivô não é 1 e sim 3. 
A linha da variável deverá ser dividida por 3 para transformar o pivô em 1. 
Essa nova linha deverá ser transferida para o quadro Q.3 na mesma posição – linha 4. 
A linha 4 é a linha do pivô. 
Agora devemos zerar a coluna do pivô, isto é, zerar os quadrados acima e abaixo do pivô.
Zerar o -3 na linha 1
Zerar o 1 na linha 2
O quadro Q.3 é ótimo.
Z=36   x1=2   x2=6   x3=2   x4=0    x5=0
Problema de Minimização
E quando temos um problema de minimização? Basta transformarmos o problema de minimização em um problema equivalente de maximização e, então, utilizamos o Simplex. Essa transformação consiste em maximizar MENOS a função objetivo original. 
Min Z = Max (-Z) 
Depois de resolvê-lo pelo Simplex, encontrando (-Z), basta trocarmos o seu sinal.
Chegamos a final da nossa aula. É importante que você tenha compreendido bem o conteúdo. Não se esqueça de testar seus conhecimentos no Registro de Participação!
AULA 4 – MÉTODO SIMPLEX E SOFTWARES
O Solver do Excel 
Considere o Problema
 Este problema não está na forma padrão e não podemos, portanto, utilizar o Método Simplex. Vamos resolvê-lo com o auxílio do Solver do Excel. Para abrir o Solver basta ir à janela dos dados. Avance a tela e confira! 
 E se o Solver não estiver instalado? Bem, neste caso, basta ir a Arquivos
 Em seguida, clique em Opções.
 Irá abrir esta janela.
 E depois basta ir a Suplementos. O Solver estará listado e bastará você ativá-lo.
 Na função objetivo, as variáveis e as restrições precisam estar especificadas nas células do Excel.
 Defina as células onde estarão as variáveis e calcule a função objetivo e as restrições com fórmulas que utilizam essas células.
A Função Objetivo 
As Variáveis 
As Restrições 
A Solução do Solver
Relatório de Resposta
Chegamos ao final da nossa aula. Reveja esta atividade quantas vezes forem necessárias, assim você terá mais facilidade na hora de resolver os exercícios do Registro de Frequência! Até a próxima e bons estudos!
AULA 5 – O PROBLEMA DUAL
Eventualmente, queremos encontrar uma estimativa para a função Objetivo no ponto ótimo ao invés de encontrar a solução ótima utilizando o método Simplex, já nosso conhecido. Vamos chamar Z* o valor da função objetivo no ponto ótimo. Lembre-se que nós não sabemos quem é Z* e queremos determiná-lo.
Vamos procurar limites inferiores para Z*. Quanto menor for o limite superior que encontrarmos, melhor será.
Soluções viáveis fornecem limites inferiores.
Analise a equação:
 Como avaliar a qualidade do limite inferior obtido?Como saber se o limite está próximo da solução ótima? Comparando com um limite superior para a solução ótima. Avance a tela e confira!
Buscando Um Limite Superior para a Solução Ótima
Compararemos as restrições com a função Objetivo. 
 Como melhorar o limite superior? Como determinar os números pelos quais devemos multiplicar cada uma das restrições?
 
Buscando Um Limite Superior para a Solução Ótima
Note que este valor é um limite superior para o problema considerado. Observe ainda que queremos estabelecer o menor limite superior possível. 
Qualquer problema de programação linear possui, associado a ele, um outro problema de programação linear, chamado de Dual. O problema original é dito Primal.
A teoria de dualidade é importante para o estudo da interpretação e implementação da análise de sensibilidade.
O Problema Dual
 
Podemos escrever os problemas Primal e Dual também como:
Ou ainda:
Teoremas Importantes Envolvendo Problemas Primais e Duais
Se o problema for de:
Maximizar, então não pode haver restrição de maior ou igual;
Minimizar, então não pode haver restrição de menor ou igual.
Bem, e se essas condições não são atendidas no problema proposto?  Precisaremos então modificar o problema e só depois determinarmos o Dual.
Se x é solução viável de (P) e y é solução viável de (D), então c’x    b’y:
Se x é solução viável de (P) e y é solução viável de (D), então c’x   b’y. 
Se (P) é ilimitado, então (D) é inviável.
Se (D) é ilimitado, então (P) é inviável.
Se x e y são soluções viáveis de (P) e (D), e c’x= b’y,  então essas soluções são ótimas para os dois problemas.
Se (P) tem solução ótima x*, então (D) tem solução ótima y* e c’x* = b’y*.
Se x* é solução ótima de (P) e y* é solução ótima de (D), então x*’ (A’y*-c) = 0 e y*’ (Ax*-b) = 0 c’x* = y*’ Ax* = y*’ b.
SAIBA MAIS Vamos resolver, com o auxílio do Solver, os dois problemas do nosso exemplo: o problema Primal e o problema Dual.  Avance a tela e confira!
Agora, vamos observar um outro relatório, o de sensibilidade. Nele podemos observar as variáveis duais. Atente para os números na coluna chamada Multiplicadores de Lagrange
 
 Nota importante: os valores obtidos como Multiplicadores de Lagrange no Relatório do problema Primal são os valores das variáveis duais. 
AULA 6 – O PAR PRIMAL-DUAL
Teorema da Existência
Para um par de problemas duais... ... uma e somente uma das alternativas abaixo é satisfeita
A) Nenhum dos problemas tem solução. 
 B) Um deles não tem solução viável e o outro tem solução ótima ilimitada.
 C) Ambos possuem solução ótima finita.  Neste caso, o valor da solução ótima dos dois problemas é o mesmo.
Teorema da Existência - Problemas Inviáveis
Opção A) Nenhum dos problemas tem solução.
Avance a tela e acompanhe o passo a passo para a resolução do problema Primal com auxílio do SOLVER.
Resolvendo o Problema Primal com o auxílio do SOLVER. 
Observe que o SOLVER sinalizou que não foi possível encontrar uma solução viável para o Problema Primal.
Resolvendo o Problema Dual com o auxílio do SOLVER.
Observe que o SOLVER sinalizou que não foi possível encontrar uma solução viável para o Problema Primal.
Teorema da Existência
Opção B) Um deles não tem solução viável e o outro tem solução ótima ilimitada.
Avance a tela e acompanhe a resolução!
Teorema da Existência - Ilimitado e Inviável
Resolvendo o Problema Primal com o auxílio do SOLVER.
ATENÇÃO Note que o SOLVER sinalizou que o problema Primal é ilimitado.
ATENÇÃO O SOLVER sinalizou que o problema não é viável.
Teorema da Existência
Ambos possuem solução ótima finita. Neste caso, o valor da solução ótima dos dois problemas é o mesmo. Veja a resolução a seguir!
Teorema da Existência - Problemas com Solução Ótima Finita
Resolvendo o Problema Primal utilizando o SOLVER.
O Relatório de Resposta do Primal:
O Relatório de Sensibilidade do Primal:
Resolvendo o Problema Dual.
Relatório de Resposta do Dual:
Relatório de Sensibilidade do Dual:
Algoritmo Dual Simplex – Teorema da Dualidade
“Se um problema primal (dual) tem uma solução ótima finita, então o problema dual (primal), tem também uma solução ótima finita, as funções objetivo do primal e do dual têm valores iguais.”
Resolvendo pelo Simplex o problema Dual:
Quadro 1: 
Quadro final: 
 
Quadro 1 
Resolvendo pelo Dual
Quadro 1: 
Quadro final: 
Chegamos ao final desta aula! Não deixe de acessar o Registro de Participação e fazer as atividades propostas.
AULA 7 – INTERPRETAÇÃO ECONÔMICA DAS VARIÁVEIS DUAIS
PREÇO SOMBRA
Sabemos que cada variável yi do Problema Dual está relacionada à restrição i do problema Primal. Chamamos o valor ótimo da variável dual, yi*, de Preço Sombra (Shadow Price) ou Preço-Dual (Dual-Price). Os valores ótimos das variáveis duais, ou ainda os Preços-Sombra, podem ser interpretados como sendo os preços que alguém estaria disposto a pagar por unidades adicionais dos recursos envolvidos nas restrições do Primal. Assim, cada restrição i possui um Preço de Sombra yi*.
O Preço Sombra yi* referente ao recurso i fornece o valor marginal desse recurso em relação ao lucro total. A quantidade do Lucro Total (Z) pode ser melhorado, se a quantidade do recurso i (bi) puder ser aumentado uma quantidade igual à unidade.
Cada variável de folga, ou seja, cada restrição do Dual está diretamente relacionada com uma variável original do problema Primal. Este valor é chamado de Custo Reduzido. Assim, cada variável do problema original possui um determinado custo reduzido. Quando estamos com um problema de Maximização, o custo reduzido é o valor que z aumenta quando se aumenta o valor da variável de 0 para 1, na solução ótima. O custo reduzido só se aplica a variáveis que na solução ótima são zero.
Para o Excel, os conceitos de Custo Reduzido (Reduced Cost) e Preço Sombra (Shadow Price) estão relacionados com o valor nominal do efeito na função objetivo. Eles indicam o quanto a função objetivo aumenta ou diminui.
A partir de agora, vamos ver alguns exemplos da literatura.
Exemplo 1:
Uma companhia de móveis fabrica secretárias, mesas, e cadeiras. A produção de cada tipo de móvel requer madeira e dois tipos de trabalho especializado: acabamentos e carpintaria. A quantidade dos recursos necessários para a produção decada móvel está na tabela abaixo:
 Fonte: <http://www.dcc.fc.up.pt/~jpp/mad/teorica-08.pdf>.
Um comprador interessado nos recursos da empresa, quanto deve pagar por cada unidade dos seus recursos? 
Lembremos das notações dos problemas Primal e Dual que utilizamos:
 
Este é um exercício sobre Preço Sombra bem interessante e foi proposto por Gerson Lachtermacher em seu livro Pesquisa Operacional na Tomada de Decisões.
Qual seria o efeito se aumentássemos a constante da restrição em 3 unidades? Clique na seta e veja a solução.
Como ficaria graficamente esta variação? A região viável ficará maior. 
 E a solução ótima deste novo problema? A solução ótima também se deslocará. No problema inicial, teríamos como Z ótimo Z*=1600. Após o acréscimo das 3 unidades na restrição, o novo Z ótimo seria de
De quanto foi a alteração da Função objetivo?
Navegue para visualizar as tabelas
Voltando ao nosso problema original:
Podemos observar pelo gráfico que esta restrição não oferece limite à solução ótima. 
Seu preço de sombra é 0.
Exemplo 2:
A tabela abaixo sintetiza o problema de um pecuarista: são três alimentos diferentes, que contribuem com alguns nutrientes para a alimentação do gado. Qual é o custo mínimo diário para estabelecer uma dieta com o requerimento mínimo?
Para o Excel, os conceitos de Custo Reduzido (Reduced Cost) e Preço Sombra (Shadow Price) estão relacionados com o valor nominal do efeito na função objetivo. Eles indicam o quanto a função objetivo aumenta ou diminui. Vale destacar que Custo Reduzido e Preço Sombra dizem respeito a alterações unitárias, podendo ser garantidas somente dentro de intervalos.
Intervalos de validação do Custo Reduzido e Preço Sombra
Voltando ao nosso problema original de maximização: 
Veja nosso problema com a restrição modificada para 24.
Algumas teorias de aquisição
A análise de sensibilidade nos permite determinar os intervalos nos quais o Custo Reduzido e o Preço Sombra são válidos.
Exemplo 4
Vejamos mais um exemplo: uma empresa pública que monopoliza o setor petroquímico de uma economia nacional. O objetivo da companhia é minimizar o custo global da produção de gasolina e de óleo, estando comprometida em satisfazer as demandas desses produtos aos níveis estipulados de, respectivamente, 5 milhões de barris e 3 milhões de barris. A companhia considera três atividades principais com o objetivo de atender à demanda.
A primeira atividade é explorar e refinar petróleo nacional. Cada 1 milhão de barris processados custa 8 milhões de dólares e gera 1 milhão de barris de gasolina e 1 milhão de barris de óleo.
A segunda atividade é importar e refinar petróleo estrangeiro.  Nesse caso, cada 1 milhão de barris importados custa 12 milhões de dólares e gera 2 milhões de barris de gasolina e 1 milhão de barris de óleo. A terceira atividade é a transformação de xisto betuminoso, na qual gasta-se 15 milhões de dólares em cada milhão de toneladas de xisto processado, gerando-se 2 milhões e 1,5 milhão de toneladas de barris de gasolina e óleo.
Resolvendo os problemas Primal e Dual utilizando o SOLVER:
Resolvendo o Primal:
Resolvendo o Dual:
Observações
As variáveis duais estão associadas aos preços dos produtos demandados pelo mercado.
A gasolina e o óleo possuem o mesmo valor agregado nos processos de fabricação.
Toda solução dual viável está associada a preços dos combustíveis para os quais nenhuma atividade gera lucro. O problema dual corresponde à busca do maior valor possível para a oferta de combustível sem que se possa contabilizar lucro.
A solução dual ótima nos fornece os preços dos produtos demandados para o qual existe um perfeito equilíbrio econômico, com custo igual à receita total. No ótimo nenhuma atividade é deficitária ou lucrativa.
AULA 8 – ANÁLISE DE SENSIBILIDADE
Para iniciarmos o estudo acerca da análise de sensibilidade, observe o problema:
Na prática, nem sempre conhecemos alguns dados de entrada (C, A e B). Consideramos os coeficientes da função Objetivo e das restrições, como entrada de dados ou parâmetros para os modelos de programação linear. As soluções ótimas que obtemos quando resolvemos o problema de programação linear são baseadas nos valores desses coeficientes.  
Por vezes, os parâmetros de um modelo de programação linear são estimativas de quantidades que não podem ser determinadas com precisão quando estamos desenvolvendo o modelo.
A ideia é estudarmos agora como a variação nos dados de entrada podem afetar a solução Ótima obtida. Por exemplo, quando estamos lidando com capital ou mesmo capacidade de produção de determinado produto, a análise de sensibilidade pode nos auxiliar no estudo das alterações nesses dados que seriam convenientes. Note que se variarmos os valores dos coeficientes, mudaremos o problema de programação linear. Será que essa mudança pode significar a mudança da solução Ótima encontrada anteriormente?
A análise de sensibilidade vai nos auxiliar a entender como essa solução Ótima mudará quando modificarmos os coeficientes. Quando modificamos as condições, representadas pelos coeficientes do modelo após a sua implementação, a análise de sensibilidade nos permitirá analisar se as alterações efetuadas significaram uma mudança na solução Ótima, sem que precisemos resolver novamente o problema com os novos dados.
Assim, pretendemos estudar a resposta para algumas perguntas:
Se modificarmos um coeficiente da função objetivo, o que ocorrerá?
Se modificarmos uma constante de uma restrição, o que ocorrerá?
O que se faz é estabelecer limites inferiores e superiores para os coeficientes e constantes, com uma alteração por vez.
Análise de sensibilidade através de limites
Como se dá a análise dos limites dos coeficientes da função objetivo e das constantes das restrições no problema? Começaremos com a análise dos coeficientes da função Objetivo e depois das restrições.
Análise dos coeficientes da função Objetivo
Obtivemos a solução gráfica:
Vamos determinar o coeficiente angular(declividade) das retas:
Vamos observar agora o relatório de sensibilidade do Solver do Excel deste problema. Você se lembra que para abrir o Solver basta ir à janela dos dados? Avance a tela e confira!
Análise das constantes das restrições
Os limites relacionados às constantes das restrições têm a ver com os Preços Sombra, e não com a solução Ótima. Os Preços Sombra equivalem à solução Ótima do Dual, onde as constantes das restrições são os coeficientes da função Objetivo. Para a informação dos limites das constantes das restrições, basta observar as colunas referentes às restrições.
 
Chegamos ao final da nossa aula. Reveja esta atividade quantas vezes for necessário, assim você terá mais facilidade na hora de resolver os exercícios do Registro de Frequência! Até a próxima e bons estudos!
AULA 9 – O PROBLEMA DO TRANSPORTE
Problema de Rede
Os chamados Modelos de Rede são utilizados em diversas áreas. Exemplos: distribuição logística, energia, comunicações, dentre outros. Os modelos de rede são casos especiais de Problemas de Programação Linear cuja análise é mais clara quando utilizamos representação gráfica.          
O que é uma rede?
Rede: conjunto de vértices ou nós ligados entre si por um conjunto de arcos.  
Os arcos podem indicar a direção do fluxo de um ponto para outro ponto e um caminho (Path) entre dois nós é uma sequência de arcos distintos conectando esses dois nós.
De maneira geral, há números associados aos nós e aos arcos. Os números associados a nós podem representar a quantidade de produtos que são ofertados, por exemplo, ou pode representar a demanda do nó. Os números associados aos arcos podemrepresentar o custo do transporte entre um nó e outro, ou mesmo tempo ou distância.
Problema de Rede de Distribuição - São problemas que consideram múltiplas fontes, centros de consumidores e locais intermediários por onde os produtos passam. O problema de transporte, sobre o qual trataremos nesta aula, é uma simplificação do problema de rede de distribuição. Nele não existem localizações intermediárias.
Problema do Menor Caminho - São problemas nos quais os arcos significam a distância entre dois pontos (nós) e desejamos achar a rota que une esses pontos com distância mínima. Entre os nós origem e destino geralmente existem nós intermediários, que podem representar cidades que conectam rodovias, subestações de energia etc. Exemplo: distribuição de energia.
Problema de Fluxo Máximo - São problemas nos quais queremos maximizar a quantidade de fluxo de um ponto de origem para um ponto de destino, e estão sujeitos a restrições de capacidade de fluxo nos arcos. Geralmente envolvem o fluxo de materiais como água, óleo, gás, energia através de uma rede de tubos ou cabos, ou fluxo máximo de carros por uma malha ferroviária, produtos em linhas de produção etc.
Problema de transporte 
O problema de transporte é um problema real especial de aplicação de Problema de Programação Linear. Esse problema consiste em determinar, dentre as diversas maneiras de distribuição de um produto, a que resulta no menor custo de transporte entre as fábricas e os centros consumidores.
Hipótese: custo unitário de transporte de cada fábrica para cada destino é constante.
Vamos formular o problema de transporte. Clique na seta para começar:
 
 
As fábricas não podem produzir mais do que as suas capacidades instaladas. Os centros consumidores não desejam receber volumes acima de suas demandas.
Temos dois modos de formular as restrições.
Modo A – Dummy – montante ofertado deve ser igual ao demandado.
Operacionalização da igualdade, clique em cada caso e veja mais detalhes:
 
 
Depois de inserida uma demanda ou uma oferta fantasma, garantimos que as restrições do problema sejam de igualdade. Isto é:  O total fabricado será virtualmente igual a demanda dos centros consumidores e vice-versa.
Veja agora o 2º modo de formular as restrições. Clique em cada caso e aprenda mais! Modo B – Sem o uso de variáveis Dummy
 
 
Agora vamos ver um exemplo sugerido por Gerson Lachtermacher em seu livro Pesquisa Operacional. Exemplo 1: problema da fábrica de bicicletas
A LCL Bicicletas Ltda. é uma empresa fabricante de bicicletas que possui três fábricas, localizadas no Rio, em São Paulo e Belo Horizonte. A produção da empresa deve ser entregue em Recife, Salvador e Manaus. Considerando os custos de transporte unitários, a capacidade de produção das fábricas e a demanda dos centros consumidores, modele o problema para que se possa determinar quanto deve ser produzido e entregue por cada fábrica em cada centro consumidor, de forma a minimizar os custos de transporte.
Agora, pense nas variáveis de decisão desse problema da fábrica de bicicletas. Veja na tabela ao lado as quantidades transportadas. Em seguida, clique na imagem!
Quando estamos com problemas de transporte onde os valores das ofertas e demandas são números inteiros, os valores das variáveis das soluções básicas viáveis e a solução ótima são inteiros também.
Exemplo 2: problema da fábrica de bicicletas
Considerando o problema anterior, mas com os dados referentes às capacidades modificados:
Exemplo 2: problema da fábrica de bicicletas
Agora temos um consumidor Dummy.
Exemplo 3: Problema da companhia de eletricidade
A companhia de eletricidade CPFLL supre 4 cidades com energia. As potências (kWA) de suas 3 subestações são 35, 50 e 40. As demandas de pico das 4 cidades são: 45, 20, 30 e 30. Os custos de perda para enviar energia para as cidades são:
Como distribuir energia de modo a minimizar o custo de perda e suprir a demanda de pico?
Exemplo 3: problema da companhia de eletricidade
Veja também as variáveis de decisão!
Exemplo 3: problema da companhia de eletricidade
As variáveis de decisão são: