运筹学理论与建模课件

运筹学理论与建模

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

3公斤A1

12小时

8小时

4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

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

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天1桶牛奶3公斤A112小时8小时4公斤A2或获利25模型分析与假设

比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和是与时间相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型模型分析与假设比例性可加性连续性xi对目标函数的“贡6A1A2现有资源设备128台时甲4016公斤乙0412公斤利润2030（元）制订生产计划,使每天获利最大

例2

工厂生产两种产品A1,A2,已知生产单位产品情况如表：设生产A1、A2分别x1、x2公斤

maxz=20x1+30x2(1)目标函数约束条件决策变量一、从现实问题到线性规划模型A1A2现有资源设备128台时甲4016公斤乙0412公斤7线性规划模型标准型:maxz=c1x1+c2x2+…+cnxn(LP)线性规划模型标准型矩阵表示：maxz=cX

max(min)z=c1x1+c2x2+…+cnxn线性规划模型一般形式：线性规划模型标准型:maxz=c1x1+c2x2+…81.线性规划的一般形化为标准型的一般步骤(1)Minf=cX转化为maxz=cX(2)加松弛变量yi

(3)加剩余变量yi(4)若存在可正可负变量xi

令1.线性规划的一般形化为标准型的一般步骤(1)Minf9例将下述线性规划问题化为标准型min

z=x1+2x2

3x3无约束标准型maxz=

x12x2+3(x4–x5)+0x6+0x7(1)

x3=

x4x5,x4,x50(2)

x1+x2+x3+x6=7(3)

x1

x2+x3

x7=2例将下述线性规划问题化为标准型minz=x1+210合理下料问题有长度为8米的某型号圆钢，现需要长度为2.5米的毛坯100根，长度为1.3米的毛坯200根，如何选者下料方式，所需总用料最省?解：可能的下料方式：2.51.3130222314406设按第i种下料方式的圆钢xi根，i=1,2,3,4

minz=x1+x2+x3+x4有一组决策变量,约束条件是决策变量的线性等式或不等式,目标函数是决策变量的线性函数,这样的规划问题称为线性规划.记为（LP）合理下料问题有长度为8米的某型号圆钢，现需要长度为211例.某小区一个24小时营业便利店,一

天各时段所需服务员最少人数如下

表.根据实际情况,要求每个服务员必

须连续工作八小时,试建立需服务员

总人数最少的排班方案数学模型.班次123456时间2-66-1010-1414-1818-2222-2人48107124解：设各班次新增服务员数分别为x1,x2,x3,x4,x5,x6,则minz=

x1+x2+x3+x4+x5+x6且xi为整数例.某小区一个24小时营业便利店,一

天各时段所需服务员最少12连续投资问题某部门计划5年内用一百万投资下列项目：A：从第一年到第四年初可投资，次年末回收本利115%B:第三年初可投资，第五年末回收本利125%，投资额≤40万C:第二年初可投资，第五年末回收本利140%，投资额≤30万D：每年初可购买公债，当年末归还，利息6%如何投资，五年后获利最大？解：设第i年初投资项目A,B,C,D分别为xiA

,xiB

,xiC

,

xiD

万元,i=1,2,3,4,5x1A+x1D=100,x2A+x2C+x2D=1.06x1D,x3A+x3B+x3D=1.06x2D+1.15

x1A,x4A+x4D=1.06x3D+1.15

x2A,x5D=1.06x4D+1.15

x3A,x2C≤40,x3B≤30,xiA

,xiB

,xiC

,

xiD≥0，i=1,2,3,4,5.MaxZ=1.15x4A

+1.40x2C+1.25x3B+1.06x5Ds.t.连续投资问题某部门计划5年内用一百万投资下列项目：解13二、线性规划模型的求解（一）图解法（n

3时）（二）单纯形法二、线性规划模型的求解（一）图解法（n3时）（二）单纯形14maxz=c

x(LP)可行解：满足约束条件AX=b,X最优解:可行解中使目标最优的.即X*∈D,且任意X∈D,CX*≥CX可行集：所有可行解的集合的X的值maxz=cx(LP)可行解：满足约束条件AX=b,15制订生产计划,使每天获利最大.

工厂生产两种产品A1,A2,已知生产单位产品情况如下：设生产A1、A2分别x1、x2公斤

maxz=20x1+30x2(1)A1A2现有资源设备128台时甲4016公斤乙0412公斤利润2030（元）制订生产计划,使每天获利工厂生产两种产品A1,A2,已设生产16（一）图解法（n3时）(1)在平面上作出可行集ABCD34z=140z=0由图解法直观得:n=2时,(LP)的可行集是凸多边形,最优解可以在其某个顶点处达到.线性规划基本性质:(LP)的可行集是凸多面体,最优解可以在凸多面体的某个顶点处达到.线性规划求解思路:通过代数的方法描述高维空间凸多面体的顶点,再使用经济的方法来求出达到极值的顶点.x1x20(2)在可行集中找最优解

maxz=20x1+30x2(1)z=60（一）图解法（n3时）(1)在平面上作出可行集ABCD3417引入松弛变量x3,x4,x5,化为标准形:（二）单纯形法系数矩阵为引入松弛变量x3,x4,x5,化为标准形:（二）单纯形18显然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=B1b

B1

NXN,系数矩阵为显然A的秩为3,任取3个线性无关的列向量,如P1,P219令非基变量XN=0,解得基变量XB=B-1b,称(XB,XN)为基本解.解的所有变量的值都非负,则称为基本可行解,此时的基称为可行基.基本可行解对应的目标值为f=cBB-1b.

若可行基进一步满足:cN–cBB-1N≥0,则对一切可行解X,

必有f(x)≥cBB-1b,此时称基可行解X=(B-1b,0)T为最优解.令非基变量XN=0,解得基变量XB=B-1b,称20另一个基本可行解定理：(LP)的可行集的顶点与(LP)的

基本可行解一一对应。单纯形法基本思想：目标重复此更优过程单纯形法基本步骤：不是最优解更优目标重复此过程(LP)的某个基本可行解最优解(LP)的某个基基本可行解另一个基基本可行解最优解另一个基定理：(LP)的可行集的顶点与(LP)的单纯形法21即从可行域的一个顶点(基本可行解)开始,转移到另一个顶点(另一个基本可行解)的迭代过程,转移的条件是使目标函数值得到改善(逐步变优),当目标函数达到最优值时,问题也就得到了最优解.顶点转移的依据？根据线性规划问题的可行域是凸多边形或凸多面体,一个线性规划问题有最优解,就一定可以在可行域的顶点上找到.于是,若某线性规划只有唯一的一个最优解,这个最优解所对应的点一定是可行域的一个顶点;若该线性规划有多个最优解,那么肯定在可行域的顶点中可以找到至少一个最优解.1.单纯形法的基本思想(1)顶点的逐步转移即从可行域的一个顶点(基本可行解)开始,转移到另22转移条件？转移结果？

使目标函数值得到改善得到LP最优解，目标函数达到最优值（单纯形法的由来？）

2．需要解决的问题：

(1)为了使目标函数逐步变优，怎么转移？(2)目标函数何时达到最优——判断标准是什么？

转移条件？232.单纯形法原理（用代数方法求解LP）劳动力原材料利润A112B143C173现有资源39例1劳动力约束原材料约束2.单纯形法原理（用代数方法求解LP）劳动力原材料利润A1124第一步：引入非负的松弛变量x4,x5,将该LP化为标准型第二步：寻求初始可行基，确定基变量对应的基变量是x4，x5；第三步：写出初始基本可行解和相应的目标函数值两个关键的基本表达式：①用非基变量表示基变量的表达式第一步：引入非负的松弛变量x4,x5,将该LP化为标25②用非基变量表示目标函数的表达式请解释结果的经济含义——不生产任何产品,资源全部节余(x4=3，x5=9),三种产品的总利润为0！第四步：分析两个基本表达式，看看目标函数是否可以改善？①分析用非基变量表示目标函数的表达式非基变量前面的系数均为正数，所以任何一个非基变量进基都能使z值增加通常把非基变量前面的系数叫“检验数”；②用非基变量表示目标函数的表达式请解释结果的经济含义——不26②选哪一个非基变量进基？

选x2为进基变量（换入变量）问题：能否选其他的非基变量进基？

任意一个

任意一个正检验数对应的非基变量

最大正检验数对应的非基变量

排在最前面的正检验数对应的非基变量×③确定出基变量：问题讨论x2进基意味着其取值从0变成一个正数（经济意义—生产B产品），能否无限增大？当x2增加时，x4，x5如何变化？②选哪一个非基变量进基？任意一个×③确定出基27现在的非基变量是哪些？具体如何确定换出变量？由用非基变量表示基变量的表达式

当x2增加时,x4,x5会减小,但有限度——必须大于等于0,以保持解的可行性！于是当x2的值从0增加到9/4时,x5首先变为0，此时x4=3/4>0,因此选x5为出基变量(换出变量).现在的非基变量是哪些？由用非基变量表示基变量的表达式当28这种用来确定出基变量的规则称为“最小比值原则”（或θ原则).如果P1≤0，会出现什么问题？最小比值原则会失效！基变换新的基变量——x2,x4；新的非基变量x1,x3,x5；写出用非基变量表示基变量的表达式：由可得新的基本可行解:X(1)=(0，9/4，0，3/4，0)T这种用来确定出基变量的规则称为“最小比值原则”29⑤写出用非基变量表示目标函数的表达式:可得相应的目标函数值为z(1)=27/4检验数仍有正的,返回①进行讨论.第五步：上述过程何时停止？当用非基变量表示目标函数的表达式中,非基变量的系数(检验数)全部非正时,当前的基本可行解就是最优解!

为什么？⑤写出用非基变量表示目标函数的表达式:可得相应的目标函数值30——分析:用非基变量表示目标函数的表达式,如果让负检验数所对应的变量进基，目标函数值将下降！三、表格单纯形法：

1.初始单纯形表的建立

(1)表格结构：

x1x2

x3

x4

x523300bXB11110147013x49x523300z——分析:用非基变量表示目标函数的表达式,如果让负检验数31（2）表格设计依据：

把目标函数表达式改写成方程的形式，和原有的m个约束方程组成一个具有n+m+1个变量、m+1个方程的方程组：（2）表格设计依据：32取出系数写成增广矩阵的形式：

xn+1，…，xn+m所对应的系数列向量构成一个基.用矩阵的初等行变换将目标函数中基变量系数化为零,这时变成0，相应的增广矩阵变成如下形式：取出系数写成增广矩阵的形式：xn+1，…，xn+m所对应的33其中，j=1，2，…，n；

增广矩阵的最后一行就是用非基变量表示目标函数的表达式,j

(j=1,2,…,n）就是非基变量的检验数.（3）检验数的两种计算方法：①利用矩阵的行变换，把目标函数表达式中基变量前面的系数变为0；②使用计算公式——其中，342.例1的表格单纯形法计算过程：x1x2x3x4x5

23300z111103x4147019

x5

23300z3/4

0

-3/4

1

-1/43/4

x41/417/401/49/4x25/40–9/40-3/4z-27/410-14/3-1/31x1012-1/31/32

x200-1-5/3-1/3z-8从最优表可知:该LP的最优解是X*=(1,2,0,0,0)T相应的目标函数最优值是Zmax=8**2.例1的表格单纯形法计算过程：x1x235表格单纯形法求解步骤第一步：将LP化为标准型，并加以整理.引入适当的松驰变量、剩余变量和人工变量,使约束条件化为等式,并且约束方程组的系数阵中有一个单位阵.

（这一步计算机可自动完成）

确定初始可行基，写出初始基本可行解.第二步：最优性检验计算检验数，检查：所有检验数是否≤0？

是—结束,写出最优解和目标函数最优值;还有正检验数—检查相应系数列≤0？是—结束,该LP无“有限最优解”！不属于上述两种情况，转入下一步—基变换.确定是停止迭代还是转入基变换？表格单纯形法求解步骤第一步：将LP化为标准型，并加以整理.第36选择(最大)正检验数对应的系数列为主元列,主元列对应的非基变量为换入变量；

最小比值对应的行为主元行,主元行对应的基变量为换出变量.第三步：基变换确定进基变量和出基变量.第四步

换基迭代（旋转运算、枢运算)利用矩阵的初等行变换把主元列变成单位向量,主元素变为1,进基变量对应的检验数变成0,从而得到一张新的单纯形表,返回第二步.完成一次迭代，得到新的基本可行解和相应的目标函数值.选择(最大)正检验数对应的系数列为主元列,主元列对第三37该迭代过程直至下列情况之一发生时停止检验数行全部变为非正值；（得到最优解）或主元列≤0（最优解无界）停止迭代的标志（停机准则）该迭代过程直至下列情况之一发生时停止停止迭代的标志38自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；运输问题各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少.三、线性规划建模实例自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求39其他费用:450元/千吨

应如何分配水库供水量，公司才能获利最多？

若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费例1自来水输送收入：900元/千吨

支出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）其他费用:450元/千吨应如何分配水库供水量，公司才能获40总供水量：160确定送水方案使利润最大问题分析A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40<总需求量：120+180=300总收入900160=144,000(元)收入：900元/千吨

其他费用:450元/千吨

支出引水管理费其他支出450160=72,000(元)

使引水管理费最小总供水量：160确定送水方案使利润最大问题分析A：50B：641供应限制约束条件需求限制

线性规划模型(LP)目标函数

水库i向j区的日供水量为xij（x34=0）决策变量

模型建立确定3个水库向4个小区的供水量供应限制约束条件需求限制线性规划模型(LP)目标函数水库42目标函数

总供水量(320)>总需求量(300)每个水库最大供水量都提高一倍利润=收入(900)–其它费用(450)

–引水管理费利润(元/千吨)甲乙丙丁A290320230280B310320260300C260250220/供应限制B,C类似处理问题讨论

确定送水方案使利润最大需求约束可以不变目标函数总供水量(320)>总需求量(300)每个水库43如何装运，使本次飞行获利最大？

例2货机装运

重量（吨）空间(米3/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物4123902850三个货舱中实际载重必须与其最大载重成比例

前仓：10；6800中仓：16；8700后仓：8；5300飞机平衡三个货舱最大载重(吨),最大容积(米3)

如何装运，使本次飞行获利最大？例2货机装运

重量（吨44决策变量

xij--第i种货物装入第j个货舱的重量(吨）i=1,2,3,4,

j=1,2,3(分别代表前、中、后仓)模型假设每种货物可以分割到任意小；货机装运每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；模型建立决策变量xij--第i种货物装入第j个货舱的重量(吨）45货舱容积

目标函数(利润)约束条件货机装运模型建立货舱重量

10；680016；87008；5300xij--第i种货物装入第j个货舱的重量货舱容积目标函数(利润)约束条件货机装运模型建立货舱重量46约束条件平衡要求

货物供应

货机装运模型建立10；680016；87008；5300xij--第i种货物装入第j个货舱的重量约束条件平衡要求货物供应货机装运模型建立10；680047第二部分整数规划建模方法一、整数规划简介二、整数规划的分支定界法三、整数规划的建模实例第二部分整数规划建模方法一、整数规划简介二、整数规划的分482.1整数规划简介要求所有xj的解为整数，称为纯整数规划要求部分xj的解为整数，称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的，最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解且为整数2.1整数规划简介要求所有xj的解为整数，称为纯整数规492.2整数规划的分枝定界法3.求解分枝的松弛问题—定界过程设两个分枝的松弛问题分别为问题1和问题2,它们的最优解有如下情况:

2.2.1思路与解题步骤只解松弛问题1.在全部可行性域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最优解2.分枝过程若松弛问题最优解中某个xk=bk不是整数，令[bk]为bk的整数部分:构造两个新的约束条件xk[bk]和xk[bk]+1，分别加于原松弛问题，形成两个新的整数规划.2.2整数规划的分枝定界法3.求解分枝的松弛问题—定界50表2.2.1分枝问题解可能出现的情况情况2,4,5找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的解进行比较，结论如情况4或5序号问题1问题2说明1无可行解无可行解整数规划无可行解2无可行解整数解此整数解即为最优解3无可行解整数解非对问题2继续分枝4整数解整数解较优的一个为最优解5整数解,目标函数值优于2非整数解问题1的解即为最优解（剪枝）6整数解整数解,目标函数值优于1问题1停止分枝，其整数解为界，对问题2继续分枝

表2.2.1分枝问题解可能出现的情况情况2,4,5512.2.2分枝定界法举例例2.1.1解：松弛问题的最优解为x1=2.5,x2=2,OBJ=23由x1=2.5得到两个分枝如下：2.2.2分枝定界法举例例2.1.1解52表2.2.3分枝问题的松弛解问题II的解即原整数问题的最优解可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程.当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解.一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题.表2.2.3分枝问题的松弛解问题II的解即原整数问53例.某厂拟用集装箱托运甲,乙两种货物。已知货物体积(米3/箱)重量(吨/箱)利润(百元/箱)甲9740乙72090托运限制5670问：如何安排利润最大？设甲乙分别托运x1,x2箱模型建立

IP(1)-(4)称为与(IP)相对应的线性规划(LP)求解(LP)得x1=4.81,x2=1.82,

z=356为整数例.某厂拟用集装箱托运甲,乙两种货物。已知货物体积(米3/箱54分枝定界法(branchandboundmethod)(IP)x1*,x2*,z

*(LP) x1=4.81,x2=1.82,z0=356(LP1)x1=4,x2=2.1,z0=349X1≤4X1≥5(LP2)x1=5,x2=1.57,z0=341(z*349定界)(LP3)x1=4,x2=2,z0=340X2≤2X2≥3(LP4)x2=3,x1=1.42,z0=327(z*≥340定界)(LP5)x2=1,x1=5.44,z0=308X2≤1(LP6)无可行解X2≥2x1≤4x1≥5分枝：分枝定界法(branchandboundmethod)55应如何安排原油的采购和加工

？

例2原油采购与加工市场上可买到不超过1500吨的原油A：购买量不超过500吨时的单价为10000元/吨；购买量超过500吨但不超过1000吨时，超过500吨的部分8000元/吨；购买量超过1000吨时，超过1000吨的部分6000元/吨.售价4800元/吨售价5600元/吨库存500吨库存1000吨汽油甲(A50%)原油A原油B汽油乙(A60%)2.3整数规划的建模实例应如何安排原油的采购和加工？例2原油采购与加工56决策变量

目标函数问题分析利润：销售汽油的收入购买原油A的支出难点：原油A的购价与购买量的关系较复杂甲(A50%)AB乙(A60%)购买xx11x12x21x224.8千元/吨5.6千元/吨原油A的购买量,原油A,B生产汽油甲,乙的数量c(x)~购买原油A的支出利润(千元)c(x)如何表述？决策变量目标函数问题分析利润：销售汽油的收入购买原油57原油供应

约束条件x

500吨单价为10千元/吨；500吨x1000吨，超过500吨的8千元/吨；1000吨x1500吨，超过1000吨的6千元/吨。目标函数购买xABx11x12x21x22库存500吨库存1000吨原油供应约束条件x500吨单价为10千元/吨；目标函58目标函数中c(x)不是线性函数，是非线性规划；对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解；想办法将模型化简，用现成的软件求解.汽油含原油A的比例限制约束条件甲(A50%)AB乙(A60%)x11x12x21x22目标函数中c(x)不是线性函数，是非线性规划；汽油含原油A59整数规划应用举例1.整数变量2.特殊约束处理3.背包问题4.集合覆盖问题5.固定费用问题整数规划应用举例1.整数变量601.整数变量表示不可分割的数量表示决策变量(0–1整数变量) 1 表示决策j为“是”

xj=

0 表示决策j为“否”1.整数变量表示不可分割的数量61表示决策之间的逻辑关系，如决策i必须以决策

j的结果为前提：xi

xj

或

xi=xj

描述互斥的选择，从多种方案中选一个方案：

j

xj=1表示决策之间的逻辑关系，如决策i必须以决策62例某公司有600万元资金用于投资，有5个项目列入投资计划，各项目投资额和期望收益见下表：项目 投资额(万元) 投资收益(万元) 1 210 150 2 300 210 3 100 60 4 130 80 5 260 180 由于技术原因，投资受到以下约束:在项目1,2和3中必须且只能有一项被选中;项目3和4最多只能被选中一项;项目5被选中的前提是项目1被选中;问如何选择最好的投资方案,使投资收益最大.例某公司有600万元资金用于投资，有5个项目列入投由63解：令xi为0-1决策变量,模型为:max

z=150x1+210x2+60x3+80x4+160x5

s.t.210x1+300x2+100x3+130x4+260x5600

x1+x2+x3=1

x3+x41

x5

x1 xi=1或0,i=1,...,5解：令xi为0-1决策变量,模型为:64(1)矛盾约束：同时出现的矛盾约束 f(x)–50或f(x)0 引入一个0—1变量y来处理：

f(x)+5M(1

y)和f(x)My

y=1f(x)50和f(x)M

y=0f(x)5

M和f(x)02.特殊约束处理(1)矛盾约束：同时出现的矛盾约束2.特殊约束处理65(2)绝对值约束:

f(x)

a(a

0) 约束可写为：f(x)

a或f(x)

–

a

引入01变量y后，约束可改写为：

f(x)+a

M(1y)和f(x)+a

My

y=1f(x)+a

0和f(x)+a

M

y=0f(x)+aM和f(x)+a0(2)绝对值约束:66(3)多中选一的约束在下列n个约束中，只能有一个约束有效: fi(x)0 i=1,2,…,n

引入n个01变量yi,i=1,2,…,n,约束可写为： fi(x)M(1yi)i=1,2,…,n

y1+y2+…+yn

=1 (3)多中选一的约束673.背包问题例一登山队员做登山准备，需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相机和通讯设备。每种物品的重要性系数和重量见下表：要求背包重量不能超过25公斤，求重要性系数最大的携带物品方案.3.背包问题例一登山队员做登山准备，需要携带的物品有：食68令xi为是否携带物品i的决策变量：

maxz=20x1+15x2+18x3+14x4+8x5+4x6+10x7

s.t.5x1+5x2+2x3+6x4+12x5+2x6+

4x7

25 xi=1或0，i=1,2,...,7背包问题的一般形式为：

max

z=c1x1+c2x2+…+cnxn

s.t.a1x1+a2x2+…+anxn

b

x1,x2,…

,xn

0令xi为是否携带物品i的决策变量：69对一维背包问题，上例使用的启发式算法是很有效的：只要比较ci/ai的比值，依次令有最大的比值的决策变量为1，直到资源b用尽为止。该算法当n较大，且ai<<b时更为准确.对一维背包问题，上例使用的启发式算法是很704.集合覆盖问题有集合S={1,2,...,m}被一系列S的子集iS，i=1,2,...,n覆盖，并要求使用的子集最少.例:

有集合S={1,2,3,4,5},子集1={1,2},2={1,3,5},

3={2,4,5},4={1},5={4,5},求最小的覆盖子集。解:一个可能的覆盖为1,2,3,另一个为2,3;该问题可以用一个整数规划来求解： 令xi为是否使用集合i的决策变量4.集合覆盖问题71Minz=x1+x2+x3+x4+x5s.t.

x1+x2+x41

x1+x3

1

x21

x3+x51

x2+x3+x51 xi=0或1,i=1,...,5Minz=x1+x2+x3+x4+x572例

某城市有6个区,规划建消防站,任何区发生火警时消防车要在15分钟内赶到,各区间消防车行驶的时间见下表,求设置消防站最少的方案.例 某城市有6个区,规划建消防站,任何区发生73解：设xj

为在j地区设置消防站的决策(j=1,2,…,6)整数规划问题为：

min

z=

x1+x2+x3+x4+x5+x6

s.t.

x1+x21

x1+x2+x61

x3+x4

1

x3+x4+x5

1

x4+x5+x61

x2+x5+x61 xi=0或1i=1,...,6最优解x2=x4=1,在地区2,4设消防站.解：设xj为在j地区设置消防站的决策(j=174人们经常会遇到固定费用问题,例如要建一条生产线,由生产能力确定的投资规模是固定的,要建设,就要投入一笔固定数量资金;再如,如果生产要租用设备,则不管如何使用该设备,你都要支付一笔固定的租金,租金一般不随生产量的变化而变化,求解这类不连续变化的固定费用问题也要借助整数规划.5.固定费用问题人们经常会遇到固定费用问题,例如要建一条生产5.固定费75例:服装厂可生产西服、衬衫和羽绒服.生产不同服装要使用不同设备，该厂可从租赁公司租用这些设备.假定市场需求不成问题，服装厂每月可用人工工时为2000小时，该厂如何安排生产可使每月利润最大.设备租金和其它经济参数见下表：例:服装厂可生产西服、衬衫和羽绒服.生产不76解：令yi为是否租赁i类设备的决策变量;xi为各类服装的生产量,具体模型为：Maxz=120x1+10x2+100x35000y12000y21000y3

s.t.5x1+x2+4x32000 3x1－300y10 0.5x2－300y2

0 2x3－300y30

xi0yi=0或1i=1,2,3解：令yi为是否租赁i类设备的决策变量;xi为各类77第三讲指派问题一、指派问题定义二、指派问题的求解三、指派问题的建模实例第三讲指派问题一、指派问题定义二、指派问题的求解三、指派78丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?例1混合泳接力队的选拔

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”579目标函数若选择队员i参加泳姿j的比赛，记xij=1,否则记xij=0

0-1规划模型

cij(秒)~队员i第j种泳姿的百米成绩约束条件每人最多入选泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有1人目标函数若选择队员i参加泳姿j的比赛，记xij=1,否则80若干项任务分给一些候选人来完成，每人的专长不同，完成每项任务取得的效益或需要的资源就不同,如何分派任务使获得的总效益最大，或付出的总资源最少.指派(Assignment)问题：n个人要完成n项任务，每项任务有且只有一人承担，每人只能承担一项，费用不同，怎样分派使总费用最小.若干项任务分给一些候选人来完成，每人的专长不指派(Assig81模型建立

Cij表示指派第i人做第j项任务所需成本.指派(Assignment)问题:n个人要完成n项任务,每项任务有且只有一人承担,每人只能承担一项,费用不同,怎样分派使总费用最大.模型建立Cij表示指派第i人做第j项任务所需成本.指派(A82一份中文说明书需要翻译成英,日,德,俄4种文字，甲乙丙丁4人翻译费用矩阵如下:一份中文说明书需要翻译成英,日,德,俄4种文字，甲乙丙丁483可行解矩阵{xij}nn每行每列均有且只有一个1，其余全为零最优解x14

=

x22

=

x33

=

x41

=1，其余xij=0,最优值

z=4+4+16+3=27可行解矩阵{xij}nn每行每列均有且只有一个1，其余全为84匈牙利算法定理1如果从费用矩阵{cij}nn中每行元素分别减去一个常数ui，从每列元素分别减去一个常数vj,所得新的费用矩阵{bij}nn的任务分配问题的最优解等价于原问题的最优解.匈牙利算法的基本思路：根据定理1变换费用矩阵,使矩阵中有足够多的零.若矩阵中存在n个不同行不同列的零,就找到了最优解否则，就尚未找到最优解,设法进一步变换矩阵,增加新的零.匈牙利算法定理1如果从费用矩阵{cij}nn中每行元85例1有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表4.6.1，问如何分配任务使完成四项任务的总工时耗费最少？例1有四个熟练工人，他们都是多面手，有四项任务要他86匈牙利算法的步骤：第一步：变换费用矩阵，使每行每列至少有一个零行变换：找出每行最小元素，从该行各元素中减去之列变换：找出每列最小元素，从该列各元素中减去之第二步(试分配)：检查矩阵中是否存在n个不同行不同列的零检查规则2、逐列检查，找零最少列的某个零(所在行零较少的)标记()，将()标记元素同行同列上其它的零打上*标记。重复1,2，直到所有行列检查完；1、逐行检查，找零最少行的某个零(所在列零较少的)标记()，将()标记元素同行同列上其它的零打上*标记；匈牙利算法的步骤：第一步：变换费用矩阵，使每行每列至少有一个873、重复1、2后，可能出现两种情况：每行都有一个(0)，显然已找到最优解，令对应(0)位置的xij=1；b.所有零都已标记，但标有()的零的个数少于m；

开始划线过程：对没有标记()的行打

对打行上所有其它零元素对应的列打再对打

列上有()标记的零元素对应的行打重复上述过程，直至无法继续对没有打的行划横线，对所有打的列划竖线

3、重复1、2后，可能出现两种情况：b.所有零都已标记，但88b.所有零都已标记，但标有()的零的个数少于m；

开始划线过程：对没有标记()的行打

对打行上所有其它零元素对应的列打再对打

列上有()标记的零元素对应的行打重复上述过程，直至无法继续对没有打的行划横线，对所有打的列划竖线

b.所有零都已标记，但标有()的零的个数少于m；89第三步：进一步变换；在未划线的元素中找最小者，设为对未被直线覆盖的各元素减去对双线覆盖的元素加上对单线覆盖的元素保持不变以上步骤实际上仍是利用定理1第四步：抹除所有标记，回到第二步，重新试分配；第三步：进一步变换；第四步：抹除所有标记，回到第二步，重新试90关于匈牙利算法的适用条件要求所有cij0若某些cij<0，则利用定理1进行变换，使所有bij0(令bij=

cij+M)目标函数为min型1.对于max∑∑cijxij型目标函数，等效于求min-∑∑cijxij=

min∑∑-cijxij型问题；再利用定理1进行变换，使所有bij=

cij+M0，则可采用匈牙利算法2.对于人数n大于工作数mC=[cij]n×m可令cnj=0,j=m+1,m+2,…,n.即增加虚拟工作Jm+1,

Jm+2,

…,

Jn

,其费用cnj=0关于匈牙利算法的适用条件要求所有cij01.对于max∑913.对于人数n小于工作数ma.若要求每人做一项工作，则同情况2,C=[cij]n×m可令cim=0,i=n+1,n+2,…,m.即增加虚拟人Jm+1,

Jm+2,

…,

Jn,其费用cnj=0.b.若要求所有工作有人做，任意两人做的工作至多差一项？3.对于人数n小于工作数ma.若要求每人做一项工作，则同情况92丁的蛙泳成绩退步到1152；戊的自由泳成绩进步到575,组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?例1混合泳接力队的选拔

甲乙丙丁戊蝶泳10685721181101074仰泳115610610781142111蛙泳1271064124610961238自由泳5865359457210245名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。丁的蛙泳成绩退步到1152；戊的自由泳成绩进步到5793目标函数若选择队员i参加泳姿j的比赛，记xij=1,否则记xij=0

0-1规划模型

cij(秒)~队员i第j种泳姿的百米成绩约束条件每人最多入选泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有1人目标函数若选择队员i参加泳姿j的比赛，记xij=1,否则94ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.466.857.2787067.475.66667.874.2718766.484.669.683.858.65359.457.262.40000066.857.2787067.475.66667.874.2718766.484.669.683.858.65359.457.262.4j=500000ciji=1i=2i=3i=4i=5j=166.857.2795最优解：x14=x21=x32=x43=1,其它变量为0;成绩为253.2(秒)=4132

甲乙丙丁戊蝶泳10685721181101074仰泳115610610781142111蛙泳1271064124610961238自由泳586535945721024甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.最优解：x14=x21=x32=x43=1,96为了选修课程门数最少，应学习哪些课程？

例2选课策略要求至少选两门数学课、三门运筹学课和两门计算机课课号课名学分所属类别先修课要求1微积分5数学

2线性代数4数学

3最优化方法4数学；运筹学微积分；线性代数4数据结构3数学；计算机计算机编程5应用统计4数学；运筹学微积分；线性代数6计算机模拟3计算机；运筹学计算机编程7计算机编程2计算机

8预测理论2运筹学应用统计9数学实验3运筹学；计算机微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程？

为了选修课程门数最少，应学习哪些课程？例2选课策970-1规划模型

决策变量

目标函数

xi=1~选修课号i的课程（xi=0~不选）

选修课程总数最少约束条件最少2门数学课，3门运筹学课，2门计算机课.课号课名所属类别1微积分数学2线性代数数学3最优化方法数学；运筹学4数据结构数学；计算机5应用统计数学；运筹学6计算机模拟计算机；运筹学7计算机编程计算机8预测理论运筹学9数学实验运筹学；计算机0-1规划模型决策变量目标函数xi=1~选修课号i98先修课程要求最优解：

x1=x2=x3=x6=x7=x9=1,其它为0；6门课程，总学分210-1规划模型

约束条件x3=1必有x1=x2=1模型求解（LINDO）课号课名先修课要求1微积分

2线性代数

3最优化方法微积分；线性代数4数据结构计算机编程5应用统计微积分；线性代数6计算机模拟计算机编程7计算机编程

8预测理论应用统计9数学实验微积分；线性代数先修课程要求最优解：x1=x2=x3=x6=99学分最多多目标优化的处理方法：化成单目标优化。两目标(多目标)规划

讨论：选修课程最少，学分尽量多，应学习哪些课程？课程最少以学分最多为目标，不管课程多少。以课程最少为目标，不管学分多少。最优解如上，6门课程，总学分21。最优解显然是选修所有9门课程。学分最多多目标优化的处理方法：化成单目标优化。两目标(多目标100第四部分动态规划建模4.1动态规划数学模型4.2资源分配问题4.3生产与存储问题4.4背包问题第四部分动态规划建模4.1动态规划数学模型1011.动态规划是解决多阶段决策过程最优化的一种有效的数学方法,它是美国学者R.bellman在1951年提出的,1957年他的专著《动态规划》的问世标志着运筹学的一个重要分支——动态规划的诞生。动态规划(DynamicProgramming)简介

3.动态规划是考察解决问题的一种途径，其基本思想是：把一个较复杂的问题按照阶段划分,分解为若干个较小的局部问题,然后按照局部问题的递推关系,依次作出一系列决策,直至整个问题达到总体最优的目标.2.所谓多阶段决策问题是指这样一类问题，该问题的决策过

程是一种在多个相互联系的阶段分别作出决策以形成序列

决策的过程，而这些决策均是根据总体最优化这一共同的

目标而采取的.1.动态规划是解决多阶段决策过程最优化的一种有效的数学方动102v2v3v4v7v5v9v6v8v10285121310710131128658854【例4.1】最短路径问题图4－1表示从起点v1到终点v10之间各点的距离.求v1到v10的最短路径.图4－1v1第1阶段第2阶段第3阶段第4阶段阶段：第5阶段状态：v1v2,v3,v4v5,

v6v7,

v8,v9

v10v2v3v4v7v5v9v6v8v1028512131071103v2v3v4v7v5v9v6v8v1028512131071013112865885405847图4－1v1第1阶段第2阶段第3阶段第4阶段阶段：第5阶段1217142019Min{2+5,8+8,6+4}=7v2v3v4v7v5v9v6v8v1028512131071104动态规划问题的基本特征：

1.问题具有多阶段决策的特征:阶段可按时间划分，也可按空间划分.2.每一阶段都有相应的“状态”与之对应.3.每一阶段的某个状态都面临若干个决策，选择不同的决策将会导致下一阶段不同的状态，同时，不同的决策将会导致这一阶段不同的目标函数值.4.每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构.注：动态规划解决问题的关键将问题归结为一个递推过程,建立一个递推的指标函数求最优解.这种递推归结的过程,称为“不变嵌入”.动态规划问题的基本特征：1.问题具有多1055.状态具有无后效性:当某阶段状态确定后，此阶段以后过程的发展不受此阶段以前各阶段状态的影响。如下图所示：9AB1B2B3D1C1C4C3D2E7812121441213651064C2905.状态具有无后效性:当某阶段状态106动态规划基本原理:

是将一个问题的最优解转化为求子问题的最优解,研究的对象是决策过程的最优化,其变量是流动的时间或变动的状态,最后到达整个系统最优.注：基本原理一方面说明原问题的最优解中包含了子问题的最优解，另一方面给出了一种求解问题的思路，将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，每一个子问题只解一次，并将结果保存起来以后直接引用，避免每次碰到时都要重复计算，以便各个击破，分而治之，即分治法，是一种解决最优化问题的算法策略.动态规划求解可分为三个步骤：分解、求解与合并.动态规划基本原理:是将一个问题的最优解转化为求子问题的最优107(1)阶段：表示决策顺序的时段序列，阶段可按时间或空间划分,阶段数用变量k表示.4.1.2基本概念(3)决策

xk：从某一状态向下一状态转移时所做的选择,决策变量记为xk，xk是所在状态sk的函数.(2)状态sk：描述决策过程当前特征并且具有无后效性的量.状态可以是数量,也可以是字符,数量状态可以是连续的,也可以是离散的.每一状态可以取不同值,状态变量记为sk.各阶段所有状态组成的集合称为状态集.在状态sk下，允许采取决策的全体称为允许决策集合,记为Dk(sk).各阶段所有决策组成的集合称为决策集.(1)阶段：表示决策顺序的时段序列，阶段可按时间或4.1.108(4)策略：从第1阶段开始到最后阶段全过程的决策构成的序列称为策略，第k阶段到最后阶段的决策序列称为子策略.(5)状态转移方程:某一状态以及该状态下的决策，与下一状态之间的函数关系，记为:sk+1=T(sk,xk)(6)指标函数或收益函数：是衡量对决策过程进行控制的效果的数量指标，具体可以是收益、成本、距离等指标.分为k阶段指标函数、k子过程指标函数及最优指标函数.注：某一阶段的状态与下一阶段的状态有某