Pesquisa Operacional - Metodo Simplex

Prévia do material em texto

21 
 
2.3 - Solução pelo algoritmo simplex 
 
Perceba que O processo gráfico tem muitas limitações, a começar pelo fato que só pode ser 
usado para duas variáveis de entrada. Foi necessário o desenvolvimento de método mais 
completo para realizar esses cálculos. Esse método é conhecido como SIMPLEX. 
 
O método simplex, ao contrário do método gráfico, trabalha com equações e não com 
inequações. Deste modo as inequações devem ser transformadas em equações e isso é feito 
com a adição de variáveis. Vamos, portanto determinar as variáveis que podem ser aparecer em 
um problema deste tipo. Utilizaremos as definições estabelecidas por Contador: 
 
Variável de entrada é a variável que deve ser otimizada e surge naturalmente do 
enunciado do problema. No caso do exercício das CPUs, que continuaremos usar como 
exemplo, as variáveis de entrada são o número de CPUs grandes (x1) e o número de 
CPUs pequenas (x2). 
Termo independente é o valor numérico de uma restrição e, por convenção, é colocado 
à direita do sinal da inequação. No nosso exemplo, são as quantidade limitantes 
produzidas para cada componente. 
Variável de folga ou residual, utilizada quando a desigualdade for do tipo ≤, é uma 
variável não negativa, somado ao lado esquerdo da desigualdade, e numericamente igual 
à diferença entre o termo independente e os valores à esquerda da desigualdade. 
Corresponde numa determinada solução à parcela não aproveitada de recursos. No 
nosso exemplo são as eventuais sobras de componentes (gabinetes ou placas) 
Variável de excesso, utilizada quando a desigualdade for do tipo ≥, é uma variável 
negativa, subtraída do lado esquerdo da desigualdade, e numericamente igual à diferença 
entre o valor do termo independente e o valor das variáveis que estão à esquerda da 
desigualdade. No nosso não existirão valores deste tipo, pois é um problema de 
maximização. 
Variável artificial é uma variável adicionada à esquerda em todas as restrições que não 
contenham uma variável de folga, sendo utilizada, portanto nas restrições que são 
originalmente com sinal ≥ ou =. A variável artificial é necessária porque a solução inicial 
do Simplex é obtida igualando a zero todas as variáveis de entrada e todas as de 
excesso, o que corresponde a fazer cada variável de folga e cada variável artificial igual 
ao valor do termo independente da equação da qual a variável em questão aparece. No 
nosso exemplo não existem variáveis deste tipo, visto serem inequações do tipo ≤. 
 
Desta forma, no nosso exemplo as inequações seriam transformadas em equações, da seguinte 
forma: 
 
Inequações: 
 
𝑔𝑎𝑏𝑖𝑛𝑒𝑡𝑒 𝑔𝑟𝑎𝑛𝑑𝑒: 𝑥1 ≤ 6 
𝑔𝑎𝑏𝑖𝑛𝑒𝑡𝑒 𝑝𝑒𝑞𝑢𝑒𝑛𝑜: 𝑥2 ≤ 15 
𝑝𝑙𝑎𝑐𝑎𝑠 𝑚ã𝑒: 3𝑥1 + 𝑥2 ≤ 24 
𝑝𝑙𝑎𝑐𝑎𝑠 𝑑𝑒 𝑣í𝑑𝑒𝑜: 2𝑥1 + 𝑥2 ≤ 20 
 
 
Equações: 
 
𝑔𝑎𝑏𝑖𝑛𝑒𝑡𝑒 𝑔𝑟𝑎𝑛𝑑𝑒: 1𝑥1 + 0𝑥2 + 1𝑥3 + 0𝑥4 + 0𝑥5 + 0𝑥6 = 6 
 
22 
 
𝑔𝑎𝑏𝑖𝑛𝑒𝑡𝑒 𝑝𝑒𝑞𝑢𝑒𝑛𝑜: 0𝑥1 + 1𝑥2 + 0𝑥3 + 1𝑥4 + 0𝑥5 + 0𝑥6 = 15 
𝑝𝑙𝑎𝑐𝑎𝑠 𝑚ã𝑒: 3𝑥1 + 1𝑥2 + 0𝑥3 + 0𝑥4 + 1𝑥5 + 0𝑥6 = 24 
𝑝𝑙𝑎𝑐𝑎𝑠 𝑑𝑒 𝑣𝑖𝑑𝑒𝑜: 2𝑥1 + 1𝑥2 + 0𝑥3 + 0𝑥4 + 0𝑥5 + 1𝑥6 = 20 
 
 
Importante notar que na frente de cada variável colocamos seu coeficiente correspondente, 
mesmo quando não teria necessidade, por ser zero ou um. Fizemos isso, para evidenciar os 
coeficientes que serão utilizados no algoritmo Simplex. 
 
Esse equacionamento tem seis valores desconhecido (as incógnitas x1; x2; x3; x4; x5; x6) e 
apenas quatro equações (as relacionadas acima), logo o sistema de equações é indeterminado, 
tem infinitas soluções viáveis e não apenas uma. Lembre-se que em matemática só 
conseguimos resolver um sistema de equações quando o número delas for igual ao número de 
incógnitas. 
 
Nesse caso, portanto, temos infinitas soluções viáveis (as soluções mostradas na área 
hachurada do gráfico mostrado anteriormente). 
 
A solução ótima será pesquisada atribuindo valores arbitrários a um número de incógnitas igual 
ao número total delas menos o número de equações. No nosso exemplo, atribuiremos valores 
arbitrários a duas incógnitas (resultado da subtração seis incógnitas menos duas equações). 
 
Essa resolução exige conhecimentos matemáticos que de modo geral não são do domínio de 
alunos de graduação de Administração, por conseguinte iremos apresentá-la de forma 
descritiva, utilizando o problema das CPUs como ilustração e apresentando o método passo a 
passo. 
 
1º passo: Estabelecer a planilha do algoritmo: 
 
É uma planilha de diversas linhas e colunas, na qual é reservada uma coluna para cada variável 
e mais quatro colunas de cálculos. Acompanhe a planilha para o nosso exemplo e o significado 
de cada coluna: 
 
A coluna base contém as variáveis que estão sendo consideradas numa determinada 
tentativa. No nosso caso teremos quatro variáveis em cada tentativa. Para as outras duas 
será atribuído o valor zero. 
As seis colunas seguintes são reservadas para cada uma das variáveis envolvidas. No 
nosso caso as duas variáveis de entrada (x1 e x2) e as quatro variáveis residuais (x3; x4; x5 
e x6). 
A antepenúltima coluna é reservada para os termos independentes das equações (no 
nosso exercício as restrições de produção). 
A penúltima coluna é destinada a receber uma divisão entre as variáveis independentes e 
a coluna de trabalho (veremos esta coluna mais a frente, durante a descrição do 
processo) 
A última coluna irá relacionar a variável que entrará e a que sairá na próxima tentativa. 
 
 
23 
 
Existe um conjunto de linhas reservadas para cada tentativa. Uma linha para cada equação e 
uma linha de controle (no caso, denominada lucro, nosso objetivo). 
 
 
 
A planilha mostrada acima está preparada para se atribuir o valor zero para as variáveis x1 e x2. 
É nossa primeira tentativa. Ao igualar as variáveis de entrada a zero automaticamente igualamos 
as variáveis residuais ou de folga ao termo independente. Veja como exemplo a primeira 
equação: 
 
𝑥1 + 𝑥3 = 6 𝑠𝑒 𝑥1 = 0 𝑒𝑛𝑡ã𝑜 𝑥3 = 6 
 
De modo idêntico ocorre com as demais equações e variáveis. 
 
2ª passo: Início do preenchimento da planilha: 
 
Colocamos em cada uma das linhas os coeficientes das equações citadas acima. A tabela fica 
da seguinte forma: 
 
 
 
Na linha de controle colocamos o lucro respectivo com sinal trocado, ou seja -500 para CPU 
grande e – 200 para CPU pequena e zero para as demais colunas: 
 
 
 
 
24 
 
Como dissemos nessa primeira tentativa atribuímos valor zero às variáveis x1 e x2. Na segunda 
tentativa iremos entrar na tabela com uma delas e sair com uma das que fizeram parte na 
primeira tentativa (x3, x4, x5, x6). Isso é feito da seguinte maneira: 
Localizar a coluna que apresentar o maior valor negativo na linha de controle, no nosso 
caso a coluna x1, que apresenta o valor -500. Essa coluna passa a ser denominada 
coluna de trabalho (ela irá variar de tentativa para tentativa). Costuma-se assinalar a 
coluna por um retângulo. Essa variável é a que entrará na próxima tentativa. Colocamos 
essa informação na última coluna. 
Dividir o termo independente pelo valor correspondente na coluna de trabalho. A linha de 
gabinete grande, por exemplo, iremos dividir 6 por 1, obtendo o valor 6 que será colocado 
na penúltima coluna. 
A variável que sairá na tentativa seguinte é aquela que corresponder a linha que 
apresentar menor valor positivo na coluna que acabamos de calcular ou seja, de termo 
independente dividido pela coluna de trabalho, no caso do exemplo o valor 
correspondente à variável x3. 
O coeficiente que estiver no cruzamento da linha que sairá com a coluna de trabalho 
chama-se pivô ou elemento pivotal e vai nos servir para os cálculos seguintes. 
 
Veja como deve ter ficado a planilha: 
 
 
 
3º passo: Determinação da tentativa seguinte: 
 
Para a segunda tentativa iremos substituir na base a linha x3, que deve sair, pela linha x1 que 
deve entrar. Todas as outras linhas, inclusive a de controle devem permanecer com a base 
inalterada. 
 
Os valores da linha que entra são obtidos pela divisão dos valoresda linha que sai pelo valor do 
pivô. Neste caso como o valor do pivô é 1, os valores permanecerão os mesmos. 
 
 
25 
 
 
 
Os valores das demais linhas, inclusive do termo independente, é obtido pela chamada regra do 
retângulo. 
 
Antes de aprendermos a usar a regra do retângulo, notemos que nas colunas que também são 
linhas (no nosso exemplo, no momento, as colunas x1, x4, x5 e x6) irão aparecer apenas números 
zero ou um. Quando uma coluna cruza com uma linha correspondente à mesma variável o valor 
será um. Veja a seguir: 
 
 
 
E quando uma coluna cruza com uma linha correspondente a outra variável o valor será zero. 
Veja novamente: 
 
 
26 
 
 
 
Apenas os valores das colunas referentes às variáveis que estão assumindo valor zero (que 
estão “fora”) e da coluna do termo independente é que deverão ser calculados pela regra do 
retângulo. 
 
Para entendermos a regra do retângulo utilizaremos o quadro abaixo, com as linhas e colunas 
numeradas à semelhança do Excel: 
 
 
 
Queremos calcular o valor da célula D12. Para isso iremos usar o retângulo definido pelo pivô 
(célula C5) e pelo valor correspondente anterior (célula D6). O valor pedido será obtido pela 
formulação: 
 
𝑁𝑜𝑣𝑜 𝑣𝑎𝑙𝑜𝑟 = 𝑉𝑎𝑙𝑜𝑟 𝑎𝑛𝑡𝑒𝑟𝑖𝑜𝑟 − (𝑝𝑟𝑜𝑑𝑢𝑡𝑜𝑠 𝑑𝑜𝑠 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠 𝑑𝑎 𝑑𝑖𝑎𝑔𝑜𝑛𝑎𝑙 𝑜𝑝𝑜𝑠𝑡𝑎) ÷ 𝑝𝑖𝑣𝑜 
 
No nosso exemplo seria: 
 
𝐷12 = 𝐷6 − (𝐶6 × 𝐷5) ÷ 𝐶5 𝑜𝑢 𝑠𝑒𝑗𝑎 1 − (0 × 0) ÷ 1 = 1 
 
27 
 
 
Para fixar esse conceito, façamos agora o cálculo do termo independente correspondente à 
placa mãe. Veja abaixo o quadro: 
 
 
 
Observe em amarelo do reangulo definido valor correspondente ao desejado na base anterior e 
o pivô. O cálculo é feito utilizando-se a formulação vista, ou seja: 
 
𝐼13 = 𝐼7 − (𝐶7 × 𝐼5) ÷ 𝐶5 𝑜𝑢 𝑠𝑒𝑗𝑎 24 − (3 × 6) ÷ 1 = 6 
 
Os demais valores são calculados de modo idêntico, ficando a planilha do seguinte modo: 
 
 
 
Repetimos então os cálculos feitos na tentativa anterior, passo a passo. O resultado será: 
 
 
28 
 
 
 
Podemos partir então para a terceira tentativa, substituindo, primeiro a linha de x5 por x2: 
 
 
Em seguida preenchendo os valores das colunas que não estão zeradas na tentativa: 
 
 
29 
 
 
 
Calculando, então, pela regra do retângulo os valores correspondentes às três colunas 
restantes: 
 
 
 
Por fim, calculando quem entra e quem sai para a próxima tentativa: 
 
30 
 
 
 
 
Essas tentativas serão repetidas sucessivamente e tantas vezes quantas necessárias até que na 
linha de controle todos os números sejam positivos ou nulos. No nosso exemplo só será 
necessária mais uma tentativa: 
 
 
31 
 
 
 
Observe a última coluna da última tentativa. Ela nos oferece a alternativa ótima para esse 
problema de programação linear: