Questão 1
Uma industria asiática precisa enviar um conjunto de
itens indivisiveis para um cliente europeu. Cada item
tem volume
e peso
. Este envio será feito por meio de containers identicos, tendo cada container capacidade de volume
e de peso
. Para fins de factibilidade, assuma que
e
para todo item
. 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:
. - Para cada item
(com ): - volume do item:
, - peso do item:
.
- volume do item:
- Capacidade de cada container (idênticos):
- capacidade de volume:
, - capacidade de peso:
.
- capacidade de volume:
- Condição de factibilidade dada: para todo
,
- Número de itens:
-
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
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.
- Escrever um problema de programação linear inteira que minimize o número de containers necessários para enviar todos os
Passo 2
Escolher as variáveis de decisão. A forma clássica e direta é usar:
- variáveis binárias de alocação:
para
Explicação didática:
ativa o container. Para que isso funcione precisamos ligar
e
nas restrições de capacidade (explico isso adiante).]
Passo 3
Escolher quantos containers potenciais indexar (
). Uma escolha segura e simples é permitir até um container por item no pior caso, ou seja:
Raciocínio: na pior distribuição cada item fica em um container separado, então é suficiente indexar containers
. 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:
Explicação: cada
vale
se o container
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:
Explicação didática: a soma das escolhas de container para o item
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
como “interruptor” (big-M implícito). Para cada container
:
Explicação passo a passo:
- Se
(container não usado), o lado direito é zero e a restrição força , ou seja nenhum item pode ser alocado a esse container (os devem ser 0). - Se
(container usado), a restrição passa a ser , que é exatamente a capacidade de volume do container.
Passo 7
Impor a capacidade de peso de cada container, de maneira análoga:
Mesma explicação:
controla se o container aceita itens; se for usado então a soma dos pesos dos itens alocados não pode ultrapassar
.
Passo 8
Definir o domínio das variáveis (integridade binária):
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
produz soluções equivalentes — e isso pode dificultar a busca do solucionador. Uma restrição simples para reduzir simetria é ordenar os
:
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 é
sujeito a, para todo
,
para todo
,
e
Se desejar, adicionar a restrição opcional de ordenação dos
:
Resposta
sujeito a, para todo
,
para todo
,