《管理運(yùn)籌學(xué)》(第二版)課后習(xí)題參考答案

1、學(xué)習(xí)幫手學(xué)習(xí)幫手管理運(yùn)籌學(xué)（第二版）課后習(xí)題參考答案第1章線性規(guī)劃（復(fù)習(xí)思考題）1什么是線性規(guī)劃？線性規(guī)劃的三要素是什么？答：線性規(guī)劃（LinearProgramming,LP）是運(yùn)籌學(xué)中最成熟的一個(gè)分支,并且是應(yīng)用最廣泛的一個(gè)運(yùn)籌學(xué)分支。線性規(guī)劃屬于規(guī)劃論中的靜態(tài)規(guī)劃，是一種重要的優(yōu)化工具，能夠解決有限資源的最佳分配問題。建立線性規(guī)劃問題要具備三要素：決策變量、約束條件、目標(biāo)函數(shù)。決策變量是決策問題待定的量值，取值一般為非負(fù)；約束條件是指決策變量取值時(shí)受到的各種資源條件的限制，保障決策方案的可行性；目標(biāo)函數(shù)是決策者希望實(shí)現(xiàn)的目標(biāo)，為決策變量的線性函數(shù)表達(dá)式，有的目標(biāo)要實(shí)現(xiàn)極大值，有的則要求極

2、小值。2求解線性規(guī)劃問題時(shí)可能出現(xiàn)幾種結(jié)果，哪種結(jié)果說明建模時(shí)有錯(cuò)誤？答：（1）唯一最優(yōu)解：只有一個(gè)最優(yōu)點(diǎn)；（2）多重最優(yōu)解：無窮多個(gè)最優(yōu)解；（3）無界解：可行域無界，目標(biāo)值無限增大；（4）沒有可行解：線性規(guī)劃問題的可行域是空集。當(dāng)無界解和沒有可行解時(shí)，可能是建模時(shí)有錯(cuò)。3什么是線性規(guī)劃的標(biāo)準(zhǔn)型？松弛變量和剩余變量的管理含義是什么？答：線性規(guī)劃的標(biāo)準(zhǔn)型是：目標(biāo)函數(shù)極大化，約束條件為等式，右端常數(shù)項(xiàng)b0，決策變量滿足非負(fù)性。i如果加入的這個(gè)非負(fù)變量取值為非零的話，則說明該約束限定沒有約束力，對(duì)企業(yè)來說不是緊缺資源,所以稱為松弛變量；剩余變量取值為非零的話,則說明“V型約束的左邊取值大于右邊規(guī)劃值

3、，出現(xiàn)剩余量。4試述線性規(guī)劃問題的可行解、基礎(chǔ)解、基可行解、最優(yōu)解的概念及其相互關(guān)系。答：可行解：滿足約束條件AX二b,X0的解,稱為可行解?；尚薪猓簼M足非負(fù)性約束的基解，稱為基可行解?？尚谢簩?duì)應(yīng)于基可行解的基，稱為可行基。最優(yōu)解：使目標(biāo)函數(shù)最優(yōu)的可行解，稱為最優(yōu)解。最優(yōu)基：最優(yōu)解對(duì)應(yīng)的基矩陣，稱為最優(yōu)基。它們的相互關(guān)系如右圖所示：5用表格單純形法求解如下線性規(guī)劃。maxZ=4x+x+2x1238x+3x+x2十123匸6x+x+x0123解：標(biāo)準(zhǔn)化maxZ=4x+x+2xTOC o 1-5 h z1238x+3x+x+x=21234012345oj0-1/23/2-1/202x28311

4、00 x6-2-20-11oj-12-50-20故最優(yōu)解為X*二(0,0,2,0,6)T,即X二0,x二0,x二2，此時(shí)最優(yōu)值為Z(X*)=4.1236表115中給出了求極大化問題的單純形表，問表中a,a,c,c,d為何值及變1212量屬于哪一類型時(shí)有：(1)表中解為唯一最優(yōu)解；(2)表中解為無窮多最優(yōu)解之一;(3)下一步迭代將以x代替基變量x；(4)該線性規(guī)劃問題具有無界解；(5)15該線性規(guī)劃問題無可行解。12d0,c0,c0,a0,；i24a2(4)c0,a;或者x為人工變114a22量，且c為包含M的大于零的數(shù),a0,d0.21學(xué)習(xí)幫手學(xué)習(xí)幫手142學(xué)習(xí)幫手142學(xué)習(xí)幫手7用大M法求解

5、如下線性規(guī)劃。maxZ=5x+3x+6x123x+2x+x18123s十2x+x+3x16s.l.0123解：加入人工變量，進(jìn)行人造基后的數(shù)學(xué)模型如下：maxZ=5x+3x+6x+0 x+0 x一Mx123456x+2x+x+x=1812342x+x+3x+x=161235x+x+x+x=101236x0(i=1,2,6)s.t.i列出單純形表536001816103918161039i18/116/310/16+6+M38/316/314/31/35/301-1/3038/316/314/31/35/301-1/302/31/3101/301/32/300-1/3138/51614/21+1

6、M31+-M300-2-1M30-1/20011/2-5/21/20101/2-1/21/2100-1/23/26j1/2000-3/2-3-M20 x4400111-35x1610201-13x2401-10-12j00-10-2-1-M故最優(yōu)解為X*二(6,4,0,4,0,0)T,即X二6,x二4,x二0,此時(shí)最優(yōu)值為123Z(X*)=42.8.A,B,C三個(gè)城市每年需分別供應(yīng)電力320,250和350單位，由I,II兩個(gè)電站提供，它們的最大可供電量分別為400單位和450單位，單位費(fèi)用如表116所示。由于需要量大于可供量,決定城市A的供應(yīng)量可減少030單位,城市B的供應(yīng)量不變,城市C的供

7、應(yīng)量不能少于270單位。試建立線性規(guī)劃模型,求將可供電量用完的最低總費(fèi)用分配方案。表116單位電力輸電費(fèi)(單位：元)城市A城市AI15II21BC18222516ij解：設(shè)x為“第i電站向第j城市分配的電量”(i=1,2;j=1,2,3),建立模型如下：ij+21x+25x+16x212223maxZ=+21x+25x+16x212223111213x+x+x=400111213x+x+x=450s.ts.t.2223x+x2901121x+x2701323x+x0,i=1,2;j=1,2,3ij9.某公司在3年的計(jì)劃期內(nèi)，有4個(gè)建設(shè)項(xiàng)目可以投資：項(xiàng)目I從第一年到第三年年初都可以投資。預(yù)計(jì)每年

8、年初投資，年末可收回本利120%，每年又可以重新將所獲本利納入投資計(jì)劃；項(xiàng)目II需要在第一年初投資,經(jīng)過兩年可收回本利150%,又可以重新將所獲本利納入投資計(jì)劃，但用于該項(xiàng)目的最大投資不得超過20萬元；項(xiàng)目III需要在第二年年初投資，經(jīng)過兩年可收回本利160%，但用于該項(xiàng)目的最大投資不得超過15萬元；項(xiàng)目IV需要在第三年年初投資,年末可收回本利140%，但用于該項(xiàng)目的最大投資不得超過10萬元。在這個(gè)計(jì)劃期內(nèi)，該公司第一年可供投資的資金有30萬元。問怎樣的投資方案，才能使該公司在這個(gè)計(jì)劃期獲得最大利潤？解：設(shè)x表示第一次投資項(xiàng)目i,設(shè)x表示第二次投資項(xiàng)目i,設(shè)x表示第三次iii投資項(xiàng)目i，(i=

9、1,2,3,4)，則建立的線性規(guī)劃模型為maxZ=1.2x+1.6x+1.4x134x(i)+x(i)3012x(2)+x(1)1.2x(1)+30 x(1)x(1)13112x+x(1)=1.2x(2)+1.5x(1)+1.2x(1)+30 xxx(2)xX141211213t.x(1)202x(1)153x(1)0,i=1,2,3,4iii通過LINGO軟件計(jì)算得：x(1)=10,x(1)=20,x(1)=0,x(2)=12,x=44.1231110.某家具制造廠生產(chǎn)五種不同規(guī)格的家具。每種家具都要經(jīng)過機(jī)械成型、打磨、上漆幾道重要工序。每種家具的每道工序所用的時(shí)間、每道工序的可用時(shí)間、每種

10、家具的利潤由表117給出。問工廠應(yīng)如何安排生產(chǎn)，使總利潤最大？表117家具生產(chǎn)工藝耗時(shí)和利潤表生產(chǎn)工序所需時(shí)間(小時(shí))每道工序可用12345時(shí)間(小時(shí))成型346233600打磨435643950上漆233432800利潤（百元）2.734.52.53解：設(shè)x表示第i種規(guī)格的家具的生產(chǎn)量（i=1,2,5）,則imaxZ=2.7x+3x+4.5x+2.5x+3xTOC o 1-5 h z123453x+4x+6x+2x+3x360012345s十4x+3x+5x+6x+4x3950123452x+3x+3x+4x+3x0,i=1,2,5i通過LINGO軟件計(jì)算得：x=0,x=3&x=254,x=

11、0,x=642,Z=3181.1234511某廠生產(chǎn)甲、乙、丙三種產(chǎn)品，分別經(jīng)過A，B，C三種設(shè)備加工。已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)數(shù)、設(shè)備的現(xiàn)有加工能力及每件產(chǎn)品的利潤如表210所示。表118產(chǎn)品生產(chǎn)工藝消耗系數(shù)甲乙丙設(shè)備能力A（小時(shí)）111100B（小時(shí)）1045600C（小時(shí)）226300單位產(chǎn)品利潤（元）1064（1）建立線性規(guī)劃模型，求該廠獲利最大的生產(chǎn)計(jì)劃。（2）產(chǎn)品丙每件的利潤增加到多大時(shí)才值得安排生產(chǎn)？如產(chǎn)品丙每件的利潤增加到6，求最優(yōu)生產(chǎn)計(jì)劃。3)產(chǎn)品甲的利潤在多大范圍內(nèi)變化時(shí)，原最優(yōu)計(jì)劃保持不變？(4)設(shè)備A的能力如為100+10q,確定保持原最優(yōu)基不變的q的變化范圍。5

12、)如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品丙，試確定最優(yōu)計(jì)劃的變化。解：（1）設(shè)x,x,x分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量,建立線性規(guī)劃模型123maxZ=10 x+6x+4x123x+x+x100123十10 x+4x+5x600sl1232x+2x+6x0123標(biāo)準(zhǔn)化得maxZ=10 x+6x+4x+0 x+0 x+0 x123456x+x+x+x=1001234stV10 x+4x+5x+x=60012352x+2x+6x+x=3001236x,x,x,x,x,x0123456列出單純形表cj10640009CBXBbx1x2x3x4x5x6i0 x41001111001000 x56001045

13、010600 x6300226001150j10640000 x44003/51/211/100200/310 x16012/51/201/1001500 x618006/550-1/51150cj02-10-106x2200/3015/65/3-1/6010 x1100/3101/6-2/31/600 x6100004-201c00-10/3-2/30j8/3故最優(yōu)解為x二100/3,x二200/3,x二0,又由于x,x,x取整數(shù),故四舍五入可123123得最優(yōu)解為x=33,x=67,x=0,Z=732.123max（2）產(chǎn)品丙的利潤c變化的單純形法迭代表如下：3cj106c30009CBX

14、Bbx1x2x3x4x5x6i6x2200/3015/65/3-1/6010 x1100/3101/6-2/31/600 x6100004-201cj00c-320/3-10/3-2/30202要使原最優(yōu)計(jì)劃保持不變，只要，3=C3-丁冬0，即于6367故當(dāng)產(chǎn)品丙每件的利潤增加到大于6.67時(shí)，才值得安排生產(chǎn)。如產(chǎn)品丙每件的利潤增加到6時(shí)，此時(shí)66.67，故原最優(yōu)計(jì)劃不變。（3）由最末單純形表計(jì)算出121c=一1一一c0,c=一10+c0,c二1一一c0,361431561解得6c、300丿3、3(100-20q)丿-20X=B-_1W=B解得-4q5，故要保持原最優(yōu)基不變的q的變化范圍為-4

15、,5.(5)如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品丙，則線性規(guī)劃模型變成maxZ=10 x+6x+4x123x+x+x100TOC o 1-5 h z123s.t.10 x+4x+5s.t.1232x+2x+6x103x,x,x0123通過LINGO軟件計(jì)算得到：x=32,x=58,x=10,Z=708123第2章對(duì)偶規(guī)劃(復(fù)習(xí)思考題)1對(duì)偶問題和對(duì)偶向量(即影子價(jià)值)的經(jīng)濟(jì)意義是什么？答：原問題和對(duì)偶問題從不同的角度來分析同一個(gè)問題，前者從產(chǎn)品產(chǎn)量的角度來考察利潤，后者則從形成產(chǎn)品本身所需要的各種資源的角度來考察利潤，即利潤是產(chǎn)品生產(chǎn)帶來的，同時(shí)又是資源消耗帶來的。對(duì)偶變量的值y表示第i種資源的邊

16、際價(jià)值,稱為影子價(jià)值?？梢园褜?duì)偶問題的解iY定義為每增加一個(gè)單位的資源引起的目標(biāo)函數(shù)值的增量。2什么是資源的影子價(jià)格？它與相應(yīng)的市場(chǎng)價(jià)格有什么區(qū)別？答：若以產(chǎn)值為目標(biāo),則y是增加單位資源i對(duì)產(chǎn)值的貢獻(xiàn),稱為資源的影子價(jià)格i(ShadowPrice)。即有“影子價(jià)格=資源成本+影子利潤”。因?yàn)樗⒉皇琴Y源的實(shí)際價(jià)格，而是企業(yè)內(nèi)部資源的配比價(jià)格，是由企業(yè)內(nèi)部資源的配置狀況來決定的，并不是由市場(chǎng)來決定，所以叫影子價(jià)格。可以將資源的市場(chǎng)價(jià)格與影子價(jià)格進(jìn)行比較，當(dāng)市場(chǎng)價(jià)格小于影子價(jià)格時(shí)，企業(yè)可以購進(jìn)相應(yīng)資源，儲(chǔ)備或者投入生產(chǎn)；當(dāng)市場(chǎng)價(jià)格大于影子價(jià)格時(shí)，企業(yè)可以考慮暫不購進(jìn)資源，減少不必要的損失。3如何根

17、據(jù)原問題和對(duì)偶問題之間的對(duì)應(yīng)關(guān)系，找出兩個(gè)問題變量之間、解及檢驗(yàn)數(shù)之間的關(guān)系？答：(1)最優(yōu)性定理：設(shè)X,Y分別為原問題和對(duì)偶問題的可行解,且CX=bTY,則X,Y分別為各自的最優(yōu)解。(2)對(duì)偶性定理：若原問題有最優(yōu)解，那么對(duì)偶問題也有最優(yōu)解，而且兩者的目標(biāo)函數(shù)值相等。(3)互補(bǔ)松弛性：原問題和對(duì)偶問題的松弛變量為x和Y,它們的可行解SSX*,Y*為最優(yōu)解的充分必要條件是Y*X=0,YX*=0-SS(4)對(duì)偶問題的最優(yōu)解對(duì)應(yīng)于原問題最優(yōu)單純形表中，初始基變量的檢驗(yàn)數(shù)的負(fù)值。若-Y對(duì)應(yīng)于原問題決策變量X的檢驗(yàn)數(shù),則-Y對(duì)應(yīng)于原問題松弛變量x的檢驗(yàn)SS數(shù)。4已知線性規(guī)劃問題maxZ=4x+x+2x

18、1238x+3x+x2(第一種資源)123stI6x+x+x0123(1)求出該問題產(chǎn)值最大的最優(yōu)解和最優(yōu)值。(2)求出該問題的對(duì)偶問題的最優(yōu)解和最優(yōu)值。(3)給出兩種資源的影子價(jià)格，并說明其經(jīng)濟(jì)含義；第一種資源限量由2變?yōu)?，最優(yōu)解是否改變？.學(xué)習(xí)幫手.學(xué)習(xí)幫手學(xué)習(xí)幫手（4）代加工產(chǎn)品丁，每單位產(chǎn)品需消耗第一種資源2單位，消耗第二種資源3單位，應(yīng)該如何定價(jià)？解：（1）標(biāo)準(zhǔn)化，并列出初始單純形表cj412009CBXBbxxxxxi0 x42831102/80 x58611018/6oj412004x1/413/81/81/8020 x13/26-5/41/4-3/4126oj0-1/23/2

19、-1/202x32831100 x56-2-20-11oj-12-50-20由最末單純性表可知，該問題的最優(yōu)解為：X*二（0,020,6）t，即x=0,x=0,x=2,最優(yōu)值為Z=4.123（2）由原問題的最末單純形表可知，對(duì)偶問題的最優(yōu)解和最優(yōu)值為：y=2,y=0,w=4.12（3）兩種資源的影子價(jià)格分別為2、0，表示對(duì)產(chǎn)值貢獻(xiàn)的大小；第一種資源限量由2變?yōu)?，最優(yōu)解不會(huì)改變。（4）代加工產(chǎn)品丁的價(jià)格不低于2x2+0 x3=4.5.某廠生產(chǎn)A，B，C，D4種產(chǎn)品，有關(guān)資料如表26所示。表26資源消耗資源、產(chǎn)品資源供應(yīng)量（公斤）原料成本（元公斤）ABCD甲23128002.0乙54341200

20、1.0丙345310001.5單位產(chǎn)品售價(jià)（元）14.52115.516.51）請(qǐng)構(gòu)造使該廠獲利潤最大的線性規(guī)劃模型，并用單純形法求解該問題（不計(jì)加工成本）。2）該廠若出租資源給另一個(gè)工廠，構(gòu)成原問題的對(duì)偶問題，列出對(duì)偶問題的數(shù)學(xué)模型，資源甲、乙、丙的影子價(jià)格是多少？若工廠可在市場(chǎng)上買到原料丙，工廠是否應(yīng)該購進(jìn)該原料以擴(kuò)大生產(chǎn)？3）原料丙可利用量在多大范圍內(nèi)變化，原最優(yōu)生產(chǎn)方案中生產(chǎn)產(chǎn)品的品種不變即最優(yōu)基不變）？（4）若產(chǎn)品B的價(jià)格下降了0.5元,生產(chǎn)計(jì)劃是否需要調(diào)整？解：（1）設(shè)x,x,x,x分別表示甲、乙、丙產(chǎn)品的生產(chǎn)量，建立線性規(guī)劃模型1234maxZ=x+5x+3x+4x12342x+

21、3x+x+2x800TOC o 1-5 h z1234十5x+4x+3x+4x1200 HYPERLINK l bookmark34 o Current Document sl12343x+4x+5x+3x0,i=1,2,3,4i初始單純形表c15340009jiCBXBbx1x2x3x4x5x6x70 x58002312100800/30 x6120054340101200/40 x7100034530011000/4j1534000最末單純形表cj15340009iCBXBbx1x2x3x4x5x6x70 x51001/40-13/4011/4-14x420020-2101-15x2100

22、-3/4111/400-3/41j-13/40-11/400-1/4-1解得最優(yōu)解為：X*二(0,100,0,200,100)T,最優(yōu)值Z=1300.2）原問題的對(duì)偶問題的數(shù)學(xué)模型為minw=800y+1200y+1000y1232y+5y+3y1TOC o 1-5 h z1233y+4y+4y5.123sL彳y+3y+5y11232y+4y+3y4123y,y,y0123解得影子價(jià)格分別為2、125、25。對(duì)比市場(chǎng)價(jià)格和影子價(jià)格，當(dāng)市場(chǎng)價(jià)低于影子價(jià)格時(shí)購進(jìn)。3）原料丙可利用量在900,1100范圍內(nèi)變化，原最優(yōu)生產(chǎn)方案中生產(chǎn)產(chǎn)品的品種不變（即最優(yōu)基不變）。（4）若產(chǎn)品B的價(jià)格下降了0.5元,

23、生產(chǎn)計(jì)劃不需要調(diào)整。學(xué)習(xí)幫手學(xué)習(xí)幫手20 x1學(xué)習(xí)幫手20 x1學(xué)習(xí)幫手6某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，產(chǎn)品生產(chǎn)的工藝路線如圖21所示，試統(tǒng)計(jì)單位產(chǎn)品的設(shè)備工時(shí)消耗,填入表27。又已知材料、設(shè)備C和設(shè)備D等資源的單位成本和擁有量如表27所示。表27資源消耗與資源成本表產(chǎn)品資源、資源消耗資源成本資源擁有量甲乙元/單位資源材料（公斤）60502004200設(shè)備C（小時(shí)）3040103000設(shè)備D（小時(shí)）6050204500據(jù)市場(chǎng)分析，甲、乙產(chǎn)品銷售價(jià)格分別為13700元和11640元，試確定獲利最大的產(chǎn)品生產(chǎn)計(jì)劃。（D設(shè)產(chǎn)品甲的計(jì)劃生產(chǎn)量為x，產(chǎn)品乙的計(jì)劃生產(chǎn)量為x,試建立其線性規(guī)劃12的數(shù)學(xué)模型；若

24、將材料約束加上松弛變量x，設(shè)備C約束加上松弛變量x，設(shè)備D約34束加上松弛變量x，試化成標(biāo)準(zhǔn)型。5（2）利用LINDO軟件求得：最優(yōu)目標(biāo)函數(shù)值為18400，變量的最優(yōu)取值分別為x=20,x=60,x=0,x=0,x=300,則產(chǎn)品的最優(yōu)生產(chǎn)計(jì)劃方案是什么？并解釋12345x二0,x二0,x二300的經(jīng)濟(jì)意義。345（3）利用LINDO軟件對(duì)價(jià)值系數(shù)進(jìn)行敏感性分析,結(jié)果如下：ObjCoefficientRangesVariableCurrentCoefVariableCurrentCoefAllowableIncrease20088AllowableDecreasex24026.6773.33試

25、問如果生產(chǎn)計(jì)劃執(zhí)行過程中，甲產(chǎn)品售價(jià)上升到13800元，或者乙產(chǎn)品售價(jià)降低60元，所制定的生產(chǎn)計(jì)劃是否需要進(jìn)行調(diào)整？(4)利用LINDO軟件對(duì)資源向量進(jìn)行敏感性分析,結(jié)果如下：RighthandSideRangesResourceCurrentRhsAllowableIncreaseAllowableDecrease材料4200300450設(shè)備C3000360900設(shè)備D4500Infinity300試問非緊缺資源最多可以減少到多少，而緊缺資源最多可以增加到多少？解：(1)建立的線性規(guī)劃模型為maxZ=200 x+240 x1260 x+50 x420012s十30 x+40 x3000s.l

26、.21260 x+50 x012將其標(biāo)準(zhǔn)化maxZ=200 x+240 x1260 x+50 x+x=4200TOC o 1-5 h z123c十30 x+40 x+x=3000s.t.212460 x+50 x+x=4500125x0,i=1,2,5i(2)甲生產(chǎn)20件,乙生產(chǎn)60件,材料和設(shè)備C充分利用,設(shè)備D剩余600單位。(3)甲上升到13800需要調(diào)整，乙下降60不用調(diào)整（4）非緊缺資源設(shè)備D最多可以減少到300，而緊缺資源材料最多可以增加到300,緊缺資源一設(shè)備C最多可以增加到360。第3章整數(shù)規(guī)劃（復(fù)習(xí)思考題）1整數(shù)規(guī)劃的類型有哪些？答：純整數(shù)規(guī)劃、0-1規(guī)劃和混合整數(shù)規(guī)劃。2試

27、述整數(shù)規(guī)劃分枝定界法的思路。答：（1）首先不考慮整數(shù)條件，求解整數(shù)規(guī)劃相應(yīng)的線性規(guī)劃問題。若相應(yīng)的線性規(guī)劃問題沒有可行解，停止計(jì)算，這時(shí)原整數(shù)規(guī)劃也沒有可行解。（2）定界過程。對(duì)于極大化的整數(shù)規(guī)劃問題，當(dāng)前所有未分枝子問題中最大的目標(biāo)函數(shù)值為整數(shù)規(guī)劃問題上界；在滿足整數(shù)約束的子問題的解中，最大的目標(biāo)函數(shù)值為整數(shù)規(guī)劃問題的下界。當(dāng)上下界相同時(shí)，則已得最優(yōu)解；否則，轉(zhuǎn)入剪枝過程。（3）剪枝過程。在下述情況下剪除這些分枝：若某一子問題相應(yīng)的線性規(guī)劃問題無可行解：在分枝過程中,求解某一線性規(guī)劃所得到的目標(biāo)函數(shù)值Z不優(yōu)于現(xiàn)有下界。（4）分枝過程。當(dāng)有多個(gè)待求分枝時(shí)，應(yīng)先選取目標(biāo)函數(shù)值最優(yōu)的分枝繼續(xù)進(jìn)行分

28、枝。選取一個(gè)不符合整數(shù)條件的變量x作為分枝變量,若x的值是b*,構(gòu)造兩個(gè)新iii的約束條件：xb*+1,分別并入相應(yīng)的數(shù)學(xué)模型中,構(gòu)成兩個(gè)子問題。iii對(duì)任一個(gè)子問題，轉(zhuǎn)步驟（1）3試用分枝定界法求如下線性規(guī)劃：maxZ=40 x+90 x129x+7x5612cx7x+20 x70Sl012x,x取整數(shù)12解：最優(yōu)整數(shù)解為：丿:=4,x=2Z=340.空應(yīng)=凹牛癥空11:匕界:1314有4最優(yōu)整數(shù)解為：丿:=4,x=2Z=340.空應(yīng)=凹牛癥空11:匕界:1314有4名職工,人的能力不同，每個(gè)人做各項(xiàng)工作所用的時(shí)間不同,所花費(fèi)時(shí)間如表37所示。A=5,12=1：表37（單，位：分鐘）匕界:3

29、49下界*34117任務(wù)xi=43j1=2.z=340人員上界:340問指派哪個(gè)人去完成哪項(xiàng)工作，可使總的消耗時(shí)間最少？解:設(shè)xj=0，任務(wù):不由人完完成，霸為個(gè)人i對(duì)于任務(wù)j的時(shí)間耗費(fèi)矩陣，則建立整數(shù)規(guī)劃模型為：minZ二茲xtijiji=1j=1工X=1ijS.t.5014567x+x+x+x+x5012567x+x+x+x+x5012367x+x+x+x+x50123478012345x+x+x+x+x9023456x+x+x+x+x9034567s.t.x0,i=1,2,7ix取整數(shù),i=1,2,7i解得：x=0,x=4,x=32,x=10,x=34,x=10,x=4,Z=942345

30、67第4章目標(biāo)規(guī)劃（復(fù)習(xí)思考題）1.某計(jì)算機(jī)公司生產(chǎn)A,B,C三種型號(hào)的筆記本電腦。這三種筆記本電腦需要在復(fù)雜的裝配線上生產(chǎn),生產(chǎn)一臺(tái)A,B,C型號(hào)的筆記本電腦分別需要5小時(shí)、8小時(shí)、12小時(shí)。公司裝配線正常的生產(chǎn)時(shí)間是每月1700小時(shí),公司營業(yè)部門估計(jì)A,B,C三種筆記本電腦每臺(tái)的利潤分別是1000元、1440元、2520元，而且公司預(yù)測(cè)這個(gè)月生產(chǎn)的筆記本電腦能夠全部售出。公司經(jīng)理考慮以下目標(biāo)：第一目標(biāo)：充分利用正常的生產(chǎn)能力，避免開工不足；第二目標(biāo)：優(yōu)先滿足老客服的需求,A,B,C三種型號(hào)的電腦各為50臺(tái)、50臺(tái)、80臺(tái)，同時(shí)根據(jù)三種電腦三種電腦的純利潤分配不同的加權(quán)系數(shù)；第三目標(biāo)：限制裝

31、配線加班時(shí)間,最好不超過200小時(shí)；第四目標(biāo)：滿足各種型號(hào)電腦的銷售目標(biāo),A,B,C三種型號(hào)分別為100臺(tái)、120臺(tái)、100臺(tái),再根據(jù)三種電腦的純利潤分配不同的加權(quán)系數(shù)；第五目標(biāo)：裝配線加班時(shí)間盡可能少。請(qǐng)列出相應(yīng)的目標(biāo)規(guī)劃模型,并用LINGO軟件求解。解：建立目標(biāo)約束。（1）裝配線正常生產(chǎn)設(shè)生產(chǎn)A,B,C型號(hào)的電腦為x,x,x（臺(tái)），d-為裝配線正常生產(chǎn)時(shí)間未利用231數(shù),d+為裝配線加班時(shí)間,希望裝配線正常生產(chǎn),避免開工不足,因此裝配線目標(biāo)約1束為mind-15x+8x+12x+dd+=17002311(2)銷售目標(biāo)優(yōu)先滿足老客戶的需求，并根據(jù)三種電腦的純利潤分配不同的權(quán)因子，A，B，C三種型號(hào)的電腦每小時(shí)的利潤是1000,1440,2520,因此,老客戶的銷售目標(biāo)約束為5812min20d-+18d-+21d-34x+d-d+50122x+d-d+5033x+d-d+8044再考慮一般銷售。類似上面的討論，得到min20d-+18d-+21d-567x+d-d+100155x+d-d+12066x+d-d+10077(3)加班限制首先是限制裝配線加班時(shí)間，不允許超過200小時(shí)，因此得到mind+85x+8x+12x+d-d+190012388其次裝配線的加班時(shí)間盡可能少，即mind+15x+8x+12x+d-d+17