運(yùn)籌學(xué)第五版習(xí)題答案解析.doc

完美WORD格式 運(yùn)籌學(xué)習(xí)題答案第一章（39頁(yè)）1.1用圖解法求解下列線性規(guī)劃問(wèn)題，并指出問(wèn)題是具有唯一最優(yōu)解、無(wú)窮多最優(yōu)解、無(wú)界解還是無(wú)可行解。（1）max 5+1050+14，0（2）min z=+1.5+33+2，0（3）max z=2+2-1-0.5+2，0（4）max z=+-03-3，0解：（1）（圖略）有唯一可行解，max z=14（2）（圖略）有唯一可行解，min z=9/4（3）（圖略）無(wú)界解（4）（圖略）無(wú)可行解1.2將下列線性規(guī)劃問(wèn)題變換成標(biāo)準(zhǔn)型，并列出初始單純形表。（1）min z=-3+4-2+54-+2-=-2+3-14-2+3-+22，0，無(wú)約束（2）max 0 (i=1n; k=1,m)（1）解：設(shè)z=-,=-, ,0標(biāo)準(zhǔn)型：Max =3-4+2-5(-)+0+0-M-Ms. t . -4+-2+-+=2+3-+=14-2+3-+2-2-+=2,0 初始單純形表:3-42-5500-M-Mb-M2-41-21-100012014113-11100014-M2-23-12-20-1102/3-4M3-6M4M-42-3M3M-55-3M0-M00(2)解：加入人工變量，得：Max s=(1/)-M-M-.-Ms.t. (i=1,2,3,n)0, 0, (i=1,2,3n; k=1,2.,m)M是任意正整數(shù)初始單純形表：-M-M-Mb-M110011000-M10100000-M1001000111-snM0001.3在下面的線性規(guī)劃問(wèn)題中找出滿足約束條件的所有基解。指出哪些是基可行解，并代入目標(biāo)函數(shù)，確定最優(yōu)解。（1）max z=2+3+4+7 2+3-4=8 -2+6-7=-3,0(2)max z=5-2+3-6+2+3+4=72+2=30（1）解：系數(shù)矩陣A是：令A(yù)=(，)與線形無(wú)關(guān)，以（，）為基，為基變量。有 2+3=8+4 -2=-3-6+7令非基變量，=0解得：=1；=2基解=（1，2，0，0為可行解=8同理，以（，）為基，基解=（45/13，0，-14/13，0是非可行解；以（，）為基，基解=（34/5，0，0，7/5是可行解，=117/5；以（，）為基，基解=（0，45/16，7/16，0是可行解，=163/16；以（，）為基，基解=（0，68/29，0，-7/29是非可行解；以（，）為基，基解=（0，0，-68/31，-45/31是非可行解；最大值為=117/5；最優(yōu)解=（34/5，0，0，7/5。（2）解：系數(shù)矩陣A是：令A(yù)=(，)，線性無(wú)關(guān)，以（，）為基，有：+2=7-3-42+=3-2令 ，=0得=-1/3，=11/3 基解=（-1/3，11/3，0，0為非可行解；同理，以（，）為基，基解=（2/5，0，11/5，0是可行解=43/5；以（，）為基，基解=（-1/3，0，0，11/6是非可行解；以（，）為基，基解=（0，2，1，0是可行解，=-1；以（，）為基，基解=（0，0，1，1是=-3；最大值為=43/5；最優(yōu)解為=（2/5，0，11/5，0。1.4分別用圖解法和單純形法求解下列線性規(guī)劃問(wèn)題，并指出單純形迭代每一步相當(dāng)于圖形的哪一點(diǎn)。（1）max z=2+ 3+515 6+224，0（2）max z=2+542123+218，0解：（圖略）（1）max z=33/4 最優(yōu)解是(15/4,3/4)單純形法：標(biāo)準(zhǔn)型是max z=2+0+0s.t. 3+5+=15 6+2+=24 ,0單純形表計(jì)算：2100b0153510502462014-z0210003041-1/23/42411/301/612-z-801/30-1/313/4011/4-1/8215/410-1/125/24-z-33/400-1/12-7/24解為：（15/4，3/4，0，0 Max z=33/4迭代第一步表示原點(diǎn)；第二步代表C點(diǎn)（4，0，3，0；第三步代表B點(diǎn)（15/4，3/4，0，0 。（2）解：（圖略） Max z=34 此時(shí)坐標(biāo)點(diǎn)為（2，6）單純形法，標(biāo)準(zhǔn)型是：Max z=2+5+0+0+0s.t. +=4 2+=12 3+2+=18,0(表略)最優(yōu)解 X=（2，6，2，0，0 Max z=34迭代第一步得=（0，0，4，12，18表示原點(diǎn)，迭代第二步得=（0，6，4，0，6，第三步迭代得到最優(yōu)解的點(diǎn)。1.5以1.4題（1）為例，具體說(shuō)明當(dāng)目標(biāo)函數(shù)中變量的系數(shù)怎樣變動(dòng)時(shí)，滿足約束條件的可行域的每一個(gè)頂點(diǎn)，都可能使得目標(biāo)函數(shù)值達(dá)到最優(yōu)。解：目標(biāo)函數(shù)：max z=+(1)當(dāng)0時(shí) =-（/）+z/ 其中，k=-/=-3/5，=-3l k 時(shí)， ，同號(hào)。當(dāng)0時(shí)，目標(biāo)函數(shù)在C點(diǎn)有最大值當(dāng)0時(shí)，目標(biāo)函數(shù)在原點(diǎn)最大值。l k時(shí)，同號(hào)。當(dāng)0， 目標(biāo)函數(shù)在B點(diǎn)有最大值；當(dāng)0，目標(biāo)函數(shù)在原點(diǎn)最大值。l k 0時(shí)， 同號(hào)。當(dāng)0時(shí)，目標(biāo)函數(shù)在A點(diǎn)有最大值當(dāng)0時(shí)，目標(biāo)函數(shù)在原點(diǎn)最大值。l k 0時(shí)， ，異號(hào)。當(dāng)0， 0時(shí)，目標(biāo)函數(shù)在A點(diǎn)有最大值；當(dāng)0， 0時(shí)，目標(biāo)函數(shù)在C點(diǎn)最大值。l k= 時(shí)， 同號(hào)當(dāng)0時(shí)，目標(biāo)函數(shù)在AB線斷上任一點(diǎn)有最大值當(dāng)0，目標(biāo)函數(shù)在原點(diǎn)最大值。l k= 時(shí)， 同號(hào)。當(dāng)0時(shí)，目標(biāo)函數(shù)在BC線斷上任一點(diǎn)有最大值當(dāng)0時(shí)，目標(biāo)函數(shù)在原點(diǎn)最大值。l k=0時(shí)，=0當(dāng)0時(shí)，目標(biāo)函數(shù)在A點(diǎn)有最大值當(dāng)0，目標(biāo)函數(shù)在OC線斷上任一點(diǎn)有最大值（2）當(dāng)=0時(shí)，max z= l 0時(shí)，目標(biāo)函數(shù)在C點(diǎn)有最大值l 0時(shí)，目標(biāo)函數(shù)在OA線斷上任一點(diǎn)有最大值l =0時(shí)，在可行域任何一點(diǎn)取最大值。1.6分別用單純形法中的大M法和兩階段法求解下列線性問(wèn)題，并指出屬于哪類解。（1）max z=2+3-5+152-5+24，0（2）min z=2+3+4+283+26，0（3）max z=10+15+125+3+9-5+6+15152+5，0（4）max z=2-+2+6-2+22-0，0解：（1）解法一：大M法化為標(biāo)準(zhǔn)型：Max z=2+3-5-M+0-Ms.t. +=7 2-5+-+=10,0 M是任意大整數(shù)。單純形表：23-5-M0-Mb-M71111007-M102-510-115-z17M3M+23-4M2M-50-M0-M207/21/211/2-1/24/7251-5/21/20-1/21/2-z2M-100(7/2)M+80.5M-600.5M+1-1.5M-134/7011/72/71/7-1/7245/7106/75/7-1/71/7-z-102/700-50/7-M-16/7-1/7-M+1/7最優(yōu)解是： X=（45/7，4/7，0，0，0 目標(biāo)函數(shù)最優(yōu)值 max z=102/7有唯一最優(yōu)解。解法二：第一階段數(shù)學(xué)模型為 min w= + S.t. + + =72 -5 + - + =10,，,0（單純形表略）最優(yōu)解X=（45/7，4/7，0，0，0 目標(biāo)函數(shù)最優(yōu)值 min w=0第二階段單純形表為：23-50b34/7011/71/7245/7106/7-1/7-z-102/700-50/7-1/7最優(yōu)解是X=（45/7，4/7，0，0，0 Max z=102/7（2）解法一：大M法=-z 有max =-min （-）=-min z化成標(biāo)準(zhǔn)形：Max =-2-3-+0+0-M-MS.T. +4+2-+=4 3+2-+=6 ,，,，0（單純性表計(jì)算略）線性規(guī)劃最優(yōu)解X=（4/5，9/5，0，0，0 ，0 目標(biāo)函數(shù)最優(yōu)值 min z=7非基變量的檢驗(yàn)數(shù)=0，所以有無(wú)窮多最優(yōu)解。兩階段法：第一階段最優(yōu)解X=（4/5，9/5，0，0，0，0 是基本可行解,min w=0第二階段最優(yōu)解（4/5，9/5，0，0，0，0 min z=7非基變量的檢驗(yàn)數(shù)=0，所以有無(wú)窮多最優(yōu)解。（3）解：大M法加入人工變量，化成標(biāo)準(zhǔn)型：Max z=10 +15 +12 +0 +0 +0 -M s.t. 5 +3 + + =9 -5 +6 +15 + =15 2 + + - + =5 ,，,，0單純形表計(jì)算略當(dāng)所有非基變量為負(fù)數(shù)，人工變量=0.5，所以原問(wèn)題無(wú)可行解。兩階段法（略）（4）解法一：大M法單純形法，（表略）非基變量的檢驗(yàn)數(shù)大于零，此線性規(guī)劃問(wèn)題有無(wú)界解。兩階段法略1.7求下述線性規(guī)劃問(wèn)題目標(biāo)函數(shù)z的上界和下界；Max z=+其中：，解：l 求Z的上界Max z=3+6s.t. -+212 2+414，0加入松弛變量，化成標(biāo)準(zhǔn)型，用單純形法解的，最優(yōu)解X=（0，7/2，5，0 目標(biāo)函數(shù)上界為z=21存在非基變量檢驗(yàn)數(shù)等于零，所以有無(wú)窮多最優(yōu)解。l 求z的下界線性規(guī)劃模型：Max Z= +4s.t. 3+58 4+610 ，0加入松弛變量，化成標(biāo)準(zhǔn)型，解得：最優(yōu)解為X=（0，8/5，0，1/5 目標(biāo)函數(shù)下界是z=32/51.8表1-6是某求極大化線性規(guī)劃問(wèn)題計(jì)算得到的單純形表。表中無(wú)人工變量，d，為待定常數(shù)，試說(shuō)明這些常數(shù)分別取何值時(shí)，以下結(jié)論成立。（1）表中解為唯一最優(yōu)解；（2）表中解為最優(yōu)解，但存在無(wú)窮多最優(yōu)解；（3）該線性規(guī)劃問(wèn)題具有無(wú)界解；（4）表中解非最優(yōu)，對(duì)解改進(jìn)，換入變量為，換出變量為?；鵥 d4100 2-1-301-10 3-500-4100-30解：（1）有唯一最優(yōu)解時(shí)，d0，0，0（2）存在無(wú)窮多最優(yōu)解時(shí)，d0，0，=0或d0，=0，0.（3）有無(wú)界解時(shí)，d0，0，0且（4）此時(shí)，有d0，0并且，3/d/41.9某晝夜服務(wù)的公交線路每天個(gè)時(shí)間段內(nèi)所需司機(jī)和乘務(wù)員人數(shù)如下：班次時(shí)間所需人數(shù)16點(diǎn)到10點(diǎn)60210點(diǎn)到14點(diǎn)70314點(diǎn)到18點(diǎn)60418點(diǎn)到22點(diǎn)50522點(diǎn)到2點(diǎn)2062點(diǎn)到6點(diǎn)30設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間區(qū)段一開(kāi)始時(shí)上班，并連續(xù)上班8小時(shí)，問(wèn)該公交線路至少配備多少司機(jī)和乘務(wù)人員。列出線型規(guī)劃模型。解 ：設(shè)（k=1，2，3，4，5，6）為個(gè)司機(jī)和乘務(wù)人員第k班次開(kāi)始上班。建立模型：Min z=+s.t. +60 +70 +60 +50 +20 +30, 01.10某糖果公司廠用原料A、B、C加工成三種不同牌號(hào)的糖果甲乙丙，已知各種糖果中ABC含量，原料成本，各種原料的每月限制用量，三種牌號(hào)糖果的單位加工費(fèi)用及售價(jià)如表所示：原料甲乙丙原料成本（元/千克）每月限制用量（千克）A60%15%22000B1.52500C20%60%50%11200加工費(fèi)0.50.40.3售價(jià)3.42.852.25問(wèn)該廠每月應(yīng)當(dāng)生產(chǎn)這三種牌號(hào)糖果各多少千克，使得獲利最大？建立數(shù)學(xué)模型。解:解：設(shè)，是甲糖果中的A，B，C成分，是乙糖果的A，B，C成分，是丙糖果的A，B，C成分。線性規(guī)劃模型：Max z=0.9+1.4+1.9+0.45+0.95+1.45-0.05+0.45+0.95s.t. -0.4+0.6+0.60 -0.2-0.2+0.80 -0.85+0.15+0.150 -0.6-0.6+0.40 -0.7-0.5+0.50 +2000 +2500 +1200, 01.11某廠生產(chǎn)三種產(chǎn)品I、III。每種產(chǎn)品經(jīng)過(guò)AB兩道加工程序，該廠有兩種設(shè)備能完成A工序，他們以,表示；有三種設(shè)備完成B工序，分別為，；產(chǎn)品I可以在AB任何一種設(shè)備上加工，產(chǎn)品可以在任何規(guī)格的A設(shè)備上加工，但完成B工序時(shí)，只能在設(shè)備上加工；產(chǎn)品III只能在，上加工。已知條件如下表，要求安排最優(yōu)生產(chǎn)計(jì)劃，使該廠利潤(rùn)最大化。設(shè)備產(chǎn)品設(shè)備有效臺(tái)時(shí)滿負(fù)荷時(shí)的設(shè)備費(fèi)用IIIIII5106000300791210000321684000250411700078374000200原料費(fèi)0.250.350.5單價(jià)1.252.002.8解：產(chǎn)品1，設(shè),完成A工序的產(chǎn)品，件；B工序時(shí)，,，完成B工序的，件，產(chǎn)品，設(shè),完成A工序的產(chǎn)品，件；B工序時(shí)，完成B的產(chǎn)品為件；產(chǎn)品111，完成A工序的件，完成B工序的件；+ = + + + = 建立數(shù)學(xué)模型：Max z=(1.25-0.25)*( + )+(2-0.35)*( + )+(2.8-0.5) -(5 +10 )300/6000-(7 +9 +12 )321/10000-(6 +8 )250/4000-(4 +11 )783/7000-7 *200/4000s.t 5 +10 60007 +9 +12 100006 +8 40004 +11 70007 4000+ = + + + = , 0最優(yōu)解為X=（1200，230，0，859，571，0，500，500，324 最優(yōu)值1147.試題：1. （2005年華南理工大學(xué)）設(shè)某種動(dòng)物每天至少需要700克蛋白質(zhì)、30克礦物質(zhì)、100毫克維生素?，F(xiàn)有5種飼料可供選擇，每種飼料每公斤營(yíng)養(yǎng)成分的含量及單價(jià)如下表所示：試建立既滿足動(dòng)物生長(zhǎng)需要，又使費(fèi)用最省的選用飼料方案的線性規(guī)劃模型。表 11飼料蛋白質(zhì)（克）礦物質(zhì)（克）維生素（毫克）價(jià)格（元/公斤）1310.50.2220.510.7310.20.20.446220.35180.50.80.8解題分析：這是一道較簡(jiǎn)單的數(shù)學(xué)規(guī)劃模型問(wèn)題，根據(jù)題意寫(xiě)出約束即可。解題過(guò)程：第二章（67頁(yè)）2.1用改進(jìn)單純形法求解以下線性規(guī)劃問(wèn)題。（1）Max z=6-2+32-+32+44，0（2）min z=2+3+=34+36+23,0解：（1）先化成標(biāo)準(zhǔn)型：Max z=6-2+3+0+0s.t. 2-+2+=2 +4+=4 , 0令=（，）= =（,=(0,0)=(,)= , =（，=(6,-2,3)，=,=非基變量的檢驗(yàn)數(shù)=-=(6,-2,3)因?yàn)榈臋z驗(yàn)數(shù)等于6，是最大值，所以，為換入變量，=；=由規(guī)則得：=1為換出變量。=(，)=,=（,，=(6,0).=(,), =（，=(0，-2，3)，=,=非基變量的檢驗(yàn)數(shù) =（-3，1，-3）因?yàn)榈臋z驗(yàn)數(shù)為1，是正的最大數(shù)。所以為換入變量；=由規(guī)則得：=6所以是換出變量。=(，)=,=（,，=(6,-2).=(,，), =（，=(0，0，3)，=,=非基變量的檢驗(yàn)數(shù) =（-2，-2，-9）非基變量的檢驗(yàn)數(shù)均為負(fù)數(shù)，愿問(wèn)題已達(dá)最優(yōu)解。最優(yōu)解X= 即：X=（4,6,0目標(biāo)函數(shù)最優(yōu)值 max z=12 （2） 解 ：Min z=2+0+M+M+0S.T. 3+=34+3-+=6+2+=3, 0M是任意大的正數(shù)。（非基變量檢驗(yàn)數(shù)計(jì)算省略）原問(wèn)題最優(yōu)解是X=（0.6，1.2，0）目標(biāo)函數(shù)最優(yōu)值： z=12/52.2已知某線性規(guī)劃問(wèn)題，用單純形法計(jì)算得到的中間某兩步的加算表見(jiàn)表，試將空白處數(shù)字填上。354000b58/32/3101/300014/3-4/305-2/310020/35/304-2/301-1/304-5/300.15/418/41-10/41-6/415/414/41-2/41-12/4115/41-解：354000b58/3014/3020/3-.580/4101015/41450/41001-6/41344/41100-2/41-000-45/412.3寫(xiě)出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題。（1）min z= 2 +2 +4 2 +3 +5 23 + +7 3+4 +6 5 , 0（1）解：對(duì)偶問(wèn)題是：Max w=2-3-5s.t. 2-3-2 3-42 5-7-64,0(2)max z= +2+3 +4 -+-3=56+7+3-5812-9-9+920,0; 0;無(wú)約束解：對(duì)偶問(wèn)題：Min w=5+8+20S.t. -+6+121 +7-92 -+3-93 -3-5+9=4無(wú)約束，0；0（3）min z= i=1,m j=1,n0解：對(duì)偶問(wèn)題: max w=+s.t. + , 無(wú)約束 i=1,2,.m; j=1,2,.n(4)Max z=, i=1,., , i=0,當(dāng)j=1，.，無(wú)約束，當(dāng)j=解：Min w=s.t. j=1,2,3 j=+1, +2,.n0 i=1,2. 無(wú)約束， i=+1, +2.m2.4判斷下列說(shuō)法是否正確，并說(shuō)明為什么.(1)如線性規(guī)劃問(wèn)題的原文題存在可行解，則其對(duì)偶問(wèn)題也一定存在可行解。（2）如線性規(guī)劃的對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題也一定無(wú)可行解。（3）如果線性規(guī)劃問(wèn)題的原問(wèn)題和對(duì)偶問(wèn)題都具有可行解，則該線性規(guī)劃問(wèn)題一定有有限最優(yōu)解。(1)錯(cuò)誤，原問(wèn)題有可行解，對(duì)偶問(wèn)題可能存在可行解，也可能不存在；（2）錯(cuò)誤，對(duì)偶問(wèn)題沒(méi)有可行解，原問(wèn)題可能有可行解也可能有無(wú)界解；（3）錯(cuò)誤，原問(wèn)題和對(duì)偶問(wèn)題都有可行解，則可能有有限最優(yōu)解也可能有無(wú)界解；2.5設(shè)線性規(guī)劃問(wèn)題1是：Max = ，i=1，2，m（）是其對(duì)偶問(wèn)題的最優(yōu)解。又設(shè)線性規(guī)劃問(wèn)題2是Max + ，i=1，2，m其中是給定的常數(shù)，求證： +解：證明：把原問(wèn)題用矩陣表示：Max =CXs.t. AXb X0b=（,.設(shè) 可行解為,對(duì)偶問(wèn)題的最優(yōu)解=（， ）已知。Max =CXs.t. AXb+k X0k=（,.設(shè)可行解為，對(duì)偶問(wèn)題最優(yōu)解是,對(duì)偶問(wèn)題是，Min w=Y(b+k)S.t. YA C Y 0因?yàn)槭亲顑?yōu)解，所以（b+k）（b+k）是目標(biāo)函數(shù)的可行解，Ab+k ；A（b+k）b+Yk原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)函數(shù)值相等，所以不等式成立，證畢。2.6已知線性規(guī)劃問(wèn)題 Max z=用單純形法求解，得到最終單純形表如表所示，要求：（1） 求，的值；（2） 求的值；3/21011/2-1/221/210-12-3000-4解：（1）初始單純形表的增廣矩陣是：=最終單純形表的增廣矩陣為=是作初等變換得來(lái)的，將作初等變換，使得的第四列和第五列的矩陣成為的單位矩陣。有：=9/2； =1； =4； =5/2； =1； =2；=9； =5由檢驗(yàn)計(jì)算得：=-3； =02.7已知線性規(guī)劃問(wèn)題Max z=2+5+6 s.t. 2+82+2+2120，j=1,4對(duì)偶變量，其對(duì)偶問(wèn)題的最優(yōu)解是=4，試應(yīng)用對(duì)偶問(wèn)題的性質(zhì)，求原問(wèn)題的最優(yōu)解。解：對(duì)偶問(wèn)題是：Min w=8+12 s.t. 2+22 21 +5 +26 ，0互補(bǔ)松弛性可知，如，是原問(wèn)題和對(duì)偶問(wèn)題的可行解，那么，=0和=0，當(dāng)且僅當(dāng)，是最優(yōu)解。設(shè) X,Y是原問(wèn)題和對(duì)偶問(wèn)題的可行解，=（，）有：Y=0; 且 X=0=0，原問(wèn)題約束條件取等號(hào)，=4；=4最優(yōu)解X=（0，0，4，4 目標(biāo)函數(shù)最優(yōu)值為44。2.8試用對(duì)偶單純形法求解下列線性規(guī)劃問(wèn)題。（1）min z=+ 2+4 +77 ,0(2) min z=3+2+42+4+5+ 03- +7-2 25+2+10 15 , , 0解：（1）取w=-z，標(biāo)準(zhǔn)形式：Max w=-+0+0s.t. -2-+=-4-7+=-7 ，0單純形法求解（略）：最優(yōu)解：X=（21/13，10/13，0，0 目標(biāo)函數(shù)最優(yōu)值為31/13。（2）令：w=-z，轉(zhuǎn)化為標(biāo)準(zhǔn)形式：Max w=-3-2-4+0+0+0s.t.-2-4-5-+=0-3+-7+2+=-2-5-2-6+=-15，0單純形法略原問(wèn)題最優(yōu)解：X=（3，0，0，0，6，7，0 目標(biāo)函數(shù)最優(yōu)值為9。2.9現(xiàn)有線性規(guī)劃問(wèn)題max z=- 5+5+13- +3 2012 +4+10 90 ， 0先用單純形法求出最優(yōu)解，然后分析在下列各種條件下，最優(yōu)解分別有什么變化？（1） 約束條件1的右端常數(shù)20變?yōu)?0（2） 約束條件2的右端常數(shù)90變?yōu)?0（3） 目標(biāo)函數(shù)中的系數(shù)變?yōu)?（4） 的系數(shù)向量變?yōu)椋?） 增加一個(gè)約束條件2+3+550（6） 將約束條件2變?yōu)?0+5+10100解： 把原問(wèn)題化成標(biāo)準(zhǔn)型的：Max z=-5 +5 +13 +0 +0 s.t- + +3 + =2012 +4 +10 + =90，0單純形法解得：最優(yōu)解：X=（0，20，0，0，10 目標(biāo)函數(shù)最優(yōu)值為100。非基變量的檢驗(yàn)數(shù)等于0，原線性問(wèn)題有無(wú)窮多最優(yōu)解。（1）約束條件的右端常數(shù)變?yōu)?0有 因此 單純形法解得：最優(yōu)解：X=（0，0，9，3，0 目標(biāo)函數(shù)最優(yōu)值為117。（2）約束條件右端常數(shù)變?yōu)?0 有 因此 單純形法解得，最優(yōu)解：X=（0，5，5，0，0 目標(biāo)函數(shù)最優(yōu)值為90。（3）的系數(shù)變成8，是非基變量，檢驗(yàn)數(shù)小于0，所以最優(yōu)解不變。（4）的系數(shù)向量變?yōu)槭欠腔兞?，檢驗(yàn)數(shù)等于-5，所以最優(yōu)解不變。（5）解：加入約束條件用對(duì)偶單純形表計(jì)算得：X=（0，25/2，5/2，0，15，0 目標(biāo)函數(shù)最優(yōu)值為95。（6）改變約束條件，沒(méi)有變化，線性規(guī)劃問(wèn)題的最優(yōu)解不變。2.10已知某工廠計(jì)劃生產(chǎn)I,II,III三種產(chǎn)品，各產(chǎn)品在ABC設(shè)備上加工，數(shù)據(jù)如下表，設(shè)備代號(hào)IIIIII每月設(shè)備有效臺(tái)時(shí)A8210300B1058400C21310420單位產(chǎn)品利潤(rùn)/千元322.9（1）如何充分發(fā)揮設(shè)備能力，使生產(chǎn)盈利最大？（2）如果為了增加產(chǎn)量，可借用其他工廠的設(shè)備B，每月可借用60臺(tái)時(shí)，租金為1.8萬(wàn)元，問(wèn)借用是否合算？（3）若另有兩種新產(chǎn)品IV,V，其中IV為10臺(tái)時(shí)，單位產(chǎn)品利潤(rùn)2.1千元；新產(chǎn)品V需用設(shè)備A為4臺(tái)時(shí)，B為4臺(tái)時(shí)，C為12臺(tái)時(shí)，單位產(chǎn)品盈利1.87千元。如A,B,C設(shè)備臺(tái)時(shí)不增加，分別回答這兩種新產(chǎn)品投產(chǎn)在經(jīng)濟(jì)上是否劃算？（4）對(duì)產(chǎn)品工藝重新進(jìn)行設(shè)計(jì)，改進(jìn)結(jié)構(gòu)，改進(jìn)后生產(chǎn)每件產(chǎn)品I，需要設(shè)備A為9臺(tái)時(shí)，設(shè)備B為12臺(tái)時(shí)，設(shè)備C為4臺(tái)時(shí)，單位產(chǎn)品利潤(rùn)4.5千元，問(wèn)這對(duì)原計(jì)劃有何影響？解：（1）設(shè)：產(chǎn)品三種產(chǎn)品的產(chǎn)量分別為，建立數(shù)學(xué)模型：Max z=3+2+2.9s.t. 8+2+1030010+5+84002+13+10420,0把上述問(wèn)題化為標(biāo)準(zhǔn)型，用單純形法解得：最優(yōu)解：X=（338/15，116/5，22/3，0，0，0 目標(biāo)函數(shù)最優(yōu)值為2029/15。（2）設(shè)備B的影子價(jià)格為4/15千元/臺(tái)時(shí)，借用設(shè)備的租金為0.3千元每臺(tái)時(shí)。所以，借用B設(shè)備不合算。（3）設(shè)備,V生產(chǎn)的產(chǎn)量為，系數(shù)向量分別為：檢驗(yàn)數(shù)=-0.06，所以生產(chǎn)不合算，=37/300，生產(chǎn)V合算。單純形法計(jì)算得：最優(yōu)解：X=（107/4，31/2，0，0，0，0，55/4 目標(biāo)函數(shù)最優(yōu)值為10957/80。（4）改進(jìn)后,檢驗(yàn)數(shù)=253/300，大于零。所以，改進(jìn)技術(shù)可以帶來(lái)更好的效益。2.11分析下列參數(shù)規(guī)劃中當(dāng)t變化時(shí)最優(yōu)解的變化情況。（1）Max =(3-6t) +(2-2t) +(5-5t) (t0)s.t. +2+ 4303+2 460+4 420，0（2）Max =(7+2t)+(12+t) +(10-t) (t0)s.t. + 202+2+ 30，0（3）Max =2+ (0 t 25)s.t. 10+2t + 25-t 10+2t，0（4）Max =21+12+18+15 (0 t 59)s.t. 6+3+6+3 30+t6-3+12+6 78-t9+3-6+9 135-2t，0解：（1）化成標(biāo)準(zhǔn)形式：Max =(3-6t) +(2-2t) +(5-5t) +0+0+0 (t0)s.t. +2+=4303+2+=460+4+=420，, 0令t=0，用單純形表計(jì)算，3-6t2-2t5-5t000B2-2t100-1/4100.5-1/40-5-5t2303/20101/20460020200-21120-z1350t-1350t-400t-12t-20t增大，t大于1，首先出現(xiàn)，大于0，所以當(dāng)0t1時(shí)有最優(yōu)解。X=（0，100，230，0，0，20 目標(biāo)函數(shù)最優(yōu)值為1350（t-1） （0t1）。t=1是第一臨界點(diǎn)。t大于1時(shí)，是換出變量。t大于1，最優(yōu)解是：X=（0，0， 0，430，460，420目標(biāo)函數(shù)最優(yōu)值為Max =0， （t大于1）（2）化成標(biāo)準(zhǔn)型，然后令t=0，單純形法解得：t開(kāi)始增大時(shí)，當(dāng)t大于8/3時(shí)，首先出現(xiàn)大于0，所以0t8/3，得最優(yōu)解。目標(biāo)函數(shù)最優(yōu)值Max =220，（0t8/3）所以，t=8/3為第一臨界點(diǎn)。當(dāng)8/3t5，首先大于0，8/3t5的時(shí)候，最優(yōu)解為：X=（0，15，0，5 目標(biāo)函數(shù)最優(yōu)值為180+15t ，（8/35時(shí)，是換入變量，為換出變量，單純性法計(jì)算，當(dāng)t繼續(xù)增大，所有檢驗(yàn)數(shù)都非正，所以當(dāng)t5，最優(yōu)解：X=（15，0，0，5目標(biāo)函數(shù)最優(yōu)值為105+30t， t0(3)化成標(biāo)準(zhǔn)型，令t=0,用單純形法計(jì)算得：當(dāng)t開(kāi)始增大，t大于5時(shí)，首先出現(xiàn)小于0，當(dāng)0t5，最優(yōu)解為：X=（10+2t，0，10+2t，5-t，0 目標(biāo)函數(shù)最優(yōu)值為6t+30 ，（0t5）。所以t=5是第一臨界點(diǎn)。當(dāng)t大于5時(shí)，是換出變量，是換入變量。用對(duì)偶單純形法計(jì)算，當(dāng)t大于5時(shí)，最優(yōu)解為：X=（10+2t，15+t，0，0，t-5 目標(biāo)函數(shù)最優(yōu)值為35+5t。（4）解：先化為標(biāo)準(zhǔn)型，令t=0，用單純形法計(jì)算，得：當(dāng)t開(kāi)始增大，當(dāng)t大于6時(shí)，首先出現(xiàn)小于0，當(dāng)0t6，有最優(yōu)解：X=（0，0，0，10+t/3，0，18-3t，45-5t 目標(biāo)函數(shù)最優(yōu)值為150+5t （0t6）。當(dāng)t大于6時(shí)，首先出現(xiàn)小于0，是換出變量，是換入變量，使用單純形法計(jì)算得：t繼續(xù)增大，當(dāng)t大于11時(shí)，首先小于零，是換出變量，為換入變量，對(duì)偶單純形法迭代得：當(dāng) t59，有最優(yōu)解：X=（0，t/3-2，t/8-11/8，59/4-t/4，0，0，0 目標(biāo)函數(shù)最優(yōu)值為5t/2+345/2 ，（11t59）。試題：1. （2006年西北工業(yè)大學(xué)）已知線性規(guī)劃：（1） 用單純形法求解該線性規(guī)劃問(wèn)題的最優(yōu)解和最優(yōu)值；（2） 寫(xiě)出線性規(guī)劃的對(duì)偶問(wèn)題；（3） 求解對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)值。解題分析：本題考察了線性規(guī)劃與對(duì)偶問(wèn)題的知識(shí)，要求讀者熟知對(duì)偶理論。解題過(guò)程：，有無(wú)窮多解。對(duì)偶問(wèn)題為： 2. （2005年?yáng)|南大學(xué)）寫(xiě)出如下線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題：無(wú)限制并利用弱對(duì)偶性說(shuō)明的最大值不大于1。解題過(guò)程：原問(wèn)題的對(duì)偶問(wèn)題為：由于（0，1，0）是上述對(duì)偶問(wèn)題的可行解，由弱對(duì)偶性可知，對(duì)原問(wèn)題的任一可行解都有 而，所以的最大值不大于1。第三章（86頁(yè)）3.1判斷表中給出的調(diào)運(yùn)方案能否作為用表上作業(yè)法求解時(shí)的最初解？為什么？表31銷(xiāo)地產(chǎn)地1234產(chǎn)量1015152151025355銷(xiāo)量5151510表32銷(xiāo)地產(chǎn)地12345產(chǎn)量1150250400220030050032505030049021030058020100銷(xiāo)量24041055033070解：表31中，有5個(gè)數(shù)字格，作為初始解，應(yīng)該有m+n-1=3+4-1=6個(gè)數(shù)字格，所以表3-1的調(diào)運(yùn)方案不能作為用表上作業(yè)法求解時(shí)的初始解。表3-2中，有10個(gè)數(shù)字格，而作為初始解，應(yīng)該有m+n-1=9個(gè)數(shù)字格，所以表3-2的調(diào)運(yùn)方案不能作為表上作業(yè)法的初始解。3.2表3-3和表3-4中分別給出兩個(gè)運(yùn)輸問(wèn)題的產(chǎn)銷(xiāo)平衡表和單位運(yùn)價(jià)表，試用伏格爾法直接給出近似最優(yōu)解。表3-3 銷(xiāo)地產(chǎn)地123產(chǎn)量15181222411433674銷(xiāo)量91011表3-4 銷(xiāo)地產(chǎn)地12345產(chǎn)量11023159252520152430315514715204201513M830銷(xiāo)量2020301025解：（1）在表3-3中分別計(jì)算出各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最右列和最下列。得到： 銷(xiāo)地 產(chǎn)地123行差額151842241133673列差額136從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，上表中，第三列是最大差額列，此列中最小元素為1，由此可以確定產(chǎn)地2的產(chǎn)品應(yīng)先供應(yīng)給銷(xiāo)售地3，得到下表： 銷(xiāo)地 產(chǎn)地123產(chǎn)量1111221434銷(xiāo)量91011同時(shí)將運(yùn)價(jià)表第三列數(shù)字劃去，得 銷(xiāo)地 產(chǎn)地12產(chǎn)量15112224143364銷(xiāo)量910對(duì)上表中的元素，計(jì)算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最右列和最下列，重復(fù)上面的步驟，直到求出初始解，最終結(jié)果是： 銷(xiāo)地 產(chǎn)地123產(chǎn)量121012231114344銷(xiāo)量91011（2）3-4分別計(jì)算出各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最右列和最下列。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素。（方法同3-3相同）最終得出原問(wèn)題的初始解： 銷(xiāo)地產(chǎn)地12345產(chǎn)量12522030320430銷(xiāo)量20203010253.3用表上作業(yè)法求給出運(yùn)輸問(wèn)題的最優(yōu)解（M是任意大正數(shù)）（1）銷(xiāo)地產(chǎn)地甲乙丙丁產(chǎn)量137645224322343853銷(xiāo)量3322解：（1）計(jì)算出各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最右列和最下列。 從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，丙列中的最小元素為3，由此可以確定產(chǎn)地2的產(chǎn)品應(yīng)先供應(yīng)丙的需要，而產(chǎn)地2的產(chǎn)量等于丙地的銷(xiāo)量，故在（2，丙）處填入0，同時(shí)將運(yùn)價(jià)表中的丙列和第二行的數(shù)字劃去，得到：銷(xiāo)地產(chǎn)地甲乙丙丁產(chǎn)量137452234353銷(xiāo)量332對(duì)上表中的元素分別計(jì)算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。得到下表：銷(xiāo)地產(chǎn)地甲乙丙丁產(chǎn)量132522023033銷(xiāo)量3322使用位勢(shì)法進(jìn)行檢驗(yàn)：上表中，數(shù)字格處填入單位運(yùn)價(jià)并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令+=（i，jB，B為基，下同）來(lái)確定和，得到下表：銷(xiāo)地產(chǎn)地甲乙丙丁1340232-234313254由=-（+）（i，j為非基，下同）計(jì)算所有空格的檢驗(yàn)數(shù)，并在每個(gè)格的右上角填入單位運(yùn)價(jià)，得到下表銷(xiāo)地產(chǎn)地甲乙丙丁13075614002 21443020-234030825013254由上表可以看出，所有的非基變量檢驗(yàn)數(shù)0，此問(wèn)題達(dá)到最優(yōu)解。又因?yàn)?0，此問(wèn)題有無(wú)窮多最優(yōu)解?？傔\(yùn)費(fèi)min z=3*3+3*3+2*3+2*4=32（2）銷(xiāo)地產(chǎn)地甲乙丙丁產(chǎn)量110671242161059935410104銷(xiāo)量5246解：（2）計(jì)算出各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最右列和最下列。 從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，甲列是最大差額列，甲列的最小元素是5，所以產(chǎn)地3的產(chǎn)品先供應(yīng)甲的需求，同時(shí)將運(yùn)價(jià)表中產(chǎn)地3所在行的數(shù)字劃去。 對(duì)上表中的元素分別計(jì)算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。得到下表：銷(xiāo)地產(chǎn)地甲乙丙丁產(chǎn)量112142369344銷(xiāo)量5246使用位勢(shì)法進(jìn)行檢驗(yàn)：上表中，數(shù)字格處填入單位運(yùn)價(jià)，并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB，B為基，下同）來(lái)確定和.由=-（+）（i，jN）計(jì)算所有空格的檢驗(yàn)數(shù)，并在每個(gè)格的右上角填入單位運(yùn)價(jià)，得到下表銷(xiāo)地產(chǎn)地甲乙丙丁11006712102 1681065090-235043108104-5106711由上表可以看出，所有的非基變量檢驗(yàn)數(shù)0，此問(wèn)題達(dá)到最優(yōu)解。此問(wèn)題有唯一最優(yōu)解?？傔\(yùn)費(fèi)min z=118（3） 銷(xiāo)地產(chǎn)地甲乙丙丁戊產(chǎn)量11020591052210830663120710424863759銷(xiāo)量44624解：（3）此問(wèn)題是一個(gè)產(chǎn)銷(xiāo)不平衡的問(wèn)題，產(chǎn)大于銷(xiāo)。增加一個(gè)假象銷(xiāo)售地己，令單位運(yùn)價(jià)為0。銷(xiāo)量為2。這樣就達(dá)到了產(chǎn)銷(xiāo)平衡。用伏格爾法求初始解：計(jì)算出各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最右列和最下列。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，產(chǎn)地1所在的行是最大差額行，最小元素0，說(shuō)以一產(chǎn)地的產(chǎn)品應(yīng)該優(yōu)先供應(yīng)己的需要，同時(shí)劃掉己列的數(shù)字。 對(duì)上表中的元素分別計(jì)算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。得到下表： 銷(xiāo)地產(chǎn)地甲乙丙丁戊己產(chǎn)量1325242632244329銷(xiāo)量446242使用位勢(shì)法進(jìn)行檢驗(yàn)：上表中，數(shù)字格處填入單位運(yùn)價(jià)，并增加一行一列，在列中填入（i=1，2，3，4），在行中填入（j=1，2，3，4，5，6），先令=0，由 +=（i，jB，B為基，下同）來(lái)確定和.由=-（+）（i，jN）計(jì)算所有空格的檢驗(yàn)數(shù)，并在每個(gè)格的右上角填入單位運(yùn)價(jià)。由上表可以看出，所有的非基變量檢驗(yàn)數(shù)0，此問(wèn)題達(dá)到最優(yōu)解。又因?yàn)?0，此問(wèn)題有無(wú)窮多最優(yōu)解。總運(yùn)費(fèi)min z=90（4） 銷(xiāo)地產(chǎn)地甲乙丙丁戊產(chǎn)量1 1018291322100213M211416120306113M1404911231819805242836303460銷(xiāo)量1001201006080解：（4）此問(wèn)題是一個(gè)產(chǎn)銷(xiāo)不平衡的問(wèn)題，產(chǎn)大于銷(xiāo)。增加一個(gè)假象銷(xiāo)售地己，令單位運(yùn)價(jià)為0。銷(xiāo)量為40。這樣就達(dá)到了產(chǎn)銷(xiāo)平衡。用伏格爾法求初始解：計(jì)算出各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最右列和最下行。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，同時(shí)劃掉所在列或行的元素。 對(duì)上表中的元素分別計(jì)算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。并用位勢(shì)法進(jìn)行檢驗(yàn)： 銷(xiāo)地產(chǎn)地甲乙丙丁戊己1 1018229813022601202133MM-1621014116001203006011030MM-6022-104941102371810198017-552422803633053460121016211316-12由上表可以看出，所有的非基變量檢驗(yàn)數(shù)0，此問(wèn)題達(dá)到最優(yōu)解。又因?yàn)?0，此問(wèn)題有無(wú)窮多最優(yōu)解?？傔\(yùn)費(fèi)min z=55203.4已知運(yùn)輸問(wèn)題的產(chǎn)銷(xiāo)平衡表、單位運(yùn)價(jià)表及最優(yōu)調(diào)運(yùn)方案如下表所示表1 銷(xiāo)地產(chǎn)地產(chǎn)量51015010152555銷(xiāo)量5151510表2 銷(xiāo)地產(chǎn)地10120111279202141618（1）到的單位運(yùn)價(jià)在什么范圍變化時(shí)，上述最優(yōu)方案不變？（2）到的單位運(yùn)價(jià)變?yōu)楹沃禃r(shí)，有無(wú)窮多最優(yōu)方案。除表1中方案外，至少寫(xiě)出其他兩個(gè)。解：(1)在對(duì)應(yīng)表的數(shù)字格處（未知）填入單位運(yùn)價(jià)，并增加一行，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB）來(lái)確定和.由=-（+）（i，jN）計(jì)算所有空格的檢驗(yàn)數(shù)，并在每個(gè)格的右上角填入單位運(yùn)價(jià)（未知）。最優(yōu)調(diào)運(yùn)方案不變，則所有非基變量的檢驗(yàn)數(shù)都是非負(fù)。所以：-30+10010-024-018-0解得:310單位運(yùn)價(jià)在此區(qū)間變化時(shí)，最優(yōu)調(diào)運(yùn)方案不變。（2）在對(duì)應(yīng)表的數(shù)字格處（未知）填入單位運(yùn)價(jià)，并增加一行，在列中