O Modulo Simplex

CONCEITOS BÁSICOS - MÉTODO SIMPLEX

PROBLEMA EXEMPLO:

Uma marcenaria produz: MESA e ARMÁRIO

Ambos produtos utilizam dois recursos:

• MADEIRA com disponibilidade igual a 12 m2
• MÃO-DE-OBRA com disponibilidade igual a 8 H.h

1 MESA gasta: 2 m2 de madeira e 2 H.h mão-de-obra

1 ARMÁRIO gasta: 3 m2 de madeira e 1 H.h de mão-de-obra

MARGENS UNITÁRIAS:         Mesa                =  R$ 4

                                Armário        =  R$ 1

OBJETIVO: Calcular quanto produzir de cada produto para maximizar a margem de contribuição total.

MODELO COMPLETO:[pic 1]

Encontrar x1 e x2 de modo a:

MAXIMIZAR         L =  4.x1  +  1.x2

sujeito a:         2.x1  +  3.x2         ≤    12

                                        2.x1  +  1.x2          ≤    8

                        Com                x1   e   x2         ≥   0

SOLUÇÃO

PASSO 1: Introduzir uma variável de folga para cada inequação, eliminando as desigualdades

X₃ - folga de madeira

X₄ - folga de mão-de-obra

MAXIMIZAR         L =         4.x1  +  1.x2  +  0.x3  +  0.x4[pic 2]

sujeito a:                 2.x1  +  3.x2          +  1.x3                        ≤        12[pic 3]

                        2.x1  +  1.x2         +               1.x4         ≤         8

com  x1  ,  x2 ,  x3  e  x4    ≥  0[pic 4]

---

PASSO 2: Montar a Matriz de Coeficientes, incluindo a função-objetivo na última linha com os sinais trocados e valor do termo independente igual a zero[pic 5]

BASE                X1        X2        X3        X4        b

X3                2        3        1        0        12

X4                2        1        0        1        8

L                -4        -1        0        0        0

PASSO 3: Criação da solução básica inicial, geralmente atribuindo valor 0 às variáveis originais.

Para:                X1  e  X2 = 0  (variáveis originais ou não básicas)

X3  =  12[pic 6]

X4  =  8                variáveis básicas (valores positivos encontrados)

L    =   0[pic 7]

PASSO 4: Variável que entra na base é aquela que tem o maior valor negativo na linha da função-objetivo transformada[pic 8][pic 9]

BASE                X1        X2        X3        X4        b

X3                2        3        1        0        12        ÷   2    =  6

X4                2        1        0        1        8        ÷   2    =  4

L                -4        -1        0        0        0[pic 10]

PASSO 5: Variável que sai da base:[pic 11]

        A) Dividir os termos independentes pelos respectivos coeficientes positivos da variável que entra.

        B) O menor quociente indica, pela equação onde ocorreu, a variável que deve sair da base.

*Devemos achar o vetor identidade para cada variável da coluna X1, com o elemento 1 na segunda linha. A posição do elemento 01 no vetor identidade é encontrada através da interseção entre a coluna X1 e a linha X1.

Ex. de vetor identidade:        

---

PASSO 6: A matriz deve ser transformada através das operações abaixo, encontrando-se a nova base:

Operação 1: Na linha da variável que entrou, divida toda esta linha pelo valor de seu primeiro número para que o resultado deste fique igual a 1

BASE	X1	X2	X3	X4	b		BASE	X1	X2	X3	X4	b
X3	2	3	1	0	12		X3	2	3	1	0	12
X1	2	1	0	1	8	÷ (2)	X1	1	1/2	0	1/2	4
L	-4	-1	0	0	0		L	-4	-1	0	0	0

Operação 2: Multiplicar cada um dos elementos da linha nova que entrou pelo valor negativo do primeiro número da linha da variável que restou e somar o resultado ao elemento correspondente da linha que restou, substituindo os  valores antigos pelos novos. Fazer isso para cada uma das linhas das variáveis restantes