《运筹学》试卷及答案002

1、运筹学试卷一、单项选择题（1x5分）线性规划（以下简称LP）模型中自由变量可以用两个非负变量之（）代换。 TOC o 1-5 h z A.和B.差C.积D.商LP原问题的第i个约束条件是“二”型，则对偶问题的变量*是（）。A.剩余变量B-自由变量 C.松弛变量 D.非负变量基可行解中的非零变量的个数小于约束条件数时，该LP问题可求得（）。A.基本解 B.多重解 C-退化解 D.无解运筹学中著名的“TSP问题”是指（）。A.背包问题B.中国邮递员问题C.哥尼斯堡七桥问题D.货郎担问题用大M法求解极大化的LP问题时，人工变量在目标函数中的系数是（）。A. -M B. M C. 1 D. -1二、判

2、断正误（对者打“”，错者打“X”。1x5分）线性规划问题的最优解不一定只在可行域的顶点上取得。（）对偶单纯形法是求解线性规划对偶问题的一种算法。（）容量网络中从发点到收点的最大流流量等于分离发点和收点的任一割集的容量。（）若整数规划问题存在可行解，则其可行解集合是凸集。（）目标规划模型中可以没有绝对约束，但不能没有目标约束。（）三、（25分）某企业生产3种产品，这些产品均需使用A、B两种原料，每种产品的原料单耗（kg/ 件）、单位利润以及这两种原料在计划期内的可供应量（kg）如下表。该企业应如何安排3种产品生 产，可使企业所获利润最大？产品原料IIIm供应量A234100B42380单位利润（

3、元/件）201518要求：建立该问题的线性规划模型；（3分）用单纯形法求该问题的最优解及最优值；（15分）产品III的单位利润在什么范围内变动时，最优解不变？ （3分）直接写出该LP的对偶问题及其最优解。（4分）四、（10分）某家电厂商生产A、B、C三种规格的某种家电产品，装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为2小时、2.5小时和3小时，生产线每月正常工作时间为480 小时；三种产品销售后，每台获利分别为150、180和200元；每月销售量预计分别为90、70和 50台。该厂经营目标如下：P1：根据三种产品的需求变动趋势，产品A按预计销量生产、产品B的产量不超过预计销量、

4、产品C的产量不低于预计销量为宜；P2：利润指标为每月不低于3万元；P3：充分利用生产线的正常工作时间；P4：产品旺销时可以适当加班，但每月加班时间不宜超过40小时。试根据上述资料建立该家电厂商产品生产计划的目标规划模型。（不求解）五、（15分）指派5位员工去完成5项不同的工作，每人做各项工作所需时间（单位：天）如下 表所示。试用匈牙利法求最优指派方案及最少总时间。作 员工ABCDEI94646II56353m4149119W1211437V28584六、（10分）有总量为a和b的两种资源，可用于n种产品的生产。如果第一种资源以数量尤、 第二种资源以数量y.分配于第i种产品的生产，其收益为g（x

5、 y.） , （1=1,2,0）如何分配这两种 资源于n种产品的生产活动可使总收益最大？试建立该问题的动态规划模型（不求解）。（提示建立动态规划模型包括：确定解法（顺序或逆序）；划分阶段；定义状态变量、状态集合、 决策变量、允许决策集合、状态转移方程、阶段指标、最优指标函数；写出动态规划基本方程）七、（15分）用Ford-Fulkerson算法求图1中容量网络的最大流和最小割集。图中弧旁的数字表示（%, f（提示 求解过程应写出，并在图上做相应的标记。一个可行流用一张图表示）八、（15分）已知产销平衡运输问题表1所示。试检验表1中的基可行解是否是最优解。如不是， 用闭回路法对表中的解进行调整，

6、求出最优解及最小总运费。（提示 应简要写出求解过程，并 将有关数据填入表中。一个基可行解用一张表表示）、销地 产地B1B2B3B4产量A1_410535060A2h.40b.35Lah.75A3_8_b.70U2090需求量40457070运筹学试卷一、单项选择题（1x5分）B2.B3.C4.D5.A二、判断正误（对者打“”，错者打“X”。1x5分）1. ”2. X 3. X 4. X 5.”三、（25分）解：（3分）设产品I、II、m在计划期内产量分别为、x2、，由题意，该问题的LP模型为:max z = 20 x +15 x +18 x2x + 3x + 4x 100s.t. 4x + 2

7、x + 3x 0, j= 1,2,3i j（15分）在约束中分别添加松弛变量x4、x5将LP化为标准形式，列单纯形表求解:c.j20151800b0CBXBx1x2x3x4x50 x423410100500 x 5_423018020b-i201518000.换入、x5换出:50 x4025/21-1/260300 x11/23/401/42040b-i0530-5-400.x2换入、x4换出:50 x2015/41/2-1/43040*101/8-1/41/85b -d00-13/4-5/2-15/4-550.7、0，.得最优解：X*=（5,30,0,0,0）T，最优值 z*=5507x3是

8、非基变量，故当如0，即% p3=13/4，亦即c320J 3“ +S 154y1 +3y2 18-yy2 0对偶问题最优解：Y*=（ 5/2,15/4）t，最优值w*=550评分标准：正确设定决策变量:1分；正确列出LP模型:2分。化标准形式、答案各1分，第1张单纯形表3分，第2,3张单纯形表各5分；3.3 分。4.正确列出对偶问题模型:3分；最优解1分。个别数据错误酌情扣分。四、（10分）解：设计划期内A、B、C三种产品的产量分别为,%,%，由题意，该问题的GP模型 为：min P (d + + d - + d -1112气+X +3+ d +), P d -, Pd -, P d +32

9、43 54 6d- d+ = 90d- d+ = 70d - d + = 5033st A150 气 +180 x 2 + 200 x 3 + d - d + = 300002 x + 2.5 x + 3 x + d - d + = 480 TOC o 1-5 h z 12355d + + d - d + = 40566 HYPERLINK l bookmark71 o Current Document x 0, j = 1,2,3, d -, d + 0, i = 1, 6l ji i评分标准：正确设定决策变量:2分；正确列出目标规划模型:8分。个别条件列错酌情扣分。五、（15分）解：化简系

10、数矩阵:C =94646-5020256353230204149119010575121143798104_28584 _06362 _5 2025 2027 020223 _0 223 _0 2 4 3020I 10 575/ 10 575-2 一0 83534 8 -4-98十一一 4-11 8 104/ 6362 -/结 6 3 6 2 -20 4140圈出C中的独立0元素:=C，/+2C中只有4个独立0元素，需要继续变换:用最少直线数覆盖所有0元素，未被直线覆盖的元素中 的最小元素是2,则未被直线覆盖的行中每个元素-2,被直线覆盖的列中每个元素+2,得到C，。 圈出C，中的独立0元素：

11、72024320835311814-0414.最优指派方案为I做B工作；II做C工作；III做A工作；IV做D工已得到5个独立0元素。作；V做E工作。总耗时为4+3+4+3+4=18 （天）。评分标准：变换系数矩阵得到C : 3分；进一步变换系数矩阵得到C，： 7分；圈出5个独立0 元素、给出最优指派方案：5分。个别数据错误酌情扣分。六、(10分)解:建立该问题的动态规划模型如下：采用逆序解法(顺序解法亦可)；阶段：按产品划分阶段，每种产品为一个阶段，k=1,2,.,.n状态变量状态变量sk=(Xk，Yk)，其中：Xk:分配用于生产第k至第n种产品的第一种资源数;Yk:分配用于生产第k至第n种

12、产品的第二种资源数。k状态集合：S1=(a,b), S 1=(0, 0), (0, 0)Sk(a,b), k=2,3,.,n决策变量uk=3k，yk)，n其中:用于第k种产品生产的第一种资源数,yk：用于第k种产品生 产的第二种资源数。允许决策集合:DJXYQ=3u yQ|0 x X，0 孔, k=1,2,.,nk k k kkk k k kJ状态转移方程：Xk+1= Xk- xk , Yk+1= Yk-yk，k=1,2,.,n阶段指标:gk(xk,yk) ， k=1,2,.,n最优指标函数f(Xk,Yk)表示表示当分配于第k种产品至第n种产品两种资源数量为Xk和Yk时 的最大收益。(10)D

13、P基本方程为:fk ( X k ,七)=maxg (x , y ) + f (X - x , Y - y ) k=n,n-1,.,2,1k k k k+1 k k k kf (sn +1n +1评分标准:(1)(10)项每项1分.七、(15分)解：(1)标号过程：先给吃标以(0，+8)。检查vs的相邻未标号点，发现vr V2符合标号条件，故 给 V 以标号(vs,min +8丛去 )=(vs,2)；给 V以标号(vs,min (+,cs2-fs2)= (vs,2)。继续标号 过程，给 v 以标号(v?,min 2,c23-f23 )=(v2,2);给 vt 以标号(v ,min 2, c 3.

14、)= (v ,2)。至此 3tv已得到标号，说明存在一条可增广链：V -V2V 一V，如图1。转调整过程。ts 2 3 I(vs,2)(2)调整过程：沿可增广链调整流量，调整量6=叫=2,即令可增广链上所有前向弧的流量增加2。 调整后得到的可行流如图2：重新标号：去掉所有标号，对新的可行流重新标号。给Vs标(0,+8),给V以标号(vs,min +8丛1去)= (vs,2)。至此标号进行不下去，而vt未得到 标号，说明图中的流已是最大流。最大流量w(f * ) =f4t+f3 t=16。最小割集,=（v，v ），（v，v ） ,（v ,v ）,如图2中的虚线所示。最小割集的容量为：c（S,S）=c +S 21314S1c13+c14=10+3+3=16,与最大流的流量相等。评分标准:（1）、（2）、（3图1、图2各3分。若算法步骤和图不完整,可适当扣分。八、（15分）解：闭回路法求得表中基可行解的非基变量的检验数，填入表1中空格的左下角。 */q11*， - 7 I/ .、“，1 /“，122221、*，11 /，I * X “，12,x21=1