Dans de nombreux problèmes, les variables de décision doivent être astreintes à ne prendre que des valeurs entières. Par exemple, dans un problème de planification globale de la production, on ne peut pas projeter de fabriquer 2,3 bateaux. Il s'agit là d'un problème linéaire en nombres entiers et non d'un programme linéaire continu.
Pour résoudre un programme en nombres entiers, la première idée qui vient à l'esprit est de relaxer (négliger) les contraintes d'intégrité et d'arrondir (ou de tronquer) la solution du problème continu résultant. Malheureusement, cela peut aboutir ou bien à des solution non réalisables ou bien à des solutions éloignées de l'optimum recherché.
Ainsi, de nombreuses méthodes ont été développées pour résoudre les programmes en nombres entiers.
Pour ce qui est de la programmation non linéaire, son objet est l'étude des problèmes d'optimisation non linéaire et la conception des méthodes pour les résoudre. Par convention, il s'agit des problèmes d'optimisation dans un univers certain ; ceux d'optimisation dans un univers incertain font l'objet de la programmation stochastique.
Bien que le terme programmation non linéaire soit apparu pour la première fois, semble-t-il, en 1950 dans le titre de l'article de M. SLATER, « Lagrange Multipliers Revisited : A Contribution to Nonlinear Programming », les débuts de cette branche de mathématique sont nettement plus anciens. Toutefois, c'est probablement KUHN et TUCKER qui ont le plus marqué l'histoire de la programmation non linéaire par leur article de 1951 intitulé « Non linear Programming ».
Il fallut attendre les années 1970 pour assister au foisonnement des publications dans ce domaine. La plupart de ces publications présentent des méthodes pour résoudre des problèmes non linéaires. Ceci s'explique par le fait que l'ultime objectif de la programmation non linéaire est de résoudre ces problèmes.
[...] Il est évident graphiquement que le point H représente la solution entière optimale. Remarquons finalement que la valeur optimale de la fonction économique dans un programme en nombres entiers est toujours plus petite ou égale à la valeur optimale de la fonction économique du programme linéaire correspondant. Dans la pratique, la méthode graphique est inutilisable dès que le problème a plus de deux variables. Il existe de nombreux algorithmes pour la résolution des programmes en nombres entiers. Ces méthodes ont été développées en tenant compte des caractéristiques de fonctionnement des ordinateurs. [...]
[...] Toutefois, c'est probablement KUHN et TUCKER qui ont le plus marqué l'histoire de la programmation non linéaire par leur article de 1951 intitulé Non linear Programming Il fallut attendre les années 1970 pour assister au foisonnement des publications dans ce domaine. La plupart de ces publications présentent des méthodes pour résoudre des problèmes non linéaires. Ceci s'explique par le fait que l'ultime objectif de la programmation non linéaire est de résoudre ces problèmes. Sommaire Chapitre 1 : La programmation linéaire en nombres entiers A. [...]
[...] En effet, étant donné une contrainte du type ( 6.31 le point représentatif de la solution optimale a toujours toutes les variables hors base (apparaissant dans ( 6.31 nulles. Par conséquent, ce point ne satisfait pas ( 6.31 ) et se trouve coupé de l'ensemble des solutions réalisables. De plus, si un point entier initial (x1 et x2 entiers) était coupé de l'ensemble des solutions réalisables, l'inégalité ( 6.31 ) ne serait pas satisfaite; par conséquent le membre de gauche de ( 6.31 ) serait strictement positif et inférieur à donc fractionnaire. [...]
[...] Nous ne pourrons rentrer dans le détail de ces difficultés techniques, mais elles constituent des limitations sérieuses de tous ces algorithmes. Nous allons expliquer le principe des deux algorithmes principaux: l'algorithme du plan sécant et la méthode par séparations et évaluations progressives. C. L'algorithme du Plan Sécant L'algorithme du plan sécant, développé par R. Gomory en 1958, est l'une des premières méthodes proposées pour la résolution des programmes en nombres entiers. La méthode utilise un algorithme de programmation linéaire pour déterminer une solution optimale sans tenir compte des contraintes de solution entière. [...]
[...] Position du problème Dans la programmation linéaire les variables de la fonction objectif x1,x ,xn considérées étaient à valeurs réelles. Or, dans certains problèmes, on peut se trouver dans l'une des deux situations suivantes : Toutes les variables x1,x ,xn ne peuvent prendre que des valeurs entières (par exemple lorsque ces variables représentent un nombre d'unités non fractionnables telles que machine, unité produites, nombre d'annonces publicitaire, etc.) Les programmes linéaires correspondants sont dits programmes linéaires en nombres entiers. Certaines de ces variables x1,x ,xn ne peuvent prendre que des valeurs entières, les autres variables étant à valeurs réelles. [...]
Référence bibliographique
Source fiable, format APALecture en ligne
avec notre liseuse dédiée !Contenu vérifié
par notre comité de lecture
