Exercice s

OPM3001 - Techniques quantitatives de gestion -Cahier dexercices corrigs

Eric LALLET, Jean-Luc RAFFYTELECOM COLE DE MANAGEMENT - 1re ANNE

Dcembre 2013

2 Eric LALLET, Jean-Luc RAFFY

Table des matires

1 Exercices 51.1 Les problmes dordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Les Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3 Recherche du plus court chemin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.4 Flot Maximal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.5 Programmation linaire : la mthode gomtrique . . . . . . . . . . . . . . . . . . . . . . 121.6 Programmation linaire : le simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.7 Non classifis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Corrections 232.1 Ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.2 Arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.3 Plus court chemin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.4 Flot maximal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.5 Mthode gomtrique et Simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422.6 Modlisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3 Annexes 793.1 Annales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793.2 Classement des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

Eric LALLET, Jean-Luc RAFFY 3

Chapitre 1

Exercices

1.1 Les problmes dordonnancement

Exercice 1.1.1 (Organisation dun colloque)

En arrivant au travail, vous trouvez sur votre bureau cette note trs claire :

La premire chose faire est de trouver le site de la confrence. Par exemple un htel qui pourrahberger les participants et qui possde des salles de confrence. Il faut compter 3 semaines pour letrouver.

Dailleurs pour toutes ces recherches, et tout laspect logistique, tu dois tentourer dune quipe, lecomit dorganisation, qui tu dlgueras lessentiel de ces tches. Choisir cette quipe devrait teprendre 1 semaine.Il te faut aussi choisir le comit de programme. a sera lquipe charge de laspect scientifique ducolloque. Compte 3 semaines pour ce choix. Ce comit de programme devra se runir 2 fois avantla confrence. Une premire fois, avant lappel communications, pour fixer les grandes lignes duprogramme qui seront indiques dans cet appel. Et une seconde fois, aprs la slection finale desarticles, et au moins 3 semaines avant le colloque, pour fixer en dtail le programme final.Le temps que les articles soient crits et envoys, il faut laisser aux auteurs, un dlais de 8 semainesentre lappel communications et la slection. Il faut aussi laisser 8 semaines au jury entre la rceptiondes articles, et la slection finale.Tu dois aussi te mettre daccord avec un imprimeur pour ldition des proceedings. En gnral il fautcompter 6 semaines pour limpression condition que tous les articles aient t mis en forme selonles conventions de limprimeur. Pour cela, accorde 4 semaines aprs la slection finale aux diffrentsauteurs pour quils fassent cette mise en forme. Il faut que tu aies reu les livres imprims au moins 1semaine avant le colloque.Prvoie aussi un programme social pour occuper les confrenciers en dehors du temps des conf-rences. Le temps fort sera un banquet lors dune soire. Ton comit dorganisation devrait pouvoirchoisir le lieu de ce banquet en 2 semaines. Il devra aussi se mettre daccord avec lhtel pour lesmenus et les prix des repas lors de la confrence. Pour cela compte 1 semaine aprs le choix delhtel. Une fois tout cela connu, laisse encore 1 semaine au comit dorganisation pour fixer le prixque devront payer les confrenciers. Ce prix et le programme social devront figurer dans lappel communications.De plus, comme on profite de sponsors gnreux, tu devrais profiter des deux runions du comit deprogramme pour tester lhtel et le lieu du banquet. Donc programme la premire runion du comitde programme dans lhtel, et prvoie un dner sur le lieu du banquet le soir de la seconde runion.Voila, je pense que je nai rien oubli.

En effet, le collgue qui devait organiser la prochaine confrence sur les techniques quantitatives Paris vient dtre mut, et cest vous qui avait hrit de la tche. Ayant dj eu lexprience de genredorganisation, il vous a donc list les tches accomplir.


La date a t fixe. Ce sera du 17 au 20 dcembre 2009 pour que les confrenciers puissent, sils lesouhaitent, prolonger leur sjour Paris lors des ftes.

Quand devez-vous commencer au plus tard organiser tout cela pour que le colloque puisse bien dbuterle 17 dcembre ?

Il nest jamais simple de fixer une date de runion. . . Quelles sont les marges dont vous disposez pourles deux runions du comit de programme pour fixer une date sans que cela ne ralonge votre prparation ?

Correction page 23

Exercice 1.1.2 (Tarte Tatin (second problme du contrle de septembre 2009))

Deux amis, Apollodore et Aristodme se dcident presque la dernire minute de faire une tarte tatinpour recevoir des amis qui doivent arriver 1 heure plus tard. Ils veulent laccompagner dune crme anglaise.Voici les diverses actions quils doivent raliser ainsi que leur dure.

Pour la pte brise : Prparer la pte (5 minutes) Laisser reposer la pte (30 minutes) taler la pte (5 minutes)

Pour la tarte Tatin : Prparation du moule (5 minutes) : Prendre un moule manquer... Verser 125g de sucre sur le fond.

Parsemer sur le dessus 120g beurre coup en petits morceaux. Prparation des pommes (10 minutes) : Peler 8 belles pommes, enlever le coeur et les couper en

quartiers. Mise en place des pommes (10 minutes) : Placer les quartiers de pommes dans le moule, sur le sucre

et le beurre. Saupoudrer avec 125g de sucre Caramlisation des pommes (5 minutes) : Placer le moule sur un feu vif, jusqu ce que le caramel

commence dorer. Mise en place de la pte (5 minutes) : Recouvrir les pommes de la pte tale. Rentrer le bord

lintrieur du moule. Faire quelques trous pour laisser chapper la vapeur. Cuisson (15 minutes) : Enfourner dans un four chaud, thermostat 9 pendant 15 minutes, le temps que

la pte soit bien dore.

Pour la crme anglaise : Prparer la crme (15 minutes). Laisser refroidir (15 minutes). Mettre au rfrigrateur (30 minutes minimum).

Apollodore se propose pour prparer la pte, et soccuper ensuite de la tarte Tatin, pendant quAristo-dme soccupera de prparer la crme anglaise puis talera la pte.

Aristodme suggre quApollodore commence immdiatement la prparation de la Tarte pendant quelui commencera la pte bris. Il prparera la crme anglaise durant le temps de repos de la pte, et ensuitetalera la pte.

Lequel des deux scnarios conseillez-vous de mettre en uvre ?Correction page 25

Exercice 1.1.3 (Petits mfaits labbaye de Shrewsbury (second problme du contrle de septembre 2011))

Juste avant loffice de Sexte (loffice de la mi-journe) Frre Jrome crie au scandale : le vin de messea disparu ! Il en faut plus pour affoler lAbb Radulphe, mais il demande quand mme Frre Cadfael defaire enqute pour savoir ce qui sest pass.

Frre Cadfael obtient vite certaines certitudes :


la fin de loffice des Laudes (6h30 du matin), le vin de messe a t enferm sous clef dans unmeuble de la sacristie.

Au dbut de loffice de Sexte (midi), le vin ntait plus l. Seuls les membres de labbaye taient prsents dans les murs durant cette matine. Le voleur a pris la clef dans le bureau du Prieur, et ly a remise aprs son mfait. Frre Cadfael

constate quil faut au minimum 20 minutes daffile pour faire ces actions.Durant cette matine, tous les frres valides ont travaills ensemble sauf trois dentre eux qui ont eu des

tches spcifiques. Seul lun de ces trois a pu avoir le temps de voler ce vin. Aprs enqute, voici ce quil apu tablir des emplois du temps de ces trois frres :Emploi du temps de Frre Daniel : Juste aprs les Laudes, Frre Daniel est all au potager avec Frre

Yves. Ils ont pass 2h rcolter des lgumes et des plantes mdicinales. Frre Daniel est ensuiteall rejoindre Frre Thomas aux cuisines o ils ont pass 1h15 prparer les repas. Enfin il a rejointlatelier mdicinal o pendant 1h45 il a prpar diverses concoctions, pommades et onguents.

Emploi du temps de Frre Yves : Juste aprs les Laudes, Frre Yves est all au potager avec Frre Daniel.Ils ont pass 2h rcolter des lgumes et des plantes mdicinales. Frre Yves est ensuite all lalproserie apporter certains de ces lgumes et plantes. Cela lui a pris 1h. Enfin il est all linfirmerieo avec Frre Thomas il a pass 2h soigner les malades.

Emploi du temps de Frre Thomas : Juste aprs les Laudes, Frre Thomas est all en ville faire descourses. Cela lui a pris 2h15. Ensuite il est all aux cuisines avec Frre Daniel o ils ont pass1h15 prparer les repas. Enfin Frre Thomas est all linfirmerie o avec Frre Yves il a pass 2h soigner les malades.

Pour Frre Cadfael, il ny a plus de mystre. Seul un des trois frres a eu le temps de commettre lemfait !

Quel frre a pu commettre le vol ? De combien de temps a-t-il dispos ?Correction page 26

1.2 Les Arbres

Exercice 1.2.1 (Promesse lectorale)

FIG. 1.1 Carte de la commune

Le rseau routier dune petite commune rurale a t laiss labandon si longtemps quune bonne partiedes routes sont devenues des chemins. Lors des dernires lections le maire a promis quil allait remettreen tat suffisamment de routes pour que toutes les habitations de la commune puissent rejoindre le centre-bourg par une route digne de ce nom. Il lui faut maintenant tenir sa promesse, mais bien sr, il voudraitengager un minimum de dpenses pour cela.

La carte de la commune et la liste des habitations relier au centre-bourg sont sur la figure 1.1. Le cotde la remise en tat dune route est directement proportionnel sa longueur. Voici la longueur des diffrentschemins :


ch1=500m ch2=1200m ch3=1400 ch4=800m ch5=1400m ch6=1600ch7=1300m ch8=1500m ch9=1400 ch10=500 ch11=1400m ch12=1600mch13=1300 ch14=1500 ch15=1700 ch16=1300

Correction page 27

Exercice 1.2.2 (Combien de nains faut-il pour creuser les tunnels ? (premier problme du contrle davril 2009))

Gorog est le nain contrematre responsable de la rcolte minire dune section comportant six salles enexploitation. Mais sa journe commence par une mauvaise nouvelle. Le responsable de la fabrication despaniers utiliss pour transporter le minerai dos de chvres a dcid den agrandir la taille. Bien sr, celapart dune bonne intention : avec des paniers plus grands, il y aura moins de voyages faire pour transporterle minerai. Mais il y a un problme. Les couloirs qui permettent de circuler jusquaux salles ne seront plusassez larges pour la circulation des chvres (charges de leurs nouveaux paniers).

Gorog va donc devoir utiliser tous ses moyens pour largir ces couloirs ! Comme il doit rpondre unecommande urgente en minerai, il veut juste, dans une premier temps, nlargir que les couloirs ncessairespour atteindre toutes les salles.

Sa section comporte six salles rparties sur deux niveaux. Les couloirs de la partie suprieure (couloirdentre, et les couloirs 1 3) sont percs dans de la roche friable facile creuser. Les couloirs de la partieinfrieur (couloirs 4 6) sont percs dans une roche trs dure beaucoup plus longue creuser. Enfin lesdeux escaliers permettant le passage entre les deux niveaux sont percs dans une roche intermdiaire.

Gorog a calcul quil fallait 1 heure de travail pour 1 nain pour largir 1 mtre de couloir dans la rochefriable. Il faut 2 heures de travail pour 1 nain pour 1 mtre de roche intermdiaire, et 3 heures pour la rochedure.

Voici la longueur des diffrents couloirs (voir schma de la grotte 1.2) :

Couloir dentre : 7m Couloir 1 : 50m Couloir 2 : 46m Couloir 3 : 35m Escalier 1 : 55mCouloir 4 : 55m Couloir 5 : 30m Couloir 6 : 45m Escalier 2 : 60m

FIG. 1.2 Schma de la grotte

Quels couloirs devront tre largis en priorit pour que toutes les salles soient nouveau exploitablesau plus vite ?

La journe de travail dun nain dure 8 heures. Combien de nains Gorog devra-t-il runir pour russir largir suffisamment de couloirs pour rendre toutes les salles accessibles en 1 seule journe ?

Correction page 30


1.3 Recherche du plus court chemin

Exercice 1.3.1 (Voyage Lyon-Agen)

FIG. 1.3 Les routes entre Lyon et Agen

Un voyageur doit aller en voiture de Lyon Agen. En regardant les cartes il a dgag diverses optionspour faire sa route (voir figure 1.3).

Il peut couper le massif-central par les nationales en passant le Le Puy-en-Velay, Brioude et Cahors. Il peut passer par les autoroutes du sud de la France, en passant par Orange, Montpellier, Narbonne,

Toulouse et Montauban. Il peut passer par les autoroutes du centre de la France, en rejoingnant lA72 Feurs, et ensuite en

passant par Clermont-Ferrand, Brive, Cahors, Montauband. Il peut enfin faire un mlange de tout cela en profitant ventuellement de lA75 qui coupe toutes ces

routes.Sachant quil ralise une moyenne de 70km/h sur les nationales et dpartementales et de 110km/h sur

les autoroutes quel chemin doit-il emprunter pour faire le trajet le plus rapidement possible ? Et quel est letemps de ce trajet ?

Correction page 31.

Exercice 1.3.2 (Le banquet (premier problme du contrle de septembre 2009))

Apollodore, un jeune traiteur, vient de se mettre son compte et propose ses services pour des banquets.En une journe de travail il arrive produire 50 repas. Par contre il ne possde pas encore ses cuisines. Ila cependant trouv une grosse collectivit qui possde des cuisines sous-utilises trois jours par semaineet qui loue alors des espaces de travail. La location, mme dune seule journe, donne aussi laccs durantla semaine un espace de stockage en chambre froide o le traiteur peut conserver jusqu 100 repas. Cetespace doit tre totalement libr le vendredi soir.

En tenant compte du prix de location (variable), et des matires premires utilises, Apollodore a calculle prix dune journe de production (50 repas) suivant la journe :

Jour lundi mardi jeudiPrix 2k euros 2k euros 1k euros

Pour la semaine venir il a trouv trois demandes pour 100 repas qui pourraient lui convenir. Sil lesaccepte, voici les jours et les prix convenus :

Jour mardi mercredi vendrediPrix 7k euros 4k euros 4k euros


Les jours o il sert un banquet, il na pas le temps de produire des repas. De plus chaque banquet luicote 1k euros de frais divers (transport, services. . . ) soustraire aux revenus indiqus ci dessus.

Est-ce quApollodore a intrt travailler cette semaine ? Si oui, selon quel planning ? Sinon pourquoi ?Correction page 33.

Exercice 1.3.3 (Le banquet (suite) (contrle septembre 2009))

Apollodore connat un ami, Aristodme, exactement dans les mmes conditions que lui. Ils peuventtravailler ensemble durant cette semaine. Aristodme devra lui aussi payer la location dun espace de travail,donc le prix des repas supplmentaires produits reste le mme. Par contre il peut trs bien continuer produire des repas les jours o Apollodore sert les banquets (sil a accs aux cuisines ce jour l !).

Leur conseillez-vous de travailler ensemble cette semaine (notez quils peuvent trs bien ne pas travaillerles mmes jours ni le mme nombre de jours) ?

Si oui, selon quel planning ? Sinon pourquoi ?Correction page 34.

1.4 Flot Maximal

Exercice 1.4.1 (Cursus de formation)

Un organisme qui vend des formations sous-traite ses enseignements dans trois coles. Une formationquelle propose son catalogue ncessite la validation des trois units de valeur (UV1, UV2, et UV3). Il fautavoir valid lUV1 pour suivre lUV2, et avoir valid lUV2 pour suivre lUV3.

La deuxime cole a des accords dquivalence avec les deux autres. Elle peut recevoir des lves ayantvalids des UV dans les deux autres coles, et ses lves peuvent aussi continuer leur cursus dans les deuxautres coles.

La troisime cole a runi les UV2 et UV3 au sein dun seul module indivisible. Voici le tableau desdates, capacits (en nombre dlves) et cot (en k euros/lve) pour les diffrentes UV et cole.

UV1 UV2 UV3Dbut : 1er septembre Dbut : 10 dcembre Dbut : 1er fvrier

Premire Fin : 30 novembre Fin : 15 fvrier Fin : 15 maicole Capacit : 40 Capacit : 20 Capacit : 25

Cot : 10 k euros Cot : 10 k euros Cot : 15 k eurosDbut : 1er octobre Dbut : 5 janvier Dbut : 1er avril

Seconde Fin : 15 dcembre Fin : 15 mars Fin : 15 juincole Capacit : 30 Capacit : 35 Capacit : 30

Cot : 8 k euros Cot : 8 k euros Cot : 8 k eurosDbut : 15 octobre Dbut : 20 janvier

Troisime Fin : 15 janvier Fin : 15 juincole Capacit : 20 Capacit : 35

Cot : 13 k euros Cot : 20 k euros

premire lecture, la premire cole peut former 20 lves, la seconde 30 et la troisime 20. Doncon pourrait former 70 lves. Mais en profitant des quivalences entre la seconde cole et les deux autres,lorganisme de formation doit pouvoir proposer mieux. Combien de formations peut-elle proposer cetteanne ?

Correction page 37.


Exercice 1.4.2 (Cursus de formation (suite))

Finalement lorganisme de formation a reu une demande pour 63 formations. Quel cursus lorganismedoit proposer ces 63 lves pour obtenir ces formations moindre prix ?

Correction page 39.

Exercice 1.4.3 (Travaux sur la route (premier problme du contrle davril 2010))

FIG. 1.4 Carte des usines, magasins et voies praticables

Une entreprise possde deux usines et deux magasins pour vendre ses produits. Au fil des ans elle a suadapter les capacits de production et de transport de ses usines aux volumes de vente de ses magasins. Sonusine dAmiens produit chaque mois 100 containers de marchandise. Son magasin de Paris vend chaquemois ce mme volume. Ils sont transports par camion par lautoroute A16. Son usine de Rouen produitchaque mois 120 containers de marchandise. Son magasin du Havre vend chaque mois ce mme volume.Ils sont transports par pniche par la Seine.

Tout allait pour le mieux jusquau jour o des travaux ont dbut sur lautoroute A16 provoquant desbouchons rguliers. Lentreprise saperoit quelle narrivera plus faire passer que 50 containers par moisentre Amiens et Paris. Son service de logistique fait une rapide tude, mais ne trouve pas dautres routespratiques entre Amiens et Paris. Par contre elle a calcul quelle pouvait faire circuler jusqu 80 containersentre Amiens et le Havre par lautoroute A29. De plus en utilisant la Seine elle sait transporter autant quecontainers quelle veut depuis Rouen vers Paris ou le Havre.

Grce ces nouvelles options lentreprise espre pouvoir nouveau vendre un maximum de sa produc-tion. Il faut donc quelle rorganise ses transports1.

Trouvez le modle qui va permettre de rsoudre cette recherche de retour la vente maximale.Modlisez la situation actuelle (50 containers qui transitent dAmiens vers Paris par lautoroute A16, et

120 containers qui transitent de Rouen vers le Havre par la Seine), et prouvez quelle nest pas optimale.Toujours en partant de cette situation, trouvez la solution optimale qui demandera le moins de change-

ment possible dans les habitudes de transport.Correction page 41.

1Notez, quune fois arrivs au Havre ou Paris, les containers ne peuvent plus bouger. Seuls les transports depuis Amiens ouRouen jusqu un magasin sont possibles.


1.5 Programmation linaire : la mthode gomtrique

Voir les exercices 1.6.1 page 12 et 1.6.2 .page 12.

Exercice 1.5.1 (La route du sel)

Au quatorzime sicle, un Touareg compte gagner un peu dor en investissant dans des dromadairesquil sait pouvoir revendre Tombouctou. Comme sa route passe par Taoudeni, il pense aussi y acheter dusel pour tirer davantage de bnfice de son voyage. Il sait quil pourra obtenir au terme de son voyage 10po (pice dor) de bnfice par dromadaire, et 1 pa (pice dargent, 1 po = 10 pa) de bnfice par kg de sel.

Avant toute chose il faut dj quil achte ces dromadaires et ce sel. Chaque dromadaire lui cote 10 po,et chaque kg de sel 0,2 pa. Il peut investir 65 po.

Sachant quun dromadaire peut transporter jusqu 150 kg de sel, comment ce Touareg doit investir sonpcule pour tirer le bnfice maximal de son investissement ?

Correction page 42.

1.6 Programmation linaire : le simplexe

Exercice 1.6.1 (Une histoire de fromage)

Une laiterie sest spcialise dans deux fromages. Le premier est un AOC qui exige plus dheures detravail et un lait en provenance dune rgion bien prcise. Le second demande moins de travail, et peut trefabriqu avec nimporte quel lait. Par contre sa vente dgage une marge moindre.

La laiterie dispose de 21 000 heures de travail annuel, elle reoit 4 millions de litres de lait de la zoneAOC, et 6 millions de litres dautres zones.

Le tableau suivant indique les ressources ncessaires pour produire 1 tonne de fromage.

heures de travail litres de laitFromage par tonne de fromage par tonne de fromage

Fromage 1 (AOC) 30 h 10 000 lFromage 2 15 h 7 500 l

Sachant quun kilo du fromage AOC dgage une marge de 3 euros et quun kilo de lautre fromageseulement 1 euro, quelle production doit fabriquer cette laiterie pour optimiser ses bnfices ?

Correction page 43.

Exercice 1.6.2 (Une histoire de fromage (bis))

Mme question, mais cette fois ci, avec une marge de 2 euros par kilo pour le fromage AOC et toujoursdun seul euro pour le second fromage.

Correction page 44.

Exercice 1.6.3 (Problme lectrique)

Un revendeur dlectricit a promis sa clientle quau moins 25% de son lectricit serait doriginerenouvelable. Il a calcul que pour lanne qui arrive il aura un march de 18 TWh (trawattheure). Il aaussi pr-slectionn trois fournisseurs qui il va acheter son lectricit en gros. Voici les quantits (enTWh), le taux dlectricit renouvelable et la marge dgage (en k euro/TWh) que peuvent lui fournir cestrois producteurs.


% dlectricit Quantit dlectricit Margerenouvelable achetable (TWh) (k Euro/TWh)

Producteur 1 10 % 25 900Producteur 2 46 % 6 700Producteur 3 100 % 4 500

Chez quels producteurs et en quelle quantit ce revendeur doit-il acheter son lectricit pour avoir lemeilleurs bnfice possible ?

Correction page 46.

Exercice 1.6.4 (Problme lectrique (bis))

Mme problme mais avec ces nouvelles marges :

% dlectricit Quantit dlectricit Margerenouvelable achetable (TWh) (k euros/TWh)

Producteur 1 10 % 25 850Producteur 2 46 % 6 710Producteur 3 100 % 4 500

Pour des raisons politiques le revendeur aimerait privilgier le second producteur. Est-il possible dache-ter une partie de llectricit chez lui sans faire baisser les profits ?

Correction page 48.

1.7 Non classifis

Dans les sections prcdentes il tait ais de deviner la technique mettre en uvre pour les exercicespuisque ctait le sujet la section. Voila pourquoi la plupart des exercices ont t placs dans cette derniresection. Ainsi vous naurez plus da priori sur le type de modlisation que vous devrez utiliser pour lesrsoudre. Il faudra le trouver par votre analyse du problme.

Mais si pour vos rvisions vous souhaitez avoir un classement des exercices, vous le trouverez en an-nexe : un classement par annale page 79 et un classement par technique page 79.

Exercice 1.7.1 (Commerce de guilde (premier problme du contrle davril 2008))

Une guilde du Seigneur des Anneaux Online a dcid de faire commerce de son artisanat. Elle vientde recevoir une commande pour un ensemble de 10 arbaltes, 10 sets complets darmures lourdes, et 10pes. Pour raliser cette commande il faut rcolter deux types de fer (le fer de nain et le fer ancien), dubois et du cuir. Il faut ensuite faire divers alliages de fer, traiter le bois et le cuir. Enfin il faut raliser lesobjets. Elle dcide de confier ces tches trois de ses membres :

Tawar : Elfe chasseur menuisier, il aura pour tche daller rcolter le bois, de chasser pour rapporter lecuir. Cest aussi lui qui fera le traitement du bois et du cuir. Enfin cest lui qui ralisera les arbaltes.

Gorog : Nain prospecteur et ferronnier, il aura pour tche de ramasser le fer de nain. Cest aussi luiqui aura la tche de faire les armures. Mais attention, Gorog exige davoir le droit une pause de 15minutes la taverne entre ses 2 tches !

Albin : Humain prospecteur et fabriquant darme, il aura pour tche de ramasser le fer ancien. Cestlui qui transformera tout le fer (fer de nain, et fer ancien) afin dobtenir les alliages utiles aux arbaltes,aux armures et aux pes. Enfin cest lui qui ralisera les pes.

Tawar prvoit de passer 45 minutes pour rcolter la totalit du cuir et du bois. Il lui faudra 15 minutespour en faire le traitement. Les arbaltes sont fabriques avec du bois traits et un alliage de fer. Il lui faudra20 minutes pour toutes les faire.

Gorog prvoit de passer 1h pour rcolter le fer de nain. La fabrication de ses armures utilisent desalliages de fer et du cuir trait. Il pense pouvoir faire toutes les armures en 25 minutes.


Albin passera 1h ramasser le fer ancien. Il lui faudra 20 minutes pour raliser les alliages. Ensuitepour fabriquer toutes les pes qui ne ncessitent que des alliages de fer, il lui faudra 10 minutes.

Une fois tout ralis, Albin doit runir la commande pour aller la livrer. Cela doit lui prendre 10 minutes.Combien de temps faut-il prvoir pour livrer cette commande ?Gorog a-t-il retard la livraison cause de sa pause la taverne ? Quelle est la pause maximale quil

peut faire sans retarder la livraison ?Correction page 49

Exercice 1.7.2 (Commerce de guilde (suite) (second problme du contrle davril 2008))

Les pes et les arbaltes ont satisfait les clients. La guilde a reu de nombreuses commandes. Elledcide de les produire en srie. Pour fabriquer une arbalte il faut ramasser 25 morceaux de bois, et 20blocs de fer de nain. Pour fabriquer une pe il faut 25 blocs de fer ancien et 20 blocs de fer de nain. Tawarpeut ramasser 1000 morceaux de bois par semaine, Gorog 1000 blocs de fer de nain et Albin 1000 blocs defer ancien.

Sachant que la guilde vend une pe pour 1 pice dor (1 pice dor = 1000 pices dargent) et unearbalte pour 500 pices dargent, quel est le gain maximal quelle peut faire par semaine.

Gorog a ngoci de recevoir 1 chope de bire par pe vendue, et 2 chopes par arbalte vendue. Or cettesemaine cest lui qui dirige la production. Sachant quil va privilgier son intrt (la bire !) quelles vonttre les pertes de gain pour la guilde cette semaine ?

Correction page 50

Exercice 1.7.3 (Reconstruction)

Vous tes le ministre du budget dun petit pays victime dune catastrophe naturelle qui a dtruit touteinfrastructure et quasiment toutes les ressources de production sauf celles situes dans la ville de Coude-bolle.

Le ministre de lquipement a fait chiffrer par ses services les cots de reconstruction du rseau routierentre les principales villes (seules peuvent tre construites, les routes dont les cots sont indiqus dans letableau suivant)

Coudebolle Borivage Ollala Pompays TecugeCoudebolle 3000 7000 7000Borivage 2000 4000

Ollala 2000 3000Pompays 6000Tecuge

Quelle solution allez-vous adopter pour obtenir un rseau routier minimal au moindre cot ? On entendpar rseau routier minimal, un rseau permettant daller de nimporte quelle ville vers nimporte quelleautre.

Correction page 51

Exercice 1.7.4 (Reconstruction (suite))

Le ministre de lindustrie intervient alors et vous reproche davoir une vue court terme et quil fautaussi prendre en compte le fait que toutes les ressources de production sont maintenant concentres Cou-debolle.

Il vous transmet donc les cots de transport (par tonne) estims entre les diffrentes villes.


Coudebolle Borivage Ollala Pompays TecugeCoudebolle 3 7 7Borivage 4 2 4

Ollala 6 4 2 3Pompays 3 6Tecuge 8 8 6 8

(Vous aurez remarqu que le cot de transport de A vers B nest pas obligatoirement le mme que de Bvers A).

En supposant que le rseau routier est complet (toutes les routes possibles existent), optimisez les cotsde transport partir de Coudebolle vers toutes les villes.

Correction page 51

Exercice 1.7.5 (Reconstruction (fin))

Comme tout ministre du budget, vous tentez de concilier les intrts de ltat (reconstruire au cotminimum) et des acteurs conomiques (ici, cots de transport minimum).

Quelle solution adopteriez-vous et pourquoi ?Quel sera le surcot par rapport ce que vous avez calcul la premire question ?Correction page 52

Exercice 1.7.6 (Prparation des secours)

FIG. 1.5 Les infrastructures de transports

Un pays tropical doit faire face avec ses propres et maigres moyens un cyclone en approche. Lesprvisions indiquent que le cyclone arrivera sur le sud dune le du pays et quil risque de dvaster la rgiondont la ville principale, Farniente est hautement touristique. Le gouvernement a fait vacuer la zone etdcide de prparer des quipes de secours pour rparer au plus vite les infrastructures aprs le passage du


cyclone. Il veut pouvoir disposer dun maximum de personnel qualifi dans une ville hors du chemin ducyclone, mais proximit : Estival. Actuellement ce personnel est cantonn dans la capitale : Aunor.

Le gouvernement dispose de quelques jours pour transporter le plus de personnes possible depuis lacapitale jusqu Estival. Pour cela il dispose de plusieurs moyens de transport (voir figure 1.5) :

Par bateau : Le voyage se fait en trois tapes. Depuis Aunor jusqu Bordelot la capacit de transportsera au total de 1000 personnes. Depuis Bordelot jusqu Danlo la capacit de transport sera autotal de 1000 personnes. Et depuis Danlo jusqu Estival la capacit totale de transport sera de 700personnes.

Par avion : Le voyage se fait en deux tapes. Depuis Aunor jusqu Danlo la capacit de transportsera de 1000 personnes. Et depuis Danlo jusqu Estival la capacit totale de transport sera de 700personnes.

Par route : Une fois arrive Bordelot, une route mne en deux tapes Estival en passant parCampagne. Entre Bordelot et Campagne la capacit totale sera de 1000 personnes. Entre Campagneet Estival la capacit totale sera de 700 personnes.

Toutes ces capacits de transports prennent en compte la totalit des gens que lon peut transporter surles quelques jours de prparation. Elle concernent des horaires qui permettent des correspondances pouracheminer les personnes jusqu Estival.

Combien de personnes au maximum sera-t-il possible dacheminer depuis Aunor jusqu Estival ?Pour chaque tape en bateau, le cot de transport dune personne est de 1 galet (lunit montaire du

pays). Pour chaque tape en avion le cot montaire de transport dune personne est de 6 galets. Pour chaquetape de route le cot montaire de transport dune personne est de 2 galets. Le gouvernement dispose dunbudget de 5400 galets pour le transport des personnes.

Combien pourra-t-il en transporter ?Correction page 53

Exercice 1.7.7 (Lor bleu (premier problme du contrle de septembre 2008))

Une socit exploite une source deau de montagne. Pour cela elle possde deux usines. La premireest construite directement la source et a une capacit dembouteillage de 6 millions de litres par mois. Laseconde est construite dans la valle. Elle est alimente par une conduite deau depuis la source et a unecapacit dembouteillage de 4 millions de litres par mois.

Un gros client lui achte toute sa production qui doit tre livre jour aprs jour dans ses entrepts. Pourcela la socit qui exploite les eaux utilisent plusieurs moyens : soit la route de bout en bout, soit la routepuis le train. La mme gare est utilise par les 2 usines.

Sa capacit de transport par route de la premire usine jusquaux entrepts est de 6 millions de litrespar mois.

Sa capacit de transport par la route de la seconde usine jusquaux entrepts est de 2 millions de litrepar mois.

Sa capacit de transport par la route de la premire usine jusqu la gare est de 4 millions de litre parmois.

Sa capacit de transport par la route de la seconde usine jusqu la gare est de 4 millions de litre parmois.

Sa capacit de transport par train depuis la gare jusquaux entrepts est de 4 millions de litre par mois.Combien de litres par mois cette socit est-elle en mesure de fournir son client ? Le cot dembouteillage dans chaque usine est de 2 centimes par litre. Le cot de transport par la route de la premire usine aux entrepts est de 10 centimes par litre. Le cot de transport par la route de la seconde usine aux entrepts est de 6 centimes par litre. Le cot de transport par la route de la premire usine la gare est de 4 centimes par litre. Le cot de transport par la route de la seconde usine la gare est de 2 centimes par litre. Le cot de transport par train de la gare aux entrepts est de 2 centimes par litre.Quel est le cot minimal pour produire et acheminer la livraison calcule dans la question prcdente ?Correction page 57


Exercice 1.7.8 (Un zeste de citron (second problme du contrle de septembre 2008))

Une socit exploite une source deau de montagne. Pour cela elle possde deux usines. La premireest construite directement la source et a une capacit dembouteillage de 6 millions de litres par mois. Laseconde est construite dans la valle. Elle est alimente par une conduite deau depuis la source et a unecapacit dembouteillage de 4 millions de litres par mois.

Pour amliorer ses marges elle a transform la production de sa seconde usine en lui ajoutant un petitgot dagrume. Ainsi elle dgage une marge (transports inclus) de 10 centimes par litre pour la premireusine, et de 15 centimes par litre pour la seconde usine.

Un gros client lui achte toute sa production qui doit tre livre jour aprs jour dans ses entrepts. Pourcela la socit qui exploite les eaux utilisent plusieurs moyens : soit la route de bout en bout, soit la routepuis le train. La mme gare est utilise par les 2 usines.

Sa capacit de transport par route de la premire usine jusquaux entrepts est de 4 millions de litrespar mois.

Sa capacit de transport par route de la seconde usine jusquaux entrepts est de 2 millions de litrespar mois.

Sa capacit de transport par train depuis la gare jusquaux entrepts est de 3 millions de litre par mois. Elle dispose de toute la capacit ncessaire pour acheminer les bouteilles des usines jusqu la gare.Cette socit aimerait dgager une marge maximale.Quel type de problme reconnaissez-vous ? Modlisez le.Quelle marge maximale cette socit des eaux peut-elle dgager chaque mois ? Comment doit-elle grer

et acheminer sa production pour y arriver ?Correction page 60.

Exercice 1.7.9 (La valeur des dchets (second problme du contrle davril 2009))

Aprs llargissement des couloirs Gorog se retrouve avec des tonnes de gravats en stock : 90 tonnes de roches friables. 30 tonnes de roches dures. 54 tonnes de roches intermdiaires.Mais tout a une valeur. Il a trouv diffrentes offres dachat pour ses gravats, mais condition quils

soient livrs dans certaines proportions. Voici les 3 types de lots quil peut vendre : Un mlange de 60% de roches friables et 40% de roches dures se vend 100 pices dor la tonne. Un mlange de 20% de roches friables, 20% de roches dures et 60% roches intermdiaires se vend

80 pices dor la tonne. Et les gravats de roches intermdiaires pures se vendent 50 pices dor la tonne.Quel gain maximal Gorog peut-il tirer de ses gravats ?Gorog utilise les gravats de roches friables pour lexploitation de sa mine. Il aimerait donc en conserver

un peu pour lui.Lui reste-t-il des gravats de roches friables aprs la vente optimale ? Existe-t-il une autre vente lui

donnant le mme gain optimal mais lui laissant davantage de gravats de roches friables ? Et si oui, commentdoit-il rpartir les lots pour garder un maximum de roches friables tout en conservant le gain maximal ?Combien de tonnes de roches friables lui reste-t-il alors ?

Correction page 62.

Exercice 1.7.10 (Choisir les bonnes voies (premier problme du contrle davril 2010))

Une entreprise possde deux usines (une Amiens, lautre Rouen) et deux magasins pour vendre sesproduits (un Paris, lautre au Havre). Les capacits de production des usines savent sadapter au besoin,par contre les capacits de transport sont limits :

Lentreprise utilise la route pour transporter la production dAmiens. Elle peut lacheminer vers Parisou le Havre, mais en tout pas plus de 120 containers par mois. De plus les difficults de transportquelle rencontre sur lautoroute A16 ne lui permettent pas dacheminer plus de 50 containers parmois entre Amiens et Paris.


Lentreprise utilise la Seine pour transporter la production de Rouen. Elle peut lacheminer vers Parisou le Havre, mais en tout pas plus de 110 containers par mois.

Ses ventes sont trs rgulires, et elle sait quelle ne peut pas vendre plus de 120 containers dans sonmagasin du Havre, et pas plus de 100 dans son magasin de Paris.

Les marges quelle obtient sur chaque container de marchandise dpend de son lieu de production, deson mode de transport et de son lieu de vente.

Un container de marchandise produit Amiens et vendu au Havre dgage une marge de 20 000 euros. Un container de marchandise produit Amiens et vendu Paris dgage une marge de 10 000 euros. Un container de marchandise produit Rouen et vendu au Havre dgage une marge de 50 000 euros. Un container de marchandise produit Rouen et vendu Paris dgage une marge de 20 000 euros.Comment lui conseillez-vous de rpartir sa production et ses ventes pour dgager une marge maximale ?Est-ce que cette solution lui permet dexploiter en totalit ses capacits de ventes de ces deux magasins ?

Sinon lesquelles sont sous-exploites ?Correction page 64.

Exercice 1.7.11 (Les vignes de labbaye (premier problme du contrle de juin 2010))

Une abbaye de Bourgogne possde 2 hectares de vignes pour sa propre consommation. Mais commeelle produit plus de vin quelle nen a besoin, elle commercialise le surplus.

Son vignoble contient deux cpages diffrents : 1 hectare de pinot noir, et 1 hectare de gamay. Cetteanne les vendanges ont permis la rcolte de 2 400 litres de pinot noir et de 6 000 litres de gamay.

Pour son usage propre, labbaye met dentre de cot 400 bouteilles (1 bouteille = 0,75 litre) de pinotnoir et 4 000 bouteilles de gamay.

Elle compte commercialiser le vin restant sous la forme de deux vins : Des bouteilles de pinot noir : ce vin est compos uniquement de pinot noir. Chaque bouteille (0,75

litre) se vendra 30 euros. Des bouteilles de passe-tout-grain : ce vin est compos dun tiers de pinot noir et deux tiers de gamay.

Chaque bouteille (0,75 litre) se vendra 12 euros.Comment cette abbaye doit repartir le vin restant pour gagner le plus dargent possible ?Cette rpartition laisse-t-elle encore du vin sans usage ? Si oui lequel ?Correction page 66.

Exercice 1.7.12 (Barcelone ou Dublin ? (second problme du contrle de juin 2010))

Une agence de voyage fidlise sa clientle en dlivrant des Herms chaque voyage achet. Ellepropose ensuite dchanger ces Herms contre des voyages. Chaque semaine elle offre ainsi une liste detrajets possibles avec leur cot en Herms.

Un client bordelais qui a accumul une belle somme dHerms compte en utiliser une partie pour sepayer un voyage. Deux destinations le tente : soit Dublin, soit Barcelone. Il consulte les propositions devoyages de la semaine, et voici la liste des trajets quil a retenus pour aller destination en partant deBordeaux (dans chaque ville les correspondances sont ralisables) :

En avion il peut faire :Bordeaux->Madrid : pour 45 Herms.Paris->Londres : pour 25 Herms.Paris->Barcelone : pour 50 Herms.Madrid->Barcelone : pour 25 Herms.Toulouse->Barcelone : pour 15 Herms.Toulouse->Dublin : pour 30 Herms.Londres->Dublin : pour 25 Herms.Bruxelles->Dublin : pour 30 Herms.Bruxelles->Barcelone : pour 25 Herms.


En train il peut faire :Bordeaux->Paris : pour 20 Herms.Paris->Londres : pour 30 Herms.Paris->Bruxelles : pour 20 Herms.

Quelle destination doit-il choisir pour minimiser sa dpense dHerms. Combien va-t-il devoir en d-penser et en prenant quels trajets ?

Correction page 68.

Exercice 1.7.13 (Faire feu de tout bois (premier problme du contrle de septembre 2010))

Au 19me sicle un exploitant dune fort utilise la rivire qui traverse son exploitation pour acheminerson bois jusquau lieu de vente. Pour cela il construit des embarcations avec le propre bois quil coupe pourensuite charger le bois restant et descendre la rivire.

La section de fort quil exploite lui permet dobtenir deux types de bois : Un bois de bonne qualit qui servira la construction ou la tonnellerie. Cette anne, il estime

pouvoir vendre ce bois avec une marge de 15 kF la tonne. Un bois de pitre qualit qui servira de bois de chauffage. Cette anne, il estime pouvoir vendre ce

bois avec une marge de 3 kF la tonne.Son quipe douvrier sait construire deux types dembarcation : Une embarcation de qualit, faite pour durer. Pour la construire il faut utiliser 1 tonne de bois de

qualit. Elle peut charger 5 tonnes de bois. Une fois la rivire descendue, elle sera revendue avec unemarge de 30 kF.

Une embarcation de pitre qualit, faite pour ne descendre quune fois la rivire. Pour la construire ilfaut utiliser 1 tonne de bois de pitre qualit. Elle peut charger 10 tonnes de bois. Une fois la riviredescendue, elle sera revendue avec une marge 2 kF.

Cette anne la section exploite devrait permettre de couper 25 tonnes de bois de bonne qualit, et 45tonnes de bois de pitre qualit.

Sachant que lexploitant na assez douvriers que pour faire lquipage de 10 embarcations au maxi-mum, que lui conseillez-vous de construire pour acheminer son bois jusquau lieu de vente et obtenir unemarge maximale.

Est-ce que cette solution lui permet de descendre tout son bois ? Sinon quel bois reste sans usage et enquelle quantit ?

Correction page 69.

Exercice 1.7.14 (En trois dimensions (second problme du contrle de septembre 2010))

Septembre Octobre Novembrelu ma me je ve sa di lu ma me je ve sa di lu ma me je ve sa di

-80 -50 -15

1 2 3 4 5 1 2 3 1 2 3 4 5 6 7-75 -70 -45 -10

6 7 8 9 10 11 12 4 5 6 7 8 9 10 8 9 10 11 12 13 14-65 -40 -35 -5 J

13 14 15 16 17 18 19 11 12 13 14 15 16 17 15 16 17 18 19 20-60 -55 -30

20 21 22 23 24 25 26 18 19 20 21 22 23 24-25 -20

27 28 29 30 25 26 27 28 29 30 31

Un petit studio de dveloppement prvoit de sortir un jeu utilisant la 3D pour nol prochain. Ses di-rigeants veulent organiser un mini show de lancement le samedi 20 novembre. Mais lorganisation de cegenre dvnement nest pas leur spcialit, et ils lont confie une toute petite agence de publicit quiveut en profiter pour se faire un nom.


Cette agence doit trouver le lieu, organiser la rception, en faire la publicit pour y faire venir le grandpublic et les journalistes. Ils doivent proposer un planning aux dirigeants du studio de jeu, sachant que cesderniers nont donn que trois obligations :

Tout doit tre totalement prt le 19 novembre au soir. Ils veulent quune runion de lancement soit organise avec tous les gens qui vont participer lor-

ganisation pour tre srs de bien tre compris. Ils veulent quune seconde runion soit organise pour slectionner et valider les choix dorganisation

avant que la machine ne soit lance de faon irrversible.Lagence de publicit nest compose que de deux indpendants : un graphiste, et un communiquant.

Le graphiste prvoit de faire des flyers avec une image 3D grave dessus pour pouvoir faire la publicitdu show auprs du grand public. De son cot le communiquant compte utiliser son carnet dadresse pourslectionner les lieux possibles, prvenir les journalistes, et trouver le traiteur qui grera le cocktail.

Pour ce projet, ils comptent bien travailler 7 jours sur 7, et voici les diverses grandes tches quils ontidentifies :

Le projet dbutera par la runion de lancement tale sur une journe. Ensuite, le graphiste prparera diverses maquettes du flyer, tandis que le communiquant prendra des

options pour rserver diverses salles. Il contactera aussi divers traiteurs pour obtenir des propositionsde cocktail. Le graphiste prvoit 10 jours de travail pour ses maquettes, et le communiquant 16 jours.

Arrive alors la runion de validation (1 journe). Le lieu, le traiteur, et la maquette devront tre choisisce jour l.

Le graphiste prvoit alors 5 jours pour finaliser le flyer. Il le fera alors imprimer par une imprimeriespcialise dans les flyers 3D. Cette impression prendra 1 journe.

De son cot le communiquant prvoit deux tches quil sait pouvoir mener en parallle. Dun cot ilse donne 11 jours pour trouver et slectionner toutes une srie dvnements grand public o il pourraorganiser une distribution de flyers. De lautre il lui faudra une priode de 20 jours pour contacter etconvaincre journalistes et attachs de presse dassister ce show.

Une fois les flyers imprims, et les lieux de distributions slectionns, la campagne dannonce grandpublic devra durer au moins 3 semaines (21 jours).

quelle date au plus tard devra se faire la runion de lancement de ce projet ?On va supposer que le projet commencera cette date.Limprimerie qui sait graver les flyers en 3D nest pas disponible en permanence. On propose au gra-

phiste de choisir un jour entre le 11 et le 15 octobre ou entre le 25 et 29 octobre. Cela est-il possible avecles dates retenus ? Si oui quelles sont les dates possibles de rservation de cette imprimerie ?

Correction page 71.

Exercice 1.7.15 (Que semer (premier problme du contrle davril 2011))

Un agriculteur doit choisir la culture de 200 hectares de ses champs pour lanne qui arrive. Il peut yfaire pousser du mas et du colza. La mas rapporte plus que le colza (il prvoit un gain de 600 euros lhectare pour le mas contre 500 euros lhectare pour le colza). Mais il sest engag respecter diversescontraintes environnementales :

Il doit limiter ses apports de phosphates. Concrtement cela signifie quil ne pourra pas utiliser plusde 30 tonnes dengrais en tout et pour tout.

Il doit limiter sa consommation deau. Il ne devra pas puiser plus de 200 000m3 deau pour larrosagede ses cultures.

Pour une anne normale : il doit puiser 2 000m3 deau et utiliser 100 kg dengrais par hectare de mas. il doit puiser 1 000m3 deau et utiliser 250 kg dengrais par hectare de colza.Comment doit-il rpartir ses cultures pour esprer un gain maximal ? Quel est ce gain ?Est-ce que cette solution lui demande dutiliser les 200 hectares de terre sa disposition2 ?Correction page 72.

2Pour cette question on vous demande dinterprter les rsultats donns par la technique utilise, et non pas de refaire des calculspour obtenir ce rsultat


Exercice 1.7.16 (Hivernage (second problme du contrle davril 2011))

Un leveur de vaches doit prvoir la production, lachat, le transport et le stockage du fourrage pourlalimentation de son btail pour lhiver prochain.

Il estime quil pourra lui mme rcolter en juin 70 tonnes de fourrage.Par ailleurs il a obtenu bon prix lachat de fourrage auprs de deux autres producteurs. Le premier pourra lui fournir fin juin jusqu 30 tonnes de fourrage. Mais cest lleveur de les

acheminer jusqu son exploitation et de les stocker en attendant lhiver. Le second lui propose jusqu 120 tonnes de fourrage. Il pourra prendre cette livraison en deux

parties. La premire fin juin quil devra stocker lui mme durant lt et lautomne et la seconde audbut de lhiver. Cest lleveur de venir prendre livraison du fourrage.

Lleveur ne peut stoker durant lt et lautomne que 130 tonnes de fourrage. Au dbut de lhiver, ilrcupre un silo supplmentaire qui lui permet de monter jusqu un total de 250 tonnes de stockage. Finjuin, il aura les moyens de transporter depuis les vendeurs jusqu son exploitation 50 tonnes de fourrage.Au dbut de lhiver il pourra en transporter 80 tonnes.

Sachant quune vache consomme environ 2 tonnes de fourrage durant lhiver, combien de vaches aumaximum sera-t-il en mesure de nourrir durant lhiver prochain ? Comment devra-t-il procder pour cela ?

Correction page 73.

Exercice 1.7.17 (Course contre la montre (premier problme du contrle de septembre 2011))

FIG. 1.6 Bassin mditerranen

Il ne reste que 65 jours un marchand phnicien pour honorer une commande de mtaux prcieux. Ilvient enfin de trouver ce quil cherchait dans larrire pays de Siga. Mais la livraison doit tre faite Tyr. Ilfaut donc acheminer cette cargaison le plus rapidement possible. Pour cela diverses routes soffrent lui. Ilpeut dj acheminer sa cargaison jusqu la cte grce trois routes diffrentes :

Une caravane peut acheminer cette cargaison jusqu Siga en 2 jours. Une caravane peut acheminer cette cargaison jusqu Tipasa en 10 jours. Une caravane peut acheminer cette cargaison jusqu Carthage en 35 jours.Une fois arrive dans ces ports diverses options sont possibles : Une fois Siga il peut soit utiliser un de ses bateaux qui pourrait naviguer vers Tyr, soit louer un

bateau pourrait caboter jusqu Tipasa. Son propre bateau est actuellement en rparation. Il estimeque les rparations plus le voyage ajouteraient 60 jours de voyage sa cargaison. Sil choisit lecabotage, sa cargaison pourra tre en 6 jours Tipasa.

Une fois Tipasa, une seule possibilit lui est offerte. Il peut louer un bateau pour caboter jusquCarthage. Cela lui prendra 10 jours.

Carthage il dispose dun de ses bateaux qui peut naviguer vers Tyr. En cette saison, il estimepouvoir faire ce voyage en 35 jours.

En faisant confiance dans ces diverses estimations, quelle route doit choisir le marchand pour arriver auplus vite Tyr ? Les voyages maritimes tant assez alatoires, de combien de jours de marge ce marchand


dispose-t-il pour honorer sa commande dans les temps ?Correction page 75.

Exercice 1.7.18 (Dmarches administrative (second problme du CF2 2012))

Un tudiant en recherche dun travail dt veut dposer un dossier auprs dune entreprise qui utilisedes procds un peu administratifs. Arriv laccueil, on lui explique les dmarches quil doit faire pourdposer son dossier.

La premire tape consiste la vrification des pices justificatives de ses comptences. La seconde tape consiste en un entretien (qui se termine par la remise du dossier rempli). La troisime et dernire tape consiste juste dposer le dossier rempli laccueil.

La socit est repartie sur trois sites :Allegri : Cest le site o se trouve ltudiant. Il contient tous les services : laccueil, un centre de vrifica-

tions et un centre dentretiens.Bach : Ce site ne propose quun seul service : la vrification des pices.Chopin : Deux services sont offerts sur ce site : la vrification des pices, et les entretiens.

Mais suivant le site le temps moyen dattente et de traitement pour chacune des tapes diffrent : Pour la vrification il faut compter 2 h sur la site Allegri, 30 min sur le site Bach, et 1h30 sur le site

Chopin. Pour lentretien il faut compter 1h sur le site Allegri, et 1h sur le site Chopin. Le dpt de dossier se fait sans temps dattente ni de traitement.

Il existe des navettes gratuites reliant les diffrents sites. Lune fait le tour des sites dans le sens Allegri,Bach, Chopin, et retour Allegri. La seconde fait des aller-retour entre Allegri et Chopin. Ainsi les tempsmoyens de trajet (attente comprise) sont :dAllegri vers Bach : 20 minutes.de Bach vers Chopin : 20 minutes.de Chopin vers Allegri : 20 minutes.dAllegri vers Chopin : 30 minutes.

Quel circuit administratif conseillez-vous cet tudiant pour esprer minimiser son temps de dmarche.Correction page 76.


Chapitre 2

Corrections

2.1 Ordonnancement

2.1.1 Correction de lexercice 1.1.1 de la page 5

Suite ces explications trs claires de votre collgue, la premire tape va tre didentifier toutes lestches et leurs dpendances.

Commenons par laspect logistique, qui ne dpend pas de laspect scientifique :

Tche A : Choix du comit dorganisation. Sans lui, aucune tche logistique ne peut se faire. Dure : 1semaine.

Tche B : Choix de lhtel. Il est fait par le comit dorganisation : aprs A. Dure : 3 semaines.Tche C : Choix des menus et prix des repas. Il faut avoir choisi lhtel : aprs C : Dure : 1 semaine.Tche D : Choix du lieux du banquet. Il est fait par le comit dorganisation : aprs A. Dure : 2 semaines.Tche E : Dtermination du prix pay par les confrenciers. Cela dpend du banquet et des menus : aprs

C et D. Dure : 1 semaine.

Traitons maintenant laspect scientifique :

Tche F : Choix du comit de programme. De lui dpend tout laspect scientifique. Dure : 3 semaines.Tche G : Premire runion. Il faut que le comit scientifique et lhtel soient choisis : aprs B et F. Dure :

0 semaine.Tche H : Appel et attente des communications : Cette tche arrive aprs la premire runion et la dter-

mination du prix : aprs G et E. Dure : 8 semaines.Tche I : Slection des articles. Elle arrive aprs les rponses lappel : aprs H. Dure 8 semaines.Tche J : Second runion. Elle suit la slection des articles et arrive aprs le choix du lieux de banquet :

aprs I et D. Elle doit arriver au moins 3 semaines avant le colloque : dure 3 semaines.Tche K : Mise en forme des articles slectionns. Elle arrive aprs la slection des articles : aprs I. Dure

4 semaines.Tche L : Impression des Proceedings. Elle arrive aprs la mise en forme des articles : aprs K. Dure

6 semaines.Tche M : Rception des livres. Elle suit limpression : aprs la tche L. Il faut les recevoir au moins 1

semaine avant le colloque : dure 1 semaine.Tche : Le dbut du colloque. Il faut que tous les aspects logistiques soit rgls que le programme final

soit fix (deuxime runion), et que les livres soient reus : aprs E, J et M.

Aprs avoir ajout une tche fictive de dure nulle place avant les tches sans dpendances, on obtientle graphe de la figure 2.1

On peut simplifier un peu ce graphe. Lorsquon a un chemin X Y Z, avec Y seul successeur deX, et Z seul successeur de Y, on peut supprimer Y, et remplacer le chemin par X Z. La dure du nouvel


FIG. 2.1 Le graphe des tches

arc reoit la somme des dures des deux anciens. la fin pour retrouver la date au plus tt et la date auplus tard de Y, il suffira dajouter la dure de la tache X aux dates de X (et donc la marge totale de Y seraexactement la mme que celle de X ).

Donc une fois simplifi on obtient le graphe de la figure 2.2 :

FIG. 2.2 Le graphe simplifi des tches

Maintenant, il suffit de mettre en uvre le potentiel-tches pour avoir la rponse toutes les questions.Cela donne le graphe de la figure 2.3

FIG. 2.3 Le rsultat du potentiel-tches

La dure minimale du projet est donc de 33 semaines. Vous devez tout prix commencer 33 semainesavant le 17 dcembre cest dire avant le 30 avril.

Vous avez une marge de 2 semaines sur la date de la premire runion (tche G) et 8 semaines sur ladate de la seconde (tche J).



Apollodore et Aristodme se demandent comment organiser leurs tches pour tre le plus efficace pos-sible. Il sagit donc videmment dun problme dordonnancement. La question porte juste sur le choixentre deux scnarios possibles. Il suffit donc de calculer le temps pris par les deux scnarios et de choisirle plus rapide. Il nest mme pas utile de trouver les tches critiques, donc un simple diagramme de Ganttsuffira. Bien sr un potentiel-tches rpond tout aussi bien la question. Pour cette correction nous allonsfaire un diagramme de Gantt.

La premire tape consiste trouver les dpendances des tches.Pour le premier scnario, Apollodore doit commencer par prparer la pte bris avant de faire la tarte

elle mme. Aristodme talera cette pte aprs la prparation de crme anglaise.On obtient donc les dpendances suivantes :

Nom de la Description Dure dpendancestche (en minute)

A Prparer la pte 5B Laisser reposer la pte 30 aprs AC Prparer la crme 15D taler la pte 5 aprs B et CE Laisser refroidir la crme 15 aprs CF Mettre la crme au rfrigrateur 30 aprs EG Prparer le moule 5 aprs AH Prparer les pommes 10 aprs GI Mettre en place des pommes 10 aprs HJ Caramliser les pommes 5 aprs IK Placer la pte 5 aprs D et JL Cuisson 15 aprs K

Traduit sous la forme dun diagramme de GANTT, on obtient :

Tches 05 10 15 20 25 30 35 40 45 50 55 60 65

A

B

C

D

E

F

G

H

I

J

K

L

Donc avec ce scnario, en 60 minutes tout est prt.


Regardons maintenant le second scnario : seule la tache A change dacteur. Donc Apollodore peutcommencer la tche G immdiatement, par contre Aristodme doit reporter le dbut de la tche C aprs lafin de la tache A.

On obtient les dpendances suivantes :

Nom de la Description Dure dpendancestche (en minute)

A Prparer la pte 5B Laisser reposer la pte 30 aprs AC Prparer la crme 15 aprs AD taler la pte 5 aprs B et CE Laisser refroidir la crme 15 aprs CF Mettre la crme au rfrigrateur 30 aprs EG Prparer le moule 5H Prparer les pommes 10 aprs GI Mettre en place des pommes 10 aprs HJ Caramliser les pommes 5 aprs IK Placer la pte 5 aprs D et JL Cuisson 15 aprs K

Traduit sous la forme dun diagramme de GANTT, on obtient :

Tches 05 10 15 20 25 30 35 40 45 50 55 60 65

A

B

C

D

E

F

G

H

I

J

K

L

Donc avec ce second scnario il faut 65 minutes pour que tout soit prt.Apollodore et Aristodme devraient suivre la premier scnario pour terminer leur prparation le plus

vite possible.


Un examen rapide des emplois du temps innocente Frre Thomas qui na pas eu une minute de librede la matine. Par contre aussi bien Frre Daniel que Frre Yves ont profit de 30 minutes de temps libre.


A priori plus que ncessaire pour commettre le mfait. Mais pour cela il faut quils aient eu au moins20 minutes daffile. Le seul moyen de vrifier cela consiste calculer leurs marges sur chacune de leurstches. Il sagit donc dun problme dordonnancement avec lusage dun potentiel-tches.

La premire tape de la modlisation consiste identifier toutes les tches, leur chronologie, et leurdure. Les trois frres participent 6 tches durant la matine :

Jardin : La matine de Frre Daniel et de Frre Yves commence par la rcolte au jardin des lgumes etplantes mdicinales. Cette tche dure 2h.

Courses : La matine de Frre Thomas commence par des courses. Cette tche dure 2h15.Cuisine : Frre Daniel et Frre Thomas continuent leur journe en cuisine. Cette tche dure 1h15. Elle ar-

rive donc aprs celles du Jardin (Daniel doit avoir termin sa premier tche) et des Courses (Thomasdoit avoir termin sa premire tche).

Lproserie : Frre Yves continue sa matine en allant la lproserie. Cela lui prend 1h. Cette tche arrivedonc aprs celle du Jardin (Yves doit avoir termin sa premire tche).

Infirmerie : Frre Yves et Frre Thomas terminent leur matine linfirmerie. Ils y passent 2h. Cette tchearrive donc aprs celles de la Cuisine (Thomas doit avoir termin sa deuxime tche) et celle de laLproserie (Yves doit avoir termin sa deuxime tche).

Atelier : Frre Daniel termine sa matine latelier pour faire ses dcoctions. Il y passe 1h45. Cette tchearrive donc aprs celle de la Cuisine (Daniel doit avoir termin sa deuxime tche).

On applique ensuite un potentiel-tches ce problme :

FIG. 2.4 Potentiel-tches

La seule tche qui permet de dgager plus de 20 minutes de temps daffile est celle de la lproserie.Elle permet en effet de dgager 30 minutes de marge. Seul Frre Yves est affect cette tche. Cest donclui lauteur du vol du vin de messe.

2.2 Arbre


Aucun doute possible pour cette exercice, il sagit de trouver un arbre de recouvrement minimal. Deplus le graphe est presque dj dessin par le plan de la commune. Il faut juste penser considrer touspoints dj relis par une route en bon tat comme tant un seul et mme sommet du graphe.

Donc le rseau du Centre-Bourg forme un seul sommet. Il est reli aux Fays par ch1, la Bergerie parch3, la Dauberie par ch9, la Croise par ch8 et enfin aux Haies par ch11.

De plus les Iris et la Croise ne forme quun seul et mme sommet. Pour la suite de ce problme, on neparlera plus que du sommet la Croise reli aux Haies par ch13 et aux Joncs par ch15.

En nommant CB le sommet du Centre-Bourg et les habitations par leur initiale, on obtient la matricedadjacence suivante (les distances sont exprimes en hectomtre) :


CB A B C D E F G H JCBAB ch3=14 ch5=14C ch8=15 ch7=13 ch6=16D ch9=14EF ch1=5 ch4=8 ch2=12G ch10=5H ch11=14 ch13=13 ch14=15 ch12=16J ch15=17 ch16=13

Le mme graphe dessin donne la figure 2.5.

CBF

B

C

D

H

A

G

J E

ch3=14

ch8=15

ch9=14ch1=5

ch11=14

ch5=14

ch7=13

ch4=8

ch6=16

ch2=12

ch13=13

ch15=17

ch10=5

ch14=15

ch16=13

ch12=16

FIG. 2.5 Le rseau de chemin de la commune

On va par exemple utiliser lalgorithme de Prim en utilisant les matrices. La premier sommet (qui peuttre choisi au hasard) plac va tre CB.

CB A B C D E F G H JCBAB ch3=14C ch8=15D ch9=14EF ch1=5

OUIGH ch11=14J

La plus petite arte partant de CB est celle allant vers F. On ajoute donc F notre ensemble desommets traits. On calcule le nouveau cocycle (on ajoute la ligne et la colonne de F mais en supprimantles artes relies aux lments dj dans lensemble).

CB A B C D E F G H JCBAB ch3=14C ch8=15D ch9=14EF XXXch1=5 ch4=8 ch2=12

OUI OUIGH ch11=14J


Dans le nouveau cocycle, la plus petite arte est celle allant de F A. On ajoute A lensembledes sommets traits, et on calcule le nouveau cocycle.

CB A B C D E F G H JCBAB ch3=14 ch5=14C ch8=15 ch7=13D ch9=14EF XXXch1=5 XXXch4=8 ch2=12

OUI OUI OUIGH ch11=14J

Cest maintenant au tour de larte allant de F B. On ajoute le sommet B lensemble :

CB A B C D E F G H JCBAB XXXXch3=14 XXXXch5=14C ch8=15 ch7=13 ch6=16

OUID ch9=14EF XXXch1=5 XXXch4=8 XXXXch2=12

OUI OUI OUIGH ch11=14J

cette tape cest larte allant de A vers C qui est prise. Et quelques itrations plus tard on obtientau final :

CB A B C D E F G H JCBAB XXXXch3=14 XXXXch5=14C XXXXch8=15 XXXXch7=13 XXXXch6=16

OUID XXXXch9=14

OUIEF XXXch1=5 XXXch4=8 XXXXch2=12

OUI OUI OUIG XXXXch10=5

OUIH ((((hhhhch11=14 ((((hhhhch13=13 ((((hhhhch14=15 ((((hhhhch12=16

OUI OUIJ ((((hhhhch15=17 ((((hhhhch16=13

OUI

Les 9 chemins transformer en route sont donc : ch1, ch2, ch4, ch7, ch9, ch10, ch13, ch14, ch16.La longueur totale payer sera donc : 5+12+8+13+14+5+13+15+13=98 hm.Et le nouveau plan de la commune est visible sur la figure 2.6.


ch1

Centre Bourg

Bergerie

Fays

Aqueduc

Croise

DauberieGrignon

Joncs

Haies

Iris

Epis dor

ch2

ch4ch5

ch6

ch8

ch3

ch9

ch10

ch12

ch11

ch13ch14

ch15

ch16

Lgende: : Chemin : Route

ch7

FIG. 2.6 Nouveau plan de la commune


Pour rsoudre le problme de Gorog il faut crer un rseau de couloirs et descaliers largis qui atteignetoutes les salles. Et comme ce travail doit tre fait au plus vite, il faut trouver la solution qui prend le moinsde temps. Il sagit donc dun problme darbre de recouvrement minimal avec des poids exprimant le tempsde travail.

La premire tape consiste calculer le temps de travail pour chaque couloir et escalier pour ensuite lesreporter sur le graphe qui va modliser notre rseau.

Niveau Couloir dentre : 7h, Couloir 1 : 50hsuprieur (1) Couloir 2 : 46h, Couloir 3 : 35hEscaliers (2) Escalier 1 : 110h, Escalier 2 : 120hNiveau Couloir 4 : 155h, Couloir 5 : 90hinfrieur (3 Couloir 6 : 135h

On obtient le graphe de la figure 2.7.Pour trouver larbre de recouvrement minimal on peut utiliser lalgorithme de Kruskal ou celui de Prim.

Dans cette correction on va utiliser Kruskal.La premire tape consiste trier les artes par ordre croissant de poids : CE=7, C3=35, C2=48, C1=50,

C5=90, E1=110, E2=120, C6=135, C4=155.Le graphe compte 7 sommets, on va donc ajouter les artes une une sans crer de cycle jusqu obtenir

un ensemble de 6 artes.1. On ajoute le couloir CE lensemble. T1 = {CE}.2. On peut ajouter C3 sans former de cycle. T2 = {CE, C3}.3. On peut ajouter C2 sans former de cycle. T3 = {CE, C3, C2}.4. On ne peut ajouter C1 qui formerait un cycle. Mais on peut ajouter C5. T4 = {CE, C3, C2, C5}.5. On peut ajouter E1 sans former de cycle. T5 = {CE, C3, C2, C5, E1}.6. On peut ajouter E2 sans former de cycle. T6 = {CE, C3, C2, C5, E1, E2}.


FIG. 2.7 Modlisation de la grotte

Lensemble contient 6 artes, lalgorithme est termin. Le poids de cet arbre vaut : 7 + 35 + 46 + 90 + 110+ 120 = 408.

Donc il faut au minimum 408 heures de travail pour dgager un accs largi toutes les salles. Pourcela il faut largir le couloir dentre, les couloirs 2, 3 et 5 ainsi que les 2 escaliers (voir figure 2.8).

FIG. 2.8 Plan de la grotte aprs largissement des couloirs

Comme chaque nain peut fournir 8h de travail par jour, pour faire ce travail en une seule journe Gorogdoit embaucher 51 nains.

2.3 Plus court chemin


Pour ce problme il faut rechercher un plus court chemin au sens du temps entre Lyon et Agen.Il faut commencer par trouver le graphe qui va servir rsoudre le problme. Il nest pas utile de

conserver les noeuds intermdiaires qui ne concernent que les changements de noms des routes (commeFeurs, Orange, . . . ). Seuls les noeuds aux intersections des routes sont intressants pour notre modle.

Il faut aussi calculer le temps de parcours entre chacun des ces noeuds : Entre Lyon et Clermont-Ferrand : il y a 77km de nationales et 88 km dautoroutes. (77/70+88/110)60 = 114 minutes de trajet.

Entre Lyon et Montpellier : il y a 308km dautoroutes. (308/110) 60 = 168 minutes de trajet. Entre Lyon et Brioude : il y a 182km de nationales. (182/70) 60 = 156 minutes de trajets.


Entre Montpellier et Brioude : il y a 275km dautoroutes. (275/110) 60 = 150 minutes de trajet. Entre Brioude et Clermont-Ferrand : il y a 66km dautoroutes. (66/110)60 = 36 minutes de trajet. Entre Clermont-Ferrand et Cahors : il y a 275km dautoroutes. (275/110) 60 = 150 minutes de

trajet. Entre Brioude et Cahors : il y a 238km de nationales. (238/70) 60 = 204 minutes de trajet. Entre Montpellier et Montauband : il y a 275km dautoroutes. (275/110) 60 = 150 minutes de

trajet. Entre Cahors et Montauband : il y a 88km dautoroutes. (88/110) 60 = 48 minutes de trajet. Entre Cahors et Agen : il y a 105km de nationales. (105/70) 60 = 90 minutes de trajet. Entre Montauband et Agen : il y a 66km dautoroutes. (66/110) 60 = 36 minutes de trajets.On na pas daprioris sur le sens de parcours de laxe transversal entre Montpellier et Clermont-Ferrand.

Il faudra donc mettre les arcs dans les deux sens pour ces routes.On obtient le graphe de la figure 2.9.

Lyon

Clermont

Brioud

e

Montpellier

Cahors

Montauband

Agen

114

168

182

15

0

15

03

6

36

150

204

150

48

90

36

FIG. 2.9 Graphe modlisant les temps de trajet

Il nous reste trouver le chemin le plus court (au sens du temps). On utilise lalgorithme de Ford-Moore.

m (Ly) (Cl) (Br) (Ml) (Ca) (Mb) (Ag) changs +0 0 HH HH HH HH HH HH Ly Cl, Br, Ml1 114/Ly XXXX182/Ly 168/Ly Cl Ca, Br

Br Cl, Ca, MlMl Br, Mb

2 XXX218/Br 150/Cl XXX332/Br 264/Cl XXXX318/Ml Br Cl, Ca, Ml

XXXX318/Ml XXX386/Br Ca Mb, AgMb Ag

3 XXX186/Br XXX300/Br XXX354/Br 312/Ca XXXX354/Ca Mb Ag

XXXX354/Mt Ag4 348/Mb Ag

Le voyageur prendra donc 5h48 (348 minutes) pour faire le trajet. Il passera par les sommets Lyon,Clermont, Cahors et Montauband.

Donc son plan de route consiste commencer son voyage sur des nationales et des dpartementalesjusqu Feurs. L, il passe sur le rseau autoroutier en rejoignant Clermont-Ferrand par lA72. Il empruntealors lA71 jusqu Combronde o il passe sur lA89 jusqu Brive la Gaillarde. Il change alors en passantsur lA20 jusqu Montauband, o il rejoint lA62 qui le mnera jusqu Agen.



Nous allons modliser ce problme avec une recherche de plus court chemin.La recherche du plus court chemin sert trouver un optimum reposant sur un graphe orient. Loptimum

en question est un minimum. Que peut-on chercher minimiser pour optimiser notre problme ? On a descots et des gains. . . Les deux tant en fait un peu la mme chose : un gain est un cot ngatif, et un cot estun gain ngatif. Pour optimiser notre problme on doit soit maximiser les gains, soit minimiser les cots.La technique de la rechercher du plus court chemin est parfaite pour le recherche dun minimum. On vadonc chercher minimiser les cots (en transformant les gains en cots ngatifs). La semaine de travail serarentable que si le minimum obtenu est un nombre ngatif. Sinon cela signifiera quelle cotera de largent.

Comment modliser la semaine de travail dApollodore sur un graphe faisant apparatre les cots ? Onva construire un graphe o chaque tat reprsentera ltat du stock des repas dApollodore la fin de chaquejourne. Il dmarre avec un stock vide, et doit finir le vendredi avec un stock vide. Sa production est de 50repas, et un banquet en utilise 100. Le stock maximal est de 100 repas. Donc la fin de chaque journe il ya trois tats possibles pour ce stock : 0 repas, 50 repas ou 100 repas. Notre graphe devra donc passer par lestats de la figure 2.10

FIG. 2.10 Tous les tats possibles du stock dApollodore

Il faut maintenant placer les arcs entre ces tats. Le lundi Apollodore peut ne rien faire (le stock reste 0) ou produire 50 repas (le stock passe 50 -tat Lun 50-). Sil produit 50 repas, cela va lui coter 2keuros. On va donc valuer cet arc avec la valeur 2 (notre unit sera le kilo euros). Ltat Lun 100 ne peut pastre atteint, il faudra le retirer du graphe. Le mardi le stock dApollodore ne lui permet pas de rpondre la demande du premier banquet. Il na donc que 2 choix possibles : ne rien faire (son stock ne bouge pas),ou produire 50 repas pour 2k euros (son stock monte de 50). Le mercredi il na pas accs aux cuisines pourproduire. Il na deux que deux choix : ne rien faire, ou servir les 100 repas du banquets de mercredi (si sonstock le lui permet). Ce banquet lui rapporte 3k euros (il faut penser retirer le 1k euros que lui cote leservice de chaque banquet). Comme ici on modlise avec des cots, ce gain va tre report comme un cotngatif. Larc va tre valu avec la valeur -3. On continue ainsi jusqu la fin de la semaine et on arrive lafigure 2.11

FIG. 2.11 Ajouts des arcs suivants les actions dApollodore

Sur le graphe de la figure 2.11, ltat Jeu 50 se trouve en dehors de tout chemin menant au seul tat


final acceptable (stock vide vendredi soir). Il faut donc le retirer de notre modlisation. On obtient le graphede la figure 2.12.

FIG. 2.12 Graphe nettoy des tats impossibles

On peut encore maintenant simplifier ce graphe avant de faire tourner lalgorithme de Ford-Moore : onsupprime les tats sur lesquels il ny quun seul arc entrant et un seul arc sortant. On remplace les 2 arcs parun nouvel arc valu par la somme des deux valeurs. On obtient le graphe de la figure 2.13.

FIG. 2.13 Graphe simplifi avant algorithme

On applique lalgorithme de Ford-Moore sur ce graphe :

m (D) (L0) (L50) (Ma50) (Ma100) (Me0) (J100) (V 0) Sommets +changs

0 0 ZZ ZZ ZZ ZZ ZZ ZZ ZZ D L0, L501 0/D 2/D L0 Me0, Ma50

L50 Ma50, Ma1002 2/L0 0/L0 Ma50 J100

2/L50 4/L50 Ma100 J100, Me0Me0 V0

3 3/Ma50 J100 V0(((

(hhhh1/Ma100 ((((hhhh4/Ma1000/Me0 V0

4 0/J100

Le plus court chemin vers Ven0 a pour valeur 0. Donc le cot minimal pour une semaine de travaildApollodore est de 0. Autrement dit, son gain (la valeur oppos du cot pour ce modle) est de 0. Il vautmieux conseiller Apollodore de ne pas travailler dans ces conditions.


Pour la seconde partie de ce problme, la modlisation est exactement la mme, sauf que la prsencedAristodme permet dajouter dautres chemins sur le graphe. En effet les jours de productions les deux


amis peuvent produire 100 repas. Et mardi, il est possible de consommer 100 repas pour le banquet et denproduire 50 par ailleurs et donc au bilan de nen consommer que 50. On obtient donc le graphe de la figure2.14

FIG. 2.14 Ajouts des arcs en tenant compte des actions dApollodore et dAristodme

Sur le graphe de la figure 2.14, ltat Jeu 50 se trouve en dehors de tout chemin menant au seul tatfinal acceptable (stock vide vendredi soir). Il faut donc le retirer de notre modlisation. On obtient le graphede la figure 2.15.

FIG. 2.15 Graphe nettoy des tats impossibles

On peut encore maintenant simplifier ce graphe avant de faire tourner lalgorithme de Ford-Moore : onsupprime les tats sur lesquels il ny quun seul arc entrant et un seul arc sortant. On remplace les 2 arcs parun nouvel arc valu par la somme des deux valeurs. On obtient le graphe de la figure 2.16.

FIG. 2.16 Graphe simplifi avant algorithme


On applique alors lalogorithme de Ford-Moore :

m (D) (L0) (L50) (L100) (Ma0) (Ma50) (Ma100) (Me0) (J100) (V 0) Sommets +changs

0 0 ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ ZZ D L0, L50, L1001 0/D 2/D 4/D L0 Ma0, Ma50, Ma100

L50 Ma50, Ma100L100 Ma0, Ma50, Ma100

2 XX0/L0 XX2/L0 4/L0 Ma0 Me0XXX2/L50 4/L50 Ma50 J100

-2/L100 0/L100 4/L100 M100 Me0, J1003 -2/Ma0 Me0 J100, V0

XXX1/Ma50 J100 V0

((((hhhh1/Ma100 ((((hhhh4/Ma100

4 0/Me0 XXX-2/Me0 J100 V0XXX-2/J100 V0

5 -3/J100 V0

36E

ricL

AL

LE

T,Jean

-Luc

RA

FFY

Pour ce graphe le plus court chemin fait -3 : il passe par Dbut, Lun100, Mar0, Mer0, Jeu100 et Ven 0.Cela signifie quApollodore et Aristodme peuvent travailler ensemble cette semaine pour un cot de

-3k euros, autrement dit un gain de 3k euros. Ils ont donc intrt le faire.Interprtons le chemin pour leur donner le bon scnario :

Dbut Lun 100 Ils doivent monter leur stock 100 ds le premier jour. Ils doivent donc travailler encuisine tous les deux le lundi.

Lun 100Mar 0 Ils doivent consommer les 100 repas (en servant le banquet du mardi), sans en produiredautres. Donc un seul des deux doit travailler le mardi au service du banquet du mardi, lautre peutse reposer.

Mar 0Mer 0 Leur stock ne bouge pas ce jour l. Le mercredi est un jour de repos pour les deux amis.Mer 0 Jeu 100 Ils doivent remonter leur stock 100 le jeudi. Ils doivent donc travailler en cuisine tous

les deux.Jeu 100 Ven 0 Ils doivent consommer les 100 repas (en servant le banquet du vendredi), sans en pro-

duire dautres. Donc un seul des deux doit travailler le vendredi au service du banquet du vendredi,lautre peut se reposer.

2.4 Flot maximal


Il sagit dun problme de flot maximal.La premire tape consiste dessiner le graphe des cursus possibles pour les lves. Ils vont devoir

passer par lacquisition des trois UV . Comme la seconde cole a des accords dquivalence avec les deuxautres, il peut y avoir des changes entre cette cole et les autres chaque tape de la formation. Maisencore faut-il que les dates le permettent. Comme la premire cole commence plus tt, les seuls transfertspossibles avec elle vont de la premire vers la seconde. Et comme la troisime cole termine toujours sesUV aprs le dbut de la seconde, les transferts possibles entre elles vont de la deuxime vers la troisime.

On arrive au graphe de la figure 2.17. Sur cette figure D signale les dbuts de formation, F les fins.Le premier nombre qui suit dsigne lcole, et aprs le point le second nombre dsigne lUV . Donc parexemple D2.3 dsigne le dbut de la formation pour lUV3 dans lcole 2.

FIG. 2.17 Graphe modlisant le cursus des lves

Ce premier modle peut tre simplifi. Il est possible de supprimer les noeuds qui nont quune seulearte entrante et une seule arte sortante. On remplace alors ces deux artes par une arte ayant la capacitminimale des deux artes.

c1 c2 min(c1, c2)

S1 S2 S3 devient S1 S3

On obtient alors le graphe de la figure 2.18.Maintenant il faut trouver le flot maximal que lon peut faire circuler sur ce graphe. Pour cela on va

commencer avec un flot reprsentant le cas o chaque lve essaye de suivre la totalit de son cursus dansune seule cole. En saturant chaque cole on arrive au flot de la figure 2.19.


FIG. 2.18 Graphe simplifi

FIG. 2.19 Premier flot. Chaque lve reste dans son cole de dpart

Ensuite on utilise lalgorithme de Ford-Fulkerson pour voir sil est possible damliorer ce flot. La figure2.20 montre le marquage dune chane qui permet de marquer le puits (on na laiss sur le graphe que lesmarquages appartenant cette chane).

FIG. 2.20 Marquage dune chane amliorante

On obtient la donc chane suivante :

40 20 = 20 0 = 30 0 = 35 20 = 15

Dbut F1.1 D2.2 F2.1 D3.2+3 Fin

On calcule les capacits restantes sur les arcs directs de cette chane et le flot passant sur les arcs inverses(il ny quun seul arc inverse pour notre cas), et on prend le minimum de ces valeurs : 15. Il est donc possibledaugmenter de 15 le flot entre Dbut et Fin. Il faut ajouter 15 aux flots des arcs directs de la chane et retirer15 larc inverse. On obtient le nouveau flot de la figure 2.21

FIG. 2.21 Nouveau flot aprs amlioration

Le flot est maintenant de 85 lves.


On tente une nouvelle itration de lalgorithme de Ford-Fulkerson. On narrive plus marquer le puits(voir figure 2.22). Donc le flot maximal est dj atteint.

FIG. 2.22 Nouveau marquage : impossible de trouver une chane amliorante

Le flot maximal est de 85.Pour obtenir la formation de 85 lves, lorganisme doit envoyer 35 lves suivre lUV1 dans la premire

cole. 20 de ces lves continueront la formation dans celle-ci, mais 15 autres iront faire les UV2 et UV3dans la deuxime cole. Il doit aussi envoyer 30 lves suivre lUV1 dans la deuxime cole. 15 continuerontdans celle-ci, mais 15 autres iront suivre le module qui regroupe les UV2 et UV3 dans la troisime cole.Enfin 20 lves feront toutes les UV dans la troisime cole.


Il sagit dun problme de type flot-maximal cot minimal. Mais attention, on sait que la capacit denotre rseau est de 85 lves. On veut nen faire passer que 63. Donc il faudra arrter lalgorithme avant leflot maximal.

Le schma modlisant notre problme est celui de la figure 2.23.

FIG. 2.23 Graphe modlisant la recherche du flot maximal cot minimal

Il est possible de simplifier ce graphe. On peut supprimer tous les noeuds nayant quune seule arteentrante et une seule arte sortant. On remplace ces deux artes par une arte ayant la capacit minimale etla somme des cots des deux artes.

cap1/cot1 cap2/cot2 min(cap1 ,cap2)/cot1+cot2S1 S2 S3 devient S1 S3

On obtient le graphe de la figure 2.24.Il faut mettre en uvre lalgorithme de Busacker et Gowen. Pour cela on dmarre avec un flot nul, et on

recherche le chemin le plus court (au sens du cot) allant de la source au puits. Il sagit du chemin1 passantpas les UV de lcole 2 . Le cot de ce chemin est de 24k euros. Sa capacit maximale est de 30 lves.On peut donc dj placer un premier flot de 30 lves sur le graphe (voir figure 2.25) dont le cot globalest 24k 30 = 720k euros. On peut aussi calculer le nouveau graphe associ pour ltape suivante (figure2.25).

Sur le nouveau graphe associ, le plus court chemin passe par Dbut F1.1D2.2 F2.1D3.2+3 Fin. Son cot est de 30k euros. Sa capacit est de 30 lves (concrtement cette tape de lalgorithme,

1Pour allger la correction de cet exercice, les calculs de recherche des chemins les plus courts ne seront pas reports ici


FIG. 2.24 Graphe simplifi

FIG. 2.25 Premier flot de 30 lves

on demanderait 30 lves de lcole 2 de poursuivre leur scolarit dans lcole 3 pour que 30 lves delcole 1 puissent finir moindre cot leur apprentissage dans lcole 2). Le cot globale de ce flot est de30k 30 = 900k euros. On obtient les nouveaux graphes de la figure 2.26.

FIG. 2.26 Un second flot de 30 autres lves

On na toujours pas atteint le flot de 63 lves. On doit donc continuer lalgorithme. Sur le nouveaugraphe associ, le chemin le plus court est celui qui passe par lcole 3. Son cot est de 33k euros, et sacapacit de 5 lves. Mais il ne nous manque que 3 lves pour atteindre le flot recherch. Il suffit donc derajouter 3 lves pour un cot de 33k 3 = 99k euros. On obtient le flot de la figure 2.27.

La solution optimale cote 720k + 900k + 99k = 1719k euros. Elle consiste envoyer 30 lves fairelUV1 dans lcole 1, et les UV2 et UV3 dans lcole 2. 30 autres lves feront lUV1 dans lcole 2, etsuivront le module runissant les UV2 et UV3 dans lcole 3. Enfin les 3 derniers feront toutes les UV danslcole 3.


FIG. 2.27 Solution optimale pour 63 lves


On veut trouver un moyen de faire transiter un maximum de containers des usines ves les magazins. Ilsagit donc dun problme de flot max.

Le flot va des deux usines (Rouen, Amiens) vers les 2 magasins (Le Havre, Paris). On ajoute une sourceet un puits notre modle pour obtenir le graphe de la figure 2.28

FIG. 2.28 Modelisation du flot

Il reste reporter les contraintes de production, transport et vente sur ce graphe. On obtient le graphe dela figure 2.29

FIG. 2.29 Modelisation du problme

Pour ltape suivant, il faut reporter le flot sur le graphe et utiliser lalgorithme de Ford-Fulkerson (voirfigure 2.30. Comme le marquage atteint le puits, il existe une chane amliorante. Cela prouve que ce flotnest pas optimal.

Il suffit de continuer lalgorithme de Ford-Fulkerson pour rpondre la troisime question. On calculele gain de la chane amliorante :

100 50 = 50 80 0 = 80 120 0 = 100 50 = 50

S Amiens Le Havre Rouen Paris P

Le minimum des diffrents maillon de cette chane est de 50 containers. On reporte ce flot sur le graphe(ajout de 50 sur les arcs orients dans le bon sens, et retrait de 50 sur les arcs inverses). On obtient le graphede la figure 2.31. Le nouveau marquage de Ford-Fulkerson ne permet pas datteindre le puits, il sagit doncdu flot maximal.


FIG. 2.30 Marquage de Ford-Fulkerson sur le flot initial

FIG. 2.31 Report du flot et nouveau marquage

Donc lentreprise devra faire transiter 50 containers par la rote depuis Amiens vers Paris, 50 containerspar la route depuis Amiens vers La Havre, 50 containers par la Seine depuis Rouen vers Paris et enfin70 containers par la Seine depuis Rouen vers Le Havre. Elle pourra ainsi toujours produire, acheminer etvendre ses 220 containers.

2.5 Mthode gomtrique et Simplexe


Il sagit dun problme de programmation linaire.La premire tape consiste trouver la fonction conomique. On nome D le nombre de dromadaires

achets, et S le nombre de kg de de sel achets. Le bnfice du voyage sera (exprim en pa) :Z = 100 D + S.

Les achats du Touareg sont limits par deux contraintes : Son pcule de dpart est de 650 pa, donc : 100D + 0.2 S 650 La seconde contrainte est un peu plus subtile : le nombre de kg de sel que lon peut transporter

est limit par le nombre de dromadaires achets : S 150 D. Pour obtenir la forme canonique,on va transformer lexpression de cette contrainte pour mettre toutes les variables du mme cot delingalit : 150D + S 0.

On arrive donc la forme canonique suivante :Trouver le maximum de Z avec

Z = 100D + S (unit : pa)

avec

100D + 0.2 S 650150D + S 0D 0 et S 0

Comme le problme na que 2 variables, on peut le rsoudre avec le simplexe ou la mthode gom-trique. Pour cette correction nous allons utiliser la mthode gomtrique.

Pour dlimiter le domaine des solutions admissible (voir figure 2.32) :


on rejette toutes les valeurs ngatives (D 0 et S 0). on trace la droite 100 D + 0.2 S = 650, et on rejette toutes les valeurs au dessus (puisque100D + 0.2 S 650).

on trace la droite 150 D + S = 0. Elle divise notre plan en deux. Dun cot il y a des valeursadmissibles et de lautre des valeurs qui ne rpond pas la contrainte (il faut que150D+S 0).Ici comme il y a un nombre ngatif dans les facteurs, la logique de dire infrieur veut dire en dessousde la droite ne tient pas. Pour trouver de quel cot de cette droite se trouvent les valeurs admissibles,il suffit des tester un point de chaque cot. On calcule par exemple la valeur pour le point P1 (S = 0et D = 4, donc 150D + S = 600). On obtient 600 qui est bien infrieur ou gale 0, doncce point est acceptable. Par contre pour le point P2 (S = 500 et D = 0 donc 150D+ S = 500),la valeur obtenue 500, prouve que ce point nest pas admissible. Donc sur le graphe de la figure 2.32,le domaine admissible des solutions se trouve au dessus de la droite 150D + S = 0.

FIG. 2.32 Rsolution gomtrique

Il ne reste plus qu tracer la droite de Z et la faire monter jusqu la limite du domaine. Lultime pointobtenu correspond D = 5 et S = 750.

Donc le touareg devrait acheter 5 dromadaires et 750 kg de sel pour un bnfice de 1005+750 = 1250pa, autrement dit 125 po.


Il sagit dun problme de programmation linaire.Commenons par trouver la fonction conomique optimiser. Si on nomme F1 le nombre de tonnes

de fromage AOC vendues en une anne et F2 le nombres de tonnes de lautre fromage, la marge annuelle(exprime en k euros) de lentreprise est : Z = 3 F1 + F2.

Les ressources imposent des contraintes sur la production : La laiterie reoit 4 millions de litres de lait de la zone AOC, et la tonne de fromage AOC en utilise10 000 litres : 10000 F1 4 000 000

La laiterie reoit 10 millions de litres de lait (4 millions de la zone AOC et 6 millions dautres zones),et tout ce qui nest pas utilis par le fromage AOC (10 000 F1) peut tre utilis pour le secondfromage qui en utilise 7 500 litres par tonne : 7 500 F2 10 000 000 10 000 F1

La tonne de fromage AOC ncessite 30 heures de travail, et celle de lautre fromage 15 heures. Lalaiterie dispose de 21 000 heures : 30 F1 + 15 F2 21 000.

Donc on obtient (aprs avoir repasser la variable F1 d

Exercice s

Documents

Exercice 3ème Cycle 4, Dimension Exercice 1ère S, …chamilo.univ-grenoble-alpes.fr/courses/FAMA8460/document/exos... · 2. Démontrer avec les probabilités Pour tout nombre entier

D veloppement - Exercices ( S rie 1 ) · Exercice 6 : Brevet - Bordeaux - 2001 Soit A = ( 7x ... EXERCICES (SERIE 1) × 99998 ? Exercice 9 : Brevet ... Développer D. Exercice 33

Bac S 2016 Centres étrangers EXERCICE I : ONDES …physchileborgne.free.fr/cours/CH05_exercices _bis_2019.pdfBac S 2016 Centres étrangers EXERCICE I : ONDES ET ELECTRONS (6 points)

lespetitspedagogues.files.wordpress.com€¦ · Web view2019/09/05 · Exercice n 1 Exercice n 2 : Exercice n 3 : Exercice n 4 : Exercice n 5 : Exercice n 6 : Exercice n 7 : Author

Exercice I Exercice II. Exercice II (suite) Exercice III

10 Exercice s

Exercice-P05.pdf - CNCI · Exercice 5 ENONCE La courbe A représente les résultats d’une étude cinétique de l’activité d’une enzyme E sur un substrat S dans des conditions

Exercice 1 : DIFFÉRENTES CONFIGURATIONS D’UN TRAIN ...stephane.genouel.free.fr/FT/0%20TD/TD%2022%20-%20Loi%20E-S%2… · Exercice 2 : TRAINS ÉPICYCLOÏDAUX DE TYPE IV. Exemple

Exemple 2 Exemple 2 PGCD(210;126) Exercice 1 Exercice 1 PGCD(1085;837) Exercice 2 Exercice 2 Les billes Exercice 3 Exercice 3 Le patchwork Exercice 4 Exercice

Exercice s Depar Cours 2008

Exercice s Corrige s Divers

SSIAP.cours.fascicule6.1. R Diger Une Notice de s Curit .Exercice d Application

Exercice s

lespetitspedagogues.files.wordpress.com€¦ · Web viewExercice n 1 : Exercice n 2 : Exercice n 3 : Exercice n 4 : Exercice n 5 : Exercice n 6 : Exercice n 7 : Author CAP – donnees

Rm Exercice s

4eme Dans la cuisine Chapitre 7 Je m entraine Correctionmonprofdephysique.weebly.com/uploads/5/3/8/1/... · Exercice 2. Exercice 3. Exercice 4 n n. Exercice 5 a s n n il. Exercice

Cours de statistique - Bienvenue · Exercice 1 Exercice 2 Exercice 3 Exercice 4 7. ANNEXE : L'OPERATEUR S 7.1. Définition 7.2. De l'opérateur symbolique à la somme explicite 7.2.1

o EYR O LLE S Best f · PASCAL ROQUES EYR O LLE S Best f o par la pratique UML 2 ... exercice 5-10). EXERCICE 6-5. Diagramme d’états simple S o l u t i …

Exercice au panier Coup Droit de décalage croisé 12nat.54.free.fr/cariboost2/cariboost_files/exos_cd.pdf · D rill 'Details Type: Suggested Time: Prepared by: 43 S Exercice au panier

Exercice N°5 Exercice N°2 Exercice N°3 Exercice … · Exercice N°1 Exercice N°2 Exercice N°3 Exercice N°4 Exercice N°5 Exercice N°6 Exercice °7. Exercice N°8 Solution