运筹学课件例题集锦

/1.1线性规划标准型maxZ=c１x１+c2x2+…+cnxns．t。ａ11ｘ1+ａ12x2+…+a１nｘn=b１a２1ｘ1+ａ２2x２+…+a2ｎｘn＝ｂ２am１x1+ａm2ｘ2+…．+amnｘn=bmx1，ｘ2…。xn³0用两个变量的差值代替无约束变量，左边加一个变量将＜变=,左边减一个变量将＞变=.目标函数左边乘—1将minZ变maxZ１用对偶单纯形法解下列线性规划问题miｎS＝x1+4ｘ2+３ｘ4s。t.x１+2ｘ2—x３+x4³３-2x1—x2+４x3＋x4³2x1,x2,x3,ｘ4³0解：此题可用人工变量方法求,但也可用对偶单纯形法。maxS’=－x1-４x2－３x4s。t。—x1—2ｘ2+x3—ｘ4＋x5=－32x1+x2—4x３－ｘ4+x6＝—２x1，x２，x３,x4，x5，x6³0Cｊ－１—４0—3０0CＢＸBｘ１x2x３ｘ4x5x6b０x5－1－2１—１10—30x6２1４－101－２σ-1－40-300０常数项是负数且最小，确定出基变量x５.用出基变量ｘ5行的所有负数分别去除对应的检验数，最小值对应的为进基变量x１，交叉元素为主元（—1)主元运算：第一行乘（—1）【提示：表格同上,x5行对应数字乘－1，这里不抄】主元运算:第二行加上第一行乘(-2)【提示:是对应第二张表的，继续画出表3】计算检验数确定出基变量X6确定进基变量Ｘ3，主元（-２）Cｊ—1－40—3０0CBXBｘ1x2x3x4x5x６b0x11２1１—1030ｘ60—３-2－3２1-8σ0—2－1-2—10-3主元运算：第一行加第二行乘（－１/２）【根据上表继续画表5，σ行不填】计算检验数：全为非正.但此时常数b已全大于零,最优解＝（７,0，４,0）最优值S’=－7Ｓ=７Cj—1－40-300CBXBｘ1x2x3x4x5x6b—1ｘ117/20１－2-１／270x303/2１—3-１-1/24σ０-1/20—1/２-2－1/2－72用对偶单纯形法解下列线性规划问题minＳ=ｘ1+2x2s。t．—x1+2x2—x3³1-x１-２ｘ２＋ｘ3³6x１，x2,x３³0解：将原问题化成maxS’=-x1—2x２ｓ.t。x1—2x２＋x3＋x4=－1ｘ1+2x２—ｘ3+x5=-6x１，ｘ2,x3，x4,x5³0Cj－1—２00０CBXBx１x２ｘ3x4x５b0X41—２110-１０X5１2－101-6σ-1—200００常数项最小出基变量X5,按比值无法比较。常数项次小出基变量Ｘ4，按比值Ｘ2为进基变量。主元(－2）主元运算:第一行乘(-1／２）【提示：表格同上X4行对应数字乘－１/2,画出表格2】主元运算：第二行加第一行乘（-２）【提示：是对表2而言的，画出表3】常数项为负数的行元素全大于零，原问题无可行解.３某地区在制定十年电力规划设置决策变量设备选方案1，２，3的装机台数分别为x１、x2、x3，它们的年发电量分别为ｘ6、x7、ｘ8亿度,备选方案1无前期土建工程要求，备选方案2和3都需要前期土建工程,这两个前期土建工程是否施工用变量ｘ4、ｘ5代表。则x1取值0-5之间的整数，ｘ2、ｘ3取值０-4之间的整数，x4、ｘ5只能取0或1，x6、x７、ｘ8大于零.约束方程满足装机容量需求约束:10ｘ1＋2５x2+3０x3³18０满足规划年发电量需求约束:x6+x7+x8³100各电站容量与发电量平衡方程：每台机组发电量等于单机容量乘全年小时数，再乘与负荷因子，换算亿度量纲,即：方案1:ｘ6=（0。66×８760×１0／1０００0）×x1方案２:x７=(0.４×876０×２5/１0000)×x2得三个约束方程：５．782x1-x６=0８．７6x2－x7＝018．３９x3-x8＝０每个方案最多的装机台数约束:方案1：不需前期土建工程;x1£5方案2:前期土建工程是装机的先决条件，且小于最大允许数；ｘ2£4x4方案3：前期土建工程是装机的先决条件，且小于最大允许数；ｘ３£4x5变量取值限制x1、ｘ2、ｘ３³０且整数x6、ｘ7、x８³0x4或x5=１前期土建工程要求x4或x5＝０无前期土建工程要求设计目标函数目标函数：年成本费用最低.成本包括两大部分：可变成本：与发电量有关的成本,如:原材料，燃料，动力和活劳动消耗等。即参数表中年运行成本.不变成本:指与装机容量及前期土建投资有关的成本.方案1：单机投资×回收因子=２１×0。１0３=2.163（百万元)方案２：单机投资×回收因子=７0×０．０5７８=４。046（百万元）方案３：单机投资×回收因子＝6５×0.1０3=6．６95(百万元）方案2和3的前期土建投资的年资本回收成本分别为5０4×０．０578=29．1３1（百万元）24０×0．１03=2４。72(百万元)对方案1，２,3每发一亿度电的运行成本分别为4。１1,2。2８，3。6５百万元。则数学模型如下：MｉnZ＝2.1６３x1+4。０４6ｘ2＋6．6９5ｘ3+２9．131x4+24．７２ｘ５+4.11ｘ6+2.２8x7＋3.65x８ｓ。t．１0x1＋25x2+30ｘ3³180x6＋x７+x8³100４某石油公司四厂七售区炼油厂123４日产量35２51５40销售区１2３4５６7日最大售量2５201０2510１5１0解:平衡问题，用最小元素法求初始方案。计算检验数.闭合回路。最优方案如下，最小运费=480000元有非基变量的检验数=0，有无穷多组解,另外一个解如下:5铁路列车编组站Ｍ/Ｍ/１／¥/¥排队问题。其中ｌ＝２，m=3,r=l/m=2/3<1系统中列车的平均数Ls=r/（1－r）=（２/3）/（1－2/3）=2（列)列车在系统中的平均停留时间Ws=Ｌs/l=2/2=1（小时）系统中等待编组的列车平均数Lq=Ls—ｒ=2-２／3＝４/３(列）列车在系统中的平均等待编组时间Wq＝Lq／l=(4／３)/(1/2)=2/3(小时)记列车平均延误（由于站内2股道均被占用而不能进站)时间为W0则Ｗ0=WＰ{Ｎ＞2}=Ｗ｛1－P0-P1-P2｝=Ｗ｛1-（l-ｒ)-（l—ｒ）r1-（l—ｒ）ｒ2}=１＊r3=r3=(2/3)３=0．2９6(小时）故每天列车由于等待而支出的平均费用E=24ｌW0ａ＝2４*２*0．296*ａ=14．２a元6某修理店只有一位修理工解:M/Ｍ/1／¥/¥排队问题.其中l=4，m=1/0。1=10(人/小时），r=l／m＝2/5<1修理店内空闲的概率P0=1—r＝（１-2／5）=0。6店内恰有３个顾客的概率P3=r３（1－ｒ）=（2/５)３(1-２/5）＝0．038店内至少有1位顾客的概率Ｐ｛N³1}=１－P0=１－（1－r)=ｒ＝２／5=0。４在店内平均顾客数L＝r/（1—r）=（2／5）/（1-2/5）=０。67（人）每位顾客在店内平均逗留时间W=L/l=0．67/4=10分钟等待服务的平均顾客数Lq=L—ｒ＝0．６７—2／5=0.27(人）每个顾客平均等待服务时间Wｑ=Ｌq／l=０．27/4=０.0６75小时=４分7某单人理发店有6个椅子N＝７为系统中最大的顾客数，λ=3人／小时，μ=４人／小时１)、某顾客一到达就能理发的概率相当于理发店内无顾客的概率:Ｐ０＝（1-ρ)/1－ρN＋1=[1－(3/4）］／［１—（3/4)7+1]=0.2７782）、需要等待的顾客数的期望值?ＬＳ＝（ρ／１—ρ）－［（Ｎ＋1）ρN+1］／（1—ρN+1)=［（3／４)/1－（３/4)]－［8×(3/４)８]/［１-(3/4）8］=２。11Lq＝Lｓ-（1－P0）=２.11-（1—0.27７８)=1．39(人）３）、求有效到达率?λe=μ(1—P０)=4（1-０。2778)=2。8９(人／小时）４)、求一顾客在理发馆内逗留的期望时间?Ws＝Ls/λｅ=2.11／２.89=0.73（小时)=4３。8（分钟）5)、在可能来的顾客中不等待就离开的概率就是求系统中有7个顾客的概率:P７=［(１-ρ)ρｎ］/［1—ρN+1]＝[(1-０。７５）0。757]／[１-0。７５8]＝3。7％8某车间有5台机器解：m=5，λ＝1/15，μ=1/12，ρ＝λ／μ=0。81）、P０=［0。80×5！／5！+0.8１×5!/４!+0．8２×５！/3！+0．８3×５！/2！+0。8４×5!/1！＋0。85×5!/0！]－1=１/１3６．8＝0．00732）、P5=0。8５×5!/０!×P0=0。2873）、Ls=５－（1/0。８）×(1—0。0073)＝3.７6(台)4)、Lｑ=3.７6—（1—0.0０7３)=2。７7（台)5)、Ws＝［5／（1／1２)(1－０.0073)］—15＝４６（分钟)６）、Wq=46－12=３4(分钟)７）、机器停工时间过长,修理工几乎没有空闲时间，应当提高服务效率,减少修理时间或增加修理工人。9某售票处有三个窗口解：这是一个M/M/c/¥/¥型排队问题.其中c=3,λ/μ=0．9/0。4=２。25，ρ=λ／cμ=0.75<11)、整个售票处空闲的概率？P０=[（2。25）0／0!＋（2。25）1/1！+（2.25)2/2!+（2。25)3/3！×1/（1-0。７５)]-1=０。074８2）、平均队长？ｌq=｛［(2。25）3×０．7５］/［３!（1—0。7５）2］｝×0.０7４8=１。7Lｓ=１.7+2.25=3.９5３)、平均等待时间和逗留时间?Ｗq=1.7/0．9＝1。89(分钟）；Ws=3.95/0.9=4，３94)、顾客必须等待的概率？P（n≥3)=Ｐ（1－P0－P1－P2）=１—0。０7４8－[1×（2.2５)1×０．0７４８］／1！-1×（２.25)2×0。0７4８］/２！=1－0.０748-0．1683—0。1893=0.５6７61０两个修理工人5台机器解:根据题意，m=5,λ=１(次/小时)，μ=4（台/小时）c=２,ρ=mλ/ｃμ＝5/8=0.625,cρ/m＝0．25P0=（1/５！）［(1/５!)（1/４）0+(1/4！）（1/4）1+(1／2!３！）(１/4)2＋(2２／2！）（1／2！）（1/8）３+(1/8）４+(1/８)5]－１=0。３1５P1=0．３94，P2=0.19７,Ｐ3＝0。07４，P4=０.018,P5=0．002１)、Lq=P３+２Ｐ4+3P5=０．1182）、Ls=P１+2Ｐ2+3P３+4P４+5P5=１．0923)λe=1×(5-1.０９２）＝3。9０84）Wq=0.11８/3。908=0。０３（小时）5）Ws=1.09２/３。908＝０。2８小时11某医院手术室根据病人来诊和完成手术时间的记录(1)算出每小时病人平均到达率=∑nfｎ/1００＝２.1（人/小时）每次手术平均时间=∑vfv/１00=０.4（小时／人)每小时完成手术人数=1/0．４=2．5(人／小时）（2)取λ=2．1μ=2。５。可认为病人到达服从泊松分布,手术时间服从负指数分布。（3）ρ=λ/μ＝2．1/2。5=０。8４说明服务机构（手术室)有84％的时间是繁忙的，16％空闲(4）病房中病人数Lｓ=2。1／（2．５－２．1）=５．25（人)排队等待病人数Lq=0.84×5．25＝4。4１（人）病人逗留时间Wｓ=1/(2。５－2.1）=2。5（小时)病人排队等待时间Wq=0.8４/(2.5-2。1）＝２．1（小时）12目标规划某人有一笔50万元的资金可用于长期投资解：设xi为第Ｉ种投资方式在总投资额中的比例,则模型如下:ＭaxZ=11ｘ１+15ｘ2+２5x3+20x4+１0x5+12x６＋3x7s.t。3x1+10ｘ2＋6x3+2x4+x5+5x6£5１１x1＋15x2+２5x3+20x４＋10x5＋12x６+3x7³13x1+３ｘ2+８x3＋6x4+ｘ5+2x6£4１5x２+３０ｘ3+2０ｘ4+5x５+10ｘ6³1０ｘ１＋ｘ2+ｘ3+x４+ｘ5+x6＋ｘ7=1x１，x２,x3，x4，x5,ｘ６,ｘ7³0整数规划整数规划的一般数学模型:max（ｍin）Z=Σcｊxjs.t．Σａijxｊ£bｉ(i=１，2，…m）ｘｊ³0且部分或全部是整数13登山准备序号1234５67物品食品氧气冰镐绳索帐篷相机设备重量5526１224重要系数201518148４10解:令ｘi=１表示登山队员携带物品ｉ，xi=0表示登山队员不携带物品则问题表示成0-1规划：maxZ=２0x１+1５x２+18x3+14x4+8x５＋4x6＋１0x７ｓ．t。5ｘ1＋5ｘ2＋2x3+６x4+12ｘ5+２x6+４x7£２5ｘi=1或xｉ＝0i＝1,2，….７１4某机械化施工公司解：设每天安排WＹ５0、WY７５、WY１00液压挖掘机和5t、8ｔ、15t自卸汽车各是Ｘ1、X2、X３、X4、Ｘ5、Ｘ6台，则根据题意建立整数规划模型为:MinZ=8８０X１+1060X2＋14２0X３+318X4+458X5＋７26X６S．t401X1+549X2+692X3≥98028Ｘ4+45X5+６８X6≥98028X4＋45X5＋68X6≥401Ｘ1+5４9Ｘ2＋６9２X3X1≤4X2≤２Ｘ３≤1X4≤10X５≤2０Ｘ6≤１0Xj≥0,且为整数.１５某种农作物在生长解：假设用甲、乙、丙、丁为X１、X２、X３、Ｘ4公斤。数学模型为：miｎS=４x１＋15ｘ２+1０x３+１3x4s。t。0.03x1+0。3x２+0.1５x4³330。05x1+0.２ｘ3+０。１ｘ４³24０.14x1＋０。０７x4³２4x1,ｘ２，ｘ３，x４³０将模型化为：maxS=-４x１-15x２－10x３—13x4-０。03x1—0.３x2—０．1５x4＋x５=—３3－０.０５x1-0。2x3—0.1x４＋x6=－24—0.1４x１—０．0７ｘ4+x7=—24ｘ1，x2，ｘ３,ｘ４,x5，ｘ6,x7³0初始可行基B1=（P5,P6，Ｐ7）Cj-4－１5—10—13000CBXBｘ１x2x3x4x5ｘ6x７ｂ0x5—0．03—０．30-0。１5１00-３30x6—０。０5０－0.２—0。１0010-240ｘ7—0.１4００—0。07001—42σ－４—１5—10—130000第三行乘以1／（－0.1４)【提示:根据上表，x7对应行乘那个数字，画出表2】第一行加上第三行乘（０。03）【提示:对表2而言的,是变第一行，第三行同表2。画表3】第二行加上第三行乘（0。0５)【提示：对表3而言的，是变第二行，第三行同表3.画表4】第一行除（－0。3)计算检验数Cj－４-15－1０-1３000CＢＸＢx１x2x3x４x5x6ｘ7b-15ｘ2０1０0.45-3.3300.7800ｘ600-０。２-0.07５0１-0。3６—9—4x110００．５00－7。14３00σ０0－1０-４。２５-4９。9５0－１8。０６—24０0第二行除以(－０.2）Ｃｊ—4—1５-10-１3000CBXBｘ1x2x3x4x5x６x7b—１5ｘ201０0。45—3。33０0.７800ｘ６０0１0。３750—51。84５－４x11０００.500—7．14300σ-28５0最优解（300,80，4５）最优值Ｓ’=—２8５0Ｓ＝28５016设有街道图，求他的最优投递路线.有四个奇顶点配成两对v2v４,ｖ6v8（1）任取ｖ2v4通路v2v1v8v7v6v５ｖ4任取v８v6通路v8v1v2ｖ３ｖ４ｖ5v6将通路上的边各重复一次，无奇顶点是欧拉图，有第一个可行方案重复边总长为=5１（2)调整可行方案:有二条重复边的去了。重复边总长为=21，检查图中圈：总权＝２4重复边长=14大于2４/2（３)去了原重复边，添上原没有的重复边，重复边总长＝1７，检查图中圈:总权=24,圈上重复边长=13大于24/２（４)去了原重复边，添上原没有的重复边重复边总长=１5，得最优方案17一个工厂要将产品送到火车站解（1)将各弧的单位运费作为长度,求v０到vn的最短增流路v0v1ｖ3v4vn，路长为8，可增加1单位的流值.（２）再求v０到vｎ的最短增流路v0v1ｖ4vｎ，路长为９，可增加２单位的流值.(3)再求ｖ0到vn的最短增流路ｖ0v２v3v1ｖ4vn,路长为14,可增加１单位的流值。（4）再求v0到vn的最短增流路v０ｖ2v3v5ｖｎ，路长为1８,可增加2单位的流值。最大流为8,最小运费=3×3+５×4+3×4+1×1+3×２+2×2＋2×９+４×2＋4×３＝9018一家电脑制造公司自行生产扬声器用于自己的产品若不允许缺货解：R=６0０0台/月,c３=12０0元，c１=0.１0元/月，k=20元。19一家电脑制造公司自行生产扬声器用于自己的产品若允许缺货解：R＝6００0台/月，c3=1２0０元，k=20元，c１=0．10元/月，ｃ2=1元/只。、２0某店拟出售甲商品解：该站的缺货损失每单位商品为70—5０＝2０。滞销损失每单位商品50－40＝10，故k=20，h＝10·２1设某公司利用塑料作原料制成产品出售解：１、计算临界值Ｎ=(C２－K)/(Ｃ1+C２）=（10１５-8０0）／（１0１5+4０)=0.2042、选使不等式成立的Si最小值作S3、原存储I＝10,订货量Q=Ｓ-I＝40-1０＝304、求s。由于已算出Ｓ=40，可以作为s的r值只有３0或4０两个值.将３0作为s得：8０0×3０+10１5×［（４0-30）×0.2+（５0－30）×０.４＋（６0－30）×０.2］=４０2４0将40作为s值,得:60＋８00×４0＋40×［（4０－30)×0。2］+1０１５×［（50-40)×0.4+（6０-40）×0。2］=４０２６0即左端数值为4０２40，右端数值为4026０,不等式成立，30已是r的最小值，故s=30．故存储策略为:每个阶段开始时检查存储量Ｉ,当I＞30箱时不必补充存