[PDF] Dualité en Programmation Linéaire Algorithmes primal et

Ecrire le dual de ce problème A-t-il une solution réalisable ? Confirmer votre réponse en résolvant (P) par l'algorithme du simplexe Que se

lité de la programmation linéaire, l'algorithme du simplexe révisé, les notions de La dualité faible affirme que si les programmes primal et dual ont la même Exercice 4 10 5 [Deux phases] Proposez une méthode, utilisant deux phases,

[PDF] TD 5 Programmation linéaire et optimisation Dualité Exercice 1 - grug

Corrigé: Exercice 2 Dans le cas d'un problème de programmation linéaire ( minimisation) possédant une solution optimale finie, l'algorithme primal du simplexe

[PDF] Dualité en Programmation Linéaire Algorithmes primal et - ENSIIE

Ecrire le dual de ce problème A-t-il une solution réalisable ? Confirmer votre réponse en résolvant (P) par l'algorithme du simplexe Que se

[PDF] 1 Programmation linéaire

Document 4 : Corrigé des exercices d'optimisation linéaire simplexe Programme 1 Le tableau de départ pour la méthode du simplexe est donc : x1 x2

[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 exercice 1 : Résoudre le programme linéaire suivant par la méthode du simplexe (a) Appliquez la phase I du simplexe au probl`eme (P) pour montrer qu'il admet Dualité – exercice 1 : Écrire le dual du programme linéaire suivant :

[PDF] Exercices corrigés PROGRAMMATION LINÉAIRE

où on reconnaît l'optimum : H“ ou HVP ne pouvant être augmentée Méthode des Tableaux Déf 4 G Tableau du Simplexe : on ajoute au système des contraintes

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

Traduire par un programme linéaire en forme canonique Maximiser le gain de l'année par la méthode du simplexe 6 Dualité - Exercice 50 - Piles, suite et fin Suite de l'Exercice 1 a Ecrire le dual (D) du programme linéaire de l'exercice

[PDF] Programmation linéaire et recherche opérationnelle Recherche

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

[PDF] Série 1: Programmation linéaire

Dans les exercices suivants, appliquer l'algorithme du simplexe pour résoudre le probl`eme de programmation linéaire Exercice 8 Une solution de base

[PDF] dualité Exercice 2 - Cedric-Cnam

Exercice 1 : dualité Formuler le problème dual de chacun des programmes linéaires suivants : Résoudre le programme linéaire suivant graphiquement : min 4x1 + 5x2 Résoudre ce PL par l'algorithme du simplexe : à chaque itération, on

Dualité en Programmation Linéaire

Algorithmes primal et dual du simplexe

Alain Faye

Option 3A

Optimisation 1

1 Plan

Dualité lagrangienne (rappels)

Programmation linéaire et dualité

DĠfinition du dual d'un programme linĠaire

Théorème de dualité forte

Algorithmes primal et dual du simplexe

Annexes

Interprétation des variables duales

Théorème des écarts complémentaires

2 3

Dualité lagrangienne

avec ܴܺ

Problème Primal

Fonction de Lagrange

Fonction duale

Problème Dual

Dualité lagrangienne

Théorème de dualité

Soit ݔܺכ

et כǡכ tels que:

Corollaire

5 6

Programmation Linéaire et dualité

96coût

unités 10unités 5C vitamine unités 20unités 30B vitamine unités 5unités 20A vitamine

2 elaboratoir1 elaboratoirpoudre de 100g

Il lui faut au moins

25 unités de vitamine A

60 unités de vitamine B

15 unités de vitamine C

Pb du pharmacien ͗ fournir une potion contenant un minimum d'unitĠs en vitamines A, B, C en utilisant les poudres fournies par 2 laboratoires 8

96coût

unités 10unités 5C vitamine unités 20unités 30B vitamine unités 5unités 20A vitamine

2 elaboratoir1 elaboratoirpoudre de 100g

Il lui faut au moins

25 unités de vitamine A

60 unités de vitamine B

15 unités de vitamine C

Pb du pharmacien ͗ fournir une potion contenant un minimum d'unitĠs en vitamines A, B, C en utilisant les poudres fournies par 2 laboratoires tt t t t 00 15105

602030

25520
s.c. 96min
21
21
21
21
21
xx xx xx xx xx

Quelques solutions

x1 = 3, x2 = 0, z = 18 x1 = 2, x2 = 1, z = 21 Ce sont des solutions sous-optimales donc majorantsde la valeur optimale z* zΎ ч 18

Comment obtenir des minorants?

͍ ч zΎ

Majorants et minorants

3/10 ×la contrainte vit.A7,5 ч 6 ǆ1+ 3/2 x2ч 6 ǆ1+ 9 x2= z

Donc 7,5 ч zΎ

3/20 ×vit.A+ 1/10 ×vit.B75ͬ20 н 6 ч 6 ǆ1+ (15/20 + 2) x2ч 6 ǆ1+ 9 x2= z

Donc 3,75 н 6 с 9,75 ч zΎ

2/10 ×la contrainte vit.B12 ч 6 ǆ1+ 4 x2ч 6 ǆ1+ 9 x2= z

Donc 12 ч zΎ

On sait dèjàque 12 ч zΎ ч 18

Peut-on faire mieux ?

Généralisons cette approche

Introduisons les variables

yAш0 , yBш0 , yCш0

25 ч 20 ǆ1+ 5 x2×yA60 ч 30 ǆ1+ 20 x2×yB15 ч 5 ǆ1+ 10 x2×yC

25 yA+ 60 yB+ 15 yCч ǆ1(20 yA+ 30 yB+ 5 yC) + x2(5 yA+ 20 yB+ 10 yC)

On impose

20 yA+ 30 yB+ 5 yCч 6(1)

5 yA+ 20 yB+ 10 yCч 9(2)

On a alors

25 yA+ 60 yB+ 15 yCч 6 ǆ1+ 9 x2= z

maximiser 25 yA+ 60 yB+ 15 yCsous contraintes (1) , (2) et avec yAш0 , yBш0 , yCш0 11

Résumons

Problème primal (P)

s.c. ൝σ௝ୀଵ௡ܽ௜௝ݔ௝൒ܾ

Problème dual (D)

s.c. ൝σ௜ୀଵ௠ܽ௜௝ݕ௜൑ܿ tt t t t 00 15105

602030

25520
s.c. 96min
21
21
21
21
21
xx xx xx xx xxquotesdbs_dbs20.pdfusesText_26

[PDF] [PDF] Dualité en Programmation Linéaire Algorithmes primal et - ENSIIE

Dualité en Programmation Linéaire

Algorithmes primal et dual du simplexe

Alain Faye

Option 3A

Optimisation 1

Dualité lagrangienne (rappels)

Programmation linéaire et dualité

DĠfinition du dual d'un programme linĠaire

Théorème de dualité forte

Algorithmes primal et dual du simplexe

Annexes

Interprétation des variables duales

Théorème des écarts complémentaires

Dualité lagrangienne

Dualité lagrangienne

Problème Primal

Fonction de Lagrange

Fonction duale

Problème Dual

Dualité lagrangienne

Théorème de dualité

Soit ݔܺכ

Corollaire

Programmation Linéaire et dualité

96coût

2 elaboratoir1 elaboratoirpoudre de 100g

Il lui faut au moins

25 unités de vitamine A

60 unités de vitamine B

15 unités de vitamine C

96coût

2 elaboratoir1 elaboratoirpoudre de 100g

Il lui faut au moins

25 unités de vitamine A

60 unités de vitamine B

15 unités de vitamine C

602030

Quelques solutions

Comment obtenir des minorants?

͍ ч zΎ

Majorants et minorants

3/10 ×la contrainte vit.A7,5 ч 6 ǆ1+ 3/2 x2ч 6 ǆ1+ 9 x2= z

Donc 7,5 ч zΎ

3/20 ×vit.A+ 1/10 ×vit.B75ͬ20 н 6 ч 6 ǆ1+ (15/20 + 2) x2ч 6 ǆ1+ 9 x2= z

Donc 3,75 н 6 с 9,75 ч zΎ

2/10 ×la contrainte vit.B12 ч 6 ǆ1+ 4 x2ч 6 ǆ1+ 9 x2= z

Donc 12 ч zΎ

On sait dèjàque 12 ч zΎ ч 18

Peut-on faire mieux ?

Généralisons cette approche

Introduisons les variables

25 ч 20 ǆ1+ 5 x2×yA60 ч 30 ǆ1+ 20 x2×yB15 ч 5 ǆ1+ 10 x2×yC

25 yA+ 60 yB+ 15 yCч ǆ1(20 yA+ 30 yB+ 5 yC) + x2(5 yA+ 20 yB+ 10 yC)

On impose

20 yA+ 30 yB+ 5 yCч 6(1)

5 yA+ 20 yB+ 10 yCч 9(2)

On a alors

25 yA+ 60 yB+ 15 yCч 6 ǆ1+ 9 x2= z

Résumons

Problème primal (P)

Problème dual (D)

602030