数模竞赛培训线性规划.ppt

1、2010年数模竞赛培训,线性规划 主讲:李建章,线性规划数学模型的组成,1）决策变量 2）目标函数 3）约束条件 4）符号约束,线性规划中的两类数学模型1,1、max 总收入或总利润 总成本b 返回,线性规划中的两类数学模型2,2、min 总成本 总收入b 返回,线性规划模型的一般形式,线性规划数学模型的特点,1、一组决策变量(x1,x2,xn) 决策者可选择 2、一个目标函数 极大化或极小化 是决策变量的线性函数 Max(或min) z=c1x1+c2x2+cnxn 3、一组约束条件 决策变量的线性等式或不等式组 4、通常变量有符号约束或整数约束或0-1变量约束 xj； xj为整数； xj=

2、0或1,建立线性规划数学模型的步骤,1、选择适当的决策变量 1) 将决策者想知道但还不知道的设为未知数； 2) 所取决策变量要便于表达目标函数和约束条件。 3) 当将决策者想知道但还不知道的是由多个部分组成时，则应将最基本的部分取为决策变量。 2、用决策变量表达目标函数 收入或利润极大化 成本或支出极小化 3、用决策变量表达所有的约束条件 4、注意变量的符号约束,例1: 生产计划问题(步骤),第1步 -确定决策变量,设 I的产量 II的产量 利润,Max Z = 2 x1 + 3 x2,第2步 写出目标函数,x1 + 2 x2 8 4 x1 16 4 x2 12 x1、 x2 0,第3步 -表

3、示约束条件,该计划的数学模型,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x1,x2,例 2 环境保护问题,工厂1（工业污水2万m3 ）治污成本 1000元/万m3 500万m3 20%自然净化 200万m3 工厂2 （工业污水1.4万m3 ） 治污成本800元/万m3 要求污水含量不大于0.2%(步骤),长江,嘉陵江,朝天门,设： 化工厂1每天处理的污水量为x1万立方米； 化工厂2每天处理的污水量为x2万立方米,建模型之前的分析和计算,整理得到本问题的数学模型为：,例3 合理下料问题,书上P38例10,原材料，长

4、7.4米,一套钢架,任务：100套钢架 目标：成本最少,2.9m,2.1m,1.5m,分析下料的方式,原材料7.4m,2.9m的元钢不少于100根： 2x1+ x2 + x3 + x4100,2.1m的元钢不少于100根： 2x2 + x3 + 3x5 +2 x6 + x7 + x8 100,1.5m的元钢不少于100根： x1+ x3 + 3x4 + x5 + 2x6 +3 x7 + 4x8 100,模型建立,1、设(未知数)决策变量 设按方案下料的原材料根数为x1,方案为x2，方案为x3，方案为x4,方案为x5 ，方案为x6，方案为x7,方案为x8 。 2、用决策变量表达目标函数 min

5、z= x1+ x2 + x3 + x4 + x5 + x6 + x7 + x8 3、用决策变量表达全部的约束条件 4、注意符号约束,数学模型为,min z= x1+ x2 + x3 + x4 + x5 + x6 + x7 + x8 2x1+ x2 + x3 + x4100 2x2 + x3 + 3x5 +2 x6 + x7 + x8 100 x1 + x3 + 3x4 + x5 + 2x6 +3 x7 + 4x8 100 xj 0， xj 为整数，j=1,2,8,能够求出最优解为： x1=10 ，x2 =50 ，x4 =30 (最优值)minz=90,教材上的模型说明,例4 人事管理问题,一个

6、企业每周七天都要生产或营业 每个工作人员每周连续5天 据分析每天的上班人数分别60、40、50、30、65、70和75人 问该企业至少需要多少个职工？,模型建立,1、设(未知数)决策变量 设从星期一开始上班的人数为x1,星期二开始上班的人数为x2，星期三开始上班的人数为x3，星期四开始上班的人数为x4,星期五开始上班的人数为x5 ，星期六开始上班的人数为x6，星期日开始上班的人数为x7。 2、用决策变量表达目标函数 min z= x1+ x2 + x3 + x4 + x5 + x6 + x7 3、用决策变量表达全部的约束条件 4、注意符号约束,min z=x1+ x2 + x3 + x4 +

7、x5 + x6 + x7 x4 + x5 + x6 + x7 + x1 60 x5 + x6 + x7 + x1+ x2 40 x6 + x7 + x1+ x2 + x3 50 x7 + x1+ x2 + x3 + x4 30 x1+ x2 + x3 + x4 + x5 65 x2 + x3 + x4 + x5 + x6 70 x3 + x4 + x5 + x6 + x7 75 xj 0， xj 为整数，j=1,2,7,数学模型为,能够求出最优解为： x1=9 ，x2 =0， x3 =23，x4 =19， x5 =14， x6 =19， x7 =0 (最优值)minz=84,例5 配料问题,模

8、型建立,1、设(未知数)决策变量 设A产品中含原材料C、P、H的数量分别为AC、AP、AH B产品中含原材料C、P、H的数量分别为BC、BP、BH D产品中含原材料C、P、H的数量分别为DC、DP、DH。 2、用决策变量表达目标函数(利润=销售收入-成本) max z= 50(AC+AP+AH)+35(BC+BP+BH)+25(DC+DP+DH)-65(AC+ BC+ DC)-25(AP+ BP+ DP)-35(AH +BH +DH) = -15AC+25AP+15AH-30BC+10BP-40DC-10DH 3、用决策变量表达全部的约束条件 4、注意符号约束,约束条件,整理得,AC+BC+D

9、C100 AP+BP+DP100 AH+BH+DH60,含量约束,原材料数量约束,数学模型为,max z= -15AC+25AP+15AH-30BC+10BP-40DC-10DH,AC、AP、AH， BC、BP、BH ，DC、DP、DH0,能够求得最优解和最优值,最优解 需要用原料C为100kg，P为50kg，H为50kg，构成产品A。其它产品不生产。 即每天只生产产品A为200kg，分别需要用原料C为100kg，P为50kg，H为50kg。 最优值即总利润是z=500元/天。,例6 运输问题的数学模型,在经济建设中，经常碰到大宗物资调运问题。根据已有的交通网,应如何制定调运方案，将这些物资从

10、产地运往销地，使总运费最小。这 样的问题可用以下数学语言描述：,已知有m个生产地点Ai,i=1,2,m.可供应某种物资（如土石方），其供应量（产量，挖方）分别为ai, i=1,2,m. 有n个销地Bj,j=1,2,n,其需要量（填方）分别为bj, j=1,2,n。 从Ai到Bj运输单位物资的运价（单价）为cij， 这些数据可汇总于产销（平衡表）和单位运价表中，见表3-1，3-2,表3-1 运输平衡表,表3-2 运价表,运 输表,例如,运输问题建摸,运输问题要解决什么？ 什么叫一个运输方案？ 什么叫一个最优的运输方案？ 若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，求总运费最小的方案

11、，,运输问题建模,可建立以下数学模型（产销平衡）,运输问题数学模型,x11+ x12+ + x1n=a1 x21+ x22+ + x2n=a2 xm1+ xm2+ + xmn=am x11+ x21+ + xm1=b1 x12+ x22+ + xm2=b2 X1n+ x2n+ + xmn=bn Xij 0,（产销不平衡）产大于销,x11+ x12+ + x1na1 X21+ x22+ + x2na2 xm1+ xm2+ + xmn am x11+ x21+ + xm1=b1 x12+ x22+ + xm2=b2 X1n+ x2n+ + xmn=bn Xij 0,（产销不平衡）销大于产,X11+

12、 x12+ + x1n = a1 X21+ x22+ + x2n = a2 Xm1+ xm2+ + xmn = am X11+ x21+ + xm1 b1 X12+ x22+ + xm2 b2 X1n+ x2n+ + xmn bn Xij 0,例7 指派问题的数学模型,在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务不同（或所费时间），效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需总时间最小）。这问题称为指派问题或分派问题（Assignment problem）。,招投标问题,一般地：有n项加工任

13、务，怎样指派到n台机床上分别完成的问题；有n条航线，怎样指定n艘船去航行问题等等。对应每个指派问题，需有类似表5-7那样的数表，称为效率矩阵或系数矩阵，其元素cij（）0（i,j=1,2.,n）表示指派第i人去完成第j项任务时的效率（或时间、成本等）。 解题时需引入变量xij；其取值只能是1或0。并令 1 当指派第i人去完成第j项任务 xij= 0 当不指派第i人去完成第j项任务,当问题要求极小化时数学模型是：, xij=1或0 约束条件说明第j项任务只能由1人去完成；约束条件说明第i人只能完成1项任务。满足约束条件-的可行解xij也可写成表格或矩阵形式，称为解矩阵。,例8 0-1变量在建立模

14、型中的应用,例4 某公司拟在市东、西、南三区建立门市部，拟议中有7个位置（点）Ai(i=1,2,7)可供选择。要求 在东区， A1， A2， A3三个点中至多选两个； 在西区， A4， A5两个点中至少选一个； 在南区， A6， A7两个点中至少选一个。 如选用Ai，设备投资估计为bi元,每年可获利润估计为ci元，但投资总额不能超过B元，问可选择哪几个点可使年利润最大？,解,1 当Aj被选中 xj= j=1,2,7 0当Aj未被选中,例9 0-1变量在表达约束条件的特殊作用,相互排斥的约束条件,在本章开始的例1中，关于运货的体积限制为 5x1+4x224 (5.9) 今设运货的方式有车运和船运

15、两种，上面的条件系用车运时的限制条件，如用船运时关于体积的限制条件为 7x1+3x245 (5.10) 这两个条件是相互排斥的，为了统一在一个问题中，引入0-1变量y,令, 二者择一,如例1中体积约束：,车运 5x1 + 4x2 24 船运 7x1 + 3x2 45,引入0-1变量y ，令 体积约束为： 5x1 + 4x2 24 + yM 7x1 + 3x2 45 + (1-y)M y = 0或1 其中M为充分大的数。,车运 y =0 船运 y=1,相互排斥的约束条件,这m个约束条件变为m+1个约束条件和m个变量。,第i个约束条件起作用, 第i个约束条件不起作用。,有m个互相排斥的约束条件： ( i =1，m),引入m个0-1变量yi ，,只有一个条件起作用, 多者择一,问题：如果要两个或最多两个约束条件成立呢？,相互排斥的约束条件,5x1+