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