《运筹学》试卷09

一、单项选择题(15分）

1. 线性规划(以下简称LP)模型中自由变量可以用两个非负变量之（ ）代换。 A．和 B．差 C．积 D．商

2.LP原问题的第i个约束条件是“=”型，则对偶问题的变量yi是（ ）。 A．剩余变量 B．自由变量 C．松弛变量 D．非负变量

3.基可行解中的非零变量的个数小于约束条件数时，该LP问题可求得( ）。 A．基本解 B．多重解 C．退化解 D．无解 4.运筹学中著名的“TSP问题”是指 ( ) 。

A.背包问题 B.中国邮递员问题 C.哥尼斯堡七桥问题 D.货郎担问题 5.用大M法求解极大化的LP问题时，人工变量在目标函数中的系数是（ ）。 A. -M B. M C. 1 D. -1

二、判断正误（对者打“√”，错者打“×”。15分）

1.线性规划问题的最优解不一定只在可行域的顶点上取得。 （ ） 2.对偶单纯形法是求解线性规划对偶问题的一种算法。 （ ）

3.容量网络中从发点到收点的最大流流量等于分离发点和收点的任一割集的容量。（ ） 4.若整数规划问题存在可行解，则其可行解集合是凸集。 （ ） 5.目标规划模型中可以没有绝对约束，但不能没有目标约束。 （ ）

三、(25分) 某企业生产3种产品，这些产品均需使用A、B两种原料，每种产品的原料单耗(kg/件)、单位利润以及这两种原料在计划期内的可供应量(kg)如下表。该企业应如何安排3种产品生产，可使企业所获利润最大？

产品 Ⅰ Ⅱ Ⅲ 供应量 原料 A 2 3 4 100 B 4 2 3 80 单位利润(元/件) 20 15 18 要求：

1.建立该问题的线性规划模型；（3分） 2.用单纯形法求该问题的最优解及最优值；（15分）

3.产品Ⅲ的单位利润在什么范围内变动时，最优解不变？（3分） 4.直接写出该LP的对偶问题及其最优解。（4分）

四、(10分) 某家电厂商生产A、B、C三种规格的某种家电产品，装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为2小时、2.5小时和3小时，生产线每月正常工作时间为480小时；三种产品销售后，每台获利分别为150、180和200元；每月销售量预计分别为90、70和50台。该厂经营目标如下：

P1：根据三种产品的需求变动趋势，产品A按预计销量生产、产品B的产量不超过预计销量、产品C的产量不低于预计销量为宜； P2：利润指标为每月不低于3万元； P3：充分利用生产线的正常工作时间；

P4：产品旺销时可以适当加班，但每月加班时间不宜超过40小时。 试根据上述资料建立该家电厂商产品生产计划的目标规划模型。（不求解）

五、（15分）指派5位员工去完成5项不同的工作，每人做各项工作所需时间（单位：天）如下表所示。试用匈牙利法求最优指派方案及最少总时间。

工作 员工 Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ A 9 5 4 12 2 B 4 6 14 11 8 C 6 3 9 4 5 D 4 5 11 3 8 E 6 3 9 7 4 六、（10分）有总量为a和b的两种资源，可用于n种产品的生产。如果第一种资源以数量xi、第二种资源以数量yi分配于第i种产品的生产，其收益为g(xi, yi) , (i=1,2,…,n)。如何分配这两种资源于n种产品的生产活动可使总收益最大？试建立该问题的动态规划模型(不求解)。

（提示 建立动态规划模型包括：确定解法(顺序或逆序)；划分阶段；定义状态变量、状态集合、决策变量、允许决策集合、状态转移方程、阶段指标、最优指标函数；写出动态规划基本方程） 七、（15分）用Ford-Fulkerson算法求图1中容量网络的最大流和最小割集。图中弧旁的数字表示(cij，fij)。 （提示 求解过程应写出，并在图上做相应的标记。一个可行流用一张图表示）

v1 (8,6) (3,3) (3,3) (6,0) (10,8) (5,2) (6,6) v2 图1

v4

八、 (15分)已知产销平衡运输问题表1所示。试检验表1中的基可行解是否是最优解。如不是，用闭回路法对表中的解进行调整，求出最优解及最小总运费。 （提示 应简要写出求解过程，并将有关数据填入表中。一个基可行解用一张表表示）

(9,9) v3 (8,5) vs vt

表1 销地 产地 B1 B2 4 5 B3 3 B4 2 产量 7 A1 A2 A3 需求量 50 10 3 2 5 40 35 8 7 2 70 20 60 75 90

4 40 45 70 70