运筹学课后习题答案

PAGE 1 运筹学作业 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 答案 (教师用) 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万元，模型有什么变化？对模型的解是否有影响？ 解：(1)设A的产量为x1，B的产量为x2，C的产量为x3，D的产量为x4，则有线性规划模型如下： max f(x)=(168(42)x1 +(140(28)x2 +(1050(350)x3 +(406(140)x4 =126 x1 +112 x2 +700 x3 +266 x4 s.t. (2)如果组织这次生产有一次性的投入20万元，由于与产品的生产量无关，故上述模型只需要在目标 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 中减去一个常数20万，因此可知对模型的解没有影响。 2、将下列线性规划化为极大化的标准形式 解：将约束条件中的第一行的右端项变为正值，并添加松弛变量x4，在第二行添加人工变量x5，将第三行约束的绝对值号打开，变为两个不等式，分别添加松弛变量x6, x7，并令 ，则有 max[(f(x)]= {(2 x1 (3 x2 (5( )+0 x4 (M x5+0 x6 +0 x7} s.t. 3、用单纯形法解下面的线性规划 解：在约束行1,2,3分别添加x4, x5, x6松弛变量，有初始基础可行解和单纯形法迭代步骤如下： Cj ( 2 5 3 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 bi/aij* 0 x4 610 3 2 (1 1 0 0 610/2 0 x5 125 (1 (6) 3 0 1 0 125/6* 0 x6 420 (2 1 1/2 0 0 1 420/1 OBJ= 0 zj ( 0 0 0 0 0 0 cj - zj 2 5 3 0 0 0 Cj ( 2 5 3 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 bi/aij* 0 x4 1705/3 (10/3) 0 (2 1 (1/3 0 170.5 5 x2 125/6 (1/6 1 1/2 0 1/6 0 － 0 x6 2395/6 (11/6 0 0 0 (1/6 1 － OBJ= 625/6 zj ( (5/6 5 5/2 0 5/6 0 cj - zj 17/6 0 1/2 0 (5/6 0 Cj ( 2 5 3 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 bi/aij* 2 x1 341/2 1 0 (3/5 3/10 (1/10 0 － 5 x5 197/4 0 1 (2/5) 1/20 3/20 0 125.125 0 x6 2847/4 0 0 (11/10 11/20 (7/20 1 － OBJ= 2349/4 zj ( 2 5 4/5 17/20 11/20 0 cj - zj 0 0 11/5 0 (11/20 0 Cj ( 2 5 3 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 bi/aij* 2 x1 1955/8 1 3/2 0 3/8 1/8 0 3 x3 985/8 0 5/2 1 1/8 3/8 0 0 x6 13555/16 0 11/4 0 11/16 1/16 1 OBJ= 6865/8 zj ( 2 21/2 3 9/8 11/8 0 cj - zj 0 (11/2 0 (9/8 (11/8 0 答：最优解为x1 =244.375, x2 =0, x3 =123.125, 剩余变量x6 =847.1875；最优解的目标函数值为858.125。 No.2 两阶段法和大M法 1、用两阶段法解下面问题： 解：将原问题变为第一阶段的标准型 第一阶段单纯形表 Cj ( 0 0 0 0 (1 (1 CB XB b x1 x2 x3 x4 x5 x6 bi/aij* (1 x5 80 1 2 (1 0 1 0 80 (1 x6 75 (3) 1 0 (1 0 1 75/3* OBJ= (155 zj ( (4 (3 1 1 (1 (1 cj - zj 4 3 (1 (1 0 0 Cj ( 0 0 0 0 (1 (1 CB XB b x1 x2 x3 x4 x5 x6 bi/aij* (1 x5 55 0 (5/3) (1 1/3 1 (1/3 55(3/5* 0 x1 25 1 1/3 0 (1/3 0 1/3 25(3 OBJ= (55 zj ( 0 (5/3 1 (1/3 (1 1/3 cj - zj 0 5/3 (1 1/3 0 (4/3 Cj ( 0 0 0 0 (1 (1 CB XB b x1 x2 x3 x4 x5 x6 bi/aij* 0 x2 33 0 1 (3/5 1/5 3/5 (1/5 0 x1 14 1 0 1/5 (2/5 (1/5 2/5 OBJ= 0 zj ( 0 0 0 0 0 0 cj - zj 0 0 0 0 (1 (1 第二阶段 Cj ( (4 (6 0 0 CB XB b x1 x2 x3 x4 bi/aij* (6 x2 33 0 1 (3/5 1/5 (4 x1 14 1 0 1/5 (2/5 OBJ= (254 zj ( (4 (6 14/5 2/5 cj - zj 0 0 (14/5 (2/5 答：最优解为x1 =14，x2 =33，目标函数值为254。 2、用大M法解下面问题，并讨论问题的解 解：第1、2行约束条件添加x4, x5松弛变量，第3行添加x6剩余变量和x7人工变量，有如下初始单纯形表和迭代步骤： Cj ( 10 15 12 0 0 0 (M CB XB b x1 x2 x3 x4 x5 x6 x7 0 x4 9 (5) 3 1 1 0 0 0 0 x5 15 (5 6 15 0 1 0 0 (M x7 5 2 1 1 0 0 (1 1 OBJ= (5M zj ( (2M (M (M 0 0 M (M cj - zj 10+2M 15+M 12+M 0 0 (M 0 Cj ( 10 15 12 0 0 0 (M CB XB b x1 x2 x3 x4 x5 x6 x7 10 x1 9/5 1 3/5 1/5 1/5 0 0 0 0 x5 24 0 9 (16) 1 1 0 0 (M x7 7/5 0 (1/5 3/5 (2/5 0 (1 1 OBJ= 18(7M/5 zj ( 10 6+M/5 2(3M/5 2+2M/5 0 M (M cj - zj 0 9(M/5 10+3M/5 (2(2M/5 0 (M 0 Cj ( 10 15 12 0 0 0 (M CB XB b x1 x2 x3 x4 x5 x6 x7 10 x1 3/2 1 39/80 0 3/10 (1/10 0 0 12 x3 3/2 0 9/16 1 1/20 3/20 0 0 (M x7 1/2 0 (43/80 0 11/20 (7/20 (1 1 OBJ= 33(M/2 zj ( 10 93/8+ 43M/80 12 21/8+ 7M/16 5/8+ 3M/80 M (M cj - zj 0 27/8 (43M/80 0 (21/8 (7M/16 (5/8 (3M/80 (M 0 答：最后单纯形表中检验数都小于等于0，已满足最优解判定条件，但人工变量x7仍未迭代出去，可知原问题无可行解(无解)。 No.3 线性规划的对偶问题 1、写出下列线性规划问题的对偶问题： (1) 解：对偶问题为 (2) 解：原问题的约束条件可改写为右式 令改写后约束条件每行对应的对偶变量为y1,...,y6，则有对偶规划如下： 第二种解法：将原问题的约束条件该写为 并令 则原问题改写为下左式，并有对偶问题如下式， 2、写出下问题的对偶问题，解对偶问题，并证明原问题无可行解 解：对偶问题为 约束条件标准化为 有对偶问题解的单纯形表如下： Cj ( 1 (1 1 0 0 CB YB b y1 y2 y3 y4 y5 0 y4 4 (1 0 1 1 0 0 y5 3 (1 (1) (2 0 1 OBJ= 0 zj ( 0 0 0 0 0 zj ( cj (1 1 (1 0 0 Cj ( 1 (1 1 0 0 CB YB b y1 y2 y3 y y5 0 y4 4 (1 0 (1) 1 0 (1 y2 3 (1 1 (2 0 1 OBJ= (3 zj ( 1 (1 2 0 (1 zj ( cj 0 0 1 0 (1 Cj ( 1 (1 1 0 0 CB YB b y1 y2 y3 y4 y5 1 y3 4 (1 0 1 1 0 (1 y2 11 (3 1 0 2 1 OBJ= (7 zj ( 2 (1 1 (1 (1 zj ( cj 1 0 0 (1 (1 ( 入变量 答：迭代到第三步，x1为入变量，但主列中技术系数全为负值，故对偶问题有可行解但解无界，由弱对偶定理推论可知，原问题无可行解。 3、用对偶单纯形法求下面问题 解： Cj ( 4 6 0 0 min{( zj - cj)/ai*j} CB XB b x1 x2 x3 x4 ai*j<0 0 x3 (80 (1 ((2) 1 0 {4,3*} 0 x4 (75 (3 (1 0 1 OBJ= 0 zj ( 0 0 0 0 zj - cj (4 (6 0 0 Cj ( 4 6 0 0 CB XB b x1 x2 x3 x4 6 x2 40 1/2 1 (1/2 0 0 x4 (35 ((5/2) 0 (1/2 1 {2/5*,6} OBJ= 240 zj ( 3 6 (3 0 zj - cj (1 0 (3 0 Cj ( 4 6 0 0 CB XB b x1 x2 x3 x4 6 x2 33 0 1 (3/5 1/5 4 x1 14 1 0 1/5 (2/5 OBJ= 254 zj ( 4 6 (14/5 (2/5 zj - cj 0 0 (14/5 (2/5 答：最优解为x1 =14，x2 =33，目标函数值为254。 No.4 线性规划的灵敏度 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 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) q1 =11, q2 =0, q3 = (1。 (2) x1 , x2 为基变量，故 x3 为非基变量，故 (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 解：(1) 西北角法 20 5 15 10 25 15 30 30 OBJ＝1415 (2) 最低费用法 20 x14 30 15 10 15 25 5 30 (2) 差额法 5 15 30 15 25 25 5 30 OBJ＝850 OBJ＝955 ( 运费表 (检验数zij |wij ) 0 6 0 9 4 (15) 8 1 5 4 -7 10 -7 6 -3 12 8 -6 7 (3 5 6 5 9 20 6 9 9 2 2 13 6 17 14 3 6 (4 (4 0 11 (3 迭代后的分配表{xij } 5 15 30 15 25 25 5 30 OBJ＝850 运费表 (检验数zij |wij ) 0 6 0 9 4 8 1 5 4 0 10 0 6 4 12 8 1 7 4 5 6 5 9 13 20 6 9 9 2 2 13 6 10 14 3 6 (4 (4 0 4 (3 答：x13=5, x14=15, x24=30, x32=15, x33=25, x41=25, x43=5, x45=30, OBJ=850。 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 解：变换效率矩阵如下： 3 3 5 3 逐 (0) 0* 2 0* 逐 (0) 0* 2 0* 3 2 5 2 行 1 0 3 0 列 1 (0) 3 0* 1 5 1 6 (标 0* 4 (0) 5 (标 0* 4 (0) 5 4 6 4 10 记 0* 2 0* 6 记 0* 2 0* 6 每行每列都有两个以上的0 未找到最优解 (4 (0) 0* 2 0* 重 0* (0) 2 0* (8 1 (0) 3 0* 新 1 0* 3 (0) (5 0* 4 (0) 5 (标 0* 4 (0) 5 (1 0* 2 0* 6 记 (0) 2 0* 6 (2 (6 (3 (7 划线过程(发现有4条直线) 找到最优解 答：容易看出，共有四个最优解：①甲(B，乙(D，丙(A，丁(C； ②甲(D，乙(B，丙(A，丁(C；③甲(B，乙(D，丙(C，丁(A；④甲(D，乙(B，丙(C，丁(A；OBJ=10。 下面是用匈亚利算法求解的过程： ( ( 1 2 1 2 * 0 3 3 5 3 0 3 (2) 5 2 0 (1) 5 1 6 * 0 4 6 4 10 slack 2 1 3 1 nbour 1 1 4 1 S*=0.5 ( ( 1.5 2.5 1.5 2.5 0.5 3 3 5 (3) -0.5 3 (2) 5 2 -0.5 (1) 5 1 6 * 0.5 4 6 4 10 slack 2 3 2 7 nbour 4 4 4 4 S*=1 ( ( 2.5 3.5 2.5 3.5 -0.5 3 3 5 (3) -1.5 3 (2) 5 2 -1.5 (1) 5 1 6 1.5 4 6 (4) 10 slack nbour 第一个最优解：OBJ＝10 ( ( 2.5 3.5 2.5 3.5 -0.5 3 3 5 (3) -1.5 3 (2) 5 2 -1.5 1 5 (1) 6 1.5 (4) 6 4 10 slack nbour 第二个最优解：OBJ＝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 解：变换效率矩阵为适用于min化问题，用96减去上面矩阵中所有元素值， 7 4 28 15 逐 3 0 24 11 逐 3 (0) 17 11 (3 9 8 31 18 行 1 0 23 10 列 1 0* 16 10 (1 1 6 11 24 (变 0 5 10 23 (变 (0) 5 3 23 21 18 7 0 换 21 18 7 0 换 21 18 (0) 0* (2 2 (0) 16 10 (5 2 (0) 13 7 答： A (物理 (0) 0* 15 9 (3 (0) 0* 12 6 B (数学 OBJ= 0* 6 3 23 (1 0* 6 (0) 20 C (化学 360 21 19 (0) 0* 24 22 0* (0) D (外语 (2 (4 No.7 动态规划 1、某公司有9个推销员在全国三个不同市场里推销货物，这三个市场里推销员人数与收益的关系如下表，做出各市场推销人员数的分配 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，使总收益最大。 推销员 市场 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 解：令分配到各地区的推销员人数为决策变量xk ，k=1,2,3代表第1、2、3地区；令各地区可供分配的推销员人数为状态变量sk 。最先分配给第1地区，然后第2、第3地区，则 s1=9。 状态转移 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 为：sk+1 = sk (xk ； 目标函数为： 第1阶段：第3地区， s3 有0～9种可能，由收益表第3行可知d(x3)单调增，故有x3 *= s3；列表如下： x3*= s3 0 1 2 3 4 5 6 7 8 9 f1* 50 61 72 84 97 109 120 131 140 150 第2阶段：第2地区，s2 仍有0～9种可能，列表如下： x2 0 1 2 3 4 5 6 7 8 9 x2* f2* s2 0 90* 0 90 1 101* 100 0 101 2 112* 111 110 0 112 3 124* 122 121 121 0 124 4 137* 134 132 132 132 0 137 5 149* 147 144 143 143 143 0 149 6 160* 159 157 155 154 154 154 0 160 7 171* 170 169 168 166 165 165 165 0 171 8 180 181* 180 180 179 177 176 176 175 1 181 9 190 190 191* 191* 191* 190 188 187 186 185 2,3,4 191 s3 9 8 7 6 5 4 3 2 1 0 第3阶段：第1地区，由s1 =9， 列表如下： x1 s1 0 1 2 3 4 5 6 7 8 9 x1* f3* 9 211 213 218* 217 215 208 206 202 201 200 2 218 s2 9 8 7 6 5 4 3 2 1 0 答：第1地区分配2名推销员，第2 地区不分配人员，第3地区分配7名推销员，总收益为218。 2、设某工厂要在一台机器上生产两种产品，机器的总运转时间为5小时。生产这两种产品的任何一件都需占用机器一小时。设两种产品的售价与产品产量成线性关系，分别为(12(x1)和(13(2x2)。这里x1和x2分别为两种产品的产量。假设两种产品的生产费用分别是4x1和3x2，问如何安排两种产品的生产量使该机器在5小时内获利最大。(要求用连续变量的动态规划方法求解) 解：设可用机时为状态si，先分配产品1机时，故有状态转移方程 sk+1 = sk (xk (i =1,2) 边界值 s1 =5, s3=0 目标函数为： 由边界条件s3 = s2 (x2 =0，得 x2 = s2，因此有 则动态规划总效果的递推方程为 由状态方程 s2 = s1 (x1 ＝5(x1，代入上式得 令 ，解得 x1 =3。因此， 答：最优策略为第1种产品生产3件，第二种产品生产2件，5小时内最大利润为27元。 No.8 最短路问题 1、求下图中v1到所有点的最短路径及其长度。(要求最短路用双线在图中标出，保留图中的标记值) 解：最短路及其长度如图中粗线和节点上永久标记所示， 2、将上图看作无向图，写出边权邻接矩阵，用Prim算法求最大生成树，并画出该树图。 解：由图可得邻接矩阵，由Prim 算法的最大生成树如下图， 1 2 3 4 5 6 7 8 (1 1 1 (4) (3 2 1 5 3 (5) (2 3 4 (5) 1 2 (6 4 3 1 6 3 (7) (4 5 5 (6) (7) (5 6 3 7 2 1 (7 7 2 7 2 (5) (8 8 1 5 答：最大生成树的权值为39。 No.9 网络流问题 1、求下面网络s到t的最大流和最小截，从给定的可行流开始标号法。(要求每得到一个可行流后，即每次增广之后，重新画一个图，标上增广后的可行流，再进行标号法) 解： EMBED Visio.Drawing.3 答：最大流为15，最小割截为 No.10 随机服务系统：输入过程 1、对一服务系统进行观察，总观察时间为102.7分钟，到达系统的累计人数为40人，顾客累计的排队等待时间为44.8分钟，顾客累计的服务时间为79.6分钟，求 (1)系统中平均排队长度； (2)平均同时接受服务的人数。 解：总观察时间为T=102.7分钟，累计到达人数40，故 (t = 40/T=0.3895人/分钟 由题意可知 由little公式， (1) =44.8/102.7=0.436 (2) =79.6/102.7=0.775 答：平均排队队长0.436人，平均同时接受服务的人数为0.775人。 2、某选举站对甲、乙二人进行选举，选票中只能选其中一人才有效。假设投票的人流服从泊松分布，投甲票的人的到达率为(1 =4人/小时，投乙票的人的到达率为(2 =2人/小时；再假设所有投票人的票都是有效的，而选举结果的统计是在一个与选民不见面的屋里与投票过程同时进行的。问选举开始后半小时统计结果为： (1)甲得三票，乙得1票的概率； (2)总票数为5的概率； (3)甲得全票的概率。 解：(1)假设投甲、乙票的人流不相关，则有 P甲3(1/2)P乙1(1/2)= =0.066； (2) ； (3) 甲得全票的事件为投乙票的人一个未来而投甲票的人至少来一个，即 P乙0(1(P甲0)= 。 No.11 随机服务系统：标准服务系统 1、某自动交换台有4条外线，打外线的呼叫强度为2次/分钟，为泊松流，平均通话时长为2分钟。当4条外线全忙时，用户呼叫将遇忙音。假设用户遇忙音后立即停止呼叫。问 (1)用户拨外线遇忙的概率为多大？ (2)一小时内损失的话务量为多少？ (3)外线的利用率为多少？(4)过负荷为100%时，外线的利用率为多少？ 解：已知损失制系统，n=4，(=2次/分钟， 分钟，( = 4erl， (1) 遇忙的概率为B=p4 =0.31； (2) 一小时内损失的话务量＝( B =1.24erl； (3) 外线利用率为 。 (4) 过负荷100%时，外线利用率为 。 2、某车间机器发生故障为一泊松流，平均4台/小时。车间只有一名维修工，平均7分钟处理一台故障。若为该维修工增加一特殊工具可使平均故障处理时间降到5分钟，但这一特殊工具的使用费用为5元/分钟。机器故障停工每台每分钟损失5元，问购置这台特殊工具是否合适？ 解：该系统可认为是M/M/1无限源等待制，已知 (=4台/小时， 分钟， 分钟； 、 分别为增加特殊工具前后修复一台机器故障的平均用时。 先求增加特殊工具前后每台机器的平均故障停机历时(等待时间＋维修时间)，由单服务员等待系统的平均队长公式有： 由Little公式得， =0.875/4=0.21875(小时)=13.125分钟， =0. 5/4=0.125(小时)=7.5分钟， 则不引入特殊工具时每台故障的总费用为 C1=5(Wd1=65.625元； 而引入特殊工具时每台故障的总费用为 C2=5(Wh+5(Wd2=62. 5元； 答：购置特殊工具是合适的。 3、有M/M/n：(/(/FIFO(先到先服务)系统，输入业务量为(，求 当n=1, 2 , 3时的等待概率D，和平均逗留队长Ld 的公式。 解：由爱尔兰等待公式 , 和 有 n=1时，D=(，Ld= ； n=2时，D= ，Ld= ； n=3时，D= ，Ld= 。 No.12 随机服务系统：特殊服务系统 1、下面是四个点间的双向业务量矩阵{fij}和距离矩阵{dij} {fij} 1 2 3 4 1 － 5 6 4 2 5 － 2 0 3 6 2 － 1.5 4 4 0 1.5 － {dij} 1 2 3 4 1 0 1 1 1 2 1 0 1 2 3 1 1 0 1 4 1 2 1 0 所谓双向业务量fij，它表示i呼叫j的业务量与j呼叫i的业务量之和，因此有fij＝fji。根据双向业务量所得的网路是无向网路，各点间的电路群都是双向电路，可同时为电路两端的用户呼叫服务。假设每条电路单位长度的费用为1单位，汇接局的交换机每条电路接口费用为1单位。 (1)根据业务量矩阵求最佳的骨干线路网，并求骨干线路各点间线束容量(电路数)，要求各线束的呼损小于0.01，并计算全网费用。 (2)若在不存在骨干电路的点对间开设独立的直达电路群，计算此时网路中各点对间的线束容量及全网费用，仍要求各线束的呼损小于0.01。 (3)若在不存在骨干电路的点对间开设高效直达电路群，其呼损小于0.3，计算此时网路中各点对间的线束容量及全网费用，要求骨干线束的呼损小于0.01。 解： (1)由流量矩阵{fij}可得最大生成树如下图，显然节点1为汇接局，该树为星形结构，即为骨干电路，点间路由表如下矩阵所示。 1 2 3 4 1 1-2 1-3 1-4 2 2-1-3 2-1-4 3 3-1-4 4 由路由表可计算骨干电路上的双向业务流量： F12=f12+f23+f24=5+2+0=7erl, F13=f13+f23+f43=6+2=1.5=9.5erl, F14=f14+f24+f34=4+0+1.5=5.5erl 该网路结构是完全的汇接制，骨干电路仍是全利用度的，根据B<0.01的服务等级要求，查爱尔兰损失表可得 n12=14, n13=17, n14=12， 由此可计算出全网费用为 C1 =2(14+17+12)=86。 (2) 若在节点(2-3)和(3-4)间开独立的直达电路，网路如下图，只有节点(2-4)间需转接，但f24=0，故该网中没有转接业务量。 查表结果 (Fij, nij) 标于图上。由此可计算出全网费用为 C2 =2 (11+13+10)＋(7+6)=81。 (3) 若在节点(2-3)和(3-4)间开高效直达电路，网路结构仍如上图，但骨干电路(1-2), (1-3), (1-4)上存在节点(2-3)和(3-4)间的溢流，由此它是一个部分利用度系统，需要利用Wilkinson等效流理论来作计算。首先计算高效电路，因为它们是全利用度的，由B<0.3，查表得 n23=3, n34=3 求(2,3)和(3,4)的溢出话务量，有 同理有 下面求(1-2),(1-3),(1-4)上的等效流和所需电路数， ①骨干电路(1,2) n12上的业务流为 等效流为 查表 得n+N=12，故 N=12(0.3114=11.6886，取 N=12，即 n12=12。 ②骨干电路(1,4) n14上的业务流为 等效流为 查表 得n+N=10，取 N=10，即 n14=10。 ③骨干电路(1,3)，(有两个溢流) n13上的业务流为 等效流为 查表 得n+N=14，取 N=14，即 n13=14。 所得网路配置入右图，骨干电路上标的是(Aw ,(w2)及电路数。全网费用为 C3 =2(12+14+10)+(3+3)=78 答：经比较设置高效电路的网路配置最优。 No.13 存储论 1、某工厂每年需某种原料1000kg，一次定购费为200元，定购量Q与单价k的关系为 0 ( Q < 500kg， k1 =2元/kg 500 ( Q < 1000kg， k2 =1.5元/kg 1000 ( Q, k3 =1.2元/kg 已知原料存储费也与Q有关 0 ( Q < 500kg， Cs1 =2元/kg.年 500 ( Q < 1000kg， Cs2 =1.5元/kg.年 1000kg ( Q, Cs3 =1.2元/kg.年 求最佳订货量Qm，并求该订货量下的全年总费用C(Qm)。 解：已知D=1000公斤/年，Cd =200元，Cs 如题意； (1) 用公式 先求Q01, Q02, Q03， < 500公斤，(落入该批量价区间) < 1000公斤, (落入该批量价区间) < 1000公斤, (落在该批量价区间外) (2) 计费各方案年费用Ci ，因为Q01, Q02都落入各自适用批量价区间，故 元 元 而按第三批量段购买，最少购买1000公斤，故 元 答：最佳订货量为每次1000公斤，全年总费用(含购料费)为2000元。 习题课1 1、某工厂生产用2单位A和1单位B混合而成的成品出售，市场无限制。A和B可以在该工厂的3个车间中的任何车间生产，生产每单位的A和B在各车间消耗的工时如下表。 工时消耗 车间1 车间2 车间3 A 2 1 1.5 B 1 2 1.5 可用工时 100 120 100 试建立使成品数量最大的线性规划模型。 解：设车间1生产x1A单位A、生产x1B单位B； 设车间2生产x2A单位A、生产x2B单位B； 设车间3生产x3A单位A、生产x3B单位B； 则有生产安排最优化的模型如下： 这是一个可分解的线性规划，这类问题就容易出现退化现象。 2、某饮料工厂按照一定的配方将A、B、C三种原料配成三种饮料出售。配方规定了这三种饮料中A和C的极限成分，具体见下表， 饮料品种 规 格 每升售价(元) 需求量 甲 (1) A≥60％，C≤20％ 6.80 1500 乙 (2) A≥15％，C≤60％ 5.70 3000 丙 (3) C≤50％ 4.50 无限制 A、B、C三种原料每月的供应量和每升的价格如下表。 供应量(升/月) 价格(元/升) A 2000 7.00 B 2500 5.00 C 1200 4.00 饮料甲、乙、丙分别由不同比例的A、B、C调兑而成，设调兑后不同成分的体积不变，求最大收益的生产方案。 解：设x1A为饮料甲中A的总含量 (升)，设x2A为饮料乙中A的总含量 (升) 设x1B为饮料甲中B的总含量 (升)，设x2B为饮料乙中B的总含量 (升) 设x1C为饮料甲中C的总含量 (升)，设x2C为饮料乙中C的总含量 (升) 设x3A为饮料丙中A的总含量 (升)， 设x3B为饮料丙中B的总含量 (升) 设x3C为饮料丙中C的总含量 (升) 则有模型如下： 3、将下列线性规划化为标准形式 4、求上题的对偶规划。 习题课2 1．用连续型动态规划求解下题 解：设分配顺序为x1, x2, x3，三阶段与分配顺序一致，逆向运算。 由约束条件有状态转移方程：Sk=Sk-1/xk-1 第三阶段：边界条件为S4=1，所以有 ， 第二阶段：S3= S2/x2， ， 第一阶段：S2= S1/x1=27/x1， ， 回溯得： 。 答：最优解为x1=3, x2=3, x3=3，min f* =9。 2．求下面网络的中心和中位点（图中每条边上标的是两点间的距离）。 解：先求所有点间的最短距离矩阵，如右下表： Max ( 5 7 12 12 15 15 51 5 3 8 8 10 10 34 7 3 5 5 7 7* 27* 12 8 5 4 2 12 31 12 8 5 4 6 12 35 15 10 7 2 6 15 40 根据中心和中位点的定义和最大最小原则可知节点3既是中心又是中位点。 3．存货问题 （1）某小型超市洗发水日销售量为几何分布 px=p(1–p)x, x=0,1,2,…。缺货损失费为每瓶1元，当日售不出去经计算损失0.1元，若p=0.5，问最佳日进货量为多少？ （2）某小型超市食用油日销售量为负指数分布，日均销售量统计值为100公斤，当a=1, b=0.25，求最佳日进货量。 （3）若食用油日销售量为正态分布，均值为100，方差49，a, b同上，求最佳日进货量。 标准正态分布表： Z ((Z) Z ((Z) 0.00 0.500000 0.75 0.773373 0.50 0.691463 0.80 0.788145 0.60 0.725747 0.85 0.802338 0.70 0.758036 0.90 0.815940 解： （1）由几何分布公式，可得离散概率和累积概率如下表： 日销量 i 0 1 2 3 概率Pi 0.5 0.25 0.125 0.0625 累积概率Fi 0.5 0.75 0.875 0.9375 临界比： a/(a+b)=0.9091 答：最佳日进3瓶洗发水。 （2）由负指数分布和日均销售量100公斤，可知有概率分布 临界比： a/(a+b)=1/1.25=0.8，解 答：最佳日进160.94公斤食用油。 （3）由正态分布， 查表得 Z ( 0.85，x=100+7(0.85=105.95 答：最佳日进105.95公斤食用油。 * * * � EMBED Visio.Drawing.4 ��� _922381398.unknown _947386849.unknown _947387846.unknown _983370494.unknown _983372145.unknown _983374698.unknown _983375153.unknown _983383505.unknown _983384278.unknown _1021958901.unknown _983383952.unknown _983375610.unknown _983374965.unknown _983374194.unknown _983374440.unknown _983374146.unknown _983370531.unknown _983370563.unknown _983370498.unknown _983370156.unknown _983370182.unknown _983370186.unknown _983370463.unknown _983370171.unknown _983366181.unknown _983368160.unknown _983368917.unknown _983367313.unknown _983091284.vsd _983360632.unknown _983086918.unknown _947386985.unknown _947387567.unknown _947387790.unknown _947387838.unknown _947387573.unknown _947387510.unknown _947387561.unknown _947387519.unknown _947387501.unknown _947386907.unknown _947386929.unknown _947386941.unknown _947386920.unknown _947386872.unknown _947386879.unknown _947386865.unknown _922512817.unknown _922518022.vsd _945929735.unknown _945930349.unknown _945930626.unknown _922520205.unknown _922514210.unknown _922515052.unknown _922515053.unknown _922515690.vsd _922514211.unknown _922515050.unknown _922514209.unknown _922510732.unknown _922512025.unknown _922512276.unknown _922511597.unknown _922382720.unknown _922428059.vsd _922429904.vsd _922383335.unknown _922383548.unknown _922383565.unknown _922382770.unknown _922382355.unknown _922382581.unknown _922381400.unknown _922263523.unknown _922379484.unknown _922381143.unknown _922381305.unknown _922381328.unknown _922381248.unknown _922379993.unknown _922380717.unknown _922379805.unknown _922378936.unknown _922379027.unknown _922379050.unknown _922378989.unknown _922378434.unknown _922378697.unknown _922263736.unknown _922090656.unknown _922259374.vsd _922260781.unknown _922262491.unknown _922262907.unknown _922259697.vsd _922254939.vsd _922257336.vsd _922120379.unknown _921953227.unknown _921954027.unknown _922082754.vsd _922082753.vsd _921953527.unknown _920446820.unknown _921952901.unknown _920446625.unknown