您所在位置: 网站首页 / 第1章 线性规划及单纯形法(2).ppt / 文档详情
第1章 线性规划及单纯形法(2).ppt 立即下载
2024-08-16
约2.6千字
约36页
0
438KB
举报 版权申诉
预览加载中,请您耐心等待几秒...

第1章 线性规划及单纯形法(2).ppt

第1章线性规划及单纯形法(2).ppt

预览

免费试读已结束,剩余 31 页请下载文档后查看

10 金币

下载文档

如果您无法下载资料,请参考说明:

1、部分资料下载需要金币,请确保您的账户上有足够的金币

2、已购买过的文档,再次下载不重复扣费

3、资料包下载后请先用软件解压,在使用对应软件打开

第三节单纯形法原理(1)可行解:满足上述约束条件(1.7),(1.8)的解X=(x1,…,xn)T,称为线性规划问题的可行解。全部可行解的集合称为可行域。
(2)最优解:使目标函数(1.6)达到最大值的可行解称为最优解。
(3)基:设A为约束方程组(1.7)的m×n阶系数矩阵,(设n>m),其秩为m,B是矩阵A中的一个m×m阶的满秩子矩阵,称B是线性规划问题的一个基。不失一般性,设B中的每一个列向量Pj(j=1,…,m)称为基向量,与基向理Pj对应的变量xj称为基变量。线性规划中除基变量以外的变量称为非基变量。(4)基解:在约束方程组(1.7)中,令所有非基变量为xm+1=xm+2=…=xn=0零,以因为有|B|≠0,根据克莱姆法则,由m个约束方程可解出m个基变量的唯一解XB=(x1,…,xm)T。将这个解加上非基解中变量取0的值有X=(x1,x2,…,xm,0,0,…,0)T,称X为线性规划问题的基解。显然在基解中变量取非零值的个数不大于方程数m,故基解的总数不超过Cnm个。
(5)基可行解:满足变量非负约束条件(1.8)的基解称为基可行解。
(6)可行基:对应基可行解的基称为可行基。可行解线性规划的基矩阵、基变量、非基变量(四)求出下列线性规划问题的所有基解、基可行解基变量x1、x2、x3,非基变量x4、x5、x6基变量x1、x2、x4,非基变量x3、x5、x6基变量x1、x2、x5,非基变量x3、x4、x6基变量x1、x2、x6,非基变量x3、x4、x5基变量x2、x3、x4,非基变量x1、x5、x6基变量x1、x2、x3,非基变量x4、x5、x6基变量x1、x2、x3,非基变量x4、x5、x6例:设有一标准的线性规划问题的约束条件如下:
2x1+x2+x4=7
x2+x3=3
x1,x2,x3,x40
已知下列各点均满足以上的两个方程:
(1)(0,7,-4,0)T,(2)(2,3,0,0)T,(3)(1,0,3,5)T
(4)(2.5,2,1,0)T,(5)(0,3,0,4)T二、凸集及其顶点2顶点
凸集C中满足下述条件的点X称为顶点:如果C中不存在任何两个不同的点X1,X2,使X成为这两个点连线上的一个点。或者这样叙述:对任何X1C,X2C,不存在X=X1+(1-)X2C(01),则称X是凸集C的顶点。三、几个定理的证明将(1.9)代入(1.10)得:引理线性规划问题的可行解X=(x1,x2,…xn)为基可行解的充要条件是X的正分量所对应的系数列向量线性独立的。
证:(1)必要性(结论条件)
由基可行解的定义显然成立。
(2)充分性。(条件结论)若向量P1,P2,…,Pk线性独立,则必有k≤m.
当k=m时,它们恰好构成一个基,从而X=(x1,x2,…,xm,0,0,..,0)为相应的基可行解。
当K<m时,则一定可以从其余列向量中找出(m-k)个与P1,P2,…,Pk构成一个基,其对应的解恰为X,所以根据定义它是基可行解。定理2线性规划问题的基可行解X对应线性规划问题可行域(凸集)的顶点。
证:即要证明X是可行域顶点X是基可行解
反证法,即X不是可行域顶点X不是基可行解
(1)X不是基可行解X不是可行域顶点
不失一般性,设X的前m个分量为正,即:(1.12)式乘上一个不为零的数μ得:
1P1+2P2+…+mPm=0(1.13)
式(1.11)+(1.13)得:
(x1+1)P1+(x2+2)P2+…+(xm+m)Pm=b
式(1.11)-(1.13)得:
(x1-1)P1+(x2-2)P2+…+(xm-m)Pm=b
令:X(1)=[(x1+1),(x2+2),…,(xm+m),0,…,0]
X(2)=[(x1-1),(x2-2),…,(xm-m),0,…,0]
又可以这样来选取,使得对所有i=1,2,…,m有
x110由引X(1)C,X(2)C,又X=X(1)/2+X(2)/2
即X不是可行域的顶点。
(2)X不是可行域顶点X不是基可行解
不失一般性,设X=(x1,x2,…,xr,0,…,0)不是可行域的顶点,因而可以找到可行域内另外两个不同点Y和Z,
有X=Y+(1-)Z(0<<1),或可写成
xj=yj+(1-)zj(0<<1;j=1,…,n)
因>0,1->0,故当xj=0时,必有yj=zj=0
因有故有定理3若线性规划问题有最优解,一定存在一个基可行解是最优解。
证设X(0)=(x10,x20,…,xn0)是线性规划的一个最优解,因CX(0)为目标函数的最大值,故有四、单纯形法迭代原理2从一个基可行解转换为相邻的基可行解。
定义:两个基可行解称为相邻的,如果它们之间变换且仅变换一个基变量
查看更多
单篇购买
VIP会员(1亿+VIP文档免费下)

扫码即表示接受《下载须知》

第1章 线性规划及单纯形法(2)

文档大小:438KB

限时特价:扫码查看

• 请登录后再进行扫码购买
• 使用微信/支付宝扫码注册及付费下载,详阅 用户协议 隐私政策
• 如已在其他页面进行付款,请刷新当前页面重试
• 付费购买成功后,此文档可永久免费下载
全场最划算
12个月
199.0
¥360.0
限时特惠
3个月
69.9
¥90.0
新人专享
1个月
19.9
¥30.0
24个月
398.0
¥720.0
6个月会员
139.9
¥180.0

6亿VIP文档任选,共次下载特权。

已优惠

微信/支付宝扫码完成支付,可开具发票

VIP尽享专属权益

VIP文档免费下载

赠送VIP文档免费下载次数

阅读免打扰

去除文档详情页间广告

专属身份标识

尊贵的VIP专属身份标识

高级客服

一对一高级客服服务

多端互通

电脑端/手机端权益通用