运筹学II练习题

1 试判定下述非线性规划是否为凸规划：

MinfXx12x2282xx20（1）1

2x1x220x,x012MinfX2x12x22x32x1x222x1x24（2）

25x1x310x,x,x0123（3） max f(X)x1x2

2x12x2≤1s..t x1,x2≥0

MinfXx12x2282g1Xx1x20解 （1）

2g2Xx1x220x1,x20fX,g1X,g2X的海赛矩阵的行列式：

2fXx122fXx2x12g1Xx122g1Xx2x12fXx1x22fXx222g1Xx1x22g1Xx2220 02 H g1200 00 g22g2Xx122g2Xx2x12g2Xx1x22g2Xx2200 02知fX为严格凸函数，g1X,为凸函数，g2X为凹函数，所以不是一个凸规划问题。 （2）

MinfX2x12x22x32x1x2'2222g1Xx1x24g1Xx1x240 2g2X5x1x310x1,x2,x30同上有fX,g1X,g2X的海赛矩阵的行列式

410 H120

0022g120（3） min (f(X))x1x2

2g1(X)1x12x2≥0 s..tg2(X)x1≥0g(X)x≥02310,是凹函数，

g200是凸函数，不是凸规划问题。

0020Hf(X)≥0,H(X)>0,g10002

00Hg(X)Hg(X)≥02300说明f(X)是凸函数，g1(X)、g2(X)、g3(X)是凹函数。因此，本模型是一个凸规划。

2 试用斐波那契法求函数 fxx3x2

2在区间[0，10]上的极小点，要求缩短后的区间长度不大于原区间长度的8%。（1.5）

Fn1/12.5,n6;a00,b010;F5(b0a0)3.846;F6F5t1'a0(b0a0)6.154;F6f(t1)5.254;f(t1')21.409;t1b0f(t1)f(t1'),Qa10;b16.154;t2'3.846;t2b1F4(b1a1)2.308;F5f(t2)0.403;f(t2)f(t2')5.254;Qa20;b23.846;t3'2.308;F3(b2a2)1.538;F4f(t3)0.248f(t3')0.403;Qa30;b32.308;t4'1.538;F2(b3a3)0.769;F3f(t4)0.284f(t4')0.248;Qa40.769;b42.308;t51.538;F1(b4a4)1.538F22t3b2t4b3t5'a4

3 用分数法求f(t)tt2在区间[1,3]上的近似极小点，要求缩短后的区向长度不大于原区间长的8%。（0.538）

4 试用最速下降法求函数

2 fXx122x2

TT00的极大点，先以X0,0为初始点进行计算，求出极大点；再以X0,1为初始点进行两次迭代。

2最后比较从上述两个不同初始点出发的寻优过程。（2，0）

22解 求fXx122x2的极大点，即求gXx122x2的极小点。 T0（1）取初始点X0,0，取精度0.1

22gX2x2,4x,gX12T04,0T gX024202162

20HX040gXgXHXgXgX0T0T000

44,002044,0040161322X1

X100gX001420200TTgX222,400,0即X1即为极小点。

为fX的极大点。

T0 （2）取初始点X0,1，取精度0.1，同上方法进行两次迭代有：

20 两次步长 0两次迭代结果

11,1 33 X143,13X2169 19比较：对于目标函数的等值线为椭圆的问题来说，椭圆的圆心即为最小值，负梯度方向指向圆心，但初值点与圆心在同一水平直线上时，收敛很快，即尽量使搜索路径呈现较少的直角锯齿状。

5求f(X)3212Tx1x2x1x22x1的极小点，取X024。(1,1) 22解 f(X)1[x12x131x1x2][20] 11x2x2Tf(X)3x1x22x2x1

f(X0)126,P0f(X0)126

TT12[126]6P0Tf(X0)50 P0THP0311217[126]1165T2638 X1X0P024126171717TT612 f(X1)1717661217171712f(X1)Tf(X1)171 0f(X0)Tf(X0)12289[126]6T210612190 P1f(X1)0P0[126]2891717289289TP1Tf(X1)17T 1,XXP112111P1THP110由于f(X2)00，故X211即极小点，计算经两步终止。

TT6试用牛顿法求解 (0,0) MaxfXT0取初始点X4,01 22x1x22。

解 求MaxfX122的极大点，即求gXx1x22的极小点。 22x1x22g(X)2x12x2T，

g(X)80Hg(X)0T201/201，Hg(X)01/2 0241/2080X1001/200 所以极大点为 X*0,0,

TT1g(X)00 ，fX*1 27 试用共轭梯度法求二次函数 (0,0)

fX的极小点，此处

1TXAX 211 A

12 解 QA

11 12fx

1T12XAXx122x1x2x222TffTfx,xx,x2x2121xx12

T0现从X1,1，开始

fX P002,3

TfX02,3

T0fXP00TTP0AP0

22,33 1122,31231334于是

X1X00P0T113285,13433434

fX12858103,, 34343434343432343,34342341

34222,33TT 0fXfX10TfX10TfXP1fX10P0

3 34121T22104,65234334341fX11TPPAPT11T

2104653,2,234343434 T1046511104652,22,2343412343431042653434339104266513344故

X21045343420118X1P, 653434130342故得到极小值点

T2 X0,0

8考虑下面的非线性规划：

max f(X)ln(x11)x2

2x1x2≤3s..t x1,x2≥0验证它为凸规划，并用K-T条件求解。(0,3)

解 原问题可写为

min f(X)ln(x11)x2

s..tg1(X)32x1-x2≥0

g2(X)x1≥0 g3(X)x2≥0

计算目标和约束函数的海赛阵

1Hf(X)(x11)20故此问题是凸规划。

000≥0,Hg1(X)Hg2(X)Hg3(X)≤0 000－1TTTf(X)1,g1(X)21，g2(X)10，g3(X)01

x11K-T条件表达式为

1x121211-131(32x1x2)0 x0213x201,2,3≥0若10，则无解，于是10，有32x1x20

令x10,30，则有

12120 1103x02解得x10,x23,121,30，显然0

9试写出下述非线性规则的Kuhn-Tucker条件并进行求解：

2Maxfxx3 1x53是可行点，从而是极小点。

T清华版，7章例1 10求解二次规划

min f(X)12(2x122x2)8x110x2 263x12x2≥0s..t

x≥0,x≥012433 (X) 1313*T见天大版例3-16

11试解二次规划

2MinfX2x124x1x24x26x13x2xx23 1

4x1x29x,x012

解 将上述二次规划改写为

122MinfX4x8xx8x6x13x211222 3x1x20

94x1x20x1,x20可知目标函数为严格凸函数，此外

c16,b29,c23,b13,a214,c114,a221c222a121

c12c214,a111,由于c1和c2小于零，故引入的人工变量z1和z2前面取负号，这样得到线性规划问题如下

mingzz1z2y34y4y14x14x2z16yy4y24x14x2z23 3

x1x2x3304xxx90124x1,x2,x3,x4,y1,y2,y3,y4,z1,z20解此线性规划问题得

*x1*39,20*x2*z20,21,20*y32*x30,*x4*y40320

2 z10,21,5392139214413921fX*2446320202020402020

12试用SUMT外点法求解 （1，2）

MaxfXx13x22x110 3x11x220x1,x20

解 原问题转化为

minfXx13x22x1103x11x220 x01x20构造惩罚函数

23Px,Mx1Mmin0,x22x11223min0,x11x22min0,xmin0,x122P3212Mmin0,x22x11•3x11 x1322Mmin0,x11x22•3x11P32Mmin0,x22x11x21

2Mmin0,x32Mmin0,x11x222Mmin0,x2解得最优解为

X*1,2

13 一工人管2台机器，每台机器发生故障前的运转时间为具有均值为1/2小时的负指数分布，修理时间也属负指数分布，均值为1/3小时。 （1） 画出转速图。

（2） 列出平衡方程式求出状态概率P0，P1，P2。 （3） 求故障机器数的均值Ls。 （4） 一台机器每次停机时间均值Ws。

解 （1）λ1＝2台/小时，μ＝3台/小时 M/M/1/·/2 模型 2λ1＝4 λ1＝2

○0 ○1 ○2 μ＝3 μ＝3

（2）3P1＝4P0 , 5P1=4P0+3P2 , 3P2＝2P1

T4248P0， P2＝P0＝P0 333948 P0＋P1＋P2＝P0＋P0＋P0＝1

399128∴ P0 ＝ P1 ＝ P2＝

292929 P1＝

121628＋＝（台）＝0.966 292929960（4）λe＝μ（1－P0）＝3（1－）＝

2929（3）Ls＝0 P0＋1P1＋2P2＝ Ws＝

14 某风景区有一小客店，每天平均到达4人，顾客平均逗留时间为2天，到达服从泊松分布，逗留时间服从负指数分布，若该旅馆只有（C＝）2个单人房间，客房住满时再到达的顾客会离去（N＝2）。（M/M/2/2模型）

（1）画出转速图，列出平衡方程式。 （2）求空闲概率P0和满员概率P2 。 （3）求每天客房占用数的均值Ls 。 解 λ＝4人/天 μ＝1/2人/天 （1）

λ λ Lse＝

28＝0 .47（小时）＝28（分钟） 60 ○0 ○1 ○2 μ 2μ

1/2P1＝4P0 P1＝8P0 P2＝4P1 P2＝32P0

（2）1＝P0（1＋8＋32）＝41P0 P0＝1/41 P1＝8/41 P2＝32/41 （3）Ls＝

npn02n8327221.76（间） 414141空闲概率为P0＝1/41 满员概率为P2＝32/41 客房占用数均值为1.76（间）

15 某加油站有一台加油设备，加油的汽车以平均每5分钟1辆的速度到达，服从泊松分布，加油时间服从负指数分布，平均每辆车的加油时间为4分钟。试求： （1）这个加油站平均有多少辆汽车在等待加油？ （2）每辆汽车为在这里加油平均需耗费多长时间？

（3）管理部门规定，若加油的平均等待时间超过 3 分钟或系统内的平均汽车数超过8辆，则需要增加加油设备，试计算现在的情况是否需要增加加油设备？ （4）如果加油的汽车流有所变化，那么当

超过多少时需要增加加油设备？

M/M/1//152143.2(1)p010.2120(2)Ws(3)Wq3Ls8Lq0.8Ls1

4 116Wq() 需要增加加油设备；

(4)Ls82,9Wq33 28 故当λ超过（3／28）时，需要增加加油设备。

16 设ns表示系统中顾客数，nq表示队列中等候的顾客数，在单服务台系统中，我们有 nsnq1n,nsq0

试说明它们的期望值 LsLq1，而是 LsLq。根据这关系式给以直观解释。

解 因为为单服务台，只有超过1个顾客时，才会出现排队等待。

Lqn1pnn1

npnpn

n1n1Ls1p0Ls则

LsLq

17 在M/ M/ 1/N/模型中，如1，试证：下式成立 P0P...1 N1

于是 LsN/2解 在M/ M/ 1/N/模型中，其状态转移图如下：

λλλλλ0112………N-1Nμμμμμ

则pnp n1又Q1则pnpn1，依次类推 ， p0p1.....pN 又Qpn0Nn1，则

p0p1.....pn1 即

N1p01 故

p01N1Nn0NLsnpn1ngN1n01gnN1n0N

1NN1gN12N2

18 对于M/ M/ 1/N/模型，试证：

1Pn1P0

并对上式给予直观的解释。

解 设由M/ M/ 1/N/模型的数字特征有 pnp01N1故

pn1pn111 N111111PN1 p011N1当1时

p0pN显然 当1时

0N

1，N1

1pN1p0

pN即

1ppN,1pN1p01 N111N1pN1N111N1N1N1 N111pN11p011N11N1则 即

1pN1p0

1pN1p0 故

1pN1p0

由于系统的容量为N，则有效到达率为：

ep0p1...pN11pN

当系统平衡时，有效到达率和有效服务率应当相等，即

1pN1p0

19

对于M/ M/ 1/m/m模型，试证 Lsm证 由于系统的有效服务率为：

1P0，并给予直观解释。 e1p0

Ls表示系统中平均出故障的机器数，则系统外的机器平均数为mLs，则系统的有效到达率，即m台机

器单位时间内实际发生故障的平均数为：

emLs

当系统达到平衡时 ee 则 故

Lsm

1p0mLs

1p0 

21（订货决策）某商店经营一种易腐食品，出售后一个单位可获利a＝5元。若当天售不出去，则每单位损失b＝3元。该店经理统计了连续40天的需求情况（不是实际销售量）。现将所得数据列出如下：

3,3,4,2,2,4,2,3,4,4,4,3,2,4,2,3,3,4,2,2,4,3,4,3,2,3,4,2,3,2,2,3,4,2,4,4,3,2,3,3 经理想应用马尔可夫链来预测需求量，确定明天进货量。 （1）已知当天需求量为3个单位，明日应进货多少单位？ （2）若不知当天需求量，明日应进货多少单位？

1110、一物体作线性运动，每次它以概率向右移动一单位，或以概率向左移动。设置障碍22后，若物体任何时候到达这些障碍之一它将留在那儿。令状态为0、1、2、3、4。状态0、4是吸收态，其余为非吸收态，且从中任一个到达吸收态是可能的。求（）各个非吸收态出发到吸收态的平均步数1（2）各非吸收态被各吸收态吸收的概率23、计算下列判断矩阵的权重

（1） A-C C1 C2 C3 C1 1 1/5 1/3

C2 5 1 3

C3 3 1/3 1