RO II Notes de Cours R.O MASTER M1

RECHERCHE OPERATIONNELLE

PARTIE II

1Mias2011.wordpress.com

RO II : PROGRAMMATION NON LINEAIRE Notes de Cours R.O MASTER M1

CHAPITRE IV PROGRAMMATION NON LINÉAIRE

I. Introduction Nous avons vu dans la partie I que certains problèmes sont modélisés en programme non linéaire. En effet la programmation linéaire ne représente qu’un cas particulier des problèmes rencontrés en optimisation et que dans beaucoup de situations, on est amené à considérer des fonctions économiques et/ou des contraintes non linéaires.Rappelons qu’un programme linéaire est représenté graphiquement par un polyèdre convexe dont un des sommets représente la solution optimale (si elle est unique) :

Un programme non linéaire est beaucoup plus difficile à résoudre, et la théorie du simplexe ne peut être utilisée. Considérons deux cas particuliers pour illustrer la difficulté de recherche de la solution optimale dans le cas non linéaire :

Cas 1 : Contraintes non linéaires / Fonction objectif linéaire

Cas 2 : Contraintes linéaires / Fonction objectif non linéaire

2Mias2011.wordpress.com

RO II : PROGRAMMATION NON LINEAIRE Notes de Cours R.O MASTER M1Dans ces deux cas, il apparaît alors comme évident que la recherche de la solution optimale est plus difficile que dans le cas linéaire. De plus, si la solution est cherchée entière, la complexité est encore augmentée. Malheureusement, il n’existe pas dans le domaine non linéaire d’équivalent à l’algorithme du simplexe, outil simple et efficace de résolution des problèmes linéaires.

Nous allons détailler dans ce qui suit la programmation quadratique et semi-définie : un cas particulier et plus fréquent de la programmation non linéaire.

II. Programmation quadratique et semi définie

II.1 DÉFINITIONUn problème de programmation quadratique est un problème qui peut se mettre sous la forme suivante :

MinZ=∑i=1

n

ci x i+∑i=1

n

∑j=1

n

hij x i x j

Avec∑i=1

n

a ij x i≤0∀ j∈1 ,.. ,m

Ou encore avec la notation matricielle :

Min Z = CX + 12 XT H X

Avec AX ≤ 0

La matrice H est appelée : Matrice Hessienne (Matrice des dérivées secondes)

Exemple :Considérons le programme quadratique suivant :

{MinZ=3 x1+7 x2+5 x12+4 x2

2+6 x1 x2

Avec 3 x1+4 x2≤09 x1+2 x2≤0

En notation matricielle, nous avons :

X=[ x1

x2], C=[ 3 4 ], H=[10 66 8 ], A=[3 4

9 3 ]Remarque : La programmation quadratique couvre aussi le cas où les contraintes sont elles aussi quadratique.

II.2. ILLUSTRATION GRAPHIQUE

Exemple en 2 dimensions Exemple en 3 dimensions

{MaxZ=x1+ x2

Avec x12+x2

2≥1x1

2+x22≤2

x1≥0x2≥0

{Max Z=x1x2+x2x3

Avec x12−x2

2+x32≤2

x12+ x2

2+x32≤10

x1 srsx2 srs

L’intersection d’une ligne avec l’ensemble L’intersection de la surface avec l’espace

3Mias2011.wordpress.com

RO II : PROGRAMMATION NON LINEAIRE Notes de Cours R.O MASTER M1des contraintes représente la solution des contraintes représente la solution

II.3 PROGRAMMATION SEMI DÉFINIE Un programme semi définie est un cas particulier de la programmation quadratique, pour lequel la matrice hessienne H est semi définie positive, c’est à dire que :

∀ X∈R :XT H X ≥0Cette condition garantie la convexité de la fonction quadratique correspondante (fonction objectif et/ou contraintes) : condition importante pour la méthode de résolution détaillée ci-après.

III. Un outil de résolution : La relaxation semi définieLa résolution des programmes quadratiques et non linéaires en général reste un domaine de recherche très actif vu la difficulté du problème. Parmi le peu de méthodes de résolution existantes, on a la relaxation semi définie qui est une extension de la relaxation lagrangienne vu précédemment.

Exemple : Soit à optimiser le rendement (Z) d’une terre en fonction de la quantité de fertilisant (x1) et d’insecticide (x2). Nous obtenons le programme quadratique suivant :

{Opt Z=x1+3x1 x2

¿ Avec x1+2x2=8

La relaxation semi définie (Lagrangienne) conduit au Lagrangien suivant :

L (x1 , x2 , λ )=x1+3 x1 x2+λ (8−x1−2 x2)

L’introduction du multiplicateur de Lagrange λ permet de transformer un problème d’optimisation avec contrainte à 2 variables (x1 et x2) en un problème d’optimisation sans contrainte à 3 variables (x1, x2, λ).

La recherche du point stationnaire se fait en posant : x L(x,) = 0 (Conditions du premier ordre)

∂L∂x1

=3 x2+1−λ=0

∂L∂x2

=3 x1−2 λ=0

∂L∂λ

=8−x1−2 x2=0

On solutionne ce système d’équations et on trouve (x1¿ , x2

¿ , λ¿ ) : x1¿= 26/6 , x2

¿=11 /6 , λ¿=39/6 .

En principe, à ce stade-ci, on doit calculer les conditions de second ordre et vérifier si le point stationnaire (x1

¿ , x2¿ , λ¿ )représente un minimum ou un maximum.

Remarque : La convexité (caractéristique de la programmation semi définie) garantie l’existence d’un seul point stationnaire (optimum global).

4Mias2011.wordpress.com

RO II : THEORIE DES JEUX Notes de Cours R.O MASTER M1

CHAPITRE V THÉORIE DES JEUX (GAME THEORY)

I. INTRODUCTIONLa théorie des jeux peut être considérée comme faisant partie de la recherche opérationnelle (RO) mais aussi de l’intelligence artificielle (IA) dans le sens où on cherche à aider les participants aux jeux (joueurs) à prendre les meilleures décisions (aide à la décision, choix optimal).

La théorie des jeux étudie les situations où le sort de chaque participant dépend non seulement des décisions qu’il prend mais également des décisions prises par d’autres participants (situation de rivalité ou d’interaction stratégique). Chaque joueur agit pour son propre compte et chacun cherche à prendre les meilleures décisions pour lui-même (principe de rationalité).

La théorie des jeux s’est avérée extrêmement riche pour l’analyse des comportements des entreprises, des luttes d’influence entre groupes au sein d’une institution, des négociations internationales entre gouvernements ou encore de la concurrence électorale entre partis politiques. Elle trouve donc son application dans plusieurs domaines : l’économie (fixation des prix, négociation au sein de l’OMC), la biologie (cohabitation et la proportion de différents types d’espèces), science sociale (comprendre comment les individus membres d’une société régissent leurs relations sociales), science politique (formation de coalition gouvernementale) ou tout simplement les jeux (jeux d’échecs…).

Comme application directe, la théorie des jeux est utilisée dans la conception de systèmes automatiques d’aide à la décision (automated decision-making) et la conception de systèmes automatiques de négociation (automated negotiation).

La théorie des jeux fut fondée par Von Neumann et Morgenstern en 1944 lors de la parution de leur ouvrage « Theory of Games and Economic Behavior ». Nash (1951) puis par la suite Selten ont donné les fondements de base pour la construction de solutions aux jeux appelées aussi équilibre.

Exemples classiques de jeux :

Le dilemme du prisonnier On suppose que deux suspects sont interrogés séparément par la police pour une action grave. La police ne dispose pas d’éléments de preuve suffisants pour obtenir la condamnation des prévenus pour l’acte dont ils sont accusés. L’aveu d’au moins l’un des deux est donc indispensable. La police propose à chaque accusé d’avouer séparément. S’il n’avoue pas mais que l’autre le fait, il écope d’une peine de prison de 15 ans. Si les deux avouent, ils peuvent espérer bénéficier de circonstances atténuantes et recevoir une peine de 8 ans chacun. Enfin, si aucun des deux n’avoue, ils seront condamnés pour des délits mineurs à 1 an de prison. Ce jeu peut être représenté comme suit :

Joueur 2Avoue N’avoue pas

Joueur 1 Avoue (-8 , -8) (0 , -15)N’avoue pas (-15 , 0) (-1 , -1)

Le jeu de la tirelireDeux étudiants sont choisis au hasard et le jeu suivant leur est proposé. Chacun a la possibilité de mettre 0 ou 1000 DA dans une tirelire. Après que chaque étudiant ait pris sa décision sans connaître la décision de l’autre, le contenu de la tirelire est multiplié par 1.5 et réparti en deux parties égales entre les deux joueurs. La matrice des gains est :

Joueur 20 DA 1000 DA

Joueur 1 0 DA (0 , 0) (750 , -250)1000 DA (-250 , 750) (500 , 500)

TYPES DE JEUX :5

Mias2011.wordpress.com

J1

J2

J2

0DA

0DA

1000DA0DA

1000DA

1000DA

(0 , 0)

(750 , -250)

(-250 , 750)

(500 , 500)

RO II : THEORIE DES JEUX Notes de Cours R.O MASTER M1

Jeux coopératifs et non coopératifsUn jeu est coopératif lorsque des joueurs peuvent passer entre eux des accords qui les lient de manière contraignante (par exemple, sous la forme d’un contrat qui prévoit une sanction légale dans le cas du non respect de l’accord). On dit alors qu’ils forment une coalition. Dans le cas contraire, c’est-à-dire lorsque les joueurs n’ont pas la possibilité de former des coalitions, le jeu est non coopératif. C’est ce dernier qui sera étudié dans ce cours.

Jeux à somme nulle / à somme variableUn jeu à deux joueurs est à somme nulle si les gains d’un joueur sont égaux aux pertes de l’autre. Sinon, on parle de jeux à somme variable, c’est le cas d’ailleurs des deux exemples cités précédemment.

Jeux statiques / dynamiquesOn dit qu’un jeu est statique (one-shot game) lorsque les joueurs choisissent simultanément leurs actions et reçoivent ensuite leurs gains respectifs. Dans un jeu dynamique le temps est une composante essentielle dans la mesure où certains joueurs ont le pouvoir d’affecter directement les gains des autres joueurs de manière irréversible parce qu’ils interviennent à des étapes antérieures du jeu.

II. REPRÉSENTATION D’UN JEUUn jeu peut être défini de deux manières différentes mais équivalentes :

- Forme stratégique (ou normale)  : Représentation matricielle- Forme extensive (ou développée) : Représentation en arbre

Forme stratégiqueUn jeu en forme stratégique est une collection de stratégies décrivant les actions de chaque joueur dans toutes les situations concevables du jeu, ainsi que les gains (payoffs) que chacun obtient lorsque les stratégies de tous les joueurs sont connues. Seules certaines actions seront effectivement choisies et donc observées, tandis que les stratégies incluent des actions possibles qui ne sont pas choisies durant le jeu.

Forme extensiveUn jeu en forme extensive (on dit aussi développée) est défini par un arbre qui décrit comment le jeu est joué. Plus précisément, chaque sommet de l’arbre spécifie le (ou les) joueur(s) qui doit (doivent) choisir une action à ce moment du jeu ainsi que l’information dont chaque joueur dispose lors de la prise de décision ; les gains que chaque joueur peut réaliser après avoir suivi un des chemins possibles au sein de l’arbre sont donnés aux sommets terminaux.

Exemple : Le jeu de la tirelire décrit précédemment sous forme stratégique peut être représenté sous forme extensive comme suit :

III. DÉFINITION D’UN JEU EN FORME STRATÉGIQUELes éléments constitutifs d’un jeu G en forme stratégique sont les suivants :

(1) N = {1, … , n} est l’ensemble des joueurs.On suppose que les joueurs sont en nombre fini. Un joueur quelconque est désigné par l’indice i.

(2) si désigne une stratégie du joueur i N.Une stratégie décrit de manière précise tout ce qu’un joueur fait.

(3) Si est l’ensemble des stratégies du joueur i N.

6Mias2011.wordpress.com

RO II : THEORIE DES JEUX Notes de Cours R.O MASTER M1Cet ensemble décrit toutes les stratégies disponibles pour le joueur i.

(4) s = (s1,…,si,…,sn) S1 × … × Si × … × Sn S , est une issue du jeu, c’est-à-dire une combinaison de stratégies à raison d’une stratégie par joueur. On désigne par s−i S−i toutes les stratégies choisies sauf celle du joueur i.

(5) ui(s) ℝ est la fonction de gain (ou utilité) du joueur i N.Autrement dit, la « fonction objectif » du joueur i dépend non seulement de sa stratégie si, mais aussi de celles des autres joueurs résumées dans s−i.

Le joueur i préfère strictement l’issue s à l’issue s’ si ui(s) > ui(s’). Si ui(s) = ui(s’), le joueur est indifférent entre les deux issues.

Remarques : Chaque joueur connaît les ensembles de stratégies et les fonctions de gains de tous les joueurs,

y compris donc les siens. Du fait de cette dernière hypothèse, on dit que le jeu est en information complète. Dans le cas contraire, le jeu est dit en information incomplète. Les joueurs ne connaissent certains éléments constitutifs du jeu qu’en termes de probabilité ; par exemple, le joueur i ne connaît pas la fonction de gain du joueur k mais dispose d’une distribution de probabilité sur les fonctions possibles.

Un jeu à deux joueurs est à somme nulle si u1(s) + u2(s) = 0 le profil de stratégies s S.

IV. RÉSOLUTION D’UN JEU (RECHERCHE D’UN ÉQUILIBRE)

IV.1. Equilibre en stratégies dominantesDans un jeu en forme stratégique, on dit qu’une stratégie si

' Si est dominante pour le joueur i si :

si Si et si si' , les inégalités ui(si

' , s−i) ≥ ui(si, s−i) sont satisfaites pour tout s−i S−i.

Si dans un jeu donné tous les joueurs disposent d’une stratégie dominante, le résultat du jeu est appelé équilibre en stratégies dominantes. Il faut préciser que dans un tel équilibre, chaque joueur dispose d’une stratégie dominante mais même si l’un des joueurs prend en compte le choix de la stratégie dominante de l’autre, il trouve la même stratégie dominante.

Exemple 1 :Dans le dilemme du prisonnier, le couple (Avouer, Avouer) est un équilibre en stratégies dominantes. Les prévenus vont subir donc une peine de 8 ans. Toutefois, s’ils “coopéraient” en n’avouant rien, la condamnation qui leur serait appliquée serait beaucoup plus légère puisqu’elle serait de 1 an. Ce jeu, malgré sa très grande simplicité, met en évidence la contradiction qui sous-tend de nombreux conflits, à savoir que les participants devraient souvent s’entendre plutôt que de se combattre.

Exemple 2 :Dans le jeu de la tirelire, on peut constater que mettre 0 DA dans la tirelire est une stratégie dominante. Mettons nous en effet à la place du joueur 1 qui tient le raisonnement suivant : “si 2 ne met rien dans la tirelire, il est optimal pour moi de ne rien mettre sinon je perdrais 250 DA ; s’il dépose 1000 DA, je gagne 750 DA si je ne mets rien, et 500 DA si je mets 1000 DA. Par conséquent, dans les deux cas de figure, j’ai intérêt à ne rien mettre dans la tirelire”. Si les deux étudiants suivent le même raisonnement, le résultat serait un gain nul pour chacun d’eux. Même s’ils se mettaient d’accord avant le début du jeu pour coopérer et mettre 1000 DA, il reste “optimal” pour chacun de ne rien mettre dans la tirelire s’ils sont motivés par la recherche de leur seul intérêt personnel. C’est là bien sur que l’on peut attaquer la solution proposée. Les étudiants ont, comme tout le monde, des préférences qui incluent d’autres variables que leur seul gain immédiat. Ils sont, par exemple, sensibles à ce que les autres vont penser d’eux et vont peut-être mettre 1000 DA pour ne pas laisser voir qu’ils ont envie de “profiter de la situation”. Mais en irait-il de même si l’anonymat leur était garanti durant le déroulement du jeu ?

IV.2. Processus de dominance successive

7Mias2011.wordpress.com

RO II : THEORIE DES JEUX Notes de Cours R.O MASTER M1a. PrincipeL’existence d’un équilibre en stratégies dominantes est rare. Aussi doit-on souvent faire appel à d’autres manières de raisonner dans l’espoir de trouver une “solution” au jeu. Si joueur 1 possède une stratégie dominante, alors on peut s’attendre à ce qu’il choisisse cette stratégie ; comme le joueur 2 est capable d’anticiper ce choix, il choisit alors sa meilleure stratégie contre la stratégie dominante du premier.

Considérons le jeu suivant :Joueur 2

G M DJoueur 1 H (4 , 3) (5 , 1) (6 , 2)

M (2 , 1) (8 , 4) (3 , 6)B (3 , 0) (9 , 6) (2 , 8)

Dans ce jeu, l’ensemble des stratégies du joueur 1 est donné par le triplet {H,M,B} tandis que celui de son rival est donné par {G,M,D}. On remarque que ce jeu ne possède pas de stratégies dominantes. Quelle solution peut-on espérer voir émerger ?Cet exemple fait apparaître un concept plus faible que celui de stratégie dominante, à savoir celui de stratégie strictement dominée.

Définition :On dit qu’une stratégie si

' Si est strictement dominée pour le joueur i s’il existe une autre stratégie

si Si telle que : ui(si, s−i) > ui(si' , s−i) pour tout s−i S−i.

Dans l’exemple précédent on remarque que M est une stratégie strictement dominée par D qui assure toujours au joueur 2 des gains plus élevés quelque soit le choix de 1 (notons cependant que D n’est pas une stratégie dominante). Dans ce cas, il est raisonnable de penser que le joueur 2 ne retiendra jamais la stratégie M. On décide donc (y compris le joueur 1) d’éliminer la stratégie M de la matrice. Cela étant fait, on remarque alors que, dans la matrice résultante, H est “devenue” une stratégie dominante pour le joueur 1. Dés lors, celui-ci devrait jouer H. Par hypothèse, le joueur 2 est capable de reconstruire ce raisonnement, de sorte que, anticipant le choix H de 1, il est “optimal” pour lui de choisir G. En conséquence, si chaque joueur est capable de raisonner comme nous venons de le faire, le “résultat” du jeu serait donné par le couple (H,G).

Le processus d’´elimination qu’y vient d’être appliqué dans cet exemple est appelé processus de dominance successive. Il exige un comportement plus sophistiqué que celui prêté aux joueurs dans le dilemme du prisonnier, dans la mesure où chaque joueur doit être capable de reconstituer les opérations auxquelles l’autre procède et d’en déduire de nouvelles implications pour lui-même. Par exemple, 1 anticipe que 2 ne jouera pas M ce qui le conduit à réaliser que H est alors son meilleur choix. Sans cela, 1 ne pourrait pas réaliser que H devient une stratégie dominante.

Bien entendu, s’il existe une stratégie dominante pour un joueur, toutes les autres sont dominées et peuvent donc être éliminées en vertu du processus de dominance successive. Celui-ci est donc de nature plus générale et permet de proposer des solutions pour des jeux qui n’admettent pas d’équilibre en stratégies dominantes.

b. Limites du processus de dominance successiveLe processus de dominance successive admet des limites. Prenons par exemple le jeu suivant :

Joueur 2G D

Joueur 1 H (3 , 6) (7 , 1)M (5 , 1) (8 , 0)B (6 , 0) (6 , 2)

Dans ce cas, il est clair que H est strictement dominée par M (pour le joueur 1). On décide donc de la négliger. Toutefois, on ne peut plus aller plus loin car il n’y a plus de stratégie strictement dominée dans la matrice résultante. Cela revient à dire que, dans ce cas, le processus de dominance stricte ne conduit pas à un “résultat” unique.

8Mias2011.wordpress.com

RO II : THEORIE DES JEUX Notes de Cours R.O MASTER M1Remarques :1. L’emploi du processus de dominance successive ne conduit pas nécessairement à une solution unique, ce qui laisse donc subsister une indétermination quant au résultat du jeu.

2. La résolution d’un jeu non coopératif par application successive de la dominance stricte semble donc fournir une solution satisfaisante quand elle conduit à une solution unique. Pourtant, la solution à laquelle conduit ce processus ne s’impose pas toujours de façon naturelle. Considérons en effet le jeu suivant :

Joueur 2G D

Joueur 1 H (8 , 10) (-100 , 9)B (7 , 6) (6 , 5)

Pour le joueur 2, D est strictement dominée. Après élimination de cette stratégie, B est strictement dominée pour le joueur 1. Dès lors, le résultat du jeu serait donné par (H,G). Toutefois, s’il a la moindre incertitude quant au comportement de 2, le joueur 1 pourrait se retrouver dans une situation catastrophique : s’il joue H tandis que 2 se trompe et joue D, 1 réalise une perte énorme. Dès lors, certains individus préfèrent jouer B qui leur garantit dans tous les cas un gain significatif et une perte relative assez faible par rapport à H. Cela correspond à ce que l’on peut appeler un comportement prudent.

IV.3. Equilibre de NashLe processus de dominance successive ne conduit pas nécessairement à un résultat clair. Il apparaît donc nécessaire de disposer d’une solution dont les conditions d’existence soient plus faibles.On considère le jeu décrit par la matrice suivante :

Joueur 2G D

Joueur 1 H (0 , 0) (2 , 2)B (10 , 11) (-1 , 0)

Il n’y a de stratégie dominante/dominée pour aucun des deux joueurs. Toutefois, la paire (B,G) semble une solution raisonnable en ce qu’aucun joueur ne semble pouvoir faire mieux pour lui-même. Plus précisément, cette paire constitue ce que l’on appelle un équilibre de Nash : chaque joueur maximise ses gains compte tenu de l’action supposée de l’autre.

Définition :On dit qu’une combinaison de stratégies s* est un équilibre de Nash (ou un équilibre non coopératif) si l’inégalité suivante est satisfaite :

pour chaque joueur i = 1, 2, ....n : ui(si¿ , s−i

¿) ui(si

❑ , s−i¿

) pour tout si Si

En d’autres termes, si le joueur i anticipe correctement que les autres participants au jeu vont choisir les stratégies associées à s−i

¿, il maximise son gain en choisissant au sein de l’ensemble Si la stratégie si

¿ . Cette

propriété de stabilité (le joueur ne souhaite pas modifier sa décision) étant satisfaite pour chaque joueur, la solution décrite par l’équilibre de Nash capte ainsi l’idée intuitive de ce que l’on entend intuitivement par “équilibre”.A l’équilibre de Nash, dès que le jeu est terminé et que chacun en observe les résultats, il n’éprouve aucun regret car il n’aurait pas pu augmenter son gain en faisant un choix différent.

Exemple : Considérons ainsi le jeu suivant :Joueur 2

G DJoueur 1 H (0 , 1) (5 , 4)

B (3 , 6) (-1 , 0)

Dans ce jeu, (B,G) est encore un équilibre de Nash, mais celui-ci ne semble pas s’imposer avec la même force que dans les cas précédents. En outre, on peut vérifier que (H,D) est aussi un équilibre de Nash. Dès lors, quel équilibre les joueurs vont-ils retenir ?

Remarque : La multiplicité des équilibres est une des difficultés majeures rencontrées en théorie des jeux.

9Mias2011.wordpress.com

RO II : THEORIE DES JEUX Notes de Cours R.O MASTER M1

10Mias2011.wordpress.com