线性规划的实际应用模型.doc

目录摘要 -1引言 -2一 线性规划的概念 -3二 线性规划的实际应用 -4（四）体育上的应用 1.合理安排比赛问题 -132.选拔选手问题 -14（五）旅行上的问题:旅行背包问题 -15（六）航空上的问题:航空时间安排问题 -16（七）城市规划的应用:设施布点问题 -18（八）日常生活上的应用 1.食用油的结构优化问题 -192.饮食问题 -21（九）农业上的应用:农业种植问题 -23三 总结及参考文献 -25线性规划的实际应用模型王丽娜（渤海大学数学系 辽宁 锦州 121000 中国）摘要：本文从运筹学的角度分析线性规划的实际应用模型，随着人类社会的进步，科学技术的发展，经济全球化进程的日益加快，线性规划在实际中的应用越来越广泛，主要应用于经济与管理,军事,金融,体育,旅行,航空,城市规划,日常生活,农业九大方面，因此，线性规划作为一门科学已被人们广泛接受，并已日益成为人类社会和经济生活中一种不可或缺的工具。关键词：运筹学 线性规划 分析 模型 Zhe model in practical application of linear programmingWang lina(Department of Mathematics Bohai University Liaoning Jinzhou 121000 China)Abstract:This article analyse the practical application of linear programming from the sight of operational research,with the advancement of human society,the development of science and technology and the faster grogramming has wider application in the practical,has been applied to nine aspects,in econemy,management,military,finance,physical education,travelling,airline,city planning,daily life, agriculture.The examples will be given to show the application in the nine aspects given abo。Key word:operational research ,linaear programming, analy ,model引言线性规划是运筹学的一个重要分支。也是研究较早的，发展较快的,应用较广而比较成熟的一个分支。早在本世纪30年代后期，苏联数学家康特洛维奇为了解决生产组织里的一系列问题，如机器负荷分配，原材料的合理利用等，提出了“解乘数法”，同时，发表了一系列文章，其中的代表作是“生产组织与计划中的数学方法”。 我国从1958年开始用线性规划来解决生产中的问题，取得了一定的效果，特别是在物资调运方面，总结出我国特有的“图上作业法”，运筹学工作者在此基础上作出进一步的发展和提高工作，随着我国四个现代化建设的需要，线性规划得到越来越广泛的普及，从事这方面理论研究和实际应用工作的队伍越来越大。 线性规划所研究的问题主要有两类:一类是当一项任务确定后，如何统筹安排，尽量做到以最少的人力，物力资源去完成；另一类是已有一定数量的人力，物力资源，如何安排使用它们，使完成的任务（或创造的财富，利润）最多？这两类问题实际上是一个问题的两个方面，即所谓寻求整个问题的某个整体指标最优的问题。日常生活，农业，体育，交通，运输，军事，经济与管理决策等领域都有应用，大到一个国家，一个地区，小到一个企业，一个车间，一个班组都有运用线性规划后提高经济效益的例子，本文主要讨论线性规划解决实际问题的应用并总结出一般模型。一.线性规划的概念 (3) 规划问题的数学模型由三个要素组成：（1）变量，或称决策变量，是问题中要确定的未知量，它用以表明规划中的用数量表示的方案，措施，可由决策者决定和控制；（2）目标函数，它是决策变量的函数，按优化目标分别在这个函数前加上max或min；（3）约束条件，指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。如果规划问题的数学模型中，决策变量的取值是连续的，即可以为正数，也可以为分数，小数或实数，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型称为线性规划的数学模型。 假定线性规划问题中含n个变量，分别用x（J=1，2，n）表示，在目标函数中x的系数为c（c通常称为价值系数），x的取值受项资源的限制，用b (i=1,m)表示第i中资源的拥有量，用a表示变量x取值为1个单位时所消耗或含有的第i种资源的数量，通常称a为技术系数或工艺系数。则上述线性规划问题的数学模型可表示为：Max(min)Z=cx+cx+cx (1) s.t. ax+ax+axb ax+ax+axb (2) ax+ax+axbx, x, x0 (3)在上述线性规划的数学模型中，或（1）称为目标函数，或（2）称为约束条件，或（3）称为非负条件，式中，Z为目标函数，x（J=1，n）为决策变量，c, c,c,b,b,b, a, a,a,a,a, ,a, a, a,a都是常数。二. 线性规划的实际应用线性规划在各行各业都有实际应用的典例，下面列举线性规划的实际应用。（一）经济与管理上的应用 经济管理中,如何有效的利用现有人力，物力去完成更多的任或在预定的任务目标下,如何用最少的人力，物力去完成目标,这就是用线性规划在经济与管理方面要解决的具体问题. 1.生产组织与计划问题产品配套问题 (5) 某车间可以用塑料生产以下三种管状产品,有关数据如下表 表1 甲(m)乙(m)丙(m)限值利润(元)233?塑料(kgm)111135工时147405现有丁产品(新产品或用户要求生产的产品),设生产1m需塑料3kg,和工时5h,每米利润为6元,如下表表2甲(m)乙(m)丙(m)丁(m)限值利润(元)2336?塑料(kgm)1113135工时1475405人们发现不仅可以单独出售上述产品,还可以把它们组成套件出售:一种是4乙产品与3丙产品组成一套,利润为27元;另一种是甲,乙,丁产品各1米组成一套,利润为13元,问如何组织生产,如何销售(单独出售多少,成套出售各多少)使总利润最大.解:设四种产品单独销售量为y,y,y,y,两种成套产品销售U,U,这6个决策变量的值求得之后,四种产品的生产量x, x,x,x就可用下式算得:x= y+U x= y+4 U+ Ux = y +3U x= y+ U 把成套的产品作为新产品,第一种是乙,丙两种产品按4:3组合,这种产品记做(乙丙),乙产品4以及丙产品3组成相当于1的(乙丙),因此它需要7(=43)塑料和37(=44+73)个工时,第二种记做(甲乙丁),相当于它1的3(=1+1+1)塑料与10(14+5)个工时,表1与两种成套产品合并成为表3 表3 甲(m)乙(m)丙(m)丁(m)乙丙 (m)甲乙丁(m)限值利润(元)23362713?塑料(kgm)111375135工学建模如下:maxZ=2 y+3 y+3 y+6 y+27 U+13 U s.t. y+ y+ y+3 y+7 U+5 U135 y+4 y+7 y+5 y+37 U +10 U405 y, y, y, y, U, U0因此:最大总利润为402 元,最优的产品结构是;出售两种成套产品,不出售单一品种,(乙丙)产品出售5 套, (甲乙丁)产品出售18 套,于是甲,乙,丙与丁产品生产:产品甲: x = y + U=18.783(m)产品乙: x= y+4 U+ U=42.261(m)产品丙: x= y+3 U =17.609(m)产品丁: x= y+ U=18.783(m)归纳一般模型为：车间生产m 种产品，利润分别a , a , a ，用原料分别为b, b, , b, 工时分别h, h, , h，总用料不超过A，总工时不超过B，问如何组织销售使总利润最大？解：maxZ=ax+ax+ +ax s.t. bx+ bx+ bx Ahx+ hx+ hxB x, x, x02.运输问题产销平衡的运输问题 某部门有3个生产同类产品的工厂,生产由4个销售点出售,各工厂的生产量,各销售点的销售量(假定单位均为t)以及各工厂到各销售点的单位运价(元t)示于表4要求研究产品如何运才能使总运费最小?表4 销地产地B1B2B3B4产量A1 41241116A22103910A38511622销量814121448解:用x表示由第 i个产地运往第 j 个产地的产品数量,即可写出该问题的数学模型:minZ=cx=4x+12x+4x+11x+2x+10x+3x+9x+8x+5x +11x+6xs.t. x+x+x+ x=16x+ x+ x+ x=10x+ x+x+ x=22x+ x+ x=8x+ x+ x=14x+ x+ x=12x+ x+ x=14x 0计算得该运输问题的一个初始解: x=10, x=6, x=2, x=14, x=8其他变量全等于零,即由A1运10单位物品给B3,运6单位物品给B4;由A2运8单位物品给B1,运2单位物品给B3;由A3运14单位物品给B2,运8单位物品给B4,总运费Z=104+611+82+23+145+86=246(元)（二）军事上的应用军事上的运载和分配武器装备等问题都需要用线性规划来解决.例子如下:向运载工具分配武器的问题 (7)四类武器(m=4)需分配到六类运载工具(n=6)上; x是第j类武器运载工具的数量,向运载工具分配武器,需要确定运载工具的总损失为最小的每类运载工具数量,毁伤运载工具的概率见下表5 表5武器运载工具的类型,j123456毁伤第类运载工具的概率,cj0.40.50.20.80.60.3解:有待最优化的目标函数是:y=0.4x+0.5x+0.2x+0.8x+0.6x+0.3x+4x+x=162x+x=10 x+2x+6x=764x+3x+x=24x0 (j=1,2,3,4)解得最优方案为:x=4,x=0,x=16,x=0,x=10,x=8目标函数最小为y=-2.44+0.80+22.8=13.2总结一般模型为：把m 种武器分配到运载工具上，x是第j类武器运载工具的数量，毁伤第j类运载工具的概率为 c,需确定运载工具的总损失最小的每类运载工具的数量，则y=cx+cx+cx ax+ax+ax=A ax+ax+ax=A x0（三）金融行业中的应用 线性规划对金融行业中的金钱投资,运行正常等方面的实际问题的具体解决有重要影响,下面就具体列出线性规划在这类问题中的具体应用:1.银行运行问题 振华银行的四个分理处的投入产出情况如表所示,要求分别确定各分理处的运行是否DEA有效.表6分理处 投入 产出职员数营业面积储蓄存取贷款中间业务分理处11514018002001600分理处22013010003501000分理处3211208004501300分理处4201359004201500解:若先确定分理处1的运行是否DEA有效,可列出线性规划模型如下:minEs.t. 1800+1000+800+9001800 200+350+450+420 200 1600+1000+1300+1500 1600 15+20+21+2015E 140+130+120+13540E +=1 0 (j=1,2,3,4)求解结果为E=1,说明分理处1的运行为DEA有效,在上述模型中只需将式的右端项数字分别更换为要确定的分理处的产出和投入的数字,就可以分别计算出E的值,计算结果为对分理处3和4,E=1,但对分理处2有E=0.996, =0.28, =0.72,=0,即分理处2运行非DEA有效,若将28%的分理处1同72%分理处3组合,其各项产出不低于分理处2的各项产出,但其投入只有分理处2的96.6%总结一般模型为：某银行n个分理处投入产出情况：职员数为 a,a,a,营业面积 b,b,b，储蓄存取c,c,c，贷款 d,d,d,中间业务e,e,e,则minEax+ax+axA bx+bx+bxA cx+cx+cxA dx+dx+dxA ex+ex+exA x02.投资组合选择问题(8)中国投资基金正在发行一个固定收益共同基金, 基金经理预测到发行结束之后,可以售出一亿份基金(一份基金等于人民币一元), 基金管理的首要目的是获取投资收益,第二个目标是通过分散投资控制风险,假设投资组合经理所面临的企业债券如下表所列:表7债券名称当前收益率(%)到期年份等级A8.52010非常好B9.02019很好C10.02006一般D9.52007一般E8.52011非常好F9.02014很好为了符合分散投资目的, 基金管理人决定投资于任何单支债券的资金额不能超过总资产的25%,至少有一半以上资金投资于长期债券(2009年以后),投资在等级为“一般”债券上的资金额不能超过总资产的30%.解:设x=投资在第i只企业债券上的资金额(单位:人民币,万元) 显然 i=A,B,C,D,E,F,目标函数:当前基金的收益率为p=0.085 x+0.09 x+0.1x+0.095x+0.085x+0.09xs.t. x+x+x+x+x+x=10000x 2500 i= A,B,C,D,E,F,x+x+x+x5000x+x 300x,x,x,x,x,x 0表8债券投资组合问题ABCDEFGHIJK1债券投资组合决策23决策变量xxxxxx符合右端项4目标函数0.0850.090.10.0950.0850.09=P(max)利润917.55可用资金111111=10000可用资金100006分散投资 债券A1000002500分散投资 债券A20007分散投资 债券B0100002500分散投资 债券B25008分散投资 债券C0001002500分散投资 债券C25009分散投资 债券D0010002500分散投资 债券D50010分散投资 债券E0000102500分散投资 债券E011分散投资 债券F0000012500分散投资 债券F250012长期债券(2009年以后)1100115000长期债券(2009年以后)700013等级要求0011003000等级要求300014解15xxxxxx1620002500250050002500总结一般模型：用x表示投资在第i只企业债券资金额，这i种债券当前收益率分别为a，总资金额为A，则投资选择p=ax+ax+ax x+ x+x=Ax0（四）体育上的应用在体育中,如何合理安排比赛项目,参赛人员才能达到最好效果非常重要,这就需要用线性规划来准确计算,找出安排的最优方案. 1.合理安排比赛问题 有16名运动员参加8个项目的游泳比赛,已知运动员号码及参加比赛项目如下表所示(表中*号表示参加项目),为使参加多项比赛的运动员恢复体力,要求比赛顺序安排保证每个运动员不连续参加两项比赛,问如何安排才能作到这一点.1 2 3 4 5 6 7 8 比赛项目运动员号100米自由泳100米蛙泳200米自由泳200米蛙泳100米仰泳100米蝶泳200米混合接力400米混合接力1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*解:将每个项目用一个点表示,同一运动员参加比赛项目的点用边相连,安排比赛顺序时作到相邻点的项目间隔开,安排顺序上可以有多个方案,如下列顺序就是满足题意要求的一个方案:100米仰泳 200米蛙泳 200米混合接力 100米自由泳 400米混合接力 100米蛙泳 100米蝶泳 200米自由泳2.选拔选手问题 54718263 某市游泳队有4名运动员甲,乙,丙,丁,他们的100米自由泳, 蛙泳,蝶泳,仰泳成绩如下表,现要组成一个4100米混合泳接力队,问应如何指派才能使总成绩最好?表10 项目运动员自由泳蛙泳蝶泳仰泳甲565746163乙63696571丙571776367丁5597616362解:设该问题的效率矩阵为C,作变换最后可令x=1,x=1,x=1,x=1,其余决策变量取值为0,即指派甲游蝶泳, 乙游蛙泳, 丙游自由泳, 丁游仰泳,这是最优分配方案,此时总成绩为minZ=61+69+571+62=2491=491（五）旅行上的问题一个人要想旅行必须作好出发前的准备,才不会有危险,用线性规划的方法准确计算相关问题是必须的.旅行背包问题 (3)登山队员,他需要携带的物品有:食品,氧气,冰镐,绳索,帐篷,照相器材,通信器材等,每种物品的重量及重要性系数见表11登山队员可携带的最大量为25kg,试选择该队员所应携带的物品.表11序号1234567物品:食品氧气冰镐绳索帐篷照相器材通信设备重量/ kg55261224重要性系数201518148410解：若x=1表示应携带物品i;若x=0表示该队员不应携带物品I,因此模型可表达为:maxZ=20x+15x+18x+14x+8x+4x+10xs.t. 5x+5x+2x+6x+12x+2x+4x25 x=1或 0, i=1,2,3,4,5,6,7解得最优解: x=1 (i=1,2,3,4,5,6,7)，x=0,背包重量Z*=24kg总结一般模型：旅行需要携带m件物品，每件物品重量a, a, a,重要系数为b,b，,b，可携带最大量为n，则队员应携带的物品怎样安排最合理？解：根据题意：minZ= bx+ bx+ bx ax+ ax+ axnx0（六）航空上的问题 航运往往需要合理安排时间,航班,才会使航运正常运作,这就需要用线性规划来准确计算解决实际问题.航空时间安排问题 某航空公司经营A,B,C三个城市之间的航线,这些航线每天班机起飞与到达时间如下表表12航班号起飞城市起飞时间到达城市到达时间101A9：00B12：00102A10：00B13：00103A15：00B18：00104A20：00C24：00105A22：00C2：00(次日)106B4：00A7：00107B11：00A14：00108B15：00A18：00109C7：00A11：00110C15：00A19：00111B13：00C18：00112B18：00C23：00113C15：00B20：00114C7：00B12：00设飞机在机场停留的损失费用大致与停留时间的平方成正比,又每架飞机从降落到下班起飞至少需2小时准备时间,试决定一个使停留费用损失为最小的飞行方案。解:把从某城市起飞的飞机当作要完成的任务,到达的飞机看作分配去完成任务的人,只要飞机到达后两小时,即可分派去完成起飞的任务,这样可以分别对城市A,B,C各列出一个指派问题,各指派问题效率矩阵的数字为飞机停留的损失费用，设飞机在机场停留一小时损失为a元,则停留2小时损失为4a元, 停留3小时损失为9a元,依此类推。对A,B,C三个城市建立的指派问题的效率矩阵见下表表13城市A 起飞到达1011021031041051064a9a64a169a225a107361a400a625a36a64a108225a256a441a4a16a109484a529a16a81a121a110196a225a400a625a9a城市B 起飞到达106107108111112101256a529a9a625a36a102225a484a4a576a25a103100a289a441a361a576a11364a225a361a289a484a114256a529a9a625a36a城市C 起飞到达10911011311410449a225a225a49a140525a169a169a25a111169a441a441a169a11264a256a256a64a对上述指派问题用匈牙利法求解,即得到一个使停留费用损失最小的方案(A)101(B)108(A)105(C)110(A)101(A)102(B)106(A)102(A)103(B)107(A)104(C)113(B)111(C)114(B)112(C)109(A)103停留费用共损失1748a元（七）城市规划的应用一个城市要想建得合理,必须要精心安排设计规划,用线性规划的方法来规划城市建设很方便,精确.设施布点问题 (3)某城市消防队布点问题:该城市共有6个区,每个区都可以建消防站,市政府希望设置的消防站最少,但必须满足在城市任何地区发生火警时, 消防车要求在15分钟内赶到现场,据实地测定,各区之间消防车行驶的时间见表14,帮助该市指定一个布点最少的计划.解:引入01变量x做决策变量,令x=1 表示在地区设消防站; x=0表示不设消防站.表14地区1地区2地区3地区4地区5地区6地区101016282720地区210024321710地区316240122721地区428321201525地区527172715014地区62002125140本问题的数学模型为:min= x+ x+ x+ x+ x+ xs.t. x+ x 1x+ x + x 1 x+ x 1 x+ x+ x 1 x+ x + x 1 x+ + x + x 1x=1或 0 (i=1,2,3,4,5,6)求的最优解为Z=2, x= x=1,其余x=0,即只有在城区2和4设消防站就可满足要求.（八）日常生活上的应用 人们在日常生活中往往会遇到统筹安排的问题,怎样使生活更合理,身体更健康,用线性规划来解决这种实际问题很重要和方便.1.食用油的结构优化问题 (6) 营养学家公布了7种食物油所含脂肪酸的成分,人们又获知市场上某日的价格,合并列表如下: 表15熟猪油豆油玉米油花生油芝麻油棉籽油菜籽色拉油成本(元/kg)187.87.610.022.08.09.2饱和脂肪酸%42.714.815.216.212.527.94.5单位不饱和脂肪酸%48.922.936.542.540.916.574.0多元不饱和脂肪酸%8.462.348.341.346.655.621.5美国营养学家提出了三种脂肪酸的合理成分为25%,50%和25%,以最低价格为目标,问用哪些油按什么配比方案,供应心脑疾病高发人群使用?还问能否给出几个便于向消费者推广使用的配比方案?解:设在1 kg的混合油中,表中的几种食用油所占成分依次记做x, x,x，它们都是非负的百分数,且其和应该等于1,minZ=18x+7.8x+7.6x+10x+22x+8x+9.2xs.t. x+ x+ x+ x+ x+x+ x=1 23%饱和脂肪酸25%50%单位不饱和脂肪酸52%23%多元不饱和脂肪酸25%x 0计算得最优解x=0.341,x=0.234,x=0.425,其余变量均等于零,而最小成本是Z=11.964(元/kg)下面给出几种配比方案:一组是熟猪油：玉米油：色拉油10：9：7,混合使用时,成分是饱和脂肪酸 22.896%,单位不饱和脂肪酸 51.396%,多元不饱和脂肪酸 25.738%;另一组是熟猪油：花生油：色拉油10：12：6, 混合使用时, 成分是饱和脂肪酸 23.157%,单位不饱和脂肪酸 51.5801%,多元不饱和脂肪酸 25.307%总结一般模型：生活食物共n种，每种成本分别为a, a, , a,食用营养满足人体要怎样用最优价格购买食物且符合人体需要？解：minZ= ax+ ax+ axx+ x+ x=1x02.饮食问题 (4) 在食品价格飞快上涨的时候,每个家庭主妇面临的困难任务是:在保持实际的预算之内,为保持家庭准备各方面协调的食物,当然营养是在计划一周菜单时应考虑的唯一因素,现在假设某主妇在制定本周菜单时考虑表16所列6种蔬菜的份数,以使使用费最小,而又能满足所有营养素的最低需要量,表16总结各种蔬菜包含的营养和费用,另外在一周内供应洋白菜不多于2次,而其他蔬菜的供应在一周内不多于4次,每周需14份蔬菜,为了使费用最小而又满足营养素和美味的要求,问在下一周内应当供应每种蔬菜多少次?解:令x供应青豆的次数, x供应胡萝卜的次数, x供应花菜的次数, x供应洋白菜的次数，x供应甜菜的次数, x供应土豆的次数表16每份所含单位数维生素每份点费用蔬菜铁磷AC烟酸(分)青豆0.451041580.35胡萝卜0.4528906530.355花菜1.05502550530.68洋白菜0.42575270.152甜菜0.5221550.256土豆0.57523580.83要求蔬菜提供的营养(最低周需要量)6.0毫克325毫克17500毫克245毫克5.0毫克求解本问题的数学模型如下:minZ=5x+5x+8x+2x+6x+3x 满足约束条件: 铁:0.45x+0.45x+1.05x+0.40x+0.50x+0.50x6.0磷:10x+28x+50x+25x+22x+75x325维生素A :415x+9065x+2550x+75x+15x+235x17500维生素C :8x+3x+53x+27x+5x+8x245烟酸:0.3x+0.35x+0.6x+0.15x+0.25x+0.8x5x2x4x4x4x4x4x+ x+ x+ x+ x+ x=14x0 (i=1,2,3,4,5,6)解得结果如下: 蔬菜青豆每周供应的次数为4, 蔬菜胡萝卜每周供应的次数为1, 蔬菜花菜每周供应的次数为3, 蔬菜洋白菜每周供应的次数为2, 蔬菜甜菜每周供应的次数为0, 蔬菜土豆每周供应的次数为4.（九）