(精品)运筹学1.1.9.ppt

《(精品)运筹学1.1.9.ppt》由会员分享，可在线阅读，更多相关《(精品)运筹学1.1.9.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 运 筹 学 (Operations Research)主讲：刘春丽Office:红瓦楼 729Mail:课程概述教材：运筹学运筹学赵可培赵可培 上海财经大学出版社上海财经大学出版社参考教材 运筹学运筹学胡运权胡运权 清华大学出版社清华大学出版社考评：平时成绩 30%期末成绩 70%答疑时间：周五上午9:3011:30绪言绪言 1.什么是运筹学什么是运筹学?运用科学的数量方法运用科学的数量方法 主要是数主要是数学模型学模型，研究对人力、财力和物力，研究对人力、财力和物力进行合理的筹划和运用，以寻求管理进行合理的筹划和运用，以寻求管理及决策最优化的综合性学科及决策最优化的综合性学科。是系统工程学

2、和现代管理科学中是系统工程学和现代管理科学中的一种基础理论和不可缺少的方法、的一种基础理论和不可缺少的方法、手段和工具。运筹学已被应用到各种手段和工具。运筹学已被应用到各种管理工程中。管理工程中。发发展展经经济济科学技术：科学技术是第一生产力科学技术：科学技术是第一生产力科学管理科学管理 决策决策定性分析方法定性分析方法定量分定量分析方法析方法概率统计分析概率统计分析方法方法最优化分析方法最优化分析方法（运筹学）（运筹学）其它数学模型分其它数学模型分析方法析方法、运筹学的发展历史：、运筹学的发展历史：（）运筹学的思想在我国很早就产生了，（）运筹学的思想在我国很早就产生了，如公元前四世纪春秋战国

3、时如公元前四世纪春秋战国时 “田忌赛马田忌赛马”的的故事。故事。（）在我们的日常生活，工作中也在有意（）在我们的日常生活，工作中也在有意无意地运用运筹学的朴素的思想与方法。无意地运用运筹学的朴素的思想与方法。（）作为一门学科，是社会生产力发展到（）作为一门学科，是社会生产力发展到一定程度的产物，产生于第二次世界大战期间，一定程度的产物，产生于第二次世界大战期间，应用到军事系统。应用到军事系统。(Operations Research)（）（）二次大战后，英美等国把对运筹学二次大战后，英美等国把对运筹学的研究从军事部门转移到工业，商业等部门，的研究从军事部门转移到工业，商业等部门，对企业管理作出

4、了很大的贡献。对企业管理作出了很大的贡献。（）（）近年来，随着计算机技术的飞速发近年来，随着计算机技术的飞速发展，运筹学本身的发展与完善，它已应用到展，运筹学本身的发展与完善，它已应用到今日经济管理的各个领域，发挥着极为重要今日经济管理的各个领域，发挥着极为重要的作用。的作用。作为一门较年青的学科，运筹学本身仍作为一门较年青的学科，运筹学本身仍在不断的发展与完善中新的模型，新的算在不断的发展与完善中新的模型，新的算法，新的思想仍在不断涌现。法，新的思想仍在不断涌现。现实世界系统现实世界系统假定的数学模型假定的数学模型 现实世界现实世界对复杂的现实世界系统，进行归纳，分析，对复杂的现实世界系统，

5、进行归纳，分析，整理，从中抽象出数学模型，然后利用数学方整理，从中抽象出数学模型，然后利用数学方法，以计算机为工具，求解出最优的方案，并法，以计算机为工具，求解出最优的方案，并可对得出的方案作种种分析。可对得出的方案作种种分析。运筹学研究的基本思想和方法：运筹学研究的基本思想和方法：计算计算由于客观世界的多样性，复杂性，对不由于客观世界的多样性，复杂性，对不同的问题，需归结出不同类型的数学模型，同的问题，需归结出不同类型的数学模型，从而有不同的计算方法，所以运筹学按从而有不同的计算方法，所以运筹学按不同的数学模型类型有很多分支。不同的数学模型类型有很多分支。如如“线性规划线性规划”、“运输问题

6、运输问题”、“目目标规划标规划”、“动态规划动态规划”、“整数规划整数规划”、“图与网络图与网络”、“存储问题存储问题”、“决策和对决策和对决策决策”、“排队论排队论”和和“模拟模拟”等。等。运筹学的主要分支：运筹学的主要分支：线性规划是运筹学中研究的比较早线性规划是运筹学中研究的比较早而比较成熟的一个分支。而比较成熟的一个分支。线性规划是运线性规划是运筹学中应用的最广泛的一个分支，所以线筹学中应用的最广泛的一个分支，所以线性规划是运筹学中最重要的一个分支。性规划是运筹学中最重要的一个分支。所谓线性规划问题是在某一个决策目标所谓线性规划问题是在某一个决策目标下（利润最大或成本最小），将有限的资

7、源下（利润最大或成本最小），将有限的资源最有效地分配到各个经济活动中去的一种数最有效地分配到各个经济活动中去的一种数学模型。学模型。第一章线性规划第一章线性规划 (Linear Programming)通常在线性规划中讨论的决策问题，通常在线性规划中讨论的决策问题，1。问题往往有若干个（有限或无限）决策方案。问题往往有若干个（有限或无限）决策方案可供选择，需要确定的决策方案或未知数即称为可供选择，需要确定的决策方案或未知数即称为决策决策变量。变量。2。把决策要达到的目标（只能是一个）表示成。把决策要达到的目标（只能是一个）表示成这些决策变量即可供选择的决策方案的函数，称为这些决策变量即可供选择

8、的决策方案的函数，称为目目标函数标函数。3。在现实目标函数最优化的过程中，必然会有。在现实目标函数最优化的过程中，必然会有各种客观的限制条件。它们是有关决策方案（变量）各种客观的限制条件。它们是有关决策方案（变量）的等式或不等式，称为的等式或不等式，称为约束条件。约束条件。线性规划模型要求这些函数及约束条件都是决策线性规划模型要求这些函数及约束条件都是决策变量的线性函数或线性方程。变量的线性函数或线性方程。1.1线性规划的数学模型及其标准形式线性规划的数学模型及其标准形式一、建立决策问题数学模型的一般方法。一、建立决策问题数学模型的一般方法。1、确定决策变量和有关参数、确定决策变量和有关参数

9、决策什么？有那些可供选择的方案？将决策什么？有那些可供选择的方案？将不同的选择方案数量化，设成决策变量。不同的选择方案数量化，设成决策变量。2、确定目标函数、确定目标函数 决策问题的决策目标是什么？它们是决决策问题的决策目标是什么？它们是决策变量（各种可选方案）的函数。（本章线策变量（各种可选方案）的函数。（本章线性规划讨论的数学模型仅有一个决策目标）性规划讨论的数学模型仅有一个决策目标）3、确定约束或限制条件（等式或不等式、确定约束或限制条件（等式或不等式方程组）方程组）二、线性规划问题的举例：二、线性规划问题的举例：例例1.1 (生产安排问题生产安排问题)假定某工厂生产甲，乙，假定某工厂生

10、产甲，乙，丙三种产品，都要经过三种不同的工序加工。每一件丙三种产品，都要经过三种不同的工序加工。每一件产品所需要的加工时间（分钟）和每天对各道工序的产品所需要的加工时间（分钟）和每天对各道工序的加工能力（分钟）以及销售各种产品的单位利润如下加工能力（分钟）以及销售各种产品的单位利润如下表：假定所生产的三种产品都能全部售出，问这三种表：假定所生产的三种产品都能全部售出，问这三种产品每天要各生产多少件才能使获得的利润最大？产品每天要各生产多少件才能使获得的利润最大？工序工序 每件产品加工时间（分钟）每件产品加工时间（分钟）每天加工能力每天加工能力 甲产品甲产品 乙产品乙产品 丙产品丙产品 （分钟）

11、（分钟）一一 二二 三三 利润利润(元元)工序工序 每件产品加工时间（分钟）每件产品加工时间（分钟）每天加工能力每天加工能力 甲产品甲产品 乙产品乙产品 丙产品丙产品 （分钟）（分钟）一一 二二 三三 利润利润(元元)解：解：设设 X1、X2、X3 是是 甲，乙，丙三种产品的甲，乙，丙三种产品的产量，产量，Z 是工厂的总利润。那么是工厂的总利润。那么 Z=3X1+2X2+5X3这里这里 Z 称为目标函数，而称为目标函数，而 X1、X2、X3称为决策称为决策变量。由于各种产品在三道工序的加工时间不能超过变量。由于各种产品在三道工序的加工时间不能超过现有的加工能力，所以现有的加工能力，所以，对于第

12、一道工序，有：对于第一道工序，有：X1+2X2+X3=430 对于第二道工序，有：对于第二道工序，有：3X1 +2X3=460 对于第三道工序，有：对于第三道工序，有：X1+4X2 =0，X2=0，X3=0这些称为决策变量这些称为决策变量非负性约束条件非负性约束条件。工序工序 每件产品加工时间（分钟）每件产品加工时间（分钟）每天加工能力每天加工能力 甲（甲（X1）乙（乙（X2）丙（丙（X3）（分钟）分钟）一一 二二 三三 利润利润(元元)所以这个问题就是要求出所以这个问题就是要求出 X1、X2、X3，它们它们满足以上约束条件，并使满足以上约束条件，并使 Z=3X1+2X2+5X3 的值的值最大

13、。该问题的数学模型为：最大。该问题的数学模型为：求求 Z=3X1+2X2+5X3 的最大值的最大值约束条件约束条件 X1+2X2+X3=430 3X1 +2X3=460 X1+4X2 =0，X2=0，X3=0 该类数学模型由一个目标函数，若干个约束条该类数学模型由一个目标函数，若干个约束条件以及决策变量的非负性约束条件组成。件以及决策变量的非负性约束条件组成。例例 1.2（营养搭配问题）。如果有甲，乙，（营养搭配问题）。如果有甲，乙，丙，丁四种食品，单价各不相同，都含有不同成分丙，丁四种食品，单价各不相同，都含有不同成分的维生素，其含量和单价如下表：的维生素，其含量和单价如下表：维生素维生素

14、单位单位 甲甲 乙乙 丙丙 丁丁 每人每天每人每天 最低需要最低需要国际单位国际单位 1 000 1 500 1 750 3 250 4 000 毫克毫克 0.6 0.27 0.68 0.8 1 C 毫克毫克 17.5 7.5 0 80 30单价单价(元元)0.8 0.5 0.9 1.5 现在我们希望每天得到的维生素不少于所规定现在我们希望每天得到的维生素不少于所规定的最低需要量，问应该如何搭配各种食品才能使所的最低需要量，问应该如何搭配各种食品才能使所花的费用最少？花的费用最少？解：设解：设 X1、X2、X3和和 X4 是每天采购甲、乙、丙、是每天采购甲、乙、丙、丁四种食品的数量，丁四种食品

15、的数量，M是每天采购食品的费用，那么是每天采购食品的费用，那么 M=0.8X1+0.5X2+0.9X3+1.5X4（求最小值）求最小值）约束条件：约束条件：1 000X1+1 500X2+1 750X3+3250X4=4 000:A 0.6X1+0.27X2+0.68X3+0.3X4=1 :B 17.5X1+7.5X2+30X4=30 :C X1,X2,X3,X4=0维生素维生素 单位单位 甲甲 乙乙 丙丙 丁丁 每人每天每人每天 X1 X2 X3 X4 最低需要最低需要国际单位国际单位 1 000 1 500 1 750 3 250 4 000 毫克毫克 0.6 0.27 0.68 0.8

16、1 C 毫克毫克 17.5 7.5 0 80 30单价单价(元元)0.8 0.5 0.9 1.5所以这个问题是要求出所以这个问题是要求出X1，X2，X3，X4，它，它们满足以上的约束条件并使目标函数们满足以上的约束条件并使目标函数M的值最小。的值最小。该问题的数学模型是：该问题的数学模型是：求求M=0.8X1+0.5X2+0.9X3+1.5X4 的最小值的最小值约束条件：约束条件：1 000X1+1 500X2+1 750X3+3250X4=4 000 :A 0.6X1+0.27X2+0.68X3+0.3X4=1 :B 17.5X1+7.5X2+30X4=30 :C X1,X2,X3,X4=0

17、定单号码宽（米）定单号码宽（米）长（米）长（米）1 0.5 1 000 2 0.7 3 000 3 0.9 2 000 该厂生产米和米两种标准宽度的卷该厂生产米和米两种标准宽度的卷纸。假定卷纸的长度无限制，即可以连接起纸。假定卷纸的长度无限制，即可以连接起来达到所需要的长度，问应如何切割才能使来达到所需要的长度，问应如何切割才能使切割损失的面积最小？切割损失的面积最小？例例 1.3 (切割损失问题切割损失问题)。假定某个造纸厂。假定某个造纸厂接到三份订购卷纸的定单，其长和宽的要接到三份订购卷纸的定单，其长和宽的要求如下：求如下：解：解：每一种标准卷纸可以有好几种切每一种标准卷纸可以有好几种切割

18、的方式。例如割的方式。例如 米宽的卷纸可以切成四个米宽的卷纸可以切成四个 0.5 米宽的卷纸，也可以切成二个米宽的卷纸，也可以切成二个 0.5 米宽和米宽和一个一个 0.9 米宽的卷纸，同时产生米宽的卷纸，同时产生 0.1米宽的边米宽的边上的切割损失等等。上的切割损失等等。设设ij是第是第 i 种标准卷纸按照第种标准卷纸按照第 j 种方式种方式的切割的长度。那么两种标准卷纸所有可能的切割的长度。那么两种标准卷纸所有可能采用的切割方式及其边上的切割损失如下表采用的切割方式及其边上的切割损失如下表。宽度宽度 1米宽卷纸米宽卷纸 米宽卷纸米宽卷纸 需要量需要量（米）（米）X11 X12 X13 X2

19、1 X22 X23 X24 X25 X26 (米米)0.52 0 0 4 2 2 1 0 0 1 000 0.7 0 1 0 0 1 0 2 1 0 3 000 0.9 0 0 1 0 0 1 0 1 2 2 000 剩余宽剩余宽 0 0.3 0.1 0 0.3 0.1 0.1 0.4 0.2 0.70.3X12X220.70.30.50.51米米2米米 设设S1、S2、S3分别是把标准卷纸切成分别是把标准卷纸切成0.5米、米、0.7米、米、0.9米宽的纸，去掉客户所需要的长度米宽的纸，去掉客户所需要的长度后的剩余长度，而是总的切割损失后的剩余长度，而是总的切割损失，0.90.70.4如如X2

20、53000米米可得到可得到0.9宽度的纸宽度的纸3000米，米，0.7宽度的宽度的纸纸3000米，而客户需要的米，而客户需要的0.9宽度的纸只有宽度的纸只有2000米，造成米，造成0.9米宽的纸的长度上米宽的纸的长度上1000米米的浪费。的浪费。1000米米于是：于是：Z=0.3X12+0.1X13+0.3X22+0.1X23+0.1X24+0.4X25+0.2X26+0.5S1+0.7S2+0.9S3约束条件是：约束条件是：2X11+4X21+2X22+2X23+X24-S1=1 000 X12+X22+2X24+X25 -S2=3 000 X13+X23+X25+2X26 -S3=2 00

21、0 Xij=0,Si=0,对一切对一切 i和和 j。所以这个问题就是要求出上面所规定的所以这个问题就是要求出上面所规定的各个各个ij和和i，它们满足以上的约束条件并使它们满足以上的约束条件并使的值最小。的值最小。车间车间 每班进料数（公斤）每班进料数（公斤）每班产量（个数）每班产量（个数）第第 1种原材料种原材料 第第 2种原材料种原材料 A零件零件 B零件零件 甲甲(X1)8 6 7 5 乙乙(X2)5 9 6 9 丙丙(X3)3 8 8 4 现有量现有量 100 200 例例 1.4 （产品配套问题）假定一个工厂的甲、（产品配套问题）假定一个工厂的甲、乙、丙三个车间生产同一种产品，乙、丙三

22、个车间生产同一种产品，每件产品包括四每件产品包括四个零件和三个零件。这两种零件由两种不同的个零件和三个零件。这两种零件由两种不同的原材料制成，原材料制成，而这两种原材料的现有数额分别是而这两种原材料的现有数额分别是100公斤和公斤和200公斤。每个生产班的原材料需要量和公斤。每个生产班的原材料需要量和零件产量如下：零件产量如下：问这三个车间各应开多少班才能问这三个车间各应开多少班才能使这种产品的配套数达到最大？使这种产品的配套数达到最大？解：设解：设X1、X2、X3是甲、乙、丙是甲、乙、丙三个车间所开的生产班数。三个车间所开的生产班数。由于原材料的限制，故约束条件由于原材料的限制，故约束条件是

23、：是：8X1+5X2+3X3=100 6X1+9X2+8X3=0 其中其中 aij,bi,cj 是常数是常数,bi=0。特点特点:1)目标函数求最大值目标函数求最大值 2)所有约束条件都是等所有约束条件都是等式式(除变量非负约束除变量非负约束)3)约束条件右边常数约束条件右边常数bj=0 j=1,2,m 4)决策变量都是非负决策变量都是非负 这样就将线性规划问题归结为在一组线性方程组这样就将线性规划问题归结为在一组线性方程组（n个变量，个变量，m个方程）个方程）的非负解中，找使目标函数的非负解中，找使目标函数达到最大值的解。达到最大值的解。亦可用矩阵表示：亦可用矩阵表示：Max Z=CX s.

24、t AX=b X=0,b=0 n Max Z=cj xj s.t j=1 aij xj=bi bi=0 i=1,2,.,m xj=0 j=1,2,.,n可简记成：可简记成：n j=1 2、非标准形式线性规划问题的标准化非标准形式线性规划问题的标准化 任一线性规划模型任一线性规划模型,可化成标准形式。可化成标准形式。非标准形式线性规划模型的转换方法：非标准形式线性规划模型的转换方法：（）求目标函数最小值（）求目标函数最小值 （目标函数乘）（目标函数乘）Min Z=CX 由于由于 Max(Z)=Min Z=CX 如：如：Min（1，2，3，4）=-Max（-1，-2，-3，-4）故可令故可令 Z=

25、Z,就可将原目标函数化为求最大值就可将原目标函数化为求最大值.例如例如:Min Z=2x1+3x2可转化为可转化为:Max Z=2x1 3x2求出最大值后，再乘求出最大值后，再乘，即得原目标函数最小值。，即得原目标函数最小值。（）约束条件是（）约束条件是“=”型型 对不等式约束条件，可通过引入非负的松对不等式约束条件，可通过引入非负的松弛变量，将其化成等式弛变量，将其化成等式：例如：有约束条件例如：有约束条件 3x1 +2x2 +x3 =0（3）约束条件是）约束条件是“=”型型 同样可通过引入非负的松弛变量，将其化同样可通过引入非负的松弛变量，将其化成等式成等式：例如：有约束条件例如：有约束条

26、件 x1+x2+2x3 =8引入非负的松弛变量引入非负的松弛变量 s2 后变为，后变为，x1+x2+2x3 s2=8 s2=0 ()约束条件右边为负约束条件右边为负约束条件两边同乘即可。约束条件两边同乘即可。例如：例如：x1 2x2 +3x3 =两边同乘得：两边同乘得：x1 +2x2 3x3 =（）决策变量无符号限制（可正，可负（）决策变量无符号限制（可正，可负或等于零）用两个非负变量的差代替：或等于零）用两个非负变量的差代替：例如例如 X1 无符号限制，则令：无符号限制，则令：例例 1.6 已知线性规划问题已知线性规划问题 Min Z=3X13X2+7X3 s.t X1+X2+3 X3=50

27、 5X1+3X2 =20 X1,X2=0,X3 的符号无约束的符号无约束试将此问题化为标准形式。试将此问题化为标准形式。+s1=40+s1=40+s1=40+s1=40-s2=50-s2=50-s2=50-s2=50*-1-通过这些变换，目标函数虽然由通过这些变换，目标函数虽然由Z变为变为G，但由于约束条件在数学上是等价的，但由于约束条件在数学上是等价的，所以所以这两种情况的最优解仍是相同的这两种情况的最优解仍是相同的。3、典则形式、典则形式:线性规划问题的另一种形式，线性规划问题的另一种形式，在有些讨论中用到。在有些讨论中用到。特点：）目标函数求最大值特点：）目标函数求最大值 ）所有约束条件都是）所有约束条件都是“=0。显然：任一线性规划模型显然：任一线性规划模型,可化成典则形式。可化成典则形式。n Max Z=cj xj j=1 典则形式的一般表示典则形式的一般表示:约束条件：约束条件：n a ij xj=0 j=1,2,n亦可用矩阵表示：亦可用矩阵表示：Max Z=CX s.t AX=0 练练 习习 题：题：第一章第一章 习题习题 （P96）线性规划建模：线性规划建模：1-1，1-4，1-7，线性规划模型标准化线性规划模型标准化 1-10