PROGRAMMATION LINEAIRE PARL’EXEMPLE

F.DROESBEKE

M.HALLINCL.LEFEVRE

RESUME

Les enseignante de Recherche Opérationnelle trouvent placeactuellement dans la formation de tous ceux que leur professiondestine à assumer des responsabilités de gestion et d’organisation:ingénieurs , économistes, gestionnaires commerciaux, cadesd’entreprises, preneurs de décision au sens le plus large. A l’ère del’ordinateur- outil essentiel de la mise en œuvre des techniques derecherche opérationnelle - Il est indispensable de prendre contactavec les principales méthodes existantes en identifiant, en «mettanten équation», en résolvant un certain nombre de problèmes de petitedimension: on n’utilise bien que ce qu’on connaît bien. Le but du présent ouvrage est de permettre un telle prise de contact.Un brève présentation théorique des méthodes décrites est suivie dela résolution détaillée de quelques problème types et d’un grandnombre

d’exercice proposés. Le niveau mathématique requis ne dépasse pas celui des années terminales des lycées et collèges, et estdonc parfaitement accessible à un large éventail de lecteurs et d’étudiants. Ce premier volume, consacré à la Programmation linéaire, accorde bien entendu une large palce à l’algorithme du simplexe et àses dérivés (notion de dualité, programmes paramétriques, algorithme dual-simplexe,…). Il couvre également quelques méthodesmoins classique, telles la méthode de Gomory pour la résolution des programmes en nombres entiers et les méthodes deséparation pour les programmes en nombres entiers et les méthodes de séparation pour les programmes à variables binaires. Unsecond volume, consacré aux applications de la théorie des graphes (algorithmes de plus court/plus long chemin, problèmes deflot optimal, de transport, d’affectation, d’ordonnancement,…) paraîtra sous peu

TABLE DES MATIERES

Chapitre I PROGRAMMATION LINEAIRE RESOLUTION ET PROBLEMES ANNEXES 7 1.1. LA PROGRAMMATION LINEAIRE 71.2. PRESENTATION THEORIQUE 91.3. RESOLUTION D'UN PROGRAMME LINEAIRE (PL) 11 1.3.1. Résolution graphique 12 1.3.2. Résolution par énumération des solutions de base 151.4. L'ALGORITHME DU SIMPLEXE 18 1.4.1. Principe de l'algorithme 18 1.4.2. Le tableau simplexe 18 1.4.3. Organigramme de l'algorithme du simplexe 21 1.4.4. Exemples résolus 23

1.4.5. Interprétation économique de30

1.5. OBTENTION D'UNE BASE REALISABLE DE DEPART 32 1.5.1. Organigramme de la méthode M et de la méthode en deux phases 32 1.5.2. Exemples résolus 341.6. DEGENERESCENCE – CYCLAGE 40

1.6.1. Solution de base dégénérée 40

1.6.2. Dégénérescence et cyclage 41 1.6.3. Méthode de perturbation 42 1.6.4. Organigramme de la méthode de perturbation 44 1.6.5. Exemples résolus 451.7. VARIABLES SANS RESTRICTION DE SIGNE 50 1.7.1. Première méthode 50

1.7.1. Première méthode 50 1.7.2. Seconde méthode 51 1.7.3. Exemples résolus 511.8. PROGRAMMES LINEAIRES A VARIABLES BORNEES 55 1.8.1. 55 1.8.2. Exemples résolus 561.9. EXERCICES PROPOSES 621.10. SOLUTION DES EXERCICES PROPOSES 68 Chapitre Il DUALITE EN PROGRAMMATION LINEAIRE 70 2.1. PROGRAMMES PRIMAL ET DUAL 702.2. THEOREMES ET PROPRIETES FONDAMENTALES 80 2.2.1. Théorèmes 80 2.2.2. Dualité et théorie de Lagrange 802.3. RESOLUTION DU DUAL 832.4. PASSAGE DU DERNIER TABLEAU SIMPLEXE DU PRIMAL AU DERNIERT ABLEAU SIMPLEXE DU DUAL 86 2.4.1. 86 2.4.2. Exemples résolus 872.5. INTERPRETATION ECONOMIQUE DU DUAL 88 2.5.1. Analyse aux dimensions des problèmes primai et dual 88 2.5.2. Le programme dual vu comme le problème d'une entreprise concurrente 90 2.5.3. Interprétation économique des YI à l'optimum 902.6. EXERCICES PROPOSES 932.7. SOLUTION DES EXERCICES PROPOSES 94 Chapitre III L'ALGORITHME DUAL – SIMPLEXE 100 3.1. INTRODUCTION 100 3.1.1. Exemple R.3.1 100 3.1.2. Exemple R.3.2. 101 3.1.3. Présentation intuitive de l'algorithme dual – simplexe 1023.2. L'ALGORITHME DUAL – SIMPLEXE 104 3.2.1. Conditions d'application 104 3.2.2. Règles de changement de base 105 3.2.3. Evolution et règles d'arrêt 105 3.2.4. Organigramme de l'algorithme dual – simplexe 1063.3. EXEMPLES RESOLUS 1073.4. METHODE DE LA CONTRAINTE ARTIFICIELLE 113 3.4.1. Principe de la méthode 114 3.4.2. Organigramme de la méthode de la contrainte artificielle 115 3.4.3. Exemples résolus 1173.5. EXERCICES PROPOSES 1213.6. SOLUTION DES EXERCICES PROPOSES 126 Chapitre IV PROGRAMMES LINEAIRES PARAMETRIQUES 130 4.1. PARAMETRISATION DE LA FONCTION ECONOMIQUE 1304.2. PARAMETRISATION DU SECOND MEMBRE DES CONTRAINTES 1324.3. REMARQUES 1324.4. EXEMPLES RESOLUS 1334.5. EXERCICES PROPOSES 1424.6. SOLUTION DES EXERCICES PROPOSES 144 Chapitre V PROGRAMMES LINEAIRES EN VARIABLES ENTIERES PROCEDURES D'OPTIMISATION PAR COUPE 154 5.1. INTRODUCTION 1545.2. PROGRAMMES LINEAIRES EN VARIABLES ENTIERES 156 5.2.1. Définition d'un programme linéaire en variables entières (PLE) 156

5.2.2. Méthodes de résolution d'un programme linéaire en variable entières 1575.3. METHODE DE COUPE DE GOMORY POUR LES PROGRAMMES LINEAIRES EN VARIABLES ENTIERES 158 5.3.1. Principe des méthodes de coupe 158 5.3.2. Théorème de base de l'algorithme de Gomory 159 5.3.3. Principe de l'algorithme de Gomory 161 5.3.4. Organigramme de la méthode de Gomory 1645.4. EXEMPLES RESOLUS 1655.5. EXERCICES PROPOSES 1735.6. SOLUTION DES EXERCICES PROPOSES 175 Chapitre VI PROGRAMMES LINEAIRES EN VARIABLES 0-1 PROCEDURES D'OPTIMISATION PAR SEPARATION 176

6.1. INTRODUCTION 1766.2. PROCEDURES D'OPTIMISATION PAR SEPARATION (PS) 177 6.2.1. Principe fondamental des PS - Ensemble sondable de solutions 177 6.2.2. Etapes d'une PS. Représentation sous forme de graphe 1786.3. PSES POUR LES PL EN VARIABLES 0-1 180 6.3.1. Allure de l'arborescence 180 6.3.2. Hypothèses et notations 181 6.3.3. Organigramme de la PSES 183 6.3.4. Commentaire de l'organigramme 1846.4. EXEMPLE RESOLU 1856.5. EXERCICES PROPOSES 1886.6. SOLUTION DES EXERCICES PROPOSES 191 BIBLIOGRAPHIE 192

LISTE DES ORGANIGRAMMES

ALGORIHME DU SIMPLEXE 21 METHODE M ET METHODE EN DEUX PHASES 33 METHODE DE PERTURBATION 44 ALGORITHME DUAl-SIMPLEXE 106 METHODE DE LA CONTRAINTE ARTIFICIELLE 115 METHODE DE GOMORY 164 ALGORITHME D'UNE PROCEDURE D'OPTIMISATION PAR SEPARATION 177 PROCEDURE D'OPTIMISATION PAR SEPARATION ET EVALUATION SEQUENTIELLE 183

LISTE DES PRINCIPALES

ABREVIATIONS UTILISEES

Pl : programme linéaire PlE : programme linéaire en variables entières PLM : programme linéaire mixte SBR : solution de base réalisable PS : procédure d’optimisation par séparation SEP : séparation et évaluation progressiVe SES : séparation et évaluation séquentielle s. r. s.: sans restriction de sigle

TOP