Remplacement variables entières par booléennes

[Tanc]

Bonjour à tous,

J'ai un exemple d'exercice avec solution devant moi mais je bloque sur un point.
Je vous expose l'ensemble.

Je dois résoudre le problème


J'ai les contraintes suivantes :






et entières, positives ou nulles.

1. On nous propose d'obtenir la borne supérieure.
La première contrainte nous donne, si , donc
La combinaison linéaire positive des deux dernières contraintes nous donne



d'où et donc ( est un entier )

Maintenant je bloque ....
En 2, on nous propose de remplacer les variables entières par des variables booléennes.

Je cite.
" On peut écrire
les variables binaires, et étant binaires, cela revient en somme, tenant compte de sa borne supérieure, à décomposer en ses poids binaires.

De même,
Si , alors x_2 = 7 ce qui viole les contraintes 1 et 2.
Ces trois variables ne pourront donc pas être égales 1."

Je ne comprends pas comment on obtient et de . Une âme charitable pourrait-elle me guider ?

Bien à vous,

Pierre

[fatal_error]

salut,

je vois pas trop pourquoi écrire une telle décomposition, mais en tout cas il s'agit juste d'écrire x1 sous sa forme binaire.

De la même manière que tu écris
5 = 101 (2) (c'est 4+0+1)
tu écris
x_1 = a_na_{n-1}...a_0 (2)
et la valeur correspondante décimale est bien sure
x_1 = 2^n a_n + 2^{n-1}a_{n-1}+...+2^0 a_0
où tes a sont des variables binaires (valant 0 ou 1)