最优化方法线性规划单纯形法.pptx
《最优化方法线性规划单纯形法.pptx》由会员分享,可在线阅读,更多相关《最优化方法线性规划单纯形法.pptx(77页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、线性规划线性规划:目标函数是线性的,约束条件是目标函数是线性的,约束条件是线性等式或不等式线性等式或不等式线性规划线性规划第1页/共77页线性规划的历史线性规划的历史渊源要追溯到渊源要追溯到Euler、Liebnitz、Lagrange等等George Dantzig,Von Neumann(Princeton)和和Leonid Kantorovich在在1940s创建了线性规划创建了线性规划1947年年,George Dantzig发明了单纯形法发明了单纯形法1979年年,L.Khachain找到了求解线性规划的找到了求解线性规划的一种有效方法一种有效方法(第一个多项式时间算法第一个多项式时
2、间算法椭球内椭球内点法点法)1984年年,Narendra Karmarkan发现了另一发现了另一种求解线性规划的有效方法,已证明是单纯形种求解线性规划的有效方法,已证明是单纯形法的强有力的竞争者法的强有力的竞争者(投影内点法投影内点法)现在求解大规模、退化问题最有效的是现在求解大规模、退化问题最有效的是原对原对偶内点法偶内点法第2页/共77页第3页/共77页第4页/共77页第5页/共77页 问题问题:确定食品数量,满足营养需求,花费最小?:确定食品数量,满足营养需求,花费最小?变量:变量:n种食品,种食品,m种营养成份;第种营养成份;第 j 种食品的单价种食品的单价每单位第每单位第 j 种食
3、品所含第种食品所含第 i 种营养的数量种营养的数量食用第食用第 j 种食品的数量种食品的数量为了健康,每天必须食用第为了健康,每天必须食用第i 种营养的数量种营养的数量 模型:模型:例例1.1.食谱问题食谱问题第6页/共77页例例2.运输问运输问题题产销产销平衡平衡/不平衡不平衡的运输问题的运输问题第7页/共77页例例3.其它应其它应用用数据包络分析数据包络分析(data envelope analysis,DEA)网络流问题网络流问题(Network flow)博弈论博弈论(game theory)等等第8页/共77页线性规划的一般形式线性规划的一般形式第9页/共77页线性规划的标准形线性规
4、划的标准形(分析、算法分析、算法)标准形的特征:标准形的特征:极小化极小化、等式约束等式约束、变量非负变量非负向量表示:向量表示:第10页/共77页一般形式一般形式 标准形标准形转化转化称称 松弛松弛(slack)/盈余盈余(surplus)变量;变量;自由自由变量变量第11页/共77页例例5.5.化成标准形化成标准形等等价价表表示示为为第12页/共77页定义:定义:给定含有给定含有n个变量,个变量,m个方程的线性方程组个方程的线性方程组Ax=b,设,设B是由是由A 的列组成的任一非奇异的列组成的任一非奇异mm子阵,则如果置子阵,则如果置x的所有与的所有与B无关的无关的n-m个分量为零后,所得
5、方程组的解是个分量为零后,所得方程组的解是Ax=b关于基关于基B的的基本解基本解(basic solution),称,称x中与基中与基B对应对应的分量为的分量为基变量基变量(basic variables)退化基本解:退化基本解:基本解中如果有一个或多个基变量的值为零基本解中如果有一个或多个基变量的值为零基本解与基变量基本解与基变量其中其中满秩假定:满秩假定:mn矩阵矩阵A满足满足mn,且,且A的行向量线性无关的行向量线性无关 在满秩假定下,方程组在满秩假定下,方程组Ax=b总有解,且至少有一个基本总有解,且至少有一个基本 解解第13页/共77页基本可行解基本可行解定义定义 称称 的非负基本解
6、是的非负基本解是标准形标准形的的基基本可行解本可行解(basic feasible solution);约束系统约束系统 第14页/共77页线性规划的基本定理线性规划的基本定理i)若标准型有可行解,则若标准型有可行解,则必有必有基本可行解;基本可行解;ii)若标准型有最优解,则若标准型有最优解,则必有必有最优最优基本可行解。基本可行解。考虑线性规划标准形,其中考虑线性规划标准形,其中A是秩为是秩为m的的mn阶阶矩阵,则以下结论成立:矩阵,则以下结论成立:基本可行解的个数基本可行解的个数不超过不超过第15页/共77页与凸性的关系与凸性的关系线性规划的基本定理线性规划的基本定理(标准形标准形)基本
7、可行解基本可行解线性方程组线性方程组的基本性质的基本性质代数理论代数理论(与与表述形式有关表述形式有关)设计算法设计算法极点极点凸集理论凸集理论几何理论几何理论(与表述形式与表述形式无关无关)直观理解直观理解第16页/共77页凸性凸性(凸集及性质凸集及性质)几何解释几何解释:连接集合中任两点的线段仍含在该集合中:连接集合中任两点的线段仍含在该集合中性质性质 定义定义 是凸集是凸集(convex set),如果对,如果对S中任意中任意 两两 点点 x,y 和和(0,1)中的任一数中的任一数 满足满足第17页/共77页一些重要的凸集一些重要的凸集有限个闭半空间的交集有限个闭半空间的交集多面集多面集
8、(polyhedral convex set):推推广广平面上:多边形平面上:多边形注:注:任一线性规划的可行集是任一线性规划的可行集是多面集多面集!超平面超平面(hyperplane):正正/负闭半空间:负闭半空间:第18页/共77页极点极点几何上几何上:极点即不能位于连接该集合中其它两点:极点即不能位于连接该集合中其它两点的开线段上的点的开线段上的点定义定义 称凸集称凸集C中的点中的点 x 是是C的极点,如果存在的极点,如果存在 C 中中的点的点 y,z 和某和某 ,有,有则必有则必有 y=z.第19页/共77页极点与基本可行解的等价性定理极点与基本可行解的等价性定理推论:推论:i)若若K
9、非空,则至少有一个极点非空,则至少有一个极点.ii)若线性规划有最优解,则必有一个极点是最优解若线性规划有最优解,则必有一个极点是最优解.iii)Ax=b对应的约束集对应的约束集K最多有有限个极点最多有有限个极点.考虑线性规划标准形,其中考虑线性规划标准形,其中A是秩为是秩为m的的mn矩阵,令矩阵,令则则x是是 K 的极点,的极点,当且仅当当且仅当x是线性规划的基本可行解是线性规划的基本可行解.(线性规划基本定理的几何形式)(线性规划基本定理的几何形式)第20页/共77页例例2.2.K有有2个极点个极点有有3个基本解,个基本解,2个个可行可行K 有有3个极点个极点有有3个基本解,个基本解,均可
10、行均可行例例1.1.第21页/共77页例例3.3.Subject to5个极点个极点极点极点第22页/共77页线性规划线性规划解的解的几何特征几何特征唯一唯一 解解(顶点顶点)!第23页/共77页线性规划解的线性规划解的几何特征几何特征无界无界:没有有限最优解:没有有限最优解不可行不可行:没有可行解:没有可行解无解无解可行集:可行集:多边形多边形(二维二维)多边集多边集(高维空间高维空间)给出给出有效的代数刻画有效的代数刻画和和严谨的几何描述严谨的几何描述,从理论上证,从理论上证实上述几何特征,并实上述几何特征,并寻求有效算法寻求有效算法有解:有解:唯一解唯一解/多个解多个解(整条边、面、甚至
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 方法 线性规划 单纯
限制150内