运筹学单纯形计算.ppt

《运筹学单纯形计算.ppt》由会员分享，可在线阅读，更多相关《运筹学单纯形计算.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1页页现在学习的是第1页，共41页第第2页页1 1、初始单纯形表、初始单纯形表现在学习的是第2页，共41页第第3页页2 2、换基操作、换基操作现在学习的是第3页，共41页第第4页页例例例例1 1 用单纯形法解用单纯形法解用单纯形法解用单纯形法解 LPLP现在学习的是第4页，共41页第第5页页单纯形表迭代单纯形表迭代进进2出出5进进1出出3现在学习的是第5页，共41页第第6页页现在学习的是第6页，共41页第第7页页线性规划及单纯型法线性规划及单纯型法 单纯形法进一步讨论 第五节现在学习的是第7页，共41页第第8页页1、人工变量法（大、人工变量法（大M法）法）现在学习的是第8页，共41页第第9

2、页页例例例例1 1 用大用大用大用大MM法求解法求解法求解法求解LPLP问题问题问题问题引入松弛变量和剩余变量引入松弛变量和剩余变量引入松弛变量和剩余变量引入松弛变量和剩余变量现在学习的是第9页，共41页第第10页页例例例例1 1 用大用大用大用大MM法求解法求解法求解法求解LPLP问题问题问题问题再引入再引入再引入再引入“人工变量人工变量人工变量人工变量”，构造初始表：，构造初始表：，构造初始表：，构造初始表：人工变量人工变量现在学习的是第10页，共41页第第11页页用单纯形表迭代用单纯形表迭代现在学习的是第11页，共41页第第12页页用单纯形表迭代用单纯形表迭代现在学习的是第12页，共41

3、页第第13页页求求 辅辅 助助 问问 题题 的的 三三 种种 情情 况况现在学习的是第13页，共41页第第14页页2、两、两 阶段法阶段法|基本思想基本思想 第一阶段第一阶段 求解目标函数只有人工变量的辅助问题求解目标函数只有人工变量的辅助问题 得到原问题的初始基可行解。得到原问题的初始基可行解。第二阶段第二阶段 利用初始基可行解求原问题的最优解利用初始基可行解求原问题的最优解现在学习的是第14页，共41页第第15页页现在学习的是第15页，共41页第第16页页原原 辅辅 助助 题题 问问 与与 题题 的的 关关 系系现在学习的是第16页，共41页第第17页页例例例例2 2 用两阶段法求解用两阶

4、段法求解用两阶段法求解用两阶段法求解LPLP问题问题问题问题引入松弛变量和剩余变量，化为等约束引入松弛变量和剩余变量，化为等约束引入松弛变量和剩余变量，化为等约束引入松弛变量和剩余变量，化为等约束现在学习的是第17页，共41页第第18页页例例例例2 2 用两阶段法求解用两阶段法求解用两阶段法求解用两阶段法求解LPLP问题问题问题问题引入引入引入引入“人工变量人工变量人工变量人工变量”，第一阶段：，第一阶段：，第一阶段：，第一阶段：第一阶段第一阶段现在学习的是第18页，共41页第第19页页第一阶段计算第一阶段计算现在学习的是第19页，共41页第第20页页第一阶段计算第一阶段计算现在学习的是第20

5、页，共41页第第21页页第二阶段计算第二阶段计算现在学习的是第21页，共41页第第22页页3、关于解的判别、关于解的判别现在学习的是第22页，共41页第第23页页3、关于解的判别、关于解的判别现在学习的是第23页，共41页第第24页页步骤框图步骤框图初始表初始表计算非基变计算非基变的量检验数的量检验数无可行解无可行解无穷多最优解无穷多最优解*基中有基中有人工变量人工变量非基变量非基变量检验数检验数=0用初等变换用初等变换换基操作换基操作唯一最优解唯一最优解无界解无界解现在学习的是第24页，共41页第第25页页例例3 3 解的判别解的判别现在学习的是第25页，共41页第第26页页例例3 3 解的

6、判别解的判别有无界解有无界解现在学习的是第26页，共41页第第27页页解的判别解的判别无可行解无可行解现在学习的是第27页，共41页第第28页页4 4、向量矩阵描述、向量矩阵描述现在学习的是第28页，共41页第第29页页单纯形表中的矩阵向量形式单纯形表中的矩阵向量形式现在学习的是第29页，共41页第第30页页5 5、单纯形法小结、单纯形法小结现在学习的是第30页，共41页第第31页页5 5、单纯形法小结、单纯形法小结现在学习的是第31页，共41页第第32页页LinDo 输输 入入 模模 式式model:MAX=3*x1+5*x2+4*x3;2*x1+3*x2=1500;2*x2+4*x3=80

7、0;3*x1+2*x2+5*x3=2000;end现在学习的是第32页，共41页第第33页页注意：注意：|目标函数中加等号目标函数中加等号|变量与系数之间用变量与系数之间用“*”|Model:-end可省略可省略现在学习的是第33页，共41页第第34页页LinGo 模式模式Model:Sets:Endsets Data:Enddata 调用函数与计算 end!定义集合！定义数据现在学习的是第34页，共41页第第35页页集集 合合 部部 分分model:！开始开始sets:！定义集合定义集合ve/1.3/:c,x;co/1.3/:b;ma(co,ve):a;endsets！注：集表达式：名称！注

8、：集表达式：名称/成员成员/：属性：属性 名称（初始集）：属性名称（初始集）：属性现在学习的是第35页，共41页第第36页页定定 义义 数数 据据data:！定义数据定义数据c=3 5 4;b=1500 800 2000;a=2 3 0 0 2 4 3 2 5;Enddata！注：数据的大小与集合定义中一致，分量注：数据的大小与集合定义中一致，分量中间用空格或逗号分开，数据结束后用分中间用空格或逗号分开，数据结束后用分号；号；现在学习的是第36页，共41页第第37页页调调 用用 函函 数数max=sum(ve(j):c(j)*x(j);for(co(i):sum(ve(j):a(i,j)*x(

9、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页第第38页页结结 果果Global optimal solution found at iteration:3Objective value:2675.000Variable Value Reduced CostC(1)3.000000 0.00000

10、0C(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现在学习的是第38页，共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现在学习的是第39页，共41页第第40页页Row Slack or Surplus Dual Price1 2675.000 1.0000002 0.000000 1.0500003 0.000000 0.62500004 0.000000 0.3000000现在学习的是第40页，共41页第第41页页感感谢谢大大家家观观看看现在学习的是第41页，共41页