【正文】 0，0，0，0 是基本可行解,min w=0第二階段最優(yōu)解（4/5，9/5，0，0，0，0 min z=7非基變量的檢驗(yàn)數(shù)=0，所以有無窮多最優(yōu)解。兩階段法（略）（4）解法一：大M法單純形法，（表略）非基變量的檢驗(yàn)數(shù)大于零，此線性規(guī)劃問題有無界解。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。（1）表中解為唯一最優(yōu)解；（2）表中解為最優(yōu)解，但存在無窮多最優(yōu)解；（3）該線性規(guī)劃問題具有無界解；（4）表中解非最優(yōu)，對解改進(jìn)，換入變量為，換出變量為。列出線型規(guī)劃模型。建立模型：Min z=+++++. +60 +70 +60 +50 +20 +30, 0、B、C加工成三種不同牌號的糖果甲乙丙，已知各種糖果中ABC含量，原料成本，各種原料的每月限制用量，三種牌號糖果的單位加工費(fèi)用及售價(jià)如表所示：原料甲乙丙原料成本（元/千克）每月限制用量（千克）A60%15%22000B2500C20%60%50%11200加工費(fèi)售價(jià)問該廠每月應(yīng)當(dāng)生產(chǎn)這三種牌號糖果各多少千克，使得獲利最大？建立數(shù)學(xué)模型。線性規(guī)劃模型：Max z=+++++++. ++ + ++ + + ++2000 ++2500 ++1200, 0、III。已知條件如下表，要求安排最優(yōu)生產(chǎn)計(jì)劃，使該廠利潤最大化?，F(xiàn)有5種飼料可供選擇，每種飼料每公斤營養(yǎng)成分的含量及單價(jià)如下表所示：試建立既滿足動(dòng)物生長需要，又使費(fèi)用最省的選用飼料方案的線性規(guī)劃模型。解題過程：第二章（67頁）。=(，)=,=（,，=(6,0).=(,), =（，=(0，2，3)，=,=非基變量的檢驗(yàn)數(shù) =（3，1，3）因?yàn)榈臋z驗(yàn)數(shù)為1，是正的最大數(shù)。=(，)=,=（,，=(6,2).=(,，), =（，=(0，0，3)，=,=非基變量的檢驗(yàn)數(shù) =（2，2，9）非基變量的檢驗(yàn)數(shù)均為負(fù)數(shù)，愿問題已達(dá)最優(yōu)解。（非基變量檢驗(yàn)數(shù)計(jì)算省略）原問題最優(yōu)解是X=（，0）目標(biāo)函數(shù)最優(yōu)值： z=12/5，用單純形法計(jì)算得到的中間某兩步的加算表見表，試將空白處數(shù)字填上。（1）min z= 2 +2 +4 2 +3 +5 23 + +7 3+4 +6 5 , 0（1）解：對偶問題是：Max w=235. 232 342 5764,0(2)max z= +2+3 +4 +3=56+7+3581299+920,0。無約束解：對偶問題：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。（2）如線性規(guī)劃的對偶問題無可行解，則原問題也一定無可行解。(1)錯(cuò)誤，原問題有可行解，對偶問題可能存在可行解，也可能不存在；（2）錯(cuò)誤，對偶問題沒有可行解，原問題可能有可行解也可能有無界解；（3）錯(cuò)誤，原問題和對偶問題都有可行解，則可能有有限最優(yōu)解也可能有無界解；：Max = ，i=1，2…，m（）是其對偶問題的最優(yōu)解。Max =CX. AXb+k X0k=（,...設(shè)可行解為，對偶問題最優(yōu)解是,對偶問題是，Min w=Y(b+k). YA C Y 0因?yàn)槭亲顑?yōu)解，所以（b+k）（b+k）是目標(biāo)函數(shù)的可行解，Ab+k ；A（b+k）b+Yk原問題和對偶問題的最優(yōu)函數(shù)值相等，所以不等式成立，證畢。有：=9/2； =1； =4； =5/2； =1； =2；=9； =5由檢驗(yàn)計(jì)算得：=3； ==0Max z=2++5+6 . 2++82+2++2120，j=1,…4對偶變量，其對偶問題的最優(yōu)解是=4，試應(yīng)用對偶問題的性質(zhì)，求原問題的最優(yōu)解。設(shè) X,Y是原問題和對偶問題的可行解，=（，）有：Y=0。（2）令：w=z，轉(zhuǎn)化為標(biāo)準(zhǔn)形式：Max w=324+0+0+0.245+=03+7+2+=2526+=15，0單純形法略原問題最優(yōu)解：X=（3，0，0，0，6，7，0 目標(biāo)函數(shù)最優(yōu)值為9。非基變量的檢驗(yàn)數(shù)等于0，原線性問題有無窮多最優(yōu)解。（2）約束條件右端常數(shù)變?yōu)?0 有 因此 單純形法解得，最優(yōu)解：X=（0，5，5，0，0 目標(biāo)函數(shù)最優(yōu)值為90。（4）的系數(shù)向量變?yōu)槭欠腔兞?，檢驗(yàn)數(shù)等于5，所以最優(yōu)解不變。（6）改變約束條件，沒有變化，線性規(guī)劃問題的最優(yōu)解不變。如A,B,C設(shè)備臺(tái)時(shí)不增加，分別回答這兩種新產(chǎn)品投產(chǎn)在經(jīng)濟(jì)上是否劃算？（4）對產(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í)，問這對原計(jì)劃有何影響？解：（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。所以，借用B設(shè)備不合算。單純形法計(jì)算得：最優(yōu)解：X=（107/4，31/2，0，0，0，0，55/4 目標(biāo)函數(shù)最優(yōu)值為10957/80。所以，改進(jìn)技術(shù)可以帶來更好的效益。（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，用單純形表計(jì)算，36t22t55t000B22t1001/4101/4055t2303/20101/204600202002[1]120z1350t1350t400t12t20t增大，t大于1，首先出現(xiàn)，大于0，所以當(dāng)0t1時(shí)有最優(yōu)解。t=1是第一臨界點(diǎn)。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開始增大時(shí)，當(dāng)t大于8/3時(shí)，首先出現(xiàn)大于0，所以0t8/3，得最優(yōu)解。當(dāng)8/3t5時(shí)，為換入變量，由規(guī)則，為換出變量，使用單純形法繼續(xù)迭代，t繼續(xù)增大，當(dāng)t5，首先大于0，8/3t5的時(shí)候，最優(yōu)解為：X=（0，15，0，5 目標(biāo)函數(shù)最優(yōu)值為180+15t ，（8/3t5）。當(dāng)t5時(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， t〉0(3)化成標(biāo)準(zhǔn)型，令t=0,用單純形法計(jì)算得：當(dāng)t開始增大，t大于5時(shí)，首先出現(xiàn)小于0，當(dāng)0t5，最優(yōu)解為：X=（10+2t，0，10+2t，5t，0 目標(biāo)函數(shù)最優(yōu)值為6t+30 ，（0t5）。當(dāng)t大于5時(shí)，是換出變量，是換入變量。（4）解：先化為標(biāo)準(zhǔn)型，令t=0，用單純形法計(jì)算，得：當(dāng)t開始增大，當(dāng)t大于6時(shí)，首先出現(xiàn)小于0，當(dāng)0t6，有最優(yōu)解：X=（0，0，0，10+t/3，0，183t，455t 目標(biāo)函數(shù)最優(yōu)值為150+5t （0t6）。試題：1. （2006年西北工業(yè)大學(xué)）已知線性規(guī)劃：（1） 用單純形法求解該線性規(guī)劃問題的最優(yōu)解和最優(yōu)值；（2） 寫出線性規(guī)劃的對偶問題；（3） 求解對偶問題的最優(yōu)解和最優(yōu)值。解題過程：，有無窮多解。解題過程：原問題的對偶問題為：由于（0，1，0）是上述對偶問題的可行解，由弱對偶性可知，對原問題的任一可行解都有 而，所以的最大值不大于1。表32中，有10個(gè)數(shù)字格，而作為初始解，應(yīng)該有m+n1=9個(gè)數(shù)字格，所以表32的調(diào)運(yùn)方案不能作為表上作業(yè)法的初始解。表33 銷地產(chǎn)地123產(chǎn)量15181222411433674銷量91011表34 銷地產(chǎn)地12345產(chǎn)量11023159252520152430315514715204201513M830銷量2020301025解：（1）在表33中分別計(jì)算出各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最右列和最下列。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素。 從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，丙列中的最小元素為3，由此可以確定產(chǎn)地2的產(chǎn)品應(yīng)先供應(yīng)丙的需要，而產(chǎn)地2的產(chǎn)量等于丙地的銷量，故在（2，丙）處填入0，同時(shí)將運(yùn)價(jià)表中的丙列和第二行的數(shù)字劃去，得到：銷地產(chǎn)地甲乙丙丁產(chǎn)量137452234353銷量332對上表中的元素分別計(jì)算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。又因?yàn)?0，此問題有無窮多最優(yōu)解。 從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，甲列是最大差額列，甲列的最小元素是5，所以產(chǎn)地3的產(chǎn)品先供應(yīng)甲的需求，同時(shí)將運(yùn)價(jià)表中產(chǎn)地3所在行的數(shù)字劃去。得到下表：銷地產(chǎn)地甲乙丙丁產(chǎn)量112142369344銷量5246使用位勢法進(jìn)行檢驗(yàn)：上表中，數(shù)字格處填入單位運(yùn)價(jià)，并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB，B為基，下同）來確定和.由=（+）（i，jN）計(jì)算所有空格的檢驗(yàn)數(shù)，并在每個(gè)格的右上角填入單位運(yùn)價(jià)，得到下表銷地產(chǎn)地甲乙丙丁11006712102 16810650902350431081045106711由上表可以看出，所有的非基變量檢驗(yàn)數(shù)≥0，此問題達(dá)到最優(yōu)解。總運(yùn)費(fèi)min z=118（3） 銷地產(chǎn)地甲乙丙丁戊產(chǎn)量11020591052210830663120710424863759銷量44624解：（3）此問題是一個(gè)產(chǎn)銷不平衡的問題，產(chǎn)大于銷。銷量為2