Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Devoir 1 1. Considérer le problème de programmation linéaire suivant : Max 1000

Devoir 1 1. Considérer le problème de programmation linéaire suivant : Max 1000x1 + 1200x2 Sujet à 8x1 + 4x2 ≤ 160 4x1 + 6x2 ≤ 120 x1 ≤ 34 x2 ≤ 14 x1 , x2 ≥ 0 Résoudre ce problème avec l’algorithme du simplexe (forme tableau). 2. Considérer le problème de programmation linéaire suivant : Max 45x1 + 80x2 Sujet à 5x1 + 20x2 ≤ 400 10x1 + 15x2 ≤ 450 x1 , x2 ≥ 0 Résoudre ce problème avec l’algorithme du simplexe (forme tableau). 3. Résoudre les problèmes avec la méthode graphique a) Min - 2x1 - x2 Sujet à x1 + 4x2 ≤ 24 x1 + 2x2 ≤ 14 2x1 - x2 ≤ 8 x1 - x2 ≤ 3 x1 , x2 ≥ 0 b) Max 45x1 + 80x2 Sujet à 5x1 + 20x2 ≤ 400 10x1 + 15x2 ≤ 450 x1 , x2 ≥ 0 4. Considérer le problème de programmation linéaire suivant : Min -3x1 - 6x2 Sujet à 3x1 + x2 ≤ 48 x1 + 3x2 ≤ 48 x1 , x2 ≥ 0 a) Résoudre le problème avec la méthode graphique. b) Résoudre ce problème avec l’algorithme du simplexe (forme tableau). 1 Devoir 2 1. Déterminer toutes les solutions de base réalisables pour le système 4 , 3 , 2 , 1 , 0 2 6 3 4 6 3 6 2 4 3 2 1 4 3 2 1 = ≥ = + + + = + + + j x x x x x x x x x j 2. Considérer le problème de programmation linéaire 4 , 3 , 2 , 1 , 0 10 2 20 5 2 15 3 2 3 2 min 4 3 2 1 3 2 1 3 2 1 4 3 2 1 = ≥ = + + + = + + = + + + − − − = j x x x x x x x x x x x à Sujet x x x x z j À une certaine itération du simplexe, l’inverse de la base est ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − − − 1 7 / 4 7 / 9 0 7 / 2 7 / 1 0 7 / 3 7 / 5 . a) Poursuivre la résolution de ce problème après avoir identifié le tableau du simplexe associé à cette base. b) Supposons que le terme de droite de la troisième contrainte devienne égale à 8 (i.e., 8 2 4 3 2 1 = + + + x x x x ). La solution de base optimale obtenue en a) demeure-t-elle réalisable? Quelle est la modification de la valeur optimale de la fonction économique? 2 3. Considérer le problème de programmation linéaire suivant 3 , 2 , 1 , 0 675 2 6 3 150 50 100 3 12 4 min 3 2 1 3 2 1 3 2 1 = ≥ ≤ + + ≤ ≤ ≤ − − − = j x x x x x x x à Sujet x x x z j Dénotant les variables d’écart, le tableau du simplexe associé à la base où sont les variables de base est de la forme 7 6 5 4 , , , x x x x 7 6 5 4 , , , x x x x Var. base z x x x x x x x − 7 6 5 4 3 2 1 Termes droite 4 x 5 x 6 x 7 x 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 3 6 2 0 0 0 1 0 100 50 150 675 z − -4 -12 -3 0 0 0 0 1 0 Tableau 1 À une certaine itération de l’algorithme du simplexe, nous retrouvons le tableau suivant Var. base z x x x x x x x − 7 6 5 4 3 2 1 Termes droite 1 x 2 x 4 x 3 x 1 0 0 0 –2 –2/3 1/3 0 0 1 0 0 1 0 0 0 0 0 0 1 2 2/3 –1/3 0 0 0 1 0 0 1 0 0 4 a 50 75 150 z − 3 2 1 a a a 0 4 1/3 4/3 1 1150 Tableau 2 3 a) Spécifier l’inverse de la base associée au Tableau 2. Justifier comment on peut la lire directement dans le Tableau 2. b) Déterminer les valeurs de dans le Tableau 2. 4 3 2 1 , , , a a a a c) La solution dans le tableau 2 est-elle optimale? Pourquoi. 4. Considérer le problème de programmation linéaire suivant 3 , 2 , 1 , 0 6 2 2 5 3 2 2 2 3 3 min 3 2 1 3 2 1 3 2 1 3 2 1 = ≥ ≤ + + ≤ + + ≤ + + − − − = j x x x x x x x x x x à Sujet x x x z j Utilisons les variables d’écart pour transformer le problème sous forme standard. 6 5 4 , , x x x À une itération du simplexe nous retrouvons le tableau suivant z x x x x x x − 6 5 4 3 2 1 5 1 0 3 –1 0 0 e 0 1 –2 1 0 0 –5 0 0 –4 1 1 0 f 1 3 d 0 0 g 2 0 1 4 a) Spécifier l’inverse de la base associée à ce tableau du simplexe. b) Déterminer les valeurs de d ,e, f, g. c) La solution dans ce tableau est-elle optimale? Pourquoi. Sinon poursuivre la résolution du problème pour identifier une solution optimale. d) Quelle est la plus grande valeur ∆ de laquelle nous pouvons augmenter le terme de droite de la première contrainte pour que la solution optimale identifiée en c) demeure réalisable pour le nouveau problème ainsi généré, et quelle est la valeur optimale de ce nouveau problème. Devoir 3 1. Résoudre les problèmes suivants en utilisant d’abord une phase I a) min z = –2x1 – x2 – x3 Sujet à 2x1 + 3x2 – x3 ≤ 9 2x2 + x3 ≥ 4 x1 + x3 = 6 xj ≥ 0, j = 1,2,3 b) min z = x1 Sujet à x1 – 2x2 + x3 = 2 – x1 + 3x2 + x3 = 1 2x1 – 3x2 + 4x3 = 7 xj ≥ 0, j = 1,2,3 c) min z = x1 Sujet à x1 + x2 = 2 – 3x1 – 3x2 = 3 xj ≥ 0, j = 1,2 2. Considérons le système d’inégalités Ax ≥ b, x ≥ 0, où b ≥ 0. Nous transformons ce système sous une forme standard en introduisant m variables d’écart y pour obtenir le système suivant Ax – y = b, x ≥ 0, y ≥ 0 où b ≥ 0. Dénotons { } i m i k b b ≤ ≤ = 1 max , et considérons le nouveau sous forme standard obtenu du précédent en additionnant la kième ligne à toutes les autres lignes après avoir changé leur signe. Indiquer pourquoi il suffit d’introduire une seule variable artificielle pour obtenir une solution de base réalisable initiale. Illustrer cette procédure sur le problème suivant x1 + 2x2 + x3 ≥ 4 2x1 + x2 + x3 ≥ 5 2x1 + 3x2 + 2x3 ≥ 6 xj ≥ 0, j = 1,2,3 Devoir 4 1. Résoudre avec la variante du simplexe pour problème avec variables bornées: max x1 + 3x2 – 2x3 Sujet à x2 – 2x3 ≤ 1 2x1 + x2 + 2x3 ≤ 8 0≤ x1 ≤1, 0≤ x2 ≤3, 0≤ x3 ≤2 2. Résoudre avec la variante du simplexe pour problème avec variables bornées max 2x1 + 3x2 – 2x3 + 5x4 Sujet à 2x1 + 2x2 + x3 + 2x4 ≤ 5 x1 + 2x2 – 3x3 + 4x4 ≤ 5 0≤ xj ≤1 , j =1,2,3,4 Devoir 5 1. a) Supposant que le dual de est 0 à Sujet min ≥ ≥ x b Ax x cT . 0 à Sujet max ≥ ≤ y c y A y b T T démontrer que le dual de est 0 à Sujet min ≥ = x b Ax x cT . à Sujet max c y A y b T T ≤ b) Démontrer que le dual est 0 à Sujet max ≥ ≤ y c y A y b T T . 0 à Sujet min ≥ ≥ x b Ax x cT 2. Supposer que x* et y* soient des solutions optimales du couple de problèmes primal-dual suivant : 0 min ≥ ≥ x b Ax à Sujet x cT . 0 max ≥ ≤ y c y A à Sujet y b T T Supposer que x' soit une solution optimale du problème uploads/s3/ devoir - 2022-12-27T143305.845.pdf