中国矿业大学：《运筹学》课程教学资源（作业习题）测试题二（题目）

测试题二一、判断正误与填空（正确的在括号内打“√”，错误的打“×”，每小题2分，共10分）1．在单纯形法选代中，任何从基变量中替换出来的变量在紧接着的下一次()选代中可能会再进入基变量。2．若线性规划与其对偶规划都有可行解，则一定都有最优解，并且它们的()目标函数最优值相等。()3.树是其同阶连通图中边数最少的。，负4.目标规划中正偏差变量表示偏差变量表示5．设有整数规划：maxz = 3x, +2x2[2x,+3x,≤14s.t.j x +0.5x2 ≤4.5[xj,x,≥0,x,x,是整数其相应线性规划的最优解如下表所示：2300xiX23x4012.51/2-1/2X2103. 25-1/43/4x100g;-1/4-5/4则可以构造的割平面为二、(20分)已知线性规划：maxz=3x,+2x,+5xx+2x+x,≤4303x,+2x,≤460X, +4x,≤420x, ≥0, i=1,2,31

1 测试题二 一、判断正误与填空（正确的在括号内打“√”，错误的打“×”，每小题 2 分， 共 10 分） 1. 在单纯形法迭代中，任何从基变量中替换出来的变量在紧接着的下一次 迭代中可能会再进入基变量。 （ ） 2. 若线性规划与其对偶规划都有可行解，则一定都有最优解，并且它们的 目标函数最优值相等。 ( ) 3. 树是其同阶连通图中边数最少的。 （ ） 4. 目标规划中正偏差变量表示 ，负 偏差变量表示 。 5．设有整数规划： 其相应线性规划的最优解如下表所示： 2 3 0 0 x1 x2 x3 x4 x2 x1 2.5 3.25 0 1 1/2 -1/2 1 0 -1/4 3/4 σj 0 0 -1/4 -5/4 则可以构造的割平面为 。 二、(20 分)已知线性规划：                    0, 1,2,3 4 420 3 2 460 2 430 max 3 2 5 1 2 1 3 1 2 3 1 2 3 x i x x x x x x x z x x x i             1 2 1 2是整数 1 2 1 2 1 2 , 0, , 0.5 4.5 2 3 14 . . maxz 3 2 x x x x x x x x s t x x

①(5分)求其最优解。②5分）写出三种资源的影子价格，并说明哪些是紧缺的，哪些是非紧缺的。③(5分）求使最优解不变的c2的取值范围。④5分）若第一种资源的资源量变为450，最优解是否发生变化，若不变说明理由，若变求出新的最优解。三、（15分）已知线性规划：mim=2x,+5x3Xi+x≤22x, + x, + 6x, ≥ 6x, -x2 +3x = 0[x,≤0,x无约束x≥0①(5分)写出其对偶问题。②(5分若用大M法求解，写出相应的扩充问题（不求解）。，求其对偶规划的最优解。③5分)若原规划的最优解是X*=(0,2，3四、（15分）已知运输问题的供需关系表与单位运价表见下表：销地甲乙丙产量产地1211200452403233303020销量20①（10分）用表上作业法求最优运输方案。②(5分）若三个产地的物资未运出，则需支付存储费用，若它们的单位存储费分别为5.4.3，问最优运输方案是否发生变化？若不变说明原因，若变求出新的最优解。五、（10分）用逆序法求解下列整数规划：2

2 ①(5 分)求其最优解。 ②(5 分)写出三种资源的影子价格，并说明哪些是紧缺的，哪些是非紧缺的。 ③(5 分)求使最优解不变的 c2的取值范围。 ④(5 分) 若第一种资源的资源量变为 450，最优解是否发生变化，若不变说 明理由，若变求出新的最优解。 三、(15 分)已知线性规划：                    0, , 0 3 0 2 6 6 2 min 2 5 1 2 3 1 2 3 1 2 3 1 3 2 3 x x x x x x x x x x x z x x 无约束 ①(5 分)写出其对偶问题。 ②(5 分)若用大 M 法求解，写出相应的扩充问题（不求解）。 ③(5 分)若原规划的最优解是 T X ) 3 2 (0, 2, *  ，求其对偶规划的最优解。 四、（15 分）已知运输问题的供需关系表与单位运价表见下表： 甲 乙 丙 产量 1 1 2 1 20 2 0 4 5 40 3 2 3 3 30 销量 30 20 20 ①(10 分)用表上作业法求最优运输方案。 ②(5 分)若三个产地的物资未运出，则需支付存储费用，若它们的单位存储 费分别为 5,4,3，问最优运输方案是否发生变化？若不变说明原因，若变求 出新的最优解。 五、（10 分）用逆序法求解下列整数规划： 销 地 产 地

maxz=6x, +7x,+2x3[x, + 2x, +3x, ≤ 4s.t.[x,≥0,x,是整数六、（10分）现有容量网络如下图所示，弧旁边的数字表示弧的容量，试求从起点A到终点H的最大流和最小割。1FHC七、（10分）设一对策的高得矩阵为：(3-1-3-33-1A=-4-33判断其是否均衡对策？若是说明理由；若不是说明对策值的取值范围，并写出求解最优混合策略的相应的线性规划。八、（10分）某商店拟购进一种商品出售。经估算，在未来旺季中每售出一箱可净得利润3千元，如旺季过后只能降价出售，每箱要赔本1千元。这种商品的需求情况经统计分析，具有以下分布规律：23需求量R(箱)0145概率P(R)0.050.100.250.350.150.10试写出损益矩阵并用最大期望收益准则求最优进货量。3

3           x j x j是整数 x x x s t z x x x 0, 2 3 4 . . max 6 7 2 1 2 3 1 2 3 六、（10 分）现有容量网络如下图所示, 弧旁边的数字表示弧的容量,试求 从起点 A 到终点 H 的最大流和最小割。 七、（10 分）设一对策的赢得矩阵为：                  4 3 3 3 3 1 3 1 3 A 判断其是否均衡对策？若是说明理由；若不是说明对策值的取值范围， 并写出求解最优混合策略的相应的线性规划。 八、（10 分）某商店拟购进一种商品出售。经估算，在未来旺季中每售出一 箱可净得利润 3 千元，如旺季过后只能降价出售，每箱要赔本 1 千元。这 种商品的需求情况经统计分析，具有以下分布规律： 需求量 R(箱) 0 1 2 3 4 5 概率 P(R) 0.05 0.10 0.25 0.35 0.15 0.10 试写出损益矩阵并用最大期望收益准则求最优进货量。 A B C D G F 9 8 2 2 8 3 8 2 7 5 4 H 1