Método Simplex: Exemplo 1

Maximize z = 3x1+ 2x2

sujeito a

-x1+ 2x2≤ 4
3x1+ 2x2≤ 14
x1– x2≤ 3

x1, x2≥ 0

Solução.

Primeiro, converta todas as restrições de desigualdade na P.L.P. em uma restrição de igualdade, de modo que a
o problema pode ser escrito em uma forma padrão. Isso pode ser feito adicionando uma variável de folga
a cada restrição. Variáveis de folga são sempre adicionadas às restrições do tipo menor que.

Convertendo desigualdades em igualdades

-x1+ 2x2+ x3= 4

3x1+ 2x2+ x4= 14
x1– x2+ x5= 3
x1, x2, x3, x4, x5≥ 0

Onde x3, x4e x5são variáveis de folga.

Uma vez que as variáveis de folga representam recursos não utilizados, sua contribuição na função objetivo é
zero. Incluindo essas variáveis de folga na função objetivo, obtemos

Maximizar z = 3x1+ 2x2+ 0x3+ 0x4 + 0x5

Solução viável básica inicial

Agora assumimos que nada pode ser produzido. Portanto, os valores das variáveis de decisão são
zero.
x1= 0, x2= 0, z = 0

Quando não estamos produzindo nada, obviamente ficamos com capacidade não utilizada.
x3= 4, x4= 14, x5= 3

Observamos que a solução atual possui três variáveis (variáveis de folga x3, x4e x5) com diferente de zero
valores da solução e duas variáveis (variáveis de decisão x1e x2) com valores zero. Variáveis com
valores não nulos são chamados de variáveis básicas. Variáveis com valores zero são chamadas de não-básicas
variables.
Método Simples: Tabela 1

a11= -1, a12= 2, a13= 1, a14 = 0, a15 = 0, b1= 4

a21= 3, a22= 2, a23= 0, a24= 1, a25= 0, b2= 14
a31= 1, a32= -1, a33= 0, a34= 0, a35= 1, b3= 3

Calculando valores para a linha do índice (zj– cj)

z1– c1= (0 X (-1) + 0 X 3 + 0 X 1) - 3 = -3

z2– c2=(0 X 2 + 0 X 2 + 0 X (-1)) - 2 = -2
z3– c3= (0 X 1 + 0 X 0 + 0 X 0) - 0 = 0
z4– c4(0 X 0 + 0 X 1 + 0 X 0) - 0 = 0
z5– c5= (0 X 0 + 0 X 0 + 0 X 1) – 0 = 0

Escolha o menor valor negativo de zj– cj(ou seja, - 3). Assim, coluna sob x1é a coluna chave.
Agora descubra o valor positivo mínimo
Mínimo (14/3, 3/1) = 3
Então linha x5 é a linha chave.
Aqui, o elemento pivô (chave) = 1 (o valor no ponto de interseção).
Portanto, x5parte e x1entra.

Obtivemos os elementos da tabela a seguir usando as seguintes regras:

1. Se os valores de zj– cjsão positivas, a inclusão de qualquer variável básica não aumentará o
valor da função objetivo. Portanto, a solução atual maximiza a função objetivo. Se
há mais de um valor negativo, escolhemos a variável como uma variável básica
correspondente ao qual o valor de zj– cjé o menor (mais negativo) pois isso maximizará o
lucro.
2. Os números na linha de substituição podem ser obtidos dividindo os elementos da linha da chave por
o elemento pivô e os números nas outras duas linhas podem ser calculados usando a fórmula:

Novo número = número antigo - (número correspondente da linha da tecla) X (número correspondente da coluna da tecla)
elemento pivô

Calculando valores para a tabela 2

x3linha

a11= -1 – 1 X ((-1)/1) = 0
a12 = 2 – (-1) X ((-1)/1) = 1
a13 = 1 - 0 X ((-1)/1) = 1
a14= 0 – 0 X ((-1)/1) = 0
a15= 0 – 1 X ((-1)/1) = 1
b1= 4 – 3 X ((-1)/1) = 7

x4 fila

a21= 3 - 1 X (3/1) = 0
a22= 2 – (-1) X (3/1) = 5
a23 = 0 – 0 X (3/1) = 0
a24= 1 – 0 X (3/1) = 1
a25= 0 – 1 X (3/1) = -3
b2= 14 - 3 X (3/1) = 5

x1 linha

a31= 1/1 = 1
a32= -1/1 = -1
a33= 0/1 = 0
a34 = 0/1 = 0
a35= 1/1 = 1
b3= 3/1 = 3

Tabela 2

cj 3 2 0 0 0
Variáveis básicas Valores da solução
cB x1x2x3x4x5
B b (= XB)
0 x3 0 1 1 0 1 7
0 x4 0 5 0 1 -3 5
3 x1 1 -1 0 0 1 3
zj-cj 0 -5 0 0 3
Calculando valores para a linha do índice (zj– cj)

z1- c1(0 X 0 + 0 X 0 + 3 X 1) - 3 = 0
z2– c2=(0 X 1 + 0 X 5 + 3 X (-1)) – 2 = -5
z3- c3= (0 X 1 + 0 X 0 + 3 X 0) - 0 = 0
z4– c4= (0 X 0 + 0 X 1 + 3 X 0) - 0 = 0
z5– c5(0 X 1 + 0 X (-3) + 3 X 1) – 0 = 3

Key column = x2coluna

Mínimo (7/1, 5/5) = 1
Key row = x4linha
Pivot element = 5
x4parte e x2entra.

Calculando valores para a tabela 3

x3fileira

a11= 0 – 0 X (1/5) = 0
a12= 1 - 5 X (1/5) = 0
umtreze= 1 – 0 X (1/5) = 1
um14= 0 – 1 X (1/5) = -1/5
a15= 1 - (-3) X (1/5) = 8/5
b1 = 7 - 5 X (1/5) = 6

x2linha

a21 = 0/5 = 0
a22= 5/5 = 1
a23 = 0/5 = 0
a24= 1/5
a25= -3/5
b2= 5/5 = 1

x1linha

a31= 1 – 0 X (-1/5) = 1
a32= -1 – 5 X (-1/5) = 0
um33= 0 – 0 X (-1/5) = 0
a34= 0 – 1 X (-1/5) = 1/5
a35= 1 – (-3) X (-1/5) = 2/5
b3= 3 – 5 X (-1/5) = 4

Não converta as frações em decimais, porque muitas frações se cancelam durante o processo.
enquanto a conversão em decimais causará complicações desnecessárias.
Método Simplex: Tabela Ótima Final

cj 3 2 0 0 0
Variáveis básicas Valores da solução
cB x1x2x3x4x5
B b (= XB)
0 x3 0 0 1 -1/5 8/5 6
2 x2 0 1 0 1/5 -3/5 1
3 x1 1 0 0 1/5 2/5 4
zj-cj 0 0 0 10

Uma vez que todos os valores de zj – cjestou positivo, esta é a solução ideal.
x1= 4, x2= 1
z = 3 X 4 + 2 X 1 = 14.

Maximization Case: Linear Programming Simplex Method

Exemplo
A Luminous Lamps produz três tipos de lâmpadas - A, B e C. Essas lâmpadas são processadas em
três máquinas - X, Y e Z. A tecnologia completa e as restrições de entrada são dadas em
tabela seguinte.

Máquina
Product Lucro por unidade
X Y Z
A 10 7 2 12
B 2 3 4 3
C 1 2 1 1
Available Time100 77 80

Encontre uma combinação de produtos adequada para maximizar o lucro.

Solução.

O problema de decisão pode ser formulado como

Maximizar z = 12x1+ 3x2+ x3

sujeito a

10x1+ 2x2+ x3≤ 100

7x1+ 3x2+ 2x3≤ 77
2x1+ 4x2+ x3≤ 80
x1, x2, x3≥ 0

Convertendo desigualdades em igualdades

10x1+ 2x2 + x3+ x4= 100

7x1+ 3x2+ 2x3 + x5= 77
2x1+ 4x2+ x3+ x6= 80
x1, x2, x3, x4, x5, x6 ≥ 0

Onde x4, x5e x6são variáveis de folga.

Incluindo essas variáveis de folga na função objetiva, obtemos

Maximize z = 12x1+ 3x2 + x3 + 0x4+ 0x5+ 0x6

Solução básica viável inicial

x1= 0, x2= 0, x3= 0, z = 0

x4= 100, x5 = 77, x6= 80

Tabela 1

Key column = x1coluna.

Mínimo (100/10, 77/7, 80/2) = 10
Key row = x4linha
Elemento pivô = 10
x4parte e x1entra

Agora estamos assumindo que você pode calcular os valores facilmente.

Aquele que quer o fruto deve subir na árvore.

Table 2

cj 12 3 1 0 0 0
Variáveis básicas Valores de solução
cB x1x2x3 x4x5x6
B b (= XB)
12 x1 1 1/5 1/10 1/10 0 0 10
0 x5 0 8/5 13/10 -7/10 1 0 7
0 x6 0 18/5 4/5 -1/5 0 1 60
zj-cj 0 -3/5 1/5 6/5 0 0

Método Simplex: Tabela Final Ótima

cj 12 3 1 0 0 0
Variáveis básicas Valores da solução
cB x1x2x3 x4x5x6
B b (= XB)
12 x1 1 0 -1/16 3/16 -1/8 0 73/8
3 x2 0 1 13/16 -7/16 5/8 0 35/8
0 x6 0 0 -17/8 11/8 -9/4 1 177/4
zj-cj 0 0 11/16 15/16 3/8 0

Uma política ótima é x1=73/8, x2= 35/8, x3= 0.

O valor ótimo associado da função objetivo é z = 12 X (73/8) + 3 X (35/8) + 1 X 0 =

981/8.

Step 2:

Configure a solução inicial.

Escreva os coeficientes de todas as variáveis na DPP dada na forma de tabela, como mostrado em
tabela abaixo para obter uma solução básica viável inicial.

xB= B-1b

A primeira linha da tabela indica o coeficiente cjde variáveis na função objetivo, que permanecem
o mesmo em tabelas sucessivas. Esses valores representam custo ou lucro por unidade da função objetivo de
cada uma das variáveis.

A segunda linha fornece os principais títulos das colunas para a tabela simples. Coluna CBdá
o
coeficientes das variáveis básicas atuais na função objetivo. Coluna xBdá a corrente
valores das variáveis correspondentes na básica.

Número aijrepresentar a taxa na qual o recurso (i- 1, 2- m) é consumido por cada unidade de um
atividade j (j = 1,2 … n).

Os valores zjrepresenta a quantidade pela qual o valor da função objetivo Z seria

diminuído ou aumentado se uma unidade da variável dada for adicionada à nova solução.

Deve-se lembrar que os valores das variáveis não básicas são sempre zero em cada iteração.

Então x1= x2= 0 aqui, coluna xBdá os valores das variáveis básicas na primeira coluna.

Assim 5, = 4, s2= 2, aqui; A solução viável inicial completa pode ser lida imediatamente de
tabela 2 como s1= 4, s2, x, = 0, x2= 0 e o valor da função objetivo é zero.
Passo 3:

Teste de optimalidade:

Agora, prossiga para testar a viabilidade básica para optimalidade pelos regras dadas abaixo. Isso é feito por
calculando a "avaliação líquida" Djpara a variável xjpela fórmula

Teste de Optimalidade:

(i) Se todos Δj≥ 0, a solução em teste será ótima.

(ii) Se pelo menos um Δjse for negativa, a solução em teste não é otimizada, então prossiga para melhorar
a solução na etapa 4.

(iii) Se correspondente ao Δ mais negativojtodos os elementos da coluna Xjsão negativos ou zero (≤

0), então a solução em teste será ilimitada

Aplicando esta regra para testar a optimalidade da solução básica viável inicial, observa-se
que Δ1, e Δ2ambos são negativos. Portanto, prossiga para melhorar esta solução na etapa 4.
Passo 4:

Para melhorar esta solução básica viável, o vetor ou entrar na matriz da base e o
os vetores a serem removidos da matriz base são determinados pelas seguintes regras, tais vetores
geralmente são chamados de "vetor de entrada" e "vetor de saída", respectivamente.

vetor de entrada

O vetor de entrada Xké sempre selecionado correspondente ao valor mais negativo de Δj. (dizer
Δk). Aqui Δk= Mistura (Δ1,Δ2) = Min [ – 3, -2] = – 3 = Δ.

Portanto k = 1 e o vetor coluna x1, deve inserir a matriz base. A coluna x1é marcado por
uma seta para cima (↑).

“Outgoing Vector”:

O vetor de saída βré selecionado correspondente à razão mínima dos elementos de XBpelo
elementos positivos correspondentes do vetor de entrada predeterminado XKEsta regra é chamada de
Regra do Mínimo Proporcional. Em forma matemática, esta regra é escrita como,

Comparando os dois lados desta equação, r = 2, então o vetor B2marcado com seta para baixo (↓)
deve ser removido da matriz base.

Agora a tabela (2) foi modificada para a tabela (3)

Passo 5:

Para trazer B2em vez do vetor de entrada X1 = a unidade deve ocupar o marcado '□'
posição e zero em todos os outros lugares de X1. Se o número na posição marcada ‘□’ for diferente de
unidade, divida todos os elementos dessa linha pelo ‘elemento chave’ (o elemento na interseção de
o mínimo raio da seta (←) e o vetor de entrada seta (↑) é chamado de elemento chave). Então
subtrair os múltiplos apropriados desta nova linha das outras linhas restantes, de modo a obter
zero na posição restante da coluna X1.

Assim, o processo pode ser fortalecido por uma simples transformação de matriz da seguinte forma:

A matriz do coeficiente intermediário é:

Table 4:

Now construct the improved simple table as follows:

Desta tabela, a solução básica viável melhorada é lida como:

x1= 2, x2= 0, s1= 2 , s2 = 0

O valor melhorado de Z = 6

Assim, a solução otimizada é obtida como

xB= 3, x2= 1, max z = 11

Etapa 6:

Agora repita as etapas 3 a 5 conforme necessário até que uma solução ótima seja obtida na tabela
5.

Δk = Maior Δ negativoj = – 5 = Δ2

... k = 2 e Portanto X2deve entrar no vetor (coluna chave) pela razão mínima

Como a razão negativa não é contabilizada, a segunda razão não é considerada.

Como a primeira razão é mínima, remova o primeiro vetor p, formando a matriz base. Portanto, a chave
o elemento é 2.

Desenvolvendo a primeira linha pelos elementos chave 2, a matriz de coeficientes intermediária é obtida
como
Esta solução, conforme lido nesta tabela, é x1= 3, x2= 2, S1, = 0, S2= 0 e Z = 11.

Também usando a fórmula Δj= CBXj– Cjverifique se todos Δj's são não negativos. Daí a otimização.

x1, = 3

x2– 1

Max Z = 11

Caminho Simples para Cálculos Simplesx:

A solução completa com seus diferentes passos computacionais pode ser representada de forma mais conveniente
por uma única tabela (6).
Assim, a solução ótima é obtida como:

X1= 3, x2= 1, max z = 11

Exemplo 2:

Minimizar z=x2- 3x3+ 2x5

Sujeito a 3x2- 23+ 2x5≤ 7

Diagrama esquemático da tabela simplex:
Fluxograma do Método Simplex: