Compreender o Simplex

1º Regras essenciais a) O simplex é apenas outro método para obter uma solução de um problema de programação linear. b) O simplex resolve-se através de um quadro: o quadro do simplex. c) No simplex existem apenas problemas de maximização. Se quisermos minimizar deveremos fazer: Max –Z d) Para resolver qualquer problema por est método é necessário cococá-lo na forma normal: Maz Z = 0 e) No simplex existem uma função quese pretende maximizar (função objectivo) e as restrições. Existem também variáveis básicas (as que figuram na base) e as não básicas) f) Uma variável é degenerada quando é básica e assume valor igual a zero. g) O número de variáveis básicas deverá ser igual ao número de restrições. h) Variaveis não básicas assumem valor nulo. i) As variáveis que poderão figurar no primeiro quadro do simplex são as de folga e as artificiais. As de excesso nunca na vida! j) Quando tivermos restrições de < devemos introduzir uma variável de folga s. k) E quando tivermos restrições de > ou = devemos usar o método do BIG M e introduzir variáveis artificiais (u) l) E se tivermos variáveis < 0 (ex: x1 <0), devemos fazer assim:
X*>0, resolvemos pelo simplex e depois nop fim inverte-se outra vez o sinal.
2ª Exemplo da aplicação do dito simplex:
Max Z = x1 + 2x2
s.a : x1 + x2<6 x1+2x2< 10
Primeiro passo a dar:
Forma normal: Maz z= 0 ↔ Max Z – x1 – 2x2 = 0
Segundo passo a dar:
Temos duas restrições de < ou igual: e agora?
Então agora introduzes uma variável de folga para compensar....
Então vem: x1 + x2 +s1= 6 X1+ 2x2 + s2 = 10
Então mas o “s” é o quê? São as variáveis folga.

Agora ides proceder à contrução do quadro do simplex.
Para quê o quadro? Para determinar a solução óptima | X1 | X2 | S1 | S2 | RHS | S1 | 1 | 1 | 1 | 0 | 6 | S2 | 1 | 2 | 0 | 1 | 10 | Z | -1 | -2 | 0 | 0 | 0 |

Como preencho este quadro?
Primeira linha : colocas todas as variáveis (folga, excesso, não básicas como x1 e x2)
Primeira coluna: colocas só e unicamente as variáveis básicas (folga ou artificiais)
Segunda linha e terceira linha: colocas os coeficientes das restrições até à coluna RHS. Deves saber o que são os coeficientes, não é?
Última linha: coeficientes da função objectivo ate à coluna RHS
RHS, mas o que é isso ? lado direito das restrições e função objectivo.
Lado direito restrição 1= 6 mete-se lá na coluna
Lado direito segunda resttrição 2= 10 mete-se lá na coluna
Na linha Z: mete-se os coeficientes na forma normal: -1, -2 (...)
Então e agora?
Escolhe-se agora o valor mais negativo da linha do Z. Qual é? R: -2
E depois? Divide-se o valor na coluna RHS pelos elementos presentes na coluna do -2 e Vê-se qual o mais baixo. Qual é? R: 6/1= 6 ; 10 /2= 5 e assim escolhe-se a linha 2.
Então: a coluna pivot é a segunda e o elemento pivot é o 2 dessa coluna.
Então: x2 entra na base e s2 sai.
E agora?
Vamos pôr o elemento 2 igual a 1 para facilitar os cálculos e os elementos da coluna do 2 iguais a zero.
AH bom, mas como?
Multiplicas a segunda linha toda por -1/2 para pôr o elemento 2 igual a 1.
Mau, e os outros que têm de estar iguais a zero, como é?
-Qual é o número que multiplicado por 2 mais 1 dá zero? Vem: 2X+1=0 ↔ X=-1/2
- Qual é o número que multiplicado por 2 mais -2 dá zero? É fazer a mesma coisa como fiz em cima.
E o acontece aos outros números ?
- Multiplica-se o número que achámos à bocado por cada elemento das linha do -2 e soma-se a cada elemento da linha anterior e posterior. Isto é muito simplex, não é?
Assim: -1/2 × 1 +1 : multiplicar -1/2 por 1 que está na segunda linha (é logo o primeiro elemento) e depois somar ao elemento imediatamente em cima). Quem diz para cima também diz para baixo.
E vai-se repetindo este procediemento todo até os elementos da linha do Z serem todos positivos. Estamos no óptimo.
Assim vem: | X1 | X2 | S1 | S2 | RHS | S1 | 1/2 | 0 | 1 | -1/2 | -1 | X2 (entrou) | 1/2 | 1 | 0 | 1/2 | 5 | Z | 0 | 0 | 0 | 1 | 0 |

Já estamos no óptimo