[PDF] Programmation Lin aire Cours 1 - Institut de Mathématiques

Notion de fonction Résolution graphique Fonction affine

2 RÉSOLUTION GRAPHIQUE Ce sera aussi l’occasion de définir mathématiquement les différents termes utili-sés avec les fonctions Enfin cela permet de faire un lien avec les deux chapitres précédents : équation et inéquation dans R que nous avons traité algébriquement et qui trouve ici un autre éclairage avec une résolution

Savoir-Faire : Résolution graphique d’équations et inéquations

Savoir-Faire : Résolution graphique d’équations et inéquations Méthodes : Résoudre graphiquement l’équation f (x) = k, c’est déterminer les abscisses des points de la courbe C f ayant pour ordonnée k (Rmq: cela revient à déterminer les antécédents de k par f )

Titre : Résolution graphique d’équations et d’inéquations

Résolution graphique de f(x)>g(x) Résolution graphique d'une inéquation, 2 courbes dont une droite (par étiquettes) Auteurs : Régine Mangeard, Marie-Claude David

Résolution graphique d’équations et d’inéquations

Lors de la résolution de ????( )= , ????, on a trouvé comme solution -1,3 et 2,6 On peut constater que sur l’intervalle [ ,???? ; ], la fonction ???? est strictement monotone et prend des valeurs strictement supérieures à 1,47 Dans ce contexte, on constate que l’équation????( )= possède une et une seule solution

Leçon 0602C La programmation linéaire 1 résolution graphique

Résolution graphique 1 - Principes Il s’agit de déterminer la combinaison productive d’articles, de produits, compte tenu des matrices techniques et du programme des ventes à réaliser, qui maximise la rentabilité tout en saturant les contraintes productives (plein emploi des facteurs de production : main d’œuvre, matériels )

TP 8 : CALCUL GRAPHIQUE DES RACINES D - IREM de la Réunion

les apports des modes de résolution graphique et algébrique On précisera les avantages et les limites de ces différents modes de résolution On pourra utiliser les graphiques des fonctions de référence et leurs positions relatives » Favoriser des changements de cadre entre algèbre et géométrie, entre méthodes numériques et graphi-

Systèmes de deux équations du premier degré à deux inconnues

Systèmes de deux équations du premier degré à deux inconnues 1 Présentation de la problématique 2 Résolution par la méthode de combinaison linéaire (Elimination ) 3 Résolution par la méthode de substitution 4 Résolution graphique 5 Diverses présentations de systèmes de deux équations du premier degré à deux

Outils et Méthode de résolution de problème

Démarche de résolution sur format A3, d’où le nom Le diagramme causes - effet est une représentation graphique simple qui, pour un effet (un défaut, une

Programmation Lin aire Cours 1 - Institut de Mathématiques

Exemples Programme lin´eaire R´esolution graphique Points extrˆemes Forme standard, bases Bilan Probl`eme de production Un fabricant produit 2 types de yaourts a la fraise A et B a partir de Fraise, de Lait et de Sucre Chaque yaourt doit respecter les proportions suivantes de mati`eres premi`eres A B Fraise 2 1 Lait 1 2 Sucre 0 1

[PDF] resolution de l equation

[PDF] Résolution de l'équation 2x-1=1/x

[PDF] Résolution de l'équation x²+4x+5=0

[PDF] Résolution de l'oeil - besoin d'un petit coup de main, s'il vous plaît

[PDF] résolution de l'onu définition

[PDF] résolution de plusieurs équations

[PDF] Résolution de problème

[PDF] resolution de probleme

[PDF] Résolution de problème

[PDF] Résolution de problème

[PDF] Résolution de problème

[PDF] Résolution de problème

[PDF] Résolution de problème

[PDF] Résolution de problème

[PDF] Résolution de probléme

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Programmation Lin´eaire

Cours 1 : programmes lin´eaires, mod´elisation et r´esolution graphique

F. Clautiaux

francois.clautiaux@math.u-bordeaux1.fr

Universit´e Bordeaux 1

Bˆat A33

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Motivation et objectif du cours

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 efficace pour la PL

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Ouvrages de r´ef´erence

V. Chv´atal - Linear Programming, W.H.Freeman, New York, 1983. •R. J. Vanderbei - Linear Programming, Foundations and Extensions,

Springer-Verlag, 2008.

•C. Gu´eret, C. Prins et M. Sevaux - Programmation lin´eaire :65 probl`emes d"optimisation mod´elis´es et r´esolus avec Visual Xpress,

Eyrolles, 2000.

•C. Prins et M. Sevaux - Programmation lin´eaire avec Excel : 55 probl`emes d"optimisation mod´elis´es pas `a pas et r´esolus avec Excel,

Eyrolles, 2011.

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Sommaire

Introduction par l"exemple

Exemple 1 : Production

Exemple 2 : Transport

Exemple 3 : Planification

Programme lin´eaire

R´esolution graphique

Points extrˆemes

Forme standard, bases

Bilan ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Probl`eme de production

Un fabricant produit 2 types de yaourts `a la fraise A et B `a partir de Fraise, de Lait et de Sucre. Chaque yaourt doit respecter les proportions suivantes de mati`eres premi`eres. AB

Fraise21

Lait12

Sucre01

On dispose de 800 Kg de Fraises, 700 Kg de Lait et 300 Kg de sucre. La vente de 1 Kg de yaourts A et B rapporte respectivement 4eet 5e.

Le fabricant cherche `a maximiser son profit.

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Que cherche-t-on `a optimiser? •Quelles sont les contraintes du probl`eme? ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Seules valeurs non constantes : les quantit´es de yaourtsAetB produites •On parle devariables •On les noteraxAetxB •Que cherche-t-on `a optimiser? •Quelles sont les contraintes du probl`eme? ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Variables :xAetxB •Que cherche-t-on `a optimiser? •Le profitz •Calcul´e `a partir dexAetxB •On parle defonction objectif •z= 4xA+ 5xB •Quelles sont les contraintes du probl`eme? ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Variables :xAetxB •Que cherche-t-on `a optimiser? •maxz= 4xA+ 5xB •Quelles sont les contraintes du probl`eme? •Premi`ere contrainte : 800 Kg de fraises disponibles •la quantit´e utilis´ee d´epend de la production : 2xA+xB ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Variables :xAetxB •Que cherche-t-on `a optimiser? •maxz= 4xA+ 5xB •Quelles sont les contraintes du probl`eme? x x ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Variables :xAetxB •Que cherche-t-on `a optimiser? •maxz= 4xA+ 5xB •Quelles sont les contraintes du probl`eme? x x x

A,xB≥0

positivit´e! ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mon premier programme lin´eaire

max4xA+ 5xB x x x

A,xB≥0

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Probl`eme de transport

Approvisionner au moindre coˆut les clients `a partir des usines.

Usines (i?I)BordeauxBiarritzToulouse

Productions (pi)251520

Clients (j?J)PauBayonneBordeauxLibourne

Demandes (dj)2012914

Prix/unit´e (ci,j)PauBayonneBordeauxLibourne

Bordeaux261904

Biarritz1222024

Toulouse19302428

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x i,j: quantit´e transport´ee dei`aj ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x i,j: quantit´e transport´ee dei`aj •Objectif :

Minimiser?

i?I? j?Jci,jxi,j ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x i,j: quantit´e transport´ee dei`aj •Objectif :

Minimiser?

i?I? j?Jci,jxi,j •Contraintes :? i?Ixi,j=dj,?j?J(Demandes `a satisfaire) x i,j≥0,?i?I,j?J ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Probl`eme de planification

Planifier la production d"articles `a moindre coˆut pour les 4 prochains mois. Production maximale normale : 1200 articles / mois Production maximale en heure sup : 400 articles / mois

Surcoˆut heures sup : 7 euros / article

Stockage : 3 euros / article / mois

mois 1mois 2mois 3mois 4

Demandes900110017001300

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x t: production normale en p´eriodet= 1,...,4 y t: production en heure sup en periodet= 1,...,4 s t: stock en fin de p´eriodet= 1,...,3 ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x t: production normale en p´eriodet= 1,...,4 y t: production en heure sup en periodet= 1,...,4 s t: stock en fin de p´eriodet= 1,...,3 •Objectif :

Minimiser 7?t=4

t=1yt+ 3?t=3 t=1st •Contraintes : x

1+y1= 900+s1

s

1+x2+y2= 1100+s2

s

2+x3+y3= 1700+s3

s

3+x4+y4= 1300

s t≥0,t= 1, ...,3 ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Sommaire

Introduction par l"exemple

Programme lin´eaire

R´esolution graphique

Points extrˆemes

Forme standard, bases

Bilan ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

R`egles de r´e´ecriture (1)

Toute contrainte d"´egalit´e peut s"´ecrire comme deux in´egalit´es : n i=1a ixi=b≡? n i=1a ixi≥b≡n? Tout probl`eme de minimisation peut s"´ecrire comme un probl`eme de maximisation : max n? i=1c ixi≡minn? i=1-cixi ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan Ecriture g´en´erale d"un programmation lin´eaire On peut ´ecrire ainsi un programme lin´eaire avecnvariables x

1,...,xnetmcontraintes.

max ?ni=1cixi x i?R,(i= 1,...,n) •Lin´earit´e :Objectif et contraintes sont des fonctions lin´eaires des variables de d´ecision (les coefficientscietaijdes variables sont constants) •Continuit´e :Les variables peuvent prendre n"importe quelle valeur r´eelle respectant les contraintes linaires ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan Exemples simples de programmes non lin´eaires (1) min?ni=1xixi x i?R,(i= 1,...,n) min ?ni=1xi x i?

N,(i= 1,...,n)

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan Exemples simples de programmes non lin´eaires (2) min?ni=1cixi x i?

R∩[l1,u1]∩[l2,u2],(i= 1,...,n)

min ?ni=1cixi x 1=x2 oux1=x3 x i?R,(i= 1,...,n) ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Forme normale d"un programme lin´eaire

Tout programme lin´eaire peut s"´ecrire sousforme normale. max ?ni=1cixi x i≥0,xi?R,(i= 1,...,n)

Si on a une variablexi?R, on introduitx+

i≥0 etx- i≥0 et on posexi=x+ i+x- i. ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Sommaire

Introduction par l"exemple

Programme lin´eaire

R´esolution graphique

Repr´esentation graphique d"un PL

R´esolution graphique

Points extrˆemes

Forme standard, bases

Bilan ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

R´esolution graphique

On dispose d"un outil (la PL) pour mod´eliser des probl`emes •Comment r´esoudre les probl`emes `a l"aide de la PL? •Plusieurs algorithmes existent, dont le simplexe (prochain cours)

•Pour des probl`emes avec deux variables, on peut r´esoudregraphiquement (aide `a comprendre la structure du probl`eme)

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Repr´esentation graphique

max 4xA+ 5xB x x x

A,xB≥0

x xAx B ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Repr´esentation graphique

max 4xA+ 5xB x x xquotesdbs_dbs49.pdfusesText_49