运筹学单纯形计算

第1页，共41页，2022年，5月20日，10点20分，星期六1、初始单纯形表第2页，共41页，2022年，5月20日，10点20分，星期六2、换基操作第3页，共41页，2022年，5月20日，10点20分，星期六例1用单纯形法解LP第4页，共41页，2022年，5月20日，10点20分，星期六单纯形表迭代进2出5进1出3第5页，共41页，2022年，5月20日，10点20分，星期六第6页，共41页，2022年，5月20日，10点20分，星期六线性规划及单纯型法

单纯形法进一步讨论

第五节第7页，共41页，2022年，5月20日，10点20分，星期六1、人工变量法（大M法）第8页，共41页，2022年，5月20日，10点20分，星期六例1用大M法求解LP问题引入松弛变量和剩余变量第9页，共41页，2022年，5月20日，10点20分，星期六例1用大M法求解LP问题再引入“人工变量”，构造初始表：人工变量第10页，共41页，2022年，5月20日，10点20分，星期六用单纯形表迭代第11页，共41页，2022年，5月20日，10点20分，星期六用单纯形表迭代第12页，共41页，2022年，5月20日，10点20分，星期六求辅助问题的三种情况第13页，共41页，2022年，5月20日，10点20分，星期六2、两阶段法基本思想

第一阶段求解目标函数只有人工变量的辅助问题得到原问题的初始基可行解。

第二阶段利用初始基可行解求原问题的最优解第14页，共41页，2022年，5月20日，10点20分，星期六第15页，共41页，2022年，5月20日，10点20分，星期六原辅助题问与题的关系第16页，共41页，2022年，5月20日，10点20分，星期六例2用两阶段法求解LP问题引入松弛变量和剩余变量，化为等约束第17页，共41页，2022年，5月20日，10点20分，星期六例2用两阶段法求解LP问题引入“人工变量”，第一阶段：第一阶段第18页，共41页，2022年，5月20日，10点20分，星期六第一阶段计算第19页，共41页，2022年，5月20日，10点20分，星期六第一阶段计算第20页，共41页，2022年，5月20日，10点20分，星期六第二阶段计算第21页，共41页，2022年，5月20日，10点20分，星期六3、关于解的判别第22页，共41页，2022年，5月20日，10点20分，星期六3、关于解的判别第23页，共41页，2022年，5月20日，10点20分，星期六步骤框图初始表计算非基变的量检验数无可行解无穷多最优解*基中有人工变量非基变量检验数=0用初等变换换基操作唯一最优解无界解第24页，共41页，2022年，5月20日，10点20分，星期六例3解的判别第25页，共41页，2022年，5月20日，10点20分，星期六例3解的判别有无界解第26页，共41页，2022年，5月20日，10点20分，星期六解的判别无可行解第27页，共41页，2022年，5月20日，10点20分，星期六4、向量矩阵描述第28页，共41页，2022年，5月20日，10点20分，星期六单纯形表中的矩阵向量形式第29页，共41页，2022年，5月20日，10点20分，星期六5、单纯形法小结第30页，共41页，2022年，5月20日，10点20分，星期六5、单纯形法小结第31页，共41页，2022年，5月20日，10点20分，星期六LinDo输入模式model:MAX=3*x1+5*x2+4*x3;2*x1+3*x2<=1500;2*x2+4*x3<=800;3*x1+2*x2+5*x3<=2000;end第32页，共41页，2022年，5月20日，10点20分，星期六注意：目标函数中加等号变量与系数之间用“*”Model:-end可省略第33页，共41页，2022年，5月20日，10点20分，星期六LinGo模式Model:

Sets:Endsets

Data:Enddata

调用函数与计算end!定义集合！定义数据第34页，共41页，2022年，5月20日，10点20分，星期六集合部分model:！开始sets:！定义集合ve/1..3/:c,x;co/1..3/:b;ma(co,ve):a;endsets！注：集表达式：名称/成员/：属性名称（初始集）：属性第35页，共41页，2022年，5月20日，10点20分，星期六定义数据data:！定义数据c=354;ba=230024325;Enddata！注：数据的大小与集合定义中一致，分量中间用空格或逗号分开，数据结束后用分号；第36页，共41页，2022年，5月20日，10点20分，星期六调用函数max=@sum(ve(j):c(j)*x(j));@for(co(i):@sum(ve(j):a(i,j)*x(j))<=b(i));主要函数：@for(set(set_index_list)|condition:expression)@sum(set(set_index_list)|condition:expression)@min(max)(set(set_index_list)|condition:expression)第37页，共41页，2022年，5月20日，10点20分，星期六结果Globaloptimalsolutionfoundatiteration:3Objectivevalue:2675.000VariableValueReducedCostC(1)3.0000000.000000C(2)5.0000000.000000C(3)4.0000000.000000X(1)375.00000.000000X(2)250.00000.000000X(3)75.000000.000000第38页，共41页，2022年，5月20日，10点20分，星期六B(1)1500.0000.000000B(2)800.00000.000000B(3)2000.0000.000000A(1,1)2.0000000.000000A(1,2)3.0000000.000000A(1,3)0.0000000.000000A(2,1)0.0000000.000000A(2,2)2.0000000.000000A(2,3)4.0000000.000000A(3,1)3.0000000.000000A(3,2)2.0000000.000000A(3,3)5.0000000.000000第39页，共41页，2022年，5月20日，10点20分，星期六RowSlackorSurplusDualPrice12675.000