【正文】 此時(shí)崗位人數(shù)要求是至少 2人。 時(shí)段 職工人數(shù) 時(shí)段 職工人數(shù) 00:00 06:00 2 16:00 18:00 6 06:00 10:00 8 18:00 22:00 5 10: 00 12:00 4 22:00 24:00 3 12:00 16:00 3 第三章 線性規(guī)劃模型 ? 例 310 人力資源合理調(diào)派問(wèn)題 定義變量： 24小時(shí)正點(diǎn)上班的人數(shù)作為變量 X0 : 0:00 上班的職工人數(shù) X1 : 1:00 上班的職工人數(shù) X2 : 2:00 上班的職工人數(shù) …… X22: 22:00 上班的職工人數(shù) X23: 23:00 上班的職工人數(shù) 目標(biāo)函數(shù)： 24小時(shí)正點(diǎn)上班的人數(shù)和為最小 MIN Z = X0+X1+X2+ …… + X22+X23 第三章 線性規(guī)劃模型 例 310 人力資源合理調(diào)派問(wèn)題 約束條件：每一個(gè)時(shí)間段（一小時(shí)）總會(huì)有人在休息，需 要分析哪個(gè)時(shí)間上班的人不在崗位和在崗位上的是哪些時(shí)間上班的人。職工可以在任何正點(diǎn)時(shí)間上班。 每 臺(tái) 機(jī) 床 生 產(chǎn) 率 （ 件 / 日 ） 機(jī) 床 種 類 機(jī) 床 臺(tái) 數(shù) 零 件 B1 零 件 B2 A1 A2 A3 3 2 4 20 35 10 30 45 18 第三章 線性規(guī)劃模型 ? 例 310 人力資源合理調(diào)派問(wèn)題 杭甬高速公路在杭州入口處在 24小時(shí)內(nèi)通過(guò)的數(shù)量是不均勻的，因此，相應(yīng)地，在入口處收費(fèi)的人數(shù)安排也應(yīng)按時(shí)段不同而有所差異。該廠有 A1， A2， A3三種機(jī)床可加工上述兩種零件，每種機(jī)床的臺(tái)數(shù)以及每臺(tái)機(jī)床每個(gè)工作日全部用于加工某一種零部件的最大產(chǎn)量（即生產(chǎn)率：件 /日）如下表所示。 第三章 線性規(guī)劃模型 第三章 線性規(guī)劃模型 問(wèn)題分析： 對(duì)于每一根 ，可有若干種下料方式把它截取成我們所需要的軸，如可以截取 2根 1根 米，合計(jì)用料 ，余料為 。 X2C≤30000 確定目標(biāo)函數(shù)：第五年末資金最大 MAX Z = +++ 第三章 線性規(guī)劃模型 完整的模型為： MAX Z = +++ . X1A+X1D =100000 +X2A+X2C+X2D =0 +X3A+X3B +X3D =0 +X4A+X4D =0 +X4D =0 X2C ≤30000 X3B ≤40000 XiA,XiB,XiC,XiD(i=1,2,3,4,5)≥0 第三章 線性規(guī)劃模型 求解結(jié)果（單位元）： 第一年： X1A=34783, X1D=65217 第二年： X2A=39130, X2C=30000, X2D=0 第三年： X3A=0, X3B=40000, X3D=0 第四年： X4A=45000, X4D=0 第五年： X5D=0 第五年末總資金： Z=143750 第三章 線性規(guī)劃模型 ?例 39: ?合理下料問(wèn)題： 某工廠生產(chǎn)某一型號(hào)的機(jī)床，每臺(tái)機(jī)床上分別需用 、 、 1跟、 2根和 1根，這些軸需用同一種園鋼制作，圓鋼的長(zhǎng)度為 。 第一年： X1A+X1D=100000 第二年：年初資金僅為 D項(xiàng)目第一年的本息。 第三章 線性規(guī)劃模型 第三章 線性規(guī)劃模型 確定變量： 以 XiA,XiB,XiC,XiD(i=1,2,3,4,5)分別表示第 i 年年初給項(xiàng)目 A,B,C,D的投資額。 項(xiàng)目 D：五年內(nèi)每年初可購(gòu)買公債于當(dāng)年末歸還并加利息 6％。 項(xiàng)目 B：從第三年初需投資，到第五年末能回收本利 125％，但規(guī)定最大投資額不超過(guò) 4萬(wàn)元。Y2 ≤1000Y1+X1。 決策變量：每月買進(jìn) Xi (i=1,2,3), 每月賣出 Yi (i=1,2,3)。如買進(jìn)的商品當(dāng)月到貨，但需到下月才能賣出，且規(guī)定“貨到付款”。 確定目標(biāo)函數(shù) ： （新刀具成本＋研磨成本）為最小，即： min Z＝ (X1+X2+X3+X4+X5)+(Y1+Y2+Y3) 第三章 線性規(guī)劃模型 確定約束條件： 由于研磨的刀具第三天才能使用，因此， X1=120 ； X2=85 第三天開(kāi)始，每天使用新的和研磨送回的刀具： X3+Y1=160, X4+Y2=145, X5+Y3=300 在頭三天送去研磨的刀具應(yīng)滿足： Y1≤120, Y2≤85+(120Y1)。第五天后應(yīng)全部換新，每期開(kāi)始時(shí)沒(méi)有任何刀具，問(wèn)這個(gè)車間需要多少刀具才能應(yīng)付需要，而成本又最低？試建立線性規(guī)劃模型。 最優(yōu)解的極點(diǎn)變化？ bi 的變化與影子價(jià)格的關(guān)系？ E2’ E1’ 第三章 線性規(guī)劃模型 ? 敏感性分析－－ 增加一個(gè)新產(chǎn)品 (教材 P56) G T 總量 影子價(jià)格 V 配料 1 2 40 0 2 蒸餾 2 2 40 10 2 包裝 1 1 25 10 2 獲利 30 20 50 代價(jià) 0 20 20 40 新產(chǎn)品 V投產(chǎn)帶來(lái)的收益值 10 ? 對(duì)偶問(wèn)題與原始問(wèn)題的關(guān)系 第三章 線性規(guī)劃模型 目標(biāo) 極大化問(wèn)題 Cj（ max Z） 極小化問(wèn)題 bi（ min W） 目標(biāo) 變 量 n xj≥0 ?—— ? ?aTijyi≥cj 約 束 n xj無(wú)約束 ?—— ? ?aTijyi=cj xj≤0 ?—— ? ?aTijyi≤cj 約 束 m ?aijxj≥bi ?—— ? yi≤0 變 量 m ?aijxj=bi ?—— ? yi無(wú)約束 ?aijxj≤bi ?—— ? yi≥0 作業(yè) 1: 對(duì)偶問(wèn)題求解 運(yùn)用對(duì)偶原理求以下原問(wèn)題的最優(yōu)解： 目標(biāo)函數(shù)： MIN Z = 2X1+3X2+X3 ： 3X1 X2+ X3≥1 X1+2X23X3≥2 X1,X2,X3≥0 寫出對(duì)偶問(wèn)題： 目標(biāo)函數(shù)： MAX W = Y1+2Y2 : 3Y1+ Y2≤2 Y1+2Y2≤3 Y1 3Y2≤1 Y1,Y2≥0 (0,3/2) 0 1 1 1 Y1 Y2 (2/3,0) 3Y1+Y2=1 Y1 3Y2=1 Y1+2Y2=3 1 (1/ 7,11/ 7) Y1+2Y2=23/7 求解對(duì)偶問(wèn)題最優(yōu)解： Y*1=1/7,Y*2=11/7,Y*3=0,Y*4=0,Y*5= 39/7 根據(jù)互補(bǔ)松弛定理得