第四章數(shù)學(xué)規(guī)劃方法建模

1、Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 第第4 4章章 數(shù)學(xué)規(guī)劃方法建模數(shù)學(xué)規(guī)劃方法建模njixRxljxhmixgtsxf ,.,2 , 1 0)( ,.,2 , 1 0)( . .)( max數(shù)學(xué)規(guī)劃的一般形式：數(shù)學(xué)規(guī)劃的一般形式： 線性規(guī)劃（Linear Programming，簡稱LP）非線性規(guī)劃（Nonlinear programming，簡稱NLP）整數(shù)規(guī)劃（Integer programming，簡稱IP）Wuhan University Science and technology主頁主頁

2、上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模4.1.1 4.1.1 線性規(guī)劃方法簡介線性規(guī)劃方法簡介0 ,),( . . max(min)xbAxtsxczTWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模4.1.2 4.1.2 線性規(guī)劃方法建模的基本技巧線性規(guī)劃方法建模的基本技巧 簡單上界和下界約束流約束 簡單資源約束 物料平衡約束 質(zhì)量要求約束 Wuhan University Science and technolog

3、y主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模4.1.3 4.1.3 線性規(guī)劃的線性規(guī)劃的LingoLingo實現(xiàn)實現(xiàn) 例1 求解線性規(guī)劃 3 , 2 , 1, 0 5 85 . 05 . 12 205 . 124 48668 . . 203060 max2321321321321ixxxxxxxxxxxtsxxxziWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模model: sets: row/1.4/:b;

4、col/1.3/:c,x; matrix(row,col):A; endsets max=sum(col:c*x); for(row(i):sum(col(j):A(i,j)*x(j)=b(i); data: c=60,30,20;b=48,20,8,5; A=8,6,1 4,2,1.5 2,1.5,0.5 0,2,0; enddata endWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模4.1.4 4.1.4 線性規(guī)劃方法建模示例線性規(guī)劃方法建模示例示例1 棋子問

5、題 有一個木匠作坊制作兩種不同大小的黃楊木棋子小型棋子一套需要車床加工3小時，大型棋子一套需要2小時木匠作坊內(nèi)有4個車床和4名熟練操作員，每人每周工作40小時小型棋子一套需要1千克黃楊木，大型棋子一套需要3千克黃楊木黃楊木每周只能得到200千克如果售出，每套大型棋子能夠得到20元利潤，每套小型棋子能夠得到5元利潤 確定加工兩種棋子的數(shù)量，使得總利潤最大Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模, 0, 2003 16023 205 maxZyxyxyxs.t.y

6、xf問題的最優(yōu)解及最優(yōu)值為： 1330,66, 2maxfyxWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模示例2 連續(xù)投資問題 某部們在今后五年內(nèi)考慮給下列項目投資，并已知： 項目A，從第一年到第四年每年年初需要投資，并于次年末回收本利115%；項目B，第三年初需要投資，到第五年末能回收本利125%，但規(guī)定最大投資額不超過4萬元；項目C，第二年初需要投資，到第五年末能回收本利140%，但規(guī)定最大投資額不超過3萬元；項目D，五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加

7、利息6% 該部們現(xiàn)在有資金10萬元，問它應(yīng)如何確定給這些項目每年的投資額，使得第五年末擁有的資金的本利總額為最大？ Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模5 , 1; 4 , 1 0, 30000 40000 006. 115. 1 006. 115. 1 006. 115. 1 0061 100000 . .06. 125. 140. 115. 1 max32235434432333212221115324jixxxxxxxxxxxxxxxxxxxxxx.

8、-xxtsxxxxzBCjDiACBDDADADADBADADCADDADBCAWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模問題的最優(yōu)結(jié)果為： A第1年投資：A項目34782.61元，D項目65217.39元 第2年投資：A項目39130.43元，C項目30000元，D項目0元 第3年投資：A項目0元，B項目40000元，D項目0元 第4年投資：A項目45000元，D項目0元 第5年投資：D項目0元 第五年末該部們擁有資金總額為143750元，即盈利43.75%

9、Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模示例3 貨機裝運問題 某運貨機有三個機艙：前艙，中艙，后艙三個貨艙所能載的貨物的最大體積和最大重量如表4-1所示為了保證飛機的平衡，三個貨艙中實際裝載貨物的重量必須與其最大容量成比例 現(xiàn)有四類貨物需飛行裝運，有關(guān)運送數(shù)據(jù)見表4-2,試建立數(shù)學(xué)模型，合理安排裝運，使貨機本次飛行獲利最大Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.

10、1 線性規(guī)劃方法建模線性規(guī)劃方法建模 表4-1 三個貨倉裝載貨物的最大容許重量和體積 前倉中倉后倉重量限制（噸）10168體積限制（立方米）680087005300表4-2 四類貨物的裝運數(shù)據(jù) 重量（噸）空間（立方米/噸）利潤（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物4123902850Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模3 , 2 , 1; 4 , 3 , 2 , 1 0 4 , 3 , 2 , 1 3 , 2

11、 , 1 3 , 2 , 1 . . max3413241214113141414131 jixVxVxVxiwxjVvxjWxtsxcZijiiiiiiijijjiiijjiijijijiWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模問題的最優(yōu)結(jié)果為： 第1個貨艙裝第2種貨物10噸； 第2個貨艙裝第3種貨物12.79412噸； 第3個貨艙裝第2種貨物5噸，第3種貨物2.794118噸； 最大獲利為111558.8元 Wuhan University Science

12、 and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模示例4 動物飼料制造問題 某飼料公司要生產(chǎn)兩種類型的動物飼料：粉狀飼料和顆粒飼料生產(chǎn)這些飼料需要的原料為：燕麥，玉米和糖渣生產(chǎn)過程中，首先需要將燕麥和玉米磨碎，然后將所有原料混合形成飼料產(chǎn)品，最后將半成品制成顆粒狀或粉末狀，從而得到最終產(chǎn)品 每種飼料產(chǎn)品都需要滿足規(guī)定的營養(yǎng)需求，見表4-3每天各種原料的可用量也有限制，其限定值及原料的價格見表4-4加工飼料的各道工序的成本見表4-5 如果每天需求量為9噸顆粒飼料，12噸粉狀飼料，則各種原材料應(yīng)分別使用多少，并應(yīng)怎樣混合

13、才能使得總成本最低Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模表4-3 營養(yǎng)成分含量百分比 原料蛋白質(zhì)脂肪纖維素燕麥玉米糖渣13.64.157.12.40.373.725要求含量9.52 6表4-4 原材料可用量與價格原料可用量（千克）價格（元/千克）燕麥玉米糖渣11900235007500.130.170.12表4-5 加工成本（元/千克）磨碎混合結(jié)粒篩粉0.250.050.420.17Wuhan University Science and technolog

14、y主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模 3 , 2 , 1; 21 0 21 3 , 2 , 1 21 . .0.1742. 005. 025. 0 min3121312133121331213121312311312121213121j, ix , ihxjWxxQxq, kxQxqtsxxxxxpfijijijjiijjiijjiijjjiijkjiijkjjjjjjiijjiijjiijjWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.

15、1 線性規(guī)劃方法建模線性規(guī)劃方法建模問題的最優(yōu)結(jié)果為： 生產(chǎn)9噸顆粒狀飼料需要燕麥288.8889千克，玉米8711.1111千克，糖渣0千克；生產(chǎn)12噸粉狀飼料需要燕麥11611.11千克，玉米0千克，糖渣388.8889千克 所需的最低成本為15097.33元Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模示例5 自行車生產(chǎn)規(guī)劃問題 某公司生產(chǎn)自行車，表4-6給出了明年各月預(yù)期的銷售量此公司的月生產(chǎn)能力為3千輛，通過工人加班，可以將產(chǎn)量提高50%，但是會將每輛自行

16、車的生產(chǎn)成本從30元提高到40元 當(dāng)前自行車的庫存量為2千輛，對庫存中的每輛自行車，每個月月底都需支出5元的存儲費用，假定此公司的庫存能力是無限的 現(xiàn)在是1月1日，在下面的12個月里應(yīng)生產(chǎn)和存儲多少輛自行車才能夠滿足此銷售預(yù)期，并使得總成本最少？ Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模表4-6：明年的銷售預(yù)期（千輛） 1月 2月 3月 4月 5月 6月 7月 8月 9月 10月 11月 12月30 15 15 25 33 40 45 45 26 14 25

17、3012, 2 , 1 0,2000 12, 1, 45000 12, 1,30000 . .54030 min01121izyxyiyixazzyxtszyxfiiiiiiiiiiiiiiWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模 問題的最優(yōu)結(jié)果見表4-7生產(chǎn)和庫存的最小總成本為1064500元。 表4-7 自行車生產(chǎn)規(guī)劃最優(yōu)結(jié)果表（千輛） 月份 1月 2月 3月 4月 5月 6月 7月 8月 9月 10月 11月 12月預(yù)期需求 30 15 15 25 33

18、 40 45 45 26 14 25 30正常生產(chǎn) 28 15 15 28 30 30 30 30 26 14 25 30加班生產(chǎn) 0 0 0 0 0 10 15 15 0 0 0 0倉庫存儲 0 0 0 4 0 0 0 0 0 0 0 0Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模示例示例6 6 體育館建設(shè)問題體育館建設(shè)問題 某市政府打算修建一個小型體育館通過競標(biāo)，一家建筑公司獲得了此合同表4-8列出了工程的主要任務(wù)，需時均以星期計有些任務(wù)只有在某些其他任務(wù)完成

19、之后才能進(jìn)行 （1）試給出各項任務(wù)的施工次序，使得這項工程能盡早完成 （2）市政府希望能夠再提前一些時間完工為此，市政府決定工期每縮短一周，便向此公司支付30千元的獎勵為縮短工期，建筑公司每周需要支付額外費用，見表4-8第5列問如何施工才能使得建筑公司的利潤最大Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模表4-8 體育館施工數(shù)據(jù)表任務(wù) 描述 耗時 先決任務(wù) 最大縮短時間 每周額外開支1 工地布置 2 沒有 0 2 場地平整 16 1 3 303 打地基 9 2 1

20、 264 通路及其它道路網(wǎng)絡(luò) 8 2 2 12 5 底層施工 10 3 2 176 主場地施工 6 4，5 1 157 劃分更衣室 2 4 1 8 8 看臺電器布置 2 6 0 9 頂部施工 9 4，6 2 42 10 照明系統(tǒng) 5 4 1 21 11 安裝階梯看臺 3 6 1 1812 封頂 2 9 0 13 更衣室 1 7 0 14 建造售票處 7 2 2 22 15 第二通路 4 4，14 2 12 16 信號設(shè)施 3 8，11，14 1 617 草坪與附屬運動設(shè)施 9 12 3 16 18 交付使用 1 17 0 Wuhan University Science and technol

21、ogy主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模問題（1）的數(shù)學(xué)模型： 1818112223224335446556447668449669441066119912min . . , , fxtstxtxxtxxtxxtxxtx xtxxtxxtxxtx xtxxtxxtxxtx7713221444151414158816111116141416121217171718 , , 0 1,18ixtxxtxxtxxtxxtxxtxxtxxtxxtxxiWuhan University Science and technology主頁主頁 上

22、頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模 問題的最優(yōu)解，即各個任務(wù)的開工周次為:0，2，18，29，27，37，37，44，43，37，43，52，39，30，37，46，54，63，相應(yīng)各個任務(wù)的完工周次為：2，18，27，37，37，43，39，46，52，42，46，54，40，37，41，49，63，64最優(yōu)施工時間安排圖，見圖4.1（其中橫坐標(biāo)為施工周次，縱坐標(biāo)為施工項目），最早完工時間為第64周 圖4.1 問題（1）的最優(yōu)施工時間安排圖 Wuhan University Science and technology主頁主頁 上頁上頁 下

23、頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模18, 1 0, 18, 1 , , , , , , , , , . .)63(30 max181717171712121216141414161111111688815141414154441422213777129991166610444966694448666744465556444533342223222211118118iyxitmyxytxxytxxytxxytxxytxxytxxytxxytxxytxxytxxytxxytxxytxxytxxytxxytxxytxxytxxytxxytxxytxxytxt

24、sycxfiiiiiii問題（2）的數(shù)學(xué)模型： Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模 問題的最優(yōu)解，即各個任務(wù)的開工周次為:0，2，18，18，26，34，26，39，39，26，39，48，28，19，26，42，50，56；相應(yīng)各個任務(wù)的完工周次為：2,18,26,26,34,39,28,41,48,31,42,50,29,26,30,45,56,57；較原先施工方案共計提前了7周；各個任務(wù)實際縮短的周次為：0，0，1，0，2，1，0，0，0，0，0，

25、0，0，0，0，0，3，0最優(yōu)施工時間安排圖，見圖4.2（其中橫坐標(biāo)為施工周次，縱坐標(biāo)為施工項目），建筑公司最多可獲益87千元 圖4.2 問題（2）的最優(yōu)施工時間安排圖 Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模示例7 農(nóng)作物種植問題 某農(nóng)場有625畝的土地可以用來種植農(nóng)作物可以種植的農(nóng)作物有玉米、小麥和高粱預(yù)計有1000畝-尺的灌溉用水可用，農(nóng)場農(nóng)民每周可以投入的時間為300小時這三種農(nóng)作物每畝的收益分別為400元，200元和250元每畝農(nóng)作物所需的資源見表4

26、-9試確定各種農(nóng)作物的種植量，使得農(nóng)場的獲益最大進(jìn)一步討論以下3個問題： （1）若用50元可以買到1畝-尺的灌溉用水，應(yīng)否做此項投資？若投資最多每周購買多少畝-尺的灌溉用水？ （2）若可以購買土地增加種植面積，購買1畝土地的費用最多是多少元？ （3）由于市場需求變化，每畝高粱的獲利增加到300元，應(yīng)否改變生產(chǎn)計劃？ Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模表4-9 農(nóng)場每畝農(nóng)作物所需的資源數(shù)據(jù) 所需資源（每畝） 玉米 小麥 高粱灌溉用水（畝-尺） 3.0 1.

27、0 1.5勞動時間（小時/周） 0.8 0.2 0.3Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模線性規(guī)劃模型： 3 , 2 , 1 0 . . min31i31i31i31ixTxbMxaVxtsxcfiiiiiiiii 問題的最優(yōu)方案為：種植玉米41.6667畝，種植小麥0畝，種植高粱583.3333畝，最大收益為162500元Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1

28、 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模 對Lingo模型進(jìn)行靈敏度分析可得下面報告：（1）土地和灌溉用水這兩種資源全部用完，而勞動時間這種資源還剩余91.6667； （2）土地、灌溉用水和勞動時間的影子價格分別為100元、100元和0元，即增加1個單位的土地量、灌溉用水量和勞動時間，總收益會分別增加100元、100元和0元（3）最優(yōu)解不變條件下目標(biāo)函數(shù)系數(shù)的變化范圍分別為250,400、0,200和250,400，即當(dāng)每畝玉米的收益在250,400，每畝小麥的收益在0,200，每畝高粱的收益在250,400變化時，不需要改變生產(chǎn)計劃（4）土地、灌溉用水和勞動時間這三種資源影子價格有意義條件

29、下約束右端的限制范圍分別為333.3333,666.6667、937.5,1275和208.3333, ，要保證前面給定的影子價格有意義，土地量、灌溉用水量和勞動時間只能在上述范圍內(nèi)取值Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模 根據(jù)上述報告可以回答前面的三個問題：問題（1）應(yīng)該做此項投資，若投資每周最多1275購買畝-尺的灌溉用水；問題（2）可以購買土地，購買1畝土地的費用最多是100元；問題（3）每畝高粱的獲利為300元時，仍小于其變化上限400元，所以不需

30、要改變生產(chǎn)計劃 Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.1 4.1 線性規(guī)劃方法建模線性規(guī)劃方法建模4.1.5 課后練習(xí) 1某公司承諾為某建設(shè)項目從2003年起的4年中每年初分別提供以下數(shù)額貸款：2003年100萬，2004年150萬，2005年120萬，2006年110萬貸款資金需于2002年底前籌集齊為了充分發(fā)揮這筆資金的作用，在滿足每年貸款額情況下，可將多余資金分別用于下列投資項目： （1）于2003年初購買A種債券，期限3年，到期后本息合計為投資額的140，但限購60萬； （2）于2003年初購

31、買B種債券，期限2年，到期后本息合計為投資額的125，且限購90萬； （3）于2004年初購買C種債券，期限2年，到期后本息合計為投資額的130，且限購50萬； （4）于每年初將任意數(shù)額的資金存放于銀行，年息4，于每年底取出問此公司如何運用這筆籌集到的資金滿足貸款要求，并使得2002年底籌集到的資金數(shù)額最少Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模4.2.1 4.2.1 整數(shù)規(guī)劃方法簡介整數(shù)規(guī)劃方法簡介njixRDxljxhmixgtsxf ,.,2 , 1 0

32、)( ,.,2 , 1 0)( . .)( max線性整數(shù)規(guī)劃、純整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、0-1規(guī)劃 Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模需要的一些特殊變量： 0-1變量： 定義變量的取值要么為0，要么為1。部分整數(shù)變量： 定義變量如果其值小于用戶指定的限制L，則其取值必須為整數(shù)值；否則可取任意值。 半連續(xù)變量： 定義變量的取值要么為0，要么位于某限定范圍內(nèi)。半連續(xù)整數(shù)變量： 定義變量的取值要么為0，要么位于某限定范圍內(nèi)的整數(shù)值。 Wuha

33、n University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模4.2.2 4.2.2 整數(shù)規(guī)劃方法建模的基本技巧整數(shù)規(guī)劃方法建模的基本技巧處理是/否邏輯問題 問題只有兩種選擇，要么做某件事，要么不做某件事對此可以借助0-1變量來處理。 處理邏輯條件問題 問題有一組項目，不妨記為A，B，C，D，E，F(xiàn)，G，和H，每個項目都可以選擇做還是不做，可借助0-1變量加以處理。具體問題要求不同，處理的方式也不相同，常見的情況如下： 1.在多個選項中進(jìn)行選擇 Wuhan University Scien

34、ce and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模如“這些項目中至多選一個”： 181iix再如，“選且僅能選擇二個項目”： 281iixWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模2.簡單蘊含式 比如“如果選擇項目A，則必須也選擇項目B”： 21xx 再如“如果選擇項目A，則不能選擇項目B”： 211xx再如“如果不選擇項目A，則必須選擇項目B”： 211xx Wuhan Univ

35、ersity Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模3.含有三個變量的蘊涵式 如“如果選擇項目A，則必須也選擇項目B和項目C”: 3212xxx再如“如果選擇項目A，則必須也選擇項目B或項目C”: 321xxx“如果同時選擇項目B和項目C，則必須選擇項目A”: 2)1 (321xxxWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模4.一般蘊涵式 比如“如果選擇項目B

36、，C,D和E中的兩個或兩個以上，則必須也選擇A”: 1543231xxxxx處理0-1變量乘積問題 對式 ，可用借助下面三個不等式將其線性化 213xxx 1,2132313xxxxxxxWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模 對乘積等式約束 ,可利用下面四個不等式約束將其線性化 3214xxxx 2,3214342414xxxxxxxxxx處理“或”約束問題 比如下面問題: 0, 72 or 62 . . min21212121xxxxxxtsxxZWuh

37、an University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模 定義0-1變量 , 表示采用第1個約束條件，否則采用第2個約束條件 y1y)1 (72622121yxxyxx處理半連續(xù)整數(shù)變量問題 如某自行車廠采用流水線作業(yè)生產(chǎn)某種自行車，對這種自行車，要么不生產(chǎn)，要生產(chǎn)要求至少生產(chǎn)1500輛。 Myxy1500Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模處

38、理固定成本問題 如某手機生產(chǎn)廠打算生產(chǎn)一種新型的手機，如果生產(chǎn)則需要投資固定成本10萬元，如果不生產(chǎn)，則此項成本為0。 0 100 0 xxf 引入0-1輔助變量 ， 表示生產(chǎn)此種手機，否則為0。y 1yyf10Myx Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模處理0-1變量和實數(shù)變量的乘積問題 用整數(shù)規(guī)劃方法建模時，有時會遇到實數(shù)變量和0-1變量相乘的問題如 ，其中 為0-1變量，可用下面不等式將其線性化 yxx12yMyxyMxxxx21212),1 (,處

39、理“或”約束問題 數(shù)學(xué)規(guī)劃中的約束條件一般都是必須同時滿足，但有時對其中的某兩個約束條件只須滿足一個即可，比如 Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模0, 72 or 62 . . min21212121xxxxxxtsxxZ 定義0-1變量 ，令 表示采用第1個約束條件，采用第2個條件，則取值為0 y1y)1 (72622121yxxyxxWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回

40、結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模處理半連續(xù)整數(shù)變量問題 如某自行車廠采用流水線作業(yè)生產(chǎn)某種自行車，對這種自行車，要么不生產(chǎn)，要生產(chǎn)要求至少生產(chǎn)1500輛定義變量 表示生產(chǎn)這種自行車的輛數(shù)，則顯然 為半連續(xù)整數(shù)變量.定義0-1變量 ，則有 xxyMyxy1500處理固定成本問題 如某手機生產(chǎn)廠打算生產(chǎn)一種新型的手機，如果生產(chǎn)則需要投資固定成本10萬元，如果不生產(chǎn)，則此項成本為0記 x表示生產(chǎn)此種新型手機的個數(shù)， f表示投資固定資產(chǎn)的費用， Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.

41、2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模0 100 0 xxf引入0-1輔助變量 1,yy表示生產(chǎn)此種手機，否則為0，則 Myxyf,10處理0-1變量和實數(shù)變量的乘積問題 21,xx 如 為實數(shù)變量，而 為0-1變量，且有 ，則 yyxx12MyxyMxxxx21212),1 (,Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模4.2.3 4.2.3 整數(shù)規(guī)劃方法的整數(shù)規(guī)劃方法的LingoLingo軟件實現(xiàn)軟件實現(xiàn)例例 用Lingo軟件求解整數(shù)規(guī)劃Zxxxxxx

42、tsxxz21212121, 43 1 . . maxWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模解：在Lingo指令窗中輸入下面指令： model:sets:row/1.2/:b;col/1.2/:c,x;matrix(row,col):A;endsetsmax=sum(col:c*x);for(col:gin(x); for(row(i):sum(col(j):A(i,j)*x(j)=b(i);data:c=1,1;b=1,4;A=-1,1,3,1;endda

43、taendWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模4.2.4 4.2.4 整數(shù)規(guī)劃方法建模示例整數(shù)規(guī)劃方法建模示例示例示例1 1 指派問題指派問題 有一份中文說明書，需翻譯成英、日、德、俄四種文字，分別記作E、J、G、R現(xiàn)有甲、乙、丙、丁、戊五人，他們將中文說明書翻譯成不同語種的說明書所需的時間見表4-15請從這五人中指派四人完成這項工作，使得所需的總時間最少Wuhan University Science and technology主頁主頁 上頁上頁 下頁

44、下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模表4-15 各人對每項任務(wù)所需時間表 語種EJGR甲乙丙丁戊210975154148613141611124151397Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模建立指派問題的數(shù)學(xué)模型如下： 4 , 3 , 2 , 1; 5 , 4 , 3 , 2 , 1 1 , 0 4 , 3 , 2 , 1 1 5 , 4 , 3 , 2 , 1 1 . . min51415141j ix jxixt

45、sxtzijiijjijijijij 問題的最優(yōu)解為: ，其余變量為0，最優(yōu)值為24，即甲翻譯俄文，乙翻譯日文，丁翻譯德文，戊翻譯英文所需的總時間最少，為24小時 151432214xxxxWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模示例2 汽車廠生產(chǎn)計劃問題 某汽車廠生產(chǎn)小、中、大三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤以及每月工廠鋼材、勞動時間的現(xiàn)有量如表4-16所示由于條件限制，規(guī)定如果生產(chǎn)某一類型的汽車，則至少要生產(chǎn)80輛，試制定月生產(chǎn)

46、計劃，使工廠的利潤最大表4-16 汽車廠相關(guān)數(shù)據(jù)表小型 中型 大型現(xiàn)有量鋼材（噸）1.5 3 5600勞動時間（小時） 280 250 40060000利潤（萬元） 2 3 4Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模3 , 2 , 1 1 , 0, 0( 3 , 2 , 1 80 . . min313131iyZxiMyxyTxbSxatsxcziiiiiiiiiiiiii 問題的最優(yōu)解為: ,即生產(chǎn)小型汽車80輛，中型汽車150輛，大型汽車0輛，工廠獲得的最

47、大利潤為610萬元 0,150,80321xxxWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模示例3 露天采礦問題 某地發(fā)現(xiàn)了一個露天鈾礦根據(jù)探測鉆探的結(jié)果，發(fā)現(xiàn)這個礦可以分為若干個可開采區(qū)礦坑需要挖掘成階梯形，以方便卡車開到礦坑底部鈾礦呈東西方向分布，如圖4.3所示鈾礦確定有18個可開采區(qū)，呈三層分布為挖掘一個可開采區(qū)，首先需要掘開它上方的三個區(qū)：正上方的區(qū)，左上方的區(qū)和右上方的區(qū) 挖第一層的區(qū)塊每噸需要耗費100元，挖的第二層每噸需要耗費200元，挖第三層每噸需

48、要耗費300元如果區(qū)塊是由含有很多石英的石頭組成（斜線區(qū)域），則每噸需要多耗費1000元只有灰色顯示的區(qū)才含有鈾（即1，7，10，12，17，18區(qū)）其市場價值分別為200，300，500，1000, 1200和1400元/噸第18區(qū)，盡管也含有大量礦石，但也同時含有大量非常硬的石頭為使總收益達(dá)到最大，應(yīng)挖掘哪些礦區(qū)?Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模123456789101112131415161718第1層第2層第3層圖4.3：露天礦山結(jié)構(gòu)圖Wuha

49、n University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模18, 1 1 , 0 3 3 3 3 3 3 3 . .)( max14131218131211178761476513654125431143210181ixxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsxcvfiiiii問題的最優(yōu)解為: 117131211107654321xxxxxxxxxxxx，其余變量為0，最大收益為1400即挖掘礦區(qū)1，2，3，4，5，6，7，10，11，12，13，17可使得總收益達(dá)

50、到最大Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模示例4 蔗糖生產(chǎn)問題 在澳大利亞，甘蔗的收割已經(jīng)實現(xiàn)了高度機械化甘蔗在砍下之后將馬上通過運行于小型鐵路網(wǎng)上的貨車運送到蔗糖廠一輛貨車的運量能夠生產(chǎn)的蔗糖量取決于甘蔗收購的地點以及甘蔗成熟的程度在收割之后，甘蔗中的含糖量由于發(fā)酵而迅速下降，一段時間之后，所含糖份將完全流失現(xiàn)在有11輛貨車到達(dá)了蔗糖廠，每輛貨車運載的甘蔗量都相同對每輛貨車每小時的損失量以及剩余時間測量的數(shù)據(jù)見表4-17： 表4-17：每車甘蔗屬性貨車編

51、號 1 2 3 4 5 6 7 8 9 10 11損失率（千克/小時）43 26 37 28 13 54 62 49 19 28 30剩余時間 8 8 2 8 4 8 8 8 8 8 8 Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模 在蔗糖廠有三條生產(chǎn)線，每輛貨車都可以選擇在哪條生產(chǎn)線上進(jìn)行加工一車甘蔗的加工時間為兩個小時必須在這車甘蔗的質(zhì)量壽命結(jié)束之前完成加工蔗糖廠的經(jīng)理希望找出一個生產(chǎn)計劃，使總的蔗糖損失降到最低4 , 3 , 2 , 1;11, 1 1 ,

52、0 11, 1 2 4 , 3 , 2 , 1 3 11, 1 1 . .2 min411114111141 tixisxttxixtsxtlfitititiittitititiWuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模 問題的最優(yōu)解為: ,其余變量1,3 ,113 ,10948271615243312412xxxxxxxxxxx為0，各個貨車蔗糖的損失量(單位：千克)分別為：172，208，74，168，52，108，124，196，152，168，180，蔗

53、糖的最小總損失量為1602（千克）于是得問題的最優(yōu)加工方案見表4-18 表4-18 最優(yōu)加工方案表 時間段1 時間段2 時間段3 時間段4貨車3 貨車1 貨車4 貨車2貨車6 貨車5 貨車10 貨車9貨車7 貨車8 貨車11 Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模示例5 文件備份問題 某公司希望將一些重要的文件備份到軟盤上每張空白軟盤的容量是1.44MB一共需要備份16個文件，其大小(單位：KB)分別為：46，55，62，87，108，114，137，164

54、，253,364,372,388,406,432,461和851 假定無法使用壓縮文件，但軟盤的數(shù)量足夠，問如何備份這些文件才能使得使用的軟盤數(shù)目最少？ Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模;16, 1, 1 , 0 16, 1 16, 1 102444. 1 16, 1 1 . . min161161161jixixjNjxsixtsNijjijiijijij文件備份問題的數(shù)學(xué)模型： 問題的最優(yōu)分配方案: 軟盤 文件大小（KB） 使用空間（MB）1 46

55、, 62,87,137, 364, 372,388 1.42192 108,406,432,461 1.37403 55,114, 164, 253,851 1.4003Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模示例6 鋼管切割問題 某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的要求切割后售出，從鋼管廠進(jìn)貨時得到的原料鋼管都是19m （1）現(xiàn)有一客戶需要50根4m，20根6m和15根8m的鋼管，應(yīng)如何下料最節(jié)??？ （2）零售商如果采用不同切割模式太多，將會導(dǎo)致生產(chǎn)過

56、程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用不同的切割模式不能超過3種此外，該客戶除需要（1）中的三種鋼管外，還需要10根5m的鋼管，應(yīng)如何下料最省？Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模表4-20 鋼管的合理切割模式表模式1模式2模式3模式4模式5模式6模式74m鋼管根數(shù)43211006m鋼管根數(shù)01021308m鋼管根數(shù)0010102, 0 3 , 2 , 1 . . min7171ZxjlxctsxZijiijiii問題（1）的數(shù)學(xué)模型：

57、Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模 結(jié)果： 按照模式1切割5根原料鋼管，按照模式2切割5根原料鋼管，按照模式5切割15根原料鋼管，最少需要切割25根原料鋼管 問題（2）的數(shù)學(xué)模型： 4 , 3 , 2 , 1; 3 , 2 , 1 , 0, 3 , 2 , 1 1915 4 , 3 , 2 , 1 . . min413131jiZyxisyjlxytsxZijijjijjiiijiiWuhan University Science and technol

58、ogy主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模 運行得切割所需的模式分別為：模式1，將原料鋼管切割成4m鋼管3根，5m鋼管0根，6m鋼管1根，8m鋼管0根；模式2，將原料鋼管切割成4m鋼管0根，5m鋼管0根，6m鋼管0根，8m鋼管2根；模式3，將原料鋼管切割成4m鋼管2根，5m鋼管1根，6m鋼管1根，8m鋼管0根最少需要切割19m的原料鋼管28根模型結(jié)果：Wuhan University Science and technology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模示例7

59、倉庫位置設(shè)置 某公司希望開設(shè)一些新倉庫，向銷售中心供貨每開設(shè)一個新倉庫都有一些固定費用貨物將從倉庫運輸?shù)礁浇匿N售中心，每次運輸?shù)倪\費取決于運輸?shù)木嚯x 目前有12個位置可以建造新倉庫，這些倉庫可以向12個銷售中心供貨表4-21給出了每個倉庫完全滿足每個客戶（銷售中心）需求所需的總成本（單位：元），如果無法進(jìn)行送貨，取對應(yīng)的成本為100000 此外，每個倉庫的固定建設(shè)費用和倉庫的容量上限見表4-22倉庫在任何時候都要保證滿足客戶需求，每個客戶的需求量見表4-23 問此公司應(yīng)在哪些位置開辦倉庫才能使得建設(shè)成本和運輸成本的總費用最低？Wuhan University Science and tech

60、nology主頁主頁 上頁上頁 下頁下頁 返回返回 結(jié)束結(jié)束 4.2 4.2 整數(shù)規(guī)劃方法建模整數(shù)規(guī)劃方法建模表4-21 完全滿足客戶需求所需的運輸總成本客戶1 客戶2 客戶3 客戶4 客戶5 客戶6 客戶7 客戶8 客戶9 客戶10 客戶11 客戶12倉庫1倉庫2倉庫3倉庫4倉庫5倉庫6倉庫7倉庫8倉庫9倉庫10倉庫11倉庫12100 80 50 50 60 100 120 90 60 70 65 110120 90 60 70 65 110 140 110 80 80 75 130 140 110 80 80 75 130 160 125 100 100 80 150160 125 100