线性规划单纯形法文档

1、线性规划单纯形法设计文档 通用优化模块编写人：徐天爽编写时间：2010年06月完成2010年06月整理目 录第一部分 功能概述1第二部分 理论知识22.1 线性规划标准型22.2单纯形法42.2.1修正单纯形法42.2.2Bland规则7第三部分 程序主要内容9第四部分 程序测试10备 注17参考文献18第一部分 功能概述单纯形法是线性规划算法的一种。由于若线性规划问题有最优解，则一定存在一个基本可行解是最优解，因此单纯形法是通过沿着可行集的边界，从一个顶点转移到改善当前目标函数值的相邻定点，以此来寻找最优解。程序编写了加入Bland规则的修正单纯形法，只需用户给定设计变量个数、约束条件个数、

2、约束条件系数，委托矩阵操作类MatrixOperation进行矩阵运算，即可实现线性规划问题的优化。第二部分 理论知识线性规划问题具备以下性质：定理1 若线性规划问题的可行域非空，则是一个凸集。定理2 线性规划问题的每一个基本可行解都对应于可行域的一个顶点。定理3 若线性规划问题有最优解，则一定存在一个基本可行解是最优解。定理4 若线性规划问题有最优解，则目标函数的最优值一定可以再可行域的某个顶点上达到。2.1 线性规划标准型定义1 如果目标函数是设计变量的线性函数，且约束条件也是关于设计变量的线性等式或线性不等式，则相应的数学问题就称为一个线性规划问题。单纯形法计算问题的最优值需要将原问题统

3、一为标准形式。定义线性规划问题的标准形式为：定义2 给定线性规划问题的标准型为其中。即对目标函数一律求最小值；设计变量均非负；约束条件除非负约束条件之外一律为等式约束；约束条件的右端项一律非负。定义3 如果约束条件中含有不等式且，则可引入一个新的变量，称为松弛变量；如果约束条件中含有不等式且，则可引入一个新的变量，称为剩余变量。任意线性规划问题，总可以在标准化过程中设法使所得到的标准型线性规划的约束系数矩阵中存在一个阶的单位阵，即（1）若线性规划的个约束条件都是“”的形式，且右端项都为非负，则在标准化时，每个约束条件的左边都加上一个松弛变量，该松弛变量对应的系数列向量是维的单位向量；（2）若第

4、个约束条件为“”的形式，且右端项为非负，则再改约束条件左端减去剩余变量化成标准形式后，再加上一个非负的新变量，称为人工变量。显然，人工变量的系数列向量也为维的单位向量；（3）若第个约束条件为等式，且右端项为非负，则直接在该等式左端添加人工变量。例：将一线性规划问题的约束条件化成标准型。第一个约束条件可化为，即；第二个约束条件可化为；第三个约束条件可化为。此时。显然，向量、和构成了一个3阶的单位阵。为讨论方便，可将标准型线性规划中的变量次序重新调整并编号，使的对应单位阵的编号排在最前或最后（本程序中排在最后）个变量的位置上，这对计算结果无影响。而在引入人工变量之后，所得到的线性规划的约束条件与原

5、来的约束条件不完全等价，需要对原目标函数进行修正，通常采用两种方法：（1）大法此方法原理是将目标函数中人工变量前乘以一个足够大的正数，当人工变量取值大于0时，目标函数就不能实现最优。例：对于线性规划问题，将其化为标准型为，其中和是人工变量，是一个足够大的正数。接下来可用单纯形法进行优化。（2）两阶段法由于问题的目标函数有两方面作用：其一是使得人工变量都取0值，从而可得问题的一个可行解；其二是在可行域内找到使目标函数达到最小值的最优解。因此这两种作用也可分为两阶段来完成：第一阶段求解一个目标函数中只包含人工变量的线性规划，由此得到问题的一个可行解；第二个阶段以此基本可行解作为初始基本可行解，应用

6、单纯形法继续求解线性规划问题，从而获得最优解。由于大法需要给定一个足够大的正数，而在计算机求解时，如何自动给定这个足够大的正数是需要考虑的。同时，当优化问题系数与这个值相对比较接近或者远远小于的时候，将可能导致计算机取值误差。以上两点为大法的缺点，但是相对两阶段法而言，大法更容易编程实现，因此本程序采用大法来处理人工变量。2.2 单纯形法2.2.1 修正单纯形法标准单纯形法每次迭代不仅需要存储一个维的矩阵，而且中所有数据都需要计算一遍。当和的数值较大时，将会占用较大的内存空间并浪费很多工作量。事实上，中除了换入列以外的其他列没必要计算。修正单纯形法每次迭代只计算换入列、常数列和检验数行，从而大

7、大减少了所需的计算机存储量，提高了计算效率。尤其当问题的约束条件数远远小于设计变量个数时，这种优势更为明显。修正单纯形法步骤如下：Step1：给定线性规划问题，将其化为标准型；Step2：初始化，确定、；Step3：计算，进行最优性检验。若满足最优性标准，则将当前最优解和目标函数最优值输出，停止迭代。否则进行Step4；Step4：根据检验数向量，确定第次迭代的进基变量；Step5：根据最小比原则，计算，确定第次迭代的离基变量，同时将向量中位置为的元素记做主元素（等于离基变量在原存储基变量的向量中的位置）；Step6：根据公式，更新、。其中，（向量是将的主元素换成其倒数，其余元素除以负的主元素

8、得到的）；Step7：令，返回Step3。例：用改进单纯形法解如下线性规划问题将上述问题化为标准型可知，。第0次迭代初始可行基阵，非基阵，。检验数。由于，则此时并未得出最优解，进入下一次迭代。第1次迭代由可知，为进基变量（即）。而，则。则为离基变量（即）。因此更新为，。根据可确定主元素为，则，从而，。检验数。由于，则此时并未得出最优解，进入下一次迭代。第2次迭代由可知，为进基变量（即）。而，则。则为离基变量（即）。因此更新为，。根据可确定主元素为，则，从而，。检验数向量。则此时最优解为，目标函数最优值为。2.2.2 Bland规则当线性规划问题存在最优解，在非退化的情况下，单纯形法的每次迭代都

9、使目标函数值严格下降。这样，经过有限次迭代必达到最优解。但是对于退化情形，即使存在最优解，也可能出现循环现象，即迭代过程总是重复解得某一部分序列，目标函数值总是不变，因而永远达不到最优解。例如E.Beale给出的例子：可以看出，由于6次迭代得到的基本可行解都对应着同一个顶点，所以继续迭代也将重复此死循环，永远不能终止。这是由于标准单纯形法的最小比原则导致的。因此，给定Bland规则为定理5 按照如下规则来确定进基变量指标和离基变量指标，则在迭代过程中就不会出现死循环：（1）；（2），其中表示基变量所对应的系数向量在中排在第个向量位置上。也就是说，根据Bland规则，在迭代过程中如果有多个检验数

10、都是负的，则选取其中小标最小的检验数的相应下标作为进基变量指标；如果有几个同时达到，则选取其中下标最小的基变量作为离基变量。由于线性规划问题的基只有有限个，而采用Bland规则的单纯形法又保证不会出现死循环，因而从理论上保证了单纯形法经过有限次迭代后必终止。但是迭代次数会增加。第三部分 程序主要内容单纯形法类名称：SimpleMethod路径： SimpleMethod.vb功能：实现线性规划问题的修正单纯形法优化（加入Bland准则，避免无限死循环）编写人：徐天爽编写时间：2010年6月完成，2010年6月30日整理l 方法实现修正单纯形法优化，参数DVNumber是设计变量个数，CNumb

11、er是约束条件个数，A是约束等式左端的系数矩阵（包含CNumber行、CNumber+DVNumber列），B是约束等式右端值组成的向量（包含CNumber个元素），C是目标函数系数向量（包含DVNumber个元素）。Public Function AdjustSimpleMethod(ByVal DVNumber As Integer, ByVal CNumber As Integer, ByVal A(,) As Double, ByVal B() As Double, ByVal C() As Double)l 调用其他类调用矩阵操作类MatrixOperation。Dim aa As

12、New MatrixOperation第四部分 程序测试案例1：对设计变量数和约束条件个数均为3的线性规划问题进行修正单纯形法优化（见文献1中37页例2-6）。图1 修正单纯形法的测试窗口Step1：在窗口Form1中新建一按钮控件并命名为“测试函数1”，如Error! Reference source not found.所示；Step2：在“测试函数1”按钮中添加如下代码Public Class Form1 测试函数1 Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

13、Handles Button1.Click Dim A(2, 5) As Double A(0, 0) = 1 : A(0, 1) = 1 : A(0, 2) = 1 : A(0, 3) = 1 : A(0, 4) = 0 : A(0, 5) = 0 A(1, 0) = -1 : A(1, 1) = 2 : A(1, 2) = -2 : A(1, 3) = 0 : A(1, 4) = 1 : A(1, 5) = 0 A(2, 0) = 2 : A(2, 1) = 1 : A(2, 2) = 0 : A(2, 3) = 0 : A(2, 4) = 0 : A(2, 5) = 1 Dim b(2)

14、 As Double b(0) = 4 : b(1) = 6 : b(2) = 5 Dim c(2) As Double c(0) = -1 : c(1) = -2 : c(2) = 1 Dim aa As New SimpleMethod Dim result As Double result = aa.AdjustSimpleMethod(3, 3, A, b, c) MsgBox(result) End SubEnd ClassStep3：运行程序，点击Form1窗口下的“测试函数1”按钮，如Error! Reference source not found.所示，弹出计算结果的对话框，

15、可见最优解约为（精确解为）。图2 案例1的优化结果案例2：对设计变量数为4，约束条件个数为3的线性规划问题进行修正单纯形法优化，此问题如不采用Bland规则，则会陷入死循环（见文献1中30页例2-4）。Step1：在窗口Form1中新建一按钮控件并命名为“测试函数3”，如Error! Reference source not found.所示；Step2：在“测试函数3”按钮中添加如下代码Public Class Form1 测试函数3Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.Event

16、Args) Handles Button3.Click Dim A(2, 6) As Double A(0, 0) = 1 / 4 : A(0, 1) = -8 : A(0, 2) = -1 : A(0, 3) = 9 : A(0, 4) = 1 : A(0, 5) = 0 : A(0, 6) = 0 A(1, 0) = 1 / 2 : A(1, 1) = -12 : A(1, 2) = -1 / 2 : A(1, 3) = 3 : A(1, 4) = 0 : A(1, 5) = 1 : A(1, 6) = 0 A(2, 0) = 0 : A(2, 1) = 0 : A(2, 2) = 1 :

17、 A(2, 3) = 0 : A(2, 4) = 0 : A(2, 5) = 0 : A(2, 6) = 1 Dim b(2) As Double b(0) = 0 : b(1) = 0 : b(2) = 1 Dim c(3) As Double c(0) = -3 / 4 : c(1) = 20 : c(2) = -1 / 2 : c(3) = 6 Dim aa As New SimpleMethod Dim result As Double result = aa.AdjustSimpleMethod(4, 3, A, b, c) MsgBox(result) End SubEnd Cla

18、ssStep3：运行程序，点击Form1窗口下的“测试函数3”按钮，如Error! Reference source not found.Error! Reference source not found.所示，弹出计算结果的对话框，可见最优解为（精确解为）。图3 案例2的优化结果案例3：对设计变量数为2，约束条件个数为2的线性规划问题进行修正单纯形法优化，此问题化成标准型后包含人工变量，则根据大法来处理人工变量，令。同时，此问题没有给定设计变量非负这一条件，因此需要令，将和做为设计变量来优化（见文献2中103页例4-5），即约束条件个数为2，设计变量个数为4。此时将原问题化为重新对设计变量进

19、行编号，有然后，需要将目标函数中的人工变量前的系数化为0。根据约束条件，令，代入到目标函数中消去前的系数，有Step1：在窗口Form1中新建一按钮控件并命名为“江爱川103页”，如Error! Reference source not found.所示；Step2：在“江爱川103页”按钮中添加如下代码Public Class Form1 江爱川 P103例4-5Private Sub Button9_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button9.Click Dim A(1,

20、 6) As Double A(0, 0) = 1 : A(0, 1) = -1 : A(0, 2) = 1 : A(0, 3) = -1 : A(0, 4) = -1 : A(0, 5) = 1 : A(0, 6) = 0 A(1, 0) = 4 : A(1, 1) = -4 : A(1, 2) = -1 : A(1, 3) = 1 : A(1, 4) = 0 : A(1, 5) = 0 : A(1, 6) = 1 Dim b(1) As Double b(0) = 3 : b(1) = 22 Dim c(4) As Double c(0) = -102 : c(1) = 102 : c(2

21、) = -90 : c(3) = 90 : c(4) = 100 Dim aa As New SimpleMethod Dim result As Double result = aa.AdjustSimpleMethod(5, 2, A, b, c) MsgBox(result) End SubEnd ClassStep3：运行程序，点击Form1窗口下的“江爱川103页”按钮，如Error! Reference source not found.所示，弹出计算结果的对话框，结果为-330。此时根据公式中的目标函数可知，程序计算结果应加上300才与原问题等价，可见最优解为（精确解为）。图4

22、案例3的优化结果案例4：对设计变量数为2，约束条件个数为3的线性规划问题进行修正单纯形法优化，此问题化成标准型后包含人工变量，则根据大法来处理人工变量，令，按照案例3中的方法处理目标函数中的人工变量系数。同时通过计算可知此问题无解（见文献2中97页例4-3）。Step1：在窗口Form1中新建一按钮控件并命名为“江爱川97页”，如Error! Reference source not found.所示；Step2：在“江爱川97页”按钮中添加如下代码Public Class Form1江爱川 P97例4-3，无解 Private Sub Button7_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button7.Click Dim A(2, 2) As Double A