北邮最优化课件3线性规划性质.ppt

北邮最优化课件3线性规划性质.ppt

ID:56972658

大小:354.00 KB

页数:33页

时间:2020-07-25

北邮最优化课件3线性规划性质.ppt_第1页
北邮最优化课件3线性规划性质.ppt_第2页
北邮最优化课件3线性规划性质.ppt_第3页
北邮最优化课件3线性规划性质.ppt_第4页
北邮最优化课件3线性规划性质.ppt_第5页
资源描述:

《北邮最优化课件3线性规划性质.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、最优化理论与算法帅天平北京邮电大学数学系§3,线性规划的基本性质2021/9/201最优化理论TPSHUAI第二章线性规划的基本性质标准形式与图解法基本性质2021/9/202最优化理论TPSHUAI我每天要求一定量的两种维生素,Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量,目标以便以最低可能的花费购买这些食物,而满足最低限度的维生素需求量。2.线性规划-例子-食谱问题2021/9/203最优化理论TPSHU

2、AI令x表示要买的奶的量,y为要买的蛋的量。食谱问题可以写成如下的数学形式:Min3x+2.5ys.t.2x+4y403x+2y50x,y0.极小化目标函数可行区域(单纯形)可行解2.线性规划-例子-食谱问题2021/9/204最优化理论TPSHUAI1标准形式矩阵表示其中A是mn矩阵,c是n维行向量,b是m维列向量。注:为计算需要,一般假设b0.否则,可在方程两端乘以(-1)即可化为非负。2.线性规划-形式2021/9/205最优化理论TPSHUAI任意非标准形式均可化为标准形式,如引入松弛变量xn+1,xn+2,…xn+

3、m.2.线性规划-形式2021/9/206最优化理论TPSHUAI则有2.线性规划-形式2021/9/207最优化理论TPSHUAIMin3x+2.5ys.t.2x+4y403x+2y50x,y0.例如,考虑食谱问题2.图解法当自变量个数少于3时,可以用较简便的方法求解.2.线性规划-图解法2021/9/208最优化理论TPSHUAI30104020501020304050yx03x+2.5y2x+4y403x+2y50(15,2.5)可行区域的极点:(0,25)(15,2.5)最优解(20,0)Min3x+2.5ys.t.

4、2x+4y403x+2y50x,y0.2.线性规划-图解法2021/9/209最优化理论TPSHUAI3基本性质3.1线性规划的可行域定理2.2线性规划的可行域是凸集.3.2最优极点观察上例,最优解在极点(15,2.5)达到,我们有如下事实:线性规划若存在最优解,则最优解一定可在某极点上达到.2.线性规划-性质12021/9/2010最优化理论TPSHUAI考察线性规划的标准形式(2.2)根据表示定理,任意可行点x可表示为2.线性规划-性质22021/9/2011最优化理论TPSHUAI把x的表达式代入(2.2),得等价的线性规

5、划:2.线性规划-性质32021/9/2012最优化理论TPSHUAI于是,问题简化成在(2.6)中令显然,当时目标函数取极小值.2.线性规划-性质42021/9/2013最优化理论TPSHUAI因此极点x(p)是问题(2.2)的最优解.即(2.5)和(2.8)是(2.4)的最优解,此时2.线性规划-性质52021/9/2014最优化理论TPSHUAI2,若(2.2)存在有限最优解,则目标数的最优值可在某极点达到.定理2.3设线性规划(2.2)的可行域非空,则1,(2.2)存在最优解的充要条件是所有(j)cd非负,其中是可行域的极方向

6、d(j)2.线性规划-性质62021/9/2015最优化理论TPSHUAI4最优基本可行解前面讨论知道们最优解可在极点达到,而极点是一几何概念,下面从代数的角度来考虑。不失一般性,设rank(A)=m,A=[B,N],B是m阶可逆的.2.线性规划-性质72021/9/2016最优化理论TPSHUAI于是,Ax=b可写为于是特别的令Nx=0,则2.线性规划-性质82021/9/2017最优化理论TPSHUAI称为方程组Ax=b的一个基本解.定义2.6B称为基矩阵,的各分量称为基变量.xB基变量的全体称为一组基.的各分量称为非基变量.xN

7、为约束条件Ax=b,x0的一个基本可行解.B称为可行基矩阵称为一组可行基.2.线性规划-性质92021/9/2018最优化理论TPSHUAIBb>0,称基本可行解是非退化的,若-1若Bb0,-1且至少有一个分量为0,称基本可行解是退化的.2.线性规划-性质102021/9/2019最优化理论TPSHUAI2.线性规划-性质112021/9/2020最优化理论TPSHUAI2.线性规划-性质122021/9/2021最优化理论TPSHUAI2.线性规划-性质132021/9/2022最优化理论TPSHUAI容易知道,基矩阵的个数是有

8、限的,因此基本解从而基本可行解的个数也是有限的,不超过2.线性规划-性质142021/9/2023最优化理论TPSHUAI定理2.4令K={x

9、Ax=b,x0},A是m×n矩阵,r(A)=m则K的极点集与Ax=b,x

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。