《2022年运筹学课件例题集锦》由会员分享,可在线阅读,更多相关《2022年运筹学课件例题集锦(10页珍藏版)》请在金锄头文库上搜索。
1、学习必备欢迎下载1.1线性规划标准型maxZ=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn =b1a21x1+a22x2+ +a2nxn =b2am1x1+am2x2+.+amnxn =bmx1,x2.xn 0 用两个变量的差值代替无约束变量,左边加一个变量将变=,左边减一个变量将变=。目标函数左边乘-1 将 minZ 变 maxZ1 用对偶单纯形法解下列线性规划问题min S = x1 + 4x2 + 3x4s.t. x1+2x2- x3 +x4 3 -2x1 - x2+4x3 +x4 2 x1,x2, x3, x4 0解:此题可用人工变量方法求,但也可用对偶单纯
2、形法。max S = -x1- 4x2 - 3x4s.t. -x1 -2x2+ x3 -x4 +x5= -3 2x1 + x2-4x3 -x4+x6 = -2 x1,x2, x3, x4,x5,x6 0 Cj-1 -4 0 -3 0 0 CBXBx1x2x3x4x5x6b 0 x5-1 -2 1 -1 1 0 -3 0 x62 1 4 -1 0 1 -2 -1 -4 0 -3 0 0 0 常数项是负数且最小,确定出基变量x5。用出基变量x5行的所有负数分别去除对应的检验数,最小值对应的为进基变量x1,交叉元素为主元( -1) 主元运算:第一行乘(-1) 【提示 :表格同上, x5行对应数字乘-
3、1,这里不抄】主元运算:第二行加上第一行乘( -2) 【提示:是对应第二张表的,继续画出表3】计算检验数确定出基变量X6 确定进基变量X3,主元( -2)Cj-1 -4 0 -3 0 0 CBXBx1x2x3x4x5x6b 0 x11 2 1 1 -1 0 3 0 x60 -3 -2 -3 2 1 -8 0 -2 -1 -2 -1 0 -3 主元运算:第一行加第二行乘( -1/2) 【根据上表继续画表5, 行不填】计算检验数:全为非正。但此时常数b 已全大于零,最优解=(7,0,4,0)最优值S = - 7 S=7 Cj-1 -4 0 -3 0 0 CBXBx1x2x3x4x5x6b -1 x
4、11 7/2 0 1 -2 -1/2 7 0 x30 3/2 1 -3 -1 -1/2 4 0 -1/2 0 -1/2 -2 -1/2 -7 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页,共 10 页学习必备欢迎下载2用对偶单纯形法解下列线性规划问题min S = x1 + 2x2s.t. -x1+2x2 - x3 1 -x1 -2x2+ x3 6 x1,x2, x3 0 解:将原问题化成max S = -x1 - 2x2 s.t. x1 - 2x2+ x3 + x4 =-1 x1 + 2x2- x3+ x5 =-6 x1,x2,x3,x
5、4,x5 0 Cj-1 -2 0 0 0 CBXBx1x2x3x4x5b 0 X41 -2 1 1 0 -1 0 X51 2 -1 0 1 -6 -1 -2 0 0 0 0 常数项最小出基变量X5,按比值无法比较。常数项次小出基变量X4,按比值X2为进基变量。主元(-2)主元运算:第一行乘(-1/2) 【提示:表格同上X4行对应数字乘 -1/2,画出表格2】主元运算:第二行加第一行乘( -2) 【提示:是对表2 而言的,画出表3】常数项为负数的行元素全大于零,原问题无可行解。3 某地区在制定十年电力规划设置决策变量设备选方案1,2,3 的装机台数分别为x1、x2、x3,它们的年发电量分别为x6
6、、x7、x8亿度,备选方案1 无前期土建工程要求,备选方案2 和 3 都需要前期土建工程,这两个前期土建工程是否施工用变量x4、x5代表。则x1取值 0-5 之间的整数, x2、x3取值0-4 之间的整数,x4、x5只能取 0或 1, x6、x7、x8大于零。约束方程满足装机容量需求约束:10x1+25x2+ 30x3 180 满足规划年发电量需求约束:x6+x7 + x8 100 各电站容量与发电量平衡方程:每台机组发电量等于单机容量乘全年小时数,再乘与负荷因子,换算亿度量纲,即:方案 1: x6=(0.66876010/10000)x1方案 2: x7=(0.4876025/10000)x
7、2得三个约束方程:5.782 x1-x6= 0 8.76 x2-x7= 0 18.39 x3-x8= 0 每个方案最多的装机台数约束:方案 1:不需前期土建工程;x1 5 方案 2:前期土建工程是装机的先决条件,且小于最大允许数;x2 4 x4方案 3:前期土建工程是装机的先决条件,且小于最大允许数;x3 4 x5变量取值限制x1、x2、 x3 0 且整数x6、x7、x8 0 x4或 x5=1 前期土建工程要求x4或 x5=0 无前期土建工程要求设计目标函数目标函数:年成本费用最低。成本包括两大部分:可变成本:与发电量有关的成本,如:原材料,燃料,动力和活劳动消耗等。即参数表中年运行成本。不变
8、成本:指与装机容量及前期土建投资有关的成本。方案 1:单机投资回收因子=210.103=2.163(百万元)方案 2:单机投资回收因子=700.0578=4.046(百万元)方案 3:单机投资回收因子=650.103=6.695(百万元)方案 2 和 3 的前期土建投资的年资本回收成本分别为5040.0578=29.131(百万元)2400.103=24.72(百万元)对方案 1,2,3 每发一亿度电的运行成本分别为4.11,2.28,3.65 百万元。则数学模型如下:Min Z = 2.163x1+4.046x2+ 6.695x3 + 29.131x4+ 24.72x5 + 4.11x6 +
9、 2.28x7 + 3.65x8s.t. 10x1+25x2+ 30x3 180 x6+x7 + x8 100精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页,共 10 页学习必备欢迎下载4 某石油公司四厂七售区炼油厂1 2 3 4 日产量35 25 15 40 解: 平衡问题,用最小元素法求初始方案。计算检验数。闭合回路。最优方案如下,最小运费=480000 元有非基变量的检验数=0,有无穷多组解,另外一个解如下:5铁路列车编组站M/M/1/排队问题。其中=2,=3,= / =2/32=W1-P0-P1-P2= W1-(l-)- (l-)
10、1 -(l-) 2 =1*3=3=(2/3)3=0.296 (小时)故每天列车由于等待而支出的平均费用E=24 W0a=24*2*0.296*a=14.2a元销售区1 2 3 4 5 6 7 日最大售量25 20 10 25 10 15 10 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页,共 10 页学习必备欢迎下载6 某修理店只有一位修理工解:M/M/1/ / 排队问题 .其中 =4, =1/0.1=10(人 /小时), = / =2/51 修理店内空闲的概率P0= 1- = (1-2/5)=0.6 店内恰有3 个顾客的概率P3= 3(
11、1- )=(2/5)3(1-2/5)=0.038 店内至少有1 位顾客的概率P N 1 =1-P0=1- (1-)= =2/5=0.4 在店内平均顾客数 L= / (1- )=(2/5)/(1-2/5)= 0.67( 人) 每位顾客在店内平均逗留时间W=L/=0.67/4=10分钟等待服务的平均顾客数Lq =L- =0.67-2/5=0.27( 人) 每 个 顾 客 平 均 等 待 服 务 时 间Wq = Lq/ =0.27/4=0.0675 小时 =4 分7 某单人理发店有6 个椅子N=7 为系统中最大的顾客数,=3 人/小时,=4 人/小时1) 、某顾客一到达就能理发的概率相当于理发店内无
12、顾客的概率:P0=(1-)/1-N+1=1-( 3/4) /1-(3/4)7+1=0.2778 2) 、需要等待的顾客数的期望值?LS=(/1-)- (N+1)N+1/(1-N+1)=(3/4)/1-(3/4 ) -8(3/4)8/ 1-(3/4)8=2.11 Lq=Ls-(1-P0)=2.11-(1-0.2778)=1.39( 人) 3) 、求有效到达率?e=(1-P0)= 4(1-0.2778)=2.89( 人/小时 ) 4) 、求一顾客在理发馆内逗留的期望时间?Ws=Ls/e=2.11/2.89=0.73( 小 时 )=43.8 ( 分钟)5) 、在可能来的顾客中不等待就离开的概率就是求
13、系统中有7 个顾客的概率:P7= ( 1-)n/1- N+1= (1-0.75)0.757/1-0.758=3.7% 8 某车间有 5 台机器解:m=5,=1/15,=1/12, = /=0.8 1) 、P0=0.805!/5!+0.815!/4!+0.825!/3!+0.835!/2!+0.845!/1!+0.85 5!/0!-1=1/136.8=0.0073 2) 、 P5= 0.855!/0! P0=0.287 3) 、 Ls=5-(1/0.8)( 1-0.0073)=3.76(台)4) 、Lq=3.76-( 1-0.0073)=2.77 (台) 5) 、Ws=5/(1/12)(1-0.
14、0073)-15=46( 分钟 ) 6) 、Wq=46-12=34 ( 分钟 ) 7)、机器停工时间过长,修理工几乎没有空闲时间,应当提高服务效率,减少修理时间或增加修理工人。9 某售票处有三个窗口解:这是一个M/M/c/ / 型排队问题。其中c=3, /=0.9/0.4=2.25, =/c=0.751 1 ) 、 整 个 售 票 处 空 闲 的 概 率 ? P0=(2.25)0/0!+ (2.25)1/1!+ (2.25)2/2!+ (2.25)3/3! 1/(1-0.75)-1=0.0748 2) 、平均队长?lq=(2.25)3 0.75/3!(1-0.75)2 0.0748 =1.7
15、Ls=1.7+2.25=3.95 3 )、 平 均 等 待 时 间 和 逗 留 时 间 ? Wq=1.7/0.9=1.89( 分 钟 ); Ws=3.95/0.9=4,39 4) 、顾客必须等待的概率?P(n3)=P(1-P0-P1-P2) =1-0.0748-1 (2.25)10.0748/1!- 1 (2.25)20.0748/2!=1-0.0748-0.1683-0.1893=0.5676 10 两个修理工人 5 台机器解: 根据题意, m=5,=1 (次 /小时), =4 (台 /小时)c=2, =m /c =5/8=0.625,c/m=0.25 P0=(1/5!)(1/5 !)(1/
16、4)0+ (1/4 !)(1/4)1+( 1/2!3!)(1/4)2+(22/2!) (1/2!)(1/8)3+(1/8)4+ (1/8)5-1=0.315 P1=0.394,P2=0.197,P3=0.074,P4=0.018,P5=0.002 1) 、 Lq=P3+2P4+3P5=0.118 2) 、Ls=P1+2P2+3P3+4P4+5P5=1.092 3)e=1(5-1.092)=3.908 4)Wq=0.118/3.908=0.03(小时)5)Ws=1.092/3.908=0.28 小时精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4
17、页,共 10 页学习必备欢迎下载11某医院手术室根据病人来诊和完成手术时间的记录(1)算出每小时病人平均到达率=nfn/100=2.1(人 /小时)每次手术平均时间= vfv/100=0.4(小时 /人) 每小时完成手术人数=1/0.4=2.5(人 /小时)(2)取 =2.1 =2.5 。可认为病人到达服从泊松分布,手术时间服从负指数分布。(3)=/=2.1/2.5=0.84说明服务机构(手术室)有84% 的时间是繁忙的,16% 空闲(4)病房中病人数Ls=2.1/ (2.5-2.1)=5.25 (人)排队等待病人数Lq=0.84 5.25=4.41 (人)病人逗留时间Ws=1/(2.5-2.
18、1)=2.5( 小时 ) 病人排队等待时间Wq=0.84/(2.5-2.1)=2.1(小时)12 目标规划某人有一笔50 万元的资金可用于长期投资解:设 xi为第 I 种投资方式在总投资额中的比例,则模型如下:Max Z=11x1+15x2 +25x3 +20x4+10x5 +12x6+3x7s.t. 3x1+10x2 + 6x3+2x4+x5+ 5x6 5 11x1+15x2+25x3+20x4+10x5+12x6+3x7 13 x1+ 3x2 + 8x3 + 6x4+x5+ 2x6 4 15x2 +30x3 +20x4+5x5 +10x610 x1+x2 +x3 + x4 +x5 +x6+
19、 x7 = 1 x1,x2,x3,x4,x5,x6,x70 整数规划整数规划的一般数学模型:max (min) Z = cjxjs.t. aijxj bi(i=1,2, m)xj 0 且部分或全部是整数13 登山准备序号1 2 3 4 5 6 7 物品食品氧气冰镐绳索帐篷相机设备重量5 5 2 6 12 2 4 重要系数20 15 18 14 8 4 10 解:令 xi=1 表示登山队员携带物品i,xi=0 表示登山队员不携带物品则问题表示成0-1 规划 : max Z= 20x1+15x2 +18x3 +14x4+8x5 +4x6 +10x7s.t. 5x1 + 5x2 +2x3 +6x4
20、+12x5 +2x6 +4x725 xi=1 或 xi=0 i=1,2,.7 14 某机械化施工公司解:设每天安排WY50 、WY75 、WY100 液压挖掘机和5t、8t、15t 自卸汽车各是X1、 X2、X3、 X4 、 X5、 X6台,则根据题意建立整数规划模型为:Min Z = 880 X1 +1060 X2 +1420 X3 +318 X4 +458 X5 +726 X6S.t 401 X1 +549 X2 +692 X3 980 28X4 + 45 X5+ 68X6 980 28X4 + 45 X5+ 68X6 401 X1 +549 X2 +692 X3X14 X22 X31 X
21、410 X5 20 X610 Xj0,且为整数。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页,共 10 页学习必备欢迎下载15 某种农作物在生长解: 假设用甲、乙、丙、丁为X1、X2、X3、 X4公斤。数学模型为: min S=4x1+15x2 + 10x3 +13x4s.t. 0.03x1+0.3x2+0.15x4 33 0.05x1+ 0.2x3 +0.1x4 24 0.14x1+0.07x4 24 x1,x2, x3, x4 0 将模型化为:max S= - 4x1-15x2-10x3-13x4- 0.03x1-0.3x2-0.15
22、x4 +x5= -33 - 0.05x1- 0.2x3 -0.1x4+x6= -24 - 0.14x1-0.07x4+x7 = -24 x1,x2,x3,x4,x5,x6,x7 0 初始可行基B1=(P5,P6, P7)Cj -4 -15 -10 -13 0 0 0 CB XBx1x2x3x4x5x6x7b 0 x5-0.03 -0.3 0 -0.15 1 0 0 -33 0 x6-0.05 0 -0.2 -0.10 0 1 0 -24 0 x7-0.14 0 0 -0.07 0 0 1 -42 -4 -15 -10 -13 0 0 0 0 第三行乘以1/(-0.14) 【提示:根据上表,x7
23、对应行乘那个数字,画出表2】第一行加上第三行乘( 0.03) 【提示:对表2 而言的,是变第一行,第三行同表2.画表 3】第二行加上第三行乘( 0.05) 【提示:对表3 而言的,是变第二行,第三行同表3.画表 4】第一行除( -0.3) 计算检验数Cj-4 -15 -10 -13 0 0 0 CBXBx1x2x3x4x5x6x7b -15 x20 1 0 0.45 -3.33 0 0.7 80 0 x60 0 -0.2 -0.075 0 1 -0.36 -9 -4 x11 0 0 0.5 0 0 -7.14 300 0 0 -10 -4.25 -49.95 0 -18.06 -2400 第二
24、行除以( -0.2) Cj-4 -15 -10 -13 0 0 0 CBXBx1x2x3x4x5x6x7b -15 x20 1 0 0.45 -3.33 0 0.7 80 0 x60 0 1 0.375 0 -5 1.8 45 -4 x11 0 0 0.5 0 0 -7.14 300 -2850 最优解( 300,80,45)最优值 S = -2850 S=2850 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页,共 10 页学习必备欢迎下载16 设有街道图,求他的最优投递路线。有四个奇顶点配成两对v2 v4,v6 v8(1)任取 v2 v
25、4通路 v2 v1 v8 v7 v6 v5 v4任取 v8 v6通路 v8 v1 v2 v3 v4 v5 v6将通路上的边各重复一次,无奇顶点是欧拉图,有第一个可行方案重复边总长为=51 (2)调整可行方案:有二条重复边的去了。重复边总长为=21,检查图中圈: 总权 =24 重复边长 =14大于 24/2 (3)去了原重复边,添上原没有的重复边,重复边总长=17,检查图中圈:总权=24,圈上重复边长 =13 大于 24/2 ( 4)去了原重复边,添上原没有的重复边重复边总长 =15,得最优方案17 一个工厂要将产品送到火车站解(1)将各弧的单位运费作为长度,求v0 到 vn 的最短增流路 v0
26、v1v3v4vn ,路长为 8,可增加 1 单位的流值。(2)再求 v0 到 vn 的最短增流路v0v1v4vn , 路长为 9, 可增加 2 单位的流值。(3)再求 v0 到 vn 的最短增流路v0v2v3v1v4vn ,路长为 14,可增加 1 单位的流值。(4)再求 v0 到 vn 的最短增流路v0v2v3v5vn ,路长为 18,可增加2 单位的流值。最大流为8,最小运费 =33+54+34+11+3 2+2 2+29+42+43=90 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页,共 10 页学习必备欢迎下载18 一家电脑制造公
27、司自行生产扬声器用于自己的产品若不允许缺货解:R=6000 台/月, c3 =1200 元, c1 =0.10 元/月, k=20 元。19 一家电脑制造公司自行生产扬声器用于自己的产品若允许缺货解:R=6000 台/月,c3 =1200 元,k=20 元,c1 =0.10 元 /月, c2 =1 元/只。、20 某店拟出售甲商品解: 该站的缺货损失每单位商品为70-50=20。 滞销损失每单位商品50-40=10 , 故 k=20, h=10 21 设某公司利用塑料作原料制成产品出售解: 1、计算临界值N=(C2-K) /(C1+C2) =(1015-800)/(1015+40) =0.20
28、4 2、选使不等式成立的 Si 最小值作S 3、原存储I=10,订货量Q=S-I=40-10=30 4、求 s。由于已算出S=40,可以作为 s 的 r 值只有 30 或 40 两个值。 将 30 作为 s 得:80030+1015 (40-30) 0.2+(50-30) 0.4+(60-30) 0.2=40240 将 40 作为 s值,得:60+80040+40 (40-30) 0.2+1015 (50-40) 0.4+(60-40) 0.2=40260 即左端数值为40240,右端数值为40260,不等式成立,30 已是 r 的最小值,故s=30. 故存储策略为:每个阶段开始时检查存储量I
29、,当 I30 箱时不必补充存储。当I 30箱时补充存储量达到40 箱。1200(元/ 月)600012000.102Rc2c)*C (Q12000(只)0.10600012002cR2cQ*2(月)60000.1012002Rc2cT*3113131091元/ 月6000/1.1120010.102)cR/(ccc2cC(Q)1144(只)1.11600012000.102)c(ccRc2cQ-Q12586(只)0.101.1600012002cc)c(c2RcQ2.1(月)600010.101.112002Rcc)c(c2cT2132121231m02121321213。此时损失的期望值最小
30、为7单位,F(7) ,故订货量应hkk因F(6)0.7440r!6eF(7)0.6063,r!6eF(6)计表。记作F(Q ),可查统P(r),r!6eP(r)0.667102020khk70rr650rr6Q0rr6iSrNP(r)40,作为SS0.2040.400.200.20P(40)P(30)0.2040.20P(30)i精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页,共 10 页学习必备欢迎下载22 木器厂有六个车间,办事员经常要到各个车间了解生产进度。最短路23 有一批货物要从 v1 运到 v9 求最短运输路线24 企业要制定一
31、台重要设备更新的五年计划目标是使总费用最小解: 用点 vi 表示年初。( i=1,2,6) , v6 表示第五年底。弧aij=(vi,vj)表示第i 年初购置设备使用到第j 年初的过程。对应的权期间发生的购置费用和维修费用之和。原问题转变为从 v1 到 v6 的一条最短路。得到两条最短路(v1,v3,v6 ) (v1,v4,v6 )表示在第一、三年或第一、四年各购置一台设备,总费用都为53 万元。25 已知一个地区的交通网络如下,医院。 。 。平均路程最短解: 这是一个选择地址问题,实际要求出图的中心,可化成一系列求最短路问题。先求出v1 到其他各点的最短路长dj ,令 d(v1)=max(d
32、1,d2d7) ,表示若医院建在v1,则离医院最远的小区距离为d(v1)依次计算v2,v3.v7 到其余各点的最短路,类似求出d(v2)d(v3). d(v7) , d(vi)中( I=1,27)中最小者。求出各个小区到区中心医院的平均路程的最小者?由于d(v6)= 48 最小, ,此时离医院最远小区距离为48,比医院建在其他小区时距离都短。同时将区医院建在v6,平均路程为23.71, 比医院建在其他小区时距离都短,所以医院应建在v6 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页,共 10 页学习必备欢迎下载26 网络中最大流解: (1)增流路: v0v3v1v2vn增流值 =2 (2)增流路: v0v2vn 增流值 =4 f = 6 (3)增流路: v0v1v2v4vn 增流值 =4 (4)增流路: v0v3vn 增流值 =3 f =13 (5)增流路: v0v1v5v4vn 增流值 =3 ( 6)增流路: v0v1v3v4vn 增流值 =2 f =18 (7)判断此时的流是否是最大流,用定理寻找最小截集。f =18 两者相等为最大流截量 =5+3+4+6=18 或精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页,共 10 页