Baixe o app para aproveitar ainda mais
Prévia do material em texto
Pesquisa Operacional Alane Alves Silva alaneaas@yahoo.com.br 2010 Alane Alves () P.O 2010 1 / 162 Pesquisa Operacional Introdução Pesquisa Operacional A análise científica do uso operacional de recursos militares de maneira sistemática foi iniciada na Segunda Guerra Mundial. As equipes estavam envolvidas em problemas de operações de guerra, como manutenção e inspeção de aviões, escolha do tipo de avião para uma missão e melhoria na probabilidade de destruição de submarinos. Além do controle de artilharia antiaérea e dimensionamento de frota. A aplicação do método científico e de ferramentas matemáticas em operações militares passou a ser chamado de Pesquisa Operacional. Hoje em dia, Pesquisa Operacional é enfoque científico para Problemas de Decisão. Alane Alves () P.O 2010 2 / 162 Pesquisa Operacional Introdução Pesquisa Operacional Dois fatores se destacam para o rápido crescimento da pesquisa operacional nesse período. Melhorias das técnicas da pesquisa operacional. Revolução computacional. Alane Alves () P.O 2010 3 / 162 Pesquisa Operacional Introdução Definições Desenvolvimento de métodos científicos de sistemas complexos, com a finalidade de prever e comparar estratégias ou decisões alternativas. O objetivo é dar suporte à definições de políticas e determinações de ações de forma científica. A Pesquisa Operacional significa abordagem científica para tomada de decisões, que procura determinar como melhor projetar e operar um sistema usualmente sob condições que requerem a alocação de recursos escassos. De forma sucinta, pode-se dizer que a pesquisa operacional é um enfoque científico sobre a tomada de decisões. Alane Alves () P.O 2010 4 / 162 Pesquisa Operacional Introdução Denominação A denominação pesquisa operacional é comumente motivo de críticas e reflexões, pois não revela a abrangência da área e pode dar a falsa impressão de estar limitada à análise de operações. Existem diversos sinônimos para Pesquisa Operacional. Os ingleses gostam de operational research (pesquisa operacional), enquanto os americanos usam operations research (pesquisa de operações). Um outro termo usado pelos americanos é management science (ciência da administração). Alane Alves () P.O 2010 5 / 162 Pesquisa Operacional Introdução Exemplos de Problemas de Decisão Em diversas áreas do mundo real existe escassez de um certo produto ou matéria-prima por sua dificuldade de produção e/ou de obtenção, entre outras razões. Busca-se maximizar ou minimizar uma quantidade (Lucro, Receita, Custo, número de produtos, etc.) chamada de objetivo, que depende de um ou mais recursos escassos. Determinação de Mix de Produtos. Escalonamento de Produção. Roteamento e Logística. Planejamento Financeiro. Carteira de Investimento. Análise de Projetos. Alocação de Pessoas. Designação de Equipes. Alane Alves () P.O 2010 6 / 162 Pesquisa Operacional Introdução Modelo 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 confiança na solução obtida através do modelo depende da validação do modelo na representação do sistema real. Alane Alves () P.O 2010 7 / 162 Pesquisa Operacional Introdução Estrutura dos Modelos Matemáticos Num modelo matemático são incluídos três conjuntos de elementos: • 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 e os parâmetros são valores fixos no problema. • Restrições: de modo a levarmos 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). • Função Objetivo: é uma função matemática que define a qualidade da solução em função das variáveis de decisão. É um critério de escolha das variáveis de decisão representado por uma função. Alane Alves () P.O 2010 8 / 162 Pesquisa Operacional Introdução Estrutura dos Modelos Matemáticos Pode-se dizer que: O problema do modelo matemático de Pesquisa Operacional é escolher os valores das variáveis de decisão de forma a obter o melhor resultado da função objetivo sujeita às restrições especificadas. Alane Alves () P.O 2010 9 / 162 Pesquisa Operacional Introdução Estrutura dos Modelos Matemáticos Vejamos o seguinte exemplo para melhor compreendermos os conjuntos de elementos: Situação Atual: R$ 90.000,00 no Caixa Situação Desejada: R$ 90.000,00 bem aplicados Ações da Tele Mundo custam R$ 50,00 e o retorno esperado é de R$ 6,00/ano. Ações da Cosmo Fone custam R$ 30,00 e o retorno esperado é de R$ 4,00/ano. A Diretoria não quer que se aplique mais de R$ 60.000,00 em ações de uma só companhia. Alane Alves () P.O 2010 10 / 162 Pesquisa Operacional Introdução Estrutura dos Modelos Matemáticos Variáveis de decisão As quantidades investidas em cada ação (CF e TM). Parâmetros Os preços e retorno de cada ação. Restrições São as limitações impostas pela diretoria e pela quantidade de dinheiro disponível para investir. Função Objetivo Função matemática que determine o retorno em função das variáveis de decisão e que deve ser maximizada. Alane Alves () P.O 2010 11 / 162 Pesquisa Operacional Introdução Estrutura dos Modelos Matemáticos Max 4, 00CF+ 6, 00TM (1) sujeito a: 30, 00CF + 50, 00TM ≤ 90.000, 00 (2) 30, 00CF ≤ 60.000, 00 (3) 50, 00TM ≤ 60.000, 00 (4) TM ≥ 0 (5) CF ≥ 0 (6) Alane Alves () P.O 2010 12 / 162 Pesquisa Operacional Introdução Técnicas Matemáticas em PO A formulação do modelo depende diretamente do sistema a ser representado. A função objetivo e as funções de restrições podem ser lineares ou não-lineares. As variáveis de decisão podem ser contínuas ou discretas e os parâmetros podem ser determinísticos ou probabilísticos. Alane Alves () P.O 2010 13 / 162 Pesquisa Operacional Introdução Técnicas Matemáticas em PO Existem muitas técnicas de otimização para resolver os diferentes tipos de modelos existentes: Programação linear Programação inteira Programação dinâmica Programação estocástica Programação não-linear Alane Alves () P.O 2010 14 / 162 Pesquisa Operacional Introdução Fases de estudo em Pesquisa Operacional 1 Definição do problema 2 Construção do Modelo 3 Solução do modelo 4 Validação do Modelo 5 Implementação do Modelo 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 Alane Alves () P.O 2010 15 / 162 Pesquisa Operacional Introdução Fases de estudo em Pesquisa Operacional Construção do Modelo 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 seja necessário a utilização de combinações de metodologias. Solução do Modelo O objetivo desta fase é encontrar uma solução para o modelo proposto através da utilização das técnicas mais adequadas e que forneçam o resultado “ótimo” em menor tempo possível. Alane Alves () P.O 2010 16 / 162 Pesquisa Operacional Introdução Fases de estudo em Pesquisa Operacional Validação do Modelo Há necessidade de validar os modelos de modo a poder se aceitar as soluções propostas. Um modelo é valido, dentro de limites razoáveis, se ele for capaz de fornecer uma previsão aceitáveldo comportamento do sistema. Implementação da Solução Avaliadas as vantagens e a validação da solução obtida, esta deve ser convertida em regras operacionais. A implementação é uma das etapas críticas do estudo. Alane Alves () P.O 2010 17 / 162 Pesquisa Operacional Introdução Observação Um tema comum na PO é a busca de uma solução ótima. É necessário que fique claro que estas soluções são ótimas apenas em relação ao modelo que está sendo usado. Como o modelo é apenas uma representação da realidade não existe nenhuma garantia que a solução ótima para o modelo se comprovará como a melhor solução possível que poderia ter sido implementada para o problema real. Porém, se o modelo for bem formulado e testado, as soluções tendem a ser uma boa representação para a solução a ser adotada no caso real. Alane Alves () P.O 2010 18 / 162 Pesquisa Operacional Introdução Outros Exemplos Exemplo 1 Uma empresa pode fabricar dois produtos (1 e 2). Na fabricação do produto 1 a empresa gasta nove horas-homem e três horas-máquina (a tecnologia utilizada é intensiva em mão-de-obra). Na fabricação do produto 2 a empresa gasta uma hora-homem e uma hora-máquina (a tecnologia é intensiva em capital). Sendo x1 e x2 as quantidades fabricadas dos produtos 1 e 2 e sabendo-se que a empresa dispõe de 18 horas-homem e 12 horas-máquina e ainda que os lucros dos produtos são $4 e $1 respectivamente, quanto deve a empresa fabricar de cada produto para obter o maior lucro possível (ou o lucro máximo ou ainda maximizar o lucro) ? Alane Alves () P.O 2010 19 / 162 Pesquisa Operacional Introdução Transformando os Dados em Expressões Matemáticas A Função Lucro Admitindo que a função lucro é uma função linear de x1 e x2 ou seja: L = 4x1 + x2 esse lucro deve ser maximizado por uma escolha de x1 e x2 Max x1,x2 L = 4x1 + x2 Se o problema parasse aqui o lucro seria ilimitado. Porém, existem recursos limitados. Restrições H-H 9x1 + x2 ≤ 18 H-M 3x1 + x2 ≤ 12 x1 ≥ 0; x2 ≥ 0 Alane Alves () P.O 2010 20 / 162 Pesquisa Operacional Introdução Exemplo 2 Uma empresa fabril está interessada em maximizar o lucro mensal proveniente de quatro de seus produtos, designados por I , II , III e IV . Para fabricar esses quatro produtos, ele utiliza dois tipos de máquinas (M1 e M2) e dois tipos de mão-de-obra (MO1 e MO2) com as seguintes disponibilidades: Máquinas Tempo disponível a M1 800 M2 200 aMáquina-hora/mês Mão-de-Obra Tempo disponível a MO1 12000 MO2 16000 aHomem-hora/mês Alane Alves () P.O 2010 21 / 162 Pesquisa Operacional Introdução O setor técnico da empresa fornece os seguintes quadros de produtividade: a) Número de máquinas-hora para produzir uma unidade de cada produto: Máquina Produto I II III IV M1 5 4 8 9 M2 2 6 — 10 Para se produzir uma unidade do produto I consome-se 5 máquinas-hora da M1 e 2 máquinas-hora da máquina M2. b) Número de homem-hora para produzir uma unidade de cada produto: Mão-de-obra Produto I II III IV MO1 2 4 2 8 MO2 7 3 — 7 Alane Alves () P.O 2010 22 / 162 Pesquisa Operacional Introdução O setor comercial da empresa fornece as seguintes informações: Produtos Potencial de Vendas Lucro Unitário I 70 10 II 60 8 III 40 9 IV 20 7 Deseja-se saber a produção mensal dos produtos I , II , III e IV para que o lucro mensal da empresa, proveniente desses quatro produtos, seja máximo. Formule um modelo de programação linear que expresse o objetivo e as restrições dessa empresa. Alane Alves () P.O 2010 23 / 162 Pesquisa Operacional Introdução Solução Sejam x1, x2, x3, x4 as produções mensais dos produtos I , II , III e IV , respectivamente. O modelo será: MaxZ = 10x1 + 8x2 + 9x3 + 7x4 sujeito a: x1 ≤ 70 x2 ≤ 60 x3 ≤ 40 x4 ≤ 20 5x1 + 4x2 + 8x3 + 9x4 ≤ 800 2x1 + 6x2 + 10x4 ≤ 200 2x1 + 4x2 + 2x3 + 8x4 ≤ 12000 7x1 + 3x2 + 7x4 ≤ 16000 x1 ≥ 0 x2 ≥ 0 x3 ≥ 0 x4 ≥ 0 Alane Alves () P.O 2010 24 / 162 Programação Linear Programação Linear Alane Alves () P.O 2010 25 / 162 Programação Linear Introdução Programação Linear Um problema de Programação Linear(PL) é um problema de programação matemática em que as Funções Objetivos e de Restrição são lineares. O problema geral pode se definido por Maximizar(ou Minimizar) Z = c1x1 + c2x2 + · · ·+ cnxn sujeito a: a11x1 + a12x2 + · · ·+ a1nxn ≤ b1(ou ≥, ou =) a21x1 + a22x2 + · · ·+ a2nxn ≤ b2(ou ≥, ou =) . . . . . . . . . am1x1 + am2x2 + · · ·+ amnxn ≤ bm(ou ≥, ou =) x1, x2, . . . , xn ≥ 0 Alane Alves () P.O 2010 26 / 162 Programação Linear Introdução Forma Reduzida Max(Min)Z = n∑ j=1 cjxj (7) sujeito a: n∑ j=1 aijxj ≤ bi (i = 1, 2, 3, . . .m) (8) x1, x2, . . . , xn ≥ 0 (9) Alane Alves () P.O 2010 27 / 162 Programação Linear Introdução Algumas Definições Solução Qualquer especificação de valores para as variáveis de decisão, independente de se tratar de uma escolha desejável ou permissível. Solução Viável Uma solução em que todas as restrições são satisfeitas. O conjunto de todos os pontos que satisfazem todas as restrições é chamado de Conjunto Viável. Solução Ótima Uma solução viável que tem o valor mais favorável da função objetivo, isto é, maximiza ou minimiza a função objetivo em toda a região viável, podendo ser única ou não. Alane Alves () P.O 2010 28 / 162 Programação Linear Solução Gráfica Solução Gráfica Quando o problema envolve apenas duas variáveis de decisão, a solução ótima de um problema de PL pode ser encontrado graficamente. MaxZ = 5x1 + 2x2 sujeito a: x1 ≤ 3 x2 ≤ 4 x1 + 2x2 ≤ 9 x1, x2 ≥ 0 x1 + 2x2 ≤ 9 Solução Viável x1 ≤ 3 x2 ≤ 4 x2 ≥ 0 x1 ≥ 0 x1 x2 A(0, 0) E(0, 4) D(1, 4) C(3, 3) B(3, 0) Alane Alves () P.O 2010 29 / 162 Programação Linear Solução Gráfica Procura da Solução Ótima b bb b b bb bbb x1 x2 A(0, 0) E(0, 4) D(1, 4) C(3, 3) B(3, 0) Z = 0 Z = 10 Z = 20 Alane Alves () P.O 2010 30 / 162 Programação Linear Hipótese Hipóteses da Programação Linear Proporcionalidade A contribuição de cada variável ao valor da função objetivo é proporcional ao valor da variável, conforme representado pelo termo cjxj na função objetivo. De modo semelhante, a contribuição de cada variável às restrições é proporcional ao valor da variável xj , como representado pelo termo aijxj na restrição. Aditividade Toda função em um modelo de programação linear é a soma das contribuições individuais das respectivas variáveis. Alane Alves () P.O 2010 31 / 162 Programação Linear Hipótese Hipóteses da Programação Linear Divisibilidade As variáveis de decisão em um modelo de programação linear podem assumir quaisquer valores, inclusive valores não-inteiros, que satisfaçam as restrições funcionais e de não-negatividade. Quando as variáveis do modelo de programação linear só puderem assumir valores inteiros, deve-se impor estas condições no próprio modelo. Passa-se, então, a lidar com um modelo de programação linear inteira. Certeza O valor atribuído a cada parâmetro de um modelo de programação linear é assumido como uma constante conhecida. Alane Alves () P.O 2010 32 / 162 Programação Linear Teoremas Teoremas Teorema O conjunto de todas as soluções viáveis de um modelo de PL é um conjunto convexo. Teorema Toda solução viável básica do sistema de equações lineares de um modelo de PL é um ponto extremo do conjunto de soluções viáveis. Teorema Se uma função objetivo possui um único ponto de ótimo finito, então este é um ponto extremo do conjunto convexo de soluções viáveis. Teorema Se a função objetivo assume o valor ótimo em mais de um ponto do conjunto de soluções viáveis (soluções múltiplas), então ela assume este valor para pelo menosdois pontos extremos do conjunto convexo e para qualquer combinação convexa desses pontos extremos, isto é, todos os pontos do segmento de reta que une estes dois pontos, ou seja, a aresta do polígono que contém estes dois pontos. Alane Alves () P.O 2010 33 / 162 Programação Linear Teoremas Problema de Mistura O problema da mistura consiste em obter uma mistura que contenha os nutrientes necessários e apresente o mínimo custo. Suponha que um agricultor queira adubar a sua plantação e disponha de dois tipos de adubo. O adubo tipo A possui 6g de fósforo, 2g de nitrogênio e 16g de potássio para cada kg , a um custo de $20 por kg . Já o adubo B possui 4g de fósforo, 6g de nitrogênio e 4g de potássio para cada kg , a um custo de $16 por kg . Sabe-se que o solo em que estão as suas plantações necessita de pelo menos 60g de fósforo, 30g de nitrogênio e 80g de potássio a cada 100m2 de terra. Desenvolver um modelo matemático de programação linear que permita determinar quantos kg de cada tipo de adubo são necessários para adubar 100m2 de terra a um mínimo custo. Alane Alves () P.O 2010 34 / 162 Programação Linear Teoremas MinZ = 20x1 + 16x2 sujeito a: 6x1 + 4x2 ≥ 60 2x1 + 6x2 ≥ 30 16x1 + 4x2 ≥ 80 x1, x2 ≥ 0 Solução Viável I II III x1 x2 Alane Alves () P.O 2010 35 / 162 Programação Linear Teoremas Solução Vértices Adubo A Adubo B Custo Total (0;20) 0 20 320 (2;12) 2 12 232 (8,57;2,14) 8,57 2,14 205,6 (15;0) 15 0 300 Alane Alves () P.O 2010 36 / 162 Programação Linear Teoremas Restrições Redundantes Uma restrição é dita redundante quando sua exclusão do conjunto de restrições, de um problema, não altera o conjunto de soluções viáveis deste. MaxZ = 4x1 + 3x2 sujeito a: x2 ≤ 2 x1 + 3x2 ≤ 7 2x1 + 2x2 ≤ 8 x1 + x2 ≤ 3 x1, x2 ≥ 0 Solução Viável x1 + x2 ≤ 3 x1 + 3x2 ≤ 7 2x1 + 2x2 ≤ 8 x2 ≥ 2 x1 x2 Alane Alves () P.O 2010 37 / 162 Programação Linear Teoremas Procura da Solução Ótima b bb b b bbb x1 x2 Z = 0 Z = 12 Alane Alves () P.O 2010 38 / 162 Programação Linear Teoremas Problema com Múltiplas Soluções Um problema de programação linear pode também apresentar mais de uma solução ótima, um ou mais conjuntos de valores produzem igual valor máximo (ou mínimo) na função objetivo. MaxZ = x1 + x2 sujeito a: x2 ≤ 2 x1 + 3x2 ≤ 7 x1 + x2 ≤ 3 x1, x2 ≥ 0 Solução Viável x1 + 3x2 ≤ 7 x1 + x2 ≤ 3 x2 ≥ 2 x1 x2 Alane Alves () P.O 2010 39 / 162 Programação Linear Teoremas Procura da Solução Ótima b bb b b b Soluções Ótimas bb x1 x2 Z = 0 Z = 3 Alane Alves () P.O 2010 40 / 162 Programação Linear Teoremas Exemplo A Whitt Window é uma empresa com apenas três funcionários que fazem dois tipos de janelas feitas à mão: uma com esquadria de alumínio e outra com esquadria de madeira. Eles têm um lucro de R$60 por janela com esquadria de madeira e de R$30 para janela com esquadria de alumínio. João faz as de esquadria de madeira e é capaz de construir seis delas por dia. Maria faz as janelas com esquadrias de alumínio e é capaz de fazer quatro delas por dia. Roberto monta e corta os vidros e é capaz de fazer 48m2/dia. Cada janela com esquadria de madeira usa 6m2 de vidro e cada janela com esquadria de alumínio usa 8m2 de vidro. A empresa quer determinar quantas janelas de cada tipo de esquadria podem ser fabricadas diariamente para maximizar o lucro total. Alane Alves () P.O 2010 41 / 162 Programação Linear Teoremas Exemplo A Agro Industria SA produz três tipos de enlatados, cada um exigindo um tratamento industrial semelhante, mas que difere na sua duração. Assim, cada 1000 caixas de sopa de tomate exigem 200 horas de mão-de-obra e 6 horas de operação dos equipamentos; cada 1000 caixas do suco de tomate exigem 80 horas de mão-de-obra e 4 horas dos equipamentos, e cada 1000 caixas do molho de tomate exigem 300 horas de mão-de-obra e 7 horas de equipamentos. Sabe-se que a empresa tem disponível, por semana, 5000 horas de mão-de-obra e 168 de equipamentos disponíveis. Sabe-se que o lucro por cada caixa produzida da sopa, suco e molho, é de R$ 3, R$2,5 e R$ 1, respectivamente. Supondo-se que a empresa deseja maximizar seu lucro, pede-se a formulação do problema de programação linear. Alane Alves () P.O 2010 42 / 162 Método Simplex Método Simplex Alane Alves () P.O 2010 43 / 162 Método Simplex Introdução Método Simplex Algoritmo criado para se obter a solução algebricamente. Seqüência finita de passos que se seguidas levam ao objetivo procurado. É necessário conhecer o método para se interpretar melhor os resultados. Se as desigualdades fossem igualdades, as restrições seriam um conjunto de equações lineares e essa nós sabemos resolver. Consegue-se isso acrescentando a cada restrição uma variável a mais, essas novas variáveis são chamadas de variáveis de folga, para restrições do tipo ≤. (Existem também as chamadas variáveis de excesso, para restrições do tipo ≥). Alane Alves () P.O 2010 44 / 162 Método Simplex Introdução MaxZ = 5x1 + 2x2 sujeito a: x1 ≤ 3 x2 ≤ 4 x1 + 2x2 ≤ 9 x1, x2 ≥ 0 MaxZ = 5x1 + 2x2 sujeito a: x1 + x3 = 3 x2 + x4 = 4 x1 + 2x2 + x5 = 9 x1, x2, x3, x4, x5 ≥ 0 1 As variáveis originais do problema são as não básicas e as variáveis de folga são as básicas. 2 Essas novas variáveis, também devem ser maiores ou iguais a zero para garantir a exigência das restrições. 3 Caso a restrição fosse, por exemplo, x1 + 2x2 ≥ 9 a introdução seria x1 + 2x2 − x5 = 9, com x5 ≥ 0. Alane Alves () P.O 2010 45 / 162 Método Simplex Introdução A função objetivo é uma equação e não uma inequação logo não precisamos introduzir variáveis de folga. Pode-se reescrever o sistema da seguinte forma: Z − 5x1 − 2x2 = 0 x1 + x3 = 3 x2 + x4 = 4 x1 + 2x2 + x5 = 9 Alane Alves () P.O 2010 46 / 162 Método Simplex Introdução x1 x2 x3 x4 x5 Constantes Z -5 -2 0 0 0 0 x3 1 0 1 0 0 3 x4 0 1 0 1 0 4 x5 1 2 0 0 1 9 Solução Viável Básica Inicial x3 = 3 x1 = 0 x4 = 4 x2 = 0 x5 = 9 Z = 0 Alane Alves () P.O 2010 47 / 162 Método Simplex Introdução O próximo passo é verificar se a solução encontrada já é a solução ótima. A solução será ótima se não houver coeficientes com valores negativos na linha correspondente a função objetivo. No exemplo, como tem-se −5 e −2 a solução ainda não é ótima. Deve-se encontrar a variável fora da base que tenha o coeficiente mais negativo. Logo quem deve entrar na base é x1 que tem o coeficiente mais negativo entre as variáveis não básicas (x1 e x2). Para determinar a variável que irá sair da base, precisa-se conhecer a variável que mais restringe o crescimento da variável que entrará na base. Como apenas uma variável não básica trocará de valor de cada vez, o que importa são os coeficientes da coluna da variável que vai entrar na base. Calcula-se, para essas linhas, a divisão do valor da constante pelo coeficiente correspondente. O resultado que apresentar o menor valor apontará a variável a sair da base. Alane Alves () P.O 2010 48 / 162 Método Simplex Introdução x1 x2 x3 x4 x5 Constantes Divisão Z -5 -2 0 0 0 0 x3 1 0 1 0 0 3 3 x4 0 1 0 1 0 4 x5 1 2 0 0 1 9 9 x3 será a variável que vai sair da base pois na divisão apresentou o menor valor. Nova Linha Pivô = Antiga Linha Pivô Num. Pivô x1 x2 x3 x4 x5 Constantes Divisão Z x1 1 0 1 0 0 3 3 x4 x5 Alane Alves () P.O 2010 49 / 162 Método Simplex Introdução Nova Linha 1 = Antiga Linha 1− (Coef. da Col. Pivô)(Nova linha Pivô) Nova l1 = Antiga l1 − 5l2 x1 x2 x3 x4 x5 Constantes Z 0 -2 5 0 0 15 x1 1 0 1 0 0 3 x4 x5 Nova Linha 3 = Antiga Linha 3− (Coef. da Col. Pivô)(Nova linha Pivô) Nova l3 = Antiga l3 − 0l2 Vamosrepetir a linha 3 pois o coeficiente da linha pivô é zero. x1 x2 x3 x4 x5 Constantes Z 0 -2 5 0 0 15 x1 1 0 1 0 0 3 x4 0 1 0 1 0 4 x5 Alane Alves () P.O 2010 50 / 162 Método Simplex Introdução Nova Linha 4 = Antiga Linha 4− (Coef. da Col. Pivô)(Nova linha Pivô) Nova l4 = Antiga l4 − 1l2 x1 x2 x3 x4 x5 Constantes Z 0 -2 5 0 0 15 x1 1 0 1 0 0 3 x4 0 1 0 1 0 4 x5 0 2 -1 0 1 6 A nova tabela ainda tem um coeficiente negativo na linha 1 (−2). Logo, essa ainda não é a solução ótima. Assim, tem-se que repetir os passos anteriores. Dessa vez a variável que entra na base é x2, pois tem o coeficiente negativo e a variável que sai é x5. O quadro ótimo será: x1 x2 x3 x4 x5 Constantes Z 0 0 4 0 1 21 x1 1 0 1 0 0 3 x4 0 0 0,5 1 -0,5 1 x2 0 1 -0,5 0 0,5 3 Alane Alves () P.O 2010 51 / 162 Método Simplex Introdução Como todos os coeficientes da linha 1 são não negativos, isto significa que atingiu-se a solução ótima para o problema. A solução encontrada foi: x1 = 3, x2 = 3, x3 = 0, x4 = 1, x5 = 0 e Z = 21 Alane Alves () P.O 2010 52 / 162 Método Simplex Introdução Resumo do Método 1.Inicialização Introduza variáveis de folga. Selecione as variáveis de decisão para serem variáveis não-básicas (configure-as para ficarem iguais a zero) e as variáveis de folga para serem variáveis básicas. 2.Teste de Otimalidade A atual solução básica viável é ótima se e somente se todos os coeficientes da primeira linha forem não-negativos (≥ 0). Se verdadeiro pare; caso contrário, realize uma iteração para obter a próxima solução básica viável, que envolve mudar uma variável não-básica para uma variável básica e vice-versa e depois se chegar a nova solução. Alane Alves () P.O 2010 53 / 162 Método Simplex Introdução Resumo do Método 3.Iteração Passo 1 Determinar a variável básica que entra na base selecionando aquela com o coeficiente “mais negativo” (maior valor absoluto). A coluna correspondente a esta variável será denominada coluna pivô. Alane Alves () P.O 2010 54 / 162 Método Simplex Introdução Resumo do Método 3.Iteração Passo 2 Determine a variável que básica que sai da base aplicando o teste da razão mínima. Selecione cada coeficiente na coluna pivô que seja estritamente positivo (> 0). Divida cada um dos elementos da coluna das constantes pelos coeficientes da coluna pivô nas respectivas linhas. Identifique a linha que possui a menor dessas razões. A variável básica para esta linha é a variável básica que sai. Passo 3 Encontre a nova solução básica usando operações elementares em linhas Alane Alves () P.O 2010 55 / 162 Método Simplex Adaptando a Outras Formas do Modelo Adaptando a Outras Formas do Modelo Variável Sem Restrição de Sinal Suponha que uma certa variável x1 possa assumir valores positivos ou negativos. Nesse caso deve-se substituí-la por: x1 = x ′ 1 + x ′′ 1 onde: x ′1 ≥ 0 e x ′′ 1 ≥ 0 Lado Direito Negativo Basta multiplicar a expressão por −1. Transformação de uma Igualdade Uma igualdade pode ser reescrita como duas desigualdades. Por exemplo: x1 = 10 equivale a: x1 ≤ 10 x1 ≥ 10 Alane Alves () P.O 2010 56 / 162 Método Simplex Casos Especiais Casos Especiais 1.Empate na Entrada Quando houver empate na escolha da variável que entra na base, deve-se tomar a decisão arbitrariamente. A única implicação envolvida é que se pode escolher uma caminho mais longo ou mais curto para se chegar à solução ótima. Alane Alves () P.O 2010 57 / 162 Método Simplex Casos Especiais Casos Especiais 2.Empate na Saída Como no caso anterior, a decisão deve ser também arbitrária. Observe o exemplo a seguir: MaxZ = 5x1 + 2x2 sujeito a: x1 ≤ 3 x2 ≤ 4 4x1 + 3x2 ≤ 12 x1, x2 ≥ 0 Alane Alves () P.O 2010 58 / 162 Método Simplex Casos Especiais Casos Especiais x1 ↓ x2 x3 x4 x5 Constantes Z -5 -2 0 0 0 0 x3 1 0 1 0 0 3 x4 0 1 0 1 0 4 x5 4 3 0 0 1 12 Para escolher a variável que sai da base deve-se fazer: x3 ⇒ 3 1 x5 ⇒ 12 4 Nos dois casos tem-se o resultado da divisão igual a 3. Escolhe-se arbitrariamente, x3 para sair da base. Alane Alves () P.O 2010 59 / 162 Método Simplex Casos Especiais Casos Especiais x1 x2 ↓ x3 x4 x5 Constantes Z 0 -2 5 0 0 15 x1 1 0 1 0 0 3 x4 0 1 0 1 0 4 ← x5 0 3 -4 0 1 0 Note que no quadro anterior a variável básica x5 é nula. Isso sempre ocorrerá quando houver empate na saída. Quando isso ocorre diz-se que a solução viável encontrada é degenerada. Alane Alves () P.O 2010 60 / 162 Método Simplex Casos Especiais Casos Especiais x1 x2 x3 x4 x5 Constantes Z 0 0 7/3 0 2/3 15 x1 1 0 1 0 0 3 x4 0 0 4/3 1 -1/3 4 x2 0 1 -4/3 0 1/3 0 Do ponto de vista teórico, a degeneração tem duas implicações. Fenômeno da ciclagem ou retorno cíclico — ao realizar-se as iterações no método simplex o valor da função objetivo não melhora, sendo possível que o método entre em uma seqüência de iterações sem nunca melhorar o valor da função objetivo e nunca satisfazer a condição de otimalidade. Iterações distintas, embora com classificações diferentes de suas variáveis como básicas e não básicas, resultam em valores idênticos para o valor da função objetivo. Alane Alves () P.O 2010 61 / 162 Método Simplex Casos Especiais Casos Especiais 3.Soluções Múltiplas Em algumas situações um modelo de programação linear pode apresentar mais de uma solução ótima. Considere o seguinte exemplo: MaxZ = 2x1 + 4x2 sujeito a: x1 + 2x2 ≤ 5 x1 + x2 ≤ 4 x1, x2 ≥ 0 Alane Alves () P.O 2010 62 / 162 Método Simplex Casos Especiais Casos Especiais x1 x2 ↓ x3 x4 Constantes Z -2 -4 0 0 0 ← x3 1 2 1 0 5 x4 1 1 0 1 4 x1 ↓ x2 x3 x4 Constantes Z 0 0 2 0 10 x2 1/2 1 1/2 0 5/2 ← x4 1/2 1 -1/2 1 3/2 A solução é ótima e tem-se x1 = 0, x2 = 5/2 e Z = 10 Observe os coeficientes das variáveis não básicas da linha (0). O coeficiente de x1 (não básica) é zero, o que indica que a variável x1 pode entrar na base, e qualquer que seja o valor que ela assuma, a função objetivo ficará com seu valor inalterado, mas causando uma mudança nos valores das variáveis. Alane Alves () P.O 2010 63 / 162 Método Simplex Casos Especiais Casos Especiais x1 x2 x3 x4 Constantes Z 0 0 2 0 10 x2 0 1 1 -1 1 x1 1 0 -1 2 3 Deixando x1 entrar na base e forçando x4 a sair a nova solução ocorre em x1 = 3, x2 = 1 e Z = 10. Ou seja, para pontos distintos o valor da função objetivo não se altera. Por um dos teoremas visto anteriormente pode-se afirmar que qualquer combinação convexa dessas duas soluções também será uma solução ótima para o modelo. Alane Alves () P.O 2010 64 / 162 Método Simplex Casos Especiais Casos Especiais 4. Função Objetivo Ilimitado Outro resultado possível é aquele no qual nenhuma variável se qualifica para ser a variável básica a deixar a base. Este resultado poderia ocorrer se a variável que entra na base pudesse ser aumentada indefinidamente sem dar valores negativos a qualquer uma das variáveis básicas atuais. Na forma tabular, isso significa que todos os coeficientes da coluna pivô (excluindo-se a linha a linha do funcional objetivo) são negativos ou então zero. Neste caso, as restrições não impedem que o valor da função objetivo cresça indefinidamente. Isto ocorre, provavelmente, porque o modelo foi mal formulado, seja por omitir restrições relevantes, seja por declará-las de modo incorreto. Alane Alves () P.O 2010 65 / 162 Método Simplex Casos Especiais Casos Especiais 5.Problema de Minimização Quando a função objetivo tiver de ser minimizada pode-se fazer duas coisas, a saber: Inverter o teste de otimização e o critério de entrada na base. Assim, se todos os coeficientes da linha (0) forem negativos, ou nulos, a presente solução é ótima. Caso contrário, escolha a variável xj para entrarna base que apresente o maior valor. Transformar o problema de minimização em um problema de maximização. Sabe-se que achar o mínimo de uma função é equivalente a achar o máximo do simétrico dessa função. MinW = 2x1 + 3x2 − 5x3 equivale a: MaxZ = −2x1 − 3x2 + 5x3 e depois, na solução final, fazer W = −Z Alane Alves () P.O 2010 66 / 162 Método Simplex Solução Inicial Artificial Solução Inicial Artificial Suponha o seguinte problema: MaxZ = 5x1 + 2x2 sujeito a: x1 ≤ 3 x2 ≤ 4 x1 + 2x2 ≥ 9 x1, x2 ≥ 0 MaxZ = 5x1 + 2x2 sujeito a: x1 + x3 = 3 x2 + x4 = 4 x1 + 2x2 − x5 = 9 x1, x2 . . . , x5 ≥ 0 Variáveis não-básicas: x1 = x2 = 0 Variáveis básicas: x3 = 3; x4 = 4 e x5 = −9 Essa não é uma solução viável pois x5 deveria ser maior que zero. Alane Alves () P.O 2010 67 / 162 Método Simplex Solução Inicial Artificial Solução Inicial Artificial Para se obter uma solução inicial viável pode-se acrescentar uma variável artificial na última equação. Essa variável x6 tomará o lugar de x5 na base inicial. Assim, obtém-se: MaxZ = 5x1 + 2x2 sujeito a: x1 + x3 = 3 x2 + x4 = 4 x1 + 2x2 − x5 + t1 = 9 x1, x2, . . . x5, t1 ≥ 0 Variáveis não-básicas: x1 = x2 = x5 = 0 Variáveis básicas: x3 = 3; x4 = 4 e t1 = 9 Obs.: 1 Os sistemas só serão equivalentes se a variável artificial t1 for nula. 2 As variáveis artificiais não têm significado algum para o problema real, mas permitem a inicialização do processo de maneira automática. Alane Alves () P.O 2010 68 / 162 Método Simplex Método do M-Grande Processo do M Grande Como as variáveis artificiais não são parte do modelo original, recebem punições muito altas na função objetivo, o que as força a ter valor igual a zero na função objetivo. Regra de Penalização das Variáveis Artificiais Dado M, um valor positivo suficientemente alto (M →∞), o coeficiente na função objetivo de uma variável artificial representa uma punição se: Coeficiente na função objetivo da variável artificial ={ M em problemas de minimização −M em problemas de maximização Alane Alves () P.O 2010 69 / 162 Método Simplex Método do M-Grande Processo do M Grande Qual o valor de M que deve ser utilizado? Vai depender dos dados do problema original. O valor de M deve ser suficientemente grande em relação aos coeficientes da função objetivo original, de modo que agirá como uma punição que força as vaiáveis artificiais a ter valor zero na solução ótima. Alane Alves () P.O 2010 70 / 162 Método Simplex Método do M-Grande Processo do M Grande Considere o exemplo anterior: MaxZ = 5x1 + 2x2 −Mt1 sujeito a: x1 + x3 = 3 x2 + x4 = 4 x1 + 2x2 − x5 + t1 = 9 x1, x2, . . . x5, t1 ≥ 0 MaxZ = 5x1 + 2x2 − 100t1 sujeito a: x1 + x3 = 3 x2 + x4 = 4 x1 + 2x2 − x5 + t1 = 9 x1, x2, . . . x5, t1 ≥ 0 No exemplo, os coeficientes de x1 e x2 na função objetivo são 5 e 2, respectivamente. Portanto, parece razoável estabelecer M = 100. Alane Alves () P.O 2010 71 / 162 Método Simplex Método do M-Grande x1 x2 x3 x4 x5 t1 cte Z -5 -2 0 0 0 100 0 x3 1 0 1 0 0 0 3 x4 0 1 0 1 0 0 4 t1 1 2 0 0 -1 1 9 Na solução inicial x3 = 3, x4 = 4 e t1 = 9. Como Z = 5x1 + 2x2 − 100t1 tem-se Z = −900. Como t1 é uma variável básica tem-se o elemento pivô igual a um e todos os elementos da coluna pivô iguais a zero. x1 x2 ↓ x3 x4 x5 t1 cte Z -105 -202 0 0 0 0 -900 x3 1 0 1 0 0 0 3 ← x4 0 1 0 1 0 0 4 t1 1 2 0 0 -1 1 9 Alane Alves () P.O 2010 72 / 162 Método Simplex Método do M-Grande x1 ↓ x2 x3 x4 x5 t1 cte Z -105 0 0 202 100 0 -92 x3 1 0 1 0 0 0 3 x2 0 1 0 1 0 0 4 ← t1 1 0 0 -2 -1 1 1 x1 x2 x3 x4 ↓ x5 t1 cte Z 0 0 0 -8 -5 105 13 ← x3 0 0 1 2 1 -1 2 x2 0 1 0 1 0 0 4 x1 1 0 0 -2 -1 1 1 Alane Alves () P.O 2010 73 / 162 Método Simplex Método do M-Grande x1 ↓ x2 x3 x4 x5 t1 cte Z 0 0 4 0 -1 101 21 ← x4 0 0 1/2 1 1/2 -1/2 1 x2 0 1 -1/2 0 -1/2 1/2 3 x1 1 0 1 0 0 0 3 x1 x2 x3 x4 x5 t1 cte Z 0 0 5 2 0 100 23 x5 0 0 1 2 1 -1 2 x2 0 1 0 1 0 0 4 x1 1 0 1 0 0 0 3 Alane Alves () P.O 2010 74 / 162 Método Simplex Método das Duas Fases Método das Duas Fases Quando uma solução viável básica não é encontrada facilmente, o método das Duas fases mostra-se como uma alternativa ao método do M-Grande. No método das Duas Fases variáveis artificiais são introduzidas às restrições da mesma forma que é feito no método do M-grande. Fase I A primeira fase consiste em resolver um problema de minimização cuja função objetivo é a soma de todas as variáveis artificiais e esta sujeita às restrições do problema original. Quando a solução ótima for atingida, duas situações podem ocorrer: Resolvendo este problema encontra-se uma solução viável básica para o problema de PL original. Fase II Use a solução viável da Fase I como uma solução básica viável inicial para o problema original. Alane Alves () P.O 2010 75 / 162 Método Simplex Método das Duas Fases Método das Duas Fases Considere o seguinte exemplo: MaxZ = 4x1 + x2 sujeito a: 3x1 + x2 = 3 4x1 + 3x2 ≥ 6 x1 + 2x2 ≤ 4 x1, x2 ≥ 0 MaxZ = 4x1 + x2 sujeito a: 3x1 + x2 = 3 4x1 + 3x2 − x3 = 6 x1 + 2x2 + x4 = 4 x1, x2, . . . x4 ≥ 0 Alane Alves () P.O 2010 76 / 162 Método Simplex Método das Duas Fases Método das Duas Fases Como o problema não apresenta uma solução viável básica as variáveis artificiais serão introduzidas para todas as restrições do tipo (≥) ou =. MaxZ = 4x1 + x2 sujeito a: 3x1 + x2+t1 = 3 4x1 + 3x2 − x3+t2 = 6 x1 + 2x2 + x4 = 4 x1, x2, . . . x4, t1, t2 ≥ 0 t1 e t2 são as variáveis artificiais. Alane Alves () P.O 2010 77 / 162 Método Simplex Método das Duas Fases Método das Duas Fases O funcional objetivo original será então: W = t1 + t2 Fase I MinW = t1 + t2 sujeito a: 3x1 + x2 + t1 = 3 4x1 + 3x2 − x3 + t2 = 6 x1 + 2x2 + x4 = 4 x1, x2, . . . x4, t1, t2 ≥ 0 Alane Alves () P.O 2010 78 / 162 Método Simplex Método das Duas Fases Método das Duas Fases Exemplo x1 x2 x3 x4 t1 t2 cte -W 0 0 0 0 1 1 0 t1 3 1 0 0 1 0 3 t2 4 3 -1 0 0 1 6 x4 1 2 0 1 0 0 4 Como t1 e t2 estão na base alguns ajustes precisam ser feitos antes de dar início ao método simplex. ↓ x1 x2 x3 x4 t1 t2 cte -W -7 -4 1 0 0 0 -9 ← t1 3 1 0 0 1 0 3 t2 4 3 -1 0 0 1 6 x4 1 2 0 1 0 0 4 Alane Alves () P.O 2010 79 / 162 Método Simplex Método das Duas Fases Método das Duas Fases x1 ↓ x2 x3 x4 t1 t2 cte -W 0 -5/3 1 0 7/3 0 -2 x1 1 1/3 0 0 1/3 0 1 ← t2 0 5/3 -1 0 -4/3 1 2 x4 0 5/3 0 1 -1/3 0 3 x1 x2 x3 x4 t1 t2 cte -W 0 0 0 0 1 1 0 x1 1 0 1/5 0 3/5 -1/5 3/5 x2 0 1 -3/5 0 -4/5 3/5 6/5 x4 0 0 1 1 1 1 1 Alane Alves () P.O 2010 80 / 162 Método Simplex Método das Duas Fases Método das Duas Fases Note-se que no último quadro o valor mínimo de W é igual a zero. A fase I produz a seguinte solução básica viável: x1 = 3/5 x2 = 6/5 x4 = 1 Neste ponto as variáveis artificiais concluíram sua missão e pode-se eliminar totalmente suas colunas(e linhas quando for o caso) da última tabela e passar para a Fase II. Alane Alves () P.O 2010 81 / 162 Método Simplex Método das Duas Fases Método das Duas Fases Fase II Após eliminar as colunas artificiais, reescrevesse o problema original como: MaxZ = 4x1 + x2 sujeito a: x1 + 1/5x3 = 3/5 x2 − 3/5x3 = 6/5 x3 + x4 = 1 x1, x2, . . . x4 ≥ 0 Alane Alves () P.O 2010 82 / 162 Método Simplex Método das Duas Fases Método das Duas Fases x1 x2 x3 x4 cte Z -4 -1 0 0 0 x1 1 0 1/5 0 3/5 x2 0 1 -3/5 0 6/5 x4 0 0 1 1 1 Alane Alves () P.O 2010 83 / 162 Programação Linear Método Simplex usando Excel Programação Linear Método Simplex usando Excel Alane Alves () P.O 2010 84 / 162 Programação Linear Método Simplex usando Excel MaxZ = 10x1 + 5x2 + 5, 5x3 sujeito a: 30x1 + 10x2+ 50x3 ≤ 1500 5x1 + 3x3 ≤ 200 0, 2x1 + 0, 1x2 + 0, 5x3 ≤ 12 0, 1x1 + 0, 2x2 + 0, 3x3 ≤ 9 x1, x2, x3 ≥ 0 Alane Alves () P.O 2010 85 / 162 Programação Linear Método Simplex usando Excel Figure: Procedimento de procura da solução ótima. Alane Alves () P.O 2010 86 / 162 Programação Linear Método Simplex usando Excel Fórmulas inseridas na tabela do excel. Célula = Fórmula B6 = B3 ∗ B5 + C3 ∗ C5 + D3 ∗ D5 E10 = B10 ∗ B5 + C10 ∗ C5 + D10 ∗ D5 E11 = B11 ∗ B5 + C11 ∗ C5 + D11 ∗ D5 E12 = B12 ∗ B5 + C12 ∗ C5 + D12 ∗ D5 E13 = B13 ∗ B5 + C13 ∗ C5 + D13 ∗ D5 Alane Alves () P.O 2010 87 / 162 Programação Linear Método Simplex usando Excel Para resolver o problema escolha Solver no menu Ferramentas: Figure: Tela de ativação da ferramenta solver. Alane Alves () P.O 2010 88 / 162 Programação Linear Método Simplex usando Excel –Indicar a célula que contém a função objetivo e informar se queremos maximizar, minimizar ou atingir valor pré-determinado: Figure: Janela da ferramenta solver. – Indicar as células que contém as variáveis: Alane Alves () P.O 2010 89 / 162 Programação Linear Método Simplex usando Excel –Informar as restrições: na área entitulada Adicionar Restrições clique no botão Adicionar. Figure: Janela de entrada de restrições. O passo seguinte será o de clicar em OK, no caso de não haver mais restrições a serem adicionadas ou Adicionar caso ainda existam restrições a adicionar. Figure: Restrições de não-negatividade. Alane Alves () P.O 2010 90 / 162 Programação Linear Método Simplex usando Excel Figure: Janela de entrada de parâmetros do solver. Alane Alves () P.O 2010 91 / 162 Programação Linear Método Simplex usando Excel — Finalizar a descrição do problema: clique no botão Opções para terminar a especificação do modelo. Você deverá selecionar as opções presumir modelo linear e presumir não negativos: Figure: Opção de não negatividade. Alane Alves () P.O 2010 92 / 162 Programação Linear Método Simplex usando Excel Uma vez inserido o modelo e suas características, deve-se efetivamente resolve-lo. Para tanto basta clicar no botão Resolver na janela de parâmetros da ferramenta Solver. Se o modelo foi corretamente inserido, será processado e o resultado será automaticamente exibido na planilha. Se observarmos valores incoerentes ou inesperados, devemos neste ponto clicar na opção Restaurar Valores Originais para restaurar os valores e iniciais do modelo. Figure: Opções de resultado da ferramenta. Alane Alves () P.O 2010 93 / 162 Programação Linear Método Simplex usando Excel Figure: Resultado inserido na planilha. Alane Alves () P.O 2010 94 / 162 Programação Linear Método Simplex usando Excel Decisões do Tipo Fazer ou Comprar A LCL Motores, uma fábrica de motores especiais, recebeu recentemente R$900.000,00 em pedidos de seus três tipos de motores. Cada motor necessita de um determinado número de horas de trabalho no setor de montagem e de acabamento. A LCL pode terceirizar parte da sua produção. A tabela a seguir resume estes dados. A LCL deseja determinar quantos motores devem ser produzidos em sua fábrica e quantos devem ser produzidos de forma terceirizada para atender a demanda de pedidos. Modelo 1 2 3 Total Demanda 3000 unid 2500 unid 500 unid 6000 unid Montagem 1h/unid 2h/unid 0,5h/unid 60000h Acabamento 2,5h/unid 1h/unid 4h/unid 10000h Custo Produção 50 90 120 Terceirizado 65 92 140 Alane Alves () P.O 2010 95 / 162 Programação Linear Método Simplex usando Excel MinZ = 50x1 + 90x2 + 120x3 + 65t1 + 92t2 + 140t3 sujeito a: x1 + 2x2 + 0, 5x3 ≤ 6000 2, 5x1 + x2 + 4x3 ≤ 10000 x1 + t1 = 3000 x2 + t2 = 2500 x3 + t3 = 500 x1, x2, x3, t1, t2, t3 ≥ 0 Alane Alves () P.O 2010 96 / 162 Programação Linear Método Simplex usando Excel Alane Alves () P.O 2010 97 / 162 Programação Linear Método Simplex usando Excel Fórmulas inseridas na tabela do excel. Célula = Fórmula B7 = B4 + B5 C7 = C4 + C5 D7 = D4 + D5 E17 = B17 ∗ B4 + C17 ∗ C4 + D17 ∗ D4 E18 = B18 ∗ B4 + C18 ∗ C4 + D18 ∗ D4 B20 = B12 ∗ B4 + C12 ∗ C4 + D12 ∗ D4 + B13 ∗ B5 + C13 ∗ C5 + D13 ∗ D5 Alane Alves () P.O 2010 98 / 162 Programação Linear Método Simplex usando Excel Escolha da Carteira de Investimentos A LCL Investimentos gerencia recursos de terceiros através da escolha de carteiras de investimentos para diversos clientes, baseados em bonds de diversas empresas. Um de seus clientes exige que: Não mais de 25% do total aplicado deve ser investido em um único investimento; Um valor superior a 50% do total aplicado dever ser investido em títulos de maturidade maiores que dez anos; O total aplicado em títulos de alto risco deve ser, no máximo, de 50% do total investido. A tabela mostra os dados dos títulos selecionados. Determine qual o percentual do total deve ser aplicado em cada tipo de título. Título Retorno Anual Anos para Vencimento Risco 1 8,7% 15 1–Muito Baixo 2 9,5% 12 3– Regular 3 12% 8 4–Alto 4 9% 7 2–Baixo 5 13% 11 4–Alto 6 20% 5 5–Muito Alto Alane Alves () P.O 2010 99 / 162 Programação Linear Método Simplex usando Excel Solução x1 = Percentual aplicado no título do tipo 1 x2 = Percentual aplicado no título do tipo 2 x3 = Percentual aplicado no título do tipo 3 x4 = Percentual aplicado no título do tipo 4 x5 = Percentual aplicado no título do tipo 5 x6 = Percentual aplicado no título do tipo 6 A Função Objetivo deverá ser dada por MaxZ = 0, 087 ( x1 100 ) + 0, 095 ( x2 100 ) + 0, 12 ( x3 100 ) + 0, 09 ( x4 100 ) + 0, 13 ( x5 100 ) + 0, 2 ( x6 100 ) Alane Alves () P.O 2010 100 / 162 Programação Linear Método Simplex usando Excel Restrição de Orçamento x1 + x2 + x3 + x4 + x5 + x6 = 100 Restrição de Aplicação Máxima por Tipo de Título x1 ≤ 25; x2 ≤ 25; x3 ≤ 25; x4 ≤ 25; x5 ≤ 25; x6 ≤ 25 Restrição de Aplicação Mínima em Títulos com Maturidade Maior que 10 anos x1 + x2 + x5 ≥ 50 Restrição de Aplicação Máxima em Títulos de Alto Risco x3 + x5 + x6 ≤ 50 Alane Alves () P.O 2010 101 / 162 Programação Linear Método Simplex usando Excel MODELO MaxZ = 0, 087 ( x1 100 ) + 0, 095 ( x2 100 ) + 0, 12 ( x3 100 ) + 0, 09 ( x4 100 ) + 0, 13 ( x5 100 ) + 0, 2 ( x6 100 ) x1 + x2 + x3 + x4 + x5 + x6 = 100 x1 ≤ 25; x2 ≤ 25; x3 ≤ 25; x4 ≤ 25; x5 ≤ 25; x6 ≤ 25 x1 + x2 + x5 ≥ 50 x3 + x5 + x6 ≤ 50 x1, x2, x3, x4, x5, x6 ≥ 0 Alane Alves () P.O 2010 102 / 162 Programação Linear Método Simplex usando Excel Alane Alves () P.O 2010 103 / 162 Programação Linear Método Simplex usando Excel Célula = Fórmula B10 = B3 ∗ D3 + B4 ∗ D4 + B5 ∗ D5 + B6 ∗ D6 + B7 ∗ D7 + B8 ∗ D8 D11 = SOMA(B3:B8) F10 = B3 + B4 + B7 H10 = B5 + B7 + B8 Alane Alves () P.O 2010 104 / 162 Dualidade Dualidade Alane Alves () P.O 2010 105 / 162 Dualidade Introdução A cada modelo de PL corresponde um outro modelo denominado DUAL. O problema DUAL é um modelo associado ao original, que traz uma interpretação econômica para os valores de recursos e para os coeficientes da função objetivo. Os dois problemas guardam uma relação tão estreita que a solução ótima de um problema fornece automaticamente a solução ótima do outro. Alane Alves () P.O 2010 106 / 162 Dualidade Introdução Construção 1 As variáveis de decisão do Dual: a cada restrição do primal será associado uma variável yi . 2 A função objetivo do Dual é de minimização ao passo que a Primal é de maximização. 3 Os coeficientes da função objetivo do dual são os termos constantes das restrições do primal. 4 Os termos constantes das restrições do dual são os coeficientes da função objetivo do primal. 5 As restrições do dual são do tipo ≥, ao passo que as do primal são de ≤. 6 O númerode variáveis do dual é igual ao número de restrições do primal. 7 O número de restrições do dual é igual ao número de variáveis do primal. Alane Alves () P.O 2010 107 / 162 Dualidade Introdução PRIMAL MaxZ = 25x1 + 20x2 sujeito a: x1 + x2 ≤ 50 (y1) 2x1 + x2 ≤ 80 (y2) 2x1 + 5x2 ≤ 220 (y3) x1, x2 ≥ 0 DUAL MinZ = 50y1 + 80y2 + 220y3 sujeito a: y1 + 2y2 + 2y3 ≥ 25 y1 + y2 + 5y3 ≥ 20 y1, y2, y3 ≥ 0 Alane Alves () P.O 2010 108 / 162 Dualidade Introdução PRIMAL MaxZ = n∑ j=1 cjxj sujeito a: n∑ j=1 aijxj ≤ bi (i = 1, . . . ,m) xj ≥ 0 DUAL MinD = m∑ i=1 biyi sujeito a: m∑ i=1 aijyi ≥ cj(j = 1, . . . , n) yi ≥ 0 Alane Alves () P.O 2010 108 / 162 Dualidade Introdução Razões para o Estudo dos Problemas Duais 1 A primeira e mais importante são as interpretações econômicas que pode-se obter dos valores das variáveis do Dual na solução ótima. 2 Algumas vezes é mais eficiente resolver o problema dual do que o primal correspondente, já que, obtendo a solução ótima de um, esta-se obtendo a do outro. Alane Alves () P.O 2010 108 / 162 Dualidade Propriedades Propriedades 1 O dual do dual é o primal. 2 Se a restrição k do primal é de igualdade, então a variável yk do dual é sem restrição de sinal. 3 Se a restrição k do primal é maior ou igual a variável yk do dual é não positiva. 4 Se a variável xp do primal é não positiva, então a restrição p do dual é menor ou igual. 5 Se a variável xp do primal é sem restrição de sinal, então a restrição p do dual é uma igualdade. Alane Alves () P.O 2010 109 / 162 Dualidade Teoremas Teoremas Teorema I Se o problema Primal e o Dual tiveram soluções viáveis, então Z ≤ D para qualquer solução viável do primal e qualquer solução viável do Dual. Teorema II (Propriedade Forte da Dualidade) Se tanto o Primal quanto o Dual tiverem soluções viáveis tais que Z = D, então elas constituem soluções ótimas. Alane Alves () P.O 2010 110 / 162 Dualidade Teoremas PRIMAL MaxZ = 5x1 + 2x2 sujeito a: x1 ≤ 3 (y1) x2 ≤ 4 (y2) x1 + 2x2 ≤ 9 (y3) x1, x2 ≥ 0 DUAL MinZ = 3y1 + 4y2 + 9y3 sujeito a: y1 + y3 ≥ 5 y2 + 2y3 ≥ 2 y1, y2, y3 ≥ 0 Considere as seguintes soluções viáveis para o dual e para o primal. x1 = 2 y1 = 3 x2 = 3 y2 = 3 y3 = 2 Z = 5(2) + 2(3) = 16 Z = 16 ≤ 39 = D D = 3(3) + 4(3) + 9(2) = 39 Z ≤ D Alane Alves () P.O 2010 111 / 162 Dualidade Teoremas Considere agora as seguintes soluções viáveis para o dual e para o primal. x1 = 3 y1 = 4 x2 = 3 y2 = 0 y3 = 1 Z = 5(3) + 2(3) = 21 D = 3(4) + 4(0) + 9(1) = 21 Como Z = D = 21 pode-se afirmar que essas duas soluções são ótimas para o primal e dual x∗1 = 3 y ∗ 1 = 4 x∗2 = 3 y ∗ 2 = 0 Z ∗ = 21 y∗3 = 1 D∗ = 21 Alane Alves () P.O 2010 112 / 162 Dualidade Teoremas Teorema da Folga Complementar Seja o problema primal representado pelo seguinte quadro inicial: x1 x2 . . . xn xn+1 xn+2 . . . xn+m cte Z −c1 −c2 . . . −cn 0 0 0 0 0 xn+1 a11 a12 . . . a1n 1 0 . . . 0 b1 xn+2 a21 a22 . . . a2n 0 1 0 0 b2 ... ... ... ... ... xn+m am1 am2 . . . amn 0 0 . . . 0 bm xj , j = 1, . . . , n → são as variáveis do primal. xn+i , i = 1, . . . ,m → são as variáveis de folga do primal. Para o dual tem-se yi , i = 1, . . . ,m → são as variáveis do dual. ym+j , j = 1, . . . , n → são as variáveis de folga do primal. Alane Alves () P.O 2010 113 / 162 Dualidade Teoremas Teorema da Folga Complementar Seja o problema primal representado pelo seguinte quadro inicial: x1 x2 . . . xn xn+1 xn+2 . . . xn+m cte Z c j = pj − cj cn+i = pn+i Obtida a solução ótima do primal pelo método Simplex, então, o teorema da folga complementar será: O valor ótimo da variável yi do dual é igual ao coeficiente na linha zero ótima da variável de folga xn+i do primal, isto é y∗i = p ∗ n+i (i = 1, 2, . . . ,m) O valor ótimo da variável de folga ym+j do dual é igual ao coeficiente na linha zero ótima, da variável xj do primal, isto é, y∗m+j = p ∗ j − cj (j = 1, 2, . . . , n) Alane Alves () P.O 2010 114 / 162 Análise de Sensibilidade Relatórios do Excel Considere o problema a seguir: MaxZ = 40x1 + 50x2 sujeito a: x1 + 2x2 ≤ 10 2x1 + 5x2 ≤ 16 x1, x2 ≥ 0 Sua modelagem no Excel e os parâmetros e opções do Solver utilizados para resolvê-lo estão apresentados nas figuras a seguir. Alane Alves () P.O 2010 115 / 162 Análise de Sensibilidade Análise de Sensibilidade Alane Alves () P.O 2010 116 / 162 Análise de Sensibilidade Análise de Sensibilidade Alane Alves () P.O 2010 117 / 162 Análise de Sensibilidade Análise de Sensibilidade Após o comando de otimização ter sido dado, a seguinte janela será apresentada para o usuário. Deve-se marcar os relatórios, clicando com o mouse nos três relatórios disponíveis para obter-se as análises de sensibilidade. Alane Alves () P.O 2010 118 / 162 Análise de Sensibilidade Análise de Sensibilidade Existem três relatórios no Excel. São eles: Relatório de Respostas (Answer Report) Relatório de Sensibilidade (Sensitivity Report) Relatório de Limites (Limits Report) Alane Alves () P.O 2010 119 / 162 Análise de Sensibilidade Relatório de Respostas A figura a seguir mostra o Relatório de Respostas do problema que acabou de ser otimizado. Figure: Relatório de Respostas. Alane Alves () P.O 2010 120 / 162 Análise de Sensibilidade Relatório de Respostas O relatório tem três partes distintas. Célula de Destino Indica o tipo de problema de otimização tratado (Máx ou Mín). Valor original (inicial) e final da função objetivo. Bem como a célula utilizada para representá-la. Células ajustáveis Apresenta os valores iniciais e finais das variáveis de decisão e as células utilizadas para defini-las. Alane Alves () P.O 2010 121 / 162 Análise de Sensibilidade Restrições A terceira parte do Relatório de Respostas diz respeito às restrições. A coluna das células indica as células utilizadas para representar os lados esquerdos de cada uma das restrições. A coluna de valor das células indica os valores dos lados esquerdos de cada uma das restrições. A coluna Fórmula indica as fórmulas utilizadas nas restrições. A coluna Status pode apresentar-se de duas formas: Agrupar – significa que os lados direito e esquerdo das restrições são iguais quando os valores da solução são substituídos na fórmula das restrições. Sem agrupar – ocorre quando os lados direito e esquerdo das restrições não são iguais ao substituir os valores ótimos da solução. Pode ocorrer o caso em que os valores dos lados da restrição são diferentes e constar como Sem Agrupar, isso é um indicativo da existência de soluções múltiplas. Alane Alves () P.O 2010 122 / 162 Análise de Sensibilidade Relatório de Limites O Relatório de Limites do problema em estudo é apresentado na figura a seguir. Figure: Relatório de Limites. Alane Alves () P.O 2010 123 / 162 Análise de Sensibilidade Relatório de Limites Primeira Parte Apresenta a célula utilizada para representar a função objetivo e seu valor na solução ótima. Segunda Parte O lado esquerdo apresenta as células utilizadas para representar as variáveis de decisão e seus valores na solução ótima. O lado direito diz respeito à variação possível dos valores das variáveis de decisão e da função objetivo. Os Limites Inferiores significam os menores valores que as variáveis de decisão podem assumir ( mantidas todas as outras variáveis constantes) mantendo a solução viável. A coluna seguinte indica o valor da função objetivo, caso a variável em questão assuma seu menor valor e as outras permaneçam constantes. As outras colunas são de interpretação análoga assumindo apenas que a variável de decisãoe a função objetivo irão assumir seus maiores valores. Alane Alves () P.O 2010 124 / 162 Análise de Sensibilidade Relatório de Sensibilidade Alane Alves () P.O 2010 125 / 162 Análise de Sensibilidade Relatório de Sensibilidade Custos Reduzidos Os custos reduzidos são os valores das variáveis de folga/excesso do problema dual. Como estes valores estão associados aos coeficientes da função objetivo do problema primal as colunas Permissível Acréscimo e Permissível Decréscimo dos coeficientes formam um intervalo no qual os coeficientes da função objetivo podem sofrer alterações sem que a solução ótima seja alterada, assumindo que todos os demais coeficientes permaneçam constantes. Por exemplo: O coeficiente de x1 na função objetivo(c1) é 40 e os valores permissíveis de acréscimo e decréscimo para este coeficiente são respectivamente 10+30 e 20. Logo, 40− 20 ≤ c1 ≤ 40+ 10 +30 20 ≤ c1 ≤ 40+ 10 +30 Alane Alves () P.O 2010 126 / 162 Análise de Sensibilidade Relatório de Sensibilidade Preço Sombra Os valores dos preços sobras são os valores da variáveis do dual. Seu significado é: A quantidade pela qual a função objetivo é alterada quando é dado um incremento de uma unidade na constante da restrição, assumindo que todos os outros coeficientes permanecem inalterados. Interpretação aqui para os valores Permissíves de Acréscimos e Decréscimo é análogo ao que foi feito para o caso dos custo reduzidos sendo que agora o interesse é no intervalo de variação das constantes das restrições (ou disponibilidade dos recursos). Por exemplo, o coeficiente da segunda restrição é 16 e os valores dos Acréscimos e Decrécimos Pemissíveis são, respectivamente, 4 e 16. Sendo assim, o recurso dois(b2) poderá variar dentro do seguinte intervalo: 16− 16 ≤ b2 ≤ 16+ 4 ⇒ 0 ≤ b2 ≤ 20 O raciocínio é o mesmo para as demais restrições. Alane Alves () P.O 2010 127 / 162 Modelo de Transporte Modelo de Transporte Alane Alves () P.O 2010 128 / 162 Modelo de Transporte Introdução Introdução O modelo de transporte visa minimizar o custo total do transporte necessário para abastecer n centros consumidores(destinos) a partir de m centros fornecedores(origens). a1 b1 a2 b2 am bn . . . . . . F o rn eced o res D isp o n ív eis P o ss ív ei s D es ti n o s Alane Alves () P.O 2010 129 / 162 Modelo de Transporte Introdução Formulação do Problema bj → as quantidades requeridas, ou demandadas, em cada destino. ai → as quantidades disponíveis, ou ofertadas em cada origem. cij → custo unitário de transporte entre a origem i e o destino j . xij → a quantidade a ser transportada da origem i ao destinoj . A fábrica i pode remeter no máximo ai itens, e o destino j necessita de pelo menos bj itens. Alane Alves () P.O 2010 130 / 162 Modelo de Transporte Introdução Formulação do Problema MinZ = m∑ i=1 n∑ j=1 cijxij sujeito a: n∑ j=1 xij = ai (i = 1, 2, . . . ,m) m∑ i=1 xij = bj (j = 1, 2, . . . , n) xij ≥ 0 Note que nas restrições do modelo todos os coeficientes das variáveis são iguais a um. Alane Alves () P.O 2010 131 / 162 Modelo de Transporte Introdução Formulação do Problema Ao se somar as m restrições de ofertas obtém-se: m∑ i=1 n∑ j=1 xij = m∑ i=1 ai Ao se somar as n restrições de demanda vem-se: n∑ j=1 m∑ i=1 xij = n∑ j=1 bj Pode-se concluir, então, que a oferta é igual a demanda m∑ i=1 ai = n∑ j=1 bj indicando que o modelo exige uma igualdade entre oferta total e demanda total. Alane Alves () P.O 2010 132 / 162 Modelo de Transporte Introdução Formulação do Problema Para aplicar o algoritmo do transporte é preciso apresentar as restrições do modelo por meio do quadro a seguir: cm1 . . . c21 c11 . . . . . . . . . . . . . . . . . .. . . a1 a2 am 1 2 m b1 b2 bn . . . 1 2 n. . . cm2 . . . c22 c12 cmn . . . c2n c1n Demanda Oferta Destino Origem Alane Alves () P.O 2010 133 / 162 Modelo de Transporte Introdução Formulação do Problema Uma outra forma de apresentar o modelo é a seguinte: MinZ = m∑ i=1 n∑ j=1 cijxij sujeito a: n∑ j=1 xij ≤ ai (i = 1, 2, . . . ,m) m∑ i=1 xij ≤ bj (j = 1, 2, . . . , n) xij ≥ 0 Neste modelo está-se considerando que a quantidade transportada da origem i , para todos os possíveis destinos, é menor ou igual a quantidade disponível (primeira restrição). Além disso, a segunda restrição diz que a quantidade recebida pelo destino j , de todas as possíveis origens, é maior ou igual a quantidade requerida. Alane Alves () P.O 2010 134 / 162 Modelo de Transporte Introdução Formulação do Problema O algoritmo utilizado para resolver o modelo de transporte, exige que a igualdade ∑m i=1 ai = ∑n j=1 bj seja respeitada. Isso pode ser alcançado definindo-se um centro consumidor fictício, cuja demanda seja exatamente a diferença entre o total da oferta e o total da demanda, enquanto que os custos de transporte de cada origem ao depósito fictício são tomados iguais a zero. Na solução obtida, quantidades transportadas da origem i ao consumidor fictício representam excedente de produção na origem i . (Produção ≥ Demanda) Outra situação hipotética é aquela em que a oferta é menor que a demanda. Para alcançar o equilíbrio (demanda=Produção) defini-se uma origem fictícia com custos de transporte a cada depósito iguais a zero. Na solução obtida, a quantidade transportada da origem fictícia ao consumidor j representará a demanda não satisfeita do consumidor j . Alane Alves () P.O 2010 135 / 162 Modelo de Transporte Introdução Exemplo Uma firma fabrica um determinado produto em quatro cidade A,B ,C e D; o produto destina-se a três centros de consumo I , II e III . O custo estimada de transportar o produto das fábricas para os centros consumidores, assim como a demanda de cada centro consumidor e a oferta de cada fábrica é dado na tabela abaixo. Destino Origem I II III Oferta A 1 2 3 30 B 10 — 8 20 C 3 4 2 50 D 5 2 1 10 Demanda 20 40 50 Formule o modelo de transporte para se determinar o programa que torna mínimo o custo total de transporte entre as quatro cidades e os três centros consumidores. Alane Alves () P.O 2010 136 / 162 Modelo de Transporte Introdução Exemplo MinZ = xAI + 2xAII + 3xAIII + 10xBI +MxBII + 8xBIII + 3xCI +4xCII + 2xCIII + 5xDI + 2xDII + xDIII sujeito a: xAI + xAII + xAIII = 30 xBI + xBII + xBIII = 20 xCI + xCII + xCIII = 50 xDI + xDII + xDIII = 10 xAI + xBI + xCI + xDI = 20 xAII + xBII + xCII + xDII = 40 xAIII + xBIII + xCIII + xDIII = 50 xij ≥ 0 Alane Alves () P.O 2010 137 / 162 Modelo de Transporte Introdução Solução Inicial Sabe-se que uma solução inicial deverá ser uma solução viável básica do sistema formado pelas restrições do modelo. Teorema Qualquer equação do sistema formado pelas restrições do modelo pode ser obtida por uma combinação linear das demais, indicando que só existem (m + n − 1) equações independentes naquele sistema. A conseqüência desse teorema é que a base será formada por (m + n − 1) variáveis básicas. Há uma série de critérios diversos para selecionar as variáveis básicas. Alane Alves () P.O 2010 138 / 162 Modelo de Transporte Regra do Canto Noroeste Regra do Canto Noroeste A regra será aplicada ao quadro de soluções segundo os seguintes passos: 1 Comece pela célula superior esquerda 2 Coloque nessa célula a maior quantidade permitida pela oferta e demanda correspondentes. 3 Atualize os valores da oferta e da demanda que foram modificados pelo passo 2. 4 Siga para a célula da direita se houver alguma oferta restante e volte ao passo2. Caso contrário, siga para célula inferior e volte ao passo 2. Alane Alves () P.O 2010 139 / 162 Modelo de Transporte Regra do Canto Noroeste Exemplo – Regra do Canto Noroeste 11 10 1 Oferta 9 10 8 1 2 3 7 6 10 4 1 2 3 4 12 8 7 4 6 9 12 8 5 Demanda Destino Origem Na célula (1, 1) atribuem-se 7 unidades que é a quantidade máxima de demanda do destino 1. Assim toda demanda do destino 1 foi atendida e ainda restaram 2 unidades na origem 1. Deve-se então seguir para a célula (1,2) e atribuí-la 2 unidades, que é o máximo valor que a origem 1 tem disponível. Alane Alves () P.O 2010 140 / 162 Modelo de Transporte Regra do Canto Noroeste Exemplo – Regra do Canto Noroeste 11 10 1 7 2 4 6 4 4 Oferta 9 2 10 6 8 4 1 2 3 7 6 4 10 4 4 1 2 3 4 12 8 7 4 6 9 12 8 5 Demanda Destino Origem O processo se repete até se alcançar a célula inferior direita do quadro de soluções, quando contar-se-á com uma solução inicial. Alane Alves () P.O 2010 141 / 162 Modelo de Transporte Regra do Canto Noroeste Exemplo – Regra do Canto Noroeste No exemplo a solução inicial foi x11 = 7 x12 = 2 x22 = 4 x23 = 6 x33 = 4 x34 = 4 (Variáveis Básicas) Z = 218 Note que na Regra do canto Noroeste a solução inicial é obtida sem levar em consideração os custos dos transportes cij , isto é, depende exclusivamente das ofertas das origens e das demandas dos destinos. Alane Alves () P.O 2010 142 / 162 Modelo de Transporte Processo do Custo Mínimo Processo do Custo Mínimo Este processo para fornecer uma solução inicial leva em consideração além das ofertas e das demandas os valores dos custos. Os seguintes passos devem ser seguidos: 1 Localize no quadro o menor cij que não tenha oferta ou demanda nula. 2 Coloque na célula a maior quantidade permitida pela oferta e demanda correspondente. 3 Atualize os valores da oferta e da demanda que foram modificadas pelo passo 2 e volte ao passo 1. O processo se repete até que sejam esgotadas as ofertas e suprimidas as demandas de todos os destinos. Alane Alves () P.O 2010 143 / 162 Modelo de Transporte Processo do Custo Mínimo Exemplo – Processo do Custo Mínimo 11 10 1 4 9 1 6 1 6 Oferta 9 10 6 8 71 1 2 3 71 6 10 1 4 1 2 3 4 12 8 7 4 6 9 12 8 5 Demanda Destino Origem O menor cij que aparece é 1 referente a célula (2,4). Logo nesta célula vai-se atribuir a quantidade máxima de unidades permitida levando em conta a restrição de oferta e demanda. Coloca-se, assim, 4 unidades nesta célula que é a demanda do destino 4 e atualiza-se a oferta da origem 2 para 6 unidades uma vez que 4 foram consumidas. Alane Alves () P.O 2010 144 / 162 Modelo de Transporte Processo do Custo Mínimo Exemplo – Processo do Custo Mínimo Eliminando-se o destino 4 do quadro o menor custo é igual a 2 e corresponde a célula (2,1). A esta célula serão atribuídas 6 unidades esgotando-se a oferta da origem 2 e diminuindo a demanda do destino 1 para 1 unidade. Este processo se repete até que todas as ofertas sejam consumidas e todas as demandas atendidas, quando então encontra-se uma solução inicial. No exemplo a solução inicial foi de: x13 = 9 x21 = 6 x24 = 4 x31 = 1 x32 = 6 x33 = 1 (Variáveis Básicas) Z = 161 Alane Alves () P.O 2010 145 / 162 Modelo de Transporte Processo do Custo Mínimo Solução Ótima Conhecida uma solução viável básica inicial, deve-se obter a função objetivo somente em função das variáveis não básicas, para saber se a presente solução já é ótima. Da mesma forma como é feito no método simplex, caso a solução ainda não seja ótima deve-se determinar a variável que entra e a que sai da base. Alane Alves () P.O 2010 146 / 162 Modelo de Transporte Processo do Custo Mínimo Obter a função objetivo somente em função das variáveis não-básicas: Método “u − v” MinZ − m∑ i=1 n∑ j=1 cijxij = 0 sujeito a: n∑ j=1 x1j = a1 (u1) . . . . . . . . . n∑ j=1 xmj = am (um) m∑ i=1 xi1 = b1 (v1) . . . . . . . . . m∑ i=1 xin = bn (vn) xij ≥ 0 Alane Alves () P.O 2010 147 / 162 Modelo de Transporte Processo do Custo Mínimo É necessário eliminar as variáveis básicas da função objetivo e, para isso, deve-se somar a ela múltiplos das restrições do modelo. Sejam u1, u2, . . . um os valores que irão multiplicar as equações de oferta, antes de somá-la a função objetivo. Sejam v1, v2, . . . vn os múltiplos análogos para cada restrição de demanda. Alane Alves () P.O 2010 148 / 162 Modelo de Transporte Processo do Custo Mínimo Conhecida uma solução viável básica, deve-se ter: cij − ui − vj = 0 (10) para cada uma das (m + n − 1) variáveis básicas, de modo a eliminá-las da função objetivo que ficará expressa somente em função das variáveis não-básicas. Uma vez que o número de variáveis básicas é igual a (m + n − 1) vai-se ter (m + n − 1) equações do tipo (10). Uma vez que o número de incógnitas (ui e vj ) é m + n e tem-se m + n − 1 equações, pode-se atribuir um valor arbitrário a uma dessas variáveis sem violar as equações. Alane Alves () P.O 2010 149 / 162 Modelo de Transporte Processo do Custo Mínimo Como exemplo, considere o quadro de soluções do método do custo mínimo. As equações são: Variáveis Básicas x13 = 6− u1 − v3 = 0 x21 = 2− u2 − v1 = 0 x24 = 1− u2 − v4 = 0 x31 = 11− u3 − v1 = 0 x32 = 12− u3 − v2 = 0 x33 = 8− u3 − v3 = 0 Fazendo u1 = 0 tem-se: v3 = 6 v1 = 9 v4 = 8 u3 = 2 u2 = −7 v2 = 10 Alane Alves () P.O 2010 150 / 162 Modelo de Transporte Processo do Custo Mínimo Determinando os ui e vj pode-se escrever a função objetivo em função das variáveis não básicas. Coeficientes da Função Objetivo xij : cij − ui − vj x11 : 10− 9 = 1 x12 : 7− 10 = −3 x14 : 5− 8 = −3 x22 : 8+ 7− 10 = 5 x23 : 9+ 7− 6 = 10 x34 : 4− 2− 8 = −6 A função objetivo será, então: Z = 161+ x11 − 3x12 − 3x14 + 5x22 + 10x23 − 6x34 Alane Alves () P.O 2010 151 / 162 Modelo de Transporte Processo do Custo Mínimo Teste de Otimalidade Uma solução viável básica é ótima se e somente se cij − ui − vj ≥ 0 para todo i , j tal que xij seja não básica. Sendo assim, como as variáveis x12, x14 e x34 apresentaram coeficientes negativos a solução ainda não é ótima. Iteração Como acontece com o método simplex tradicional tem-se que determinar a variável que entra na base (passo 1) e uma variável que sai da base (passo 2) e depois identificar a nova solução viável (passo 3). Alane Alves () P.O 2010 152 / 162 Modelo de Transporte Processo do Custo Mínimo Teste de Otimalidade Passo 1 – Encontrar a variável que entra na base Obtida a função objetivo somente em função das variáveis não-básicas a variável que entra na base deve ter um valor de cij − ui − vj negativo para diminuir o custo total. Portanto, no exemplo as candidatas a entrar na base são x12, x14 e x34. Para escolher entre as candidatas, selecione aquela com menor valor de cij − ui − vj negativo como variável que entra na base, nesse caso x34 pois apresenta coeficiente −6. Alane Alves () P.O 2010 153 / 162 Modelo de Transporte Processo do Custo Mínimo Teste de Otimalidade Passo 2 – Encontrar a variável que sai da base Aumentando-se o valor da variável que entra na base dispara uma reação em cadeia para compensar mudanças nas demais variáveis básicas de modo a continuar satisfazendo as restrições de oferta e demanda. A primeira variável básica que chegar a zero se torna a variável que deixa a base. Imagine que a variável x34 entrará na base com valor θ ≥ 0, que deve ser o maior possível. Estabelecer um valor θ para variável x34, requer diminuir x24 na mesmaquantidade para restabelecer a demanda igual a 4 na coluna 4. Essa mudança requer então aumentar x21 na mesma quantidade para continuar obedecendo a oferta da linha 2. Mais uma vez, tal mudança requer diminuir a variável x31 na mesma quantidade para restabelecer a demanda 7 da coluna 1. Esse decrescimento também restabelece a oferta da origem 3 igual 8 na linha 3. Alane Alves () P.O 2010 154 / 162 Modelo de Transporte Processo do Custo Mínimo 11 10 1 9 4− θ 6 1 θ 6+θ 1−θ Oferta 9 10 8 1 2 3 7 6 10 4 1 2 3 4 12 8 7 4 6 9 12 8 5 Demanda Destino Origem Alane Alves () P.O 2010 155 / 162 Modelo de Transporte Processo do Custo Mínimo Teste de Otimalidade Passo 2 – Encontrar a variável que sai da base Deve-se agora, determinar o maior valor permitido a θ, isto é, o valor de θ que gera a variável básica que se anula mais rapidamente. Do quadro anterior tem-se: x21 = 6+ θ x24 = 4− θ ≥ 0 ∴ θ ≤ 4 x31 = 1− θ ≥ 0 ∴ θ ≤ 1 Então θ = 1 e x31 é a variável que sai da base por ser a primeira a se anular. Alane Alves () P.O 2010 156 / 162 Modelo de Transporte Processo do Custo Mínimo Passo 3 – Encontrar a nova solução viável básica A nova solução viável básica é identificada adicionando-se o valor de θ no último quadro. O valor da variável que sai é x31 = 1 o quadro ficará: 11 10 1 3 9 0 6 1 1 7 Oferta 9 10 8 1 2 3 7 6 10 4 1 2 3 4 12 8 7 4 6 9 12 8 5 Demanda Destino Origem Como cada variável tem um custo na função objetivo, o efeito da entrada de x34 pode ser assim calculado: ∆Z = c34 − c24 + c21 − c31 = 4− 1+ 2− 11 = −6 Alane Alves () P.O 2010 157 / 162 Modelo de Transporte Processo do Custo Mínimo Continuando com o algoritmo resta saber se a solução é ótima, para isso calcula-se ui e vj e reinicia-se o processo. Variáveis Básicas x13 = 6− u1 − v3 = 0 x21 = 2− u2 − v1 = 0 x24 = 1− u2 − v4 = 0 x32 = 12− u3 − v2 = 0 x33 = 8− u3 − v3 = 0 x34 = 4− u3 − v4 = 0 Fazendo u3 = 0 tem-se: u1 = −2 u2 = −3 v4 = 4 v1 = 5 v3 = 8 v2 = 12 Alane Alves () P.O 2010 158 / 162 Modelo de Transporte Processo do Custo Mínimo Calculando-se ui e vj deve-se calcular os coeficientes das variáveis não básicas (cij − ui − vj) x11 : 10+ 2− 5 = 7 x12 : 7+ 2− 12 = −3 x14 : 5+ 2− 4 = 3 x22 : 8+ 3− 12 = −1 x23 : 9+ 3− 8 = 4 x31 : 11− 0+ 5 = 6 Como há coeficientes negativos a solução não é ótima e a variável que deve entrar na base é x12 por apresentar o menor coeficiente negativo (−3). Alane Alves () P.O 2010 159 / 162 Modelo de Transporte Processo do Custo Mínimo 11 10 1 3 9−θ+θ 6− θ 1 + θ 1 7 Oferta 9 10 8 1 2 3 7 6 10 4 1 2 3 4 12 8 7 4 6 9 12 8 5 Demanda Destino Origem x13 = 9− θ ≥ 0 ∴ 9 x32 = 6− θ ≥ 0 ∴ 6 x33 = 1+ θ ≥ 0 Sendo assim, o valor máximo que θ pode assumir é 6 e a variável que deve deixar a base é x32. Alane Alves () P.O 2010 160 / 162 Modelo de Transporte Processo do Custo Mínimo Para determinar a variação na função objetivo ∆Z = 6(c12 − c13 + c33 − c32) = 6(7− 6+ 8− 12) = −18 11 10 1 3 36 0 7 1 7 Oferta 9 10 8 1 2 3 7 6 10 4 1 2 3 4 12 8 7 4 6 9 12 8 5 Demanda Destino Origem Alane Alves () P.O 2010 161 / 162 Modelo de Transporte Processo do Custo Mínimo Variáveis Básicas x12 = 7− u1 − v2 = 0 x13 = 6− u1 − v3 = 0 x21 = 2− u2 − v1 = 0 x24 = 1− u2 − v4 = 0 x33 = 8− u3 − v3 = 0 x34 = 4− u3 − v4 = 0 Fazendo u1 = 0 tem-se: v2 = 7 u3 = 2 u2 = −1 v1 = 1 v3 = 6 v4 = 2 Variáveis Não-Básicas x11 = 10− 0− 1 = 9 x14 = 5− 0− 2 = 3 x22 = 8+ 1− 7 = 2 x23 = 9+ 1− 6 = 4 x31 = 11− 2− 1 = 8 x32 = 12− 2− 7 = 3 Como não há coeficiente negativos a solução é ótima. x12 = 6 x13 = 3 x21 = 7 x24 = 3 x33 = 7 x34 = 1 Z ∗ = 137 Alane Alves () P.O 2010 162 / 162 Pesquisa Operacional Introdução Programação Linear Introdução Solução Gráfica Hipótese Teoremas Método Simplex Introdução Adaptando a Outras Formas do Modelo Casos Especiais Solução Inicial Artificial Método do M-Grande Método das Duas Fases Programação Linear Método Simplex usando Excel Dualidade Introdução Propriedades Teoremas Análise de Sensibilidade Modelo de Transporte Introdução Regra do Canto Noroeste Processo do Custo Mínimo
Compartilhar