Slide - Teorema Fundamental e Método Dual Simplex - 2020-1

Programação Linear Gilberto de Miranda Jr. & Alexandre X. Martins DEENP/ICEA/UFOP – 2020/1 Teoria da Dualidade: Aula 03: Teorema Fundamental e Método Dual SIMPLEX Material parcialmente retirado de ‘Linear Programming and Network Flows’, 4a. Edição, 2010 – Wiley – by Bazaraa, Jarvis & Sherali e também de ‘Otimização Linear’, 1a. Edição, 2011, Ed. UNB – by Maculan & Fampa. Sumário ● Teorema Fundamental da Dualidade ● Método Dual SIMPLEX Dualidade em Programação Linear ● Relembrando: – Dado um PPL em forma canônica, denominado Primal (P): – A ele está associado um outro PPL denominado Dual (D): Dualidade em Programação Linear (I) Se A⋅x ⩾ b e w ⩾ 0 então wT⋅A⋅x ⩾ wT⋅b. (II) Se wT⋅A ⩽ cT e x ⩾ 0 então wT⋅A⋅x ⩽ cT⋅x. (III) De (I) e (II) vem wT⋅b ⩽ wT⋅A⋅x ⩽ cT⋅x. E na otimalidade temos wT⋅b = wT⋅A⋅x = cT⋅x. ● No entanto sabemos que não existe garantia a priori de que a região de viabilidade primal ou dual seja não-vazia. ● Caso o primal seja inviável, isto é, possua região de viabilidade vazia, o que acontece com o dual? ● E se o primal for ilimitado, o que acontece com o dual? ● Embora tenhamos discutido isso de passagem, não nos debruçamos sobre essa matéria e nem utilizamos resultados matemáticos para embasar nenhuma conclusão. ● Essa discussão dá origem ao resultado que se conhece como Teorema Fundamental da Dualidade. Dualidade: Teorema Fundamental ● Dado que wT⋅b ⩽ wT⋅A⋅x ⩽ cT⋅x , se o primal tiver mínimo ilimitado, não existe quota inferior wT⋅b que seja finita, logo o dual é inviável. ● Dado que wT⋅b ⩽ wT⋅A⋅x ⩽ cT⋅x , se o dual for ilimitado, não existe quota superior cT⋅x que seja finita, logo o primal é inviável. ● Mas veja que se o problema de entrada for inviável, não sabemos se seu dual é ilimitado ou inviável. Dualidade: Teorema Fundamental ● Sumarizando: ● Este é o Teorema Fundamental da Dualidade. Dualidade: Teorema Fundamental Problema\Saída Ilimitado Inviável Primal Inviável Ilimitado ou inviável Dual Inviável Ilimitado ou inviável ● Seja o PPL: ● Se todos os parâmetros forem não-negativos, até agora só dispomos do método primal SIMPLEX, com a primeira fase unicamente dedicada à obtenção de uma primeira solução básica viável. Método Dual Simplex ● Convertendo o PPL para a forma padrão vem: ● Dualizando: Método Dual Simplex min ∑ j c j x j+∑ i 0 xi s s . t . : ∑ j ∈E aij x j− xi s=bi , ∀ i x j , xi s≥0, ∀ i max ∑ i ui bi s . t . : ∑ i∈ E ui aij≤c j , ∀ j −ui≤0, ∀ i - Note que ao zerar todas as variáveis duais u, a solução que temos seria dual viável, mas primal inviável, e portanto sub-ótima!!! ● A idéia do Método Dual Simplex, portanto, é resolver o problema Dual diretamente no Tableau SIMPLEX primal. ● Partindo de uma solução Dual viável, mas primal inviável, busca-se a viabilidade primal (ou a Otimalidade, se preferir) enquanto se mantém a viabilidade Dual. ● No caso de problemas na forma primal canônica em que todos os parâmetros são não-negativos, isso significa evitar toda a primeira fase (busca de viabilidade primal) do algoritmo. ● É particularmente útil quando o problema será modificado iterativamente através de adição de restrições. (???!!!.) Método Dual Simplex ● Partindo de: ● Negamos as restrições obtendo: ● Agora, escolhemos como primeira base as colunas associadas às variáveis de folga xsi, o que seria equivalente a escolher ui = 0, e procedemos ao Tableau... Método Dual Simplex min∑ j c j x j+∑ i 0 xi s s . t . : ∑ j ∈E aij x j− xi s=bi , ∀ i x j , xi s≥0, ∀ i min∑ j c j x j+∑ i 0 xi s s . t . : −∑ j ∈E aij x j+ xi s=−bi , ∀ i x j , xi s≥0, ∀ i ● Tableau Dual SIMPLEX - inicial: ● Tableau Dual SIMPLEX - iteração genérica: Método Dual Simplex [cB B­1 A – cN] = [u Aj – cj] = (zj – cj) = ­ cj 0 z0 = cB B­1 b = u b = 0 ­ B­1 A = ­ I A = ­ A B = I ­ B­1 b = ­ I b = ­ b ­ cj 0 z0 = cB B­1 b = u b = 0 ­ A I ­ b (zj – cj) 0 z0 = cB B­1 b = u b Y = ­ B­1 N I ­ B­1 b ● Tableau Dual SIMPLEX - iteração genérica: ● A partir daí escolhemos como linha de entrada (variável dual que entra na base) aquela que corresponde à maior inviabilidade primal, isto é a linha que contém o valor mais negativo para o termo independente -B-1b. ● O teste para decidir qual é a variável dual que sai da base obdece à mesma lógica do primal SIMPLEX: escolher a variável dual que é básica na desigualdade dual mais justa... Método Dual Simplex (zj – cj) 0 z0 = cB B­1 b = u b Y = ­ B­1 N I ­ B­1 b ● Exemplo: Seja o PPL ● Em forma Tableau: Método Dual Simplex Teste da Razão: c1: - 2 / - 2 = 1 c2: - 4 / - 3 = 1.333 Operações: L2 = L2 / - 2 L1 = L1 + L2 Z = Z + 2 L2 ● Exemplo: (Continuação) Método Dual Simplex Teste da Razão: c2: - 4 / - 5/2 = 8 Operações: L1 = L1 / (-5/2) L2 = L2 + (½) L1 Z = Z + 4 L1 ● Exemplo: (Continuação) ● Se a solução atual é primal e dual viável, então é ótima!!! Método Dual Simplex [uA – c] = zj ­ cj ⩽ 0 : Dual Viável b ⩾ 0 : Primal Viável Muito Obrigado !!! Questões??? gilbertomirandajr@gmail.com gilberto.junior@ufop.edu.br