搜索
运筹学基础及应用期末考试复习资料（内部使用）主编（讲）：刘亚春（教授）南华大学信息科学与数学系1第一章线性规划及单纯形法1、（生产计划问题）某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表1-12..若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0.2万元.现该厂考虑明年的昀佳生产方案，使该厂在完成合同的情况下，全年的生产费用昀低.试建立线性规划模型.表1-12季度j生产能力ja（吨）生产成本jd（万元/吨）需求量jb（吨）13015．02024014．02032015．33041014．810解:现在我们对本问题定义三种不同形式的决策变量，从而从不同的途径来构建模型.（1）设工厂第j季度生产产品jx吨首先，考虑约束条件：第一季度末工厂需交货20吨，故应有201≥x；第一季度末交货后积余（201−x）吨；第二季度末工厂需交货20吨，故应有202021≥+−xx；类似地，应有3034021≥+−+xxx；第四季度末供货后工厂不能积压产品，故应有10704321=+−++xxxx；又考虑到工厂每个季度的生产能力，故应有jjax≤≤0.其次，考虑目标函数：第一季度工厂的生产费用为15.01x，第二季度工厂生产的费用包括生产费用142x及积压产品的存贮费)20(2.01−x；类似地，第三季度费用为)40(2.03.15213−++xxx，第四季度费用为)70(2.08.143214−+++xxxx.工厂一年的费用即为这四个季度费用之和.整理后，得下列线性规划模型：min268.145.154.146.154321−+++=xxxxzs.t.21xx+40≥321xxx++70≥804321=+++xxxx30201≤≤x，4002≤≤x，2003≤≤x，1004≤≤x.（2）设第j季度工厂生产的产品为jx吨，第j季度初存贮的产品为jy吨（显然，01=y）.因为每季度初的存贮量为上季度存贮量、生产量之和与上季度的需求量之差，又考虑到第四季度末存贮量为零，故有：2120yx=−，32220yxy=−+，43330yxy=−+，1044=+xy；同时，每季度的生产量不能超过生产能力：jjax≤；而工厂四个季度的总费用由每季的生产费用与存贮费用组成，于是得线性规划：min44332218.142.03.152.0142.00.15xyxyxyxz++++++=2s.t.2021=−yx20322=−+yxy30433=−+yxy1044=+xy3001≤≤x4002≤≤x2003≤≤x1004≤≤x0≥jy，=j2，3，4.（3）设第i季度生产而用于第j季度末交货的产品数量为jix吨.根据合同要求，必须有：2011=x，202212=+xx，30332313=++xxx，1044342414=+++xxxx.又每季度生产而用于当季和以后各季交货的产品数不可能超过该季工厂的生产能力，故应有：3014131211≤+++xxxx，40242322≤++xxx，203433≤+xx，1044≤x.第i季度生产的用于第j季度交货的每吨产品的费用)(2.0ijdciij−+=，于是，有线性规划模型：minz=141312116.154.152.150.15xxxx+++2423224.142.1414xxx+++4434338.145.153.15xxx+++s.t.2011=x202212=+xx30332313=++xxx1044342414=+++xxxx3014131211≤+++xxxx40242322≤++xxx203433≤+xx1044≤x0≥jix=i1，…，4；=j1，…，4，ij≥.2、（合理下料问题）某工厂要制作100套专用钢架，每套钢架需要用长为2.9m、2.1m和1.5m的圆钢各一根。已知原料每根长7.4m，现考虑应如何下料，可使所用原料昀省？解:分析：利用7.4m长的圆钢截成2.9m、2.1m、1.5m的圆钢共有如表1-13所示的8种下料方案.表1-13下料方案表方案毛坯/m方案1方案2方案3方案4方案5方案6方案7方案82．9211100002．10210321031．510130234合计7．37．16．57．46．37．26．66．0剩余料头0．10．30．90．01．10．20．81．4一般情况下，我们可以设87654321,,,,,,,xxxxxxxx分别为上面8种方案下料的原材料根数.根据目标的要求，可以建立两种形式的目标函数：材料根数昀少：minz=87654321xxxxxxxx+++++++(1.27)剩余料头昀少：minz=876543214.18.02.01.109.03.01.0xxxxxxxx+++++++（1.28）约束是要满足各种方案剪裁得到的2.9m、2.1m、1.5m三种圆钢各自不少于100个，即2.9m:43212xxxx+++100≥2.1m:322xx+76523xxx+++100≥1.5m:1x433xx++100432876≥+++xxx非负条件1x，2x，3x，4x，5x，6x，7x，08≥x这样我们用目标函数（1.27）可建立如下数学模型：min87654321xxxxxxxxz+++++++=s.t.43212xxxx+++100≥322xx+76523xxx+++100≥1x433xx++100432876≥+++xxx1x，2x，3x，4x，5x，6x，7x，08≥x利用线性规划单纯形法求解可得：*x=（10，50，0，30，0，0，0，0）T，昀少使用的材料为90（根），各种圆钢数均正好100个.如果用目标函数（1.28），可建立如下数学模型：min876543214.18.02.01.109.03.01.0xxxxxxxxz+++++++=s.t.43212xxxx+++100≥322xx+76523xxx+++100≥1x433xx++100432876≥+++xxx1x，2x，3x，4x，5x，6x，7x，08≥x利用线性规划单纯形法求解可得：*x=（0，0，0，100，0，50，0，0）T，昀少的剩余料头为10m.这时2.9m和2.1m的圆钢数正好100个，而1.5m的圆钢数多300个.显然，这不是昀优解，为什么会出现误差呢？仔细观察一下会发现，原因出现在方案4的剩余料头为零，求解过程中目标函数昀小对它失去了作用.由此提示我们，在实际使用线性规划解决问题时，隐含的逻辑错误往往很难发现，必须进行解的分析才能够找出问题.3、（多阶段投资问题）某企业现有资金200万元，计划在今后5年内给A，B，C，D，4个项目投资。根据有关情况的分析得知：项目A：从第一年到第五年每年年初都可进行投资，当年末就能收回本利110%；项目B：从第一年到第四年每年年初都可进行投资，当年末能收回本利125%，但是要求每年昀大投资额不能超过30万元；4项目C：若投资则必须在第三年年初投资，到第五年末能收回本利140%，但是限制昀大投资额不能超过80万元；项目D：若投资则需在第二年年初投资，到第五年末能收回本利155%，但是规定昀大投资额不能超过100万元；根据测定每万元每次投资的风险指数为：项目A为1，项目B为3，项目C为4，项目D为5.5.问题：（1）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为昀大？（2）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上保证其投资的总风险系数昀小？解:首先考虑问题（1）：1）确定决策变量.本题是一个连续投资的问题，由于需要考虑每年年初对不同项目的投资数，为了便于理解，建立双下标决策变量.设ijx（=i1，2，3，4，5；=j1，2，3，4）表示第i年初投资于项目A（1=j）、项目B（2=j）、项目C（3=j）、项目D（4=j）的金额.根据题意，我们建立如下决策变量：第一年年初第二年年初第三年年初第四年年初第五年年初项目A11x21x31x41x51x项目B12x22x32x42x项目C33x项目D24x2）考虑约束条件.由于项目A的投资当年末就可以收回本息，因此在每一年的年初必然把所有的资金都投入到各项目中，否则一定不是昀优的.下面我们分年来考虑：第一年年初：由于只有项目A和项目B可以投资，又应把全部200万元资金投出去，于是有2001211=+xx第二年年初：由于项目B要次年末才可收回投资，故第二年年初的资金只有第一年年初对项目A投资后，在年末收回的本利110%11x，而投资项目为A，B和D，于是有：112422211.1xxxx=++整理后得：01.124222111=+++−xxxx第三年年初：年初的资金为第二年年初对项目A投资后，在年末收回的本利110%21x以及第一年年初对项目B投资后，在年末收回的本利125%12x.可投资项目有A，B和C，于是有：122133323125.11.1xxxxx+=++整理后得：025.11.13332311221=+++−−xxxxx第四年年初：年初的资金为第三年年初对项目A投资后，在年末收回的本利110%31x以及第二年年初对项目B投资后，在年末收回的本利125%22x.可投资项目只有A和B，于是有：2231424125.11.1xxxx+=+整理后得：025.11.142412231=++−−xxxx第五年年初：年初的资金为第四年年初对项目A投资后，在年末收回的本利110%41x以及第三5年年初对项目B投资后，在年末收回的本利125%32x.可投资项目只有A，于是有：32415125.11.1xxx+=整理后得：025.11.1513241=+−−xxx其他的还有项目B，C，D的投资限制以及各决策变量的非负约束：项目B的投资限制：302≤ix（=i1，2，3，4）项目C的投资限制：8033≤x项目D的投资限制：10024≤x各决策变量的非负约束：1ix，2jx，33x，024≥x（=i1，2，3，4，5；=j1，2，3，4）3）建立目标函数.问题要求在第五年末公司这200万元用于4个项目投资的运作获得本利昀大，而第五年末的本利获得有4项：第五年年初对项目A投资后，在年末收回的本利110%51x；第四年年初对项目B投资后，在年末收回的本利125%42x；第三年年初对项目C投资后，在年末收回的本利140%33x；第二年年初对项目D投资后，在年末收回的本利155%24x.于是得到目标函数为：2433425155.14.125.11.1xxxxz+++=根据上面的分析得到线性规划模型：max2433425155.14.125.11.1xxxxz+++=s.t.2001211=+xx01.124222111=+++−xxxx025.11.13332311221=+++−−xxxxx025.11.142412231=++−−xxxx025.11.1513241=+−−xxx302≤ix(=i1，2，3，4)8033≤x10024≤x1ix，2jx，33x，024≥x（=i1，2，3，4，5;=j1，2，3，4）考虑问题（2）：据题意，问题（2）的决策变量设置与问题（1）的设置1）完全相同；而问题（2）的约束设置除与问题（1）的设置2）完全相同外，还增加一约束，就是考虑要使第五年末拥有资金的本利在330万元上，即33055.14.125.11.124334251≥+++xxxx问题（2）的主要区别在于目标不同，是要使得第五年年末拥有资金的本利在330万元的基础上保证其投资的总风险系数为昀小.因此，目标函数为各年各项目的风险系数之和，而风险系数等于投资数乘以相应风险指数.于是得到下列目标函数：24334232221251413121115.54)(3)(xxxxxxxxxxxz++++++++++=综合以上分析，问题（2）的线性规划模型为：min24334232221251413121115.54)(3)(xxxxxxxxxxxz++++++++++=6s.t.2002111=+xx01.124222111=+++−x