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

《运筹学01-线性规划引论.ppt》由会员分享，可在线阅读，更多相关《运筹学01-线性规划引论.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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 7 1 6 4 2 5 3 8 每单位添每单位添加剂

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

5、，x4，0同时，我们有一个追求的目标同时，我们有一个追求的目标-成本最低，即：成本最低，即：Min Z=2x1+5x2+6x3+8x4综合上述讨论，在添加剂中各维生素的含量以及成本与原综合上述讨论，在添加剂中各维生素的含量以及成本与原料消耗量成线性关系的假设下，把目标函数和约束条件放料消耗量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的数学模型：在一起，可以建立如下的数学模型：目标函数目标函数约束条件约束条件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

6、类似的例子：类似的例子：教材教材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运输运输单价单价求：求：运输费用最小的运输方案运输费用最小的运输方案。解：设解：设x xij为为i 仓库运到仓库运到j j工厂的原棉数量工厂的原棉数量 其中：其中：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+

7、x22+x23 30 x31+x32+x33 10 x11 +x21+x31 =40 x12 +x22+x32 =15x13 +x23+x33 =35 xij 0类似的例子：类似的例子：教材教材P6-P7，例，例3 2.9m 2.9m钢筋架子钢筋架子100100个，每个需用个，每个需用 2.1m 2.1m 各各1 1，原料长，原料长7.4m7.4m 1.5m 1.5m求：如何下料，使得残余料头最少。求：如何下料，使得残余料头最少。例例4 4、合理下料问题、合理下料问题解：首先列出各种可能的下料方案；解：首先列出各种可能的下料方案；计算出每个方案可得到的不同长度钢筋的数量及计算出每个方案可得到的

8、不同长度钢筋的数量及残余料头长度；残余料头长度；确定决策变量；确定决策变量；根据不同长度钢筋的需要量确定约束方程根据不同长度钢筋的需要量确定约束方程;根据下料目标确定目标函数。根据下料目标确定目标函数。设按第设按第i种方案下料的原材料为种方案下料的原材料为x xi根根组合方案组合方案 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.1m 6.5m 7.4m 6.3m 7.2m 6.6m 6.0m 料料 长长 7.4m 7.4m 7.4m 7.4m 7.4m 7

9、.4m 7.4m 7.4m 料料 头头 0.1m 0.3m 0.9m 0.0m 1.1m 0.2m 0.8m 1.4m(2)线性规划问题的特点线性规划问题的特点l决策变量：决策变量：(x x1 1 x xn n)T T 代表某一方案，代表某一方案，决策者要考虑决策者要考虑和控制的因素非负；和控制的因素非负；l目标函数：目标函数：Z=(Z=(x x1 1 x xn n)为线性函数，求为线性函数，求Z Z极大或极小极大或极小;l约束条件：可用线性等式或不等式表示约束条件：可用线性等式或不等式表示.具备以上三个要素的问题就称为具备以上三个要素的问题就称为 线性规划问题线性规划问题。目标函数目标函数约

10、束条件约束条件(3)线性规划模型一般形式线性规划模型一般形式隐含的假设隐含的假设l比例性：决策变量变化引起目标的改变量与决策变量改比例性：决策变量变化引起目标的改变量与决策变量改变量成比例（即线性关系假定，比例可能会不同）变量成比例（即线性关系假定，比例可能会不同）l可加性：每个决策变量对目标和约束的影响独立于其它可加性：每个决策变量对目标和约束的影响独立于其它变量变量l连续性：每个决策变量取连续值连续性：每个决策变量取连续值l确定性：线性规划中的参数确定性：线性规划中的参数aij,bi,cj为为确定值确定值1.2 线性规划问题的图解法线性规划问题的图解法定义定义2 2：满足约束：满足约束(2

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

12、24 X X1 1 0 0 X X2 2 0 02030100102030X2DABC2X2 24X1+2X2 303X1+2X2 60X X1 1 0 0X X2 2 0 0可行域可行域(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 0 0解

13、：解：(1)(1)确定可行域与上例完全相同。确定可行域与上例完全相同。(2)(2)求最优解求最优解0203010102030DABC最优解最优解Z=1200最优解：最优解：BCBC线段线段X1X2最优解：最优解：BCBC线段线段B B点：点：X X(1)(1)=(6,12)C=(6,12)C点：点：X X(2)(2)=(15,7.5)=(15,7.5)X=X=X X(1)(1)+(1-+(1-)X)X(2)(2)(0 0 1 1)Max Z=1200 Max Z=1200 X1 6 15 X2 12 7.5X=+(1-)X1=6 +(1-)15X2=12+(1-X1=15-9 X2 (0 1)

14、例例3、Max Z=2X1+4X2 2X1+X2 8-2X1+X2 2X1,X2 0Z=08246X240X1-2X1+X2 22X1+X2 8X1 0X2 0可行域可行域无界无界无有限最优解无有限最优解可行域可行域无上界无上界无有限最优解无有限最优解例例4、Max Z=3X1+2X2-X1-X2 1X1,X2 0无可行域无可行域无可行解无可行解-1X2-1X10X2 0X1 0-X1-X2 1直观结论直观结论n若线性规划问题有解，则可行域是一个凸多边形若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）；（或凸多面体）；n若线性规划问题有最优解，则若线性规划问题有最优解，则q唯一最优解对

15、应于可行域的一个顶点；唯一最优解对应于可行域的一个顶点；q无穷多个最优解对应于可行域的一条边；无穷多个最优解对应于可行域的一条边；n若线性规划问题有可行解，但无有限最优解，则可若线性规划问题有可行解，但无有限最优解，则可行域必然是无界的；行域必然是无界的；n若线性规划问题无可行解，则可行域必为空集。若线性规划问题无可行解，则可行域必为空集。第一章作业第一章作业P P1616-P-P1717:6:6、7 7、8 8、9 9、1010中任选三题中任选三题思考题n某医院护士值班班次、某医院护士值班班次、护士上班后连续工作护士上班后连续工作8小时，每班工作时间及小时，每班工作时间及各班所需护士数量如右各班所需护士数量如右表。请建立线性规划模表。请建立线性规划模型，决定该医院最少需型，决定该医院最少需要多少名护士，以满足要多少名护士，以满足轮班的需要？轮班的需要？班次班次工作工作时间时间需需护护士数士数16：0010：0060210：0014：0070314：0018：0060418：0022：0050522：002：002062：006：0030