1.4 Appli ca tions élé men taires
© Dunod – Toute reproduction non autorisée est un délit.
35
2. Nous ne sommes pas encore cer tains que les deux solu tions obte nues soient
opti males, car il nous faut encore remettre en ques tion le tout pre mier choix, 1*, que
nous avons effec tué.
Ce fai sant, nous obte nons un nou veau second membre 1, écrit tout à droite du
tableau des seconds membres et consta tons que F < 5. Il est donc inutile de pour -
suivre le cal cul.
Conclu sion. Les deux solu tions équi va lentes déter mi nées pré cé dem ment sont opti
males.
L’explo ra tion réa li sée peut être sché ma ti sée par l’arbo res cence ci- après.
Nous ver rons ulté rieu re ment, au cha pitre consa cré à la théo rie des graphes, qu’il
s’agit d’une pro cé dure de recherche arbo res cente avec la stra té gie « en pro fon deur
d’abord » (appe lée aussi pro cé dure d’éva lua tion et sépa ra tion séquen tielle). Les
traits doubles indiquent des impli ca tions du choix immé dia te ment réa lisé ; ainsi, si
après avoir choisi x 2 5 1 (qui n’a pas d’impli ca tion directe), on choi sit x 1 5 1, on a
alors les impli ca tions (consé quences) : x 4 5 0 et x 3 5 1. De même si l’on fait x 2 = 1
puis x 1 = 0, on a les implications x 4 = 1 et x 3 = 0 .
Figure 1.19
Variables posi tives entières quel conques
L’exemple pré senté ci- dessous est l’exemple résolu aussi dans le cha pitre 4 dédié
aux méthodes de réso lu tion par sépa ra tion et éva lua tion.
© Dunod – Toute reproduction non autorisée est un délit.
35
2. Nous ne sommes pas encore cer tains que les deux solu tions obte nues soient
opti males, car il nous faut encore remettre en ques tion le tout pre mier choix, 1*, que
nous avons effec tué.
Ce fai sant, nous obte nons un nou veau second membre 1, écrit tout à droite du
tableau des seconds membres et consta tons que F < 5. Il est donc inutile de pour -
suivre le cal cul.
Conclu sion. Les deux solu tions équi va lentes déter mi nées pré cé dem ment sont opti
males.
L’explo ra tion réa li sée peut être sché ma ti sée par l’arbo res cence ci- après.
Nous ver rons ulté rieu re ment, au cha pitre consa cré à la théo rie des graphes, qu’il
s’agit d’une pro cé dure de recherche arbo res cente avec la stra té gie « en pro fon deur
d’abord » (appe lée aussi pro cé dure d’éva lua tion et sépa ra tion séquen tielle). Les
traits doubles indiquent des impli ca tions du choix immé dia te ment réa lisé ; ainsi, si
après avoir choisi x 2 5 1 (qui n’a pas d’impli ca tion directe), on choi sit x 1 5 1, on a
alors les impli ca tions (consé quences) : x 4 5 0 et x 3 5 1. De même si l’on fait x 2 = 1
puis x 1 = 0, on a les implications x 4 = 1 et x 3 = 0 .
Figure 1.19
Variables posi tives entières quel conques
L’exemple pré senté ci- dessous est l’exemple résolu aussi dans le cha pitre 4 dédié
aux méthodes de réso lu tion par sépa ra tion et éva lua tion.