您好,欢迎访问三七文档
当前位置:首页 > 行业资料 > 交通运输 > 运筹学与系统分析---复习资料答案
1运筹学与系统分析复习资料一单选题1在产销平衡运输问题中,设产地为m个,销地为n个,那么解中非零变量的个数【C】A.等于(m+n-1)B.不能小于(m+n-1)C.不能大于(m+n-1)D.不确定2在单纯形表的终表中,若非基变量的检验数有0,那么最优解【B】A.不存在B.唯一C.无穷多D.无穷大3.在用对偶单纯形法解最大化线性规划问题时,每次迭代要求单纯形表中【D】A.b列元素不小于零B.检验数都大于零C.检验数都不小于零D.检验数都不大于零4在约束方程中引入人工变量的目的是【D】A.体现变量的多样性B.变不等式为等式C.使目标函数为最优D.形成一个单位矩阵5若运输问题已求得最优解,此时所求出的检验数一定是全部【A】A.大于或等于零B.大于零C.小于零D.小于或等于零6在线性规划模型中,没有非负约束的变量称为【C】A.多余变量B.松弛变量C.自由变量D.人工变量7线性规划问题的最优解对应其可行域的【B】A.内点B.顶点C.外点D.几何点8对偶问题的对偶是【D】A.基本问题B.解的问题C.其它问题D.原问题9原问题与对偶问题具有相同的最优【B】A.解B.目标值C.解结构D.解的分量个数10在对偶问题中,若原问题与对偶问题均具有可行解,则【A】A.两者均具有最优解,且它们最优解的目标函数值相等B.两者均具有最优解,原问题最优解的目标函数值小于对偶问题最优解的目标函数值C.若原问题有无界解,则对偶问题无最优解2D.若原问题有无穷多个最优解,则对偶问题只有唯一最优解11表上作业法中初始方案均为【A】A.可行解B.非可行解C.待改进解D.最优解12若原问题中xi为自由变量,那么对偶问题中的第i个约束一定为【A】A.等式约束B.“≤”型约束C.“≥”约束D.无法确定13线性规划一般模型中,自由变量可以代换为两个非负变量的【B】A.和B.差C.积D.商14建立运筹学模型的过程不包括的阶段是【D】A.观察环境B.数据分析C.模型设计D.模型实施15使用人工变量法求解极大化线性规划问题时,当所有的检验数0j,在基变量中仍含有非零的人工变量,表明该线性规划问题【D】A.有唯一的最优解B.有无穷多个最优解C.为无界解D.无可行解16线性规划模型不包括的要素有【D】A.目标函数B.约束条件C.决策变量D.状态变量二填空题1线性规划问题的可行解是指满足约束条件和非负条件解。2若线形规划问题存在可行解,则该问题的可行域是凸集。3线性规划问题有可行解,则必有。5动态规划模型中,各阶段开始时的客观条件叫做状态。6当线性规划问题的系数矩阵中不存在现成的可行基时,一般可以加入人工变量构造可行解。7在大M法中,M表示人工变量一个绝对值很大的负系数。8线形规划问题的标准形式是:目标函授是求是确定的,约束条件全为线性等式,约束条件右侧常数项全为非负值。9线性规划的右端常数项其对偶问题的价值系数;线性规划的第i个约束条件其对偶问题决策变量。310在一个基本可行解中,取正数值的变量称为基变量;取零值的变量称为非基变量。11在线性规划模型中,没有非负约束的变量称为自由变量。12为求解需要量大于供应量的运输问题,可虚设一个供应点,该点的供应量等于需求量与供应量的差值。13线性规划问题可分为目标函数求极大值和极小值两类。14若线性规划为最大化问题,则对偶问题为极小化问题。15用运筹学解决问题的核心是建立数学模型,并对数学模型求解。16在将线性规划问题的一般形式化为标准形式时,引入的松弛变量在目标函数中的系数为零。17动态规划模型的构成要素有阶段、状态、决策和策略、状态转移和目标函数。三计算题1用大M法求解线性规划问题MinZ=-3X1+X2+X3s.tX1-2X2+X3≤11-4X1+X2+2X3≥3-2X1+X3=1X1,X2,X3≥0解:(1)将线性规划化为标准型。引入松弛变量4x,剩余变量5x,并令'ZZ;得:123123412351312345maxZ'=3x211423..21,,,,0xxxxxxxxxxstxxxxxxx约束方程系数矩阵A为:1-2110-4120-1-20100AA中只有一个单位列向量,故对第二、第三个约束条件引入人工变量6x,7x对模4型整理得:12367123412356137maxZ'=3x211423..210;1,2,3.....7jxxMxMxxxxxxxxxxstxxxxj改造后的系数矩阵A为:1-211000-4120-110-2010001A以467,,xxx为初始基变量进行单纯形法求解如下表。BCBXjcjxb3-1-100MMj1x2x3x4x5x6x7x04x111-21100011/1M6x3-4120-1103/2M7x1-20100011'Z4M3-6M-1+M-1+3M0-M0004x103-20100-1--M6x10100-11-21-13x1-2010001--'Z1+M1-1+M00-M01-3M04x123001-22-54-12x10100-11-2--5-13x1-2010001--'Z21000-M1-M-1-M31x41001/3-2/32/3-5/3-12x10100-11-2-13x90012/3-4/34/3-7/3'Z-2000-1/3-1/31/3-M2/3-M故,当1234,1,9xxx时,取得最优解。'2ZZ。2用单纯形法求解下列线性规划,解出最优解。MaxZ=3X1+4X2s.tX1+X2≤42X1+3X2≤6X1,X2≥0解:将线性规划化成标准型,引入松弛变量3x和4x:121231241234maxZ=3x44..236,,,0xxxxstxxxxxxx系数矩阵A为:11102301A,以3x和4x为初始基变量计算,单纯性计算表如下表。BCBXjcjxb3400j1x2x3x4x03x41110404x6230126Z0340003x21/301-1/3642x22/3101/33Z81/300-4/303x10-1/21-1/231x313/201/2Z90-1/20-3/2故,当123,0xx时,线性规划取得最大值9Z。3已知:运输问题的单价表。(1)用最小元素法找出初始可行解;(2)用位势法求出初始可行解相应的检验数;(3)求最优方案。单位:万元单价甲乙丙供给量A35810B74620C32910需求量5255解:(1)用最小元素法求初始可行解。设供应地A、B、C到甲、乙、丙三地的运价分别为ijc;运量分别为ijx。由于总的供给量为40,需求量为35,为供给量大于需求量的不平衡运输问题,增设一个假想需求地丁,需求量为5,A、B、C到给地的运价均为零。运价表变更为:单价甲乙丙丁(存储)供给量A358010B7460207C329010需求量5255540先不考虑丁地的需求,由表格可知32x的运价最小,C全部供应乙地,乙地需求还剩15;依次找出最小运价,首先满足其需求,重复此过程,可以得出初始可行解,如下表所示:运量甲乙丙丁A53050850B071545600C031020900(2)用位势法求检验数。设120,0uu;可知11142223323;0;4;6;2;uvuvuvuvuv代入,可解:12312340;0;2;3;4;6.0uuuvvvv;计算如下表:甲乙丙丁甲乙丙丁A301uA34600B462uB34600C23uC124-2-21v2v3v4v3460成本表ijuv根据()ijijijcuv计算如下表:ijcijuv甲乙丙丁甲乙丙丁A3580A3460B7460B3460C3290C124-2ij8甲乙丙丁A0120B4000C2052故,所有检验数均为非负值,得到最优解:112223325,15;5;10xxxx最小运价min5315410256125Z4将下述线性规划模型化为标准型MinZ=X1-X2+3X3s.tX1+X2+X3=105X1-7X2+3X3≤-8X1+X2≥2X3≤18X1≥0,X2≤0,X3无符号限制解,引入松弛变量4x,6x,剩余变量5x,两个非负变量3'x和3''x,且333'''xxx。令'ZZ,则线性规划的标准型为:12331233123341253361233456maxZ'=x3''''''10573'3''8..2'''18,,','',,,0xxxxxxxxxxxxstxxxxxxxxxxxxx5有四项工作要甲,乙,丙,丁四个人去完成,每一项工作只许一个人去完成,四项工作要四个不同的人去完成;问:应指派每个人完成哪一项工作,使得总的消耗时间为最短?用匈牙利法求解。消耗时间工作1工作2工作3工作4甲15182124乙21232218丙26171619丁232119179解:(1)以各员工完成各项工作的时间构造矩阵一,如下:矩阵一15182124212322182617161923211917(2)对矩阵一进行行约减,即每一行数据减去本行数据中的最小数,得矩阵二。矩阵二03693540101036420(3)检查矩阵二,若矩阵二各行各列均有“0”,则跳过此步,否则进行列约减,即每一列数据减去本列数据中的最小数,得矩阵三。矩阵三02693440100036320(4)画“盖0”线。即画最少的线将矩阵三中的0全部覆盖住02693440100036320(5).数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步,若“盖0”线得数目小于矩阵得维数则进行数据转换,本题属于后一种情况,应进行转换,操作步骤如下:A、找出未被“盖0”线覆盖的数中的最小值,例中=2。B、将未被“盖0”线覆盖住的数减去。C、将“盖0”线交叉点的数加上。可得矩阵四026111220100054100(6)重复步骤(4)、(5)直到“盖0”线的数目等于矩阵的维数,计算过程如10下。026111220100054100得到矩阵五026111220100054100(7)求最优解。对n维矩阵,找出不同行、不同列的n个“0”,每个“0”的位置代表一对配置关系,具体步骤如下:A、先找只含有一个“0”的行(或列),将该行(或列)中的“0”打“√”。B、将带“√”的“0”所在列(或行)中的“0”打“”。C、重复(1)步和(2)步至结束。若所有行列均含有多个“0”,则从“0”的数目最少的行或列中任选一个“0”打“√”。0√26111220√100√05410√0故,工作分配关系结果如下表。即甲完成工作1,乙完成工作4,丙完成工作2,丁完成工作3。消耗时间工作1工作2工作3工作4甲15乙18丙17丁196写出下列线形规划问题的对偶问题MaxZ=X1+2X2+3X311s.t3X1+3X2+X3≥122X1+X2+4X3≤182X1+2X2+3X3=20X1,X2,X3≥0解:将线性规划化成一般对称形式。123123123123123123max2333122418..2232022320,,0Zxxxxxxxxxstxxxxxxxxx写出其对偶问题:12331233123312331233min=12y'1820'''3'22'''13'2'''2..'43'''3,,',''0Wyyyyyyyyyyystyyyyyyyy令11333','''yyyyy
本文标题:运筹学与系统分析---复习资料答案
链接地址:https://www.777doc.com/doc-1897272 .html