Cours 3: Programmation linéaire PDF

Programmation Linéaire - Cours 3

Programmation Linéaire - Cours 3. F. Clautiaux francois.clautiaux@math.u-bordeaux1.fr Toute combinaison linéaire de contraintes du programme linéaire.

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.

Programmation Linéaire Cours 1 : programmes linéaires

Sommaire. Introduction par l'exemple. Exemple 1 : Production. Exemple 2 : Transport. Exemple 3 : Planification. Programme linéaire. Résolution graphique.

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.

LA PROGRAMMATION LINEAIRE : UN OUTIL DE MODELISATION

Une autre limitation risque d'intervenir sur la production. L'assemblage est caractérisé en particulier

Introduction à la programmation linéaire

Problème 3 Planifier la production d'articles à moindres coûts pour les 4 mois 3 mois 4. Demandes. 900. 1100. 1700. 1300. Cours - Introduction à la ...

Optimisation Linéaire (OL) -G4SIOL- Cours 0 - Introduction

4 oct. 2020 3- Algorithme du simplexe (2) : preuve et complexité ... L'objet du cours est d'étudier la “Programmation Linéaire”.

RCP104 – Optimisation en Informatique Cours 4 – Méthodes

Cours 1 : Introduction. ? Cours 2 : Modélisation. ? Cours 3 : Rappels de Programmation Linéaire (PL). ? Cours 4 : Méthodes arborescentes et PLNE.

Sujet 3: Programmation linéaire : interpretation géometrique

3 mars 2010 Sujet 3: Programmation linéaire : interpretation géometrique. MHT 423 : Mod`eles et méthodes d'optimisation. Andrew J. Miller.

MOD 4.4: Recherche opérationnelle

Dual d'un programme linéaire. • Qu'est ce qu'un graphe? • Application de la dualité aux graphes. Cours 3: Programmation Linéaire en nombre entiers.

Programmation Linéaire - Cours 3 - u-bordeauxfr

Fondements de la 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 La deuxième méthode est plus algébrique et elle justi?era la troisième qui porte le nom de

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

1 3 0 1 et b= 2 3 : Onnoterapara 1;a 2;a 3 eta 4 les4colonnesdeA Pourlechoixx 3 = x 4 = 0onenlèvelescolonnes3et4 Ax= x 1a 1 + x 2a 2 + x 3a 3 + x 4a 4 = x 1a 1 + x 2a 2 = b quiadmetlasolution(x 1;x 2) = (3=5;4=5) Laphilosophiegénéraleestque Unsommet unebasedel’espace-colonnedeA

Fondements de la programmation linéaire - Université Laval

Généralités sur la programmation linéaire La programmation linéaire traite de manière générale d'un problème d'allocation de ressources limitées parmi des activités concurrentes et ce d'une façon optimale La programmation linéaire emploie un modèle mathématique qui décrit le problème réel

Leçon N° 3 : La programmation linéaire

Leçon N° 3 : La programmation linéaire En premier il faut savoir résoudre graphiquement une inéquation linéaire à deux inconnues dans un repère du plan (P) Voyons un exemple : Chercher les réels x et y tels que 2x – y + 4 ? 0 Méthode : nous traçons la droite d’équation 2x – y + 4 = 0 en prenant deux valeurs simples de x

Searches related to cours 3 programmation linéaire filetype:pdf

L3 MiaSHS 2017-2018OptimisationUniversités de Rennes 1 & 2 Chapitre 2 Programmation linéaire 12 0 1 Unexemple

Quels sont les fondements de la programmation linéaire ?

Fondements de la programmation linéaire Généralités Notations et définitions Propriétés du problème de programmation linéaire Théorème fondamental de la programmation linéaire Représentation géométrique d’une solution de base réalisable Exemples Illustration de la notion de base 2 Généralités sur la programmation linéaire

Qu'est-ce que la programmation linéaire ?

Généralités sur la programmation linéaire La programmation linéaire traite de manière générale d'un problème d'allocation de ressources limitéesparmi des activités concurrentes et ce d'une façon optimale. La programmation linéaire emploie un modèle mathématique qui décrit le problème réel.

Est-ce que tout modèle de programmation linéaire est réalisable ?

En effet, on ne peut pas toujours avoir la garantie que tout modèle de programmation linéaire possède une solution réalisable. Il se peut que les contraintes du modèle soient incompatibles. Exemple :

Comment optimiser une fonctionnelle linéaire ?

En utilisant la relation minimum f(x) = -maximum [-f(x)] dans laquelle f(x) représente la fonctionnelle linéaire à optimiser, on peut toujours se ramener à un problème de minimisation (ou de maximisation). Opération B Une variable de signe quelconque, x, peut toujours être remplacée par deux variables non négatives x+ et x-.

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,

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,

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

4-3Un exemple bateau: le

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

4-6Un exemple bateau: le

4-7Un exemple bateau: le

4-8Un exemple bateau: le

4-9Un exemple bateau: le

4-10Un exemple bateau: le

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 lineaire

5-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 lineaire

5-3Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,

5-4Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,

5-5Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,

5-6Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,

5-7Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,

5-8Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,

5-9Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,

5-10Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,

5-11Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,

5-12Interpretation geometriqueDonnee:Une matrice r eelleA= (ai;j)de taillemn,

laquelle 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,

laquelle 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,

laquelle 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,

laquelle 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,

laquelle 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,

laquelle 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 global

6-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,

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 >0etAu0

8-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 lesyi0

8-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 borne

8-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 directionutq

Au0etcu >0, on a trouve une direction

de croissance innie et on peut s'arr^eter.,l'optimum est borneil existeutqcu> 0etAu0, 1

8-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 directionutq

Au0etcu >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, 1

9-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.