Questão 1
Uma industria asiática precisa enviar um conjunto de N itens indivisiveis para um cliente europeu. Cada item j tem volume V_{j} e peso W_{j}. Este envio será feito por meio de containers identicos, tendo cada container capacidade de volume V_{\text {max }} e de peso W_{\text {max }}. Para fins de factibilidade, assuma que V_{j} \leq V_{\text {max }} e W_{j} \leq W_{\text {max }} para todo item j. Escreva um problema de programação linear inteira para minimizar o número de containers necessários para realizar este transporte. Lembre-se que todos os itens devem ser enviados e os limites de peso e volume dos containers não podem ser excedidos.

Passo 1

Vou listar claramente o que o enunciado nos deu e o que ele pede (sem ainda resolver nada).
  • Dados fornecidos:
    • Número de itens: N.
    • Para cada item j (com j=1,\dots,N):
      • volume do item: V_{j},
      • peso do item: W_{j}.
    • Capacidade de cada container (idênticos):
      • capacidade de volume: V_{\text{max}},
      • capacidade de peso: W_{\text{max}}.
    • Condição de factibilidade dada: para todo j, V_{j} \le V_{\text{max}}\quad\text{e}\quad W_{j} \le W_{\text{max}}.
  • O que o enunciado pede:
    • Escrever um problema de programação linear inteira que minimize o número de containers necessários para enviar todos os N itens, respeitando que:
      • cada item deve ser enviado (cada item alocado a exatamente um container),
      • para cada container utilizado não sejam excedidos os limites de volume e de peso.

Passo 2

Escolher as variáveis de decisão. A forma clássica e direta é usar:
  • variáveis binárias de alocação: x_{ij}=\begin{cases} 1, & \text{se o item } j \text{ for colocado no container } i,\\[4pt] 0, & \text{caso contrário}, \end{cases}ápara i=1,\dots,M\) e \(j=1,\dots,N\). - variáveis binárias que indicam se o container \(i\) é usado: \[y_i=\begin{cases} 1, & \text{se o container } i \text{ for utilizado},\\[4pt] 0, & \text{se não for utilizado}. \end{cases}
Explicação didática: x_{ij}\] diz exatamente onde cada item fica; \(y_i ativa o container. Para que isso funcione precisamos ligar x_{ij} e y_i nas restrições de capacidade (explico isso adiante).]

Passo 3

Escolher quantos containers potenciais indexar ( M). Uma escolha segura e simples é permitir até um container por item no pior caso, ou seja:
M=N.
Raciocínio: na pior distribuição cada item fica em um container separado, então é suficiente indexar containers i=1,\dots,N. Isso não força usar todos; o modelo minimizará o número efetivamente usados.

Passo 4

Escrever a função objetivo (o que queremos minimizar). Queremos minimizar o número de containers usados, portanto:
\text{minimize}\quad \sum_{i=1}^{N} y_i.
Explicação: cada y_i vale 1 se o container i for aberto/usar-se, então somando temos o total de containers efetivamente utilizados.

Passo 5

Garantir que cada item seja enviado (cada item alocado a exatamente um container). Isso dá as restrições de alocação:
\sum_{i=1}^{N} x_{ij} = 1,\qquad \text{para todo } j=1,\dots,N.
Explicação didática: a soma das escolhas de container para o item j deve ser 1, ou seja o item vai para exatamente um container.

Passo 6

Impor a capacidade de volume de cada container. A técnica padrão usa y_i como “interruptor” (big-M implícito). Para cada container i:
\sum_{j=1}^{N} V_{j}\,x_{ij} \le V_{\text{max}}\,y_i,\qquad \text{para todo } i=1,\dots,N.
Explicação passo a passo:
  • Se y_i=0 (container não usado), o lado direito é zero e a restrição força \sum_j V_j x_{ij}=0, ou seja nenhum item pode ser alocado a esse container (os x_{ij} devem ser 0).
  • Se y_i=1 (container usado), a restrição passa a ser \sum_j V_j x_{ij} \le V_{\text{max}}, que é exatamente a capacidade de volume do container.

Passo 7

Impor a capacidade de peso de cada container, de maneira análoga:
\sum_{j=1}^{N} W_{j}\,x_{ij} \le W_{\text{max}}\,y_i,\qquad \text{para todo } i=1,\dots,N.
Mesma explicação: y_i controla se o container aceita itens; se for usado então a soma dos pesos dos itens alocados não pode ultrapassar W_{\text{max}}.

Passo 8

Definir o domínio das variáveis (integridade binária):
x_{ij}\in\{0,1\},\qquad \text{para todo } i=1,\dots,N,\; j=1,\dots,N,
y_i\in\{0,1\},\qquad \text{para todo } i=1,\dots,N.
Explicação: as variáveis são binárias porque alocação e uso são decisões “sim/não”.

Passo 9

Comentário prático (opcional, útil na prova/implementação): há muita simetria porque os containers são idênticos — permutar índices i produz soluções equivalentes — e isso pode dificultar a busca do solucionador. Uma restrição simples para reduzir simetria é ordenar os y_i:
y_1 \ge y_2 \ge \cdots \ge y_N.
Isto não altera o número mínimo de containers factíveis, mas ajuda algoritmos a evitar permutações redundantes. Use essa restrição só se quiser ajudar o solucionador; ela é opcional.

Passo 10

Resumo final e “cola” do modelo (juntando tudo): a formulação inteira mista (MILP) completa é
\text{minimize}\quad \sum_{i=1}^{N} y_i
sujeito a, para todo j=1,\dots,N,
\sum_{i=1}^{N} x_{ij} = 1,
para todo i=1,\dots,N,
\sum_{j=1}^{N} V_{j}\,x_{ij} \le V_{\text{max}}\,y_i,
\sum_{j=1}^{N} W_{j}\,x_{ij} \le W_{\text{max}}\,y_i,
e
x_{ij}\in\{0,1\}\quad\text{para todo } i,j,\qquad y_i\in\{0,1\}\quad\text{para todo } i.
Se desejar, adicionar a restrição opcional de ordenação dos y_i:
y_1 \ge y_2 \ge \cdots \ge y_N.

Resposta

\text{minimize}\quad \sum_{i=1}^{N} y_i
sujeito a, para todo j=1,\dots,N,
\sum_{i=1}^{N} x_{ij} = 1,
para todo i=1,\dots,N,
\sum_{j=1}^{N} V_{j}\,x_{ij} \le V_{\text{max}}\,y_i,
\sum_{j=1}^{N} W_{j}\,x_{ij} \le W_{\text{max}}\,y_i,
x_{ij}\in\{0,1\}\quad\text{para todo } i=1,\dots,N,\; j=1,\dots,N,
y_i\in\{0,1\}\quad\text{para todo } i=1,\dots,N.

Exercícios relacionados