《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 页
