LP之单纯形法教辅软件设计与实现

曹迎槐　张静　赵强

摘要：在线性规划理论中，单纯形法是非常经典的求解算法，但它计算复杂，涉及数据较多，掌握相对困难，为提高教学效果，笔者开发了《军事运筹原理仿真模拟系统》，其中涉及了线性规划模型的单纯形求解算法仿真问题，经教学实用，效果良好。

关键词：LP;模型;单纯形法;仿真

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2020）20-0070-02

Design and Implementation of LP Simplex Method Teaching Auxiliary Software

CAO Ying-huai. ZHANG Jing， ZHAO Qiang

（China Coast Cuard Academy， Ningb0 315801. China）

Abstract： In the theory of' linear programming， Simplex method is a very c：lassical solution algorithm， But it's complicated， More da-to involved， lt's relatively difficult to master. In order to improve the teaching effect， 'rhe author develc}ped the simulation system ofmilitary operation principle， It involves the simulation of' simplex algorithm of' linear programming model， After teaching practical，the effect is good.

Key words： linear programming; simplex method; foundation： simulation

目前，在运筹学之线性规划（linear programming，简称LP）分支中，最经典的求解算法就是单纯形法，它既是运筹学教材之重点，也是教学之难点所在。但该算法相对复杂，计算过程烦琐，学生掌握相对困难，为此，笔者开发了该算法的求解仿真软件，教学效果良好。

1单纯形法的求解步骤

单纯形法和基于穷举思想的基可行解法不同，它不需要求出所有的基可行解，而是以LP模型之标准形式为出发点先求出一个基可行解，并检验其是否为最优解。如果它已最优，则求解结束，算法终止;如果它不是最优解，就按照算法给定的方法求出另一个基可行解，该算法可以保证新求出的基可行解肯定要优于上一个基可行解。只要LP问题存在最优解，就一定可通过有限次的运算求出最优解。如果，所求的问题不存在有限的最优解（即无解），则该算法也有相应法则判断之。

其具体的求解算法可归纳为五步。

1.1确定初始基可行解

確定出初始（即第一个）可行基时，因标准化处理中多加入松弛变量，所以，初始基可行解的确定往往并不困难，一般直接选取各松弛变量即可。当然，若个别约束方程未添加松弛变量，亦可借助线性代数知识，通过行或列的交换等操作来得到。

1.2最优解检验

检验初始基可行解是否最优。若是最优解，则停止运算;若不是最优解，就转下一步。

1.3无解检验

当检验初始基可行解不是最优解时，继续检验该规划问题是否无解（即无有限的最优解）。若无解则停止运算，若依然无法判定是否无解则转下一步。

1.4基变换

当经过上面的两种检验发现，该基可行解既不最优，也不能判定其无解，则需要寻找另一个基可行解。即在该可行基之基础上，先从原非基变量中选一个变量，称换人变量;再于原基变量中选择一个变量使其成为非基变量，称之为换出变量。于是，新的基变量对应的系数列向量，同原来保持不变的基变量对应的系数列向量（m-1）个，就组成一个新的可行基，此即基变换。

1.5旋转运算

基变换完成后，需进一步求出其相应的新基可行解，该过程即旋转运算。然后，转步骤12。

单纯行法的求解算法亦可用传统流程图来描述，在仿真实现中如图1所示。

2单纯形表

利用单纯形法求解LP问题，涉及大量的数值计算，且各数值之间关系复杂，种类繁多，为简明其见，通常是列表（称为单纯形表，见图2）进行。一般地，单纯形表中应考虑以下数据：

1）基变量：这里用xBi，表示，有xBi=xi（i=l，2，…，m），如图2上部左侧第1列;

2）基变量的价值系数：用cBi表示，有cBi=ci（i=1，2，…，m），如图2上部左侧第2列;

3）约束方程右端的常数bi（i=l，2，…，m），如图2上部有侧第2列;

4）目标函数中各变量的价值系数cj（j=1，2，…，n），填入Cj列，如图2上部第1行;

5）规划模型之各基向量，Pj（j=1，2，…，n），填人xj行下面的对应区域，如图2上部中间区域;

6）检验数σj（j=1，2，…，n）填在单纯形表的最下面一行，如图2中部σj所示。公式为：

7）确定换人变量时，利用“θ最小比法则”计算出来的θi（i-1，2，…，m），填入单纯形表最右侧一列。当然，换入变量确定之后，计算θi=bi/aik时，当aik>0时才须计算之，当aik≤0时不用计算。所以，运算过程中，θi一列并非总要填满，要视情况而定。

3单纯形法求解仿真

单纯形法仿真求解是笔者设计开发之《军事运筹学原理仿真模拟系统》中的一个子模块，假设给定的LP问题之标准型如图2下半部区域所示。其中涉及目标函数系数、约束方程系数矩阵、资源列向量、未知变量个数、约束方程个数等。

界面最底部的文字用来描述仿真求解过程中相关操作信息。而“导入”按钮则可将已标准化的LP模型纳入单纯形法求解仿真模块，导人操作刚完成时，并没有图2界面中上半部分单纯形表中的相关数据，这些数据是在求解过程中随着各步操作的进行而出现并动态变化的。“清除”按钮则可将该仿真模块中的LP数据清空，届时整个仿真界面呈现空白状态。

本仿真模块的求解分两种模式，一是“分步求解”，一是“连续求解”。当LP模型数据导入完成后，即可通过单击“分步求解”按钮，启动单纯形求解之第一步“确定初始可行基”，该步完成则同时填充该界面上半部分的“单纯形表”之相关区域，并将“分步求解按钮上的文字变为“下一步”，如图2所示。此后，可依次单击“下一步”按钮，则求解过程中各相关数据的变化即体现在该界面上半部分的单纯形表相关区域中。

持续单击“下一步”按钮，如果该LP模型存在最优解，则求解完成时，最优解出现在相应位置，同时“下一步”命令按鈕变为“分步求解”，如图3所示。

任何时候，均可通过“打印”按钮将当前界面的状态打印出来，不过，在一般教学实施过程中，该功能使用并不多。通过“设置”按钮可改变未知变量的个数和约束方程的个数等LP规模数据，当LP规模较高时，可协同“高维模型”按钮共同使用，但此刻仿真模块已基本失去教学辅助之意义，逐渐靠向求解工具的范畴，因此，课堂上不常使用。

“连续求解”按钮可从导入标准化模型开始，直达最后得到求解结果，中间的各步信息也不再显示在界面的底部，界面上半部直接显示最优解，这里不再赘述。

“基解列表”按钮可显示该LP模型在本模块之仿真求解过程中得到的所有可行基，如图4所示。但一般肯定不是该LP模型的所有可能的基（含不可行的），这一点必须清楚。

当然，在该仿真模块中，标准化之后LP模型未必能直接得出初始可行基，此时可借助大M法或两阶段法求解之。另外，如果LP模型无解，仿真模块同样会给出相关反馈信息。鉴于篇幅这里不再详述。因水平所限，不妥和错误之处，敬请大家批评指正！

参考文献：

[1]钱颂迪.运筹学[M].北京：清华大学出版，1993.

[2]曹迎槐，尹健，梁春美.军事运筹学[M].北京：国防工业出版社.2013.

[3]曹迎槐.LP模型标准化教辅软件设计与实现[J].电脑知识与技术，2018（7）：87-88.

[4]曹迎槐.LP之单纯形法教辅软件设计与实现[J].电脑知识与技术，2020（17）：63-64.

【通联编辑：谢媛媛】

收稿日期：2020-05-08

作者简介：曹迎槐（1966-），男，河北蔚县人，教授，技术5级，硕士，长期从事计算机技术、运筹建模、海警信息与情报等领域的教学与科研工作;张静（1980-），女，辽宁大连人，副教授，硕士，从事信息安全专业教学工作;赵强（1976-），男，青海西宁人，讲师，硕士，从事多媒体和信息技术专业教学和科研工作。