运筹学练习题.doc

运筹学练习题一、填空题1、线性规划模型有三种参数，其名称分别为_ 、 _ 和 。2、一个模型是m个约束，n个变量，则它的对偶模型为 个约束， 个变量。3、动态规划是解决 最优化问题的一种理论和方法。 4、在运输问题中，一个空格只存在_闭回路，计算闭回路的目的是要计算解中_。5、若线性规划问题最优解不唯一，则在最优单纯形表上的非基变量的检验数_。6、为求解销量大于产量的运输问题，可虚设一个产地Am+1，它的销量等于_ 。二、单项选择题1使用人工变量法求解极大化线性规划问题时，当所有的检验数，在基变量中仍含有非零的人工变量，表明该线性规划问题（ ）。A有唯一的最优解；B有无穷多个最优解；C为无界解；D无可行解。2一个极大化的线性规划问题用单纯形法求解，若对所有的检验数，但对某个非基变量，有，则该线性规划问题（ ）。A有唯一的最优解；B有无穷多个最优解；C为无界解；D无可行解。3在用对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（ ）。Ab列元素不小于零； B检验数都大于零；C检验数都不小于零； D检验数都不大于零。4在运输问题中，每次迭代时，如果有某基变量的解值等于零，则该运输问题（ ）。A无最优解；B有无穷多个最优解；C有唯一最优解；D出现退化解。5若一个产销平衡运输问题的数据表的各元素都乘以常数（k.0）得到一个新的数据表，这一新数据表对应着一个新的产销平衡运输问题，则（ ）。A新问题与原问题有相同的最优解；B新问题最优目标值大于原问题最优目标函数值；C新问题最优解等于原问题最优解加上； D新问题最优解小于原问题最优解。6如果要使目标规划实际实现值达到或超过目标值，则相应的偏差变量应满足（ ）。A； B； C； D7在对偶问题中，若原问题与对偶问题均有可行解，则（ ）。A两者均具有最优解，且它们最优解的目标函数值相等；B两者均具有最优解，原问题最优解的目标函数值小于对偶问题最优解的目标函数值；C若原问题有无界解，则对偶问题无最优解；D若原问题有无穷多个最优解，则对偶问题只有唯一最优解；8在产销平衡运输问题中，设产地为m个，销地为n个，那么解中基变量的个数（ ）。A不能大于(m+n-1)；B不能小于(m+n-1)；C等于(m+n-1)；D等于（m+n）。9求解纯整数规划模型常用的方法有（ ）。A 单纯形法和表上作业法 B 表上作业法C 表上作业法和割平面法D 分枝定界法10在目标规划中，求解的基本原则是首先满足高级别的目标，但当高级别目标不能满足时（ ）。A其后的所有低级别目标一定不能被满足；B其后的所有低级别目标一定能被满足；C其后的某些低级别目标一定不能被满足；D其后的某些低级别目标有可能被满足。三、多项选择题1、下列叙述中正确的有（ ）A线性规划问题的每一个基本可行解都对应着可行域的一个顶点，反之亦然；B 整数规划最优解的目标函数值一般优于其相应的线性规划问题最优解的目标函数值；C 正偏差变量取正值，负偏差变量取负值；D动态规划中的某些问题可用标号法求解；2、求解整数线性规划常用的方法有（ ）A 单纯形法 B 分枝定界法 C 割平面法 D 表上作业法3、关于对偶理论，下列叙述错误的有（ ）（注：原问题为最大化的产品生产问题，对偶问题是最小化的出售资源问题）A 任何线性规划问题存在并具有惟一的对偶问题;B 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解；对偶问题无可行解时，其原问题可能具有无界解或无可行解;C 有n个变量、m个约束的标准型的线性规划问题，其可行域的顶点恰好为Cnm个;D 已知为线性规划对偶问题的最优解，若0，说明在最优生产计划中第i种资源已完全耗尽;4、第i种资源的影子价格的定义是（ ）（注：原问题为最大化的产品生产问题，对偶问题是最小化的出售资源问题）A 相应的对偶最优解 B -CBB-1C B-1b D 该种资源在最优决策下的边际价值5、关于运输问题，下列说法正确的有（ ）A 运输问题模型是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有惟一最优解、有无穷多最优解、无界解、无可行解；B 在产销平衡的运输问题中，只要给出一组含（m+n-1)个非零的xij ，且不构成闭回路，就可以作为一个初始基可行解；C 按最小元素法给出的初始可行解，从每一空格出发可以找出而且仅能找出惟一的闭回路（不考虑闭回路的方向）；D有转运的产销平衡运输问题如无特殊规定，每个纯转运站的收发货物量相等，均为总产量或总销量.四、填表题已知某线性规划规划问题用单纯形法迭代时，得到的初始单纯形表及最终单纯形表如下，请将表中空白处的数字填上。cj2-11000CBXBbx1x2x3x4x5x6000x4x5x66010203111-1112-1100010001-Z2-11000cj2-11000CBXBbx1x2x3x4x5x60（ ）（ ）x4x1x2（ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）100-11/2-1/2-21/21/2-Z（ ）（ ）（ ）（ ）（ ）（ ）五、用大M法求解线性规划问题六、某建筑公司从三个水泥厂A1、A2、A3将同一型号同一品质的水泥运往四个工地B1、B2、B3、B4，各水泥厂的产量、各工地的需求量和各水泥厂运往各工地每袋水泥的运费如下表所示。问应如何调运，可使得总运费最小？（建立产销平衡数据表、最小元素法给出初始调运方案、闭回路法调优） 工地水泥厂B1B2B3B4产量（t）A13113107A219284A3741059需求量（t）365620(产销平衡)七、已知某运输问题的供需关系及单位运价表如下表所示：销地产地甲乙丙丁产量A1A2A3372255724635506025销量60402015试用表上作业法找出最优调运方案； 八、友谊农场有3万亩农田，欲种植玉米、大豆和小麦三种农作物。各种作物每亩需施化肥分别为0.12吨、0.20吨、0.15吨。预计秋后玉米每亩可收获500千克，售价为0.24元/千克，大豆每亩可收获200千克，售价为1.20元/千克，小麦每亩可收获300千克，售价为0.70元/千克。农场年初规划时考虑如下几个方面：p1:年终收益不低于350万元；p2:总产量不低于1.25万吨；p3:小麦产量以0.5万吨为宜；p4:大豆产量不少于0.2万吨；p5:玉米产量不超过0.6万吨；p6:农场现能提供5000吨化肥；若不够，可在市场高价购买，但希望高价采购量越少越好。请就该农场生产计划建立目标规划数学模型。九、写出以下原始问题的对偶问题（化为最简形式）。maxz=2x1-x2+4x3+x4s.t.x1+3x2-x3+5x412-2x1-2x2+3x3-2x4=253x1+x2-2x3+x418x10x20x40十、某厂生产I、II、III三种产品，需消耗劳工时和原料两种资源，其有关数据如表：（1）用单纯形法确定总利润最大的生产计划（建立线性规划模型并用单纯形法求解）。（2）分别求出工时和原料的影子价格，若原料不够，可到市场上购买，市场价格为0.8元/单位，问是否要购进，最多可购进多少？总利润增加多少？ （3）劳动力可减少多少而不改变原最优生产计划？ IIIIII资源限量工时原料63345545（单位）30（单位）单位利润315十一、请给出下图所示的网络从A点到F点的最短路线及计算其长度（用标号法直接在下图中相应位置标出并叙述其最优策略及最优目标函数值）。43735191257962424468515454AB1B2B3C1C2C3D1D2D3E1E2F十二、某房地产公司生产A、B两种物业构件，有关数据如下：AB资源限制量电力23100（百度）煤42120（百吨）利润64万元（1）求最优生产计划；（2）若电力可多供应20（百度），利润能否达240（万元）；（3）若（2）达不到，改为以下目标规划，目标1：保证利润不低于240万元；目标2：耗电量、耗煤量应尽量少地超过120，请建立起模型并求满意解。 10参考答案 一、填空题1、价值系数、技术/工艺系数、右端常数 2、n、m 3、多阶段决策过程4、一个、空格的检验数 5、至少有一个为0 6、二、单项选择题1D 2B 3D 4D 5A 6C 7A 8C 9D 10D三、多项选择题1、AD 2、BC 3、ABD 4、AD 5、CD四、填表题cj2-11000CBXBbx1x2x3x4x5x60（ 2 ）（ -1 ）x4x1x2（ 10 ）（ 15 ）（ 5 ）（ 0 ）（ 1 ）（ 0 ）（ 0 ）（ 0 ）（ 1 ）（ 1 ）（ 1/2）（-3/2 ）100-11/2-1/2-21/21/2-Z（ 0 ）（ 0 ）（-3/2）（ 0 ）（-3/2）（-1/2）五、解：用大M法，先化为等效的标准模型：max z/ =5x12x24x3s.t.增加人工变量x6、x7，得到：max z/ =5x12x24x3Mx6Mx7s.t大M法单纯形表求解过程如下：Cjb52400MMiCBXBx1x2x3x4x5x6x7Mx64（3）1210104/3Mx71063501015/3Cj-Zj9M54M27M4MM005x14/311/32/31/301/30Mx72011（2）1211Cj-Zj0M1/3M2/32M5/3M3M+5/305x15/311/25/601/601/610/30x410（1/2）1/211/211/22Cj-Zj01/21/605/6MM+5/65x12/3101/311/311/32x220112121Cj-Zj001/311/3M+1M+1/3x*=（，2，0，0，0）T最优目标函数值min z =max z/ =（）=六、解：最小元素法给出初始调运方案如下表： 工地水泥厂B1B2B3B4产量（t）A1311341037A21392184A374610539需求量（t）3656产销平衡（2）求检验数 工地水泥厂B1B2B3B4产量（t）A131112341037A21391218-14A3710461012539需求量（t）3656产销平衡因为240，所以此方案不最优（3）用闭回路法调优得最优表 工地水泥厂B1B2B3B4产量（t）A130112351027A2139221814A379461012539需求量（t）3656产销平衡因为11=0，所以本运输问题有另一最优调运方案如下： 工地水泥厂B1B2B3B4产量（t）A130112351027A2139221814A379461012539需求量（t）3656产销平衡七、解：最有调运方案如下：销地产地甲乙丙丁产 量A1A2A3352515252015506025销 量60402015八、解：设种植玉米x1亩，大豆x2亩，小麦x3亩，则该问题的数学模型为：九、解：对偶问题为minf=12y1+25y2+18y3s.t.y1-2y2+3y3 23y1-2y2+y3-1-y1+3y2-2y3= 45y1-2y2+y3 1y10y2:unry30十、解：（1）该问题的线性规划模型为设：x1,x2,x3分别为产品A、B、C的产量。用单纯形法迭代的最优表如下：cj31500CBXBbx1x2x3x4x5i05x4x315633/5-1-4/50110-11/5-Z-300-300-1j因而最优生产计划为A、B产量均为0，C产量为6，可使利润最大，最大利润为30。（2）工时和原料的影子价格分别是0和1，这说明在企业最优安排中，工时资源没有用完（实际用了30个单位），而原料资源已耗尽，若原料市场价格为0.8元/单位影子价格1元/单位，因此可应适量购进原料扩大生产。设购进的原料数为b2，为保持最优基不变，必有B-1b0，即解得 -30b215因而最多可购进原料15单位，总利润增加CBB-1b-30=15单位，净利润增加15-0.815=3单位。（3）设劳动力减少b1，即右边常数列变化为b=(45-b1，30)T,为使最优计划不变，则B-1b0。即所以b115。即劳动力可减少15单位，原最优计划不变注：本题还有另一最优解x*=（5，0，3）T,Z*=30十一、解：此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下：17343201257962424468515454AB1B2B3C1C2C3D1D2D3E1E2F59147711859121414以上每个k部子过程指标函数值为分，全对得最佳策略为：AB2C1D1E2F此时的最短距离为5+4+1+2+2=14十二、解：（1）设x1、x2分别为A、B两种构件生产的数量LP模型如下：MaxZ=6X1+4X22X1+3X21004X1+2X2120X1，X20解为：X1=20，X2=20， maxZ=200(万元)（2）用灵敏度分析，可得：X1=15，X2=30 Z*=210，Z*=210240要回答第三问。（3）建立目标规划模型minZ=P1(d1-)+P2(d2+d3+)6X1+4X2 +d1- -d1+=2402X1 +3X2+d2- -d2+=120 4X1 +2X2 +d3- -d3+=120Xi , di- , di+ 0解