运筹学单纯形计算精选课件.ppt
第第1页页第一页，本课件共有41页第第2页页1 1、初始单纯形表、初始单纯形表第二页，本课件共有41页第第3页页2 2、换基操作、换基操作第三页，本课件共有41页第第4页页例例例例1 1 用单纯形法解用单纯形法解用单纯形法解用单纯形法解 LPLP第四页，本课件共有41页第第5页页单纯形表迭代单纯形表迭代进进2出出5进进1出出3第五页，本课件共有41页第第6页页第六页，本课件共有41页第第7页页线性规划及单纯型法线性规划及单纯型法 单纯形法进一步讨论 第五节第七页，本课件共有41页第第8页页1、人工变量法（大、人工变量法（大M法）法）第八页，本课件共有41页第第9页页例例例例1 1 用大用大用大用大MM法求解法求解法求解法求解LPLP问题问题问题问题引入松弛变量和剩余变量引入松弛变量和剩余变量引入松弛变量和剩余变量引入松弛变量和剩余变量第九页，本课件共有41页第第10页页例例例例1 1 用大用大用大用大MM法求解法求解法求解法求解LPLP问题问题问题问题再引入再引入再引入再引入“人工变量人工变量人工变量人工变量”，构造初始表：，构造初始表：，构造初始表：，构造初始表：人工变量人工变量第十页，本课件共有41页第第11页页用单纯形表迭代用单纯形表迭代第十一页，本课件共有41页第第12页页用单纯形表迭代用单纯形表迭代第十二页，本课件共有41页第第13页页求求 辅辅 助助 问问 题题 的的 三三 种种 情情 况况第十三页，本课件共有41页第第14页页2、两、两 阶段法阶段法|基本思想基本思想 第一阶段第一阶段 求解目标函数只有人工变量的辅助问题求解目标函数只有人工变量的辅助问题 得到原问题的初始基可行解。得到原问题的初始基可行解。第二阶段第二阶段 利用初始基可行解求原问题的最优解利用初始基可行解求原问题的最优解第十四页，本课件共有41页第第15页页第十五页，本课件共有41页第第16页页原原 辅辅 助助 题题 问问 与与 题题 的的 关关 系系第十六页，本课件共有41页第第17页页例例例例2 2 用两阶段法求解用两阶段法求解用两阶段法求解用两阶段法求解LPLP问题问题问题问题引入松弛变量和剩余变量，化为等约束引入松弛变量和剩余变量，化为等约束引入松弛变量和剩余变量，化为等约束引入松弛变量和剩余变量，化为等约束第十七页，本课件共有41页第第18页页例例例例2 2 用两阶段法求解用两阶段法求解用两阶段法求解用两阶段法求解LPLP问题问题问题问题引入引入引入引入“人工变量人工变量人工变量人工变量”，第一阶段：，第一阶段：，第一阶段：，第一阶段：第一阶段第一阶段第十八页，本课件共有41页第第19页页第一阶段计算第一阶段计算第十九页，本课件共有41页第第20页页第一阶段计算第一阶段计算第二十页，本课件共有41页第第21页页第二阶段计算第二阶段计算第二十一页，本课件共有41页第第22页页3、关于解的判别、关于解的判别第二十二页，本课件共有41页第第23页页3、关于解的判别、关于解的判别第二十三页，本课件共有41页第第24页页步骤框图步骤框图初始表初始表计算非基变计算非基变的量检验数的量检验数无可行解无可行解无穷多最优解无穷多最优解*基中有基中有人工变量人工变量非基变量非基变量检验数检验数=0用初等变换用初等变换换基操作换基操作唯一最优解唯一最优解无界解无界解第二十四页，本课件共有41页第第25页页例例3 3 解的判别解的判别第二十五页，本课件共有41页第第26页页例例3 3 解的判别解的判别有无界解有无界解第二十六页，本课件共有41页第第27页页解的判别解的判别无可行解无可行解第二十七页，本课件共有41页第第28页页4 4、向量矩阵描述、向量矩阵描述第二十八页，本课件共有41页第第29页页单纯形表中的矩阵向量形式单纯形表中的矩阵向量形式第二十九页，本课件共有41页第第30页页5 5、单纯形法小结、单纯形法小结第三十页，本课件共有41页第第31页页5 5、单纯形法小结、单纯形法小结第三十一页，本课件共有41页第第32页页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第三十二页，本课件共有41页第第33页页注意：注意：|目标函数中加等号目标函数中加等号|变量与系数之间用变量与系数之间用“*”|Model:-end可省略可省略第三十三页，本课件共有41页第第34页页LinGo 模式模式Model:Sets:Endsets Data:Enddata 调用函数与计算 end!定义集合！定义数据第三十四页，本课件共有41页第第35页页集集 合合 部部 分分model:！开始开始sets:！定义集合定义集合ve/1.3/:c,x;co/1.3/:b;ma(co,ve):a;endsets！注：集表达式：名称！注：集表达式：名称/成员成员/：属性：属性 名称（初始集）：属性名称（初始集）：属性第三十五页，本课件共有41页第第36页页定定 义义 数数 据据data:！定义数据定义数据c=3 5 4;b=1500 800 2000;a=2 3 0 0 2 4 3 2 5;Enddata！注：数据的大小与集合定义中一致，分注：数据的大小与集合定义中一致，分量中间用空格或逗号分开，数据结束后量中间用空格或逗号分开，数据结束后用分号；用分号；第三十六页，本课件共有41页第第37页页调调 用用 函函 数数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)第三十七页，本课件共有41页第第38页页结结 果果Global optimal solution found at iteration:3Objective value:2675.000Variable Value Reduced CostC(1)3.000000 0.000000C(2)5.000000 0.000000C(3)4.000000 0.000000X(1)375.0000 0.000000X(2)250.0000 0.000000X(3)75.00000 0.000000第三十八页，本课件共有41页第第39页页B(1)1500.000 0.000000B(2)800.0000 0.000000B(3)2000.000 0.000000A(1,1)2.000000 0.000000A(1,2)3.000000 0.000000A(1,3)0.000000 0.000000A(2,1)0.000000 0.000000A(2,2)2.000000 0.000000A(2,3)4.000000 0.000000A(3,1)3.000000 0.000000A(3,2)2.000000 0.000000A(3,3)5.000000 0.000000第三十九页，本课件共有41页第第40页页Row Slack or Surplus Dual Price1 2675.000 1.0000002 0.000000 1.0500003 0.000000 0.62500004 0.000000 0.3000000第四十页，本课件共有41页第第41页页感感谢谢大大家家观观看看第四十一页，本课件共有41页
