Sr. Alfredo necessita definir a quantidade a ser enviada de cada uma das 2 fábricas da PiseBem, principal empresa de calçados do estado. Existem 3 fábricas: TOLEDO com capacidade de produção de 6000 unidades e PONTA GROSSA com capacidade de produção de 2500 unidades, e DOIS VIZINHOS, com capacidade de 5000 unidades e 4 depósitos: Curitiba, com demanda de 6000, Cascavel, com demanda de 4000, Maringá com demanda de 2000 e Campo Mourão com demanda de 1500. Formule este problema como um PPLI de modo a obter o menor custo possível dada a tabela de custo a seguir:
Orig. Dest. Curitiba Cascavel Maringá Campo Mourão
Toledo 7 5 2 3
Ponta Grossa 2 5 4 5
Dois Vizinhos 3 2 7 6

Passo 1

O enunciado pede que formulemos um problema de distribuição (transporte) como um PPLI para obter o menor custo possível. Dados fornecidos:
  • Fábricas (origens) e suas capacidades:
    • Toledo: capacidade 6000
    • Ponta Grossa: capacidade 2500
    • Dois Vizinhos: capacidade 5000
  • Depósitos (destinos) e suas demandas:
    • Curitiba: demanda 6000
    • Cascavel: demanda 4000
    • Maringá: demanda 2000
    • Campo Mourão: demanda 1500
  • Custo unitário de envio (tabela do enunciado; peguei os dados da tabela do enunciado):
\begin{array}{c|cccc} \text{Orig.}\backslash\text{Dest.} & \text{Curitiba} & \text{Cascavel} & \text{Maringá} & \text{Campo Mourão}\\hline \text{Toledo} & 7 & 5 & 2 & 3\\\ \text{Ponta Grossa} & 2 & 5 & 4 & 5\\\ \text{Dois Vizinhos} & 3 & 2 & 7 & 6 \end{array}áã
  • Verificação rápida dos totais (identificação dos dados): soma das capacidades
6000+2500+5000=13500
e soma das demandas
6000+4000+2000+1500=13500.
Portanto o problema está balanceado (oferta total igual à demanda total), o que significa que podemos usar restrições de igualdade para oferta e demanda.

Passo 2

Definir variáveis de decisão (explicando o que cada variável representa): para cada origem i e destino j definimos a variável \,x_{ij}\, como a quantidade (número de unidades) enviada da fábrica i para o depósito j.
Escolha de índices (para ficar claro):
  • i=1 representa Toledo,
  • i=2 representa Ponta Grossa,
  • i=3 representa Dois Vizinhos.
  • j=1 representa Curitiba,
  • j=2 representa Cascavel,
  • j=3 representa Maringá,
  • j=4 representa Campo Mourão.
Interpretação concreta: por exemplo, \,x_{12}\, é o número de pares enviados de Toledo ( i=1) para Cascavel ( j=2).
Como estamos lidando com unidades físicas, as variáveis devem ser não negativas e inteiras. Vou explicitar isso depois nas restrições.

Passo 3

Construir a função objetivo (a aula curta por trás disso): queremos minimizar o custo total. O custo total é a soma, para cada rota origem-destino, do custo unitário multiplicado pela quantidade enviada nessa rota. Assim, se c_{ij} denota o custo unitário da origem i para o destino j, a função objetivo é
\min Z=\sum_{i=1}^{3}\sum_{j=1}^{4} c_{ij}\,x_{ij}.
Agora substituímos os c_{ij} com os valores da tabela (peguei cada valor na tabela do enunciado) e escrevemos explicitamente a soma:
\min Z = 7x_{11}+5x_{12}+2x_{13}+3x_{14} +2x_{21}+5x_{22}+4x_{23}+5x_{24} +3x_{31}+2x_{32}+7x_{33}+6x_{34}.
Explicação: cada termo como 7x_{11} representa o custo de enviar \,x_{11}\, unidades de Toledo para Curitiba a 7 por unidade.

Passo 4

Escrever as restrições de oferta (capacidade das fábricas) e explicar por que são iguais: cada fábrica i não pode enviar mais do que sua capacidade. Como o problema está balanceado e normalmente desejamos usar toda a produção disponível para atender a demanda, usamos igualdade (toda a produção de cada fábrica será enviada). As equações são:
  • Para Toledo ( i=1, capacidade 6000):
x_{11}+x_{12}+x_{13}+x_{14}=6000.
  • Para Ponta Grossa ( i=2, capacidade 2500):
x_{21}+x_{22}+x_{23}+x_{24}=2500.
  • Para Dois Vizinhos ( i=3, capacidade 5000):
x_{31}+x_{32}+x_{33}+x_{34}=5000.
Breve justificativa didática: cada soma representa as parcelas de produção daquela fábrica destinadas a todos os depósitos. Igualamos à capacidade porque total oferta = total demanda; se o modelo estivesse desbalanceado (oferta maior que demanda), usaríamos desigualdades “ \le” e possivelmente uma variável de estoque ou de descarte.

Passo 5

Escrever as restrições de demanda (cada depósito precisa receber exatamente sua demanda) e explicar: cada depósito j deve receber um total de unidades igual à sua demanda. Como o problema está balanceado, usamos igualdade:
  • Para Curitiba ( j=1, demanda 6000):
x_{11}+x_{21}+x_{31}=6000.
  • Para Cascavel ( j=2, demanda 4000):
x_{12}+x_{22}+x_{32}=4000.
  • Para Maringá ( j=3, demanda 2000):
x_{13}+x_{23}+x_{33}=2000.
  • Para Campo Mourão ( j=4, demanda 1500):
x_{14}+x_{24}+x_{34}=1500.
Explicação prática: cada restrição soma as quantidades enviadas a esse depósito, vindas de todas as fábricas; garantir igualdade significa que a demanda será exatamente satisfeita (nem falta nem sobra).

Passo 6

Não negatividade e integridade das variáveis (e por que isso importa): como as variáveis representam quantidades de pares, obrigamos
x_{ij}\ge 0\quad\text{para todo }i=1,2,3\text{ e }j=1,2,3,4.
E, se o professor exige modelo inteiro (PPLI = programação inteira linear), acrescentamos a restrição de integridade:
x_{ij}\in\mathbb{Z}_{\ge 0}\quad\text{para todo }i,j.
Comentário didático curto: na prática, para problemas de transporte com dados inteiros e matriz de coeficientes da forma usual, a solução básica inteira é garantida mesmo relaxando a integridade (isso ocorre por propriedades de unimodularidade), mas se o enunciado pede explicitamente um PPLI, ponha a condição inteira.

Passo 7

Resumo final do modelo (colocando tudo junto — esta é a formulação pedida como PPLI):
Função objetivo:
\min Z = 7x_{11}+5x_{12}+2x_{13}+3x_{14} +2x_{21}+5x_{22}+4x_{23}+5x_{24} +3x_{31}+2x_{32}+7x_{33}+6x_{34}.
Restrições de oferta:
\begin{cases} x_{11}+x_{12}+x_{13}+x_{14}=6000,\\[4pt] x_{21}+x_{22}+x_{23}+x_{24}=2500,\\[4pt] x_{31}+x_{32}+x_{33}+x_{34}=5000. \end{cases}
Restrições de demanda:
\begin{cases} x_{11}+x_{21}+x_{31}=6000,\\[4pt] x_{12}+x_{22}+x_{32}=4000,\\[4pt] x_{13}+x_{23}+x_{33}=2000,\\[4pt] x_{14}+x_{24}+x_{34}=1500. \end{cases}
Condições das variáveis:
x_{ij}\ge 0\quad\text{e}\quad x_{ij}\in\mathbb{Z}_{\ge 0}\quad\text{para todo }i=1,2,3;\;j=1,2,3,4.
Observação final (opcional para a prova): para resolver numericamen­te esse PPLI você pode usar o método do transporte (Simplex de transporte, como início com NW corner, custo mínimo, ou Vogel, e depois otimizar) ou um solver de PL/MILP; como o problema está balanceado, não precisa de variável artificiais extras.]

Resposta

\min Z = 7x_{11}+5x_{12}+2x_{13}+3x_{14} +2x_{21}+5x_{22}+4x_{23}+5x_{24} +3x_{31}+2x_{32}+7x_{33}+6x_{34}
\begin{cases} x_{11}+x_{12}+x_{13}+x_{14}=6000,\\\ x_{21}+x_{22}+x_{23}+x_{24}=2500,\\\ x_{31}+x_{32}+x_{33}+x_{34}=5000,\\[4pt] x_{11}+x_{21}+x_{31}=6000,\\\ x_{12}+x_{22}+x_{32}=4000,\\\ x_{13}+x_{23}+x_{33}=2000,\\\ x_{14}+x_{24}+x_{34}=1500,\\[4pt] x_{ij}\ge 0,\;x_{ij}\in\mathbb{Z}_{\ge 0}\quad\text{para todo }i=1,2,3;\;j=1,2,3,4. \end{cases}]

Exercícios relacionados