【正文】 等于5，所以最優(yōu)解不變。如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í)，問(wèn)這對(duì)原計(jì)劃有何影響？解：（1）設(shè)：產(chǎn)品三種產(chǎn)品的產(chǎn)量分別為，建立數(shù)學(xué)模型：Max z=3+2+. 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。單純形法計(jì)算得：最優(yōu)解：X=（107/4，31/2，0，0，0，0，55/4 目標(biāo)函數(shù)最優(yōu)值為10957/80。（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，最優(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)解。當(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開(kāi)始增大，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）。（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，183t，455t 目標(biāo)函數(shù)最優(yōu)值為150+5t （0t6）。解題過(guò)程：，有無(wú)窮多解。表32中，有10個(gè)數(shù)字格，而作為初始解，應(yīng)該有m+n1=9個(gè)數(shù)字格，所以表32的調(diào)運(yùn)方案不能作為表上作業(yè)法的初始解。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素。又因?yàn)?0，此問(wèn)題有無(wú)窮多最優(yōu)解。得到下表：銷(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 16810650902350431081045106711由上表可以看出，所有的非基變量檢驗(yàn)數(shù)≥0，此問(wèn)題達(dá)到最優(yōu)解。銷(xiāo)量為2。 對(duì)上表中的元素分別計(jì)算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。總運(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)。用伏格爾法求初始解：計(jì)算出各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該表的最右列和最下行。又因?yàn)?0，此問(wèn)題有無(wú)窮多最優(yōu)解。最優(yōu)調(diào)運(yùn)方案不變，則所有非基變量的檢驗(yàn)數(shù)都是非負(fù)。另外的兩種調(diào)運(yùn)方案：銷(xiāo)地產(chǎn)地產(chǎn)量15015015102555銷(xiāo)量5151510銷(xiāo)地產(chǎn)地產(chǎn)量15150015102555銷(xiāo)量5151510某百貨公司去外地采購(gòu)ABCD四種規(guī)格的服裝，數(shù)量分別為：A,1500套；B，2000套；C，3000套；D，3500套；有三個(gè)城市可以供應(yīng)上述服裝，分別為：I，2500套，II，2500套；III，5000套。對(duì)上表中的元素分別計(jì)算各行和各列的次最小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。最大盈利為72000元。甲乙丙A151822B212516解：此問(wèn)題的供應(yīng)量小于需求量，假設(shè)供應(yīng)地C，產(chǎn)量為70萬(wàn)噸。（2）將此問(wèn)題化為產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題，并求出一個(gè)初始基本可行解。每生產(chǎn)1件產(chǎn)品I需要3小時(shí)，每周的有效時(shí)間120小時(shí)，若加班生產(chǎn)，每件產(chǎn)品II利潤(rùn)少1元，決策者希望在允許的時(shí)間和加班時(shí)間獲取最大利潤(rùn)，試建立該問(wèn)題的目標(biāo)規(guī)劃模型，并求解？解：條件不足，無(wú)法建立模型。j=1,2,3)其中，z=(++)+5(++)+（++）6(++)(++)3(++)+試題：1. 某生產(chǎn)基地每天需從A、B兩倉(cāng)庫(kù)中提取原材料用于生產(chǎn)，需提取的原材料有：原材料甲不少于240件，原材料乙不少于80公斤，原材料丙不少于120噸。第五章答案，問(wèn)：用先解相應(yīng)的線性規(guī)劃，然后湊整的辦法，能否求到最優(yōu)整數(shù)解？（1） max z=3+2.2+4+,0,是整數(shù)（1） 解：將上述問(wèn)題化為：Max z=3+2+0+0 .2+3+=4++=,0,N用單純形法求解：3200b029/2231029/4033/2【4】10133/8z03200（迭代過(guò)程略）相應(yīng)的線性規(guī)劃問(wèn)題最優(yōu)解是= ,目標(biāo)函數(shù)的最優(yōu)值z(mì)=31/2湊整數(shù)時(shí)，=,是非可行解；=，是非可行解；=，是非可行解；=，是可行解，z=13；使用分支定界法解整數(shù)規(guī)劃問(wèn)題。 0將上述問(wèn)題化為標(biāo)準(zhǔn)型，使用單純形法求解：=3，=2是最優(yōu)整數(shù)解，z=13.（2）max z=3+2.2+3142+9,0,是整數(shù)（2） 解：使用圖解法或者單純形法求解此問(wèn)題，線性規(guī)劃問(wèn)題最優(yōu)解是（13/4，5/2）目標(biāo)函數(shù)最優(yōu)值max z=59/4；湊整數(shù)時(shí)，=,是可行解，z=13；=，是非可行解；=，是非可行解；=，是非可行解；使用分支定界法求解原整數(shù)規(guī)劃問(wèn)題，令令=59/4，==0是可行解。圖解法解得：最優(yōu)解是B點(diǎn)（51/46+7/691/6，51/23+14/69）目標(biāo)函數(shù)最優(yōu)值為：58/23+51/461/6使用分支定界法求解，令=58/23+51/461/6，==0是可行解；因此 =0，故058/23+51/461/6將原問(wèn)題分解為下列問(wèn)題：（I）Max = +. 2 +9/14 51/142 + 1/31 ， 0（I）Max = +. 2 +9/14 51/142 + 1/32 ， 0按照以上步驟，求解最終得到：最優(yōu)解是（1，2）目標(biāo)函數(shù)最優(yōu)值z(mì)=3：（1）max z=+. 2+64+520,0,是整數(shù)解：將上述問(wèn)題化成標(biāo)準(zhǔn)型：max z=++0+0. 2++=64+5+=20,，0,，是整數(shù)單純形法求得最優(yōu)解是：= ，目標(biāo)函數(shù)最優(yōu)值13/3變量之間的關(guān)系：+5/6/6=5/32/3+/3=8/3把系數(shù)和常數(shù)項(xiàng)都分解成為整數(shù)和非負(fù)真分?jǐn)?shù)之和；所以有：2/35/65/602/3（+）/30加入松弛變量，繼續(xù)迭代得到最終結(jié)果：= ，目標(biāo)函數(shù)最優(yōu)值4解得：最優(yōu)整數(shù)解是 =0，=4；目標(biāo)函數(shù)是4.（3） max z=3 . 3 2 354102+5,0,是整數(shù)解：將原問(wèn)題化成標(biāo)準(zhǔn)型，并使用單純形法求解：最優(yōu)解為= ，目標(biāo)函數(shù)最優(yōu)值30/7從單純形表可以得到變量間的關(guān)系，把系數(shù)和常數(shù)項(xiàng)都分解成整數(shù)和非負(fù)分?jǐn)?shù)之和，可以得知：6/7（/7+2/7）0加入松弛變量，把新的約束條件加入后，繼續(xù)迭代，得到最終的結(jié)果：最優(yōu)解是=1，=2目標(biāo)函數(shù)最優(yōu)值1.，設(shè)有四個(gè)防火站，如圖所示(課本P114)，其中①②③④是四個(gè)消防站，1，2，…11是防火區(qū)域，根據(jù)歷史資料證實(shí)，各個(gè)消防站可在事先規(guī)定的允許時(shí)間內(nèi)對(duì)所有負(fù)責(zé)的地區(qū)的火災(zāi)予以消滅，虛線表示各地區(qū)是哪個(gè)消防站負(fù)責(zé)，現(xiàn)在總部提出：是否可以減少消防站的數(shù)目，仍能夠負(fù)責(zé)各個(gè)地區(qū)的防火任務(wù)，如果可以，關(guān)閉哪個(gè)？提示：對(duì)每個(gè)消防站定義一個(gè)01變量，令1代表當(dāng)某個(gè)防火區(qū)域由第i個(gè)消防站負(fù)責(zé)，0代表不是它負(fù)責(zé)。如果是型的，我們將如何利用和M呢？解：在m個(gè)約束條件右端分別減去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）分別帶入到約束條件中，可以得到：原問(wèn)題的最優(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解：= 是一個(gè)可行解，目標(biāo)函數(shù)數(shù)值是4；所以可以增加約束條件：2+5+3+44把可能的解（0，0，0，0）（0，0，0，1）…（1，1，1，1）分別帶入約束條件的問(wèn)題中，得到最優(yōu)解= ，目標(biāo)函數(shù)最優(yōu)值4.，指派他們完成4種工作，每人做各種工作所消耗的時(shí)間如下表，問(wèn)指派哪個(gè)人去完成哪種工作，可以使得總耗時(shí)最小？ 任務(wù)人員ABCD甲15182124乙19232218丙26171619丁19212317解：系數(shù)矩陣C為：① 系數(shù)矩陣的每行元素減去該行的最小元素得矩陣B② B矩陣的每列元素減去該列的最小元素得到矩陣A此時(shí)，細(xì)數(shù)矩陣的每行每列都有元素0.先給加圈，然后給加圈，劃掉。當(dāng)解題分析：0—1規(guī)劃即約束中自變量只能取值0或1。表5—1工作所需工時(shí)工人Ⅰ9437Ⅱ4656Ⅲ5475Ⅳ7523Ⅴ10674試找出一個(gè)工作分配方案，使總工時(shí)最少。