中南大学现代远程教育平台—运筹学课程作业答案.doc

1、1运筹学作业答案作业一一、是非题：1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。 （）2.线性规划问题的每一个基解对应可行解域的一个顶点。 （）3.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。 （）4.用单纯形法求解 Max 型的线性规划问题时，检验数 Rj0 对应的变量都可以被选作入基变量。 （）5.单 纯 形 法 计 算 中 ， 如 果 不 按 最 小 比 值 规 划 选 出 基 变 量 ， 则 在 下 一 个 解 中 至 少 有 一 个 基 变 量 的 值 为 负 。（）6.线性规划问题的可行解如为最优解，则该可行解一定是基可行解。 （）7

2、.若线性规划问题具有可行解，且可行解域有界，则该线性规划问题最多具有有限个数的最优解。 （）8.对一个有 n 个变量，m 个约束的标准型线性规划问题，其可行域的顶点数恰好为 个。 （）mnC9.一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 （）10.求 Max 型的单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解。 （）二、线性规划建模题：1.某公司一营业部每天需从 A、B 两仓库提货用于销售，需提取的商品有：甲商品不少于 240 件，乙商品不少于 80 台，丙商品不少于 120 吨。已知：从 A 仓库每部汽车每天能运回

3、营业部甲商品 4 件，乙商品 2 台，丙商品 6 吨，运费 200 元/每部；从 B 仓库每部汽车每天能运回营业部甲商品 7 件，乙商品 2 台，丙商品 2 吨，运费 160 元/每部。问：为满足销售量需要，营业部每天应发往 A、B 两仓库各多少部汽车，并使总运费最少？解：设营业部每天应发往 A、B 两仓库各 x1，x2 部汽车,则有：1212min0647860(,)jWxx2.现有一家公司准备制定一个广告宣传计划来宣传开发的新产品，以使尽可能多的未来顾客特别是女顾客得知。现可利用的广告渠道有电视、广播和报纸，根据市场调查整理得到下面的数据：电 视项目一般时间 黄金时间 广播 报纸每个广告单

4、元的费用(元)每个广告单元所接触的顾客数(万人)每个广告单元所接触的女顾客数(万人)40004030700090403000502015002010该企业计划用于此项广告宣传的经费预算是80万元，此外要求：至少有200万人次妇女接触广告宣传；电视广告费用不得超过50万元,2电视广告至少占用三个单元一般时间和两个单元黄金时间,广播和报纸广告单元均不少于5个单元而不超过10个单元。解：设电视一般时间、黄金时间、广播和报纸各投放广告单元数为x1，x2，x3，x4，有： 12341234234max40950.7.83.510(,.)Zxxxxj三、计算题：对于线性规划模型1212jma34 68 x

5、0(=,)z1.用图解法求出其所有基本解，并指出其中的基本可行解和最优解。2.三个方程中分别添加松驰变量 x3,x4,x5 后把模型化成标准型，用单纯形法寻求最优解。并与 1 题中图解法中对照，单纯形表中的基可行解分别对应哪些顶点。3.若直接取最优基 ，请用单纯形表的理论公式进行计算对应基 B 的单纯形表，并与第 2125,BP题最优单纯形表的计算结果比较是否一致。 （附单纯形表的理论公式：非基变量 xj 的系数列向量由 Pj变成 基变量的值为 ，目标函数的值为 ，检验数公-1jjp ， 1BXb10 BZCXb式 ） 。jjjBRCP解：（1）图解如下：3所有基本可行解：O（0,0） ，Q

6、1（6,0） ，Q 2（4,2） ，Q 3（2,3） ，Q 4（0,3）共五个基可行解。从上图知：最优解为点 Q2（4,2） ，目标函数值为 Z20。（2）模型标准化为： 1212345jmax6 8() += x0(jzx 一 切单纯形法表迭代过程如下表示：cj 3 4 0 0 0CB XB x1 x2 x3 x4 x5 b 000x3x4x51 1 1 0 0 1 2 0 1 00 1 0 0 16836 出基8-Z 3 4 0 0 0 06262300x1x4x51 1 1 0 0 0 1 -1 1 00 1 0 0 1 3 3Z 0 1 -3 0 0 18340x1x2x51 0 2

7、-1 00 1 -1 1 00 0 1 -1 1421Z 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）若取基 ，基变量为 x1,x2,x5，刚好是最优表中的对应基变量，可125B=P,0算出 （从第三个单纯形表也可找到 B1 ） ，由单纯形表计算公式计算非基-1-变量的系数列向量、检验数及基解等。4， ，32-1021P4-101P。125-608231BxX，33(,4)BRcCP4410(3,)BRcC

8、P与迭代的第三个单纯形表计算结果一致。四、写出下列线性规划问题的对偶问题。 123312231Min Z=5x+4 78 - 60 x,自 由 变 量解：设三个方程的对偶变量分别为 y1,y2,y3，有：12123123ma85054760,Wyyy为 自 由 变 量五、有一个 Max 型的线性规划问题具有四个非负变量，三个“”型的条件，其最优表格如下表，请写出其对偶问题的最优解及目标函数值。解：该问题的松驰变量为 x5,x6,x7，由对偶规划的性质知三个对偶变量的值分别为 x5,x6,x7检验数的负值，目标函数值与原问题相等。故 ， W34/3。12341Y=(y,)(,0)六、求下列运输问

9、题的解：XB x1 x2 x3 x4 x5 x6 x7 bx4x6x10 1 2/3 1 2/3 0 -1/30 2 -1 0 0 1 01 1 1/3 0 1/3 0 1/3 14/3410/3-Z 0 -2 -4/3 0 -4/3 0 -1/3 -34/35销 地产 地 B1 B2 B3 供应量A1 6 4 2 4A2 8 5 7 5需求量 3 3 3用表上作业法求解此问题的最优解。 （要求用行列差值法给初始解，用位势法求检验数。 ）解：（1）这是一个产销平衡的运输问题，用行列差值法给初始解：销 地产 地 B1 B2 B3 行差值 供应量A1 6（1） 4（） 2（3） 2,2 4A2 8

10、（2） 5（3） 7（） 2,3 5列差值 2,2 1,1 5需求量 3 3 3（2）用位势法求检验数：对基变量有： ()0ijijijRcuv,并令 u1=0，求出行列位势，如下表。各非基变量的检验数分别为：R 12=4(3+0)=1， R 23=7(3+2)=2，即基变量的检验数都大于 0，当前方案为最优调运方案。作业二一、用隐枚举法求解下面 01 型整数规划问题：10,4253.321213或xxtsZMax解：问题为求极大型，需所有的变量前的价值系数变为负号，故令 ，模型变12,1xx为：销 地产 地 B1 B2 B3 行位势 vi 供应量A1 6（1） 4（） 2（3） u1=0 4

11、A2 8（2） 5（3） 7（） u2=2 5列位势 vj v1=6 v2=3 v3=2需求量 3 3 36，231123123() (4. )1(4,0MaxZxstx或用目标函数值探索法求最大值：是否满足约束方程jcx1 x2 x3 (1) (2) (3) （4） Z01000100 32从表中可以看出，当 时具最大目标函数值，即 ，23,xx13,0,xxZmax2。二、某服装厂有五项工作需要分给五个技工去完成，组成分派问题，各技工完成各项工作的能力评分如下表所示。请问应如何分派，才能使总得分最大？解：（1）效率矩阵为：，问题是求极大，转化为求极小问题，设.30.801.12.3. 2.

12、5.4.090.61ijc ，14ijijbc 工作 评分人员 B1平车 B2考克 B3卷边 B4绷缝 B5打眼A1 1.3 0.8 0 0 1.0A2 0 1.2 1.3 1.3 0A3 1.0 0 0 1.2 0A4 0 1.05 0 0.2 1.4A5 1.0 0.9 0.6 0 1.17构造以 bij为系数的矩阵，0.1.6.41.0.4420.2.350.81.40.3ijb （2）对 bij矩阵进行系数变换，使每行每列出现 0 元素，0.41.3.31.3012.2.2.5.00.ijb （3）进行试分配：，()0.41.3.31.312.2(0).2.5.0.ijb （4）作最少

13、的直线覆盖所有的 0 元素：().41.3.0.31.3102.2().2.5.0.ijb （5）在没有被覆盖的部分中找出最小数 0.1，则第四、五行减去这个最小数 0.1，同时第五列加上这个最小数，其他元素不变，目的是增加 0 元素的个数。0.41.3.41.3012.2.3.5.00.4ijb （6）试分配：8，此时，所有的 0 都已打括号或划掉，且打(0).41.3.0.41.3(0)12.2.3.5.()().4ijb 括号的 0 元素（独立的 0 元素）个数刚好为 5 个，得到了问题的最优解，问题的解矩阵为：，即 A1做平车，A 2做卷边，A 3做绷缝，A 4做打眼，A 5做考克，1

14、001ijx总得分为 6.1。三、某厂从国外引进一台设备，由工厂 A 至 G 港口有多条通路可供选择，其路线及费用如图 1 所示。现要确定一条从 A 到 G 的使总运费最小的路线，请将该问题描述成一个动态规划问题，然后求其最优解。解：把问题分为 4 个阶段，如图 1 示。设 Sk为每一阶段的起点，x k为第 k 阶段的决策变量，状态转移方程为：S K+1x k(Sk)。k=1,2,3,4。阶段指标函数 为 Sk到 xk(Sk)的距离值，最优指标函数 fk(Sk)为第 k 阶段状态为 Sk时，(,)kd从 Sk到终点 G 的最短距离值。指标函数递推方程：，k=3,2,11()min()(,)kk

15、kxff边界方程为： 。44,SdA B1 C2 G20 30 图 1B2 C1C3 D11D217060 50 400 0 30403010第一阶段 第二阶段 第三阶段 第四阶段9下面列表计算如下：k=4 时：k=3 时： 34(,)(dSxfx3S3D1 D2 3()fSx4C1 0+30 30 D1C2 4030 3040 70 D1或 D2C3 040 40 D2k=2 时： 23(,)(dSxfx2S2C1 C2 C3 2()fSx4B1 70+30 60+70 100 C1B2 1070 5040 80 C2k=1 时： 12(,)(dSxfx1S1B1 B21()fSx4A 20

16、+100 3080 110 B2最优路线有两条：AB 2C 2D 1G 或 AB 2C 2D 2G，最短距离值为 110。四、某公司打算在三个不同的地区设置 4 个销售点，根据市场预测部门估计，在不同的地区设置不同数量的销售店，每月可得到的利润如表 1 所示。试问在各个地区应如何设置销售点，才能使每月获得的总利润最大？其值是多少?表 1销售店利润地区0 1 2 3 41 0 16 25 30 322 0 12 17 21 223 0 10 14 16 17解：设给每一个地区设置一个销售点为一个阶段，共三个阶段。xk为给第 k 个地区设置的销售点数；S k 为第 k 阶段还剩余的销售点数，S 1

17、4状态转移方程为：S k+1=Skx k dk(xk)为在第 k 个地区设置 xk个销售点增加利润最优指标函数 fk(Sk)为第 k 阶段把 Sk个销售点时分给第 k、k+1,3 个销售点获取的最大收益。指标函数递推方程： ，k=2,11(ma(,)kxfd44()(,)fSdGx4S4G 4()fSx4D1 30 30 GD2 40 40 G10边界方程为： 。33(),)fSdx逆推计算如下：k=3 时：S 3=x3 33(),)fSdxx3S30 1 2 3 43()fSx30 0 0 01 10 10 12 14 14 23 16 16 34 17 17 4k=2 时：S 3= S2x

18、 2 232(,)()dSxfxx3S30 1 2 3 42()fSx20 0 0 01 010 12+0 12 12 0+14 12+10 17+0 22 13 0+16 12+14 17+10 21+0 27 24 0+17 12+16 17+14 21+10 22+0 31 2 或 3k=1 时：S 2= S1x 1 121(,)()dSxfxx1S10 1 2 3 41()fSx24 031 1627 2522 3012 320 47 2最优决策方案为：第一个地区设置 2 个销售点，第二个地区设置 1 个销售点，第三个地区设置1 个销售点，每月可获总利润为 47。五、某厂生产一种产品，

19、该产品在未来三个月中的需要量分别为 3，4，3 万件，若生产准备费为 3 万元/次，每件成本为 1 元，每件每月存储费为 0.7 元，假定 1 月初和 4 月初存货为 0，并每月产量不限。试求该厂未来三个月内的最优生产计划？要求用动态规划求解。动态规划求解，建立如下动态规划数学模型。阶段(月份)n： 1 2 3 4状态变量 Sn：每月初库存，有 S1=0，S 2=0,1,2,3, 4,5,6,7，S 3=0,1，2,3， S 4=0。决策变量 Xn：每月的生产量据题意有决策变量的允许范围：3x 110, 0x 27, 0x 33 。状态转移方程： S n+1 = Sn +XnD n 阶段指标函数(成本)：成本=生产费用存储费用1 月 3 月 4 月2 月rn(Xn)=31X n ， X n00 ， Xn0