中南大学现代远程教育平台-运筹学课程作业答案

中南大学现代远程教育平台—运筹学课程作业答案中南大学现代远程教育平台—运筹学课程作业答案中南大学现代远程教育平台—运筹学课程作业答案中南大学现代远程教育平台—运筹学课程作业答案编制仅供参考审核批准生效日期地址：电话：传真:邮编:《运筹学》作业答案作业一一、是非题：1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。（√）2.线性规划问题的每一个基解对应可行解域的一个顶点。（╳）3.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。（√）4.用单纯形法求解Max型的线性规划问题时，检验数Rj＞0对应的变量都可以被选作入基变量。（√）5.（√）6.线性规划问题的可行解如为最优解，则该可行解一定是基可行解。（╳）7.若线性规划问题具有可行解，且可行解域有界，则该线性规划问题最多具有有限个数的最优解。（╳）8.对一个有n个变量，m个约束的标准型线性规划问题，其可行域的顶点数恰好为个。（╳）9.一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。（√）10.求Max型的单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解。（√）二、线性规划建模题：1.某公司一营业部每天需从A、B两仓库提货用于销售，需提取的商品有：甲商品不少于240件，乙商品不少于80台，丙商品不少于120吨。已知：从A仓库每部汽车每天能运回营业部甲商品4件，乙商品2台，丙商品6吨，运费200元/每部；从B仓库每部汽车每天能运回营业部甲商品7件，乙商品2台，丙商品2吨，运费160元/每部。问：为满足销售量需要，营业部每天应发往A、B两仓库各多少部汽车，并使总运费最少？

解：设营业部每天应发往A、B两仓库各x1，x2部汽车,则有：2.现有一家公司准备制定一个广告宣传计划来宣传开发的新产品，以使尽可能多的未来顾客特别是女顾客得知。现可利用的广告渠道有电视、广播和报纸，根据市场调查整理得到下面的数据：项目电视广播报纸一般时间黄金时间每个广告单元的费用(元)每个广告单元所接触的顾客数(万人)每个广告单元所接触的女顾客数(万人)40004030700090403000502015002010该企业计划用于此项广告宣传的经费预算是80万元，此外要求：①至少有200万人次妇女接触广告宣传；②电视广告费用不得超过50万元,③电视广告至少占用三个单元一般时间和两个单元黄金时间,④广播和报纸广告单元均不少于5个单元而不超过10个单元。解：设电视一般时间、黄金时间、广播和报纸各投放广告单元数为x1，x2，x3，x4，有：三、计算题：对于线性规划模型1.用图解法求出其所有基本解，并指出其中的基本可行解和最优解。2.三个方程中分别添加松驰变量x3,x4,x5后把模型化成标准型，用单纯形法寻求最优解。并与1题中图解法中对照，单纯形表中的基可行解分别对应哪些顶点。3.若直接取最优基，请用单纯形表的理论公式进行计算对应基B的单纯形表，并与第2题最优单纯形表的计算结果比较是否一致。（附单纯形表的理论公式：非基变量xj的系数列向量由Pj变成基变量的值为，目标函数的值为，检验数公式）。解：（1）图解如下：所有基本可行解：O（0,0），Q1（6,0），Q2（4,2），Q3（2,3），Q4（0,3）共五个基可行解。从上图知：最优解为点Q2（4,2），目标函数值为Z＝20。（2）模型标准化为：单纯形法表迭代过程如下表示：cj34000CBXBx1x2x3x4x5bθ000x3x4x5[1]110012010010016836出基8-－Z340000300x1x4x5111000[1]-11001001626233－Z01-300－18340x1x2x5102-1001-110001-11421－Z00-2-10-20从上表知：表一中的基可行解（0,0,6,8,3）对应坐标原点O，表二中的基可行解为（6,0,0,2,3）对应图中的Q1点，表三中的基可行解为（4,2,0,0,1）对应图中的Q2点，得到最优解。（3）若取基，基变量为x1,x2,x5，刚好是最优表中的对应基变量，可算出（从第三个单纯形表也可找到B－1），由单纯形表计算公式计算非基变量的系数列向量、检验数及基解等。，，。，与迭代的第三个单纯形表计算结果一致。四、写出下列线性规划问题的对偶问题。解：设三个方程的对偶变量分别为y1,y2,y3，有：五、有一个Max型的线性规划问题具有四个非负变量，三个“≤”型的条件，其最优表格如下表，请写出其对偶问题的最优解及目标函数值。XBx1x2x3x4x5x6x7bx4x6x1012/312/30-1/302-10010111/301/301/314/3410/3-Z0-2-4/30-4/30-1/3-34/3解：该问题的松驰变量为x5,x6,x7，由对偶规划的性质知三个对偶变量的值分别为x5,x6,x7检验数的负值，目标函数值与原问题相等。故，W＝34/3。六、求下列运输问题的解：销地产地B1B2B3供应量A16424A28575需求量333用表上作业法求解此问题的最优解。（要求用行列差值法给初始解，用位势法求检验数。）解：（1）这是一个产销平衡的运输问题，用行列差值法给初始解：销地产地B1B2B3行差值供应量A16（1）4（╳）2（3）2,24A28（2）5（3）7（╳）2,35列差值2,21,15需求量333（2）用位势法求检验数：对基变量有：,并令u1=0，求出行列位势，如下表。销地产地B1B2B3行位势vi供应量A16（1）4（╳）2（3）u1=04A28（2）5（3）7（╳）u2=25列位势vjv1=6v2=3v3=2需求量333各非基变量的检验数分别为：R12=4－(3+0)=1，R23=7－(3+2)=2，即基变量的检验数都大于0，当前方案为最优调运方案。作业二一、用隐枚举法求解下面0－1型整数规划问题：解：问题为求极大型，需所有的变量前的价值系数变为负号，故令，模型变为：，用目标函数值探索法求最大值：x1’x2’x3是否满足约束方程Z(1)(2)(3)（4）01000100╳√√√√32从表中可以看出，当时具最大目标函数值，即，Zmax＝2。二、某服装厂有五项工作需要分给五个技工去完成，组成分派问题，各技工完成各项工作的能力评分如下表所示。请问应如何分派，才能使总得分最大？

工作评分人员B1平车B2考克B3卷边B4绷缝B5打眼A100A200A3000A400A50解：（1）效率矩阵为：，问题是求极大，转化为求极小问题，设，构造以bij为系数的矩阵，（2）对bij矩阵进行系数变换，使每行每列出现0元素，（3）进行试分配：，（4）作最少的直线覆盖所有的0元素：（5）在没有被覆盖的部分中找出最小数，则第四、五行减去这个最小数，同时第五列加上这个最小数，其他元素不变，目的是增加0元素的个数。（6）试分配：，此时，所有的0都已打括号或划掉，且打括号的0元素（独立的0元素）个数刚好为5个，得到了问题的最优解，问题的解矩阵为：，即A1做平车，A2做卷边，A3做绷缝，A4做打眼，A5做考克，总得分为。三、某厂从国外引进一台设备，由工厂A至G港口有多条通路可供选择，其路线及费用如图1所示。现要确定一条从A到G的使总运费最小的路线，请将该问题描述成一个动态规划问题，然后求其最优解。070C1070C1B1D11D1130602030602040G40GC240AC240A1030D21301030D21300050C3B50C3B2第四阶段第三阶段第第四阶段第三阶段第二阶段第一阶段图1图1解：把问题分为4个阶段，如图1示。设Sk为每一阶段的起点，xk为第k阶段的决策变量，状态转移方程为：SK+1＝xk(Sk)。k=1,2,3,4。阶段指标函数为Sk到xk(Sk)的距离值，最优指标函数fk(Sk)为第k阶段状态为Sk时，从Sk到终点G的最短距离值。指标函数递推方程：，k=3,2,1边界方程为：。下面列表计算如下：x4S4x4GD13030GD24040Gk=4时：k=3时：x3S3x4D1D2C10+30－30D1C240＋3030＋4070D1或D2C3－0＋4040D2k=2时：x2S2x4C1C2C3B170+3060+70－100C1B210＋7050＋4080C2k=1时：x1S1x4B1B2A20+10030＋80110B2最优路线有两条：A→B2→C2→D1→G或A→B2→C2→D2→G，最短距离值为110。四、某公司打算在三个不同的地区设置4个销售点，根据市场预测部门估计，在不同的地区设置不同数量的销售店，每月可得到的利润如表1所示。试问在各个地区应如何设置销售点，才能使每月获得的总利润最大其值是多少表1销售店利润地区01234101625303220121721223010141617解：设给每一个地区设置一个销售点为一个阶段，共三个阶段。xk为给第k个地区设置的销售点数；Sk为第k阶段还剩余的销售点数，S1＝4状态转移方程为：Sk+1=Sk－xkdk(xk)为在第k个地区设置xk个销售点增加利润最优指标函数fk(Sk)为第k阶段把Sk个销售点时分给第k、k+1,…3个销售点获取的最大收益。指标函数递推方程：，k=2,1边界方程为：。逆推计算如下：k=3时：S3=x3x3S3x3012340000110101214142316163417174k=2时：S3=S2－x2x3S3x201234000010＋1012+012120+1412+1017+022130+1612+1417+1021+027240+1712+1617+1421+1022+0312或3k=1时：S2=S1－x1x1S1x20123440＋3116＋2725＋2230＋1232＋0472最优决策方案为：第一个地区设置2个销售点，第二个地区设置1个销售点，第三个地区设置1个销售点，每月可获总利润为47。五、某厂生产一种产品，该产品在未来三个月中的需要量分别为3，4，3万件，若生产准备费为3万元/次，每件成本为1元，每件每月存储费为元，假定1月初和4月初存货为0，并每月产量不限。试求该厂未来三个月内的最优生产计划？要求用动态规划求解。

动态规划求解，建立如下动态规划数学模型。1月1月3月4月2月①阶段(月份)n：1234②状态变量Sn：每月初库存，有S1={0}，S2={0,1,2,3,4,5,6,7}，S3={0,1，2,3}，S4={0}。③决策变量Xn：每月的生产量据题意有决策变量的允许范围：3≤x1≤10,0≤x2≤7,0≤x3≤3。④状态转移方程：Sn+1=Sn+Xn－Dn⑤阶段指标函数(成本)：成本=生产费用＋存储费用rrn(Xn)=3＋1·Xn，Xn＞00，Xn＝0＋＋⑥递推方程：，下面利用表格进行计算，从最后一个阶段开始：n=3时：此时S3+X3－D3=0，即X3=3－S3X3S3r3(X3)f3(S3)X3*012306+0=66315+=224+=130+=0n=2时：此时S2+X2≥2=4，即X2≥4－S2；S3=S2+X2－D2，即S3=S2+X2－4X2S2r2(X2)+f3(S3)f2(S2)X20123456707+68+9+10+71+6+++62+6+++53+6+++44+6+++05+++06++07+70n=1时：X1≥3－S1；S2=S1+X1－D1，即S2=S1+X1－3X1S1r1(X1)+f2(S2)f1(S1)X1*0123456706+7+8+9+10+3由此可知：S1=0，此时X1*=3；S2=S1+X1*－3=0＋3－3=0，此时X2*=7；S3=S2+X2*－4=0＋7－4=3，此时X3*=0。最优策略为：X*={x1*，x2*，x3*}={3，7，0}Z*=f1*(S1)=即第一个月生产3万件，第二个月生产7万件，第三个月生产0万件，可使总成本最低为万元。作业三（图与网络分析、存贮论部分）判断题：1.图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意。（╳）2.在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（√）3.如图中某点vi有若干个相邻点，与其距离最远的相邻点为vj，则边[vi,vj]必不包含在最小支撑树内。（╳）4.在任一连通图G中，点数为N，则保证这N点相互连通且任意两点间仅有一条链相通的图一定含有N－1条边。（√）5.求网络最大流问题可归结为求解一个线性规划问题。（√）6.订购费为每订一次货所发生的费用，它同每次订货的数量无关。（√）7.在同一存贮模型中，可能既发生存贮费用，又发生短缺费用。（√）8.在允许缺货发生短缺的存贮模型中，订货批量的确定应使由于存贮量的减少带来的节约能抵消缺货时造成的损失。（√）9.当订货数量超过一定的值允许打折扣的情况下，打折扣条件下的订货批量要大于不打折扣时的订货批量。（√）10.在其他费用不变的情况下，随着单位存贮费用的增加，最优订货批量也相应增大。（╳）二、求图1中的最小树5v5v1v2v3v4v6v7v8v565456278333441图1解：用破圈法求得的最小部分树为：vv1v2v3v4v6v7v8v54233315最小部分树的权为：1＋3+3＋3+2＋4+5＝21。三、求图2中从点v1到其余各点的最短路：43v1v43v1v3v5v73251382736图2v4v288005252解：用T、P标号算法：1.给v1点标P标号，其他点标T标号，为＋∞。2.从v1点出发，修改v2、v3点的T标号，并把其中最小者改为P标号。T(v2)=3，T(v3)=2＝P（v3）。3.从刚刚获得P标号的点v3出发，可达v2,v4,v5,修改T标号，并把最小者改为P标号。4.依此类推，各点的P标号如图2所示。从v1到v7的最短路为：v1→v3→v5→v7，距离为8。四、求图3中网络的最大流、最大流的流量和最小割。vv2v5v7v1v3v6v458434428898图36v2v2v5v7v1v3v6v45,58,84,43,34,44,42,