资源描述：
《最优化方法第二周作业答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第二周作业：(0)1．设S={x
2、Ax≥b}，其中A是m×n矩阵，m>n，A的秩为n。证明x是S的极点的充要条件是A和b可作如下分解：⎡A1⎤⎡b1⎤A=⎢⎥，b=⎢⎥Ab⎣2⎦⎣2⎦(0)其中，A有n个行，且A的秩为n，b是n维列向量，使得Ax=b，11111(0)Ax≥b。22(1)(2)(1)(2)证明：""⇐∈≥设x,xSA，则xb,Axb≥(1)(2)∴≥AxbAx,≥b1111(0)(1)(2)对，∀∈λλ(0,1)若xx=+−(1λ)x,则(0)(1)(2)bA==+xλλAx(1−)Ax1111≥+−=λλbb(1)b111
3、(1)(2)∴==必有AxbAx,b1111(0)(1)(2)⇒==AxAxAx111(0)(1)(2)∵Ax可逆，有∴==xx1(0)即x为极点。(0)(0)""⇒∴(1证法)∵xA是极点,x≥b.⎛⎞⎛⎞Ab′11∴=Ab,,总可以分解为A⎜⎟⎜⎟b=使得⎝⎠⎝⎠Ab′22(0)(0)Ax′′=>bAx,.b1122设，AP′′=≠(,,,)PPr"若()An，112n1则存在不全为零的数ll,,"使得1nlPlP+++="lP0.1122nn(1)(0)定义xxlj=+=ε,1,2,,"njjj(2)(0)xxlj=−=ε,1,2,,
4、"njjj(1)(0)则Ax′′=+++Axε()lPlP"+=lPb111122n1(2)同理，有Ax′=b.11(0)(1)(2)又∵Ax′′>∴b,当足够小时，有εAx≥bAx，′≥b，222222(1)(2)⇒∈xxS，。(0)11(1)(2)(0)但xxxx=+，与是极点矛盾。22所以rA()′=n。设A′′为sn×=阶矩阵，由于rAnsn(),故≥，111因此A和b可作如下分解：⎡A1⎤⎡b1⎤A=⎢⎥，b=⎢⎥Ab⎣2⎦⎣2⎦(0)其中，A有n个行，且A的秩为n，b是n维列向量，使得Ax=b，11111(0)Ax≥b。22(0
5、)(0)""⇒∴（证法）2∵xS是的极点，有Axb≥.设中只有个线性无关的行向量AkAA,,("k)当取足
6、够小时，有ε⎛⎞B(1)(0)(0)(2)Ax=+⎜⎟()xεy≥≥bAx,b⎝⎠B'(0)'(若Ax=⇒=++bAlA"lAii21i1kk(0)(0)(0)∴Ay=+lAy"+=lAy0)ik11k(0)11(1)(2)(0)而与xxxx=+,是极点矛盾。22第二周作业（2）1．用单纯形方法解下列线性规划问题：(1)min3xxxx−−−521234st.4x++xx≤12342xxxx−++≤61234−+++≤xxxx23121234xj≥=0,1,",4jT⎛⎞868xf*0==⎜⎟,4,0,,−.min2．⎝⎠33(2)min−
7、−3xx12st.33x++=xx3012344xxx−+=1612421xx−≤212xj≥=0,1,",4jTxf*==()7,3,0,0,min−24.2．假设用单纯形方法解线性规划问题mincxst..Axb=x≥0−1在某次迭代中对应变量xj的判别数zcjj−>0，且单纯形表中对应的列yBpjj=≤0。证明：⎡⎤−yj⎢⎥⎢⎥0⎢⎥#d=⎢⎥⎢⎥1⎢⎥#⎢⎥⎢⎥⎣⎦0是可行域的极方向。其中分量1对应xj。−1证明：显然dy≥=0，由于BPjj∴Ad=(,,,,,,)P"""PPPd1mjn=−Py−Py−−"Py+P11jjm22
8、mjj⎛⎞y1j⎜⎟−1=−(,,)PP"#⎜⎟+PB=−BPP+=01mjjj⎜⎟y⎝⎠mj⇒d为方向。又由于PP,,""线性无关，Ad=∴0,,，PPP，11mmj线性相关，⇒d为极方向。−1证明2：显然dy≥=0，由于BPjj∴Ad=(,,,,,,)P"""PPPd1mjn=−Py−Py−−"Py+P11jjm22mjj⎛⎞y1j⎜⎟−1=−(,,)PP"#⎜⎟+PB=−BPP+=01mjjj⎜⎟y⎝⎠mj⇒d为方向。(1)(2)(1)(2)假设存在方向dd,,使得dd=+λλλd(,0λ>).1212(1)(2)（）1（）2则且d,
9、0d≥==Ad0，Ad0。−1(1)(2)⎛⎞⎛−BPdd⎞⎛⎞j(1)BB(2)设d=⎜⎟⎜,,.dd==⎟⎜⎟则有⎜⎟⎜ddd(1)⎟⎜(2)⎟⎝⎠⎝NNN⎠⎝⎠−1(1)(
