La programmation linéaire
<span class="mw-headline" id="La_programmation_lin.C3.A9aire »>La 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 utilisé sur plusieurs pages, être p
rolongé 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.
Algorithmes
algorithme Simplex
L’algorithme du simplexe, développé par Dantzig de 1947, est une méthode de résolution finie d’une émission de LO. Les moyens de durée déterminée d’un nombre fini d’étapes de l’algorithme trouve une solution ou de montrer que le problème n’est pas borné ou montre que le problème n’est pas possible (les trois seules possibilités pour un problème de LO voir ci-dessus). L’algorithme a une interprétation géométrique simple. L’itération sont des sommets de l’ensemble admissible (un polyèdre convexe).Un sommet, l’algorithme détermine un bord (face à la dimension 1) de l’ensemble recevable le long de laquelle la fonction de coût diminue et prend une nouvelle itération du pic à la fin de l’arête sélectionnée (ce qu’on appelle pivotement). Il peut y avoir plusieurs arêtes de diminution de la fonction de coût. La règle du coût minimum réduit, l’algorithme choisit un bord le long de laquelle la fonction de coût diminue le plus.
Bien que l’algorithme du simplexe est souvent efficace dans la pratique ce n’est pas un algorithme polynomial: en fait, il est exponentielle dans le pire des cas. Klee et Minty (1972) ont en effet construit un problème où l’ensemble admissible est un ‘cube’ d’un peu déformée, pour laquelle l’algorithme du simplexe visites sommets 2n de l’ensemble recevable. Variations de l’exemple de Klee et Minty sont disponibles pour la plupart des règles de pivoting.It ne prendre une décision à chaque itération basée sur des informations locales (par exemple un coût réduit), avec des effets globaux (le nombre d’itérations dépend du nombre de sommets visité avant d’arriver à une solution) qui n’atteint pas l’algorithme polynomialité. Ce contre-exemple a stimulé la recherche d’algorithmes qui peuvent être polynôme en optimisation linéaire, un problème considéré comme assez simple d’admettre un tel algorithme.Cela a conduit à des algorithmes de points intérieurs, qui ont ensuite été étendu à tous les problèmes d’optimisation (éventuellement non convexe).
L’efficacité souvent observé l’algorithme du simplexe est justifiée par le fait aujourd’hui la preuve de son polynomialité en moyenne, pour les données distribuées au hasard en fonction de diverses lois de probabilité, voir Borgwardt (1982, 1987), Smale (1983), Megiddo (1987), Sharma ( 1987).
algorithmes de points intérieurs
Le premier algorithme polynomial pour les LO a été proposé par Leonid Khachiyan (fr) dans 1979.It est basé sur la méthode de l’ellipsoïde en optimisation non linéaire précédemment proposée par Naum Shor Z. (fr). Cette méthode est elle-même une généralisation de la méthode de l’ellipsoïde en optimisation convexe due à Arkadi Nemirovski (John von Neumann Prix 2003), et David B. Yudin. L’efficacité de l’algorithme de Khachiyan est décevante: l’algorithme du simplexe est presque toujours plus rapide. Toutefois, ce résultat a encouragé la recherche sur les méthodes de point intérieur.
En 1984, Narendra Karmarkar (en ligne) a la méthode projective. C’est le premier algorithme efficace en théorie et en pratique. complexité dans le pire cas est polynomiale et des expériences sur des problèmes concrets montrent que la méthode peut raisonnablement être comparée à l’algorithme du simplexe.
Depuis lors, plusieurs méthodes de point intérieur ont été proposées et studied.Unlike l’algorithme du simplexe dont les sommets sont itération du polyèdre convexe défini par des contraintes, donc appartenant à la limite de ce polyèdre, les méthodes de point intérieur (dans leur version de qualification) génère une itération à l’intérieur relative de tous admissibles. L’un des plus Courrent en œuvre est l’algorithme prédicteur-correcteur.
Algorithmes pour des problèmes de grande
Algorithmes
algorithme Simplex
L’algorithme du simplexe, développé par Dantzig de 1947, est une méthode de résolution finie d’une émission de LO. Les moyens de durée déterminée d’un nombre fini d’étapes de l’algorithme trouve une solution ou de montrer que le problème n’est pas borné ou montre que le problème n’est pas possible (les trois seules possibilités pour un problème de LO voir ci-dessus). L’algorithme a une interprétation géométrique simple. L’itération sont des sommets de l’ensemble admissible (un polyèdre convexe). Un sommet, l’algorithme détermine un bord (face à la dimension 1) de l’ensemble recevable le long de laquelle la fonction de coût diminue et prend une nouvelle itération du pic à la fin de l’arête sélectionnée (ce qu’on appelle pivotement). Il peut y avoir plusieurs arêtes de diminution de la fonction de coût.La règle du coût minimum réduit, l’algorithme choisit un bord le long de laquelle la fonction de coût diminue le plus.
Bien que l’algorithme du simplexe est souvent efficace dans la pratique ce n’est pas un algorithme polynomial: en fait, il est exponentielle dans le pire des cas. Klee et Minty (1972) ont en effet construit un problème où l’ensemble admissible
est un ‘cube’ d’un peu déformée, pour laquelle l’algorithme du simplexe visites sommets 2n de l’ensemble recevable. Variations de l’exemple de Klee et Minty sont disponibles pour la plupart des règles de pivoting.It ne prendre une décision à chaque itération basée sur des informations locales (par exemple un coût réduit), avec des effets globaux (le nombre d’itérations dépend du nombre de sommets visité avant d’arriver à une solution) qui n’atteint pas l’algorithme polynomialité. Ce contre-exemple a stimulé la recherche d’algorithmes qui peuvent être polynôme en optimisation linéaire, un problème considéré comme assez simple d’admettre un tel algorithme. Cela a conduit à des algorithmes de points intérieurs, qui ont ensuite été étendu à tous les problèmes d’optimisation (éventuellement non convexe).
L’efficacité souvent observé l’algorithme du simplexe est justifiée par le fait aujourd’hui la preuve de son polynomialité en moyenne, pour les données distribuées au hasard en fonction de diverses lois de probabilité, voir Borgwardt (1982, 1987), Smale (1983), Megiddo (1987), Sharma ( 1987).
algorithmes de points intérieurs
Le premier algorithme polynomial pour les LO a été proposé par Leonid Khachiyan (fr) dans 1979.It est basé sur la méthode de l’ellipsoïde en optimisation non linéaire précédemment proposée par Naum Shor Z. (fr). Cette méthode est elle-même une généralisation de la méthode de l’ellipsoïde en optimisation convexe due à Arkadi Nemirovski (John von Neumann Prix 2003), et David B. Yudin. L’efficacité de l’algorithme de Khachiyan est décevante: l’algorithme du simplexe est presque toujours plus rapide. Toutefois, ce résultat a encouragé la recherche sur les méthodes de point intérieur.
En 1984, Narendra Karmarkar (en ligne) a la méthode projective. C’est le premier algorithme efficace en théorie et en pratique. complexité dans le pire cas est polynomiale et des expériences sur des problèmes concrets montrent que la méthode peut raisonnablement être comparée à l’algorithme du simplexe.
Depuis lors, plusieurs méthodes de point intérieur ont été proposées et étudiées.Contrairement à l’algorithme du simplexe dont les sommets sont itération du polyèdre convexe défini par des contraintes, donc appartenant à la limite de ce polyèdre, les méthodes de point intérieur (dans leur version de qualification) génère une itération à l’intérieur relative de tous admissibles. L’un des plus Courrent en œuvre est l’algorithme prédicteur-correcteur.
Algorithmes pour des problèmes de grande
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. Algorithmique ainsi 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.Secondly, le théorème de l’optimisation / séparation Grötschel, Lovasz et Schrijver résout des problèmes pratiques par des entiers OL que nous connaissons une polyédriques 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.
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).
Existe
nce 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.
Applications
L’optimisation linéaire est principalement utilisée pour résoudre des problèmes d’optimisation à moyen et à long terme (problèmes stratégiques et tactiques dans le vocabulaire de la recherche opérationnelle). Les domaines d’application de ces problèmes sont nombreux tant dans la nature des problèmes (planification et contrôle de la production, réseaux de distribution) que dans les secteurs industriels: la fabrication, de l’énergie (pétrole, gaz, électricité, nucléaire), transport (aérien, routier et ferroviaire) , des télécommunications, de la foresterie, de la finance.
‘