安徽建筑大學運籌學模擬試題.doc

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