Modelagem de problemas com variáveis binárias

Modelagem de problemas com variáveis binárias

Solução Problema 1

a) Variáveis de decisão

ij: percorrer ou não o trajeto que vai de "i" para "j", onde i={A, B, C, D, E, F} e j={B, C, D, E, F, G}

b) Função objetivo

MIN 2 AB + 1 AC + 3 BA + 7 BD + 5 BF + 4 CD + 2 CE + 2 DF + 1 DG + 2 EC + 6 EG + 3 FG

c) Restrições

A) AB + AC = 1

G) DG + FG + EG = 1

B) AB - BA - BD - BF = 0

C) AC + EC - CD - CE = 0

D) BD + CD - DF - DG = 0

E) CE - EC - EG = 0

F) BF + DF - FG = 0

d) Solução do software

!ij: percorrer ou não o trajeto que vai de "i" para "j", onde i={A, B, C, D, E, F} e j={B, C, D, E, F, G}

!Funçao objetivo

!===============

MIN 2 AB + 1 AC + 3 BA + 7 BD + 5 BF + 4 CD + 2 CE + 2 DF + 1 DG + 2 EC + 6 EG + 3 FG

ST

!Restricoes:

!===========

A) AB + AC = 1

G) DG + FG + EG = 1

B) AB - BA - BD - BF = 0

C) AC + EC - CD - CE = 0

D) BD + CD - DF - DG = 0

E) CE - EC - EG = 0

F) BF + DF - FG = 0

END

INT 12

e) Interpretação da solução do software

A solução diz que devemos percorrer as rotas A-C-D-G, totalizando uma distância de 6.

Objective value: 6.000000

Variable Value Reduced Cost

AB 0.000000 2.000000

AC 1.000000 1.000000

BA 0.000000 3.000000

BD 0.000000 7.000000

BF 0.000000 5.000000

CD 1.000000 4.000000

CE 0.000000 2.000000

DF 0.000000 2.000000

DG 1.000000 1.000000

EC 0.000000 2.000000

EG 0.000000 6.000000

FG 0.000000 3.000000

Row Slack or Surplus Dual Price

1 6.000000 -1.000000

A 0.000000 0.000000

G 0.000000 0.000000

B 0.000000 0.000000

C 0.000000 0.000000

D 0.000000 0.000000

E 0.000000 0.000000

F 0.000000 0.000000

Solução Problema 2

a) Variáveis de decisão

Xi: Levar ou não levar o produto i, onde i={A, B, C, D, E, F, G, H, I}

b) Função objetivo

MAX