运筹学线性规划引论PPT课件

1、1.1 线性规划问题及其数学模型线性规划问题及其数学模型(1) 线性规划问题例1、生产组织与计划问题A, B 各生产多少, 可获最大利润?可用资源煤劳动力仓库A B1 23 2 2单位利润40 50306024第1页/共26页解: 设产品A, B产量分别为变量x1， x2根据题意，两种产品的生产要受到可用资源的限制，具体讲：对于煤，两种产品生产消耗量不能超过30，即： x1 + 2x2 30对于劳动力，两种产品生产的占用量不超过60，即： 3x1 + 2x2 60对于仓库，B种产品生产量的2倍不能超过24，即： 2x2 24另外，产品数不能为负，即： x1，x2 0第2页/共26页同时，我们有

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

3、每单位添加剂中原料j的用量为xj(j =1,2,3,4) 根据题意：混合配料后， 每单位添加剂中A的含量不得低于12，即 4x1 + 6x2 + x3+2x4 12 每单位添加剂中B的含量不得低于14，即 x1 + x2 +7x3+5x4 14 每单位添加剂中C的含量不得低于8，即 2x2 + x3+3x4 8 另外，原料使用量不能为负，即： x1，x2 ， x3， x4， 0第5页/共26页同时，我们有一个追求的目标-成本最低，即： Min Z= 2x1 + 5x2 +6x3+8x4综合上述讨论，在添加剂中各维生素的含量以及成本与原料消耗量成线性关系的假设下，把目标函数和约束条件放在一起，可

4、以建立如下的数学模型：目标函数约束条件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第6页/共26页例3、运输问题（纺纱厂） 工 厂 1 2 3 库存 仓 1 2 1 3 50 2 2 2 4 30 库 3 3 4 2 10 需求 40 15 35运输单价求：运输费用最小的运输方案。第7页/共26页解：设xij为i 仓库运到j工厂的原棉数量 其中：i 1，2，3 j 1，2，3Min Z= 2x11 + x12

5、+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第8页/共26页 2.9m钢筋架子100个，每个需用 2.1m 各1，原料长7.4m 1.5m求：如何下料，使得残余料头最少。例4、合理下料问题解：首先列出各种可能的下料方案； 计算出每个方案可得到的不同长度钢筋的数量及残余料头长度； 确定决策变

6、量； 根据不同长度钢筋的需要量确定约束方程; 根据下料目标确定目标函数。 第9页/共26页设按第i种方案下料的原材料为xi根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

7、 1.5m 1 0 1 3 0 2 3 4 合 计 7.3m 7.1m 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第10页/共26页(2) 线性规划问题的特点l决策变量： (x1 xn)T 代表某一方案， 决策者要考虑和控制的因素非负；l目标函数：Z=(x1 xn) 为线性函数，求Z极大或极小;l约束条件：可用线性等式或不等式表示.具备以上三个要素的问题就称为 线性规划问题。第11页/共26页0,.212

8、21122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目标函数约束条件(3) 线性规划模型一般形式第12页/共26页隐含的假设隐含的假设l比例性：决策变量变化引起目标的改变量与决策变量比例性：决策变量变化引起目标的改变量与决策变量改变量成比例（即线性关系假定，比例可能会不同）改变量成比例（即线性关系假定，比例可能会不同）l可加性：每个决策变量对目标和约束的影响独立于其可加性：每个决策变量对目标和约束的影响独立于其它变量它变量l连续性：每个决策变量取连续值连续性：每个决策变量取连续值l确定性：线性规划

9、中的参数确定性：线性规划中的参数aij , bi , cj为确定值为确定值第13页/共26页1.2 线性规划问题的图解法线性规划问题的图解法 20,.1XbAXtsCXZMinMax定义2：满足约束(2)的X=(X1 Xn)T称为线性规划问题的可行解，全部可行解的集合称为可行域。定义3：满足(1)的可行解称为线性规划问题的最优解。定义1：一组决策变量X=(X1 Xn)T的集合称为一个解。第14页/共26页例1 Max Z= 40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t第15页/共26页解：(1) 确定可行域 X1+2X2 30 3X1+2

10、X2 60 2X2 24 X1 0 X2 02030100102030X2DABC2X2 24X1+2X2 303X1+2X2 60X1 0X2 0可行域第16页/共26页(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等值线第17页/共26页例2、 Max Z=40X1+ 80X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t第18页/共26页

11、解：(1) 确定可行域与上例完全相同。 (2) 求最优解0203010102030DABC最优解Z=1200最优解：BC线段X1X2第19页/共26页最优解：BC线段B点：X(1)=(6,12) C点：X(2)=(15,7.5)X=X(1)+(1-)X(2) (0 1) 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)第20页/共26页例3、 Max Z=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2 0s.tZ=08246X240X1-2

12、X1+X2 22X1+X2 8X1 0X20可行域无界无有限最优解可行域无上界无有限最优解第21页/共26页例4、 Max Z=3X1+2X2 -X1 -X2 1X1 , X2 0无可行域无可行解-1X2-1X10s.tX2 0X1 0-X1 -X2 1第22页/共26页直观结论直观结论若线性规划问题有解，则可行域是一个凸多边若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）；形（或凸多面体）；若线性规划问题有最优解，则若线性规划问题有最优解，则唯一最优解对应于可行域的一个顶点；唯一最优解对应于可行域的一个顶点；无穷多个最优解对应于可行域的一条边；无穷多个最优解对应于可行域的一条边；若线性规划问题有可行解，但无有限最优解，若线性规划问题有可行解，但无有限最优解，则可行域必然是无界的；则可行域必然是无界的；若线性规划问题无可行解，则可行域必为空集。若线性规划问题无可行解，则可行域必为空集。第23页/共26页第一章作业第一章作业P P1616-P-P1717:6:6、7 7、8 8、9 9、1010中任选三题中任选三题第24页/共26页思