第 2 天打卡--整数计划 (1)
文章目录
- 一、谈谈我的理解
- 二、题目
- 1)题目与简析
- 2)分枝定界法步骤
- 2.1)第一步
- 2.2)第二步
- 2.3)第三步
- 2.4)第四步
- 2.5)结论
- 三、总结
一、谈谈我的理解
前两次打卡,我们学会了线性规划,这里为什么又引入一个整数规划呢?其实两个规划很类似,唯一的区别就是整数规划限制了我们的变量x必须为整数,而线性规划没有限制变量类型。
为什么我们要引入整数规划呢?在实际生活中,我们就算付钱,可能也很少遇到让你付小数的钱,都是让你给一个整数,因此这就是整数规划的由来。
二、题目
1)题目与简析
假设我们有如下的整数规划:
假设我们先把最后一个条件限制为整数暂时忽略?你是不是能用前面的知识求解出max,x1,x2呢?请把你的matlab求解过程写到博客,提交到任务中。(晚上我提交答案)
我在这里先直接给出答案:
x1 = 4.8092, x2 = 1.8168,z = 355.8779
根据我计算出的结果可以看到x1和x2都不满足整数情况,因此这就不再是最优解了。
2)分枝定界法步骤
方法用处:分枝定界法可用于解纯整数或混合的整数规划问题
2.1)第一步
根据我们出的结果,我们可以暂定z的上限(最大值)可以是356;我们也可以一样看出x1,x2分别为0时,z最小值为0;因此最大值z的范围可以暂定为:0=<z=<356
2.2)第二步
因为 x1, x2 当前均为非整数,故不满足整数要求,任选一个进行分枝。设选 x1进行分枝,把可行集分成 2 个子集:
x1 =<[4.8092] = 4 , x1 >= [4.8092] +1 = 5
4与5之间没有整数,因此这种方法就是叫做分枝。
这两个子集的规划及求解如下:
问题 B1 :
目标函数:
Max z = 40x1 + 90x2
约束条件:
9*x1+7*x2<=56 7*x1+20*x2<=70 0<x1<4 x2>0
因为我们只对x1做了分枝,因此x2的约束不变。
这里计算方法跟线性规划不一样,但是有一点我没有讲到的是前面我们没有遇到x在两者之间的问题,因此我对此B1做matlab计算最优解如下:
clc clear all c=[40 90];%用目标函数系数来确定 a=[9 7 ;7 20];%约束条件左边约束 b=[56 70];%约束条件右边系数 aeq=[];%没有等式约束,因此aeq,beq都为空 beq=[]; lb=[0;0];%下限依然都为0 ub=[4;inf];%x1上限为4,x2没有上限 [x,y]=linprog(-c,a,b,aeq,beq,lb,ub); %这里没有等式约束,对应的矩阵为空矩阵 x %获取对应x1,x2 best=c*x%计算最优值
运行结果:
因此我们得出:x1 = 4.0, x2 = 2.1,z1 = 349
。
我们对下x1做了分支,因此我们还要计算x1的另一半(我们就是相当于把x1范围划分两半,分别计算,后面我们再求其和)。因此对于x1有问题 B2 :
目标函数:
Max z = 40x1 + 90x2
条件约束:
9*x1+7*x2<=56 7*x1+20*x2<=70 x1>=5 x2>0
上面我已经写过解法了,请对照上面的解法写出你的matlab求解,并写在博客里(本篇文章所有留下的问题写在一篇博客提交任务)
我直接给出答案:
可以看到x1=5 x2=1.5714 z=341.4286
现在我们把最优值再定界确定范围为:0 ≤ z ≤ 349
。
2.3)第三步
对第二步的问题B1继续分支,我们可以看到问题B1只有x2有小数,因此我们是对B1问题里的x2进行分枝(按照第一步的方法):
0=<x2<[2.1]=2,x2>[2.1]+1=3
从而得到问题如下:
B11问题目标函数:
Max z = 40x1 + 90x2
约束条件:
9*x1+7*x2<=56 7*x1+20*x2<=70 0<=x1<=4 2>x2>0
matlab计算代码如下:
clc clear all c=[40 90];%用目标函数系数来确定 a=[9 7 ;7 20];%约束条件左边约束 b=[56 70];%约束条件右边系数 aeq=[];%没有等式约束,因此aeq,beq都为空 beq=[]; lb=[0;0];%下限依然都为0 ub=[4;2];%x1上限为4,x2没有上限 [x,y]=linprog(-c,a,b,aeq,beq,lb,ub); %这里没有等式约束,对应的矩阵为空矩阵 x %获取对应x1,x2 best=c*x%计算最优值
运行:
然后我们再计算x2另一个分枝,唯一变化的还是x范围.
问题B12:
目标函数:
Max z = 40x1 + 90x2
条件约束:
9*x1+7*x2<=56 7*x1+20*x2<=70 0<=x1<=4 x2>3
matlab计算结果为:(请你在博客写上此题的matlab计算过程)
因此我们可以再次确定z范围为:340 ≤ z ≤ 341
到这里我们已经对问题B1做出完美分枝,因此我们再对问题B2进行分枝,请看第四步。
2.4)第四步
为了便于观看,我把问题B2拖下来:
根据上面的结果,x2=1.5714为小数,因此我们对B2中的x2进行分枝。
0=<x2<[1.5714]=1,x2>[1.5714]+1=2
得到问题B21如下:
目标函数:
Max z = 40x1 + 90x2
条件约束:
9*x1+7*x2<=56 7*x1+20*x2<=70 x1>=5 1>x2>0
用matlab计算结果如下:(请你在博客写出你的matlab代码)
B22问题如下:
目标函数:
Max z = 40x1 + 90x2
条件约束:
9*x1+7*x2<=56 7*x1+20*x2<=70 x1>=5 x2>2
matlab如下:
clc clear all c=[40 90];%用目标函数系数来确定 a=[9 7 ;7 20];%约束条件左边约束 b=[56 70];%约束条件右边系数 aeq=[];%没有等式约束,因此aeq,beq都为空 beq=[]; lb=[5;2];%下限 ub=[inf;inf];%上限 [x,y]=linprog(-c,a,b,aeq,beq,lb,ub) %这里没有等式约束,对应的矩阵为空矩阵
运行如下:
根据结果我指出的地方可以看到,没有解。
综合B2的两个分枝,B21分枝后依然有小数,不可取;B22不可行解,因此也不可取。这样的操作呢,叫做剪枝。
2.5)结论
由于B2的两个分枝都不可取,B1只有一个枝可取,即最优解为:
x1 = 4, x2 = 2,z = 340
三、总结
开始,将要求解的整数规划问题称为问题 A ,将与它相应的线性规划问题称为问题 B。求解情况如下:
- B 没有可行解,这时 A 也没有可行解,则停止
- ) B 有最优解,并符合问题 A 的整数条件, B 的最优解即为 A 的最优解,则停止。
- B 有最优解,但不符合问题 A 的整数条件,记它的目标函数值为 z,通过我上述所说的四个步骤使用花枝定界法进行分枝,剪枝,最后得出结果。
再次提醒: 请务必完成我在本篇文章中留下的问题,写一篇博客提交任务,学习是靠你自己,你不努力,总有人比你更努力。
推荐阅读
-
正负偏差变量 即 d2+、d2- 分别表示决策值中超出和未达到目标值的部分。而 di+、di- 均大于 0 刚性约束和目标约束(柔性目标约束有偏差) 在多目标规划中,>=/<= 在刚性约束中保持不变。当需要将约束条件转换为柔性约束条件时,需要将 >=/<= 更改为 =(因为已经有 d2+、d2- 用来表示正负偏差),并附加上 (+dii-di+) 注意这里是 +di、-di+!之所以是 +di,-di+,是因为需要将目标还原为最接近的原始刚性约束条件 优先级因素和权重因素 对多个目标进行优先排序和优先排序 目标规划的目标函数 是所有偏差变量的加权和。值得注意的是,这个加权和都取最小值。而 di+ 和 dii- 并不一定要出现在每个不同的需求层次中。具体分析需要具体问题具体分析 下面是一个例子: 题目中说设备 B 既要求充分利用,又要求尽可能不加班,那么列出的时间计量表达式即为:min z = P3 (d3- + d3 +) 使用 + 而不是 -d3 + 的原因是:正负偏差不可能同时存在,必须有 di+di=0 (因为判定值不可能同时大于目标值和小于目标值),而前面是 min,所以只要取 + 并让 di+ 和 dii- 都为正值即可。因此,得出以下规则: 最后,给出示例和相应的解法: 问题:某企业生产 A 和 B 两种产品,需要使用 A、B、C 三种设备。下表显示了与工时和设备使用限制有关的产品利润率。问该企业应如何组织生产以实现下列目标? (1) 力争利润目标不低于 1 500 美元; (2) 考虑到市场需求,A、B 两种产品的生产比例应尽量保持在 1:2; (3)设备 A 是贵重设备,严禁超时使用; (4)设备 C 可以适当加班,但要控制;设备 B 要求充分利用,但尽量不加班。 从重要性来看,设备 B 的重要性是设备 C 的三倍。 建立相应的目标规划模型并求解。 解:设企业生产 A、B 两种产品的件数分别为 x1、x2,并建立相应的目标计划模型: 以下为顺序求解法,利用 LINGO 求解: 1 级目标: 模型。 设置。 variable/1..2/:x;! s_con_num/1...4/:g,dplus,dminus;!所需软约束数量(g=dplus=dminus 数量)及相关参数; s_con(s_con_num);! s_con(s_con_num,variable):c;!软约束系数; 结束集 数据。 g=1500 0 16 15. c=200 300 2 -1 4 0 0 5; 结束数据 min=dminus(1);!第一个目标函数;!对应于 min=z 的第一小部分;! 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); !使用设置完成的数据构建软约束表达式; ! !软约束表达式 @for(variable:@gin(x)); !将变量约束为整数; ! 结束 此时,第一级目标的最优值为 0,第一级偏差为 0: 第二级目标: !求 dminus(1)=0,然后求解第二级目标。 模型。 设置。 变量/1..2/:x;!设置:变量/1..2/:x; ! s_con_num/1...4/:g,dplus,dminus;!软约束数量及相关参数; s_con(s_con_num(s_con_num));! s_con(s_con_num,variable):c;! 软约束系数; s_con(s_con_num,variable):c;! 结束集 数据。 g=1500 0 16 15; c=200 300 2 -1 4 0 0 5; 结束数据 min=dminus(2)+dplus(2);!第二个目标函数 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); ! 软约束表达式;! dminus(1)=0; !第一个目标结果 @for(variable:@gin(x)); ! 结束 此时,第二个目标的最优值为 0,偏差为 0: 第三目标 !求 dminus(2)=0,然后求解第三个目标。 模型。 设置。 变量/1..2/:x;!设置:变量/1..2/:x; ! s_con_num/1...4/:g,dplus,dminus;!软约束数量及相关参数; s_con(s_con_num(s_con_num));! s_con(s_con_num,variable):c;! 软约束系数; s_con(s_con_num,variable):c;! 结束集 数据。 g=1500 0 16 15; c=200 300 2 -1 4 0 0 5; 结束数据 min=3*dminus(3)+3*dplus(3)+dminus(4);!第三个目标函数。 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); ! 软约束表达式;! dminus(1)=0; !第一个目标约束条件; ! dminus(2)+dplus(2)=0; !第二个目标约束条件 @for(variable:@gin(x));! 结束 最终结果为 x1=2,x2=4,dplus(1)=100,最优利润为
-
第 2 天打卡--整数计划 (1)
-
科比鹰郡事件始末最强解析(全文)-插曲:OK两人最初的相识。OK两人在齐聚湖人之前就曾相遇。1992年,14岁的科比通过父亲的关系,进入了奥兰多更衣室向便士哈达威索要签名,但遭到置之不理,反倒是新秀时期的奥尼尔对科比鼓励有加,不仅给他签名,还和科比聊了很多,并且希望日后能在NBA看见科比,没想到一语成真,后者真的成为了他的队友,这也是日后奥尼尔对于科比和自己的矛盾产生仇恨心里的原因,因为奥尼尔始终认为最初对科比的善意没有换来以德报德。 多年以后,鹰郡事件女主角凯特琳澄清事实。据她自述,当时她是为了给母亲凑医药费,设法和科比发生关系,目的就是为了钱,科比支付的赔偿金拯救了她的母亲。最终事情真相浮出水面,这是有预谋的“仙人跳”讹诈,但是好事依然不出门。 不得不说,鹰郡事件是科比犯下的错。自此,除了篮球以外,科比将更多的时间回归家庭。然而鹰郡事件最大的受害者是科比本人和他的妻子瓦妮莎。那么他们都有哪些损失呢? 在道德上:科比饱受批评,引发不少妇女团体对他不满,甚至受人唾弃。 image 在家庭上:科比与瓦妮莎产生了信任危机,尤其是瓦妮莎的流产导致这个家庭失去了第二个孩子,而这个孩子或许是科比夫妇唯一的儿子。因此这件事让科比一直很后悔。 在金钱上:科比的律师费(至少1200万美元)、赔偿费(不少于500万美元)、再加上往返奔波费、诉讼费等估计超过2000万美金。此外商业上严重受阻,商业价值跌落谷底,赞助商几乎抛弃了他,阿迪达斯也在这个时候和科比解约。其经济损失不可估量。 在事业上:球迷的质疑和谩骂声音不断;湖人队内部发生微妙变化,队友和他有了一定距离;禅师菲尔杰克逊在得知科比“强奸”女性后更是对他区别对待,因为禅师的女儿曾经经历了强奸,他对科比十分厌恶,间接地导致禅师离开了湖人队;OK这对王炸组合解散;大卫斯特恩放弃了科比的造神计划,迅速将资源推向了詹姆斯;赛场上,虽然科比有着赶场法则的传奇,但就整个03—04赛季而言,科比表现起起伏伏,整体状态下滑明显。 image 不可否认,鹰郡事件导致科比处在生涯最低谷的时刻,那个阶段也许只有麦迪经常陪在科比身边给他带来一些安慰。但接下来科比以他顽强的意志和超乎常人的努力为自己进行救赎:三节打卡62分、单场81分神迹、连续4场50+、更改球衣号码变成黑曼巴、连续双一阵、MVP、奥运会冠军、两连冠+FMVP…… 现在回想起来,连当时受伤害最大的瓦妮莎都选择原谅了科比,但键盘侠们依然指指点点。 2018年3月5日,科比凭借其亲自参与制作并配音的退役动画短片《亲爱的篮球》获得了第90届奥斯卡“最佳动画短片奖”,而“小金人”的巨大荣誉,让奥尼尔都自嘲“兄弟,你真的让我羡慕!真没法追逐你了”,同时他也因此被选为了Animation Is电影节的评委。 image 随后科黑以“鹰郡事件”为理由向奥斯卡请愿,要收回科比的小金人,虽然小金人未收回,但10月18日,科比被取消了电影节的评委资格。 时间回到2020年。 1月26日科比因直升机坠毁意外身亡。斯人已逝,可喷子们还是没有放过他。有些人甚至借科比死亡这一消息来蹭热度! 就在科比去世的第二天,美国女演员埃文·蕾切尔·伍德(Evan Rachel Wood)在推特上称呼科比为“强奸犯”,遭到美国网友们的强烈反对。 一周后,据2月3日《每日邮报》消息,迪斯尼的女继承人阿比盖尔·迪斯尼在社交网络上连续发了24个帖子,直指2003年科比的性侵事件,认为科比犯强奸罪,强调科比不该被神化,他不是上帝。 但也有很多人相信科比没有强奸,据2月4日《每日邮报》报道,WNBA传奇女篮运动员丽莎·莱斯利为科比辩护,认为科比不是用武力侵犯女性的人,科比的妻子也一直在维护自己逝去的丈夫…… image 然而,不管是怎样的事实,即使法律宣判了科比无罪,即使是被敲诈勒索,成为受害人,可事到如今,科比依然被很多人戴上“强奸犯”的帽子,对于一个已经逝世的人来说,这是他最大的损失。 插曲:中国官方媒体对科比的态度,只列举一下几个主要媒体。
-
仅剩1天!参与乐享活动,赢取视频VIP季卡和MUJI套装|12月享礼月·第2波