2022年运筹学期末复习题.docx

《2022年运筹学期末复习题.docx》由会员分享，可在线阅读，更多相关《2022年运筹学期末复习题.docx（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

2、 5,9,请写出其他解：9. 线性规划的解有唯独最优解、 无穷多最优解、 无界解 和无可行解四种；10. 在求运费最少的调度运输问题中, 假如某一非基变量的检验数为 4,就说明 如果在该空格中增加一个运量运费将增加 4 ；11. “ 假如线性规划的原问题存在可行解,就其对偶问题肯定存在可行解”,这句话对仍是错？错12. 假如某一整数规划：名师归纳总结 MaxZ=X 1+X2 试卷 A 共 4页第 1页第 1 页,共 14 页- - - - - - -精选学习资料 - - - - - - - - - X1+9/14X251/14 -2X1+X21/3 X1,X20 且均为整数所对应的线性规划放松

3、问题的最优解为X1=3/2,X2=10/3 ,MaxZ=6/29,我们现在要对 X1 进行分枝,应当分为 X1 1 和 X1 2 ；13. 在用逆向解法求动态规划时,f ks k 的含义是：从第 k 个阶段到第 n 个阶段的最优解；14. 假设某线性规划的可行解的集合为D,而其所对应的整数规划的可行解集合为B,那么 D和 B的关系为 D 包含 B 15. 已知下表是制订生产方案问题的一张LP 最优单纯形表极大化问题,约束条件均为“ ” 型不等式其中X3,X4,X5 为松驰变量；_某一XBbX1X2X3X4X5X43 0 0 -2 1 3 X14/3 1 0 -1/3 0 2/3 X21 0 1

4、 0 0 -1 Cj-Z j0 0 -5 0 -23 213问： 1写出 B-1=1/3.02/30012 对偶问题的最优解： Y 5,0,23,0,0T 16. 线性规划问题假如有无穷多最优解,就单纯形运算表的终表中必定有个非基变量的检验数为0_；17. 极大化的线性规划问题为无界解时,就对偶问题_ 无解 _；18. 假设整数规划的松驰问题的最优解不符合整数要求,假设 Xi =bi 不符合整数要求,INTbi是不超过 bi 的最大整数,就构造两个约束条件： Xi INTbi 1 和Xi INTbi ,分别将其并入上述松驰问题中,形成两个分支,即两个后继问题；19. 知下表是制订生产方案问题的

5、一张LP最优单纯形表极大化问题,约束条件均为“ ” 型不等式其中X4,X5,X6 为松驰变量；X6第 2 页,共 14 页XBbX1X2X3X4X5X12 1 1 0 2 0 1 X32/3 0 0 1 1 0 4 X51 0 -2 0 1 1 6 Cj-Zj0 0 0 -4 0 -9 名师归纳总结 试卷 A 共 4页第 2页- - - - - - -精选学习资料 - - - - - - - - - T问： 1 对偶问题的最优解： Y 4,0,9,0,0,02写出 B-1= 2 0 11 0 41 1 620. 线性规划问题 MaxZ=CX；AX=b,X0A 为 kxl 的矩阵,且 lk的基的

6、最多个数为 _,基的可行解的最多个数为 _.21.指派问题的最优解的性质 _ _. 22. 线 性 规 划 问 题 的 所 有 可 行 解 构 成 的 集 合 是 _,它 们 有 有 限 个_,线性规划问题的每个基可行解对应可行域的 _,假设线性规划问题有最优解,必在_得到；23.影子价格的经济含义 _.在完全市场经济的条件下,当某种资源的市场价格低于影子价格时,企业应 _该资源,而当某种资源的市场价格高于影子价格时,就企业应 _该资源,可见影子价格对市场有 _作用；24. 运输问题的产销平稳表中有 m 个产地 n 个销地,其决策变量的个数有 _个,其数值格有 _个二、不定项挑选题 每题 2

7、分,共 6 分 1线性规划的标准型有特点； A、右端项非零； B、目标求最大； C、有等式或不等式约束； D、变量均非负；2一个线性规划问题 P与它的对偶问题 D有关系；A、P无可行解就 D肯定无可行解；B、P、D均有可行解就都有最优解；名师归纳总结 C、P的约束均为等式,就 D的全部变量均无非负限制；第 3 页,共 14 页 D、假设 D是 P的对偶问题,就 P是 D的对偶问题；试卷 A 共 4页第 3页- - - - - - -精选学习资料 - - - - - - - - - 3关于动态规划问题的以下命题中是错误的； A、动态规划阶段的次序与求解过程无关；B、状态是由决策确定的； C、用逆

8、序法求解动态规划问题的重要基础之一是最优性原理；D、列表法是求解某些离散变量动态规划问题的有效方法；4. 最早运用运筹学理论的是A 二次世界大战期间,英国军事部门将运筹学运用到军事战略部署 B 美国最早将运筹学运用到农业和人口规划问题上C 二次世界大战期间,英国政府将运筹学运用到政府制定方案 D 50 岁月,运筹学运用到讨论人口,能源,粮食,第三世界经济进展等问题上5. 以下哪些不是运筹学的讨论范畴系统设计A 质量掌握 B 动态规划 C 排队论 D 6. 对于线性规划问题,以下说法正确的选项是A线性规划问题可能没有可行解B 在图解法上,线性规划问题的可行解区域都是“ 凸” 区域C 线性规划问题

9、如有最优解,就最优解可在可行解区域顶点上到达D 上述说法都正确7. 下面哪些不是线性规划问题的标准形式所具备的A 全部的变量必需是非负的B 全部的约束条件变量的非负约束除外必需是等式C 添加新变量时,可以不考虑变量的正负性D 求目标函数的最小值8. 在求解运输问题的过程中运用到以下哪些方法A 西北角法 B 位势法 C 闭回路法 D 以上都是三、判定题1假设某种资源的影子价格等于k,在其他条件不变的情形下,当该种资源增加5第 4 页,共 14 页试卷 A 共 4页第 4页名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 个单位时,相应的目标函数值将增大 5

10、k 个单位；2假如运输问题单位运价表的某一行或某一列元素分别加上一个常数 k,最优调运方案将不会发生变化；3运输问题是一种特别的线性规划模型,因而求解结果也可能显现以下四种情形之一：有唯独最优解,有无穷多最优解,无界解,无可行解；4用割平面法求解纯整数规划问题时,要求包括放松变量在内的全部变量必需取整数值；iv 有假设干个相邻点,与其距离最远的相邻点为5如图中某点jv ,就边 , j 必不包含在最小支撑树内；6. 用两阶段法求解线性规划时,假如第一阶段的最终表中基变量显现人工变量,就该问题肯定无解；【 】7. 运输问题肯定存在有限的最优解；【 】；【】8. 假如某种资源的影子价格等于零,说明该

11、种资源肯定已经用完9. 单纯形法只适合求解线性规划,对偶单纯形法只适合求解对偶规划【】10. 分枝定界法求解最大化问题中,假如某个分支的目标值少于已经得到整数解的目标值,就这一分支将被减去而不再往下求解；【 】11. 运输问题表上作业法的最优判别标准是全部的检验数应当小于等于 0；【 】12. 分枝定界法和割平面法一样适用于线性规划的求解；【】13. 假如原规划无可行解,就其对偶规划也必将无可行解【】14. 假如原问题最优解的某个重量非零,就其对偶规划对应的约束条件肯定是等式【 】4 , 而 该 资 源 的 市 场 价 格 为【 】3 ； 就 应 买 进 该 资 源 投 入 生 产16. 最优

12、表中假如某个非基变量检验数为零,说明该问题有多重解【 】【 】第 5 页,共 14 页17. 对偶单纯形法应用的前提是对偶问题可行,原规划不行行试卷 A 共 4页第 5页名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 18. 线性规划问题的解只有唯独最优解、无解和无界解几种情形【】n-1 条边的图肯定是树【 】20. 线性规划原问题和对偶问题都有可行解,就该线性规划问题肯定有唯独最优解【 】21. 运输问题表上作业法的最优判别标准是全部的检验数应当大于等于 0；【 】22. 用两阶段法求解线性规划时,假如该线性规划问题存在最优解,就第一阶段最终表中的基

13、变量中肯定不会显现人工变量；】【 】“ 定界” 的目的是加快解的搜寻速度；【24. 用闭回路法运算的检验数假如等于3,说明沿该闭回路调整一个单位运量可以节省 3 个单位成本；【】四、表中给出的是某极大化问题的单纯型表,试依据下面的问题,确定表中的值或取值范畴；（1） 运算 a2的值；（2） 运算目标函数值；（3） 已知 初始,求 d 的值；（4） 该线性规划问题具有无界解,就a1, C1的取值范畴是多少？（5） 表中解为无穷多最优解之一,就表中 C1 等于多少？（6） 写出对偶规划的解和其次种资源的影子价格；表 1名师归纳总结 CB XB 4 2 1 3 0 0 0 第 6 页,共 14 页x

14、1 x2x3x4x5X62 X 11 -50 0 2 a23 X31 0 -7 1 0 1 0 0 X 4d 0 a101 0 4 试卷 A 共 4页第 6页- - - - - - -精选学习资料 - - - - - - - - - j 0 C1 0 0-4 -2 五、考虑以下线性规划：maxz23 x 15x2x34 x 1x2x 314x 1,0x2x 34xjj2,1 3,其最优单纯形表为：CBXBbx1x2x34xx50 4x6 2 0 -1 1 -2 5 2x4 1 1 1 0 1 -Z -20 -2 0 -4 0 -5 1、写出此线性规划的最优解、最优值；2、求线性规划的对偶问题的

15、最优解；3、试求 c 在什么范畴内,此线性规划的最优解不变；4、假设 1b 14 变为 9,最优解及最优值是什么？例：设线性规划max z 10 x 1 6 x 2 4 x 3x 1 x 2 x 3 100,10 x 1 4 x 2 5 x 3 600,2 x 1 2 x 2 6 x 3 300,x i 0, i 1,2,3.求： 1.最优解 ; 名师归纳总结 c c 2,c 的范畴 ,使最优解不变 ; 取c 350,求最优解 ; 第 7 页,共 14 页6试卷 A 共 4页第 7页- - - - - - -精选学习资料 - - - - - - - - - b b b 的范畴 ,使最优基不变

16、, 取b 1100,求最优解 ; 名师归纳总结 x 7,P 71,4,3T,c 78求最优解 ; 第 8 页,共 14 页xx 1x 2x 3x 4x 5x 6c1064000x 4111100100x 51045010600x 62260013001064000x 4031110405210x 1121010605210x 606501118055021010600x 20155102006363x 11012101006363x 6004201100008102022003333即 ,原问题的最优解为X100 200 ,3 3,0T,z2200.33x 为非基变量 ,故当c 338时,即c

17、 320时, 最优解不变 ; 33x x为基变量 ,由公式 ,当4c 15, 2c 24,最优解不变 , 即试卷 A 共 4页第 8页- - - - - - -精选学习资料 - - - - - - - - - 6c 115,4c 210时,最优解不变 . 现对c 35020, 3最优解转变 ,此时38135, 3原最优表为633xx 1x 2x 3x 4x 5x 6200625000c10315510x206363x 11012101006363x 600420110005102022000x233330102515275126246x 1100711175126246x 3001101252

18、42325000525即相应的最优解为23123175 275 ,6 6,25T,z2325.X3510200363,B1210 ,b100363201100试卷 A 共 4页第 9页名师归纳总结 - - - - - - -第 9 页,共 14 页精选学习资料 - - - - - - - - - 得40b 150, 200b 2400, 100b 3,60b 1150,400b 21000,b 3200,最优基不变 . 700,当b 110050,最优解转变 ,此时510200bb200363210100b600 ,b1 B b600363300300201100此时最优表为名师归纳总结 即最

19、优解为Xxx 1x 2x 3x 4x 5x 6700第 10 页,共 14 页c1064000x20155106363x 11012101006363x 6004201100810203200003333x20125 601515066x 1101 2011063x40021015020028 3025900330,150,0T,z900.第 10页试卷 A 共 4页- - - - - - -精选学习资料 - - - - - - - - - 7c B1P 7c 710 2 ,3 3,0186820,故最优解转变 . 43P 71 B P 75x 11201x 41相应的最优表为3621040

20、,36131x 5x 6x 720x 3xxc10640008200x 201551016363x 110121001006363x 600420111000081020222003333x 701551012006363x 110121001006363x 60019111101006363六、下述线性规划问题02132010026003333：试卷 A 共 4页第 11页名师归纳总结 - - - - - - -第 11 页,共 14 页精选学习资料 - - - - - - - - - max z 10 x 1 24 x 2 20 x 3 20 x 4 25 x 5x 1 x 2 2 x 3

21、 3 x 4 5 x 5 192 x 1 4 x 2 3 x 3 2 x 4 x 5 57x j 0 , j ,1 2 , , 5以 y 1, y 2 为对偶变量写出其对偶问题；七、某公司下属的 2 个分厂 A1、A2 生产质量相同的工艺品,要运输到 B1、B2、B3,3个销售点,分厂产量、销售点销量、单位物品的运费数据如下表：A1B1B2B3产量23 11 20 25 A218 16 17 25 销量20 10 20 用伏格尔法给出近似最优解；七、有甲、乙、丙、丁四个人,要分别指派他们完成 人做各项工作所消耗的时间如下表所示：A、B、C、D 不同的工作,每甲A B C D 7 9 10 12

22、 乙13 12 15 17 丙15 16 14 15 丁11 12 15 16 问：应当如何指派,才能使总的消耗时间为最少？八、某公司生产三种产品,各产品的重量和利润关系如下：产品重量 t 4 5 6 利润元8 11 13 现将三种产品运往市场出售,运输才能为总重量不超过10t ,如何支配运输使总利名师归纳总结 试卷 A 共 4页第 12页第 12 页,共 14 页- - - - - - -精选学习资料 - - - - - - - - - 润最大；试建立此问题的动态规划模型只建模,不求解；九、 某旅行者要从 A 地动身到终点 F,他事先得到的路线图如下：A 3 5 B1 5 7 9 C1 5

23、1 D1 4 E1 1 F2 4 8 6 4 B2 3 C2 4 D2 9 E2 2 5 6 B3 1 4 4 7 5 C3 2 D3 各点之间的距离如上图所示数值,旅行者沿着箭头方向行走总能走到 F 地,试找出 AF 间的最短路线及距离；解：此为动态规划之“ 最短路问题”决如下：,可用逆向追踪“ 图上标号法” 解14 3 5 14 9 1 4 4 1 F5 5 5 2 9 4 E1 1 8 6 A B2 3 C2 4 7 9 2 5 试卷 A 6 共 4页 11 第 13页名师归纳总结 E2 第 13 页,共 14 页- - - - - - -精选学习资料 - - - - - - - - - D2 4 B3 1 7 4 4 7 5 2 C3 2 D3 12 8 7 最正确策略为： AB 2C1D1E2F 此时的最短距离为5+4+1+2+2=14 第 14页试卷 A 共 4页名师归纳总结 - - - - - - -第 14 页,共 14 页