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-1Cours 3: Programmation lineairePosition du problemeDualite.Degenerescence et terminaison de l'algorithmeAlgorithme du simplexe generiqueGilles Schaeer INF-550-3: Programmation lineaire
2-1Cours 3: Programmation lineairePosition du problemeDualite.Degenerescence et terminaison de l'algorithmeAlgorithme du simplexe generiqueGilles Schaeer INF-550-3: Programmation lineaire
3-1Un probleme de programmation lineaireDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem,un vecteurc= (c1;:::;cn)de taillen.Probleme:T rouveru np ointx= (x1;:::;xn)quisatisfait lesmcontraintesai;1x1+:::+ai;nxnbi,et maximise le produitcx=c1x1+:::+cnxn.Gilles Schaeer INF-550-3: Programmation lineaire
3-2Un probleme de programmation lineaireDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem,un vecteurc= (c1;:::;cn)de taillen.Probleme:T rouveru np ointx= (x1;:::;xn)quisatisfait lesmcontraintesai;1x1+:::+ai;nxnbi,et maximise le produitcx=c1x1+:::+cnxn.Reformulation matricielle:on cherche max(cxjAxb).Gilles Schaeer INF-550-3: Programmation lineaire
3-3Un probleme de programmation lineaireDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem,un vecteurc= (c1;:::;cn)de taillen.Probleme:T rouveru np ointx= (x1;:::;xn)quisatisfait lesmcontraintesai;1x1+:::+ai;nxnbi,et maximise le produitcx=c1x1+:::+cnxn.Reformulation matricielle:on cherche max(cxjAxb).Gilles Schaeer INF-550-3: Programmation lineaireRemarque:Les ai;j,bietcipeuvent ^etre negatifs, on peut donc
modeliser des contraintesou=et chercherminau lieu demax.4-1Un exemple bateau: le
euristeDonnee.En sto ck:50 lys, 80 roses, 80 jonquilles. Composition des bouquets au catalogue:10 lys, 10 roses, 20 jonquilles: 4 euros10 lys, 20 roses, 10 jonquilles: 5 eurosGilles Schaeer INF-550-3: Programmation lineaire
4-2Un exemple bateau: le
euristeDonnee.En sto ck:50 lys, 80 roses, 80 jonquilles. Composition des bouquets au catalogue:10 lys, 10 roses, 20 jonquilles: 4 euros10 lys, 20 roses, 10 jonquilles: 5 eurosProblemeQue lsb ouquetsp reparersi on est assur ede tout vendre ? Gilles Schaeer INF-550-3: Programmation lineaire
4-3Un exemple bateau: le
euristeDonnee.En sto ck:50 lys, 80 roses, 80 jonquilles. Composition des bouquets au catalogue:10 lys, 10 roses, 20 jonquilles: 4 euros10 lys, 20 roses, 10 jonquilles: 5 eurosProblemeQue lsb ouquetsp reparersi on est assur ede tout vendre ? xbouquetsybouquetsGilles Schaeer INF-550-3: Programmation lineaire
4-4Un exemple bateau: le
euristeDonnee.En sto ck:50 lys, 80 roses, 80 jonquilles. Composition des bouquets au catalogue:10 lys, 10 roses, 20 jonquilles: 4 euros10 lys, 20 roses, 10 jonquilles: 5 eurosProblemeQue lsb ouquetsp reparersi on est assur ede tout vendre ? xbouquetsybouquetsContraintes:sur les lys: 10x+ 10y50sur les roses:10x+ 20y80sur les jonquilles:20x+ 10y80Gilles Schaeer INF-550-3: Programmation lineaire
4-5Un exemple bateau: le
euristeDonnee.En sto ck:50 lys, 80 roses, 80 jonquilles. Composition des bouquets au catalogue:10 lys, 10 roses, 20 jonquilles: 4 euros10 lys, 20 roses, 10 jonquilles: 5 eurosProblemeQue lsb ouquetsp reparersi on est assur ede tout vendre ? xbouquetsybouquetsContraintes:sur les lys: 10x+ 10y50sur les roses:10x+ 20y80sur les jonquilles:20x+ 10y80x0y0Gilles Schaeer INF-550-3: Programmation lineaire
4-6Un exemple bateau: le
euristeDonnee.En sto ck:50 lys, 80 roses, 80 jonquilles. Composition des bouquets au catalogue:10 lys, 10 roses, 20 jonquilles: 4 euros10 lys, 20 roses, 10 jonquilles: 5 eurosProblemeQue lsb ouquetsp reparersi on est assur ede tout vendre ? xbouquetsybouquetsContraintes:sur les lys: 10x+ 10y50sur les roses:10x+ 20y80sur les jonquilles:20x+ 10y80Fonction economique a maximiser:max(4x+ 5y).x0y0Gilles Schaeer INF-550-3: Programmation lineaire
4-7Un exemple bateau: le
euristeDonnee.En sto ck:50 lys, 80 roses, 80 jonquilles. Composition des bouquets au catalogue:10 lys, 10 roses, 20 jonquilles: 4 euros10 lys, 20 roses, 10 jonquilles: 5 eurosProblemeQue lsb ouquetsp reparersi on est assur ede tout vendre ? xbouquetsybouquetsContraintes:sur les lys: 10x+ 10y50sur les roses:10x+ 20y80sur les jonquilles:20x+ 10y80Fonction economique a maximiser:max(4x+ 5y).x0y0xy01123401234Gilles Schaeer INF-550-3: Programmation lineaire
4-8Un exemple bateau: le
euristeDonnee.En sto ck:50 lys, 80 roses, 80 jonquilles. Composition des bouquets au catalogue:10 lys, 10 roses, 20 jonquilles: 4 euros10 lys, 20 roses, 10 jonquilles: 5 eurosProblemeQue lsb ouquetsp reparersi on est assur ede tout vendre ? xbouquetsybouquetsContraintes:sur les lys: 10x+ 10y50sur les roses:10x+ 20y80sur les jonquilles:20x+ 10y80Fonction economique a maximiser:max(4x+ 5y).x0y0xy0112340123416222320Gilles Schaeer INF-550-3: Programmation lineaire
4-9Un exemple bateau: le
euristeDonnee.En sto ck:50 lys, 80 roses, 80 jonquilles. Composition des bouquets au catalogue:10 lys, 10 roses, 20 jonquilles: 4 euros10 lys, 20 roses, 10 jonquilles: 5 eurosProblemeQue lsb ouquetsp reparersi on est assur ede tout vendre ? xbouquetsybouquetsContraintes:sur les lys: 10x+ 10y50sur les roses:10x+ 20y80sur les jonquilles:20x+ 10y80Fonction economique a maximiser:max(4x+ 5y).x0y0xy0112340123416222320cGilles Schaeer INF-550-3: Programmation lineaire
4-10Un exemple bateau: le
euristeDonnee.En sto ck:50 lys, 80 roses, 80 jonquilles. Composition des bouquets au catalogue:10 lys, 10 roses, 20 jonquilles: 4 euros10 lys, 20 roses, 10 jonquilles: 5 eurosProblemeQue lsb ouquetsp reparersi on est assur ede tout vendre ? xbouquetsybouquetsContraintes:sur les lys: 10x+ 10y50sur les roses:10x+ 20y80sur les jonquilles:20x+ 10y80Fonction economique a maximiser:max(4x+ 5y).x0y0xy0112340123416222320cLorsqu'on a les contraintesxi0on peut toujours penser en termes
economiques: produits nis, matieres premieres, benece.Gilles Schaeer INF-550-3: Programmation lineaire
5-1Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Gilles Schaeer INF-550-3: Programmation lineaire5-2Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).Gilles Schaeer INF-550-3: Programmation lineaire5-3Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).Gilles Schaeer INF-550-3: Programmation lineaire5-4Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).Gilles Schaeer INF-550-3: Programmation lineaire5-5Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).Gilles Schaeer INF-550-3: Programmation lineaire5-6Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).Gilles Schaeer INF-550-3: Programmation lineaire5-7Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).Gilles Schaeer INF-550-3: Programmation lineaire5-8Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).L'ensemble desxsatisfaisantAxb forme un p olyhedrecon vexePGilles Schaeer INF-550-3: Programmation lineaire5-9Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).L'ensemble desxsatisfaisantAxb forme un p olyhedrecon vexePeventuellement videGilles Schaeer INF-550-3: Programmation lineaire5-10Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).L'ensemble desxsatisfaisantAxb forme un p olyhedrecon vexePeventuellement videGilles Schaeer INF-550-3: Programmation lineaire5-11Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).L'ensemble desxsatisfaisantAxb forme un p olyhedrecon vexePeventuellement videou non borneGilles Schaeer INF-550-3: Programmation lineaire5-12Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).L'ensemble desxsatisfaisantAxb forme un p olyhedrecon vexePLe vecteurcindique la direction danslaquelle on optimise:max(cxjx2P)eventuellement videou non borneGilles Schaeer INF-550-3: Programmation lineaire
5-13Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).L'ensemble desxsatisfaisantAxb forme un p olyhedrecon vexePLe vecteurcindique la direction danslaquelle on optimise:max(cxjx2P)eventuellement videou non borneGilles Schaeer INF-550-3: Programmation lineaireL'optimum peut ^etre a l'inni.
5-14Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).L'ensemble desxsatisfaisantAxb forme un p olyhedrecon vexePLe vecteurcindique la direction danslaquelle on optimise:max(cxjx2P)eventuellement videou non borneGilles Schaeer INF-550-3: Programmation lineaireL'optimum peut ^etre a l'inni.
5-15Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).L'ensemble desxsatisfaisantAxb forme un p olyhedrecon vexePLe vecteurcindique la direction danslaquelle on optimise:max(cxjx2P)eventuellement videou non borneS'il est ni, il est atteint en un sommet.C'est toujours le cas siPest borne.Gilles Schaeer INF-550-3: Programmation lineaireL'optimum peut ^etre a l'inni.
5-16Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).L'ensemble desxsatisfaisantAxb forme un p olyhedrecon vexePLe vecteurcindique la direction danslaquelle on optimise:max(cxjx2P)eventuellement videou non borneGilles Schaeer INF-550-3: Programmation lineairePar convexite, un sommet est optimum si
et seulement si il est meilleur que ses voisins.5-17Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,
un vecteurb= (b1;:::;bm)de taillem, un vecteurc= (c1;:::;cn)de taillen.Chaque equationai;1x1+:::+ai;nxnbicoupe l'espace en 2, le long d'un l' hyperplan no rmalau vecteur Li= (ai;1;:::;ai;n).L'ensemble desxsatisfaisantAxb forme un p olyhedrecon vexePLe vecteurcindique la direction danslaquelle on optimise:max(cxjx2P)eventuellement videou non borneGilles Schaeer INF-550-3: Programmation lineairePar convexite, un sommet est optimum si
et seulement si il est meilleur que ses voisins.optimum local)optimum global6-1Cours 3: Programmation lineairePosition du problemeDualite.Degenerescence et terminaison de l'algorithmeAlgorithme du simplexe generiqueGilles Schaeer INF-550-3: Programmation lineaire
7-1Gilles Schaeer INF-550-3: Programmation lineaireL'algorithme du simplexe (casgenerique)Algorithme du simplexe, premier essaiInitialiserxavec un sommet quelconque deP
7-2Gilles Schaeer INF-550-3: Programmation lineaireL'algorithme du simplexe (casgenerique)Algorithme du simplexe, premier essaiInitialiserxavec un sommet quelconque dePTant qu'on a pas trouve une direction innie oucxcroit,
et qu'il existex0voisin dexaveccx0> cx, fairex:=x0.7-3Gilles Schaeer INF-550-3: Programmation lineaireL'algorithme du simplexe (casgenerique)Algorithme du simplexe, premier essaiInitialiserxavec un sommet quelconque dePTant qu'on a pas trouve une direction innie oucxcroit,
et qu'il existex0voisin dexaveccx0> cx, fairex:=x0.Remarques:Glouton...7-4Gilles Schaeer INF-550-3: Programmation lineaireL'algorithme du simplexe (casgenerique)Algorithme du simplexe, premier essaiInitialiserxavec un sommet quelconque dePTant qu'on a pas trouve une direction innie oucxcroit,
et qu'il existex0voisin dexaveccx0> cx, fairex:=x0.Remarques:Glouton... Qu'est ce qu'un sommet, un voisin ?7-5Gilles Schaeer INF-550-3: Programmation lineaireL'algorithme du simplexe (casgenerique)Algorithme du simplexe, premier essaiInitialiserxavec un sommet quelconque dePTant qu'on a pas trouve une direction innie oucxcroit,
et qu'il existex0voisin dexaveccx0> cx,fairex:=x0.Remarques:Glouton... Qu'est ce qu'un sommet, un voisin ?donne parI=findices desnequationsgSommet = intersection denhyperplans,
7-6Gilles Schaeer INF-550-3: Programmation lineaireL'algorithme du simplexe (casgenerique)Algorithme du simplexe, premier essaiInitialiserxavec un sommet quelconque dePTant qu'on a pas trouve une direction innie oucxcroit,
et qu'il existex0voisin dexaveccx0> cx,fairex:=x0.Remarques:Glouton... Qu'est ce qu'un sommet, un voisin ?donne parI=findices desnequationsgSommet = intersection denhyperplans,Voisin = partagen1equations
7-7Gilles Schaeer INF-550-3: Programmation lineaireL'algorithme du simplexe (casgenerique)Algorithme du simplexe, premier essaiInitialiserxavec un sommet quelconque dePTant qu'on a pas trouve une direction innie oucxcroit,
et qu'il existex0voisin dexaveccx0> cx,fairex:=x0.Remarques:Glouton... Qu'est ce qu'un sommet, un voisin ?donne parI=findices desnequationsgSommet = intersection denhyperplans,Voisin = partagen1equations)un sommet an(mn)voisins ?n= 2m= 5
7-8Gilles Schaeer INF-550-3: Programmation lineaireL'algorithme du simplexe (casgenerique)Algorithme du simplexe, premier essaiInitialiserxavec un sommet quelconque dePTant qu'on a pas trouve une direction innie oucxcroit,
et qu'il existex0voisin dexaveccx0> cx,fairex:=x0.Remarques:Glouton... Qu'est ce qu'un sommet, un voisin ?donne parI=findices desnequationsgSommet = intersection denhyperplans,Voisin = partagen1equations)un sommet an(mn)voisins ?n= 2m= 5On veut un voisin qui soit un sommet deP.
7-9Gilles Schaeer INF-550-3: Programmation lineaireL'algorithme du simplexe (casgenerique)Algorithme du simplexe, premier essaiInitialiserxavec un sommet quelconque dePTant qu'on a pas trouve une direction innie oucxcroit,
et qu'il existex0voisin dexaveccx0> cx,fairex:=x0.Remarques:Glouton... Qu'est ce qu'un sommet, un voisin ?donne parI=findices desnequationsgSommet = intersection denhyperplans,Voisin = partagen1equations)un sommet an(mn)voisins ?n= 2m= 5On veut un voisin qui soit un sommet deP.Le long d'une ar^ete (In fig), seul le premier
voisin rencontre est dansP: comparer les distances.8-1Gilles Schaeer INF-550-3: Programmation lineaireDetecter les directions innies oucxcro^t.Si le polyhedre n'est pas borne,cxpeut cro^tre indeniment:cs'ecritc=P
iyiLiavec lesyi0Lemme:les 2 cas s uivantss'excluent mutuellement: il existeutqcu >0etAu08-2Gilles Schaeer INF-550-3: Programmation lineaireDetecter les directions innies oucxcro^t.Si le polyhedre n'est pas borne,cxpeut cro^tre indeniment:cs'ecritc=P
iyiLiavec lesyi0Lemme:les 2 cas s uivantss'excluent mutuellement: il existeutqcu >0etAu0cs'ecritc=P iyiLiavec lesyi08-3Gilles Schaeer INF-550-3: Programmation lineaireDetecter les directions innies oucxcro^t.Si le polyhedre n'est pas borne,cxpeut cro^tre indeniment:cs'ecritc=P
iyiLiavec lesyi0Lemme:les 2 cas s uivantss'excluent mutuellement: il existeutqcu >0etAu0cs'ecritc=P iyiLiavec lesyi0,l'optimum est borne8-4Gilles Schaeer INF-550-3: Programmation lineaireDetecter les directions innies oucxcro^t.Si le polyhedre n'est pas borne,cxpeut cro^tre indeniment:cs'ecritc=P
iyiLiavec lesyi0Lemme:les 2 cas s uivantss'excluent mutuellement: il existeutqcu >0etAu0,l'optimum est borneil existeutqcu> 0etAu0
8-5Gilles Schaeer INF-550-3: Programmation lineaireDetecter les directions innies oucxcro^t.Si le polyhedre n'est pas borne,cxpeut cro^tre indeniment:cs'ecritc=P
iyiLiavec lesyi0Lemme:les 2 cas s uivantss'excluent mutuellement: il existeutqcu >0etAu0,l'optimum est borneil existeutqcu> 0etAu0, 1
8-6Gilles Schaeer INF-550-3: Programmation lineaireDetecter les directions innies oucxcro^t.Si le polyhedre n'est pas borne,cxpeut cro^tre indeniment:cs'ecritc=P
iyiLiavec lesyi0Lemme:les 2 cas s uivantss'excluent mutuellement: il existeutqcu >0etAu0En eet:c=yA)cu=yAudonc siy0etAu0, on acu0.,l'optimum est borneil existeutqcu> 0etAu0, 1
8-7Gilles Schaeer INF-550-3: Programmation lineaireDetecter les directions innies oucxcro^t.Si le polyhedre n'est pas borne,cxpeut cro^tre indeniment:cs'ecritc=P
iyiLiavec lesyi0Lemme:les 2 cas s uivantss'excluent mutuellement: il existeutqcu >0etAu0En eet:c=yA)cu=yAudonc siy0etAu0, on acu0.Application:si au cours de l'ex ecution
on rencontre une ar^ete de directionutqAu0etcu >0, on a trouve une direction
de croissance innie et on peut s'arr^eter.,l'optimum est borneil existeutqcu> 0etAu0, 18-8Gilles Schaeer INF-550-3: Programmation lineaireDetecter les directions innies oucxcro^t.Si le polyhedre n'est pas borne,cxpeut cro^tre indeniment:cs'ecritc=P
iyiLiavec lesyi0Lemme:les 2 cas s uivantss'excluent mutuellement: il existeutqcu >0etAu0En eet:c=yA)cu=yAudonc siy0etAu0, on acu0.Application:si au cours de l'ex ecution
on rencontre une ar^ete de directionutqAu0etcu >0, on a trouve une direction
de croissance innie et on peut s'arr^eter.Si au pointxI, on ac=P i2IyiLiavecyi0, on a trouve l'optimum.,l'optimum est borneil existeutqcu> 0etAu0, 19-1Gilles Schaeer INF-550-3: Programmation lineaireAlgorithme du simplexe, versiongeneriqueSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2I
9-2Gilles Schaeer INF-550-3: Programmation lineaireAlgorithme du simplexe, versiongeneriqueSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2IExprimercdans la basefLkgk2I:c=P
k2IykLk.9-3Gilles Schaeer INF-550-3: Programmation lineaireAlgorithme du simplexe, versiongeneriqueSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2IExprimercdans la basefLkgk2I:c=P
k2IykLk.Siyk0pour toutk2I, on a trouve l'optimum.9-4Gilles Schaeer INF-550-3: Programmation lineaireAlgorithme du simplexe, versiongeneriqueSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2IExprimercdans la basefLkgk2I:c=P
k2IykLk.Siyk0pour toutk2I, on a trouve l'optimum.Sinon on choisiti2Itqyi<0et on considere l'ar^ete denie
par les equations deI0=In fig. Soituson vecteur directeur tqLiu=1(on s'eloigne):uest une colonne de(AI)1.9-5Gilles Schaeer INF-550-3: Programmation lineaireAlgorithme du simplexe, versiongeneriqueSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2IExprimercdans la basefLkgk2I:c=P
k2IykLk.Siyk0pour toutk2I, on a trouve l'optimum.Sinon on choisiti2Itqyi<0et on considere l'ar^ete denie
par les equations deI0=In fig. Soituson vecteur directeur tqLiu=1(on s'eloigne):uest une colonne de(AI)1.Calculer la vitesse versLjquand on suitu:vj=Lju.9-6Gilles Schaeer INF-550-3: Programmation lineaireAlgorithme du simplexe, versiongeneriqueSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2IExprimercdans la basefLkgk2I:c=P
k2IykLk.Siyk0pour toutk2I, on a trouve l'optimum.Sinon on choisiti2Itqyi<0et on considere l'ar^ete denie
par les equations deI0=In fig. Soituson vecteur directeurtqLiu=1(on s'eloigne):uest une colonne de(AI)1.Calculer la vitesse versLjquand on suitu:vj=Lju.sivj0on s'eloigne de l'hyperplanLj: si8j,max =1.
9-7Gilles Schaeer INF-550-3: Programmation lineaireAlgorithme du simplexe, versiongeneriqueSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2IExprimercdans la basefLkgk2I:c=P
k2IykLk.Siyk0pour toutk2I, on a trouve l'optimum.Sinon on choisiti2Itqyi<0et on considere l'ar^ete denie
par les equations deI0=In fig. Soituson vecteur directeurtqLiu=1(on s'eloigne):uest une colonne de(AI)1.Calculer la vitesse versLjquand on suitu:vj=Lju.sivj0on s'eloigne de l'hyperplanLj: si8j,max =1.Parmi les voisins sur l'ar^ete, prendre celui qui est dansP.
C'est celui qui est le plus proche parmi ceux du bon c^ote: donne par un desjtels quevj>0qui minimisentbjLjxIv j.9-8Gilles Schaeer INF-550-3: Programmation lineaireAlgorithme du simplexe, versiongeneriqueSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2IExprimercdans la basefLkgk2I:c=P
k2IykLk.Siyk0pour toutk2I, on a trouve l'optimum.Sinon on choisiti2Itqyi<0et on considere l'ar^ete denie
par les equations deI0=In fig. Soituson vecteur directeurtqLiu=1(on s'eloigne):uest une colonne de(AI)1.Calculer la vitesse versLjquand on suitu:vj=Lju.sivj0on s'eloigne de l'hyperplanLj: si8j,max =1.Parmi les voisins sur l'ar^ete, prendre celui qui est dansP.
C'est celui qui est le plus proche parmi ceux du bon c^ote: donne par un desjtels quevj>0qui minimisentbjLjxIv j.faireI=In fig [ fjg, recalculerxIet reprendre.10-1Algorithme du simplexe, analyseGilles Schaeer INF-550-3: Programmation lineaireSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2ISi on avance vers le sommetxJ,J=In fig [ fjg, alors:c=P
k2IykLk, avecyi<0.10-2Algorithme du simplexe, analyseGilles Schaeer INF-550-3: Programmation lineaireSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2ISi on avance vers le sommetxJ,J=In fig [ fjg, alors:Comparons l'objectifcxIaveccxJ:c=P
k2IykLk, avecyi<0.10-3Algorithme du simplexe, analyseGilles Schaeer INF-550-3: Programmation lineaireSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2ISi on avance vers le sommetxJ,J=In fig [ fjg, alors:Comparons l'objectifcxIaveccxJ:cxJ=cxI+cbjLjxIv
ju=cxI+bjLjxIv jcuorcu=P k2IykLku=yi>0puisqueuest dans les hyperplansLk,k6=ietLiu=1.c=P k2IykLk, avecyi<0.10-4Algorithme du simplexe, analyseGilles Schaeer INF-550-3: Programmation lineaireSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2ISi on avance vers le sommetxJ,J=In fig [ fjg, alors:Comparons l'objectifcxIaveccxJ:cxJ=cxI+cbjLjxIv
ju=cxI+bjLjxIv jcuorcu=P k2IykLku=yi>0puisqueuest dans les hyperplansLk,k6=ietLiu=1.)comme prevuxJameliore l'objectif...c=P k2IykLk, avecyi<0.10-5Algorithme du simplexe, analyseGilles Schaeer INF-550-3: Programmation lineaireSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2ISi on avance vers le sommetxJ,J=In fig [ fjg, alors:Comparons l'objectifcxIaveccxJ:cxJ=cxI+cbjLjxIv
ju=cxI+bjLjxIv jcuorcu=P k2IykLku=yi>0puisqueuest dans les hyperplansLk,k6=ietLiu=1.)comme prevuxJameliore l'objectif...sauf sibjLjx= 0!c=P k2IykLk, avecyi<0.10-6Algorithme du simplexe, analyseGilles Schaeer INF-550-3: Programmation lineaireSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2ISi on avance vers le sommetxJ,J=In fig [ fjg, alors:Comparons l'objectifcxIaveccxJ:cxJ=cxI+cbjLjxIv
ju=cxI+bjLjxIv jcuorcu=P k2IykLku=yi>0puisqueuest dans leshyperplansLk,k6=ietLiu=1.)comme prevuxJameliore l'objectif...sauf sibjLjx= 0!Si plus denhyperplansLkpassent parxI, certaines ar^etes degenerent
et on peut avoirxJ=xI, l'algorithme risque de boucler.c=P k2IykLk, avecyi<0.10-7Algorithme du simplexe, analyseGilles Schaeer INF-550-3: Programmation lineaireSoitxIle sommet courant, solutions desnequations(Lkx=bk)k2ISi on avance vers le sommetxJ,J=In fig [ fjg, alors:Comparons l'objectifcxIaveccxJ:cxJ=cxI+cbjLjxIv
ju=cxI+bjLjxIv jcuorcu=P k2IykLku=yi>0puisqueuest dans leshyperplansLk,k6=ietLiu=1.)comme prevuxJameliore l'objectif...sauf sibjLjx= 0!Si plus denhyperplansLkpassent parxI, certaines ar^etes degenerent
et on peut avoirxJ=xI, l'algorithme risque de boucler.Une solution: perturber lesbipour eliminer les degenerescences.c=P
k2IykLk, avecyi<0.11-1Algorithme du simplexe, initialisationGilles Schaeer INF-550-3: Programmation lineairePour demarrer l'algorithme il faut avoir un sommet deP.
11-2Algorithme du simplexe, initialisationGilles Schaeer INF-550-3: Programmation lineairePour demarrer l'algorithme il faut avoir un sommet deP.On cherche:argmax(cxjAxb)
11-3Algorithme du simplexe, initialisationGilles Schaeer INF-550-3: Programmation lineairePour demarrer l'algorithme il faut avoir un sommet deP.On cherche:argmax(cxjAxb)On peut toujours poserxi=yizi(le nombre de variables double)
et maximiser(c;c)y zpour(A;A)y zbety z0.11-4Algorithme du simplexe, initialisationGilles Schaeer INF-550-3: Programmation lineairePour demarrer l'algorithme il faut avoir un sommet deP.On cherche:argmax(cxjAxb)On peut toujours poserxi=yizi(le nombre de variables double)
et maximiser(c;c)y zpour(A;A)y zbety z0.On cherche donc:argmax(cxjAxb; x0)11-5Algorithme du simplexe, initialisationGilles Schaeer INF-550-3: Programmation lineairePour demarrer l'algorithme il faut avoir un sommet deP.On cherche:argmax(cxjAxb)On peut toujours poserxi=yizi(le nombre de variables double)
et maximiser(c;c)y zpour(A;A)y zbety z0.On cherche donc:argmax(cxjAxb; x0)Si lesbisont positifs,(0;:::;0)est notre sommet initial.11-6Algorithme du simplexe, initialisationGilles Schaeer INF-550-3: Programmation lineairePour demarrer l'algorithme il faut avoir un sommet deP.On cherche:argmax(cxjAxb)On peut toujours poserxi=yizi(le nombre de variables double)
et maximiser(c;c)y zpour(A;A)y zbetyz0.On cherche donc:argmax(cxjAxb; x0)Si lesbisont positifs,(0;:::;0)est notre sommet initial.Sinon on cherche un sommet deP=fxjAxb; x0g
11-7Algorithme du simplexe, initialisationGilles Schaeer INF-550-3: Programmation lineairePour demarrer l'algorithme il faut avoir un sommet deP.On cherche:argmax(cxjAxb)On peut toujours poserxi=yizi(le nombre de variables double)
et maximiser(c;c)y zpour(A;A)y zbetyz0.On cherche donc:argmax(cxjAxb; x0)Si lesbisont positifs,(0;:::;0)est notre sommet initial.Sinon on cherche un sommet deP=fxjAxb; x0gOn fait cela en cherchant parmi les(x1;:::;xn;t)tq
a i;1x1+:::+ai;nxntbipour touti, un point qui minimiset.11-8Algorithme du simplexe, initialisationGilles Schaeer INF-550-3: Programmation lineairePour demarrer l'algorithme il faut avoir un sommet deP.On cherche:argmax(cxjAxb)On peut toujours poserxi=yizi(le nombre de variables double)
et maximiser(c;c)y zpour(A;A)y zbetyz0.On cherche donc:argmax(cxjAxb; x0)Si lesbisont positifs,(0;:::;0)est notre sommet initial.Sinon on cherche un sommet deP=fxjAxb; x0gOn fait cela en cherchant parmi les(x1;:::;xn;t)tq
a i;1x1+:::+ai;nxntbipour touti, un point qui minimiset.On connait un sommet initial(0;:::;0;T)pour ce probleme lineaire.11-9Algorithme du simplexe, initialisationGilles Schaeer INF-550-3: Programmation lineairePour demarrer l'algorithme il faut avoir un sommet deP.On cherche:argmax(cxjAxb)On peut toujours poserxi=yizi(le nombre de variables double)
et maximiser(c;c)y zpour(A;A)y zbetyz0.On cherche donc:argmax(cxjAxb; x0)Si lesbisont positifs,(0;:::;0)est notre sommet initial.Sinon on cherche un sommet deP=fxjAxb; x0gOn fait cela en cherchant parmi les(x1;:::;xn;t)tq
a i;1x1+:::+ai;nxntbipour touti,un point qui minimiset.On connait un sommet initial(0;:::;0;T)pour ce probleme lineaire.Il existe (et on obtient) un sommet dePssit= 0dans sa solution.
12-1Cours 3: Programmation lineairePosition du problemeDualite.Degenerescence et terminaison de l'algorithmeAlgorithme du simplexe generiqueGilles Schaeer INF-550-3: Programmation lineaire
13-1Primal/dual et theoreme de dualiteGilles Schaeer INF-550-3: Programmation lineaireTheoreme (cas inegalites+positivite).Si l'un des 2 p roblemessuivant (P) max(cxjAxb; x0)(D) min(ybjyAc; y0)admet une solution nie, alors l'autre aussi et on amin(ybjyAc; y0) = max(cxjAxb;x0)
13-2Primal/dual et theoreme de dualiteGilles Schaeer INF-550-3: Programmation lineaireTheoreme (cas inegalites+positivite).Si l'un des 2 p roblemessuivant (P) max(cxjAxb; x0)(D) min(ybjyAc; y0)admet une solution nie, alors l'autre aussi et on amin(ybjyAc; y0) = max(cxjAxb;x0)Interpretation.Retour au
euriste. Primal max(4x+ 5x0)10x+ 10x050
10x+ 20x080
20x+ 10x080
x0,x0013-3Primal/dual et theoreme de dualiteGilles Schaeer INF-550-3: Programmation lineaireTheoreme (cas inegalites+positivite).Si l'un des 2 p roblemessuivant (P) max(cxjAxb; x0)(D) min(ybjyAc; y0)admet une solution nie, alors l'autre aussi et on amin(ybjyAc; y0) = max(cxjAxb;x0)Interpretation.Retour au
euriste. Primal max(4x+ 5x0)10x+ 10x050
10x+ 20x080
20x+ 10x080
x0,x00 y 1 y 2 y 313-4Primal/dual et theoreme de dualiteGilles Schaeer INF-550-3: Programmation lineaireTheoreme (cas inegalites+positivite).Si l'un des 2 p roblemessuivant (P) max(cxjAxb; x0)(D) min(ybjyAc; y0)admet une solution nie, alors l'autre aussi et on amin(ybjyAc; y0) = max(cxjAxb;x0)Interpretation.Retour au
euriste. Primal max(4x+ 5x0)10x+ 10x050
10x+ 20x080
quotesdbs_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
