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

第二周作业 1 设 bAxxS 其中A是nm 矩阵 nm A的秩为n 证明 0 x是S的极点 的充要条件是A和b可作如下分解 2 1 A A A 2 1 b b b 其中 1 A有n个 行 且 1 A的 秩 为n 1 b是n维 列 向 量 使得 1 0 1 bxA 2 0 2 bxA 1 2 1 2 1 2 1111 0 1 2 0 1 2 1111 111 1 2 1111 0 1 2 111 0 1 2 1 0 1 1 1 1 xxSAxb Axb Axb Axb xxx bAxAxAx bbb Axb Axb AxAxAx Axxx x 证明 设 则 对 若则 必有 可逆 有 即 0 为极点 0 0 11 22 0 0 1122 1121 1 1 122 1 0 2 0 1 0 1 2 1 2 n n nn jjj jjj xAxb Ab A bAb Ab Axb A xb AP PPr An ll l Pl Pl P xxljn xxlj 证法是极点 总可以分解为使得 设 若 则存在不全为零的数使得 定义 1 0 111 1221 2 11 0 1 2 222222 1 2 0 1 2 0 11 22 n n AxAxl Pl Pl Pb Axb A xbA xbA xb xxS xxxx 则 同理 有 又当 足够小时 有 但 与是极点矛盾 所以 1 r An 设 11 Asnr Ansn 为阶矩阵 由于故 因此A和b可作如下分解 2 1 A A A 2 1 b b b 其中 1 A有n个 行 且 1 A的 秩 为n 1 b是n维 列 向 量 使得 1 0 1 bxA 2 0 2 bxA 0 0 1 1 0 0 1 1 1 0 0 12 0 21 2 0 k k k km m iiik xSAxb AkAA kn A Bxxb A bk A Am kAAB xxb A AxbAAA knBx 穷解 设为的非零解 则 令 当 取足够小时 有 若 而与 是极点矛盾 第二周作业 2 1 用单纯形方法解下列线性规划问题 2 1234 123 1234 1234 m in 12 123 124 12 m in 1 m in352 4 426 2312 0 1 4 868 0 4 0 33 2 m in3 3330 4416 212 0 1 4 7 3 0 0 24 j T j T xxxx s txxx xxxx xxxx xj xf xx s txxx xxx xx xj xf 2 假设用单纯形方法解线性规划问题 min 0 cx stAxb x 在某次迭代中对应变量 xj的判别数0 jj zc 且单纯形表中对应的列 1 0 jj yB p 证 明 0 1 0 j y d 是可行域的极方向 其中分量 1 对应 xj 1 1 1122 1 1 1 11 0 0 0 jj mjn jjmmjj j mjjj mj mmj dyB P AdPPPP d PyP yP yP y PPPBB PP y d PPAdPPP d 证明 显然 由于 为方向 又由于线性无关 线性相关 为极方向 1 1 1122 1 1 1 1 2 1 2 1212 1 2 12 1 0 0 0 000 jj mjn jjmmjj j mjjj mj j dyB P AdPPPP d PyP yP yP y PPPBB PP y d ddddd ddAdAd B P d d 证明2 显然 由于 为方向 假设存在方向使得 则且 设 1 2 1 2 1 2 1 1 2 12 1 2 1 2 12 1 2 12 1 2 1 12 010 0 0 BB NNN jBB NNN NNN T N jjii dd dd dd B Pdd ddd ddd ddd dddd 则有 有 1 2 12 1 1 1 1 1 1 1 2 2 2 1 2 2 1 1 2 1 2 1 1 2 2 00 0 0 0 0 00 BNBNjj BN