Inscription / Connexion Nouveau Sujet
Trouver x1, x2, x3, tels que x1+x2+x3>=N ?
Bonjour,
Comme mon pseudo pourrait le laisser comptrendre, les maths ne sont pas franchement ma tasse de thé.
J'ai étudié la physique puis la chimie - qu'en partie à cause des maths dans le premier cas, et de la biologie dans le deuxième.
Je suis actuellement apprenant en informatique, et on m'a demandé de prévoir en Basic le tranport de nombreux voyageurs avec des moyens limités.
J'ai trouvé le sujet suivant, qui y ressemble à mon problème que je n'ai solutionné:
https://www.ilemaths.net/sujet-combien-de-solutions-a-x1-x2-x3-k-431983.html
(j'ai pensé y poster pour éviter des redites, mais le site insiste bien sur un post par sujet, conformément aux recommandations élémentaires de bases de données).
-Je n'ai plus la donnée sous les yeux, elle ne m'est plus accessible, mais c'est le principe qui compte:
On désire transporter un nombre considérable de voyageurs, pour un marriage de notables par exemple ou quelconque autre chose, (de l'ordre du millier de personnes). Pour cela, on a à disposition x1 cars de A places, x2 cars de B places, x3 cars de C places (cars loués).
A, B, C sont bien-sûr constantes, et connues
(A: 65 places, B: 50 places, C: 35 places).
Il y a bien-sûr des contraintes économiques:
frais kilométrique (évidemment), et
frai fixe par car (et par journée).
Ce qu'il faut en tirer, c'est évidemment la nécessité d'employer le moins de cars possibles.
Par ailleurs, le nombre de chaque type de cars est limité.
x1 ≤ M, x2 ≤ N, x3 ≤ P
(p. ex.: x1 ≤ 17, x2 ≤ 19, x3 ≤21).
Enfin, je veux donc m'assurer que le total des places des cars est au moins égale au nombre de voyageurs (tout en évitant de faire rouler un car contenant un seul chauffeur en plus); j'ai posé:
65x1+50x2+35x3 ≥ N
(N est le nombre de voyageurs).
Comment puis-je m'y prendre pour résoudre (je dois en effet trouver toutes les combinaisons d'un minimum de cars, i.e.: en enlevant les combinaisons doublons ou non-économiques)?
J'ai pensé résoudre à partir du cas limite où c'est égal à N, mais même dans ce cas, il me manque deux équations! J'ai aussi pensé à la résolution d'une équation du 3ème degré, que j'ai vite abandonnée, pour cause qu'elle n'avait rien à voir.
Je vous invite à oublier le problème des doublons en première approche, afin d'aller à l'essentiel sans compliquer.
Dans le lien que j'ai repris - si on oublie les coeffiscients -, il est écrit par Jandri, que:
x1+x2+x3 ≤ N, revient à
x1+x2+x3+x4 = N;
je comprends cela comme: "je peux trouver un nombre quelconque tel que l'inéquation "inférieure" devient une égalité". Cependant, je ne suis pas sûr que je puisse faire l'inverse; en d'autres termes, je doute que
x1+x2+x3 ≥ N revienne à
x1+x2 = N - en effet, ce serait soustraire un nombre prédéterminé (cf majorant sur x3) en place d'un nombre absolument quelconque; ce serait donc je pense ajouter des possibles.
Alors... comment puis-je m'y prendre, je vous prie ?
Bonjour,
on s'y perd dans ton long texte dis donc ^^.
En gros tu veux optimiser le nombre de car à utiliser pour transporter N personnes !
tu peux nous donner plus de détails économiques, ça peut faire plus d'équation je pense, sinon je ne vois pas comment on peut optimiser les frais sans avoir ces données.
Bonjour LeMathematicien1 !
Merci pour cette réponse déjà maintenant.
Oui, en effet, j'ai tendance à en écrire plutôt trop que pas assez (un défaut récurent chez moi).
Malheureusement, je n'ai plus la donnée exacte pour les frais fixe; je ne demande pas la réponse numérique; par ailleurs vous avez parfaitement deviné le problème, il est d'optimisation - minimiser les cars, minimiser les coûts.
Je reviens avez ces détails dans 15 minutes, à tout'!
Bonjour,
en l'absence d'infos de cout a proprement parler, il est probable qu'il faut se contenter du nombre minimum de cars et pour cela remplir en priorite les 65 places (qui sont a priori plus economiques par passager lorsqu'ils sont pleins).
Il faut donc diviser N par 65 et s'interesser au reste de la division (on se limite pour l'instant a N
17*65). Selon le valeur de ce reste on remplira un buse de 35 si possible (r35), ou de 50 (35<r50), voire de 65. On a neanmoins le cas particulier si le reste r est suffisamment petit, on peut remplacer le dernier bus de 65 par un bus de 50 et rentrer les autres passagers 15+r dans un 35 places (donc pour un r 20)
Apres pour affiner, il faut savoir s'il est plus interessant d'utiliset un 65 et un 35, plutot que deux 50...
Voilà:
Frais de séjour: F1 francs par nuit pour logement chauffeur (100.--/nuit),
Immobilisation du car: F2 francs par jours (300.--/jr)
En principe, il nous est écrit que l'on doit commencer par les plus grands cars avant les plus petits,
- p.ex.: 67 passagers donne 1 car de 65 place et 1 car de 35 places.
mais qu'"un programme capable d'allouer la meilleure combinaison possible serait trop difficile à ce stade".
J'ai un collègue qui avait trouvé un article de combinatoire sur wikipedia, mais je ne l'ai retrouvé, et la donnée apparemment simple que je n'ai résolue continue de me troubler. Je souhaite donc trouver malgré tout implémenter la solution optimisée.
C'est pourquoi si un matheux doué pouvait me procurer l'algorithme - mathématique, hein, pas en Basic - je lui en serait infiniment reconnaissant.
Excusez-moi, j'ai écrit entre temps,
Merci Sbarre également! L'alogithme a l'air simple.
Vous avez parfaitement deviné qu'il fallait commencer par les grands cars.
Étant donné que tant les frais kilométriques que journaliers sont les mêmes (il s'agit d'une location) entre différents cars, les deux cars de 50 places sera aussi économique que le cars de 65 places avec le car de 35 places.
Précision et rectification sur le nombre de cars:
on a au garage 3 cars de 65 places,
5 cars de 50 places,
2 cars de 35 places.
Evidemment, si le nombre de voyageur est supérieur à 515 (le max possible par le total des places), je renonce au transport.
Le problème est que le nombre de voyageurs - entré comme paramètre - fait que je ne sais par par où commencer.
Il faudrait que l'algorithme soit lui aussi optimisé.
Je continue de chercher. Si je comprends bien, il va falloir faire un test, de savoir si N (nombre de voyageurs), est un tuple de tels ou tels cars ?
donc si le prix de revient d'un bus est le meme quelle que soit sa taille, c'est assez simple
Appelons E le partie entiere de (N/65) et R le reste de la division euclidienne de N par 65.
si N1105 (17*65), alors il faudra prendre E bus de 65 places si R=0 et E+1 bus de 65 places sinon.
si 1106N2055 (17*65+19*50).
Posons N'=N-1105, et Appelons E' le partie entiere de (N'/50) et R'le reste de la division euclidienne de N' par 50.
alors il faudra prendre 17 bus de 65 places et E'bus de 50 si R=0 ou 17 bus de 65 places et E'+1 bus de 50 sinon.
meme raisonnement avec les 21 cars de 35 places avec un maximum de 735 passagers restants (21*35)
Le maximum de passager transportables avec tes donnees est de 2790.
Bonjour,
Quelques observations :
Le problème n'est pas du niveau terminale.
Il s'agit d'un problème d'optimisation sous contraintes, qui dans le "cas général" relève du niveau école d'ingénieur.
L'exercice de combinatoire que tu cites en exemple au tout début n'a rien à voir.
Tout au plus il a un vague et lointain rapport avec le dénombrement des solutions satisfaisant les contraintes (nombre très élevé si on essaie toutes les possibilités sans "intelligence" : on parle de problème NP complexe, ou de complexité exponentielle).
Dans le cas que tu présentes, sbarre indique une solution pragmatique et de bon sens qui résout probablement ton problème dans la plupart des cas :
1. Saturer les contraintes (cars de chaque sorte disponibles) en commençant par les cars les plus rentables (a priori les plus gros), jusqu'à atteindre le N cible. A chaque affretement d'un car, on diminue "N" (passagers restant à affecter) de la capacité du car... jusqu'à atteindre zéro.
2. Evaluer le cas échéant des "variantes" si cette solution conduit à l'affretement d'un petit car quasi vide.
Pour celà : lorsqu'on se rapproche de N < a + b + c, on envisage toues les permutations possibles : il n'y en a pas beaucoup et on peut trouver la "bonne affaire" facilement.
Par exemple, on a affrété dans un "premier passage" :
NA cars de capacité A (65), tous les A sont utilisés
NB cars de capacité B (50), tous les B sont utilisés
NC cars de capacité C (35).
Solution de base : NA ; NB ; NC
Le dernier cars de type C (le plus petit) contient seulement 10 passagers (tous les autres étant supposés saturés).
Cela veut dire qu'à l'étape précédente, on a surement intérêt à prendre 1 car de type B en moins et à le remplacer par un car de type C.
Solution améliorée : NA ; NB-1 ; NC+1
Dans ce cas le car incomplet contient 30 passagers.
Il ne reste que 5 places vides et cette solution est probablement optimale ou quasi, car un car C coûte moins qu'un B.
Le calcul de la fonction économique qui cumule tous les coûts permettra de faire une hiérarchie des différentes variantes.
Si j'ai bien compris, il faut commencer par remplir les grands car puis les petits et que ça soit le car A, B ou C les frais sont les mêmes. c'est ça ?
Pour un cas un peu plus général...
REFORMULATION :
Nombre de passagers : N
Capacités (nb places) : p1, p2, p3 ...
Nombres de cars dispo : n1, n2, n3 ...
Coûts par type de car : c1, c2, c3 ...
On cherche une solution : S = (x1 ; x2 ; x3 ; ...)
Minimisant les frais : F = 
xi.ci
Sous contraintes : xi = n et xi <= ni
Solution de base :
Ordonner les cars selon leur rentabilité unitaire maximale (coût par passager du car saturé) : ci/ni
Affecter autant de cars que disponibles dans l'ordre de rentabilité.
Calculer à chaque étape le nombre R de passagers restant (non encore affectés) : R = N - c1.n1 - c2.n2 ... jusqu'à épuisement.
Calculer le coût F0 de cette solution S0.
Solution améliorée :
Si la place vide dans le dernier car affrêté est importante, il y a lieu d'évaluer des solutions voisines, en permutant quelques cars.
A chaque itération respectant les contraintes : calcul de la fonction économique F.
Pour la solution améliorée :
Lorsque R s'approche de la somme des ni, on peut commencer à chercher toutes les possibilités d'affectations satisfaisant les contraintes restantes.
Schématiquement, si on a 4 types de cars (4 capacités), lorsqu'on s'approche de 4 cars à affrêter (ou un peu plus) par rapport à la solution de base, on peut se permettre un calcul exaustif.
Pour celà boucle imbriquée sur x1, x2, x3 x4, respectant les contraintes.
Evaluation de la fonction de coût pour chaque itération.
Illustration sous Excel :
Pour N = 340
On trouve la solution de base :
S0 : 3 + 4 + 0 Coût = 3070
Et les variantes S1, S2 et S3 se déduisent de S0 en faisant +1 et -1 sur les différents cas possibles.
S1 : 2 + 5 + 0 Coût = 3050
S2 : 3 + 3 + 1 Coût = 3040
S3 : 2 + 4 + 1 Coût = 3020
R sur la dernière ligne donne le nombre de places vides...
Bonjour à tous, et merci d'ores et déjà pour toutes vos réponses.
LeDino,
il me semble que vous faites une remarque très pertinente, là: "Ce n'est pas du niveau de terminale, mais de l'école d'ingénieur". Je m'attendais à une remarque de ce type; à vrai dire je ne savais pas exactement de quel niveau ça relevait. Il me semblait que l'optimisation pouvait parfois être abordée en fin de lycée. Par ailleurs mon niveau correspond au bac, ce qui pour certains domaines ou problèmes peut même être prétencieux (je me souviens de ce problème de pH d'un sel d'acide et base tous deux faibles).
Enfin, ce problème que j'ai eu est apparu en formation d'apprentissage, qui mène à un CFC en Suisse, et je ne connaît pas la correspondance en France (il y a plein d'abréviations).
Peut-être un modérateur pourrait-il envisager de transférer ce topic sous "Supérieur", (mais là, il se pourrait que ce soit moi qui ne comprenne pas) - or si l'opportunité existe de transférer le topic dans une section plus adéquate, vous avez mon accord; j'en fais même la demande publiquement - au besoin, j'en ferai la requête à un modérateur.
Merci encore pour toutes vos réponsesk, que je vais lire.
Bonjour Lavoisier,
Je suis tout à fait d'accord avec toi sur la difficulté de classer certains problèmes.
Sur un énoncé donné, tu peux parfois déplacer une virgule ou modifier deux paramètres... et la nature du problème peut changer radicalement et devenir extrêmement simple ou extrêmement complexe.
L'expression "la plus générale" de ton énoncé en fait un problème de recherche "d'optimum sous contraintes" : il s'agit de minimiser un coût en respectant un certain nombre de contraintes.
Ces problèmes s'abordent en général en première année d'école d'ingénieur et relèvent de la "recherche opérationnelle".
Dans le cas précis que tu poses, la forme de la fonction économique et des contraintes en fait même plus précisément un problème de "programmation linéaire", qui est un cas particulier "résolu", au sens où il existe une méthode (assez complexe, mais programmable), qui trouve l'optimum sans faire un nombre exponentiel de calculs.
Mais revenons à ton cas :
Si tu n'as pas le bagage pour traiter le problème par la recherche opérationnelle, cette approche ne te convient probablement pas. D'où l'idée respectable de ne pas poster en section "ingénieur".
Qui plus est, dans le cas de ton problème, il existe une solution "optimisée" mais non "optimale" : c'est à dire une solution assez proche de l'optimum, sans être à coup sûr l'optimum (surtout si le coût des gros cars n'est pas beaucoup plus élevé que celui des petits).
En pratique une telle solution peut s'avérer tout à fait satisfaisante, selon le contexte du problème : vie réelle, exercice, travail exploratoire ... ?
C'est dans cet esprit que sbarre t'avait donné une très bonne réponse, "optimisée" mais "non optimale" (si les coûts par cars sont différents)... en observant qu'il faut commencer par affrêter les gros cars (qui permettent de charger des passagers avec un coût unitaire minimal, donc imbattable).
Le petit défaut de cette solution que j'ai qualifiée "de base", c'est qu'elle n'est pas assurée d'aboutir au parfait optimum. Elle tombera souvent sur une solution proche de l'optimum, mais pas parfaitement optimum.
C'est le cas de l'exemple que je t'ai donné : la solution de base conduit au dernier car peu rempli, ce qui laisse la place pour des opportunités de permutations.
Pour conclure sur ton problème : tout dépend du niveau de réponse qu'on attend de toi.
La solution de base est suffisante si le coût des cars est le même quel que soit la taille (hypothèse peu réaliste, mais bon...).
Et elle est encore pas mal satisfaisante dans le cas général.
Tu peux l'améliorer pour pas cher :
... en ajoutant les petites permutations finales +1 -1 que j'ai proposées : c'est vite fait à tester (en contraintes) et à évaluer (en coût). Si ça gagne tant mieux. Sinon, c'est que la solution de base est vraiment pas mauvaise.
Et si tu veux améliorer encore plus :
... tu peux étendre le principe des permutations sur un petit nombre de cars. Ca ne fera pas tant de cas que ça à traiter, et tu as des bonnes chances de tomber sur l'optimum ou tout proche.
D'ailleurs, dans le cas présent, un indicateur simple peut te dire si tu es proche de l'optimum théorique :
Dans la solution de base, ou dans sa meilleure variante améliorée par permutation : si R est nul la solution est optimale, et si R est faible, la solution est très proche de l'optimum (il ne reste plus grand chose à optimiser...).
Pour la suite : c'est toi seul qui peut apprécier ce qu'on attend de toi et le niveau de réponse qui convient.
LeDino,
Je suis sachez-le en train de lire attentivement votre solution.
Aussi - plutôt qu'une requête formelle à un modérateur de déplacement de thème - ai-je recréé un sujet sous Supérieur - Ecole d'ingénieur, avec la donnée nécessaire cette fois - je sais: c'est déconseillé, mais je l'ai fait selon votre avis que le problème avait été mal posé ici (un malheureux inconvénient d'inaccès à la donnée, alors que j'ai le droit d'améliorer mon programme hors autre urgence). J'ai donc pensé bon de ne mettre que la donnée nécessaire au départ, dans la section que vous m'avez indiquée.
Ceci afin d'avoir rapidement la "Solution générale" (comme on dit en calcul différentiel) - personne ne m'y a cependant encore répondu.
Je n'ai pas réalisé de suite que votre texte était l'algorithme.
Je suis précisément en train de le ré-écrire à la main afin de l'"intégrer" mentalement.
Un grand merci à LeDino, donc, j'apprécie grandement votre effort et votre implication sous Excel, de même qu'aux autres, je pense notamment à Sbarre à qui je dois en même temps des excuses pour l'avoir laissé trouver quelque chose qui m'était indiqué (commencer par les grands cars), c'était très bien vu de sa part.
J'ai encore du mal à concrétiser l'algorithme et je ne veux cependant pas abuser de votre patience, LeDino, mais si le nombre N est entré en paramètre (et ne m'est donc encore connu):
m'est-il possible de faire un programme optimisé ?
Si la réponse à cette question est "Non": basiquement, mon programme de dénombrement "manuel" des solutions était le bon, qu'en pensez-vous ?
Une chose me chiffonne, c'est un ami qui a trouvé un long article sur les tris dans wikipedia; de même que le formateur qui avait trouvé une seule personne jusqu'alors, qui avait trouvé toutes les solutions et rien que les solutions. C'est ce qui me laisse un doute, consistant à croire qu'il y a un algorithme "parfait", et plus intelligent que la transcription d'un dénombrement manuscrit des solutions. Je crois que mon formateur n'a pas de loin pas été impressionné, c'est pourquoi je pense qu'il doit y avoir un programme qui vérifierait juste quelque conditions (deux-trois, si ça se trouve).
J'ai lu votre réponse un peu vite, LeDino,
en effet, tout dépend de l'exactitude que l'on attend; mais elle-même dépend de ce dont on est capable (grande pensée pholosphique, je sais).
Basiquement, quitte à avoir la "solution générale", je suis capable de me satisfaire d'un algorithme qui soit exhaustif, pour autant que je sois capable de le ré-écrire et de ne le comprendre qu'après coup - même si cela peut heurter ces sensibilités mathématiciennes, ce que je conçois.
Désolé pour le multipost (je n'arrive pas à éditer mes posts, ce qui est probablement un choix de l'administration).
Pour l'exactitude, même pour une solution générale, j'oublie la rentabilité variant: elle est posée comme étant la même entre les cars.
Ce que je souhaiterais pouvoir lire, à condition que vous l'acceptiez et que cela ne vous prenne pas une heure, ou à la condition que j'arrive à ré-écrire votre algorithme, c'est un algorithme du type:
-Déclarer un entier N, et l'initialiser à zéro;
-Demander: N voyageurs;
-Entrer: N voyageurs;
après, au stade de la division, j'hésite sur comment faire. Je crois savoir des posts des contributeurs de ce thème, qui faut vérifier la multiplicité par rapport à 65, à 50, et à 35; ça semble faisable.
Je vous redonnerai des nouvelles ce soir (afin d'éviter le multipost).
Pour un algorithme "exploratoire", c'est à dire qui teste un grand nombre de variantes, un programme en BASIC est pertinent.
Pour un algorithme "simplifié", qui teste la solution de base et quelques variantes ciblées, une simple feuille de calcul sur tableur semble bien plus pratique.
As-tu la possibilité de travailler sur tableur ?
RECHERCHE D'UNE SOLUTION DE BASE :
Entrer N (nombre de passagers total)
Entrer N1, N2, N3 (nombre de cars)
Entrer P1, P2, P3 (places par car)
Entrer C1, C2, C3 (coûts par car)
Calculer les coûts unitaires (coût par passager) et ordonner les cars... :
CU1, CU2, CU3 : CUi = Ci/Pi
Si les catégories i=1,2,3 ne sont pas triées par coûts unitaires croissant : réordonner les catégories, de façon à ce qu'elles le soient.
Remarque : à ce stade, i=1 devrait correspondre au gros car (supposé plus économique), i=2 le moyen car, i=3 le petit car.
Initialisation :
R = N (passagers restants)
X1 = 0 (nombre de cars de type 1 affectés)
X2 = 0 (nombre de cars de type 2 affectés)
X3 = 0 (nombre de cars de type 3 affectés)
Saturer les cars les plus économiques :
Tant que X1<N1 et R>0 :
X1 = X1 + 1
R = R - C1
Fin Tant Que
Tant que X2<N2 et R>0 :
X2 = X2 + 1
R = R - C2
Fin Tant Que
Tant que X3<N3 et R>0 :
X3 = X3 + 1
R = R - C3
Fin Tant Que
COUT = X1.C1 + X2.C2 + X3.C3
Afficher COUT, R, X1, X2, X3
Erreur : R = R - Pi dans chaque boucle TANT QUE
On retranche la capacité (nombre de places Pi) du dernier car affecté, du nombre de passagers restant (R).
Voici l'agorithme de base sous ALGOBOX :
L'idée est d'affecter car par car, en commençant par les plus économiques (supposés être les plus gros).
Dans les données de coût, j'ai pris 100 pour le chauffeur + 300 pour l'immobilisation + des frais kilométriques variables progressifs avec la taille du car.
1 VARIABLES
2 N EST_DU_TYPE NOMBRE
3 N1 EST_DU_TYPE NOMBRE
4 N2 EST_DU_TYPE NOMBRE
5 N3 EST_DU_TYPE NOMBRE
6 P1 EST_DU_TYPE NOMBRE
7 P2 EST_DU_TYPE NOMBRE
8 P3 EST_DU_TYPE NOMBRE
9 C1 EST_DU_TYPE NOMBRE
10 C2 EST_DU_TYPE NOMBRE
11 C3 EST_DU_TYPE NOMBRE
12 R EST_DU_TYPE NOMBRE
13 COUT EST_DU_TYPE NOMBRE
14 MSG EST_DU_TYPE CHAINE
15 X1 EST_DU_TYPE NOMBRE
16 X2 EST_DU_TYPE NOMBRE
17 X3 EST_DU_TYPE NOMBRE
18 SEUIL EST_DU_TYPE NOMBRE (sert juste à tester si la solution est optimale : fioriture)
19 DEBUT_ALGORITHME
20 N1 PREND_LA_VALEUR 3
21 N2 PREND_LA_VALEUR 5
22 N3 PREND_LA_VALEUR 2
23 P1 PREND_LA_VALEUR 65
24 P2 PREND_LA_VALEUR 50
25 P3 PREND_LA_VALEUR 35
26 C1 PREND_LA_VALEUR 100 + 300 + 600
27 C2 PREND_LA_VALEUR 100 + 300 + 500
28 C3 PREND_LA_VALEUR 100 + 300 + 450
29 LIRE N
30 R PREND_LA_VALEUR N
31 X1 PREND_LA_VALEUR 0
32 X2 PREND_LA_VALEUR 0
33 X3 PREND_LA_VALEUR 0
34 SEUIL PREND_LA_VALEUR 1
35 TANT_QUE ((R > 0) ET (X1 < N1) ) FAIRE
36 DEBUT_TANT_QUE
37 X1 PREND_LA_VALEUR X1 + 1
38 R PREND_LA_VALEUR R - P1
39 FIN_TANT_QUE
40 TANT_QUE ((R > 0) ET (X2 < N2) ) FAIRE
41 DEBUT_TANT_QUE
42 X2 PREND_LA_VALEUR X2 + 2
43 R PREND_LA_VALEUR R - P2
44 FIN_TANT_QUE
45 TANT_QUE ((R > 0) ET (X3 < N3) ) FAIRE
46 DEBUT_TANT_QUE
47 X3 PREND_LA_VALEUR X3 + 1
48 R PREND_LA_VALEUR R - P3
49 FIN_TANT_QUE
50 COUT PREND_LA_VALEUR X1*C1 + X2*C2 + X3*C3
51 MSG PREND_LA_VALEUR "X1="+X1 +" X2="+X2 +" X3="+X3 + " COUT = " + COUT +" SIEGES VACANTS = "+ (-R)
52 AFFICHER MSG
53 MSG PREND_LA_VALEUR "COUT = " + X1 +"*"+ C1 + " + " + X2 +"*"+ C2 + " + " + X3 +"*"+ C3 + " = " + COUT
54 AFFICHER MSG
55 SI (R > 0) ALORS
56 DEBUT_SI
57 MSG PREND_LA_VALEUR "ATTENTION : il manque " + R + " places pour emmener tous les passagers !"
58 AFFICHER MSG
59 FIN_SI
60 SI (ABS(R) < SEUIL) ALORS
61 DEBUT_SI
62 AFFICHER "La solution est OPTIMALE !"
63 FIN_SI
64 FIN_ALGORITHME
Le même ALGO, avec 3 variantes de type +1 -1 à la fin...
1 VARIABLES
2 N EST_DU_TYPE NOMBRE
3 N1 EST_DU_TYPE NOMBRE
4 N2 EST_DU_TYPE NOMBRE
5 N3 EST_DU_TYPE NOMBRE
6 P1 EST_DU_TYPE NOMBRE
7 P2 EST_DU_TYPE NOMBRE
8 P3 EST_DU_TYPE NOMBRE
9 C1 EST_DU_TYPE NOMBRE
10 C2 EST_DU_TYPE NOMBRE
11 C3 EST_DU_TYPE NOMBRE
12 R EST_DU_TYPE NOMBRE
13 COUT EST_DU_TYPE NOMBRE
14 MSG EST_DU_TYPE CHAINE
15 X1 EST_DU_TYPE NOMBRE
16 X2 EST_DU_TYPE NOMBRE
17 X3 EST_DU_TYPE NOMBRE
18 SEUIL EST_DU_TYPE NOMBRE
19 COUT1 EST_DU_TYPE NOMBRE
20 COUT2 EST_DU_TYPE NOMBRE
21 COUT3 EST_DU_TYPE NOMBRE
22 DEBUT_ALGORITHME
23 N1 PREND_LA_VALEUR 3
24 N2 PREND_LA_VALEUR 5
25 N3 PREND_LA_VALEUR 2
26 P1 PREND_LA_VALEUR 65
27 P2 PREND_LA_VALEUR 50
28 P3 PREND_LA_VALEUR 35
29 C1 PREND_LA_VALEUR 100 + 300 + 600
30 C2 PREND_LA_VALEUR 100 + 300 + 500
31 C3 PREND_LA_VALEUR 100 + 300 + 450
32 LIRE N
33 R PREND_LA_VALEUR N
34 X1 PREND_LA_VALEUR 0
35 X2 PREND_LA_VALEUR 0
36 X3 PREND_LA_VALEUR 0
37 SEUIL PREND_LA_VALEUR 1
38 TANT_QUE ((R > 0) ET (X1 < N1) ) FAIRE
39 DEBUT_TANT_QUE
40 X1 PREND_LA_VALEUR X1 + 1
41 R PREND_LA_VALEUR R - P1
42 FIN_TANT_QUE
43 TANT_QUE ((R > 0) ET (X2 < N2) ) FAIRE
44 DEBUT_TANT_QUE
45 X2 PREND_LA_VALEUR X2 + 1
46 R PREND_LA_VALEUR R - P2
47 FIN_TANT_QUE
48 TANT_QUE ((R > 0) ET (X3 < N3) ) FAIRE
49 DEBUT_TANT_QUE
50 X3 PREND_LA_VALEUR X3 + 1
51 R PREND_LA_VALEUR R - P3
52 FIN_TANT_QUE
53 COUT PREND_LA_VALEUR X1*C1 + X2*C2 + X3*C3
54 MSG PREND_LA_VALEUR "X1="+X1 +" X2="+X2 +" X3="+X3 + " COUT = " + COUT +" SIEGES VACANTS = "+ (-R)
55 AFFICHER MSG
56 MSG PREND_LA_VALEUR "COUT = " + X1 +"*"+ C1 + " + " + X2 +"*"+ C2 + " + " + X3 +"*"+ C3 + " = " + COUT
57 AFFICHER MSG
58 SI (R > 0) ALORS
59 DEBUT_SI
60 MSG PREND_LA_VALEUR "ATTENTION : il manque " + R + " places pour emmener tous les passagers !"
61 AFFICHER MSG
62 FIN_SI
63 SI (ABS(R) < SEUIL) ALORS
64 DEBUT_SI
65 AFFICHER "La solution est OPTIMALE !"
66 FIN_SI
67 AFFICHER "*********** VARIANTES ************"
68 X1 PREND_LA_VALEUR X1 - 1
69 X2 PREND_LA_VALEUR X2 + 1
70 R PREND_LA_VALEUR R + P1 - P2
71 SI ((X1 >=0) ET (X2 <= N2) ET (R <= 0)) ALORS
72 DEBUT_SI
73 COUT1 PREND_LA_VALEUR X1*C1 + X2*C2 + X3*C3
74 MSG PREND_LA_VALEUR "X1="+X1 +" X2="+X2 +" X3="+X3 + " COUT = " + COUT1 +" SIEGES VACANTS = "+ (-R)
75 AFFICHER MSG
76 FIN_SI
77 X2 PREND_LA_VALEUR X2 - 1
78 X3 PREND_LA_VALEUR X3 + 1
79 R PREND_LA_VALEUR R + P2 - P3
80 SI ((X1 >=0) ET (X3 <= N3) ET (R <= 0)) ALORS
81 DEBUT_SI
82 COUT2 PREND_LA_VALEUR X1*C1 + X2*C2 + X3*C3
83 MSG PREND_LA_VALEUR "X1="+X1 +" X2="+X2 +" X3="+X3 + " COUT = " + COUT2 +" SIEGES VACANTS = "+ (-R)
84 AFFICHER MSG
85 FIN_SI
86 X1 PREND_LA_VALEUR X1 + 1
87 X2 PREND_LA_VALEUR X2 - 1
88 R PREND_LA_VALEUR R - P1 + P2
89 SI ((X2 >=0) ET (X3 <= N3) ET (R <= 0)) ALORS
90 DEBUT_SI
91 COUT3 PREND_LA_VALEUR X1*C1 + X2*C2 + X3*C3
92 MSG PREND_LA_VALEUR "X1="+X1 +" X2="+X2 +" X3="+X3 + " COUT = " + COUT3 +" SIEGES VACANTS = "+ (-R)
93 AFFICHER MSG
94 FIN_SI
95 FIN_ALGORITHME
Dans le cas où le nombre de types de cars est faible :
Une recherche exaustive est alors possible.
Si par exemple il n'y a que 3 types de cars, deux boucles imbriquées sur les deux premiers types suffisent.
Le nombre de cars du troisième type nécessaire se calcule pour obtenir la capacité requise.
Il suffit de veiller au respect des contraintes N1, N2, N3.
Et de retenir la solution à cout minimal.
1 VARIABLES
2 N EST_DU_TYPE NOMBRE
3 N1 EST_DU_TYPE NOMBRE
4 N2 EST_DU_TYPE NOMBRE
5 N3 EST_DU_TYPE NOMBRE
6 P1 EST_DU_TYPE NOMBRE
7 P2 EST_DU_TYPE NOMBRE
8 P3 EST_DU_TYPE NOMBRE
9 C1 EST_DU_TYPE NOMBRE
10 C2 EST_DU_TYPE NOMBRE
11 C3 EST_DU_TYPE NOMBRE
12 R EST_DU_TYPE NOMBRE
13 COUT EST_DU_TYPE NOMBRE
14 MSG EST_DU_TYPE CHAINE
15 X1 EST_DU_TYPE NOMBRE
16 X2 EST_DU_TYPE NOMBRE
17 X3 EST_DU_TYPE NOMBRE
18 I1 EST_DU_TYPE NOMBRE
19 I2 EST_DU_TYPE NOMBRE
20 I3 EST_DU_TYPE NOMBRE
21 COUTMIN EST_DU_TYPE NOMBRE
22 DEBUT_ALGORITHME
23 N1 PREND_LA_VALEUR 3
24 N2 PREND_LA_VALEUR 5
25 N3 PREND_LA_VALEUR 2
26 P1 PREND_LA_VALEUR 65
27 P2 PREND_LA_VALEUR 50
28 P3 PREND_LA_VALEUR 35
29 C1 PREND_LA_VALEUR 100 + 300 + 600
30 C2 PREND_LA_VALEUR 100 + 300 + 500
31 C3 PREND_LA_VALEUR 100 + 300 + 450
32 COUTMIN PREND_LA_VALEUR N1*C1 + N2 * C2 + N3 * C3 + 1
33 LIRE N
34 POUR I1 ALLANT_DE 0 A N1
35 DEBUT_POUR
36 POUR I2 ALLANT_DE 0 A N2
37 DEBUT_POUR
38 R PREND_LA_VALEUR N - I1*P1 - I2*P2
39 I3 PREND_LA_VALEUR - FLOOR(- R/P3)
40 R PREND_LA_VALEUR R - I3*P3
41 SI (R<=0 ET I3>=0 ET I3<=N3) ALORS
42 DEBUT_SI
43 COUT PREND_LA_VALEUR I1*C1 + I2*C2 + I3*C3
44 SI (COUT <= COUTMIN) ALORS
45 DEBUT_SI
46 COUTMIN PREND_LA_VALEUR COUT
47 X1 PREND_LA_VALEUR I1
48 X2 PREND_LA_VALEUR I2
49 X3 PREND_LA_VALEUR I3
50 MSG PREND_LA_VALEUR "COUT = " + X1 +"*"+ C1 + " + " + X2 +"*"+ C2 + " + " + X3 +"*"+ C3 + " = " + COUT + " SIEGES VACANTS = "+ (-R)
51 AFFICHER MSG
52 FIN_SI
53 FIN_SI
54 FIN_POUR
55 FIN_POUR
56 R PREND_LA_VALEUR N - N1*P1 - N2*P2 - N3*P3
57 SI (R > 0) ALORS
58 DEBUT_SI
59 MSG PREND_LA_VALEUR "ATTENTION : il manque " + R + " places pour emmener tous les passagers !"
60 AFFICHER MSG
61 FIN_SI
62 FIN_ALGORITHME
Annuler
connectez vous