清华版《运筹学》第三版课后习题详解、

1绪论1、运筹学的内涵答本书将运筹学定义为“通过构建、求解数学模型，规划、优化有限资源的合理利用，为科学决策提供量化依据的系统知识体系。”2、运筹学的工作过程答解释、修正求解构造模型现实系统模型现实结论模型结论图11运筹学的工作过程（1）提出和形成问题。即要弄清问题的目标、可能的约束、可控变量、有关的参数以及搜索有关信息资料。（2）建立模型。即要把问题中的决策变量、参数和目标、约束之间的关系用一定的模型表示出来。（3）求解模型。根据模型的性质，选择相应的求解方法，求得最优或者满意解，解的精度要求可由决策者提出。（4）解的检验和转译。首先检查求解过程是否有误，然后再检查解是否反映客观实际。如果所得之解不能较好地反映实际问题，必须返回第（1）步修改模型，重新求解；如果所得之解能较好地反映实际问题，也必须仔细将模型结论转译成现实结论。（5）解的实施。实施过程必须考虑解的应用范围及对各主要因素的敏感程度，向决策者讲清楚用法，以及在实施中可能产生的问题和修改的方法。3、数学模型及其三要素答数学模型可以简单的描述为用字母、数字和运算符来精确地反映变量之间相互关系的式子或式子组。数学模型由决策变量、约束条件和目标函数三个要素构成。决策变量即问题中所求的未知的量，约束条件是决策所面临的限制条件，目标函数则是衡量决策效益的数量指标。2线性规划1、试述线性规划数学模型的组成部分及其特性答线性规划数学模型由决策变量、约束条件和目标函数三个部分组成。线性规划数学模型特征（1）用一组决策变量表示某一方案，这组决策变量均为非负的连续变量；（2）存在一定数量（M）的约束条件，这些约束条件可以用关于决策变量的一组线性等式或者不等式来加以表示；（3）有一个可以用决策变量加以表示的目标函数，而该函数是一个线性函数。2、一家餐厅24小时全天候营业，在各时间段中所需要的服务员数量分别为2006003人60010009人1000140012人140018005人1800220018人22002004人设服务员在各时间段的开始时点上上班并连续工作八小时，问该餐厅至少配备多少服务员，才能满足各个时间段对人员的需要。试构造此问题的数学模型。解用决策变量,1X2X3X,4X,5X,6X分别表示200600，6001000，10001400，14001800，18002200，2200200时间段的服务员人数。其数学模型可以表述为12345MIN6ZXXXXXX16122334455612345639125184,0XXXXXXXXXXXXXXXXXX3、现要截取29米、21米和15米的元钢各100根，已知原材料的长度是74米，问应如何下料，才能使所消耗的原材料最省。试构造此问题的数学模型。解圆钢的截取有不同的方案，用表示每种切割方案的剩余材料。其切割方案如下所示29211511110922000131200341030501308600414702202803011目标函数为求所剩余的材料最少，即1234567MIN0901030081402118ZXXXXXXXX1234135781245671234567821002231003342100,0XXXXXXXXXXXXXXXXXXXXXXX4、某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C三种原料的含量要求、各种原料的单位成本、各种原料每月的限制用量、三种牌号糖果的单位加工费及售价如表1所示。问该厂每月生产这三种牌号糖果各多少千克，才能使该厂获利最大试建立这个问题的线性规划模型。、某糖果厂用原料、加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中、三种原料的含量要求、各种原料的单位成本、各种原料每月的限制用量、三种牌号糖果的单位加工费及售价如表所示。问该厂每月生产这三种牌号糖果各多少千克，才能使该厂获利最大试建立这个问题的线性规划模型。表1表甲甲乙乙丙丙原料成本原料成本限制用量限制用量A60以上15以上2002000B1502500C20以下60以下50以下1001200加工费050040030售价340285225解以表示甲产品中的A成分，表示甲产品中的B成分，表示甲产品中的C成分，依此类推。据表216，有A甲B甲C甲35A甲甲，15C乙乙，35C我们的目的是使利润最大，即产品售价减加工费再减去原材料的价格为最大。目标函数为12345678091419045095145005045095MAXZXXXXXXXXX95、某厂在今后4个月内需租用仓库存放物资，已知各个月所需的仓库面积如表2所示。租金与租借合同的长短有关，租用的时间越长，享受的优惠越大，具体数字见表3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积数和期限。因此该厂可根据需要在任何一个月初办理租借合同，且每次办理时，可签一份，也可同时签若干份租用面积和租借期限不同的合同，总的目标是使所付的租借费用最小。试根据上述要求，建立一个线性规划的数学模型。表2月份1234所需面积（100M2）15102012表3合同租借期限1个月2个月3个月4个月单位（100M2）租金（元）2800450060007300解设IJX（I1,2,3,4J1,24I1）为第I个月初签订的租借期限为J个月的合同租借面积（单位100M）；R表示第I个月所需的面积（J表示每100仓库面积租借期为J个月的租借费）；则线性规划模型为2I2M44111IJIJIJMINZCX41111,2,3,401,2,3,41,241KIIJKIJKIIJXRXIJI6、某农场有100公顷土地及25万元资金可用于发展生产。农场劳动力情况为秋冬季4500人日，春夏季6000人日，如劳动力本身过剩可外出打工，春夏季收入为20元人日，秋冬季12元人日。该农场种植三种作物大豆、玉米和小麦，并饲养奶牛和鸡。种作物不需要专门投资，而饲养动物时每头奶牛投资8000元，每只鸡投资2元。养奶牛时每头需拨出15公顷土地种饲草，并占用人工秋冬季为100人日，春夏季为50人日，年净收入3000元每头奶牛。养鸡不占土地，需人工为每只鸡秋冬季03人日，春夏季01人日，年净收入为每只8元。农场现有鸡舍允许最多养5000只鸡，牛栏允许最多养50头奶牛，三种作物每年需要的人工及收入情况如表4所示。试决定该农场的经营方案，使年净收入最大。表4大豆玉米麦子每公顷秋冬季所需人日数203510每公顷春夏季所需人日数507540年净收入（元/公顷）11001500900解设,1X2X3X分别代表大豆、玉米、麦子的种植数（公顷）；4X,5X分别代表奶牛和鸡的饲养数；6X,7X分别代表秋冬季和春夏季多余的劳动力（人日数）则有12345611001500900300081220MAXZXXXXXXX712445123456123457451234567151008000225000020351010003450050754050014500505000X,X,X,X,X,X,X0XXXXXXXXXXXXXXXXXXX土地限制资金限制）劳动力限制）劳动力限制）牛栏限制）（鸡栏限制）7、用图解法求解下列线性规划问题（1）（2）212MAXXXZ2123MAXXXZ123421XX4221XX8221XX142321XX8421XX321XX0,21XX0,21XX（3）（4）2132MAXXXZ21MAXXXZ221XX021XX4321XX3321XX0,21XX0,21XX解（1）（2）23484此题有无穷多最有解，其中一个是4,1TX9,14Q849,14TX此题有唯一最有解，234（3）（4）8、考虑线性规划43212MAXXXXXZ1X52X3X4X1X22X5X261X2X3X6X0,61XX（1）通过观察写出初始的基可行解并构造初始单纯形表；（2）在保持2X和3X为零的情况下，给出非基变量1X增加一个单位时的可行解，并指出目标函数的净增量是多少（3）在模型约束条件的限制下，1X的最大增量是多少（4）在1X有其最大增量时，给出一个新的基可行解。解（1）因存在初始可行基456,TXXX，故可令,1X2X3X全为0,则可得初始可行解为，Z5。0,0,0,5,2,6T初始单纯行表为CJ211100CBXBX1X2X3X4X5X6B10X4X511110011001052243找不到可行域，此题为无可行解244此题为无界解0X62110016J320000Z02非基变量,2X3X仍然取零，由0变为1,即1,0,1X1X2X3X0,代入约束条件得一个可行解X。其目标函数值为Z81,0,0,6,1,4T因此，随着增加1个单位目标函数值的净增量为Z8531X（3）因为决策变量全非负所以由约束条件知增加可以引起,1X2X3X,4X增加，即条件对无约束；由约束条件知增加可引起,1X1X2X5X减少，由非负约束知最大增量为2；同理可得约束条件的最大增量为3，综合得的最大增量为2。1X1X1X（4）2，非基变量0,1X2X3X0,代入约束条件得基可行解X，目标函数值为Z11。2,0,0,7,2,2T9、将线性规划模型转化为标准形式432132MAXXXXXZ1024321XXXX85324321XXXX12464321XXXX0,321XXX，无约束4X解（1）令4X5X6X并代入模型，这里5X0,6X0；（2）第二个约束条件方程两侧同乘“1”；（3）第一个约束条件引入松弛变量7X，第三个约束条件引入8X作为松弛变量。（4）目标函数同乘“1”，即可实现最少化。1235MIN236ZXXXXX1235671236123568123456782123586441,0XXXXXXXXXXXXXXXXXXXXXXXX0210、用单纯形法求解下述线性规划问题（1）（2）43213MINXXXXW32154MAXXXXZ422321XXX21813X2X3X63421XXX12X2X40,4321XXXX1X2X3X50,321XXX（1）解构造初始单纯行表，并进行初等变换，得CJ3111CBXBX1X2X3X4B11X3X42（2）10310146J2200W1011X2X4111/20401/2124J0010W6最优解，由非基变量的检验数为0,知此问题有无穷多最有解，所以该解为无穷多最优解中的一个，最优值为W6。0,2,0,4TX71X（2）解此问题用大M法求解，先把问题标准化为1236MIN45ZXXXMXMX1234612512371234567321245,0XXXXXXXXXXXXXXXXXXX8构造初始单纯行表，并进行初等变换，得CJ45100MMCBXBX1X2X3X4X5X6X7BM0MX6X5X73211010210010011100011845J44M53M1M000M4MX6X1X701/2112/31011/2001/20001/2101/2011223J051M2M200M5MX6X2X71011210210010010101011041J2M401M3M50015MX3X2X710112102100100200131110411J2M500M13M310因为所有检验数均为非负，但人工变量7X仍为基变量，故此问题无解。11、求解线性规划问题并给出其中三个最优解43213MINXXXXW422321XXX63421XXX0,4321XXXX解构造初始单纯行表，并进行初等变换，得CJ3111CBXBX1X2X3X4B11X3X42（2）10310146J2200W1011X2X4111/20401/2124J0010W613X2X1013/81/4101/81/431J0010W6从单纯形表可以找到两个顶点，。可以找到变量之间存在以下关系10,2,0,4TX21,3,0,0TX2X1X2；4X41X4；30X令1X1/2则有，从而找到了LP问题的三个最优解。31/2,5/2,0,2TX12、（1）如为唯一最优解则要求非基变量的检验数全少于零，从而有1即可。（2）要令表中解为无穷多最优解中的一个，则有以下关系成立1（3）要使表中的解为退化的基可行解，则必有0；当21且20时，。10（4）若为无界解，则满足能找到入基变量，但找不到出基变量的条件。即满足0；21，且20；102，且10；300，且33040；3X0；4X0；2X0；2X0；1X0解上述不等式得00，即X3。也就是说A3到B5的单位运价大于等于3时，最有方案不变。同理可以算出A4到B1的单位运价变化范围是2，此时最优方案不变。（2）把变化直接反映到表中可得下表B1B2B3B4B5B6IUA12302150A2（3）22（20）451A33（1）（0）2（1）11A43111220JV233120因存在检验数为负数，最优方案发生改变，用闭合回路法调整得B1B2B3B4B5B6AIA1212950A2202040A39401160A413031BJ305020403011重新计算检验数，得B1B2B3B4B5B6IUA12302050A2（3）22（4）251A33（1）（0）2（0）11A4320（1）231JV233130非基变量检验数均为非负，故为最优方案。（3）把A3到B5的单位运价改为2，然后求检验数得B1B2B3B4B5B6IUA12122150A2（1）22（3）131A33（3）（2）2（1）11A42111220JV211120由于存在负检验数，故最优方案发生变化，此时用闭合回路法调整得B1B2B3B4B5B6AIA1203050A2202040A3109301160A43131BJ305020403011重新计算检验数，得B1B2B3B4B5B6IUA12102050A2（3）22（4）251A33（1）（0）2411A41111（1）20JV233130检验数有负数，用闭合回路法调整得B1B2B3B4B5B6AIA1203050A2202040A310391160A413031BJ305020403011重新计算检验数，得B1B2B3B4B5B6IUA12122150A2（1）22（2）131A33（3）（2）2（1）11A42111220JV211120检验数全为非负，故已得最优方案。5整数规划1、用分枝定界法求解下述整数规划问题（1）1MAX2ZXX（2）12MAX43ZXX1214951XX12341XX21263XX191242XX12,XX00且取整且取整12,XX解（1）用单纯型法求得相应星星规划问题,最终单纯型表0LCJ1100CBXBX1X2X3X4B11X1X2101/323/32011/1625/483/210/3J003/1691/48Z5/29即0X，3/2,10/3,0,0T0Z29/5在基础上分别增加约束条件0L1X1和1X8，分别形成两个子线性规划和1L2L1L1MAX2ZXX2L1MAX2ZXX141X92X51141X27X5161X32X161X220X11X181X1X,2X,3X,4X,5X02X,3X,4X,5X0求解和有1L2L1X1,7/3T1Z10/32X3,1T2Z42L有最优解，又1Z2Z，故整数规划有最优值Z4，X3,1T此题求解过程如下图0L0X，3/2,10/3,0,0T0Z29/51X11X81L2L1X1,7/3T1Z10/32X3,1T2Z4（2）定义相应线性规划为0L12MAX43ZXX12341XX299XX12XX1242XX12,0XX42341212234解得0X，6/5,21/10T0Z111/10在基础上分别增加约束条件0L1X1和1X2，分别形成两个子线性规划和1L2L1L1MAX432ZXX2L12MAX43ZXX31X42X1231X42X1241X22X941X22X91X121X1X,2X02X0求解得1X1,9/4T1Z43/42X2,1/2T2Z19/2在基础上分别增加约束条件1L2X2和2X3，分别形成两个子线性规划和3L4L解得3X1,2T3Z10无解4L故X1,2TZ10此题求解过程如0L0X，6/5,21/10T0Z111/101X11X21L2L1X1,9/4T1Z43/42X2,1/2T2Z19/22X22X33L4L3X1,2T3Z10无可行解2、某航空公司为满足客运量日益增长的需要，正考虑购置一批新的远程、中程及短程的喷气式客机。每架远程客机价格670万元，中程客机500万元，短程客机350万元。该公司现有资金12000万元可用于购买飞机。据估计年净利润（扣除成本）每架远程客机82万元，中程客机60万元，短程客机40万元。设该公司现有熟练驾驶员可用来配备30架新购飞机。维修设备足以维修新增加40架新的短程客机，每架中程客机维修量相当于43架短程客机，每架远程客机维修量相当于53架短程客机。为获取最大利润，该公司应购买各类客机各多少架解设购买远程、中程及短程的喷气式客机数量分别为1X，2X，3X，数学模型如下MAXZ821X602X403X1231231231236705003501200030243040,0XXXXXXXXXXXX且取整解得，有最大利润1454元。1231710XXX，3、某市为方便学生，拟在新建的7个居民小区增设若干所学校。已知各备选校址代号及其能覆盖的居民小区编号如表1所示，问要覆盖所有居民小区至少应建多少所学校对应的校址代号是哪些表1备选校址ABCDEF小区编号1，5，71，2，51，3，52，4，53，64，6解对每一个学校定义一个变量JX1，当某居民小区可由第J个学校负责JX0，当某居民小区不可由第J个学校负责则对于第1个小区1231XXX对于第2个小区241XX对于第3个小区351XX对于第4个小区461XX对于第5个小区12341XXXX对于第6个小区561XX对于第7个小区11XMINZ61JJX解得1,0,0,1,1,0TXZ34、求解下述01规划问题（1）1234MAX25345ZXXXXX1234532754XXXXX6012345242XXXXX01JXOR1,2,3,4,5J（2）123MAX25344ZXXXX123440XXXX12342424XXXX412341XXXX01JXOR1,2,3,4J85解（1）将01规划问题换形为21453MIN34511WXXXXX2145323547XXXXX21453422XXXXX24153,XXXXX取0或1显然零解不满足，分枝41X11X40X51X41X40X41X40X50X51X10X11X50X51XW5W5W1W2W62524W9W9W6W2W6W1W7W4W5W8W7W1020X21XW1119863245111427261918151031X30X50X50X51X51X41X40X10XW7W6W7W2W7W3W8W8W4713172022232116122将01规划问题换形为1342MIN234514WXXXX134241XXXX13422244XXXX413421XXXX1234,01XXXXOR0显然零解不满足，分枝可行解W91X01X1W14321W12故0,1,1,1,12TXZ5、求解例53所述的01规划问题。解将01规划问题换形为352764MIN2530303535404524WXXXXXXX1352764859590100105110120205XXXXXXX1322XXX1321XXX541XX761XX011,2,3,4,5,6,7JXORJ显然零解不可行，用隐枚举法分枝定界0,1,1,1,0,1,0,210TXZ6、有四项工作要甲、乙、丙、丁四个人去完成，每项工作只允许一个人去完成，每个人只完成其中一项工作。已知每个人完成各项工作的时间如表2所示，问应指派哪个人去完成哪项工作才能使总的消耗时间为最少表2工作1工作2工作3工作4甲10131619乙14181713丙21121114丁14161812解变换系数矩阵02691440100032360找到独立零元素并在次变换026100330100041250最后得到下表中的独立零元素（0）0410011（0）120（0）61（0）30故最优方案为甲，乙，丙，丁此时总消耗时间最少。1J4J3J2J7、甲、乙、丙、丁四人要去完成五项工作，每项工作只由一个人来完成，其中有一人兼做一项工作。试指出每个人去完成哪项（或哪两项）工作才能使总的消耗时间为最少已知每个人完成各项工作的时间如表3所示。1J2J3J4J5J甲1215101820乙812201411丙189161215丁2022151012解1J2J3J4J5J甲1215101820乙812201411丙189161215丁2022151012戊89101011变换系数矩阵2508804126190734101250001221得最终表35（0）88（0）31150100734111270000110故最优方案为甲，乙，丙，丁,而乙或丁兼任3J1J2J4J5J8、某电子系统由三种元件组成，为使系统正常运转，每个元件都必须工作良好。如一个或多个元件安装几个备用件将提高系统的可靠性。已知系统运转可靠性为各元件可靠性的乘积，而每一元件的可靠性则是备用件数量的函数，具体数值见表4。又三种元件的价格分别是20、30和40元，重量分别是2、4和6千克。已知全部备用件的费用预算限制为150元，重量限制为20千克，问每个元件各安装多少备件，才能使系统的可靠性最大。表4备用件数量元件1元件2元件3005060710607092070910308101040910105101010解设元件1的备用件数从0到5分别位126XXX、，元件2备用件数从0到3分别设为7810XXX、，因为在3时已达到最优，故不需再考虑备用件数位4、5的情况；同理设元件3的备用件数从0到2为111213XXX、。12345678910111213MAX05060708090607090709ZXXXXXXXXXXXXX06436111164361011161013171201301401150214161201,1,1011,213IIIIIIIIIIIIIIIIIIIIXIXIXIXIXIXXXXXI或求解得，即元件1、2、3的备用件数分别为2、2、1。39121,1,1XXX第7章动态规划1、某公司打算向它的三个营业区增设6个销售店，每个营业区至少增设1个。各营业区每年增加的利润与增设的销售店个数有关，具体关系如表1所示。试规划各营业区应增设销售店的个数，以使公司总利润增加额最大。表1增设销售店个数营业区A营业区B营业区C1100（万元）120（万元）150（万元）216015016531901701754200180190解阶段将每个营业区作为一个阶段，即K1,2,3状态变量代表从第K各营业区到第3个营业区的店数KS决策变量KX代表第K个营业区的销售店数状态转移律1KKSSXK边界条件601S4S决策允许集合0KKKKKDSXXS阶段标准函数MAX10KKKKKSXKKXSFXGSFKK1,2,3K044SF当时3KMAX0MAX330330333333XGXGSFSXSX于是有下表2，表中表示第三个阶段的最优决策。3X表2（单位万元）3S12343X123433SF150165175190当时2KMAX2232202222XSFXGSFSX于是有表3。表3（单位万元）X2S2123422SF2X11200150121201501500150131201651501501700300241201751501651701501800320351201901501751701651801503353当时1KMAX1121101111XSFXGSFSX于是有表4。表4G1（X1）F2（S1X1）X1S10123411SF1X603451003751603201903002002704903故最优分配方案为A区建3个销售店，B区建2个销售店，C区建1个销售店，总利润为490万元。2、某工厂有100台机器，拟分4个周期使用，在每一周期有两种生产任务，据经验把机器投入第一种生产任务，则在一个周期中将有六分之一的机器报废，投入第二种生产任务，则有十分之一的机器报废。如果投入第一种生产任务每台机器可收益1万元，投入第二种生产任务每台机器可收益05万元。问怎样分配机器在4个周期内的使用才能使总收益最大解阶段将每个周期作为一个阶段，即K1,2,3，4状态变量第K阶段的状态变量代表第K个周期初拥有的完好机器数KS决策变量决策变量为第K周期分配与第一种任务的机器数量，于是该周期分配在第二种任务的机器数量。KXKKXS状态转移律15/609091/15KKKKKSSSXSKX允许决策集合0KKKKKDSXXS令最优函数1MAX0505091/15KKKKKKKKKKXDSFSSXFSX边界条件55FS0当K4时444444550MAX0505XSFSSXFS44440MAX0505XSSX因是关于的单调递增函数，故取，相应有44SF4X44SX444FSS；依次类推，可求得当时，3K33SX3311/6FSS3当时2K22XS，22291/36FSS当时1K11XS，111100671/21631065FSS计算表明，每一期都将全部机器投入第一种任务中，其中1S100，83，69，582S3S4S3、某公司生产一种产品，估计该产品在未来四个月的销售量分别为300、400、350和250件。生产该产品每批的固定费用为600元，每件的变动费用为5元，存储费用为每件每月2元。假定第一个月月初的库存为100件，第四个月月底的存货为50件。试求该公司在这四个月内的最优生产计划。解阶段将今后4个月中的每一个月作为一个阶段，即1,2,3,4K；状态变量第K阶段的状态变量S代表第个月初产品存储量；KK决策变量决策变量代表第K个月的生产量；KX状态转移律S（是第个月的销售量）；KKKKDXS1KDK边界条件，S，1100S550550FS；固定生产费用0,K0C600,K0和存贮费122KKKKKZSSXD变动生产费用KG5最优指标函数最优指标函数具有如下递推形式11MINKKKKKKKXFSCGZFS1MIN52KKKKKKKKKKKKXFSCXSXDFSXD当时4K表1S4050100150200250300X4300250200150100500F4（S4）22001950170014501200950100当K3时3333333344MIN52XFSCXSXDFS表2X3S30501001502002503003504004503X33SF04550465047503504550504300440045004600300430010040504150425043504450250405015038003900400041004200430020038002003550365037503850395040503550150，45035502503300340035003600370038003300100，4003300300305031503250335034503550305050，35030503502200290030003100320033002800022004002050225028502950305025502050当K2时表3S30501001502002503003504004502X22SF0715072504007150506900700071003506900100665067506850695030066501506400650066006700680025064002006150625063506450655066502006150当K1时表4X1S10501001502002503003504004501X11SF1008750885089509050915092502008750利用状态转移律，按上述计算的逆序可推算出最优策略为第1个月生产200件，第2个月生产400件，第3个月生产350件，最后一个月生产300件。4、用动态规划求解下述规划问题（1）（2）51MAXIIMZ22112MAXXXXZ1051IIM6322221XX0IM5,4,3,2,1I0,21XX解（1）解阶段将问题的变量数作为阶段，即3,2,1K，4，5；决策变量决策变量；KX状态变量状态变量代表第阶段的约束右端项，即从到KSKKX5X占有的份额；状态转移律；KKKXSS1边界条件110S，661FS；允许决策集合KKSX0当K5时555555555665500MAXMAX|XSXSXSFSXFSXS当K4时44444445544400MAXMAXXSXSFSXFSXSX设，于是令444HXSX44420DHDXSX可得44/2XS又因2242DHDX当当当当4又若生产出来的产品当月销售不出去，其库存费用为每台每月02万元。设在第一个月月初及第四个月月末该产品无库存，试确定在满足需求的条件下，使该工厂生产与库存总费用最小的生产方案。解阶段将今后4个月中的每一个月作为一个阶段，即1,2,3,4K；状态变量第K阶段的状态变量代表第个月存储量；KSK决策变量决策变量代表第K个月的生产量；KX状态转移律（是第个月的销售量）；KKKKDXSS1KDK边界条件150SS，550FS；生产费用和存贮费KCKZ20KKKKDXSZ最优指标函数最优指标函数具有如下递推形式11MINKKKKKKKXFSCZFS1MIN02KKKKKKKKKKKXFSCSXDFSXD当时4K表1S401234X443210F4（S4）1613510550当K3时表2X5S501234563X33SF035347634713231731463142295297294271627132627226425121862184215237239221198225198516192204196168200166137159161143013771041161080104当K2时表3X3S301234562X22SF0482476465434643414474514354144165414240241641384396386383347371375359366363590347431633324341333393280316当K1时表4X1S10123451X11SF05345515445342,6534利用状态转移律，按上述计算的逆序可推算出最优策略有两种（1）第1个月生产2台，第2个月和第3个月生产6台，最后一个月不生产2第1个月生产6，第2个月不生产，第3个月生产6台，最后一个月生产2台。总费用为534万元。8、某研发部（乙方）拟承担一种新产品的研发任务，甲方提供研发经费10万元。为适应市场竞争的需要，合同要求乙方应在三个月内向甲方交付一台合格样品，否则乙方将退还甲方10万元的研发费。据估计，研发时投产1台即合格的概率为035，投产一批的准备费用为025万元，每台的研发费用为1万元。若投产一批而未得到合格样品，可再投产一批，但每批的研发周期是一个月。试分析该研发部应否接受此研发任务，如果接受应该采用怎样的研发策略。解阶段将每个试制周期（1个月）作为一个阶段，即3,2,1K；决策变量决策变量代表第K阶段投产试制的台数；KX状态变量状态变量代表第阶段初是否已获得合格样品，尚无合格样品时，已获得合格样品时；KSK1KS0KS允许决策集合001,3,2,1KKKKSSSD状态转移律11065KXKPS，101065KXKPS；边界条件，；11S4411FS00044SF阶段指标函数02000KKKKKXXCXX最优指标函数00KKSF11111MIN065110650KKKKKXXKKKKKKKKXDSFSCXFSFS211MIN0651KKKXKKKKXDSCXFS当时3K0033SF33333333441MIN0651XXDSFSCXFS表1X3S30123453X33SF000110775648660448836当时2K0022SF22222222331MIN0651XXDSFSCXFS表2X2S20123X222SF00016515478492478当时1K11111111221MIN0651XXDSFSCXFS表3X1S10123X111SF14784364274562427即该公司的最佳试制计划为第一个月初投产试制2台；如果在第二个月初无合格样品出现，再投产试制2；如果在第三个月初仍然无合格样品出现，再投产试制3。按此最佳试制方案最小期望总费用是427元。9图论1、判断下列说法是否正确（1）图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、边的长短曲直等都要严格注意。（错）（2）当图的点集确定后，树图是所有图中边数最少的简单图。（正确）（3）在连通图G中，其权数最大的边必不包含在其最小部分树内。（正确）（4）若图中从V1至各点均有唯一的最短路，则连接V1至其他各点的最短路在去掉重复部分后，恰好构成改图的最小部分树。（正确）（5）求网络最大流问题可用线性规划数学模型加以描述（正确）2、试回答（1）具有N个顶点的完全图有多少条边；2NC（2）具有N个顶点的二分图最多有多少条边；21,2222NNNNN且为奇数，为偶数（3）具有N个顶点的简单图最多有多少条边。2NC3、在某海上油田的一个区块上有8口油井，它们相互之间的距离如表1所示。已知1号井距离海岸最近，这一最近距离为5海里。试问从海岸经1号井铺设输油管线将各油井同陆地连接起来，应如何铺设才能使输油管线的长度最短，最短输油管线的铺设长度是多少表1（单位海里）到从2井3井4井5井6井7井8井1井132109071820152井0918122623113井26172519104井071615095井0911086井06107井05解此问题可转化为求最小部分数来求，用KRUSKAL顺序生枝法求解，得到如下图的最小部分数，总长度为525102。5105060907154876320807海岸4、已知图1，试求（1）最小部分树；（2）1V点到其他各点的最短路；（3）各点之间的最短路。解（1）7V8V6V8187853V5V4V62V81V2NLG7LG23即最多运算到即可3D0D08126809121201051569100810580781210701618