1、精選優質文檔-傾情為你奉上運籌學習題集二 習題一1.1 用法求解下列線性規劃問題并指出各問題是具有唯一最優解、無窮多最優解、無界解或無可行解。(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. 在下列線性規劃問題中找出所有基本解指出哪些是基本可行解并分別代入目標函數比較找出最優解。(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. 分別用法和單純形法求解下列線性規劃問題并對照指出單純形法迭代的每一步相當于法可行域中的哪一個頂點。(1) max z 10x15x2 st.

3、3x14x295x12x28x1, x20(2) max z 100x1200x2st. x1 x2500x1 2002x16x21200 x1, x201.4. 分別用大M法和兩階段法求解下列線性規劃問題并指出問題的解屬于哪一類：(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 線性規劃問題max zCXAXbX0如X*是該問題的最優解又0為某一常數分別討論下列情況時最優解的變化：（1）目標函數變為max zCX；（2）目標函數變為max z（C）X；（3）目標函

5、數變為max z X約束條件變為AXb。1.6 下表中給出某求極大化問題的單純形表問表中a1, a2, c1, c2, d為何值時以及表中變量屬于哪一種類型時有：（1）表中解為唯一最優解；（2）表中解為無窮多最優解之一；（3）表中解為退化的可行解；（4）下一步迭代將以x1替換基變量x5 ；（5）該線性規劃問題具有無界解；（6）該線性規劃問題無可行解。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 戰斗機是一種重要的作戰工具但要使戰斗機發揮作用必須有足夠的駕駛員。因此生產出來的戰斗機除

6、一部分直接用于戰斗外需抽一部分用于駕駛員。已知每年生產的戰斗機數量為aj（j1,n）又每架戰斗機每年能出k名駕駛員問應如何分配每年生產出來的戰斗機使在n年內生產出來的戰斗機為空防作出最大貢獻？1.8. 某石油管道公司希望知道在下圖所示的管道絡中可以流過的最大流量是多少及怎樣輸送弧上數字是容量限制。請建立此問題的線性規劃模型不必求解。2 5 410 3 111 4 3 656 8 73 51.9. 某晝夜服務的公交線每天各時間區段內所需司機和乘務人員數如下：班 次 時 間 所需人數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設司機和乘務人員分別在各時間區段一開始時上班并連續工作八小時問該公交線至少配備多少名司機和乘務人員。列出此問題的線性規劃模型。1.10 某班有男生30人女生20人周日去植樹。根據經驗一天男生平均每人挖坑20個或栽樹30棵或給25棵樹澆水；女生平均每人挖坑10個或栽樹20棵或給15棵樹澆水。問應怎樣安排才能使植樹（包括挖坑、栽樹、澆水）最多？請建立此問題的線性規劃模型不必求解。1.11.某糖果用原料A、B、C加工成三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果中A、B、C含量原料成本各種原料的每月限制用量三種牌號糖果的單位加工費

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

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

10、養3000只雞牛欄允許最多養32頭奶牛。三種作物每年需要的人工及收人情況如下表所示。大豆玉米麥子秋冬季需人日數203510春夏季需人日數507540年凈收入(公頃)175300120試決定該農場的經營方案使年凈收人為最大。(建立線性規劃模型不需求解)習題二2.1 寫出下列線性規劃問題的對偶問題(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 已知線性規劃問題max zCXAX=bX0。分別說明發生下列情況時其對偶問題的解的變化：（1）問題的第k個約束條件乘上常數（0）；（2）將第k個約束條件乘上常數（0）后加到第r個約束條件上；（3）目標函數改變為max zCX（0）；（4）模型中全部x1用3 代換。2.3 已知線性規劃問題 min z8x16x23x36x4st

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

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

14、持不變；（3）問題的目標函數變為max z 12x14x2時上述最優解的變化；（4）約束條件右端項由 變為 時上述最優解的變化。2.7 線性規劃問題如下： max z5x15x213x3 st. x1x23x320 12x14x210x390 xj0 （j1,2,3）先用單純形法求解然后分析下列各種條件下最優解分別有什么變化？（1）約束條件的右端常數由20變為30；（2）約束條件的右端常數由90變為70；（3）目標函數中x3的系數由13變為8；（4）x1的系數列向量由（112）T變為（05）T；（5）增加一個約束條件：2x13x25x350；（6）將原約束條件改變為：10x15x210x310

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

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

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

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

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

20、件類型和存貯介質如下表。時 間（分鐘） 處理文件 源程序文件 數據文件硬盤 5 4 4存貯器 2 1 1磁帶 10 8 6如果目標是極小化每月用戶訪問所需文件所花的時間請構造一個運輸問題的模型來決定文件應該怎么存放并求解。3.7 已知下列五名運動員各種姿勢的游泳成績（各為50米）如表5-2：試用運輸問題的方法來決定如何從中選拔一個參加200混合泳的接力隊使預期比賽成績為最好。趙錢張王周仰 泳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 求總運費最小的運輸問

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

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

23、煤500萬噸A、B、C三個電發電需要各電用量分別為300、300、400萬噸。已知煤礦之間、煤礦與電之間以及各電之間相互距離（單位：公里）如下列三個表所示。又煤可以直接運達也可經轉運抵達,試確定從煤礦到各電間煤的最優調運方案（最小總噸公里數）。從 到 甲 乙 從 到 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習題四4.1 分別用法和單純形法求解下述目標規劃問題（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考慮下述目標規劃問題min z 1（d1d2）22d42d33d1st. x1 d1d120x2d2d2355x13x2d3d3220x1x2d4d460x1x20；didi 0（i =14）（1）求滿意解；（2）當第二個約束右端項由35改為75時求解的變化；（3）若增加一個新的目標約束：4x1x2d5d58該目標要求盡量達到目標值并列為第一優先級考慮求解的變

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

26、配時間。可用的裝配時間共計為每周120小時但允許加班。在加班時間內 生產兩種產品時每件的獲利分別降低1。加班時間限定每周不超過40小時企業希望總獲利最大。試憑自己的經驗確定優先結構并建立該問題的目標規劃模型。4.5 某生產A、B兩種型號的微型計算機產品。每種型號的微型計算機均需要經過兩道工序I、II。已知每臺微型計算機所需要的加工時間、銷售利潤及工每周最大加工能力的數據如下：AB每周最大加工能力I46150II3270利潤（/臺）300450工經營目標的期望值及優先級如下：1：每周總利潤不得低于10000；2：因合同要求A型機每周至少生產10臺：B型機每周至少生產15臺；3：由于條件限制且希望

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

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

29、 47x1 3x34x43x5 811x16x2 3x43x5 3xj 0或1（j15）5.6 請用解01整數規劃的隱枚舉法求解下面的兩維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 分配甲、乙、丙、丁四人去完成五項任務。每人完成各項任務時間如下表所示。由于任務數多于人數故規定其中有一個人可兼完成兩項任務其余三人每人完成一項。試確定總花費時間為最少的指派方案。人 任務 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米）試問如何進行指派從中選拔一個參加200米混合泳的接力隊使預期比賽成績為最好。趙錢張王周仰 泳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. 運籌學中著名的旅行商販（貨郎擔）問題可以敘述如下：某旅行商販從某一城市出發到其它幾個城市去推銷商品規定每個城市均須到達而且只

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

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

33、窮多最優解 z*=66（6）唯一最優解 z*=92/3,x1=20/3,x2=3/81.2 （1）解：由題目可知其系數矩陣為因 線性獨立故有 令非基變量 得 得到一個基可行解 。線性獨立故有 令非基變量 得 得到一個基本解但非可行解 。同理可以求出得基本可行解 。得基本可行解 。得基本可行解 。得基本可行解 。得基本 非可行解 。得基本非可行解 。（1）、（2）如下表所示其中打三角符號的是基本可行解打星號的為最優解：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)解：單純形法首先將問題化為標準型。加松弛變量x3x4得其次列出初始單純形表計算最優值。CBXB10500bX1X2X3X40X3341090X452018j105000X3014/51-3/521/510X112/501/58/5j010-25X2115/14-3/143/210X

35、100-1/72/71j00-5/14-25/14（表一）由單純形表一得最優解為 法：（2）略1.4 (1) 解：大M法首先將數學模型化為標準形式式中x4x5為松弛變量x5可作為一個基變量第一、三約束分別加入人工變量x6 x7目標函數中加入-Mx6-Mx7一項得到大M單純形法數學模型由單純形表計算：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在迭代過程中人工變量一旦出基后不會在進基所以當人工變量X6出基后對應第六列的系數可以不再計算以減少計算量。當用大M單純形法計算得到最優解并且存在人工變量大于零時則表明原線性規劃無可行解。兩階段單純形法首先化標準形同大M法第一、三約束分別加入人工變量x6 x7后構造第一階段問題用單純形法求解得到第一階段問題的計算表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在第一階段的最優解中人工變量不為零則原問題無可行解。注：在第二階段計算時初始表中的檢驗數不能引用第一階段最優表的檢驗數必須換成原問題的檢驗數。(2) 無窮多最優解如X1（400）；X2（008）(3) 無界解 (4) 唯一最優解 X*（5/25/25/20）(5) 唯一最優解 X*（2433）(6) 唯一最優解 X*（1404）1.5（4）X*仍為最優解max zCX；（5）除C為常數向量外一般X*

38、不再是該問題的最優解；（6）最優解變為X*目標函數值不變。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解：設xj表示第j年生產出來分配用于作戰的戰斗機數；yj為第j年已出來的駕駛員；（ajxj）為第j年用于駕駛員的戰斗機數；zj為第j年用于駕駛員的戰斗機總數。則模型為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 提示：設出每個管道上的實際流量則發點發出的流量等于收點收到的流量中間點則流入等于流出再考慮容量限制條件即可。目標函數為發出流量最大。設xij從點i到點j的流量max zx12x13st. x12x23x24x25x13x23x34x35x24x34x54x46x25x35x54x56 以上為流量平衡條件x12x13x46x56 始點收點x1210x136x234x245x253x345x358x4611x543x567xij0對所有ij1.9 提示：設每個區段上班的人數分別為x1x2x6即可1.10 解：設男生中挖坑、栽樹、澆水的人數分別為x

40、11 、x12 、x13女生中挖坑、栽樹、澆水的人數分別為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 解：設各生產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 解：設712月各月初進貨數量為xi件而各月售貨數量為yi件i126S為總收入則問題的模型為：max S29y124y226y328y422y525y6（28x124x225x327x423x523x6）st. y1200x1500y2200x1y1x2500y3200x1y1x2y2x3500y4200x1y1x2y2x3y3x4500y5200x1y1x2y2x3y3x4y4x5500y2200x1y1x2y2x3y3x4y4x5y5x6500xi0yi0 i126 整數1.13解：用x1x2x3分別代表大豆、玉米、麥子的種植面積（hm2公頃）；x4x5分別代表奶牛和雞的飼養數；x6

42、x7分別代表秋冬和春夏季多余的勞動力（人日）則有第二 章 對偶理論和靈敏度分析2.1 對偶問題為(1) (2) (3) (4) 2.2（1）因為對偶變量Y=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) 由互補松弛性 （ 分別為松弛變量和最優解）可得 從而可知又由對偶性質的最優性 可得四方程聯立即可求得對偶問題的最優解：Y*（2210）2.4 解： 其對偶問題為min w=8y1+1