Chapitre 1 • Structures ordonnées Applications des treillis
34
ces colonnes sont infé rieurs ou égaux, à la valeur du second membre (et ceci dans
cha cune des lignes).
Pre nons donc le meilleur, appa rem ment, en essayant x 1 5 1. Ce sera notre choix
2*, que nous note rons sur la ligne des choix. Ses consé quences appa raissent à la
colonne 2 du second membre.
Nous nous aper ce vons alors que les choix ulté rieurs ne seront plus libres. En
effet, nous ne pou vons faire ni x 4 5 1, ni x 3 5 1, car le second membre devien drait
néga tif, ce qui est impos sible évi dem ment.
Contraints de prendre x 4 5 0 et x 3 5 1, nous dirons que ces affec ta tions sont
des impli ca tions du choix 2*. C’est pour quoi sur la ligne des choix, nous écri rons
2 (sans asté risque) dans les colonnes cor res pon dantes. Met tons à jour le second
membre (2a).
Étant par ve nus au bord droit du tableau des coef fi cients, nous avons donc une
solu tion. C’est x 1 5 1 ; x 2 5 1 ; x 3 5 1 ; x 4 5 0, qui donne bien à F la valeur 7 qui
figure au bas de la colonne 2a. En effet :
F 5 10 2 1 5 3 0 1 3 3 0 1 2 3 1 1 1 3 12 5 10 2 3 5 7.
Mais nous ne savons pas si cette solu tion est opti male.
• Deuxième phase : recherche de la solu tion opti male (ou des solu tions
équi va lentes à la pré cé dente, si elle se révèle opti male)
S’il existe une meilleure solu tion que la pré cé dente, c’est que nos choix n’ont pas été
heu reux. C’est pour quoi nous allons les remettre en ques tion, sys té ma ti que ment, en
remon tant de proche en proche.
1. Lorsque nous avons effec tué le choix 2*, nous aurions aussi bien pu prendre
x 1 5 1 (en effet, notre choix était libre) et c’est ce que nous ferons main te nant. Ce
choix entraîne un nou veau second membre numé roté 2, à droite du double trait, et
l’on remarque déjà que l’on ne pourra pas ainsi trou ver une solu tion meilleure que la
pré cé dente , puisque ce choix implique F < 7. Conti nuons, dans l’espoir de décou -
vrir une solu tion équi va lente.
Nos choix sont libres : autre ment dit, le nou veau choix 2* n’implique aucune
affec ta tion. Il faut néan moins, pour notre choix 3*, prendre x 4 5 1, car, sans cela, F
serait infé rieure ou égale à 5. Dans ces condi tions, nous écri rons, non pas 3*, mais
2r, d’où un nou veau second membre, 2a.
Notre choix est encore libre, en appa rence. Mais si nous pre nions x 3 5 1, il en
résul te rait F < 6. C’est pour quoi nous choi sis sons x 3 5 1 et nous obte nons le second
membre 2b.
Une nou velle fois, nous sommes arri vés au bord droit du tableau des coef fi cients. La
nou velle solu tion obte nue est équi va lente à la pré cé dente : x 1 5 0, x 2 5 1 ; x 3 5 0 ;
x 4 5 1 ; F 5 7.
34
ces colonnes sont infé rieurs ou égaux, à la valeur du second membre (et ceci dans
cha cune des lignes).
Pre nons donc le meilleur, appa rem ment, en essayant x 1 5 1. Ce sera notre choix
2*, que nous note rons sur la ligne des choix. Ses consé quences appa raissent à la
colonne 2 du second membre.
Nous nous aper ce vons alors que les choix ulté rieurs ne seront plus libres. En
effet, nous ne pou vons faire ni x 4 5 1, ni x 3 5 1, car le second membre devien drait
néga tif, ce qui est impos sible évi dem ment.
Contraints de prendre x 4 5 0 et x 3 5 1, nous dirons que ces affec ta tions sont
des impli ca tions du choix 2*. C’est pour quoi sur la ligne des choix, nous écri rons
2 (sans asté risque) dans les colonnes cor res pon dantes. Met tons à jour le second
membre (2a).
Étant par ve nus au bord droit du tableau des coef fi cients, nous avons donc une
solu tion. C’est x 1 5 1 ; x 2 5 1 ; x 3 5 1 ; x 4 5 0, qui donne bien à F la valeur 7 qui
figure au bas de la colonne 2a. En effet :
F 5 10 2 1 5 3 0 1 3 3 0 1 2 3 1 1 1 3 12 5 10 2 3 5 7.
Mais nous ne savons pas si cette solu tion est opti male.
• Deuxième phase : recherche de la solu tion opti male (ou des solu tions
équi va lentes à la pré cé dente, si elle se révèle opti male)
S’il existe une meilleure solu tion que la pré cé dente, c’est que nos choix n’ont pas été
heu reux. C’est pour quoi nous allons les remettre en ques tion, sys té ma ti que ment, en
remon tant de proche en proche.
1. Lorsque nous avons effec tué le choix 2*, nous aurions aussi bien pu prendre
x 1 5 1 (en effet, notre choix était libre) et c’est ce que nous ferons main te nant. Ce
choix entraîne un nou veau second membre numé roté 2, à droite du double trait, et
l’on remarque déjà que l’on ne pourra pas ainsi trou ver une solu tion meilleure que la
pré cé dente , puisque ce choix implique F < 7. Conti nuons, dans l’espoir de décou -
vrir une solu tion équi va lente.
Nos choix sont libres : autre ment dit, le nou veau choix 2* n’implique aucune
affec ta tion. Il faut néan moins, pour notre choix 3*, prendre x 4 5 1, car, sans cela, F
serait infé rieure ou égale à 5. Dans ces condi tions, nous écri rons, non pas 3*, mais
2r, d’où un nou veau second membre, 2a.
Notre choix est encore libre, en appa rence. Mais si nous pre nions x 3 5 1, il en
résul te rait F < 6. C’est pour quoi nous choi sis sons x 3 5 1 et nous obte nons le second
membre 2b.
Une nou velle fois, nous sommes arri vés au bord droit du tableau des coef fi cients. La
nou velle solu tion obte nue est équi va lente à la pré cé dente : x 1 5 0, x 2 5 1 ; x 3 5 0 ;
x 4 5 1 ; F 5 7.