1、运筹学II练习题运筹学II练习题1 试判定下述非线性规划是否为凸规划:Min2 2f X x1 x2 82X2 0(1) X1XiX22 2 00X2 0f X ,gi X ,g2 X的海赛矩阵的行列式:2XiXiX22f X2fX2x2 xiX222gi XgiX2XiXX222gi XgiXHgi2f X2f X2 00 22 00 02g2Xx2g2XX2X1g22g2XX1X22g2X2X20 00 2g1 X ,为凸函数,知f X为严格凸函数,g2 X为凹函数，所以不是一个凸规划问题。Min f X 2x12 x22 x32 %2 2 2gi X Xi X2 4 gi X2g2 X
2、5% x3 10Xi,X2,X3 0同上有X ,gi X ,g2 X的海赛矩阵的行列式2g| 2 ,是凹函数， g20100 是凸函数，不是凸规划问题。0(3) min(f(X)X1X222 小g1(X)1X1X20S.tg2(X)X1 0g3(X)X2 000Hf(X)0- 0,H g02 00 20,0 0“)(X) 0 0 0说明 f (X)是凸函数,g1 (X )、g2(X)、g3(X)是凹函数。因此，本模型是一个凸规划。2试用斐波那契法求函数2f x x 3x 28% ()在区间0 , 10上的极小点，要求缩短后的区间长度不大于原区间长度的Fn 1/12.5 ,n 6;a0 0,b0
3、 10;t1 b0F5(b0 a0) F63.846;t1 a0F5(b0 a0) F66.154;f(t1)5.254;f (t1) 21.409;f(t1)f (t1),Qa1 0;b1 6.154;t2 3.846;t2 b1F4(b1 a1)F52.308;f(t2)0.403;f (t2)f(t2) 5.254Q a2 0; b23.846;t32.308;t3 b2F3(b2 a2)F41.538;f(t3)0.248 f (t3)0.403Q a3 0;b3 2.308;t4 1.538;t4 b3F2(b3 a3)F30.769;f(t4)0.284 f (t4)0.248;Q
4、 a4 0.769;b42.308;t51.538;t5 a4F1(b4 a4) F21.5383用分数法求f(t)2t t 2在区间1,3上的近似极小点，要求缩短后的区向长度不大于原区间长的 8% ()4试用最速下降法求函数2 2f X Xi 2 2X2最后比较从上述两个不同初始点出发的寻优过程。 (2，0) (1 )取初始点X 0 0,0 T，取精度 0.14 2 02 1644,0 02 0 44,0 0 4 016132210 001 42X X0 g X02 00TTg X12 2 2 ,400,01即X即为极小点。2为f X的极大点。0（2）取初始点X 00,1T，取精度0.1，同
5、上方法进行两次迭代有两次步长110 匚， 133两次迭代结果416、，2 9X ,X丄139比较：对于目标函数的等值线为椭圆的问题来说，椭圆的圆心即为最小值，负梯度方向指向圆心，但 初值点与圆心在同一水平直线上时，收敛很快，即尽量使搜索路径呈现较少的直角锯齿状。5求f（x）3 2X11 22X2x1x22x1的极小点，取TX。 2 4 0 (1,1)解f(X)X231 x2 0X11 1X2X2f(X)3x1X22 x2TX1TTf(X。)12 6,pf(X。) 12612T126p。f（x。）65PTHP。3112170 12 61160Xi Xo PoT 5T26T382 4 126171
6、7176T121717f(Xi)61217171712f(Xi)Tf(Xi)17 10f(X)Tf（X。）12 28912666121Pif (Xi)0 P012 617172896T90 210289 289PiT f(Xi)P1THP1XiiP由于f(X2)0 0 T，故 X2Ti i即极小点，计算经两步终止。6试用牛顿法求解(0,0)Max f X2Xi1 x； 2取初始点X 04,0解 求Max f X2xi1X2的极大点,2即求2Xi2X22的极小点。g(X)2x-i 2x2g(X0)80Hg(X)ig(X)i/ 2 00 i/2X1 4i/ 2iTi/2 0所以极大点为* TX 0
7、,07试用共轭梯度法求二次函数 （0,0）Af X -xtax2的极小点，此处A1 11 2解Q A1 11 21 -xtax212x： 2x1x22x2Tf fTJx- X2, x-2x2x-i x2现从x 0T1,1 ，开始0 Tf X 0 2,3P 0X02, 3于是f x0 T22,331122,31231334P 0 T AP0p1 -3 21 34 3T8 534 34f X 1 345 834,34T-034334 ,T234332341 T34 ,342f X 1f X 134 10 f X 0 Tf X 02,32 3423P1oP034342342104,65 T34Tp1
8、P1 T AP 18考虑下面的非线性规划：max f （X） In（捲 1） x22x. x2 0验证它为凸规划，并用 K-T条件求解。（0,3）解原问题可写为min f (X) 巾(论 1) x2s.t g1 (X)3 2X1 - X20g2(X)x- 0g3(X)x2 0计算目标和约束函数的海赛阵Hf(X)(X1 1)2000 0,Hg1(X)故此问题是凸规划。f(X)T 1Jg)2x 1K-T条件表达式为12 1 2x1 11-131(32x1x2) 02X103X201 2、000Hg2(X) Hg3(X)0 0 s.tx, 0, x, 0T4 3313 13见天大版例3-1611试解
9、二次规划2 22x1 4x-|X2 4x2 6x1 3x2由于g和C2小于零，故引入的人工变量 Z1和Z2前面取负号，这样得到线性规划问题如下min g z z1 z2y3 4y4 y1 4X1 4x?乙 6y3 y4 y2 4为 4x2 z? 3x, x2 x3 3 04x1 x2 X4 9 0X1,X2,X3,X4,y1,y2, 丫3”4忆忆2 0解此线性规划问题得12试用SUMT7卜点法求解 （1，2）Max f X x13x2 2 x1 1 03X1 1 X2 2 0X,X2 0解 原问题转化为Min f Xx1 x2 34xi X2 9Xl,X2 0解 将上述二次规划改写为1 2 2
10、Min f X 4x1 8x1x2 8x2 6论 3x223 x1 x2 09 4xi x2 0X1,X2 0可知目标函数为严格凸函数，此外6, c2 3, c11 4, c22 23x2 2 Xj 1 03x1 1 x2 2 0x-i 0x2 0构造惩罚函数32P x,Mx1 M min0,x2 2X11232 2min 0,为1x2 2min0, x-i min 0, x?P3212M min 0, x22X-i 1?3 x-i1X1322M min 0, x11x2 2?3 x11 2M min 0,为P32Mmin 0, x2 2X11X232M min 0, x11X2 22Mmin
11、 0, x2解得最优解为* TX 1,21/2小时的负指数分布，修理时间13 一工人管2台机器，每台机器发生故障前的运转时间为具有均值为 也属负指数分布，均值为 1/3小时。（1） 画出转速图。（2） 列出平衡方程式求出状态概率 Po, R, P2。（3） 求故障机器数的均值 Ls。（4） 一台机器每次停机时间均值 W。解 （1）入1= 2台/小时，卩=3台/小时 M/M/1/ /2模型c 4 c c248 rP1= Po, P2 =P0 一P033394Po+ P1 + P2= Po +P0+8 Po - 139r 9 厂12c 8-P 0 一 P1P 2 =292929(3) Ls= 0
12、Po+ 1Pi+ 2P2= l2 + I6 = 28 (台)=29 29 29(4 )入 e=u( 1 Fb)= 3 (1 -9 ) = 6029 29L 28W s= = = 0 .47 (小时)=28 (分钟)e 6014某风景区有一小客店，每天平均到达 4人，顾客平均逗留时间为 2天，到达服从泊松分布，逗留时间服从负指数分布，若该旅馆只有( C=)2个单人房间，客房住满时再到达的顾客会离去( N= 2)。( M/M/2/2模型)(1)画出转速图，列出平衡方程式。(2)求空闲概率Po和满员概率P2。(3) 求每天客房占用数的均值 Ls 。解入=4人/天 (i= 1/2人/天(1)2= 4P
13、12= 32Po(2)1 = Po (1 + 8+ 32)=41PoPo= 1/41 P 1= 8/41 P 2= 32/41(3)2Ls= npnn o412翌41721.76 (间)41空闲概率为Po= 1/41满员概率为P2= 32/41客房占用数均值为(间)15某加油站有一台加油设备，加油的汽车以平均每 5分钟1辆的速度到达，服从泊松分布，加油时间服从负指数分布，平均每辆车的加油时间为 4分钟。试求：(1)这个加油站平均有多少辆汽车在等待加油(2)每辆汽车为在这里加油平均需耗费多长时间(3) 管理部门规定，若加油的平均等待时间超过 3分钟或系统内的平均汽车数超过 8辆，则需要增加加油设
14、备，试计算现在的情况是否需要增加加油设备(4) 如果加油的汽车流有所变化，那么当 超过多少时需要增加加油设备0.8(1) P。0.2LqLs(2) W1 20Wq16(3) W3 Ls 8需要增加加油设备;故当入超过（3/ 28）时，需要增加加油设备16设ns表示系统中顾客数， nq表示队列中等候的顾客数，在单服务台系统中，我们有ns nq 1 ns, nq 0试说明它们的期望值 Ls Lq 1，而是Ls Lq 。根据这关系式给 以直观解释。Lqn 1n1 PnnpnPnn 1n 1Ls1P0Ls则LsLqP) PLs N/2解 在M/ M/ 1/N/ 模型中，其状态转移图如下:则 Pn -
15、Pn 1又Q 1则Pn Pn 1，依次类推PnP0 P1又Q Pn 1，则n 0Pn 1Po P即N 1 Po 1PoLs1N 1NnPnn 0ngN1 N N 1 gN 1 2N218 对于M/ M/ 1/N/ 模型，试证:1 Pn 1 F0并对上式给予直观的解释。解 设 一由M/ M/ 1/N/模型的数字特征有Pn Pn 1 Pn 11P01 N71N 11 P01 PN 11显然PopNPnPnPnPo1 PopNPNPnPoPo1 Po由于系统的容量为则有效到达率为:Po P1Pn 1Pn当系统平衡时，有效到达率和有效服务率应当相等,1 Pn1 Po，并给予直观解释。19 对于M/ M
16、/ 1/m/m模型，试证 Ls m证 由于系统的有效服务率为:1 Po器单位时间内实际发生故障的平均数为:e m Ls当系统达到平衡时e e则m Ls故1 P)Ls m1 Po21 (订货决策)某商店经营一种易腐食品，出售后一个单位可获利 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,323,3经理想应用马尔可夫链来预测需求量，确定明天进货量。(1) 已知当天需求量为 3个单位，明日应进货多少单位(2)若不知当天需求量，明日应进货多少单位23、计算下列判断矩阵的权重A-CC1C2C3(1)C111/51/3C2513C331/31
