运筹学习题精选

第 1 页 共 16 页 运运筹筹学学习习题题精精选选 第第一一章章 线线性性规规划划及及单单纯纯形形法法 选选择择 1 在线性规划模型中 没有非负约束的变量称 为 C A 多余变量 B 松弛变量 C 自由变量 D 人工变量 2 约束条件为的线性规划问题的可行解集0 XbAX 是 B A 补集 B 凸集 C 交集 D 凹集 3 线性规划问题若有最优解 则一定可以在可行域的 C 上 达到 A 内点 B 外点 C 顶点 D 几何点 4 线性规划标准型中bi i 1 2 m 必须 是 B A 正数 B 非负数 C 无约束 D 非零的 5 线性规划问题的基本可行解X 对应于可行域D 的 D A 外点 B 所有点 C 内点 D 极点 6 基本可行解中的非零变量的个数小于约束条件数时 该问 题可求得 B A 基本解 B 退化解 C 多重解 D 无解 7 满足线性规划问题全部约束条件的解称 为 C A 最优解 B 基本解 C 可行解 D 多重解 8 线性规划一般模型中 自由变量可以用两个非负变量的 B 代换 A 和 B 差 C 积 D 商 9 当满足最优检验 且检验数为零的变量的个数大于基变量 的个数时 可求得 A 第 2 页 共 16 页 A 多重解 B 无解 C 正则解 D 退化解 10 若线性规划问题有最优解 则必定存在一个 D 是最优解 A 无穷多解 B 基解 C 可行解 D 基可行解 填填空空 计计算算 1 1 某某厂厂生生产产甲甲 乙乙 丙丙三三种种产产品品 已已知知有有关关数数据据如如下下表表所所示示 求求使使该该厂厂获获 利利最最大大的的生生产产计计划划 2 目标函数为max Z 28x4 x5 2x6 约束形式为 且 x1 x2 x3 为松弛变量 表中的解代入目标函数中得Z 14 求出a g 的值 并判断是 否最优解 j c 0 00 00 028281 12 2 B C基基 b 1 x 2 x 3 x 4 x 5 x 6 x 2 2 6 x A A3 30 0 14 3 14 30 01 11 1 0 02 x 5 56 6D D2 20 05 25 20 0 28284 x 0 00 0E EF F1 10 00 0 jj zc B BC C0 00 0 1 1G G 第 3 页 共 16 页 3 某工厂生产A B 两种产品 已知生产A 每公斤要用煤6 吨 电4 度 劳动力3 个 生产B 每公斤要用煤4 吨 电5 度 劳动力10 个 又知每公斤A B 的利润分别为7 万元和 12 万元 现在该工厂只有煤360 吨 电200 度 劳动力300 个 问在这种情况下 各生产A B 多少公斤 才能获最大利 润 请建立模型 仅建立模型 不求解 4 已知单纯形表如下 其中x1 x2 x3 表示三种产品 的产量 x4 x5 是松弛变量 目标函数为max Z 1 写出此时生产方案 并判断是否最优生产方案 2 该生产方案下每种产品的机会费用 3 以此表为基础 请求出最优生产方案 答 1 生产方案是 不生产1 3 两种产品 只生产第2 种 产品100 3 个单位 不是最优方案 2 30 45 15 3 最优生产方案 不生产第3 种产品 1 2 两种产品各生产20 个单位 最大利润 1700 5 给出下面线性规划的标准形式 并用图解法求解 第 4 页 共 16 页 12 2 12 12 12 max2 515 6224 5 0 zxx x xx s t xx xx 解 标准形式如右下 12 23 124 125 15 max2 515 6224 5 0 zxx xx xxx s t xxx xx 最优解为 x1 2 x2 3z 8资源2 剩余6 6 某公司生产两种产品 其耗材获利情况如下表 问如何获利最大 产品1产品2资源量 原料1 0 40 520 原料2 00 26 原料3 0 60 321 获利 4030 请你 1 建立线性规划模型 2 并用单纯形法求解 3 根据单纯形表最终结果分析 若产品 1 的 获利上升到56 最优解是否会变化 若同时产品 2 的获利下降到24 最优解是否会变化 解 1 设产品 1 2 的产量分别为 x1 x2 可得如下模型 12 12 2 12 12 max4030 0 40 520 0 26 0 60 321 0 zxx xx x s t xx xx 2 单纯形表求解结果为 00410甲 0110乙 12006丙 1030丁 ABCD 12 25 20 2xx 资资源源剩剩余余2 2 通过代入参数到最终单纯形表 结合检验数可得 3 若产品 1 的获利上升到 56 最优解不会变化 若同时产品 2 的获利下降到 24 最优解会变化 7 已知某线性规划问题的初始单纯形表和用单纯形迭代后得到的表如下 运用单纯形法的向 量矩阵的方法求格中的未知数 P47 1 8lkjihgfedcba 第 5 页 共 16 页 解 8 已知某线性规划问题用单纯形迭代时得到中间某两步的单纯形表如下表所示 试将表中空 白处数字填上 P48 1 10 j c 354000 B C基b 1 x 2 x 3 x 4 x 5 x 6 x 5 2 x8 32 3101 300 0 5 x14 3 4 305 2 310 0 6 x29 35 304 2 301 jj zc 1 304 5 300 5 2 x15 418 41 10 41 4 3 x 6 415 414 41 3 1 x 2 41 12 4115 41 jj zc 证证明明 1 证明若线性规划问题存在可行解 则问题的可行域必定是凸集 2 第第二二章章 线线性性规规划划的的对对偶偶理理论论 选选择择 1 对偶问题的对偶 是 A 基本问题 B 解的问题 C 其它问题 D 原问题 正确答案为 4 2 若原问题是一标准型 则对偶问题的最优解值就等 于原问题最优表中松弛变量的 A 值 B 个数 C 机 会费用 D 检验数 正确答案 1 x 2 x 3 x 4 x 5 x 4 x6bcd10 5 x1 13E01 jj zc a 1200 1 x 2 x 3 x 4 x 5 x 1 xfg2 11 20 5 x4hi11 21 jj zc 0 7jkl 第 6 页 共 16 页 为 3 3 若原问题中xI 为自由变量 那么对偶问题中的第i 个约束一定为 A 等式约束 B 型约束 C 约束 D 无法确 定 正确答案为 1 4 原问题的第i 个约束方程是 型 则对偶问题的 变量qi 是 A 多余变量 B 自由变量 C 松弛变量 D 非负变量 正确答案为 B 5 若原问题求 目标最小 则对偶问题的最优解值就等于原问题最优 表中多余变量的 A 机会费用 B 个数 C 值 D 机会费用的相反数 正确答案为 D 6 原问题与对偶问题的最优 相同 A 解 B 目标值 C 解结构 D 解的分量个数 正确答案为 B 填填空空 1 对偶理论中 如原问题具有无界解 则其对偶问题 的解的情况为 2 对偶理论中 如原问题无可行解时 其对偶问题的 解的情况为 3 对偶理论中 若线性规划问题的最优解中 对应某 一约束条件的对偶变量值为非零 则该约束条件一定是 严格的 等式或不等式 反之 如果约束条件取 严格不等式 则其对应的对偶变量一定 第 7 页 共 16 页 为零或不为零 计计算算 1 写出该线性规划问题的对偶问题 求出原问题的最优 解 对偶问题的最优解为 0 0 4 4 原问题的最优解为 6 5 1 5 2 若某线性规划问题的标准模型为 且按单纯形法求解的其最优单纯 0 155 16 4 1222 32 max 21 2 1 21 21 xx x x xx ts xxz 形表为 j c 23000 B C基b 1 x 2 x 3 x 4 x 5 x 2 1 x3101 20 1 5 0 4 x400 214 5 3 2 x301001 5 jj zc 00 10 1 5 1 如果相应的目标系数由 2 3 分别变为 试运用灵敏度分析知识分析 21 c c 21 32 和 分别在什么范围变化 问题的最优解不变 21 和 2 如果标准模型中的常数列由 试运用灵敏度分 321 15 16 1215 16 12 分别变为 析知识分析分别在什么范围变化 问题的最优基不变 321 和和 3 如标准模型中增加了一个变量 且相应的目标系数最初单纯形表中的 6 x 4 6 c 试运用灵敏度分析的知识分析问题最优解的变化 T P 5 4 2 6 4 如在标准模型中增加了一个约束条件 试运用灵敏度分析知识分析最优解1423 21 xx 的变化 5 若相应的目标系数由 2 3 分别变为 试运用参数线性规划的知识分析 21 c c 322和 最优解随参数变化情况 并画出目标函数最优值随参数变化图 6 如果标准模型中的常数列中第三个约束的常数由 试运用参数线性规划的 1515变为 第 8 页 共 16 页 知识分析最优解随参数变化情况 并画出目标函数最优值随参数变化图 z 3 已知线性规划问题若其对偶问题的最优解为 0 12222 82 652 max 4321 4321 431 4321 xxxx xxxx xxx ts xxxxz 1 4 21 yy 1 写出线性规划问题的对偶问题 2 运用对偶理论分析求解原线性规划问题的最优解 4 已知线性规划问题当时 求 0 3 00 max 54321 225323222121 214313212111 543322111 xxxxx tbxxaxaxa tbxxaxaxa ts xxxcxcxtcz 0 11 tt 得问题的最终单纯形表为 P78 2 11 1 x 2 x 3 x 4 x 5 x 3 x5 201 211 20 1 x5 21 1 20 1 61 3 jj zc 0 40 4 2 1 确定的值 21321232221131211 bbcccaaaaaa 2 当值在什么范围内变化 上述最优解不变 12 0tt时 3 当值在什么范围内变化 上述最优基不变 21 0tt时 证证明明 1 叙述并证明对偶问题的基本性质中的弱对偶性 5 试叙述并证明对偶问题的基本性质中的最优性 6 试叙述并证明对偶定理 强对偶性 第第三三章章 运运输输问问题题 选选择择 1 若运输问题已求得最优解 此时所求出的检验数一定是全部 A 大于或等于零 B 大于零 C 小于零 D 小于或等于零 正确答案为 1 2 运输问题中 m n 1 个变量构成基本可解的充要条件是它不 含 A 松弛变量 B 多余变量 C 闭回路 D 圈 正确答案为 C 第 9 页 共 16 页 填填空空 计计算算 1 根据所给的表和一组解判断是否最优解 若不是 请求出最优解 x13 x14 x21 x22 x32 x34 5 2 3 1 5 4 2 求运输问题的最优解 解 增加一个产地 最优解 A1 B1 5 A1 B2 15 A1 B3 5 A1 B4 15 A2 B4 30 A3 B3 30 虚产地 B4 5 3 某部门有3 个生产同类产品的工厂 生产的产品由 4 个销售点出售 各厂产量 各地销量和各 厂到销售点的单位运价如下表 为使得总运费最小 请用西北角法求初始解 用表上作业法找 出最优运输方案 工厂 销售点 B1B2B3B4 产量 A141241116 A22103910 A38511622 销量 814121448 解 最后得结果如下 4 12 4 6 14 8 即运输方案为 A1 B1 运 4 A1 B3 运 12 A2 B1 运 4 A2 B4 运 6 A3 B2 运 14 A3 B4 运 8 或 第 10 页 共 16 页 124 8 2 14 8 即运输方案为 A1 B3 运 12 A1 B4 运 4 A2 B1 运 8 A2 B4 运 2 A3 B2 运 14 A3 B4 运 8 4 试分析发生下列情况时 运输问题的最优调动方案及总运价有何变化 1 单位运价表第 行的每个都加上一个常数 r ij ck 2 单位运价表第列的每个都加上一个常数 P100 3 2p ij ck 5 已知运输问题的产销平衡表 最优调运方案及单位运价表分别如下表所示 P101 3 3 产销平衡表及最优方案 销地 产地1 B 2 B 3 B 4 B 产量 1 A51015 2 A0101525 3 A55 销量 5151510 单位运价表 销地 产地1 B 2 B 3 B 4 B 1 A1012011 2 A127920 3 A2141618 试分析 1 从在什么范围变化时 上述最优调运方案不变 2222 cBA的单位运价到 2 从从变为何值时 将有无限多最优调运方案 4242 cBA的单位运价到 6 已知运输问题的产销平衡表 某一调运方案及单位运价表分别如下表所示 P103 3 7 产销平衡表及某一调运方案 销地 产地1 B 2 B 3 B 产量 1 A156 2 A11 3 A628 销量 753 单位运价表 销地 产地1 B 2 B 3 B 1 A2311 2 A328 3 A5815 第 11 页 共 16 页 1 以调运方案对应的变量为基变量 列出该运输问题用单纯形表求解时的单纯形表 2 在单纯形表上判断该调运方案是否最优 若否 用单纯形法继续迭代求出最优 3 在最终单纯形表上判别在什么范围内变化 表中最优调运不变 33 c 证证明明 第第四四章章 整整数数规规划划与与分分配配问问题题 选选择择 1 对max 型整数规划 若最优非整数解对应的目标函数值为 Zc 最优整数解对应的目标值为Zd 那么一定有 A Zc Zd B Zc Zd C Zc Zd D Zc Zd 正确答案为 4 2 求解指派问题的匈牙利方法要求系数矩阵中每个元素都是 A 非负的 B 大于零 C 无约束 D 非零常数 正确答案为 A 3 用割平面法求解整数规划时 构造的割平面只能切去 A 整数可行解 B 整数解最优解 C 非整数解 D 无法确定 正确答案为 C 4 只有一部分变量限制为整数的线性规划称 为 A 混合整数规划 B 局部整数规划 C 部分整数规划 D 0 1 规划 正确答案为 A 6 若是否采用 项目的0 1 变量为 那么个项目中至多只能选择一个项目的约束方程为 j j xJ A B C D 正确答案为 C Ji i x1 Ji i x1 Ji i x1 Ji i x1 填填空空 1 整数规划的分配问题中 若效率矩阵的元素可分成 0 与非0 两部分 则覆盖元素的最少直线数 不同行不同列的0 元素的最大个数 填大于 等于或小于 计计算算 1 有一份说明书 要分别译成英 日 德 俄四种文字 分别用 E J G R 表示 由甲 乙 丙 丁四人去完成 每个人完成任务所需时间见表所示 问怎样安排 才能使所用的时间最 少 2 指派4 个工人完成四项工作 每人做各项工作所耗时间如下表 工 人 工作 ABCD 甲 15182124 乙 19232218 丙 26171619 丁 19212317 第 12 页 共 16 页 问如何安排可使总耗时最少 用匈牙利法求解 解 匈牙利法求解如下 0269 1440V 10003 2360V V 工作安排 甲 A 乙 D 丙 C 丁 B 或 甲 B 乙 A 丙 C 丁 B 最小耗时为 70 3 已知某纯整数标准线性规划 运用割平面法求解 第一步得到该问题的最优单纯形表如下 B C基b 1 x 2 x 3 x 4 x 2 2 x5 2011 2 1 2 3 1 x13 410 1 43 4 jj zc 00 1 4 5 4 试简要说明并写出运用割平面法继续求解的下一步所确定的 Gomory 约束不等式 2 试0 1 变量将下列叙述成一般线性约束条件 1 5322 2121 xxxx或 2 变量只能取0 3 5 或7 中的一个 x 3 变量 或或等于500 x 证证明明 1 证明 如果从分配问题的效率矩阵的每一行元素分别减去一个常数 从每一列分别减去一个 常数 得到一个新的效率矩阵 则以新效率矩阵的分配问题模型与原分配问题的最优解相等价 第第五五章章目目标标规规划划 选选择择 填填空空 计计算算 1 某彩电组装工厂 生产 A B C 三种规格电视机 装配工作在同一生产线上完成 三种 产品装配每台的工时消耗分别为 6 小时 8 小时和 10 小时 生产线每月正常工作时间为 200 小时 每台彩电的利润分别为 500 元 650 元和 800 元 每月销售量预计分别为 12 台 10 台 和 6 台 该厂经营目标如下 p1 利润指标为 1 6 104 元 月 p2 充分利用生产能力 p3 加班时间不超过 24 小时 p4 产量以预计销量为标准 为确定生产计划 请你为该问题建立目标规划模型 不求解 解 设生产 A B C 三种规格电视机各为123 xxx 目标规划模型为 02610V 0330V 10004 1250V V V 第 13 页 共 16 页 1122334445566 4 12311 12322 233 144 255 366 min 5006508001 610 6810200 24 12 10 6 0 1 2 3 0 1 2 3 4 5 6 i jj PdP dP dPdddddd xxxdd xxxdd ddd xdd s t xdd xdd xi ddj 1 用图解法求解下面目标规划问题 1 0 2 42 92 62 35 min 21 442 3321 2221 1121 144332211 ii ddxx ddx ddxx ddxx ddxx ts dPddPdPdPz 证证明明 第第八八章章 动动态态规规划划 选选择择 填填空空 计计算算 1 某工厂自国外进口一部精密仪器 从制造厂至出口港有三个港口可选 而进口港又有三个 可供选择 进口后可经由两个城市到达目的地 其间运输成本如下图所示 用逆序解法求运 费最低的路线 第 14 页 共 16 页 解 逆序解法图示如下 粗线部分为可行路径 运费最低为 110 相应的路线可以为 A B2 C1 D1 E 或者 A B3 C1 D1 E 或者 A B3 C2 D2 E 2 运用动态规划的方法求解 0 10 294 max 321 321 2 321 xxx xxx ts xxxz 证证明明 第第十十一一章章 决决策策分分析析 选选择择 填填空空 计计算算 1 某书店希望订购最新出版的图书出售 根据以往经验 新书的销售量可能为 50 100 150 或200 本 假定每本书的订购价为4 元 销售价为6 元 剩书处理价为每本2 元 要求 1 建立条 件收益矩阵 2 分别依据悲观主义 乐观主久及等可能性决策准则 决定该书店订购新书 的数量 3 建立机会损失矩阵 并依据最小机会损失的决策准则决定订购数量 4 如果书 店统计过去销售新书数量的规律如下图所示 求 a 分别用EMV 和EOL 准则决定订购数量 b 第 15 页 共 16 页 假如书店负