第四讲 线性规划与非线性规划

运筹学——线性规划与非线性规划线性规划与非线性规划是运筹学的一个分支.运筹学研究什么呢?运筹学是研究“如何做出正确决策或选择，以达到最好结果”的一门数学学科.有一句成语形象地说明了运筹学的特点：运筹帷幄，决胜千里.数学因实际的需要而产生，数学的很多重大发现也因实际的需要而出现.数学建模竞赛既因实际的重要需要而在世界范围内(在我国近十几年)各大学蓬勃开展.没有受到条条框框制约、富有聪明才智的大学生们，在每次竞赛中都能对实际中的一些重要问题与难题给出富有新鲜创意的解决办法，往往因此产生重大的社会效益和经济效益.建模竞赛就是知识的“强行军”.竞赛会极大地激发学生们的创造性思维，是对学生们思考能力和动手能力的考验.竞赛能让学生们切身感受到学习各科知识的必要性、重要性，成为学生们认真学习的推动力.数学建模会涉及数学的众多学科：微分方程，运筹学，概率统计，图论，层次分析，变分法……，要求建模者有较高的数学素养，有综合应用已学到的数学方法和思维对问题进行分析、抽象及简化的能力.数学建模既是建立实际问题的数学模型.一、最优化模型数学建模的目的是使决策人的“利益”最大化，因此而建立的数学模型即所谓的最优化模型.决策人在作决策时要有“科学观”，为实现目标(“利益”最大化)应进行“科学决策”.最优化模型正是为实现科学决策而建立的数学模型，是科学决策的科学体现.科学决策的目的是要对为实现目标而提出的设计和操作最佳化，最终实现决策人的“利益”最大化.一个最优化模型包括决策变量、目标函数和约束条件，它将“说明”决策变量在满足约束条件的前提下应使目标函数值最优化(最大或最小).决策变量是指影响并决定目标实现的变量，其变化范围一般是可控制的.目标函数是指根据决策变量建立的目标的函数表达式.约束条件是指决策变量所受的限制(用等式、不等式的函数方程表示).人们建立最优化模型的目的是，希望通过科学的计算方法(称为最优化方法)找出使目标函数值最优(最大或最小)的决策变量的值(称为最优决策).实际问题的7步建模过程：第1步：表述问题.说明目标及各种因素.第2步：分析数据或采集(或收集)并分析数据.第3步：建立数学模型.第4步：对模型求解.即寻找最优决策.第5步：检验、评价模型.如果与实际情况(或实际数据)吻合，则转到第7步，否则转到第6步.第6步：修改或矫正模型，并返回到第1步、第2步或第3步.第7步：模型应用，提出合理化建议.最优化数学模型的一般形式为.,,1,0),,,(,,,1,0),,,(..);,,,(max212121min)(mpixxxgpixxxgtsxxxfzninin或(1.1)其中，),,1(njxj是决策变量；),,,(21nxxxfz是目标函数；),,1(0),,,(21pixxxgni和),,1(0),,,(21mpixxxgni是约束条件，前者称为等式约束，后者称为不等式约束.不带约束条件的(1)式是无约束问题的模型.由满足所有约束条件的决策向量Tnxxxx),,,(21组成的集合称为可行域，通常记为D.求解(1)是指，寻找DxxxxTn),,,(**2*1*使),,,(**2*1nxxxfz为目标函数f在可行域D上的最小值(或最大值).*x称为最优解，),,,(**2*1nxxxf称为最优值.最优解有严格与非严格和全局与局部之分.优化模型的最优解是指全局最优解.严格极小点严格极小点局部全局非严格极小点非严格极小点图1一维函数的最优解图示这里指出：最优化方法解出的多是优化模型的局部最优解.由于最优化方法多为迭代法，所以取不同的初始点一般会得到一个或多个局部最优解，然后再从这些局部最优解中找出“全局”最优解.二、线性规划(LP)线性规划在银行、教育、林业、石油、运输……等各种行业以及科学的各个领域中有着广泛的应用.1.线性规划模型目标函数、约束函数均为线性函数的最优化模型既是所谓的线性规划模型.(1)标准形式.,,1,0,,,1,..;min22112211max)(njxmibxaxaxatsxcxcxczjininiinn或(2.1)这里，约束ininiibxaxaxa2211),,1(mi是对决策变量的主要约束，称为主约束，而约束),,1(0njxj(),,1(njxj称为非负变量)是对决策变量的符号约束；(1,,)jbim是主约束的右端常数项(通常不妨设为非负数)；),,1(njcj称为价值系数.(2.1)式可以写成如下矩阵形式.0,..;minmax)(xbxAtsxczT或(2.2)其中，mnnmnmmnnbbbbxxxxccccaaaaaaaaaA212121212222111211,,,.Tnxxxx),,,(21——决策向量，Tmbbb),,(1——主约束右端常数向量，1(,,)Tnccc——价值向量.(2)一般形式.,,1,,,,1,0,,,1,,,,1,,,,1,..;min2211221122112211max)(nqjxqjxmuibxaxaxaupibxaxaxapibxaxaxatsxcxcxczjjininiiininiiininiinn任意或(2.3)这里，约束),,1(2211pibxaxaxaininii、ininiibxaxaxa2211),,1(upi和),,1(2211muibxaxaxaininii是主约束，而约束),,1(0qjxj和jx任意),,1(nqj是符号约束，其中jx),,1(nqj称为自由变量.一般形式可以(通过如下办法)转化为标准形式.(i)将不等式约束转化为等式约束引入剩余变量0is，将不等式约束ininiibxaxaxa2211改写为iininiibsxaxaxa2211，upi,,1.(2.4)引入松弛变量0ie，将不等式约束ininiibxaxaxa2211改写为iininiibexaxaxa2211，mui,,1.(2.5)(ii)去除自由变量去掉自由变量),,1(nqjxj有两种办法：①用非负变量的差表示自由变量设jjjxxx，(2.6)其中0jx，0jx，代入到目标函数和其它约束中便可去掉jx.②取一个包含jx的等式约束(如果有的话)，比如：11iijjinniaxaxaxb，由此解出11iiinjnijijijbaaxxxaaa，(2.7)代入到目标函数和其它约束函数中便可去掉jx.第一种方法将增加变量的数目，导致问题的维数增大.第二种方法正好相反.用(2.4)、(2.5)两式替换(2.3)式中相应的不等式约束，将(2.6)式或(2.7)式代入目标函数和其它约束函数中，去掉目标函数与主约束中的所有自由变量，最后将),,1(0upisi、),,1(0muiei和),,1(0,0nqjxxjj加入(2.3)式的符号约束中，(2.3)式就此转化为标准形式的线性规划.,,1,0;,,1,0;,,1,0,0;,,1,0,,,1,,,,1,,,,1,..;min11111111111111111111max)(muieupisnqjxxqjxmuibexxaxxaxaxaupibsxxaxxaxaxapibxxaxxaxaxatsxxcxxcxcxcziijjjiinninqqiqqiqiiinninqqiqqiqiinninqqiqqiqinnnqqqqq）（）（）（）（）（）（）（）（或，一般形式与其标准形式问题的求解等价，因为这两个问题的可行解一一对应，目标函数值对应相等.所以如果这两个问题之一有最优解，那么另一个也必有最优解，且最优值相等.2.线性规划的特点(1)线性规划的可行域是凸集：凸多边形、凸多面体或空集.凸集非凸集凸多边形凸多面体(2)目标函数的等值面(或等值线)是平行的(超)平面(或直线).(3)如果线性规划有最优解，那么可行域的某个顶点必是最优解.(4)求解线性规划将出现下列4种情况之一.情况1：有唯一(最优)解.情况2：有无穷多(最优)解.情况3：解无界.情况4：无解.有唯一解有无穷多解有无界解无解3.一般线性规划的解法线性规划的解法有Dantzig单纯形法，大M法，对偶单纯形法，Karmarkar法，列生成法，目标规划，分解算法等.软件中多为Dantzig单纯形法.参考书目：薛嘉庆.线性规划.北京：高等教育出版社,1989刁在筠郑汉鼑等.运筹学.北京：高等教育出版社,20014.特殊的线性规划当所有决策变量都取整数时，称为整数规划(IP).当所有决策变量只取0或1时，称为0-1规划.当只有部分决策变量取整数时，称为混合整数规划(混合IP).解整数规划的方法主要有穷举法(对决策变量过多的问题不适用)、分枝定界法和割平面法.分枝定界法比较常用.解小规模0-1规划的常用方法——隐枚举法.分枝定界法也适用于求解混合整数规划.参考书目：刁在筠郑汉鼑等.运筹学.北京：高等教育出版社,2001胡运权.运筹学基础及应用.北京：高等教育出版社,20045.特殊的线性规划问题及其解法(1)运输问题运输问题用“运输”单纯形法求解.(2)转运问题转运问题可以化为运输问题，所以也用“运输”单纯形法求解.(3)指派问题指派问题是特殊的0-1规划，常用匈牙利法求解.线性规划的算法可在Matlab“优化”工具箱中寻找.6.线性规划建模实例在一个线性规划模型中，(1)决策变量应当完全描述要做出的决策.(2)决策者都希望由决策变量表示的目标函数最大化(通常为收入或利润)或最小化(通常为成本).目标函数中的系数反映的是决策变量对目标函数的单位贡献.(3)主约束条件中决策变量的系数称为“技术”系数，这是因为技术系数经常影响用于“生产”不同“产品”的技术.右端项常表示可用资源的数量.示例1一家汽车公司生产轿车和卡车.每辆车都必须经过车身装配车间和喷漆车间处理.车身装配车间如果只装配轿车，每天可装配50辆；如果只装配卡车，每天可装配50辆.喷漆车间如果只喷轿车，每天可喷60辆；如果只喷卡车，每天可喷40辆.每辆轿车的利润是1600元，每辆卡车的利润是2400元.公司的生产计划部门须制定一天的产量计划以使公司的利润最大化.建模过程：公司追求的目标是其利润的最大化，生产计划部门为此要决定每一种车型的产量，所以定义两个决策变量：1x每天生产的轿车数量，2x每天生产的卡车数量.公司每天的利润为2124001600xx，因此该公司追求利润最大化即为2124001600maxxxz.按题意，决策变量须满足以下3个条件(如果把每天的时间设为1，那么每天的工作时间应该小于等于1.)：(1)装配车间每天处理一辆轿车和一辆卡车的时间均为501，所以处理1x辆轿车和2x辆卡车的时间应满足150150121xx.(2)喷漆车间每天处理一辆轿车的时间为601，处理一辆卡车的时间为401，所以处理1x辆轿车和2x辆卡车的时间应满足140160121xx.(3)非负限制jx为负整数,2,1j.该汽车公司追求利润最大化的数学模型为如下线性规划.2,1,,1401601,1501501..24001600max212121jxxxxxtsxxzj为非负整数；示例2(饮食问题)有一个美国人的饮食方案要求他吃的所有食物都来自四个“基本