运筹学完整版本

1、污水处理问题200万m3500万m32万m31.4万m3200万m3500万m32万m31.4万m3化工厂1化工厂21000元/万m3800元/万m3分析：化工厂1处理污水x1万m3,化工厂2处理污水x2万m3。minz=1000x1+800x2(2-x1)/500≤2/1000[(1-0.2)(2-x1)+1.4-x2]/(500+200)≤2/1000x1≤2x2≤1.4x1，x2≥0这里minz:表示求z的最小值。松弛变量:在线性规划中，一个“≤”约束条件中没有使用的资源或能力称之为松弛变量位于直线①、②的交点上，故可知设备台时和材料A的松弛变量都为0；交点不在直线③上，材料B的松弛变量大于0.剩余变量:在线性规划中，对于“≥”约束条件，可以增加一些代表最低限约束的超过量，称之为剩余变量。化为标准型minz=-x1+2x2-3x3x1+x2+x3≤7① x1-x2+x3≥2② -3x1+x2+2x3=5③ x1,x2≥0，x3无约束令x3=x3’-x3”，x3’,x3”≥0；①式加上一个松弛变量x4；②式减去一个剩余变量x5；令z’=-zmaxz’=x1-2x2+3(x3’-x3”)+0x4+0x5x1+x2+(x3’-x3”)+x4=7 x1-x2+(x3’-x3”)-x5=2 -3x1+x2+2(x3’-x3”)=5 x1,x2,x3’,x3”,x4,x5≥0在约束条件常数项中增加一个单位而使最优目标函数值得到改进的数量称之为这个约束条件的对偶价格。当某约束条件中的松弛变量（或剩余变量）不为零时，这个约束条件的对偶价格就为0.2、人力资源分配的问题例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?解：设xi表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6约束条件：s.t.x1+x6≥60x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1,x2,x3,x4,x5,x6≥0例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？解：设xi(i=1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6+x7约束条件：s.t.x1+x2+x3+x4+x5≥28x2+x3+x4+x5+x6≥15x3+x4+x5+x6+x7≥24x4+x5+x6+x7+x1≥25x5+x6+x7+x1+x2≥19x6+x7+x1+x2+x3≥31x7+x1+x2+x3+x4≥28x1,x2,x3,x4,x5,x6,x7≥03、生产计划的问题例3．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？解：设x1,x2,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。求xi的利润：利润=售价-各成本之和产品甲全部自制的利润=23-(3+2+3)=15产品甲铸造外协，其余自制的利润=23-(5+2+3)=13产品乙全部自制的利润=18-(5+1+2)=10产品乙铸造外协，其余自制的利润=18-(6+1+2)=9产品丙的利润=16-(4+3+2)=7可得到xi的利润分别为15、10、7、13、9元。通过以上分析,可建立如下的数学模型:目标函数：Max15x1+10x2+7x3+13x4+9x5约束条件：5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0例4．永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成A工序；有三种规格的设备B1、B2、B3能完成B工序。Ⅰ可在A、B的任何规格的设备上加工；Ⅱ可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？解：设xijk表示第i种产品，在第j种工序上的第k种设备上加工的数量。建立如下的数学模型:s.t.5x111+10x211≤6000（设备A1）7x112+9x212+12x312≤10000（设备A2）6x121+8x221≤4000（设备B1）4x122+11x322≤7000（设备B2）7x123≤4000（设备B3）x111+x112-x121-x122-x123=0（Ⅰ产品在A、B工序加工的数量相等）x211+x212-x221=0（Ⅱ产品在A、B工序加工的数量相等）x312-x322=0（Ⅲ产品在A、B工序加工的数量相等）xijk≥0,i=1,2,3;j=1,2;k=1,2,3目标函数为计算利润最大化，利润的计算公式为：利润=[（销售单价-原料单价）*产品件数]之和-（每台时的设备费用*设备实际使用的总台时数）之和。这样得到目标函数：Max(1.25-0.25)(x111+x112)+(2-0.35)x221+(2.80-0.5)x312–300/6000(5x111+10x211)-321/10000(7x112+9x212+12x312)-250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).经整理可得：Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x1234、套裁下料问题例5．某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？解：共可设计下列5种下料方案，见下表设x1,x2,x3,x4,x5分别为上面5种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5约束条件：s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0用“管理运筹学”软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。即x1=30;x2=10；x3=0；x4=50；x5=0；只需90根原材料就可制造出100套钢架。注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。配料问题例6．某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？解：设xij表示第i种（甲、乙、丙）产品中原料j的含量。这样我们建立数学模型时，要考虑：对于甲：x11，x12，x13；对于乙：x21，x22，x23；对于丙：x31，x32，x33；对于原料1：x11，x21，x31；对于原料2：x12，x22，x32；对于原料3：x13，x23，x33；目标函数：利润最大，利润=收入-原料支出约束条件：规格要求4个；供应量限制3个。利润=总收入-总成本=甲乙丙三种产品的销售单价*产品数量-甲乙丙使用的原料单价*原料数量目标函数Max50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）=-15x11+25x12+15x13-30x21+10x22-40x31-10x33约束条件：从规格要求可知：x11≥0.5(x11+x12+x13)x12≤0.25(x11+x12+x13)x21≥0.25(x21+x22+x23)x22≤0.5(x21+x22+x23)从第2个表中，生产甲乙丙的原材料不能超过原材料的供应限额，(x11+x21+x31)≤100(x12+x22+x32)≤100(x13+x23+x33)≤60目标函数：Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33约束条件：s.t.0.5x11-0.5x12-0.5x13≥0（原材料1不少于50%）-0.25x11+0.75x12-0.25x13≤0（原材料2不超过25%）0.75x21-0.25x22-0.25x23≥0（原材料1不少于25%）-0.5x21+0.5x22-0.5x23≤0（原材料2不超过50%）x11+x21+x31≤100(供应量限制）x12+x22+x32≤100(供应量限制）x13+x23+x33≤60(供应量限制）xij≥0,i=1,2,3;j=1,2,35、投资问题例7．某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。据测定每万元每次投资的风险指数如下表，问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？解：1）确定决策变量：连续投资问题设xij(i=1～5，j=1～4)表示第i年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：Ax11x21x31x41x51Bx12x22x32x42Cx33Dx242）约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是x11+x12=200；第二年：B次年末才可收回投资，故第二年年初有资金1.1x11，于是x21+x22+x24=1.1x11；第三年：年初有资金1.1x21+1.25x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初有资金1.1x31+1.25x22，于是x41+x42=1.1x31+1.25x22；第五年：年初有资金1.1x41+1.25x32，于是x51=1.1x41+1.25x32；B、C、D的投资限制：xi2≤30(i=1、2、3、4)，x33≤80，x24≤1003）目标函数及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi2≤30(i=1、2、3、4)，x33≤80，x24≤100xij≥0(i=1、2、3、4、5；j=1、2、3、4）b)所设变量与问题a相同，目标函数为风险最小，有

Minf=x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24在问题a的约束条件中加上“第五年末拥有资金本利在330万元”的条件，于是模型如下：Minf=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.t.x11+x12=200x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi2≤30(i=1、2、3、4)，x33≤80，x24≤1001.1x51+1.25x42+1.4x33+1.55x24≥330xij≥0(i=1、2、3、4、5；j=1、2、3、4）单纯形法几种特殊情况：求线性规划的最优解里有人工变量大于零，则此线性规划无可行解。存在着一个大于零的检验数，并且该列的系数向量的每个元素aij(i=1,2,…,m)都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是由于建模的错误所引起的。如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解。6、运输问题解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，各地之间的运输单价已知的前提下，如何确定一个使得总的运输费用最小的方案的问题。例某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：使运费最小，即所以此线性规划问题的线性规划模型如下：表上作业法：最小元素法（西北角法）—>势差法（闭合回路法）7、产销不平衡的运输问题例石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为：由于需大于供，经院研究决定一区供应量可减少0--300吨，二区必须满足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。解：根据题意，作出产销平衡与运价表：例设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表，试求总费用为最低的化肥调拨方案。解：根据题意，作出产销平衡与运价表：最低要求必须满足，因此把相应的虚设产地运费取为M，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为0。对应4”的销量50是考虑问题本身适当取的数据，根据产销平衡要求确定D的产量为50。8、生产与储存问题例某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。解：设xij为第i季度生产的第j季度交货的柴油机数目，那么应满足：交货：x11=10生产：x11+x12+x13+x14≤25x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10把第i季度生产的柴油机数目看作第i个生产厂的产量；把第j季度交货的柴油机数目看作第j个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：目标函数：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44例光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7--8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1--6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？解：这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地1）1--6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设一假想销地销量为36；2）上年末库存103台，只有仓储费和运输费，把它列为第0行；3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台；4）1--6表示1--6月份正常生产情况，1’--6’表示1--6月份加班生产情况。产销平衡与运价表：9、转运问题在原运输问题上增加若干转运站。运输方式有：产地转运站、转运站销地、产地产地、产地销地、销地转运站、销地产地等例腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产400台，广州分厂每月生产600台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如图，单位是百元。问应该如何调运仪器，可使总运输费用最低？1-广州2-大连3-上海4-天津5-南京6-济南7-南昌8-青岛解：设xij为从i到j的运输量，可得到有下列特点的线性规划模型：目标函数：Minf=所有可能的运输费用（运输单价与运输量乘积之和）约束条件：对产地（发点）i：输出量-输入量=产量对转运站（中转点）：输入量-输出量=0对销地（收点）j：输入量-输出量=销量Minf=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48s.t.x13+x14≤600(广州分厂供应量限制）x23+x24+x28≤400(大连分厂供应量限制）-x13-x23+x35+x36+x37+x38=0（上海销售公司，转运站）-x14-x24+x45+x46+x47+x48=0（天津销售公司，转运站）x35+x45=200（南京的销量）x36+x46=150（济南的销量）x37+x47=350（南昌的销量）x38+x48+x28=300（青岛的销量）xij≥0,i,j=1,2,3,4,5,6,7,810、投资场所的选择例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Aj(j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由A1，A2，A3三个点至多选择两个；在西区由A4，A5两个点中至少选一个；在南区由A6，A7两个点中至少选一个；在北区由A8，A9，A10三个点中至少选两个。投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?解：设0--1变量xi=1(Ai点被选用）或0(Ai点没被选用）。Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720x1+x2+x3≤2x4+x5≥1x6+x7≥1x8+x9+x10≥2xj≥0且xj为0--1变量，i=1,2,3,……,1011、固定成本问题例5．高压容器公司制造小、中、大三种尺寸的金属容器，现在要制定一个生产计划，使获得的利润为最大。解：设x1，x2，x3分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设yi=引入约束xi≤Myi，i=1，2，3，M充分大，以保证当yi=0时，xi=0。这样我们可建立如下的数学模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300x1+2x2+3x3≤100xi≤Myi，i=1，2，3，M充分大xj≥0yj为0--1变量，i=1,2,312、指派问题有n项不同的任务，恰好n个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把n项任务指派给n个人，使得完成n项任务的总的效率最高。例6．问应如何指派工作，才能使总的消耗时间为最少？解：引入0—1变量xij，并令xij=这可以表示为一个0--1整数规划问题：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(甲只能干一项工作)x21+x22+x23+x24=1(乙只能干一项工作)x31+x32+x33+x34=1(丙只能干一项工作)x41+x42+x43+x44=1(丁只能干一项工作)x11+x21+x31+x41=1(A工作只能一人干)x12+x22+x32+x42=1(B工作只能一人干)x13+x23+x33+x43=1(C工作只能一人干)x14+x24+x34+x44=1(D工作只能一人干)xij为0--1变量，i,j=1,2,3,413、分布系统设计例7．某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂。已知在A2，A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外，A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。a)问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?b)如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂?解：a)设xij为从Ai运往Bj的运输量(单位千箱)，yk=1(当Ak被选中时)或0（当Ak没被选中时),k=2,3,4,5．这可以表示为一个整数规划问题：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4项为固定投资额，后面的项为运输费用。s.t.x11+x12+x13≤30(A1厂的产量限制)x21+x22+x23≤10y2(A2厂的产量限制)x31+x32+x33≤20y3(A3厂的产量限制)x41+x42+x43≤30y4(A4厂的产量限制)x51+x52+x53≤40y5(A5厂的产量限制)x11+x21+x31+x41+x51=30(B1销地的限制)x12+x22+x32+x42+x52=20(B2销地的限制)x13+x23+x33+x43+x53=20(B3销地的限制)xij≥0，i=1,2,3,4,5；j=1,2,3，yk为0--1变量，k=2,3,4,514、投资问题例8．某公司在今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限；项目B：第三年初需要投资，到第五年末能回收本利128％，但规定最低投资金额为3万元，最高金额为5万元；项目C：第二年初需要投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。项目D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到