我的運(yùn)籌學(xué)wang線性規(guī)劃與單純形法學(xué)習(xí)教案

1、會計(jì)學(xué)1我的運(yùn)籌學(xué)我的運(yùn)籌學(xué)wang線性規(guī)劃線性規(guī)劃(xin xn u hu)與單純形法與單純形法第一頁，共123頁。 LP的數(shù)學(xué)模型(mxng) 圖解法 單純形法 單純形法的進(jìn)一步討論人工變量法 LP模型(mxng)的應(yīng)用第1頁/共122頁第二頁，共123頁。生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益(xioy)，這就是規(guī)劃問題。（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多 、利潤最大.）

2、第2頁/共122頁第三頁，共123頁。xa xxav 220 dxdv0)2()2()2(22 xaxxa6ax 第3頁/共122頁第四頁，共123頁。例1.2 某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源(zyun)及單位產(chǎn)品利潤 問：應(yīng)如何安排生產(chǎn)計(jì)劃，才能(cinng)使總利潤最大？ 解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量 分別為 x1、x22.目標(biāo)函數(shù)：設(shè)總利潤為z，則有： max z = 2 x1 + x23.約束條件： 5x2 15 6x1+ 2x2 24 x1+ x2 5 x1， x20第4頁/共122頁第五頁，共123頁。例1.3 已知資料如下(rxi)表所示，問如何安排生產(chǎn)才

3、能使利潤最大？或如何考慮利潤大，產(chǎn)品好銷。 設(shè) 備產(chǎn) 品 A B C D利潤（元） 2 1 4 0 2 2 2 0 4 3 有 效 臺 時(shí)12 8 16 12解：1.決策變量(binling)：設(shè)產(chǎn)品I、II的產(chǎn)量分別為 x1、x22.目標(biāo)函數(shù)：設(shè)總利潤為z，則有： max z = 2 x1 + 3x23.約束條件： x1 0 , x2 0 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12第5頁/共122頁第六頁，共123頁。例 某廠生產(chǎn)三種藥物，這些藥物可以從四種不同的原料中提取(tq)。下表給出了單位原料可提取(tq)的藥物量 解：要求：生產(chǎn)A種藥物至少160單位

4、；B種藥物恰好200單位，C種藥物不超過(chogu)180單位，且使原料總成本最小。1.決策變量：設(shè)四種原料的使用 量分別為：x1、x2 、x3 、x42.目標(biāo)函數(shù)：設(shè)總成本為z min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.約束條件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x1 x2 +x3 +2 x4 180 x1、x2 、x3 、x4 0第6頁/共122頁第七頁，共123頁。 例 某航運(yùn)局現(xiàn)有船只種類、數(shù)量以及(yj)計(jì)劃期內(nèi)各條航線的貨運(yùn)量、貨運(yùn)成本如下表所示：航線號航線號船隊(duì)船隊(duì)類型類型編隊(duì)形式編隊(duì)形式貨運(yùn)成

5、本貨運(yùn)成本（千元隊(duì)）（千元隊(duì)）貨運(yùn)量貨運(yùn)量（千噸）（千噸）拖輪拖輪A型型駁船駁船B型型駁船駁船1112362521436202322472404142720船只種類船只種類船只數(shù)船只數(shù)拖拖 輪輪30A型駁船型駁船34B型駁船型駁船52航線號航線號合同貨運(yùn)量合同貨運(yùn)量12002400問：應(yīng)如何編隊(duì)，才能既完成合同(h tong)任務(wù)，又使總貨運(yùn)成本為最?。康?頁/共122頁第八頁，共123頁。 解：設(shè)：xj為第j號類型(lixng)船隊(duì)的隊(duì)數(shù)（j = 1，2，3，4）， z 為總貨運(yùn)成本則： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4

6、 30 2x1 + 2x3 34 4x2 + 4x3 + 4x4 5225x1+20 x2 200 40 x3+20 x4 400 xj 0 （ j = 1,2,3,4）第8頁/共122頁第九頁，共123頁。第9頁/共122頁第十頁，共123頁。第10頁/共122頁第十一頁，共123頁。第11頁/共122頁第十二頁，共123頁。00 )( )( (min) max12211112121112211 nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 簡寫為：第12頁/共122頁第

7、十三頁，共123頁。) (21ncccC nxxX1 mjjjaaP1 mbbB1 0 )( (min) maxXBxpCXzjj其中(qzhng)：第13頁/共122頁第十四頁，共123頁。 mnmnaaaaA1111 0 )( (min) maxXBAXCXZ其中(qzhng)：) (21ncccC nxxX1 mbbB1第14頁/共122頁第十五頁，共123頁。minjxbxatsxcZjnjijijnjjj, 2 , 1, 2 , 1, 0.max11 特點(diǎn)：(1) 目標(biāo)(mbio)函數(shù)求最大值（有時(shí)求最小值）(2) 約束條件都為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于零(3) 決策變量

8、xj為非負(fù)。第15頁/共122頁第十六頁，共123頁。 目標(biāo)(mbio)函數(shù)的轉(zhuǎn)換 如果是求極小值即 ，則可將目標(biāo)函數(shù)乘以(-1)，可化為求極大值問題。 jjxczmin也就是：令 ，可得到上式。zz jjxczzmax即 若存在取值無約束的變量 ，可令 其中：jxjjjxxx 0, jjxx 變量的變換第16頁/共122頁第十七頁，共123頁。 約束方程的轉(zhuǎn)換(zhunhun)：由不等式轉(zhuǎn)換(zhunhun)為等式。 ijijbxa0 iniinjijxbxxa稱為松弛(sn ch)變量 ijijbxa0 iniinjijxbxxa稱為剩余變量 常量 bi0 的變換:約束方程兩邊乘以（1）第

9、17頁/共122頁第十八頁，共123頁。例 將下列線性規(guī)劃(xin xn u hu)問題化為標(biāo)準(zhǔn)形式 ,0,52324 7 532min321321321321321無無約約束束xxxxxxxxxxxxxxxZ用 替換(t hun) ，且 解:（）因?yàn)閤3無符號要求 ，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以33xx 3x0,33 xx第18頁/共122頁第十九頁，共123頁。(2) 第一個(gè)約束條件是“”號，在“”左端加入松馳變量x4，x40,化為等式；(3) 第二個(gè)約束條件是“”號，在“”左端減去剩余變量x5，x50；(4) 第3個(gè)約束方程右端常數(shù)項(xiàng)為-5，方程兩邊同乘以(-1),

10、將右端常數(shù)項(xiàng)化為正數(shù)； (5) 目標(biāo)(mbio)函數(shù)是最小值，為了化為求最大值，令z=-z,得到max z=-z，即當(dāng)z達(dá)到最小值時(shí)z達(dá)到最大值，反之亦然;第19頁/共122頁第二十頁，共123頁。 0,5 )(252 )( 7 )(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ標(biāo)準(zhǔn)(biozhn)形式如下：第20頁/共122頁第二十一頁，共123頁。 例1.7 將下列(xili)線性規(guī)劃問題化為標(biāo)準(zhǔn)形式 ,0,52324 7 532min321321321321321xxxxxxxxxxxxxxxZ為無約束（無非

11、(wfi)負(fù)限制）第21頁/共122頁第二十二頁，共123頁。 解: 用 替換(t hun) ，且 ， 54xx 3x0,54 xx將第3個(gè)約束方程兩邊(lingbin)乘以（1）將極小值問題(wnt)反號，變?yōu)榍髽O大值標(biāo)準(zhǔn)形式如下： 0,5 )(252 )( 7 )(500)(32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxZ76, xx引入變量第22頁/共122頁第二十三頁，共123頁。 無約束2121212,0435832xxxxxxx-xminZ10 x ,x ,x ,x ,xx)x(xxx)x(xx)x(xxZaxm1

12、111654364354343435832例1.8 將線性規(guī)劃(xin xn u hu)問題化為標(biāo)準(zhǔn)型解：第23頁/共122頁第二十四頁，共123頁。 例1.9 將線性規(guī)劃(xin xn u hu)問題化為標(biāo)準(zhǔn)型解：Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4 28 4 x1 + 2 x2 + 3 x3 - 9 x4 39 6 x2 + 2 x3 + 3 x4 - 58 x1 , x3 , x4 0； x2無約束 Max z = 3x15x2+5x2”8x3 +7x4 s.t. 2x13x2+3x2”+5x3+6

13、x4+x5= 28 4x1+2x2-2x2”+3x3-9x4-x6= 39 -6x2+6x2”-2x3-3x4-x7 = 58 x1 ,x2,x2”,x3 ,x4 ,x5 ,x6 ,x7 0 第24頁/共122頁第二十五頁，共123頁。12nc ,c ,c )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnjijijnjjj線性規(guī)劃(xin xn u hu)問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值。 為價(jià)值系數(shù)， 為技術(shù)系數(shù)1112mna ,a ,a第25頁/共122頁第二十六頁，

14、共123頁。 可行解：滿足約束條件、的解為可行解。所有可行解的集合為可行域。 最優(yōu)解：使目標(biāo)(mbio)函數(shù)達(dá)到最大值的可行解。 基：設(shè)A為約束條件的mn階系數(shù)矩陣(m04010換出行(chxng)將3化為15/311801/301/31011/3303005/304/3乘以1/3后得到103/51/518011/5 2/540011第57頁/共122頁第五十八頁，共123頁。 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)(biozhn)形式： 5 , 2 , 1, 02053115232.2max53214321321jxxx

15、xxxxxxtsxxxZj不難看出x4、x5可作為初始基變量，列單純形表計(jì)算。第58頁/共122頁第五十九頁，共123頁。cj12100icB基變量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x2j 2021/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9-1/9-7/3j 第59頁/共122頁第六十頁，共123頁。 0,124 16 482122232max2121212121xxxxxxxxxxZ變成標(biāo)準(zhǔn)型 0, 12 4 16 4 8 2 21 220000

16、32max6543216251421321654321xxxxxxxxxxxxxxxxxxxxxxZ第60頁/共122頁第六十一頁，共123頁。約束方程的系數(shù)(xsh)矩陣 654321100040010004001021000122ppppppA IppppB100001000010000165436543 xxxx,21xx ,為基變量(binling)為非基變量(binling)I 為單位矩陣且線性獨(dú)立第61頁/共122頁第六十二頁，共123頁。第62頁/共122頁第六十三頁，共123頁。第63頁/共122頁第六十四頁，共123頁。第64頁/共122頁第六十五頁，共123頁。n判斷(pn

17、dun)現(xiàn)行的基本可行解是否最優(yōu) 假如(jir)已求得一個(gè)基本可行解將這一基本(jbn)可行解代入目標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函數(shù)值其中分別表示基變量和非基變量所對應(yīng)的價(jià)值系數(shù)子向量。1B bX=01-1BNBB bZ=CX=(C C )=C B b0B12mNm+1m+2nC =(c ,c ,c ), C =(c,c,c )第65頁/共122頁第六十六頁，共123頁。要判定是否已經(jīng)(y jing)達(dá)到最大值，只需將代入目標(biāo)函數(shù)，使目標(biāo)函數(shù)用非基變量表示，即： m+1m+2-1-1BNNBm+1,m+1,nnxxC B b+ XC B b+( )x 其中 稱為非基變量N的檢驗(yàn)向量(xinglin

18、g)，它的各個(gè)分量稱為檢驗(yàn)數(shù)。若N的每一個(gè)檢驗(yàn)數(shù)均小于等于0，即N0，那么現(xiàn)在的基本可行解就是最優(yōu)解。-1-1BNX=B b-B NX-1BZ=C B b-1NNBm+1m+1n=C -C B N=(,)BBNN-1-1BBNNBNNN-1-1BNBNXZ=CX=(C C )X=C X +C X =C (B b-B NX )+C X=C B b+(C -C B N)X-1-1-1BNBNNBAX=bBX +NX =bX =B b-B NXX =0,X =B b第66頁/共122頁第六十七頁，共123頁。定理1 最優(yōu)解判別定理 對于線性規(guī)劃問題若某個(gè)基本可行解所對應(yīng)(duyng)的檢驗(yàn)向量，則這

19、個(gè)基本可行解就是最優(yōu)解。定理2 無窮多最優(yōu)解判別定理 若是一個(gè)基本可行解，所對應(yīng)的檢驗(yàn)(jinyn)向量，其中存在一個(gè)檢驗(yàn)(jinyn)數(shù)m+k=0，則線性規(guī)劃問題有無窮多最優(yōu)解。nmaxZ=CX, D= XR /AX=b,X0-1NNB=C -C B N01B bX=0-1NNB=C -C B N0第67頁/共122頁第六十八頁，共123頁。例 用單純形方法求解線性規(guī)劃(xin xn u hu)問題解：本題的目標(biāo)函數(shù)是求極小化的線性函數(shù)，可以令則這兩個(gè)線性規(guī)劃(xin xn u hu)問題具有相同的可行域和最優(yōu)解，只是目標(biāo)函數(shù)相差一個(gè)符號而已。 121324125jminZ=-x -2xxx

20、4xx3x2xx8x0 j1,2,3,4,5，12Z = -Z = x +2x1212minZ=-x -2xmaxx +2xZ第68頁/共122頁第六十九頁，共123頁。0 1 0 1 03x220 0 1 2 -12x30-0 1 0 1 03x224/11 0 1 0 04x303/10 1 0 1 03x40_1 0 1 0 04x30 0 0 0 0 -18Z1 0 0 -2 12x11 1 0 0 -2 06Z2/11 0 0 -2 12x50 1 2 0 0 00Z8/21 2 0 0 18x50 x1 x2 x3 x4 x5bXBCB 1 2 0 0 0C最優(yōu)解最優(yōu)值X2,3,2

21、,0,0TmaxZ=8 or minZ=-82/23/1-第69頁/共122頁第七十頁，共123頁。 因?yàn)榉腔兞縳4的檢驗(yàn)數(shù)4=0，由無窮多最優(yōu)解判別定理，本例的線性規(guī)劃問題(wnt)存在無窮多最優(yōu)解。事實(shí)上若以x4為換入變量，以x3為換出變量，再進(jìn)行一次迭代，可得以下單純形表：最優(yōu)解 最優(yōu)值最優(yōu)解的一般(ybn)表示式maxZ =8 or minZ=-8X4,2,0,1,0TX(2,3,2,0,0)(1) 4,2,0,1,0,01.TTC 1 2 0 0 0CBXBb x1 x2 x3 x4 x5021x4x2x1124 0 0 1/2 1 -1/2 0 1 -1/2 0 1/2 1 0

22、1 0 0Z8 0 0 0 0 -1第70頁/共122頁第七十一頁，共123頁。對于極小化的線性規(guī)劃問題的處理：先化為標(biāo)準(zhǔn)型，即將極小化問題變換為極大化問題，然后利用單純形方法求解直接利用單純形方法求解，但是檢驗(yàn)是否最優(yōu)的準(zhǔn)則有所不同，即： 若某個(gè)基本可行解的所有非基變量對應(yīng)(duyng)的檢驗(yàn)數(shù) （而不是），則基本可行解為最優(yōu)解否則采用最大減少原則（而非最大增加原則）來確定換入變量，即： 若則選取對應(yīng)(duyng)的非基變量xm+k為換入變量確定了換入變量以后，換出變量仍采用最小比值原則來確定。 NNB= C-CN0jjm+kmin / 0因但所以(suy)原問題無最優(yōu)解1-1P=01-2第

23、89頁/共122頁第九十頁，共123頁。 退化(tuhu) 即計(jì)算出的 （用于確定換出變量）存在有兩個(gè)以上相同的最小比值，會造成下一次迭代中由一個(gè)或幾個(gè)基變量等于零，這就是(jish)退化（會產(chǎn)生退化解）。 為避免出現(xiàn)計(jì)算的循環(huán)，勃蘭特(Bland)提出一個(gè)簡便有效的規(guī)則（攝動(dòng)法原理）： 當(dāng)存在多個(gè) 時(shí)，選下標(biāo)最小的非基變量為換入變量；(2) 當(dāng)值出現(xiàn)兩個(gè)以上相同的最小值時(shí)，選下標(biāo)最大的基變量為換出變量。0j第90頁/共122頁第九十一頁，共123頁。例 求解下述線性規(guī)劃問題(wnt)：解：引入松弛變量化標(biāo)準(zhǔn)型123412341234 3jmaxZ=3x -80 x +2x -24xx -32

24、x -4x36x 0 x -24x - x 6x 0 x 1 x0,j1,2,3,41234123451234 637jmaxZ=3x -80 x +2x -24xx -32x -4x36x x 0 x -24x - x 6x x 0 x x 1 x0,j1,2,3,4,5,6,7567x ,x ,x第91頁/共122頁第九十二頁，共123頁。000-242-8030Z-5-30-420-805Z10001001x3 211060-2411x1 3321300-803x5 00-30-425-800Z1000 1001x7 00106-1-2410 x1 30-1130-3-800 x5 0-

25、10001001x7 000106-1-2410 x6 0000136-4-3210 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 000-242-803C 第一次迭代中使用了攝動(dòng)法原理(yunl)，選擇下標(biāo)為6的基變量x6離基?？傻米顑?yōu)解maxZ=，X1,0,1,0,3T第92頁/共122頁第九十三頁，共123頁。 無窮(wqing)多最優(yōu)解 若線性規(guī)劃問題某個(gè)基本(jbn)可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零，但其中存在一個(gè)檢驗(yàn)數(shù)等于零，那么該線性規(guī)劃問題有無窮多最優(yōu)解。例：最優(yōu)表：非基變量檢驗(yàn)數(shù)，所以有無窮多最優(yōu)解。C 1 2 0 0 0CBXBb x1 x2 x

26、3 x4 x5021x3x2x12320 0 1 2 -10 1 0 1 01 0 0 -2 12/23/1-Z8 0 0 0 0 -14= 0第93頁/共122頁第九十四頁，共123頁。解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)(jinyn)數(shù)非零,則線性規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗(yàn)(jinyn)數(shù)為零,則線性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。3）無界解判別：某個(gè)k0且aik（i=1，2,m）則線性規(guī)劃具有無界解。4）無可行解的判斷：當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri0時(shí)，則表明原線性規(guī)劃無可行解。5）退化解的判別：存在某個(gè)基變

27、量為零的基本可行解。第94頁/共122頁第九十五頁，共123頁。建建立立模模型型個(gè)個(gè) 數(shù)數(shù)取取 值值右右 端端 項(xiàng)項(xiàng)等式或等式或不等式不等式極大或極小極大或極小新加變新加變量系數(shù)量系數(shù)兩兩個(gè)個(gè)三個(gè)三個(gè)以上以上xj0 xj無無約束約束xj 0 bi 0bi 0=max Zmin Zxs xa求求解解圖圖解解 法法、單單純純形形法法單單純純形形法法不不處處理理令令xj = xj - xj xj 0 xj 0令令 xj =- xj不不處處理理約束約束條件條件兩端兩端同乘同乘以以-1-1加加松松弛弛變變量量xs加加入入人人工工變變量量xa減減去去xs加加入入xa不不處處理理令令z=- ZminZ=ma

28、x z0-M第95頁/共122頁第九十六頁，共123頁。停止停止Ajjjzc :求求0 j所所有有kj即即找找出出max)()0(0 jika對對任任一一)0( lklkiiaab 計(jì)計(jì)算算lkxx替替換換基基變變量量用用非非基基變變量量新新單單純純形形表表列列出出下下一一個(gè)個(gè)ax含有含有量中是否量中是否基變基變 0 j非非基基變變量量的的有有某某個(gè)個(gè)最最優(yōu)優(yōu)解解一一唯唯 無無可可行行解解最最優(yōu)優(yōu)解解無無窮窮多多是是否否環(huán)環(huán)循循否否否否否否是是是是是是循環(huán)循環(huán)無無界界解解第96頁/共122頁第九十七頁，共123頁。 要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù) 存在著多種方案 要求達(dá)到

29、(d do)的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線性等式或不等式描述第97頁/共122頁第九十八頁，共123頁。合理利用線材問題：如何下料使用材最少。配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤。投資問題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大。產(chǎn)品生產(chǎn)(shngchn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大。勞動(dòng)力安排：用最少的勞動(dòng)力來滿足工作的需要。運(yùn)輸問題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。第98頁/共122頁第九十九頁，共123頁。 (1)設(shè)立決策變量； (2)明確約束條件并用(bn yn)決策變量的線性等式或不等式表示； (3)用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大（M

30、ax）還是極小（Min）； (4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。建立線性規(guī)劃模型的過程可以(ky)分為四個(gè)步驟：第99頁/共122頁第一百頁，共123頁。 某廠計(jì)劃在下一生產(chǎn)周期內(nèi)生產(chǎn)B1,B2, Bn種產(chǎn)品，要消耗A1,A2, Am種資源，已知每件產(chǎn)品所消耗的資源數(shù)、每種資源的數(shù)量限制以及每件產(chǎn)品可獲得的利潤(lrn)如表所示，問如何安排生產(chǎn)計(jì)劃，才能充分利用現(xiàn)有的資源，使獲得的總利潤(lrn)最大？單件單件 產(chǎn)產(chǎn) 消耗消耗 品品資源資源資源資源限制限制單件利潤單件利潤1 nBBL1 mAAM1 mbbM1 CnCL1111 nmm naaaaLMML 0maxjijijjjx

31、bxaxcZ模型第100頁/共122頁第一百零一頁，共123頁。 某工廠用機(jī)床A1,A2, Am 加工B1,B2, Bn 種零件。在一個(gè)(y )周期內(nèi)，各機(jī)床可能工作的機(jī)時(shí)（臺時(shí)），工廠必須完成各種零件的數(shù)量、各機(jī)床加工每個(gè)零件的時(shí)間（機(jī)時(shí)/個(gè)）和加工每個(gè)零件的成本（元/個(gè)）如表所示，問如何安排各機(jī)床的生產(chǎn)任務(wù)，才能完成加工任務(wù)，又使總成本最低？加工加工 零零 時(shí)間時(shí)間 件件機(jī)床機(jī)床機(jī)時(shí)機(jī)時(shí)限制限制必須零件數(shù)必須零件數(shù)1 nBBL1 maaM1 nbbL1 111 nmm naaaaLMML加工加工 零零 成本成本 件件機(jī)床機(jī)床1 nBBL1 mAAM1 111 nmm nccccLMML1

32、mAAM第101頁/共122頁第一百零二頁，共123頁。 0 min ( 11ijjijiijijminjijijijjiijxbxaxaxcZxBAx一一組組變變量量）。模模型型：的的數(shù)數(shù)量量，求求在在一一生生產(chǎn)產(chǎn)周周期期加加工工零零件件為為機(jī)機(jī)床床設(shè)設(shè)第102頁/共122頁第一百零三頁，共123頁。例1： 某廠生產(chǎn)、三種產(chǎn)品，都分別經(jīng)A、B兩道工序(gngx)加工。設(shè)A工序(gngx)可分別在設(shè)備A1和A2上完成，有B1、B2、B3三種設(shè)備可用于完成B工序(gngx)。已知產(chǎn)品可在A、B任何一種設(shè)備上加工；產(chǎn)品可在任何規(guī)格的A設(shè)備上加工，但完成B工序(gngx)時(shí)，只能在B1設(shè)備上加工；產(chǎn)

33、品只能在A2與B2設(shè)備上加工。加工單位產(chǎn)品所需工序(gngx)時(shí)間及其他各項(xiàng)數(shù)據(jù)如下表，試安排最優(yōu)生產(chǎn)計(jì)劃，使該廠獲利最大。第103頁/共122頁第一百零四頁，共123頁。設(shè)備設(shè)備產(chǎn)品產(chǎn)品設(shè)備有效設(shè)備有效臺時(shí)臺時(shí)設(shè)備加工費(fèi)設(shè)備加工費(fèi)（單位小時(shí)）（單位小時(shí)）2791210 000321B1684000250B24117000783B374000200原料費(fèi)（每件）原料費(fèi)（每件）0.250.350.5售價(jià)（每件）售價(jià)（每件）1.252.002.8第104頁/共122頁第一百零五頁，共123頁。）（上加工的數(shù)量相等）上加工的數(shù)量相等），在工序在工序（產(chǎn)品（產(chǎn)品上加工的數(shù)量相

34、等）上加工的數(shù)量相等），在工序在工序（產(chǎn)品（產(chǎn)品上加工的數(shù)量相等）上加工的數(shù)量相等），在工序在工序（產(chǎn)品（產(chǎn)品設(shè)備設(shè)備設(shè)備設(shè)備）（設(shè)備（設(shè)備）（設(shè)備（設(shè)備設(shè)備設(shè)備3 , 2 , 1; 2 , 1; 3 , 2 , 10BAIIIBAIIBAI)3B(40007)2B(70001141B4000862A100001297)1A(6000105322312221212211123122121112111123322122221121312212112211111 kjixxxxxxxxxxxxxxxxxxxxxijk第105頁/共122頁第一百零六頁，共123頁。300/6000(5x111+10

35、 x211 )-321/10000(7x112+9x212+12x312 )- 250/4000(6x121+8x221 )-783/7000(4x122+11x322 )-200/4000(7x123)n經(jīng)整理可得：nx111x112x211x212x312x121x221x122x322x123 5131)()(ii該該設(shè)設(shè)備備實(shí)實(shí)際際使使用用臺臺時(shí)時(shí)每每臺臺時(shí)時(shí)的的設(shè)設(shè)備備費(fèi)費(fèi)用用該該產(chǎn)產(chǎn)品品件件數(shù)數(shù)銷銷售售單單價(jià)價(jià)原原料料單單價(jià)價(jià)利利潤潤第106頁/共122頁第一百零七頁，共123頁。 ）（3,2,1;2,1;3,2,1040007700011440008610000129760001

36、05.35.023.1448.05.0375.0915.136.115.1775.075.0max322312221212211123122121112111123322122221121312212112211111123322122221121312212211112111kjixxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxijk第107頁/共122頁第一百零八頁，共123頁。 例例2 2：明興公司：明興公司(n s)(n s)生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機(jī)加工生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦

37、可以自行生產(chǎn)，但產(chǎn)和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問：公司品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問：公司(n s)(n s)為了獲得最大為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司(n s)(n s)鑄造和由外包協(xié)作各應(yīng)多少件？鑄造和由外包協(xié)作各應(yīng)多少件？甲乙丙資源限制鑄造工時(shí)(小時(shí)/件)51078000機(jī)加工工時(shí)(小時(shí)/件)64812000裝配工時(shí)(小時(shí)/件)32210000自產(chǎn)鑄件成本(元/件)354

38、外協(xié)鑄件成本(元/件)56-機(jī)加工成本(元/件)213裝配成本(元/件)322產(chǎn)品售價(jià)(元/件)231816第108頁/共122頁第一百零九頁，共123頁。n目標(biāo)函數(shù)： Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 n約束條件： s.t. 5x1 + 10 x2 + 7x3 8000n 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000n 3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000nx1,x2,x3,x4,x5 0第109頁/共122頁第一百一十頁，共123頁。例3：現(xiàn)有一批某種型號(xngho)的圓鋼長8米，需要截取米長的毛坯

39、100根，長米的毛坯200根。問如何才能既滿足需要，又能使總的用料最少？解：為了找到一個(gè)省料的套裁方案，必須(bx)先設(shè)計(jì)出較好的幾個(gè)下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，以滿足對各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的，為此可以設(shè)計(jì)出4種下料方案以供套裁用。2.5m32101.3m0246料頭料頭0.50.40.30.2第110頁/共122頁第一百一十一頁，共123頁。 )4.3.2.1(020064210023min4323214321jxxxxxxxxxxxZj設(shè)按方案、下料的原材料根數(shù)分別(fnbi)為xj (j=1，2,3,4)，可列出下面的數(shù)學(xué)模型：第111頁/共

40、122頁第一百一十二頁，共123頁。4. 合理合理(hl)配料問題配料問題 某飼養(yǎng)場用n種飼料B1,B2, Bn配置成含有m種營養(yǎng)成分A1,A2, Am的混合飼料，其余資料如表所示。問應(yīng)如何配料(pi lio)，才能既滿足需要，又使混合飼料的總成本最低？解： 0 m)1,2(i min 11jnjijijnjjjjxbxaxcZjx其其模模型型如如下下：種種飼飼料料所所用用的的數(shù)數(shù)量量，表表示示第第設(shè)設(shè)第112頁/共122頁第一百一十三頁，共123頁。例4：某人每天食用甲、乙兩種食物（如豬肉、雞蛋），其資料如下：問兩種食物各食用多少(dusho)，才能既滿足需要、又使總費(fèi)用最??？ 2 1.5原

41、料單價(jià)原料單價(jià)1.007.5010.00 0.1 0.15 1.7 0.75 1.10 1.30A1A2A3 最最 低低需要量需要量 甲甲 乙乙含量含量 食物食物成分成分第113頁/共122頁第一百一十四頁，共123頁。 0,00.1030.110.150.775.070.100.115.010.05.12min2121212121xxxxxxxxxxZ第114頁/共122頁第一百一十五頁，共123頁。例例5 5某工廠要用三種原料某工廠要用三種原料1 1、2 2、3 3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下乙、丙，數(shù)據(jù)如下(rxi)(rxi)表。問：該

42、廠應(yīng)如何安排生產(chǎn)，使利潤收入為表。問：該廠應(yīng)如何安排生產(chǎn)，使利潤收入為最大？最大？產(chǎn)品名稱規(guī)格要求單價(jià)（元/kg）甲原材料1不少于50%，原材料2不超過25%50乙原材料1不少于25%，原材料2不超過50%35丙不限25原材料名稱每天最多供應(yīng)量單價(jià)（元/kg）11006521002536035第115頁/共122頁第一百一十六頁，共123頁。x32；n對于原料3： x13，x23，x33；n目標(biāo)函數(shù)： 利潤最大，利潤 = 收入 - 原料支出(zhch) n約束條件： 規(guī)格要求 4 個(gè)；n供應(yīng)量限制 3 個(gè)。第116頁/共122頁第一百一十七頁，共123頁。Max z = -15x11+25x1

43、2+15x13-30 x21+10 x22-40 x31-10 x33 Max z = -15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 . 0.5 x11-0.5 x12 -0.5 x13 0 . 0.5 x11-0.5 x12 -0.5 x13 0 （原材料（原材料1 1不少于不少于50%50%） x11x12x13 0 x11x12x13 0 （原材料（原材料2 2不超過不超過(chogu)25%(chogu)25%） x21x22x23 0 x21x22x23 0 （原材料（原材料1 1不少于不少于25%25%） -0.5 x21+0.5 x

44、22 -0.5 x23 0 -0.5 x21+0.5 x22 -0.5 x23 0 （原材料（原材料2 2不超過不超過(chogu)50%(chogu)50%） x11+ x21 + x31 100 ( x11+ x21 + x31 100 (供應(yīng)量限制）供應(yīng)量限制） x12+ x22 + x32 100 ( x12+ x22 + x32 100 (供應(yīng)量限制）供應(yīng)量限制） x13+ x23 + x33 60 ( x13+ x23 + x33 60 (供應(yīng)量限制）供應(yīng)量限制） xij 0 , i = 1,2,3; j = 1,2,3 xij 0 , i = 1,2,3; j = 1,2,3第117頁/共122頁第一百一十八頁，共123頁。例6 某晝夜(zhuy)服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員人數(shù)如下表所示：班次班次時(shí)間時(shí)間所需人員所需人員16:0010:0060210:0014:0070314:0018:006