運(yùn)籌學(xué)-總復(fù)習(xí)_第1頁(yè)
運(yùn)籌學(xué)-總復(fù)習(xí)_第2頁(yè)
運(yùn)籌學(xué)-總復(fù)習(xí)_第3頁(yè)
運(yùn)籌學(xué)-總復(fù)習(xí)_第4頁(yè)
運(yùn)籌學(xué)-總復(fù)習(xí)_第5頁(yè)
已閱讀5頁(yè)，還剩69頁(yè)未讀， 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明：本文檔由用戶(hù)提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

運(yùn)籌學(xué)復(fù)習(xí)求解如下線(xiàn)性規(guī)劃問(wèn)題例1復(fù)習(xí)解：加入松弛變量，標(biāo)準(zhǔn)化得建立單純形表如下：復(fù)習(xí)復(fù)習(xí)解畢復(fù)習(xí)用對(duì)偶單純形法計(jì)算例2復(fù)習(xí)解：為了便于尋找初始正則解，將問(wèn)題變形為：取{x4,x5}為初始正則解，列單純形表如下：復(fù)習(xí)-2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4[-2]1-3010-2-3-4由于初始正則解有負(fù)分量，于是取min{-3,-4}=-4x5為換出變量，取x1為換入變量，得新基{x4,x1}，51=-2為主元復(fù)習(xí)基變換的過(guò)程：主元變?yōu)?，即用-2去除單純形表中基變量x5所在的行；主元所在列的其它元變?yōu)?，消去非基變量x1所在的列的其余元-1，-2；得新基{x4,x1}的單純形表-2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4[-2]1-3010-2-3-4復(fù)習(xí)基變換的過(guò)程：-2-3-4XBbx1x2x3x4x5x4x1-2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4[-2]1-3010-2-3-421-1/23/20-1/2-10-5/21/21-1/240-4-10-1復(fù)習(xí)-2-3-4XBbx1x2x3x4x5x4x121-1/23/20-1/2-10-5/21/21-1/240-4-10-1可見(jiàn)正則解的有負(fù)分量，由于x4=1,所以取x4為換出變量，取x2為換入變量，得新基{x2,x1}，42=-5/2為主元復(fù)習(xí)-2-3-4XBbx1x2x3x4x5x22/501-1/5-2/51/5x111/5107/5-1/5-2/528/500-3/5-8/5-1/5此時(shí)正則解是可行解，也是最優(yōu)解。X*=(11/5，2/5，0，0，0)；z*=-28/5進(jìn)行基變換，得新正則解的單純形表：復(fù)習(xí)(1)寫(xiě)出下列線(xiàn)性規(guī)劃的對(duì)偶規(guī)劃(2)試用對(duì)偶原理求解線(xiàn)性規(guī)劃問(wèn)題已知其對(duì)偶規(guī)劃的最優(yōu)解為例3復(fù)習(xí)解：該問(wèn)題的對(duì)偶規(guī)劃為復(fù)習(xí)利用松緊關(guān)系，代入對(duì)偶規(guī)劃的約束條件得下列約束是松約束，將最優(yōu)解松約束緊約束其對(duì)偶約束是緊約束復(fù)習(xí)設(shè)原問(wèn)題的最優(yōu)解為緊約束復(fù)習(xí)設(shè)某種物資有3個(gè)產(chǎn)地A1，A2，A3，

生產(chǎn)量分別為9，5，7;有4個(gè)銷(xiāo)地B1，B2，B3，B4，銷(xiāo)售量分別為3，8，4，6

;已知從Ai到Bj

物資的單位運(yùn)價(jià)見(jiàn)下表。求總運(yùn)費(fèi)最小的調(diào)運(yùn)方案。B1B2B3B4產(chǎn)量A1291079A213425A384257銷(xiāo)量3846例4復(fù)習(xí)存在基變量為0的解稱(chēng)為退化解。在確定初始基可行解的過(guò)程中，如果某一步中出現(xiàn)情況：當(dāng)產(chǎn)地Ai處的余量與銷(xiāo)地Bj處的需求量相等時(shí)，在格(i,j)填入運(yùn)量后，產(chǎn)地Ai處的余量與銷(xiāo)地Bj處的銷(xiāo)量同時(shí)為0,相應(yīng)地要?jiǎng)澣ヒ恍泻鸵涣小＿@時(shí)就出現(xiàn)了退化。為了使基變量個(gè)數(shù)恰好有m+n-1個(gè)，應(yīng)在同時(shí)劃去的一行或一列中的某個(gè)格中填入數(shù)字0，表示這格中的變量是取值為0的基變量；復(fù)習(xí)B1B2B3B4ai行差A(yù)1291079A213425A384257bj3846列差伏格爾法計(jì)算1用伏格爾法尋找初始基：先算出運(yùn)價(jià)表中各行與各列的最小運(yùn)費(fèi)與次小運(yùn)費(fèi)的差額，并填入該運(yùn)價(jià)表的最右列和最下行。從行差或列差中選出最大者，并選擇其所在行或列的最小元素。A1的行差最大，而其中運(yùn)價(jià)c11最小,令x11為優(yōu)先運(yùn)輸路線(xiàn)。5121123復(fù)習(xí)B1B2B3B4ai行差A(yù)12910795A2134251A3842572bj3846列差11230303/09/6用伏格爾法尋找初始基：銷(xiāo)地B1的銷(xiāo)量3全由產(chǎn)地A1供給，所以x21=x31=0。將x11=3填到調(diào)運(yùn)方案表中第1行第1列上。畫(huà)去運(yùn)輸數(shù)據(jù)表第一列，A1的產(chǎn)量剩余為9-3=6。得到新的產(chǎn)銷(xiāo)平衡與單位運(yùn)價(jià)表.令伏格爾法計(jì)算1復(fù)習(xí)B1B2B3B4ai行差A(yù)1291079/65A2134251A3842572bj3/0846列差11230306/15/0用伏格爾法尋找初始基：再算出運(yùn)價(jià)表中的行差與列差。B4的列差最大，而其中運(yùn)價(jià)c24最小,令x24為優(yōu)先運(yùn)輸路線(xiàn)。產(chǎn)地A2的產(chǎn)量2全供給銷(xiāo)地B4，所以x23=x24=0。畫(huà)去運(yùn)輸數(shù)據(jù)表中第2行，B4的銷(xiāo)量還要6-5=1。得新表。521122112233050令伏格爾法計(jì)算1復(fù)習(xí)B1B2B3B4ai行差A(yù)1291079/65A213425/01A3842572bj3/0846/1列差11230304/07/3用伏格爾法尋找初始基：5211221122330505221122211522833204伏格爾法計(jì)算1復(fù)習(xí)B1B2B3B4ai行差A(yù)1291079/65A213425/01A384257/32bj3/084/06/1列差11230308/57/3/0用伏格爾法尋找初始基：521122112233050522112221152283320452221122211155228332203伏格爾法計(jì)算1復(fù)習(xí)B1B2B3B4ai行差A(yù)1291079/65A213425/01A384257/32bj3/084/06/1列差11230308/57/3/0用伏格爾法尋找初始基：0500452221122211155228332203現(xiàn)在只有一個(gè)產(chǎn)地兩個(gè)銷(xiāo)地，故令x12=5

,x14=1為基變量，將其分別填到調(diào)運(yùn)方案表中1行2列與1行4列上。51得到產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的一個(gè)初始方案伏格爾法計(jì)算1復(fù)習(xí)B1B2B3B4aiA1291079A213425A384257bj3846354351此方案的運(yùn)費(fèi)是3×2+5×9+4×7+5×2+3×4+4×2=88。伏格爾法給出的初始解往往更接近于最優(yōu)解。復(fù)習(xí)利用伏格爾法確定的初始解如下表所示：B1B2B3B4aiA1325910179A2134525A38344257bj38461、寫(xiě)出基可行解對(duì)應(yīng)的位勢(shì)方程組;2、并計(jì)算非基變量的檢驗(yàn)數(shù)。復(fù)習(xí)求解位勢(shì)及檢驗(yàn)數(shù)的過(guò)程可在一個(gè)特殊設(shè)計(jì)的表上完成，這個(gè)表的構(gòu)造如下：在原單位運(yùn)價(jià)表增加一行與一列，在列中填入ui，在行中填入vj；把運(yùn)價(jià)cij記在每一格的右上角，用框標(biāo)定，在基變量對(duì)應(yīng)的格中標(biāo)出0，構(gòu)成表。復(fù)習(xí)由u1+v1=2,u1+v2=9,u1+v4=7,得v1=2,v2=9,v4=7;B1B2B3B4uiA102091007A213402A3804025vj0-5-52977位勢(shì)表：再由u2+v4=2，u3+v2=4，得u2=-5，u3=-5;最后由u3+v3=2得v3=7.取u1=0;復(fù)習(xí)檢驗(yàn)數(shù)表：(計(jì)算所有非基變量的檢驗(yàn)數(shù))B1B2B3B4uiA102091007A213402A3804025vj0-5-52977(3)(4)(-1)(2)(11)(3)當(dāng)存在非基變量的檢驗(yàn)數(shù)kl

≥0，說(shuō)明現(xiàn)行方案為最優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。復(fù)習(xí)伏格爾法的初始方案：B1B2B3B4uiA1325910170A213452-5A3834425-5vj2977(3)(4)(-1)(2)(11)(3)x22為換入變量,

從x22所在格出發(fā)做閉回路L,L中有兩個(gè)偶點(diǎn)x24,x12，取x12為換出變量，調(diào)整量為5.復(fù)習(xí)伏格爾法的調(diào)整方案：B1B2B3B4aiA1325910179A21034525A38344257bj3486在閉回路L上，偶點(diǎn)變量減5，奇點(diǎn)變量加5.0x22為換入變量,取x12為換出變量.065復(fù)習(xí)它所對(duì)應(yīng)的位勢(shì)與檢驗(yàn)數(shù)為：B1B2B3B4uiA13291067A2153402A3834425vj28670-5-4(1)(4)(4)(3)(10)(2)所有檢驗(yàn)數(shù)都非負(fù)，迭代停止，運(yùn)費(fèi)為：3×2+6×7+5×3+3×4+4×2=83復(fù)習(xí)P1：充分利用現(xiàn)有工時(shí)，必要時(shí)可以加班；P2：A，B，C的最低產(chǎn)量分別為5，5，8臺(tái)，并依單位工時(shí)的利潤(rùn)比例確定權(quán)系數(shù)；P3：生產(chǎn)線(xiàn)加班時(shí)每月不超過(guò)20小時(shí)；P4：A，B，C的月銷(xiāo)售指標(biāo)分別定為10，12，10臺(tái)，依單位工時(shí)利潤(rùn)比例確定權(quán)系數(shù).試建立目標(biāo)規(guī)劃模型.A、B、C三種計(jì)算機(jī)，在一條生產(chǎn)線(xiàn)上裝配。裝配時(shí)間分別為5，8，12小時(shí)；利潤(rùn)分別為每臺(tái)1000元，1440元，2520元。生產(chǎn)線(xiàn)每月正常運(yùn)轉(zhuǎn)170小時(shí)。該廠(chǎng)的經(jīng)營(yíng)目標(biāo)為：例5復(fù)習(xí)復(fù)習(xí)在5個(gè)地點(diǎn)中選3處建生產(chǎn)同一產(chǎn)品的工廠(chǎng)，在這5個(gè)地點(diǎn)建廠(chǎng)所需投資，占用農(nóng)田，建成以后的生產(chǎn)能力等數(shù)據(jù)如下表所示。地點(diǎn)12345所需投資（萬(wàn)元）320280240210180占用農(nóng)田（畝）201815118生產(chǎn)能力（萬(wàn)噸）7055422811現(xiàn)在有總投資800萬(wàn)元，占用農(nóng)田指標(biāo)60畝，應(yīng)如何選擇廠(chǎng)址，使建成后總生產(chǎn)能力最大。例6復(fù)習(xí)復(fù)習(xí)解：設(shè)五個(gè)0—1變量x1，x2，x3，x4，x5，其中i=1,2,3,4,5.建立整數(shù)規(guī)劃模型為

Maxz=70x1+55x2+42x3+28x4+11x5s.t.320x1+280x2+240x3+210x4+180x580020x1+18x2+15x3+11x4+8x5

60x1+x2+x3+x4+x5=3x1，x2，x3，x4，x5=0,1利用割平面算法求解下面的規(guī)劃問(wèn)題例7復(fù)習(xí)解：將約束條件的系數(shù)化整；去掉“x1,x2是整數(shù)”的條件，得到一個(gè)線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)型（LP1）為：利用單純形法求解這個(gè)線(xiàn)性規(guī)劃問(wèn)題，得出最終單純形表：

3200

x1

x2

x3

x4

x2

x1

2.53.25

011/2-1/210-1/43/4

σj

00-1/4-5/4復(fù)習(xí)最優(yōu)解不是整數(shù)解，由最終表得到變量之間的關(guān)系：

3200

x1

x2

x3

x4

x2

x1

2.53.25

011/2-1/210-1/43/4

σj

00-1/4-5/4將上面的約束條件當(dāng)中的變量和系數(shù)改寫(xiě)成整數(shù)與非負(fù)真分?jǐn)?shù)的和把整數(shù)部分放在左邊，非整數(shù)部分放在右邊。下面增加割平面，選真分?jǐn)?shù)最大的一個(gè)由于上式左端是整數(shù)，因此右端也應(yīng)是整數(shù)，由于變量都是不小于0的整數(shù)，所以上式右端必是一個(gè)不大于0.5的整數(shù)，即稱(chēng)這個(gè)不等式為一個(gè)割平面。引入一個(gè)松弛變量，化割平面為：將它作為一個(gè)新增加的約束條件加入線(xiàn)性規(guī)劃LP1中得到一個(gè)新的線(xiàn)性規(guī)劃LP2

；或者直接反映到LP1的最終單純形表中，得LP2單純形表：割平面的處理：復(fù)習(xí)LP2的單純形表：

32000x1

x2

x3

x4

x5x2x1x55/213/4-1/2

011/2-1/2010-1/43/4000[-1/2]-1/21

00-1/4-5/40

3200

x1

x2

x3

x4

x2

x1

2.53.25

011/2-1/210-1/43/4

σj

00-1/4-5/4LP1

：LP2

：復(fù)習(xí)

32000

x1

x2

x3

x4

x5

σj

00-1/4-5/40x2x1x327/21

010-111001-1/20011-2

σj

000-1-1/2由于不是整數(shù)解，找出不滿(mǎn)足條件的基變量x1.用對(duì)偶單純型法求解：復(fù)習(xí)將它作為一個(gè)新增加的約束加到線(xiàn)性規(guī)劃LP2中又得一個(gè)線(xiàn)性規(guī)劃LP3∶構(gòu)造線(xiàn)性規(guī)劃LP2的割平面復(fù)習(xí)LP3

：LP3的單純形表：

320000

x1

x2

x3

x4

x5

x6x2x1x3x6

27/21-1/2

σj

000-10-1復(fù)習(xí)

320000

x1

x2

x3x4

x5

x6

σj

000-1-1/20x2x1x3x5

1431

σj

000-10-1從上表中我們可以看到，已經(jīng)找到了整數(shù)最優(yōu)解：x1=4,x2=1。故求解結(jié)束。用對(duì)偶單純型法求解：復(fù)習(xí)有一份資料，要分別譯成四種文字，現(xiàn)有甲、乙、丙、丁四人可以承擔(dān)這項(xiàng)工作。因?yàn)楦魅藢?zhuān)長(zhǎng)不同，他們翻譯成不同文字所需要的時(shí)間用效率矩陣C表示。應(yīng)如何分配工作，使他們完成任務(wù)的總時(shí)間最短？Ⅰ

Ⅱ

Ⅲ

Ⅳ例8Step1、先對(duì)效率矩陣進(jìn)行列變換，使其各行各列中都出現(xiàn)0元素.效率矩陣變換方法為：從效率矩陣C

的每行元素中減去該行的最小元素,得矩陣B

；從矩陣B

中每列元素中減去該列的最小元素得矩陣C1

。

min0050Step2、確定C1中線(xiàn)性獨(dú)立的0元素.從第一行開(kāi)始，若該行只有一個(gè)0元素，就對(duì)這個(gè)0元素加圈，然后劃去其所在列的其它0元素;若該行沒(méi)有其它0元素或有兩個(gè)以上0元素（已劃去的不計(jì)），轉(zhuǎn)下一行；直到最后一行為止。然后,從第一列開(kāi)始,若該列只有一個(gè)0元素,就對(duì)這個(gè)0元素加圈（同樣不考慮已劃的）,再劃去其所在行的其它0元素;若該列沒(méi)有0元素或有兩個(gè)以上0元素，則轉(zhuǎn)下列直到最后一列為止。重復(fù)上述步驟.上述步驟可能出現(xiàn)三種情況情況一：矩陣每行都有一個(gè)打圈的0元素。此時(shí)得到問(wèn)題的最優(yōu)解.情況二：有多于兩行或兩列存在兩個(gè)以上的未處理的0元素，即出現(xiàn)0元素的閉回路。此時(shí)，可從中任選一個(gè)0元素加圈，劃掉其同行同列的0元素，再重復(fù)上述兩個(gè)步驟。情況三：矩陣中所有0元素或被加圈，或被劃去，而已加圈的0元素m小于矩陣的行數(shù)n。即矩陣中至少存在有一行不含加圈的0元素。轉(zhuǎn)步驟三。Step3尋找能覆蓋C1中所有0元素的最小直線(xiàn)數(shù).(1)按照從上到下、從左到右的順序?qū)1沒(méi)有加圈的0元行打√號(hào)；(2)對(duì)已打√號(hào)的行中未加圈0元的列打√號(hào)；(3)對(duì)已打√號(hào)的列中加圈0元的行打√號(hào)；(4)重復(fù)下去，直到找不出打√號(hào)的行、列為止。√

(5)對(duì)沒(méi)打√號(hào)的行劃一橫線(xiàn)，對(duì)打√號(hào)的列劃一縱線(xiàn)，這就是覆蓋矩陣C1中所有0元素的最小直線(xiàn)數(shù).√

√

Step4、改進(jìn)C1(1)尋找C1

沒(méi)有被直線(xiàn)覆蓋的所有元素中的最小元素θ；例中θ=2.(2)在已打√號(hào)的行中減去θ；(3)在已打√號(hào)的列中加上θ；得到一個(gè)新矩陣C2?！?/p>

√

√

-2603-292301340054300用C2代替C1，返回步驟2.即例題的最優(yōu)分配方案：確定C2中線(xiàn)性獨(dú)立的0元素.

用dijkstra算法求下圖從頂點(diǎn)V1到其余各點(diǎn)的最短路徑：例9V1112921865129734136971V1V2V3V4V5V6V7V8V9V1024V1112921865129734136971V1V2V3V4V5V6V7V8V9V1024V1112921865129734136971V1V2V3V4V5V6V7V8V9V1002∞8∞∞∞∞∞∞1240∞∞∞∞∞∞∞∞∞∞V1112921865129734136971V1V2V3V4V5V6V7V8V9V1002∞8∞10∞∞∞∞124V1112921865129734136971V1V2V3V4V5V6V7V8V9V10038∞10∞∞∞∞1224V1112921865129734136971V1V2V3V4V5V6V7V8V9V10081210∞∞6512324V1112921865129734136971V1V2V3V4V5V6V7V8V9V10081210∞146123524V111921865129734136971V1V2V3V4V5V6V7V8V9V10071210∞1412356242V111921865129734136971V1V2V3V4V5V6V7V8V9V100129111921865129734136971V1V2V3V4V5V6V7V8V9V1001210141235679242V111921865129734136971V1V2V3V4V5V6V7V8V9V1001114121056793242V111921865129734136971V1V2V3V4V5V6V7V8V9V1001210567932411132求下圖s→t的最大流stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●網(wǎng)絡(luò)最大流例10stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●解:(1)在已知可行流的基礎(chǔ)上，通過(guò)標(biāo)號(hào)尋找增廣鏈。(∞)ε(2)=min{∞,6}=6(6)ε(3)=min{6,2}=2(2)ε(t)=min{2,5}=2(2)存在增廣鏈s→v2→v3→t網(wǎng)絡(luò)最大流(2)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●(∞)(6)(2)(2)網(wǎng)絡(luò)最大流(3)擦除原標(biāo)號(hào)，重新搜尋增廣鏈。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)(6)(2)(2)網(wǎng)絡(luò)最大流(4)重新搜尋增廣鏈。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)ε(2)=min{∞,4}=4(4)(1)ε(5)=min{4,1}=1ε(3)=min{1,2}=1(1)(1)ε(t)=min{1,3}=1存在增廣鏈：s→v2→v5→v3→t網(wǎng)絡(luò)最大流(5)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。stv1v2v3v4v54(3)3(2)10(6)3(2)1

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論