运筹学作业题集 No.1线性规划 1、某织带厂生产A、B两种纱线和C、D两种纱带,纱带由专门纱线加工而成。 这四种产品的产值、成本、加工工时等资料列表如下 产品 B 项目 单位产值(元) 168 140 1050 406 单位成本(元) 42 单位纺纱用时(h) 单位织带用时(h) 工厂有供纺纱的总工时7200h,织带的总工时1200h。 (1)列出线性规划模型,以便确定产品的数量使总利润最大 (2)如果组织这次生产具有一次性的投入20万元,模型有什么变化?对模型的 解是否有影响?(所谓一次性投入就是与产量无关的初始投资) 、将下列线性规划化为极大化的标准形式 inf(x)=2x1+3x2+5 0,x3±不限 3、用单纯形法解下面的线性规划 max f(x)=2x,+5x2+3x ≤610 SI -2x1+x2+0.5x3≤420 ≥0, N.,2两阶段法和大M法 1、用两阶段法解下面问题:2、用大M法解下面问题,并讨论问题的解。 min f(x)=4x,+6x2 max 10x1+15x2+12x3 9 S st ≥0 2x1+x2+x3≥5 ≥0
运 筹 学 作 业 题 集 1 No.1 线性规划 1、某织带厂生产 A、B 两种纱线和 C、D 两种纱带，纱带由专门纱线加工而成。 这四种产品的产值、成本、加工工时等资料列表如下： 产品 项目 A B C D 单位产值 (元) 168 140 1050 406 单位成本 (元) 42 28 350 140 单位纺纱用时 (h) 3 2 10 4 单位织带用时 (h) 0 0 2 0.5 工厂有供纺纱的总工时 7200h，织带的总工时 1200h。 (1) 列出线性规划模型，以便确定产品的数量使总利润最大； (2) 如果组织这次生产具有一次性的投入 20 万元，模型有什么变化？对模型的 解是否有影响？（所谓一次性投入就是与产量无关的初始投资） 2、将下列线性规划化为极大化的标准形式 3、用单纯形法解下面的线性规划 − + + − + + + − = + + , , 0, 2 0.5 420 6 3 125 3 2 610 . . max ( ) 2 5 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x x st f x x x x No.2 两阶段法和大 M 法 2、用大 M 法解下面问题，并讨论问题的解。 + + − + + + + = + + , , 0, 2 5 5 6 15 15 5 3 9 . . max ( ) 10 15 12 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x x s t f x x x x 1、用两阶段法解下面问题： + + = + , 0 3 75 2 80 . . min ( ) 4 6 1 2 1 2 1 2 1 2 x x x x x x s t f x x x − + − + − = + − − = + + 1 2 3 不限 1 2 3 1 2 3 1 2 3 1 2 3 , 0, |19 7 5 | 13 6 7 9 16 5 . . min ( ) 2 3 5 x x x x x x x x x x x x st f x x x x
运筹学作业题集 No3线性规划的对偶问题 1、写出下列线性规划问题的对偶问题: maxf(x)=2x,+,-5>An< min f(x)=4x,-3x2+8x3 x1+x2-x3+x42 2≤x1≤6 (1) (2)s.t.{4≤x2≤14 x2+x3+x4=6 12≤x3≤-8 x1≤0,x2,x3≥0,x4±不限 2、写出下问题的对偶问题,解对偶问题,并证明原问题无可行解 maxf(x)=-4x1-3x2 ≤1 ≤-1 x1+2x,≤1 3、用对偶单纯形法求下面问题 mnf(x)=4x,+6x2 x1,x2≥0 No4线性规划的灵敏度分析 1、下表是一线性规划最优解的单纯形表 C1 21 21 030 x5 -1/3 11 原问题为max型,¤,为松驰变量,x6为剩余变量,回答下列问题 (1)资源1、2、3的边际值各是多少?(x4,x5是资源1、2的松驰变量,x6是资 源3的剩余变量) (2)求C1,C2和C3的灵敏度范围 (3)求A1b1,Abz的灵敏度范围
运 筹 学 作 业 题 集 2 No.3 线性规划的对偶问题 − − − = − + 12 8 4 14 2 6 . . min ( ) 4 3 8 3 2 1 1 2 3 x x x s t f x x x x 2、写出下问题的对偶问题，解对偶问题，并证明原问题无可行解 3、用对偶单纯形法求下面问题 + + = + , 0 3 75 2 80 . . min ( ) 4 6 1 2 1 2 1 2 1 2 x x x x x x s t f x x x No.4 线性规划的灵敏度分析 1、下表是一线性规划最优解的单纯形表 Cj → 21 9 4 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 21 x1 4 1 0 1/3 2/3 0 1/3 0 x5 2 0 0 −2/3 −4/3 1 1/3 9 x2 23 0 1 1/3 −1/3 0 −2/3 zj 21 9 10 11 0 1 cj − zj 0 0 −6 −11 0 −1 原问题为 max 型，x4，x5 为松驰变量，x6 为剩余变量，回答下列问题： (1)资源 1、2、3 的边际值各是多少？(x4，x5 是资源 1、2 的松驰变量，x6 是资 源 3 的剩余变量) (2)求 C1, C2 和 C3 的灵敏度范围； (3)求b1，b2 的灵敏度范围。 1、写出下列线性规划问题的对偶问题： (1) + + = + + − + = + − 1 2 3 4 不限 2 3 4 1 3 1 2 3 4 1 2 3 0, , 0, 6 2 4 5 . . max ( ) 2 3 5 x x x x x x x x x x x x x s t f x x x x (2) − + − − + = − − , 0, 2 1 1 1 . . max ( ) 4 3 1 2 1 2 2 1 2 1 2 x x x x x x x st f x x x
运筹学作业题集 No5运输问题 分别用西北角法、最低费用法和运费差额法,求下面运输问题(见表)的初始 可行解,并计算其目标函数。(可不写步骤) 2、以上题中最低费用法所得的解为初始基础可性解,用表上作业法(踏石法 求出最优解。(要求列出每一步的运费矩阵和基础可行解矩阵) 销地B1 B 产量 12 A 15 No.6指派问题 1、有4个工人。要指派他们分别完成4项工作。每人做各项工作所消耗的时间 (h)如下表,问如何分派工作,使总的消耗时间最少? D 3256 260 2、学生A、B、C、D的各门成绩如下表,现将此4名学生派去参加各门课的 单项竞赛。竞赛同时举行,每人只能参加一项。若以他们的成绩为选派依据, 应如何指派最有利? 数学 物理 化学 外语 C 280 882%
运 筹 学 作 业 题 集 3 No.5 运输问题 1、分别用西北角法、最低费用法和运费差额法，求下面运输问题(见表)的初始 可行解，并计算其目标函数。(可不写步骤) 2、以上题中最低费用法所得的解为初始基础可性解，用表上作业法（踏石法） 求出最优解。（要求列出每一步的运费矩阵和基础可行解矩阵） 销地 产地 B1 B2 B3 B4 B5 产量 A1 6 9 4 8 5 20 A2 10 6 12 8 7 30 A3 6 5 9 20 9 40 A4 2 13 6 14 3 60 销量 25 15 35 45 30 No.6 指派问题 1、有 4 个工人。要指派他们分别完成 4 项工作。每人做各项工作所消耗的时间 (h) 如下表，问如何分派工作，使总的消耗时间最少？ 消耗 工作 工人 A B C D 甲 3 3 5 3 乙 3 2 5 2 丙 1 5 1 6 丁 4 6 4 10 2、学生 A、B、C、D 的各门成绩如下表，现将此 4 名学生派去参加各门课的 单项竞赛。竞赛同时举行，每人只能参加一项。若以他们的成绩为选派依据， 应如何指派最有利？ 得分 课程 学生 数学 物理 化学 外语 A 89 92 68 81 B 87 88 65 78 C 95 90 85 72 D 75 78 89 96
运筹学作业题集 No7动态规划 某公司有9个推销员在全国三个不同市场里推销货物,这三个市场里推销员 人数与收益的关系如下表,做出各市场推销人员数的分配方案,使总收益最大。 4 5 110 4050 8293 4115125135 97109120131140150 2、设某工厂要在一台机器上生产两种产品,机器的总运转时间为5小时。生产 这两种产品的任何一件都需占用机器一小时。设两种产品的售价与产品产量成 线性关系,分别为(12-x)和(13-2x2)。这里x和x2分别为两种产品的产量。假 设两种产品的生产费用分别是4x1和3x2,问如何安排两种产品的生产量使该机 器在5小时内获利最大 No8最短路问题 1、求下图中η到所有点的最短路径及其长度。(要求最短路用双线在图中标出, 保留图中的标记值) 2、将右图看作无向图,写出边权 邻接矩阵,用Prim算法求最大生 成树,并画出该树图。 No9网络流问题 1、求下面网络s到t的最大流和最小截,从给定的可行流开始标号法。(要求每 得到一个可行流后,即每次增广之后,重新画一个图,标上增广后的可行流 再进行标号法) (44) 2∠4.4) (3.0) 地(0 (4.0)
运 筹 学 作 业 题 集 4 No.7 动态规划 1、某公司有 9 个推销员在全国三个不同市场里推销货物，这三个市场里推销员 人数与收益的关系如下表，做出各市场推销人员数的分配方案，使总收益最大。 推销员 市场 0 1 2 3 4 5 6 7 8 9 1 20 32 47 57 66 71 82 90 100 110 2 40 50 60 71 82 93 104 115 125 135 3 50 61 72 84 97 109 120 131 140 150 2、设某工厂要在一台机器上生产两种产品，机器的总运转时间为 5 小时。生产 这两种产品的任何一件都需占用机器一小时。设两种产品的售价与产品产量成 线性关系，分别为(12−x1)和(13−2x2)。这里 x1 和 x2 分别为两种产品的产量。假 设两种产品的生产费用分别是 4x1 和 3x2，问如何安排两种产品的生产量使该机 器在 5 小时内获利最大。 No.8 最短路问题 1、求下图中 v1 到所有点的最短路径及其长度。(要求最短路用双线在图中标出， 保留图中的标记值) 2、将右图看作无向图，写出边权 邻接矩阵，用 Prim 算法求最大生 成树，并画出该树图。 No.9 网络流问题 1、求下面网络 s 到 t 的最大流和最小截，从给定的可行流开始标号法。(要求每 得到一个可行流后，即每次增广之后，重新画一个图，标上增广后的可行流， 再进行标号法) s v 1 v3 v2 v 4 v 5 t (2,0) (8,4) (3,0) (4,0) (4,0) (4,4) (9,0) (3,0) (3,0) (6,0) (4,4) (10,0) v1 v2 v 3 v4 v 5 v 6 v 7 v 8 1 4 5 5 3 6 1 2 7 3 7 5 2 1
运筹学作业题集 No.10随机服务系统:输入过程 1、对一服务系统进行观察,总观察时间为1027分钟,到达系统的累计人数为 40人,顾客累计的排队等待时间为44.8分钟,顾客累计的服务时间为796 分钟,求 (1)系统中平均排队长度 (2)平均同时接受服务的人数 2、某选举站对甲、乙二人进行选举,选票中只能选其中一人才有效。假设投票 的人流服从泊松分布,投甲票的人的到达率为A1-4人/小时,投乙票的人的 到达率为A2=2人/小时:再假设所有投票人的票都是有效的,而选举结果的 统计是在一个与选民不见面的屋里与投票过程同时进行的。问选举开始后半 小时统计结果为: (1)甲得三票,乙得1票的概率 (2)总票数为5的概率; (3)甲得全票的概率 No.11随机服务系统:标准服务系统 1、某自动交换台有4条外线,打外线的呼叫强度为2次/分钟,为泊松流,平 均通话时长为2分钟。当4条外线全忙时,用户呼叫将遇忙音。假设用户 遇忙音后立即停止呼叫。问 (1)用户拨外线遇忙的概率为多大? (2)一小时内损失的话务量为多少? (3)外线的利用率为多少? (4)过负荷为100%时,外线的利用率为多少? 2、某车间机器发生故障为一泊松流,平均4台/小时。车间只有一名维修工, 平均7分钟处理一台故障。若为该维修工増加一特殊工具可使平均故障处 理时间降到5分钟,但这一特殊工具的使用费用为5元/分钟。机器故障停 工每台每分钟损失5元,问购置这台特殊工具是否合适? 3、有MMn:∞/∞/FIFO(先到先服务)系统,输入业务量为o,求 当n=1,2,3时的等待概率D,和平均逗留队长Ld的公式
运 筹 学 作 业 题 集 5 No.10 随机服务系统：输入过程 1、对一服务系统进行观察，总观察时间为 102.7 分钟，到达系统的累计人数为 40 人，顾客累计的排队等待时间为 44.8 分钟，顾客累计的服务时间为 79.6 分钟，求 (1) 系统中平均排队长度； (2)平均同时接受服务的人数。 2、某选举站对甲、乙二人进行选举，选票中只能选其中一人才有效。假设投票 的人流服从泊松分布，投甲票的人的到达率为1 =4 人/小时，投乙票的人的 到达率为2 =2 人/小时；再假设所有投票人的票都是有效的，而选举结果的 统计是在一个与选民不见面的屋里与投票过程同时进行的。问选举开始后半 小时统计结果为： (1)甲得三票，乙得 1 票的概率； (2)总票数为 5 的概率； (3)甲得全票的概率。 No.11 随机服务系统：标准服务系统 1、某自动交换台有 4 条外线，打外线的呼叫强度为 2 次/分钟，为泊松流，平 均通话时长为 2 分钟。当 4 条外线全忙时，用户呼叫将遇忙音。假设用户 遇忙音后立即停止呼叫。问 (1)用户拨外线遇忙的概率为多大？ (2)一小时内损失的话务量为多少？ (3)外线的利用率为多少？ (4)过负荷为 100%时，外线的利用率为多少？ 2、某车间机器发生故障为一泊松流，平均 4 台/小时。车间只有一名维修工， 平均 7 分钟处理一台故障。若为该维修工增加一特殊工具可使平均故障处 理时间降到 5 分钟，但这一特殊工具的使用费用为 5 元/分钟。机器故障停 工每台每分钟损失 5 元，问购置这台特殊工具是否合适？ 3、有 M/M/n：//FIFO(先到先服务)系统，输入业务量为，求： 当 n=1, 2 , 3 时的等待概率 D，和平均逗留队长 Ld 的公式