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 et Optimisation
On consid`ere le cas d'un fabricant d'automobiles qui propose deux mod`eles `a la vente des grosses voitures et des petites voitures.
Introduction à la programmation linéaire
? On a x1 = x2 = 0. ? Solution de base réalisable : {2xA + xB = 800} ? {xA + 2xB = 700}. Cours - Introduction à la programmation linéaire. LAAS. CNRS. Page
Leçon 1 Programmation linéaire
Un programme linéaire (PL) est un probl`eme qui consiste `a maximiser sur R d une fonction linéaire sous des contraintes linéaires. max x1 + x2.
Optimisation Combinatoire : Programmation Linéaire et Algorithmes
29 sept. 2015 1.4 Programme non-linéaire. 13. ZIB. Un des objectifs de ce cours est de comprendre comment et dans quels cas ces.
Programmation Linéaire
Ce cours expliquer la notion de programmation linéaire et son utilité dans la Ceci complète les transformations sur les équations ; la solution de base ...
Dualité en Programmation Linéaire Algorithmes primal et dual du
minimisation maximisation. Fonction objectif min. Fonction objectif max. Second membre. Fonction objectif. A matrice des contraintes.
Programmation linéaire
Programmation linéaire. 1. Le problème un exemple. 2. Le cas b = 0. 3. Théorème de dualité. 4. L'algorithme du simplexe. 5. Problèmes équivalents.
Cours 3: Programmation linéaire
Cours 3: Programmation linéaire. • Position du probl`eme. • Dualité. • Dégénérescence et terminaison de l'algorithme. • Algorithme du simplexe générique.
COURS DE RECHERCHE OPERATIONNELLE
Ufr des Sciences Economues et de Gestion. COURS DE RECHERCHE OPERATIONNELLE. ECUE 1 : PROGRAMMATION LINEAIRE. NOTES DE COURS. PAR. Dr Yao Silvère KONAN.
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
Chapitre 2 Programmation linéaire - univ-rennes1fr
L’image de l’application linéaire dé?nie par la multiplication par Aest le sous-espace vectoriel engendré par ses vecteurs colonne Le rang de la matrice Aest la dimension de cette image Cette dimension ne peut pas excéder la dimension de l’espace d’arrivée (i e lenombredelignesdelamatriceici3)nilenombredevecteurscolonne(ici5;la
Institut de Mathématiques de Bordeaux
Institut de Mathématiques de Bordeaux
Searches related to cours complet de programmation linéaire PDF
Programmation linéaire en nombre entiers : toutes les ariablesv sont entières Résoudre un PLNE est un problème NP-complet Dé nition Etant donné un P L en nombre entiers on appelle P L relaxé le P L privé de ses ontrcaintes d'intégrité àdc les variables sont elérles Théorème Soit w
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
Comment choisir la solution optimale d’un problème d’optimisation linéaire ?
La solution de base pour le choixfa1; a3gsera(0;0;1).De même, la solution de base pour le choixfa2; a3gsera(0;0;1).Il est facile de voir qu’il y a qu’un seul sommet. Voici le théorème fondamental qui permet d’a?rmer que la solution optimale d’un problèmed’optimisation linéaire est toujours atteinte en un sommet de la région admissible.
Comment écrire un problème d’optimisation linéaire avec des contraintes d’inégalité ?
Nous savons que tout problème d’optimisation linéaire avec des contraintes d’inégalité peuts’écrire sous la forme canonique ayant des contraintes d’égalité (en ajoutant des variablesd’écarts ou de surplus). Donc, il su?t de ne considérer que des problèmes avec des contraintesd’égalité 0 oùAest une matrice de formatmnetb2Rm.
Comment calculer un système linéairement indépendant ?
Théorème2.2.1Un pointx 2K(x6= 0) est un sommet deKsi et seulement sifajgj2I+(x) forme un système linéairement indépendant. Supposons le contraire, i.e. fajgj2I+(x) est linéairement dépendant. Ceci signi?e qu’il existedeswj non tous nuls tel que Pourj 2=I+(x), on posewj = 0.
1 Programmation linéaire
1.Le problème, un exemple.
2.Le casb= 03.Théorème de dualité
4.L"algorithme du simplexe
5.Problèmes équivalents
6.Complexité de l"Algorithme
Robert Cori,Conception et analyse d"algorithmes 4
2Position du problème
SoitAune matrice de réels de taillem×n,betcdeux vecteurs de réels de taillemet nrespectivement. Résoudre le problème linéaire défini parA,b,cconsiste à trouver des réelsx1,x2,...,xnsatisfaisant lesminéquations (une pour chaqueientre 1 et m) :n j=1A n j=1c jxj(2)Robert Cori,Conception et analyse d"algorithmes 4 3Problème concret
Un fleuriste dispose de 50 lys, 80 roses et 80 jonquilles. Il réalise ou bien des bouquets qu"il vend 40 euros comprenant 10 lys, 10 roses et 20 jonquilles, ou bien des bouquets dont il tire un prix de 50 euros qui comprennent 10 lys, 20 roses et 10 jonquilles. Comment le fleuriste doit il former les bouquets pour réaliser une recette maximale ?Modélisation mathématique10x: nombre de bouquets du premier type,
10y: nombre de bouquets du deuxième type.?
max4x+ 5yRobert Cori,Conception et analyse d"algorithmes 4 4Remarques
On appelle souvent
?nj=1cjxjlafonction économiqueLesAi,j,bi,cjne sont pas nécessairement positifs. On peut remplacer la recherche
1.Il n"existe pas dexjsatisfaisant les inéquations (1)2.Parmi lesxjsatisfaisant les inéquations la somme (2) peut être aussi grande que
l"on veut3.Il existe plusieurs valeurs donnant l"optimum4.Il existe une et une seule valeur donnant l"optimum
Robert Cori,Conception et analyse d"algorithmes 4
5Interprétation économique
•x jnombre de produits finis de typejfabriqués•a i,jquantité de matière première de typeinécessaire pour fabriquer un produit de typej•b iquantité de matière première de typeidisponible•cjbénéfice réalisé par produit fini de typejRobert Cori,Conception et analyse d"algorithmes 4
6 Sur l" exemple très simple du fleursite il y a deux variablesxety, les contraintes sont? max4x+ 5yRobert Cori,Conception et analyse d"algorithmes 4 7020 16 22
23
Robert Cori,Conception et analyse d"algorithmes 4
8Résultats géomètriques
•L"ensemble desxsatisfaisantforme un polyèdre convexe•Unsommetdu polyèdre est l"intersection denhyperplans•Si le polyèdre est borné, il existe nécessairement un sommet qui réalise l"optimum
•Un sommet réalise l"optimum si et seulement si ses voisins donnent une valeur plus faible à la fonction économiqueRobert Cori,Conception et analyse d"algorithmes 4 9Trois situations possibles
1.Les contraintes sont impossibles à satisfaire
100Robert Cori,Conception et analyse d"algorithmes 4
11Méthode du Simplexe
1.Partir d"un sommet quelconqueP0du polytope,i :=02.Tant qu"il existe un voisinQdePiqui améliore la fonction économique faireP
i+1=Q;i++3.Si on trouve une direction pour laquelle la fonction augmente indéfiniment :ArrêtA préciser :
•Terminaison •Que faire si voisin égal? •Comment trouver si cela augmente indéfiniment?Robert Cori,Conception et analyse d"algorithmes 4
12Casb= 0Situation particulière:
•Il existe toujours un point qui satisfait les contraintes •On a soit un optimum infini soit un optimum nul, car s"il existe unusatisfaisant 13 •Sicn"est pas combinaison linéaire des lignes deA, alors il existeutel quecu >0etAu= 0ainsi l"optimum est infini•Sics"exprime comme une combinaison des lignes deAalors ou bien il existe unu
yA=c?cu=yAu, y≥0?cuetAuont même signeRobert Cori,Conception et analyse d"algorithmes 4 14 ThéorèmeSi l"un des deux problèmes suivants 15Algorithme du simplexe simplifié
SOITIUN ENSEMBLE D"INDICES QUI FORME UNE BASE DE L"ESPACE ENGENDRÉ PAR LES LIGNES DEA,EXPRIMERcCOMME UNE COMBINAISON LINÉAIRE DESLIGNESLi, i?I.c=?
i?Iy iLiTANT QU"IL EXISTEyi<0FAIRESOIThLE PLUS PETIT INDICE TEL QUEyh<0ET SOITuLE VECTEUR DERnTEL EXPRIMERcCOMME PLUS HAUT.Robert Cori,Conception et analyse d"algorithmes 4 16Preuve de terminaison (1)
Ensemble d"indicesItel queL
ipouri?Iest une base de l"espace engendré par les lignes. c=y1Li1+y1Li1+······+ykLik•Si pour touti?Ion ay i≥0c"est fini. •Sinon on prendhle plus petit tel quey h<0Robert Cori,Conception et analyse d"algorithmes 4 17Preuve de terminaison (2)
Vecteurutel queL
iu= 0pouri?=h?IetL hu=-1.On a toujours
cu=-yh>0•Si pour touti /?Ion aL •Sinon on prendsle plus petitidans{1,2,...,m}tel queL su >0et on pose I ?=I-h+s•On vérifie queI ?définit les indices de lignes qui forment une base de l"espace engendré par celles-ci.Robert Cori,Conception et analyse d"algorithmes 4 18Preuve de terminaison (3)
On suppose que l"algorithme boucle
On retrouve deux fois le même ensembleI; soitrl"indice le plus grand qui sort deIentre les deux étapes
On remarque aussi que c"est le plus grand qui entre!.On noteI
pla valeur deIavant quersorte etI pla valeur deIaprès querentre I→...→Ip→ ······ →Iq→...→I•Soitu ?la valeur deuavant construction deI q. •AlorsL ru?est le seulL iu?non nul pouri?Iqet: cu ?>0Robert Cori,Conception et analyse d"algorithmes 4 19Preuve de terminaison (4)
On suppose que l"algorithme boucle ...
c=? i?Ipy iLiPouri?Ip,i < r, on ay i>0On remarque aussi que l"on a aussi pour ces valeurs dei,L iu?<0car au moment de rentrer dansI q,rest le plus petit parmi{1,2,...,m}tel queL ru?>0Robert Cori,Conception et analyse d"algorithmes 4 20Preuve de terminaison (5)
On suppose que l"algorithme boucle ...
cu i?Ipy iLiu?cu iPet dansI
qdoncL iu?= 0ainsi : cu iSystème d"inéquations
?u=b•Ce qui est équivalent à:yA 22Théorème de dualité
Si l"un des deux problèmes suivants
(D) min{by|y≥0, yA=c}admet une solution finie alors il en est de même pour l"autre et on a : 23Interprétation économique du dual
RemarqueOn augmente la quantité de matière première d"une valeur marginaleti(petit), l"augmentation du gain est alorsyitioùyiest la valeur qui rend optimum le
problème dual.Robert Cori,Conception et analyse d"algorithmes 4 24Algorithme du simplexe
SOITIUN SOUS-ENSEMBLE DEnÉLÉMENTS DE{1,2,...,m}ET SOITxi?IyiLiETyj= 0POURj /?I.SIy≥0ALORSxEST SOLUTION DU SYSTÈME.SINON SOITiLE PLUS PETIT INDICE TEL QUEyi<0ET SOITUiLA COLONNE
CORRESPONDANTE DEA-1
I;DÉTERMINER POUR CHAQUE LIGNELjDE LA
jSOIT MINIMUM PARMI LESvjPOSITIFS. ON POSE ALORSI:=I- {i} ? {j}ET ON CALCULEx,INTERSECTION DES HYPERPLANS CORRESPONDANTS.Robert Cori,Conception et analyse d"algorithmes 4 25Calcul effectif d"un exemple
On considère?
x I=( ((-1 0 0 0 0-12 1-1)
))AI-1=( ((-1 0 0 2-1 10-1 0)
))Robert Cori,Conception et analyse d"algorithmes 4 26Etape 1.
cA I-1= (1,-2,1)On supprime la ligne2la colonne correspondante dansAI-1est :( ((0 -1 -1) ))Le produit de cette colonne par l"opposée de chacune des lignes de la matriceA donne0,-1,0,-1,-2,1.I={1,3,6}A I=( ((-1 0 0 2 1-1 -1 0-1) ))AI-1=( ((-1 0 0 1 1 1 -1 0-1) ))Robert Cori,Conception et analyse d"algorithmes 4 27Etape 2.
Le pointxest égal à(0,12,8)cA
I-1= (-1,1,2)On supprime la ligne1, la colonne correspondante est alors( ((-1 1 -1) ))Le produit de cette colonne par l"opposée de chacune des lignes de la matriceA donne-1,-1,0,6,3,0. b j-Ljxv jqui vaut 3 pourj= 4et9.66pourj= 5on retient donc la ligne4et on obtient I= 3,4,6.Robert Cori,Conception et analyse d"algorithmes 4quotesdbs_dbs33.pdfusesText_39[PDF] programmation linéaire définition
[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
