数学建模-投资收益、加工次序及其他

第二讲投资收益、加工次序及其他§1投资收益问题问题的提出一个公司有22亿元资金可用来投资，现有6个项目可供选择，各项目所需投资金额和预计年收益如下表所示：表1项目123456投资（亿元）526468收益（亿元）0.50.40.60.50.91问应选择那几个项目投资，使公司收益最大？2、模型的建立记显然，投资总金额满足而预计年总收益满足从而数学模型为：3、模型的求解由于共有个项目，对每一项目都有投资和不投资两种选择，因此总共有种选择。穷举法分枝定界法*1计算每个项目的收益率：项目1

2

3

4

56

投资（亿元）526468收益（亿元）0.50.40.60.50.91收益率0.10.20.10.1250.150.125放宽约束条件，允许取正实数值，优先选择收益率高的项目，得到两组最优解：对应的年收益为，对应的年收益为由于我们放宽了必须取值的约束，所以上述最优收益超过实际的最优收益。1）先松弛，求得最优解；2）分支定界在分支求解的过程中，会出现各变量均取值的可行解，这些解对应的收益值之最大者，可定为原问题最优收益的一个候选者，同时，分支求得的最优解（不管变量是否取分数值）表明：该最优值是分支所含有的一切可行解的收益的上界。这一过程称为定界。3）当分支进行到某一步时发现某一分支的上界不大于已发现的候选者，或继续进行找不到可行解时，这一支的分支可不必进行下去，这一过程叫做剪支。分支定界法就是不断采用分支、定界、剪支的过程，最终得到最优解。§2加工次序问题1、问题的提出有10个工件在一台机床上加工。在这10个工件中，有些工件必须在另一些工件加工完毕之后才能加工，这些必须加工的工件称为紧前工件。按规定，在工件运抵后266小时内应加工完毕，否则要支付一定的赔款，赔款数正比于延误的时间，各工件每延误1小时的赔款额不同。表2列出了各工件所需的加工时间、加工次序要求和每延误1小时的赔款额。表2工件号12345678910加工时间20282545161260102030紧前工件387/1,2,6843591小时赔款12141510101112867设由于机床的故障，10个工件运抵之后T小时才开始加工。要求安排一个加工次序，使得支付的赔款最少。模型的建立绘制网络图用圆圈表示加工一个工件；用箭头表示加工的次序要求，即箭头指向的圆圈内的工件必须在箭尾圆圈内的工件加工完毕之后方能开始加工。ii)优化目标假设两个工件加工之间，机床做准备的时间可以忽略。第个工件的加工时间，第个工件延误1小时的赔款数，设是的一个排列，满足网络图描述的加工次序，称为可行的加工次序。由于开工延误了小时，第个工件的完工时间为则对于可行的加工次序，赔款总额为Total=问题归结为求可行的加工次序，使得赔款总额Total达到最小。§3两辆平板车的装载问题问题的提出有两辆长，载重的铁路平板车，要装载7种不同规格的货物箱。这7种箱子的厚度、重量、库存量如表3所示。表3箱类型厚度48.75261.37248.75264重量2310.5421库存量（个）8796648若各种箱子的高度和宽度均符合铁路运输的标准（不妨设它们的宽度和高度均为相同的），在每辆车上装载的货物箱的厚度和不超出，总重量不超过的前提下，应如何装载，使得平板车浪费的空间最小？当地铁路部门还有一个附加的规定：第三种箱子装车的厚度和不得超过模型的建立假设装载时相邻两箱货物之间的间隙可以忽略。记第种货物箱的厚度，第种货物箱的重量，第种货物箱的库存量，分别表示第种货物箱在两辆平板车上的装载数。车辆浪费的空间最小，等价于使装载货物箱的厚度和达到最大。记装载在两辆车上货物箱的厚度和，则目标函数依据题目的要求，应满足如下约束条件：装载空间的限制为载重量的限制为货物箱库存量的限制为第三种货物箱的限制可表述为综上所述，两辆平板车的装载问题，可以归结为如下的整数规划模型：其中为非负整数。§4截断切割1、问题的提出某些工业部门（如贵重石材加工等）采用截断切割的加工方式。这里“截断切割”是指将物体沿某个切割平面分成两部分。从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过6次截断切割。设水平切割单位面积的费用是垂直切割单位面积费用的r倍，且当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时，因调整刀具需额外费用e。试为这些部门设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少。（由工艺要求，与水平工作台接触的长方体底面是事先指定的）详细要求如下：（1）需考虑的不同切割方式的总数。（2）给出上述问题的数学模型和求解方法。（3）试对某部门用的如下准则作出评价：每次选择一个加工费用最少的待切割面进行切割。（4）对于e=0的情形有无简明的优化准则。（5）用以下实例验证你的方法：待加工长方体和成品长方体的长、宽、高分别为10、14.5、19和3、2、4，二者左侧面、正面、底面之间的距离分别为6、7、9（单位均为厘米）。垂直切割费用为每平方厘米1元，r和e的数据有以下4组：a.r=1,e=0;b.r=1.5,e=0;c.r=8,e=0;d.r=1.5;2<=e<=15.2、模型的假设及说明⒈每次切割将物体分成两部分，并把切除部分立即拿走。⒉切割加工具有水平切割和垂直切割两种专用刀具。⒊第一次垂直切割时，无需调整刀具。⒋假设最后一次切割底面。⒌在切割过程中物体不能翻转、旋转，否则否则垂直切割与水平切割可以互相转化。3、基本符号及有关概念的说明表示成品长方形的左、右、前、后、上、下表面；:表示对第面进行操作；:表示成品长方体面i与原长方体相应面之间的距离(单位：cm)；A、B、C:分别表示原长方体的长、宽、高(单位：cm)；:垂直切割单位面积的费用(单位：元/)；:水平切割单位面积与垂直切割单位面积费用的比值；:垂直切割每调整一次刀具所花的费用(单位：元/次)；:当时，采用最优切割方式进行切割所需费用；:当e=0时，采用最优切割方式调整刀具的次数。4、模型的建立因最后一次切割是切割底面，当把不同的切割方式当把不同的切割方式仅仅理解为的不同排列方式时，则切割方式总数为。i)刀具调整费用e=0的情形 在e=0的情形下，由于调整刀具的费用为0，因此若能找到一种切割方式，使各个切面的有效切割面积之和最小(此时费用最小)，则此方式即为最优切割。定理1当采取最优切割方式进行切割时，⑴若满足且时，切割优于的充要条件为；⑵若满足而时，切割优于的充要条件为；证明：设X表示截断切割后所剩下的长方体待切割面的集合，a,b,c表示截断切割后剩下的长方体的长、宽、高，设f(X,a,b,c)出发，对待切割的表面采取最优的切割方式，将X中所有面切割完毕所需费用，f(X,a,b,c,i)表示由状态(X,a,b,c)出发，先进行切割，再以最优的切割方式将中所有面切割完毕的费用，其中表示由状态出发，相继进行切割，切割，再以最优切割方式对中所有面切割完毕的费用，则 ⑴当时故从而得到对左、右两侧进行连续切割时，与先后顺序无关。同理可得出对前后两面进行连续切割亦与先后顺序无关。⑵当i=1,2且j=3,4时同理，于是 故优于的充分必要条件为⑶当i=1,2且j=5时而故故优于的充分必要条件为，即同理，i=3,4且j=5时，优于的充分必要条件为综合⑴⑵⑶知定理1得证。利用定理1，我们得到如下的简明优化准则：优化准则：设分别表示成品长方体与原材料长方体对应的左侧面、右侧面、前面、后面、上面、下面之间的距离。将记成，再将它们按由小到大的顺序排成：则最优切割方式为：ii)、调整刀具费用情形当时，由优化准则可以很容易地找出最优切割方式，计算出最优切割方式的费用及调整刀具次数K，显然调整刀具次数K只可能为1，2，3中的某一个。下面，我们根据K的取值情况利用e=0时优化准则，来建立的优化数学模型。首先，根据调整刀具次数来把所有切割方式分成三类，对同一类，我们把切割方式的费用分别进行排序。用表示e=0时调整刀具次数为i的切割费用的排序结果，其中i=1，2，3。即于是，当时，问题转化为计算，此时最优切割方式的费用为，如何寻找成为问题的焦点。定理2：若e=0时最优切割方式的调整刀具次数为K=1，则当时最优切割方式的费用为。证明：当K=1时，有，从而对所有i,j均有，i=1,2,3;j=1,2,…,ki.当e0时，显然有故最优切割方式的费用为，可见当K=1时，e0时的最优切割方式与e=0时的最优切割方式相同。证毕。定理3：⑴若e=0时，最优切割方式的调整刀具次数为K=2，则当时，最优切割方式的费用为。⑵若e=0时，最优切割方式的调整刀具次数为K=3，则当时，最优切割方式的费用为。证明：⑴当K=2时，由的定义有，从而故最优方式切割费用为=⑵当K=3时，同理可证。证毕推论：⑴无论K为何值，要求出最优切割方式的费用，最多只需计算和⑵当K=2时若，则最优切割方式的费用为若，则最优切割方式的费用为⑶当K=3时若，则最优切割方式的费用为若，则最优切割方式的费用为若，则最优切割方式的费用为定理4：（最优切割方式的必要条件）设分别表示原材料长方体与成品长方体左侧面、右侧面之间的距离，表示切割左、右侧面，则在任何最优切割方式中，（或）一定是按（或）从大到小的顺序进行切割，换句话说，若（或），则最优切割方式一定是以（或）的形式出现。证明：我们不考虑为相邻切割方式的情形，因为当以相邻形式出现时，由于切割平行，所以对换所得到的切割方式与对换前的切割方式是同一种切割方式。（反证法）假设存在某个最优切割方式，其中，对换得到切割方式显然的调整刀具的次数相同。用表示采用切割方式所需的费用，为了证明方便，不妨设之间穿插了一个切割（i=3,4）设按方式T进行到时的状态为(X,a,b,c)（符号定义见定理1的证明）则同理由题设知，，即当之间穿插或进行几个切割时，同理可证仍然成立，这说明切割方式优于切割方式，与假设切割方式T为最优的切割方式相矛盾。证毕。下面，我们利用前面的结果，通过建立定理5和定理6，可显著地减少搜索次数，事实上，在最坏的情形，也只需进行6次搜索，有时，可一次得到。设对应于的面的切割，i=1，2，3，4令对应于的面的切割，即对应于的面的切割，即定理5：当时（即K=2），在从切割方式中抽去和的情况下：i)若则所对应的切割方余下切割的排列为ii)若则所对应的切割方余下切割的排列为iii)若则所对应的切割方余下切割的排列为或证明：因为所对应的切割方式的调整刀具的次数为1，而水平切割不影响刀具调整的次数，所以在抽去后，所对应的切割方式余下切割的排列，其调整刀具次数仍然为1，从而只可能为⑴⑵用表示按进行切割所需费用，则若即当时，将优于，i)得证。同理可证得ii),iii)。证毕。定理6：若时（即K=3），在从所有切割方式中抽去和的情况下：i)若则所对应的切割方余下切割的排列为ii)若则所对应的切割方余下切割的排列为iii)若则所对应的切割方余下切割的排列为或仿定理5，同样可证明之。由定理1-6，我们归纳出如下算法：由e=0的优化准则得到最优切割方式；计算K值，赋初值,,若K=1：计算，转向第6步；若K=2：转向第4步；3．⑴计算，若1-a)若则按切割方式计算，转向第4步；1-b)若则按切割方式计算，转向第4步；1-c)比较：i)ii)iii)取，转向第4步⑵2-a)若则按切割方式计算，转向第4步；2-b)若