管理運(yùn)籌學(xué)課后答案.doc

2.2 將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式并列出初始單純形表。（1） 解：（1）令，則得到標(biāo)準(zhǔn)型為（其中M為一個(gè)任意大的正數(shù)）初始單純形表如表2-1所示： 表2-1cj-224-400-M-MqCBXBbx2x4x5x6x70x419322-2100019/3-Mx614 4 34-40-11014/4-Mx726524-4000126/5-z-2+9M2+5M4+8M-4-8M0-M00 2.3 用單純形法求解下列線性規(guī)劃問題。 （1） （2） 解：（1）最優(yōu)解為。（2） 最優(yōu)解為。2.4 分別用大M法和兩階段法求解下列線性規(guī)劃問題。（1） （2） 解：（1）最優(yōu)解為。 （2）最優(yōu)解為。2.6 已知線性規(guī)劃問題其對(duì)偶問題最優(yōu)解為。試用對(duì)偶理論找出原問題最優(yōu)解。 解：先寫出它的對(duì)偶問題將代入約束條件可知，第2、3、4個(gè)約束為嚴(yán)格不等式，因此，由互補(bǔ)松弛性得。又因?yàn)?，所以原問題的兩個(gè)約束條件應(yīng)取等式，因此有 故原問題最優(yōu)解為。2.12 現(xiàn)有線性規(guī)劃問題先用單純形法求出最優(yōu)解，然后分析在下列各種條件下，最優(yōu)解分別有什么變化？ （1）約束條件的右端項(xiàng)系數(shù)由20變?yōu)?0；（2）約束條件的右端項(xiàng)系數(shù)由90變?yōu)?0；（3）目標(biāo)函數(shù)中的系數(shù)由13變?yōu)?；（4）的系數(shù)列向量由變?yōu)?；?）將原約束條件改變?yōu)?；?）增加一個(gè)約束條件。 解：在上述LP問題的第、個(gè)約束條件中分別加入松弛變量x4,x5得列出此問題的初始單純形表并進(jìn)行迭代運(yùn)算，過程如表2-11所示。由表2-11中的計(jì)算結(jié)果可知，LP問題的最優(yōu)解X*=(0,20,0,0,10)T，z*=5*20=100。（1）約束條件的右端項(xiàng)系數(shù)由20變?yōu)?0，則有列出單純形表，并利用對(duì)偶單純形法求解，過程如表2-12所示。表2-11cj-551300iCBXBbx1x2x3x4x50x420-11 3 1020/30x59012410019cj-zj-55130013x320/3-1/3 1/3 11/30200x570/346/32/30-10/3135cj-zj-2/32/30-13/305x220-113100x510160-2-41cj-zj00-2-50表2-12cj-551300CBXBbx1x2x3x4x55x230-113100X5-30160 -2 -41cj-zj00-2-505x2-152310 -5 3/213x315-8012-1/2cj-zj-1600-1-10x43-23/5-1/501-3/1013x396/52/5101/10cj-zj-103/5-1/500-13/10由表2-12中計(jì)算結(jié)果可知，LP問題的最優(yōu)解變?yōu)椤＃?）約束條件的右端常數(shù)由90變?yōu)?0，則有列出單純形表，并利用對(duì)偶單純形法求解，結(jié)果如表2-13所示。 表2-13cj-551300CBXBbx1x2x3x4x55x220-113100X5-10160 -2 -41cj-zj00-2-505x252310-53/213x35-8012-1/2cj-zj-1600-1-1由表2-13結(jié)果知，LP問題的最優(yōu)解變?yōu)?。?）目標(biāo)函數(shù)中x3的系數(shù)由13變?yōu)?，由于x3是非基變量，其檢驗(yàn)數(shù)變?yōu)樗訪P問題的最優(yōu)解不變。（4）x1的系數(shù)列向量由(-1,12)T變?yōu)?0,5) T，則x1在最終單純形表中的系數(shù)列向量變?yōu)閺亩鴛1在最終單純形表中的檢驗(yàn)數(shù)變?yōu)樗訪P問題的最優(yōu)解保持不變。（5）將原約束條件改變?yōu)?0x1+5x2+10x3100，則x1在最終單純形表中系數(shù)列向量變?yōu)椋瑱z驗(yàn)數(shù)x2在最終單純形表中系數(shù)列向量變?yōu)?，檢驗(yàn)數(shù)。又因的各分量均大于0，故LP問題的最優(yōu)解不變。 （6）增加一個(gè)約束條件2x1+3x2+5x350，則在此約束條件中加入松弛變量x6，并將此約束加入到最終單純形表中，繼續(xù)迭代，過程如表2-14所示。由表2-14中計(jì)算結(jié)果可知，LP問題的最優(yōu)解變?yōu)?，。?-14cj-5513000CBXBbx1x2x3x4x5x65x220-1131000x510160-2-4100x6502350015x220-1131000x510160-2-4100x6-1050 -4 -301cj - zj00-2-5005x225/211/410-5/403/40x51527/200-5/21-1/213x35/2-5/4013/40-1/4cj - zj-5/200-7/20-1/23.1 分別用分支定界法和割平面法求解下列整數(shù)規(guī)劃模型。（1） （2） 解：（1）求解得到最優(yōu)解。（計(jì)算步驟略）（2）僅寫出利用割平面法求解的過程。在原IP問題約束條件中加入松弛變量x3,x4，化為標(biāo)準(zhǔn)型，可得不考慮整數(shù)條件，用單純形法求解原問題的松弛問題，計(jì)算結(jié)果如表3-1所示。表3-1cj1100qiCBXBbx1x2x3x40x36211060x4204 5 014cj-zj11000x32 6/5 01-1/55/31x244/5101/55cj-zj1/500-1/51x15/3105/6-1/61x28/301-2/31/3cj-zj00-1/6-1/30因此，松弛問題的最優(yōu)解為x1=5/3,x2=8/3,x3=0,x4=0;z=13/3。由于x2不為整數(shù)，因此在最終單純形表中根據(jù)x2所在的行作割平面即將它作為約束條件，引入松弛變量后加到最終單純形表中，并采用對(duì)偶單純形法繼續(xù)迭代，計(jì)算過程如表3-2所示。表3-2cj11000CBXBbx1x2x3x4x51x15/3105/6-1/601x28/301-2/31/300x5-200-1 -1 1cj-zj00-1/6-1/3001x121010-1/61x2201-101/30x420011-1cj-zj0000-1/6 由于的值均為整數(shù)，所以得到原問題的最優(yōu)解為3.4 某廠新購4臺(tái)不同類型機(jī)器，可以把它們安裝在4個(gè)不同的地點(diǎn)。由于對(duì)特定的機(jī)器而言，某些地方可能安裝起來特別方便且合適，所以不同的機(jī)器安裝在不同的地點(diǎn)費(fèi)用是不同的。估計(jì)的費(fèi)用見表3-3，試制定使得總安裝費(fèi)用最小的安裝方案。表3-3 （費(fèi)用單位：元） 地點(diǎn)機(jī)器1234機(jī)器總數(shù)1109871234561321121443561需要量1111解：設(shè) cij機(jī)器i安裝在地點(diǎn)j所需的費(fèi)用。建立該問題的數(shù)學(xué)模型如下：目標(biāo)函數(shù)：約束條件：(1)每一部機(jī)器只分配在一個(gè)地點(diǎn)，即 (2)每一個(gè)地點(diǎn)只能有一臺(tái)機(jī)器，即 (3) 工作指派問題可以看成是一類特殊的運(yùn)輸問題，每個(gè)供應(yīng)點(diǎn)的供應(yīng)量為1，每個(gè)需求點(diǎn)的需求量也為1。因此，本題可以采用表上作業(yè)法進(jìn)行計(jì)算，也可以利用匈牙利法進(jìn)行計(jì)算。計(jì)算得到的最佳安裝方案為：機(jī)器1安裝在地點(diǎn)4、機(jī)器2安裝在地點(diǎn)1、機(jī)器3安裝在地點(diǎn)3、機(jī)器4安裝在地點(diǎn)2，最小總安裝費(fèi)為14元。3.9 設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用的效果相同。各化肥廠年產(chǎn)量、各地區(qū)年需求量及從各化肥廠到各地區(qū)運(yùn)送單位化肥的運(yùn)價(jià)如表3-17所示。試確定使總運(yùn)費(fèi)最少的化肥調(diào)撥方案。表3-17 需求產(chǎn)地IIIIIIIV產(chǎn)量(萬噸)A1613221750B1413191560C192023-50最低需求(萬噸)最高需求(萬噸)3050707003010不限解：這是一個(gè)產(chǎn)銷不平衡的運(yùn)輸問題，總產(chǎn)量為160萬t，四個(gè)地區(qū)的最低需求為110萬t，最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，第IV個(gè)地區(qū)每年最多能分配到60萬t，這樣最高需求就為210萬t，大于產(chǎn)量。為了求得平衡，在產(chǎn)銷平衡表中增加一個(gè)假想的化肥廠D，其年產(chǎn)量為50萬t。由于各地區(qū)的需求量包含兩部分，如地區(qū)I，其中30萬t是最低需求，故不能由假想化肥廠D供給，令相應(yīng)的單位運(yùn)價(jià)為M（任意大的正數(shù)）；而另一部分20萬t滿足或不滿足均可以，因此可以由假想化肥廠D供給，按前述，可令相應(yīng)的單位運(yùn)價(jià)為0。對(duì)凡是需求分兩種情況的地區(qū)，實(shí)際上可按照兩個(gè)地區(qū)看待。這樣可以寫出這個(gè)問題的產(chǎn)銷平衡表（表3-18）和單位運(yùn)價(jià)表（表3-19）。并根據(jù)表上作業(yè)法，可以求得這個(gè)問題的最優(yōu)解，如表3-20所示。表3-18 銷地產(chǎn)地IIIIIIIIVIV產(chǎn)量A50B60C50D50銷量302070301050表3-19 銷地產(chǎn)地IIIIIIIIVIVA161613221717B141413191515C19192023MMDM0M0M0表3-20 銷地產(chǎn)地IIIIIIIIVIV產(chǎn)量A5050B20103060C3020050D302050銷量3020703010504.2 利用單純形法求解下列目標(biāo)規(guī)劃模型。（1）解：（1）本題的三個(gè)約束條件都是目標(biāo)約束，有三個(gè)負(fù)偏差變量，因此選擇負(fù)偏差變量為初始基變量。并計(jì)算出各非基變量的檢驗(yàn)數(shù)，得到初始的單純形表如表4-1所示。非基變量x1,x2的檢驗(yàn)數(shù)分別為1= -P1-2P2和2= -2P1 -2P2，它們的最高優(yōu)先級(jí)的系數(shù)都小于零，但2中P1的系數(shù)等于-2，其絕對(duì)值等于2，大于1中P1的系數(shù)的絕對(duì)值1，因此x2應(yīng)當(dāng)進(jìn)基。用最小比值法確定應(yīng)當(dāng)出基。換基后，通過計(jì)算求得新的基本可行解，如表4-2所示。表4-1cj00P100P1P20qCBXBbx1x2P1501 2 1-100002504021001-10040P2802200001-140jP1-1-2010100P2-2-2000001表4-2cj00P100P1P20qCBXBbx1x20x2251/211/2-1/2000050015 3/2 0-1/21/21-10010P23010-11001-130jP100100100P2-101-10001盡管x1與具有相同的負(fù)檢驗(yàn)數(shù)，但根據(jù)前面討論的原則，由于x1是決策變量，選擇x1進(jìn)基，用最小比值法確定出基，換基后，計(jì)算所得新的基本可行解如表4-3所示。表4-3cj00P100P1P20qCBXBbx1x20x220012/3-2/3-1/31/3000x11010-1/3 1/3 2/3-2/30030P22000-2/32/3-2/32/31-130jP100100100P2002/3-2/32/3-2/301首項(xiàng)系數(shù)小于零的檢驗(yàn)數(shù)只有的為，因此應(yīng)當(dāng)進(jìn)基，由于存在兩個(gè)最小比值，取下標(biāo)最小的變量出基，因此x1出基，換基后，再計(jì)算新的基本可行解，如表4-4所示。表4-4cj00P100P1P20qCBXBbx1x20x24021001-10003030-112-200P20-2000-221-1jP100100100P220002-201此時(shí)所有變量的檢驗(yàn)數(shù)的首項(xiàng)系數(shù)都已經(jīng)大于等于零，因此獲得了滿意解如下：x1=0,x2 =40,=30，其他偏差變量都等于零。4.3 某廠生產(chǎn)A、B、C三種產(chǎn)品，裝配工作在同一生產(chǎn)線上完成，三種產(chǎn)品時(shí)的工時(shí)消耗分別為6、8、10小時(shí)，生產(chǎn)線每月正常工作時(shí)間為200小時(shí)；三種產(chǎn)品銷售后，每臺(tái)可獲利分別為500、650和800元；每月銷售量預(yù)計(jì)為12、10和6臺(tái)。該廠經(jīng)營目標(biāo)如下：（1）利潤(rùn)指標(biāo)為每月16000元，爭(zhēng)取超額完成；（2）充分利用現(xiàn)有生產(chǎn)能力；（3）可以適當(dāng)加班，但加班時(shí)間不得超過24小時(shí)；（4）產(chǎn)量以預(yù)計(jì)銷售量為準(zhǔn)。試建立目標(biāo)規(guī)劃模型。 解：該問題的數(shù)學(xué)模型如下：5.2 計(jì)算從A到B、C和D的最短路。已知各段路線的長(zhǎng)度如圖5-1所示。圖5-1解：求從A到B、C和D的最短路等價(jià)于求從B、C和D到A的最短路。設(shè)階段變量k=1,2,3,4，依次表示4個(gè)階段選路得過程，第1階段從B、C或D出發(fā)到B3、C3或D3，第2階段從B3、C3或D3出發(fā)到B2、C2或D2，第3階段從B2、C2或D2出發(fā)到B1、C1或D1，第4階段從B1、C1或D1出發(fā)到A；狀態(tài)變量sk表示k階段初可能處的位置；決策變量xk表示k階段可能選擇的路線；階段指標(biāo)vk表示k階段與所選擇的路線相應(yīng)的路長(zhǎng)；指標(biāo)函數(shù)表示k至第4階段的總路長(zhǎng)；遞推公式計(jì)算過程如表5-1所示。 由表中計(jì)算結(jié)果可以看出：從B到A的最短路線為BC3C2B1A，最距離為16；從C到A的最短路線為CC3C2B1A或CD3C2B1A，最短距離為21；從D到A的最短路線為DD3C2B1A，最短距離為20。表5-1kskxkvkvk4=vk+fk+1fkxk*4B1A33+03AC1A88+08AD1A77+07A3B2B144+37B1C122+8C2B133+36B1C188+8D177+7D2C144+812C1D166+72B3B21010+717B2C21313+6C3B21212+711C2C255+6D266+12D3C277+613C2D288+121BB399+1716C3C355+11CB31010+1721C3、D3C31010+11D388+13DC31515+1120D3D377+135.3 某工業(yè)部門根據(jù)國家計(jì)劃的安排，擬將某種高效率的設(shè)備5臺(tái)，分配給所屬的甲、乙、丙三個(gè)工廠，各工廠若獲得這種設(shè)備之后，可以為國家提供的盈利如表5-2所示。表5-2 設(shè)備數(shù)工廠012345甲03791213乙0510111111丙046111212問：這5臺(tái)設(shè)備如何分配給各工廠，才能使國家得到的盈利最大？解：將問題按工廠分為3個(gè)階段，甲、乙、丙3個(gè)工廠分別編號(hào)為1、2、3；設(shè)sk表示分配給第k個(gè)工廠至第n個(gè)工廠的設(shè)備臺(tái)數(shù)；xk表示分配給第k個(gè)工廠的設(shè)備臺(tái)數(shù)；則sk+1=sk - xk為分配給第k+1個(gè)工廠至第n個(gè)工廠的設(shè)備臺(tái)數(shù)；Pk(xk)表示xk臺(tái)設(shè)備分配給第k個(gè)工廠所得得盈利值；fk(sk)表示sk臺(tái)設(shè)備分配給第k個(gè)工廠至第n個(gè)工廠時(shí)所得到得最大贏利值。由以上的假設(shè)可寫出逆推關(guān)系式為下面采用逆推法進(jìn)行計(jì)算。第3階段：設(shè)s3臺(tái)設(shè)備(s3=0,1,2,3,4,5)全部分配給工廠丙時(shí)，則最大贏利值為其中x3=s3=0,1,2,3,4,5。 因?yàn)榇藭r(shí)只有一個(gè)工廠，有多少臺(tái)設(shè)備就全部分配給工廠丙，故它的盈利值就是該段的最大盈利值。其數(shù)值計(jì)算如表5-3所示。表5-3表中表示使為最大值時(shí)的最優(yōu)決策。第2階段：設(shè)把s2臺(tái)設(shè)備(s2=0,1,2,3,4,5)分配給工廠乙和工廠丙時(shí)，則對(duì)每個(gè)s2值有一種最優(yōu)分配方案，使最大盈利值為其中x2=0,1,2,3,4,5。因?yàn)榻o乙工廠x2臺(tái)，其盈利為P2(x2)，余下的s2-x2臺(tái)就給丙工廠，則它的盈利最大值為f3(s2-x2)?，F(xiàn)要選擇x2的值使取最大值。其數(shù)值計(jì)算如表5-4所示。表5-4第1階段：設(shè)把s1臺(tái)(這里只有s1=5的情況)設(shè)備分配給甲乙丙3個(gè)工廠，則最大盈利值為其中x1=0,1,2,3,4,5。 因?yàn)榻o甲工廠x1臺(tái)，其盈利為P1(x1)，剩下的5-x1臺(tái)就分給一合丙兩個(gè)工廠，則它的盈利最大值為f2(5-x1)。現(xiàn)要選擇x1值使取最大值，它就是所求的總盈利最大值，其數(shù)值計(jì)算如表5-5所示。表5-5然后按計(jì)算表格的順序反推算，可知最優(yōu)方案有兩個(gè)：（1）由于，根據(jù)s2=s1 -=5 - 0=5，查表5-4知，由s3=s2 -=5-2=3，故。即甲工廠分配0臺(tái)、乙工廠分配2臺(tái)、丙工廠分配3臺(tái)。（2）由于，根據(jù)s2=s1 -=5 - 2=3，查表5-4知，由s3=s2 -=3-2=1，故。即甲工廠分配2臺(tái)、乙工廠分配2臺(tái)、丙工廠分配1臺(tái)。以上兩個(gè)分配方案所得的總盈利均為21萬元。在此問題中，如果原設(shè)備的太熟不是5臺(tái)，而是4臺(tái)或3臺(tái)，用其他方法求解時(shí)，往往需要從頭再算，但用動(dòng)態(tài)規(guī)劃求解時(shí)，這些列出的表仍舊有用，只需要修改最后的表格就可得到：當(dāng)設(shè)備臺(tái)數(shù)位4臺(tái)時(shí)，最優(yōu)分配方案為或，總盈利為17萬元。當(dāng)設(shè)備臺(tái)數(shù)位3臺(tái)時(shí)，最優(yōu)分配方案為：，總盈利為14萬元。5.4設(shè)有一輛載重量為15噸的卡車，要裝運(yùn)4種貨物。已知4種貨物的單位重量和價(jià)值如表5-6所示，在裝載重量許可的情況下每輛車裝載某種貨物的條件不限，試問如何搭配這4種貨物才能使每輛車裝載貨物的價(jià)值最大？ 表5-6貨物代號(hào)重量(噸)價(jià)值(千元)貨物代號(hào)重量(噸)價(jià)值(千元)123345234456解：設(shè)決策變量分別為4種貨物的裝載件數(shù)，則問題為一線性整數(shù)規(guī)劃： 將其轉(zhuǎn)化為動(dòng)態(tài)規(guī)劃問題，分為4個(gè)階段，每個(gè)階段的指標(biāo)函數(shù)記為， ， ， 狀態(tài)變量sk表示第k種至第4種貨物總允許載重量，即允許狀態(tài)集合為，最優(yōu)值函數(shù)表示裝載第k種至第4中貨物的價(jià)值，則動(dòng)態(tài)規(guī)劃模型為狀態(tài)轉(zhuǎn)移方程為允許決策集合為即表示在載重量允許的范圍內(nèi)可能裝載第k種貨物的件數(shù)。 用逆推方法求解如下：；。最后得到問題的最優(yōu)解為，最優(yōu)值為22千克。7.1 求解下列矩陣對(duì)策，其中贏得矩陣A分別為 （1） （2） （3） （4）解：（1）由于，所以A所對(duì)應(yīng)的支付矩陣沒有純對(duì)策。即局中人1以(0.36,0.36,0.27)的概率分別出策略1、2和3，其贏得值為-0.4545。（2）由于，所以A所對(duì)應(yīng)的支付矩陣沒有純對(duì)策。即局中人1以0.56、0.44的概率分別出策略1和策略2，贏得值為0.67.（3）根據(jù)贏得矩陣有，所以G的解為。（4）根據(jù)贏得矩陣有，所以G的解為。7.2 甲、乙兩家公司生產(chǎn)同一種產(chǎn)品，爭(zhēng)奪市場(chǎng)的占有率。假設(shè)兩家公司市場(chǎng)占有率之和為100，即顧客只購買這兩家公司的產(chǎn)品，無其他選擇。若公司甲可以采用的商業(yè)策略為A1、A2、A3，公司乙可以采用的商業(yè)策略為B1、B2、B3。表7-1給出在不同策略下公司甲的市場(chǎng)占有率。在此情況下，請(qǐng)為這兩家公司選擇他們的最優(yōu)策略。 表7-1B1B2B3A10.40.80.6A20.30.70.4A30.50.90.5解：若完全采用二人常數(shù)和對(duì)策的方法確定最優(yōu)純策略，則由可得，局中人甲采用策略A3、局中人乙采用策略B1，各獲得50%的市場(chǎng)占有率。從計(jì)算結(jié)果可以看出，局中人甲采用策略A3、局中人乙采用策略B1，各獲得50%的市場(chǎng)占有率。10.1某一決策問題的損益矩陣如表10-1所示，其中矩陣元素值為年利潤(rùn)。表10-1 單位：元 （1）若各事件發(fā)生的概率是未知的，分別用max min決策準(zhǔn)則、max max決策準(zhǔn)則、拉普拉斯準(zhǔn)則和最小機(jī)會(huì)損失準(zhǔn)則選出決策方案。 （2）若值仍是未知的，并且是樂觀系數(shù)，問取何值時(shí)，方案S1和S3是不偏不倚的？（3）若P1=0.2,P2=0.7,P3=0.1,那么用EMV準(zhǔn)則會(huì)選擇哪個(gè)方案？解：（1）采用maxmin準(zhǔn)則應(yīng)選擇方案S2，采用maxmax決策準(zhǔn)則應(yīng)選擇方案S1，采用Laplace準(zhǔn)則應(yīng)選擇方案S1，采用最小機(jī)會(huì)損失準(zhǔn)則應(yīng)選擇方案S1。（2）0.10256； （3）方案S1或S3。10.8假設(shè)有外表完全相同的木盒100只，將其分為兩組，一組內(nèi)裝白球，有70盒，另一組