运筹学01-线性规划引论ppt课件

1、第一章第一章 线性规划引论线性规划引论1.1 线性规划问题及其数学模型线性规划问题及其数学模型1.2 线性规划问题的图解法线性规划问题的图解法1.1 线性规划问题及其数学模型线性规划问题及其数学模型(1) 线性规划问题线性规划问题例例1 1、生产组织与计划问题、生产组织与计划问题A, B A, B 各生产多少各生产多少, , 可获最大利润可获最大利润? ?可用资源可用资源煤煤劳动力劳动力仓库仓库A B1 23 2 2单位利润单位利润40 50306024解解: : 设产品设产品A, BA, B产量分别为变量产量分别为变量x1x1， x2x2根据题意，两种产品的生产要受到可用资源的限制，根据题意

2、，两种产品的生产要受到可用资源的限制，具体讲：具体讲：对于煤，两种产品生产消耗量不能超过对于煤，两种产品生产消耗量不能超过30，即：，即： x1 + 2x2 30对于劳动力，两种产品生产的占用量不超过对于劳动力，两种产品生产的占用量不超过60，即：，即： 3x1 + 2x2 60对于仓库，对于仓库，B种产品生产量的种产品生产量的2倍不能超过倍不能超过24，即：，即： 2x2 24另外，产品数不能为负，即：另外，产品数不能为负，即： x1，x2 0同时，我们有一个追求的目标同时，我们有一个追求的目标-最大利润，即：最大利润，即： Max Z= 40 x1 +50 x2综合上述讨论，在生产资源的消

3、耗以及利润与产品产量成综合上述讨论，在生产资源的消耗以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的数学模型：以建立如下的数学模型：Max Z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目标函数目标函数约束条件约束条件类似的例子：类似的例子：教材教材P4-P5，例，例1例例2 2 合理配料问题合理配料问题求：最低成本的原料混合方案求：最低成本的原料混合方案 原料原料 A B 每单位成本每单位成本 1 4 1 0 2 2 6 1 2 5 3 1

4、 7 1 6 4 2 5 3 8 每单位添每单位添加剂中维生加剂中维生 12 14 8 素最低含量素最低含量解：设每单位添加剂中原料解：设每单位添加剂中原料j j的用量为的用量为xj(j =1,2,3,4)xj(j =1,2,3,4) 根据题意：混合配料后，根据题意：混合配料后， 每单位添加剂中每单位添加剂中A A的含量不得低于的含量不得低于1212，即，即 4x1 + 6x2 + x3+2x4 4x1 + 6x2 + x3+2x4 1212 每单位添加剂中每单位添加剂中B B的含量不得低于的含量不得低于1414，即，即 x1 + x2 +7x3+5x4 x1 + x2 +7x3+5x4 14

5、14 每单位添加剂中每单位添加剂中C C的含量不得低于的含量不得低于8 8，即，即 2x2 + x3+3x4 2x2 + x3+3x4 8 8 另外，原料使用量不能为负，即：另外，原料使用量不能为负，即： x1x1，x2 x2 ， x3x3， x4x4， 0 0同时，我们有一个追求的目标同时，我们有一个追求的目标-成本最低，即：成本最低，即： Min Z= 2x1 + 5x2 +6x3+8x4综合上述讨论，在添加剂中各维生素的含量以及成本与原综合上述讨论，在添加剂中各维生素的含量以及成本与原料消耗量成线性关系的假设下，把目标函数和约束条件放料消耗量成线性关系的假设下，把目标函数和约束条件放在一

6、起，可以建立如下的数学模型：在一起，可以建立如下的数学模型：目标函数目标函数约束条件约束条件Min Z= 2x1 + 5x2 +6x3+8x44x1 + 6x2 + x3+2x4 12 x1 + x2 + 7x3+5x4 142x2 + x3 + 3x4 8 xj 0 (j =1,4)s.t类似的例子：类似的例子：教材教材P5-P6，例，例2例例3 3、运输问题纺纱厂）、运输问题纺纱厂） 工工 厂厂 1 2 3 库存库存 仓仓 1 2 1 3 50 2 2 2 4 30 库库 3 3 4 2 10 需求需求 40 15 35运输运输单价单价求：运输费用最小的运输方案。求：运输费用最小的运输方案

7、。解：设解：设xijxij为为i i 仓库运到仓库运到j j工厂的原棉数量工厂的原棉数量 其中：其中：i i 1 1，2 2，3 3 j j 1 1，2 2，3 3Min Z= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33x11 + x12+ x13 50 x21 + x22+ x23 30 x31 + x32+ x33 10 x11 + x21+ x31 = 40 x12 + x22+ x32 = 15x13 + x23+ x33 = 35 xij 0s.t类似的例子：类似的例子：教材教材P6-P7，例，例3 2.9m 2.9m钢筋架子

8、钢筋架子100100个，每个需用个，每个需用 2.1m 2.1m 各各1 1，原料长，原料长7.4m7.4m 1.5m 1.5m求：如何下料，使得残余料头最少。求：如何下料，使得残余料头最少。例例4 4、合理下料问题、合理下料问题解：首先列出各种可能的下料方案；解：首先列出各种可能的下料方案； 计算出每个方案可得到的不同长度钢筋的数量及计算出每个方案可得到的不同长度钢筋的数量及残余料头长度；残余料头长度； 确定决策变量；确定决策变量； 根据不同长度钢筋的需要量确定约束方程根据不同长度钢筋的需要量确定约束方程; ; 根据下料目标确定目标函数。根据下料目标确定目标函数。 设按第设按第i i种方案下

9、料的原材料为种方案下料的原材料为xixi根根8 , 7 , 6 , 5 , 4 , 3 , 2 , 1100432030100002302010000002. .4 . 18 . 02 . 01 . 109 . 03 . 01 . 087654321876543218765432187654321ixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxZMini为大于零的整数，组合方案组合方案 1 2 3 4 5 6 7 8 2.9m 2 1 1 1 0 0 0 0 2.1m 0 2 1 0 3 2 1 0 1.5m 1 0 1 3 0 2 3 4 合合 计计 7.3m 7.1

10、m 6.5m 7.4m 6.3m 7.2m 6.6m 6.0m 料料 长长 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 料料 头头 0.1m 0.3m 0.9m 0.0m 1.1m 0.2m 0.8m 1.4m(2) 线性规划问题的特点线性规划问题的特点l决策变量：决策变量： (x1 xn)T (x1 xn)T 代表某一方案，代表某一方案， 决策者要考决策者要考虑和控制的因素非负；虑和控制的因素非负；l目标函数：目标函数：Z=Z=(x1 xn) (x1 xn) 为线性函数，求为线性函数，求Z Z极大或极小极大或极小; ;l约束条件：可用线性等式或不等式表示约

11、束条件：可用线性等式或不等式表示. .l具备以上三个要素的问题就称为具备以上三个要素的问题就称为 线性规划问题。线性规划问题。0,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目标函数目标函数约束条件约束条件(3) 线性规划模型一般形式线性规划模型一般形式隐含的假设隐含的假设比例性：决策变量变化引起目标的改变量与决策比例性：决策变量变化引起目标的改变量与决策变量改变量成比例即线性关系假定，比例可变量改变量成比例即线性关系假定，比例可能会不同）能会不同）可加性：每个决策变量对目标和约束

12、的影响独立可加性：每个决策变量对目标和约束的影响独立于其它变量于其它变量连续性：每个决策变量取连续值连续性：每个决策变量取连续值确定性：线性规划中的参数确定性：线性规划中的参数aij , bi , cjaij , bi , cj为确定为确定值值1.2 线性规划问题的图解法线性规划问题的图解法 20,.1XbAXtsCXZMinMax定义定义2 2：满足约束：满足约束(2)(2)的的X=(X1 Xn)TX=(X1 Xn)T称为线性规划问题称为线性规划问题的可行解，全部可行解的集合称为可行域。的可行解，全部可行解的集合称为可行域。定义定义3 3：满足：满足(1)(1)的可行解称为线性规划问题的最优

13、解。的可行解称为线性规划问题的最优解。定义定义1 1：一组决策变量：一组决策变量X=(X1 Xn)TX=(X1 Xn)T的集合称为一个解。的集合称为一个解。例例1 Max Z= 40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t解：解：(1) (1) 确定可行域确定可行域 X1+2X2 X1+2X2 30 30 3X1+2X2 3X1+2X2 60 60 2X2 2X2 24 24 X1 X1 0 0 X2 X2 0 02030100102030X2DABC2X2 24X1+2X2 303X1+2X2 60X1 X1 0 0X2 X2 0 0可

14、行域可行域(2) (2) 求最优解求最优解最优解：最优解：X* = (15,7.5) Zmax =975Z=40X1+50X20=40X1+50X2 (0,0)， (10,-8)C点：点： X1+2X2 =30 3X1+2X2 =600203010102030X1X2DABC最优解最优解Z=975可行解可行解Z=0等值线等值线例例2、 Max Z=40X1+ 80X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t解：解：(1) (1) 确定可行域与上例完全相同。确定可行域与上例完全相同。 (2) (2) 求最优解求最优解0203010102030DABC最优解

15、最优解Z=1200最优解：最优解：BCBC线段线段X1X2最优解：最优解：BCBC线段线段B B点：点：X(1)=(6,12) CX(1)=(6,12) C点：点：X(2)=(15,7.5)X(2)=(15,7.5)X=X=X(1)+(1-X(1)+(1-)X(2) (0 )X(2) (0 1) 1) Max Z=1200 Max Z=1200 X1 6 15 X2 12 7.5X= = +(1- )X1 =6 +(1- )15X2=12+(1- )7.5X1 =15-9X2 =7.5+4.5 (0 1)例例3、 Max Z=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2

16、0s.tZ=08246X240X1-2X1+X2 22X1+X2 8X1 0X20可行域可行域无界无界无有限最优解无有限最优解可行域可行域无上界无上界无有限最优解无有限最优解例例4、 Max Z=3X1+2X2 -X1 -X2 1X1 , X2 0无可行域无可行域无可行解无可行解-1X2-1X10s.tX2 0X1 0-X1 -X2 1直观结论直观结论n若线性规划问题有解，则可行域是一个凸多边形若线性规划问题有解，则可行域是一个凸多边形或凸多面体）；或凸多面体）；n若线性规划问题有最优解，那么若线性规划问题有最优解，那么n唯一最优解对应于可行域的一个顶点；唯一最优解对应于可行域的一个顶点；n无穷多个最优解对应于可行域的一条边；无穷多个最优解对应于可行域的一条边；n若线性规划问题有可行解，但无有限最优解，则若线性规划问题有可行解，但无有限最优解，则可行域必然是无界的；可行域必然是无界的；n若线性规划问题无可行解，则可行域必为空集。若线性规划问题无可行解，则可行域必为空集。第一章作业第一章作业P16-P17:6P16-P17:6、7 7、8 8、9 9、1