運籌學(xué)習(xí)題集04(編輯修改稿)
2025-04-22 04:30 本頁面
【文章內(nèi)容簡介】 ），先令=0，由 +=（i，jB，B為基，下同）來確定和.由=（+）（i，jN）計算所有空格的檢驗數(shù)，并在每個格的右上角填入單位運價。由上表可以看出，所有的非基變量檢驗數(shù)≥0，此問題達到最優(yōu)解。又因為=0，此問題有無窮多最優(yōu)解。總運費min z=90（4） 銷地產(chǎn)地甲乙丙丁戊產(chǎn)量1 1018291322100213M211416120306113M1404911231819805242836303460銷量1001201006080解：（4）此問題是一個產(chǎn)銷不平衡的問題，產(chǎn)大于銷。增加一個假象銷售地己，令單位運價為0。銷量為40。這樣就達到了產(chǎn)銷平衡。用伏格爾法求初始解：計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下行。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，同時劃掉所在列或行的元素。 對上表中的元素分別計算各行和各列的次最小運費和最小運費的差額，填入該標(biāo)的最右列和最下行，重復(fù)步驟，直到求出初始解為止。并用位勢法進行檢驗： 銷地產(chǎn)地甲乙丙丁戊己1 1018229813022601202133MM1621014116001203006011030MM602210494110237181019801755242280363305346012101621131612由上表可以看出，所有的非基變量檢驗數(shù)≥0，此問題達到最優(yōu)解。又因為=0，此問題有無窮多最優(yōu)解?？傔\費min z=5520有四個工人，指派他們完成4種工作，每人做各種工作所消耗的時間如下表，問指派哪個人去完成哪種工作，可以使得總耗時最??？ 任務(wù)人員ABCD甲15182124乙19232218丙26171619丁19212317解：系數(shù)矩陣C為：① 系數(shù)矩陣的每行元素減去該行的最小元素得矩陣B② B矩陣的每列元素減去該列的最小元素得到矩陣A此時，細數(shù)矩陣的每行每列都有元素0.先給加圈，然后給加圈，劃掉。給加圈，劃掉得：此時，畫圈的數(shù)目是3,少于4個，所以指派不成功，進入下一步，給第四行打√號，給第四列打√號，給第二行打√號，將第一，第三行畫一橫線，將第四列畫縱線，變換矩陣得到給第一，第四列打√號，對第一，第二，第四行打√號，給第一，第四列畫一縱線，第三行畫一橫線，變換矩陣得到 甲 乙 丙 丁得到最優(yōu)指派方案為： 甲—B；乙—A。 丙—C；丁—D。所消耗的總時間是70.2. 現(xiàn)要在5個工人中確定4個人來分別完成四項工作中的一項工作。由于每個工人的技術(shù)特長不同，他們完成各項工作所需的工時也不同。每個工人完成每項工作所需工時如表5—1所示。表5—1工作所需工時工人Ⅰ9437Ⅱ4656Ⅲ5475Ⅳ7523Ⅴ10674試找出一個工作分配方案，使總工時最少。解題分析：本題屬“不平衡”指派問題，故應(yīng)先虛擬一項工作，使其平衡，再按常規(guī)求解即可。解題過程：虛擬一項工作E，設(shè)每人完成E所需時間都是“0”，從而轉(zhuǎn)化為五個人完成五項工作的分配問題，再用匈牙利法求解。最優(yōu)解為：Ⅰ—C，Ⅱ—A，Ⅲ—B，Ⅳ—D，Ⅴ—E，即應(yīng)安排工人Ⅰ、Ⅱ、Ⅲ、Ⅳ分別完成工作C、A、B、D，此時所用時間最少，為3+4+4+3=14。用標(biāo)號法求下圖所示的最大流問題，弧上數(shù)字為容量和初始可行流量。解：最大流f*=152. 試找出A→F間的最短路線及距離。19B1245534168E19435FC2AB2265E274145247D1C1D3C3D2B3解：此為動態(tài)規(guī)劃之“最短路問題”，可用逆向追蹤“圖上標(biāo)號法”解決如下：144519B131245541490168E15943FC2AB2117265E2741425247D1C1D3C3D2B31287最佳策略為：A→B2→C1→D1→E2→F此時的最短距離為5+4+1+2+2=14v5v283.221732v7v4v174431v6v3求v1到v7的最短路徑和最短距離。解：此為網(wǎng)絡(luò)分析之“最短路問題”，可用順向追蹤“TP標(biāo)號法”解決如下：94v2v5852217732v7v4v1744310v6v314v1到v7的最短路徑是：v1→v3→v4→v7，最短距離為1+4+2=7。v3v1求下圖所示網(wǎng)絡(luò)的最大流：（4，0）（5，0）（3，0）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2圖中為（Cij，fij）解：此為網(wǎng)絡(luò)分析之“尋求網(wǎng)絡(luò)最大流問題”，可用“尋求網(wǎng)絡(luò)最大流的標(biāo)號法（福特—富克爾遜算法）”解決如下：㈠標(biāo)號過程：給vs標(biāo)上（0，∞）；檢查vs，在?。╲s，v1）上，fs1=0，Cs1=3，fs1Cs1，給v1標(biāo)號(s，β(v1))，其中，（s，3）v1v3（4，0）（5，0）（3，0）（s，∞）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2（s，5）同理，給v2標(biāo)號(s，β(v2))，其中，檢查v1，在?。╲1，v3）上，f13=0，C13=4，f13C13，給v3標(biāo)號(1，β(v3))，其中，（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（s，∞）（3，0）（1，0）（1，0）
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1