Niveau Maths sup

Optimisation Linéaire / Programmation Linéaire

Posté par lolo84 (invité) 25-05-06 à 13:55

Bonjour, j'ai un petit exo à resoudre pr demain et je seche un peu sur la mise en forme du problème sous forme d'un système d'inéquations....
si quelqu'un peut m'aider ca serait super sympa
merci bcp !

Le responsable d'une formation universitaire veut organiser la semaine de cours en prenant en compte les diverses contraintes fonctionnelles (disponibilites des enseignants,horaire de travail quotidien,...) tout en prenant en compte les preferences des enseignants et des etudiants.
Pour cela, il demande dans un premier temps a chaque enseignant de lui fournir la liste des horaires ou il peut faire cours ainsi que la frequence par semaine de ses cours. Le tableau suivant donne une idee des propositions des enseignants.

Matieres  Freq./sem.   Propositions

Algebre    2           Lu 13h-15h / Ma 10h-12h / Ma 16h-18h / Me 11h-13h
Proba      1           Lu 10h-12h / Ma 10h-12h / Je 10h-12h
Stats      2           Lu 8h-10h / Lu 17h30-19h30 / Ma 14h-16h / Ve 8h-10h
Analyse    1           Me 8h-11h / Me 13h30-17h30 / Je 8h-11h
Anglais    1.5         Lu 9-10h30 / Lu 10h30-12h / Ve 11h-12h30

La liste des contraintes fonctionnelles a respecter peut s'ecrire ainsi (mais vous pouvez en ajouter...) :
- On ne veut pas placer plus de 7 heures par jour,
- Il faut laisser une heure de libre dans le creneau 12h-14h pour que les etudiants puissent aller manger
- On veut amenager une demi-journee libre de cours pour les travaux en groupe.
On considere ici que tous les etudiants de cette formation doivent assister a tous les enseignements. Selon des principes democratiques, les enseignants et les etudiant ont exprimes leurs preferences pour chaque horaire. On a ainsi obtenu une note moyenne entre 1 et 10.
La tache du responsable est donc de fournir un emploi du temps en maximisant la satisfaction des participants a cette formation. En pratique, le responsable dispose de la liste des differents horaires possibles pour chacun des cours et la moyenne des preferences des participants (etudiants ou enseignants) pour chacun des horaires.

1. Modelisez ce probleme comme un programme lineaire en nombres entiers. Cette formulation se compose de plusieurs familles d'inegalites qui correspondent chacune a une des contraintes logiques du probleme.
2. On remarque que les inegalites du programme dependent des donnees du probleme :
par exemple, si les horaires ne se chevauchent pas, il n'y aura pas d'inegalites correspondant a interdire a un etudiant d'avoir 2 cours en meme temps.
Pour chacune des familles d'inegalites, proposez un moyen de produire ces contraintes a partir des donnees du probleme, c'est-a-dire un algorithme permettant d'ecrire les contraintes dans le programme lineaire.

desole si c'est un peu long...

merci bcp par avance pr votre aide, même un début c'est tjs ca
merci

Posté par re : Optimisation Linéaire / Programmation Linéaire 25-05-06 à 14:28

bonjour,

la fréquence par semaine indique (par exemple) que les étudiants doivent suivre 2 TD d'algèbre ?

Pookette

Posté par re : Optimisation Linéaire / Programmation Linéaire 25-05-06 à 15:07

$\begin{tabular}{|c|c|c|c|c|c|} \\ {algebre}&{proba}&{stats}&{analyse}&{anglais}\\ \hline \\ {x_1}&x_5&x_8&x_{12}&x_{15}\\ \hline \\ {x_2}&x_6&x_9&x_{13}&x_{16}\\ \hline \\ {x_3}&x_7&x_{10}&x_{14}&x_{17}\\ \hline \\ {x_4}& &x_{11} \\ \end{tabular}$

Rmq: désolée pour les accolades, je n'arrive pas à faire un tableau normal ...

A chaque proposition de matière, on associe une variable x_i.
x_i = 1 si l'étudiant retient cette proposition
x_i = 0 sinon.

Fonction objectif : $\begin{tabular}{|c|}\hline{Max} \sum_{i=1}^{17} p_i x_i \\\hline\end{tabular}$

Contraintes :

7h de cours maximum par jour
lundi : 2x₁ + 2x₅ + 2x₈ + 2x₉ + 1,5x₁₅ 7
mardi : 2x₂ + 2x₃ + 2x₆ + 2x₁₀ 7
mercredi : 2x₄ + 3x₁₂ + 3x₁₃ 7
jeudi : 2x₇ + 3x₁₄ 7
vendredi : 2x₁₁ + 1,5x₁₇ 7

Une heure de pause.
Lundi, mardi, jeudi et vendredi ne posent pas de problème
mercredi : x₄ + x₁₃ 1 (soit c'est l'algèbre de 11h à 13h, soit c'est l'analyse de 13h30 à 17h30)

Un étudiant ne peut pas être à 2 cours simultanément
lundi : x₈ + x₁₅ 1 et x₅ + x₁₆ 1
mardi : x₂ + x₆ 1
jeudi : x₇+ x₁₄ 1

L'étudiant doit suivre 2 cours d'algèbre, 1 cours de proba, 2 cours de stats, 1 cours d'analyse, 1,5 cours d'anglais
x₁ + x₂ + x₃ + x₄ 2
x₅ + x₆ + x₇ 1
x₈ + x₉ + x₁₀ + x₁₁ 2
x₁₂ + x₁₃ + x₁₄ 1
x₁₅ + x₁₆ + x₁₇ 1,5

je ne vois pas comment exprimer la demi journée de libre ...

Et j'ai un doute sur la contrainte "Fréquence des cours par semaine" ... (1,5 cours ça ne semble pas logique

)

Bon courage pour la suite !

Pookette

Posté par lolo84 (invité)re : Optimisation Linéaire / Programmation Linéaire 25-05-06 à 15:57

merci bcp bcp Pookette

dsl de pas t'avoir repondu avant
a priori oui l afrequence par semaine c'est le nbre de fois que la matiere doit avoir lieu
je trouve cela bizarre aussi le 1.5 en anglais... je sais pas si ca a un rapport ms c'est de la programmation lineaire en nombres entiers que je dois faire
en tt cas, merci pr tout...
a bientot
lolo.

Posté par lolo84 (invité)re : Optimisation Linéaire / Programmation Linéaire 25-05-06 à 15:59

j'aimerais juste savoir une chose, c koi ds ta formule Pi ds la fonction objective max Pixi ?

Posté par re : Optimisation Linéaire / Programmation Linéaire 25-05-06 à 15:59

de rien. N'hésite pas à poster la suite ou la correction si tu les as.

Pookette

Posté par re : Optimisation Linéaire / Programmation Linéaire 25-05-06 à 16:00

ah oui
p_i ce sont les préférences des élèves.

Pookette