《2022年运筹学课件例题集锦.docx》由会员分享，可在线阅读，更多相关《2022年运筹学课件例题集锦.docx（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 学习必备 欢迎下载1.1 线性规划标准型maxZ=c1x 1+c 2x 2+ +cnx ns.t. a11x 1+a12x2+ +a1nx n =b1a21x1+a22x2+ +a2nx n =b 2=,左边减一个变量将变=；am1x 1+a m2x2+ .+amnxn =bmx 1,x2 .xn 0 用两个变量的差值代替无约束变量,左边加一个变量将变目标函数左边乘-1 将 minZ 变 maxZ1 用对偶单纯形法 解以下线性规划问题min S = x1 + 4x2 + 3x4s.t. x1+2x 2- x 3 +x 4 3 -2x1 - x2
2、+4x 3 +x 4 2 x 1,x2 , x3, x4 0解：此题可用人工变量方法求,但也可用对偶单纯形法；max S = -x 1- 4x2 - 3x 4s.t. -x 1 -2x2+ x 3 -x 4 +x 5= -3 2x1 + x 2-4x3 -x 4+x 6 = -2 x 1,x2 , x3, x4 ,x5 ,x6 0 Cj-1 -4 0 -3 0 0 CB X B x1 x 2 x3 x4 x 5 x 6 b 0 x5-1 -2 1 -1 1 0 -3 0 x6 2 1 4 -1 0 1 -2 -1 -4 0 -3 0 0 0 常数项是负数且最小,确定出基变量 x 5；用出基变量
3、 x 5 行的全部负数分别去除对应的检验数,最小值对应的为进基变量 x 1,交叉元素为主元（ -1） 主元运算：第一行乘（-1）【提示 :表格同上, x5 行对应数字乘 -1,这里不抄】名师归纳总结 主元运算：其次行加上第一行乘（ -2）【提示：是对应其次张表的,连续画出表b 3】第 1 页,共 10 页运算检验数确定出基变量X 6 确定进基变量X 3,主元（ -2）Cj-1 -4 0 -3 0 0 CBX Bx1x 2x3x4x 5x 63 0 x11 2 1 1 -1 0 0 x60 -3 -2 -3 2 1 -8 -3 0 -2 -1 -2 -1 0 主元运算：第一行加其次行乘（ -1/
4、2） 【依据上表连续画表5, 行不填】b 运算检验数：全为非正；但此常常数b 已全大于零,最优解=（7,0,4,0）最优值S= - 7 S=7 Cj-1 -4 0 -3 0 0 CBX Bx1x 2x3x4x 5x 6-1 x 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 - - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载2 用对偶单纯形法 解以下线性规划问题min S = x1 + 2x2s.t. -x1+2x 2 - x 3 1 -x 1 -2x2+
5、x 3 6 x1,x2 , x 3 0 2】b 解：将原问题化成max S = -x1 - 2x2 s.t. x1 - 2x 2+ x 3 + x 4 =-1 x 1 + 2x 2- x3+ x 5 =-6 x 1,x2,x3,x4,x5 0 Cj-1 -2 0 0 0 CBX Bx1x2x 3x 4x 5-1 0 X 41 -2 1 1 0 -6 0 X 51 2 -1 0 1 -1 -2 0 0 0 0 常数项最小出基变量X 5,按比值无法比较；常数项次小出基变量X 4,按比值 X 2 为进基变量；主元（-2）主元运算：第一行乘（-1/2）【提示：表格同上X 4 行对应数字乘 -1/2,画
6、出表格主元运算：其次行加第一行乘（ -2）【提示：是对表2 而言的,画出表3】常数项为负数的行元素全大于零,原问题无可行解；3 某地区在制定十年电力规划设置决策变量 设备选方案 1,2,3 的装机台数分别为 x 1、x 2、x 3,它们的年发电量分别为x6、x7、x8亿度,备选方案 1 无前期土建工程要求,备选方案 2 和 3 都需要前期土建工程,这两个前期土建工程是否施工用变量 x4、x 5 代表；就 x 1 取值 0-5 之间的整数, x 2、x 3 取值0-4 之间的整数,x4、x5只能取 0 或 1, x6、x7、x8大于零；约束方程 满意装机容量需求约束：10x1+25x2+ 30x
7、 3 180 满意规划年发电量需求约束：x6+x 7 + x 8 100 各电站容量与发电量平稳方程：每台机组发电量等于单机容量乘全年小时数,再乘与负荷因子,换算亿度量纲,即：方案 1： x6=0.66 8760 10/10000 x 1方案 2： x 7=0.4 8760 25/10000 x 2得三个约束方程：5.782 x1-x 6= 0 8.76 x2-x 7= 0 18.39 x3-x 8= 0 每个方案最多的装机台数约束：方案 1：不需前期土建工程；x 1 5 方案 2：前期土建工程是装机的先决条件,且小于最大答应数；x2 4 x 4方案 3：前期土建工程是装机的先决条件,且小于最
8、大答应数；x3 4 x5变量取值限制 x 1、x 2、 x3 0 且整数 x 6、x7、x8 0 x4或 x5=1 前期土建工程要求x4或 x5=0 无前期土建工程要求设计目标函数 目标函数：年成本费用最低；成本包括两大部分：可变成本：与发电量有关的成本,如：原材料,燃料,动力和活劳动消耗等；即参数表中年运行成本；不变成本：指与装机容量及前期土建投资有关的成本；方案 1：单机投资 回收因子 方案 2：单机投资 回收因子方案 3：单机投资 回收因子=21 0.103=2.163百万元）=70 0.0578=4.046 百万元）=65 0.103=6.695百万元）方案 2 和 3 的前期土建投资
9、的年资本回收成本分别为 504 0.0578=29.131百万元）240 0.103=24.72百万元）对方案 1,2,3 每发一亿度电的运行成本分别为4.11,2.28,3.65 百万元；就数学模型如下：名师归纳总结 Min Z = 2.163x1+4.046x 2+ 6.695x 3 + 29.131x 4+ 24.72x 5 + 4.11x6 + 2.28x 7 + 3.65x8第 2 页,共 10 页s.t. 10x 1+25x2+ 30x3 180 x6+x 7 + x8 100- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载4 某石油公
10、司四厂七售区销售区1 2 3 4 5 6 7 炼油厂1 2 3 4 日最大售量25 20 10 25 10 15 10 日产量35 25 15 40 解： 平稳问题,用最小元素法求初始方案；运算检验数；闭合回路；最优方案如下,最小运费=480000 元有非基变量的检验数=0,有无穷多组解,另外一个解如下：5 铁路列车编组站=2/3（小时）记列车平均延误（由于站内M/M/1/排队问题；其中=2,=3,2 股道均被占用而不能进站）时间为W 0= / =2/32=W1-P0-P1-P2= Ls= / 1- =2/3/1-2/3=2 （列）W1-l- l- 1 -l- 2 列车在系统中的平均停留时间W
11、s=Ls/ = =1*3=3=2/33=0.296 （小时）2/2=1（小时）系统中等待编组的列车平均故每天列车由于等待而支出的平均费用名师归纳总结 数 Lq=Ls-= 2-2/3=4/3 （列）列车在系统中E=24 W 0a=24*2*0.296*a=14.2a元第 3 页,共 10 页的平均等待编组时间Wq = Lq/ =4/3/1/2 - - - - - - -精选学习资料 - - - - - - - - - 学习必备6 某修理店只有一位修理工欢迎下载=1-P0=1- 1-= =2/5=0.4 在店内平均顾客解： M/M/1/ / 排队问题 .其中 =4,数 L= / 1- =2/5/1
12、-2/5= 0.67 人）每位顾 =1/0.1=10 人 /小时）, = / =2/51 客在店内平均逗留时间W=L/=0.67/4=10分钟等待服务的平均顾客数Lq 修理店内闲暇的概率P0= 1- = 1-2/5=0.6 =L- =0.67-2/5=0.27 人 店内恰有 3 个顾客的概率P3= 31- =2/531-2/5=0.038 每 个 顾 客 平 均 等 待 服 务 时 间Wq = Lq/ 店内至少有1 位顾客的概率P N 1 =0.27/4=0.0675 小时 =4 分 L q=L s-1-P 0=2.11-1-0.2778=1.39 人 7 某单人理发店有6 个椅子N=7 为系
13、统中最大的顾客数, =3 人/小时,3）、求有效到达率？e= 1-P0= =4 人/小时 1）、某顾客一到达就能理发的概率相当于理41-0.2778=2.89 人/小时 4）、求一顾客在理发馆内逗留的期望时间？发店内无顾客的概率：P0=（1- ）/1- N+1=W s=L s/ e=2.11/2.89=0.73 小 时 =43.8 （ 分1-（ 3/4）/1-（3/4）7+1=0.2778 钟）2）、需要等待的顾客数的期望值？L S=（ /1- ）-（N+1） N+1/（1- N+1）=3/4/1-3/4 ）-8 3/4 8/ 1-3/4 8=2.11 8 某车间有 5 台机器 解： m=5,
14、 =1/15, =1/12, = / =0.8 5）、在可能来的顾客中不等待就离开的概率就是求系统中有 7 个顾客的概率：P7=（ 1- ） n/1- N+1 = 1-0.750.75 7/1-0.75 8=3.7% 1）、P0=0.8 0 5./5.+0.81 5./4.+0.82 5./3.+0.83 5./2.+0.84 5./1.+0.85 5./0.-1=1/136.8=0.0073 2）、 P5= 0.8 5 5./0. P0=0.287 3）、 Ls=5-（1/0.8） （ 1-0.0073）=3.76（台）4）、L q=3.76-（ 1-0.0073）=2.77 （台） 5）、
15、W s=5/1/121-0.0073-15=46 分钟 6）、W q=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.752 0.0748 =1.7
16、 Ls=1.7+2.25=3.95 3 ）、 平 均 等 待 时 间 和 逗 留 时 间 ？ W q=1.7/0.9=1.89 分 钟 ; Ws=3.95/0.9=4,39 4）、顾客必需等待的概率？Pn3=P1-P 0-P1-P2 =1-0.0748-1 2.25 1 0.0748/1 .- 1 2.25 2 0.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/40+ 1/4
17、 .）1/41+ 1/2.3.）1/42+22/2.）1/2.1/83+1/84+（1/8）5-1=0.315 P1=0.394,P2=0.197,P3=0.074,P4=0.018,P5=0.002 1）、 L q=P3+2P4+3P5=0.118 2）、L s=P1+2P2+3P3+4P4+5P5=1.092 名师归纳总结 3）e=1 5-1.092=3.908 4）W q=0.118/3.908=0.03（小时）5）W s=1.092/3.908=0.28 小时第 4 页,共 10 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载11 某医
18、院手术室依据病人来诊和完成手术时间的记录（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 （人）病人逗留时间 W s=1/2.5-2.1=2.5 小时 病人排
19、队等待时间 W q=0.84/（2.5-2.1 ）=2.1（小时）12 目标规划某人有一笔50 万元的资金可用于长期投资解：设 x i 为第 I 种投资方式在总投资额中的比例,就模型如下：Max Z=11x 1+15x 2 +25x 3 +20x 4+10x 5 +12x 6+3x 7s.t. 3x1+10x 2 + 6x 3+2x 4+x 5+ 5x 6 5 11x1+15x 2+25x 3+20x4+10x 5+12x 6+3x 7 13 x 1+ 3x 2 + 8x 3 + 6x 4+x 5+ 2x6 4 15x2 +30x 3 +20x 4+5x 5 +10x 6 10 x1+x 2
20、+x 3 + x 4 +x 5 +x 6+ x 7 = 1 x1,x2,x3,x4,x5,x6,x7 0 整数规划 整数规划的一般数学模型 :max min Z = cjxj s.t. aijx j bii=1,2, mx j 0 且部分或全部是整数13 登山预备序号1 2 3 4 5 6 7 0-1 规划 : 物品食品氧气冰镐绳索帐篷相机设备重量5 5 2 6 12 2 4 重要系数20 15 18 14 8 4 10 解：令 xi=1 表示登山队员携带物品i,x i=0 表示登山队员不携带物品就问题表示成max Z= 20x 1+15x 2 +18x 3 +14x 4+8x 5 +4x6
21、+10x7s.t. 5x1 + 5x 2 +2x 3 +6x 4 +12x 5 +2x6 +4x725 xi=1 或 xi=0 i=1,2, .7 14 某机械化施工公司解：设每天支配WY50 、WY75 、WY100 液压挖掘机和5t、8t、15t 自卸汽车各是X 1 、 X 2 、X 3 、 X 4 、 X5 、 X 6台,就依据题意建立整数规划模型为：名师归纳总结 Min Z = 880 X1 +1060 X 2 +1420 X 3 +318 X 4 +458 X 5 +726 X 6第 5 页,共 10 页S.t 401 X 1 +549 X 2 +692 X 3 980 28X 4
22、+ 45 X 5+ 68X 6 980 28X 4 + 45 X 5+ 68X 6 401 X 1 +549 X 2 +692 X 3X 14 X 22 X 3 1 X 4 10 X5 20 X 6 10 X j 0,且为整数；- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载15 某种农作物在生长解： 假设用甲、乙、丙、丁为 X 1、X 2、X 3、 X4 公斤；数学模型为： min S=4x 1+15x 2 + 10x 3 +13x 4s.t. 0.03x1+0.3x 2+0.15x 4 33 0.05x 1+ 0.2x3 +0.1x 4 24
23、0.14x1+0.07x 4 24 x1,x2 , x3, x4 0 将模型化为：max S= - 4x 1-15x 2-10x 3-13x 4- 0.03x 1-0.3x 2-0.15x4 +x 5= -33 - 0.05x 1- 0.2x 3 -0.1x 4+x 6= -24 0 b - 0.14x 1-0.07x 4+x 7 = -24 x1,x2,x3,x4,x5,x6,x7 0 初始可行基B 1=（P5,P6, P7）Cj -4 -15 -10 -13 0 0 x7CB X Bx1x2x 3x4x 5x 60 x 5-0.03 -0.3 0 -0.15 1 0 0 -33 0 x 6
24、-0.05 0 -0.2 -0.10 0 1 0 -24 0 x7-0.14 0 0 -0.07 0 0 1 -42 0 0 -4 -15 -10 -13 0 0 第三行乘以1/（-0.14）【提示：依据上表,x7 对应行乘那个数字,画出表2】2.画表 3】第一行加上第三行乘（ 0.03）【提示：对表2 而言的,是变第一行,第三行同表其次行加上第三行乘（ 0.05）【提示：对表3 而言的,是变其次行,第三行同表3.画表 4】第一行除（ -0.3） 运算检验数CBCjX B-4 -15 -10 -13 0 0 0 b x1x2x3x4x 5x 6x7-15 x20 1 0.45 -3.33 0
25、0.7 80 0 0 x60 0 -0.2 -0.075 0 1 -0.36 -9 -4 x 11 0 0 0.5 0 0 -7.14 300 0 0 -10 -4.25 -49.95 0 -18.06 -2400 其次行除以（ -0.2 名师归纳总结 Cj-4 -15 -10 -13 0 0 0 b 第 6 页,共 10 页CBX Bx1x2x3x4x 5x 6x7-15 x20 0.45 -3.33 0 0.7 80 1 0 0 x60 0 1 0.375 0 -5 1.8 45 0.5 0 0 -7.14 300 -4 x 11 0 0 最优值 S = -2850 S=2850 -285
26、0 最优解（ 300,80,45）- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载16 设有街道图,求他的最优投递路线；有四个奇顶点配成两对 v 2 v4 ,v 6 v8（1）任取 v2 v4 通路 v2 v1 v 8 v7 v 6 v 5 v4 任取 v8 v6 通路 v8 v1 v2 v3 v 4 v5 v6将通路上的边各重复一次,无奇顶点是欧拉图,有第一个可行方案重复边总长为 =51 （2）调整可行方案：有二条重复边的去了；重复边总长为 =21,检查图中圈： 总权 =24 重复边长 =14大于 24/2 （3）去了原重复边,添上原没有的重复边
27、,重复边总长=17,检查图中圈：总权=24,圈上重复边长 =13 大于 24/2 （ 4）去了原重复边,添上原没有的重复边 重复边总长 =15,得最优方案17 一个工厂要将产品送到火车站 解（ 1）将各弧的单位运费作为长度,求 v0 到 vn 的最短增流路 v0v1v3v4vn ,路长为 8,可增加 1 单位的流值；（2）再求 v0 到 vn 的最短增流路v0v1v4vn ,路长为 9,可增加 2 单位的流值；（3）再求 v0 到 vn 的最短增流路 v0v2v3v1v4vn ,路长为 14,可增加 1 单位的流值；（4）再求 v0 到 vn 的最短增流路v0v2v3v5vn ,路长为 18,
28、可增加 2 单位的流值；最大流为 8,最小运费 =3 3+5 4+3 4+1 1+3 2+2 2+2 9+4 2+4 3=90 名师归纳总结 - - - - - - -第 7 页,共 10 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载18 一家电脑制造公司自行生产扬声器用于自己的产品如不答应缺货解:R=6000 台/月, c3 =1200 元, c1 =0.10 元/月, k=20 元；T*2c3212002（月）1200（元/ 月 如答应缺货c1R0.106000Q*2c3R21200600012000（只）c10.10C（Q*）2c1c3R20.101200600
29、019 一家电脑制造公司自行生产扬声器用于自己的产品解： R=6000 台/月,c3 =1200 元,k=20 元,c1 =0.10 元 /月, c2 =1 元/只；、T2c3 c1c22212001.12.1 （月）1091元/ 月c1 c2 R0.1016000Q2Rc3c1c22120060001.112586（只）c1c20.10Q 0-Q mc2c1 c3R20.101120060001144（只）2 c1c1.1CQ2c1c2c3R/c1c220.10112006000/1.120 某店拟出售甲商品解：该站的缺货缺失每单位商品为 70-50=20；滞销缺失每单位商品k 20 0.6
30、67h k 20 106 r QPr e 6 , Pr 记作F（Q）,可查统 计表；r. r 050-40=10 ,故 k=20, h=10 F6r50e66r0.6063,F7r70e66r0.7440r.r.因F6kkhF7 ,故订货量应为7单位,此时缺失的期望值最小；21 设某公司利用塑料作原料制成产品出售解： 1、运算临界值 N= （C2-K ） /（C1+C2） =（1015-800 ）/（1015+40） =0.204 2、选 使不等式 Pr N 成立的 Si 最小值作 S r iS P30 0.20 0.204P30 P40 0.20 0.20 0.40 0.204S i 40,
31、作为S3、原储备 I=10 ,订货量 Q=S-I=40-10=30 4、求 s；由于已算出S=40,可以作为 s 的 r 值只有 30 或 40 两个值； 将 30 作为 s 得：800 30+1015 （40-30） 0.2+（50-30） 0.4+（60-30） 0.2=40240 将 40 作为 s值,得：60+800 40+40 （40-30） 0.2+1015 （50-40） 0.4+（60-40） 0.2=40260 名师归纳总结 即左端数值为40240,右端数值为40260,不等式成立,30 已是 r 的最小值,故s=30. 第 8 页,共 10 页故储备策略为：每个阶段开头时检
32、查储备量I,当 I30 箱时不必补充储备；当I 30箱时补充储备量达到40 箱；- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载22 木器厂有六个车间,办事员常常要到各个车间明白生产进度；最短路23 有一批货物要从 v1 运到 v9 求最短运输路线24 企业要制定一台重要设备更新的五年方案目标是使总费用最小解： 用点 vi 表示年初；（ i=1,2, 6）, v6 表示第五年底；弧aij=（vi,vj）表示第 i 年初购置设备使用到第 j 年初的过程；对应的权期间发生的购置费用和修理费用之和；原问题转变为从 v1 到 v6 的一条最短路；得到两条最
33、短路（v1,v3,v6 ）（v1,v4,v6 ）表示在第一、三年或第一、四年各购置一台设备,总费用都为 53 万元；25 已知一个地区的交通网络如下,医院； ；平均路程最短解： 这是一个挑选地址问题,实际要求出图的中心,可化成一系列求最短路问题；先求出v1 到其他各点的最短路长 dj ,令 d（v1）=max（d1,d2 d7）,表示如医院建在 v1,就离医院最远的小区距离为 d（v1）依次运算 v2,v3 .v7 到其余各点的最短路,类似求出 d（v2）d（v3） . d（v7）, d（vi）中（ I=1,2 7）中最小者；求出各个小区到区中心医院的平均路程的最小者？由于 d（v6）= 48
34、 最小,此时离医院名师归纳总结 最远小区距离为48,比医院建在其他小第 9 页,共 10 页区时距离都短；同时将区医院建在v6,平均路程为23.71,比医院建在其他小区时距离都短,所以医院应建在v6 ；- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载26 网络中最大流解：（1）增流路： v0v3v 1v 2v n 增流值 =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 页