Recherche Opérationnelle 1A

Programmation Linéaire
Modèles classiques

Zoltán Szigeti

Laboratoire G-SCOP
INP Grenoble, France

Z. Szigeti (G-SCOP, Grenoble) RO 1A 1 / 20

Programmation Linéaire

Plan
1 Modélisation,
2 Résolution : L’Algorithme du Simplexe,
3 Dualité,
4 Application : Jeux de stratégie.

C’est quoi la Programmation Linéaire ?

1 Modéliser des problèmes par des Programmes Linéaires,
2 Résoudre ces Programmes Linéaires.

C’est quoi un Programme Linéaire ?

1 Optimiser une Fonction Linéaire sur un domaine défini par des
Contraintes Linéaires.

Z. Szigeti (G-SCOP, Grenoble) RO 1A 1 / 20

Programme Linéaire

Exemple, Définitions
2x1 + 1x2 ≤ 8
1x1 + 2x2 ≤ 7 Contraintes d’inégalités Solution
x2 ≤ 3
x1 , x2 ≥ 0 Contraintes de non-négativité Solution réalisable
4x1 + 5x2 = z(max) Fonction Objectif Solution optimale
x2 ✻

4x1 + 5x2 = z(max)

✲
x2 = 3
❄

x1 + 2x2 = 7
✲
☛ ✻
x1
✙
2x1 + x2 = 8

Programme Linéaire
Z. Szigeti (G-SCOP, Grenoble) RO 1A 2 / 20
Modélisation

Modèles classiques
1 Problème de production,
2 Problème de transport,
3 Problème d’alimentation.

Visualisation Problème de production

di Disponibilité
U1 U2
Matières premières
cij
Contenu

V1 V2 V3 Produits
bj Bénéfice

Z. Szigeti (G-SCOP, Grenoble) RO 1A 3 / 20

Modélisation

Modèles classiques
1 Problème de production,
2 Problème de transport,
3 Problème d’alimentation.

Visualisation Problème de transport

di Disponibilité
U1 U2
Usines
cij
Coût de transport

V1 V2 V3 Ateliers
bj Besoin

Z. Szigeti (G-SCOP, Grenoble) RO 1A 4 / 20

Modélisation

Modèles classiques
1 Problème de production,
2 Problème de transport,
3 Problème d’alimentation.

Visualisation Problème d’alimentation

di Dépense
U1 U2
Aliments
cij
Contenu

V1 V2 V3 Vitamines
bj Besoin

Z. Szigeti (G-SCOP, Grenoble) RO 1A 5 / 20

Problème de production

Avant l’arrivage massif de nouveaux modèles, un vendeur de

téléphones portables veut écouler rapidement son stock composé de
1 8 appareils,
2 4 kits ”mains libres” et
3 19 cartes avec des communications prépayées.
Après une étude de marché, il sait très bien que, dans cette période
de soldes, il peut proposer aux clients deux coffrets qui vont lui
rapporter des profits nets :
1 Coffret 1 : 1 téléphone, 0 kit et 2 cartes, avec un profit net de 7e.
2 Coffret 2 : 1 téléphone, 1 kit et 3 cartes, avec un profit net de 9e.
Il est assuré de pouvoir vendre tranquillement n’importe quelle
quantité de ses offres dans la limite du stock disponible.
Quelle quantité de chaque offre notre vendeur doit-il préparer pour
maximiser son profit net?

Z. Szigeti (G-SCOP, Grenoble) RO 1A 6 / 20

Problème de production

Solution
Produit Coffret I Coffret II En stock
Téléphone 1 1 8
1 Tableau de données : Kit 0 1 4
Carte 2 3 19
Profit 7 9 ??
2 Variables : xi quantité du produit i ; x1 , x2 .
3 Contraintes de disponibilité : Pour produire x1 (x2 ) Coffrets I (II),
1 on a besoin de x1 + x2 téléphones mais il y en a seulement 8,
2 on a besoin de x2 kits mais il y en a seulement 4,
3 on a besoin de 2x1 + 3x2 cartes mais il y en a seulement 19.
4 Contraintes de non-négativité : x1 , x2 ≥ 0.
5 Fonction Objectif : maximiser le profit : 7x1 + 9x2 = z(max).

Z. Szigeti (G-SCOP, Grenoble) RO 1A 7 / 20

Problème de production

Programme linéaire
1x1 + 1x2 ≤ 8
x2 ≤ 4 Contraintes d’inégalités
2x1 + 3x2 ≤ 19
x1 , x2 ≥ 0 Contraintes de non-négativité
7x1 + 9x2 = z(max) Fonction Objectif

Programme linéaire sous forme générale

Ax ≤ b Contraintes d’inégalités
x ≥0 Contraintes de non-négativité
T
c x = z(max) Fonction Objectif
   
1 1   8 P CI C II S
x1 T 1 1 8
, b = 4  , cT = 7 9 .


A = 0 1 ,x =
   K 0 1 4
x2 C 2 3 19
2 3 19 P 7 9 ?

Z. Szigeti (G-SCOP, Grenoble) RO 1A 8 / 20

Problème de transport

Un modèle de voiture est assemblé dans un des trois ateliers situés

dans les villes V1 , V2 et V3 . Les besoins hebdomadaires des trois
ateliers d’assemblage sont au moins 5, 4 et 3 moteurs.
Le moteur qui équipe ce modèle est fourni par une des deux usines
situées dans les villes U1 et U2 . Chaque usine peut fournir au plus 6
moteurs.
Le seul souci pour la direction est de minimiser le coût total de
transport des moteurs entre les deux lieux de fabrication et les trois
ateliers d’assemblage.
Le tableau suivant donne les coûts unitaires (par moteur transporté)
pour tous les trajets envisageables.
V1 V2 V3
U1 38 27 48
U2 37 58 45

Comment minimiser le coût total de transport en respectant l’offre et

la demande ?
Z. Szigeti (G-SCOP, Grenoble) RO 1A 9 / 20
Problème de transport

6 6
U1 U2

38 45
27 58
37 48
V1 V2 V3

5 4 3

Z. Szigeti (G-SCOP, Grenoble) RO 1A 10 / 20

Problème de transport
Solution
Villes V1 V2 V3 disponible
U1 38 27 48 6
1 Tableau de données :
U2 37 58 45 6
demande 5 4 3
2 Variables : xij quantité de moteurs transportés de l’usine i à l’atelier j.
3 Contraintes de disponibilité : on veut transporter
1 x11 + x12 + x13 moteurs de l’usine 1 mais il y en a seulement 6,
2 x21 + x22 + x23 moteurs de l’usine 2 mais il y en a seulement 6,
4 Contraintes de demande : on veut transporter
1 x11 + x21 moteurs à l’atelier 1 mais il en faut 5,
2 x12 + x22 moteurs à l’atelier 2 mais il en faut 4,
3 x13 + x23 moteurs à l’atelier 3 mais il en faut 3,
5 Contraintes de non-négativité : xij ≥ 0.
6 Fonction Objectif : minimiser le coût des transports :
38x11 + 27x12 + 48x13 + 37x21 + 58x22 + 45x23 = w (min).
Z. Szigeti (G-SCOP, Grenoble) RO 1A 11 / 20
Problème de transport

Programme linéaire
x11 + x12 + x13 ≤6
x21 + x22 + x23 ≤ 6
x11 + x21 ≥5
x12 + x22 ≥4
x13 + x23 ≥ 3
xij ≥ 0
38x11 + 27x12 + 48x13 + 37x21 + 58x22 + 45x23 = w (min)

Z. Szigeti (G-SCOP, Grenoble) RO 1A 12 / 20

Problème de transport

Programme linéaire
−x11 − x12 − x13 ≥ −6
−x21 − x22 − x23 ≥ −6
x11 + x21 ≥5
x12 + x22 ≥4
x13 + x23 ≥ 3
xij ≥ 0
38x11 + 27x12 + 48x13 + 37x21 + 58x22 + 45x23 = w (min)

Z. Szigeti (G-SCOP, Grenoble) RO 1A 13 / 20

Problème de transport

Programme linéaire
−x11 − x12 − x13 = −6
−x21 − x22 − x23 = −6
x11 + x21 =5
x12 + x22 =4
x13 + x23 = 3
xij ≥ 0
38x11 + 27x12 + 48x13 + 37x21 + 58x22 + 45x23 = w (min)

Z. Szigeti (G-SCOP, Grenoble) RO 1A 14 / 20

Problème de transport

Programme linéaire sous forme générale

Ax = b Contraintes d’inégalités
x ≥0 Contraintes de non-négativité
c T x = w (min) Fonction Objectif
 
  x11  
−1 −1 −1 0 0 0 x12  −6
0 0 0 −1 −1 −1    −6
 , x = x13  , b =  5  ,
     
A=  1 0 0 1 0 0  x21   
0 1 0 0 1 0   4
x22 
0 0 1 0 0 1 3
x23
c T = 38 27 48 37 58 45 .


6 6
U1 U2

Remarque
38 45
27 58

A est la matrice d’incidence du graphe biparti orienté. V1

37
V2
48
V3

5 4 3

Z. Szigeti (G-SCOP, Grenoble) RO 1A 15 / 20

Problème d’alimentation

Le régime nutritionnel d’un sportif devrait garantir au moins

9 unités de vitamine A et
19 unités de vitamine C par jour.
On trouve sur le marché six produits (numérotés de 1 à 6) riches en
ces vitamines. Un kilogramme de chacun de ces produits contient
respectivement
1, 0, 2, 2, 1, 2 unités de vitamine A et
0, 1, 3, 1, 3, 2 unités de vitamine C et
coûte respectivement 35, 30, 58, 50, 27, 22e.
Quels produits faut-il acheter, et en quelles quantités, pour se nourrir
en minimisant les dépenses?

Z. Szigeti (G-SCOP, Grenoble) RO 1A 16 / 20

Problème d’alimentation

Solution
1 Tableau de données :
Produits 1 2 3 4 5 6 besoin
A 1 0 2 2 1 2 9
C 0 1 3 1 3 2 19
Prix 35 30 58 50 27 22 ?
2 Variables : xi quantité (kg) du produit i à acheter.
3 Contraintes de demande : on aura
1 x1 + 2x3 + 2x4 + x5 + 2x6 unités de vitamine A mais il en faut 9,
2 x2 + 3x3 + x4 + 3x5 + 2x6 unités de vitamine C mais il en faut 19,
4 Contraintes de non-négativité : xi ≥ 0.
5 Fonction Objectif : minimiser la dépense :
35x1 + 30x2 + 58x3 + 50x4 + 27x5 + 22x6 = w (min).

Z. Szigeti (G-SCOP, Grenoble) RO 1A 17 / 20

Problème d’alimentation

Programme linéaire
1x1 + + 2x3 + 2x4 + 1x5 + 2x6 ≥ 9
1x2 + 3x3 + 1x4 + 3x5 + 2x6 ≥ 19
xi ≥ 0
35x1 + 30x2 + 58x3 + 50x4 + 27x5 + 22x6 = w (min)

Programme linéaire
sous forme générale Produits 1 2 3 4 5 6 besoin
A 1 0 2 2 1 2 9
Ax ≥ b C 0 1 3 1 3 2 19
x ≥0 Prix 35 30 58 50 27 22 ?
T
c x = w (min)
   
1 0 2 2 1 2 9
, c T = 35 30 58 50 27 22 .


A= ,b =
0 1 3 1 3 2 19

Z. Szigeti (G-SCOP, Grenoble) RO 1A 18 / 20

Formes Générales

Définition
Forme canonique Forme standard
Ax ≤ b Ax = b
x ≥0 x ≥0
c T x = z(max) c T x = z(max)

Théorème
Tout programme linéaire admet
1 une forme canonique et
2 une forme standard.

Z. Szigeti (G-SCOP, Grenoble) RO 1A 19 / 20

Formes Générales

Démonstration (pour la forme canonique)

a i · x ≥ bi =⇒ (−ai ) · x ≤ (−bi ).
a i · x = bi =⇒ ai · x ≤ bi , (−ai ) · x ≤ (−bi ).
xi ≤ 0 =⇒ xi′ = −xi ≥ 0.
xi sans contrainte de non-négativité =⇒ xi′ ≥ 0, xi′′ ≥ 0, xi = xi′ − xi′′ .
c T · x = w (min) =⇒ (−c)T · x = z(max).

Démonstration (pour la forme standard)

a i · x ≤ bi =⇒ ai · x + yi = bi , yi ≥ 0.

Z. Szigeti (G-SCOP, Grenoble) RO 1A 20 / 20