《最優化計算》考試樣卷第4頁共4頁華南理工大學研究生課程考試《最優化計算》考試樣卷注意事項：1.所有答案請按要求填寫在答題紙上；2.課程代碼：（S0003010）3.考試形式：閉卷（√）開卷（）開閉卷結合（）4.考生類別：博士研究生（）碩士研究生（√）5.試卷共9大題，滿分100分，考試時間為150分鐘。選擇、判斷、填空（10小題，每題2分，共20分）**第1-3小題：選擇A、B、C、D四個答案之一，填在橫線上***1、線性規劃問題化為標準型以后，原來的某自由變量被兩個非負變量之差代替，在完成一次單純形法迭代過程后，這兩個非負變量的值_______________。A、可同時不為0；B、必然同時為0；C、最多只能有一個不為0；D、必然同時不為0。2、關于線性規劃，以下敘述正確的是________。A、若存在最優解，則一定是最優基本可行解；B、若存在最優基本可行解，則其對偶問題未必存在最優解；C、若無可行解，則對偶問題一定有無界解；D、若存在最優解，則必存在最優基本可行解。3、關于P類問題、NP類問題和P類算法、NP類算法，以下正確的敘述是______________。A、存在P類算法的判定問題不一定是P類問題；B、線性規劃問題的單純形算法不是P類算法，所以線性規劃問題是NP類問題；C、NP類問題包含P類問題；D、P類問題與NP類問題是互相對立的兩類問題。***第4-6小題：判斷正誤，正確的填“√”，錯誤的填“╳”，填在括號內***4、用模擬退火算法求出的組合優化問題的解一定是最優解（）。5、對于有約束非線性規劃問題，目標函數的極值點一定是K-T點（）。6、已知LP為求最小值問題，第i個約束是“≤”約束，則對偶問題的第i個對偶變量yi≤0（）。***第7-10小題：將答案填在橫線上***7、若x(0)和y(0)分別是線性規劃問題min{z=cTx|Ax≥b,x≥0}和其對偶問題的可行解，則x(0)和y(0)的關系是____________________（兩者目標函數在x(0)和y(0)處值的關系）。8、設xi是某線性規劃問題的一個決策變量，在單純形法某次迭代后，若它的檢驗數不為零，則xi是________變量。9、使用黃金分割法和拋物線法進行一維搜索（設目標函數為minf(x)）之前，必須首先找到三點，x1、x2和x3，這三點應滿足的條件為____________________________________。10、用牛頓法求解約束優化問題minf(x)的x(1)（假設f(x)在x(1)）二階光滑，且Hasse矩陣正定）處的牛頓方向是_____________________________。二、（（12分））考慮如下線性規劃問題令和表示每個約束的松弛變量．應用單純形方法，得到最優單純形表如下1/31-1/31/30-2/3601102/311/31/341(1)分析c1在什么范圍變化時，上述單純形表仍是最優表．（2）當b變化為時，求新的最優解。三、試證明下述線性規劃問題或者沒有最優解或者最優值為0：其中．（10分）。用單純形法求解以下線性規劃問題（10分）五、建立線性規劃數學模型（不必求解）（10分） 福安商場是個中型的百貨商場，它對售貨人員的需求經過統計分析如下表所示，為了保證售貨人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續的，問該如何安排售貨人員的休息，既滿足了工作需要，又使配備的售貨人員的人數最少，請列出此問題的數學模型。時間所需售貨人員數時間所需售貨人員數星期一28星期五19星期二15星期六3l星期三24星期日28星期四25六、考慮非線性規劃問題求K-T點(10分)