Cours de programmation linéaire
<span class="mw-headline" id="Cours_de_programmation_lin.C3.A9aire »>Cours de programmation linéaire
Gregory Glockner: C’est une technologie qui résout les problèmes pour lesquels il existe plusieurs contraintes. Il se compose d’algorithmes de programmation linéaire et logique, il utilise des techniques de propagation de contraintes et exploite les relations logiques qui existent entre les nombreuses variables à isoler les solutions ne sont pas compatibles avec le résultat souhaité (arbre des candidats). Il permet également de résoudre un problème distinct de la modélisation.
Le temps de réponse varie évidemment en fonction du problème de quelques secondes à plusieurs heures pour des questions plus complexes. Par rapport aux algorithmes de recherche personnalisé, le moteur de JSolver est plus rapide, grâce à ses algorithmes de réduction de domaines, et la propagation de contraintes. Notre moteur est un dérivé de la recherche menée sur une douzaine d’années sur les contraintes de la technologie. Son but est de résoudre aussi rapidement que possible à la clientèle de planification problems.A de Seattle m’a dit hier que, après le passage de notre consultant, il a réalisé un temps de réponse divisé par deux par rapport à une solution basée sur des algorithmes de recherche personnalisé. Leur solution n’est pas mauvaise en soi, mais notre moteur, c’est mieux!
À propos de ces modules personnalisés de recherche, Ilog JSolver promesses que lors du fonctionnement d’une entreprise d’une société est changé, il est inutile de réécrire les algorithmes, comment est-ce possible? A la recherche des modules personnalisés il n ‘ya pas de division entre les contraintes et les algorithmes, il est donc très difficile de changer la logique du programme où les règles de changement d’entreprise, et cela arrive souvent. Ilog JSolver juste une couche intercalée entre les algorithmes de modélisation et des contraintes. Selon le type de changement d’affecter le processus d’optimisation, ces modifications sont effectuées sur une heure ou quelques jours pour des révisions plus contraintes importantes.Comment sont définis?
Avant de définir les contraintes à travers une étape de modélisation pour décrire le type d’activité concerné et les contraintes liées à ce programme (nombre de plantes, le nombre de salariés …). Puis vous entrez cette information dans une interface Java se compose d’éléments tels que les types génériques de décisions, le temps … Quel est le délai pour la mise en œuvre en utilisant ILOG JSolver?
Il faut compter entre un et deux mois pour un contraintes de modélisation optimisée, puis quelques mois pour l’intégration et les tests. Selon le type de clientèle est plus ou moins 6 mois.Une nouvelle version d’ILOG Concert Technology est incluse dans JSolver. Il ‘unifie les deux principales techniques d’optimisation, programmation par contraintes et programmation mathématique. Quelle différence voyez-vous entre ces deux types de programmation? La programmation mathématique est bien connue. Son histoire commence aux États-Unis dans les années 40. Son domaine d’expertise est autour des questions de planification à long terme des objectifs économiques à atteindre, par exemple, tout ce qui relève du domaine stratégique dans la programmation fact.Constraint est utilisé à d’autres problèmes ‘actuel’, à court terme. Il s’agit de répondre rapidement à un problème opérationnel . Pour un constructeur automobile, par exemple, il peut être calculé quels modèles de véhicules doivent être conçues principalement sur la ligne de production, avec les contraintes de couleurs, pourquoi pas, de sorte que tout changement de machine est de se perdre dans cette chaîne le moins de temps possible. Quel est le profil de vos clients? Certaines compagnies aériennes (vols de remplissage, service de fret …), les constructeurs automobiles, généralement partout où une gestion de la chaîne d’approvisionnement est cruciale. Air France, la confiance United Airlines, Michelin, PSA Peugeot Citroën, Daimler Chrysler … nous.
Java est capable de couvrir toute l’entreprise. Il est très utile pour intégrer l’optimisation des applications.La plate-forme J2EE permet d’intégrer ILOG JSolver sur les serveurs d’applications tels que BEA WebLogic ou IBM WebSphere.Beyond ses capacités à s’intégrer dans un environnement Web, Java est également très efficace pour développer des applications plus rapidement que dans grâce C / C en partie à sa mémoire la gestion plus facile. Nous notons cependant que les sociétés en train de regarder et d’attendre ce qui va arriver sur le côté de la plate-forme. la technologie Net. Jusqu’à ce que Java n’est que les prochains mois seront intéressants.
Dr. Gregory Glockner a obtenu un doctorat dans les opérations de recherche en «Georgia Institute of Technology, a obtenu son doctorat en 1997 les prix. Avant de rejoindre ILOG Gregory Glockner a travaillé comme analyste de recherche opérationnelle dans l’aviation, et un créateur d’outils statistiques dans le domaine de l’énergie.
Zope (Z Object Publishing Environment) est une plate-forme pour développer son propre droit, à mi-chemin entre le serveur d’applications Web et de système de gestion de contenu. Open Source (potentiellement gratuit), multi-plate-forme et orienté objet, il est souvent considérée comme la prochaine génération des gestionnaires du portail Internet / Intranet.Sa situation dans les entreprises est encore limité, principalement en raison de ses caractéristiques techniques, et la performance contre l’évolutivité ont été ici et là, être mise en doute, mais le fait demeure que l’outil est prometteur et actif dans son développement.
Zope a été développé principalement en Python, avec certains aspects construite en C. L’interface Zope est écrit en HTML 3.2, le rendre fonctionnel sur toutes les plateformes et tous les navigateurs. Le code source facilite également l’installation de la solution sur mesure pour que, avec une certaine connaissance de Python, un langage de script orienté objet très puissant et facile à apprendre.
Zope est divisé en composants, parmi lesquels un serveur Web (la solution aurait pu tout aussi bien avec son propre serveur HTTP avec Apache ou IIS, ou de toute autre avec un module CGI), et que l’interface (HTML) de gestion du site Web, qui comprennent création d’une page, mettre une photo, se connecter à une base de données (Gadfly sa propre base de données ou Oracle, MySQL, Sybase …) ou écrire des scripts (même dans d’autres langues) … D’une certaine manière, les groupes environnementaux en une seule application Zope paquets dispersés au cours de la Apache-MySQL-PHP ou IIS-ASP-SQL Server, tout compte fait …
Zope est construit autour du principe de l’offre (ou publier) les objets plutôt que des pages HTML avec du contenu dynamique. En travaillant avec Zope, il utilise principalement les objets stockés (dans l’objet basé sur Zope). Grâce à l’interface graphique, la manipulation de ces objets est complètement transparent, et de construire une application Web dynamique n’est pas faite que d’un environnement de programmation plus facile.En orientée objet permet web Zope moins linéaire: nous n’avons pas raisonner en termes de page, mais en termes d’objet, chacune avec un comportement, de logique et une présentation différente, de leur interaction qui permet de produire une page Web. Un objet peut être ut
ilisé sur plusieurs pages, être prolongé d’hériter d’un autre objet … Les possibilités sont nombreuses et riches avantages: séparation des données, la logique et la présentation, l’extensibilité, la réutilisabilité …
Optimisation, qui est une branche des mathématiques, un problème d’optimisation linéaire est un problème d’optimisation dans laquelle on minimise une fonction linéaire sur un polyèdre convexe. La fonction de coût et les contraintes peuvent être décrites par des fonctions linéaires (nous devrions dire affine), d’où le nom donné à ces problèmes.Ces cependant ne sont pas linéaires dans le sens que leur solution dépend linéairement de certaines données, une importante non-linéarité est en effet induit par la présence de contraintes d’inégalité de définir (en l’absence de l’inégalité, le problème devient linéaire Dans ce sens, mais est ensuite trivial: soit il n’y a pas de solution, soit tous les points sont des solutions admissibles). Optimisation linéaire (LO) est la discipline qui étudie ces questions.
où est l’inconnu, le vecteur des variables réelles doivent être optimisés, et des données et sont des vecteurs et une matrice. L’inégalité vecteur doit être comprise composante par composante: pour chaque indice i, nous devons have.The ensemble admissible est donc un polyèdre convexe, car il est l’intersection des demi-espaces, pour en nombre fini. Bien sûr, comme toujours dans l’optimisation, un problème de maximisation se réduit à la formulation précédente en minimisant l’opposé de la fonction de coût sur le polyèdre convexe même.
On peut dire que, parmi les problèmes avec contraintes d’inégalité, problèmes d’optimisation linéaire sont simples à résoudre numériquement. Nous savons en effet des algorithmes polynomiaux, ce qui nécessite un certain nombre d’itérations qui est bornée par une fonction polynomiale des dimensions du problème.Typiquement, un algorithme de points intérieurs théoriquement besoin de plus à l’ordre d’itérations pour une formulation du problème similaire à celle donnée ci-dessus.
De nombreux problèmes de recherche opérationnelle peuvent être exprimés comme des problèmes d’optimisation linéaire. Ces problèmes apparaissent aussi comme des sous-produits dans les algorithmes conçus pour résoudre des problèmes plus difficiles.
Dans certains problèmes d ‘OL, il faut aussi que les variables ne prennent que des valeurs entières (contraintes d’intégrité que l’on appelle), ou les valeurs 0 ou 1. C’est ce qu’on appelle problème d’optimisation linéaire en nombres entiers (OLNE). Ces problèmes sont beaucoup plus difficiles à résoudre que les problèmes d’OL avec des variables continues décrites ci-dessus.
L’analyse des problèmes
Définitions
Les formulations du problème
nous disons que le polyèdre (ou d’un problème d’optimisation linéaire avec un tel polyèdre) est écrite sous forme canonique. Lorsque le polyèdre convexe est considéré comme l’intersection de la orthant positive et un sous-espace affine:
Dans la pratique, les problèmes peuvent avoir des contraintes plus variées ou plus comme les contraintes d’égalité formelle ou des contraintes de bornes inférieures et supérieures:
solveurs Bonne pouvez utiliser ces représentations de l’ensemble recevable.Cependant, de nombreuses contraintes et ajoute complique inutilement l’analyse des problèmes d’optimisation linéaire, il se fait généralement sur une formulation simplifiée de l’ensemble, toutefois, admissible à représenter toutes les contraintes affines imaginables. Canonical et formulations standard ont cette propriété de généricité, à condition que nous introduisons les données et les variables supplémentaires. En particulier, un ensemble admissible écrite sous forme canonique peut être représenté sous la forme standard suivante:
le lien entre la variable x et les variables canoniques (u, v, s) de la formulation supérieur à la norme étant de x = u – v. Inversement un ensemble admissible écrit sous forme standard peut être représenté sous la forme canonique suivante:
L’analyse du problème d’optimisation linéaire sont le plus souvent le problème avec l’ensemble admissible est représenté sous forme standard, nous écrivons problème comme suit:
Sommet
Certains algorithmes sont intéressés par les sommets du polyèdre convexe qui nous réduire au minimum un function.In linéaire de l’algorithme simplex, par exemple, toutes les itérations sont des sommets du polyèdre convexe qui est l’ensemble admissible.
Un sommet d’un polyèdre convexe est une face de dimension zéro dans cette série, c’est-à-dire un point que nous pouvons retirer le convexe sans remettre en cause sa convexité; dit encore autrement, c’est précisément la définition, c’est quelque chose qui ne peut être écrite comme la moitié de la somme de deux points distincts de polyèdre convexe. Alors x est un sommet du polyèdre convexe P si et si
Tous les polyèdres ne sont pas nécessairement un sommet. Par exemple, le demi-espace ne fonctionne pas. Toutefois, un polyèdre convexe écrit sous forme standard a toujours et est l’une des raisons pour lesquelles l’algorithme du simplexe est fixé à un problème avec le jeu de l’OL recevable écrit sous cette forme. En outre, il est alors facile à reconnaître par une technique d’algèbre linéaire.
Haut d’un polyèdre convexe de forme classique – Soit un polyèdre convexe et. Ensuite, les suivantes sont équivalentes:
Existence d’une solution
Existence d’une solution – Pour un problème d’optimisation linéaire, les propriétés suivantes sont équivalentes:
Un autre résultat de l’existence de la solution, basée sur précédente et très souvent utilisé, est donnée par le théorème de dualité forte dans la section Propriétés de la dualité.
Comme toutes les solutions de (PL) est un polyèdre convexe écrit sous forme standard, il aura un sommet si elle n’est pas vide et le sommet sera aussi un sommet de l’ensemble admissible de (PL).
Existence d’une solution-sommet – Si le problème (PL) a une solution, il a une solution à un sommet de son jeu possible.
Ce résultat est important pour l’algorithme du simplexe, pour sa part, générant une itération sur ses sommets, est à la recherche d’une solution-top (qui doit exister pour elle d’en trouver un!).
conditions d’optimalité
Déclaration
conditions d’optimalité du problème d’optimisation linéaire (PL) peuvent être obtenus comme un cas particulier de la théorie générale des problèmes d’optimisation différentiable finie conditions dimensions (Karush, Kuhn et Tucker), avec la plus grande simplification de ne pas avoir à faire face à la caractérisation de la contraintes du problème. L’affinité de ce dernier effet qui les rend admissibles (voir locales Affinity (QC-A)), de sorte que nous ne pouvons pas trouver aucune trace de ces questions dans les manuels de l’optimisation linéaire. En outre, grâce à la convexité du problème de l’OL, les conditions ci-dessous sont nécessaires et suffisantes pour l’optimalité.
conditions d’optimalité – Le point est solution de (LP) si et seulement si il existe des vecteurs et tel que
Les variables y et s sont introduits par ces conditions d’optimalité sont appelés multiplicateurs de Lagrange ou variables duales. Les premiers sont liés à des contraintes d’égalité (il est l’un par contrainte), et les secondes aux contraintes de positivité de la variable primale x.As vous aurez l’occasion de voir ci-dessous les variables cachées dans le problème (PL)
jouent un rôle important dans son analyse. Il
Relations (a) exprimer le double admissibilité et la première de ces relations est le gradient en x du Lagrangien du problème, qui est la fonction
Relations (b) exprimer primal d’admissibilité et la relation (c) exprime la complémentarité entre les variables primales et multiplicateurs de x: soit xi ou alors est égale à zéro (ou les deux), voir aussi ci-dessous.
Ces conditions d’optimalité ont des usages multiples. Ils permettent notamment de concevoir des algorithmes primal-dual (ainsi caractérisé, car ils utilisent tellement de variables primales et duales) de résolution. Ils établissent également des propriétés différentes des problèmes de LO.
solutions produit cartésien – toutes les solutions primal-dual est un produit cartésien:
En d’autres termes, si (x1, y1, s1) et (x2, y2, s2) sont des solutions de primal-dual, alors (x1, y2, s2) est également une solution primale-duale.
dualité de Lagrange
Le problème double standard
La dualisation lagrangienne est une technique utilisée pour introduire un double problème d’un problème d’optimisation. Si l’on considère le problème d’optimisation (PL), la polarisation double problème de Lagrange conduit à la norme suivante
technique de polarisation
On pourrait poser le problème dual du problème d’optimisation linéaire plus général, mais nous préférons ne donner ici la technique utilisée pour mettre en place, qui va faire face dans tous les cas. Soit le problème (PL), appelé ici primordiale.
L’égalité reflète la convention que la borne inférieure sur un ensemble vide, alors si il n’y a pas satisfaisant Ax = b, on trouve dans les deux branches. Il était bien écrit que le problème primal (on enlève les supports, en gardant à l’esprit que le sens est de donner à celui-ci-dessus):
Ils disent que nous avons dualisées la contrainte d’égalité Ax = b, parce que c’est avec elle qui a été impliqué dans la construction de la technique de dualisation lagrangienne ci-dessus.
propriétés de dualité
C’est ce qu’on appelle la relation dualité faible.Pour la technique de dualisation lagrangienne décrit ci-dessus, nous obtenons la relation suivante entre primale et duale des valeurs optimales.
Dans le cas de l’optimisation linéaire, cette inégalité est obtenue par simple calcul: prenez un point x primal admissible, un double point y admissibles, on en déduit que, et nous concluons en prenant le coin supérieur gauche et le droit infimum.
Ils disent qu’il n’y a pas d’écart si la dualité. Une optimisation linéaire, il est rare d’avoir un écart de dualité. La seule possibilité est que nous avons (à savoir le problème primal n’est pas possible) et (le double problème n’est pas possible). Ceci est une conséquence du résultat existence de solution dans la LO (voir ci-dessus) et le résultat de dualité suivantes forte.
L’implication 1 → 2 [resp. 1 → 3] est souvent utilisé pour montrer que le resp primitive [problème. ] A un double solution.To ce faire, il suffit de vérifier que les problèmes primal et dual sont réalisables, un fait qui peut être trouvé sans difficulté dans certains cas.
Integer optimisation linéaire
Un problème d’optimisation linéaire en nombres entiers n’est pas un problème d’optimisation linéaire dans le sens où son nom de domaine n’est pas recevable un polyèdre, mais un ensemble discret de points.Toutefois, elle peut être décrite comme un problème de l’OL qui est ajoutée la contrainte supplémentaire que certaines variables peuvent prendre des valeurs entières. Nous distinguons l’optimisation linéaire mixte avec variables entières et continues problème dans son ensemble avec toutes les variables entier.
Le OLNE est NP-complet que de nombreux problèmes NP-complets peuvent être exprimés en OLNE problèmes (par exemple, trouver une stabilité dans un graphe G = (V, E) signifie qu’il faut trouver un bon vecteur pour chaque bord). Les algorithmes décrits ci-dessus pour l’OL ne résout pas les problèmes OLNE.Algorithmically donc résoudre un problème OLNE est beaucoup plus difficile que d’un problème de l’OL qui joue un rôle crucial dans la résolution pour deux raisons principales. Premièrement, la relaxation continue d’un OLNE problème (c’est le OLNE problème sans contraintes d’intégrité) est un problème de LO qui peuvent être résolus de manière efficace et fournir ainsi un marqueur double (dans le sens de non-réalisable). Les algorithmes de résolution de problèmes OLNE, comme la branche et des algorithmes consolidés sont fondés sur cette relaxation continue afin de minimiser la liste des solutions.Deuxièmement, l’optimisation théorème / Séparation Grötschel, Lovasz et Schrijver résout des problèmes pratiques par des entiers OL que nous connaissons un polyèdre bonne description (c’est-à-dire que nous pouvons séparer les contraintes en temps polynomial). C’est le principe de fonctionnement de la méthode des plans sécants.
Domaines d’application
Ils sont extrêmement variés: l’optimisation d’un chemin, la forme d’un objet, un prix de vente d’une réaction chimique, le contrôle du trafic aérien, les performances d’un dispositif, le fonctionnement d’un moteur, le chemin de fer de gestion en ligne, le choix des investissements économiques, construction d’un navire, etc. L’optimisation de ces systèmes, on trouve une configuration idéale pour obtenir un effort de gagner, temps, argent, énergie, matières premières, ou la satisfaction.
Très loin d’être exhaustifs, ces exemples montrent la variété des formulations et préfigure les divers outils mathématiques capables de résoudre ces problèmes.
Méthodes numériques
Simplifications
Le problème d’origine est remplacé par un problème équivalent. Par exemple, un changement de variables pour décomposer le problème en sous-problèmes, ou la substitution d’inconnues pour réduire le nombre.
La technique des multiplicateurs de Lagrange permet de surmonter certaines contraintes (comme l’égalité); cette méthode est en effet d’instaurer des sanctions plus en plus que la solution se rapproche de la contrainte. Un algorithme dû à Hugh Everett pouvez mettre à jour systématiquement les valeurs des multiplicateurs à chaque itération pour assurer la convergence. Ce fut également l’interprétation large de ces multiplicateurs à appliquer à toutes les fonctions qui ne sont ni continue ni dérivable. Lambda exprime un facteur de pénalité (concept du coût marginal d’une contrainte en économie).
Trouver des zéros du gradient
De nombreuses méthodes et les algorithmes peuvent trouver un zéro de la dérivée de f (certaines sont spécifiques aux fonctions d’une variable) ou de son gradient. Ils valablement s’appliquer dans des situations où les contraintes sur les A ne sont pas très actifs.
Cas particulier: Lorsque f est polynomiale de degré 2 dans ses arguments (forme linéaire et quadratique) et sans contrainte, d’annuler les montants gradient pour résoudre un système linéaire (voir Catégorie: Analyse numérique matricielle).
Direct méthodes d’analyse
Dans cette catégorie, la plupart des algorithmes généraux s’appliquent à des situations où les contraintes sur les A ne sont pas très actifs. Elles sont basées sur quelques idées dominantes:
Techniques d’optimisation combinatoire
Ces techniques posent des problèmes dont certains (au moins) l’ensemble A variables prennent des valeurs discrètes. Ils se trouvent sous
Heuristiques et métaheuristiques
Pour résoudre des problèmes difficiles (par exemple celles avec de nombreux extrema locaux pauvres), les techniques ont été développées pour déterminer les solut
ions qui ne sont pas strictement optimale, mais sont proches. Ces méthodes sont généralement fondées sur des éléments physiques, biologiques, socio-psychologiques ou appelez au hasard. Les domaines d’application sont vastes et s’étendent souvent bien au-delà des problèmes pour lesquels ils ont été initialement conçus.
techniques d’optimisation multiobjectif
Ces questions ne relèvent pas du cadre strict de la définition donnée ci-dessus: une solution réalisable de A, la fonction objectif n’est pas d’associer une valeur numérique, mais un point d’un ensemble qui est le plus souvent associé à un vecteur. L’objectif est d’optimiser simultanément toutes les composantes de ce vecteur. On peut aussi voir l’optimisation multi-objectifs comme un ensemble de problèmes d’optimisation impliquant les mêmes paramètres, avec des objectifs parfois contradictoires, et qu’il cherche à résoudre au mieux.
En général, la zone qui est exprimée dans le vecteur solution a un ordre partiel impliquant les critères de dominance (par exemple en relation avec la frontière de Pareto).La résolution est de trouver une solution dont l’objectif est dominé par un autre.
Horaires