Alternative optimal solutions in linear programming

What is Alternate Optimal Solution?

An alternate optimal solution is also called as an alternate optima, which is when a linear / integer programming problem has more than one optimal solution. Typically, an optimal solution is a solution to a problem which satisfies the set of constraints of the problem and the objective function which is to maximize or minimize.

Example:

Here, the graphical analysis of a problem is given with set of (< =) constraints and a maximizing objective function. The optimal solution set is a smaller set within the feasible region. Here, the objective function is parallel to cd line segment. Hence, all points (x1, x2) on cd give maximum yield. In such case, there is alternate optimal solution.

This article has been researched & authored by the Business Concepts Team. It has been reviewed & published by the MBA Skool Team. The content on MBA Skool has been created for educational & academic purpose only.

Browse the definition and meaning of more similar terms. The Management Dictionary covers over 2000 business concepts from 5 categories.

Continue Reading:

Research output: Contribution to journal › Article › peer-review

Abstract

In the presence of degeneracy, the meaning of alternative optimal solutions may not necessarily imply the existence of alternative solution points. This note is intended to highlight the possibly ambiguous meaning of alternative optimal solutions to L. P. problems in the presence of degeneracy- a point which is glossed over by most O. R. texts.

Fingerprint

Dive into the research topics of 'Alternative optimal solutions to linear programming problems in the presence of degeneracy'. Together they form a unique fingerprint.

Abstract

In this paper, the nonlinear programming problem with quasimonotonic (both quasiconvex and quasiconcave) objective function and linear constraints is considered. With the decomposition theorem of polyhedral sets, the structure of optimal solution set for the programming problem is depicted. Based on a simplified version of the convex simplex method, the uniqueness condition of optimal solution and the computational procedures to determine all optimal solutions are given, if the uniqueness condition is not satisfied. An illustrative example is also presented.

Access options

References

1. Zheng Y J. Structure of the optimal solution set and sufficient condition for the unique optimal solution in linear programming problems, Communication on Applied Mathematics and Computation, 1992, 6(1): 42–46.

   Google Scholar 

2. Li J. Discussions on alternative optimal solutions of linear programming, Operations Research and Management, 1999, 8(1): 87–92.

   Google Scholar 

3. Xu Z K. Introduction to Mathematical Programming, Beijing: Science Publishing Press, 2000.

   Google Scholar 

4. Zuo X D, Xue S J, Liang Y, et al. A way to find all optimal solutions in linear programming, Journal of Systems Science and Systems Engineering, 2000, 9(4): 482–487.

   Google Scholar 

5. Mangasarian, O L. A simple characterization of solution sets of convex programs, Operations Research Letters, 1988, 7(1): 21–26.

   Article  MATH  MathSciNet  Google Scholar 

6. Burke J V, Ferris M C. Characterization of solution sets of convex programs, Operational Research Letters, 1991, 10(1): 57–60.

   Article  MATH  MathSciNet  Google Scholar 

7. Jeyakumar V, Yang X Q. On characterizing the solution sets of pseudolinear programs, Journal of Optimization Theory and Applications, 1995, 87: 747–755.

   Article  MATH  MathSciNet  Google Scholar 

8. Lu Q H, Zeng L F. Characterizations of solution sets of pseudolinear programs, Journal of Fudan University, 2004, 43(1): 130–134.

   MATH  MathSciNet  Google Scholar 

9. Avriel M. Nonlinear Programming: Analysis and Methods, New Jersey: Prentice Hall, Inc, 1976.

   MATH  Google Scholar 

10. Bazaraa M S, Shetty C M. Nonlinear Programming: Theory and Algorithms, New York: John Wiley & Sons, Inc, 1979.

    MATH  Google Scholar 

11. Xue S J, Shen S Y. Eleven kinds of convexity, Chinese Journal of Operations Research, 1989, 8(1): 72–75.

    MathSciNet  Google Scholar 

12. Xue S J. Determining the optimal solution set for linear fractional programming, Journal of Systems Engineering and Electronics, 2002,13(3): 40–45.

    Google Scholar 

13. Wei Q L, Yan H. Generalized Optimization Theory and Methods, Beijing: Science Press, 2003.

    Google Scholar 

14. Horst R, Pardalos P M, Thaoi N V. Introduction to Global Optimization, 2nd ed, Dordrecht: Kluwer Academic Publishers, 2000.

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

1. School of Management, Jinan University, Guangzhou, 510632, China

   Xue Shengjia

Authors

1. Xue Shengjia

   You can also search for this author in PubMed Google Scholar

Additional information

Supported by the Research Foundation of Jinan University (04SKZD01).

Rights and permissions

About this article

Cite this article

Xue, S. On alternative optimal solutions to quasimonotonic programming with linear constraints. Appl. Math. Chin. Univ. 22, 119–125 (2007). https://doi.org/10.1007/s11766-007-0015-x

Download citation

• Received: 30 April 2006

• Issue Date: March 2007

• DOI: https://doi.org/10.1007/s11766-007-0015-x

MR Subject Classification

• 90C30

Keywords

• quasimonotonic programming problem
• polyhedral set
• decomposition theorem
• alternative optimal solution
• convex simplex method

What is alternative optimal solution in simplex method?

How many optimal solutions are there in linear programming?

Can there be more than one optimal solution in linear programming?

How can you tell for sure that a problem has alternate optimal solutions?