1、專業(yè)： 科類： 科班級： 級班姓名： 學(xué)號：裝訂線裝訂線專業(yè)： 科類： 科班級： 級班姓名： 學(xué)號：臨沂師范學(xué)院數(shù)學(xué)本科階段性測試運籌學(xué)試題（3）題號一二三四五六七八九十總分得分閱卷人填空題（5=5分）1設(shè)（）在的一個鄰域內(nèi)二階連續(xù)可微，那么為無約束最優(yōu)化問題的一個最優(yōu)解的二階充分條件是。 橢球算法和內(nèi)點算法的作為線性規(guī)劃的一個求解算法，其算法復(fù)雜性是。 對于標(biāo)準(zhǔn)形線性規(guī)劃問題，如果有有限的最優(yōu)解，則必可在其取得。如果互為對偶的兩個線性規(guī)劃問題中一個有最優(yōu)解，則另一個也有。如果兩個互為對偶的線性規(guī)劃問題各有一個可行解,且相應(yīng)的目標(biāo)函數(shù)值相同，則這兩個可行解。二計算題（0分）1（）用圖解法確定下

2、面線性規(guī)劃問題的最優(yōu)解 （）單純行法確定下面線性規(guī)劃問題的最優(yōu)解（）出下面線性規(guī)劃問題的對偶問題（）用對偶單純行法確定下面線性規(guī)劃問題的最優(yōu)解三、證明題(25分)(10)設(shè)DRn 是非空凸集，是定義在D上的凸函數(shù)，是一個實數(shù)，則集合L=x D| 是一個凸集。(10)對任何線性規(guī)劃問題,其對偶的對偶還是原問題。（）寫出下面線性規(guī)劃的條件臨沂師范學(xué)院數(shù)學(xué)系階段性測試(3)試題標(biāo)準(zhǔn)答案填空題：（=）1、，2、，多項式時間算法，3、可行域的某個頂點，、最優(yōu)解,且兩者的最優(yōu)目標(biāo)函數(shù)值相等，、各是相應(yīng)問題的最優(yōu)解計算題（）（，）D v=(1,3) 分如圖給出了這一問題的可行域 F，它是由線段AB,BC,C

3、D,DA圍成的凸多邊形(凸集)，A,B, C,D是這個凸集的4個頂點。隨著同位線的向右移動，目標(biāo)函數(shù)值逐漸減小，f=的同位線同可行域相交于可行域的頂點A.如果把f=的同位線向右作任何一點點的移動，盡管目標(biāo)函數(shù)值會有所減小，但同可行域不再有任何交點。也就是說不存在任何使目標(biāo)函數(shù)值小于的可行點，因此可行域的頂點A是上述線性規(guī)劃問題的最優(yōu)解，最優(yōu)目標(biāo)函數(shù)值為.由圖我們還可以看出在頂點A為最優(yōu)點，即有x1*=,x2*=4分 （敘述不標(biāo)準(zhǔn)者酌情扣分）（）解：首先，引入三個松馳變量，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形的線性規(guī)劃問題 分取，為初始基變量得下面單純形表基變量右端項分取為出基變量，為出基變量，以為旋轉(zhuǎn)主元，得下表

4、基變量右端項 分取為出基變量，為出基變量，以1為旋轉(zhuǎn)主元，得下表基變量右端項0 8分取為出基變量，為出基變量，以為旋轉(zhuǎn)主元，得下表基變量右端項0 至此，所有 ，當(dāng)前的迭代點已是問題的一個最優(yōu)解，得最優(yōu)解為 ， ， ， ， ，相應(yīng)的最優(yōu)目標(biāo)函數(shù)值為分（敘述不標(biāo)準(zhǔn)者酌情扣分）（）解：分（）解首先，將本題中的約束轉(zhuǎn)化成型，再引入松馳變量得分取，為初始基變量得下面單純形表基變量右端項分取為出基變量，為入基變量，以為旋轉(zhuǎn)主元，得下表基變量右端項分取為出基變量，為入基變量，以為旋轉(zhuǎn)主元，得下表基變量右端項分至此，右端項的所有分量都已非負(fù)，當(dāng)前的迭代點已是問題的一個最優(yōu)解，得最優(yōu)解為，相應(yīng)的最優(yōu)目標(biāo)函數(shù)值為分（敘述不標(biāo)準(zhǔn)者酌情扣分）證明題(25)（）證明：設(shè) L, 于是D, , .今設(shè),分由于是凸函數(shù)，故分因此， 從而 L是凸集。分（）證明：因為任何形式的線性問題都可以轉(zhuǎn)化為經(jīng)典形式，在此我們只考慮經(jīng)典形線性規(guī)劃問題：易知，其對