運(yùn)籌學(xué)試題庫(kù)試卷3

1、運(yùn)籌學(xué)試題庫(kù)（試卷3）一、 填空題：（10分）1、在圖論中，圖的基本要素有兩個(gè)，它們是 和 。2、結(jié)點(diǎn)的最早開(kāi)始時(shí)間和 時(shí)間是同一時(shí)間，最早開(kāi)始是對(duì)結(jié)點(diǎn)的后接工序而言， 是對(duì)結(jié)點(diǎn)的緊前工序而言。3、對(duì)需要量 供應(yīng)量的運(yùn)輸問(wèn)題，求最優(yōu)解時(shí)要先 一個(gè)供應(yīng)點(diǎn)。4、關(guān)鍵路線是從起點(diǎn)到終點(diǎn)所有路中的最 路，它的線路時(shí)差為 。5、在圖論中，為了表示兩個(gè)隊(duì)比賽的勝負(fù)關(guān)系可以用一條帶 的 來(lái)表示。二、 選擇題（10分）1、若T是圖G的最小支撐樹(shù)，則（ ）AT必唯一 B. G不一定是連通圖CT中必不含圈 D.G中不含圈3、在網(wǎng)絡(luò)計(jì)劃中，進(jìn)行時(shí)間與成本優(yōu)化時(shí)，隨工期延長(zhǎng)，間接費(fèi)用將（ ）。A減少 B.增加 C.不

2、變 D.不易估計(jì)4、若線性規(guī)劃問(wèn)題的最優(yōu)解在可行域的兩個(gè)頂點(diǎn)達(dá)到，則最優(yōu)解（ ）。A有兩個(gè) B.有無(wú)窮多個(gè) C.過(guò)這兩點(diǎn)的直線 D.不可能發(fā)生5、在n個(gè)產(chǎn)地，m個(gè)銷地的產(chǎn)銷平衡運(yùn)輸問(wèn)題中，（ ）是錯(cuò)誤的。A 運(yùn)輸問(wèn)題是線性規(guī)劃問(wèn)題B 基變量的個(gè)數(shù)是數(shù)字格的個(gè)數(shù)C 空格有mn-n-m+1個(gè)D 每一格在運(yùn)輸圖中均有一閉合回路三、 判斷題（10分）1、用單純形法求解標(biāo)準(zhǔn)型式的線性規(guī)劃問(wèn)題時(shí)，與>0對(duì)應(yīng)的變量都可以被選作換入變量。（ ）2、對(duì)偶問(wèn)題的對(duì)偶一定是原問(wèn)題。（ ）3、如果運(yùn)輸問(wèn)題單位運(yùn)價(jià)表的某一行（或某一列）元素分別加上一個(gè)常數(shù)k，最優(yōu)調(diào)運(yùn)方案將不會(huì)發(fā)生變化。（ ）4、指派問(wèn)題效率矩陣

3、地每個(gè)元素都乘以同意常數(shù)k，將不影響最優(yōu)指派方案。（ ）5、求網(wǎng)絡(luò)最大流的問(wèn)題可歸結(jié)為求解一個(gè)線性規(guī)劃模型。（ ）四、 規(guī)劃問(wèn)題（16分）已知線性規(guī)劃問(wèn)題（1） 寫(xiě)出其對(duì)偶問(wèn)題；（2） 用圖解法求對(duì)偶問(wèn)題的解；（3） 利用（2）的結(jié)果及對(duì)偶性質(zhì)求原問(wèn)題解。五、 運(yùn)輸問(wèn)題（10分）某土石方從三個(gè)產(chǎn)地運(yùn)往四個(gè)工地，產(chǎn)地的產(chǎn)量、工地的需求量及單位運(yùn)費(fèi)如下表，求最優(yōu)運(yùn)輸方案。產(chǎn)地 銷地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量3656六、 支撐樹(shù)問(wèn)題（6分）求下面網(wǎng)絡(luò)圖的最小支撐樹(shù)：七、 指派問(wèn)題（10分）分配甲、乙、丙、丁、戊五人去完成五項(xiàng)工作，每人完成一項(xiàng)工作，每人完

4、成各項(xiàng)任務(wù)時(shí)間如下表，試確定總花費(fèi)時(shí)間為最少的指派問(wèn)題。人 任務(wù)ABCDE甲127979乙89666丙71712149丁15146610戊4107109八、 網(wǎng)絡(luò)最大流問(wèn)題（10分）求下圖所示容量網(wǎng)絡(luò)中從的最大流。其中每邊上的數(shù)為。9、 指派問(wèn)題有三臺(tái)設(shè)備，可用于五項(xiàng)不同的工程。但由于設(shè)備數(shù)有限，只能分給其中的三項(xiàng)工程。下表給出了不同的工程得到設(shè)備后所創(chuàng)的利潤(rùn)，試用匈牙利法確定使總利潤(rùn)最大的設(shè)備分配方案（單位：萬(wàn)元）。 利潤(rùn)工程設(shè)備B1B2B3B4B5A1372911A2681075A394125610 動(dòng)態(tài)規(guī)劃某公司決定投資60萬(wàn)元（以10萬(wàn)元為單位），以提高三種主要產(chǎn)品 A、B、C 的產(chǎn)量

5、?，F(xiàn)決定每種產(chǎn)品至少要投資10萬(wàn)元。各種產(chǎn)品投資不同資金后可獲得的期望利潤(rùn)如下：分配的投資金額利 潤(rùn)產(chǎn)品 A產(chǎn)品 B產(chǎn)品 C1014.516.215.92016.418.418.43018.019.922.64019.624.124.2試確定如何安排對(duì)各種產(chǎn)品的投資數(shù)，可獲得最大總期望利潤(rùn)？11 整數(shù)規(guī)劃某公司擬建立4個(gè)超市，可選的地址有A、B、C三處。在不同地址設(shè)置不同數(shù)量的超市后，每個(gè)月的營(yíng)業(yè)利潤(rùn)如下表所示（單位：萬(wàn)元）：超市數(shù)地址1234A16203032B12152024C10131617問(wèn)這些超市應(yīng)如何分布，可使公司總的營(yíng)業(yè)利潤(rùn)最高。12 指派問(wèn)題：用匈牙利算法求解下述指派問(wèn)題，已知效率矩陣分別如下：（a） （b）13 分配甲、乙、丙、丁四個(gè)人去完成五項(xiàng)任務(wù)。每人完成任務(wù)的時(shí)間如表所示。由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中有一人可兼完成兩項(xiàng)任務(wù)，其余三人每人完成一項(xiàng)。試確定總花費(fèi)時(shí)間為最少的指派方案。 任 務(wù)人ABCDE甲2529314237乙3938262033丙3427284032丁2442362345十四求下圖的最小生成樹(shù)和最大生成樹(shù)： V1 6 V2 6 6 2 2V6 7 V7 3 V