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