Cours de modelisation en PLI

Chapitre 6Mod´elisation en P.L.I.6.1 Lien entre PL et PLI(P) probl`eme de PL.– On restreint les variables `a ˆetre enti`eres : on a un probl`eme de PLI (ILP en anglais).– On restreint certaines variables `a ˆetre enti`eres : on a un probl`eme mixte (MILP enanglais).– On peut aussi contraindre les variables `a ˆetre dans {0,1} : on a un probl`eme deprogrammation 0-1.La question de r´esoudre efficacement les problemes de PLI se pose donc. On sait qu’onpeut le faire de mani`ere efficace pour la PL en th´eorie (le probl`eme est polynomial) eten pratique (bien que exponentiel dans le pire cas, le simplexe fonctionne bien). Peut-onobtenir les mˆemes r´esultats pour le probl`eme de PLI?6.1.1 Approximation de la PLIUne m´ethode imm´ediate consiste `a r´esoudre le probl`eme de PL obtenu en relachant lacontrainte x∈N en x∈R, `a r´esoudre le probl`eme de PL obtenu, puis `a prendre commesolution la solution enti`ere la plus proche. Plusieurs probl`emes se posent :– Quelle approximation? partie enti`ere inf´erieure ou sup´erieure, la plus proche?x = 1.22 est proche de ⌊x⌋ = 1 et ⌈x⌉ = 2, le plus proche est 1. Mais x = 1.5 estaussi proche de 1 que de 2.Par contre le dessin suivant montre que c¸a ne donne pas forc´ement une solution!1´2 CHAPITRE 6. MODELISATION EN P.L.I.– Quelle est le lien entre solution enti`eres et solution r´eelles? Le dessin suivant montrequ’elle peuvent ˆetre tr`es ´eloign´ees.Le seul lien exact qu’on peut ´etablir (pour un probl`eme de ...