運籌學(xué)習(xí)題集.doc

.例：將下面的線性規(guī)劃化為標準型無非負限制解1.9某晝夜服務(wù)的公交線路每天個時間段內(nèi)所需司機和乘務(wù)員人數(shù)如下：班次時間所需人數(shù)16點到10點60210點到14點70314點到18點60418點到22點50522點到2點2062點到6點30設(shè)司機和乘務(wù)人員分別在各時間區(qū)段一開始時上班，并連續(xù)上班8小時，問該公交線路至少配備多少司機和乘務(wù)人員。列出線型規(guī)劃模型。解：設(shè)（k=1，2，3，4，5，6）為個司機和乘務(wù)人員第k班次開始上班。建立模型：Min z=+s.t. +60+70+60+50+20+30,01.10某糖果公司廠用原料A、B、C加工成三種不同牌號的糖果甲乙丙，已知各種糖果中ABC含量，原料成本，各種原料的每月限制用量，三種牌號糖果的單位加工費用及售價如表所示：原料甲乙丙原料成本（元/千克）每月限制用量（千克）A60%15%22000B1.52500C20%60%50%11200加工費0.50.40.3售價3.42.852.25問該廠每月應(yīng)當生產(chǎn)這三種牌號糖果各多少千克，使得獲利最大？建立數(shù)學(xué)模型。解:解：設(shè)，是甲糖果中的A，B，C成分，是乙糖果的A，B，C成分，是丙糖果的A，B，C成分。線性規(guī)劃模型：Max z=0.9+1.4+1.9+0.45+0.95+1.45-0.05+0.45+0.95s.t. -0.4+0.6+0.60 -0.2-0.2+0.80 -0.85+0.15+0.150 -0.6-0.6+0.40 -0.7-0.5+0.50+2000+2500+1200,01.11某廠生產(chǎn)三種產(chǎn)品I、III。每種產(chǎn)品經(jīng)過AB兩道加工程序，該廠有兩種設(shè)備能完成A工序，他們以,表示；有三種設(shè)備完成B工序，分別為，；產(chǎn)品I可以在AB任何一種設(shè)備上加工，產(chǎn)品可以在任何規(guī)格的A設(shè)備上加工，但完成B工序時，只能在設(shè)備上加工；產(chǎn)品III只能在，上加工。已知條件如下表，要求安排最優(yōu)生產(chǎn)計劃，使該廠利潤最大化。設(shè)備產(chǎn)品設(shè)備有效臺時滿負荷時的設(shè)備費用IIIIII5106000300791210000321684000250411700078374000200原料費0.250.350.5單價1.252.002.8解：產(chǎn)品1，設(shè),完成A工序的產(chǎn)品，件；B工序時，,，完成B工序的，件，產(chǎn)品，設(shè),完成A工序的產(chǎn)品，件；B工序時，完成B的產(chǎn)品為件；產(chǎn)品111，完成A工序的件，完成B工序的件；+=+ = 建立數(shù)學(xué)模型：Max z=(1.25-0.25)*(+)+(2-0.35)*(+ )+(2.8-0.5) -(5+10)300/6000-(7+9 +12 )321/10000-(6+8 )250/4000-(4+11 )783/7000-7*200/4000s.t 5+1060007+9 +12 100006+8 40004+11 700074000+=+ = ,0用單純形法求解線性規(guī)劃極大化MAX解引入松弛變量，得到原規(guī)劃的標準型極大化單純形表為所以，最優(yōu)解為最優(yōu)解值為21.解：最優(yōu)解例：設(shè)線性規(guī)劃求：1.最優(yōu)解; 2.確定的范圍,使最優(yōu)解不變; 取,求最優(yōu)解; 3.確定的范圍,使最優(yōu)基不變, 取求最優(yōu)解; 4.引入求最優(yōu)解;解 1.由單純形方法得即,原問題的最優(yōu)解為例求下面運輸問題的最小值解：12341311310721923437410593656解：由最小元素法得到初始解：v1=2v2=9v3=3v4=101934u1=01311310743u2=-121923431u3=-53741059633656則：，最小值為-6，非基變量為，閉回路，最大調(diào)整量為1，得新解：，重新計算位勢及影響系數(shù)，得下表：v1=8v2=9v3=3v4=101234u1=01311310752u2=-721923431u3=-53741059633656，最小值為-5，非基變量為，閉回路，最大調(diào)整為2，得新解：重新計算位勢及影響系數(shù)，得下表：v1=3v2=4v3=3v4=51234u1=01311310725u2=-221923413u3=03741059633656，此時，故當前解為最優(yōu)解。最優(yōu)解值為：。3.2表3-3和表3-4中分別給出兩個運輸問題的產(chǎn)銷平衡表和單位運價表，試用伏格爾法直接給出近似最優(yōu)解。表3-3銷地產(chǎn)地123產(chǎn)量15181222411433674銷量91011表3-4銷地產(chǎn)地12345產(chǎn)量11023159252520152430315514715204201513M830銷量2020301025解：（1）在表3-3中分別計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下列。得到：銷地產(chǎn)地123行差額151842241133673列差額136從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，上表中，第三列是最大差額列，此列中最小元素為1，由此可以確定產(chǎn)地2的產(chǎn)品應(yīng)先供應(yīng)給銷售地3，得到下表：銷地產(chǎn)地123產(chǎn)量1111221434銷量91011同時將運價表第三列數(shù)字劃去，得銷地產(chǎn)地12產(chǎn)量15112224143364銷量910對上表中的元素，計算各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下列，重復(fù)上面的步驟，直到求出初始解，最終結(jié)果是：銷地產(chǎn)地123產(chǎn)量121012231114344銷量91011（2）3-4分別計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下列。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素。（方法同3-3相同）最終得出原問題的初始解：銷地產(chǎn)地12345產(chǎn)量12522030320430銷量20203010253.3用表上作業(yè)法求給出運輸問題的最優(yōu)解（M是任意大正數(shù)）（1）銷地產(chǎn)地甲乙丙丁產(chǎn)量137645224322343853銷量3322解：（1）計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下列。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，丙列中的最小元素為3，由此可以確定產(chǎn)地2的產(chǎn)品應(yīng)先供應(yīng)丙的需要，而產(chǎn)地2的產(chǎn)量等于丙地的銷量，故在（2，丙）處填入0，同時將運價表中的丙列和第二行的數(shù)字劃去，得到：銷地產(chǎn)地甲乙丙丁產(chǎn)量137452234353銷量332對上表中的元素分別計算各行和各列的次最小運費和最小運費的差額，填入該標的最右列和最下行，重復(fù)步驟，直到求出初始解為止。得到下表：銷地產(chǎn)地甲乙丙丁產(chǎn)量132522023033銷量3322使用位勢法進行檢驗：上表中，數(shù)字格處填入單位運價并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令+=（i，jB，B為基，下同）來確定和，得到下表：銷地產(chǎn)地甲乙丙丁1340232-234313254由=-（+）（i，j為非基，下同）計算所有空格的檢驗數(shù)，并在每個格的右上角填入單位運價，得到下表銷地產(chǎn)地甲乙丙21443020-234030825013254由上表可以看出，所有的非基變量檢驗數(shù)0，此問題達到最優(yōu)解。又因為=0，此問題有無窮多最優(yōu)解?？傔\費min z=3*3+3*3+2*3+2*4=32（2）銷地產(chǎn)地甲乙丙丁產(chǎn)量110671242161059935410104銷量5246解：（2）計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下列。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，甲列是最大差額列，甲列的最小元素是5，所以產(chǎn)地3的產(chǎn)品先供應(yīng)甲的需求，同時將運價表中產(chǎn)地3所在行的數(shù)字劃去。對上表中的元素分別計算各行和各列的次最小運費和最小運費的差額，填入該標的最右列和最下行，重復(fù)步驟，直到求出初始解為止。得到下表：銷地產(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 1681065090-235043108104-5106711由上表可以看出，所有的非基變量檢驗數(shù)0，此問題達到最優(yōu)解。此問題有唯一最優(yōu)解?？傔\費min z=118（3）銷地產(chǎn)地甲乙丙丁戊產(chǎn)量11020591052210830663120710424863759銷量44624解：（3）此問題是一個產(chǎn)銷不平衡的問題，產(chǎn)大于銷。增加一個假象銷售地己，令單位運價為0。銷量為2。這樣就達到了產(chǎn)銷平衡。用伏格爾法求初始解：計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下列。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，產(chǎn)地1所在的行是最大差額行，最小元素0，說以一產(chǎn)地的產(chǎn)品應(yīng)該優(yōu)先供應(yīng)己的需要，同時劃掉己列的數(shù)字。對上表中的元素分別計算各行和各列的次最小運費和最小運費的差額，填入該標的最右列和最下行，重復(fù)步驟，直到求出初始解為止。得到下表：銷地產(chǎn)地甲乙丙丁戊己產(chǎn)量1325242632244329銷量446242使用位勢法進行檢驗：上表中，數(shù)字格處填入單位運價，并增加一行一列，在列中填入（i=1，2，3，4），在行中填入（j=1，2，3，4，5，6），先令=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)銷平衡。用伏格爾法求初始解：計算出各行和各列的次最小運費和最小運費的差額，填入該表的最右列和最下行。從行差額或者列差額中找出最大的，選擇它所在的行或者列中的最小元素，同時劃掉所在列或行的元素。對上表中的元素分別計算各行和各列的次最小運費和最小運費的差額，填入該標的最右列和最下行，重復(fù)步驟，直到求出初始解為止。并用位勢法進行檢驗：銷地產(chǎn)地甲乙丙丁戊己1 1018229813022601202133MM-1621014116001203006011030MM-6022-104941102371810198017-552422803633053460121016211316-12由上表可以看出，所有的非基變量檢驗數(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ù)特長不同，他們完成各項工作所需的工時也不同。每個工人完成每項工作所需工時如表51所示。表51工作所需工時工人943746565475752310674試找出一個工作分配方案，使總工時最少。解題分析：本題屬“不平衡”指派問題，故應(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。1、用標號法求下圖所示的最大流問題，弧上數(shù)字為容量和初始可行流量。解：最大流f*=152.試找出AF間的最短路線及距離。19B1245534168E19435FC2AB2265E274145247D1C1D3C3D2B3解：此為動態(tài)規(guī)劃之“最短路問題”，可用逆向追蹤“圖上標號法”解決如下：144519B131245541490168E15943FC2AB2117265E2741425247D1C1D3C3D2B31287最佳策略為：AB2C1D1E2F此時的最短距離為5+4+1+2+2=14v5v283.221732v7v4v174431v6v3求v1到v7的最短路徑和最短距離。解：此為網(wǎng)絡(luò)分析之“最短路問題”，可用順向追蹤“TP標號法”解決如下：94v2v5852217732v7v4v1744310v6v314v1到v7的最短路徑是：v1v3v4v7，最短距離為1+4+2=7。v3v14、求下圖所示網(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ò)最大流的標號法（福特富克爾遜算法）”解決如下：標號過程：1、給vs標上（0，）；2、檢查vs，在?。╲s，v1）上，fs1=0，Cs1=3，fs1Cs1，給v1標號(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標號(s，(v2)，其中，3、檢查v1，在弧（v1，v3）上，f13=0，C13=4，f13C13，給v3標號(1，(v3)，其中，（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（s，）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2（2，2）（s，5）檢查v2，同理，給v4標號(2，(v4)，其中，4、檢查v4，在弧（v4，vt）上，f4t=0，C4t=2，f13C13，給vt標號(4，(vt)，其中，vt得到標號，標號過程結(jié)束。（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（4，2）（s，）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2（2，2）（s，5）調(diào)整過程：從vt開始逆向追蹤，找到增廣鏈。（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（2，2）（s，）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2（2，2）（s，5）（vs，v2，v4，vt），=2，在上進行流量=2的調(diào)整，得可行流f 如圖所示：（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（1，0）（4，2）（s，）（3，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（2，2）（s，5）去掉各點標號，從vs開始，重新標號。（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（3，3）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（t，2）（s，3）vt又得到標號，標號過程結(jié)束。再次從vt開始逆向追蹤，找到增廣鏈。（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（3，3）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（t，2）（s，3）（vs，v1，v3，vt），=3，在上進行流量=3的調(diào)整，得可行流f 如圖所示：（1，3）（s，3）v1v3（4，3）（5，3）（3，3）（3，3）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（t，2）（s，3）去掉各點標號，從vs開始，重新標號。（1，1）（2，1）v1v3（4，3）（5，3）（3，3）（3，1）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（s，3）vt又得到標號，標號過程結(jié)束。再次從vt開始逆向追蹤，找到增廣鏈。（1，1）（2，1）v1v3（4，3）（5，3）（3，3）（3，1）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（s，3）（vs，v2，v1，v3，vt），=1，在上進行流量=1的調(diào)整，得可行流f 如圖所示：（1，1）（2，1）v1v3（4，4）（5，4）（3，3）（3，1）（s，）（3，0）（1，0）（1，1）vtvs（2，2）（5，3）（2，2）v4v2（s，3）去掉各點標號，從vs開始，重新標號。v1v3（4，4）（5，4）（3，3）（s，）（3，0）（1，0）（1，1）vtvs（2，2）（5，3）（2，2）v4v2（s，2）標號至點v2：標號過程無法進行，所以f 即為最大流。v1v3（4，4）（5，4）（3，3）（s，）（3，0）（1，0）（1，1）vtvs（2，2）（5，3）（2，2）v4v2（s，2）=vs，v2，=v1，v3，v4，vt截集（，）=（vs，v1），（v2，v1），（v2，v4）V（ f ）=C（，）=3+1+2=6v3v16、求下圖所示網(wǎng)絡(luò)的最大流：（9，5）（5，5）（8，6）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（9，7）v4v2圖中為（Cij，fij）解：此為網(wǎng)絡(luò)分析之“尋求網(wǎng)絡(luò)最大流問題”，可用“尋求網(wǎng)絡(luò)最大流的標號法（福特富克爾遜算法）”解決如下：標號過程：1、給vs標上（0，）；2、檢查vs，在?。╲s，v1）上，fs1=6，Cs1=8，fs1Cs1，給v1標號(s，(v1)，其中，v3v1（s，2）（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（s，3）（9，7）v4v2同理，給v2標號(s，(v2)，其中，3、檢查v1，在?。╲1，v3）上，f13=5，C13=9，f13C13，給v3標號(1，(v3)，其中，v3v1（1，2）（s，2）（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（2，2）（s，3）（9，7）v4v2檢查v2，同理，給v4標號(2，(v4)，其中，4、檢查v3，在?。╲3，vt）上，f3t=C3t=5，不滿足標號條件，v3v1（1，2）（s，2）（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（2，2）（s，3）（9，7）v4v2檢查v4，在?。╲4，vt）上，f4t=5，C4t=10，f13C13，給vt標號(4，(vt)，其中，vt得到標號，標號過程結(jié)束。調(diào)整過程：從vt開始逆向追蹤，找到增廣鏈。（s，2）v1v3（1，2）（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（9，7）v4v2（2，2）（s，3）（vs，v2，v4，vt），=2，在上進行流量=2的調(diào)整，得可行流f 如圖所示：（1，2）（s，2）v3v1（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，7）（7，6）v4v2（9，9）（2，2）（s，3）去掉各點標號，從vs開始，重新標號。（1，2）（s，2）v3v1（9，5）（5，5）（8，6）（4，2）（0，）（6，2）（2，2）（5，1）vtvs（10，7）（7，6）v4v2（9，9）（3，2）（s，1）vt又得到標號，標號過程結(jié)束。再次從vt開始逆向追蹤，找到增廣鏈。（1，2）（s，2）v3v1（9，5）（5，5）（8，6）（4，2）（0，）（6，2）（2，2）（5，1）vtvs（10，7）（7，6）v4v2（9，9）（3，2）（s，1）（vs，v1，v3，v4，vt），=2，在上進行流量=2的調(diào)整，得可行流f 如圖所示：（1，2）（s，2）v3v1（9，7）（5，5）（8，8）（4，2）（0，）（6，0）（2，2）（5，1）vtvs（10，9）（7，6）v4v2（9，9）（3，2）（s，1）去掉各點標號，從vs開始，重新標號。（1，1）（2，1）v3v1（9，7）（5，5）（8，8）（0，）（6，0）（2，2）（5，1）vtvs（10，9）（7，6）v4v2（9，9）（s，1）標號至點v3：標號過程無法進行，所以f 即為最大流。v1v3（2，1）（1，1）（9，7）（5，5）（8，8）（0，）（6，0）（2，2）（5，1）vtvs（10，9）（7，6）（9，9）v4v2（s，1）=vs，v2，v1，v3，=v4，vt截集（，）=（v2，v4），（v3，vt）V（ f ）=C（，）=9+5=143、公司擬建一預(yù)制構(gòu)件廠，一個方案是建大廠，需投資300萬元，建成后如銷路好每年可獲利100萬元，如銷路差，每年要虧損20萬元，該方案的使用期均為10年；另一個方案是建小廠，需投資170萬元，建成后如銷路好，每年可獲利40萬元，如銷路差每年可獲利30萬元；若建小廠，則考慮在銷路好的情況下三年以后再擴建，擴建投資130萬元，可使用七年，每年盈利85萬元。假設(shè)前3年銷路好的概率是0.7，銷路差的概率是0.3，后7年的銷路情況完全取決于前3年；試用決策樹法選擇方案。解：這個問題可以分前3年和后7年兩期考慮，屬于多級決策類型，如圖所示。403銷路好0.7P=1P=1后7年前3年建大廠(300)100103010建小廠（170）銷路好0.7銷路差0.31-2010擴建(130)不擴建8574072銷路差0.334決策樹圖示考慮資金的時間價值，各點益損期望值計算如下：點：凈收益100(P/A，10，10)0.7+(-20)（P/A，10，10）0.3-300=93.35(萬元)點：凈收益85(P/A，10，7)1.0-130=283.84(萬元)點：凈收益40(P/A，10，7)1.0=194.74(萬元)可知決策點的決策結(jié)果為擴建，決策點的期望值為283.84+194.7447