Um pequeno entregador pode transportar madeira ou frutas em seu carrinho de mão, mas cobra R$20,00 para cada fardo de madeira e\mathrm{R} \35,00por saco de frutas. Os fardos com 1 kg ocupam2 \mathrm{dm}^{3} \mathrm{de}espaço. Os sacos de fruta pesam 1 kg e ocupam3 \mathrm{dm}^{3}de espaço. O carrinho tem capacidade para transportar 12 kg e10 \mathrm{dm}^{3}$, e o entregador pode levar quantos sacos e fardos desejar. Formule um problema de programação linear para determinar:
A. Quantos sacos de fruta e quantos fardos de madeira devem ser transportados para que o entregador ganhe o máximo possível.
B. Resolva o problema pelo método simplex tabular e determine qual será o lucro do entregador e como ele deve encher o seu carrinho.
c. O carrinho será totalmente utilizado? Sobrar capacidade de carga ou capacidade de volume?
Passo 1
O enunciado dá as seguintes informações e pede três coisas claras:
Preços cobrados:
fardo de madeira: \mathrm{R}\$\,20{,}00 por fardo;
saco de frutas: \mathrm{R}\$\,35{,}00 por saco.
Peso e volume de cada item:
cada fardo de madeira pesa 1 kg e ocupa 2\\ \mathrm{dm}^3;
cada saco de frutas pesa 1 kg e ocupa 3\\ \mathrm{dm}^3.
Capacidade do carrinho:
capacidade de massa: 12 kg;
capacidade de volume: 10\\ \mathrm{dm}^3.
O entregador pode levar quantos sacos/fardos desejar (variáveis não-negativas).
Perguntas do enunciado que temos que responder:
A. Quantos sacos de fruta e quantos fardos de madeira devem ser transportados para maximizar o ganho?
B. Resolver o problema usando o método simplex tabular e determinar o lucro e como encher o carrinho.
C. O carrinho será totalmente utilizado? Se sobra capacidade, qual (massa ou volume)?
Passo 2
Vamos traduzir as informações para um modelo de programação linear (variáveis, função objetivo e restrições).
Definimos as variáveis:
x = número de sacos de frutas a transportar;
y = número de fardos de madeira a transportar.
Função objetivo (maximizar ganho/receita):
\text{Maximizar } Z = 35x + 20y,
onde Z é o ganho em reais.
Restrições:
limite de massa (cada item pesa 1 kg):x + y \le 12;
limite de volume (cada saco ocupa 3\\ \mathrm{dm}^3, cada fardo 2\\ \mathrm{dm}^3):3x + 2y \le 10;
não-negatividade:x \ge 0,\quad y \ge 0.
Portanto o modelo é:
\begin{cases} \text{Maximizar } Z = 35x + 20y,\\[4pt] x + y \le 12,\\[4pt] 3x + 2y \le 10,\\[4pt] x\ge 0,\; y\ge 0. \end{cases}]
Passo 3
Convertendo para a forma padrão para aplicar simplex (introduzimos variáveis de folga \;s_1,s_2\; para transformar desigualdades em equações):
Equações com folgas:
\begin{array}{rcl} x + y + s_1 &=& 12,\\[4pt] 3x + 2y + s_2 &=& 10, \end{array}
com s_1\ge0 e s_2\ge0. Aqui s_1 é a massa não utilizada e s_2 é o volume não utilizado.
Objetivo em forma de equação (para tableau):
-35x -20y + Z = 0.
Montamos o tableau inicial (as linhas correspondem às equações acima). Colocando as colunas na ordem x,y,s_1,s_2 e o lado direito (RHS):
Explicação rápida do tableau: as variáveis básicas iniciais são s_1=12 e s_2=10; x e y estão com valor 0. A linha Z mostra os coeficientes -c_j usados para decidir qual variável entra na base.]
Passo 4
Relembrando (didático e prático) como o método simplex funciona nesse tableau:
Critério de entrada: para maximizar, procuramos na linha Z o coeficiente mais negativo (pois temos -c_j); a variável associada entra na base.
Teste de razão (para saída): para a coluna escolhida, calculamos \text{RHS} / \text{coef. da coluna} apenas quando o coeficiente da coluna na linha de restrição for positivo; a menor razão determina a variável que sai (garante viabilidade).
Pivot: tornar o pivô igual a 1 e zerar os outros elementos da coluna, atualizando todas as linhas (operações elementares).
Repetir até que todos os coeficientes da linha Z sejam não-negativos (ótimo encontrado).
Agora aplicamos o procedimento passo a passo.
Passo 5
Primeira iteração do simplex:
Na linha [Z) os coeficientes são -35 para x e -20 para y. O mais negativo é -35, então a variável que entra é x.
Coluna de x tem coeficientes 1 (linha s_1) e 3 (linha s_2), ambos positivos. Fazemos o teste de razão:
\frac{\text{RHS}}{\text{coef. de } x} = \begin{cases} \dfrac{12}{1}=12 &\text{(para a linha } s_1),\\[6pt] \dfrac{10}{3} &\text{(para a linha } s_2). \end{cases}
A menor razão é \dfrac{10}{3}\], então a variável que sai da base é \(s_2. O pivô é o elemento 3 (interseção linha s_2, coluna x).
Tornamos o pivô igual a 1 dividindo a linha s_2 por 3. A nova linha s_2 fica:
Observações sobre esta tabela: as variáveis básicas agora são s_1 e x. Os valores correntes são x=\tfrac{10}{3}, s_1=\tfrac{26}{3}, com y=0 e s_2=0.]
Passo 6
Verificação de otimalidade e interpretação:
Na linha Z agora os coeficientes correspondentes a x e y são 0 e \tfrac{10}{3} respectivamente. Para maximização, quando todos os coeficientes na linha Z (ou, na forma -c_j, quando não há coeficientes negativos) forem não-negativos, chegamos ao ótimo. Aqui não há coeficientes negativos restantes, portanto a solução atual é ótima.
Leitura direta da solução ótima a partir do tableau:
x = \tfrac{10}{3},\qquad y = 0.
O valor ótimo do ganho é
Z^\ast = \tfrac{350}{3}\\ \text{(reais)}.
Interpretando em termos do problema: o melhor é carregar apenas sacos de fruta, na quantidade \tfrac{10}{3} (seguindo o modelo contínuo). O carrinho usa todo o volume permitido e sobra capacidade de massa (vamos calcular esses detalhes).
Passo 7
Cálculos finais e resposta à pergunta C (uso das capacidades):
Verificação das restrições com x=\tfrac{10}{3} e y=0:
Massa utilizada: x + y = \tfrac{10}{3} + 0 = \tfrac{10}{3} kg.
Capacidade de massa: 12 kg. Logo sobra12 - \tfrac{10}{3} = \tfrac{36-10}{3} = \tfrac{26}{3}\\ \text{kg}de capacidade de massa (ou seja, \tfrac{26}{3} kg livres).
Capacidade de volume: 10\\ \mathrm{dm}^3. Logo o volume fica totalmente utilizado (sobra 0\\ \mathrm{dm}^3).
Observação prática: o modelo contínuo permite x fracionário. Se na prática x precisa ser inteiro (não é permitido 1/3 de saco), então seria preciso resolver o problema inteiro; isso pode alterar a solução (por exemplo, testar x=3 ou x=4), mas o enunciado pediu programação linear e o método simplex, então a solução contínua acima é a que buscamos aqui.
Resposta
A: x=\dfrac{10}{3} sacos de fruta e y=0 fardos de madeira.
B: Lucro máximo Z^\ast=\dfrac{350}{3}\\ \mathrm{R}\$ (ou \mathrm{R}\$\,116{,}66\ldots). O processo foi resolvido pelo método simplex tabular conforme os pivôs mostrados: primeira entrada x, saída s_2, pivotamento, atingindo a solução ótima x=\tfrac{10}{3},\;y=0.
C: O carrinho não fica totalmente utilizado em massa (sobra \tfrac{26}{3} kg de capacidade), mas o volume fica totalmente utilizado (sobra 0\\ \mathrm{dm}^3).