Mausser H and Laguna M A new mixed integer formulation for the maximum regret problem. Int Trans Opl Res 5 : — A heuristic to minimax absolute regret for linear programs with interval objective function coefficients.
Minoux M Robust linear programming with right hand side uncertainty, duality and application. Encyclopedia of Optimization. Springer: USA, pp. Chapter Google Scholar. Roy B Lavoisier : Paris, pp 35— Soyster A Convex programming with set-inclusive constraints and applications to inexact linear programming. Opns Res 21 : — Vincke P Robust solutions and methods in decision-aid. J Multi-Criteria Decis Anal 8 : — Download references. The anonymous referee is gratefully acknowledged for his comments on a first version of the paper.
You can also search for this author in PubMed Google Scholar. Correspondence to V Gabrel. Reprints and Permissions. Gabrel, V. Robustness and duality in linear programming. J Oper Res Soc 61, — Download citation. Received : 01 May Accepted : 01 April Published : 26 August Issue Date : 01 August Anyone you share the following link with will be able to read this content:. Sorry, a shareable link is not currently available for this article. Provided by the Springer Nature SharedIt content-sharing initiative.
Skip to main content. Search SpringerLink Search. Abstract In this paper, we consider a linear program in which the right hand sides of the constraints are uncertain and inaccurate.
Figure 1. References Averbakh I and Lebedev V Article Google Scholar Minoux M A Narrow Margin. Skip to content. Home About. Any feasible solution to the dual problem gives a bound on the optimal objective function value in the primal problem. This is how I motivate the dual problem in class, in fact. The formal statement of this is the weak duality theorem. Understanding the dual problem leads to specialized algorithms for some important classes of linear programming problems.
Examples include the transportation simplex method, the Hungarian algorithm for the assignment problem, and the network simplex method. Even column generation relies partly on duality. The dual can be helpful for sensitivity analysis. However, this only changes the objective function or adds a new variable to the dual, respectively, so the original dual optimal solution is still feasible and is usually not far from the new dual optimal solution.
Sometimes finding an initial feasible solution to the dual is much easier than finding one for the primal. For example, if the primal is a minimization problem, the constraints are often of the form , , for. The dual constraints would then likely be of the form , , for. The origin is feasible for the latter problem but not for the former. The dual variables give the shadow prices for the primal constraints.
Suppose you have a profit maximization problem with a resource constraint i. Then the value of the corresponding dual variable in the optimal solution tells you that you get an increase of in the maximum profit for each unit increase in the amount of resource i absent degeneracy and for small increases in resource i. Sometimes the dual is easier to solve. A primal problem with many constraints and few variables can be converted into a dual problem with few constraints and many variables.
Fewer constraints are nice in linear programs because the basis matrix is an matrix, where n is the number of constraints. Thus the fewer the constraints, the smaller the size of the basis matrix, and thus the fewer computations required in each iteration of the simplex method. The dual can be used to detect primal infeasibility. This is a consequence of weak duality: If the dual is a minimization problem whose objective function value can be made as small as possible, and any feasible solution to the dual gives an upper bound on the optimal objective function value in the primal, then the primal problem cannot have any feasible solutions.
Share this: Twitter Facebook.
0コメント