• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Robustesse et dualité en programmation linéaire

Murat, Cécile; Gabrel, Virginie (2008), Robustesse et dualité en programmation linéaire. https://basepub.dauphine.fr/handle/123456789/4445

View/Open
notedeRLamsade41.pdf (264.6Kb)
Type
Document de travail / Working paper
Date
2008
Publisher
Université Paris-Dauphine
Series title
Note du LAMSADE
Series number
41
Published in
Paris
Pages
26
Metadata
Show full item record
Author(s)
Murat, Cécile
Gabrel, Virginie
Abstract (FR)
Dans cet article, nous étudions un programme linéaire dans lequel les valeurs des second membres des contraintes sont entachées d’incertitude et d’indétermination. Cette incertitude est modélisée par un intervalle, c’est- à-dire que le second membre de chaque contrainte peut prendre une valeur quelconque dans un intervalle indépendamment des autres contraintes. Dans la littérature, les programmes linéaires, dont les coefficients des variables dans la fonction objectif sont incertains et approchés par un intervalle, ont été largement étudiés. Il s’agit alors de déterminer une solution qui résiste au mieux aux incertitudes, une telle solution étant qualifiée de robuste. Pour cela, les critères classiques du pire cas et du regret maximum sont appliqués pour définir différentes versions robustes du programme linéaire de départ. Des modèles de robustesse plus récents, généralisant le critère du pire cas (dû à Bertsimas et Sim), ont également été proposés. Le sujet de ce papier est d’établir des correspondances entre programmes linéaires avec second membres incertains et programmes linéaires avec coefficients incertains dans la fonction objectif en utilisant la dualité classique. Nous montrons que le transfert de l’incertitude des second membres des contraintes vers les coefficients de la fonction objectif est possible en établissant des nouvelles relations de dualité entre différentes versions robustes. Lorsque les second membres des contraintes sont approchés par des intervalles, nous proposons également une extension du modèle de Bertsimas et Sim et montrons que le critère du regret maximum est équivalent au critère du pire cas.
Abstract (EN)
In this article, we consider a linear program in which the right hand sides of the constraints are uncertain and inaccurate. This uncertainty is represented by intervals, that is to say that each right hand side can take any value in its interval regardless of other constraints. In the literature, linear programs with uncertain objective function coefficients have been widely studied. The problem is then to determine a robust solution which is satisfactory for all possible coefficient values. Classical criteria like the worst case and the maximum regret are applied to define different robust versions of the initial linear program. More recently, Bertsimas and Sim have proposed a new model which generalizes the worst case criterion. The subject of this paper is to establish the relationships between linear programs with uncertain right hand sides and linear programs with uncertain objective function coefficients using the classical duality theory. We show that the transfer of the uncertainty from the right hand sides to the objective function coefficients is possible by establishing new dual relationships. When the right hand sides are approximated by intervals, we also propose an extension of the Bertsimas and Sim’s model and we show that the maximum regret criterion is equivalent to the worst case criterion.
Subjects / Keywords
maximum regret criteria; programmation linéaire; second membre incertain; robustesse; critère du pire cas; critère du regret maximum; linear programming; interval right hand side; robustness analysis; worst case criteria

Related items

Showing items related by title and author.

  • Thumbnail
    La pw‐robustesse : pourquoi un nouveau critère de robustesse et comment l’appliquer ? 
    Gabrel, Virginie; Murat, Cécile; Thièle, Aurélie (2013) Communication / Conférence
  • Thumbnail
    Nouvelle approche pour traiter des problèmes linéaires avec seconds membres incertains. Application au problème de transport 
    Remli, Nabila; Gabrel, Virginie; Murat, Cécile (2010) Communication / Conférence
  • Thumbnail
    New models for the robust shortest path problem: complexity, resolution and generalization 
    Gabrel, Virginie; Murat, Cécile; Wu, Lei (2013) Article accepté pour publication ou publié
  • Thumbnail
    A robust p-Center problem under pressure to locate shelters in wildfire context 
    Demange, Marc; Gabrel, Virginie; Haddad, Marcel Adonis; Murat, Cécile (2020) Article accepté pour publication ou publié
  • Thumbnail
    Robust location transportation problems under uncertain demands 
    Gabrel, Virginie; Lacroix, Mathieu; Murat, Cécile; Remli, Nabila (2014) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo