emp_lp_fundenmental_2016_spring.

第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础线性规划：基本理论与方法刘红英北航数学与系统科学学院第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础目标函数是线性的，约束条件是线性等式或不等式线性规划第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础◎问题：确定食品数量，满足营养需求，花费最小？◎变量：n种食品，m种营养成份；－第j种食品的单价－每单位第j种食品所含第i种营养的数量－第j种食品的数量－为了健康，每天必须食用第i种营养的数量◎模型：2.1.1问题举例例1.配餐问题第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础例4.其它应用•博弈论(gametheory)等(习题2.26,2.27)•网络流问题(networkflow,3.1-3.2节)•整数线性规划(3.3-3.4节)•数据包络分析(dataenvelopeanalysis,DEA,Charnes&Copper，1986)例2.目标函数中含绝对值的问题(习题2.2)例3.逐段线性凸函数(习题2.3)是一种对多投入/多产出的多个决策单元的效率进行评价的方法，广泛应用于业绩评价，如快餐分销店、银行支行、诊所、小学或者图书馆等第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础线性规划解的几何特征惟一解(顶点)！第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础无(下)界没有有限解(-1,-1)一条边(1,0)一条边(0,1)惟一的顶点(1,1)解的几何特征(0,0)(x1,0),x1≥0(0,x2),x2∈[0,1]Tc*()Tx第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础•无界：没有有限最优解(极小化时表示无下界，极大化时无上界)•不可行：没有可行解无解•有解：惟一解或多个解(整条边、面、甚至整个可行集)有顶点解线性规划解的几何特征可行集：多边形(二维)→多面集(高维空间)给出顶点有效的代数刻画和严谨的几何描述，从理论上证实上述几何特征，并寻求有效算法第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础线性规划的一般形式其中c是n维向量，是m维行向量，是实数，这些均是给定的数据；是变量.第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础2.1.2标准形(便于分析分析和设计算法)*****标准形的特征：极小化、等式约束、变量非负其中给定，变量是向量表示：其中给定，变量是第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础例4.化成标准形等价表示为第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础一般形式标准形转化称松弛(slack)/盈余(surplus)变量第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础定义设B是A的m个线性无关列组成的矩阵，置其余列所对应的变量为零，称所得方程组的解是Ax=b的基本解(basicsolution);非负基本解是标准形问题的基本可行解(basicfeasiblesolution)；称B是基(basis)；称与B的列对应的变量为基变量(basicvariables)2.1.3基本可行解(*****)其中满秩假定：mn，且A的行向量线性无关例第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础基本可行解的个数不超过◆退化基本可行解：某个或某些基变量取零的基本可行解！问题：基本可行解与基的对应关系？(见习题2.5)事实：设x是线性规划的可行解，则x是线性规划的基本可行解当且仅当它的正分量对应的列线性无关.例.基本可行解及几何意义第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础基本可行解的存在性与基本定理(*****)定理(线性规划基本定理)考虑线性规划标准形，其中A是秩为m的m×n矩阵.若问题有解，则必有某个基本可行解是最优解.定理(BFS的存在性)考虑LP标准形，其中A是秩为m的m×n矩阵.若问题有可行解，则必存在基本可行解.第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础“Youdon‘tunderstandanythinguntilyoulearnitmorethanoneway.”MarvinMinsky(人工智能领域的专家)2.1.5几何直观线性规划的基本定理(标准形)基本可行解线性方程组的基本性质代数理论(与表述形式有关)设计算法极点凸集理论几何理论(与表述形式无关)直观理解第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础凸集的定义及性质几何解释：连接集合中任两点的线段仍含在该集合中性质称集合C是锥(cone)，如果蕴含着对所有有.若锥C还是凸的，称为凸锥(convexcone).称中的集合C是凸的(convex)，如果任给个x,y及每个，点.第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础一些重要的凸集有限个闭半空间的交集多面集(polyhedralset):推广平面上：多边形注：任一线性规划的可行集是多面集！超平面(hyperplane):正/负闭半空间：给定第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础极点几何上：极点即不能位于连接该集合中其它两点的开线段上的点定义称凸集C中的点x是C的极点，如果存在C中的点y,z和某，有则必有y=z.(1)xyz(0,1)第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础定理(极点与基本可行解的等价性)推论：(i)若C非空，则至少有一个极点.(ii)若线性规划有解，则必有一个极点是最优解.(iii)C的极点集是有限集.考虑线性规划标准形，其中A是秩为m的m×n矩阵，令,则x是C的极点当且仅当x是系统，的基本可行解(非负基本解).(iv)C中的点x是极点当且仅当它的正分量对应的列线性无关.{:,}R0nCxAxbx第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础C有2个极点有3个基本解，2个可行C有3个极点有3个基本解，均可行例2.C例1.C第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础例3.subjectto5个极点x*=(3/2,1/2)T－极点问题/作业(习题2.6)证明这两个集合的极点是一一对应的！考虑集合第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础线性规划问题解的几种情况第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础2.2单纯形法•适用形式：标准形(基本可行解等价于极点)•理论基础：线性规划的基本定理！•基本思想：从约束集的某个极点/BFS开始，依次移动到相邻极点/BFS，直到找出最优解，或判断问题无界.•初始化：如何找到一个BFS？•判断准则：何时最优？何时无界？•迭代规则：如何从一个极点/BFS迭代到相邻极点/BFS？第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础基本解基变量非基变量即可，次序可以打乱！只要有m个单位列e1,e2,…,em2.1.1既约/相对费用系数－规范形不妨设得到了基变量为的BFS，对应基为B，则有1mx,,x不妨设，则有1mBa,,a][第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础即可，次序可以打乱！只要有m个单位列e1,e2,…,em◎规范形的系数的一种解释规范形第j列的系数是用当前基表示aj时的系数！不妨设，则有1mBa,,a][11122jjjjjmjmyBaayayaya第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础将Ax=b的任一解x用非基变量表示为既约费用系数/相对费用系数(*****)◎相对费用系数的经济解释！(合成费用、相对费用)第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础◎定理(最优性判别)在某基本可行解处，如果对所有j有,0jjjcrz则这个基本可行解是最优的.◎既约线性规划◎假设令第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础2.2.2基本可行解的改进定理(BFS的提高)给定目标值为z0的非退化基本可行解，且假定存在q使得rq0，则(i)如果用aq替换基中某列得到了新的BFS，则新BFS处的目标值比z0严格小.(ii)如果任何替换都产生不了新的BFS(yq≤0)，则问题无界.第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础◎(p,q)转轴后，新规范形的系数转轴公式－转轴元(pivotelement)'qjjpjpqrrryy◎(p,q)转轴后，新的既约费用系数第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础2.2.3.计算过程－单纯形法单纯形表：BFS对应规范形的表格＋既约费用系数和BFS目标值的相反数单纯形表可以提供计算需要的所有信息！第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础如何得到第一张单纯形表◎用转轴运算(初等行变换)将最后一行与基变量对应的元素化为零，即得第一张单纯形表！◎初始表格：BFS对应规范形的表格＋(,0)第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础例1.化标准形转轴得标准形的初始表格/第一张单纯形表第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础转轴0↓-2↓-4↓-27/5转轴第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础最优解：最优值：原问题的极大值：第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础单纯形法的步骤步0形成与初始BFS对应的初始表格.通过行变换求出第一张单纯形表.步1若对每个j都有，停；当前BFS是最优的.步2选取q满足步4以为转轴元进行转轴，更新单纯形表，返回步1.转轴规则：进基变量－最小既约费用系数规则；出基变量－最小指标规则！步3若≤0,停，问题无界；否则，选p满足第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础2.2.4单纯形法的收敛性◎非退化的线性规划问题任意一个基本可行解都非退化的线性规划问题.对非退化的线性规划问题，从任一基本可行解出发，利用单纯形法可在有限步内得到最优解或判断问题无界.◎定理(收敛性)第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础退化的基本可行解→退化的线性规划问题(几何解释)对于三维问题(非标准形，如图)，若极点是三个平面的交点，是非退化的；否则，是退化的。对于标准形而言，当BFS仅对应一个基时，是非退化的；当BFS对应多个基时，是退化的，见习题2.5，2.21;x=(0,0,1)第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础021-3020010-1031-100410000200300010-1102010-1000100-50-40-100-6非退化转轴退化的基本可行解→退化转轴→循环基本可行解是退化的当且仅当单纯形表最后一列有一个或者多个零！退化转轴！退化基本可行解退化转轴指转轴后目标函数的值没有发生变化！第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础◎转轴规则(进基出基变量的选取规则)⊙进基变量：最小既约费用系数规则⊙出基变量：最小指标规则◎循环的例子Beale的例子习题2.21退化(degenerate)→循环(cycling)◎退化问题⊙单纯形法可能出现循环(从某张单纯形表开始，若干次转轴迭代后又返回到该单纯形表的一串转轴)！第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础x=(0,0,1,0,0,0,0)TB=(a1,a2,a3)B=(a4,a2,a3)B=(a4,a5,a3)第2章线性规划:基本理论与方法LHY-SMSS-BUAA数学规划基础B=(a6,a5,a