經典運籌學試題15套

試卷一一、

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

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

試卷二一、

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

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

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

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

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

設車間生產所需零件的時間很短（即看成瞬時供應）；（2）

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

46101603305

8104200310產值（百元）43

34

1．

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

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

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

B1B2B3B4產量A11613221650A21214181560A3192123…50最低要求3070010

最高要求457030不限

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

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

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

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

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

簡要對比線性規(guī)劃同目標規(guī)劃在模型結構上的相同點和異同點（6分）。

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

Cj5300CBXBbx1x2x3x40x3

c011/55x1

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

求a~g的值；（2）

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

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

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

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

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

正偏差變量取正值，負偏差變量取負值；（B）

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

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

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

無圈且不連通；（B）

n個頂點的樹必有n-1條邊；（C）

樹中任意兩點，恰有一條初等鏈；（D）

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

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

試卷十五一、知線性規(guī)劃問題（本題14分）minz=-5x1-6x2-7x3要求：（1）化為標準形式（7分）（2）列出用兩階段法求解時第一階段的初始單純形表（7分）。二、已知下表是某極大化線性規(guī)劃問題的初始單純形表和迭代計算中某一步的單純形表，試求出表中未知數a~l的值（每個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ōu)調運方案（16分）。問：（1）從A2→B2的單位運價c22在什么范圍內變化時，上述最優(yōu)調運方案不變（8分）。（2）A2→B4的單位運價c24變?yōu)楹沃禃r，該運輸問題有無窮多最優(yōu)調運方案。（4分）除表中給出的方案外，至少再給出另兩個不同的最優(yōu)的方案。（4分）四、有十名研究生參加六門課程考試，由于每人研究方向不同，所選課程也不一樣，已知每名研究生要參加考試的課程如下表所示（表中打√的為參加考試的課程）（16分）?？荚嚢才旁?月18~20日連續(xù)三天，上、下午各考一門。每名研究生都要提出希望自己每天最多只參加一門課程考試。已知要求C課程安排在19日上午，D課程必須安排在下午考，F課的考試必須安排在B、E考試之后。要求排出一張滿足上述所有要求的考試日程表。

上午下午1

1

1

五、見以下有向圖，圖中數字為兩點間距離（16分）。

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

線性規(guī)劃問題minz=3x1+5x2已知其最優(yōu)解為x1=2,x2=6,z*=36,則其對偶問題的最優(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）已知某個含10個節(jié)點的樹圖，其中9個節(jié)點的次（線度）為，1，1，3，1，1，1，3，1，3，則另一節(jié)點的次為。（①1；②4；③3；④2）（3）用標號法尋找網絡最大流時，發(fā)生標號中斷。這時若用V表示已標號的節(jié)點集合，用表示未標號的節(jié)點集合，則在網絡中所有V→方向的弧上有，→V方向的弧上有。（①f≥0;②f≤c;③f=c;④f=0）注：f為流量，c為弧的容量。

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

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

對偶問題的對偶問題是原問題；(b)

原問題存在可行解，其對偶問題必存在可行解；(c)

原問題可行解，其對偶問題必無可行解；(d)

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

正偏差變量取正值，負偏差變量取負值；（b）

目標函數可以是求min。也可以求max；（c）

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

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

線性規(guī)劃問題的基本解對應可行域的頂點；（b）

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

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

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

對偶問題的對偶問題是原問題；(b)

原問題存在可行解，其對偶問題必存在可行解；(c)

原問題可行解，其對偶問題必無可行解；(d)

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

正偏差變量取正值，負偏差變量取負值；（b）

目標函數可以是求min。也可以求max；（c）

目標