线性规划单纯形法文档

线性规划——单纯形法设计文档——《通用优化模块》编写人：徐天爽编写时间：2010年06月完成2010年06月整理目录第一部分功能概述....................................................................................................1第二部分理论知识....................................................................................................22.1线性规划标准型...........................................................................................22.2单纯形法......................................................................................................42.2.1修正单纯形法....................................................................................42.2.2Bland规则.........................................................................................7第三部分程序主要内容............................................................................................9第四部分程序测试..................................................................................................10备注......................................................................................................................17参考文献......................................................................................................................181第一部分功能概述单纯形法是线性规划算法的一种。由于若线性规划问题有最优解，则一定存在一个基本可行解是最优解，因此单纯形法是通过沿着可行集的边界，从一个顶点转移到改善当前目标函数值的相邻定点，以此来寻找最优解。程序编写了加入Bland规则的修正单纯形法，只需用户给定设计变量个数、约束条件个数、约束条件系数，委托矩阵操作类MatrixOperation进行矩阵运算，即可实现线性规划问题的优化。2第二部分理论知识线性规划问题具备以下性质：定理1若线性规划问题的可行域X非空，则X是一个凸集。定理2线性规划问题的每一个基本可行解x都对应于可行域X的一个顶点。定理3若线性规划问题有最优解，则一定存在一个基本可行解是最优解。定理4若线性规划问题有最优解，则目标函数的最优值一定可以再可行域X的某个顶点上达到。2.1线性规划标准型定义1如果目标函数是设计变量的线性函数，且约束条件也是关于设计变量的线性等式或线性不等式，则相应的数学问题就称为一个线性规划问题。单纯形法计算问题的最优值需要将原问题统一为标准形式。定义线性规划问题的标准形式为：定义2给定线性规划问题的标准型为11min..1,2,,01,2,,njjjnijjijjzcxstaxbimxjn(1)其中01,2,,ibim。即对目标函数一律求最小值；设计变量均非负；约束条件除非负约束条件之外一律为等式约束；约束条件的右端项一律非负。定义3如果约束条件中含有不等式1nijjijaxb且0ib，则可引入一个新的变量ix，称为松弛变量；如果约束条件中含有不等式1nijjijaxb且0ib，则可引入一个新的变量ix，称为剩余变量。3任意线性规划问题，总可以在标准化过程中设法使所得到的标准型线性规划的约束系数矩阵A中存在一个m阶的单位阵，即（1）若线性规划的m个约束条件都是“”的形式，且右端项都为非负，则在标准化时，每个约束条件的左边都加上一个松弛变量，该松弛变量对应的系数列向量是m维的单位向量；（2）若第i个约束条件为“”的形式，且右端项为非负，则再改约束条件左端减去剩余变量化成标准形式后，再加上一个非负的新变量，称为人工变量。显然，人工变量的系数列向量也为m维的单位向量；（3）若第i个约束条件为等式，且右端项为非负，则直接在该等式左端添加人工变量。例：将一线性规划问题的约束条件123123123123..3243235200,0,0stxxxxxxxxxxxx化成标准型。第一个约束条件可化为1233243xxx，即12343243xxxx；第二个约束条件可化为12356235xxxxx；第三个约束条件可化为123720xxxx。此时01,2,,7jxj。显然，向量4A、6A和7A构成了一个3阶的单位阵。为讨论方便，可将标准型线性规划中的变量次序重新调整并编号，使的对应单位阵的编号排在最前或最后（本程序中排在最后）m个变量的位置上，这对计算结果无影响。而在引入人工变量之后，所得到的线性规划的约束条件与原来的约束条件不完全等价，需要对原目标函数进行修正，通常采用两种方法：（1）大M法此方法原理是将目标函数中人工变量前乘以一个足够大的正数M，当人工变量取值大于0时，目标函数就不能实现最优。4例：对于线性规划问题13123123123123min3..3243235200,0,0zxxstxxxxxxxxxxxx，将其化为标准型为12345671234123561237min3000..32432352001,2,,7jzxxxxxMxMxstxxxxxxxxxxxxxxj，其中6x和7x是人工变量，M是一个足够大的正数。接下来可用单纯形法进行优化。（2）两阶段法由于问题的目标函数有两方面作用：其一是使得人工变量都取0值，从而可得问题的一个可行解；其二是在可行域内找到使目标函数达到最小值的最优解。因此这两种作用也可分为两阶段来完成：第一阶段求解一个目标函数中只包含人工变量的线性规划，由此得到问题的一个可行解；第二个阶段以此基本可行解作为初始基本可行解，应用单纯形法继续求解线性规划问题，从而获得最优解。由于大M法需要给定一个足够大的正数M，而在计算机求解时，如何自动给定这个足够大的正数M是需要考虑的。同时，当优化问题系数与这个M值相对比较接近或者远远小于M的时候，将可能导致计算机取值误差。以上两点为大M法的缺点，但是相对两阶段法而言，大M法更容易编程实现，因此本程序采用大M法来处理人工变量。2.2单纯形法2.2.1修正单纯形法标准单纯形法每次迭代不仅需要存储一个mn维的矩阵A，而且A中所有数据都需要计算一遍。当m和n的数值较大时，将会占用较大的内存空间并浪费很多工作量。事实上，A中除了换入列以外的其他列没必要计算。修正单纯形法每次迭代只计算换入列、常数列和检验数行，从而大大减少了5所需的计算机存储量，提高了计算效率。尤其当问题的约束条件数m远远小于设计变量个数n时，这种优势更为明显。修正单纯形法步骤如下：Step1：给定线性规划问题，将其化为标准型；Step2：初始化，确定0B、0N、0Bx、0Nx、0Bc、0Nc；Step3：计算Nσ，进行最优性检验。若满足最优性标准，则将当前最优解x和目标函数最优值z输出，停止迭代。否则进行Step4；Step4：根据检验数向量Nσ，确定第i次迭代的进基变量kx；Step5：根据最小比原则，计算111min0iikijkjBbθBABA，确定第i次迭代的离基变量lx，同时将向量1ikBA中位置为的元素记做主元素（等于离基变量lx在原存储基变量的向量iBx中的位置）；Step6：根据公式111iiiBDB，更新1iB、1iN、1iBx、1iNx、1iBc、1iNc。其中10BE，1211illmMeeeξee（向量ξ是将1ikBA的主元素换成其倒数，其余元素除以负的主元素得到的）；Step7：令1ii，返回Step3。例：用改进单纯形法解如下线性规划问题12312312312123min2..4226250,0,0zxxxstxxxxxxxxxxx(2)将上述问题化为标准型6123456123456123456123456min2000..004220062000501,2,,6jzxxxxxxstxxxxxxxxxxxxxxxxxxxj(3)可知1,2,1,0,0,0Tc，4,6,5Tb。第0次迭代——初始可行基阵0456BAAAE，非基阵0123NAAA，010456,,4,6,5TTxxxBxBb，0123,,0,0,0TTxxxNx，0456,,0,0,0cccBc，0123,,1,2,1cccNc。检验数0001001,2,1NNBσccBN。由于010σ，020σ，则此时并未得出最优解，进入下一次迭代。第1次迭代——由0021,2,3min2jjσσ可知，2x为进基变量（即2k）。而1004,6,5TbBb，100221,2,1TABA，则0001,2,3min03jjjjbθAA。则025xBx为离基变量（即2l）。因此更新为1426BAAA，1153NAAA。根据02A可确定主元素为00222lkaa，则0111,,222Tξ，从而0110210021012D，11100110210021012BDB，111426,,1,3,2TTxxxBxBb。检验数1111112,1,1NNBσccBN。由于110σ，130σ，则此7时并未得出最优解，进入下一次迭代。第2次迭代——由1111,5,3min2jjσσ可知，1x为进基变量（即1k）。而1111,3,2TbBb，11111315,,222TABA，则1114,6min03jjjjbθAA。则114xBx为离基变量（即1l）。因此更新为21