茹少鋒運(yùn)籌學(xué)課后答案西北大學(xué)考研第二章到第十章

1、第二章1用圖解法求解兩個(gè)變量線性規(guī)劃問(wèn)題的最優(yōu)解和最優(yōu)值。2用圖解法求解以下線性規(guī)劃問(wèn)題，并指出哪個(gè)問(wèn)題有惟一解、無(wú)窮多最優(yōu)解、無(wú)界解或無(wú)可行解 無(wú)可行解3某公司從中心制造地點(diǎn)向分別位于城區(qū)北、東、南、西方向的分配點(diǎn)運(yùn)送材料。該公司有26輛卡車，用于從制造地點(diǎn)向分配點(diǎn)運(yùn)送材料。其中有9輛，每輛能裝5噸的大型卡車，12輛每輛能裝2噸的中型卡車和5輛每輛能裝1噸的小型卡車。北、東、南、西四個(gè)點(diǎn)分別需要材料14噸、10噸、20噸、8噸。每輛卡車向各分配點(diǎn)送材料一次的費(fèi)用如表2-7所示。建立運(yùn)送材料總費(fèi)用最小的線性規(guī)劃模型。表2-7 車輛運(yùn)送一次的費(fèi)用北東南西大80639275中50605542小20

2、153822解 設(shè)大、中、小型車分別用表示，則；東、南、西、北四個(gè)分點(diǎn)分別用表示，則；向方向發(fā)出的型車數(shù)量為。4某工廠生產(chǎn)A、B、C三種產(chǎn)品，現(xiàn)根據(jù)合同及生產(chǎn)狀況制定5月份的生產(chǎn)計(jì)劃。已知合同甲為：A產(chǎn)品1000件，每件價(jià)格為500元，違約金為100元/每件；合同乙：B產(chǎn)品500件，每件價(jià)格為400元，違約金為120元/每件；合同丙為：B產(chǎn)品600件，每件價(jià)格為420元，違約金為130元/每件；C產(chǎn)品600件，價(jià)格400元/每件，違約金為90元/每件。有關(guān)各產(chǎn)品生產(chǎn)過(guò)程所需工時(shí)以及原材料的情況如表2-8所示。試以利潤(rùn)為目標(biāo)建立該工廠生產(chǎn)計(jì)劃的線性規(guī)劃模型。表2-8 產(chǎn)品使用的原材料、加工工序、

3、資源限制、成本產(chǎn)品A產(chǎn)品B產(chǎn)品C資源限制工時(shí)或原材料成本工序1212460015工序2311400010工序3232600010原料2432800040其他成本101010解 設(shè)工廠5月份為完成合同甲生產(chǎn)件A產(chǎn)品；為完成合同乙生產(chǎn)件B產(chǎn)品；為完成合同丙生產(chǎn)件 B產(chǎn)品，件C產(chǎn)品。5某公司從事某種商品的經(jīng)營(yíng)，現(xiàn)欲制定本年度10至12月的進(jìn)貨及銷售計(jì)劃。已知該種商品的初始庫(kù)存量為2000件，公司倉(cāng)庫(kù)最多可存放10000件，公司擁有的經(jīng)營(yíng)資金80萬(wàn)元，據(jù)預(yù)測(cè)，10至12月的進(jìn)貨及銷售價(jià)格如表2-9所示。若每個(gè)月僅在1號(hào)進(jìn)貨1次，且要求年底時(shí)商品存量達(dá)到3000件，在以上條件下

4、，建立該問(wèn)題的線性規(guī)劃模型，使公司獲得最大利潤(rùn)？（注：不考慮庫(kù)存費(fèi)用）表2-9 進(jìn)貨和銷售價(jià)格月份101112進(jìn)貨價(jià)格/（元/件）909598銷售價(jià)格/（元/件）100100115解 ，為每月購(gòu)進(jìn)的貨物，為每月銷售的貨物。6某飼養(yǎng)場(chǎng)飼養(yǎng)動(dòng)物出售，設(shè)每頭動(dòng)物每天至少需700g蛋白質(zhì)、30g礦物質(zhì)、100mg維生素?，F(xiàn)有五種飼料可供選用，各種飼料每公斤營(yíng)養(yǎng)成分含量單價(jià)如表2-10所示。表2-10 飼料所含的營(yíng)養(yǎng)成分及價(jià)格飼料蛋白質(zhì)/g礦物質(zhì)/g維生素/g價(jià)格/（元·）1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8求這個(gè)問(wèn)題的規(guī)劃模型，

5、使既滿足動(dòng)物生長(zhǎng)的需要，又使費(fèi)用最小的選用飼料的方案。解 設(shè)各送這5鐘飼料，kg。7某一企業(yè)家需要找人清理5間會(huì)議室、12張桌子和18個(gè)貨架。今有兩個(gè)臨時(shí)工A和B可供該企業(yè)家雇傭。A一天可清理1間會(huì)議室、3張桌子與3個(gè)貨架；而B(niǎo)一天可清理1間會(huì)議室、2張桌子與6個(gè)貨架。A的工資每天25元，B每天22元。為了使成本最低，應(yīng)雇傭A和B各多少天？（用線性規(guī)劃圖解法求解）解：設(shè)雇傭A和B分別為天由圖知A點(diǎn)為最優(yōu)解，聯(lián)立方程： 解得： =2, 3,即： Zmin=25+22=252+223=116 因此，雇傭A工人2天，B工人3天。8某外貿(mào)公司專門(mén)經(jīng)營(yíng)某種雜糧的批發(fā)業(yè)務(wù)。公司現(xiàn)有庫(kù)容5000擔(dān)的倉(cāng)庫(kù)。1

6、月1日，公司擁有庫(kù)存1000擔(dān)雜糧，并有資金20000元。估計(jì)第一季度雜糧價(jià)格如表2-11所示。表2-11 第一季度雜糧價(jià)格表進(jìn)貨價(jià)/元出貨價(jià)/元1月2.853.102月3.053.253月2.902.95如果買(mǎi)進(jìn)的雜糧當(dāng)月到貨，但需到下月才能賣出，且規(guī)定“貨到付款”。公司希望本季度末庫(kù)存為2000擔(dān)，建立該問(wèn)題的線性規(guī)劃模型使三個(gè)月總的獲利最大。解 設(shè)一月份買(mǎi)入擔(dān)，賣出擔(dān)；二月份買(mǎi)入擔(dān)，賣出擔(dān)；三月份買(mǎi)入擔(dān)，賣出擔(dān)。第三章1求下列線性規(guī)劃問(wèn)題的所有基解、基可行解、最優(yōu)解解：由題意知：A= =（） b= c=（3，1，3）（1）=（），0，是基，是基變量，是非基變量，令=0，得=-2，=4 即

7、=為基解，但不是基本可行解。（2）=（），0，是基，是基變量，是非基變量。令=0，得=2/3，=3/4，即=為基解，同時(shí)為基本可行解，zmax=(2/3)*3+0+4/3*3=6。（3），0，是基，是基變量，是非基變量，令=0，得=1，=1，即=為基解，同時(shí)為基本可行解， zmax=1+3=4。綜上所述，基解為=，=，=其中第二個(gè)和第三個(gè)為基本可行解，=為最優(yōu)解。2分別用圖解法和單純形法求解下列線形規(guī)劃問(wèn)題，并指出單純形法迭代的每一步相當(dāng)于圖形上哪一個(gè)頂點(diǎn) 解：（1）圖解法有圖解法知線性規(guī)劃模型的可行域如陰影部分所示，令z=0，1，2時(shí)，max z逐漸增大，可行域是無(wú)界的，所以，此模型是無(wú)界解

8、。（2）單純形法：化為標(biāo)準(zhǔn)型為： A= C=（2，3，0，0）2 3 0 0 b01-11010100122300對(duì)應(yīng)圖中原點(diǎn)。以1為軸心項(xiàng)，換基迭代，得2 3 0 0 b21-1101001-11105-20-2此時(shí)對(duì)應(yīng)圖中A點(diǎn)，坐標(biāo)是 （1，0） 以1為軸心項(xiàng)，換基迭代，得2 3 0 0 b210012301-1110035-7此時(shí)對(duì)應(yīng)圖中B點(diǎn)，坐標(biāo)是 （2，3）因?yàn)椋?5>0,同時(shí)對(duì)應(yīng)的列小于等于0，則原模型有無(wú)界解。 解：（1）圖解法：可行域如上圖陰影部分所示，令z=0，1，2做等值線，得出在c點(diǎn)取最大值，c點(diǎn)坐標(biāo)為（2，6），max z=34（2）單純形法：化為標(biāo)準(zhǔn)型為： =（

9、） b= C=（2，5，0，0，0） 取B=（）為可行基，=（0，0，0）單純性表如下：2 50 0 0b0101004002010120320011825000此時(shí)對(duì)應(yīng)圖中O點(diǎn)，坐標(biāo)為（0，0），以1為軸心項(xiàng)，換基迭代，得2 50 0 0b210100400201012002-301605-200-8此時(shí)對(duì)應(yīng)圖中A點(diǎn)，坐標(biāo)為（4，0） 以2為軸心項(xiàng)，換基迭代，得2 50 0 0b210100400031-16501-3/201/230011/20-2/5-23此時(shí)對(duì)應(yīng)圖中B點(diǎn)，坐標(biāo)為（4，3） 以3為軸心項(xiàng)，換基迭代，得2 50 0 0b2100-1/31/3200011/3-1/32501

10、01/206000-11/6-2/3-34由于 =0，<0,所以存在唯一解，也是最優(yōu)解。此時(shí)對(duì)應(yīng)圖中C點(diǎn)，坐標(biāo)為（2，6），max z=2*2+5*6=34， 解：（1）圖解法：可行域如圖陰影部分，當(dāng)z=0，1，2做等值線，已知與直線的斜率相同，當(dāng)z與這條直線重合時(shí)，該模型取最大值，因此該模型有無(wú)窮多個(gè)解，無(wú)窮多個(gè)解是B,C兩點(diǎn)線段中的點(diǎn)，max z=16（2）單純形法：化為標(biāo)準(zhǔn)型：= （） b= C=（2，4，0，0，0） B=（） =（0，0，0）單純形表為：2 40 0 0b022100120120108003001924000此時(shí)對(duì)應(yīng)圖中點(diǎn)O，坐標(biāo)為（0，0），以2為軸心項(xiàng)，換基

11、迭代，得2 40 0 0b2111/2006001-1/2102003001902-100-12此時(shí)對(duì)應(yīng)圖中點(diǎn)A，坐標(biāo)為（6，0） 以1為軸心項(xiàng)，換基迭代，得2 40 0 0b2101-104401-1/21020002/3-313000-20-16此時(shí)對(duì)應(yīng)圖中點(diǎn)B，坐標(biāo)為（4，2） 由于0,又為非基變量，且=0，且此列存在正數(shù)，則此線性規(guī)劃模型有無(wú)窮解。其中一個(gè)基本最優(yōu)解為，max z=2*4+4*2=163用單純形法求解下列線性規(guī)劃問(wèn)題解：化為標(biāo)準(zhǔn)型： A= b= C=（-1，-2，1，0，0，0）令B=（） B為可行基，=（0，0，0）單純形表如下：- -20 00b021-110040

12、1-22010801110015-1-21000以2為軸心項(xiàng)，換基迭代，得- -20 00b05/20011/20811/2-1101/20401/2200-1/211-2/3-100-1/20-4 =0，<0,存在唯一解，此時(shí)=0，=4。min f=0+2*0-4=-44用大M法求解下列線性規(guī)劃問(wèn)題解：化為標(biāo)準(zhǔn)型（加上人工變量a）： b= C=（5，1，3，0，0）5 30 0-Mab-Ma142-1011001-21010165+M1+4M3+2M-M00以2為軸心項(xiàng)，換基迭代，得5 30 0-Mab5142-1011000-6-111-160-19-750-5-M-10（M+5）以

13、1為軸心項(xiàng)，換基迭代，得5 30 0-Mab51-210101600-6-111-16011-20-5-M-10（M+8）由于第二列對(duì)應(yīng)的檢驗(yàn)數(shù)為11>0，并且所對(duì)應(yīng)的列全小于0，則此線性規(guī)劃模型的解是無(wú)界解。5. 已知線性規(guī)劃問(wèn)題，用單純形法計(jì)算時(shí)得到的中間某兩步的計(jì)算表見(jiàn)表3-16所示，試將表中空白處的數(shù)字填上。表3-16 單純形迭代中的兩步計(jì)算表10000510040104005010400131000 1 0 6已知線性規(guī)劃問(wèn)題 用單純形法求解，得到最優(yōu)單純形表如表如表3-17所示：表3-17 最終單純形表10110-122-3000-4求的值；求的值。解：由題意可知：初始的基變

14、量是， ，將最終單純形表的基變量通過(guò)迭代轉(zhuǎn)換為，還原成最初單純形表，如下：14108120153600從而得出： b= C=所以,= =1 =4 = =1 =2 =8 =5， = =3 =67某公司生產(chǎn)1、2兩種產(chǎn)品，市場(chǎng)對(duì)1、2兩種產(chǎn)品的需求量為：產(chǎn)品1在1-4月每月需求10000件，5-9月每月30000件，10-12月每月100000件，產(chǎn)品2在3-9月每月需求15000件，其它月每月50000件，該公司生產(chǎn)這兩種產(chǎn)品的成本為：產(chǎn)品1在1-5月內(nèi)生產(chǎn)每件5元，6-12月內(nèi)生產(chǎn)每件4.5元；產(chǎn)品2在1-5月內(nèi)生產(chǎn)每件8元，6-12月內(nèi)生產(chǎn)每件7元。該公司每月生產(chǎn)這兩種產(chǎn)品的能力總合不超過(guò)1

15、20000件。產(chǎn)品1容積每件0.2立方米，產(chǎn)品2每件0.4立方米，該公司倉(cāng)庫(kù)容量為15000立方米，占用公司倉(cāng)庫(kù)每月每立方米庫(kù)容需1元；如該公司倉(cāng)庫(kù)不足時(shí)，可從外邊租借，租用外面?zhèn)}庫(kù)每月每立方米庫(kù)容需1.5元。試問(wèn)在滿足市場(chǎng)需求的情況下，該廠應(yīng)如何安排生產(chǎn)，使總的費(fèi)用最??？8某煉油廠使用三種原料油甲、乙、丙混合加工成A、B、C三類不同的汽油產(chǎn)品，有關(guān)數(shù)據(jù)如下表3-18所示。另外，由于市場(chǎng)原因，A的產(chǎn)量不得低于產(chǎn)品總量的40%。問(wèn)該廠應(yīng)如何安排生產(chǎn)才能使其總利潤(rùn)最大？表3-18 三種原料的信息產(chǎn)品產(chǎn)品規(guī)格原料ABC原料成本（千元/噸）原料限量（噸）甲1.8002000乙1.3502500丙0.9

16、001200加工費(fèi)（千元/噸）0.4500.3600.270售價(jià)（千元/噸）3.0602.5652.025解：設(shè)，分別為A產(chǎn)品中甲、乙、丙的成分；，分別為B產(chǎn)品中甲、乙、丙的成分；，分別為C產(chǎn)品中甲、乙、丙的成分。由題意，有max z=（3.060-0.450）*（+）+（2.565-0.360）*（+）+（2.025-0.270）*（+）-1.800*（+）-1.350*（+）-0.900*（+）用計(jì)算機(jī)求解為：9線性規(guī)劃的目標(biāo)函數(shù)是求其值的極大化，在標(biāo)準(zhǔn)的單純形法求解過(guò)程中得到如下表(其中是常數(shù))表3-19 求解中某一步的單純形表00302050-2-118-2（1）在所有的空格上填上適當(dāng)

17、的數(shù)（可包含參數(shù)）（2）判斷下面四種情況在什么時(shí)候成立，說(shuō)明理由。1）此解為最優(yōu)解，寫(xiě)出相應(yīng)的基解和目標(biāo)函數(shù)值；2）此解為最優(yōu)解，且此線性規(guī)劃有無(wú)窮多最優(yōu)解；3）此規(guī)劃有無(wú)界解；4）此解不是最優(yōu)解，但可用單純形法得到下一個(gè)基可行解。解：（1）00030002051000-20-111182-50-20-0（2）1)當(dāng)2-5<0 即 >時(shí)，此線性規(guī)劃模型有唯一解，基解為最優(yōu)值為5。 2）2-5=0，即 =時(shí)，大于0，此線性規(guī)劃模型有無(wú)窮多最優(yōu)解。 3）2-5>0且 <0，即<0時(shí)， 此線性規(guī)劃模型有無(wú)界解。 4）2-5>0且 >0且>0, 即0&l

18、t;<且>0時(shí)，此解不是最優(yōu)解。10表3-20是求某極大化線性規(guī)劃問(wèn)題計(jì)算得到的單純形表。表中無(wú)人工變量，、為待定常數(shù)。試說(shuō)明這些常數(shù)分別取何值時(shí)，以下結(jié)論成立。表3-20 極大化線性規(guī)劃問(wèn)題計(jì)算得到的單純形表4100-1-301-102-500-41300-30表中解為惟一最優(yōu)解； 表中解為最優(yōu)解，但存在無(wú)窮多最優(yōu)解；該線性規(guī)劃問(wèn)題具有無(wú)界解；表中解非最優(yōu)，為對(duì)解改進(jìn)，換入變量為，換出變量為解：（1）當(dāng)d0，<0 且 <0, 此線性規(guī)劃模型有唯一解。（2）當(dāng)d0，=0 或 =0，<0, 此線性規(guī)劃模型有無(wú)窮個(gè)最優(yōu)解。 （3）當(dāng)d0，>0 且 <0,

19、此線性規(guī)劃模型有無(wú)界解。 （4）當(dāng)d0，>0 且 >，表中解非最優(yōu)，為對(duì)解改進(jìn)，換入變量為，換出變量為。第四章1寫(xiě)出線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題。 解：（1） （2） （3） （4）2判斷下列說(shuō)法是否正確，并說(shuō)明理由。（1）如果線性規(guī)劃的原問(wèn)題存在可行解，則其對(duì)偶問(wèn)題也一定存在可行解（2）如果線性規(guī)劃的對(duì)偶問(wèn)題無(wú)可行解，則其原問(wèn)題也一定無(wú)可行解（3）在互為對(duì)偶問(wèn)題的一對(duì)原問(wèn)題與對(duì)偶問(wèn)題中，不管原問(wèn)題是求最大或最小，原問(wèn)題可行解的目標(biāo)函數(shù)值一定不超過(guò)其對(duì)偶問(wèn)題的可行解的目標(biāo)函數(shù)值（4）任何線性規(guī)劃問(wèn)題具有唯一的對(duì)偶問(wèn)題解：（1）不正確。因?yàn)楫?dāng)原模型存在可行解且目標(biāo)函數(shù)值無(wú)界時(shí)，其對(duì)偶模型無(wú)

20、可行解。（2）不正確。因?yàn)閷?duì)偶模型無(wú)可行解，其原模型可能存在可行解且目標(biāo)函數(shù)值無(wú)界。（3）不正確。當(dāng)原模型求最小值時(shí)，原模型的目標(biāo)函數(shù)值可能超過(guò)對(duì)偶模型的目標(biāo)函數(shù)值。（4）正確。對(duì)偶模型具有對(duì)稱性。3用計(jì)算機(jī)求解線性規(guī)劃問(wèn)題,說(shuō)明每一種資源的影子價(jià)格。解：計(jì)算機(jī)求解結(jié)果如下圖所示：由圖可知，原模型的最優(yōu)解為（50，250），其對(duì)偶模型的最優(yōu)解為（50，0，50），三個(gè)約束條件的影子價(jià)格分別為50，0，50 。4 某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，其單位利潤(rùn)分別為2元和3元。每生產(chǎn)一件甲產(chǎn)品需勞動(dòng)力3個(gè)，原材料2個(gè)單位。每生產(chǎn)一件乙產(chǎn)品需勞動(dòng)力6個(gè)，原材料1個(gè)單位。企業(yè)現(xiàn)有勞動(dòng)力24個(gè)，原材料10單位。

21、試問(wèn)：（1）該企業(yè)應(yīng)如何安排生產(chǎn)才能獲得最大利潤(rùn)？（2）若另一個(gè)企業(yè)想利用該企業(yè)的這兩種資源（勞動(dòng)力和原材料），該企業(yè)最低應(yīng)以多少價(jià)格轉(zhuǎn)讓？解：設(shè)該企業(yè)生產(chǎn)甲產(chǎn)品個(gè)，乙產(chǎn)品個(gè)，利潤(rùn)為z，建立模型為 （1）化為標(biāo)準(zhǔn)型 ，(10,3,0,0)，,最初單純形表2300b 2 5 1 0 24 2 1 0 0 10 2 3 0 0 經(jīng)過(guò)換基迭代后，形成最優(yōu)單純形表2300b 0 1 2/9 -1/3 2 1 0 -1/9 1/3 4 0 0 -4/9 -1/3 由最優(yōu)單純形表可知，最優(yōu)解為（4，2，0，0），即應(yīng)生產(chǎn)4個(gè)甲產(chǎn)品，2個(gè)乙產(chǎn)品，獲利最大。（2） 由（1）中最優(yōu)單純形表知對(duì)偶模型最優(yōu)解為（4

22、/9,1/3），因此，最低轉(zhuǎn)讓價(jià)應(yīng)為24*4/9+10*1/3=14 (元)。5已知線性規(guī)劃問(wèn)題（1）寫(xiě)出該問(wèn)題的對(duì)偶問(wèn)題（2）已知原問(wèn)題的最優(yōu)解為：。根據(jù)對(duì)偶理論，直接求出對(duì)偶問(wèn)題的最優(yōu)解。解：（1）對(duì)偶模型為 （2）根據(jù)對(duì)偶模型的互補(bǔ)松弛性理論，可知原模型的松弛變量=0, =0, =0, =-1。 設(shè)對(duì)偶模型最優(yōu)解為，由互補(bǔ)松弛性可知，=0 ，所以=0。 又設(shè)對(duì)偶模型剩余變量為，且均為正數(shù)，互補(bǔ)性有=0，于是得=0，此時(shí)對(duì)偶模型的約束條件為 解之得=2 ，=10 ，=-2 ， =0 。 6對(duì)線性規(guī)劃問(wèn)題(1)寫(xiě)出其對(duì)偶問(wèn)題；(2)利用對(duì)偶問(wèn)題性質(zhì)證明原問(wèn)題目標(biāo)函數(shù)值。解：（1）對(duì)偶模型為

23、（2）取對(duì)偶模型的可行解（0，1，0），求得對(duì)偶模型的目標(biāo)函數(shù)值為1，根據(jù)弱對(duì)偶性中原模型可行解目標(biāo)函數(shù)值不可能超過(guò)對(duì)偶模型可行解目標(biāo)函數(shù)值，可證得原模型目標(biāo)函數(shù)值z(mì)1。7給出線性規(guī)劃問(wèn)題利用對(duì)偶問(wèn)題性質(zhì)證明上述問(wèn)題目標(biāo)函數(shù)值無(wú)界。解：對(duì)偶模型為：由圖解法可知該線型規(guī)劃模型無(wú)可行解，對(duì)于原模型可取，說(shuō)明原模型有可行解，根據(jù)弱對(duì)偶性可知原模型目標(biāo)函數(shù)無(wú)界。8用對(duì)偶單純形方法求解下列線性規(guī)劃問(wèn)題 解：（1）化為標(biāo)準(zhǔn)型 A=, c=(-4,-12,-18,0,0), b=用對(duì)偶單純形法得初始單純形表為-4-12-1800b -1 0 -3 1 0 -3 0 -2 0 1 -5 -4 -12 -18

24、0 0 由（-4，-12，-18，0，0）0可知B為正則基；以為軸心項(xiàng)，換基迭代得-4-12-1800b -1 0 1 0 -3 0 1 1 0 -1/2 5/2 -4 0 -6 0 -6 以為軸心項(xiàng)，換基迭代得-4-12-1800b 1/3 0 -1/3 -1/3 0 1 -1/3 1 1/3 1/3 -1/2 3/2 -2 0 -2 -2 -6 由于所有檢驗(yàn)數(shù)b0，得到最優(yōu)解為（0, 3/2，1）。（2）化為標(biāo)準(zhǔn)型 A=, c=(-5,-2,-4,0,0)， b=初始單純形表為-5-2-400b -1 -2 1 0 -4 -6 -3 -5 0 1 -10 -5 -2 -4 0 0 以為軸心

25、項(xiàng)，換基迭代得-5-2-400b 1 1/3 2/3 -1/3 0 4/3 0 -1 -2 1 -2 0 -1/3 -2/3 -5/3 0 以為軸心項(xiàng)，換基迭代得-5-2-400b 1 0 1/3 -1 1/3 2/3 0 1 1 2 -1 2 0 0 -1/3 -1 -1/3 由于所有檢驗(yàn)數(shù)b0，得到最優(yōu)解為（ 2/3 ，2 , 0 ）。9對(duì)下列線性規(guī)劃問(wèn)題(1) 寫(xiě)出對(duì)偶問(wèn)題；（2）用對(duì)偶單純形法求解原問(wèn)題；（3）用單純形法求解其對(duì)偶問(wèn)題；（4）比較（2）與（3）中每一步計(jì)算得到的結(jié)果。解：（1）對(duì)偶模型（2）原模型化為標(biāo)準(zhǔn)模型得 對(duì)偶單純形法得到的初始單純形表-60-40-80000b

26、-1 -1 1 0 0 -2 -4 -1 -3 0 1 0 -4 -2 -2 -2 0 0 1 -3 -60 -40 -80 0 0 0 以為軸心項(xiàng)，換基迭代得-60-40-80000b 1 2/3 1/3 -1/3 0 0 2/3 0 5/3 -5/3 1 0 -4/3 0 -2/3 -4/3 -2/3 0 1 -5/3 0 0 -60 -20 0 0 以為軸心項(xiàng)，換基迭代得-60-40-80000b 1 1/4 3/4 0 -1/4 0 1 0 -5/4 5/4 1 -3/4 0 1 0 -1/3 0 -1/2 1 -1 0 -25 -35 0 -15 0 以為軸心項(xiàng)，換基迭代得-60-4

27、0-80000b 1 0 4/9 3/4 -1/12 -1/12 5/6 0 0 55/36 1 -3/4 -5/6 11/6 0 1 2/9 0 1/3 -2/3 2/3 0 0 -260/9 0 -20/3 25 全部的檢驗(yàn)數(shù)b0，得到最優(yōu)解為（5/6,2/3,0）。（3）對(duì)偶模型化為標(biāo)準(zhǔn)型得 初始單純形表為b 4 3 1 0 0 60 2 1 2 0 1 0 40 1 3 2 0 0 1 80 2 4 3 0 0 0 以為軸心項(xiàng)，換基迭代得b 1 2/3 1/3 0 0 20 0 -5/3 2/3 -2/3 1 0 0 0 5/3 4/3 -1/3 0 0 60 0 4 /3 5/3 -

28、2/3 0 0 以為軸心項(xiàng)，換基迭代得b 3/4 1 1/2 1/4 0 0 15 5/4 0 -1/4 1 0 25 -5/4 0 1/2 -3/4 0 0 35 -4/3 0 1 -1 0 0 以為軸心項(xiàng)，換基迭代得b 1/3 1 0 1/3 -1/3 0 20/3 5/6 0 1 -1/6 2/3 0 50/3 -5/3 0 0 -2/3 -1/3 0 85/3 -13/6 0 0 -5/6 -2/3 0 由全部檢驗(yàn)數(shù)0，得最優(yōu)解為（0，20/3,50/3）。（4）比較第五章1某公司制造甲、乙兩種產(chǎn)品，甲、乙兩種產(chǎn)品的產(chǎn)量每天分別為30個(gè)和120個(gè)。公司希望了解是否通過(guò)改變這兩種產(chǎn)品的數(shù)

29、量而提高公司的利潤(rùn)，制造每個(gè)產(chǎn)品所需的加工工時(shí)和各個(gè)車間的加工能力如表5-10所示。表5-10 產(chǎn)品的相關(guān)數(shù)據(jù)假設(shè)每天甲、乙產(chǎn)品的生產(chǎn)產(chǎn)量分別為：，則線性規(guī)劃模型為使用QM軟件求解并回答下面問(wèn)題。（1）最優(yōu)解是什么，最大利潤(rùn)是多少？（2）哪個(gè)車間的加工工時(shí)已用完？那個(gè)車間的加工工時(shí)還沒(méi)用完？其松弛變量即沒(méi)用完的加工工時(shí)各為多少？（3）四個(gè)車間的加工工時(shí)的對(duì)偶價(jià)格各為多少？請(qǐng)對(duì)此對(duì)偶的含義予以說(shuō)明。（4）如果請(qǐng)你在這四個(gè)車間中選擇一個(gè)車間進(jìn)行加班生產(chǎn)，你會(huì)選擇哪一個(gè)？為什么？（5）目標(biāo)函數(shù)中的系數(shù)在什么范圍內(nèi)變化時(shí)，最優(yōu)解不變。（6）目標(biāo)函數(shù)中的系數(shù)從400提高到490時(shí)，最優(yōu)解變了沒(méi)有，為什么

30、？（7）請(qǐng)解釋右端常數(shù)項(xiàng)各值的上限和下限。（8）車間1的加工工時(shí)數(shù)從300增加到400時(shí)，總利潤(rùn)能增加多少，這時(shí)最優(yōu)解變化了沒(méi)有？（9） 車間3的加工工時(shí)數(shù)從440增加到480時(shí)，能否求得總利潤(rùn)增加的數(shù)量？為什么？解：(1)將原模型變換成標(biāo)準(zhǔn)形CX0010003000030100540022001044001.21.500013005004000000500100.5000150003010054000-1010140001.5-0.60011200400-250000500100.50001500001.51-1.5033040001-0.500.50700000.150-0.7511500

31、-500-2000最優(yōu)解為： 最大利潤(rùn)：(2)由最終單純形表知：，因此，一車間和三車間的加工工時(shí)已用完，二車間和四車間沒(méi)有用完，分別剩余330和15個(gè)加工工時(shí)。(3)由最終單純形表知：第一車間的影子價(jià)格為-(-50)，即50，第二車間的影子價(jià)格為-(-200)，即200。這表示在一定范圍內(nèi)，第一車間每增加一個(gè)設(shè)備臺(tái)時(shí)，目標(biāo)函數(shù)增加50；第二車間每增加一個(gè)設(shè)備臺(tái)時(shí)，目標(biāo)函數(shù)增加200。(4)選擇第三車間，因?yàn)榈谌囬g的影子價(jià)格高，每增加一工時(shí)帶來(lái)的利潤(rùn)大。(5)由最優(yōu)單純形表知：，=。的系數(shù)為基變量系數(shù)，因此，設(shè)：的波動(dòng)為，令=500+，要使優(yōu)解不變，則：，即：解得：，=500+（6）設(shè)的波動(dòng)為

32、，令=400+，若使最優(yōu)解不變，則：，即：解得：，。(7)常數(shù)項(xiàng)波動(dòng)變化，當(dāng)變化時(shí)，只要，則仍是最優(yōu)基。令，則：，即：解得：,同理：分別令，；解得：，。(8)400在常數(shù)項(xiàng)變化范圍（200，440）之間，因此，總利潤(rùn)變化量：50(400-300)=5000；最優(yōu)解變化為：(9)不能，因?yàn)槌?shù)項(xiàng)變化超出其變化范圍（300，460）。2已知線性規(guī)劃問(wèn)題:的最終單純形表如表5-11所示。表5-11 最優(yōu)單純形表（1）寫(xiě)出其對(duì)偶模型；（2）求出對(duì)偶模型的最優(yōu)解；（3）寫(xiě)出最優(yōu)基及其逆矩陣；（4）若右端項(xiàng)變?yōu)?，最?yōu)基是否變化？求出變化后的最優(yōu)解及其最優(yōu)值。解：(1)其對(duì)偶模型為：(2)原模型最優(yōu)解為：，

33、設(shè)對(duì)偶模型最優(yōu)解為,知；設(shè)對(duì)偶模型的剩余變量為,由于剩余變量均為非負(fù)，故=0，=0，此時(shí)對(duì)偶模型的約束條件為：(3)最優(yōu)基為(4) 常數(shù)項(xiàng)波動(dòng)變化，當(dāng)變化時(shí)，只要，則仍是最優(yōu)基。令，則：解得：當(dāng)常數(shù)項(xiàng)在其變化范圍中變化，故最優(yōu)基不變；最優(yōu)解為,最優(yōu)值為。3給出了下列線形規(guī)劃：的最優(yōu)單純形表如表5-12所示。表5-12 最優(yōu)單純形表（1）求出最優(yōu)基不變的的變化范圍；（2）求出最優(yōu)解不變的的變化范圍；（3）在原線性規(guī)劃的約束條件上，增加下面的約束條件：其最優(yōu)解是否變化，如變化，求出最優(yōu)解。解：(1)設(shè)的變化為，只要?jiǎng)t仍為最優(yōu)基，即： ，即上變化是最優(yōu)基不變。(2)設(shè)的變化為，要是最優(yōu)基不變，則，即

34、：（3）其最優(yōu)解變化為。4有一標(biāo)準(zhǔn)型的線性規(guī)劃問(wèn)題：其最優(yōu)單純形表如表5-13所示：表5-13 最優(yōu)單純形表其中：是對(duì)用于初始單位矩陣的松弛變量。試求：（1）利用最優(yōu)單純形表求。（2）假定用代替，其中，要使現(xiàn)行最優(yōu)基保持不變，的變化范圍？當(dāng)時(shí)，求最優(yōu)解。（3）求約束影響價(jià)格。解：（1）從最優(yōu)單純形表中得出：= 由于，是松弛變量所以，均為0。根據(jù)=-知： 得出：分別為2，3，1，0，0。（2）要使最優(yōu)基不變，則=b0，即 0 得出： 。當(dāng)，在區(qū)間內(nèi)，最優(yōu)基不變，最優(yōu)解為：（3）根據(jù)影子價(jià)格與松弛變量之間的關(guān)系知： ， 5有最大問(wèn)題的最優(yōu)單純形表如下，其中為松弛變量。表5-14 最優(yōu)單純形表寫(xiě)出該

35、問(wèn)題的最優(yōu)解。當(dāng)為何值時(shí)，其對(duì)偶問(wèn)題無(wú)解？并說(shuō)明理由。解：（1）由以上的最優(yōu)單純表得出最優(yōu)解為： （2）若原模型有可行解但目標(biāo)函數(shù)值無(wú)界，則對(duì)偶模型無(wú)解。 設(shè)C=(),因?yàn)闉樗沙谧兞浚跃鶠? 。 C-=（，0，0）-（）解得：=0， =-4， =1 設(shè)=+，當(dāng)C-0時(shí)，最優(yōu)基不變，即C-=（0，-4，1+，0，0）-（1+，0）0 解得：-13 即當(dāng)-13時(shí)，最優(yōu)基不變。此時(shí)=-4-（+，0）=-3+ 當(dāng)0 且 -13 時(shí)，原模型有無(wú)界解，即=3時(shí)，對(duì)偶模型無(wú)可行解。 6考慮下列線性規(guī)劃：最優(yōu)單純形表如表5-15所示：表5-15 最優(yōu)單純形表(1) 寫(xiě)出此線性規(guī)劃的最優(yōu)解、最優(yōu)基和它的逆；

36、(2) 求此線性規(guī)劃的對(duì)偶問(wèn)題的最優(yōu)解；(3) 試求在什么范圍內(nèi)，此線性規(guī)劃的最優(yōu)解不變；(4) 若 = 20 變?yōu)?45，最優(yōu)解及最優(yōu)值是什么？解：（1）由最優(yōu)單純形表知：最優(yōu)解為 = = （2）因?yàn)閷?duì)偶模型的最優(yōu)解是原模型松弛變量檢驗(yàn)數(shù)值的相反數(shù)，所以，對(duì)偶模型的最優(yōu)解為： 5， 0 。 （3）設(shè)=+，是基變量對(duì)應(yīng)的系數(shù)，要使原模型的最優(yōu)解不變，則-0，即0解得：，所以 ，在此范圍內(nèi)變化時(shí)，此線性規(guī)劃模型最優(yōu)解不變。 （4）設(shè)=+，當(dāng)時(shí)最優(yōu)基不變，即0，解得： 即 。若 = 20 變?yōu)?45，最優(yōu)基發(fā)生變化，將45代入，重新用單純形表解得最優(yōu)解為，最優(yōu)值為117 。7分析線性規(guī)劃問(wèn)題中變化

37、時(shí)最優(yōu)解變化情況： 解：化為標(biāo)準(zhǔn)型： C=單純形表如下：（）（）000b01010040020101203200118000以1為軸心項(xiàng)，換基迭代得：（）（）000b10100400201012002-3016000當(dāng)>5時(shí), <0,此線性規(guī)劃模型有唯一解，最優(yōu)解為 。當(dāng)=5時(shí), =0且對(duì)應(yīng)的列存在正數(shù),有無(wú)窮個(gè)解。當(dāng)<5時(shí)，>0, 以2為軸心項(xiàng)，進(jìn)一步換基迭代，得：（）（）000b10100400031-1601-3/201/23000由于<5，則<0，此線性規(guī)劃模型有唯一解，最優(yōu)解為：8現(xiàn)有線性規(guī)劃問(wèn)題先用單純形法求出最優(yōu)解，然后分析在下列各種條件下，最

38、優(yōu)解分別有什么變化？（1）第一個(gè)約束條件的右端常數(shù)由常數(shù)20變?yōu)?0；（2）第二個(gè)約束條件的右端常數(shù)由常數(shù)90變?yōu)?0；（3）目標(biāo)函數(shù)中的系數(shù)由13變?yōu)?；（4）的系數(shù)列向量由變?yōu)?；?）增加一個(gè)約束條件 ；（6）將原來(lái)第二個(gè)約束條件改變?yōu)?解：?jiǎn)渭冃畏ㄇ蟮米顑?yōu)單純形表為-551300b -1 1 3 1 0 20 16 0 -2 -4 1 10 0 0 -2 -5 0 由表可得，最優(yōu)解為（0，20，0），=（，），= 。（1）設(shè)波動(dòng)為，由=0,得-202.25，即022.5時(shí)最優(yōu)解不變。所以當(dāng)從20變?yōu)?0時(shí)，最優(yōu)解已經(jīng)改變?yōu)椋?，0，9）。（2）設(shè)波動(dòng)為，由=0,得10，即80時(shí)最優(yōu)解不變

39、。所以當(dāng)從90變?yōu)?0時(shí)，最優(yōu)解已經(jīng)改變?yōu)椋?，5，5）。（3）由=（，）知為非基變量系數(shù)，其變化幅度-=2時(shí)，最優(yōu)解不變。所以當(dāng)從13變?yōu)?時(shí)，=8-13=-52，最優(yōu)解不變。（4）當(dāng)系數(shù)列向量由變?yōu)闀r(shí)，最優(yōu)單純形表為-551300b 0 1 3 1 0 20 1 0 -2 -4 1 10 -5 0 -2 -5 0 由表可知，最優(yōu)解仍為（0，20，0）。（5）增加約束條件后，模型變?yōu)?最優(yōu)單純形表為-5513000b -5/4 0 1 3/4 0 -1/4 5/2 27/2 0 0 -5/4 1 27/6 40/3 33/12 1 0 -5/4 0 3/4 25/2 -5/2 0 0 -7/2 0 -23/6 由表得最優(yōu)解為（0,25/2,5/2）.(6)條件改變后模型變?yōu)?最優(yōu)單純形表為-551300b -1 1 3 1 0 20 15 0 -5 -5 0 0 0 0 -2 -5 0 最優(yōu)解為（