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

1《运筹学》作业答案作业一一、是非题：1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。（√）2.线性规划问题的每一个基解对应可行解域的一个顶点。（╳）3.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。（√）4.用单纯形法求解Max型的线性规划问题时，检验数Rj＞0对应的变量都可以被选作入基变量。（√）5.单纯形法计算中，如果不按最小比值规划选出基变量，则在下一个解中至少有一个基变量的值为负。（√）6.线性规划问题的可行解如为最优解，则该可行解一定是基可行解。（╳）7.若线性规划问题具有可行解，且可行解域有界，则该线性规划问题最多具有有限个数的最优解。（╳）8.对一个有n个变量，m个约束的标准型线性规划问题，其可行域的顶点数恰好为mnC个。（╳）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部汽车,则有：12121212min200160472402280621200(1,2)jWxxxxxxxxxj2.现有一家公司准备制定一个广告宣传计划来宣传开发的新产品，以使尽可能多的未来顾客特别是女顾客得知。现可利用的广告渠道有电视、广播和报纸，根据市场调查整理得到下面的数据：项目电视广播报纸一般时间黄金时间每个广告单元的费用(元)每个广告单元所接触的顾客数(万人)每个广告单元所接触的女顾客数(万人)40004030700090403000502015002010该企业计划用于此项广告宣传的经费预算是80万元，此外要求：①至少有200万人次妇女接触广告宣传；②电视广告费用不得超过50万元,③电视广告至少占用三个单元一般时间和两个单元黄金时间,④广播和报纸广告单元均不少于5个单元而不超过10个单元。2解：设电视一般时间、黄金时间、广播和报纸各投放广告单元数为x1，x2，x3，x4，有：123412341234121234max409050200.40.70.30.1580304020102000.40.750325105100(1,...4)Zxxxxxxxxxxxxxxxxxxxjj三、计算题：对于线性规划模型1212122jmax34628x3x0(j=1,2)zxxxxxx1.用图解法求出其所有基本解，并指出其中的基本可行解和最优解。2.三个方程中分别添加松驰变量x3,x4,x5后把模型化成标准型，用单纯形法寻求最优解。并与1题中图解法中对照，单纯形表中的基可行解分别对应哪些顶点。3.若直接取最优基125[,,]BPPP，请用单纯形表的理论公式进行计算对应基B的单纯形表，并与第2题最优单纯形表的计算结果比较是否一致。（附单纯形表的理论公式：非基变量xj的系数列向量由Pj变成-1jjpBp　　　，基变量的值为1BXBb，目标函数的值为10BBBZCXCBb，检验数公式jjjBRCCP）。解：（1）图解如下：3所有基本可行解：O（0,0），Q1（6,0），Q2（4,2），Q3（2,3），Q4（0,3）共五个基可行解。从上图知：最优解为点Q2（4,2），目标函数值为Z＝20。（2）模型标准化为：1212312425jmax34628(2)x+x=3(3)x0(j)zxxxxxxxx　(1)一切单纯形法表迭代过程如下表示：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）若取基125110B=P,P,P120011，基变量为x1,x2,x5，刚好是最优表中的对应基变量，可算出-12-10B-1101-11（从第三个单纯形表也可找到B－1），由单纯形表计算公式计算非基变量的系数列向量、检验数及基解等。32-1012-110011-1101P，42-1001-110111-1101P，41252-1064-110821-1131BxXxx。33320(3,4,0)121BRcCP，44410(3,4,0)111BRcCP与迭代的第三个单纯形表计算结果一致。四、写出下列线性规划问题的对偶问题。1231312323231MinZ=5x+4x+3x2x+7x88x+5x-4x154x+6x=30x,x0,x自由变量解：设三个方程的对偶变量分别为y1,y2,y3，有：1231223123123max8153028554474630,0,Wyyyyyyyyyyyyy为自由变量五、有一个Max型的线性规划问题具有四个非负变量，三个“≤”型的条件，其最优表格如下表，请写出其对偶问题的最优解及目标函数值。解：该问题的松驰变量为x5,x6,x7，由对偶规划的性质知三个对偶变量的值分别为x5,x6,x7检验数的负值，目标函数值与原问题相等。故12341Y=(y,y,y)=(,0,)33，W＝34/3。六、求下列运输问题的解：销地产地B1B2B3供应量A16424A28575需求量333XBx1x2x3x4x5x6x7bx4x6x1012/312/30-1/302-10010111/301/301/314/3410/3-Z0-2-4/30-4/30-1/3-34/35用表上作业法求解此问题的最优解。（要求用行列差值法给初始解，用位势法求检验数。）解：（1）这是一个产销平衡的运输问题，用行列差值法给初始解：销地产地B1B2B3行差值供应量A16（1）4（╳）2（3）2,24A28（2）5（3）7（╳）2,35列差值2,21,15需求量333（2）用位势法求检验数：对基变量有：()0ijijijRcuv,并令u1=0，求出行列位势，如下表。各非基变量的检验数分别为：R12=4－(3+0)=1，R23=7－(3+2)=2，即基变量的检验数都大于0，当前方案为最优调运方案。作业二一、用隐枚举法求解下面0－1型整数规划问题：10,,44225423..232132132132321321或xxxxxxxxxxxxxxtsxxxZMax解：问题为求极大型，需所有的变量前的价值系数变为负号，故令11221',1'xxxx，模型变为：231123231231231233('2')'3'2(1)4'1(2)..'2'1(3)'4'1(4)',',01MaxZxxxxxxxxstxxxxxxxxx或，销地产地B1B2B3行位势vi供应量A16（1）4（╳）2（3）u1=04A28（2）5（3）7（╳）u2=25列位势vjv1=6v2=3v3=2需求量3336用目标函数值探索法求最大值：jcx1’x2’x3是否满足约束方程Z(1)(2)(3)（4）01000100╳√√√√32从表中可以看出，当123'0,'1,0xxx时具最大目标函数值，即1231,0,0xxx，Zmax＝2。二、某服装厂有五项工作需要分给五个技工去完成，组成分派问题，各技工完成各项工作的能力评分如下表所示。请问应如何分派，才能使总得分最大？解：（1）效率矩阵为：1.30.8001.001.21.31.30[]1.0001.2001.0500.21.41.00.90.601.1ijc，问题是求极大，转化为求极小问题，设1.4ijijbc，构造以bij为系数的矩阵，0.10.61.41.40.41.40.20.10.11.4[]0.41.41.40.21.41.40.351.41.200.40.50.81.40.3ijb（2）对bij矩阵进行系数变换，使每行每列出现0元素，00.41.31.30.31.30001.3[']0.21.11.201.21.40.251.41.200.10.10.51.10ijb工作评分人员B1平车B2考克B3卷边B4绷缝B5打眼A11.30.8001.0A201.21.31.30A31.0001.20A401.0500.21.4A51.00.90.601.17（3）进行试分配：(0)0.41.31.30.31.3(0)1.3[']0.21.11.2(0)1.21.40.251.41.2(0)0.10.10.51.1ijb，（4）作最少的直线覆盖所有的0元素：(0)0.41.31.30.31.3(0)1.3[']0.21.11.2(0)1.21.40.251.41.2(0)0.10.10.51.1ijb　　　　√√　（5）在没有被覆盖的部分中找出最小数0.1，则第四、五行减去这个最小数0.1，同时第五列加上这个最小数，其他元素不变，目的是增加0元素的个数。00.41.31.30.41.30001.4[']0.21.11.201.31.30.151.31.10000.41.00ijb（6）试分配：(0)0.41.31.30.41.3(0)1.4['']0.21.11.2(0)1.31.30.151.31.1(0)(0)0.41.0ijb，此时，所有的0都已打括号或划掉，且打括号的0元素（独立的0元素）个数刚好为5个，得到了问题的最优解，问题的解矩阵为：1000000100000100000101000ijx，即A1做平车，A2做卷边，A3做绷缝，A4做打眼，A5做考克，总得分为6.1。8三、某厂从国外引进一台设备，由工厂A至G港口有多条通路可供选择，其路线及费用如图1所示。现要确定一条从A到G的使总运费最小的路线，请将该问题描述成一个动态规划问题，然后求其最优解。解：把问题分为4个阶段，如图1示。设Sk为每一阶段的起点，xk为第k阶段的决策变量，状态转移方程为：SK+1＝xk(Sk)。k=1,2,3,4。阶段指标函数(,)kkkdSx为Sk到xk(Sk)的距离值，最优指标函数fk(Sk)为第k阶段状态为Sk时，从Sk到终点G的最短距离值。指标函数递推方程：11()min{()(,)}kk