2022年运筹学模型借鉴 .pdf

《2022年运筹学模型借鉴 .pdf》由会员分享，可在线阅读，更多相关《2022年运筹学模型借鉴 .pdf（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 运筹学模型运筹学发展至今已有五十多年的历史，其作用是为决策者在作决策时提供科学依据。运筹学在生产管理、工程技术、军事科学、科学试验、经济和社会科学中都有着极其广泛的应用。运筹学的分支很多，我们只介绍数学建模中常见的：线性规划、非线性规划、库存、决策、对策和动态规划等几个方面的几个数学模型。第一节线性规划问题的数学模型在生产管理、工程投术、交通运输以及工商贸易等各项经济活动中，都有提高经济效益，做到耗费较少的人力物力，创造出较多经济效益的问题。提高经济效益可以通过两种途径：一种是技术方面的各种改进，改革生产工艺，使用新设备和新材料等。另一种是改进计划和生产管理安排，合理安排人力物力，合理组织

2、生产过程，在条件不变的情况下，统筹安排，使总的经济效益最好。后者就是运筹学研究的主要内容。线性规划是运筹学中研究较早、发展较快、应用较广、比较成熟的一个分支。它研究的问题主要有两类：一类是当一项任务确定后，如何统筹安排，尽量做到用最少的人力物力资源去完成这一任务。二是已有一定数量的人力物力资源，如何安排使用它们，使得完成任务最多。其实这两类问题是一个问题的两个方面，就是所谓寻求整个问题的某个整体指标最优的问题。在经济领域中，这类问题特别多。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 36 页 -2(一)运输问题在某个区域内，有某种产品的产地与销地若干个，把这种产品从各个产地调

3、运到各个销地，调运方案可以很多，应如何组织调运，才能使总的费用或运输量(即总的运行吨公里数)最少。(二)生产的组织与计划问题一个工厂或车间有各种不同类型的车床各若干台，各种不同类型车床生产各种零件的效率不同，在一个生产周期，应如何安排各车床的生产时间，使得成套的产品总量最大。类似的还有劳动力的安排问题(三)合理下料问题在加工中需要将某种条材或板材下不同规格的毛坯，各种毛坯的数量也可能不同，应如何选取合适的裁法，使毛坯数量符合要求，并且使总料头最少(即所用原材料最少)。(四)配料问题在食品、化工、冶炼等企业，常常用几种原料，制成达到含有一定成分的产品，而这些不同原料价格不同，应如何决定配料的方案

4、，才能使生产的产品所含成分合乎要求，而产品的成本最低。(五)布局问题各种农作物在不同土壤上单位面积产量不一样，如何合理安排各种作物在各种不同土壤上的种植面积，达到因地制宜，在完成种植计划的前提下，使总产量最多。这是作物布局问题。将某几个地方出产的原料，集中到某几个地方加工成成品，然后再运到某几个成品需名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 36 页 -3 要地。有些地方可能既是原料出产地，又是成品需要地，也是成品加工地。因各地间运费不同，产品加工费不同，设厂条件不同，应在什么地方设厂，规模多大，才能满足成品需要地的需要，又使费用(包括运费、加工费)最低。这是工厂布局问题。

5、(六)分派问题n 件工作给 n 个人去做，而各人对做各种工作的效率不同，问应如何合理分派，才能使完成全部工作的总工时最少。类似的问题还有作物的种植安排、机床加工零件任务的分配问题等。在经济领域运用数学方法作为分析经济活动、提高经济效益的一种手段是当今经济管理工作不可忽缺的重要工具。线性规划在这方面有着独特的作用。早在 20世纪 30 年代末 40年代初，康托洛维奇()和希奇柯克(Hitchcock)等在生产组织和运输问题等方面就开始研究应用线性规这一数学方法；后来，在40 年代末又由旦次基(Dantzig)等人提出了单纯形方法并从理论上给线性规划奠定了基础。我国也在建国初期就开始应用线性规划的

6、方法。如东北的一个物资调运小组，就创造了一个物资调运的图上作业法；并经过中国科学院数学研究所的同志给予理论上证明，在全国推广应用，成效显著，对我国交通运输工作作出了重大贡献。随着电子计算机的不断发展，计算能力的大大提高，使这一数学方法在经济活动中不仅提供了可能，而且迅速发展。1951年国际水平只能解约束条件为10 个方程的线性规划问题，到了 1963 年就能解 1000-10000个方程的线性规划问名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 36 页 -4 题了。另一面，从时间上看，解一个 67 个方程的线性规划问题，1956年要一个小时，到 1963年只要 28 秒钟。现在

7、，不但解题规模大，速度快。而且有专用的软件。以下介绍几个典型的实际问题。(一)运输问题设有两个砖厂 A1、A2。其产量分别为 23 万块和 27 万块。它们生产的砖供应 B1、B2、B3 三个工地。其需要量分别为17 万块、18万块和 15 万块。而各自产地到各工地的运价列表如下(见表 1-1)：表 1-1 运价工地(元/万块)砖厂B1 B2 B3 A1 50 60 70 A2 60 110 160 应如何调运，才使总费用最省？解设ijx表示由砖厂iA运往工地Bj砖的数量(单位：万块,i=1,2;j=1,2,3),例如11x表示由砖厂 A1 运往工地 B1 砖的数量等等。现列表如下(见表 1-

8、2)表 1-2 运价(元)工/万块地砖厂1B2B3B发量1A11x12x13x23 2A21x22x23x27 收量17 18 15 50 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 36 页 -5 因为由砖厂 A1 运往三个工地砖的总数应为A1 的产量 23 万块，即：11121323xxx+=同样由砖厂 A2 运往三个工地砖的总数应为A2 的产量 27 万块，即：21222327xxx+=另一方面，两个砖厂运往 B1 工地的砖的数量应等于B1 的需要量17 万块，即：112117xx+=同理可得：122213221815xxxx+=+=因 此，调 运 方 案 就 是 满

9、足 下 面 约 束 条 件 的 一 组 变 量111213,212223,xxxxxx的值；约束条件1 11 21 32 12 22 31 12 11 22 21 32 32 32 71 71 81 501,2;1,2,3ijxxxxxxxxxxxxxij显然，可行的方案有很多个。现在的问题是要在这很多个方案中，找一个运费最小的方案，即：名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 36 页 -6 求一组变量111213212223xxxxxx、的值，使它满足约束条件111213212223112112221323232717181501,2;1,2,3ijxxxxxxxxxx

10、xxxij并使目标函数11121321222350607060110160sxxxxxx=+的 值最小（即总运费最少）一般地，设某种物资有 m 个产地：A1,A2,Am,联合供应 n 个销地：B1,B2,Bn。各产地产量(单位：吨)，各销地销量(单位：吨)，各产地至销地单位运价(单位：元/吨)如表 13 所示：表 1-3 销地单价(元/吨)产地1B2B,nB产量(吨)1A2AmA11c12c,1nc21c22c,2nc,1mc2mc,mnc1a2ama销量(吨)1b2b,nb表中：ia表示产地iA的产量(i=1，2，,，m)；jb表示销地jB的销量(j=1，2，,n)；名师资料总结-精品资料欢

11、迎下载-名师精心整理-第 6 页，共 36 页 -7 ijc表示,ijA B间的单位运价(元/吨)(i=1，2，,m；j=1，2，,，n)。向应如何调运，才使总运费最少？解假定产销平衡（即11mnijijab）。设ijx表示由产地iA运往销地jB 的物资数(i=1，2，,，m；j=1，2，,，n)。那么，上述运输问题的数学模型为：求一组变量ijx(i=1，2，,，m；j=1，2，,，n)的值使它满足约束条件1 11 2112 12 222121121111222221201,2,1,2,nnmmmnmmmnnmnnijxxxaxxxaxxxaxxxbxxxbxxxbximjn；并使目标函数11

12、111212mnmnsc xc xcx的值最小。如果运输问题中，没有产销平衡这一限制，当产大于销时(即11mnijijab)，这一问题的数学模型应为：求一组变量ijx(i=1，2，,，m；j=1，2，,，n)的值，使它满足：名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 36 页 -8 约束条件111,2,1,2,01,2,1,2,ni jijmi jjiijxaimxbjnximjn；并且使目标函数11nmijijjisc x的值最小。(二)布局问题作物布局问题，某生产队要在12,nB BBn 块地上，种值12,mA AAm 种作物。各块土地亩数、各种作物计划播种面积及各种作物

13、在各块地上的单产(每亩的产量)如表 14 所示，问应如何合理安排种植计划，才使总产量最多。这里假 定11mnijijab(即计划播种总面积等于土地面积)。表 1-4 单产土地(公斤/亩)作物1B2B,nB种植面积(亩)1A2AmA11c12c,1nc21c22c,2nc1mc2mc,mnc1a2ama土地亩数1b2b,nb名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 36 页 -9 表中：ia表示作物iA的播种面积(i=1，2，,，m)；jb表示土地jB的亩数(j=1，2，,，n)；ijc表示在土地jB上种植作物iA的单产数(i=1，2，,，m；j=1，2，,，n)。解设ijx

14、为土地jB种植作物iA的亩数 i=1，2，,，m；j=1，2，,，n)，那么作物布局问题的数学模型为：求一组变量ijx（i=1，2，m；j=1，2，,，n)的值，使它满足约束条件111,2,1,2,01212nijijiimijjijjijxaimAAxbjnBBximjn在各块地上种植作物的总亩数，应等于的计划播种数在土地上种植各种作物的总亩数，应等于的面积，；，种植数不能为负数并使目标函数11nmijijjiSc x的值最大。(总产量最多)这一数学模型和前面运输问题的数学模型相同。具有这杆数学模型的问题还有机床加工零件的问题等。我们称这类问题为康-希问题，或统称为运输问题。(三)分派问题设

15、有 n 件工作12,nB BB分派给 n 个人12,nA AA去做，每名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 36 页 -10 人只做一件工作且每件工作只分派一人去做。设iA完成jB的工时为ijc(i，j=1，2，,，n)。问应如何分派才使完成全部工作的总工时最少。解设ijx为jB分派给iA的情况：jB分派给iA时，ijx=1；不分派给iA时ijx=0(i，j=1，2，,，n)。那末这一问题的数学模型为：求一组变量ijx(i，j=1，2，,，n)的值，使它满足约束条件1111,2,11,2,01,1,2,nijinijjijxjnxinxi jn每件工作只分派给一人去做每

16、人只做一件工作或每人对每件工作只有做与不做两种情况并且使目标函数11nnijijijsc x的值最小。(完成全部工作的总工时最少)分派问题是运输问题的特例。因为变量只取0 和 1，所以又称它为01 规划问题。(四)生产组织与计划问题设 用12,mA AA种原料，可以生产12,nB BB种产品。现有原料数、每单位产品所需原料数，及每单位产品可得利润数如表15 所示。问应如何组织生产才能使利润最大？名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 36 页 -11 表 15 解设jx为生产产品jB(j=1，2，,，n)的计划数。这一问题的数学模型为：求一组变量jx(j=1，2，,，n

17、)的值，使它满足约束条件11,2,01,2,ni jjijiiijcxaimAAaxjn生产各种产品所需原料的总数不能超过的现有数,各种产品计划数不能为负数并且使目标函数1njjjsb x的值最大(总利润最多)。(五)合理下料问题设用某原材料(条材或板材)下零件12,mA AA的毛坯。根据过去经验在一件原材料上有12,nB BB种不同的下料方式，每种下料方式可得各种毛坯个数及每种零件需要量如表16 所示。问应怎样安排下料方式，使得既能满足需要，用的原材料又最少。解设用jB种方式下料的原材料数为jx，则这一问题的数学模单位产品产品所需原料原料1B2B,nB现有原料1A2AmA11c12c,1nc

18、21c22c,2nc,1mc2mc,mnc1a2ama单位产品可得利润1b2b,nb名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 36 页 -12 型为：求一组变量jx(j=1，2，,，n)的值，使它满足约束条件11,2,0,1,2,ni jjiiijjc xainAaxjn所下的零件总数不能少于整数各种方式下料的原材料数不能是负数、分数并使目标函数1njjsx的值最小。(所用原材料数最少)表 1-6(六)配料问题设用 n 种原料12,nB BB制成具有 m 种成分12,mA AA的产品，其所含各成分需要量分别不低于12,ma aa。各种原料的单价，以及各种原料所含成分的数量

19、如表17 所示。问应如何配料，才能使产品成本最低。各方式下的下料方零件个数式零件名称1B2B,nB零件需要量1A2AmA11c12c,1nc21c22c,2nc,1mc2mc,mnc1a2ama名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 36 页 -13 表 1-7 一单位原料原所含成分的料数量原科所含成分名称1B2B,nB产品所含成分需要量1A2AmA11c12c,1nc21c22c,2nc,1mc2mc,mnc1a2ama单价1b2b,nb解设取原料jB为jx单位(j=1，2，,，n)。这一问题的数学模型为：求一组变量jx(j=1，2，,，n)的值，使它满足约束条件11

20、,2,01,2,nijjijiiijc xa imAAaxjn所有各种原料所含成分的总数应不少于产品对的需要量所取原料不能为负数并且使目标函数1njjjsb x的值最小。(产品成本最低)上面我们建立几个实际问题的数学模型。这些问题是各式各样的，但它们的数学模型却有相同的数学形式。这就是：表示约束条件的数学式子都是线性等式或线性不等式，表示问题最优化指标的目标函数都是线性函数。因为约束条件和目标函数都是线性的，所以我们把具名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 36 页 -14 有这种模型的问题称为线性规划问题。线性规划问题的数学模型的一般形式是：求一组变量jx(j=1，

21、2，,，n)的值，使其满足约束条件1,1,2,01,2,ni jjiiijjaxbbbimxjn或或并使目标函数1njjjsc x的值最小(或最大)。其中ijijabc、(i=1，2，,，m；j=1，2，,，n)为已知量。我们称满足约束条件的一组变量的值0jx(j=1，2，,，n)为线性规划问题的一个 可行解。使目标函数取得最大(或最小)值的可行解称为最优解。线性规划问题的数学模型是描述实际问题的抽象的数学形武。它反映了客观事物数量间的本质规律。建立数学模型可以建立粗一点的模型，也可以建立细一点的模型。建立模型时，要根据问题的要求而定。第二节线性规划问题的标准形式线性规划问题的数学模型的一般形

22、式是：求一组变量12,nx xx的值，使它满足名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 36 页 -15 约束条件1 111 2211112 112 222222112212,0,0,0nnnnmmmnnmmmna xa xa xbbba xa xa xbbbaxaxaxbbbxxx或或或或或或并且使目标函数1122nnsc xc xc x的值最小(或最大)。为了讨论与计算上的方便，我们把线性规划问题化为标准形式。为此，作如下规定。(1)如果第 k 个式子为：1122kkk nnkaxaxaxb则加入变量0n kx，改为：1122kkknnnkka xaxa xxb如果第

23、 e个式子为：1122eeennea xa xa xb则减去变量n ex，改为：1122eeennn eea xa xa xxbn knexx、称为松弛变量。松驰变量在目标函数中的系数为零。(2)如果问题是求目标函数1122nnsc xc xc x的最大值，则化为求目标函数1122nnSSc xc xc x的最小值。(3)如果 对某 变量jx没 有 非负 限 制，则 引 进两 个非 负变 量,0,0jjxx，令,jjjxxx代入约束条件和目标函数中，化为对全部变量都有非负限制。名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 36 页 -16 这样，我们可以把线性规划问题写成标准

24、形式如下：求一组变量12,nx xx的值，使它满足约束条件1 111 2212 112 22221122120,0,0nnnnmmmnnmna xa xa xba xa xa xba xaxaxbxxx并且使目标函数1122nnsc xc xc x的值最小。利用向量和矩阵的符号，线性规划问题可以简记为：mins=cx 0Axbx或mins=cx 10njjjx Pbx其中12,ncc cc111212122212nnmmmnaaaaaaAaaa12mbbbb名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 36 页 -17 12nxxxx12jjjmjaaPa(j=1,2,n)第

25、三节线性规划问题解的性质一.几个概念1.可行解、基础可行解、最优解、基础最优解设线性规划问题mins=cx0Axbx我们把满足约束条件的解010020nxxxx称为线性规划问题的 可行解若0 x=0，或0 x的非零分量所对应的系数列向量线性无关时，称可行解0 x为基础可行解。使目标函数取最小值的可行解，称为最优解。使目标函数取最小值的基础可行解，称为基础最优解。2.凸集名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 36 页 -18 若连接 n 维点集 S中任意两点12,xx的线段仍在 S内，则称 S为凸集。即，若12(1)(2)1,01,x xxxxS xSS则称 S为凸集。

26、例如，矩形、三角形、园、四面体等都是凸集。园环、空心球等都不是凸集。3.极点 若凸集 S中的点 x，不能成为 S中任何线段的内点，则称 x 为 S 有极点。即，若对于任意两点12,xs xs不存在 01,使121xxx,则称 x 为 S的极点。例如，矩形、三角形、四面体的顶点，园周上的点等都是极点。二.线性规划问题解的性质对于线性规划问题解的性质我们仅写出以下几个定理，不作证明。定理 1线性规划问题的可行解集为凸集。即连接线性规划问题任意两个可行解的线段上的点仍是可行解。定理 2 可行解集 S中的点 x 是极点的必要充分条件为x 是基础可行解。定理 3最优值可以在极点上达到。第四节两个变量的线

27、性规划问题的图解法为了使线性规划问题的基本理论提供较直观的几何说明，我们介绍两个变量的线性规划问题的图解法。例 1 求12xx、的值，使它们满足名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 36 页 -19 约束条件12121243280,0 xxxxxx并且使目标函数1225sxx的值最大。解我们把12xx、看成坐标平面上点的坐标，那么满足约束条件中每一亇不等式的点集就是一个半平面。因为约束条件是由5 个不等式组成的，所以满足约束条件的点集是五个半平面的相交部分。即图 41 中凸多边形 OABCD 上任何一点的坐标，都同时满足约束条件的五个不等式；凸多边形外的任何一点的坐标

28、都不能同时满足这五个不等式。所以凸多边形 OABCD 上的每个点的坐标都是这个线性规划问题的可行解。而凸多边形上点的全体构成这一线性规划问题的可行解全体，称为 可行解集。我们再在全体可行解中，找一个最优解，就是找使目标函数值最大的可行解。为此，给定s一个值，比如 s=4，那么12254xx是坐标平面上一条直线。在这直线介于凸区域中的线段上任何一点都使目标函数取值为 4，我们称这样的直线为 等值线。再令目标函数值s 分别为 8、15、19、,作平行直线族，由图41 可以看出，当 s值愈增加，直线离开原点愈远。名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 36 页 -20 因此，

29、这一问题成为：在上列平行线中，找出一条，使与凸多边形 OABCD 相交，而又尽可能地离原点最远。从图 41 中显然可见，经过 B 点的一条即符合要求。即B 点坐标既满足约束条件，又使目标函数取得最大值。解212328xxx得最优解为122,3xx。相应的目标函数的最大值为：S=22+53=19 例 2若把例 1 的目标函数改为122sxx，那么，BC 边上每一点的坐标都是最优解(因为平行直线族中，离原点最远的一条直线1228xx与 BC 边相重台)。因此，最优解有无穷多个，而它们对应的目标函数值都是8(参看图 42)。名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 36 页 -

30、21 例 3求12,x x的值，使它们满足约束条件1212121200,0 xxxxxx并使目标函数1222sxx的值最小。解满足约束条件的点，即图 43 中的凸域 ABCD 是无界的。再令目标函数值分别为16、10、6、2 等，作平行直线族，显见直线离原点愈近时，目标函数值愈小。由图 43 可以看出，s的最小值由C 点达到，而C 点坐标可求得为(1，0)。所以最优解为121,0 xx；相应的目标函数最小值为s=21+0=2。例 4若把例 3 改为使目标函数的值最大，从圆 43 可以看出，因为凸域 ABCD 无界，当平行直线族的直线无限远离原点时，都可以与凸域 ABCD 相交，所以目标函数无上

31、界，因此无最优解。名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 36 页 -22 例 5 求12,x x的值，使它们满足约束条件121212120,0 xxxxxx并且使目标函数1222sxx的值最小。解从图 44 可以看出，同时满足约束条件四个不等式的点不存在，所以没有可行解，当然没有最优解。名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 36 页 -23 从以上几个例子可以把线性规划问题解的情况归结为：有可行解且有唯一最优解，如例1 和例 3；有无穷多最优解，如例2；有可行解但没有最优解，如例4；无可行能，如例5。另外，从前面例子的几何直观表示还可得出下面

32、两个重要结论：(1)线性规划问题的任意两个可行解联线上的点都是可行解。(2)线性规划问题的最优解如果存在，必然可在某个“顶点”达到。第五节非线性规划模型在许多实际问题中，其目标函数和(或)约束条件很用难线性函数表示，如果目标函数或约束条件中，有一个或多个是变量是非线性函数，则称这种规划问题为非线性规划问题。非线性规划问题的数学模型为名师资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 36 页 -24 目标函数m a xm i n fz约束条件01,2,001,2,ijhzimgzjn或,(5.1)其中12,nzx xx是 n 维欧氏空间中的向量(点)。一般说来，求解非线性规划问题比

33、求解线性规划问题困难得多，也不像线性规划问题有单纯形法这一通用解法。非线性规划问题目前还没有适于各种问题的一般算法，各个方法都有自已的特定的适用范围。因而，这是需要人们更深入地去进行研究的一个领域。1.投资决策问题某钢厂准备用5000 万元用于A、B 两个项目的技改投资，设12xx、分别表示分配给项目A、B 的投资，据专家预估，投资项目 A、B 的年收益分别为20和 16。同寸，投资后总的风险损失将随着总 投 资 和 单 项 投 资 的 增 加 而 增 加，已 知 总 的 风 险 损 失 为22212122xxxx。问应如何分配资金，才能使期望的收益最大，同时使风险损失为最小。这个问题有两个指

34、标函数，一个是收益函数，另一个是风险损失函数。一般来说不能同时满足，将期望的收益和风险损失合并在一个目标函数，从而使问题得以简化。该投资决策问题的数学模型为目标函数222121212max20162fzxxxxxx约束条件1121250000,0gzxxxx,(5.2)目标函数中的 0 是权系数，它是事先根据收益和风险损失权衡来名师资料总结-精品资料欢迎下载-名师精心整理-第 24 页，共 36 页 -25 确定。如果=0，表示不考虑风险损失；如果=1，表示收益和风险损失同等重要；而当 取值很大时，表示在目标函数中，主要考虑风险损失要最小，收益可以忽略不计。为简单计，取=1，则数学模型为目标函

35、数222121212max20162fzxxxxxx约束条件1121250000,0gzxxxx,(5.3)这是一个非线性规划问题。2.武器分配问题用 m 组不同类型的兵器，来摧毁 n 个目标，设第 i 组兵器由iN个单位组成，jp表示目标的重要性(或危险性)，ijw表示用第 i 组兵器击中第 j个目标的概率，试问如何分配现有的兵器攻击相应的目标，使击毁目标数的数学期望M 达到最大值。设ijx表示用于攻击第 j 个目标的第 i 类型兵器的数量。击毁目标数的数学期望为1111ijmnxijijjiMpw因此，兵器分配问题的数学模型为目标函数11m a x11ijmnxijijjiMpw名师资料总

36、结-精品资料欢迎下载-名师精心整理-第 25 页，共 36 页 -26 约束条件1,1,2,0,1,2,1,2,ni jijijxNimximjn,(5.4)由上可以看出，兵器分配问题中的目标函数是非线性函数，故该问题是非线性规划问题。3.飞行管理问题1995年全国大学生数学建模竞赛试题A：在约 10000m高空的某边长 160km的正方形区域内，经常有若干架飞机作水平飞行。区域内每架飞机的位置和速度向量均由计算机记彔其数据，以便进行飞行管理，当一架欲进入该区域的飞机到达区城边缘时，记录其数据后，要立即计算并判断是否会与区域内的飞机发生碰撞。如界会碰撞，则应计算如何调整各架(包括新进入的)飞机

37、飞行的方向角，以避免碰撞。现假定条件如不：1)不碰撞的标准为任意两架飞机的距离大于8 km；2)飞机飞行方向角调整的幅度不应超过030；3)所有飞机飞行速度均为每小时800 km；4)进入该区域的飞机在到达区域边缘时，与区域内飞机的距离应在 60 km 以上；5)最多需考虑 6 架飞机；6)不必考虑飞机离开此区域后的状况。请你对这个避免碰撞的飞行管理问题建立数学模型，列出计算步骤，对以下数据进行计算(方向角误差不超过00.01)，要求飞机飞行的方向角调整的幅度尽量小。名师资料总结-精品资料欢迎下载-名师精心整理-第 26 页，共 36 页 -27 设该区域 4 个顶点的坐标为(0，0)，(16

38、0，0)，(160，160)，(0，160)。记录数据为：表 5-1 飞机编号横坐标 X 纵坐标 Y 方向角1 2 3 4 5 新进入150 85 150 145 130 0 140 85 155 50 150 0 243度236度220.5度159 度230 度52 度注：方向角指飞行方向与X 轴正向的夹角。试根据实际应用背景对你的模型进行评价与推广。解为使问题简化，增加以下假设：1)飞机在所定区域内作直线飞行，不偏离航向；2)飞机管理系统发出的转向指令应被飞机立刻扏行，即认为转向是在瞬间完成；3)飞机在区域内不发生意外，如发动机失灵，或其他意外原因迫使飞机改变航向。设 6 架飞机在调整时的

39、方向角为i，调整后的方向角为1,2,6iiii，。又设任意两架飞机在区域内的最短距离为,ijijd,22200000000coscossinsinijiijjiijjdxvtxvtyvtyvt根据题意的要求，飞行管理问题可归结为一非线性规划模型61minii名师资料总结-精品资料欢迎下载-名师精心整理-第 27 页，共 36 页 -28 0,8.301,6,ijiijjidsti jij,(5.5)第六节经济定货量库存模型一个公司或工厂必须考虑购买和库存一定量的商品或原材料。如果一次大批量的购买，必然要造成资金积压并增加库存量。如果小批量购买(多买儿次)，虽然库存费减少了，但是定货费用却增加了

40、，甚至有时出现商品脱销或停工待料而带来损失，如何合理安排定货和适当库存，使得所花总费用最少是值得考虑的。下面讨论经济定货量模型。所谓经济定货量即是使全年(或某个时间区间)的库存和定货总费用达到最小值。假定年需求量(使用量)为已知确定的。1.列表法试探法是求解经济定货量的方法之一，其步骤为：(1)选择一定数目的可能购买的数量方案；(2)确定每种方案的总费用；(3)选出总费用最小的定量，见表6-1。在此例中，年需求量为8000 件，每批定货费用12.5 元，平均库存后保管费用是每年20，每件价值 1 元。由表 6-1 表明，批量为1000 件的方案总费用最少。值得注意的是，在这个总费用最小的方案中

41、，保管费用与定货费用相等。在此例中，碰巧确定了可能的最低费用。如果设有计算年定货次数为8 的方案，就只能在剩下的 6 种方案中进行选择，以求出其中费用最低的解，这就是列表法的缺点。在许多具体事例中，只有在计算了相当大量的方案以后，才能确定可能名师资料总结-精品资料欢迎下载-名师精心整理-第 28 页，共 36 页 -29 的最小总费用方案。表 5-2 年定货次数/次每 次 数 量/件平 均 库 存/件保 管 费 用 计算量/件(每年20)定货费用/元(每批 12.5元)年 总 费 用/元1 2 4 8 12 16 32 8000 4000 2000 1000 667 500 250 4000

42、2000 1000 500 333 250 125 800 400 200 100 66 50 25 12.5 25 50 100 150 200 400 812.5 425 250 200 216 250 425 2.图解法用上述数据可以进行图解，这种图解能够显示出经济定货量问题所涉及的互相对立的各种费用的性质，图6.1表明，总费用曲线呈V型。它表明每年的库存保管和定货两项的总费用开始递减，在保管费用与定货费用相等处达到最低点。然后，随着定货量的增加而递增。我们的目的是在曲线上找出总费用最小的经济定货量。然而要精确地找出这个数值不易，因为曲线的描绘是不精确的。不过在实际中，要求出精确的公司或

43、工厂是很少的，多数是求出近似值，只要误差不太大(一般为 10)就行了。名师资料总结-精品资料欢迎下载-名师精心整理-第 29 页，共 36 页 -30 3.代数法由上可知，总库存费用的最经济点就是库存保管费用等于定货费用的点。这是讨论代数方法的基础，为了导出经济定货量代数模型，令 Q 表示经济定货量或使企业总费用最小的每次定货的最佳件数，C表示每件价值，I 表示年库存保管费用(表示为平均库存价值的百分率)，R 表示年总需求量，S 表示每次定货费用(也可定义为每批生产的准备费用)。因为平均库存量等于定货量的一半即Q/2，每年一件存货保管费为 CI。那么年库存保管费为22QQCICI,(6.1)我

44、们知道：总定货费用=年定货次数每次定货费用。显然，年定货次数等于 R/Q，所以总定货费用为RS/Q。由总库存费用的最经济点为库存保管费用等于定货费用，所以有2QRCISQ名师资料总结-精品资料欢迎下载-名师精心整理-第 30 页，共 36 页 -31 2RSQCI,(6.2)取前面列表法和图解法中同样一组数据，C=1 元，I=20，R=8000件，S=12.5 元，则28000 12.51000120Q件件这与前面两种方法得出的结论是一样的。第七节工厂生产和销售的库存模型对于既是生产型又是销售型的工厂，任务是把进来的原料加工成产品，并把它销售出去。生产就必须库存一定的原材料，销售就要保证库存一

45、定产品。如何确定一个最优的生产周期，使得在单位时间内所花生产费用最小，这是每个工厂的现实问题。下面由简单情况逐步复杂化讨论边生产边销售时的库存问题。第一步考虑仓库只库存产品的简单情形。记 K 表示生产线运转时商品的生产速率(K 为常数)，r(K)表示商品的销售速率，Q 表示库存量仓库的库存以下列方式变化：开始边生产边销售，库存量Q 以速率 Kr 增加，到时刻 t 只销售不生产，Q 以速率 r 减少到时刻 T，Q减少为零。如此为一周期。Qt 关系如图 71 所示。名师资料总结-精品资料欢迎下载-名师精心整理-第 31 页，共 36 页 -32 设 C 表示每开动一次生产线成本，S 表示单位时间每

46、件商品的库存费，W 表示单位时间总费用。问题是如何确定周期T，使单位时间的总费用最小。由上假设有：单位时间成本为C/T，单位时间库存费为SA/T。OPT 的面积 A=Tt(Kr)/2，又有 Kt=rT(一个周期生产的商品等于销售的商品)。则单位时间总费用为22CSACS TCS rTWt KrKrTTTTTK=2Sr KrCTTK记2Sr KrBK则CBTT,(7.1)名师资料总结-精品资料欢迎下载-名师精心整理-第 32 页，共 36 页 -33 由20dWCBdTT,有minCTB,(7.2)代入(7.1)有min2WBC,(7.3)由(7.2)式表明，最优周期与生产成本的平方根成正比，与

47、贮存费的平方根成反比。不经过计算这亇结论是不易看出来的。由于种种原因，最优周期不可能准确得到，这时考虑由于T 的误差引起 W 变大来判断 T 变大好还是变小好。如果 T 被T 代替，问 1+，1()哪个较为有利？由(7.1)和(7.2)有1CWTB TBCTmin11122BCWTfWBC,(7.4)从图 62 中 f()的图形可知，取 比1较有利。名师资料总结-精品资料欢迎下载-名师精心整理-第 33 页，共 36 页 -34 第二步仓库除存放产品外，还存放原料。设一个周期生产所需原料一次备足，即t=0 时，仓库要存放能生产 Kt 件商品的原料，如图6-3 所示。设单位时间每件原料存放费为,

48、S，则单位时间原料存放费为,/S AT，而,2122KtAtKt单位时间总费用应为名师资料总结-精品资料欢迎下载-名师精心整理-第 34 页，共 36 页 -35,2,21122SKtCS rWWBTTTTK令,212SrBBK（B）则11CWBTT,(7.5)可按第一步相同步骤，求得最优周期1minmin1CCTTBB,(7.6)第三步设一次备足P 个周期生产所需的原料，即t=0 时，仓库存入 N=PKt=PrT 件商品所需原料。这时原料存放量的变化如图64所示。P 个周期中原料总存放量是图64 中台阶形面积,A，而,A是以 N 为高,(P1)T+t 为底的矩形面积的一半(注意 N=PrT=PKt)。有,1122NNNrAPTtTrK名师资料总结-精品资料欢迎下载-名师精心整理-第 35 页，共 36 页 -36 则单位时间原料存放费为,121222NNrSTrKS ASrNrTNPTrKrKr rNSTK此时单位时间总费用为,2,22222Sr Krr KrCNWTSTTKKrKrSSCS NTTK,(7.7)如果,SS，最好使 T 尽可能大，即 P=1。当,SS时，得最优值,2CKTr KrSS,2Crtr KrSS,222C rKrSSS NWK,(7.8)对于更复杂的情况，这里不作讨论。名师资料总结-精品资料欢迎下载-名师精心整理-第 36 页，共 36 页 -