运筹学单纯形计算课件

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

单纯形法进一步讨论

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

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

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

Sets:Endsets

Data:Enddata

调用函数与计算end!定义集合！定义数据第34页，讲稿共41页，2023年5月2日，星期三集合部分model:！开始sets:！定义集合ve/1..3/:c,x;co/1..3/:b;ma(co,ve):a;endsets！注：集表达式：名称/成员/：属性名称（初始集）：属性第35页，讲稿共41页，2023年5月2日，星期三定义数据data:！定义数据c=354;ba=230024325;Enddata！注：数据的大小与集合定义中一致，分量中间用空格或逗号分开，数据结束后用分号；第36页，讲稿共41页，2023年5月2日，星期三调用函数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页，2023年5月2日，星期三结果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页，2023年5月2日，星期三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页，2023年5月2日，星期三RowSlackorSurplusDualPrice12675.000