工程硕士运筹学考试.doc

一判断下述说法的正误（每题2分共20分）（1） 线性规划（LP）问题的最优解一定是基本可行解。（ ）（2） 若LP对偶问题有可行解，则原问题必有有限最优解。（ ）（3） 若X是某个LP问题的基本可行解，则X必是可行域顶点。 （ ）（4） 若增加极小化LP模型的约束方程个数, 则可能会使其最优值变大（ ）（5） 在LP灵敏度分析中，改变Ci只影响Xi的检验数。（ ）（6） 凡是多段决策问题都可用动态规划予以求解。 （ ）（7） 适合用DP求解的决策问题，目标函数应关于阶段效应可分离。（ ）（8） 由P个点，P-1个边构成的图G就是树。 （ ）（9） 没有负回路的网络最短路问题，都可以用Dijkstra算法求解。 （ ）（10） 网络最大流算法中的流量增广链上必无饱和弧。（ ）二选择题：（15分）（1）已知X1 = (1, 2), X2 = (2, 4)是某LP的两个基本可行解, 则_必不是该LP的可行解. A) X = (3, 4) B) X = (1.5, 3) C) X = (2.5, 5) D) X = (5, 2)（2）影子价格的定义是 ，其计算公式为 ，经济含义为 。A）B-1b B）单纯形乘子C）单位资源市场价格D）CBB-1 E）对偶问题最优解 F）资源的边际效用（3） 某连通图G的各个顶点的次分别为2，1，3，2，3，2，1，2，2，2，则G 。A） 是树B）不是树C）无法判断（4）当需求量增加50%时，经济订购批量将 ：A) 约增加50%； B) 约减少100%； C) 约增加22.5%； D) 约减少22.5%（5）在用福德福克逊方法求得网络最大流时，设为最小割，则在网络中从S到的弧都应是 （ ）A) 零流弧； B) 饱和弧； C)非饱和弧； D)非零流弧；三简答题（每题5分，共10分）1简要描述表上作业法求解运输问题时确定初始调运方案的原则；（50字左右）2简要描述动态规划求解过程；（50字左右）四建模题（每题10分，共20分）1有一艘货轮，分前后两个舱位，它们的容积与最大载重量如下表所示。现有三种物品需要装船运走，有关数据如表所示。为了安全，要求前后仓的货物重量之比与载重能力之比的偏差不超过10%，试建立LP模型。（不求解）前舱后舱最大允许载重量（吨）22003300容积（立方米）45005500商品数 量（件）每件体积（立方米/件）每件重量（吨/件）运价（元/件）A5001081000B70015161700C400171416002 某甲工厂厂长欲为所生产的A、B、C 三种产品制定第一季度的生产销售计划。在生产计划讨论会上，各部门汇报的信息如下： 生产部:： A, B, C 三种产品的生产成本依次为36, 43, 52元；生产单位产品所需原材料1依次为2, 1, 2公斤；原材料2依次为3, 2, 1公斤, 所需工时依次为3, 2, 3；工厂第一季度可使用的最大工时数为300000。 物资部：工厂第一季度可使用的原材料1为250000公斤，原材料2为 350000公斤。原材料的购入价依次为6, 7元。 销售部：A, B, C 三种产品的销售成本依次为4, 4, 3元；销售价格依次为75, 64, 83元；根据已经签定的购货意向协议，各产品需求量依次为25000, 15000, 10000；其中若采用促销手段, 则可使B产品的市场容量增加6,000, 增加部分的销售成本6元, 价格为61元。 仓库：A, B, C 三种产品的现有库存量依次为1500, 800, 1500；第一季度末的保险库存量依次为1800, 1000, 1000。 厂办公室：接乙工厂电话, 该厂请甲厂转让一部分原材料1, 转让价格为7.8元/公斤。 试建立此问题的LP模型. 五计算题： 1 （15分）某工厂生产A、B、C三种产品，每种产品都需要工时和材料两种资源，以总利润最大为目标，所建立的生产计划线性规划模型如下：其中x1, x2, x3为A、B、C的生产数量(单位：吨)，下表中给出了最优生产计划对应的单纯型表(只保留三位小数)。 CB XB cj810300 qxjb x1x2x3x4x58x17.5100.750.417-0.08310x27.501-0.25-0.25025-13500-0.5-0.833-1.833试分别回答以下问题：（1） 由于市场原因，A产品的单位利润由8千元改变为7.5千元，你将做何决策？（2） 若可以再购买10单位的原材料，则单位价格超过多少时购买是不经济的？ （3） 若企业又有一笔资金要投入到购买原材料和工时上，你有什么建议？2（10分）某网络图上各个结点之间的距离如下图所示, Li,j 表示Vi与Vj之间的一步距离。V2V4V3V7591096647V568V16V681011V8选用合适的网络最短路方法求解V1到V8的最短距离和最短路线。3（10分）某羽毛球俱乐部每周需要给会员提供60打羽毛球，羽毛球的市场价格是每打10元；俱乐部保存羽毛球的年费用是采购单价的2%，每次订货需要10元钱的订货费；由于业务需要，俱乐部需要保留60打的最低库存；订货提前期1周。要求： 1) 画出库存量变化图；2) 计算经济订货批量(每年按48周计算)；3) 计算订货点。一判断下述说法的正误（每题2分共20分）1（F）2（F）3（T）4（T） 5（F）6（F）7（T）8（F）9（F）10（F）二选择题：（15分）1（C） 2（E、D、F） 3（B） 4（C） 5（B）三简答题（每题5分，共10分）1原则： a基变量的值均为非负，且总数恰好为m+n-1个； b所有的约束条件均得到满足； c所得的变量不构成闭回路。2在构建出动态规划模型后，首先利用动态规划基本方程逆序求出条件最优目标函数值集合和条件最优决策集合，然后顺序地求出最优目标值、最优策略和最优路线。四建模题（每题10分，共20分）1、用i =1，2，3 依次表示A、B、C三种商品，用j =1，2依次表示前、后两个舱位。设xji为i商品装入j舱位的数量，目标函数为总运费收入Z，则模型为22 用xi, i =1，2，3 依次表示A、B、C三种产品的生产量；用yj, j =1，2，3, 4 依次表示A销售量、B的正常销售量、B的促销量、C销售量；用w表示原材料1的转让数量。则销售收入为；生产成本为；销售成本为；转让原材料1的收益为；最终，模型为五计算题： 1 （1）由表格可计算出保持原生产计划不变的A的单位利润的变化范围为(7.333, 30)产品，所以应继续执行原计划。（2）由表格可知，原材料的影子价格为1.833,故原材料的购买价格不应高于1.833。（3） 应将资金投放到（资源的影子价格-购买资源的价格），即边际效益高的资源上；但应注意到资源的边际效益会随着资源的增加而下降，所以同时应随时比较资源的边际效益的变化。2V1到V8的最短距离为18，最短路线为V1，V3，V5 ，V83（10分）1) 库存量变化图；QTtQ0602) 经济订货批量；, h = 0.2 , k=103) 订货点=60+60=120，即库存量降至120打时发出订单。1. 判断下述论述的正误(在括号填入T 或F ) 或填空:(1) 凸集的顶点个数必为有限个. （ 如圆等） （错）(1) 任何凸集均可找到一LP模型与之对应. （表面为曲面或者曲线就不行了） (错)(2) LP模型的可行域的顶点必为有限个. (对)(3) LP模型的基本可行解必为有限个. (对) 顶点和基本可行解一一对应(4) 某LP模型有且仅有两个最优解. （要么唯一，要么无穷多个） (错)(5) 某LP模型有且仅有有限个(大于等于2)最优解. (错)(6) 某LP模型有无穷多个最优解. （任何线性规划模型都有无穷多个是错的） (对)(7) 若LP模型存在可行解, 则必存在最优解 （无有限最优解的情况存在） (错)(8) 若LP模型的可行域非空有界, 则其顶点中必存在最优解 (对)(9) 若LP模型的可行域非空, 则其顶点中必存在最优解 （无界） (错)(10) 若X是某LP模型的最优解, 则X必为该LP模型可行域的某一个顶点. （有可能在边界上） (错)(11) 若X是某LP模型的基本解, 则X必为该LP模型可行域的某一个顶点. (错)(12) 某LP的两个基本可行解中零分量的个数必相同. (基变量等于零的个数不一定相同，退化的基本可行解) (错)(13) 在单纯形算法中, 采用最小比值原则确定换出变量是为了保持解的可行性. (对)(14) 对偶单纯形算法中, 采用最小比值原则确定换出变量是为了保持对偶解的可行性.（改善解的可行性） (错)(15) 若增加极大化LP模型的约束方程个数, 则可能会使其最优值变大. (错)(16) 若增加极小化LP模型的约束方程个数, 则可能会使其最优值变小. (错)(15) 若减少极大化LP模型的约束方程个数, 则可能会使其最优值变大. (对)(16) 若减少极小化LP模型的约束方程个数, 则可能会使其最优值变小. (对) 增加约束条件个数，最优值变差，减少约束条件个数，最优值变好！(17) 在运输问题中, 任一组M+N个变量必含有闭回路. （M+N-1） (对)(18) 在运输问题中, 可任选一组M+N-1个变量作为基变量. （不能任选） (错)增广路概念2个条件：1）正向非饱和 U+ 2）反向非零流 U- (19) 设是用FORT-FULKERSON方法求解网络最大流过程中所的得一条增广路，则+ 上必无零流弧. (错)(20) 设为是用FORT-FULKERSON方法求解网络最大流过程中所的得一条增广路,则- 上必无饱和弧. (错)(21) 用Dijkstra算法求网络的最短路时, 使用条件是该网络不含负回路. （负权，权重非负，fude算法是不含负回路，可以有负权） (错)(22) 由P个顶点, P-1条边组成的图G必为树. （连通图，或者无圈图可以） (错) (24) 某连通图G的各顶点的次分别为 2, 3, 1, 2, 1, 2, 1, 2, 则G A A) 是树 B) 不是树 C) 不一定是树 D) 条件不够, 无法判断.(24) 某图G的顶点数 p 等于其边数 q + 1, 则G _C_. (不知道是否连通，是否无圈) a 是树 b 不是树 c 条件不够, 无法判断.(24) 连通图G的可达阵M的元素mij 必为1. ( )(24) 点vi 是图G的孤立点, 则图G的可达阵M的元素mij 必为0. ( ) (26) 用对偶法求解最大流-最小费用问题的过程中, 均可用Dijkstra算法求所绘 的增广费用网络的最短路（第一个可以用） (错) (31) 建立动态规划模型的四个要素一个方程是指:_1）动态规划模型2）状态变量1）动态规划基本方程_ _ _. (33) 用表上作业法求解运输问题时, 常用的确定初始方案的两个方法是:西北角法 _ _和_最小元素法_, 常用的确定检验数的两个方法是: _闭回路法_和_卫氏法_.(34) 已知X1 = (1, 2), X2 = (2, 3)是某LP的两个可行解, 则_B_也是该LP的可行解. a. X = (3, 4) b. X = (1.5, 2.5) c. X = (1.2, 1.8) d. 条件不够, 无法判断. (34) 已知X1 = (1, 2), X2 = (2, 4)是某LP的两个基本可行解, 则_C_必不是该LP的可行解. 在线上，且不在两个点之间（即在延长线上的） A) X = (3, 4) B) X = (1.5, 3) C) X = (2.5, 5) D) X = (5, 2) E) 条件不够, 无法判断.(35) 在单纯形的最优表上, 最优解不唯一, 则_A_ (至少有一个非基变量的检验数为零) a. 非基变量的检验数必有为零者 b. 非基变量的检验数不必有为零者.(36) 已知原问题有可行解, 但无最优解. 则原问题的对偶问题_A_. (都有可行解都有最优解) a. 无可行解 b. 有可行解, 但无最优解 c. 有可行解且有最优解(37) 已知某极大化LP问题及其对偶问题均有可行解, 而Y1 , Y2 为对偶问题的两个可行解, 它们对应的目标函数值分别为4, 7. 则原问题的最优值Z满足_A_ （极大化原问题最小的可行解；极小化原问题最大可行解） a. Z 4 b. 7 Z c. 4 Z 7（一定不可能）(38) 极小化(MinZ)LP问题可转化为目标函数取极大化即_B_的问题求解. 而原问 题的目标函数值等于_C_. a. MaxZ b. Max(-Z) c. -Max(-Z) d. -MaxZ(39) 对产销不平衡的运输问题, 可通过_引入虚拟产地_或_引入虚拟需求点（产量等于供需缺口来平衡）_ 的方法, 将其转化产销平衡的运输问题求解.(40) 通常, 运输问题的变量个数为_B_, 其基由_C_个变量组成. a. M + N b. M * N c. M + N - 1 d. M + N + 1(41) 在网络分析中, 所求得的最大流_C_唯一(最大流量一定相同的), 所求得的最短路_C_唯一. a. 一定 b. 一定不 c. 不一定1. 求解LP的单纯形法中，先确定 入基 变量，后确定 出基 变量。入基变量是按照 的原则确定的，其目的是 ，出基变量是按照 确定的，是为了 。A) 使目标函数值得到改善；B) 保持解的可行性；C) 决策变量小于零；D) 检验数大于零；E) 最小比值法；F)消除解的不可行性；G) 入基变量； H)出基变量2. 求解线性规划模型时，引入人工变量是为了 B (敲门转，使得问题可以继续解决，最后人工变量都是要出基的！如果最后没有出基，那就问题没有可行解) 。A) 使该模型存在可行解；B) 确定一个初始的基本可行解；C) 使该模型标准化；3. 影子价格的定义是 B ，其计算公式是 D ，经济含义是 E 。A) B-1b；B) 对偶问题的最优解；C) 单纯形乘子；D) CBB-1；E) 购买单位资源时企业所付出的代价；F) 约束条件所付出的代价；4. 建立动态规划模型的要素包括有： 4大要素，一个方程。 5. 容量网络上满足 C F 条件的 G 称为可行流.A) 费用最小；B) 无重边也无环；C) 容量限制；D) 弧上的流；E) 正向饱和反向非零流；F) 中间点平衡条件；G) 图上的流；H) 最大流最小割定理；I) 线性约束条件6. 在求解网络最大流的标记化算法中，增广路是满足 F C 的从源顶点到汇顶点的一条通路。A) 增广路上的弧均为非零流弧；B) 增广路上的弧均非饱和弧；C) 增广路上反向弧均为非零流弧；D) 增广路上的正向弧均为非零流弧；E) 增广路上反向弧均为非饱和弧；F) 增广路上的正向弧均为非饱和弧；7. 求最小费用最大流的对偶法求解思路是始终保持 E 是 G ,通过不断调整, 使 C 逐步 A , 最终成为最小费用最大流。A) 增大； B) 减少； C)流量； D)费用； E)可行流； F)最大流；G)最小费用流；8. 运输问题的模型的变量个数为 A ，其中基变量个数为 C ；用表上作业法求解该模型时，常用的确定初始调运方案的方法有 ，求检验数的方法有 ；A) m+n；B) mn；C) m+n-1；D) 人工变量法；E) 行最小法；F) 闭回路法；G) 西北角法；H) 最小元素法；I) 行变换法；J) 位势法；9. 若可行域是空集,则表明存在矛盾的约束条件。( 对 )10. 用表格单纯形法求解LP问题，若最终表上非基变量的检验数均非正（要求严格小于零），则该模型一定有唯一的最优解。( 错 )13. 用表格单纯形法求解LP问题，若最终表上某非基变量的检验数为零（是必要条件，非充分条件，除非加上“基变量都大于零”），则该模型有无穷多个最优解。(错 )11. 单纯形法的思路是保持基的可行性, 逐步迭代达到基的对偶可行性。(对)12. 对偶单纯形法的思路是：保持对偶问题的基的可行性, 逐步迭代达到原问题的基的可行性。(对)13. 若原问题存在可行解，但无有限最优解,则对偶问题可行解不存在。(对)14. 当有负权（无负权）时,可用D氏标号法求网络最短路问题, 当存在负回路时,可以用列表法(FORD算法)或函数迭代法求解最短路问题。( 错 )15. 适合用动态规划模型求解的多段决策问题的目标函数，必须具有关于阶段效应的可分离形式。 ( 对 )16. 线性规划灵敏度分析中，若变量在目标函数中的系数发生变化，只影响最终单纯形表中该变量的检验数。 ( 错 )二、建模题(共20分，每小题10分)1. 某工厂生产A、B、C三种产品，现欲根据订货合同以及生产状况制定5月份的生产计划。已知合同甲为：A产品1000件，单件价格为500元，违约金为100元/件；合同乙：B产品500件，单件价格为400元，违约金为120元/件；合同丙：B产品600件，单件价格为420元，违约金为130元/件；C产品600件，单件价格为400元，违约金为90元/件；有关各产品生产过程所需工时以及原材料的情况见表1，试以利润为目标，建立该工厂的生产计划线性规划模型（不求解）。表1工序1工序2工序3原材料1原材料2其它成本/件产品A2323410产品B1132310产品C2124210总工时（原材料）460040006000100008000工时原材料成本（元某单位拟将四种物品从救灾现场抢运到另一城市，其运输工具为一架运输机，且只能运输一趟。该飞机的载重能力为45吨，货舱空间为20m3。已知4种物品的有关数据如表2所示。试为该单位制定使总价值为最大的运输方案。只建立动态规划模型，不求解。 表2物 品重 量 (kg)体 积 (m3)价 值 (元)13000.41500022000.3800031000.2900041500.26000三. 现有40台某种大型成套设备要装入一艘远洋货轮运走，每套该设备由两大部件组成，各部件的重量、体积如下表1所示。已知货轮有两个货舱，每个货舱的载重量与容积如下表2所示。每套设备的运费为40万元，装不走的设备可以留下，航行安全要求各舱的实际载重之比与它们的载重能力之比的误差不超过10，试建立线性规划模型以确定使装载运费收入最大的装运方案（不求解；忽略整数要求）。表2表1部件重量（吨）体积(m3 )125070280100货舱载重（吨）容积(m3 )160002500240002500四、某公司需要将50万元技改资金根据下属甲、乙、丙三个工厂的技改项目进行分配。已知各工厂申报的技改项目如下：甲工厂：项目A：需投资10万元，预计可增加年利润2万元；项目B：需投资15万元，预计可增加年利润4万元；项目C：需投资20万元，预计可增加年利润6万元。乙工厂：项目A：需投资5万元，预计可增加年利润1.5万元；项目B：需投资15万元，预计可增加年利润5万元；项目C：需投资25万元，预计可增加年利润5万元。丙工厂：项目A：需投资15万元，预计可增加年利润3万元；项目B：需投资15万元，预计可增加年利润3.5万元；项目C：需投资20万元，预计可增加年利润4万元；项目D：需投资30万元，预计可增加年利润5万元。试建立关于技改资金分配的动态规划模型（不求解）。三段问题，而非十段问题！T1v1v2v3v5(200)(100)(60)(100)(120)(150)(220)(240)(280)v6(80)(110)(150)T2470S(210)(225)六、(20分)如下所示为北大荒某农场灌溉系统的网络模型。图中，S为初级提水泵站，所标数值为泵站的日提水量；vi为具备分流功能的次级泵站，其中v6的能力为290，其他次级泵站的能力均超过该泵站输水管道能力之和；弧为埋藏式地下输水渠道，所标数值为渠道输水设计能力；T1、T2为两个农田灌区，所标数值为各灌区目前灌溉用水的需求量。1、 在不考虑灌区目前灌溉用水的需求量的前提下，用计算机软件求出该系统网络的最大输水能力与各个次级泵站的分流控制方案，并标注在你绘制的网络图上。2、 根据农场发展规划，明年各灌区水的日需求量将有显著增加，现有的灌溉系统可能不能够满足要求，需要改造。问应如何改造？为什么？在改造过程中，应注意那些问题？（找到系统中的所有最小割，对未来需求进行预测，瓶颈问题，投入产出问题）可能求解题类型）线性规划灵敏度分析）和运输问题表上作业法）最短路、最短树）库存控制动态规划绝对不会求解，只会建模。2. 某甲工厂厂长欲为其所生产的A, B, C 三种产品制定第一季度的生产 销售计划. 各部门汇报的信息如下: 生产部: A, B, C 三种产品的生产成本依次为56, 31, 42元; 生 产单位产品所需原材料1依次为2, 1, 2公斤; 原材料2依次为3, 2, 1 公斤, 所需工时依次为3, 2, 3; 工厂第一季度可使用的最大工时数为 300000. 物资部: 工厂第一季度可使用的原材料1为200000公斤, 原材料2为 250000公斤. 原材料的购入价依次为6, 7元. 销售部: A, B, C 三种产品的销售成本依次为2, 3, 2元; 销售价 格依次为75, 52, 63元;市场容量依次为20000, 10000, 10000; 其中若采用促销手段, 则可使B产品的市场容量增加5,000, 增加 部分的销售成本3元, 价格为50元. 仓库: A, B, C 三种产品的现有库存量依次为1000, 800, 1500; 第一季度末的保险库存量依次为1500, 1800, 1000. 厂办公室: 接乙工厂电话, 该厂请甲厂转让一部分原材料1, 转让价 格为7.8元/公斤. 试建立此问题的LP模型. (10分)3. 某工厂为其所生产的X1 , X2 , X3 三种产品制定生产计划建立了如下所示的LP模型: Max Z = 4X1 + 2X2 + 3X3 s.t. 2X1 + 2X2 + 4X3 100 原材料1 3X1 + X2 + 6X3 0(1) 用表格单纯形法求最优生产计划.(2) 在所得最优表的基础上, 分别就以下情况单独发生时, 进行灵敏度分析:(a) 由于市场变化, 产品X1 的单位利润可能改变, 求此变化保持在那个范围内时, 最优生产计划不须改变; 若产品X1 的单位利润变为7, 求相应的最优生产计划.(b) 由于原材料市场变化, 原材料1的供应量从100个单位降低为50个单位, 问此变化是否影响原最优生产计划? 若影响,求相应的最优生产计划.2.1 某工厂为其所生产的X1 , X2 , X3 三种产品制定生产计划建立了如下所示的LP模型: Max Z = 4X1 + 2X2 + 3X3 s.t. 2X1 + 2X2 + 4X3 100 3X1 + X2 + 6X3 100 3X1 + X2 + 2X3 0(1) 用表格单纯形法求最优生产计划.(2) 在所得最优表的基础上, 分别就以下情况单独发生时, 进行灵敏度分析:(a) 由于市场变化, 产品Y的单位利润可能改变, 求此变化保持在那个范围内时, 最 优生产计划不须改变; 若产品Y的单位利润变为5, 求相应的最优生产计划.(b) 由于原材料市场变化, 原材料1的供应量从100个单位降低为50个单位, 问此变化是否 影响原最优生产计划? 若影响,求相应的最优生产计划.(c) 由于生产技术的改进, 产品Z的单位利润, 消耗的工时, 原材料发生变化, 从原先的3, 4, 6, 2依此变为6, 2, 2, 1. 求相应的最优生产计划.2.2 某LP问题如下所示: Max Z = -5X1 + 5X2 + 13X3 s.t. -X1 + X2 + 3X3 20 (1) 12X1 + 4X2 + 10X3 0(1) 用表格单纯形法求最优解.(2) 在所得最优表的基础上, 分别就以下情况单独发生时, 进行灵敏度分析:(a) 目标函数中, X2 的系数由5变为3.(b) 约束方程(2)右端的常数项由90变为70.(c) 增加一个约束方程: 2X1 + 2X2 + 5X3 50典型考试题目如下：三、(25分)某工厂制造三种产品A、B和C，需要劳动力和原材料两种资源，为确定总利润最大的生产计划，可列出如下的线性规划模型：max Z = 4x1 + x2 + 5x3s.t. 6x1 + 4x2 + 5x3 45(劳动力限制) 3x1 + x2 + 5x3 30(原材料限制) x1，x2，x3 0其中，x1，x2，x3分别是A、B、C的产量。表4为用单纯形求解该模型所得到的最终表，表中x4、x5分别为劳动力与原材料约束的松弛变量。根据最终表回答下列问题：C41500CBXBbx1x2x3x4x54x151101/3-1/35x330-2/51-1/52/5-Z-350-10-1/3-2/3（1）当产品B的单位利润由1元/件变为2元/件时，问是否必须修改生产计划，为什么？（2）当产品A的单位利润由4元/件变为2元/件时，问是否需要修改生产计划？若不需修改计划，陈述理由；若需修改计划，计算得出新的生产计划。（3）假如能以10元的代价，另外再获得20个单位的原材料，通过计算结果说明这样做是否有利？（4）若在原问题中增加一个设备约束条件：2x1 + x2 + 3x3 20，这对于最优解和对偶解有什麽影响？（把现在的最优解代入这个约束条件，满足没有影响，不满足则有影响）（5）若在原问题中，单位产品B消耗劳动力的数量由4工时/件变为2工时/件，问是否需要修改生产计划？若不需修改计划，陈述理由；若需修改计划，计算得出新的生产计划。3. 某运输问题的有关数据如下, 试用表上作业法制定运费最小的调运方案. 运 销 价 地 产地 B1 B2 B3 产量 - A1 3 5 8 30 A2 7 4 2 50 A3 10 3 5 60 - 销量 40 30 404.1 某公司拟将6万元技改资金分配给下属的A, B, C, 3个子公司, 各子公司在获得不同数量的资金后的收益如下表所示. 试建立资金分配的动态规划模型, 并据此求出资金的最优分配方案. - 投 资 (万元) 0 1 2 3 4 5 6 - A 0 2 2 2 3 3 4 收益 B 0 1 2 2 4 5 6 C 0 2 2 3 3 3 4 -4.2 （可靠性问题，考试不会出了） 某公司拟投入6万元资金用于研制A1 , A2 , A3 , 3种新产品, 已知第k种新产品研制成功的可能性Pk 与投入的资金量Mk 的关系分别为: Pk = 1 - 1/( 1 + Rk * Mk ) 其中 R1 = 0.5, R2 = 1.0, R3 = 1.5 Mk = 0, 1, 2, 3, 4, 5, 6 万元, ( k = 1, 2, 3 )求如何分配资金使三种新产品均研制成功的可能性最大. 试建立此问题的动态规化模型并求解.四、（最短路问题）(10分)已知某网络如下所示，试用Djikstra算法求网络起点到终点的最短路。书写格式尽量简单，用最简单的方式表示（表格形式）stv1v2v3v5v6362185363373五、(10分)已知某容量网络如下所示，图中各弧上所标数值依次为容量与可行流流量。试用Ford-Fulkerson标记化算法求该网络的最大流。必须以给定的可行流为初始流。stv1v2v3v5(12,8)(5,5)(6,4)(7,4)(3,3)(5,4)(7,4)(14,12)(10,8)v6(4,1)(8,4)(5,4)S1tv1v2v3v5(20)(5)(6)(10)(6)(10)(17)(20)(13)v6(6)(8)(12)S2121030六、(13分)如下所示为某城市的污水处理系统的网络模型。图中，si为各个污水源，si上所标数值为相应污水源的排污量； vi为具备分流功能的污水汇集点；弧为排污管道，所标数值为管道容量；t为中心污水处理厂，t上所标数值为污水处理厂的处理能力。3、 试用计算机软件求出该网络的最大排污能力与各个汇集点的分流控制方案，并标注在图上。4、 根据城市发展规划，若干年后各个排污点的排污量将有显著增加，现有的排污管系统可能不能够满足要求，需要改造。问应如何改造？为什么？在改造过程中，应注意那些问题？一、(20分) 某物流公司为扩大业务范围并提高服务效率，考虑在北京、上海、广州和武汉四个城市设立配送中心，这些配送中心将负责向华北、华中、华南三个地区供货。配送中心的规模为两种，一种月处理货物为2000件，另一种月处理货物为3000件。规模为2000的中心所需月费用，在北京为6万元，上海为8万元，广州为9万元，武汉为5万元。而规模为3000的中心所需月费用依次为北京8万元，上海10万元，广州11万元，武汉7万元。每个地区的月平均需求量分别为华北1500件，华中1800件，华南1700件。发送货物的运输成本（元/件）见下表：华北华中华南北京200400500上海300250400广州600350300武汉35