[PDF] Programmation Linéaire Cours 1 : programmes linéaires





Previous PDF Next PDF



Programmation linéaire

Programme linéaire : définition. Définition. Un programme linéaire c'est : Un ensemble de n variables réelles x1



Fondements de la programmation linéaire

linéaire. Généralités. Notations et définitions. Propriétés du problème de programmation linéaire. Théorème fondamental de la programmation linéaire.



Programmation Linéaire Cours 1 : programmes linéaires

Programmation Linéaire. Cours 1 : programmes linéaires modélisation et résolution graphique. F. Clautiaux francois.clautiaux@math.u-bordeaux1.fr.



Programmation linéaire

24 févr. 2011 Définition : Programme linéaire (PL). Dans un programme linéaire on cherche un point x? ? R n qui maximise une fonction objectif linéaire.



Dualité en Programmation Linéaire Algorithmes primal et dual du

Programmation linéaire et dualité. – Définition du dual d'un programme linéaire. – Théorème de dualité forte. • Algorithmes primal et dual du simplexe.



Programmation linéaire et Optimisation

Définition 4.6. On appelle probl`eme d'optimisation linéaire sous forme canonique un probl`eme de la forme maximiser. ?q j=1 cjxj sous les contraintes ?.



Programmation linéaire

Définition 14. Le point de coordonnées (0



Méthodes de points intérieurs pour la programmation linéaire

30 juin 2012 Définition 1.1.1 On appelle un programme linéaire tout programme mathématique o[ la fonction objectif est linéaire et lVensemble des ...



MOD 4.4: Recherche opérationnelle

Programmation Linéaire (PL). Minimisation/ maximisation d'une fonction linéaire sous des con- traintes elles-même linéaires. Définition (programme linéaire).



Optimisation Combinatoire : Programmation Linéaire et Algorithmes

29 sept. 2015 6.2 Définitions et algorithme de Branch&Bound . ... parle de Programme linéaire discret (ou entier ou mixte) (on notera PLNE). Ce cas.



Fondements de la programmation linéaire - Université Laval

La programmation linéaire traite de manière générale d'un problème d'allocation de ressources limitées parmi des activités concurrentes et ce d'une façon optimale La programmation linéaire emploie un modèle mathématique qui décrit le problème réel L'adjectif "linéaire" indique que toutes les fonctions mathématiques de ce



Chapitre 2 Principes généraux de la programmation linéaire

Principes généraux de la programmation linéaire 2 1 Généralités Nousdébutonslechapitreparunthéorèmequigarantiel’existenced’unminimumetaussi d’unmaximumpourunproblèmed’optimisationquelconque Théorème2 1 1 Soitfunefonctioncontinuedé?niesurundomaineKˆRn ferméet bornéalorsfatteintsesvaleursminimaleetmaximale: 9 x 2K f( x



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

Qu'est-ce que la 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

Où se situe une solution de programmation linéaire ?

Si un problème de programmation linéaire a une solution optimale, alors la solution se situe sur la frontière (c’est-à-dire sur les arrêtes et les sommets). De plus, si une frontière contenant une solution optimale a un sommet (ou des sommets), alors la solution se situe sur l’un des sommets.

Quelle est la forme d'une fonction objectif en programmation linéaire?

En programmation linéaire, la fonction objectif est une fonction affine de plusieurs variables à laquelle on peut ajouter une constante. En d’autres termes, pour un problème de programmation linéaire à deux variables, une fonction objectif doit prendre la forme ???? ( ????, ????) = ???? ???? + ???? ???? + ????, pour des constantes ????, ???? et ????.

Quels sont les sommets de la programmation linéaire ?

On a le graphique de trois régions colorées correspondant aux contraintes. La région de chevauchement est le quadrilatère marron avec un sommet à l’origine. Il s’agit de l’ensemble réalisable pour ce problème de programmation linéaire. D’après le graphique donné, on peut dire que les sommets sont ( 0, 0), ( 0, 4), ( 2, 3), ( 3, 0).

  • Past day

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Programmation Lin´eaire

Cours 1 : programmes lin´eaires, mod´elisation et r´esolution graphique

F. Clautiaux

francois.clautiaux@math.u-bordeaux1.fr

Universit´e Bordeaux 1

Bˆat A33

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Motivation et objectif du cours

Introduction `a la programmation lin´eaire

Un outil qui permet de :

•mod´eliser •r´esoudre toute une classe de probl`emes d"optimisation.

Existence de solveurs efficace pour la PL

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Ouvrages de r´ef´erence

V. Chv´atal - Linear Programming, W.H.Freeman, New York, 1983. •R. J. Vanderbei - Linear Programming, Foundations and Extensions,

Springer-Verlag, 2008.

•C. Gu´eret, C. Prins et M. Sevaux - Programmation lin´eaire :65 probl`emes d"optimisation mod´elis´es et r´esolus avec Visual Xpress,

Eyrolles, 2000.

•C. Prins et M. Sevaux - Programmation lin´eaire avec Excel : 55 probl`emes d"optimisation mod´elis´es pas `a pas et r´esolus avec Excel,

Eyrolles, 2011.

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Sommaire

Introduction par l"exemple

Exemple 1 : Production

Exemple 2 : Transport

Exemple 3 : Planification

Programme lin´eaire

R´esolution graphique

Points extrˆemes

Forme standard, bases

Bilan ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Probl`eme de production

Un fabricant produit 2 types de yaourts `a la fraise A et B `a partir de Fraise, de Lait et de Sucre. Chaque yaourt doit respecter les proportions suivantes de mati`eres premi`eres. AB

Fraise21

Lait12

Sucre01

On dispose de 800 Kg de Fraises, 700 Kg de Lait et 300 Kg de sucre. La vente de 1 Kg de yaourts A et B rapporte respectivement 4eet 5e.

Le fabricant cherche `a maximiser son profit.

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Que cherche-t-on `a optimiser? •Quelles sont les contraintes du probl`eme? ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Seules valeurs non constantes : les quantit´es de yaourtsAetB produites •On parle devariables •On les noteraxAetxB •Que cherche-t-on `a optimiser? •Quelles sont les contraintes du probl`eme? ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Variables :xAetxB •Que cherche-t-on `a optimiser? •Le profitz •Calcul´e `a partir dexAetxB •On parle defonction objectif •z= 4xA+ 5xB •Quelles sont les contraintes du probl`eme? ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Variables :xAetxB •Que cherche-t-on `a optimiser? •maxz= 4xA+ 5xB •Quelles sont les contraintes du probl`eme? •Premi`ere contrainte : 800 Kg de fraises disponibles •la quantit´e utilis´ee d´epend de la production : 2xA+xB ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Variables :xAetxB •Que cherche-t-on `a optimiser? •maxz= 4xA+ 5xB •Quelles sont les contraintes du probl`eme? x x ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Variables :xAetxB •Que cherche-t-on `a optimiser? •maxz= 4xA+ 5xB •Quelles sont les contraintes du probl`eme? x x x

A,xB≥0

positivit´e! ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mon premier programme lin´eaire

max4xA+ 5xB x x x

A,xB≥0

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Probl`eme de transport

Approvisionner au moindre coˆut les clients `a partir des usines.

Usines (i?I)BordeauxBiarritzToulouse

Productions (pi)251520

Clients (j?J)PauBayonneBordeauxLibourne

Demandes (dj)2012914

Prix/unit´e (ci,j)PauBayonneBordeauxLibourne

Bordeaux261904

Biarritz1222024

Toulouse19302428

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x i,j: quantit´e transport´ee dei`aj ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x i,j: quantit´e transport´ee dei`aj •Objectif :

Minimiser?

i?I? j?Jci,jxi,j ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x i,j: quantit´e transport´ee dei`aj •Objectif :

Minimiser?

i?I? j?Jci,jxi,j •Contraintes :? i?Ixi,j=dj,?j?J(Demandes `a satisfaire) x i,j≥0,?i?I,j?J ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Probl`eme de planification

Planifier la production d"articles `a moindre coˆut pour les 4 prochains mois. Production maximale normale : 1200 articles / mois Production maximale en heure sup : 400 articles / mois

Surcoˆut heures sup : 7 euros / article

Stockage : 3 euros / article / mois

mois 1mois 2mois 3mois 4

Demandes900110017001300

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x t: production normale en p´eriodet= 1,...,4 y t: production en heure sup en periodet= 1,...,4 s t: stock en fin de p´eriodet= 1,...,3 ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x t: production normale en p´eriodet= 1,...,4 y t: production en heure sup en periodet= 1,...,4 s t: stock en fin de p´eriodet= 1,...,3 •Objectif :

Minimiser 7?t=4

t=1yt+ 3?t=3 t=1st •Contraintes : x

1+y1= 900+s1

s

1+x2+y2= 1100+s2

s

2+x3+y3= 1700+s3

s

3+x4+y4= 1300

s t≥0,t= 1, ...,3 ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Sommaire

Introduction par l"exemple

Programme lin´eaire

R´esolution graphique

Points extrˆemes

Forme standard, bases

Bilan ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

R`egles de r´e´ecriture (1)

Toute contrainte d"´egalit´e peut s"´ecrire comme deux in´egalit´es : n i=1a ixi=b≡? n i=1a ixi≥b≡n? Tout probl`eme de minimisation peut s"´ecrire comme un probl`eme de maximisation : max n? i=1c ixi≡minn? i=1-cixi ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan Ecriture g´en´erale d"un programmation lin´eaire On peut ´ecrire ainsi un programme lin´eaire avecnvariables x

1,...,xnetmcontraintes.

max ?ni=1cixi x i?R,(i= 1,...,n) •Lin´earit´e :Objectif et contraintes sont des fonctions lin´eaires des variables de d´ecision (les coefficientscietaijdes variables sont constants) •Continuit´e :Les variables peuvent prendre n"importe quelle valeur r´eelle respectant les contraintes linaires ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan Exemples simples de programmes non lin´eaires (1) min?ni=1xixi x i?R,(i= 1,...,n) min ?ni=1xi x i?

N,(i= 1,...,n)

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilanquotesdbs_dbs16.pdfusesText_22
[PDF] programmation lineaire methode simplexe

[PDF] programmation linéaire recherche opérationnelle

[PDF] interprétation droite de henry

[PDF] principe droite de henry

[PDF] exercice corrigé droite de henry

[PDF] courbe de henry excel

[PDF] droite de henry pdf

[PDF] programmation linéaire exercices corrigés pdf

[PDF] programmation linéaire exercices corrigés

[PDF] programmation linéaire simplexe

[PDF] recherche opérationnelle programmation linéaire exercices corrigés pdf

[PDF] exercices recherche operationnelle

[PDF] theme astral chinois complet gratuit interpretation

[PDF] cours recherche opérationnelle methode de simplexe

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