[PDF] [PDF] Méthode du simplexe implantation de l'algorithme du

View - Download [PDF] Méthode du simplexe

Previous PDF

Next PDF

Méthode du simplexe

Introduction, définitions et notations préliminaires, théorè

mesfondamentaux, algorithme (primal) du simplexe, déterminationde toutes les solutions optimales et des solutions réalisables"proches" de l'optimum, interpréta

tion géométrique de la méthode du simplexe, solution de base réa lisable initiale, convergence et

implantation de l'algorithme du simplexe, méthode révisée dusimplexe (relation entre deux bases successives, forme réviséede l'algorithme du simplexe), propriétés des multiplicateurs dusimplexe, variante du simplexe

pour problème avec variables bornées.

Introduction

Si un problème de programmation linéaire admet au moins unesolution réalisable optimale finie, il existe au moins une solutionréalisable optimale de base.Puisque le nombre de solutions réal

isables de base est fini, comme le nombre de bases elles-mêmes, et que l'on sait calculer ces solutions, le problème est entièrement réso lu du point de vue théorique.

En pratique, la méthode qui consisterait à

r

ésoudre tous les systèm

es donnant une solution de base est e xclure car elle conduit à u n volume considérable de calculs.Le nombre total de bases pour un système à m

équations et n

inconnues croît rapidement. Si toutes les sous-matrices d'ordre métaient régulières, ce nombre

serait égal à n m

Exemple :

Un problème comportant 10 équations et 20 inconnues, le calcul detoutes les solutions de base pourra

it ainsi exiger la résolution d'env.

250,000 systèmes de dix équations à

d ix inconnues.

Plusieurs de ces calculs seraient ef

fectués inutilement car, certains systèmes d'ordre m n'ont aucune solution , et les solutions comportant des valeurs négatives des variables sont à r ejeter.

La considération des seules solution

s de base ne permet pas de mettre en évidence l'existence d'une solution optimale infinie.

Introduction à

l a méthode du simplexe

La méthode du simplexe est un

e procédure itérative permettant

d'effectuer une exploration dirigée de l'ensemble des solutionsréalisables de base.L'application de la méthode nécessi

te la connaissance d'une solution réalisable de base, au départ.La méthode consiste à calcule r à c haque itération un programme (une solution réalisable) "voisin» de celui qui vient d'être calculé e t "au moins aussi bon» que celui-ci.

On peut aussi s'assurer, moyennant certaines précautions, que lamême base ne puisse jamais apparaît

re dans deux itérations distinctes, ce qui suffit à a ssurer la convergence du procédé.

Intérêt de la méthode du simplexe

Converger vers une solution

de base réalisable optimale si elle existe, vérifier la compatibilité des équations ou la redondance du système savoir si le problème est possible ou non et, dans l'affirmative, trouver une solution réalisable de base initiale mettre en évidence l'absence de so lution réalisable optimale finie.

Définitions et notations préliminaires

Considérons un problème de programmation linéaire sous sa forme standard: Min z = c t x sujet à A x b x 0 où x, c n , b m , A est une matrice de dimension m x n (m n) de rang m.

Lorsque nous considérerons une base

B de ce système, les m vecteurs

colonnes de A constituant une telle base conserveront l'indice decolonne qu'ils avaient originellement dans A, quel que soit l'ordredans lequel ils sont placés pour constituer B.L'ensemble de ces indices rangés dans l'ordre des colonnes de B seradésigné

p ar I = {j 1 , j 2 , ..., j m

L'indice courant de I sera désigné

par s, d'où B = a j 1 , a j 2 , ..., a j m ) = (a s ), s I, I

N, N = {1, 2, ..., n}.

Les (n -

m ) autres colonnes de A seront désignées par : a j , j

J = N \

I Les m variables de base, associées aux colonnes "de base» a s constituent un vecteur colonne à m composantes x B = (x s ), s I.

Les "coûts»

associés constituent un vecteur colonne à m composant e s c B = (c s ), s I.

Les variables restantes, ou variable

s hors base, constituent un vecteur colonne à n - m ) composantes, x R = (x j ), j

J; les coûts associés

constituent le vecteur colonne c R = (c j ), j J.

Le système peut alors s'écrire,

après réarrangement des colonnes de

A et des lignes de x :

Min z = c t B x B + c t R x R

Sujet à

B x B + Rx R = b x B 0 x R 0.

Étant donné

que B -1 existe, on peut exprimer x B en fonction de x R et substituer dans la fonction objective pour obtenir la forme canoniqueassociée à l a base B équivalente au problème initial : Min z c t B (B -1 b - B -1 R x R ) + c t R x R = c t B B -1 b + [c R B -1 R) t c B t x R

Sujet à

B -1 Ax = A x= x B + B -1 R x R B -1 b = b x B 0, x R 0.

La solution de base associée à

B , obtenue en posant x R = 0 peut être

écrite sous la forme

x B =B -1 b = b

La valeur de la forme linéaire z,

pour la solution de base considérée, est: z = c t B B -1 b. L'ensemble des indices de lignes du système est l'ensemble I desindices de lignes de B -1 (ou des indices de colonne de B), et non plus l'ensemble M = {1, 2, ..., m}. Le vecteur [c Rquotesdbs_dbs12.pdfusesText_18

[PDF] Introduction aux méthodes numériques

[PDF] Analyse physico-chimique des sols Agricoles

[PDF] Résumé de méthodes quantitatives II 1 Introduction - Etudiant·e·s

[PDF] Plan du cours Méthodologie de la recherche 1 Introduction 11 Les

[PDF] Matière Métiers Sciences et Technologie 1 1er Licence Tronc

[PDF] lecture de plans et métré - ffc-Constructiv

[PDF] Métrologie - ganil

[PDF] LA MÉTROLOGIE

[PDF] fiche semestre - usthb

[PDF] En microbiologie et immunologie - Département de microbiologie

[PDF] Microbiologie industrielle et Biotechnologie - Groupe IMT

[PDF] Notes de cours de micro-économie en 2ème année du DEUG

[PDF] Microéconomie - fsegn

[PDF] LE MIND-MAPPING

[PDF] modems - cours Yves LESCOP