Slide - Interpret Econômica e Ligações com o Simplex - 2020-1

Programação Linear Gilberto de Miranda Jr. & Alexandre X. Martins DEENP/ICEA/UFOP – 2020/1 Teoria da Dualidade: Aula 02: Interpretação Econômica e Conexões com o 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 ● Dualidade e o Método SIMPLEX ● Interpretação Econômica da Dualidade Dualidade em Programação Linear ● Resumo dos resultados alcançados até agora: – 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. ● Esse resultado é conhecido como Teorema da Dualidade Fraca em Programação Linear. É possível extrair dele também um sistema na forma: wT⋅ [b – A⋅x] = 0 [wT⋅A – cT]⋅x = 0 Esse sistema é também conhecido como Teorema da Complementaridade de Folgas ou Condição de Folgas Complementares. ● Condições de Karush-Kuhn-Tucker para Programação Linear: (a) Viabilidade Primal: A⋅x ⩾ b, x ⩾ 0 (b) Viabilidade Dual: w ⩾ 0, wT⋅A ⩽ cT (c) Complementaridade de Folgas: wT⋅[b – Ax] = 0, [- cT + wT⋅A ]⋅x = 0 ● Portanto, as variáveis duais de programação linear correspondem aos multiplicadores de Lagrange – ou variáveis duais Lagrangeanas – associados às restrições de um PPL e as Condições KKT quando escritas para um PPL são exatamente as condições de otimalidade previstas na Teoria da Dualidade em Programação Linear. Dualidade em Programação Linear ● Algumas consequências dos resultados, que podem ter passado despercebidas: – (I) Só há uma solução capaz de assegurar a viabilidade Primal e também a viabilidade Dual: A solução ótima, ou melhor dizendo o par ótimo (x*, w*). – (II) Logo, toda solução básica Primal viável que não é ótima tem que ser Dual inviável. – (III) Pode-se portanto argüir que o contraponto também é verificável, isto é, toda solução básica Dual viável que é sub-ótima é Primal inviável. ● Enfim: Ao executar o Método SIMPLEX dispondo de uma solução básica Primal viável, a busca da otimalidade tem que se traduzir na busca da viabilidade Dual, e vice-versa!!! Dualidade e o Método SIMPLEX ● Mas seria possível ver isto diretamente no algoritmo? Isto é, haveria como detectar a invibilidade dual diretamente ao lançar o método? ● Vejamos: Ao dispor da primeira solução básica viável B, induzimos o particionamento do problema original em B e N e seguimos com o algoritmo: B xB + N xN = b ∴ xB + B-1 N xN = B-1 b Substituindo xB na função objetivo vem: z = cB xB + cN xN ∴ z = cB [ B-1 b - B-1 N xN ] + cN xN ∴ z = cB B-1 b - cB B-1 N xN + cN xN Fazendo w = cB B-1 igual temos: z = w b - w N xN + cN xN ∴ z = w b - [ w N - cN ] xN Dualidade e o Método SIMPLEX ● Algumas observações importantes sobre z = w b - [ w N - cN ] xN : – A quota da função-objetivo que não depende mais de x, z0, está escrita em sua versão dual w b. – A parcela [ w N - cN ] xN é uma partição de [ w A - c ] x induzida pela base primal viável B. – Note que os valores de wb sub-ótimos são duais inviáveis, uma vez que é possível identificar colunas em N que são tais que [ w A - c ] é positivo (condição de entrada para compor a nova base B). – Caso contrário, quando se atinge a condição de parada do SIMPLEX, todas as colunas não-básicas são tais que [ w N - cN ] xN ⩽ 0, e as colunas na base são tais que [ w B - cB ] = 0 (porque w = cBB-1 !!!), ou seja, [ w A - c ] ⩽ 0 e a solução é dual viável !!! – Como a regra de saída da base garante a manutenção da viabilidade primal a solução ótima é primal e dual viável, como prescrito pelas Condições KKT para Programação Linear. Dualidade e o Método SIMPLEX ● Dessa forma, na ausência de degeneração, temos o seguinte: – Na solução ótima, que primal e dual viável, todos os preços (ou variáveis duais) w são tais que: (a) São suficientes para remunerar os custos, isto é, w A = c, e portanto a variável primal associada com esta linha dual é básica na solução ótima. Como [ w A – c ] = 0, a quota primal x fica livre para assumir valor não-nulo (básico), pois a condição de folgas complementares está naturalmente satisfeita. (b) Ou então os preços w são insuficientes para para remunerar os custos, situação em que w A < c, e logo a única maneira de satisfazer a condição de folgas complementares é manter x = 0 (não-básico). – Mas já esperávamos por isso, dado que a maior receita possível (o máximo valor agregado) em um modelo de programação linear para um sistema é equivalente ao mínimo custo atingível, isto é, w b = c x para o par (x, w) ótimo. – Essa é a Condição de Equilíbrio Econômico, que preconiza que em mercados perfeitos, a taxa de lucro de qualquer atividade é zero, uma vez que só se aufere valor suficiente para remunerar os custos na igualdade. Interpretação Econômica da Dualidade ● A Teoria da Dualidade em Programação Linear foi fundamental no desenvolvimento teórico da Economia Matemática e da Análise Micro- Econômica. ● É importante destacar que embora a Condição de Equilíbrio Econômico pareça contra-intuitiva se comparada à realidade da maioria das economias de mercado capitalistas contemporâneas, ela é perfeitamente hígida do ponto de vista de Engenharia: Ela viabiliza um Regime Permanente Econômico, no qual os custos marginais são cobertos pelos preços marginais, situação em que todos os agentes econômicos são mantidos minimamente saudáveis sem prejuízos. ● Também é importante salientar que mercados reais têm perturbações como diferenciais tecnológicos, subsídios, impostos, propriedades intelectuais, informação assimétrica, contratos com cláusulas de exclusividade, cartéis setoriais e etc, e logicamente estão muito distantes das condições que definem mercados perfeitos. ● A interpretação econômica da Teoria da Dualidade em Programação Linear também permitiu mimetizar dos mercados a noção de coordenção por preços, peça fundamental do Princípio de Decomposição de Dantzig-Wolfe, que estudaremos mais adiante no curso. Interpretação Econômica da Dualidade min ∑ (i , j)∈ E cij xij sujeito a : ∑ ( j , i)∈E x ji− ∑ (i , j)∈ E xij=di , ∀ i ∈V xij≤kij , ∀ (i , j)∈ E xij≥0, ∀ (i , j)∈ E ● Exemplo: Construção da formulação dual com interpretação econômica. Seja o Problema de Fluxo a Custo Mínimo, tradicional formulação de fluxos em redes, dado a seguir: Aqui E é o conjunto de arcos da rede de transporte subjacente, N é o conjunto de nodos, cij são os custos de transporte por unidade de fluxo, di é a demanda do i-ésimo nodo da rede, kij é capacidade máxima de transporte em cada arco e xij decide o fluxo transportado em cada arco (i,j) da rede. Interpretação Econômica da Dualidade 1a. Lei de Kirchoff min ∑ (i , j)∈E cij xij sujeito a : ∑ ( j , i)∈E x ji− ∑ (i , j)∈ E xij≥di , ∀ i ∈V : si − ∑ ( j , i)∈ E x ji+ ∑ (i , j)∈ E xij≥−di , ∀ i ∈V : ti −xij≥−kij , ∀ (i , j)∈ E : aij xij≥0, ∀ (i , j)∈E ● Exemplo: Para construir a formulação dual de PL do PFCM, primeiro devemos convertê-lo à forma primal canônica: Em seguida associamos variáveis duais às várias famílias de restrições primais, conforme indicado ao final de cada família de linhas. Interpretação Econômica da Dualidade ∑ (i , j)∈E xij− ∑ ( j , i)∈ E x ji≥d j , ∀ j ∈V : s j − ∑ (i , j)∈ E xij+ ∑ ( j , i)∈ E x ji≥−d j , ∀ j∈V : t j max ∑ i ∈N di si−∑ i ∈N di ti− ∑ (i , j)∈ E kij aij sujeito a : s j−t j−si+ti−aij≤cij , ∀ (i , j)∈ E si≥0, ∀ i ∈N ti≥0, ∀ i ∈N aij≥0, ∀ (i , j)∈E ● Exemplo: Agora sabemos qual é a forma algébrica do problema dual, ela aparece como a seguir: Lembrando que diferenças de variáveis não-negativas são equivalentes a variáveis irrestritas em sinal, e reescrevendo -si+ti como -(si -ti), podemos substituir cada (s-t)i por um preço pi irrestrito em sinal, se colocarmos di em evidência na função-objetivo… ● Observação-chave: Note que para escrever a equação dual é preciso pensar tanto no balanço de fluxos para o nodo i quanto para o nodo j, situação em que todos os índices se invertem e todos os preços mudam de sinal. Interpretação Econômica da Dualidade i j ∑ (i , j)∈ E xij− ∑ ( j , i)∈ E x ji≥d j , ∀ j∈V : s j − ∑ (i , j)∈ E xij+ ∑ ( j , i)∈ E x ji≥−d j , ∀ j∈V : t j max ∑ i ∈N di (s−t)i− ∑ (i , j)∈E kij aij sujeito a : (s−t)j−(s−t)i−aij≤cij , ∀ (i , j)∈ E si≥0, ∀ i ∈N ti≥0, ∀ i ∈N aij≥0, ∀ (i , j)∈E ● Exemplo: Depois de todas as manipulações propostass, resulta: ⇛ Interpretação Econômica da Formulação Dual: – Se o primal decide a quota de fluxo por arco, o dual decide o valor do produto em cada nodo da rede. – Ao mover o preço dual aij para o lado direito das desigualdades duais ele se soma aos custos cij, logo ele tem papel de taxa de uso da capacidade kij do arco (i,j). – A diferença de valor do produto entre a origem i e o destino j deve cobrir os custos de transporte mais a taxa de uso da rota, senão a rota deixa a solução ótima!!! Interpretação Econômica da Dualidade max ∑ i ∈N di pi− ∑ (i , j)∈E kij aij sujeito a : p j− pi−aij≤cij , ∀ (i , j)∈ E aij≥0, ∀ (i , j)∈E ● Interpretação Econômica da Formulação Dual: – Caso o operador da rede precise ou queira induzir uma dada rota que não é básica na solução ótima, agora, ele sabe como interferir: Ou reduz os custos unitários de transporte (via substituição de tecnologia) ou disponibiliza maior capacidade, reduzindo a soma (aij+cij). – Portanto, mais do que entregar informação de ‘distância’ para a otimalidade, a leitura dos preços duais permite orientar o investimento, pois traz informação sobre a sensibilidade da solução ótima às mudanças de tecnologia e melhorias de infra-estrutura. – Outra informação de natureza tática/estratégica importante que é tornada visível é relativa a qual é o menor preço de mercado (não confundir com os preços duais, internos ao sistema do operador) que o operador pode praticar (em situação de competição por market share), sem com isso entrar em situação deficitária. Interpretação Econômica da Dualidade Muito Obrigado !!! Questões??? gilbertomirandajr@gmail.com gilberto.junior@ufop.edu.br