运筹学.doc

试题一一、某炼油厂生产三种牌号的汽油，70#，80#和85#汽油。每种汽油有不同的辛烷值和含硫量的质量要求并由三种原料油调和而成。每种原料也有不同的质量指标。每种原料每日可用数量、质量指标和生产成本见表1，每种汽油的质量要求和销售价格见表2。问该炼油厂如何安排生产才能使其利润最大？假定在调和中辛烷值和含硫量指标都符合线性相加关系。试建立数学模型。（25分)表 1 序号i原料辛烷值含硫量（）成本（元/吨）可用量（吨/日）1直馏汽油621.560020002催化汽油780.890010003重整汽油900.21400500 表2 序号j产品辛烷值含硫量（）销售价（元/吨）170汽油701900280汽油8011200385汽油850.61500二、用对偶单纯形法求解下列线性规划问题：（25分）三、已知某运输问题的产销平衡表与单位运价表如下表所示，B2地区需要的115单位必须满足，试确定最优调拨方案。（20分）Ai BjB1B2B3B4B5产量A1101520204050A22040153030100A33035405525130销量25115603070四、从甲, 乙, 丙, 丁, 戊五人中挑选四人去完成四项工作，已知每人完成各项工作的时间如下表所示。规定每项工作只能由一个人去单独完成，每个人最多承担一项工作，假定甲必须保证分配到工作，丁因某种原因不同意承担第四项工作。在满足上述条件下，如何分配工作，使完成四项工作总的花费时间最少。（20分）人 工作一二三四甲1051520乙210515丙3151413丁15276戊94158五、求V1到各点的最短路及最短路径。（20分）六、某公司有资金4百万元向A，B，C三个项目追加投资，各个项目可以有不同的投资额（以百万元为单位），相应的效益值如下表。问怎样分派资金，使总效益值最大，试用动态规划方法求解。（25分）项目投资额01234A3841486066B4042506066C3864687876七、用单纯形法解线性规划问题，如何判断下列问题：（15分）1. 无可行解；2. 有多重解；3. 有无界解。 试题一答案一、 解：设代表第i种原料混入第j种产品中的数量，其中i=1，2，3；j=1，2，3；则 二、 解：原问题可化为：2 1 0 0 0 2 0 0 1 1 1 0 00 2 1 1 00 -4 -6 0 155-90 -1 -2 0 0- 1/4 1/3 - -2 0 0 1 0 1/2 0 1/40 0 -2 1 1/20 1 3/2 0 -1/40 0 -1/2 0 -1/4-31/4三、 解：将原问题改成产销平衡问题，并用沃格尔法给出初始解得： 销产产 105 1550 2020 205 403550-15 2010 4010 1560 3030 30101000 305 3565 4020 5520 25651305 015 MM-10 05 0-10 0520-20销251156030703002030153020此方案还不是最优，需要调整 销产产 1015 1550 2030 2015 403550-25 2025 400 1560 3015 3001000 3015 3565 4030 5530 2565130-5 010 MM-10 015 015 0520-30销251156030703002040153030此时检验数均大于或等于0，为最优解 四、 解：10 5 15 20 M 8 3 10 12 M 5 0 7 9 M-32 10 5 15 0 0 8 0 7 0 0 8 0 7 0 3 15 14 13 0 1 13 9 5 0 1 13 9 5 0 15 2 7 M 0 13 0 2 M-8 0 13 0 2 M-8 09 4 15 8 0 7 2 10 0 0 7 2 10 0 04 0 6 8 M-30 9 0 7 10 13 8 4 012 0 1 M-9 07 3 10 0 1此时，费用最小，其中，丙 一， 甲 二， 乙 三， 戌 四 五、 解： 0* 11 9* 10 11 10* 20 11* 21 20 21 21* 21* 28 25* 11 ： 9 ： 10 ： 21 ： 20 ： 25 ： 六、 解： 阶段：以向某一项目投资作为一个阶段，如此可划分为三个阶段。 状态变量：以可以提供的投资额作为状态变量 ，其范围为0，1，2，3，4百万 决策变量：以给某项目投资的金额作为决策变量，则 状态转移方程： 0 1 2 3 4*01234384148 60 66384148606601234 0 1 2 3 4*0123440+3840+41 42+3840+48 42+41 50+3840+60 42+48 50+41 60+3840+66 42+60 50+48 60+41 66+38788188100106000，200 0 1 2 3 4*438+106 64+100 68+88 78+81 76+781641总效益最大值为164，其中。 七、 解：1、无可行解：最终表人工变量不为零；或右侧常数 ，对应的；2、有多重解：（非基变量）且至少有一个为零。3、有无界解：非基变量的检验数 ，且对应的系数列向量。试题 二 一、华津机器制造厂专为拖拉机厂配套生产柴油机，今年头四个月收到的订单数量分别为3000，4500，3500，5000台柴油机。该厂正常生产每月可生产柴油机3000台，利用加班还可生产1500台。正常生产成本为每台5000元，加班生产还要追加1500元成本，库存成本为每台每月200元。华津厂如何组织生产才能使生产成本最低，建立其线性规划模型。（20分）二、考虑线性规划问题：（25分）用单纯形法求解，得其终表如下： 51240-M B-1b12 01-1/52/5-1/58/55 107/51/52/59/500-3/5-29/5-M+2/5X4为松弛变量，X5为人工变量，1上述模型的对偶模型为： ；2对偶模型的最优解为： ；3当两种资源分别单独增加一个单位时，目标函数值分别增加 和 ；4最优基的逆矩阵B-1 = 5如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？ .三、求解下列各题（解题方法自选）（20分）四、用隐枚举法求解下列0-1规划问题（20分） 五、用动态规划方法求解下列问题（25分） 六、今有三个仓库运送某种产品到四个市场上去，仓库的供应量是20，20和100，市场需求量是20，20，60和20，仓库与市场之间的路线上的容量如下表（容量零表示两点间无直接的路线可通）。用图论方法确定现有路线容量能否满足市场的需求，若不能，应修改哪条线路的容量。（20分）市场仓库1234供应量130100402020010502032010405100需求量20206020七下列叙述中正确的是 （ ）（20分）1. 图解法与单纯形法，虽然求解的形式不同，但从几何上理解，两者是一致的；2. 若线性规划的原问题有多重最优解，则其对偶问题也一定具有多重最优解；3. 如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化；4. 对于极大化问题max Z =令转化为极小化问题，则利用匈牙利法求解时，极大化问题的最优解就是极小化问题的最优解，但目标函数相差： n+c；5. 如果图中从至各点均有惟一的最短路，则连接至其他各点的最短路在去掉重复部分后，恰好构成该图的最小支撑树。试题二答案一、 解：设代表第i月正常生产的柴油机数量， 代表第i月加班生产的柴油机数量， 代表第i月末的库存量，则=4 二、 解：1、 对偶模型 2、 由单纯形表可看出，由于 则对偶问题的第一、二个约束是紧的，可解出将代入第三个约束，满足约束条件，则3、5和24、 5、如果原问题增加一个变量，则对偶问题就增加一个约束条件，它的可行域要么减少，要么不变，绝对不会变大。三、 解：此题可看作指派问题求解：5 6 10 1 2 5 0 1 4 0 0 38 10 12 4 6 7 0 2 3 0 1 24 4 5 0 0 0 0 0 0 1 0 0四、 解：将最大化问题化为极小化问题，并将系数转为正，即令，整理得 综上，该0-1规划无可行解五、 解：按三个变量划分为三个阶段，状态转移方程第三阶段： 第二阶段： 其中 第一阶段： 其中 六、 解：依题意，首先给出一个可行流在初始流上增流到不能再增，得到如下结果：此时已不能再增流，流量 ，不能满足市场的需求量。应修改仓库3到市场3和4的容量，分别增流10和5即能满足需求。七、 解：3、5正确。试题三一、用单纯形法求解下述线性规划问题（20分）二、设一线性规划问题为（25分） 其最优单纯形表为 2-7100 B-1b2 111106003111100-9-1-20在下述每一种情况下，进行灵敏度分析并求出最优解。2 目标函数变为；3 约束条件右端项由(6,4)T变为(3,5)T；4 增加一个约束条件三、某种产品今后四周的需求量分别为300，700，900，600件，必须得到满足。已知每件产品的成本在起初两周是10元，以后两周是15元。工厂每周能生产这种产品700件，且在第二、三周能加班生产。加班后，每周可增产200件产品，但成本每件增加5元。产品如不能在本周交货，则每件每周存贮费是3元。问如何安排生产计划，使总成本最小，要求建立运输问题数学模型求解。（25分）四、某校蓝球队准备从以下6名预备队员中选拔3名为正式队员，并使平均身高尽可能高，这6名预备队员情况如下表所示，试建立数学模型。（20分）队员的挑选要满足下列条件：2 少补充一名后卫队员；3 大李或小田中间只能入选一名；4 最多补充一名中锋；5 如果大李或小赵入选，小周就不能入选。预备队员号码身高（厘米）位置大张大李小王小赵小田小周456789193191187186180185中锋中锋前锋前锋后卫后卫五、某高校拟开设文学、艺术、音乐、美术四个学术讲座。每个讲座每周下午举行一次。经调查知，每周星期一至星期五不能出席某一讲座的学生数如下表：（20分）星期讲座一二三四五文学5040603010艺术4030203020音乐4030302010美术2030203030问：应如何安排一周的讲座日程，使不能出席讲座的学生总数最少，并计算不能出席讲座的学生总数。六、某飞行队有5名正驾驶员和5名副驾驶员。由于种种原因，某些正、副驾驶员不能同机飞行，某些则可以，如下表所示。每架飞机出航时需正，副驾驶员各一人。问最多能有几架飞机同时出航？应如何安排正，副驾驶员?用图论方法求解。（20分）正副B1B2B3B4B5A1*A2*A3*A4*A5*七、填空：（20分）1某工程公司拟从四个项目中选择若干项目，若令用的线性表达式表示下列要求：（1）从1，2，3项目中至少选2个： ；（2）只有项目2被选中，项目4才能被选中： ；2用表上作业法求解某运输问题，若已计算出某空格的检验数为-2，则其经济意义是 ，若从该空格出发进行调整，设调整量为2，则调后可使总运费下降 ；3. 动态规划中的Bellman最优性原理是 。试题三答案一、 解：将原问题化为标准形得 4 1 0 0 0 0 -1 1 1 0 0 2 -0 1 -4 0 1 0 4 40 1 -2 0 0 1 8 8 4 1 0 0 00 0 -3 1 1 0 6 -4 1 -4 0 1 0 4 -0 0 2 0 -1 1 4 2 0 17 0 -4 00 0 0 1 -1/2 3/2 124 1 0 0 -1 2 121 0 1 0 -1/2 1/2 2 0 0 0 9/2 -17/2由于而对应的 此线性规划问题无界二、 解（1）X2的价值系数由-7变为3。最优解发生变化，继续迭代。2 3 1 0 0 2 0 1 1 1 1 00 3 1 1 1610610/30 1 -1 -2 02 3 1 0 2/3 2/3 -1/30 1 1/3 1/3 1/38/310/30 0 -4/3 -2 -1/3-46/3此时最优解为（2） 此时不影响解的最优性，只改变解的值及目标函数值（3） 最优解不满足新增加的约束条件 最优解要发生改变 将约束条件改写为 加入最优表中继续迭代。2 -7 1 0 0 0 2 0 0 1 1 1 1 0 00 3 1 1 1 00 -1 -3 -1 0 1610-80 -9 -1 -2 0 0- 9 1/3 2 - -2 0 1 1 2/3 0 2/3 0 1/30 8/3 0 2/3 1 4/30 1/3 1 1/3 0 -1/310/322/38/30 -26/3 0 -5/3 0 -1/3-28/3新的最优解为三、 解：建立运输问题模型并给出初始方案得： 销产12345产1 10300 1317 16200 19200 0470001 151 1818 211 241 020020042 M 10700 13-7 16-7 0070042 M 1517 180 21200 0220023 M M 15700 180 05700-13 M M 200 23200 0020044 M M M 15-8 070070044 M M M 20-3 02002004销3007009006001100360010-41619-4 检验数有负，重复调整，得如下解： 销产12345产1 10300 130 16200 194 020070001 155 185 215 249 020020002 M 10700 130 164 03700-32 M 152 182 216 020020003 M M 15700 184 01700-13 M M 204 238 020020004 M M M 15600 010070004 M M M 205 02002000销30070090060011003600101316150此时检验数全，为最优解分配计划如下：第一个月正常生产500件，分别给1月300件，3月200件。 第二个月正常生产700件，供给第二个月 第三个月正常生产700件，供给第三个月 第四个月正常生产600件，供给第六个月四、 解：设五、 解：利用匈牙利法求解，增加一行元素 此时方案最优，最少人数方案为周一上美术课，周三上艺术课，周四上音乐课，周五上文学课。六、 解如图所示，最多只能有四架飞机出航：A1B1，A2B5，A3B3，A4B2七、 解：1、（1） （2）2、运费还可以减少，此方案不是最优方案3、在多阶段决策过程中，最优决策序列具有这种性质，即不管该序列上某状态以前的状态和决策如何，余下的决策序列必构成该状态的最优决策序列。试题四一、对约束条件（20分） 说明解X=（1,2,1,0,0,0,0）T是不是基可行解，假定不是，试找出一个基可行解。二、已知线性规划问题（20分） 其最优解为1求k的值；2求出对偶问题的最优解三、已知某运输问题的产销平衡表与单位运价表如下表所示（25分）Ai BjB1B2B3B4B5产量A1101520204050A22040153030100A33035405525150销量251156030701求最优调拨方案；2如产地A3的产量变为130，又B2地区需要的115单位必须满足，试重新确定最优调拨方案四、塞尔默公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他雇佣了四个临时工（安、伊恩、琼、肖恩），每一个人负责完成下面的一项任务：1.书面陈述的文字处理；2.制作口头和书面陈述的电脑图；3.会议材料的准备，包括书面材料的抄写和组织；4.处理与会者的提前和当场注册报名。虽然这四个临时工都有完成这四项任务所需的基本能力，但是在他们完成每一项任务时所表现出来的有效程度是有很大差异的。表1显示了每一个人完成每一项任务所用的时间（单位：小时）。试问营销经理应该将哪一项任务指派给哪一个人，才能使总时间最小？（20分）表1 塞尔默公司问题中的有关数据文字处理制作电脑图材料准备记录安35412740伊恩47453251琼39563643肖恩32512546五、用动态规划方法求解下列问题（25分） 六、求解下图的中国邮路问题（20分）62342512216七、选择（20分）1标准形式的线性规划问题，其可行解（ ）是基可行解，最优解（ ）是可行解，最优解（ ）在可行域的某一顶点。（a）一定 （b）不一定 （c）一定不2影子价格是（ ），其经济意义为（ ）（a）对偶最优解 （b） （c）约束资源的供应限制 （d）约束条件所付的代价3运用表上作业法求解运输问题时，计算检验数可用（ ）（a）闭回路法 （b）西北角法 (c) 位势法 (d) 最小元素法4动态规划的研究对象是（ ），其求解的一般方法是（ ）（a）最优化原理 （b）静态决策 （c）逆序求解 （d）函数迭代法 （e）多阶段决策过程试题四答案一、 解：（1） 首先将解代入约束条件，满足，说明是可行解 线性相关，此解不是基可行解（2） 选取 作为基变量， 线性无关。 令 ，解出 得出一个基可行解即。二、 解：写出原问题的对偶问题得 由互补松弛定理：得 得 联立得 而代入 则 综上，对偶问题最优解为三、解：（1）表上作业法求解得： 销产产 100 1550 2015 200 403550-10 2010 4015 1560 3030 30151000 3015 3565 4025 5515 257015010销251156030703002025153015检验数，此方案最优（2）增加虚拟产地 销产产 1015 1550 2030 2015 403550-25 2025 400 1560 3015 3001000 3015 3565 4030 5530 2565130-5 010 M 015 015 0520-20销251156030703002040153030检验数，此方案最优四、 解：用匈牙利法求解 最优方案为：肖恩 文字处理，伊恩 制作电脑图 安 材料准备， 琼 记录 最小时间五、 解：按变量划分为三个阶段 可以提供第到第 阶段的资源数， 第三阶段： 其中 第二阶段： 其中 第三阶段： 其中 ，其中， 六、 解：将奇数点变为偶数点得经检验，重复边权小于等于非重复边权，此时为最优解七、 解1、 b,a,a2、 a,c3、 ac4、 ec试题五一、对约束条件（20分） 说明解X=（1,2,1,1,0,0,0）T是不是基可行解，假定不是，试找出一个基可行解。二、某极小化线性规划的最优单纯形表为（25分）b01/211/205/21-1/20-1/61/35/20-40-4-2其中，为松驰变量，问题的约束为形式1写出原线性规划问题；2写出原问题的对偶问题；3直接由最优表写出对偶问题的最优解。三、考虑四种不同类型的机器和五项任务的分配问题，可利用的四种类型机器的台数是25，30，20和30，五项任务的工作量是20，20，30，10和25，不能把第4类机器分配到第4项工作上，单位成本如下表所示，求各类机器分到各项任务上的最优分配。（20分）任务类型12345机11023159器25101524类315514715型42015138四、有A、B、C三种资源可用来生产甲、乙、丙三种产品。资源量、单位产品利润和单位产品资源消耗量、各种产品生产的固定费用如下表所示。现在要求制定一个生产计划，使总收益最大，试建立数学模型。（20分）单位产品 产品资源消耗量甲乙丙资源限量资源A248500B234300C123100单件利润456固定费用100150200五、动态规划方法是解决 ，它是在明确 条件的基础上，建立 ，最终应求出 。（20分） A、动态问题 B、多阶段决策过程的问题C、阶段和阶段数 D、无后效性E、最优性原理 F、基本方程（递推关系式）G、决策变量与允许决策集合 H、阶段指标与指标函数I、状态转移方程 J、逆序解法和顺序解法K、最优决策序列和最优目标值 L、状态与状态变量六、有3个电站t1，t2，t3，每月每个电站各需60kt煤，有2个煤矿S1，S2，每月每个煤矿可提供100kt煤。煤矿向电站每月的最大运输能力：（25分）运输量/ ktt1t2t3S1404030S2402050各线路的千吨运费为运价 / 千元t1t2t3S1458S2556试用网络分析方法给出供煤方案，使总运费最小。七、什么是线性规划问题的灵敏度分析？（20分） 答案一、 解： ，列向量线性相关，不是基可行解选取 作为基变量， 线性无关。 解出二、 解：1、 由题可知而得此外， 2、 对偶问题为3、 由于对偶问题的最优解是最终单纯形表中检验数的相反数，则 三、 解：利用表上作业法求解： 任务机器12345机器1 1011 20 325 1519 91125-62 520 102 156 210 403003 1513 520 148 78 151420-34 2011 153 135 M 825304任务202030102510558924检验数，此方案最优四、 解：设代表第种产品的生产数量， 其中可取上界 五、 解：B，CGL，H，K六、 解：建立网络图得：图中数字分别为最大流量和费用。 分别找出各步最小费用流，然后在此基础上增加流量得：此时已满足需求量达到最优，七、 解：灵敏度分析是指：当A，b，C的系统中一个或几个发生变化时，已求得的最优解会有什么变化；这些系数在什么范围内改变时，规划问题的最优解或最优基不变；若最优解变化，如何用最简单的方法找到新的最优解。运筹学试卷A 参考答案及评分标准一、填空题（共44分，每空2分）1标准形式的线性规划问题，其可行解 不一定 是基可行解，最优解 一定 是可行解，最优解 一定 能在顶点达到。（填入一定、不一定或一定不）2线性规划原问题的约束条件个数与其对偶问题中的 变量 个数相等。若原问题第j个约束为等式，则对偶问题第j个 变量 无约束。3 用表上作业法求解m个产地n个销地的平衡运输问题，其方案表上数字格的个数为 个；若已计算出某空格的检验数为-2，若从该空格出发进行调整，设调整量为5，则调整后可使总运费下降 10 。4、某足球队要从1，2，3，4，5号五名队员中挑选若干名上场。若令1 第号队员上场xi= 0 第号队员不上场 i=1，2，3，4，5请用xi的线性表达式表示下列要求：1）从1，2，3中至多选两名 x1+ x2+ x32 1） 如果2号和3号都上场，则5号不上场： x2+ x3+ x52 2） 只有4号上场，1号才上场： x4- x10 5、目标规划的特点是引入了 偏差变量 ，模型的目标函数是这些变量的极 小 （小还是大）化，模型的约束中也含有用这种变量表示的 目标 约束。6、动态规划中的Bellman最优性原理是 无论初始状态和初始决策如何，对于先前决策形成的状态而言，其以后的所有决策必构成最优策略。 7、有一线性规划为解103-1101-11200-3-1-8设，为引入的松弛变量，得到最优单纯形表如上表，则12，23，1.5，3.5；各资源的影子价格为（3，1）。8、 某整数规划（）的目标函数为，与它相应的松弛线性规划（）为无可行解，则该整数规划没有（有或没有）最优解；若该的最优解为（5，3，6），则该整数规划的最优解为（5，3，6），若该的最优解为（5.5，2，6.5），则下列那个不可能是该整数规划的最优解（5，3，5）（5，3，4），（5，3，5），（5，2，6）。二、判断下述说法是否正确（每题2分，共10分）1、若某个线性规划模型没有可行解，则该线性规划问题的对偶模型不存在最优解。（正确 ）2、图解目标规划模型，其满意解既可能是一个点，也可能是一条线段，甚至也可能为一个区域。（ 正确 ）3、在产销不平衡问题中，应有产地个数不等于销地个数。（ 错误 ）4、在目标线性规划中，正偏差变量取正值，负偏差变量取负值。（错误 ）5、动态规划模型中的状态变量应具有后效性。（ 错误 ）三、（20分）某建材厂生产三种型号的构件：A，B，C型。各型号每件所需制造时间、装配时间、销售收入以及检验时间如表所示。根据市场情况，C型每月产量应控制在150件以内。现工厂需制定使总利润Z最大的生