運籌學大題舉例

運籌學大題舉例例1:某藥廠生產(chǎn)A、B、C三種藥物，可供選擇的原料有甲、乙、丙、丁，四種原料的成本分別是5元，6元，7元，8元。每公斤不同原料所能提取的各種藥物的數(shù)量（單位：克/公斤）見下表.藥廠要求每天生產(chǎn)A藥恰好100克，B藥至少530克，C藥不超過160克，要求選配各種原料的數(shù)量既滿足生產(chǎn)需要，又使總成本最小，試建立此問題的數(shù)學模型。

藥名原料ABC成本（元/kg）甲1525乙1416丙1517丁1628生產(chǎn)量恰好100克至少530克不超過160克解：設x1,x2,x3,x4分別為原料甲、乙、丙、丁的選配數(shù)量（單位：公斤），則有minz=5x1+6x2+7x3+8x4s.t.x1+x2+x3+x4=100

5x1+4x2+5x3+6x45302x1+x2+x3+2x4160x1,x2,x3,x40求解如下線性規(guī)劃問題例2復習解：加入松弛變量，標準化得建立單純形表如下：復習復習解畢復習例3:用大M法計算下列線性規(guī)劃maxz=2x1+3x2

s.t. 2x1+x2

16

x1+3x2

20

x1+x2=10

x1,x2

0解：化為標準形并加入人工變量為：maxz=2x1+3x2-Mx5-Mx6s.t.2x1+x2

+x4=16

x1+3x2-x3+x5

=20

x1+x2+x6=10

x1,x2,x3,x4,x5,x6

0cj2300-M-MCBXBB-1bx1x2x3x4x5x60x4610010-13x2102100010x3101010-13j30-1000-M-M-3最優(yōu)解為(0，10)T,最優(yōu)值為z*=30設某種物資有3個產(chǎn)地A1，A2，A3，

生產(chǎn)量分別為9，5，7;有4個銷地B1，B2，B3，B4，銷售量分別為3，8，4，6

;已知從Ai到Bj

物資的單位運價見下表。求總運費最小的調(diào)運方案。B1B2B3B4產(chǎn)量A1291079A213425A384257銷量3846例4復習B1B2B3B4ai行差A1291079A213425A384257bj3846列差伏格爾法計算1用伏格爾法尋找初始基：先算出運價表中各行與各列的最小運費與次小運費的差額，并填入該運價表的最右列和最下行。從行差或列差中選出最大者，并選擇其所在行或列的最小元素。A1的行差最大，而其中運價c11最小,令x11為優(yōu)先運輸路線。5121123復習B1B2B3B4ai行差A12910795A2134251A3842572bj3846列差11230303/09/6用伏格爾法尋找初始基：銷地B1的銷量3全由產(chǎn)地A1供給，所以x21=x31=0。將x11=3填到調(diào)運方案表中第1行第1列上。畫去運輸數(shù)據(jù)表第一列，A1的產(chǎn)量剩余為9-3=6。得到新的產(chǎn)銷平衡與單位運價表.令伏格爾法計算1復習B1B2B3B4ai行差A1291079/65A2134251A3842572bj3/0846列差11230306/15/0用伏格爾法尋找初始基：再算出運價表中的行差與列差。B4的列差最大，而其中運價c24最小,令x24為優(yōu)先運輸路線。產(chǎn)地A2的產(chǎn)量2全供給銷地B4，所以x23=x24=0。畫去運輸數(shù)據(jù)表中第2行，B4的銷量還要6-5=1。得新表。521122112233050令伏格爾法計算1復習B1B2B3B4ai行差A1291079/65A213425/01A3842572bj3/0846/1列差11230304/07/3用伏格爾法尋找初始基：5211221122330505221122211522833204伏格爾法計算1復習B1B2B3B4ai行差A1291079/65A213425/01A384257/32bj3/084/06/1列差11230308/57/3/0用伏格爾法尋找初始基：521122112233050522112221152283320452221122211155228332203伏格爾法計算1復習B1B2B3B4ai行差A1291079/65A213425/01A384257/32bj3/084/06/1列差11230308/57/3/0用伏格爾法尋找初始基：0500452221122211155228332203現(xiàn)在只有一個產(chǎn)地兩個銷地，故令x12=5

,x14=1為基變量，將其分別填到調(diào)運方案表中1行2列與1行4列上。51得到產(chǎn)銷平衡運輸問題的一個初始方案伏格爾法計算1復習B1B2B3B4aiA1291079A213425A384257bj3846354351此方案的運費是3×2+5×9+4×7+5×2+3×4+4×2=88。伏格爾法給出的初始解往往更接近于最優(yōu)解。復習利用伏格爾法確定的初始解如下表所示：B1B2B3B4aiA1325910179A2134525A38344257bj38461、寫出基可行解對應的位勢方程組;2、并計算非基變量的檢驗數(shù)。復習求解位勢及檢驗數(shù)的過程可在一個特殊設計的表上完成，這個表的構造如下：在原單位運價表增加一行與一列，在列中填入ui，在行中填入vj；把運價cij記在每一格的右上角，用框標定，在基變量對應的格中標出0，構成表。復習由u1+v1=2,u1+v2=9,u1+v4=7,得v1=2,v2=9,v4=7;B1B2B3B4uiA102091007A213402A3804025vj0-5-52977位勢表：再由u2+v4=2，u3+v2=4，得u2=-5，u3=-5;最后由u3+v3=2得v3=7.取u1=0;復習檢驗數(shù)表：(計算所有非基變量的檢驗數(shù))B1B2B3B4uiA102091007A213402A3804025vj0-5-52977(3)(4)(-1)(2)(11)(3)當存在非基變量的檢驗數(shù)kl

≥0，說明現(xiàn)行方案為最優(yōu)方案，否則目標成本還可以進一步減小。復習伏格爾法的初始方案：B1B2B3B4uiA1325910170A213452-5A3834425-5vj2977(3)(4)(-1)(2)(11)(3)x22為換入變量,

從x22所在格出發(fā)做閉回路L,L中有兩個偶點x24,x12，取x12為換出變量，調(diào)整量為5.復習伏格爾法的調(diào)整方案：B1B2B3B4aiA1325910179A21034525A38344257bj3486在閉回路L上，偶點變量減5，奇點變量加5.0x22為換入變量,取x12為換出變量.065復習它所對應的位勢與檢驗數(shù)為：B1B2B3B4uiA13291067A2153402A3834425vj28670-5-4(1)(4)(4)(3)(10)(2)所有檢驗數(shù)都非負，迭代停止，運費為：3×2+6×7+5×3+3×4+4×2=83復習練習:單純形表解：化為標準形為C2–11000CBXBB-1bx1x2x3x4x5x60x4603111000x5101–120100x62011–100102–110002010200x4603111002x1101–120100x62011–100102–110000304-5-30102-3-101-3-2207.550x43004–51–302x1101–12010-1x21002–30–1115-1.5-0.50.51500.50.50.51001-1-225000-1.5-1.5-0.5所以，所求最優(yōu)解為z*=25,

x1=15,x2=5,x3=0,x4=10,x5=x6=0練習:求解下列運費最少的運輸問題

銷地產(chǎn)地B1B2B3B4產(chǎn)量A11056725A2827625A3934850銷/p>

銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A12510567A2258276A3509348銷伏格法（差額法）得：差額差額14111212201144303217251265515最優(yōu)性檢驗：由位勢法得

銷地產(chǎn)地B1B2B3B4A110567A28276A39348uivj610222712315-1從表中可以看出，a32

的檢驗數(shù)小于零，需要進行調(diào)整，得

銷地產(chǎn)地B1B2B3B4A125A2205A315305+5–5+5–5新的運輸方案為

銷地產(chǎn)地B1B2B3B4A125A21510A315530重新進行檢驗得：

銷地產(chǎn)地B1B2B3B4A110567A28276A39348uivj6102138122041z*=257+152+106+159+53+304=535練習:求節(jié)點v1到節(jié)點v5的最短距離及其路線vSv1v2v3v4v5122233344[解]P(vs)=0T(vj)=∞,j=1,…,5第一步：T(v1)=min{T(v1),P(vs)+ds1}=min{∞,0+4}=4(1)與節(jié)點vs直接相連的臨時標號的節(jié)點為v1,v2，將這兩個節(jié)點的臨時標號改為T(v2)=min{T(v2),P(vs)+ds2}=min{∞,0+3}=30∞∞∞∞∞42(2)在所有T標號中，最小的為T(v2)=3,于是令P(v2)=3vSv1v2v3v4v51222333440∞∞43第二步：(1)與節(jié)點v2直接相連的臨時標號的節(jié)點為V1和v4，把這兩個節(jié)點的T標號改為T(v1)=min{T(v1),P(v2)+d21}=min{4,3+2}=4T(v4)=min{T(v4),P(v2)+d24}=min{∞,3+2}=5(2).在所有T變化中，T(v1)=4最小，于是令P(v1)=4∞5