【文章內(nèi)容簡介】 設(shè)備B，每月可借用60臺時，問借用是否合算？（3）若另有兩種新產(chǎn)品IV,V，其中IV為10臺時，；新產(chǎn)品V需用設(shè)備A為4臺時，B為4臺時，C為12臺時。如A,B,C設(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臺時，設(shè)備B為12臺時，設(shè)備C為4臺時，問這對原計(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。（2）設(shè)備B的影子價格為4/15千元/臺時。所以，借用B設(shè)備不合算。（3）設(shè)備,V生產(chǎn)的產(chǎn)量為，系數(shù)向量分別為：檢驗(yàn)數(shù)=，所以生產(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ù)可以帶來更好的效益。（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時有最優(yōu)解。X=（0，100，230，0，0，20 目標(biāo)函數(shù)最優(yōu)值為1350（t1） （0t1）。t=1是第一臨界點(diǎn)。t大于1時，是換出變量。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開始增大時，當(dāng)t大于8/3時，首先出現(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時，為換入變量，由規(guī)則，為換出變量，使用單純形法繼續(xù)迭代，t繼續(xù)增大，當(dāng)t5，首先大于0，8/3t5的時候，最優(yōu)解為：X=（0，15，0，5 目標(biāo)函數(shù)最優(yōu)值為180+15t ，（8/3t5）。所以，t=5為第二臨界點(diǎn)。當(dāng)t5時，是換入變量，為換出變量，單純性法計(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時，首先出現(xiàn)小于0，當(dāng)0t5，最優(yōu)解為：X=（10+2t，0，10+2t，5t，0 目標(biāo)函數(shù)最優(yōu)值為6t+30 ，（0t5）。所以t=5是第一臨界點(diǎn)。當(dāng)t大于5時，是換出變量，是換入變量。用對偶單純形法計(jì)算，當(dāng)t大于5時，最優(yōu)解為：X=（10+2t，15+t，0，0，t5 目標(biāo)函數(shù)最優(yōu)值為35+5t。（4）解：先化為標(biāo)準(zhǔn)型，令t=0，用單純形法計(jì)算，得：當(dāng)t開始增大，當(dāng)t大于6時，首先出現(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）。當(dāng)t大于6時，首先出現(xiàn)小于0，是換出變量，是換入變量，使用單純形法計(jì)算得：t繼續(xù)增大，當(dāng)t大于11時，首先小于零，是換出變量，為換入變量，對偶單純形法迭代得：當(dāng) t≤59，有最優(yōu)解：X=（0，t/32，t/811/8，59/4t/4，0，0，0 目標(biāo)函數(shù)最優(yōu)值為5t/2+345/2 ，（11t≤59）。試題：1. （2006年西北工業(yè)大學(xué)）已知線性規(guī)劃：（1） 用單純形法求解該線性規(guī)劃問題的最優(yōu)解和最優(yōu)值；（2） 寫出線性規(guī)劃的對偶問題；（3） 求解對偶問題的最優(yōu)解和最優(yōu)值。解題分析：本題考察了線性規(guī)劃與對偶問題的知識，要求讀者熟知對偶理論。解題過程：，有無窮多解。對偶問題為： 2. （2005年東南大學(xué)）寫出如下線性規(guī)劃問題的對偶問題：無限制并利用弱對偶性說明的最大值不大于1。解題過程：原問題的對偶問題為：由于（0，1，0）是上述對偶問題的可行解，由弱對偶性可知，對原問題的任一可行解都有 而，所以的最大值不大于1。第三章（86頁）？為什么？表3—1銷地產(chǎn)地1234產(chǎn)量1015152151025355銷量5151510表3—2銷地產(chǎn)地12345產(chǎn)量1150250400220030050032505030049021030058020100銷量24041055033070解：表3—1中，有5個數(shù)字格，作為初始解，應(yīng)該有m+n1=3+41=6個數(shù)字格，所以表31的調(diào)運(yùn)方案不能作為用表上作業(yè)法求解時的初始解。表32中，有10個數(shù)字格，而作為初始解，應(yīng)該有m+n1=9個數(shù)字格，所以表32的調(diào)運(yùn)方案不能作為表上作業(yè)法的初始解。表33和表34中分別給出兩個運(yùn)輸問題的產(chǎn)銷平衡表和單位運(yùn)價表，試用伏格爾法直接給出近似最優(yōu)解。表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)的差額，填入該表的最右列和最下列。得到： 銷地 產(chǎn)地123行差額151842241133673列差額136從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，上表中，第三列是最大差額列，此列中最小元素為1，由此可以確定產(chǎn)地2的產(chǎn)品應(yīng)先供應(yīng)給銷售地3，得到下表： 銷地 產(chǎn)地123產(chǎn)量1111221434銷量91011同時將運(yùn)價表第三列數(shù)字劃去，得 銷地 產(chǎn)地12產(chǎn)量15112224143364銷量910對上表中的元素，計(jì)算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最右列和最下列，重復(fù)上面的步驟，直到求出初始解，最終結(jié)果是： 銷地 產(chǎn)地123產(chǎn)量121012231114344銷量91011（2）34分別計(jì)算出各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最右列和最下列。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素。（方法同33相同）最終得出原問題的初始解： 銷地產(chǎn)地12345產(chǎn)量12522030320430銷量2020301025（M是任意大正數(shù)）（1）銷地產(chǎn)地甲乙丙丁產(chǎn)量137645224322343853銷量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)量等于丙地的銷量，故在（2，丙）處填入0，同時將運(yùn)價表中的丙列和第二行的數(shù)字劃去，得到：銷地產(chǎn)地甲乙丙丁產(chǎn)量137452234353銷量332對上表中的元素分別計(jì)算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。得到下表：銷地產(chǎn)地甲乙丙丁產(chǎn)量132522023033銷量3322使用位勢法進(jìn)行檢驗(yàn)：上表中，數(shù)字格處填入單位運(yùn)價并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令+=（i，jB，B為基，下同）來確定和，得到下表：銷地產(chǎn)地甲乙丙丁1340232234313254由=（+）（i，j為非基，下同）計(jì)算所有空格的檢驗(yàn)數(shù)，并在每個格的右上角填入單位運(yùn)價，得到下表銷地產(chǎn)地甲乙丙丁13075614002 21443020234030825013254由上表可以看出，所有的非基變量檢驗(yàn)數(shù)≥0，此問題達(dá)到最優(yōu)解。又因?yàn)?0，此問題有無窮多最優(yōu)解。總運(yùn)費(fèi)min z=3*3+3*3+2*3+2*4=32（2）銷地產(chǎn)地甲乙丙丁產(chǎn)量110671242161059935410104銷量5246解：（2）計(jì)算出各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最右列和最下列。 從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，甲列是最大差額列，甲列的最小元素是5，所以產(chǎn)地3的產(chǎn)品先供應(yīng)甲的需求，同時將運(yùn)價表中產(chǎn)地3所在行的數(shù)字劃去。 對上表中的元素分別計(jì)算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。得到下表：銷地產(chǎn)地甲乙丙丁產(chǎn)量112142369344銷量5246使用位勢法進(jìn)行檢驗(yàn)：上表中，數(shù)字格處填入單位運(yùn)價，并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB，B為基，下同）來確定和.由=（+）（i，jN）計(jì)算所有空格的檢驗(yàn)數(shù)，并在每個格的右上角填入單位運(yùn)價，得到