数学建模教案----线性规划课件

1、德州学院数学系数学建模教案德州学院数学系数学建模教案运筹学模型运筹学模型 主讲人主讲人 高秀莲高秀莲德州学院数学系数学建模教案德州学院数学系数学建模教案线性规划线性规划线性规划问题及其数学模型线性规划问题及其数学模型 例例1 美佳公司计划制造美佳公司计划制造I，II两种家电产品。已知各两种家电产品。已知各制造一件时分别占用的设备制造一件时分别占用的设备A、B的台时、调试时间及的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表一件时的获利情况如表Il所示。问该公司应制造所示。问该公司应制造A、B两两种家电各

2、多少件，使获取的利润为最大？种家电各多少件，使获取的利润为最大？项目项目I IIIII每天可用能力每天可用能力设备设备A A（h h）设备设备B B（h h）调试工序（调试工序（h h）0 06 61 15 52 21 1151524245 5利润（元）利润（元）2 21 1线性规划数学模型线性规划数学模型德州学院数学系数学建模教案德州学院数学系数学建模教案目标函数目标函数约束条件约束条件项目项目I IIIII每天可用能力每天可用能力设备设备A A（h h）设备设备B B（h h）调试工序（调试工序（h h）0 06 61 15 52 21 1151524245 5利润（元）利润（元）2 21

3、 1例例1 112max2zxx0,52426155.2121212xxxxxxxts用数学语言描述用数学语言描述线性规划数学模型线性规划数学模型德州学院数学系数学建模教案德州学院数学系数学建模教案解：用变量解：用变量 和和 分别表示美佳公司制造家电分别表示美佳公司制造家电I I和和IIII的数量。的数量。1x2x例例2 捷运公司拟在下一年度的捷运公司拟在下一年度的1-4月的月的4个月内需租用仓库堆个月内需租用仓库堆放物资。已知各月份所需仓库面积数列见下表。仓库租借费用随放物资。已知各月份所需仓库面积数列见下表。仓库租借费用随合同期定，期限越长折扣越大，具体数字见下表。租借仓库的合合同期定，期

4、限越长折扣越大，具体数字见下表。租借仓库的合同每月初都可办理，每份台同具体现定租用面积数和期限。因此同每月初都可办理，每份台同具体现定租用面积数和期限。因此该厂可根据需要，在任何一个月初办理租借台同。每次办理时可该厂可根据需要，在任何一个月初办理租借台同。每次办理时可签一份，也可签若干份租用面积和租借期限不同的合同，试确定签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。该公司签订租借合同的最优决策，目的是使所付租借费用最小。月份月份1 12 23 34 4所需仓库面积所需仓库面积1515101020201212合同租借期限合同租借

5、期限1 1个月个月2 2个月个月3 3个月个月4 4个月个月合同期内的租合同期内的租费费28002800450045006000600073007300线性规划数学模型线性规划数学模型德州学院数学系数学建模教案德州学院数学系数学建模教案解：设变量xij表示捷运公司在第i(i1，4)个月初签订的租借期为jj1，4)个月的仓库面积的合同(单位为100m2)。约束条件目标函数例例2 2月份月份1 12 23 34 4所需仓库面积所需仓库面积1515101020201212合同租借期限合同租借期限1 1个月个月2 2个月个月3 3个月个月4 4个月个月合同期内的租费合同期内的租费28002800450

6、04500600060007300730011213141122232132314min2800() 4500() 6000() 7300zxxxxxxxxxx)4.1;4.1(012201015.4132231432312322141323222114131214131211jixxxxxxxxxxxxxxxxxxxxxtsij线性规划数学模型线性规划数学模型决策变量：向量(x1 xn)T 决策人要考虑和控制的因素。约束条件：线性等式或不等式目标函数：Z=(x1 xn) 线性式，求Z极大或极小线性规划模型特点线性规划数学模型线性规划数学模型8max(min)Z=c1x1+ c2x2+cnxn

7、n个变量个变量价值系价值系数数第第i 种资种资源的拥有源的拥有量量技术系数或技术系数或工艺系数工艺系数a11x1+ a12x2+ a1nxn (=, )b1a21x1+ a22x2+ a2nxn (=, )b2 am1x1+ am2x2+ amnxn (=, )bmxj 0(j=1,n)s.t.线性规划的一般式线性规划的一般式线性规划数学模型线性规划数学模型njjjxcz1max(min), 2 , 1(0), 2 , 1(.1njxmibxastjinjjij线性规划的简写式线性规划的简写式线性规划数学模型线性规划数学模型线性规划问题应用线性规划问题应用市场营销(广告预算和媒介选择，竞争性定

8、价，新产品开发，制定销售计划)生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计划，设备更新)城市管理(供水，污水管理，服务系统设计、运用)线性规划数学模型线性规划数学模型德州学院数学系数学建模教案德州学院数学系数学建模教案运输问题模型运输问题模型 线性规划线性规划仓库仓库工厂工厂 1 2 3 库存库存 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10 需求需求 40 15 35工厂需要的原棉存放在三个仓

9、库中，现将原棉运往工工厂需要的原棉存放在三个仓库中，现将原棉运往工厂以满足工厂生产的需求。已知原棉运到各个工厂的单位厂以满足工厂生产的需求。已知原棉运到各个工厂的单位运费如表所示。问使总运费最小的运输方案？运费如表所示。问使总运费最小的运输方案？运输问题模型运输问题模型解：设解：设xij为为i 仓库运到仓库运到 j工厂的原棉数量工厂的原棉数量(i =1,2,3 j =1,2,3)minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33x11 +x12+x13 50 x21+x22+x23 30 x31+x32+x33 10 x11 +x2

10、1+x31 = 40 x12 +x22+x32 = 15x13 +x23+x33 = 35 xij 0st.运输问题模型运输问题模型供应地约束供应地约束需求地约束需求地约束运输问题的描述：运输问题的描述： 设某种物品有设某种物品有m个产地个产地A1,A2,.,Am，各产地的产量，各产地的产量分别是分别是a1,a2,.,am；有；有n个销地个销地B1,B2,.,Bn，各销地的销，各销地的销量分别为量分别为b1,b2,.bn。假定从产地。假定从产地Ai(i=1,2,m)向销地向销地出出Bj(jl,2,.n)运输单位物品的运价是运输单位物品的运价是cij，问怎样调运，问怎样调运这些物品才能使总运费最

11、小这些物品才能使总运费最小?运输问题及其数学模型运输问题及其数学模型运运价价表表 销地销地产地产地B1B2Bn产量产量A1C11C12C1na1x11x12x1nA2C12C22C2na2x21x22x2n.AmC1mC2mCmnamxm1xm2xmn销量销量b1b2bm运输问题及其数学模型运输问题及其数学模型产销平衡运输问题的数学模型表示：产销平衡运输问题的数学模型表示：j xciBA设ijij njmixnjbxmiaxxCzijmijijnjiijminjijij,.,2 , 1;,.,2 , 10,.2 , 1,.2 , 1min1111（ ）0,ijjiCba其中jiba运输问题及其

12、数学模型运输问题及其数学模型该模型是一个线性规划模型，可以用单纯形法该模型是一个线性规划模型，可以用单纯形法求解。但是变量数目非常多。如求解。但是变量数目非常多。如3个产地，个产地，4个销地。个销地。变量数目会有变量数目会有19个之多。个之多。因此应该寻求更简便的解法。因此应该寻求更简便的解法。为了说明适于求解运输问题的更好的解法，先为了说明适于求解运输问题的更好的解法，先分析运输问题数学模型的特点。分析运输问题数学模型的特点。运输问题及其数学模型运输问题及其数学模型运输问题数学模型的特点：运输问题数学模型的特点：1运输问题有有限最优解运输问题有有限最优解jibaQnjmiQbaxjiij,.

13、2,1;,.,2,1,是一个可行解。同时，目标函数有下界，且不会趋于负无穷。所以，必存在有限最优解。运输问题及其数学模型运输问题及其数学模型2运输问题约束条件的系数矩阵运输问题约束条件的系数矩阵111.1111.1.1.11.1.1221111mnmnnxxxxxxA =n 行行m 行行jmiijeeP系数列向量：系数列向量：TijA)0,.,0,1 ,0,.,0,1 ,0,.,0(第第i个个第第m+ j个个运输问题及其数学模型运输问题及其数学模型由此可知，运输问题具有下述特点：由此可知，运输问题具有下述特点： (1)约束条件系数矩阵的元素等于约束条件系数矩阵的元素等于0或或1； (2)约束条

14、件系数矩阵的每一列有两个非零元素，这约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前对应于每一个变量在前m个约束方程中出现一次，在后个约束方程中出现一次，在后n个约束方程中也出现一次；个约束方程中也出现一次；对产销平衡运输问题，除上述两个特点外，还有以对产销平衡运输问题，除上述两个特点外，还有以下特点：下特点：(3)所有结构约束条件都是等式约束；所有结构约束条件都是等式约束；(4)各产地产量之和等于各销地销量之和。各产地产量之和等于各销地销量之和。 秩秩 ( A) =m+n-1运输问题的基可行解中应包含运输问题的基可行解中应包含m+n-1个基变量个基变量.运输问题及其数学模型运输

15、问题及其数学模型表上作业法表上作业法 表上作业法是一种迭代法，迭代步骤为：表上作业法是一种迭代法，迭代步骤为： 1、先按某种规则找出一个初始解、先按某种规则找出一个初始解(初始调运方案初始调运方案)； 2、再对现行解作最优性判别；、再对现行解作最优性判别； 3、若这个解不是最优解，就在运输表上对它进行调整、若这个解不是最优解，就在运输表上对它进行调整改进，得出改进，得出个新解；个新解； 4、再判别，再改进；、再判别，再改进； 5、直至得到运输问题的最优解为止。、直至得到运输问题的最优解为止。 迭代过程中得出的所有解都要求是运输问题的基可行解迭代过程中得出的所有解都要求是运输问题的基可行解。例例

16、1： 销地销地产地产地B1B2B3B4产量产量A141241116A22103910A38511622销量销量814121448表上作业法表上作业法 思路：思路：为了减少运费，应优先考虑单位运价最小为了减少运费，应优先考虑单位运价最小(或或运距员短运距员短)的供销业务，最大限度地满足其供销量。在可的供销业务，最大限度地满足其供销量。在可供物品已用完的产地或需求已全部满足的销地，以后将不供物品已用完的产地或需求已全部满足的销地，以后将不再考虑。然后，在余下的供、销点的供销关系中，继续按再考虑。然后，在余下的供、销点的供销关系中，继续按上述方法安排调运，直至安排完所有供销任务，得到一个上述方法安排

17、调运，直至安排完所有供销任务，得到一个完整的调运方案完整的调运方案(完整的解完整的解)为止。这样就得到了运输问题为止。这样就得到了运输问题的一个初始基可行解的一个初始基可行解(初始调运方案初始调运方案)。 由于该方法基于优先满足单位运价由于该方法基于优先满足单位运价(或运距或运距)最小的供最小的供销业务，故称为最小元素法。销业务，故称为最小元素法。1、初始基可行解最小元素法、初始基可行解最小元素法表上作业法表上作业法 销地销地产地产地B1B2B3B4产量产量A141241116A22103910A38511622销量销量81412144882101486所以，初始基可行解为：所以，初始基可行解

18、为：目标函数值目标函数值Z246表上作业法表上作业法在满足约束条件下尽可能的给最左上角的变量最大值. 销地销地产地产地B1B2B3B4产量产量A141241116A22103910A38511622销量销量8141214488864814所以，初始基可行解为：所以，初始基可行解为：目标函数值目标函数值Z3721、初始基可行解西北角法、初始基可行解西北角法表上作业法表上作业法最小元素法，有时按某一最小单位运价优先安排最小元素法，有时按某一最小单位运价优先安排物品调运时，却可能导致不得不采用运费很高的其他物品调运时，却可能导致不得不采用运费很高的其他供销点，从而使整个运输费用增加。供销点，从而使整

19、个运输费用增加。6202455551、初始基可行解沃格尔法、初始基可行解沃格尔法表上作业法表上作业法对每一个供应地或销售地，均可由它到各销售地或到对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。并称这两个单位运价之差为该供应地或销售地的罚数。沃格尔法基本思想：沃格尔法基本思想： 在罚数最大处采用最小运费调运。在罚数最大处采用最小运费调运。 如果罚数的值不大，当不能按最小单位运价安排运输如果罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失

20、不大；反之，如果罚数的值很大，不按时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。位运价安排运输。沃格尔法就是基于这种考虑提出来的。表上作业法表上作业法沃格尔法计算步骤：沃格尔法计算步骤：1) 分别算出各行、各列的罚数。分别算出各行、各列的罚数。2) 从行、列中选出差额最大者，选择它所在行、从行、列中选出差额最大者，选择它所在行、列中的最小元素，进行运量调整。列中的最小元素，进行运量调整。3) 对剩余行、列再分别计算各行、列的差额。返对剩余行、

21、列再分别计算各行、列的差额。返回回1)、2)。表上作业法表上作业法 销地销地产地产地B1B2B3B4产量产量A141241116A22103910A38511622销量销量81412144814所以，初始基可行解为：所以，初始基可行解为：目标函数值目标函数值Z244881224表上作业法表上作业法 思路：要判定运输问题的某个解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量(对应于运输表中的空格)的检验数，若有某空格(Ai,Bj)的检验数为负，说明将xij变为基变量将使运输费用减少，故当前这个解不是最优解。若所有空格的检验数全非负，则不管怎样变换解均不能使运输费用降低，即目标函数值已无

22、法改进，这个解就是最优解。 以最小元素法的初始解为例。假设产地A1供应1个单位的物品给销地B1。则解的变化和目标函数的变化如何。2、解的最优性检验闭回路法、解的最优性检验闭回路法表上作业法表上作业法 销地销地产地产地B1B2B3B4产量产量A141241116A22103910A38511622销量销量814121448821014861211012-1表上作业法表上作业法 由此可知，为了求某个空格由此可知，为了求某个空格(非基变量非基变量)的检验数，的检验数，先要找出它在运输表上的闭回路，这个闭回路的顶点，先要找出它在运输表上的闭回路，这个闭回路的顶点，除这个空格外，其它均为填有数字的格除这

23、个空格外，其它均为填有数字的格(基变量格基变量格)，它是，它是由水平线段和竖直线段依次联接这些顶点构成的一封闭由水平线段和竖直线段依次联接这些顶点构成的一封闭多边形。每个空格都唯一存在这样的一条闭回路。多边形。每个空格都唯一存在这样的一条闭回路。表上作业法表上作业法某空格的检验数是以该空格为第一个顶点，某回路的某空格的检验数是以该空格为第一个顶点，某回路的奇数顶点运价和减去其偶数顶点运价和。奇数顶点运价和减去其偶数顶点运价和。表上作业法表上作业法B1B2B3B4A1A2A3特征特征:1. 每个顶点都是转角点每个顶点都是转角点.2. 每一边都是水平或垂直的每一边都是水平或垂直的.3. 每一行每一

24、行(或列或列)若有闭回路的顶点若有闭回路的顶点,则必有两个则必有两个. 销地产地B1B2B3B4产量A167531414557A284272781369A35910619-11-3613销量22131213 销地销地产地产地B1B2B3B4产量产量A167531414A28427278136A35910619613销量销量22131213例：确定下列可行解的检验数例：确定下列可行解的检验数表上作业法表上作业法运输问题的进一步讨论运输问题的进一步讨论 前面讲述的运输问题的算法，是以总产前面讲述的运输问题的算法，是以总产量等于总销量量等于总销量(产销平衡产销平衡)为前提的。实际上，为前提的。实际上

25、，在很多运输问题中，总产量不等于总销量。在很多运输问题中，总产量不等于总销量。 0,ijjiCba其中njmixnjbxmiaxxCzijmijijnjiijminjijij1 ,10,.2 , 1,.2 , 1min1111（ ）表上作业法 以产销平衡 为前提。jiba1、产销不平衡的运输问题、产销不平衡的运输问题运输问题的进一步讨论运输问题的进一步讨论0,.2 , 1,.2 , 1min1111ijmijijnjiijminjijijxnjbxmiaxxCzjiba 产大于销 产销不平衡产销平衡模型：模型：运输问题的进一步讨论运输问题的进一步讨论设 为Ai的贮存量。1, nixmiaxxx

26、injijninjij,.,2 , 1111,1jininijmiijbaxnjbx11,1,.,2 , 1将多余物原地贮存。令：101njnjCCijij运输问题的进一步讨论运输问题的进一步讨论111njjmiiba理解： 产 销 假想有一销地 j=n+1 销量为 运价 njjmiiba1101,niC01,.2, 1,.2, 1min111111ijmijijnjiijminjijijxnjbxmiaxxCz模型：运输问题的进一步讨论运输问题的进一步讨论 销地销地产地产地B1B2BnBn+1 （贮存）（贮存） 产量产量A1C11C12C1n0a1x11x12x1nx1,n+1A2C12C2

27、2C2n0a2x21x22x2nx2,n+1.AmC1mC2mCmn0amxm1xm2xmnxm ,n+1销量销量b1b2bma- b运输问题的进一步讨论运输问题的进一步讨论2、有转运的运输问题、有转运的运输问题在以上讨论中，假定物品由产地直接运送到销售在以上讨论中，假定物品由产地直接运送到销售目的地，不经中间转运。但是，常常会遇到这种情形：目的地，不经中间转运。但是，常常会遇到这种情形：需先将物品由产地运列某个中间转运站需先将物品由产地运列某个中间转运站(可能是另外的可能是另外的产地、销地或中间转运仓库产地、销地或中间转运仓库)，然后再转运到销售目的，然后再转运到销售目的地。有时，经转运比直

28、接运到目的地更为经济。因此，地。有时，经转运比直接运到目的地更为经济。因此，在决定运输方案时有必要把转运也考虑进去。在决定运输方案时有必要把转运也考虑进去。运输问题的进一步讨论运输问题的进一步讨论2、有转运的运输问题、有转运的运输问题注：所有i=j，cij=-cia1a5b1b5Qc1c5c11c55 例：如图所示是一个运输系统，它包括二个产地（例：如图所示是一个运输系统，它包括二个产地（1和和2）、二）、二个销地个销地(4和和5)及一个中间转运站及一个中间转运站(3)，各产地的产量和各销地的，各产地的产量和各销地的销量用相应节点处箭线旁的数字表示，节点联线上的数字表示销量用相应节点处箭线旁的

29、数字表示，节点联线上的数字表示其间的运输单价，节点旁的数字为该地的转运单价，试确定最其间的运输单价，节点旁的数字为该地的转运单价，试确定最优运输方案。优运输方案。 销地销地产地产地A1A2B3C4C5产量产量A1A2B3C4C5销量销量 销地销地产地产地A1A2B3C4C5产量产量A1-4532M60A25-12M490B332-35550C42M5-3650C5M456-550销量销量5050508070运用举例运用举例例例 1 、某飞机制造厂生产一种民用喷气式飞机，生产的最后、某飞机制造厂生产一种民用喷气式飞机，生产的最后阶段是制造喷气发动机，以及把发动机安装到已完成的飞机阶段是制造喷气发

30、动机，以及把发动机安装到已完成的飞机骨架上（一种很快的操作）。为了不误合同规定的交货期，骨架上（一种很快的操作）。为了不误合同规定的交货期，第一第一.二二.三三.四月必须安装发动机的台数分别为：四月必须安装发动机的台数分别为：10 ,15, 25 ,20。但受生产能力等条件的限制，这些月份的最高生产。但受生产能力等条件的限制，这些月份的最高生产台数分别为：台数分别为：25,35 ,30 , 10。每月单台发动机的存储费用为。每月单台发动机的存储费用为1.5万元。已知一、二、三、四月份的单台生产费用各为：万元。已知一、二、三、四月份的单台生产费用各为：108 、111、 110、113万元。试安

31、排这四个月的生产计划，万元。试安排这四个月的生产计划，使生产费用和存储费用之和最小。使生产费用和存储费用之和最小。 1）建立此问题的一般）建立此问题的一般LP模型。模型。 2）把此问题作为运输问题来处理，试建立相应的运输表格。）把此问题作为运输问题来处理，试建立相应的运输表格。 3）求此）求此“运输问题运输问题”的最优解。的最优解。 解：1）设xi表示第i个月生产发动机的台数，yi表示第个月的存储台数，则一般LP模型为：0,1030352570502510)(5 . 1113110111108min43214432133212211143214321iiyxxxxxyxxxxyxxxyxxyx

32、yyyyxxxx运用举例运用举例个月发动机的安装。第收点个月发动机的生产。第设发点jjii、)2(ijijxijciij 第 个月生产供第 个月安装的发动机的台数。第 个月的单台生产费用与第 月生产存储到第 月的单台发动机存储费用之和。 由于不能缺货，并考虑到是不平衡问题（虚设由于不能缺货，并考虑到是不平衡问题（虚设收点收点5）建立如下运输表格）建立如下运输表格运用举例运用举例：计算得最优生产安排为10410203525101014321最小费用为： w*=7730(万元）123451108109.5111112.50252M111112.51140353MM110111.50304MMM11

33、30101015252030运用举例运用举例例例2 某航运公司承担六个港口城市某航运公司承担六个港口城市A.B.C.D.E.F的四的四条固定航线的物资运输任务。已知各条航线的起点、终点条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见表：城市及每天航班数见表：航线起点城市终点城市每天航线1ED32BC23AF14DB1每条航线使用相同型号的船只，各城市间的航程天数如表：每条航线使用相同型号的船只，各城市间的航程天数如表：运用举例运用举例每条船只每次装卸货物的时间各需一天。每条船只每次装卸货物的时间各需一天。 问该航运公司至少应配备多少条船，才能满足所有航线问该航运公司至少应配

34、备多少条船，才能满足所有航线的运货需求。的运货需求。 终点终点起点起点ABCDEFA0121477B1031388C23015557851703F7852030运用举例运用举例ABCDEF2311173713每天载货航程所需的船只数：每天载货航程所需的船只数：每天到每天到达数达数每天需每天需求数求数余缺数余缺数ABCDEF运用举例运用举例分析：1）所需船只可分为两部分：载货航程所需的船只数、各港口间调度所需的船只数。 2）每天载货航程所需的船只数：1591057137317BDFACBDE只。共 91 3） 每天各港口调度所需船只数。 每天到达数每天到达数每天需求数每天需求数余缺数