運(yùn)籌學(xué)應(yīng)用實(shí)例分析

1、如形餐埔第一部分 小型案例分析建模與求解案例1.雜糧銷售問題一貿(mào)易公司專門經(jīng)營某種雜糧的批發(fā)業(yè)務(wù)，公司現(xiàn)有庫容5011擔(dān)的倉庫。一月一日，公司擁有庫存1000擔(dān)雜糧，并有 資金20000元。估計(jì)第一季度雜糧價(jià)格如下所示：一月份，進(jìn)貨價(jià)2.85元，出貨價(jià)3.10元；二月份，進(jìn)貨價(jià)3.05元，出貨 價(jià)3.25元；三月份，進(jìn)貨價(jià)2.90元，出貨價(jià)2.95元；如買進(jìn)的雜糧當(dāng)月到貨，需到下月才能賣出，且規(guī)定“貨到付款”。公 司希望本季度末庫存為2000擔(dān)，問應(yīng)采取什么樣的買進(jìn)與賣出的策略使三個(gè)月總的獲利最大，每個(gè)月考慮先賣后買？ 解：設(shè)第i月出貨X0擔(dān)，進(jìn)貨擔(dān)，1=1，2, 3；可建立數(shù)學(xué)模型如下：目標(biāo)

2、函數(shù)：Max z = 3.10*x + 3.25*x + 2.95*x -2.85*x -3.05*x -2.90*x102030112131約束條件:工 1000工 1000 -工+工 TOC o 1-5 h z 201011工 1000 -工+工-工 +工30101120211000 -工 + 工 50111000 -工 + 工-工 + 工 5011丁 200011 202.85工 20000 + 3.10工3.05工 20000 + 3.10工 + 3.25工-2.85工2.90工 XIX2X3X5X6DirectionR H.S.Maximize3.10-2.853 一方2.95-29

3、0ClI1000C21-11=1帥C31-I1-11-1000C4-11=4M1C5-111I=MlC6-3.102.85=20000C7-3.102.E5-3.253.05=20000cs-3.10混S-1253.05-2.952 90=20000Lowtrlioujid000002000I IpperBound1000SOI501 150 nsoil2000VariablcTTcIntegerInlcgcrliUegerIntegerhtcgciIntegerCombined Report for案例1雜糧銷售問題12:4244SundayMay312009DecisionVariable

4、Solution ValueUnit Cost or Profit c(j)Total ContributionReducedCostBasisStatusAllowable Mm, c(j)Allowable Max. c(j)1XI1,000WOO3.10003,100,000。0basic2.8500M2X25,011X1000-2.8500-14,28135000basic-3.1000M3X35,011.0000psoo16,285.75000basic2.9500M4X40-3.05000-0.1000at bound-M-2.95005X502,950000basic03.050

5、06X623(M)0WOO2.9000-2,9000at bound-MMObitctiveFunction(Max.) =-695,5998ConslrainlLift Hand SideDirvtionRight Hand SideSlack or SurplusShadow PriceAllowableMim RHSAllowableMax, RHS1Cl1,000WOO.=1,000,000000,250001,000.00002C21,000.0000=,000,0000003000-4,011.00001,000,00003C31,000.0000=1,000.000002.950

6、01,000.00006,011.00004C44,011.0000=4,011.000000.4000-L000.00O04,011.00005C5-L000.000O=4,011 00005,0】 LOO。000,0000M6C611,181.3500=20,000.00008318.6500011JS1 3500M7C7-5 J 04.4000-20,000.00002 5J 04.40000-5,104 4000M8C8695,5998=20,000,000019304.40000695.5996M所以最優(yōu)策略為：1月份賣出1000擔(dān)，進(jìn)貨5011擔(dān)；2月份賣出5011擔(dān)，不進(jìn)貨；3月

7、份不出貨，進(jìn)貨2000擔(dān)。此時(shí)，資金余額為20000-695.60=19304.40 （元），存貨為2000擔(dān)。案例2.生產(chǎn)計(jì)劃問題某廠生產(chǎn)四種產(chǎn)品。每種產(chǎn)品要經(jīng)過A，B兩道工序加工。設(shè)該廠有兩種規(guī)格的設(shè)備能完成A工序，以A1，A2表示； 有三種規(guī)格的設(shè)備能完成B工序，以B1，B2，B3表示。產(chǎn)品D可在A，B任何一種規(guī)格的設(shè)備上加工。產(chǎn)品E可在任 何規(guī)格的A設(shè)備上加工，但完成B工序時(shí)只能在B1設(shè)備上加工。產(chǎn)品F可在A2及B2，B3上加工。產(chǎn)品G可在任何一 種規(guī)格的A設(shè)備上加工，但完成B工序時(shí)只能在B1，B2設(shè)備上加工。巳知生產(chǎn)單件產(chǎn)品的設(shè)備工時(shí)，原材料費(fèi)，及產(chǎn)品 單價(jià)，各種設(shè)備有效臺時(shí)如下表，

8、要求安排最優(yōu)的生產(chǎn)計(jì)劃，使該廠利潤最大？設(shè) 設(shè)產(chǎn)品設(shè)備有效臺時(shí)1234A151066011A27912810000B168104000B241187000B37104000原料費(fèi)（元/件）0.250.350.500.4單價(jià)（元/件）1.252.002.802.4解：設(shè)Xia(b)j為i產(chǎn)品在a(b)j設(shè)備上的加工數(shù)量,i=1,2,3,4;j=1,2,3,得變量列表如下:設(shè)備產(chǎn)品設(shè)備有效臺時(shí)Ta(b)j1234A1X1a1X2a1XX4U6011A2X1a2Xa2X3a2X4a210000B1X1b1X2b1皿X4b14000B2X1b2X3b2X3b2X4b27000B3X1b3X3b3X3b

9、3X4b34000原料費(fèi)Ci(元/件) 單價(jià)Pi(元/件)0.251.250.352.000.502.800.42.4其中，令 X3a X3b X3b2, X3b3, X4b3=0可建立數(shù)學(xué)模型如下：目標(biāo)函數(shù)：Max z = X X *( Pi - Ci)i=1 J =1= 1.00*(X1a1+X1a2)+1.65*(X2a1+X2a2)+2.30* X3a2+2.00*( X4a1+X4a2) 約束條件：i = 1,2,3,4J =i = 1,2,3,4J = 1,2J = 1,2,3=X3b3 = X4b3 = 0i = 1,2,3,4; J = 1,2i = 1,2,3,4; j =

10、1,2，3j=1j=1Wx T = TaJi=1X X T = 0且為整數(shù)X.b. = 0且為整數(shù)利用 WinSQB 求解(X1X4，X5X8,X9X12,X13X17,X18X20分別表示各行變量):案例2生產(chǎn)計(jì)劃問題VariflNeXIX2X3X4XSX6X7XSX9XIOXIKC2X13XAXI5X16X17XIKX20Direcimfl R. El *IW.652.M2 .(H)I.CfiI.fi5?.加Cl11-1-1-1IIC2L1-1-I-10C311-1-1-1uC4I1-L 140C55ID6=6011C679128c=ODOOC76810=4W0CHJ11&70003-Id

11、-=4MI0Olli1IIni10C121DCl 30CI410liwcTtkiLmiLl00000(10Q000D000Q00D0Upper BoundMMMMMWMMMMMMMMJutegerMghi殍 cinkrli ii 01nlcrIl虹埋IT tllcm-llitCLCf【血啊bilegcrhllcgclInieuTiik；r【1就理hileLIniuMnteetCombined Report for案例2生產(chǎn)計(jì)劃問題14:22:292001-26 14:22:29 F午2009-4-26 14 22:2? F午2009-4-26 14 22:29 F 午2009-26 14:22

12、:29 下午DccisitmiVairiablcSoluiio)ValueUnit Cost or Profit dj)TotalC-onuibutioiiReduced CostBasisStains1XIQ1.000000-basic2X277.00001 6500127.050(1.650()ill brtuiiid3X?02-300000basic4X4873 W002 00001.746.00000-basic5X501.00(10(1t)it bouM6X6423.00001.6500697.95000basic7XT400 00002JOOO920.0000-0bssic8XK2

13、.00004.0UO00basic9X9000-0.2375Mlbuund10XI。5fl0t000000basic1X】10000bask2XI2000-0 M25ill bound3XI30000il hound14XI40000ba成15X15&00-04500航 bound16XI6875.0000000bisic17XI70000 6100at bound18XIS000&basic19XI9400.0000IF00basic20X200000basicObjectiveFuncliaii(Max )=3,495.0000ConsUaiinlLeft HandSideDireclio

14、nRight HandSideShek r S unil usSliadnwPrice1Cl0001.00001C200&-1.65003a000230004C4(0t)-2.-OOOIJ5C56,U0S.0CKJ0=6,() IL .00003.CKJ0006C68 應(yīng) 3IWM)o10,000 OQ00L377 ftOOft07C74,0(X).00110()0.20628CB7,000,0000=7,000.00000025009C94hQQO.0(M)()4.000.000000,2300()CIO00()011Cll0002.300012C120001.650013CL3000-1.

15、6500MCU0002.on(xi綜上，最優(yōu)生產(chǎn)計(jì)劃如下:設(shè)備產(chǎn)品1234A177873A24234002B1500B2875B3400目標(biāo)函數(shù) Max z =3495，即最大利潤為3495案例3.報(bào)刊征訂、推廣費(fèi)用的節(jié)省問題解：該問題可以看成是求費(fèi)用最小的產(chǎn)銷平衡運(yùn)輸問題，日本香港特別行政區(qū)韓國產(chǎn)量中文書刊出口部10.2072015000深圳分公司12.504147500上海分公司687.57500銷量15000100005000利用WinSQB求解From ToDestinatkm 1Destination 2Destination 3SupplySource 110.2072015000

16、Source 212,504147500Source 3687.575001 Jejnand15000100005000得最優(yōu)分配方案為:(M-26-2009IromIdShipmentUnit CostTotal CostReduced Cost1Source Ueslinatim 11250010 2012750002Sou 心 1Destination 2250071750003Source 2Destination 2750043000004Source 3Desl ination L250061500()05Source 3Desiitiation 350007,503750(101

17、otalObicciivcPimclionValue -227500即最優(yōu)任務(wù)分配如下:日本香港特別行政區(qū)韓國中文書刊出口部125002500深圳分公司7500上海分公司25005000采用此方案費(fèi)用最小，為227500 （元）。案例4.供電部門職工交通安排問題我們把通勤費(fèi)作為優(yōu)化的目標(biāo)。ai (i=1, 2, .18)表示住地的職工人數(shù)，用bj (j=1, 2, .8)表示工作地點(diǎn)的定員，cij (i=1,2, .18; j=1，2, .8)表示每個(gè)職工從住地到各工作地點(diǎn)的月通勤費(fèi)(單位：元)，有關(guān)數(shù)據(jù)列表如下表，試建立此問題的 數(shù)學(xué)模型并求解。C、 -j_工作地點(diǎn)12345678ai112

18、13.5208.328.328.3213.528.32323.128.3211.443.123.123.128.323.1231305.2011.44003.125.203.129409.3612.487.287.287.289.367.28255.20010.405.205.205.2010.400963.12011.443.123.123.128.323.12677.289.3612.488.328.328.329.364.16784.169.364.16004.169.364.16197.289.3612.484.164.164.169.364.161108.325.2013.008.3

19、28.328.3213.523.1281112.4814.569.365.205.209.3614.569.361123.125.208.320008.3205135.2010.4016.648.848.848.8410.408.846143.125.2011.443.123.1208.3204153.128.3211.440008.3202163.125.208.320008.3204173.128.3211.443.123.1208.3204187.289.3612.484.164.164.169.364.161b.36991956155104j解：根據(jù)題意，以員工住地為產(chǎn)地，工作地點(diǎn)為銷

20、地，將問題轉(zhuǎn)化為求月總通勤費(fèi)最小的運(yùn)輸方案利用WinSQB建立模型求解：案例4供電部口職工交通安排問題:Minimization (Transportation Problem)From ToDesttnalDon IDes 血 ation 2kslinaticni 3Dehlinalion 4Destination SDestination 6Deslinalion D 削 nalKW $SupplySrce 11211520$.328.3?*.3205?S.32aSource 23.12&.3W11.443.121121128.32U231蝦由況305.2031.44(10U25.20J

21、124Source 4093612.487.2S7.2S72B9367.282Source 55.20010.405.205.2052010.400JSflurte 63.120H 443.12112112血M26Source 7936I2.4SS.32832329.36416?jSource K1169364.16004169.364 16iiSluice 97.2R93632.484.164.164.169.36416iSource |0S.325.2013.如幻?832&羽】3&5.12g灑wl 1I2.4S14569365.205.209一3614.56936ijSflurce 123

22、.125.20KS20Ufl&.3205Stnirce 135.2010.4016.6404&848.S4如制Source 14M25.2011.443.121120S320和功叫153.12N.211440Q08.技02Source 163.125.20KS2000&.3?04Snurce 173.12&.3211.443.121120統(tǒng)(14Sflurci； 1 &7.289362.48 1X8 + X9 + X10 187*5hi為i隊(duì)員的身高i=1ZXi*Pi 8.4*5Pi為i隊(duì)員的技術(shù)分i=1Xi = 0或 1； i = 1,2,3,4,5,6,7,8,9,10利用WinSQB建立

23、模型求解：案例5籃球隊(duì)員選拔問題Variable XIX2X3X4X5X6X7XSX9X10DirectionR. H S.Minimize241 1260(J3500250018002200190024003200ClI1I111111I02I1I1=1C311I=2C4IL=9%C6K.29R.49.58SI7.S8.29.2=421 DwcrHound000000000UpperBoundI1I111111IVariubklypeBinaryBinaryBinaryBinaryBinaryBinaryBinar| BinaryBiniiryBinary綜上，應(yīng)該選拔第2, 6, 7, 8

24、, 10號隊(duì)員為正式隊(duì)員，共需支付月薪12 100 （元）Combined Report for案例5籃球隊(duì)員選拔問題15:12:412009-4-2618:12:41 下午2009-4-2618:12:41 下午2009-4-26 18:12:41 下午200M-26 18:12:41 下午DecisionVariableSolutionValueUnit Cost or Profit ej)Fotal ContributicnReductdCostBasisStatus1XI0辜11州902,411.0000at hound2X21.00003,000.00003,0000000basic

25、-tX30W0OT002,600.0000at bound4X403,500.00000300.0000at hoiuid5X502,300.000002,500.0000at bound6X61.00001,800.1X)00LBOO.OOOO0basic7XT1.00002,200.00002,200.00000basic8X81.00001,900.0000L900.00000basic9X901400.000002400.0000dt buimd10 xioI .oooo3.200.00003,200.00000basicObjectiveFunction(MinJ =12,100,0

26、000ConstraintLift Hand SideDirectjcMiRight Hand SideSlack or SurplusShadow Price1Cl5,00005.0(X)G0J,2QO.OOnO2C21.0000=1.0000003C32,0000=2.0QAQ004C40=42 0000U.1UOO0案例6.工程項(xiàng)目選擇問題某承包企業(yè)在同一時(shí)期內(nèi)有八項(xiàng)工程可供選擇投標(biāo)。其中有五項(xiàng)住宅工程，三項(xiàng)工業(yè)車間。由于這些工程要求同時(shí)施工， 而企業(yè)又沒有能力同時(shí)承擔(dān)，企業(yè)應(yīng)根據(jù)自身的能力，分析這兩類工程的盈利水平，作出正確的投標(biāo)方案。有關(guān)數(shù)據(jù)見下表:表1可供選擇投際工程的有關(guān)數(shù)據(jù)統(tǒng)計(jì)

27、工程類型預(yù)期利潤/元抹灰量/m2混凝土量/ m3砌筑量/ m3住宅每項(xiàng)5001125 0002804 200工業(yè)車間每項(xiàng)80 0004808801 800企業(yè)尚有能力108 0003 68013 800試建立此問題的數(shù)學(xué)模型。解：設(shè)承包商承包X1項(xiàng)住宅工程，X2項(xiàng)工業(yè)車間工程可獲利最高，依題意可建立如下整數(shù)模型:目標(biāo)是獲利最高，故得目標(biāo)函數(shù)為Max z = 50011X1 + 80000X2根據(jù)企業(yè)工程量能力限制與項(xiàng)目本身特性，有約束：產(chǎn) 25000 X 1 + 480 X 2 108000280X + 880X 3680 1 24200X + 1800X 13800 12X5,X XIX2D

28、irectionRJI S,Maximize500 180000Cl25000480=108000C2280S80=3680C342001800=138()0LawerBonnd00UpperBound53VariableTypcIntegerIntegerCombined R印ort for案例6工程項(xiàng)我擇疏1到25524-2618:42:547 午204-261W:54Tt2W4-2618:42:54 Tf20M4-26 8:42:54 WDtcisioflVariableValueUnit Costar Prefit c(j)Tftial ContributionRetailCosiBa

29、sisSlamsAllowableAlleleMatcfj)1Xloom辿LOTO12.00000basic0186確，測）2X23.0000郵0加即2400.00000basic21,4312900MObjecliveFunction(Mm) -3022.0000恤tr血1Left Hmd&也Diredan岫t Hand ZdeSI眥 or SurplusShiadow PticeAllowableMin RHSAllmbleMai RHS1Cl傾頗-皿即順M5&豌顧051440.0000M2C2UDOW=3,68 MO做順0頃岫M3C3底觥知0缶13,岫.傾011.90745,0.0000

30、210.00M綜上，承包商對2項(xiàng)住宅工程，3項(xiàng)車間工程進(jìn)行投標(biāo)，可獲利最大，目標(biāo)函數(shù)Max z=340022元。各類人員承擔(dān)的丁作量、丁資及所占比例如下表:變量承擔(dān)的教學(xué)工作量所占教師的百分比年工資本科生研究生最大最小x1003,000美元口26學(xué)時(shí)/周07%3,000 x312078,000 x4901513,000 x590515,000 x _660217,000 x73012,000 x803學(xué)時(shí)/周1%30,000 x94,000y1632113,000y2631415,000y3332317,000口0322,000y03230,0005由校方確定的各級決策目標(biāo)為:P1要求教師有一

31、定的學(xué)術(shù)水平。即：要求75%的教師是專職的。要求擔(dān)任本科生教學(xué)工作的教師中，至少有40%的 人具有博士學(xué)位。要求擔(dān)任研究生教學(xué)工作的教師中，至少有75%的人具有博士學(xué)位。P2要求各類人員增加工資的總額不得超過176, 000美元，其中x1、x2和x9增加的工資數(shù)為其原工資基數(shù)的6%，而 其他人員為8%。P3要求能完成學(xué)校的各項(xiàng)教學(xué)工作。即學(xué)校計(jì)劃招收本科生1，820名，研究生100名。要求為本科生每周開課不低于910學(xué)時(shí)。要求為研究生每周開課不低于100學(xué)時(shí)。要求本科生教師與學(xué)生人數(shù)比為1： 20，即為本科生上課的教師數(shù)不超過1820/20=91人。要求研究生教師與學(xué)生人數(shù)比為1： 10，即為

32、研究生上課的教師數(shù)不超過100/10=10人。P4設(shè)教師總數(shù)P4設(shè)教師總數(shù)T=要求各類教學(xué)人員有適當(dāng)比例，如上表。i=1i =1P5要求教師與行政管理職工之比不超過4： 1。P6要求教師與助研x1之比不超過5： 1。P7設(shè)所有人員總的年工資基數(shù)為1，850，000美元，要求其盡可能小。 試建立其目標(biāo)規(guī)劃的數(shù)學(xué)模型。解：依題意，建立目標(biāo)規(guī)劃模型： TOC o 1-5 h z HYPERLINK l bookmark113 o Current Document Min z = P (d - + d + + d - + d -) + P (d +) + P (d - + d - + d + + d

33、+) 111232435678+ P (d + d + d + +d + d + d + d -+ d -+ d -+ d -+ d + d -) HYPERLINK l bookmark116 o Current Document 91011121314151617181920+ P (d + ) + P (d + ) + P (d + )21622723(X1 + X2 + X7 + y4)/T + d- d： = 0.25T (X1 + X2 + X7 + y4)/T + d- d： = 0.25(y1 + y2 + y3)/(X2 + X3 + X4 + X5 + X6 + X7 +

34、y1 + y2 + y3) + d- - d+ = 0.40 (y1 + y2 + y3 + y4 + y5)/(y1 + y2 + y3 + y4 + y5 + X8) + dd+ = 0.75 (300(*X1+300(*X2+400(*X9尹6%+(cXi+cy)*8%+d-d+=176000.Ci為各工資基數(shù).44i=3i=1 XiPi + X yiPi + d- - d+ = 910Pi為各類教師承擔(dān)的本科 教學(xué)學(xué)時(shí)i=2i=1X8*P + yiPi + d- - d+ = 100Pi為各類教師承擔(dān)的研究 生教學(xué)學(xué)時(shí)i=1 Xi+ yi + d- d+= 91i=2i=1X8 + y

35、i + d- - d+ = 10i=1X2/( Xi + yi) + d- - d+ = 0.07i =1i =1X3/( Xi + yi) + d- - d + = 0.0710i=1i=1X4/( Xi + yi) + d- - d + = 0.1511i=1i=1X5/( Xi + yi) + d- - d + = 0.0512s.t.i=1is.t.X6/( Xi+ yi) + d- - d + = 0.0213i=1i=1X7/( Xi + yi) + d- - d + = 0.0114i=1i=1X 8/( Xi + yi) + d- - d + = 0.0115i=1y1/( X

36、i +i=1y1/( Xi +i =1i =1y 2/( Xi+ yi) + d -17i =1i =1y 3/( Xi+ yi) + d -18i=1i=1y4/( Xi+ yi) + di =1i =1+ d1-6 - d + = 0.21+16一 d +17一 d +18一 d +19=0.14=0.23= 0.02y5/( Xi+ yi) + d- - d+ = 0.02 TOC o 1-5 h z i=1i=1( Xi + yi)/X9 + d- + d+ = 4i=1i=1( Xi+ yi)/X1 + d一 + d + = 5i=1i=1Ci為各人員的年工資 Xi Ci + yiC

37、i + d- + d+ = Ci為各人員的年工資i=1i=1Xi, yi為正整數(shù)案例8.電纜工程投資資金優(yōu)化問題有一項(xiàng)工程，要埋設(shè)電纜將中央控制室與15個(gè)控制點(diǎn)相連通。圖中的各線段標(biāo)出了允許挖電纜溝的地點(diǎn)和距離（單位: 百米）。若電纜線每米10元，挖電纜溝（深1米，寬0.6米）土方每立方米3元，其它材料和施工費(fèi)用每米5元，則該工程 預(yù)算最少需多少元？解：該問題等價(jià)于求網(wǎng)絡(luò)最小支撐樹，利用WinSQB建立模型求解:4-24-2009From N odeConnect ToDistan ce/Cos tFrom N odeConnect T oD istance/Cos：t1：NodelGNode

38、239Model GNodel 042Node4Node3210Nodel 0Nodel 143NodelNode4711Nodel 6Nodel 244Node3NodeS512Nodel 2Model 355Node3NodeS413Nodel 3Nodel 45Node9Node?414Nodel 2Model 527Node?Node8315Node3Nodel 658Model 0Node95TotalMinimalConnectedD istanceor Cost62網(wǎng)絡(luò)最小支撐樹為上圖加粗線路，所以按照加粗路線挖電纜溝能使工程預(yù)算最小，路線總長62米，故最小預(yù)算為：62*1*0.

39、6*3+62*（10+5）=1041.6 （元）x ,x ,y ,y ,，yxy xy , y x巳知有六臺機(jī)床126，六個(gè)零件/ 12。；機(jī)床1可加工零件1 ；2可加工零件/ 1七；3可加y , y , y xy xy , y , y xy , y , y工零件/ 1 2七；4可加工零件2 ； 5可加工零件/ 2七4 ； 6可加工零件/ 2 5 6 ；現(xiàn)在要求制定一個(gè)加工方 案，使一臺機(jī)床只加工一個(gè)零件，一個(gè)零件只在一臺機(jī)床上加工，要求盡可能多地安排零件加工，試把這個(gè)問題化為求網(wǎng)絡(luò) 最大流問題，求出能滿足上述條件的加工方案。解：則盡多安排加工的方案等價(jià)于求網(wǎng)絡(luò)取得最大流時(shí)的路徑。利用WinS

40、QB建立模型求解如下（點(diǎn)114分別表示點(diǎn)s，XE，yy6, t）：Maximal Flow Problem案例9零件加工安排問題ram JoNodelNode 衛(wèi)Node4Node 5NodefiNode?MndeKNodeSNodE NndeNode 12N仙13Node 4NNel11lL11IN展蜀11NrKie41111Ndc611111I1N屆91101Node 1 11Nkide 121Models1NkEE 40426-2009PramToEel FlowFromToNn Slowrtj-27-2(1091ramToMel FlowliwnTn附 FlowNodelNode。19

41、gll11Nude INodel19Node6Nodel12Node】No(k4110燮？NodeB1?NMHNodM110Node?Nodel 213NodeNodeS1IIgK傾1413N血1NudeiIINodesN(del414NodeNcdcCi1ilModel4或4NodelNikH112NockSNckJcH15N妣Nude?113NoiklONodd4NodHNode?1BNodeIONodel J16Nk：2NodeS114Nuik1116Nodr2NodeS14NodellN odcl 417NmWNock 10115Node 13ndtl417Node4Nodcltf15

42、Nik1l12Model 41sNwk5No岫18Node?N(dc91Nd rinwFram蜒1qNodcH5如Nd l-lowFromModelr&NlkIcM5可以得到兩種結(jié)果（如上），綜上，最佳加工方案為：Xi加工yi； X3加工y3； X4加工y2； X加工y4； X加工ys或y6共5個(gè)零件。下面是某公司房屋施工工程作業(yè)明細(xì)表，請繪制網(wǎng)絡(luò)圖，并確定關(guān)鍵路線。工序工序內(nèi)容緊前工序完成 時(shí)間工序工序內(nèi)容緊前工序完成 時(shí)間a破土挖槽，澆墊層4l安裝廚房設(shè)備k1b澆混凝土基a2m安裝預(yù)制的衛(wèi)生設(shè)備k2c安裝構(gòu)架及屋面b4n完成細(xì)木工活k3d砌磚c6o完成屋頂并罩面油漆d2e安裝排水管b1p安

43、裝天溝及落水管o1f澆地下室地坪e2q安裝防暴雨水管b1g敷設(shè)主管道e3r地板打磨及上光漆n ，s2h敷設(shè)主干電路c2s油漆l，m3i安裝空調(diào)設(shè)備c，f4t完成電器作業(yè)s1j安裝墻板及裝飾板g，h，i10u最后平整p，q2k鋪設(shè)預(yù)制地板j3v鋪便道及綠化u5解：依題意，利用WinSQB建立模型求解：案例10房屋施工網(wǎng)籍計(jì)劃問題Activity MumberActivity NameImiTicdiate Predecessor (list tiiimber/name separated bvNormal TimeA42B123C244D3651：2161527G53SH3293,641()J7

44、,810I IK10312L1 II3M1 I214Z1 I315O4216P15I1 7Q211 8RI4J921 9s12J3320119121U6J7222V215AcHvity Analysis for案例10房屋施工網(wǎng)絡(luò)計(jì)劃問題04-26-300922:36:22Activity NameOn CriticalPathActivity TiineEarliestStartEarliestFinishLatent StartLatestFiniahShek (LS-ES)1AY.s4040402BYes2464603CYei461061004D1W6101616226SEnd67892

45、6Fno279262B197Gno371091228HYea21012。120g1no4101428技1810JYes10122212220iKYei322252225012.no125262627113MYes225272527014Nno3252827302IS0HO216182224616Pno1181924256.?Qno67242518IKRYc!230323032019SYes327302730020nHO21921252T622VDO5212(527326ProjectCompletionTime32weeksNumber ofCriticalPath(

46、5)1網(wǎng)絡(luò)圖如下:Project:案例10房屋施工網(wǎng)絡(luò)計(jì)劃問骸(Detcjministic Acrivih Time)Project Completicui Time = 32 weeks所以關(guān)鍵線路為：A B C H JK一M Sk R第二部分：案例設(shè)計(jì)基于0-1整數(shù)規(guī)劃的公務(wù)員招聘指派問題背景：我國公務(wù)員制度已實(shí)施多年，1993年10月1日頒布施行的國家公務(wù)員暫行條例規(guī)定：“國家行政 機(jī)關(guān)錄用擔(dān)任主任科員以下的非領(lǐng)導(dǎo)職務(wù)的國家公務(wù)員，采用公開考試、嚴(yán)格考核的辦法，按照德才兼?zhèn)?的標(biāo)準(zhǔn)擇優(yōu)錄用”。目前，我國招聘公務(wù)員的程序一般分三步進(jìn)行：公開考試（筆試）、面試考核、擇優(yōu)錄取。 如何對公務(wù)員選

47、撥中的各方面能力進(jìn)行定量化使人才的錄用更加理性化越來越受關(guān)注。同時(shí)，針對公務(wù)員 選舉的最優(yōu)方案建立的數(shù)學(xué)模型和運(yùn)用的方法對進(jìn)一步改進(jìn)我國公務(wù)員招聘的運(yùn)行程序和考核指標(biāo)越發(fā)具 有很強(qiáng)的實(shí)用價(jià)值和參考意義。關(guān)鍵詞：公務(wù)員招聘整數(shù)規(guī)劃指派問題一、問題的提出現(xiàn)有某市直屬單位因工作需要，擬向社會公開招聘8名公務(wù)員，具體的招聘辦法和程序如下：（一）公開考試，根據(jù)考試總分的高低排序按1:2的比例（共16人）選擇進(jìn)入第二階段的面試考核。（二）面試考核：面試考核主要考核應(yīng)聘人員的知識面、對問題的理解能力、應(yīng)變能力、表達(dá)能力等綜合 素質(zhì)。按照一定的標(biāo)準(zhǔn)，面試專家組對每個(gè)應(yīng)聘人員的各個(gè)方面都給出一個(gè)等級評分，從高到

48、低分成A/B/C/D 四個(gè)等級，具體結(jié)果見表1所示。（三）由招聘領(lǐng)導(dǎo)小組綜合專家組的意見、筆初試成績以及各用人部門需求確定錄用名單，并分配到各用人 部門。該單位擬將錄用的8名公務(wù)員安排到所屬的7個(gè)部門，并且要求每個(gè)部門至少安排一名公務(wù)員。這7 個(gè)部門按工作性質(zhì)可分為四類：（1）行政管理、（2）技術(shù)管理、（3）行政執(zhí)法、（4）公共事業(yè)。見表2所示。招聘領(lǐng)導(dǎo)小組在確定錄用名單的過程中，本著公平、公開的原則，同時(shí)考慮錄用人員的合理分配和使 用，有利于發(fā)揮個(gè)人的特長和能力。招聘領(lǐng)導(dǎo)小組將7個(gè)用人單位的基本情況（包括福利待遇、工作條件、 勞動強(qiáng)度、晉升機(jī)會和學(xué)習(xí)深造機(jī)會等）和四類工作對聘用公務(wù)員的具體條

49、件的希望達(dá)到的要求都向所有 應(yīng)聘人員公布（見表2）。每一位參加面試人員都可以申報(bào)兩個(gè)自己的工作類別志愿（見表1）?，F(xiàn)在在已知各應(yīng)聘人員面試成績、專家測評和用人單位需求的的情況下，試根據(jù)以下要求探究如何選出 適合公務(wù)員需求的人員,指派到合適的部門：（1）如果不考慮應(yīng)聘人員的意愿，擇優(yōu)按需錄用，試幫助招聘領(lǐng)導(dǎo)小組設(shè)計(jì)一種錄用分配方案；（2）在考慮應(yīng)聘人員意愿和用人部門的希望要求的情況下，請你幫助招聘領(lǐng)導(dǎo)小組設(shè)計(jì)一種分配方案;（3）你的方法對于一般情況，即N個(gè)應(yīng)聘人員M個(gè)用人單位時(shí)，是否可行？表1：招聘公務(wù)員筆試成績，專家面試評分及個(gè)人志愿應(yīng)聘 人員筆試成績申報(bào)類別志愿專家組對應(yīng)聘者特長的等級評分知

50、識面理解能力應(yīng)變能力表達(dá)能力人員1290(2)(3)AABB人員2_288_(3)_(1)ABAC人員3288(1)(2)BADC人員4285(4)(3)ABBB人員5283(3)(2)BABC人員6283(3)(4)BDAB人員7280(4)(1)ABCB人員8280(2)(4)BAAC人員9280(1)(3)BBAB人員10280(3)(1)DBAC人員11278(4)(1)DCBA人員12277(3)(4)ABCA人員13275(2)(1)BCDA人員14275(1)(3)DBAB人員15274(1)(4)ABCB人員16_273_(4)(1)BABC表2:用人部門的基本情況及對公務(wù)員的

51、期望要求用人部門工作類別各用人部門的基本情況各部門對公務(wù)員特長的希望達(dá)到的要求福利待遇工 作 條 件勞動強(qiáng)度晉升機(jī)會深造機(jī)會知識面理解能力應(yīng)變能力表達(dá)能力部門1(1)優(yōu)優(yōu)中多小BACA部門2(2)中優(yōu)大多少AC部門3(2)中優(yōu)中少多BB部門4(3)優(yōu)差大多多CCAA部門5(3)優(yōu)中中中中部門6(4)中中中中多CBBA部門7(4)優(yōu)中大少多二、具體問題分析和建模求解分析：這是一個(gè)人多事少的非標(biāo)準(zhǔn)指派問題，適用01整數(shù)規(guī)劃求解。使用01整數(shù)規(guī)劃求解的條件分析：人員與任務(wù)數(shù)目和指派要求明確：1、在16個(gè)人中選8人，分配于7個(gè)部門，每個(gè)部門至少一個(gè)人，這是本案例的絕對約束條件；2、“擇優(yōu)按需”錄用，同

52、時(shí)考慮錄用人員的合理分配和使用，有利于發(fā)揮個(gè)人的特長和能力。優(yōu)先考慮考慮應(yīng)聘者能 力與部門需求“擇優(yōu)按需”確定初步分配方案，再結(jié)合應(yīng)聘人員意愿進(jìn)行方案優(yōu)化；3、用人部門對公務(wù)員的期望要求和應(yīng)聘人員的意愿不是絕對約束，但是要盡量滿足（實(shí)際上這里沒有一個(gè)應(yīng)聘者可以 完全滿足部門1的能力期許）。系數(shù)矩陣應(yīng)該體現(xiàn)“擇優(yōu)按需”原則，表征每個(gè)應(yīng)聘者能給各個(gè)部門到來的效率，在本案例中沒有直接給出，需要首先 求解出系數(shù)矩陣；顯見，“擇優(yōu)”要求受聘者的總體綜合得分盡量地高，“按需”指人員合理分配，各部門對公務(wù)員特長 的期望與受聘人員特長盡量吻合，所以系數(shù)矩陣是充分合理地結(jié)合應(yīng)聘者的筆試成績，面試成績及用人部門要

53、求給每個(gè) 應(yīng)聘者打出的綜合評分。解：1、數(shù)據(jù)整理面試環(huán)節(jié)采用等級評分，不便于分析，給A，B，C，D四個(gè)等級分別賦值4、3、2、1，同時(shí)，用人部 門的基本情況主要用于應(yīng)聘者參考選擇申報(bào)志愿，在以下求解中可以忽略，重新整理數(shù)據(jù)得新表格：表1：招聘公務(wù)員筆試成績，專家面試評分及個(gè)人志愿應(yīng)聘.人員1筆試成績申報(bào)類別志愿專家組對應(yīng)聘者特長的等級評分b1知識面理解能力應(yīng)變能力 13表達(dá)能力 14人員1290(2)(3)4433人員2288(3)(1)4342人員3288(1)(2)3412人員4285(4)(3)4333人員5283(3)(2)3432人員6283（3）（4）3143人員7280（4）（1

54、）4323人員8280L2J（4）3442人員9280（1）（3）3343人員10280（3）（1）1342人員11278（4）（1）1234人員12277（3）（4）4324人員13_275_（2）_（1）3214人員14275（1）（3）1343人員15274（1）（4）4323人員16273（4）（1）3432表2:用人部門對公務(wù)員的期望要求用人.部門j工作類別各部門對公務(wù)員特長的希望達(dá)到的要求bj知識面理解能力J2應(yīng)變能力J3表達(dá)能力部門1（1）3424部門2（2）4332部門3（2）部門4（3）2244部門5（3）部門6（4）2334部門7（4）2、結(jié)合每個(gè)應(yīng)聘者的筆試，面試成績及各

55、部門對公務(wù)員的能力期望確定系數(shù)矩陣C：由上表可以得到筆試成績矩陣ai,面試成績矩陣bi，用人部門要求矩陣bj，設(shè)Cij為矩陣第i行第j列 元素，代表第i個(gè)公務(wù)員對應(yīng)于第j個(gè)部門的綜合得分，結(jié)合ai，bi，bj三個(gè)矩陣求解矩陣C，用人部門對 應(yīng)聘者的特長要求在筆試成績部分無法體現(xiàn)，Cij的值應(yīng)該包括考慮用人部門要求影響的面試成績與筆試成 績兩部分。j部門k項(xiàng)能力的期望分越高代表這項(xiàng)能力在該部門越被看重，所以將bj看成bi矩陣的權(quán)重矩 陣，取面試成績矩陣與用人部門要求矩陣相乘所得矩陣、筆試成績矩陣分別乘以各自的權(quán)重在相加所得矩 陣作為系數(shù)矩陣即令C =日 * la ,a ,a ,a+日 *bi*b

56、jT ，1 i i i i 2有Cij = p *a +p *bik*bjk ；k=1、2、3、4，R、R 0為根據(jù)實(shí)際情況設(shè)定的權(quán)數(shù)，這里暫取1 i 212R = 0.1，R = 1,可以得到系數(shù)矩陣如下：應(yīng)聘人員進(jìn)入各部門的面試得分應(yīng)聘人員進(jìn)入各部門的面試得分Cij部門1部門2部門3部門4部門5部門6部門7人員175727269697070人員268.869.869.866.866.865.865.8人員363.859.859.854.854.857.857.8人員470.568.568.566.566.566.566.5人員567.365.365.362.362.363.363.3人員6

57、61.361.361.364.364.361.361.3人員768656562626363人員869686866666666人員969676768686767人員1059575760605959人員1160.854.854.861.861.860.860.8人員1271.766.766.765.765.766.766.7人員1362.556.556.557.557.558.558.5人員1462.558.558.563.563.562.562.5人員1567.464.464.461.461.462.462.4人員1673.370.370.367.367.368.368.33、用Xj. (i =

58、 1,2,.,16; j = 1,2,.,7)表示決策變量，依題意可建立0-1整數(shù)規(guī)劃模型：I 1當(dāng)錄用第i個(gè)應(yīng)聘者是，將其分配到部門x = .j 0不錄用第i個(gè)應(yīng)聘者或者錄用i但不分配到j(luò)部口問題就轉(zhuǎn)化為求下面的優(yōu)化模型：i =1 j =1F! x廣 8，s.t. X. 1(i = s.t. j=11 彖工尸 2(j = 1,2,.7)，j=1X = 0或 1(i = 1,2,.,16; j = 1,2,.,7).2-,2-,c.7 ，得:利用WinSQB求解：增設(shè)虛部門8,取Ci8 = min應(yīng)聘 人員進(jìn)入各部門的面試得分Cij部門1部門2部門3部門4部門5部門6部門7部門8人員17572

59、726969707069人員268.869.869.866.866.865.865.865.8人員363.859.859.854.854.857.857.854.8人員470.568.568.566.566.566.566.566.5人員567.365.365.362.362.363.363.362.3人員661.361.361.364.364.361.361.361.3人員76865656262636362人員86968686666666666人員96967676868676767人員105957576060595957人員1160.854.854.861.861.860.860.854.8

60、人員1271.766.766.765.765.766.766.765.7人員1362.556.556.557.557.558.558.556.5人員1462.558.558.563.563.562.562.558.5人員1567.464.464.461.461.462.462.461.4人員1673.370.370.367.367.368.368.367.3將上表系數(shù)錄入Maximization (Assignment Problem)模型中得解如下： Solution for 公務(wù)員招聘分配問題:Maximization (Assignment Problem)FromToAssignmen