资源描述
No .1线性规划1、某织带厂生产 A、B两种纱线和 C、D两种纱带，纱带由专门纱线加工而 成。这四种产品的产值、成本、加工工时等资料列表如下：项目产品ABCD单位产值(元)1681401050406单位成本(元)4228350140单位纺纱用时(h)32104单位织带用时(h)0020.5工厂有供纺纱的总工时 7200h ，织带的总工时1200h。(1) 列出线性规划模型，以便确定产品的数量使总利润最大；(2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的解是否有影响？解：设A的产量为X1，B的产量为X2，C的产量为X3，D的产量为X4， 则有线性规划模型如下：max f(x)=(16842)X1 +(140 28)X2 +(1050350) X3+(406140) X4=126 x 1 +112 X2 +700 X3 +266 X43x12x210x34x47200s.t.2x30.5x41200xi0,i1,2,3,4(2)如果组织这次生产有一次性的投入20万元，由于与产品的生产量无关,故上述模型只需要在目标函数中减去一个常数20万，因此可知对模型的解没有影响。2、将下列线性规划化为极大化的标准形式minf (x)2X13x25X3X1X2X35s.t.6x17 x29x316|19x17x25x3| 13X1,X20,X3不限解：将约束条件中的第一行的右端项变为正值，并添加松弛变量 X4，在第二行添加人工变量X5，将第三行约束的绝对值号打开，变为两个不等式，分别添加松弛变量X6, X7，并令，则有maxf (x)= 2 X1 3 X2 5()+0 X4 M X 5+0 X6 +0 X7x1 x2 x3 x3 x456x1 7x2 9x3 9x3 x51619Xi 7X2 5X3 5X3X6 13X713Xi,X2,X3,X3,X4,X5,X6,X7019x1 7x2 5x3 5x33、用单纯形法解下面的线性规划max f(x)2x15x23x33x12x2X3610丄Xi6x23x3125s.t.2x1X20.5X3420Xi,X2,X30,解：在约束行1,2,3分别添加 X4, X5, X6松弛变量，有初始基础可行解和单纯形法迭代步骤如下：Cj253000CbXbbX1X2X3X4X5X6b i/ aij*0X4610321100610/20X51251(6)3010125/6*0X6420211/2001420/1OBJ=0Zj000000Cj - z j253000Cj253000CbXbbX1X2X3X4X5X6b i/ aij*0X41705/3(10/3)0211/30170.55X2125/61/611/201/60一0X62395/611/60001/61一OBJ=625/6Zj5/655/205/60Cj - z j17/601/205/60Cj253000CbXbbX1X2X3X4X5X6b i/ aij*2X1341/2103/53/101/100一5X5197/401(2/5)1/203/200125.1250X62847/40011/111/207/201一0OBJ=2349/Zj254/517/2011/2004Cj - Z j0011/5011/200Cj253000CbXbbX1X2X3X4X5X6b i/ aij*2X11955/813/203/81/803X3985/805/211/83/800X613555/011/4011/161/16116OBJ=6865/Zj221/239/811/808Cj - Z j011/209/811/80答：最优解为X1 =244.375,X2 =0, X3 =123.125,剩余变量 X6 =847.1875最优解的目标函数值为858.125 。No .2两阶段法和大M法max f (x)0Xi0 x2X5X6Xi2x2X3X580s.t. 3xiX2X4X675Xi，X2，X3，X4, X5，X60解：将原问题变为第一阶段的标准型1、用两阶段法解下面问题:min f(x) 4x1 6x2Xi 2x280s.t. 3xi X275x1 ,x20第一阶段单纯形表Cj0000iiCbXbbXiX2X3X4X5X6b i/ aij*iX580i2i0i080iX675(3)i0i0i75/3*OBJ=i55Zj43iiiiCj - z j43ii00Cj0000iiCbXbbXiX2X3X4X5X6b i/ ariX5550(5/3)ii/3ii/3553/5*0Xi25ii/30i/30i/325 3OBJ=55Zj05/3ii/3ii/3Cj - z j05/3ii/304/3Cj0000iiCbXbbXiX2X3X4X5X6b i/ aij*0X2330i3/5i/53/5i/50Xii4i0i/52/5i/52/5OBJ=0Zj000000Cj - z j0000ii第二阶段Cj4600CbXbbXiX2X3X4b i/ aij*6X2330i3/5i/54Xii4i0i/52/5OBJ=254Zj46i4/52/5Cj - Z j00i4/52/5答：最优解为 X1 =14 , X2 =33，目标函数值为254。2、用大 M法解下面问题，并讨论问题的解maxf (x)10xi15X212x35x13x2X3 95xi6X215X315s.t.2xiX2X35Xi,X2,X30,解：第1、2行约束条件添加 X4, X5松弛变量，第 3行添加X6剩余变量和 X7 人工变量，有如下初始单纯形表和迭代步骤：Cj101512000MCbXbbX1X2X3X4X5X6X70X49(5)3110000X51556150100MX752110011OBJ=5Mzj2MMM00MMCj - z j10+2M15+M12+M00M0Cj101512000MCbXbbX1X2X3X4X5X6X710X19/513/51/51/50000X52409(16)1100MX77/501/53/52/5011OBJ=18 7M/zj106+M/52 3M/52+2M/50MM5Cj - z j09 M/510+3M/2 2M/50M05Cj101512000MCbXbbX1X2X3X4X5X6X710X13/2139/8003/101/100012X33/209/1611/203/2000MX71/2043/80011/207/2011OBJ=33 M/2zj1093/8+1221/8+5/8+MM43M/807M/163M/80cj - z j027/8021/85/8M043M/807M/163M/80答：最后单纯形表中检验数都小于等于0,已满足最优解判定条件，但人工变量X7仍未迭代出去，可知原问题无可行解（无解）。No .3线性规划的对偶问题min f (x) 4x1 3x2 8x32 x16st. 4 x21412 X38解：原问题的约束条件可改写为右式X16X12x214X2 4X38X312X1不限,X20, X30令改写后约束条件每行对应的对偶变量为yi,.,y6，则有对偶规划如下:1、写出下列线性规划问题的对偶问题：解：对偶问题为max f (x)2x13x25X3mi ng(y) 5力4y26y3X1x2X3X45y1 2y22 t2x1X34y1y33s.t.X2X3X46s.t.y1y2y35X10,X2,X30,X4不限y1y30y1 0,y20, y3不限maxg(y)6y12y214y3 4y4 8y512y6y1y24st.y3y43y5y68y1,y3,y50,y2,y4,y60第二种解法：将原问题的约束条件该写为0 xi 26并令 X1X12, X2X24, X3X312,则原0 X24100 x3124问题改写为下左式，并有对偶问题如下 式，min f (x) 4x1 3x2 8x3116max g(y) 8y110y2 4y3x18x210s.t X34X1,X2,X30y14y23s.t y38y1 ,y2, y32、写出下问题的对偶问题，解对偶问题，并证明原问题无可行解max f (x) 4x1 3x2解：对偶问题为st.X1 X21X21x1 2x21X1 , X20,mi ng(y)y1 y?讨3y1 y34s.t. y1y2 2y33y1, y2,y3 0约束条件标准化为y1y3 y4 4讨1 y2 2y3 + y5 3y1, y2, y3, y4, y5 0有对偶问题解的单纯形表如下:Cj11100CbYbby1y2y3y4y50y44101100y531(1)201OBJ=0Zj00000ZjCj11100Cj11100CbYbby1y2y3yy50y4410(1)101y2311201OBJ=3Zj11201ZjCj00101Cj11100CbYbby1y2y3y4y51y34101101y21131021OBJ=7Zj21111ZjCj10011入变量答：迭代到第三步，X1为入变量，但主列中技术系数全为负值，故对偶问题有可行解但解无界，由弱对偶定理推论可知，原问题无可行解。3、用对偶单纯形法求下面问题min f(x) 4xi6x2x1 2x280st. 3x1 x275xi, X20解:Cj4600min( Zj - Cj)/ai*jCbXbbX1X2X3X4ai*j 154-7 |10 -!11111ti7i6II-3 1LR8-6735 615920699221116171436运费表(检验数Zij |Wij )44011351530152525530迭代后的分配表 xij OBJ = 8500 i 6109481510 110106r4 -12181715 i 615913L206922L136101143运费表(检验数Zij |Wij )449644043答：X13 =5, X14 =15, X24 =30, X32 =15, X33 =25, X41 =25, X43 =5, X45 =30,OBJ=850。No .6 指派问题1、有4个工人。要指派他们分别完成4项工作。每人做各项工作所消耗的时间(h)如下表，问如何分派工作，使总的消耗时间最少？消工作ABCD甲3353乙3252丙1516丁46410解：变换效率矩阵如下:3353逐(0)0*20*逐(0)0*20*3252行1030列1(0)30*1516标0*4(0)5标0*4(0)546410记0*20*6记0*20*6每行每列都有两个以上的未找到最优解4(0)0*810*(0)5410*23(0)0*0*0*重0*(0)20*新10*3(0)标0*4(0)5记(0)20*6划线过程（发现有4条直线）找到最优解答：容易看出，甲 D，乙共有四个最优解：甲B，丙 A，丁 C;甲B,乙 D，丙B,乙 D，丙A，丁 C ；C, 丁 A ;甲D，乙 B,丙 C, 丁 A ； OBJ=10下面是用匈亚利算法求解的过程：12121.52.51.52.5* 03353El。/335(3)03(2)520.50(1)5163(2)52* 046410巳0-0.5slack2131(1)516nbo1141-0.5ur* 0.546410S*=0.5slack2327nbo4444urS*=12.53.52.53.5335(3)-0.5352-1.5 (1)516-1.51.54610slack nbo ur第一个最优解：OBJ = 102.53.52.53.5335(3)-0.53(2)52W-1.515(1)6lb-1.51.56410slack nbo ur第二个最优解：OBJ = 102、学生 A、B、C、D的各门成绩如下表，现将此4名学生派去参加各门课的单项竞赛。竞赛同时举行，每人只能参加一项。若以他们的成绩为选派依 据，应如何指派最有利?得八s课程数学物理化学外语A89926881B87886578C95908572D75788996解：变换效率矩阵为适用于min化问题，用96减去上面矩阵中所有元素值,742815逐302411逐3(0)1711983118行102310列10*1610161124变051023变(0)5323211870换211870换21 18(0)0* 3122(0)0*(0)161052(0)137答：A物理0*1593(0)0*126B数学OBJ=632310*6(0)20C化学3602119(0)0*24220*(0)D外语24No .7动态规划1、某公司有 9个推销员在全国三个不同市场里推销货物，这三个市场里推销员人数与收益的关系如下表，做出各市场推销人员数的分配方案，使总收 益最大。推销员市场012345678912032475766718290100110240506071829310411512513535061728497109120131140150解：令分配到各地区的推销员人数为决策变量xk，k=1,2,3代表第1、2、3地区；令各地区可供分配的推销员人数为状态变量Sk。最先分配给第 1地区，然后第 2、第3地区，则 si=9。状态转移公式为：Sk+1 = Sk Xk ；目标函数为：第1阶段：第3地区，S3有09种可能，由收益表第3行可知d(X3)单调增，故有X3 *=S3 ；列表如下：X3 *=S30123456789f1*5061728497109120131140150第2阶段：第 2地区，S2仍有09种可能，列表如下: X2、S20123456789X2*f2*090*0901101* -100 f01012112* .111 11001123124*122 121-12101244137* .134一 132 13213201375149*、147 r 14414314314301496160*、159157 -1、155154 .154 -15401607171*.170 *169= 168 .166 165.165 - 1.65、01718180*181八180180179 “177176-17617511819190.190191* 191*191*1901881871861852,3,4191S39876543210第3阶段：第1地区，由S1 =9 , 列表如下:、S10123456789X1*f3*9211213218*2172152082062022012002218S298765432103地区分配 7名答：第1地区分配 2名推销员，第 2地区不分配人员，第推销员，总收益为218 。5小时。2、设某工厂要在一台机器上生产两种产品，机器的总运转时间为生产这两种产品的任何一件都需占用机器一小时。设两种产品的售价与产品产量成线性关系，分别为 （12 X1）和（13 的产量。假设两种产品的生产费用分别是 的生产量使该机器在5小时内获利最大。2X2）。这里X1和X2分别为两种产品4X1和3X2，问如何安排两种产品（要求用连续变量的动态规划方法求解）解：设可用机时为状态Si，先分配产品1机时，故有状态转移方程Sk+1 = sk xk(i =1,2)边界值目标函数为:Si =5, S3=0f2 max( 12 x1 )x12max( 8x1X1 )4x1(13 2x2 )x2 3x22(10x2 2x2)由边界条件S3 = S2 X2 =0，得 X2 = S2，因此有2 2f (S2)10X2 2X210S2 2S2则动态规划总效果的递推方程为f2 (X1)max( 8x1X| 0X12)f1(S2)maXX 8x1X| 0X12)(10S2 2s2)由状态方程S2 = S1X1 = 5X1 ,代入上式得f2 (X1 )max( 8x1X 0X12)10(5 xj 2(5 X1)22max18x-i 3x-) x, 0，解得 X1 =3。因此,f218 3 3 927答：最优策略为第最大利润为 27元。1种产品生产3件，第二种产品生产2件，5小时内No .8 最短路问题（要求最短路用双线在图中标1、求下图中V1到所有点的最短路径及其长度。 出，保留图中的标记值）解：最短路及其长度如图中粗 线和节点上永久标记所示，2、将上图看作无向图，写出边权邻接矩阵，用Prim算法求最大生成树，并画出该树 图。1132236445567788解：由图可得邻接矩阵，由 Prim 算法的最大生成树如 下图，答：最大生成树的权值为39。No .9 网络流问题1、求下面网络 s到t的最大流和最小截，从给定的可行流开始标号法。 求每得到一个可行流后，即每次增广之后，重新画一个图，标上增广后的可 行流，再进行标号法 )解：答：最大流为15，最小割截为No .10随机服务系统：输入过程1、对一服务系统进行观察，总观察时间为102.7分钟，到达系统的累计人数为40人，顾客累计的排队等待时间为44.8分钟，顾客累计的服务时间为79.6分钟，求(1) 系统中平均排队长度；(2) 平均同时接受服务的人数。解：总观察时间为T=102.7 分钟，累计到达人数 40 ,故t = 40/ T=0.3895人 /分钟由题意可知由little 公式,=44.8/102.7=0.436 =79.6/102.7=0.775答：平均排队队长0.436人，平均同时接受服务的人数为0.775人。2、某选举站对甲、乙二人进行选举，选票中只能选其中一人才有效。假设投票的人流服从泊松分布，投甲票的人的到达率为1 =4人/小时，投乙票的人的到达率为2 =2人/小时；再假设所有投票人的票都是有效的，而选举结果的统计是在一个与选民不见面的屋里与投票过程同时进行的。问选举开始后半小时统计结果为：(1)甲得三票，乙得 1票的概率；总票数为5的概率；(3) 甲得全票的概率。解:(1 )假设投甲、乙票的人流不相关，则有3P 甲 3(1/2) P 乙 1(1/2)=(4 1/2) e 4 1/22 2=0.066；3!1!5丘(1/2)(6 1/2)6 1/23e2.025e0.1008 ；5!甲得全票的事件为投乙票的人一个未来而投甲票的人至少来一个，即1 2P 乙 0(1 P 甲 0)= e (1 e )0.368 (10.135)0.318。No .11随机服务系统：标准服务系统1、 某自动交换台有4条外线，打外线的呼叫强度为2次/分钟，为泊松流，平均通话时长为2分钟。当4条外线全忙时，用户呼叫将遇忙音。假设用户遇忙音后立即停止呼叫。问(1) 用户拨外线遇忙的概率为多大？(2) 一小时内损失的话务量为多少？(3) 外线的利用率为多少？(4)过负荷为100%时，外线的利用率为多少？解：已知损失制系统，n =4 , =2次/分钟，分钟， =4erl ，(1) 遇忙的概率为B=p4 =0.31 ；(2) 一小时内损失的话务量=B =1.24erl ；(3) 外线利用率为。 过负荷100%时，外线利用率为。2、 某车间机器发生故障为一泊松流，平均4台/小时。车间只有一名维修工，平均7分钟处理一台故障。若为该维修工增加一特殊工具可使平均故障处理时间降到5分钟，但这一特殊工具的使用费用为5元/分钟。机器故障停工每台每分钟损失5元，问购置这台特殊工具是否合适？解：该系统可认为是M/M/1 无限源等待制，已知 =4台/小时，分钟,分钟； 、分别为增加特殊工具前后修复一台机器故障的平均用时。先求增加特殊工具前后每台机器的平均故障停机历时（等待时间+维修时间），由单服务员等待系统的平均队长公式有：由Little 公式得,=0.875/4=0.21875（ 小时）=13.125 分钟,=0. 5/4=0.125（ 小时）=7.5 分钟,则不引入特殊工具时每台故障的总费用为C1=5 Wd1 =65.625 元;而引入特殊工具时每台故障的总费用为C2=5 Wh+5 Wd2 =62. 5元；答：购置特殊工具是合适的。3、有M/M/ n :/ /FIFO（先到先服务）系统，输入业务量为 ，求当n =1,2,3时的等待概率D，和平均逗留队长Ld的公式。解：由爱尔兰等待公式n =1时,D=,Ld=；n=2时,D =,Ld =;n=3时,D =,Ld =。No .12随机服务系统:特殊服务系统1、下面是四个点间的双向业务量矩阵fij和距离矩阵djfjdj12341 2341一5641011125一2021012362一1.5311014401.5一41210所谓双向业务量 f j，它表示i呼叫j的业务量与 j呼叫i的业务量之和，因此有fij = fji。根据双向业务量所得的网路是无向网路，各点间的电路群都是双向电路，可同时为电路两端的用户呼1单位，汇接局的交换机每条电路 并求骨干线路各点间线束容量0.01，并计算全网费用。叫服务。假设每条电路单位长度的费用为 接口费用为 1单位。(1)根据业务量矩阵求最佳的骨干线路网,(电路数)，要求各线束的呼损小于(2)若在不存在骨干电路的点对间开设独立的直达电路群，计算此时网路中各点对间的线束容量及全网费用，仍要求各线束的呼损小于0.01 O若在不存在骨干电路的点对间开设高效直达电路群，其呼损小于0.3 ,计算此时网路中各点对间的线束容量及全网费用，要求骨干线束的呼损小于0.01 o解：(1)由流量矩阵fij可得最大生成树如下图，显然节点1为汇接局，该树为星形结构，即为骨干电路，点间路由表如下矩阵所示。231-21-31-42-132-143-143412由路由表可计算骨干电路上的双向业务流量：F12 = f 12+ f23 + f24 =5+2+0=7erl,F13 = f 13 + f 23 + f 43 =6+2=1.5=9.5erl,F14 = f 14 + f 24 + f34 =4+0+1.5=5.5erl该网路结构是完全的汇接制，骨干电路仍是全利用度的，根据B0.01的服务等级要求，查爱尔兰损失表可得n 12 =14, n 13 =17, n 14 =12 ,由此可计算出全网费用为C1 =2(14+17+12)=86 O 若在节点(2-3)和(3-4)间开独立的直达电路，网路如下图，只有节点(2-4)间需转接，但 f24=0，故该网中没有转接业务量。查表结果(Fj, nj)标于图上。由此可计算出全网费用为C2 =2 (11 + 13+10)+ (7+6)=81。 若在节点(2-3)和(3-4)间开高效直达电路，网路结构仍如上图，但骨干电路(1-2), (1-3), (1-4)上存在节点(2-3)和(3-4)间的溢流，由此它是一个部分利用度系统，需要利用Wilk inson等效流理论来作计算。首先计算高效电路,因为它们是全利用度的，由B0.3，查表得n23 =3,n34 =3求(2,3)和(3,4)的溢出话务量，有同理有下面求(1-2),(1-3),(1-4)骨干电路(1,2)m2上的业务流为等效流为上的等效流和所需电路数,查表得 n + N=12，故 N=120.3114=11.6886 ，取n12 =12 。N=12，即骨干电路 (1,4) n14上的业务流为等效流为查表得 n+ N=10，取N=10，即 n 14=10。骨干电路(1,3),(有两个溢流) ni3上的业务流为等效流为查表得n + N =14，取N =14 ，即 n 13 =14 。所得网路配置入右图，骨干电路上标的是(Aw , w2)及电路数。全网费用为C3 =2(12+14+10)+(3+3)=78答：经比较设置高效电路的网路配置最优。No .13 存储论1、某工厂每年需某种原料1000kg价k的关系为0 Q 500kg 500 Q 1000kg 1000 Q,已知原料存储费也与Q有关0Q 500kg500Q 1000kg1000kg Q,，一次定购费为200元，定购量，k1 =2 元 /kg， k2 =1.5 元 /kgk3 =1.2 元/kg，Cs1 =2 元/kg.年， Cs2 =1.5 元 /kg.年Cs3 =1.2 元 /kg.年Q与单求最佳订货量Qm，并求该订货量下的全年总费用C(Qm)。解：已知 D=1000 公斤/年，Cd =200 元，Cs如题意;(1)用公式先求 Q01, Q02 , Q03， 500 公斤，(落入该批量价区间) 1000 公斤，（落入该批量价区间） 60 %, C 15 %, CW 60 %5.703000丙C W 50 %4.50无限制A、B、C三种原料每月的供应量和每升的价格如下表。供应量（升/月）价格（元/升）A20007.00B25005.00C12004.00饮料甲、乙、丙分别由不同比例的A、B、C调兑而成，设调兑后不同成分的体积不变，求最大收益的生产方案。解：设X1A为饮料甲中 A的总含量 （升），设X2A为饮料乙中 A的总含量（升）设X1B为饮料甲中B的总含量（升），设X2B为饮料乙中B的总含量(升)设X1C为饮料甲中C的总含量（升）,设X2C为饮料乙中C的总含量(升)设X3A为饮料丙中A的总含量（升），设X3B为饮料丙中B的总含量(升)设X3C为饮料丙中C的总含量（升）3、将下列线性规划化为标准形式min f(x) 5x1 3x2 2x3x1 x2 x3106x1 3x2 7x315s.t.|10x112x2 x31 19x10, x20, x3 不限maxf (x)5x13x22x3 2x3X1X2X3 X3X4106X1 3X27x3 7x315s.t.10x112x2X3X3X51910x112x2X3X3X619X1,X2,X3,X3,X4,X5,X64、求上题的对偶规划。maxg(y)10y1 15y? 19y3 19y4力 6y2 10y3 10y4 5y1 3y2 12y3 12 y43s.t.y1 7y2 y3 y42y1 0, y2 不限，y3 0, y4 0maxg(y)10% 15y? 19y3 19y4y1 6y2 10y3 10y4 5y1 3y212y3 12y43s.t.y1 7y2 y3 y42y1 0, y2 不限，y3 0, y4 0则有模型如下:max f (x)6.8(x1AX1BX1c)5.7(X2AX2BX2c) 4.5(X3AX3BX3C)7.0(X1AX2AX3A )5.0(x1BX2BX3B )4.0(X1CX2CX3C )0.2x1A 1.8x1B28X1c1.3X2A.7X2B1 .7x2C2 .5x3 A0.5x3B0.5x3CX1AX1BX1C1500X2 AX2BX2C3000需求约束X1AX2AX3A2000X1BX2BX3B2500资源约束X1CX2CX3C1200s.t.0.4x1A0.6x1E!0.6X1c0.2X1A0.2x1E!0.8X1c0甲配方约束0.85x2A 0.15x2B0.15x2C00.6X2A0.6X2B0.4X2C0乙配方约束0.5x3A0 .5x3B：0.5x3c0丙配方约束XiA ,XiB,XiC0,i 1,2,3习题课21 .用连续型动态规划求解下题min f(x) x1 x2 x3Xi X2 X327s.t.Xi,X2,X30解：设分配顺序为Xi, X2, X3，三阶段与分配顺序一致，逆向运算。由约束条件有状态转移方程：Sk= Sk-i /Xk-i第三阶段：边界条件为S4=i，所以有X3 S3，f3(S3 ,X3 ) f3 (S3) S3第阶段：S3 = S2/X2， f 2( S2 , X2 ) X2 f3 (S3) X2 S2 / X2824253516476
展开阅读全文