运筹学模拟卷

1、 运筹学模拟卷一、填空题：1.下面为一线性规划模型（Max型）迭代过程中的某一单纯形表，表中CB列表示对应基变量的价值系数。Cj行表示各变量的价值系数。要求：（ ）（ ）（ ）（ ）（ ）4（ ）11/202-1206（ ）01/21-1130-Z0-30-2-2-260把单纯形表中的空格补充完整。基本可行解为：X*（ ）T目标函数值为：Z（ ）。当前基本可行解是否是最优解。（ ）注：填是或不是2.已知某线性规划问题用单纯形法计算时得到的初始单纯形表及最终单纯形表见下表，请将表中空白处数字填上。cj 2 -1 1 0 0 0CBXB x1 x2 x3 x4 x5 x6b000x4x5 x6 3

2、 1 1 1 0 0 1 -1 2 0 1 0 1 1 -1 0 0 1601020-Z 2 -1 1 0 0 000x4( ) ( ) 1 ( ) -1 -2( )2x1( ) ( ) 0.5 ( ) 1/2 1/2( )( )x2( ) ( ) -1.5 ( ) -1/2 1/2( )-Z( ) ( ) ( ) ( ) （ ） ( )( )1.（4）（2）（6）（0）（0）4（x1）102-1206(x3)01-1130-Z0-30-2-2-260单纯形表填空如上表示。基本可行解为：X*（20,0,30,0,0）T目标函数值为：Z（260）。是2.已知某线性规划问题用单纯形法计算时得到的初

3、始单纯形表及最终单纯形表见下表，请将表中空白处数字填上。cj 2 -1 1 0 0 0CBXB x1 x2 x3 x4 x5 x6b000x4x5 x6 3 1 1 1 0 0 1 -1 2 0 1 0 1 1 -1 0 0 1601020-Z 2 -1 1 0 0 000x4（0） (0) 1 (1) -1 -2(10)2x1（1） (0) 0.5 (0) 1/2 1/2(15)(-1)x2（0） (1) -1.5 (0) -1/2 1/2(5)-Z（0） (0) (-1.5) （0） (-1.5) (-0.5 )(-25)注：计算方法如下：（1）单纯形表中基变量的系数列向量为单位列向量，检

4、验数为0。（2）从最终单纯形表中抄出最优基的逆矩阵，根据单纯形表的计算公式分别算出单纯形表中xj的系数列向量、检验数和基变量的值。二、计算题：1.对于线性规划模型，请先把模型化成标准型，然后用单纯形表迭代求其最优解。解：添加松驰变量x3,x4,x5把模型化成标准型： （5分）单纯形表迭代过程如下:(每一单纯形表各占6分,其中正确写出基变量1分,b列1分,其余计算4分)cj3 5 0 0 0CBXBx1 x2 x3 x4 x5b000x3x4x51 0 1 0 0 0 2 0 1 03 2 0 0 141218 6 9Z3 5 0 0 00050x3x2x51 0 1 0 00 1 0 1/2

5、03 0 0 -1 1 46462Z3 0 0 -5/2 030053x3x2x10 0 1 1/3 -1/30 1 0 1/2 01 0 0 -1/3 1/3262Z0 0 0 -3/2 -1-36最优解为：， Z36 2. 某建筑工地每月需求水泥量为1200吨,每吨定价为1500元,不允许缺货。设每吨每月的存储费为价格的2，每次订货费为1800元,需要提前7天订货。试求经济订购批量、每月总费用和再订货点。解：Ch30（元/吨·月），CO1800（元/次），R1200（吨/月） 故 最小费用：， 再订货点：LRTL1200×7÷30280吨。 3.已知某运输问题

6、的供输关系及单位运价表如下表示：产地 销地B1B2B3产量A14258A23537A31324需求量4851)列出产销平衡表，并用行列差值法给出该运输问题的初始基可行解。2)用位势法求初始可行解对应的各非基变量的检验数。3)求出该运输问题的最优解。解.产大于销，增添假想销地B4，列出产销平衡表(3分)，用行列差值法给初始解（5分）如下表示：销地产地B1B2B3B4产量行差值A14（）2（8）5（）0（）82,2,3A23（）5（0）3（5）0（2）73,0,2A31（4）3（）2（0）0（）41,1,-需求量4852列差值2,2,-1,1,31,1,22,-用位势法求初始可行解对应的各非基变量

7、的检验数：对基变量有：Rij=cij(ui+vj)=0，求出行、列位势，如表示：销地产地B1B2B3B4产量行位势A14（）2（8）5（）0（）8u1=0A23（）5（0）3（5）0（2）7u2=3A31（4）3（）2（0）0（）4u3=2需求量4852列位势v1=1v2=2v3=0v4=3利用Rij=cij(ui+vj)求出非基变量的检验数：R11=5，R13=5，R14=3，R21=1，R32=1，R34=1。选x32为入基变量，作闭回路调整，调整量为0，如表示：销地产地B1B2B3B4行位势A14（）2（8）5（）0（）u1=0A23（）5（）3（5）0（2）u2=2A31（4）3（0）

8、2（0）0（）u3=1列位势v1=0v2=2v3=1v4=2 再次利用Rij=cij(ui+vj)求出非基变量的检验数：R11=4，R13=4，R14=2，R21=1，R22=1，R34=1。当前调运方案为最优方案，如上表示，最小运费Z2×83×51×435。4.求下面网络节点1到节点7的最短路径。v2v3v4v6v7v14655567v541812解：用T、P标号算法：给v1点标P标号，其他点标T标号，为。（1分）从v1点出发，修改v2、v3、v4点的T标号，并把其中最小者改为P标号。T(v2)=4=P(v2)，T(v3)=6，T(v4)=5= P(v4)。（2

9、分）从刚刚获得P标号的点v2出发，可达v3,v5（与其相邻的且还未获得P标号的点）,修改其T标号，并把最小T标号v3,v5改为P标号。（2分）T(v3)=min6，p(v2)+d23=min6,4+1=5=P(v3)，T(v5)=11。依此类推，各点的P标号如图所示。（其余各个P标号点各占2分）从v1到v7的最短路为：v1 v2v3v5v7或v1 v2v3v6v5v7，距离为16。（2分）4v2v3v4v6v7v14655567v541812100516955.已知线性规划问题：其对偶问题的最优解为：，要求：写出该问题的对偶问题。应用对偶规划的性质，求原问题的最优解。（2分）（2分）（1分）（

10、2分）（2分）（1分）解：（1）其对偶问题为：（2）设对偶问题的松驰变量为ys1，ys2，ys3，ys4，把代入对偶问题中的约束方程，知ys10，ys20，由互补松驰性有：x1=x2=0。又由，均不等于0，由互补松驰性知原问题的两个约束对应的松驰变量xs10，xs20，则原问题约束方程可化为：，解得x34，x44。 即原问题最优解为：X*（0,0,4,4）T，Z44。 6.某公司打算在三个不同的地区设置4个销售点，根据市场预测部门估计，在不同的地区设置不同数量的销售店，每月可得到的利润如表1所示。试问在各个地区应如何设置销售点，才能使每月获得的总利润最大？其值是多少? 表1销售店利润地区012

11、34101625303220121721223010141617解：设给每一个地区设置一个销售点为一个阶段，共三个阶段。 xk为给第k个地区设置的销售点数。 Sk为第k阶段还剩余的销售点数，S14 状态转移方程为：Sk+1=Skxk dk(xk)为在第k个地区设置xk个销售点增加利润。 最优指标函数fk(Sk)为第k阶段把Sk个销售点时分给第k、k+1,3个销售点获取的最大收益。指标函数递推方程：，k=2,1 边界方程为：。 逆推计算如下：k=3时：S3=x3 x3S3x3012340000110101214142316163417174k=2时：S3= S2x2 x3S3x201234000

12、0101012+012120+1412+1017+022130+1612+1417+1021+027240+1712+1617+1421+1022+0312或3k=1时：S2= S1x1 x1S1x2012344031162725223012320472最优决策方案为：第一个地区设置2个销售点，第二个地区设置1个销售点，第三个地区设置1个销售点，每月可获总利润为47。 7.设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可选择，而进口港又有三个可选择，进口后可经由两个城市到达目的地，其间的运输费用如图所示（单位：百元），试把该问题描述成一个多阶段决策问题，并用动态规划方法求解。2

13、040307040203010405603030303040401050AB1B2B3C1C2C3D1D2E解：按决策的过程分为四个阶段。状态变量Sk为第k阶段的起点。xk为第k阶段的决策变量，状态转移方程为：SK+1xk(Sk)。k=1,2,3,4。阶段指标函数为Sk到xk(Sk)的距离值，最优指标函数fk(Sk)为第k阶段状态为Sk时，从Sk到终点E的最短距离值。指标函数递推方程：，k=3,2,1 边界方程为：。 下面列表计算如下：k=4时，出发点有D1、D2，分别计算由各状态到终点的最短路径值： u4S4d4(S4, u4)f4 (S4)u4ED13030ED24040Ek=3时，出发点有C1、C2、C3三个，分别计算由各状态到终点的最短路径值，如表示： u3S3d3(S3, u3)+ f4(S4)f3 (S3)u 3D1D2C110+30404040D1C260+3030+4070D2C330+3030+4060D1k=2时，状态集合为：S2B1，B2，B3，分别计算由各状态到终点的最短路径值，如表示：u2S2d2(S2, X2)+ f3 (S