运筹学模型

《运筹学模型》由会员分享，可在线阅读，更多相关《运筹学模型（36页珍藏版）》请在金锄头文库上搜索。

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

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

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

4、局问题各种农作物在不同土壤上单位面积产量不一样，如何合理安排各种作物在各种不同土壤上的种植面积，达到因地制宜，在完成种植计划的前提下，使总产量最多。这是作物布局问题。将某几个地3方出产的原料，集中到某几个地方加工成成品，然后再运到某几个成品需要地。有些地方可能既是原料出产地，又是成品需要地，也是成品加工地。因各地间运费不同，产品加工费不同，设厂条件不同，应在什么地方设厂，规模多大，才能满足成品需要地的需要，又使费用(包括运费、加工费)最低。这是工厂布局问题。(六) 分派问题n 件工作给 n 个人去做，而各人对做各种工作的效率不同，问应如何合理分派，才能使完成全部工作的总工时最少。类似的问题还有

5、作物的种植安排、机床加工零件任务的分配问题等。在经济领域运用数学方法作为分析经济活动、提高经济效益的一种手段是当今经济管理工作不可忽缺的重要工具。线性规划在这方面有着独特的作用。早在 20 世纪 30 年代末 40 年代初，康托洛维奇()和希奇柯克(Hitchcock) 等在生产组织和运输问题等方面就开始研究应用线性规这一数学方法；后来，在 40 年代末又由旦次基(Dantzig)等人提出了单纯形方法并从理论上给线性规划奠定了基础。我国也在建国初期就开始应用线性规划的方法。如东北的一个物资调运小组，就创造了一个物资调运的图上作业法；并经过中国科学院数学研究所的同志给予理论上证明，在全国推广应用

6、，成效显著，对我国交通运输工作作出了重大贡献。随着电子计算机的不断发展，计算能力的大大提高，使这一数学方法在经济活动中不仅提供了可能，而且迅速发展。1951 年国际水平只能解约束条件为 104个方程的线性规划问题，到了 1963 年就能解 1000-10000 个方程的线性规划问题了。另一面，从时间上看，解一个 67 个方程的线性规划问题，1956 年要一个小时，到 1963 年只要 28 秒钟。现在，不但解题规模大，速度快。而且有专用的软件。以下介绍几个典型的实际问题。(一) 运输问题设有两个砖厂 A1、A2。其产量分别为 23 万块和 27 万块。它们生产的砖供应 B1、B2、B3 三个工

7、地。其需要量分别为 17 万块、18 万块和 15 万块。而各自产地到各工地的运价列表如下(见表 1-1)：表 1-1运价 工地(元/万块)砖厂B1 B2 B3A1 50 60 70A2 60 110 160应如何调运，才使总费用最省？解 设 表示由砖厂 运往工地 砖的数量(单位：万块, ijxiABji=1,2;j=1,2,3),例如 表示由砖厂 A1 运往工地 B1 砖的数量等等。现1列表如下(见表 1-2)表 1-2运价(元) 工/ 万块 地砖厂1B 2B 3B 发 量1A1x12x 13x 2352A 21x 2x 23x 27收 量 17 18 15 50因为由砖厂 A1 运往三个工

8、地砖的总数应为 A1 的产量 23 万块，即： 112132xx+=同样由砖厂 A2 运往三个工地砖的总数应为 A2 的产量 27 万块，即： 212237xx+=另一方面，两个砖厂运往 B1 工地的砖的数量应等于 B1 的需要量 17 万块，即： 1217x+=同理可得： 1223815x+=因此，调运方案就是满足下面约束条件的一组变量的值；1213,223, ,xx6约束条件 12132112213378501,;,23ijxxxij显然，可行的方案有很多个。现在的问题是要在这很多个方案中，找一个运费最小的方案，即：求一组变量 的值，使它满足1213223xx、 、 、 、 、约束条件 1

9、21231237850,2;1,3ijxxxij并使目标函数的值1121321223506706016sxxxx=+最小（即总运费最少）一般地，设某种物资有 m 个产地：A1, A2,Am, 联合供应 n个销地：B1, B2, Bn。各产地产量 (单位：吨) ，各销地销量 (单位：吨)，各产地至销地单位运价 (单位：元/吨 )如表 13 所示：表 1-37销地单价(元 /吨)产地 1B2nB 产量(吨)1A2m 1c21nc 2 1mc2mnc 1a 2 ma销量(吨) bb表中： 表示产地 的产量 (i=1，2， ，m)；iaiA表示销地 的销量 (j=1，2， n)；jbjB表示 间的单位

10、运价 (元/吨) ijc,ij(i=1， 2， m；j=1 ， 2，n)。向应如何调运，才使总运费最少？解 假定产销平衡 （即 ） 。设 表示由产地11mnijijabijx运往销地 的物资数 (i=1，2，m； j=1，2，n)。那么，iAjB上述运输问题的数学模型为：求一组变量 (i=1，2，m；j=1 ，2，n)的值使它满ijx足8约束条件 1212121122120,1,2,nmmnnmnijxxaxxabxxbijn；并使目标函数 的值最小。112mscxcx如果运输问题中，没有产销平衡这一限制，当产大于销时(即)，这一问题的数学模型应为：11mnijijab求一组变量 (i=1，2

11、，m；j=1 ，2，n)的值，使它jx满足：约束条件 111,2,0,21,2nijijmijjiijxabnxmj；并且使目标函数 的值最小。1nijjiscx(二) 布局问题作物布局问题，某生产队要在 n 块地上，种值12,B9m 种作物。各块土地亩数、各种作物计划播种面积及12,A各种作物在各块地上的单产(每亩的产量)如表 14 所示，问应如何合理安排种植计划，才使总产量最多。这里假 定 (即计划播种总面积等于土地面积)。11mnijijab表 1-4表中： 表示作物 的播种面积 (i=1，2，m)；iaiA表示土地 的亩数 (j=1，2，n)；jbjB表示在土地 上种植作物 的单产数

12、ijcj iA(i=1， 2，m；j=1，2，n )。解 设 为土地 种植作物 的亩数ijxjBiAi=1，2， ，m；j=1 ，2，n)，那么作物布局问题的数学模型为：求一组变量 （i=1，2， ，m；j=1，2，n)的值，使它满jx足约束条件单产 土地(公斤/亩) 作物 1B2nB种植面积(亩)1A2m 1c21nc 2 1mc2mnc 1a 2 ma土地亩数 bb10 111,21,2012nijij i imijjij jijxamAAxbnB Bximjn在 各 块 地 上 种 植 作 物 的 总 亩 数 ， 应 等 于 的 计 划 播 种 数在 土 地 上 种 植 各 种 作 物

13、的 总 亩 数 ， 应 等 于 的 面 积， ， ， ； ， ， ，种 植 数 不 能 为 负 数并使目标函数 的值最大。(总产量最多)1nmijjiScx这一数学模型和前面运输问题的数学模型相同。具有这杆数学模型的问题还有机床加工零件的问题等。我们称这类问题为康-希问题，或统称为运输问题。(三 ) 分派问题设有 n 件工作 分派给 n 个人 去做，每12,nB12,nA人只做一件工作且每件工作只分派一人去做。设 完成 的工时为ijB(i，j=1 ，2， n)。问应如何分派才使完成全部工作的总工时ijc最少。解 设 为 分派给 的情况： 分派给 时， =1；ijxjBiAjBiAijx不分派给

14、 时 =0(i，j=1，2，n)。那末这一问题的数学模型iAij为：求一组变量 (i，j=1，2，n)的值，使它满足x11约束条件 111,21,20,1,2nijinijjijxnxnxijn每 件 工 作 只 分 派 给 一 人 去 做每 人 只 做 一 件 工 作或 每 人 对 每 件 工 作 只 有 做 与 不 做 两 种 情 况并且使目标函数 的值最小。1nijijscx(完成全部工作的总工时最少)分派问题是运输问题的特例。因为变量只取 0 和 1，所以又称它为01 规划问题。(四) 生产组织与计划问题设 用 种原料，可以生产 种产品。现12,mA12,nB有原料数、每单位产品所需原料数，及每单位产品可得利润数如表15 所示。问应如何组织生产才能使利润最大？表 15单位产品 产品所需原料原料 1B2n现有原料1A2 c1c 212n 1a212解 设 为生产产品 (j=1，2，n ) 的计划数。这一问题jxB的数学模型为：求一组变量 (j=1，2，n)的值，使它满足x约束条件 11,0,2nijij i i ijcamAAaxn生 产 各 种 产 品 所 需 原 料 的 总 数 不 能 超 过 的 现 有 数各 种 产 品 计 划 数 不 能 为 负 数并且使目标函数 的值最大(总利润最多)。1njjsbx(五) 合理