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

專業(yè)： 科類： 科　班級(jí)：　　 級(jí)　　班　　姓名：　　　　 學(xué)號(hào)：　　　　　　　　 ………………………………裝………………………………訂……………………………線………………………… ………………………………裝………………………………訂……………………………線………………………… 專業(yè)： 科類： 科　班級(jí)：　　 級(jí)　　班　　姓名：　　　　 學(xué)號(hào)：　　　　　　　　 臨沂師范學(xué)院數(shù)學(xué)本科階段性測(cè)試 《運(yùn)籌學(xué)》試題（2） 題號(hào) 一 二 三 四 五 六 七 八 九 十 總分 得分 閱卷人 一、 填空題（３５=１５分） １．對(duì)于集合和，若滿足對(duì)任意的和有 則稱Ｄ為＿＿＿＿＿，ｆ（ｘ）為＿＿＿＿＿＿． ２．設(shè)ｆ（ｘ）在ｘ＊的一個(gè)鄰域內(nèi)二階連續(xù)可微，那么ｘ＊為無約束最優(yōu)化問題的一個(gè)最優(yōu)解的二階必要條件是＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿． ３．標(biāo)準(zhǔn)形線性規(guī)劃的可行點(diǎn)是Ｆ的頂點(diǎn)的充分必要條件是＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿． ４．單純行法作為線性規(guī)劃的一個(gè)求解算法，其算法復(fù)雜性＿＿＿＿＿＿＿＿＿＿． ５．對(duì)于標(biāo)準(zhǔn)形線性規(guī)劃問題，如果有有限的最優(yōu)解，則＿＿＿＿＿＿＿＿＿＿＿＿＿＿取得。 二．計(jì)算題（６0分） 1．（１０）用圖解法確定下面線性規(guī)劃問題的最優(yōu)解 　　　　 ２． （２０）單純行法確定下面線性規(guī)劃問題的最優(yōu)解 ３． （１０）出下面線性規(guī)劃問題的對(duì)偶問題 ４．（２０）用對(duì)偶單純行法確定下面線性規(guī)劃問題的最優(yōu)解 三、證明題（２５分） 1．(1０)凸規(guī)劃問題的一個(gè)局部最優(yōu)解一定是它的全局最優(yōu)解． ２．（１０）對(duì)任何線性規(guī)劃問題,其對(duì)偶的對(duì)偶還是原問題。 ３．（５）敘述強(qiáng)對(duì)偶定理． 臨沂師范學(xué)院數(shù)學(xué)系階段性測(cè)試(2) <<運(yùn)籌學(xué)>>試題標(biāo)準(zhǔn)答案 一、 填空題：（３５=１５） 1、凸集，凸函數(shù)， 2、， 3、ｘ是一個(gè)基本可行解， 4、不是多項(xiàng)式時(shí)間算法 ５、必可在其可行域的某個(gè)頂點(diǎn) Ａ（１，２） Ｂ Ｃ Ｄ ｘ1-2x2=z (-1,2) 二、 計(jì)算題（６０）　　　　　　　　　　　　　 ?。保　　　　　　　　　　　　　　　　　　　　　　? 　　　　　　　　　　　　　　　　　　　　　　　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　　　　　　　　　　　?。? 　　　　　　　　　　　　 　　　　　　　　　　　?。牛? 　　　　　　　　　　　　　　Ｄ　　　　　　　　　　　　?。? 　　　　　　　　　　　　　　　　　　　　　　　　　　　４ ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．6分 如圖給出了這一問題的可行域 F，它是由線段AB,BC,CD,DA圍成的凸多邊形(凸集)， A,B, C,D是這個(gè)凸集的４個(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*=1,x2*=２.．．．．．．．．．．．．．．．１０分 （敘述不標(biāo)準(zhǔn)者酌情扣分） ２．（２０）解：首先，引入三個(gè)松馳變量和人工變量，，，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形的線性規(guī)劃問題 ．．．．．．．．．．．．．．．．．．．．．．．．．４分 取，，為初始基變量得下面單純形表 基變量 　　　　　　　　　　　　　　　　 右端項(xiàng) －ｆ ２M+3　－4M　　?。?　　　０　　?。汀　　。啊　。? 　 １　　?。薄　　　。薄　　。薄　　。啊　　。啊　。? －２　　?。薄　　。薄　　。啊　。薄　　。薄　。? ０　　?。场　　　。薄　　。啊　　。啊　　。啊　。? 　　 　４ １ ９ 　　　　　　　　　　　　　　　?。阜? 取為出基變量，為入基變量，以１為旋轉(zhuǎn)主元，得下表 基變量 　　　　　　　　　　　　　　　 右端項(xiàng) －ｆ －６M+3?。啊。矗停薄　。啊。常汀　。矗汀　。? 　 ３　　?。啊　　　。病　　。薄　　。薄　。薄　。? －２　　?。薄　　。薄　　。啊　。薄　　。薄　。? ６　　?。啊　　　。础　　。啊　　。场　。场　。? 　　 ?。? １ ６ 　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１２分 取為出基變量，為入基變量，以６為旋轉(zhuǎn)主元，得下表 基變量 　　　　　　　　　　　 右端項(xiàng) －ｆ ０　?。啊。场　。啊。　。停。停? 　 ０　　０　　０　?。薄。　　　　　。? ０　　１　　　?。啊　。啊　　。啊　　　? １　　０　　　?。啊　　　。　　　? 　　 　 ０ ３ １ 　　　　　　　　　　　　　　　　　　?。保斗? 取為出基變量，為入基變量，以６為旋轉(zhuǎn)主元，得下表 基變量 　　　　　　　　　　　　 右端項(xiàng) －ｆ 　　０　?。啊　　。啊　　　。停。停? 　 ０　?。啊　。啊　。薄　。　　　　　。? －　?。薄　。啊　。啊　。　　　　　　? 　?。啊　。薄　。啊　　　　。　　　? 　　 　 ０ 至此，所有 ，當(dāng)前的迭代點(diǎn)已是問題的一個(gè)最優(yōu)解，得最優(yōu)解為 ＝ ０， ＝， ＝， ＝０， ＝０． 　　　　　　　　　　　　　　　　　　?。玻胺? （敘述不標(biāo)準(zhǔn)者酌情扣分） ３．（１０）解： 　　　　　　　　　?。保胺? ４．（２０）解．首先，將本題中的約束轉(zhuǎn)化成型，再引入松馳變量得 　　　　　　　　　　　　　　　　　?。捶? 取，為初始基變量得下面單純形表 基變量 　　　　　　　　 右端項(xiàng) －ｆ ３　?。病　　。础　。啊　。? ?。? －２?。薄　　。啊　。薄　。啊? ０?。病　　。薄　。啊　。? 　 ?。? －１０ 　　　　　　　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．．．．．８分 取為出基變量，為出基變量，以－２為旋轉(zhuǎn)主元，得下表 基變量 　　　　　　　　 右端項(xiàng) －ｆ ３　?。啊　　。怠　。啊　。? －１０ －２?。啊　　　　。薄　　? ０　?。薄　。　。啊。? 　 －１０ ５ 　　　　　　　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．．．１２分 取為出基變量，為出基變量，以－２為旋轉(zhuǎn)主元，得下表 基變量 　　　　　　　　 右端項(xiàng) －ｆ ０　?。啊　。怠　　。? －25 １　?。啊。。　。? ０　?。薄　。　。啊。? 　 ５ ５ 　　　　　　　　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．１６分 至此，右端項(xiàng)的所有分量都已非負(fù)，當(dāng)前的迭代點(diǎn)已是問題的一個(gè)最優(yōu)解，得最優(yōu)解為＝５，＝５，＝０，相應(yīng)的最優(yōu)目標(biāo)函數(shù)值為２５．．．．．．．．．．．．．．．．．．．２０分 （敘述不標(biāo)準(zhǔn)者酌情扣分） 三、 證明題(25) 　?。保ǎ保埃┳C明：設(shè)是凸規(guī)劃問題的一個(gè)局部最優(yōu)解，但不是它的全局最優(yōu)解，則存在另一個(gè)可行點(diǎn)，設(shè)為滿足．．．．．．．．．．．．．．．．．．．．．．．．．．．２分 有可行集的凸性，對(duì)于任意的，點(diǎn)都是可行點(diǎn)．．．．．．．．．５分 又根據(jù)目標(biāo)函數(shù)的凸性有 　　　　　　　　　　　　　　　　　　?。阜? 這表明在的任意小的鄰域內(nèi)都存在函數(shù)值小于的可行點(diǎn)，這與是凸規(guī)劃問題的一個(gè)局部最優(yōu)解相矛盾，因此，函數(shù)值小于的可行點(diǎn)不存在，一定是凸規(guī)劃問題的一個(gè)全局最優(yōu)解．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１０分 ２．（１０）證明：因?yàn)槿魏涡问降木€性問題都可以轉(zhuǎn)化為經(jīng)典形式，在此我們只考慮經(jīng)典形線性規(guī)劃問題： 易知，其對(duì)偶問題為： ．．．．．．．．．．．．．．．．．．．．．．．５分 將對(duì)偶形式轉(zhuǎn)化為經(jīng)典形式： 　　　　　　　　　　　　　 它的對(duì)偶為 　　　　　　　　　　　　　　　 經(jīng)整理即得原線性規(guī)劃問題． 　　　　　　　　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．１０分 ３（５）強(qiáng)對(duì)偶定理：如果互為對(duì)偶的兩個(gè)線性規(guī)劃問題中一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解,且兩者的最優(yōu)目標(biāo)函數(shù)值相等。 　　　　　　　　　　　　　　　　　?。捣?