运筹学习题

习题一1.1用图解法求解下列线性问题，并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。minz=6x1+4x?st.2xi+X2>13xi+4x2》1.5Xi,X2》0maxz=X1+X2st.8x1+6x2》244x1+6x2》－122x2》4x1,x2》0(5)maxz=3x1+9x?st.X1+3x2<22—x1+x2<4X2w62x1—5x2^0x1,x2》0(2)maxz=4x1+8x?st.2x1+2x2w10—x1+x2》8x1,x2》0(4)maxz=3x1—2x2st.x1+x2w12x1+2x2》4x1,x2》0(6)maxz=3x1+4x?st.—x1+2x2w8x1+2x2w122x1+x2w16x1,x2》0在下列线性规划问题中，找出所有基本解，指出哪些是基本可行解并分别代入目标数，比较找出最优解。st.x1+x3=42x2+x4=123x1+2x2+x5=18(1)maxz=3x1+5x2Xj>0(j=1,…,5)⑵minz=4x1+12x2+18x3St.X1+3X3—X4=32X2+2X3—X5=5Xj>0(j=1,…,5)分别用图解法和单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。maxz=10X1+5x2st.3x1+4x2w95x1+2x2w8x1,x2》0maxz=100X1+200X2st.x1+x2w500x1w2002x1+6x2w1200x1,x2》0分别用大M法和两阶段法求解下列线性规划问题，并指出问题的解属于哪一类：(2)maxz=2x1+x2+x3st.4x1+2x2+2x3》42x1+4x2w204x1+8x2+2x3w16xj》0(j=1,2,3)(3)maxz=xi+X2st.8xi+6x2>244x1+6x2》—122x2》4xi,X2》0(5)maxz=4xi+6x?st.2xi+4X2w1803xi+2x2w150xi+X2=57X2—22xi,X2》0maxz=xi+2x2+3x3—X4st.xi+2x2+3x3=152xi+x2+5x3=20Xi+2X2+X3+X4=10Xj》0(j=1,…,4)(6)maxz=5xi+3x2+6x3st.xi+2x2+X3w182xi+X2+3x3w16xi+x2+x3=10Xi,X2>0,X3无约束1.5线性规划问题maxz=CX,AX=b,X>0,如X*是该问题的最优解，又入>0为某一常数,分别讨论下列情况时最优解的变化：(1)目标函数变为maxz=入CX；(2)目标函数变为maxz=(C+入)X；(3)目标函数变为Cmaxz=X，约束条件变为AX=入b。1.6下表中给出某求极大化问题的单纯形表，问表中ai,a2,ci,C2,d为何值时以及表中变量属于哪一种类型时有：表中解为唯一最优解；表中解为无穷多最优解之一；表中解为退化的可行解；下一步迭代将以Xi替换基变量X5；该线性规划问题具有无界解；该线性规划问题无可行解。XiX2X3X4X5X3d4ai100X42—1—5010X53a2—3001Cj—zjCiC20001.7战斗机是一种重要的作战工具，但要使战斗机发挥作用必须有足够的驾驶员。因此生产出来的战斗机除一部分直接用于战斗外，需抽一部分用于培训驾驶员。已知每年生产的战斗机数量为aj(j=1,…,n),又每架战斗机每年能培训出k名驾驶员，问应如何分配每年生产出来的战斗机，使在n年内生产出来的战斗机为空防作出最大贡献？1.8.某石油管道公司希望知道，在下图所示的管道网络中可以流过的最大流量是多少及怎样输1.9.某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下:班次时间所需人数16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030设司机和乘务人员分别在各时间区段一开始时上班，并连续工作八小时，问该公交线路至少配备多少名司机和乘务人员。列出此问题的线性规划模型。1.10某班有男生30人，女生20人，周日去植树。根据经验，一天男生平均每人挖坑20个,或栽树30棵，或给25棵树浇水；女生平均每人挖坑10个，或栽树20棵，或给15棵树浇水。问应怎样安排，才能使植树（包括挖坑、栽树、浇水）最多？请建立此问题的线性规划模型，不必求解。1.11.某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表所示。问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建立此问题的线性规划的数学模型。甲乙丙原料成本（元/千克）每月限量（千克）A>60%>15%2.002000B1.502500C<20%<60%<50%1.001200加工费（元/千克）0.500.400.30售价3.402.852.251.12.某商店制定7-12月进货售货计划，已知商店仓库容量不得超过500件，6月底已存货200件，以后每月初进货一次，假设各月份此商品买进售出单价如下表所示，问各月进货售货各多少，才能使总收入最多？请建立此问题的线性规划模型，不必求解。TOC\o"1-5"\h\z月份789101112买进单价282425272323售出单价2924262822251.13.某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日，春夏季4000人日，如劳动力本身用不了时可外出干活，春夏季收入为2.1元/人日，秋冬季收入为1.8元/人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养动物时每头奶牛投资400元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲草，并占用人工秋冬季为100人日，春夏季为50人日，年净收入400元/每头奶牛。养鸡时不占土地，需人工为每只鸡秋冬季需0.6人日，春夏季为0.3人日，年净收人为2元/每只鸡。农场现有鸡舍允许最多养3000只鸡，牛栏允许最多养32头奶牛。三种作物每年需要的人工及收人情况如下表所示。大豆玉米麦子秋冬季需人日数203510春夏季需人日数507540年净收入(元/公顷)175300120试决定该农场的经营，使年净收人为最大。(建立线性规划模型，不需求解)习题二2.1写出下列线性规划问题的对偶问题maxz=10xi+X2+2x3St.Xi+X2+2X3W104xi+X2+X3W20Xj>0(j=1,2,3)(3)minz=3X1+2x?—3X3+4x4St.X1—2x2+3x3+4X4w3X2+3X3+4X4》一52x1—3x2—7x3—4x4=2=X1>0,X4<0,X2,,X3无约束(2)maxz=2x1+X2+3x3+X4st.x1+x2+x3+x4w52x1—x2+3x3=—4X1—X3+X4>1X1,X3>0,X2,X4无约束⑷minz=—5X1—6x2—7x3st.—X1+5x2—3x3>15—5x1—6x2+10X3w20X1一X2一X3=一5X1W0,X2>0,X3无约束2.2已知线性规划问题maxz=CX,AX=b,X>0。分别说明发生下列情况时，其对偶问题的解的变化：(1)问题的第k个约束条件乘上常数入(入工0);将第k个约束条件乘上常数入(入工0)后加到第r个约束条件上；目标函数改变为maxz=?CX(入工0);模型中全部X1用3x'1代换。2.3已知线性规划问题minz=8x1+6x?+3x3+6x4St.X1+2X2+X4》33x1+X2+X3+X4》6X3+X4=2X1+X3》2Xj>0(j=1,2,3,4)写出其对偶问题；已知原问题最优解为X*=(1,1,2,0),试根据对偶理论，直接求出对偶问题的最优解。2.4已知线性规划问题minz=2x1+X2+5x3+6x4对偶变量st.2x1+X3+X4W8y12x1+2X2+X3+2X4W12y2Xj>0(j=1,2,3,4)其对偶问题的最优解y；=4；yj=1，试根据对偶问题的性质，求出原问题的最优解。2.5考虑线性规划问题maxz=2xi+4x2+3x3st.3xi+4x2+2x3<602xi+x2+2x3<40xi+3X2+2X3W80Xj>0(j=1,2,3)(1)写出其对偶问题(2)用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；比较(2)和(3)计算结果。2.6已知线性规划问题maxz=10xi+5x?st.3xi+4x?w95xi+2x2^8Xj》0(j=1,2)用单纯形法求得最终表如下表所示：X1X2X3X4bX20151431432X11017271c(=Cj-Zj005251414试用灵敏度分析的方法分别判断:(1)目标函数系数G或C2分别在什么范围内变动，上述最优解不变；约束条件右端项b1,b2,当一个保持不变时，另一个在什么范围内变化，上述最优基保持不变；问题的目标函数变为maxz=12x1+4x2时上述最优解的变化；约束条件右端项由f9)变为11时上述最优解的变化。TOC\o"1-5"\h\z9丿19丿2.7线性规划问题如下：maxz=—5x1+5x2+13x3st.—X1+x2+3x3^20①12x1+4x2+10X3W90②Xj>0(j=1,2,3)先用单纯形法求解，然后分析下列各种条件下，最优解分别有什么变化?(1)约束条件①的右端常数由20变为30；(2)约束条件②的右端常数由90变为70；(3)目标函数中X3的系数由13变为8；(4)X1的系数列向量由(一1,12)T变为(0,5)T；(5)增加一个约束条件③：2x1+3x2+5x3<50；(6)将原约束条件②改变为：10X1+5X2+10X3<100。2.8用单纯形法求解某线性规划问题得到最终单纯形表如下:Cj基变量50401060SX1X2X3X4ac011216bd101424Qj=Cj-Zj00efg（1）给出a,b,c,d,e,f,g的值或表达式；（2）指出原问题是求目标函数的最大值还是最小值；（3）用a+a，b+b分别代替a和b，仍然保持上表是最优单纯形表，求.：a，：b满足的范围。2.9某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每月白坯纸供应量为30000千克。已知工人的劳动生产率为：每人每月可生产原稿纸30捆，10或日记本30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸10千克，每打日记本3用白坯纸40千克，每箱练习本用白坯纸80千克。又知每生产一捆原稿纸可获利2元，生产一打日33记本获利3元，生产一箱练习本获利1元。试确定：（1）现有生产条件下获利最大的方案；（2）如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为每人每月40元，则该厂要不要招收临时工？如要的话，招多少临时工最合适？2.10某厂生产甲、乙两种产品，需要A、B两种原料，生产消耗等参数如下表（表中的消耗系数为千克/件）。产品原料甲乙可用量（千克）原料成本（元/千克）A241601.0B321802.0销售价（元）1316（1）请构造数学模型使该厂利润最大，并求解。（2）原料A、B的影子价格各为多少。（3）现有新产品丙，每件消耗3千克原料A和4千克原料B，问该产品的销售价格至少为多少时才值得投产。（4）工厂可在市场上买到原料A。工厂是否应该购买该原料以扩大生产？在保持原问题最优基的不变的情况下，最多应购入多少？可增加多少利润？习题二3.1求解下表所示的运输问题，分别用最小元素法、西北角法和伏格尔法给出初始基可行解:B1B2B3B4供应量Ai（10）（6）（7）「（12）「4A2（16）（10）（5）（9）9A3（5）（4）（10）:（10）:5需要量5346183.2由产地A1,A2发向销地B1，B2的单位费用如下表，产地允许存贮，销地允许缺货，存贮和缺货的单位运费也列入表中。求最优调运方案，使总费用最省。B1B2供应量存贮费/件Ai854003A2693004需要量200350缺货费/件253.3对如下表的运输问题:AB供应量X100（6）（4）100Y30（5）50（8）80Z:（2）60（7）60需要量130110240（1）若要总运费最少，该方案是否为最优方案（2）若产地Z的供应量改为100，求最优方案。3.4某利润最大的运输问题，其单位利润如下表所示:B1B2B3B4供应量Ai（6）（7）（5）（8）8A2（4）（5）（10）（8）9A3（2）（9）（7）（3）7需要量865524（1）求最优运输方案，该最优方案有何特征?⑵当A的供应量和B3的需求量各增加2时，结果又怎样？3.5某玩具公司分别生产三种新型玩具，每月可供量分别为1000、2000、2000件，它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具预期销售量均为1500件，由于经营方面原因，各商店销售不同玩具的盈利额不同，见下表。又知丙百货商店要求至少供应C玩具1000件，而拒绝进A玩具。求满足上述条件下使总盈利额最大的供销分配方案。甲乙丙可供量A54一1000B16892000C12101120003.6目前，城市大学能存贮200个文件在硬盘上，100个文件在计算机存贮器上，300个文件在磁带上。用户想存贮300个字处理文件，100个源程序文件，100个数据文件。每月，一个典型的字处理文件被访问8次，一个典型的源程序文件被访问4次，一个典型的数据文件被访问2次。当某文件被访问时，重新找到该文件所需的时间取决于文件类型和存贮介质，如下表。时间(分钟)处理文件源程序文件数据文件硬盘544存贮器211磁带1086如果目标是极小化每月用户访问所需文件所花的时间，请构造一个运输问题的模型来决定文件应该怎么存放并求解。3.7已知下列五名运动员各种姿势的游泳成绩(各为50米)如表5-2:试用运输问题的方法来决定如何从中选拔一个参加200混合泳的接力队，使预期比赛成绩为最好。赵钱张王周仰泳37.732.933.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.13.8求总运费最小的运输问题，其中某一步的运输图如下表。BiB2B3供应量A13(3)(5)(7)3A22(4)4(2)(4)6A3(5)「1(6)5(3)d需要量abce写出a,b,c,d,e的值，并求出最优运输方案；A到B1的单位运费满足什么条件时，表中运输方案为最优方案。3.9某一实际的运输问题可以叙述如下：有n个地区需要某种物资，需要量分别为bj(j=1,…,n)。这些物资均由某公司分设在m个地区的工厂供应，各工厂的产量分别为ai(i=1,…,m),已知从imn地区的工厂至第j个需求地区的单位物资的运价为Cj，又aai八bj,试阐述其对偶问题并解释idj=1对偶变量的经济意义。为确保飞行安全，飞机上的发动机每半年必须强迫更换进行大修。某维修厂估计某种型号战斗机从下一个半年算起的今后三年内每半年发动机的更换需要量分别为：100,70,80,120,150,140。更换发动机时可以换上新的，也可以用经过大修的旧的发动机。已知每台新发动机的购置费为10万元，而旧发动机的维修有两种方式：快修，每台2万元，半年交货（即本期拆下来送修的下批即可用上）；慢修，每台1万元，但需一年交货（即本期拆下来送修的需下下批才能用上）设该厂新接受该项发动机更换维修任务，又知这种型号战斗机三年后将退役，退役后这种发动机将报废。问在今后三年的每半年内，该厂为满足维修需要各新购、送去快修和慢修的发动机数各是多少，使总的维修费用为最省？（将此问题归结为运输问题，只列出产销平衡表与单位运价表，不求数值解。）3.11甲、乙两个煤矿分别生产煤500万吨，供应A、B、C三个电厂发电需要，各电厂用量分别为300、300、400万吨。已知煤矿之间、煤矿与电厂之间以及各电厂之间相互距离（单位：公里）如下列三个表所示。又煤可以直接运达，也可经转运抵达，试确定从煤矿到各电厂间煤的最优调运方案（最小总吨公里数）。从\到甲乙从\到ABC心到ABC甲0120甲15012080A070100乙1000乙6016040B500120C1001500习题四4.1分别用图解法和单纯形法求解下述目标规划问题minz=p1(d1+d2')+P2d3一st.—X1+X2+d1—d1=1—0.5x1+x?+d2—d2=23x1+3x2+d3—d3=50X1,X2>0;di,d：>0(i=1,2,3)minz=P1(2d1+3d2)+P2df+p3d4st.X1+X2+d1—『1=10X1+d2—d2=45x1+3x2+d3—d3=56X1+X2+d4—d4=12X1,X2>0;di,d：>0(i=1，…，4)4.2考虑下述目标规划问题minz=p1(d1+d2)+2p2d4+P2d3+P3d1st.X1+d1—d*1=20x2+d2—『2=35—5x1+3x2+d3—d3=220X1—X2+d4—d*4=60X1,X2>0;d—i,d+i>0(i=1，…，4)求满意解；当第二个约束右端项由35改为75时，求解的变化;（3）若增加一个新的目标约束：—4xi+X2+d一5-d+5=8,该目标要求尽量达到目标值，并列为第一优先级考虑，求解的变化；（4）若增加一个新的变量X3,其系数列向量为（0，1，1，—1）T，则满意解如何变化?4.3一个小型的无线电广播台考虑如何最好地来安排音乐、新闻和商业节目时间。依据法律，该台每天允许广播12小时，其中商业节目用以赢利，每小时可收入250美元，新闻节目每小时需支出40美元，音乐节目每播一小时费用为17.50美元。法律规定，正常情况下商业节目只能占广播时间的20%，每小时至少安排5分钟新闻节目。问每天的广播节目该如何安排？优先级如下：P1:满足法律规定要求；P2：每天的纯收入最大。试建立该问题的目标规划模型。4.4某企业生产两种产品，产品I售出后每件可获利10元，产品n售出后每件可获利8元。生产每件产品I需3小时的装配时间，每件产品n需2小时装配时间。可用的装配时间共计为每周120小时，但允许加班。在加班时间内生产两种产品时，每件的获利分别降低1元。加班时间限定每周不超过40小时，企业希望总获利最大。试凭自己的经验确定优先结构，并建立该问题的目标规划模型。4.5某厂生产A、B两种型号的微型计算机产品。每种型号的微型计算机均需要经过两道工序I、II。已知每台微型计算机所需要的加工时间、销售利润及工厂每周最大加工能力的数据如下：AB母周最大加工冃匕力I46150II3270利润（元/台）300450工厂经营目标的期望值及优先级如下：P1:每周总利润不得低于10000元；P2:因要求，A型机每周至少生产10台：B型机每周至少生产15台；P3:由于条件限制且希望充分利用工厂的生产能力，工序I的每周生产时间必须恰好为150小时,工序II的每周生产时间可适当超过其最大加工能力（允许加班）。试建立此问题的目标规划模型习题五0—1规划问题5个钻井探油，使总的钻探费用为最小。若C1,C2,…，C10,并且井位选择上要满足下5.1试将下述非线性的0-1规划问题转换为线性的2,3maxz=X1十X2X3—X3st.—2x1+3x2+X3w3Xj=0或1(j=1,2,3)5.2某钻井队要从以下10个可供选择的井位中确定10个井位的代号为S1,S2,…，S10,相应的钻探费用为列限制条件:(1)或选择Si和S7,或选择钻探S8；(2)选择了S3或S4就不能选或反过来也一样;在s5,s6,s7,s8中最多只能选两个。试建立此问题的整数规划模型。5.3用分枝定界法求解下列整数规划问题(1)st.maxz=xi+X2,9v51Xi十X2V14141—2x1十X2v3X1,X2>0且为整数maxz=2x1+3x2st.5x1+7x2v354x1十9x2v36x1,x2>0且为整数5.4用割平面法求解下列整数规划问题maxz=7x1+9x?st.—X1+3X2v67x1十X2v35x1,x2>0且为整数minz=4x1+5x2st.3x1+2x2>7X1+4X2》53x1十X2>2X1,X2》0且为整数5.5用隐枚举法求解0—1整数规划问题maxz=3x1+2x2—5x3—2x4+3x5St.X1+X2十X3+2X4+X5v47x1十3x3—4x4+3x5=811x1—6x2十3X4—3x5》3Xj=0或1(j=1，…，5)5.6请用解0—1整数规划的隐枚举法求解下面的两维0—1背包问题:maxf=2x1+2X2+3X3S.t.X1+2X2+2X3v42x1+X2+3x3v5Xj=0或1,j=1,2,35.7用匈牙利法求解如下效率矩阵的指派问题r791012、1312161715161415J1121516’5.8分配甲、乙、丙、丁四人去完成五项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。八^任务ABCDE甲2529314237乙3938262033丙3427284032丁24423623455.9已知下列五人各种姿势的游泳成绩（各为50米），试问如何进行指派，从中选拔一个参加200米混合泳的接力队，使预期比赛成绩为最好。赵钱张王'周仰泳37.732.933.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1运筹学中著名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某一城市出发，到其它几个城市去推销商品，规定每个城市均须到达而且只到达一次，然后回到原出发城市。已知城市i和j之间的距离为dj，问该商贩应选择一条什么样的路线顺序旅行，使总的旅程为最短。试对此问题建立整数规划模型。有三个不同的产品要在三台机床上加工，每个产品必须首先在机床1上加工，然后依次在机床2，3上加工。在每台机床上加工三个产品的顺序应保持一样，假定用tij表示在第j机床上加工第i个产品的时间，问应如何安排，使三个产品总的加工周期为最短。试建立此问题的整数规划模型。习题参考答案第一章线性规划及单纯形法1.1(1)解:第一，求可行解集合。令两个约束条件为等式，得到两条直线，在第一象限划出满足两个不等式的区域，其交集就是可行集或称为可行域，如图1-1所示，交集为（1/2,0）。第二，绘制目标函数图形。将目标函数的系数组成一个坐标点（6，4），过原点0作一条矢量指向点（6,4），矢量的长度不限，矢量的斜率保持4比6,再作一条与矢量垂直的直线，这条直线就是目标函数图形，目标函数图形的位置任意，如果通过原点则目标函数值Z=0，如图1-2所示。第三，求最优解。图1-2的矢量方向是目标函数增加的方向或称梯度方向，在求最小值时将目标函数图形沿梯度方向的反方向平行移动，（在求最大值时将目标函数图形沿梯度方向平行移动）直x=(1/2,0)到可行域的边界，停止移动，其交点对应的坐标就是最优解，如图1-3所示。最优解目标函数的最小值Z=3。X2」1yx1+X2》1V\\\3X^4x2W1.50v2X1图1.1-1彳p—X2\2*1乎2》1、3x^+4x2W「5€0、心X1图1.1-3（2）无可行解；［求解方法与（1）类似］（3）无界解；无可行解；无穷多最优解z*=66唯一最优解z*=92/3,x1=20/3,x2=3/81.2(1)解：由题目可知，其系数矩阵为10100(R,P2,P3,P4,P5)即卩02010洛X3=4■=2x2=12—x43捲+2x2=18-x532001101因(R，P2，巳)=020线性独立，故有320一X1X3=4花=4令非基变量x4,x5=0得2x2=12tx2=63x12x2=18x3=2X1X3=4x4=12-2x23X1=18-2X2-X5得到一个基可行解x⑴=(2,6,2,0,0),Z1=36。110(P,F3,P4)001线性独立，故有]300一|X1■X3=4|X1=6令非基变量x2,x5=0得标准

excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载