Article Contents
Article Contents

# Duality in linear programming: From trichotomy to quadrichotomy

• 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.
Mathematics Subject Classification: Primary: 90C05; Secondary: 49M29.

 Citation:

•  [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.