Abstract FR:

Notre travail concerne la résolution des problèmes de programmation fractionnaire en variables bivalentes, qui consistent à optimiser un objectif mis sous la forme d'un rapport de deux fonctions, soumis à un ensemble de contraintes. La première partie (chapitres 1 et 2) propose un tour d'horizon de la littérature sur les problèmes de programmation fractionnaire. De nouveaux résultats théoriques et algorithmiques relatifs à la dualité et aux heuristiques lagrangiennes font l'objet de la deuxième partie (chapitres 3, 4 et 5). Dans le chapitre 3, les problèmes envisagés sont modélisés sous la forme de la maximisation en variables 0-1 d'un objectif hyperbolique (rapport de deux fonctions affines) soumis à des contraintes linéaires. Pour ces modèles qui sont à objectif non linéaire et non concave, une nouvelle décomposition lagrangienne est décrite. Dans le chapitre 4, on se propose d'étendre ce résultat à une classe plus large, celle des programmes fractionnaires concaves-convexes qui consistent en la maximisation d'un objectif rapport d'une fonction concave et d'une fonction convexe soumis à des contraintes convexes. Pour ces modèles à objectif non lineaire et non concave (et non convexe), nous proposons une décomposition lagrangienne construite sur un principe identique à celui du chapitre 3. Le but du chapitre 5 est la construction de deux heuristiques lagrangiennes fournissant des minorants de la valeur d'un programme hyperbolique en variables 0-1 en exploitant les solutions duales engendrées par une méthode de sous-gradient appliquée tour à tour sur les deux duals lagrangiens obtenus par relaxation lagrangienne ou par décomposition lagrangienne (chapitre 3). La troisième partie constitue la partie experimentale de notre travail, dediée a la resolution du probleme du sac a dos hyperbolique en variables 0-1: le chapitre 6 traite de la résolution du problème de programmation hyperbolique sans contraintes ; l'application au problème du sac à dos hyperbolique en variables 0-1 des outils algorithmiques décrits aux chapitres 3,5 et 6 est l'objet du chapitre 7