Recherche opérationnelle Les démonstrations et les exemples

[PDF] Programmation linéaire et recherche opérationnelle Recherche lim univ reunion staff fred Enseignement Optim doc PL pdf

Simplexe - Méthodes, Techniques et Outils pour le Raisonnement

[PDF] Simplexe Méthodes, Techniques et Outils pour le Raisonnementdossier univ st etienne pem public simplexeSlides pdf

Simplexe - Recherche Opérationnelle et Optimisation Master - LISIC

[PDF] Simplexe Recherche Opérationnelle et Optimisation Master LISIC lisic univ littoral ~verel TEACHING cours pdf

TP Recherche Opérationnelle Méthode du Simplexe - FSTM

[PDF] TP Recherche Opérationnelle Méthode du Simplexe FSTM fstm ac ma deptmath Taik TP RO pdf

Recherche opérationnelle Les démonstrations et les exemples

[PDF] Recherche opérationnelle Les démonstrations et les exemples fsr ac ma cours maths RO SMI Etudiants pdf

LES ÉTAPES DE L ALGORITHME DU SIMPLEXE

[PDF] LES ÉTAPES DE L 'ALGORITHME DU SIMPLEXE hec ca cam rubriques algorithme simplexe pdf

Optimisation linéaire Algorithme du simplexe Phase I

[PDF] Optimisation linéaire Algorithme du simplexe Phase Itransp or epfl ch courses RechOp slides PhaseI pdf

Recherche Opérationnelle - Chapitre 2 : Programmation linéaire

[PDF] Recherche Opérationnelle Chapitre Programmation linéaire tugaut perso math cnrs pdf enseignement RO CM pdf

Recherche opérationnelle et applications - SI Management

[PDF] Recherche opérationnelle et applications SI Management sietmanagement wp content uploads Cours ro pdf

PROGRAMMATION LINEAIRE

nov Recherche Opérationnelle Programmation linéaire ainsi que les indices des variables en base et hors base au cours des () Déterminer la solution optimale par la méthode du simplexe (utiliser les tableaux réduits de

[PDF] recherche opérationnelle simplexe exercices corrigés

[PDF] livre recherche opérationnelle pdf

[PDF] cours et exercices corrigés de recherche opérationnelle+pdf

[PDF] recherche opérationnelle cours maroc

[PDF] inpes

[PDF] methode boscher pdf download

[PDF] méthode boscher cahier de lecture pdf

[PDF] methode boscher en ligne

[PDF] méthode boscher gratuit

[PDF] méthode boscher cahier des sons pdf

[PDF] adjectif pour acrostiche

[PDF] recherche qualitative définition

[PDF] méthode qualitative et quantitative

[PDF] méthode qualitative mémoire

[PDF] méthode quantitative

Recherche op

´erationnelle

Les d ´emonstrations et les exemples seront trait´es en cours

Souad EL Bernoussi

Groupe d"Analyse Num

´erique et Optimisation Rabat

http ://www.fsr.ac.ma/ANO/

Table des mati

`eres

1 Programmation lin

´eaire 2

1.1 Exemple. . . . . . . . . . . . . . . . . . . . . .2

1.2 Forme g

´en´erale d"un programme lin´eaire. . . . .3

1.3 Formes matricielles classiques et convensions. . .3

1.4 Interpr

´etation´economique. . . . . . . . . . . . .4 2 R

´esolution graphique. 5

3 Principes de la r

´esolution alg´ebrique. 5

3.1 Bases , solutions de bases et solutions r

´ealisables.5

3.2 Caract

´erisation alg´ebrique des points extˆemes. . .8

3.3 Propri

3.4 Op

´eration de pivotage. . . . . . . . . . . . . . .10

3.5 Algorithme du simplexe

`a la main. . . . . . . . .10

4 Algorithme du simplexe . 11

4.1 Exemple. . . . . . . . . . . . . . . . . . . . . .12

4.2 Algorithme du simplexe. . . . . . . . . . . . . .13

4.3 Complexit

´e de l"algorithme et´efficacit´e pratique.15 1

4.4 Initialisation de l"algorithme du simplexe. . . . .16

4.4.1 La m

´ethode du grand M. . . . . . . . . .17

5 la notion de dualit

´e. 17

5.1 Th

´eor`emes de dualit´e. . . . . . . . . . . . . . . .17

5.2 Interpr

´etation´economique de la dualit´e. . . . . .20

6 Exercices 22

1 Programmation lin

´eaire

La programmation lin

´eaire est un outil tr`es puissant de la re-

cherche op ´erationnelle. C"est un outil g´en´erique qui peut r´esoudre un grand nombre de probl `emes. En effet, une fois un probl`eme mod ´elis´e sous la forme d"´equations lin´eaires, des m´ethodes as- surent la r

´esolution du probl`eme de mani`ere exacte.

On distingue dans la programmation lin

´eaire, la programmation

lin ´eaire en nombres r´eels, pour laquelle les variables des´equations sont dansIR+et la programmation en nombres entiers, pour la- quelle les variables sont dansIN. Bien entendu, il est possible d"avoir les deux en m

ˆeme temps. Cependant, la r´esolution d"un

probl qu"un probl `eme en nombres r´eels.

Unedesm

lin ´eaires en nombre r´eels est la m´ethode du Simplex. En th´eorie, elle a une complexit ´e non polynomiale et est donc suppos´ee peu efficace. Cependant, en pratique, il s"av `ere au contraire qu"il s"agit d"une bonne m

´ethode.

Un programme lin

´eaire est la maximisation ou la minimisation

d"une fonction lin

´eaire sous des contraintes lin´eaires.

1.1 Exemple.

Voici un petit exemple traitable par la programmation lin ´eaire.Une usine produit deux ciments, rapportant500Dhet700Dhpar tonne.Une tonne du ciment N°1 nec

´essite40minde calcination dans

un four `a chaux et20minde broyage.Une tonne du ciment N°2 nec

´essite30minde calcination dans

un four `a chaux et30minde broyage.3

Le four et l"atelier de broyage sont disponibles6het8hpar jour.Combien de ciment de chaque type peut-on produire par jour pour

maximiser le b

´en´efice?

Ce probl

`eme se mod´elise comme suit :????? ???Max z= 500x1+ 700x2(1) x

1≥0, x2≥0 (4)

(1): est le profit total qui est`a optimiser appel´e fonction objective. (2)et(3)sont des contraintes.(2)est la disponibilit´e du four et (3)est la disponibilit´e du broyeur. (4)est le domaine des variables.

1.2 Forme g

´en´erale d"un programme lin´eaire.

????(1) maxouminn? j=1c jxj (2)?i= 1,...,m:n? j=1a (3)?j= 1,...,n xj≥0 (1): fonction objective. (2):mcontraintes lin´eaires. (3): contraintes de positivit´e.

1.3 Formes matricielles classiques et convensions.

Notons parx= (x1,x2,...,xn)Tle vecteur des variables.b= (b1,b2,...,bm)Tlesecondmembredescontraintes,c= (c1,c2,...,cn)T le vecteur c ˆout ou profit associ´e aux variables etAla matrice m×ndesaij.4 ???Forme canonique : maxz=cx x≥0.,? ???Forme standard : maxz=cx Ax=b x≥0. repr egalit´e s"utilise dans la r´esolution alg´ebrique.Remarque:1.Cesformesneserventqu" `asimplifierlesrepr´esentations th

´eoriques.

Danslar

egalit´ees ou in´egalit´ees. Ainsi n j=1a ijxj=bi??? ??n j=1a n? j=1a n j=1a j=1a ijxj+ei???? variable d"

´ecart.=bi

maxz=-min-z x?R, x=x+-x-avecx+et x-?R+.

1.4 Interpr

´etation´economique.

Un programme lin

´eaire a une int´erpr´etation´economique tr`es large :

Un acteur

´economique qui exercenactivit´es avec des intensit´es x j`a d´et´erminer.

Ces activit

´es utilisentmresources.

La quantit

´eaijde resourcesin´ecessaires pour exerser l"activit´e javec une intensit´e1.5

On connait le profit (en maximisation) et le c

ˆout (en minimisa-

tion). c jcorrespond`a une intensit´e 1 de l"activit´ej. 2 R

´esolution graphique.

On r

´esoud graphiquement le probl`eme suivant :

maxz=x1+ 2x2 x x x

1,x2≥0

matriciellement on am= 2, n= 2, c= (1,2), x= (x1,x2)T, b= (6,3)TetA=?1 1 0 1?

3 Principes de la r

´esolution alg´ebrique.

La r ´esolution alg´ebrique utilise la forme standard, o`uAest une matricem×nde rangm. (P)? ?maxz=cx Ax=b x≥0

3.1 Bases , solutions de bases et solutions r

´ealisables.

Les bases deAsont les matricesm×minversibles extraites de A.

SoitBune base deA.6

On partitionneAsous la forme suivante :A= [B N]( on sup- pose pour faciliter la pr

´esentation que les colonnes de bases sont

lesmpremi`eres colonnes), on partitionne de mˆeme les vecteursx etc. x= (xB,xN)Tetc= (cB,cN)T. Ax=b ??BxB+NxN=b ??xB=B-1b-B-1NxN. z=cx=cBxB+cNxN =cBB-1b+?cN-cBB-1N?xN.

On notec

N=cN-cBB-1N.

Le probl

`eme(P)s"´ecrit alors sous la forme : (P?)? ?maxz=cBB-1b+c NxN x

B=B-1b-B-1NxN

B,xN≥0

C"estla forme canonique par rapport

`a la baseB. x ?est dite solution de basesi elle v

´erifieAx?=betx?=?xB=B-1b

x N= 0?

Si en plusxB≥0alorsx

?est une solution de base r´ealisable. x ?est dite solution r´ealisablesi elle v