《《運籌學試題》word版》由會員分享，可在線閱讀，更多相關《《運籌學試題》word版（8頁珍藏版）》請在裝配圖網上搜索。

1、專業(yè)： 科類： 科　班級：　　 級　　班　　姓名：　　　　 學號：　　　　　　　　 ………………………………裝………………………………訂……………………………線………………………… ………………………………裝………………………………訂……………………………線………………………… 專業(yè)： 科類： 科　班級：　　 級　　班　　姓名：　　　　 學號：　　　　　　　　 臨沂師范學院數學本科階段性測試 《運籌學》試題（3） 題號 一 二 三 四 五 六 七 八 九 十 總分 得分

2、 閱卷人 一、 填空題（３×5=１5分） 1．設ｆ（ｘ）在ｘ＊的一個鄰域內二階連續(xù)可微，那么ｘ＊為無約束最優(yōu)化問題的一個最優(yōu)解的二階充分條件是＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。 ３．橢球算法和內點算法的作為線性規(guī)劃的一個求解算法，其算法復雜性是＿＿＿＿＿＿＿＿＿＿。 ４． 對于標準形線性規(guī)劃問題，如果有有限的最優(yōu)解，則必可在其＿＿＿＿＿＿＿＿＿＿＿＿＿＿取得。 ５．如果互為對偶的兩個線性規(guī)劃問題中一個有最優(yōu)解，則另一個也有——————————————。 ６．如果兩個互為

3、對偶的線性規(guī)劃問題各有一個可行解,且相應的目標函數值相同，則這兩個可行解＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。 二．計算題（６0分） 1．（１０）用圖解法確定下面線性規(guī)劃問題的最優(yōu)解 ２． （２０）單純行法確定下面線性規(guī)劃問題的最優(yōu)解 ３． （１０）出下面線性規(guī)劃問題的對偶問題 ４．（２０）用對偶單純行法確定下面線性規(guī)劃問題的最優(yōu)解 三、證明題(25分) １．(10)設D∈Rn 是非空凸集，是定義在D上的凸函數，是一個實數，則集合L={x∈ D| }是一個凸集。

4、 ２．(10)對任何線性規(guī)劃問題,其對偶的對偶還是原問題。 ３．（５）寫出下面線性規(guī)劃的ＫＫＴ條件． 　　　　　　　　　　　　　 臨沂師范學院數學系階段性測試(3) <<運籌學>>試題標準答案 一、 填空題：（３×５=１５） 1、， 2、，多項式時間算法， 3、可行域的某個頂點， ４、最優(yōu)解,且兩者的最優(yōu)目標函數值相等， ５、各是相應問題的最優(yōu)解 二、 計算題（６０）　　　　　　　　　　　　　 　１．　　　　　　　　　　　　　　　　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

5、　　　　　　　　　　　　　　　　　　　　　　　　　　　　Ａ（４／３，１４／３） 　　　　　　　　　　　　　４D v=(1,3) 　　　　　　　　　　　　 　　　　　　　　　　　　 　　　　　　　　　　　　　　　　　　　　　　　　　?。? 　　　　　　　　　　　　　　Ｃ　　　　　　　　　　 ６ ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．７分 如圖給出了這一問題的可行域 F，它是由線段AB,BC,CD,DA圍成的凸多邊形

6、(凸集)，A,B, C,D是這個凸集的4個頂點。隨著同位線的向右移動，目標函數值逐漸減小，f=－４６／３的同位線同可行域相交于可行域的頂點A.如果把f=－４６／３的同位線向右作任何一點點的移動，盡管目標函數值會有所減小，但同可行域不再有任何交點。也就是說不存在任何使目標函數值小于－４６／３的可行點，因此可行域的頂點A是上述線性規(guī)劃問題的最優(yōu)解，最優(yōu)目標函數值為－４６／３.由圖我們還可以看出在頂點A為最優(yōu)點，即有 x1*=４／３,x2*=１4／３．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１０分

7、 （敘述不標準者酌情扣分） ２．（２０）解：首先，引入三個松馳變量，，將其轉化為標準形的線性規(guī)劃問題 ．．．．．．．．．．．．．．．．．．．．．．．．．４分 取，，為初始基變量得下面單純形表 基變量 　　　　　　　　　　　　　　 右端項 －ｆ －２　　?。场　　　。啊　　　。啊　　　。? ?。? －１　　　１　　　　?。薄　　　。啊　　　。? －２　　　１　　　　?。啊　　　。薄　　　。啊? ４　　

8、　　１　　　　?。啊　　　。啊　　　。? 　　 　３ ２ １６ 　　　　　　　　　　　　　　　?。阜? 取為出基變量，為出基變量，以－２為旋轉主元，得下表 基變量 　　　　　　　　　　　　　　 右端項 －ｆ －８　　?。啊　　　? ０　　　　　３　　?。? 　６ １　　?。啊　　　　。薄　　。薄　　　。? －２　　?。薄　　　　。啊　　　。薄　　　。啊? ６　　?。啊　　　　。啊　　。薄　　　。? 　　 ?。? ２ １４ 　　　　　　　　　　　　　　　?。?/p>

9、．．．．．．．．．．．．．．．．．．．．．．．．１２分 取為出基變量，為出基變量，以1為旋轉主元，得下表 基變量 　　　　　　　　　　　　　　 右端項 －ｆ 0　　　 ０　　　　 　8　　　－５　　　?。? 　１４ １　　?。啊　　　　。薄　　。薄　　　。? ０　　?。薄　　　　。病　　。薄　　　。啊? ０　　?。啊　　　。丁　　　。怠　　　。? 　　 ?。? ４ ８ 　　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１６分 取為出基變量，為出基變量，以５為旋轉主元，得下表

10、基變量 　　　　　　　　　　　　　　 右端項 －ｆ 0　　　 ０　　　　 １４　　?。啊　　　。? ?。玻? １　　　０　　　?。　　。啊　　　? ０　　?。薄　　　　　　　。啊　　　　? ０　　?。啊　　　。　　。薄　　　? 　　 　 至此，所有 ，當前的迭代點已是問題的一個最優(yōu)解，得最優(yōu)解為 ＝ ， ＝ ， ＝０， ＝ ， ＝０，相應的最優(yōu)目標函數值為－２２． 　　　　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．２０分 （敘述不標準者酌情扣分） ３．（１０）解：

11、 　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１０分 ４．（２０）解．首先，將本題中的約束轉化成型，再引入松馳變量得 　　　　　　　　　　　　　　　　　?。捶? 取，為初始基變量得下面單純形表 基變量 　　　　　　　　 右端項 －ｆ ９　?。怠　　。场　。啊　。? ?。? －３?。病　　。场　。薄　。啊? ０?。病　。薄　。啊　。? 　 ?。? －５ 　　　　　　　　　　　　　　　　　　　　　　．．．．．．．

12、．．．．．．．．．．．．．．．．．．．８分 取為出基變量，為入基變量，以－２為旋轉主元，得下表 基變量 　　　　　　　　 右端項 －ｆ ９　?。啊　　　　。啊　? － －３?。啊　　。础　。薄。薄? ０　?。薄　　　　。啊。? 　 －８ 　　　　　　　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．．．１２分 取為出基變量，為入基變量，以－３為旋轉主元，得下表 基變量 　　　　　　　　 右端項 －ｆ ０　　０?。保病　。场　? － １　?。啊。　。　? ０　　１　　　?。?/p>

13、?。? 　 　　　　　　　　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．１６分 至此，右端項的所有分量都已非負，當前的迭代點已是問題的一個最優(yōu)解，得最優(yōu)解為＝，＝，＝０，相應的最優(yōu)目標函數值為－．．．．．．．．．．．．．．．．．．．２０分 （敘述不標準者酌情扣分） 三、 證明題(25) １．（１０）證明：設∈ L, 于是∈D, , . 今設,．．．．．．．．．．．．．．．．．．．．．．．．．．４分 由于是凸函數，故 　　　　　　　　　　　　　　　　　　?。阜? 因此，

14、 從而 L是凸集。．．．．．．．．．．．．．．．．．．．．．．．．．．１０分 ２．（１０）證明：因為任何形式的線性問題都可以轉化為經典形式，在此我們只考慮經典形線性規(guī)劃問題： 易知，其對偶問題為： ．．．．．．．．．．．．．．．．．．．．．．．５分 將對偶形式轉化為經典形式： 　　　　　　　　　　　　　 它的對偶為 　　　　　　　　　　　　　　　 經整理即得原線性規(guī)劃問題． 　　　　　　　　　　　　　　　　　　　　　　?。保胺? ３（５）標準形線性規(guī)劃的ＫＫＴ條件：設是其最優(yōu)解，在最優(yōu)解處存在和，使得 　　　　　　 　　　　　　　　　　　　　　　　　?。捣?