範學院數學本科階段性測試
《運籌學》試題（１）
一、 填空題（３×５=１５分）
１．設ｆ（ｘ）在ｘ＊的乙個鄰域內二階連續可微，那麼ｘ＊為無約束最優化問題的乙個最優解的二階必要條件是
２．設ｆ（ｘ）在ｘ＊的乙個鄰域內二階連續可微，那麼ｘ＊為無約束最優化問題的乙個最優解的二階充分條件是
３．單純行法作為線性規劃的乙個求解演算法，其演算法複雜性
4．橢球演算法和內點演算法的作為線性規劃的乙個求解演算法，其演算法複雜性是
５．如果互為對偶的兩個線性規劃問題中乙個有最優解，則另乙個
二．計算題（60分）
1．(10)用**法確定下面線性規劃問題的最優解
２．（20)用單純行法確定下面線性規劃問題的最優解
３．(10)給出下面線性規劃問題的對偶問題
４．(20)用對偶單純行法確定下面線性規劃問題的最優解
三、證明題(25)
1．(1０)凸規劃問題的乙個區域性最優解一定是它的全域性最優解．
2．(1０)敘述並證明弱對偶定理．
３．（５）寫出標準形線性規劃的ｋｋｔ條件．
臨沂師範學院數學系階段性測試(1)
《運籌學》試題標準答案
一、 填空題：（３×５=１５）
1、，2、，
3、不是多項式時間演算法，
4、，多項式時間演算法，
５、也有最優解,且兩者的最優目標函式值相等。
二、 計算題
6分如圖給出了這一問題的可行域 f，它是由線段ab,bc,cd,de,ea$圍成的凸多邊形(凸集)，
a,b, c,d,e是這個凸集的五個頂點。隨著同位線的向左移動，目標函式值逐漸減小，f=-5的同位線同可行域相交於可行域的頂點a.如果把f=-5的同位線向左作任何一點點的移動，儘管目標函式值會有所減小，但同可行域不再有任何交點。
也就是說不存在任何使目標函式值小於-5的可行點，因此可行域的頂點a是上述線性規劃問題的最優解，最優目標函式值為-5.由圖我們還可以看出在頂點a為最優點，即有x1*=1,x2*=4分
敘述不標準者酌情扣分)
２．（２０）解：首先，引入三個鬆馳變數，，將其轉化為標準形的線性規劃問題
分取，，為初始基變數得下面單純形表
分取為出基變數，為入基變數，以－２為旋轉主元，得下表
分取為出基變數，為入基變數，以1為旋轉主元，得下表
分取為出基變數，為入基變數，以５為旋轉主元，得下表
至此，所有，當前的迭代點已是問題的乙個最優解，得最優解為相應的最優目標函式值為－２２．
分(敘述不標準者酌情扣分)
３．（１０）解：
分４．（２０）解．首先，將本題中的約束轉化成型，再引入鬆馳變數得
分取，為初始基變數得下面單純形表
分取為出基變數，為入基變數，以－２為旋轉主元，得下表
分取為出基變數，為入基變數，以－２為旋轉主元，得下表
分至此，右端項的所有分量都已非負，當前的迭代點已是問題的乙個最優解，得最優解為＝５，＝５，＝０，相應的最優目標函式值為分
(敘述不標準者酌情扣分)
三、 證明題(25)
1． （１０）證明：設是凸規劃問題的乙個區域性最優解，但不是它的全域性最優解，則
存在另乙個可行點，設為滿足分
有可行集的凸性，對於任意的，點都是可行點分
又根據目標函式的凸性有
分這表明在的任意小的鄰域內都存在函式值小於的可行點，這與是凸規劃問題的乙個區域性最優解相矛盾，因此，函式值小於的可行點不存在，一定是凸規劃問題的乙個全域性最優解分
２．（１０）敘述弱對偶定理．設和分別是原始問題和對偶問題的可行解，則有
分證明：考慮標準形線性規劃問題：
易知，其對偶問題為：
6分根據的對偶可行性有，再由得
分３（５）標準形線性規劃的ｋｋｔ條件：設是其最優解，在最優解處存在和，使得分
運籌學試題
四 計算題 本大題共5小題，每小題8分，共40分 利用對偶理論證明其目標函式值無界。25 試用大m法解下列線性規劃問題。26 福安商場是個中型的百貨商場，它對售貨人員的需求經過統計分析如下表所示，為了保證售貨人員充分休息，售貨人員每週工作五天，休息兩天，並要求休息的兩天是連續的，問該如何安排售貨人員...
運籌學一試題
可不抄題，答案必須寫在我校統一配發的專用答題紙上！第1題 15分 簡述題 1 試述線性規劃問題的可行解 基解 基可行解 最優解的概念以及它們之間的相互關係。2 簡述單純形法解線性規劃問題中可能遇到的退化問題及處理退化問題的勃蘭特規則。3 已知線性規劃問題如下，簡述兩階段法的求解思路。max z cx...
管理運籌學試題
一 單項選擇題 1 10 10分 1 一般講，對於某一問題的線性規劃與該問題的整數規劃可行域的關係存在 a.前者大於後者 b.後者大於前者 c.二者相等 d.二者無關 2 求解整數規劃的方法是 a.標號法 b.匈牙利法 c.隱列舉法 d.割平面法 3.線性規劃靈敏度分析應在 基礎上，分析係數變化對最...