|
programmation linéaire est la science de la modélisation d'un problème qui minimise ou maximise soit une fonction objective linéaire , sous un ensemble de contraintes exprimées inégalités linéaires . Lorsque complètement résolu , la solution du programme linéaire entier garantit la solution optimale au problème . Cependant, la complexité des échelles de problèmes de façon exponentielle avec la taille du problème. Par conséquent, il peut prendre un certain temps pour arriver à la solution finale. Sinon, le problème peut être résolu partiellement et différentes heuristiques peuvent être explorées pour obtenir une solution sous-optimale à un temps plus court . Choses que vous devez
Programmation linéaire solveur
ordinateur avec suffisamment de mémoire et de puissance de traitement
Voir Plus Instructions
la formulation et la résolution des programmes linéaires
1 décider si le problème est un problème de « maximisation » ou un problème de « minimisation ». Un problème de maximisation essaie de trouver une solution telle où la fonction objectif est maximisée. Un problème de minimisation essaie de trouver une solution où la fonction objectif est minimisée. Par exemple, le problème de trouver le plus court chemin entre deux points est un problème de minimisation . D'autre part , le problème d'emballer le nombre maximal cailloux de différentes tailles dans une bouteille est un problème de maximisation .
2 Décider les variables nécessaires à la formulation. Choisir le bon ensemble de variables est nécessaire de minimiser la complexité du problème et, corrélativement, arriver à la solution plus rapidement. Typiquement, chaque entité dont la valeur affecte la solution finale est une variable.
3 modèle de la fonction objective. La fonction objectif est modélisée comme une somme de produits de variables et de leur impact sur la solution finale. Par exemple, si le problème est de minimiser la distance entre deux noeuds d'un graphe , chaque connexion entre deux noeuds sera une variable qui prend la valeur 0 ou 1, et sa contribution à la fonction objectif sera la distance entre les nœuds . Dans ce cas, la variable peut être appelée "X (i, j) , " où " i " et " j" sont les deux nœuds dans le graphe , et la distance entre les deux noeuds peuvent être « V (i, j) ». X ( i, j) sera 1 si la connexion est une partie de la trajectoire finale entre les deux noeuds . Par conséquent, la fonction objectif sera de minimiser la somme de V (i, j) * X ( i , j) , où la sommation est sur toutes les connexions .
4 Mettre en place les contraintes . Les contraintes doivent saisir toutes les restrictions imposées par le problème. Pour l'exemple de la trajectoire la plus courte , il existe des contraintes suivantes:
X ( i, j) peut être soit 0 ou 1 . Par conséquent, X (i, j) doit être supérieur ou égal à 0, et X (i, j) doit être inférieur ou égal à 1.
Si la connexion X (i, j) est choisie, exactement une connexion à partir du noeud "j" à un autre nœud autre que le "i" devrait être choisie. Ainsi, X (i, j) doit être supérieure ou égale à la somme de toutes les variables de type X (j, k ), où "k" n'est pas égal à " i ".
Une connexion de le noeud de départ doit être sélectionné. Par conséquent , la somme de X ( n, k) doit être de 1 , où "n" est le noeud de départ . De même , la somme de X (k, m) devrait être de 1 , où "m" est le nœud de fin.
5 modèle le problème soit dans le système de programmation mathématique ( MPS ) format ou le linéaire programmation (LP ) Format .
6 soit acheter un solveur commercial comme FICO ou CLPEX , ou télécharger un solveur libre comme GLPK . Notez les solveurs libres sont beaucoup plus lents que les solveurs commerciaux et peuvent ne pas convenir pour la résolution de grands problèmes.
7 Si le solveur ne converge pas vers la solution finale dans un délai raisonnable , essayez heuristiques . Une heuristique pourrait être de lever les contraintes entières sur les variables et approximatives des variables à l'entier le plus proche pour obtenir une solution sous-optimale.
|
