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