Formation CNAM 1

 

 

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 * *