Dualidade em Programação Linear

Prévia do material em texto

Dualidade em Programação Linear 
 A cada problema de programação linear de variáveis x1, x2 , ... , xn , está associado um outro problema de programação linear de variáveis y1, y2, ...,ym a que se designa por problema dual. O problema original é designado por problema primal. Portanto, o dual do problema dual é o problema primal. 
Transformação de um problema primal em dual 
Seja dado o seguinte problema de PL, na forma canónica (problema primal): 
	 
 
Das relações entre o primal e dual podemos enunciar o seguinte: 
· A matriz dos coeficientes técnicos do problema dual é igual à matriz transposta dos coeficientes técnicos do problema primal; 
· Os termos independentes do problema dual são os coeficientes da função objectivo do problema primal e vice-versa; 
· Se o problema primal for de maximização, o dual será de minimização, se o problema primal for de minimização, o dual será de maximização; 
· Se a restrição i do problema primal é uma igualdade, então a variável Yi é livre (não tem restrição de sinal); 
· Se uma restrição de desigualdade for do tipo oposto ao da respectiva forma canónica, então a correspondente variável dual é não positiva; 
· Se a variável Xi do primal não tem restrição de sinal, então a restrição j do dual é uma igualdade. 
 
Propriedades operacionais da dualidade 
P1- Em qualquer iteração do problema primal ou dual os valores das variáveis na base podem ser obtidos pela multiplicação da matriz que aparece sob as variáveis básicas usadas na solução inicial, pelo vector coluna contendo os valores originais dos recursos. 
P2- Em qualquer iteração do problema primal ou dual, os coeficientes de qualquer variável nas restrições podem ser obtidos pela multiplicação da matriz que aparece sob as variáveis básicas usadas na solução inicial, pelo vector coluna contendo os coeficientes originais da mesma variável nas restrições. 
P3- Em qualquer iteração do problema primal, a variável de folga do dual tem valor simétrico ao valor dos custos reduzidos correspondentes às colunas das variáveis de decisào. 
P4- Em qualquer iteração do problema dual, as variáveis de folga do primal são simétricos aos custos reduzidos das colunas correspondentes às variáveis de decisào duais. 
P5- Em qualquer iteração (ou na tabela terminal) do problema dual, a solução viável (ou a solução óptima) para o problema primal encontra-se na linha Zj nas colunas correspondentes à matriz inicial identidade. 
 
Método dual-simplex 
Dado um problema de minimização para resolvé-lo pelo método dual-simplex deve-se transformar as inequações do tipo  para  , em seguida aplicar os passos 1, 2, 3 e 4. 
Passso 1 -Elaborar um quadro simplex onde se identifique uma solução básica admissível para o dual (valores da última linha do quadro todos menores ou iguais a zero). 
Passso 2 -Verificar se a solução é óptima, isto é, se a solução é admissível para o primal (todos os bi maiores ou iguais a zero). Caso contrário, determina-se a variável que vai ser substituída na base e que corresponde à linha (linha pivotal) em que se verifica: min bi | bi  0  . 
Passso 3- Determinar a variável que vai entrar na base a que corresponde a coluna (coluna pivotal) onde se verifica, 	
 
Caso não exista nenhum arj<0 este algoritmo termina, sendo o problema dual ilimitado e o problema primal impossível. 
Passso 4- No caso de empate no critério de saída ou de entrada na base escolher a variável de menor índice. Identificado o elemento pivô, aplicar as regras de pivotação, para efectuar a mudança de solução básica admissível. 
Análise de sensibilidade 
Análise de sensibilidade se refere a como mudança na formulação de um problema de programação linear afecte a solução óptima. Poratnto, na análise de pós-optimização é abordado o impacto na solução óptima de alterações discretas nos parâmetros do modelo: alterações dos coeficientes da função objectivo, dos termos independentes e dos coeficientes da matriz, introdução de novas variáveis e de novas restrições. 
image1.jpg
image2.jpg
image3.jpeg
image4.jpg
image5.jpg