Duality in linear programming: From trichotomy to quadrichotomy

Yanqun Liu

doi:10.3934/jimo.2011.7.1003

Article Contents

2011, Volume 7, Issue 4: 1003-1011. Doi: 10.3934/jimo.2011.7.1003

This issue Previous Article Multiple solutions for a class of semilinear elliptic variational inclusion problems Next Article Global convergence of an inexact operator splitting method for monotone variational inequalities

Duality in linear programming: From trichotomy to quadrichotomy

Yanqun Liu^1,

1.
School of Mathematical & Geospatial Sciences, RMIT University, Melbourne

Received: August 31, 2010

Revised: June 30, 2011

Published: September 2011

Abstract Related Papers Cited by

Abstract

In this paper, we present a new approach to the duality of linear programming. We extend the boundedness to the so called inclusiveness, and show that inclusiveness and feasibility are a pair of coexisting and mutually dual properties in linear programming: one of them is possessed by a primal problem if and only if the other is possessed by the dual problem. This duality relation is consistent with the symmetry between the primal and dual problems and leads to a duality result that is considered a completion of the classical strong duality theorem. From this result, complete solvability information of the primal (or dual) problem can be derived solely from dual (or primal) information. This is demonstrated by applying the new duality results to a recent linear programming method.

Keywords:

Mathematics Subject Classification: Primary: 90C05; Secondary: 49M29.

Citation:

Related Papers

Cited by

References

[1]	M. C. Ferris, O. L. Mangasarian and S. J. Wright, "Linear Programming with MATLAB," MPS-SIAM Series on Optimization, 7, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, Mathemathical Programming, Society (MPS), Philadelphia, PA, 2007.doi: 10.1137/1.9780898718775.
[2]	H. J. Greenberg, How to analyze the results of linear programs--part 3: Infeasibility diagnosis, Interface, 23 (1993), 120-139.doi: 10.1287/inte.23.6.120.
[3]	C. Li, X. He, B. Chen, Z. Gong, B. Chen and Q. Zhang, Infeasibility diagnosis on the linear programming model of production planning in refinery, Chinese J. Chem. Eng., 14 (2006), 569-573.doi: 10.1016/S1004-9541(06)60117-1.
[4]	Y. Liu, An exterior point linear programming method based on inclusive normal cones, Journal of Industrial and Management Optimization, 6 (2010), 825-846.doi: 10.3934/jimo.2010.6.825.
[5]	D. G. Luenburg and Y. Ye, "Linear and Nonlinear Programming," 3rd edition, International Series in Operations Research & Management Science, 116, Springer, New York, 2008.
[6]	G. Roodman, Post-infeasibility analysis in linear programming, Management Science, 25 (1979), 916-922.doi: 10.1287/mnsc.25.9.916.