线性规划案例课件.ppt-淘文阁

资源描述

《线性规划案例课件.ppt》由会员分享，可在线阅读，更多相关《线性规划案例课件.ppt（146页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

2、转换概念概念第第4页页某工厂用三种原料生产三种产品，已知的条件如表某工厂用三种原料生产三种产品，已知的条件如表某工厂用三种原料生产三种产品，已知的条件如表某工厂用三种原料生产三种产品，已知的条件如表2.1.12.1.1所示，试制订总利润最大的生产计划所示，试制订总利润最大的生产计划所示，试制订总利润最大的生产计划所示，试制订总利润最大的生产计划单位产品所需原单位产品所需原料数量（公斤）料数量（公斤）产品产品Q1产品产品Q2产品产品Q3原料可用量原料可用量（公斤（公斤/日）日）原料原料P12301500原料原料P2024800原料原料P33252000单位产品的利润单位产品的利润（千元）（千元

3、）354生生产产计计划划问问题题第第5页页问问题题分分析析第第6页页模模型型第第7页页计计算算结结果果第第8页页运运运运输输输输问问问问题题题题第第9页页问问题题分分析析第第10页页模模型型第第11页页一一般般形形式式目标函数目标函数约束条件约束条件第第12页页注注释释第第13页页规规范范形形式式第第14页页标标准准形形式式第第15页页概概念念第第16页页模模型型转转换换v约束转换约束转换v实例实例v目标转换目标转换v变量转换变量转换第第17页页约约束束转转换换v不等式变等式不等式变等式v不等式变不等式不等式变不等式v等式变不等式等式变不等式第第18页页不不等等式式变变等等式式

6、第第39页页定理定理2.3.1第第40页页定定理理2.3.2第第41页页定定理理2.3.3第第42页页算算法法步步骤骤第第43页页单单纯纯形形表表第第44页页第第45页页第第46页页第第47页页算算例例第第48页页初初始始单单纯纯形形表表第第49页页迭迭代代1第第50页页迭迭代代2第第51页页第第52页页初初始始解解|两阶段法两阶段法|大大M法法|说明说明第第53页页两两阶阶段段法法|基本思想基本思想第一阶段第一阶段：通过求解辅助问题的最优基可行通过求解辅助问题的最优基可行解得到原问题的初始基可行解。解得到原问题的初始基可行解。第二阶段第二阶段：求原问题的最优解求原问题的最优解|算例算例第第5

7、4页页辅辅助助问问题题第第55页页原原辅辅助助题题问问与与题题的的关关系系第第56页页求求辅辅助助问问题题的的三三种种情情况况第第57页页算算例例第第58页页第第1阶阶段段第第59页页第第1阶阶段段第第60页页第第1阶阶段段第第61页页第第1阶阶段段第第62页页第第1阶阶段段第第63页页第第2阶阶段段第第64页页大大M法法第第65页页说说明明第第66页页对对偶偶理理论论|对偶规划对偶规划|对偶理论对偶理论|对偶单纯形算法对偶单纯形算法第第67页页对对偶偶规规划划|标准形式线性规划的对偶规划标准形式线性规划的对偶规划|规范形式线性规划的对偶规划规范形式线性规划的对偶规划|一般形式线性规划的对偶规

8、划一般形式线性规划的对偶规划|实例实例第第68页页标准形式的对偶规划标准形式的对偶规划第第69页页第第70页页规规范范形形式式的的对对偶偶规规划划第第71页页一般形式的对偶规划一般形式的对偶规划第第72页页实实例例第第73页页对对偶偶理理论论第第74页页定定理理2.5.1第第75页页定定理理2.5.2第第76页页定定理理2.5.5第第77页页对偶单纯形算法对偶单纯形算法|基本思想基本思想|算法过程算法过程|算例算例第第78页页基基本本思思想想第第79页页单单纯纯形形算算法法第第80页页对对偶偶单单纯纯形形第第81页页正正则则解解正则解正则解对偶可行解对偶可行解第第82页页正则解的单纯性表正则解

9、的单纯性表第第83页页规划无可行解规划无可行解保持正则性保持正则性第第84页页入基变量入基变量第第85页页第第86页页否否算算法法过过程程初始正则解初始正则解检查可行检查可行是则停止是则停止得最优解得最优解选出基变量选出基变量检查检查是否无可是否无可行解行解是则停止是则停止否否无最优解无最优解选入基变量选入基变量计算典式检验数计算典式检验数第第87页页算算例例第第88页页迭迭代代第第89页页迭迭代代第第90页页迭迭代代第第91页页第第92页页第第93页页灵灵敏敏度度分分析析|概况概况|改变价值向量改变价值向量|改变右端向量改变右端向量第第94页页概概况况|信息的不确定性信息的不确定性信息的变化

10、：信息的变化：价值向量价值向量市市场变化场变化右端向量右端向量资源变化资源变化系数矩阵系数矩阵技术进步技术进步认知的误差认知的误差|分析方法分析方法静态分析静态分析-比较静态分析比较静态分析-动态分析动态分析第第95页页改变价值向量改变价值向量v一般改变情况一般改变情况v改变非基变量的价值向量改变非基变量的价值向量v改变基变量的价值向量改变基变量的价值向量v算例算例第第96页页一一般般改改变变第第97页页非非基基变变量量第第98页页基基变变量量第第99页页算算例例第第100页页第第101页页改变右端向量改变右端向量基本思想基本思想算例算例第第102页页基基本本思思想想第第103页页第第104页

12、数与边量之间加空格系数与边量之间加空格|不等号为不等号为:=(=(),=,=与与等同等同|变量非负约束可省略变量非负约束可省略|结束时以结束时以end标示标示第第110页页结结果果LPOPTIMUMFOUNDATSTEP3OBJECTIVEFUNCTIONVALUE1)2675.000VARIABLEVALUEREDUCEDCOSTX1375.0000000.000000X2250.0000000.000000X375.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.0000001.0500003)0.0000000.6250004)0.0000000

13、.300000第第111页页LinGo|输入模型输入模型LinDo模式模式LinGo模式模式|求解求解点击求解按钮点击求解按钮即可即可|结果结果第第112页页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第第113页页注意与注意与LinDo的区别的区别|目标函数中加等号目标函数中加等号|变量与系数之间用变量与系数之间用“*”|Model:-end可省略可省略第第114页页LinGo模式模式Model:Sets:EndsetsData:Enddata调用函数与计算

14、end!定义集合！定义数据第第115页页集集合合部部分分model:！开始开始sets:！定义集合定义集合ve/1.3/:c,x;co/1.3/:b;ma(co,ve):a;endsets！注：集表达式：名称！注：集表达式：名称/成员成员/：属性：属性名称（初始集）：属性名称（初始集）：属性第第116页页定定义义数数据据data:！定义数据定义数据c=3 5 4;b=1500 800 2000;a=2 3 0 0 2 4 3 2 5;Enddata！注：数据的大小与集合定义中一致，注：数据的大小与集合定义中一致，分量中间用空格或逗号分开，数据分量中间用空格或逗号分开，数据结束后用分号；结束后用

15、分号；第第117页页调调用用函函数数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)第第118页页结结果果Global optimal solution found at iteration:3Objective value

16、: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第第119页页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.00000

17、0A(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第第120页页Row Slack or Surplus Dual Price1 2675.000 1.0000002 0.000000 1.0500003 0.000000 0.62500004 0.000000 0.3000000第第121页页Scilab函数函数命令命令1：x,lagr,f=linpro(p,C,b,

18、x0)命令命令2：x,lagr,f=linpro(p,C,b,ci,cs,x0)命令命令3：x,lagr,f=linpro(p,C,b,ci,cs,me,x0)命令命令4：x,lagr,f=linpro(p,C,b,ci,cs,me,x0,imp)命令命令5：x1,crit=karmarkar(a,b,c,x0)注意事项注意事项第第122页页命令命令1v问题形式问题形式minp*xs.t.C*x=bx,lagr,f=linpro(p,C,b,x0）第第123页页命命令令2x,lagr,f=linpro(p,C,b,ci,cs,x0)|问题形式问题形式minp*xs.t.C*x=bci=x=cs

19、第第124页页命命令令3x,lagr,f=linpro(p,C,b,ci,cs,me,x0)|问题问题minp*xs.t.C(j,:)x=b(j),j=1,.,meC(j,:)x=b(j),j=me+1,.,me+mdci=x=cs第第125页页命命令令4x,lagr,f=linpro(p,C,b,ci,cs,me,x0,imp)问题形式问题形式minp*xs.t.C(j,:)x=b(j),j=1,.,meC(j,:)x=b(j),j=me+1,.,me+mdci=x=0第第127页页注注意意事事项项|命令命令2和和3中中x0可省略，可省略，但命令但命令4和和5中不可省中不可省略略|向量都是列

20、向量，参向量都是列向量，参数的顺序不可换数的顺序不可换|命令命令3中等式约束必须中等式约束必须在前面在前面第第128页页人力资源分配问题人力资源分配问题某个中型百货商场对售货人员（周工资某个中型百货商场对售货人员（周工资200元）的需求经统计如下表元）的需求经统计如下表为了保证销售人员充分休息，销售人员为了保证销售人员充分休息，销售人员每周工作每周工作5天，休息天，休息2天。问应如何安排天。问应如何安排销售人员的工作时间，使得所配售货人销售人员的工作时间，使得所配售货人员的总费用最小？员的总费用最小？星期星期一一二二三三四四五五六六七七人数人数12151214161819第第129页页模模型型

21、假假设设|每天工作每天工作8小时，不考虑夜班的小时，不考虑夜班的情况；情况；|每个人的休息时间为连续的两天每个人的休息时间为连续的两天时间；时间；|每天安排的人员数不得低于需求每天安排的人员数不得低于需求量，但可以超过需求量量，但可以超过需求量第第130页页问问题题分分析析因素因素：不可变因素：需求量、休息时间、单位：不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的费用；可变因素：安排的人数、每人工作的时间、总费用；时间、总费用；方案方案：确定每天工作的人数，由于连续休息：确定每天工作的人数，由于连续休息2天，天，当确定每个人开始休息的时间就等于知道工当确定每个人开始休

22、息的时间就等于知道工作的时间，因而确定每天开始休息的人数就作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工知道每天开始工作的人数，从而求出每天工作的人数。作的人数。变量变量：每天开始休息的人数：每天开始休息的人数约束条件约束条件：1.每人休息时间每人休息时间2天，自然满足。天，自然满足。2.每天工作人数不低于需求量，第每天工作人数不低于需求量，第i天工作天工作的人数就是从第的人数就是从第i-2天往前数天往前数5天内开始工作天内开始工作的人数，所以有约束：的人数，所以有约束：第第131页页3.变量非负约束：变量非负约束：第第132页页目标函数目标函数：总费用最小，总费

23、用与使总费用最小，总费用与使用的总人数成正比。由于每个人必然在用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等且仅在某一天开始休息，所以总人数等于于第第133页页模模型型第第134页页计计算算第第135页页注注解解|该问题本质上是个整数规划问题，该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数放松的线性规划的最优解是个整数解，所以两规划等价。解，所以两规划等价。|定义整数变量用函数定义整数变量用函数gin(x1)gin(x7);0-1整数变量为整数变量为bin(x1)第第136页页配配料料问问题题某化工厂要用三中原料混合配置某化工厂要用三中原料混合配置三种不同规

24、格的产品各产品的规格三种不同规格的产品各产品的规格单价如表单价如表1，产品产品规格规格单价（元单价（元/公斤）公斤）A原料原料不少于不少于50%原料原料不超过不超过25%50B原料原料不少于不少于25%原料原料不超过不超过50%35C不限不限25第第137页页问如何安排生产使得生产利润最大？问如何安排生产使得生产利润最大？原料原料日最大供应量日最大供应量单价单价(元元/公公斤斤)10065100256035原料的单价与每天最大供应量如表原料的单价与每天最大供应量如表2第第138页页配配料料问问题题案案例例|问题问题|问题分析问题分析|模型模型|求解求解|结果分析结果分析第第139页页问问题题分

25、分析析|变量变量|约束条件约束条件|目标函数目标函数第第140页页变变量量生产计划就是要确定每天生产三种产生产计划就是要确定每天生产三种产品的数量以及非中产品中三中原料的品的数量以及非中产品中三中原料的数量。而由于每种产品的数量等于三数量。而由于每种产品的数量等于三种原料数量之和，所以只要确定每天种原料数量之和，所以只要确定每天生产三种产品分别含有的原料数量即生产三种产品分别含有的原料数量即可。所以变量就是每天生产三种产品可。所以变量就是每天生产三种产品所用的原料数，设用于生产第所用的原料数，设用于生产第i 种产种产品的第品的第j 种原料数为种原料数为第第141页页约约束束条条件件|规格约束规格约束第第142页页|资源约束资源约束约约束束条条件件第第143页页目标函数目标函数总产值总产值总成本总成本总利润总利润=总产值总产值-总成总成本本第第144页页第第145页页模模型型第第146页页求求解解

展开阅读全文