LP模型标准化教辅软件设计与实现

摘要：在线性规划（LP）求解过程中，模型的标准化是个非常重要的知识点，因为会涉及LP模型的各个部分，且相互牵扯，故实际操作时出错率很高。为提高教学效果，笔者开发了《军事运筹原理仿真模拟系统》，其中涉及LP模型的标准化自动处理问题，实践证明，教学效果良好。

关键词：线性规划；标准化；模型；仿真

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）17-0087-02

Abstract： In the process of solving linear programming（LP），Standardization of models is a very important knowledge point， Because it involves all the parts of the LP model， And involved each other， Therefore ， the error rate in actual operation is high. In order to improve the teaching effect， The author has developed the Simulation and Simulation system of military operational Research principle， Which involves the standardization of LP model automatic processing problem， Practice has proved that the teaching effect is good.

Key words： linear programming； standardizing； model； simulation

现实活动中的许多问题，若可用一组决策变量x1，x2，…，xn来描述其实施方案，且还存在着可用一组线性等式（或不等式）来表示的限制条件，而且，还有一个要达到的目标，该目标可用决策变量的线性函数来表示，或追求最大化，抑或是最小化。求解此类问题的理论即线性规划。

1 LP标准型

线性规划问题的求解算法较多，但规定一个标准形式总是必需的。为研究问题方便，规定线性规划问题数学模型的标准形式如下面图1所示。

2 LP模型标准化

一般情况下，基于现实问题抽象出来的线性规划模型或多或少总会与标准化形式有一定距离，为求解方便，总是将抽象出来的非标准化模型转化为标准形式，然后再使用诸如单纯形法等方法求解之，所以，标准化过程便成了求解线性规划问题的必经之路，也是教学过程中必须多加练习的一个知识点。任意形式的线性规划模型均可通过适当处理将其转化为标准型，且表现在不同位置上与标准型之间的差异需要不同的处理方法和数学技巧，下面将分情况讨论LP模型的标准化处理过程。

2.1 非等式的约束方程

当约束条件中包含的约束关系符不是‘=，而是‘≥或‘≤时，为了平衡该约束条件两端的值，常采用‘减去或‘加上一个非负的新变量之方式，把原来的‘≥或‘≤转化为‘=。该新引进的非负变量被称之为‘松弛变量，为使松弛变量不影响目标函数，可将其在目标函数系数恒设为0。

2.2 含自由变量

未在线性规划模型之非负条件中加以限制的未知变量称为自由变量。此时，可设在模型中存在自由變量xk，则可令： xk = xk′- xk″；其中，xk′，xk″≥ 0。不难理解，不论xk取值如何，通过两个非负的数值（即xk′，xk″）之差，总能表示xk。

另外，因为线性规划的标准形式中规定，所有的未知变量均必须是非负的，所以，如果抽象出来的线性规划模型中某个未知变量虽做了限制性说明，但却并不是非负的，则同样要做处理，方法基本类似，这里不再赘述。

2.3 目标函数求最小值

当线性规划模型中的目标函数是求最小值时，只需将目标函数Z的值取反并求其最大值即可。即，Min（Z） = - Max（- Z）。当然，此刻需将目标函数中的所有项目均改变符号，待- Z的最大值求得后，再取反变号即原线性规划问题要求解的最小值。

线性规划模型的标准化过程是正确求解线性规划问题的基础，因标准化过程中需牵扯到模型的各个部分，故标准化处理时须格外谨慎，认真对待。通过一定的练习，熟练掌握标准化的处理技巧和原则，为后续求解算法打下基础。但在教学测试时，标准化问题的得分率并不太高，学生们出现这样那样的问题总是不可避免的。为提高教学效果，笔者基于VB6.0开发出了LP求解原理仿真模拟CAI，下面即该CAI中关于标准化处理部分的分析、设计和运行效果，希望能对相关读者有所帮助。

3 基于CAI的LP模型标准化流程分析

虽然LP模型组成只有三部分，标准化也是针对这三部分展开讨论的，但标准化过程中它们会相互牵扯，故极易出错，因此在设计CAI时必须就标准化动作做适当分解，我们将其拆分成下面7步。

1）确定标准化之后的变量总数

涉及变量名称（Xi'或Xi''）的确定，及其在目标函数、约束条件和非负条件中的显示位置和显示处理等。当然，也包括各变量的系数（不是最后的准确数值，仅仅是将其原始数据传过来而已）。处理思路相对简单，按原未知变量顺序，依次处理原模型中的每个未知变量（非松弛变量）即可。

2）加入松驰变量

确定其系数、变量名称等，最后显示其对应的文本控件等即可。

3）确定资源列向量信息

计算资源列向量的显示位置、约束条件关系运算符的显示位置，并传过其对应的原始数值。如果最后的结果模型中总的变量数不足18个（CAI模拟规模限制），需前移以确定其新位置；否则（够18个变量），使用原始设计的老位置显示。

4）资源列向量为负

约束条件两边均乘“-1”，所有系数变号，关系运算变方向，同时需考虑松驰变量的符号问题。针对非负限制条件的不同限制类型（如：Xi≥p、Xi≤p及自由变量等），须做不同的处理动作。

5）标准化非负条件中各变量

若Xi≥p，有Xi-p≥0，设Xi'=Xi-p，得Xi'≥0，且Xi=Xi'+p，代之入约束条件可知，对应的变量系数并不变化，只不过需在约束条件右边减去aki*p而已； 若Xi≤p，有Xi-p≤0，设Xi'=p-Xi，得Xi'≥0，同理，只需在约束条件右边减去aki*p而已的同时，再将对应的变量系数取反； 若Xi后面为空，表示其为自由变量，只需处理成对应的Xi'-Xi''，Xi''的对应系数取反，其他部位不变。同时，需考虑目标函数中对应变量的代入问题。

6）显示标准的非负条件限制

将新模型中所有变量的非负条件限制（“Xi≥0”中的“≥0”部分）显示出来；

7）优化目标函数

如果原模型求“min”，则可将其后面的每一项取反即可。当然，对应的Z，应是Z‘，最后求解结果后，将其符号取反即可。

4 标准化CAI仿真实现

标准化处理是笔者设计开发之《军事运筹学原理仿真模拟系统》中的一个子模块，其主界面如图2。

通过界面上的‘设置命令按钮可以灵活调整LP模型规模，诸如未知变量个数（在图2示例中为4）、约束方程个数（在图2示例中为5）、各参数的取值范围等。通过界面上的‘系数命令按钮可以随机生成模型的所有参数，进而利用系数调节滚动条，还可灵活修改任意一个参数。‘保存命令按钮可将设置好的LP模型存储起来以备它用，而‘导入命令按钮则可将已存好的LP模型读入该模块，进而实施标准化处理。当单击‘标准化命令按钮时，可打开‘标准化结果处理窗口。该窗口刚打开时处于空白状态，单击‘第1步命令按钮即可完成第4节中的‘确定标准化之后的变量总数计算等功能，同时将初始模型显示在该窗口中，进而可开始实施‘第2步处理，如图3所示。

紧跟着，可依次展开后续各步的标准化处理动作，图3即完成第6步处理时的状态。不难看出，此刻LP模型的标准化动作即将完成，可以转入后续的基本可行解求解处理，或是单纯法求解等仿真模拟过程。鉴于该文所关注的重点所限，后续内容将不再赘述。

鉴于水平所限制，不妥和错误之处，敬请批评指正！

参考文献：

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

[2] 曹迎槐. 軍事运筹学[M]. 北京： 国防工业出版社， 2013.