运筹学理论与建模课件.ppt

1、运筹学理论与建模运筹学理论与建模 主要内容主要内容第一部分第一部分 线性规划建模方法线性规划建模方法第二部分第二部分 整数规划建模方法整数规划建模方法第三部分第三部分 指派问题指派问题第四部分第四部分 动态规划建模动态规划建模第五部分第五部分 图论与网络优化图论与网络优化第一部分第一部分 线性规划建模方法线性规划建模方法一、从现实问题到线性规划模型一、从现实问题到线性规划模型二、线性规划模型的求解二、线性规划模型的求解三、线性规划建模实例三、线性规划建模实例例例1 加工奶制品的生产计划加工奶制品的生产计划1桶桶牛奶牛奶 3公斤公斤A1 12小时小时 8小时小时 4公斤公斤A2 或或获利获利24

2、元元/公斤公斤 获利获利16元元/公斤公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到 30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天每天:一、从现实问题到线性规划模型一、从现实问题到线性规划模型1桶桶牛奶牛奶 3公斤公斤A1 12小时小时 8小时小时 4公斤公斤A2 或或获利获利2

3、4元元/公斤公斤 获利获利16元元/公斤公斤 x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 获利获利 243x1 获利获利 164 x2 原料供应原料供应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031 x决策变量决策变量 目标函数目标函数 216472xxzMax 每天获利每天获利约束条件约束条件非负约束非负约束 0,21 xx线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型分析与假设模型分析与假设 比比例例性性 可可加加性性 连续性连续性 xi对目标函数的对目标函数的

4、“贡献贡献”与与xi取值取值成正比成正比 xi对约束条件的对约束条件的“贡献贡献”与与xi取值取值成正比成正比 xi对目标函数的对目标函数的“贡献贡献”与与xj取值取值无关无关 xi对约束条件的对约束条件的“贡献贡献”与与xj取值取值无关无关 xi取值连续取值连续 A1,A2每公斤的获利是与各每公斤的获利是与各自产量无关的常数自产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和的数量和时间是与各自产量无关的常数时间是与各自产量无关的常数A1,A2每公斤的获利是与相每公斤的获利是与相互产量无关的常数互产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和的数量和是与时间相互产量无

5、关的常数是与时间相互产量无关的常数加工加工A1,A2的牛奶桶数是实数的牛奶桶数是实数 线性规划模型线性规划模型A1A2现有资源现有资源设备设备128台时台时甲甲4016公斤公斤乙乙0412 公斤公斤利润利润2030（元）（元）制订生产计划制订生产计划,使使每天获利最大每天获利最大 例例2 2 工厂生产两种工厂生产两种产品产品A1,A2,已知生已知生产单位产品情况如产单位产品情况如表：表：设设生产生产A1、A2分别分别x1、x2公斤公斤 max z=20 x1+30 x2 (1)1212121228,(2)4016,(3).0412,(4)0,0.(5)xxxxs txxxx目标函数目标函数约约

6、束束条条件件决策变量决策变量一、从现实问题到线性规划模型一、从现实问题到线性规划模型线性规划模型标准型线性规划模型标准型:maxz=c1 x1+c2x2+cnxn11112211211222221122,.,0,1,.nnnnmmmnnmiaxaxaxbaxaxaxbs taxaxaxbxin (LP)线性规划模型标准型矩阵表示：线性规划模型标准型矩阵表示：max z=cX.0s tAXbX 12,ncc cc12,Tmbb bb12,TnXx xx.ij m nAa0,b max(min)z=c1 x1+c2x2+cnxn1111221121122222112211(,),(,),.(,),

7、0,0,.nnnnmmmnnmijkla xa xa xba xa xaxbs taxaxaxbxxiiijjj 线性规划模型一般形式：线性规划模型一般形式：1.线性规划的一般形化为标准型的一般步骤线性规划的一般形化为标准型的一般步骤(1)Min f=cX 转化为转化为max z=cX(2)1122iiinna xa xa x ib 加松弛变量加松弛变量yi 1122iiinniia xa xa xyb 1122iiinna xa xa x (3)ib 加剩余变量加剩余变量yi1122iiinniia xa xa xyb (4)若存在可正可负变量若存在可正可负变量xi 令令12,iiixxx

8、12,0.iixx 例例 将下述线性规划问题化为标准型将下述线性规划问题化为标准型1231231231237,2,.325,0,xxxxxxs txxxx xx min z=x1+2x2 3x3无约束无约束标准型标准型maxz =x1 2x2+3(x4 x5)+0 x6+0 x7 124561245712451245677,2,.3225,0.xxxxxxxxxxs txxxxxxxxxx (1)x3=x4 x5,x4,x5 0(2)x1+x2+x3+x6=7(3)x1 x2+x3 x7=2合理下料问题合理下料问题 有长度为有长度为8米的某型号圆米的某型号圆钢，现需要长度为钢，现需要长度为2.

9、5米的米的毛坯毛坯100根，长度为根，长度为1.3米米的毛坯的毛坯200根，如何选者下根，如何选者下料方式，所需总用料最省料方式，所需总用料最省?解：可能的下料方式：解：可能的下料方式：2.51.3130222314406设按第设按第i种下料方式的种下料方式的圆钢圆钢xi根，根，i=1,2,3,4 min z=x1+x2+x3+x4 12323432100,.246200,0,1,2,3,4.ixxxs txxxxi 有一组决策变量有一组决策变量,约束条件是决约束条件是决策变量的线性等式或不等式策变量的线性等式或不等式,目目标函数是决策变量的线性函数标函数是决策变量的线性函数,这样的规划问题称

10、为线性规划这样的规划问题称为线性规划.记为（记为（LP）例例.某小区一个某小区一个24小时营业便利店小时营业便利店,一一天各时段所需服务员最少人数如下天各时段所需服务员最少人数如下表表.根据实际情况根据实际情况,要求每个服务员必要求每个服务员必须连续工作八小时须连续工作八小时,试建立需服务员试建立需服务员总人数最少的排班方案数学模型总人数最少的排班方案数学模型.班次班次123456时间时间2-6 6-10 10-1414-1818-2222-2人人48107124解：解：设各班次设各班次新增服务员数分别为新增服务员数分别为 x1,x2,x3,x4,x5,x6,则则 min z=x1+x2+x3

11、+x4+x5+x66112233445564,8,10,7,.12,4,0,1,6.ixxxxxxxxs txxxxxi 且且xi为整数为整数连续投资问题连续投资问题某部门计划某部门计划5年内用一百万年内用一百万投资下列项目：投资下列项目：A：从第一年到第四年初可：从第一年到第四年初可投资，次年末回收本利投资，次年末回收本利115%B:第三年初可投资，第五年第三年初可投资，第五年末回收本利末回收本利125%，投资，投资额额40万万C:第二年初可投资，第五年第二年初可投资，第五年末回收本利末回收本利140%，投资，投资额额30万万D：每年初可购买公债，当：每年初可购买公债，当年末归还，利息年末归

12、还，利息6%如何投资，五年后获利最大？如何投资，五年后获利最大？解：设解：设第第i年初投资项目年初投资项目A,B,C,D分别为分别为xiA,xiB,xiC,xiD 万元万元,i=1,2,3,4,5x1A+x1D=100,x2A+x2C+x2D=1.06 x1D,x3A+x3B+x3D=1.06 x2D+1.15 x1A,x4A+x4D=1.06 x3D+1.15 x2A,x5D=1.06 x4D+1.15 x3A,x2C 40,x3B 30,xiA,xiB,xiC,xiD0，i=1,2,3,4,5.Max Z=1.15x4A+1.40 x2C+1.25x3B+1.06 x5Ds.t.二、线性规

13、划模型的求解二、线性规划模型的求解（一）图解法（一）图解法（n 3时）时）（二）单纯形法（二）单纯形法max z=c x.,0s tAXbX(LP):,0DX AX b X可行解：满足约束条件可行解：满足约束条件AX=b,X最优解最优解:可行解中使目标最优的可行解中使目标最优的.即即X*D,且任意且任意XD,CX*CX可行集：所有可行解的集合可行集：所有可行解的集合0的的X的值的值12,Tnx xx制订生产计划制订生产计划,使每天获利使每天获利最大最大.工厂生产两种产品工厂生产两种产品A1,A2,已已知生产单位产品情况如下：知生产单位产品情况如下：设设生产生产A1、A2分别分别x1、x2公斤公

14、斤 max z=20 x1+30 x2 (1)1212121228,(2)4016,(3).0412,(4)0,0.(5)xxxxs txxxx A1A2现有资源现有资源设备设备128台时台时甲甲4016公斤公斤乙乙0412 公斤公斤利润利润2030（元）（元）（一）图解法（一）图解法（n 3时）时）(1)在平面上作出可行集在平面上作出可行集ABCD34z=140z=0由图解法直观得由图解法直观得:n=2时时,(LP)的可行集是凸多边形的可行集是凸多边形,最优解最优解可以在其某个顶点处达到可以在其某个顶点处达到.线性规划基本性质线性规划基本性质:(LP)的可行集是的可行集是凸多面体凸多面体,最

15、优解可以在凸多面体的最优解可以在凸多面体的某个顶点处达到某个顶点处达到.线性规划求解思路线性规划求解思路:通过通过代数的方法描述代数的方法描述高维空间凸多高维空间凸多面体的面体的顶点顶点,再使用再使用经济经济的方法来的方法来求出达到极值的顶点求出达到极值的顶点.x1x20(2)在可行集中找最优解在可行集中找最优解 max z=20 x1+30 x2 (1)1212121228,(2)4016,(3).0412,(4)0,0.(5)xxxxs txxxx z=60引入松弛变量引入松弛变量x3,x4,x5,化为标准形化为标准形:（二）单纯形法（二）单纯形法),(100010102010001565

16、4321PPPPPA 系数矩阵为系数矩阵为 815060b显然显然A的秩的秩为为3,任取任取3个线性无关的列向量个线性无关的列向量,如如P1,P2,P3称为一称为一组组基基,记为记为B=(P1,P2,P3).P1,P2,P3 称为称为基基向量向量,基基向量向量对应对应的变量的变量 x1,x2,x3称为称为基变量基变量,其余列向量其余列向量 P4,P5 称为称为非非基向量基向量,记为记为N=(P4,P5).非基对应的变量非基对应的变量 x4,x5 称为称为非基变量非基变量.A=(B,N),相应相应X=(XB,XN)T,c=(cB,cN)AX=BXB+NXN=b,则则 XB=B 1b B 1 NX

17、N,),(1000101020100015654321PPPPPA 系数矩阵为系数矩阵为 815060b令非基变量令非基变量XN=0,解得基变量解得基变量XB=B-1b,称称(XB,XN)为为基本解基本解.解的所有变量的值都非负解的所有变量的值都非负,则称为则称为基本可行解基本可行解,此时的基称此时的基称为为可行基可行基.基本可行解对应的目标值为基本可行解对应的目标值为f=cBB-1b.若可行基进一步满足若可行基进一步满足:cN cBB-1N0,则对一切可行解则对一切可行解X,必有必有f(x)cBB-1b,此时称基可行解此时称基可行解X=(B-1b,0)T为为最优解最优解.另一个基另一个基本可

18、行解本可行解定理：定理：(LP)的可行集的的可行集的顶点顶点与与(LP)的的 基本可行解基本可行解一一对应。一一对应。单纯形法基本思想：单纯形法基本思想：目标目标重复此重复此更优更优过程过程单纯形法基本步骤：单纯形法基本步骤：不是不是最优解最优解更优更优目标目标重复此重复此过程过程(LP)的某个的某个基本可行解基本可行解最优解最优解(LP)的的某个基某个基基基本本可可行解行解另一另一个基个基基本基本可行解可行解最优解最优解 即从可行域的即从可行域的(基本可行解基本可行解)开始开始,(另一个基本可行解另一个基本可行解)的迭代过程的迭代过程,转移的条件转移的条件是是使使(逐步变优逐步变优),当目标

19、函数达到最优值时当目标函数达到最优值时,问题也就得问题也就得到了最优解到了最优解.顶点转移的依据？顶点转移的依据？根据根据线性规划问题的可行域是凸多边形或凸多面体线性规划问题的可行域是凸多边形或凸多面体,一个一个线性规划问题有最优解线性规划问题有最优解,就一定可以在可行域的顶点上找到就一定可以在可行域的顶点上找到.于是于是,若某线性规划只有唯一的一个最优解若某线性规划只有唯一的一个最优解,这个最优解这个最优解所对应的点一定是可行域的一个顶点所对应的点一定是可行域的一个顶点;若该线性规划有多个最若该线性规划有多个最优解优解,那么肯定在可行域的顶点中可以找到至少一个最优解那么肯定在可行域的顶点中可

20、以找到至少一个最优解.(1)顶点的逐步转移顶点的逐步转移 使目标函数值得到改善使目标函数值得到改善 得到得到LP最优解，目标函数达到最优值最优解，目标函数达到最优值 （单纯形法的由来？（单纯形法的由来？）2需要解决的问题：需要解决的问题：(1)为了使目标函数逐步变优，怎么转移？为了使目标函数逐步变优，怎么转移？(2)目标函数何时达到最优目标函数何时达到最优判断标准是什么？判断标准是什么？2.单纯形法原理（用代数方法求解单纯形法原理（用代数方法求解LP）123123123123max2333.479,0zxxxxxxs txxxx xx 劳动力劳动力原材料原材料利润利润A112B143C173现

21、有资源现有资源39劳动力约束劳动力约束原材料约束原材料约束第一步：引入非负的松弛变量第一步：引入非负的松弛变量x4,x5,将该将该LP化为标准型化为标准型123451234123512345max233003.479,0zxxxxxxxxxs txxxxx xxxx 第二步：寻求初始可行基，确定基变量第二步：寻求初始可行基，确定基变量1 1 1 1 01 4 7 0 1A 1001,54PPB对应的基变量是对应的基变量是 x4，x5；第三步：写出初始基本可行解和相应的目标函数值第三步：写出初始基本可行解和相应的目标函数值两个关键的基本表达式：两个关键的基本表达式：用非基变量表示基变量的表达式用

22、非基变量表示基变量的表达式41235123(0)3947(0,0,0,3,9)TxxxxxxxxX 初初始始基基本本可可行行解解用非基变量表示目标函数的表达式用非基变量表示目标函数的表达式123233zxxx 0)0(Z当当前前的的目目标标函函数数值值请解释结果的经济含义请解释结果的经济含义 不生产任何产品不生产任何产品,资源全部节余资源全部节余(x4=3，x5=9),三种产品的总利润为三种产品的总利润为0！第四步：分析两个基本表达式，看看目标函数是否可以改善？第四步：分析两个基本表达式，看看目标函数是否可以改善？分析用非基变量表示目标函数的表达式分析用非基变量表示目标函数的表达式123233

23、zxxx 非基变量前面的系数均为正数，所以任何一个非基变量进基都非基变量前面的系数均为正数，所以任何一个非基变量进基都能使能使z值增加值增加通常把非基变量前面的系数叫通常把非基变量前面的系数叫“”；选哪一个非基变量进基？选哪一个非基变量进基？选选x2为为进基变量进基变量（换入变量换入变量）问题：能否选其他的非基变量进基？问题：能否选其他的非基变量进基？任意一个任意一个 任意一个正检验数对应的非基变量任意一个正检验数对应的非基变量 最大正检验数对应的非基变量最大正检验数对应的非基变量 排在排在最前面的正检验数对应的非基变量最前面的正检验数对应的非基变量 确定出基变量：确定出基变量：问题讨论问题讨

24、论 x2进基意味着其取值从进基意味着其取值从0变成一个正数（经济意义变成一个正数（经济意义生产生产B 产品），能否无限增大？产品），能否无限增大？当当x2增加时，增加时，x4，x5如何变化？如何变化？现在的非基变量是哪些？现在的非基变量是哪些？321532147493xxxxxxxx由由用非基变量表示基变量的表达式用非基变量表示基变量的表达式 当当x2增加时增加时,x4,x5会减小会减小,但有限度但有限度必须大于等于必须大于等于0,以保以保持解的可行性！于是持解的可行性！于是24225223303 991min,9 4091 444xxxxxxx 当当x2的值从的值从0增加到增加到9/4时时,

25、x5首先变为首先变为0，此时，此时x4=3/40,因此因此选选x5为出基变量为出基变量(换出变量换出变量).这种用来确定出基变量的规则称为这种用来确定出基变量的规则称为 如果如果P10，会出现什么问题？，会出现什么问题？最小比值原则会失效！最小比值原则会失效！新的基变量新的基变量x2,x4；新的非基变量；新的非基变量x1,x3,x5；写出写出412351233947xxxxxxxx 由由213541359171444433314444xxxxxxxx X(1)=(0，9/4，0，3/4，0)T12311353135233917123()344442751234444Zxxxxxxxxxxx 可

26、得相应的目标函数值为可得相应的目标函数值为 z(1)=27/4检验数仍有正的检验数仍有正的,返回返回进行讨论进行讨论.当当用非基变量表示目标函数的表达式用非基变量表示目标函数的表达式中中,时时,当前的基本可行解当前的基本可行解就是就是!为什么？为什么？分析分析:用非基变量表示目标函数的表达式用非基变量表示目标函数的表达式,如果如果让负检验数让负检验数 所对应的变量进基所对应的变量进基，目标函数值将下降！目标函数值将下降！x1 x2 x3 x4 x52 3 3 0 0b XB1 1 1 1 01 4 7 0 13 x49 x52 3 3 0 0z123451234123512345max2330

27、03.479,0zxxxxxxxxxst xxxxx x x x x 把目标函数表达式改写成方程的形式，和原有的把目标函数表达式改写成方程的形式，和原有的m个约束个约束方程组成一个具有方程组成一个具有n+m+1个变量、个变量、m+1个方程的方程组：个方程的方程组：1111221112112222221122112211nnnnnnmmmnnn mmnnnnn mn ma xa xa xxba xa xa xxba xa xa xxbc xc xc xcxcxz 取出系数写成增广矩阵的形式：取出系数写成增广矩阵的形式：xn+1，xn+m所对应的系数列向量构成一个基所对应的系数列向量构成一个基.1

28、11211212222121212100010001nnmmmnmnnnn maaabaaabaaabccccccz 1212nnnn mxxxxxxb 用矩阵的初等行变换将目标函数中基变量系数化为零用矩阵的初等行变换将目标函数中基变量系数化为零,这时这时 变成变成0，相应的增广矩阵变成如下形式：，相应的增广矩阵变成如下形式：12,nnnmccc 1mjjn iijicca 01mn iiizcb 其中，其中，j=1，2，n；111211212222120121000 100 010 00nnmmmnmnaaabaaabaaabzz 增广矩阵的最后一行就是用非基变量表示目标函数的表增广矩阵的最

29、后一行就是用非基变量表示目标函数的表达式达式,j(j=1,2,n）就是非基变量的检验数）就是非基变量的检验数.（3）检验数的两种计算方法：）检验数的两种计算方法：利用矩阵的行变换，把目标函数表达式中基变量前面的系利用矩阵的行变换，把目标函数表达式中基变量前面的系 数变为数变为0；使用计算公式使用计算公式 1,1,2,.mjjn iijjBjjjicc acC Pczjn 2.例例1的表格单纯形法计算过程：的表格单纯形法计算过程：x1 x2 x3 x4 x5 2 3 3 0 0z1 1 1 1 03 x41 4 7 0 1 9 x5 2 3 3 0 0z3/4 0 -3/4 1 -1/43/4

30、x41/4 1 7/4 0 1/49/4 x25/4 0 9/4 0 -3/4z-27/4 1 0 -1 4/3 -1/3 1 x1 0 1 2 -1/3 1/3 2 x2 0 0 -1 -5/3 -1/3z-8*表格单纯形法求解步骤表格单纯形法求解步骤第一步：第一步：将将LPLP化为标准型化为标准型，引入适当的松驰变量、剩余变量和人工变量引入适当的松驰变量、剩余变量和人工变量,使约束条件使约束条件化为等式化为等式,第二步：第二步：最优性检验最优性检验是是结束结束,写出最优解和目标函数最优值写出最优解和目标函数最优值;检查相应系数列检查相应系数列 0？是是结束结束,该该LP无无“有限最优解有限

31、最优解”！，转入下一步，转入下一步基变换基变换.确定是停止迭代还是转入基变换？确定是停止迭代还是转入基变换？选择选择(最大最大)对应的系数列为对应的系数列为,主元列对主元列对应的非基变量为应的非基变量为 最小比值对应的行为最小比值对应的行为,主元行主元行对应的基变量为对应的基变量为.第三步：第三步：基变换基变换确定进基变量和出基变量确定进基变量和出基变量.第四步第四步 换基迭代（旋转运算、枢运算换基迭代（旋转运算、枢运算)利用矩阵的利用矩阵的把把,从而得到一张新的单从而得到一张新的单纯形表纯形表,返回第二步返回第二步.完成一次迭代，得到新的基本可行解和相应的目标函数值完成一次迭代，得到新的基本

32、可行解和相应的目标函数值.该迭代过程直至下列情况之一发生时停止该迭代过程直至下列情况之一发生时停止检验数行全部变为非正值；检验数行全部变为非正值；（得到最优解）（得到最优解）或或主元列主元列 0 （最优解无界）（最优解无界）停止迭代的标志（停机准则）停止迭代的标志（停机准则）自来水输送与货机装运自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；怎样安排输送方案使运费最小，或利润最大；运输问题运输问题各种类型的货物装箱，由于受体积、重量等限制，各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载

33、，使获利最高，或装箱数量最少如何搭配装载，使获利最高，或装箱数量最少.三、线性规划建模实例三、线性规划建模实例其他费用其他费用:450元元/千吨千吨 应如何分配水库供水量，公司才能获利最多？应如何分配水库供水量，公司才能获利最多？若水库供水量都提高一倍，公司利润可增加到多少？若水库供水量都提高一倍，公司利润可增加到多少？元元/千吨千吨甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费例例1 自来水输送自来水输送收入：收入：900元元/千吨千吨 支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁

34、：10；40水库供水量水库供水量(千吨千吨)小区基本用水量小区基本用水量(千吨千吨)小区额外用水量小区额外用水量(千吨千吨)（以天计）（以天计）总供水量：总供水量：160确定送水方案确定送水方案使利润最大使利润最大问题问题分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40 总需求量总需求量(300)每个水库最大供水量都提高一倍每个水库最大供水量都提高一倍利润利润 =收入收入(900)其它费用其它费用(450)引水管理费引水管理费利润利润(元元/千吨千吨)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220

35、/1112131421222324313233290320230280310320260300260250220Max zxxxxxxxxxxx 供应供应限制限制B,C 类似处理类似处理11121314:50Axxxx11121314100 xxxx 问题讨论问题讨论 确定送水方案确定送水方案使利润最大使利润最大需求约束可以不变需求约束可以不变如何如何装运，装运，使本次飞行使本次飞行获利最大？获利最大？例例2 货机装运货机装运 重量（吨）重量（吨）空间空间(米米3/吨）吨）利润（元利润（元/吨）吨）货物货物1184803100货物货物2156503800货物货物3235803500货物货物41

36、23902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例 前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡三个货舱三个货舱最大最大载载重重(吨吨),),最大容积最大容积(米米3 3)决策决策变量变量 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量(吨）吨）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)模型假设模型假设 每种货物可以分割到任意小；每种货物可以分割到任意小；货机装运货机装运每种货物可以在一个或多个货舱中任意分布；每种货物可以在一个或多个货舱中任意

37、分布；多种货物可以混装，并保证不留空隙；多种货物可以混装，并保证不留空隙；模型建立模型建立 货舱货舱容积容积 目标目标函数函数(利润利润)约束约束条件条件 )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxZMax680039058065048041312111xxxx870039058065048042322212xxxx530039058065048043332313xxxx货机装运货机装运模型建立模型建立 货舱货舱重量重量 1041312111xxxx1642322212xxxx843332313xxxx10；6800

38、16；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量约束约束条件条件平衡平衡要求要求 81610433323134232221241312111xxxxxxxxxxxx货物货物供应供应 18131211xxx15232221xxx23333231xxx12434241xxx货机装运货机装运模型建立模型建立 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量第二部分第二部分 整数规划建模方法整数规划建模方法一、整数规划简介一、整数规划简介二、二、整数整数规划的规划的分分支定界法支定界法三、三、

39、整数整数规划的建模实例规划的建模实例2.1 整数规划简介整数规划简介v要求所有要求所有 xj 的解为整数，称为纯整数规划的解为整数，称为纯整数规划v要求部分要求部分 xj 的解为整数，称为混合整数规划的解为整数，称为混合整数规划v对应没有整数解要求的线性规划称之为松弛问题对应没有整数解要求的线性规划称之为松弛问题v整数规划的解是可数个的，最优解不一定发生在极点整数规划的解是可数个的，最优解不一定发生在极点v整数规划的最优解不会优于其松弛问题的最优解整数规划的最优解不会优于其松弛问题的最优解11max(min)()(,),1,2,.0,1,2,njjjnijjijjf xc xa xbims t

40、xjn 且且 整整且为整数且为整数2.2 整数规划的分枝定界法整数规划的分枝定界法3.求解分枝的松弛问题求解分枝的松弛问题 定界过程定界过程设两个分枝的松弛问题分别为问题设两个分枝的松弛问题分别为问题 1 和问题和问题 2,它们的最它们的最优解有如下情况优解有如下情况:2.2.1 思路与解题步骤思路与解题步骤只解松弛问题只解松弛问题1.在全部可行性域上解松弛问题在全部可行性域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最优解若松弛问题最优解为整数解，则其也是整数规划的最优解2.分枝过程分枝过程若松弛问题最优解中某个若松弛问题最优解中某个 xk=bk 不是整数，令不是整数，令 bk为

41、为 bk 的整数的整数部分部分:构造两个新的约束条件构造两个新的约束条件 xk bk 和和 xk bk+1，分别加，分别加于原松弛问题，形成两个新的整数规划于原松弛问题，形成两个新的整数规划.表表2.2.1 分枝问题解可能出现的情况分枝问题解可能出现的情况情况情况 2,4,5 找到最优解找到最优解情况情况 3 在缩减的域上继续分枝定界法在缩减的域上继续分枝定界法情况情况 6 问题问题 1 的整数解作为的整数解作为界界被保留，用于以后与问题被保留，用于以后与问题 2 的后的后续分枝所得到的解进行比较，结论如情况续分枝所得到的解进行比较，结论如情况 4 或或 5序号序号问题问题1问题问题2说明说明

42、1无可行解无可行解无可行解无可行解整数规划无可行解整数规划无可行解2无可行解无可行解整数解整数解此整数解即为最优解此整数解即为最优解3无可行解无可行解整数解非整数解非对问题对问题2继续分枝继续分枝4整数解整数解整数解整数解较优的一个为最优解较优的一个为最优解5整数解整数解,目标函数目标函数值优于值优于2非整数解非整数解问题问题1的解即为最优解（剪枝）的解即为最优解（剪枝）6整数解整数解整数解整数解,目标函目标函数值优于数值优于1问题问题1停止分枝，其整数解为界，停止分枝，其整数解为界，对问题对问题2继续分枝继续分枝 2.2.2 分枝定界法举例分枝定界法举例 例例2.1.1 且为整数且为整数 0

43、,7 2134246)(max21212121xxxxxxxxxf解：解：松弛问题的最优解为松弛问题的最优解为 x1=2.5,x2=2,OBJ=23 由由 x1=2.5 得到两个分枝如下：得到两个分枝如下：且为整数且为整数问题问题 0,2 7 21342I46)(max211212121xxxxxxxxxxf且为整数且为整数问题问题 0,3 7 21342II46)(max211212121xxxxxxxxxxf 表表2.2.3 分枝问题的松弛解分枝问题的松弛解问题问题II的解即原整数问题的最优解的解即原整数问题的最优解 可能存在两个分枝都是非整数解的情况，则需要两边同时可能存在两个分枝都是非

44、整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程继续分枝，直到有整数解出现，就可以进行定界过程.当存在很多变量有整数约束时，分枝即广又深，在最坏情当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解况下相当于组合所有可能的整数解.一般整数规划问题属于一类未解决的难题，一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如只有少数特殊问题有好的算法，如任务分配问题、匹配问题任务分配问题、匹配问题.例例.某厂拟用集装箱托运某厂拟用集装箱托运甲甲,乙两种货物。已知乙两种货物。已知货物货物体积体积(米米3/箱箱

45、)重量重量(吨吨/箱箱)利润利润(百元百元/箱箱)甲甲9740乙乙72090托运托运限制限制5670问：如何安排利润最大？问：如何安排利润最大？设甲乙分别托运设甲乙分别托运x1,x2箱箱模型建立模型建立 12max4090(1)zxx IP(1)-(4)称为与称为与(IP)相相对应的线性规划对应的线性规划(LP)求解求解(LP)得得 x1=4.81,x2=1.82,z=356121212129756(2)72070(3).,0(4),(5)xxxxs txxxx 为整数为整数分枝定界法分枝定界法(branch and bound method)(IP)x1*,x2*,z*(LP)x1=4.81

46、,x2=1.82,z0=356(LP1)x1=4,x2=2.1,z0=349X14X15(LP2)x1=5,x2=1.57,z0=341(z*349定界定界)(LP3)x1=4,x2=2,z0=340X22X23(LP4)x2=3,x1=1.42,z0=327(z*340 定界定界)(LP5)x2=1,x1=5.44,z0=308X21(LP6)无无可行解可行解X22x14x15分枝：分枝：应如何安排原油的采购和加工应如何安排原油的采购和加工？例例2 原油采购与加工原油采购与加工 市场上可买到不超过市场上可买到不超过1500吨的原油吨的原油A：购买量不超过购买量不超过500吨时的单价为吨时的单

47、价为10000元元/吨；吨；购买量超过购买量超过500吨但不超过吨但不超过1000吨时，超过吨时，超过500吨的吨的 部分部分8000元元/吨；吨；购买量超过购买量超过1000吨时，超过吨时，超过1000吨的部分吨的部分6000元元/吨吨.售价售价4800元元/吨吨 售价售价5600元元/吨吨库存库存500吨吨 库存库存1000吨吨 汽油甲汽油甲(A 50%)原油原油A 原油原油B 汽油乙汽油乙(A 60%)2.3整数整数规划的建模实例规划的建模实例决策决策变量变量 目标目标函数函数问题问题分析分析 利润：销售汽油的收入利润：销售汽油的收入 购买原油购买原油A的支出的支出 难点：原油难点：原油

48、A的购价与购买量的关系较复杂的购价与购买量的关系较复杂)()(6.5)(8.422122111xcxxxxzMax甲甲(A 50%)A B 乙乙(A 60%)购买购买xx11x12x21x224.8千元千元/吨吨 5.6千元千元/吨吨原油原油A的购买量的购买量,原油原油A,B生产生产汽油汽油甲甲,乙的数量乙的数量c(x)购买原油购买原油A的支出的支出利润利润(千元千元)c(x)如何表述？如何表述？原油供应原油供应 约束约束条件条件xxx500121110002221 xx1500 x10 (0500)8 1000 (5001000)63000 (10001500)()xxc xxxxx x 5

49、00吨单价为吨单价为10千千元元/吨；吨；500吨吨 x 1000吨，超过吨，超过500吨的吨的8千千元元/吨；吨；1000吨吨 x 1500吨，超过吨，超过1000吨的吨的6千千元元/吨。吨。目标目标函数函数购买购买x A B x11x12x21x22库存库存500吨吨 库存库存1000吨吨 目标函数中目标函数中c(x)不是线性函数，是非线性规划；不是线性函数，是非线性规划；对于用分段函数定义的对于用分段函数定义的c(x)，一般的非线性规划软，一般的非线性规划软件也难以输入和求解；件也难以输入和求解；想办法将模型化简，用现成的软件求解想办法将模型化简，用现成的软件求解.汽油含原油汽油含原油A

50、的比例限制的比例限制 5.0211111 xxx6.0221212 xxx2111xx 221232xx 约束约束条件条件甲甲(A 50%)A B 乙乙(A 60%)x11x12x21x221.整数变量整数变量2.特殊约束处理特殊约束处理3.背包问题背包问题4.集合覆盖问题集合覆盖问题5.固定费用问题固定费用问题1.整数变量整数变量表示不可分割的数量表示不可分割的数量表示决策变量表示决策变量(0 1 整数变量整数变量)1表示决策表示决策 j 为为“是是”xj=0表示决策表示决策 j 为为“否否”v表示决策之间的逻辑关系，如决策表示决策之间的逻辑关系，如决策 i 必须以决策必须以决策 j 的结果