ในการแก ป ญหาโลจ สต กส เช งว เคราะห ก าหนดการเช งเส นค ออะไร (LP)? เรามาลองสร าง LP แรกของเราก น. Outline - PDF

Description
การอบรมการใช Microsoft Excel ในการแก ป ญหาโลจ สต กส เช งว เคราะห ผ ช วยศาสตราจารย ดร.มาโนช โลหเตปานนท ห วหน าโครงการเพ มศ กยภาพเพ อก าวส ความเป นเล ศด าน ว ศวกรรมศาสตร วศวกรรมศาสตร สาขาโครงสรางพนฐานเพอสงเสรม

Please download to get full document.

View again

of 23
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Magazines/Newspapers

Publish on:

Views: 28 | Pages: 23

Extension: PDF | Download: 0

Share
Transcript
การอบรมการใช Microsoft Excel ในการแก ป ญหาโลจ สต กส เช งว เคราะห ผ ช วยศาสตราจารย ดร.มาโนช โลหเตปานนท ห วหน าโครงการเพ มศ กยภาพเพ อก าวส ความเป นเล ศด าน ว ศวกรรมศาสตร วศวกรรมศาสตร สาขาโครงสรางพนฐานเพอสงเสรม สาขาโครงสร างพ นฐานเพ อส งเสร ม ระบบการขนส ง โลจ สต กส และโซ อ ปทาน คณะว ศวกรรมศาสตร จ ฬาลงกรณ มหาว ทยาล ย Outline ก าหนดการเช งเส น (Linear Programming: LP) ต วอย าง ตวอยาง LP การหาค าตอบโดยใช กราฟ การใช Excel s olver ก าหนดการเช งจ านวนเต ม (Integer Programming: IP) Manoj Lohatepanont 29 2 Mathematical Model แบบจ าลอง (Model) ค ออะไร? การจ าลองความเป นจร ง แบบจ าลองเคร องบ น แบบจ าลองเช งคณ ตศาสตร ค ออะไร (mathematical model)? การจ าลองความเป นจร งด วยฟ งก ช นหร อสมการคณ ตศาสตร F = ma, E = mc 2 Linear Programming (LP) ก าหนดการเช งเส นค ออะไร (LP)? ก าหนดการเช งเส นค อแบบจ าลองคณ ตศาสตร ท ต องการหา ค าสงสดหร อต คาส งส ดหรอตาส ดของฟงกชนเชงเสนวตถ ประสงคหนง าสดของฟ งก ช นเช งเส นว ตถประสงค หน ง โดยม เง อนไขเช งเส นประกอบอย ช ดหน ง เรามาลองสร าง LP แรกของเราก น Manoj Lohatepanont 29 3 Manoj Lohatepanont 29 4 Example: Galaxy Industries Galaxy Industries ผล ตส นค า 2 ชน ดค อ: pace Rays () appers () ก าไรจากส นค าแต ละชน ดค อ: $8 ส าหร บ a dozen of pace Rays $5 ส าหร บ สาหรบ a dozen of appers ด งน นฟ งก ช นว ตถ ประสงค (Objective Function) ค อ: Profit = $8+ $5 และ เป นต วแปรแทนจ านวนโหลท ผล ต Resource Limitation ในการผล ตส นค าแต ละชน ดใช ทร พยกรต อส ปดาห ด งน ทร พยากรท ใช pace Ray apper ทร พยากรท ม (ต อโหล) (ต อโหล) Plastic (lb) Time (min) Manoj Lohatepanont 29 5 Manoj Lohatepanont 29 6 Resource Limitation จากเง อนไขด งกล าวเราสามารถเข ยนเง อนไขเช งเส น (Linear Constraints) ได ด งน Plastic: = 1 Time: = 24 Additional Requirements ก าหนดว าไม สามารถผล ตส นค ารวมเก น 7 ช น (marketing limit) Marketing: + = 7 จ านวน จานวน pace Rays ต องน อยกว าจ านวน ตองนอยกวาจานวน appers บวก 35 ช นต อส ปดาห Product Mix: = + 35 or = 35 Manoj Lohatepanont 29 7 Manoj Lohatepanont 29 8 Physical Limitation ส นค าท ผล ตห ามเป นจ านวนต ดลบ Nonnegativity: = = Galaxies Industries LP Model Max Profit = $8+ $5 ubject to: Plastic: = 1 Time: = 24 Marketing: + = 7 Product Mix: = 35 Nonnegativity: =, = Manoj Lohatepanont 29 9 Manoj Lohatepanont 29 1 LP Model Components ต วแปรต ดส นใจ Decision Variables ฟ งก ช นว ตถประสงค ฟงกชนวตถ ประสงค Objective Function เง อนไข Constraints ส มประส ทธ ของฟ งก ช นว ตถ ประสงค Objective Function Coefficients เมทร กซ เง อนไข Constraint Matrix ค าด านขวาม อ Right-Hand-ide (RH) เคร องหมายของเง อนไข Constraint s ense Galaxies Industries Model Max Objective Profit Function = $8+ $5 ubject to: Plastic: = 1 Time: = 24 Marketing: Constraint + = 7 RH Matrix Product Mix: = 35 Nonnegativity: it = = ense nt s e nstrain Con Obj. Func. Coeff. Manoj Lohatepanont Manoj Lohatepanont 29 12 Optimal olution Galaxy Industries ควรผล ต pace Rays และ appers อย างละก ช นจ งจะได ก าไรส งส ด? จ านวนผล ตท ให ก าหรส งส ด เร ยกว า ผลเฉลยท ด ท ส ด (optimal solution) ) ผลเฉลยท ด ท ส ด เป นผลเฉลยท เป นไปได (feasible solution) ท ม ค า ฟ งก ช นว ตถ ประสงค ด ท ส ด ในท น ด ท ส ดค อ ส งท ส ด ผลเฉลยท เป นไปได ค อ ผลเฉลยท ผ านเง อนไขท กข อ น าเสนอ 3 ว ธ การหาค าตอบ ลองผ ดลองถ ก การใช กราฟ การใช Microsoft Excel s olver การลองผ ดลองถ ก ใช เวลา ใชเวลา พ ส จน ไม ได ว าค าตอบท ได ด ท ส ดหร อย ง Manoj Lohatepanont Manoj Lohatepanont ข อด Graphical olution ง ายต อการท าความเข าใจ ง ายต อการพ ส จน ว าค าตอบท ได ด ท ส ดแล ว ข อเส ย ช าและเส ยเวลา ชาและเสยเวลา ไม สามารถแก ป ญหาขนาดเก น 2-3 ต วแปรได Plastic Plastic: = Plastic: = 1. Note: This figure already implies nonnegativity. Manoj Lohatepanont Manoj Lohatepanont 29 16 Plastic + Time Plastic + Time + Marketing Time: = 24. Plastic: = Marketing: = 7. Time: = 24. Plastic: = Plastic: = 1. Time: = 24. With each added constraint, the feasible region can only get MALLER or stay the same. Plastic: = 1. Time: = 24. Marketing: = 7. Manoj Lohatepanont Manoj Lohatepanont Plastic + Time + Marketing + Mix Mix: = 35. Marketing: = 7. Time: = 24. Plastic: = บร เวณท เป นไปได (Feasible Region) บร เวณท เป นไปได : เซตของท กจ ดท สอดคล องก บ ทกเง ท กเงอนไขของแบบจาลอง อนไขของแบบจ าลอง Plastic: = 1. Time: = 24. Marketing: = 7. Mix: = 35. Plastic: = 1. Time: = 24. Marketing: = 7. Mix: = 35. A feasible solution always resides in the feasible region. Manoj Lohatepanont Manoj Lohatepanont 29 2 การหาผลเฉลยท ด ท ส ด การหาผลเฉลยท ด ท ส ด Payoff: = Payoff: = Plastic: = 1. Time: = 24. Marketing: = 7. Mix: = 35. Plastic: = 1. Time: = 24. Marketing: = 7. Mix: = 35. Manoj Lohatepanont Manoj Lohatepanont การหาผลเฉลยท ด ท ส ด การหาผลเฉลยท ด ท ส ด Payoff: = Payoff: = Optimal Decisions(,): (32., 36.) Plastic: = 1. Time: = 24. Marketing: = 7. Mix: = 35. Plastic: = 1. Time: = 24. Marketing: = 7. Mix: = 35. Manoj Lohatepanont Manoj Lohatepanont 29 24 การหาผลเฉลยท ด ท ส ด ถ าฟ งก ช นว ตถ ประสงค เปล ยนไป Payoff: = 436. Payoff: = (32, 36) Optimal olution for THI obj. func. is: dozens of pace Rays dozens of appers Optimal Decisions(,): (32., 36.) Plastic: = 1. Time: = 24. Marketing: = 7. Mix: = Optimal olution for THI obj. func. is: dozens of pace Rays dozens of appers Optimal Decisions(,): (45., 1.) Plastic: = 1. Time: = 24. Marketing: = 7. Mix: = 35. (45, 1) Manoj Lohatepanont Manoj Lohatepanont ถ าฟ งก ช นว ตถ ประสงค เปล ยนไป (, 6) 6 Payoff: = Optimal olution for THI obj. func. is: dozens of pace Rays dozens of appers Optimal Decisions(,): (., 6.) Plastic: = 1. Time: = 24. Marketing: = 7. Mix: = 35. ค ณสมบ ต ของผลเฉลยท ด ท ส ด ถ าผลเฉลยท ด ท ส ด (Optimal olution) ม อย จร ง จะต องอย ท จ ด มม ม ม (Corner Point) ของบร เวณท เป นไปได ของบรเวณทเปนไปได (Feasible Region) (, 6) (, ) (32, 36) (35, ) (45, 1) Manoj Lohatepanont Manoj Lohatepanont 29 28 กรณ พ เศษ กรณพเศษ 1: ม หลายผลเฉลย มหลายผลเฉลย (Multiple Optimal olution) Payoff: = 1. กรณ พ เศษ 2: ไม ม ผลเฉลย (Infeasible) Payoff: = (32, 36) Optimal olutions for THI obj. func. are all points satisfying equation = 1 in ranges of [32,45] pace Rays and [1,36] appers (45, 1) Optimal Decisions(,): (32., 36.) (45., 1.) Plastic: = 1. Time: = 24. Marketing: = 7. Mix: = 35. Note optimal solutions also contain extreme/corner points. Optimal Decisions(,): (32., 36.) Plastic: = 1. Time: = 24. Marketing: = 7. Mix: = 35. Crazy Manager: = 65. An infeasible problem is one in which feasible region is of zero size. Manoj Lohatepanont Manoj Lohatepanont กรณ พ เศษ กรณพเศษ 3: ป ญหาม ปลายเป ปญหามปลายเปด (Unbounded Problem) Payoff: = Optimal Decisions(,): (32., 36.) (45., 1.) Plastic: = 1. Time: = 24. Marketing: = 7. Mix: = 35. Objective function can be increased (or decreased) indefinitely. เคร องหมายของเง อนไข (Constraint s ense) In mathematical programming, all constraints senses must be inclusive That is it must be either =, = or, =. It cannot be or . Consider a simple problem Max X.T. X 5 X = What s the optimal solution? Manoj Lohatepanont Manoj Lohatepanont 29 32 Excel s olver Microsoft Excel ม ค าส งท ต ดมาอย แล วช อ olver เราจะลองใช Excel ในการแก ป ญหาเม อส กคร ท ผ าน มา จากแบบจ าลองเด ม Max Profit = $8+ $5 ubject to: Plastic: = 1 Time: = 24 Marketing: + = 7 Product Mix: = 35 Nonnegativity: =, = Manoj Lohatepanont Manoj Lohatepanont เข าส แบบจ าลองใน Excel Max Profit = $8+ $5 ubject to: Plastic: = 1 Time: = 24 Decision Variables Marketing: + = 7 Obj. Func. Coeff. Product Mix: = 35 Constraint Matrix Nonnegativity: =, = Obj. Func. Value RH ใส ข อม ลใน Excel Manoj Lohatepanont Manoj Lohatepanont 29 36 Enter Objective Function LP Model Obj. Func. Value Manoj Lohatepanont Manoj Lohatepanont Invoking olver olver Window If olver does not exist, select Add Add-Ins and then check an empty box in front of olver. Click OK. Manoj Lohatepanont Manoj Lohatepanont 29 4 et Target Cell Enter Decision Variables Manoj Lohatepanont Manoj Lohatepanont Enter Constraints Add Constraints Manoj Lohatepanont Manoj Lohatepanont 29 44 Options Ready to olve Manoj Lohatepanont Manoj Lohatepanont Done! View olution Manoj Lohatepanont Manoj Lohatepanont 29 48 Verify olution Payoff: = (32, 36) Optimal olution for THI obj. func. is: dozens of pace Rays dozens of appers Optimal Decisions(,): (32., 36.) Plastic: = 1. Time: = 24. Marketing: = 7. Mix: = 35. Manoj Lohatepanont Manoj Lohatepanont 29 5 ก าหนดการเช งจ านวนเต ม กาหนดการเชงจานวนเตม Integer Programming (IP) ก าหนดการเช งจ านวนเต มค ออะไร ก าหนดการเช งจ านวนเต มค อแบบจ าลองท ม บางต วแปรเป นจ านวนเต ม กาหนดการเชงจานวนเตมคอแบบจาลองทมบางตวแปรเปนจานวนเตม Max ubject to 2 + = = 24, = and integer Feasible Region ของ IP How does an IP s feasible region look like? Y X Manoj Lohatepanont Manoj Lohatepanont 29 52 Feasible Region ของ IP LP optimal is not necessary IP optimal IP optimal cannot be better than LP optimal; why? olving IP with Excel Designate the integer variables in the Add Constraint Window Y IP Optimal LP Optimal X Manoj Lohatepanont Manoj Lohatepanont ป ญหาการไหลในโครงข าย ปญหาการไหลในโครงขาย Network Flow Problem กล มป ญหาท ศ กษาการไหลในโครงข าย ใช มากในงานขนส งและโลจ สต กส ใชมากในงานขนสงและโลจสตกส ม ล กษณะพ เศษท ท าให การสร างแบบจ าลองท าได ง าย Manoj Lohatepanont Manoj Lohatepanont 29 56 องค ประกอบของโครงข าย ข อม ลในโครงข าย โครงข ายม องค ประกอบหล ก 2 ส วนค อ: Nd Node Arc Arc เช อม 2 Node ท อย ต ดก น A B C D ข อม ลในโครงข าย: Nodes Demand or upply Arcs ต นท นต อหน วย ปร มาณการไหลท เก ดข นจร ง ความจ ของ Arc A upply: A A Unit Cost: C AB Flow: X AB Capacity: U AB B Manoj Lohatepanont Manoj Lohatepanont Example B = 2 C BC = 7 B BC = 12 A = 2 A D D D = 25 U BC ปร มาณการไหล (Arc Flow) ปร มาณการไหลเก ดข นบน Arc ปร มาณการไหลบน Arc AB เข ยนแทนด วยต วแปร ส ใ X ตดสนใจ X AB C A Flow: X AB B D C = 15 Manoj Lohatepanont Manoj Lohatepanont 29 6 Decision Variable X AB X AC X BC X BD X CD ต นท น ต นท นของการไหลเก นจากผลค ณของปร มาณการไหลและ ต นทนต อหน วยบนแต ล ตนท นตอหนวยบนแตละ Arc ต นท นบน Arc AB = C AB * X AB A Unit Cost: C AB B Flow: X AB ต นทนรวมท ตนท นรวมทงโครงขายเกดจากตนท นของแตละ งโครงข ายเก ดจากต นทนของแต ละ Arc รวมก น รวมกน Manoj Lohatepanont Manoj Lohatepanont Objective Function Coefficient X AB X AC X BC X BD X CD การสงวนปร มาณการไหล (Conservation of Flow) Flows In + upply = Flows Out + Demand B = 2 Flows In = B + X AB B Flows Out = X BC + X BD A D X AB + B = X BC + X BD C X AB -X BC -X BD = - B Manoj Lohatepanont Manoj Lohatepanont 29 64 การแทนอปสงค แล การแทนอ ปสงคและอ ปทาน อปทาน Demand and upply Representation อ ปทาน ให ปร มาณก บ node Flow In Positive อปสงค อ ปสงค บร โภคปร มาณจาก บรโภคปรมาณจาก node Flow Out Negative upply: A or Demand: D A A A Flow Conservation X AB X AC X BC X BD X CD AB AC BC BD CD B C D Flow Conservation at Node B X AB -X BC -X BD = -2 = -2 Manoj Lohatepanont Manoj Lohatepanont Flow Conservation X AB X AC X BC X BD X CD ขอบเขตของต วแปร ความจ ของ Arc เป น ขอบเขตบนของต วแปรต ดส นใจ AB AC BC BD CD A -1-1 = -2 B = -2 C = 15 D 1 1 = 25 B A ขอบเขตล างม กจะเป น ขอบเขตลางมกจะเปน X ij = = X AB AB = U AB Manoj Lohatepanont Manoj Lohatepanont 29 68 Network Model Node-Arc Incidence Matrix X AB X AC X BC X BD X CD X AB X AC X BC X BD X CD AB AC BC BD CD X ij ij = U ij X ij = AB AC BC BD CD X ij ij = U ij X ij = A -1-1 = -2 A -1-1 = -2 B = -2 B = -2 C = 15 D 1 1 = 25 C = 15 D 1 1 = 25 Manoj Lohatepanont Manoj Lohatepanont 29 7 ว ธ เข ยน Node-Arc เมทร กซ อย างง าย Node-Arc Incidence Matrix เร ยง เรยง Arc ในแนวต ในแนวตง ง (variables) เร ยง Node ในแนวนอน (constraints) ใส เลข +1 และ -1 แล วแต กรณ (ด ต วอย าง) A Node-Arc Incidence Matrix B This is our constraint matrix D C A -1-1 AB AC BC BD CD B C D 1 1 Manoj Lohatepanont um = Manoj Lohatepanont 29 72 A Network Model X AB X AC X BC X BD X CD B This is our constraint matrix X ij = U ij D X ij = AB AC BC BD CD Min Cost Flow: Example B =2 B C A -1-1 = -2 B 1-1= -1-2 C 1 1 = 15-1 D = C BC = 7 BC = 12 A = 2 A D D D = 25 U BC C D C = 15 Manoj Lohatepanont Manoj Lohatepanont Min Cost Flow Problem Transshipment Problem X AB X AC X BC X BD X CD X AB X AC X BC X BD X CD AB AC BC BD CD X ij ij = U ij X ij = 1 5 Unit Arc 7 Cost 2 8 AB AC BC BD CD X ij ij = U ij X ij = A -1-1 = -2 B = -2 C = 15 D 1 1 = 25 A -1-1 = -2 Node-Arc Incidence Matrix B C = -2 ense RH = 15 D 1 1 = 25 Manoj Lohatepanont Manoj Lohatepanont 29 76 แบบจ าลองใน Excel X AB X AC X BC X BD X CD AB AC BC BD CD X ij ij = U ij X ij = A -1-1 = -2 B = -2 C = 15 D 1 1 = 25 Manoj Lohatepanont Manoj Lohatepanont ผลเฉลย B = 2 B BC = 12 A = 2 A D D D = 25 X BC BC = 12 U BC C D C = 15 Manoj Lohatepanont 29 79 LP 1. A farmer has 1 acres to plant in wheat and rye. He has to plant at least 7 acres. However, he has only $12 to spend and each acre of wheat costs $2 to plant and each acre of rye costs $1 to plant. Moreover, the farmer has to get the planting done in 12 hours and it takes an hour to plant an acre of wheat and 2 hours to plant an acre of rye. If the profit is $5 per acre of wheat and $3 per acre of rye how many acres of each should be planted to maximize profits? 2. Furnco manufactures tables and chairs. A table requires 4 board ft of wood, and a chair requires 3 board ft of wood. Wood may be purchased at a cost of $1 per board ft, and 4, board ft of wood are available for purchase. It takes 2 hours of skilled labor to manufacture an unfinished table or an unfinished chair. Three more hours of skilled labor will turn an unfinished table into a finished table, and 2 more hours of skilled labor will turn an unfinished chair into a finished chair. A total of 6, hours of skilled labor are available (and have already been paid for). All furniture produced can be sold at the following unit prices: unfinished table. $7; finished table, $14; unfinished chair, $6; finished chair, $11. Formulate an LP that will maximize the contribution to profit from manufacturing tables and chairs. 3. A gold processor has two sources of gold ore, source A and source B. In order to keep his plant running, at least three tons of ore must be processed each day. Ore from source A costs $2 per ton to process, and ore from source B costs $1 per ton to process. Costs must be kept to less than $8 per day. Moreover, Federal Regulations require that the amount of ore from source B cannot exceed twice the amount of ore from source A. If ore from source A yields 2 oz. of gold per ton, and ore from source B yields 3 oz. of gold per ton, how many tons of ore from both sources must be processed each day to maximize the amount of gold extracted subject to the above constr
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks