Pesquisa Operacional II
Aula 39
Módulo 5.2 – Programação Produção:Modelo by A.A.
i
j
xij
Variáveis de Decisão
Xij = 1 se o caixeiro vai do nó i para o nó j.
xi j
Origem
(Cidade i)
Destino
(Cidade j)
Programação: Uma máquina
i
j
xij
Variáveis de Decisão
Xij = 1 se a máquina processa a tarefa i e depois a tarefa j.
xi j
Origem
(Tarefa i)
Destino
(Tarefa j)
Programação: Uma máquina
S.a.:
MODELO COM RESTRIÇÕES APENAS
Min
???
Tarefa fictícia 0 antes da primeira tarefa e após a última tarefa. Cada tarefa tem uma única sucessora e predecessora.
Programação: Modelo
S.a.:
MODELO COM RESTRIÇÕES APENAS
Min
???
Se xij = 1, então, Cj ≥ Ci + pj, ou seja, o instante de término da tarefa j só pode ser depois do instante de término da tarefa i. Se xij = 0, então, Cj – Ci ≥ - M (M – valor grande), e a restrição está desativada !
Programação: Modelo
Exemplo numérico
Tarefa | Tempo (min) |
1 | 3 |
2 | 6 |
3 | 4 |
Solução | 1 | 2 | 3 |
Xij | X01=1 | X12=1 | X23=1 |
Solução | 1 | 3 | 2 |
Xij | X01=1 | X13=1 | X32=1 |
Solução | 2 | 1 | 3 |
Xij | X02=1 | X21=1 | X13=1 |
Solução | 2 | 3 | 1 |
Xij | X02=1 | X23=1 | X31=1 |
Solução | 3 | 1 | 2 |
Xij | X03=1 | X31=1 | X12=1 |
Solução | 3 | 2 | 1 |
Xij | X03=1 | X32=1 | X21=1 |
Exemplo numérico
Tarefa | Tempo (min) |
1 | 3 |
2 | 6 |
3 | 4 |
Solução | 1 | 2 | 3 |
Xij | X01=1 | X12=1 | X23=1 |
I = 0 e J = 1
C0 = 0
I = 0 e J = 2
C0 = 0
Exemplo numérico
Tarefa | Tempo (min) |
1 | 3 |
2 | 6 |
3 | 4 |
Solução | 1 | 2 | 3 |
Xij | X01=1 | X12=1 | X23=1 |
I = 1 e J = 2
I = 1 e J = 3
Exemplo numérico
Tarefa | Tempo (min) |
1 | 3 |
2 | 6 |
3 | 4 |
Solução | 1 | 2 | 3 |
Xij | X01=1 | X12=1 | X23=1 |
I = 2 e J = 3
I = 2 e J = 1
Exemplo numérico
Tarefa | Tempo (min) |
1 | 3 |
2 | 6 |
3 | 4 |
Solução | 1 | 2 | 3 |
Xij | X01=1 | X12=1 | X23=1 |
C0
C1
C2
C3
p1
p2
p3
S.a.:
MODELO COM RESTRIÇÕES APENAS
Min
???
Se xij = 1, então, Cj ≥ Ci + pj, ou seja, o instante de término da tarefa j só pode ser depois do instante de término da tarefa i. Se xij = 0, então, Cj – Ci ≥ - M (M – valor grande), e a restrição está desativada !
Programação: Modelo
S.a.:
MODELO MINIMIZA FLUXO TOTAL
Min
Soma dos tempos de término das tarefas
Programação: Modelo
Pesquisa Operacional II
Aula 39
Módulo 5.2 – Programação Produção:Modelo by A.A.