最全運籌學習題及答案-資料下載頁

　　

【正文】 n z=（+）+（2+）. 10+=503+5+=208+6+=100，，，，0（2）min z=（+）+++(+). ++=40++=100+=30+=15，，，，,0(3) min z=（+）+ +. ++=103+4+=508+10+=300，，，，0解（1）滿意解是：（50，0）（2）滿意解是：（25，15）（3）滿意解是：（10，0）。（1）min z= + +（5+3 ）+ . ++=80++ =90+=70+=45，，，，,0（2）min z= + + . +2+=1010+12+=+28，，， 0（3）min z=（+ ）+ . ++=12+2+=464+=50，，，，0解：（1）把原問題轉化為：Min z=++.+2+=1010+12+=2++=8，，，0是松弛變量單純形法計算得：0000b101【2】01100510120001108211000081012000021200100迭代…原問題最優解=0，=，非基變量的的檢驗數是0，所以有多重解；繼續迭代得到：=，=（2）使用單純形法計算：=70，=20（3）滿意解是=1，=0min z=+ +（5+3 ）+（5+3）. ++=80+=70+=45+=10，，，，，0（1）用單純形法求解（2）若目標函數變成min z=+ +（5+3 ）+（5+3），問原問題的解有什么變化？（3）若第一個目標約束的右端改為120，原滿意解有何變化？解：（1） 單純形法計算得到：=70，=45是滿意解（2） 實際上是對優先因子，進行調換，最優解不變。（3）b列出現負數，行的系數乘以1，重新迭代，=75，=45是滿意解；，產品I每件獲利10元，產品II每件獲利8元。每生產1件產品I需要3小時，每周的有效時間120小時，若加班生產，每件產品II利潤少1元，決策者希望在允許的時間和加班時間獲取最大利潤，試建立該問題的目標規劃模型，并求解？解：條件不足，無法建立模型。已知道三種酒的供應量和單位成本如下表；設該種牌號酒有三種商標（紅黃藍），各種商標的酒對原料酒的混合比及售價見下表，決策者規定：首先必須嚴格按規定比例兌制各種商標的酒，其次獲利最大；再次，紅商標的酒每天至少生產2000kg，列出數學模型。解：設，（i=1，2，3）表示第i種等級的兌制紅黃藍三種商標的酒的數量，數學模型：Max z=(+++++)++.（++）+=0（++）+=0（++）+=0（++）+=0（++）+=0（++）+=0+++=2000 (i=1,2,3。j=1,2,3)其中，z=(++)+5(++)+（++）6(++)(++)3(++)+試題：1. 某生產基地每天需從A、B兩倉庫中提取原材料用于生產，需提取的原材料有：原材料甲不少于240件，原材料乙不少于80公斤，原材料丙不少于120噸。已知：從A倉庫每部貨車能運回生產基地甲4件，乙2公斤，丙6噸，運費200元/部；從B倉庫每部貨車每天能運回生產基地甲7件，乙2公斤，丙2噸，運費160元/部，問：為滿足生產需要，生產基地每天應發往A、B兩倉庫多少部貨車，并使總運費最少？解題過程：根據題意列出下表：單位運量倉庫原材料甲（件）乙（公斤）丙（噸）運費（元/部）A426200B722160需求量24080120設每天發往A，B兩倉庫的貨車數分別為部，則有①②③④⑤且為整數先不考慮整數約束，用圖解法（如上圖），得最優解為，恰好是整數解。故就是原問題的最優整數解，且。 故生產基地每天發往A倉庫10部車，發往B倉庫30部車，可使總運費最少為6800元。第五章答案，問：用先解相應的線性規劃，然后湊整的辦法，能否求到最優整數解？（1） max z=3+2.2+4+,0,是整數（1） 解：將上述問題化為：Max z=3+2+0+0 .2+3+=4++=,0,N用單純形法求解：3200b029/2231029/4033/2【4】10133/8z03200（迭代過程略）相應的線性規劃問題最優解是= ,目標函數的最優值z=31/2湊整數時，=,是非可行解；=，是非可行解；=，是非可行解；=，是可行解，z=13；使用分支定界法解整數規劃問題。令=31/2，==0是可行解。所以=0，031/2把原問題分解為兩個問題：（I） max =3+2. 2+4+03。 0（II） max =3+2. 2+4+4。 0將上述問題化為標準型，使用單純形法求解：=3，=2是最優整數解，z=13.（2）max z=3+2.2+3142+9,0,是整數（2） 解：使用圖解法或者單純形法求解此問題，線性規劃問題最優解是（13/4，5/2）目標函數最優值max z=59/4；湊整數時，=,是可行解，z=13；=，是非可行解；=，是非可行解；=，是非可行解；使用分支定界法求解原整數規劃問題，令令=59/4，==0是可行解。所以=0，059/4；把原問題分解為兩個問題：（a）max =3+2. 2+3142+903。 0（b）max =3+2. 2+3142+94。 0解得：最優整數解是 =4，=1；目標函數是14.：Max z= +. 2 +9/14 51/142 + 1/3 ， 0 都是整數。圖解法解得：最優解是B點（51/46+7/691/6，51/23+14/69）目標函數最優值為：58/23+51/461/6使用分支定界法求解，令=58/23+51/461/6，==0是可行解；因此 =0，故058/23+51/461/6將原問題分解為下列問題：（I）Max = +. 2 +9/14 51/142 + 1/31 ， 0（I）Max = +. 2 +9/14 51/142 + 1/32 ， 0按照以上步驟，求解最終得到：最優解是（1，2）目標函數最優值z=3：（1）max z=+. 2+64+520,0,是整數解：將上述問題化成標準型：max z=++0+0. 2++=64+5+=20,，0,，是整數單純形法求得最優解是：= ，目標函數最優值13/3變量之間的關系：+5/6/6=5/32/3+/3=8/3把系數和常數項都分解成為整數和非負真分數之和；所以有：2/35/65/602/3（+）/30加入松弛變量，繼續迭代得到最終結果：= ，目標函數最優值4解得：最優整數解是 =0，=4；目標函數是4.（3） max z=3 . 3 2 354102+5,0,是整數解：將原問題化成標準型，并使用單純形法求解：最優解為= ，目標函數最優值30/7從單純形表可以得到變量間的關系，把系數和常數項都分解成整數和非負分數之和，可以得知：6/7（/7+2/7）0加入松弛變量，把新的約束條件加入后，繼續迭代，得到最終的結果：最優解是=1，=2目標函數最優值1.，設有四個防火站，如圖所示(課本P114)，其中①②③④是四個消防站，1，2，…11是防火區域，根據歷史資料證實，各個消防站可在事先規定的允許時間內對所有負責的地區的火災予以消滅，虛線表示各地區是哪個消防站負責，現在總部提出：是否可以減少消防站的數目，仍能夠負責各個地區的防火任務，如果可以，關閉哪個？提示：對每個消防站定義一個01變量，令1代表當某個防火區域由第i個消防站負責，0代表不是它負責。然后對每個防火區域列出約束條件；解：令1代表當某個防火區域由第i個消防站負責，0代表不是它負責；i=1，2，3，4。建立數學模型：Min z=. +11+11++1+1++1+11+1有以上約束條件可以解得：===1繼續求解當=0時，是可行解，目標函數是3；當=1時，是可行解，目標函數是4；比較可以得到，最優解是= ，目標函數最優值是3.所以，可以關閉消防站②。，如果約束條件時型的，我們加M（是01變量，M是很大的常數）的方法統一在一個問題中。如果是型的，我們將如何利用和M呢？解：在m個約束條件右端分別減去M（是01變量，M是很大的常數，i=1，2…m）并且：（1）max z=4+3+2. 25+34 4++33+1,=0或1解：將（0，0，0）（0，0，1）（0，1，0）（1，0，0）（0，1，1）（1，0，1）（1，1，0）（1，1，1）分別帶入到約束條件中，可以得到：原問題的最優解是（0，0，1），目標函數最優值2.（2）min z=2+5+3+4 . 4+++02+4+2+4++1，，=0或1解：= 是一個可行解，目標函數數值是4；所以可以增加約束條件：2+5+3+44把可能的解（0，0，0，0）（0，0，0，1）…（1，1，1，1）分別帶入約束條件的問題中，得到最優解= ，目標函數最優值4.，指派他們完成4種工作，每人做各種工作所消耗的時間如下表，問指派哪個人去完成哪種工作，可以使得總耗時最??？ 任務人員ABCD甲15182124乙19232218丙26171619丁19212317解：系數矩陣C為：① 系數矩陣的每行元素減去該行的最小元素得矩陣B② B矩陣的每列元素減去該列的最小元素得到矩陣A此時，細數矩陣的每行每列都有元素0.先給加圈，然后給加圈，劃掉。給加圈，劃掉得：此時，畫圈的數目是3,少于4個，所以指派不成功，進入下一步，給第四行打√號，給第四列打√號，給第二行打√號，將第一，第三行畫一橫線，將第四列畫縱線，變換矩陣得到給第一，第四列打√號，對第一，第二，第四行打√號，給第一，第四列畫一縱線，第三行畫一橫線，變換矩陣得到 甲 乙 丙 丁得到最優指派方案為： 甲—B；乙—A。 丙—C；丁—D。所消耗的總時間是70.試題：1. （2006年復旦大學）采用變量代換，試把非線性0—1整數規劃為0或1轉換成一個0—1整數規劃。當解題分析：0—1規劃即約束中自變量只能取值0或1。當否則解題過程：令 ，故有否則再令 ，故有而與等價，故原問題可等價地寫為為0或12. （2005年南京大學）現要在5個工人中確定4個人來分別完成四項工作中的一項工作。由于每個工人的技術特長不同，他們完成各項工作所需的工時也不同。每個工人完成每項工作所需工時如表5—1所示。表5—1工作所需工時工人Ⅰ9437Ⅱ4656Ⅲ5475Ⅳ7523Ⅴ10674試找出一個工作分配方案，使總工時最少。解題分析：本題屬“不平衡”指派問題，故應先虛擬一項工作，使其平衡，再按常規求解即可。解題過程：虛擬一項工作E，設每人完成E所需時間都是“0”，從而轉化為五個人完成五項工作的分配問題，再用匈牙利法求解。最優解為：Ⅰ—C，Ⅱ—A，Ⅲ—B，Ⅳ—D，Ⅴ—E，即應安排工人Ⅰ、Ⅱ、Ⅲ、Ⅳ分別完成工作C、A、B、D，此時所用時間最少，為3+4+4+3=14。