《運籌學(xué)復(fù)習(xí)》ppt課件

1、運籌學(xué)復(fù)習(xí) 1、線性規(guī)劃的基本概念2、單純形法和對偶單純形法3、對偶線性規(guī)劃4、運輸問題5、目標(biāo)規(guī)劃6、整數(shù)規(guī)劃7、網(wǎng)絡(luò)最大流問題8、網(wǎng)絡(luò)最短路徑問題第一章 線性規(guī)劃模型和單純形法q線性規(guī)劃問題一般模型目標(biāo)函數(shù) ：max，min約束條件：,=,變量符號：0, unr, 0q線性規(guī)劃的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：min約束條件：=變量符號：0unr, 0 )(Xb),(AX. t . sXCzmax(min)T0XbAX. t . sXCzminTq 非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式 極大化目標(biāo)函數(shù)轉(zhuǎn)化為極小化：目標(biāo)函數(shù)系數(shù)變號 約束條件是不等式轉(zhuǎn)化為等式：“”約束 加上松弛變量 “”約束 減去松弛變量 變量沒有

2、符號限制轉(zhuǎn)化為變量非負(fù)：沒有符號限制的變量用兩個非負(fù)變量的差表示例如:max z=3x1+4x2-2x3+5x4s.t 4x1-x2+2x3-x4=4 x1+x2+3x3-x414 -2x1+3x2-x3+2x43x10,x22,x30,x4:unr線性規(guī)劃的圖解 畫約束直線 確定滿足約束條件的半平面 所有半平面的交集凸多邊形線性規(guī)劃的可行域 畫兩條目標(biāo)函數(shù)等值線 確定目標(biāo)函數(shù)優(yōu)化的方向 平行移動目標(biāo)函數(shù)等值線 得到線性規(guī)劃的最優(yōu)解q線性規(guī)劃問題的概念基：設(shè)標(biāo)準(zhǔn)形式的LP問題的約束方程組的秩為M，B是系數(shù)矩陣A中的M階滿秩子矩陣，則稱B是該LP問題的一個基?；兞浚築中的每一個列向量成為基向量

3、，對應(yīng)的變量為基變量，共有M個。非基變量：B以外的列向量稱為非基向量，對應(yīng)變量成為非基變量，共有N-M個?；A(chǔ)解：對應(yīng)基B，令所有的非基變量為零，求解約束方程組AX=b，可惟一得出基變量的一組值，這樣得到的N個變量的一組解成為一個“基礎(chǔ)解”?；A(chǔ)可行解：如果一個基礎(chǔ)解中的所有變量都大于或等于0，則稱這個基礎(chǔ)解為“基礎(chǔ)可行解”。退化解：基解中的非零分量的個數(shù)小于M個時，即某個基變量為零時，此時為退化解。q線性規(guī)劃的基本定理 線性規(guī)劃的基礎(chǔ)可行解就是可行域的極點。線性規(guī)劃的基本概念min z=x1+2x2s.t. x1+x2 4(1) -x1+x22(2) x2 5(3) x1, x2 0OABC

4、DEFG41234123x1x2x3=0 x4=0 x2=0 x1=0 x5=0引進(jìn)松弛變量x3, x4, x5min z=x1+2x2s.t. x1+x2+x3 =4 -x1+x2 -x4=2 x2 +x5=5 x1, x2 x3, x4, x50基礎(chǔ)解O A B C D E F GBEF四邊形B E F G基礎(chǔ)可行解可行域目標(biāo)函數(shù)等值線.最優(yōu)解B5GqA不是可行解，是由于變量（ ） 0。qC不是可行解，是由于變量（ ）0，則xn+i=0如果xn+i0，則wi=0邊際利潤大于0的資源，在最優(yōu)生產(chǎn)計劃條件下沒有剩余wm+jxj=0如果wm+j0，則xj=0如果xj0，則wm+j=0最優(yōu)生產(chǎn)計劃

5、條件下有剩余的資源，其邊際利潤等于0差額成本大于0（機會成本大于利潤）的產(chǎn)品，不安排生產(chǎn)安排生產(chǎn)的產(chǎn)品，差額成本等于0（機會成本等于利潤）q靈敏度分析 主要分析當(dāng)所給問題數(shù)據(jù)改變時，原有解的可行性和最有優(yōu)性有何變化。v目標(biāo)函數(shù)中系數(shù)的變化v約束條件右端常數(shù)的變化v約束條件左端系數(shù)的變化v引入新的變量v引入新的約束 利用對偶單純形法求解 Min z=4x1+6x2+18x3 S.t x1+ 3x3 3 x2+2x3 5 x1,x2,x3 0第三章 運輸問題q 運輸問題的模型q運輸問題的表格表示123467531x11x12x13x141484272x21x22x23x2427591063x31x

6、32x33x341922131213q 運輸表中一個基必須具備的特點1、一個基應(yīng)占表中的m+n-1格2、構(gòu)成基的同行同列格子不能構(gòu)成閉回路3、一個基在表中所占的格子應(yīng)包括表的每行和每列q初始基可行解的求法v西北角法v最小元素法q最優(yōu)解的獲得123411291114120271513823031065418012585110210運輸問題12341129111412027151382303106541801258511021012510508535018003030075357507500用最小元素法得到一個初始基礎(chǔ)可行解1234112911141202715138230310654180125

7、8511021012585180303575-7求非基變量x11的檢驗數(shù)12341129111412027151382303106541801258511021012585180303575-7-8求非基變量x14的檢驗數(shù)12341129111412027151382303106541801258511021012585180303575-7-8-4求非基變量x22的檢驗數(shù)12341129111412027151382303106541801258511021012585180303575-7-8-6-7求非基變量x31的檢驗數(shù)123411291114120271513823031065418

8、01258511021012585180303575-7-8-4-7+1求非基變量x32的檢驗數(shù)12341129111412027151382303106541801258511021012585180303575-7-8-4-7+1+4求非基變量x33的檢驗數(shù)12341129111412027151382303106541801258511021012585180303575-7-8-6-7+1+4x33=75進(jìn)基，x23=0離基，x24=30+75=105，x34=180-75=105確定進(jìn)基變量和離基變量123411291114120271513823010531065418075125

9、851102101258510535-3求非基變量x11的檢驗數(shù)123411291114120271513823010531065418075125851102101258510535-3-4求非基變量x14的檢驗數(shù)123411291114120271513823010531065418075125851102101258510535-3-4-8求非基變量x22的檢驗數(shù)123411291114120271513823010531065418075125851102101258510535-6-4-4-8求非基變量x23的檢驗數(shù)1234112911141202715138230105310654

10、18075125851102101258510535-5-4-4-7-8求非基變量x31的檢驗數(shù)123411291114120271513823010531065418075125851102101258510535-5-4-4-7-3-8得到最優(yōu)解：x12=85, x13=35, x21=125, x24=105, x33=75, x34=105 min z = 3660求非基變量x32的檢驗數(shù)q不平衡運輸問題v 發(fā)大于收，則虛設(shè)收地，運價為零v 發(fā)小于收，則虛設(shè)發(fā)地，運價為零q靈敏度分析v 基變量的運價調(diào)整v 非基變量的運價調(diào)整物流配送案例騰飛電子儀器廠在大連和廣州有兩個分廠生產(chǎn)同一種儀器

11、 。大連分廠每月生產(chǎn)400臺廣州分廠每月生產(chǎn)600臺。該公司在上海和天津有兩個物流配送服務(wù)網(wǎng)點，負(fù)責(zé)對南京、濟(jì)南、南昌、青島四個城市的儀器進(jìn)行配送供應(yīng)。另外，因為大連距離青島較近，公司同意大連分廠向青島直接供貨。 這些城市間的每臺儀器的運輸費用標(biāo)在兩個城市間的弧上，單位為百元。公司應(yīng)該如何調(diào)運儀器可使總運輸費用最低?廣州600南昌350天津南京200濟(jì)南150大連400青島300上海2446362561433多工廠模型一家公司有A和B兩個工廠,每個工廠生產(chǎn)兩種同樣的產(chǎn)品,一種是普通的,每件利潤10元;一種是精制的,每件利潤15元.兩廠采用相同的加工工藝:研磨和拋光.A廠每周的研磨能力為80小時

12、,拋光能力為60小時; B廠每周的研磨能力為60小時,拋光能力為75小時.兩廠生產(chǎn)各類單位產(chǎn)品所需的研磨和拋光工時(以小時計)如表所示.另外,每類每件產(chǎn)品都消耗4公斤的原材料,該公司每周可獲得原材料120公斤.問:應(yīng)該如何制定生產(chǎn)計劃?工廠AB產(chǎn)品普通精制普通精制研磨4253拋光2556分析 先假定每周分配原料給A廠75公斤,B廠45公斤.設(shè)x1為A廠的普通產(chǎn)品產(chǎn)量;x2為A廠的精制產(chǎn)品產(chǎn)量;x3為B廠的普通產(chǎn)品產(chǎn)量;x4為B廠的精制產(chǎn)品產(chǎn)量.A廠模型:Maxz=10 x1+15x2S.t 4x1+4x2 75 (原料A) 4x1+2x2 80(研磨A) 2x1+5x2 60(拋光A) X1,

13、x2 0最優(yōu)解:(11.25,7.5,利潤225)剩余20小時的研磨時間B廠模型:Maxz=10 x3+15x4S.t 4x3+4x4 45 (原料B) 5x3+3x4 60(研磨B) 5x3+6x4 75(拋光B) X3,x4 0最優(yōu)解:(11.25,3.75,利潤168.5)剩余26.25小時的研磨時間和7.5小時的拋光工時.假設(shè)建立一個公司模型,讓模型去確定原材料的分配:Max z=10 x1+15x2+10 x3+15x4S.t 4x1+4x2+4x3+4x4 120 4x1+2x2 80 2x1+5x2 60 5x3+3x4 60 5x3+6x4 75 x1,x2,x3,x4 0最優(yōu)

14、解:X1=9.17,x2=8.33,x4=12.5, z=404.15多周期動態(tài)生產(chǎn)計劃問題 考慮某廠配套生產(chǎn)產(chǎn)品問題.今年頭四個月收到的訂單數(shù)量分別為3000,4500,3500和5000件.該廠正常生產(chǎn)每月可生產(chǎn)產(chǎn)品3000件,利用加班還可生產(chǎn)1500件.正常生產(chǎn)成本為每件5000元,加班生產(chǎn)還要追加1500元的成本,庫存成本為每件每月200元.問該廠如何組織生產(chǎn)才能使生產(chǎn)成本最低?第五章 目標(biāo)規(guī)劃q概念v偏差變量：實際值與目標(biāo)值之間差距的變量表示，通常以di+ di-表示，分別為正、負(fù)偏差變量，且有di+0、 di- 0， di+ di- =0 v優(yōu)先因子：描述問題中目標(biāo)重要性程度的差別

15、，一般用pi表示，通常i值越小，代表的優(yōu)先程度越高。v目標(biāo)約束：用來描述允許對給定目標(biāo)值有一定偏離程度的限制條件。q目標(biāo)規(guī)劃模型的特點1、引進(jìn)正負(fù)偏差變量 2、模型中必須有目標(biāo)約束 3、目標(biāo)函數(shù)為偏差變量的表達(dá)式 4、以優(yōu)先級因子描述目標(biāo)的重要性程度q 目標(biāo)規(guī)劃的解法 單純形法：按單純形法求解一搬目標(biāo)規(guī)劃問題的滿意解。求解時需按優(yōu)先級的順序進(jìn)行逐步優(yōu)化。v 各目標(biāo)具有相同等級的目標(biāo)規(guī)劃v 各目標(biāo)具有不同優(yōu)先等級的目標(biāo)規(guī)劃v 各目標(biāo)具有賦權(quán)優(yōu)先等級的目標(biāo)規(guī)劃 第六章 整數(shù)規(guī)劃q整數(shù)規(guī)劃的基本概念v 變量的取值為整數(shù)的LP問題為整數(shù)規(guī)劃問題。q 整數(shù)規(guī)劃的一般模型q整數(shù)規(guī)劃的解法v 割平面法（純整

16、數(shù)規(guī)劃）v 分支定界法人力資源安排 某超市物流配送中心，星期六有4個裝卸工人當(dāng)班要分別指派他們?nèi)ネ瓿?項不同的裝卸工作每人做各項工作所取得的利潤如下表所示應(yīng)如何合理地指派這4人的工作，才能使配送中心獲得的利潤最大。 任務(wù)人員ABCD甲66697275乙70747386丙77686770丁78727468v 點與（有向）邊 每一條邊和兩個節(jié)點關(guān)聯(lián)，一條邊可以用兩個節(jié)點的標(biāo)號表示（i，j）jiv路徑（Path） 前后相繼并且方向相同的邊序列 P=(1,2),(2,3),(3,4)42314231v網(wǎng)絡(luò)由點和邊組成第七章 網(wǎng)絡(luò)規(guī)劃q 圖的基本概念v連通圖 任意兩個節(jié)點之間至少有一條鏈的圖稱為連通圖2

17、4351v圈(Cycle) 起點和終點重合的鏈稱為圈 =(1,2),(2,4),(3,4),(1,3) 圈中各條邊方向不一定相同4231v樹(Tree) 無圈的連通圖稱為樹 樹中只與一條邊關(guān)聯(lián)的節(jié)點稱為懸掛節(jié)點v 回路（Circuit） 起點和終點重合的路徑稱為回路 =(1,2),(2,4),(4,1) 回路中各條邊方向相同4231v 鏈（Chain） 前后相繼并且方向不一定相同的邊序列稱為鏈 C=(1,2),(3,2),(3,4)4231q 樹的性質(zhì)v 任何樹至少有一個懸掛節(jié)點243512435124351v如果樹的節(jié)點個數(shù)為m，則邊的個數(shù)為m-1v樹中任意兩個節(jié)點之間只有唯一的一條鏈v在樹

18、的任意兩個不相鄰的節(jié)點之間增加一條邊，則形成唯一的圈q 最小支撐樹v由網(wǎng)絡(luò)的所有節(jié)點（m個）和網(wǎng)絡(luò)的m-1條邊組成的樹稱為網(wǎng)絡(luò)的支撐樹，構(gòu)成支撐樹的各邊賦權(quán)之和最小的為最小支撐樹。4231423142314231423142314231q 最小支撐樹的算法vKruskal算法vPrim算法q最短路問題 vD氏算法q最短鏈問題q網(wǎng)絡(luò)上的最大流問題q最小割集1254367最大流問題36112743847125uij求從1到7的最大流125436736112743847125uij檢查每一條邊不飽和的方向，用 表示x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0

19、 x=0 D=minD12, D26, D 67=min3,6,12=3 D=minD13, D35, D 57=min11,4,5=4125436736112743847125uij尋找從1到7的不飽和鏈，用 表示，求出每一條不飽和鏈的間隙 Dx=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0D=3D=6D=12D=11D=4D=5125436736112743847125uij增加不飽和鏈的流量檢查每一條邊不飽和的方向，用 表示x=3x=3x=4x=0 x=0 x=0 x=0 x=0 x=3x=4x=4x=0f=7f=7尋找從1到7的不飽和鏈，用

20、 表示，求出每一條不飽和鏈的間隙 D125436736112743847125uijx=3x=3x=4x=0 x=0 x=0 x=0 x=0 x=3x=4x=4x=0D=7f=7f=7D=minD13, D34, D 46 , D 67=min7,3,4,8=3D=3D=4D=9125436736112743847125uij增加不飽和鏈的流量檢查每一條邊不飽和的方向，用 表示x=3x=3x=7x=0 x=0 x=3x=3x=0 x=6x=4x=4x=0f=10f=10尋找從1到7的不飽和鏈，用 表示，求出每一條不飽和鏈的間隙 D125436736112743847125uijx=3x=3x=

21、7x=0 x=0 x=3x=3x=0 x=6x=4x=4x=0f=10f=10 D=minD13, D32, D 26 , D 67=min4,2,3,6=2D=4D=2D=3D=6增加不飽和鏈的流量檢查每一條邊不飽和的方向，用 表示125436736112743847125uijx=3x=5x=9x=2x=0 x=3x=3x=0 x=8x=4x=4x=0f=12f=12尋找從1到7的不飽和鏈125436736112743847125uijx=3x=5x=9x=2x=0 x=3x=3x=0 x=8x=4x=4x=0f=12f=12已不存在從1到7的不飽和鏈。獲得最大流， f=12X=1,3，X

22、=2,4,5,6,7最小割集為(1,2),(3,2),(3,4),(3,5)，用 表示最小割集的容量為u12+u32+u34+u35=3+2+3+4=1212345678263958476104117126最短路徑問題求1到8的最短路徑12345678263958476104117126w1=0X=1min0+2,0+6,0+3=min2,6,3=2，w2=212345678263958476104117126w1=0X=1,2min2+9,2+5,2+4,0+6,0+3=min11,7,6,6,3=3，w4=3w2=212345678263958476104117126w1=0w2=2X=1

23、,2,4min2+9,2+5,2+4,0+6,3+7,3+6,3+10=min11,7,6,6,10,9,13=5，w3=6w4=312345678263958476104117126w1=0w2=2X=1,2,3,4min2+9,2+5,6+8,3+6,3+10=min11,7,14,9,13=7，w6=7w4=3w3=612345678263958476104117126w1=0w2=2X=1,2,3,4,6min2+9,7+4,7+11,3+10=min11,11,18,13=11，w5=11w4=3w3=6w6=712345678263958476104117126w1=0w2=2X=

24、1,2,3,4,5,6min11+12,7+7,7+11,3+10=min23,14,18,13=13，w7=13w4=3w3=6w6=7w5=1112345678263958476104117126w1=0w2=2X=1,2,3,4,6,7min11+12,7+7,13+6=min23,14,19=14，w8=14w4=3w3=6w6=7w5=11w7=1312345678263958476104117126w1=0w2=2X=1,2,3,4,6,7,8min11+12,7+7,13+6=min23,14,19=14，w8=14w4=3w3=6w6=7w5=11w7=13w8=1412345

25、678263958476104117126w1=0w2=2w4=3w3=6w6=7w5=11w7=13w8=14從1到8的最短路徑為14，最短路徑為12 6 8從1到其他節(jié)點的最短路徑如上圖紅線所示，其中到3和5的最短路徑有兩條。2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路徑問題求從A到E的最短路徑2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0505)E(f

26、)ED(d)D(f5114+2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5202)E(f)ED(d)D(f5224+2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5112421141113DC8118min2953min)D(f)D,C()D(f)D,C(min)C(f+最優(yōu)決策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0

27、f3(C2)=7f4(D1)=5f3(C1)=8222422141223DC7711min2556min)D(f)D,C()D(f)D,C(min)C(f+最優(yōu)決策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7232423141333DC121213min21058min)D(f)D,C()D(f)D,C(min)C(f+最優(yōu)決策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3

28、(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=81133312321131112CB20222120min1210714812min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f+最優(yōu)決策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=211233322322131222CB14161714min12471086min)C(f)C,B()C(f)C,B()C(f)C,B(

29、min)B(f+最優(yōu)決策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142333332323131332CB19231921min1211712813min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f+最優(yōu)決策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=1

30、9f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=2123232221211BA19201923min191145212min)B(f)B,A()B(f)B,A()B(f)B,A(min)A(f+最優(yōu)決策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài)A （ A，B2） B22511214

31、106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài)A （ A，B2） B2 （B2，C1） C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f

32、2(B1)=21狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài)A （ A，B2） B2 （B2，C1） C1 （C1，D1） D12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài)A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E從A到E的最短路徑為19，路線為AB

33、 2C1 D1 E 資源分配問題 4臺設(shè)備，分配給A、B、C三個工廠，每個工廠分配到不同數(shù)量的設(shè)備所能產(chǎn)生的效益（萬噸）如下表所示。求設(shè)備的最優(yōu)分配方案，使總效益最大。設(shè)備臺數(shù)產(chǎn)生的效益（萬噸）工廠A工廠B工廠C0000115129228282734042474505553動態(tài)規(guī)劃模型工廠A工廠B工廠C k=1k=2k=3k=4狀態(tài)變量xk：尚未分配的設(shè)備臺數(shù)x2x3x4決策變量dk：每個工廠分配的設(shè)備臺數(shù)d1d2d3x2=x1-d1階段kx1x3=x2-d2x4=x3-d3決策允許集合Dk(xk)：分配臺數(shù)dk的范圍0d1 x10d2 x20d3 x3狀態(tài)轉(zhuǎn)移方程Dk(xk)：狀態(tài)如何隨上一

34、狀態(tài)以及決策變化階段指標(biāo)Vk(xk,dk)：每個工廠分配設(shè)備產(chǎn)生的效益v1(x1,d1)v2(x2,d2)v3(x3,d3)最優(yōu)指標(biāo)函數(shù)fk(xk)fk(xk)=maxvk(xk,dk)+fk+1(xk+1)終端條件fn(xn)f4(x4)=0 x3D3(x3)x4v3(x3,d3) v3(x3,d3)+f4(x4) f3(x3)d3*00000+0=00010100+0=0911099+0=9*20200+0=02721199+0=9202727+0=27*30300+0=04731299+0=9212727+0=27304747+0=47*40400+0=05341399+0=922272

35、7+0=27314747+0=47405353+0=53*x3f3(x3)d3*000191227234734534f3(x3)f4(x4)x4f4(x4)0010203040 x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*00000+0=00010100+9=9121101212+0=12*20200+27=27282111212+9=21202828+0=28*30300+47=47*470121212+27=39212828+9=37304242+0=4240400+53=53591131212+47=59*222828+27=55314242+

36、9=51405555+0=55x3f3(x3)d3*000191227234734534f3(x3)x2f2(x2)d2*0001121228234704591f2(x2)f4(x4)=0 x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*40400+59=59621131515+47=62*222828+28=56314040+12=52405050+0=50 x1f1(x1)d1*4621x2f2(x2)d2*0001121228234704591x3f3(x3)d3*000191227234734534最優(yōu)解為：x1=4, d1*=1x2=x1-d1=3, d2*=0 x3=x2-d2=3, d3*=3x4=x3-d3=0即工廠A分配1臺，工廠B不分配，工廠C分配3臺，最大效益為62萬噸，設(shè)備沒有剩余。背包問題一艘貨輪載重量為1000噸，裝載以下三種貨物：貨物A貨物B貨物C重量（噸/件）240320430價值（萬元/件）354663單位重量價值0.1460.1440.147每種貨物各裝載多少件