Corrigé: i) Qu'en est-il de l'algorithme dual du simplexe? L'algorithme dual du simplexe permet de passer d'une solution de base du primal à une autre qui
| Previous PDF | Next PDF |
[PDF] TD 5 Programmation linéaire et optimisation Dualité Exercice 1 - grug
Corrigé: i) Qu'en est-il de l'algorithme dual du simplexe? L'algorithme dual du simplexe permet de passer d'une solution de base du primal à une autre qui
[PDF] 174 EXERCICES SUPPLÉMENTAIRES — PARTIE II
Exercice 4 5 2 [Pivots] Pour s'exercer avec l'opération de pivot du simplexe, Selon la table 4 6, les variables du dual sont libres et ses contraintes sont de type
[PDF] SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual
DUAL : Le nombre de variables est déterminé par le nombre de contrainte du primal Excel dans son algorithme du simplexe utilise une construction du dual
[PDF] CORRIGE du TD N°3 : PROGRAMMATION LINEAIRE EXERCICE 1
EXERCICE 1 : corrigé Ecrivons le dual du programme primal de la question précédente Il s'agit du simplexe obtenu lors de la résolution du dual Le plan
[PDF] 1 Programmation linéaire
Document 4 : Corrigé des exercices d'optimisation linéaire 1 Programmation Le tableau de départ pour la méthode du simplexe est donc : x1 x2 x3 x4 x5 3
[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 (a) Appliquez la phase I du simplexe au probl`eme (P) pour montrer qu'il exercice 1 : Écrire le dual du programme linéaire suivant :
[PDF] Examen et corrigé
30 mai 2012 · Corrigé 1 1 Exercice 2 Application de la méthode du simplexe (10 points) Mettre le probl`eme dual (D) sous forme standard (DS) 3
[PDF] Exercice 121 Résoudre par le simplexe Max x1 + 2x2 sous −3x1
2) Tableau du simplexe (forme canonique ) x1 x2 x3 x4 x5 z b -1 -2 0 0 0 -1 0 - 3
[PDF] Exercices corrigés PROGRAMMATION LINÉAIRE
Optimisation discrète, Séance 5 : Exercices corrigés Déf 4 G Tableau du Simplexe : on ajoute au système des contraintes une ligne Algorithme dual
[PDF] Série 1: Programmation linéaire
Pour chaque exercice, formuler le probl`eme de programmation linéaire et le résoudre Dans les exercices suivants, appliquer l'algorithme du simplexe pour Ecrire le probl`eme dual de chacun des programmes linéaires étudiés dans
[PDF] exercices corrigés en recherche opérationnelle dualité
[PDF] programmation linéaire dualité exercices corrigés pdf
[PDF] cice et aide ? l'embauche pme
[PDF] aide embauche pme heures supplémentaires
[PDF] structure par âge de la population mondiale
[PDF] prolongation aide embauche pme 2017
[PDF] structure démographique définition
[PDF] aide embauche pme batiment
[PDF] composition de la population mondiale
[PDF] aide embauche pme renouvellement cdd
[PDF] structure par age definition
[PDF] cumul aide embauche pme
[PDF] rsa socle et prime d'activité cumulable
[PDF] rsa et reprise d'activité 2017
TD 5 Programmation linéaire et optimisation
Dualité
Exercice 1 : Donner le dual du primal suivant :
Primal Dual
a) Max Z = 2x1 + 4x2 + 3x33x1 + 4x2 + 2x3 60
2x1 + x2 + 2x3 40
x1 + 3x2 + 2x3 80 x1, x2, x3 0 b) Min Z = 20x1 + 24x2 x1 + x2 30 x1 + 2x2 40 x1, x2 0 c) Max Z = 10x1 + 6x2 x1 + 4x2 403x1 + 2x2 = 60
2x1 + x2 25
x1, x2 0Corrigé:
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 permet à chaque itération de passer d'une solution de base
réalisable pour le primal à une autre jusqu'à ce que les conditions d'optimalité soient satisfaites: un
vecteur de coût relatif dont les composantes sont non négatives. i) Qu'en est-il de l'algorithme dual du simplexe? ii) Qu'en est-il de l'algorithme primal-dual?Corrigé:
i) Qu'en est-il de l'algorithme dual du simplexe?L'algorithme dual du simplexe permet de passer d'une solution de base du primal à une autre qui satisfait
aux conditions d'optimalité: un vecteur de coût relatif dont les composantes sont non négatives.
L'algorithme termine lorsque la solution de base est réalisable pour le primal. ii) Qu'en est-il de l'algorithme primal-dual?L'algorithme primal-dual permet de passer à chaque itération d'une solution réalisable pour le problème
dual à une autre, et d'une solution irréalisable pour le primal qui satisfait aux conditions d'optimalité (le
théorème des écarts complémentaires) à une autre. L'algorithme termine lorsque la solution primale est
réalisable. c) Min w = 40y1 + 60y2 - 25y3 y1 + 3y2 - 2y3 104y1 + 2y2 - y3 6
y1 0, y3 0, y2 quelconque a) Min w = 60y1 + 40y2 + 80y33y1 + 2y2 + y3 2
4y1 + y2 + 3y3 4
2y1 + 2y2 + 2y3 3
y1 0, y2 , y3 0 b) Max w = 30y1 + 40y2 y1 + y2 20 y1 + 2y2 24 y1 0, y3 0Exercice 3
Max Z = 40x1 + 50x2
5x1 + 4x2 80
x1 + 2x2 243x1 + 2x2 36
x1, x2 01- Donner le dual PL
de ce primal PL2- Résoudre le primal PL par le simplexe ou graphiquement
3- Déduire la solution du dual PL
Corrigé:
1. Donner le dual PL
de ce primal PLMin w=80y1 + 24y2 + 36y3
5y1+y2+3y3 40
4y1+2y2+2y3 50
y1,y2,y302. Résoudre le primal PL par le simplexe ou graphiquement
z - 40x 1 - 50x 2 - 0s 1 - 0s 2 - 0s 3 = 0 5x 1 + 4x 2 + s 1 = 80 x 1 + 2x 2 +s 2 = 24 3x 1 + 2x 2 +s 3 = 36 x 1 0, x 2 0 x 1 x 2 s 1 s 2 s 3 bi ratio base5 4 1 0 0 80 80/4 s
11 2 0 1 0 24 24/2 s
23 2 0 0 1 36 36/2 s
3 -40 -50 0 0 0 0 x 1 x 2 s 1 s 2 s 3 bi ratio base3 0 1 -2 0 32 32/3 s
11/2 1 0 1/2 0 12 12*2 x
22 0 0 -1 1 12 12/2 s
3 -15 0 0 25 0 600 x 1 x 2 s 1 s 2 s 3 bi ratio base0 0 1 -1/2 -3/2 14 s
10 1 0 3/4 -1/4 9 x
21 0 0 -1/2 1/2 6 x
10 0 0 17.5=35/27.5=15/2690
La solution est :
x 1 = 6, x 2 = 9, s 1 =14, s 2 = 0, s 3 = 0 z = 6903. Déduire la solution du dual PL
A l'optimum, le primal et le dual sont liés par les règles suivantes: - les fonctions objectifs z et w ont la même valeur optimale z=cx* = y*b=w- la valeur marginale d'une variable dans un programme est égale à l'opposé de la valeur optimale de la
variable associée dans l'autre programme et réciproquement - les variables du primal (x 1 , x 2 ), étant toutes différentes de 0, alors les contraintes associées du dual sont saturées, d'où pour le dual à résoudre: