Un problème de programmation mathématique

Question

J'ai un problème d'optimisation comme suit.

Étant donné une matrice d'entiers positifs, par ex. (y1 = 2, y2 = 3, y3 = 1, y4 = 4, y5 = 3), je vise à maximiser la somme des valeurs des fonctions f(x), où f(x) = x if x + y <= m et f(x) = 0 sinon. (m est un entier positif)

Par exemple, dans cet exemple particulier ci-dessus (avec m = 5), la valeur x optimale est 2, comme la somme serait 2 + 2 + 2 + 0 + 2 = 8, ce qui est le plus élevé parmi les autres valeurs possibles pour x (implicitement , possible x se situerait entre 0 et 5)

je peux bien sûr travailler de façon exhaustive et de comparer les sommes entraîné par toutes les valeurs possibles de x et sélectionnez le x qui donne la somme la plus élevée, à condition que la gamme de x est raisonnablement faible . Cependant, si la gamme devient grande, cette méthode peut devenir excessivement coûteuse.

Je me demande s'il y a quelque chose que je peux utiliser à partir de choses comme la programmation linéaire pour résoudre ce problème plus généralement et correctement.

Answer 1

Il n'y a pas besoin de programmation linéaire ici, juste un tri et un seul passage pour déterminer le x optimal.

Le pseudo-code est:

getBestX(m, Y) { 
    Y = sort(Y); 
    bestSum = 0; 
    bestX = 0; 

    for (i from 0 to length(Y)) { 
     x = m - Y[i]; 
     currSum = x * (i + 1); 
     if (currSum > bestSum) { 
      bestSum = currSum; 
      bestX = x; 
     } 
    } 

    return bestX; 
} 

Note pour chaque i nous savons que si x = m - Y[i] puis f(x) = x pour chaque élément jusqu'à et y compris i et f(x) = 0 pour chaque élément après, puisque Y est dans l'ordre croissant.