Questão FC236102
Considerando o problema como aplicação de programação linear inteira, e definindo X k (k = 1,2,3...,m) como uma variável binária para o embarque ou não do k-ésimo tonel, qual é a f
Programação Linear
CESGRANRIO · 2014
Uma empresa de transporte de carga foi contratada para transportar tonéis de determinada matéria-prima. O caminhão adequado tem uma capacidade de transportar até T toneladas. Os tonéis têm pesos e valores diferentes de tal forma que o tonel i pesa pi quilos e vale r i reais. A empresa deseja maximizar o valor da carga do caminhão.
Considerando o problema como aplicação de programação linear inteira, e definindo X
k (k = 1,2,3...,m) como uma variável binária para o embarque ou não do k-ésimo tonel, qual é a formulação correta?
-
Max r k.x k , para k = 1,2,3...,m
Sujeito a p k .x k \(\le\) T , para k = 1,2,3...,m
\(X_k\mathbb{E}\){0,1},para K=1,2,3...,m
-
\(Max \sum_{K=0}^{K=m} r_K.X_K\)
\(Sujeito\,a \sum_{K=0}^{K=m} p_K.X_K\)
\(X_K\mathbb{E}\){0,1}, para K=1,2,3...,m
p e r, inteiros
-
\(Max \sum_{K=1}^{K=m} r_K.X_k\)
\(Sujeito\,a \sum_{K=1}^{K=m} p_K.X_K \le T\)
\(X_K={\begin{cases}0,\,se\,o\,K-ésimo\,tonel\,não\,embarca\\1,\,se\,o\,K-ésimo\,tonel\,embarca\end{cases}}\)
p e r, inteiros
-
\(Max \sum_{K=1}^{K=m} p_K.X_k\)
\(Sujeito\,a \sum_{K=1}^{K=m} r_K.X_k=T\)
\(X_K={\begin{cases}0,\,se\,o\,K-ésimo\,tonel\,não\,embarca\\1,\,se\,o\,K-ésimo\,tonel\,embarca\end{cases}}\)
p e r, inteiros.
-
\(Max \sum_{K=1}^{K=m} p_K.r_k\)
\(Sujeito\,a \sum_{K=1}^{K=m} r_K=T\)
\(X_K\mathbb{E}\){0,1}, para K=1,2,3...,m
p e r, inteiros.
Mostrar resposta e comentário
Gabarito
Certo
Comentário do professor
Objetivo: escolher os tonéis que maximizam o valor total embarcado, representado por \( \max \sum_{k=1}^{m} r_k X_k\). Aqui \(r_k\) é o valor do k-ésimo tonel e a soma ponderada por \(X_k\) dá o lucro da carga.
Restrição de capacidade: o caminhão não pode exceder sua capacidade, imposta por \( \sum_{k=1}^{m} p_k X_k \le T\). Assim, a soma dos pesos dos tonéis selecionados deve ficar dentro de \(T\).
Variável binária: \(X_k\) indica decisão de embarcar: \(X_k=1\) se o tonel k entra na carga e \(X_k=0\) caso contrário. Isso garante escolhas discretas (embarcar ou não).
Inteireza e consistência de unidades: exige-se integridade das decisões (\(X_k\in\{0,1\}\)); os parâmetros \(p_k\) e \(T\) devem estar em mesma unidade para validade da restrição.
Portanto, a formulação apresentada é a modelagem inteira correta do problema de seleção (knapsack) visando maximizar valor sob limite de peso.
Conteúdo do catálogo FC Concursos · Atualizado em