Optimisation en Informatique
RCP104
Cours 3 – Principes de base de
la Programmation Linéaire (PL)
Plan du chapitre 4 – Principes de
base de la PL
Introduction à la programmation linéaire
1.
2. Modélisation de problèmes
3. Première utilisation d’un solveur
4. Résolution graphique : un pb à deux
variables
5. Méthode des tableaux du simplexe
6. Dualité en programmation linéaire
Eric Soutif
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
2
1. Introduction à la Programmation
Linéaire
(cid:1) Un problème central en Recherche Opérationnelle
(cid:1) Problème classique de planification : affecter des
ressources limitées à plusieurs activités concurrentes
(cid:1) Programme = Plan (solution de ce problème)
(cid:1) Programmation RO ≠ Programmation informatique
(cid:1) Fonction linéaire : fonction dans laquelle chaque variable
évolue linéairement
xxf
1
(
,
2
,
K
,
x
n
)
=
xc
11
+
xc
2
2
+
K
+
xc
n
n
(cid:1) Programme linéaire = Programme mathématique où
toutes les fonctions sont linéaires
Exemple d’un modèle de PL
(cid:1) Données du problème (Entreprise Clotûres Martin)
• Deux types de produits (produit 1, produit 2)
• Trois usines (usine 1, usine 2, usine 3)
• Capacité limitée de production de chaque usine (par semaine)
• Profit par lot (20 unités de chaque produit)
Tps de production (h / lot)
Produit 1
Produit 2
Capacité de
production (h)
Usine 1
Usine 2
Usine 3
1
0
3
0
2
2
4
12
18
Profit (€) / lot
3000
5000
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
3
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
4
Exemple d’un modèle de PL (suite)
Exemple d’un modèle de PL (suite)
(cid:1) Chaque lot du produit 1 (2) est le résultat combiné de la production
aux usines 1 et 3 (2 et 3)
(cid:1) Énoncé du problème : déterminer
le taux de production pour
chaque produit (nombre lots par semaine) de façon à maximiser le
profit total
(cid:1) Contraintes de capacité de production
≤ 4 (usine 1)
≤ 12 (usine 2)
≤ 18 (usine 3)
• x1
• 2 x2
• 3 x1 + 2 x2
(cid:1) Variables de décision :
•
•
x1 : nombre de lots du produit 1
x2 : nombre de lots du produit 2
(cid:1) Fonction objectif :
Z = profit total
Z = 3 x1 + 5 x2 (profit total en milliers d’euros)
•
•
• Maximiser Z
(cid:1) Contraintes de non-négativité :
• x1
≥ 0, x2
≥ 0 (nombre d’unités produites ≥ 0)
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
5
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
6
Formation CNAM
1
Exemple d’un modèle de PL (fin)
Terminologie de base en PL
Maximiser
Z
=
+
3
x
1
sous
les
contrainte
s
2
x
5
x
1
2
x
3
x
1
2
4
12
2
x
+
x
1
,0
2
x
2
18
0
(cid:1) Solution réalisable (admissible) : solution pour laquelle toutes les
contraintes sont satisfaites (appartient au domaine réalisable)
(cid:1) Solution non réalisable : solution pour
laquelle au moins une
contrainte n’est pas satisfaite (n’appartient pas au domaine
réalisable)
(cid:1) Solution optimale : solution ayant la meilleure valeur possible de
l’objectif
(cid:1) Modèle n’ayant aucune solution optimale :
• Domaine réalisable vide
• Objectif non borné
(cid:1) Modèle ayant une infinité de solutions optimales
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
7
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
8
Terminologie de base en PL (suite)
Pas de solution
=
Z
3
x
1
+
5
x
2
c. s.
Maximiser
x
4
1
x
5
1
x
,0
1
x
2
0
Objectif non borné
+
Maximiser
Z
5
x
4
x
1
=
3
x
2
2
x
1
5
x
1
,0
x
2
0
c. s.
Une infinité de solutions optimales
c. s.
Maximiser
+
x
x
1
x
1
2
,0
+
x
1
x
2
Z
=
4
x
2
0
2. Modélisation de problèmes –
Exemple 1 : horaire de personnel
(cid:1) Chaque jour est divisé en périodes
(cid:1) On a pu estimer un nombre minimum d’employés (MinEmp)
devant être affectés durant chaque période
(cid:1) Chaque jour est divisé en quarts de travail de 8 heures
(cid:1) Plusieurs quarts partagent une même période
(cid:1) Chaque quart de travail exige un salaire particulier
(cid:1) Combien d’employés doit-on affecter à chaque quart de
travail de façon à minimiser le total des salaires versés, en
respectant le nombre minimum d’employés pour chaque
période ?
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
9
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
10
Exemple 1 : données du problème
Exemple 1 : modèle
(cid:1) xj : nombre d’employés affectés au quart j
(cid:1) Objectif :
Minimiser Z = 170 x1 + 160 x2 + 175 x3 + 180 x4 + 195 x5
(cid:1) Pour chaque période, le nombre d’employés affectés aux
différents quarts doit couvrir le minimum d’employés requis
pour cette période
(cid:1) Exemple, période de 14h à 16h :
≥ 64
x2 + x3
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
11
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
12
Formation CNAM
2
‡
‡
£
£
£
‡
‡
‡
£
‡
‡
‡
£
‡
‡
£
Exemple 1 : modèle détaillé
Exemple 1 : conclusions
Minimiser
Z
=
170
x
1
+
175
x
3
+
180
x
4
+
195
x
5
sous
les
contrainte
s
+
160
x
1
+
x
1
+
x
1
+
x
1
+
x
2
+
x
3
+
x
3
x
x
x
x
4
+
4
5
j
x
2
48
x
2
x
2
+
x
2
x
3
x
4
x
4
82
x
5
15
,0
87
79
65
x
3
64
73
43
52
=
j
5,4,3,2,1
o
o
o
o
o
+
x
x
1
Cette dernière contrainte est donc redondanteet peut être enlevée
65
79
x
1
x
2
2
⇒
+
+
⇒
4
x
82
x
3
Même observation avec cette contrainte
x
1
73
x
5
,0
,0
0
x
x
x
4
3
4
+
aucun intérêt à les éliminer : prise en compte implicite dans le
sont aussi redondantes mais il n’y a
processus de résolution
Solution optimale (obtenue par le solveur d’Excel) :
,
)15,43,39,31,48(
=x
)
xxxx
,
1
2
(
,
,
3
4
5
Problème : le nombre d’employés doit toujours être entier, donc
l’hypothèse de divisibilité n’est pas satisfaite dans le modèle
(bien que la solution optimale dans ce cas particulier soit entière)
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
13
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
14
Exemple 2 : un réseau de
distribution
(cid:1) Deux usines (U1, U2)
(cid:1) Un centre de distribution (CD)
(cid:1) Deux entrepôts (E1, E2)
(cid:1) Chaque usine confectionne un certain nombre d’unités d’un
(cid:1) Chaque entrepôt requiert un certain nombre d’unités de ce
même produit (offre)
même produit (demande)
(cid:1) Sur chaque lien (arc) du réseau, il y a un coût de transport
par unité de produit (coût unitaire)
(cid:1) Sur certains arcs, il y a une capacité sur le nombre d’unités
transportées
(cid:1) Objectif : minimiser le coût de transport total
Exemple 2 : données du problème
50 unités
produites
U1
900€/unité
E1
30 unités
requises
400€/unité
200€/unité
[10]
CD
200€/unité
300€/unité
300€/unité
100€/unité
[80]
40 unités
produites
U2
E2
60 unités
requises
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
15
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
16
Exemple 2 : modèle
Exemple 2 : modèle détaillé
(cid:1) mxi,j = nombre d’unités du produit transportées sur l’arc (i, j) (entre les
sommets i et j)
(cid:1) Objectif (en centaines d’€) : Minimiser Z
=
Z
2
x
+
4
x
+
9
x
+
3
x
U1,
U2
U1,CD
E1U1,
U2,CD
+
x
CD,
E2
+
3
x
E1,
E2
+
2
x
E2,
E1
(cid:1) Conservation du flot : en chaque sommet du réseau,
•
flot sortant = flot entrant
• Nbre d’unités produites (usines) = Nbre d’unités requises (entrepôt)
(cid:1) Capacité (sur certains arcs)
• Exemple, pour larc (U1,U2) : xU1,U2
≤ 10
(cid:1) Contraintes de non-négativité
+
9
x
+
3
x
E1U1,
U2,CD
+
x
CD,
E2
+
3
x
E1,
E2
+
2
x
Minimiser
Z
+
U2
=
2
+
x
U1,
x
4
x
U1,CD
+
x
E1U1,
U1,
U2
U1,CD
x
x
U1,
U2
x
U1,CD
x
E1U1,
c. s.
x
U1,
U2
,0
x
U1,CD
,0
x
E1U1,
,0
x
U2,CD
+
x
x
U2,CD
+
x
U2,CD
CD,
E2
+
E1,
x
x
E1,
,0
x
E2
E2
E1,
E2
x
+
x
,0
E2,
E1
E1
E2,
x
E2,
E1
-=
-=
0
30
60
x
CD,
,0
x
E2
CD,
E2
E2,
E1
=
50
=
=
40
0
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
17
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
18
Formation CNAM
3
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
‡
–
–
–
–
–
–
–
Exemple 2 : conclusions
(cid:1) C’est un problème de flot à coût minimum (ou problème de transport)
(cid:1) Solution optimale :
(
x
,
x
,
x
,
x
U1,
U2
U1,CD
E1U1,
U2,CD
,
x
CD,
E2
,
x
,
x
E1,
E2
E2,
E1
=
)
)20,0,80,40,10,40,0(
(cid:1) Le nombre d’unités transportées doit toujours être une valeur entière,
donc l’hypothèse de divisibilité semble ne pas être satisfaite dans ce
modèle mais :
(cid:1) Pour un problème de flot à coût minimum (dont les paramètres sont
entiers), il existe toujours une solution optimale entière (on peut le
prouver)
(cid:1) Confirmation de ce résultat dans ce cas particulier
Exemple 3 : Composition
d’aliments pour le bétail
On désire déterminer la composition, à côut minimal, d’un aliment pour bétail
qui est obtenu en mélangeant au plus trois produits bruts : orge, arachide,
sésame. L’aliment ainsi conditionné devra comporter au moins 22% de
protéines et 3,6% de graisses, pour se conformer aux exigences de la
clientèle. On a indiqué ci-dessous les pourcentages de protéines et de
graisses contenus, respectivement, dans l’orge, les arachides et le sésame,
ainsi que le coût par tonne de chacun des produits bruts :
1
2
3
Produit brut
Pourcentage de
protéines
Pourcentage de
graisses
Coût par tonne
ORGE
ARACHIDES
SESAME
Pourcentage
requis
12%
52%
42%
22%
2%
25
2%
41
10%
3,60%
39
On notera xj (j = 1,2,3) la fraction de tonne de produit brut j contenu dans une
tonne d’aliment. Formuler le problème algébriquement.
Montrer qu’il est est possible de réduire la dimension du problème en
éliminant x1.
Résoudre graphiquement ce problème.
(cid:1)
(cid:1)
(cid:1)
(cid:1)
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
19
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
20
Modèle général de PL
Modèle général de PL (suite)
(cid:1) m ressources (3 usines)
(cid:1) n activités (2 produits)
(cid:1) xj : niveau de l’activité j (taux de production du produit j)
(cid:1) Mesure de performance globale (profit total) : Z
(cid:1) Accroissement de Z résultant de l’augmentation d’une unité
du niveau de l’activité j : cj
(cid:1) Quantité disponible de la ressource i : bi
(cid:1) Quantité de ressource i consommée par l’activité j : aij
Objectif
xc
22
+
K
+
xc
nn
Maximiser
+
=
Z
xc
11
fonctionne
lles
+
+
K
s
Contrainte
+
xa
1
11
xa
1
21
xa
12
2
xa
22
2
+
xa
1
nn
xa
2
nn
b
1
b
2
+
K
+
+
xa
xa
11
22
m
m
Contrainte
non de s
x
,0
,0
1
x
2
+
+
K
xa
mn
négativité
K
x
0
,
n
n
b
m
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
21
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
22
3. Première utilisation d’un solveur
(cid:1) Résoudre le PL servant d’exemple à l’aide du solveur d’Excel
(cid:1) Bouton Office (rond), Options Excel, Compléments, Complément
Solveur
Maximiser
Z
=
3
x
1
les
contrainte
s
sous
x
2
+
5
x
1
x
2
2
4
12
3
x
1
+
2
x
x
1
,0
2
x
2
18
0
4. Résolution graphique : un
problème à deux variables
=
Z
3
x
1
+
5
x
2
Maximiser
4
x
1
2
x
2
12
c. s.
3
x
1
+
2
x
1
,0
x
2
x
2
18
0
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
23
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
24
Formation CNAM
4
‡
‡
‡
£
£
£
‡
‡
£
£
£
‡
‡
£
£
£
Résolution graphique (suite)
Méthode graphique (résumé)
(cid:1) Tracer les droites correspondant aux contraintes
(cid:1) Déterminer le domaine réalisable en vérifiant le sens des inégalités
pour chaque contrainte
(cid:1) Tracer les droites correspondant à la variation de l’objectif
• Dans l’exemple :
=
Z
3
x
1
+
5
x
2
• Ordonnée à l’origine (dépend de la valeur de Z) :
x
-=
2
+
x
1
3
5
1
5
Z
1
5
Z
• Pente :
3-
5
• Maximiser correspond donc à augmenter Z
(cid:1) Mais : uniquement pour les modèles à deux variables
(cid:1) Plus de deux variables : méthode du simplexe
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
25
Optimisation en informatique – RCP 104
Chapitre 3 – Principes de base de la Programmation Linéaire
26
Formation CNAM
5
(cid:219)
RCP104 Optimisation en Informatique
Chapitre 3 – Bases de la Programmation Linéaire (PL)
E. Soutif (eric.soutif@cnam.fr)
1. INTRODUCTION A LA PL (
Fichier powerpoint)
2. MODELISATION DE PROBLEMES (
Fichier powerpoint)
→
3. PREMIERE UTILISATION D’UN SOLVEUR (
Fichier powerpoint)
→
→
4. RESOLUTION GRAPHIQUE : PROBLEME A DEUX VARIABLES (
Fichier powerpoint)
→
5. METHODE DES TABLEAUX DU SIMPLES
5.1) Forme générale, canonique et standard d’un P.L.
• Forme générale. La forme générale d’un P.L. est la suivante :
(cid:22)
(cid:5) maximiser (cid:14)(cid:15)(cid:16)(cid:17) = (cid:19) (cid:20)(cid:21)(cid:16)(cid:21)
(cid:3)
(cid:3)
(cid:3)
(cid:3)
(cid:21)(cid:23)(cid:24)
(cid:22)
(cid:15)(cid:31) ∈ !(cid:17)
(cid:19) (cid:28)(cid:29)(cid:21)(cid:16)(cid:21) = (cid:30)(cid:29)
(cid:21)(cid:23)(cid:24)
(cid:22)
s.c.
(cid:27)
(cid:19) (cid:28)(cid:29)(cid:21)(cid:16)(cid:21) ≤ (cid:30)(cid:29)
(cid:21)(cid:23)(cid:24)
(cid:15)(cid:31) ∈ !#(cid:17)
(cid:16)(cid:21) ≥ 0
(cid:16)(cid:21) réel
(cid:15)& ∈ ‘(cid:17)
(cid:15)& ∈ ‘#(cid:17)
(cid:27)
(cid:27)
(cid:4)
(cid:3)
(cid:3)
(cid:3)
(cid:3)
(cid:2)
*
NB : si (cid:20) et (cid:16) sont deux vecteurs colonne :
(cid:22)
(cid:20)(cid:16) = (cid:19) (cid:20)(cid:21)(cid:16)(cid:21)
(cid:21)(cid:23)(cid:24)
(cid:15)produit scalaire(cid:17)
(cid:22)
(cid:14)(cid:15)(cid:16)(cid:17) = ∑
(cid:21)(cid:23)(cid:24)
(cid:20)(cid:21)(cid:16)(cid:21) = (cid:20)(cid:16)
• Forme canonique :
7
Max (cid:20)(cid:16)
:(cid:16) ≤ (cid:30)
(cid:16) ≥ 0
s.c. 9
NB : A est une matrice m
composantes.
×
est appelée fonction objectif (ou fonction économique), notée souvent
• Forme standard :
6 = (cid:14)(cid:15)(cid:16)(cid:17).
7
Max (cid:20)(cid:16)
:(cid:16) = (cid:30)
(cid:16) ≥ 0
s.c. 9
n, x et c sont deux vecteurs colonnes de n composantes, b est un vecteurs à m
:(cid:16) = (cid:30) ⇔
A
x
b
(cid:22)
∑
(cid:21)(cid:23)(cid:24)
(cid:22)
∑
(cid:21)(cid:23)(cid:24)
(cid:28)(cid:24)(cid:21)(cid:16)(cid:21) = (cid:30)(cid:24)
(cid:28)(cid:29)(cid:21)(cid:16)(cid:21) = (cid:30)(cid:29)
(cid:22)
∑
(cid:21)(cid:23)(cid:24)
(cid:28)>(cid:21)(cid:16)(cid:21) = (cid:30)>
⋮
⋮
⇔
(cid:5)
(cid:3)
(cid:4)
(cid:3)
(cid:2)
RCP104 Optimisation en Informatique
Bases de la programmation linéaire
1
*
*
*
*
*
*
Remarque : maximiser
revient à minimiser
6 = (cid:14)(cid:15)(cid:16)(cid:17)
– 6 = −(cid:14)(cid:15)(cid:16)(cid:17) ∶ maxB∈C (cid:14)(cid:15)(cid:16)(cid:17) = − minB∈C −(cid:14)((cid:16)).
Résoudre
revient donc à résoudre
. Les solutions optimales sont
les mêmes, les valeurs optimales sont opposées.
Min (cid:20)(cid:16)
:(cid:16) = (cid:30)
(cid:16) ≥ 0
7
s.c. 9
7
Max − (cid:20)(cid:16)
:(cid:16) = (cid:30)
(cid:16) ≥ 0
s.c. 9
• Passage de la forme générale à la forme canonique :
(cid:22)
(cid:19) (cid:28)(cid:29)(cid:21)(cid:16)(cid:21) = (cid:30)(cid:29)
(cid:21)(cid:23)(cid:24)
→
(cid:5) (cid:19) (cid:28)(cid:29)(cid:21)(cid:16)(cid:21) ≤ (cid:30)(cid:29)
(cid:3)
(cid:22)
(cid:21)(cid:23)(cid:24)
(cid:22)
*
− (cid:19) (cid:28)(cid:29)(cid:21)(cid:16)(cid:21) ≤ −(cid:30)(cid:29)
(cid:4)
(cid:3)
(cid:2)
(cid:24)
On remplace la variable (cid:16)(cid:21) par deux variables ≥0, (cid:16)(cid:21)
(cid:21)(cid:23)(cid:24)
G
et (cid:16)(cid:21)
en posant :
(cid:16)(cid:21) réel (& ∈ ‘#) → 7
• Passage de la forme générale à la forme standard :
(cid:24)
(cid:16)(cid:21) = (cid:16)(cid:21)
G
− (cid:16)(cid:21)
(cid:24)
, (cid:16)(cid:21)
G
, (cid:16)(cid:21)
≥ 0
(cid:22)
On introduit une variable dite variable d’écart (slack) positive ou nulle, (cid:16)̅(cid:29) ∶
(cid:19) (cid:28)(cid:29)(cid:21)(cid:16)(cid:21) ≤ (cid:30)(cid:29)
(cid:21)(cid:23)(cid:24)
→ H
(cid:19) (cid:28)(cid:29)(cid:21)(cid:16)(cid:21) + (cid:16)̅(cid:29) = (cid:30)(cid:29)
(cid:21)(cid:23)(cid:24)
, avec (cid:16)̅(cid:29) ≥ 0
5.2) Polyèdre des solutions et représentation graphique
L’ensemble
est appelé polytope des solutions associé à un P.L. Il s’agit d’un polytope convexe. S’il est borné, on parle de
polyèdre convexe. Pour des problèmes à deux ou trois variables (cas d’école), on peut représenter le polyèdre
des solutions.
M = N(cid:16) ∈ ℝ
t.q. :(cid:16) = (cid:30), (cid:16) ≥ 0Q
(cid:22)
(cid:22)
Un vecteur
est dit solution réalisable ou admissible du P.L. considéré.
Exemple : Polyèdre des solutions du PL suivant :
(cid:16) ∈ M
maximiser 6 = 4(cid:16)(cid:24) + 12(cid:16)G + 3(cid:16)V
s.c.
(cid:16)(cid:24) ≤ 1000
(cid:16)G ≤ 500
(cid:16)V ≤ 1500
3(cid:16)(cid:24) + 6(cid:16)G + 2(cid:16)V ≤ 6750
(cid:16)(cid:24) ≥ 0, (cid:16)G ≥ 0, (cid:16)V ≥ 0
(cid:27)
(cid:27)
(cid:5)
(cid:3)
(cid:4)
(cid:3)
(cid:2)
RCP104 Optimisation en Informatique
Bases de la programmation linéaire
2
*
*
*
*
*
*
*
*
Le plan GHI a pour équation :
L’ensemble des solutions réalisables est l’ensemble des points situés à l’intérieur du polyèdre (OABCDEFGHI).
3(cid:16)(cid:24) + 6(cid:16)G + 2(cid:16)V = 6750
5.3) Bases, solutions de base, géométrie des polyèdres
On considère un P.L. sous sa forme standard :
7
Max (cid:20)(cid:16)
:(cid:16) = (cid:30)
(cid:16) ≥ 0
s.c. 9
On considère que le rang de la matrice A est m.
NB : rang(A) = dimension de la plus grande sous-matrice carrée régulière (= inversible, de déterminant
0)
que l’on peut extraire de A
≠
Remarque : On peut toujours le supposer : si rang(A) < m, une ou plusieurs lignes de A peuvent s’exprimer , les contraintes comme combinaisons linéaires des autres. Suivant la valeur des coefficients correspondantes sont soit redondantes (on peut alors les éliminer), soit incompatibles avec les autres (Ax = b n’a alors pas de solution). (cid:30)(cid:29) Définition : On appelle matrice de base (ou encore, par un léger abus de langage, base) toute sous- matrice carrée inversible ( ) extraite de A (il en existe au moins une puisque rang(A) = m). [ × [ Définition : On appelle base l’ensemble des indices des colonnes qui constitue une matrice de base (on appelera également base l’ensemble de variables correspondant à ces colonnes). Soit B une matrice de base. En permutant les colonnes, on peut mettre A sous la forme A=[B, N] où N est la sous-matrice des colonnes hors-base. De même, on peut écrire x sous la forme et c : ] (cid:16) ^_ ` (cid:16) ] . (cid:20) ^_ ` (cid:20) L’équation Ax = b s’écrit alors : ] variables de base (cid:16)^ ∶ variables hors-base (cid:16) ∶ (1) ] ^ a(cid:16) + '(cid:16) = (cid:30) RCP104 Optimisation en Informatique Bases de la programmation linéaire 3 * *