華南理工大學(xué) 工商管理學(xué)院 運(yùn)籌學(xué) 課后習(xí)題及答案

《華南理工大學(xué) 工商管理學(xué)院 運(yùn)籌學(xué) 課后習(xí)題及答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《華南理工大學(xué) 工商管理學(xué)院 運(yùn)籌學(xué) 課后習(xí)題及答案（133頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

4、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 第五章 運(yùn)輸問(wèn)題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 習(xí) 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 第七章 圖論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 習(xí) 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

7、 I 第一章 線性規(guī)劃基礎(chǔ) 第一章 線性規(guī)劃基礎(chǔ) 習(xí)題 一、應(yīng)用問(wèn)題的建模 1、某養(yǎng)雞場(chǎng)飼養(yǎng)肉雞出售，設(shè)每只雞每天至少需100克蛋白質(zhì)、12克礦物質(zhì)、60毫克維生素。 現(xiàn)有五種飼料可供選用，各種飼料每千克營(yíng)養(yǎng)成分含量及單價(jià)如表1-10所示： 表 1-10 飼料成分和成本表 飼料 蛋白質(zhì)（克） 礦物質(zhì)（克） 維生素（毫克） 價(jià)格（元/千克） 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 問(wèn)：如何在滿足肉雞營(yíng)養(yǎng)需求的前提下，最經(jīng)濟(jì)地搭配飼料？建立本問(wèn)題的建立線性規(guī)劃模型。 答案： 解：定義第種飼料的購(gòu)買量為 ( = 1, , 5)，則本問(wèn)題的線性規(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) 必須有變量的非負(fù)約 束 2、某工廠利用兩條生產(chǎn)線 1和 2生產(chǎn)兩種產(chǎn)品 1和 2。這兩種產(chǎn)品分別由其核心部件和普通易耗品部件組裝而成，其銷售價(jià)格為部件價(jià)格之和的110%（單位：元）。表1-11給出了各生產(chǎn)線生產(chǎn)各部件所需單位工時(shí)，以及各生產(chǎn)線的每月可使用的總工時(shí)（單位：小時(shí)）。 表 1-11 單位產(chǎn)品生產(chǎn)的

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

11、模型。 答案： 1 第一章 線性規(guī)劃基礎(chǔ) 解：根據(jù)下表定義由各生產(chǎn)線所生產(chǎn)各種部件的數(shù)量： 答案表 1-1 變量定義 產(chǎn)量 產(chǎn)品 1 產(chǎn)品 2 核心部件A 普通部件B 核心部件C 普通部件D 生產(chǎn)線1 1 1 1 1 生產(chǎn)線2 2 2 2 2 本問(wèn)題完整模型為： 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; = , , , 必須有變量的非負(fù)約 束 3、某公司在兩個(gè)工廠生產(chǎn)產(chǎn)品滿足顧客需求?，F(xiàn)已知下個(gè)月三個(gè)地區(qū)的需求情況，問(wèn)如何安排供貨，從而使得公司的總運(yùn)輸成本最低？表1-12給出了

13、這兩個(gè)工廠的生產(chǎn)能力，以及工廠到三個(gè)地區(qū)送貨的單位物流成本（單位：元/件）。 表 1-12 運(yùn)費(fèi)表 單位運(yùn)費(fèi) 銷地 地區(qū)1 地區(qū)2 地區(qū)3 生產(chǎn)能力 產(chǎn)地 工廠1 700 750 650 400 工廠2 850 550 450 600 需求量 350 250 400 試建立本問(wèn)題的線性規(guī)劃模型。 答案： 解：定義 為工廠向地區(qū)送貨的數(shù)量。則本問(wèn)題的模型為： 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種不同型號(hào)的彩色涂料產(chǎn)品 1、 2、 3和 4，各型號(hào)產(chǎn)品的市場(chǎng)售價(jià)如表1-13所示。這些彩色涂料由3種原料（原色涂料 1、 2和 3）根據(jù)不同的配方物理混合而成 

15、 以上兩式符號(hào)可以為等號(hào)，對(duì)于供需不平衡的問(wèn)題，則必須為6 也可以為>，以下兩式同 必須有變量的非負(fù)約束 2 第一章 線性規(guī)劃基礎(chǔ) （成品重量為原料重量之和），各原料在成品中的配方比例如表1-13所示，采購(gòu)售價(jià)如表1-14所示。 表 1-13 不同型號(hào)成品的配方和銷售價(jià)格成品型號(hào) 配方比例要求 銷售價(jià)格（元/公斤） 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種原料的市場(chǎng)售價(jià)原料 1 2 3 價(jià)格 50 30 40 假設(shè)4種產(chǎn)品均供不應(yīng)求，且本月的采購(gòu)預(yù)算為10 000元，問(wèn)：該公司本月應(yīng)如何采購(gòu)并如何生產(chǎn)，可獲得最多利潤(rùn)？試建立本問(wèn)題的線性規(guī)劃模型。 解：定義 ( = 1, 2, 3, 4

17、; = 1, 2, 3)為成品 中原料 的數(shù)量。則本問(wèn)題的線性規(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、某公司將產(chǎn)品從三個(gè)工廠( 1、 2和 3 )運(yùn)往四個(gè)城市 ( 6、 7、 8 和 9 ) ，圖1-1給出了各可行路線的單位運(yùn)輸成本（單位：千元/公斤），其中 4和 5為分銷中心，圖兩側(cè)的數(shù)字  表示第種原料的市場(chǎng)價(jià)格 必須有變量的非負(fù)約束 3 第一章 線性規(guī)劃基礎(chǔ) 分別表示各工廠的供應(yīng)量和各個(gè)城市的需求量（單位：公斤）。 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)絡(luò)數(shù)據(jù)圖 問(wèn)：如何安排運(yùn)輸可使總運(yùn)費(fèi)最少？試建立本問(wèn)題的線性規(guī)劃模型。 答案： 解： 定義從 到 的運(yùn)輸量為 ，其中 到 有運(yùn)輸路線， = 1, 2, , 5, = 4, 5, , 9。則本問(wèn)題的本問(wèn)題的線性規(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 以上兩個(gè)約束條件容 46 + 56 = 200 易漏掉 47 + 57 = 150 48 + 58 = 350 49 + 59 = 300

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

24、定不存在投資風(fēng)險(xiǎn)且忽略利率波動(dòng)因素，問(wèn)：該集團(tuán)應(yīng)如何安排投資計(jì)劃，使得第5年年末時(shí)擁有的本利總額最大？建立本問(wèn)題的線性規(guī)劃模型。 答案： 定義 ( = 1, , 5; = 1, , 4)為第年年初用于第個(gè)投資方向的投資額。根據(jù)問(wèn)題描述，可以得到每年年初的投資額，以及年底的收益如下表所示： 4 第一章 線性規(guī)劃基礎(chǔ) 答案表 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 本問(wèn)題的線性規(guī)劃模型為： max = 1.07 51 + 1.18 42 + 1.30 33 + 1.55 34 s.t. 11 + 12 + 13

26、 6 20 符號(hào)可以為等號(hào)，下 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) 必須有變量的非負(fù)約 束 7、某手工作坊生產(chǎn)的竹制座椅中需要用到3種規(guī)格楠竹片，每張椅子需要長(zhǎng)度為60cm、40cm 和 30cm 的楠竹片 2、 6和2 片?？梢栽谑袌?chǎng)上采購(gòu)這些規(guī)格的現(xiàn)貨，也可以將作坊倉(cāng)庫(kù)中長(zhǎng)度為110cm的楠竹片切割成所需的規(guī)格，但每切割1次會(huì)發(fā)生1cm的長(zhǎng)度損耗。 問(wèn)：如果要制作100張竹制座椅，該作坊的倉(cāng)庫(kù)中至少要有多少條長(zhǎng)度為110cm的楠竹片，才不用去市場(chǎng)上采購(gòu)？試建立本問(wèn)題的線性規(guī)劃模型。 答案：

28、 解：將110cm長(zhǎng)的竹片切割為60cm、40cm和30cm共有5種方式，見(jiàn)下表： 答案表 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ù)量，則本問(wèn)題的線性規(guī)劃模型為： min = 1 + 2 + 3 + 4 + 5 s.t. 1 + 2 > 200 符號(hào)必須為> 1

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

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

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

32、 2 √ √ √ √ √ √ √ 3 √ √ √ √ √ √ √ √ √ 4 √ √ √ √ √ √ √ √ √ √ √表示倉(cāng)儲(chǔ)面積當(dāng)月可用 本問(wèn)題的模

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 符號(hào)必須為 ，下同 > 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ī)劃問(wèn)題的圖解法計(jì)算 9、應(yīng)用圖解法求解下列線性規(guī)劃問(wèn)題：

35、 6 第一章 線性規(guī)劃基礎(chǔ) (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。圖略。 無(wú)可行域，所以問(wèn)題無(wú)可行解。圖略。

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ī)劃 習(xí)題 一、標(biāo)準(zhǔn)單純形法的計(jì)算 1、將下列線性規(guī)劃問(wèn)題變換為標(biāo)準(zhǔn)形式。 答案： (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無(wú)限制 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無(wú)限制 2 1 ? 2′ + 2′′ ? 4 = 2 1, 2′, 2′′, 3, 4 > 0 2、請(qǐng)窮舉出下列線性規(guī)劃問(wèn)題的所有基本解，指出其

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將模型變換為標(biāo)準(zhǔn)形式： max = 1 + 2 s.t. 2 1 + 3 2 + 3 = 6 2 1 + 2 + 4 = 4

41、 1, 2, 3, 4 > 0 約束條件數(shù)量為2，所以基本解中基變量個(gè)數(shù)為2。 答案表 2-1 序 基變量組合 基本解 可行解 目標(biāo)函數(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 答案： 將模型標(biāo)準(zhǔn)化為： 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，所以基本解中基變量個(gè)數(shù)為2。 答案表 2-2 序 基變量組合 基本解 可行解 目標(biāo)函數(shù)值 ( 1, 2, 3, 4) 最優(yōu)解 這里要么寫(xiě)成? ， 1 ( 1, 2) (12, ?4, 0, 0) 否 ― ― 要么寫(xiě)成 ，不能寫(xiě) 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、 注：由于還不涉及單純形法求解，本題的目標(biāo)函數(shù)也可以不用化為max ，而是直接計(jì)算。 3、應(yīng)用單純形表法求解下列線性規(guī)劃問(wèn)題。 (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ī)劃 本例在一開(kāi)始求解即出現(xiàn)退化（答案中不需明確），本問(wè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 答案： 標(biāo)準(zhǔn)化后用單純形表求解結(jié)果如下： 答案表 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 本問(wèn)題有唯一最

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 答案：  下表為目標(biāo)函數(shù)

52、轉(zhuǎn)化為max = 3 1 + 3 2 + 3的 單純形表，如直接以min求解，檢驗(yàn)數(shù)為相反數(shù)。 注意：如果轉(zhuǎn)換了目 標(biāo)函數(shù)，在最后應(yīng)轉(zhuǎn) 換為 。 標(biāo)準(zhǔn)化后用單純形表求解結(jié)果如下： 答案表 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檢驗(yàn)數(shù) 2 2 2 10 第二章 深入線性規(guī)劃 本問(wèn)題有無(wú)窮多最優(yōu)解，其中一個(gè)最優(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個(gè)約束條件中分別引入剩余變量 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 本問(wèn)題有無(wú)窮多最優(yōu)解，其中一個(gè)最優(yōu)解為： X * = ( *1, *2, *3, *4, *5) = (4, 8, 0, 0, 0) , * = 20. 4、分別應(yīng)用大M法和兩階段法求解下列線性規(guī)劃問(wèn)題。 (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  注：下表為最小值直 接求解的單純形表， 如以最大值為目標(biāo)函 數(shù)，檢驗(yàn)數(shù)取相反數(shù) 有0檢驗(yàn)數(shù) 必須明確 答案： 大M法： 標(biāo)準(zhǔn)化后在第1、2個(gè)約束條件中分別引入人工變量 5和 6，將問(wèn)題的目標(biāo)函數(shù)改寫(xiě)為 max = 1 + 2 2 + 3 3 ? 5 ? 6

59、注意人工問(wèn)題是否寫(xiě) 單純形表求解結(jié)果如下： 對(duì)，特別是 的符號(hào) 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 本問(wèn)題有唯一最優(yōu)解：

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

63、 6 ，單純形表求解結(jié)果如下： 注意輔助問(wèn)題是否寫(xiě) 答案表 2-8 對(duì)，特別是目標(biāo)函數(shù) 應(yīng)求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（非基變量），可進(jìn)入第二階段。 第二階段：去掉第一階段最優(yōu)表中的人工變量，將原始問(wèn)題的目標(biāo)函數(shù)系數(shù)代回，單純形表求解結(jié)果如下： 注意2：求解過(guò)程中 答案表 2-9 右端常數(shù)不得出現(xiàn)負(fù) 數(shù) 1 2 3 0 b CB XB 1 2 3 4