Ift1575_demo_4_sol_h13

IFT1575 Démonstration 4 1. Fournir un modèle de programmation linéaire équivalent au modèle suivant, où |x| correspond à la valeur absolue de x. Min x1 + x 2 + x 3 s.a. ≤ 1 x1 + x2 2 x1 + x3 = 3 Solution. On pose d’abord: xi = xi1 – xi2, xi1, xi2 ≥ 0, i = 1, 2, 3. Puisque xi1 et xi2 ne peuvent se retrouver toutes deux dans la même base et jouer le rôle de variables dépendantes dans le tableau du simplexe associé à cette base, et ce, quelle que soit la base et quel que soit i (car la base serait alors une matrice singulière), au moins l’une des deux variables a une valeur nulle dans le tableau optimal. Cette observation nous permet de formuler le problème ainsi : Min x11 + x12 + x21 + x22 + x31 + x32 s.a. x11 – x12

+ x21 – x22

2 x11 – 2 x12

≤ 1 + x31 – x32

= 3

x11, x12 , x21, x22, x31, x32 ≥ 0 2. Résoudre le problème de programmation linéaire en nombres entiers (PLE) suivant avec la méthode de branch-and-bound. Min z = - x1 - 2 x2 s.a. 2 x1 + x2 ≤ 5.5 x2 ≤ 2 x1, x2 ≥ 0 et entiers.

1

Solution.

1. x1 = 1.75 x2 = 2

- 5.75

z = - 5.75 x1 ≥ 2

x1 ≤ 1

2.

7. x1 = 2

x1 = 1

x2 = 1.5

x2 = 2

z = -5

z = -5

x2 ≥ 2

x2 ≤ 1

3.

4. x1 = 2.25 Non réalisable

x2 = 1 z = -4.25 x1 ≤ 2

x1 ≥ 3

6.

5.

x1 = 2 Non réalisable

x2 = 1 z = -4

La solution optimale est donc x1 = 1, x2 = 2 et la valeur de cette solution est z = -5. Nous présentons dans la suite, la résolution graphique de chacun des sous-problèmes.

2

Problème 1. x2 2x1+x2=5.5 3

(1.75, 2) x2=2 2 -x1 - 2x2= - 5.75

1

1

0

2

x1

3

Problème 2. x2 2x1+x2=5.5

x1=2

3

x2=2 2

(2, 1.5)

1

-x1 - 2x2= - 5

0

1

2

Problème 3. Le domaine réalisable est vide.

3

3

x1

Problème 4. x2 2x1+x2=5.5

x1=2

3

x2=2 2

(2.25, 1) x2=1 1 -x1 - 2x2= - 4.25

2

1

0

x1

3

Problème 5. Le domaine réalisable est vide. Problème 6. x2 2x1+x2=5.5

x1=2

3

x2=2 2

x2=1 1 -x1 - 2x2= - 4

(2, 1)

0

1

2

3

4

x1

Problème 7. x2 x1=1

3

2x1+x2=5.5 x2=2 2

-x1 - 2x2= - 5

(1, 2) 1

0

2

1

3

x1

3. Soit le problème suivant avec k ≥ 0 : s.a.

Min z = – x1 – 2 x2 – x1 + x2

≤ 2

x2

≤ 3

k x 1 + x2

≤ 2k + 3

x1 , x 2 ≥ 0 Soit maintenant la solution x1 = 2, x2 = 3. À l’aide d’une analyse graphique, déterminer les valeurs de k permettant d’assurer que cette solution est optimale. Solution. Notons tout d’abord que le point (2, 3) est toujours réalisable quelle que soit la valeur de k. En effet, les deux premières contraintes sont vérifiées et la troisième contrainte devient alors 2k + 3 ≤ 2k + 3 qui est nécessairement vérifiée. Par ailleurs, puisque la droite k x1 + x2 = 2k + 3 ↔ x2 = –k x1 + (2k +3) est de pente –k et qu’elle passe toujours par le point (2, 3), toute modification de la valeur de k entraîne une rotation de cette droite autour du point (2, 3). Notons enfin que pour la pente –k = –½, la droite correspondant à la troisième contrainte devient ½ x1 + x2 = 4 ↔ x1 + 2x2 = 8 ↔ -x1 – 2x2 = -8 et elle se confond ainsi avec la droite de la fonction objectif lorsque z = -8.

5

Tel qu’illustré dans les deux figures suivantes, le point (2,3) est optimal en autant que la pente de la droite correspondant à la troisième contrainte demeure plus petite ou égale à –½. Autrement dit, lorsque –k ≤ –½ ↔ k ≥ ½. x2 -x1+x2=2

pente = -k > -½

4 x2= 3

3

z = -x1 - 2x2 < -8

2

(2, 3)

optimum

1

pente = -k = -½ z = -x1 - 2x2 = -8 1

2

3

4

5

6

7

x1

8

x2 pente = -k < -½

-x1+x2=2

(2, 3) optimum

4

x2= 3

3

2

pente = -k = -½ 1

z = -x1 - 2x2 = -8 1

2

3

4

5

6

7

6

8

x1

4. Question #2 du devoir 1 On désire déterminer la composition, à coût minimal, d’une tonne d’aliment pour bétail qui est obtenu en mélangeant au plus trois produits bruts: orge, arachide, sésame. L’aliment ainsi obtenu devra comporter au moins 22% de protéines et 3.6% de graisses, pour se conformer aux exigences de la clientèle. On a indiqué ci-dessous les pourcentages de protéines et de graisses contenus, respectivement, dans l’orge, les arachides et le sésame, ainsi que le coût par tonne de chacun des produits bruts. Orge

Arachide

Sésame

% requis

% protéines

12%

52%

42%

22%

% graisses

2%

2%

10%

3.6%

Coût/tonne ($)

25

41

39

Formuler ce problème à l’aide d’un modèle de programmation linéaire ne comportant que deux variables de décision. Solution (a) Considérons d’abord une formulation « naturelle » avec 3 variables de décision : i) Actions ou activités

Niveau (fraction de tonne)

quantité d’orge dans une tonne d’aliment quantité d’arachide dans une tonne d’aliment quantité de sésame dans une tonne d’aliment

x1 x2 x3

ii) Fonction économique Minimiser le coût Min 25 x1 + 41 x2 + 39 x3 iii) Contraintes - % requis 12 x1 + 52 x2 + 42 x3 ≥ 22 2 x1 + 2 x2 + 10 x3 ≥ 3.6

(protéines) (graisses)

- La somme des fractions de tonne doit égaler 1 tonne x1 + x 2 + x3 = 1 - Non négativité des variables x1 , x 2 , x3 ≥ 0

7

À l’aide de la contrainte d’égalité, on peut éliminer une variable en posant par exemple : x1 = 1 – x2 – x3 . i) La fonction objectif devient Min 25 (1 – x2 – x3) + 41 x2 + 39 x3 = 25 + 16 x2 + 14 x3. Note. Puisque la constante 25 n’a aucun impact lors de la minimisation, on peut la retirer de l’objectif. ii) Les deux premières contraintes deviennent 12 (1- x2 –x3) + 52 x2 + 42 x3 = 12 + 40 x2 + 30 x3 ≥ 22 2 (1- x2 –x3) + 2 x2 + 10 x3 = 2 + 8 x3 ≥ 3.6 iii) La contrainte de non négativité de x1 devient 1 – x2 – x3 ≥ 0. iv) Modèle Min 16 x2 + 14 x3 s.a. 40 x2 + 30 x3 ≥ 10 8 x3 ≥ 1.6 x2 +

x3 ≤ 1

x2 , x 3 ≥ 0 5. Question #3 du devoir 1 Une compagnie engage trois employés afin de produire deux types de portes-patio : l’une avec cadre en bois et l’autre avec cadre en aluminium. Le profit est de 60$ par porte-patio avec cadre en bois et 30$ par fenêtre avec cadre en aluminium. L’employé 1 fabrique 6 portes-patio avec cadre en bois par jour. L’employé 2, de son côté, fabrique 4 portes-patio avec cadre en aluminium par jour. Enfin, le troisième employé peut couper 48 mètres carrés de verre par jour. Chaque porte-patio avec cadre en bois nécessite 6 mètres carrés de verre, tandis que chaque porte-patio avec cadre en aluminium nécessite 8 mètres carrés de verre. La compagnie veut déterminer le nombre de portes-patio de chaque type qu’elle doit produire à chaque jour pour maximiser son profit. (a) Formuler ce problème à l’aide d’un modèle de programmation linéaire. (b) Résoudre ce problème à l’aide de la méthode graphique. 8

(c) Toujours à l’aide d’une analyse graphique, expliquer ce que devient la solution optimale du problème modélisé en (a) si on suppose que le profit associé à chaque porte-patio avec cadre en bois est réduit de 60$ à 20$? (d) Toujours à l’aide d’une analyse graphique, expliquer ce que devient la solution optimale du problème modélisé en (a) si l’employé 1 ne peut produire que 5 portes-patio avec cadre en bois? Solution. (a) i) Actions ou activités

Niveau (nombre)

production de portes-patio avec cadre en bois

x1

production de portes-patio avec cadre en aluminium

x2

ii) Fonction économique Maximiser le profit Max 60 x1 + 30 x2 iii) Contraintes - Capacité de production maximale x1

≤ 6

(portes-patio en bois)

x2 ≤ 4

(portes-patio en aluminium)

6 x1 + 8 x2 ≤ 48

(verre)

- Non-négativité des variables x1 , x 2 ≥ 0 iv) Modèle Max 60 x1 + 30 x2 s.a. 6 x1 + 8 x2 ≤ 48 x1

≤ 6 x2 ≤ 4

x1 , x 2 ≥ 0

9

(b) x2 60x1+30x2 = 405

x1=6

6x1+8x2=48

6 5

x2=4 4 3 (6, 3/2)

2 1

0

1

2

3

4

5

6

7

8

x1

La solution optimale est donc x1 = 6, x2 = 3/2 pour un profit de 405$. (c) x2 x1=6 6x1+8x2=48

6 5

(8/3, 4) x2=4

4 3 2

20x1+30x2 = 520/3

1

0

1

2

3

4

5

6

7

8

x1

La solution optimale est donc x1 = 8/3, x2 = 4 pour un profit de 173.33$

10

(d) x2 60x1+30x2 = 1470/4 6x1+8x2=48

6

x1=5

5 x2=4 4 3

(5, 9/4)

2 1

0

1

2

3

4

5

6

7

8

x1

La solution optimale est donc x1 = 5, x2 = 9/4 pour un profit de 367.50$

11