《《運(yùn)籌學(xué)試題》word版》由會員分享，可在線閱讀，更多相關(guān)《《運(yùn)籌學(xué)試題》word版（8頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

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

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

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

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

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

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

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

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

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

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

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

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