Aula 7: Método Simplex e Análise de Sistemas Ambientais

CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DE MINAS GERAIS COORDENAÇÃO DO CURSO DE ENGENHARIA AMBIENTAL E SANITÁRIA DEPARTAMENTO DE CIÊNCIA E TECNOLOGIA AMBIENTAL Aula 7 Simplex Análise de Sistemas Ambientais Prof Frederico Keizo Odan Análise de Sistemas Ambientais As restrições do problema de PL definem semi espaços A intersecção do conjunto de semiespaços define a região factível As soluções ótimas recaem sobre vértices pontos extremos da região factível A solução ótima depende da função objetivo Tais conclusões se estendem a PL de n dimensões Conclusão das aulas anteriores Hipóteses e Propriedades do modelo de PL Proporcionalidade Aditividade Divisibilidade Coeficientes constantes Hipóteses e Propriedades do modelo de PL Proporcionalidade Função Objetivo FO Ci Xi o Ci coeficiente de custo Restrições o Aij Xi bj Aij e bj são coeficientes Hipóteses e Propriedades do modelo de PL Aditividade FO R σ Ci X i Restrições σaij X i bj j 12 Hipóteses e Propriedades do modelo de PL nos racionais As variáveis podem assumir valores fracionários não inteiros Divisibilidade 𝑋𝑖 Q Hipóteses e Propriedades do modelo de PL Cenário Determinístico Coeficientes aij bj e ci são considerados constantes e conhecidos Hipótese adicional para o Simplex Todas as variáveis devem ser não negativas Método Simplex Problema anterior Sistema de inequações Como transformar o sistema de inequações em um sistema de equações lineares Seja o seguinte problema de otimização Método Simplex Problema anterior Sistema de inequações Como transformar o sistema de inequações em um sistema de equações lineares limitação da capacidade da ETR limitação de resíduo lançado unidades tratadas nãonegatividade 2 X1 X2 X3 10 04 X1 15 X2 X4 4 2 X1 X2 X5 0 X3 e X4 variáveis de folga X5 variável de excesso Seja o seguinte problema de otimização Método Simplex Sistema linear m 5 incógnitas n 3 equações Sistema indeterminado com infinitas soluções Esta representação assemelhase ao sistema de inequações infinitas soluções infinitos pontos viáveis dentro da região factível Como transformar sistema indeterminado em determinado 2 X1 X2 X3 10 04 X1 15 X2 X4 4 2 X1 X2 X5 0 Método Simplex Sistema linear m 5 incógnitas n 3 equações Sistema indeterminado com infinitas soluções Esta representação assemelhase ao sistema de inequações infinitas soluções infinitos pontos viáveis dentro da região factível Como transformar sistema indeterminado em determinado Para encontrar uma solução arbitrase valor para 2 variáveis e podese obter as outras 3 2 X1 X2 X3 10 04 X1 15 X2 X4 4 2 X1 X2 X5 0 Método Simplex Seja a equação 2X1 X2 X3 10 Explicitando X3 10 2X1 X2 o Em P132 X3 10 232 6 o Em B50 X3 10250 0 o Em P282 X3 10 282 4 0 1 2 3 4 5 9 8 7 6 0 2 8 10 P132 E05 D24 C62 F100 B50 4 6 X1 Unidades fabricadas A 00 P282 Área factível Método Simplex Seja a equação 2X1 X2 X3 10 Explicitando X3 10 2X1 X2 o Em P132 X3 10 232 6 o Em B50 X3 10250 0 o Em P282 X3 10 282 4 0 1 2 3 4 5 6 9 8 7 0 2 8 10 P132 E05 D24 C62 F100 B50 4 6 X1 Unidades fabricadas A 00 P282 Intersecção de equações vértices C62 X3 10262 0 X4 4046082 0 X3 X4 0 Área factível Método Simplex Solução Básica Anteriormente 3 equações n3 5 incógnitas m5 Fixandose 2 variáveis 0 intersecção entre retas restrições São denominados pontos extremos No problema anterior A B C F são pontos extremos Se o problema possuir mais de 2 variáveis a região factível tornase um poliedro convexo no espaço n dimensional Método Simplex Solução Básica Definida ao fixar mn variáveis como 0 zero Todos os pontos extremos vértices são soluções básicas 0 1 2 3 4 5 9 8 7 6 0 2 8 10 E05 D24 C62 F100 B50 4 6 X1 Unidades fabricadas A 00 Área factível Método Simplex Solução Básica Factível Está contida no interior da região factível A B C e D Infactível Está fora da região factível E e F 0 1 2 3 4 5 6 9 8 7 0 2 8 10 E05 D24 C62 F100 B50 4 6 X1 Unidades fabricadas A 00 Método Simplex Representação da PL na forma canônica padrão FO Sujeito à Para o problema anterior A matriz tecnológica b recursos disponíveis cT vetor de custos Max Z cTX A X b A 2 1 04 15 2 1 b 10 4 0 X X1 X2 cT 5 1 Método Simplex A 2 1 1 0 0 04 15 0 1 0 2 1 0 0 1 b 10 4 0 0 0 X X1 X2 X3 X4 X5 cT 5 1 0 0 0 Formato Padrão do problema de otimização Introduzindose as variáveis de folga ou excesso BL 5X1 X2 0X3 0X4 0X5 2 X1 X2 X3 X4 04 X1 15 X2 2 X1 X2 10 4 X5 0 Método Simplex Busca pela solução ótima Pontos extremos candidatos à solução ótima Seria possível testar todos os pontos extremos n c n n n n m Se n100 m80 C 53610²¹ Necessário uma busca eficiente Método Simplex Procedimento de busca Divisão da solução em Conjunto de variáveis básicas I conjunto de soluções básicas Ex I 123 Conjunto de variáveis nãobásicas J conjunto de soluções não básicas Ex J 45 Matricialmente Max Z CIXI CJXJ sujeito à AIXI AJXJ b XI 0 e XJ 0 XI X1 X2 X3 2 4 10 JX X4 X5 0 0 Método Simplex Procedimento de busca 1 Escolher n variáveis básicas Ex de folga ou excesso inicialmente 2 Passar de uma solução básica factível a outra melhorando a FO Basta trocar uma variável que está na base Xi I por outra variável nãobásica Xj J A cada mudança apenas uma variável é substituída A escolha é em função do custo relativo de cada variável não básica o Em Max escolhese variáveis que aumentem a FO cj 0 Método Simplex Procedimento de busca 3 Após definir variável que entrará na base realizase eliminação de GaussJordan pivoteamento 4 A busca é finalizada quando não existe mudança que melhore a FO i e cj 0 para max Método Simplex Exemplo de aplicação Seja o seguinte Problema Zmax X1 2X1 X1 X2 X2 8 2X2 7 X2 3 Método Simplex Exemplo de aplicação Inserindo as variáveis de folgaexcesso X1 X2 Zmax 2X 1 X2 X3 8 X1 2X2 X4 7 X2 X5 3 1 Iniciase com base I Método Simplex Exemplo de aplicação Inserindo as variáveis de folgaexcesso X1 X2 Zmax 2X 1 X2 X3 8 X1 2X2 X4 7 X2 X5 3 1 Iniciase com base I 345 Portanto X1 0 X2 0 X3 8 X4 7 X5 3 Variáveis X1 e X2 não básicas possuem custo relativos cj 0 c1 1 e c2 1 Método Simplex Exemplo de aplicação 2 Como c1 c2 1 Qual escolher X1 ou X2 como novas variáveis básicas Método Simplex Exemplo de aplicação 2 Como c1 c2 1 podese escolher X1 ou X2 como novas variáveis básicas Escolhese arbitrariamente X2 mantendo X1 fora da base É necessário determinar qual variável básica sairá para dar lugar a X2 Método Simplex Exemplo de aplicação Para tanto é necessário determinar qual impacto da entrada de X2 nas demais variáveis o Anteriormente 8 X2 7 2X2 3 X2 o Avaliando o impacto X3 X4 X5 obs X1 0 X4 2X1 X2 X3 X1 2X2 X2 8 7 X5 3 Método Simplex Exemplo de aplicação Para garantir factibilidade cada variável deve ser maior ou igual a 0 X3 8 X2 0 X4 7 2X2 0 X5 3 X2 0 Método Simplex Exemplo de aplicação Para garantir factibilidade cada variável deve ser maior ou igual a 0 X3 8 X2 0 X2 8 X4 7 2X2 0 X2 72 X5 3 X2 0 X2 3 Qual a inequação mais limitante para X2 Método Simplex Exemplo de aplicação Para garantir factibilidade cada variável deve ser maior ou igual a 0 X3 8 X2 0 X2 8 X4 7 2X2 0 X2 72 X5 3 X2 0 X2 3 Qual a inequação mais limitante para X2 X2 3 No limite inferior da factibilidade 0 X2 3 e X5 0 Portanto X5 sai da base Antes I 345 I 342 Método Simplex Exemplo de aplicação Representação do Sistema de PL em tabela Tableau Simplex Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 1 1 0 0 0 Z X3 1 2 1 1 0 0 8 X4 2 1 2 0 1 0 7 X5 3 0 1 0 0 1 3 X1 X2 Zmax 2X1 X2 X3 8 X1 2X2 X4 7 X2 X5 3 Método Simplex Exemplo de aplicação Após determinação da variável que sai da base definese o elemento pivô 3 Pivoteamento do elemento a32 1ª Iteração Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 1 1 0 0 0 Z X3 1 2 1 1 0 0 8 X4 2 1 2 0 1 0 7 X5 3 0 1 0 0 1 3 Método Simplex Exemplo de aplicação 3 Pivoteamento do elemento a32 1ª Iteração Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 1 1 0 0 0 Z X3 1 2 1 1 0 0 8 X4 2 1 2 0 1 0 7 X2 3 0 1 0 0 1 3 x2 Multiplicar restrição 3 por 2 e somar à restrição 2 Método Simplex Exemplo de aplicação 3 Pivoteamento do elemento a32 1ª Iteração Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 1 1 0 0 0 Z X3 1 2 1 1 0 0 8 X4 2 1 0 0 1 2 1 X2 3 0 1 0 0 1 3 x1 Multiplicar restrição 3 por 1 e somar à restrição 1 Método Simplex Exemplo de aplicação 3 Pivoteamento do elemento a32 1ª Iteração Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 1 1 0 0 0 Z X3 1 2 0 1 0 1 5 X4 2 1 0 0 1 2 1 X2 3 0 1 0 0 1 3 x1 Multiplicar restrição 3 por 1 e somar FO Z Método Simplex Exemplo de aplicação 3 Pivoteamento do elemento a32 1ª Iteração a13 a24 e a32 1 pertencem a I 342 X1 e X5 0 pertencen a J 15 Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 1 0 0 0 1 Z3 X3 1 2 0 1 0 1 5 X4 2 1 0 0 1 2 1 X2 3 0 1 0 0 1 3 Método Simplex Exemplo de aplicação 3 2ª Iteração Qual será o próximo elemento a ir para a base Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 1 0 0 0 1 Z3 X3 1 2 0 1 0 1 5 X4 2 1 0 0 1 2 1 X2 3 0 1 0 0 1 3 Método Simplex Exemplo de aplicação 3 2ª Iteração X1 X5 maxZ3 c1 0 Portanto X1 será a próxima variável a entrar para a base Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 1 0 0 0 1 Z3 X3 1 2 0 1 0 1 5 X4 2 1 0 0 1 2 1 X2 3 0 1 0 0 1 3 Método Simplex Exemplo de aplicação 3 2ª Iteração Para manter factibilidade Análise de viabilidade X3 5 2X1 0 X1 52 X4 1 X1 0 X1 1 X2 3 X1 Método Simplex Exemplo de aplicação 3 2ª Iteração Para manter factibilidade Análise de viabilidade X3 5 2X1 0 X1 52 X4 1 X1 0 X1 1 X2 3 X1 irrestrito 312 Maior limitação X1 1 Portanto X4 sai da base e entra X1 I Pivoteamento será em relação a a21 1 Método Simplex Exemplo de aplicação 3 2ª Iteração Realizase pivoteamento de a21 1 Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 1 0 0 0 1 Z3 X3 1 2 0 1 0 1 5 X4 2 1 0 0 1 2 1 X2 3 0 1 0 0 1 3 Método Simplex Exemplo de aplicação 3 Resultado da 2ª Iteração Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 0 0 0 1 1 Z4 X3 1 0 0 1 2 3 3 X1 2 1 0 0 1 2 1 X2 3 0 1 0 0 1 3 Método Simplex Exemplo de aplicação 3 Resultado 2ª Iteração Apenas X5 possui custo relativo positivo Assim X5 deve entrar na base Pela Análise de viabilidade X3 deve sair da base I512 Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 0 0 0 1 1 Z4 X3 1 0 0 1 2 3 3 X1 2 1 0 0 1 2 1 X2 3 0 1 0 0 1 3 Método Simplex Exemplo de aplicação 3 Resultado 2ª Iteração Apenas X5 possui custo relativo positivo Assim X5 deve entrar na base Pela Análise de viabilidade X3 deve sair da base I512 Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 0 0 0 1 1 Z4 X3 1 0 0 1 2 3 3 X1 2 1 0 0 1 2 1 X2 3 0 1 0 0 1 3 Método Simplex Exemplo de aplicação 3 3ª Iteração Realizase pivoteamento de a15 3 Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 0 0 0 1 1 Z4 X3 1 0 0 1 2 3 3 X1 2 1 0 0 1 2 1 X2 3 0 1 0 0 1 3 Método Simplex Exemplo de aplicação 3Resultado da 3ª Iteração Próxima variável básica Por que Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 0 0 13 13 0 Z5 X5 1 0 0 13 23 1 1 X1 2 1 0 23 13 0 3 X2 3 0 1 13 13 0 2 Método Simplex Exemplo de aplicação 3 3ª Iteração Para esta base I512 não há variável nãobásica para substituir variável básica cj 0 Solução ótima Introdução de qualquer solução diminuiria FO Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 0 0 13 13 0 Z5 X5 1 0 0 13 23 1 1 X1 2 1 0 23 13 0 3 X2 3 0 1 13 13 0 2 Método Simplex Exemplo de aplicação Resultado Final Conjunto de variáveis básicas Conjunto de variáveis não básicas FO Z5 Variáveis Básicas Nº da restrição Coeficientes das variáveis na FO Z e na matriz A Z e vetor recurso X1 X2 X3 X4 X5 0 0 13 13 0 Z5 X5 1 0 0 13 23 1 1 X1 2 1 0 23 13 0 3 X2 3 0 1 13 13 0 2 XI X5 X1 X2 1 3 2 J X X3 X4 0 0 Método Simplex Exemplo de aplicação Pontos extremos associados às mudanças de base 0 1 2 3 4 5 6 7 8 9 0 1 2 3 6 7 4 5 X1 X50 C D E A Iteração Ponto Base Z X1 X2 X3 X4 X5 0 A I345 0 0 0 8 7 3 1 E I342 3 0 3 5 1 0 2 D I312 4 1 3 3 0 0 3 C I512 5 3 2 0 0 1 B X20 Método Simplex Exemplo de aplicação Classificação das restrições do modelo no ponto ótimo Recurso Restrição Valor da Folga Status 1 X3 0 Escasso 2 X4 0 Escasso 3 X5 1 Abundante Método Simplex Fluxograma Maximização Expressar o problema de PL na forma preparada Encontrar uma solução básica factível inicial Dentre as variáveis nãobásicas existe variável X j J j com cj 0 Solução é ótima FIM Escolhida a variável nãobásica Xj a entrar na base verificar a viabilidade e identificar a variável que sai da base Proceder a mudança de base Pivoteamento NÃO SIM Verificar se solução básica é factível Método Simplex Pivoteamento 1 Na linha do pivô a Substituir variável que sai da Base por uma variável Nãobásica b 2 Todas as outras linhas incluindo da FO Nova linha Linha atual Coeficiente da coluna do pivô Nova Linha Do Pivô x Nova Linha do Pivô Linha do pivô atual elemento Pivô Método Simplex Casos especiais Solução Degenerada Seja o Exemplo de PL Após 1 iteração o Há empate entre as soluções candidatas a saírem da base x3 e x2 escolha é arbitrária o Isso ocorre devido a intersecção entre mais de duas restrições hiperdeterminação de pontos extremos Variável Básica Restrição nº Coeficientes Z e o vetor recurso x1 x2 x3 x4 13 0 0 43 Z24 x3 1 13 0 1 13 3 x2 2 23 1 0 13 6 Método Simplex Casos especiais Solução Degenerada Seja o Exemplo de PL 10 9 8 7 6 5 4 3 2 1 0 0 2 4 6 8 X1 X20 10 hiperdeterminação Análise de Viabilidade R1 X2 313X1 0 X1 9 R2 X3 623X1 0 X1 9 Método Simplex Casos especiais Solução Múltipla Seja o exemplo de PL Após 2 iterações Max L 6X1 6X2 sa 15X1 4X2 24 3X1 15X2 21 X1 X2 8 X3 0 25 35 25 Variável Básica Restriçã o nº Coeficientes Z e o vetor recurso X1 X2 X4 X5 0 0 0 6 Z48 X2 1 0 1 0 35 245 X4 2 0 0 1 3910 215 X1 3 1 0 0 85 165 Variável nãobásica com custo nulo Método Simplex Casos especiais Solução Múltipla Seja o exemplo de PL Max L 6X1 6X2 sa 15X1 4X2 24 3X1 15X2 21 X1 X2 8 2 0 4 6 8 16 14 12 10 0 2 4 6 8 10 12 14 16 18 X1 S oluções múltiplas Método Simplex Casos especiais Solução Ilimitada Seja o exemplo de PL Após 1 iteração solução ainda não é ótima Pela análise de viabilidade escolhendose x1 como VB Rest 1 x1 20 Rest 2 x1 01 Max Z X1 X2 sa X 2 2 X1 2X2 4 X1 X2 0 Variável Básica Restrição nº Coeficientes Z e o vetor recurso x1 x2 x3 x4 1 0 1 0 Z2 x2 1 0 1 1 0 2 x4 2 1 0 2 1 0 1 Não foi encontrado variável candidata a sair da base Solução ilimitada Método Simplex Casos especiais Solução Ilimitada Seja o exemplo de PL 0 1 2 3 4 5 6 7 8 0 2 6 8 4 X1 Z aumenta indefinidamente São admitidas infinitas soluções Max Z X1 X2 sa X2 2 X1 2X2 4 X1 X2 0 2 X 2 Método Simplex Obtenção de Solução básica factível Nem sempre é possível obter uma solução inicial básica factível Exemplo Se x10 e x2 0 x32 x41 e x53 o Mas x3 e x4 são negativos não é factível É necessário iniciar o Simplex com uma solução básica factível Max Z x1 2x2 Max Z x1 2x2 x1 2x2 2 x1 2x2 x3 2 x1 x2 1 x1 x2 x4 1 x2 3 x1 x2 0 x2 x1 x2 0 x5 3 Método Simplex Obtenção de Solução básica factível Nem sempre é possível obter uma solução inicial básica factível Exemplo Max Z x1 2x2 x1 2x2 x3 x1 x2 x4 x2 2 1 x5 3 x1 x2 0 É necessário aplicar o Simplex em 2 fases o 1ª Fase obter solução factível o 2ª Fase resolver problema de otimização Método Simplex Obtenção de Solução básica factível Nem sempre é possível obter uma solução inicial básica factível Exemplo Adicionase mais 2 variáveis de folga x6 e x7 o Base I675 é factível xi0 o Realizase otimização Min x6x7 para que este problema seja equivalente ao original se as variáveis artificiais forem nulas o Este problema estará sujeito as restrições anteriores x1 2x2 x3 x1 x2 x4 x2 2 1 x5 3 x1 2x2 x3 x6 x1 x2 x4 x2 x5 2 x7 1 3 x1 x2 0 x1 x2 0 Método Simplex Minimização de um problema