Arbres et arborescences
177
Ce problème s'exprime de la façon suivante : si on pose
si le randonneur choisit
l'objet et
s'il ne le choisit pas, il s'agit de résoudre le PL en variables bivalentes
suivant :
Remarque : le problème du choix des investissements évoqué à la fin de la partie sur la
programmation linéaire obéit à la même formulation, ce qui montre que cet exemple n'a
pas seulement une valeur anecdotique.
On peut fort bien imaginer de résoudre ce problème par une méthode arborescente, en
construisant des sous-ensembles de solutions, où certaines des variables
sont
spécifiées et pas les autres. Une évaluation par excès (on est ici dans une perspective de
maximisation) est obtenue en chacun de sous-ensembles en résolvant le programme
linéaire en variables réelles correspondant, compte tenu des variables spécifiées.
Pour fixer les idées, prenons le petit exemple numérique suivant, à quatre variables :
Indépendamment du fait que des considérations très simples aboutissent ici à l'optimum
(une énumération exhaustive pour
variables conduit à
calculs), appliquons les
principes précédents.
Le PL en variables réelles donne
, les autres variables nulles, et
(ici le
simplexe est réduit à sa plus simple expression) et ne donne donc pas une solution
réalisable. Mais c'est bien une évaluation par excès sur l'ensemble des solutions.
Prenons alors le sous-ensemble des solutions tel que
et le sous-ensemble des
solutions tel que
(pourquoi le choix de ? parce que le rapport
est le plus
grand pour cette variable, ce qui correspond à une règle intuitive de choix). On obtient le
début d'une arborescence, en calculant à chaque fois une évaluation par excès par
résolution du PL en variables réelles, avec d'une part
et d'autre part
.
177
Ce problème s'exprime de la façon suivante : si on pose
si le randonneur choisit
l'objet et
s'il ne le choisit pas, il s'agit de résoudre le PL en variables bivalentes
suivant :
Remarque : le problème du choix des investissements évoqué à la fin de la partie sur la
programmation linéaire obéit à la même formulation, ce qui montre que cet exemple n'a
pas seulement une valeur anecdotique.
On peut fort bien imaginer de résoudre ce problème par une méthode arborescente, en
construisant des sous-ensembles de solutions, où certaines des variables
sont
spécifiées et pas les autres. Une évaluation par excès (on est ici dans une perspective de
maximisation) est obtenue en chacun de sous-ensembles en résolvant le programme
linéaire en variables réelles correspondant, compte tenu des variables spécifiées.
Pour fixer les idées, prenons le petit exemple numérique suivant, à quatre variables :
Indépendamment du fait que des considérations très simples aboutissent ici à l'optimum
(une énumération exhaustive pour
variables conduit à
calculs), appliquons les
principes précédents.
Le PL en variables réelles donne
, les autres variables nulles, et
(ici le
simplexe est réduit à sa plus simple expression) et ne donne donc pas une solution
réalisable. Mais c'est bien une évaluation par excès sur l'ensemble des solutions.
Prenons alors le sous-ensemble des solutions tel que
et le sous-ensemble des
solutions tel que
(pourquoi le choix de ? parce que le rapport
est le plus
grand pour cette variable, ce qui correspond à une règle intuitive de choix). On obtient le
début d'une arborescence, en calculant à chaque fois une évaluation par excès par
résolution du PL en variables réelles, avec d'une part
et d'autre part
.