1、1运筹学练习题一、填空题1、线性规划模型有三种参数，其名称分别为_ 、 _ 和。2、一个模型是 m 个约束，n 个变量，则它的对偶模型为 个约束， 个变量。3、动态规划是解决 最优化问题的一种理论和方法。 4、在运输问题中，一个空格只存在_闭回路，计算闭回路的目的是要计算解中_。5、若线性规划问题最优解不唯一，则在最优单纯形表上的非基变量的检验数_。6、为求解销量大于产量的运输问题，可虚设一个产地 Am+1，它的销量等于_ 。二、单项选择题1使用人工变量法求解极大化线性规划问题时，当所有的检验数 ，在基变量0j中仍含有非零的人工变量，表明该线性规划问题（ ） 。A有唯一的最优解；B有无穷多个最
2、优解；C为无界解；D无可行解。2一个极大化的线性规划问题用单纯形法求解，若对所有的检验数 ，但对某j个非基变量 ，有 ，则该线性规划问题（ ） 。jx0jA有唯一的最优解；B有无穷多个最优解；C为无界解；D无可行解。3在用对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（ ） 。Ab 列元素不小于零； B检验数都大于零；C检验数都不小于零； D检验数都不大于零。4在运输问题中，每次迭代时，如果有某基变量的解值等于零，则该运输问题（ ） 。A无最优解；B有无穷多个最优解；C有唯一最优解；D出现退化解。5若一个产销平衡运输问题的数据表的各元素都乘以常数 （k.0）得到一个新的数k据表，这
3、一新数据表对应着一个新的产销平衡运输问题，则（ ） 。A新问题与原问题有相同的最优解；B新问题最优目标值大于原问题最优目标函数值；C新问题最优解等于原问题最优解加上 ； kD新问题最优解小于原问题最优解。6如果要使目标规划实际实现值达到或超过目标值，则相应的偏差变量应满足（ ） 。A ； B ； C ； D0d0d0d.0,d7在对偶问题中，若原问题与对偶问题均有可行解，则（ ） 。A两者均具有最优解，且它们最优解的目标函数值相等；B两者均具有最优解，原问题最优解的目标函数值小于对偶问题最优解的目标函数值；C若原问题有无界解，则对偶问题无最优解；D若原问题有无穷多个最优解，则对偶问题只有唯一最
4、优解；8在产销平衡运输问题中，设产地为 m 个，销地为 n 个，那么解中基变量的个数（ ） 。A不能大于(m+n-1)；B不能小于( m+n-1)；C 等于( m+n-1)；D等于（m +n） 。9求解纯整数规划模型常用的方法有（ ） 。2A 单纯形法和表上作业法 B 表上作业法C 表上作业法和割平面法 D 分枝定界法10在目标规划中，求解的基本原则是首先满足高级别的目标，但当高级别目标不能满足时（ ） 。A其后的所有低级别目标一定不能被满足；B其后的所有低级别目标一定能被满足；C其后的某些低级别目标一定不能被满足；D其后的某些低级别目标有可能被满足。三、多项选择题1、下列叙述中正确的有（ ）
5、A 线性规划问题的每一个基本可行解都对应着可行域的一个顶点，反之亦然；B 整数规划最优解的目标函数值一般优于其相应的线性规划问题最优解的目标函数值；C 正偏差变量取正值，负偏差变量取负值；D 动态规划中的某些问题可用标号法求解；2、求解整数线性规划常用的方法有（ ）A 单纯形法 B 分枝定界法 C 割平面法 D 表上作业法3、关于对偶理论，下列叙述错误的有（ ）（注：原问题为最大化的产品生产问题，对偶问题是最小化的出售资源问题）A 任何线性规划问题存在并具有惟一的对偶问题 ;B 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解；对偶问题无可行解时，其原问题可能具有无界解或无可行解;C
6、 有 n 个变量、m 个约束的标准型的线性规划问题，其可行域的顶点恰好为 Cnm 个;D 已知 为线性规划对偶问题的最优解，若 0，说明在最优生产计划中第 i 种资*iy *iy源已完全耗尽;4、第 i 种资源的影子价格的定义是（ ）（注：原问题为最大化的产品生产问题，对偶问题是最小化的出售资源问题）A 相应的对偶最优解 B -CBB-1 C B-1b D 该种资源在最优决策下的边际价值5、关于运输问题，下列说法正确的有（ ）A 运输问题模型是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有惟一最优解、有无穷多最优解、无界解、无可行解；B 在产销平衡的运输问题中，只要给出一组
7、含（ m+n-1)个非零的x ij ，且不构成闭回路，就可以作为一个初始基可行解；C 按最小元素法给出的初始可行解，从每一空格出发可以找出而且仅能找出惟一的闭回路（不考虑闭回路的方向） ；D 有转运的产销平衡运输问题如无特殊规定，每个纯转运站的收发货物量相等，均为总产量或总销量.四、填表题已知某线性规划规划问题用单纯形法迭代时，得到的初始单纯形表及最终单纯形表如下，请将表中空白处的数字填上。cj 2 -1 1 0 0 0CB XB b x1 x2 x3 x4 x5 x6000x4x5x66010203111-1112-1100010001-Z 2 -1 1 0 0 0cj 2 -1 1 0 0
8、 0CB XB b x1 x2 x3 x4 x5 x630（ ）（ ）x4x1x2（ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）100-11/2-1/2-21/21/2-Z （ ） （ ） （ ） （ ） （ ） （ ）五、用大 M 法求解线性规划问题无 正 负 约 束321321,0,1685maxxtsxz六、某建筑公司从三个水泥厂 A1、A 2、A 3将同一型号同一品质的水泥运往四个工地B1、B 2、B 3、B 4，各水泥厂的产量、各工地的需求量和各水泥厂运往各工地每袋水泥的运费如下表所示。问应如何调运，可使得总运费最小？（建立产销平衡数据表、最小元素法给出初始
9、调运方案、闭回路法调优）工地水泥厂 B1 B2 B3 B4 产量（t）A1 3 11 3 10 7A2 1 9 2 8 4A3 7 4 10 5 9需求量（t） 3 6 5 6 20(产销平衡)七、已知某运输问题的供需关系及单位运价表如下表所示：销地产地 甲 乙 丙 丁 产量A1A2A3372255724635506025销量 60 40 20 15试用表上作业法找出最优调运方案； 八、友谊农场有 3 万亩农田，欲种植玉米、大豆和小麦三种农作物。各种作物每亩需施化肥分别为 0.12 吨、0.20 吨、0.15 吨。预计秋后玉米每亩可收获 500 千克，售价为0.24 元/千克，大豆每亩可收获
10、200 千克，售价为 1.20 元/千克，小麦每亩可收获 300 千克，售价为 0.70 元/千克。农场年初规划时考虑如下几个方面：p1:年终收益不低于 350 万元； p2:总产量不低于 1.25 万吨； p3:小麦产量以 0.5 万吨为宜；p4:大豆产量不少于 0.2 万吨； p5:玉米产量不超过 0.6 万吨； p6:农场现能提供 5000 吨化肥；若不够，可在市场高价购买，但希望高价采购量越少越好。请就该农场生产计划建立目标规划数学模型。九、写出以下原始问题的对偶问题（化为最简形式） 。max z= 2x1 -x2 +4x3 +x4s.t. x1 +3x2 -x3 +5x4 12-2x
11、1 -2x2 +3x3 -2x4 =2543x1 +x2 -2x3 +x4 18x10 x20 x40十、某厂生产 I、II 、III 三种产品，需消耗劳工时和原料两种资源，其有关数据如表：（1）用单纯形法确定总利润最大的生产计划（建立线性规划模型并用单纯形法求解） 。（2）分别求出工时和原料的影子价格，若原料不够，可到市场上购买，市场价格为0.8 元/单位，问是否要购进，最多可购进多少？总利润增加多少？ （3）劳动力可减少多少而不改变原最优生产计划？ I II III 资源限量工时原料63345545（单位）30（单位）单位利润 3 1 5十一、请给出下图所示的网络从 A 点到 F 点的最短
12、路线及计算其长度（用标号法直接在下图中相应位置标出并叙述其最优策略及最优目标函数值） 。十二、某房地产公司生产 A、 B 两种物业构件，有关数据如下：A B 资源限制量电力 2 3 100（百度）煤 4 2 120（百吨）利润 6 4 万元（1）求最优生产计划；（2）若电力可多供应 20（百度） ，利润能否达 240（万元） ；（3）若（2）达不到，改为以下目标规划，目标 1：保证利润不低于 240 万元；目标2：耗电量、耗煤量应尽量少地超过 120，请建立起模型并求满意解。 43735191257962424468515454AB1B2B3C1C2C3D1D2D3E1E2F5参考答案 一、填
13、空题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四、填表题cj 2 -1 1 0 0 0CB XB b x1 x2 x3 x4 x5 x60（ 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）
14、 （ 0 ） （-3/2） （-1/2）五、解：用大 M 法，先化为等效的标准模型：max z/ =5x 1 2x24x 3s.t. 5,.,0106433214jyxxj增加人工变量 x6、x 7，得到：max z/ =5x 1 2x24x 3M x6Mx 7s.t ,.,01054375321 64jxj大 M 法单纯形表求解过程如下：Cj 5 2 4 0 0 M MCB XB b x1 x2 x3 x4 x5 x6 x7 iM x6 4 （3） 1 2 1 0 1 0 4/3M x7 10 6 3 5 0 1 0 1 5/3Cj-Zj 9M5 4M2 7M4 M M 0 05 x1 4/
15、3 1 1/3 2/3 1/3 0 1/3 0 M x7 2 0 1 1 （2） 1 2 1 1Cj-Zj 0 M1/3 M2/3 2M5/3 M 3M+5/3 065 x1 5/3 1 1/2 5/6 0 1/6 0 1/6 10/30 x4 1 0 （1/2） 1/2 1 1/2 1 1/2 2Cj-Zj 0 1/2 1/6 0 5/6 M M+5/65 x1 2/3 1 0 1/3 1 1/3 1 1/32 x2 2 0 1 1 2 1 2 1Cj-Zj 30 0 1/3 1 1/3 M+1 M+1/3x *=（ ，2 ，0，0，0） T最优目标函数值 min z =max z / =（
16、 ）=32六、解：最小元素法给出初始调运方案如下表：工地水泥厂 B1 B2 B3 B4 产量（t）A1 3 11 34 103 7A2 13 9 21 8 4A3 7 46 10 53 9需求量（t） 3 6 5 6 产销平衡（2）求检验数工地水泥厂 B1 B2 B3 B4 产量（t）A1 31 112 34 103 7A2 13 91 21 8-1 4A3 710 46 1012 53 9需求量（t） 3 6 5 6 产销平衡因为 240，所以此方案不最优（3）用闭回路法调优得最优表工地水泥厂 B1 B2 B3 B4 产量（t）A1 30 112 35 102 7A2 13 92 21 81
17、 4A3 79 46 1012 53 9需求量（t） 3 6 5 6 产销平衡7因为 11=0，所以本运输问题有另一最优调运方案如下：工地水泥厂 B1 B2 B3 B4 产量（t）A1 30 112 35 102 7A2 13 92 21 81 4A3 79 46 1012 53 9需求量（t） 3 6 5 6 产销平衡七、解：最有调运方案如下：销地产地 甲 乙 丙 丁 产 量A1A2A335251525 20 15506025销 量 60 40 20 15八、解：设种植玉米 x1 亩，大豆 x2 亩，小麦 x3 亩，则该问题的数学模型为： ， ， 6100515.20.1.4407 1025
18、701523min3 63454433 42314 654321 iddxxdxdxxts dpppdpz iiii九、解：对偶问题为minf=12y1+25y2+18y3s.t.y1-2y2+3y323y1-2y2+y3-1-y1+3y2-2y3=45y1-2y2+y31y10y2:unry30十、解：（1）该问题的线性规划模型为设：x 1,x2,x3 分别为产品 A、B 、C 的产量。8xtsZ0,35436ma2121用单纯形法迭代的最优表如下：cj 3 1 5 0 0CB XB b x1 x2 x3 x4 x5 i05x4x315633/5-1-4/50110-11/5-Z -30 0
19、 -3 0 0 -1 j因而最优生产计划为 A、B 产量均为 0，C 产量为 6，可使利润最大，最大利润为30。（2）工时和原料的影子价格分别是 0 和 1，这说明在企业最优安排中，工时资源没有用完（实际用了 30 个单位） ，而原料资源已耗尽，若原料市场价格为 0.8 元/单位影子价格 1 元/单位，因此可应适量购进原料扩大生产。设购进的原料数为 b2，为保持最优基不变，必有 B-1b0，即0516304512bbB解得 -30b215因而最多可购进原料 15 单位，总利润增加 CBB-1b-30=15 单位，净利润增加 15-0.815=3 单位。（3）设劳动力减少 b1，即右边常数列变化
20、为 b=(45-b1，30) T,为使最优计划不变，则 B-1b0。即 b065304512所以 b115。即劳动力可减少 15 单位，原最优计划不变注：本题还有另一最优解 x*=（5，0，3） T,Z*=30十一、解：此为动态规划之“最短路问题” ，可用逆向追踪“图上标号法”解决如下：17343201257962424468515454AB1B2B3C1C2C3D1D2D3E1E2F59147711859121414以上每个 k 部子过程指标函数值为分，全对得最佳策略为：AB 2C 1D 1E 2F9此时的最短距离为 5+4+1+2+2=14十二、解：（1）设 x1、x 2 分别为 A、B
21、两种构件生产的数量LP 模型如下：MaxZ=6X1+4X22X1+3X21004X1+2X2120X1，X 20解为：X 1=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解：1010X2X1DCBAd3- d1+d2-4X1+2X2 =1206X1+4X2 =2402X1+3X2 =120OE分析：满足 P1，部分满足 P2 的点有 A，B，C ，D(如果不考虑 A，B 产品均需生产 )由解方程可得：A(40，0) ，B(60 ，0)，C(24，24) ，D(0，60)比较与目标的偏差A 点：Z A=P1d1-+P2d2+P2d3+=0+0+P2d3+=(4X1+2X2+d3-120)P2=(440-120）P 2=40P2B 点：Z B=120P2 C 点：Z C=24P2 D 点：Z D=60P2 结论：取 C 点方案：A24，B2410利润：240。电力未超，煤超用 24(百吨)
