Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Instance du problŁme

E = 2000, V = 800 et P = 55.

Aliment Calories ProtØines Vitamines Coßt

4

a1

32

a2

13

a3

8

a4

4

a5

14

a6

2

12

54

285

22

80

110

205

160

160

420

260

3

24

19

9

20

19

Nour Houda Dougui

Recherche OpØrationnelle

14

2

s.c. : 110x1 + 205x2 + 160x3 + 160x4 + 420x5 + 260x6 ≥ 2000

4x1 + 32x2 + 13x3 + 8x4 + 4x5 + 14x6 ≥ 55

2x1 + 12x2 + 54x3 + 285x4 + 22x5 + 80x6 ≥ 800

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0 et x6 ≥ 0.

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Instance du problŁme

E = 2000, V = 800 et P = 55.

Aliment Calories ProtØines Vitamines Coßt

4

a1

32

a2

13

a3

8

a4

4

a5

14

a6

110

205

160

160

420

260

2

12

54

285

22

80

3

24

19

9

20

19

1 Fonction-objectif : z = 3x1 + 24x2 + 19x3 + 9x4 + 20x5 + 19x6

Nour Houda Dougui

Recherche OpØrationnelle

14

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Instance du problŁme

E = 2000, V = 800 et P = 55.

Aliment Calories ProtØines Vitamines Coßt

4

a1

32

a2

13

a3

8

a4

4

a5

14

a6

2

12

54

285

22

80

110

205

160

160

420

260

3

24

19

9

20

19

2

1 Fonction-objectif : z = 3x1 + 24x2 + 19x3 + 9x4 + 20x5 + 19x6

s.c. : 110x1 + 205x2 + 160x3 + 160x4 + 420x5 + 260x6 ≥ 2000

4x1 + 32x2 + 13x3 + 8x4 + 4x5 + 14x6 ≥ 55

2x1 + 12x2 + 54x3 + 285x4 + 22x5 + 80x6 ≥ 800

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0 et x6 ≥ 0.

Nour Houda Dougui

Recherche OpØrationnelle

14

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Plan

1 Programmmation linØaire

Introduction

RØsultats fondamentaux de la P.L.

Di(cid:27)Ørentes formes de programmes linØaires

DØ(cid:28)nitions

ThØorŁmes fondamentaux

RØsolution graphique

MØthode du Simplexe

DualitØ

2 Programmmation linØaire en nombres entiers

Nour Houda Dougui

Recherche OpØrationnelle

15

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Dans cette section, nous prØsentons les fondements thØoriques

de la programmation linØaire. Nous commencerons par voir les

di(cid:27)Ørentes formes de programmes linØaires. Puis, nous

demontrerons quelques rØsultats thØoriques avant de

considØrer les mØthodes de rØsolutions.

Dans le cadre de ce cours, nous nous bornerons (cid:224) l’application

de la mØthode graphique et l’Øtude de l’algorithme du

simplexe, bienque d’autres mØthodes existent.

En e(cid:27)et, il existe plusieurs algorithmes (cid:224) temps polynomial

pour la programmation linØaire, comme les mØthodes de

point intØrieur. D’un aute c(cid:244)tØ, l’algorithme du simplexe qui

est le plus vieil algorithme de programmation linØaire ne

s’exØcute pas en temps polynomial dans le cas le plus

dØfavorable, mais il est relativement e(cid:30)cace et largement

utilisØ en pratique.

Nour Houda Dougui

Recherche OpØrationnelle

16

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Plan

1 Programmmation linØaire

Introduction

RØsultats fondamentaux de la P.L.

Di(cid:27)Ørentes formes de programmes linØaires

DØ(cid:28)nitions

ThØorŁmes fondamentaux

RØsolution graphique

MØthode du Simplexe

DualitØ

2 Programmmation linØaire en nombres entiers

Nour Houda Dougui

Recherche OpØrationnelle

17

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ







Max (ou Min) z = C tX

AX = b

X ≥ 0

Le programme linØaire est dit Øcrit sous forme standard : les

contraintes autres que les contraintes de signe sont toutes des

contraintes d’ØgalitØs et toutes les variables sont ≥ 0







Max (ou Min) z = C tX

AX ≤ b

X ≥ 0

Ce programme linØaire est dit Øcrit sous forme canonique : les

contraintes autres que les contraintes de signe sont des inØgalitØs

du type ≤ et toutes les variables sont ≥ 0.

Nour Houda Dougui

Recherche OpØrationnelle

18

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

PropriØtØ

Tout programme linØaire sous forme standard peut s’Øcrire sous

forme canonique. (RØciproquement : tout programme linØaire sous

forme canonique peut s’Øcrire sous forme standard).

⇒

Soit le programme linØaire (p.l)

AX = b ⇔

(cid:40)

(cid:40)

AX ≥ b

AX ≤ b

⇔





Max (ou Min) z = C tX

AX = b

X ≥ 0

− AX ≤ −b

AX ≤ b



donc le p.l. ⇔





Max (ou Min) z = C tX sous contraintes : X ≥ 0

(cid:18) −b

(cid:18) −A

b

A

A(cid:48)X ≤ b(cid:48) avec A(cid:48) =

et b(cid:48) =

(cid:19)



(2m,n)

Nour Houda Dougui

Recherche OpØrationnelle

(cid:19)

2m

19

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

⇐

(cid:40)

Soit le p.l

Max (ou Min) z = C tX sous contraintes : X ≥ 0

AX ≤ b

AX ≤ b ⇔ (AX )i ≤ bi , i ∈ [1..m]

⇔ ∃yi ≥ 0 telque (AX )i + yi = bi , i ∈ [1..m]

⇔ ∃Y ∈ Rm telque AX + Y = b, Y ≥ 0

donc le p.l. ⇔









Max (ou Min) z = C (cid:48)tX (cid:48)

A(cid:48)X (cid:48) = b(cid:48)

X (cid:48) ≥ 0

⇔





Max (ou Min) z = C tX

AX + Y = b

X ≥ 0, Y ≥ 0

(cid:18) X

Y

(cid:19)

n+m

avec X (cid:48) =

, A(cid:48) = (A, I )(m,n+m) et C (cid:48) =

(cid:19)

(cid:18) C

0

n+m

On appelle (yi )1≤i≤m des variables d’Øcarts.

Nour Houda Dougui

Recherche OpØrationnelle

20

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Remarque :

Max z = - Min(-z)

Les contraintes de signe peuvent s’inclure dans les autres

contraintes de type AX ≤ b (ou AX = b).

Exemple :

A(cid:48) =

(cid:18) A

−I

(cid:40)

⇔

(cid:40)

AX ≤ b

X ≥ 0

(cid:19)

et b(cid:48) =

AX ≤ b

− X ≤ 0

(cid:18) b

(cid:19)

0

(m+n,n)

m+n

⇔ A(cid:48)X ≤ b(cid:48) avec

Nour Houda Dougui

Recherche OpØrationnelle

21

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Exercice

Mettez sous forme standard le programme linØaire suivant :

Min (5x1 − 3x2)

s.c. :

x1 − x2 ≥ 2

2x1 + 3x2 ≤ 4

−x1 + 6x2 = 10

x1 ≥ 0, x2 ≥ 0

Nour Houda Dougui

Recherche OpØrationnelle

22

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Correction

x1 − x2 ≥ 2 ⇔ x2 − x1 ≤ −2 ⇔ ∃x3 telque x2 − x1 + x3 = −2

2x1 + 3x2 ≤ 4 ⇔ ∃x4 telque 2x1 + 3x2 + x4 = 4





⇒ le p.l. sous forme standard est :



Min z = c tX avec z = 5x1 − 3x2, X =

















x1

x2

x3

x4

, C =

















5

−3

0

0





−1 1 1 0

3 0 1

2

−1 6 0 0













x1

x2

x3

x4











=







−2

4

10

X ≥ 0

Nour Houda Dougui

Recherche OpØrationnelle

23

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Tout programme linØaire se met sous forme standard ou canonique.

1 − x −

1 avec x +

1 = − min(x1, 0)

1 , x −

Si on a AX ≥ b alors AX ≥ b ⇔ −AX ≤ −b

⇔ ∃Y ≥ 0 telque − AX + Y = −b

Si une plusieurs variable n’a pas de contraintes de signe : on

suppose que x1 est de signe quelconque ⇒ on pose

x1 = x +

1 ≥ 0 et x −

et x −

X t → X (cid:48)t = (x +

⇒ Max z = C tX = C (cid:48)tX (cid:48) avec C (cid:48)t = (c1, −c1, c2, ..., cn)n+1

et AX = b ⇔ (AX )i = bi , i ∈ [1..m]

⇔ (cid:80)n

j=1 aij xj = bi , i ∈ [1..m]

⇔ ai1x1 + (cid:80)n

⇔ ai1x +

j=2 aij xj = bi , i ∈ [1..m]

1 ≥ 0 telque x +

j=2 aij xj = bi , i ∈ [1..m]

1 , x2, ..., xn)

1 − ai1x −

1 + (cid:80)n

1 = max(x1, 0)

Nour Houda Dougui

Recherche OpØrationnelle

24

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

















a11 −a11

a21 −a21

.

.

.

⇔

a12

a22

...

...

a1n

a2n

















X (cid:48) = b

am1 −am1

am2

⇒ A → A(cid:48) ∈ R(m,n+1)

... amn

Nour Houda Dougui

Recherche OpØrationnelle

25

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Plan

1 Programmmation linØaire

Introduction

RØsultats fondamentaux de la P.L.

Di(cid:27)Ørentes formes de programmes linØaires

DØ(cid:28)nitions

ThØorŁmes fondamentaux

RØsolution graphique

MØthode du Simplexe

DualitØ

2 Programmmation linØaire en nombres entiers

Nour Houda Dougui

Recherche OpØrationnelle

26

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

On considŁre un programme linØaire sous forme standard avec

n variables et m contraintes.

On suppose que A (matrice de contraintes) est de rang m. ⇔

∃ une matrice B(m,m) de A de dØt (cid:54)= 0 ⇔ les m contraintes sont

indØpendantes.

On appelle (P)







Max z = C tX

AX = b

X ≥ 0

On appelle solution admissible ou rØalisable de (P) tout vecteur

X de Rn vØri(cid:28)ant les contraintes de (P).

L’ensemble des solutions admissibles ou rØalisables est l’ensemble

des X ∈ Rn telque X ≥ 0 et AX = b.

Nour Houda Dougui

Recherche OpØrationnelle

27

Le vecteur

X = (x1 = 0, x2 = 0, x3 = 0.5, x4 = 0.5, x5 = 0.5, x6 = 0, x7 = 0.5)

est une solution rØalisable du problŁme (E). La valeur de la

fonction objectif correspendante est −0.5.

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Exemple

ProblŁme de programmation linØaire (E)

max(z) = x1 + 2x2 + 3x3 − 4x4

sous conditions :

x1 − x2 + x3 + x5 = 1

x1 − x3 − x4 + x6 = −1

x2 + x3 + x4 + x7 = 1

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0 et x7 ≥ 0.

Nour Houda Dougui

Recherche OpØrationnelle

28

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Exemple

ProblŁme de programmation linØaire (E)

max(z) = x1 + 2x2 + 3x3 − 4x4

sous conditions :

x1 − x2 + x3 + x5 = 1

x1 − x3 − x4 + x6 = −1

x2 + x3 + x4 + x7 = 1

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0 et x7 ≥ 0.

Le vecteur

X = (x1 = 0, x2 = 0, x3 = 0.5, x4 = 0.5, x5 = 0.5, x6 = 0, x7 = 0.5)

est une solution rØalisable du problŁme (E). La valeur de la

fonction objectif correspendante est −0.5.

Nour Houda Dougui

Recherche OpØrationnelle

28

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

On appelle base du problŁme (P) toute matrice B(m,m) inversible de

A.

En supposant que les m premiers vecteurs de A forment une base B

(on pourra toujours changer l’ordre des colonnes de A), on pourra

Øcrire A = (B, N) oø N(m,n−m) et B(m,m).

Une solution X rØalisable sera notØe

(cid:19)

X =

m composantes

(cid:18) XB }

XN } n − m composantes

d’oø AX = b ⇔ BXB + NXN = b

.

DØ(cid:28)nition :

Si une solution rØalisable X vØri(cid:28)e XN = 0, X est appelØe solution

rØalisable de base associØe (cid:224) la base B ⇒ X =

XB = B −1b (B base ⇒ inversible).

Nour Houda Dougui

Recherche OpØrationnelle

(cid:19)

(cid:18) XB

0

et

29

Une solution rØalisable qui maximise la fonction objectif (ou qui

minimise selon la forme du problŁme) est une solution optimale.

La valeur correspendante de la fonction objectif est la valeur

optimale du problŁme.

Exemple (E)

Le vecteur X = (x1 = 0, x2 = 0, x3 = 1, x4 = 0, x5 = 0, x6 = 0,

x7 = 0) est la solution optimale du problŁme (E). La valeur

optimale du problŁme est 3.

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Exemple (E)

Le vecteur X = (x1 = 0, x2 = 0, x3 = 0, x4 = 1, x5 = 1, x6 = 0,

x7 = 0) est une solution rØalisable de base du problŁme (E)

associØ (cid:224) la base (c4, c5, c6) (ou la base (x4, x5, x6)). La valeur de la

fonction objectif correspendante est −4.

Nour Houda Dougui

Recherche OpØrationnelle

30

Exemple (E)

Le vecteur X = (x1 = 0, x2 = 0, x3 = 1, x4 = 0, x5 = 0, x6 = 0,

x7 = 0) est la solution optimale du problŁme (E). La valeur

optimale du problŁme est 3.

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Exemple (E)

Le vecteur X = (x1 = 0, x2 = 0, x3 = 0, x4 = 1, x5 = 1, x6 = 0,

x7 = 0) est une solution rØalisable de base du problŁme (E)

associØ (cid:224) la base (c4, c5, c6) (ou la base (x4, x5, x6)). La valeur de la

fonction objectif correspendante est −4.

Une solution rØalisable qui maximise la fonction objectif (ou qui

minimise selon la forme du problŁme) est une solution optimale.

La valeur correspendante de la fonction objectif est la valeur

optimale du problŁme.

Nour Houda Dougui

Recherche OpØrationnelle

30

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Exemple (E)

Le vecteur X = (x1 = 0, x2 = 0, x3 = 0, x4 = 1, x5 = 1, x6 = 0,

x7 = 0) est une solution rØalisable de base du problŁme (E)

associØ (cid:224) la base (c4, c5, c6) (ou la base (x4, x5, x6)). La valeur de la

fonction objectif correspendante est −4.

Une solution rØalisable qui maximise la fonction objectif (ou qui

minimise selon la forme du problŁme) est une solution optimale.

La valeur correspendante de la fonction objectif est la valeur

optimale du problŁme.

Exemple (E)

Le vecteur X = (x1 = 0, x2 = 0, x3 = 1, x4 = 0, x5 = 0, x6 = 0,

x7 = 0) est la solution optimale du problŁme (E). La valeur

optimale du problŁme est 3.

Nour Houda Dougui

Recherche OpØrationnelle

30

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Exemple







Max Z = 100x1 + 200x2

s.c. :

3x1 + 4x2 ≤ 42

x1 + 3x2 ≤ 24

x1 ≥ 0, x2 ≥ 0

−→ Forme standard







Max Z = 100x1 + 200x2

s.c. :

3x1 + 4x2 + y1 = 42

x1 + 3x2 + y2 = 24

x1 ≥ 0, x2 ≥ 0, y1 ≥ 0, y2 ≥ 0

Y = (y1, y2) : vecteur des variables d’Øcart.

Nour Houda Dougui

Recherche OpØrationnelle

31

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

(cid:201)criture matricielle :







Max (z) = (100, 200, 0, 0) ×

















x1

x2

y1

y2

s.c :

(cid:18) 3 4 1 0

1 3 0 1

(cid:19)

×

















x1

x2

y1

y2

(cid:19)

=

(cid:18) 42

24

⇔







Max (z) = C tX

s.c. :

AX = b

X ≥ 0

Nour Houda Dougui

Recherche OpØrationnelle

32

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

A = [B, N] : On partitionne A en deux sous matrices.

A =

(cid:18) 3 4 1 0

1 3 0 1

(cid:19)

B est inversible et B −1 =

et B −1b =

(cid:18) 3 0

1 1

(cid:19)

0

1

⇒ B =

(cid:18) 1

3

−1

3

(cid:19)

et N =

(cid:19)

(cid:18) 4 1

3 0

(cid:18) 14

10

(cid:19)

Dans ce cas :

(cid:19)

xB =

(cid:18) x1

y2

hors base.

Ce choix donne la solution de base :

les variables de base et xN =

(cid:19)

(cid:18) x2

y1

les variables

xB =

(cid:19)

(cid:18) 14

10

et xN =

(cid:19)

(cid:18) 0

0

Nour Houda Dougui

Recherche OpØrationnelle

33

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Un choix (cid:224) rejeter :

(cid:18) 3 4 1 0

(cid:19)

1 3 0 1

A =

⇒ B =

(cid:18) 4 0

3 1

B est inversible et B −1 = 1

4

(cid:18) 1

0

−3 4

(cid:19)

(cid:19)

et N =

et B −1b =

(cid:19)

(cid:18) 3 1

1 0

(cid:18) 21

2

−30

4

(cid:19)

Remarque :

La Solution Initiale (cid:201)vidente (SIE) admet la matrice identitØ

comme base. Dans le cas de l’exemple, la (SIE) est :

xB =

(cid:18) y1

y2

(cid:19)

=

(cid:18) 42

24

(cid:19)

et xN =

(cid:18) x1

x2

(cid:19)

=

(cid:18) 0

0

(cid:19)

Nour Houda Dougui

Recherche OpØrationnelle

34

Exemple de problŁmes P.L. sans solution

Le problŁme suivant n’a aucune solution rØalisable (problŁme

non-rØalisable) :

Max 3x1 − x2

s.c. :

x1 + x2 ≤ 2

−2x1 − 2x2 ≤ −10

x1 ≥ 0, x2 ≥ 0

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Les problŁme de programmation linØaire n’ont pas tous une unique

solution optimale.

Certains problŁmes ont plusieurs solutions optimales di(cid:27)Ørentes,

d’autres n’en ont aucune.

Nour Houda Dougui

Recherche OpØrationnelle

35

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Les problŁme de programmation linØaire n’ont pas tous une unique

solution optimale.

Certains problŁmes ont plusieurs solutions optimales di(cid:27)Ørentes,

d’autres n’en ont aucune.

Exemple de problŁmes P.L. sans solution

Le problŁme suivant n’a aucune solution rØalisable (problŁme

non-rØalisable) :

Max 3x1 − x2

s.c. :

x1 + x2 ≤ 2

−2x1 − 2x2 ≤ −10

x1 ≥ 0, x2 ≥ 0

Nour Houda Dougui

Recherche OpØrationnelle

35

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Exemple de problŁmes P.L. sans solution

Le problŁme suivant a des solutions rØalisables mais aucune n’est

optimale (problŁme non-bornØ) :

Max x1 − x2

s.c. :

−2x1 + x2 ≤ −1

−x1 − 2x2 ≤ −2

x1 ≥ 0, x2 ≥ 0

∀M ∈ R, ∃ solution rØalisable tq : x1 − x2 > M

Tout problŁme de P.L. appartient (cid:224) l’une des trois catØgories :

a une solution optimale.

est non-rØalisable.

est non-bornØ

Nour Houda Dougui

Recherche OpØrationnelle

36

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

Plan

1 Programmmation linØaire

Introduction

RØsultats fondamentaux de la P.L.

Di(cid:27)Ørentes formes de programmes linØaires

DØ(cid:28)nitions

ThØorŁmes fondamentaux

RØsolution graphique

MØthode du Simplexe

DualitØ

2 Programmmation linØaire en nombres entiers

Nour Houda Dougui

Recherche OpØrationnelle

37

Programmmation linØaire

Programmmation linØaire en nombres entiers (PLNE)

Introduction

RØsultats fondamentaux de la P.L.

RØsolution graphique

MØthode du Simplexe

DualitØ

ThØorŁme

1 S’il ∃ une solution rØalisable du problŁme (P), alors ∃ une

solution rØalisable de base.

2 S’il ∃ une solution optimale du problŁme (P), alors ∃ une

solution optimale rØalisable de base.

DØmonstration :

-1- Soient A1, ..., An les n vecteurs colonnes de A et soit X une

solution rØalisable de (P). On suppose que X possŁde p

composantes strictement positives et n...