Exemplo ( Algoritmo Dual do Simplex ) IO
Minimizar:
z = 10x1 + 5x2
Sujeito a:
20x1 + 50x2 ≥ 200
50x1 + 10x2 ≥ 150
30x1 + 30x2 ≥ 210
x1,x2 ≥0
Dado a forma assumida por este problema, pode aplicar-se imediatamente o algoritmo do dual do simplex com efeito, a estandardização do problema seguido da MULTIPLICAÇÃO DE TODAS AS EQUAÇÕES por (-1) conduz a uma forma canónica em que se identifica uma solução básica não admissível do primal a satisfazer o critério óptimo tal como é exigido pelo algoritmo dual do simplex.
1º Quadro do Algoritmo Dual do Simplex
Aplicando o algoritmo dual do simplex selecciona-se em primeiro lugar o vector a sair da base; esta selecção é feita através do critério
min{ xi0 | xi0 <0}
pelo que, neste caso, x2 sai da base pois
X2=min{ -200, -150, -210}
O vector a entrar na base é determinado por:
min{ Zj-Cj / xsj | xsj < 0}
min{ -10/-30, -5/30} = 5/30
devendo portanto o vector x2 entrar na base, aplicando o método de Gauss- Jordan, tornando x52=-30 como elemento redutor, tem-se 0 2º quadro do algoritmo dual do Simplex
Como a solução obtida não é admissível aplicam-se de novo os critérios de saída e entrada, verificando que S2 sai da base sendo substituído por x1, obtendo-se após condensação, a nova solução que se apresenta no quadro seguinte:
A solução obtida é admissível, tratando-se da solução óptima do problema primal
