經(jīng)典運(yùn)籌學(xué)試題15套

試卷一一、

填空題（15）1．在求極小值的線性規(guī)劃問(wèn)題中，松弛變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)為，人工變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)為。2.某極小化線性規(guī)劃問(wèn)題（P）一個(gè)“≤”型的約束所對(duì)應(yīng)的（P）對(duì)偶問(wèn)題的決策變量0，（P）中的一個(gè)取值“≤0”的決策變量對(duì)應(yīng)了（P）對(duì)偶問(wèn)題的一個(gè)3.在線性規(guī)劃的迭代過(guò)程中，保證經(jīng)過(guò)一次迭代得到的仍是基可行解。4.若整數(shù)規(guī)劃,在時(shí)均取得最優(yōu)解，則其最優(yōu)解，。5.用動(dòng)態(tài)規(guī)劃求解某生產(chǎn)計(jì)劃問(wèn)題。已知第一期期初庫(kù)存為0，第五期期末庫(kù)存也必須是0，每期的生產(chǎn)數(shù)量不少于5，決策變量表示第k期生產(chǎn)量，狀態(tài)變量表示第k期末庫(kù)存量，則第三期的狀態(tài)變量的取值范圍是。（已知第1~5期市場(chǎng)對(duì)產(chǎn)品的需求量分別為2，4，3，4，4。）二、

選擇題（15）1.關(guān)于線性規(guī)劃的可行解和基解，下面敘述正確。A.可行解必是基解；B.基解必是可行解C.可行解必然是非基變量為0，基變量均非負(fù)；D.非基變量均為0得到的解均為基解。2.下列規(guī)定中，是繪制網(wǎng)絡(luò)圖時(shí)可以不遵循的。A.網(wǎng)絡(luò)圖只能有一個(gè)起始點(diǎn)及一個(gè)終止點(diǎn)；B.網(wǎng)絡(luò)圖中的有向邊不允許交叉；C.網(wǎng)絡(luò)圖中不允許出現(xiàn)回路；D.任兩個(gè)結(jié)點(diǎn)之間，最多只能有一條有向邊。3.求解總利潤(rùn)最大的運(yùn)輸問(wèn)題時(shí)，下列敘述正確。A.應(yīng)選擇最大檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量為換入變量；B.應(yīng)選擇正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量為換入變量；C.應(yīng)選擇最小檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量為換入變量；D.應(yīng)選擇負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量為換入變量。4.對(duì)某線性規(guī)劃問(wèn)題（P）及其對(duì)偶問(wèn)題（D），下列結(jié)果永遠(yuǎn)不會(huì)同時(shí)出現(xiàn)。A.（P）有可行解，（D）也有可行解；B.（P）無(wú)可行解，（D）也無(wú)可行解；C.（P）有無(wú)界解，（D）也有無(wú)界解；D.（P）有最優(yōu)解，（D）也有最優(yōu)解。5.一個(gè)連通圖的最小支撐樹，該最小支撐樹上邊的總長(zhǎng)度。A.是唯一存在的；B.可能不唯一；C.可能不存在；D.一定有多個(gè)。三、簡(jiǎn)答題（15）什么是基解？什么是基可行解？2.試比較求解Max化、Min化線性規(guī)劃問(wèn)題的單純形法在最優(yōu)性判別定理及迭代過(guò)程上有何不同（假設(shè)模型中不含人工變量）。3.網(wǎng)絡(luò)計(jì)劃中作業(yè)的四種時(shí)差的名稱及計(jì)算公式是什么？4.在中國(guó)郵遞員問(wèn)題的最優(yōu)解判別定理是什么？5.為什么說(shuō)產(chǎn)銷平衡的運(yùn)輸問(wèn)題必有最優(yōu)解？四、判斷對(duì)錯(cuò)（10）1.若為L(zhǎng)P的可行解，則亦為L(zhǎng)P的基本解。（）2.設(shè)LP的可行域?yàn)镈，D非凸集，則LP的最優(yōu)點(diǎn)必在D的頂點(diǎn)上。（）3.若LP經(jīng)過(guò)若干次迭代后已得到一退化的最優(yōu)解，則繼續(xù)迭代下去必可得到非退化的最優(yōu)解。（）4．如果線性規(guī)劃的原問(wèn)題和對(duì)偶問(wèn)題都具有可行解，則該線性規(guī)劃問(wèn)題一定具有有限最優(yōu)解。（）5．一旦一個(gè)人工變量在迭代中變?yōu)榉腔兞亢?，該變量及相?yīng)列的數(shù)字可以從單純形表中刪除，而不影響計(jì)算結(jié)果。（）五、計(jì)算題（35）1.用對(duì)偶單純形法求解2.用單純形法求解如下目標(biāo)規(guī)劃的滿意解：出逆序解法求解下列動(dòng)態(tài)規(guī)劃問(wèn)題的求解模型：六、建模題（10）某工廠用原料A，B，C加工成三種不同牌號(hào)的產(chǎn)品甲、乙、丙。已知各種牌號(hào)產(chǎn)品中A，B，C含量，原料成本，各種原料的每月限制用量，三種牌號(hào)產(chǎn)品的單位加工費(fèi)及售價(jià)如表所示：甲乙丙原料成本（元/千克）每月限制用量（千克）A≥60%≥15%2.002000B1.502500C≤20%≤60%≤50%1.001200加工費(fèi)（元/千克）0.500.400.30售價(jià)3.42.852.25問(wèn)該廠每月應(yīng)生產(chǎn)這三種牌號(hào)產(chǎn)品各多少千克，使該廠獲利最大？試建立這個(gè)問(wèn)題的線性規(guī)劃的數(shù)學(xué)模型（不求解）。

試卷二一、

填空題1．一般線性規(guī)劃求解的結(jié)果有種，分別為。2.若線性規(guī)劃的原問(wèn)題為MaxZ=CX;AX≤b；X≥0，其最優(yōu)解為x*,則其對(duì)偶問(wèn)題的形式為，在最優(yōu)點(diǎn)的目標(biāo)函數(shù)值為。3．求解目標(biāo)規(guī)劃問(wèn)題時(shí)，某非基變量的檢驗(yàn)數(shù)為：-P1+10P2-2P3,該變量可否作為換入變量？。4．若整數(shù)規(guī)劃,在時(shí)均取得最優(yōu)解，則其最優(yōu)解，。5.用動(dòng)態(tài)規(guī)劃求解某生產(chǎn)計(jì)劃問(wèn)題。已知第一期期初庫(kù)存為0，第五期期末庫(kù)存也必須是0，每期的生產(chǎn)數(shù)量不少于5，決策變量表示第k期生產(chǎn)量，狀態(tài)變量表示第k期末庫(kù)存量，則第三期的狀態(tài)變量的取值范圍是。（已知第1~5期市場(chǎng)對(duì)產(chǎn)品的需求量分別為2，4，3，4，4。）二、

選擇題1．用圖解法求解目標(biāo)函數(shù)為MaxZ=2x1+3x2的線性規(guī)劃問(wèn)題時(shí)，目標(biāo)函數(shù)等值線應(yīng)沿方向移動(dòng)，可以使目標(biāo)函數(shù)值降低。A.（2，3）；B.（2，-3）；C.（-2，3）；D.（-2，-3）；2.對(duì)某線性規(guī)劃問(wèn)題（P）及其對(duì)偶問(wèn)題（D），下列結(jié)果永遠(yuǎn)不會(huì)同時(shí)出現(xiàn)。A.（P）有可行解，（D）也有可行解；B.（P）無(wú)可行解，（D）也無(wú)可行解；C.（P）有無(wú)界解，（D）也有無(wú)界解；D.（P）有最優(yōu)解，（D）也有最優(yōu)解。3．對(duì)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題，設(shè)產(chǎn)地有m個(gè)。銷地有n個(gè)，則在基可行解中基變量的個(gè)數(shù)為。A.m+n個(gè)；B.m+n-1個(gè)；C.m+n+1個(gè)；D.m+n-2個(gè)；4.一個(gè)連通圖的最小支撐樹，該最小支撐樹上邊的總長(zhǎng)度。A.是唯一存在的；B.可能不唯一；C.可能不存在；D.一定有多個(gè)。5.在增廣鏈中，。A.所有的前向弧都是飽和弧，所有的后向弧都是零流?。籅.所有的前向弧都是非飽和弧，所有的后向弧都是零流??；C.所有的前向弧都是飽和弧，所有的后向弧都是非零流??；D.所有的前向弧都是非飽和弧，所有的后向弧都是非零流弧。三、簡(jiǎn)答題1．求解Max化線性規(guī)劃問(wèn)題時(shí)，在迭代過(guò)程中選擇最大正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量作為換入變量，可以使目標(biāo)函數(shù)值增加最快。這正確嗎？說(shuō)明理由。2.試比較求解Max化、Min化線性規(guī)劃問(wèn)題的單純形法在最優(yōu)性判別定理及迭代過(guò)程上有何不同（假設(shè)模型中不含人工變量）。3.網(wǎng)絡(luò)計(jì)劃中作業(yè)的四種時(shí)差的名稱及計(jì)算公式是什么？4.在中國(guó)郵遞員問(wèn)題的最優(yōu)解判別定理是什么？5.為什么說(shuō)產(chǎn)銷平衡的運(yùn)輸問(wèn)題必有最優(yōu)解？四、判斷對(duì)錯(cuò)（10）1.若為L(zhǎng)P的可行解，則亦為L(zhǎng)P的基本解。（）2.設(shè)LP的可行域?yàn)镈，D非凸集，則LP的最優(yōu)點(diǎn)必在D的頂點(diǎn)上。（）LP經(jīng)過(guò)若干次迭代后已得到一退化的最優(yōu)解，則繼續(xù)迭代下去必可得到非退化的最優(yōu)解。（）4．如果線性規(guī)劃的原問(wèn)題和對(duì)偶問(wèn)題都具有可行解，則該線性規(guī)劃問(wèn)題一定具有有限最優(yōu)解。（）5．一旦一個(gè)人工變量再迭代中變?yōu)榉腔兞亢?，該變量及相?yīng)列的數(shù)字可以從單純形表中刪除，而不影響計(jì)算結(jié)果。（）五、計(jì)算題1.用對(duì)偶單純形法求解2.用單純形法求解如下目標(biāo)規(guī)劃的滿意解：3.寫出逆序解法求解下列動(dòng)態(tài)規(guī)劃問(wèn)題的求解模型：六、建模題下表給出了A，B，C，D，E五種合金含鉛，鋅，錫的百分率?，F(xiàn)要用這五種合金熔煉成一種含鉛，鋅，錫含量比例為3：2：5的新合金。求總費(fèi)用最小的生產(chǎn)方案。只建模型，不求解。合金ABCDE鉛含量（%）3010501050鋅含量（%）6020201010錫含量（%）1070308040單價(jià)（元/kg）8.56.08.95.78.8試卷三建立下列各問(wèn)題的運(yùn)籌學(xué)模型（共30分）1、有一艘貨輪，分前、中、后三個(gè)艙位，它們的容積與最大允許載重量如表1所示?，F(xiàn)有三種貨物待運(yùn)，已知有關(guān)數(shù)據(jù)列于表2。為了航運(yùn)安全，要求前、中、后艙在實(shí)際載重量上大體保持各艙最大允許載重量的比例關(guān)系，具體要求前、后艙分別與中艙之間載重量比例上偏差不超過(guò)15%，前、后艙之間不超過(guò)10%。問(wèn)該貨輪應(yīng)裝載A，B，C各多少件，運(yùn)費(fèi)收入為最大？試建立這個(gè)問(wèn)題的線性規(guī)劃模型。（15分）表1前艙中艙后艙最大允許載重量（噸）200030001500容積（立方米）400054001500表2商品數(shù)量（件）每件體積（立方米/件）每件重量（噸/件）運(yùn)價(jià)（元/件）A6001081000B100056700C800756002、設(shè)有一紡織廠可生產(chǎn)衣料和窗簾布共兩種產(chǎn)品。該廠兩班生產(chǎn)，每周的生產(chǎn)時(shí)間為80小時(shí)，無(wú)論生產(chǎn)哪種產(chǎn)品，該廠每小時(shí)的產(chǎn)量都是1千米。據(jù)市場(chǎng)預(yù)測(cè)，每周窗簾布的銷售量為70千米，而衣料的銷售量為45千米。假定窗簾布和衣料的單位利潤(rùn)分別為2.5千元/千米和1.5千元/千米，上級(jí)主管部門對(duì)該廠提出了以下四個(gè)順序目標(biāo)：（1）盡可能避免開工不足；（2）盡可能限制每周加班時(shí)間不超過(guò)10小時(shí)；（3）盡可能滿足市場(chǎng)需求；（4）盡可能減少加班時(shí)間。問(wèn)該廠應(yīng)如何安排生產(chǎn)才能使這些目標(biāo)依序?qū)崿F(xiàn)，試建立其數(shù)學(xué)模型。（15分）二、計(jì)算題（每小題10分，共20分）：1．求贏得矩陣為下列矩陣的對(duì)策問(wèn)題的解和對(duì)策值。（共10分）2．某公司要把4個(gè)有關(guān)能源工程項(xiàng)目承包給4個(gè)互不相關(guān)的外商投標(biāo)者，規(guī)定每個(gè)承包商只能且必須承包一個(gè)項(xiàng)目，試在總費(fèi)用最小的條件下確定各個(gè)項(xiàng)目的承包者，總費(fèi)用為多少？各承包商對(duì)工程的報(bào)價(jià)如表3所示：（共10分）表3項(xiàng)目投標(biāo)者ABCD甲15182124乙19232218丙26171619丁192123173．已知運(yùn)輸問(wèn)題的調(diào)運(yùn)和運(yùn)價(jià)表如下，求最優(yōu)調(diào)運(yùn)方案和最小總費(fèi)用。（共10分）。銷地產(chǎn)地B1B2B3產(chǎn)量A159215A231718A362817銷量181216三、模型求解（每小題20分，共40分）1．求解下列線性規(guī)劃問(wèn)題：共20分maxz=2x1+7x2-3x3x1+3x2+4x3≤30（第一種資源限制約束）x1+4x2-x3≤10（第二種資源限制約束）x1、x2、x3≥0求出該問(wèn)題的最優(yōu)解和最優(yōu)值；求出該問(wèn)題的對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)值；第二種資源限量由10變?yōu)?0，最優(yōu)解是否改變；若改變請(qǐng)求出新的最優(yōu)解；增加一個(gè)新變量x6，其目標(biāo)函數(shù)系數(shù)為3，技術(shù)消耗系數(shù)為，最優(yōu)解是否改變；若改變請(qǐng)求出新的最優(yōu)解。2．某科研項(xiàng)目由三個(gè)小組用不同手段分別研究，它們失敗的概率各為0.40，0.60，0.80。為了減少三個(gè)小組都失敗的可能性，現(xiàn)決定給三個(gè)小組中增派兩名高級(jí)科學(xué)家，到各小組后，各小組科研項(xiàng)目失敗的概率如表6所示：表6高級(jí)科學(xué)家數(shù)小組12300．400．600．8010．200．400．5020．150．200．30問(wèn)：應(yīng)如何分派科學(xué)家才使三個(gè)小組都失敗的概率（即科研項(xiàng)目最終失敗的概率）最小？試建立其動(dòng)態(tài)規(guī)劃模型并求解。（共20分）。試卷四一、建立下列各問(wèn)題的運(yùn)籌學(xué)模型（共30分）1．一個(gè)木材儲(chǔ)運(yùn)公司有很大的倉(cāng)庫(kù)用以儲(chǔ)運(yùn)出售木材。由于木材季度價(jià)格的變化，該公司于每季度初購(gòu)進(jìn)木材，一部分于本季度內(nèi)出售，一部分儲(chǔ)存起來(lái)以后出售。已知該公司倉(cāng)庫(kù)的最大儲(chǔ)存量為20萬(wàn)米3，儲(chǔ)存費(fèi)用為（70+100u）千元/萬(wàn)米3，u為存儲(chǔ)時(shí)間（季度數(shù)）。已知每季度的買進(jìn)賣出價(jià)及預(yù)計(jì)的銷售量如表1所示。表1季度買進(jìn)價(jià)（萬(wàn)元/萬(wàn)米3）賣出價(jià)（萬(wàn)元/萬(wàn)米3）預(yù)計(jì)銷售量（萬(wàn)米3）冬410425100春430440140夏460465200秋450455160由于木材不宜久貯，所有庫(kù)存木材應(yīng)于每年秋末售完。為使售后利潤(rùn)最大，試建立這個(gè)問(wèn)題的線性規(guī)劃模型。（15分）2．某?；饡?huì)有一筆數(shù)額為5000萬(wàn)元的基金，打算將其存入銀行。當(dāng)前銀行存款的利率見下表2。取款政策與銀行的現(xiàn)行政策相同，定期存款不提前取，活期存款可任意支取。?；饡?huì)計(jì)劃在5年內(nèi)每年用部分本息獎(jiǎng)勵(lì)優(yōu)秀師生，要求每年的獎(jiǎng)金額大致相同，且在5年末仍保留原基金數(shù)額。?；饡?huì)希望獲得最佳的基金使用計(jì)劃，以提高每年的獎(jiǎng)金額。請(qǐng)你幫助?；饡?huì)設(shè)計(jì)一個(gè)基金最佳使用方案，試建立其模型。（15分）表2銀行存款稅后年利率（%）活期0.792半年期1.664一年期1.800二年期1.944三年期2.160五年期2.304二、計(jì)算題（第一小題15分，第二、三每小題10分，共35分）1．設(shè)有線性規(guī)劃問(wèn)題其中b1,b2是常數(shù)，且已知此規(guī)劃的最終表為：C52300CBXBbx1x2x3x4x55x1301b2100x5100c-8-11Z1500a7de試確定該模型中和其最終表中的所有參數(shù)。（共15分）知運(yùn)輸問(wèn)題的調(diào)運(yùn)和運(yùn)價(jià)表如下，求最優(yōu)調(diào)運(yùn)方案和最小總費(fèi)用。共10分。表4銷地產(chǎn)地B1B2B3產(chǎn)量A11267A204212A331511銷量1010103．求贏得矩陣為下列矩陣的矩陣對(duì)策的解及對(duì)策的值。共10分。三、模型求解（第一小題20分，第二小題15分，共35分）1．求解下列線性規(guī)劃問(wèn)題：共20分maxz=2x1+7x2-3x3x1+3x2+4x3≤30（第一種資源限制約束）x1+4x2-x3≤10（第二種資源限制約束）x1、x2、x3≥0出該問(wèn)題的最優(yōu)解和最優(yōu)值；求出該問(wèn)題的對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)值；第二種資源限量由10變?yōu)?0，最優(yōu)解是否改變；若改變請(qǐng)求出新的最優(yōu)解；第一種產(chǎn)品x1的價(jià)值系數(shù)由2改為4，其最優(yōu)解是否改變。2．用隱枚舉法求解下列0—1規(guī)劃。（15分）maxz=8x1+2x2-4x3-7x4-5x53x1+3x2+x3+2x4+3x5≤45x1+3x2-2x3-x4+x5≤4xj=0或1(j=1,2,…,5)試卷五建立下列各問(wèn)題的運(yùn)籌學(xué)模型（共30分）1、某公司現(xiàn)有300萬(wàn)元準(zhǔn)備在未來(lái)的三年內(nèi)投資，根據(jù)考察和洽談的意向確定了四個(gè)可以考慮的項(xiàng)目：項(xiàng)目1：在三年內(nèi)，投資人應(yīng)在每年年初投資，年末可獲利20%，每年取息后可將本息一起重新投資，獲利率仍為20%。項(xiàng)目2：在三年內(nèi)，投資人應(yīng)在第一年年初投資，兩年末可獲利50%，取息后，可將本息一起重新投資，仍在兩年末獲利50%；但本項(xiàng)目投資最多不得超過(guò)200萬(wàn)元。項(xiàng)目3：在三年內(nèi)，投資人應(yīng)在第二年年初投資，兩年后可獲利60%，本項(xiàng)目投資最多不得超過(guò)150萬(wàn)元。項(xiàng)目4：：在三年內(nèi)，投資人應(yīng)在第三年年初投資，一年內(nèi)可獲利40%，本項(xiàng)目投資最多不得超過(guò)100萬(wàn)元。請(qǐng)協(xié)助投資人設(shè)計(jì)能在第三年末獲得最高收益的三年投資計(jì)劃，建立LP模型。（共15分）2、（生產(chǎn)管理問(wèn)題）某工廠生產(chǎn)A、B兩種產(chǎn)品，這兩種產(chǎn)品都需要經(jīng)過(guò)加工和裝配兩道工序。已知每道工序在每個(gè)作業(yè)班內(nèi)可利用的生產(chǎn)能力分別為210小時(shí)和120小時(shí)，每件產(chǎn)品加工和裝配的定額工時(shí)和單件產(chǎn)品提供的毛利如表1所示：表1工廠領(lǐng)導(dǎo)提出下列目標(biāo)：（1）每個(gè)作業(yè)班的毛利不少于9800元；（2）充分利用兩個(gè)工序的工時(shí)，且已知加工工時(shí)費(fèi)是裝配工時(shí)費(fèi)的二倍；（3）盡量減少加班。問(wèn)：該工廠應(yīng)如何生產(chǎn)，才能使這些目標(biāo)依序?qū)崿F(xiàn)？試建立其數(shù)學(xué)模型。（15分）二、計(jì)算題（每小題10分，共30分）1．某公司要把4個(gè)有關(guān)能源工程項(xiàng)目承包給4個(gè)互不相關(guān)的外商投標(biāo)者，規(guī)定每個(gè)承包商只能且必須承包一個(gè)項(xiàng)目，試在總費(fèi)用最小的條件下確定各個(gè)項(xiàng)目的承包者，總費(fèi)用為多少？各承包商對(duì)工程的報(bào)價(jià)如表2所示：（10分）表2項(xiàng)目投標(biāo)者ABCD甲15182124乙19232218丙26171619丁192123172．求贏得矩陣為下列矩陣的矩陣對(duì)策的解及對(duì)策的值。共10分。3．已知運(yùn)輸問(wèn)題的調(diào)運(yùn)和運(yùn)價(jià)表如下，求最優(yōu)調(diào)運(yùn)方案和最小總費(fèi)用。共10分。銷地產(chǎn)地B1B2B3產(chǎn)量A162912A235114A347810銷量91011三、模型求解（每小題15分，共40分）1、某公司打算在三個(gè)不同的地區(qū)設(shè)置4個(gè)銷售點(diǎn)，根據(jù)市場(chǎng)預(yù)測(cè)部門估計(jì)，在不同的地區(qū)設(shè)置不同的數(shù)量的銷售點(diǎn)，每月可得到的利潤(rùn)如表2所示。試問(wèn)在各個(gè)地區(qū)應(yīng)如何設(shè)置銷售點(diǎn)，才能使每月獲得的總利潤(rùn)最大？其最大利潤(rùn)是多少？并給出最優(yōu)方案。（15分）表2銷售點(diǎn)利潤(rùn)地區(qū)012341016253032201217212230101416172、求解下列線性規(guī)劃問(wèn)題：共25分maxz=4x1+x2+2x38x1+3x2+x3≤2（第一種資源限制約束）6x1+x2+x3≤8（第二種資源限制約束）x1、x2、、x3≥0求出該問(wèn)題的最優(yōu)解和最優(yōu)值；求出該問(wèn)題的對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)值；第一種資源限量由2變?yōu)?，最優(yōu)解是否改變，若改變請(qǐng)求出新的最優(yōu)解；現(xiàn)有新產(chǎn)品丁，每單位產(chǎn)品需消耗第一種資源2單位，消耗第二種資源3單位，問(wèn)該產(chǎn)品的售價(jià)至少為多少時(shí)才值得生產(chǎn)？由于資源缺乏，現(xiàn)有第三種原來(lái)并不受約束資源現(xiàn)在受到限制，限制方程為：，問(wèn)此時(shí)最優(yōu)解是否受到影響，若需要改變，請(qǐng)求出新的最優(yōu)解。試卷六1.試證（1）對(duì)稱性：線性規(guī)劃的對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。（2）弱對(duì)偶性：若是原問(wèn)題的可行解,是對(duì)偶問(wèn)題的可行解,則。（20％）2.某制造公司有兩臺(tái)機(jī)器，制造產(chǎn)品A和B，每種產(chǎn)品在每臺(tái)機(jī)器上所需要的操作時(shí)間，以及每臺(tái)機(jī)器在一天可允許的操作時(shí)間，（單位為小時(shí)）均由表列出：機(jī)器產(chǎn)品A產(chǎn)品B一天總?cè)萘?231823215考慮到正常銷路，可以認(rèn)為公司可能賣出的產(chǎn)品與能生產(chǎn)的產(chǎn)品一樣多。每個(gè)產(chǎn)品的銷價(jià)分別為500元和600元。（1）請(qǐng)制定一份最佳生產(chǎn)計(jì)劃，使其總收入達(dá)到最大。試建立此問(wèn)題的數(shù)學(xué)模型。（2）用單純形法求解此問(wèn)題。（3）若把機(jī)器的工作時(shí)間出租,問(wèn)應(yīng)如何定價(jià)?（25％）設(shè)問(wèn)題的對(duì)偶問(wèn)題的最優(yōu)解為，求原問(wèn)題的最優(yōu)解。（15％）4.一家晝夜服務(wù)的飯店每天24小時(shí)中需要的服務(wù)員如下表所示：起止時(shí)間服務(wù)員的最少人數(shù)2—646—10810—141014—18718—221222—24每個(gè)服務(wù)員每天連續(xù)工作八小時(shí)，且在時(shí)段開始時(shí)上班。求滿足以上要求的最少上班人數(shù)，試建立該問(wèn)題的數(shù)學(xué)模型。（10％）石油公司有三個(gè)石油貯存點(diǎn)，四個(gè)石油需求點(diǎn)。其容量和單位運(yùn)價(jià)如表所示：需求點(diǎn)貯存需求點(diǎn)貯存d1d2d3d4貯存總?cè)萘緼15456100A23366200A32578400需求點(diǎn)的需求量200100150250制定一個(gè)貯存點(diǎn)到需求點(diǎn)的運(yùn)輸計(jì)劃，使總的運(yùn)輸費(fèi)用最小。試建立此問(wèn)題的數(shù)學(xué)模型并且求解。（10％）6.許多非洲國(guó)家由于惡劣氣候而使農(nóng)業(yè)蒙受損害，聯(lián)合國(guó)組織決定派5位農(nóng)業(yè)專家去幫助5個(gè)非洲不發(fā)達(dá)國(guó)家，以提高他們的糧食供應(yīng)。，每位專家能幫助不同國(guó)家提高糧食供應(yīng)達(dá)到不同水平，提高的期望值如下表：專家\國(guó)家ABCDE1121513141721117141619314151118184151312171651315121514假定每個(gè)國(guó)家有同樣的人口，試提出一個(gè)專家指派計(jì)劃，使糧食供應(yīng)的增長(zhǎng)達(dá)到極大。試建立此問(wèn)題的數(shù)學(xué)模型并且用匈牙利法求解。（10％）7.試推導(dǎo)允許缺貨的EOQ模型的最佳實(shí)有訂貨批量為：其中為訂貨費(fèi)，為一件貨物在單位時(shí)間內(nèi)的存貯費(fèi)，為一件貨物在單位時(shí)間內(nèi)的缺貨費(fèi)，為單位時(shí)間內(nèi)的貨物需求量。（10％）試卷七1.試推導(dǎo)允許缺貨的EOQ模型的最佳訂貨周期為：。其中為訂貨費(fèi)，為一件貨物在單位時(shí)間內(nèi)的存貯費(fèi)，為一件貨物在單位時(shí)間內(nèi)的缺貨費(fèi)（15％）2.證明線性規(guī)劃問(wèn)題的弱對(duì)偶性：若是原問(wèn)題的可行解,是對(duì)偶問(wèn)題的可行解,則。（15％）設(shè)問(wèn)題的對(duì)偶問(wèn)題的最優(yōu)解為，求原問(wèn)題的最優(yōu)解。（15％）4.假設(shè)已知各種營(yíng)養(yǎng)物(食品)所含有的各種營(yíng)養(yǎng)成分,諸如蛋白質(zhì)、淀粉、纖維素、維生素、鈣質(zhì)等等。根據(jù)營(yíng)養(yǎng)學(xué)的要求，為保證人的健康成長(zhǎng)，在每日的服用方案中所包含的各種營(yíng)養(yǎng)物成分的數(shù)量不能少于規(guī)定的數(shù)量。制訂一個(gè)滿足最低營(yíng)養(yǎng)要求，而總費(fèi)用最少的配料方案，建立此問(wèn)題的數(shù)學(xué)模型。（10％）5.某汽車廠與一些單位簽訂了生產(chǎn)70輛汽車的合同，按合同規(guī)定明年每季度末分別提供10，15，25和20臺(tái)汽車。該廠各季度的生產(chǎn)能力及生產(chǎn)每輛汽車的成本如表所示：季度交付輛數(shù)生產(chǎn)能力每輛成本(萬(wàn)元)Ⅰ102510．8Ⅱ153511．1Ⅲ253011．0Ⅳ201011．3根據(jù)生產(chǎn)能力，該廠能提前完成合同，但因此要付出相應(yīng)的貯存費(fèi)?，F(xiàn)規(guī)定每輛汽車積壓一個(gè)季度需付0.15萬(wàn)元貯存費(fèi)。試問(wèn)該廠應(yīng)怎樣安排各季的生產(chǎn)計(jì)劃，使總的生產(chǎn)費(fèi)用最少？試建立此問(wèn)題的數(shù)學(xué)模型并且求解。（15％）顧客6.某服務(wù)公司有4名技術(shù)員（A1,A2,A3,A4）為四位顧客（B1,B2,B3,B4）提供服務(wù)，由于技術(shù)員專長(zhǎng)不同其服務(wù)時(shí)間隨顧客而變化。具體服務(wù)時(shí)間由下表給出：顧客服務(wù)時(shí)間B1B2B3B4A136710A25638A328416A48659試為該公司制定一份指派計(jì)劃，使其總服務(wù)時(shí)間達(dá)到最小。試建立此問(wèn)題的數(shù)學(xué)模型并求解。（10％）7.某廠的二種產(chǎn)品I、II分別在四種設(shè)備A1、A2、A3、A4上加工。產(chǎn)品所需的機(jī)器臺(tái)時(shí)、設(shè)備在計(jì)劃內(nèi)的有效臺(tái)時(shí)、每件產(chǎn)品利潤(rùn)如下表所示：A1A2A利潤(rùn)I21402百元II22043百元有效臺(tái)時(shí)1281612（1）請(qǐng)制定一份最佳生產(chǎn)計(jì)劃，使其總收入達(dá)到最大。試建立此問(wèn)題的數(shù)學(xué)模型。（2）用單純形法求解此問(wèn)題。（3）若把機(jī)器臺(tái)時(shí)出租,問(wèn)應(yīng)如何定價(jià)?（20％）試卷八填空題（每空格2分，共28分）1．線性規(guī)劃問(wèn)題的可行解X=（，，．．．）為基本可行解的充要條件是X的正分量對(duì)應(yīng)的系數(shù)列向量是。2．單純形法中，要把數(shù)學(xué)模型化為標(biāo)準(zhǔn)型，須引入；若約束條件中附加變量的系數(shù)是或原約束為，則必須引入，以構(gòu)成初始可行基。3．0-1規(guī)劃的隱枚舉法的基本思想是從所有變量等于出發(fā)，依次指定一些變量為，直到得到一個(gè)可行解。4．目標(biāo)規(guī)劃中，和分別表示變量；對(duì)于第i個(gè)目標(biāo)約束（X）+—=，若希望（X）≤，則目標(biāo)函數(shù)為。5．建立目標(biāo)規(guī)劃的數(shù)學(xué)模型時(shí)，需要排定各目標(biāo)的，確定各目標(biāo)值，各權(quán)系數(shù)。6．動(dòng)態(tài)規(guī)劃模型中，狀態(tài)變量的選擇要能滿足兩個(gè)條件：和。7．動(dòng)態(tài)規(guī)劃中，對(duì)于一個(gè)給定的問(wèn)題，如果有固定的和，則順序遞推和逆序遞推會(huì)得到相同的最優(yōu)結(jié)果。計(jì)算題（共40分）已知線性規(guī)劃的數(shù)學(xué)模型如下，請(qǐng)用圖解法求該模型的最優(yōu)解。（10分）maxZ=4+77+13≤1825+3≤60≥0，（i=1，2）采用隱枚舉法求解0-1規(guī)劃問(wèn)題（15分）minZ=16+10+174+2≤65+2+≥24–2+3≤75+2+3≥1，，=0或13．已知線性規(guī)劃的數(shù)學(xué)模型如下，請(qǐng)寫出對(duì)偶問(wèn)題的數(shù)學(xué)模型，并求其對(duì)偶問(wèn)題的最優(yōu)解。（15分）maxZ=5+3+6+2+≤182++3≤16++=10，≥0，無(wú)約束應(yīng)用題（共70分）1．某農(nóng)場(chǎng)有3萬(wàn)畝農(nóng)田，欲種植玉米、大豆和小麥三種農(nóng)作物。各種作物每畝需施肥料分別為0.12噸、0.2噸、0.15噸。預(yù)計(jì)秋后玉米每畝可收獲500千克，售價(jià)為0.24元/千克，大豆每畝可收獲200千克，售價(jià)為1.20元/千克，小麥每畝可收獲300千克，售價(jià)為0.70元/千克。農(nóng)場(chǎng)年初規(guī)劃時(shí)依次考慮以下的幾個(gè)方面：P1：年終收益不低于350萬(wàn)元；P2：總產(chǎn)量不低于1.25萬(wàn)噸；P3：小麥產(chǎn)量以0.5萬(wàn)噸為宜；P4：大豆產(chǎn)量不少于0.2萬(wàn)噸；P5；玉米產(chǎn)量不超過(guò)0.6萬(wàn)噸；P6：農(nóng)場(chǎng)現(xiàn)能提供5000噸化肥，若不夠，可在市場(chǎng)高價(jià)購(gòu)買，但希望高價(jià)采購(gòu)量愈少愈好。試建立該目標(biāo)規(guī)劃問(wèn)題的數(shù)學(xué)模型（不需要求解）。（16分）2．現(xiàn)指派五位員工去完成五項(xiàng)不同的工作，每人做各項(xiàng)工作所需費(fèi)用（元）如下表所示。問(wèn)應(yīng)該如何指派，才能使總的費(fèi)用最小？相應(yīng)的總費(fèi)用為多少？（16分）任務(wù)人員A1A2A3A4A5B1127979B289666B3717121412B415146610B541071063．某農(nóng)場(chǎng)生產(chǎn)四種農(nóng)作物，每種農(nóng)作物的成本和利潤(rùn)如下：農(nóng)作物肥料（公斤/畝）殺蟲劑（公斤/畝）利潤(rùn)（元）蘿卜4250包心菜2940洋蔥5210土豆0320目前農(nóng)場(chǎng)有400公斤肥料和500公斤殺蟲劑，問(wèn)每種農(nóng)作物種植多少畝才使利潤(rùn)最大？（20分）4．已知四個(gè)城市間的距離如下表所示，求從A城市出發(fā)，經(jīng)其余城市一次且僅一次，最后返回到A城市的最短路徑與距離。（18分）ABCDA--112028B12--1825C239--10D34326--證明題（12分）證明：若線性規(guī)劃問(wèn)題存在可行域，則問(wèn)題的可行域是凸集。試卷九簡(jiǎn)答題（每小題5分，共20分）⑴.什么叫運(yùn)籌學(xué)？它有那些分支？應(yīng)用領(lǐng)域有那些？⑵.利用單純形方法求解線性規(guī)劃問(wèn)題的基本思路是什么？⑶.什么是參數(shù)線性規(guī)劃？靈敏度分析的實(shí)質(zhì)是什么？⑷.試述組成對(duì)策模型的三個(gè)基本要素及各要素的涵義。2.用單純形法求解下列線性規(guī)劃問(wèn)題(本題20分)s.t.3.用對(duì)偶單純形法求解下列線性規(guī)劃問(wèn)題（本題20分）（以上2，3題解在本頁(yè)背面）4.試用最小元素法編制初始調(diào)運(yùn)方案（本題20分）設(shè)有某物資要從調(diào)往，平衡表及運(yùn)價(jià)表如下:平衡表（單位:噸）運(yùn)價(jià)表（單位：元／噸）產(chǎn)地銷地B1B2B3B4產(chǎn)量B1B2B3B4A1437311312A23141928A363974105銷量365620問(wèn)怎樣調(diào)運(yùn)，才能使總運(yùn)費(fèi)最少？5.利用優(yōu)超原則，解下列混合策略的對(duì)策(本題20分)矩陣為對(duì)策時(shí)，的贏得矩陣。試卷十一、某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，其單位利潤(rùn)分別為2元和3元。每生產(chǎn)一件甲產(chǎn)品需勞動(dòng)力3個(gè)，原材料2斤。每生產(chǎn)一件乙產(chǎn)品需勞動(dòng)力6個(gè)，原材料1斤。企業(yè)現(xiàn)有勞動(dòng)力24上，原材料10斤。（15分）試問(wèn)：1、該企業(yè)應(yīng)如何安排生產(chǎn)才能獲得最大利潤(rùn)？2、若另一個(gè)企業(yè)想利用該企業(yè)的這兩種資源（勞動(dòng)力和原材料），該企業(yè)最低應(yīng)以多少價(jià)格轉(zhuǎn)讓？3、甲產(chǎn)品的單位利潤(rùn)在什么范圍內(nèi)變化時(shí)，最優(yōu)生產(chǎn)計(jì)劃（利潤(rùn)最大的生產(chǎn)計(jì)劃）不變。最低轉(zhuǎn)讓價(jià)格又如何變化？二、某拖拉機(jī)廠與農(nóng)機(jī)供銷站簽訂了一項(xiàng)生產(chǎn)100臺(tái)某型小型拖拉機(jī)的合同。按合同規(guī)定，該廠要在今后4個(gè)月內(nèi)的每月內(nèi)各交付一定臺(tái)數(shù)的拖拉機(jī)。為此，該廠生產(chǎn)計(jì)劃科根據(jù)本廠實(shí)際情況列出了一個(gè)生產(chǎn)高度數(shù)據(jù)表（見下表）。若生產(chǎn)出來(lái)的拖拉機(jī)每存儲(chǔ)一月需費(fèi)用100元/臺(tái)，則該廠應(yīng)如何制定最經(jīng)濟(jì)的生產(chǎn)進(jìn)度？（10分）月份合同規(guī)定交付臺(tái)數(shù)生產(chǎn)能力（臺(tái)）單臺(tái)成本（百元）1234152535253035452050525153合計(jì)100130/三、某高校擬開設(shè)文學(xué)、藝術(shù)、音樂(lè)、美術(shù)四個(gè)學(xué)術(shù)講座。每個(gè)講座每周下午舉行一次。經(jīng)調(diào)查知，每周星期一至星期五不能出席某一講座的學(xué)生數(shù)如下表（10分）：

星期講座一二三四五文學(xué)5040603010藝術(shù)4030203020音樂(lè)4030302010美術(shù)2030203030問(wèn)：應(yīng)如何安排一周的講座日程，使不能出席講座的學(xué)生總數(shù)最少，并計(jì)算不能出席講座的學(xué)生總數(shù)。四、某企業(yè)擬開發(fā)一新產(chǎn)品，該新產(chǎn)品投產(chǎn)前工序資料如下表（15分）：工序ABCDEFGHIJKL工序緊前關(guān)系//AADC，EFB，GB，GHGI，J，K緊前關(guān)系工時(shí)（周）4103682328521工時(shí)（周）試求：1、繪制網(wǎng)絡(luò)圖；2、計(jì)算時(shí)間參數(shù)；3、確定關(guān)鍵線路。運(yùn)籌學(xué)試卷十一一、回答下面問(wèn)題(每小題3分)1.在單純形法計(jì)算中,如果不按最小比值規(guī)則確定換基變量,則在下一個(gè)解中一定會(huì)出現(xiàn)。2.原問(wèn)題無(wú)界時(shí)，其對(duì)偶問(wèn)題，反之，當(dāng)對(duì)偶問(wèn)題無(wú)可行解時(shí)，原問(wèn)題。3．已知y0為線性規(guī)劃的對(duì)偶問(wèn)題的最優(yōu)解，若y0>0，說(shuō)明在最優(yōu)生產(chǎn)計(jì)劃中對(duì)應(yīng)的資源。4．已知y0為線性規(guī)劃的對(duì)偶問(wèn)題的最優(yōu)解，若y0=0，說(shuō)明在最優(yōu)生產(chǎn)計(jì)劃中對(duì)應(yīng)的資源。5．已知線形規(guī)劃問(wèn)題的原問(wèn)題有無(wú)窮多最優(yōu)解，則其對(duì)偶問(wèn)題的最優(yōu)解一定是。6．m個(gè)產(chǎn)地n個(gè)銷地的產(chǎn)銷平衡運(yùn)輸問(wèn)題的模型其決策變量的個(gè)數(shù)是個(gè)；基變量的個(gè)數(shù)是個(gè)；決策變量的系數(shù)列向量的特點(diǎn)是。7．用位勢(shì)法求解運(yùn)輸問(wèn)題，位勢(shì)的含義是；行位勢(shì)與列位勢(shì)中有一個(gè)的取值是任意的，這是因?yàn)椤?.用割平面法求解整數(shù)規(guī)劃，割平面割去了；但未割去。9．按教材中的符號(hào)寫出最大流問(wèn)題的數(shù)學(xué)模型。10．什么是截集，何謂最小截集？二、（10分）下表是用單純形法計(jì)算到某一步的表格，已知該線性規(guī)劃的目標(biāo)函數(shù)值為z=14表1cjx1x2x3x4x3x12acd0e101/51σjb-1fg（1）

求a—g的值；（8分）（2）

表中給出的解是否為最優(yōu)解。（2分）三、（每小題6分共12分）車間為全廠生產(chǎn)一種零件，其生產(chǎn)準(zhǔn)備費(fèi)是100元，存貯費(fèi)是0.05元／天·個(gè)，需求量為每天30個(gè)，而且要保證供應(yīng)。（1）

設(shè)車間生產(chǎn)所需零件的時(shí)間很短（即看成瞬時(shí)供應(yīng)）；（2）

設(shè)車間生產(chǎn)零件的生產(chǎn)率是50個(gè)／天。要求在（1）（2）條件下的最優(yōu)生產(chǎn)批量Q*，生產(chǎn)間隔期t*和每天的總費(fèi)用C*。四、（18分）某公司下屬甲、乙兩個(gè)廠，有A原料360斤，B原料640斤。甲廠用A、B兩種原料生產(chǎn)x1,x2兩種產(chǎn)品，乙廠也用A、B兩種原料生產(chǎn)x3,x4兩種產(chǎn)品。每種單位產(chǎn)品所消耗各種原料的數(shù)量及產(chǎn)值、分配等如下工廠甲分配原料乙分配原料產(chǎn)品x1x2x3x4原料AB8

46101603305

8104200310產(chǎn)值（百元）43

34

1．

求各廠最優(yōu)生產(chǎn)計(jì)劃；（12分）2．

問(wèn)公司能否制定新的資源分配方案使產(chǎn)值更高？（6分）五、（10分）ABCDEF2746381163已知有六個(gè)村莊，相互間道路的距離如圖所示，已知各村莊的小學(xué)生數(shù)為：A村50人，B村40人，CABCDEF2746381163

六、（8分）A、B、C、D、E、F分別代表陸地和島嶼，1、2、3……14表示橋梁及其編號(hào)。若河兩岸分別敵對(duì)的雙方部隊(duì)占領(lǐng)，問(wèn)至少應(yīng)切幾座橋梁（具體指出編號(hào)）才能達(dá)到阻止對(duì)方部隊(duì)過(guò)河的目的，試用圖論方法進(jìn)行分析。（提示：以陸地為點(diǎn)，橋梁為弧，兩點(diǎn)之間的橋梁數(shù)為弧的容量。）七、（12分）設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥。各化肥的年產(chǎn)量，各地區(qū)的需求量，化肥的運(yùn)價(jià)如下表所示，請(qǐng)寫出產(chǎn)銷平衡運(yùn)輸表。

B1B2B3B4產(chǎn)量A11613221650A21214181560A3192123…50最低要求3070010

最高要求457030不限

試卷十二一、參數(shù)線性規(guī)劃問(wèn)題（20分）maxz（θ1,θ2）=（5+2θ1）x1+(2-θ1)x2+(3+θ1)x3+0x4-Mx5-Mx6當(dāng)θ1=θ2=0時(shí)，用單純形法求解，得最終單純形表如下

x1x2x3x4x5x6x210312001x45-1021-11cj-zj-10-10-M-M-2要求：1.分析當(dāng)θ2=0時(shí)，θ1在[0，∞]范圍內(nèi)變化時(shí)最優(yōu)解的變化（8分）；2.分析當(dāng)θ1=0時(shí)，θ2在[0，1]范圍內(nèi)變化時(shí)最優(yōu)解的變化（8分）；3.將上述1、2的分析結(jié)果畫兩張圖，第一張以θ1為橫坐標(biāo)，z(θ1)為縱坐標(biāo)，第二張以θ2為橫坐標(biāo)，z(θ2)為縱坐標(biāo)，用以表示目標(biāo)函數(shù)值隨參數(shù)θ1、θ2分別變化的規(guī)律（4分）。二、已知4種化工品A、B、C、D擬存放于7個(gè)庫(kù)房?jī)?nèi)，已知各化工品需存放量（噸），各庫(kù)存最大允許存放量（噸）及存放費(fèi)用（元/噸·年）如下表所示。存放費(fèi)用↘倉(cāng)庫(kù)需存放量1234567化工品A122345575B233115550C443215525D112236480最大允許缺貨量2525406080100100

考慮到安全因素，每個(gè)倉(cāng)庫(kù)內(nèi)最多只能存放一種化工品。要求：1.上述條件下，為使存放費(fèi)用最小，建立相應(yīng)數(shù)學(xué)模型（10分）；2.若各倉(cāng)庫(kù)對(duì)應(yīng)一個(gè)固定啟用費(fèi)用Fj(j=1,…,7)，當(dāng)倉(cāng)庫(kù)不存放任何化工品時(shí)，F(xiàn)j=0；否則不管存放多少，F(xiàn)j固定不變。要求重新建立使啟用費(fèi)用加上存放費(fèi)總和為最小的數(shù)學(xué)模型（10分）。（以上兩個(gè)模型均不需求解）三、司了解到競(jìng)爭(zhēng)對(duì)手將推出一種具有很大市場(chǎng)潛力的新產(chǎn)品，該公司正在研制性能類似產(chǎn)品，并接近完成。為此公司決定加速研制開發(fā)進(jìn)度。已知產(chǎn)品投入市場(chǎng)前尚有4個(gè)階段工作：下表1列出各階段工作正常情況下，采取應(yīng)急措施和采取特別措施時(shí)，完成各階段工作所需時(shí)間（周）。表2列出4個(gè)階段采取相應(yīng)措施時(shí)的費(fèi)用（萬(wàn)元），已知用于該產(chǎn)品研制的剩余費(fèi)用為30萬(wàn)元，要求；1.將此問(wèn)題歸結(jié)為最短路問(wèn)題，畫出相應(yīng)網(wǎng)絡(luò)圖（10分）；2.應(yīng)用Dijkstra算法為該公司找出在費(fèi)用允許條件下完成研制開發(fā)的最佳方案（10分）。表1單位：周措施階段1234正常應(yīng)急54352特殊2231表2單位：萬(wàn)元措施階段1234正常應(yīng)急36693特殊99126四、某項(xiàng)重點(diǎn)攻關(guān)任務(wù)由三個(gè)單位按各自的方案獨(dú)立研制，只要任何一個(gè)單位完成，該項(xiàng)任務(wù)即完成。該攻關(guān)任務(wù)指揮部有2名經(jīng)驗(yàn)豐富人員可用于支援上述研制單位。已知各單位在無(wú)人員支持及分別有1名或2名人員支援時(shí)，其完成研制任務(wù)的概率如下表所示。問(wèn)該指揮部應(yīng)如何分配這兩名支援人員，使完成攻關(guān)任務(wù)的概率為最大。

支援各單位人數(shù)完成研制任務(wù)概率單位1單位2單位30120.600.400.200.800.600.500.850.800.70要求用動(dòng)態(tài)規(guī)劃方法求解：1.建立動(dòng)態(tài)規(guī)劃模型，列出和說(shuō)明各模型要素（10分）2.求數(shù)值解（10分）。五、簡(jiǎn)要回答下列問(wèn)題（20分）1.

運(yùn)輸問(wèn)題的數(shù)學(xué)模型通常表為（6分）minz=s.t=說(shuō)明該模型對(duì)實(shí)際的運(yùn)輸問(wèn)題作出哪幾點(diǎn)簡(jiǎn)化假定。2.希望工程主管部門想在西部地區(qū)某個(gè)市的升初中一年級(jí)學(xué)生中（該市由小學(xué)升初中進(jìn)行了一次全市統(tǒng)一考試）獎(jiǎng)勵(lì)一名優(yōu)希望小學(xué)升入初中的統(tǒng)一考試成績(jī)總分最高的女學(xué)生?？紤]到在全市考生中普查工作量太大，請(qǐng)你應(yīng)用分枝定界法的思想步驟為解決此問(wèn)題設(shè)計(jì)一個(gè)方案。簡(jiǎn)述思路步驟（8分）。2.

簡(jiǎn)要對(duì)比線性規(guī)劃同目標(biāo)規(guī)劃在模型結(jié)構(gòu)上的相同點(diǎn)和異同點(diǎn)（6分）。

試卷十三一、填空（15×2分）1、在線性規(guī)劃問(wèn)題的約束方程AX=b,X≥0中，對(duì)于選定的基B，令非基變量XN=0，得到的解X=；若，則稱此基本解為基本可行解；若，則稱此基本可行解為退化的解；若，則此基可行解為最優(yōu)解。2、用對(duì)偶單純形法求解線性規(guī)劃問(wèn)題時(shí)，根據(jù)br確定xr為出基變量；根據(jù)最小比值法則θ=，確定xk為進(jìn)基變量。3、在單純形法的相鄰兩次迭代中，迭代前的可行基B和迭代后的可行基的逆矩陣存在關(guān)系：-1=ErkB-1其中Erk=。4、已知y*為某線形規(guī)劃問(wèn)題的對(duì)偶問(wèn)題的最優(yōu)解，若y*>0，說(shuō)明在最優(yōu)化生產(chǎn)計(jì)劃中對(duì)應(yīng)的資源。5、平衡運(yùn)輸問(wèn)題（m個(gè)產(chǎn)地，n個(gè)銷地）的基可行解中基變量共有個(gè)；其中決策變量xij所對(duì)應(yīng)的列向量pij=.。6、對(duì)于Max型整數(shù)規(guī)劃問(wèn)題，若其松弛問(wèn)題的最優(yōu)單純形表中有一行數(shù)據(jù)為：XBbx1x2x3x4x23/4017/4-11/4則對(duì)應(yīng)的割平面方程為。7、用匈牙利法解分配問(wèn)題時(shí)，當(dāng)則找到了分配問(wèn)題的最優(yōu)解；稱此時(shí)獨(dú)立零元素對(duì)應(yīng)的效益矩陣為。8、將網(wǎng)絡(luò)D=（V，A，C）的頂點(diǎn)集合V分割成兩個(gè)非空集合V1和V1，使VS∈V1，Vt∈V1，則弧集成為分割VS和Vt的截集；稱為截集的容量。二、問(wèn)答題（2×5分）1．材寫出目標(biāo)規(guī)劃的一般模型；2．試敘動(dòng)態(tài)規(guī)劃的最優(yōu)性原理。三、已知某線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)為max=5x1+3x2,約束形式為“≤”。設(shè)x3,x4為松弛變量，用單純形法計(jì)算是某一步的表格如下所示：（15分）

Cj5300CBXBbx1x2x3x40x3

c011/55x1

de01-Z-10b-1fg（1）

求a~g的值；（2）

表中給出的解是否為最優(yōu)解，并求出最優(yōu)解。四、已知某線性規(guī)劃問(wèn)題，其初始及最優(yōu)單純形表如下：（15分）Cj12000CBXBbX1x2x3x4x50x312221000x49300110x5802001σj12000最優(yōu)解表Cj12000CBXBBx1x2x3x4x51x12101/20-1/20x4300-3/213/22x2401001/2σj00-1/20-1/2(1)求出對(duì)偶問(wèn)題的最優(yōu)解;(2)求C1的變化范圍,使最優(yōu)基不變;(3)如果b1由12變?yōu)?6,求最優(yōu)解.五、種機(jī)器可以在高低兩種不同的負(fù)荷下生產(chǎn),高負(fù)荷生產(chǎn)時(shí),產(chǎn)品的年產(chǎn)量g與投資的機(jī)器數(shù)量x的關(guān)系為:g(x)=8x,這時(shí)機(jī)器的年完好率a=0.7;在低負(fù)荷下生產(chǎn)時(shí)產(chǎn)品的年產(chǎn)量h和投入的機(jī)器數(shù)量y的關(guān)系為:h(x)=5y,這時(shí)機(jī)器的年完好率b=0.7。假定開始生產(chǎn)時(shí)的完好機(jī)器數(shù)量s1=1000臺(tái)，試制定一個(gè)5年計(jì)劃，確定每年投入高、低兩種負(fù)荷下生產(chǎn)的完好機(jī)器數(shù)量，使5年內(nèi)產(chǎn)品的總產(chǎn)品量最大，并且5年末完好的機(jī)器數(shù)量是500臺(tái)。（1）

寫出階段變量、狀態(tài)變量、決策變量；（6分）（2）

寫出第k階段的決策集合與狀態(tài)轉(zhuǎn)移方程；（9分）（3）

寫出遞推方程，并規(guī)范化求解。（選作10分）六、如圖所示是某地區(qū)交通運(yùn)輸示意圖，s是起點(diǎn)t終點(diǎn)，弧旁數(shù)字為cij(fij)。（15分）（1）寫出此交通運(yùn)輸規(guī)劃的線性規(guī)劃數(shù)學(xué)模型；（2）用標(biāo)號(hào)法求出從s到t最大流及其流量；（3）寫出該網(wǎng)絡(luò)的最小割集。

試卷十四一、填空(11×3分)1、在線性規(guī)劃問(wèn)題的約束方程AX=b,X≥0中，對(duì)于選定的基B，令非基變量XN=0，得到的解X=；若，則稱此基本解為基本可行解；若，則稱此基本可行解為退化的解。2、用單純形法求解線性規(guī)劃問(wèn)題的迭代步驟中，根據(jù)σK=確定xk為進(jìn)基變量；根據(jù)最小比值法則=，確定xr為出基變量。3、平衡運(yùn)輸問(wèn)題（m個(gè)產(chǎn)地，n個(gè)銷地）的基可行解中基變量共有個(gè)。4、對(duì)于Max型整數(shù)規(guī)劃問(wèn)題，若其松弛問(wèn)題的最優(yōu)單純形表中有一行數(shù)據(jù)為：XBbx1xxxx23/4017/4-11/4則對(duì)應(yīng)的割平面方程為。5、用匈牙利法解分配問(wèn)題時(shí)，當(dāng)則找到了分配問(wèn)題的最優(yōu)解；稱此時(shí)獨(dú)立零元素對(duì)應(yīng)的效益矩陣為。6、將網(wǎng)絡(luò)D=(V,A,C)的頂點(diǎn)集合V分割成兩個(gè)非空集合V1和，使VS∈V1,Vt∈，則弧集成為分割VS和Vt的截集；稱為截集的容量。二、單項(xiàng)選擇題（3×5分）1、含有兩個(gè)變量的線性規(guī)劃問(wèn)題若有可行解，則可行域是（）（A）全平面（B）多平面（C）凸多平面（D）凹多平面2、在目標(biāo)線性規(guī)劃問(wèn)題中，敘述正確的選項(xiàng)為（）（A）

正偏差變量取正值，負(fù)偏差變量取負(fù)值；（B）

目標(biāo)規(guī)劃模型中，若模型有解，則一定有最優(yōu)解；（C）

目標(biāo)函數(shù)中的優(yōu)先級(jí)P1，P2，P3，……之間表明數(shù)量上的重要型差別，如：P1比P2級(jí)重要10倍或20倍等；（D）

描寫可以含系統(tǒng)約束（剛性約束），也可以不含。3、下列敘述中，有關(guān)樹G（V，E）性質(zhì)不正確的選項(xiàng)為（）（A）

無(wú)圈且不連通；（B）

n個(gè)頂點(diǎn)的樹必有n-1條邊；（C）

樹中任意兩點(diǎn)，恰有一條初等鏈；（D）

樹無(wú)回路，但不相鄰頂點(diǎn)連一條邊，恰得一回路。三、已知某線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)為maxZ=5x1+3x2,約束形式為“≤”。設(shè)x3,x4為松弛變量，用單純形法計(jì)算是某一步的表如下所示：（15分）Cj5300CBXBBx1x2x3x40x32c011/55x1ade01Z-10b-1fg（1）求a~g的值；（2）表中給出的解是否為最優(yōu)解，并求出最優(yōu)解。四、已知某線性規(guī)劃問(wèn)題，其初始及最優(yōu)單純形表如下：（15分）

Cj12345CBXBbx1x2x3x4x50x312221000x49300100x5802001σj12000最優(yōu)解表Cj12000CBXBbx1x2x3x4x51x12101/20-1/20x4300-3/213/22x2401001/2σj00-1/20-1/2（1）求對(duì)偶問(wèn)題的最優(yōu)解；（2）求C1的變化范圍，使最優(yōu)基不變；（3）如果b1由12變?yōu)?6，求最優(yōu)解。五、如圖所示是某地區(qū)交通運(yùn)輸示意圖。VS是起點(diǎn)，Vt是終點(diǎn)。（12分）（1）求出從VS到Vt的最短距徑；（2）用雙箭頭在圖上標(biāo)明。六、某物資每月需供應(yīng)50箱，每次訂貨費(fèi)為60元，每月每箱的存貯費(fèi)為40元。（10分）（1）若不允許缺貨，且一訂貨就可以提貨，試問(wèn)每隔多少時(shí)間訂購(gòu)一次，每次應(yīng)訂購(gòu)多少箱？（2）若一個(gè)周期中缺一箱的缺貨損失費(fèi)為40元，缺貨不補(bǔ)，問(wèn)每隔多少時(shí)間訂購(gòu)一次，每次應(yīng)訂購(gòu)多少箱？

試卷十五一、知線性規(guī)劃問(wèn)題（本題14分）minz=-5x1-6x2-7x3要求：（1）化為標(biāo)準(zhǔn)形式（7分）（2）列出用兩階段法求解時(shí)第一階段的初始單純形表（7分）。二、已知下表是某極大化線性規(guī)劃問(wèn)題的初始單純形表和迭代計(jì)算中某一步的單純形表，試求出表中未知數(shù)a~l的值（每個(gè)1.5分，共18分）。

x1x2x3x4x5x6X5205-413(b)10X68(j)-1(k)(c)01cj-zj16-7(a)00┇┇x3(d)-1/701-3/7(5)4/7X2(e)(l)10-3/7-5/7(g)cj-zj72/70011/7(k)(i)三、已知某一運(yùn)輸問(wèn)題的產(chǎn)銷平衡表、單位運(yùn)價(jià)表如下表所示，且表中給出一個(gè)最優(yōu)調(diào)運(yùn)方案（16分）。問(wèn)：（1）從A2→B2的單位運(yùn)價(jià)c22在什么范圍內(nèi)變化時(shí)，上述最優(yōu)調(diào)運(yùn)方案不變（8分）。（2）A2→B4的單位運(yùn)價(jià)c24變?yōu)楹沃禃r(shí)，該運(yùn)輸問(wèn)題有無(wú)窮多最優(yōu)調(diào)運(yùn)方案。（4分）除表中給出的方案外，至少再給出另兩個(gè)不同的最優(yōu)的方案。（4分）四、有十名研究生參加六門課程考試，由于每人研究方向不同，所選課程也不一樣，已知每名研究生要參加考試的課程如下表所示（表中打√的為參加考試的課程）（16分）?？荚嚢才旁?月18~20日連續(xù)三天，上、下午各考一門。每名研究生都要提出希望自己每天最多只參加一門課程考試。已知要求C課程安排在19日上午，D課程必須安排在下午考，F(xiàn)課的考試必須安排在B、E考試之后。要求排出一張滿足上述所有要求的考試日程表。

上午下午1

1

1

五、見以下有向圖，圖中數(shù)字為兩點(diǎn)間距離（16分）。

要求：（1）用動(dòng)態(tài)規(guī)劃的方法求出A→D的最短路（8分）（2）若f2(B1)為從B1出發(fā)至D點(diǎn)的最短距離，寫出f2(B1)的動(dòng)態(tài)規(guī)劃遞推方程的一般表達(dá)式，并具體說(shuō)明遞推方程中每個(gè)符號(hào)的意義（8分）。六、選擇填充題（每題4分，共20分）（1）

線性規(guī)劃問(wèn)題minz=3x1+5x2已知其最優(yōu)解為x1=2,x2=6,z*=36,則其對(duì)偶問(wèn)題的最優(yōu)解為.。.（①y1=3,y2=2,y3=0;②y1=0,y2=3/2,y3=1;③y1=0,y2=1,y3=4/3;④y1=3,y2=1,y3=2/3）（2）已知某個(gè)含10個(gè)節(jié)點(diǎn)的樹圖，其中9個(gè)節(jié)點(diǎn)的次（線度）為，1，1，3，1，1，1，3，1，3，則另一節(jié)點(diǎn)的次為。（①1；②4；③3；④2）（3）用標(biāo)號(hào)法尋找網(wǎng)絡(luò)最大流時(shí)，發(fā)生標(biāo)號(hào)中斷。這時(shí)若用V表示已標(biāo)號(hào)的節(jié)點(diǎn)集合，用表示未標(biāo)號(hào)的節(jié)點(diǎn)集合，則在網(wǎng)絡(luò)中所有V→方向的弧上有，→V方向的弧上有。（①f≥0;②f≤c;③f=c;④f=0）注：f為流量，c為弧的容量。

試卷十六一、某投資者有30000元可供為期四年的投資?，F(xiàn)有下列五項(xiàng)投資機(jī)會(huì)可供選擇：A：四年內(nèi)，投資者可在每年年初投資，每年每元投資可獲到0.2元，每年獲利后將本利重新投資。B：在四年內(nèi)，投資者應(yīng)在第一年年初或第三年年初投資，每?jī)赡昝吭顿Y可獲利潤(rùn)0.5元，兩年后獲利。然后可將本利再重新投資。C：在四年內(nèi)，投資者應(yīng)在第一年年初投資，三年后每元投資可獲利0.8元。獲利后可將本利重新投資。這項(xiàng)投資最多不超過(guò)20000元。D：在四年內(nèi)，投資者應(yīng)在第二年年初投資，兩年后每元投資可獲利0.6元。獲利后可將本利重新投資。這項(xiàng)投資最多不超過(guò)15000元。E：在四年內(nèi)，投資者應(yīng)在第一年年初投資，四年后每元投資可獲利1.7元。這項(xiàng)投資最多不超過(guò)20000元。投資者在四年內(nèi)應(yīng)如何投資，使他在四年后所獲利潤(rùn)最大？寫出這個(gè)問(wèn)題的線性規(guī)劃模型，不用求解。二、現(xiàn)要在五個(gè)工人中確定四個(gè)人來(lái)分別完成四項(xiàng)工作中的一項(xiàng)工作。由于每個(gè)工人的技術(shù)特長(zhǎng)不同，他們完成各項(xiàng)工作所需的工時(shí)也不同。每個(gè)工人完成每項(xiàng)工作所需的工時(shí)如下表所示：試找出一個(gè)工作分配方案，使總工時(shí)最小。三、采用變量代換，試把非線形0-1整數(shù)規(guī)劃maxz=s.t.–3x1+4x2+x3≤3x1、x2、x3為0或1轉(zhuǎn)換成一個(gè)線形0-1整數(shù)規(guī)劃。五、設(shè)某公司擬將五臺(tái)設(shè)備分配給下屬的甲、乙、丙三個(gè)工廠。各工廠獲得這種設(shè)備后，可以為公司帶來(lái)的盈利如下表所示：?jiǎn)柗峙浣o各工廠多少臺(tái)這種設(shè)備，可以為公司帶來(lái)盈利的總和為最大。用動(dòng)態(tài)規(guī)劃方法求解。（平分標(biāo)準(zhǔn)：每題都為20分）

試卷十七一、多重選擇判斷（共5小題，每小題4分，共20分）下面5小題，每題有（a）(b)(c)(d)四項(xiàng)，你認(rèn)為正確的打√，不正確的打×。答對(duì)者記1分，答錯(cuò)者扣1分，不答者不記分。以小題為單位，每小題最高四分，最低0分，不記負(fù)分。1.形法求解標(biāo)準(zhǔn)型的線性規(guī)劃問(wèn)題時(shí)(a)當(dāng)所有檢驗(yàn)數(shù)cj-zj≤0時(shí)，即可判定表中解即為最優(yōu)解；(b)為使目標(biāo)函數(shù)值最快增長(zhǎng)，必須選取與最大正檢驗(yàn)數(shù)（ck-zk）對(duì)應(yīng)變量xk為換為基的變量；(c)按最小比值原則確定換出基的變量是為了保證迭代計(jì)算后的解仍為基本可行解；(d)若存在σj=cj-zj>0，且該列系數(shù)PJ≤0，則線形問(wèn)題最優(yōu)解不存在（無(wú)界解）2.線性規(guī)劃的原問(wèn)題與其對(duì)偶問(wèn)題之間存在如下關(guān)系(a)

對(duì)偶問(wèn)題的對(duì)偶問(wèn)題是原問(wèn)題；(b)

原問(wèn)題存在可行解，其對(duì)偶問(wèn)題必存在可行解；(c)

原問(wèn)題可行解，其對(duì)偶問(wèn)題必?zé)o可行解；(d)

原問(wèn)題有無(wú)窮多最優(yōu)解，其對(duì)偶問(wèn)題也有無(wú)窮多最優(yōu)解。3.已知線性規(guī)劃問(wèn)題（A）maxz=（B）maxz=則有（A）、（B）的兩對(duì)偶問(wèn)題，各自最優(yōu)解y*z*與y′*,z′*間關(guān)系(a)y*=y′*,z*=z′*(b)y′*=2y*,z′*=z*(c)y′*=y*,z′*=2z*(d)(a)(b)(c)以外其他關(guān)系4.滿足下面條件的簡(jiǎn)單圖G（V，E）是樹圖（a）無(wú)圈且連通；（b）有n個(gè)點(diǎn)和恰好（n-1）條邊；（c）圖中任意兩點(diǎn)間存在唯一的鏈；（d）G無(wú)圈，但只要加一條邊即得唯一的圈。5．在目標(biāo)線性規(guī)劃問(wèn)題中（a）

正偏差變量取正值，負(fù)偏差變量取負(fù)值；（b）

目標(biāo)函數(shù)可以是求min。也可以求max；（c）

目標(biāo)函數(shù)中的優(yōu)先級(jí)P1，P2，P3…之間表明數(shù)量上的重要性差別，如P1比P2級(jí)重要10倍或20倍等；（d）

模型可以含系統(tǒng)約束（剛性約束），也可以不含。6．判斷下列說(shuō)法是否正確：（a）

線性規(guī)劃問(wèn)題的基本解對(duì)應(yīng)可行域的頂點(diǎn)；（b）

若X1，X2是某線性規(guī)劃問(wèn)題的可行解，則X=λ1X1+λ2X2（其中λ1+λ2=1）也必是該問(wèn)題的可行解；（c）

線性規(guī)劃問(wèn)題若存在可行解，其可行解集合為凸集；（d）

若X1，X2是某線性規(guī)劃問(wèn)題的最優(yōu)解，則X=λ1X1+（1+λ）X2(0≤λ≤1)也是該問(wèn)題的最優(yōu)解。三、形規(guī)劃問(wèn)題maxz=-x1+18x2+c3x3+c4x4(本題20分，每小題5分)要求（a）以x1,x2為基變量，列出單純形表（當(dāng)λ=0時(shí)）（b）若x1,x2為最優(yōu)基，確定問(wèn)題最優(yōu)解不變時(shí)c3,c4的變化范圍；（c）保持最優(yōu)基不變時(shí)的λ的變化范圍；（d）增加一個(gè)新變量，其約束條件中系數(shù)向量為，目標(biāo)函數(shù)中系數(shù)為ck，求問(wèn)題最優(yōu)解不變時(shí)ck取值范圍。四、已知運(yùn)輸問(wèn)題的產(chǎn)銷平衡表、單位運(yùn)價(jià)表及某一調(diào)運(yùn)方案如下（20分）產(chǎn)銷平衡表及調(diào)運(yùn)方案要求：（a）以該調(diào)運(yùn)方案對(duì)應(yīng)的變量x11、x12、x23、x31、x33為基變量，列出該運(yùn)輸問(wèn)題用單純形法求解時(shí)的單純形表（8分）。（b）在單純形表上判斷方案是否最優(yōu)？若否，用單純形法繼續(xù)迭代求出最優(yōu)（8分）。（c）利用單純形表判斷A3→B3運(yùn)費(fèi)c33在什么范圍內(nèi)變化，最優(yōu)解不變（4分）。五、由800萬(wàn)元，分別用于3個(gè)項(xiàng)目的投資，按規(guī)定每個(gè)項(xiàng)目至少投資200萬(wàn)元，最多投資400萬(wàn)元，各項(xiàng)目得到不同投資時(shí)的預(yù)期效益如下表所示，要求確定使投資效益最大的各項(xiàng)目投資數(shù)（20分）。要求：（a）建立動(dòng)態(tài)規(guī)劃模型，列出遞推關(guān)系式（基本方程），并說(shuō)明方程中各符號(hào)的意義（10分）；（b）建立網(wǎng)絡(luò)模型，畫出網(wǎng)絡(luò)圖，簡(jiǎn)要說(shuō)明圖中點(diǎn)、線和權(quán)術(shù)的意義（10分）。試卷十八一、多重選擇判斷（共5小題，每小題4分，共20分）下面5小題，每題有（a）(b)(c)(d)四項(xiàng)，你認(rèn)為正確的打√，不正確的打×。答對(duì)者記1分，答錯(cuò)者扣1分，不答者不記分。以小題為單位，每小題最高四分，最低0分，不記負(fù)分。1.形法求解標(biāo)準(zhǔn)型的線性規(guī)劃問(wèn)題時(shí)(a)當(dāng)所有檢驗(yàn)數(shù)cj-zj≤0時(shí)，即可判定表中解即為最優(yōu)解；(b)為使目標(biāo)函數(shù)值最快增長(zhǎng)，必須選取與最大正檢驗(yàn)數(shù)（ck-zk）對(duì)應(yīng)變量xk為換為基的變量；(c)按最小比值原則確定換出基的變量是為了保證迭代計(jì)算后的解仍為基本可行解；(d)若存在σj=cj-zj>0，且該列系數(shù)PJ≤0，則線形問(wèn)題最優(yōu)解不存在（無(wú)界解）2.線性規(guī)劃的原問(wèn)題與其對(duì)偶問(wèn)題之間存在如下關(guān)系(a)

對(duì)偶問(wèn)題的對(duì)偶問(wèn)題是原問(wèn)題；(b)

原問(wèn)題存在可行解，其對(duì)偶問(wèn)題必存在可行解；(c)

原問(wèn)題可行解，其對(duì)偶問(wèn)題必?zé)o可行解；(d)

原問(wèn)題有無(wú)窮多最優(yōu)解，其對(duì)偶問(wèn)題也有無(wú)窮多最優(yōu)解。3.已知線性規(guī)劃問(wèn)題（A）maxz=（B）maxz=則有（A）、（B）的兩對(duì)偶問(wèn)題，各自最優(yōu)解y*z*與y′*,z′*間關(guān)系(a)y*=y′*,z*=z′*(b)y′*=2y*,z′*=z*(c)y′*=y*,z′*=2z*(d)(a)(b)(c)以外其他關(guān)系4.滿足下面條件的簡(jiǎn)單圖G（V，E）是樹圖（a）無(wú)圈且連通；（b）有n個(gè)點(diǎn)和恰好（n-1）條邊；（c）圖中任意兩點(diǎn)間存在唯一的鏈；（d）G無(wú)圈，但只要加一條邊即得唯一的圈。5．在目標(biāo)線性規(guī)劃問(wèn)題中（a）

正偏差變量取正值，負(fù)偏差變量取負(fù)值；（b）

目標(biāo)函數(shù)可以是求min。也可以求max；（c）

目標(biāo)