运筹学 第三章 - 图文

西安邮电学院试题库管理系统——试题表

专业代码 11 专业名称 信息管理与信息系统 课程代码 18 课程名称 运筹学 试题类型代码 08 试题类型名称 计算题 出题人 管理员 出题 日期 难度系数 2005-11-4 认知分类 建议分数 8 建议时间 8 知识点 代码 题 干 答 案 评分标准 11180301 某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见表。 仪器装置代号 A1 A2 A3 A4 A5 A6 体积 v1 v2 v3 v4 v5 v6 重量 w1 w2 w3 w4 W5 w6 实验中的价值 c1 c2 c3 c4 c5 c6 max z=?cj?16 jxj 中 运用 ?6??vjxj?V?j?1?6??wjxj?W?j?1?st.?x1?x3?1 ?x2?x4?1??x5?x6??x??1, 安装Aj仪器?j?0, 否则?? 要求： （1） 装入卫星的仪器装置总体积不超过V，总重量不超过W （2） A1与A3中最多安装一件； （3） A2与A4中至少安装一件； （4） A5与A6或者都安上，或者都不安。总的目的是装上去的仪器装置使该科学卫星发挥最大的实验价值。试建立这个问题的数学模型。 现有一批每根长度为L的圆钢，需要截取n种不同长度的零件毛坯，长度为aj的毛坯需要 设使用xj根L米长的圆钢来截取aj米长的毛坯（1,2,……n）。 有mj（1,2,….n）段。为了方便，每根圆钢只截取一种长度的毛坯。应当怎样截取，才能使动用的圆钢数目最少？ ?L?设sj???为每根L 米长的圆钢用来截取aj米长毛坯时可以得到的最多段数。 ?aj???数学模型为 nminz??xjj?1??sjxj?mj?2.....n）??xj?0且为整数（j?1， 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用最小。若10个井位的代号要满足以下限制条件： （1）或选择s1和s7，或选择钻探s8； （2）选择了s3或s4就不能选择s5，或反过来也一样； （3）在s5，s6，s7，s8中最多只能选择两个；试建立这个问题的数学模型。 min z= ?cj?110 j xj ?10??xj?5?j?1?x?x?1 x?x?11853??st.?x7?x8?1 x5?x4?1 ?x?x?x?x?2678?5??1, 选择钻探第sj井位?xj??否则??0, ? 运筹学中著名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某一城市出发，到i直接去j?1，旅行商贩从设x= 其他n个城市去推销商品，规定每个城市均须到达而且只能到达一次，然后回到原出发城ij?市。已知城市i和城市j之间的距离为dij，问该商贩应选择一条什么样的路线顺序旅行，使总的旅程为最短。试建立这个问题的数学模型。 ?0，否则nn由此可写出整数规划模型为 min z=??di?1j?1ijxij ?n??xij?1(j?1,?,n)?i?1?n??xij?1(i?1,?,n)?j?1?st.?ui?uj?nxij?n?1 ??ui为连续变量(i?1,?,n)，也可取整数值?i，j?1,?,n，i?j???? 一种产品可分别在A，B，C，D4种设备的任一种上加工。已知每种设备启用时的准备结束设xj为在第j设备上加工的产品数（j=1，…，4）； 费用，生产上述产品时的单件成本以及每种设备的最大加工能力如表所示。如需生产该产品2000件，如何使总的费用最少，试建立数学模型。 ?1，启用设备j加工产品yj=?（j=1，…，4） ?1设备 准备结束费/元 生产成本/最大加工能力/件 （元·件） ?0，设备j不启用A B C D 1 000 920 800 700 20 24 16 28 900 1 000 1 200 1 600 由此可写出模型为 min z=1 000y1+20x1+920 y2+24x2+800 y3+16x3+700 y4+28 x4 ?x1?x2?x3?x4?2000?x?900y x?1000y ?1122st.? ?x3?1200y3 x4?1600y4?xj?0 yj?0或1 (j?1,?,4)?第 1 页 共 8 页

西安邮电学院试题库管理系统——试题表

有三个不同产品要在三台机床上加工，每个产品必须首先在机床1上加工，然后依次在机床2，3上加工。在每台机床上加工三个产品的顺序应保持一样，假定用tij表示在第j机床上加工第i个产品的时间，问应如何安排，使三个产品总的加工周期为最短。试建立这个问题的数学模型。 ?xij?tij?ti,j?1(i?1,2,3;j?1,2) ??xij?tij?xi?1,j?M?M?i ?st.?xi?1,j?ti?1,j?xij?M(1??i) ? ?i?1,2;j?1,2,3;?i?0或1 ?min z=max{x13+t13, x23+t23, x33+t33} 用xij表示第i个产品在第j机床上开始加工的时刻，这个问题的数学模型为： ?xij?0 在N个地点中选r个（N>r）建厂，在第i个地点建厂（i=1，2，…，N）所需投资为 Ii万元，占地Li亩，建成以后的生产能力为Pi万吨。现在有总投资I万元，土地L亩，应如何选择厂址，使建成后总生产能力最大。 设xi?? ?0表示在i地不建厂 ?1表示在i地建厂N整数规划模型为 maxz??Pixis.t.?Ixii?1Ni?1Ni?1Ni?1i?I ?Lixi?L?x 红豆服装厂利用三种专用设备分别生产衬衣,短袖衫和休闲服,已知上述三种产品的每件用工量,用料量,销售价及可变费用如表所示. 产品名称 衬衣 短袖衫 休闲服 单位用工 3 2 6 单件用料 4 3 6 销售价 120 80 180 可变费用 60 40 80 i?rxi?0,1设该厂生产衬衣x1件,短袖衫x2件,休闲服x3件 设xj为在第j设备上加工的产品数（j=1，…，4）； yj=? ?1，启动相应的j种专用设备?0，否则 已知该厂每周可用工量为150单位,可用料量为160单位,生产衬衣,短袖衫和休闲服三种专用设备的每周固定费用分别为2000,1500和1000.要求为该厂设计一个周的生产计划,使其由此可写出模型为 获利为最大. max z=120x1-(2 000y1+60x1)+80x2-(1500 y2+40 x2)+150x3-(1000 y3+80 x3) ?3x1?2x2?6x3?150?4x?3x?6x?160 123???x1?40y1 st.? x?53y 2?2?x3?25y3 ???xj?0 yj?0或1 (j?1,2,3) 某大学运筹学专业硕士研究生要求课程计划中必须选修两门数学类,两门运筹学类和两门计算机类课程,课程中有些只归属某一类,如微积分归属数学类,计算机程序归属计算机类;但有些课程是跨类的,如运筹学可归为运筹学类和数学类,数据结构归属计算机类和数学类,管理统计归属数学和运筹学类,计算机模拟归属计算机类和运筹学类,预测归属运筹学类和数学类,凡归属两类的课程学后可认为两类中各学了一门课.此外,有些课程要求先学习先修课,如学计算机模拟或数据结构必须先修计算机程序,学管理统计必须先修微积分,学预测必须先修管理统计.问一个硕士研究生最少应学几门及哪几门,才能满足上述要求. 对微积分,运筹学,数据结构,管理统计,计算机模拟,计算机程序,预测7门课程分别编号为1,2,3,4,5,6,7. 设xj=? ?1，选学第j课程?0，否则 由此可写出模型为 min z=x1+x2+…+x7 ?x1?x2?x3?x4?x7?2?x?x?x?x?2457?2?x3?x5?x6?2 ??x1?x4 st.? x?x5?6?x6?x3??x4?x7 ? x?0或1 ?j设xj为j种容器生产的数量 设yj=? 红星塑料厂生产6种规格的塑料容器,每种容器的容量(cm),需求量及可变费用(元/件)如表所示. 容器代号 容量(cm) 需求量 可变费用(元/件) 331 1500 500 5 2 2500 550 8 3 4000 700 10 4 6000 900 12 5 9000 400 16 6 12000 300 18 ?1，生产j种容器?0，否则 由此可写出模型为 min z=1200?yjj+5x1+8x2+10x3+12 x4+16 x5+18x6 ?x?x?x?x?x?x?335023456每种容器分别用不同专用设备生产,其固定费用均为1200元.当某容器数量上不能满足需要?1?x6?300时,可用容量大的代替.问在满足需求的情况下,如何组织生产,使总的费用为最小. ?x?x?700 6?5 ? x4?x5?x6?1600? st.? x3?x4?x5?x6?2300 ?x?x?x?x?x?28503456?2?xj?My（，?，6）jj?1?? xj?0 ? y?0或1（ j?1，?，6） ?j第 2 页 共 8 页

西安邮电学院试题库管理系统——试题表

要在长度为L的一根圆钢上截取不同长度的零件毛坯，毛坯长度分别有n种，分别为 aj（j=1,2,…..,n）。每种毛坯应当各截取多少根，才能使圆钢残料最少？如果求毛坯的总根数最多，应当怎样截取毛坯？ 设截取长为aj的毛坯xj根（j=1，2……,n）。 使圆钢残料最少的下料问题数学模型为 minz1?L??ajxjj?1n?n ax?L(j?1,2,...n)??jj?j?1?x?0 且为整数 j?1,2,......n?j由于z2=L-z1= n?axjj?1nj是实际用料总长，故问题的目标函数等价于 maxz2? ?ajxj j?1如果求毛坯总根数最多则可将目标函数改为 maxz3? ?xj j?1n 某地准备投资D元建民用住宅。可以建住宅的地段有n处：A1，A2 A3，…. An，在Aj处每幢住宅的造价为dj，最多可造aj幢。应当在哪处建住宅，分别建几幢，才能使住宅总数最多？ 设在Aj处建住宅xj幢（j=1，2…..n）。 数学模型为 maxz??xjj?1n?n??djxj?D j?1???0?xj?aj?n）?xj是整数（j?1,2.....??11180302 某公司今后三年内有五项工程可以考虑投资 设xj???1,投资j项目?0，不投资j项目 最优解X＝(1,1,1,0,1)，Z=110万元。 maxZ?30x1?40x2?20x3?15x4?30x5?5x1?4x2?5x3?7x4?8x5?30?x?7x?9x?5x?6x?252345?1??8x1?2x2?6x3?2x4?9x5?30?xj＝0或1,j?1,,5? 求最优解和投资的最大收益 用分枝定界法求解下列整数规划问题 max z=3x1+2 x2 最优解z=14, x1=4, x2=1; ?2x1?3x2?14?st. ?x1?0.5x2?4.5 ?x,x?0且为整数?12 用分枝定界法求解下列整数规划问题 max z=2x1+3 x2 最优解z=14, x1=4, x2=2; ?5x1?7x2?35??4x1?9x2?36?x,x?0且为整数st. ?12 用分枝定界法求解下列整数规划问题 max z=x1+ x2 最优解z=5, x1=5, x2=0;或x1=4, x2=1 ?2x1?5x2?16?st. ?6x1?5x2?30 ?x,x?0且为整数?12 用分枝定界法求下列整数规划。 最优解和最优值如下： maxz?2x1?x2?x1?x2?5??x?x?0 ?12??6x1?2x2?21??x1,x2?0且为整数 用分枝定界法解下列整数规划： x*?(3,1)T,z*?7 最优解和最优值如下： maxz?2x1?3x2??x1?x2?2?47x?8x?188 ?12??3x1?2x2?19??x1,x2?0且为整数 用割平面法求解下列整数规划问题 max z=7x1+9 x2 x*?(3,5)T,z*?21 最优解z=55, x1=4, x2=3; ??x1?3x2?6?st. ?7x1?x2?35 ?x,x?0且为整数?12第 3 页 共 8 页

西安邮电学院试题库管理系统——试题表

用割平面法求解下列整数规划问题 max z=4x1+5 x2 最优解z=13, x1=2, x2=1; ?3x1?2x2?7?x?4x?5?12st. ? 3x?x?22?1??x1,x2?0且为整数 用割平面法求解下列整数规划问题 max z=4x1+6 x2+2 x3 最优解z=26, x1=2, x2=1, x3=6; ?4x1?4x2?5??x?6x?5?12st. ? ?x?x?x?523?1??x1,x2,x3?0且为整数 用割平面法求解下列整数规划问题 max z=11x1+4x2 最优解z=34, x1=2, x2=3; ??x1?2x2?4?5x?2x?16?12st. ? 2x?x?42?1??x1,x2?0且为整数 分别用割平面法求解以下整数规划问题 maxz?x1?4x2?14x1?42x2?196 ?s.t.??x1?2x2?5?x,x?0且为整数?12 先求解相应的线性规划的最优解： z x1 x2 z x3 x4 z x3 x2 z x1 x2 z 1 0 0 x1 0 1 0 x2 0 0 1 z 1 0 0 x1 -3 [35] -1/2 x2 0 0 1 1 0 0 -1 14 -1 -4 42 [2] x3 0 1 0 x3 0 1 0 x3 3/35 1/35 1/70 x4 0 0 1 x4 2 -21 1/2 x4 1/5 -3/5 1/5 RHS 0 196 5 RHS 10 91 5/2 RHS 89/5 13/5 19/5 线性规划的最优解为x1=13/5，x2=19/5，max z=89/5。 对于x2=19/5， b2=19/5，I2=3，F2=4/5 y23=1/70，I23=0，F23=1/70；y24=1/5，I24=0，F24=1/5 构造附加的切割约束： 4/5-（1/70x3+1/5x4）≤0 即 1/70x3+1/5x4≥4/5 z x1 x2 x3 x4 x5 z x1 x2 x5 z x1 x2 x4 用割平面法解下列整数规划： z 1 0 0 0 x1 0 1 0 0 x2 0 0 1 0 x3 1/14 3/35 0 1/14 x4 0 0 0 1 x5 1 -3 1 -5 1 0 0 0 0 1 0 0 0 0 1 0 3/35 1/35 1/70 1/5 -3/5 0 0 0 1 RHS 89/5 13/5 19/5 -4/5 RHS 17 5 3 4 1/5 [-1/5-1/70 ] 得到整数解：x1=5，x2=3，x3=0，x4=4，x5=0，max z=17。 最优解和最优值如下： maxz?x1?x2?2x1?x2?6 ?4x?5x?20?12?x,x?0且为整数?12x*?(2,2)T,z*?4 第 4 页 共 8 页

西安邮电学院试题库管理系统——试题表

用割平面法求解以下整数规划 先求相应的线性规划问题，得到最优单纯形表 z x1 x2 z 1 0 0 x1 0 1 0 x2 0 0 1 x3 -2/5 -2/5 1/5 x4 -9/5 1/5 -3/5 RHS 44/5 4/5 8/5 minz?3x1?4x2?3x1?x2?4 ?s.t.?x1?2x2?4?x,x?0且为整数?12 选择一个非整数的基变量，例如x2=8/5，构造约束条件（3.4），其中 b2=8/5=1+3/5，I2=1，F2=3/5 y23=1/5=0+1/5，I23=0，F23=1/5 y24=-3/5=-1+2/5，I24=-1，F24=2/5 附加的约束条件Fr?nj?m?1?Frjxj?0为 3/5-（1/3x3+2/5x4）≤0 即 1/5x3+2/5x4≥3/5 将这个约束加到线性规划的最优单纯形表中，并增加一个松弛变量x5，得到 z x1 x2 x5 z 1 0 0 0 x1 0 1 0 0 x2 0 0 1 0 x3 -2/5 -2/5 1/5 [-1/5] x4 -9/5 1/5 -3/5 -2/5 x5 0 0 0 1 RHS 44/5 4/5 8/5 -3/5 用对偶单纯形法，x5离基，x3进基 已获得整数的最优解。 z z x1 x2 x3 x1 0 1 0 0 x2 0 0 1 0 x3 0 0 0 1 x4 -1 1 -1 2 x5 -2 -2 1 -5 RHS 10 2 1 3 1 0 0 0 用割平面法解下列整数规划： 最优解和最优值如下： maxz?4x1?3x2?4x1?4x2?17 ?2x?17?1?x,x?0且为整数?12 用割平面法解下列整数规划： x*?(3,1)T,z*?15 最优解和最优值如下： maxz?2x1?x2?x1?x2?6 ??x1?4x2?2?x,x?0且为整数?12 用割平面法解下列整数规划： x*?(5,1)T,z*?11 最优解和最优值如下： maxz?4x1?5x2?3x1?2x2?10 ??x1?4x2?11?x,x?0且为整数?12 用分枝定界法求下列整数规划。 x*?(2,2)T,z*?18 最优解和最优值如下： maxz??5x1?x2?2x37??2x?x?x?x?1234?2??2x?x?x?x?2 ?1235?x1,x2,x3,x4,x5?0???x3和x5为整数 用分枝定界法求下列整数规划。 x*?(0,2,0,1.5,0)T,z*?2 最优解和最优值如下： maxz??5x1?x2?2x3?3x1?10x2?50?7x?2x?28?12??x1,x2?0??x3为整数 x*?(4.857,3)T,z*??18.71429 11180303 设xj为投资第j个点的状态，xj=1或0，j=1,2,…,12 maxZ?400x1?500x2?450x3??400x12最优解：x1＝x5=x12=0，其余xj=1,总收益Z=3870万元，实际完成投资额8920万元 ?900x1?1200x2?1000x3??850x11?1000x12?9000?44771212 ?x?2,x?3,x?1,x?2,x?3,x?4??j?????jjjjjj?1j?1j?5j?5j?8j?8??x?1或0，j?1,,12?j 求最优解和总收益及实际完成的投资额。 用隐枚举法求解0—1规划问题 max z=3x1+2 x2-5 x3-2 x4+3 x5 最优解x1= x2=1, x3=x4= x5=0, z=5 ?x1?x2?x3?2x4?x5?4?7x?3x?4x?3x?8345?1st. ? ?11x1?6x2?3x4?3x5?3?xj?0或1(j?1,?,5)? 用隐枚举法求解0—1规划问题 max z=2x1- x2+5 x3-3 x4+4x5 最优解x1= x2=0, x3=x4= x5=1, z=6 ?3x1?2x2?7x3?5x4?4x5?6?st. ?x1?x2?2x3?4x4?2x5?0 ?x?0或1(j?1,?,5)?j第 5 页 共 8 页

西安邮电学院试题库管理系统——试题表

用隐枚举法求解0—1规划问题 max z=8x1+2 x2-4 x3-7 x4-5x5 最优解x1= x3=1, x2=x4= x5=0, z=4 ?3x1?3x2?x3?2x4?3x5?4?st. ?5x1?3x2?2x3?x4?x5?4 ?x?0或1(j?1,?,5)?j 已知下列五名运动员各种姿势的游泳成绩(各为50m)如表所示,试问如何从中选拔一个参加200m混合泳的接力队,使预期比赛成绩为最好. 单位:s 游泳姿势 仰泳 蛙泳 蝶泳 自由泳 由下列运动员组混合接力队:张仰泳,王蛙泳,钱蝶泳,赵自由泳,预期总成绩为126.2s. 赵 37.7 43.4 33.3 29.2 钱 32.9 33.1 28.5 26.4 张 33.8 42.2 38.9 29.6 王 37.0 34.7 30.4 28.5 周 35.4 41.8 33.6 31.1 应当分派业务员1去处理业务4，业务员2去处理业务2，业务员3去处理业务1，业务员4去处理业务3 公司在各地有四项业务，选定了四位业务员去分别处理。由于业务能力、经验和其他情况不同，四位业务员处理这四项业务的费用各不相同，费用估算见表。应当怎样分派这四位业务员，才能使四项业务得到处理，同时总的业务费用又最少？ （业务，业务员，费用） 业务 业务员 1 2 3 4 1 1100 600 400 1100 2 800 500 800 1000 3 1000 300 1000 500 4 700 800 900 700 有五项设计任务可供选择。各项设计任务的预题完成时间分别为3，8，4，10天，设计报应当选择设计任务3，4，5 酬分别为7，17，11，9，21千元。设计任务只能一项一项地进行，总的期限是20天。选 择任务时必须 满足下面的要求： （1）至少完成三项设计任务 ; (2 )若选择任务1，必须同时选择任务2； （3）任务3和任务4不能同时选择。 应当选择那些设计任务，才能使总的设计报酬最大 ？ 便民超市准备在城市西北郊新建的居民小区中开设若干连锁店。为方便购物，规划任一居xE= xH= xJ=1，其余xj为0 民小区至其中一个连锁店的距离不超过800m。表给出了新建的居民小区及离该居民小区半径800m内的各个小区，问该超市最少应在上述小区中建多少个连锁店及建于哪些小区内。 小区代号 A B C D E F G H I J K L 该小区800m半径内的各小区 ACEGHI BHI ACGHI DJ AEG FJK ACEG ABCHI ABCHI DFJKL FJKL JKL 设取第i种物品xi件（i=1，2，…，k），则规划问题可以写为 max s.t. z= v1x1 +v2x2 w1x1 +w2x2 x1, x1, x2, x2, +… +vkxk +… +wkxk … … xk xk为整数 ≤W ≥0 有一只背包，最大装载重量为W公斤，现有k种物品，每种物品数量无限。第i种物品每件重量为wi公斤，价值为vi元。每种物品各取多少件装入背包，使其中物品的总价值最高。 这个问题如果用线性规划求解，k个变量中将只有一个基变量大于0，其余k-1个非基变量都等于0，而且这个大于0的基变量一般情况下是非整数。这样的解显然是没有意义的。例如以下一个背包问题 max s.t. z= 17x1 +72x2 10x1 +42x2 x1, x1, x2, x2, +35x3 +20x3 x3 ≤50 ≥0 x3为整数 线性规划最优解为 x1=0，x2=50，x3=0 41而整数规划的最优解是 x1=1，x2=0，x3=2。 在最小成本问题中，设第j种设备运行的固定成本为dj，运行的变动成本为cj，则生产成本与设备运行时间的关系为 mins.t.z??djyj?cjxjj?1ijn 较运10 10 难 用 当xj?0?0fj(xj)?? ?dj?cjxj当xj?0设第j种设备运行每小时可以生产第i种产品aij件，而第i种产品的定货为bi件。列出使要满足定货同时使设备运行的总成本最小的问题的线性规划模型并求最优解。 ?axj?1nj?bii?1,2,?,m j?1,2,?,nxj?Myjxj?0,yj?0,1这里M是一个很大的正数。 当yj=0时，xj=0，即第j种设备不运行，相应的运行成本 djyj+cjxj=0 当yj>0时，0≤xj≤M，实际上对xj没有限制，这时相应的运行成本为 dj+cjxj 第 6 页 共 8 页

西安邮电学院试题库管理系统——试题表

男球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高及擅长位置见下表 队员 1 2 3 4 5 6 7 8 身高（m） 1.92 1.90 1.88 1.86 1.85 1.83 1.80 1.78 擅长位置 中锋 中锋 前锋 前锋 前锋 后卫 后卫 后卫 ?0队员j不出场设xj?? (j=1,2…..n) 1队员j出场?1maxz?(1.92x1?1.90x2?1.88x3?1.86x4?1.85x5?1.86x6?1.80x7?1.78x8)8?x1?x2?1?x?x?x?178?6 ??x1?x4?x6?2??x2?x6?1?x1?x2?x3?x4?x5?x6?x7?x8?5?8)??xj?0或1(j?1,2.......最优解为x1=x3=x4=x5=x7=1，x2=x6=x8=0 目标函数最优解为1.862 将问题改写为 max z=x1+2 x2+5 x3 出现阵容应满足以下条件： （1）中锋只能有一个上场； （2）至少有一名后卫； （3）如1号和4号上场，则6号不出场 ； （4）2号和6号至少保留一个不出场。 应当选择哪5名队员上场 ，才能使出场队员平均身高最高？ 用你认为合适的方法求解下述问题 max z=x1+2 x2+5 x3 ?|?x1?10x2?3x3|?15?st. ?2x1?x2?x3?10 ?x,x,x?0?123 解下列0-1型整数规划： （1?y）M??x1?10x2?3x3??15??x?10x?3x??15?My?123st. ? 2x?x?x?1023?1??x1,x2,x3?0，y?0或1求的解x1=0， x2=0， x3=10，y=1，z=50 无可行解 minx?5x1?7x2?10x3?3x4?x5?x1?3x2?5x3?x4?4x5?2??2x?6x?3x?2x?2x?0 12345????2x2?2x3?x4?x5?1?xj?0或（1j?1,2,3,4,5）? 解下列0-1型整数规划 最优解和最优值如下： maxz?2x1?x2?x3?x1?3x2?x3?2??4x2?x3?5??x1?2x2?x3?2?x?4x?x?423?1??x1,x2,x3?0或111180304 x*?(1,0,0)T,z*?2 用匈牙利法求解下述指派问题,已知效率矩阵如下: 9 10 12??7 ?13 ?12 16 17?? ?15 16 14 15???11 12 15 16 ?? 用匈牙利法求解下述指派问题,已知效率矩阵如下: 最优指派方案为x13= x22= x34= x41=1, 最优值为48; 8 2 10 3??3 ?8 ?7 2 9 7???6 4 2 7 5? ??8 4 2 3 5 ???10 6 9 10 ??9 ? 分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表所示。由于任务多与人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。 任务 人 甲 乙 丙 丁 最优指派方案为x15= x23= x32= x44= x51= 1, 最优值为21; A 25 39 34 24 B 29 38 27 42 C 31 26 28 36 D 42 20 40 23 E 37 33 32 45 最优分配方案为 甲-B 乙-D、C 丙-E 丁-A 需要分派五人去做五项工作，各人做各项工作的能力评分见表所示，应如何分配才能使总的利润最大？ （工作，人员，评分） 工作 人员 A1 A2 A3 A4 B1（平车） B2（考克） B3（卷边） B4（棚缝） 应当分派A1做B1，A2 做B3，A3做B4，A4做B5，A5做B2 中 运用 8 12 B5（打眼） 1.0 0 0 1.4 1.1 1.3 0 1.0 0 0.8 1.2 0 1.05 0 1.3 0 0 0 1.3 1.2 0.2 A5 1.0 0.9 0.6 0 分别解具有下列系数矩阵的最小化指派问题。 ?8?0??3??4??94261?9554??8926? ?3103?5895???00001??10000????00010? ??10000????01000?? 第 7 页 共 8 页

西安邮电学院试题库管理系统——试题表

分别解具有下列系数矩阵的最小化指派问题。 ?3162?12?19?1729??3540?1930???7230 41?40??22?? 33?2916223??30504120??293950384215557141224227?000010??0?01000???100000??? ?001000??000100???010000???? 分别解具有下列系数矩阵的最小化指派问题。 ?1011428??7?12111410?? ?5691214????131511107? 分别解具有下列系数矩阵的最小化指派问题。 ?00?1?0?01??00010??000? 000??001?0?0??0?? 0?0??0?? ?36?7?1?38??64?52??57?24536?4??8?? 7?43??26???001?0?10?100??000?000???000 11180305 下述整数规划问题： max z=20x1+10 x2+10 x3 当不考虑整数约束，求解相应线性规划问题得最优解为x1=10/3，x2=x3=0。用凑整数法时令x1=3，x2=x3=0，其中第二个约束无法满足，故不可行。 ?2x1?20x2?4x3?15?st. ?6x1?20x2?4x3?20 ?x,x,x?0且为整数?123说明能否用先求解相应的线性规划问题然后凑正的办法来求得该整数规划的一个可行解。

第 8 页 共 8 页

本文来源：https://www.bwwdw.com/article/ci28.html