Modèles linéaires: étude de cas industrielset économiques

Pierre Fouilhoux

pierre.fouilhoux@lip6.fr

March 22, 2011

Avant-propos

Ce document est un support de cours et de projets pour 4 séances de 4 heures d'un cours

intégré donné à l'école ENSTA (Ecole Nationale Supérieure de Techniques Avancées)

dans l'Unité d'Enseignement Introduction à l'optimisation discréte. Il s'adresse à des

étudiants ayant des connaissances en algorithmique, théorie des graphes et Program-

mation Linéaire (des rappels sont mis en �n de recueil).

Son objectif est de voir comment la Programmation Linéaire peut traiter des prob-

lèmes de Recherche Opérationnelle en insistant plus particulièrement sur les problèmes

industrielles ou économiques.

Séances correspondantes:

29/03/11: Exercices de base et solveur linéaire Glpk / Première partie du projet

05/04/11: Interprétation économique / Etude de cas

26/04/11: Seconde partie du projet

10/05/11: Rendu du projet

Références utilisées pour ce cours

• Linear Programming, Freeman, de Vasek Chvátal (incontournable mais en anglais)

• Exercices et problèmes résolus de recherche opérationnelle (3 tomes), Dunod, par

Roseaux.

• Programmation Lineaire, Jean Teghem, Université de Bruxelles.

Il existe de très nombreux autres et bons livres sur la Programmation Linéaire dans

les livres de Recherche Opérationelle et d'Optimisation combinatoire.

2

Contents

1 Premiers exercices de modélisation 5

1.1 Introduction par 2 exemples . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Exercices de modélisation . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.1 Combinaison optimale en vitamines . . . . . . . . . . . . . . . . 6

1.2.2 Alliages et pourcentages . . . . . . . . . . . . . . . . . . . . . . 6

1.2.3 Essence sans plomb . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Utilisation du logiciel Glpk 8

3 Interprétation économique 14

3.1 Interprétation du Théorème des Ecarts Complémentaires . . . . . . . . 14

3.2 Interprétation des variables duales . . . . . . . . . . . . . . . . . . . . . 15

3.3 Exemples d'interprétation économique . . . . . . . . . . . . . . . . . . 16

3.3.1 Economie sans tendresse... . . . . . . . . . . . . . . . . . . . . . 16

3.3.2 Machine-outils . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.4 Programme linéaire paramétré . . . . . . . . . . . . . . . . . . . . . . . 17

4 Etudes de cas 18

4.1 Aide à la décision dans une exploitation agricole . . . . . . . . . . . . . 18

4.2 Aide à la décision dans une exploitation forestière . . . . . . . . . . . . 20

5 Projet: Jeu de l'arbre de poids minimum 23

5.1 Organisation du projet . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

5.2 Première partie: une répartition stable . . . . . . . . . . . . . . . . . . 24

5.2.1 Dé�nition du problème . . . . . . . . . . . . . . . . . . . . . . . 24

5.2.2 Coalitions et répartitions . . . . . . . . . . . . . . . . . . . . . . 25

5.2.3 Répartition stable . . . . . . . . . . . . . . . . . . . . . . . . . . 26

5.2.4 Questions théoriques . . . . . . . . . . . . . . . . . . . . . . . . 26

5.2.5 Questions pratiques . . . . . . . . . . . . . . . . . . . . . . . . . 27

5.3 Deuxième partie: une répartition équitable . . . . . . . . . . . . . . . . 28

5.3.1 Répartition équitable . . . . . . . . . . . . . . . . . . . . . . . . 283

5.3.2 Egalité et équité . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5.3.3 Excès . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.3.4 Questions théoriques . . . . . . . . . . . . . . . . . . . . . . . . 31

5.3.5 Questions pratiques . . . . . . . . . . . . . . . . . . . . . . . . . 33

6 Annexe: Programmation Linéaire 34

6.1 Dé�nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

6.1.1 Dé�nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

6.2 Résolution d'un Programme Linéaire . . . . . . . . . . . . . . . . . . . 35

6.2.1 Résultats principaux . . . . . . . . . . . . . . . . . . . . . . . . 35

6.2.2 Algorithme du simplexe: cadre général . . . . . . . . . . . . . . 35

6.2.3 Forme standard et variables d'écart . . . . . . . . . . . . . . . . 35

6.2.4 Base réalisable et solutions associées . . . . . . . . . . . . . . . 36

6.3 Algorithme du simplexe: exercices calculatoires . . . . . . . . . . . . . 38

6.3.1 Interprétation géométrique . . . . . . . . . . . . . . . . . . . . . 38

6.3.2 Algorithme du simplexe: les di�cultés . . . . . . . . . . . . . . 38

6.4 Dualité et interprétation économique . . . . . . . . . . . . . . . . . . . 39

6.4.1 Dé�nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

6.4.2 Dualité et borne supérieure . . . . . . . . . . . . . . . . . . . . 40

6.4.3 Propriétés de la dualité . . . . . . . . . . . . . . . . . . . . . . . 40

6.4.4 Le théorème des écarts complémentaires . . . . . . . . . . . . . 41

4

Chapter 1

Premiers exercices de modélisation

1.1 Introduction par 2 exemples

1er exemple Problème de production (tiré d'un livre de 1ere S)

Un fabriquant de yaourt produit 2 types de yaourts à la fraise A et B à partir de

Fraise, de Lait et de Sucre. Chaque yaourt doit respecter les proportions suivantes de

matières premières.

A B

Fraise 2 1

Lait 1 2

Sucre 0 1

Les matières premières sont en quantité limitée: 800 kilos de Fraises, 700 kilos de Lait

et 300 kilos de sucre. La vente des yaourts A rapportent 4ε par kilo et les yaourts B

5ε.

a) Donner une formulation du problème sous la forme d'un programme linéaire.

b) Donner la représentation graphique du problème.

c) Donner la solution optimale.

2ème exemple Problème de transport

Une entreprise de construction d'automobiles possèdent 3 usines à Paris, Strasbourg

et Lyon. Elle a besoin d'acheminer les métaux nécessaires à partir du Havre ou de

Marseille. Chaque usine nécessite hebdomadairement 400t à Paris, 300t à Strasbourg

et 200t à Lyon. Les ports du Havre et de Marseille peuvent fournir respectivement

550t et 350t.

5

Les coûts de transport entre ces villes sont donnés en kilo-ε par tonne dans le tableau

suivant.

Paris Strasbourg Lyon

le Havre 5 6 3

Marseille 3 5 4

Proposer une modélisation de ce problème de transport de manière à satisfaire la

demande, à partir des quantités disponibles et en minimisant les coûts de transport.

1.2 Exercices de modélisation

1.2.1 Combinaison optimale en vitamines

Une personne soucieuse de sa forme physique souhaite absorber chaque jour 36 unités

de vitamine A, 28 unités de vitamine C et 32 unités de vitamine D. Deux marques sont

succeptibles de forunir ces apports. La marque 1 coûte 3 euros et procure 2 unités de

vitamine C et 8 unités de vitamine D. La marque 2 coûte 4 euros et procure 3 unité

de vitamine A, 2 unités de vitamine C et 2 unités de vitamine D.

Il s'agit de trouver la combinaison respectant les exigences d'absorption quotidiennes

au moindre coût.

- Dé�nir les variables de décision de ce problème.

- Formuler la fonction objectif.

- Ecrire les contraintes.

1.2.2 Alliages et pourcentages

Un industriel veut fabriquer un alliage dont la composition est 30% de cuivre, 30%

de zinc et 40% de fer. Il trouve disponible sur le marché 9 sortes d'alliages dont les

compositions et les prix sont donnés par le tableau suivant.

Alliage 1 2 3 4 5 6 7 8 9

Cuivre 10 10 40 60 30 30 30 50 20

Zinc 10 30 50 30 30 40 20 40 30

Fer 80 60 10 10 40 30 50 10 50

Coût au kg (ε) 4 5 6 6 8 8 7 6 7

Sachant que le coût de l'opération de mélange est indépendant des alliages util-

isés, l'industriel se demande quels alliages il doit acheter et dans quelles proportions

pour minimiser son coût de production? Formuler ce problème comme un programme

linéaire.6

1.2.3 Essence sans plomb

Une ra�nerie veut fabriquer dans une période donnée de l'essence sans plomb avec 3

ingrédients: du butane, du naphta lourd et du réformat catalytique. Quatre caractéris-

tiques de l'essence résultante et de ses composants sont importants: le coût, l'indice

d'octane, la tension de vapeur et la volatilité. Ces caractéristiques sont résumées dans

le tableau ci-dessous. L'indice d'octane est une mesure du pouvoir antidétonant du

carburant dans le moteur (un faible indice donne un �cognement� caractéristique). La

tension de vapeur et la volatilité sont très liées. La tension de vapeur est une mesure du

risque d'explosion au stockage, notamment par temps chaud. La volatilité est plutôt

une mesure de la facilité de démarrage du moteur par temps froid.

Caractéristiques Butane Réformat Naphta Essence

Coût/tonne 7.3 18.2 12.5 ?

Indice d'octane 120 100 74 >=94

Tension de vapeur 60 2.6 4.5 <=11

Volatilité 105 3 12 >=17

On suppose que les intéractions entre ingrédients sont linéaires: par exemple un mélange

50-50 de butane et de réformat aura un indice d'octane 0.5*120+0.5*100=110. Cette

simpli�cation est exacte avec l'essence sans plomb: de légères non-linéarités existent

pour l'essence classique avec plomb.

On dispose de 800t de butane seulement, tandis que les autres ingrédients sont en

quantité supérieure à la capacité de production sur la période et sont donc virtuelle-

ment illimités. La ra�nerie fabrique aussi du fuel lourd sur les mêmes installations,

et la capacité totale de production est limitée à 12000t (essence+fuel). Le processus

de fabrication du fuel est �xé et n'intervient pas dans le problème d'optimisation qui

nous intéresse. On sait seulement que ce produit rapporte 2.5ε par tonne, coût des

ingrédients compris. L'essence rapporte par contre 18.4ε par tonne, mais le coût des

ingrédients n'est pas compris et doit être déduit.

L'objectif est de calculer les quantités d'ingrédients et d'essence à fabriquer de façon

à respecter les contraintes et à maximiser le pro�t total de la ra�nerie sur la période.

L'originalité du problème est qu'on ne connaît pas le coût de fabrication de l'essence,

car il va dépendre des proportions des divers ingrédients.

a). Modéliser.

b). Faite varier la quantité maximale de butane et le montant du béné�ce dû au fuel

et regarder quelles sont les variables serrées. Interpréter.

7

Chapter 2

Utilisation du logiciel Glpk

Glpk: GNU Linear Programming Kit

Glpk signi�e GNU Linear Programming Kit. Il s'agit d'un ensemble d'algorithmes

permettant de résoudre di�érents problèmes allant de la programmation linéaire (PL)

à la programmation linéaire en nombres entiers (PLNE).

Glpk est codé en langage C Ansi et on peut accéder directement aux algorithmes par

une API C (Application Program Interface), c'est-à-dire un ensemble de fonctions C.

Il est également possible d'accéder aux fonctionnalités de Glpk à partir d'un logiciel,

dit solveur, appelé glpsol. Glpk peut traiter des programmes linéaires fournis sous dif-

férents formats (lp, mps) ou décrits à partir d'un langage spécialisé, appelé modeleur,

le GNU MathProg.

Ce document résume les fonctionnalités principales du logiciel glpsol ainsi que les

formats principaux de données et de description. Pour obtenir des documents sur la

bibliothèque C API, installer le logiciel sous linux ou windows, avoir accés à une Faq,...

vous pouvez accéder à la page dédiée à glpk sur le site général GNU:

http://www.gnu.org/software/glpk/glpk.html.

Glpk est une partie du GNU Project et est distribuée en logiciel libre à sources

disponibles (free software, open source), sous la licence publique générale GNU qui

permet de la redistribuer ou de la modi�er selon les termes publiés par la Free Soft-

ware Foundation.

Algorithmes utilisés

Glpk résoud des programmes linéaires (PL) et des programmes linéaires en nombres

8

entiers (PLNE). Ces deux types de problèmes sont très proche en apparence mais de-

mandent à ce jour des traitements bien di�érents.

Résoudre un programme linéaire peut se faire en temps polynomial. Glpk propose les

2 plus célèbres algorithmes connus: la méthode du simplexe (qui n'est pas polynomiale

mais qui est très e�cace) et une méthode de points intérieurs (qui est polynomiale).

Résoudre un PLNE est un problème NP-di�cile. Glpk utilise le seul algorithme

connu capable de résoudre e�cacement tous les PLNE: la méthode de branchement

(Branch-and-Bound) qui est exponentielle dans le pire des cas.

L'interface API, le logiciel glpsol ou le modeleur GNU MathProg?

Il existe ainsi trois façons d'accéder aux algorithmes de Glpk. Tous les olveurs

linéaires similaires à Glpk possèdent ces 3 accès.

Si l'on désire une utilisation optimale, sécurisée, capable de fonctionner pour des

grandes tailles de problèmes, il faut utiliser bien entendu l'interface API. Elle existe à

l'origine en C Ansi mais on peut trouver des interfaces externes pour Java, Delphi ou

Glpkmex Matlab.

Pour résoudre des programmes de taille plus réduite, le logiciel glpsol est facile

d'utilisation. Il prend un �chier d'entrée sous des formats simples et produit un �chier

en retour contenant le résultat. Il est ainsi possible de créer un logiciel complet utilisant

glpsol, c'est-à-dire un programmant créant le �chier d'entrée pour glpsol et lisant son

�chier de sortie.

Parmi les �chiers d'entrée possible, le format modeleur peut être très utile. Un

modeleur décrit le PL ou le PLNE en utilisant une description mathématique assez

simple. Ce format de �chier peut ainsi être lu par glpsol ou par l'interface API.

Le logiciel glpsol

Si votre système Unix/Linux ou Windows est bien con�guré, la commande glpsol

(sous un terminal Unix/Linux ou sous une fenêtre Dos) vous permet d'accéder au logi-

ciel glpsol.

L'usage de glpsol est glpsol [options...] nomdefichier

Avec les options principales suivantes:

�help: permet d'accéder à la liste de toutes les options.

-check: ne lance pas d'algorithme, sert à tester les donées d'entrées

�cpxlp: format Cplex lp pour le �chier d'entrée PL ou PLNE nomdefichier

�mps: idem format mps,

�glp: idem format GNU lp

�math: idem format modeleur GNU MathProg.

�wcpxlp fichiersortie: écrit dans �chiersortie le PL ou le PLNE au format Cplex

LP (idem avec �wmps, �wglp)

9

-o fichiersortie: écrit dans �chiersortie l'ensemble des résultats dans un �chier �txt�

Il existe également des options spéci�ques aux algorithmes utilisés comme par exem-

ple le choix entre algorithme du simplexe et des points intérieurs, de la base intiale pour

la méthode de simplexe ou la stratégie de branchement dans le Branch-and-Bound.

Exemples:

glpsol �check �wmps entree.mps �cpxlp entree.lp: transfert du format .lp au

format .mps

glpsol -o solution.txt �cpxlp entree.lp: résoud entree.lp et donne la solution

dans sortie.txt

Format Cplex lp

Glpk peut donc lire di�érents formats d'entrée. Le plus simple et le plus répandu a été

créé pour le logiciel Cplex (Ilog). Il revient à écrire un PL ou un PLNE sous le format

habituel.Voici un petit exemple de programme linéaire sous le format Cplex lp.

\Problem name: exemple.lp

Maximize

obj: 5 x1 + 7 x2

Subject To

c1: 3 x1 - 2 x2 <= -9

c2: 10 x1 + 6 x2 >= 11

c3: 8 x1 + x2 = -6

Bounds

-Inf <= x1 <= 0

1 <= x2 <= 4

End

Cet exemple se passe de commentaires, mais il faut noter

que:

- la première ligne, optionnelle, indique un nom de problème

- les noms de la fonction obj ou des contraintes sont

optionnels

- les variables peuvent prendre des noms quelconques

- Si une variable n'a pas borne inférieure dans la section

Bounds, elle est considérée positive ou nulle.

Pour les PL mixtes ou entiers, on ajoute une section.

- Integers contenant la liste des variables entières

- Binary contenant la liste des variables binaires

Fichier de sortieGlpsol peut fournir en sortie un �chier .txt donnant la solution du PL ou du PLNE.Le tableau suivant est le �chier .txt correspondant au programme précédent. Il

indique le statut de la solution (optimale ou irréalisable) et la valeur de la fonctionobjective optimale. Dans le cas d'un PLNE, une valeur supplémentaire �nissant par(LP) est en fait la valeur du PLNE relaxée des contraintes d'intégrité. .

Problem:

Rows: 3

Columns: 2

Non-zeros: 6

Status: OPTIMAL10

Objective: obj = 21.75 (MAXimum)

No. Row name St Activity Lower bound Upper bound Marginal

------ ------------ -- ------------- ------------- ------------- -------------

1 c1 B -11.75 -9

2 c2 B 11.5 11

3 c3 NS -6 -6 = 0.625

No. Column name St Activity Lower bound Upper bound Marginal

------ ------------ -- ------------- ------------- ------------- -------------

1 x1 B -1.25 0

2 x2 NU 4 1 4 6.375

Les deux sections concernent les contraintes/lignes (Rows) et les variables/colonnes

(Columns), pour lesquelles sont indiquées:

No le numéro des contraintes et des variables

Row (Column) name le nom des contraintes et de variables

St: le statut de la ligne/colonne: B=en base (pour la variable ou la variable d'écart

associée à la contrainte), NF NL NU NS=Hors-base libre, à borne inf, à borne sup ou

valeur �xée.

Activity: Valeur d'activité de la ligne/colonne dans la solution: pour les lignes, c'est

la somme des variables fois leurs coe�cients et pour les variables, c'est leur valeur.

Lower/Upper bound: sans commentaire.

Marginal: pour les variables hors-base, c'est le coût réduit.

Le modeleur GNU MathProg

Le langage-modeleur GNU MathProg est une partie du langage AMPL. Il s'agit d'un

langage de description d'un PL sous un format assez naturel. En fait, ce format permet

de diviser un PL entre sa structure et ses données. Pour l'utiliser, glpsol nécessite ainsi

plusieurs options:

�math: pour indiquer que le �chier est dans ce format

�data fichierdata: indique le �chier des données

�display filename: redirige la sortie vers un �chier

Pour comprendre ce qu'est un modeleur, prenons le célèbre exemple de Dantzig

(1963): trouver le coût minimal de transport en respectant les demandes des clients

et de l'approvisionnement des usines. La description du problème dans un �chier de

format �modeleur� se comprend elle-même:

Fichier Transport_description.math11

set I;

/* I est l'ensemble des usines de production */

set J;

/* J est l'ensemble des clients */

param a{i in I};

/* a[i] est la capacité de production de l'usine i en nombre de caisses */

param b{j in J};

/* b[j] est la demande du client j en nombre de caisses */

param d{i in I, j in J};

/* d[i,j] est la distance en milliers de kilomètres entre une usine i et un client j */

param f;

/* f est le coût de transport en dollars par caisse et par milliers de kilomètre */

param c{i in I, j in J} := f * d[i,j] / 1000;

/* c[i,j] est le coût de transport en Kilo-dollars par caisse de l'usine i

au client j */

var x{i in I, j in J} >= 0;

/* x[i,j] est une variable de décision égale au nombre de caisses tranportées

de l'usine i vers le client j */

/* Si on veut les variables x entières, on écrit: var x{i in I, j in J} >= 0, integer; */

minimize cost: sum{i in I, j in J} c[i,j] * x[i,j];

/* Objectif: coût total de transport minimum en kilo-dollars */

s.t. CteCapacite{i in I}: sum{j in J} x[i,j] <= a[i];

/* Contrainte due à la capacité max de production de chaque usine i */

s.t. CteDemande{j in J}: sum{i in I} x[i,j] >= b[j];

/* Contrainte due à la demande de chaque client j */

Dans un deuxième �chier, on place les données de l'instance du problème. Notez

que les dimensions du problème ne sont pas données dans le �chier de description.

Fichier Transport_pbm_numero1.data

data;

set I := Seattle San-Diego;

set J := New-York Chicago Topeka;

12

param a := Seattle 350

San-Diego 600;

param b := New-York 325

Chicago 300

Topeka 275;

param d : New-York Chicago Topeka :=

Seattle 2.5 1.7 1.8

San-Diego 2.5 1.8 1.4 ;

param f := 90;

end;

En fait un même �chier de description produira autant de PL ou PLNE qu'il y a

de �chiers de données associés. Un �chier modeleur plus un �chier de données permet

aisni à glpsol de générer un PL ou un PLNE. On peut visualiser le résultat par exemple

en écrivant le PL ou PLNE au format Cplex lp avec

glpsol �check �wcpxlp Transport_pbm_numero1.lp

�data Transport_pbm_numero1.data.lp �math Transport_description.math

Ce langage est très riche, pour en maîtriser les �nesses, le �chier lang.ps, qui est

fourni avec les �chiers d'installation, contient une description complète du langage.

Mais cette génération par �chier de description reste néanmoins une étape potentielle-

ment coûteuse pour un problème de très grande taille et il est préférable d'utiliser

directement l'interface API dans ce cas.

13

Chapter 3

Interprétation économique

3.1 Interprétation du Théorème des Ecarts Complé-

mentaires

On utilise traditionnellement le problème de diététique suivant pour interpréter le

Théorème des écarts complémentaires:

Un diététicien joue un rôle de producteur en établissant quelle quantité de produit

vitaminé il doit acheter pour sa clinique. chaque aliment j, j = 1, ..., n possède les

aij unités de vitamine i, i = 1, ...,m. Il doit au total disposer au moins de bi unité

de chacune des vitamines i = 1, ...,m. Il veut minimiser ses dépenses z sachant que

chaque produit coûte ci euros, i = 1, ..., n.

Ce qui revient bien sûr à résoudre le PL suivant:

Minimiser z =n∑j=1

cjxj

n∑j=1

aijxj ≥ bi, ∀i ∈ {1, ...,m}

xj ≥ 0, ∀j ∈ {1, ..., n}

Plaçons-nous du côté du fournisseur, c'est-à-dire de celui qui produit les vitamines. Le

fournisseur veut déterminer le prix unitaire yi de chaque vitamine i, i = 1, ...,m. Il veut

�xer le prix des vitamines de manière à ce que le diétécien ait intérêt à se fournir chez

lui, c'est-à-dire à acheter les vitamines directement plutôt que des produits vitaminés.

Son objectif est donc de maximiser son prix de vente w des vitamines au diététicien

de façon à ce que, pour chaque produit vitaminée j, j = 1, ..., n, le prix∑m

i=1 aijyi des

vitamines contenant dans le produit j ne dépasse pas le prix cj de ses concurents.

14

Ce qui revient en fait à résoudre le dual du problème précédent:

Maximiser w =m∑i=1

bjyj

m∑i=1

aijyi ≤ cj, ∀j ∈ {1, ..., n}

yi ≤ 0, ∀i ∈ {1, ...,m}.

Ainsi, à l'optimum, on doit avoir z∗ = w∗ avec:

- Sin∑j=1

aijx∗j > bi, alors y

∗i = 0,

c'est-à-dire s'il y a un excès en vitamine i, le diététicien n'acceptera pas de payer un

prix y∗i > 0 pour l'avoir.

- Si y∗i > 0 alorsn∑j=1

aijx∗j = bi,

c'est-à-dire si le fournisseur �xe un prix unitaire de la vitamine i non nul, c'est que le

diététicien n'a pas d'éxédent de celle-ci.

- Si x∗j > 0 alorsm∑i=1

aijy∗i = cj,

c'est-à-dire si le diétécien achète du produit vitaminé j, c'est que le fournisseur a choisi

des prix y∗i tel que le prix des vitaminine le constituant n'est pas inférieur au prix

unitaire du produit.

- Sim∑i=1

aijy∗i < cj, alors x

∗j = 0,

c'est-à-dire si le prix unitaire contenu dans une unité de produit vitaminé j est inférieur

au prix unitaire cj du produit, le diététicien n'a pas intérêt à en acheter.

3.2 Interprétation des variables duales

Théorème: de post-optimisation

Suppossons que P admette une solution optimale x∗ non dégénérée de valeur z∗ et ainsi

qu'il existe y∗ la solution duale optimale associée.

Si le second membre b varie légérement de ∆b mais insu�semment pour que la base

optimale du problème P ne soit plus optimale, alors le problème dé�nit en remplaçant

b par b+ ∆b a pour valeur optimale z∆ = z∗ +∑n

i=1 ∆biy∗i .

Attention: Ce théorème ne s'applique que si la solution n'est pas dégénérée (i.e. véri-

�ant à l'égalité plus de n contraintes deP).

On considère à présent P comme un problème de production dont l'objectif est de

maximiser son pro�t. On doit décider le niveau de production xj de chaque produit xj15

de pro�t cj, j = 1, ..., n. Mais la production de chaque objet j nécessite aij unité de

matières premières i limitée en quantité bi, i = 1, ...,m.

Il serait intéressant de savoir l'e�et de petites variations positives sur l'o�re de ressources

supplémentaires de la ressource i sur le pro�t total de l'entreprise. Or pour chaque

unité supplémentaire de la ressource i, le pro�t augmente de y∗i . Les valeurs optimales

des variables duales correspondent alors au prix maximum que l'entreprise peut ac-

cepter d'acheter pour chaque unité de plus en ressource i. On nomme y∗i la valeur

marginale de la ième ressource.

3.3 Exemples d'interprétation économique

3.3.1 Economie sans tendresse...

Un pays désire accroître son potentiel d'armement; il veut acquérir au moins 100 000

fusils, 200 000 grenades défensives et o�ensives, une centaine de chars, 400 mitrailleuses

lourdes et autant de bazookas. Il s'adresse pour ce faire à des marchands d'armes qui

récupérent les matériels utilisés ou non sur tous les champs de bataille. Ces marchands

proposent 3 types de lots:

Lot1 Lot2 Lot3

fusils 500 300 800

grenades 1000 2000 1500

chars 10 20 15

mitrailleuses 100 80 150

bazookas 80 120 200

coûts des lots 1.5 Mε 1.8 Mε 2.3 Mε

Le pays en question va donc essayer de minimiser le coût de l'armement supplémen-

taire qu'il veut acheter.

A l'aide d'une modélisation du problème en un programme linéaire et en intérpré-

tant les résultats fournis par un solveur, donnez les interprétations économiques pour

le pays acheteur et, sans état d'âme, vous ferez de mêmes pour un éventuel fabriquants

d'armes désirant s'emparer du marché.

3.3.2 Machine-outils

Un atelier peut fabriquer trois types d'articles:

- l'article A à la cadence de 35 objets à l'heure

- l'article B à la cadence de 45 objets à l'heure

16

- l'article C à la cadence de 20 objets à l'heure

Cette fabrication utilise une machine-outil unique, disponible 200 heures par mois? Le

béné�ce unitaire pour l'article A est de 10 euros par objet, pour B de 6 euros, pour C

de 12 euros.

Ces objets sont vendus en totalité à des grossistes. On a observé que l'on ne pouvait

pas écouler par mois plus de 4900 objets de type A, ni plus de 5400 objets de type B,

ni plus de 2000 objets de type C.

D'autre part, chaque objet doit être véri�é avant sa commercialisation: une équipe

de trois techniciens est chargée de cette mission. Chaque technicien travaille 170 heures

par mois. La véri�cation d'un objet du type A prend quatre minutes, du type B trois

minutes et du type C deux minutes.

L'atelier veut organiser sa production de telle manière que son béné�ce soit maximum.

1) Formuler ce problème comme un programme linéaire.

2) Ecrire le dual ce de programme

3) Montrer que la solution optimale pour l'entreprise est de produire 4900 objets du

type A et 2700 objets du type B.

4) Chaque heure supplémentaire (par mois) sur la machine-outil cûte 230 euros. La

société a-t-elle intérêt à augmenter la capacité de la machine-outil? Si oui, de combien?

3.4 Programme linéaire paramétré

Résoudre le problème de programmation linéaire suivant :

max z = (6− 2p)x1 + (5 + p)x2

x1 + x2 ≤ 8

− 2x1 + 3x2 ≤ 6

x1 − x2 ≤ 2

xi ≥ 0, ∀ i ∈ {1, 2}

Ce problème peut être économique interprété comme le fait que la fonction coût

dépend d'un paramètre extérieur. Par exemple, on veut voir ici:

- la variable p comme le coût du pétrole

- le premier terme de la fonction objective comme les gains obtenus en livrant des

marchandises: ce gain diminue en fonction de l'augmentation du pétrole

- le deuxième terme de la fonction objective comme la facturation d'un transport réalisé

en sous-traitance par l'entreprise: on a ici pris en compte le prix du pétrole dans la

facturation.

- les variables de décision x1 et x2 correspondent aux quantité transporté en livraison

1 et 2.

Interprétez alors le graphique obtenue lors de l'étude précédente.17

Chapter 4

Etudes de cas

4.1 Aide à la décision dans une exploitation agricole

Les activités de notre exploitation agricole se divisent en deux grandes productions:

culture et élevage. Nous ne voulons pas toucher à notre production agricole mais nous

voulons pouvoir améliorer le rendement de notre activité d'élevage. La charge de travail

(main d'oeuvre) disponible pour l'élevage varie selon les saisons de la façon suivante:

Table 1

Mois Heures Mois Heures

Janvier 420 Juillet 380

Février 415 Août 395

Mars 355 Septembre 270

Avril 345 Octobre 230

Mai 160 Novembre 310

Juin 95 Décembre 420

On pratique 5 types d'élevage:

i). Elevage porçin de printemps.

ii). Elevage porçin d'automne.

iii). Elevage de bovins en batteries.

iv). Elevage de bovins en pâture.

v). Engraissage de bovins.

Dans les élevages porcins, les cochons naissent en février (printemps) ou en août (au-

tomne) et sont vendus à peu près 6 mois plus tard. Dans les élevages bovins, les veaux

sont achetés en octobre et sont vendus environ un an plus tard. La charge estimée de

travail peut se résumer ainsi:

18

Table 2 Temps de travail estimé

Types d'élevage

Mois i)∗ ii)∗ iii)+ iv)+ v)+

Janvier 1.4 1.8 1.5 1.4 1.4

Février 9.8 2.4 1.4 1.4 1.4

Mars 4.0 0.4 1.4 1.4 1.4

Avril 2.8 0.6 1.3 1.4 1.5

Mai 2.2 0.4 1.3 1.5 1.2

Juin 2.2 0.4 1.3 1.3 1.2

Juillet 2.2 0.6 1.3 1.3 1.2

Août 2.6 5.8 1.5 1.5 1.2

Septembre 0.6 4.0 1.3 - -

Octobre 0.6 1.2 1.3 1.3 2.6

Novembre 0.6 1.8 1.2 1.2 1.2

Décembre 0.6 1.8 1.5 1.4 1.4∗ heures par portée+ heures par vache

En plus de la charge de travail, chacun de ses 5 élevages nécessite une certaine quantité

de nourriture produite par la ferme: soit en laissant les bêtes en pâture, soit en leur

apportant des produits récoltés et stockés que l'on appelle communément �nourriture

stockée� (fourrage, herbe, pomme de terre,...). La pâture se mesure en unités appelées

�jour de pâture�: c'est la quantité d'herbe mangée par jour par un cheval adulte ou

une vache ne recevant pas d'autre nourriture. Les pâturages sont disponibles d'avril à

septembre, durant cette période, il est aussi possible de remplacer la pâture par de la

nourriture stockée. La disponibilité des pâturages est indiquée ici avec la demande de

pâture pour chacun des 5 élevages.

Table 3 Besoin en pâture

Besoin(j.pâture/unité)

Période i) ii) iii) iv) v) Disponilité

Avril et Mai 16 0 0 12 35 5200

Juin et juillet 20 0 0 36 50 5200

Aoüt et Septembre 16 0 0 12 35 3600

Total 52 0 0 60 120 14000

La pâture peut être convertie en nourriture stockée avec un temps de travail de 5.5

heures et 50 jours de pâture par tonne de nourriture stockée. A part pour l'élevage

porçin de printemps, les élevages nécessitent l'utilisation du stock de nourriture dans

les saisons sans pâturage disponible. La demande total en nourriture stockée est:

0.1 tonnes par portée de porcelets,

0.9 tonnes par bovin nourri au fourrage,

0.8 tonnes par bovin nourri en pâture,

2.3 tonnes par bovin engraissé.19

Finallement, voici les revenus estimés des cinq élevages:

i). 139ε par portée de porcelets,

ii). 88ε par portée de porcelets,

iii). 133ε par bovins,

iv). 137ε par bovins,

v). 165ε par bovins.

L'objectif est bien entendu de plani�er l'élevage le plus rentable. Néanmoins, toutes les

données peuvent être remises en questions car ce ne sont que des approximations que

l'on peut diminuer ou augmenter sans trahir la réalité. Au lieu de prévoir une durée de

95 heures de travail en juin, on peut tout à fait prévoir une durée de 97 heures ou 92

heures. Une plani�cation demandant de travailler 92 ou 97 heures au moins de juin est

parfaitement admissible. Cette même incertitude s'applique aussi au calcul du pro�t

qui �uctue d'une année à l'autre en fonction du marché.

Vous pourrez discuter avec les responsables de cette exploitation agricole en posant des

questions précises mais vous devrez leur rendre le rapport rédigé de vos propositions.

Attention, en cas d'insatisfaction des responsables, vous ne serez pas payés.

4.2 Aide à la décision dans une exploitation forestière

New Forest est un domaine composé de forêts et de plaines situé en Hampshire en

Angleterre. Donc nous allons compter en livres et mesurer le cubage du bois en Hoppus

feet (Un Hoppus feet (h.ft.) est un volume d'un foot carré sur un inch de haut, c'est-

à-dire en sachant qu'un pied fait 30,48 cm, un pouce un 36ème de yard et qu'un yard

fait trois pieds, cela fait un quart de stère). Les responsables de New Forest doivent

décider un programme d'abattage sur une surface d'environ 30 000 acres (une acre est

environ un demi-hectare) avec pour objectif d'optimiser les revenus sur les dix ans à

venir. Le problème considéré ici concerne seulement une zone de 8 500 acres avec 6

types de bois, comme montré en table 1.

Table 1 Types de bois

Vol. si abatt.

Type Description Acres (h.ft/acre)

1 Feuillus hauts 2 754 2 000

2 Feuillus moyens 850 1 200

3 Feuillus bas 855 700

4 Résineux hauts 1 598 4 000

5 Mixtes hauts 405 2 500

6 Plaines 1 761

Les bois de feuillus sont en plus divisés entre ceux qui ont un sous-bois complet, ceux

qui ont un sous-bois partiel et ceux sans sous-bois. Les surfaces correspondantes sont

inscrites dans la table 2.20

Table 2 Classi�cation des feuillus

Sous-bois

complet partiel nul total

Feuillus hauts 357 500 1 897 2 754

Feuillus moyens 197 130 523 850

Feuillus bas 39 170 646 855

Toute étendue de tous types de bois peut recevoir l'un des deux traitements basiques

suivant: abattre et planter des résineux (traitement 1A) ou abattre et planter des

feuillus (traitement 1B). Appliqués à une plaine, ces traitements deviennent �planter

des résineux� et �planter des feuillus�. De plus, pour les bois de feuillus avec un sous-bois

complet, les responsables ont l'option d'abattre et conserver le sous-bois (traitement

2). Similairement pour les bois de feuillus avec sous-bois partiel, ils peuvent abattre

et enrichir le sous-bois (traitement 3). Une dernière possibilité consiste à reporter sine

die le traitement d'une surface d'un bois quelconque.

Le revenu sur les 10 prochaines années varie selon les traitements et les types de bois.

Ces cas de �gures en livres par acre, sont estimés en table 3.

Table 3 Revenus estimés (£./acre)Traitement

Type 1A 1B 2 3 Auc.

1 287 215 228 292 204

2 207 135 148 212 148

3 157 85 98 162 112

4 487 415 371

5 337 265 264

6 87 15 61

Les exigences gouvernementales (dues à des raisons esthétiques) et les limitations de

capacité de production impliquent les quatre conditions suivantes: les zones traitées ne

doivent pas dépasser 5 000 acres, la surface totale de résineux 3 845 acres, le volume

de feuillus abattus 2,44 millions de h.ft. et le volume de résineux et de forêts mixtes

hautes abattues 4,16 millions de h.ft.

Les volumes moyens estimés par acre de chacun des types de bois sont listés dans la

première table.

Les responsables de New Forest demandent l'intervention de spécialistes de l'aide à la

décision pour répondre à leur problème. Ils veulent connaître une ou plusieurs solutions

possibles à cette énoncé exacte mais attendent aussi une ré�exion sur les données qui

peuvent être éventuellemement modi�ées (dans tous les domaines: super�cie, limitation

o�cielle,...) dans l'esprit d'une utilisation rentable mais raisonnée de la forêt. Par

exemple, ils s'interrogent sur l'application d'une réglementation qui obligerait à planter

au moins 500 acres de feuillus, mais aussi ils exigent une explication économique de ce

que vous recommendez, proposez à leur choix ou déconseillez.21

Vous pourrez discuter avec les responsables de New Forest en posant des questions

précises mais vous devrez leur rendre le rapport rédigé de vos propositions. Attention,

en cas d'insatisfaction des responsables, vous ne serez pas payés.

22

Chapter 5

Projet: Jeu de l'arbre de poids

minimum

5.1 Organisation du projet

• Le travail se fait par monôme ou binôme.

•N'hésitez pas à poser des questions lors des séances ou par mail à Pierre.Fouilhoux@lip6.fr.

• Le logiciel glpk est disponible dans vos salles de TP. Pour cela, utiliser les com-

mandes suivantes créées par Maurice Diamantini pour les TP de RO:

use diam

usediam ro

Véri�er que le solveur glpsol est accessible en tapant :

glpsol --help

Il est aussi facile à installer sur les distributions linux, mac ou windows.

Il y a deux façons principales d'utiliser ce logiciel: soit avec une API, soit en utilisant

des �chiers d'entrée et de sortie.

• Vous rédigerez un petit rapport contenant la description de votre travail, c'est-à-

dire l'analyse du problème, les formulations et les réponses aux di�érentes questions.

Il doit clairement comporter une réponse aux questions posées dans les parties précé-

dentes et tout particulièrement l'analyse théorique. Vous pouvez sauter les questions

pour lesquelles vous n'avez pas de réponses.

23

• Le mot rapport doit apparaître dans le nom du �chier soumis par mail en n'oubliant

pas de noter en première page les participants du binôme. Il doit être dans un format

lisible en PDF. Votre livraison doit être constituée d'une archive (�chier tgz (par tar

cvzf nomRepertoire.tgz nomRepertoire).

Envoyez ce �chier en pièce attachée d'un courrier électronique ayant pour sujet Projet

MAE41 et adressé à Pierre.Fouilhoux@lip6.fr.

• Le 10/05/11 la matinée est consacrée au rendu de projet. Nous établirons un emploi

de temps de passage a�n que chaque projet soit présenté rapidement: fonctionnement,

capacité, questions diverses. Merci de venir avec votre rapport imprimé.

5.2 Première partie: une répartition stable

5.2.1 Dé�nition du problème

On considère ici un ensemble N de clients distincts caractérisés par leur coordon-

nées (distinctes) dans un plan représentant une zone géographique (par exemple une

campagne isolée). Cette zone géographique contient un point 0 correspondant à un bâ-

timent passerelle relié au réseau extérieur. Les clients désirent être réliés à la passerelle

0 par un réseau de télécommunications a�n d'être reliés au réseau extérieur.

On note d(ij) la distance euclidienne entre deux clients i et j de N . Comme le coût

permettant de relier les points i et j est proportionnel à d(ij), on va considérer ici que ce

coût est directement d(ij). On peut ainsi dé�nir un graphe complet G = (N ∪ {0}, E)

valués par les distances d(ij) pour tout i, j ∈ N ∪ {0}.On note ici ij une arête de G. On note également P = (s1s2, s2s3, ...sk−1sk) un

chemin de G. Un cycle est un chemin tel que s1 = sk. On rappelle qu'un graphe est

connexe s'il existe un chemin reliant toute paire de sommets. Un arbre est un sous-

graphe connexe sans-cycle. Pour un ensemble S ⊆ N ∪ {0} de sommets, on appelle

arbre couvrant un arbre reliant tous les sommets de S. On rappelle qu'un arbre cou-

vrant k sommets possèdent exactement k − 1 arêtes. Il est bien connu que l'on peut

déterminer un arbre de poids minimum en temps polynomial (algorithme de Prim ou

de Kruskall).

Pour un ensemble S ⊆ N de clients, le réseau le moins onéreux est l'arbre de poids

minimum de G couvrant les sommets S ∪ {0} (en e�et, il s'agit du plus petit graphe

connexe couvrant tous les sommets). Si une coalition S ⊆ N de clients décident de

coopérer pour construire leur propre réseau, on note alors ΓS = (S ∪{0}, ES) un arbre

de poids minimum couvrant {0}∪S et on note v(S) =∑

ij∈ESd(ij) le coût de cet arbre.

Considérons un arbre ΓN = (N ∪{0}, EN) reliant tous les clients de N au sommet 0:24

cet arbre constitue donc le réseau de télécommunications le moins onéreux pour relier

les clients de manière à ce qu'aucune coalition S ( N n'ait intérêt à se former pour

construire un arbre couvrant ΓS concurrent. Pour cela, on doit répartir le coût v(N)

sur les n clients.

On appelle ainsi jeu de l'arbre de poids minimum le problème consistant à étudier les

répartitions possibles du coût v(N) de ΓN sur tous les clients N .

Ce jeu est motivé par deux interprétations complémentaires du problème:

- interprétation coopérative: globalement les n clients ont intérêt à coopérer tous ensem-

ble: un réseau global coûtera moins que plusieurs sous-réseaux (et l'impact écologique

sera aussi moindre). Mais pour atteindre cette solution, il faut être certain qu'aucun

client ne sera mécontent et préfèrera faire un autre réseau. La solution est alors de

répartir les coûts inégalitairement de manière à ce que ceux qui auraient le plus de

raisons de ne pas coopérer soient ceux qui payent le moins.

- interprétation concurrentielle: une autre interprétation plus �réaliste� est le cas où

un opérateur télécom désire construire un réseau et proposer une répartition de son

coût à ses futurs clients. Son objectif est donc de répartir le coût de manière à ce

qu'aucun concurrent n'ait la possibilité de construire un réseau concurrent en coalisant

une partie des clients potentiels.

5.2.2 Coalitions et répartitions

Soit N l'ensemble des n joueurs. Il y a donc 2n−1 coalitions possibles dans ce jeu. On

note v(S) la valeur obtenue par la coalition S ⊆ N et on appelle alors v la fonction

caractéristique: on se place, pour ce projet, dans le cas où v(S) correspond à un coût

que doit payer la coalition de tous les joueurs de S.

On suppose souvent que v est sous-additive, c'est-à-dire que

v(S ∪ T ) ≤ v(S) + v(T ) ∀S, T ⊂ N tels que S ∩ T = ∅.

Ainsi, les joueurs ont intérêt globalement à coopérer. En e�et, si les joueurs se ré-

partissaient entre S1, ..., Sk coalitions, alors le coût v(N) de la coopération de tous les

joueurs serait inférieur à la somme v(S1) + v(S2) + ...+ v(Sk) des coûts des coalitions.

On appelle parfois ce type de jeu, un jeu conditionnel et ici l'objectif est de �per-

mettre� la coopération N de tous les joueurs, c'est-à-dire répartir le coût à payer par

la coopération N de façon à ce qu'il y ait le moins de joueurs mécontents, voir aucun

joueur mécontent si cela est possible.

25

Pour cela, on doit décider d'une répartition du coût total v(N) de la coopération

entre tous les joueurs. On note xi, i ∈ N , la répartition du coût v(N) sur le joueur i,

c'est-à-dire ∑i∈N

xi = V (N) et xi ≥ 0 ∀i ∈ N.

5.2.3 Répartition stable

Une répartition x correspond à une coopération stable si et seulement si∑i∈S

xi ≤ v(S) ∀S ⊂ N.

On appelle c÷ur du jeu l'ensemble des répartitions menant à des coopérations sta-

bles. Le c÷ur de certains jeux est parfois vide. Lorsqu'il n'est pas vide, il contient en

général un très grand nombre de répartitions possibles.

Il a été montré que lorsque le c÷ur est non vide, alors le nucléolus est dans le c÷ur.

Dans le cas particulier d'une répartition du c÷ur du jeu, l'excès est bien-entendu positif.

5.2.4 Questions théoriques

On désire dans cette partie construire une première solution stable pour le problème

du jeu de l'arbre de poids minimum. Pour cela, montrer les résultats suivants.

Q.1 La fonction caractéristique v associée au jeu de l'arbre couvrant est sous-additive.

Q.2 Soit ΓN un arbre de poids minimum couvrant les sommets {0} ∪ S. On note ei

l'arête issue de i dans l'unique chemin reliant i à 0 dans ΓN . On considère alors le

vecteur x ∈ IRn où xi = d(ei). On peut montrer que x est une répartition.

Q.3 On veut prouver que x appartient au c÷ur du jeu. Pour cela, prenons S ⊂ N et

considérons l'arbre de poids minimum ΓS = (S ∪ {0}, ES). On veut donc prouver que∑i∈S xi ≤ v(S) =

∑e∈ES

d(e).

Posons ξ = {ei/i ∈ S} et ξ = EN \ ξ.a) v(N) =

∑i∈S xi +

∑e∈ξ d(e).

b) ES ∩ ξ = ∅.c) Considérons alors le graphe HS = (N ∪ {0}, ES ∪ ξ). Alors |ES ∪ ξ| = n.

d) On peut montrer que Hs est connexe. (Indication, montrer qu'il existe un chemin

de i à 0 dans HS pour tout i ∈ N).

e) On rappelle qu'un graphe connexe connexe sur n+ 1 sommets possédant n arête26

est un arbre. On peut en déduire que x est dans le c÷ur du jeu.

5.2.5 Questions pratiques

Nous allons déterminer un réseau optimal et, en nous appuyant sur les questions précé-

dentes, une première répartition stable de son coût.

• Choisir une structure de données pour coder le graphe (nous n'allons pas manipuler

de très grandes instances). On peut remarquer que le graphe est complet et que le

poids des arêtes se déduit des coordonnées en calculant la distance euclidienne.

• Le site http://comopt.i�.uni-heidelberg.de/software/TSPLIB95/ contient des instances

pour le problème dit du voyageur de commerce. Ces instances sont très utilisées pour

les tests pratiques de problèmes de télécommunications. En e�et, ces instances provi-

ennent de données réelles de plusieurs opérateurs et correspondent souvent à des zones

géographiques précises.

Nous allons considérer les instances �TSP data� du problème symétrique qui sont en

fait données selon un format simple (en�n la plupart, faire attention): un nuage de

points d'un plan dont les coordonnées sont données en liste.

Ajouter à votre structure une fonction permettant de lire ces instances.

• A partir de l'instance précédente, nous allons construire des instances pour notre

problème. Pour cela, pour un n donné en paramètre, nous allons choisir n + 1 points

dont l'un d'entre eux sera notre sommet 0. Donner plusieurs fonctions de génération

d'instances: une totalement sera totalement aléatoire, les autres ont pour but de fournir

des instances de structures particulières.

Pour ces instances, nous allons prendre un coût d'installation d'une liaison égal au coût

de la distance euclidienne.

• Ajouter à votre structure la visualisation du nuage de points correspondant aux

instances. Vous pouvez pour cela utiliser le logiciel de dessin x�g. Voir l'exemple

ExCfig.cpp sur la page http://www-desir.lip6.fr/∼fouilhoux/documentens.php (com-

mentaire dans le document pdf associé).

• Coder l'algorithme de Prim a�n d'obtenir un arbre couvrant de poids minimum.

En déduire une répartition stable du coût de l'arbre. Attention: dans l'objectif de la

deuxième partie du projet, il est nécessaire de coder cet algorithme de manière à pouvoir

obtenir un arbre couvrant les sommets S ∪ 0 où S est un sous-ensemble quelconque de

27

sommets-clients.

Algorithme de Prim

Notons F un ensemble d'arêtes initialisé à vide.

Notons B un ensemble de sommets initialisé à vide.

B ← {0}Tant que B 6= S ∪ {0} Faire

Déterminer l'arête e de plus petit poids parmi les arêtes sortantes de B

F ← F ∪ {e}Ajouter l'extrémité sortante de e à B

Fin Tant que

A la �n (S ∪ {0}, F ) est un arbre de poids minimum couvrant S ∪ {0}

• Ajouter une visualisation graphique de l'arbre obtenue.

5.3 Deuxième partie: une répartition équitable

Lorsqu'il existe une solution stable (i.e. coeur non vide), on peut consider que déter-

miner une solution stable su�t à permettre la coopération en répartissant les coûts de

manière à ne pas mécontenter les joueurs. Néanmoins, certaines solutions du c÷ur sont

fortement inégalitaires, nous cherchons une solution du c÷ur qui soit équitable entre

les écarts de coûts entre les clients.

5.3.1 Répartition équitable

En théorie des jeux, un jeu modélise les comportements d'acteurs économiques devant

décider d'une stratégie face à un même problème (économique) alors que leurs béné�ces

individuels dépendent des choix de tous. Les jeux permettent de modéliser et d'étudier

di�érents modèles: modèles économiques de concurrence entre entreprises, stratégie de

joueurs dans un jeu d'argent, évolution d'une population animale proies-prédateurs,

etc. On nomme ainsi joueurs les acteurs d'un jeu.

Certains choix de stratégies individuelles des joueurs permettent d'atteindre des sit-

uations stables, c'est-à-dire des situations du jeu où aucun des joueurs n'a intérêt à

changer de stratégie individuelle. Dans certains jeux, il a été montré que ces situations

stables existent. Plus globalement, que des situations stables existent ou non, il est

intéressant de rechercher des solutions où les joueurs sont le moins mécontents.

On s'intéresse ici à un jeu coopératif où les joueurs peuvent se concerter et s'engager

à coopérer a�n de dé�nir leurs stratégies individuelles, créant ainsi une stratégie com-

mune. On appelle ainsi coalition le fait que plusieurs joueurs se regroupent pour28

coopérer ensemble. La coalition de tous les joueurs, que l'on appelle coopération, est

ainsi stable s'il n'existe pas de sous-coalition qui aurait intérêt à se mettre à part des

autres.

Nous allons nous intéresser ici à déterminer une coopération qui mécontente le moins

les joueurs pour le problème du jeu de l'arbre de poids minimum.

5.3.2 Egalité et équité

Une répartition égalitaire serait bien entendu xi = v(N)n

pour tous les joueurs i ∈ N .

Malheureusement, une solution égalitaire peut mécontenter certains joueurs. Ils peu-

vent préférer se rassembler en une coalition partielle et ne pas participer à la coopéra-

tion. On va plutôt rechercher des répartitions équitables, c'est-à-dire répartir de façon

à tenir compte du cas particulier de chaque individu, ce que l'on appelle parfois le

�mérite� de chaque joueur.

Pour cela, dé�nissons la notion d'équité dans le cadre d'un problème d'optimisation

combinatoire multi-agent. On considère ici un problème à q agents dont les solutions

σ = (σ1, ..., σq) dont la qième composante représente la solution σ pour l'agent i et on

note f(σi) le coût de cette solution. Ainsi, la comparaison des solutions se ramène à la

comparaison de leurs coûts. Il existe plusieurs façon de dé�nir l'équité pour comparer

si une solution σ est plus équitable qu'une solution σ′.

Un des plus simples est de rechercher une solution minimax, c'est-à-dire une solution

telle que:

min{ maxj=1,...,q

f(σj) | σ est solution}.

Plus généralement, on peut dé�nir un ordre lexicographique minmax qui se dé�nit

ainsi:

Pour une solution σ, on note Θ(σ) le vecteur de IRq obtenu en classant les q valeurs

f(σ)) dans l'ordre décroissant.

Soient k ∈ {1, ..., q} et deux solutions σ et σ′, on dit que

σ �k σ′ si Θi(σ) = Θi(σ

′) ∀i = 1, ..., k − 1

et Θk(σ) < Θk(σ′).

Soient deux répartitions σ et σ′, on dit que

σ � σ′ s'il existe k ∈ {1, ..., q} tel que σ �k σ′.

On peut alors considérer un élément (ou un ensemble d'éléments) qui soit minimum

selon l'ordre lexicographique minmax. Ce minimum peut-être alors considérer comme29

équitable.

Néanmoins, cette dé�nition de l'équité n'est pas unique. De plus, celle-ci est critiquée

(car elle ne prend pas en compte qu'il ne peut y avoir de �compensation� entre les

agents).

5.3.3 Excès

On désire appliquer la notion d'équité vu précédemment à notre problème où les agents

seront en fait les coalitions. Pour cela, nous dé�nissons les notions suivantes.

Soit x une répartition (quelconque) du coût v(N). On appelle excès1 de x, la fonction

ex(S) =∑i∈S

xi − v(S) ∀S ⊆ N.

Cette fonction excès représente la di�érence de coût que la coalition S paye réellement

dans la répartition x (i.e.∑

i∈S xi et ce qu'elle aurait à payer si elle était seule (i.e.

v(S)). Plus cette di�érence est faible moins les clients sont insatisfait et on la tentation

d'aller dans la coalition.

On peut remarquer que les excès sont souvent très inégalitaires entre les clients.

Pour déterminer une meilleure solution, on applique le principe de l'ordre lexi-

cographique minmax à nos coalitions. Pour cela, on introduit plusieurs relations d'ordre

qui vont donner un ordre lexicographique � entre deux répartitions.

Pour une répartition x, on note Θ(x) le vecteur de IR2n−1 obtenu en classant les

2n − 1 valeurs ex(S), S ⊆ N , S 6= ∅, dans l'ordre décroissant.Soient k ∈ {1, ..., 2n − 1} et deux répartitions x et y, on dit que

x�k y si Θi(x) = Θi(y) ∀i = 1, ..., k − 1

et Θk(x) < Θk(y).

Soient deux répartitions x et y, on dit que

x� y s'il existe k ∈ {1, ..., 2n − 1} tel que x�k y.

Exemple: Pour N limité à trois joueurs, on considère donc les coalitions

{1},{2}, {3},{1, 2},{1, 3}, {2, 3} et {1, 2, 3}.Supposons que v soit la fonction:

v({1}) = 1, v({2}) = 2, v({3}) = 2, v({1, 2}) = 3, v({1, 3}) = 3, v({2, 3}) = 4 et

1Pour un jeu qui considère des coûts

30

v({1, 2, 3}) = 4.

Considérons les deux répartitions x = (1, 2, 1) et y = (1, 1.5, 1.5) qui sont toutes deux

dans le c÷ur.

On obtient l'ordonnancement suivant des partitions:

x({1}) = 1, x({2}) = 2, x({3}) = 1, x({1, 2}) = 3, x({1, 3}) = 2, x({2, 3}) = 3 et

x({1, 2, 3}) = 4

et y({1}) = 1, y({2}) = 1.5, y({3}) = 1.5, y({1, 2}) = 2.5, y({1, 3}) = 2, y({2, 3}) = 3

et y({1, 2, 3}) = 4.

Et donc

Θ(x) = (1, 1, 1, 0, 0, 0, 0) et Θ(y) = (1, 1, 0.5, 0.5, 0.5, 0, 0).

On voit que y �3 x et donc y � x d'après la dé�nition.

On s'intéresse ici aux éléments x∗ qui minimisent l'ordre lexicographique �. On

appelle l'ensemble de ces éléments le nucléolus.

5.3.4 Questions théoriques

Prouver les a�rmations suivantes où l'on applique les dé�nitions précédentes au cas

du jeu de l'arbre couvrant:

Q.1

Θ(x)[1] représente la plus grande valeur d'excès pour une coalition S de N .

Lemme ??.2 On considère le programme linéaire P1 suivant:

P1

Min r ∑i∈N

xi = v(N), (1)∑i∈S

xi ≤ v(S) ∀S ( N, (2)∑i∈S

xi + r ≥ v(S) ∀S ( N, (3)

xi ≥ 0 ∀i ∈ N,r ≥ 0.

a) On peut montrer que les solutions du programme linéaire P1 correspondent à des

répartitions.

b) P1 possède toujours une solution optimale (x1, r1).

c) Soit y une solution et posons ry = Θ(y)[1]. Alors (y, ry) est solution de P [1].

31

d) x1 minimise �1.

Q.3 On note ζ1 l'ensemble des coalitions S pour lesquelles les inégalités (2) sont véri�ées

à l'égalité par la solution (x1, r1). Si ζ1 6= ∅, on construit alors le programme linéaire

Pk suivant pour k = 2

Pk

Min r ∑i∈N

xi = v(N), (1)∑i∈S

xi ≤ v(S) ∀S ( N, (2)

∑i∈S

xi + r ≥ v(S) ∀S ⊂ 2N \

(k−1⋃l=1

ζl

), (3)∑

i∈S

xi = v(S)− rk ∀S ⊂ ζl ∀l = 1, ..., k − 1, (4)

xi ≥ 0 ∀i ∈ N,r ≥ 0.

En fait, on va dé�nir itérativement le programme Pk+1 à partir de la solution du pro-

gramme Pk en posant (xk, rk) la solution optimale de Pk et ζk l'ensemble des coalitionspour lesqueles lles inégalités (3) sont véri�ées à l'égalité par la solution (xk, rk). En

fait, P(k + 1) existe si P(k) admet bien une solution et si ζk 6= ∅.a) On prouve que Pk admet une solution avec rk > 0, alors ζk 6= ∅.b) On montre que si Pk admet une solution avec rk > 0, alors Pk+1 admet une

solution optimale.

Q.4 Soit k ≥ 1 tel que Pk existe. En fonction des ζk, on peut donner l'expression du

plus grand entier i tel que xk minimise �i.

Q.5 On considère l'algorithme (dit de Kopelowitz) où l'on construit itérativement le

programme Pk+1 à partir du programme Pk tant qu'il existe dans Pk des contraintes

(3). On montre qu'à la �n des itérations, on obtient x∗ qui minimise l'ordre �.

Q.6 Donner le nombre maximal d'itérations de l'algorithme. Peut-on s'attendre à ce

que le pire des cas soit toujours atteint?

Q.7 Proposer des tests d'arrêt pour cet algorithme.

32

5.3.5 Questions pratiques

Une mise en ÷uvre simple de ce projet est de concevoir un programme qui écrit

sur le disque un �chier d'entrée au format lp (ce format reprend exactement la de-

scription du programme linéaire dans son ecriture classique). Ensuite, on peut lire

la solution optimale obtenue dans un �chier de sortie et réinjecter �à la main� les

valeurs dans le programme linéaire initiale a�n d'améliorer la solution. Une telle so-

lution est esquissée sur l'exemple �Horaire aérien� proposé sur la pagehttp://www-

desir.lip6.fr/∼fouilhoux/documentens.php.

Une mise en ÷uvre plus élaborée consiste à automatiser ce processus de manière à ce

que ce soit votre programme qui aille lire le �chier et modi�e le �chier .lp en fonction

de manière à réitérer le processus.

Une mise en ÷uvre très élaborée consiste à utiliser l'API de glpk pour réaliser toutes

ces opérations.

Le travail demandé pour ce projet se limite aux points suivants:

• Construction du programme linéaire P1.

La di�culté essentielle de cette mise en ÷uvre repose sur la nécessité d'énumérer cor-

rectement les coalitions possibles. Leur nombre limite d'ailleurs la taille des instances

que l'on peut résoudre par ce biais.

Vous devez proposez une façon de numéroter/énumérer les coalitions et construire le

programme correspondant.

• Itérations de l'algorithme

Proposer quelques itérations de l'algorithme de Kapelowitz, faite à la main, sur des

exemples de petites tailles.

• Observer l'évolution des répartitions obtenus sur diverses structures d'instances.

• Evaluer jusqu'à quelle taille vous pouvez utiliser l'algorithme.

33

Chapter 6

Annexe: Programmation Linéaire

6.1 Dé�nitions

6.1.1 Dé�nitions

Dé�nition Un Programme Linéaire, noté PL, est un problème P- où l'on recherche à maximiser ou minimiser une fonction linéaire, dite fonction objec-

tive ou objectif,

- dont les variables prennent des valeurs réelles,

- en respectant des égalités ou des inégalités linéaires, appelées contraintes.

Un programme linéaire peut toujours s'écrire:

Max cx

Ax ≤ b

x ≥ 0

où A est une matrice m× n, b ∈ IRn, c ∈ IRm et x ∈ IRm.

Un vecteur x véri�ant les contraintes d'un PL est dit solution ou solution réalisable du

PL.

L'ensemble des solutions d'un PL forme sous domaine de dé�nition. Ce domaine est

un polyèdre.

Le domaine de dé�nition d'un PL peut être:

- vide. Dans ce cas, le problème n'admet pas de solutions,

- tel que la direction donnée par la fonction objective ne rencontre pas d'hyperplan

formé par une contrainte de PL (donc le domaine est non bornée). Alors le problème

n'admet pas de solutions.

- dans les cas restants, le problème admet une ou plusieurs solutions de coût maximal

par rapport à l'objectif. On dit que ces solutions sont optimales.34

6.2 Résolution d'un Programme Linéaire

6.2.1 Résultats principaux

Un problème linéaire peut être résolu en temps polynomial (Khachiyan 1979). En e�et,

il existe des algorithmes polynomiaux pour résoudre un programme linéaire.

Jusqu'en 1979, on ignore justement si la Programmation Linéaire est un problème di�-

cile ou non. On connaît simplement l'algorithme du simplexe qui n'est pas polynomial

(Dantzig, 1947).

L'algorithme du simplexe repose sur le fait qu'une solution optimale d'un programme

linéaire peut être prise parmi les sommets du polyèdre formé par le domaine de dé�ni-

tions. Ceci transforme donc la Programmation Linéaire qui est un problème continue

en un problème discret.

A la suite de Karmarkar (1984), de nouveaux algorithmes polynomiaux, dits de points

intérieurs, arrivent à battre en vitesse l'algorithme du simplexe pour les problèmes de

très grande taille. Néanmoins, l'algorithme du simplexe reste l'algorithme connu le

plus performant pour les tailles classiques, bien qu'il ne soit pas polynomial!

6.2.2 Algorithme du simplexe: cadre général

6.2.3 Forme standard et variables d'écart

Un PL peut toujours d'écrire selon sa forme standard

Max cx

Ax = b

x ≥ 0

Par exemple, à partir d'une contrainte de la forme

n∑j=1

aijxi ≤ bi

on peut écriren∑j=1

aijxi + xn+i = bi

en ajoutant une variable supplémentaire indicée n + i où i est le numéro de la con-

trainte. Cette variable n'apparaît pas dans la fonction objective et prend des valeurs

positives.

35

Par exemple:

max z = 4x1 +5x2

2x1 +x2 ≤ 8

x1 +2x2 ≤ 7

x2 ≤ 3

xi ≥ 0, i ∈ {1, 2}

max z = 4x1 +5x2

2x1 +x2 +x3 = 8

x1 +2x2 +x4 = 7

x2 +x5 = 3

xi ≥ 0, i ∈ {1, .., 5}

6.2.4 Base réalisable et solutions associées

On appelle variables de base m variables, parmi les n + m d'une forme standard, qui

peuvent êcrites en fonctions des n autres variables. Ces variables forment alors une

base du PL, les autres variables sont dites Hors-Base (HB).

On associe à une base une solution du PL en �xant les variables Hors-Base à 0. Un

base est dite réalisable si sa solution associée est réalisable pour le PL.

On peut facilement véri�er qu'une telle solution est réalisable: il su�t de véri�er que

toutes ses valeurs sont positives ou nulles!

Par exemple, les variables d'écart forme toujours une base:

x3 = 8 −2x1 −x2

x4 = 7 −x1 −2x2

x5 = 3 −x2

et, dans ce cas précis, cette solution est admissible (ce n'est pas toujours le cas).

Il est très facile de savoir si la solution associée à une base admissible est optimale

pour le PL. Pour cela, il su�t de réécrire la fonction objective en fonction des variables

Hors-Base:

Cas maximisation: si les coe�cients obtenus sont tous négatifs, alors la solution asso-

ciée est optimale.

Cas minimisation: si les coe�cients obtenus sont tous positifs, alors la solution associée

est optimale.

En e�et, dans le cas maximisation par exemple, la seule façon d'avoir une meilleure

solution serait de baisser la valeur des variables Hors-Base. Or ces variables sont déjà

�xées à leur minimum, c'est-à-dire 0.

Dans notre exemple, on a z = 4x1 + 5x2, ce qui n'est pas un cas d'optimalité.

36

Description de l'algorithme du simplexe

En fait, l'idée de l'algorithme du simplexe consiste à passer d'une base admissible à

une autre jusqu'à trouver une base associée à une solution optimale.

Pour cela, à chaque itération de l'algorithme, on fait sortir une variable de la base et

on fait entrer en base une varialbe Hors-Base.

Variable entrante dans la base:

Il n'y a pas d'obligation théorique à prendre une variable plutôt qu'une autre. Il n'y a

pas non plus de stratégie marchant dans tous les cas pour la choisir.

On utilise fréquemment le critère de Dantzig:

Si maximisation: faire sortir la variable de plus grand coe�cient dans z.

Si minimisation: faire sortir la variable de plus petit coe�cient dans z.

Variable sortante dans la base:

Il faut pénaliser le moins possible le coût de la future solution. On va donc tenter

d'augmenter la solution objective au maximum. Cette augmentation est conditionnée

par les contraintes. On va rechercher la contrainte la plus bloquante et faire sortir la

variable de base qui lui correspond.

Posons e l'indice de la variable entrante et s celui de la variable sortante. On note b et

a les valeurs des coe�cients du PL à l'itération courante.

Si maximisation: s véri�e bsase

minimum parmi les biaie

où aie > 0, i ∈ {1, ...,m}.Si maximisation: s véri�e bs

aseminimum parmi les bi

aieoù aie < 0, i ∈ {1, ...,m}.

L'algorithme du simplexe quand tout va bien

L'algorithme suivant correspond au cas Maximisation.

Soit B ⊂ {1, ..., n+m} un ensemble de m indices distincts formant une base réalisable.

On écrit alors le PL en fonction de cette base.

xi = bi −∑

j /∈B aijxi,∀i ∈ B (Notez le signe −.)z = z +

∑j /∈B cjxj

1) Si cj ≤ 0,∀j /∈ B, alors la solution associée est optimale,

c'est-à-dire la solution:

x∗i = bi,∀i ∈ B,x∗i = O, ∀i /∈ B,z∗ = z.

2) Sinon

- Choix de la variable entrante xe, e /∈ B.37

- Si aie ≤ 0, ∀i ∈ B, alors le PL n'admet pas de solution

(on peut augmenter xe à l'in�ni).

- Sinon

◦ Choix de la variable sortante xs, s ∈ B telle que

bsase

= mini ∈ B

aie > 0

biaie

◦ B ← (B \ s) ∪ {e}◦ Réécriture du système en fonction de la nouvelle base B.

Pour cela, on utilise la seule ligne contenant xs dans l'écriture courante.

Cette ligne d'échange permet d'obtenir xs en fonction des variables

Hors-Base. On remplace ensuite xs dans toutes les autres lignes et

dans z par cette expression.

3) Aller en 1)

6.3 Algorithme du simplexe: exercices calculatoires

Résoudre le problème linéaire suivant par la méthode du simplexe.

max z = 3x1 +2x2 +4x3

x1 +x2 +2x3 ≤ 4

2x1 +3x3 ≤ 5

2x1 +x2 +3x3 ≤ 7

xi ≥ 0, i ∈ {1, .., 3}

6.3.1 Interprétation géométrique

Exercice: Dans le cas d'un programme linéaire à 2 variables et 3 contraintes, donnez

une interprétation géométrique des solutions correspondantes aux bases réalisables,

non réalisables, des variables d'écart, de la direction de la fonction objective et du

déroulement de l'algorithme du simplexe.

6.3.2 Algorithme du simplexe: les di�cultés

Malheureusement la méthode du simplexe ne se limite pas l'algorithme vu jusqu'ici. Il

faut préciser

- son initialisation: dans le cas où la base formée par les variables d'écart n'est pas

réalisable. (On applique alors une recherche préalable appelé phase I)38

- comment éviter le cyclage: en e�et, l'algorithme passe de base réalisable en base réal-

isable, il peut donc �cycler� c'est-à-dire retomber sur la même base indé�niment. Ce

sont des cas dits dégénérés. Pour éviter ce cyclage, on peut soit utiliser des pertuba-

tions numériques du problèmes, soit utiliser des règles lexicographiques pour s'interdire

de passer 2 fois par la même base.

Ainsi, comme il existe un nombre �ni de bases et que l'algorithme se termine, l'algorithme

du simplexe se termine. Néanmoins, dans le pire des cas, il peut demander 2n−1 itéra-

tions.

Heureusement, en pratique, cet algorithme est très e�cace, pouvant résoudre des PL

de plusieurs centaines de milliers de variables et de contraintes.

6.4 Dualité et interprétation économique

Chaque programme linéaire est associé à un autre programme linéaire, de sens d'opitmisation

inverse, que l'on appelle son dual. Ces 2 programmes linéaires sont liés par les pro-

priétés suivantes:

- Une solution réalisable de l'un constitue une borne pour la valeur optimale de l'autre.

- Si l'un possède une solution optimale alors l'autre en a une aussi et leurs valeurs

optimales coïncident.

6.4.1 Dé�nitions

Soit (P) le programme linéaire suivant:

Maximiser z =n∑j=1

cjxj

n∑j=1

aijxj ≤ bi, ∀i ∈ {1, ...,m}

xj ≥ 0, ∀j ∈ {1, ..., n}On appelle dual de (P), le programme linéaire (D) suivant:

Minimiser w =m∑i=1

biyi

m∑i=1

aijyi ≤ cj, ∀j ∈ {1, ..., n}

yi ≥ 0, ∀i ∈ {1, ...,m}

On appelle alors (P) le primal par opposition à (D) son dual.

39

On peut noter:

- qu'à chaque contrainte i du primal, on associe une variable duale yi.

- qu'à chaque variable xj du primal, on associe une contrainte j du dual.

- le rôle des valeurs cj et bi sont inversés entre les 2 PL.

Pour passer d'un Programme linéaire à son dual, on utilise le tableau suivant:

Primal(Dual) Dual(Primal)

Fct obj Max Fct obj Min

cte ≥ var ≤cte ≤ var ≥cte = var �libre�

var ≥ 0 cte ≥var ≤ 0 cte ≤var �libre� cte =

6.4.2 Dualité et borne supérieure

En combinant les inégalités du programme primal de manière à calculer la meilleure

borne supérieure possible, montrer sur un exemple que l'on retrouve le programme

dual.

6.4.3 Propriétés de la dualité

Les résultats suivants correspondent à l'écriture d'un problème (P) et de son dual (D)

écrit comme dans la section précédente (forme canonique).

Remarque: Le dual du dual est le primal.

Propriété 1:

Si le vecteur x = (x1, ..., xn) est une solution réalisable pour (P)

et le vecteur y = (y1, ..., ym) est une solution réalisable pour (D)

alorsn∑j=1

cjxj ≤m∑i=1

biyi.

Ainsi une solution de (P) est une borne inférieure pour (D) et inversement.

Propriété 2: Certi�cat d'optimalité

Si, en plus des hypothèses de la propriété précédente, on an∑j=1

cjxj =m∑i=1

biyi,

40

alors x et y sont respectivement des solutions optimales de (P) et (D).

Propriété 3:

Si le vecteur x∗ = (x∗1, ..., x∗n) est une solution optimale de (P),

alors il existe une solution optimale y∗ = (y∗1, ..., y∗m) de (D)

telle quen∑j=1

cjx∗j =

m∑i=1

biy∗i .

Corollaires:

i) (P) admet une solution optimale si et seulement si (D) en admet une.

ii) Si (P) est non borné (valeur optimale non bornée), alors (D) est irréalisable.

6.4.4 Le théorème des écarts complémentaires

Dé�nition: On dit qu'une contrainten∑j=1

aijxj ≤ bi est lâche pour une solution x si

elle est véri�ée avec une inégalité stricte. Dans le cas contraintre, elle est dite serrée.

Théorème des écarts complémentaires (TEC)

Les solutions réalisables x∗ de (P) et y∗ du (D) sont optimales

si et seulement si

- Pour toute contrainte i non serrée de (P), alors y∗i = 0.

- Pour toute variable x∗j > 0 de (P), alors la contrainte j de (D) est serrée.

41