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

目 錄目 錄第一章 線性規(guī)劃基礎(chǔ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 習(xí) 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 第二章 深入線性規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 習(xí) 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8第三章 線性規(guī)劃的對偶理論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 習(xí) 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 第四章 整數(shù)規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 習(xí) 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23第五章 運(yùn)輸問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 習(xí) 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 第七章 圖論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 習(xí) 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56第八章 動態(tài)規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 習(xí) 題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63I第一章 線性規(guī)劃基礎(chǔ)第一章 線性規(guī)劃基礎(chǔ)習(xí)題一、應(yīng)用問題的建模1、某養(yǎng)雞場飼養(yǎng)肉雞出售，設(shè)每只雞每天至少需100克蛋白質(zhì)、12克礦物質(zhì)、60毫克維生素?，F(xiàn)有五種飼料可供選用，各種飼料每千克營養(yǎng)成分含量及單價(jià)如表1-10所示：表 1-10 飼料成分和成本表飼料蛋白質(zhì)（克）礦物質(zhì)（克）維生素（毫克）價(jià)格（元/千克）13160.5220.3100.8320.480.6452715160.831.5問：如何在滿足肉雞營養(yǎng)需求的前提下，最經(jīng)濟(jì)地搭配飼料？建立本問題的建立線性規(guī)劃模型。答案：解：定義第種飼料的購買量為( = 1, , 5)，則本問題的線性規(guī)劃模型為：min= 0.5 1 + 0.8 2 + 0.6 3 + 4 + 1.5 5s.t.3 1 + 2 2 + 2 3 + 5 4 + 16 5>100必須為>，下同。1 + 0.3 2 + 0.4 3 + 2 4 + 0.8 5>126 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)的工時(shí)和售價(jià)表單位產(chǎn)品工時(shí)產(chǎn)品 1產(chǎn)品 2可用工時(shí)核心部件A普通部件B核心部件C普通部件D生產(chǎn)線10.030.020.050.0140生產(chǎn)線20.040.020.050.0245單位售價(jià)250150400100配合產(chǎn)品的售后服務(wù)政策，每生產(chǎn)1件產(chǎn)品 1和 2需額外生產(chǎn)2件普通部件作為備件單獨(dú)銷售。問：該工廠應(yīng)如何安排生產(chǎn)可實(shí)現(xiàn)月銷售額最大？建立本問題的線性規(guī)劃模型。答案：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)線11111生產(chǎn)線22222本問題完整模型為：max= 740( 1 + 2 ) + 750( 1 + 2 )s.t.3( 1 + 2 ) ( 1 + 2 ) = 03( 1 + 2 ) ( 1 + 2 ) = 00.03 1 + 0.02 1 + 0.05 1 + 0.01 1 6 400.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ū)的需求情況，問如何安排供貨，從而使得公司的總運(yùn)輸成本最低？表1-12給出了這兩個(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)地工廠1700750650400工廠2850550450600需求量350250400試建立本問題的線性規(guī)劃模型。答案：解：定義 為工廠向地區(qū)送貨的數(shù)量。則本問題的模型為：min= 700 11 + 750 12 + 650 13+ 850 21 + 550 22 + 450 23s.t.11 + 12 + 13 6 40021 + 22 + 23 6 60011 + 21 = 35011 + 22 = 25013 + 23 = 400> 0,= 1, 2;= 1, 2, 34、某公司提供4種不同型號的彩色涂料產(chǎn)品 1、 2、 3和 4，各型號產(chǎn)品的市場售價(jià)如表1-13所示。這些彩色涂料由3種原料（原色涂料 1、 2和 3）根據(jù)不同的配方物理混合而成以上兩式符號可以為等號，對于供需不平衡的問題，則必須為6也可以為>，以下兩式同必須有變量的非負(fù)約束2第一章 線性規(guī)劃基礎(chǔ)（成品重量為原料重量之和），各原料在成品中的配方比例如表1-13所示，采購售價(jià)如表1-14所示。表 1-13 不同型號成品的配方和銷售價(jià)格成品型號 配方比例要求 銷售價(jià)格（元/公斤）1不少于40%12不多于20%1203不多于5%1不多于10%22不多于30%903不少于50%31不多于10%702不少于60%1不多于30%42不多于40%503不多于40%答案：表 1-14 3種原料的市場售價(jià)原料 1 2 3價(jià)格503040假設(shè)4種產(chǎn)品均供不應(yīng)求，且本月的采購預(yù)算為10 000元，問：該公司本月應(yīng)如何采購并如何生產(chǎn)，可獲得最多利潤？試建立本問題的線性規(guī)劃模型。解：定義 ( = 1, 2, 3, 4; = 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.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, 3, 4;= 1, 2, 35、某公司將產(chǎn)品從三個(gè)工廠( 1、 2和 3 )運(yùn)往四個(gè)城市 ( 6、 7、 8 和 9 ) ，圖1-1給出了各可行路線的單位運(yùn)輸成本（單位：千元/公斤），其中 4和 5為分銷中心，圖兩側(cè)的數(shù)字表示第種原料的市場價(jià)格必須有變量的非負(fù)約束3第一章 線性規(guī)劃基礎(chǔ)分別表示各工廠的供應(yīng)量和各個(gè)城市的需求量（單位：公斤）。3.5A6200250A1223A45A7150366300A2444A53A83506450A335A9300圖 1-1 物流網(wǎng)絡(luò)數(shù)據(jù)圖問：如何安排運(yùn)輸可使總運(yùn)費(fèi)最少？試建立本問題的線性規(guī)劃模型。答案：解： 定義從 到 的運(yùn)輸量為 ，其中 到 有運(yùn)輸路線， = 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 59s.t.16 + 14+ 15 = 25024+ 25 = 30034+ 35 = 45014 + 24 + 34 = 46 + 47 + 48 + 4915 + 25 + 35 = 56 + 57 + 58 + 59以上兩個(gè)約束條件容46+ 56= 200易漏掉47+ 57= 15048+ 58= 35049+ 59= 300> 0, = 1, , 5, = 1, , 96、SH地產(chǎn)集團(tuán)有閑置資金20億元，擬在未來5年進(jìn)行對外投資。為了保證資金安全，財(cái)務(wù)部門提出了以下4個(gè)可選的投資方向：投資方向1：企業(yè)借貸投資每年年初可投資，當(dāng)年年末收回本利107%；投資方向2：國內(nèi)基金投資每年年初可投資，次年年末收回本利118%；投資方向3：土地買賣每年年初可投資，回收周期為3年，回收本利130%；投資方向4：股權(quán)投資只能在第3年年初投資，最大投資不能超過10億元，第5年年末收回本利155%。假定不存在投資風(fēng)險(xiǎn)且忽略利率波動因素，問：該集團(tuán)應(yīng)如何安排投資計(jì)劃，使得第5年年末時(shí)擁有的本利總額最大？建立本問題的線性規(guī)劃模型。答案：定義 ( = 1, , 5; = 1, , 4)為第年年初用于第個(gè)投資方向的投資額。根據(jù)問題描述，可以得到每年年初的投資額，以及年底的收益如下表所示：4第一章 線性規(guī)劃基礎(chǔ)答案表 1-2年份年初投資總額年末收回本利總額111 + 12+ 131.07 11221+ 22+ 231.07 21 + 1.18 12331+ 32+ 33 + 341.07 31+ 1.18 22+ 1.30 13441+ 42+ 431.07 41+ 1.18 32+ 1.30 23551+ 52+ 531.07 51+ 1.18 42+ 1.30 33 + 1.55 34本問題的線性規(guī)劃模型為：max= 1.07 51 + 1.18 42 + 1.30 33 + 1.55 34s.t.11 + 12+ 13 620符號可以為等號，下21 + 22+ 23 6 1.07 11同31 + 32+ 33+ 34 6 1.07 21+ 1.18 1241+ 42+ 43 6 1.07 31+ 1.18 22 + 1.30 1351+ 52+ 53 6 1.07 41+ 1.18 32 + 1.30 2334 6 10> 0( = 1, , 5; = 1, , 4)必須有變量的非負(fù)約束7、某手工作坊生產(chǎn)的竹制座椅中需要用到3種規(guī)格楠竹片，每張椅子需要長度為60cm、40cm和 30cm 的楠竹片 2、 6和2 片。可以在市場上采購這些規(guī)格的現(xiàn)貨，也可以將作坊倉庫中長度為110cm的楠竹片切割成所需的規(guī)格，但每切割1次會發(fā)生1cm的長度損耗。問：如果要制作100張竹制座椅，該作坊的倉庫中至少要有多少條長度為110cm的楠竹片，才不用去市場上采購？試建立本問題的線性規(guī)劃模型。答案：解：將110cm長的竹片切割為60cm、40cm和30cm共有5種方式，見下表：答案表 1-3 5種切割方式得到片數(shù) 規(guī)格60cm40cm30cm切割方式11102101301240205003定義為采取第種方式切割的110cm楠竹片的數(shù)量，則本問題的線性規(guī)劃模型為：min=1 + 2 + 3 + 4 + 5s.t. 1+ 2>200符號必須為>1+ 3 + 2 4> 6002+ 2 3+ 3 5 > 200> 0,= 1, , 5必須有變量的非負(fù)約束5第一章 線性規(guī)劃基礎(chǔ)8、JM公司是一家基于互聯(lián)網(wǎng)的化妝品銷售公司，該公司每個(gè)月需租用倉庫存放貨物。已知其未來4個(gè)月的倉儲面積需求如表1-15所示，租金按單位面積的租用時(shí)間計(jì)算，租金價(jià)格見表1-16。表 1-15 倉儲面積需求月份 面積（單位：平方米）1 40,0002 30,0003 20,000450,000表 1-16 不同租期的倉庫租金租用時(shí)長（月） 每平方米月租金（元）160210031354170現(xiàn)JM公司需要與出租方簽訂未來4個(gè)月的租用合同，該合同可細(xì)化到各月不同租期租用不同倉儲面積，例如：在2月份，租10,000平方米租期1個(gè)月，20,000平方米的3個(gè)月。問：JM公司應(yīng)如何制訂租用計(jì)劃，可使租金支出最少？建立本問題的線性規(guī)劃模型 (提示：設(shè) 為第個(gè)月初租用租期為個(gè)月的倉儲面積( = 1, , 4; = 1, , 4)。)答案：定義為第個(gè)月初租用租期為個(gè)月的倉儲面積( = 1, , 4; = 1, , 4).每個(gè)月實(shí)際可用倉儲面積如下表所示：答案表 1-4月份111213142122232431323334414243441234表示倉儲面積當(dāng)月可用本問題的模型為：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 44s.t.11 + 12 + 13+ 14> 40000符號必須為 ，下同>12+ 13 + 14 + 21 + 22 + 23+ 24 > 3000013 + 14 + 22+ 23 + 24 + 31 + 32 + 33+ 34> 2000014 + 23 + 24 + 32+ 33 + 34 + 41 + 42 + 43+ 44> 50000> 0( = 1, , 4; = 1, , 4)二、線性規(guī)劃問題的圖解法計(jì)算9、應(yīng)用圖解法求解下列線性規(guī)劃問題：6第一章 線性規(guī)劃基礎(chǔ)(1)max= 2 1 + 2(2)max= 1 3 2s.t.1 + 2 6 4s.t.1 2 > 1 1 + 2 > 51 + 2 2 6 41, 2 > 01, 2 > 0答案：答案：最優(yōu)解為(4, 0)，最優(yōu)值為4。圖略。無可行域，所以問題無可行解。圖略。(3)max= 2 1 + 2(4)min= 2 1 4 2s.t.2 6 10s.t. 1 + 2 2 6 152 1 + 5 2 6 301 + 2 6 121 + 2 6 205 1 + 3 2 6 453 1 + 2 6 361, 2 > 01, 2 > 0答案：答案：最優(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ī)劃問題變換為標(biāo)準(zhǔn)形式。答案：(1) min= 3 1 + 4 2 2 3 + 5 4s.t. 4 12+2 34= 2max= 3 1 4 2 2 3 5 4 + 5 4+3614s.t.4 1+2+ 2 3+ 4 4= 212341 + 2 3 3 4 + 4 + 5= 142 1 + 3 2 3 + 2 4 > 22 1 + 3 2 + 3+ 2 4 2 4 6 = 21, 2 > 0, 3 6 0, 4無限制1, 2, 3, 4, 4, 5, 6 > 0答案：(2) max= 2 1 + 3 2s.t.1+ 26 3max= 2 1+ 3 2 3 22 1 2> 2s.t.1+ 2 2 + 3= 31 > 0, 2無限制2 1 2+ 2 4 = 21, 2, 2, 3, 4 > 02、請窮舉出下列線性規(guī)劃問題的所有基本解，指出其中的基本可行解和最優(yōu)解。(1) max= 1 + 2s.t. 2 1 + 3 2 6 6 2 1 + 2 6 41, 2 > 0答案：引入松弛變量 3, 4將模型變換為標(biāo)準(zhǔn)形式：max= 1 + 2s.t.2 1 + 3 2 + 3= 62 1 + 2+ 4 = 41, 2, 3, 4 > 0約束條件數(shù)量為2，所以基本解中基變量個(gè)數(shù)為2。答案表 2-1序基變量組合基本解可行解目標(biāo)函數(shù)值( 1, 2)最優(yōu)解13是53是( 1, 2)(, 1, 0, 0)(, 1)2222( 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)8第二章 深入線性規(guī)劃(2) min= 3 1 2 + 2 3 4 4 s.t. 2 1 + 3 2 + 3 + 2 4 = 121 + 2 3 + 2 4 = 81, 2, 3, 4 > 0答案：將模型標(biāo)準(zhǔn)化為：max= 3 1 + 2 2 3 + 4 4s.t.2 1 + 3 2 + 3 + 2 4 = 121 +2 3 + 2 4 = 81, 2, 3, 4 > 0約束條件數(shù)量為2，所以基本解中基變量個(gè)數(shù)為2。答案表 2-2序基變量組合基本解可行解目標(biāo)函數(shù)值( 1, 2, 3, 4)最優(yōu)解這里要么寫成 ，1( 1, 2)(12, 4, 0, 0)否要么寫成 ，不能寫2204否成( 1, 3)(, 0, , 0)333( 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)是注：由于還不涉及單純形法求解，本題的目標(biāo)函數(shù)也可以不用化為max ，而是直接計(jì)算。3、應(yīng)用單純形表法求解下列線性規(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 601, 2, 3 > 0答案：答案表 2-3152000bCBXB12345652010110163371123001312124111001513121240005231=83121249第二章 深入線性規(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 3s.t.1 + 26 12 1 + 2 + 3 3 6 143 1 + 2 +3 6 161, 2, 3 > 0答案：標(biāo)準(zhǔn)化后用單純形表求解結(jié)果如下：答案表 2-4331000bCBXB1234565134332010488413001111324421135311004884000511=3712442本問題有唯一最優(yōu)解：X * = ( 1*, 2*, 3*, 4*, 5*, 6*)5433, 0, 0, 0) , *= 371= (,.4422(3) max= 4 1 + 5 2 + 4 3s.t.1 + 2 + 3 6 81 + 3 2 + 3 6 213 1 + 2 2 + 3 6 151, 2, 3 > 0答案：下表為目標(biāo)函數(shù)轉(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-5454000bCBXB123456711543001442452010110132221111411004424000710=381有0檢驗(yàn)數(shù)22210第二章 深入線性規(guī)劃本問題有無窮多最優(yōu)解，其中一個(gè)最優(yōu)解為：必須明確X* = ( *, *, *, *, *, *)= (1,13,5, 0, 0, 0) , *= 381.1234564242(4) min= 1 + 2 2 + 3s.t. 1 + 2>121 3 641, 2, 3 > 0答案：在第1、2個(gè)約束條件中分別引入剩余變量 4和松弛變量 5：min= 1 + 2 2 + 3s.t.1 + 2 4= 121 3+ 5 = 41, 2, 3, 4, 5 > 0可直接以 2, 5為基變量建立初始單純形表直接求解。答案表 2-612100bCBXB123452211010120510101410120=24220111 181110101400021=20本問題有無窮多最優(yōu)解，其中一個(gè)最優(yōu)解為：X * = ( *1, *2, *3, *4, *5) = (4, 8, 0, 0, 0) ,* = 20.4、分別應(yīng)用大M法和兩階段法求解下列線性規(guī)劃問題。(1) max= 1 + 2 2 + 3 3s.t. 2 1 + 3 2 + 5 3 > 10 2 1 + 5 2 + 7 3 = 151, 2, 3 > 0注：下表為最小值直接求解的單純形表，如以最大值為目標(biāo)函數(shù)，檢驗(yàn)數(shù)取相反數(shù) 有0檢驗(yàn)數(shù) 必須明確答案：大M法： 標(biāo)準(zhǔn)化后在第1、2個(gè)約束條件中分別引入人工變量 5和 6，將問題的目標(biāo)函數(shù)改寫為max = 1 + 2 2 + 3 3 5 6注意人工問題是否寫單純形表求解結(jié)果如下：對，特別是 的符號11第二章 深入線性規(guī)劃答案表 2-71230bCBXB123456111570011522220402211150 110 1=152222本問題有唯一最優(yōu)解：X* = ( *, *, *, *, *, *)= (15, 0, 0, 5, 0, 0) , * =15.12345622兩階段法： 第一階段：構(gòu)造輔助問題min = 5 + 6，單純形表求解結(jié)果如下：注意輔助問題是否寫答案表 2-8對，特別是目標(biāo)函數(shù)應(yīng)求min而不是max000011bCBXB123456032510011577770444011557777000011=0最優(yōu)表中= 0，亦即人工變量全部為0（非基變量），可進(jìn)入第二階段。第二階段：去掉第一階段最優(yōu)表中的人工變量，將原始問題的目標(biāo)函數(shù)系數(shù)代回，單純形表求解結(jié)果如下：注意2：求解過程中答案表 2-9右端常數(shù)不得出現(xiàn)負(fù)數(shù)1230bCBXB1234