最优化方法第二周作业答案

1、第二周作业:1.设S=xAxb，其中A是mXn矩阵，mn,A的秩为n。证明x是S的极点的充耍条件是4和b可作如I、分解：其中，人有n个行，且&的秩为，切是n维列向量，使得4x(0)=*,停b2.证明：U设X,x2)gS,则Axb,Ax2)b对V2g(0,1),若x=Axw+(1-加,则S=&.卅丿=+(1-2)人尤n肋i+(i-a)h=b、:.必有Ax=q,人.严=b=&少=停A可逆，.有x即X为极点。=(证法1)x是极点,.Ab./(b、.A,b总、可以分解为4=；,b=,使得设=代)，若)工，则存在不全为零的数厶,丄使得比+也+比.定义=普+码,j=1,2,/*2)=甥)一/,/=1,2,

2、/则Ax(l)=A；/o+w(/+If)=b同理，有人少=休又.筠凹$,.当足够小时,有辱性妇,停沁,),x(2)GSo但;2=丄0丿+丄0),与兀是极点矛盾。22所以广()=。设A；为sxn阶矩阵，由丁*()=n,sn,因此4和b可作如卜分解：其中，A有n个行，且&的秩为，勺是n维列向量，使得4x(0)=bA2x(0)b2o”n”(证法2).少是S的极点,有Ab.设A中只有R个线性无关的行向量人,人伙)满足Bxw=少=休4丿其中q为r维列向量。则对A中其余的加-k行A+，,A”,有B“=且若A,.=bi2，则人可由人,，人线性表出。k=x0)-sy0)(w0)当取足够小时，有A严=$(x+严

3、)b,b冶丿(若Ax=丘=人=也+/,A4严=也艸+=o)而少=l/o+丄X?与X是极点矛盾。22第二周作业(2)1.用单纯形方法解卜列线性规划问题:00(1)min3心一Sx2一2x3一x4s.tX+x2+x544xx-x2+x3+2x46-xk+x2+2x3+3x4o,j=1,，4c8、7z.68X*=0,4.u，三，/mm32.3丿(2)min一3心一心s.t3“42+3x2+x3=30-4x2+x4=16一心o,j=1,-,4X*=(7,3,o,o)7，九=-24.2假设用单纯形方法解线性规划问题1)1111CXs.t.Ax=bA0在某次迭代中对应变帛巧的判别数.-C.0,且单纯形表中

4、对应的列儿=BlPj0。证明：0d=：1是可行域的极方向。其中分鼠1对应巧。证明：显然dno,由于儿=歹比.Md=（,，化，号，工Jd=儿-p*pmymi+Pj=一（片,，化）+P产一BB-Pj+Pj=d为方向。乂由于，化线性无关，Ad=O,./,，化,Pj线性相关,nd为极方向。证明2：显然dno,由于兀=旷巧.4d=（,必，号，即d=-pJu-叽pmymj+Pj九、=-（片,，匕）:+Pj=_BB7Pj+Pj=ON丿二为方向。假设存在方向d,d,使得d=川+加（九心0）.则d,d0且Ad=0,4d=0o设d=严網/d，d=f订.则有血福d?5比、=A酉、+入=卅+砖比=(0,1,0)丁,40,d,d0有彳d*+人d：)=i,严二严二0(,丰j)o乂因为Ad=0,Ad=0。Bdf+Nd綱=0=d中=-Nd$=-d)BiPjB