运筹学II理解练习知识题

《运筹学II理解练习知识题》由会员分享，可在线阅读，更多相关《运筹学II理解练习知识题（25页珍藏版）》请在装配图网上搜索。

1、运筹学II练习题1 试判定下述非线性规划是否为凸规划:(1)Min f Xx/ x22 8x,2 x2 02Xi x22 0X! ,x20Minf Xc 2222x-| x2 x3 x-|X222X1X245x12X310X1 , X2 , X30(2)(3) Cmax f (X) x, x2St2 2x,x2 02 2Min f Xx1x28”g1 X x1x20解(1)1122g2 Xx1 x22 0X1 , X20f X ,g1 X ,g2 X的海赛矩阵的行列式:2X1X1X22f X2fX2x2 x1X222g1 Xg1X2X1X1X222g1 Xg1XHg1x x-i2f X2f X

2、2 00 22 0X22g2XTX2g2XX2X1g22g2XX1X22g2X2X2知f X为严格凸函数,gi X ,为凸函数,g2 X为凹函数，所以不是一个凸规划问题。(2)Min fgi X2X15X122%22X22X22X3g12X2g2 XX1,X2,X30X310同上有，gi，g2的海赛矩阵的行列式(3)说明2102,是凹函数，g2000是凸函数，不是gimin (Xi凸规划问题。s.tf(X)g1(X) g2(X) g3(X)f(X)g2(X)2X1X1X2f （X）是凸函数, 0,Hg3（X）g1（X）、2试用斐波那契法求函数2f x x 3x 2g(X)020,g2（X） g

3、3（X）是凹函数。因此,本模型是一个凸规划。在区间0 , 10上的极小点，要求缩短后的区间长度不大于原区间长度的8%。(1.5 )3用分数法求f(t)的极大点，先以X 00,0 t为初始点进行计算，求出极大点;再以X 00,1 T为初始点进行两次迭代。最后比较从上述两个不同初始点出发的寻优过程。(2，22x1 22x2的极大点，即求2x1222x2的极小点。(1 )取初始点X 0T0,0，取精度0.1Fn 1/12.5,n 6; a0 0,b0 10;t1 b0F5(b0 a0) 3.846; F6t1 a0F5(b0 a0)6.154;F6f(t1) 5.254;f(t1) 21.409;1

4、1f(t1)f(t1)al 0;b1 6.154;t23.846;t2 b1F4(b1 a1) 2.308;F511f(t2)0.403;f (t2)f(t2)5.254冷 a2 0; b2 3.846;t3 2.308;t3 b2F3(b2 a2) 1.538;F4* if(t3)0.248 f (t3)0.403料 a3 0;b3 2.308;t41.538;t4 b3F2(b3 a3) 0.769;F311f(t4) 0.284 f (t4)0.248 a4 0.769;b4 2.308;t5 1.538;F1t5 a4 (b4 a4) 1.538F22t t 2在区间1,3上的近似极小

5、点，要求缩短后的区向长度不大于原区间长的 8%。( 0.538)4试用最速下降法求函数X12x；T4,0TX12 ,4x2x0Th44,0 02 044,004 016 13221 0 001 42XX0 g X02 001TTg X2 2 2 ,400,01即X 即为极小点。2为f X的极大点。0(2)取初始点X 00,1 T，取精度0.1，同上方法进行两次迭代有:两次步长110 133两次迭代结果416、，13、，29X1X1139比较：对于目标函数的等值线为椭圆的问题来说，椭圆的圆心即为最小值，负梯度方向指向圆心，但 初值点与圆心在同一水平直线上时，收敛很快，即尽量使搜索路径呈现较少的直

6、角锯齿状。5 求 f (X)3 2122x1的极小点，取T2X1x2X-|X22X。2 4 。(1,1)解 f(X)131X-!x1x1X2“彳 20211x2x2f(X)3x1x22x2T%f(X。)12 6 ,Pof(X。)126PoT f(Xo) PoTHP。126121261 121 65175 “T26T3824126171717X1 XoPo6T121717f(XJ66121717171217126126f(XJT f(XJ f(Xo)T f(Xo)1289Rf (X1) 0P012 12 61717289T90210289289Rt f(xj rthrX1由于f(X2)00 T，

7、故 X2T11即极小点，计算经两步终止。6试用牛顿法求解(0,0)Max f X1x； 2取初始点X 04,0解 求Max f X2x11X22的极大点，即求2X12X22的极小点。g(X0)80Hg(X)1g(X)1/ 2 00 1/2X141/ 21/2g(X1)T00所以极大点为X 0,01xtax22Xi2xAx22X2X2XiX2,XiT2x2Xi0T现从X 01,1,开始T2,3X0T2, 3于是f X0 T22,33ii22,3i23i334P 0 T AP0piI3 2i34 3_834534x1TA _L _L3434,3434T3234 , 347试用共轭梯度法求二次函数(

8、0,0)f Xi -xtax2的极小点，此处iiAi211ii解Ali2P1故得到极小值点f X1 T3422,331340P0342342104,65 T34Tp1P1 T AP 13234，34104 65342342104 651 1342 3421 23 104 2 653433910426 65344X1104 6534234133434 3413104毎653420,08考虑下面的非线性规划：max f (X) In(捲 1) x22x1 x2 0K-T条件求解。(0,3)验证它为凸规划，并用解原问题可写为Hf(X)1(X11)20f(X),gi(X)1 T , g2(X)1 0T

9、g3(X)0 1 Tmin f (X) In(为 1) x2s.t g1 (X)3 2x1 - x2 0g2(X)X1 0g3(X)x2 0计算目标和约束函数的海赛阵0 0,Hg1(X) Hg2(X)讥彳以)0故此问题是凸规划。K-T条件表达式为x1 111(32X112x10X2)3X2 1 2、X2若10,则无解,令x10, 3 0 ,则有1 2 1 2 01 1 03 x20解得X10,X23, 121, 30 ,显然0 3 T是可行点，从而是极小点。Max f x x 3清华版，7章例110求解二次规划2 2min f(X)(2x-| 2x2) 8论 10x226 3x1 2x2 0S

10、.tx- 0, x2 0(X4133313见天大版例3-1611试解二次规划Min f X2 22x-| 4x(x2 4x2 6x1 3x24x-| x29x1, x20解将上述二次规划改写为1 2Min f X4x-i28x1x28x26x-i3x23 x1x209 4x1 x20X1,X20可知目标函数为严格凸函数，此外C1 6, C2 3,C114,C222C12C214,33,an1,a121b29,a214,a221由于G和C2小于零，故引入的人工变量 乙和Z2前面取负号，这样得到线性规划问题如下ming z乙Z2y34y4y14x14X2 Z16y3y4y24x14X2 Z23Xi

11、X2X33 04x1X2X490Xi,X2,X3,&,yi,y2, 丫3”4忆忆20解此线性规划问题得*39*21*c*3120，X220，X30，X420* 21*Z10,Z20,y3 T，y4022*393921213921441f X2446 -3 -2020 202020204012试用SUMT外点法求解 （1 , 2 ）Max f XX1X223X110x1 1 3x220N，X20解原问题转化为min f XX1x223X-i103X11x220X10X20构造惩罚函数32P x,Mx1 M min0,x22X11322 2min 0,Xj1x22min0, xjmin 0, x2

12、P3212M min 0, x22x-i1?3 x-i1X1322M min 0, x11x22?3 x112M min 0, x-jP 32Mmin 0, x2 2X11X232M min 0,x11x222Mmin 0, x2解得最优解为*TX 1,21/2小时的负指数分布，修理时间13一工人管2台机器，每台机器发生故障前的运转时间为具有均值为 也属负指数分布，均值为 1/3小时。（1）画出转速图。（2）列出平衡方程式求出状态概率Po，P1，P2。（3）求故障机器数的均值 Ls。（4）一台机器每次停机时间均值Ws。解 （1）入1 = 2台/小时，卩=3台/小时M/M/1/ /2模型卩=3(

13、1=3(2 ) 3P1 = 4Po , 5P 1 =4P o+3P 2 , 3P2= 2P14248P1 =P0,P2 =P0= P0333948P0+ P1 + P2 = P0 +P0 +P0 = 1399128-P0 =P1 =P2 =29292912 16 28(3 ) Ls= 0 P0 + 1P1 + 2P2 =+ =(台)=0.966292929960(4 ) Xe=(1 Po)= 3 ( 1 )=2929L 28Ws =0.47 (小时)=28 (分钟)e 6014某风景区有一小客店， 每天平均到达4人，顾客平均逗留时间为 2天，到达服从泊松分布， 逗留时间服 从负指数分布，若该旅

14、馆只有(C =)2个单人房间，客房住满时再到达的顾客会离去(N = 2)。( M/M/2/2模型)(1) 画出转速图，列出平衡方程式。(2) 求空闲概率 Po和满员概率 P2。(3) 求每天客房占用数的均值 Ls 。解入=4人/天(1=1/2人/天(1 )1/2P 1= 4PoP1 = 8P 0P2 = 4P1P2= 32P0(2 ) 1 = P0 (1 + 8 + 32 )= 41P0 P0 = 1/41P1 = 8/41P2 = 32/412(3) Ls=npnn 0旦2 32414172411.76 (间)空闲概率为P0 = 1/41满员概率为P2 = 32/41客房占用数均值为1.76

15、 (间)15某加油站有一台加油设备，加油的汽车以平均每 5分钟1辆的速度到达，服从泊松分布，力啪时间服从 负指数分布，平均每辆车的加油时间为4分钟。试求：(1 )这个加油站平均有多少辆汽车在等待加油？(2) 每辆汽车为在这里加油平均需耗费多长时间?(3) 管理部门规定，若加油的平均等待时间超过3分钟或系统内的平均汽车数超过 8辆，则需要增加 加油设备，试计算现在的情况是否需要增加加油设备？(4) 如果加油的汽车流有所变化，那么当超过多少时需要增加加油设备？M/M/1 / Po 10.21(2) Ws20(3) Wq3 Ls 8110.8542Lq3.2 Ls1 1Wq16( )328需要增加加

16、油设备；(4) Ls 89， Wq 39故当A超过(3 /28 )时，需要增加加油设备16 设ns表示系统中顾客数，nq表示队列中等候的顾客数，在单服务台系统中，我们有ns nq 1ns, % 0试说明它们的期望值Ls Lq 1，而是Ls Lq。根据这关系式给以直观解释。解因为为单服务台，只有超过1个顾客时，才会出现排队等待。Lqn 1 Pnn 1nPnPnn 1n 1Ls 1 P0Ls则Ls Lq17 在M/ M/ 1/N/ 模型中，如 1，试证：下式成立F0 P于是Ls N/2解 在M/ M/ 1/N/ 模型中，其状态转移图如下:则 Pn - Pni* I又1,则PnPn 1，依次类推Po

17、Pi PnN又Pn 1，则1 n 0Po BPn1N 1 Po 1PoLsnPnn 01 N N 1N 12N218 对于M/ M/ 1/N/ 模型，试证:1 Pn1 P0并对上式给予直观的解释。显然解 设 一由M/ M/ 1/N/ 模型的数字特征有PnPn1N 11N111PN 11N1pN1N 1pN11Np p1N 1p1P0PoPo1PopNpn 11 PoPopNPnpNPoPo1 Pn1 Po由于系统的容量为 N，则有效到达率为:pN 1Pn当系统平衡时，有效到达率和有效服务率应当相等,1 Pn1 Po19 对于M/ M/ 1/m/m模型，试证m1 P)，并给予直观解释。证 由于系

18、统的有效服务率为:1 PoLs表示系统中平均出故障的机器数，则系统外的机器平均数为 m Ls，则系统的有效到达率， 即m台机器单位时间内实际发生故障的平均数为:Ls当系统达到平衡时LsPomLs1 Po8 A.臥C三竦公诃生产同 种产品.根拯调杳得知”各京公司产品上月占据市场 的協额分别为50%3%和20%设第杯月顾客对这种产品的各种肄号的盂求状况 可用-个齐次马尔可夫S(TJ-1(2 表示令状态N】、N* N分别表示实入B. E公词产品相庵的槪事转移矩阵D 70 0.10 0_20尸匸0.10 0H0 000.05 0 05 0.90试M冷M和下片三家公诃产品占据市场的悅報各为$步？-年后三

19、線公训产品 占齬市场的分额各为多少？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,323,3经理想应用马尔可夫链来预测需求量，确定明天进货量。(1) 已知当天需求量为 3个单位，明日应进货多少单位？(2) 若不知当天需求量，明日应进货多少单位？1110、一物体作线性运动，每次它以概率1向右移动一单位，或以概率1向左移动。设置障碍22后，若物体任何时候到达这些障碍之一它将留在那儿。令状态为0、1、2、3、4。状态04是吸收态，其余为非吸收态，且从中任一个到达吸收态是可能的。求()各个非吸收态出发到吸收态的平均步数(2)各非吸收态被各吸收态吸收的概率23、计算下列判断矩阵的权重A-CC1C2C3C111/51/3C2513C331/31C-D13411/213F51 31 311 211/412L31/71 51131