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

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

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

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

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

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

6、(凸集)，A,B, C,D是這個(gè)凸集的4個(gè)頂點(diǎn)。隨著同位線的向右移動(dòng)，目標(biāo)函數(shù)值逐漸減小，f=－４６／３的同位線同可行域相交于可行域的頂點(diǎn)A.如果把f=－４６／３的同位線向右作任何一點(diǎn)點(diǎn)的移動(dòng)，盡管目標(biāo)函數(shù)值會(huì)有所減小，但同可行域不再有任何交點(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)者酌情扣分） ２．（２０）解：首先，引入三個(gè)松馳變量，，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形的線性規(guī)劃問題 ．．．．．．．．．．．．．．．．．．．．．．．．．４分 取，，為初始基變量得下面單純形表 基變量 　　　　　　　　　　　　　　 右端項(xiàng) －ｆ －２　　?。场　　　。啊　　　。啊　　　。? ?。? －１　　?。薄　　　　。薄　　　。啊　　　。? －２　　?。薄　　　　。啊　　　。薄　　　。啊? ４　　

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

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

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

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

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

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

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