(最新)管理运筹学课后答案——谢家平

(最新)管理运筹学课后答案——谢家平内容摘要：

标函数 值 为整数规划问题上界；在满足整数约束的子问题的解中，最大的目标函数值为整数规划问 题的下界。 当上下界相同时，则已得最优解；否则，转入剪枝过程。 (3)剪枝过程。 在下述情况下剪除这些分枝：①若某一子问题相应的线性规划问题无可行解； ②在分枝过程中，求解某一线性规划所得到的目标函数值 Z 不优于现有下界。 (4)分枝过程。 当有多个待求分枝时，应先选取目标函数值最优的分枝继续进行分枝。 选 取一个不符合整数条件的变量 xi 作为分枝变量，若 xi 的值是 bi* ，构造两个新的约束条 件： xi≤[bi ] 或 xi≥[bi ]+1,分别并入相应的数学模型中，构成两个子问题。 对任一个子 问题， 转步骤 (1)。 最整数解为： x1=4, x2=2, z = 340 4. 解：设 ,tij 为个人对于个任务的时间耗费矩阵，则目标函 数为： 约束条件为： * * 解之得： x = 1 ， x = 1 ， x = 1， x = 1 ，其余均为 0， z=70，即任务 A 由 12 21 33 44 乙完成，任务 B 由甲完成，任务 C 由丙完成，任务 D 由丁完成。 5. 解：设在第 i 天应聘的雇员人数为 xi。 数学模型为： 解得： x1=0， x2=4， x3=32， x4=10， x5=34， x6=10， x7=4， Z=94。 第五章 1. 解：建立目标约束。 （ 1）装配线正常生产 设生产 A, B,C 型号的电脑为 x1, x2 , x3（台）， d + − 1 为装配线正常生产时间未利用数， d1 为 装配线加班时间，希望装配线正常生产，避免开工不足，因此装配线目标约束为 （ 2）销售目标 优先满足老客户的需求，并根据三种电脑的纯利润分配不同的权因子， A, B,C 三种型号的 电脑每小时的利润是 ， ， ，因此，老客户的销售目标约束为 再考虑一般销售。 类似上面的讨论，得到 （ 3）加班限制 首先是限制装配线加班时间，不允许超过 200h，因此得到 其次装配线的加班时间尽可能少，即 写出目标规划的数学模型 经过 Lingo 计算得到 x1 = 100， x2= 55， x3=80。 装配线生产时间为 1900h，满足装 配线加班不超过 200h 的要求。 能够满足老客户的需求，但未能达到销售目标。 销售总利 润为 1001000+551440+802520=380800（元）。 2. 解：假设三个工厂对应的生产量分别为 300， 200， 400。 （ 1）求解原运输问题 由于总生产量小于总需求量，虚设工厂 4，生产量为 100 个单位，到各个用户间的运费单 价为 0。 用 LINGO 软件求解，得到总运费是 2950 元，运输方案如下表所示。 （ 2）下面按照目标的重要性的等级列出目标规划的约束和目标函数。 设 xij 工厂 i(i =1,2,3)调配给用户 j( j = 1,2,3,4)的运量， cij 表示从工厂 i 到用户 j 的 单位产品的运输费用， aj( j = 1,2,3,4)表示第 j 个用户的需求量， bi(i =1,2,3)表示第 i 个工厂的生产量。 i）供应约束应严格满足，即 ii）供应用户 1 的产品中，工厂 3 的产品不少于 100 个单位，即 iii）需求约束。 各用户的满足率不低于 80％， 即。 应尽量满足各用户的需求，即 iv）新方案的总运费不超过原方案的 10％（原运输方案的运费为 2950 元），即 v）工厂 2 到用户 4 的路线应尽量避免运输任务，即 vi）用户 1 和用户 3 的满足率应尽量保持平衡，即 vii）力求总运费最少，即 目标函数为 经 8 次运算，得到最终的计算结果，见下表。 总运费为 3360 元，高于原运费 410 元，超 过原方案 10％的上限 115 元。 A 机器 x1 台， B 机器 x2 台。 目标函数为： Lingo 计算结果为：生产 A 机器 15 台， B 机器 21 台，利润增加 4129 元，工序Ⅱ 加班 小时。 第六章 1. 原有问题的求解就化为逐个求解几个简单的阶段子问题，当每一个阶段的决策子问题确定后，就组成了一个决策序列， 每个阶段的决策一旦确定，整个决策过程也随之确定，此类把一个问题看作是一个前后关联具有明显阶段性的决策过程 就称为多阶段决策问题。 2. 动态规划最优性原理导出了它的解 题思路，即将决策问题划分为若干个阶段，将全过程的优化问题分解为子过程的优 化问题；逆着阶段顺序的方向，由后向前逐步倒推；各阶段求解都是在后部子过程最优策略基础上，再考虑本阶段的指 标函数，求出本阶段的最优策略；由后向前推算直到第一阶段为止，最优化的子过程逐渐成为最优化的全过程。 3.（ 1）模型建立 将三个营业区看作是三个阶段，即阶段变量 k =1,2,3； 第 k 阶段初尚未被分配出去的销售点是其决策的起点，则状态变量 Sk 表示第 k 阶段初可分配的销售区数， Sk≥ 0 ， 且 初始状态已知 S1= 6 ； 决策变量 xk表示第 k 阶段分配给区 A， B， C 的销售店，允许决策集合 状态转移方程为 Sk+1=Skk 阶段指标 Vk( Sk,xk)表示第 k 阶段从 Sk 销售点中分配给第 k 区 xk 个的阶段效益； 最优指数函数 fk(Sk)表示第 k 阶段从 Sk 开始到最后阶段采用最优分配策略取得的最大收益，递推方程函数式 （ 2）逆序求解 当 k =3 时 当 k=2 时 当 k =1 时 顺序递推，得出结论：第 A 小组建 3 个 ,第 B 区建 2 个，第 C 区建 1 个， 4.（ 1）模型建立 多阶段性的月度生产决策，可以按月划分阶段，即阶段变量 k = 1, 2,3, 4 分别表示这四个 月。 上期未需求的产品将会进入仓库存放，供下期需求消费；下期生产与否，视期初库存数 量和当期需求量而定，第 k 月 的期初库存反映出其状态特征。 因此，状态变量 Sk 表示第 k 月 期初的产品库存量， 0≤ Sk≤4。 决策变量 xk 表示第 k 月的实际生 产量，允许决策集合 Xk(Sk) {0 ≤ xk≤ 4}。 第 k 月的订货量记为 dk，而供给量为 Sk+ xk，则状态转移方程为 Sk+1=Sk+ xkdk。 阶段指标 vk(Sk ,xk)k 表示第 k 月的费用。 本月若不安排生产，则仅需支出存货费；若安排 生产，则需支出生产成本 和固定运营费，同时还需存货费。 为了将存储问题简化，忽略本月 生产和需求产品的短期存货费。 因此当 xk=0 时， v k(Sk ,xk)= H Sk= 1500Sk；当 xk＞ 0 时， 最优指数函数 fkSk( )表示第 k 阶段从期初库存 Sk 开始到最后阶段采用最优生产策略实现的最低生产费用。 （ 2）逆序求解 k =4 时，因为 4 月末交货后的计划存货 0 件，则 S5=0；第 4 月的订单需求 d4=1 万件，则由状态转移方程 S = S4+ x4d4 知， S4+ x4= 1。 5 k=3 时，第 3 月的订单需求 d3=5 万件，则满足需求有 S3+ x3≥ 5 ；而仓库的最大 存货能力为 4 万件，则由状态转 移方程 S4= S3+ x3d3 有 S3+ x3≤ 6。 k=2 时，第 2 月的订单需求 d2=3 万件，则满足需求有 S2+ x2≥ 3 ；而仓库的最大存货能力为 4 万件，则由状态 转移方程 S3= S2+ x2d2 有 S2+ x2≤ 7。 k=1 时，企业现有存货 0 件，即 S1= 0 ，第 1 月的订单需求 d1=2 万件，而仓库的最大存货能力为 4 万件，则有 x ≤ 6。 1 顺序递推，得出结论：第 1 月生产 5 万件；由状态转移方程 S2= S1+x1d 1 知， S2= 3 ，则第 2 月生产 0 件；再由状 态转移方程 S3= S2+ x2d2−知， S3= 0 ，则第 3 月生产 6 万件；再由状态转移方程 S4= S3+x3d3 ，则第 4 月生产 0 件。 ，即阶段变量 k = 1, 2,3, 4,5 ； 知， S4= 1 状态变量 Sk 表示第 k 年 初所拥有的完好机器台数，已知 S1=200；决策变量 xk 表示第 k 年投入超负荷生产的设备 数，则剩余设备 Sk− xk 投入低负荷的生产作业，允许决策集合 0≤ xk≤ Sk； 状态转移方程为 S = (1α)x +(1β)(S x ) = ； k+1 k k k k k 阶段指标 vk(sk,xk)表示第 k 年的收益，即 vk(sk,xk)=12xk+ 8(Skxk)=8Sk+4xk； 最优指数函数 fk(Sk)表 示第 k 年从 Sk 开始到 5 年末采用最优分配策略实现的最收益； 基本递推方程 边界条件： f6(s6)=0 k=5， 由于 f (s )是关于 x 的单增函数，故 x * =s 时， f (s ) 最大， f5(s5)=12s5 5 5 5 5 5 5 5 k=4， 由于 f4(s4)是关于 x4 k=3， 的单增函数，故 x 4=S4 时， f4(s4)最大， f4(s4)=， 由于 f3(s3)是关于 x3 k=2， 的单减函数，故 x3 =0 时， f3(s3)最大， f3(s3)=。 由于 f2(s2)是关于 x2 的单减函数，故 x 2=0 时， f2(s2)最大， f s2( )2= s1。 * 最优作业安排策略是前三年将低负荷，后两年全部重负荷。 s1=200，而 x1 * * =0，则 S2==170 台；同 * 理，由 x2 =0，则 S3==144 台；由 x * 3 =0，则 S4==122 台；由 x4 =S4=122 台，则 S5==67 台；由 x5 =S5=36 台。 * * * 第七章 1. 求得的最小树如下图： 2. （ 1）给网络始点 v s 标号 (vs,0) ，并在标号下面画横线表示为永久标号；并给从 vs 出发的各弧的点 vj 赋予临时标号 (ws,v sj )，不能一步到达的点赋 予临时标号 (vs, ∞)。 （ 2）在所有临时标号中选择路权最小者，即结点 v1，将 v1 的临时标号变为永久标号，在 标 号 下 画 横 线。 然 后 ， 考 察 从 v 1 出 发 的 各 弧 的 点 vj 的 临 时 标 号 ： 结 点 v 5 的 路 权 d5= min{∞,d1+w 15 } = min {∞,4+5}=9，则将 v5 的临时标号变为 (v1,9) ，并划去其原有较大的临 时标号 (vs, ∞)；同理，对于结点 v4，临时标 号变为 (v1,8) ；对于结点 v2，临时标号变为 (v1,11) ；其他结点标号不变。 （ 3）依此类推，重复上述标号过程。 当所有标号都是永久标号，即每一个标号下都画上横线时，则标号过程结束。 vt 的后一个标号为 vs 到 vt 的最短路权，即 14；根据 vt 的另一个标号反向追踪求得 vs 到 vt 的最短路径为 {vs,v3,v2,v6, vt} 3.（ 1）网络的中心 从表中可得出：各列之和的最小值为 22，对应的点 D 即是网络的中心；也可以根据各行选择最大值，再从中选择最小 值为 5，同样对应的点 D 是网络的中心。 因此，仓库应建在位于网络中心的销售点 D。 （ 2）网络的重心 各列加权之和的最小。