Programmation linéaire PDF La programmation linéaire peut

1 Programmation linéaire

Méthodes Numériques. Document 4 : Corrigé des exercices d'optimisation linéaire Le tableau de départ pour la méthode du simplexe est donc :.

Cahier dexercices corrigés Eric LALLET Jean-Luc RAFFY

Correction page 42. 1.6 Programmation linéaire : le simplexe. Exercice 1.6.1 (Une histoire de fromage). Une laiterie s'

TD 7 : Exercice corrigé Algorithme du simplexe Méthode des deux

Algorithme du simplexe. Méthode des deux phases. Exercice. Résoudre par la méthode des deux phases le modèle de programmation linéaire suivant :.

Programmation linéaire Jean-Philippe Javet

6.5 Exemple accompagné (reprise de l'exercice 3.1 déjà étudié en page 17) : . . . . . . . . . 47. 7 Résolution par la méthode du simplexe.

Corrigé : Programmation linéaire II

Corrigé : Programmation linéaire II. Exercice 1. Au quatorzième siècle un Touareg compte gagner un b) Résoudre en utilisant l'algorithme du simplexe.

Recherche opérationnelle

2 La programmation linéaire - Méthode du simplexe. 31. 2.1 Introduction . 2.2.6 Exercices récapitulatifs .

- Exercices de TD - 1 Modélisation.

Résoudre la relaxation linéaire de ce probl`eme en utilisant l'algorithme du simplexe du TP1. - Exercice 5 - Taxis. Une compagnie de taxi dispose de quatre

Programmation linéaire en nombres entiers : la méthode du simplexe

Méthode du simplexe : en oubliant les contraintes d'intégrité il se peut que la soln optimale soit entière auquel cas nous avons résolu le problème demandé

FSJES-AC RECHERCHE OPERATIONNELLE Semestre 6 Filière

PROGRAMMATION LINEAIRE - Complément – Exercices avec solutions. M.ATMANI ... Dans ce paragraphe on présentera la méthode du simplexe pour un problème de ...

(Microsoft PowerPoint - 5_dualite [Mode de compatibilité])

Problème de programmation linéaire sous forme standard L'algorithme dual du simplexe est une méthode itérative pour résoudre un.

Chapitre 3 Méthode du simplexe - Université Laval

6 CHAPITRE 3 MÉTHODE DU SIMPLEXE Onobservequeladernièrelignes’écrit 1=3 x 1 2=3 x 4 z = 2 ()z = 2+1=3 x 1 2=3 x 4: Etantdonnéquelesvariablehors-basevéri?ex 1 = x 4 = 0onaquez = 2 quiestla valeurdelafonctionobjectiveausommetx = (0;1;1;0) 3 Onretourneàl’étape1 La dernière ligne du tableau ~cx z = 2 fournie toujours la valeur de

Programmation linéaire - Méthodes et applications

sation sous contraintes linéaires s’appuie sur l’algèbre linéaire et l’analyse convexe L’èremoderned’optimisationmathématiqueoriginedestravauxdeGeorgeBernardDant-zig sur la programmation linéaire à la ?n des années 1940 Le chapitre 4 en présente les résultats principaux

Exercice corrigé Algorithme du simplexe forme tableaux

Exercice corrigé Algorithme du simplexe forme tableaux Méthodes des deux phases Exercice corrigé Algorithme du simplexe forme tableaux Méthodes des deux phases Soit le modèle du problème de programmation linéaire suivant : ? ? + ? ? ? + ? = + = 0 4 2 2 16 2 3 0 6 4 13 3 2 12 2 1 2 1 2 1 2 1 2 xx x x x x x S C x x

6 10 60 8 25 200 - Université Ibn Khaldoun de Tiaret

Algorithme du simplexe Méthode des deux phases Exercice 12 Résoudre par la méthode des deux phases le modèle de programmation linéaire suivant : 12 12 12 12 60 0 80 0 x x x xx xx ° t °° t ® ° d ° °¯ tt a) Standardisation de (P) par ajout des variables d’écart : 1 2 3 4 5 1 2 3 1 2 4 1 2 5 1 2 3 4 5 12 20 0 0 0 6 10 60 8 25

Simplexe forme Tableau Exercice corrigés x 2 x - x

Simplexe forme Tableau Exercice corrigés Exercice N° 1 : Soit le problème de Programmation linéaire suivant : Max Z = 3x1 + 2x2 x1 + 2x2

1 Programmation linéaire - pagesperso-orangefr

Corrigé ex 3 : Méthode des variables ajoutées Les deux programmes d’optimisation de cet exercice présentent une dif?culté sup-plémentaire pour appliquer la méthode du simplexe : on ne peut pas démarrer le sim-plexe à partir de l’origine (c’est-à-dire à partir du point de coordonnées nulles) car ce

Programmation linéaire

La programmation linéaire peut se dé?nir comme une technique mathématique permettant de résoudre des problèmes de gestion et particulièrement ceux où le gestionnaire doit déterminer face à di?érentes possibilités l’utilisation optimale des ressources de l’entreprise pour atteindre

Programmation linéaire Algorithme du simplexe Résolution de

1-Rajouter les variables d’écart (positives ou nulles) Puis résoudre le problème par l’algorithme du simplexe et la méthode des tableaux 2-Pour vérifier le résultat de la question précédente résoudre le problème (à 2 variables x 1 x 2) graphiquement Algorithme du simplexe Soit le problème (P):

TD 5 Programmation linéaire et optimisation Dualité Exercice

Dans le cas d'un problème de programmation linéaire (minimisation) possédant une solution optimale finie l'algorithme primal du simplexe permet à chaque itération de passer d'une solution de base réalisable pour le primal à une autre jusqu'à ce que les conditions d'optimalité soient satisfaites: un

Devoir de vacances de Programmation Linéaire (Correction)

Les exercices se rapportent tous au programme linéaire (P) Néanmoins ils sont indépendants et peuvent être traités dans n’importe quel ordre Exercice 1 Forme canonique forme standard et dual (2 points) 1 Mettre le programme linéaire sous forme canonique 2 Mettre le programme linéaire sous forme standard 3

Programmation lin´eaire Sa?aKedad-Sidhoum Sa?akedad-sidhoum

L'algorithme du simplexe - HEC Montréal

Avant que l’algorithme du simplexe puisse être utilisé pour résoudre un programme linéaire ce programme linéaire doit être converti en un programme équivalent où toutes les contraintes technologiques sont des équations et toutes les variables sont non négatives a Contraintes de type

Comment fonctionne l’algorithme du simplexe ?

L’algorithme du simplexe est mis en œuvre selon deux méthodes, la méthode des dictionnaires et la méthode des tableaux. La première méthode permet de bien comprendre le déroulement du simplexe alors que la méthode des tableaux est plus algébrique et elle conduit à la mise en œuvre effective de l’algorithme du simplexe.

Qu'est-ce que la méthode du simplexe?

1 - Principe Lorsque nous sommes en présence de plus de deux produits, la méthode du simplexe est la seule méthode permettant de trouver la combinaison de produits qui rend optimal la fonction économique.

Qui a inventé le simplexe ?

Ce terme a été introduit pendant la Seconde Guerre mondiale et systématiquement utilisé à partir de 1947 lorsque G. Dantzig inventa la méthode du simplexe pour résoudre les problèmes de programmation linéaire.

Comment fonctionne la communication simplex ?

En télécommunications, la communication simplex utilise un canal de communication qui envoie l’information dans une direction seulement 1. Un canal de communication « duplex » nécessite deux canaux « simplex » qui envoient l’information dans des directions opposées.

Programmation linéaire

2 eOption spécifique

Jean-Philippe Javet

x3 x 4 x 5x

1x2x3x4x5¨°°3 4 1 0 0 42001 3 0 1 0 24002 2 0 0 1 2600

100 120 0 0 0 0

http://www.javmath.ch

Table des matières

1 Introduction 1

1.1 Préambule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 1

1.2 Un exemple résolu par voie graphique . . . . . . . . . . . . . . . . .. . . . . . . . . 2

2 Résolution de systèmes d"inéquations à 2 ou 3 variables 5

2.1 Inéquations linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 5

2.2 Système d"inéquations linéaires . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 8

2.3 Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 12

2.3.1 Quelques propriétés des ensembles convexes . . . . . . . .. . . . . . . . . . 12

3 Traduction des problèmes en langage mathématique 15

3.1 Un exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 15

4 Résolution graphique d"un problème à 2 variables 21

4.1 Reprenons l"exemple résolu au premier chapitre . . . . . . .. . . . . . . . . . . . . 21

4.2 Résolution graphique d"un problème de minimisation . . .. . . . . . . . . . . . . . 22

5 Résolution graphique d"un problème à 3 variables 25

5.1 Un exemple à 3 variables . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 25

5.2 Un théorème important . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 29

5.3 Exemple FIL ROUGE (à compléter) . . . . . . . . . . . . . . . . . . . . .. . . . . 29

6 Résolution par méthode algébrique 33

6.1 Variables d"écart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 33

6.2 Coefficients des variables d"écart dans la fonction économique . . . . . . . . . . . . . 34

6.3 Résolution complète de l"exemple FIL ROUGE . . . . . . . . . . .. . . . . . . . . . 36

6.4 Marche à suivre de la méthode algébrique . . . . . . . . . . . . . .. . . . . . . . . 46

6.5 Exemple accompagné(reprise de l"exercice 3.1 déjà étudié en page 17): . . . . . . . . . 47

7 Résolution par la méthode du simplexe 55

7.1 Résolution du problème FIL ROUGE par la méthode du simplexe . . . . . . . . . . 55

7.2 Marche à suivre de la résolution matricielle . . . . . . . . . .. . . . . . . . . . . . . 60

I II

7.3 Les variables dans et hors programme dans la résolution matricielle . . . . . . . . . 61

7.4 Exemple accompagné . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 62

7.5 Quelques remarques pour terminer . . . . . . . . . . . . . . . . . . .. . . . . . . . 66

8 OpenOffice pour résoudre des problèmes de P.L. 67

8.1 Résolution de l"exemple accompagné(cf. pages 47 et 62). . . . . . . . . . . . . . . . 67

8.2 Quelques exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 70

A Quelques éléments de solutions I

A.2 Résolution de systèmes d"inéquations . . . . . . . . . . . . . . .. . . . . . . . . . . I

A.3 Traduction des prob. en langage mathématique . . . . . . . . .. . . . . . . . . . . II A.4 Résolution graphique d"un prob. à 2 variables . . . . . . . . .. . . . . . . . . . . . IV A.5 Résolution graphique d"un prob. à 3 variables . . . . . . . . .. . . . . . . . . . . . IV

A.6 Résolution par méthode algébrique . . . . . . . . . . . . . . . . . .. . . . . . . . . V

A.7 Résolution par méthode du simplexe . . . . . . . . . . . . . . . . . .. . . . . . . . VI A.8 OpenOffice pour résoudre des problèmes de P.L. . . . . . . . . . .. . . . . . . . . . VII

Index VIII

Introduction

1.1 Préambule

Laprogrammation linéairepeut se définir comme une technique mathématique permettant

de résoudre des problèmes de gestion et particulièrement ceux où le gestionnaire doit déterminer,

face à différentes possibilités, l"utilisation optimale des ressources de l"entreprise pour atteindre

un objectif spécifique comme la maximisation des bénéfices oula minimisation des coûts. Dans la

plupart des cas, les problèmes de l"entreprise pouvant êtretraités par la programmation linéaire

comportent un certain nombre de ressources. On peut mentionner, par exemple,la main-d"uvre,

les matières premières, les capitaux, ... qui sont disponibles en quantité limitée et qu"on veut

répartir d"une façon optimale entre un certain nombre de processus de fabrication. Notre approche

pour résoudre ce type de problèmes sera divisée en deux étapes principales :

a) La modélisationdu problème sous forme d"équations ou d"inéquations linéaires qui permet-

tra ainsi de bien identifier et structurer les contraintes que doivent respecter les variables du

modèle; de plus, on doit définir l"apport de chaque variable àl"atteinte de l"objectif poursuivi

par l"entreprise, ce qui se traduira par une fonction à optimiser. b)La détermination de l"optimum mathématiqueà l"aide de certaines techniques propres à 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 latroisième qui porte le nom de

méthode (ou algorithme) du simplexe.

Plan général du polycopié :

(I)Un exemple résolu par voie graphique (II)Résolution de systèmes d"inéquations à 2 ou 3 variables (III)Traduction des problèmes en langage mathématique (IV)Résolution de problèmes de programmation linéaire à 2 variables par voie graphique (V)Résolution de problèmes de programmation linéaire à 3 variables par voie graphique (VI)Résolution de problèmes de programmation linéaire par méthode algébrique (VII)Résolution de problèmes de programmation linéaire par méthode du simplexe 1

2 CHAPITRE 1. INTRODUCTION

1.2 Un exemple résolu par voie graphique

Problème:La direction d"une usine de meubles a constaté qu"il y a des temps morts dans chacun des départements de l"usine. Pour remédier à cette situation, elle décide d"utiliser ces temps morts pour fabri- quer deux nouveaux modèles de bureaux,M1etM2. Les temps de réalisation pour chacun de ces modèles dans les ateliers de sciage, d"assemblage et de sablage ainsi que les temps libres dans chacun de ces ateliers sont donnés dans le tableau ci-dessous. Ces temps représentent le nombre d"heures nécessaires à un homme pouref- fectuer le travail. Les profits que la compagnie peut réaliser pour chacun de ces modèles sont de Fr. 300.- pourM1et de Fr. 200.- pourM2.

M1M2Temps libres

Sciage 1 2 20

Assemblage 2 1 22

Sablage 1 1 12

La direction désire déterminer combien de bureaux de chaquemo- dèle elle doit fabriquer pour maximiser son profit. Solution:Posonsx1le nombre de bureaux du modèleM1etx2le nombre de bureaux du modèleM2. Les temps libres de chaque département imposent des contraintes qu"il faut respecter. La contrainte imposée par les temps libres à l"atelier de sciage : x les autres contraintes sont : x Il s"ajoute à ces contraintes des contraintes denon-négativité puisque le nombre de bureaux ne peut être négatif, on a donc : x

1ě0 etx2ě0

CHAPITRE 1. INTRODUCTION 3

Graphiquement les solutions réalisables sont les points dupolygone convexe de la figure suivante : x1

246810121416182022

x2 2 4 6 8 10

12x1`x2"122x

1`x 2"22 x1`2x2"20 La direction veut maximiser son profit, c"est-à-dire maximiser la fonction : fpx1;x2q "300x1`200x2 Pour chacune de ces solutions, c"est-à-dire pour chacun despoints du polygone convexe, la compagnie fera un profit positif. Si la com- pagnie fabrique trois exemplaires du modèleM1et deux exemplaires du modèleM2, le profit sera : fp3;2q "300¨3`200¨2"1300 (Fr.) Il ne saurait être question de calculer le profit réalisable pour chacun des points du polygone convexe. Pour avoir une vision globale du problème, représentons le profit réalisé par le paramètrep. On a :

300x1`200x2"p

qui représente une famille de droites parallèles. En isolantx2, on obtient : x

2" ´300x1

200`p200

2" ´3

2x1`p200

Il s"agit donc d"une famille de droites de pente´3{2 et dont l"ordon- née à l"origine estp{200. Parmi les droites de cette famille, seules celles ayant des points communs avec le polygone convexe nous inté- ressent. La fonctionfpx1;x2qatteindra sa valeur maximale lorsque l"ordonnée à l"originep{200 de la droite : x

2" ´3

2x1`p200

atteindra sa valeur maximum tout en passant par au moins un des points du polygone convexe.

4 CHAPITRE 1. INTRODUCTION

246810121416182022

x2 2 4 6 8 10

12x1`x2"122x

1`x 2"22 x1`2x2"20 Graphiquement on constate que la droite respectant ces conditions semble être la droite de la famille passant par le point-sommet p10;2q. Le profit est alors : fp10;2q "300¨10`200¨2"3400 (Fr.) Il reste à s"assurer algébriquement des coordonnées du point- sommet en résolvant le système : #2x1`x2"22 x

1`x2"12ñ"x1"10

x 2"2 2 Résolution de systèmes d"inéquations à 2 ou 3 variables

2.1 Inéquations linéaires

Cette partie est consacrée à la présentation des définitionset des propriétés des inéquations, de systèmes d"inéquations linéaires et d"ensemble-solution des systèmes d"inéquations linéaires. Nous ac- corderons de l"importance à ces définitions parce qu"elles sont in- dispensables pour la compréhension des démarches de résolution de problèmes de programmation linéaire. Définition:Uneinéquation linéaireest une expression de la forme : a oùxisont les variables (ou inconnues), lesaisont les coefficients des variables,best une constante etnest le nombre d"inconnues.

Remarque:Une expression de la forme :

1x1`a2x2`a3x3` ¨¨¨ `anxněb

est également une inéquation linéaire àninconnues. Cependant, en multipliant les deux termes de l"inéquation par un nombre négatif, on change également le sens de l"inégalité. On peut donc toujours exprimer une inéquation linéaire sous la forme :quotesdbs_dbs11.pdfusesText_17

[PDF] Programmation linéaire La programmation linéaire peut

Comment fonctionne l’algorithme du simplexe ?

Qu'est-ce que la méthode du simplexe?

Qui a inventé le simplexe ?

Comment fonctionne la communication simplex ?

Programmation linéaire

Jean-Philippe Javet

1x2x3x4x5¨°°3 4 1 0 0 42001 3 0 1 0 24002 2 0 0 1 2600

100 120 0 0 0 0

Table des matières

1 Introduction 1

1.1 Préambule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 1

1.2 Un exemple résolu par voie graphique . . . . . . . . . . . . . . . . .. . . . . . . . . 2

2 Résolution de systèmes d"inéquations à 2 ou 3 variables 5

2.1 Inéquations linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 5

2.2 Système d"inéquations linéaires . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 8

2.3 Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 12

2.3.1 Quelques propriétés des ensembles convexes . . . . . . . .. . . . . . . . . . 12

3 Traduction des problèmes en langage mathématique 15

3.1 Un exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 15

4 Résolution graphique d"un problème à 2 variables 21

4.1 Reprenons l"exemple résolu au premier chapitre . . . . . . .. . . . . . . . . . . . . 21

4.2 Résolution graphique d"un problème de minimisation . . .. . . . . . . . . . . . . . 22

5 Résolution graphique d"un problème à 3 variables 25

5.1 Un exemple à 3 variables . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 25

5.2 Un théorème important . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 29

5.3 Exemple FIL ROUGE (à compléter) . . . . . . . . . . . . . . . . . . . . .. . . . . 29

6 Résolution par méthode algébrique 33

6.1 Variables d"écart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 33

6.2 Coefficients des variables d"écart dans la fonction économique . . . . . . . . . . . . . 34

6.3 Résolution complète de l"exemple FIL ROUGE . . . . . . . . . . .. . . . . . . . . . 36

6.4 Marche à suivre de la méthode algébrique . . . . . . . . . . . . . .. . . . . . . . . 46

6.5 Exemple accompagné(reprise de l"exercice 3.1 déjà étudié en page 17): . . . . . . . . . 47

7 Résolution par la méthode du simplexe 55

7.1 Résolution du problème FIL ROUGE par la méthode du simplexe . . . . . . . . . . 55

7.2 Marche à suivre de la résolution matricielle . . . . . . . . . .. . . . . . . . . . . . . 60

7.3 Les variables dans et hors programme dans la résolution matricielle . . . . . . . . . 61

7.4 Exemple accompagné . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 62

7.5 Quelques remarques pour terminer . . . . . . . . . . . . . . . . . . .. . . . . . . . 66

8 OpenOffice pour résoudre des problèmes de P.L. 67

8.1 Résolution de l"exemple accompagné(cf. pages 47 et 62). . . . . . . . . . . . . . . . 67

8.2 Quelques exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 70

A Quelques éléments de solutions I

Index VIII

Introduction

1.1 Préambule

Plan général du polycopié :

2 CHAPITRE 1. INTRODUCTION

1.2 Un exemple résolu par voie graphique

M1M2Temps libres

Sciage 1 2 20

Assemblage 2 1 22

Sablage 1 1 12

1ě0 etx2ě0

CHAPITRE 1. INTRODUCTION 3

246810121416182022

12x1`x2"122x

300x1`200x2"p

2" ´300x1

200`p200

2" ´3

2x1`p200

2" ´3

2x1`p200

4 CHAPITRE 1. INTRODUCTION

246810121416182022

12x1`x2"122x

1`x2"12ñ"x1"10

2.1 Inéquations linéaires

Remarque:Une expression de la forme :

1x1`a2x2`a3x3` ¨¨¨ `anxněb