数学建模暑期集训2016-2003

2016年数学建模竞赛暑期集训讲座之规划模型主讲教师：董庆来2016年8月一、概况二、历届竞赛赛题基本解法三、运筹学（最优化）概述四、线性规划五、目标规划六、整数规划七、非线性规划八、层次分析法九、赛题选讲什么是数学建模？什么是模型？模型与原型一、概况指人们在现实世界里关心、研究或者从事生产、管理的实际对象是为了一定目的，对客观事物的一部分进行简缩、抽象、提炼出来的原型的替代物原型模型模型物质模型（形象模型）理想模型（抽象模型）直观模型物理模型玩具、照片、飞机、火箭模型…水箱中的舰艇、风洞中的飞机思维模型符号模型数学模型地图、电路图、分子结构汽车司机对方向盘的操纵数学模型：由数字、字母或其它数学符号组成的，描述现实对象数量规律的数学公式、图形或算法自然科学：爱因斯坦的质能公式E=mc2社会科学：马克思的社会再生产公式简单再生产Ⅰ（v+m）=Ⅱc扩大再生产Ⅰ（v+m）》Ⅱc☆典型模型你碰到过的数学模型——“航行问题”

用x

表示船速，y表示水速，列出方程：答：船速每小时20千米/小时.甲乙两地相距750千米，船从甲到乙顺水航行需30小时，从乙到甲逆水航行需50小时，问船的速度是多少?x=20y=5求解航行问题建立数学模型的基本步骤作出简化假设（船速、水速为常数）；用符号表示有关量（x,y表示船速和水速）；用物理定律（匀速运动的距离等于速度乘以时间）列出数学式子（二元一次方程）；求解得到数学解答（x=20,y=5）；回答原问题（船速每小时20千米/小时）。模型准备模型应用分析检验模型求解模型建立模型假设反馈☆建模的一般步骤二、历届竞赛赛题基本解法赛题解法93A非线性交调的频率设计拟合、规划93B足球队排名图论、层次分析、整数规划94A逢山开路图论、插值、动态规划94B锁具装箱问题图论、组合数学95A飞行管理问题非线性规划、线性规划95B天车与冶炼炉的作业调度动态规划、排队论、图论96A最优捕鱼策略微分方程、优化96B节水洗衣机非线性规划历届竞赛赛题基本解法97A零件的参数设计非线性规划97B截断切割的最优排列随机模拟、图论98A一类投资组合问题多目标优化、非线性规划98B灾情巡视的最佳路线图论、组合优化99A自动化车床管理随机优化、计算机模拟99B钻井布局0-1规划、图论00ADNA序列分类模式识别、Fisher判别、人工神经网络00B钢管订购和运输组合优化、运输问题历届竞赛赛题基本解法01A血管三维重建曲线拟合、曲面重建01B工交车调度问题多目标规划02A车灯线光源的优化非线性规划02B彩票问题单目标决策03ASARS的传播微分方程、差分方程03B露天矿生产的车辆安排整数规划、运输问题04A奥运会临时超市网点设计统计分析、数据处理、优化04B电力市场的输电阻塞管理数据拟合、优化历届竞赛赛题基本解法05A长江水质的评价和预测

聚类、模糊评判主成分分析、多目标决策

05BDVD在线租赁

多目标规划06A出版社的资源配置

线性规划、多目标规划

06B艾滋病疗法评价及疗效预测

回归线性规划

07A中国人口增长预测问题

微分方程、差分方程07B乘公交，看奥运问题

图论、0-1规划、动态规划

08A数码相机定位问题几何、优化08B高等教育学费标准探讨多元回归、多目标优化历届竞赛赛题基本解法09A制动器试验台的控制方法分析微元分析法

09B眼科病床的合理安排层次分析法，整数规划，动态规划10A储油罐的变位识别与罐容表标定非线性规划多元拟合10B上海世博会影响力的定量评估数据收集和处理，层次分析法，时间序列分析

11A城市表层土壤重金属污染分析概率优化模型11B交巡警服务平台的设置与调度多目标规划，动态规划，图论，0-1规划12A葡萄酒的评价数据收集和处理、模糊评判主成分分析数据处理、优化模型12B太阳能小屋的设计运筹学是一种给出问题不坏的答案的艺术，否则的话问题的结果会更坏。☆运筹学的定义三、运筹学（最优化）概述1、在数学上，最优化是一种求极值的方法。2、最优化已经广泛的渗透到工程、经济、电子技术等领域。在实际生活当中，人们做任何事情，不管是分析问题，还是进行决策，都要用一种标准衡量一下是否达到了最优。（比如基金人投资）在各种科学问题、工程问题、生产管理、社会经济问题中，人们总是希望在有限的资源条件下，用尽可能小的代价，获得最大的收获。（比如保险）

线性规划数学规划非线性规划整数规划动态规划运筹学多目标规划组合优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析☆主要内容数学规划模型的数学描述下的最大值或最小值将一个优化问题用数学式子来描述，即求函数在约束条件和数学规划问题的一般形式约束条件决策变量目标函数“受约束于”之意优化模型的简单分类

线性规划(LP)

目标和约束均为线性函数

非线性规划(NLP)

目标或约束中存在非线性函数

二次规划(QP)

目标为二次函数、约束为线性

整数规划(IP)

决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)

纯整数规划(PIP),混合整数规划(MIP)

一般整数规划，0-1（整数）规划连续优化离散优化数学规划满足所有约束条件的向量x称为可行解或者可行点三者皆满足的向量x是最优解最优值：最优解的目标函数值可行区域：所有的可行点组成的集合称为(LP)问题的可行区域.记为D四、线性规划线性规划的解法1、图解法（只有两个变量）2、单纯形法3、LINDO(LINGO)4、MATLAB5、EXCEL6、椭球算法例

加工奶制品的生产计划一奶制品加工厂用牛奶生产A1，A2两种奶制品，1桶牛奶可以在甲类设备上用12小时加工成3公斤A1，或者在乙类设备上用8小时加工成4公斤A2.根据市场需求，生产的A1，A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元.现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且甲类设备每天至多能加工100公斤A1，乙类设备的加工能力没有限制.试为该厂制定一个生产计划，使每天获利最大，并进一步讨论一下3个附加问题

35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?

A1的获利增加到30元/公斤，应否改变生产计划？☆奶制品的生产与销售例

加工奶制品的生产计划1桶牛奶3公斤A1

12小时8小时4公斤A2

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

制订生产计划，使每天获利最大

35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?

A1的获利增加到30元/公斤，应否改变生产计划？每天：1桶牛奶3公斤A1

12小时8小时4公斤A2

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

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应劳动时间加工能力决策变量目标函数每天获利约束条件非负约束线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天模型求解

软件实现

LINDO6.1max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产A1,30桶生产A2，利润3360元。结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2最优解下“资源”增加1单位时“效益”的增量原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润影子价格

35元可买到1桶牛奶，要买吗？35<48,应该买！聘用临时工人付出的工资最多每小时几元？2元！RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系数范围(64,96)

x2系数范围(48,72)

A1获利增加到30元/公斤，应否改变生产计划x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)结果解释

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加53

35元可买到1桶牛奶，每天最多买多少？最多买10桶!(目标函数不变)例自来水输送问题某市有甲、乙、丙、丁四个居民区，自来水由A、B、C三个水库供应。四个区每天必须的基本生活用水分别为30、70、10、10千吨，但三个水库每天最多只能分别供应50、60、50千吨自来水。由于地理位置的差别，自来水公司从各水库向各区送水所付出的引水管理费不同（如表，其中C水库与丁区间无输水管道），其它管理费均为450元/千吨。元/千吨甲乙丙丁A160130220170B140130190150C190200230/各区用户每千吨收费900元。此外，各区用户都向公司申请了额外用水量，分别为每天50、70、20、40千吨。问公司应如何分配供水量，才能获利最多？为了增加供水量，自来水公司正在考虑进行水库改造，使三个水库每天的最大供水是提高一倍，问那时供水方案应如何改变？公司利润加多少？其他费用:450元/千吨

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

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

支出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；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(元)使引水管理费最小供应限制约束条件需求限制

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

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

模型建立确定3个水库向4个小区的供水量模型求解

OBJECTIVEFUNCTIONVALUE1)24400.00VARIABLEVALUEREDUCEDCOSTX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000X2250.0000000.000000X230.00000020.000000X2410.0000000.000000

X3140.0000000.000000X320.00000010.000000X3310.0000000.000000利润=总收入-其它费用-引水管理费=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理费24400(元)目标函数

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

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

确定送水方案使利润最大需求约束可以不变求解

OBJECTIVEFUNCTIONVALUE1)88700.00VARIABLEVALUEREDUCEDCOSTX110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000

X2130.0000000.000000

X2240.0000000.000000X230.00000010.000000

X2450.0000000.000000

X3150.0000000.000000X320.00000020.000000

X3330.0000000.000000这类问题一般称为“运输问题”(TransportationProblem)总利润88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030☆一般运输问题的提法：假设A1,A2,…,Am

表示某物资的m个产地；B1,B2,…,Bn

表示某物资的n个销地；si表示产地Ai

的产量；dj

表示销地Bj

的销量；cij

表示把物资从产地Ai

运往销地Bj

的单位运价。如果

s1+s2+…+sm

=d1+d2+…+dn

则称该运输问题为产销平衡问题；否则，称产销不平衡。运输问题数据表设xij

为从产地Ai

运往销地Bj

的运输量，根据这个运输问题的要求，可以建立运输变量表。销地产地B1B2…Bn产量A1A2┇

Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmns1s2┇

sm销量d1d2…dn

运输问题变量表销地产地B1B2…Bn产量A1A2

┇Amx11x12…x1nx21x22…x2n┇┇┇┇xm1xm2…xmns1s2

┇sm销量d1d2…dn

m

nminf=cijxij

（1）

i=1j=1

n

s.t.xij

si

i=1,2,…,m

（2）

j=1

mxij

(=,)dj

j=1,2,…,n

（3）

i=1xij0(i=1,2,…,m;j=1,2,…,n)（4）于是得到下列一般运输问题的模型：

在模型（1）—（4）中，式（2）为m个产地的产量约束；式（3）为n

个销地的销量约束。

mnminf=cijxiji=1j=1

n

s.t.xij=si

i=1,2,…,m

(5)

j=1

m

xij

=dj

j=1,2,…,n(6)

i=1xij≥0(i=1,2,…,m;j=1,2,…,n)对于产销平衡问题，可得到下列运输问题的模型：运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路。由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。LINGO

某企业生产甲、乙两种产品，需要用到A,B,C三种设备，关于产品的盈利与使用设备的工时及限制如下表所示。例

生产安排问题问该企业应如何安排生产，使得在计划期内总利润最大？五、目标规划☆线性规划建模该例是一个线性规划问题，直接考虑它的线性规划模型设甲、乙产品的产量分别为x1,x2,建立线性规划模型：用Lindo或Lingo软件求解,得到最优解☆目标规划建模在上例中，企业的经营目标不仅要考虑利润，还需要考虑多个方面，因此增加下列因素(目标)：力求使利润指标不低于1500元考虑到市场需求,甲、乙两种产品的产量比应尽量保持1:2设备A为贵重设备，严格禁止超时使用设备C可以适当加班，但要控制；设备B既要求充分利用，又尽可能不加班，在重要性上，设备B是设备C的3倍从上述问题可以看出，仅用线性规划方法是不够的，需要借助于目标规划的方法进行建模求解☆线性规划建模局限性线性规划要求所有求解的问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足；线性规划只能处理单目标的优化问题，而对一些次目标只能转化为约束处理。但在实际问题中，目标和约束好似可以相互转化的，处理时不一定要严格区分；线性规划在处理问题时，将各个约束(也可看作目标)的地位看成同等重要，而在实际问题中，各个目标的重要性即有层次上的差别，也有在同一层次上不同权重的差别线性规划寻求最优解，而许多实际问题只需要找到满意解就可以了。☆目标规划的数学模型为了克服线性规划的局限性,目标规划采用如下手段：1.

设置偏差变量;2.

统一处理目标与约束;3.

目标的优先级与权系数。目标规划的基本概念1.

设置偏差变量用偏差变量(Deviationalvariables)来表示实际值与目标值之间的差异，令

----超出目标的差值，称为正偏差变量

----未达到目标的差值，称为负偏差变量其中与至少有一个为0约定如下：当实际值超过目标值时，有当实际值未达到目标值时，有当实际值与目标值一致时，有2.

统一处理目标与约束在目标规划中，约束可分两类，一类是对资源有严格限制的，称为刚性约束(HardConstraint)；例如在用目标规划求解例中设备A禁止超时使用，则有刚性约束另一类是可以不严格限制的，连同原线性规划的目标,构成柔性约束(SoftConstraint).例如在求解例中，我们希望利润不低于1500元，则目标可表示为求解例中甲、乙两种产品的产量尽量保持1:2的比例，则目标可表示为设备C可以适当加班，但要控制，则目标可表示为设备B既要求充分利用，又尽可能不加班，则目标可表示为从上面的分析可以看到：如果希望不等式保持大于等于，则极小化负偏差；如果希望不等式保持小于等于，则极小化正偏差；如果希望保持等式，则同时极小化正、负偏差．

3.目标的优先级与权系数在目标规划模型中，目标的优先分为两个层次，第一个层次是目标分成不同的优先级，在计算目标规划时，必须先优化高优先级的目标，然后再优化低优先级的目标。通常以P1,P2,...表示不同的因子,并规定Pk>>Pk+1，第二个层次是目标处于同一优先级，但两个目标的权重不一样，因此两目标同时优化，用权系数的大小来表示目标重要性的差别。解在例中设备A是刚性约束，其于是柔性约束．首先，最重要的指标是企业的利润，将它的优先级列为第一级；其次，甲、乙两种产品的产量保持1:2的比例，列为第二级；再次，设备

B和C的工作时间要有所控制，列为第三级，设备B的重要性是设备C的三倍，因此它们的权重不一样。由此可以得到相应的目标规划模型。目标规划模型的建立☆用目标规划方法求解例题目标规划的一般模型目标规划模型的一般数学表达式为：求解目标规划的序贯式算法其算法是根据优先级的先后次序，将目标规划问题分解成一系列的单目标规划问题，然后再依次求解。算法

对于k=1,2,…,q,求解单目标问题解因为每个单目标问题都是一个线性规划问题，因此可以采用LINDO软件进行求解。按照算法1和目标规划模型编写单个的线性规划求解程序。求第一级目标企业利润最大，列出LINDO程序。程序名：exam0804a.ltx

☆用算法求解例题

MINDMINUS1SUBJECTTO2X1+2X2<=12200X1+300X2-DPLUS1+DMINUS1=15002X1-X2-DPLUS2+DMINUS2=04X1-DPLUS3+DMINUS3=165X2-DPLUS4+DMINUS4=15END求解结果DMINUS1=0目标

计算结果如下：

LPOPTIMUMFOUNDATSTEP5OBJECTIVEFUNCTIONVALUE1)0.0000000E+00VARIABLEVALUEREDUCEDCOSTDMINUS10.0000001.000000X13.0000000.000000X23.0000000.000000DPLUS10.0000000.000000DPLUS23.0000000.000000DMINUS20.0000000.000000DPLUS30.0000000.000000DMINUS34.0000000.000000DPLUS40.0000000.000000DMINUS40.0000000.000000

ROWSLACKORSURPLUSDUALPRICES2)0.0000000.0000003)0.0000000.0000004)0.0000000.0000005)0.0000000.0000006)0.0000000.000000NO.ITERATIONS=5

目标函数的最优值为0，即第一级偏差为0。

解因求出的目标函数的最优值为０，即第一级偏差为０.再求第二级目标，列出其LINDO程序。程序名：exam0804b.ltx☆用算法求解例题MINDPLUS2+DMINUS2SUBJECTTO

2X1+2X2

<=12200X1+300X2-DPLUS1+DMINUS1=1500

2X1-

X2-DPLUS2+DMINUS2=0

4X1

-DPLUS3+DMINUS3=16

5X2-DPLUS4+DMINUS4=15

DMINUS1=0END求解结果DPLUS2+DMINUS2=0修改的目标增加的约束求第二级目标(偏差)，列出LINDO程序如下：

MINDPLUS2+DMINUS2SUBJECTTO2X1+2X2<=12200X1+300X2-DPLUS1+DMINUS1=15002X1-X2-DPLUS2+DMINUS2=04X1-DPLUS3+DMINUS3=165X2-DPLUS4+DMINUS4=15DMINUS1=0END计算结果如下：

LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)0.0000000E+00VARIABLEVALUEREDUCEDCOSTDPLUS20.0000001.000000DMINUS20.0000001.000000X11.8750000.000000X23.7500000.000000DPLUS10.0000000.000000DMINUS10.0000000.000000DPLUS30.0000000.000000DMINUS38.5000000.000000DPLUS43.7500000.000000DMINUS40.0000000.000000

ROWSLACKORSURPLUSDUALPRICES2)0.7500000.0000003)0.0000000.0000004)0.0000000.0000005)0.0000000.0000006)0.0000000.0000007)0.0000000.000000NO.ITERATIONS=2

目标函数最优值还是0，即二级偏差仍为0。解因求出的目标函数的最优值仍为０，即第二级偏差仍为０.继续求第三级目标，列出其LINDO程序。程序名：exam0804c.ltx例

用算法求解例题MIN3DPLUS3+3DMINUS3+DPLUS4SUBJECTTO

2X1+

2X2

<=12200X1+300X2-DPLUS1+DMINUS1=1500

2X1-

X2-DPLUS2+DMINUS2=0

4X1

-DPLUS3+DMINUS3=16

5X2-DPLUS4+DMINUS4=15

DMINUS1=0DPLUS2+DMINUS2=0END求解结果29修改的目标增加的约束求出的目标函数的最优值为29,即第三级偏差为29,分析结果,x1为2,x2为4,DPLUS1为100,因此目标规划的最优解为x

*=(2,4),最优利润为1600.求第三级目标(偏差)，列出LINDO程序：

MIN3DPLUS3+3DMINUS3+DPLUS4SUBJECTTO2X1+2X2<=12200X1+300X2-DPLUS1+DMINUS1=15002X1-X2-DPLUS2+DMINUS2=04X1-DPLUS3+DMINUS3=165X2-DPLUS4+DMINUS4=15DMINUS1=0DPLUS2+DMINUS2=0END计算结果如下：LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)29.00000VARIABLEVALUEREDUCEDCOSTDPLUS30.0000006.000000DMINUS38.0000000.000000DPLUS45.0000000.000000X12.0000000.000000X24.0000000.000000DPLUS1100.0000000.000000DMINUS10.0000000.000000DPLUS20.0000000.000000DMINUS20.00000011.333333DMINUS40.0000001.000000ROWSLACKORSURPLUSDUALPRICES2)0.0000000.3333333)0.0000000.0000004)0.0000005.6666675)0.000000-3.0000006)0.0000001.0000007)0.0000000.0000008)0.0000005.666667NO.ITERATIONS=2目标函数最优值为29，即第三级偏差为29。分析结果知，X1为2，X2为4，DPLUS1为100，因此目标规划的最优解为（2，4），最优利润为1600。六、整数规划要求变量取整数值的线性规划问题称为整数线性规划要求变量取0或1的线性规划问题称为0-1规划只要求部分变量取整数值的线性规划称为混合整数线性规划例投资决策问题

解投资决策变量

设获得的总利润为z，则上述问题的数学模型为

变量限制为整数本质上是一个非线性约束，它不可能用线性约束来代替它.☆常用算法：割平面算法、分枝定界法、解0-1规划的隐枚举法、分解算法、群论方法、动态规划方法一般只能用来解决中小型的ILP问题近似算法1993年7月W.J.Cook并行计算

10907064个城市货郎担问题计算机模拟法如Monte-Carlo方法考虑纯整数线性规划问题

可行区域记为D

(P)的松弛问题

可行区域

由有限个或可数的格点构成的集合

多面凸集

☆Gomory割平面法割平面法的基本思想费用减小方向★目标:①找到子域内的最优值②明确原问题P的最优解不在这个子域内★分枝定界法的关键是分枝和定界★思路：利用其松弛问题的最优解(值)来分枝定界1、分枝定界法的基本思想★分枝定界法是“巧妙”枚举ILP问题可行解★理论依据：有界ILP问题的可行集合中格点的数目是有限的☆分枝定界法考虑纯整数线性规划问题

分枝树分枝过程树根用增加两个互斥且穷举的不等式约束将一个问题分解为它的两个子问题作为该问题的两个后代.对第i个子问题，我们有一个松弛解xi，即相应于这个子域的ILP问题的目标函数下界zi=cTxi.这样的树称为分枝树分枝过程在某个点上由下述两个原因之一而停止：

⑴相应的松弛LP问题的解是满足整数要求的；

⑵相应松弛LP问题是不可行的

.树叶分枝树分枝过程树根定界过程死点被剪枝其余的点称为活点，从活点那里分枝仍可能改进值zm现有一客户需要50根4m、20根6m和15根8m的钢管.应如何下料最节省？原料钢管:每根19米4米50根6米20根8米15根客户需求问题.如何下料最节省?例某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管都是19m.☆钢管下料如何下料最节省？切割模式按照客户需要在原料钢管上安排切割的一种组合余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根余料5米4米1根6米1根4米1根可行的切割模式是很多的

哪些切割模式是合理的？余料应小于客户需要钢管的最小尺寸余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根余料5米4米1根6米1根4米1根针对问题有哪些合理的切割模式？4m钢管根数6m钢管根数8m钢管根数余料/m模式14003模式23101模式32013模式41203模式51111模式60301模式70023

何为节省？一是切割后剩余的总余料量最小二是切割原料钢管的总根数最少xi~按第i种模式切割的原料钢管根数(i=1,2,…7)决策变量

目标函数（总余量）整数约束：xi为整数约束条件需求502015整数线性规划模型最优解：x2=12,x5=15,

其余为0；最优值：27整数约束：xi为整数按模式2切割12根,按模式5切割15根，余料27米

xi~按第i种模式切割的原料钢管根数(i=1,2,…7)决策变量

目标函数（总根数）整数约束：xi为整数约束条件整数约束：xi为整数最优解：x2=15,x5=5,x7=5,其余为0；最优值：25按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米按模式2切割12根,按模式5切割15根，余料27米

按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米余料为目标根数为目标当余料没有用处时，通常以总根数最少为目标余料增加8米，但减少了2根零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以零售商规定采用的不同切割模式不能超过3种.此外，该客户除刚才需要的三种钢管外，还需要10根5m的钢管.应如何下料最节省？客户增加需求：5米10根问题.切割模式不能超过3种,如何下料最节省?例

选课策略某学校规定，运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课.这些课程的编号、名称、学分、所属类别和先修课要求如下表所示.那么，毕业时学生最少可一学习这些课程中的哪些课程.如果某个学生既希望选修课程的数量少，又希望所获得学分多，他可以选修哪些课程?课号课名学分所属类别先修课要求1微积分5数学

2线性代数4数学

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

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

例

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

2线性代数4数学

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

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

0-1规划模型

决策变量

目标函数

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

选修课程总数最少约束条件最少2门数学课，3门运筹学课，2门计算机课。

课号课名所属类别1微积分数学2线性代数数学3最优化方法数学；运筹学4数据结构数学；计算机5应用统计数学；运筹学6计算机模拟计算机；运筹学7计算机编程计算机8预测理论运筹学9数学实验运筹学；计算机先修课程要求最优解：

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数学实验微积分；线性代数学分最多多目标优化的处理方法：化成单目标优化。两目标(多目标)规划

讨论：选修课程最少，学分尽量多，应学习哪些课程？课程最少以学分最多为目标，不管课程多少。以课程最少为目标，不管学分多少。最优解如上，6门课程，总学分21。最优解显然是选修所有9门课程。多目标规划

在课程最少的前提下以学分最多为目标。最优解：

x1=x2=x3=x5=x7=x9=1,其它为0；总学分由21增至22。注意：最优解不唯一！课号课名学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3LINDO无法告诉优化问题的解是否唯一。可将x9=1易为x6=1增加约束，以学分最多为目标求解。多目标规划

对学分数和课程数加权形成一个目标，如三七开。=-0.8x1-0.5x2-0.5x3-0.2x4-0.5x5-0.2x6+0.1x7+0.1x8-0.2x9多目标规划

对学分数和课程数加权形成一个目标，如三七开。最优解：

x1=x2=x3=x4=x5=x6=x7=x9=1，其它为0；总学分28。课号课名学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3七、非线性规划约束集或可行域MP的可行解或可行点当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题否则，称为约束非线性规划或者约束最优化问题（一）基本概念(二)非线性规划方法概述极值问题无条件极值有条件极值必要条件充分条件Lagrange乘子法困难连续可微求驻点的方程组难，L中也有高维方程组只适合等式约束，而非线性规划有大量不等式约束解法数值解法（迭代法）例(最小二乘法问题)设通过观察或实验得到一上，即大体上可用直线方程来反映变量x与y之间的对应关系(参见右图).现要确定一直线,使得与这n个点的偏差平方之和为最小(最小二乘方)．解设所求直线方程为为此令把这组关于a,b的线性方程加以整理并求解，得并由实际意义可知这极小值即为最小值.问题：若已知xk,如何产生下一个迭代点xk+1？1、迭代法的基本思想和基本格式①按某种方法给出目标函数f(x)极小点x*的一个初始估计x0------初始点②按某种特定的迭代规则产生一个点列最后一个点最优解有穷点列极限点无穷点列方法是收敛的（三）迭代法求解问题(MP)问题迭代法的最基本的迭代格式第k轮搜索方向第k轮沿pk方向的步长迭代法求解的关键：构造每一轮的搜索方向和确定步长2、非线性规划基本迭代格式八、层次分析模型层次分析法（AHP）是美国运筹学家匹茨堡大学教授萨蒂(T.L.Saaty)于上世纪70年代初，为美国国防部研究“根据各个工业部门对国家福利的贡献大小而进行电力分配”课题时，应用网络系统理论和多目标综合评价方法，提出的一种层次权重决策分析方法。这种方法的特点是在对复杂的决策问题的本质、影响因素及其内在关系等进行深入分析的基础上，利用较少的定量信息使决策的思维过程数学化，从而为多目标、多准则或无结构特性的复杂决策问题提供简便的决策方法。是对难于完全定量的复杂系统作出决策的模型和方法。一、层次分析法概述决策是指在面临多种方案时需要依据一定的标准选择某一种方案。日常生活中有许多决策问题。举例

1.在海尔、新飞、容声和雪花四个牌号的电冰箱中选购一种。要考虑品牌的信誉、冰箱的功能、价格和耗电量。

2.在泰山、杭州和承德三处选择一个旅游点。要考虑景点的景色、居住的环境、饮食的特色、交通便利和旅游的费用。

3.在基础研究、应用研究和数学教育中选择一个领域申报科研课题。要考虑成果的贡献（实用价值、科学意义），可行性（难度、周期和经费）和人才培养。

层次分析法（AnalyticHierarchyProcess,AHP)这是一种定性和定量相结合的、系统化的、层次化的分析方法。

过去研究自然和社会现象主要有机理分析法和统计分析法两种方法，前者用经典的数学工具分析现象的因果关系，后者以随机数学为工具，通过大量的观察数据寻求统计规律。近年发展的系统分析是又一种方法，而层次分析法是系统分析的数学工具之一。二、层次分析法的基本原理层次分析法根据问题的性质和要达到的总目标，将问题分解为不同的组成因素，并按照因素间的相互关联影响以及隶属关系将因素按不同层次聚集组合，形成一个多层次的分析结构模型，从而最终使问题归结为最低层(供决策的方案、措施等)相对于最高层(总目标)的相对重要权值的确定或相对优劣次序的排定。层次分析法的基本思路：与人们对某一复杂决策问题的思维、判断过程大体一致。选择钢笔质量、颜色、价格、外形、实用钢笔1、钢笔2、钢笔3、钢笔4质量、颜色、价格、外形、实用进行排序将各个钢笔的质量、颜色、价格、外形、实用进行排序经综合分析决定买哪支钢笔三、层次分析法的步骤和方法

运用层次分析法构造系统模型时，大体可以分为下四个步骤：

1.建立层次结构模型

2.构造判断(成对比较)矩阵

3.层次单排序及其一致性检验

4.层次总排序及其一致性检验

1.建立层次结构模型将决策的目标、考虑的因素（决策准则）和决策对象按它们之间的相互关系分为最高层、中间层和最低层，绘出层次结构图。

最高层：决策的目的、要解决的问题。

最低层：决策时的备选方案。

中间层：考虑的因素、决策的准则。对于相邻的两层，称高层为目标层，低层为因素层。下面举例说明。目标层O(选择旅游地)P2黄山P1桂林P3北戴河准则层方案层C3居住C1景色C2费用C4饮食C5旅途例选择旅游地如何在3个目的地中按照景色、费用、居住条件等因素选择.2.构造判断(成对比较)矩阵在确定各层次各因素之间的权重时，如果只是定性的结果，则常常不容易被别人接受，因而Santy等人提出：一致矩阵法，即：1.不把所有因素放在一起比较，而是两两相互比较2.对此时采用相对尺度，以尽可能减少性质不同的诸因素相互比较的困难，以提高准确度。心理学家认为成对比较的因素不宜超过9个，即每层不要超过9个因素。

判断矩阵是表示本层所有因素针对上一层某一个因素的相对重要性的比较。判断矩阵的元素aij用Santy的1—9标度方法给出。2468比较尺度aij

Saaty等人提出1~9尺度——aij

取值1,2,…,9及其互反数1,1/2,…,1/9尺度13579相同稍强强明显强绝对强aij=1,1/2,,…1/9的重要性与上面相反心理学家认为成对比较的因素不宜超过9个用1~3,1~5,…1~17,…,1p~9p

(p=2,3,4,5),d+0.1~d+0.9(d=1,2,3,4)等27种比较尺度对若干实例构造成对比较阵，算出权向量，与实际对比发现，1~9尺度较优。便于定性到定量的转化：设要比较各准则C1,C2,…,Cn对目标O的重要性A~成对比较阵A是正互反阵要由A确定C1,…,Cn对O的权向量选择旅游地目标层O(选择旅游地)准则层C3居住C1景色C2费用C4饮食C5旅途C1C2C3C4C5C1C2C3C4C5尺度13579相同稍强强明显强绝对强3.层次单排序及一致性检验问题：如何根据判断矩阵求出各因素的重要性程度的排序权重？方法：特征向量法特征值与特征向量定