西南交通大学运筹学模拟试题二

1、试题二试题代码：453 试题名称：运筹学考生注意：1 .本试题共 七 题,共皂页，请考生认真检查；2 .请务必将答案写在答卷纸写在试卷上的答案无效。题号一一三四五六七总分得分签字一、华津机器制造厂专为拖拉机厂配套生产柴油机，今年头四个月收到的订单数量分别为3000, 4500, 3500, 5000台柴油机。该厂正常生产每月可生产柴油机3000台，利用加班还可生产1500台。正常生产成本为每台 5000元，加班生产还要追加1500元成本，库存成本为每台每月200元。华津厂如何组织生产才能使生产成本最低，建立其线性规划模型。（20分）二、考虑线性规划问题：（25分）maxz=5x1 +12x2

2、+4x3x1 +2x2 + x3 壬 52x1 -x2 +3x3 = 2'乂乂 N0用单纯形法求解，得其终表如下：cj51240-MB-1bC BX Bx1x2x3x4x512x201-1/52/5-1/58/55A107/51/52/59/5cj -zj00-3/5-29/5-M+2/5X4为松弛变量，X5为人工变量，1 .上述模型的对偶模型为： ；2. 对偶模型的最优解为：3. 当两种资源分别单独增加一个单位时，目标函数值分别增加 和一1III4 .最优基的逆矩阵B-1=-5.如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？、求解下列各题（解题方法自选）（20分）mi

3、n z = 5x11 6x12 10x13 8x21 10x22 12x234x4x 5xqq|3 13233为1、2为3 = 1x2ix22 为3 = 1x31x32 为3 = 1、1 x21 x31 = 1、2 x22 如=1为3 x23 x33 = 1% = 1 或0（i = 1,2,3; j = 1,2,3）四、用隐枚举法求解下列 0-1规划问题（20分）max 5x1 7x2 10x3 3x4 x5x1 - 3x2 + 5x3 + x4 - 4x5 芝 2 一2x1 十6x2 3x3 2x4+ 2x5 芝0-2x2 +2x3- x4- x5 '1xj =01 （j =1,，5

4、）五、 用动态规划方法求解下列问题（25分）maxz - x1（1 - x2）x3x - x2 x3 三 1xj -0 j -1,2,3六、 今有三个仓库运送某种产品到四个市场上去，仓库的供应量是20, 20和100,市场需 求量是20, 20, 60和20,仓库与市场之间的路线上的容量如下表（容量零表示两点间无直接的路线可通）。用图论方法确定现有路线容量能否满足市场的需求，若不能，应修改哪条 线路的容量。（20分）1234供应量30100402000105020201040510020206020七. 下列叙述中正确的是（）（20分）1. 图解法与单纯形法，虽然求解的形式不同，但从几何上理解

5、，两者是一致的；2. 若线性规划的原问题有多重最优解，则其对偶问题也一定具有多重最优解；3. 如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k,最优调运方案将不会发生变化；n n4. 对于极大化问题maxZ=%珈为令C = ma&如=C - Cj转化为"、化问n nmin W - '、' bij Xj题旦ji ,则利用匈牙利法求解时，极大化问题的最优解就是极小化问题的最优解，但目标函数相差：n+c;5. 如果图中从Vi至各点均有惟一的最短路，则连接至其他各点的最短路在去掉重复部 分后，恰好构成该图的最小支撑树。试题二答案、解：设xi代表第i月正

6、常生产的柴油机数量, yi代表第i月加班生产的柴油机数量, zi代表第i月末的库存量，则Zi=4厂 min Z =5000E 为 +6500E yj +200E zix1 +y 2 0 0 0Zi +x2 +y2 >4500V Z2 + x3 + y3 芝 3 5 0 0z3 + x4 + y4 = 5 0 0 0xi,yi,Zi",i =1,2,3,4二、解：'minW =5y1 +2y2yi +2y2 >5< 2yiy2 32y +3y2 芝4、,* _/29、_ 29yi一一(一亏)一亏 由1、对偶模型yi b0,y2无约束2、由 单 纯 形 表 可

7、看 出ysi 乂为=0;ys2 区乂2 = 0,而x 0,x 0ys1 = 0, ys2 = 02则对偶问题的第一、二个约束是紧的，可解出y2 - -5将yi,y2代入第三个约束，满足约束条件，贝u y* =(yi,y2)T =(W,"hw* =峭3、5 和 22/5 1/5、4、B= l1/52/5 >5、如果原问题增加一个变量，则对偶问题就增加一个约束条件，它的可行域要么减少,要么不变，绝对不会变大。610 -110 1245584优解 X21 =1,X2I24600以33=1，其余为Z* =19四、解：将最大化问题化为极小化问题，并将系数转为正，即令Xi=1 一 xi ,

8、整理得厂minZ =5x1 +7x2 +10x3 +3x4 + x5 -26x - 3x2 ' 5X3 ' X4 - 4x5 2-2xi 6x2 - 3x3 - 2x4 2x5 - 1-2x2 ' 2X3 - X4 - X5 -3'r、.xj' =0或 1( j =1,2, 5)X2 =0X21011=012综上，该0-1规划无可行解五、解：按三个变量划分为三个阶段，状态转移方程第三阶段：f3（S3）"max'. i = S3,X3* =S20 £ x3 誓3r:''；12第二阶段：f2（S2）=maxX2（S3），= max x2（S2 - 冷），=4 S20X2S20 x2_S2其中 x2* =捉（X2=1-X2） 12 :'12 】28第一阶段：f1（S1）=max 次1 0S2 =maxX1 彳（2 - x）=五0三x1三20三x1三2其中x1* =旨二最优解 X1* =%X2* =1 X2* =1 一号=：,X3* =号7* - -8-Z 27六、解：依题意，首先给出一个可