O_MÉTODO_SIMPLEX

Prévia do material em texto

PESQUISA OPERACIONAL I – Prof: SERGIO RICARDO 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 1 
O MÉTODO SIMPLEX 
Forma geral de um problema de programação linear. Como vimos anteriormente, um 
modelo linear possui uma função objetivo linear para obter um resultado ótimo, e várias inequações 
(ou equações) lineares correspondentes às restrições às quais o problema está condicionado. 
Podemos montar um sistema do tipo: 
(MAX) Z = c1x1 + c2x2+ . . .+cnxn sujeito a: 
a11x1 + a12x2+ . . .+a1nxn ≤ b1 
a21x1 + a22x2+. . .+a2nxn ≤ b2 
... 
am1x1 + am2x2+ . . .+amnxn ≤ bm; com xi ≥ 0, onde aij, bi e cj são chamados de 
parâmetros do modelo, a saber: 
cj são os coeficientes da função objetivo 
bi são os constantes do lado direito 
aij são os coeficientes das restrições ou coeficientes tecnológicos 
Um método bastante usado para resolver problemas deste tipo é o método Simplex, que foi 
proposto por George B. Dantzig e aperfeiçoado por outros matemáticos de renome. 
Neste método, uma solução é qualquer conjunto de valores para as variáveis de restrição. 
Por solução praticável, entende-se uma solução que não viole nenhuma das restrições do modelo. 
Solução impraticável é aquela que viola alguma restrição. Já solução básica é aquela em que o 
sistema com as m equações com n incógnitas (n>m) é resolvido fazendo-se n-m variáveis iguais a 
zero e solucionando-se o sistema de m equações restante . 
Assim, se temos o sistema de equações abaixo, onde m=2 e n=5: 
3x1 + 2x2 – x3 + 3x4 + x5 = 12 
 x1 + 4x2 + x3 - 2x4 + 2x5 = 14 
 PESQUISA OPERACIONAL I – Prof: SERGIO RICARDO 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 2 
Podemos fazer x3 = x4 = x5 = 0 e solucionar o sistema restante, obtendo x1 = 2 e x2 = 3. 
Variando-se as variáveis a serem zeradas, obteremos outras soluções básicas. 
A quantidade de soluções básicas é dada pela fórmula 
de combinação simples: 
As variáveis resolvidas pelo sistema de equações são as variáveis básicas. As variáveis 
zeradas são as não básicas. 
O método propõe o conceito de variáveis de folga, que são variáveis a serem introduzidas 
nas inequações para transformá-las em equações. Por exemplo, a inequação 3x1 ≤ 10, seria 
transformada na equação 3x1 + F1 = 10, onde F1 é a variável de folga introduzida. Vamos analisar 
o método com um exemplo: 
Uma industria de tintas possui duas unidades de produção, cada uma produzindo um tipo de 
tinta. A unidade 1 produz tinta a óleo e unidade 2 produz tinta automotiva. As unidades são 
distantes, de forma que não é possível aproveitar a mão de obra de uma unidade na outra. A unidade 
1 conta com uma força de trabalho de 80 homens/hora por dia e a unidade 2 conta com 180 
homens/hora por dia. As quantidades de resinas e pigmentos disponíveis para compra são limitadas, 
devido às cotas impostas pelos monopólios fornecedores. As cotas são de 4900 Kg diários de 
resinas e 4500Kg de pigmentos. Devido ao dimensionamento dos vasilhames utilizados, cada 
mistura de tinta a óleo necessita de 70 kg de resinas e 90 Kg de pigmentos e 2 homens/hora para ser 
produzida. Cada mistura de tinta automotiva requer 70 kg de resinas e 50 kg de pigmentos e 3 
homens/hora. A quantidade de tinta produzida por uma mistura de tinta a óleo oferece um lucro de 
$20 e a de tinta automotiva de $60. Deseja-se programar as quantidades diárias a produzir de forma 
a maximizar o lucro. 
As variáveis de decisão são: 
x1 = quantidade de misturas de tinta a óleo a ser produzida 
x2 = quantidade de misturas de tinta automotiva a ser produzida 
Função que maximiza o lucro: (MAX) Z = 20 x1 + 60 x2 
As restrições são: 
( )!!
!
mnm
n
m
n
−
=





 PESQUISA OPERACIONAL I – Prof: SERGIO RICARDO 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 3 
Quantidade disponível de resina: 70x1 + 70x2 ≤ 4900 
Quantidade disponível de pigmentos: 90x1 + 50x2 ≤ 4500 
Mão de obra na unidade 1: 2x1 ≤ 80 
Mão de obra na unidade 2: 3x2 ≤ 180 
Positividade das quantidades produzidas: x1 ≥ 0 e x2 ≥ 0 
Primeiramente, vamos acrescentar as variáveis de folga: 
70x1 + 70x2 + F1 = 4900 
90x1 + 50x2 + F2 = 4500 
2x1 + F3 = 80 
3x2 + F4 = 180 
Temos, portanto, 4 equações e 6 variáveis (incluindo as de folga), ou seja, 6! / (4! 2!) = 15 
soluções básicas. 
Um método não muito prático é calcular as 15 soluções possíveis: 
# não básicas Variáveis básicas diagnóstico Z 
1 x1 = x2 = 0 F1=4900 F2=4500 F3=80 F4=180 praticável 0 
2 x1 = F1 = 0 x2=70 F2=1000 F3=80 F4=−30 impraticável - 
3 x1 = F2 = 0 x2=90 F3=80 F4=−90 F1=−1400 impraticável - 
4 x1 = F3 = 0 0 = 80 impossível - 
5 x1 = F4 = 0 F3=80 x2=60 F1=700 F2=1500 praticável 3600 
 PESQUISA OPERACIONAL I – Prof: SERGIO RICARDO 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 4 
6 x2 = F1 = 0 F3=−60 F2=−1800 F4=180 x1=70 impraticável - 
7 x2 = F2 = 0 F3=−20 F1=1400 x1=50 F4=180 impraticável - 
8 x2 = F3 = 0 F1=2100 F2=900 x1=40 F4=180 praticável 800 
9 x2 = F4 = 0 0 = 180 impossível - 
10 F1 = F2 = 0 x1=25 x2=45 F3=30 F4=45 praticável 3200 
11 F1 = F3 = 0 x1=40 x2=30 F2=−600 F4=90 impraticável - 
12 F1 = F4 = 0 x1=10 x2=60 F3=60 F2=600 praticável 3800 
13 F2 = F3 = 0 x1=40 x2=18 F1=840 F4=126 praticável 1880 
14 F2 = F4 = 0 x1=16.7 x2=60 F3=46.7 F1=−466.6 impraticável - 
15 F3 = F4 = 0 x1=40 x2=60 F1=−2100 F2=−2100 impraticável - 
 
Podemos observar na solução gráfica ao 
lado, cada uma das 15 soluções básicas. Como o 
modelo é de 2 variáveis de decisão (x1, x2), cada 
solução básica é a intersecção de 2 restrições. 
Podemos inclusive observar que 2 das soluções 
(4 e 9) são a intersecção de 2 paralelas que se 
interceptam no infinito. 
Uma das retas da família de retas 
representadas pela função objetivo (Z = 20 x1 + 
60 x2) está desenhada de forma sublinhada na 
 PESQUISA OPERACIONAL I – Prof: SERGIO RICARDO 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 5 
figura acima. Foi usado Z = 2400, o que resultou na passagem pelos pontos (0,40) e (120,0). A 
solução gráfica nos mostra que o ponto 12 é a solução ótima, o que pode ser confirmado 
observando-se os valores de Z apresentados na tabela anterior para cada solução básica. De uma 
forma geral podemos dizer que: 
Se um modelo de Programação linear possui uma única solução ótima, então ela é uma 
solução básica do sistema de equações lineares formado pelas restrições do modelo acrescidas das 
suas respectivas variáveis de folga. No caso de termos mais de uma solução ótima, teremos sempre 
um número infinito de soluções ótimas pois serão ótimos todos os pontos que unem 2 vértices 
adjacentes, ou seja, os pontos de uma aresta do espaço solução. 
Agora vamos supor que temos um modelo com 50 restrições e 100 variáveis. Teremos então 
este número de soluções: 
 
Claro que é inviável a análise de cada uma dessas soluções. Assim, temos que aplicar um 
outro método. 
Primeiramente vamos definir um conceito: solução básica praticável adjacente é uma 
solução básica praticável que difere de outra por apenas uma variável não básica. Assim, as 
soluções básicas a seguir, provenientes do exemplo anterior, são adjacentes: 
Solução básica praticável 1 Solução básica praticável 8 
Variáveis básicas Variáveis não básicas Variáveis básicas Variáveis não básicas 
F1 = 4900 
F2 = 4500 
F3 = 80 
F4 = 180 
x1 = 0 
x2 = 0 
F1 = 2100 
F2 = 900 
x1 = 40 
F4 = 180 
F3 = 0 
x2 = 0 
A quantidade de variáveis de decisão determina a de soluções básicas adjacentes. No 
exemplo, para duas variáveis de decisão,temos também duas soluções básicas adjacentes para cada 
solução básica. 
O método Simplex se baseia simplesmente no fato, que pode ser provado, de que se uma 
solução básica é melhor que as suas adjacentes, então ela é a solução ótima. 
( )
2910
!50100!50
!100
=
−
 PESQUISA OPERACIONAL I – Prof: SERGIO RICARDO 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 6 
As etapas do método são: 
1. Obter uma solução básica praticável inicial. Esta solução é obtida fazendo-se as 
variáveis de decisão como variáveis não básicas, ou seja, iguais a 0. As variáveis básicas 
serão as variáveis de folga. 
2. Dada uma solução básica testar se ela é melhor que suas adjacentes. Se for, é a 
solução ótima. 
3. Se não for ir para a melhor das soluções básicas adjacentes já encontradas e voltar 
a etapa 2. 
Para o exemplo que estamos trabalhando, teríamos: 
1) Z - 20 x1 - 60 x2 = 0 (função objetivo transformada) 
2) 70x1 + 70x2 + F1 = 4900 
3) 90x1 + 50x2 + F2 = 4500 
4) 2x1 + F3 = 80 
5) 3x2 + F4 = 180 
Esta é a chamada forma padrão, na qual as equações são de igualdade, o lado direito é ≥ 0 e 
os coeficientes de cada variável básica inicial são 1. 
Encontrando a solução inicial 
Como dissemos, a solução básica inicial para o problema será sempre obtida fazendo as 
variáveis de decisão do modelo (no caso x1 e x2) iguais a zero e achando-se o valor das demais. 
Assim, fazendo x1=x2=0 (variáveis não básicas), obtemos: 
F1 = 4900 (2); F2 = 4500 (3); F3 = 80 (4); F4 = 180 (5); e Z = 0 (1) 
Examinando as soluções adjacentes 
As adjacentes à solução inicial são obtidas substituindo-se uma das varáveis não básicas (x1 
ou x2). Caso x1 ou x2 deixem de ser zeradas, passarão a ter valores positivos (consideremos que não 
 PESQUISA OPERACIONAL I – Prof: SERGIO RICARDO 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 7 
são degeneradas, o que explicaremos depois) e passarão a contribuir para aumentar o valor de Z 
(equação 1). Portanto ambas as soluções adjacentes são melhores. A melhor delas deve ser a que 
deixa de zerar a variável que mais contribui para aumentar Z (provavelmente x2, pois possui 
coeficiente 60). Como desejamos ir para a melhore das adjacentes, vamos fazer x2 ≠ 0. 
 Como x2 é a variável que vai entrar para o time de variáveis básicas, chamamo-la de 
entrante. A variável a ser substituída será chamada de sainte. Candidatas a saintes: F1, F2, F3 ou F4. 
Escolhendo a variável sainte 
Isolando as variáveis candidatas a saintes nas equações, temos: 
(2) F1 = 4900 - 70x1 - 70x2 
(3) F2 = 4500 - 90x1 - 50x2 
(4) F3 = 80 - 2x1 
(5) F4 = 180 - 3x2 
Entretanto, como x1 vai permanecer não básica (zerada), temos: 
(2) F1 = 4900 - 70x2 
(3) F2 = 4500 - 50x2 
(4) F3 = 80 
(5) F4 = 180 - 3x2 
Como as variáveis de folga não podem se tornar negativas, o valor de x2 não pode 
ultrapassar 60 (restrição maior vem da equação 5). 
Quando aumentamos x2, a primeira variável a se tornar negativa é F4 e é esta, portanto, a que 
escolheremos como sainte. Na nova solução a ser investigada teremos F1, F2, F3 e x2 como variáveis 
básicas e x1 e F4 como variáveis não básicas. 
Reduzindo a 1 o coeficiente da variável entrante 
O sistema de equações, está da seguinte forma: 
 PESQUISA OPERACIONAL I – Prof: SERGIO RICARDO 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 8 
(1) Z – 20 x1 – 60 x2 = 0 
(2) 70x1 +70x2 + F1 = 4900 
(3) 90x1 + 50x2 + F2 = 4500 
(4) 2x1 + F3 = 80 
(5) 3x2 + F4 = 180 
Para que o sistema de equações esteja na forma normal, precisamos fazer a redução para 1 
do coeficiente da variável básica x2 na equação em que ela for aparecer (ou seja, precisamos 
também eliminá-la das demais equações). Desta forma, na equação 5, em que x2 aparece sozinha, 
podemos dividir por 3 os dois lados e teremos: (5) x2 + F4 / 3 = 60. Agora temos: 
(1) Z – 20 x1 – 60 x2 = 0 
(2) 70x1 + 70x2 + F1 = 4900 
(3) 90x1 + 50x2 + F2 = 4500 
(4) 2x1 + F3 = 80 
(5) x2 + F4 / 3 = 60 
Para eliminar x2 das demais equações podemos usar a propriedade de que um sistema não 
se altera quando somamos à uma equação uma outra multiplicada por uma constante. Assim, 
podemos substituir a equação 1 por: (1)+ (5)*60. Teremos então: 
 (1) Z – 20 x1 + 20 F4 = 3600 
Para eliminar x2 de (2), substituímo-la por (2)+(5)*-70. Assim: 
(2) 70x1 + F1 – F4 70 / 3 = 700 
Para eliminar x2 de (3), substituímo-la por (3)+(5)*-50. Assim: 
(3) 90x1 + F2 – F4 50 / 3 = 1500 
Como não existe x2 em (4), não precisamos eliminá-la. Ficamos: 
 PESQUISA OPERACIONAL I – Prof: SERGIO RICARDO 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 9 
(1) Z – 20 x1 + 20 F4 = 3600 
(2) 70x1 + F1 – F4 70 / 3 = 700 
(3) 90x1 + F2 – F4 50 / 3 = 1500 
(4) 2x1 + F3 = 80 
*(5) x2 + F4 / 3 = 60 
Quando substituímos por zero as variáveis não básicas (x1 e F4): 
(1) Z = 3600 
(2) F1 = 700 
(3) F2 = 1500 
(4) F3 = 80 
(5) x2 = 60 
Onde o valor de cada variável básica já está determinado. 
Escolhendo a variável entrante (agora já no segundo ciclo) 
Observando a equação a otimizar: (1) Z = 3600 + 20 x1 – 20 F4; vemos que se F4 deixar de 
ser zero, Z piora, ao passo que se x1 deixar de ser zero, Z melhora. Logo, escolhemos x1 como 
entrante. 
Reescrevendo as equações, temos: 
(2) F1 = 700 – 70x1 + F4 70 / 3 
(3) F2 = 1500 - 90x1 – F4 50 / 3 
(4) F3 = 80 – 2x1 
(5) x2 = 60 – F4 / 3 
Como F4 vai continuar não básica (zerada), teremos na verdade: 
 PESQUISA OPERACIONAL I – Prof: SERGIO RICARDO 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 10 
(1) Z – 20 x1 + 20 F4 = 3600 
(2) F1 = 700 – 70x1 + F4 70 / 3 (x1 máximo = 10) 
(3) F2 = 1500 – 90x1 + F4 50 / 3 (x1 máximo = 16,67) 
(4) F3 = 80 – 2x1 (x1 máximo = 40) 
(5) x2 = 60 – F4 / 3 (x1 máximo = infinito) 
Logo, F1 é a primeira variável a chegar a zero e será a sainte. 
Neste momento, temos: 
Básicas: F¹, F², F³, x² 
Não básicas: x¹, F4 
Entrante: x¹ e sainte: F¹ 
(1) Z – 20 x1 + 20 F4 = 3600 
(2) 70x1 + F1 – F4 70 / 3 = 700 
(3) 90x1 + F2 – F4 50 / 3 = 1500 
(4) 2x1 + F3 = 80 
(5) x2 + F4 / 3 = 60 
Para que (2), onde aparece a entrante, tenha coeficiente 1 (÷ 70): 
(2) x1 + F1 /70 – F4 / 3 = 10 
Para eliminar x1 de (1), faremos: (1)+(2)*20. Assim: 
(1) Z + F1 20/70 + F4 40/3 = 3800 
Para eliminar x1 de (3), substituímo-la por (3)+(2)*-90. Assim: 
(3) - F1 90/70 + F2 + F4 40/3 = 600 
 PESQUISA OPERACIONAL I – Prof: SERGIO RICARDO 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 11 
Para eliminar x1 de (4), substituímo-la por (4)+(2)*-2. Assim: 
(4) - F1 2/70 + F3 + F4 2/3 = 60 
Como x1 não aparece em (5), ficamos com: 
(1) Z + F1 20/70 + F4 40/3 = 3800 
(2) x1 + F1 /70 – F4 / 3 = 10 
(3) - F1 90/70 + F2 + F4 40/3 = 600 
(4) - F1 2/70 + F3 + F4 2/3 = 60 
(5) x2 + F4 / 3 = 60 
Zerando as variáveis não básicas (F1 e F4), teremos a solução: 
(1) Z = 3800 
(2) x1 = 10 
(3) F2 = 600 
(4) F3 = 60 
(5) x2 = 60 
Pegando a função objetivo: Z = 3800 - F1 20/70 - F4 40/3 
Observa-se que qualquer valor de F1 e F4 maiores que zero, ou seja, torná-las básicas, fará 
com que Z diminua, piorando a solução. Logo, como as soluções adjacentes são piores que esta, ela 
é a solução ótima.