Baixe o app para aproveitar ainda mais
Prévia do material em texto
Introduc¸a˜o a` Programac¸a˜o Linear Inteira Mista Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG Departamento de Engenharia de Produc¸a˜o EE UFMG carlos@dep.ufmg.br 28 de junho de 2011 Programac¸a˜o Inteira Introduc¸a˜o Definic¸a˜o Te´cnica branch-and-baund Algoritmo branch-and-baund Programac¸a˜o Linear Bina´ria Definic¸a˜o Algoritmo branch-and-bound para PLIB - Balas [1] Programac¸a˜o Linear Inteira Mista Definic¸a˜o Algoritmo branch-and-bound para PLIM Bibliografia Um problema inteiro O problema de sequ¨enciamento em uma ma´quina 1|ri , d˜i |Cmax Job J1 J2 J3 J4 ri 4 1 1 0 pi 2 1 2 2 d˜i 7 5 6 4 Uma a´rvore branch-and-baund +r1 1p(T1 /)1v v 21 +r1 p1 ( 1 T T2 r , /) max{ +p22}, � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� raiz )/(T p+r2 2 2 )/ p(T +rn n n. . .v v2 n 1v 1v3 n . . . , }+p )/, r TT( 1 1p1 max{ +r , }+p )/, max{ r T( 1 T 1p1 +r 3 3 3 n n n Um problema inteiro O problema de sequ¨enciamento em uma ma´quina 1|ri , d˜i |Cmax Job J1 J2 J3 J4 ri 4 1 1 0 pi 2 1 2 2 d˜i 7 5 6 4 Uma a´rvore branch-and-baund +r1 1p(T1 /)1v v 21 +r1 p1 ( 1 T T2 r , /) max{ +p22}, � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��������������� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� �������������������� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� raiz )/(T p+r2 2 2 )/ p(T +rn n n. . .v v2 n 1v 1v3 n . . . , }+p )/, r TT( 1 1p1 max{ +r , }+p )/, max{ r T( 1 T 1p1 +r 3 3 3 n n n Definic¸a˜o Programac¸a˜o Linear Inteira minimizar z = n∑ j=1 cjxj sujeito a` n∑ j=1 aijxj ≥ bi ∀i = 1, . . . , n xi ∈ IN ∀j = 1, . . . , n. Caracter´ısticas do problema I a func¸a˜o objetivo e´ linear; I todas as restric¸o˜es sa˜o lineares; I todas as varia´veis sa˜o inteiras (∈ IN). Definic¸a˜o Programac¸a˜o Linear Inteira minimizar z = n∑ j=1 cjxj sujeito a` n∑ j=1 aijxj ≥ bi ∀i = 1, . . . , n xi ∈ IN ∀j = 1, . . . , n. Caracter´ısticas do problema I a func¸a˜o objetivo e´ linear; I todas as restric¸o˜es sa˜o lineares; I todas as varia´veis sa˜o inteiras (∈ IN). Definic¸a˜o Programac¸a˜o Linear Inteira minimizar z = n∑ j=1 cjxj sujeito a` n∑ j=1 aijxj ≥ bi ∀i = 1, . . . , n xi ∈ IN ∀j = 1, . . . , n. Caracter´ısticas do problema I a func¸a˜o objetivo e´ linear; I todas as restric¸o˜es sa˜o lineares; I todas as varia´veis sa˜o inteiras (∈ IN). Definic¸a˜o Programac¸a˜o Linear Inteira minimizar z = n∑ j=1 cjxj sujeito a` n∑ j=1 aijxj ≥ bi ∀i = 1, . . . , n xi ∈ IN ∀j = 1, . . . , n. Caracter´ısticas do problema I a func¸a˜o objetivo e´ linear; I todas as restric¸o˜es sa˜o lineares; I todas as varia´veis sa˜o inteiras (∈ IN). Definic¸a˜o Programac¸a˜o Linear Inteira minimizar z = n∑ j=1 cjxj sujeito a` n∑ j=1 aijxj ≥ bi ∀i = 1, . . . , n xi ∈ IN ∀j = 1, . . . , n. Caracter´ısticas do problema I a func¸a˜o objetivo e´ linear; I todas as restric¸o˜es sa˜o lineares; I todasas varia´veis sa˜o inteiras (∈ IN). Dificuldades no arredondamento - 1 a viabilidade na˜o e´ mantida maximizar z = x1 + 2x2 sujeito a` −x1 + x2 ≤ 2, 5 x1 + x2 ≤ 3, 5 x1 ∈ IN x2 ∈ IN I o´timo cont´ınuo: x1 = 0, 5; x2 = 3 e z = 6, 5 I o´timo inteiro: x1 = 1; x2 = 2 e z = 5 Dificuldades no arredondamento - 1 a viabilidade na˜o e´ mantida maximizar z = x1 + 2x2 sujeito a` −x1 + x2 ≤ 2, 5 x1 + x2 ≤ 3, 5 x1 ∈ IN x2 ∈ IN I o´timo cont´ınuo: x1 = 0, 5; x2 = 3 e z = 6, 5 I o´timo inteiro: x1 = 1; x2 = 2 e z = 5 Dificuldades no arredondamento - 2 o´timo inteiro longe do o´timo arredondado maximizar z = x1 + 5x2 sujeito a` x1 + 10x2 ≤ 20 x1 ≤ 2 x1 ∈ IN x2 ∈ IN I o´timo cont´ınuo: x1 = 2; x2 = 9/5 e z = 11 I o´timo inteiro: x1 = 0; x2 = 2 e z = 10 Dificuldades no arredondamento - 2 o´timo inteiro longe do o´timo arredondado maximizar z = x1 + 5x2 sujeito a` x1 + 10x2 ≤ 20 x1 ≤ 2 x1 ∈ IN x2 ∈ IN I o´timo cont´ınuo: x1 = 2; x2 = 9/5 e z = 11 I o´timo inteiro: x1 = 0; x2 = 2 e z = 10 Construc¸a˜o de uma a´rvore de pesquisa Caracter´ısticas dos ve´rtices da a´rvore I ve´rtice aberto I ve´rtice fechado I limite superior (LSk) I limite inferior (LIk) I Subconjunto de soluc¸o˜es (Sk) Construc¸a˜o do algoritmo I LA: lista de ve´rtices aberto I LF : lista de ve´rtices fechado I LS : limite superior do problema I LI : limite inferior do problema Construc¸a˜o de uma a´rvore de pesquisa Caracter´ısticas dos ve´rtices da a´rvore I ve´rtice aberto I ve´rtice fechado I limite superior (LSk) I limite inferior (LIk) I Subconjunto de soluc¸o˜es (Sk) Construc¸a˜o do algoritmo I LA: lista de ve´rtices aberto I LF : lista de ve´rtices fechado I LS : limite superior do problema I LI : limite inferior do problema Inicializac¸a˜o Fac¸a: 1. LA = {0}: colocar o ve´rice 0 na lista aberto; 2. LF = ∅: lista fechado e´ vazia; 3. LS = LS0 =∞; LI0 = 0; 4. LI = 0 ou calculado pelas caracter´ısticas do problema; 5. S0 = conjunto de todo o universo de valores para as varia´veis. Isto inclui as soluc¸o˜es na˜o via´veis do problema; 6. s = ∅ melhor soluc¸a˜o encontrada; Inicializac¸a˜o Fac¸a: 1. LA = {0}: colocar o ve´rice 0 na lista aberto; 2. LF = ∅: lista fechado e´ vazia; 3. LS = LS0 =∞; LI0 = 0; 4. LI = 0 ou calculado pelas caracter´ısticas do problema; 5. S0 = conjunto de todo o universo de valores para as varia´veis. Isto inclui as soluc¸o˜es na˜o via´veis do problema; 6. s = ∅ melhor soluc¸a˜o encontrada; Inicializac¸a˜o Fac¸a: 1. LA = {0}: colocar o ve´rice 0 na lista aberto; 2. LF = ∅: lista fechado e´ vazia; 3. LS = LS0 =∞; LI0 = 0; 4. LI = 0 ou calculado pelas caracter´ısticas do problema; 5. S0 = conjunto de todo o universo de valores para as varia´veis. Isto inclui as soluc¸o˜es na˜o via´veis do problema; 6. s = ∅ melhor soluc¸a˜o encontrada; Inicializac¸a˜o Fac¸a: 1. LA = {0}: colocar o ve´rice 0 na lista aberto; 2. LF = ∅: lista fechado e´ vazia; 3. LS = LS0 =∞; LI0 = 0; 4. LI = 0 ou calculado pelas caracter´ısticas do problema; 5. S0 = conjunto de todo o universo de valores para as varia´veis. Isto inclui as soluc¸o˜es na˜o via´veis do problema; 6. s = ∅ melhor soluc¸a˜o encontrada; Inicializac¸a˜o Fac¸a: 1. LA = {0}: colocar o ve´rice 0 na lista aberto; 2. LF = ∅: lista fechado e´ vazia; 3. LS = LS0 =∞; LI0 = 0; 4. LI = 0 ou calculado pelas caracter´ısticas do problema; 5. S0 = conjunto de todo o universo de valores para as varia´veis. Isto inclui as soluc¸o˜es na˜o via´veis do problema; 6. s = ∅ melhor soluc¸a˜o encontrada; Inicializac¸a˜o Fac¸a: 1. LA = {0}: colocar o ve´rice 0 na lista aberto; 2. LF = ∅: lista fechado e´ vazia; 3. LS = LS0 =∞; LI0 = 0; 4. LI = 0 ou calculado pelas caracter´ısticas do problema; 5. S0 = conjunto de todo o universo de valores para as varia´veis. Isto inclui as soluc¸o˜es na˜o via´veis do problema; 6. s = ∅ melhor soluc¸a˜o encontrada; Regra de parada teste I se LI ≥ LS ou LA = ∅: PARE I se s = ∅: o problema na˜o tem soluc¸a˜o; I sena˜o: s e´ a soluc¸a˜o o´tima; I sena˜o: va´ para iterac¸a˜o; Regra de parada teste I se LI ≥ LS ou LA = ∅: PARE I se s = ∅: o problema na˜o tem soluc¸a˜o; I sena˜o: s e´ a soluc¸a˜o o´tima; I sena˜o: va´ para iterac¸a˜o; Iterac¸a˜o - primeira parte branch Na lista aberto LA, selecione um ve´rtice k (por exemplo, o ve´ritice de menor limite inferior LIk , neste caso, fac¸a LI = max{LI , LIk}); 1. retire o ve´rtice k de LA e coloque-o em LF ; 2. utilizando uma regra apropriada, subdivida o subconjunto Sk de soluc¸o˜es representadas pelo ve´rtice k em novos subconjuntos Sk ′ gerando assim os novos ve´rtices k ′ para a a´rvore de pesquisa; Iterac¸a˜o - primeira parte branch Na lista aberto LA, selecione um ve´rtice k (por exemplo, o ve´ritice de menor limite inferior LIk , neste caso, fac¸a LI = max{LI , LIk}); 1. retire o ve´rtice k de LA e coloque-o em LF ; 2. utilizando uma regra apropriada, subdivida o subconjunto Sk de soluc¸o˜es representadas pelo ve´rtice k em novos subconjuntos Sk ′ gerando assim os novos ve´rtices k ′ para a a´rvore de pesquisa; Iterac¸a˜o - segunda parte bound Para cada novo ve´ritice k ′ gerado, verifique se existe a possibilidade de soluc¸o˜es via´veis no ve´rtice; I se sim: 1. calcule o limite inferior LIk′ do ve´rtice; 2. verifique se LIk′ < LS I se sim: verifique se uma soluc¸a˜o via´vel foi encontrada; - se sim: (i) s = nova soluc¸a˜o encontrada; (ii) LS = LIk′ ; (iii) transferir todos os ve´rtices k ′′ de LA cujo LIk′′ ≥ LS para LF ; - sena˜o: colocar o ve´rtice na LA; I sena˜o: colocar o ve´rtice k ′ na LF ; I sena˜o: colocar o ve´rtice k ′ na lista fechado LF ; Iterac¸a˜o - segunda parte bound Para cada novo ve´ritice k ′ gerado, verifique se existe a possibilidade de soluc¸o˜es via´veis no ve´rtice; I se sim: 1. calcule o limite inferior LIk′ do ve´rtice; 2. verifique se LIk′ < LS I se sim: verifique se uma soluc¸a˜o via´vel foi encontrada; - se sim: (i) s = nova soluc¸a˜o encontrada; (ii) LS = LIk′ ; (iii) transferir todos os ve´rtices k ′′ de LA cujo LIk′′ ≥ LS para LF ; - sena˜o: colocar o ve´rtice na LA; I sena˜o: colocar o ve´rtice k ′ na LF ; I sena˜o: colocar o ve´rtice k ′ na lista fechado LF ; Iterac¸a˜o - segunda parte bound Para cada novo ve´ritice k ′ gerado, verifique se existe a possibilidade de soluc¸o˜es via´veis no ve´rtice; I se sim: 1. calcule o limite inferior LIk′ do ve´rtice; 2. verifique se LIk′ < LS I se sim: verifique se uma soluc¸a˜o via´vel foi encontrada; - se sim: (i) s = nova soluc¸a˜o encontrada; (ii) LS = LIk′ ; (iii) transferir todos os ve´rtices k ′′ de LA cujo LIk′′ ≥ LS para LF ; - sena˜o: colocar o ve´rtice na LA; I sena˜o: colocar o ve´rtice k ′ na LF ; I sena˜o: colocar o ve´rtice k ′ na lista fechado LF ; Iterac¸a˜o - segunda parte bound Para cada novo ve´ritice k ′ gerado, verifique se existe a possibilidade de soluc¸o˜es via´veis no ve´rtice; I se sim: 1. calcule o limite inferior LIk′ do ve´rtice; 2. verifique se LIk′ < LS I se sim: verifique se uma soluc¸a˜o via´vel foi encontrada; - se sim: (i) s = nova soluc¸a˜o encontrada; (ii) LS = LIk′ ; (iii) transferir todos os ve´rtices k ′′ de LA cujo LIk′′ ≥ LS para LF ; - sena˜o: colocar o ve´rtice na LA; I sena˜o: colocar o ve´rtice k ′ na LF ; I sena˜o: colocar o ve´rtice k ′ na lista fechado LF ; Iterac¸a˜o - segunda parte bound Para cada novo ve´ritice k ′ gerado, verifique se existe a possibilidade de soluc¸o˜es via´veis no ve´rtice; I se sim: 1. calcule o limite inferior LIk′ do ve´rtice; 2. verifique se LIk′ < LS I se sim: verifique se uma soluc¸a˜o via´vel foi encontrada; - se sim: (i) s = nova soluc¸a˜o encontrada; (ii) LS = LIk′ ; (iii) transferir todos os ve´rtices k ′′ de LA cujo LIk′′ ≥ LS para LF ; - sena˜o: colocar o ve´rtice na LA; I sena˜o: colocar o ve´rtice k ′ na LF ; I sena˜o: colocar o ve´rtice k ′ na lista fechado LF ; Iterac¸a˜o - segunda parte bound Para cada novo ve´ritice k ′ gerado, verifique se existe a possibilidade de soluc¸o˜es via´veis no ve´rtice;I se sim: 1. calcule o limite inferior LIk′ do ve´rtice; 2. verifique se LIk′ < LS I se sim: verifique se uma soluc¸a˜o via´vel foi encontrada; - se sim: (i) s = nova soluc¸a˜o encontrada; (ii) LS = LIk′ ; (iii) transferir todos os ve´rtices k ′′ de LA cujo LIk′′ ≥ LS para LF ; - sena˜o: colocar o ve´rtice na LA; I sena˜o: colocar o ve´rtice k ′ na LF ; I sena˜o: colocar o ve´rtice k ′ na lista fechado LF ; Observac¸o˜es performace de um algoritmo branch-and-bound 1. branch: uma maneira eficiente de selecionar o ve´rtice para dividir o seu subconjunto 2. bound: uma maneira de se obter uma bom limite inferior maneiras principais para selecionar um ve´ritice 1. pelo menor limite inferior 2. pela largura da a´rvore 3. pela profundidade da a´rvore Observac¸o˜es performace de um algoritmo branch-and-bound 1. branch: uma maneira eficiente de selecionar o ve´rtice para dividir o seu subconjunto 2. bound: uma maneira de se obter uma bom limite inferior maneiras principais para selecionar um ve´ritice 1. pelo menor limite inferior 2. pela largura da a´rvore 3. pela profundidade da a´rvore Observac¸o˜es performace de um algoritmo branch-and-bound 1. branch: uma maneira eficiente de selecionar o ve´rtice para dividir o seu subconjunto 2. bound: uma maneira de se obter uma bom limite inferior maneiras principais para selecionar um ve´ritice 1. pelo menor limite inferior 2. pela largura da a´rvore 3. pela profundidade da a´rvore Observac¸o˜es performace de um algoritmo branch-and-bound 1. branch: uma maneira eficiente de selecionar o ve´rtice para dividir o seu subconjunto 2. bound: uma maneira de se obter uma bom limite inferior maneiras principais para selecionar um ve´ritice 1. pelo menor limite inferior 2. pela largura da a´rvore 3. pela profundidade da a´rvore Observac¸o˜es performace de um algoritmo branch-and-bound 1. branch: uma maneira eficiente de selecionar o ve´rtice para dividir o seu subconjunto 2. bound: uma maneira de se obter uma bom limite inferior maneiras principais para selecionar um ve´ritice 1. pelo menor limite inferior 2. pela largura da a´rvore 3. pela profundidade da a´rvore Observac¸o˜es performace de um algoritmo branch-and-bound 1. branch: uma maneira eficiente de selecionar o ve´rtice para dividir o seu subconjunto 2. bound: uma maneira de se obter uma bom limite inferior maneiras principais para selecionar um ve´ritice 1. pelo menor limite inferior 2. pela largura da a´rvore 3. pela profundidade da a´rvore Problema de minimizac¸a˜o modelo minimizar z = n∑ j=1 cjxj sujeito a` n∑ j=1 aijxj ≥ bi ∀i = 1, . . . ,m xj ∈ {0, 1} ∀j = 1, . . . , n. caracter´ısticas I ordenac¸a˜o no vetor c c1 ≤ c2 ≤ . . . ≤ cn I vetor c todo possitivo se cj , fazer xj = (1− x ′j ), onde x ′j ∈ {0, 1} Linear Inteira =⇒ Programac¸a˜o Linear Bina´ria Todo problema de Programac¸a˜o Linear Inteira pode ser transformado em Programac¸a˜o Linear Bina´ria. Por exemplo, se 0 ≤ x ≤ u, onde 2n−1 < u < 2n enta˜o cada valor via´vel de x pode ser expresso como: x = n∑ i=0 2iyi , com yi ∈ {0, 1} Assim a varia´vel x pode ser substituida em todo o problema por esta soma envolvendo (n + 1) varia´veis bina´rias. Algoritmo Branch-and-bound para PLIB - Balas [1] Notac¸a˜o I soluc¸a˜o parcial: subconjunto de soluc¸o˜es onde se conhece o valor de k primeiras varia´veis do conjunto total das n varia´veis do problema (x1, . . . , xk−1, xk , xk+1, . . . , xn); I soluc¸a˜o completa: soluc¸a˜o onde se conhece o valor de todas as n varia´veis do problema; I conclusa˜o de uma soluc¸a˜o parcial: e´ uma soluc¸a˜o completa partindo de uma soluc¸a˜o parcial (x1, . . . , xk−1, xk , xk+1, . . . , xn); I z∗k : valor o´timo da func¸a˜o objetivo quando a soluc¸a˜o onde a s k primeiras varia´veis foram fixadas e as n − k varia´veis restantes forem nulas (xj = 0 para j = k + 1, . . . , n) for soluc¸a˜o via´vel do problema. Algoritmo Branch-and-bound para PLIB - Balas [1] Notac¸a˜o I soluc¸a˜o parcial: subconjunto de soluc¸o˜es onde se conhece o valor de k primeiras varia´veis do conjunto total das n varia´veis do problema (x1, . . . , xk−1, xk , xk+1, . . . , xn); I soluc¸a˜o completa: soluc¸a˜o onde se conhece o valor de todas as n varia´veis do problema; I conclusa˜o de uma soluc¸a˜o parcial: e´ uma soluc¸a˜o completa partindo de uma soluc¸a˜o parcial (x1, . . . , xk−1, xk , xk+1, . . . , xn); I z∗k : valor o´timo da func¸a˜o objetivo quando a soluc¸a˜o onde a s k primeiras varia´veis foram fixadas e as n − k varia´veis restantes forem nulas (xj = 0 para j = k + 1, . . . , n) for soluc¸a˜o via´vel do problema. Algoritmo Branch-and-bound para PLIB - Balas [1] Notac¸a˜o I soluc¸a˜o parcial: subconjunto de soluc¸o˜es onde se conhece o valor de k primeiras varia´veis do conjunto total das n varia´veis do problema (x1, . . . , xk−1, xk , xk+1, . . . , xn); I soluc¸a˜o completa: soluc¸a˜o onde se conhece o valor de todas as n varia´veis do problema; I conclusa˜o de uma soluc¸a˜o parcial: e´ uma soluc¸a˜o completa partindo de uma soluc¸a˜o parcial (x1, . . . , xk−1, xk , xk+1, . . . , xn); I z∗k : valor o´timo da func¸a˜o objetivo quando a soluc¸a˜o onde a s k primeiras varia´veis foram fixadas e as n − k varia´veis restantes forem nulas (xj = 0 para j = k + 1, . . . , n) for soluc¸a˜o via´vel do problema. Algoritmo Branch-and-bound para PLIB - Balas [1] Notac¸a˜o I soluc¸a˜o parcial: subconjunto de soluc¸o˜es onde se conhece o valor de k primeiras varia´veis do conjunto total das n varia´veis do problema (x1, . . . , xk−1, xk , xk+1, . . . , xn); I soluc¸a˜o completa: soluc¸a˜o onde se conhece o valor de todas as n varia´veis do problema; I conclusa˜o de uma soluc¸a˜o parcial: e´ uma soluc¸a˜o completa partindo de uma soluc¸a˜o parcial (x1, . . . , xk−1, xk , xk+1, . . . , xn); I z∗k : valor o´timo da func¸a˜o objetivo quando a soluc¸a˜o onde a s k primeiras varia´veis foram fixadas e as n − k varia´veis restantes forem nulas (xj = 0 para j = k + 1, . . . , n) for soluc¸a˜o via´vel do problema. Construc¸a˜o da a´rvore de pesquisa Caracter´ısticas da a´rvore de pesquisa 1. ve´rtice k: representa uma soluc¸a˜o parcial onde as k primeiras varia´veis foram fixadas 2. branch: criar dois novos ve´rtices onde xk+1 = 0 e xk+1 = 1 3. limite iferior de cada ve´rtice e´ calculado: LIk = k∑ j=1 cjxj se xk = 1 (ou se k = 0 ou k = n); k−1∑ j=1 cjxj + ck+1 se xk = 0. Construc¸a˜o da a´rvore de pesquisa Caracter´ısticas da a´rvore de pesquisa 1. ve´rtice k: representa uma soluc¸a˜o parcial onde as k primeiras varia´veis foram fixadas 2. branch: criar dois novos ve´rtices onde xk+1 = 0 e xk+1 = 1 3. limite iferior de cada ve´rtice e´ calculado: LIk = k∑ j=1 cjxj se xk = 1 (ou se k = 0 ou k = n); k−1∑ j=1 cjxj + ck+1 se xk = 0. Construc¸a˜o da a´rvore de pesquisa Caracter´ısticas da a´rvore de pesquisa 1. ve´rtice k: representa uma soluc¸a˜o parcial onde as k primeiras varia´veis foram fixadas 2. branch: criar dois novos ve´rtices onde xk+1 = 0 e xk+1 = 1 3. limite iferior de cada ve´rtice e´ calculado: LIk = k∑ j=1 cjxj se xk = 1 (ou se k = 0 ou k = n); k−1∑ j=1 cjxj + ck+1 se xk = 0. Construc¸a˜o da a´rvore de pesquisa outras caracter´ısticas 1. soluc¸a˜o via´vel no ve´rtice k: verificar se cada restric¸a˜o do problema pode ser satisfeita. O ve´rtice k da a´rvore na˜o tem soluc¸a˜o via´vel se k∑ j=1 aij + n∑ j=k+1 max{aij , 0} < bi Exemplo minimizar z = 3x1 + 5x2 + 6x3 + 9x4 + 10x5 + 10x6 sujeito a` −2x1 + 6x2 − 3x3 + 4x4 + x5 − 2x6 ≥ 2 −5x1 − 3x2 + x3 + 3x4 − 2x5 + x6 ≥ −2 5x1 − x2 + 4x3 − 2x4 + 2x5 − x6 ≥ 3 xj ∈ {0, 1} ∀j = 1, . . . , 6. Definic¸a˜o Modelo minimizar z = n∑ j=1 cjxj sujeito a` n∑ j=1 aijxj ≥ bi ∀i = 1, . . . , n xj ∈ IN ∀j = 1, . . . , k(k < n), xj ≥ 0 ∀j = k + 1, . . . , n. Quando i = n, este problema e´ uma problema de Programac¸a˜o Linear Inteira. Algoritmo branch-and-bound para PLIM Origem Proposto por Dakin [2]baseado em Land e Doig [3]. Bibliografia E. Balas. An algorithm for solving linera programs with zero-one variables. Operations Research, 13(4):517–546, 1965. R. J. Dakin. A tree search algorithm for mixed integer programming problems. Computer Journal, 8(3):250–255, 1965. A. H. Land and A. G. Doig. An automatic method for solving discrete programming problems. Econometrica, 28:497–520, 1960. Programação Inteira Introdução Definição Técnica branch-and-baund Algoritmo branch-and-baund Programação Linear Binária Definição Algoritmo branch-and-bound para PLIB - Balas balas65 Programação Linear Inteira Mista Definição Algoritmo branch-and-bound para PLIM Bibliografia
Compartilhar