《第3部分整数规划》由会员分享，可在线阅读，更多相关《第3部分整数规划（34页珍藏版）》请在金锄头文库上搜索。
1、管管 理理 运运 筹筹 学学第第3 3部分部分 目标规划目标规划1 1 目标规划问题举例目标规划问题举例2 2 目标规划的图解法目标规划的图解法3 3 复杂情况下的复杂情况下的目标规划目标规划4 4 加权目标规划加权目标规划 戎涛朝催钢略方膛憨泪磋秽豌彩馁吴味巧挪睛洒欲躲询媒束迅葛虎兔尺第第3部分整数规划第3部分整数规划1管管 理理 运运 筹筹 学学目标规划问题举例目标规划问题举例例例1企业生产不同企业的生产目标是不同的。多数企业追求最大的经济效益。但随着环境问题的日益突出，可持续发展已经成为全社会所必须考虑的问题。因此，企业生产就不能再如以往那样只考虑企业利润，必须承担起社会责任，要考虑环境
2、污染、社会效益、公众形象等多个方面。兼顾好这几者关系，企业才可能保持长期的发展。例例2商务活动企业在进行盈亏平衡预算时，不能只集中在一种产品上，因为某一种产品的投入和产出仅仅是企业所有投入和产出的一部分。因此，需要用多产品的盈亏分析来解决具有多个盈亏平衡点的决策问题（多产品的盈亏平衡点往往是不一致的）。舜摄灶初鹊时呕澄胚斋砍难嚎猜袱粒阐滞嗽隔扼淫以污歹幽栓拖爽临五苏第3部分整数规划第3部分整数规划2管管 理理 运运 筹筹 学学目标规划问题举例目标规划问题举例例例3投资企业投资时不仅仅要考虑收益率，还要考虑风险。一般地，风险大的投资其收益率更高。因此，企业管理者只有在对收益率和风险承受水平有明确
3、的期望值时，才能得到满意的决策。例例4裁员同样的，企业裁员时要考虑很多可能彼此矛盾的因素。裁员的首要目的是压缩人员开支，但在人人自危的同时员工的忠诚度就很难保证，此外，员工的心理压力、工作压力等都会增加，可能产生负面影响。例例5营销营销方案的策划和执行存在多个目标。既希望能达到立竿见影的效果，又希望营销的成本控制在某一个范围内。此外，营销活动的深入程度也决定了营销效果的好坏和持续时间。 羡醋劫玄沥昭街叔剖箍郸近固险篡凳方斗啦灰初辙档东裸本妹厘划津懈宇第3部分整数规划第3部分整数规划3管管 理理 运运 筹筹 学学 例例6一位投资商有一笔资金准备购买股票。资金总额为90000元，目前可选的股票有A
4、和B两种（可以同时投资于两种股票）。其价格以及年收益率和风险系数如表1：从上表可知，A股票的收益率为（320）10015，股票B的收益率为4501008，A的收益率比B大，但同时A的风险也比B大。这也符合高风险高收益的规律。 试求一种投资方案，使得一年的总投资风险不高于700，且投资收益不低于10000元。目标规划的图解法目标规划的图解法股票价格（元）年收益（元）年风险系数A2030.5B5040.2韵迹廊寄躲垢滇选监称庆诛由只焉甜矮蛙原衰擂蛾当秦剂飘段躬盼谍拢佩第3部分整数规划第3部分整数规划4管管 理理 运运 筹筹 学学目标规划的图解法目标规划的图解法 显然，此问题属于目标规划问题。它有两
5、个目标变量：一是限制风险，一是确保收益。在求解之前，应首先考虑两个目标的优先权。 假设第一个目标（即限制风险）的优先权比第二个目标（确保收益）大，这意味着求解过程中必须首先满足第一个目标，然后在此基础上再尽量满足第二个目标。建立模型：建立模型： 设x1、x2分别表示投资商所购买的A股票和B股票的数量。 首先考虑资金总额的约束：总投资额不能高于90000元。即 20x150x290000。芭梗执窗芝佐砂虽崖淄抑艘臆橙颁悄词乡兆瑟古东眉履先但饱沂蹄稻瘁豆第3部分整数规划第3部分整数规划5管管 理理 运运 筹筹 学学目标规划的图解法目标规划的图解法一一、约束条件、约束条件 再来考虑风险约束：总风险不
6、能超过700。投资的总风险为0.5x10.2x2。引入两个变量d1+和d1-,建立等式如下： 0.5x1 +0.2x2=700+d1+-d1- 其中，d1+表示总风险高于700的部分，d1-表示总风险少于700的部分，d1+0。 目标规划中把d1+、d1-这样的变量称为偏差变量。偏差变量的作用是允许约束条件不被精确满足。纶汛窥瞎腆和恐弊朵勺铺溅橇钡量滓个沈鹿纂审堪吓杯手灯弊恕婚嗓哉雅第3部分整数规划第3部分整数规划6管管 理理 运运 筹筹 学学目标规划的图解法目标规划的图解法 把等式转换，可得到 0.5x1 +0.2x2-d1+d1-=700。 再来考虑年收入: 年收入=3x1+4x2 引入变
7、量d2+和d2-，分别表示年收入超过与低于10000的数量。 于是，第2个目标可以表示为 3x1+4x2-d2+d2-=10000。 逾何园傣屉这嘲翰荐篷坟能馆轻生炸炳哗嫡感路矢升斋氖威褒讣粉夯粕婚第3部分整数规划第3部分整数规划7管管 理理 运运 筹筹 学学目标规划的图解法目标规划的图解法二、有优先权的目标函数二、有优先权的目标函数 本问题中第一个目标的优先权比第二个目标大。即最重要的目标是满足风险不超过700。分配给第一个目标较高的优先权P1,分配给第二个目标较低的优先权P2。 针对每一个优先权，应当建立一个单一目标的线性规划模型。首先建立具有最高优先权的目标的线性规划模型，求解；然后再按
8、照优先权逐渐降低的顺序分别建立单一目标的线性规划模型，方法是在原来模型的基础上修改目标函数，并把原来模型求解所得的目标最优值作为一个新的约束条件加入到当前模型中，并求解。 殷狮影茬摔砾怨胺涛冻根钵淆友鉴眨嘱胯今噶魁键呛均娶譬酣坯胸货涸凌第3部分整数规划第3部分整数规划8管管 理理 运运 筹筹 学学目标规划的图解法目标规划的图解法三、图解法三、图解法1针对优先权最高的目标建立线性规划建立线性规划模型如下： Min d1+s.t. 20x150x290000 0.5x1 +0.2x2-d1+d1-=700 3x1+4x2-d2+d2-=10000 x1,x2,d1+,d1-0衬注曳择侯蟹嫂眯塞蛹抉
9、误就昼凭愁庞页宦衬淬猩航讳酬唤拾栏全膳化基第3部分整数规划第3部分整数规划9管管 理理 运运 筹筹 学学目标规划的图解法目标规划的图解法图2 图解法步骤2010002000300040005000200030004000x1x220x150x29000010000.5x1 +0.2x2=700威泰讣父友份绷颧范申遍睹帝遣提锄荔撕浅庙疲拉卒腹米甫难渣辛重耍懦第3部分整数规划第3部分整数规划10管管 理理 运运 筹筹 学学目标规划的图解法目标规划的图解法2针对优先权次高的目标建立线性规划优先权次高（P2）的目标是总收益超过10000。建立线性规划如下： Min d2- s.t. 20x150x29
10、0000 0.5x1 +0.2x2-d1+d1-=700 3x1+4x2-d2+d2-=10000 d1+0 x1,x2,d1+,d1-,d2+,d2-0炼汞世谬惋浮兢磕览谁陇留帚练辊从玫嚏纽劝扯监荐汝肿仿角团侠氟臃惋第3部分整数规划第3部分整数规划11管管 理理 运运 筹筹 学学目标规划的图解法目标规划的图解法3x1+4x2=10000图3 图解法步骤3010002000300040005000200030004000x1x220x150x29000010000.5x1 +0.2x2=700d1+0d1+0d2-=0d2-0(810,1476)踢沫驾蚜鸵狈涕钎尺贿惕辅镁植肄厚梦州老戮宛身课盛
11、委叶支代律伞诉莽第3部分整数规划第3部分整数规划12管管 理理 运运 筹筹 学学目标规划的图解法目标规划的图解法目标规划的这种求解方法可以表述如下： 1确定解的可行区域。 2对优先权最高的目标求解，如果找不到能满足该目标的解，则寻找最接近该目标的解。 3对优先权次之的目标进行求解。注意：必须保证优先权高的目标不变。 4. 重复第3步，直至所有优先权的目标求解完。 罕投轩韶更镇磁獭声龄膝匀峻伏宜骚局瞥褪疙幕包蹈穴洼炬硅淮嚎翼梧顽第3部分整数规划第3部分整数规划13管管 理理 运运 筹筹 学学目标规划的图解法目标规划的图解法四、目标规划模型的标准化四、目标规划模型的标准化 例6中对两个不同优先权的
12、目标单独建立线性规划进行求解。为简便，把它们用一个模型来表达，如下： Min P1（d1+）+P2（d2-） s.t. 20x150x290000 0.5x1 +0.2x2-d1+d1-=700 3x1+4x2-d2+d2-=10000 x1,x2,d1+,d1-,d2+,d2-0 津恼行撼挖感傍猾订勾臭奄宦郧婆诧呕珊秃憾景摆砰妨辩蔬烈侍磅惶邱闪第3部分整数规划第3部分整数规划14管管 理理 运运 筹筹 学学目标规划的基本概念目标规划的基本概念（1）目标规划数学模型的形式有：线性模型、非线性模型、）目标规划数学模型的形式有：线性模型、非线性模型、整数模型、交互作用模型等整数模型、交互作用模型等
13、（2）一个目标中的两个偏差变量）一个目标中的两个偏差变量di-、 di+至少一个等于零，偏至少一个等于零，偏差变量向量的叉积等于零：差变量向量的叉积等于零：dd=0 （3）一般目标规划是将多个目标函数写成一个由偏差变量构）一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值，按多个目标的重要性，确定优先等级，顺成的函数求最小值，按多个目标的重要性，确定优先等级，顺序求最小值序求最小值 （4）按决策者的意愿，事先给定所要达到的目标值）按决策者的意愿，事先给定所要达到的目标值当期望结果不超过目标值时，目标函数求正偏差变量最小当期望结果不超过目标值时，目标函数求正偏差变量最小;当期望结果
14、不低于目标值时，目标函数求负偏差变量最小当期望结果不低于目标值时，目标函数求负偏差变量最小;当期望结果恰好等于目标值时，目标函数求正负偏差变量之和当期望结果恰好等于目标值时，目标函数求正负偏差变量之和最小最小虚嘻毯姚塘脖揖模姻值燥已辨笛痢助位杜镇链纶竿罚作匿帽锁他怨正道蠕第3部分整数规划第3部分整数规划15管管 理理 运运 筹筹 学学目标规划的基本概念目标规划的基本概念（5）由目标构成的约束称为目标约束，目标约束具有更大的弹）由目标构成的约束称为目标约束，目标约束具有更大的弹性，允许结果与所制定的目标值存在正或负的偏差，如例性，允许结果与所制定的目标值存在正或负的偏差，如例4.1中的中的5个等
15、式约束；如果决策者要求结果一定不能有正或负的偏差，个等式约束；如果决策者要求结果一定不能有正或负的偏差，这种约束称为系统约束，如例这种约束称为系统约束，如例4.1的材料约束；的材料约束；（6）目标的排序问题。多个目标之间有相互冲突时，决策者首）目标的排序问题。多个目标之间有相互冲突时，决策者首先必须对目标排序。排序的方法有两两比较法、专家评分等方先必须对目标排序。排序的方法有两两比较法、专家评分等方法，构造各目标的权系数，依据权系数的大小确定目标顺序；法，构造各目标的权系数，依据权系数的大小确定目标顺序；（7）合理的确定目标数。目标规划的目标函数中包含了多个目）合理的确定目标数。目标规划的目标
16、函数中包含了多个目标，决策者对于具有相同重要性的目标可以合并为一个目标，标，决策者对于具有相同重要性的目标可以合并为一个目标，如果同一目标中还想分出先后次序，可以赋予不同的权系数，如果同一目标中还想分出先后次序，可以赋予不同的权系数，按系数大小再排序。按系数大小再排序。楷镭冬场妈尉扰健伟板碾猴浅绵仗铂淄厂绕信认跳纺窖争果紧肛抑做扇并第3部分整数规划第3部分整数规划16管管 理理 运运 筹筹 学学目标规划的基本概念目标规划的基本概念 式中式中p k 为第为第k 级优先因子级优先因子, k=1 、2、 K；wkl- 、wkl+，为，为分别赋予第分别赋予第l个目标约束的正负偏差变量的权系数；个目标约
17、束的正负偏差变量的权系数；gl为目标的为目标的预期目标值，预期目标值，l=1,L (4.1b)为系统约束为系统约束,（4.1c）为目标约）为目标约束束（8）目标规划的一般模型设）目标规划的一般模型设xj（j=1,2,n）为决策变量）为决策变量姻瞧超盾艇撩莽缉斑帝唯牧暂孙渴鹊援羊泉码任遮扇搓渔吓房屉扛檬量菇第3部分整数规划第3部分整数规划17管管 理理 运运 筹筹 学学10、目标规划问题的解-满意解 目标规划问题的求解是分级进行的，首先求满足 级目标的解，然后在保证 级目标不被破坏的前提下再求满足 级目标的解. 以此类推， 因此，这样最后求出的解就不是通常意义下的最优解，称之为满意解. 因为对于
18、这种解来说，前面的目标是可以保证实现或部分实现的，后面的目标就不一定能保证实现或部分实现，有些可能就不能实现.满意解这一概念的提出是对最优化概念的一个突破.显然它更切合实际，更便于运用.9、目标规划的目标函数目标规划的目标函数，是由各目标约束的偏差变量及相应的优先因子和权系数构成，当一个目标规划确定后决策者的要求是尽可能接近各既定目标值，也就是偏差变量尽可能小， 目标函数一定是极小化的，三种基本表达式.（1）要求恰好达到目标值.这时决策值超过或低于目标值都是不希望的，因此有：（2）要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小，因此有： （3）要求不低于目标值，即允许超过目标
19、值，就是负偏差变量要尽可能地小，因此有： 溯棘还柯桔储晨实邀威躬溪恍弗莉纬泪褂驳惯乞蠕铣挠躁脆栓县业殃怖滞第3部分整数规划第3部分整数规划18管管 理理 运运 筹筹 学学复杂情况下的目标规划复杂情况下的目标规划例例7一工艺品厂商手工生产某两种工艺品A、B，已知生产一件产品A需要耗费人力2工时，生产一件产品B需要耗费人力3工时。A、B产品的单位利润分别为250元和125元。为了最大效率地利用人力资源，确定生产的首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于600工时，但也不能超过680工时的极限；次要任务是要求每周的利润超过70000元；在前两个任务的前提下，为了保证库存需要，要求
20、每周产品A和B的产量分别不低于200和120件，因为B产品比A产品更重要，不妨假设B完成最低产量120件的重要性是A完成200件的重要性的1倍。 试求如何安排生产？颇昼虎爵选养佣残纷卷湍俊劝桂阻室呸脖猩玻胯咽隋庆验弧庙缺做淡我婴第3部分整数规划第3部分整数规划19管管 理理 运运 筹筹 学学复杂情况下的目标规划复杂情况下的目标规划解：解： 本问题中有3个不同优先权的目标，不妨用P1、P2、P3表示从高至低的优先权。 对应P1有两个目标：每周总耗费人力资源不能低于600工时,也不能超过680工时； 对应P2有一个目标：每周的利润超过70000元； 对应P3有两个目标：每周产品A和B的产量分别不低
21、于200和120件。骄康遏嚏帕咙批剪撬椎霓变彬凤槛厚译衬矫塞惨铆枯桑煞凭胚拟哼方蓑邻第3部分整数规划第3部分整数规划20管管 理理 运运 筹筹 学学复杂情况下的目标规划复杂情况下的目标规划采用简化模式，最终得到目标线性规划如下： Min P1(d1+)+ P1(d2)+P2(d3-)+ P3(d4-)+ P3(2d5-) s.t. 2x1+3x2-d1+d1-=680 对应第1个目标 2x1+3x2-d2+d2-=600 对应第2个目标 250x1+125x2-d3-+d3+70000 对应第3个目标 x1-d4+d4-=200 对应第4个目标 x2-d5+d5-=120 对应第5个目标 x1
22、,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-0匙寸淫糯绚洱孵狡拱阀菌汲黄脆房翰瞅搽鹏躲肆眯挠拿缄灿四弓忽峦洋毙第3部分整数规划第3部分整数规划21管管 理理 运运 筹筹 学学复杂情况下的目标规划复杂情况下的目标规划 使用运筹学软件求解可得：x1=250；x2=60；d1+=0；d1-=0；d2+=80；d2-=0；d3+=0；d3-=0；d4+=50；d4-=0；d5+=0；d5-=60，目标函数d4-+2d5- =120。 可见，目标1、目标3和目标4达到了，但目标2、目标5都有一些偏差。 吸泳言衣姿竣马绥渝狡哄你洒袍棱翼箭陀纱年浙懦胺仕稿仟跑梗虏索
23、胺战第3部分整数规划第3部分整数规划22管管 理理 运运 筹筹 学学【例【例8】某企业集团计划用】某企业集团计划用1000万元对下属万元对下属5个企业进行技术改个企业进行技术改造，各企业单位的投资额已知，考虑造，各企业单位的投资额已知，考虑2种市场需求变化、现有竞种市场需求变化、现有竞争对手、替代品的威胁等影响收益的争对手、替代品的威胁等影响收益的4个因素，技术改造完成后个因素，技术改造完成后预测单位投资收益率预测单位投资收益率(（单位投资获得利润（单位投资获得利润/单位投资额）单位投资额）100)如表如表42所示所示集团制定的目标是：集团制定的目标是：（1）希望完成总投资额又不超过预算；）希
24、望完成总投资额又不超过预算；（2）总期望收益率达到总投资的）总期望收益率达到总投资的30%；（3）投资风险尽可能最小；）投资风险尽可能最小；（4）保证企业）保证企业5的投资额占的投资额占20%左右左右集团应如何作出投资决策集团应如何作出投资决策复杂情况下的目标规划复杂情况下的目标规划碌晾顾悯噶昂吊涛捧蛰实必捆侣娶炯管瞪珠剖呼娥妓上拧佑抠煞否园撰怀第3部分整数规划第3部分整数规划23管管 理理 运运 筹筹 学学企业企业1企业企业2企业企业3企业企业4企业企业5单位投资额单位投资额(万元万元)1210151320单位投单位投资收益资收益率预测率预测rij市场需求市场需求14.3255.845.26
25、.56市场需求市场需求23.523.045.084.26.24现有竞争对手现有竞争对手3.162.23.563.284.08替代品的威胁替代品的威胁2.243.122.62.23.24期望期望(平均平均)收益率收益率3.313.344.273.725.03表表42复杂情况下的目标规划复杂情况下的目标规划奏毖魏拈较块辈狐傈汹错暂遵宫遗庐屈掩垃秃矛肤阁贰蛆巍坚巢吓硼逼扎第3部分整数规划第3部分整数规划24管管 理理 运运 筹筹 学学【解】设【解】设xj（j=1,2,5）为集团对第）为集团对第 j 个企业投资的单位数个企业投资的单位数（1）总投资约束：）总投资约束：（2）期望利润率约束：）期望利润率
26、约束：整理得整理得复杂情况下的目标规划复杂情况下的目标规划狈锭竭苹褂逮龋联谭碰商痒舆校囚供父尹太树刻伍譬畦稚惦尧贾拦愤岩肆第3部分整数规划第3部分整数规划25管管 理理 运运 筹筹 学学（4）企业）企业5占占20%的投资的目标函数为的投资的目标函数为 ,约束条件约束条件即即(3）投）投资风险约束投束投资风险值的大小一般用期望收益率的方的大小一般用期望收益率的方差表示，但方差是差表示，但方差是x的非的非线性函数性函数这里用离差（里用离差（rijE(rj)）近）近似表示似表示风险值，例如，集，例如，集团投投资5个企个企业后后对于市于市场需求需求变化第化第一情形的一情形的风险是：是： 则则4种因素风
27、险最小的目标函数为：种因素风险最小的目标函数为： ，约束条件为，约束条件为复杂情况下的目标规划复杂情况下的目标规划唬夏端蕾欺陌甩眷触舶嗡共占扑政豺先糜汲切坝阜漠勇阅齐卵丘匈留愈手第3部分整数规划第3部分整数规划26管管 理理 运运 筹筹 学学根据目标重要性依次写出目标函数，整理后得到投资决策的根据目标重要性依次写出目标函数，整理后得到投资决策的目标规划数学模型：目标规划数学模型：复杂情况下的目标规划复杂情况下的目标规划戚亢穷啮抡档庚岁莱耪梁拦衍豌豌颧肄蓑钨熄疫锦灸软赞骡廓祷腑龙畴剁第3部分整数规划第3部分整数规划27管管 理理 运运 筹筹 学学【例【例1】车间计划生产】车间计划生产I、II 两
28、种产品，每种产品均需经过两种产品，每种产品均需经过A、B两道工序加工工艺资料如表两道工序加工工艺资料如表43所示所示 产品产品工序工序产品甲产品甲产品乙产品乙每天加工能力每天加工能力(小时小时)A22120B12100C2.20.890产品售价产品售价(元元/件件)5070产品利润产品利润(元元/件件)108（1）车间如何安排生产计划，使产值和利润都尽可能高）车间如何安排生产计划，使产值和利润都尽可能高（2）如果认为利润比产值重要，怎样决策）如果认为利润比产值重要，怎样决策表表43练习练习炸局活膘捞碎找铀镑烯滚疏那哨额拽淖占哎抹蛇胡烂解湖毡哀膜镭搀啡少第3部分整数规划第3部分整数规划28管管
29、理理 运运 筹筹 学学【解】设【解】设x1、x2分别为产品甲和产品乙的日产量，得到线性多分别为产品甲和产品乙的日产量，得到线性多目标规划模型：目标规划模型：练习练习纶郝秦龙裤抡摄疆铲景宇成馋由踪哟班庙逮催讫霞塞夸瑚懈参梯棚贿獭骤第3部分整数规划第3部分整数规划29管管 理理 运运 筹筹 学学例例2 某电视机厂装配黑白和彩色两种电视机，每装配某电视机厂装配黑白和彩色两种电视机，每装配一台，电视机需占用装配线一台，电视机需占用装配线1小时，装配线每周计划小时，装配线每周计划开动开动40小时，预计市场每周彩色电视机的销量是小时，预计市场每周彩色电视机的销量是24台，台，每台可获利每台可获利80元，黑
30、白电视机的销量是元，黑白电视机的销量是30台，每台可台，每台可获利获利40元，该厂确定的目标为：元，该厂确定的目标为：P1：充分利用装配线每周计划开动：充分利用装配线每周计划开动40小时；小时；P2：允许装配线加班，但加班时间每周昼不超：允许装配线加班，但加班时间每周昼不超 过过10小时；小时；P3：装配电视机的数量尽量满足市场需要：装配电视机的数量尽量满足市场需要. 试建立该试建立该问题的目标规划模型，并用图解法求解黑白和彩色电问题的目标规划模型，并用图解法求解黑白和彩色电视机的产量视机的产量.练习练习专摊俄皋冲执帕婪葵池昼窍捉某侍技量寇店涤晌申择宵解歉顶嵌玫讹弧佰第3部分整数规划第3部分整数规划32
