运筹学讲稿_运筹学简介

运筹学简介 运筹学( Operations research)是一门新兴的应用学科.由于它所研究的对象极其广泛有 着许多不同的定义 1976年美国运筹学会定义:“运筹学是研究用科学方法来决定在资源不充分的情况下如 何最好地设计人一机系统,并使之最好地运行的一门学科” 1978年联邦德国的科学词典上定义:“运筹学是从事决策模型的数学解法的一门学科” 前者着重于处理实际问题,而对于“科学方法”则未加说明,后者强调数字解,而注重数学 方法 英国运筹学杂志认为:“运筹学是运用科学方法(特别是数学方法)来解决那些在工业、商 业、政府部门、国防部门中有关人力、机器、物资、金钱等的大型系统的指挥和管理方面所 出现的问题,其目的是帮助管理者科学地决定其策略和行动” 有人则认为运筹学是近代应用数学的一个分支,主要是将生产、管理中出现的一些带普遍 性的运筹问题加以提炼,然后利用数学方法去解决.前者提供模型,后者提供理论和方法,前 者是后者发展的基础,后者是事前者进行工作的科学依据.其实运筹学(缩写0.R)是两者有 机结合而成的.英文 operations research(运筹学)一词的原意是作战研究.早在1938年英 国空军就有了飞机定位和控制系统,并在沿海有几个雷达站,可以用来发现敌机,但在一次防 空大演习中发现,由这些雷达送来的(常常是互相矛盾的)信息,需要加以协调和关联,以改进 作战效果,这一任务的提出即产生“运筹学”一词,英国空军成立了运筹学小组,主要从事警 报和控制系统的研究 我国运筹学的先驱者从《史记.高祖本记》:“夫运筹策帷幄之中,决胜于千里之外”一语 摘取“运筹”二字作为这门科学的名称,既显示其军事的起源,也表明其萌芽早已出现在我 运筹学在20世纪40年代以后得到迅速发展,其原因大致有以下几个方面:①大规模新兴工 业的出现,同行业间的竞争加剧,迫切需要对大型工业的复杂的生产结构和管理关系进行研 究,作出科学的分析和设计;②产品更新换代的加速使得生产者必须密切注意市场情况和消 费者的心理分析;③快速计算机的出现,一些复杂的问题能得到及时解决而使运筹学具有现 实意义 运筹学有广阔的应用领域,它已渗透到诸如服务、库存、搜索、人口、对抗、控制、时间表、 资源分配、厂址定位、能源、设计、生产、可靠性、设备维修和更换、检验、决策、规划、 管理、行政、组织、信息处理及恢复、投资、交通市场分析、区域规划、预测、教育、医疗 卫生各个方面 第一本运筹学杂志和英国的运筹学会分别于1950年和1953年出现.世界上第一个运筹学 会“美国运筹学会”于1952年成立,1959年成立了国际运筹学会联盟,到1986年已有35个 会员国和6个兄弟学会,会员3万多人,大多数会员国都办有自己的杂志.“中国数学会运筹 学会”于1980年成立,于1982年加入国际运筹学会联盟并创刊《运筹学杂志》 为本书《数学规划方法》撰写序言的是中国数学会理事、中国运筹学会常务理事、西北运筹 学会副理事长、兰州交通大学应用数学研究所所长张忠辅教授.他已将该书推荐到兰州交大 和兰州理工大数学建模课的参考教材.2003年3月我也将该书作为《运筹学》的主教材向天 水师院数学系数学与应用数学专业本科生的选修课试讲,效果良好.这次重新使用,对内容作 了调整,并纠正了书中的印刷错误,除去年补讲的对策论和决策分析外又增了加运筹学的新 内容.欢迎同学们在使用中提出批评和建议,以便修订出版为《运筹学》正式教材 运筹学包含以下一些分支:数学规划(它又包含线性规划;非线性规划;整数规划、混合整数 规划、0-1规划;组合规划(组合最优化);随机规划;多目标规划;几何规划;动态规划等);图

1 运筹学简介 运筹学(Operations research)是一门新兴的应用学科.由于它所研究的对象极其广泛有 着许多不同的定义. 1976 年美国运筹学会定义:“运筹学是研究用科学方法来决定在资源不充分的情况下如 何最好地设计人 一 机系统,并使之最好地运行的一门学科”. 1978 年联邦德国的科学词典上定义:“运筹学是从事决策模型的数学解法的一门学科”. 前者着重于处理实际问题,而对于“科学方法”则未加说明,后者强调数字解,而注重数学 方法. 英国运筹学杂志认为:“运筹学是运用科学方法(特别是数学方法)来解决那些在工业、商 业、政府部门、国防部门中有关人力、机器、物资、金钱等的大型系统的指挥和管理方面所 出现的问题,其目的是帮助管理者科学地决定其策略和行动”. 有人则认为运筹学是近代应用数学的一个分支,主要是将生产、管理中出现的一些带普遍 性的运筹问题加以提炼,然后利用数学方法去解决.前者提供模型,后者提供理论和方法,前 者是后者发展的基础,后者是事前者进行工作的科学依据.其实运筹学(缩写 O.R)是两者有 机结合而成的.英文 operations research(运筹学)一词的原意是作战研究.早在 1938 年英 国空军就有了飞机定位和控制系统,并在沿海有几个雷达站,可以用来发现敌机,但在一次防 空大演习中发现,由这些雷达送来的(常常是互相矛盾的)信息,需要加以协调和关联,以改进 作战效果,这一任务的提出即产生“运筹学”一词,英国空军成立了运筹学小组,主要从事警 报和控制系统的研究. 我国运筹学的先驱者从《史记.高祖本记》:“夫运筹策帷幄之中,决胜于千里之外”一语 摘取“运筹”二字作为这门科学的名称,既显示其军事的起源,也表明其萌芽早已出现在我 国. 运筹学在20世纪40年代以后得到迅速发展,其原因大致有以下几个方面:①大规模新兴工 业的出现,同行业间的竞争加剧,迫切需要对大型工业的复杂的生产结构和管理关系进行研 究,作出科学的分析和设计;②产品更新换代的加速使得生产者必须密切注意市场情况和消 费者的心理分析;③快速计算机的出现,一些复杂的问题能得到及时解决而使运筹学具有现 实意义. 运筹学有广阔的应用领域,它已渗透到诸如服务、库存、搜索、人口、对抗、控制、时间表、 资源分配、厂址定位、能源、设计、生产、可靠性、设备维修和更换、检验、决策、规划、 管理、行政、组织、信息处理及恢复、投资、交通市场分析、区域规划、预测、教育、医疗 卫生各个方面. 第一本运筹学杂志和英国的运筹学会分别于 1950 年和 1953 年出现.世界上第一个运筹学 会“美国运筹学会”于 1952 年成立,1959 年成立了国际运筹学会联盟,到 1986 年已有 35 个 会员国和 6 个兄弟学会,会员 3 万多人,大多数会员国都办有自己的杂志.“中国数学会运筹 学会”于 1980 年成立,于 1982 年加入国际运筹学会联盟并创刊《运筹学杂志》. 为本书《数学规划方法》撰写序言的是中国数学会理事、中国运筹学会常务理事、西北运筹 学会副理事长、兰州交通大学应用数学研究所所长张忠辅教授.他已将该书推荐到兰州交大 和兰州理工大数学建模课的参考教材.2003 年 3 月我也将该书作为《运筹学》的主教材向天 水师院数学系数学与应用数学专业本科生的选修课试讲,效果良好.这次重新使用,对内容作 了调整,并纠正了书中的印刷错误,除去年补讲的对策论和决策分析外又增了加运筹学的新 内容.欢迎同学们在使用中提出批评和建议,以便修订出版为《运筹学》正式教材. 运筹学包含以下一些分支:数学规划(它又包含线性规划;非线性规划;整数规划、混合整数 规划、0-1 规划;组合规划(组合最优化);随机规划;多目标规划;几何规划;动态规划等);图

论与网络流;对策论;决策分析;排队论与可靠性数学理论;库存论;搜索论;模拟等. 我们不可能在短短的十周时间里仅用60学时去讲清运筹学的各个分支,只能择其最基本 的分支在讲明原理的同时,侧重于方法的使用,为同学们进一步学习运筹学打下基础.运筹学 是应用数学专业的一门重要而实用的课程,尽管是一门选修课且在面临双向选择的毕业前夕, 还是请同学们静下心来,认真学好这门课.著名数学家华罗庚教授说过:学数学不做作业,好 比入宝山而空返.因此完成一定数量的习题是必不可少的.为配合教材,这里选编了少量的习 题,务请大家按时完成 上篇线性规划( Linear programming 第一章线性规划问题 1.用图解法求解下列两个变量的线性规划问题,指出问题是否具有唯一最优解,无穷多最 优解或无可行解. ①mnS=6x1+4x x1+x2 t 3x,+4x,≥1.5 (答案:有唯 最优解 x12x2≥0 x1=112,x2=0,mnS=3) ②mxS=4x1+8x2 2x,+2x,<10 s. t x1+x2≥8 (答案:无可行解) ≥0 ③maxS=3x1+9x x1+3x,≤22 <4 (答案:有无穷多最优解.maxS=66) 2x1-5x,≤0 x1,x2 第二章单纯形方法

2 论与网络流;对策论;决策分析;排队论与可靠性数学理论;库存论;搜索论;模拟等. 我们不可能在短短的十周时间里仅用 60 学时去讲清运筹学的各个分支,只能择其最基本 的分支在讲明原理的同时,侧重于方法的使用,为同学们进一步学习运筹学打下基础.运筹学 是应用数学专业的一门重要而实用的课程,尽管是一门选修课且在面临双向选择的毕业前夕, 还是请同学们静下心来,认真学好这门课.著名数学家华罗庚教授说过:学数学不做作业,好 比入宝山而空返.因此完成一定数量的习题是必不可少的.为配合教材,这里选编了少量的习 题,务请大家按时完成. 上篇 线性规划 (Linear programming) 第一章 线性规划问题 1.用图解法求解下列两个变量的线性规划问题,指出问题是否具有唯一最优解,无穷多最 优解或无可行解. ① min 6 1 4 2 S = x + x s.t.       +  +  , 0 3 4 1.5 2 1 1 2 1 2 1 2 x x x x x x ( 答 案 : 有 唯 一 最 优 解 x1 =1/ 2, x2 = 0,min S = 3 ) ② max 4 1 8 2 S = x + x s.t.       − +  +  , 0 8 2 2 10 1 2 1 2 1 2 x x x x x x (答案:无可行解) ③ max 3 1 9 2 S = x + x s .t .           −   − +  +  , 0 2 5 0 6 4 3 22 1 2 1 2 2 1 2 1 2 x x x x x x x x x (答案:有无穷多最优解. maxS=66 ) 第二章 单纯形方法

复习思考题 2.试述单纯形方法的一般原理 3对应于基B的单纯形表的四个部分的内容及计算 4利用单纯形法求解线性规划问题的基本思路是什么? 5什么叫检验数?它与线性规划问题解的关系是什么? 6把一个基本可行解转换成另一个较好的基本可行解的方法是在单纯形表中进行换基迭 代中怎样确定进基变量?(答:负检验数中绝对值最大的所第应的基变量)和出基变量?(答;用最 小比值原则求之) 用单纯形方法求解下列线性规划问题 7. max S=3x,+5x2 4 2x2≤12 3x1+2x2≤18 (答案:X=(2,6,2,00),mxS=36) x1,x,≥0 8. max S=2x,-x+x x,+x2+x 10 (答案:X=(15,50,10,0,0)) x1+x2-x3≤20 ≥0 9.mxS=6x1+2x2+10x3+8x4 5x1+6x2-4x3-4x4220 3x1-3x2+2x3+8x4≤25 S t (答案:X=(0,5,200.0.70), 4x1-2x2+x3+3x4≤10 0 axS无界) 10.maxS=x,+6x,+4 x1+2x2+2x3≤13 4x1-4x2+x3≤20 答案:有无穷多最优解,其中之一为 x1+2x2+x3≤17 ≥1,x2≥2,x3≥3 x1=11/2,x2=9/4 分别用大M法和两阶段法求解下列线性规划问题 S=4x1+5

3 复习思考题: 2.试述单纯形方法的一般原理. 3.对应于基 B 的单纯形表的四个部分的内容及计算. 4.利用单纯形法求解线性规划问题的基本思路是什么? 5.什么叫检验数?它与线性规划问题解的关系是什么? 6.把一个基本可行解转换成另一个较好的基本可行解的方法是在单纯形表中进行换基迭 代中怎样确定进基变量?(答:负检验数中绝对值最大的所第应的基变量)和出基变量?(答;用最 小比值原则求之) 用单纯形方法求解下列线性规划问题. 7. max 3 1 5 2 S = x + x s. t.         +    , 0 3 2 18 2 12 4 1 2 1 2 2 1 x x x x x x (答案: X = (2,6,2,0,0) ,max S = 36) T 8. max 2 1 2 3 S = x − x + x s.t .         + −  − +  + +  , , 0 20 2 10 3 60 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x x (答案: T X = (15,5,0,10,0,0) ) 9. max 6 1 2 2 10 3 8 4 S = x + x + x + x s.t.         − + +  − + +  + − −  , , , 0 4 2 3 10 3 3 2 8 25 5 6 4 4 20 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 x x x x x x x x x x x x x x x x (答案: (0,5,20,0,0,70) , T X = maxS 无界 ) 10. max 1 6 2 4 3 S = x + x + x s.t.           + +  − +  − + +  1, 2, 3 2 17 4 4 20 2 2 13 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x x (答案: 有无穷多最优解,其中之一为 x1 =11/ 2, x2 = 9/ 4, x3 = 7 ) 分别用大 M 法和两阶段法求解下列线性规划问题. 11. max 4 1 5 3 S = x + x + x

X, 18 2 4 St (答案无可行解) x x3 0(j=1,2,3) 12. max S=2x,+x2+x3 4x1+2x2+2x3≥4 2x1+4x2≤20 ≥0(j=1,2,3) (答案有无穷多最优解,例如X)=(4,0,0) X2)=(00,8)) 8x1+6x2≥2 4x1+6x,≥-12 S t (答案:有可行解,最优解无界) 2x,≥4 S=x1+2x,+3 x1+2x2+3x3=15 S. t x1+2x2+x3+x4=10 (答案:有唯一最优解X=(5/25/2,5/2,0) 15.用改进单纯形法求解下列线性规划问题 max s=4x +2x x1+2x2≤6 x1+x2≤9 t. 3x1-x2≤15 (答案经两次换基迭代得问题的最优解为X=(6,360 最优值为maxS=4×6+2×3=30)

4 s.t.         = + − = +  + +  0( 1,2,3) 5 2 4 3 2 18 1 2 3 1 2 1 2 3 x j x x x x x x x x j (答案:无可行解) 12. max 2 1 2 3 S = x + x + x s.t.         = + +  +  + +  0( 1,2,3) 4 8 2 16 2 4 20 4 2 2 4 1 2 3 1 2 1 2 3 x j x x x x x x x x j (答案:有无穷多最优解,例如 T X (4,0,0) (1) = T X (0,0,8) (2) = ) 13. max 1 2 S = x + x s.t.          +  − +  , 0 2 4 4 6 12 8 6 24 1 2 2 1 2 1 2 x x x x x x x (答案:有可行解,最优解无界) 14. max 1 2 2 3 3 4 S = x + x + x − x s.t.         = + + + = + + = + + = 0( 1,2,3,4) 2 10 2 5 20 2 3 15 1 2 3 4 1 2 3 1 2 3 x j x x x x x x x x x x j (答案:有唯一最优解 T X (5/ 2,5/ 2,5/ 2,0) * = ) 15. 用改进单纯形法求解下列线性规划问题: max 4 1 2 2 S = x + x s.t.         −  +  − +  , 0 3 15 9 2 6 1 2 1 2 1 2 1 2 x x x x x x x x (答案;经两次换基迭代得问题的最优解为 T X (6,3,6,0,0) * = 最优值为 max S = 46+ 23 = 30 )

第三章线性规划问题的对偶理论 复习思考题 16.什么是资源的影子价格,它同市场价格之间有何区别研究影子价格的意义是什么? 17.试从经济上解释对偶问题及对偶变量的含义 写出下列线性规划问题的对偶问题: 18.mnS=3x1+2x2-3x3+4x4 xI 2x,+3x,+4x,≤3 x2+3x3+4x4 (这是混合型规划) 2 3x,-7x3-4x4=2 x1≥0,x4≤0, x2, x 无约束 19. max s= 2x, +x 6x,+2x<24 S. t x1+x2≤5 x1,x2 0 20.mnS=-5x,-6x,-7 x1+5x2-3x3≥15 x1-6x2+10x3≤20 S t R-x,-x x1≤0,x2≥0,x3 无约束 21试述对偶单纯形法的计算步骤,它的优点及应用的局限性 22已知线性规划问题 max S=x,+x2 x2+x3≤2 S t x1+x2-x3 ≥0 试应用对偶理论证明上述线性规划问题无最优解 23已知线性规划问题 S=4x1+7x,+2

5 第三章 线性规划问题的对偶理论 复习思考题: 16. 什么是资源的影子价格,它同市场价格之间有何区别,研究影子价格的意义是什么? 17. 试从经济上解释对偶问题及对偶变量的含义. 写出下列线性规划问题的对偶问题: 18. min 3 1 2 2 3 3 4 4 S = x + x − x + x s.t.          − − − = + +  − − + +  1 4 2 3 1 2 3 4 2 3 4 1 2 3 4 0, 0, , 2 3 7 4 2 3 4 5 2 3 4 3 x x x x x x x x x x x x x x x (这是混合型规划) 无约束 19. max 2 1 2 S = x + x s.t.         +  +   , 0 5 6 2 24 5 15 1 2 1 2 1 2 2 x x x x x x x 20. min 5 1 6 2 7 3 S = − x − x − x s.t.          − − = − − − +  − + −  1 2 3 1 2 3 1 2 3 1 2 3 0, 0, 5 5 6 10 20 5 3 15 x x x x x x x x x x x x 无约束 21.试述对偶单纯形法的计算步骤,它的优点及应用的局限性. 22.已知线性规划问题: max 1 2 S = x + x s.t.       − + −  − + +  , , 0 2 1 2 1 2 3 1 2 3 1 2 3 x x x x x x x x x 试应用对偶理论证明上述线性规划问题无最优解. 23.已知线性规划问题: max 4 1 7 2 2 3 S = x + x + x