IE10-OR05-CH1-线性规划及单纯形法.ppt

第第1页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学第第5 5讲讲 目目 录录CH1 CH1 线性规划及单纯形法线性规划及单纯形法|1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型|1.2 1.2 线性规划问题的解线性规划问题的解|1.3 1.3 线性规划的单纯形法线性规划的单纯形法|1.3.1 1.3.1 单纯形法的基本思路单纯形法的基本思路|1.3.2 1.3.2 确定初始基可行解确定初始基可行解|1.3.3 1.3.3 最优性检验最优性检验|1.3.4 1.3.4 基可行解的转换基可行解的转换|1.3.5 1.3.5 单纯形法的步骤单纯形法的步骤|1.4 1.4 单纯形表单纯形表|1.5 1.5 单纯形法应用的几个问题单纯形法应用的几个问题|1.6 1.6 线性规划建模举例线性规划建模举例西南科技大学制造学院西南科技大学制造学院西南科技大学制造学院西南科技大学制造学院IEIE系系系系小结：线性规划求解流程图（小结：线性规划求解流程图（小结：线性规划求解流程图（小结：线性规划求解流程图（P35)P35)2 2第第3页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学1.5 1.5 单纯形法应用的几个问题单纯形法应用的几个问题|1.5.1 1.5.1 大大MM法和两阶段单纯形法法和两阶段单纯形法|1.5.2 1.5.2 退化退化第第4页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学1.5.2退化|若用若用 规则确定换出变量时，有时存在两个以上的最规则确定换出变量时，有时存在两个以上的最小比值，这样在下一次迭代中就有一个或几个基变小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。当出现退化解时，会量等于零，这就出现退化解。当出现退化解时，会出现循环。出现循环。|19741974年勃兰特年勃兰特(Bland)(Bland)提出了一种简便规则：提出了一种简便规则：|(1)(1)选取选取 j0j0中下标最小的非基变量中下标最小的非基变量xkxk为换入变为换入变量量k=min(j|k=min(j|j0)j0)|(2)(2)当按当按 规则计算存在两个和两个以上最小比值规则计算存在两个和两个以上最小比值时，始终选取下标最小的基变量换出变量。时，始终选取下标最小的基变量换出变量。第第5页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学1.6 1.6 线性规划建模举例线性规划建模举例|线性规划技术应用广泛：军事、工业、农业线性规划技术应用广泛：军事、工业、农业|财富财富500500强公司中，有强公司中，有85%85%使用线性规划技术帮助决使用线性规划技术帮助决策企业决策：生产计划、运输、财务、营销策企业决策：生产计划、运输、财务、营销|建模步骤：建模步骤：1 1.理解要解决的问题，了解解题的目标和条件；理解要解决的问题，了解解题的目标和条件；2.2.定义决策变量（定义决策变量（x1 x1，x2 x2，xn xn），每一组值表），每一组值表示一个方案；示一个方案；3.3.用决策变量的线性函数形式写出目标函数，确定最用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；大化或最小化目标；4.4.用一组决策变量的等式或不等式表示解决问题过程用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件中必须遵循的约束条件第第6页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学线性规划求解工具简介线性规划求解工具简介|Excel SolverExcel Solver|Lindo Lindo Linear Interactive and Discrete OptimizerLinear Interactive and Discrete Optimizer字首的缩字首的缩写，即写，即“交互式的线性和离散优化求解器交互式的线性和离散优化求解器”|Lingo Lingo Linear Interactive and General OptimizerLinear Interactive and General Optimizer字首的缩写，字首的缩写，即即“交互式的线性和通用优化求解器交互式的线性和通用优化求解器”|MatlabMatlab|第第7页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学vvLINDOLINDO,可以用来求解线性规划可以用来求解线性规划(LP-Linear Programming)(LP-Linear Programming)、整数规划整数规划(IP-Integer Programming)(IP-Integer Programming)和和 二次规划二次规划(QP-(QP-Quadratic Programming)Quadratic Programming)问题问题.v 这套软件包由美国芝加哥大学的这套软件包由美国芝加哥大学的Linus SchargeLinus Scharge教授于教授于19801980年前后开发，专门用于求解最优化问题，后经不断完善和扩年前后开发，专门用于求解最优化问题，后经不断完善和扩充，并成立充，并成立LINDOLINDO公司进行商业化运作，取得了巨大的成功。公司进行商业化运作，取得了巨大的成功。全球全球财富财富杂志杂志500500强的企业中，一半以上使用该公司产强的企业中，一半以上使用该公司产品，其中前品，其中前2525强企业中有强企业中有2323家使用该产品。家使用该产品。vv该软件包功能强大，版本也很多，而我们该软件包功能强大，版本也很多，而我们 使用的只是演示使用的只是演示版（试用版），演示版与正式版功能基本上是版（试用版），演示版与正式版功能基本上是 类似的，只是类似的，只是能够求解问题的规模受到限制，总变量数不超过能够求解问题的规模受到限制，总变量数不超过3030个，这在个，这在我们目前的使用过程中，基本上是足够。我们目前的使用过程中，基本上是足够。第第8页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学初试 LINDOLILINDO NDO 中己假设所有的变量都是非负的中己假设所有的变量都是非负的,所以非负约束所以非负约束条件不必再输入到计算机中条件不必再输入到计算机中;LILINDO NDO 也不区分变量中的大小写字符也不区分变量中的大小写字符 ;约束条件中的约束条件中的“=”可用可用“”代代替替.解决一个简单的线性规划（解决一个简单的线性规划（LP）问题）问题其Lindo程序为：例9现在我们用Lindo软件来求解这个模型，单击工具栏中的 图标，便得到以下运行状态窗口：Lindo求解器运行状态窗口各项的含义名称含义Status显示当前求解状态：Optimal表示已经达到最优解；其他可能的显示：Feasible，Infeasible，UnboundedIterations显示迭代次数Infeasibility 约束不满足的量；0表示这个解是可行的Objective显示当前解的目标函数值Best IP显示整数规划当前解的最佳标函数值：N/A表示无答案或无意义IP Bound显示整数规划的界Branches显示分支定界算法已经计算的分支数：N/A表示无答案或无意义Elapsed Time显示计算所用时间：0：00说明计算太快，用时还不到0.05SUpdate Time显示控制和刷新本界面的时间间隔Interrupt Solver中断求解程序Close关闭该窗口添加Lindo求解器10显示结果如下单纯行法迭代两次得到最优解最优目 标值最优解各变量 的值对偶价格影子价格：表示该非基变量增加一个单位而其他变量不变时目标函数减少的量（对max型问题）松弛变量的值【紧约束】单纯行法进行两次迭代11变量以字母开头、不区分大小写，变量名可不超过变量以字母开头、不区分大小写，变量名可不超过8个字符；个字符；变量不能出现在约束条件的右端，右端只能是常数；变量与系变量不能出现在约束条件的右端，右端只能是常数；变量与系数之间可以有空格，但数之间可以有空格，但绝对不能有任何运算符绝对不能有任何运算符；Lindo中不接受中不接受”（）（）“和逗号和逗号”，“等任何运算符号（除非等任何运算符号（除非在注释语句中）；在注释语句中）；模型中的表达式应当经过化，如不能出现模型中的表达式应当经过化，如不能出现（X+1）2+2X2 +3Y，而应该写成，而应该写成3X2+2X+3Y+1；模型中已假定所有变量非负，可在模型的模型中已假定所有变量非负，可在模型的”end“语句后面用语句后面用命令命令”free“取消变量的非负假定，其用法是在取消变量的非负假定，其用法是在”free“后面后面跟变量名；跟变量名；在模型的在模型的”end“语句后面可以用命令语句后面可以用命令”SUB“设定变量的上界，设定变量的上界，用命令用命令”SLB“设定变量的下界；设定变量的下界；Lindo中以中以“！”开始的是说明语句，说明语句也以开始的是说明语句，说明语句也以“;”结束。结束。使用使用Lindo软件的一些注意事项：软件的一些注意事项：12第第13页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学例例 有一家具制造车间有一家具制造车间,制造书桌制造书桌(DESK)(DESK)、桌子、桌子(TABLE)(TABLE)、椅子椅子(CHAIR),(CHAIR),所用原料及木工、漆工所用原料及木工、漆工的数据如表的数据如表1 1所示所示 .每个书桌每个书桌每个桌子每个桌子每个椅子每个椅子 资源总数资源总数木木料料8 8单位单位6 6单位单位1 1单位单位4848单位单位漆工漆工4 4单位单位2 2单位单位1.51.5单位单位2020单位单位木工木工2 2单位单位1.51.5单位单位0.50.5单位单位8 8单位单位成品单价成品单价 6060单位单位3030单位单位2020单位单位表 1第第14页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学若要求桌子的生产量不超过若要求桌子的生产量不超过 5 5 件件,问如何安排三种产品的问如何安排三种产品的产量可使收入最大产量可使收入最大?用用 分别表示书桌、桌子、椅子的生产量分别表示书桌、桌子、椅子的生产量.建立建立LP 模型模型 :LP OPTIMUM FOUND AT STEP 2OBJECTIVE FUNCTION VALUE1)280.00000VARIABLE VALUE REDUCED COSTXI 2.000000 .000000X2 .000000 5.000000X3 8.000000 .000000 ROW SLACK OR SURPLUS DUAL PRICES 2)24.000000 .000000 3).000000 10.000000 4).000000 10.000000 5)5.000000 .000000LINDO在2次迭代后得到最优解。最优目标值最优解带有松弛变量的最优解检验数15第第16页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学 例例1 1某昼夜服务的公交线路每天各时间段内所需司机某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员既能满足工作需要，又配备最少司机和乘务人员?v 人力资源分配的问题人力资源分配的问题 解：设解：设 x xi i 表示第表示第i i班次时开始上班的司机和乘务人员数班次时开始上班的司机和乘务人员数,这样建立如下的数学模型。这样建立如下的数学模型。目标函数：目标函数：Min Min x x1 1+x x2 2+x x3 3+x x4 4+x x5 5+x x6 6 约束条件：约束条件：s.t.s.t.x x1 1+x x6 6 60 60 x x1 1+x x2 2 70 70 x x2 2+x x3 3 60 60 x x3 3+x x4 4 50 50 x x4 4+x x5 5 20 20 x x5 5+x x6 6 30 30 x x1 1,x x2 2,x x3 3,x x4 4,x x5 5,x x6 6 0 017第第18页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学 例例2 2一家中型的百货商场，它对售货员的需求经一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作息，售货人员每周工作5 5天，休息两天，并要求休天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数息，既满足工作需要，又使配备的售货人员的人数最少？最少？解：设解：设 x xi i(i=1,2,(i=1,2,7),7)表示星期一至日开始休息表示星期一至日开始休息的人数的人数,这样我们建立如下的数学模型。这样我们建立如下的数学模型。目标函数：目标函数：Min Min x x1 1+x x2 2+x x3 3+x x4 4+x x5 5+x x6 6+x x7 7 约束条件：约束条件：s.t.s.t.x x1 1+x x2 2+x x3 3+x x4 4+x x5 5 28 28 x x2 2+x x3 3+x x4 4+x x5 5+x x6 6 15 15 x x3 3+x x4 4+x x5 5+x x6 6+x x7 7 24 24 x x4 4+x x5 5+x x6 6+x x7 7+x x1 1 25 25 x x5 5+x x6 6+x x7 7+x x1 1+x x2 2 19 19 x x6 6+x x7 7+x x1 1+x x2 2+x x3 3 31 31 x x7 7+x x1 1+x x2 2+x x3 3+x x4 4 28 28 x x1 1,x x2 2,x x3 3,x x4 4,x x5 5,x x6 6,x x7 7 0 019第第20页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学 例例3 3某公司面临一个是外包协作还是自行生产的问某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应两种产品的铸造中，由本公司铸造和由外包协作各应多少件？多少件？生产计划的问题生产计划的问题 解：设解：设 x x1 1,x x2 2,x x3 3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，数，x x4 4,x x5 5 分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。求数。求 x xi i 的利润：利润的利润：利润 =售价售价 -各成本之和各成本之和:产品甲全部自制的利润产品甲全部自制的利润=23-(3+2+3)=15=23-(3+2+3)=15 产品甲铸造外协，其余自制的利润产品甲铸造外协，其余自制的利润 =23-(5+2+3)=13=23-(5+2+3)=13 产品乙全部自制的利润产品乙全部自制的利润 =18-(5+1+2)=10=18-(5+1+2)=10 产品乙铸造外协，其余自制的利润产品乙铸造外协，其余自制的利润 =18-(6+1+2)=9=18-(6+1+2)=9 产品丙的利润产品丙的利润=16-(4+3+2)=7=16-(4+3+2)=7 可得到可得到 x xi i （i=1,2,3,4,5i=1,2,3,4,5）的利润分别为的利润分别为 1515、1010、7 7、1313、9 9 元。元。21通过以上分析通过以上分析,可建立如下的数学模型可建立如下的数学模型:目标函数：目标函数：Max 15Max 15x x1 1+10+10 x x2 2+7+7x x3 3+13+13x x4 4+9+9x x5 5 约束条件：约束条件：5 5x x1 1+10+10 x x2 2+7+7x x3 3 8000 8000 6 6x x1 1+4+4x x2 2+8+8x x3 3+6+6x x4 4+4+4x x5 5 12000 12000 3 3x x1 1+2+2x x2 2+2+2x x3 3+3+3x x4 4+2+2x x5 5 10000 10000 x x1 1,x x2 2,x x3 3,x x4 4,x x5 5 0 022第第23页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学 例例4 4 某工厂要做某工厂要做100100套钢架，每套用长为套钢架，每套用长为2.9 m,2.1 m,1.5 m2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长的圆钢各一根。已知原料每根长7.4 m7.4 m，问：应如何下料，问：应如何下料，可使所用原料最省？可使所用原料最省？解：共可设计下列5 种下料方案，见下表 设 x1,x2,x3,x4,x5 分别为上面 5 种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Min x1+x2+x3+x4+x5 约束条件：s.t.x1+2x2 +x4 100 2x3 +2x4+x5 100 3x1+x2+2x3 +3x5 100 x1,x2,x3,x4,x5 0v套裁下料问题套裁下料问题用用“运筹学运筹学”软件计算得出最优下料方案：按方案软件计算得出最优下料方案：按方案1 1下料下料3030根；按方案根；按方案2 2下料下料1010根；按方案根；按方案4 4下料下料5050根。根。即即 x x1 1=30;=30;x x2 2=10=10；x x3 3=0=0；x x4 4=50=50；x x5 5=0=0；只需只需9090根原材料就可制造出根原材料就可制造出100100套钢架。套钢架。注意：在建立此类型数学模型时，约束条件用大于等于号注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。等于号，这一方案就不是可行解了。24投资问题 例5 某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。据测定每万元每次投资的风险指数如右表：问：问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？解：解：1 1）确定决策变量：连续投资问题 设 xij(i=15，j=14)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24252 2）约束条件：）约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是 x11+x12=200；第二年：B次年末才可收回投资，故第二年年初有资金1.1 x11，于是 x21+x22+x24=1.1x11；第三年：年初有资金 1.1x21+1.25x12，于是 x31+x32+x33=1.1x21+1.25x12；第四年：年初有资金 1.1x31+1.25x22，于是 x41+x42=1.1x31+1.25x22；第五年：年初有资金 1.1x41+1.25x32，于是 x51=1.1x41+1.25x32；B、C、D的投资限制：xi2 30(i=1、2、3、4)，x33 80，x24 100 3 3）目标函数及模型：）目标函数及模型：a)a)Max z=1.1x51+1.25x42+1.4x33+1.55x24 s.t.x11+x12=200 x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi2 30(i=1、2、3、4)，x33 80，x24 100 xij 0 (i=1、2、3、4、5；j=1、2、3、4）投资问题26b)b)所设变量与问题a相同，目标函数为风险最小，有 Min f=x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24 在问题a的约束条件中加上“第五年末拥有资金本利在330万元”的条件，于是模型如下：Min f=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t.x11+x12=200 x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi2 30(i=1、2、3、4)，x33 80，x24 100 1.1x51+1.25x42+1.4x33+1.55x24 330 xij 0 (i=1、2、3、4、5；j=1、2、3、4）投资问题27第第28页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学|教材例题教材例题:P40P42:P40P42|配料问题|生产存贮问题第第1章章 线性规划与单纯形法线性规划与单纯形法 （小结）（小结）n n1.线性规划的概念线性规划的概念（1）线性规划模型的构成）线性规划模型的构成 决策变量决策变量 目标函数目标函数：max(min)Z(是决策变是决策变量的线性函数）量的线性函数）约束条件约束条件：s.t.（满足于含决策变（满足于含决策变量的线性等式或不等式）量的线性等式或不等式）2929（2）一般形式：）一般形式：3030max=cmax=c1x x1 1+c+c2x x2 2+c+cnx xn n s.t.a s.t.a1111x x1 1+a+a1212x x2 2+a a1n1nx xn n=b=b1 1 a a2121x x1 1+a+a2222x x2 2+a a2n2nx xn n=b=b2 2 a am1m1x x1 1+a+am2m2x x2 2+a amnmnx xn n=b=bm m xj0;j=1,2,n,n b bi i0;i=0;i=1,2,m,m(3)标准形式标准形式3131 线性规划的标准形式有如下四个特点：线性规划的标准形式有如下四个特点：目标最大化；目标最大化；约束为线性等式；约束为线性等式；决策变量均非负；决策变量均非负；右端项非负。右端项非负。(4)剩余变量、松驰变量及意义剩余变量、松驰变量及意义32322.有关线性规划解的概念有关线性规划解的概念n n(1)概念：凸集、可行解、可行域、最概念：凸集、可行解、可行域、最优解、最优值、基、基变量、基解、基优解、最优值、基、基变量、基解、基可行解、可行基、最优基。可行解、可行基、最优基。n n(2)可行域、基解、基可行解、最优基可行域、基解、基可行解、最优基的关系。的关系。33333.图解法图解法n n图解法的步骤：图解法的步骤：(1)建立直角坐标系建立直角坐标系(2)图示约束条件、找出可行解图示约束条件、找出可行解(3)图示代表目标函数的直线及目标函数图示代表目标函数的直线及目标函数值增加（或减小）的方向值增加（或减小）的方向(4)找出最优解找出最优解34344.单纯形法单纯形法(1)理论基础理论基础n n定理定理若若LP问题可行域存在，则可行问题可行域存在，则可行域是凸集合域是凸集合n n定理定理 LP问题的基可行解与可行域顶问题的基可行解与可行域顶点一一对应点一一对应n n定理定理若若LP问题存在最优解，则一定问题存在最优解，则一定存在一个基可行解是最优解存在一个基可行解是最优解3535(2)单纯形法计算步骤单纯形法计算步骤3636线性规划求解流程图线性规划求解流程图37375.大大M法与二阶段法法与二阶段法n n(1)大大M法法人工变量在目标函数中的系数确定：人工变量在目标函数中的系数确定：若目标函数为若目标函数为maxZmaxZ，则系数为，则系数为-M-M；否则；否则为为M M计算方法：单纯形法计算方法：单纯形法3838(2)二阶段法二阶段法第一阶段第一阶段：求解一个目标函数仅含人工变量，：求解一个目标函数仅含人工变量，且为极小化的线性规划问题，其最优表有两且为极小化的线性规划问题，其最优表有两种情况：种情况：目标函数最优值为目标函数最优值为0 0则去掉人工则去掉人工变量转为第二阶段变量转为第二阶段目标函数最优值不为目标函数最优值不为0 0则原问题则原问题无可行解，停止计算无可行解，停止计算第二阶段第二阶段：去掉第一阶段中的人工变量，将第：去掉第一阶段中的人工变量，将第一阶段得到的最优解作为初始基可行解，利一阶段得到的最优解作为初始基可行解，利用单纯形法继续进行迭代，直至求出原问题用单纯形法继续进行迭代，直至求出原问题最优解最优解3939