【正文】 第 64 頁(yè) 共 64 頁(yè)運(yùn)籌學(xué)習(xí)題答案第一章（39頁(yè)），并指出問(wèn)題是具有唯一最優(yōu)解、無(wú)窮多最優(yōu)解、無(wú)界解還是無(wú)可行解。（1）max 5+1050+14，0（2）min z=++33+2，0（3）max z=2+21+2，0（4）max z=+033，0解：（1）（圖略）有唯一可行解，max z=14（2）（圖略）有唯一可行解，min z=9/4（3）（圖略）無(wú)界解（4）（圖略）無(wú)可行解，并列出初始單純形表。（1）min z=3+42+54+2=2++3142+3+22，0，無(wú)約束（2）max 0 (i=1…n。 k=1,…,m)（1）解：設(shè)z=,=, ,0標(biāo)準(zhǔn)型：Max =34+25()+0+0MMs. t . 4+2++=2++3++=142+3+22+=2,,0 初始單純形表:3425500MMbM2412110001201411311100014M22[3]12201102/34M36M4M423M3M553M0M00(2)解：加入人工變量，，…，得：Max s=(1/)MM…..M. (i=1,2,3…,n)0, 0, (i=1,2,3…n。 k=1,2….,m)M是任意正整數(shù)初始單純形表：MM…M………b…………M110…011……00…0M101…00……00…0…………………………………………M100…100…0…11…1snM00…0………。指出哪些是基可行解，并代入目標(biāo)函數(shù)，確定最優(yōu)解。（1）max z=2+3+4+7 2+34=8 2+67=3,0(2)max z=52+36+2+3+4=72+++2=30（1）解：系數(shù)矩陣A是：令A(yù)=(，，)與線形無(wú)關(guān)，以（，）為基，為基變量。有 2+3=8++4 2=36+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=7342+=32令 ，=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。，并指出單純形迭代每一步相當(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+0. 3+5+=15 6+2+=24 ,0單純形表計(jì)算：2100b01535105024[6]2014z02100030[4]11/23/42411/301/612z801/301/313/4011/41/8215/4101/125/24z33/4001/127/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+0. +=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）為例，具體說(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)取最大值。，并指出屬于哪類(lèi)解。（1）max z=2+35++1525+24，0（2）min z=2+3++4+283+26，0（3）max z=10+15+125+3+95+6+15152++5，0（4）max z=2+2++62+220，0解：（1）解法一：大M法化為標(biāo)準(zhǔn)型：Max z=2+35M+0M. +++=7 25++=10,,0 M是任意大整數(shù)。單純形表：235M0MbM71111007M10[2]510115z17M3M+234M2M50M0M20[7/2]1/211/21/24/72515/21/201/21/2z2M100(7/2)M+80+134/7011/72/71/71/7245/7106/75/71/71/7z102/70050/7M16/71/7M+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= + . ++ + =72 5 + + =10,，,0（單純形表略）最優(yōu)解X=（45/7，4/7，0，0，0 目標(biāo)函數(shù)最優(yōu)值 min w=0第二階段單純形表為：2350b34/7011/71/7245/7106/71/7z102/70050/71/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 =23+0+0MM. +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 . 5 +3 + + =9 5 +6 +15 + =15 2 + + + =5 ,，,，0單純形表計(jì)算略當(dāng)所有非基變量為負(fù)數(shù)，人工變量=，所以原問(wèn)題無(wú)可行解。兩階段法（略）（4）解法一：大M法單純形法，（表略）非基變量的檢驗(yàn)數(shù)大于零，此線性規(guī)劃問(wèn)題有無(wú)界解。兩階段法略；Max z=+其中：，，，，解：l 求Z的上界Max z=3+6. +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= +4. 3+58 4+610 ，0加入松弛變量，化成標(biāo)準(zhǔn)型，解得：最優(yōu)解為X=（0，8/5，0，1/5 目標(biāo)函數(shù)下界是z=32/5。表中無(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)，換入變量為，換出變量為。基b d4100 2130110 3500410030解：（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/4：班次時(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=+++++. +60