Exemplo ( Algoritmo Dual do Simplex ) IO

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