[PDF] 1 IFT1575 Démonstration 2 1. Modéliser le problème suivant où la

View - Download 1 IFT1575 Démonstration 2 1. Modéliser le problème suivant où la

Previous PDF

Next PDF

1IFT1575

Démonstration 2

1. Modéliser le problème suivant, où la fonction objectif f est linéaire par morceaux,

comme un problème de programmation linéaire.

Max f(x

1) + 450 x2

s.a. 6 x 10 x x x

1, x2 ≥ 0.

avec

Solution.

Pour modéliser ce problème à l'aide de la programmation linéaire, on pose : x

1 = x11 + x12

12

On obtient alors :

Max 2 x

11 + 0.5 x12 + 450 x2

s.a. 6 x 10 x x x x

11, x12, x2 ≥ 0

f(x1) x1 0.5 5 2

22. Résoudre le problème suivant à l'aide de l'algorithme du simplexe :

Max 60x

1 +35x2 +20x3

s.a. 8x 4x

1 + 2 x2 + 2

2x

1 + 2

3x2 + 2

x x

1, x2, x3 ≥ 0.

Solution.

On transforme d'abord le Max en Min et on introduit ensuite les variables d'écart s

1, s2,

s

3, s4 afin de transformer les inégalités en égalités. On obtient le tableau initial suivant :

v.d. x

1 x2 x3 s1 s2 s3 s4 -z t.d.

s1 8 6 1 1 48 s2 4 2 23 1 20 s3 [2] 23 21 1 8 s4 1 1 5 -z -60 -35 -20 1 0 variable d'entrée: x1 variable de sortie: s 3 v.d. x1 x2 x3 s1 s2 s3 s4 -z t.d. s1 -1 1 -4 16 s2 -1 [21] 1 -2 4 x1 1 43 41 21 4 s4 1 1 5 -z 10 -5 30 1 240 variable d'entrée: x3 variable de sortie: s 2

3v.d. x

1 x2 x3 s1 s2 s3 s4 -z t.d.

s1 -2 1 2 -8 24 x3 -2 1 2 -4 8 x1 1 45 -21 23 2 s4 1 1 5 -z 10 10 1 280 La solution optimale est x1= 2, x2= 0, x3= 8, s1= 24, s2= s3= 0, s4= 5 de valeur z = -280.

3. Notes de cours, Section 2.12, #11 (a) i) Actions ou activités Niveau

traitement d'un patient de type A x 1 traitement d'un patient de type B x 2 ii) Fonction objectif

Maximiser l'impact social

Max 1 000 x

1 + 1 200 x2

iii) Contraintes - disponibilité d'unités d'acte 9 x - disponibilité de jours-lits 6 x - patients de type A et B x x iv) Modèle

Max 1 000 x

1 + 1 200 x2

s.a. 9 x 6 x x x x

1, x2 ≥ 0

44. Notes de cours, Section 2.12, #11 (b)

5. Notes de cours, Section 2.12, #11 (c)

• on introduit des variables d'écart pour obtenir des contraintes d'égalité. • on transforme le Max en Min.

Min z = - 1 000 x

1 - 1 200 x2

s.a. 9 x

1 + 14 x2 + u = 630

6 x

1 + 5 x2 + p = 300

x

1 + h = 40

x

2 + w = 40

x

1, x2, u, p, h, w ≥ 0

v.d. x

1 x2 u p h w -z t.d.

u 9 14 1 630 p 6 5 1 300 h 1 1 40 w [1] 1 40 -z -1 000 -1 200 1 0 variable d'entrée: x2 variable de sortie: w -1000x1-1200x2= - 782000 13

13360,13350

x2

9x1+14x2=630

6x1+5x2=300

20 30
40
50
60
10 x1 10 x2=40 x1=40

20 30 40 50 60 70

5 v.d. x

1 x2 u p h w -z t.d.

u [9] 1 -14 70 p 6 1 -5 100 h 1 1 40 x2 1 1 40 -z -1 000 1 200 1 48 000 variable d'entrée: x1 variable de sortie: u v.d. x1 x2 u p h w -z t.d. x1 1 1/9 -14/9 70/9 p -⅔ 1 [13/3] 160/3 h -1/9 1 14/9 290/9 x2 1 1 40 -z 1 000/9 - 3 200/9 1 502 000/9 variable d'entrée: w variable de sortie: p v.d. x1 x2 u p h w -z t.d. x1 1 -15/117 42/117 350/13 w -2/13 3/13 1 160/13 h 15/117 -42/117 1 170/13 x2 1 2/13 -3/13 360/13 -z 6 600/117 9 600/117 1 782 000/13

On est à l'optimum! La solution optimale est:

x

1 = 350/13

x

2 = 360/13

u = 0 p = 0 h = 170/13 w = 160/13.

La valeur de la solution optimale est z

= - 782 000/13

6Note. Cet exemple illustre l'une des limites de la programmation linéaire. En effet,

cette solution est fractionnaire (alors qu'il s'agit d'un nombre de patients).

6. Soit le problème:

Min z =

α x1 - 2x2 - x3 + 4x4

s.a. x

1 +x2 - x4 = 4 + 2Δ (1)

2x

1 - x2 + 3x3 - 2x4 = 5 + 7Δ (2)

x (a) Après avoir remplacé la contrainte (1) par (1') = (1) + (2) et la contrainte (2) par (2') = -2(1) + (2), déterminer le tableau du simplexe où x

1 et x2 sont les

variables dépendantes. (b) Si Δ = 0, déterminer les valeurs de

α pour que la solution associée au tableau

obtenu en (a) soit optimale. Justifier votre réponse. (c) Si α = -3, déterminer les valeurs de Δ pour que la solution associée au tableau obtenu en (a) soit optimale. Justifier votre réponse.

Solution.

(a) Après avoir remplacé les contraintes (1) et (2) par les contraintes (1') = (1) + (2) et (2') = -2(1) + (2), respectivement, déterminer le tableau du simplexe où x

1 et x2 sont les variables dépendantes.

Après la transformation, nous obtenons le tableau suivant: v.d. x

1 x2 x3 x4 -z t.d.

x1 3 3 -3 9 + 9Δ x2 -3 3 -3 + 3Δ -z α -2 -1 4 1 0 Ce n'est pas une forme appropriée pour appliquer l'algorithme du simplexe.

Afin que x

1 et x2 puissent jouer le rôle de variables dépendantes dans les

première et deuxième lignes, nous procédons aux transformations suivantes : • on divise la ligne de x

1 par 3.

• on divise la ligne de x

2 par -3.

• on élimine α et -2 sous x

1 et x2 dans la ligne de la fonction économique.

7On obtient alors une forme appropriée, soit:

v.d. x

1 x2 x3 x4 -z t.d.

x1 1 1 -1 3 + 3Δ x2 1 -1 1 - Δ -z -(α + 3) α + 4 1 - α (3 + 3Δ) + 2(1-Δ) (b) Si Δ = 0, déterminer les valeurs de

α pour que la solution associée au tableau

obtenu en (a) soit optimale. Justifier votre réponse. Soit Δ = 0. Pour que la solution soit optimale, il faut que : • - (α + 3) • α + 4 ≥ 0 ↔ α ≥ -4.

Donc, α ? [-4, -3].

(c) Si α = -3, déterminer les valeurs de Δ pour que la solution associée au tableau obtenu en (a) soit optimale. Justifier votre réponse. Soit α = -3. Puisque tous les coefficients dans la fonction économique deviennent plus grands ou égaux à 0, il faut simplement s'assurer que la solution est réalisable. Pour celà, il faut que : • 3 + 3Δ ≥ 0 ↔ Δ ≥ -1 • 1 - Δ

Donc, Δ ? [-1, 1].

quotesdbs_dbs47.pdfusesText_47

[PDF] Modéliser par une fonction (Images , antécentent , fonctions ) Long et besoin d'aide Merci ? vous

[PDF] Modéliser par une fonction pour conjecturer

[PDF] modéliser par une fonction seconde

[PDF] modeliser resonner communiquer

[PDF] modéliser un problème géométrique

[PDF] Modéliser une fonction ( ex 60 p 48 _ math'x )

[PDF] modéliser une roulette aléatoire

[PDF] Modéliser une situation ( pouvez vous m'aider svp )

[PDF] modéliser une situation par une fonction

[PDF] Modem Bayrou

[PDF] moderation definition

[PDF] moderato cantabile analyse du repas

[PDF] Moderato cantabile de Marguerite Duras

[PDF] Modernisation d'un texte

[PDF] Moderniser un tableau