[PDF] Introduction à la programmation linéaire

View - Download Introduction à la programmation linéaire

Previous PDF

Next PDF

Introduction à la programmation linéaire

Informations pratiques2

Enseignant

Denis Arzelier : directeur de recherche au LAAS-CNRS

Contacts

Tel : 05 61 33 64 76 - email : arzelier@laas.fr

Web-page

http ://homepages.laas.fr/ ≂arzelier

Organisation du cours➊

5cours

1h15 :

06h15

Cours magistral en amphi avec supports de cours

4séances TD

1h15 :

05h00

Exercices d'application

2séances TP

2h45 :

5h30 Application avec support Python sous Notebook Jupyter

1examen final

:1h15

Durée totale = 18h00

Cours - Introduction à la programmation linéaire LAAS CNRS

Exemple I : problème de production3

✍Problème 1 Maximiser le profit d'un fabriquant de yaourts à la fraise A etB ✔Composition des yaourts de types A et B

Yaourt A

Yaourt B

Fraise

2 1 Lait 1 2 Sucre 0 1 ✔Disponibilité des matières pre- mières - Fraises : 800 kilos - Lait : 700 kilos - Sucre : 300 kilos ✔Profit par type de yaourt - Yaourt A : 4 euros/kilo - Yaourt B : 5 euros/kilos Cours - Introduction à la programmation linéaire LAAS CNRS

Exemple 1 : modélisation4

✔Variables de décision? (Ce que l'on doit décider)

Nombres de yaourts de type A et de type B :x

A,x B ✔Objectif? (Ce que l'on doit optimiser)

Profit :z= 4x

A+ 5x B ✔Contraintes? (Ce que l'on doit respecter) - Quantité maximale de fraises :2x A+x - Quantité maximale de lait :x A+ 2x - Quantité maximale de sucre :x

Problème de programmation linéaire :

max xA,x B4x A + 5x B sous 2x A +x B x A + 2x B x B x A, x B ≥0 Cours - Introduction à la programmation linéaire LAAS CNRS

Exemple 2 : problème de transport5

✍Problème 2 Approvisionner à moindre coût différents clients à partir de différentes usines ✔Lieux de production et quantités produites

Usines (i?I)

Bordeaux

Biarritz

Toulouse

Productions (p

i) 25
15 20 ✔Lieux et quantités de livraison

Clients (j?J)

Pau

Bayonne

Bordeaux

Libourne

Demandes (d

j) 20 12 9 14 ✔Coûts de livraison

Prix/unité (c

ij) Pau

Bayonne

Bordeaux

Libourne

Bordeaux

26
19 0 4

Biarritz

12 2 20 24

Toulouse

19 30
24
28
✔Variablesx ij : quantité produite eniet livrée enj

Problème de PL :

min xij? i,j cijxij sous? i xij =d j, j?J j xij =p i, i?I x ij ≥0, i?I, j?J Cours - Introduction à la programmation linéaire LAAS CNRS

Exemple 3 : problème de planification6

Problème 3

Planifier la production d'articles à moindres coûts pour les4 prochains mois

Production maximale normale :

1200 articles / mois

Production maximale en heure sup :

400 articles / mois

Sur-coût heures sup :

7 euros / article

Stockage :

3 euros / article / mois

Demande sur les 4 prochains mois :

mois 1 mois 2 mois 3 mois 4

Demandes

900
1100
1700
1300
Cours - Introduction à la programmation linéaire LAAS CNRS

Exemple 3 : modélisation7

✔Variables : -x t: production normale en périodet= 1,...,4 -y t: production en heure sup en périodet= 1,...,4 -st: stock en fin de périodet= 1,...,3 ✔Objectif :

Minimiser7

t=4?t=1 yt+ 3 t=3?t=1 st ✔Contraintes x1+y

1= 900+s

1 s1+x 2+y

2=1100+s

2 s2+x 3+y

3=1700+s

3 s3+x 4+y

4=1300

st≥0t= 1,...,3 Cours - Introduction à la programmation linéaire LAAS CNRS

Quelques remarques historiques (I)8

✔Etude des systèmes d'inégalités linéaires par J. Fourier en1827 - Méthode d'élimination de Fourier-Motzkin - Généralise l'élimination de Gauss-Jordan

J. Fourier (1768-1830)

✔Formulation d'une classe restreinte de PL + Algorithme en URSS par L.V. Kantorovich en 1939

L.V. Kantorovich (1912-1986)

- Réorganisation de l'industrie du bois dans une économie centralisée - Optimisation de la production industrielle de contreplaqué - Théorie de l'utilité marginale - Co-prix Nobel d'économie en 1975 (travaux en allocation optimale de ressources)

✔Minimisation du coût total de transport de biens par T.C. Koopmans en 1944 pour la British Merchant Shipping

Mission

-Exchange ratios between cargos on various routes - Co-prix Nobel d'économie en 1975 (travaux en allocation optimale de ressources) - Fondation de la recherche opérationnelle

T.C. Koopmans (191O-1985)

Cours - Introduction à la programmation linéaire LAAS CNRS

Quelques remarques historiques (II)9

✔Algorithme du simplexe par G. Dantzig en 1947 pour l'U.S. AirForce - Problèmes militaires de planification d'opérations et d'allocation de ressources - Algorithme dans le top 10 en 2000

G. Dantzig (1914-2005)

✔Algorithme de l'ellipsoïde par L.G. Kachiyan en 1979 xk -→g k xk+1 Ek Ek+1 - Algorithme en temps polynomial - Peu efficace en pratique (degré élevé du polynôme(t)) ✔Algorithme polynomial de point intérieur par N. Karmakar en1984 - Brevet U.S. Patent 4,744,028 "Methods and apparatus for efficient resource allocation" (mai 1988), débattu au sénat U.S. - Méthodes de point intérieur pour la programmation convexe(SDP) Cours - Introduction à la programmation linéaire LAAS CNRS

Hypothèses fondamentales et terminologie10

minx?R n(max x?R n)f( x) =c 1x1+c

2x2+...+c

nxn sousa 1,1 x1+a 1,2 x2+...+a 1,n xn=b 1 a m,1 x1+a m,2 x2+...+a m,n xn=b m am+1,1 x1+a m+1,2 x2+...+a m+1,n m+1 a m+p,1 x1+a m+p,2 x2+...+a m+p,n m+p ✔Linéarité : -Fonction objectif : f( x) =c Tx -Contraintes :

X={x?R

n :h( x) =A 1x-B

1= 0, g(

x) =A 2x-B 2?0} ✔Continuité :x ?R n?= PLNE = x?N n -Solution réalisable : xest une solution réalisable ssi x?X

Région réalisable :

ensemble des solutions réalisablesX Cours - Introduction à la programmation linéaire LAAS CNRS

Géométrie et PL (I)11

Un ensembleCest

convexe ssi le segment de droite entre deux points quelconquesx, y? Cappartient àC ?λ?[0,1], x, y? C ?(1-λ)x+λy? C z= (1-λ)x+λy, λ?[0,1]est la combinaison convexe dexety xxxyy y ✔L'enveloppe convexecoC d'un ensembleCest l'ensemble de toutes les combinaisons convexes des points deC coC=?? i

λixi:x

i? C, λ i≥0,? i

λi= 1?

x? Cest un point extrême d'un ensemble convexeCsi x=λx1+ (1-λ)x 2, x 1, x

2? C, λ?(0,1)?x=x

1=x 2 ♥Propriétés 1L'intersection finie de plusieurs ensembles convexes n?i=1

Ciest un ensemble convexe

Cours - Introduction à la programmation linéaire LAAS CNRS

Géométrie et PL (II)12

Un hyperplan deR nest un sous-espace affine de dimensionn-1 H=? x?R n|a T(x-x

0) = 0?

oùa?= 0?R nest le vecteur normal

à l'hyperplan

Un hyperplan diviseR

nen 2 demi-espaces H -=?x?R n|a T(x-x n H +=?x?R n|a T(x-x

0)≥0?, a?= 0?R

n a x 0x x1 x 2H +H

Hyperplan et demi-espacesx? H

,x1? H+ ,x2? H- Un polyèdre convexe est un ensemble défini par un nombre fini d'inégalités linéaires a3 a1 a 2 a4a 5a 6

Polytope intersection de demi-espaces

P=?x?R

n:a T j,j= 1,···,m? ={x?R n :Ax?b} Ex : l'orthant positifR est un ensemble polyèdral conique xE est un point extrême du polyèdrePsi?y?=z? P, x

E??(y,z)

Un polyèdre convexe borné est un

polytope convexe Cours - Introduction à la programmation linéaire LAAS CNRS

Géométrie et PL (III)13

Un point

vd'un polyèdre convexe P est un sommet de P si v? Pet?c?= 0?Rn:cTv > cTy,?y? P \ {v} c v c

Tx=cTv

Les sommets d'un polyèdre convexe sont exactement ses points extrêmes L'ensemble des solutions admissibles d'un PL est un polyèdre convexe P x1 x2 P a11x1+a12x2=b1a21x1+a22x2=b2 a31x1+a32x2=b3 x2= 0quotesdbs_dbs28.pdfusesText_34

[PDF] forme standard dun programme linéaire

[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