最优化方法论(运筹)

最优化方法论(运筹)运筹帷幄，决胜千里史记《张良传》1．了解线性规划解的基本特征，掌握线性规划的标准形；2．理解单纯形法的基本思想；3．熟练掌握单纯形法，并能熟练运用Matlab求解线性规划；重点：单纯形法。第一章要求第一章线性规划与单纯形法1.1线性规划问题及其一般数学模型1.1.1线性规划问题举例例1、生产计划问题（Max,）设x1,x2分别代表I、II两种产品的产量，.14)(max,2,4:0,12416482..32)(max:2121212121xfxxxxBxAxxxtsxxxfOBJ最优解产量不允许为负值约束原料约束原料设备约束例2、配料问题（min,)原料甲原料乙最低含量VA0.50.52VB11.00.33VB20.20.61.2VD0.50.22单价0.30.5设x1,x2分别代表每粒胶丸中甲、乙两种原料的用量一个制造厂要把若干单位的产品从两个仓库2,1;iAi发送到零售点4,3,2,1;jBj，仓库iA能供应的产品数量为2,1;iai，零售点jB所需的产品的数量为4,3,2,1;jbj。假设供给总量和需求总量相等，且已知从仓库iA运一个单位产品往jB的运价为ijc。问应如何组织运输才能使总运费最小？运输问题问题分析:可控因素：从仓库iA运往jB的产品数量设为4,3,2,1,2,1;jixij目标：总运费最小费用函数2141ijijijxc受控条件：从仓库运出总量不超过可用总量，运入零售点的数量不低于需求量。由于总供给量等于总需求量，所以都是等号。即2,1;4321iaxxxxiiiii4,3,2,1;21jbxxjjj蕴含约束：数量非负4,3,2,1,2,1;0jixij模型:min2141ijijijxc2,1;4321iaxxxxiiiiis.t.4,3,2,1;21jbxxjjj4,3,2,1,2,1;0jixij♂返回1.1.2线性规划数学模型的一般表示方式技术系数右端项价值系数线性规划问题的规模约束行数变量个数:;:;::;:;:0,,,),(),(),(..)(max(min)21221122222121112121112211ijjjnmnmnmmnnnnnnabcmnmnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf1、和式njxmibxatsxcxfjinjjijnjjj,,2,1,0,,2,1,..)(min112、向量式3、矩阵式概念可行解（或可行点）：满足所有约束条件的向量),,(21nxxxx可行集（或可行域）：所有的可行解的全体}0,{xbAxxD最优解：在可行域中目标函数值最大（或最小）的可行解，最优解的全体称为最优解集合DyycxcDxO,{}最优值：最优解的目标函数值Oxxcv,图解法对于只有两个变量的线性规划问题可以用图解法求解：变量用直角坐标系中的点表示约束条件用坐标系中的半空间或直线的交表示，可行区域是一个凸多面体目标函数用一组等值线表示，沿着增加或减少的方向移动，与可行域最后的交点就是最优解。1.1.3线性规划的图解法1187654322x1876543O109x2ABCEDFGH123f(x)=0f(x)=12.36)(max,6,2:0,78102..46)(max21212212121xfxxxxxxxxxtsxxxf最优解1187654322x1876543O109x2ABCEDFGH123说明：对一般的线性规划问题而言，求解结果可以是有唯一最优解、无穷多最优解、无界解或者无可行解.注释可能出现的情况：•可行域是空集•可行域无界无最优解•最优解存在且唯一，则一定在顶点上达到•最优解存在且不唯一，一定存在顶点是最优解♂返回问题1．可行域顶点的个数是否有限？2．最优解是否一定在可行域顶点上达到？3．如何找到顶点？4．如何从一个顶点转移到另一个顶点♂返回线性规划标准型问题解的关系约束方程的解空间基础解可行解非可行解基础可行解退化解总结：线性规划求解的几个特点：•线性规划问题的可行解的集合是凸集•线性规划问题的基础可行解一般都对应于凸集的极点•凸集的极点的个数是有限的•最优解只可能在凸集的极点上，而不可能发生在凸集的内部1.2线性规划问题的单纯形法1.2.1线性规划问题的标准形式为了使线性规划问题的解法标准，就要把一般形式化为标准形式njxmibxatsxczjinjjijnjjj,,2,1,0,,2,1,..min11变换的方法•目标函数为max型，价值系数一律反号。令f(x)=-f(x)=-CX,有maxf(x)=-min[-f(x)]=-minf(x)•第i个约束的bi为负值，则该行左右两端系数同时反号，同时不等号也要反向•第i个约束为型，在不等式左边增加一个非负的变量xn+i，称为松弛变量；同时令cn+i=0•第i个约束为型，在不等式左边减去一个非负的变量xn+i，称为剩余变量；同时令cn+i=0•若xj0，令xj=-xj，代入非标准型，则有xj0•若xj不限，令xj=xj-xj，xj0，xj0，代入非标准型例2.1把线性规划0,32,47,632..max121212121xxxxxxxtsxxz化为标准形.练习：0,,20040065300432..423)(max:213321321321321xxxxxxxxxxxxtsxxxxf不限原非标准型0,,,,,,2004006653004432..0004423)(min:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf标准型关于标准型解的若干基本概念：•标准型中有n个变量，m个约束条件•“基”的概念–在标准型中，技术系数矩阵有n列，即A=(P1,P2,…,Pn)–A中线性独立的m列，构成该标准型的一个基，即B=(P1,P2,…,Pm)，|B|0–P1,P2,…,Pm称为基向量–与基向量对应的变量称为基变量，记为XB=(x1,x2,…,xm)T，其余的变量称为非基变量，记为XN=(xm+1,xm+2,…,xn)T，故有X=XB+XN–最多有个基mnC1.2.2单纯形法的基本思路确定初始基础可行解求最优解的目标函数值确定改善方向求新的基础可行解检查是否为最优解？是否1.2.3单纯形表及其格式ABCT0中心部分右列底行右下端(底线)称为例试列出下面线性规划问题的初始单纯形表.0,,,,53,642..423min43213214314321xxxxxxxxxxtsxxxxz20-416-113051-32401.2.4标准型的单纯形算法1找初始基础可行基–对于(min,)，松弛变量对应的列构成一个单位阵–若有bi0，则单位阵也不能构成一个可行基2检验当前基础可行解是否为最优解–所有检验数cjzj0，则为最优解，否则3确定改善方向–从(cjzj)0中找最小者，选中者称为进基变量，xj*–第j*列称为主列4确定进基变量的最大值和离基变量–最小比例原则(1.2.4)0min**ijijiiaab1.2.4标准型的单纯型算法4确定进基变量的最大值和离基变量–设第i*行使最小，则第i*行对应的基变量称为出变量，第i*行称为主行5迭代过程–主行i*行与主列j*相交的元素ai*j*称为主元，迭代以主元为中心进行–迭代的实质是线性变换，即要将主元ai*j*变为1，主列上其它元素变为0，变换步骤如下：(1)变换主行nmjaaajijiji,,2,1****1.2.4标准型的单纯型算法5迭代过程(2)变换主列除主元保留为1，其余都置0(3)变换非主行、主列元素aij(包括bi)四角算法公式：数据表示当前单纯形表中的的数据表示上一个单纯形表中,(1.2.5b)(1.2.5a)********ijijijiijjiijijjiijiiiaabaaaaaaabbb1.2.4标准型的单纯形法5、迭代过程(4)变换CB，XB(5)计算目标函数、机会成本zj和检验数cjzj6、返回步骤2aijai*jaij*ai*j*主行主列主元四角算法图示小结•单纯形法的运算：1.底线以上部分进行行变换；2.底线以上某一行乘一非零常数；3.底线以上的行进行倍加运算；4.把底线以上行乘常数后加至底行（包括右下端）上。最优解得到时，单纯形表的特点：1.中心部位具有单位子块；2.右列元素非负；3.底行相应于单位子块位置的元素为0；4.底行其他元素非负。表例题中单纯型表的迭代过程.0)6,0,5,0();(,,3142等行变换化为素通过初应于单位子块位置的元基本可行解；将底行相为非基变量为自由变量为基变量；Txxxx变量进基选为将1x042-315031-161-402-90270-105031-161-402单位子块相应基可行解的目标函数值为9行变换变为单位子块将相应的列通过初等21570081/211031/2-201.21)0,0,8,3(；最优值为最优解为T例2.20,,153,102,2..32min2121212121xxxxxxxxtsxxz1.3人工变量的引入及其解法当约束条件为“”型，引入剩余变量和人工变量•由于所添加的剩余变量的技术系数为1，不能作为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量•由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定•两种方法–大M法–二阶段法大M法的求解过程例2.3大M法的一些说明–大M法实质上与原单纯型法一样，M可看成一个很大的常数–人工变量被迭代出去后一般就不会再成为基变量–当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解–大M法手算很不方便–因此提出了二阶段法•计算机中常用大M法•二阶段法手算可能容易1.5单纯型法的一些具体问题1.5.1关于无界解问题–可行区域不闭合(约束条件有问题)–单纯型表中入变量xj*对应的列中所有0a*ij0,501002..)(max1.5.121212121xxxxxxtsxxxf例f(x)=x1+x2x1x2505050100x1-x2=50-2x1+x2=100表1.5.1例1.5.1的单纯型表及其迭代过程x1x2x3x4序号CBXBb1100bi/aij*0x310021100x450(1)101(50)OBJ=00000I初始解cj-zj11000x32001121x1501101OBJ=50101IIcj-zj0201.5.2关于退化问题–退化问题的原因很复杂，当原问题存在平衡约束时–当单纯型表中同时有多个基变量可选作出变量时–退化的严重性在于可能导致死循环，克服死循环的方法有“字典序”法0,060240..43)(max1.5.22121212121xxxxxxxxtsxxxf例x1x2x3x4序号CBXBb3400bi/aij*0x340(2)10(20)0x460001(20)3x10100OBJ=03300IIcj-zj07004x22011/200x4003/213x12011/20OBJ=14033.50