《運(yùn)籌學(xué)試題》word版

1、專業(yè)： 科類： 科班級： 級班姓名： 學(xué)號(hào)：裝訂線裝訂線專業(yè)： 科類： 科班級： 級班姓名： 學(xué)號(hào)：臨沂師范學(xué)院數(shù)學(xué)本科階段性測試運(yùn)籌學(xué)試題（3）題號(hào)一二三四五六七八九十總分得分閱卷人填空題（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（）用圖解法確定下

2、面線性規(guī)劃問題的最優(yōu)解 （）單純行法確定下面線性規(guī)劃問題的最優(yōu)解（）出下面線性規(guī)劃問題的對偶問題（）用對偶單純行法確定下面線性規(guī)劃問題的最優(yōu)解三、證明題(25分)(10)設(shè)DRn 是非空凸集，是定義在D上的凸函數(shù)，是一個(gè)實(shí)數(shù)，則集合L=x D| 是一個(gè)凸集。(10)對任何線性規(guī)劃問題,其對偶的對偶還是原問題。（）寫出下面線性規(guī)劃的條件臨沂師范學(xué)院數(shù)學(xué)系階段性測試(3)試題標(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ì)算題（）（，）D v=(1,3) 分如圖給出了這一問題的可行域 F，它是由線段AB,BC,C

3、D,DA圍成的凸多邊形(凸集)，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分 （敘述不標(biāo)準(zhǔn)者酌情扣分）（）解：首先，引入三個(gè)松馳變量，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形的線性規(guī)劃問題 分取，為初始基變量得下面單純形表基變量右端項(xiàng)分取為出基變量，為出基變量，以為旋轉(zhuǎn)主元，得下表

4、基變量右端項(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ī)劃問題：易知，其對