Qu'est-ce que la programmation linéaire? [fermé]
j'ai lu sur wikipedia article, mais il semble être au-delà de ma compréhension. Ça dit que c'est pour l'optimisation, mais en quoi est-ce différent de n'importe quelle autre méthode pour optimiser les choses?
une réponse qui me présente à la programmation linéaire pour que je puisse commencer à plonger dans du matériel moins accessible aux débutants serait très utile.
5 réponses
Les réponses jusqu'à présent ont donné une définition algébrique de la programmation linéaire, et d'une définition opérationnelle. Mais il existe aussi une définition géométrique. polytope est une généralisation n-dimensionnelle d'un polygone (en deux dimensions) ou d'un polyèdre (en trois dimensions). polytope convexe est un polytope qui est aussi un ensemble convexe. Par définition, la programmation linéaire est un problème d'optimisation dans lequel vous voulez maximiser ou minimiser une fonction linéaire sur un polytope convexe.
Par exemple: Supposons que vous voulez acheter une combinaison de sable rouge, de bleu et de sable. Supposons aussi:
- Vous ne pouvez pas acheter un montant négatif de genre.
- le dépôt n'a que 300 livres de sable rouge et 400 livres de sable bleu.
- Également votre jeep a une limite de poids de 500 livres.
si vous dessinez dans l'avion combien vous pouvez acheter avec ces contraintes, c'est un pentagone convexe. Alors, ce que vous voulez l'optimiser (par exemple, le montant total de l'or dans le sable), vous pouvez savoir à l'optimum (pas nécessairement le seul optimum) est l'un des sommets du polytope. En fait, il est beaucoup plus fort résultat: Même dans les dimensions, tout problème de programmation linéaire peut être résolu en temps polynomial en le nombre de contraintes, ou putatifs faces du polytope. Noter que chaque contrainte correspond à un côté. Si la contrainte est une égalité, il pourrait réduire la dimension du polytope. Ou si la contrainte est une inégalité, elle pourrait ne pas créer un côté si elle est déjà implicite par toutes les autres contraintes.
il y a beaucoup de problèmes pratiques d'optimisation qui sont de la programmation linéaire. Un des premiers exemples était le "problème de régime": étant donné un menu d'un tas de types d'aliments, Quelle est la moins chère alimentation équilibrée possible? C'est un problème de programmation linéaire est parce que le coût est linéaire, et parce que toutes les contraintes (vitamines, calories, l'hypothèse que vous ne pouvez pas acheter une quantité négative d'aliments,etc.) sont linéaires.
Oui, deux généralisations sont convexes programmation et programmation entière. Avec certaines qualifications, la programmation convexe peut fonctionner aussi bien que la programmation linéaire, à condition que l'objectif (la chose à maximiser) soit linéaire. Il s'avère que la convexité, pas les côtés plats, est la principale raison pour laquelle la programmation linéaire a un bon algorithme.
la programmation entière, d'un autre côté, est habituellement difficile. Par exemple, supposons dans le problème d'exemple que vous devez acheter le sable dans des sacs de taille fixe plutôt que dans la masse; qui est puis programmation entière. Il y a un théorème qu'il peut être NP-dur. La difficulté dans la pratique dépend de la proximité de la programmation linéaire. Il y a quelques exemples célèbres de problèmes de programmation entière dans lesquels, miraculeusement, tous les sommets du programme linéaire sont des points entiers. Ensuite, vous pouvez résoudre le programme linéaire et la solution se trouvera être intégrante. Un exemple d'un tel problème est le problème du mariage, comment marier n hommes et n Femmes À l'autre pour maximiser le bonheur total. (Ou, n villes à n usines, n emplois à n candidats, n ordinateurs à n imprimantes, etc.)
la programmation Linéaire est un sujet de "programmation mathématique", qui est aussi appelé "optimisation mathématique'. Les programmes linéaires diffèrent des programmes mathématiques généraux en ce que pour un programme linéaire (LP) toutes les fonctions de contrainte et la fonction objective sont linéaires par rapport à leurs variables.
Un bon endroit pour commencer serait ici si vous voulez que le travail original de Dantzig, ou si vous voulez obtenir un manuel, je recommande . Si vous vous voulez chercher vos propres ressources, commencez par chercher le méthode du Simplexe--c'est une technique très courante pour résoudre ces programmes, ou du moins fréquents, mais certainement temps polynomial méthode ellipsoïde. Bien que je n'ai pas tout lu, en le regardant rapidement suggère aussi PDF peut être un bon point de départ. Assurez-vous que tout ce que vous finissez par lire couvre la dualité (et peut-être spécifiquement le Farkas lemme c'est une idée centrale dans la plupart des résolveurs LP.
les extensions les plus naturelles sont soit des programmes entiers (similaires aux LP, mais toutes les variables doivent prendre des valeurs entières--c'est-à-dire pas de composants fractionnels) ou une programmation convexe (peut-être une extension plus générale). Un bon manuel d'optimisation convexe est disponible en format PDF ici.
comme tout le monde l'a dit, la programmation linéaire est un moyen de résoudre les problèmes d'optimisation, dans lesquels les termes sont linéaires.
Il pourrait aider à comprendre quels types de problèmes de LP résoudre
un exemple où j'ai utilisé la programmation linéaire est la construction d'un horaire de restaurant. Dans un restaurant, vous avez des compétences ensembles:
- Cuisiniers
- Serveurs
- lave-Vaisselle
- Hosts
- Bussers
- Gestionnaire de etc
Et vous avez des employés, chacun avec un ou plusieurs ensembles de compétences. Chaque employé possède une certaine disponibilité. Par exemple, Bob ne peut pas travailler le dimanche matin parce qu'il est pasteur dans une église locale. Les employés ont aussi un coût connexe. Bob pourrait être $ 10.50 / hr tandis que Suzy est $5.15 / hr. Enfin Salariés pourrait avoir minimum garanti heures. Comme Bob est employé depuis 15 ans, le patron dit qu'il aura toujours au moins 35 heures.
le restaurant lui-même a des exigences. Par exemple, il y a 3 équipes: le matin, L'après-midi et la nuit, et chacune de ces équipes a un ensemble de besoins en personnel: nous avons besoin de 1 cuisinier, 1 Serveur, 1 Gestionnaire le matin, 3 cuisiniers, 2 serveurs, 2 hôtes, 2 gestionnaires l'après-midi, et 4 cuisiniers, 4 serveurs, 3 hôtes, 2 gestionnaires, 2 serveurs le soir. Chaque quart de travail vous pouvez calculer le coût de chaque poste en multipliant la durée par le salaire horaire de l'employé.
enfin, nous avons des lois d'état et fédérales, et quelques règles "d'affaires" de base: Aucun employé ne peut travailler plus de 8 heures sans faire des heures supplémentaires. Aucun employé ne peut être mis à l'horaire pour moins de deux heures (parce que ça craint de faire un trajet de 30 minutes pour un quart de 2 heures), les employés ne peuvent pas travailler deux quarts qui se chevauchent, etc.
Maintenant, compte tenu de tous ces exigences, donnez-moi un calendrier qui a satisfait à toutes les exigences, et produit le coût de main-d'œuvre le plus bas.
C'est un exemple de programmation linéaire problème d'optimisation.
Un programme linéaire se compose généralement de:
une fonction objective, des variables, des limites variables et des contraintes.
Puisque nous voulons réduire les coûts, notre fonction objectif va impliquer des quarts de travail des employés et les coûts associés (maj durée * salaire.)
Les variables dans ce cas, sont les changements que chaque employé peut travailler.
Les limites de ces variables entiers compris entre 0 et 1, car un employé travaille le passage (1), ou l'employé ne travaille pas la maj (0). Ceci, soit dit en passant, est un programme spécial, appelé un programme binaire entier ou BIP pour faire court, parce que toutes les variables sont des entiers (pas de valeurs fractionnaires) et toutes les valeurs sont soit 0 ou 1.
Les contraintes sont contraintes d'égalité/d'inégalité fondées sur les exigences ci-dessus.
par exemple, si Bob et Suzy peuvent tous les deux travailler comme cuisiniers le matin, alors Bob_Morning_Cook1_Shift + Suzy_Morning_Cook1_Shift = 1Bob_Morning_Cook_Shift = {0,1} et Suzy_Morning_Cook_Shift = {0,1} en raison des limites mentionnées ci-dessus. Ces trois éléments d'information précisent qu'au plus un seul employé peut être désigné comme premier cuisinier du matin.
donc une fois que vous avez défini toutes les contraintes qui modèlent votre problème, vous pouvez commencer à résoudre le problème. Si une solution peut être trouvée (et selon les contraintes le problème peut être infaisable), il vous donnera les affectations d'employés qui produisent le coût hebdomadaire de main-d'œuvre le plus bas.
la programmation linéaire est une technique d'optimisation qui implique des contraintes linéaires et une fonction d'objectif linéaire. Les contraintes sont écrites pour lier l'espace de problème, tandis que la fonction objective est quelque chose que vous tentez de minimiser (ou peut-être de maximiser) qui satisfait les contraintes. algorithme du simplexe est typiquement utilisé pour marcher le long des bords de l'intersection de contraintes pour trouver la valeur minimale (ou maximale) de la fonction d'objectif satisfaisant contrainte.
lors de la configuration d'un problème LP, il est important de s'assurer que les contraintes lient correctement la fonction objective. Il est possible de définir des contraintes qui ne conduisent pas à une solution possible (par exemple x > 1 et-x > 1). Ce n'est plus contraint. Il est également possible de sous-contraindre un problème (par exemple trouver min x tel que x < 1).
Une grande différence (ou au moins, caractéristique)linéaire la programmation est que les contraintes sont modélisées comme linéaire équations, c'est à dire qu'ils sont tous de la forme c_1 x_1 + c_2 x_2.... La section forme standard de l'article de wikipedia donne un assez bon aperçu de ceci.
une autre différence / caractéristique est que la programmation linéaire cherche à maximiser (ou minimiser) une fonction - vous ne pouvez pas efficacement faire l'optimisation multi-objectifs.