安徽建筑大學(xué)運(yùn)籌學(xué)模擬試題.doc

一、 （8分）已知線性規(guī)劃問(wèn)題其對(duì)偶問(wèn)題最優(yōu)解為，試根據(jù)隊(duì)友理論求出原問(wèn)題的最優(yōu)解。2、已知運(yùn)輸問(wèn)題的供需關(guān)系表與單位運(yùn)價(jià)表如下所示，試用伏格爾法求出該問(wèn)題的近似最優(yōu)解。（6分）產(chǎn)地 銷地甲乙丙丁產(chǎn)量132765027523603254525銷量604020153請(qǐng)用匈牙利法求解該指派問(wèn)題：（8分）已知效率矩陣如下：4網(wǎng)絡(luò)最大流問(wèn)題：（12分）下面為一容量網(wǎng)絡(luò)，各弧上的代表該弧的（可行流流量，容量） 請(qǐng)用標(biāo)號(hào)法求出該網(wǎng)絡(luò)最大流。5、指派問(wèn)題：（10分）現(xiàn)有五個(gè)人Ai (i=1,2,3,4,5)被分配去完成完成五項(xiàng)工作Bj (j=1,2,3,4,5)，每人只能完成一項(xiàng)工作，且每項(xiàng)工作只能有一人來(lái)完成，每人完成每項(xiàng)工作所花費(fèi)的費(fèi)用如下表，請(qǐng)求使總費(fèi)用最小的最優(yōu)解。人員 任務(wù)B1B2B3B4B5A1127979A289666A3717121412A415146610A541071066、規(guī)劃問(wèn)題：（7分）用單純形法求解某線性規(guī)劃問(wèn)題得如下單純形表：cj1008000S基變量x1x2x3x4ac013/10-1/512bd10-1/102/516cj-zjef-14-24g（1） 上述問(wèn)題是求maxS=100x1+80x2 ,x3,x4為松弛變量，則a,b,c,d,e,f,g各為多少，上述表所給出的解是最優(yōu)解嗎？（2） 上述問(wèn)題的對(duì)偶問(wèn)題的解是什么？最優(yōu)值是什么？7、運(yùn)輸問(wèn)題：（10分）對(duì)如下表的運(yùn)輸方案：（1） 若要使總利潤(rùn)最大，該方案是否為最優(yōu)方案？（2） 若問(wèn)題中B1的需要量改為700，該方案是否為最優(yōu)方案？8.已知線性規(guī)劃問(wèn)題（1） 寫出其對(duì)偶問(wèn)題；（2） 用圖解法求對(duì)偶問(wèn)題的解；（3） 利用（2）的結(jié)果及對(duì)偶性質(zhì)求原問(wèn)題解。9某土石方從三個(gè)產(chǎn)地運(yùn)往四個(gè)工地，產(chǎn)地的產(chǎn)量、工地的需求量及單位運(yùn)費(fèi)如下表，求最優(yōu)運(yùn)輸方案。產(chǎn)地 銷地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量365610求下面網(wǎng)絡(luò)圖的最小支撐樹(shù)：11求總運(yùn)費(fèi)最小的運(yùn)輸問(wèn)題，某步運(yùn)輸圖如下：(1) 寫出a, b ,c ,d ,e的值，并求出最優(yōu)運(yùn)輸方案；(2) A3到B1的單位運(yùn)費(fèi)滿足什么條件時(shí)，表中運(yùn)輸方案為最優(yōu)方案。12.分配甲、乙、丙、丁、戊五人去完成五項(xiàng)工作，每人完成一項(xiàng)工作，每人完成各項(xiàng)任務(wù)時(shí)間如下表，試確定總花費(fèi)時(shí)間為最少的指派問(wèn)題。人 任務(wù)ABCDE甲127979乙89666丙71712149丁15146610戊410710913.求下圖所示容量網(wǎng)絡(luò)中從的最大流。其中每邊上的數(shù)為。14.某公司下屬的3個(gè)分廠A1、A2、A3生產(chǎn)質(zhì)量相同的工藝品，要運(yùn)輸?shù)紹1、B2、B3、B4 ，4個(gè)銷售點(diǎn)，分廠產(chǎn)量、銷售點(diǎn)銷量、單位物品的運(yùn)費(fèi)數(shù)據(jù)如下：求最優(yōu)運(yùn)輸方案。15.考慮下列線性規(guī)劃：最優(yōu)單純形表為：（1）、寫出此線性規(guī)劃的最優(yōu)解、最優(yōu)基 B 和它的逆 B-1 ；（2）、求此線性規(guī)劃的對(duì)偶問(wèn)題的最優(yōu)解；（3）、試求 c2 在什么范圍內(nèi)，此線性規(guī)劃的最優(yōu)解不變；（4）、若 b1 = 20 變?yōu)?45，最優(yōu)解及最優(yōu)值是什么？16.某公司決定投資60萬(wàn)元（以10萬(wàn)元為單位），以提高三種主要產(chǎn)品 A、B、C 的產(chǎn)量。現(xiàn)決定每種產(chǎn)品至少要投資10萬(wàn)元。各種產(chǎn)品投資不同資金后可獲得的期望利潤(rùn)如下： 試確定如何安排對(duì)各種產(chǎn)品的投資數(shù)，可獲得最大總期望利潤(rùn)？17.有下面線性規(guī)劃：要求：1、用單純性發(fā)就解該線性規(guī)劃問(wèn)題；2、寫出該問(wèn)題的對(duì)偶規(guī)劃；3、利用原問(wèn)題的最優(yōu)解和互補(bǔ)松弛性，直接秋池對(duì)偶問(wèn)題的最優(yōu)解；4、利用原問(wèn)題的最后一張單純形表，直接秋池對(duì)偶問(wèn)題最優(yōu)解。18.某公司有3個(gè)生產(chǎn)同類產(chǎn)品的工廠，生產(chǎn)的產(chǎn)品由4個(gè)銷售點(diǎn)銷售，各工廠的生產(chǎn)量、各銷售點(diǎn)的銷售量以及各工廠到各銷售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)如下表所示。問(wèn)該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷售點(diǎn)的需求量的前提下，使總的運(yùn)費(fèi)最小。產(chǎn)地 需地B1B2B3B4產(chǎn)量A1291079A213425A334257需求量384619.已知下圖表示7個(gè)城市間擬建一條連接各個(gè)城市的通訊線路，各邊的權(quán)數(shù)表示兩個(gè)城市之間的修建費(fèi)用，求連接各城市通訊線路最修修建費(fèi)用方案。20.下圖中vs表示倉(cāng)庫(kù)，vt表示商店