#### 期刊菜单

On the Teaching of Degenerate Solutions to Linear Programming Problems
DOI: 10.12677/ORF.2022.122043, PDF, HTML, XML, 下载: 79  浏览: 110  科研立项经费支持

Abstract: This paper illustrates how to solve degenerate solutions to linear programming problems using the simplex method with three examples. Degeneracy might have the simplex method become not very efficient. In the circumstance of highly degeneracy, wrong selection of entering basic variables or leaving basic variables could have the iterations go round in a perpetual loop. Degeneracy could cause misjudgment or omission of optimal solutions. When a linear programming problem has a degenerate optimal solution, the multiple optimality test rule becomes ineffective, there is exactly one optimal solution with multiple optimal bases.

1. 引言

2. 求解线性规划问题退化解的理论基础

$\left\{\begin{array}{l}{x}_{1}+{x}_{2}+{x}_{3}=4\\ {x}_{1}+{x}_{4}=4\\ {x}_{j}\ge 0,j=1,2,3,4\end{array}$,

3. 求解线性规划问题退化解的常见题型分析

$\begin{array}{l}\mathrm{max}z=10{x}_{1}-57{x}_{2}-9{x}_{3}-24{x}_{4}\\ \text{s}\text{.t}.\text{\hspace{0.17em}}\left\{\begin{array}{l}0.5{x}_{1}-5.5{x}_{2}-2.5{x}_{3}+9{x}_{4}\le 0\\ 0.5{x}_{1}-1.5{x}_{2}-0.5{x}_{3}+{x}_{4}\le 0\\ {x}_{1}\le 1\\ {x}_{j}\ge 0,j=1,2,3,4\end{array}\end{array}$

Table 1. Starting simplex tableau of Example 1

Table 2. Simplex tableaus of Example 1

$\begin{array}{l}\mathrm{max}z={x}_{1}+{x}_{2}+4{x}_{3}\\ \text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left\{\begin{array}{l}{x}_{1}+4{x}_{3}\le 4\\ {x}_{2}+4{x}_{3}\le 4\\ {x}_{j}\ge 0,j=1,2,3\end{array}\end{array}$

Table 3. Complete simplex tableaus of Example 2

《管理数学(下)：运筹学》教材对问题2的求解过程是，在初始表确定 ${x}_{3}$ 为进基变量，因为其检验数是4，在正检验数中最大，确定离基变量时进行最小θ比值检验，有两个相同的θ比值1，在后续的两步换基迭代中依次出现了两个退化基可行解 [6]。本文选择检验数大于0的下标小的变量 ${x}_{1}$ 为进基变量，在后续换基迭代过程中没有出现退化基可行解，见表3。因此，在用单纯形法求解极大化线性规划问题时，尽量避免选择可能出现多个相同θ比值的变量为进基变量，只要检验数大于0的变量都可以作为进基变量，优先考虑下标小的变量作为进基变量。

$\begin{array}{l}\mathrm{max}z=-2{x}_{1}-{x}_{2}-{x}_{3}+1.5{x}_{4}+{x}_{5}\\ \text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left\{\begin{array}{l}{x}_{1}+2{x}_{3}-{x}_{4}+{x}_{5}=2\\ 2{x}_{1}+2{x}_{2}-2{x}_{3}+2{x}_{4}=2\\ -3{x}_{1}-{x}_{2}-{x}_{3}+{x}_{4}=1\\ {x}_{j}\ge 0,j=1,2,3,4,5\end{array}\end{array}$

Table 4. Complete simplex tableaus of Example 3

 [1] 胡运权. 运筹学教程[M]. 第5版. 北京: 清华大学出版社, 2018: 23-34. [2] 张汉斌. 线性规划退化解的进一步讨论[J]. 邢台职业技术学院学报, 2006, 23(3): 54-56. [3] 刘舒燕. 关于线性规划解的退化问题的讨论[J]. 武汉交通科技大学学报, 2000, 24(4): 402-405. [4] 李钦. 运筹学教学中对影子价格和对偶问题最优解关系的讨论[J]. 高师理科学刊, 2020, 40(10): 57-63. [5] 《运筹学》教材编写组. 运筹学[M]. 第4版. 北京: 清华大学出版社, 2012: 23-45. [6] 蓝伯雄, 等. 管理数学(下): 运筹学[M]. 北京: 清华大学出版社, 1997: 40-45. [7] 潘平奇. 线性规划计算(上) [M]. 北京: 科学出版社, 2012: 65.