Resolver um Problema de Pesquisa Operacional Voltado para o Tema Distribuição

Descrição do problema Modelo matemático Execução do GAMS Resultados da resolução do modelo e análises TEMA Distribuição Model Building in Mathematical Programming HP Williams capítulos 12 13 14 seção 18 1218 Optimising a constraint In an integer programming problem the following constraint occurs 9x1 13x2 14x3 17x4 13x5 19x6 23x7 21x8 37 All the variables occurring in this constraint are 01 variables that is they can only take the value of 0 or 1 Find the simplest version of this constraint The objective is to find another constraint involving these variables that is logically equivalent to the original constraint but that has the smallest possible absolute value of the righthand side with all coefficients of similar signs to the original coefficients If the objective were to find an equivalent constraint where the sum of the absolute values of the coefficients apart from the righthand side coefficient were a minimum what would be the result 1318 Optimizing a constraint A procedure for simplifying a single 01 constraint has been described by Bradley et al 1974 We adopt their procedure of using a linear programming model It is convenient to consider the constraint in a standard form with positive coefficients in descending order of magnitude This can be achieved by the transformation y1 x7 y2 x8 y3 1 x6 y4 x4 y5 1 x3 y6 x5 y7 x2 y8 x1 giving 23y1 21y2 19y3 17y4 14y5 13y6 13y7 9y8 70 We wish to find another equivalent constraint of the form a1y1 a2y2 a3y3 a4y4 a5y5 a6y6 a7y7 a8y8 a0 The ai coefficients become variables in the linear programming model In order to capture the total logical import of the original constraint we search for subsets of the indices known as roofs and ceilings Ceilings are maximal subsets of the indices of the variables for which the sum of the corresponding coefficients does not exceed the righthand side coefficient Such a subset is maximal in the sense that no subset properly containing it or to the left in the implied lexicographical ordering can also be a ceiling For example the subset 1 2 4 8 is a ceiling 23 21 17 9 70 but any subset properly containing it eg 1 2 4 7 8 or to the left of it eg 1 2 4 7 is not a ceiling Roofs are minimal subsets of the indices for which the sum of the corresponding coefficients exceeds the righthand side coefficient Such a subset is minimal in the same sense as a subset is maximal For example 2 3 4 5 is a roof 21 19 17 14 70 but any subset properly contained in it eg 3 4 5 or to the right of it eg 2 3 4 6 is not a roof If i 1 i 2 ir is a ceiling the following condition among the new coefficients ai is implied ai1 ai2 air a0 If i 1 i 2 ir is a roof the following condition among the new coefficients ai is implied ai1 ai2 air a0 1 It is also necessary to guarantee the ordering of the coefficients This can be done by the series of constraints a1 a2 a3 a8 If these constraints are given together with each constraint corresponding to a roof or ceiling then this is a sufficient set of conditions to guarantee that the new 01 constraint has exactly the same set of feasible 01 solutions as the original 01 constraint In order to pursue the first objective we minimize a0a3a5 subject to these constraints For the second objective we minimize For this example the set of ceilings is 1 2 31 2 4 81 2 6 71 3 5 62 3 4 62 5 6 7 8 The set of roofs is 1 2 3 81 2 5 71 3 4 71 5 6 7 82 3 4 53 4 6 7 8 The resultant model has 19 constraints and 9 variables If the constraint were to involve general integer rather than 01 variables then we could still formulate the simplification problem in a similar manner after first converting the constraint to one involving 01 variables in the way described in Section 101 It is however necessary to ensure by extra constraints in our LP model the correct relationship between the coefficients in the simplified 01 form How this may be done is described in Section 102 1418 Optimizing a constraint The simplest version of this constraint with minimum righthand side coefficient is 6x1 9x2 10x3 12x4 9x5 13x6 16x7 14x8 25 This is also the equivalent constraint with the minimum sum of absolute values of the coefficients Tradução chat 1218 Otimizando uma restrição Em um problema de programação inteira ocorre a seguinte restrição 9x 1 13x2 14x3 17x4 13x5 19x6 23x7 21x8 37 Todas as variáveis que ocorrem nesta restrição são variáveis binárias 01 ou seja só podem assumir os valores 0 ou 1 Encontre a versão mais simples desta restrição O objetivo é encontrar outra restrição envolvendo essas variáveis que seja logicamente equivalente à restrição original mas que tenha o menor valor absoluto possível no lado direito com todos os coeficientes de sinais semelhantes aos coeficientes originais Se o objetivo fosse encontrar uma restrição equivalente onde a soma dos valores absolutos dos coeficientes exceto o coeficiente do lado direito fosse mínima qual seria o resultado 1318 Otimizando uma restrição Um procedimento para simplificar uma única restrição 01 foi descrito por Bradley et al 1974 Adotamos o procedimento deles usando um modelo de programação linear É conveniente considerar a restrição em uma forma padrão com coeficientes positivos em ordem decrescente de magnitude Isso pode ser conseguido pela transformação y1 x7 y2 x8 y3 1 x6 y4 x4 y5 1 x3 y6 x5 y7 x2 y8 x1 dando 23y1 21y2 19y3 17y4 14y5 13y6 13y7 9y8 70 Desejamos encontrar outra restrição equivalente da forma a1y1 a2y2 a3y3 a4y4 a5y5 a6y6 a7y7 a8y8 a0 Os coeficientes ai tornamse variáveis no modelo de programação linear Para capturar o total significado lógico da restrição original procuramos subconjuntos dos índices conhecidos como tetos e pisos Tetos são subconjuntos máximos dos índices das variáveis para os quais a soma dos coeficientes correspondentes não excede o coeficiente do lado direito Tal subconjunto é máximo no sentido de que nenhum subconjunto que o contém ou que está à esquerda na ordem lexicográfica implícita pode também ser um teto Por exemplo o subconjunto 1 2 4 8 é um teto pois 23 21 17 9 70 mas qualquer subconjunto que o contenha por exemplo 1 2 4 7 8 ou à esquerda dele por exemplo 1 2 4 7 não é um teto Pisos são subconjuntos mínimos dos índices para os quais a soma dos coeficientes correspondentes excede o coeficiente do lado direito Tal subconjunto é mínimo no mesmo sentido que um subconjunto é máximo Por exemplo 2 3 4 5 é um piso pois 21 19 17 14 70 mas qualquer subconjunto contido nele por exemplo 3 4 5 ou à direita dele por exemplo 2 3 4 6 não é um piso Se i1 i2 ir é um teto a seguinte condição entre os novos coeficientes ai é implicada ai1 ai2 air a0 Se i1 i2 ir é um piso a seguinte condição entre os novos coeficientes ai é implicada ai1 ai2 air a0 1 Também é necessário garantir a ordenação dos coeficientes Isso pode ser feito pela série de restrições a1 a2 a3 a8 Se essas restrições forem dadas juntamente com cada restrição correspondente a um teto ou piso então este é um conjunto suficiente de condições para garantir que a nova restrição 01 tenha exatamente o mesmo conjunto de soluções viáveis 01 que a restrição original 01 Para buscar o primeiro objetivo minimizamos a0 a3a5 sujeito a essas restrições Para o segundo objetivo minimizamos a soma dos valores absolutos dos coeficientes exceto o coeficiente do lado direito Para este exemplo o conjunto de tetos é 1 2 3 1 2 4 8 1 2 6 7 1 3 5 6 2 3 4 6 2 5 6 7 8 O conjunto de pisos é 1 2 3 8 1 2 5 7 1 3 4 7 1 5 6 7 8 2 3 4 5 3 4 6 7 8 O modelo resultante tem 19 restrições e 9 variáveis Se a restrição envolvesse variáveis inteiras gerais em vez de 01 poderíamos ainda formular o problema de simplificação de maneira semelhante após primeiro converter a restrição para uma que envolva variáveis 01 conforme descrito na Seção 101 No entanto é necessário garantir por meio de restrições extras em nosso modelo de PL a relação correta entre os coeficientes na forma simplificada 01 Como isso pode ser feito é descrito na Seção 102 1418 Otimizando uma restrição A versão mais simples desta restrição com o menor coeficiente no lado direito é 6x1 9x2 10x3 12x4 9x5 13x6 16x7 14x8 25 Esta também é a restrição equivalente com a menor soma dos valores absolutos dos coeficientes