运筹学(一)
- 格式:ppt
- 大小:1.51 MB
- 文档页数:107
一、绪论§1 运筹学的简史运筹学作为科学名称出现于20世纪30年代末。
英、美对付德国空袭,采用雷达,技术上可行,实际运用不好用。
如何合理运用雷达?“运用研究”(Operational Research),我国1956年用“运用学”名词,1957年正式定名为运筹学。
运筹学小组在英、美军队中成立,研究:护航舰队保护商船队的编队问题、当船队遭受德国潜艇攻击时如何使船队损失最小问题、反潜深水炸弹的合理爆炸深度(德国潜艇被摧毁数增到400%)、船只在受敌机攻击时的逃避方法(大船急转向、小船缓转向,中弹数由47%降到29%)。
运筹学组织在英、美军队(RAND)中成立,研究:战略性问题、未来武器系统的设计和合理运用方法、美国空军各种轰炸机系统的评价、未来武器系统和未来战争战略、苏联军事能力及未来预报、苏联政治局计划的行动原则和未来战争的战略、到底发展哪种洲际导弹(50年代)、战略力量的构成和数量(60年代)。
运筹学在工业、农业、经济、社会问题等领域有应用。
运筹数学:数学规划(线性规划(丹捷格(G.B.Dantzig)1947,单纯形法;康托洛维奇1939解乘数法,1960《最佳资源利用的经济计算》,诺贝尔奖;列昂节夫1932投入产出模型;冯.诺意曼)、非线性规划、整数规划、目标规则、动态规划、随机规划等)、图论与网络、排队论(随机服务系统理论)(丹麦工程师爱尔朗(Erlang)1917提出一些著名公式)、存贮论、对策论(冯.诺意曼和摩根斯坦,1944《对策论与经济行为》)、决策论、维修更新理论、搜索论、可靠性和质量管理等。
运筹学领域的诺贝尔奖得主:阿罗、萨谬尔逊、西蒙(经济学家)、多夫曼、胡尔威茨、勃拉凯特(Blackett,美,物理学家)。
运筹学会的建立:英国(1948年)、美国(1952年)、法国(1956年)、日本(1957年)、印度(1957年)、中国(1980年),38个国家和地区。
国际运筹学联合会(IFORS)的成立:1959年,英、美、法发起成立,中国1982年加入。
第一章 线性规划及单纯形法(作业)1.4 分别用图解法和单纯型法求解下列线性规划问题,并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。
(1)Max z=2x 1+x 2St.⎪⎩⎪⎨⎧≥≤+≤+0,24261553212121x x x x x x 解:①图解法:由作图知,目标函数等值线越往右上移动,目标函数越大,故c 点为对应的最优解,最优解为直线⎩⎨⎧=+=+242615532121x x x x 的交点,解之得X=(15/4,3/4)T 。
Max z =33/4. ② 单纯形法:将上述问题化成标准形式有: Max z=2x 1+x 2+0x 3+0x 4St. ⎪⎩⎪⎨⎧≥≤++≤++0,,,242615535421421321x x x x x x x x x x其约束条件系数矩阵增广矩阵为:P 1 P 2 P 3 P 4⎥⎦⎤⎢⎣⎡241026150153 P 3,P 4为单位矩阵,构成一个基,对应变量向,x 3,x 4为基变量,令非基变量x 1,x 2为零,找到T 优解,代入目标函数得Max z=33/4.1.7 分别用单纯形法中的大M 法和两阶段法求解下列线性规划问题,并指出属哪一类。
(3)Min z=4x 1+x 2⎪⎪⎩⎪⎪⎨⎧=≥=++=-+=+)4,3,2,1(0426343342132121j xj x x x x x x x x 解:这种情况化为标准形式: Max z '=-4x 1-x 2⎪⎪⎩⎪⎪⎨⎧=≥=++=-+=+)4,3,2,1(0426343342132121j xj x x x x x x x x 添加人工变量y1,y2Max z '=-4x 1-x 2+0x 3+0x 4-My 1-My 2⎪⎪⎩⎪⎪⎨⎧≥=≥=++=+-+=++0,).4,3,2,1(04263433214112321121y y j xj x x x y x x x y x x(2) 两阶段法: Min ω=y 1+y 2St.⎪⎪⎩⎪⎪⎨⎧≥=≥=++=+-+=++0,).4,3,2,1(04263433214112321121y y j xj x x x y x x x y x x第二阶段,将表中y 1,y 2去掉,目标函数回归到Max z '=-4x 1-x 2+0x 3+0x 4第二章 线性规划的对偶理论与灵敏度分析(作业)2.7给出线性规划问题:Max z=2x 1+4x 2+x 3+x 4⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤++≤++≤+≤++)4,3,2,1(096628332143221421j x x x x x x x x x x x x j要求:(1)写出其对偶问题;(2)已知原问题最优解为X *=(2,2,4,0),试根据对偶理论,直接求出对偶问题的最优解。
运筹学复习一、单纯形方法(表格、人工变量、基础知识)线性规划解的情况:唯一最优解、多重最优解、无界解、无解。
其中,可行域无界,并不意味着目标函数值无界。
无界可行域对应着解的情况有:唯一最优解、多重最优解、无界解。
有界可行域对应唯一最优解和多重最优解两种情况。
线性规划解得基本性质有:满足线性规划约束条件的可行解集(可行域)构成一个凸多边形;凸多边形的顶点(极点)与基本可行解一一对应(即一个基本可行解对应一个顶点);线性规划问题若有最优解,则最优解一定在凸多边形的某个顶点上取得。
单纯形法解决线性规划问题时,在换基迭代过程中,进基的非基变量的选择要利用比值法,这个方法是保证进基后的单纯型依然在解上可行。
换基迭代要求除了进基的非基变量外,其余非基变量全为零。
检验最优性的一个方法是在目标函数中,用非基变量表示基变量。
要求检验数全部小于等于零。
“当x1由0变到45/2时,x3首先变为0,故x3为退出基变量。
”这句话是最小比值法的一种通俗的说法,但是很有意义。
这里,x1为进基变量,x3为出基变量。
将约束方程化为每个方程只含一个基变量,目标函数表示成非基变量的函数。
单纯型原理的矩阵描述。
在单纯型原理的表格解法中,有一个有趣的现象就是,单纯型表中的某一列的组成的列向量等于它所在的单纯型矩阵的最初的基矩阵的m*m矩阵与其最初的那一列向量的乘积。
最初基变量对应的基矩阵的逆矩阵。
这个样子:'1222 1 0 -32580 1 010 0 158P B P -⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦51=5所有的检验数均小于或等于零,有最优解。
但是如果出现非基变量的检验数为0,则有无穷多的最优解,这时应该继续迭代。
解的结果应该是:X *= a X 1*+(1-a)X 2* (0<=a<=1)说明:最优解有时不唯一,但最优值唯一;在实际应用中,有多种方案可供选择;当问题有两个不同的最优解时,问题有无穷多个最优解。
运筹学模型(一)本章重点:线性规划基础模型、目标规划模型、运输模型及其应用、图论模型、最小树问题、最短路问题复习要求:1. 进一步理解基本建模过程,掌握类比法、图示法以及问题分析、合理假设的内涵.2. 进一步理解数学模型的作用与特点.本章复习重点是线性规划基础模型、运输问题模型和目标规划模型. 具体说来,要求大家会建立简单的线性规划模型,把实际问题转化为线性规划模型的方法要掌握,当然比较简单. 运输问题模型主要要求善于将非线性规划模型转化为运输规化模型,这种转化后求解相当简单. 你至少把一个很实际的问题转化为用表格形式写出的模型,至于求解是另外一回事,一般不要求. 目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型. 另外,关于图论模型的问题涉及到最短路问题,具体说来用双标号法来求解一个最短路模型. 这之前恐怕要善于将一个实际问题转化为图论模型. 还有一个最小数的问题,该如何把一个网络中的最小数找到. 另外在个别场合可能会涉及一笔划问题.1. 营养配餐问题的数学模型m i Z n =C 1x 1+C 2x + C n x n⎧a 11x 1+a 12x 2+ +a 1n x n ≥b 1, ⎪⎪a 21x 1+a 22x 2+ +a 2n x n ≥b 2, ⎪ s ⋅t⋅⎨⎪a x +a x + +a x ≥b , m 22mn n m ⎪m 11⎪⎩x j ≥0(j =1, 2, , n或更简洁地表为m i Z n =∑C x jj =1n j⎧n ⎪∑a ij x j ≥b i ⎪j =1s ⋅t ⋅⎨⎪x ≥0(i =1, 2, , m j ⎪j =1, 2, , n ⎩其中的常数C j 表示第j 种食品的市场价格,a ij 表示第j 种食品含第i 种营养的数量,b i 表示人或动物对第i 种营养的最低需求量.2. 合理配料问题的数学模型有m 种资源B 1,B 2,…,B m ,可用于生产n 种代号为A 1,A 2,…,A n 的产品. 单位产品A j 需用资源B i 的数量为a ij ,获利为C j 单位,第i 种资源可供给总量为b i 个单位. 问如何安排生产,使总利润达到最大?设生产第j 种产品x j 个单位(j =1,2,…,n ),则有m a Z x =C 1x 1+C 2x 2+ +C n x n⎧a 11x 1+a 12x 2+ +a 1n x n ≤b 1, ⎪⎪a 21x 1+a 22x 2+ +a 2n x n ≤b l , ⎪ s ⋅t⋅⎨⎪a x +a x + +a x ≤b , m 22mn n m ⎪m 11⎪⎩x j ≥0(j =1, 2, , n或更简单地写为m a z x =∑Cj =1n j x j⎧n ⎪∑a ij x j ≤b i ⎪j =1 s ⋅t ⋅⎨i =1, 2, , m ⎛⎫⎪x ≥0 j =1, 2, , n ⎪⎪⎪j ⎝⎭⎩3. 运输问题模型运输问题也是一种线性规划问题,只是决策变量设置为双下标变量. 假如问题具有m 个产地和n 个销地,第i 个产地用A i 表示,其产量为a i (i =1,2,…,m ),第j 个销地用B j 表示,其销量为b j (j =1,2,…,n ),从A i 运往B j 的运价为c ij ,而写成为∑a i =1m i =∑b j =1n j 表示产销平衡. 那么产销平衡运输问题的一般模型可以min Z =∑∑c ij x iji =1j =1m n⎧n ⎪∑x ij =a i ⎪j =1⎪⎪m s ⋅t ⋅⎨∑x ij =b j ⎪i =1⎪⎛i =1, 2, , m ⎫⎪x ij ≥0 j =1, 2, , n ⎪⎪⎪⎝⎭⎩4. 目标规划模型某工厂生产代号为Ⅰ、Ⅱ的两种产品,这两种产品都要经甲、乙两个车间加工,并经检验与销售两部门处理. 已知甲、乙两车间每月可用生产工时分别为120小时和150小时,每小时费用分别为80元和20元,其它数据如下表表4-1工厂领导希望给出一个可行性生产方案,使生产销售及检验等方面都能达标.问题分析与模型假设经与工厂总经理交谈,确定下列几条:p 1:检验和销售费每月不超过4600元;p 2:每月售出产品I 不少于50件;p 3:两车间的生产工时充分利用(重要性权系数按两车间每小时费用比确定);p 4:甲车间加班不超过20小时;p 5:每月售出产品Ⅱ不少于80件;p 6:两车间加班总时数要有控制(对权系数分配参照第三优先级).模型建立设x 1,x 2分别为产品Ⅰ和Ⅱ的月产量,先建立一般约束条件组,依题设50x 1+30x 2≤4600x 1≥50 售出量x 2≥80 2x 1+x 2≤120 两车间总工时x 1+3x 2≤150+ 设d 1表检验销售费偏差,则希望d 1达最小,有p 1d 1+, 相应的目标约束为 5x 1+30x 2+d 1--d 1+ = 4600; --达最小,有p 2d 2, 相应的目标约束 d 2表产品I 售量偏差,则希望d 2-+x 1+d 2-d 2=50,以d 3、d 4表两车间生产工时偏差,则由于充分利用,故希望d 320=4:1,有--p 3(4d 3+d 4 . 相应的目标约束应为 --达最小,考虑到费用比例为80:, d 4-+-+=150, -d 42x 1+x 2+d 3-d 3=120和x 1+3x 2+d 4以d 5表甲车间加班偏差,则有+-+d 3+d 5-d 5=20, p 4d 5+, 相应目标约束为以d 6表产品Ⅱ售量偏差,则希望d 6达最小,有相应约束为-+x 2+d 6-d 6=80.++++表示,考虑到权系数,有p6(4d 3+d 4, 其目标约束由于利用超生+d 4- 最后优先级p 6可利用d 3产工时,已在工时限制中体现,于是得到该问题的目标规划模型为---+-++m i z n =p 1d 1++p 2d 2+p 3(4d 3+d 4 +p 4d 5+p 5d 6+p 6(4d 3+d 4 ⎧50x 1+30x 2+d 1--d 1+⎪-+x 1+d 2-d 2⎪⎪-+2x +x +d -d 1233⎪⎪-+s ⋅t ⋅⎨x 1+3x 2+d 4-d 4⎪+-+d +d -d 355⎪⎪x 2+d 6--d 6+⎪-+⎪⎩x 1, x 2≥0, d l , d l≥0=4600=50=120=150=20=80(l =1, 2, , 65. 最小树问题一个图中若有几个顶点及其边的交替序列形成闭回路,我们就说这个图有圈;若图中所有连顶点间都有边相接,就称该图是连通的;若两个顶点间有不止一条边连接,则称该图具有多重边. 一个图被称为是树意味着该图是连通的无圈的简单图. .在具有相同顶点的树中,总赋权数最小的树称为最小树.最小树的求法有两种,一种称为“避圈法”,一种是“破圈法”,两法各具优缺点,它们具有共同的特征——去掉图中的圈并且每次都是去掉圈中边权较大的边.6. 最短路问题的数学模型最短路问题一般描述如下:在一个图(或者说网络)中,给定一个始点v s 和一个终点v t ,求v s 到v t 的一条路,使路长最短(即路的各边权数之和最小).狄克斯屈(E.D.Dijkstra )双标号法该法亦称双标号法,适用于所有权数均为非负(即一切w ij ≥0 w ij 表示顶点v i 与v j 的边的权数)的网络,能够求出网络的任一点v s 到其它各点的最短路,为目前求这类网络最短路的最好算法.该法在施行中,对每一个点v j 都要赋予一个标号,并分为固定标号P (v j )和临时标号T (v j )两种,其含义如下:P (v j )——从始点v s 到v j 的最短路长;T (v j )——从始点v s 到v j 的最短路长上界.一个点v j 的标号只能是上述两种标号之一. 若为T 标号,则需视情况修改,而一旦成为P 标号,就固定不变了.开始先给始点v s 标上P 标号0,然后检查点v s ,对其一切关联边(v s ,vj )的终点v j ,给出v j 的T 标号w ij ;再在网络的已有T 标号中选取最小者,把它改为P 标号. 以后每次都检查刚得到P 标号那点,按一定规则修改其一切关联边终点的T 标号,再在网络的所有T 标号中选取最小者并把它改为P 标号. 这样,每次都把一个T 标号点改为P 标号点,因为网络中总共有n 个结点,故最多只需n -1次就能把终点v t 改为P 标号. 这意味着已求得了v s 到v t 的最短路.狄克斯屈标号法的计算步骤如下:1°令S ={v s }为固定标号点集,=V \{v s }为临时标号点集,再令P (v i =0,v t ∈S ; 2°检查点v i ,对其一切关联边(v i , vj )的终点v j∈,计算并令 min{T (v j , P (v i +w ij }⇒T (v j3°从一切v j∈中选取并令 min{T (v j }=T (v r ⇒T (v r 选取相应的弧(v i , vr ). 再令 S {v r }⇒S , \{v r }⇒=∅,则停止,P (v j 即v s 到v j 的最短路长,特别P (v t 即v s 到v t 的最短路长,而已选出 4°若的弧即给出v s 到各点的最短路;否则令v r ⇒v i ,返2°. 注意:若只要求v s 到某一点v t 的最短路,而没要求v s 到其他各点的最短路,则上述步骤4°可改为 4°若r = t 则结束,P (v r 即为所求最短路长;否则令v r ⇒v i ,返2°.。