优化模型

优化模型一般来说，大学生数学建模竞赛用到的优化模型包括数学规划（线性与非线性规划）、组合优化、网络优化、动态规划、随机规划等，竞赛题目涉及这方面的内容还是比较多的，请看表9.1。本节重点讨论数学规划和动态规划。即在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题。我们所说的数学规划通常是指单目标规划问题，还有一类应用更广泛的多目标规划问题，即目标函数至少两个以上。线性规划：若目标函数厂和约束函数hi（i-l，2，…，Z）、9i(j=1，2，…，77z)都是线性函数。整数规划：若决策变量z的分量部分或全体都是整数的线性规划。非线性规划：若目标函数，和约束函数hi（i-l，2，…，Z）、9i(j=l，2，…，优)中至少有一个函数是非线性函数。数学规划问题举例9.2.1下料问题制造某种产品，需要A、B、C三种轴件，其规模和数量如表9.2所示。各类轴件都用5.5m长的同一种圆钢下料。若计划生产100台机床，最少要用多少根圆钢？(1)问题分析首先，应当确定哪种切割模式是可行的。所谓一个切割模式是指按照需要在圆钢上安排切割的一种组合。例如我们可以将5.5m长的圆钢切割成一个B种轴件和一个C种轴件，余料为2.2m;或者将5.5m长的圆钢切割成一个A种轴件和一个B种轴件，余料为0.3m。显然，可行的切割模式是很多的。其次，应当确定哪种切割模式是合理的。通常假设一个合理的切割模式的余料不应当大于或等于任何一种轴件的长度。例如：将5.5m长的圆钢切割成一个B种轴件和一个C种轴件，余料为2.2m，显然，余料还可以切割成一个B种轴件或者一个C种轴件，因此这种切割模式是不合理的；再如将5.5m长的圆钢切割成一个A种轴件和一个B种轴件，余料为o．3m，显然余料不可能再切割成任何一种轴件，因此这种切割模式是合理的。在这种合理性假设下，切割模式一共有五种，如表9.3所示。①决策变量用z：表示按照第z种模式(i-l，2，3，4，5)切割圆锕的根数，显然它们应当是非负整数。②决策目标切割圆钢的总根数最少，目标为tliitnl2=il+z2+13+14+z5(1)③约束条件首先应满足z．为非负整数，即I。≥0(z—l，2，3，4，5)(2)工，∈z(3)同时，为满足各种轴件数量的要求，应有11+z2≥100(4)x1+2r3+xo≥200(5)222+i3+4X4+2xs≥400,(∞(3)模型求解式(1)～式(6)用Matlab编程，命令如下：》a=[-1,-1,0,0,0;-1,0,-2,0,-1;O,-2,-1,-4,-Z];》b=[-100.-200,-400l;》[x,fval]=linprog(c,a,b,aeq,beq.lh,uh).输出结果如下：x-0.0000100.0000100000025.000000000fval一225.0000(4)结果分析根据Matlab软件的计算结果可得：按照模式2切割100根圆钢，按照模式3切割100根圆钢，按照模式4切割25根圆钢，在此情况下：A种轴件的根数为'100×1+100×0+25×O-100根；B种轴件的根数为100XO+100×2+25×0-200根5C种轴件的根数为100×2+100×1+25X4-400根。满足各种轴件数量的约束条件，而且切割圆钢总数为：;,,,;];][0b9.2.5生产计划问题一家制造计算机的公司计划生产两种产品：两种计算机使用相同的微处理芯片，但一种使用27英寸的显示器，而另一种使用31英寸的显示器，除了400000美元的固定费用外，每台27英寸的显示器的计算机花费1950美元，而31英寸的需要花费2250美元。制造商建议每台27英寸显示器的计算机零售价格为3390美元，而31英寸的零售价格为3990美元。营销人员估计，在销售这些计算机的竞争市场上，一种类型的计算机每多销售出一台，它的价格就下降0.1美元。此外，一种类型的计算机的销售也会影响另一种类型的销售：每销售一台31英寸显示器的计算机，估计27英寸显示器的计算机零售价格下降0.03美元；每销售一台27英寸的显示器，估计31英寸的显示器的计算机的价格下降0.04美元。假设制造的所有计算机可以售出，那么该公司应该怎样安排生产计划，才能使利润最大？(1)模型分析这是一个优化问题，目标是使获利最大，要做的决策是如何安排生产计划。即27英寸的显示器的计算机应该生产多少台，31英寸的生产多少台。决策受两个条件的限制：一种类型的计算机每多售出一台，它的价格就下降0.1美元；一种类型的计算机的销售也会影响另一种类型的销售。(2)模型假设①设27英寸显示器的计算器生产x1台，31英寸显示器的计算机生产x2台。②pi为xi的零售价格，R为两种计算机的零售收入，C为计算机制造成本，P为计算机零售的总利润。③制造的所有计算机都可以售出。④每种类型的计算机的零售价格受自身台数以及另一种类型台数的影响，当两种类型的计算机的台数已经确定时，则两种类型的计算机的零售价格也被确定。(3)模型建立约束条件：p1=3390-O.lxl-0.03x2P2=3990-O.04xl-0.1x2xl≥0，x2≥O两种计算机的零售总收入：R=p1x1+p2x2两种计算机的制造成本：C=400000+1950x1+2250x2于是，所求目标函数为使获利最大：40000007.01.017401.0144021222211xxxxxxCRP(4)模型求解由于目标函数是非线性方程，故将该模型输入LINGO软件求解。输出结果为：x1=4736，x2=7063，即生产4736台27英寸显示器的计算机，7063台31英寸显示器的计算机可使获利最大。9.2.6战术决策模型某战略轰炸机队指挥官得到了摧毁敌方坦克生产能力的命令。根据情报，敌方有四个生产坦克部件的工厂，位于不同地方。只要破坏其中任一工厂的生产设施就可以有效地停止敌方坦克的生产。根据分析，执行该任务的最大因素是汽油短缺，为此项任务只能提供48000加仑汽油。而对于任何一种轰炸机来说，不论去轰炸哪一个工厂都必须有足够往返的燃料和100加仑备余燃料。该轰炸机队现有重型和中型两种轰炸机，其燃油消耗量及数量见表9.6。编号飞机类型每千米耗油量飞机架数1重型1/2482中型1/332试问：指挥官应向四个工厂派遣每种类型的飞机各多少架去执行任务才能使成功的概率最大？先建立模型。设Xij为派遣第i型飞机去第j个工厂执行任务的飞机数量i=l，2；j=l,2,3,4(1)目标函数我们的目标是使至少摧毁一个工厂的概率最大。这相当于不摧毁任何工厂的概率最小，假设用Q代表这个概率，则14)0251(1312)0151()20.01(11)0101(xxxQx所以目标函数为minQ。(2)约束条件燃料限制：2540224802245021211xx飞机数量限制：3241xj变量的非负限制：4,3,2,1;2,1,0jixn9.2.7投资决策问题某企业有理个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金A元，投资于第i(i=l，2，…，咒)个项目需花资金ai元，并预计可收益bi元。试选择最佳投资方案。先建立模型。设投资决策变量为：资第i个项目zi一{l羹喜票鋈资第i个项目聍托则投资总额为∑口ixi，投资总收益为∑bixi。因为该公司至少要对一个项目i-li-l投资，并且总的投资金额不能超过总资金，故有限制条件：Axaiini10另外，由于xi（i-l，2，…，咒）只取值O或1，所以还有zf(1～zi)一0，i一1，2，…，以最佳投资方案应是投资额最小而总收益最大的方案，’所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为：另外，由于xi（i-l，2，…，咒）只取值O或1，所以还有zf(1～zi)一0，i一1，2，…，以最佳投资方案应是投资额最小而总收益最大的方案，’所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为：nixxiAxatsiiii,,2,1,0)1(10..问题：如何用多目标规划来建模呢？9.2.8海洋运输问题某航运公司承接了一项将客户停放在港口等待运输的N种货物运往目的地的业务。设航运公司运输单位货物i的收益为ci（元／t），货船能够装载的货物的质量限制为W(t)，相应的容积限制为V(1T13)。设ai是单位货物i所占的容积(m3/t)，bi是货物i可提供的最大数量(t)。问如何确定货船的装载方案，使航运公司获利最大？设xi(i=l，2，…，N)是货船装载货物i的数量，货物i的日平均装船速度为wi(t)，货物的日泊位费为qi，货船在海上航行时的日费用为q2，同时假定航行距离为d，航行速度为口，那么货船的旅行时间为装船时间和航行时间两部分之和，表示为LVdwxTiiNi1货船从该项运输服务中所获得的净收益为vdqzvixqCixpiNiNii2111目标是期望单位时间内的平均利润即净收益率最大，从而得到如下线性规划模型NibxvxaiWxtsTpziiiiNii,,2,1,01..max1