【正文】 033銷量3322使用位勢法進行檢驗：上表中，數(shù)字格處填入單位運價并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令+=（i，jB，B為基，下同）來確定和，得到下表：銷地產(chǎn)地甲乙丙丁1340232234313254由=（+）（i，j為非基，下同）計算所有空格的檢驗數(shù)，并在每個格的右上角填入單位運價，得到下表銷地產(chǎn)地甲乙丙丁13075614002 21443020234030825013254由上表可以看出，所有的非基變量檢驗數(shù)≥0，此問題達到最優(yōu)解。 對上表中的元素分別計算各行和各列的次最小運費和最小運費的差額，填入該標的最右列和最下行，重復(fù)步驟，直到求出初始解為止。增加一個假象銷售地己，令單位運價為0。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，產(chǎn)地1所在的行是最大差額行，最小元素0，說以一產(chǎn)地的產(chǎn)品應(yīng)該優(yōu)先供應(yīng)己的需要，同時劃掉己列的數(shù)字。又因為=0，此問題有無窮多最優(yōu)解。這樣就達到了產(chǎn)銷平衡。并用位勢法進行檢驗： 銷地產(chǎn)地甲乙丙丁戊己1 1018229813022601202133MM1621014116001203006011030MM602210494110237181019801755242280363305346012101621131612由上表可以看出，所有的非基變量檢驗數(shù)≥0，此問題達到最優(yōu)解。解：(1)在對應(yīng)表的數(shù)字格處（未知）填入單位運價，并增加一行，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB）來確定和.由=（+）（i，jN）計算所有空格的檢驗數(shù)，并在每個格的右上角填入單位運價（未知）。有無窮多最優(yōu)方案，則至少有一個非基變量的檢驗數(shù)為0.取17=0，所以單價變?yōu)?7時，該問題 有無窮多最優(yōu)調(diào)運方案。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，同時劃掉所在列或行的元素。盈利最大方案：銷地產(chǎn)地ABCDI05040320II238430441III107161210541此時，總運費為28000元。試求將供應(yīng)量分配完又使總運費最低的調(diào)運方案。最優(yōu)解時，最小運費是14650萬元。此問題產(chǎn)銷不平衡，增加設(shè)想銷地，運價0，銷量7.使用伏格爾法求初始解：并用位勢法檢驗：此問題有無窮多最優(yōu)解，總運費 min z=4730萬元銷地產(chǎn)地供應(yīng)量500540006060006006055010620060S40460需求量50054056060試題：(2001年上海大學(xué))某產(chǎn)品由產(chǎn)地Ai發(fā)往銷地Bj的每噸運費如下表：元/噸B1B2B3供應(yīng)量（噸）A1504060150A2453065200A3201050250需求量150220180為滿足各銷地需求，應(yīng)如何確定運輸方案使總費用最??？（1） 建立此運輸問題的數(shù)學(xué)模型。（3）b列出現(xiàn)負數(shù)，行的系數(shù)乘以1，重新迭代，=75，=45是滿意解；，產(chǎn)品I每件獲利10元，產(chǎn)品II每件獲利8元。解：設(shè)，（i=1，2，3）表示第i種等級的兌制紅黃藍三種商標的酒的數(shù)量，數(shù)學(xué)模型：Max z=(+++++)++.（++）+=0（++）+=0（++）+=0（++）+=0（++）+=0（++）+=0+++=2000 (i=1,2,3。 故生產(chǎn)基地每天發(fā)往A倉庫10部車，發(fā)往B倉庫30部車，可使總運費最少為6800元。 0（II） max =3+2. 2+4+4。 0解得：最優(yōu)整數(shù)解是 =4，=1；目標函數(shù)是14.：Max z= +. 2 +9/14 51/142 + 1/3 ， 0 都是整數(shù)。，如果約束條件時型的，我們加M（是01變量，M是很大的常數(shù)）的方法統(tǒng)一在一個問題中。所消耗的總時間是70.試題：1. （2006年復(fù)旦大學(xué)）采用變量代換，試把非線性0—1整數(shù)規(guī)劃為0或1轉(zhuǎn)換成一個0—1整數(shù)規(guī)劃。每個工人完成每項工作所需工時如表5—1所示。最優(yōu)解為：Ⅰ—C，Ⅱ—A，Ⅲ—B，Ⅳ—D，Ⅴ—E，即應(yīng)安排工人Ⅰ、Ⅱ、Ⅲ、Ⅳ分別完成工作C、A、B、D，此時所用時間最少，為3+4+4+3=14。解題分析：本題屬“不平衡”指派問題，故應(yīng)先虛擬一項工作，使其平衡，再按常規(guī)求解即可。當(dāng)否則解題過程：令 ，故有否則再令 ，故有而與等價，故原問題可等價地寫為為0或12. （2005年南京大學(xué)）現(xiàn)要在5個工人中確定4個人來分別完成四項工作中的一項工作。給加圈，劃掉得：此時，畫圈的數(shù)目是3,少于4個，所以指派不成功，進入下一步，給第四行打√號，給第四列打√號，給第二行打√號，將第一，第三行畫一橫線，將第四列畫縱線，變換矩陣得到給第一，第四列打√號，對第一，第二，第四行打√號，給第一，第四列畫一縱線，第三行畫一橫線，變換矩陣得到 甲 乙 丙 丁得到最優(yōu)指派方案為： 甲—B；乙—A。然后對每個防火區(qū)域列出約束條件；解：令1代表當(dāng)某個防火區(qū)域由第i個消防站負責(zé)，0代表不是它負責(zé)；i=1，2，3，4。所以=0，059/4；把原問題分解為兩個問題：（a）max =3+2. 2+3142+903。令=31/2，==0是可行解。已知：從A倉庫每部貨車能運回生產(chǎn)基地甲4件，乙2公斤，丙6噸，運費200元/部；從B倉庫每部貨車每天能運回生產(chǎn)基地甲7件，乙2公斤，丙2噸，運費160元/部，問：為滿足生產(chǎn)需要，生產(chǎn)基地每天應(yīng)發(fā)往A、B兩倉庫多少部貨車，并使總運費最少？解題過程：根據(jù)題意列出下表：單位運量倉庫原材料甲（件）乙（公斤）丙（噸）運費（元/部）A426200B722160需求量24080120設(shè)每天發(fā)往A，B兩倉庫的貨車數(shù)分別為部，則有①②③④⑤且為整數(shù)先不考慮整數(shù)約束，用圖解法（如上圖），得最優(yōu)解為，恰好是整數(shù)解。解：（1）設(shè)某產(chǎn)品為從Ai發(fā)往銷地Bj的噸數(shù)，則此運輸問題的數(shù)學(xué)模型為：（2）增加一個虛擬銷地B4，其需求量為50噸，各產(chǎn)地到虛擬銷地B4的每噸運費分別為0，則可將此問題化為如下產(chǎn)銷平衡的運輸問題：元/噸B1B2B3B4供應(yīng)量A15040600150A24530650200A32010500250需求量15022018050由最小元素法可得到如下的一個初始基本可行解：元/噸B1B2B3B4供應(yīng)量A110050150A212080200A330220250需求量15022018050第四章（98頁），試述其邏輯是否正確？（1）max=+（2）max z=（3）min z=+（4）min z= 解：（1）不正確（2）正確（3）正確（4）正確試用圖解法找出以下目標函數(shù)的滿意解；（1）min z=（+）+（2+）. 10+=503+5+=208+6+=100，0（2）min z=（+）+++(+). ++=40++=100+=30+=15，,0(3) min z=（+）+ +. ++=103+4+=508+10+=300，0解（1）滿意解是：（50，0）（2）滿意解是：（25，15）（3）滿意解是：（10，0）。已知該廠這三年內(nèi)生產(chǎn)大型客貨輪的能力及每艘客貨輪成本如下表，年度正常生產(chǎn)時間內(nèi)可完成的客貨輪數(shù)加班生產(chǎn)時間內(nèi)可完成的客貨輪數(shù)正常生產(chǎn)時的每艘成本/萬元123500242600313550已知加班生產(chǎn)時，每艘客貨輪的成本比正常生產(chǎn)高出70萬元，又知道造出來的可貨輪如當(dāng)年不交貨，每艘積壓一年造成積壓損失40萬元，在簽合同時，該廠已經(jīng)存儲了2艘客貨輪，而該廠希望在第三年木完成合同后還能存儲一艘備用，問該廠如何安排每年的生產(chǎn)量，能夠在滿足上述要求的情況下，總的生產(chǎn)費用加積壓損失最少？解：設(shè)，是三年的需求訂貨，是三年的正常生產(chǎn)能力；，是三年的加班能力，S是事先積壓產(chǎn)生的供貨能力。用伏格爾法求解得： 銷地產(chǎn)地甲甲‘乙丙丙‘供應(yīng)A150250400B1403027010450C7070需求2903025027080使用位勢法檢驗：數(shù)字格處填入單位運價，并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB，）來確定和.由=（+）（i，jN）計算所有空格的檢驗數(shù)，并在每個格的右上角填入單位運價。：320萬噸、250萬噸、350萬噸，由A、B兩處煤礦供應(yīng)。銷地產(chǎn)地ABCD產(chǎn)量I15005005002500II25002500III150035005000銷量1500200030003500使用位勢法檢驗：數(shù)字格處填入單位運價，并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB，）來確定和.由=（+）（i，jN）計算所有空格的檢驗數(shù)，并在每個格的右上角填入單位運價。已知下表，求預(yù)期盈利最大的采購方案。所以：30+100100240180解得:310單位運價在此區(qū)間變化時，最優(yōu)調(diào)運方案不變?？傔\費min z=5520已知運輸問題的產(chǎn)銷平衡表、單位運價表及最優(yōu)調(diào)運方案如下表所示表1 銷地產(chǎn)地產(chǎn)量51015010152555銷量5151510表2 銷地產(chǎn)地10120111279202141618（1）到的單位運價在什么范圍變化時，上述最優(yōu)方案不變？（2）到的單位運價變?yōu)楹沃禃r，有無窮多最優(yōu)方案。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，同時劃掉所在列或行的元素。增加一個假象銷售地己，令單位運價為0。得到下表： 銷地產(chǎn)地甲乙丙丁戊己產(chǎn)量1325242632244329銷量446242使用位勢法進行檢驗：上表中，數(shù)字格處填入單位運價，