Fórum de Matemática
DÚVIDAS? Nós respondemos!

Olá boa tarde ... Não sei se essa dúvida pode ser respondida aqui, mas vou tentar...

Estudando Programação Linear me deparei com o seguinte PPL (Problema de Programação Linear):

Max Z = 2x + y
S.a:
4x – 2y ≥ 20
2x + y ≤ 10
- 3x + 3y ≤ -3
-2x – 2y ≤ -2
x ≥ 2
x ≤ 6
y ≤ 2
y ≥ -2


Gostaria se possível que me dessem umas dicas de como fazer o Pré-processamento para a resolução pelo Método Simplex.

Desde já agradeço e, peço desculpas se não for o lugar adequado para a dúvida...

O método do Simplex na sua forma mais usual é aplicado a um problema linear do tipo:
\(\max ~ c^Tx:
Ax=b
x\geq 0\) onde \(b,c,x\) são vetores colunas e \(A\) uma matriz.
Na prática isto é o mesmo que ter um conjunto de equações com variáveis não-negativas.
No problema dado, temos desigualdades em vez de equações e as variáveis não estão restritas a valores não-negativos.
Podemos transformar uma desigualdade em igualdade introduzindo uma variável extra não-negativa (denominada às vezes por variável de folga). Por exemplo, as desigualdades 4x – 2y ≥ 20 e 2x + y ≤ 10 ficariam 4x - 2y - a = -20 e 2x + y + b = 10 (tome nota que o sinal + ou - antes da variável de folga depende do tipo de desigualdade ≤ ou ≥).
Em geral para ficarmos restritos a variáveis não-negativas o usual é considerar cada variável real como diferença de duas variáveis não negativas (por exemplo x=u-v) nesse caso aumentaríamos o nº de variáveis. No entanto, neste problema em concreto em que temos x ≥ 2 e y ≥ -2 não é preciso aumentar o nº de variáveis, basta fazer a mudança de variáveis x=x'+2 e y=y'-2.
Deste modo o nosso problema fica:
Max Z = 2x + y = 2x' + y' +2
S.a:
4x – 2y -a = 20 ↔ 4x' – 2y' -a = 16
2x + y +b = 10 ↔ 2x' + y' +b = 8
-3x + 3y + c = -3 ↔ -3x' + 3y' + c = 9
-2x – 2y + d = -2 ↔ -2x' – 2y' + d = -2
x + e = 6 ↔ x' + e = 4
y + f = 2 ↔ y' + f = 4
x',y',a,b,c,d,e,f ≥0

Depois use o Simplex para obter uma solução optimal (x',y') que se transformará numa solução optimal (x,y)=(x'+2,y'-2) do problema original.