考研题库 运筹学教材编写组《运筹学》（第3版）配套题库（真题 课后题 章节题 模拟题）

第二部分课后习题第1章线性规划与单纯形法第2章对偶理论与灵敏度分析第3章运输问题第4章目标规划第5章整数规划第6章无约束问题第7章约束极值问题第8章动态规划的基本方法第9章动态规划应用举例第10章图与网络优化第11章网络计划第12章排队论第13章存储论第14章对策论基础第15章单目标决策第16章多目标决策第17章启发式方法第三部分章节题库第1章线性规划与单纯形法第2章对偶理论与灵敏度分析第3章运输问题第4章目标规划第5章整数规划第6章无约束问题第7章约束极值问题第8章动态规划的基本方法第9章动态规划应用举例第10章图与网络优化第11章网络计划第12章排队论第13章存储论第14章对策论基础第15章单目标决策第16章多目标决策第17章启发式方法第四部分模拟试题运筹学教材编写组《运筹学》(第3版)模拟试题及详解(二)第一部分名校考研真题2011年南开大学897运筹学(商学院)考研真题2011年南开大学897运筹学(商学院)考研真题及详解一、某厂生产A、B两种产品，需经过金工和装配两个车间加工，有关数据如表1所示.产品B无论生产批量大小，每件产品生产成本总为400元。产品A的生产成本分段线性：第1件至第70件，每件成本为200元；从第71件开始，每件成本为190元。试建立线性整数规划模型，使该厂生产产品的总利润最大。(本题共15分)则建立线性整数规划模型如下：其对偶问题的最优解为Y*=(yi,y₂,y3,…,ym)。另有一线性规划(p2):证：问题1的对偶问题为：问题2的对偶问题为：易见，问题1的对偶问题与问题2的对偶问题具有相同的约束条件，从而，问题1的对偶问题的最优解题的最优解定是问题2的对偶问题的可行解。因为原问题与对偶问题的最优值相等，所以需加工小时数、设备的有效台时和单位产品的利润如表2所示。表2为4万元，假定各设备的有效台时数不变，投产这种产品在经济上是否合算?解：1.设生产甲、乙、丙三种产品各为xi,X2,x₃单位，则由题意得加入松弛变量后，利用单纯形法计算如下：001X₆X₆σ000010100解：设A、B、C分别代表三套仪器1#、2#,3#,A;表示在第i次实验中用仪器A,依此类推Bi、C,并设虚拟开始S和结束点D。则得网络图如图1所示：求总的中断试验的时间最小，即找最短路问题，利用Dijkstra算法计算如下：∵A₁,B₁,C₁到S点距离相同，∴可同时标号(5)比较T(A4)、T(B4)、T(C4),可得出，T(B4)最小的使用顺序是：三=,即3#-2#-3#-2#。五、某农场考虑是否提早种植某种作物的决策问题，如果提早种，又不遇霜冻.则收入为45元：如遇霜冻，则收入仅为10万元.遇霜冻的概率为0.4。如不提早种，又不遇霜冻.则收入为35万元：即使遇霜冻.受灾也轻，收入为25万元，遇霜冻的概率为0.2,已知：(1)该农场的决策者认为：“以50%的机会每45万元.50%的机会得10万元”和“稳获35万元”(2)该农场的决笨者认为：“以50%的机会得45万元，50%的机会得35万元”和“稳获40万(3)该农场的决策者认为：“以50%的机会得35万元，50%的机会得10万元”和“稳获25万元”二者对其来说没有差别。(南开大学2011研)1.说明该决策者对风险的态度，按期望效用最大的原则，该决策者应做何种决策?2.按期望收益最大的原则，该决策者又应做何种决策?解：1.将最高收益45万元的效用定为10,记为。把最低收益值10万元的效用定为0,记为令提早种的期望效用为=,不提早种的期望效用为=。则,所以，决策者的决策应为不提早种。2.令提早种的期望收益为三，不提早种的期望收益为三。表4(1)标号过程③检查B,在弧(B1,D)上，,则给D标号(B1,20),这样找到了一条增广链，(2)调整过程，由(1)知，3=,得新的可行流量图，如图3所示。图3依据上述方法，重复标号及调整过程，直到不存在增广链为止，最终得最大流量图，如图4所示。调运方案如表5所示.A₁A₂A₃图4表5B₁B₂B₃B₄实际供出量七、某公司生产两种小型摩托车.其中甲型完全由本公司制造，而乙型是进口零件由公司装配而成，这两种产品每辆所需的制造、装配及检验时间如下表6所示。表6P₁每周的总利润至少为3000元：P₂:每周甲型车至少生产5辆；P3:尽量减少各道工序的空余时间，三工序的权系数和它们的某商科技公司的MIS中心处理本公司信息系统的维护服务。公司其他部门职员打电话到信该中心每小时平均接受到40个服务请求，服务请求的到达服从泊松分布。每个请求的平均服务时间是3分钟，且服从负指数分布。信息中心服务人员每小时的平均工资是15元。公司职员每小时为公司创造的收益是25元。我们已经通过软件计算出服务中心的服务人员个数与等待接受MIS维护服务的平均职员数之间的关系，如表7所示。表71.如果公司经理希望职员等待MIS维护服务(排队等待和服务等待的平均时间)不要超过52.如果公司经理考虑聘用服务人员的成本以及因为等待或正在接受MIS维护服务造成的企25分，其中第一小题10分，第二小题15分)解：1.要求等待MIS维护服务时间小于等于5分钟，已知平均服务时间是3分钟，故服务时间是2分钟，约是0.0333小时查表6可知，该信息中心最少需要聘用服务人员3人。cW234表856表93456Z869.432547.500262011年南开大学813运筹学(信息学院)考研真题及详解一、(35分)已知某工厂计划生产A、B、C三种产品，备产品均需使用甲、乙、丙这三种数据如表1所示。试问：(1)应如何安排三种产品的生产使得总利润最大?(2)若另有两种新产品D、E,生产单位D产品需用甲、乙、丙三种设备12小时、5小时、10小时，单位产品利润2.1千元；生产单位E产品需用甲、乙、丙三种设备4小12小时，单位产品利润1.87千元，请分别回答这两种新产品投产是否合算?(3)若为了增加产量，可租用其他工厂的设备甲，可租用的时间是60小时，租金1.8万元。(4)增加设备乙的工时是否可使工厂的总利润进一步增加?添加人工变量x₄,X₅,x6利用单纯形法计算如表2所示。(2)增加新变量x7,x₈,对应的c7=2.1,cg=1.87,约束矩阵增加两个列向量则判断出：产品D的投产不合算，产品E投产合算。(3)即,其不影响检验数的结果，故最优解不变。(4)当增加乙的工时，,故利润不会增加。二、(15分)有A、B、C、D四种零件均可在设备甲或设备乙上加工。已知这两种设备上分别加工一个零件的费用如表3所示。又知设备甲或设备乙只要动费用，分别为100元和150元。现要求加工四种零件各3件，问应如何安排生产使总的费用最小?请建立该问题的线性规划模型(不需求解)。加工一个零件的费用(单位：元)表3三、(25分)某工程公司在未来1~4月份内需完成三项工程：第一项工程的工期为1~3月份，总计需劳动力80人月；第二项工程的工期为1~4月份，总计需劳动力100人月；第三项工程的工期为3～4月份，总计需劳动力120人月。该公司每月可用劳力为80人，但任一项工程上投入的劳动力任一月内不准超过60人。问该工程公司能否按期完成上述三项工程任务，应如何安排劳力?(请将该问题归结为网络最大流问题求解)解：可以构建网络图(弧上数字为最大流量),如图1所示。其中，结点1、2、3、4分别代表1、2、3、4月份，结点5、6、7分别代表第一、二、三项工程。通过标号与调整，得到的最大流如图2所示。图2所以该公司能按期完成上述三项工程任务，安排劳力的方案可以为：1月份，安排60人做第一项任务、20人做第二项任务；2月份，安排60人做第二项任务；3月份，安排60人做第三项任务、20人做第一项任务；4月份，安排60人做第四项任务、20人做第三项任务。四、(25分)某工厂设计的一种电子设备由A、B、C三种元件串联而成，已知三种元件的单价分别为2万元、3万元、1万元，单件的可靠性分别为0.7、0.8、0.6,要求设计中使用元件的总费用不超过10万元，问应如何设计使设备的可靠性最大?(请使用动态规划方法求解：设各种元件的个数为x1,X₂,X3,则根据变量的个数，将该问题分为3阶段。设状态变量令最优值函数f.(s)表示第k阶段的初始状态为sk,从第k阶段至第3阶段的最大值，用逆推方法用逆推方法由由,但1≤x₂≤S₂/3,s₂≤10-2*1=8,∵I≤xi≤S₁/2,且为整即购买三种元件分别为3件、1件、1件。五、(25分)某公司兴建一座港口码头，只有一个装卸船只的位置。设船只到达的间隔时间和装卸时间都服从负指数分布，预计船只的平均到达率为3只/天，船只到港后如不能及时装卸，停留一日公司将损失1500元。现需设计该港口码头的装卸能力(即每日可以装卸的船只数),已知单位装卸能力每日平均生产费用为2000元，问装卸能力为多大时，每天的总支出最少?在此装卸能力之下，求：(1)装卸码头的利用率；(2)船只到港后的平均等候时间?(3)船只到港后总停留时间大于一天的概率。所以时，每天的总支出最少。∴码头的利用率为1-P⁰=2/3即船只到港后的平均等候时间是(3)设船只到港后的总停留时间T六、(25分)已知A、B各自的纯策略及A的赢得矩阵如表4所示，求双方的最优策略及对策值。解：在A的赢得矩阵中第4列优超于第2列，第1列优超于第3列，故可划去第2列和第3列，得到新的赢得矩阵对于=,第二行优超于第4行，因此去掉第4行，得到1检验数1检验数00y₆1检验数01121001001000-1/81/7表501第二部分课后习题第1章线性规划与单纯形法可得A₃的坐标为(2,4),所以,该线性规划问题具解：如图1-2所示，该线性规划问题的可行域无界。目标函数在点A处取得最小值，求解方程组得A点的坐标为,所以,该问题具有惟一最优解。解：如图1-3所示，该问题的可行域无界。目标函数可以增加到无穷大，因此该问题无最优解或称为无界解。解：如图1-4所示，该问题的可行域为空集，因此该线性规划无可行解。1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。 解：令,且;在第一个约束条件两边同时乘以-1后引入人工变量-=,在第二个约束条件右端加上松弛变量4=;在第三个约束条件右端减去剩余变量4=,同时加入人工变量三，将目标函数最小化变换为最大化，得该线性规划的标准型其中，M为充分大的正数，对应的初始单纯形表如表1-1所示。解：在上述约束条件两边同时乘以-1,然后分别引入人工变量x1:x₂:.x,得该线性规划的标准型其中，M为充分大的正数。对应的初始单纯形表如表1-2所示。1.3在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解，并代入目标函数，确定哪一个是最优解。解：在第二个约束条件两边同时乘以-1,得到该线性规划问题的系数矩阵①因为三、三线性无关，故有P③因为1、=线性无关，故有令非基变量],解得故有基可行解⑥因B、「线性无关，故有,解得不是可行解。解：其系数矩阵为①因为P、P线性无关，故有不是可行解。令非基变量x₂=x₄=0,解得为基可行解，P、P线性无关，故有③因为令非基变量₂=x₃=0,解得不是可行解。④因为P、P线性无关，故有⑤因为⑥因为2、P4线性相关，故一不能构成基变量。在E=中，三为最大值，所以最优解1.4分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相当于图1-5该线性规划问题的可行域如图1-5所示。由图可1,对应于图上的点A₂,其最优目标函数值—=三。引入松弛变量,得该线性规划问题的标准型故问题的最优解一,最优目标函数值z=33/4。单纯形表第一步迭代得,对应于图1-5中的的坐标原点；单纯形表第二步迭代得,对应于图1-5中的点A₃(4,0);单纯形表第三步迭代得,对应于图1-5中的点A₂该线性规划的可行域如图1-6所示，由图知该线性规划的惟一最优解为,对应于图上的点A₂(2,6),最优目标函数值为在上述问题的约束条件中引入松弛变量,得到该规划问题的标准型利用单纯形表进行迭代计算如表1-4所示。故问题的最优解一,最优目标函数值z=34。单纯形表第一步迭代得I,对应于图1-6中的的坐标原点；单纯形表第二步迭代得,对应于图1-6中的点A₁(0,6);单纯形表第三步迭代得,对应于图1-6中的点A₂(2,6)。1.5以第1.4题(1)为例，具体说明当目标函数中变量的系数怎样改变时，使满足约束条件的可行域的每一个顶点，都有可能使目标函数值达到最优。①若则当一时，目标函数在点A₃(4,0)处取得最大值；当时，目标函数在原点(0,0)处取得最大值；②若，则当一日时，目标函数在点A₂(15/4,3/4)处取得最大值，其中时，在线段A₂A₃上的任一点取得最大值；当一时，目标函数在原点处取得最大在线段A₁A₂上的任一点取得最大值；当一E=时，目标函数在坐标原点处取得最大值；(2)当一E=时，目标函数①当一F时，目标函数在点A₃(4,0)处取得最大值；②当一=时，目标函数在可行域OA₁A₂A₃中的任一点处均可取得最大值；③当一==时，目标函数在线段OA₁上的任一点取得最大值。1.6分别用单纯形法中的大法和两阶段法求解下述线性规划问题，并指出属哪一类解。在上述问题的第二个约束条件中减去剩余变量3,再加入人工变量一，得其中，是一个任意大的正数，应用单纯形法迭代计算如表1-5所示。0010111101表1-50-1010M/2+1-3M/2-1757最优目标函数值=故-为原线性规划问题的基可行解。在上述两个约束条件中依次分别减去剩余变量,再加上人工变量E,得的检验数中,所以该线性规划问题有无穷多最优解。在上述线性规划问题的约束条件中分别减去剩余变量x4:Xs,再加上人工变量X₆:Xx,得第上述线性规划问题最优L,其目标函数最优值0*=0,可以继续故此线性规划问题有无穷多最优解。去剩余变量再加上人工变量7,并化为标准型，得010010-Mx752361111000109939/80000σσ01/16σ变量=,故原线性规划问题无可行解。去剩余变量再加上人工变量，得第一阶段的数学模型为在最终单纯形表中，人工变量x=1/2≠0,而所有非基变量的检验数均满足一旧，所在原线性规划问题的约束条件中分别减去剩余变量=,再加上人工变量，σ001o3M/2+3/-5M/2-301σσ100==,0-11θ604在最终单纯形表中，在最终单纯形表中，11110100000σ0000x₂11000000100010010-1/21/2-b由表1-15中计算可知，在上述问题的第一个约束条件中加入松弛变量三，第二个约束条件左右两边同时除以2再加入松弛变量=,得到该线性规划问题的标准型解得最优解三=,目标函数z的上界(2)要求z的下界2,则一应取其最小值；应取其最大值，此时，在上述问题的第一个约束条件中加入松弛变量三，第二个约束条件左右两边同时除以2再加入松弛变量=,得到该线性规划问题的标准型1.8表1-18是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，(1)表中解为惟一最优解；(2)表中解为最优解，但存在无穷多最优解；(3)该线性规划问题具有无界解；(4)表中解非最优，为对解改进，换入变量为F,换出变量为x₆。(2)当且三=0时，表中的解为最优解，且原问题有无穷多个最优解；进，换入变量为E,换出变量为x6。1.9某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如表1-19所示。设司机和乘务人员分别在各时间区段一开始时上班，并连续工作8h,问该公交线路至少需配备解：设一为从第班次开始上班的司机和乘务员的人数，则可建立数学模型为：中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如表1-20所示。表1-20售价(元/问该厂每月应生产这三种牌号糖果各多少千克，才能使该厂获利最大?试建立该问题的线性规划模型。解：设甲糖果中原料A、B、C的含量分别为xi:x₂.Xx3;乙糖果中原料A,B,C的含量分别为丙糖果中原料A、B、C的含量分别为x7:xg:X,则生产甲糖果癫骨起骨写千克，乙糖果—=千克，丙糖果—=,可建立如下数学模型：1.11某厂生产三种产品I,Ⅱ,Ⅲ。每种产品要经过A,B两道工序加工。设该厂有两种规格的设备能完成A工序，它们以A,A₂表示；有三种规格的设备能完成B工序，它们以B,B₂,B₃表示。产品I可在A,B任何一种规格设备上加工。产品Ⅱ可在任何规格的A设备上加工，但完成B工序时，只能在B₁设备上加工；产品Ⅲ只能在A₂与B₂设备上加工。已知各种设备的单件工时，原材料费，产品销售价格，各种设备有效台时以及满负荷操作时设备的费用如表1-21所示。要求安排最优的生产计划，使该厂利润最大。A₂47表1-21原料费(元/0.20.30.5解：设|==分别为用Ai,A₂加工产品I的件数，,x:X:X5分别用Bi,B₂,B₃加工产品I的件用A₂及B₂加工产品Ⅲ的件数。由题意，可建立数学规划模型：即用A₁加工产品I1200件，用A₂加工产品I230件，用B₁加工产品I0件，用B₂加工产品 I859件，用B₃加工产品I571件，用A₁加工产品ⅡO件，用A₂加工产品Ⅱ500件，用B₁加工产品Ⅱ500件，用A₂及B₂加工产品Ⅲ324件，可获得最大利润1147元。第2章对偶理论与灵敏度分析2.1用改进单纯形法求解以下线性规划问题。得到初始基,初始基变量;非基变量,对应的系数非基变量的检验数ox=C。-C₈B=N₀=(6.-2.3),则1为换入变量。,所以对应的换出变量为x4。计算换入变量1的系数向量F及一=为：计算非基变量的检验数为：由一=可确定F为换入变量，再由 知5为换出变量。计算换入变量的系数向量=及一==为：非基变量的检验数向量为此时，非基变量的检验数均为负，最优解为最优目标函数值为解：在第二个约束条件中减去剩余变量考，再分别在第一、二个约束条件中加入人工变量x4.x3,在第三个约束条件中加入松弛变量%,得该线性规划的标准型：得到初始基,初始基变量,对应的系数Xx=(x,x₂,x),,对应的系数。非基变量的检验数L,则1为换入变量。,所以对应的换出变量为x4。由此得到新的基B₁、基变量XE及系数C、非基变量XA及系数Cx.分别为：计算换入变量1的系数向量P及B₁为：由N₂可确定为换入变量，再由知X5为换出变量。因为非基变量的检验数均大于0,故问题的最优解为：2.2已知某线性规划问题，用单纯形法计算时得到的中间某两步的计算表见表2-2,试将表2-2解：先求=,由上表中的上一部分知表中空缺的系数矩阵为迭代后的基变量对应的系数，所以表2-2中要填写的数字如表2-3所表2-32.3写出下列线性规划问题的对偶问题。解：设对应于各约束条件的对偶变量为,则其对偶问题为：解：设对应于各约束条件的对偶变量为,则其对偶问题解：设对应于各约束条件的对偶变量为1,则其对偶问题为：2.4判断下列说法是否正确，为什么?(1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；(2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解；(3)如果线性规划的原问题和对偶问题都具有可行解，则该线性规划问题一定具有有限最解：(1)错误。线性规划的原问题存在可行解，其对偶问题不一定存在可行解。当原问题易知该线性规划问题存在可行解，如,该问题的对偶问题为(2)错误。当线性规划问题的对偶问题无可行解时，原问题可能具有无界解或者是无可行(3)错误。当线性规划的原问题和对偶问题都具有可行解时，该线性规划问题可能存在有2.5设线性规划问题1是)是其对偶问题的最优解。又设线性规划问题2是其中三是给定的常数，求证证明：问题1的矩阵表示为设=为它的一个可行解，其对偶问题的最优解为问题2的矩阵表示为设：=为它的一个可行解，其对偶问题的最优解为问题1的对偶问题为问题2的对偶问题为由此可知，问题1的对偶问题与问题2的对偶问题有相同的约束条件，所以问题1的对偶问题的最优解x=(i.…v)一定是问题2的对偶问题的一个可行解。又因为Y2是问题2对偶问题的最优解，所以，2.6已知线性规划问题用单纯形法求解，得到最终单纯形表如表2-4所示。表2-4解：(1)由题意可设初始单纯形表的增广矩阵为对矩阵二：=作初等行变换，使其第4,5列组成单位矩阵(2)由检验数的计算式可知2.7已知线性规划问题其对偶问题的最优解为==,试应用对偶问题的性质，求原问题的最优解。将分别代入对偶问题的各约束条件中，可知，式①和式②为严格不等式，由互补松弛性可知,所以根据互补松弛性知，原问题的两个约2.8试用对偶单纯形法求解下列线性规划问题。解：在两个约束条件两边同乘以-1,再分别加入松弛变量一F得到如下形式列出初始单纯形表，并利用对偶单纯形法进行求解，求解过程如表2-5所示。表2-5得线性规划问题的最优解为L,目标函数值为。解：先将上述线性规划问题化成如下形式，以便得到对偶问题的初始可行基建立此问题的初始单纯形表，并利用对偶单纯法进行计算，如表2-6所示。表2-61202/5(1)约束条件式①的右端常数由20变为30;(2)约束条件式②的右端常数由90变为70;(3)目标函数中=的系数由13变为8;(4)=的系数列向量由(6)将原约束条件②改变为所以，原问题得到最优解为1,最优目标函数值=。(1)约束条件式①的右端常数由20变为30列出单纯形表，并利用对偶单纯形法求解，求解过程如表2-8所示。表2-8所以，线性规划问题的最优解变为,最优目标函数值为=。(2)约束条件式②的右端常数由90变为70列出初始单纯形表，并利用对偶单纯形法进行迭代计算，求解过程如表2-9所示。表2-9所以，线性规划的最优解变为,最优目标函数值为—[(3)目标函数中3的系数由13变为8在约束条件式③中加入松弛变量6,得。将此约束条件加入原单C50b5131σ030310001025027/25300000001000000010010所以，线性规划的最优解变为,最优目标函数值为一=。2.10已知某工厂计划生产I,Ⅱ,Ⅲ三种产品，各产品需要在A,B,C设备上加工，有关表2-11设备代号IⅡⅢ设备有效台时/月单位产品利润/千元322.9试回答：(1)如何充分发挥设备能力，使生产盈利最大?(2)若为了增加产量，可借用其他的工厂的设备B,每月可借用60台时，借用金1.8万元，问借用设备B是否合算?(3)若另有两种新产品IV,V,其中IV需用设备A12台时，设备B5台时，设备C10台时，单位产品盈利2.1千元；新产品V需用设备A4台时，设备B4台时，设备C12台时，单位产品盈利1.87千元。如设备A,B,C设备台时不增加，分别回答这两种新产品投产在经济上是否合算?(4)对产品工艺重新进行设计，改进结构，改进后生产每件产品I,需用设备A9台时，设备B12台时，设备C4台时，单位产品盈利4.5千元，问这对原计划有何影响?解：(1)设分别生产产品I,Ⅱ,Ⅲ三种产品：x₂x3单位，由题意，可建立数学模型在上述线性规划问题的约束条件中分别加上松弛变量建立初始单纯形表，并利用单纯形法进行迭代，过程如表2-12所示。C3可σ10000100000010001030019σ所以生产IV产品在经济上不合算。在最终单纯形表中对应的列向量及对应的检验数为所以，生产产品V在经济上合算。将的系数列向量加入最终单纯形表，并进行进一步迭代，如表2-13所示。0003x,107/41023/401/4021/24-3/8007σ,最优目标函数值为所以，改进技术后能带来更多的经济效益。2.11分析下列参数规划中当变化时最优解的变化情况。解：在约束条件中分别加入松弛变量x4:x,:xs,并将模型化为标准型为令t=0,并利用单纯形法进行求解，如表2-14所示。000σXBbX₁X₂X₃X₄X₅X₆θ02301所以，该线性规划问题的最优解为一,将目标函数系数的变化直接反映到最终表上，如表2-15所示。表2-15当t≤1时，所有变量的检验数均不大于0,最优解X=(0.100.230.0.0.20)";当t>1时，,需进行进一步迭代，以三为换出变量，三为换入变量，进一步迭代过程如表2-16所示。o00000000x₄4301101000420σ所以，当t>1时，最优解为解：在约束条件中分别引入松弛变量,并化成如下标准型。表2-20令t=0,并利用单纯形法进行求解，如表2-17所示。所以，该线性规划问题的最优解为一,将目标函数系数的变化直接反映到最终表上，如表2-18所示。表2-18Cb01510o00当O≤t≤8/3时，所有变量的检验数均不大于0,最优解一当>8/3时，σ₄>0,需进行进一步迭代，以F为换出变量，,=为换入变量，进一步迭代过程如表2-19所示。表2-19θ当t>5时，,需进行进一步迭代，以一三为换出变量，三为换入变量，进一步迭代过程如表2-20所示。令t=0,并利用单纯形法进行求解，如表2-21所示。0200201b5210210001000101110110010000100010001001000101000010001001-计算：将计算结果代入到最终单纯形表中，得到表2-22。表2-22所示。2-24所示。0σ表2-240100101001011010b10所以，当t=0时，该线性规划问题的最优解为当O≤≤6时，表2-25中=12.,得最优解00所示。表2-28所以，当11<t≤59时，族=12.0,,最优解为3.1判断表3-1和表3-2中给出的调运方案能否作为用表上作业法求解时的初始解?为什么?表3-1表3-2解：表3-1中有5个基格，而要作为初始解，应有m+n-l=3+4-1=6个基格，所以表3-1给出的调运方案不能作为表上作业法的初始解；表3-2中，有10个数基格，而理论上只应有m+n-l=9个，多出了一个，所以表3-2给出的调运方案不能作为表上作业法的初始解。3.2表3-3和表3-4中，分别给出两个运输问题的产销平衡表和单位运价表，试用伏格尔(Vogel)法直接给出近似最优解。表3-3表3-4表3-9运价12315182241336749解：(1)第一步：在表3-3中分别求各行和各列的最小运价和次小运价的差额，并分别填入该表的最右列和最下行，如表3-5所示。表3-5第二步：从行差额或列差额中选出最大者，选择它所在行或列中的最小元素。在表3-5中，第3列是最大差额所在列。第3列中最小元素为1,可确定产地2的产品优先供应销地3的需要，得表3-6。同时将运价表中的第3列数字划去，如表3-7所示。表3-6表3-7第三步：对表3-7中未划去的元素再分别计算出各行、各列的最小运价和次小运价的差额，并填入该表的最右列和最下行。重复第一、二步，直到给出初始解为止，初始解如表3-8所(2)第一步：在表3-4中分别计算各行和各列的最小运价和次小运价的差额，并分别填入该表的最右列和最下行，如表3-9所示。第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表3-9中第3列是最大差额所在列。第3列中最小元素为3,可确定产地1的产品优先供应销地3的需要。同时将运价表中的第1行数字划去，如表3-10所示。表3-10单单位销地运价12345产量139zS2435745M8填入该表的最右列和最下行。重复第一、二步，直到给出初始解为止，初始解见表3-10的3.3用表上作业法求表3-11至表3-14中给出的运输问题的最优解(表中数字M为任意大正表3-11表3-12表3-13表3-14解：(1)解表3-11表3-19第一步：用伏格尔法求初始可行解(过程类似于上一题，不再赘述),求得的初始解如表3-15所示。第二步：用位势法进行最优解的判断。在对应于表3-15的数字格处填入单位运价，并增加的三和三，如表3-16所示。对于表3-16中的空格，依据检验数，如表3-17所示。表3-16表3-17由表3-17可知，所有空格处的检验数均为非负。所以，表3-15中的运输方案，即为此问题的最优调运方案，最小运价为32。由于非基变量的检验数中一3三，所以该运输问题有无穷多最优解。(2)解表3-12第一步：用伏格尔法求初始可行解，求得的初始解，如表3-18所示。第二步：用位势法进行最优解的判断。在对应于表3-18的数字格处填入单位运价，并增加一行一列，在行中填入E,在列中填入日。令一，按照求出所有的和，并依据三=计算所有空格处的检验数，计算结果如表3-19所示。由表3-19可知，所有空格处的检验数均为非负。所以，表3-18中的运输方案即为此问题的最优调运方案，最小运价为118。(3)解表3-13由于表3-13中产大于销，因此需要增添一个假想的销地“己”,其运价为0,其销量为2,如表3-20所示。表3-20第一步：用伏格尔法求初始可行解，求得的初始解，如表3-21所示。表3-21一行一列，在行中填入，在列中填入“。令=0,按照量=(J∈B)求出所有的“i和V,并依据表3-22表3-25由表3-22可知，所有空格处的检验数均为非负。所以，表3-21中的运输方案即为此问题的最优调运方案，最小运价为90。由于非基变量的检验数中=所以该运输问题(4)解表3-14由于表3-14中产大于销，因此需要增添一个假想的销地“己”,其运价为0,其销量为40,如表3-23所示。表3-23第一步：用伏格尔法求初始可行解，求得的初始解，如表3-24所示。甲乙丙丁戊己123405第二步：用位势法进行最优解的判断。在对应于表3-24的数字格处填入单位运价，并增加一行一列，在行中填入V,在列中填入ü:。令Y=0,按照u:和V,并依据0,=c-(u+v,)iEN)计算所有空格处的检验数，计算结果如表3-25所示。在表3-25中，。所以，表3-24中的运输方案不是此问题的最优调运方案，需从表3-25中的空格(3,1)出发点作一闭回路，并对闭回路上的点进行正负编号，如表3-26表3-26运运甲乙丙丁戊己量12345由表3-26可知，调入量为0,按闭回路上的正、负号，加上或减去调入量。调整后的调运方案，如表3-27所示。表3-27第四步：重复第二、三步，得到新的调运方案，如表3-28所示。表3-28对表3-28中给出的调运方案，再用位势法进行检验，如表3-29所示。表3-29位价运价甲乙西T戊己1280602M03063M0047805535036由表3-29可知，所有空格处的检验数均为非负。所以，表3-28中的运输方案即为此问题的3.4已知运输问题的产销平衡表、单位运价表及最优调运方案分别见表3-30和表3-31,试表3-30表3-31(1)从A₂→B₂的单位运价=在什么范围变化时，上述最优调运方案不变?(2)从A₂→B₄的单位运价=变为何值时，有无穷多最优调运方案?除表3-30中方案外，解：(1)因为，当以单位运价表计算的基变量检验数为0,且非基变量检验数为非负时，调运方案不变。所以，假设三未知，对表3-30中的最优调运方案，利用位势法计算非基变量的检验数，如表3-32所示。表3-32表3-37计算得，当厂时，表3-30给出的最优方案不变。(2)当存在某非基变量的检验数为0时，有无穷多最优解。假设C24未知，利用位势法计算所有非基变量的检验数，如表3-33所示。表3-33可得,所以当C24变为17时，此问题有无穷多最优调运方案。以表3-34表3-35预计售出后的利润(元/套)也不同，详见表3-36。请帮助该公司确表3-36解：用10减去利润表上的数字，使之变成一个运输问题，如表3-37所示。利用伏格尔法求出表3-37运输问题的初始解，求解结果见表3-38。利用位势法求出表3-38中各空格的检验数，如表3-39。表3-39整。利用闭回路法进行调整，结果如表3-40所示。表3-40利用位势法求出表3-40中各空格的检验数，如表3-41所示。表3-41由表3-41可知，所有空格处的检验数均为非负。所以，表3-40中的运输方案即为此问题的最优调运方案，最小运价为72000元。3.6甲、乙、丙三个城市每年需要煤炭分别为：320、250、350万吨，由A、B两处煤矿负运价(万元/万吨)见表3-42。由于需大于供，经研究平衡决定，甲城市供应量可减少0～30万吨，乙城市需求量应全满足，丙城市供应量不少于270万吨。试求将供应量分配完又使总年煤炭总供应量为850万吨。可见供少于需，故虚拟一个产地煤矿C,其供应量为70万吨，由题意可构造如表3-43的运价表。问题变为求解表3-43的最优调运方案。表3-43第一步：用伏格尔法求初始可行解，求得的初始解，如表3-44所示。表3-44第二步：用位势法进行最优解的判断。在对应于表3-44的数字格处填入单位运价，并增加表3-45由表3-45可知，所有空格处的检验数均为非负。所以，表3-44中的运输方案即为此问题的最优调运方案，最小运价为14650万元。3.7某造船厂根据合同要从当年起连续三年末各提供三艘规格型号相同的大型客货轮，已知该厂在三年内生产大型客货轮的能力及每艘客货轮的成本如表3-46所示。已知加班生产时，每艘客货轮成本比正常生产时高出70万元。又知造出来的客货轮如当年不交货，每艘每积压一年造成积压损失为40万元。在签订合同时，该厂已储存了两艘客货生产量，使在满足上述各项要求的情况下，总的生产解：设F为第1年的正常生产能力，F为第1年的加班生产能力；为第「年的需求订货，S为因积压而产生的供货能力。因为产大于销，的运价表。问题变为求解表3-47的最优调运方案。表3-47单位：千万元第一步：用伏格尔法求初始可行解，求得的初始解，如表3-48所示。从表3-49中的空格==出发作一闭回路，利用闭回路法进行调整，得到的结果如表3-50继续重复第二、三步，再一次得到新的调运方案，如表3-52所示。表3-52利用位势法计算表3-52中空格处的检验数，如表3-53所示。表3-532000M0MAMoMMM0s0v由表3-53可知，所有非基变量的检验数均为非负。所以，表3-52中的解为最优解，最小运价为4730万元。由于存在一个非基变量的检验数为0,所以此问题有无穷多最优解。即，该厂第1年生产2艘船供应第1年和第2年；第2年正常生产4艘，其中2艘船供应给第2年，另2艘储备；第3年正常生产1艘供应给第3年，加班生产3艘再供应给第3年。另有2艘船是原先储备下来而供应给第1年。这样可以使得总的生产费用加积压损失最少。4.1若用以下表达式作为目标规划的目标函数，试述其逻辑是否正确?解：(1)不正确。当要求==时，问题变为求一F或一=最大，即超过目标值越大越好，或未达到目标值越大越好，这两项是相反方向的，所以即表示未达到目标值越大越好。图4-2从图4-2中可以看到，在考虑具有P1的目标实现后，x:x2的取值范围为OADFO;考虑P₂的目标要求实现后，x:x2的取值范围为E=;考虑-三的目标要求实现后，x₁:x₂的取值范围为BE;考虑=的目标要求实现时，因为三的权系数大于=的权系数，故考虑,所以点E为满意解，其坐标为,即满意解是一解：令各偏差变量为0,作出所有的约束直线，并标示出各偏差量增加对约束直线的影响，如图4-3所示。图4-3的目标要求实现时，要实现一|==|,从图中可以看出，只有B点可使-三最小，所以B点为满足目标规划问题的满意解，其坐标为一==|,即满意解是|==。4.3用单纯形法求解以下目标规划问题的满意解。解：在第三个约束条件中加入松弛变量考，该目标规划的标准型为：建立初始单纯形表，在表中将检验数列按优先因子个数排成两行，并采用单纯形法进行进一步迭代，如表4-1所示。表4-1c00000b2Z101005000108211000080000010020051000006103010020000061000200x0100110003001一00000001001010000100001000101/600000001001010由表4-1可知，为该目标规划的满意解。由于非基变量三的检验数为0,所以该问题有多重解。进一步迭代得另一满意解为解：建立初始单纯形表，在表中将检验数列按优先因子个数排成4行，并采用单纯形法进行进一步迭代，如表4-2所示。表4-2表4-2由表4-2可知，为该目标规划的满意解。解：建立初始单纯形表，在表中将检验数列按优先因子个数排成两行，并采用单纯形法进行进一步迭代，如表4-3所示。表4-34.4以下为目标规划问题，试求以下问题。(1)用单纯形法求这问题的满意解；(2)若目标函数变为解有什么变化?(3)若第一个目标约束的右端项改为120,这时原满意解又有什么变化?解：(1)建立初始单纯形表，在表中将检验数列按优先因子个数排成三行，并采用单纯形法进行进一步迭代，求解过程如表4-4所示。表4-4由表4-4可知，为该目标规划的满意解。(2)将变化的优先等级直接反代入表4-4的最终单纯形表中，再计算各变量的检验数，如表4-5所示。表4-5表4-5目标函数变化后，各检验数均为非负，所以满意解不变，仍为o(3)首先计算：将一的值代入表4-4中最终单纯形表的b列中，并进一步迭代，如表4-6所示。表4-64.5某商标的酒是用三种等级的酒兑制而成。若这三种等级的酒每天供应量和单位成本为：设该种牌号酒有三种商标(红、黄、蓝),各种商标的酒对原料酒的混合比及售价，见表4-7。决策者规定：首先必须严格按规定比例兑制各商标的酒；其次是获利最大；再次是红商标的酒每天至少生产2000kg,试列出数学模型。表4-7解：设以分别为兑制红、黄、蓝三种商标的酒时第1种等级的酒的用量，由题意可建立如下数学模型：可根据如下模型求出：5.1对下列整数规划问题，问用先解相应的解：在该线性规划问题的约束条件中分别加入松弛变量≥,,化为标准型先不考虑上述模型中的整数约束，利用单纯形法进行求解，如表5-1所示。表5-1此时的最优解为,最优目标值时均为非可行解.用分支定界法进一步求解此整数规划.求得B₂的最优解为max于是得到l,再将B₁分解成两个子问题：求得三的最优解为max面表5-2 B₃已求得整数解，则可取为,故1,对于B₂而言，继续分解已无意义，可舍去。继续将B₄分解为两个子问题：B₅无可行解，舍去。求得B₆的最优解所以，得到最优解,与用舍去法得到的最优解一致。所以，用先解相应的线性规划然后凑整的办法能得到最优整数解。解：在该线性规划问题的约束条件中分别加入松弛变量x::x4,并化为标准型先不考虑上述模型中的整数约束，利用单纯形法进行求解，如表5-2所示。此时的最优解为时，为非可行解。对该最优解进行凑整，当凑整为时，为非可行解。用分支定界法进一步求解此整数规划。记一，因为X=(0.0.0.0)为可行解，所以1。将原问题分解为两个求得B₁的最优解求得B₂的最优解B₁已求得整数解，则可取故一,继续将B₂分解为两个子问题：求得B₃的最优解减去B3、B₄枝，从而最优整数解5.2用分支定界法解以下问题。解：在该线性规划问题的约束条件中分别加入松弛变量：x4,化为标准型先不考虑模型中的整数约束，利用单纯形法求解，过程如表5-3所示。表5-3子问题：求得B₁的最优解求得B₃的最优解B₄:maxz=x+x₂B₅:maxz=x+x₂求得B₅最优解,或者为整数解，所以可取B₆:maxz=x+x₂因为，减去B3分枝，得最优整数解为解：(1)在该线性规划问题的约束条件中分别加入松弛变量.x4,化为标准型先不考虑上述模型中的整数约束，利用单纯形法进行求解，如表5-4所示。表5-4最优目标值由表5-4中最终单纯形表可得变量间的关系式：将系数和常数项都分解成整数和非负真分数之和，移项将系数和常数项都分解成整数和非负真分数之和，移项要求将该约束条件加入到表5-4的最终单纯形表中，并进行进一步求解，如表5-5所示。表5-5由于x₁:x₂已为整数，所以最优解为(2)在该线性规划问题的约束条件中分别加入松弛变量及人工变量5,化为标准型maxz=3x-x₂-Mx₃先不考虑模型中的整数约束，利用单纯形法进行求解，如表5-6所示。表5-66一(2)≤0加入松弛变量，得到切割方程：将该约束条件加入到表5-6的最终单纯形表中，并进一步求解，如表5-7所示。表5-7从表5-7中得到的是非整数解，需要进一步求解。按照上述步骤，再次加入切割方程并进行求解，最终求得：5.4某城市的消防总部将全市划分为11个防火区，设有4个消防(救火)站。图5-1表示各防火区域与消防站的位置，其中①②③④表示消防站，1、2、.….、11表示防火区域。根据历史资料证实，各消防站可在事先规定的允许时间内对所负责的地区的火灾予以消灭。图中虚线即表示各地区由哪个消防站负责(没有虚线连接，就表示不负责)。现在总部提出：可否减少消防站的数目，仍能同样负责各地区的防火任务?如果可以，应当关闭哪个?图5-1提示：对每个防火站定义一个0-1变量=,令然后对每个防火区域列一个约束条件。于是，可建立如下数学模型：由条件②,④,⑨可判定,分析可知(1,0,1,1)为问题的一个可行解，此一==。假设可以减少一个消防站，即增加约束条件。通过单纯形法计算可知，只有(1,0,1,1)为可行解，所以可关闭消防站②。5.5在有互相排斥的约束条件的问题中，如果约束条件是(≤)型的，我们可用加以一=项(F是0-1变量，M是很大的常数)的方法统一在一个问题中。如果约束条件是(≥)型的，解：在互相排斥的约束条件问题中，如果约束件右端减去一，其中F是0-1变量，M是充分大的正数，且5.6解下列0-1规划问题。解：通过观察可知(0,0,1)T为可行解，相应的z=2,故增加约束条件进行枚举及选择，如表5-8所示。表5-8表5-10由表5-8可判定，最优解为解：通过观察可知(0,0,0,1)为可行解，相应的z=4,故增加约束条件，进行枚举及选择，如表5-9所示。由表5-9可判定最优解为5.7有4个工人，要指派他们分别完成4项工作，每个人做各项工作所消耗的时间如表5-10所示。问指派哪个人去完成哪项工作，可使表7-1因为m=3<n=4,指派不成功，转入下一步。第三步：做最少的直线覆盖所有的0元素，并进行再指派第6章无约束问题第7章约束极值问题7.1在某一试验中变更条件F四次，测得相应的结果Vi见表7-1,试为这一试验拟合一条直7.2有一线性方程组如下现欲用无约束极小化方法求解，试建立数学模型并说明计算原理。解：(1)建立数学模型：(2)以梯度法为例解无约束极值问题，计算原理如下：②或者对三求导，并令等于0,则可求得最佳步长三。以②为判断准则，重复迭代，直至满足精度为止。7.3试判定下述非线性规划是否为凸规划。 从而可知一为严格凸函数，==为凸函数，为凹函数，所以这不是一个凸规划分别计算,,海塞矩阵的行列式:从而可知f(X)为严格凸函数，g(X)为凹函数，8₂(X)为凸函数，所以这不是一个凸规划7.4试用斐波那契法求函数在区间[0,10]上的极小点，要求缩短后的区间长度不大于原区间长度的8%。用斐波那契法求解：(1)由=,可确定试点的个数一底，这里取一同。(3)由于,故取一(4)依次进行迭代，得最终区间为L,近似极小点为=,近似7.5试用0.618法重做习题7.4,并将计算结果与用斐波那契法所得计算结果进行比较。可确定试点的个数一F,计算得最终区间为比较，用0.618法求解，试点数n值大一些，但求值更接近于精确值。7.6试用最速下降法求解,选初始点一l,要求做三次迭代，并验证相邻两步的搜索方向正交。解：,用最速下降法迭代计算的过程如表7-2所示。表7-2迭代方向正交。7.7试用最速下降法求函数行计算，求出极大点，再以为初始点进为初始点进行两次迭代，最后比较从上述两个不同初始点出发的寻优过程。 (1)以x⁰=(0.0)²为初始点，取精度一间，则,所以一用为极小点，即一日为f(X)的极大点。(2)以x=(0,1)为初始点，取精度8=0.1,采用相同的方法进行两次迭代，有：两次的步长：;两次迭代的结果：比较：一般的，二元二次凸函数的等值线是椭圆，椭圆的圆心即为极小值，(1)中负梯度方向直指圆心，且初值点与圆心在同一水平直线上，所以收敛很快；(2)中的搜索路径呈直角锯齿状，所以收敛较慢。7.8试用牛顿法重解习题7.6。因为f(X)为二次函数，所以一自，7.9试用牛顿法求解,取初始点,用最佳步长进行迭代。然后采用固定步长一国，观察迭代情况，并加以分析说明。解：令,要求f(X)的极大点即求F(X)的极小点。仿照7.8的即极大点为由上可知，步长λ=1。故采用固定步长λ=1与采用最佳步长情形一致。。7.10试用共轭梯度法求二次函数的极小点，此处所以因此因此,即二为极小点。7.11令为一组A共轭向量(假定为列向量),A为对称正定矩阵，试证用左乘上式，并且由共轭关系可知：故得证。 7.12试用变尺度法解,取初始点,要求近 似极小点处梯度的模不大于0.5。解：取初始点可得,于是又因为,所以为近似极小点。7.13试以为初始点，使用(1)最速下降法(迭代4次);(2)牛顿法；(3)变尺度法。解：(1)用最速下降法：图7-1(2)牛顿法：所以极小点为。其寻优过程，如图7-2所示。图7-2(3)变尺度法：其寻优过程，如图7-3所示。图7-37.14试用步长加速法(模矢法)求下述函数的极小点，初始点,步长为。并绘图表示整个迭代过程。表7-31,此时应在点=附近搜索，缩小步长以求得符合精度要求的结果。所以，最优解为一其迭代过程如图7-4所示。图7-47.15分析非线性规划在以下各点的可行下降方向(使用教材中式(7-6)o并绘图表示各点可行下降方向的范围。解：将原非线性规划改写为：目标函数和约束条件的梯度为：(1),起作用的约束为8:(X),所以则有所以，存在可行下降方向，如图7-5所示。图7-5(2),起作用的约束为8(X)和8₂(X),所以令D=(x,y)²,则有该方程组无解，所以不存在可行下降方向，如图7-6所示。图7-6(3),起作用的约束为8₂(X),所以所以，存在可行下降方向，如图7-7所示。图7-77.16试写出下述二次规划的K-T条件：解：原二次规划可改写为：设为K-T点，且与点起作用约束的各梯度线性无关，假设8₁(X),g₂(X)都是起作用7.17试写出下述非线性规划问题的K-T条件并进行求解：解：(1)原非线性规划问题可改写成：目标函数和约束函数的梯度为：对第一、二个约束条件分别引入广义拉格朗日乘子=和-=,并令K-T点为，则有K-T为解该方程组，考虑以下几种情形：由于该非线性规划问题不是凸规划，且K-T条件只是确定某点为最优点的必要条件，而非充分条件，所以1或5不一定是全局极小点。(2)原非线性规划问题可改写成：目标函数和约束函数的梯度为：对第一、二个约束条件分别引入广义拉格朗日乘子/和/2,并令K-T点为X,则有K-T为解该方程组，考虑以下几种情形：由于该非线性规划问题是凸规划，所以—:是该问题的全局极小点。7.18试找出非线性规划问题的极大点，然后写出其K-T条件，这个极大点满足K-T条件吗?试加以说明。解：原非线性规划问题可改写成：(1)找极大点将第一、二个约束条件相加得：即一=。又由第三个约束条件知，庙，约束条件得，以极大点为X*=(1,2)T,由于点X*起约束作用的梯度为7g₁(X),▽g₂(X”),它们线性相关，故点X=(1,2)T不是正则点。把极大点X*=(1,2)代入K-T条件，可求得。所以当，时，极大点X⁴=(1,2)T满足K-T条件。7.19试解二次规划解：上述二次规划问题可改写为下列形式：显然，目标函数为严格凸函数，并且因为小于0,引入人工变量一并在前面取负号，得到如下的线性规划模型：7.20试用可行方向法求解取精度三而取搜索方向则w:(X)=(-1,-1)T,W₂(X)=(-1,X⁰不是近似极小点。又一令则构成下述线性规划问题：为便于用单纯形法求解，令从而得到其最优解为：7.21试用SUMT外点法求解并求出当罚因子等于1和10时的近似解。所以，当7.22试用SUMT外点法求解,得in)的解为日=,,为最优解。7.23试用SUMT内点法求解解：构造障碍函数则当一F时，又由约束条件一，所以最优解为7.24试用SUMT内点法求解解：原问题可改写为：第8章动态规划的基本方法8.1试分析《运筹学》教材第8章第1节之例2问题中：(1)阶段的划分；(2)状态变量和它的取值范围；(3)决策变量和它的允许决策集合；(4)状态转移方程；(5)指标函数与最优指标函数。解：(1)阶段的划分：共划分为五个阶段，阶段变量k=1,2,3,4,5。(2)状态变量为=,它表示第k年初完好的机器数量取值范围，即(3)决策变量为三，它表示第k年度中高负荷下分配生产的机器数；De(s)表示第k阶段从出发的允许决策集合，则(4)状态转移方程为开始到第5年结束的总产量的最大值，即8.2设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到图8-1解：设阶段变量,依次表示4个阶段选择路线的过程；状态变量表示第k阶段fe(sk)表示从初可能处的位置；决策变量=表示第k阶段初可能选择的路线；最优值函数第k阶段点5开始至终点E的最少运费，则有;图8-2点A到第k阶段状态的最短距离，则有