IntroductionLa recherche oprationnelle (R.O) est une discipline dont le but est:

De fournir un ensemble de mthodes (algorithmiques, mathmatiques, modlisation) pour rpondre un type prcis de problme.

Dlaborer des dmarches qui permettent de prendre des dcisions optimales ou proches de loptimum dans des problmes complexes.

De traiter la maximisation dun profit ou la minimisation dun cot (problme doptimisation):

Comment aller le plus vite de Paris Safi, en voiture?

Comment ordonnancer les tches dun projet en fonction de la main duvre, tout en minimisant sa dure?

Comment investir ses 1000 Dirhams dconomie de sorte maximiser le profit obtenu aprs deux ans?

Comment Envoyer un maximum dinformation dans un rseau

Gnralement, les dmarches proposes par la recherche oprationnelle peuvent tre traduites en programmes informatiques.

Cette traduction -d'une dmarche- en un programme informatique n'est pas sans difficult.

Tout d'abord, le temps d'excution du programme rsultant et/ou la place occupe dans la mmoire de l'ordinateur peuvent ne pas tre acceptables.

Ainsi, une mthode en recherche oprationnelle sera juge sur ces critres de temps et de place. Plus une mthode sera rapide et peu gourmande en mmoire, plus elle sera considre bonne.

Parmi les outils importants de la recherche oprationnelle: les graphes: se sont des outils la fois graphique et thorique.

La programmation linaire: Elle permet d'apporter une solution gnrique la rsolution de nombreux problmes. De plus, cet outil est disponible sous diffrentes formes pour une utilisation informatique.Introduction

Chemin le plus court / le plus longSoit un ensemble de villes et des chemins directs reliant ces villes entre elles.

Le problme dit "du plus court chemin" consiste trouver, pour une ville de dpart donne et une ville d'arrive donne, le chemin le plus court qui relie ces deux villes.

Le problme peut galement tre de trouver un chemin le plus court pour chaque couple de villes.

Pour certains problmes, trouver le plus long chemin entre deux points peut tre intressant

Ordonnancement / planificationConsidrons la gestion d'un grand projet. Il est constitu de diffrentes tapes raliser.

Donc, certaines tches doivent tre effectues avant d'autres alors que certaines peuvent trs bien tre effectues en mme temps (utilisation de diagramme Gantt).

Ainsi, on tablit une certaine relation d'ordre entre les tapes. Un premier problme consiste trouver une planification des tches qui aboutisse la ralisation du projet en un minimum de temps. Ensuite, il peut tre intressant de dtecter les tapes dites "critiques" dont le moindre retard peut affecter toute la suite du projet. Exemples de problmes traits par R.O

Flot maximumSoit des chteaux d'eau ayant un dbit constant. Ils desservent un certain nombre de villes, chacune ayant des besoins quantifis constants. L'eau est achemine travers des conduits dont le dbit maximum est connu.

Le problme est de trouver un moyen de satisfaire au mieux les demandes de chaque ville. En d'autres termes, essayer d'apporter le plus d'eau possible vers les villes.

Flot de cot minimumIl s'agit d'un problme semblable celui du flot maximum mais on suppose en plus qu'un cot en fonction du dbit est associ l'utilisation d'un conduit.

Le problme devient alors de satisfaire les villes mais de la manire la moins onreuse. Exemples de problmes traits par R.O

Sac dosUn randonneur prpare son sac dos pour partir en excursion. Il veut viter d'avoir un sac trop lourd et dcide de se limiter dans le choix des objets qu'il emporte afin de ne pas dpasser un certain poids.

mais, il veut emporter le maximum de choses utiles. Pour cela, il affecte une valeur quantitative chaque objet en plus de son poids (plus la valeur est importante, plus le randonneur juge l'objet important).

Le problme peut donc se formuler de la manire suivante: Trouver l'ensemble des objets dont la somme des utilits est maximum tout en ne dpassant pas un poids fix.

AffectationDes modifications de postes sont effectues dans une entreprise.Plusieurs personnes doivent tre affectes de nouveaux postes.Ainsi, chacun classe par ordre de prfrence les postes qu'il veut occuper.

Le problme ici est d'attribuer chaque personne un poste tout en essayant de satisfaire au mieux le souhait de chacun. Exemples de problmes traits par R.O

Voyageur de commerceUn voyageur de commerce doit dmarcher dans un certain nombre de villes. Le voyageur connat la distance qui spare les villes entre elles. Cependant, le voyageur de commerce veut perdre le moins de temps possible dans ses dplacements.

Le problme est donc de trouver un chemin qui passe par toutes les villes une et une seule fois et qui soit le plus court possible. Exemples de problmes traits par R.O

Les problmes de programmation linaire (PL) sont des problmes doptimisation (maximisation ou minimisation): dune fonction objectif linaire (de plusieurs variables) sous certaines contraintes (quations ou inquations) qui sont toutes linaires.

La fonction objectif et les contraintes sont dduites via la modlisation dun problme rel

Si lon constate que le problme traiter sexprime comme un PL, on le rsout via des mthodes et algorithmes qui assurent la rsolution du problme de manire exacte.

On distingue dans la programmation linaire: La programmation linaire en nombres rels, pour laquelle les variables des quations sont dans IR+ La programmation en nombres entiers, pour laquelle les variables sont dans IN

Lcriture du problme optimiser sous la forme: Des inquations Dun objectif optimiser forment ce quon appel un Programme LinaireProgrammation linaire

Objectif : Apprendre modliser les problmes rels et rsoudre les programmes linaires.De nombreux problmes rels peuvent tre exprims comme des programmes linaires.Les programmes linaires peuvent tre rsolus efficacement par certains algorithmes, de mathmatiques lmentaires et de bon sens.

En Recherche Oprationnelle (RO), modliser un problme consiste identifier:Les variables intrinsques (inconnues)les diffrentes contraintes auxquelles sont soumises ces variablesl'objectif vise (optimisation).Pourquoi un cours sur la programmation linaire?

Considrons un agriculteur qui possde des terres,

de superficie gale H hectares, dans lesquelles il peut planter du bl et du mas.

Lagriculteur possde une quantit E dengrais et I dinsecticide.

Le bl ncessite une quantit Eb dengrais par hectare et Ib dinsecticide par hectare.

Les quantits correspondantes pour le mas sont notes Em et Im.

Soit Pb le prix de vente du bl et Pm celui du mas.

Si lon note par xb et xm le nombre dhectares planter en bl et en mas, comment exprimer le fait que lagriculteur souhaite maximiser son gain, tout en restant dans les limites de ses ressources?Exemple: Le problme

Remarque pour la modlisation du PbComprendre la question de lobjectif: Maximiser le revenu net ou le gain

Identifier ou dfinir les variables dont dpend lobjectif de la question: xb le nombre dhectares planter en blxm le nombre dhectares planter en mas

Dfinir les rgles associs ses variables et leurs interactions: Dfinir les inquations reliant xb et xm en utilisant les contraintes du problme

Dfinir la fonction objectif: La fonction maximiser en fonction de xb et xm

Rsoudre le problme avec la mthode adquate. Exemple: modlisation du problme

maximiser Pb * xb + Pm * xm (maximiser le revenu net)

contraintes xb + xm H (surface) Eb * xb + Em * xm E (engrais) Ib * xb + Im * xm I (insecticide) xb 0 xm 0 Exemple: modlisation du problme

En gnrale, un Programme Linaire est dfini par:Des variables relles qui sont les variables de dcision:x1, x2, . . . , xnUne fonction objectif linaire (fonction de cot ou fonction conomique), optimiser (min ou max) :z = c1*x1 + c2*x2 + + cn*xnContraintes linaires (galits ou ingalits) :a11x1 + a12x2 + + a1nxn b1a21x1 + a22x2 + + a2nxn b2 am1x1 + am2x2 + + amnxn = bm

P = (x1, x2, . . . , xn) est appele solution admissible dun PL: si P satisfait toutes les contraintes.On appel solution optimale dun PL: toute solution admissible qui optimise (maximise ou minimise) la fonction objectif.Rgion admissible = lensemble des solutions admissibles

Il y a plusieurs manires dexprimer un programme linaire :la forme canonique et la forme standard.Programme linaire : dfinition

Programme linaire : Forme canoniqueUn programme linaire (P.L) est dit canonique sil est de la forme

Donc, on a:Un problme de maximisationToutes les variables sont non ngativesToutes les autres contraintes sont des inquations du type

Sous format matricielle, (P.L) devient:

Programme linaire : Forme standardUn programme linaire (P.L.) est dit standard sil est de la forme

Donc, on a:Un problme de maximisationToutes les variables sont non ngativesToutes les autres contraintes sont des quations du type =

Sous format matricielle, (P.L) devient:

Proprit Tout P.L peut se mettre au choix sous forme canonique ou standard.

Quelques rgles de transformation :Inquation quation : ajouter une variable d carta x b a x + s = b, s 0a x b a x s = b, s 0

quation inquations :a x = b a x b et a x b a x b et (-a) x -b

Variable libre :x IR x = x+ x, avec x+ 0, x 0

Cas variable ngativex 0 x = (-x+) et x+ 0

Variable borne infrieurementx b x = x+ + b et x+ 0 Rgles de transformation

Transformation Pb non linaire en Pb linaire:Problmes min maxLe problme doptimisation non linairemin z = max{c1x + d1, . . . , ck x + dk}s.c . . . .

est quivalent au programme linairemin z = ts.c. . . .t c1x + d1.t ck x + dkt IR

La transformation sadapte galement aux problmes max-min.

Transformation Pb non linaire en Pb linaire: Problmes max minLe problme doptimisation non linairemax z = min{c1x + d1, . . . , ckx + dk}s.c . . . .

est quivalent au programme linairemax z = ts.c . . . .t c1x + d1.t ck x + dkt IR

Transformation Pb non linaire en Pb linaire: Valeurs absolues ??Rgle de transformation valeur absolue|x| b x b et x -b

Le problme doptimisation non linaire (Rappel: |x| = max(x,-x))min z = |x|s.c. . . .

est quivalent au programme linairemin z = t min z = x+ + x-s.c. . . . s.c. . . .t x x = x+ - x-t x x+ 0t 0 x- 0

RemarqueLa premire mthode ci-dessus ne sadapte pas aux problmes du type max z = |x| ni aux contraintes du type |x| b.

Transformation Pb non linaire en Pb linaire: Valeurs absoluesLe problme doptimisation non linairemin z = |f(x1, x2, , xn)|s.c. . . .

est quivalent au programme linairemin z = ts.c. . . .t f(x1, x2, , xn)t f(x1, x2, , xn)t 0

Exemple de conversionSoit le programme linaire suivant :

Remarque:Minimiser une fonction = maximiser la fonction oppose ( 1)Minimisation maximisation : min f(x) = max (f(x))Pour minimiser z = c x, il suffit de: maximiser w = c x = (c) x et demultiplier la valeur optimale de w par 1 pour obtenir celle de z.Les contraintes de positivits :

Transformation des galits en deux contraintes : (pas de contraintes sur x2)

Exemple de conversionLe programme linaire devient le programme suivant :

Version canonique du programme linaire ci-dessus

Exemple de conversionConversion en forme standardSoit xn+i la variable dcart de la ime contrainte (si n contraintes)Donc la ime contrainte sera sous la forme de lgalit :

Comme le nombre de contraintes est n = 3, on aura (P.L) sous format standard est donn par:

Ou simplement, on dduit directement la forme standard de la forme canonique

Programme linaire : solution de baseDfinitionSoit un polydre P = { x : Ax = b, x 0} avec A IRm * n est de rang plein, alors: x* est une solution de base de P ssi A x* = b et Il existe m indice B(1), , B(m) tels que les colonnesAB(1),.., AB(m), sont linairement indpendantSi i B(1), , B(m), alors x*i = 0

Remarque:A IRm * n est de rang plein c.a.d les lignes de A sont linairement indpendantsm est le nombre de contraintes dgalit.n est le nombre de variables.

Problme: Comment obtenir une solution de base sous les mmes conditions que la dfinition

Choisir m colonne de A linairement indpendantSoit B=[AB(1),.., AB(m) ] la matrice compose de ces colonnes.B est appele matrice de baseImposer xi=0 pour tout i B(1), , B(m), Rsoudre le systme Bx = b pour les inconnues xB(1),.., xB(m)Note: B est inversible

Exemple : solution de baseOn dduit alors la matrice de base, donne par les vecteurs dont lindices sontB(1)=4, B(2)=5, B(3)=6, B(4)=7De plus, on a x1=x2=x3=0

Puis, on rsout:On dduit, x4=8, x5=12, x6=4, x7=6Donc, (0, 0, 0, 8, 12, 4, 6) est une solution de base admissibleSolution admissible car on vrifie aussi la contrainte de positivit

Programme linaire : solution de baseSous format matricielle, la solution de base Systme linaire Ax = b est dtermineAvec A de format m *n, dont le rang A = m n

On a la matrice de base de A : est la sous-matrice B(m * m) inversible de A

En posant A = (B; N), x= (xB, xN) T le systme linaire devient:(B, N) (xB, xN)T = b ou bien B xB + N xN = b;Do: xB = B-1 b - B-1 N xN

Donc, la solution de base associe B :xN = 0 valeur des variables hors base.xB = B-1 b valeurs des variables de base.

En dimension deux, chaque contrainte dun P.L. dfinit un demi-plan de IR2 (ou une droite sil sagit dune quation)

Soit R_A la rgion dadmissibilit Si R_A est borne non videR_A est un polygone de IR2 dont les cts sont des segments de droites reprsentant les contraintes linaires du problmeun point P l intersection de 2 cts du polygone est un point extrme ou sommetUne solution optimale est soit:Un sommet : solution optimale uniqueUn ct du polygone: infinit de solutions optimales ( la valeur de la f.o. est unique)Rsolution graphique: problme deux variables

Si R_A est non borne et non videLa solution optimale est soit:Un sommet: solution optimale uniqueun ct de la rgion admissible: infinit de solutions optimales( la valeur de la f.o. est unique )Elle est infinie (aucune solution admissible finie)Rsolution graphique:problme deux variables

Si R_A est vide (cas de contraintes incompatible)Rsolution graphique: problme deux variables

Soit rsoudre le problme suivant:Maximiser z = 1200 x1 + 1000x2s.c 3 x1 + 4 x2 160 6 x1 + 3 x2 180 x1 0 ; x2 0

On obtient alors la rgion admissible donne par la figure ci-dessousExemple :problme deux variables de dcision

Il s'agit donc de chercher l'intrieur de ce domaine : le couple (x1, x2) qui maximise la fonction objectif.

On a l'quation 1200 x1 + 1000x2 = z0 est reprsente par une droite de pente constante =-1,2dont tous les points (x1 , x2) fournissent la mme valeur z0 pour la fonction conomique (Une lignes de niveaux dont la valeur est z0).

En particulier, la droite 1200 x1 + 1000x2 = 0 passe par l'origine et donne une valeur nulle la fonction objectif (z0 = 0).

Pour augmenter la valeur de z0 et donc la fonction objectif, il suffitd'loigner de l'origine (dans le quart de plan x1 0;x2 0) la droite de pente = -1,2 (dune faon parallle cette droite )

Pour respecter les contraintes, cette droite sera dplace paralllement vers le haut (dans le sens du gradient: (dz/dx, dz/dy)) jusqu' l'extrme limite o il n'y aura plus qu'un point d'intersection (ventuellement un segment) avec la rgion des solutions admissibles. Exemple : problme deux variables de dcision

On remarquera que la solution optimale se trouve ncessairement sur le contour de la rgion des solutions admissibles.

La solution se trouvant sur les deux droites d'quation 3 x1 + 4 x2 = 160 6 x1 + 3 x2 = 180

La rsolution de ce systme conduit la solution x1 =16 , x2 = 28,

d'o z = 47200.Exemple :problme deux variables

Identification du domaine admissible

Identification des lignes de niveau

Lignes de niveaux perpendiculaire au vecteur gradient de z (dz/dx, dz/dy) et donc parallles entre elles.

A chaque valeur de z correspond une ligne de niveau

La valeur de z augmente dans la direction du gradient

la solution optimale se trouve ncessairement sur le contour de la rgion des solutions admissibles (si elle est non vide et borne)

RemarqueLes lignes de niveau {f.o = constant} de la fonction-objectif f.o sont des hyperplans affines (n = 2 droite, n = 3 plan...)Solution optimal via la reprsentation graphique

Vocabulaire suggr par la mthode graphique : cas dim > 2PropositionLa rgion admissible, note DR, est une rgion convexe dun espace de dimension r ( polytope ou polydre convexe dans le cas de contraintes compatible).

DfinitionUn point x DR est un sommet si et seulement sil nexiste pasy, z DR, y z tels que x = y + (1)z avec 0 < < 1.

Propritun point P lintersection de (s 2) hyperplans reprsentant les contraintes est un sommet (point extrme) du polydre

Propritune solution optimale est soit:Un unique sommet du polydreUne infinit de solutions optimales frontire du polydre = hyperplan de dimension < r ( la valeur de la f. o. est unique)Elle est infinie (aucune solution admissible finie)

RemarqueLa rgion admissible est vide dans le cas de contraintes incompatibles

Solution graphique: cas dim > 2DfinitionSoit E un IK-espace vectoriel et H un sous espace vectoriel de E.On dit que H est un hyperplan de E si H est de codimension 1.

Un polytope convexe de IRm est l'intersection (suppose non vide) d'une famille finie de demi-espaces ferms de IRm.

Remarques:Dans un espace de dimension finie n, les hyperplans sont donc les sous-espaces vectoriels de dimension n-1. Dans IR3, la notion d'hyperplan est confondue avec celle de plan, mais ce n'est plus vrai quand la dimension de l'espace est suprieure 3

RemarquesLensemble DR nest pas ncessairement born. Pour un P.L, on a trois situations qui peuvent se produire: DR = : P.L na pas de solution.DR ; et la fonction objectif f.o nest pas majore sur DR : le maximum de f.o vaut +. Si DR est born, ce cas est exclu.DR ; et la fonction objectif f.o est majore sur DR : le P.L admet une solution optimale (non ncessairement unique).

****Remarque. Pour la forme canonique pure avec Ax b, lhypothse de rang plein nest pas non plusrestrictive car si rang(A) < m, il y a des contraintes ingalits redondantes quon peut supprimer pourobtenir un systme de rang plein.Cas max, prendre x = x1 x2 avec |x| = x1+x2 et x1 >= 0, x2>=0**Un polydre = intersection de demi-espaces.P reprsente les contraintes dans le cas de forme standard****Hyperplan H={x in IRn: x.b = a} avec b un vecteur de IRn et a rel Demi-espace E ={x in IRn: x.b