- 1、本文档共28页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第1章线性规划与单纯形法第2节
第1章 线性规划与单纯形法 第2节线性规划问题的几何意义 2.1 基本概念 2.2 几个定理 2.1 基本概念 凸集 凸组合 顶点 1.凸集 设K是n维欧氏空间的一点集,若任意两点X(1)∈K,X(2)∈K的连线上的所有点αX(1)+(1-α)X(2)∈K,(0≤α≤1);则称K为凸集。 图1-7 实心圆,实心球体,实心立方体等都是凸集,圆环不是凸集。从直观上讲,凸集没有凹入部分,其内部没有空洞。图1-7中的(a)(b)是凸集,(c)不是凸集。 图1-2中的阴影部分 是凸集。 任何两个凸集的交集是凸集,见图1-7(d) 2. 凸组合 设X(1),X(2),…,X(k)是n维欧氏空间E中的k个点。若存在μ1,μ2,…,μk,且0≤μi≤1, i=1,2,…,k; 使X=μ1X(1)+μ2X(2)+…+μkX(k) 则称X为X(1),X(2),…,X(k)的凸组合。(当0<μi<1时,称为严格凸组合). 3. 顶点 设K是凸集,X∈K;若X不能用不同的两点X(1)∈K和X(2)∈K的线性组合表示为 X=αX(1)+(1-α)X(2),(0<α<1) 则称X为K的一个顶点(或极点)。 图中0,Q1,2,3,4都是顶点。 2.2 几个定理 定理1 若线性规划问题存在可行域,则其可行域 是凸集 证:为了证明满足线性规划问题的约束条件 的所有点(可行解)组成的集合是凸集, 只要证明D中任意两点连线上的点必然在D内即可。 设 是D内的任意两点;X(1)≠X(2)。 引理 1 线性规划问题的可行解X=(x1,x2,…,xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。 定理2 线性规划问题的基可行解X对应于可行 域D的顶点。 证:不失一般性,假设可行解X的前m个分量为正。故 现在分两步来讨论,分别用反证法。 (1-8) 若X不是基可行解,则它一定不是可行域D的顶点 根据引理1,若X不是基可行解,则其正分量所对应的系数列向量P1,P2,…,Pm线性相关,即存在一组不全为零的数αi,i=1,2,…,m使得 α1P1+α2P2+…+αmPm=0 (1-9) 用一个μ>0的数乘(1-9)式再分别与(1-8)式相加和相减, 这样得到(x1-μα1)P1+(x2-μα2)P2+…+(xm-μαm)Pm=b(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]由X(1),X(2)可以得到X=(1/2)X(1)+(1/2)X(2), 即X是X(1),X(2)连线的中点 另一方面,当μ充分小时,可保证 xi±μαi≥0,i=1,2,…,m 即X(1),X(2)是可行解。 这证明了X 不是可行域 D 的顶点。 (2) 若X不是可行域D的顶点,则它一定不是基可行解 因为X不是可行域 D 的顶点,故在可行域D中可找到不同的两点 X(1)=(x1(1),x2(1),…,xn(1))T X(2)=(x1(2),x2(2),…,xn(2))T 使 X=αX(1)+(1-α) X(2) , 0<α<1 设X是基可行解,对应向量组P1…Pm线性独立。当j>m时,有xj=xj(1)=xj(2)=0,由于X(1),X(2)是可行域的两点。应满足 将这两式相减,即得 因X(1)≠X(2),所以上式系数不全为零,故向量组P1,P2,…,Pm线性相关,与假设矛盾。即X不是基可行解。 引理2 若K是有界凸集,则任何一点X∈K可表示为K的顶点的凸组合。 本引理证明从略,用以下例子说明这引理。 例5 设X是三角形中任意一点,X(1),X(2)和X(3)是三角形的三个顶点,试用三个顶点的坐标表示X(见图1-8) 解 任选一顶点X(2),做一条连线XX(2);并延长交于X(1)、X(3)连接线上一点X′。因X′是X(1)、X(3)连线上一点,故可用X(1)、X(3)线性组合表示为 X′=αX(1)+(1-α)X(3) 0<α<1 又因X是X′与X(2)连线上的一个点,故 X=λX′+(1-λ)X(2) 0<λ<1 将X′的表达式代入上式得到 X=λ[αX(1)+(1-α)X(3)]+(1-λ)X(2) =λαX(1)+λ(1-α)X(3)+(1-λ)X(2) 令 μ1=αλ,μ2=(1-λ),μ3=λ(1-α) 这就得到 X=
文档评论(0)