运筹学简介
运筹学(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.用图解法求解下列两个变量的线性规划问题,指出问题是否具有唯一最优解,无穷多最优解或无可行解.
①
s.t,(答案:有唯一最优解 )
②
s.t,(答案:无可行解)
③
s,t,(答案:有无穷多最优解,maxS=66 )
第二章 单纯形方法
复习思考题:
2.试述单纯形方法的一般原理.
3.对应于基的单纯形表的四个部分的内容及计算.
4.利用单纯形法求解线性规划问题的基本思路是什么?
5.什么叫检验数?它与线性规划问题解的关系是什么?
6.把一个基本可行解转换成另一个较好的基本可行解的方法是在单纯形表中进行换基迭代中怎样确定进基变量?(答:负检验数中绝对值最大的所第应的基变量)和出基变量?(答;用最小比值原则求之)
用单纯形方法求解下列线性规划问题.
7,
s,t,(答案,
8,
s.t, (答案,)
9,
s.t,(答案, maxS 无界 )
10,
s.t,(答案,有无穷多最优解,其中之一为 )
分别用大法和两阶段法求解下列线性规划问题.
11,
s.t,(答案:无可行解)
12,
s.t,
(答案:有无穷多最优解,例如 )
13,
s.t,(答案:有可行解,最优解无界)
14,
s.t,
(答案:有唯一最优解 )
15,用改进单纯形法求解下列线性规划问题:
s.t,
(答案;经两次换基迭代得问题的最优解为
最优值为 )
第三章 线性规划问题的对偶理论
复习思考题:
16,什么是资源的影子价格,它同市场价格之间有何区别,研究影子价格的意义是什么?
17,试从经济上解释对偶问题及对偶变量的含义.
写出下列线性规划问题的对偶问题:
18,
s.t,(这是混合型规划)
无约束
19,
s.t,
20,
s.t,
无约束
21.试述对偶单纯形法的计算步骤,它的优点及应用的局限性.
22.已知线性规划问题:
s.t,
试应用对偶理论证明上述线性规划问题无最优解.
23.已知线性规划问题:
s.t,
应用对偶理论证明该问题最优解的目标函数值不大于25.
24.用对偶单纯形法求解下列线性规划问题;
①
s.t,
②
s.t,
③
s.t,
第四章 参数线性规划与灵敏度分析
25.分析下列参数规划问题中当变化时最优解的变化情况;
① ()
s.t,
(答案:时 ,时
时 )
②
s.t,
(答案,时
时
时 )
26.分析下列参数规划问题中,当变化时,最优解的变化情况:
① ()
s.t,
(答案,时,无可行解
时
时
时
②
s.t,
(答案,时,无可行解.
时
时
时
时,无可行解.
27.已知线性规划问题:
s.t,
用单纯形方法求解得最终单纯形如下表
试确定,(1) 当目标函数变为 时,最优解会出现什么变化?
(2) 当目标函数变为 时,在什么范围内变化,最优解不变?
(答案:(1) 新解
(2) 时,最优解不变,)
28,上题中 (1) 若第2个约束条件的右端项增大到32时,分析最优解的变化;(的灵敏度分析),(2) 若第2个约束条件变为 ,分析在什么范围内变化,表中基为最优基?
(答案,(1) 最优解为 (2) 时,最优解不变.
对三,四,五种情况的灵敏度分析不留作业.
第五章 运输问题
复习思考题:
29.试述运输问题数学模型的特征,为什么模型的个约束中最多只有个是独立的?
30.写出运输问题数学模型的约束条件的系数和其中变量的系数列向量的表达式.
31.试用最小元素法编制初始调运方案.(运输问题的表上作业法)
运筹学(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.用图解法求解下列两个变量的线性规划问题,指出问题是否具有唯一最优解,无穷多最优解或无可行解.
①
s.t,(答案:有唯一最优解 )
②
s.t,(答案:无可行解)
③
s,t,(答案:有无穷多最优解,maxS=66 )
第二章 单纯形方法
复习思考题:
2.试述单纯形方法的一般原理.
3.对应于基的单纯形表的四个部分的内容及计算.
4.利用单纯形法求解线性规划问题的基本思路是什么?
5.什么叫检验数?它与线性规划问题解的关系是什么?
6.把一个基本可行解转换成另一个较好的基本可行解的方法是在单纯形表中进行换基迭代中怎样确定进基变量?(答:负检验数中绝对值最大的所第应的基变量)和出基变量?(答;用最小比值原则求之)
用单纯形方法求解下列线性规划问题.
7,
s,t,(答案,
8,
s.t, (答案,)
9,
s.t,(答案, maxS 无界 )
10,
s.t,(答案,有无穷多最优解,其中之一为 )
分别用大法和两阶段法求解下列线性规划问题.
11,
s.t,(答案:无可行解)
12,
s.t,
(答案:有无穷多最优解,例如 )
13,
s.t,(答案:有可行解,最优解无界)
14,
s.t,
(答案:有唯一最优解 )
15,用改进单纯形法求解下列线性规划问题:
s.t,
(答案;经两次换基迭代得问题的最优解为
最优值为 )
第三章 线性规划问题的对偶理论
复习思考题:
16,什么是资源的影子价格,它同市场价格之间有何区别,研究影子价格的意义是什么?
17,试从经济上解释对偶问题及对偶变量的含义.
写出下列线性规划问题的对偶问题:
18,
s.t,(这是混合型规划)
无约束
19,
s.t,
20,
s.t,
无约束
21.试述对偶单纯形法的计算步骤,它的优点及应用的局限性.
22.已知线性规划问题:
s.t,
试应用对偶理论证明上述线性规划问题无最优解.
23.已知线性规划问题:
s.t,
应用对偶理论证明该问题最优解的目标函数值不大于25.
24.用对偶单纯形法求解下列线性规划问题;
①
s.t,
②
s.t,
③
s.t,
第四章 参数线性规划与灵敏度分析
25.分析下列参数规划问题中当变化时最优解的变化情况;
① ()
s.t,
(答案:时 ,时
时 )
②
s.t,
(答案,时
时
时 )
26.分析下列参数规划问题中,当变化时,最优解的变化情况:
① ()
s.t,
(答案,时,无可行解
时
时
时
②
s.t,
(答案,时,无可行解.
时
时
时
时,无可行解.
27.已知线性规划问题:
s.t,
用单纯形方法求解得最终单纯形如下表
试确定,(1) 当目标函数变为 时,最优解会出现什么变化?
(2) 当目标函数变为 时,在什么范围内变化,最优解不变?
(答案:(1) 新解
(2) 时,最优解不变,)
28,上题中 (1) 若第2个约束条件的右端项增大到32时,分析最优解的变化;(的灵敏度分析),(2) 若第2个约束条件变为 ,分析在什么范围内变化,表中基为最优基?
(答案,(1) 最优解为 (2) 时,最优解不变.
对三,四,五种情况的灵敏度分析不留作业.
第五章 运输问题
复习思考题:
29.试述运输问题数学模型的特征,为什么模型的个约束中最多只有个是独立的?
30.写出运输问题数学模型的约束条件的系数和其中变量的系数列向量的表达式.
31.试用最小元素法编制初始调运方案.(运输问题的表上作业法)
