运筹练习题

11.线性规划问题的对偶问题：.x,x,x,xxx,xxx.t.sxxxzmax无限制3213213213210624514723523解：.y,yyyyyyy.t.syyfmin无限制122121212105272423536143.用图解法求解线性规划问题：.x,x,xx,xx,xx.t.sxxzmin0142334232121212121解：x*=(0,7)T，z*=-21（过程略）2三、计算题1、考虑下列线性规划问题Maxz=-x1-x2+4x3s.t.x1+x2+2x3≤9x1+x2-x3≤2-x1+x2+x3≤4x1,x2,x3≥0计算得到以上问题的最优单纯形表：-1-14000cBxBRHSX1x2x3x4x5x6-1x11/31-1/301/30-2/30x560200114x313/302/311/301/3-z-170-40-10-2(1)写出线性规划问题的最优解、最优值、最优基B和它的逆B-1；解：3131323113133101100101111201170600B,Bz,),,,,,(xT*(2)写出此线性规划的对偶问题，并写出对偶问题的解；解：04211429321321321321321y,y,yyyyyyyyyy.t.syyyfmin对偶问题的最优解y*=(1,0,2)T(3)若目标函数中x1的系数从-1变为-3而其它参数均不变时，问题的最优解和最优值是什么？解：31031323131313143231410304003042031)()()()()()(最优解不变3(5)第3种资源的影子价格在什么范围内不变。解：216061633313133332313132331331bbbbb即第三种资源的变化在-6到0.5之间，影子价格不变。2.用表上作业法求解以下运输问题：销地运价产地ABC产量甲36560乙85730丙49830销量384529解：最优运输量为销地运价产地ABCD产量甲161529060乙0300030丙2200830销量38452983.某运输公司拟将一批物资从下列交通网络的S点运输到R点，各路段的距离如图所示。试求从S到R的最短路径。解：最优路径：S----B1----C1----D2-----E2-----R（过程略）44.一个小型的平价自选市场只有一个收款出口，假设到达收款出口的顾客流为泊松流，平均每小时为30人。收款员的服务时间服从负指数分布，平均每小时可服务40人。计算这个排队系统的数量指标P0,Lq,Ls,Wq,Ws解：模型M/M/1λ=30μ=402525407500250101610312501430.WL)(.)h(...WW)()h(.LW,L,.p,qqsqsss，分钟分钟5.有一个铁路列车编组站，待编列车到达时间间隔服从负指数分布，平均到达2列/小时，服务台是编组站，编组时间服从负指数分布，平均每20分钟可编一组。求（1）在平稳状态下系统中列车的平均数；（2）每一列车的平均停留时间；（3）等待编组的列车的平均数；（4）每一列车在系统中的平均等待编组的时间。=2=3132（1）列车平均数2232L(列)（2）平均停留时间12311W（小时）（3）等待编组的列车平均数为：342)(2qL(列)（4）平均等待编组时间32234qqLW小时51、考虑线性规划问题Minf(x)=3x1–4x2+2x3S.t.-x1-2x2+2x3≤7（P）2x1+3x2+4x3≥12x1，x2≥0写出（P）的对偶规划；0y,y2y4y24y3y23y2y.t.sy12y7zMax2121212121三、计算题1、（21分）考虑下列线性规划：MaxZ(x)=x1+2x2S.t.-2x1+x2≤2-x1+2x2≤7x1≤3x1,x2≥0最优单纯形表为：cBxBb'12000x1x2x3x4X52x250101/21/21x13100010x33001-1/23/2-z-13000-1-2⑴、用图解法求解此线性规划；⑵、求此线性规划的影子价格？讨论b2在什么范围变化，可保持影子价格不变？⑶、讨论c3在什么范围变化，可保持最优解不变；解：（1）结果如上表，考察过程。（2）y*=(0,1,2)T，当-10≤△b2≤6时，可保持影子价格不变。（3）时，最优解不变2c3402c3112120,02c212033362、运输问题的数据如下表：B1B2B3B4产量A1A2A3302526272822272629232428252550销量15203035求最优运输方案。最优解：B1B2B3B4产量A1A2A325151015530252550销量15203035f*=5353、某运输公司拟将一大型设备从下列交通网络的A点运输到F点，试用动态规划求从A到F的最短路径。解：最优路径：S---B3---C2---D2---E2---R路径长度：2774、某排队系统只有1名服务员，平均每15分钟有1名顾客到达，到达过程为Poisson流，服务时间服从负指数分布，平均服务1名顾客需6分钟，由于场地限制，系统内最多不超过3名顾客，求：⑴利用kendall符号表示此排队系统的模型；⑵写出平稳时系统各状态概率pn与p0的关系，并求出系统空闲的概率；⑶系统内顾客的平均数和排队等待服务的顾客数；⑷顾客在系统中的平均花费时间和顾客平均排队时间。解：(1)单位时间为小时，4.0,10,4,3/1/M/M；(2)3,2,1n,pp0nn；系统空闲概率：616.04.014.0111p440；(3)系统内顾客的平均数：562.04.014.044.014.01)1K(1L441K1K（人）；排队等待服务的顾客数：178.0384.0562.0)p1(LL0q（人）；(4)顾客在系统中的平均花费时间：8.8146.0842.3562.0)p1(LW03（分钟）顾客平均排队时间：8.2046.01.0146.01WWq（分钟）。max32132xxxzst.0,,33734311313131321321321xxxxxxxxx其最优单纯形表为：23100CBXBbx1x2x3x4x52x1110-14-13x22012-11-z00-3-5-1（1）对c2、c3进行灵敏度分析；（2）对b1进行灵敏度分析；（3）增加一个新变量x6，661,71Pc，问题的最有基是否改变？（1）215c，c3≤48（2）3/4≤b1≤3（3）变化