运筹学期末复习题.pdf

《运筹学期末复习题.pdf》由会员分享，可在线阅读，更多相关《运筹学期末复习题.pdf（14页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、运筹学期末考试试卷运筹学期末考试试卷(A)(A)学院学院班级班级学号学号题号得分一二三四五六七八九总分一、填空题一、填空题以下是关于目标函数求最大值的单纯行表的一些结论，请根据所表述的意思判断解的情况：1.所有的检验数非正，这时的解是。2. 有 一 个 正 检 验 数 所 对 应 的 列 系 数 均 非 正 ， 这 时 线 性 规 划 的解。3.非基变量检验数中有一个为零时，线性规划的解。4.在两阶段法中，如果第一阶段的最优表中的基变量中有人工变量，则该线性规划。6.基变量取值为负时的解为。7.最优表中的非基变量检验数的相反数就是。8.已知一个线性规划两个最优解是：3，2，和5，9，请写出其他

2、解：9.线性规划的解有唯一最优解、 无穷多最优解、 无界解和无可行解四种。10.在求运费最少的调度运输问题中， 如果某一非基变量的检验数为 4， 则说明如果在该空格中增加一个运量运费将增加 4。11.“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解” ，这句话对还是错？错12.如果某一整数规划：MaxZ=X1+X2试卷 A共4页第1页X1+9/14X251/14-2X1+X21/3X1,X20 且均为整数所对应的线性规划松弛问题的最优解为 X1=3/2，X2=10/3，MaxZ=6/29，我们现在要对 X1进行分枝，应该分为 X11和 X12。13.在用逆向解法求动态规划时，fk(

3、sk)的含义是：从第 k 个阶段到第 n 个阶段的最优解。14. 假设某线性规划的可行解的集合为 D，而其所对应的整数规划的可行解集合为B，那么 D 和 B 的关系为 D 包含 B15. 已知下表是制订生产计划问题的一张 LP 最优单纯形表极大化问题，约束条件均为“”型不等式其中 X3,X4,X5 为松驰变量。XBbX1X2X3X4X5X4300-213X14/310-1/302/3X210100-1Cj-Zj00-50-233 21-1问：1写出 B =1/3.02/3001(2)对偶问题的最优解： Y5，0，23，0，0T16. 线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有

4、_某一个非基变量的检验数为 0_；17. 极大化的线性规划问题为无界解时，则对偶问题_无解_；18. 假设整数规划的松驰问题的最优解不符合整数要求，假设 Xi=bi不符合整数要求， INT bi 是不超过 bi的最大整数， 则构造两个约束条件： XiINT bi 1和XiINTbi，分别将其并入上述松驰问题中，形成两个分支，即两个后继问题。19. 知下表是制订生产计划问题的一张 LP 最优单纯形表极大化问题，约束条件均为“”型不等式其中 X4,X5,X6 为松驰变量。XBbX1X2X3X4X5X6X12110201X32/3001104X510-20116Cj-Zj000-40-9试卷 A共4

5、页第2页问：(1)对偶问题的最优解： Y(4,0,9,0,0,0)T2写出 B-1=20110411620. 线性规划问题 MaxZ=CX；AX=b，X0A 为 kxl 的矩阵，且 lk的基的最多个数为_，基的可行解的最多个数为_.21.指派问题的最优解的性质_.22. 线 性 规 划 问 题 的 所 有 可 行 解 构 成 的 集 合 是 _, 它 们 有 有 限 个_,线性规划问题的每个基可行解对应可行域的_,假设线性规划问题有最优解，必在_得到。23.影子价格的经济含义_.在完全市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应_该资源，而当某种资源的市场价格高于影子价格时，则

6、企业应_该资源，可见影子价格对市场有_作用。24. 运输问题的产销平衡表中有 m 个产地 n 个销地，其决策变量的个数有_个，其数值格有_个二、不定项选择题(每题 2 分，共 6 分)1线性规划的标准型有特点 。 A、右端项非零； B、目标求最大； C、有等式或不等式约束； D、变量均非负。2一个线性规划问题P与它的对偶问题D有关系 。A、 P无可行解则D一定无可行解；B、 P 、 D均有可行解则都有最优解； C、 P的约束均为等式，则D的所有变量均无非负限制； D、假设D是P的对偶问题，则P是D的对偶问题。试卷 A共4页第3页3关于动态规划问题的以下命题中是错误的。 A、动态规划阶段的顺序与

7、求解过程无关；B、状态是由决策确定的； C、用逆序法求解动态规划问题的重要基础之一是最优性原理；D、列表法是求解某些离散变量动态规划问题的有效方法。4.最早运用运筹学理论的是A二次世界大战期间，英国军事部门将运筹学运用到军事战略部署 B美国最早将运筹学运用到农业和人口规划问题上C二次世界大战期间，英国政府将运筹学运用到政府制定计划 D50 年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上5.以下哪些不是运筹学的研究范围A质量控制 B动态规划 C排队论 D系统设计6.对于线性规划问题，以下说法正确的选项是A 线性规划问题可能没有可行解B在图解法上，线性规划问题的可行解区域都是“凸

8、”区域C线性规划问题如有最优解，则最优解可在可行解区域顶点上到达D上述说法都正确7.下面哪些不是线性规划问题的标准形式所具备的A所有的变量必须是非负的B所有的约束条件变量的非负约束除外必须是等式C添加新变量时，可以不考虑变量的正负性D求目标函数的最小值8.在求解运输问题的过程中运用到以下哪些方法A西北角法 B位势法 C闭回路法 D以上都是三、判断题1假设某种资源的影子价格等于 k，在其他条件不变的情况下，当该种资源增加 5试卷 A共4页第4页个单位时， 相应的目标函数值将增大 5k 个单位。2如果运输问题单位运价表的某一行或某一列元素分别加上一个常数k，最优调运方案将不会发生变化。3运输问题是

9、一种特殊的线性规划模型，因而求解结果也可能出现以下四种情况之一： 有唯一最优解， 有无穷多最优解， 无界解， 无可行解。4用割平面法求解纯整数规划问题时，要求包括松弛变量在内的全部变量必须取整数值。5如图中某点vi有假设干个相邻点，与其距离最远的相邻点为vj，则边i, j必不包6.用两阶段法求解线性规划时，如果第一阶段的最终表中基变量出现人工变量，则该问题一定无解。【 】7.运输问题一定存在有限的最优解；【 】含在最小支撑树内。8. 如果某种资源的影子价格等于零，说明该种资源一定已经用完。【 】9. 单纯形法只适合求解线性规划，对偶单纯形法只适合求解对偶规划【 】10.分枝定界法求解最大化问题

10、中，如果某个分支的目标值少于已经得到整数解的目标值，则这一分支将被减去而不再往下求解。【 】11. 运输问题表上作业法的最优判别标准是所有的检验数应该小于等于 0。【 】12.分枝定界法和割平面法一样适用于线性规划的求解 。【 】13.如果原规划无可行解，则其对偶规划也必将无可行解【 】14.如果原问题最优解的某个分量非零，则其对偶规划对应的约束条件一定是等式【 】4 ， 而 该 资 源 的 市 场 价 格 为3 。 则 应 买 进 该 资 源 投 入 生 产【 】16.最优表中如果某个非基变量检验数为零， 说明该问题有多重解【 】17.对偶单纯形法应用的前提是对偶问题可行， 原规划不可行【

11、】试卷 A共4页第5页18.线性规划问题的解只有唯一最优解、无解和无界解几种情况【 】n-1 条边的图一定是树【 】20.线性规划原问题和对偶问题都有可行解，则该线性规划问题一定有唯一最优解【 】21.运输问题表上作业法的最优判别标准是所有的检验数应该大于等于 0。 【 】22.用两阶段法求解线性规划时，如果该线性规划问题存在最优解，则第一阶段最终表中的基变量中一定不会出现人工变量。【 】“定界”的目的是加快解的搜索速度。【】24. 用闭回路法计算的检验数如果等于 3，说明沿该闭回路调整一个单位运量可以节约 3 个单位成本。【】四、表中给出的是某极大化问题的单纯型表，试根据下面的问题，确定表中

12、四、表中给出的是某极大化问题的单纯型表，试根据下面的问题，确定表中的值或取值范围。的值或取值范围。（1） 计算 a2的值。（2） 计算目标函数值。（3） 已知初始，求 d 的值。（4） 该线性规划问题具有无界解，则 a1, C1的取值范围是多少？（5） 表中解为无穷多最优解之一，则表中 C1等于多少？（6） 写出对偶规划的解和第二种资源的影子价格。表表 1 1CB2302XBX1X3X41x2-5-7a13x30100 x40010 x52100X6a204x110041d试卷 A共4页第6页j五、考虑以下线性规划：0C100-4-2maxz 3x15x2 x34x1 2x2 x314x x

13、x 4123x 0, j 1,2,3j其最优单纯形表为：CBXBb64-20 x1x2x3x4x505x4x221-2010-11-4100-21-5-Z1、写出此线性规划的最优解、最优值；2、求线性规划的对偶问题的最优解；3、试求c2在什么范围内，此线性规划的最优解不变；4、假设b114变为 9，最优解及最优值是什么？例：设线性规划maxz 10 x1 6x2 4x3x1 x2 x3100,10 x1 4x25x3 600,2x 2x 6x 300,231xi 0,i 1,2,3.求：1.最优解;c1,c2,c3的范围,使最优解不变; 取c350,求最优解;6试卷 A共4页第7页b1,b2,

14、b3的范围,使最优基不变, 取b1100,求最优解;x7,P71,4,3,c78求最优解;Txcx4x5x6x1101x26142635256521000 x3415641212515616483x401000100053232103Tx5001001101101511616023x60001000100010406018060020031003100220031006003001021001000100 x4x1x6x2x1x62200100 200X ,0,z .即,原问题的最优解为333820 x3为非基变量,故当c33时,即c3时, 最优解不变;33x1,x2为基变量,由公式,当4 c

15、1 5,2 c2 4,最优解不变, 即试卷 A共4页第8页6 c115,4 c210时,最优解不变.现对c350208135最优解改变,此时, ,原最优表为363333xcx2x1x6x11001000100 x2610001000 x325356164530010 x405323210325127121252Tx5016160231616023x600010524124145122003100310022003275617562523253x2x1x32325175 275,25,z .即相应的最优解为X 636 5321B 321 2000361100,0,b3601100试卷 A共4页第

16、9页得40 b1 50,200 b2 400,100 b3,60 b1150,400 b21000,b3 200,最优基不变.当b1100 50,最优解改变,此时 53200,12b b b 600b B b 33002此时最优表为1 700 0362001100,06003630010001x50 x600010561312537003100310032003150050 xcx2x1x6x11001000100Tx2610001000 x345616483256122283x4051362136201030010231616023x2x1x4即最优解为X9000,150,0,z 900.试

17、卷 A共4页第10页110 27 cBB1P7 c7,048 6 8 2 0,故最优解改变.3 3 3 5321P7 B P7 32xcx2x1x61061110,相应的最优表为04 61301 x3456164835616196133x4x500513621362010233513621361113620133x6000100010 x78x1x2106010001001000100210121000 x7x1x6200310031002200320031003100326003六、下述线性规划问题 ：试卷 A共4页第11页maxz 10 x1 24x2 20 x3 20 x4 25x5x1

18、 x2 2x33x45x5192x1 4x23x3 2x4 x5 57x 0, j 1,2,5j以y1, y2为对偶变量写出其对偶问题。七、某公司下属的 2 个分厂 A1、A2生产质量相同的工艺品，要运输到 B1、B2、B3，3个销售点，分厂产量、销售点销量、单位物品的运费数据如下表：A1A2销量B1231820B2111610B3201720产量2525用伏格尔法给出近似最优解。七、有甲、乙、丙、丁四个人，要分别指派他们完成 A、B、C、D 不同的工作，每人做各项工作所消耗的时间如下表所示：甲乙丙丁A7131511B9121612C10151415D12171516问：应该如何指派，才能使总

19、的消耗时间为最少？八、某公司生产三种产品，各产品的重量和利润关系如下：产品重量t利润元48511613现将三种产品运往市场出售，运输能力为总重量不超过 10t，如何安排运输使总利试卷 A共4页第12页润最大。试建立此问题的动态规划模型只建模，不求解 。九、九、某旅游者要从 A 地出发到终点 F，他事先得到的路线图如下：3B1545B23541B379C158C2461D142E161F2E2AD2944C3275D3各点之间的距离如上图所示数值， 旅游者沿着箭头方向行走总能走到 F 地，试找出 AF 间的最短路线及距离。解：此为动态规划之“最短路问题” ，可用逆向追踪“图上标号法”解决如下：B 14141539 95B235495 5158C2464 42641 1E111414A97 7E22F1111试卷 A共4页第13页D241B31212744C38 82D37 7752 2最正确策略为：AB2C1D1E2F此时的最短距离为 5+4+1+2+2=14试卷 A共4页第14页