معلومات المقرر

Exercice 1 : Optimisation d’un programme linéaire par la méthode grahique

 

Rappel :

Un programme linéaire (PL) → forme canonique :

-         1^er cas : si PL ne dépend que de deux variables principales → résolution graphique est possible.

 

-         2^ème cas : si PL dépend de plus deux variables principales → résolution graphique est impossible.

Dans ce 2^ème cas, il faut trouvez une méthode algébrique, c’est la méthode du simplexe (George Dantzig).

 

1^er Méthode : résolution graphique :

 

A--Maximisation de la fonction objective (la fonction économique, des gains):

 

Exercice 1 :

Le but de cet exercice est de maximiser (on doit chercher) la fonction objective suivante :

M(X ;Y) = max(X ;Y) = Max (4*X + 5*Y)

 

En tenant compte des contraintes suivantes :

 

X ≥ 0 et Y ≥ 0

2*X + Y ≤ 8

X + 2*Y ≤ 7

 

Résolution graphique : 

1-    Transformer les inéquations en équations :

On doit transformer les inéquations en équations.

2*X + Y ≤ 8           → Y = -2*X +  8    équation D1

X + 2*Y ≤ 7            → Y = -X + 7        équation D2

         On obtient ainsi deux droites.

 

2-    Détermination des points d’intersections des deux droites D1 et D2:

2*X + Y = 8              équation D1

X + 2*Y = 7              équation D2

On peut aussi écrire en multipliant la 2^ème équation par 2 et on aura :

2*X + Y = 8                    équation D1

2*X + 4*Y = 14              équation D2

D2-D1 → 2*X - 2*X + 4*Y - Y= 14 -8

                  3*Y= 6

                       Y= 6/3 = 2

Je remplace Y par sa valeur dans l’équation D1 :

2*X + 2 = 8 donc 2*X = 8 – 2

                              2*X = 6 et X = 3

Donc A(3,2) est le point d’intersection entre D2 et D1

 

3. Détermination des points d’intersections des deux droites D1 et D2 avec l’axe des abscisses  et  l’axe des ordonnée :

3.1. Pour la droite D1 :

2*X + Y = 8           

Si X= 0 donc Y = 8 donc on a le point B(0,8)

Si Y= 0 donc X = 4 donc on a le point C(4,0)

3.2. Pour la droite D2 :

X + 2*Y = 7

Si X= 0 donc Y = 7/2 = 3,5 donc on a le point D(0,3.5)

Si Y= 0 donc X = 7 donc on a le point E(7,0)

 

4. Représentation graphique :

         Pour faire la représentation graphique, on doit construire le tableau suivant :

 

En utilisant le logiciel, on va tracer Y en fonction de X et on obtient le graphe suivant :

 

5. Représentation des sommets de domaine faisable :

         Nous avons représenté sur le 1^er graphe les différents points d’intersection. Dans le 2^ème graphe nous allons présenter les sommets de domaine faisable.   

 

 

         D’après cet graphe, le domaine faisable est une surface comprise entre les sommets suivants : O, D, A et C avec O(0,0)

 

6. Recherche du point qui peut maximiser la fonction objective (la fonction économique):

Le but de cet exercice est de maximiser (on doit chercher) la fonction objective suivante :

M(X ;Y) = max(X ;Y) = Max (4*X + 5*Y)

Question :

Pour chacun des sommets (O, D, A et C), lequel des points peut maximiser la fonction objective (la fonction économique) ?

 

6.1. Pour le point D(0,3.5) :

Max (4*X + 5*Y) = 4*0 + 5*3,5 = 17,5

 

6.2. Pour le point A(3,2) :

Max (4*X + 5*Y) = 4*3 + 5*2 = 22

 

6.3. Pour le point C(4,0) :

Max (4*X + 5*Y) = 4*4 + 5*0 = 16

6.4. Pour le point O(0,0) :

Max (4*X + 5*Y) = 4*0 + 5*0 = 0

 

7. Conclusion :

         Le point qui maximise notre fonction objective (programme linéaire) est le sommet solution A(3,2).

         Si une entreprise cherche à maximiser son profil, elle doit produire :

X = 3 et Y = 2 pour avoir un chiffre d’affaire de 22.

************************************************************

Exercice 2 :

Le but de cet exercice est de maximiser (on doit chercher) la fonction objective suivante :

M(X ;Y) = max(X ;Y) = Max (4*X + 5*Y)

 

En tenant compte des contraintes suivantes :

 

X ≥ 0 et Y ≥ 0

2*X + Y ≤ 8

X + 2*Y ≤ 7

Y ≤ 3 (nouvelle contrainte par rapport à l’exercice 1)

On suit les mêmes étapes que l’exercice 1

Résolution graphique : 

1-    Transformer les inéquations en équations :

On doit transformer les inéquations en équations.

2*X + Y ≤ 8           → Y = -2*X +  8    équation D1

X + 2*Y ≤ 7            → Y = -X + 7        équation D2

Y ≤ 3                       → Y = 3                 équation D3

         On obtient ainsi 3 droites.

 

2-    Détermination des points d’intersections des deux droites D1 et D2:

2*X + Y = 8              équation D1

X + 2*Y = 7              équation D2

On peut aussi écrire en multipliant la 2^ème équation par 2 et on aura :

2*X + Y = 8                    équation D1

2*X + 4*Y = 14              équation D2

D2-D1 → 2*X - 2*X + 4*Y - Y= 14 -8

                  3*Y= 6

                       Y= 6/3 = 2

Je remplace Y par sa valeur dans l’équation D1 :

2*X + 2 = 8 donc 2*X = 8 – 2

                              2*X = 6 et X = 3

Donc A(3,2) est le point d’intersection entre D2 et D1

 

3.Détermination des points d’intersections des deux droites D1 et D3:

2*X + Y = 8              équation D1

                Y = 3              équation D3

D1-D3 → 2*X + Y - Y= 8 - 3

                  2*X = 5

                       X = 5/2= 2,5

Donc B(2.5,3) est le point d’intersection entre D1 et D3

 

4.Détermination des points d’intersections des deux droites D2 et D3:

X + 2*Y = 7              équation D2

                Y = 3              équation D3

Je remplace Y par sa valeur dans l’équation D2.

X + 2*3 = 7 donc X = 7-6 et X = 1

  Donc C(1, 3) est le point d’intersection entre D2 et D3

                     

5. Détermination des points d’intersections des droites D1, D2 et D3 avec l’axe des abscisses  et  l’axe des ordonnée :

5.1. Pour la droite D1 :

2*X + Y = 8           

Si X= 0 donc Y = 8 donc on a le point D(0,8)

Si Y= 0 donc X = 4 donc on a le point E(4,0)

5.2. Pour la droite D2 :

X + 2*Y = 7

Si X= 0 donc Y = 7/2 = 3,5 donc on a le point F(0,3.5)

Si Y= 0 donc X = 7 donc on a le point G(7,0)

 

5.3. Pour la droite D3 :

         Y = 3 quel que soit la valeur de X. En particulier le point H(0,3).

6. Représentation graphique :

         Pour faire la représentation graphique, on doit construire le tableau suivant :

 

En utilisant le logiciel, on va tracer Y en fonction de X et on obtient le graphe suivant :

 

5. Représentation des sommets de domaine faisable :

         Nous avons représenté sur le 1^er graphe les différents points d’intersection. Dans le 2^ème graphe nous allons présenter les sommets de domaine faisable.  

 

 

         D’après cet graphe, le domaine faisable est une surface comprise entre les sommets suivants : O, H, C, A et E avec O(0,0)

 

6. Recherche du point qui peut maximiser la fonction objective (la fonction économique):

Le but de cet exercice est de maximiser (on doit chercher) la fonction objective suivante :

M(X ;Y) = max(X ;Y) = Max (4*X + 5*Y)

Question :

Pour chacun des sommets (O, H, C, A et E), lequel des points peut maximiser la fonction objective (la fonction économique) ?

 

6.1. Pour le point H(0,3) :

Max (4*X + 5*Y) = 4*0 + 5*3= 15

 

6.2. Pour le point A(3,2) :

Max (4*X + 5*Y) = 4*3 + 5*2 = 22

 

6.3. Pour le point C(1,3) :

Max (4*X + 5*Y) = 4*1 + 5*3 = 19

6.4. Pour le point O(0,0) :

Max (4*X + 5*Y) = 4*0 + 5*0 = 0

6.5. Pour le point E(4,0) :

Max (4*X + 5*Y) = 4*4 + 5*0 = 16

 

 

7. Conclusion :

         Le point qui maximise notre fonction objective (programme linéaire) est le sommet solution A(3,2).

         Si une entreprise cherche à maximiser son profil, elle doit produire :

X = 3 et Y = 2 pour avoir un chiffre d’affaire de 22.

***************************************************************

 

Exercice 3 :

         Une station de traitement des eaux usées (STEU) produit une eau de qualité qui peut être réutilisée dans l’industrie de textile (A : eau traitée produite) et une boue de qui peut être utilisée en agriculture (B : boue produite).

         Une seule chaine de traitement est nécessaire pour l’élaboration de ces deux produits.  La production de A nécessité :

1h30 de traitement (t_A1) et 3h de main d’œuvre (t_A2).

La production de B nécessité :

3h de traitement (t_B1) et 1h de main d’œuvre (t_B2).

  

         L’ensemble des coûts de production et de prix de vente sont résumés dans le tableau suivant :

 

         L’ensemble des contraintes de production sont :

-         Durant un mois, on ne dispose que de 2025 h et de 1950 h qui sont réservés    respectivement au traitement et à la main d’œuvre,

-         Le coût mensuel pour la matière 1^er ne pas dépasser 795 Da,

-         De plus le marché mensuel ne peut pas absorber plus de 600 produits B.

 

Question :

         Le but de cet exercice est de déterminer le programme mensuel de fabrication de ces deux produits afin de maximiser la marge totale sur les coûts variables.

 

Solution de l’exercice :

 

1^er Méthode : résolution graphique :

1-    Définition :

1-1.         Définition des variables principles (VP) :

X : quantité de produits A à produire et à vendre par mois,

Y : quantité de produits B à produire et à vendre par mois

1-2.         Définition de la fonction économique :

Marge sur les coûts variables mensuels à maximiser :

M(X ;Y) = max(X ;Y) = m_A * X + m_B * Y

Avec :     m_A = V_A – [(t_A1* A_t) + (t_A2* A_mo) + MP_A]

         m_A = 41,5DA – [(1,5 h* 1,2 DA/h) + (3 h* 4,6 DA/h) + 0,9DA] = 25 DA

et

              m_B = V_B – [(t_B1* B_t) + (t_B2* B_mo) + MP_B]

m_B = 29,2DA – [(3 h* 1,2 DA/h) + (1h* 4,6 DA/h) + 1DA] = 20 DA

 

Donc on doit chercher : Max (25*X + 20*Y) 

1-3.         Les contraintes :

1-3-1. Contraintes main d’œuvre (h) :

3*X + Y ≤ 1950

1-3-2. Contraintes traitement (h) :

         1,5*X + 3*Y ≤ 2025

1-3-3. Contraintes coût matière 1^er (DA) :

         0,9*X + 1*Y ≤ 795

1-3-4. Contraintes marché du produit B (unité) :

                   Y  ≤ 600

         Toutes les données sont traduites par des équations et inéquations. Ce qui nous permet d’écrire la forme canonique du programme linéaire.

 

X ≥ 0 et Y ≥ 0

3*X + Y ≤ 1950

1,5*X + 3*Y ≤ 2025

0,9*X + 1*Y ≤ 795

Y  ≤ 600

Max (25*X + 20*Y)

 

Résolution graphique : 

2.     Transformer les inéquations en équations :

On doit transformer les inéquations en équations.

3*X + Y ≤ 1950           → Y = -3*X +  1950 équation D1

1,5*X + 3*Y ≤ 2025    → Y = -0,5*X + 675 équation D2

0,9*X + 1*Y ≤ 795      → Y = -0,9*X + 795 équation D3

Y  ≤ 600                   → Y =  600                équation D4

         On obtient ainsi quatre droites.

 

3-    Détermination des points d’intersections des droites :

On déterminer les points d’intersections des droites deux à deux.

3.1. Détermination du point d’intersection des droites D1 et D2:

3*X +    Y = 1950            équation D1

0,5*X + Y =   675            équation D2

D1-D2 → 3*X + 0,5*X = 1950-675

                  2,5*X= 1275

                         X= 1275/2,5

                         X = 510

Je remplace X par sa valeur dans l’équation D1 :

3*510 +Y = 1950 donc Y= 1950-3*510 = 1950-1530= 420

Donc A(510,420)

 

3.2. Détermination du point d’intersection des droites D1 et D3:

3*X +    Y = 1950            équation D1

0,9*X + Y =  795             équation D3

D1-D3 → 3*X - 0,9*X = 1950-795

                 2,1*X = 1155

                        X = 1155/2,1=550

Je remplace X par sa valeur dans l’équation D1 :

3*550 +Y = 1950 donc Y= 1950-3*550=  300

Donc B(550,300)

 

3.3. Détermination du point d’intersection des droites D1 et D4:

3*X +    Y = 1950            équation D1

Y =  600                           équation D4

D1-D4 → 3*X  = 1950-600 → X = 1350/3=450

Donc C(450,600)

 

3.4. Détermination du point d’intersection des droites D2 et D3:

0,5*X + Y = 675     équation D2

0,9*X + Y = 795     équation D3

D3-D2 → 0,9*X - 0,5*X =795–675

                           0,4*X =120

                                    X=120/0,4=300

Je remplace X par sa valeur dans l’équation D2 :

0,5*300 +Y = 675 donc Y=675-0,5*300= 525

Donc D(300,525)

 

3.5. Détermination du point d’intersection des droites D2 et D4:

0,5*X + Y = 675     équation D2

Y  = 600                  équation D4

D2-D4 → 0,5*X  = 675-600 → X =75/0,5=150

Donc E(150,600)

 

 

 

3.6. Détermination du point d’intersection des droites D3 et D4:

0,9*X + Y = 795     équation D3

Y  = 600                  équation D4

D3-D4 → 0,9*X  = 795-600 → X =195/0,9=216,67

Donc F(216.67,600)

 

4. Détermination des points d’intersections des droites avec l’axe des abscisses  et  l’axe des ordonnée :

4.1. Pour la droite D1 :

Y = -3*X +  1950 équation D1     

Si X= 0 donc Y = 1950 donc on a le point G(0,1950)

Si Y= 0 donc X = 1950/3 =650 donc on a le point H(650,0)

4.2. Pour la droite D2 :

Y = -0,5*X + 675 équation D2

Si X= 0 donc Y = 675 donc on a le point I(0,675)

Si Y= 0 donc X =675/0,5= 1350 donc on a le point J(1350,0)

4.3. Pour la droite D3 :

Y = -0,9*X + 795 équation D3

Si X= 0 donc Y = 795 donc on a le point K(0,795)

Si Y= 0 donc X =795/0,9= 883,34 donc on a le point L(883.34,0)

4.4. Pour la droite D4 :

Y =  600 quel que soit la valeur de X. En particulier le point M(0,600).

 

5. Représentation graphique :

         Pour faire la représentation graphique, on doit construire le tableau suivant :

 

 

 

 

 

En utilisant le logiciel EXCEL, on va tracer  Y en fonction de X et on obtient le graphe suivant :

 

 

6. Représentation des sommets de domaine faisable :

         Nous avons représenté sur le 1^er graphe les différents points d’intersection. Dans le 2^ème graphe nous allons présenter les sommets de domaine faisable.  

 

 

D’après cet graphe, le domaine faisable est une surface comprise entre les sommets suivants : O, M, E, D, B et H avec O(0,0).

 

7. Recherche du point qui peut maximiser la fonction objective (la fonction économique):

Le but de cet exercice est de maximiser (on doit chercher) la fonction objective suivante :

M(X ;Y) = max(X ;Y) = Max (25*X + 20*Y)

Question :

Pour chacun des sommets (O, M, E, D, B et H), lequel des points peut maximiser la fonction objective (la fonction économique) ?

 

6.1. Pour le point H(650,0) :

Max (25*X + 20*Y) = 25*650 + 20*0 = 16250

 

6.2. Pour le point B(550,300) :

Max (25*X + 20*Y) = 25*550 + 20*300  = 19750

 

6.3. Pour le point C(300,525) :

Max (25*X + 20*Y) = 25*300 + 20*525  = 18000

6.4. Pour le point O(0,0) :

Max (25*X + 20*Y) = 25*0 + 20*0 = 0

6.5. Pour le point E(150,600) :

Max (25*X + 20*Y) = 25*150 + 20*600 = 15750

6.6. Pour le point M(0,600) :

Max (25*X + 20*Y) = 25*0 + 20*600 = 12000

 

7. Conclusion :

         Le point qui maximise notre fonction objective (programme linéaire) est le sommet solution B(550,300).

         Si la STPU cherche à maximiser son profil, elle doit produire :

X = 550 (550 unités (m³) d’eau traitée), et Y = 300 (300 unités (tonnes) de boues) pour avoir un chiffre d’affaire de 19750 DA.

****************************************************************

Exercice 4 :

En utilisant la méthode graphique optimiser (maximiser) la fonction objective suivante :

M(X ;Y) = max(X ;Y) = Max (300*X + 200*Y)

 

En tenant compte des contraintes suivantes :

 

X ≥ 0 et Y ≥ 0

X + 2*Y ≤ 20

2*X + Y ≤ 22

**************************************************************

Exercice 5 :

En utilisant la méthode graphique optimiser (maximiser) la fonction objective suivante :

M(X ;Y) = max(X ;Y) = Max (130*X + 100*Y)

 

En tenant compte des contraintes suivantes :

 

X ≥ 0 et Y ≥ 0

1,5*X + Y ≤ 27

X + Y ≤ 21

0,3*X + 0,5*Y ≤ 9

**********************************************

Exercice 6 :

En utilisant la méthode graphique optimiser (maximiser) la fonction objective suivante :

M(X ;Y) = max(X ;Y) = Max (10*X + 20*Y)

 

En tenant compte des contraintes suivantes :

 

X ≥ 0 et Y ≥ 0

4*X + 2*Y ≤ 20

8*X + 8*Y ≤ 20

2*X ≤ 10

*****************************************************

 

 

 

 

 

****************************************************************

 

B--Minimisation de la fonction objective (la fonction économique, des coûts):

 

Exercice 1 :

Une entreprise vise à minimiser ses coûts en utilisant la fonction objective suivante :

Min(X ;Y) = Min (24*X + 20*Y)

 

En tenant compte des contraintes suivantes :

 

X ≥ 0 et Y ≥ 0

X + Y ≥ 30

X + 2*Y ≥ 40

Question :

Utiliser la méthode graphique pour minimiser la fonction objective.

 

Résolution graphique : 

1-    Transformer les inéquations en équations :

On doit transformer les inéquations en équations.

X + Y = 30       D1

X + 2*Y= 40    D2

         On obtient ainsi 2 droites.

 

2-    Détermination des points d’intersections des deux droites D1 et D2:

 

X + Y = 30       D1

X + 2*Y= 40    D2

D2-D1 → X - X + 2*Y - Y= 40 - 30

                  Y= 10

Je remplace Y par sa valeur dans l’équation D1 :

X + 10 = 30 donc X = 20

Donc A(20,10) est le point d’intersection entre D2 et D1

 

3. Détermination des points d’intersections des droites D1, D2 avec l’axe des abscisses  et  l’axe des ordonnée :

5.1. Pour la droite D1 :

X + Y = 30       D1   

Si X= 0 donc Y = 30 donc on a le point B(0,30)

Si Y= 0 donc X = 30 donc on a le point C(30,0)

5.2. Pour la droite D2 :

X + 2*Y= 40    D2

     Si X= 0 donc 2*Y = 40 et Y = 20 donc on a le point D(0,20)

Si Y= 0 donc X = 40 donc on a le point E(40,0)

 

 

 

6. Représentation graphique :

         Pour faire la représentation graphique, on doit construire le tableau suivant :

 

En utilisant le logiciel, on va tracer Y en fonction de X et on obtient le graphe suivant :

 

 

5. Représentation des sommets de domaine faisable :

         Nous avons représenté sur le 1^er graphe les différents points d’intersection. Dans le 2^ème graphe nous allons présenter les sommets de domaine faisable.  

 

 

         D’après cet graphe, la partie supérieure du graphe (délimitée par points B, A et E) est la partie dans laquelle on peut réaliser le minimum de coûts.

 

6. Recherche du point qui peut minimiser la fonction objective (la fonction économique):

Le but de cet exercice est de minimiser (on doit chercher) la fonction objective suivante :

Min(X ;Y)  = Min (24*X + 20*Y)

Question :

Pour chacun des sommets (B, A et E), lequel des points peut minimiser la fonction objective (la fonction économique) ?

 

6.1. Pour le point B(0,30) :

Min (24*X + 20*Y)=24*0+20*30=600

6.2. Pour le point A(20,10) :

Min (24*X + 20*Y)=24*20+20*10= 680

6.3. Pour le point E(40,0) :

Min (24*X + 20*Y)=24*40+20*0= 960

 

7. Conclusion :

         Le point qui minimise notre fonction objective (programme linéaire) est le sommet solution B(0,30).

         Si une entreprise cherche à minimiser ces coûts, elle doit produire :

X = 0 et Y = 30. Avec Min (24*X + 20*Y)=24*0+20*30=600.

****************************************************************

Exercice 2 :

En utilisant la méthode graphique minimiser la fonction objective suivante :

Min(X ;Y) = Min (130*X + 100*Y)

 

En tenant compte des contraintes suivantes :

 

X ≥ 0 et Y ≥ 0

1,5*X + Y ≥ 27

X + Y ≥ 21

0,3*X + 0,5*Y ≥ 9

**********************************************

Exercice 3 :

En utilisant la méthode graphique minimiser la fonction objective suivante :

Min(X ;Y) = Min (10*X + 20*Y)

 

En tenant compte des contraintes suivantes :

 

X ≥ 0 et Y ≥ 0

4*X + 2*Y ≥ 20

8*X + 8*Y ≥ 20

2*X ≥ 10

**********************************************************