Plan du cours

1. Introduction
– Historique, Modélisation
2. Aide à la décision
– Approches unicritères et multicritères
– Prise de décision de groupe
– Logiciel Decision Lab
– Applications
3. Optimisation (programmation linéaire)
– Modélisations
– Algorithmes
– Logiciels : Excel, MPL 4
– Applications
4. Graphes
– Chemins les plus courts et les plus longs
– Gestion de projets
– Réseaux de transport
2007/2008 128

Programmation linéaire
• Technique utilisée par 85% des entreprises Fortune 500.
• Utilisée par : banques, éducation, foresterie, industrie
pétrolière, transport, sidérurgie, compagnies
aériennes, …

• Un premier exemple
• Solution graphique
• Applications typiques – Formulation
• Algorithme du simplexe
• Analyse de sensibilité
• Programmation linéaire en variables entières
• Logiciels : Excel et MPL

2007/2008 129

1
 Un premier exemple

• Giapetto’s Woodcarving, Inc., fabrique deux

types de jouets en bois : des soldats et des
trains.
• Chaque soldat fabriqué se vend €27 et requiert
un dépense de €10 en matières premières. De
plus, chaque soldat produit génère €14 de
coûts supplémentaires (salaires et frais
généraux).
• Un train se vend €21 et coûte €9 en matières
premières, plus €10 en coûts supplémentaires .
2007/2008 130

Un premier exemple
• La fabrication des soldats et des trains
demande deux types de main-d’œuvre :
menuiserie et finition.
• Un soldat demande 2 heures de travail de
finition et 1 heure de menuiserie .
• Un train demande 1 heure de travail de
finition et 1 heure de menuiserie .

2007/2008 131

2
 Un premier exemple
• Hebdomadairement, Giapetto peut
disposer de toutes les matières premières
nécessaires à la fabrication mais
l’entreprise ne dispose que de 100 heures
de finition et 80 heures de menuiserie .
• La demande pour les trains est illimitée,
mais un maximum de 40 soldats peuvent
être vendus chaque semaine .
• Giapetto souhaite maximiser son profit
hebdomadaire (revenus - coûts).
2007/2008 132

Formulation (1)
• Variables de décision :
– x1 = nombre de soldats produits chaque sem.
– x2 = nombre de trains produits chaque sem.
• Fonction économique (objectif) :
– Revenus hebdomadaires = 27 x + 21x
1 2

– Coûts hebdomadaires = 10 x + 9 x
1 2

– Autres coûts variables = 14 x + 10 x

1 2

– Fonction économique à maximiser =

2007/2008 z = 3x + 2 x
1 2
133

3
 Formulation (2)
• Contraintes :
– Finition (100h) : 2 x + x ≤ 100
1 2

– Menuiserie (80h): x + x ≤ 80
1 2
– Soldats (max 40): x ≤ 40
1
• Restrictions de signe :
x ≥0
1
x ≥0
2

2007/2008 134

Programme linéaire (PL)

Max z = 3x + 2 x
1 2

2x + x ≤ 100
x +x ≤ 80
1 2

1 2

x 1
≤ 40
x ≥0
1
x ≥0
2

2007/2008 135

4
 Hypothèses
• Proportionnalité: Les contributions de chaque
variable à la fonction économique et aux
contraintes sont proportionnelles à la valeur
prise par cette variable.
• Additivité: Les contributions de chaque
variable à la fonction économique et aux
contraintes sont indépendantes des valeurs
prises par les autres variables.
• Divisibilité: Les variables de décision peuvent
prendre des valeurs fractionnaires. (cf. IP)
• Certitude: Chaque paramètre est connu avec
certitude.
2007/2008 136

2007/2008 137

5
2007/2008 138

2007/2008 139

6
2007/2008 140

2007/2008 141

7
2007/2008 142

2007/2008 143

8
2007/2008 144

2007/2008 145

9
2007/2008 146

Définitions
• Domaine réalisable :
– Ensemble de tous les jeux de valeurs des variables
de décision satisfaisant toutes les contraintes et
restrictions de signe du PL (solutions réalisables ou
solutions admissibles).
• Solution optimale :
– Solution réalisable qui optimise (max ou min) la
fonction économique.
– Existence ?
– Unicité ?

2007/2008 147

10
 Solution graphique - cas de 2
variables

•Domaine réalisable
= région dans le
plan.
•Contrainte :
équation = droite

2007/2008 148

Solution graphique

• Contraintes
• Courbes iso-profit
• Solution optimale

2007/2008 149

11
 Contrainte active - Finition
x2
z = 60
110 z = 120
100 heures 100
z = 180
Finition
90

80

70
Soldats
60

50

40

30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 150

Contrainte active - Finition

x2
z = 60
110 z = 120
110 heures 100
z = 180
z = 190
Finition
90

80

70
Soldats
60

50

40

30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 151

12
 Contrainte active - Finition
x2
z = 60
110 z = 120
90 heures 100
z = 180
z = 170
Finition
90

80

70
Soldats
60

50

40

30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 152

Contrainte non active - Soldats

x2
z = 60
110 z = 120
40 soldats 100
z = 180
Finition
90

80

70
Soldats
60

50

40

30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 153

13
 Contrainte non active - Soldats
x2
z = 60
110 z = 120
45 soldats 100
z = 180
Finition
90

80

70
Soldats
60

50

40

30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 154

Contrainte non active - Soldats

x2
z = 60
110 z = 120
35 soldats 100
z = 180
Finition
90

80

70
Soldats
60

50

40

30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 155

14
 Solutions optimales multiples
Une entreprise du secteur automobile fabrique
des voitures et des camions. Chaque véhicule
doit être traité dans l’atelier de peinture et dans
l’atelier de carrosserie. La capacité de l’atelier
de peinture permet de traiter 40 camions par
jour (si l’on ne peint que des camions), ou 60
voitures par jour (si l’on ne peint que des
voitures). De la même façon la capacité de
l’atelier de carrosserie est limitée à 50 camions
par jour et à 50 voitures par jour. Chaque camion
produit rapporte €300, et chaque voiture €200.
Déterminer un plan de production quotidien qui
permette de maximiser le profit de l’entreprise.
2007/2008 156

Solutions optimales multiples

x1 = number of trucks produced daily

x2 = number of cars produced daily
max z = 300 x1 + 200 x2
s.t.
1 1
x1 + x2 ≤ 1
40 60
1 1
x1 + x2 ≤ 1
50 50
x1 ≥ 0 x2 ≥ 0

2007/2008 157

15
 Exemple de PL contradictoire
Suppose now that the auto company is required to product at
least 30 trucks and 20 cars per day.
→ 2 additional constraints:
x1 ≥ 30 x2 ≥ 20

2007/2008 158

Exemple de PL non borné

max z = 2 x1 − x2
s.t.
x1 − x2 ≤ 1
2 x1 + x2 ≥ 6
x1 ≥ 0 x2 ≥ 0

2007/2008 159

16
 Solution optimale
• Peut être :
– Unique → sommet du domaine réalisable,
– Multiple → côté du domaine réalisable,
– Infinie (contraintes manquantes ?),
– Impossible (contraintes incompatibles !).
• Certaines contraintes sont actives (binding) :
LHS = RHS
• Certaines contraintes sont non-actives
(nonbinding):
LHS ≠ RHS (différence (écart) = slack)
2007/2008 160

Un problème réel
• Integrated Production and Distribution
Facility Planning at Ault Foods
(John Pooley, Interfaces, 24:4, July-august 1994, pp.113-121.)

• Problème : optimiser la production et la

distribution des produits dans une laiterie
industrielle en Ontario .

2007/2008 161

17
 Ault Foods

Dépôt 1 10 usines (production),

Usine 1 (indice: i)
13 dépôts
Client 1 (pour approvisionner les
clients),
Usine i (indice: j)
48 clients,
(indice: k)
Dépôt j Client k 6 produits (lait, crème, …)
(indice: l)
2007/2008 162

Questions
• Que produire, et en quelles quantités, dans
chaque usine ?
• Doit-on fermer certaines usines, ou certains
dépôts ?
• Comment organiser le transport des
produits (usine vers dépôt, dépôt vers
client) ?
• A partir de quel dépôt faut-il approvisionner
chaque client ?
2007/2008 163

18
 Modèle mathématique
• Variables de décision :
– Ai = 0 if plant i is closed, 1 otherwise,
– Bj = 0 if warehouse j is closed, 1 otherwise,
– Cjk = 1 if cust.k is served from warehouse j, 0 otherwise,
– Xijl = qty of prod.l transported fr. plant i to warehouse j
• Paramètres :
– Pi = total production capacity (per year) of plant i,
– Wj = total capacity of warehouse j,
– ei = fixed operating cost for plant i,
– fj = fixed operating cost for warehouse j,
– pil = unit production cost for product l in plant i,
– vj = ave. variable cost per unit stored in warehouse j,
– cijl = unit transportation cost for product l from plant i to wareh. j,
– hjkl = total transportation cost for product l from wareh. j to cust. k,
– dkl = demand of customer k for product l.
2007/2008 164

Formulation PL
   
Minimiser ∑ ei Ai + ∑ pil X ijl  + ∑  f j B j + v j ∑ C jk d kl 
i  j ,l  j  k ,l 
+ ∑ cijl X ijl + ∑ h jkl C jk
i , j ,l j ,k ,l

sous : ∑ X ijl ≤ Ai Pi ∀i
j ,l

∑ X ijl ≤ B jW j ∀j
i ,l

∑ X ijl = ∑ C jk d kl ∀l
i, j j ,k

∑ C jk = 1 ∀k
j

Xijl ≥ 0, Ai , Bj , Cjk = 0 or 1.

→ 1427 variables et 77 contraintes.

2007/2008 165

19
 PL typiques :
Régime alimentaire
Four foods are available for consumption: brownies,
chocolate ice cream, cola and pineapple cheesecake.
One brownie costs ¢50, one scoop of chocolate ice cream
costs ¢20, one bottle of cola costs ¢30, and one piece of
cheesecake costs ¢80. Each day, you must ingest at least
500 calories, 6 oz of chocolate, 10 oz of sugar and 8 oz of
fat. Formulate a LP to satisfy these requirements at
minimum cost.
Per unit: Calories Chocolate Sugar Fat
Brownie 400 3 2 2
Chocolate ice cream 200 2 2 4
Cola 150 0 4 1
2007/2008 Cheesecake 500 0 4 5 166

PL typiques :
Régime alimentaire
x1 number of brownies
x2 number of scoops of chocolate ice cream
x3 bottles of cola
x4 pieces of pineapple cheesecake

• LP formulation:
min z = 50 x1 + 20 x2 + 30 x3 + 80 x4
400 x1 +200 x2 +150 x3 +500 x4 ≥ 500
3 x1 +2 x2 ≥ 6
2 x1 +2 x2 +4 x3 +4 x4 ≥ 10
2 x1 +4 x2 + x3 +5 x4 ≥ 8
xi ≥ 0 ( i = 1, 2,3,4 )
• LP solution:
x1 = 0 x2 = 3 x3 = 1 x4 = 0 z = 90
• Slacks:
2007/2008 t1 = 250 t2 = 0 t3 = 0 t4 = 5 167

20
 PL typiques :
Work scheduling problems
A fast food restaurant requires different numbers of full-time
employees on different days of the week.

Day Full-time employees

1: Monday 17
2: Tuesday 13
3: Wednesday 15
4: Thursday 19
5: Friday 14
6: Saturday 16
7: Sunday 11

Each full-time employee must work five consecutive days and

then receive two days off. The manager wants to use only full-
2007/2008 time employees. Formulate a LP to minimize the number of 168
full-time employees that must be hired.

PL typiques :
Work scheduling problems
xi = number of employees beginning work on day i

• LP formulation:
min z = x1 + x2 + x3 + x4 + x5 + x6 + x7
x1 + x4 + x5 + x6 + x7 ≥ 17
x1 + x2 + x5 + x6 + x7 ≥ 13
x1 + x2 + x3 + x6 + x7 ≥ 15
x1 + x2 + x3 + x4 + x7 ≥ 19
x1 + x2 + x3 + x4 + x5 ≥ 14
+ x2 + x3 + x4 + x5 + x6 ≥ 16
+ x3 + x4 + x5 + x6 + x7 ≥ 11
xi ≥ 0 ( i = 1, 2,…,7 )
• LP solution:
4 10 22 10 67
x1 = x2 = x3 = 2 x4 = x5 = 0 x6 = x7 = 5 z =
3 3 3 3 3

• Rounded up solution:
x1 = 2 x2 = 4 x3 = 2 x4 = 8 x5 = 0 x6 = 4 x7 = 5 z = 25

2007/2008 • IP optimal solution: 169

x1 = 4 x2 = 4 x3 = 2 x4 = 6 x5 = 0 x6 = 4 x7 = 3 z = 23

21
 PL typiques :
Capital budgeting problems
Star Oil Company is considering 5 different investment
opportunities. The cash outflows and net present values (in
M$) are the following:
Inv.1 Inv.2 Inv.3 Inv.4 Inv.5
Time 0 cash outflow $11 $53 $5 $5 $29
Time 1 cash outflow $3 $6 $5 $1 $34
NPV $13 $16 $16 $14 $39

Star Oil has $40 million available for investment at the present
time (time 0); it estimates that one year from now (time 1) $20
million will be available for investment. Star Oil may
purchase any fraction of each investment. In this case, the cash
outflows and NPV are adjusted accordingly. Star Oil wants to
maximize the NPV that can be obtained by investment.
Formulate an LP to achieve this goal. Any funds left over at
time 0 cannot be used at time 1.
2007/2008 170

PL typiques :
Capital budgeting problems
xi = fraction of investment i purchased by Star Oil
• LP formulation:
max z = 13 x1 + 16 x2 + 16 x3 + 14 x4 + 39 x5
11x1 +53 x2 +5 x3 +5 x4 +29 x5 ≤ 40
3 x1 +6 x2 +5 x3 + x4 +34 x5 ≤ 20
x1 ≤ 1
x2 ≤ 1
x3 ≤ 1
x4 ≤ 1
x5 ≤ 1
xi ≥ 0 ( i = 1,2,…,5 )
• LP solution:
x1 = 1 x2 = 0.201 x3 = 1 x4 = 1 x5 = 0.288 z = 57.449
2007/2008 171

22
 PL typiques : Blending problems
Sunco Oil manufactures 3 types of gasoline (gas 1, gas 2 and
gas 3). Each type is produced by blending 3 types of crude oil Octane rating Sulfur content
(crude 1, crude 2, and crude 3). The sales price per barrel of Crude 1 12 0.5%
gasoline and the purchase price per barrel of crude oil are as
Crude 2 6 2.0%
follows:
Crude 3 8 3.0%
Sales price Purchase price
Sunco’s customers require the following amounts of each
Gas 1 $70 Crude 1 $45
gasoline: gas 1 – 3000 barrels per day, gas 2 – 2000 barrels
Gas 2 $60 Crude 2 $35 per day, gas 3 – 1000 barrels per day. The company wants to
Gas 3 $50 Crude 3 $25 meet these demands. Sunco has also the option of advertising
to stimulate demand for its products. Each dollar spent daily in
Sunco can purchase up to 5000 barrels of each type of crude advertising a particular type of gas increases the daily demand
oil daily. for that type of gas by 10 barrels.
The 3 types of gasoline differ in their octane rating and sulfur Formulate an LP to maximize the daily profits (revenues –
content. Gas 1 must have an octane rating of at least 10 and costs) of Sunco.
contain at most 1% of sulphur. Gas 2 must have an octane
rating of at least 8 and contain at most 2% of sulphur. Gas 3
must have an octane rating of at least 6 and contain at most
1% of sulphur. It costs $4 to transform one barrel of oil into
one barrel of gasoline, and Sunco’s refinery can produce up to
14,400 barrels of gasoline daily.

2007/2008 172

PL typiques : Blending problems

ai = dollars spent daily on advertising gas i
xij = barrels of crude oil i used daily to produce gas j
• LP formulation:
x11 x12 x13 x21 x22 x23 x31 x32 x33 a1 a2 a3
21 11 1 31 21 11 41 31 21 -1 -1 -1 MAX
1 0 0 1 0 0 1 0 0 -10 0 0 = 3000
0 1 0 0 1 0 0 1 0 0 -10 0 = 2000
0 0 1 0 0 1 0 0 1 0 0 -10 = 1000
1 1 1 0 0 0 0 0 0 0 0 0 ≤ 5000
0 0 0 1 1 1 0 0 0 0 0 0 ≤ 5000
0 0 0 0 0 0 1 1 1 0 0 0 ≤ 5000
1 1 1 1 1 1 1 1 1 0 0 0 ≤14000
2 0 0 -4 0 0 -2 0 0 0 0 0 ≥0
0 4 0 0 -2 0 0 0 0 0 0 0 ≥0
-0.005 0 0 0.01 0 0 0 0 0.02 0 0 0 ≤0
0 -0.015 0 0 0 0 0 0.01 0 0 0 0 ≤0
0 0 -0.005 0 0 0.01 0 0 0.02 0 0 0 ≤0

• LP solution:
z = 287,500
x11 = 2222.22 x12 = 2111.11 x13 = 666.67
x21 = 444.44 x22 = 4222.22 x23 = 333.34
2007/2008 x31 = 333.33 x23 = 3166.67 x33 = 0 173
a1 = 0 a2 = 750 a3 = 0

23
 Multi-period decision problems:
An inventory model
Sailco Corp. must determine how many sailboats should be
produced during each of the next four quarters. The demand
during each quarter is as follows: Q1 – 40 sailboats, Q2 – 60,
Q3 – 75, Q4 – 25. Sailco must meet demands on time. At the
beginning of Q1, Sailco has an inventory of 10 sailboats. At
the beginning of each quarter, Sailco must decide how many
sailboats should be produced during this quarter. We assume
that sailboats manufactured during a quarter can be used to
meet demand for that quarter. During each quarter, Sailco can
produce up to 40 sailboats with regular-time labor at a total
cost of $400 per sailboat. Additional boats can be produced
with overtime labor at a total cost of $450 per sailboat.
At the end of each quarter (after demand has been satisfied), a
carrying or holding cost of $20 per sailboat is incurred. Use
LP to schedule production to minimize the sum of production
and inventory costs during the next four quarters.
2007/2008 174

Multi-period decision problems:

An inventory model
xt = number of sailboats produced (regular-time) during Qt
yt = number of sailboats produced (overtime) during Qt
it = number of sailboats on hand at the end of Qt
• LP formulation:
min 400 ( x1 + x2 + x3 + x4 ) + 450 ( y1 + y2 + y3 + y4 ) + 20 ( i1 + i2 + i3 + i4
x1 ≤ 40 x2 ≤ 40 x3 ≤ 40 x4 ≤ 40
i1 = 10 + x1 + y1 − 40 i2 = i1 + x2 + y2 − 60
i3 = i2 + x3 + y3 − 75 i4 = i3 + x4 + y4 − 25
xt ≥ 0 yt ≥ 0 it ≥ 0 ( t = 1,2,3,4 )
• LP solution: z = 78, 450
x1 = x2 = x3 = 40 x4 = 25
y1 = 0 y2 = 10 y3 = 35 y4 = 0
i1 = 10 i2 = i3 = i4 = 0
2007/2008 175

24
 Multiperiod financial models
Finco Investment Corp. must determine investment strategy
for the firm during the next three years. At present time (time
0), $100,000 is available for investment. Investments A, B, C,
D and E are available. The cash flow associated with investing
$1 in each investment are:

0 1 2 3
A -$1 +$0.50 +$1 $0
B $0 -$1 +$0.50 +$1
C -$1 +$1.2 $0 $0
D -$1 $0 $0 +$1.9
E $0 $0 -$1 +$1.5
To ensure that the company’s portfolio is diversified, Finco
requires that at most $75,000 be placed in a single investment.
In addition to investments A-E, Finco can earn interest at 8%
per year by keeping univested cash in money market funds.
Returns from investments may be immediately reinvested.
Finco cannot borrow funds. Formulate an LP to maximize
2007/2008 176
cash on hand at time 3.

Multiperiod financial models

A = dollars invested in A
B = dollars invested in B
C = dollars invested in C
D = dollars invested in D
E = dollars invested in E
St = dollars invested in MM funds at time t
• LP formulation:
max z = B + 1.9 D + 1.5 E + 1.08S 2
A + C + D + S 0 = 100,000
0.5 A + 1.2C + 1.08S0 = B + S1
A + 0.5 B + 1.08S1 = E + S2
A ≤ 75,000 B ≤ 75,000 C ≤ 75,000 D ≤ 75,000 E ≤ 75,000
A, B, C , D, E , S1 , S 2 ≥ 0
2007/2008 177

25
 Définitions
• Programme linéaire :
Max z = c1x1 + c2 x 2 + … + cn xn (1)

 a11x1 + a12 x 2 + … + a1n x n ≤ b1


 a 21x1 + a 22 x 2 + … + a 2n x n ≤ b2
 ⋮ ⋮
 (2)
 a i1x1 + a i2x 2 + … + a in x n ≤ bi
 ⋮ ⋮

a m1x1 + a m2 x 2 + … + a mn x n ≤ bm

xj ≥ 0 j = 1,2,…,n (3)

2007/2008 178

Définitions
• Fonction économique à max ou min :
Min z = – Max ( – z )
• Contraintes : ≤ ou ≥ ou =
a i1x1 + a i2 x 2 + … + a in x n ≥ bi
⇕
−a i1x1 − a i2 x 2 − … − a in x n ≤ −b i
a i1x1 + a i2 x2 + … + a in x n = bi
⇕
a i1x1 + a i2 x2 + … + a inx n ≤ bi

a i1x1 + a i2 x2 + … + a inx n ≥ bi
2007/2008 179

26
 Notations
• PL sous forme canonique :

Min z = c1x1 + c 2 x2 + … + c n x n (1)

n
 a11x1 + a12 x 2 + … + a1n x n ≤ b1 Min z = ∑ cj xj
 a 21x1 + a 22 x 2 + … + a 2n x n ≤ b2 j=1


⋮ ⋮ n
 a i1x1 + a i2x 2 + … + a in x n ≤ bi
(2)  ∑ a ijx j ≤ b i , i = 1, 2,…,m
 j=1
 ⋮ ⋮  x ≥ 0 , j = 1, 2,…,n
a m1x1 + a m2 x 2 + … + a mn x n ≤ bm  j

xj ≥ 0 j = 1,2,…,n (3)

où c1, c2, …, cn, a11, a12, …, amn, b1, b2, …, bm ∈ R

2007/2008 180

Notations
• Forme vectorielle :
n
Min z = ∑ c jx j  a1j   b1 
j=1    
 n  2j
a  b2 
P j =   , ⋯ , P0 =  


∑ x jP j ≤ P 0
 
⋮ ⋮
j=1 a   
x ≥ 0 , j = 1,2,…, n  mj   m
b
 j

• Forme matricielle : Min { CX  AX ≤ b , X ≥ 0 }

 c1   x1 
 c2   x2   a11 a12 ⋯ a1n   b1 
    a a 22 ⋯ a 2n  b 
C' =   X =   A =  21  b= 2
  ⋮   ⋮  ⋮ ⋮ ⋱ ⋮   ⋮ 
     a m1 a m1 ⋯ a mn   bm 
 cn   xn 
2007/2008 181

27
 Variables d’écart
• Pour passer d’inéquations à des équations.
a i1x1 + a i2 x 2 + … + a in x n ≤ b i
⇕
a i1x1 + a i2x 2 + … + a in x n + t i = bi
avec t i ≥ 0
a i1x1 + a i2 x 2 + … + a in x n ≥ b i
⇕
a i1x1 + a i2x 2 + … + a in x n − t i = bi
avec t i ≥ 0

• Permet de ramener toutes les contraintes à des

équations, au prix de l’ajout de variables → 2ème
forme canonique pour un PL.
2007/2008 182

Exemple 2
Max z = 40x1 + 30x2

x1 ≤ 8
x2 ≤ 6
x1 + 2x2 ≤ 15
2x1 + x2 ≤ 18

x1 ≥ 0 x2 ≥ 0
⇓⇑

Max z = 40x1 + 30x2

x1 + t1 = 8
x2 + t2 = 6
x1 + 2x2 + t3 = 15
2x1 + x2 + t4 = 18

x1 ≥ 0 x2 ≥ 0 t1 ≥ 0 t2 ≥ 0 t3 ≥ 0 t4 ≥ 0

2007/2008 183

28
 Exemple 2
x1 = 0

t1 = 0

t3 = 0

t2 = 0

x2 = 0
2007/2008 184
t4 = 0

Exemple 2 - Remarques
• Le domaine réalisable est un polygone
convexe.
• Contrainte = côté du polygone = une
variable égale à 0.
• Sommet = intersection de deux côtés =
deux variables égales à 0.
• n = 6, m = 4

2007/2008 185

29
 Base
• Sous-matrice non singulière B, m×m, de A.
• Colonnes de B : vecteurs de base :
– Soit B = { Pj1 , Pj2 , … , Pjm }.
– I(B) = { j1 , j2 , … , jm } = ensemble des indices
de base.
– xj1 , xj2 , … , xjm : variables de base.
– J(B) = ensemble des indices hors base →
variables hors base.

2007/2008 186

Solution de base
• Solution obtenue à partir d’une base B,
en annulant les n–m variables hors base
et en résolvant le système de Cramer
associé aux m variables de base :
AX = b ⇒ BXB = b ⇒ XB = B–1 b
• Cas particuliers :
– Solution de base réalisable (s.b.r.) : XB ≥ 0
– Solution de base explicitée : si B = I,
⇒ XB = b

2007/2008 187

30
 Exemple 2 : bases
Max z = 40x1 + 30x2

x1 ≤ 8
x2 ≤ 6
x1 + 2x2 ≤ 15
2x1 + x2 ≤ 18

x1 ≥ 0 x2 ≥ 0
⇓⇑

Max z = 40x1 + 30x2

x1 + t1 = 8
x2 + t2 = 6
x1 + 2x2 + t3 = 15
2x1 + x2 + t4 = 18

x1 ≥ 0 x2 ≥ 0 t1 ≥ 0 t2 ≥ 0 t3 ≥ 0 t4 ≥ 0

2007/2008 188

Exemple 2 - Remarques
• Le domaine réalisable est un polygone
convexe.
• Contrainte = côté du polygone = une
variable égale à 0.
• Sommet = intersection de deux côtés =
deux variables égales à 0.
• n = 6, m = 4
• Solution de base : n−m = 2 variables hors
base (égales à 0) !
2007/2008 189

31
 s.b.r. de l’exemple 2
Enumération des Solutions de Base
Sommet x1 x2 t1 t2 t3 t4 Solution
z
O 0 0 8 6 15 180 s.b.r.
0 0 - -
E 0 6 8 0 3 12 180 s.b.r.
0 7,5 8 -1,5 0 10,5 - s.b.
0 18 8 -12 -21 0 - s.b.
A 8 0 0 6 7 2 320 s.b.r.
0 0 - -
15 0 -7 6 0 -12 - s.b.
9 0 -1 6 6 0 - s.b.
8 6 0 0 -5 -4 - s.b.
8 3,5 0 2,5 0 -1,5 - s.b.
B 8 2 0 4 3 0 380 s.b.r.
D 3 6 5 0 0 6 300 s.b.r.
6 6 2 0 -3 0 - s.b.
2007/2008 190
C 7 4 1 2 0 0 400 s.b.r.≡s.o.

Résultats théoriques
• Si le domaine réalisable est borné et non
vide, l’ensemble des solutions optimales
du PL comporte au moins un sommet du
domaine réalisable.
• Il y a une correspondance 1-1 entre les
sommets du domaine réalisable et les
solutions de base réalisables.

2007/2008 191

32
 Algorithme du simplexe
• Principe :
Cheminer de sommet
(s.b.r.) en sommet
adjacent en améliorant
à chaque étape la
fonction économique z,
jusqu'à atteindre une
solution optimale ou à
montrer que la solution
optimale est infinie.
2007/2008 192

Algorithme du simplexe
(inclus dans le solver d’Excel)
• Algorithme itératif (1948).
• Permet de trouver une solution de base optimale
(sommet du domaine réalisable).
– Variables de base : > 0
– Variables hors base : = 0
• Détecte les cas non-bornés ou contradictoires.
• Fournit des résultats additionnels :
Analyse post-optimale (analyse de sensibilité)
– Coûts marginaux (reduced costs) :
impact d’une augmentation unitaire d’une variable hors-base
(0 → 1) sur la valeur optimale de la fonction économique.
– Prix marginaux (shadow prices) :
impact d’une augmentation unitaire du membre de droite
RHS d’une contrainte sur la valeur optimale de la fonction
économique.
2007/2008 193

33
 Algorithmes d’optimisation
• Variables continues :
– Algorithme du simplexe,
– Algorithme de type « point intérieur »
• Variables entières :
– Procédures de séparation et d’évaluation
(« branch and bound »)
• Programmes mixtes (continu-entier)

2007/2008 194

Giapetto et le Solver d’Excel

Microsoft Excel 11.0 Rapport des réponses
Feuille: [LPexemples.xls]Giapetto
Date du rapport: 16/10/2005 18:50:49

Cellule cible (Max)

Cellule Nom Valeur initiale Valeur finale
$D$4 Fonction écon. MAX 180 180

Cellules variables
I.
Cellule Nom Valeur initiale Valeur finale
$B$3 x1 20 20
$C$3 x2 60 60

Contraintes
Cellule Nom Valeur Formule État Marge
II.
$D$6 Finition MAX 100 $D$6<=$F$6 Lié 0
$D$7 Menuiserie MAX 80 $D$7<=$F$7 Lié 0
$D$8 Soldats MAX 20 $D$8<=$F$8 Non lié 20
$B$3 x1 20 $B$3>=0 Non lié 20
$C$3 x2 60 $C$3>=0 Non lié 60

2007/2008 195

34
 Résultats
I. Solution optimale trouvée par le
solver.
II. Contraintes actives et non actives et
valeurs des variables d’écart
(« marge »).

2007/2008 196

Giapetto et le Solver d’Excel

Microsoft Excel 11.0 Rapport de la sensibilité

Feuille: [LPexemples.xls]Giapetto
Date du rapport: 16/10/2005 18:50:49

III. IV.
Cellules variables
Finale Réduit Objectif Admissible Admissible
Cellule Nom Valeur Coût Coefficient Augmentation Réduction
$B$3 x1 20 0 3 1 1
$C$3 x2 60 0 2 1 0,5

Contraintes
Finale Ombre Contrainte Admissible Admissible
Cellule Nom Valeur Coût à droite Augmentation Réduction
$D$6 Finition MAX 100 1 100 20 20
$D$7 Menuiserie MAX 80 1 80 20 20
$D$8 Soldats MAX 20 0 40 1E+30 20

2007/2008 V. VI. 197

35
 Résultats
III. Coûts marginaux des variables hors
base.
IV. Intervalles de stabilité de la solution
de base optimale (fonction objectif).
V. Prix marginaux des contraintes.
VI. Intervalles de validité des prix
marginaux.

2007/2008 198

Fonction économique - Trains

x2
z = 60
110 z = 120
2€/train 100
z = 180
Finition
90

80

z = 180 70
Soldats
60

50

40

30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 199

36
 Fonction économique - Trains
x2
z = 60
110 z = 120
2,5€/train 100
z = 180
z = 210
Finition
90

80

z = 210 70
Soldats
60

50

40

30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 200

Fonction économique - Trains

x2
z = 60
110 z = 120
3€/train 100
z = 180
z = 240
Finition
90

80

z = 240 70
Soldats
60

s.o. 50

multiples 40

30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 201

37
 Fonction économique - Trains
x2
z = 60
110 z = 120
2€/train 100
z = 180
Finition
90

80

z = 180 70
Soldats
60

50

40

30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 202

Fonction économique - Trains

x2
z = 60
110 z = 120
1,75€/train 100
z = 180
z = 165
Finition
90

80

z = 165 70
Soldats
60

50

40

30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 203

38
 Fonction économique - Trains
x2
z = 60
110 z = 120
1,5€/train 100
z = 180
z = 150
Finition
90

80

z = 150 70
Soldats
60

s.o. 50

multiples 40

30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 204

Fonction économique - Trains

x2
z = 60
110 z = 120
1€/train 100
z = 180
z = 140
Finition
90

80

z = 140 70
Soldats
60

Nouvelle 50

s.o. 40

30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 205

39
 Prix marginal - Finition
x2
z = 60
110 z = 120
100 heures 100
z = 180
Finition
90

80

PM = 1 70
Soldats
60

50

40

30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 206

Prix marginal - Finition

x2
z = 60
110 z = 120
110 heures 100
z = 180
z = 190
Finition
90

80

PM = 1 70
Soldats
60

50

40
z = 190 30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 207

40
 Prix marginal - Finition
x2
z = 60
110 z = 120
90 heures 100
z = 180
z = 170
Finition
90

80

PM = 1 70
Soldats
60

50

40

z = 170 30

20

10
Menuiserie
x1
10 20 30 40 50 60 70 80 90 100 110

2007/2008 208

…
• Exemple Big Mac

• Solver MPL4 :

http://www.maximal-usa.com

2007/2008 209

41
 Plan du cours
1. Introduction
– Historique, Modélisation
2. Aide à la décision
– Approches unicritères et multicritères
– Prise de décision de groupe
– Logiciel Decision Lab
– Applications
3. Optimisation (programmation linéaire)
– Modélisations
– Algorithmes
– Logiciels : Excel, MPL 4
– Applications
4. Graphes
– Chemins les plus courts et les plus longs
– Gestion de projets
– Réseaux de transport
2007/2008 210

42