Optimisation linéaire

IdC 2A Jeudi 16 octobre La méthode du simplexe sur un exemple. 1 Mise en place du cadre. On étudie le programme linéaire suivant écrit sous forme canonique : max z = 5x + y   x    30x + y  y sous contraintes   x    y Dénition 1.1 On appelle variable d'écart la quantité mer une contrainte d'inégalité en contrainte d'égalité. ≤ 4 ≤ 150 ≤ 60 ≥ 0 ≥ 0 positive qui permet de transfor- Ici, on a trois contraintes donc on ajoute trois variables

estimés à 1000 femmes et 2000 hommes dans "le soir". La direction estime d’autre part que la compagne devait toucher au moins 50000 femmes et 90000 hommes. 1. Exprimer le problème suivant un programme linéaire 2pts 2. Trouver la solution optimale du problème. 4pts Exercice 2 On considère le programme linéaire suivant : Max Z = 3X1 + X2 – X3 Sujet à : X1 + 2X2 + X3 ≤ 20 X1 + X2 + 3X3 ≥ 15 X1 – 2X2 + 4X3 = 20 X1 ≥ 0, X2 ≥ 0 et X3 srs. 1. Ecrire le programme sous la forme standard 2pts 2. Trouver le dual

ALGORITHME DU SIMPLEXE Considérons le problème de programmation linéaire suivant : Max Z = 2x1 + x2 x1 + x2 6 3x1 + 4x2 9 x1 0 , x2 0 La mise sous forme standard (introduction des variables d'inactivité x3 et x4) donne : Max Z = 2x1 + x2 x1 + x2 + x3 = 6 3x1 + 4x2 + x4 = 9 x1 0 , x2 0, x3 0, x4 0 On passe de cette forme standard au tableau suivant : |x1 |x2 |x3 |x4 |R |

télévision : 40 x1  75x2  500 , x1  3 et x2  2 La fonction objectif à maximiser représente le nombre de clients potentiels par publicité z  400 x1  900 x2  500 x3  200 x4 . Les contraintes de non-négativité sont vérifiées. Le programme linéaire résultant est : Max s.c. 400 x1  900 x2  500 x3  200 x4 40 x1  75 x2  30 x3  15 x4  800 30 x1  40 x2  20 x3  10 x4  2000 40 x1  75 x2 x1 x2  500 3 2 x1  0, x2  0, x3  0, x4  0 Exercice 4 : Les variables de décisions sont

qu’appartenant à des domaines de la gestion très différents, sont susceptibles d’être traités à l’aide du même modèle, le modèle de transport, qui constitue une catégorie particulière de programmes linéaires. Il serait, bien entendu, possible de résoudre ces problèmes à l’aide des techniques de la programmation linéaire (simplexe), mais la structure très spécifiques des problèmes de transport permet de recourir à des techniques particulières beaucoup plus légères. Nous envisagerons, dans la première

Techniques Quantitatives : Recherche Oppérationnelle : Mr EZZEHAR Eléments du cours Programme Linéaire Résolution du Simplexe Notion de Dualité Exemples avec corrigés Numérisation & Conception Mr Lehcen HABCHI Le Portail des Etudiant d’Economie www.e-tahero.net contact@e-tahero.net Synthèse de Cours Recherche Opérationnelle Résolution Simplexe Soit le programme linéaire (P) suivant : Max z =500 x1 +300 x2 20 x1 +10 x2 ≤ 2000 10 x1 + 45 x2 ≤ 5400 40 x1 + 30 x2 ≤ 4800

Programmation linéaire D IDIER M AQUIN ´ ´ ´ Ecole Nationale Superieure d’Electricite et de Mecanique Institut National Polytechnique de Lorraine ´ ` ` ´ Mathematiques discretes – cours de 2eme annee ´ Programmation lineaire – p.1/49 Programmation linéaire Problèmes d’optimisation sous contraintes (cas particulier) Fonction objectif et contraintes linéaires (par rapport aux variables inconnues). Formulation générale : max M = cT x x sous les contraintes Ax ≤ b x≥0

d’adapter la production à la demande, de déterminer les niveaux de stocks.En économie les problèmes sont devenus complexes, en raison : de la taille croissante des entreprises et les liens entre elles, et du choixdes investissements les plus rentables, optimisation des niveaux d’activité, fiabilité et sûreté de fonctionnement des équipements, gestion de la production . . . etc. En raison de l’ampleur des enjeux décisionnels, le décideur ne peut plus prendre de décisions hâtives et justifier un choix d’attribution

Programmation Lineaire Rachidi Kotchoni 02 Février 2010 R. Kotchoni (U. de Montreal) Programmation Lineaire 02 Février 2010 1 / 20 Programmation Linéaire Dans le chapitre précédent, on a vu qu’ problème d’ un optimisation dans Rn sous-contraintes d’ inégalité peut s’ écrire sous la forme: max f (x1 , x2 , ..., xn ) 8 > g1 (x1 , x2 , ..., xn ) > < g2 (x1 , x2 , ..., xn ) sc: .... > > : gK (x1 , x2 , ..., xn ) c1 c2 cK R. Kotchoni (U. de Montreal) Programmation Lineaire 02 Février

Prf. Adil Chergui 2012/2013 I. II. III. IV. V. VI. Introduction à la recherche opérationnelle Modélisation et formulation d’un programme linéaire Résolution graphique d’un PL La méthode simplexe Problèmes de minimisation et problèmes irréguliers Dualité  Définition la recherche opérationnelle (RO) peut être définie comme un ensemble de méthodes d’analyse scientifique (mathématique et informatique) des phénomènes d’organisation qui traite de la maximisation d’un profit, d’une