Investigação Operacional Métodos de Programação Linear: Gráfica, Simplex (Mestrado) Engenharia Industrial http://dps.uminho.pt/pessoais/zan Universidade do Minho - Escola de Engenharia Departamento de Produção e Sistemas Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 1 Representação Gráfica Considere o seguinte problema de PL: duas variáveis, permite a representação gráfica do problema Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 2 Representação Gráfica Não negatividade Uma restrição Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 3 Representação Gráfica Duas restrições Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 4 Representação Gráfica Conjunto de restrições Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 5 Representação Gráfica Espaço de soluções Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 6 Representação Gráfica Função objectivo: família de rectas Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 7 Representação Gráfica Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 8 Soluções de modelos de PL Conjunto das soluções admissíveis pode ser –Vazio –Não vazio (Limitado ou Ilimitado) Um modelo de PL pode –Ser impossível –Ser ilimitado –Ter soluções óptimas alternativas* –Ter uma única solução óptima Os dois primeiros casos, normalmente, indicam que o modelo de PL está mal formulado ou houve erros na sua introdução, já que não é frequente existirem problemas de decisão "reais" sem alternativas ou com alternativas tão boas quanto desejarmos. * Tipicamente, o software para PL só identifica uma solução óptima. Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 9 Soluções de modelos de PL Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 10 Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 11 Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 12 Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 13 Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 14 Algoritmos para PL Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 15 Algoritmos para PL Se tiver curiosidade em ter uma ideia do que é isto de teoria da complexidade, uma excelente introdução para leigos é feita em J. Buescu, “Quem quer ser milionário?”, em “O Mistério do Bilhete de Identidade e outras histórias – Crónicas das fronteiras da Ciência”, Gradiva, 4ª edição, 2002. Já agora, o problema de PL é um problema do tipo P (provado em 1979 devido ao método do Elipsóide) mas o algoritmo Simplex não é polinomial. Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 16 Forma do modelo de PL •Forma normal /estandardizada / padrão – Maximização; – Todas as restrições são equações; – Todas as variáveis são restringidas a serem não negativas. Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 17 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 18 Simplex Considere um problema de maximização de lucro relacionado com duas actividades e três recursos. Na tabela seguinte são dados os consumos unitários de cada recurso (A, B e C) por actividade (1 e 2), a disponibilidade de cada recurso e o lucro unitário de cada actividade. Formule o problema através de um modelo de PL. Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 19 Simplex • Temos 3 equações e 5 incógnitas (sistema de equações indeterminado). • Se fixarmos 2 variáveis a zero, temos 3 equações a 3 incógnitas e podemos determinar a solução desse sistema. Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 20 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 21 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 22 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 23 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 24 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 25 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 26 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 27 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 28 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 29 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 30 Simplex Problema geral: n variáveis, m equações. Qualquer conjunto de m variáveis cujo sistema de equações tenha solução designa-se por base (exemplo, x3, x4, x5). Dada uma base é fácil determinar a solução lhe está associada, basta fixar a 0 as variáveis que não fazem parte da base (variáveis não básicas, no exemplo dado x1 e x2) e resolver o sistema de equações para as restantes (variáveis básicas) - obtendo-se uma solução básica ex. x1=0, x2=0, x3=720, x4=880, x5=160 Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 31 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 32 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 33 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 34 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 35 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 36 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 37 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 38 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 39 Simplex A cada ponto extremo corresponde uma solução básica admissível (sem coordenadas negativas) e vice-versa. Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 40 Simplex •Uma solução básica pode ser admissível ou não admissível (no exemplo, A,B,G,F,I correspondem a bases admissíveis e C,H,E,D a bases não admissíveis). Para saber se a base é admissível ou não basta ver se as restrições de não negatividade são satisfeitas. •Já tínhamos chegado à conclusão de que se existe uma solução óptima finita, então há, pelo menos, um ponto extremo que é solução óptima. A cada ponto extremo está associada uma base admissível... •...então basta determinar todas as soluções básicas e o seu valor (na função objectivo) e ver qual é a solução que tem maior valor (problema de maximização). Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 41 Simplex •Determinar a solução associada a uma base é fácil: resolver um sistema de m equações a m incógnitas (método de Gauss-Jordan). •Só há um "pequeno" problema, o número de bases pode atingir n! Cm n n m !m ! •Por exemplo, para um problema com 100 variáveis e 10 restrições esse número é 1.73e+13. Com a folha de cálculo Excel (Microsoft Office 2003) já não se consegue determinar esse valor para um problema com 2000 variáveis e 250 restrições. O número de combinações é gigantesco para um problema pequeno! Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 42 Simplex •Algoritmo Simplex: – começa-se numa base e vê-se se ela corresponde à solução óptima (temos maneira de fazer isso?). – Se for, temos a solução óptima. – Se não for, passamos para outra base (como?) que pareça promissora (e como se vê isso?) e repetimos o procedimento. •Não parece grande ideia, dado o número de bases ser tão grande... De facto, a análise (com base na teoria da complexidade) do comportamento do algoritmo simplex no pior caso não é muito simpática para este algoritmo (já foram construídos propositadamente problemas em que o simplex tinha de testar todas as bases!). Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 43 Simplex A boa notícia é que, em problemas reais, o comportamento do algoritmo é muitíssimo melhor do que a análise para o pior caso da teoria da complexidade. •O algoritmo Simplex (na verdade, os algoritmos da classe de métodos Simplex, porque, na prática, há diferenças consideráveis entre os diferentes algoritmos que se baseiam nestas ideias) continua a ser largamente o mais utilizado na resolução de problemas de PL reais. •O Simplex é um exemplo clássico de como, por vezes, a análise teórica do pior caso, não é adequada à classificação prática dos algoritmos. Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 44 Simplex •No seguinte problema qual é a base que tem uma solução mais fácil de calcular? Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 45 Simplex •função objectivo: z-10x1-9x2-0x3-0x4-0x5=0 •Os valores que aparecem nesta linha são denominados por custos reduzidos. •A que solução corresponde o quadro simplex apresentado? Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 46 Simplex •Um quadro simplex que corresponda a uma solução básica admissível (primal) tem as seguintes características: – Uma coluna correspondente a uma variável básica tem um 1 na linha associada à variável básica e zeros em todas as outras linhas (exemplo, a coluna de x5 tem um 1 na terceira linha associada à variável x5 e zeros nas primeira e segunda linhas). Esta característica implica que as colunas das variáveis básicas formam uma matriz identidade. – Na linha da função objectivo, todas as variáveis básicas têm coeficiente 0. – Os termos independentes são sempre maiores ou iguais a zero (manter válida a não-negatividade). Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 47 Simplex •A cada quadro simplex corresponde uma solução básica admissível imediatamente perceptível através das variáveis básicas e da coluna dos termos independentes. – No exemplo, x3=200, x4=230, x5=70. •A solução associada ao quadro simplex é óptima? Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 48 Simplex •Não! Se se aumentar o valor de x1 ou x2 o valor de z aumenta (e pretende-se maximizar o valor de z). O que o coeficiente -10 de x1 (linha da função objectivo) significa é que por cada unidade de aumento de x1 o valor da função objectivo, aumenta 10 unidades (o sinal negativo é devido à mudança de membro efectuada inicialmente). •Em cada iteração do simplex passa-se (da base actual) para uma base adjacente (que se obtém da actual passando uma variável não básica a básica e uma variável básica a não básica - o número de variáveis básicas é constante). Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 49 Simplex •Não! Se se aumentar o valor de x1 ou x2 o valor de z aumenta (e pretende-se maximizar o valor de z). O que o coeficiente -10 de x1 (linha da função objectivo) significa é que por cada unidade de aumento de x1 o valor da função objectivo, aumenta 10 unidades (o sinal negativo é devido à mudança de membro efectuada inicialmente). •Em cada iteração do simplex passa-se (da base actual) para uma base adjacente (que se obtém da actual passando uma variável não básica a básica e uma variável básica a não básica - o número de variáveis básicas é constante). •Qual a variável mais promissora para entrar na base? Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 50 Simplex •A variável mais promissora é x1 (aumento de 10 unidades na função objectivo por unidade de aumento de x1, para x2 esse valor é 9 o que é pior já que se está a maximizar). – Isto é uma decisão gulosa, míope… não garante que seja a melhor decisão. – E se houver empate? (custos reduzidos iguais) Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 51 Simplex •Sendo assim x1 entra na base (passará a tomar um valor positivo)! – Qual a variável que sai base? •Como o aumento do valor de x1 aumenta o valor da função objectivo, queremos aumentar o mais possível o seu valor. – Qual é o limite? Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 52 Simplex • Tem de haver um limite (ou melhor, se não houver um limite o problema é ilimitado, mas não é esse o caso do exemplo). O que acontece às outras variáveis quando se aumenta o valor de x1 A variável x2 continua não básica (logo com valor igual a 0). As outras relacionam-se com x1 através das restrições. Qual a variável que deve sair da base? Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 53 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 54 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 55 Coluna pivot Universidade do Minho 2006 Simplex Investigação Operacional José António Oliveira – [email protected] 56 Coluna pivot Universidade do Minho 2006 Simplex Investigação Operacional José António Oliveira – [email protected] 57 Coluna pivot Simplex Linha pivot A variável que sai da base é x5, a primeira que se anula (logo passa a não básica) quando se tenta aumentar x1 o mais possível. A razão entre o valor da coluna dos termos independentes e o valor da coluna da variável que vai entrar na base para todas as linhas (cujo valor seja positivo) e escolher a menor. Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 58 Coluna pivot Simplex Linha pivot (Na resolução primal) O elemento pivot nunca pode ser negativo. Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 59 Coluna pivot Simplex Se houver empate na saída? – escolha indiferente: algoritmo pode entrar em ciclo – escolhe-se a razão de maior divisor: sai x3 Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 60 Simplex •Como obter o quadro correspondente à nova base? – Cada linha corresponde a uma equação de um sistema, logo • pode-se multiplicar toda a linha por uma constante • pode-se somar duas linhas, substituindo uma delas pelo resultado da soma, que o sistema de equações não se altera (só se altera a sua representação). No exemplo, a linha 3 (L3) é a linha pivot, fazendo as operações L3 / 2 (para a linha L3) 5L3 + L4 (para a linha L4) -2L3+L2 (para a linha L2) -(5/2)L3+L1 (para a linha L1) Coluna pivot •obtém-se o quadro simplex correspondente à nova base Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 61 Simplex Para experimentar e/ou verificar cálculos: http://www.tutor.ms.unimelb.edu.au/simplex_intro/index.html Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 62 PROGRAMAÇÃO LINEAR - PL • Fizemos uma iteração do algoritmo simplex primal: 1. Teste de optimalidade (a solução básica actual é óptima se todos os coeficientes da função objectivo (custos reduzidos) são não negativos). Se a solução é óptima, parar. Se não, prosseguir com o passo 2. Decidir qual a variável que entra na base (é aquela que tem o coeficiente mais negativo na linha da função objectivo - em caso de empate escolher a variável que “crescerá mais”. Se persistir o empate, escolher arbitrariamente). Prosseguir com o passo 3. Decidir qual a variável básica que sai da base (é aquela que tem a razão do critério de saída mais pequena - excluindo as razões negativas; em caso de empate, escolher o maior elemento pivot. Se persistir o empate, escolher arbitrariamente). Se não houver nenhuma razão estritamente positiva o problema é ilimitado, parar. Se não, prosseguir para 4. Actualizar o quadro simplex para a base actual e passar à iteração seguinte (passo 1). 2. 3. 4. Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 63 Simplex Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 64 Simplex • O quadro simplex obtido em qualquer iteração corresponde sempre a uma solução básica admissível e a um ponto extremo. • Quadro óptimo do exemplo (após duas iterações). Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 65 Simplex • Soluções alternativas – O que são? – Como se identifica a sua existência? •Custo(s) reduzido(s) NULO(s) nas variáveis não básicas. Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 66 Simplex • Degenerescência… – O algoritmo simplex pode entrar em ciclo (se não forem tomadas as devidas previdências) por causa da existência de soluções básicas degeneradas (soluções em que há variáveis básicas com valor zero). – A causa é a presença de restrições redundantes (que não são fáceis de detectar analiticamente...). De uma iteração para a seguinte, pode acontecer que a base seja diferente, mas o valor das variáveis de decisão seja o mesmo (uma básica com valor zero sai da base e uma não básica entre na base com valor zero). Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 67 Simplex • Degenerescência… – Na prática, o software actual tem implementadas formas de lidar com a degenerescência (através de regras mais sofisticadas do que escolher arbitrariamente a variável que entra na base em caso de empate). – De qualquer maneira, em problemas muito degenerados, este fenómeno pode abrandar significativamente a execução do método. Um só ponto extremo e duas bases! Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 68 Simplex •Como obter um quadro simplex válido para um problema que tenha restrições de igualdade e/ou de maior ou igual? – Note-se que, se o problema só tiver restrições de "menor ou igual", temos sempre uma base "à mão": a constituída pelas variáveis de folga - como no exemplo anterior. – O ponto de solução nula pertence ao espaço de soluções válidas, e forma-se a base com as variáveis de folga. Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 69 Simplex •Modelos (a) e (b) são equivalentes. – O modelo (b) está na forma estandardizada e inclui uma variável de excesso (primeira restrição) e uma variável de folga (segunda restrição). – Para a segunda linha é fácil encontrar uma variável básica inicial (tem coeficiente 1 na própria linha e 0 nas restantes). – Qual a variável básica a associar à primeira linha? Não é claro. Não há nenhuma variável que tenha coeficiente 1 na própria linha e 0 nas restantes. •Modifica-se o modelo por inclusão de variáveis artificiais ->vê-se isso na próxima aula Universidade do Minho 2006 Investigação Operacional José António Oliveira – [email protected] 70
Download
