线性规划与非线性规划

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

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

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

4、第4步：对模型求解.即寻找最优决策.第5步：检验、评价模型.如果与实际情况(或实际数据)吻合，则转到第7步，否则转到第6步.第6步：修改或矫正模型，并返回到第1步、第2步或第3步.第7步：模型应用，提出合理化建议.最优化数学模型的一般形式为 (1.1)其中，是决策变量；是目标函数；和是约束条件，前者称为等式约束，后者称为不等式约束.不带约束条件的(1)式是无约束问题的模型.由满足所有约束条件的决策向量组成的集合称为可行域，通常记为.求解(1)是指，寻找使为目标函数f在可行域上的最小值(或最大值).称为最优解，称为最优值.最优解有严格与非严格和全局与局部之分.优化模型的最优解是指全局最优解. 严

5、格极小点 严格极小点局部 全局 非严格极小点 非严格极小点图1 一维函数的最优解图示这里指出：最优化方法解出的多是优化模型的局部最优解.由于最优化方法多为迭代法，所以取不同的初始点一般会得到一个或多个局部最优解，然后再从这些局部最优解中找出“全局”最优解.二、线性规划(LP) 线性规划在银行、教育、林业、石油、运输等各种行业以及科学的各个领域中有着广泛的应用.1. 线性规划模型 目标函数、约束函数均为线性函数的最优化模型既是所谓的线性规划模型.(1)标准形式 (2.1)这里，约束是对决策变量的主要约束，称为主约束，而约束(称为非负变量)是对决策变量的符号约束；是主约束的右端常数项(通常不妨设为

6、非负数)；称为价值系数.(2.1)式可以写成如下矩阵形式 (2.2)其中，.决策向量，主约束右端常数向量，价值向量.(2)一般形式 (2.3)这里，约束、和是主约束，而约束和任意是符号约束，其中称为自由变量.一般形式可以(通过如下办法)转化为标准形式.(i)将不等式约束转化为等式约束引入剩余变量，将不等式约束改写为，. (2.4)引入松弛变量，将不等式约束改写为，. (2.5)(ii)去除自由变量去掉自由变量有两种办法：用非负变量的差表示自由变量设， (2.6)其中，代入到目标函数和其它约束中便可去掉.取一个包含的等式约束(如果有的话)，比如：，由此解出， (2.7)代入到目标函数和其它约束函

7、数中便可去掉.第一种方法将增加变量的数目，导致问题的维数增大.第二种方法正好相反.用(2.4)、(2.5)两式替换(2.3)式中相应的不等式约束，将(2.6)式或(2.7)式代入目标函数和其它约束函数中，去掉目标函数与主约束中的所有自由变量，最后将、和加入(2.3)式的符号约束中，(2.3)式就此转化为标准形式的线性规划， 一般形式与其标准形式问题的求解等价，因为这两个问题的可行解一一对应，目标函数值对应相等.所以如果这两个问题之一有最优解，那么另一个也必有最优解，且最优值相等.2. 线性规划的特点(1)线性规划的可行域是凸集：凸多边形、凸多面体或空集.凸集非凸集凸多边形 凸多面体(2)目标函

8、数的等值面(或等值线)是平行的(超)平面(或直线).(3)如果线性规划有最优解，那么可行域的某个顶点必是最优解.(4)求解线性规划将出现下列4种情况之一.情况1：有唯一(最优)解.情况2：有无穷多(最优)解.情况3：解无界.情况4：无解.有唯一解 有无穷多解 有无界解 无解3. 一般线性规划的解法线性规划的解法有Dantzig单纯形法，大M法，对偶单纯形法，Karmarkar法，列生成法，目标规划，分解算法等.软件中多为Dantzig单纯形法.参考书目高等教育出版社,1989刁在筠 郑汉鼑等. 运筹学.北京：高等教育出版社,2001 4. 特殊的线性规划当所有决策变量都取整数时，称为整数规划(

9、IP).当所有决策变量只取0或1时，称为0-1规划.当只有部分决策变量取整数时，称为混合整数规划(混合IP).解整数规划的方法主要有穷举法(对决策变量过多的问题不适用)、分枝定界法和割平面法.分枝定界法比较常用.解小规模0-1规划的常用方法隐枚举法.分枝定界法也适用于求解混合整数规划.参考书目：刁在筠 郑汉鼑等. 运筹学.北京：高等教育出版社,2001 5. 特殊的线性规划问题及其解法(1)运输问题运输问题用“运输”单纯形法求解.(2)转运问题转运问题可以化为运输问题，所以也用“运输”单纯形法求解.(3)指派问题指派问题是特殊的0-1规划，常用匈牙利法求解.线性规划的算法可在Matlab“优化

10、”工具箱中寻找.6. 线性规划建模实例在一个线性规划模型中，(1)决策变量应当完全描述要做出的决策.(2)决策者都希望由决策变量表示的目标函数最大化(通常为收入或利润)或最小化(通常为成本).目标函数中的系数反映的是决策变量对目标函数的单位贡献.(3)主约束条件中决策变量的系数称为“技术”系数，这是因为技术系数经常影响用于“生产”不同“产品”的技术.右端项常表示可用资源的数量.示例1 一家汽车公司生产轿车和卡车.每辆车都必须经过车身装配车间和喷漆车间处理. 车身装配车间如果只装配轿车，每天可装配50辆；如果只装配卡车，每天可装配50辆.喷漆车间如果只喷轿车，每天可喷60辆；如果只喷卡车，每天可

11、喷40辆. 每辆轿车的利润是1600元，每辆卡车的利润是2400元.公司的生产计划部门须制定一天的产量计划以使公司的利润最大化.建模过程：公司追求的目标是其利润的最大化，生产计划部门为此要决定每一种车型的产量，所以定义两个决策变量：每天生产的轿车数量，每天生产的卡车数量.公司每天的利润为，因此该公司追求利润最大化即为.按题意，决策变量须满足以下3个条件(如果把每天的时间设为1，那么每天的工作时间应该小于等于1.)： (1)装配车间每天处理一辆轿车和一辆卡车的时间均为，所以处理辆轿车和辆卡车的时间应满足.(2)喷漆车间每天处理一辆轿车的时间为，处理一辆卡车的时间为，所以处理辆轿车和辆卡车的时间应

12、满足.(3)非负限制为负整数,.该汽车公司追求利润最大化的数学模型为如下线性规划示例2(饮食问题) 有一个美国人的饮食方案要求他吃的所有食物都来自四个“基本食物组”之一(巧克力蛋糕、冰淇淋、苏打水和干酪蛋糕).目前他可以消费的食物有下列4种：胡桃巧克力糖、巧克力冰淇淋、可口可乐和菠萝干酪蛋糕.一块胡桃巧克力糖的价格为50美分，一勺巧克力冰淇淋的价格为20美分，一瓶可口可乐的价格为30美分，一块菠萝干酪蛋糕的价格为80美分.自己每天的营养要求，那他应该怎样做.表1 食物的营养价值数据食物类型卡路里巧克力(盎司)糖(盎司)脂肪(盎司)胡桃巧克力糖(1块)400322巧克力冰淇淋(1勺)200224

13、可口可乐(1瓶)150041菠萝干酪蛋糕(1块)500045建模过程：这个美国人追求的目标是使饮食的费用最少.因此这个美国人必须做出决策：对于每种食物，每天应当吃多少.因此，需要定义下列决策变量：每天吃的胡桃巧克力糖的数量(单位：块)，每天吃的巧克力冰淇淋的数量(单位：勺)，每天喝的可口可乐的数量(单位：瓶)，每天吃的菠萝干酪蛋糕的数量(单位：块).他追求的目标是使饮食的费用最少，因此目标函数为.决策变量必须满足以下4个条件：(1) 每天摄取的卡路里至少必须达到500卡路里.即.(2)每天摄取的巧克力至少必须达到6盎司.即.(3)每天摄取的糖至少必须达到10盎司.即.(4)每天摄取的脂肪至少必

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

15、最少.该服务部门因此必须做出决策：每天聘用多少人.为此，定义以下决策决量：分别表示周一至周日聘用的人数.因此目标函数为.决策变量必须满足以下7个条件：周一工作的雇员应是周四到周一聘用的，按照需要至少有50人，即.类似地，有人数应该是整数，所以决策变量须是非负的整数变量，即 为非负整数，.该服务部门聘用总人数最少的数学模型是如下的整数规划模型：示例4(工作调度问题)表1 邮局的需要工作日 需要的专职员工数量 工作日 需要专职员工的数量1=星期一 172=星期二 133=星期三 154=星期四 195=星期五 146=星期六 167=星期日 11首先来看一个不正确的模型.有许多学生定义决策变量为第

16、天上班员工的数量(第1天=星期一，第2天=星期二，依次类推),然后推出邮局专职员工的数量=(星期一上班员工的数量+星期二上班员工的数量+星期日上班员工的数量)/5，于是得到如下目标函数.添加约束条件(第天需要的员工数量)和符号限制条件后，得到如下不正确的线性规划模型：为非负整数,.这里目标函数是专职员工的数量的5倍，问题是约束条件不能反映员工连续工作五天然后休息两天的事实.建模过程：这个邮局追求的目标是聘用尽可能少的专职员工.正确表述这个问题的关键是，定义的决策变量不应该是每天有多少人上班，而是一周中每天有多少人开始上班.定义决策变量：=第天开始上班员工的数量.例如，是星期一开始上班员工的数量

17、(这些人从星期一工作到星期五).那么邮局(专职员工的数量)=(星期一开始上班员工的数量)+(星期二开始上班员工的数量)+(星期日开始上班员工的数量).由于每个员工都只在一周的某一天开始上班，所以这个表达式不会重复计算员工.因此，追求聘用尽可能少的专职员工的目标函数为决策变量满足以下约束条件：在星期一上班员工的数量不少于17人：；在星期二上班员工的数量不少于13人：；在星期三上班员工的数量不少于15人：；在星期四上班员工的数量不少于19人：；在星期五上班员工的数量不少于14人：；在星期六上班员工的数量不少于16人：；在星期日上班员工的数量不少于11人：.及符号限制条件：为非负整数,.邮局追求聘用

18、尽可能少的专职员工的调度方案数学模型为 ,为非负整数,.这个模型的一个最优解为，最优值. 该模型存在另外一个问题：只有在周一、周二开始上班的员工才能在周末休息，而在其它时间开始上班的员工永远不会有在公休日与家人团聚的机会.显然这不公平合理.从该模型的解出发，我们可以设计出如下公平合理的以23周为一个轮转周期的员工调度方案：·第1-4周：在星期一开始上班·第5-8周：在星期二开始上班·第9-10周：在星期三开始上班·第11-16周：在星期四开始上班·第17-20周：在星期六开始上班·第21-23周：在星期日开始上班员工1将遵守这个调度方

19、案23周，员工2从第2周开始遵守这个调度方案23周(在星期一开始上班的时间为3周，在星期二开始上班的时间为4周，在星期日开始上班的时间为3周，在星期一开始上班的时间为1周).以这样的方式继续下去，就可以为每个员工制定一个23周调度方案.例如，员工13的调度方案如下：·第1-4周：在星期四开始上班·第5-8周：在星期六开始上班·第9-11周：在星期日开始上班·第12-15周：在星期一开始上班·第16-19周：在星期二开始上班·第20-21周：在星期三开始上班·第22-23周：在星期四开始上班本示例提醒我们，所建立的模型一定要考

20、虑合理性，符合实际.而本示例更符合实际的考虑是员工还有年休假.在邮局这个示例中，如果邮局可以同时使用专职员工和兼职员工来满足每天的需要，且在每一周，专职员工必须连续工作5天，每天工作8小时；兼职员工必须连续工作5天，每天工作4小时. 专职员工的工资是每小时15美元，而兼职员工的工资只有每小时10美元(没有附加福利).工会把每周的兼职劳动限制在25%，表述一个LP，使这个邮局每周的劳动力成本最少.比示例5的单阶段工作调度模型更复杂的是多阶段工作调度模型.类似的还有多阶段库存模型、多阶段财务管理(投资)模型等.示例5(指派问题) 某班准备从5名游泳队员中选4人，组队参加学校的m混合泳接力比赛.5名

21、队员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人的泳姿各不相同(容易想到的一个办法是穷举法，组成接力队的方案共有5!=120种.).设分别代表甲、乙、丙、丁和戊队员，分别代表蝶泳、仰泳、蛙泳和自由泳泳姿，表示队员的第种泳姿的百米平均成绩.定义决策决量：若选择队员参

22、加泳姿的比赛()，则，否则.该班追求的目标是接力队的成绩最好(只要对每一方案的成绩作比较，即可找出最优方案，但显然这不是解决问题的好办法.随着问题规模的变大，穷举法的计算量将是无法接受的).当队员入选泳姿时，表示他的成绩，否则，因此目标函数为.决策变量必须满足以下3个条件：(1) 每人最多只能入选4种泳姿之一，即，.(2)每种泳姿必须有1人而且只能有1人入选，即，.(3)取值受限或，.该班追求接力队成绩最好的数学模型为0-1规划：三、非线性规划(NLP)非线性规划广泛存在于科学与工程领域.1.非线性规划模型目标函数、约束函数中至少有一个非线性函数的最优化模型既是所谓的非线性规划模型.其中函数中

23、至少有一个为非线性函数.非线性规划有无约束问题与有约束问题之分.2.非线性规划的特点非线性规划的可行域及最优解的情况远比线性规划的可行域及最优解复杂的多：可能有最优解，也可能没有最优解；约束问题的最优解可能在可行域的内部，也可能在可行域的边界上.一些常用概念：等值面(线)函数值相等的决策变量曲面(曲线).上升/下降方向至少在局部范围内，函数值升的方向/函数值降的方向.梯度多元函数的“一阶导数”，由函数的偏导数组成的向量. 当梯度连续时，若，则必垂直于过点的等值面；梯度的方向是函数在点具有最大变化率的方向.方向导数函数在某方向上的变化率(下式中是方向上的单位向量).若，即，则方向是在点处的上升方

24、向；若，即，则方向是在点处的下降方向.海赛矩阵多元函数的“二阶导数”，由函数的二阶偏导数组成的矩阵.空间中由点和方向所确定的直线方程为.图2 直线的几何图示3.非线性规划的解法(1)非线性规划基本解法基本解法的迭代格式一般为, k = 0,1,.称为初始点，为处的搜索方向，为步长因子，满足，且仍在可行域内.判断是否为最优解.若是，则输出和；否则，继续迭代.由基本解法解出的一般是局部最优解.的确定方法直线搜索(一维优化问题的数值迭代方法)，.直线搜索方法有“精确的”对分法、黄金分割法、抛物线插值法和不精确的直线搜索技术.的确定方法各种优化方法求解无约束问题的基本方法按确定方法的不同，有使用导数的

25、最速下降法、Newton法、阻尼-Newton法、共轭梯度法、逆Newton法(DFP法、BFGS法)等，有不使用导数的单纯形替换法、步长加速法、Power法等，以及最小二乘法.最速下降法, k = 0,1,.特点：简单，存储量小，锯齿现象.线性收敛.Newton法：, k = 0,1,.特点：对目标函数的要求高，计算量、存储量大.二阶收敛.阻尼-Newton法：, k = 0,1,.特点：比Newton法相对有效的方法，计算量、存储量大.F-R共轭梯度法：, k = 0,1,，其中.特点：存储量小.是二次收敛算法.超线性收敛.DFP法：, k = 0,1,，其中.特点：是二次收敛算法.是拟N

26、ewton法.超线性收敛.单纯形替换法、步长加速法、Power法等适用于目标函数的导数不存在或导数过于复杂的情形.最小二乘法是求解最小二乘问题的特定解法.求解约束问题的基本方法有Z-容许方向法、梯度投影法、外点法(外部罚函数法)、内点法(内部罚函数法)、乘子法、线性化法、简约梯度法等.Z-容许方向法：利用线性规划得到搜索方向，然后再通过受限的直线搜索确定步长因子.梯度投影法：利用对梯度投影的方式得到搜索方向，然后再通过受限的直线搜索确定步长因子.外点法、内点法、乘子法：通过求解一系列的无约束问题解约束问题.而这一系列无约束问题的目标函数则是根据目标函数及约束函数，通过“惩罚”方式产生. (2)

27、非线性规划智能算法遗传算法、蚁群算法、粒子群算法、禁忌搜索算法.非线性规划的算法可在Matlab“优化”工具箱中寻找.参考书目 现代应用数学手册编委会.现代应用数学手册运筹学与最优化理论卷.北京：清华大学出版社,19984. 特殊的非线性规划问题及其解法(1)二次规划(QPP)Wolfe法.(2)数据拟合问题(最小二乘问题)最小二乘法5. 非线性规划建模实例示例1 某公司有6个建筑工地要开工，每个工地的位置(用平面坐标表示，距离单位：km)及水泥日用量(单位：(吨)由表1给出.目前有两个临时料场位于和，日储量各有20.请回答以下两个问题：(1)假设从料场到工地之间均有直线道路相连，试制定每天从

28、A、B两料场分别向各工地运送水泥的供应计划，使总的吨公里数最小.(2)为进一步减少吨公里数，打算舍弃目前的两个临时料场，修建两个新料场，日储量仍各为20，问建在何处最佳，可以节省多少吨公里数.表1 工地的位置及水泥日用量的数据料场1234561.258.750.55.7537.251.250.754.7556.57.753547611建模过程：公司追求的目标是每天从A、B两料场分别向各工地运送水泥总的吨公里数最小.为表述该问题，设工地的位置与水泥日用量分别为和()，料场位置及其日储量分别为和().定义决策变量(,)：料场向工地的运送量(,)，在问题(2)中，新建料场位置也是决策变量.公司追求总的吨公里数最小的目标函数为.决策变量(,)必须满足以下约束条件：(i)满足各工地的水泥日用量.(ii)各料场的运送量不能超过日储量.(iii)符号限制条件, ,.(1)公司追求总的吨公里数最小的数学模型是如下线性规划模型;, ,.这个模型的解，即料场A、B向6个工地运送水泥的计划为工地1 工地2 工地3 工地4 工地5 工地6料场A料场B3 5 0 7 0 10 0 4 0 6 1