[PDF] [PDF] Optimisation linéaire La dualité

[PDF] Optimisation linéaire La dualité

1 Optimisation linéaire Recherche opérationnelle GC-SIE La dualité contrainte du problème de départ Dualité Michel Bierlaire 7 Introduction

[PDF] 174 EXERCICES SUPPLÉMENTAIRES — PARTIE II

L'algorithme du simplexe recherche itérativement une La dualité faible affirme que si les programmes primal et dual ont la même valeur de fonction

[PDF] Chapitre 4 Dualité

Dualité 4 1 Problème dual On suppose que A est une matrice de format m × n et b ∈ Rm A chaque problème d'optimisation linéaire, nous allons définir un 

[PDF] Recherche opérationnelle et applications

Une solution optimale est une solution admissible qui optimise la fonction objectif Définition 3 (Modèle de recherche opérationnelle) Maximiser ou minimiser ( 

[PDF] Programmation linéaire et recherche opérationnelle - LIM

maximiser le profit obtenu apr`es deux ans? 3/56 Introduction Méthode graphique Simplexe Dualité Des probl 

[PDF] FSJES-AC RECHERCHE OPERATIONNELLE Semestre 6 Filière

PROGRAMMATION LINEAIRE - Complément – - Partie III : Algorithme du simplexe - Partie IV : Post – Optimalité • Dualité • Analyse de sensibilité - Exercices 

[PDF] Exercices de Programmation Linéaire – Modélisation –

exercice 1 : On veut préparer 500 litres de punch `a partir de cinq boissons A, B, C, D et E Le punch doit comporter au moins 20 de Dualité – exercice 1 : Écrire le dual du programme linéaire suivant : Le four est opérationnel 6 heures 

[PDF] - Exercices de TD - 1 Modélisation - LIRMM

Formuler le probl`eme de la recherche d'un plan de production maximisant le chiffre Le but de cet exercice est la recherche d'une stratégie mixte optimale pour le 6 Dualité - Exercice 50 - Piles, suite et fin Suite de l'Exercice 1 a Ecrire le 

[PDF] 1 Programmation linéaire

Document 4 : Corrigé des exercices d'optimisation linéaire On introduit 3 variables positives x1,a,x2,a,x3,a dans les contraintes et on cherche à minimiser la 

[PDF] Modèles de Recherche Opérationnelle - Département d

Département d'Informatique et de Recherche Opérationnelle 4 5 Exercices DUALITÉ 25 2 5 6 Variables à valeurs quelconques Si une variable xj peut 

[PDF] exercices corrigés espérance conditionnelle

[PDF] exercices corrigés essais mécaniques

[PDF] exercices corrigés et illustrations en matlab et octave pdf

[PDF] exercices corrigés fiabilité des systèmes

[PDF] exercices corrigés fifo lifo cmup pdf

[PDF] exercices corrigés files d'attente

[PDF] exercices corrigés fiscalité

[PDF] exercices corrigés fiscalité sénégalaise

[PDF] exercices corrigés fonctions numériques terminale s pdf

[PDF] exercices corrigés forces de frottement

[PDF] exercices corrigés fractions

[PDF] exercices corrigés génétique humaine

[PDF] exercices corrigés génie chimique pdf

[PDF] exercices corrigés géométrie dans l'espace terminale s pdf

[PDF] exercices corrigés géométrie des molécules

1 hƦƷźƒźƭğƷźƚƓ ƌźƓĽğźƩĻ wĻĭŷĻƩĭŷĻ ƚƦĽƩğƷźƚƓƓĻƌƌĻ

D/Ώ{L9

2

•...Ɠ ƚƩźŭźƓğƌ ƚŅŅƩĻ Ġ ǒƓ ğƌƦźƓźƭƷĻ ǒƓ ƦƩźǣ ƌźĽ Ġ ƌ͸ğƌƷźƷǒķĻ ƨǒ͸źƌ ƦĻǒƷ ğƷƷĻźƓķƩĻ ʹ ЊC Ή ƒļƷƩĻ͵

•/ĻƦĻƓķğƓƷͲ źƌ ƌǒź źƒƦƚƭĻ ķĻ ƩĻƭƷĻƩ ĻƓ CƩğƓĭĻ͵

•[ğ ƭƚƌǒƷźƚƓ ƚƦƷźƒğƌĻ ƦƚǒƩ ƌ͸ğƌƦźƓźƭƷĻ ĻƭƷ ķĻ ŭƩźƒƦĻƩ ƭǒƩ ƌĻ aƚƓƷ .ƌğƓĭ ʹ ЍБЉАƒ͵

DualitéMichel Bierlaire3

3

Ʀğƭ ķ͸ľƷƩĻ ĭƚƓƷƩğźƓƷ Ġ ƩĻƭƷĻƩ ĻƓ CƩğƓĭĻ͵

ƨǒźƷƷĻƩ ƌğ CƩğƓĭĻ͵

•{ź ƌĻ ƒƚƓƷğƓƷ ķĻ ƌ͸ğƒĻƓķĻ ĻƭƷ ƷƩƚƦ ƦĻǒ ĽƌĻǝĽͲ ƌ͸ğƌƦźƓźƭƷĻ Ġ źƓƷĽƩľƷ Ġ ŭƩźƒƦĻƩ ƭǒƩ ƌĻ aƚƓƷ 9ǝĻƩĻƭƷ ʹ

DualitéMichel Bierlaire5

4 •{ź ƌ͸ğƒĻƓķĻ ĻƭƷ ķĻ ЍЉЍЊ C

•DƩźƒƦĻƩ ƭǒƩ ƌĻ aƚƓƷ .ƌğƓĭ ƌǒź ƩğƦƦƚƩƷĻ ЍБЉА C

•DƩźƒƦĻƩ ƭǒƩ ƌĻ aƚƓƷ 9ǝĻƩĻƭƷ ƌǒź ƩğƦƦƚƩƷĻ ББЍБ C Α ЍЉЍЊ C ў ЍБЉА C

DualitéMichel Bierlaire7

aƚķĽƌźƭğƷźƚƓ ʹ •tƩĻƒźĻƩ ƦƩƚĬƌļƒĻ ʹ -ƭƚǒƭ ĭƚƓƷƩğźƓƷĻ ǣ ÎCƩğƓĭĻ

DualitéMichel Bierlaire8

5

•hƓ źƓƷƩƚķǒźƷ ǒƓ ƦƩźǣ Ʀ ğƭƭƚĭźĽ Ġ ƌğ ĭƚƓƷƩğźƓƷĻ

DualitéMichel Bierlaire9

bƚƷĻƭ ʹ

DualitéMichel Bierlaire10

6

DualitéMichel Bierlaire11

•5ğƓƭ ĭĻ ĭğƭͲ ƚƓ ğ źƓƷĽƩľƷ Ġ ǝźƚƌĻƩ ƌğ ĭƚƓƷƩğźƓƷĻ ķǒ ƦƩƚĬƌļƒĻ źƓźƷźğƌ ƦƚǒƩ ƚĬƷĻƓźƩ ǒƓ ƒĻźƌƌĻǒƩ ĭƚǕƷ͵

DualitéMichel Bierlaire12

7

DualitéMichel Bierlaire13

•5ğƓƭ ĭĻ ĭğƭͲ ƌĻ ƦƩƚĬƌļƒĻ ķĻǝźĻƓƷ ƓƚƓ ĬƚƩƓĽ͵ [Ļ ƦƩźǣ ĻƭƷ ĭĻƩƷğźƓĻƒĻƓƷ ƓƚƓ ğķğƦƷĽ͵

•/ƚƒƒĻƓƷ ͪ 9Ɠ ƒĻƷƷğƓƷ ķĻƭ ĭƚƓƷƩğźƓƷĻƭ ƭǒƩ ƌĻƭ ƦƩźǣ͵

DualitéMichel Bierlaire14

8

DualitéMichel Bierlaire15

•5ğƓƭ ĭĻ ĭğƭͲ ƨǒĻƌƨǒĻ ƭƚźƷ ƌğ ǝğƌĻǒƩ ķĻ ǤͲ Ʀğƭ ƒƚǤĻƓ ķ͸ƚĬƷĻƓźƩ ǒƓ ĭƚǕƷ ƒĻźƌƌĻǒƩ ƨǒĻ ƌĻ ĭƚǕƷ ƚƦƷźƒğƌ ķǒ ƦƩƚĬƌļƒĻ źƓźƷźğƌ͵

•Lƌ Ɠ͸Ǥ ğ ğǒĭǒƓ ğǝğƓƷğŭĻ Ġ ƌğ ǝźƚƌĻƩ͵

DualitéMichel Bierlaire16

9

LķĽĻ ʹ

•LƓƷĻƩķźƩĻ ƌĻƭ ƦƩźǣ ƨǒź ƩĻƓķĻƓƷ ƌĻ ƦƩƚĬƌļƒĻ ƓƚƓ ĬƚƩƓĽ͵

DualitéMichel Bierlaire17

•hƓ ğ ƷƚǒƆƚǒƩƭ ŭΛƦΜ £ĭΫ͵

•hƓ ķĽƭźƩĻ ƷƩƚǒǝĻƩ ƌĻƭ ƦƩźǣ ƦƚǒƩ ƨǒĻ ƌ͸ğǝğƓƷğŭĻ ƌźĽ Ġ ƌğ

•hƓ ķƚźƷ ķƚƓĭ ƷƩƚǒǝĻƩ Ʀ ƨǒź

DualitéMichel Bierlaire18

10

DualitéMichel Bierlaire19

■Il est appelé le problème primal. ■Le problème relaxé est

DualitéMichel Bierlaire20

11

•hƓ ǝĻǒƷ ƒğźƓƷĻƓğƓƷ ĭğƌĭǒƌĻƩ ƌĻ ƦƩźǣ ƷĻƌ ƨǒĻ ŭΛƦΜ ƭƚźƷ

•9Ɠ ƦƩƚŭƩğƒƒğƷźƚƓ ƌźƓĽğźƩĻͲ ƚƓ ğƩƩźǝĻ Ġ ƷƩƚǒǝĻƩ ƦΫ ƦƚǒƩ ƨǒĻ

DualitéMichel Bierlaire21

•wĽƭƚǒķƩĻ ƌĻ ƦƩƚĬƌļƒĻ ƩĻƌğǣĽ ĻƭƷ ķƚƓĭ ĽƨǒźǝğƌĻƓƷ Ġ ƩĽƭƚǒķƩĻ ƌĻ ƦƩƚĬƌļƒĻ ƦƩźƒğƌ͵

•vǒĻƭƷźƚƓ ʹ ĭƚƒƒĻƓƷ ķĽƷĻƩƒźƓĻƩ ƦΫ ͪ

DualitéMichel Bierlaire22

12

DualitéMichel Bierlaire23

cas à éviter

•tƚǒƩ ĽǝźƷĻƩ ƌĻ ĭğƭ ƷƩźǝźğƌ ƚǓ ƌĻ ƦƩƚĬƌļƒĻ ĻƭƷ ƓƚƓ ĬƚƩƓĽͲ ƚƓ źƒƦƚƭĻ

DualitéMichel Bierlaire24

13

•Lƌ ƭ͸ğŭźƷ ķ͸ǒƓ ƦƩƚŭƩğƒƒĻ ƌźƓĽğźƩĻ͵

•Lƌ ĻƭƷ ğƦƦĻƌĽ ƌĻ

DualitéMichel Bierlaire25

bƚƷĻ ʹ

5ĽŅźƓźƷźƚƓ ʹ

DualitéMichel Bierlaire26

max pTb s.c. A

Tp £c

min cTx s.c. Ax = b x ³0DualPrimal 14

•LƓƷƩƚķǒźƭƚƓƭ ƌĻƭ ǝğƩźğĬƌĻƭ ķ͸ĽĭğƩƷ

DualitéMichel Bierlaire27

DualitéMichel Bierlaire28

15 •hƓ ƚĬƷźĻƓƷ ƌĻ ƦƩƚĬƌļƒĻ

ƭ͵ĭ͵ Cǩ =Ĭ

•C ў Λ! Ό LΜ

DualitéMichel Bierlaire29

•tƩƚĬƌļƒĻ ķǒğƌ

ƭ͵ĭ͵ C

•C ў Λ! Ό LΜ

DualitéMichel Bierlaire30

16 bƚƷĻ ʹ

•9Ɠ ƦƩĽƭĻƓĭĻ ķĻ ĭƚƓƷƩğźƓƷĻƭ ķ͸źƓĽŭğƌźƷĽͲ źƌ ŅğǒƷ źƒƦƚƭĻƩ ǒƓĻ ĭƚƓƷƩğźƓƷĻ ķĻ ƭźŭƓĻ ƭǒƩ ƌĻƭ ƦƩźǣ͵

DualitéMichel Bierlaire31

max pTb s.c. A

Tp £c

p £0 min cTx s.c. Ax £b x ³0DualPrimal

ǣ ÎLwƓ

DualitéMichel Bierlaire32

17

DualitéMichel Bierlaire33

•tƚǒƩ ĽǝźƷĻƩ ƌĻ ĭğƭ ƷƩźǝźğƌ ƚǓ ƌĻ ƦƩƚĬƌļƒĻ ĻƭƷ ƓƚƓ ĬƚƩƓĽͲ ƚƓ źƒƦƚƭĻ

DualitéMichel Bierlaire34

18

DualitéMichel Bierlaire35

max pTb s.c. A Tp =c min cTx s.c. Ax = b x ÎIR n

DualPrimal

wĽƭǒƒĽ ʹ

•hƓ ķźƭƦƚƭĻ ķ͸ǒƓ ǝĻĭƷĻǒƩ ķĻ ƦƩźǣ Ʀ ΛƌĻƭ ǝğƩźğĬƌĻƭ

•tƚǒƩ ĭŷğƨǒĻ ƦͲ ƚƓ ƦĻǒƷ ƚĬƷĻƓźƩ ǒƓĻ ĬƚƩƓĻ źƓŅĽƩźĻǒƩĻ ƭǒƩ ƌĻ ĭƚǕƷ ƚƦƷźƒğƌ ķǒ ƦƩźƒğƌ͵

•tƚǒƩ ĭĻƩƷğźƓƭ ƦͲ ƌğ ĬƚƩƓĻ ĻƭƷ -¥Ͳ ĻƷ Ɠ͸ğƦƦƚƩƷĻ

DualitéMichel Bierlaire36

19 wĽƭǒƒĽ ΛƭǒźƷĻΜ ʹ

•hƓ ƒğǣźƒźƭĻ ǒƓźƨǒĻƒĻƓƷ ƭǒƩ ƌĻƭ Ʀ ƨǒź ƦƩƚķǒźƭĻƓƷ ǒƓĻ ĬƚƩƓĻ ŅźƓźĻ͵

DualitéMichel Bierlaire37

•bƚƷƚƓƭ ğźƌĻƭ ƌźŭƓĻƭ ķĻ ƌğ ƒğƷƩźĭĻ

•bƚƷƚƓƭ !źƌĻƭ ĭƚƌƚƓƓĻƭ ķĻ ƌğ ƒğƷƩźĭĻ

DualitéMichel Bierlaire38

20

DualitéMichel Bierlaire39

PRIMALDUAL

DualitéMichel Bierlaire40

PRIMAL minmax DUAL

³bi³0

contraintes£bi£ 0variables = bilibre

³0£cj

variables£0³cjcontraintes libre= cj 21

9ǣĻƒƦƌĻ

•tğƭƭĻƩ ķǒ ƦƩźƒğƌ ğǒ ķǒğƌ

DualitéMichel Bierlaire41

9ǣĻƒƦƌĻ

DualitéMichel Bierlaire42

22

9ǣĻƒƦƌĻ

DualitéMichel Bierlaire43

9ǣĻƒƦƌĻ

DualitéMichel Bierlaire44

■C"est le problème de départ. 23

•{ƚźƷ ǒƓ ƦƩƚŭƩğƒƒĻ ƌźƓĽğźƩĻ t͵ {ƚźƷ 5 ƭƚƓ ķǒğƌ͵ [Ļ ķǒğƌ ķĻ 5 ĻƭƷ ƌĻ ƦƩƚŭƩğƒƒĻ t͵

DualitéMichel Bierlaire45

DualitéMichel Bierlaire46

■Introduisons les variables d"écart dans le primal, et déterminons le dual

PrimalDual

min cTx s.c. Ax ³b x ÎIR M1 N3 max pTb s.c. p ³0 A

Tp = c

24

•wĻƒƦƌğIJƚƓƭ ƒğźƓƷĻƓğƓƷ ƌĻƭ ǝğƩźğĬƌĻƭ ķǒ ƦƩƚĬƌļƒĻ ƚƩźŭźƓğƌ ƦğƩ ķĻƭ ǝğƩźğĬƌĻƭ ƦƚƭźƷźǝĻƭ ʹ ǣўǣњ-ǣΏ

DualitéMichel Bierlaire47

quotesdbs_dbs2.pdfusesText_3