Exercices de Programmation Lin´eaire – Mod´elisation
Exercices de Programmation Lin´eaire – Simplexe Primal – exercice 1 : R´esoudre le programme lin´eaire suivant par la m´ethode du simplexe Max z =5x1+6x2+9x3+8x4 s c x1+2x2+3x3+ x465 x1+ x2+2x3+3x463 x1, x2, x3, x4>0 – en faisant entrer en base la variable hors base dont le couˆt r´eduit est le plus grand
174 EXERCICES SUPPLÉMENTAIRES — PARTIE II
180 CHAPITRE 4 PROGRAMMATION LINÉAIRE Introduction La programmation linéaire constitue l’origine de l’optimisation mathématique moderne Son étude a été menée par George Bernard Dantzig à partir de 1947 L’algorithme du sim-plexe, que nous présentons dans ce chapitre, est considéré comme un des dix algorithmes les
Programmation linéaire
la programmation linéaire Nous étudierons 3 méthodes pour résoudre les différents types de problèmes de programmation linéaire; la première est basée sur une résolution graphique, elle est donc limitée à 2 ou 3 variables La deuxième méthode est plus algébrique et elle justifiera la troisième qui porte le nom de
1 Programmation linéaire
1 Programmation linéaire Corrigé ex 1 : Méthode du simplexe Programme 1 8 >> >> >> < >> >> >>: Max(x 1 + 2x 2) x 1 + 3 2 21 x 1 + 3x 2 18 x 1 2 5 x 1 et x 2 0 On introduit des variables d’écart, ce qui conduit aux équations suivantes pour les contraintes du problème : 8 >< >: x 1 + 3 2 + 3 = 21 x 1 + 3x 2 + x 4 = 18 x 1 x 2 + x 5 = 5
Programmation lin eaire et Optimisation
Programmation lin eaire et Optimisation Didier Smets Chapitre 1 Un probl eme d’optimisation lin eaire en dimension 2 On consid ere le cas d’un fabricant d
CORRIGE du TD N°1 : PROGRAMMATION LINÉAIRE
CORRIGE du TD N°1 : PROGRAMMATION LINÉAIRE EXERCICE 1 : corrigé 1- Modélisation sous forme de programme linéaire Désignons par et les nombres d’articles de chaque type (poterie, émaux sur cuivre) produits et par Z, le bénéfice généré par cette fabrication et sont les variables de décision du modèle
Programmation Lin aire Cours 1 : programmes lin aires, mod
•C Gu´eret, C Prins et M Sevaux - Programmation lin´eaire : 65 probl`emes d’optimisation mod´elis´es et r´esolus avec Visual Xpress, Eyrolles, 2000 •C Prins et M Sevaux - Programmation lin´eaire avec Excel : 55 probl`emes d’optimisation mod´elis´es pas `a pas et r´esolus avec Excel, Eyrolles, 2011
Chapitre : PROGRAMMATION LINÉAIRE 1ere ES
Chapitre : PROGRAMMATION LINÉAIRE 1ere ES Exercice4 Dans un centre de loisirs, il est possible de prendre une carte d’abonnement annuelle de 140 e, commune à la disco-thèque et au cinéma A la discothèque, l’entrée sans réduction est de 15 eet l’abonnement donne droit à une réduction de 40
Exercices 1 Programmes lin eaires - imag
Exercices 1 Programmes lin eaires Mod elisation et g eom etrie Exercice 1 Votre r egime alimentaire exige que tous les aliments que vous mangez proviennent de l’un des quatre \groupes d’aliments de base" (g^ateau au chocolat, cr eme glac ee, soda et chee-secake)
MHT 423: Mod elisation et optimisation - u-bordeauxfr
Programmation en nombres entiers mixtes et relaxations Le deuxi eme fait veut dire que, malheureusement, la programmation en nombres entiers est plus di cil (m^eme beaucoup plus di cil) que la programmation lin eaire Le premier veut dire qu’on peut n eanmoins d e nir des m ethodes de r esolution pour les programmes en nombres entiers qui
[PDF] exercice corrigé methode simplexe pdf
[PDF] multiples et sous multiples physique
[PDF] multiples et sous multiples physique exercices
[PDF] multiples et sous multiples du gramme
[PDF] multiple et sous multiple exercice
[PDF] multiples et sous multiples du litre
[PDF] multiplicateur fiscal formule
[PDF] multiplicateur fiscal macroéconomie
[PDF] cobb douglas explication
[PDF] revenu d'équilibre formule
[PDF] multiplicateur des dépenses publiques macroéconomie
[PDF] fonction de cobb douglas pdf
[PDF] revenu d'équilibre et revenu de plein emploi
[PDF] fonction cobb douglas ses
Programmation lineaire et Optimisation
Didier Smets
Chapitre 1
Un probleme d'optimisation lineaire
en dimension 2 On considere le cas d'un fabricant d'automobiles qui propose deux modeles a la vente, des grosses voitures et des petites voitures. Les voitures de ce fabriquant sont tellement a la mode qu'il est certain de vendre tout ce qu'il parvient a produire, au moins au prix catalogue actuel de 16000 euros pour les grosses voitures, et 10000 euros pour les petites voitures. Son probleme vient de l'approvisionnement limite en deux matieres premieres, le caoutchouc et l'acier. La construction d'une petite voiture necessite l'emploi d'une unite de caoutchouc et d'une unite d'acier, tandis que celle d'une grosse voiture necessite une unite de caoutchouc mais deux unites d'acier. Sachant que son stock de caoutchouc est de 400 unites et son stock d'acier de 600 unites, combien doit-il produire de petites et de grosses voitures au moyen de ces stocks an de maximiser son chire d'aaire? Nous appelleronsxle nombre de grosses voitures produites,yle nombre de petites voitures produites, etzle chire d'aaire resultant. Le probleme se traduit alors sous la formemaximiserz= 16000x+ 10000y sous les contraintesx+y4002x+y600
x0; y0:(1.1)1.1 Solution graphique
Un tel systeme, parce qu'il ne fait intervenir que deux variables, peu se resoudre assez facilement de maniere graphique, en hachurant la zone correspondant aux contraintes, et en tracant les lignes de niveaux (ici des lignes paralleles) de la fonction a maximiser (cfr. graphique ci-dessous). On obtient ainsi la solution optimalex= 200 ety= 200, qui correspond az= 5200000:Elle est unique dans ce cas precis, et correspond a un \sommet" de la zone de contraintes. 11.2 Sensibilite a la variation des stocks
Observons comment la solution du probleme evolue lorsqu'on modie certaines donnees de depart, par exemple une augmentation du stock de caoutchouc ou du stock d'acier. Imaginons que le stock d'acier soit de 700 au lieu de 600, le nouveau probleme s'ecrit maximiserz= 16000x+ 10000y sous les contraintesx+y4002x+y700
x0; y0:(1.2) Toujours de maniere graphique, on s'apercoit que la solution optimale est maintenant donnee parx= 300 ety= 100, ce qui correspond az= 5800000:Autrement dit, une augmentation de 100 unites d'acier a un impact de 600000 euros sur le chire d'aaire. On dira alors que leprix marginalde l'unite d'acier est de 6000 euros. 2 Si le stock d'acier passe a 800, la solution optimale devientx= 400 ety= 0 et le chire d'aairez= 6400000:Augmenter le stock d'acier au-dela de 800, sans changer le stock de caoutchouc, n'a plus aucune in uence sur la solution optimale, caryest contraint a rester positif. Imaginons maintenant que le stock d'acier reste xe a 600 mais que le stock de caou- tchouc passe de 400 a 500. Le nouveau probleme s'ecrit maximiserz= 16000x+ 10000y sous les contraintesx+y5002x+y600
x0; y0:(1.3) Toujours de maniere graphique, on s'apercoit que la solution optimale est maintenant donnee parx= 100 ety= 400, ce qui correspond az= 5600000:Autrement dit, une augmentation de 100 unites de caoutchouc a un impact de 400000 euros sur le chire 3 d'aaire. On dira alors que leprix marginalde l'unite de caoutchouc est de 4000 euros. Si le stock de caoutchouc passe a 600, la solution optimale devientx= 0 ety= 600 et le chire d'aairez= 6000000:Augmenter le stock de caoutchouc au-dela de 600, sans changer le stock d'acier, n'a plus aucune in uence sur la solution optimale, carxest contraint a rester positif. 41.3 Le probleme dual du concurrent
Supposons maintenant que le fabricant d'automobile possede un concurrent qui, pour honorer des commandes en trop grand nombre, se propose de lui racheter tous ses stocks. Ce dernier doit faire une ore de prix (la m^eme, disonsu) pour chaque unite de caoutchouc et une ore de prix (disonsv) pour chaque unite d'acier. Pour que l'ore soit acceptee, il faut que le prix paye par le concurrent soit au moins egal a ce que le fabriquant pourrait en tirer en produisant des voitures. Le probleme du concurrent s'ecrit ainsi minimiserp= 400u+ 600v sous les contraintesu+v10000 u+ 2v16000 u0; v0:(1.4) Une analyse graphique fournit la solution optimaleu= 4000 etv= 6000, ce qui corres- pond a un prix globalp= 5200000:On remarque (nous verrons par la suite que ce n'est pas un hasard) que la solution optimale du probleme du concurrent (on parlera deprobleme dual, par opposition auprobleme primaldu fabriquant) correspond aux prix marginaux du probleme du fabricant, et que le prix minimal que puisse proposer le concurrent est egal au chire d'aaire maximal du fabricant. 5Chapitre 2
Un probleme d'optimisation lineaire
en dimension superieure Dans ce chapitre, nous allons decrire un probleme de transport optimal assimilable a un probleme d'optimisation lineaire en dimension 6. De ce fait, il ne sera plus possible de le resoudre au moyen de la methode graphique du chapitre precedent. Notre fabricant d'automobiles possede trois cha^nes de montageM1,M2etM3, tandis que son stock d'acier provient de deux acieriesA1etA2:Les co^uts de transport d'une unite d'acier d'une acierie vers une usine de montage sont donnes par le tableau suivant :M 1M 2M 3A191628
A2142919
Les besoins de production des cha^nes de montage dierent, ainsi que les capacites de production des acieries, et sont donnees par les deux tableaux suivants :A 1206A 2394M
1142
M 2266
M 3192
Il s'agit donc pour le fabricant de determiner le plan de transport des unites d'acier produites vers les cha^nes de montage an de minimiser le co^ut total de transport. Pour i= 1;2 etj= 1;2;3, notonsxijle nombre d'unites d'acier acheminees depuis l'acierieAi vers la cha^ne de montageMj:Le probleme de transport optimal peut alors s'ecrire : minimisert= 9x11+16x12+28x13+14x21+29x22+19x23 sous les contraintesx11+x12+x13206; x