第六章 運(yùn)籌與優(yōu)化模型

1、1第六章 運(yùn)籌與優(yōu)化模型6.1 簡單的運(yùn)籌與優(yōu)化模型 一、 線性規(guī)劃模型 線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，它起源于工業(yè)生產(chǎn)組織管理的決策問題。在數(shù)學(xué)上它用來確定多變量線性函數(shù)在變量滿足線性約束條件下的最優(yōu)值；隨著計(jì)算機(jī)的發(fā)展，出現(xiàn)了如單純形法等有效算法，它在工農(nóng)業(yè)、軍事、交通運(yùn)輸、決策管理與規(guī)劃等領(lǐng)域中有廣泛的應(yīng)用。 例例 1 1 生產(chǎn)計(jì)劃問題生產(chǎn)計(jì)劃問題假設(shè)某廠計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品都要分別在A，B，C三種不同設(shè)備上加工按工藝資料規(guī)定：生產(chǎn)每件甲產(chǎn)品需占用設(shè)備的小時(shí)數(shù)分別為2，l，4；生產(chǎn)每件乙產(chǎn)品需占用設(shè)備的小時(shí)數(shù)分別為2，2，0. 已知各設(shè)備計(jì)劃期內(nèi)用于生產(chǎn)這兩種產(chǎn)品的能力(

2、小時(shí)數(shù))分別為12，8，16；又知每生產(chǎn)一件甲產(chǎn)品，該廠會(huì)獲得利潤2元，每生產(chǎn)一件乙產(chǎn)品，該廠能獲利潤3元，問該廠應(yīng)安排生產(chǎn)兩種產(chǎn)品各多少件才能使總的利潤收入為最大?解解 (1)明確決策變量 工廠需要確定的是甲、乙兩種產(chǎn)品的計(jì)劃生產(chǎn)量，設(shè)x1, x2分別為甲、乙兩種產(chǎn)品的計(jì)劃生產(chǎn)量，總的利潤為z (2)明確約束條件因設(shè)備A在計(jì)劃期內(nèi)有效時(shí)間為12小時(shí)，不允許超過 故有 12 2212xx對設(shè)備B，C也可列出類似的不等式12 28xx14 16x 此外產(chǎn)品的產(chǎn)量 12,x x只能取非負(fù)值，即 1x0 2x0 這種限制稱為變量的非負(fù)約束條件(3)明確目標(biāo) 工廠的目標(biāo)是在各種設(shè)備能力允許的條件下，使

3、總利潤收入 1223zxx為最大 綜合起來，該問題的數(shù)學(xué)模型為：求一組變量 12,x x的值在滿足約束條件 的情況下，1212112221228 4 16x ,0 xxxxxx1223zxx 為最大 使利潤例例 運(yùn)輸問題運(yùn)輸問題 設(shè)有三個(gè)地方 l23A ,A ,A生產(chǎn)某種物資 簡稱為產(chǎn)地) (四個(gè)地方 l234B ,B ,B ,B需要該種物資 簡稱為銷地) 產(chǎn)地的產(chǎn)量和銷地的銷量以及問如何組織物資的運(yùn)輸，才能在滿足供需的條件下使總的運(yùn)費(fèi)最少產(chǎn)地到銷地的單位運(yùn)價(jià)表見表1(表1產(chǎn)銷運(yùn)輸表 例例 3 合理下料問題合理下料問題(后面詳述其解法后面詳述其解法) 某工廠生產(chǎn)某一種型號(hào)的機(jī)床，每臺(tái)機(jī)床上需要

4、2.9m，2.1m ，1.5m的軸分別為一根、二根、一根，這些軸需用同一種圓鋼制作，圓鋼的長度為7.4m，如果要生產(chǎn)100臺(tái)機(jī)床，問應(yīng)如何安排下料，才能使用料最省?7 例4、某工廠制造A.B兩種產(chǎn)品，制造A每噸需用煤9t，電力4kw，3個(gè)工作日；制造B每噸需用煤5t，電力5kw，10個(gè)工作日。已知制造產(chǎn)品A和B每噸分別獲利7000元和12000元，現(xiàn)工廠只有煤360t，電力200kw，工作日300個(gè)可以利用，問A、B兩種產(chǎn)品各應(yīng)生產(chǎn)多少噸才能獲利最大？解：設(shè) ,（單位為噸）分別表示A、B產(chǎn)品的計(jì)劃生產(chǎn)數(shù)； 1x2x f 表示利潤（單位千元） 則問題歸結(jié)為如下線性規(guī)劃問題：8目標(biāo)函數(shù) 21127

5、maxxxf約束條件 3605921 xx2005421 xx30010321xx. 0, 021xx 其中( , )為決策向量， 1x2x滿足約束條件的( , )稱為可行決策。 1x2x 線性規(guī)劃問題就是指目標(biāo)函數(shù)為諸決策變量的線性函數(shù)，給定的條件可用諸決策變量的線性等式或不等式表示的決策問題。線性規(guī)劃求解的有效方法是單純形法（進(jìn)一步了解可參考有關(guān)書籍），當(dāng)然簡單的問題也可用圖解法。 線性規(guī)劃的圖解法(解的幾何表示)： 對于只有兩個(gè)決策變量的線性規(guī)劃問題，可以二維直角坐標(biāo)平面上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。 圖解法求解線性規(guī)劃問題的步驟如下： (1)建立直角坐標(biāo)系： 分別取決策變量

6、x1 ,x2 為坐標(biāo)向量。 （2）繪制可行域： 對每個(gè)約束（包括非負(fù)約束）條件，作出其約束半平面（不等式）或約束直線（等式）。 各半平面與直線交出來的區(qū)域若存在，其中的點(diǎn)為此線性規(guī)劃的可行解。稱這個(gè)區(qū)域?yàn)榭尚屑蚩尚杏颉Ｈ缓筮M(jìn)行下步。否則若交為空，那么該線性規(guī)劃問題無可行解。 （3）繪制目標(biāo)函數(shù)等值線，并移動(dòng)求解： 目標(biāo)函數(shù)隨著取值不同，為一族相互平行的直線。 首先，任意給定目標(biāo)函數(shù)一個(gè)值，可作出一條目標(biāo)函數(shù)的等值線（直線）； 然后，確定該直線平移使函數(shù)值增加的方向； 最后，依照目標(biāo)的要求平移此直線。 結(jié)果 若目標(biāo)函數(shù)等值線能夠移動(dòng)到既與可行域有交點(diǎn)又達(dá)到最優(yōu)的位置，此目標(biāo)函數(shù)等值線與可行域的

7、交點(diǎn)即最優(yōu)解（一個(gè)或多個(gè)），此目標(biāo)函數(shù)的值即最優(yōu)值。 否則，目標(biāo)函數(shù)等值線與可行域?qū)⒔挥跓o窮遠(yuǎn)處，此時(shí)稱無有限最優(yōu)解。 Max z = 1500 x1 + 2500 x2 s.t. 3x1+ 2x2 65 (A) 2x1+ x2 40 (B) 3x2 75 (C) x1 , x2 0 (D, E)例題作圖（例題作圖（1 1）按照圖解法的步驟： （1）以決策變量x1 ，x2 為坐標(biāo)向量作平面直角坐標(biāo)系； （2 2）對每個(gè)約束（包括非負(fù)約束）條件）對每個(gè)約束（包括非負(fù)約束）條件作出直線（作出直線（A A、B B、C C、D D、E E），），并通過判斷并通過判斷確定不等式所決定的半平面。確定不等式

8、所決定的半平面。 各約束半平面交出來的區(qū)域即可行集或各約束半平面交出來的區(qū)域即可行集或可行域如下圖陰影所示?？尚杏蛉缦聢D陰影所示。 例題作圖（例題作圖（2 2） 第2步圖示(1) 分別作出各約束半平面X2 0 x1 03x2 753x1+ 2x2 65 2x1+ x2 40 例題作圖（例題作圖（3 3） 第2步圖示(2) 各約束半平面的交可行域 （3）任意給定目標(biāo)函數(shù)一個(gè)值（例如37500）作一條目標(biāo)函數(shù)的等值線，并確定該等值線平移后值增加的方向（向上移動(dòng)函數(shù)值增大），平移此目標(biāo)函數(shù)的等值線，使其達(dá)到既與可行域有交點(diǎn) 又 不 可 能 使 值 再 增 加 的 位 置 ， 得 到 交 點(diǎn) (5,2

9、5)T ，即最優(yōu)解。此目標(biāo)函數(shù)的值為70000。 例題作圖（例題作圖（4 4）w第3步圖示 作出目標(biāo)函數(shù)等值線函數(shù)值增大2.2.線性規(guī)劃的圖解法線性規(guī)劃的圖解法 例題作圖（例題作圖（5 5） 第3步圖示(2) 求出最優(yōu)解121一般線性規(guī)劃問題的數(shù)學(xué)表達(dá)式： nnxcxcxcf2211max(min) s.t 11212111),(bxaxaxann22222121),(bxaxaxannmnmnmmbxaxaxa),(22110,21nxxx 線性規(guī)劃問題可以用單純形方法求解，但是比較復(fù)雜，可以用常用的數(shù)學(xué)軟件如MATLAB，MATHEMATICA,LINGO等求解，這里只介紹用LINGO求解

10、的方法。當(dāng)你在windows下開始運(yùn)行LINGO系統(tǒng)時(shí)，會(huì)得到類似下面的一個(gè)窗口：外層是主框架窗口，包含了所有菜單命令和工具條，其它所有的窗口將被包含在主窗口之下。在主窗口內(nèi)的標(biāo)題為LINGO Model LINGO1的窗口是LINGO的默認(rèn)模型窗口，建立的模型都都要在該窗口內(nèi)編碼實(shí)現(xiàn)。 例例4 4 如何在LINGO中求解如下的LP問題：0,6002100350.32min212112121xxxxxxxtsxx在模型窗口中輸入如下代碼：min=2*x1+3*x2;x1+x2=350;x1=100;2*x1+x2=50 x2+2x4+x5+3x6=20 x3+x5+2x7=15endgin7求

11、解可以得到最優(yōu)解如下：30OBJECTIVE FUNCTION VALUE1) 27.00000VARIABLE VALUE REDUCED COST X1 0.000000 3.000000 X2 12.000000 1.000000 X3 0.000000 3.000000 X4 0.000000 3.000000 X5 15.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 3.000000 即按照模式2切割12根原料鋼管，按照模式5切割15根原料鋼管，共27根，總余料量為27m。 顯然，在總余料量最小的目標(biāo)下，最優(yōu)解將是使用余料盡可能小的

12、切割模式（模式2和5的余料為1 m），這會(huì)導(dǎo)致切割原料鋼管的總根數(shù)較多。31 2將（2）（5）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO求解，可以得到最優(yōu)解如下： OBJECTIVE FUNCTION VALUE1） 25.00000VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 15.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 5.000000 1.000000 X6 0.000000 1.000000 X7 5.000000 1.000000 即按

13、照模式2切割15根原料鋼管、按模式5切割5根、按模式7切割5根、共25根，可算出總余料量為35 m。 與上面得到的結(jié)果相比，總余料量增加了8 m，但是所用的原料鋼管的總根數(shù)減少了2根。 在余料沒有用途情況下，通常選擇總根數(shù)最小為目標(biāo)。 32問題（2）的求解 問題（2）：零售商如果采用的不同切割模式太多，將會(huì)導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外，該客戶除需要（1）中的三種鋼管外，還需要10根5 m的鋼管。應(yīng)如何下料最節(jié)省。問題分析 按照（1）的思路，可以通過枚舉法首先確定哪些切割模式是可行的。但由于需求的鋼管規(guī)格增加到4種，所以枚舉法

14、的工作量較大。 下面介紹的整數(shù)非線性規(guī)劃模型，可以同時(shí)確定切割模式和切割計(jì)劃，是帶有普遍性的方法。 33 同（1）類似，一個(gè)合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸（本題中為4 m），切割計(jì)劃中只使用合理的切割模式，而由于本題中參數(shù)都是整數(shù)，所以合理的切割模式的余量不能大于3 m。 此外，這里我們僅選擇總根數(shù)最小為目標(biāo)進(jìn)行求解。模型建立決策變量 由于不同切割模式不能超過3種， 可以用ix表示按照第i種模式（3, 2, 1i ）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。 34 設(shè)所使用的第i種切割模式下每根原料鋼管生產(chǎn)4 m，5 m，6 m和8 m的鋼管數(shù)量分別為iiii

15、rrrr4321,（非負(fù)整數(shù)）。 決策目標(biāo) 切割原料鋼管的總根數(shù)最小，目標(biāo)為)6(321xxxMin約束條件 為滿足客戶的需求，應(yīng)有)7(50313212111xrxrxr)8(10323222121xrxrxr)9(20333232131xrxrxr)10rxrxr35 每一種切割模式必須可行、合理，所以每根原料鋼管的成品量不能超過19m，也不能少于16 m（余量不能大于3 m），于是)11(1986541641312111rrrr)12(1986541642322212rrrr)13(1986541643332313rrrr模型求解 在（7）（10）式中出現(xiàn)決策變

16、量的乘積，是一個(gè)整數(shù)非線性規(guī)劃模型，雖然用LINGO軟件可以直接求解，但我們發(fā)現(xiàn)運(yùn)行很長時(shí)間也難以得到最優(yōu)解。 為了減少運(yùn)行時(shí)間，可以增加一些顯然的約束條件，從而縮小可行解的搜索范圍。 36 例如，由于3種切割模式的排列順序是無關(guān)緊要的，所以不妨增加以下約束)14(321xxx 又例如，我們注意到所需原料鋼管的總根數(shù)有著明顯的上界和下界。 首先，無論如何，原料鋼管的總根數(shù)不可能少于19158206105504根即至少需26根。 其次，考慮一種非常特殊的生產(chǎn)計(jì)劃： 第一種切割模式下只生產(chǎn)4m鋼管，一根原料鋼管切割成4根4 m鋼管，為滿足50根4 m鋼管的需求，需要13根原料鋼管； 37 第二種切

17、割模式下只生產(chǎn)5 m、6 m鋼管，一根原料鋼管切割成1根5 m鋼管和2根6 m鋼管，為滿足10根5 m和20根6 m鋼管的需求，需要10根原料鋼管； 第三種切割模式下只生產(chǎn)8 m鋼管，一根原料鋼管切割成2根8 m鋼管，為滿足15根8 m鋼管的需求，需要8根原料鋼管。 于是滿足要求的這種生產(chǎn)計(jì)劃共需13+10+8=31根原料鋼管，這就得到了最優(yōu)解的一個(gè)上界。 所以可增加以下約束)15(3126321xxx將（6）（15）構(gòu)成的模型輸入LINGO如下：38model：min=x1+x2+x3；x1*r11+x2*r12+x3*r13=50；x1*r21+x2*r22+x3*r23=10；x1*r3

18、1+x2*r32+x3*r33=20；x1*r41+x2*r42+x3*r43=15；4*r11+5*r21+6*r31+8*r41=19；4*r12+5*r22+6*r32+8*r42=19；4*r13+5*r23+6*r33+8*r43=16；4*r12+5*r22+6*r32+8*r42=16；4*r13+5*r23+6*r33+8*r43=16；x1+x2+x3=26；x1+x2+x3=x2；x2=x3；gin(x1) ；gin(x2) ；gin(x3) ；gin(r11) ；gin(r12) ；gin(r13) ；gin(r21) ；gin(r22) ；gin(r23) ；gin(r

19、31) ；gin(r32) ；gin(r33) ；gin(r41) ；gin(r42) ；gin(r43) ；end39Local optimal solution found at iteration： 12211Objective value： 28.00000 Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.00000 1.000000 R11 3.00000 0.000000 R12 2.00000 0.000000 R21 0.00000 0.000000 R22 1.00000 0

20、.000000 R31 1.00000 0.000000 R32 1.00000 0.000000 R33 0.00000 0.000000 R41 0.00000 0.000000 R42 0.00000 0.000000 R43 2.00000 0.00000040 即按照模式1，2，3分別切割10，10，8根原料鋼管，使用原料鋼管總根數(shù)為28根， 第一種切割模式下一根原料鋼管切割成3根4m鋼管和1根6 m鋼管； 第二種切割模式下一根原料鋼管切割成2根4 m鋼管、1根5 m鋼管和1根6 m鋼管； 第三種切割模式下一根原料鋼管切割成2根8 m鋼管。41二、非線性規(guī)劃模型非線性規(guī)劃模型的一般形

21、式為： )2(., 2 , 10)(.miXgtsi)3(., 2 , 10)(ljXhiDX 為為可可行行集集其其中中nTnRDxxxX,),(21 f(X)為目標(biāo)函數(shù)， (2)、(3)為約束條件， (2)為不等式約束，(3)為等式約束；若只有(1)稱為無約束問題。 ) 1 ()(minXf4232321213215),(minxxxxxxxxf如如0516223121xxxxx010312221xxxx 注：LINGO軟件用于求解非線性規(guī)劃（包括含有整數(shù)變量的），輸入總是以“model：”開始，以“end”結(jié)束；中間的語句必須以“；”分開。約束中“gin(x1)”表示x1為整數(shù)，其他類似（

22、如果要表示x1為0-1整數(shù)，應(yīng)該用“int(x1)”）。43例 容器的設(shè)計(jì)問題 某公司專門生產(chǎn)儲(chǔ)藏用容器，定貨合同要求該公司制造一種敞口的長方體容器，容積恰好為12立方米，該容器的底必須為正方形，容器總重量不超過68公斤。已知用作容器四壁的材料為每平方米10 元，重3公斤；用作容器底的材料每平方米20元，重2公斤。試問制造該容器所需的最小費(fèi)用是多少？ 模型建立 設(shè)該容器底邊長和高分別為 米、 米， 1x2x則問題的數(shù)學(xué)模型為 21212040)(minxxxXf（容器的費(fèi)用） . 0, 0,68212,12. .212121221xxxxxxxts（容器重量）（容器重量）（容器體積）（容器體積

23、）44一般來說，非線性規(guī)劃模型的求解要比線性規(guī)劃模型求解困難得多，雖然現(xiàn)在已經(jīng)發(fā)展了許多非線性規(guī)劃的算法，但到目前為止，還不象線性規(guī)劃那樣有通用的單純形算法，而是各種算法都有自己特定的適用范圍，如求解法有：最速下降法、牛頓法、可行方向法、懲罰函數(shù)法等。盡管如此，非線性規(guī)劃的實(shí)際應(yīng)用還是相當(dāng)廣泛的。45 實(shí)際問題中的優(yōu)化模型一、投資策略(了解) 某部門現(xiàn)有資金10萬元，五年內(nèi)有以下投資項(xiàng)目供選擇： 項(xiàng)目A,從第一年到第四年每年初投資，次年末收回本金且獲利15%； 項(xiàng)目B，第三年初投資，第五年末收回本金且獲利25%，最大投資額為4萬元； 項(xiàng)目C，第二年初投資，第五年末收回本金且獲利40%，最大投資

24、額為3萬元； 項(xiàng)目D，每年初投資，年末收回本金且獲利6%。問如何確定投資策略使第五年末本息總額最大。46問題的目標(biāo)函數(shù)是第五年末的本息總額， 決策變量是每年初各個(gè)項(xiàng)目的投資額， 約束條件是每年初擁有的資金。 用ijx表示第i年初（5 , , 2 , 1i）項(xiàng)目4 , 3 , 2 , 1(jj分別代表A,B,C,D)的投資額， 根據(jù)所給條件只有下表1列出的ijx才是需要求解的。 項(xiàng)目 年份 A B C D 1 2 3 4 5 11x21x31x41x32x23x14x24x34x44x54x47 因?yàn)轫?xiàng)目D 每年初可以投資，且年末能收回本息，所以每年初都應(yīng)把資金全部投出去， 項(xiàng)目A,從第一年到第

25、四年每年初投資，次年末收回本金且獲利15%； 項(xiàng)目B，第三年初投資，第五年末收回本金且獲利25%，最大投資額為4萬元； 項(xiàng)目C，第二年初投資，第五年末收回本金且獲利40%，最大投資額為3萬元； 項(xiàng)目D，每年初投資，年末收回本金且獲利6%。由此可得如下的約束條件： 第一年初： 101411 xx第二年初： 1424232106. 1xxxx第三年初 241134323106. 115. 1xxxxx第四年初： 3421444106. 115. 1xxxx第五年初： 44315406. 115. 1xxx項(xiàng)目B,C對投資額的限制： 3, 42332xx48 項(xiàng)目項(xiàng)目A,A,從第一年到第四年每年初投

26、資，次年末收回本金且從第一年到第四年每年初投資，次年末收回本金且獲利獲利15%15%； 項(xiàng)目項(xiàng)目B B，第三年初投資，第五年末收回本金且獲利，第三年初投資，第五年末收回本金且獲利25%25%，最，最大投資額為大投資額為4 4萬元；萬元； 項(xiàng)目項(xiàng)目C C，第二年初投資，第五年末收回本金且獲利，第二年初投資，第五年末收回本金且獲利40%40%，最，最大投資額為大投資額為3 3萬元；萬元； 項(xiàng)目項(xiàng)目D D，每年初投資，年末收回本金且獲利，每年初投資，年末收回本金且獲利6%6%。 每項(xiàng)投資應(yīng)為非負(fù)的每項(xiàng)投資應(yīng)為非負(fù)的： 0ijx第五年末本息總額為第五年末本息總額為5432234106. 125. 14

27、0. 115. 1xxxxz將上條件等價(jià)變形如1424232106. 1xxxx006. 124232114xxxx49由此得投資問題的線性規(guī)劃模型如下：5432234106. 125. 140. 115. 1maxxxxxzs.t. 101411 xx006. 124232114xxxx006. 115.xxxx006. 115, 144413421xxxx006. 115. 1544431xxx3, 42332xx0ijx50求解得4008. 0, 0,000. 3,5436. 3,1732. 6,8268. 3312423211411xxxxxx4609. 0,

28、 0,0752. 4, 0,0000. 45444413432xxxxx3750.14z 即即第第1年項(xiàng)目年項(xiàng)目A,D分別投資分別投資3.8268和和6.1732(萬元萬元)；第第2年項(xiàng)目年項(xiàng)目A,C分別投資分別投資3.5436和和3(萬元萬元)；第第3年項(xiàng)目年項(xiàng)目A,B分別投資分別投資0.4008和和4(萬元萬元)；第第4年項(xiàng)目年項(xiàng)目A投資投資4.0752(萬元萬元)；第第5年項(xiàng)目年項(xiàng)目D投資投資0.4609(萬元萬元)；5年后總資金年后總資金 14。375萬元，即盈利萬元，即盈利43.75%.51二、貨機(jī)裝運(yùn)（了解）問題 某架貨機(jī)有三個(gè)貨艙：前倉、中倉、后倉。三個(gè)貨艙所能裝載的貨物的最大重

29、量和體積都有限制，如表3所示。并且，為了保持飛機(jī)的平衡，三個(gè)貨艙中實(shí)際裝載貨物的重量必須與其最大容許重量成比例。前倉中倉后倉重量限制（噸）10168體積限制（米3）680087005300 現(xiàn)有四類貨物供該貨機(jī)本次飛行裝運(yùn)，其有關(guān)信息如表4，最后一列指裝運(yùn)后所獲得的利潤。52重量（噸）空間（米3/噸）利潤（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物4123902850應(yīng)如何安排裝運(yùn)，使該貨機(jī)本次飛行獲利最大？模型假設(shè) 問題中沒有對貨物裝運(yùn)提出其它要求，我們可作如下假設(shè)： 1）每種貨物可以分割到任意小； 2）每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；533

30、）多種貨物可以混裝，并保證不留空隙。 模型建立 決策變量： ijx表示第i種貨物裝入第j個(gè)貨艙的重量（噸）， 貨艙j=1,2,3分別表示前倉、中倉、后倉。 決策目標(biāo)是最大化總利潤，即)(3800)(3100232221131211xxxxxxZMax)(2850)(3500434241333231xxxxxx)13(約束條件包括以下4個(gè)方面：1）從裝載的四種貨物的總重量約束，即)14(18131211xxx54)15(15232221xxx)16(23333231xxx)17(12434241xxx2）三個(gè)貨艙的重量限制，即)18(1041312111xxxx)19(1642322212xxx

31、x)20(843332313xxxx3）三個(gè)貨艙的空間限制，即)21(680039058065048041312111xxxx122232424806505803908700(22)xxxx132333434806505803905300(23)xxxx554）三個(gè)貨艙裝入重量的平衡約束，即)24(81610433323134232221241312111xxxxxxxxxxxx模型求解 將以上模型輸入LINDO求解，可以得到：56OBJECTIVE FUNCTION VALUE1) 121515.8VARIABLE VALUE REDUCED COSTX11 0.000000 400.000

32、000X12 0.000000 57.894737X13 0.000000 400.000000X21 10.000000 0.000000X22 0.000000 239.473679X23 5.000000 0.000000X31 0.000000 0.000000X32 12.947369 0.000000X33 3.000000 0.000000X41 0.000000 650.000000X42 3.052632 0.000000X43 0.000000 650.000000實(shí)際上，不妨將所得最優(yōu)解作四舍五入， 57結(jié)果為 貨物2裝入前倉10噸、裝入后倉5噸； 貨物3裝入中倉13噸、裝入后倉3噸； 貨物4裝入中倉3噸， 最大利潤約121516元。 評(píng)注 初步看來，本例與運(yùn)輸問題類似，似乎可以把4種貨物看成4個(gè)供應(yīng)點(diǎn)，3個(gè)貨艙看成3個(gè)需求點(diǎn)（或者反過來，把貨艙看成供應(yīng)點(diǎn)，貨物看成需求點(diǎn)）。但是，這里對供需量的限制包括兩個(gè)方面：重量限制和空間限制，且有裝載均勻要求，因此它只能看成是運(yùn)輸問題的一種變形和擴(kuò)展。 58 例 某工廠制造A.B兩種產(chǎn)品，制造A每噸需用煤9t，電力4kw，3個(gè)工作日；制造B每噸需用煤5t，電力5kw，10個(gè)工作日。已知制造產(chǎn)品A和B每噸分別獲利7000元和12000元，現(xiàn)工廠只有煤360t，電力200kw，工作日300個(gè)可以利用，問A、B