Module D108 : Programmation mathématique et optimisation
Programmation linéaire
Programmation linéaire en nombres entiers

Pourquoi les contraintes d’intégrité ?
Effet des contraintes d’intégrité
Forme standard d’un programme linéaire en nombres entiers
Applications
Méthode par séparation et évaluation
Exercices


Auteur(s) : Nasser SAHEB;- IUP Miage Bordeaux
Date de dernière modification : 30 Janvier 2006

Pourquoi les contraintes d’intégrité ?

La méthode du simple permet de trouver la solution optimale d’une fonction linéaire économique face à des contraintes du type linéaire. Elle autorise des variables de signes quelconques et peut aussi les astreindre à être positives (ou négatives). Dans beaucoup de circonstances réelles, les variables ne peuvent être que de type entiers. Il arrive en effet fréquemment que le choix imposé doit respecter la règle d’intégrité. Malheureusement ce type de contraintes ne peut pas être traité directement par l’algorithme de simplexe.

Exemple illustratif. :  Un produit es disponible dans des paquets de 20kg de prix de 50€ ou des paquets de 40kg de prix de 80€. Un client, qui a d’au moins de 100kg du produit cherche à en acheter au moindre coût possible. La contrainte d’intégrité qui s’oppose tout naturellement ici, implique qu’il ne peut pas en acheter la moitié ou deux tiers de paquet. Soient et les nombres respectifsde paquets que le client va acheter. Le programme linéaire suivant formalise le problème :

minimiser

sous :

Effet des contraintes d’intégrité

Dans le problème illustratif, si l’on enlève la contrainte d’intégrité de le problème devient très simple. En effet puisque le prix du produit dans le paquet de 20kg est de 2,5 €/kg et dans le paquet de 50kg est de 2€/kg, le client pourrait acheter 2,5 paquets de contenance de 80kg et cela lui coûterait . Malheureusement, la contrainte d’intégrité lui impose de remplacer le nombre 2,5 par 3, et cela lui coûterait Or, il existe une solution moins coûteuse : 2 paquets de 40kg et un paquet de 20kg, coûtant au total de 130€.

Cet exemple simple montre que l’arrondissement de la solution optimale d’un programme linéaire et nombres réels n’aboutit pas nécessairement à une solution optimale pour le même problème avec la contrainte d’intégrité.

On peut être tenté de confirmer maintenant que du moment où la recherche d’un solutions optimale pour un programme linéaire en nombre d’entrées se fait dans un ensemble plus restreint, la méthode de résolution doit être plus simple que ce même problème sans la contrainte d’intégrité. C’est une confirmation tout à fait erronée. En effet, alors que l’algorithme du simplexe fournit une solution satisfaisante pour les programmes linéaire en nombres réels, on démontre que le problème de programmation linéaire en nombres entiers s’apparente à une classe de problème, appelés problèmes NP-complets, qui sont considérés comme des problèmes algorithmiquement difficiles. Il s’agit d’un ensemble de problèmes de décision qui ont été démontrés être polynomialement équivalents. On ne connaît pas d’algorithmes de décision en temps polynomial pour ces problèmes, sans avoir prouvé que la difficulté est de nature intrinsèque. Quoiqu’il en soit on admet en général que ces problèmes et, donc, celui de programmation linéaire en nombres entiers est de nature difficile.

Forme standard d’un programme linéaire en nombres entiers.

Tout programme linéaire en nombres entiers s’écrit sous la forme :

maximiser

sous :

c est un vecteur de une matrice à m lignes et n colonnes et On peut transformer un problème de maximisation ou un problème avec contraintes de type (au lieu de ) en un problème sous cette forme, en appliquant les méthodes utilisées en programmation linéaire.

Applications

Les problèmes d’optimisation, où des contraintes d’intégrité interviennent, ont un champ d’application très vaste. On peut en énumérer, à titre d’exemple, production en séries, allocations de ressources, localisation des sites, exploitations des mimerais , investissement, et programme des vols d’avions. D’autres applications de programmes linéaires se trouvent en calculs scientifiques tels que les problèmes d’optimisation combinatoires dans un contexte d’ingénierie ou mathématico-physique.

Problème du sac-à-dos

Une instance très particulière des programmes linéaire qui, malgré sa simplicité apparente, se classifie dans les problèmes difficiles est celui du sac-à-dos (knapsack en anglais).

Ce problème s’énonce ainsi :

Un randonneur peut faire un certain nombre de choix parmi les n nourritures disponibles numérotées Chaque nourriture i possède un volume et sa valeur nutritive . Le sac à dos du randonneur a une capacité à ne pas dépasser. Le randonneur souhaite alors à faire un menu qui maximise la valeur nutritive totale. Désignons par la quantité de la nourriture i que le randonneur va prendre (si  la nourriture i n’est pas choisie, si elle est choisie). Le problème du sac-à-dos s’écrit alors :

maximiser

sous :

Il existe une variante de ce problème légèrement plus générale : on suppose que toute nourriture j est disponible en quantité ( entier). Les contraintes dans cette invariante deviennent alors :

La version initiale est appelée par certains auteurs ‘‘programme linéaire en variables bivalentes’’. Ces deux variantes de problème du sac-à-dos et d’autres variables sont liées à un bon nombre de problèmes d’optimisation combinatoire. Etant tous liés au problèmes difficiles. A bondonnant une recherche entièrement algébrique, les informaticiens se limitent à des méthodes de résolutions ‘‘approximatives’’, appelées heuristiques pour aborder ces problèmes dans toute leur généralité. Ces recours ne sont pas tout à fait satisfaisants, dans la mesure où l’heuristique ne fournit pas toujours la solution exacte et elle n’est pas non plus à l’abri d’une complexité exponentielle.

Il existe de nombreuses méthodes, qui avec de divers degré de succès, s’appliquent aux programmes linéaires en variables aléatoires. Les techniques les plus populaires sont fondées sur séparation et évaluation (branch and bound en anglais).

Méthode par séparation et évaluation

Soit à résoudre le programme :

maximiser

sous :

Soit z la valeur maximum de la fonction objective .

Etape 1. On considère le programme linéaire relaxé (i.e. sans contrainte d’intégrité).

La méthode simplexe s’applique et l’on peut trouver une solution optimale ().

est évidemment un majorant de dans une initial. Il n’est pas nécessairement  réalisable, puisque la solution trouvée  peut ne pas respecter les contraintes d’intégrité.

Etape 2. Si on considère deux programmes linéaires relaxés, l’un avec la contrainte supplémentaire et l’autre avec (appelée branche gauche et branche droite respectivement). La résolution éventuelle de chacune des branches (s’elle admet une solution) permet de trouver deux solutions plus restrictives (mais pas nécessairement réalisables).

Etape 3. On continue l’étape 2 pour une des variables qui n’a pas reçu une valeur entière et cela pour chacune des branches.

Il est évident qu’à chaque branchement les valeurs trouvées pour z seront plus petites et donc, en descendant une branche de l’arborescence, on finira soit par l’irréalisablité du programme linéaire relaxé avec des contraintes associées au branchement soit par une solution entière optimale.

Une comparaison finale des branches abouties permet de trouver la solution optimale entière recherchée.

Exemple 1. Soit :

maximiser

sous :

\begin{figure}
\begin{center}
\input{test.pstex_t}
\end{center}
\end{figure}
Solution optimale

Exemple 2. (Une application de la programmation dynamique)

L’exemple suivant est emprunté à D. Sills. Soit le problème du sac-à-dos :

maximiser

sous :

On suppose et sont positifs et Nous utilisons la méthode de programmation dynamique pour aborder ce problème.

Cherchons dans un premier temps la solution optimale du problème relaxé. Soit cette solution et soit la valeur de la fonction objective pour cette solution. Désignons par le vecteur formé des valeurs entières par défaut de est alors une solution réalisable du problème. Donc la valeur optimale recherchée se trouve dans l’intervalle

Soit maintenant est donc la valeur maximum de la fonction objective, lorsqu’on remplace et Calculons pour tenant compte de et

On peut poser La formule pour correspond au fait que le problème du sac-à-dos pour un volume à ne pas dépasser consiste à remplir le sac d’abord d’un volume et ajouter ensuite un article de volume  ; on choisit donc l’indice j qui maximise La deuxième solution pour est la solution optimale.

Exemple numérique.

Soit

maximiser

sous :

Solution : Dans le problème relaxé le rapport ‘‘quantité-prix’’, montre que le randonneur a l’intérêt de prendre la 1ère nourriture au maximum et cela fournit la solution , donnant la valeur à la fonction objective. La solution arrondie vaut alors  donnant la valeur 44 à la fonction objective. Donc la valeur optimale de doit satisfaire

Appliquons maintenant l’algorithme de programmation dynamique à cette instance du problème du sac-à-dos.

On en déduit alors que la valeur nutritive maximale que la randonneur peut placer dans son sac-à-dos est de 45, obtenu en choisissant le menu



 


 

Exercices

Questionnaire de compréhension immédiate

Questionnaire à choix multiple

K exercices