≤ 2 En résolvant le problème de cet exemple sous sa forme standard, on obtiendrait comme solution de base réalisable optimale (2,1,0)
Previous PDF | Next PDF |
[PDF] Programmation Linéaire Cours 1 : programmes linéaires
Programme linéaire Résolution graphique Points extrêmes Forme standard, bases Bilan Motivation et objectif du cours Introduction `a la programmation
[PDF] Chapitre 4 Formes générale, canonique et standard dun probl`eme
Dans ce chapitre, nous définissons la forme générale d'un probl`eme d' optimisation linéaire, ainsi que la forme canonique et la forme standard Nous montrons
[PDF] Programmation linéaire et Optimisation
La forme standard associée au primal (apr`es introduction des variables d'écart) aura m = 1000 contraintes pour n = p + q = 1100 inconnues L'algo- rithme du
[PDF] Fondements de la programmation linéaire
≤ 2 En résolvant le problème de cet exemple sous sa forme standard, on obtiendrait comme solution de base réalisable optimale (2,1,0)
[PDF] Support de cours : Introduction à la programmation linéaire - IA - LIP6
On peut toujours transformer la forme canonique en forme standard en ajoutant des variables d'écart UPEC - Master ScTIC 4 Page 6 Forme canonique maxcx
[PDF] Programmation linéaire - LaBRI
13 Programmation linéaire Interprétation géométrique Bases et points extrêmes L'algorithme du simplexe Programmation linéaire Forme standard d'un PL
[PDF] Programmation linéaire - LACIM - UQAM
Forme standard minimiser cTx sous les contraintes Ax = b A Blondin Massé ( UQAM) Chapitre 5: Programmation linéaire MAT7560 Hiver 2019 17 / 54
[PDF] Programmation linéaire
Un problème d'optimisation linéaire sous forme standard est un problème de la forme (P LS) min Ax=b x≥0 c · x Proposition 2 3 Tout problème d'optimisation
[PDF] Programmation linéaire
Peut-on mettre le problème suivant sous forme standard ? Minimiser : cx Sous les contraintes : Ax = b et l ≤ x ≤ u Exercice Donner une solution optimale pour
[PDF] Chapitre I : Programmation linéaire
La méthode du simplexe nécessite la mise sous forme standard du programme linéaire à résoudre en ajoutant autant de variables d'écart qu'il y a de
[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 recherche opérationnelle methode de simplexe
1
Fondements
de la programmation linéaireGénéralitésNotations et définitionsPropriétés du problème de programmation linéaireThéorème fondamental de la programmation linéaireReprésentation géométrique d'une solution de base réalisableExemplesIllustration de la notion de base
2 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 quidécrit le problème réel.L'adjectif "linéaire"indique que toutes les fonctions mathématiques
de ce modèle sont linéaires tandis que le terme "programmation" signifie essentiellement planification 3Notations et définitions
Le problème général de programmation linéaire est la recherche de l'optimum (minimum ou maximum) d'une fonction linéaire de n variables x j (j=1,2,...,n) liées par des équations ou inéquations linéaires appelées contraintes.Parmi les contraintes on distingue généralement celles du type x j 0 (ou x j0), imposant à une partie ou à l'ensemble des variables d'être
non négatives (ou non positives). Les variables peuvent prendre n'importe quelles valeurs réelles satisfaisant aux contraintes. Certaines des variables sont remplacées par leurs opposées pour que les contraintes du type x j0 ou x
j0 soient toutes des conditions de
non-négativité. Certaines des inéquations ont été multipliées par -1 de façon que toutes les inégalités soient dans le même sens (par exemple). 4Formulation algébrique
nMinimiser (ou maximiser) z=c
j x j j=1 nSujet à:a
ij x j b j , i = 1, 2, ..., p j=1 n a ij x j =b j , i = p + 1, p + 2, ..., m j=1 x j0, j = 1, 2, ..., q
x j quelconque, j = q + 1, q + 2, ..., n, où les constantes c j , a ij et b j sont des nombres réels.(fonction objective) contraintes 5 1 e formulation équivalente nMinimiser (ou maximiser) z =c
j x j j=1 nSujet à:a
ij x j b j , i = 1, 2, ..., m j=1 x j0, j = 1, 2, ..., n.
Forme canonique
Note :
Utilisée en théorie de la dualité.
6 2 ième formulation équivalente nMinimiser (ou maximiser) z =c
j x j j=1 nSujet à:a
ij x j =b j , i = 1, 2, ..., m j=1 x j0, j = 1, 2, ..., n.
Forme standard
Note :
Servira au développement des méthodes de calcul. 7 3 ième formulation équivalenteMinimiser z = c
t x sujet à Ax = b x 0 où c = [c 1 , c 2 , ..., c n t b = [b 1 , b 2 , ..., b m t et A = [a ij , i = 1, 2, ..., m et j = 1, 2, ..., n] est une matrice de dimension m x n.Forme standard matriciel
Note :
Les formulations précédentes sont équivalentes; les opérations suivantes sont là pour nous en convaincre. 8 Opérations à effectuer pour passer d'une forme à l'autreOpération A
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 BUne variable de signe quelconque, x, peut toujours être remplacée par deux variables non négatives x+ et x-. Il suffit de poser x = x+ - x- où x+ = maximum [0, x], x- = maximum [0, -x]. Les variables x+ et x- ne peuvent pas faire partie d'un même "programme de base" i.e. l'une d'entre elles est nécessairement nulle dans l'une, au moins, des solutions optimales du problème.Note :
9 Opérations à effectuer pour passer d'une forme à l'autreOpération C
Toute équation de la forme
n a ij x j =b i j=1 peut être remplacée par les deux inéquations n a ij x j b i j=1 n -a ij x j -b i j=1 10 Opérations à effectuer pour passer d'une forme à l'autreOpération D
Toute inéquation, par exemple
n a ij x j b i j=1 peut être remplacée par les relations n a ij x j -e i =b i j=1 e i 0 obtenues par l'introduction d'une variable supplémentaire non négative appelée variable d'écart et affectée d'un coefficient nul dans la forme à optimiser. 11Exemple 2.2.1
- Mise sous forme canonique Le problème suivant est déjà sous forme canonique :Min Z = 2x
1 + 3x 2 -x 3 sous les contraintes: x 1 0, x 2 0, x 3 0, 2x 1 + x 2 -x 3 100x 1 + x 2 + x 3 80
12
Exemple 2.2.2
- Mise sous forme canonique Soit le problème de programmation linéaire suivant :Max C = 6x
1 -3x 2 + x 3Min -C = -6x
1 + 3x 2 -x 3 sous les contraintes: sous les contraintes: x 1 0, x 2 0, x 1 0, x 2 0, 4x 1 + 2x 2 + x 3 65 4x1 + 2x 2 + x 3 65
x 1 + x 2quotesdbs_dbs12.pdfusesText_18