Determinar a solução gráfica (espaço de soluções factíveis e a solução ótima) dos seguintes problemas
a) max z=3 x1+4 x2 sujeito a:
2 x1+5 x2 & <= 18 4 x1+4 x2 & <= 12 5 x1+10 x2 & <= 20 x1, x2 & >= 0
b) min z=2 x1+3 x2 sujeito a:
4 x1-x2 & >= 11 4 x1+6 x2 & >= 32 x1, x2 & >= 0
Como você identificaria estas duas situações aplicando o método simplex?

Passo 1

Beleza, vamos encarar esse exercício de otimização juntos! Temos duas situações diferentes de Programação Linear (PL) que queremos resolver usando o método Simplex. No primeiro caso, estamos tentando maximizar uma função objetivo, e no segundo, minimizar. Para resolver isso, vamos precisar entender como configurar nossas equações, transformar as desigualdades em igualdades (se necessário) e aplicar o método Simplex passo a passo. Vamos lá!

Passo 2

Situação a): Queremos maximizar 2x1 + 5x2 & <= 18 4x1 + 4x2 & <= 12 5x1 + 10x2 & <= 20 x1, x2 & >= 0 sujeito às restrições:
Primeiro, vamos transformar as desigualdades em igualdades adicionando variáveis de folga (s1, s2, s3). Isso é necessário para aplicar o método Simplex, que trabalha com equações iguais.

Passo 3

Adicionando as variáveis de folga, temos:
2x1 + 5x2 + s1 &= 18 4x1 + 4x2 + s2 &= 12 5x1 + 10x2 + s3 &= 20 x1, x2, s1, s2, s3 &>= 0
Agora, nossa função objetivo z - 3x1 - 4x2 = 0 precisa ser reescrita para o método Simplex. Subtraímos de ambos os lados para formar a equação:

Passo 4

Vamos montar a Tabela Simplex inicial. As variáveis básicas inicialmente são as variáveis de folga s1, s2 e s3. O objetivo é maximizar z, então queremos aumentar o valor de z tanto quanto possível dentro das restrições.
c|ccccc|c Base & x1 & x2 & s1 & s2 & s3 & Direito hline s1 & 2 & 5 & 1 & 0 & 0 & 18 s2 & 4 & 4 & 0 & 1 & 0 & 12 s3 & 5 & 10 & 0 & 0 & 1 & 20 hline z & -3 & -4 & 0 & 0 & 0 & 0
Os coeficientes negativos na linha de indicam que ainda podemos aumentar o valor de z.

Passo 5

Identificamos a coluna com o coeficiente negativo mais à esquerda, que é 182 = 9, 124 = 3, 205 = 4 com -3. Isso significa que é a variável que vai entrar na base. Agora, precisamos determinar qual linha vai sair da base.
Para isso, usamos a regra da razão mínima: dividimos o termo constante pelo coeficiente positivo correspondente na coluna de .
O menor valor é 3, então a segunda linha (s2) é a que sai da base, e entra.

Passo 6

Realizamos a operação de pivotamento para atualizar a tabela. Dividimos a segunda linha por 4 para tornar o coeficiente de Nova linha de s2: 4x1 + 4x2 + s24 = 124 Rightarrow x1 + x2 + 14s2 = 3 igual a 1.
Agora, eliminamos das outras linhas usando a nova linha de .

Passo 7

Atualizada a tabela Simplex após o pivotamento:
c|ccccc|c Base & x1 & x2 & s1 & s2 & s3 & Direito hline s1 & 0 & 32 & 1 & -12 & 0 & 9 x1 & 1 & 1 & 0 & 14 & 0 & 3 s3 & 0 & 52 & 0 & -54 & 1 & 5 hline z & 0 & -1 & 0 & 34 & 0 & 9
Agora, ainda temos um coeficiente negativo na linha de (-1 em ), então repetimos o processo.

Passo 8

Escolhemos 932 = 6, 31 = 3, 552 = 2 para entrar na base. Aplicamos novamente a regra da razão mínima:
O menor valor é 2, então a terceira linha (s3) sai da base, e entra.

Passo 9

Realizamos o pivotamento na terceira linha:
Atualizamos a tabela eliminando Nova linha de s3: 0x1 + 52x2 - 54s2 + s352 = 552 Rightarrow x2 - 12s2 + 25s3 = 2 das outras linhas.

Passo 10

Tabela Simplex atualizada:
c|ccccc|c Base & x1 & x2 & s1 & s2 & s3 & Direito hline s1 & 0 & 0 & 1 & -12 + 12 times 12 & 0 - 12 times 25 & 9 - 6 x1 & 1 & 0 & 0 & 14 - 1 times 12 & 0 + 12 times 25 & 3 - 3 x2 & 0 & 1 & 0 & -12 times 12 + 25 & 25 & 2 hline z & 0 & 0 & 0 & 34 + 1 times 12 & 0 - 1 times 25 & 9 + 2
Após simplificar, obtemos:
c|ccccc|c Base & x1 & x2 & s1 & s2 & s3 & Direito hline s1 & 0 & 0 & 1 & -14 & -15 & 3 x1 & 1 & 0 & 0 & -14 & 15 & 0 x2 & 0 & 1 & 0 & -14 & 25 & 2 hline z & 0 & 0 & 0 & 54 & -25 & 11
Agora, não há mais coeficientes negativos na linha de , o que significa que atingimos a solução ótima.

Passo 11

Situação b): Agora, queremos minimizar 4x1 - x2 & >= 11 4x1 + 6x2 & >= 32 x1, x2 & >= 0 sujeito às restrições:
Primeiro, precisamos transformar as desigualdades em igualdades adicionando variáveis de excesso (e1, e2) e variáveis de folga (s1, s2) se necessário. Porém, como estamos lidando com desigualdades do tipo “ ”, adicionamos variáveis de excesso.

Passo 12

Adicionando as variáveis de excesso, temos:
4x1 - x2 - e1 &= 11 4x1 + 6x2 - e2 &= 32 x1, x2, e1, e2 &>= 0
Como queremos minimizar z - 2x1 - 3x2 = 0 , podemos ajustar a função objetivo para o método Simplex. Subtraímos de ambos os lados:

Passo 13

Montamos a Tabela Simplex inicial:
c|ccccc|c Base & x1 & x2 & e1 & e2 & s & Direito hline e1 & 4 & -1 & -1 & 0 & 0 & 11 e2 & 4 & 6 & 0 & -1 & 0 & 32 hline z & -2 & -3 & 0 & 0 & 1 & 0
Note que adicionamos uma variável de folga “s” na função objetivo para facilitar o processo.

Passo 14

Identificamos o coeficiente negativo mais à esquerda na linha de 114 = 2.75, 324 = 8 , que é -2 em . Portanto, entra na base. Agora, determinamos qual variável sai usando a regra da razão mínima:
O menor valor é 2.75, então a primeira linha (e1) sai da base.

Passo 15

Realizamos o pivotamento na primeira linha:
Nova linha de e1: 4x1 - x2 - e14 = 114 Rightarrow x1 - 14x2 - 14e1 = 114
Agora, eliminamos das outras linhas usando a nova linha de .

Passo 16

Atualizamos a tabela após o pivotamento:
c|ccccc|c Base & x1 & x2 & e1 & e2 & s & Direito hline x1 & 1 & -14 & -14 & 0 & 0 & 114 e2 & 0 & 7 & 14 & -1 & 0 & 214 hline z & 0 & -52 & 12 & 0 & 1 & 112
Ainda temos um coeficiente negativo na linha de (-5/2 em ), então continuamos.

Passo 17

Escolhemos 114-14 (não aplicável, pois negativo), 2147 = 34 para entrar na base. Aplicamos a regra da razão mínima:
ãá
Apenas a segunda linha �� válida, então sai da base.

Passo 18

Realizamos o pivotamento na segunda linha:
Nova linha de e2: 0x1 + 7x2 + 14e1 - e27 = 214 times 7 Rightarrow x2 + 128e1 - 17e2 = 34
Atualizamos a tabela eliminando das outras linhas.

Passo 19

Tabela Simplex atualizada:
c|ccccc|c Base & x1 & x2 & e1 & e2 & s & Direito hline x1 & 1 & 0 & -14 + 14 times 128 & 17 & 0 & 114 + 34 times 128 x2 & 0 & 1 & 128 & -17 & 0 & 34 hline z & 0 & 0 & 12 + 52 times 128 & 514 & 1 & 112 + 158
Após simplificar, obtemos:
c|ccccc|c Base & x1 & x2 & e1 & e2 & s & Direito hline x1 & 1 & 0 & -14 & 17 & 0 & 3 x2 & 0 & 1 & 128 & -17 & 0 & 34 hline z & 0 & 0 & 914 & 514 & 1 & 598
Agora, não há mais coeficientes negativos na linha de , indicando que alcançamos a solução ótima.

Passo 20

Resumindo, aplicamos o método Simplex em ambas as situações, ajustando as equações e utilizando variáveis de folga ou excesso conforme necessário. Assim, encontramos as soluções ótimas para maximizar e minimizar as respectivas funções objetivo dentro das restrições dadas.

Resposta

Através do método Simplex, determinamos que:
a) A solução ótima é , com .
b) A solução ótima é , com .

Exercícios relacionados