Em um determinado instituto de pesquisas, existem 3 computadores (máquinas) disponíveis para realizar 4 simulações diferentes, designadas pelos nomes
S1, S2
etc. Cada máquina
M1, M2
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
1,00 Dadas as informações abaixo, e sabendo-se que cada simulação precisa ser executada exatamente 50 vezes para que seus resu<ados 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 &
que deverão ser executadas por cada máquina, de forma que o tempo (ou custo) total gasto seja minimizado |l|l|l|l|l| hline mu<irow2* & mu<icolumn4|r|Tempo necessário para cada máquina executar cada simulação (minutos) hline & S1 &
& S3 &
& S3 &
\
\hline M1 & 86 & 57 & 50 & 67 \
\hline
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.

Passo 1

Resumindo: temos três máquinas M1,M2,M3 com capacidades máximas de 75, 95 e 60 simulações, respectivamente, e quatro tipos de simulação S1,S2,S3,S4, cada uma com demanda de exatamente 50 execuções. A máquina M2 não pode fazer S4. O custo por minuto de máquina é 1 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
xij = número de vezes que a simulação Sj roda em Mi, úçã
para i=1,2,3, j=1,2,3,4, com x24=0.
O custo unitário cij (minutos por execução) é
c|cccc & S1&S2&S3&S4hline M1&86&57&50&67 M2&68&62&80&infty M3&74&34&19&83
As restrições são
sumj=1^4xij<= si, s=(75,95,60),
sumi=1^3xij=50(forall j), xij>=0 inteiro
Objetivo
minsumi=1^3sumj=1^4cij,xij

Passo 3

Aplicamos o método do custo mínimo, ordenando células (i,j) por cij crescente e alocando o máximo possível até suprir cada demanda ou exaurir oferta:
  1. c33=19 é o menor, e a demanda de S3 é 50: x33=50,capacidade restante M3=60-50=10
  2. Próximo, c32=34. Demanda de S2 é 50: alocamos x32=10,capacidade restante M3=0,demanda S2=50-10=40
  3. M3 esgotou. O próximo menor custo viável para S2 é c12=57. Cap. M1=75, demanda S2=40: x12=40, M1 rem=75-40=35, S2 rem=0
  4. Agora S4 só pode ser feita em M1 ou M3, mas M3 está cheia; então atribuímos a M1 (custo 67): x14=min(50,;35)=35, M1 rem=0, S4 rem=15
  5. Como M1 esgotou, os 15 faltantes de S4 não podem ir a M2. Logo, precisamos liberar 15 vagas em M1 trocando parte de S2 ( c12=57) por S2 em M2 ( c22=62).
    Reduzimos x12 de 40 para 25 e atribuimos a M2: x22=15, M2 usado=15, M1 rem=35-25=10+25,(recuo)=15, então podemos completar S4 em M1: x14=35+15=50, M1 rem=0, S4 rem=0
  6. Restam S1 (50 execuções). Custo mínimo é em M2 ( c21=68), e M2 ainda tem capacidade: x21=50, M2 usado total=15+50=65<=95, S1 rem=0
Todas as demandas ficaram zeradas e as ofertas respeitadas.

Passo 4

Matriz solução xij:
c|cccc|c & S1&S2&S3&S4&Disponívelhline M1&0&25&0&50&75 M2&50&15&0&0&65<=95 M3&0&10&50&0&60hline Demanda&50&50&50&50& í
O custo total é
25cdot57+50cdot67;+;50cdot68+15cdot62;+;10cdot34+50cdot19 =10395 minutos

Resposta

M1 executa 25 de S2 e 50 de S4.
M2 executa 50 de S1 e 15 de S2.
M3 executa 10 de S2 e 50 de S3.

Exercícios relacionados