运筹学模拟卷

运筹学模拟卷一、填空题：1.下面为一线性规划模型(Max型)迭代过程中的某一单纯形表，表中CB列表示对应基变量的价值系数。C行表示各变量的价值系数。要求：()()()()()4()11/202-1206()01/21-1130-Z0-30-2-2-260⑴把单纯形表中的空格补充完整。⑵基本可行解为：X*=( )T⑶目标函数值为：Z=( )。⑷当前基本可行解是否是最优解。( )［注：填是或不是］2.已知某线性规划问题用单纯形法计算时得到的初始单纯形表及最终单纯形表见下表，请将表中空白处数字填上。cj2-11000C XxxxxxxbJ0 x4311100600 x51-12010100 x11-100120 6 -Z2-1100000 x4()()1()-1-2()2 x1()()0.5()1/21/2()()七()()-1.5()-1/21/2()-Z()()()()()()()1.(4)(2)(6)(0)(0)4(x1)102-1206(x)01-1130-Z0-30-2-2-260⑴单纯形表填空如上表示。⑵基本可行解为：X*=(20,0,30,0,0)t⑶目标函数值为：Z=(260)。⑷是2.已知某线性规划问题用单纯形法计算时得到的初始单纯形表及最终单纯形表见下表，请将表中空白处数字填上。cj2-11000CXxxxxxxb B 0 B x4x5 1 32131 4 150 6 06001-12010100x11-100120-Z——6 2-1100000x4(0)(0)1(1)-1-2(10)

2x1(1)(0)0.5(0)1/21/2(15)(-1)x2(0)(1)-1.5(0)-1/21/2(5)-Z(0)(0)(-1.5)(0)(-1.5)(-0.5)(-25)注：计算方法如下：（1） 单纯形表中基变量的系数列向量为单位列向量，检验数为0。TOC\o"1-5"\h\z"1 -1 -2一（2）从最终单纯形表中抄出最优基的逆矩阵 Bt=01/21/2，根据单纯形表的计算公式0-1/21/2P=B-1p，X=B-1b,R=c-CP分别算出单纯形表中x的系数列向量、检验数和基变量的值。j jB jjBj j二、计算题：maxz=3x+5xx<41 2对于线性规划模型十］2x<12 ，请先把模型化成标准型，然后用单纯形表迭代求其最优解。st-|3x2+2x<181 2、八x,x,x>0v1 2 3解：添加松驰变量x3，x4，x5把模型化成标准型：maxz=3x+5x1 2x+x=42X2+x4=12 （5分）3x+2x+x=18x.>0（j=1,...5）单纯形表迭代过程如下：（每一单纯形表各占6分,其中正确写出基变量1分,b列1分,其余计算4分）cj35000CBXBx1x2x3x4x5be0x3101004—0x40[2]010126-►0x s. 32001189-Z3叶00000x310100445x20101/206—0[3]00-116x52 .-Z3t00-5/20-300x30011/3-1/325x20101/2063x1100-1/31/32-Z000-3/2-1-36TOC\o"1-5"\h\z最优解为：X=（xx,x,x,x）T=（2,6,2,0,0）t， Z=36\o"CurrentDocument"1，2 3 4 5某建筑工地每月需求水泥量为1200吨，每吨定价为1500元，不允许缺货。设每吨每月的存储费为价格的2%，每次订货费为1800元，需要提前7天订货。试求经济订购批量、每月总费用和再订货点。解：Ch=30（元/吨-月），Co=1800（元/次），R=1200（吨/月）

2RC故2X2RC故2X1200X1800=379.5(吨)30最小费用：f*=、：2RC匕=、J2X1200x30X1800=11384.2(元/月),再订货点：L=RT=1200X7930=280吨。3.已知某运输问题的供输关系及单位运价表如下表示:-_产地销地__BB 2 B 3 产量A4258A23537A 3 1324需求量4851）列出产销平衡表，并用行列差值法给出该运输问题的初始基可行解。2） 用位势法求初始可行解对应的各非基变量的检验数。3） 求出该运输问题的最优解。解.①产大于销，增添假想销地B4,列出产销平衡表（3分），用行列差值法给初始解（5分）如下表示:~~~--- 销地产地 〜 _B1B2B3B4产量行差值A4（X）2(8)5（X）0(X)82,2,3A 2 3（X）5(0)3(5)0(2)73,0,2A1(4)3（X）2(0)0(X)41,1,-需求量4852列差值2,2,-1,1,31,1,22,-②用位势法求初始可行解对应的各非基变量的检验数:对基变量有：Ri.=cij—（ui+vj）=0,求出行、列位势，如表示:〜—销地产地B1B2B3B4产量行位势气4(X)2(8)5(X)0(X)8u=0a23(X)5(0)3(5)0(2)7 1 u=3 2 A31(4)3(X)2(0)0(X)4u3=2J需求量4852列位势V=—1 -4 v2=2v=0v=—3 ③选为入基量，作闭路调整，整量为如表示：再次利—（u+v.）x32变7'一一一、销地产地f'-ffB1B2B3B4行位势回A4(X)2(8)5(X)0(X)u=0调 1 A3(X)5(X)③选为入基量，作闭路调整，整量为如表示：再次利—（u+v.）x32变7'一一一、销地产地f'-ffB1B2B3B4行位势回A4(X)2(8)5(X)0(X)u=0调 1 A3(X)5(X)3(5)0(2) 1 u=20, 2 A1(4)3(0)2(0)0(X) 2 u=13列位势v1=0v2=2v3=1v=—2 4 3用R..=c..求出非基变量的检验数：R=4,R=4,R=2,R=1,R=1,R=1。11 13 14 21 22 34当前调运方案为最优方案，如上表示，最小运费Z=2X8+3X5+1X4=35。4.求下面网络节点1到节点7的最短路径。解：用t、P标号算法：给v点标P标号，从v点出发，修改（v）,T（v）=6得P标号的点v2'出,v5改为P标V2他点标!T标号，为+8解：用t、P标号算法：给v点标P标号，从v点出发，修改（v）,T（v）=6得P标号的点v2'出,v5改为P标V2他点标!T标号，为+8。

'点的T标号一

v4》=：5=--p（v,）。（2分）

发，可达-v.一一.一号。（2分4+d}=n2Lr{6,4+1}=5=P（v）④依此类推，各点的P标号如图所示。（ …1T(v2)③从刚I把最小T标号T(v)=min{6,3 2八3、、、门

v、v、v

^，V（土分把其P标号。4,。、一八/ 1 〉V_3v5（与其相邻的且还未获得p标号的点），修改其T标号，并23—v5—v7或v1—v?V2V1V不口个P标号点各占2分）；告-距离为16。（2分）从v1到v7的最短路为:—v2—V3\ 6 /5^6L 卜3厂L1____14v485.已知线性规划问题其对偶问题的最优解为：写出该问题的对偶I命应用对偶规划的性质，求原问题的最优解。y*=4,v*/1V 5L4，要求:解：（1）其对偶问题为：minW=8y+12y1 2叫+2y2>22y2>1yi+y2>5y+2y>612〔yj>0,j=1,2.9V6-（2分）（2分）（1分）（2分）（2分）（1分）（2）设对偶问题的松驰变量为y，y，y，y，把y*=4,y*=1代入对偶问题中的约束方程，知y力0,ys1s2s3s4 1 2 S1 s2NO，由互补松驰性有：X]=x2=0。又由y1*=4,yf=1，均不等于0，由互补松驰性知原问题的两个约束对应的松驰变量xs1=0,xs2=0,则原问题约束方程可化为：l3：4—匚，解得x=4,x=4。[x+2x=12 3 4即原问题最优解为：X*=（0,0,4,4）t，Z=44。6.某公司打算在三个不同的地区设置4个销售点，根据市场预测部门估计，在不同的地区设置不同数量的销售店，每月可得到的利润如表1所示。试问在各个地区应如何设置销售点，才能使每月获得的总利润最大？其彳 地区\销售店■利润01234101625303220121721223010141617解：设给每一个地区设置一个销售点为一个阶段，共三个阶段。

\为给第k个地区设置的销售点数。Sk^第k阶段还剩余的销售点数，S1=4状态转移方程为：Sk+i=Sk-xkdk(xk)为在第k个地区设置xk个销售点增加利润。最优指标函数fk(Sk)为第k阶段把Sk个销售点时分给第k、k+1,...3个销售点获取的最大收益。指标函数递推方程：f(S)max{f(S)d(S,x)},k=2,1 边界方程为:kk k1k1kkkxkf(S)d(S,x)。3 3 3 3 3逆推计算如下:k=3时：S3=逆推计算如下:k=3时：S3=x3 _x3012340000110101214142316163417174k=2时:爻=S2—x2x201234000010+1012+012120+1412+1017+022130+1612+1417+1021+027240+1712+1617+1421+1022+0312或3k=1时:：S2=S]—X]x20123440+3116+2725+2230+1232+0472最优决策方案为：第一个地区设置2个销售点，第二个地区设置1个销售点，第三个地区设置1个销售点，每月可获总利润为47。7.设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可选择，而进口港又有三个可选择，进口后可经由两个城市到达目的地，其间的运输费用如图所示(单位：百元)，试把该问题描述成一个多阶段决策问题，并用动态规划方法求解。解：按决策的过程分为四个状态变量Sk为第k阶 —….、\为第叫阶段的决策变量，状态;阶段指标函数々(Sk7040 /方程为：S当)为Sk至3(xJSk溢20C解：按决策的过程分为四个状态变量Sk为第k阶 —….、\为第叫阶段的决策变量，状态;阶段指标函数々(Sk7040 /方程为：S当)为Sk至3(xJSk溢20C110k值。一程：f(S)>U kkd点E的最短指标函数递:边界方程为：匕捋下面列表计算如下:B3in4(f (s、k1/xk 、、、、>',')。"'■ 50K+1 %'k，¥ '离直，阚尤指标函数，'d：(S4<DJ，为备火阶段状态为sk时，/\30

k，x^

30/=3,2,140C30D2k=4时，出发点有D1、D2,分别计算由各状态到终点的最短路径值：s\4IS,u)f4(S4)u4ED 1 3030ED 2 4040Ek=3时，出发点有C,、C、C。三个，分别计算由各状态到终点的最短路径值，如表示:J 2 2—7d3(S3,u3)+5f3(S3)u3D 1 D 2 C 1 10+3040+4040D 1 C 2 60+3030+4070D 2 C 3 30+3030+4060D -4 k=2时，状态集合为：S2={B1,B2,B3},分别计算由各状态到终点的最短路径