Método Simplex para Problemas de Programação Linear

Prévia do material em texto

Método Simplex 
 
Um importante método para a resolução de problemas de PL é o Método 
Simplex, criado por George B. Dantzig. O princípio básico do método consiste 
em, partindo de uma solução inicial, buscar a minimização ou a maximização do 
problema a ser resolvido. 
Para que possamos aprender a resolver um problema de PL utilizando o 
método simplex, vamos utilizar o exemplo da indústria de artigos de couro. 
Relembrando os dados do problema, para a fabricação de uma bolsa, a 
indústria utiliza 500 gramas de couro e 1 hora do setor de corte e costura e 
para a fabricação de cada carteira, a indústria utiliza 200 gramas de couro e 1 
hora de corte e costura. Sabemos também que atualmente a indústria tem à 
disposição, por semana, 20 quilos de couro (20.000 gramas) e 44 horas de 
corte e costura. O lucro referente à fabricação e venda de uma bolsa é de R$ 
39,00 e o lucro referente à fabricação e venda de cada carteira é de R$ 17,00. 
A formulação do problema é: 
max L = 39b + 17c 
s.a. 500b + 200c <= 20.000 
 1b + 1c <= 44 
b >= 0, c >= 0 
O primeiro passo é transformarmos as restrições de desigualdade em 
restrições de igualdade. Mas como podemos fazer isso. A resposta é bem 
simples: basta adicionarmos uma variável de folga para cada restrição de <= 
(menor ou igual). A variável de folga indica a quantidade que falta para que a 
igualdade entre os dois membros da inequação seja verificada. Como a folga 
não representa lucro, o coeficiente de cada variável de folga na função objetivo 
é sempre igual a zero. 
 
Logo, acrescentando as variáveis de folga, temos a seguinte formulação. 
max L = 39b + 17c + 0x3 + 0x4 
s.a. 500b + 200c + x3 <= 20.000 
 1b + 1c + x4 <= 44 
b >= 0, c >= 0 
O próximo passo é criarmos uma tabela inicial para que possamos escrever 
os coeficientes da função objetivo e das restrições, bem como os termos 
independentes. Devido às características do método simplex, os coeficientes da 
função objetivo são escritos na tabela com os respectivos sinais invertidos. Para 
facilitar os cálculos que veremos a seguir, é importante colocarmos nomes nas 
linhas da tabela (L0, L1, L2...). 
 
 
As variáveis b e c são chamadas de variáveis não básicas. Toda variável 
não básica tem valor igual a zero. Nesse caso, b=0, c=0 e, consequentemente, 
L=0 (valor que aparece no canto superior esquerdo). Por outro lado, as 
variáveis básicas x3 e x4 têm seus valores apresentados na primeira coluna das 
linhas 1 e 2: x3=20000 e x4=44. Isso significa que todo o recurso disponível 
ainda não foi utilizado. 
Após preenchermos a tabela inicial, precisamos identificar qual variável 
deverá entrar na base e qual deverá sair. A variável que entrará na base é a 
que representa maior lucro. Nesse caso é a variável b cujo coeficiente é igual a 
-39. É importante lembrarmos que o sinal negativo existe apenas pelas 
características do método Simplex. 
Sabendo que b deverá entrar na base, precisamos saber qual das variáveis 
básicas (x3 ou x4) deverá sair da base. A variável que sai da base é aquela cujo 
recurso limita primeiro a produção. Para sabermos qual é o máximo que 
podemos produzir da variável que está entrando na base, basta dividirmos o 
total dos recursos disponíveis pela quantidade utilizada pela variável. No nosso 
exemplo devemos dividir 20000 por 500 e 44 por 1. O menor resultado indica 
qual é a variável que deixará a base. Como o menor resultado ocorreu na 
divisão de 20000 por 500, quem deixará a base é a variável x3. Isso pode ser 
facilmente observado ao olharmos a coluna referente a x3 e identificarmos em 
qual linha o coeficiente é igual a 1. 
O próximo passo é identificar o pivô (intersecção da coluna da variável que 
entra com a linha da variável que sai). 
 
Devemos sempre transformar o pivô em 1. Como o pivô é igual a 500, 
basta dividirmos toda a linha 1 por esse número (500). 
 
O próximo passo agora é zerarmos os demais coeficientes da coluna da 
variável básica. Essa é uma das características da variável básica: pivô igual a 
1 e demais elementos iguais a zero. 
O primeiro passo é zerarmos o coeficiente da linha 0. Para isso devemos 
multiplicar a linha do pivô (linha 1) pelo coeficiente da linha a ser zerada 
(linha 0), mas com o sinal invertido (39). Em seguida, somamos os 
resultados. 
 
O procedimento para zerarmos o coeficiente da linha 2 é análogo. 
Devemos multiplicar a linha 1 por -1 e, em seguida, somarmos com a linha 2. 
 
Os passos realizados até aqui devem ser repetidos até que todos os 
coeficientes da linha 0 sejam positivos ou zero, e nunca negativos. 
Como o coeficiente de c na linha zero é negativo (-1,4), devemos realizar 
mais uma iteração do método Simplex. 
A variável que entra na base é c e a variável que sai da base é x4. O pivô é 
igual a 0,6. 
 
Para transformarmos o pivô em 1, devemos dividir a linha 2 por 0,6. 
 
Em seguida, devemos zerar os demais coeficientes da coluna da variável c. 
 
 
 
Note que não há mais coeficientes negativos na linha 0. Isso significa que 
encontramos a solução ótima do problema. 
A solução ótima consiste em 
b=37,33 
c=6,67 
L=1.569,34