课程设计论文-求解线性规划的两阶段法设计与实现.doc

课程设计（论文）课程设计（论文）课程名称：系统优化算法设计与实现题目：求解线性规划的两阶段法设计与实现院（系）：管理学院专业班级：信管1501姓名：学号：指导教师：2014年7月18日西安建筑科技大学课程设计（论文）任务书专业班级：信管1501学生姓名：指导教师（签名）：一、课程设计（论文）题目一、课程设计（论文）题目求解线性规划的两阶段法设计与实现二、本次课程设计（论文）应达到的目的二、本次课程设计（论文）应达到的目的系统优算法设计与实现课程设计是实践教学环节的重要组成部分，其目的是通过课程设计加深学生对系统优算法设计与实现基本知识掌握和基本编程技能的培养，提高综合运用知识解决实际问题的能力；本次要求学生通过掌握系统优算法设计与实现的程序设计方法，以提高学生独立分析问题、解决问题的能力，逐步增强实际工程训练。三、本次课程设计（论文）任务的主要内容和要求三、本次课程设计（论文）任务的主要内容和要求设计内容：设计内容：一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。第一阶段：第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。第二阶段：第二阶段：将第一阶段计算得到的最终表，除去人工变量。将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表，再进行一次单纯形法求解，若检验数符合条件时，非基变量的检验数小于0，则判断为无界解，若非基变量的检验数为0，则判断为存在无穷多最优解，否则这次求解得到最优解。要求：要求：1提交正确的和完整的程序设计代码。2提交设计说明书。3.接受现场检验。四、应收集的资料及主要参考文献：四、应收集的资料及主要参考文献：应收集的资料：本次设计应该收集和题目背景的有关资料。主要参考文献：1.胡运权.运筹学.清华大学出版社，2012五、审核批准意见五、审核批准意见教研室主任（签字）教研室主任（签字）设计总说明常用的解线性规划问题的方法有图解法，单纯形法，对偶单纯形法，解乘数法，椭球法等。而本论文即主要阐述的是从属于单纯形法的两阶段法。两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，当第一阶段求解结果表明问题有可行解时，第二阶段是从第一阶段的最终单纯形表出发，去掉人工变量，并按问题原来的目标函数，继续寻找问题的最优解，即是一种为使人工变量被替换出成为非基变量的方法。与大M法同时被广为使用，但相较于大M法，两阶段法能够求的更准确地结果。关键字：线性规划，单纯形法，两阶段法，大M法目录1绪论绪论.11.1内容简介.11.2本次课设目的.11.3课设内容.22求解线性规划的两阶段法设计与实现求解线性规划的两阶段法设计与实现设计说明设计说明.32.1程序设计过程详述.32.2编程实现过程详述.52.4原代码.73实验研究小结实验研究小结.223.1使用说明详述.223.1.1本部分功能操作注意事项.223.1.2本部分功能与其他系统的关系.223.2测试案例详述.23参考文献参考文献.28第1页共33页1绪论1.1内容简介在各种优化算法中，两阶段法（Twostage）是非常重要的一种。即如果线性规划模型中的约束条件系数矩阵不存在单位向量组，阶梯式应先加入人工变量，人工构成一个单位向量组，其只起过渡作用，不应影响决策变量的取值，两阶段法即可控制人工变量取值。寻找线性规划问题初始基可行解的一种方法.把增加人工变量的线性规划问题分为两个阶段去求解.第一阶段是构造一个辅助的人工目标函数。若原问题有可行解则在本阶段的最终单纯形表中使人工变量均为非基变量。此时，划去人工变量所在的列与人工目标函数所在的行，就得到原问题的初始可行基对应的单纯形表，进入第二阶段。1.2本次课设目的（1）通过C语言求解线性规划的两阶段法设计与实现（2）熟悉运用开发环境，基于VC+6.0的软件开发环境；（3）完成课程设计基本任务的设计及编码；第2页共33页（4）熟练掌握VC+6.0上的基本的调试方法。1.3课设内容两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其变量的系数取0，人工变量的系数取某个正的常数，（一般取1），在保持原问题约束条件不变的情况下求这个目标函数极小化的解。显然在第一阶段中，当人工变量取值为0的时候，目标函数值也为0。这时候的最优解就是原线性规划问题的一个可行解，。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有人工基变量，表明原线性规划问题无可行解。当第一阶段求解结果表明问题有可行解时，第二阶段是从第一阶段的最终单纯性表出发，去掉人工变量，并按问题原来的目标函数，继续寻找问题的最优解。第3页共33页2求解线性规划的两阶段法设计与实现设计说明2.1程序设计过程详述第一步：求出线性规划的初始基可行解，列出初始单纯形表。第二步：进行最优性检验。第三步从一个基可行解转换到另一个目标函数值更大的基可行解，列出新的单纯形表。(1)确定换入基变量。只要检验数j0对应的变量xj就可作为换入基的变量，当有一个以上检验数大于零时，一般从中找出最大的一个k。其对应变量xk作为换入基的变量（简称换入变量）。(2)确定换出基的变量，确定。确定xl为换出基的变量（简称出基变量）。元素alk决定了从一个基本可行解到另一个可行解的转移去向，取名主元素。max0kjjmin0ilikiklkbbaaa第4页共33页(3)用换入变量xk替换基变量中的换出变量，得到一个新的基。对应这个基可以找出一个新的基本可行1111()lklmmmnPPPPppP解。并可划出一个新的单纯形表。进行如下计算:a、将主元素所在的l行数字除以主元素alk，即有b、为使Pk列变换成单位向量，将单纯形表的第l行数字乘上，()ljlkaa加到单纯形表第i行数字上，计入其相应行。即有()()liiiklkljljljiklkbbbailbaaaailaAAc、计算单纯形表中各检验数，如下11111()11()lmllliikkiikiillkmkiikkkilklklkczccaccaaccaczaaa1111111()()()lmmmljjjjiijiijiikkiikiiliillkmmljljjiijkiikjjkkiilklkaczccacacaccaaaaccaccaczczaaljllljlklkabbaaa第5页共33页检验数计算同样因xk基变量后，其检验数应为零，故将单纯形表中第l行数字乘上加到该表的检验数上，得新的变量的检验数。()()kklkcza第四步：重复第二、三步一直到计算终止。第五步：去除人工变量。根据求得初始基本可行解，求得最优解。2.2编程实现过程详述1.首先第一阶段是将此问题化为标准形式，在约束条件中增加松弛变量、剩余变量、人工变量、确定基变量显示标准化后的方程组。printf(n原问题为：nn)if(ma_mi=1)printf(maxz=)elseprintf(minz=)printf(%lgx%dc11)for(i=2i=0)printf(+%lgx%dcii)elseprintf(%lgx%dcii).if(ma_mi=2)for(i=1i=0&k=0)printf(%lgx%daijj)elseprintf(%lgx%daijj)k=1printf(=%lgnbi)printf(x1x%d=0num_x)voidexchange(doublecMAXdoubletemp_cMAX)intidoubletempMAXfor(i=1i=%lgbi)breakcase3:printf(=0&k=0)printf(%lgx%daijj)elseprintf(%lgx%daijj)k=1switch(re_sti)case1:printf(=%lgnbi)breakcase2:printf(=%lgnbi)breakcase3:printf(=0nnum_x)tnum_x=num_xfor(i=1i=0&k=0)printf(%lgx%daijj)elseprintf(%lgx%daijj)k=1第17页共33页printf(=%lgnbi)printf(x1x%d=0num_x)voiditerative()intijkk_ak_flk_ak_f值为0或1，记录当前下标在arti或base里的搜索结果intbase_elemintbase_outbase_indoublesigmaMAXtempdoublue_be高斯消元里保存主元素值printf(nn第%d次迭代：nnstop)for(i=1i0)base_in=itemp=sigmai确定换出变量for(i=1i0)temp=biaibase_in+1breaktemp赋初值for(i=1i=num_sti+)if(biaibase_in0)for(j=1j=num_arj+)if(basei=artij)base_out=baseibase_elem=itemp=biaibase_inbreak人工变量优先换出if(biaibase_in0)base_out=basei第20页共33页base_elem=itemp=biaibase_inprintf(基变量：)for(i=1i=num_sti+)printf(x%dbasei)printf(换入变量：x%d换出变量：x%dbase_inbase_out)基变量变换，进行新方程初始化后迭代for(i=1i=num_sti+)if(basei=base_out)basei=base_in初始化主元素行系数value_be=abase_elembase_inbbase_elem=value_befor(i=1i=num_xi+)abase_elemi=value_befor(i=1i=num_sti+)if(i!=base_elem)bi-=bbase_elemaibase_invalue_be=aibase_infor(j=1jSTP)status=-2returniterative()voidoutput()intijdoubleXMAXprintf(n结果如下：n)printf(nX=()for(i=1i=num_xi+)for(j=1j=num_stj+)if(i=basej)Xi=bjbreakelseXi=0printf(%lgXi)第21页共33页printf()for(i=1i=num_xi+)max+=ciXiif(ma_mi=1)printf(nMaxz=%lfnmax)elseprintf(nMinz=%lfn-max)第22页共33页3实验研究小结3.1使用说明详述3.1.1本部分功能操作注意事项添加人工变量的个数；将条件不等式中含有的人工变量考虑在其中所以在此不再对含有的不等式添加松弛变量（只对含有的不等式添加松弛变量）这时候添加的人工变量要看条件不等式的形式，并加以变化。计算的时候，除数小于等于0时候，其值是为负的，此时应将定义成inf（无穷大）。3.1.2本部分功能与其他系统的关系两阶段法(two-phase)是寻找线性规划问题初始基可行解的一种方法，大M法与两阶段法都是在原问题缺少初始可行基的情况下利用引人人工变量构造人工基，以达到运用单纯形法求解原问题的目的。用大M法处理人工变量，电子计算机求解时，对M就只能在计算机内输出一个机器最大字长的数字。如果线性规划问题中的aij、bi或cj等参数值与这个代表M的数比较接近，或远远小于这个数字，由计算机计算时有可能使计算结果发生错误，从而使求解的最终结果与原问题真正的最优解不一致。为了克服这个困难，在VC+6.0的软件开发环境下直接输入初始状态下使用两阶段法，可以对添加人工变量后的线性规划问题分为两个阶段来计算，而避免M的使用。第23页共33页3.2测试案例详述例：用单纯形法两阶段法求解线性规划问题1312312323max3421.390(123)jzxxxxxxxxstxxxj首先第一阶段是将此问题化为标准形式，在约束条件中加入松弛变量x4x5x6x7后得67123412356237min421.390(17)jwxxxxxxxxxxxstxxxxj先用单纯形法解一阶段问题，迭代如下：1jjBjjBjjzccBPccyc第24页共33页其中，时目标函数中基变量的系数构成的维行向量，是上表中的第列，Bcjyj是上表中的右端列。求解过程如下单纯形表3-1b表3-1单纯形表所有判别级数，因此达到最优解，在第一阶段问题最优解中，0jjczjc00000-1-1Bc基b1x2x3x4x5x6x7x04x41211000-16x1-21-10-110-17x90310001jjcz-2400-10004x330211-1002x1-21-10-110-17x660403-31jjcz60403-4004x0000112121202x301130001301x110230121216jjcz00000-1-1第25页共33页人工变量、都是非基变量。因此我们可得到初始基可行解6x7x1234513000 xxxxx第二阶段是将表3-1中的人工变量去除，目标函数改为：67xx12345max3000zxxxxx再从表3-1最后一个表出发，继续迭代，求解过程的单纯形表如下表表3-2单纯形表得到其最优解，所以目标函数最优值12353022xxxmax32fjc-30100Bc基b1x2x3x4x5x04x000011202x3011300-31x11