運(yùn)籌學(xué)習(xí)題集二

1、精選優(yōu)質(zhì)文檔-傾情為你奉上運(yùn)籌學(xué)習(xí)題集二 習(xí)題一1.1 用法求解下列線性規(guī)劃問題并指出各問題是具有唯一最優(yōu)解、無窮多最優(yōu)解、無界解或無可行解。(1) min z 6x14x2 (2) max z 4x18x2 st. 2x1 x21 st. 2x12x2103x1 4x21.5 x1 x28x1, x20 x1, x20(3) max z x1 x2 (4) max z 3x12x2 st. 8x16x224 st. x1x214x16x212 2x12x242x24 x1, x20x1, x20(5) max z 3x19x2 (6) max z 3x14x2st. x13x222 st.

2、x12x28x1 x24 x12x212x26 2x1 x2162x15x20 x1, x20x1, x201.2. 在下列線性規(guī)劃問題中找出所有基本解指出哪些是基本可行解并分別代入目標(biāo)函數(shù)比較找出最優(yōu)解。(1) max z 3x15x2 (2) min z 4x112x218x3st. x1 x3 4 st. x1 3x3 x4 32x2 x4 12 2x22x3 x553x1 2x2 x5 18 xj 0 （j1,5）xj 0 （j1,5）1.3. 分別用法和單純形法求解下列線性規(guī)劃問題并對照指出單純形法迭代的每一步相當(dāng)于法可行域中的哪一個頂點(diǎn)。(1) max z 10x15x2 st.

3、3x14x295x12x28x1, x20(2) max z 100x1200x2st. x1 x2500x1 2002x16x21200 x1, x201.4. 分別用大M法和兩階段法求解下列線性規(guī)劃問題并指出問題的解屬于哪一類：(1) max z 4x15x2 x3 (2) max z 2x1 x2 x3st. 3x12x2 x318 st. 4x12x22x342x1 x2 4 2x14x2 20x1 x2 x35 4x18x22x316xj 0 （j1,2,3） xj 0 （j1,2,3）(3) max z x1 x2 (4) max z x12x23x3x4 st. 8x16x224

4、 st. x12x23x3154x16x212 2x1 x25x3202x24 x12x2 x3 x410x1, x20 xj 0 （j1,4）(5) max z 4x16x2 (6) max z 5x13x26x3 st. 2x14x2 180 st. x12x2 x3183x12x2 150 2x1 x23x316x1 x257 x1 x2 x310x222 x1, x20x3無約束x1, x201.5 線性規(guī)劃問題max zCXAXbX0如X*是該問題的最優(yōu)解又0為某一常數(shù)分別討論下列情況時(shí)最優(yōu)解的變化：（1）目標(biāo)函數(shù)變?yōu)閙ax zCX；（2）目標(biāo)函數(shù)變?yōu)閙ax z（C）X；（3）目標(biāo)函

5、數(shù)變?yōu)閙ax z X約束條件變?yōu)锳Xb。1.6 下表中給出某求極大化問題的單純形表問表中a1, a2, c1, c2, d為何值時(shí)以及表中變量屬于哪一種類型時(shí)有：（1）表中解為唯一最優(yōu)解；（2）表中解為無窮多最優(yōu)解之一；（3）表中解為退化的可行解；（4）下一步迭代將以x1替換基變量x5 ；（5）該線性規(guī)劃問題具有無界解；（6）該線性規(guī)劃問題無可行解。x1 x2 x3 x4 x5x3 d 4 a1 1 0 0 x4 2 1 5 0 1 0x5 3 a2 3 0 0 1cj zj c1 c2 0 0 01.7 戰(zhàn)斗機(jī)是一種重要的作戰(zhàn)工具但要使戰(zhàn)斗機(jī)發(fā)揮作用必須有足夠的駕駛員。因此生產(chǎn)出來的戰(zhàn)斗機(jī)除

6、一部分直接用于戰(zhàn)斗外需抽一部分用于駕駛員。已知每年生產(chǎn)的戰(zhàn)斗機(jī)數(shù)量為aj（j1,n）又每架戰(zhàn)斗機(jī)每年能出k名駕駛員問應(yīng)如何分配每年生產(chǎn)出來的戰(zhàn)斗機(jī)使在n年內(nèi)生產(chǎn)出來的戰(zhàn)斗機(jī)為空防作出最大貢獻(xiàn)？1.8. 某石油管道公司希望知道在下圖所示的管道絡(luò)中可以流過的最大流量是多少及怎樣輸送弧上數(shù)字是容量限制。請建立此問題的線性規(guī)劃模型不必求解。2 5 410 3 111 4 3 656 8 73 51.9. 某晝夜服務(wù)的公交線每天各時(shí)間區(qū)段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：班 次 時(shí) 間 所需人數(shù)1 6:00-10:00 602 10:00-14:00 703 14:00-18:00 604 18:00-22:

7、00 505 22:00-2:00 206 2:00-6:00 30設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間區(qū)段一開始時(shí)上班并連續(xù)工作八小時(shí)問該公交線至少配備多少名司機(jī)和乘務(wù)人員。列出此問題的線性規(guī)劃模型。1.10 某班有男生30人女生20人周日去植樹。根據(jù)經(jīng)驗(yàn)一天男生平均每人挖坑20個或栽樹30棵或給25棵樹澆水；女生平均每人挖坑10個或栽樹20棵或給15棵樹澆水。問應(yīng)怎樣安排才能使植樹（包括挖坑、栽樹、澆水）最多？請建立此問題的線性規(guī)劃模型不必求解。1.11.某糖果用原料A、B、C加工成三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果中A、B、C含量原料成本各種原料的每月限制用量三種牌號糖果的單位加工費(fèi)

8、及售價(jià)如下表所示。問該每月應(yīng)生產(chǎn)這三種牌號糖果各多少千克使該獲利最大？試建立此問題的線性規(guī)劃的數(shù)學(xué)模型。甲 乙 丙 原料成本(/千克) 每月限量（千克）A 60 15 2.00 2000B 1.50 2500C 20 60 50 1.00 1200加工費(fèi)（/千克） 0.50 0.40 0.30售 價(jià) 3.40 2.85 2.251.12. 某商店制定712月進(jìn)貨售貨計(jì)劃已知商店倉庫容量不得超過500件6月底已存貨200件以后每月初進(jìn)貨一次假設(shè)各月份此商品買進(jìn)售出單價(jià)如下表所示問各月進(jìn)貨售貨各多少才能使總收入最多？請建立此問題的線性規(guī)劃模型不必求解。月 份 7 8 9 10 11 12買進(jìn)單價(jià)

9、28 24 25 27 23 23售出單價(jià) 29 24 26 28 22 251.13 .某農(nóng)場有100公頃土地及15000資金可用于發(fā)展生產(chǎn)。農(nóng)場勞動力情況為秋冬季3500人日春夏季4000人日如勞動力本身用不了時(shí)可外出干活春夏季收入為2.1人日秋冬季收入為1.8人日。該農(nóng)場種植三種作物：大豆、玉米、小麥并飼養(yǎng)奶牛和雞。種作物時(shí)不需要專門投資而飼養(yǎng)動物時(shí)每頭奶牛投資400每只雞投資3。養(yǎng)奶牛時(shí)每頭需撥出1.5公頃土地種飼草并占用人工秋冬季為100人日春夏季為50人日年凈收入400每頭奶牛。養(yǎng)雞時(shí)不占土地需人工為每只雞秋冬季需0.6人日春夏季為0.3人日年凈收人為2每只雞。農(nóng)場現(xiàn)有雞舍允許最多

10、養(yǎng)3000只雞牛欄允許最多養(yǎng)32頭奶牛。三種作物每年需要的人工及收人情況如下表所示。大豆玉米麥子秋冬季需人日數(shù)203510春夏季需人日數(shù)507540年凈收入(公頃)175300120試決定該農(nóng)場的經(jīng)營方案使年凈收人為最大。(建立線性規(guī)劃模型不需求解)習(xí)題二2.1 寫出下列線性規(guī)劃問題的對偶問題(1) max z 10x1 x22x3 (2) max z 2x1 x23x3 x4st. x1 x22 x310 st. x1 x2 x3 x4 54x1 x2 x320 2x1 x23x3 4xj 0 （j1,2,3） x1 x3 x41x1x30x2x4無約束(3) min z 3x12 x23x

11、34x4 (4) min z 5 x16x27x3st. x12x23x34x43 st. x15x23x3 15x23x34x45 5x16x210x3 202x13x27x3 4x42 x1 x2 x35x10x40x2x3 無約束 x10 x20x3 無約束2.2 已知線性規(guī)劃問題max zCXAX=bX0。分別說明發(fā)生下列情況時(shí)其對偶問題的解的變化：（1）問題的第k個約束條件乘上常數(shù)（0）；（2）將第k個約束條件乘上常數(shù)（0）后加到第r個約束條件上；（3）目標(biāo)函數(shù)改變?yōu)閙ax zCX（0）；（4）模型中全部x1用3 代換。2.3 已知線性規(guī)劃問題 min z8x16x23x36x4st

12、. x12x2 x433x1 x2 x3 x46x3 x42 x1 x3 2xj0（j1,2,3,4）(1) 寫出其對偶問題；(2) 已知原問題最優(yōu)解為x*（1120）試根據(jù)對偶理論直接求出對偶問題的最優(yōu)解。2.4 已知線性規(guī)劃問題 min z2x1x25x36x4 對偶變量st. 2x1 x3 x48 y12x12x2x32x412 y2xj0（j1,2,3,4）其對偶問題的最優(yōu)解y1*=4；y2*=1試根據(jù)對偶問題的性質(zhì)求出原問題的最優(yōu)解。2.5 考慮線性規(guī)劃問題 max z2x14x23x3 st. 3x14 x22x3602x1 x22x340x13x22x380xj0 （j1,2,3

13、）（1）寫出其對偶問題（2）用單純形法求解原問題列出每步迭代計(jì)算得到的原問題的解與互補(bǔ)的對偶問題的解；（3）用對偶單純形法求解其對偶問題并列出每步迭代計(jì)算得到的對偶問題解及與其互補(bǔ)的對偶問題的解；（4）比較（2）和（3）計(jì)算結(jié)果。2.6 已知線性規(guī)劃問題 max z10x15x2st. 3x14x295x12x28xj0（j1,2）用單純形法求得最終表如下表所示：x1x2x3x4bx201 x110 1?j=cj-Zj00 試用靈敏度分析的方法分別判斷：（1）目標(biāo)函數(shù)系數(shù)c1或c2分別在什么范圍內(nèi)變動上述最優(yōu)解不變；（2）約束條件右端項(xiàng)b1b2當(dāng)一個保持不變時(shí)另一個在什么范圍內(nèi)變化上述最優(yōu)基保

14、持不變；（3）問題的目標(biāo)函數(shù)變?yōu)閙ax z 12x14x2時(shí)上述最優(yōu)解的變化；（4）約束條件右端項(xiàng)由 變?yōu)?時(shí)上述最優(yōu)解的變化。2.7 線性規(guī)劃問題如下： max z5x15x213x3 st. x1x23x320 12x14x210x390 xj0 （j1,2,3）先用單純形法求解然后分析下列各種條件下最優(yōu)解分別有什么變化？（1）約束條件的右端常數(shù)由20變?yōu)?0；（2）約束條件的右端常數(shù)由90變?yōu)?0；（3）目標(biāo)函數(shù)中x3的系數(shù)由13變?yōu)?；（4）x1的系數(shù)列向量由（112）T變?yōu)椋?5）T；（5）增加一個約束條件：2x13x25x350；（6）將原約束條件改變?yōu)椋?0x15x210x310

15、0。2.8 用單純形法求解某線性規(guī)劃問題得到最終單純形表如下：cj基變量50401060Sx1x2x3x4ac01 16bd10 24?j=cj-Zj00efg（1）給出abcdefg的值或表達(dá)式；（2）指出原問題是求目標(biāo)函數(shù)的最大值還是最小值；（3）用a+?ab+?b分別代替a和b仍然保持上表是最優(yōu)單純形表求?a?b滿足的范圍。2.9 某文教用品用原材料白坯紙生產(chǎn)原稿紙、日記本和練習(xí)本三種產(chǎn)品。該現(xiàn)有工人100人每月白坯紙量為30000千 克。已知工人的勞動生產(chǎn)率為：每人每月可生產(chǎn)原稿紙30捆或日記本30打或練習(xí)本30箱。已知原材料消耗為：每捆原稿紙用白坯紙 千克每打日記本用白坯紙 千克每箱

16、練習(xí)本用白坯紙 千克。又知每生產(chǎn)一捆原稿紙可獲利2生產(chǎn)一打日記本獲利3生產(chǎn)一箱練習(xí)本獲利1。試確定：（1）現(xiàn)有生產(chǎn)條件下獲利最大的方案；（2）如白坯紙的數(shù)量不變當(dāng)工人數(shù)不足時(shí)可招收臨時(shí)工臨時(shí)工工資支出為每人每月40則該要不要招收臨時(shí)工？如要的話招多少臨時(shí)工最合適？2.10 某生產(chǎn)甲、乙兩種產(chǎn)品需要A、B兩種原料生產(chǎn)消耗等參數(shù)如下表（表中的消耗系數(shù)為千克/件）。產(chǎn)品原料甲乙可用量（千克）原料成本（/千克）A241601.0B321802.0銷售價(jià)（）1316（1）請構(gòu)造數(shù)學(xué)模型使該利潤最大并求解。（2）原料A、B的影子各為多少。（3）現(xiàn)有新產(chǎn)品丙每件消耗3千克原料A和4千克原料B問該產(chǎn)品的銷售至

17、少為多少時(shí)才值得投產(chǎn)。（4）工可在市場上買到原料A。工是否應(yīng)該購買該原料以擴(kuò)大生產(chǎn)？在保持原問題最優(yōu)基的不變的情況下最多應(yīng)購入多少？可增加多少利潤？習(xí)題三3.1 求解下表所示的運(yùn)輸問題分別用最小素法、西北角法和伏格爾法給出初始基可行解：B1B2B3B4量A1（10）（6）（7）（12）4A2（16）（10）（5）（9）9A3（5）（4）（10）（10）5需要量5346183.2由產(chǎn)地A1A2發(fā)向銷地B1B2的單位費(fèi)用如下表產(chǎn)地允許存貯銷地允許缺貨存貯和缺貨的單位運(yùn)費(fèi)也列入表中。求最優(yōu)調(diào)運(yùn)方案使總費(fèi)用最省。B1B2量存貯費(fèi)/件A1854003A2693004需要量200350缺貨費(fèi)/件253.3

18、 對如下表的運(yùn)輸問題：AB量X100（6）（4）100Y30（5）50（8）80Z（2）60（7）60需要量130110240(1)若要總運(yùn)費(fèi)最少該方案是否為最優(yōu)方案?(2)若產(chǎn)地Z的量改為100求最優(yōu)方案。3.4 某利潤最大的運(yùn)輸問題其單位利潤如下表所示：B1B2B3B4量A1（6）（7）（5）（8）8A2（4）（5）（10）（8）9A3（2）（9）（7）（3）7需要量865524(1)求最優(yōu)運(yùn)輸方案該最優(yōu)方案有何特征?(2)當(dāng)A1的量和B3的需求量各增加2時(shí)結(jié)果又怎樣?3.5 某玩具公司分別生產(chǎn)三種新型玩具每月可量分別為1000、2000、2000件它們分別被送到甲、乙、丙三個百貨商店銷售

19、。已知每月百貨商店各類玩具預(yù)期銷售量均為1500件由于經(jīng)營方面原因各商店銷售不同玩具的盈利額不同,見下表。又知丙百貨商店要求至少C玩具1000件 而拒絕進(jìn)A玩具。求滿足上述條件下使總盈利額最大的銷分配方案。甲 乙 丙 可量A 5 4 1000B 16 8 9 2000C 12 10 11 20003.6 目前城市大學(xué)能存貯200個文件在硬盤上100個文件在計(jì)算機(jī)存貯器上300個文件在磁帶上。用戶想存貯300個字處理文件100個源程序文件100個數(shù)據(jù)文件。每月一個典型的字處理文件被訪問8次一個典型的源程序文件被訪問4次一個典型的數(shù)據(jù)文件被訪問2次。當(dāng)某文件被訪問時(shí)重新找到該文件所需的時(shí)間取決于文

20、件類型和存貯介質(zhì)如下表。時(shí) 間（分鐘） 處理文件 源程序文件 數(shù)據(jù)文件硬盤 5 4 4存貯器 2 1 1磁帶 10 8 6如果目標(biāo)是極小化每月用戶訪問所需文件所花的時(shí)間請構(gòu)造一個運(yùn)輸問題的模型來決定文件應(yīng)該怎么存放并求解。3.7 已知下列五名運(yùn)動員各種姿勢的游泳成績（各為50米）如表5-2：試用運(yùn)輸問題的方法來決定如何從中選拔一個參加200混合泳的接力隊(duì)使預(yù)期比賽成績?yōu)樽詈谩Ｚw錢張王周仰 泳37.732.933.837.035.4蛙 泳43.433.142.234.741.8蝶 泳33.328.538.930.433.6自由泳29.226.429.628.531.13.8 求總運(yùn)費(fèi)最小的運(yùn)輸問

21、題其中某一步的運(yùn)輸圖如下表。B1B2B3量A13（3）（5）（7）3A22（4）4（2）（4）6A3（5）1（6）5（3）d需要量abce（1）寫出a,b,c,d,e的值并求出最優(yōu)運(yùn)輸方案；（2）A3到B1的單位運(yùn)費(fèi)滿足什么條件時(shí)表中運(yùn)輸方案為最優(yōu)方案。3.9 某一實(shí)際的運(yùn)輸問題可以敘述如下：有n個地區(qū)需要某種物資需要量分別為bj（j1,n）。這些物資均由某公司分設(shè)在m個地區(qū)的工各工的產(chǎn)量分別為ai（i1,m）已知從i地區(qū)的工至第j個需求地區(qū)的單位物資的運(yùn)價(jià)為cij又 試闡述其對偶問題并解釋對偶變量的經(jīng)濟(jì)意義。3.10. 為確保飛行安全飛機(jī)上的發(fā)動機(jī)每半年必須強(qiáng)迫更換進(jìn)行大修。某維修估計(jì)某種型

22、號戰(zhàn)斗機(jī)從下一個半年算起的今后三年內(nèi)每半年發(fā)動機(jī)的更換需要量分別為：50140。更換發(fā)動機(jī)時(shí)可以換上新的也可以用經(jīng)過大修的舊的發(fā)動機(jī)。已知每臺新發(fā)動機(jī)的購置費(fèi)為10萬而舊發(fā)動機(jī)的維修有兩種方式：快修每臺2萬半年交貨（即本期拆下來送修的下批即可用上）；慢修每臺1萬但需一年交貨（即本期拆下來送修的需下下批才能用上）。設(shè)該新接受該項(xiàng)發(fā)動機(jī)更換維修任務(wù)又知這種型號戰(zhàn)斗機(jī)三年后將退役退 役后這種發(fā)動機(jī)將報(bào)廢。問在今后三年的每半年內(nèi)該為滿足維修需要各新購、送去快修和慢修的發(fā)動機(jī)數(shù)各是多少使總的維修費(fèi)用為最??？（將此問題歸結(jié)為運(yùn)輸問題只列出產(chǎn)銷平衡表與單位運(yùn)價(jià)表不求數(shù)值解。）3.11 甲、乙兩個煤礦分別生產(chǎn)

23、煤500萬噸A、B、C三個電發(fā)電需要各電用量分別為300、300、400萬噸。已知煤礦之間、煤礦與電之間以及各電之間相互距離（單位：公里）如下列三個表所示。又煤可以直接運(yùn)達(dá)也可經(jīng)轉(zhuǎn)運(yùn)抵達(dá),試確定從煤礦到各電間煤的最優(yōu)調(diào)運(yùn)方案（最小總噸公里數(shù)）。從 到 甲 乙 從 到 A B C 從 到 A B C 甲 0 120 甲 150 120 80 A 0 70 100乙 100 0 乙 60 160 40 B 50 0 120C 100 150 0習(xí)題四4.1 分別用法和單純形法求解下述目標(biāo)規(guī)劃問題（1）min z 1（ ）2 st. x1 x2 d1 d110.5x1 x2 d2d223x13x2

24、d3 d350x1x20；didi0（i =123）（2） min z 1（2 3 ）2 3 st. x1 x2d1d1 10x1 d2d2 45x13x2d3d3 56x1 x2d4d4 12x1x20；didi 0（i =14）4.2考慮下述目標(biāo)規(guī)劃問題min z 1（d1d2）22d42d33d1st. x1 d1d120x2d2d2355x13x2d3d3220x1x2d4d460x1x20；didi 0（i =14）（1）求滿意解；（2）當(dāng)?shù)诙€約束右端項(xiàng)由35改為75時(shí)求解的變化；（3）若增加一個新的目標(biāo)約束：4x1x2d5d58該目標(biāo)要求盡量達(dá)到目標(biāo)值并列為第一優(yōu)先級考慮求解的變

25、化；（4）若增加一個新的變量x3其系數(shù)列向量為（0111）T則滿意解如何變化？4.3 一個小型的無線電廣播臺考慮如何最好地來安排音樂、新聞和商業(yè)節(jié)目時(shí)間。依據(jù)法律該臺每天允許廣播12小時(shí)其中商業(yè)節(jié)目用以贏利每小時(shí)可收入250美新聞節(jié)目每小時(shí)需支出40美音樂節(jié)目每播一小時(shí)費(fèi)用為17.50美。法律規(guī)定正常情況下商業(yè)節(jié)目只能占廣播時(shí)間的20每小時(shí)至少安排5分鐘新聞節(jié)目。問每天的廣播節(jié)目該如何安排？優(yōu)先級如下：1：滿足法律規(guī)定要求；2：每天的純收入最大。試建立該問題的目標(biāo)規(guī)劃模型。4.4 某企業(yè)生產(chǎn)兩種產(chǎn)品產(chǎn)品售出后每件可獲利10產(chǎn)品售出后每件可獲利8。生產(chǎn)每件產(chǎn)品需3小時(shí)的裝配時(shí)間每件產(chǎn)品需2小時(shí)裝

26、配時(shí)間?？捎玫难b配時(shí)間共計(jì)為每周120小時(shí)但允許加班。在加班時(shí)間內(nèi) 生產(chǎn)兩種產(chǎn)品時(shí)每件的獲利分別降低1。加班時(shí)間限定每周不超過40小時(shí)企業(yè)希望總獲利最大。試憑自己的經(jīng)驗(yàn)確定優(yōu)先結(jié)構(gòu)并建立該問題的目標(biāo)規(guī)劃模型。4.5 某生產(chǎn)A、B兩種型號的微型計(jì)算機(jī)產(chǎn)品。每種型號的微型計(jì)算機(jī)均需要經(jīng)過兩道工序I、II。已知每臺微型計(jì)算機(jī)所需要的加工時(shí)間、銷售利潤及工每周最大加工能力的數(shù)據(jù)如下：AB每周最大加工能力I46150II3270利潤（/臺）300450工經(jīng)營目標(biāo)的期望值及優(yōu)先級如下：1：每周總利潤不得低于10000；2：因合同要求A型機(jī)每周至少生產(chǎn)10臺：B型機(jī)每周至少生產(chǎn)15臺；3：由于條件限制且希望

27、充分利用工的生產(chǎn)能力工序I的每周生產(chǎn)時(shí)間必須恰好為150小時(shí)工序II的每周生產(chǎn)時(shí)間可適當(dāng)超過其最大加工能力（允許加班）。試建立此問題的目標(biāo)規(guī)劃模型習(xí)題五5.1 試將下述非線性的01規(guī)劃問題轉(zhuǎn)換為線性的01規(guī)劃問題max z x12x2x3x33st. 2x13x2x3 3xj0或1（j1,2,3）5.2 某鉆井隊(duì)要從以下10個可選擇的井位中確定5個鉆井探油使總的鉆探費(fèi)用為最小。若10個井位的代號為s1s2s10相應(yīng)的鉆探費(fèi)用為c1c2c10并且井位選擇上要滿足下列限制條件：（1）或選擇s1和s7或選擇鉆探s8；（2）選擇了s3或s4就不能選s5或反過來也一樣；（3）在s5s6s7s8中最多只能

28、選兩個。試建立此問題的整數(shù)規(guī)劃模型。5.3 用分枝定界法求解下列整數(shù)規(guī)劃問題(1) max z x1x2st. x1 x2 2x1 x2 x1x20且為整數(shù)(2) max z 2x13x2st. 5x17x235 4x19x236 x1x20且為整數(shù)5.4 用割平面法求解下列整數(shù)規(guī)劃問題(1) max z 7x19x2 st. x13 x2 67x1 x2 35 x1x20且為整數(shù)(2) min z 4x15x2st. 3x12x27x14x253x1 x22x1, x20且為整數(shù)5.5用隱枚舉法求解01整數(shù)規(guī)劃問題max z 3x12x25x32x43x5st. x1 x2 x32x4 x5

29、 47x1 3x34x43x5 811x16x2 3x43x5 3xj 0或1（j15）5.6 請用解01整數(shù)規(guī)劃的隱枚舉法求解下面的兩維01背包問題：max f = 2x1+2x2+3x3s.t. x1+2x2+2x342x1+x2+3x35xj=0或1j=1,2,3 5.7 用匈牙利法求解如下效率矩陣的指派問題7 9 10 1213 12 16 1715 16 14 1511 12 15 165.8 分配甲、乙、丙、丁四人去完成五項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)時(shí)間如下表所示。由于任務(wù)數(shù)多于人數(shù)故規(guī)定其中有一個人可兼完成兩項(xiàng)任務(wù)其余三人每人完成一項(xiàng)。試確定總花費(fèi)時(shí)間為最少的指派方案。人 任務(wù) A

30、B C D E甲 25 29 31 42 37乙 39 38 26 20 33丙 34 27 28 40 32丁 24 42 36 23 455.9 已知下列五人各種姿勢的游泳成績（各為50米）試問如何進(jìn)行指派從中選拔一個參加200米混合泳的接力隊(duì)使預(yù)期比賽成績?yōu)樽詈谩Ｚw錢張王周仰 泳37.732.933.837.035.4蛙 泳43.433.142.234.741.8蝶 泳33.328.538.930.433.6自由泳29.226.429.628.531.15.10. 運(yùn)籌學(xué)中著名的旅行商販（貨郎擔(dān)）問題可以敘述如下：某旅行商販從某一城市出發(fā)到其它幾個城市去推銷商品規(guī)定每個城市均須到達(dá)而且只

31、到達(dá)一次然后回到原出發(fā)城市。已知城市i和j之間的距離為dij問該商販應(yīng)選擇一條什么樣的線順序旅行使總的旅程為最短。試對此問題建立整數(shù)規(guī)劃模型。5.11. 有三個不同的產(chǎn)品要在三臺機(jī)床上加工每個產(chǎn)品必須首先在機(jī)床1上加工然后依次在機(jī)床23上加工。在每臺機(jī)床上加工三個產(chǎn)品的順序應(yīng)保持一樣假定用tij表示在第j機(jī)床上加工第i個產(chǎn)品的時(shí)間問應(yīng)如何安排使三個產(chǎn)品總的加工周期為最短。試建立此問題的整數(shù)規(guī)劃模型。習(xí)題參考第一章 線性規(guī)劃及單純形法1.1（1）解：第一求可行解集合。令兩個約束條件為等式得到兩條直線在第一象限劃出滿足兩個不等式的區(qū)域其交集就是可行集或稱為可行域如圖1-1所示交集為（1/2, 0）

32、。第二繪制目標(biāo)函數(shù)圖形。將目標(biāo)函數(shù)的系數(shù)組成一個坐標(biāo)點(diǎn)（64）過原點(diǎn)O作一條矢量指向點(diǎn)（64）矢量的長度不限矢量的斜率保持4比6再作一條與矢量垂直的直線這條直線就是目標(biāo)函數(shù)圖形目標(biāo)函數(shù)圖形的位置任意如果通過原點(diǎn)則目標(biāo)函數(shù)值Z=0如圖1-2所示。第三求最優(yōu)解。圖1-2的矢量方向是目標(biāo)函數(shù)增加的方向或稱梯度方向在求最小值時(shí)將目標(biāo)函數(shù)圖形沿梯度方向的反方向平行移動（在求最大值時(shí)將目標(biāo)函數(shù)圖形沿梯度方向平行移動）直到可行域的邊界停止移動其交點(diǎn)對應(yīng)的坐標(biāo)就是最優(yōu)解如圖1-3所示。最優(yōu)解x=（1/2, 0）,目標(biāo)函數(shù)的最小值Z=3。（2）無可行解；求解方法與（1）類似（3）無界解；（4）無可行解；（5）無

33、窮多最優(yōu)解 z*=66（6）唯一最優(yōu)解 z*=92/3,x1=20/3,x2=3/81.2 （1）解：由題目可知其系數(shù)矩陣為因 線性獨(dú)立故有 令非基變量 得 得到一個基可行解 。線性獨(dú)立故有 令非基變量 得 得到一個基本解但非可行解 。同理可以求出得基本可行解 。得基本可行解 。得基本可行解 。得基本可行解 。得基本 非可行解 。得基本非可行解 。（1）、（2）如下表所示其中打三角符號的是基本可行解打星號的為最優(yōu)解：x1 x2 x3 x4 x5 z x1 x2 x3 x4 x5 0 0 4 12 18 0 0 0 0 -3 -5 4 0 0 12 6 12 3 0 0 0 -56 0 -2 1

34、2 0 18 0 0 1 0 -3 4 3 0 6 0 27 -9/2 0 5/2 0 0 0 6 4 0 6 30 0 5/2 0 -3 0* 2 6 2 0 0 36 0 3/2 1 0 0 *4 6 0 0 -6 42 3 5/2 0 0 0 0 9 4 -6 0 45 0 0 5/2 9/2 0 1.3(1)解：單純形法首先將問題化為標(biāo)準(zhǔn)型。加松弛變量x3x4得其次列出初始單純形表計(jì)算最優(yōu)值。CBXB10500bX1X2X3X40X3341090X452018j105000X3014/51-3/521/510X112/501/58/5j010-25X2115/14-3/143/210X

35、100-1/72/71j00-5/14-25/14（表一）由單純形表一得最優(yōu)解為 法：（2）略1.4 (1) 解：大M法首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式式中x4x5為松弛變量x5可作為一個基變量第一、三約束分別加入人工變量x6 x7目標(biāo)函數(shù)中加入-Mx6-Mx7一項(xiàng)得到大M單純形法數(shù)學(xué)模型由單純形表計(jì)算：CBXB45100-M-MbX1X2X3X4X5X6X7-MX6321-1010180X521001004-MX711-100015j4+4M5+3M1-M000-MX6-101-1-210105X221001004-MX7-10-100011j4-2M01-M-2M001X3-101-1-2010

36、0X22100104-MX7-200-1-2111j5-2M001-M2-2M0表1.4-1.1在迭代過程中人工變量一旦出基后不會在進(jìn)基所以當(dāng)人工變量X6出基后對應(yīng)第六列的系數(shù)可以不再計(jì)算以減少計(jì)算量。當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在人工變量大于零時(shí)則表明原線性規(guī)劃無可行解。兩階段單純形法首先化標(biāo)準(zhǔn)形同大M法第一、三約束分別加入人工變量x6 x7后構(gòu)造第一階段問題用單純形法求解得到第一階段問題的計(jì)算表1.4-1.2CBXB0000011bX1X2X3X4X5X6X71X6321-1010180X5210010041X711-100015j-4-3010001X601/21-1-3/210

37、120X111/2001/20021X701/2-10-1/2013j0-1012001X6-101-1-210100X2210020041X7-10-10-1011j2001300表1.4-1.2在第一階段的最優(yōu)解中人工變量不為零則原問題無可行解。注：在第二階段計(jì)算時(shí)初始表中的檢驗(yàn)數(shù)不能引用第一階段最優(yōu)表的檢驗(yàn)數(shù)必須換成原問題的檢驗(yàn)數(shù)。(2) 無窮多最優(yōu)解如X1（400）；X2（008）(3) 無界解 (4) 唯一最優(yōu)解 X*（5/25/25/20）(5) 唯一最優(yōu)解 X*（2433）(6) 唯一最優(yōu)解 X*（1404）1.5（4）X*仍為最優(yōu)解max zCX；（5）除C為常數(shù)向量外一般X*

38、不再是該問題的最優(yōu)解；（6）最優(yōu)解變?yōu)閄*目標(biāo)函數(shù)值不變。1.6（7）d0,c10, c20（8）d0,c10, c20,但c1c2中至少一個為零（9）d0或d0而c10且d/4=3/a2（10）c10,d/43/a2（11）c20,a10（12）x5為人工變量且c10, c201.7解：設(shè)xj表示第j年生產(chǎn)出來分配用于作戰(zhàn)的戰(zhàn)斗機(jī)數(shù)；yj為第j年已出來的駕駛員；（ajxj）為第j年用于駕駛員的戰(zhàn)斗機(jī)數(shù)；zj為第j年用于駕駛員的戰(zhàn)斗機(jī)總數(shù)。則模型為max z = nx1+(n-1)x2+2xn-1+xn s.t. zj=zj-1+(aj-xj)yj=yj-1+k(aj-xj)x1+x2+xjy

39、jxj,yj,zj0 (j=1,2, ,n)1.8 提示：設(shè)出每個管道上的實(shí)際流量則發(fā)點(diǎn)發(fā)出的流量等于收點(diǎn)收到的流量中間點(diǎn)則流入等于流出再考慮容量限制條件即可。目標(biāo)函數(shù)為發(fā)出流量最大。設(shè)xij從點(diǎn)i到點(diǎn)j的流量max zx12x13st. x12x23x24x25x13x23x34x35x24x34x54x46x25x35x54x56 以上為流量平衡條件x12x13x46x56 始點(diǎn)收點(diǎn)x1210x136x234x245x253x345x358x4611x543x567xij0對所有ij1.9 提示：設(shè)每個區(qū)段上班的人數(shù)分別為x1x2x6即可1.10 解：設(shè)男生中挖坑、栽樹、澆水的人數(shù)分別為x

40、11 、x12 、x13女生中挖坑、栽樹、澆水的人數(shù)分別為x21 、x22 、x23 ,S為植樹棵樹。由題意模型為：max S20 x11+10 x21 s.t. x11 +x12 +x13 =30x21 +x22 +x23 =2020 x11+10 x21 =30 x12+20 x22=25 x13+15 x23Xij0 i=1,2；j=1,2,31.11 解：設(shè)各生產(chǎn)x1,x2,x3max z = 1.2 x1+1.175x2+0.7x3 s.t. 0.6x1+0.15x2 20000.2x1+0.25x2+0.5x325000.2x1+ 0.6x2+0.5x31200x1,x2,x301

41、.12 解：設(shè)712月各月初進(jìn)貨數(shù)量為xi件而各月售貨數(shù)量為yi件i126S為總收入則問題的模型為：max S29y124y226y328y422y525y6（28x124x225x327x423x523x6）st. y1200x1500y2200x1y1x2500y3200x1y1x2y2x3500y4200x1y1x2y2x3y3x4500y5200x1y1x2y2x3y3x4y4x5500y2200x1y1x2y2x3y3x4y4x5y5x6500xi0yi0 i126 整數(shù)1.13解：用x1x2x3分別代表大豆、玉米、麥子的種植面積（hm2公頃）；x4x5分別代表奶牛和雞的飼養(yǎng)數(shù)；x6

42、x7分別代表秋冬和春夏季多余的勞動力（人日）則有第二 章 對偶理論和靈敏度分析2.1 對偶問題為(1) (2) (3) (4) 2.2（1）因?yàn)閷ε甲兞縔=CBB-1,第k個約束條件乘上（0）即B-1的k列將為變化前的1/由此對偶問題變化后的解（y1, y2, , yk,ym）=（y1, y2, , (1/)yk,ym）（2）與前類似yr= yi= yi（ir）（3）yi=yi（i=1,2, ,m）（4）yi（i=1,2, ,m）不變2.3 (1) 對偶問題為(2) 由互補(bǔ)松弛性 （ 分別為松弛變量和最優(yōu)解）可得 從而可知又由對偶性質(zhì)的最優(yōu)性 可得四方程聯(lián)立即可求得對偶問題的最優(yōu)解：Y*（2210）2.4 解： 其對偶問題為min w=8y1+12y22y1+