管理運籌學(xué)課后習(xí)題解答

1、1 緒論1、運籌學(xué)的內(nèi)涵答：本書將運籌學(xué)定義為：“通過構(gòu)建、求解數(shù)學(xué)模型，規(guī)劃、優(yōu)化有限資源的合理利用，為科學(xué)決策提供量化依據(jù)的系統(tǒng)知識體系?！苯忉尅⑿拚?解構(gòu) 造 模 型現(xiàn) 實 系 統(tǒng)模 型現(xiàn) 實 結(jié) 論模 型 結(jié) 論圖1-1運籌學(xué)的工作過程2、運籌學(xué)的工作過程答：（1）提出和形成問題。即要弄清問題的目標(biāo)、可能的約束、可控變量、有關(guān)的參數(shù)以及搜索有關(guān)信息資料。（2）建立模型。即要把問題中的決策變量、參數(shù)和目標(biāo)、約束之間的關(guān)系用一定的模型表示出來。（3）求解模型。根據(jù)模型的性質(zhì)，選擇相應(yīng)的求解方法，求得最優(yōu)或者滿意解，解的精度要求可由決策者提出。（4）解的檢驗和轉(zhuǎn)譯。首先檢查求解過程是否有誤

2、，然后再檢查解是否反映客觀實際。如果所得之解不能較好地反映實際問題，必須返回第（1）步修改模型，重新求解；如果所得之解能較好地反映實際問題，也必須仔細(xì)將模型結(jié)論轉(zhuǎn)譯成現(xiàn)實結(jié)論。（5）解的實施。實施過程必須考慮解的應(yīng)用范圍及對各主要因素的敏感程度，向決策者講清楚用法，以及在實施中可能產(chǎn)生的問題和修改的方法。3、數(shù)學(xué)模型及其三要素答：數(shù)學(xué)模型可以簡單的描述為：用字母、數(shù)字和運算符來精確地反映變量之間相互關(guān)系的式子或式子組。數(shù)學(xué)模型由決策變量、約束條件和目標(biāo)函數(shù)三個要素構(gòu)成。決策變量即問題中所求的未知的量，約束條件是決策所面臨的限制條件，目標(biāo)函數(shù)則是衡量決策效益的數(shù)量指標(biāo)。2 線性規(guī)劃1、試述線性規(guī)

3、劃數(shù)學(xué)模型的組成部分及其特性答：線性規(guī)劃數(shù)學(xué)模型由決策變量、約束條件和目標(biāo)函數(shù)三個部分組成。線性規(guī)劃數(shù)學(xué)模型特征：（1） 用一組決策變量表示某一方案，這組決策變量均為非負(fù)的連續(xù)變量；（2） 存在一定數(shù)量（m）的約束條件，這些約束條件可以用關(guān)于決策變量的一組線性等式或者不等式來加以表示；（3） 有一個可以用決策變量加以表示的目標(biāo)函數(shù)，而該函數(shù)是一個線性函數(shù)。2、一家餐廳24小時全天候營業(yè)，在各時間段中所需要的服務(wù)員數(shù)量分別為： 2：006：00 3人 6：0010：00 9人10：0014：00 12人 14：0018：00 5人18：0022：00 18人 22：00 2：00 4人設(shè)服務(wù)員在

4、各時間段的開始時點上上班并連續(xù)工作八小時，問該餐廳至少配備多少服務(wù)員，才能滿足各個時間段對人員的需要。試構(gòu)造此問題的數(shù)學(xué)模型。解：用決策變量,分別表示2：006：00， 6：0010：00 ，10：0014：00 ，14：0018：00，18：0022：00， 22：00 2：00 時間段的服務(wù)員人數(shù)。其數(shù)學(xué)模型可以表述為：3、現(xiàn)要截取2.9米、2.1米和1.5米的元鋼各100根，已知原材料的長度是7.4米，問應(yīng)如何下料，才能使所消耗的原材料最省。試構(gòu)造此問題的數(shù)學(xué)模型。解：圓鋼的截取有不同的方案，用表示每種切割方案的剩余材料。其切割方案如下所示： 2.92.11.51'1110.92

5、'2000.13' 1200.34'10305'0130.86'0041.47'0220.28'0301.1 目標(biāo)函數(shù)為求所剩余的材料最少，即4、某糖果廠用原料A、B、C加工成三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果中A、B、C三種原料的含量要求、各種原料的單位成本、各種原料每月的限制用量、三種牌號糖果的單位加工費及售價如表1所示。問該廠每月生產(chǎn)這三種牌號糖果各多少千克，才能使該廠獲利最大？試建立這個問題的線性規(guī)劃模型。表1甲乙丙原料成本限制用量A60%以上15%以上2.002000B1.502500C20%以下60%以下50%以下

6、1.001200加工費0.500.400.30售 價3.402.852.25解：以表示甲產(chǎn)品中的A成分，表示甲產(chǎn)品中的B成分，表示甲產(chǎn)品中的C成分，依此類推。據(jù)表2-16，有：，其中：，把逐個代入并整理得：，原材料的限制，有以下不等式成立：，在約束條件中共有9個變量，為方便計算，分別用,表示，即令=，=，=，=，=，=，=，=，=由此約束條件可以表示為：我們的目的是使利潤最大，即產(chǎn)品售價減加工費再減去原材料的價格為最大。目標(biāo)函數(shù)為5、某廠在今后4個月內(nèi)需租用倉庫存放物資，已知各個月所需的倉庫面積如表2所示。租金與租借合同的長短有關(guān)，租用的時間越長，享受的優(yōu)惠越大，具體數(shù)字見表3。租借倉庫的合同

7、每月初都可辦理，每份合同具體規(guī)定租用面積數(shù)和期限。因此該廠可根據(jù)需要在任何一個月初辦理租借合同，且每次辦理時，可簽一份，也可同時簽若干份租用面積和租借期限不同的合同，總的目標(biāo)是使所付的租借費用最小。試根據(jù)上述要求，建立一個線性規(guī)劃的數(shù)學(xué)模型。表2月 份1234所需面積（100m2）15102012表3合同租借期限1個月2個月3個月4個月單位（100m2）租金（元）2800450060007300解：設(shè)（i1,2,3,4;j=1,24-i+1）為第i個月初簽訂的租借期限為j個月的合同租借面積（單位：100）；表示第i個月所需的面積（j表示每100倉庫面積租借期為j個月的租借費）；則線性規(guī)劃模型為

8、：6、某農(nóng)場有100公頃土地及25萬元資金可用于發(fā)展生產(chǎn)。農(nóng)場勞動力情況為秋冬季4500人日，春夏季6000人日，如勞動力本身過?？赏獬龃蚬?，春夏季收入為20元人日，秋冬季12元人日。該農(nóng)場種植三種作物：大豆、玉米和小麥，并飼養(yǎng)奶牛和雞。種作物不需要專門投資，而飼養(yǎng)動物時每頭奶牛投資8000元，每只雞投資2元。養(yǎng)奶牛時每頭需撥出1.5公頃土地種飼草，并占用人工秋冬季為100人日，春夏季為50人日，年凈收入3000元每頭奶牛。養(yǎng)雞不占土地，需人工為每只雞秋冬季0.3人日，春夏季0.1人日，年凈收入為每只8元。農(nóng)場現(xiàn)有雞舍允許最多養(yǎng)5000只雞，牛欄允許最多養(yǎng)50頭奶牛，三種作物每年需要的人工及收

9、入情況如表4所示。試決定該農(nóng)場的經(jīng)營方案，使年凈收入最大。表4大豆玉米麥子每公頃秋冬季所需人日數(shù)203510每公頃春夏季所需人日數(shù)507540年凈收入（元/公頃）11001500900解：設(shè),分別代表大豆、玉米、麥子的種植數(shù)（公頃）；,分別代表奶牛和雞的飼養(yǎng)數(shù)；,分別代表秋冬季和春夏季多余的勞動力（人日數(shù)）則有7、用圖解法求解下列線性規(guī)劃問題（1） （2）（3） （4）解：（1） （2）84 2 3 4此題有唯一最有解， 2 3 484此題有無窮多最有解，其中一個是（3） （4） 2 44此題為無界解 2 43找不到可行域，此題為無可行解8、考慮線性規(guī)劃： + + + = 5 + + = 22

10、+ + + = 6（1） 通過觀察寫出初始的基可行解并構(gòu)造初始單純形表；（2） 在保持和為零的情況下，給出非基變量增加一個單位時的可行解，并指出目標(biāo)函數(shù)的凈增量是多少?（3） 在模型約束條件的限制下，的最大增量是多少？（4） 在有其最大增量時，給出一個新的基可行解。解：（1）因存在初始可行基，故可令,全為0,則可得初始可行解為，Z5。初始單純行表為：cj2 -1 1 1 0 0CBXBx1 x2 x3 x4 x5 x6100x4x5x6 -1 1 1 1 0 0 1 1 0 0 1 0 2 1 1 0 0 1526sj 3 -2 0 0 0 0z=0(2)非基變量,仍然取零，由0變?yōu)?,即1,

11、0,=0,代入約束條件得一個可行解X=。其目標(biāo)函數(shù)值為Z8因此，隨著增加1個單位目標(biāo)函數(shù)值的凈增量為Z8-5=3.（3）因為決策變量全非負(fù)所以由約束條件知增加可以引起,增加，即條件對無約束；由約束條件知增加可引起,減少，由非負(fù)約束知最大增量為2；同理可得約束條件的最大增量為3，綜合得的最大增量為2。（4）2，非基變量=0,0,代入約束條件得基可行解X=，目標(biāo)函數(shù)值為Z11。9、將線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)形式，無約束解：（1）令并代入模型，這里>=0,>=0；（2）第二個約束條件方程兩側(cè)同乘“-1”；（3）第一個約束條件引入松弛變量，第三個約束條件引入作為松弛變量。（4）目標(biāo)函數(shù)同乘“

12、-1”，即可實現(xiàn)最少化。10、用單純形法求解下述線性規(guī)劃問題（1） （2） + 2 + 18 + 4+ 5（1）解：構(gòu)造初始單純行表，并進行初等變換，得：cj3 1 1 1 CBXBx1 x2 x3 x411x3x4 -2 （2） 1 0 3 1 0 1 46sj 2 -2 0 0 w=1011x2x4 -1 1 1/2 0 4 0 -1/2 1 24sj 0 0 1 0 w=6最優(yōu)解，由非基變量的檢驗數(shù)為0,知此問題有無窮多最有解，所以該解為無窮多最優(yōu)解中的一個，最優(yōu)值為w6。（2）解：此問題用大M法求解，先把問題標(biāo)準(zhǔn)化為：構(gòu)造初始單純行表，并進行初等變換，得：cj-4 -5 -1 0 0

13、M MCBXBx1 x2 x3 x4 x5 x6 x7M0 Mx6x5x7 3 2 1 -1 0 1 0(2) 1 0 0 1 0 01 1 -1 0 0 0 11845sj-4-4M -5-3M-1 M 0 0 0M-4Mx6x1x70 1/2 1 -1 -2/3 1 0 1 (1/2 ) 0 0 1/2 0 0 0 1/2 -1 0 -1/2 0 11223sj0 -5 -1 M2M+2 0 0M-5Mx6x2x7-1 0 (1) -1 -2 1 0 2 1 0 0 1 0 0 -1 0 -1 0 -1 0 11041sj2M-4 0 -1 M3M+5 0 0-1-5Mx3x2x7-1 0

14、 1 -1 -2 1 0 2 1 0 0 1 0 0 -2 0 0 -1 -3 1 110411sj2M+5 0 0 M-1 3M+3 1 0因為所有檢驗數(shù)均為非負(fù)，但人工變量仍為基變量，故此問題無解。11、求解線性規(guī)劃問題并給出其中三個最優(yōu)解：解：構(gòu)造初始單純行表，并進行初等變換，得：cj3 1 1 1 CBXBx1 x2 x3 x411x3x4 -2 （2） 1 0 3 1 0 1 46sj 2 -2 0 0 w=1011x2x4 -1 1 1/2 0 (4 ) 0 -1/2 1 24sj 0 0 1 0 w=613x2x1 0 1 3/8 1/4 1 0 -1/8 1/4 31sj 0

15、0 1 0 w=6從單純形表可以找到兩個頂點，?？梢哉业阶兞恐g存在以下關(guān)系：2；44；令1/2則有，從而找到了LP問題的三個最優(yōu)解。12、（1）如為唯一最優(yōu)解則要求非基變量的檢驗數(shù)全少于零，從而有<0，<0。并且要令表中的解為最優(yōu)解，則要求原問題可行，這只要滿足即可。（2）要令表中解為無窮多最優(yōu)解中的一個，則有以下關(guān)系成立：<=0，<=0，且=0若=0，則。（3）要使表中的解為退化的基可行解，則必有；當(dāng)>且>0時，。（4）若為無界解，則滿足能找到入基變量，但找不到出基變量的條件。即滿足：；>，且>0；。（5）以代替，即入基，出基，則有以下關(guān)系成

16、立：>，且>0；，且。3 線性規(guī)劃的對偶問題1 試從經(jīng)濟角度解釋對偶變量的含義。答：假設(shè)有一企業(yè)欲將另一個企業(yè)擁有的資源收買過來，至少應(yīng)付出多少代價，才能使此企業(yè)愿意放棄生產(chǎn)活動，出讓資源。顯然后者放棄自己組織生產(chǎn)活動的條件時，對同等數(shù)量資源出讓的代價不低于該企業(yè)自己組織生產(chǎn)活動是的產(chǎn)值。2 判斷下列說法是否正確（1） 任何線性規(guī)劃問題都存在其對偶問題 （正確）（2） 如果原問題存在可行解，則其對偶問題也一定存在可行解；（錯）（3） 當(dāng)原問題為無界解時，對偶問題也為無界解；（錯）（4） 當(dāng)對偶問題無可行解時，原問題一定具有無界解；（錯）（5） 若原問題有無窮多最優(yōu)解，則對偶問題也一

17、定具有無窮多最優(yōu)解 （錯）3寫出下列線性規(guī)劃問題的對偶問題：（1） + 2 + 2 2 + +3 6 +4 +6 5解：（2） + 2 + 10 3 +215 +2 + 12無約束解：4. 用對偶單純形法求解下述線性規(guī)劃問題（1） （2） +3 3 +2 +2 +3302 +2 5 2 + +3 +220（1） 轉(zhuǎn)換化成標(biāo)準(zhǔn)形式：cj4 12 18 0 0CBXBx1 x2 x3 x4 x500x4x5 -1 0 -3 1 0 0 -2 -2 0 1-3-5sj 4 12 18 0 01812x3x2 1/3 0 1 -11/3 0 -1/3 1 0 1/3 -1/212/3sj 2 0 10

18、 2 6W=36X=(0,2/3,1,0,0)(2)轉(zhuǎn)化為標(biāo)準(zhǔn)形式cj1 2 3 4 0 0CBXBx1 x2 x3 x4 x5 x6 00x5x6 -1 -2 -2 -3 1 0 -2 -1 -3 -2 0 1-30-20sj 1 2 3 4 0 010x1x6 1 2 2 3 -1 0 0 3 1 4 -2 112/3sj 0 0 1 1 1 0W=30X(30,0,0,0,0,40)minz=305 （1）由最終單純形表可知，為保持原最優(yōu)解不變應(yīng)有：解不等式組得：C(2)將C1=2直接反映進單純形表中：cj-2 -1 -5 0 0CBXBx1 x2 x3 x4 x5-2-5x1x3 1

19、-1/3 0 1/3 -1/3 0 1 1 -1/5 2/553sj 0 10/3 0 -1/3 4/30-5x4x3 3 -1 0 1 -1 3/5 4/5 1 0 1/5156sj 1 3 0 5 1-30X=(0,0,6,15,0) max z=30(3)因為原材料的市場價格0.8小于原材料的影子價格1，所以，可以買進原材料。假設(shè)買進原材料100單位，則此公司擁有原材料的總額為130。b´將b´反映進單純形表中：cj-3 -1 -5 0 0CBXBx1 x2 x3 x4 x5-3-5x1x3 1 -1/3 0 1/3 -1/3 0 1 1 -1/5 2/585/311

20、1sj 0 3 0 0 1w=-30最終的單純形表cj-3 -1 -5 0 0CBXBx1 x2 x3 x4 x5-50x3x5 6/5 3/5 1 1/5 0 -3 1 0 -1 1985sj 3 2 0 1 0w=-45(4)為非基變量，所以，最優(yōu)解不變。（5）將原問題的最優(yōu)解X=（5，0，3，0，0）代入不等式中，不等式仍然成立，故最優(yōu)解不變。（6）將原問題的最優(yōu)解X=（5，0，3，0，0）代入不等式中，不等式不成立，所以最優(yōu)解將發(fā)生變化。將新的約束條件反映進單純形表中：cj-3 -1 -5 0 0 0CBXBx1 x2 x3 x4 x5 x6-3-50x1x3x6 1 -1/3 0 1

21、/3 -1/3 0 0 1 1 -1/5 2/5 0 3 1 2 0 0 15320-3-50x1x3x6 1 -1/3 0 1/3 -1/3 0 0 1 1 -1/5 2/5 0 0 0 0 -3/5 1/5 15320sj 0 3 0 0 1 0w=-30最終單純形表為：cj-3 -1 -5 0 0 0CBXBx1 x2 x3 x4 x5 x6-3-50x1x3x4 1 -1/3 0 0 -2/9 5/9 0 1 1 0 1/3 -1/3 0 0 0 0 -1/3 -5/340/98/35/3sj 0 3 0 0 1 0w=-80/3（40/9，0，8/3，5/3，0，0）Maxz=80/

22、34 運輸問題1、運輸問題表上作業(yè)法的基本步驟。答：表上作業(yè)法的基本步驟可參照單純形法歸納如下：（1）找出初始基可行解：即要在階產(chǎn)銷平衡表上給出“”個數(shù)字格（基變量）；（2）求各非基變量（空格）的檢驗數(shù)，判斷當(dāng)前的基可行解是否是最優(yōu)解，如已得到最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一步；(3)確定入基變量，若，那么選取為入基變量；(4)確定出基變量，找出入基變量的閉合回路，在閉合回路上最大限度地增加入基變量的值，那么閉合回路上首先減少為“0”的基變量即為出基變量；（5）在表上用閉合回路法調(diào)整運輸方案；（6）重復(fù)2、3、4、5步驟，直到得到最優(yōu)解。2、“最小元素法”和“伏格爾”法的基本思想及基本操作。答

23、：最小元素法的基本思想是就近供應(yīng)，即從單位運價表中最小的運價開始確定產(chǎn)銷關(guān)系，依此類推，一直到給出基本方案為止。伏格爾法把費用增量定義為給定行或列次小元素與最小元素的差（如果存在兩個或兩個以上的最小元素費用增量定義為零）。最大差對應(yīng)的行或列中的最小元素確定了產(chǎn)品的供應(yīng)關(guān)系，即優(yōu)先避免最大的費用增量發(fā)生。當(dāng)產(chǎn)地或銷地中的一方在數(shù)量上供應(yīng)完畢或得到滿足時，劃去運價表中對應(yīng)的行或列，再重復(fù)上述步驟，即可得到一個初始的基可行解。3、閉合回路的構(gòu)成以及利用閉合回路法求檢驗數(shù)的基本操作。答：判斷基可行解的最優(yōu)性，需計算空格（非基變量）的檢驗數(shù)。閉合回路法即通過閉合回路求空格檢驗數(shù)的方法。從給定的初始方案的

24、任一空格出發(fā)尋找閉合回路，閉合回路頂點所在格括號內(nèi)的數(shù)字是相應(yīng)的單位運價，單位運價前的“+”、“-”號表示運量的調(diào)整方向?？崭裉巻挝贿\量調(diào)整所引起的運費增量就是空格的檢驗數(shù)。仿照此步驟可以計算初始方案中所有空格的檢驗數(shù)。4、利用位勢法求檢驗數(shù)以及利用閉合回路進行方案調(diào)整的基本操作。答：位勢法求解非基變量檢驗數(shù)的基本步驟：第一步：把方案表中基變量格填入其相應(yīng)的運價并令；讓每一個基變量都有，可求得所有的位勢；第二步：利用計算各非基變量的檢驗數(shù)方案的優(yōu)化基本步驟：在負(fù)檢驗數(shù)中找出最小的檢驗數(shù)，該檢驗數(shù)所對應(yīng)的變量即為入基變量。在入基變量所處的閉合回路上，賦予入基變量最大的增量，即可完成方案的優(yōu)化。在

25、入基變量有最大增量的同時，一定存在原來的某一基變量減少為“0”，該變量即為出基變量。切記出基變量的“0”運量要用“空格”來表示，而不能留有“0”。5、某玩具公司生產(chǎn)A、B、C三種玩具，每月的生產(chǎn)能力分別為1000、2000和2000件。玩具被運至甲、乙、丙三個百貨商店銷售。已知各家百貨商店每月對三種型號玩具的總銷量都是1500件，由于經(jīng)營環(huán)境的原因，各商店銷售不同型號玩具的盈利不同，具體數(shù)據(jù)見表1。又已知丙商店要求至少供應(yīng)1000件C型玩具且拒絕A型玩具。求能夠滿足上述條件而又使總盈利最大的供銷分配方案。表1甲乙丙A540B1689C121011解：此題屬于產(chǎn)大于銷問題，可以增加假想的需求部門

26、丁，使供需平衡。由于部門丁不存在，故其盈利都為0。供需平衡表示如下所示：甲乙丙丁產(chǎn)量A54001000B168902000C12101102000銷量150015001500500因為原問題為求最大值，故用類伏格爾法（求兩最大元素之差，其他步驟相同）求解問題的初始可行基，得甲乙丙丁產(chǎn)量A500500100050015002000銷量150015001500500用位勢法進行檢驗得：甲乙丙丁A（-7） 4（-5）00B168（0）（-4）4C（-6）1011（-6）612450非基變量檢驗數(shù)全為非負(fù)，說明所得初始可行基已為最優(yōu)解。表中將A調(diào)撥給丁500件，表明玩具A有5

27、00件銷售不出去。6、已知某廠每月最多生產(chǎn)甲產(chǎn)品270噸，先運至A1、A2、A3三個倉庫，然后再分別供應(yīng)B1、B2、B3、B4、B5五個用戶。已知三個倉庫的容量分別為50、100和150噸，各用戶的需要量分別為25、105、60、30和70噸。已知從該廠經(jīng)由各倉庫然后供應(yīng)各用戶的儲存和運輸費用如表2所示。試確定一個使總費用最低的調(diào)運方案。表2B1B2B3B4B5A11015202040A22040153030A33035405525解：此題屬于產(chǎn)銷不平衡問題，倉庫的總存儲能力為300t，用戶總需求量為290t，但該廠的最大生產(chǎn)能力為270t。故倉庫有30t剩余，用戶有20t得不到滿足，故可假設(shè)

28、存在倉庫A4，它的存儲量為20t，用戶B6 的需求量為30t。這樣就轉(zhuǎn)化為產(chǎn)銷平衡問題。與因A4與B6都是假設(shè)的，不需要運輸，故運價都為0，但是由A4運到B6的運輸無法發(fā)生，因兩者皆為假設(shè)的，運價為無窮大，設(shè)為M。得到產(chǎn)銷平衡表如下所示：B1B2B3B4B5B6產(chǎn)量A11015202040050A220401530300100A330354055250150A400000M20銷量2510560307030 用伏格爾法求解初始基可行解得：B1B2B3B4B5B6產(chǎn)量A15050A2254530100A310605030150A42020銷量2510560307030用位勢法檢驗是否為最優(yōu)解，得

29、：B1B2B3B4B5B6A1（15）15(0)(15)(35)(20)0A22040(-30)30(0)(-5)25A3(15)3540(30)25020A4(10)(-10)(-15)(0)0(M+25)-5-5152055-20因檢驗數(shù)存在負(fù)數(shù)，故用閉合回路法調(diào)整得：B1B2B3B4B5B6產(chǎn)量A15050A2256015100A350607030150A451520銷量2510560307030用位勢法檢驗得：B1B2B3B4B5B6A1（5）15(20)(5)(35)(20)0A220（10）1530(10)(5)15A3(5)35（20）(20)25020A4(10)0(15)0

30、(10)(M+35)-155150155-20因檢驗數(shù)全為正，所以已得最優(yōu)方案。即A3差30t沒有得到滿足， B2缺5t，B4缺15t。7、已知某運輸問題的單位運價及最優(yōu)調(diào)運方案如表3所示（括號中的數(shù)據(jù)代表運輸數(shù)量），由于產(chǎn)地A2至銷地B2的道路關(guān)閉，故最優(yōu)調(diào)運方案將發(fā)生變化，試在原最優(yōu)調(diào)運方案的基礎(chǔ)上，尋找新的最優(yōu)調(diào)運方案。表3B1B2B3B4B5aiA110205（4）9（5）109A2210（4）103064A31（3）20（1）710（1）4（3）8bj35463解：由于A2 到B2道路關(guān)閉，則其運價為M，應(yīng)令其出基，以實現(xiàn)最優(yōu)調(diào)度。先將M反映進產(chǎn)銷平衡表，然后用位勢法作檢驗，有：B1

31、B2B3B4B5A1（10）（1）59(7)0A2（21-M）M (24-M)（40-M）(22-M)M-19 A3120（1）1041019593要令A(yù)2B2出基，即令其運輸量為0，找出負(fù)檢驗數(shù)最小的來進行調(diào)整，得：B1B2B3B4B5產(chǎn)量A1459A2314A35128銷量35463用位勢法作檢驗，有：B1B2B3B4B5A1（11）（1）59(7)0A22（M-22） (2)（18）63 A3（1）20（1）1041-119593檢驗數(shù)已全為非負(fù)，故已得最優(yōu)調(diào)度方案。8、已知某運輸問題的單位運價及最優(yōu)調(diào)運方案如表4所示，試回答下述問題：表4B1B2B3B4B5B6aiA12（20）1（3

32、0）333550A242（20）2（20）44440A33（10）542（39）41（11）60A44221（1）2（30）231bj305020403011（1） A1到B2、A3到B5、和A4到B1的單位運價，分別在什么范圍內(nèi)變化時上表中給出的最優(yōu)方案不變；（2） 若A1到B2的單位運價由1變?yōu)?，最優(yōu)方案將發(fā)生怎樣的變化；（3） 若A3到B5的單位運價由4變?yōu)?，最優(yōu)方案將發(fā)生怎樣的變化；解：（1）設(shè)A1到B2的單位運價為x，因A1到B2是基變量，它的運價變化會引起非基變量檢驗系數(shù)的變化，此時，只需對其再進行位勢法分析即可。B1B2B3B4B5B6A12x(3-x)(2)(1)(5)0A

33、2（x）22（20）(1+x)(2+x)2-xA33（4-x）（3-x）2（1）11A4(x)(2-x)(1)1 2(2)02 xx120要令最優(yōu)方案不變，則非基變量的檢驗數(shù)非負(fù)；故有x>=0；3-x>=0；4-x>=0；2-x>=0；2+x>=0；1+x>=0解上述不等式得0<=x<=2。即A1到B2的單位運價在0，2內(nèi)變化時，最有方案不變。A3到B5的單位運價屬于非基變量，它的變化不會引起其它檢驗數(shù)變化，故只需保證其檢驗數(shù)非負(fù)即可。先用位勢法算出原方案的檢驗數(shù)：B1B2B3B4B5B6A121(2)(2)(1)(5)0A2（1）22（3）(1

34、)(3)1A33（3）（2）2（1）11A4(2)(1)(1)1 2(2)02 11120設(shè)A3到B5的單位運價為x，則其檢驗數(shù)滿足x-（1+2）>=0，即x>=3。也就是說A3到B5的單位運價大于等于3時，最有方案不變。同理可以算出A4到B1的單位運價變化范圍是2，+)，此時最優(yōu)方案不變。（2）把變化直接反映到表中可得下表：B1B2B3B4B5B6A123(0)(2)(1)(5)0A2（3）22（20）(4)(5)-1A33（1）（0）2（1）11A4(3)(-1)(1)1 2(2)0233120因存在檢驗數(shù)為負(fù)數(shù)，最優(yōu)方案發(fā)生改變，用閉合回路法調(diào)整得：B1B2B3B4B5B6a

35、iA1212950A2202040A39401160A413031bj305020403011重新計算檢驗數(shù)，得：B1B2B3B4B5B6A123(0)(2)(0)(5)0A2（3）22（4）(2)(5)-1A33（1）（0）2（0）11A4(3)2(0)（1） 2(3)-1233130非基變量檢驗數(shù)均為非負(fù)，故為最優(yōu)方案。（3）把A3到B5的單位運價改為2，然后求檢驗數(shù)得：B1B2B3B4B5B6A121(2)(2)(1)(5)0A2（1）22（3）(1)(3)1A33（3）（2）2（-1）11A4(2)(1)(1)1 2(2)02 11120由于存在負(fù)檢驗數(shù)，故最優(yōu)方案發(fā)生變化，此時用閉合

36、回路法調(diào)整得：B1B2B3B4B5B6aiA1203050A2202040A3109301160A43131bj305020403011重新計算檢驗數(shù)，得：B1B2B3B4B5B6A121(0)(2)(0)(5)0A2（3）22（4）(2)(5)-1A33（1）（0）2411A4(1)(-1)(-1)1 （-1）(2)0233130檢驗數(shù)有負(fù)數(shù)，用閉合回路法調(diào)整得：B1B2B3B4B5B6aiA1203050A2202040A310391160A413031bj305020403011重新計算檢驗數(shù)，得：B1B2B3B4B5B6A121(2)(2)(1)(5)0A2（1）22（2）(1)(3)1A33（3）（2）2（1）11A4(2)(1)(1)1 2(2)0211120檢驗數(shù)全為非負(fù)，故已得最優(yōu)方案。5 整數(shù)規(guī)劃1、用分枝定界法求解下述整數(shù)規(guī)劃問題（1） （2）且取整 且取整解：（1）用單純型法求得相應(yīng)星星規(guī)劃問題,最終單純型表：cj1 1 0 0 CBXBx1 x2 x3 x411x1x2 1 0 1/32 -3/32 0 1 1/1