線性規(guī)劃課后題答案(張干宗)

P11.3（1）將下列線性規(guī)劃模型化成標(biāo)準(zhǔn)形式：解：令，代入上面的線性規(guī)劃，得標(biāo)準(zhǔn)形式P14:1、用圖解法求解下列線性規(guī)劃問題：利用圖解法：于是得最優(yōu)解為(4,1),最優(yōu)值為-10。P15：2解：利用圖解法于是最優(yōu)解為（6，0），最優(yōu)值為36。P15.3解：利用圖解法求得有無窮多最優(yōu)解，都落在一個(gè)線段上，該線段的兩個(gè)端點(diǎn)是：于是全部的最優(yōu)解可以表示成與的凸組合，即最優(yōu)值都是-21。P16:解：設(shè)表示第臺(tái)機(jī)床加工第類產(chǎn)品的產(chǎn)量，于是可得數(shù)學(xué)模型P16:解：設(shè)表示第食品的采購量，于是可得數(shù)學(xué)模型P18:9(2)將下列線性規(guī)劃問題變換成標(biāo)準(zhǔn)形式：解：令，則得P18:9(4)將下列線性規(guī)劃問題變換成標(biāo)準(zhǔn)形式：解：此題關(guān)鍵是將目標(biāo)函數(shù)中的絕對(duì)值去掉。令則有因此都是非負(fù)變量。于是原規(guī)劃可以化成標(biāo)準(zhǔn)形式：P1913、某養(yǎng)雞場有一萬只雞，用動(dòng)物飼料和谷物飼料混合喂養(yǎng)，每天每只雞平均吃混合飼料0.5公斤，其中動(dòng)物飼料占的比例不得少于1/5。動(dòng)物飼料每公斤0.2元，谷物飼料每公斤0.16元。飼料公司每周只保證供應(yīng)谷物飼料21000公斤。問飼料應(yīng)怎樣混合，才能使每天的總成本最低？試建立問題的數(shù)學(xué)模型并求解（圖解法）。解：設(shè)養(yǎng)雞場每天用動(dòng)物飼料和谷物飼料分別為公斤，則問題模型為用圖解法:求得其最優(yōu)解為。P19:14解:設(shè)甲乙廠各處理萬立方米/天；總費(fèi)用元/天；考慮工廠1與工廠2所在的兩點(diǎn)：工廠1：工廠2：于是建立數(shù)學(xué)模型為：目標(biāo)函數(shù)利用圖解法，畫圖求得其最優(yōu)解為：最優(yōu)值為：P37:1解：線性規(guī)劃問題由第一個(gè)約束的3倍減去第二個(gè)約束的2倍，得即（1）根據(jù)上式得到，再帶回第一個(gè)約束，整理得（2）由（1）、（2）表示出，帶入目標(biāo)函數(shù)，整理得于是整理得基對(duì)應(yīng)的典式為：根據(jù)典式，得基的基可行解是同樣根據(jù)典式，得基可行解的非基變量的檢驗(yàn)數(shù)是由于，因此不是最優(yōu)解。P37:3證明：先化成標(biāo)準(zhǔn)形式這個(gè)顯然是可行基對(duì)應(yīng)的典式，注意到，因此該線性規(guī)劃目標(biāo)值趨于負(fù)無窮，原線性規(guī)劃目標(biāo)函數(shù)趨于正無窮，即沒有最優(yōu)解。證畢。P46:用單純形法求解下列線性規(guī)劃問題：（1）解：先轉(zhuǎn)化成標(biāo)準(zhǔn)形式選為初始的基變量組，得單純形表X1X2X3X4X5X6f0-11-1000X4X5X623412-1110-211100010001f-2-201-100X2X5X621411-1100-2311-10010001f-7/3-7/300-2/3-1/30X2X3X68/31/311/35/31/3-4/31000101/3-1/31/32/31/3-1/3001最后一個(gè)單純形表的檢驗(yàn)數(shù)全部非正，得最優(yōu)解為最優(yōu)值為（2）解：選為初始的基變量組，化為典式：得單純形表X1X2X3X4f303-10X1X41/27101/21-1/2301f0-6020X2X4162-210-1401f-3-500-1/2X2X35/23/23/2-1/210011/41/4最后一個(gè)單純形表的檢驗(yàn)數(shù)全部非正，得最優(yōu)解為最優(yōu)值為P63：1.用兩階段法解下列線性規(guī)劃問題：解：首先化成標(biāo)準(zhǔn)形式由于上面的規(guī)劃的系數(shù)矩陣中存在一個(gè)單位向量，因此只需要在添加一個(gè)人工變量，構(gòu)造輔助問題：選為初始基變量組，化成典式：于是初始單純形表為：X1X2X3X4z42-100X3X434122-11001X1X2X3X4z0000-1X3X112015/2-1/210-1/21/2得輔助問題的最優(yōu)解，且此時(shí)人工變量已經(jīng)出基，因此得原問題的一個(gè)初始可行基及其不完全形式的典式（去掉上表中的人工變量列及檢驗(yàn)數(shù)行）：根據(jù)約束條件得，帶入目標(biāo)函數(shù)中，得典式：由于檢驗(yàn)數(shù)，因此應(yīng)用得到原問題的一個(gè)最優(yōu)解原問題的最優(yōu)值為P63：3.用兩階段法解下列線性規(guī)劃問題：解：先轉(zhuǎn)化成標(biāo)準(zhǔn)形式然后加入人工變量，構(gòu)造輔助問題：選為初始的基變量組，化成典式：得單純形表:X1X2X3X4X5X6z51-2-1-100X5X6232-1-31-100-11001z40-1/2-1/2-1-3/20X1X61410-3/2-1/2-1/2-1/20-11/21/201于是得到輔助問題的最優(yōu)解為：最優(yōu)值為由于，因此原問題無可行解。P75：對(duì)線性規(guī)劃問題驗(yàn)證是否為可行基？如果是，求出其典式。解：對(duì)于來說，為基變量，為非基變量。令，代入問題的約束中，得，于是得基解由于0，因此是一個(gè)可行基。下面將問題化成基的典式。約束條件轉(zhuǎn)換成。轉(zhuǎn)換成，即。轉(zhuǎn)換成。目標(biāo)函數(shù)。于是，基的典式為：P76：5（1）用單純形法求解下列線性規(guī)劃問題：解：將模型化為選為初始的基變量組，化成典式：單純形表為：X1X2X3X4X5z23002-4-3X1X2251001[1]2-100-1z19-200-2-3X3X2211-20110-120－1最后一個(gè)單純形表的檢驗(yàn)數(shù)全部非正，得最優(yōu)解為x＝(0,1,2)；最優(yōu)值為f＝19。P76：5（2）用單純形法求解下列線性規(guī)劃問題：解：選作為初始的基變量組，根據(jù)第二個(gè)約束求出，帶入目標(biāo)函數(shù)，整理得標(biāo)準(zhǔn)形式：于是，得單純形表：X1X2X3X4X5f15069/207100X4X5231/23/4-2/301/23/21001X1X2X3X4X5f8-1000-142/3X4X3121/41/2-2/300110-1/32/3最后一個(gè)單純形表的檢驗(yàn)數(shù)全部非正，得最優(yōu)解為最優(yōu)值為P7919對(duì)線性規(guī)劃問題：不經(jīng)單純形迭代，證明為其最優(yōu)基，并求出最優(yōu)解。解：先標(biāo)準(zhǔn)化：令，則于是因此對(duì)應(yīng)的基可行解為檢驗(yàn)數(shù)為：因此為其最優(yōu)基，即為最優(yōu)解。P99第4題：判斷下列關(guān)于對(duì)偶問題的說法是否正確：若原問題存在可行解，則其對(duì)偶問題必定存在可行解；（錯(cuò)誤，因?yàn)閷?duì)偶問題也可能無可行解）若對(duì)偶問題無可行解，則原問題必定無可行解；（錯(cuò)誤，因?yàn)閷?duì)偶問題也可能無界解，當(dāng)然此時(shí)對(duì)偶問題一定無最優(yōu)解）若原問題和對(duì)偶問題都有可行解，則兩者必都有最優(yōu)解。（正確）P99第5題：設(shè)LP有最優(yōu)解，并設(shè)(LP)’：有可行解。試?yán)脤?duì)偶理論證明：(LP)’必有最優(yōu)解。證：首先根據(jù)LP有最優(yōu)解及對(duì)偶理論知：一定存在最優(yōu)解，因此一定有可行解。又(LP)’的對(duì)偶問題是其約束與LP對(duì)偶規(guī)劃的約束一樣，因此根據(jù)LP的對(duì)偶存在可行解推知，其也存在可行解。結(jié)合對(duì)偶理論和(LP)’存在可行解知，(LP)’必有最優(yōu)解。證畢。P99第6題：解：所給線性規(guī)劃問題的對(duì)偶規(guī)劃是：由于對(duì)偶規(guī)劃只有兩個(gè)決策變量，因此可以利用比單純形法更簡單的圖解法來求解。利用圖解法求得：對(duì)偶問題的最優(yōu)解為：下面利用互補(bǔ)松弛性求解原問題的最優(yōu)解。由于因此它們的互補(bǔ)約束均為緊約束，即（1）又由于于是其對(duì)偶約束也是緊約束，即（2）將（2）帶入（1），得求解該方程得：于是原問題的最優(yōu)解為：P99：7、解：設(shè)分別表示A型，B型產(chǎn)品的產(chǎn)量，則所給問題的數(shù)學(xué)模型為：其對(duì)偶規(guī)劃為：先將原問題化成標(biāo)準(zhǔn)形式：選為初始的基變量組，做表如下：x1x2x3x4x5f’054000x39013100x48021010x54511001f’-20003/20-5/20x35005/21/2-1/20x14011/201/20x5501/20-1/21f’-215000-1-3x325001/22-5x1351001-1x210010-12于是所求問題的最優(yōu)解為：對(duì)偶問題的最優(yōu)解為：最優(yōu)值都是：P105:1、用對(duì)偶單純形法求解下列線性規(guī)劃問題：解：先將所給線性規(guī)劃問題轉(zhuǎn)化成：選作為初始基變量，作出如下初始單純形表：x1x2x3x4x5f0-5-2-400x4-4-3-1-210x5-10-6-3-501x1x2x3x4x5f20/3-10-2/30-2/3x4-2/3-10-1/31-1/3x210/3215/30-1/3x1x2x3x4x5f22/300-1/3-1-1/3X12/3101/3-11/3X220112-1于是所求問題的最優(yōu)解為：最優(yōu)值為：P105:2、用對(duì)偶單純形法求解下列線性規(guī)劃問題：解：先將所給線性規(guī)劃問題轉(zhuǎn)化成：選作為初始基變量，作出如下初始單純形表：x1x2x3x4x5x6f0-3-2-1000x46111100x5-4-101010X6-30-11001x1x2x3x4x5x6f120-2-40-30x42012110x1410-10-10X6-30-11001x1x2x3x4x5x6f1800-60-3-2x4-1003111x1410-10-10X2301-100-1由上面最后一個(gè)表格的第一行得方程：顯然上式與非負(fù)約束矛盾，因此該線性規(guī)劃沒有可行解。P105:3、用對(duì)偶單純形法求解下列線性規(guī)劃問題：解：先將所給線性規(guī)劃問題轉(zhuǎn)化成：選作為初始基變量，作出如下初始單純形表：x1x2x3x4x5x6f0-1-2-3000x4-4-21-1100x58112010X6-20-11001f20-5/2-5/2-1/200x121-1/21/2-1/200x5603/23/21/210x6-20-11001f700-5-1/20-5/2x1310-1-1/20-1/2x530031/213/2X2201-100-1于是所求問題的最優(yōu)解為：最優(yōu)值為：P111:解：先化成標(biāo)準(zhǔn)形式選做為初始基，建立擴(kuò)充問題：得如下單純形表：x1x2x3x4x5x6f0012000x141-1-1000x48012100X5-20-11010X6M011001讓x3進(jìn)基，x6離基，得x1x2x3x4x5x6f-20-1000-2x1M+4100001x48-20-1010-2X5-2-M0-2001-1X3M011001得到擴(kuò)充問題的一個(gè)正則解，繼續(xù)用對(duì)偶單純形法迭代，得：x1x2x3x4x5x6f-20-1000-2x1M+4100001x48-20-1010-2X5-2-M0-2001-1X3M011001f-8000-100X1M+4100001X2-8+2010-102X5-18+3000-213X38-M00110-1f-8000-100X112101100X28012100X46003110X6M-800-1-101于是得最優(yōu)解：最優(yōu)值：該問題最優(yōu)解不惟一，繼續(xù)迭代得：x1x2x3x4x5x6f-8000-100X112101100X28012100X46003110X6M-800-1-101f-8000-100X1101002/3-1/30X240101/3-2/30X320011/31/30X6M-6000-2/31/31于是得課后答案所給的最優(yōu)解：上面計(jì)算的Matlab程序?yàn)椋簊ymsMA=[001200041-1-10008012100-20-11010M011001];fori=1:4A(i,:)=A(i,:)+A(5,:)*(-A(i,4));endA(3,:)=-A(3,:);fori=[1245]A(i,:)=A(i,:)+A(3,:)*(-A(i,3));endA(5,:)=-A(5,:);fori=[1234]A(i,:)=A(i,:)+A(5,:)*(-A(i,7));endA(4,:)=A(4,:)/3;fori=[1235]A(i,:)=A(i,:)+A(4,:)*(-A(i,4));endP1112、解：添加人工約束，得到如下擴(kuò)充問題得如下單純形表：x1x2x3x4x5x6x7x8f00001-2-300x1171005-1510x2-22010-12-110X3-3300111-110X8M00011111讓x4進(jìn)基，x8離基，得x1x2x3x4x5x6x7x8f-M0000-3-4-1-1x117-5*M1000-60-4-5x2M-2201003021X3-M-3300100-20-1X4M00011111f-17/5-1/5000-9/5-4-1/50x8M-17/5-1/50006/504/51x2-93/51/51009/506/50X3-182/5-1/50106/5,24/50X417/51/5001-1/511/50于是根據(jù)x2行知，擴(kuò)充問題沒有可行解，于是原問題也沒有可行解。程序：symsMA=[00001-2-300171005-1510-22010-12-110-3300111-110M00011111];fori=1:4A(i,:)=A(i,:)+A(5,:)*(-A(i,5));endk1=2;k2=9;A(k1,:)=A(k1,:)/A(k1,k2);fori=[1345]A(i,:)=A(i,:)+A(k1,:)*(-A(i,k2));endP1123、解：添加人工約束，得到如下擴(kuò)充問題得如下表格：x1x2x3x4x5f0-12000x3-1-41100x45-12010X5M11001讓x2進(jìn)基，x5離基，得x1x2x3x4x5f-2-3000-2x3-M-1-5010-1x45-2-3001-2X2M11001得到擴(kuò)充問題的一個(gè)正則解，繼續(xù)用對(duì)偶單純形法迭代，得：x1x2x3x4x5f-2-3000-2x3-M-1-5010-1x45-2-3001-2X2M11001f-5000-10x3(7*M)/3-28/3001-5/37/3x1(2*M)/3-5/3100-1/3-2/3X2M/3+5/30101/31/3當(dāng)時(shí)，于是得原問題的無窮多最優(yōu)解：特別的取，得最優(yōu)解最優(yōu)值都是程序symsMA=[0-12000-1-411005-12010M11001];fori=1:3A(i,:)=A(i,:)+A(4,:)*(-A(i,3));endk1=3;k2=2;A(k1,:)=A(k1,:)/A(k1,k2);fori=[124]A(i,:)=A(i,:)+A(k1,:)*(-A(i,k2));endP119:解：對(duì)偶規(guī)劃為:利用圖解法求對(duì)偶規(guī)劃的最優(yōu)解：得對(duì)偶規(guī)劃的最優(yōu)解為:最優(yōu)值為下面利用互補(bǔ)松弛性求解原問題的最優(yōu)解：首先由于，都嚴(yán)格大于零，因此它們的對(duì)偶約束都為緊約束，即：（1）另一方面，將最優(yōu)解代入對(duì)偶的約束中，得：由于第二個(gè)約束為松約束，因此其對(duì)偶約束應(yīng)該是緊約束，于是將上式代入方程組（1），得求解，得于是原問題的最優(yōu)解為：P119:2解：對(duì)偶規(guī)劃為：P119:3證明：對(duì)偶規(guī)劃為：根據(jù)對(duì)偶理論，只要尋找對(duì)偶規(guī)劃的一個(gè)可行解，其對(duì)應(yīng)的目標(biāo)值小于等于1即可。顯然滿足這個(gè)條件，其對(duì)應(yīng)的目標(biāo)值等于1。證畢。P119:4證明：對(duì)偶規(guī)劃為：顯然對(duì)偶規(guī)劃的第一個(gè)約束與矛盾，因此對(duì)偶規(guī)劃沒有可行解。根據(jù)對(duì)偶理論，原規(guī)劃可能沒有可行解，也可能是無界解，因此原規(guī)劃一定沒有最優(yōu)解。證畢。P120:6證明：所給線性規(guī)劃的對(duì)偶規(guī)劃是由于為對(duì)稱方陣，且，令，則因此是對(duì)偶問題的可行解。又此時(shí)對(duì)偶的目標(biāo)函數(shù)為由對(duì)偶理論知，為原問題目標(biāo)值的一個(gè)下界。又因?yàn)檫@個(gè)下界，即為時(shí)原問題的目標(biāo)函數(shù)值，因此是原問題的最優(yōu)解。證畢。P120:7解：設(shè)(j=1，2，…，6)為第個(gè)時(shí)段開始上班的營業(yè)員，則這個(gè)問題的線性規(guī)劃模型為其對(duì)偶規(guī)劃為：將該對(duì)偶問題轉(zhuǎn)化成標(biāo)準(zhǔn)形式得：利用單純形法求解，選作為初始基變量：u1u2u3u4u5u6u7u8u9u10u11u12g’048107124000000u71110000100000u81011000010000u91001100001000u101000110000100u111000011000010u121100001000001u1u2u3u4u5u6u7u8u9u10u11u12g’-124810-504000-1200u71110000100000u81011000010000u91001100001000u51000110000100u110000-101000-110u121100001000001u1u2u3u4u5u6u7u8u9u10u11u12g’-224-20-5040-100-1200u71110000100000u31011000010000u900-101000-11000u51000110000100u110000-101000-110u121100001000001u1u2u3u4u5u6u7u8u9u10u11u12g’-260-60-504-4-100-1200u11110000100000u31011000010000u900-101000-11000u51000110000100u110000-101000-110u1200-10001-100001u1u2u3u4u5u6u7u8u9u10u11u12g’-260-60-100-4-100-8-40u11110000100000u31011000010000u900-101000-11000u51000110000100u60000-101000-110u1200-10100-1001-11于是由最優(yōu)表中松弛變量檢驗(yàn)數(shù)的相反數(shù)得原問題的最優(yōu)解為：P121:8、應(yīng)用對(duì)偶理論說明線性規(guī)劃問題及其對(duì)偶問題都有最優(yōu)解，并求最優(yōu)值的上界和下界。解：對(duì)偶問題為觀察可知，原問題有可行解：；對(duì)偶問題有可行解：。根據(jù)對(duì)偶基本定理，原問題和對(duì)偶問題都有最優(yōu)解，且最優(yōu)值，因此于是是最優(yōu)值的一個(gè)下界，是最優(yōu)值的一個(gè)上界。P121:9、已知線性規(guī)劃問題的最優(yōu)解為，試?yán)没パa(bǔ)松弛性質(zhì)，求出其對(duì)偶問題的最優(yōu)解。解：其對(duì)偶問題是：由原問題的最優(yōu)解知，原問題第4個(gè)約束為松約束，于是其對(duì)偶約束。又由已知得都不等于零，因此它們的對(duì)偶約束，即對(duì)偶問題的第1、2、3個(gè)約束均為緊約束：求解該方程組得：。因此對(duì)偶問題的最優(yōu)解P121：10、解：（1）因?yàn)樵瓎栴}的第個(gè)約束條件乘以常數(shù)，則對(duì)偶規(guī)劃的在目標(biāo)函數(shù)及約束中的系數(shù)全部變?yōu)樵鹊谋?，因此?duì)偶的可行解的第個(gè)分量變?yōu)樵鹊谋?，其余的分量不變。?）令為變化前對(duì)偶的可行解，為變化后對(duì)偶的可行解。令因?yàn)樵谠瓎栴}中，把第個(gè)約束的倍加到第個(gè)約束條件上，則相當(dāng)于將對(duì)偶規(guī)劃的列約束的倍加到第列上，為了抵消這種影響，只需要事實(shí)上，此時(shí)有其第個(gè)約束為：因此與原對(duì)偶規(guī)劃的第個(gè)約束為左邊相同。（3）當(dāng)原問題中所有的用替換時(shí)，對(duì)偶規(guī)劃約束的第個(gè)約束的中的數(shù)據(jù)都變成原來的3倍，因此約束的兩邊的3可以消掉，與原來的約束一樣。因此可行解不變。P122：11、證明：若滿足，則必定不是如下線性規(guī)劃問題的最優(yōu)解：證：顯然是該規(guī)劃的可行解，其對(duì)應(yīng)的目標(biāo)值為。假設(shè)是該線性規(guī)劃問題的最優(yōu)解，則其對(duì)偶規(guī)劃也有最優(yōu)解，設(shè)為，由互補(bǔ)松弛性和知：于是根據(jù)原規(guī)劃與對(duì)偶規(guī)劃最優(yōu)值相等，得再結(jié)合，知，這與矛盾。證畢。P122：12、證明：顯然該規(guī)劃可以拆成如下兩個(gè)線性規(guī)劃(1)和(2)顯然（1）與（2）是互為互補(bǔ)的關(guān)系。根據(jù)已知規(guī)劃存在可行解知，（1）與（2）皆存在可行解，因此再根據(jù)對(duì)偶定理知：，因此所給規(guī)劃的目標(biāo)函數(shù)有下界令。另外，根據(jù)對(duì)偶定理又知：（1）與（2）都存在最優(yōu)解，且最優(yōu)值相等，即存在是（1）的可行解，是（2）的可行解，且，于是是所給規(guī)劃的可行解，且目標(biāo)值。因此所給規(guī)劃有最優(yōu)解，且最優(yōu)值等于零。P131：具體說明平衡運(yùn)輸問題的約束方程組（4.2），（4.3）中任何一個(gè)方程都是其余個(gè)方程的線性組合。證明：因?yàn)槭瞧胶膺\(yùn)輸問題，所以線性方程組的增廣系數(shù)矩陣為在方程組中任取一個(gè)方程，如第個(gè)方程，由可知又結(jié)合上面兩個(gè)式子及已知的方程組中除第個(gè)方程外的方程成立，得因此方程組中的第個(gè)方程也成立，即其可由其余方程推出來，且是由后個(gè)方程之和減去前個(gè)中除了第個(gè)方程之外的和得到的。P137：1、(1)解：利用左上角法得到產(chǎn)量71×2×673094×212×31110511銷量101010利用最小元素法求得：產(chǎn)量×1×2767100×42212×31011511銷量101010P142：用位勢法計(jì)算習(xí)題4.2中第1題的兩個(gè)運(yùn)輸問題按最小元素法所得調(diào)運(yùn)方案的檢驗(yàn)數(shù)。解：考慮第1題的（1）426產(chǎn)量0×1×2767-4100×42212-1×31011511銷量101010于是得檢驗(yàn)數(shù)其他檢驗(yàn)數(shù)均為零。P149：1、用位勢法計(jì)算習(xí)題4.2中第1題的兩個(gè)運(yùn)輸問題，以最小元素法所得調(diào)運(yùn)方案為初始方案，用表上作業(yè)法求其最優(yōu)解。解：考慮第1題的（1）。由于選進(jìn)基，其對(duì)應(yīng)的閉回路為于是調(diào)整量，調(diào)整后的方案為：產(chǎn)量71×2×6730×49212×31011511銷量101010再求位勢，得1-13產(chǎn)量071×2×67-130×492122×31011511銷量101010于是得檢驗(yàn)數(shù)其他檢驗(yàn)數(shù)均為零。由于所有的檢驗(yàn)數(shù)均小于等于零，于是得最優(yōu)調(diào)運(yùn)方案:最小運(yùn)費(fèi)為:P154.1.(1)該運(yùn)輸問題屬于銷大于產(chǎn)的問題，且收點(diǎn)3的需求必須正好滿足，因此轉(zhuǎn)換成如下平衡運(yùn)輸問題：產(chǎn)量5261064680325150040銷量752050運(yùn)用最小元素法求得初始方案為：產(chǎn)量×5102×610306×45068053102×515400×0×40銷量752050再求位勢，得：323產(chǎn)量0×5102×6103306×450680053102×515-3400×0×40銷量752050于是得非基變量的檢驗(yàn)數(shù)為323產(chǎn)量0-2×5102-3×61033061×450680053102-2×515-3400-1×0-M×40銷量752050（以上三個(gè)表格可以合成一個(gè)表格，紅色為非基變量的檢驗(yàn)數(shù)）由于，因此讓進(jìn)基，同時(shí)其閉回路為，因此調(diào)整得新的運(yùn)輸方案為424產(chǎn)量0-1×5102-2×610220610450680-1153-1×2-2×515-4400-2×0-M×40銷量752050由于檢驗(yàn)數(shù)全非正，因此得最優(yōu)調(diào)運(yùn)方案：最小費(fèi)用為：P154.1.(2)該運(yùn)輸問題屬于產(chǎn)大于銷的問題，且收點(diǎn)1的需求必須由發(fā)電4供應(yīng)，因此轉(zhuǎn)換成如下平衡運(yùn)輸問題：產(chǎn)量100202401052015960015銷量5101530用最小元素法求初始調(diào)用方案，再求位勢，再求非基變量的檢驗(yàn)數(shù)得-MM-300產(chǎn)量0-2M×M-4×115050200-2M×M-5×2-4×41001000M-8×5-2×2150159-M591069-M×09-M×015銷量5101530由于，因此讓進(jìn)基，同時(shí)其閉回路為，因此調(diào)整得新的運(yùn)輸方案為2-100產(chǎn)量02-M×01150502002-M×-3×2-4×41001002-M×-6×5-2×2150157591067×07×015銷量5101530由于，因此讓進(jìn)基，同時(shí)其閉回路為，因此調(diào)整得新的運(yùn)輸方案為2100產(chǎn)量02-M×10150502002-M×-1×2-4×41001002-M×-4×5-2×215015059-5×61000×015銷量5101530由于檢驗(yàn)數(shù)全非正，因此得最優(yōu)調(diào)運(yùn)方案：最小費(fèi)用為：P154.2解：設(shè)變量xij表示第i季度正常生產(chǎn)的產(chǎn)品在第j季度銷售的臺(tái)數(shù)，變量yij表示第i季度正常生產(chǎn)的產(chǎn)品在第j季度銷售的臺(tái)數(shù)則決策變量集合為第1季度交貨第2季度交貨第3季度交貨第4季度交貨第1季度正常生產(chǎn)第1季度加班生產(chǎn)第2季度正常生產(chǎn)第2季度加班生產(chǎn)第3季度正常生產(chǎn)第3季度加班生產(chǎn)第4季度正常生產(chǎn)第4季度加班生產(chǎn)x11y11x12y12x22y22x13y13x23y23x33y33x14y14x24y24x34y34x44y44由于每臺(tái)積壓一個(gè)季度所需的存儲(chǔ)、維護(hù)等費(fèi)用為10元，因此得費(fèi)用表如下：第1季度交貨第2季度交貨第3季度交貨第4季度交貨第1季度正常生產(chǎn)第1季度加班生產(chǎn)第2季度正常生產(chǎn)第2季度加班生產(chǎn)第3季度正常生產(chǎn)第3季度加班生產(chǎn)第4季度正常生產(chǎn)第4季度加班生產(chǎn)200300MMMMMM210310200300MMMM220320210310200300MM230330220320210310200300則數(shù)學(xué)模型為：這是一個(gè)產(chǎn)大于銷的運(yùn)輸問題，利用表上作業(yè)法求解即可。最優(yōu)解為：200210220200-100產(chǎn)量010020002100220-30230-100010010020300031020320-3033010050-10190-M1502002102200150905030030310320080-20100200210010080100300310010002002000200100030050050銷量12020025020060P163.3.(1)對(duì)于以下列矩陣為系數(shù)矩陣的分派問題，求最小值分派：解：利用匈牙利法求解于是得最優(yōu)分派為：最優(yōu)值為：P1644、解:這是不平衡的指派問題，首先轉(zhuǎn)換為標(biāo)準(zhǔn)型，再用匈牙利法求解。由于地點(diǎn)數(shù)多于機(jī)床數(shù)，所以假定一臺(tái)虛擬的機(jī)床，設(shè)為4，則標(biāo)準(zhǔn)型的效率矩陣表示為：用匈牙利法求解于是得最優(yōu)解為：最優(yōu)值為：P1645.解：該分派問題為最大值類型，先轉(zhuǎn)換成最小值，用系數(shù)矩陣中的最大值減去該系數(shù)矩陣，得利用匈牙利法求解于是得最優(yōu)分派為：最優(yōu)值為：P167：7、在下表所示的運(yùn)輸問題中，總銷量超過總產(chǎn)量。設(shè)對(duì)銷地缺貨的單位懲罰成本分別為5,3,2,。求總費(fèi)用最少的調(diào)運(yùn)方案。產(chǎn)量517646325108015銷量752050解：屬于產(chǎn)銷不平衡的運(yùn)輸問題，增加一個(gè)產(chǎn)地，用最小元素求初始調(diào)運(yùn)方案，得：。用位勢法求解檢驗(yàn)數(shù)，得由于檢驗(yàn)數(shù)存在負(fù)數(shù)，因此不是最優(yōu)方案。用閉回路法調(diào)整得：再求檢驗(yàn)數(shù)，此時(shí)全小于等于零，因此是最優(yōu)方案。P168:12、解：先求最小值分派于是得最優(yōu)分派：或效率都是：1+3+3+4+2=13。再求最大值分派：先將其轉(zhuǎn)化為最小值分派，選效率矩陣的最大元素11，用11減去效率矩陣的每一個(gè)元素，得最小值分派問題于是得最優(yōu)分派：效率都是：9+10+10+7+9=45。P168:13、某學(xué)校為提高學(xué)生的學(xué)習(xí)興趣和加強(qiáng)學(xué)術(shù)氣氛，決定舉辦四個(gè)學(xué)術(shù)講座。講座在周一至周五的下午舉行。每個(gè)下午至多安排一個(gè)講座。經(jīng)調(diào)查周一至周五不能出席各講座的學(xué)生人數(shù)如下表。問如何安排講座日程，才使不能出席講座的學(xué)生人次最少？（用匈牙利方法求解）生態(tài)學(xué)能源運(yùn)輸生物工程星期一星期二星期三星期四星期五5040602040304030602030203030203010201030解：最優(yōu)解。周二不安排講座。P16914、某游泳隊(duì)教練員需選派一組運(yùn)動(dòng)員去參加4×100米混合接力賽，候選者有甲、乙、丙、丁和戊五位運(yùn)動(dòng)員，他們的百米仰泳、蛙泳、蝶泳和自由泳的成績(以秒計(jì))如表4-42所示．教練員應(yīng)選派哪四名運(yùn)動(dòng)員，各游哪種姿式，才使總成績最好?解：添加一項(xiàng)虛擬的任務(wù)，得效率矩陣于是得最優(yōu)分派為：甲為自由泳、乙為蝶泳、丙為仰泳、丁為蛙泳、戊不參加。P16915、解：根據(jù)已知條件得，需要添加一個(gè)虛設(shè)的零件。當(dāng)允許3號(hào)機(jī)床輪空時(shí)，所有的虛設(shè)零件對(duì)應(yīng)的加工時(shí)間為零。因此得如下的效率矩陣：于是得最優(yōu)分派為：零件1在4號(hào)機(jī)床加工、零件2在1號(hào)機(jī)床加工、零件3在2號(hào)機(jī)床加工、零件4在5號(hào)機(jī)床加工?？倳r(shí)間為2+7+6+7=22.當(dāng)不允許3號(hào)機(jī)床輪空時(shí)，3號(hào)機(jī)床加工虛設(shè)零件的時(shí)間為大M。因此得如下的效率矩陣：于是得最優(yōu)分派為：零件1在3號(hào)機(jī)床加工、零件2在1號(hào)機(jī)床加工、零件3在2號(hào)機(jī)床加工、零件4在5號(hào)機(jī)床加工?？倳r(shí)間為4+7+6+7=24.P212解：對(duì)線性規(guī)劃標(biāo)準(zhǔn)化得根據(jù)最優(yōu)單純形表，得最優(yōu)基的逆矩陣為(1)根據(jù)初始單純形表的b列和最優(yōu)單純形表的b列之間的關(guān)系，得于是得方程組：求解得：根據(jù)初始單純形表的檢驗(yàn)數(shù)行和最優(yōu)單純形表的檢驗(yàn)數(shù)行之間的關(guān)系，得于是得到方程組：求解，得（2）分析的變化范圍。根據(jù)得不等式組：求解，得如果，則且目標(biāo)函數(shù)變成了-6，將這些帶入最優(yōu)單純性表，得x1x2x3x4x5f-600-1/4-1/40x13103/8-1/80x2001-1/21/20x5-400-211利用對(duì)偶單純形法迭代，x5離基，x3進(jìn)基，得x1x2x3x4x5f-11/2000-3/8-1/8x19/41001/163/16x210101/4-1/4x32001-1/2-1/2于是得最優(yōu)解為最優(yōu)值為只需要考慮非基變量的檢驗(yàn)數(shù)，即于是得到不等式組：再結(jié)合都為正數(shù)，得P212.2解：（1）設(shè)分別表示甲、乙、丙的產(chǎn)量，則可建立如下線性規(guī)劃模型(2)將上面的模型化成標(biāo)準(zhǔn)形式，得利用原單純形法求解，得最優(yōu)表為x1x2x3x4x5x6f’-1350-400-1-20x2100-1/4101/2-1/40x32303/20101/20x620200-211于是最優(yōu)的生產(chǎn)方案是乙生產(chǎn)100件，丙生產(chǎn)230件。（3）先分析：根據(jù)求解得：因此的最大增量為10.再分析：根據(jù)求解得：因此的最大增量為400.最后分析：根據(jù)求解得：因此的最大增量為無窮.考慮各工序的影子價(jià)格，即最優(yōu)單純形表中檢驗(yàn)數(shù)的相反數(shù)，于是各工序的影子價(jià)格為（1，2，0）由于第二道工序的影子價(jià)格最大，因此應(yīng)該增加第二道工序的加工能力。相當(dāng)于增加了一個(gè)約束添加松弛變量，得將其添加到原最優(yōu)單純形表，得x1x2x3x4x5x6x7f’-1350-400-1-200x2100-1/4101/2-1/400x32303/20101/200x620200-2110x75484120001先將第2、3列化成單位向量，得x1x2x3x4x5x6x7f’-1350-400-1-200x2100-1/4101/2-1/400x32303/20101/200x620200-2110x7-125/400-1/2-3/401由于，因此用對(duì)偶單純形法迭代，得x1x2x3x4x5x6x7f’-1326-13/2000-1/20-2x2881100-101x32303/20101/200x668-300041-4x424-5/20013/20-2于是，得最優(yōu)解為最優(yōu)值為相當(dāng)于增加新變量，設(shè)新產(chǎn)品的產(chǎn)量為，則原模型變成在原最優(yōu)單純形表的檢驗(yàn)數(shù)為：因此新產(chǎn)品值得生產(chǎn)。再求出在原最優(yōu)單純形表上增加對(duì)應(yīng)的一列，得x1x2x3x4x5x6x7f’-1350-400-1-202x2100-1/4101/2-1/401x32303/20101/201x620200-2110然后按照原單純形法迭代，得x1x2x3x4x5x6x7f’-1550-7/2-20-2-3/200x7100-1/4101/2-1/401x31307/4-11-1/23/400x620200-2110于是得最優(yōu)生產(chǎn)方案為：丙生產(chǎn)130件，新產(chǎn)品生產(chǎn)100件。最大利潤為1550元，即利潤增加了200元。P225,4解：先化成標(biāo)準(zhǔn)形式當(dāng)時(shí)，用原單純形法得最優(yōu)表為：x1x2x3x4f-120-40-120x251/211/21/2x453/20-1/20對(duì)于一般