A Modelagem Matemática

Forma padrão de um modelo de Programação Linear:

• Função objetivo de minimização;
• Termo independente não-negativo ( >= 0 );
• Restrições de igualdade ( = );
• Variáveis não-negativas ( >= 0 ).

Max -2x1 + x2 + 3x3

s.a.: x1 + 2x2 <= -3

x1 + x2 + 5x3 <= 10

x2 + 4x3 = -5

x1, x2, x3 >= 0

Min 2x1 – x2 – 3x3

s.a.: -x1 – 2x2 >= 3

x1 + x2 + 5x3 <= 10

-x2 – 4x3 = 5

X1, x2, x3 >= 0

Min 2x1 – x2 – 3x3

s.a.: -x1 – 2x2 – x4 = 3

x1 + x2 + 5x3 + x5 = 10

-x2 – 4x3 = 5

X1, x2, x3, x4, x5 >= 0

Sistemas lineares

Def.: conjunto de equações lineares para as quais desejamos descobrir uma solução.

Operações elementares que não alteram a solução do sistema linear:

• Multiplicar/dividir equações por uma constante;
• Trocar equações;
• Multiplicar uma equação por uma constante e somar à outra equação.

Eliminação de Gauss

• Identificar o pivô em uma equação. O pivô é o primeiro elemento NÃO-NULO de uma linha;
• Transformar o pivô em 1;
• Zerar os elementos abaixo do pivô.

2x1 + x2 – x3 = 1

3x1 + 2x2 + x3 = 10

x1 + x2 – 2x3 = -3

x1 + x2/2 – x3/2 = 1/2

x2 + 5x3 = 17

x3 = 3

x2 + 15 = 17 🡪 x2 = 17 – 15 = 2

x2 = 2

x1 + 1 – 3/2 = 1/2

x1 = 1/2 – 2/2 + 3/2 = 2/2 = 1

x1 = 1

X1 – 2x2 + 5x3 + 3x4 – 4x5 = 2

2x1 – 5x2 + 7x3 + 7x4 + 3x5 = -7

2x1 – 4x2 + 5x3 + 6x4 + 2x5 = -6

x1 + x4 – 4x5 = 2

x2 – x4 – 5x5 = 5

x3 – 2x5 = 2

x1 = 2 – x4 + 4x5

x2 = 5 + x4 + 5x5

x3 = 2 + 2x5

VARIÁVEIS BÁSICAS: são aquelas que nos dão a identidade – x1, x2 e x3.

VARIÁVEIS NÃO-BÁSICAS: são as demais variáveis – x4 e x5.

X4 = x5 = 0 🡪 x1 = 2, x2 = 5, x3 = 2

(2, 5, 2, 0, 0)

...