第四章--线性规划进一步讨论.ppt
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四 线性规划 进一步 讨论
- 资源描述:
-
单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第四章,线性规划进一步讨论,4.1,目标规划,4.2,运输问题,4.1,目标规划基本概念,(,1,)偏差变量,d,+,:正偏差变量,表示决策值超出目标值的部分,d,-,:负偏差变量,表示决策值未达到目标值的部分,按定义有:,d,+,0,,,d,-,0,,,d,+,d,-,=0,(,2,),绝对约束和目标约束,绝对约束(硬约束):必须严格满足的约束条件,目标约束(软约束):目标规划特有,(,3,)优先因子(,P,),和权系数(,W,),优先因子用,P,1,,,P,2,,,,,P,l,表示,规定,P,l,P,l+1,,表示,P,l,比,P,l+1,有更大的优先权。,(,4,),目标函数,决策值,=,目标值,min f(d,+,+d,-,),决策值,目标值,min f(d,-,),4.1.2,目标规划模型的建立,例,4.1,某企业计划生产甲、乙两种产品。已知有关数据见表,4-1,。问如何安排生产使获得的总利润最大?,项 目,甲,乙,拥有量,原材料,(,kg,),2,1,11,设备,(,台时,),1,2,10,利 润(元,/,件),8,10,表,4-1,设,x,1,、,x,2,分别表示计划生产产品甲、乙的产量,它的数学模型为:,它的最优解为,x,1,=4,,,x,2,=3,,最大目标函数值为,62,。,max z=8x,1,+10 x,2,2x,1,+x,2,11,st.x,1,+2x,2,10,x,1,x,2,0,但企业的经营目标不仅是利润,企业还考虑了以下问题:,(,1,)根据市场信息,产品甲开始出现滞销现象,故考虑产品甲的产量应不超过产品乙;,(,2,)超过计划供应的原材料需高价采购,应避免过量消耗;,(,3,)应尽可能充分利用设备台时,但不希望加班;,(,4,)应尽可能达到并超过计划利润指标,56,元。,例,4.2,例,4.1,的决策者经过综合考虑,决策者的目标分别为:首先原材料使用限额不能突破;其次产品甲的产量不大于产品乙;再次充分利用设备台时,不希望加班;最后利润额不少于,56,元。问应如何安排生产?,解:原材料使用限额的约束是绝对约束,其他三个约束是属于目标约束,分别赋予这三个目标的优先因子为,P,1,,,P,2,,,P,3,。这问题的数学模型为:,2x,1,+x,2,11,x,1,-x,2,+d,1,-,-d,1,+,=0,x,1,+2x,2,+d,2,-,-d,2,+,=10,8x,1,+10 x,2,+d,3,-,-d,3,+,=56,x,1,x,2,d,i,-,d,i,+,0 i=1,2,3,min P,1,d,1,+,P,2,(d,2,-,+,d,2,+,),P,3,d,3,-,s.t,.,目标规划模型的一般形式:,Min,P,l,(,(,w,lk,-,d,k,-,+,w,lk,+,d,k,+,),l=1,2,L,k=1,K,c,kj,x,j,+,d,k,-,-,d,k,+,=,g,k,,,k,=1,,,2,,,,,K,j=1,n,a,ij,x,j,(,=,,),b,i,,,i,=1,,,2,,,,,m,j=1,n,x,j,0,j,=1,,,2,,,,,n,d,k,-,,,d,k,+,0,k,=1,,,2,,,,,K,S.t.,6,x,1,x,2,0,d,1,+,B,d,2,+,A,d,3,-,4.1.3,目标规划的图解法,2x,1,+x,2,11,x,1,-x,2,+d,1,-,-d,1,+,=0,x,1,+2x,2,+d,2,-,-d,2,+,=10,8x,1,+10 x,2,+d,3,-,-d,3,+,=56,x,1,x,2,d,i,-,d,i,+,0 i=1,2,3,min P,1,d,1,+,P,2,(d,2,-,+,d,2,+,),P,3,d,3,-,s.t,.,G,E,D,C,d,2,-,所以满意域为线段,GD,A,B,C,D,E,F,d,1,-,d,2,+,x,1,+x,2,+d,1,-,-d,1,+,=40,st.x,1,+x,2,+d,2,-,-d,2,+,=50,x,1,+d,3,-,-d,3,+,=24,x,2,+d,4,-,-d,4,+,=30,x,1,x,2,d,i,-,d,i,+,0 i=1,2,3,4,min P,1,d,1,-,P,2,d,2,+,P,3,d,3,-,P,4,d,4,-,x,1,=24,x,2,=26,为满意解,d,3,-,d,4,-,4.1.4,解目标规划的单纯形法,目标规划可以用单纯形法求解。,检验数是各优先因子的线性组合,其正负首先决定于,P,1,的系数的正负。若为正,此时检验数的正负就决定于,P,2,的系数的正负,依此类推。,目标规划问题以检验数非负作为最优准则。,例,4.4,试用单纯形法求解例,4.2,。,解:首先将此目标规划模型化为线性规划标准形式:,2x,1,+x,2,+x,3,=11,x,1,-x,2,+d,1,-,-d,1,+,=0,x,1,+2x,2,+d,2,-,-d,2,+,=10,8x,1,+10 x,2,+d,3,-,-d,3,+,=56,x,1,x,2,x,3,d,i,-,d,i,+,0 i=1,2,3,min P,1,d,1,+,P,2,(d,2,-,+,d,2,+,),P,3,d,3,-,s.t,.,取,x,3,、,d,1,-,、,d,2,-,、,d,3,-,为初始基变量,列初始单纯形表,4-2,c,j,0,0,0,0,P,1,P,2,P,2,P,3,0,C,B,X,B,b,x,1,x,2,x,3,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,0,x,3,11,2,1,1,0,0,0,0,0,0,0,d,1,-,0,1,-1,0,1,-1,0,0,0,0,P,2,d,2,-,10,1,2,0,0,0,1,-1,0,0,P,3,d,3,-,56,8,10,0,0,0,0,0,1,-1,c,j,-z,j,P,1,0,0,0,0,1,0,0,0,0,P,2,-1,-2,0,0,0,0,2,0,0,P,3,-8,-10,0,0,0,0,0,0,1,因为,x,2,的检验数,0,且最小,,故确定,x,2,为换入变量,继续迭代,得,单纯形表,4-3,c,j,0,0,0,0,P,1,P,2,P,2,P,3,0,C,B,X,B,b,x,1,x,2,x,3,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,0,x,3,6,3/2,0,1,0,0,-1/2,1/2,0,0,0,d,1,-,5,3/2,0,0,1,-1,1/2,-1/2,0,0,0,x,2,5,1/2,1,0,0,0,1/2,-1/2,0,0,P,3,d,3,-,6,3,0,0,0,0,-5,5,1,-1,c,j,-z,j,P,1,0,0,0,0,1,0,0,0,0,P,2,0,0,0,0,0,1,1,0,0,P,3,-3,0,0,0,0,5,-5,0,1,因为,x,1,的检验数,0,且最小,,故确定,x,1,为换入变量,继续迭代,得,单纯形表,4-4,c,j,0,0,0,0,P,1,P,2,P,2,P,3,0,C,B,X,B,b,x,1,x,2,x,3,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,0,x,3,3,0,0,1,0,0,2,-2,-1/2,1/2,0,d,1,-,2,0,0,0,1,-1,3,-3,-1/2,1/2,0,x,2,4,0,1,0,0,0,4/3,-4/3,-1/6,1/6,0,x,1,2,1,0,0,0,0,-5/3,5/3,1/3,-1/3,c,j,-z,j,P,1,0,0,0,0,1,0,0,0,0,P,2,0,0,0,0,0,1,1,0,0,P,3,0,0,0,0,0,0,0,1,0,因为所有检验数,0,,所以得到满意解,x,1,=2,x,2,=4,。又因,非基变量,d,3,+,的检验数为,0,,故知例,4.2,有多重解,以,d,3,+,为换入变量,,d,1,-,为换出变量,经迭代得表,4-5,c,j,0,0,0,0,P,1,P,2,P,2,P,3,0,C,B,X,B,b,x,1,x,2,x,3,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,0,x,3,1,0,0,1,-1,1,-1,1,0,0,0,d,3,+,4,0,0,0,2,-2,6,-6,-1,1,0,x,2,10/3,0,1,0,-1/3,1/3,1/3,-1/3,0,0,0,x,1,10/3,1,0,0,2/3,-,2/3,1/3,-1/3,0,0,c,j,-z,j,P,1,0,0,0,0,1,0,0,0,0,P,2,0,0,0,0,0,1,1,0,0,P,3,0,0,0,0,0,0,0,1,0,所以得到另一个满意解,x,1,=10/3,x,2,=10/3,,此解相当于图,4-1,中点,D,。,G,、,D,两点的凸线性组合都是例,4.2,的满意解。,10,a,2,=4,a,3,=9,b,1,=3,b,2,=6,b,3,=5,b,4,=6,a,1,=7,总产 量,供应地,运价,总销量,需求地,A,2,A,3,B,2,A,1,B,3,B,4,B,1,3,11,3,10,1,9,2,8,7,4,5,当总产量,=,总销量,称为产销平衡问题 当总产量总销量,称为产销不平衡问题,4.2,运输问题,产销平衡的运输问题的数学模型如下,运输问题含有,m,n,个变量,,m+n,个约束方程。其系数矩阵的结构比较特殊,对应变量,x,ij,的系数向量,其分量中除第,i,个和第,m+j,个为,1,以外,其余的都为零,模型中只有个相互独立的约束方程。因此,运输问题的任一基可行解都有,m+n-1,个基变量,。,4.2.3,运输问题的表上作业法,1,、给出运输问题的初始基可行解(初始调运方案),1,)最小元素法,3,1,4,6,3,3,2),沃格尔法,列罚数,行罚数,2,5,1,3,0,1,1,6,2,1,3,0,1,2,3,2,1,2,1,2,0,1,7,6,3,5,2,0,0,1,2,6,3,1,4,3,3,1,11,=,c,11,-c,13,+c,23,-c,21,=3-3+2-1=1,2,、解的最优性检验,1),闭回路法,1,2,6,3,3,4,1,3,12,=,c,12,-c,14,+c,34,-c,34,=11-10+5-4=2,6,3,3,4,1,3,1,2,1,22,=,c,22,-c,23,+c,13,-c,14,+c,34,-c,34,=9-2+3 10+5-4=1,6,3,3,4,1,3,1,2,1,-1,24,=,c,24,-c,23,+c,13,-c,14,=8-2+3-10=-1,6,3,3,4,1,3,1,2,1,-1,10,31,=,c,31,-c,21,+c,23,-c,13,+c,14,-c,34,=7-1+2 3+10-5=10,6,3,3,4,1,3,1,2,1,-1,10,12,33,=,c,33,-c,13,+c,14,-c,34,=10-3+10-5=12,1,2,1,-1,10,12,因为,24,=-1,总销量,假想一销地,B,n+1,,,令销量为,运价,c=0,总产量,总销量,A,A,A,销量,B,1,B,2,B,3,3,12,3,1,11,2,5,2,6,7,1,3,4,3,5,B,4,4,9,5,6,产量,8,5,9,B,5,0,0,0,4,4,3,5,4,2,2,2,2),总产量,总销量,假想一产地,A,m+1,,令,产量为 ,运价,c=0,2.,带弹性需求的产销不平衡运输问题,需求地,化肥厂,B,1,B,2,B,3,B,4,产量,A,1,16,13,22,17,50,A,2,14,13,19,15,60,A,3,19,20,23,50,最低需求,最高需求,30,50,70,70,0,30,10,不限,B,1,B,1,B,2,B,3,B,4,B,4,产量,A,1,16,16,13,22,17,17,50,A,2,14,14,13,19,15,15,60,A,3,19,19,20,23,M,M,50,A,4,M,0,M,0,M,0,50,需求量,30,20,70,30,10,50,210,50,20,0,30,20,30,10,30,20,展开阅读全文

咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。
咨信网小贴示:
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】


第四章--线性规划进一步讨论.ppt
















自信AI助手














微信客服
客服QQ
发送邮件
意见反馈



链接地址:https://www.zixin.com.cn/doc/14770840.html