Moi je commencerai par un programme linéaire en nombre entier.
Le principe, c'est de réduire ton problème à une forme du type:
minimiser A X
tel que B X = C
avec X un vecteur d'entier qui sont les inconnues (et qu'on peut trivialement borner si besoin), C vecteurs de réels constants et B de matrices réeles constantes. Les inconnues peuvent être trivialement bornées, la minimisation peut se transformer facilement en maximisation (suffit de prendre des nombres negatifs dans A), et on peut facilement transformer une égalité en inégalité (si a <= b, alors a = b + inconnue positive)
Sous forme non-matricielle, et en pratique, ça donne :
maximiser a1x1 + a2x2 + .... + anxn
avec b11x1 + b12x2 + .... + b1nxn <= c1
et b21x1 + b22x2 + .... + b2nxn = c2
et b31x1 + b32x2 + .... + b3nxn >= c3
et ....
et bm1x1 + bm2x2 + .... + bmnxn <= cm
Après, il faut juste choisir ses inconnues et ses variables et éxprimer correctement ses contraintes.
L'avantage de cette méthode c'est qu'elle est éxacte et même si tu ne t'en sert pas pour résoudre, elle permet de prouver que tu est bien à l'optimum. Elle est rapide pour des petits problèmes, par contre, elle peut devenir lente si le nombre de relation/variable éxplose, mais dans ce cas la elle peut proposer des solution intermédiaires.
# Programme Lineaire en Nombre Entier
Posté par Batchyx . En réponse au message Programmation générique / programmation par contraintes. Minimisation du nombre d' "insatisfaits". Évalué à 3.
Moi je commencerai par un programme linéaire en nombre entier.
Le principe, c'est de réduire ton problème à une forme du type:
avec X un vecteur d'entier qui sont les inconnues (et qu'on peut trivialement borner si besoin), C vecteurs de réels constants et B de matrices réeles constantes. Les inconnues peuvent être trivialement bornées, la minimisation peut se transformer facilement en maximisation (suffit de prendre des nombres negatifs dans A), et on peut facilement transformer une égalité en inégalité (si a <= b, alors a = b + inconnue positive)
Sous forme non-matricielle, et en pratique, ça donne :
Après, il faut juste choisir ses inconnues et ses variables et éxprimer correctement ses contraintes.
L'avantage de cette méthode c'est qu'elle est éxacte et même si tu ne t'en sert pas pour résoudre, elle permet de prouver que tu est bien à l'optimum. Elle est rapide pour des petits problèmes, par contre, elle peut devenir lente si le nombre de relation/variable éxplose, mais dans ce cas la elle peut proposer des solution intermédiaires.