1 Programmation linéaire
Master d'économie. Cours de M. Desgraupes. Méthodes Numériques. Document 4 : Corrigé des exercices d'optimisation linéaire. 1 Programmation linéaire.
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'
Programmation linéaire Jean-Philippe Javet
Exercice 2.6: Un corrigé peut être vu à votre demande. Exercice 2.7: Indications : ‚ Proposer dans un premier temps un raisonnement
Corrigé : Programmation linéaire II
Corrigé : Programmation linéaire II. Exercice 1. Au quatorzième siècle un Touareg compte gagner un peu d'or en investissant dans des.
Devoir de vacances de Programmation Linéaire
Les exercices se rapportent tous au programme linéaire (P) Néanmoins ils sont Exercice 1 Forme canonique forme standard et dual (2 points).
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.
La Programmation Linéaire : Cours Exercices corrigés et Etude de
20-Nov-2016 est-ce une solution de base ? Exo. 15.6 ? Algorithme du simplexe pour un PL `a 2 variables. Résoudre le programme linéaire suivant avec l' ...
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.
Unité D Programmation linéaire Corrigé
Exercice 1 : Problèmes préliminaires - corrigé. Ces problèmes ont été conçus pour être effectués par les élève à l'aide de feuilles de calcul. Ils.
Programmation linéaire en nombres entiers : la méthode du simplexe
Programme linéaire entier facile : Un PLE qui en oubliant les contraintes d'intégrité
Unité D Programmation linéaire Corrigé - Province of Manitoba
Exercice 5 : Résolution de problèmes de programmation linéaire - corrigé Note à l’enseignant : La dernière partie de chaque problème permet à l’élève de découvrir que la meilleure solution se situe au sommet de la région des solutions réalisables 1 a) x + y 100 b) 10x + 30y 1 500 c)
Programmation Lin aire Cours 1 - u-bordeauxfr
180 CHAPITRE 4 PROGRAMMATION LINÉAIRE Introduction La programmation linéaire constitue l’origine de l’optimisation mathématique moderne Son étude a été menée par George Bernard Dantzig à partir de 1947 L’algorithme du sim-plexe que nous présentons dans ce chapitre est considéré comme un des dix algorithmes les
Programmation linéaire
la programmation linéaire Nous étudierons 3 méthodes pour résoudre les di?é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
Searches related to programmation linéaire exercices corrigés pdf PDF
Chapitre : PROGRAMMATION LINÉAIRE 1ere ES Exercice2 Un artisan fabrique des objets A et des objets B La réalisation d’un objet A demande 30ede matière première et 125 de main-d’œuvre La réalisation d’un objet B demande 70ede matière première et 75 de main-d’œuvre
Qu'est-ce que la programmation lin'eaire?
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 e?cace pour la PL
Quels sont les exercices de programmation linéaire ?
I Exercices de programmation linéaire (1, 2, 3, 4, 5.1 et 5.2) sont dans l’objectif minimum…. 1 Résoudre par la méthode graphique : Max [CA] : 4 xa + 6 xb (1) 6 xa + 5 xb ? 30 (2) 3 xa + 9 xb ? 27 (3) xa ? 5 (4) xb ? 4
Comment résoudre les problèmes de programmation linéaire ?
Re?soudre les proble?mes de programmation line?aire suivants a? l’aide de l’algorithme du simplexe (en introduisant si ne?cessaire des variables artificielles). Max z = 2x ?y s.c. x +y ? 2 y ? 2 x +y ? 4 x, y ? 0 9.2.
Quels sont les avantages de la programmation linéaire?
Ainsi qu`en deuxième lieu (S. HOUNDEDAKO et al, 2014)à utiliser le système HVDC (courant continu à haute tension) pour la synchronisation entre deux réseaux différents aussi que le transport de l`énergie électrique. De ce qui précède la programmation linéaire, nous permet de développer un système pour la transmission et le stockage de
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 4 28A I=( ((2 1-1 3-2 1 -1 0-1) ))AI-1=16 ((2 1 1 4-1 5
2 1 7)
))Etape 3.On trouve le pointx= (3,9,11)et on acA-1
I= 1/6(8,1,13)qui est positif on a
donc atteint l"optimum qui vaut 23 pour ce pointx.Robert Cori,Conception et analyse d"algorithmes 4 29Problèmes posés par l"algorithme du simplexe •Risque de bouclage, car la fonction économique n"augmente pas strictement à chaque étape ?•Comment trouver une valeur initiale? •Algorithme non polynomial
Robert Cori,Conception et analyse d"algorithmes 4
30Initialisation
polyèdre•On ajoute une nouvelle variablexn+1et on conside're :n j=1A debiLe problème initial est réalisable si et seulement si le deuxième admet pour solution optimalexn+1= 0Robert Cori,Conception et analyse d"algorithmes 4 31Complexité
Robert Cori,Conception et analyse d"algorithmes 4
32Algorithme non polynomial
On montre que le système suivant ànvariables donne lieu à un nombre d"étapes voisin de2n:max n? j=110 n-jxj(2 i-1? j=110 33De l"obtention d"une solution
vers l"obtention de l"optimumSi on a un algorithme polynomial qui résout des systèmes d"inéquations linéaires,
alors on peut résoudre un problème d"optimisation linéaire en temps polynomialOn utilise la dualité
maxcx? yA≥c cx≥ybRobert Cori,Conception et analyse d"algorithmes 4 34De l"existence d"une solution
vers l"obtention d"une solutionOn suppose que l"algorithmeAlg(S)donne pour résultattruesiSadmet une
solution etfalsesinonProcédure ReduitVariables(S) •J={1,2,...,n}•Pourj1= 1,2,...nfaire-Si Alg(? j?J\j1A J:=J\j1Robert Cori,Conception et analyse d"algorithmes 4 35Remarques
quotesdbs_dbs22.pdfusesText_28[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
[PDF] livre recherche opérationnelle pdf
[PDF] cours et exercices corrigés de recherche opérationnelle+pdf
[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
