Programmation linéaire

par **KAREN44** » 12 Nov 2009, 18:10

Bonsoir,
Je prépare un concours et je tombe sur un os avec la programmation linéaire.
une agence de voyage organise un séjour pour 200 personnes. Elle dispose de deux types de cars. Un car A pour 55 personnes loué 1000, un car B pour 40 personnes loué 800.
Le nombre de cars disponibles est de 5 pour le type A et de 6 pour le type B. L'agence prévoit une animatrice par car et dispose au maximum de 10 animatrices.
Quel est le nombre de cars de type A et de type B faut-il prévoir pour un coût minimum?

Il s'agit d'un exercice de programmation linéaire -> le résultat à lire sur le graphique (dans le domaine de réalisation) et est à calculer
Je connais la méthode
mon problème est que je ne sais ps poser l'équation et les deux inéquations!...
Merci d'avance

par **fatal_error** » 12 Nov 2009, 21:56

salut,

Je prépare un concours et je tombe sur un os avec la programmation linéaire.
une agence de voyage organise un séjour pour 200 personnes. Elle dispose de deux types de cars. Un car A pour 55 personnes loué 1000, un car B pour 40 personnes loué 800.
Le nombre de cars disponibles est de 5 pour le type A et de 6 pour le type B. L'agence prévoit une animatrice par car et dispose au maximum de 10 animatrices.
Quel est le nombre de cars de type A et de type B faut-il prévoir pour un coût minimum?

Fonction a minimiser :
z = f(x_1,x_2), avec x_1 nombres de cars de type A, x_2 nombres de cars de type B.
z = x_1 * cout(A) + x_2*cout(B). Avec cout(A), le cout d'un car de type A.
z = x_1*1000 + x_2 * 800
Il reste a traduire les contraintes :
x_1200 //nombres de personnes

par **KAREN44** » 25 Nov 2009, 18:55

Bonsoir, Je vous remercie infiniment pour votre aide.
Seulement je ne comprends pas trop bien votre raisonnement.

Le problème est que je ne vois pas votre point optimum (appelons-le A).
Par les calculs, je trouve A (7.66 ; 2.33). Et ça ne peut pas être ça car ce point ne fait pas partie de mon domaine des contraintes (ou de réalisations) sur le graphique!!!... sans compter que x et y doivent être des nombres entiers.

Pourriez-vous me dire ce qui ne va pas?
Merci d'avance.
Bonne soirée!

par **Ben314** » 25 Nov 2009, 19:58

Bonsoir,
Quels "calculs" fait tu pour trouver le point A ?
(Tu disait toi même que le résultat "est à lire sur le graphique")
Je pense que tu doit sur le graphique chercher le point A COORDONNEES ENTIERES qui réalise le maximum...

par **KAREN44** » 26 Nov 2009, 17:33

je vais te le dire mais ça ne colle pas. Pour le point A, j'ai calculé en résolvant ceci :
55 x + 40 y = 200
x + y = 10

Je te remercie d'avance Ben

par **Ben314** » 26 Nov 2009, 18:33

Ton système n'est pas si bête que ca. Comme tu as deux inconnues, tu cherche deux équations : c'est assez logique...
Ce qui ne colle pas c'est que rien ne dit dans l'énoncé que les cars doivent tous être complètement plein ni que l'on doit absolument faire travailler les dix animatrices... De plus ton système ne tient pas compte des données de cette partie de l'énoncé "Le nombre de cars disponibles est de 5 pour le type A et de 6 pour le type B"
Si tu traduit exactement ce que te dit l'énoncé, tu obtient les contraintes données par fatal_error qui délimitent une partie du plan (chaque inéquation correspond à un demi-plan).
Dans cette partie du plan tu ne dois (évidement) considérer que les points à coordonnées entiéres : on ne vas pas louer 3.7 cars !!!!
Et parmi ces point, il faut chercher celui pour lequel la fonction à minimiser (aussi donnée par fatal_error) est... la plus petite possible.

Tu devrais avoir vu en cours comment trouver "graphiquement" ce minimum.

P.S. La solution consistant a essayer tout les points du domaine n'est pas celle attendu par le professeur.......

par **KAREN44** » 28 Nov 2009, 12:23

Je trouvais plus logique de résoudre :
55 x + 40 y = 200
5x +6 :briques: y = 10
mais paraît-il que ce n'était pas ça!!!

par **Ben314** » 28 Nov 2009, 12:37

Ce système serait le bienvenu... pour un énoncé différent dans lequel on demande de remplir COMPLETEMENT tout les cars et de donner du travail à TOUTES les acompagnatrices.
L'énoncé que tu as, quand à lui, te dit seulement que :
55 x + 40 y >= 200 (il faut AU MOINS 200 places dans les bus)
x + y <= 10 (il y a AU MAXIMUM 10 animatrices)

par **fatal_error** » 28 Nov 2009, 13:07

salut,

(im semble que c'est x+y<=10
il n'y a ni 5 animatrices par car A, ni 6 amatrices par car B, avec x le nombre de cars A et y le nombre de car B)

Concernant les parties entières, est-il envisageable de résoudre dans R (je pense au simplexe) pis de tester les arrondis apres?

par **Ben314** » 28 Nov 2009, 13:28

OUPSSS,
Je rectifie (et je ne comprend pas d'ou peut sortir la 2em égalité de son système)
Pour les 'arondis', je pense qu'en général, ca ne marche pas, si le max réel est situé sur un "angle trés pointu" du domaine, le max entier risque d'étre à trifouilli les oies...

P.S. Je ne sais pas s'il existe une méthode informatisable (style simplexe) pas trop pourrie pour résoudre DANS Z des problème d'optimisation.
Si quelqu'un a un élément de réponse, je suis preneur.

Programmation linéaire

programmation linéaire

Réponse à votre message

réponse à ton message Ben

réponse à ben

Qui est en ligne