Resolva pelo Simplex:
\begin{array}{rrrrrrrr} \min & -2 x_{1} & -2 x_{2} & +4 x_{3} & +0 x_{4} & +5 x_{5} & +3 x_{6} & \\\ \text { s.a } & 3 x_{1} & +6 x_{2} & +3 x_{3} & +3 x_{4} & +3 x_{5} & +4 x_{6} & \leq 60 \\\ & x_{1}, & x_{2}, & x_{3}, & x_{4}, & x_{5}, & x_{6} & \geq 0 \end{array}

Passo 1

O enunciado dá o problema de programação linear abaixo e pede a solução pelo método Simplex:
  • Função objetivo a ser minimizada:
\min\\ z = -2x_{1} -2x_{2} +4x_{3} +0x_{4} +5x_{5} +3x_{6}
  • Restrição (uma só):
3x_{1} +6x_{2} +3x_{3} +3x_{4} +3x_{5} +4x_{6} \le 60
  • Não negatividade:
x_{1},x_{2},x_{3},x_{4},x_{5},x_{6} \ge 0
O que se pede explicitamente: encontrar os valores de x_{1},x_{2},x_{3},x_{4},x_{5},x_{6} que minimizam z sujeitos à restrição dada, e o valor mínimo z^{*}.

Passo 2

Transformação para usar o Simplex de forma direta (explicação didática curta e concreta):
  • O Simplex é normalmente apresentado para problemas de maximização na forma padrão com igualdades. Para aplicar o Simplex aqui eu faço duas coisas simples:
    1. Introduzo uma variável de folga (slack) x_{7}\ge0 para transformar a desigualdade em igualdade.
    2. Como o problema é de minimização, considero a função auxiliar w = -z. Assim, maximizo w. Isso é válido pois maximizar w é equivalente a minimizar z (pois w=-z).
Aplicando 1: a restrição vira igualdade
3x_{1}+6x_{2}+3x_{3}+3x_{4}+3x_{5}+4x_{6}+x_{7}=60, \qquad x_{7}\ge0.
Aplicando 2: a nova função a maximizar é
w = -z = 2x_{1}+2x_{2}-4x_{3}-0x_{4}-5x_{5}-3x_{6}.

Passo 3

Construção da solução básica inicial (explicação do conceito):
  • Solução básica inicial natural: colocar todas as variáveis de decisão x_{1},\dots,x_{6}=0 e a variável de folga x_{7}=60. Isso satisfaz a restrição e é factível.
  • Valor inicial de w nessa solução: substituir tudo zero em w w=0.
Escrevendo a equação da base (a partir da igualdade) isolando x_{7}:
x_{7} = 60 - 3x_{1} -6x_{2} -3x_{3} -3x_{4} -3x_{5} -4x_{6}.
E a função objetivo (forma de teste de entrada) escrita como
w - 2x_{1} - 2x_{2} +4x_{3} +0x_{4} +5x_{5} +3x_{6} = 0,
ou, em forma direta para leitura de coeficientes, os coeficientes de x_{1},\dots,x_{6} na função w são 2,2,-4,0,-5,-3.

Passo 4

Critério de escolha da variável que entra na base (ensino do conceito de custo reduzido):
  • No Simplex (maximização) escolhe-se como variável que entra aquela com maior coeficiente positivo na função objetivo (maior impacto de aumento em w). Aqui os coeficientes são:
    • c_{1}=2, c_{2}=2, c_{3}=-4, c_{4}=0, c_{5}=-5, c_{6}=-3.
  • Só variáveis com coeficiente positivo podem aumentar w. Temos empate entre x_{1} e x_{2} (ambas com coeficiente 2). Faço um desempate arbitrário e escolho x_{1} para entrar na base (poderia ser x_{2}, mas o procedimento é análogo).

Passo 5

Teste da razão (regra da razão mínima) para decidir quem sai da base:
  • A equação da restrição na forma x_{7} = 60 - 3x_{1} - \cdots mostra que ao aumentar x_{1} a variável básica atual x_{7} diminui com coeficiente 3. Mantendo não negatividade, o máximo que x_{1} pode crescer é dado por
\text{máx } x_{1} = \frac{60}{3} = 20.á
  • Assim, x_{7} atinge zero primeiro e sai da base. Ou seja, x_{1} entra e x_{7} sai.

Passo 6

Pivoteamento (atualizar as equações) — explicação passo a passo das contas:
  • Isolo x_{1} a partir da equação de x_{7}. Da equação
x_{7} = 60 - 3x_{1} -6x_{2} -3x_{3} -3x_{4} -3x_{5} -4x_{6},
despejando x_{1}:
3x_{1} = 60 - x_{7} -6x_{2} -3x_{3} -3x_{4} -3x_{5} -4x_{6},
logo
x_{1} = 20 -\tfrac{1}{3}x_{7} -2x_{2} -1x_{3} -1x_{4} -1x_{5} -\tfrac{4}{3}x_{6}.
  • Como após o pivoteamento x_{7} vira não básica (será 0 na solução básica), podemos anotar a forma prática:
x_{1} = 20 -2x_{2} -1x_{3} -1x_{4} -1x_{5} -\tfrac{4}{3}x_{6} \quad\text{(tomando }x_{7}=0\text{ na solução básica)}.çãá
  • Atualizo também a função objetivo w substituindo x_{1} na expressão original w = 2x_{1}+2x_{2}-4x_{3}-5x_{5}-3x_{6}. Substituindo:
\begin{aligned} w &= 2\Big(20 -\tfrac{1}{3}x_{7} -2x_{2} -x_{3} -x_{4} -x_{5} -\tfrac{4}{3}x_{6}\Big) +2x_{2} -4x_{3} -5x_{5} -3x_{6} \\\ &= 40 -\tfrac{2}{3}x_{7} -4x_{2} -2x_{3} -2x_{4} -2x_{5} -\tfrac{8}{3}x_{6} +2x_{2} -4x_{3} -5x_{5} -3x_{6}. \end{aligned}
Agora junto termos semelhantes:
w = 40 -\tfrac{2}{3}x_{7} -2x_{2} -6x_{3} -2x_{4} -7x_{5} -\tfrac{17}{3}x_{6}.
  • Interpretação prática: na nova tabela as variáveis não básicas x_{2},x_{3},x_{4},x_{5},x_{6},x_{7} aparecem com coeficientes (nosso “custo reduzido”) -2,-6,-2,-7,-\tfrac{17}{3},-\tfrac{2}{3} respectivamente na expressão de w. Esses números dizem quanto w mudaria (com sinal) se aumentássemos a variável não básica correspondente a partir de zero, mantendo as outras não básicas em zero.

Passo 7

Critério de otimalidade e conclusão do Simplex:
  • Para maximização, o critério de otimalidade é: se todos os coeficientes (custos reduzidos) das variáveis não básicas na expressão de w são menores ou iguais a zero, a solução atual é ótima.
  • Aqui, após o pivoteamento, os coeficientes de todas as variáveis não básicas x_{2},x_{3},x_{4},x_{5},x_{6},x_{7} são todos negativos ( -2,-6,-2,-7,-\tfrac{17}{3},-\tfrac{2}{3}). Isso significa que não existe nenhuma variável que, se aumentada, aumentaria w. Logo a solução é ótima para o problema de maximização de w.
  • Como maximizar w é equivalente a minimizar z=-w, essa solução também é ótima para o problema original de minimização.

Passo 8

Leitura da solução ótima e valor objetivo final (como obter valores das variáveis):
  • Da base final temos x_{1}=20 (obtido na equação isolada) e todas as demais variáveis de decisão são zero:
x_{2}=x_{3}=x_{4}=x_{5}=x_{6}=0.
  • A variável de folga ficou x_{7}=0 (como previsto pelo teste da razão).
  • Valor de w ótimo (da expressão encontrada com todas as não básicas zero) é w=40.
  • Portanto o valor mínimo do original z é
z^{*} = -w^{*} = -40.
Breve intuição para fixar: como as variáveis x_{1} e x_{2} tinham coeficientes negativos na função original ( -2 cada) elas “reduzem” mais o valor de z por unidade, mas x_{1} consome menos recurso da restrição (coeficiente 3 em vez de 6 para x_{2}). Então é melhor aplicar toda a capacidade na x_{1}: 3\cdot 20 = 60.

Resposta

x_{1}=20
x_{2}=0
x_{3}=0
x_{4}=0
x_{5}=0
x_{6}=0
Valor mínimo z^{*}=-40

Exercícios relacionados