运筹学毕业论文-单纯形法.doc

目 录1 算法分析1.1单纯形算法（1）2 单纯形算法的实现2.1输入模块（8）2.2显示线性规划数学模型模块（10）2.3标准化模块（12）2.4迭代计算模块(15）2.5显示详细迭代过程模块(18)4 软件测试4.1单纯形算法(25)参考文献(29)281 算法分析1.1单纯形算法1.1.1单纯形法的基本思路利用求线性规划问题基本可行解（极点）的方法求解较大规模的问题是不可行的。有选择地取基本可行解，即从可行域的一个极点出发，沿着可行域的边界移动到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。在线性规划的可行域中先找出一个可行解，检验它是否为最优解，如果是最优解，计算停止；如果不是最优解，那么可以判断线性规划无有限最优解，或者根据一定步骤得出使目标函数值接近最优值的另一个基本可行解。由于基本可行解的个数有限，所以总可以通过有限次迭代，得到线性规划的最优基本可行解或判定线性规划无有限最优解。1.1.2单纯形法的基本步骤描述第1步：求初始基可行解，列出初始单纯形表。对非标准型的线性规划问题首先要化成标准形式。由于总可以设法使约束方程的系数矩阵中包含一个单位矩阵，以此作为基求出问题的一个初始基可行解。为检验一个基可行解是否最优，需要将其目标函数值与相邻基可行解的目标函数值进行比较。为了书写规范和便于计算，对单纯形法的计算设计了一种专门表格，称为单纯形表(见表1-1)。迭代计算中每找出一个新的基可行解时，就重画一张单纯形表。含初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表。第2步：最优性检验。表1-1单纯形表cjc1cmcjcnCB基bx1xmxjxnc1c2cmx1x2xmb1b2bm100001a1ja2jamja1na2namncj-zj00如表中所有检验数cj-zj0，且基变量中不含有人工变量时，表中的基可行解即为最优解，计算结束。当表中存在cj-zj 0时，如有Pj0，则问题为无界解，计算结束；否则转下一步。第3步：从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。1.确定换入基的变量。只要有检验数j0，对应的变量xj就可作为进基的变量，当有一个以上检验数大于零时，一般从中找出最大一个k，其对应的变量xk作为进基变量。2.确定出基的变量。确定xr是出基变量,ark为主元。3.用进基变量xk替换出基变量xr，得到一个新的基。对应这个基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表(表1-2)。(1) 把第r行乘以之后的结果填入新表的第r行；对于行，把第r行乘以之后与原表中第i行；在列中的r行位置填入，其余行不变；在列中用代替r行原来的值，其余的行与原表中相同。(2) 然后用的价值系数减去列的各元素与列各对应元素的乘积，把计算结果填入列的最后一行，得到检验数，计算并填入的值（以零减去列各元素与b列各元素的乘积）1。第4步：重复上述过程，就可以得到最优解或判断出无有限最优解。表1-2初始单纯形表cjc1crcmcjckCB基bx1xrxmxjxkc1ckcmx1xkxm100001010cj- zj0001.1.3单纯形算法求解线性规划的范例在实践中，根据实际问题的要求，常常可以建立线性规划问题的数学模型。下面这个范例，就是一个用单纯形算法求解的线性规划的范例。美佳公司计划制造甲,乙两种家电产品。但因财力、物力等原因，资源有限，已知制造一个家电产品分别占用的设备A，B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件的获利情况，如表1-3所示。问该公司应制造两种家电各多少件，使获取的利润为最大。表1-3 产品有关数据表项目甲乙每天可用能力设备A（h）0515设备B(h)6224调试工序(h)115利润（元）21解：根据题意构建下列线性规划模型：目标函数 约束条件 用单纯形法求解线性规划问题，标准化后得： 取初始基本可行解（单位矩阵）。初始化单纯形表并计算的过程如表1-4所示。在最优单纯形表中，非基变量的检验数均为负数，于是得到最优解，最优目标值元（表中-17/2为-Z的值）。为了能够更清晰地看清单纯形算法的解题思路以及单纯形算法表格计算过程中表格内各量的关系，把例中的3次迭代计算过程重述如下：第一次迭代：取初始可行基，那么为基变量，为非基变量。将基变量和目标函数用非基变量表示：第二次迭代：当前的可行基，那么为基变量，为非基变量。将基变量和目标函数用非基变量表示： 第三次迭代：当前的可行基，那么为基变量，为非基变量。将基变量和目标函数用非基变量表示： 在目标函数中，非基变量的检验数不是正数，于是得到最优解,最优目标值。表1-4 单纯形表表格计算过程cBxBb21000X1X2X3X4X50X31505100-0X4246201040X55110015-Z0210000X3150510032X1412/601/6037/30X5104/60-1/614/3-Z-801/30-1/300X315/20015/4-15/2-2X17/21001/4-1/2-1X23/2010-1/43/24/3-Z-17/2000-1/4-1/2在最优单纯形表中，非基变量的检验数均为负数，于是得到最优解，最优目标值元（表中-17/2为-Z的值）。图1-1单纯形算法流程图1.2大M单纯形算法1.2.1大M单纯形算法的基本思想一般线性规划问题的系数矩阵中不含单位矩阵，这时没有明显的基本可行解，常常采用引入非负人工变量的方法来求得初始基本可行解，一般采用大M单纯形算法。大M法也称为惩罚法，主要做法是取M0为一个任意大的正数，在原问题的目标函数中加入-M乘以每一个人工变量。首先根据不等式符号添加正的或负的松弛变量，查找加入的松弛变量是否构成单位矩阵，构成单位矩阵则计算方法和单纯形算法一样；若是尚未构成单位矩阵，则添加的人工变量与松弛变量构成一个单位矩阵后进行计算。松弛变量在目标函数中的系数为0，而人工变量的系数则为-M，此处-M是强加于人工变量的一种惩罚，其目的是为了强制人工变量由变量转换为非基变量，使之恢复原问题或者说与原问题等价。M在计算时，可看作一个任意大的正数，非严格的说法，仅为便于在检验数含M时判断值的正负，但M并不是无穷大，理论上可以证明，M只要取到某个数值以上就可以。1.2.2大M单纯计算法的基本步骤描述1. 添加松弛变量，看松弛变量的系数是否构成单位矩阵，若尚未构成单位矩阵则加入人工变量，迫使人工变量的系数和松弛变量的系数构成单位矩阵。这也是添加人工变量的目的。2. 加入松弛变量和人工变量后就完成了标准化线性规划模型。3. 计算标准化后的线性规划模型的方法是应用单纯形算法，所以大M单纯形算法的迭代计算方法和单纯形算法的计算方法相同。4. 大M单纯形算法中含有人工变量系数“-M”，加入人工变量的目的是构成单位矩阵，应用单纯形算法迭代计算，但是不能改变原问题，因此让每个人工变量乘以“-M”，就能够保证标准化后的线性规划模型与原问题等价。5. “-M”作为字符不能参与计算，然而M作为一个任意大的正数，一般在教学中所要解决的线性规划模型规模并不太大，因此取值M=10000参与计算。计算过程中的所有“M”都有10000代替。除了上述需要注意的问题之外，单纯形表的计算过程与单纯形算法的计算过程相同，根据算法步骤依次迭代计算，直到得到最优解或判断出无有限最优解为止。2 单纯形算法的实现2.1输入模块2.1.1模块描述此模块所要实现的功能是从窗体输入线性规划数学模型。首先是登录界面，用户可以根据自己的实际需要，选择运用单纯形法还是大M法进行计算。这节我们点击“单纯形法”按钮，演示单纯形法的计算过程。打开单纯形法的页面后，从窗体输入模型的变量个数到变量VarNum、输入约束个数到ConNum，然后根据模型的变量个数和约束条件个数自动生成一个表格，为表格的每行取一个class属性，这样做是为了方便把输入的数存放到数组里。由于自动生成的表格是不可以在其中输入数据 ，所以在需要输入数据的单元格中包上一个文本框（有不需要输入数据的单元格如：表头等提示信息），然后再往该表中输入目标函数系数、约束条件系数和约束常量b，因为输入的是一个ConNum+1行和VarNum+1列的一个矩阵，所以存入的时候要用一个二维数组ConArray存放。首先在文本框内输入变量个数VarNum的值和约束个数ConNum的值。输入之后就确定了线性规划数学模型的变量个数以及约束个数。在输入模型的过程中，依次输入约束条件系数、约束常量和目标函数系数。输入之后就确定了线性规划数学模型。2.1.2关键算法描述 1. 自动生成表格的关键算法描述： For(var i=0;i约束条件个数+2;i+) str=str+; For(var j=0;j模型变量个数+2;j+) If(j=0&i=0)|(j=(模型变量个数+1)&(i=约束条件个数+1) str=str+-; Else If(i=0) If(j=模型变量个数+1) str=str+b; Else str=str+x(+j+);Else If(j=0) If(i=约束条件个数+1)str=str+目标函数系数; Else str=str+c(+i+); Else If(i=约束条件个数+1&j!=0) str=str+; Else str=str+; str=str+; 2.将数据存入二维数组的关键算法描述：For(var i=0; iconNum+1; i+) For(var j=0;jvarNum+2;j+) If(i=0&j0)conArrayij=$(.sign+(i)0.value; Else if(i0) If(j=varNum+1) conArrayij=$(.cells+i)j-1.value; Else conArrayij=$(.cells+i)j.value; 说明：使用jquery的语法”$(“.cells”)”是为了简化编程编程，这里只使用了jquery的选择器用来代替javaScript的document.getElementById()。“.cells”和”.sign”，是前面所说的每行的class属性。2.2显示线性规划数学模型模块2.2.1模块描述首先显示目标函数，根据变量个数VarNum显示出线性规划模型，“Max Z=”是目标函数的固定显示方式，其后的目标函数系数和变量的下标是根据每行的数组元素和变量个数VarNum决定的。显示的方式根据变量的不同有两种表达方法：若不是最后一个变量，X(i)后要加上“+”号；若是最后一个变量，则其后不需要加上“+”号,同时要是约束条件是系数如果是负数也不需要加上“+”号。如此目标函数的显示就完成了。其次是约束条件的显示，约束条件中有一个非负约束。根据约束个数ConNum分行显示约束条件，变量个数VarNum+1在显示变量的情况下还要显示约束常量b，约束条件系数和约束常量都存放在约束条件系数数组ConArray()中。第一个约束条件前要显示“S.T.”，然后再显示约束条件，根据变量个数显示，最后一个变量后加上“=0”，这表示线性规划数学模型中的变量是非负的。2.2.2关键算法描述（1） 显示目标函数的关键算法描述： For (i = 1; i=变量个数; i+) If ( i = 最后一个变量|后一个变量的系数是负数) 最后一个变量后无“+”号 Else 不是最后一个变量则每个变量后都要加上“+”号 （2） 显示约束条件的关键算法描述： For (j = 1; j= 约束个数; j+) For ( i= 1; i=变量个数+1; i+) If ( i = 最后一个变量|后一个变量的系数是负数) 最后一个变量后无“+”号 Else If（i = 变量个数+1） 则在每个约束条件后加上“=”约束常量 Else 若不是最后一个变量则每个变量后边都自带一个“+”号 （3） 显示非负约束的关键算法描述： For (i = 1; i=0” Else 不是最后一个变量则在变量后自带“，”号 备注：因为变量和约束系数的都存入到二维数组ConArray中，在显示线性规划模型时是从数组中拿出每个变量和约束系数的，上面“j=0”，这表示线性规划数学模型中的变量是非负的。同时在标准化之后要将ConArray中的数以及加好了松弛变量后松弛变量的系数从新倒入到一个新的数组ConArray1中，因为在标准化时本人是从数组中再拿出那些系数的，这样的话做起来比较方便，而且javaScript的一个好处就是在创建二维数组的时候不需要考虑你要是几行几列是数组，只要你往里面加了内容他会帮你自动扩充数组的长度。2.3.2关键算法描述（1） 标准化约束条件的关键算法描述： For (j = 1; j=约束条件个数; j+) For(i=1;i=变量个数+1;i+) If(i=变量个数+1) 最后一个变量后不显示“+”号 Else If( i = 变量个数+1) 加入松弛变量和约束常量b Else if(后一个变量的系数大于零) 每个变量后都自带一个“+”号 显示约束条件说明：因为变量和约束系数的都存入到二维数组ConArray1中，在标准化的时候是从数组中拿出每个变量和约束系数的，上面“j=约束条件个数”等for语句中的条件其实是根据数组的长度来定，这里这样写主要是为了让描述更容易理解，后面也是同样的。（2） 标准化非负约束的关键算法描述： For (i = 1;i=”符号 Else 其他变量后加上“，”号 2.4迭代计算模块2.4.1模块描述该模块的功能是完成线性规划数学模型的计算，应用单纯形算法计算最优解和最优目标值。首先找出初始基本可行基，这里都是用松弛变量作为基本可行基的，因为它们组合起来正好是一个单位矩阵，然后就是把ConArray1中的数再倒入到mydata数组中，其中mydata数组中的值正好跟初始单纯形表中的每个单元格的数一一对应的。这样是为了更好的生成单纯形表，同时在以后的迭代过程中只要在改变数组中的值就可以生成下一步迭代的单纯形表了。接下来就开始计算，计算分为以下几个步骤：（1） 计算变量的检验数Check( )，本来只要计算非基变量的检验数，因为基变量的检验数肯定是0，但是为了计算简单同时因无论是基变量还是非基变量它们检验数的计算规则都是一样的，所以我们不管是不是非基变量都计算它的检验数，同时把新计算出来的检验数存入到mydata的最后一行，在计算出变量的检验数后，若检验数全小于或等于0，则当前解为最优解MaxVal，不用再计算；否则若存在检验数大于0，则选取最大检验数所对应的变量作为进基变量然后记录进基变量在二维数组mydata中的下标indexIn，本次计算的函数为InBase( )。 （2） 根据进基变量在二维数mydata中的下标indexIn系数求出基变量在mydata中的下标indexOut。indexOut的计算规则是将mydata数组中存放b的那一列除以indexIn的那一列，如果indexIn的那一列有小于0的数则的对应那列的该行就用“-”代替，否则就存入那个商，找出mydata数组中存那列最小的那行，该行就是出基变量对应的那行记录他的系数就是indexOut。若那列的数全是“-”的话说明出基变量所对应的系数都小于0，这样就可以判断出该模型是没有有限最优解的。在indexIn和indexOut相交的那一个即mydataindexOut-1indexIn-1存入的就是本次迭代的主元，本次计算的函数为OutBase( )。（3） 更新系数矩阵updataMydata( )。更新的方法是出基变量的系数行的各个系数除以主元后代替原来的系数。非出基变量的系数行乘以负的进基变量对应列与本行交汇的系数除以主元后加上本行的各个系数后的值代替原来的系数。约束常量也是这样计算并替换。在基变量BasVar( )中，进基变量替换出基变量的下标值。（4） 接下来再根据新的系数矩阵求检验数Check( )、进基变量InBase( )、出基变量OutBase r ( )、和更新系数矩阵updataMydata ( )，如此循环，直到计算出最优解。最优目标值MaxVal则等于基变量的目标函数系数与其对应约束常量b的累加和。但是问题来了，循环几次呢？如何知道本次计算的MaxVal就是最优值呢？我们可以通过一个递归来完成循环的次数，同用一个变量flag存放IndexIn是否在本次迭代后是否改变，如果改变就继续迭代如果没有改变说明本次就是最优的情况。2.4.2关键算法描述（1） 迭代时递归关键算法描述： Function 递归方法( ) Check( ); InBase( ); OutBase( ); If(本次迭代后indexIn的值改变了)调用本方法（2） 计算检验数关键算法描述： 基变量的检验数计算： For(k = 1; k=约束个数; k+) 是基变量则基变量所对应的检验数为0 非基变量的检验数计算： For(g =1; g=约束个数; g+) 检验数 = 基变量的目标函数系数进基变量所对应的系数 （3） 寻找进基变量关键算法描述： For( i = 1; i0) 在大于零的检验数中找最大值其所对应的变量作为进基变量 （4） 计算出基规则关键算法描述： For(i = 1; i=约束个数; i+) If (进基变量的系数=0 | 进基变量检验数=0) 进基规则无穷大，用“-”表示 Else 若是进基变量所对应的系数大于零则计算出基规则 出基规则基变量所对应的约束常量进基变量所对应系数 （5） 寻找出基变量的关键算法描述： For (i = 1; i=约束个数; i+) If (出基规则中比较出最小的出基规则) 最小出基规则所对应的变量即为出基变量 （6） 更新系数矩阵关键算法描述： For(i = 1; i=约束个数; i+) If (非出基变量所对应的系数) 非出基变量的系数行=出基变量的系数行（进基变量对应列与本行交汇的系数主元）+本行的各个系数 Else 出基变量的系数行=出基变量的系数行（1主元） （7） 计算临时最优解的关键算法描述： For(i = 1; i=约束个数; i+) 临时最优解=各基变量的目标函数系数各约束常量系数的累加和（8）生成单纯形表的关键算法首先同过document.createElement(table);添加一个表格对象For(i=1; i=约束条件个数+3; i+)在表格中插入一行For(j=1; j=更新后的系数矩阵的列数; j+) 在该行中插入个单元格（单元格中的内容等于mydata中的值） 说明：为了方便学生学习单纯形表格的迭代计算过程，本系统将所有迭代过程放入一个表格里，这样使学生浏览起来更加简单、明了。2.5显示详细迭代过程模块2.5.1模块描述详细迭代过程模块旨在把计算的每一个过程及每个过程中变量的变化显示出来，让学习者更确切的懂得计算的细节。每次迭代中的计算方式都是相同的，直到求出最优解或无解才停止计算。其中每次迭代包括计算检验数、确定进基变量、计算出基规则以及计算临时最优解的详细计算过程。其详细计算过程描述如下：把变量名的信息全部存到一个二维数组StrArray中，就拿我们经常使用的模型来说StrArray中的内容如下表：-C(1)C(2)C(3)C(4)C(5)CBXBbX(1)X(2)X(3)X(4)X(5)C(3)X(3)b(1)A(1,1)A(1,2)A(1,3)A(1,4)A(1,5)-C(4)X(4)b(2)A(2,1)A(2,2)A(2,3)A(2,4)A(2,5)-C(5)X(5)B(2)A(3,1)A(3,2)A(3,3)A(3,4)A(3,5)-Z(1)(2)(3)(4)(5)-详细迭代过程的表达式如：(1) = C(1)-C(3)*A(1,1)-C(4)*A(2,1)- C(5)*A(3,1) =1500-0*3-0*2-0*0=1500。这个表达式是通过字符串的拼接完成的，在迭代过程时是通过递归完成的，要完成详细迭代过程只需在迭代的方法中多加入几个函数，就可以完成详细迭代的过程，函数messageAbCheck完成检验数的详细迭代过程和该次最优解的详细迭代过程，函数calCoe()完成约束系数的详细迭代过程，最优解的详细迭代表达式为：Z=C(3)*b(1)+C(4)*b(2)+C(5)*b(3)=0-0*65+0*40+0*75=0。约束系数详细迭代过程的表达分为两种,当它同主元在同一行的时候表达式为：A(3,1)=A(3,1)/A(3,2)=0/3=0 (A(3,2)是主元) ，当与主元不在同一行的时候表达式是：A(1,1)=A(3,1)*-A(1,2)/A(3,2)+A(1,1)=0* (-2/3)+3=3 。是否显示详细迭代过程，根据各人的不同需要我们做了比较人性化的设计，若只需得到计算结果，就不显示详细计算过程；若是学习运筹学的算法，那么在运行软件的过程中就可以点击“显示详细迭代过程”按钮，就可以看到详细迭代过程，一目了然，过程清晰，比较容易理解单纯形法的原理。2.5.2关键算法描述（1） 显示计算检验数详细及最优解过程的函数代码：Function messageAbCheck()/mymessage存放 mymessage=mymessage+检验数的计算过程：;/拼接表达式一的字符串如C(1)-C(3)*A(1,1)-C(4)*A(2,1)- C(5)*A(3,1) var str1=;/拼接表达式一的字符串如1500-0*3-0*2-0*0var str2=; /因为在strArray中最后一行检验数的计算是从第三列开始的 For(var i=3;i加上松弛变量后约束系数的个数+3;i+) str1=; str2=; str1=strArrayconNum+2i+=+strArray0i+-; str2=mydata0i+-; For(var j=2;jconNum+2;j+)/从strArray数组中第一个存放检验数的单元开始拼接/如果是最后一个是话 If(j=conNum+1) str1=str1+strArrayj0+*+strArrayji+=;str2=str2+mydataj0+*+mydataji+=+mydataconNum+2i+; /其他情况 else str1=str1+strArrayj0+*+strArrayji+-; str2=str2+mydataj0+*+mydataji+-; /把两段字符串加在一起 mymessage=mymessage+str1+str2; /本次最优目标值的详细计算过程/将str1，str2重新清空 str1=; str2=; mymessage=mymessage+本次迭代最优目标值的详细计算过程:; For(var i=2;iconNum+2;i+) If(i=conNum+1) str1=str1+strArrayi0+*+strArrayi2+=;str2=str2+mydatai0+*+mydatai2+=+(-mydataconNum+22)+; else str1=str1+strArrayi0+*+strArrayi2+; str2=str2+mydatai0+*+mydatai2+; mymessage=mymessage+Z=+str1+str2;（2） 显示更新系数矩阵详细过程的函数描述：Function calCoe() mymessage=mymessage+第+(count)+次迭代; mymessage=mymessage+约束系数的详细计算过程：; mymessage=mymessage+本次迭代主元为：+strArrayindexOut indexIn +; var str1=; var str2=;/result是用来存放结果的数即表达式的计算结果 var result; For(var i=2;iconNum+2;i+) For(var j=3;jconNum+conNum+3;j+) str1=; str2=;/如果跟主元在同一行的话 If(i=indexOut)str1=strArrayij+=+strArrayij+/+strArrayindexOutindexIn+=;str2=mydataij+/+mydataindexOutindexIn+=;result=parseFloat(mydataij/mydataindexOutindexIn).toFixed(2);mymessage=mymessage+str1+str2+result+; else str1=strArrayij+=+strArrayindexOutj+*-+strArrayiindexIn+/+strArrayindexOutindexIn+strArrayij+=; str2=mydataindexOutj+*+(-mydataiindexIn)+/+mydataindexOutindexIn+mydataij+=;/计算表达式的结果 result=parseFloat(parseFloat(mydataindexOutj)*(parseFloat(-mydataiindexIn)/parseFloat(mydataindexOutindexIn)+ parseFloat(mydataij).toFixed(2);/将表达式和结果都拼接到一起mymessage=mymessage+str1+str2+result+; 4 软件测试4.1单纯形算法输入六组线性规划模型对软件进行测试，模型及其结果如下所示：在输入模型界面输入如下数据：变量个数：3约束条件个数：4-X(1)X