中南大学现代远程教育平台—运筹学课程作业答案
-标准化文件发布号:(9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII
《运筹学》作业答案
作业一
一、是非题:
1.图解法与单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的。(√) 2.线性规划问题的每一个基解对应可行解域的一个顶点。(╳)
3.如果线性规划问题存在最优解,则最优解一定可以在可行解域的顶点上获得。(√)
4.用单纯形法求解Max型的线性规划问题时,检验数Rj>0对应的变量都可以被选作入基变量。(√) 5.单纯形法计算中,如果不按最小比值规划选出基变量,则在下一个解中至少有一个基变量的值为负。(√)
6.线性规划问题的可行解如为最优解,则该可行解一定是基可行解。(╳)
7.若线性规划问题具有可行解,且可行解域有界,则该线性规划问题最多具有有限个数的最优解。(╳)
8.对一个有n个变量,m个约束的标准型线性规划问题,其可行域的顶点数恰好为Cn个。(╳) 9.一旦一个人工变量在迭代中变为非基变量后,该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果。(√)
10.求Max型的单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解。(√)
二、线性规划建模题:
m
1.某公司一营业部每天需从A、B两仓库提货用于销售,需提取的商品有:甲商品不少于240件,乙商品不少于80台,丙商品不少于120吨。已知:从A仓库每部汽车每天能运回营业部甲商品4件,乙商品2台,丙商品6吨,运费200元/每部;从B仓库每部汽车每天能运回营业部甲商品7件,乙商品2台,丙商品2吨,运费160元/每部。问:为满足销售量需要,营业部每天应发往A、B两仓库各多少部汽车,并使总运费最少?
minW?200x1?160x2?4x1?7x2?240?解:设营业部每天应发往A、B两仓库各x1,x2部汽车,则有:?2x1?2x2?80??6x1?2x2?120?xj?0(j?1,2)?
1
2.现有一家公司准备制定一个广告宣传计划来宣传开发的新产品,以使尽可能多的未来顾客特别是女顾客得知。现可利用的广告渠道有电视、广播和报纸,根据市场调查整理得到下面的数据:
项目 每个广告单元的费用(元) 每个广告单元所接触的顾客数(万人) 每个广告单元所接触的女顾客数(万人) 电 视 一般时黄金时间 间 4000 40 30 7000 90 40 广播 报纸 3000 50 20 1500 20 10 该企业计划用于此项广告宣传的经费预算是80万元,此外要求:
①至少有200万人次妇女接触广告宣传;②电视广告费用不得超过50万元, ③电视广告至少占用三个单元一般时间和两个单元黄金时间, ④广播和报纸广告单元均不少于5个单元而不超过10个单元。
解:设电视一般时间、黄金时间、广播和报纸各投放广告单元数为x1,x2,x3,x4,有:
maxZ?40x1?90x2?50x3?20x4?0.4x1?0.7x2?0.3x3?0.15x4?80?30x?40x?20x?10x?200234?1?0.4x1?0.7x2?50? ?x1?3??x2?2?5?x3?10??5?x4?10?xj?0(j?1,...4)?
三、计算题:
2
maxz?3x1?4x2?x1?x2? 6?对于线性规划模型?x1?2x2?8?? x2?3?xj?0(j=1,2)?
1.用图解法求出其所有基本解,并指出其中的基本可行解和最优解。
2.三个方程中分别添加松驰变量x3,x4,x5后把模型化成标准型,用单纯形法寻求最优解。并与1题中图解法中对照,单纯形表中的基可行解分别对应哪些顶点。 3.若直接取最优基
B?[P1,P2,P5],请用单纯形表的理论公式进行计算对应基B的单纯形
表,并与第2题最优单纯形表的计算结果比较是否一致。(附单纯形表的理论公式:非
pj?B-1pj ,XB?B?1b基变量xj的系数列向量由Pj变成基变量的值为,目标函数的值为
Z0?CBXB?CBB?1b,检验数公式
Rj?Cj?CBPj)。
解:(1)图解如下:
所有基本可行解:O(0,0),Q1(6,0),Q2(4,2),Q3(2,3),Q4
(0,3)共五个基可行解。
从上图知:最优解为点Q2(4,2),目标函数值为Z=20。
(2)模型标准化为:
3
maxz?3x1?4x2?x1?x2?x3?6 (1) ??x1?2x2?x4?8 (2) ?? x2+x5=3 (3)?xj?0(一切j)?单纯形法表迭代过程如下表示:
cj CB XB 0 0 0 x3 x4 x5 -Z x1 x4 x5 -Z 3 4 0 x1 x2 x5 -Z 3 4 0 0 0 x1 x2 x3 x4 x5 [1] 1 1 0 0 1 2 0 1 0 0 1 0 0 1 3 4 0 0 0 1 1 1 0 0 0 [1] -1 1 0 0 1 0 0 1 0 1 -3 0 0 1 0 2 -1 0 0 1 -1 1 0 0 0 1 -1 1 0 0 -2 -1 0 b 6 8 3 0 6 2 3 -18 4 2 1 -20 θ 6 出基 8 - 6 2 3 3 0 0 从上表知:表一中的基可行解(0,0,6,8,3)对应坐标原点O,表二中的基可行解为(6,0,0,2,3)对应图中的Q1点,表三中的基可行解为(4,2,0,0,1)对应图中的Q2点,得到最优解。
?110??,基变量为x,x,x,刚好是最优表中的对应基120(3)若取基B=?P1,P2,P5???125
????011???2-10??(从第三个单纯形表也可找到B-1),由单纯形-110变量,可算出B-1??????1-11??表计算公式计算非基变量的系数列向量、检验数及基解等。
4