Chapitre I : Programmation linéaire · 2020. 3. 15. · coût variable unitaire). Pour traiter de la formulation de ces problèmes ainsi que leur résolution nous étudierons le

© Reproduction interdite - 3 -

Chapitre I : Programmation linéaire

Introduction

La programmation linéaire est sans aucun doute la technique la plus

connue de la recherche opérationnelle. C’est aussi un des outils les plus

puissants et les plus utilisés en applications industrielles parmi les

technologies d’aide à la décision pour ne citer que :

- Planification de la production

- Répartition des ressources

- Choix de produits à fabriquer

- Planification d’investissements

- Etablissement de routes et d’horaires

- Affectation et gestion de personnel

- Gestion de projet

- …

La renommée de la programmation linéaire remonte en effet aux

années cinquante quand G.B. Dantzig découvrit l’algorithme du simplexe,

principal outil de résolution des programmes linéaires.

L’importance de la programmation linéaire est liée aux facteurs

suivants :

- De nombreux problèmes de la vie économique peuvent se formuler

comme des programmes linéaires. Ceci est d’autant plus vrai que

depuis la deuxième guerre mondiale, les organisations

économiques et sociales en grandissant en taille ont également

grandi en complexité quant à leur fonctionnement.

- Une autre raison est le développement des outils de calcul. Il ne

fait nul doute que le développement de la recherche opérationnelle

et en particulier de la programmation linéaire est lié au

développement des ordinateurs qui grâce à leurs fantastiques

moyens de calcul permettent de résoudre des problèmes qu’il

n’était pas possible d’étudier avant l’apparition de ces outils de

calcul. De fait, résoudre un programme linéaire est un problème de

mathématiques appliquées et l’algorithme du simplexe n’est pas


autre chose qu’une méthode de calcul destinée à être programmée

et utilisée sur un ordinateur. Notons d’ailleurs que le terme

programmation linéaire ne provient pas de l’expression

« programmation » telle qu’elle est conçue par les informaticiens.

Les applications de la programmation linéaire sont nombreuses et

relèvent de milieux divers comme la médecine, les transports, la finance,

le marketing, la gestion des ressources humaines ainsi que l’agriculture.

Vu la taille ainsi que la complexité des problèmes rencontrés dans ces

diverses applications, le développement de tous les modèles de

programmation linéaire pour approcher ces problèmes peut se faire

selon trois étapes :

(1) Une étape de formulation

(2) Une étape de résolution

(3) Une étape d’interprétation

(1) La formulation consiste à traduire le problème sous forme

d’expressions mathématiques (équations, inéquations)

(2) L’étape de résolution consiste à résoudre le modèle

mathématique en évaluant les variables de décision.

(3) Interprétation et analyse de sensibilité : en supposant que le

modèle mathématique est correct et qu’une solution a été trouvée

grâce aux outils (logiciels) comment utiliser ces résultats, telle est

la question qui se pose au décideur ou manager.

Propriétés des programmes linéaires

Tous les modèles de programmation linéaire possèdent les propriétés

suivantes :

1- Tous les problèmes ont un objectif qui consiste à maximiser ou

minimiser une quantité, souvent un profit ou un coût. On parle de

fonction économique ou fonction objectif pour un programme

linéaire.

2- Les programmes linéaires font état d’un certain nombre de

restrictions ou contraintes qui traduisent des ressources limitées ou


autres. Des contraintes de non-négativité font partie de l’ensemble

des contraintes pour traduire l’impossibilité de valeurs négatives

pour les variables du modèle. Produire des quantités négatives de

meubles ou d’ordinateurs n’a pas de sens.

3- La fonction objectif et les contraintes d’un programme linéaire

doivent être formulées en termes d’expressions mathématiques

linéaires (équations, inéquations linéaires)

Exemple

Expressions linéaires : 24,177 yxyx …

Expressions non linéaires :

12)ln(,2²,103²5²2 yxyxyxyyx …

Hypothèses de base d’un programme linéaire

1- On se place dans le cadre déterministe, c’est à dire toutes les

données numériques sont utilisées dans le programme linéaire

(fonction objectif et contraintes) sont supposées connues et

constantes durant la période d’étude.

2- On suppose le principe de proportionnalité dans la fonction

économique et les contraintes. Exemple : si la production d’une

unité d’un produit nécessite 3 heures d’une ressource, alors

produire 10 unités de ce produit utiliseront 30 heures de cette

ressource.

3- La troisième hypothèse est l’additivité. Si l’objectif est de

maximiser un profit de 8 DH/unité du premier produit + 3DH/unité

du second produit, et si une unité de chaque produit est fabriquée,

les profits unitaires 8 DH et 3 DH doivent être additionnées pour

produire un profit de 8 + 3 = 11 DH.

4- L’hypothèse de divisibilité qui exprime que les variables du

problème sont réelles et pas forcément des entiers naturels. Si les

variables sont sujettes à la contrainte d’indivisibilité, on est alors en

cas de programmation en nombres entiers (PNE) qui sort du cadre

du présent ouvrage.


La production des biens est l’une des applications courantes de la

programmation linéaire (Product mix problem).

Dans la plupart des firmes manufacturières, deux ou plusieurs

produits sont fabriqués utilisant des ressources limitées comme le

personnel, les machines, la matière première, etc.

Le profit que cherche à maximiser la firme dépend du profit unitaire

réalisé sur chaque produit (profit unitaire = prix de vente unitaire –

coût variable unitaire).

Pour traiter de la formulation de ces problèmes ainsi que leur

résolution nous étudierons le cas simple de problèmes à deux

variables avant de discuter le cas général à plusieurs variables.

I- Programmes linéaires à deux variables

1-Problème de maximisation

a) Un problème de production : cas de la menuiserie

MOBILIA

La menuiserie MOBILIA fabrique des tables et des chaises bon marché.

Le procédé de fabrication est le même pour ces deux produits dans le

sens où chacun nécessite un certain nombre d’heures de travail dans

l’atelier « Menuiserie » et un certain nombre d’heures dans l’atelier

« peinture ».

Le tableau suivant résume les données du problème :

Atelier

« menuiserie »

Atelier

« peinture »

Table 4 2

Chaise 3 1

Capacité horaire

totale 240 100

Table 1.1

Le commercial confirme la vente de toute la production de tables.

Cependant et pour cause d’un stock de chaises, il recommande de na

pas dépasser la fabrication de 60 nouvelles chaises.


Chaque table vendue laisse une marge de 7 DH et chaque chaise vendue

une marge de 5 DH.

Le problème que se pose le gestionnaire de la fabrique MOBILIA est de

déterminer un plan de production de chaises et de tables optimal.

Pour ce faire, une modélisation sous forme d’un programme linéaire

s’impose.

b) Modélisation

La construction d’un modèle est, en général, une opération en trois

étapes :

1- Le choix des variables de décision

2- L’expression de l’objectif en fonction de ces variables

3- L’expression des contraintes en fonction de ces variables

1. Variables de décision

Définition 1 : on appelle variable de décision toute quantité utile à la

résolution du problème dont le modèle détermine la valeur.

Par exemple, dans le cas de MOBILIA, ce sont les quantités de tables et

de chaises à produire.

Généralement, elles sont notées par des lettres de la fin de l’alphabet (x,

y, z, etc.) ou autres symboles évocateurs. Par exemple, on peut noter T

le nombre de tables à fabriquer et C le nombre de chaises à fabriquer.

Ce sont les notations qu’on va retenir pour notre exemple.

2. Fonction objectif

Définition 2 : l’objectif est la quantité que l’on veut maximiser ou

minimiser.

Ici, il s’agit de la somme des contributions de chacune des productions

au profit net de la fabrique. Elle s’exprime simplement par :


Profit = (7DH/table) x (Nombre de tables produites) + (5 DH/chaise) x

(Nombre de chaises produites)

En utilisant la notation retenue pour les variables de décision ci-dessus,

la fonction objectif s’écrit alors :

Maximiser 7T + 5C ou CTZMax 57][

C’est cette dernière notation qu’on retiendra pour l’expression de la

fonction objectif.

3. Contraintes

Définitions 3 : les contraintes sont toutes les relations entre les

variables qui limitent les valeurs possibles que peuvent prendre ces

variables.

Ici, il y a trois contraintes :

- la première et la deuxième concernent la ressource temps limitée

dans les ateliers « menuiserie » et « peinture »

- la troisième concerne la fabrication limitée des chaises imposée par

le commercial de la fabrique.

Les deux premières contraintes doivent assurer que le temps global

nécessaire au plan de production est inférieur ou égal au temps

disponible.

Par exemple, dans le cas de l’atelier « menuiserie », le temps utilisé est :

(4 h/table) x (Nombre de tables produites) + (3 h/chaise) x (Nombre de

chaises produites)

Or on dispose au maximum de 240 heures dans cet atelier.

En utilisant les variables de décision T et C définies précédemment, cette

contrainte peut s’écrire :

24034 CT

De même la deuxième contrainte portant sur l’atelier de peinture peut se

traduire par l’inéquation :

10012 CT


Enfin, la contrainte commerciale s’écrit : 60C

Ces trois contraintes représentent les restrictions portées sur les

quantités à fabriquer de tables et de chaises.

Par exemple, la fabrication de 70 tables viole les deux contraintes (T=

70)

De même la fabrication de 50 tables et 100 chaises viole la deuxième

contrainte.

On note en effet certaines interactions entre les variables de décision.

Plus on fabrique de tables moins de chaises sont produites.

Avant de passer à l’étape de résolution, nous complétons le modèle

mathématique par les remarques suivantes :

- produire des quantités négatives de tables et de chaises n’ayant

aucun sens, les contraintes de non-négativité doivent être

spécifiées dans le modèle par les inégalités :

0

0

C

T

- il est possible de tomber sur des quantités fractionnaires ou réelles

pour les quantités T et C. en effet, dans la plupart des problèmes

les variables de décision sont plutôt de type entier et on a affaire à

des problèmes de programmation en nombres entiers (PNE)

La programmation en nombres entiers est très délicate en termes de

résolution et ne présente pas tous les avantages de la programmation

linéaire.

Aussi, nous ignorons dans la plupart des cas cette restriction sur les

variables de décision et nous résolvons le modèle avec des variables

réelles.

c) Résolution graphique

Les modèles de programmation linéaire à deux variables sont des

problèmes très simples à résoudre moyennant une représentation

graphique en géométrie plane. Ceci dit, les modèles relevant de cas

concrets sont rarement à deux variables.


Nous rappelons quelques résultats importants de la géométrie analytique

avant de traiter la résolution de notre cas.

Rappels théoriques

Nous admettons les résultats suivants.

Théorème 1 : les valeurs de la fonction linéaire à deux variables x et y

de type Ax + By le long de tout segment de droite sont comprises entre

les valeurs des extrémités, sauf cas particulier où elles peuvent leur être

égales.

Théorème 2 : la valeur maximum de la fonction linéaire à Ax + By le

long de tout segment est atteinte à une extrémité du segment et la

valeur minimum à l’autre extrémité.

Théorème 3 : la valeur maximum d’une fonction linéaire à deux

variables ),( yxf sur un polygone convexe est atteinte en un sommet de

ce polygone et sa valeur minimum en un autre sommet.

Théorème 4 : la valeur maximum d’une fonction linéaire à plusieurs

variables ),...,,( 21 nxxxf sur un polyèdre convexe est atteinte en un

sommet de ce polyèdre et sa valeur minimum en un autre.

La résolution graphique passe par deux étapes :

- Une étape de représentation des contraintes qui permet d’identifier

un ensemble ou une région de solutions dites admissibles c’est à

dire vérifiant l’ensemble des contraintes.

- Ensuite une étape de calcul de l’optimum, autrement dit la

déduction de la solution optimale parmi l’ensemble des solutions

admissibles.

Représentation graphique des contraintes


Le modèle du cas MOBILIA se résume sous la forme suivante, appelée

aussi forme canonique du programme linéaire :

0,0

60

1002

24034

57][

CT

C

CT

CT

sous

CTZMAX

La représentation graphique se fait sur le plan (XOY) avec (OX) comme

axe des abscisses et (OY) axe des ordonnées.

Ici, on peut utiliser comme axe des abscisses l’axe des tables T et

comme axe des ordonnées l’axe des chaises C.

Les contraintes de non-négativité impliquent que la résolution se fait

principalement dans le premier quadrant du plan.

Pour représenter la première contrainte (l’inéquation 24034 CT )

nous convertissons l’inéquation en équation 24034 CT , équation

cartésienne d’une droite dans le plan géométrique.

Deux points suffisent pour la représenter. Parmi tous les points

candidats, ceux de rencontre des axes d’abscisses et d’ordonnées sont

les plus simples à calculer.

Si T = 0 alors 4.0 + 3.C = 240 soit C = 80 ;

Si C = 0 alors 4.T +0.C = 240 soit T = 60

Pour tracer la droite 24034 CT il suffit de joindre les points (0,80)

et (60,0) par une ligne droite.

Nous avons représenté dans la figure 1.1 la droite ainsi que la région de

points satisfaisant cette contrainte.


On procède de même pour la deuxième contrainte.

On trace la droite d’équation 1002 CT passant par les points

(0,100) et (50,0).

La figure 1.2 représente la région des points satisfaisant les deux

contraintes.

Figure 1.1

Figure 1.2


Enfin, on représente la troisième contrainte 60C en traçant la

droite 60C , droite passant par le point (0,60) et parallèle à l’axe

des abscisses (OT)

Le domaine des solutions admissibles est l’ensemble des points

satisfaisant l’ensemble des contraintes du modèle.

La figure 1.3 représente le domaine des solutions admissibles pour la cas

MOBILIA.

Ce domaine est un polygone convexe. Tout point hors de ce polygone

est une solution inadmissible ou irréalisable.

Maintenant qu’on a délimité l’ensemble des solutions admissibles, il s’agit

de dégager une solution optimale parmi toutes les solutions possibles.

Deux méthodes sont envisageables :

- Méthode des droites parallèles

- Méthode de recensement de sommets

Figure 1.3


Méthode des droites parallèles

Une fois le polygone des solutions admissibles représenté, il s’agit de

déterminer l’optimum qui se trouve forcément sur l’un des sommets du

polygone. Cette méthode consiste alors à :

- Tracer la droite représentant la fonction objectif de valeur nulle Z

= 0, puis à repousser la parallèle à cette droite jusqu’au sommet le

plus éloigné de l’origine. Les coordonnées de ce sommet

fournissent la solution optimale.

Toutefois, on peut toujours vérifier ce résultat en procédant par la

seconde méthode qu’on traitera par la suite.

Dans notre cas le sommet optimal tel qu’il apparaît dans la figure 1.4 est

le sommet de rencontre des droites 24034 CT et 1002 CT . Il

s’agit de résoudre le système linéaire simple :

24034 CT

1002 CT (x –2)

200240C , soit 302

)100(40

CTetC

Donc c’est le sommet de coordonnées (30,40).

Pour maximiser le profit, l’entreprise MOBILIA doit fabriquer 30 tables et

40 chaises, soit un profit de : 7 x 30 + 5 x 40 = 410 DH.

Méthode de recensement des sommets

Cette deuxième technique consiste à :

- déterminer les coordonnées de chaque sommet du polygone des

solutions réalisables ;

- substituer dans la fonction objectif les valeurs des coordonnées de

chaque sommet ;

- la plus grande valeur obtenue est le maximum recherché.

Ici le polygone convexe (OABCD) renferme toutes les solutions possibles.

Pour calculer les coordonnées des sommets O, A, B, C et D, on procède

comme ci dessus, ces sommets étant forcément la rencontre de deux

droites. Soit :


Sommet O (0,0) ZO = 0

Sommet A(0,60) ZA = 300

Sommet B(15,60) ZB = 405

Sommet C(30,40) ZC = 410

Sommet D(50,0) ZD = 350

Remarquons que le sommet C réalise le profit le plus élevé parmi les

autres sommets et donc correspond à l’optimum recherché. Comme

prévu, on obtient la même solution que la méthode précédente.

2-Problème de minimisation

a) Un problème d’alimentation : cas de la société DINDINO

La société DINDINO spécialisée dans l’élevage de la volaille en particulier

la dinde et le dindon. Pour les nourrir elle utilise un mélange deux types

d’aliments A et B.

Chaque type d’aliments contient, dans des proportions variées, une

partie ou la totalité des trois ingrédients (protéines, vitamines, fer)

nécessaires à l’engraissement des dindes.

Chaque « livre1 » de type A contient 5 unités de protéines, 4 unités de

vitamines et ½ unité de fer.

Chaque livre de type B contient 10 unités de protéines, 3 unités de

vitamines et pas de fer.

Une livre de type A revient à 2 DH et une livre de type B à 3 DH.

La table 2.1 résume l’ensemble des données de la société DINDINO.

Ingrédient

Composition de chaque livre de

nourriture

Besoin mensuel

minimum /

dindon Type A Type B

Protéine 5 10 90

Vitamine 4 3 48

Fer ½ 0 1,5

Coût/livre 2 DH 3 DH

Table 2.1

1 Unité de mesure de poids ancienne, à peu près 500 grammes


Le propriétaire de la société souhaite un programme d’alimentation de

coût minimal.

b) Modélisation

Notons A le nombre de livres de type A achetées et B le nombre de livres

de type B achetées. Ce sont les deux variables de décision du problème.

Le problème DINDINO peut se formuler ainsi :

Minimiser le coût BAZ 32 ou BAZMIN 32][

Sous les contraintes

)int(0,0

)int(2

3

2

1

)minint(4834

)int(90105

3

2

1

négativiténondeescontraBA

DferlesurescontraA

DesvitalessurescontraBA

DeslesproteinsurecontraBA

c) Résolution

Dans un premier temps nous représentons le domaine des solutions

réalisables en résolvant graphiquement le système d’inéquations des

contraintes. Ce domaine est présenté dans la figure 2.1.

Le polygone convexe des solutions admissibles est non borné. C’est le

cas de la plupart des problèmes de minimisation.

Méthode des parallèles

On trace la droite correspondant au coût nul (Z = 0), soit 032 BA ou

AB32

Ensuite on trace la parallèle passant par le sommet le plus proche de

l’origine O, ici c’est la parallèle passant par le point F. F est le sommet

extrême correspondant à la solution optimale. Pour déterminer ces

coordonnées, on résout le système linéaire suivant :

4834

90105

BA

BA

Soit A = 8,4 et B = 4,8


Le coût minimal d’alimentation des dindons est : ZMIN = 2.8,4 + 3.4,8,

soit ZMIN = 31,20 DH

Méthode d’énumération des sommets

Le polygone convexe non borné des solutions réalisable possède trois

points extrêmes E, F et G.

Sommet E(3,12) ZE = 42 DH

Sommet F(8,4, 4,8) ZF = 31,20 DH

Sommet G(18,0) ZG = 36 DH

Comme calculé précédemment, le sommet F est le sommet optimal.

La société DINDINO doit commander le plan d’approvisionnement

optimal suivant :

8,4 livres du type d’aliment A

4,8 livres du type d’aliment B

pour un coût total minimal de 31,20 DH.

Figure 2.1


3-Cas particuliers

a) Redondance

Une contrainte est dite redondante lorsqu’elle est inutile. Les autres

contraintes la rendent superflue.

Exemple :

Soit le programme linéaire suivant :

0;0

252

302

20

32][

YX

YX

YX

YX

sous

yXZMAX

On remarque que la droite D3 n’affecte pas le polygone des solutions

réalisables (Figure 3.1) et donc la contrainte correspondante est

redondante. On peut donc l’éliminer sans affecter la résolution du

problème.

Figure 3.1


b) Problèmes « insolubles »

Si l’ensemble des contraintes est incohérent (intersection vide) alors le

problème est insoluble.

Ceci est courant dans des situations concrètes comportant des centaines

de contraintes.

Par exemple, suppose que le responsable marketing insiste sur la

production de 300 tables minimum afin de satisfaire la demande (T

300) et d’autre part, le responsable de production annonce la production

d’au plus 250 tables pour un problème de rupture de stock en matière

premières (T 250)

Dans ce cas là, le domaine des solutions admissibles est forcément vide

à cause de l’incohérence de ces deux contraintes (T 300 et T 250)

Pour illustrer graphiquement un problème infaisable, considérons le cas

suivant :

0;0

2443

82

62

YX

YX

YX

YX

Figure 3.2


c) Problèmes non bornés

Un problème de programmation linéaire peut avoir une solution non

finie. C’est le cas d’un problème de maximisation quand une ou plusieurs

variables solutions peuvent prendre des valeurs infiniment grandes sans

violer aucune des contraintes.

Graphiquement, on a affaire à un domaine de solutions non borné.

Considérons le cas suivant pour illustrer cette situation :

0;0

102

10

5

53][

YX

YX

Y

X

sous

yXZMAX

Une telle situation doit ramener le modélisateur à revoir son modèle de

départ et étudier l’origine du problème. En effet, produire une infinité

d’unités d’articles n’a pas de sens dans la mesure où les ressources sont

limitées d’une part, et la demande aussi d’autre part.

Figure 3.3


d) Dégénérescence

On rencontre deux types de dégénérescence :

Premier type de dégénérescence

En effet, un problème de programmation linéaire peut avoir plusieurs

solutions optimales.

Graphiquement ceci se produit quand la droite représentant la fonction

objectif possède la même pente qu’une contrainte non redondante du

problème.

Les coordonnées de tous les points situés sur un côté du polygone

convexe ou sur un côté de l’ensemble non borné des solutions

admissibles, représentent la solution optimale. Il y a donc une infinité de

solutions.

Soit l’exemple illustratif suivant :

0;0

3

2446

23][

YX

X

YX

sous

YXZMAX

Le polygone convexe (OABC) est le domaine des solutions réalisables

(Figure 3.4). Les droites ZO )0( Z et D1 )2446( YX sont

parallèles. Tous les points du segment [A,B] fournissent la solution

optimale.

En A(0,6) ZA = 12

En B(3,3/2) ZB = 12

En M(2,3) ZM = 12

Etc.


Deuxième type de dégénérescence

Pour illustrer ce type, utilisons le programme linéaire simple suivant :

0;0

60

120

1602

40042

2050][

YX

X

YX

YX

YX

sous

YXZMAX

Figure 3.4

Figure 3.5


On est en présence d’une dégénérescence de deuxième type si, par un

des sommets du domaine des solutions réalisables au moins, passent

plus de deux droites. C’est le cas de la droite D4 dans notre exemple

(Figure 3.5). Seules interviennent dans la résolution du problème les

droites qui forment la frontière de la zone des solutions admissibles.

La droite D4 ne joue aucun rôle dans la résolution du problème et peut

être supprimée.

4-Analyse de sensibilité

Un problème de programmation linéaire est défini par un certain nombre

de paramètres. Ce sont :

- les coefficients de la fonction objectif (cj),

- les seconds membres des contraintes (bi),

- les coefficients techniques (aij).

Si ces coefficients changent, la solution du problème de programmation

linéaire peut être modifiée. A partir du cas MOBILIA nous pouvons

étudier l’effet de telles variations.

a) Modification d’un coefficient de la fonction objectif

la fonction objectif du cas MOBILIA est :

ycxcyxZ 2157 Modifions la contribution c1 en lui ajoutant une quantité . La nouvelle

fonction objectif devient :

yxycxcZ 5)7()( 21

L’équation d’une droite « iso-profit » était Z = 0, soit :

xZ

y5

7

5

Donc la valeur absolue de la pente de cette droite était donnée par :

5

7p


La valeur absolue de la pente devient, après perturbation, 5

7 p

Si est négatif, la valeur absolue de la pente diminue, si est positif elle

augmente. On voit sur la figure 4.1, que lorsque > 0 est ajouté au

coefficient c1, la solution restera au même point extrême C tant que la

droite iso-profit reste comprise entre le cas 1 sans perturbation le cas 3,

qui est celui où la pente de la droite iso-profit est identique à la pente de

la droite D1. Ce cas correspond à :

25

7

C’est-à-dire aussi

3 On en conclut que si la contribution unitaire varie entre 7 DH et 10 DH,

la solution du programme reste inchangée. Si la contribution dépasse

légèrement la valeur 10 DH l’optimum va se déplacer au point extrême

D.

Pour une contribution exactement égale à 10 DH, il y a une infinité de

solutions qui sont tous les points de l’arête [C,D].

Si < 0 est ajouté à la contribution unitaire, la solution reste inchangée

tant que la droite iso-profit reste comprise entre le cas 1 et le cas 2. Ce

dernier correspond à l’égalité des pentes de la droite iso-profit et de la

droite D2, c’est à dire

3

4

5

7

ce qui donne 3

1

Si devient légèrement inférieur à 3

1 , c'est-à-dire si c1 devient

inférieur à 3

20, l’optimum se trouve au point extrême B.

Pour une contribution exactement égale à 3

20 DH, il y a une infinité de

solutions qui sont tous les points du segment [B,C].


Nous venons de voir que si la « plage » de variation 103

201 c

l’optimum reste au même point extrême. Cette information est utile pour

le gestionnaire. Une analyse similaire peut être faite pour le coefficient

c2.

b) Modification d’un second membre d’une contrainte

Le second membre de la deuxième contrainte est égale à 100.

Supposons qu’il devienne 100 . Une valeur 0 correspond à une

augmentation de la quantité de ressource disponible, 0 correspond à une diminution. La contrainte

1002 yx correspond à un demi-espace délimité par la droite d’équation

1002 yx

la droite iso-profit conserve la même pente. Lorsque 0 , le point solution reste le point extrême défini par l’intersection des droites D1 et

Figure 4.1


D2 tant que la droite correspondant à D2 reste comprise entre les cas 1

et 2 représentées sur la figure 4.2.

Lorsque 0 , le point solution reste le point extrême défini par l’intersection des droites D1 et D2 tant que la droite D2 reste comprise

entre les cas 1 et 3.

La solution est donc définie par l’intersection des droites associées aux

deux mêmes contraintes tant que reste comprise entre les deux

valeurs min et max, où min est la valeur telle que la droite d’équation

min1002 yx passe par le point B et max est la valeur telle que la droite d’équation

max1002 yx passe par le point E.

Or B est de coordonnées

60

15 et E de coordonnées

0

60

On doit donc avoir, pour définir min

2.15 + 60 = 100 + min soit min = -10

et pour max

2.60 + 0 = 100 + max soit max = 20

Donc tant que le second membre de la contrainte D2 reste compris entre

100 – 10 = 90 et 100 + 20 = 120

Le point correspondant à l’optimum reste défini par l’intersection de D1

et D2 et l’optimum se déplace sur le segment [B ,E]. Quand ce point

optimum se déplace, la valeur de la fonction objectif est modifiée. Il sera

utile pour le gestionnaire de savoir comment va varier son profit quand

la disponibilité des ressources sera modifiée. Tant que l’optimum reste

sur l’arête [B ,E] on aura un même taux de variation du profit en

fonction de la variation de la quantité de ressource disponible. Ce taux

de variation pourrait être calculé, à partir du cas de figure considéré. Il

sera appelé la valeur marginale de la ressource associée à la contrainte

D2.

Les logiciels de Programmation Linéaire, comme le Solveur d’Excel,

fournissent cette information. On y reviendra dans une section spéciale.


c) Modification d’un coefficient technique

La modification d’un coefficient technique changera la pente d’une droite

associée à une contrainte. Une analyse similaire aux précédentes

pourrait être développée.

II- Programmes linéaires à plusieurs variables

Tout programme linéaire peut se ramener à une formulation ayant une

interprétation économique simple et intuitive. On l’appelle formulation

primale en opposition à une formulation duale qui sera étudiée plus tard.

Cette formulation appelée aussi forme canonique peut s’écrire de

plusieurs façons .

Par exemple dans le cas d’un problème de maximisation, on a :

Figure 4.2


0...,,0,0

...

...

...

...

int

...][

21

2211

22222112

11212111

2211

n

mnmnmm

nn

nn

nn

xxx

bxaxaxa

bxaxaxa

bxaxaxa

escontralessous

xcxcxcZMAX

ou bien

njx

mixa

sous

xcZMAX

j

n

j

jij

nj

j

jj

,...,10

,...,1

][

1

1

Ou bien, en utilisant une écriture matricielle :

0

][

x

bAx

Sous

xcZMAX t

Où

mnm

n

aa

aa

A

...

.....

...

1

111

; ),...,,( 21 nt cccc ; ),...,,( 21 n

t xxxx et

mb

b

b .

1

Les variables xj et les coefficients cj, aij et bi étant des réels.

Dans la section précédente, nous avons montré comment formuler de

cas simples à deux variables sous forme de programmes linéaires et

comment les résoudre simplement moyennant une technique graphique.


Mais cette méthode est impraticable au-delà de deux variables et le

recours à une méthode générale devient indispensable pour des cas

concrets à plusieurs variables et plusieurs contraintes.

Nous consacrons cette section à l’algorithme de simplexe qui permet de

résoudre efficacement ces problèmes.

Cette méthode fut développée par G. Dantzig en 1947. Le principe du

simplexe consiste à poser d’abord le problème sous une forme dite

standard et à déterminer, à partir d’une solution dite de base réalisable

une autre solution admissible qui améliore la fonction objectif et ainsi de

suite : la solution optimale, si elle existe, sera obtenue une fois

l’amélioration de la fonction objectif est impossible.

La forme standard d’un programme linéaire consiste en une

transformation des contraintes de type inéquation en équations.

Toutes les contraintes de la forme

ininii bxaxaxa ...2211

peuvent s’écrire sous la forme d’équations en introduisant des variables

additionnelles non négatives dites variables d’écart.

Par exemple, le système de contraintes :

1002

24034

yx

yx

deviendra

1002

24034

2

1

eyx

eyx

par l’ajout de deux variables d’écart non négatives e1 et e2.

1- Algorithme du simplexe : méthode algébrique de résolution

Nous utilisons le cas simple du cas MOBILIA pour illustrer cette méthode.


Soit le programme linéaire sous sa forme canonique :

0,0

60

1002

24034

57][

yx

y

yx

yx

sous

yxZMAX

La méthode du simplexe nécessite la mise sous forme standard du

programme linéaire à résoudre en ajoutant autant de variables d’écart

qu’il y a de contraintes de type inégalité.

Ainsi pour le problème ci-dessus, la forme standard associée s’exprime

ainsi :

0,0,0,0,0

60

1002

24034

57][

321

3

2

1

eeeyx

ey

eyx

eyx

sous

yxZMAX

ou bien

0

][

x

bAx

sous

xcZMAX t

où

3

2

1

eeeyx

x ; )0,0,0,5,7(

tc ;

10010

01012

00134

A et

60

100

240

b.


L’algorithme du simplexe est itératif, autrement dit, il part d’une solution

de départ admissible dite solution de base réalisable et essaie de

l’améliorer de proche en proche, c'est-à-dire d’une solution de base

réalisable à une autre solution de base améliorante jusqu’à l’optimum.

De manière générale, un programme linéaire sous forme standard se

ramène à la forme :

0

),(

][

x

mnnmformatdematriceAbAx

sous

xcZMAX t

faisant apparaître une matrice A qui peut se décomposer en deux sous-

matrices

][ BIDA

Les colonnes de la matrice B sont des colonnes-unités, linéairement

indépendantes. Ces colonnes forment une base de l’espace vectoriel des

colonnes à m éléments. On appellera B matrice de base.

Les variables associées aux colonnes de la matrice B seront appelées les

variables de base. Dans notre exemple les variables de base sont

essentiellement les variables d’écart e1, e2 et e3.

Les variables associées aux colonnes de la matrice D seront appelées

variables hors-base ; il s’agit des variables de décision x et y dans

l’exemple.

D’une manière générale, la matrice A a m lignes (autant qu’il y a de

contraintes) et n colonnes, avec n > m. Si on sélectionne m variables de

base et si on annule les n-m variables hors-base, la matrice A se

décompose en

][ BIDA

et le système se réduit à :

bBxB

avec B une matrice d’ordre m.


La matrice B est carrée d’ordre m. Si elle définit une base, elle admet

une matrice inverse B-1.

Une solution du système est donc

bBxx BD1,0

Si l’expression B-1b est non négative (≥0), on une solution admissible qui

vérifie les contraintes et que nous appellerons une solution de base

réalisable ou admissible.

0),0(),( 1 bBxxx BD Si le second membre b est positif, une solution de base réalisable

évidente est obtenue en annulant les variables de décision et en

affectant le second membre aux variables d’écart.

En effet B est réduite à la matrice identité et la solution de base est

décomposée en deux types de variables :

Vecteur de variables de base : xB

Vecteur de variables hors-base : xD

Revenons à notre exemple et remarquons :

BD

A

100

010

001

10

12

34


60

100

240

100

010

001

10

12

34

)57(][

3

2

1

e

e

e

y

x

sous

y

xZMAX

BD

Soit

bBxDx BD

avec

60

100

240

0

03

1 bbIbBxety

xx BD

Une solution de base réalisable de départ correspond ici à l’origine.

Nous sommes donc en présence de :

- variables de base : 60100,240 321 eetee

- variables hors-base : 0 yx

et la valeur correspondante de la fonction objectif Z est nulle : Z = 0.

Recherche d’une solution de base améliorante : première itération

Dans la solution de base admissible initiale on a :

00 Zetyx

pour améliorer la valeur de l’objectif Z, il suffit de faire passer l’une de

ces deux variables de la valeur 0 à une valeur positive.

Or la fonction économique est : yxZ 57

Il est donc plus intéressant de choisir x qui vaut 7 par unité alors que y

ne vaut que 5.


La variable ainsi sélectionnée est appelée variable entrante ( y restant

nulle, c'est-à-dire variable hors-base)

Maintenant il s’agit de savoir la valeur maximale à donner à x, variable

entrante.

Le système de contraintes permet d’exprimer les variables de base en

fonction de x et y

ye

yxe

yxe

60

2100

34240

3

2

1

or y = 0

soit

60

2100

4240

3

2

1

e

xe

xe

on doit avoir

00,0 321 eetee

60,0424001 xsoitxsie

50,0210002 xsoitxsie

Pour satisfaire le système de contraintes, la valeur maximale que nous

pouvons donner à x est 50.

Nous obtenons la nouvelle solution de base réalisable :

- variables de base : 6040,50 31 eetex

- variables hors-base : 0,0 2 ey

la valeur de la fonction objectif est : 350Z

En fait, nous arrivons au sommet adjacent à l’origine, le sommet de

coordonnées

0

50


La variable e2 devient variable hors-base. e2 est dite variable sortante.

Maintenant la question qui se pose est : peut-on améliorer cette

solution ?

Pour ce faire, exprimons la fonction Z en fonction de la valeur de x

valeur tirée de la contrainte qui nous a permis de déterminer la valeur

maximale que nous pourrions lui attribuer (50), c'est-à-dire :

1002 2 eyx

soit

22

1

2

150 eyx

et

22

7

2

3350 eyZ

Z est ainsi exprimée en fonction des nouvelles variables hors-base y et

e2.

On peut toujours améliorer la valeur de Z puisque le coefficient de y est

positif (2

3).

Deuxième itération

22

7

2

3350 eyZ

Seule la variable y peut être retenue comme variable entrante.

Reportons maintenant la valeur de x tirée précédemment de la deuxième

équation contrainte ( 221

2150 eyx ) dans les deux autres équations :

Soit pour la première équation :

2403)21

2150(4 12 eyey

soit : 2402200 12 eey

La troisième équation ne subit aucun changement : 603ey

soit le nouveau système :


601002402

3

2

12

eyeyxeey

ye

eyx

eye

6021

2150

240

3

2

21

02eOr

060

02150

040

3

21

ye

yx

ye

6010040

yyy

donc, la valeur maximale que nous pouvons affecter à y est 40.

20;0;3040 31 eexalorsySi

la variable e1 devient variable hors-base : c’est la variable sortante.

Nous obtenons ainsi la solution de base admissible suivante :

- variables hors base : 021 ee

- variables de base : 20;40;30 3 eyx

- la valeur de Z : 41020021040.530.7 Z

en fait, on se trouve au sommet adjacent de coordonnées 4030 Cette solution peut-elle être améliorée ?

Nous avons déterminer la valeur 40 à donner à y à partir de l’équation :

21 240 eye

21 240 eeysoit

La fonction objectif résultant de la première itération est :

22

7

2

3350 eyZ

devient 221 27)240(

23350 eeeZ


soit 21 21

23410 eeZ

Les coefficients des variables e1 et e2 sont négatifs. Faire « entrer » e1

ou e2 réduirait la valeur de Z. Il n’est donc plus possible d’améliorer Z.

Nous avons obtenu la solution optimale :

410;40;30 optimalZyx

Remarques

- A chaque itération nous avons choisi parmi les variables hors-base

de la solution en cours une variable qui devient positive : c’est la

variable entrante.

- Cette variable est portée à une valeur telle qu’une des variables de

base devient nulle : c’est la variable sortante.

Cette transformation correspond au passage d’un sommet à un sommet

adjacent.

Il y a échange de variables : l’une « sort » de la base, l’autre y « entre ».

Critères de sélection de ces variables

Critère de choix de la variable entrante :

Pour déterminer la variable entrante, on exprime la fonction économique

en fonction des seules variables hors base et on choisit la variable du

coefficient positif le plus élevé.

Critère de choix de la variable sortante :

On effectue les rapports des seconds membres des contraintes aux

coefficients correspondants de la variable entrante. La variable sortante

correspond au plus petit rapport strictement positif.

Critère d’arrêt :

Lorsque les coefficients de la fonction objectif exprimée en fonction des

seules variables hors base sont négatifs ou nuls, l’algorithme s’arrête. La

solution optimale est trouvée.

2- Algorithme du simplexe : méthode des tableaux

La méthode du simplexe peut être présentée sous forme de tableaux qui

facilitent considérablement les calculs. Reprenons le même cas traité par

la méthode algébrique, sous sa forme standard :


0,0,0,0,0

60

1002

24034

57][

321

3

2

1

eeeyx

ey

eyx

eyx

sous

yxZMAX

et présentons la solution algébrique sous forme d’une suite de tableaux.

Le premier tableau correspondant à la solution de base de départ se

présente comme suit :

x y e1 e2 e3 R

e1 4 3 1 0 0 240

e2 2 1 0 1 0 100

e3 0 1 0 0 1 60

Z 7 5 0 0 0 0

Détermination de la variable entrante

Selon le premier critère de Dantzig, on sélectionne dans la fonction

objectif Z la variable affectée du coefficient positif le plus élevé.

Donc la variable entrante est x (coefficient 7 dans Z).

Détermination de la variable sortante

Selon le second critère de Dantzig, il faut établir les rapports des seconds

membres des contraintes aux coefficients correspondants de la variable

entrante (colonne x) et sélectionner la variable du plus petit rapport

positif.

On divise donc successivement 240 par 4 (60), 100 par 2 (50) et nous

sélectionnons la variable e2 (ligne correspondant à 50, plus petit rapport

positif).

Variables d’écart

Coefficients de la fonction Z

Va

ria

ble

s

de

ba

se

Variables de décision

Seconds

membres

des contraintes

Valeur de Z

Coefficients du système

des contraintes


x y e1 e2 e3 R ColonneR

e1 4 2 1 0 0 240 604240

e2 2 1 0 1 0 100 502100

e3 0 1 0 0 1 60 -

Z 7 5 0 0 0 0

Le nombre pivot va nous permettre de transformer ce tableau en un

deuxième tableau correspondant à une solution améliorante.

Cette transformation se fait selon les étapes suivantes :

- si le nombre pivot est différent de un, on divise toute la ligne par

ce nombre ;

- on transforme la colonne du pivot en une colonne unitaire par des

opérations élémentaires suivant les lignes.

D’où le deuxième tableau simplexe :

Comme 23 nombre positif fait partie de la ligne Z, la solution est à

améliorer par une nouvelle transformation.

Soit le nouveau tableau simplexe :

x Y e1 e2 e3 R

y 0 1 1 -2 0 40

x 1 0 21

23 0 30

e3 0 0 -1 2 1 20

Z 0 0 23

21 0 - 410

x y e1 e2 e3 R ColonneR

e1 0 1 1 -2 0 40 40140

x 1 21 0 2

1 0 50 100

2150

e3 0 1 0 0 1 60 60160

Z 0 23 0 2

7 0 -

350

Min positif

Min positif


Tous les éléments de la ligne Z sont négatifs ou nuls. L’algorithme du

simplexe s’arrête. La solution optimale trouvée est :

4104030

optimalZyx

la variable d’écart 203e signifie que la troisième contrainte n’est

pas saturée. 20406040 ety

Remarques :

- le nombre à l’intersection de la ligne Z et de la colonne R sera

toujours négatif (ici –410) ; il ne faut tenir compte que de sa

valeur absolue qui représente la valeur de la fonction objectif

( 4030,410 yetxvautZ ).

- Le nombre pivot n’est pas nul, certains calculs peuvent être évités :

o Lorsqu’un zéro figure sur la ligne pivot d’un tableau, la

colonne contenant ce zéro peut être recopiée intégralement

dans le tableau suivant ;

o Lorsqu’un zéro figure dans la colonne du pivot, la ligne qui le

contient peut également être transcrite sans changement

dans le tableau suivant.

- Pour dégager la variable sortante, il faut diviser chaque élément de

la colonne que nous avons intitulée R par l ‘élément correspondant,

sur la même ligne, de la colonne pivot. Un zéro peut apparaître

dans la colonne R : dans ce cas, il faut le remplacer par un nombre

positif infiniment petit, noté « » et continuer les calculs avec

cette valeur que, dans la solution optima le, nous arrondirons

à zéro.

3- Recherche d’une solution de base réalisable de départ

Comme toute méthode itérative, l’algorithme du simplexe nécessite la

connaissance préalable d’une solution de base réalisable. Cette dernière

est immédiate quand les variables principales étant nulles


( Oorigineldireàestcxxx n '',0...21 ), toutes les contraintes sont

respectées.

Aussi, nous avons cette solution de base initiale quand toutes les

contraintes sont du type et leur second membre positif.

Cette solution ne convient pas :

- si le second membre d’une contrainte de type est négatif

- si une contrainte est du type et son second membre positif

- si une contrainte est définie par une égalité.

Dans ces trois cas, la solution correspondant à l’origine ne convient pas

puisque les contraintes ne sont pas vérifiées.

1er cas

Si le second membre d’une contrainte de type est négatif, il faut

multiplier les deux membres de l’inégalité par (-1) et changer le signe de

l’inégalité. On se retrouve avec une contrainte correspondant au second

cas.

2ème cas

Si une contrainte (ou plusieurs contraintes) est du type , le second

membre étant positif, le fait d’introduire une variable d’écart ne permet

pas de prendre l’origine comme solution de base de départ.

Par exemple

2525

eyx

yx

Pour pallier cet inconvénient, on introduit dans l’équation un nouveau

type de variable, variable positive affectée du coefficient +1, appelée

variable artificielle et notée V.

25 Veyx

L’introduction de la variable artificielle V a pour effet d’élargir le champ

des solutions admissibles et permet d’obtenir une solution de base

réalisable de départ :

- variables hors base : ;0,0,0 eyx

- variable de base : .25V


La variable d’écart est traité comme les variables x et y, la variable

artificielle V comme variable de base. En cours du déroulement de la

méthode du simplexe, la mise hors-base de la variable artificielle

réintroduit la contrainte initiale 25yx sans la dénaturer.

Pour que la fonction économique ne change pas de valeur, il faut que la

variable artificielle n’influe pas sur l’optimum de la fonction objectif. La

variable artificielle intervient dans l’optimum avec une valeur nulle, si

nous l’affectons dans la fonction économique à maximiser d’un coût

négatif élevé, qu’on notera –M (méthode du « Big M »).

Exemple

Soit le programme linéaire sous forme canonique suivant :

yxZMAX 4030][

0,02

2282

yxy

yxyx

ou sous forme standard

MVyxZMAX 4030][

0,0,0,0,0,02

2282

321

3

2

1

Veeeyxey

Veyxeyx

or

22 22)22( MeMyMxMeyxMMV

d’où la forme de la fonction objectif

2224030][ MeMyMxMyxZMAX

ou bien

MMeyMxMZMAX 2)40()230(][ 2

d’où le premier tableau simplexe :


x y e1 e2 e3 V R

e1 2 1 1 0 0 0 8

V 2 -1 0 -1 0 1 2

e3 0 1 0 0 1 0 2

Z (30+2M) (40-M) 0 -M 0 0 2M

Remarque : une fois que V quitte la base, plus besoin de garder la

colonne V dans les tableaux suivants.

x y e1 e2 e3 R

e1 0 2 1 0 0 6

X 1 21 0

21 0 1

e3 0 1 0 0 1 2

Z 0 55 0 15 0 -30

x y e1 e2 e3 R

e1 0 0 1 1 -2 2

x 1 0 0 21

21 2

y 0 1 0 0 1 2

Z 0 0 0 15 -55 -140

x y e1 e2 e3 R

e2 0 0 1 1 -2 2

X 1 0 21 0

21 3

Y 0 1 0 0 1 2

Z 0 0 -15 0 -25 -170

D’où la solution optimale

17023

optimalZyx


3ème cas

Si une contrainte (ou plusieurs) est définie par une égalité, on utilisera

également une variable artificielle V (d’un coût négatif élevé –M dans la

fonction objectif), sans introduire une variable d’écart.

Exemple

yxZMAX 24][

0,03605640058

yxyxyx

ou sous forme standard

MVeyxZMAX 1024][

0,0,0,03605640058

1

1

VeyxVyxeyx

déterminons l’expression de –MV à partir de la deuxième contrainte

MMyMxMV 36056

reportons ensuite cette valeur dans Z

MMyMxeyxZ 36056024 1

MeyMxMZSoit 3600)25()46( 1

x y e1 V R

e1 8 5 1 0 400

V 6 5 0 1 360

Z 6M+4 5M+2 0 0 360M

x y e1 V R

x 1 85

81 0 50

V 0 8

10 86 1 60

Z 0 8

410 M 8

46 M 0 60M-200


x y e1 R

x 1 0 2

1 20

y 0 1 53 48

Z 0 0 54 - 176

D’où la solution optimale

1764820

optimalZyx

III- Dualité

Cette section concerne la relation que l’on peut établir entre un problème

de programmation linéaire et son dual. La notion de dualité en

programmation linéaire est très intéressante puisqu’elle permet de

montrer qu’à un problème d’allocation optimale de ressources rares est

aussi associé un problème de tarification optimale de ressources. On

retrouve ainsi un des paradigmes de base de l’analyse économique où un

équilibre est sous-tendu par un système de prix approprié. Cette

tarification optimale de ressources va aussi permettre une analyse de

sensibilité de la solution quand le second membre des contraintes est

perturbé. Nous verrons alors que la solution du problème dual indique

l’influence marginale des dotations en ressources sur la fonction objectif.

1- Formes primale et duale d’un problème de programmation

linéaire

Nous allons définir de manière formelle les formes primale et duale d’un

même programme linéaire. Par la suite nous donnerons les résultats

mathématiques qui lient ces formes entre elles et nous interpréterons

ces résultats.

a) un problème sous forme primale et son dual

Soit le problème de programmation linéaire défini ci-dessus :


0,0

60

1002

24034

57][

yx

y

yx

yx

sous

yxZMAX

Qui représente une situation d’allocation optimale de ressources rares.

Nous appelons cette forme du problème la forme primale.

Nous définissons formellement, la forme duale de ce problème comme

suit ;

wvuWMIN 60100240][

0,0,053

724

wvuwvuvu

Remarquons que, dans cette forme duale, il y a autant de variables qu’il

y a de contraintes dans la forme primale et il y a autant de contraintes

qu’il y a de variables primales. Ces deux problèmes ont ainsi des

formulations symétriques. Cette symétrie est ainsi mise en évidence si

nous utilisons la notation matricielle.

Forme primale

0

][

x

bAx

Sous

xcZMAX t

Forme duale

sousubZMIN t][

0ucAut


Cette symétrie qui relève plus d’une esthétique mathématique cache en

fait un paradigme fondamental de l’analyse économique, appelée dualité

quantité-prix qui permet de considérer un problème d’allocation de

ressources de deux façons équivalents, soit comme la détermination des

niveaux optimaux des activités (détermination des quantités), soit

comme la valorisation optimale des ressources (détermination des prix).

b) Correspondance Dual/Primal

Le tableau ci-dessus donne un ensemble de règles formelles permettant

de passer d’un problème de programmation linéaire général à sa forme

duale.

[MAX] Z [Min] W

Variable xj ≥ 0 Contrainte j ≥

Variable xj ≤ 0 Contrainte j ≤

Variable xj sans restriction de signe Contrainte j =

Contrainte i ≤ Variable ui ≥ 0

Contrainte i ≥ Variable ui ≤ 0

Contrainte i = Variable ui sans restriction de signe

Table 3.1 – Règles de dualité

2- Propriétés fondamentales

Nous admettons les résultats suivants sans démonstrations (pour les

puristes, voir références)

a) La fonction objectif du problème primal à la même valeur optimale

que la fonction objectif du problème dual.

b) Si, pour une solution d’un programme linéaire, une contrainte n’est

pas saturée, alors la valeur optimale de la variable duale

correspondante est nulle. La réciproque est fausse.

c) Si la valeur optimale d’une variable d’un programme linéaire n’est

pas nulle, alors la contrainte duale correspondante est saturée

pour la solution optimale.


3- Résolution d’un problème de minimisation par passage au

dual

a) Méthode

La résolution d’un problème de minimisation par la méthode du simplexe

n’est pas toujours simple dans la mesure où la plupart des contraintes

sont de type et on ne dispose pas d’une solution de base réalisable de

départ évidente.

Il faut introduire des variables artificielles, ce qui complique

singulièrement la solution.

Aussi utiliserons-nous la notion de dualité en tenant compte des

propriétés fondamentales précédentes.

La démarche est alors la suivante :

1. A partir de la forme canonique du programme à minimiser, écrire le

dual.

2. Résoudre le programme dual par la méthode du simplexe (méthode

des tableaux).

3. Le maximum du dual est le minimum recherché.

4. Rechercher par application des propriétés fondamentales b et c ci

dessus :

- d’une part, les contraintes du dual non saturées par la solution

trouvée : en déduire que la variable du primal correspondant à

chaque contrainte non saturée est nulle ;

- d’autre part, le système à résoudre à partir des contraintes du

primal (obligatoirement saturées) correspondant aux variables

optimales du dual non nulles.

La résolution de ce système donne la solution optimale.

Une autre façon de détecter la solution optimale peut se faire à partir du

dernier tableau simplexe de résolution du dual :

Les solutions du primal sont, au signe près, les valeurs des variables

d’écart du dual qui figurent sur la dernière ligne du dernier tableau

simplexe du dual. Il est don recommandé de vérifier la solution obtenue

précédemment par application des propriétés fondamentales b et c.


b) Application

Soit le problème de la société DINDINO

BAZMIN 32][

)int(0,0

)int(2

3

2

1

)minint(4834

)int(90105

3

2

1

négativiténondeescontraBA

DferlesurescontraA

DesvitalessurescontraBA

DeslesproteinsurecontraBA

* Ecrivons d’abord le dual

ZYXZMAX 34890'][

0,0,03310245

ZYXYXZYX

Soit sous forme standard

ZYXZMAX 34890'][

0,2,1

2

1

,,,3310245

eeZYXeYXeZYX

* Résolvons ensuite ce problème par la méthode de simplexe

X Y Z e1 e2 R

e1 5 4 1 1 0 2

e2 10 3 0 0 1 3

Z’ 90 48 3 0 0 0

X Y Z e1 e2 R

e1 0 25 1 1 2

1 21

X 1 103 0 0 10

1 103

Z’ 0 21 3 0 -9 -27


X Y Z e1 e2 R

Y 0 1 52

52

51

51

X 1 0 253

253

251

256

Z’ 0 0 527

542

524 -31,20

La ligne Z’ne contient plus que des éléments nuls ou négatifs. La solution

optimale trouvée est : le minimum cherché est : 31,20.

e1 = e2 = 0 à la fin des calculs implique que les deux contraintes duales

sont saturées.

Les deux variables optimales du dual X et Y sont non nulles. D’après la

propriété fondamentale (c) les contraintes primales correspondantes sont

obligatoirement saturées.

Soit

483490105

BABA

Système dont la solution est :

8,44,8

BA

Solution conforme à celle obtenue par la méthode graphique.

Rappelons que les solutions sont, au signe près, les valeurs des variables

d’écart du dual, figurant sur la ligne Z’ du dernier tableau du dual.

Sur la ligne Z’ du dernier tableau calculé, on lit :

e1 = 542 et e2 = 5

24

Donc A = 542 = 8,4 et B = 5

24 = 4,8

D’autre part, on lit aussi : Z = 527 ce qui correspond à l’excédent de la

troisième contrainte du primal. En effet, A = 8,4, soit un excédent de

8,4 – 3 = 5,4

4- Interprétation économique de la dualité

Pour cela, nous reprenons l’exemple de la société MOBILIA.


Il s’agit d’un problème où deux activités se partagent trois ressources

rares.

On cherche les niveaux qui maximisent la contribution totale aux profits

et frais fixes.

0,0

60

1002

24034

57][

yx

y

yx

yx

sous

yxZMAX

a) Tarification optimale des ressources

Imaginons que le choix des niveaux d’activités soit confié à un gérant. Le

propriétaire de l’entreprise détient les ressources mais il n’a aucun

contrôle direct sur les niveaux d’activité.

Le propriétaire cherche à établir un système de prix pour les ressources

qui force le gérant à choisir les niveaux d’activité optimaux. Soit :

- u le prix de la ressource #1

- v le prix de la ressource #2

- w le prix de la ressource #3

Pour le propriétaire des ressources, une façon, de s’assurer que la valeur

totale des ressources soit toujours supérieure ou égale à la contribution

des activités, consiste à définir les prix de telle sorte que, pour chaque

activité, la contribution unitaire soit inférieure ou égale à la valeur des

ressources utilisées, valeur calculée à partir des coefficients techniques

(taux d’utilisation) et des prix définis ci-dessus. Nous avons donc deux

inégalités :

53

724

wvu

vu

Nous imposons en outre à ces prix d’être non négatifs (≥0).

Si nous envisageons de facturer le gérant, pour l’utilisation des

ressources, à partir du système de prix (u,v,w) satisfaisant les inégalités

ci-dessus, nous pouvons garantir au propriétaire un paiement total qui


soit toujours supérieur ou égal à la contribution des activités choisies par

le gérant.

Comme on ne peut demander au gérant de verser un loyer supérieur à

la contribution maximale possible qu’il peut retirer des activités, nous

devons chercher le système de prix qui rende minimal le loyer total

versé, sous les contraintes indiquées plus haut, c'est-à-dire résoudre le

problème dual du problème :

wvuWMIN 60100240][

0,0,053

724

wvuwvuvu

La solution de ce problème est : u* = 1,5 ; v* = 1/2 ; w* = 0

En fait, la solution du problème dual correspond à la valeur marginale de

chaque ressource.

La solution du problème primal est :

x* = 30 ; y* = 40.

Les deux premières contraintes sont saturées, la troisième ne l’est pas.

En effet les variables d’écart correspondantes valent : e1 = e2 = 0 ; e3 =

20

La valeur marginale d’une ressource qui n’est pas complètement utilisée

est nulle.

Ici e3* 0 w

* = 0

Les ressources 1 et 2 sont complètement utilisées, leur valeur marginale

est positive. Le système optimal de tarification de ressources est donc :

u* = 1,5 ; v* = 0,5 ; w* = 0

Avec ce système de prix, pour chaque activité de production, on a

égalité entre contribution unitaire et la valeur des ressources utilisées.

4.1,5 + 2.0,5 = 7

3.1,5 + 0,5 + 0 = 5

La valeur totale des ressources est :

W* = 240.1,5 + 100.0,5 + 60.0 = 360 + 50 = 410

Ce qui correspond bien à la valeur optimale de la fonction objectif.


b) Tarification optimale de la demande pour un service public

Considérons un service public, par exemple l’ONEP fournisseur d’eau

potable. On distingue la demande suivant m différents postes horaires.

La demande d’eau potable est donc définie par un vecteur d=(di)i=1,…,m

de quantités d’eau à fournir pour chaque poste. Pour satisfaire cette

demande le service doit s’engager dans un certain nombre de n

d’activités.

L’activité #j a un coût cj et contribue à la satisfaction de la demande au

taux aij. Le problème du service public est de satisfaire la demande au

moindre coût total. Il doit donc choisir les niveaux d’activité qui satisfont

le programme linéaire suivant

xcZMIN t][

0x

dAx

Le problème dual s’écrit

udWMAX t][

0u

cAut

Nous savons qu’à l’optimum les deux fonctions économiques seront

égales. La solution du premier problème donne un plan de production

optimal pour le service public. La solution du problème dual donne une

tarification optimale du service, basée sur le coût marginal de la

demande.

IV- Programmation linéaire sous Excel

Dans la première section nous avons vu que la méthode graphique

permettait de résoudre facilement des programmes linéaires à deux

variables.

Cependant cette méthode se révèle impraticable pour des problèmes

plus complexes de taille considérable tels que les problèmes rencontrés

dans la réalité des entreprises et organisations. la version utilisée est Excel XP 2002


La méthode du simplexe développée en section deux apporte une

solution au problème. C’est une méthode générale ayant fait ses preuves

dans l’industrie et qui est implémentée dans divers packages logiciels

pour ne citer que LINDO, X-Press, GAMS, etc., ainsi que dans divers

tableurs sous forme d’ « add-in », c'est-à-dire un sous-programme

incorporé permettant de résoudre des programmes linéaires.

Nous nous intéressons ici au tableur Excel et à l’outil intégré

« Solveur » permettant de solutionner des problèmes de

programmation linéaire.

Nous avons retenu cet outil, qui n’est pas, avouons-le, l’outil idéal pour

résoudre des programmes linéaires de vraie grandeur industrielle, pour

diverses raisons :

- Excel est le tableur, pour ne pas faire de la pub gratuite, le plus

utilisé et pratiquement toute organisation y a accès ;

- D’autre part, c’est un outil utilisé dans divers cursus académiques

(maths, statistiques,…) et la plupart des étudiants sont familiarisés

avec cet outil ;

Excel utilise une macro appelée Solveur permettant de résoudre des

problèmes d’optimisation, en particulier des programmes linéaires.

La version incluse dans Excel permet de traiter des programmes linéaires

à la hauteur de 200 variables et 100 contraintes en dehors des

contraintes de non négativité. Des versions plus sophistiquées du

Solveur sont commercialisées par la société éditrice du Solveur d’Excel

Frontline Systems inc. (www.frontsys.com ou www.solver.com) . Nous

allons donc montrer l’utilisation du Solveur sur des cas pratiques déjà

traités. Pour commencer, reprenons le cas MOBILIA.

1- Cas MOBILIA sous Excel

Le programme linéaire correspondant est :

http://www.frontsys.com/http://www.solver.com/


0,0

60

1002

24034

57][

yx

y

yx

yx

sous

yxZMAX

Résoudre un problème de programmation linéaire via Excel nécessite un

certain nombre d’étapes.

D’abord, il faut transcrire le modèle linéaire dans une feuille de calcul

Excel. Ensuite il faut lancer le Solveur et lui transmettre un certain

nombre d’information concernant le problème à résoudre, en particulier

les cellules variables, la cellule cible et les contraintes. C’est ce que nous

allons illustrer sur l’exemple MOBILIA.

Pour la première étape, il n’y a pas de méthodes ou règles pour

représenter un programme linéaire dans une feuille Excel. Nous disons

plutôt que plusieurs représentations sont possibles et tout dépend de

l’utilisateur, de son expérience et ses préférences (feeling).

Cependant pour raison de commodité et pour ne pas dérouter le lecteur

novice, nous utiliserons la même représentation pour les différents

problèmes traités dans cette section.

Ainsi comme vous pouvez le remarquer sur l’écran 1.1, nous avons

utilisé des colonnes différents pour représenter tous les paramètres

(valeur de la solution, contribution au profit et les coefficients des

contraintes) associés aux variables de décision.

La fonction objectif et chaque contrainte sont représentées dans

différentes lignes de la feuille de calcul.

Bien qu’elles ne soient pas nécessaires pour la résolution du problème,

nous avons rajouté différentes étiquettes pour une bonne lisibilité du

modèle et une meilleure compréhension des résultats fournis par le

Solveur comme on le verra par la suite.


Ecran 1.1

a) Cellules variables

La boîte de dialogue du Solveur présente un certain nombre de zones

correspondant aux différents éléments d’un programme linéaire, à savoir

les variables de décision, la fonction objectif et les contraintes. Aussi la

zone nommée Cellules variables fait références aux variables de

décision du programme linéaire à résoudre.

Chaque variable de décision du modèle est représentée par une cellule

dans la feuille de calcul. Bien qu’il n’y ait pas de règles quant à la

représentation de ces variables, il est plus pratique d’utiliser des cellules

contiguës pour les variables de décision.

Dans le cas MOBILIA, nous avons deux variables de décision à

représenter par deux cellules adjacentes de la feuille Excel.

Dans l’écran 1.1, nous avons utilisé les cellules B5 et C5 pour représenter

respectivement le nombre de tables (T) et le nombre de chaises (C) à

fabriquer.

On peut aussi laisser vide ces cellules que leur affecter une valeur de

notre choix. Le Solveur affectera automatiquement les valeurs optimales

dans ces cellules si solution y en a.

Il est souhaitable de formater ces cellules, par exemple le format décimal

retenu pour la solution du problème.

On peut également nommer ces cellules au lieu des références B5 et C5.

Les étiquettes descriptives de ces cellules (comme celles dans les cellules

A5, B4 et C4) sont recommandées pour une meilleure compréhension du

modèle.


b) Cellule cible à définir

La valeur de la fonction objectif se trouve dans la zone nommée Cellule

cible à définir de la boîte de dialogue du Solveur. On choisit une

nouvelle cellule libre de la feuille et on y saisit la formule correspondant

à la fonction économique en fonction des cellules variables.

Nous avons choisi la cellule D6 dans le cas MOBILIA (écran 1.1). Bien

qu’on puisse utiliser directement les profits unitaires 7 DH et 5 DH dans

la formule, il est préférable de saisir ces valeurs dans des cellules à part

dans la feuille du modèle et utiliser leurs références relatives dan la

formule de la cellule D6.

Dans l’écran 1.1, nous avons entré les profits unitaires 7 DH et 5 DH

dans les cellules B6 et C6 respectivement.

La formule à entrer dans la cellule D6 peut s’écrire :

= B6*B5 + C6*C5

Le symbole « = » est impératif en Excel pour distinguer les formules des

autres données. Cette formule reflète donc l’expression de la fonction

objectif Z. On peut aussi formater la cellule D6 en format monétaire.

En cas de problème à plusieurs variables, cette formule devient très

longue et encombrante à la saisie. Pour pallier cet inconvénient, on peut

utiliser la fonction intégrée d’Excel « SOMMEPROD » pour exprimer la

fonction objectif du problème. Pour ce faire, il faut respecter la syntaxe

de cette fonction. En effet, al fonction SOMMEPROD nécessite au moins

deux plages de cellules de même taille comme arguments séparés par

un point-virgule. L’une de ces plages (B5:C5) contient les cellules

correspondant aux variables de décision et l’autre plage aux cellules des

profits unitaires (plage B6:C6). Cette fonction calcule le produit scalaire

de deux plages arguments.

Dans notre cas, la formule en D6 peut s’écrire aussi :

=SOMMEPROD(B6:C6;$B$5:$C$5)

La plage ($B$5 :$C$5) a été saisie en références absolues (symbole $)

pour fixer ces références lors de la recopie de la formule.


c) Contraintes

Maintenant, il faut transcrire les contraintes dans la feuille Excel. Pour ce

faire, nous convenons de la chose suivante : nous distinguons dans

chaque contrainte trois éléments : le membre de droite (RHS) de la

contrainte qui est un nombre en général, le membre de gauche (LHS) de

la contrainte qui est une fonction linéaire des cellules variables et le type

de la contrainte, c'est-à-dire une égalité ou une inégalité (=, ≤,≥).

Pour traduire ces différents éléments d’une contrainte dans la feuille de

calcul, nous devons réserver une cellule par membre de contrainte.

Cellules associées aux membres gauches des contraintes (LHS)

Nous associons une cellule de la feuille de calcul à chaque membre

gauche de chaque contrainte du programme linéaire et nous traduisons

en formule l’expression correspondante en fonction des variables de

décision.

Dans l’écran 1.1, nous avons utilisé la cellule D8 pour exprimer le

membre gauche de la contrainte sur les heures de travail de l’atelier

« menuiserie ». Au préalable, nous avons entré les coefficients (4 et 3)

du membre gauche dans les cellules B8 et C8 respectivement. Ainsi on

peut saisir indifféremment l’une ou l’autre des formules suivantes dans la

cellule D8 :

= B8*B5 + C8*C5

ou bien

= SOMMEPROD(B8:C8 ;$B$5:$C$5)

Au passage remarquez que l’on aurait pu obtenir cette seconde formule

par copie de la formule similaire de la cellule D6 (=

SOMMEPROD(B6:C6 ;$B$5:$C$5)). Les formules des membres gauches

des autres contraintes (D9 pour la peinture et D10 pour la contrainte

commerciale) sont obtenues par copie de la formule saisie en cellule D8.

Cellules associées aux membres droits des contraintes (RHS)

Là aussi, on doit choisir une cellule de la feuille pour chaque membre

droit de chaque contrainte.


Bien qu’on ait que des constantes dans notre exemple (240, 100 et 60),

il est possible d’avoir des formules comme membre droit des contraintes

comme pour les membres gauches.

Dans l’écran 1.1 de notre exemple, nous avons reporté les membres

droits des contraintes, à savoir 240, 100 «et 60 dans les cellules F8, F9

et F10 respectivement.

Type de contraintes

Dans l’écran 1.1, nous avons aussi rajouté le type de relation (=, ≤, ≥)

entre les deux membres de chaque contrainte (cellules E8:E10).

A noter que ces signes ne jouent aucun rôle dans la résolution du

problème mais ils ont été rajoutés pour une meilleure compréhension du

modèle.

d) Résolution via le Solveur

Une fois les contraintes saisies dans la feuille, nous lançons la macro

« Solveur » du menu « Outils » du tableau Excel. La boîte de dialogue

« Paramètres du solveur » s’affiche à l’écran. Cette boîte de dialogue

apparaît dans l’écran 1.2.

Ecran 1.2

Spécification de la cellule cible à définir

On entre la référence de la cellule correspondant à la valeur de la

fonction objectif (ici la cellule D6) dans la zone Cellule cible à définir

de la boîte « Paramètres du Solveur ». L’option Max est retenue par

défaut. Pour un problème de minimisation, on doit sélectionner l’option


Min pour spécifier que la fonction objectif est à minimiser. La troisième

option « Valeur » nous permet de spécifier la valeur à atteindre par la

cellule cible. Nous n’utiliserons pas cette option.

Spécification des cellules variables

Maintenant on passe à la zone Cellules variables. On entre dans cette

zone les références des cellules des variables de décision du problème.

Pour le cas MOBILIA, on entre donc la plage B5:C5. Excel affecte le

symbole $ automatiquement aux cellules sélectionnées.

Spécification des contraintes

Ensuite nous utilisons le bouton Ajouter dans la zone suivante pour

entrer les références des membres gauche (LHS) et membres droits

(RHS) de chaque contrainte. La boîte de dialogue Ajouter une

contrainte (voir écran 1.2) contient trois zones, une zone pour entrer la

référence de la cellule du membre gauche Cellule (LHS) de la

contrainte, ensuite une liste déroulante pour le type de contrainte et une

zone pour saisir la référence de la cellule du membre droit Contrainte

(RHS) de la contrainte. La liste déroulante propose cinq options ou

choix : ≤, ≥, =, ent (pour entier), et bin (pour binaire).

Nous pouvons entrer aussi bien chaque contrainte à la fois que plusieurs

contraintes de même type (≤, ≥, =) en même temps. Pour notre cas, on

peut ajouter la contrainte de l’atelier menuiserie en entrant D8 dans la

zone de gauche (LHS), F8 dans la zone de droite (RHS) et en

sélectionnant le type ≤ dans la liste du milieu. Comme il a été mentionné

précédemment, le type ≤ de la cellule E8 n’a pas d’intérêt pour le

Solveur et on doit plutôt entrer le type de chaque contrainte à partir de

la boîte de dialogue « Ajouter une contrainte ». On peut maintenant

ajouter la contrainte de l’atelier peinture en entrant D9 et F9 dans les

zones LHS et RHS respectives de la boîte « Ajouter une contrainte ».

Enfin, on ajoute la contrainte commerciale qui limite la fabrication des

chaises en entrant D10 et F10 dans les zones LHS et RHS respectives.

Du moment que les trois contraintes sont de même type (≤), on peut

entrer la plage de cellules D8 :D10 dans la zone de gauche (LHS), et la


plage correspondante F8:F10 dans la zone de droite (RHS). On

sélectionne « ≤ » comme type de contrainte dans la zone du milieu (liste

déroulante) entre les deux entrées LHS et RHS. Le Solveur interprète

alors ceci comme (D8≤F8, D9≤F9 et D10≤F10).

Ainsi, il apparaît que trois entrées sont suffisantes pour saisir toutes les

contraintes possibles, une pour les contraintes de type ≤, une pour les

contraintes de type ≥ et une troisième pour toutes les contraintes de

type =. Ceci suppose que les membres LHS et RHS des contraintes de

même type sont disposées dans des cellules contiguës.

Au cours de la saisie des contraintes, on peut utiliser les autres boutons

Modifier et Supprimer pour modifier ou supprimer une contrainte.

Notons qu’il n’est pas possible d’entrer les formules de la fonction

objectif et des membres LHS et/ou RHS des contraintes dans la boite de

dialogue Paramètres du Solveur. Les formules doivent être saisies

dans des cellules appropriées de la feuille de calcul Excel avant d’utiliser

le Solveur.

Bien qu’il soit possible d’entrer directement des constantes (240, 100 et

60 pour notre modèle) dans la zone de droite (RHS) au cours de l’ajout

des contraintes, il est préférable d’entrer plutôt des références de

cellules (F8, F9 et F10 dans notre modèle).

Options du Solveur

Une fois toutes les contraintes saisies, la résolution du modèle est enfin

prête. Cependant, avant de cliquer le bouton Résoudre de la boîte

Paramètres du Solveur, on doit d’abord cliquer le bouton Options

pour afficher la boite de dialogue « Options du Solveur » (voir écran

1.3).

Pour résoudre la plupart des programmes linéaires, nous n’avons besoin

de changer aucun des paramètres pris par défaut par le Solveur.

Néanmoins, nous devons cocher les cases Modèle supposé linéaire et

Supposé non négatif. La première case oblige le Solveur à renvoyer un

plan détaillé de l’analyse de sensibilité de la solution trouvée et la


deuxième case ajoute automatiquement les conditions de non négativité

des variables de décisions.

Ecran 1.3

Résolution du modèle

Quand on clique le bouton Résoudre, le Solveur lance le programme de

résolution d’un programme linéaire et les résultats apparaissent sur la

feuille du modèle, comme, le montre l’écran 1.4. Avant de voir les

résultats, il est important de jeter un coup d’œil sur le message de la

boîte Résultats du solveur pour vérifier

Documents

Chapitre I : Programmation linéaire · 2020. 3. 15. · coût variable unitaire). Pour traiter de la formulation de ces problèmes ainsi que leur résolution nous étudierons le