Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 28-12-2009 15:55:43
- SébastienB
- Membre
- Lieu : Annecy
- Inscription : 16-06-2008
- Messages : 55
Théorème des écarts complémentaires
Salut BibM@th !
Bonnes fêtes de fin d'année.
Voila ce qui m'amènes:
maximiser:
[tex]z = 80x_{1,1} + 140x_{1,2} + 110x_{1,3} + 40x_{2,1} + 120x_{2,2} + 70x_{2,3} + 60x_{3,1} + 130x_{3,2} + 90x_{3,3}[/tex]
sous:
[tex]\begin{cases}x_{1,1} + x_{1,2} + x_{1,3} \le 480 & \text{(y1)}\\ x_{2,1} + x_{2,2} + x_{2,3} \le 400 & \text{(y2)}\\ x_{3,1} + x_{3,2} + x_{3,3} \le 230 & \text{(y3)} \\ x_{1,2} + x_{2,2} + x_{3,2} \le 420 & \text{(y4)} \\ x_{1,3} + x_{2,3} + x_{3,3} \le 250 & \text{(y5)} \end{cases}[/tex]
[tex]x_{1,1} \ge 0 , x_{1,2} \ge 0 , x_{1,3} \ge 0 , x_{2,1} \ge 0 , x_{2,2} \ge 0 , x_{2,3} \ge 0 , x_{3,1} \ge 0 , x_{3,2} \ge 0 , x_{3,3} \ge 0[/tex]
La représentation duale de ce programme linéaire est plus simple si je ne me trompes pas:
minimiser:
[tex]w = 480y1 + 400y2 + 230y3 + 420y4 + 250y5[/tex]
sous:
[tex]\begin{cases}y1 & \ge 80 \\ y1 + y4 & \ge 140 \\ y1 + y5 & \ge 110 \\ y2 & \ge 40 \\ y2 + y4 & \ge 120 \\ y2 + y5 & \ge 70 \\ y3 & \ge 60 \\ y3 + y4 & \ge 130 \\ y3 + y5 & \ge 90 \end{cases}[/tex]
[tex]y1 \ge 0 , y2 \ge 0 , y3 \ge 0 , y4 \ge 0 , y5 \ge 0[/tex]
La question est de savoir si [tex] 440x_{1,1} + 20x_{1,2} + 20x_{1,3} + 400x_{2,2} + 230x_{3,3}[/tex] (cela fait 108900) est optimale à l'aide du théorème des écarts complémentaires ?
La résolution par le simplex à l'aide d'un logiciel donne:
MAX Z = 109100.0000
VARIABLES DE DÉCISION
Variable Valeur Couts réduits
------------------------------------------------------
x11 230.0000 0.0000
x12 0.0000 -10.0000
x13 250.0000 0.0000
x21 0.0000 -10.0000
x22 400.0000 0.0000
x23 0.0000 -10.0000
x31 210.0000 0.0000
x32 20.0000 0.0000
x33 0.0000 0.0000
------------------------------------------------------
CONTRAINTES
Contrainte Elasticicité? Couts marginaux
------------------------------------------------------
c1 0.0000 80.0000
c2 0.0000 50.0000
c3 0.0000 60.0000
c4 0.0000 70.0000
c5 0.0000 30.0000
------------------------------------------------------
Au passage, savez vous ce que signifient "Couts réduits", "Elasticité" et "Couts marginaux" dans cette solution ?
Et la réponse à la question est : bien sur que non car l'optimum a été trouvé pour une valeur de 109100 avec [tex]230x_{1,1}, 250x_{1,3}, 400x_{2,2}, 210x_{3,1} \text{et} 20x_{3,2}[/tex] mais auriez vous le théorème des écarts complémentaires s'il vous plaît ? et surtout pourriez vous me l'expliquer ?
Merci d'avance
@+
Hors ligne
#2 28-12-2009 17:47:02
- freddy
- Membre chevronné
- Lieu : Paris
- Inscription : 27-03-2009
- Messages : 7 457
Re : Théorème des écarts complémentaires
Salut,
c'est un résultat assez classique en matière d'optimisation linéaire sous contrainte
Si le lien ci dessous fonctionne, tu auras tout compris.
www.tsi.enst.fr/~gfort/Enseignement/MDI102/Slides3Optim.pdf
Bonne lecture.
Hors ligne
#3 30-12-2009 12:01:06
- SébastienB
- Membre
- Lieu : Annecy
- Inscription : 16-06-2008
- Messages : 55
Re : Théorème des écarts complémentaires
Bonjour,
Merci pour les slides.
Dans cet exercice, les 5 contraintes primales sont saturées car [tex]y^*_i > 0[/tex].
De plus, [tex]\forall a_{ij}, a=1[/tex].
Pour [tex]z = 108900 = w[/tex] on a [tex]x^* = (440,20,20,0,400,0,0,0,230)[/tex] et [tex]y^* = (80,50,70,70,20)[/tex].
Or dans [tex]y^*[/tex], la 3è contrainte n'est pas respectée [tex]80 + 20 \gneq 110[/tex]
[tex]\begin{cases}y_3^*(b_3 - \sum_{j=1}^{n} a_{ij} x_j^*) = 0 \\ x_3^*(c_3 - \sum_{i=1}^{m}y_i^* a_{ij}) \neq 0 \end{cases}[/tex]
[tex]\begin{cases} 70 ( 230 - (0 + 0 + 230 )) = 0 \\ 20 ( 110 - ((y1 = 80) + (y5 = 20))) \neq 0 \end{cases}[/tex]
Donc cette solution n'est pas optimale.
La solution optimale est : [tex]109100=\begin{cases}x^* = (230,0,250,0,400,0,210,20,0) & \text{Ct marginaux dual} \\ y^* = (80,50,60,70,30) & \text{Ct marginaux primal} \end{cases}[/tex]
C'est tout juste ?
Hors ligne
#5 10-04-2015 07:58:00
- katuiscia
- Invité
Re : Théorème des écarts complémentaires
comment verifier ou appliquer le theoreme des ecarts complementaires dans un exo simple
max z=200x1+300x2
2x1+3x2<ou egal 12
3x1+6x2<ou egal 15