專業(yè)： 科類： 科　班級：　　 級　　班　　姓名：　　　　 學(xué)號：　　　　　　　　 ………………………………裝………………………………訂……………………………線………………………… ………………………………裝………………………………訂……………………………線………………………… 專業(yè)： 科類： 科　班級：　　 級　　班　　姓名：　　　　 學(xué)號：　　　　　　　　 臨沂師范學(xué)院數(shù)學(xué)本科階段性測試 《運(yùn)籌學(xué)》試題（3） 題號 一 二 三 四 五 六 七 八 九 十 總分 得分 閱卷人 一、 填空題（３×5=１5分） 1．設(shè)ｆ（ｘ）在ｘ＊的一個(gè)鄰域內(nèi)二階連續(xù)可微，那么ｘ＊為無約束最優(yōu)化問題的一個(gè)最優(yōu)解的二階充分條件是＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。 ３．橢球算法和內(nèi)點(diǎn)算法的作為線性規(guī)劃的一個(gè)求解算法，其算法復(fù)雜性是＿＿＿＿＿＿＿＿＿＿。 ４． 對于標(biāo)準(zhǔn)形線性規(guī)劃問題，如果有有限的最優(yōu)解，則必可在其＿＿＿＿＿＿＿＿＿＿＿＿＿＿取得。 ５．如果互為對偶的兩個(gè)線性規(guī)劃問題中一個(gè)有最優(yōu)解，則另一個(gè)也有——————————————。 ６．如果兩個(gè)互為對偶的線性規(guī)劃問題各有一個(gè)可行解,且相應(yīng)的目標(biāo)函數(shù)值相同，則這兩個(gè)可行解＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。 二．計(jì)算題（６0分） 1．（１０）用圖解法確定下面線性規(guī)劃問題的最優(yōu)解 ２． （２０）單純行法確定下面線性規(guī)劃問題的最優(yōu)解 ３． （１０）出下面線性規(guī)劃問題的對偶問題 ４．（２０）用對偶單純行法確定下面線性規(guī)劃問題的最優(yōu)解 三、證明題(25分) １．(10)設(shè)D∈Rn 是非空凸集，是定義在D上的凸函數(shù)，是一個(gè)實(shí)數(shù)，則集合L={x∈ D| }是一個(gè)凸集。 ２．(10)對任何線性規(guī)劃問題,其對偶的對偶還是原問題。 ３．（５）寫出下面線性規(guī)劃的ＫＫＴ條件． 　　　　　　　　　　　　　 臨沂師范學(xué)院數(shù)學(xué)系階段性測試(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ì)算題（６０）　　　　　　　　　　　　　 ?。保　　　　　　　　　　　　　　　? 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　?。粒ǎ矗常保矗常? 　　　　　　　　　　　　?。碊 v=(1,3) 　　　　　　　　　　　　 　　　　　　　　　　　　 　　　　　　　　　　　　　　　　　　　　　　　　　?。? 　　　　　　　　　　　　　?。谩　　　　　　　　　?６ ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．７分 如圖給出了這一問題的可行域 F，它是由線段AB,BC,CD,DA圍成的凸多邊形(凸集)，A,B, C,D是這個(gè)凸集的4個(gè)頂點(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／３．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１０分 （敘述不標(biāo)準(zhǔn)者酌情扣分） ２．（２０）解：首先，引入三個(gè)松馳變量，，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形的線性規(guī)劃問題 ．．．．．．．．．．．．．．．．．．．．．．．．．４分 取，，為初始基變量得下面單純形表 基變量 　　　　　　　　　　　　　　 右端項(xiàng) －ｆ －２　　?。场　　　。啊　　　。啊　　　。? ?。? －１　　?。薄　　　　。薄　　　。啊　　　。? －２　　?。薄　　　　。啊　　　。薄　　　。啊? ４　　　?。薄　　　　。啊　　　。啊　　　。? 　　 ?。? ２ １６ 　　　　　　　　　　　　　　　?。阜? 取為出基變量，為出基變量，以－２為旋轉(zhuǎn)主元，得下表 基變量 　　　　　　　　　　　　　　 右端項(xiàng) －ｆ －８　　?。啊　　　? ０　　　　?。场　　。? 　６ １　　?。啊　　　　。薄　　。薄　　　。? －２　　?。薄　　　　。啊　　　。薄　　　。啊? ６　　?。啊　　　　。啊　　。薄　　　。? 　　 　１ ２ １４ 　　　　　　　　　　　　　　　?。保卜? 取為出基變量，為出基變量，以1為旋轉(zhuǎn)主元，得下表 基變量 　　　　　　　　　　　　　　 右端項(xiàng) －ｆ 0　　　 ０　　　　 　8　　　－５　　　?。? ?。保? １　　?。啊　　　　。薄　　。薄　　　。? ０　　　１　　　　?。病　　。薄　　　。啊? ０　　　０　　　?。丁　　　。怠　　　。? 　　 　１ ４ ８ 　　　　　　　　　　　　　　　　?。保斗? 取為出基變量，為出基變量，以５為旋轉(zhuǎn)主元，得下表 基變量 　　　　　　　　　　　　　　 右端項(xiàng) －ｆ 0　　　 ０　　　　 １４　　　０　　　?。? 　２２ １　　?。啊　　　。　　。啊　　　? ０　　?。薄　　　　　　　。啊　　　　? ０　　?。啊　　　。　　。薄　　　? 　　 　 至此，所有 ，當(dāng)前的迭代點(diǎn)已是問題的一個(gè)最優(yōu)解，得最優(yōu)解為 ＝ ， ＝ ， ＝０， ＝ ， ＝０，相應(yīng)的最優(yōu)目標(biāo)函數(shù)值為－２２． 　　　　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．２０分 （敘述不標(biāo)準(zhǔn)者酌情扣分） ３．（１０）解： 　　　　　　　　　?。保胺? ４．（２０）解．首先，將本題中的約束轉(zhuǎn)化成型，再引入松馳變量得 　　　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．４分 取，為初始基變量得下面單純形表 基變量 　　　　　　　　 右端項(xiàng) －ｆ ９　　５　　?。场　。啊　。? ?。? －３　－２　　?。场　。薄　。啊? ０?。病　。薄　。啊　。? 　 ?。? －５ 　　　　　　　　　　　　　　　　　　　　　?。阜? 取為出基變量，為入基變量，以－２為旋轉(zhuǎn)主元，得下表 基變量 　　　　　　　　 右端項(xiàng) －ｆ ９　?。啊　　　　。啊　? － －３　０　　?。础　。薄。薄? ０　　１　　　　?。啊。? 　 －８ 　　　　　　　　　　　　　　　　　　　　　?。保卜? 取為出基變量，為入基變量，以－３為旋轉(zhuǎn)主元，得下表 基變量 　　　　　　　　 右端項(xiàng) －ｆ ０　?。啊。保病　。场　? － １　　０?。　。　? ０　?。薄　　　。啊。? 　 　　　　　　　　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．１６分 至此，右端項(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ù)，故 　　　　　　　　　　　　　　　　　　?。阜? 因此， 從而 L是凸集。．．．．．．．．．．．．．．．．．．．．．．．．．．１０分 ２．（１０）證明：因?yàn)槿魏涡问降木€性問題都可以轉(zhuǎn)化為經(jīng)典形式，在此我們只考慮經(jīng)典形線性規(guī)劃問題： 易知，其對偶問題為： ．．．．．．．．．．．．．．．．．．．．．．．５分 將對偶形式轉(zhuǎn)化為經(jīng)典形式： 　　　　　　　　　　　　　 它的對偶為 　　　　　　　　　　　　　　　 經(jīng)整理即得原線性規(guī)劃問題． 　　　　　　　　　　　　　　　　　　　　　　?。保胺? ３（５）標(biāo)準(zhǔn)形線性規(guī)劃的ＫＫＴ條件：設(shè)是其最優(yōu)解，在最優(yōu)解處存在和，使得 　　　　　　 　　　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．５分