374管理運籌學(xué)第十二章排序與統(tǒng)籌方法§1§2車間作業(yè)計劃模型統(tǒng)籌方法375管理運籌學(xué)§1車間作業(yè)計劃模型車間作業(yè)計劃是指一個工廠生產(chǎn)工序的計劃和安排。一、一臺機器、n個零件的排序問題二、兩臺機器、n個零件的排序問題376管理運籌學(xué)§1車間作業(yè)計劃模型一、一臺機器、n個零件的排序問題 例1．某車間只有一臺高精度的磨床，常出現(xiàn)很多零件同時要求這臺磨床加工的情況，現(xiàn)有六個零件同時要求加工，這六個零件加工所需時間如表12-1所示。

表12-1零件零件123加工時間（小時）

1.8 2.0 0.5456加工時間（小時）

0.9 1.3 1.5

應(yīng)該按照什么樣的加工順序來加工這六個零件，才能使得這六個零件在車間里停留的平均時間為最少？∑P∑P377管理運籌學(xué)§1車間作業(yè)計劃模型解：如果我們用Pi表示安排在第i位加工的零件所需的時間，用Tj表示安排在第j位加工的零件在車間里總的停留時間，則有i

ji=1Tj=P1+P2++Pj?1+Pj=

不同的加工順序得到不同的各零件的平均停留時間，如何得到一個使得各零件的平均停留時間最少的排序呢？這就是我們最后要解決的優(yōu)化問題，而且我們要設(shè)法找到一種簡便的算法。對于某種加i

ji=1工順序，我們知道安排在第j位加工的零件在車間里總的停留時間Tj=1113131351356135可知這六個零件的停留時間為

T1+T2+T3+T4+T5+T6

=P+(P+P2)+(P+P2+P)+(P+P2+P+P4)+

(P+P2+P+P4+P)+(P+P2+P+P4+P+P)

=6P+5P2+4P+3P4+2P+P6那么各個零件平均停留時間為6P1+5P2+4P3+3P4+2P5+P6

6

從上式可知，對于一臺機器n個零件的排序問題，只要系數(shù)越大，配上加工時間越少的，即按照加工時間排出加工順序，加工時間越少的零件排在越前面，加工時間越多的零件排在越后面，可使各個零件的平均停留時間為最少。也就是按照3，4，5，6，1，2的順序來加工零件，可使各個零件的平均停留時間為最少。378管理運籌學(xué)§1車間作業(yè)計劃模型

按照3，4，5，6，1，2的順序來加工零件，各個零件的停留時間如表12-2所示。

表12-2零件

3 4 5加工時間

0.5 0.9 1.3停留時間

0.5 1.4 2.7零件

6 1 2加工時間

1.5 1.8 2.0停留時間

4.2 6.0 8各個零件的平均停留時間為0.5+1.4+2.7+4.2+6.0+8.0 6=3.8h

這與用“先到先加工”順序所需平均停留時間4.93相比較，有很大的進(jìn)步。對于一臺機器n個零件的排序問題，我們按照加工時間從少到多排出加工零件的順序就能使各個零件的平均停留時間為最少。379管理運籌學(xué)§1車間作業(yè)計劃模型二、兩臺機器、n個零件 例2．某工廠根據(jù)合同定做一些零件，這些零件要求先在車床上車削，然后再在磨床上加工，每臺機器上各零件加工時間如表12-3所示。

表12-3零件

1 2車床

1.5 2.0磨床

0.50.25零件

4 5車床1.250.75磨床

2.51.2531.01.75

應(yīng)該如何安排這五個零件的先后順序，才能使完成這五個零件的總的加工時間為最少？ 解：由于每個零件必須先進(jìn)行車床加工，再進(jìn)行磨床加工，所以在車床上加工零件的順序與在磨床上加工零件的順序是一樣的。 如果這些零件在車床上和磨床上加工順序都為1，2，3，4，5。我們用圖12-1中的線條圖來表示各零件加工的開始時間與完成時間，這種圖是由一根時間軸和車床、磨床在每個時間段的狀況的圖形所構(gòu)成。380管理運籌學(xué)§1車間作業(yè)計劃模型

圖12-1

從上圖中我們可以看出，加工時間的延長主要是由于磨床的停工待料造成的，只要減少磨床的停工待料的時間，就能減少整個加工任務(wù)的總時間。為了減少磨床的停工待料，我們應(yīng)該一方面把在車床上加工時間越短的零件越早加工，減少磨床等待的時間；另一方面把在磨床上加工時間越短的零件越晚加工，以便充分利用前面的時間，這樣我們就得到了使完成全部零件加工任務(wù)所需總時間最少的零件排序方法。381管理運籌學(xué)§1車間作業(yè)計劃模型

尋找例2的最優(yōu)解：我們在表12-5中找到所列出的最短加工時間是0.25，它是第二道工序磨床加工零件2的所需時間，由于這個時間與磨床有關(guān)，故我們把零件2放在加工順序的末尾，即第五位，并在表中劃去零件2所在行，如表12-4中紅色線條所示。

表12-4零件

1 2

車床（第一工序）

1.5 2.0

磨床（第二工序）

0.5 0.25零件

4 5

車床（第一工序）

1.25 0.75

磨床（第二工序）

2.5 1.2531.01.75

接著，我們又找到最短加工時間為0.5，這一時間與磨床（第二工序）有關(guān)，我們把磨床加工時間為0.5的零件1放到除第五外的加工順序的末尾，即第四位加工，同時把表中的零件1所在的行劃去，如表12-4中黃色線條所示。 下一個最短加工時間為0.75，這個加工時間是車床（第一工序）加工零件5的所需時間，故把零件5排在加工順序的第一位上，同時把表中的零件5所在的行劃去，如表12-4中藍(lán)色線條所示。382管理運籌學(xué)§1車間作業(yè)計劃模型

同樣，下一個最短加工時間為1，這是車床加工零件3的所需時間，故把零件3排在第二位上，同時把零件3所在的行劃去，如表12-4中黑色線條所示。 這樣就得到了最優(yōu)加工順序：5，3，4，1，2。一共只需7個小時就能完成全部加工。 從例2中我們可以歸納出關(guān)于兩臺機器n個零件的排序問題，使得全部任務(wù)總的時間最短的排序算法。 在加工所需時間表上選出最短加工時間tij，這是第i工序加工j零件所需時間，當(dāng)i=1時，將零件j的順序盡量靠前，若i=2時，將零件j的順序盡量靠后。在表上劃去零件j的所在行，回到步驟1。383管理運籌學(xué)§2統(tǒng)籌方法

統(tǒng)籌方法包括繪制計劃網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)，下面進(jìn)行分別討論。一、計劃網(wǎng)絡(luò)圖 統(tǒng)籌方法的第一步工作就是繪制計劃網(wǎng)絡(luò)圖，也就是將工序（或稱為活動）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。 例3．某公司研制新產(chǎn)品的部分工序與所需時間以及它們之間的相互關(guān)系都顯示在其工序進(jìn)度表，如表12-5所示，請畫出其統(tǒng)籌方法網(wǎng)絡(luò)圖。

表12-5工序代號

a b c d e

工序內(nèi)容產(chǎn)品設(shè)計與工藝設(shè)計 外購配套零件 外購生產(chǎn)原料 自制主件 主配件可靠性試驗所需時間（天) 60 15 13 38 8緊前工序

—

a a c b,d384管理運籌學(xué)§2統(tǒng)籌方法

解：用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表。 網(wǎng)絡(luò)圖中的點表示一個事件，是一個或若干個工序的開始或結(jié)束，是相鄰工序在時間上的分界點，點用圓圈表示，圓圈里的數(shù)字表示點的編號?；”硎疽粋€工序（或活動），弧的方向是從工序開始指向工序的結(jié)束，弧上是各工序的代號，下面標(biāo)以完成此工序所需的時間（或資源）等數(shù)據(jù)，即對此弧所賦的權(quán)數(shù)。

圖12-2385運§2統(tǒng)籌方法

例4．把例3的工序進(jìn)度表做一些擴充，如表12-6所示，請畫出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。

表12-6工序代號

a b c d所需時間 （天）

60 15 13 38緊前工序

—

a a c

管 理

工序代號

e f g h籌 學(xué)所需時間 （天）

8 10 16 5緊前工序

b，ｄ

d d e，f，g386管理運籌學(xué)§2統(tǒng)籌方法

解：我們把工序f擴充到圖12-2時發(fā)生了問題，由于d是f的緊前工序，故d的結(jié)束應(yīng)該是f的開始，所以代表f的弧的起點應(yīng)該是④，由于工序b的結(jié)束也是④，所以工序b也成了工序f的緊前工序，與題意不符。 為此我們設(shè)立虛工序。虛工序是實際上并不存在而虛設(shè)的工序，用來表示相鄰工序的銜接關(guān)系，不需要人力、物力等資源與時間。

圖12-3387管理運籌學(xué)§2統(tǒng)籌方法

在網(wǎng)絡(luò)圖上添加g、h工序得網(wǎng)絡(luò)圖12-4。

圖12-4

在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許存在兩個點之間多于一條弧，因此增加了一個點和虛工序如圖12-5所示。388管理運籌學(xué)§2統(tǒng)籌方法

圖12-5在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時，要注意圖中不能有缺口和回路。389管理運籌學(xué)§2統(tǒng)籌方法二、網(wǎng)絡(luò)時間與關(guān)鍵路線 在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出以下四方面。 （1）完成此工程項目所需的最少時間。 （2）每個工序的開始時間與結(jié)束時間。 （3）關(guān)鍵路線及其相應(yīng)的關(guān)鍵工序。 （4）非關(guān)鍵工序在不影響工程的完成時間的前提下，其開始時間與結(jié)束時間可以推遲多久。 例5．某公司裝配一條新的生產(chǎn)線，具體過程如表12-7，求：完成此工程的最少時間、關(guān)鍵路線及相應(yīng)的關(guān)鍵工序，各工序的最早開始時間及結(jié)束時間和非關(guān)鍵工序在不影響工程完成時間的前提下，其開始時間與結(jié)束時間可以推遲多久。390管理運籌學(xué)§2

統(tǒng)籌方法表12-7工序代號

a b c d e f g h i j

工序內(nèi)容生產(chǎn)線設(shè)計外購零配件下料、鍛件工裝制造1木模、鑄件機械加工1工裝制造2機械加工2機械加工3

裝配調(diào)試所需時間（天）

60 45 10 20 40 18 30 15 25 35緊前工序

/

a a a a c d d,e g b,i,f,h391管理運籌學(xué)§2統(tǒng)籌方法

解：據(jù)表12-7，繪制網(wǎng)絡(luò)圖，如圖12-6。

圖12-6

如圖12-6所示，①→②→③→⑦→⑧就是一條關(guān)鍵路線，我們要干完所有的工序就必須走完所有這樣的路線，由于很多工序可以同時進(jìn)行，所以網(wǎng)絡(luò)中最長的路線就決定了完成整個工程所需的最少時間，這條路線稱為關(guān)鍵路線。392管理運籌學(xué)§2統(tǒng)籌方法

下面我們給出找關(guān)鍵路線的辦法 首先，從網(wǎng)絡(luò)的發(fā)點開始，按順序計算出每個工序的最早開始時間（ES）和最早結(jié)束時間（EF），設(shè)一個工序所需的時間為t，這對于同一個 工序來說，有EF=ES+t，如圖12-7所示。

圖12-7393管理運籌學(xué)§2統(tǒng)籌方法

圖12-8

其次，從網(wǎng)絡(luò)的收點開始計算出在不影響整個工程最早結(jié)束時間的情況下各個工序的最晚開始時間（縮寫為LS）和最晚結(jié)束時間（縮寫為LF），顯然對同一工序有LS=LF?t。394管理運籌學(xué)§2統(tǒng)籌方法

運用此法則，可以從首點開始計算出每個工序的LF與LS，如圖12-9所示。

圖12-9

接著，可以計算出每一個工序的時差，把在不影響工程最早結(jié)束時間的條件下，工序最早開始（或結(jié)束）的時間可以推遲的時間，稱為該工序的時差，對每個工序來說其時差記為Ts有

Ts=LS–ES=LF–EF395管理運籌學(xué)§2統(tǒng)籌方法最后將各工序的時差，以及其他信息構(gòu)成工序時間表，如表12-8所示。

表12-8工最早開始最晚開始最早完成最晚完成時差是否為關(guān)序

a b c d e f g h i j時間（ES）時間（LS）時間（EF）時間（LF）（LS?ES）

0060600 609010513530 601077011747 606080800 608010012020 701178813547 80801101100 10012011513520 1101101351350 1351351701700鍵工序 是 否 否 是 否 否 是 否 是 是這樣就找到了一條由關(guān)鍵工序a,d,g,i和j依次連成的從發(fā)點到收點的關(guān)鍵路線。396管理運籌學(xué)§2統(tǒng)籌方法三、完成工序所需時間不確定時的網(wǎng)絡(luò)時間和關(guān)鍵路線 當(dāng)完成工序所需時間不確定的情況下怎樣求網(wǎng)絡(luò)時間和關(guān)鍵路線呢，下面我們結(jié)合案例介紹求解辦法。 例6．長征研究院培訓(xùn)中心負(fù)責(zé)明年春天的各干部的工商管理培訓(xùn)，培訓(xùn)中心列出有關(guān)培訓(xùn)組織的各項活動的信息如表12-9所示，要求繪制出統(tǒng)籌方法的網(wǎng)絡(luò)圖，設(shè)法求出網(wǎng)絡(luò)時間和關(guān)鍵路線，并確定開始這個組織工作的時間以保證培訓(xùn)工作如期舉行。 解：由表12-9，繪出統(tǒng)籌方法的網(wǎng)絡(luò)圖如圖12-10所示。

圖12-10397管理運籌學(xué)§2

統(tǒng)籌方法表12-9活動（工序）

a b c d e f g h i

活動（工序）內(nèi)容制定培訓(xùn)計劃選聘培訓(xùn)教師列出一些可供選擇的培訓(xùn)地點確定培訓(xùn)地點確定培訓(xùn)的日程安排落實教學(xué)設(shè)備、器材、資料發(fā)培訓(xùn)通知并確定學(xué)員名單訂旅館房間處理最后的一些事務(wù)緊前活動（工序）

—

a

—

c b,d e b,d g f,h398管理運籌學(xué)§2統(tǒng)籌方法

由于是第一次搞培訓(xùn)，缺乏經(jīng)驗和有關(guān)統(tǒng)計資料來確定完成每個活動所需時間，但對所需時間做了以下三種估計。 （1）樂觀時間，指在順利情況下，完成活動所需最少時間，用a表示。 （2）最可能時間，指在正常情況下，完成活動所需時間，用m表示。 （3）悲觀時間，指不順利情況下，完成活動所需最多時間，用b表示。如表12-10所示。399管理運籌學(xué)表12-10單位：周活動abcdefghi樂觀時間

1.5 2.0 1.0 1.5 0.5 1.0 3.0 3.0 1.5最可能時間

2.0 2.5 2.0 2.0 1.0 2.0 3.5 4.0 2.0悲觀時間

2.5 6.0 3.0 2.5 1.5 3.0 7.0 5.0 2.5(6)σ2=ba=400管理運籌學(xué)§2統(tǒng)籌方法

顯然這三種完成活動所需時間都具有一定概率，由經(jīng)驗，我們可以可以假定這些時間的概率分布近似服從β分布。我們可以用如下公式計算出完成活動所需的平均時間：a+4m+b

6T=以及方差2

?例如：完成活動g所需平均時間：=4a+4m+b3.0+4×3.5+7.0 66Tg=同時求出方差為4。

9401管理運籌學(xué)§2統(tǒng)籌方法同樣可以求出每個活動的完成所需平均時間及方差，如表12-11。

表12-11活動T（平均時間）σ2（方差）活動T（平均時間）σ2方差abcd23220.0280.445 0.1110.028fghi24420.1110.4450.1110.028e10.028402管理運籌學(xué)§2統(tǒng)籌方法

下面就用平均時間代替完成活動所需時間，并在網(wǎng)絡(luò)圖上標(biāo)上每個活動最早開始時間和最早結(jié)束時間，如圖12-11所示。

圖12-11403管理運籌學(xué)同樣也可以標(biāo)上最晚開始時間和最晚完成時間等。

圖12-12404管運籌表12-12活動最早開始最晚開始最早完成最晚完成時差時間（ES）時間（LS）時間（EF）時間（LF）（LS-ES）是否為關(guān)鍵工序abcdefghi

0 2 0 2 5 6 5 913

0 2 1 31011 5 913

2 5 2 4 6 8 91315理

2 5 3 5 11 13 9 13 15學(xué)001155000是是否否否否是是是405管理運籌學(xué)§2統(tǒng)籌方法

從表12-12上我們找到了一條從發(fā)點到收點由關(guān)鍵工序a,b,g,h,i組成的關(guān)鍵路線，用雙線標(biāo)出來。則完成培訓(xùn)工作所需的平均時間為各關(guān)鍵路線的時間之和：

Ta+Tb+Tg+Th+Ti=2+3+4+4+2=15（周） 同時完成時間近似服從一定的概率分布正態(tài)分布，則均值為關(guān)鍵路線上各關(guān)鍵活動之均值之和15，方差也為關(guān)鍵路線上各關(guān)鍵活動方差之和1.05。 由此我們可以計算出此項培訓(xùn)組織工作不同完工時間的概率，如16周內(nèi)完工的概率。T?E(T)

σ為求此概率，可以先求μ值，μ=

式中的T為預(yù)定完工時間16，E（T）=15，σ=1.05=1.025。 算得μ=0.976，查正態(tài)分布函數(shù)表可知概率為φ（μ)=φ(0.976)=0.8355，即在16周內(nèi)完工的概率為83.55%。406管理運籌學(xué)§2統(tǒng)籌方法

其正態(tài)分布圖如圖12-13所示。

圖12-13

如果我們要求以99%的概率來保證培訓(xùn)組織工作如期做完，使培訓(xùn)工作如期舉行，也就是說，概率為99%的完工時間應(yīng)為多少周。在標(biāo)準(zhǔn)

σT=17.39（周）。也就是說只要在培訓(xùn)工作前17.39周開始做培訓(xùn)組織工作就能保證培訓(xùn)工作如期舉行。407管理運籌學(xué)§2統(tǒng)籌方法四、網(wǎng)絡(luò)優(yōu)化 得到初始的計劃方案，但通常要對初始方案進(jìn)行調(diào)整與完善。根據(jù)計劃目標(biāo)，綜合考慮進(jìn)度、資源和降低成本等目標(biāo)，進(jìn)行網(wǎng)絡(luò)優(yōu)化，確定最優(yōu)的計劃方案。

1．時間—資源優(yōu)化 （1）優(yōu)先安排關(guān)鍵工序所需的資源。 （2）利用非關(guān)鍵工序的時差，錯開各工序的開始時間，拉平資源需要量的高峰。 （3）統(tǒng)籌兼顧工程進(jìn)度的要求和現(xiàn)有資源的限制，往往要經(jīng)過多次綜合平衡，才能得到比較合理的計劃方案。 下面列舉一個拉平資源需要量最高峰的實例。在例5中，若機械加工工人人數(shù)為65人，并假定這些工人可完成這5個工序中的任一個，下面來尋求一個時間—資源最優(yōu)方案，如表12-13所示。408管理運籌學(xué)§2

統(tǒng)籌方法表12-13工序

d f g h i需要人數(shù)

58 22 42 39 26最早開始時間

60 70 80 100 110所需時間

20 18 30 15 25時差

0 47 0 20 0

若上述工序都按最早開始時間安排，那么從第60天至第135天的75天里，所需的機械加工工人人數(shù)如圖12-14所示。409管理運籌學(xué)§2統(tǒng)籌方法

在圖的上半部中，工序代號后的數(shù)字是所需機械加工工人數(shù)，點劃線下面的數(shù)字是非關(guān)鍵工序時差長度。圖的下半部表示從第60天至135天內(nèi)的75天里，所需機械加工工人數(shù)，這樣的圖稱為資源負(fù)荷圖。

圖12-14410管理運籌學(xué)§2統(tǒng)籌方法

同時我們應(yīng)優(yōu)先安排關(guān)鍵工序所需的工人，再利用非關(guān)鍵工序的時差，錯開各工序的開始時間，從而拉平工人需要量的高峰。經(jīng)過調(diào)整，我們讓非關(guān)鍵工序f從第80天開始，工序h從第110天開始。找到了時間—資源優(yōu)化的方案，如圖12-15所示，在不增加工人的情況下保證了工程按期完成。

圖12-15411管理運籌學(xué)§2統(tǒng)籌方法

2．時間—費用優(yōu)化 需要考慮時間與費用的問題：在既定的時間前工程完工的前提下，使得所需的費用最少，或者在不超工程預(yù)算的條件下使工程最早完工。這些是時間—費用優(yōu)化要研究和解決的問題。 直接費用：為了加快工程進(jìn)度，需要增加人力、設(shè)備和工作班次，這需要增加一筆費用，稱為直接費用。 間接費用：由于工程早日完工，減少了管理人員的工資辦公費等費用，稱為間接費用。一般說工序作業(yè)時間越短，直接費用越多，間接費用越少。412管理運籌學(xué)§2統(tǒng)籌方法jj

縮短工序的作業(yè)時間有一定的限度，這個限度稱為工序的最快完成時間。 我們設(shè)完成工序j的正常所需時間為Tj，直接費用為cj，完成工序j的最快完成時間為T'j,直接費用為c'j。這樣我們可以計算出縮短工序j的一天工期所增加的直接費用，用kj表示，稱為直接費用變

c′?cj

Tj?T′

時間—費用優(yōu)化問題可建立兩個線性規(guī)劃模型。 模型一，在既定的時間T完工的前提下，問各工序的完成時間為多少才使因縮短工期而增加的直接費用最少。 設(shè)工序（i,j)的提前完工時間為yij,我們用Tij,T'ij分別表示正常完工時間與最快完工的時間，則有工序（i,j)的實際完工時間為：Tij?yij。我們用cij,c'ij表示用正常完工時間和最快完成時間完成工序所需要的費用，kij為工序（i,j)的直接費用變動率。得到這個問題的線性規(guī)劃模型如下：

minf=ijij

(i,j)s.t.xj?xi≥Tij?yij,對一切?。╥,j）yij≤Tij?T′ij,對一切?。╥,j）xn?x1≤T,xi≥0，yij≥0。413管理運籌學(xué)§2統(tǒng)籌方法

例7．例5所提供的信息都作為本例的信息，另外還給出在裝配過程中各道工序所需正常完工時間與最快完工時間，以及對應(yīng)正常完工時間與最快完工時間的所需的直接費用和每縮短一天工期所需增加的直接費用，如表12-14所示。cij′?cijTij?Tij′414表12-14正常情況下采取措施后縮短一天工期增加的直接費用（費用

工序a(1,2)b(2,7)c(2,3)d(2,4)e(2,5)f(3,7)g(4,6)h(5,7)i(6,7)j(7,8)Tij正常完工時間/天

60 45 10 20 40 18 30 15 25 35cij工序直接費用/元

10000 4500 2800 7000 10000

3600

9000 3750 6250 12000

Tij′最快完 工時間/天

60 30 5 10 35 10 20 10 15 35管 理 運 籌

cij′工序直 接費用/元

10000 6300 4300 11000 12500 5440 12500 5700 9150 12000學(xué)變動率元/天）

kij=

— 120 300 400 500 230 350 400 290 —415管理運籌學(xué)§2統(tǒng)籌方法

該工程要求在150天內(nèi)完工，問每個工序應(yīng)比正常完工時間提前多少天完成，才能使整個工程因縮短工期而增加的直接費用為最少。如果工期要求在140天完工呢？

圖12-16416管理運籌學(xué)§2統(tǒng)籌方法解：網(wǎng)絡(luò)圖如圖12-16所示，根據(jù)此網(wǎng)絡(luò)圖建立數(shù)學(xué)模型。設(shè)此網(wǎng)絡(luò)圖上第i點發(fā)生的時間為xi，工序提前完工的時間為yij。目標(biāo)函數(shù)

minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t.x2?x1≥60?y12x7?x2≥45?y27x3?x2≥10?y23x4?x2≥20?y24x5?x2≥40?y25x7?x3≥18?y37x6?x4≥30?y46x5?x4≥0，虛擬?。?，5）x7?x5≥15?y57x7?x6≥25?y67x8?x7≥35?y78417管理運籌學(xué)§2統(tǒng)籌方法x1=0y12≤0y27≤15y23≤5y24≤10y25≤5y37≤8y46≤10y57≤5y67≤10y78≤0x8≤150xi≥0，yij≥0。（對一切可能的i和j）418管理運籌學(xué)

用“管理運籌學(xué)”軟件進(jìn)行計算，很快得到以下結(jié)果：

f=6400

x1=0,y12=0,y67=10

x2=60,y27=0,y78=0

x3=97,y23=0

x4=80,y24=0

x5=100,y25=0

x6=100,y37=0

x7=115,y46=10

x8=150,y57=0

也就是說我們縮短工序g和工序i的10天工期，我們可以付出最少的直接費用6400元，提前20天即在150天里完成整個工程。419管理運籌學(xué)

如果工期要求在140天里完成，那么我們只要在上述的線性規(guī)劃的模型里把約束條件中的最后一個：

x8≤150，改為x8≤140， 其余一切不變，用“管理運籌學(xué)軟件”運算，得到如下結(jié)果：

f=14900

x1=0,y27=0,y12=0，

x2=60,y23=0,y78=0，

x3=87,y24=10,

x4=70,y25=5,

x5=95,y37=0,

x6=90,y46=10,

x7=105,y57=5,

x8=140,y67=10,

為了使工程在140天里完成，我們至少要付出14900元的直接費用，各工序的開始時間和縮短的工期如解所示。420管理運籌學(xué)

對于例7這樣的問題我們也可以用統(tǒng)籌法予以解決： 若要求我們在150天里完成工程，縮短了正常工期的20天。我們