运筹学纸质作业答案中南大学.pdf

1 运筹学运筹学作业作业答案答案 作业一作业一 一、一、是非题：是非题： 1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。 （） 2.线性规划问题的每一个基解对应可行解域的一个顶点。 （） 3.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。 （） 4.用单纯形法求解 Max 型的线性规划问题时，检验数 Rj0 对应的变量都可以被选作入基变量。 （） 5.单纯形法计算中， 如果不按最小比值规划选出基变量， 则在下一个解中至少有一个基变量的值为负。 （） 6.线性规划问题的可行解如为最优解，则该可行解一定是基可行解。 （） 7.若线性规划问题具有可行解，且可行解域有界，则该线性规划问题最多具有有限个数的最优解。 （） 8.对一个有 n 个变量，m 个约束的标准型线性规划问题，其可行域的顶点数恰好为 m nC 个。 （） 9.一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影 响计算结果。 （） 10.求 Max 型的单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解。 （） 二、二、线性规划建模题：线性规划建模题： 1.某公司一营业部每天需从 A、B 两仓库提货用于销售，需提取的商品有：甲商品不少于 240 件，乙商品 不少于 80 台，丙商品不少于 120 吨。已知：从 A 仓库每部汽车每天能运回营业部甲商品 4 件，乙商品 2 台，丙商品 6 吨，运费 200 元/每部；从 B 仓库每部汽车每天能运回营业部甲商品 7 件，乙商品 2 台， 丙商品 2 吨，运费 160 元/每部。问：为满足销售量需要，营业部每天应发往 A、B 两仓库各多少部汽 车，并使总运费最少？ 解：设营业部每天应发往 A、B 两仓库各 x1，x2 部汽车,则有： 12 12 12 12 min200160 47240 2280 62120 0(1,2) j Wxx xx xx xx xj 2.现有一家公司准备制定一个广告宣传计划来宣传开发的新产品，以使尽可能多的未来顾客特别是女顾 客得知。现可利用的广告渠道有电视、广播和报纸，根据市场调查整理得到下面的数据： 项目 电 视 广播 报纸 一般时间 黄金时间 每个广告单元的费用(元) 每个广告单元所接触的顾客数(万人) 每个广告单元所接触的女顾客数(万人) 4000 40 30 7000 90 40 3000 50 20 1500 20 10 该企业计划用于此项广告宣传的经费预算是80万元，此外要求： 至少有200万人次妇女接触广告宣传；电视广告费用不得超过50万元, 电视广告至少占用三个单元一般时间和两个单元黄金时间, 广播和报纸广告单元均不少于5个单元而不超过10个单元。 2 解：设电视一般时间、黄金时间、广播和报纸各投放广告单元数为x1，x2，x3，x4，有： 1234 1234 1234 12 1 2 3 4 max40905020 0.40.70.30.1580 30402010200 0.40.750 3 2 510 510 0(1,.4) Zxxxx xxxx xxxx xx x x x x xjj 三、三、计算题计算题： 对于线性规划模型 12 12 12 2 j max34 6 28 x3 x0(j=1,2) zxx xx xx 1.用图解法求出其所有基本解，并指出其中的基本可行解和最优解。 2.三个方程中分别添加松驰变量 x3,x4,x5 后把模型化成标准型，用单纯形法寻求最优解。并与 1 题中图 解法中对照，单纯形表中的基可行解分别对应哪些顶点。 3.若直接取最优基 125 ,BP P P ，请用单纯形表的理论公式进行计算对应基 B 的单纯形表，并与第 2 题 最优单纯形表的计算结果比较是否一致。 （附单纯形表的理论公式：非基变量 xj 的系数列向量由 Pj 变 成 -1 jj pB p ， 基变量的值为 1 B XB b ，目标函数的值为 1 0 BBB ZC XC B b ，检验数公式 j jjB RCC P ） 。 解： （1）图解如下： 3 所有基本可行解：O（0,0） ，Q1（6,0） ，Q2（4,2） ，Q3（2,3） ，Q4（0,3）共五个基可行解。 从上图知：最优解为点 Q2（4,2） ，目标函数值为 Z20。 （2）模型标准化为： 12 123 124 25 j max34 6 28 (2) x +x =3 (3) x0(j) zxx xxx xxx (1) 一切 单纯形法表迭代过程如下表示： cj 3 4 0 0 0 CB XB x1 x2 x3 x4 x5 b 0 0 0 x3 x4 x5 1 1 1 0 0 1 2 0 1 0 0 1 0 0 1 6 8 3 6 出基 8 - Z 3 4 0 0 0 0 3 0 0 x1 x4 x5 1 1 1 0 0 0 1 -1 1 0 0 1 0 0 1 6 2 6 2 3 3 Z 0 1 -3 0 0 18 3 4 0 x1 x2 x5 1 0 2 -1 0 0 1 -1 1 0 0 0 1 -1 1 4 2 1 Z 0 0 -2 -1 0 -20 从上表知： 表一中的基可行解 （0,0,6,8,3） 对应坐标原点 O， 表二中的基可行解为 （6,0,0,2,3） 对应图中的 Q1点，表三中的基可行解为（4,2,0,0,1）对应图中的 Q2点，得到最优解。 （3）若取基 125 110 B = P,P ,P120 011 ，基变量为 x1,x2,x5，刚好是最优表中的对应基变量，可 算出 -1 2-10 B-110 1-11 （从第三个单纯形表也可找到 B 1） ，由单纯形表计算公式计算非基变 量的系数列向量、检验数及基解等。 3 2-1012 -11001 1-1101 P ，4 2-1001 -11011 1-1101 P ， 4 1 2 5 2-1064 -11082 1-1131 B x Xx x 。 333 2 0(3,4,0)12 1 B RcC P ， 444 1 0(3,4,0) 11 1 B RcC P 与迭代的第三个单纯形表计算结果一致。 四四、写出下列线性规划问题的对偶问题。写出下列线性规划问题的对偶问题。 123 13 123 23 231 Min Z = 5x +4x + 3x 2x +7x 8 8x +5x -4x 15 4x + 6x = 30 x ,x0,x 自由变量 解：设三个方程的对偶变量分别为 y1,y2,y3，有： 123 12 23 123 123 max81530 285 544 7463 0,0, Wyyy yy yy yyy yyy 为自由变量 五五、有一个、有一个 MaxMax 型的线性规划问题具有四个非负变量，三个“”型的条件，其最优表格如下表，请写出型的线性规划问题具有四个非负变量，三个“”型的条件，其最优表格如下表，请写出 其对偶问题的最优解及目标函数值。其对偶问题的最优解及目标函数值。 解：该问题的松驰变量为 x5,x6,x7，由对偶规划的性质知三个对偶变量的值分别为 x5,x6,x7检验数的负 值，目标函数值与原问题相等。故 123 41 Y=(y ,y ,y )=(,0, ) 33 ， W34/3。 六六、求下列运输问题的解、求下列运输问题的解： 销 地 产 地 B1 B2 B3 供应量 A1 6 4 2 4 A2 8 5 7 5 需求量 3 3 3 XB x1 x2 x3 x4 x5 x6 x7 b x4 x6 x1 0 1 2/3 1 2/3 0 -1/3 0 2 -1 0 0 1 0 1 1 1/3 0 1/3 0 1/3 14/3 4 10/3 -Z 0 -2 -4/3 0 -4/3 0 -1/3 -34/3 5 用表上作业法求解此问题的最优解。 （要求用行列差值法给初始解，用位势法求检验数。 ） 解： （1）这是一个产销平衡的运输问题，用行列差值法给初始解： 销 地 产 地 B1 B2 B3 行差值 供应量 A1 6（1） 4（） 2（3） 2,2 4 A2 8（2） 5（3） 7（） 2,3 5 列差值 2,2 1,1 5 需求量 3 3 3 （2）用位势法求检验数：对基变量有： ()0 ijijij Rcuv ,并令 u1=0，求出行列位势，如下 表。 各非基变量的检验数分别为：R12=4(3+0)=1， R23=7(3+2)=2，即基变量的检验数 都大于 0，当前方案为最优调运方案。 作业二作业二 一、用隐枚举法求解下面一、用隐枚举法求解下面 0 01 1 型整数规划问题：型整数规划问题： 10, 44 22 54 23 . . 2 321 321 321 32 321 321 或xxx xxx xxx xx xxx ts xxxZMax 解： 问题为求极大型，需所有的变量前的价值系数变为负号， 故令 1122 1,1xxxx ， 模型变为： 231 123 23 123 123 123 3(2) 32 (1) 41 (2) . . 21 (3) 41 (4) ,01 MaxZxxx xxx xx stxxx xxx xxx 或 ， 销 地 产 地 B1 B2 B3 行位势 vi 供应量 A1 6（1） 4（） 2（3） u1=0 4 A2 8（2） 5（3） 7（） u2=2 5 列位势 vj v1=6 v2=3 v3=2 需求量 3 3 3 6 用目标函数值探索法求最大值： j c x1 x2 x3 是否满足约束方程 Z (1) (2) (3) （4） 0 1 0 0 0 1 0 0 3 2 从表中可以看出， 当 123 0,1,0xxx时具最大目标函数值， 即 123 1,0,0xxx， Zmax2。 二、二、某服装厂有五项工作需要分给五个技工去完成，组成分派问题，各技工完成各项工作的能力评分如下 表所示。请问应如何分派，才能使总得分最大？ 解： （1）效率矩阵为： 1.30.8001.0 01.21.31.30 1.0001.20 01.0500.21.4 1.00.90.601.1 ij c ， 问题是求极大， 转化为求极小问题， 设1.4 ijij bc， 构造以 bij为系数的矩阵， 0.10.61.41.40.4 1.40.20.10.11.4 0.41.41.40.21.4 1.40.351.41.20 0.40.50.81.40.3 ij b （2）对 bij矩阵进行系数变换，使每行每列出现 0 元素， 00.41.31.30.3 1.30001.3 0.21.11.201.2 1.40.251.41.20 0.10.10.51.10 ij b 工作 评分 人员 B1 平车 B2 考克 B3 卷边 B4 绷缝 B5 打眼 A1 1.3 0.8 0 0 1.0 A2 0 1.2 1.3 1.3 0 A3 1.0 0 0 1.2 0 A4 0 1.05 0 0.2 1.4 A5 1.0 0.9 0.6 0 1.1 7 （3）进行试分配： (0)0.41.31.30.3 1.3(0)1.3 0.21.11.2(0)1.2 1.40.251.41.2(0) 0.10.10.51.1 ij b ， （4）作最少的直线覆盖所有的 0 元素： (0)0.41.31.30.3 1.3(0)1.3 0.21.11.2(0)1.2 1.40.251.41.2(0) 0.10.10.51.1 ij b （5）在没有被覆盖的部分中找出最小数 0.1，则第四、五行减去这个最小数 0.1，同时第五列加 上这个最小数，其他元素不变，目的是增加 0 元素的个数。 00.41.31.30.4 1.30001.4 0.21.11.201.3 1.30.151.31.10 000.41.00 ij b （6）试分配： (0)0.41.31.30.4 1.3(0)1.4 0.21.11.2(0)1.3 1.30.151.31.1(0) (0)0.41.0 ij b ，此时，所有的 0 都已打括号或划掉，且打括 号的 0 元素（独立的 0 元素）个数刚好为 5 个，得到了问题的最优解，问题的解矩阵为： 10000 00100 00010 00001 01000 ij x ，即 A1做平车，A2做卷边，A3做绷缝，A4做打眼，A5做考克，总 得分为 6.1。 8 三、三、某厂从国外引进一台设备，由工厂 A 至 G 港口有多条通路可供选择，其路线及费用如图 1 所示。现要 确定一条从 A 到 G 的使总运费最小的路线，请将该问题描述成一个动态规划问题，然后求其最优解。 解：把问题分为 4 个阶段，如图 1 示。 设 Sk为每一阶段的起点， xk为第 k 阶段的决策变量， 状态转移方程为： SK+1xk(Sk)。 k=1,2,3,4。 阶段指标函数(,) kkk dSx为 Sk到 xk(Sk)的距离值，最优指标函数 fk(Sk)为第 k 阶段状态为 Sk时， 从Sk到终点G的最短距离值。 指标函数递推方程： 11 ()min()(,) k kkkkkkk x fSfSdSx ， k=3,2,1 边界方程为： 4444 ()(,)fSdS G。 下面列表计算如下： k=4 时： k=3 时： x3 S3 33344 (,)()d S xfS 33 ()f S x4 D1 D2 C1 0+30 30 D1 C2 4030 3040 70 D1或 D2 C3 040 40 D2 k=2 时： x2 S2 22233 (,)()d Sxf S 22 ()fS x4 C1 C2 C3 B1 70+30 60+70 100 C1 B2 1070 5040 80 C2 k=1 时： x4 S4 4444 ()(,)fSdS G 44 ()fS x4 G D1 30 30 G D2 40 40 G A B1 C2 G 20 30 图 1 B2 C1 C3 D1 D2 70 60 50 40 0 0 30 40 30 10 第一阶段 第二阶段 第三阶段 第四阶段 9 x1 S1 11122 (,)()d S xfS 11 ()f S x4 B1 B2 A 20+100 3080 110 B2 最优路线有两条：AB2C2D1G 或 AB2C2D2G，最短距离值为 110。 四、四、某公司打算在三个不同的地区设置 4 个销售点，根据市场预测部门估计，在不同的地区设置不同数量 的销售店，每月可得到的利润如表 1 所示。试问在各个地区应如何设置销售点，才能使每月获得的总 利润最大？其值是多少? 表 1 销售店 利润 地区 0 1 2 3 4 1 0 16 25 30 32 2 0 12 17 21 22 3 0 10 14 16 17 解：设给每一个地区设置一个销售点为一个阶段，共三个阶段。 xk为给第 k 个地区设置的销售点数；Sk 为第 k 阶段还剩余的销售点数，S14 状态转移方程为：Sk+1=Skxk dk(xk)为在第 k 个地区设置 xk个销售点增加利润 最优指标函数 fk(Sk)为第 k 阶段把 Sk个销售点时分给第 k、k+1,3 个销售点获取的最大收益。 指标函数递推方程： 11 ()max()(,) k kkkkkkk x fSfSdSx ，k=2,1 边界方程为： 33333 ()(,)f Sd S x。 逆推计算如下： k=3 时：S3=x3 x3 S3 33333 ()(,)f Sd S x 33 ()f S x3 0 1 2 3 4 0 0 0 0 1 10 10 1 2 14 14 2 3 16 16 3 4 17 17 4 k=2 时：S3= S2x2 x3 S3 222322 (,)()dSxf Sx 22 ()fS x2 0 1 2 3 4 0 0 0 0 1 010 12+0 12 1 2 0+14 12+10 17+0 22 1 3 0+16 12+14 17+10 21+0 27 2 4 0+17 12+16 17+14 21+10 22+0 31 2 或 3 10 k=1 时：S2= S1x1 x1 S1 111211 (,)()d S xfSx 11 ()f S x2 0 1 2 3 4 4 031 1627 2522 3012 320 47 2 最优决策方案为：第一个地区设置 2 个销售点，第二个地区设置 1 个销售点，第三个地区设置 1 个销售点，每月可获总利润为 47。 五、五、某厂生产一种产品，该产品在未来三个月中的需要量分别为 3，4，3 万件，若生产准备费为 3 万元/ 次，每件成本为 1 元，每件每月存储费为 0.7 元，假定 1 月初和 4 月初存货为 0，并每月产量不限。 试求该厂未来三个月内的最优生产计划？要求用动态规划求解。 动态规划求解，建立如下动态规划数学模型。 阶段(月份)n： 1 2 3 4 状态变量 Sn：每月初库存，有 S1=0，S2=0,1,2,3, 4,5,6,7，S3=0,1，2,3， S4=0。 决策变量 Xn：每月的生产量 据题意有决策变量的允许范围：3x110, 0x27, 0x33 。 状态转移方程： Sn+1 = Sn +XnD n 阶段指标函数(成本)：成本=生产费用存储费用 递推方程： )()()( 1 * 1 0 * nnnn DxS x nn SfxrMinSf nnn nn ， 1 , 2 n ),()( 333 0 3 * 3 333 3 yxrMinSf DxS x 下面利用表格进行计算，从最后一个阶段开始： n=3 时： 此时 S3+X3D3=0，即 X3=3S3 n=2 时： 此时 S2+X22=4，即 X24S2；S3 = S2 +X2D2，即S3 = S2 +X24 X3 S3 r3(X3) f3(S3) X3 * 0 1 2 3 0 6+0=6 6 3 1 5+0.7=5.7 5.7 2 2 4+1.4=5.4 5.4 1 3 0+2.1=2.1 2.1 0 1 月 3 月 4 月 2 月 rn(Xn)= 31Xn ， Xn0 0 ， Xn0 0.7Sn 11 X 2 S2 r2(X2)+ f3 (S3) f2 (S2) X2 0 1 2 3 4 5 6 7 0 7+6 8+5.7 9+5.4 10+2.1 12.1 7 1 6.7+6 7.7+5.7 8.7+5.4 9.7+2.1 11.8 6 2 6.4+6 7.4+5.7 8.4+5.4 9.4+2.1 11.6 5 3 6.1+6 7.1+5.7 8.1+5.4 9.1+2.1 11.2 4 4 2.8+6 6.8+5.7 7.8+5.4 8.8+2.1 8.8 0 5 3.5+5.7 7.5+5.4 8.5+2.1 9.2 0 6 4.2+5.4 8.2+2.1 9.6 0 7 4.9+2.1 7 0 n=1 时： X13S1；S2 = S1 +X1D1，即S2 = S1 +X13 X1 S1 r1(X1)+ f2 (S2) f1 (S1) X1 * 0 1 2 3 4 5 6 7 0 6+12.1 7+11.8 8+11.6 9+11.2 10+8.8 18.1 3 由此可知：S1=0，此时 X1 *=3； S 2 = S1+X1 *3=033=0，此时 X 2 *=7； S3 = S2+X2 *4=074=3，此时 X 3 *=0。 最优策略为：X *=x 1*，x2*，x3*=3，7，0 Z *=f 1 *(S 1)=18.1 即第一个月生产 3 万件，第二个月生产 7 万件，第三个月生产 0 万件，可使总成本最低为 18.1 万元。 作业三（图与网络分析、存贮论部分）作业三（图与网络分析、存贮论部分） 一、 判断题判断题： 1.图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、 点与点连线的长短曲直等都要严格注意。 （） 2.在任一图 G 中，当点集 V 确定后，树图是 G 中边数最少的连通图。 （） 3.如图中某点 vi 有若干个相邻点，与其距离最远的相邻点为 vj，则边vi,vj必不包含在最小支撑树内。 （） 4.在任一连通图 G 中，点数为 N，则保证这 N 点相互连通且任意两点间仅有一条链相通的图一定含有 N 1 条边。 （） 5.求网络最大流问题可归结为求解一个线性规划问题。 （） 6.订购费为每订一次货所发生的费用，它同每次订货的数量无关。 （） 7.在同一存贮模型中，可能既发生存贮费用，又发生短缺费用。 （） 8.在允许缺货发生短缺的存贮模型中，订货批量的确定应使由于存贮量的减少带来的节约能抵消缺货时 造成的损失。 （） 9.当订货数量超过一定的值允许打折扣的情况下，打折扣条件下的订货批量要大于不打折扣时的订货批 量。 （） 10.在其他费用不变的情况下，随着单位存贮费用的增加，最优订货批量也相应增大。 （） 二、求图二、求图 1 1 中的最小树中的最小树： 5 v1 v2 v3 v4 v6 6 5 4 5 6 2 3 4 12 解：用破圈法求得的最小部分树为： 最小部分树的权为：13+33+24+521。 三、求图三、求图 2 2 中从点中从点 v v1 1到其余各点的最短路到其余各点的最短路： 解：用 T、P 标号算法： 1.给 v1点标 P 标号，其他点标 T 标号，为。 2.从 v1点出发，修改 v2、v3点的 T 标号，并把其中最小者改为 P 标号。 T(v2)=3，T(v3)=2P（v3） 。 3.从刚刚获得 P 标号的点 v3 出发，可达 v2,v4,v5,修改 T 标号，并把最小者改为 P 标号。 4.依此类推，各点的 P 标号如图 2 所示。从 v1到 v7的最短路为：v1 v3v5v7，距离为 8。 四、求图四、求图 3 3 中网络的最大流、最大流的流量和最小割。中网络的最大流、最大流的流量和最小割。 v2 v4 v1 v3 v5 v7 3 2 5 1 3 8 2 7 3 6 图 2 v1 v2 v3 v4 v6 v7 v8 v5 4 2 3 3 3 1 5 0 2 3 4 5 8 13 解：最大流如图示： 仅有起点 v1可标号，最小割为 min121314 ( ,),( ,),( ,)Sv vv vv v，最大流流量为 17。 五、计算题五、计算题： 1.设需要某物品 12 件/天，不允许缺货，存贮费率为 0.02 元/件一天。为满足需要，可以采取订购或自 行组织生产。有关数据如下： 订购 自行生产 提前期或生产准备期 8 天 13 天 物品单位 11