运筹学期末考试试卷解答

1 06 运筹学运筹学 试卷试卷 A 解答解答 1 1 不可能 因为 对应两列系数与其它列合在一起不能构成基 已 j x j x 经线性相关 2 是的 其对偶问题也一定具有无穷多个最优解 由对偶问题解与原问题检 验数的对应关系便可得出 原问题非基变量检验数为零 这个时候得到一组原 问题和对偶问题的最优解 继续迭代又会得到另外一组 所以原问题有多少解 对偶问题就有多少 3 因为伏格尔方法不是一味选最小运价来填 而是通过比较行列差额 将差 额大的行或列优先按最小运价来添 这样就不会为了节省一处的费用而致使其 他处的费用增加 而是权衡之后填入 这就有可能使得由此得出的初始方案比 用最小元素法给出的初始方案更接近于问题的最优解 4 因为目标规划存在目标约束条件 目标规划的满意解是指尽量接近目标值 的方案 同时目标优先次序的改变也会使满意方案改变 而最优解是求满足所 有约束条件的使目标最好的解 所有约束条件同等看待 使得所有约束均为刚 性约束 没有伸缩余地 特别在处理多目标时 有可能不存在最优解 因为可 能目标之间存在冲突 而目标规划就可以依据优先次序求出满意解 5 缓冲存储量是为了预防需求突然增加或拖后时间延长而准备的库存 通常 依据一定的方式计算或估计出来 正常情况不使用 订货点是当库存降到一定 数量之后就要发出定单 这个指示点就是订货点 订货点 缓冲存储量 正常拖 后时间内的需求量 2 解 解 1 当 0 0 时 我们利用 0 时 最优解所对应的单纯形表 可以得出反映本问题的一个单纯形表如下 2 11 00 CBXBbx1x2x3x4x5 2x1611110 0 x51003111 120 3 1 20 2 即只是非基变量 x3的检验数发生变化 其余不变 这时 若 0 1 则最优 解不变 仍然为 x1 x2 x3 x4 x5 6 0 0 0 10 若 1 则以 x3 为换入变量 x1为换出变量 进行基变换得如下表 2 11 00 CBXBbx1x2x3x4x5 1 x3611110 0 x54 12001 18 6 1 2 0 1 0 则最优解变为 x1 x2 x3 x4 x5 0 0 6 0 4 2 若 0 0 我们将目标函数中 3 移到左边 令新的目标函数Z Z 3 并利用 0 时 最优解所对应的单纯形表可以得出反映本问题的一个单 纯形表如下 2 1100 CBXBbx1x2x3x4x5 2x16 11110 0 x510 2 03111 120 3 1 20 显然 若 0 6 则最优解为 x1 x2 x3 x4 x5 6 0 0 0 10 2 若 6 则由于 x1 6 0 且其所对应约束条件的所有变量系数 0 故由对 偶单纯形算法可知 原问题没有可行解即无解 3 解 解 1 该问题的目标规划数学模型为 3 2 1 0 0 5450 5340 4002020 min 21 332 221 1121 332211 iddxx ddx ddx ddxx dPdPdPZ ii 2 与 1 相比较 只是目标函数改变了 而约束条件没有变 因而本问题 3 的目标规划数学模型为 3 2 1 0 0 5450 5340 4002020 min 21 332 221 1121 133221 iddxx ddx ddx ddxx dPdPdPZ ii 4 解 解 这是一个人数多于任务数的非平衡指派问题 虚设两项任务 V VI 并 设任务的收益为零 化成平衡的指派问题 该平衡的指派问题的收益矩阵为 0013111213 0012101112 001191010 0010898 008676 005453 ij c 目标函数为 将其化为极小值问题 ij ij ijx cz 6 1 6 1 max ijijij ccccc 13max 13130210 13131321 13132433 13133545 13135767 131389810 ij c 880110 770110 660111 550112 330112 000002 13130210 13131321 13132433 13133545 13135767 131389810 ij c 4 550000 440000 330001 220002 000002 003225 770000 660000 550001 440002 220002 001003 由上可得 该指派问题的最优解为 1 615243342516 xxxxxx 其余为 0 即第三个人完成第四项任务 第四个人完成第三项任务 第五个人 完成第二项任务 第六个人完成第一项任务 所得的最大总收益为 Z 6 13 13 13 3 4 2 43 5 解 解 这是一个价格有折扣的订货模型 已知 年需求量 D 2000 双 年 订购 费 C3 30 元 次 存贮费 C1 5 6 元 年 双 设订货量为 Q 双 则商场从供应商 处所获得的每双鞋的进货价格 K Q 为 30028 30020030 20010032 100036 Q Q Q Q QK 1 首先 我们利用 E O Q 公式计算 Q 如下 双 1465713 21428 6 5 20003022 1 3 C DC Q 显然 146 100 200 所以计算 52 2828 300 30 20002 3006 5 300 3002 300 300 43 3030 200 30 20002 2006 5 200 2002 200 200 51 3232 146 30 20002 1466 5 2 31 4 31 3 3 1 2 K C D C C K C D C C QK Q C D QC QC 比较 所以 该商场的 52 28300300 200 146min 4432 CCCC 5 最佳订货量是每次 300 双 2 订 500 双时的全年总费用 元 57520200028 500 200030 2 5006 5 500 5002 500 500 31 DK DCC C 订 300 双时的全年总费用 元 57040200028 300 200030 2 3006 5 300 3002 300 300 31 DK DCC C C 500 C 300 57520 57040 480 元 采纳新的库存建议策略 则会比现行库存策略每年节省 480 元 6 解 解 1 外部随机事件是 3 年行程公里数 这是一个随机变量 取值有 36000 45000 和 54000 公里三种 2 王先生该问题的支付矩阵如下表所示 单位 美元 支付费用支付费用 行程行程 经销商经销商 三年行程 36000KM 三年行程 45000KM 三年行程 54000KM 经销商 1107641211413464 经销商 2111601116012960 经销商 3117001170011700 3 假设 E1 三年行程 36000 公里 E2 三年行程 45000 公里 E3 三 年行程 54000 公里 则乐观法的决策是 小中取小 会选择经销商 1 的租赁方式 悲观法的决策是 大中取小 会选择经销商 3 的租赁方式 后悔值法的决策 首先构造后悔值矩阵 见如下表 表中值为每个元素减去该列中最小元素 支付费用支付费用 行程行程 经销商经销商 E1E2E3 经销商 109541764 经销商 239601260 经销商 39365400 每行取最大 再在这三个数中取最小得 936 对应可知应选择经销商 3 6 12 5 3 4 6 0 0 12 8 7 4 15 8 8 12 15 5 4 由 2 中的表得反映本问题的支付表如下 E1E2E3支付费用支付费用 行程行程 经销商经销商 0 50 40 1 经销商 1107641211413464 经销商 2111601116012960 经销商 3117001170011700 由表中可得 选择经销商 1 的期望支付为 Payment1 0 5 10764 0 4 12114 0 1 13464 11574 美元 选择经销商 2 的期望支付为 Payment2 0 5 11160 0 4 11160 0 1 12960 11340 美元 选择经销商 3 的期望支付为 Payment3 0 5 11700 0 4 11700 0 1 11700 11700 美元 那么依据期望值法则 王先生将会选择期望支付最小的经销商 即经销商 2 7 解 解 1 该问题的网络图既网络时间如下图所示 B 8 C 6 D 3 G 4 H 3 A 4 E 5 F 7 2 总时差