AS VARIÁVEIS BINÁRIAS

[pic 1] [pic 2]

Aluna: Glauce Pâmela da Silva Rodrigues

Variáveis binárias

Problema de Roteirização

1. Variáveis De Decisão

ij: percorrer ou não o caminho de “i” a “j”, onde i = {A, B, C, D, E, F, G} e j = {A, B, C, D, E, F, G}, o valor de “ij” pode ser 0 ou 1

AB = caminho de A até B AC = caminho de A até C BA = caminho de B até A BD = caminho de B até D BF = caminho de B até F CD = caminho de C até D CE = caminho de C até E DF = caminho de D até F DG = caminho de D até G EC = caminho de E até C EG = caminho de E até G FG = caminho de F até G

 

 

B) Função Objetivo

 

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

 

C) Restrições

 

AB + AC = 1 AB - BA - BD - BF = 0 AC + EC - CD - CE = 0 BD + CD - DF - DG = 0 CE - EC - EG = 0 BF + DF - FG = 0 DG + EG + FG = 1

 

 

D) Solução:  

 

MIN: 6 unidades de distância. O caminho de menor distância encontrado é o caminho de A até C, C até D e de D até G que percorre 6 unidades de distância.

PROBLEMA 2 – MOCHILA C/ VARIÁVEIS BINÁRIAS

 

A) Variáveis De Decisão

 

Yi: levar ou não o item “i” na mochila, sendo i= {A, B, C, D, E, F, G, H, I} Pode assumir os valores de: Yi = 0 (não levar) ou Yi = 1 (levar)

 

 

B) Função Objetivo

 

MÁX: 10A + 15B + 5C + 8D + 12E + 2F + 4G + 6H + 0I

 

 

C) Restrições

 

A + B + C + D + E + F + G + H + I ≤ 40 D - G ≥ 0  D + I ≤ 1

 

D) Solução

 

MÁX: Satisfação máxima é 22. O grau de satisfação máxima encontrado é 22. Para alcançar este objetivo Alencar deverá comprar os itens C, D, E, F, G, H, sobrando troco de R$ 3.

 

...