Conversions    
 
  Constantes 
 
  Unités  
 
  Calculette  
 
  home  
 
  ask us  
 

 

Linear
optimization



Optimisation
linéaire




Avec Solveur d'Excel
MS Office







© The scientific sentence. 2010

Mathematics 2: Optimisation linéaire
Examples



Les auberges et les campings




Isa et Franklin préparent à voyager ensemble. Ila planifient de dormir dans des auberges à 20$/nuité et dans des campings à 30$/nuité.

Pour ce voyage, Isa a ses contraintes, Franklin a les siennes.

• Isa ne dispose que de 30 jours au maximum pour ce voyage avec un budget maximal de 600 $. Le nombre de nuits en camping doit être au plus le double de celui dans des auberges.

La différence entre le nombre de nuits dans les auberges et celui en camping de doit pas dépasser 6 nuits.


• Franklin ne dispose pas plus de 24 jours pour ce voyage avec un budget maximal de 750 $. Il veut passer au maximum 3 fois plus de nuits en camping que dans des auberges.

De plus, le nombre de nuits en camping est au moins égal à celui dans des auberges diminué de 4.

Isa et Franklin veulent partir le plus longtemps possible tout en minimisant les dépenses de l'hébergement

Quel est le nombre de nuits qu'ils doivent passer dans chaque type d'hébergement ainsi que le coût de cet hébergement.

x: nombre de nuits à passer dans des aubeges.
y: nombre de nuits à passer dans des campings.


Pour Isa

• (1) x ≥ 0
• (2) y ≥ 0
• (3) x + y ≤ 30 → y ≤ - x + 30
• (4) 20x + 30y ≤ 600 → y ≤ - (2/3)x + 20
• (5) y ≤ 2x → y ≤ 2x
• (6) x - y ≤ 6 → y ≥ x - 6


Pour Franklin

• (1) x ≥ 0
• (2) y ≥ 0
• (3) x + y ≤ 24 → y ≤ - x + 24
• (4) 20x + 30y ≤ 750 → y ≤ - (2/3)x + 25
• (5) y ≤ 3x → y ≤ 3x
• (6) y ≥ x - 4 → y ≥ x - 4

Le voyage va se faire ensemble, il faut donc que toutes les 12 contrantes d'Isa et de Franklin concordent.

Des contraintes (3) d'isa y ≤ - x + 30 et y ≤ - x + 24 de franklin, on retient juste celle de Franklin, puisque ces inégalités ont un même ordre et que le droites correspondantes ont même pente, on retient celle qui a la plus petite ordonnée à l'origine positive .
On retient donc y ≤ - x + 24.

De même pour (4) y ≤ - (2/3)x + 20 d'Isa et (4) y ≤ - (2/3)x + 25 de Franklin.
On retient juste y ≤ - (2/3)x + 20 .

De même pour (6) y ≥ x - 6 d'Isa et (6) y ≥ x - 4 de Franklin, on retient celle qui a la plus grande ordonnée à l'origine négative.
On retient juste y ≥ x - 4 .

Enfin pour (6) y ≤ 2x d'Isa et (6) y ≤ 3x de Franklin, les droites sont linéaires,on retient celle qui a le plus petite pente.
On retient donc y ≤ 2x .

Ainsi les 12 contraintes se réduisent à 6:

• (1) x ≥ 0
• (2) y ≥ 0
• (3) y ≤ - x + 24
• (4) y ≤ - (2/3)x + 20
• (5) y ≥ x - 4
• (6) y ≥ 2x .

   C → f(x) ∩ h(x)
   - x + 24 = x - 4 → x = 14 et y = 10

   D → f(x) ∩ g(x)
   - x + 24 = - (2/3) x + 20 → x = 12 et y = 12

   E → g(x) ∩ k(x)
   - (2/3) x + 20 = 2x → x = 15/2 et y = 15



Sommets Fonction Z1 (maximiser les jours) = x + y Valeurs de Z1 (jours) Fonction Z2 (minimiser les dépenses) = 20 x + 30 y Valeurs de Z2 ($)
A(0, 0) 0 + 0 0 20 (0) + 30 (0) 0
B(4, 0) 4 + 0 4 20 (4) + 30 (0) 80
C(14, 10) 14 + 10 24 20 (14) + 30 (10) 580 ***
D(12, 12) 12 + 12 24 20 (12) + 30 (12) 600
E(15/2, 15) = (7,15) par defaut 7 + 15 22 20 (15/2) + 30 (15) 600
*** : à considérer


Réponse:     Isa et Franklin doivent passer 14 nuits dans des auberges
    et 10 nuits dans des campings pour un maximum de 24 jours
    et pour un coût total d'herbergement minimum de 580 $.






  

Google
  Web ScientificSentence
 


chimie labs
|
scientific sentence
|
java
|
php
|
green cat
|
contact
|


© Scientificsentence 2009. All rights reserved.