《華南理工大學 工商管理學院 運籌學 課后習題及答案》由會員分享，可在線閱讀，更多相關《華南理工大學 工商管理學院 運籌學 課后習題及答案（133頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、目 錄 目 錄 第一章 線性規(guī)劃基礎 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 習 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 第二章 深入線性規(guī)劃 . . . . . . . . . .

2、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 習 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 第三章 線性規(guī)劃的對偶理論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3、 . . . . 19 習 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 第四章 整數(shù)規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 習 題 . . . . . . . . . . . . . . . .

4、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 第五章 運輸問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 習 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 第七章 圖論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 習 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6、 . . . . . . . . . 56 第八章 動態(tài)規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 習 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

7、 I 第一章 線性規(guī)劃基礎 第一章 線性規(guī)劃基礎 習題 一、應用問題的建模 1、某養(yǎng)雞場飼養(yǎng)肉雞出售，設每只雞每天至少需100克蛋白質、12克礦物質、60毫克維生素。 現(xiàn)有五種飼料可供選用，各種飼料每千克營養(yǎng)成分含量及單價如表1-10所示： 表 1-10 飼料成分和成本表 飼料 蛋白質（克） 礦物質（克） 維生素（毫克） 價格（元/千克） 1 3 1 6 0.5 2 2 0.3

8、 10 0.8 3 2 0.4 8 0.6 4 5 2 7 1 5 16 0.8 3 1.5 問：如何在滿足肉雞營養(yǎng)需求的前提下，最經(jīng)濟地搭配飼料？建立本問題的建立線性規(guī)劃模型。 答案： 解：定義第種飼料的購買量為 ( = 1, , 5)，則本問題的線性規(guī)劃模型為： min = 0.5 1 + 0.8 2 + 0.6 3 + 4 + 1.5 5 s.t. 3 1 + 2 2 + 2 3 + 5 4 + 16 5> 100 必須為>，下同。 1 + 0.3 2 + 0

9、.4 3 + 2 4 + 0.8 5>12 6 1 + 10 2 + 8 3 + 7 4 + 3 5>60 > 0( = 1, , 5) 必須有變量的非負約 束 2、某工廠利用兩條生產線 1和 2生產兩種產品 1和 2。這兩種產品分別由其核心部件和普通易耗品部件組裝而成，其銷售價格為部件價格之和的110%（單位：元）。表1-11給出了各生產線生產各部件所需單位工時，以及各生產線的每月可使用的總工時（單位：小時）。 表 1-11 單位產品生產的

10、工時和售價表 單位產品工時 產品 1 產品 2 可用工時 核心部件A 普通部件B 核心部件C 普通部件D 生產線1 0.03 0.02 0.05 0.01 40 生產線2 0.04 0.02 0.05 0.02 45 單位售價 250 150 400 100 配合產品的售后服務政策，每生產1件產品 1和 2需額外生產2件普通部件作為備件單獨銷 售。 問：該工廠應如何安排生產可實現(xiàn)月銷售額最大？建立本問題的線性規(guī)劃

11、模型。 答案： 1 第一章 線性規(guī)劃基礎 解：根據(jù)下表定義由各生產線所生產各種部件的數(shù)量： 答案表 1-1 變量定義 產量 產品 1 產品 2 核心部件A 普通部件B 核心部件C 普通部件D 生產線1 1 1 1 1 生產線2 2 2 2 2 本問題完整模型為： max = 740( 1 + 2 ) + 750( 1 + 2 ) s.t. 3( 1 + 2 ) ? ( 1 + 2 ) = 0

12、 3( 1 + 2 ) ? ( 1 + 2 ) = 0 0.03 1 + 0.02 1 + 0.05 1 + 0.01 1 6 40 0.04 2 + 0.02 2 + 0.05 2 + 0.02 2 6 45 > 0, = 1, 2; = , , , 必須有變量的非負約 束 3、某公司在兩個工廠生產產品滿足顧客需求?，F(xiàn)已知下個月三個地區(qū)的需求情況，問如何安排供貨，從而使得公司的總運輸成本最低？表1-12給出了

13、這兩個工廠的生產能力，以及工廠到三個地區(qū)送貨的單位物流成本（單位：元/件）。 表 1-12 運費表 單位運費 銷地 地區(qū)1 地區(qū)2 地區(qū)3 生產能力 產地 工廠1 700 750 650 400 工廠2 850 550 450 600 需求量 350 250 400 試建立本問題的線性規(guī)劃模型。 答案： 解：定義 為工廠向地區(qū)送貨的數(shù)量。則本問題的模型為： min =

14、700 11 + 750 12 + 650 13 + 850 21 + 550 22 + 450 23 s.t. 11 + 12 + 13 6 400 21 + 22 + 23 6 600 11 + 21 = 350 11 + 22 = 250 13 + 23 = 400 > 0, = 1, 2; = 1, 2, 3 4、某公司提供4種不同型號的彩色涂料產品 1、 2、 3和 4，各型號產品的市場售價如表1-13所示。這些彩色涂料由3種原料（原色涂料 1、 2和 3）根據(jù)不同的配方物理混合而成 

15、 以上兩式符號可以為等號，對于供需不平衡的問題，則必須為6 也可以為>，以下兩式同 必須有變量的非負約束 2 第一章 線性規(guī)劃基礎 （成品重量為原料重量之和），各原料在成品中的配方比例如表1-13所示，采購售價如表1-14所示。 表 1-13 不同型號成品的配方和銷售價格成品型號 配方比例要求 銷售價格（元/公斤） 1不少于40% 1 2不多于20% 120 3不多于5% 1不多于10%

16、 2 2不多于30% 90 3不少于50% 3 1不多于10% 70 2不少于60% 1不多于30% 4 2不多于40% 50 3不多于40% 答案：  表 1-14 3種原料的市場售價原料 1 2 3 價格 50 30 40 假設4種產品均供不應求，且本月的采購預算為10 000元，問：該公司本月應如何采購并如何生產，可獲得最多利潤？試建立本問題的線性規(guī)劃模型。 解：定義 ( = 1, 2, 3, 4

17、; = 1, 2, 3)為成品 中原料 的數(shù)量。則本問題的線性規(guī)劃模型為： max = 120( 11 + 12 + 13) + 90( 21 + 22 + 23) + 70( 31 + 32 + 33) + 50( 41 + 42 + 43) ? 50( 11 + 21 + 31 + 41) ? 30( 12 + 22 + 32 + 42) ? 40( 13 + 23 + 33 + 43) s.t. 11 > 0.4( 11 + 12 + 13) 12 6 0.2( 11 + 12 + 13) 13 6 0

18、.05( 11 + 12 + 13) 21 6 0.1( 21 + 22 + 23) 22 6 0.3( 21 + 22 + 23) 23 > 0.5( 21 + 22 + 23) 31 6 0.1( 31 + 32 + 33) 32 > 0.6( 31 + 32 + 33) 41 6 0.3( 41 + 42 + 43) 42 6 0.4( 41 + 42 + 43) 43 6 0.4( 41 + 42 + 43) 4 3 ∑ ∑ 6 10000 =1 =1 > 0, = 1, 2,

19、3, 4; = 1, 2, 3 5、某公司將產品從三個工廠( 1、 2和 3 )運往四個城市 ( 6、 7、 8 和 9 ) ，圖1-1給出了各可行路線的單位運輸成本（單位：千元/公斤），其中 4和 5為分銷中心，圖兩側的數(shù)字  表示第種原料的市場價格 必須有變量的非負約束 3 第一章 線性規(guī)劃基礎 分別表示各工廠的供應量和各個城市的需求量（單位：公斤）。 3.5

20、 A6 200 250 A1 2 2 3 A4 5 A7 150 3 6 6 300 A2 4 4 4 A5 3 A8 350 6 450 A3 3 5

21、 A9 300 圖 1-1 物流網(wǎng)絡數(shù)據(jù)圖 問：如何安排運輸可使總運費最少？試建立本問題的線性規(guī)劃模型。 答案： 解： 定義從 到 的運輸量為 ，其中 到 有運輸路線， = 1, 2, , 5, = 4, 5, , 9。則本問題的本問題的線性規(guī)劃模型為： min = 3.5 16 + 2 14 + 3 15 + 6 24 + 4 25 + 4 34 + 3 35 + 2 46 + 5 47 + 3 48 + 6 49 + 4 56 + 3 57 + 6 58 + 5 59 s.t. 16 + 14

22、 + 15 = 250 24 + 25 = 300 34 + 35 = 450 14 + 24 + 34 = 46 + 47 + 48 + 49 15 + 25 + 35 = 56 + 57 + 58 + 59 以上兩個約束條件容 46 + 56 = 200 易漏掉 47 + 57 = 150 48 + 58 = 350 49 + 59 = 300

23、 > 0, = 1, , 5, = 1, , 9 6、SH地產集團有閑置資金20億元，擬在未來5年進行對外投資。為了保證資金安全，財務部門提出了以下4個可選的投資方向： 投資方向1：企業(yè)借貸投資――每年年初可投資，當年年末收回本利107%；投資方向2：國內基金投資――每年年初可投資，次年年末收回本利118%；投資方向3：土地買賣――每年年初可投資，回收周期為3年，回收本利130%； 投資方向4：股權投資――只能在第3年年初投資，最大投資不能超過10億元，第5年年末收回本利155%。 假

24、定不存在投資風險且忽略利率波動因素，問：該集團應如何安排投資計劃，使得第5年年末時擁有的本利總額最大？建立本問題的線性規(guī)劃模型。 答案： 定義 ( = 1, , 5; = 1, , 4)為第年年初用于第個投資方向的投資額。根據(jù)問題描述，可以得到每年年初的投資額，以及年底的收益如下表所示： 4 第一章 線性規(guī)劃基礎 答案表 1-2 年份 年初投資總額 年末收回本利總額 1 11 + 12 + 13 1.07 11 2 21 + 22 +

25、23 1.07 21 + 1.18 12 3 31 + 32 + 33 + 34 1.07 31 + 1.18 22 + 1.30 13 4 41 + 42 + 43 1.07 41 + 1.18 32 + 1.30 23 5 51 + 52 + 53 1.07 51 + 1.18 42 + 1.30 33 + 1.55 34 本問題的線性規(guī)劃模型為： max = 1.07 51 + 1.18 42 + 1.30 33 + 1.55 34 s.t. 11 + 12 + 13

26、 6 20 符號可以為等號，下 21 + 22 + 23 6 1.07 11 同 31 + 32 + 33 + 34 6 1.07 21 + 1.18 12 41 + 42 + 43 6 1.07 31 + 1.18 22 + 1.30 13 51 + 52 + 53 6 1.07 41 + 1.18 32 + 1.30 23 34 6 10 > 0( = 1, , 5; = 1, ,

27、4) 必須有變量的非負約 束 7、某手工作坊生產的竹制座椅中需要用到3種規(guī)格楠竹片，每張椅子需要長度為60cm、40cm 和 30cm 的楠竹片 2、 6和2 片?？梢栽谑袌錾喜少忂@些規(guī)格的現(xiàn)貨，也可以將作坊倉庫中長度為110cm的楠竹片切割成所需的規(guī)格，但每切割1次會發(fā)生1cm的長度損耗。 問：如果要制作100張竹制座椅，該作坊的倉庫中至少要有多少條長度為110cm的楠竹片，才不用去市場上采購？試建立本問題的線性規(guī)劃模型。 答案：

28、 解：將110cm長的竹片切割為60cm、40cm和30cm共有5種方式，見下表： 答案表 1-3 5種切割方式 得到片數(shù) 規(guī)格 60cm 40cm 30cm 切割方式 1 1 1 0 2 1 0 1 3 0 1 2 4 0 2 0 5 0 0 3 定義 為采取第種方式切割的110cm楠竹片的數(shù)量，則本問題的線性規(guī)劃模型為： min = 1 + 2 + 3 + 4 + 5 s.t. 1 + 2 > 200 符號必須為> 1

29、 + 3 + 2 4 > 600 2 + 2 3 + 3 5 > 200 > 0, = 1, , 5 必須有變量的非負約 束 5 第一章 線性規(guī)劃基礎 8、JM公司是一家基于互聯(lián)網(wǎng)的化妝品銷售公司，該公司每個月需租用倉庫存放貨物。已知其未來4個月的倉儲面積需求如表1-15所示，租金按單位面積的租用時間計算，租金價格見表1-16。 表 1-15 倉儲面積需求月份 面積（單位：平方米）

30、 1 40,000 2 30,000 3 20,000 450,000  表 1-16 不同租期的倉庫租金 租用時長（月） 每平方米月租金（元） 1 60 2 100 3 135 4 170 現(xiàn)JM公司需要與出租方簽訂未來4個月的租用合同，該合同可細化到各月不同租期租用不同倉儲面積，例如：在2月份，租10,000平方米租期1個月，20,000平方米的3個月。 問：JM公司應如何制訂租用計劃，可使租金支出最少？建立本問題的線性規(guī)劃模型 (提示：設 為第個月初租用租期為個月的倉儲面積( = 1, , 4

31、; = 1, , 4)。) 答案： 定義 為第個月初租用租期為個月的倉儲面積( = 1, , 4; = 1, , 4). 每個月實際可用倉儲面積如下表所示： 答案表 1-4 月份 11 12 13 14 21 22 23 24 31 32 33 34 41 42 43 44 1 √ √ √ √

32、 2 √ √ √ √ √ √ √ 3 √ √ √ √ √ √ √ √ √ 4 √ √ √ √ √ √ √ √ √ √ √表示倉儲面積當月可用 本問題的模

33、型為： min = 60 11 + 100 12 + 135 13 + 170 14 + 60 21 + 100 22 + 135 23 + 170 24 + 60 31 + 100 32 + 135 33 + 170 34 + 60 41 + 100 42 + 135 43 + 170 44 s.t. 11 + 12 + 13 + 14 > 40000 符號必須為 ，下同 > 12 + 13 + 14 + 21 + 22 + 23 + 24 > 30000

34、 13 + 14 + 22 + 23 + 24 + 31 + 32 + 33 + 34 > 20000 14 + 23 + 24 + 32 + 33 + 34 + 41 + 42 + 43 + 44 > 50000 > 0( = 1, , 4; = 1, , 4) 二、線性規(guī)劃問題的圖解法計算 9、應用圖解法求解下列線性規(guī)劃問題：

35、 6 第一章 線性規(guī)劃基礎 (1) max = 2 1 + 2 (2) max = 1 ? 3 2 s.t. 1 + 2 6 4 s.t. 1 ? 2 > ?1 ? 1 + 2 > 5 1 + 2 2 6 4 1, 2 > 0 1, 2 > 0 答案： 答案： 最優(yōu)解為(4, 0)，最優(yōu)值為4。圖略。 無可行域，所以問題無可行解。圖略。

36、 (3) max = 2 1 + 2 (4) min = ?2 1 ? 4 2 s.t. 2 6 10 s.t. ? 1 + 2 2 6 15 2 1 + 5 2 6 30 1 + 2 6 12 1 + 2 6 20 5 1 + 3 2 6 45 3 1 + 2 6 36 1, 2 > 0 1, 2 > 0

37、 答案： 答案： 最優(yōu)解為(3, 9)，最優(yōu)值為?42。圖略。 最優(yōu)解為( 15013 , 1813 )，最優(yōu)值為31813 。圖略。 7 第二章 深入線性規(guī)劃 第二章 深入線性規(guī)劃 習題 一、標準單純形法的計算 1、將下列線性規(guī)劃問題變換為標準形式。 答案： (1) min= ?3 1 + 4 2 ? 2 3 + 5 4 s.t.

38、 4 1 ? 2 + 2 3 ? 4 = ?2 max = 3 1 ? 4 2 ? 2 3′ ? 5 4′ + 5 4′′ + + 3 ? 6 14 s.t. ?4 1 + 2 + 2 3′ + 4′ ? 4′′ = 2 1 2 3 4 1 + 2 ? 3 3′ ? 4′ + 4′′ + 5 = 14 ?2 1 + 3 2 ? 3 + 2 4 > 2 ?2 1 + 3 2 + 3′ + 2 4′ ? 2 4′′ ? 6 = 2

39、 1, 2 > 0, 3 6 0, 4無限制 1, 2, 3′, 4′, 4′′, 5, 6 > 0 答案： (2) max= 2 1 + 3 2 s.t.1 + 2 6 3 max = 2 1 + 3 2′ ? 3 2′′ 2 1 ? 2 > 2 s.t. 1 + 2′ ? 2′′ + 3 = 3 1 > 0, 2無限制 2 1 ? 2′ + 2′′ ? 4 = 2 1, 2′, 2′′, 3, 4 > 0 2、請窮舉出下列線性規(guī)劃問題的所有基本解，指出其

40、中的基本可行解和最優(yōu)解。 (1) max= 1 + 2 s.t. 2 1 + 3 2 6 6 2 1 + 2 6 4 1, 2 > 0 答案： 引入松弛變量 3, 4將模型變換為標準形式： max = 1 + 2 s.t. 2 1 + 3 2 + 3 = 6 2 1 + 2 + 4 = 4

41、 1, 2, 3, 4 > 0 約束條件數(shù)量為2，所以基本解中基變量個數(shù)為2。 答案表 2-1 序 基變量組合 基本解 可行解 目標函數(shù)值 ( 1, 2) 最優(yōu)解 1 3 是 5 3 是 ( 1, 2) ( , 1, 0, 0) ( , 1) 2 2 2

42、 2 ( 1, 3) (2, 0, 2, 0) 是 2 (2, 0) 3 ( 1, 4) (3, 0, 0, ?2) 否 ― ― 4 ( 2, 3) (0, 4, ?6, 0) 否 ― ― 5 ( 2, 4) (0, 2, 0, 2) 是 2 (0, 2) 6 ( 3, 4) (0, 0, 6, 4) 是 0 (0, 0)

43、 8 第二章 深入線性規(guī)劃 (2) min= 3 1 ? 2 + 2 3 ? 4 4 s.t. 2 1 + 3 2 + 3 + 2 4 = 12 1 + 2 ? 3 + 2 4 = 8 1, 2, 3, 4 > 0 答案： 將模型標準化為： max = ?3 1 + 2 ? 2 3 + 4 4 s.t. 2 1 + 3 2 + 3 + 2 4 = 12 1 + 2 ? 3 + 2 4 = 8 1, 2, 3, 4 > 0 約束條件

44、數(shù)量為2，所以基本解中基變量個數(shù)為2。 答案表 2-2 序 基變量組合 基本解 可行解 目標函數(shù)值 ( 1, 2, 3, 4) 最優(yōu)解 這里要么寫成? ， 1 ( 1, 2) (12, ?4, 0, 0) 否 ― ― 要么寫成 ，不能寫 2 20 4 否 ― ― 成 ( 1, 3) (

45、 , 0, ? , 0) 3 3 3 ( 1, 4) (4, 0, 0, 2) 是 ?4 (4, 0, 0, 2) 4 ( 2, 3) (0, 5, ?3, 0) 否 ― ― 5 ( 2, 4) (0, 2, 0, 3) 是 14 (0, 2, 0, 3) 6 ( 3, 4) (0, 0, 2, 5) 是 16 (0, 0, 2, 5) 是

46、 注：由于還不涉及單純形法求解，本題的目標函數(shù)也可以不用化為max ，而是直接計算。 3、應用單純形表法求解下列線性規(guī)劃問題。 (1) max= ? 1 + 5 2 + 2 3 s.t. 1 + 2 ? 3 6 16 ? 1 + 2 2 + 3 6 32 2 1 + 3 2 + 2 3 6 60 1, 2, 3 > 0 答案： 答案表 2-3 ?1 5 2 0 0 0 b CB XB 1 2 3 4 5 6 5 2 0 1 0 1

47、 1 0 16 3 3 7 1 1 2 3 0 0 1 ? ? 3 12 12 4 ?1 1 1 0 0 1 ? 5 1 3 12 12 4 0 0

48、 0 ? 5 ? 23 ? 1 =83 12 12 4 9 第二章 深入線性規(guī)劃 本例在一開始求解即出現(xiàn)退化（答案中不需明確），本問題有唯一最優(yōu)解： X * = ( *1, *2, *3, *4, *5, *6) = (3, 16, 3, 0, 0, 0) , * = 83. (2) min= ?3 1 ? 3 2 ? 3 s.t.1 + 2 6 12 ? 1 + 2 + 3 3 6 14 3 1 + 2 + 3 6 16 1,

49、 2, 3 > 0 答案： 標準化后用單純形表求解結果如下： 答案表 2-4 3 3 1 0 0 0 b CB XB 1 2 3 4 5 6 5 1 3 43 3 2 0 1 0 ? 4 8 8 4

50、 1 3 0 0 1 ? 1 1 1 3 2 4 4 2 1 1 3 5 3 1 1 0 0 ? ? 4 8 8 4 0 0 0 ? 5 ? 1 ? 1 =37 1 2 4 4 2 本問題有唯一最

51、優(yōu)解： X * = ( 1*, 2*, 3*, 4*, 5*, 6*) 5 43 3 , 0, 0, 0) , * = ?37 1 = ( , , . 4 4 2 2 (3) max= 4 1 + 5 2 + 4 3 s.t.1 + 2 + 3 6 8 1 + 3 2 + 3 6 21 3 1 + 2 2 + 3 6 15 1, 2, 3 > 0 答案：  下表為目標函數(shù)

52、轉化為max = 3 1 + 3 2 + 3的 單純形表，如直接以min求解，檢驗數(shù)為相反數(shù)。 注意：如果轉換了目 標函數(shù)，在最后應轉 換為 。 標準化后用單純形表求解結果如下： 答案表 2-5 4 5 4 0 0 0 b CB XB 1 2 3 4

53、 5 6 7 1 1 5 4 3 0 0 1 4 ? 4 ? 2 4 5 2 0 1 0 ? 1 1 0 13 2 2 2 1 1 1 1

54、 4 1 1 0 0 ? 4 ? 4 2 4 0 0 0 ? 7 ? 1 0 =38 1 有0檢驗數(shù) 2 2 2 10 第二章 深入線性規(guī)劃 本問題有無窮多最優(yōu)解，其中一個最優(yōu)解為： 必須明確

55、 X * = ( * , * , * , * , * , *) = ( 1 , 13 , 5 , 0, 0, 0) , * = 38 1 . 1 2 3 4 5 6 4 2 4 2 (4) min= 1 + 2

56、 2 + 3 s.t. 1 + 2 > 12 1 ? 3 6 4 1, 2, 3 > 0 答案： 在第1、2個約束條件中分別引入剩余變量 4和松弛變量 5： min = 1 + 2 2 + 3 s.t. 1 + 2 ? 4 = 12 1 ? 3 + 5 = 4 1, 2, 3, 4, 5 > 0 可直接以 2, 5為基變量建立初始單純形表直接求解。 答案表 2-6 1 2 1 0 0 b CB XB 1 2 3 4 5 2

57、 2 1 1 0 ?1 0 12 0 5 [1] 0 ?1 0 1 4→ ?1↑ 0 1 2 0 =24 2 2 0 1 1 ?1 ?1 8 1 1 1 0 ?1 0 1 4 0 0 0 2 1 =20 本問題有無窮多最優(yōu)解，其中一個最優(yōu)解為： X * = ( *1, *2, *3, *4, *5) = (4, 8, 0, 0, 0) , * = 20. 4、分別應用大M法和兩階段法求解下列線性規(guī)劃問題。 (1)

58、max= 1 + 2 2 + 3 3 s.t. 2 1 + 3 2 + 5 3 > 10 2 1 + 5 2 + 7 3 = 15 1, 2, 3 > 0  注：下表為最小值直 接求解的單純形表， 如以最大值為目標函 數(shù)，檢驗數(shù)取相反數(shù) 有0檢驗數(shù) 必須明確 答案： 大M法： 標準化后在第1、2個約束條件中分別引入人工變量 5和 6，將問題的目標函數(shù)改寫為 max = 1 + 2 2 + 3 3 ? 5 ? 6

59、注意人工問題是否寫 單純形表求解結果如下： 對，特別是 的符號 11 第二章 深入線性規(guī)劃 答案表 2-7

60、 1 2 3 0 ?? b CB XB 1 2 3 4 5 6 1 1 1 5 7 0 0 1 15 2 2 2 2

61、 0 4 0 2 2 1 ?1 1 5 0 ? 1 ? 1 0 ?? 1 ? = 15 2 2 2 2 本問題有唯一最優(yōu)解：

62、 X * = ( * , * , * , *, * , *) = ( 15 , 0, 0, 5, 0, 0) , * = 15 . 1 2 3 4 5 6 2 2 兩階段法： 第一階段：構造輔助問題min = 5 +

63、 6 ，單純形表求解結果如下： 注意輔助問題是否寫 答案表 2-8 對，特別是目標函數(shù) 應求min而不是max 0

64、 0 0 0 1 1 b CB XB 1 2 3 45 6 0 3 2 5 1 0 0 1 15

65、 7 7 7 7 0 4 ? 4 4 0 1 ?1 5 5 7 7 7

66、 7 0 0 0 0 1 1 =0 最優(yōu)表中 = 0，亦即人工變量全部為0（非基變量），可進入第二階段。 第二階段：去掉第一階段最優(yōu)表中的人工變量，將原始問題的目標函數(shù)系數(shù)代回，單純形表求解結果如下： 注意2：求解過程中 答案表 2-9 右端常數(shù)不得出現(xiàn)負 數(shù) 1 2 3 0 b CB XB 1 2 3 4