運(yùn)籌學(xué)復(fù)習(xí)資料ppt課件(已修改)
2025-01-27 13:29 本頁(yè)面
【正文】 某市準(zhǔn)備在下一年度預(yù)算中購(gòu)置一批救護(hù)車，已知每輛救護(hù)車購(gòu)置價(jià)為 20萬(wàn)元。救護(hù)車用于所屬的兩個(gè)郊區(qū)縣 ,各分配 xA和 xB臺(tái)， A縣救護(hù)站從接到求救電話到救護(hù)車出動(dòng)的響應(yīng)時(shí)間為 (40 xA)min， B縣相應(yīng)的響應(yīng)時(shí)間為 (50 4 xB )min，該市確定如下優(yōu)先級(jí)目標(biāo)。 P1：救護(hù)車購(gòu)置費(fèi)用不超過(guò) 400萬(wàn)元。 要求建立目標(biāo)規(guī)劃模型。 P2： A縣的響應(yīng)時(shí)間不超過(guò) 5min。 P3： B縣的響應(yīng)時(shí)間不超過(guò) 5min。 Ax1 1 2 2 3 3112233m in z20 20 40 040 3 5 .50 4 5, 0 。 , 0 , ( 1 , 2 , 3 )? ? ?????????? ? ?? ? ? ? ??? ? ? ???? ? ? ??? ? ? ??ABABA B i iP d P d P dx x d dx d dx d dx x d d i 解 設(shè) 為分配給 A縣的救護(hù)車數(shù)量， 其目標(biāo)規(guī)劃模型 為： Bx為分配給 B縣的救護(hù)車數(shù)量。 目標(biāo)規(guī)劃 某工廠計(jì)劃生產(chǎn) A、 B兩種產(chǎn)品，每噸產(chǎn)品的耗電量指 標(biāo)、原材料消耗、單位產(chǎn)品利潤(rùn)及資源限量如表所示。 – 廠長(zhǎng)首先考慮要充分利用供電部門分配的電量限額 66， – 然后考慮利潤(rùn)不低于 100元； – 據(jù)市場(chǎng)調(diào)查結(jié)果，希望 B產(chǎn)品的產(chǎn)量不低于 A產(chǎn)品的產(chǎn)量， – 問(wèn)應(yīng)如何制定產(chǎn)品 A、 B的產(chǎn)量。建立該目標(biāo)規(guī)劃的數(shù)學(xué)模型。 產(chǎn)品 資源 A B 資源限量 電力 10 12 66 原材料 2 1 8 單位產(chǎn)品利潤(rùn) 10 20 目標(biāo)規(guī)劃 解： 設(shè) x x2分別 表示 A、 B兩種產(chǎn)品的產(chǎn)量 ， 則目 標(biāo)規(guī)劃模型如下： minZ=P1 (d1 + d1+ ) + P2d2 + P3d3 2x1+x2 ≤8 10x1+12x2 +d1 d1+ =66 10x1+20x2 +d2 d2+ =100 x1+x2 +d3 d3+ =0 x1,x2 ,d1 ,d1+ ,d2 , d2+ ,d3 , d3+ ≥0 6個(gè)人完成 4項(xiàng)工作，由于個(gè)人和技術(shù)專長(zhǎng)不同，他們完成 4項(xiàng)工作任務(wù)所獲得收益如下表： Ⅰ Ⅱ Ⅲ Ⅳ 1 3 5 4 5 2 6 7 6 8 3 8 9 8 8 4 10 10 9 11 5 12 11 10 12 6 13 12 11 13 且規(guī)定每人只能做一項(xiàng)工作，一項(xiàng)工作任務(wù)只需一人操作，試求使 總收益最大的分派方案。 解 此問(wèn)題是一個(gè)非標(biāo)準(zhǔn)的指派問(wèn)題 ， 虛設(shè)兩項(xiàng)任務(wù) Ⅴ ， Ⅵ 并設(shè)任務(wù)的收益為 0， 化為標(biāo)準(zhǔn)的指派問(wèn)題 。 標(biāo)準(zhǔn)的指派問(wèn)題的收益矩陣為： ? ?3 5 4 5 0 06 7 6 8 0 08 9 8 10 0 010 10 9 11 0 012 11 10 12 0 013 12 11 13 0 0????????? ??????????ijc6611m a x??? ??目 標(biāo) 函 數(shù) ： i j i jijz c x 將其化為極小值問(wèn)題 。 ? ?10 8 9 8 13 137 6 7 5 13 135 4 5 3 13 133 3 4 2 13 131 2 3 1 13 130 1 2 0 13 13????????? ? ??????????ijc 最優(yōu)解矩陣為： ? ?0 0 0 0 0 10 0 0 0 1 00 0 0 1 0 00 0 1 0 0 00 1 0 0 0 01 0 0 0 0 0????????? ? ??????????ijc 最優(yōu)分派方案為：第 3個(gè)人做第 Ⅳ 項(xiàng)工作 ， 第 4個(gè)人 做第 Ⅲ 項(xiàng)工作 ， 第 5個(gè)人做第 Ⅱ 項(xiàng)工作 ， 第 6個(gè)人做第 Ⅰ 項(xiàng)工作 ， 所得最大總收益為： m a x 6 13 ( 13 13 3 4 2) 43? ? ? ? ? ? ? ? z?用 FordFulkerson標(biāo)號(hào)法求下圖中從 s到 t的最大流及其流量， ?并求網(wǎng)絡(luò)的最小割?；∨詳?shù)字為（ cij， fij）。 ?解用 FordFulkerson標(biāo)號(hào)法求出網(wǎng)絡(luò)的增廣鏈，如下圖中虛線所示。（ 5分） 因此，網(wǎng)絡(luò)中的可行流不是最大流，將其調(diào)整后得一新的可行流，如下圖所示（ 2分） ?再用標(biāo)號(hào)法在上圖中找增廣鏈，標(biāo)號(hào)法中斷，表明已找不出增廣鏈，故上圖中的可行流即為最大流，其流量為 5+3+5=13。最小割為： ( , ) ={ ( , ) ,( , ) ,( A ,B ) }V V s D s C3分 第 11章 網(wǎng)絡(luò)計(jì)劃 例 ()：根據(jù)下表給定的條件，繪制 PERT網(wǎng)絡(luò)圖。 作 業(yè) 代 號(hào) 緊 前作 業(yè) 作 業(yè) 代 號(hào) 緊 前作 業(yè) A 無(wú) H B B 無(wú) I E , H C 無(wú) J E , H D A , B K C , D , F , J E B L K F B M L, I , G G F , C A B C D E F G H I J K L M 1 3 9 8 7 6 5 4 2 10 1 (10分 ) 、寫出如下線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題，并利用弱對(duì)偶性說(shuō)明 z的最大值不大于 1。 1 2 31 2 31 2 31 2 31 2 3221 .2200m ax,z
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1