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
| Previous PDF | Next PDF |
[PDF] Programmation linéaire et Optimisation
Méthode du simplexe : un aperçu par l'exemple Considérons le probl`eme d' optimisation linéaire : maximiser z = 5x1 +4x2 +3x3 sous les contraintes 2x1
[PDF] Chapitre I : Programmation linéaire
programmation linéaire pour approcher ces problèmes peut se faire selon trois de la solution en cours une variable qui devient positive : c'est la variable
[PDF] Programmation linéaire et recherche opérationnelle Recherche
Les probl`emes de programmation linéaire (PL) sont des probl`emes d' optimisation o`u Simplexe Dualité Pourquoi un cours sur la programmation linéaire?
[PDF] 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
[PDF] COURS DE RECHERCHE OPERATIONNELLE - UFR SEG
U des Sciences Economues et de Gestion COURS DE RECHERCHE OPERATIONNELLE ECUE 1 : PROGRAMMATION LINEAIRE NOTES DE COURS PAR
[PDF] Programmation linéaire - JavMathch
6 3 Résolution complète de l'exemple FIL ROUGE 36 ( IV) Résolution de problèmes de programmation linéaire à 2 variables par voie graphique Au cours du mois prochain, l'entreprise disposera en temps- machine
[PDF] Modèles de Recherche Opérationnelle - Département d
2 2 Modèle général de programmation linéaire 3 Programmation non linéaire 31 visiter les campus de trois universités du Maine au cours d'un voyage unique, Avant d'essayer de résoudre le problème d'optimisation complet (à l' aide
[PDF] i la programmation linéaire
(a) est important en tant que tel, puisqu'il s'agit d'un cours de mathématiques Formulation d'un problème de programmation linéaire, est une description Étape 6 – Ce tableau est la matrice complète du système d'équations suivant : x + 3s
[PDF] Recherche opérationnelle et applications
II Applications de la programmation linéaire 6 Un problème est difficile s'il appartient à la classe des problèmes NP-complets, pour Défaut : méthodes “ aveugles”, un mauvais choix fait en cours de construction ne peut pas être “défait ”
[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] recherche opérationnelle cours complet
![[PDF] Cours 3: Programmation linéaire](https://pdfprof.com/Listes/18/5648-18INF550-2011-3.pdf.pdf.jpg "[PDF] Cours 3: Programmation linéaire")
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.