Em um determinado instituto de pesquisas, existem 3 computadores (máquinas) disponíveis para realizar 4 simulações diferentes, designadas pelos nomes
etc. Cada máquina
etc., devido aos recursos disponíveis de processador, memória e disco, pode ser mais ou menos adequada que as outras para completar uma determinada simulação. Por razões técnicas, a máquina 2 não pode realizar a simulação 4 (ou seja, não existirá a variável
x 24
no modelo de PL). Estima-se que o custo de cada minuto de operação das máquinas seja de
$ 1,00
. Dadas as informações abaixo, e sabendo-se que cada simulação precisa ser executada exatamente 50 vezes para que seus resultados sejam confiáveis, deseja-se saber o número de simulações
que deverão ser executadas por cada máquina, de forma que o tempo (ou custo) total gasto seja minimizado.
\begin{tabular}{|l|l|l|l|l|}
\hline \multirow{2}{*}{
} & \multicolumn{4}{|r|}{Tempo necessário para cada máquina executar cada simulação (minutos)} \
\hline & S1 &
& S3 &
\
\hline M1 & 86 & 57 & 50 & 67 \
\hline
& 68 & 62 & 80 & - \
\hline M3 & 74 & 34 & 19 & 83 \
\hline \multirow{5}{*}{
} & Máquin & \multicolumn{3}{|l|}{Número máximo de} \
\hline & a & \multicolumn{3}{|l|}{simulações permitido} \
\hline & M1 & \multicolumn{3}{|c|}{75} \
\hline & M2 & \multicolumn{3}{|c|}{95} \
\hline & M3 & \multicolumn{3}{|c|}{60} \
\hline
\end{tabular}
Dica: esse problema é inspirado no Problema 14 no documento Problemas de Modelagem no Moodle. Mas, apesar da semelhança do enunciado com o Problema 14, ele deve ser modelado como se fosse um Problema de Transporte, da mesma forma como o Problema 3 desse mesmo documento.
\hline \multirow{2}{*}{
\hline & S1 &
\hline M1 & 86 & 57 & 50 & 67 \
\hline
\hline M3 & 74 & 34 & 19 & 83 \
\hline \multirow{5}{*}{
\hline & a & \multicolumn{3}{|l|}{simulações permitido} \
\hline & M1 & \multicolumn{3}{|c|}{75} \
\hline & M2 & \multicolumn{3}{|c|}{95} \
\hline & M3 & \multicolumn{3}{|c|}{60} \
\hline
\end{tabular}
Passo 1
Resumindo: temos três máquinas
com capacidades máximas de 75, 95 e 60 simulações, respectivamente, e quatro tipos de simulação
, cada uma com demanda de exatamente 50 execuções. A máquina
não pode fazer
. O custo por minuto de máquina é
e os tempos (minutos) necessários são dados pela tabela abaixo. Queremos distribuir as 200 execuções de modo a minimizar o tempo total gasto—ou seja, é um Problema de Transporte clássico.
Passo 2
Definimos as variáveis
para
,
, com
.
O custo unitário (minutos por execução) é
O custo unitário
As restrições são
Objetivo
Passo 3
Aplicamos o método do custo mínimo, ordenando células
por
crescente e alocando o máximo possível até suprir cada demanda ou exaurir oferta:
-
é o menor, e a demanda de é 50: - Próximo,
. Demanda de é 50: alocamos -
esgotou. O próximo menor custo viável para é . Cap. , demanda : - Agora
só pode ser feita em ou , mas está cheia; então atribuímos a (custo 67): - Como
esgotou, os 15 faltantes de não podem ir a . Logo, precisamos liberar 15 vagas em trocando parte de ( ) por em ( ).
Reduzimosde 40 para 25 e atribuimos a : então podemos completar em : - Restam
(50 execuções). Custo mínimo é em ( ), e ainda tem capacidade:
Todas as demandas ficaram zeradas e as ofertas respeitadas.
Passo 4
Matriz solução
:
O custo total é
Resposta
M1 executa 25 de
e 50 de
.
M2 executa 50 de e 15 de
.
M3 executa 10 de e 50 de
.
M2 executa 50 de
M3 executa 10 de