线性规划与非线性规划

1、运筹学线性规划与非线性规划线性规划与非线性规划是运筹学的一个分支.运筹学研究什么呢?运筹学是研究“如何做出正确决策或选择，以达到最好结果”的一 门数学学科.有一句成语形象地说明了运筹学的特点：运筹帷幄，决胜千里数学因实际的需要而产生，数学的很多重大发现也因实际的需要而出现数学建模竞赛既因实际的重要需要而在世界范围内（在我国近十几年）各大学蓬勃开展. 没有受到条条框框制约、富有聪明才智的大学生们，在每次竞赛中都能对实际中的一些重要 问题与难题给出富有新鲜创意的解决办法，往往因此产生重大的社会效益和经济效益建模 竞赛就是知识的“强行军”.竞赛会极大地激发学生们的创造性思维，是对学生们思考能力 和动

2、手能力的考验.竞赛能让学生们切身感受到学习各科知识的必要性、重要性，成为学生 们认真学习的推动力.数学建模会涉及数学的众多学科：微分方程，运筹学，概率统计，图论，层次分析，变 分法，要求建模者有较高的数学素养，有综合应用已学到的数学方法和思维对问题进行 分析、抽象及简化的能力.数学建模既是建立实际问题的数学模型.一、最优化模型数学建模的目的是使决策人的“利益”最大化，因此而建立的数学模型即所谓的最优化 模型.决策人在作决策时要有“科学观”，为实现目标（“利益”最大化）应进行“科学决策”. 最优化模型正是为实现科学决策而建立的数学模型，是科学决策的科学体现科学决策的目的是要对为实现目标而提出的设

3、计和操作最佳化，最终实现决策人的“利 益”最大化.一个最优化模型包括决策变量、目标函数和约束条件，它将“说明”决策变量在满足约 束条件的前提下应使目标函数值最优化（最大或最小）.决策变量是指影响并决定目标实现的变量，其变化范围一般是可控制的目标函数是指根据决策变量建立的目标的函数表达式约束条件是指决策变量所受的限制（用等式、不等式的函数方程表示）.人们建立最优化模型的目的是，希望通过科学的计算方法（称为最优化方法）找出使目标 函数值最优（最大或最小）的决策变量的值（称为最优决策）.实际问题的7步建模过程：第1步：表述问题.说明目标及各种因素.第2步：分析数据或采集（或收集）并分析数据.第3步：

4、建立数学模型.第4步：对模型求解.即寻找最优决策.第5步：检验、评价模型.如果与实际情况（或实际数据）吻合，则转到第7步，否则转 到第6步.第6步：修改或矫正模型，并返回到第1步、第2步或第3步.第7步：模型应用，提出合理化建议.最优化数学模型的一般形式为maxz = f （x，x，,x ）; TOC o 1-5 h z 12n（或 min）（1.1）s.t. g （x，x，x ） = 0，i = 1，p，i 1 2ng （x，x，,x ） 0，i = p +1，,m.i12n其中，x j （ j = 1,n）是决策变量；乙=f （气,%，,七）是目标函数；g （x，X，x ） = 0（，=

5、1，p）和 g （x，x，x ） 0（i = p +1，m）是约束条件，i 12 ni 12 n前者称为等式约束，后者称为不等式约束.不带约束条件的（1）式是无约束问题的模型.由满足所有约束条件的决策向量x =（气,x2，.，xn）T组成的集合称为可行域，通常记 为D.求解（1）是指，寻找x * = （x*, x*，.，x*）T G D使z = f （x*, x；，,x*）为目标函数f在可行 域D上的最小值（或最大值）.x*称为最优解，f （x*,x：,x*）称为最优值.最优解有严格与非严格和全局与局部之分.优化模型的最优解是指全局最优解.严格极小点一严格极小点全局一非严格极小点一非严格极小点

6、图1 一维函数的最优解图示这里指出：最优化方法解出的多是优化模型的局部最优解.由于最优化方法多为迭代法， 所以取不同的初始点一般会得到一个或多个局部最优解，然后再从这些局部最优解中找出 “全局”最优解.二、线性规划（LP）线性规划在银行、教育、林业、石油、运输等各种行业以及科学的各个领域中有着 广泛的应用.线性规划模型目标函数、约束函数均为线性函数的最优化模型既是所谓的线性规划模型（1）标准形式min z = cx + c x + c x ;（或 max）1 12 2n ni = 1,，m,（2.1）st. a x + a x + a x = b,i1 1 i 2 2in n ix 0, j

7、= 1,.,n.这里，约束a x + a x + a x = b (i = 1,m)是对决策变量的主要约束，称为主约束 i1 1 i 2 2in n i而约束x, 0( j = 1,n) (x,(j = 1,n)称为非负变量)是对决策变量的符号约束； 七(i = 1,m)是主约束的右端常数项(通常不妨设为非负数)；值系数.c j (j = L,n)称为价(2)式可以写成如下矩阵形式,min z = ctx;(或 max)s.t. Ax = b,_x 0.(2.2)其中，a11a12.a1nc1ba21.a22:.a2n:_,c =c:2_,x=x:2_,b =b:2Ia m1am2.amn)n

8、 j n b, 0, j = 1,q,x,任意,j = q +1,n.i = 1,p,i = p +1,，u,i = u +1,，m,(2.3)这里，约a x + a x + a xi1 1i 2 2in na x + a x +i1 1i 2 2in ni(j = q +1,n)是符号约束，其中xj (j = q +1,n)称为自由变量.一般形式可以(通过如下办法)转化为标准形式.=b (i = L，p)i(i = p +1,u) + a x 0(j = 1,q)一一一 ja x + a x + a xi1 1 i 2 2in n、和和七任意(i)将不等式约束转化为等式约束引入剩余变量*0将

9、不等式约束a x + a x + a x b改写为i1 1 i 2 2in n ia x + a x + a x s = b , i = p +1,，u .i1 1i 2 2in n i i(2.4)引入松弛变量匕0将不等式约束a x + a x + a x 0，x- 0，代入到目标函数和其它约束中便可去掉x取一个包含x的等式约束(如果有的话)，比如：ja x ；F a x ；F a x = b，i1 1ij jin n i由此解出baa(2.7)x = H x ，, , in x ，j aa 1 a n代入到目标函数和其它约束函数中便可去掉.第一种方法将增加变量的数目，导致问题的维数增大.第

10、二种方法正好相反.用(2.4)、(2.5)两式替换(2.3)式中相应的不等式约束，将(2.7)式代入目标函数和其它 约束函数中，去掉目标函数与主约束中的所有自由变量，最后将s 0(i = p +1,.,u)、ie 0(i = u +1,.,m)和 x+ 0,x- 0( j = q +1,n)加入(2.3)式的符号约束中，(2.3)ij j式就此转化为标准形式的线性规划min z = cx + + c x + c (x + x + ) + + c (x + x+);(或max)1 1q qq;1 q;1q;1n n nst. a x + a x + a (x ; x ; )+ a (x ; x

11、;) = b, i = 1,p,i1 1iq qiq;1 q;1q;1in n n ia x ; + a x ; a (x ; x ; ) ; ; a (x ; x ;) s b, i = p ;1,u,i1 1iq qiq;1q;1q;1innniia x + a x ; a (x ; x ; )+ a (x ; x +) ; e 0, j = 1,q; x ; 0, x- 0, j = q ;1,n;s 0,i = p ;1,，u;e 0,i = u ;1,m.一般形式与其标准形式问题的求解等价，因为这两个问题的可行解一一对应，目标函数 值对应相等.所以如果这两个问题之一有最优解，那么另一

12、个也必有最优解，且最优值相等.线性规划的特点线性规划的可行域是凸集：凸多边形、凸多面体或空集.凸集非凸集凸多边形凸多面体（2）目标函数的等值面（或等值线）是平行的（超）平面（或直线）.如果线性规划有最优解，那么可行域的某个顶点必是最优解求解线性规划将出现下列4种情况之一.情况1：有唯一（最优）解.情况2：有无穷多（最优）解.情况3：解无界.情况4：无解.有唯一解 有无穷多解 有无界解 无解线性规划的解法线性规划的解法有Dantzig单纯形法，大M法，对偶单纯形法，Karmarkar法，列生成 法，目标规划，分解算法等.软件中多为Dantzig单纯形法.参考书目：薛嘉庆.线性规划.北京：高等教育

13、出版社,1989刁在筠 郑汉鼐等.运筹学.北京：高等教育出版社,2001特殊的线性规划当所有决策变量都取整数时，称为整数规划（IP）.当所有决策变量只取0或1时，称为0-1规划.当只有部分决策变量取整数时，称为混合整数规划（混合IP）.解整数规划的方法主要有穷举法（对决策变量过多的问题不适用）、分枝定界法和割平面 法.分枝定界法比较常用.解小规模0-1规划的常用方法一一隐枚举法.分枝定界法也适用于求解混合整数规划.参考书目：刁在筠郑汉鼐等.运筹学.北京：高等教育出版社,2001胡运权.运筹学基础及应用.北京：高等教育出版社,2004特殊的线性规划问题及其解法（1）运输问题运输问题用“运输”单纯

14、形法求解.（2 ）转运问题转运问题可以化为运输问题，所以也用“运输”单纯形法求解（3 ）指派问题指派问题是特殊的0-1规划，常用匈牙利法求解.线性规划的算法可在Mat lab “优化”工具箱中寻找.线性规划建模实例在一个线性规划模型中，决策变量应当完全描述要做出的决策.决策者都希望由决策变量表示的目标函数最大化(通常为收入或利润)或最小化(通 常为成本).目标函数中的系数反映的是决策变量对目标函数的单位贡献.主约束条件中决策变量的系数称为“技术”系数，这是因为技术系数经常影响用于 “生产，不同“产品，的技术.右端项常表示可用资源的数量.示例1 一家汽车公司生产轿车和卡车.每辆车都必须经过车身装

15、配车间和喷漆车间处 理.车身装配车间如果只装配轿车，每天可装配50辆；如果只装配卡车，每天可装配50 辆.喷漆车间如果只喷轿车，每天可喷60辆；如果只喷卡车，每天可喷40辆.每辆轿车的 利润是1600元，每辆卡车的利润是2400元公司的生产计划部门须制定一天的产量计划以 使公司的利润最大化.建模过程：公司追求的目标是其利润的最大化，生产计划部门为此要决定每一种车型的 产量，所以定义两个决策变量：气=每天生产的轿车数量，=每天生产的卡车数量.公司每天的利润为1600气+ 2400%，因此该公司追求利润最大化即为 max z = 1600 x + 2400 x .按题意，决策变量须满足以下3个条件

16、(如果把每天的时间设为1，那么每天的工作时间应该小于等于1.)：(1)装配车间每天处理一辆轿车和一辆卡车的时间均为二，所以处理x辆轿车和x辆 5012卡车的时间应满足-1 x + x 150 1 50 2喷漆车间每天处理一辆轿车的时间为土1处理一辆卡车的时间为40,所以处理辆轿车和x2辆卡车的时间应满足1160 七 + 40 x2非负限制xj为负整数，j = 1,2 .该汽车公司追求利润最大化的数学模型为如下线性规划max z = 1600 x + 2400 x ；,1. 11 八 2s.t. x + x 1,50 1 50 211x + x 500.（2）每天摄取的巧克力至少必、须达到2 6

17、盎司.即43x + 2x 6.（3）每天摄取的糖至少必须达到10盎司.即22 x + 2 x + 4 x + 4 x 10.（4） 每天摄取的脂肪至少必须达到8盎司.即42 x + 4 x + X + 5 X 8.以及非负限制1234X. 0, j = 1,2,3,4.该美国人饮食费用最少的数学模型为max z = 50 x + 20 x + 30 x + 80 x ；s.t. 400 x + 200 x +150X + 500 x 500,12343x + 2x 6,2x + 2x + 4x + 4x 10,2x + 4x + x + 5x 8,x 0, i = 1,2,3,4.这个问题的最

18、优解是气=X4 = 0,X2 = 3,X3 = 1,z = 90，表示每天最少花90美分便可得到符 合饮食要求的750卡路里、6盎司巧克力、10盎司糖和13盎司脂肪.列出更现实的食物和营养需求的饮食问题是计算机解决的最早的LP之一.整数规划已 用于计划每周或每月的公共饮食业菜单.菜单计划模型包含反映可口性和多样性要求的约束 条件.示例3某服务部门一周中每天需要不同数目的雇员：周一到周四每天至少需要50人， 周五至少需要80人，周六和周日至少需要90人.规定应聘者需连续工作5天.试确定聘用方 案：使在满足需要的条件下聘用的总人数最少.建模过程：该服务部门追求的目标是一周中聘用的总人数最少.该服务

19、部门因此必须做 出决策：每天聘用多少人.为此，定义以下决策决量：X ,X，,X分别表示周一至周日聘用的人数. TOC o 1-5 h z 127因此目标函数为z - X + X + X + X + X + X + X .1234567决策变量必须满足以下7个条件：周一工作的雇员应是周四到周一聘用的，按照需要至少有50人，即x + x + x + x + x 5014567类似地，有x + x + x + x + x 50,12567x + x + x + x + x 50,12367x + x + x + x + x 50,12347x + x + x + x + x 80,12345x +

20、x + x + x + x 90,23456x + x + x + x + x 90.34567人数应该是整数，所以决策变量须是非负的整数变量，即X,为非负整数，i = 1,2,7 .该服务部门聘用总人数最少的数学模型是如下的整数规划模型：min z = X + X + X + X + X + X + x ；1234567s.t. X + X + X + X + X 50,14567x + x + x + x + x 50,12567x + x + x + x + x 50,12367x + x + x + x + x 50,12347x + x + x + x + x 80,12345x +

21、 x + x + x + x 90,23456x + x + x + x + x 90, 34567 X,为非负整数,i = 1,2,.,7.示例4（工作调度问题）在每周的不同工作日，一个邮局需要不同数量的专职员工.表1 给出了每天需要的专职员工的数量.工会章程规定：每个专职员工每周必须连续工作五天， 然后休息两天.这个邮局希望通过只使用专职员工来满足每天的需要，那么这个邮局至少要 聘用多少专职员工.表1邮局的需要工作日需要的专职员工数量工作日需要专职员工的数量1=星期一175=星期五142=星期二136=星期六163=星期三157=星期日114二星期四19首先来看一个不正确的模型.有许多学生

22、定义决策变量X,为第i天上班员工的数量（第1 天=星期一，第2天=星期二，依次类推），然后推出邮局专职员工的数量=（星期一上班员工的 数量+星期二上班员工的数量+星期日上班员工的数量）/5，于是得到如下目标函数z = X + X + X + X + X + X + X .1234567添加约束条件X, （第i天需要的员工数量）和符号限制条件X, 0（i = 1,2,7）后，得到如 下不正确的线性规划模型：min z = x + x + x + x + x + x + x ; HYPERLINK l bookmark66 o Current Document s.t. x 17,1x 13,2x

23、 15,3x 19,4x 14,12345675x 16,6x 11, x,为非负整数，=1,2,7 .这里目标函数是专职员工的数量的5倍，问题是约束条件不能反映员工连续工作五天然后休 息两天的事实.建模过程：这个邮局追求的目标是聘用尽可能少的专职员工.正确表述这个问题的关键 是，定义的决策变量不应该是每天有多少人上班，而是一周中每天有多少人开始上班.定义 决策变量：x,二第，天开始上班员工的数量.例如，x是星期一开始上班员工的数量（这些人从星期一工作到星期五）.那么邮局（专职员 工的数量）=（星期一开始上班员工的数量）+ （星期二开始上班员工的数量）+（星期日开始 上班员工的数量）.由于每个

24、员工都只在一周的某一天开始上班，所以这个表达式不会重复计 算员工.因此，追求聘用尽可能少的专职员工的目标函数为z = x + x + x + x + x + x + x ; TOC o 1-5 h z 1234567决策变量满足以下约束条件：在星期一上班员工的数量不少于17人：x + x + x + x + x 17 ；14567在星期二上班员工的数量不少于13人：x + x + x + x + x 13 ；1 2 567在星期三上班员工的数量不少于15人：x + x + x + x + x 15 ；1 2 367在星期四上班员工的数量不少于19人：x + x + x + x + x 19 ；

25、12347在星期五上班员工的数量不少于14人：x + x + x + x + x 14 ； 12345 在星期六上班员工的数量不少于16人：x + x + x + x + x 16 ； 23456在星期日上班员工的数量不少于11人：x + x + x + x + x 11.34567及符号限制条件：x,为非负整数，, = 1,2,7 .邮局追求聘用尽可能少的专职员工的调度方案数学模型为min z = x + x + x + x + x + x + x ;1234567+ x + x + x + x 17,s.t. x1x1 + x2x1 + x2 + x3x + x + x + x123456

26、7+ x + x + x 13,+ x + x 15 ,+ x 19, 14.x + x + x + x + x12345x + x + x + x + x23456x + x + x + x + x3456716,11=3，最优值z = 23.x,为非负整数，, = 1,2,7 .这个模型的一个最优解为x = 4, x = 4, x = 2, x = 6, x = 0, x = 4, x1234567该模型存在另外一个问题：只有在周一、周二开始上班的员工才能在周末休息，而在其 它时间开始上班的员工永远不会有在公休日与家人团聚的机会.显然这不公平合理.从该模型的解出发，我们可以设计出如下公平合

27、理的以23周为一个轮转周期的员工调 度方案：第1-4周：在星期一开始上班第5-8周：在星期二开始上班第9-10周：在星期三开始上班第11-16周：在星期四开始上班第17-20周：在星期六开始上班第21-23周：在星期日开始上班员工1将遵守这个调度方案23周，员工2从第2周开始遵守这个调度方案23周（在星期一 开始上班的时间为3周，在星期二开始上班的时间为4周，在星期日开始上班的时间为 3周，在星期一开始上班的时间为1周）.以这样的方式继续下去，就可以为每个员工制定一 个23周调度方案.例如，员工13的调度方案如下：第1-4周：在星期四开始上班第5-8周：在星期六开始上班第9-11周：在星期日开

28、始上班第12-15周：在星期一开始上班第16-19周：在星期二开始上班第20-21周：在星期三开始上班第22-23周：在星期四开始上班本示例提醒我们，所建立的模型一定要考虑合理性，符合实际.而本示例更符合实际的 考虑是员工还有年休假.在邮局这个示例中，如果邮局可以同时使用专职员工和兼职员工来满足每天的需要，且 在每一周，专职员工必须连续工作5天，每天工作8小时；兼职员工必须连续工作5天，每 天工作4小时.专职员工的工资是每小时15美元，而兼职员工的工资只有每小时10美元（没 有附加福利）.工会把每周的兼职劳动限制在25%，表述一个LP，使这个邮局每周的劳动力成 本最少.比示例5的单阶段工作调度

29、模型更复杂的是多阶段工作调度模型.类似的还有多阶段库存模型、多阶段财务管理（投资）模型等.示例5（指派问题）某班准备从5名游泳队员中选4人，组队参加学校的4 x 100 m混合 泳接力比赛.5名队员4种泳姿的百米平均成绩如表1所示，问应该怎样选拔接力队成员？表1 5名队员4种泳姿的百米平均成绩（秒）数据队员甲乙丙丁戊蝶泳66.857.2787067.4仰泳75.66667.874.271蛙泳8766.484.669.683.8自由泳58.65359.457.262.4建模过程：该班追求的目标是接力队的成绩最好.该班因此要做出决策：从5名队员中 选出4人，每人一种泳姿，且4人的泳姿各不相同（容易

30、想到的一个办法是穷举法，组成接 力队的方案共有5!=120种.）.设i = 1,2,3,4,5分别代表甲、乙、丙、丁和戊队员，j = 1,2,3,4分别代表蝶泳、仰泳、 蛙泳和自由泳泳姿，%表示队员i的第j种泳姿的百米平均成绩.定义决策决量、：若选择队员i参加泳姿j的比赛（i = 1,2,3,4,5, j = 1,2,3,4），则 X = 1，否则气=0.该班追求的目标是接力队的成绩最好(只要对每一方案的成绩作比较，即可找出最优方 案，但显然这不是解决问题的好办法.随着问题规模的变大，穷举法的计算量将是无法接受 的).当队员，入选泳姿j时，C X表示他的成绩，否则C X = 0，因此目标函数为

31、 ij ijj jz = 24E5 c x .j=1 i=1 决策变量必须满足以下3个条件：每人最多只能入选4种泳姿之一，即4 x 1， i = 1,2,3,4,5 .ij j=1每种泳姿必须有1人而且只能有1人入选，即5 x = 1， j = 1,2,3,4.i=1(3 )取值受限x= 0 或 1, i = 1,2,3,4,5, j = 1,2,3,4. 该班追求接力队成绩最好的数学模型为0-1规划：min z = 区 cx ;ij ijj=1 i=1s.t. X 0, i = p +1,.,m.其中函数f,g,(i = 1,p),g,(i = p +1,m)中至少有一个为非线性函数.非线性

32、规划有无约束问题与有约束问题之分.非线性规划的特点非线性规划的可行域及最优解的情况远比线性规划的可行域及最优解复杂的多:可能有 最优解，也可能没有最优解；约束问题的最优解可能在可行域的内部，也可能在可行域的边 界上.一些常用概念：等值面(线)一一函数值相等的决策变量曲面(曲线)f (元)=C.上升/下降方向一一至少在局部范围内，函数值升的方向/函数值降的方向 f 0 + tp) f 0), t E (0,8)/f 0 + tp) f (无),t E (0,8).梯度一一多元函数的“一阶导数”，由函数的偏导数组成的向量1_2 /若Vf (x)。0，则Vf (x)必垂直于f (无)过点无的等值面；

33、梯Vf (x)4空，绑，乎T.oxoxox当梯度Vf (x )连续时，度Vf (x)的方向是函数f (x)在点x具有最大变化率的方向.方向导数函数在某方向上的变化率(下式中e是p方向上的单位向量)of (x)f(x + te) - f (x)-=lim -op-0+罕) = Vf (x )re.op若号)0，即Vf (x0p0 ,则p方向是f (x)在点x0处的上升方向；若 of(x) 0，即Vf (xp V 0，则p方向是f (x)在点x处的下降方向.op00V 2 f (x )=海赛矩阵一一多元函数的“二阶导数”，由函数的二阶偏导数组成的矩阵ox ox I，匕空间中由点x0和方向p所确定的

34、直线方程为x = x + tp,t e Ri.0图2直线的几何图示非线性规划的解法(1)非线性规划基本解法基本解法的迭代格式一般为x i = x + tp , k = 0,1，称x为初始点，p为x处的搜索方向，t为步长因子，满足f (x +1 p ) pCx = dWolfe 法.参考书目：赵凤治.约束最优化方法.北京：科学出版社,1991(2)数据拟合问题(最小二乘问题)最小二乘法非线性规划建模实例示例1某公司有6个建筑工地要开工，每个工地的位置(用平面坐标(a,b)表示，距离 单位：km)及水泥日用量d (单位：t (吨)由表1给出.目前有两个临时料场位于A(5,1)和 B(2,7)，日储

35、量各有201 .请回答以下两个问题：假设从料场到工地之间均有直线道路相连，试制定每天从A、B两料场分别向各工地 运送水泥的供应计划，使总的吨公里数最小.为进一步减少吨公里数，打算舍弃目前的两个临时料场，修建两个新料场，日储量 仍各为201，问建在何处最佳，可以节省多少吨公里数.表1工地的位置(a, b)及水泥日用量d的数据料场123456a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611建模过程：公司追求的目标是每天从A、B两料场分别向各工地运送水泥总的吨公里数 最小.为表述该问题，设工地的位置与水泥日用量分别为(气,b)和七(i = 1,2,

36、6),料场位 置及其日储量分别为3 , J )和e (j = 1,2).定义决策变量w (i: 1,2, j = 1,2):料 j j jij场j向工地，的运送量(i = 1,2,6, j = 1,2 )，在问题(2)中，新建料场位置(七,七)也是决 策变量.公司追求总的吨公里数最小的目标函数为f =空j =1 i=1WjV(x- a)2 + (y. b)2 .决策变量w (i = 1,2,6, j = 1,2)必须满足以下约束条件:满足各工地的水泥日用量 w = d , i = 1,2, .,6.j=1各料场的运送量不能超过日储量 w. 0 , i = 1,2,.,6, j = 1,2.(1)公司追求总的吨公里数最小的数学模型是如下线性规划模型w .v(2 - a )2 + (7 - b )2 ；i = 1min f = w. J(5-a.)2 + (1 -b) + i = 1s.t. w = d , i = 1,2, ,6 ,j=1w. 0 , i = 1,2,.,6, j = 1,2.这个模型的解，即料场A、B向6个工地运送水泥的计划为wii工地1工地2工地3工地4工地5