Exercício 9 - Parte 1

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,00 por saco de frutas. Os fardos com 1 kg ocupam2 \mathrm{dm}^{3} \mathrm{de} espaço. Os sacos de fruta pesam 1 kg e ocupamç3 \mathrm{dm}^{3} de espaço. O carrinho tem capacidade para transportar 12 kg eç10 \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):
Tabela inicial:
\begin{array}{c|cccc|c} \text{Base} & x & y & s_1 & s_2 & \text{RHS}\\hline s_1 & 1 & 1 & 1 & 0 & 12\\\ s_2 & 3 & 2 & 0 & 1 & 10\\hline Z & -35 & -20 & 0 & 0 & 0 \end{array}
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:
    \text{(nova } s_2):\quad x + \tfrac{2}{3}y + 0\cdot s_1 + \tfrac{1}{3}s_2 = \tfrac{10}{3}.
  • Zeramos o elemento de x na linha s_1 subtraindo a nova linha s_2 da linha s_1:
    \text{(nova } s_1) = \text{(antiga } s_1) - 1\cdot\text{(nova } s_2).
    Cálculo:
    \begin{array}{l} s_1: (1,\,1,\,1,\,0,\,12) - (1,\,\tfrac{2}{3},\,0,\,\tfrac{1}{3},\,\tfrac{10}{3})\\[4pt] \quad = \big(0,\;\tfrac{1}{3},\;1,\;-\tfrac{1}{3},\;12-\tfrac{10}{3}\big)\\[4pt] \quad = \big(0,\;\tfrac{1}{3},\;1,\;-\tfrac{1}{3},\;\tfrac{26}{3}\big). \end{array}
  • Atualizamos a linha Z. Como Z tinha coeficiente -35 em x, fazemos:
    \text{(nova } Z) = \text{(antiga } Z) + 35\cdot\text{(nova } s_2).
    Cálculo:
    \begin{array}{l} Z: (-35,\,-20,\,0,\,0,\,0) + 35\cdot(1,\tfrac{2}{3},0,\tfrac{1}{3},\tfrac{10}{3})\\[4pt] \quad = \big(0,\;-\!20 + \tfrac{70}{3},\;0,\;\tfrac{35}{3},\;\tfrac{350}{3}\big)\\[4pt] \quad = \big(0,\;\tfrac{10}{3},\;0,\;\tfrac{35}{3},\;\tfrac{350}{3}\big). \end{array}
  • O tableau após essa iteração fica:
    \begin{array}{c|cccc|c} \text{Base} & x & y & s_1 & s_2 & \text{RHS}\\hline s_1 & 0 & \tfrac{1}{3} & 1 & -\tfrac{1}{3} & \tfrac{26}{3}\\\ x & 1 & \tfrac{2}{3} & 0 & \tfrac{1}{3} & \tfrac{10}{3}\\hline Z & 0 & \tfrac{10}{3} & 0 & \tfrac{35}{3} & \tfrac{350}{3} \end{array}
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 sobra 12 - \tfrac{10}{3} = \tfrac{36-10}{3} = \tfrac{26}{3}\\ \text{kg}de capacidade de massa (ou seja, \tfrac{26}{3} kg livres).
    • Volume utilizado: 3x + 2y = 3\cdot\tfrac{10}{3} + 0 = 10\\ \mathrm{dm}^3.
      • 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).

Exercícios relacionados