【正文】 表5—1工作所需工時工人Ⅰ9437Ⅱ4656Ⅲ5475Ⅳ7523Ⅴ10674試找出一個工作分配方案，使總工時最少。如果是型的，我們將如何利用和M呢？解：在m個約束條件右端分別減去M（是01變量，M是很大的常數(shù)，i=1，2…m）并且：（1）max z=4+3+2. 25+34 4++33+1,=0或1解：將（0，0，0）（0，0，1）（0，1，0）（1，0，0）（0，1，1）（1，0，1）（1，1，0）（1，1，1）分別帶入到約束條件中，可以得到：原問題的最優(yōu)解是（0，0，1），目標(biāo)函數(shù)最優(yōu)值2.（2）min z=2+5+3+4 . 4+++02+4+2+4++1，=0或1解：= 是一個可行解，目標(biāo)函數(shù)數(shù)值是4；所以可以增加約束條件：2+5+3+44把可能的解（0，0，0，0）（0，0，0，1）…（1，1，1，1）分別帶入約束條件的問題中，得到最優(yōu)解= ，目標(biāo)函數(shù)最優(yōu)值4.，指派他們完成4種工作，每人做各種工作所消耗的時間如下表，問指派哪個人去完成哪種工作，可以使得總耗時最??？ 任務(wù)人員ABCD甲15182124乙19232218丙26171619丁19212317解：系數(shù)矩陣C為：① 系數(shù)矩陣的每行元素減去該行的最小元素得矩陣B② B矩陣的每列元素減去該列的最小元素得到矩陣A此時，細(xì)數(shù)矩陣的每行每列都有元素0.先給加圈，然后給加圈，劃掉。 0將上述問題化為標(biāo)準(zhǔn)型，使用單純形法求解：=3，=2是最優(yōu)整數(shù)解，z=13.（2）max z=3+2.2+3142+9,0,是整數(shù)（2） 解：使用圖解法或者單純形法求解此問題，線性規(guī)劃問題最優(yōu)解是（13/4，5/2）目標(biāo)函數(shù)最優(yōu)值max z=59/4；湊整數(shù)時，=,是可行解，z=13；=，是非可行解；=，是非可行解；=，是非可行解；使用分支定界法求解原整數(shù)規(guī)劃問題，令令=59/4，==0是可行解。j=1,2,3)其中，z=(++)+5(++)+（++）6(++)(++)3(++)+試題：1. 某生產(chǎn)基地每天需從A、B兩倉庫中提取原材料用于生產(chǎn)，需提取的原材料有：原材料甲不少于240件，原材料乙不少于80公斤，原材料丙不少于120噸。（2）將此問題化為產(chǎn)銷平衡的運(yùn)輸問題，并求出一個初始基本可行解。甲乙丙A151822B212516解：此問題的供應(yīng)量小于需求量，假設(shè)供應(yīng)地C，產(chǎn)量為70萬噸。對上表中的元素分別計算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。最優(yōu)調(diào)運(yùn)方案不變，則所有非基變量的檢驗數(shù)都是非負(fù)。用伏格爾法求初始解：計算出各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最右列和最下行。 對上表中的元素分別計算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。得到下表：銷地產(chǎn)地甲乙丙丁產(chǎn)量112142369344銷量5246使用位勢法進(jìn)行檢驗：上表中，數(shù)字格處填入單位運(yùn)價，并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB，B為基，下同）來確定和.由=（+）（i，jN）計算所有空格的檢驗數(shù)，并在每個格的右上角填入單位運(yùn)價，得到下表銷地產(chǎn)地甲乙丙丁11006712102 16810650902350431081045106711由上表可以看出，所有的非基變量檢驗數(shù)≥0，此問題達(dá)到最優(yōu)解。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素。解題過程：，有無窮多解。當(dāng)t5時，是換入變量，為換出變量，單純性法計算，當(dāng)t繼續(xù)增大，所有檢驗數(shù)都非正，所以當(dāng)t5，最優(yōu)解：X=（15，0，0，5目標(biāo)函數(shù)最優(yōu)值為105+30t， t〉0(3)化成標(biāo)準(zhǔn)型，令t=0,用單純形法計算得：當(dāng)t開始增大，t大于5時，首先出現(xiàn)小于0，當(dāng)0t5，最優(yōu)解為：X=（10+2t，0，10+2t，5t，0 目標(biāo)函數(shù)最優(yōu)值為6t+30 ，（0t5）。（1）Max =(36t) +(22t) +(55t) (t0). +2+ 4303+2 460+4 420，0（2）Max =(7+2t)+(12+t) +(10t) (t0). ++ 202+2+ 30，0（3）Max =2+ (0 t 25). 10+2t + 25t 10+2t，0（4）Max =21+12+18+15 (0 t 59). 6+3+6+3 30+t63+12+6 78t9+36+9 1352t，0解：（1）化成標(biāo)準(zhǔn)形式：Max =(36t) +(22t) +(55t) +0+0+0 (t0). +2++=4303+2+=460+4+=420，, 0令t=0，用單純形表計算，36t22t55t000B22t1001/4101/4055t2303/20101/204600202002[1]120z1350t1350t400t12t20t增大，t大于1，首先出現(xiàn)，大于0，所以當(dāng)0t1時有最優(yōu)解。如A,B,C設(shè)備臺時不增加，分別回答這兩種新產(chǎn)品投產(chǎn)在經(jīng)濟(jì)上是否劃算？（4）對產(chǎn)品工藝重新進(jìn)行設(shè)計，改進(jìn)結(jié)構(gòu)，改進(jìn)后生產(chǎn)每件產(chǎn)品I，需要設(shè)備A為9臺時，設(shè)備B為12臺時，設(shè)備C為4臺時，問這對原計劃有何影響？解：（1）設(shè)：產(chǎn)品三種產(chǎn)品的產(chǎn)量分別為，建立數(shù)學(xué)模型：Max z=3+2+. 8+2+1030010+5+84002+13+10420,0把上述問題化為標(biāo)準(zhǔn)型，用單純形法解得：最優(yōu)解：X=（338/15，116/5，22/3，0，0，0 目標(biāo)函數(shù)最優(yōu)值為2029/15。非基變量的檢驗數(shù)等于0，原線性問題有無窮多最優(yōu)解。有：=9/2； =1； =4； =5/2； =1； =2；=9； =5由檢驗計算得：=3； ==0Max z=2++5+6 . 2++82+2++2120，j=1,…4對偶變量，其對偶問題的最優(yōu)解是=4，試應(yīng)用對偶問題的性質(zhì)，求原問題的最優(yōu)解。無約束解：對偶問題：Min w=5+8+20. +6+121 +792 +393 35+9=4無約束，0；0（3）min z= i=1,…,m j=1,…,n0解：對偶問題: max w=+. + , 無約束 i=1,2,….m。=(，)=,=（,，=(6,0).=(,), =（，=(0，2，3)，=,=非基變量的檢驗數(shù) =（3，1，3）因為的檢驗數(shù)為1，是正的最大數(shù)。線性規(guī)劃模型：Max z=+++++++. ++ + ++ + + ++2000 ++2500 ++1200, 0、III。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。，并指出屬于哪類解。l k 0時， 同號。，并指出單純形迭代每一步相當(dāng)于圖形的哪一點(diǎn)。（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）（圖略）無界解（4）（圖略）無可行解，并列出初始單純形表。（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ù)=(，)與線形無關(guān)，以（，）為基，為基變量。當(dāng)0時，目標(biāo)函數(shù)在C點(diǎn)有最大值當(dāng)0時，目標(biāo)函數(shù)在原點(diǎn)最大值。l k= 時， 同號。（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單純形表計算略當(dāng)所有非基變量為負(fù)數(shù)，人工變量=，所以原問題無可行解。解 ：設(shè)（k=1，2，3，4，5，6）為個司機(jī)和乘務(wù)人員第k班次開始上班。表 1—1飼料蛋白質(zhì)（克）礦物質(zhì)（克）維生素（毫克）價格（元/公斤）131221314622518解題分析：這是一道較簡單的數(shù)學(xué)規(guī)劃模型問題，根據(jù)題意寫出約束即可。354000b58/32/3101/300014/34/3052/310020/35/3042/3011/3045/300...15/418/4110/416/415/414/412/4112/4115/41解：354000b58/3014/3020/3...580/4101015/41450/410016/41344/411002/4100045/41。又設(shè)線性規(guī)劃問題2是Max + ，i=1，2…，m其中是給定的常數(shù)，求證： +解：證明：把原問題用矩陣表示：Max =CX. AXb X0b=（,...設(shè) 可行解為,對偶問題的最優(yōu)解=（，… ）已知。（1）min z=+ 2+4 +77 ,0(2) min z=3+2++42+4+5+ 03 +72 25+2++10 15 , , 0解：（1）取w=z，標(biāo)準(zhǔn)形式：Max w=+0+0. 2+=47+=7 ，0單純形法求解（略）：最優(yōu)解：X=（21/13，10/13，0，0 目標(biāo)函數(shù)最優(yōu)值為31/13。（5）解：加入約束條件用對偶單純形表計算得：X=（0，25/2，5/2，0，15，0 目標(biāo)函數(shù)最優(yōu)值為95。（4）改進(jìn)后,檢驗數(shù)=253/300，大于零。目標(biāo)函數(shù)最優(yōu)值Max =220，（0t8/3）所以，t=8/3為第一臨界點(diǎn)。當(dāng)t大于6時，首先出現(xiàn)小于0，是換出變量，是換入變量，使用單純形法計算得：t繼續(xù)增大，當(dāng)t大于11時，首先小于零，是換出