【正文】 。用伏格爾法求初始解：計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下列。 對上表中的元素分別計算各行和各列的次最小運費和最小運費的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。由上表可以看出，所有的非基變量檢驗數(shù)≥0，此問題達到最優(yōu)解?？傔\費min z=90（4） 銷地產(chǎn)地甲乙丙丁戊產(chǎn)量1 1018291322100213M211416120306113M1404911231819805242836303460銷量1001201006080解：（4）此問題是一個產(chǎn)銷不平衡的問題，產(chǎn)大于銷。銷量為40。用伏格爾法求初始解：計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下行。 對上表中的元素分別計算各行和各列的次最小運費和最小運費的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。又因為=0，此問題有無窮多最優(yōu)解。除表1中方案外，至少寫出其他兩個。最優(yōu)調(diào)運方案不變，則所有非基變量的檢驗數(shù)都是非負。（2）在對應(yīng)表的數(shù)字格處（未知）填入單位運價，并增加一行，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB）來確定和.由=（+）（i，jN）計算所有空格的檢驗數(shù)，并在每個格的右上角填入單位運價（未知）。另外的兩種調(diào)運方案：銷地產(chǎn)地產(chǎn)量15015015102555銷量5151510銷地產(chǎn)地產(chǎn)量15150015102555銷量5151510某百貨公司去外地采購ABCD四種規(guī)格的服裝，數(shù)量分別為：A,1500套；B，2000套；C，3000套；D，3500套；有三個城市可以供應(yīng)上述服裝，分別為：I，2500套，II，2500套；III，5000套。ABCDI10567II8276III9348解：因為利潤表中的最大利潤是10，所以令M=10，用M減去利潤表上的數(shù)字，此問題變成一個運輸問題，見下表：銷地產(chǎn)地ABCD產(chǎn)量I05432500II28342500III17625000銷量1500200030003500使用伏格爾法計算初始解：計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下行。對上表中的元素分別計算各行和各列的次最小運費和最小運費的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。如果沒有得到最優(yōu)解，用逼回路法進行改進。最大盈利為72000元。煤炭供應(yīng)量分別為：A,400萬噸；B,450萬噸；運價如下表，由于需大于供應(yīng)，經(jīng)研究平衡決定，甲城市供應(yīng)量可以減少0~30萬噸，乙城市需要完全供應(yīng)，丙城市供應(yīng)不少于270萬噸。甲乙丙A151822B212516解：此問題的供應(yīng)量小于需求量，假設(shè)供應(yīng)地C，產(chǎn)量為70萬噸。如果沒有得到最優(yōu)解，用閉回路法進行改進。第三年的需求量是4艘。（2）將此問題化為產(chǎn)銷平衡的運輸問題，并求出一個初始基本可行解。（1）min z= + +（5+3 ）+ . ++=80++ =90+=70+=45，,0（2）min z= + + . +2+=1010+12+=+28， 0（3）min z=（+ ）+ . ++=12+2+=464+=50，0解：（1）把原問題轉(zhuǎn)化為：Min z=++.+2+=1010+12+=2++=8，0是松弛變量單純形法計算得：0000b101【2】01100510120001108211000081012000021200100迭代…原問題最優(yōu)解=0，=，非基變量的的檢驗數(shù)是0，所以有多重解；繼續(xù)迭代得到：=，=（2）使用單純形法計算：=70，=20（3）滿意解是=1，=0min z=+ +（5+3 ）+（5+3）. ++=80+=70+=45+=10，，0（1）用單純形法求解（2）若目標(biāo)函數(shù)變成min z=+ +（5+3 ）+（5+3），問原問題的解有什么變化？（3）若第一個目標(biāo)約束的右端改為120，原滿意解有何變化？解：（1） 單純形法計算得到：=70，=45是滿意解（2） 實際上是對優(yōu)先因子，進行調(diào)換，最優(yōu)解不變。每生產(chǎn)1件產(chǎn)品I需要3小時，每周的有效時間120小時，若加班生產(chǎn)，每件產(chǎn)品II利潤少1元，決策者希望在允許的時間和加班時間獲取最大利潤，試建立該問題的目標(biāo)規(guī)劃模型，并求解？解：條件不足，無法建立模型。已知道三種酒的供應(yīng)量和單位成本如下表；設(shè)該種牌號酒有三種商標(biāo)（紅黃藍），各種商標(biāo)的酒對原料酒的混合比及售價見下表，決策者規(guī)定：首先必須嚴(yán)格按規(guī)定比例兌制各種商標(biāo)的酒，其次獲利最大；再次，紅商標(biāo)的酒每天至少生產(chǎn)2000kg，列出數(shù)學(xué)模型。j=1,2,3)其中，z=(++)+5(++)+（++）6(++)(++)3(++)+試題：1. 某生產(chǎn)基地每天需從A、B兩倉庫中提取原材料用于生產(chǎn)，需提取的原材料有：原材料甲不少于240件，原材料乙不少于80公斤，原材料丙不少于120噸。故就是原問題的最優(yōu)整數(shù)解，且。第五章答案，問：用先解相應(yīng)的線性規(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（迭代過程略）相應(yīng)的線性規(guī)劃問題最優(yōu)解是= ,目標(biāo)函數(shù)的最優(yōu)值z=31/2湊整數(shù)時，=,是非可行解；=，是非可行解；=，是非可行解；=，是可行解，z=13；使用分支定界法解整數(shù)規(guī)劃問題。所以=0，031/2把原問題分解為兩個問題：（I） max =3+2. 2+4+03。 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是可行解。 0（b）max =3+2. 2+3142+94。圖解法解得：最優(yōu)解是B點（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將原問題分解為下列問題：（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=3：（1）max z=+. 2+64+520,0,是整數(shù)解：將上述問題化成標(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ù)項都分解成為整數(shù)和非負真分?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ù)解：將原問題化成標(biāo)準(zhǔn)型，并使用單純形法求解：最優(yōu)解為= ，目標(biāo)函數(shù)最優(yōu)值30/7從單純形表可以得到變量間的關(guān)系，把系數(shù)和常數(shù)項都分解成整數(shù)和非負分?jǐn)?shù)之和，可以得知：6/7（/7+2/7）0加入松弛變量，把新的約束條件加入后，繼續(xù)迭代，得到最終的結(jié)果：最優(yōu)解是=1，=2目標(biāo)函數(shù)最優(yōu)值1.，設(shè)有四個防火站，如圖所示(課本P114)，其中①②③④是四個消防站，1，2，…11是防火區(qū)域，根據(jù)歷史資料證實，各個消防站可在事先規(guī)定的允許時間內(nèi)對所有負責(zé)的地區(qū)的火災(zāi)予以消滅，虛線表示各地區(qū)是哪個消防站負責(zé)，現(xiàn)在總部提出：是否可以減少消防站的數(shù)目，仍能夠負責(zé)各個地區(qū)的防火任務(wù)，如果可以，關(guān)閉哪個？提示：對每個消防站定義一個01變量，令1代表當(dāng)某個防火區(qū)域由第i個消防站負責(zé)，0代表不是它負責(zé)。建立數(shù)學(xué)模型：Min z=. +11+11++1+1++1+11+1有以上約束條件可以解得：===1繼續(xù)求解當(dāng)=0時，是可行解，目標(biāo)函數(shù)是3；當(dāng)=1時，是可行解，目標(biāo)函數(shù)是4；比較可以得到，最優(yōu)解是= ，目標(biāo)函數(shù)最優(yōu)值是3.所以，可以關(guān)閉消防站②。如果是型的，我們將如何利用和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此時，細數(shù)矩陣的每行每列都有元素0.先給加圈，然后給加圈，劃掉。 丙—C；丁—D。當(dāng)解題分析：0—1規(guī)劃即約束中自變量只能取值0或1。由于每個工人的技術(shù)特長不同，他們完成各項工作所需的工時也不同。表5—1工作所需工時工人Ⅰ9437Ⅱ4656Ⅲ5475Ⅳ7523Ⅴ10674試找出一個工作分配方案，使總工時最少。解題過程：虛擬一項工作E，設(shè)每人完成E所需時間都是“0”，從而轉(zhuǎn)化為五個人完成五項工作的分配問題，再用匈牙利法求解。