【正文】 200 300 300 200 100 D 圖 21 規(guī)劃與決策 0 100 200 300 300 200 100 D B(50,250) Z= 50x1+100x2 圖 22 時(shí)序與路徑規(guī)劃 ? 討論各種時(shí)序規(guī)劃問題 ? 介紹時(shí)序規(guī)劃原則 ? 分派問題 ? 運(yùn)輸問題 ? 網(wǎng)絡(luò)的最短路徑 ? 網(wǎng)絡(luò)的最大流 時(shí)序規(guī)劃問題 A B E F D C 機(jī)器 機(jī)器 D E F C A B 等待處理的一批工作 按最優(yōu)次序排隊(duì) 一臺(tái)機(jī)器工作的時(shí)序規(guī)劃 時(shí)序規(guī)劃問題 原則： (1) 最緊迫的優(yōu)先 實(shí)例 1： 6種部件作為一批等待一臺(tái)機(jī)器加工。 （ 2）目標(biāo)函數(shù)： MAX 50x1+100x2 （ 3）約束條件： subject to (.): x1+x2 ≤300 2x1+x2 ≤400 x2 ≤250 x1,x2 ≥0 規(guī)劃與決策 線性規(guī)劃模型： max 50x1+100x2 . x1+x2 ≤300 2x1+x2 ≤400 x2 ≤250 x1,x2 ≥0 規(guī)劃與決策 線性規(guī)劃模型的一般形式 max c1x1+c2x2+ …+ c n xn s. t. a11x1 + …+ a 1nx n≤ (≥,=) b1 a21x1 + …+ a 2nx n≤ (≥,=) b2 … am1x1 + …+ a mnx n≤ (≥,=) bm xij ≥ 0 i = 1, …,n, j =1, …,m 規(guī)劃與決策 線性規(guī)劃應(yīng)用領(lǐng)域 ： ?合理利用板、線材問題； ?配料問題； ?投資問題； ?生產(chǎn)計(jì)劃問題、勞動(dòng)力安排問題； ?運(yùn)輸問題、電子商務(wù)配送問題； ?企業(yè)決策問題；企業(yè)或商業(yè)競(jìng)爭(zhēng)對(duì)策問題等。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品都需要經(jīng)過鑄造、機(jī)加工和裝配三個(gè)車間。 第 2步： 在安排的時(shí)序中找到 1項(xiàng)延誤的工作。 工 作 G B C A E F D H 到期時(shí)間 2 7 8 13 14 20 30 36 開始加工時(shí)間 0 2 7 10 12 16 23 31 加工時(shí)間 2 5 3 2 4 7 8 3 完成加工時(shí)間 2 7 10 12 16 23 31 34 延誤工作 * * * * 第 2步： 在上述時(shí)序中，第 1項(xiàng)被延誤的工作是 C。 步驟 4： 不必再考慮這一工作，回到步驟