线性规划模型(Linear

Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,*,Copyright(c)2004 Brooks/Cole,a division of Thomson Learning,Inc.,Chapter 3Introduction to Linear Programming,to accompanyOperations Research:Applications&Algorithms,4th edition,by Wayne L.Winston,3.1-What,I,s a Linear Programming Problem?,Each soldier built:,Sell for$27 and uses$,10,worth of raw materials.,Increase,Giapettos,variable labor/overhead costs by$14.,Requires 2 hours of finishing labor.,Requires 1 hour of carpentry labor.,Each train built:,Sell for$21 and used$9 worth of raw materials.,Increases,Giapettos,variable labor/overhead costs by$10.,Requires 1 hour of finishing labor.,Requires 1 hour of carpentry labor.,Exam,p,le from last week,Giapettos,Inc.,manufactures wooden soldiers and trains.,線性規劃模型(Linear Programming model)是在一組線性的限制式(a set of linear constraints)之下，尋找極大化(maximize)或極小化(minimize)一個特定的目標函數(objective function),線性規劃模型由以下三個局部組成:,一組決策變數(A set of decision variables),一個特定的目標函數(An objective function),一組線性的限制式(A set of constraints),Introduction to Linear Programming,Assumptions for Linear Programming,參數具有,確定性,(,certainty),目標函數與限制式符合,固定規模報酬,之假設,(,constant returns to scale),疊加性,之假設：決策變數間沒有互動性,，即某函數之總價值只能藉由線性加總求得,連續性,(Continuity,),之假設變數值必須再某一個可行範圍內,1,單位產品,$4,，,3Hrs,生產,500,單位產品,$4*500=$2000,，,3*500=1,500Hrs,生產,Example of Industries Production Problem,生產兩種玩具模型,:,宇宙光,Space Ray.,射擊手,Zapper.,資源限制,(Resources),1000,磅特殊塑膠化合物,(special plastic),每週,40,小時生產時間,(40 hrs of production time per week),市場需求,(Marketing requirement),每週總產量至多,700,打,Space Rays,週產量不能過,Zappers 350,打以上,技術係數,(Technological inputs),Space Rays,每打需要,2 pounds,塑膠與,3,分鐘生產時間,Zappers,每打需要,1pound,塑膠與,4,分鐘生產時間,Example of Industries Production Problem,生產需求,:,Space Ray,每打利潤,(profit)$8,，,Zappers,每打利潤,(profit)$5,盡量多生產,Space Ray,，剩餘資源再生產,Zapper,目前生產計畫,:,Space Rays =450 dozen,Zapper =100 dozen,Profit =$4100 per week,Example of Industries Production Problem,8(450)+5(100),決策變數,(,Decisions variables),:,X,1,=,每週生產的,Space Rays,打數,X,2,=,每週生產的,Zappers,打數,目標函數,(,Objective Function):,極大化每週總利潤,Example of Industries Production Problem,Max 8X,1,+5X,2,(,每週總利潤,),subject to,2X,1,+1X,2,1000 (,塑膠原料,Plastic),3X,1,+4X,2,2400 (,生產時間,Production Time),X,1,+X,2,700 (,最大產量,Total production),X,1,-X,2,350 (,組合,),X,j,=0,j=1,2 (,非負值,Nonnegativity),Example of Industries Production Problem,Graphical Analysis of Linear Programming,滿足模型全部限制式的所有點集合稱為,The set of all points that satisfy all the constraints of the model is called a,可行區域,FEASIBLE REGION,圖形表示法,(graphical presentation),所有限制式,(all the constraints),目標函數,(objective function),可行點,(three types of feasible points),The non-negativity constraints,(,非負限制式,),X,2,X,1,Graphical Analysis the Feasible Region,1000,500,Feasible,X,2,Infeasible,Production Time,限制式,3X,1,+4X,2,2400,Total production,限制式,X,1,+X,2,700(,多餘,),500,700,Plastic,限制式,2X,1,+X,2,1000,X,1,700,Graphical Analysis the Feasible Region,1000,500,Feasible,X,2,Infeasible,Production Time,限制式,3X,1,+4X,2,2400,Total production,限制式,X,1,+X,2,700(,多餘,),500,700,Mix,限制式,X,1,-X2,350,Plastic,限制式,2X,1,+X,2,1000,X,1,700,Graphical Analysis the Feasible Region,可行點,(feasible points),有三種,內部點,Interior points.,邊界點,Boundary points,.,端點,Extreme points.,The search for an optimal solution,由任一個,profit,開始,say profit=$1,250.,往利潤增加方向移動,increase the profit,if possible.,持續平行移動到無法增加為止,continue until it becomes infeasible,Optimal Profit=$4360,500,700,1000,500,X,2,X,1,紅色線段,Profit,=$1250,Summary of the optimal solution,Space Rays X1*=320 dozen,Zappers X2*=360 dozen,Profit Z*=$4360,此最正确解使用了所有的塑膠原料(plastic)與生產時間(production hours).,2X1+1X2=1000 (塑膠原料,Plastic),3X1+4X2=2400 (生產時間,Production Time),Excel,試算表,束縛方程式,(Binding Constraints):,等式被滿足之限制式,Summary of the optimal solution,總產量,(Total production)680,打,(not 700,打,),Space Rays,產量只超過,Zappers 40,打,非束縛方程式(Non-Binding Constraints)：最正确點不在其等式之限制式,寬鬆(Slack)：限制式右邊與左邊的差額，代表資源的剩餘數量,X1+X2,=680 700(,總產量,),X1 -X2 =-40 350 (,產品組合,),總產量有,700-680=20,的寬鬆,產品組合有,350-(-40)=390,的寬鬆,假设一個線性規劃問題有一組最正确解，此最正确解一定發生在端點上 (端點最正确解之候選人,True/False),兩個束縛方程式的交點形成一個端點或角點,Extreme points and optimal solutions,端點：可行區域的角點,2X1+X2=1000,X1-X2=350,之解,(450,100),(320,360),2X1+X2=1000,3X1+4X2=2400,之解,(0,600),3X1+4X2=2400,X1 =0,之解,假设多重最正确解存在，則目標函數必定平行其中一個限制式,Multiple optimal solutions,多重最正确解之任何加權平均值亦為一組最正确解,X1=(350,0)最正确解1,X2=(0,600),最正确解2,X=X1+(1-)X2,0,1 亦為最正确解,目標函數,Z,Linear Programming Problem,列出,EXCEL,的求解方式,:,Min:,H3=F3*F4+G3*G4,H6=F3*F6+G3*G6,H7=F3*F7+G3*G7,H8=F3*F8+G3*G8,輸入公式,1.,輸入變數,x1,x2,的值所在的儲存格,2.,新增,限制式,1.,輸入限制式左邊及右邊的儲存格,2.,選擇適當的符號,按,求解,後的結果,3.2 Graphical Solution to a 2-Variable LP,Binding and Nonbinding constraints,A constraint is,binding,if the left-hand and right-hand side of the constraint are,equal,when the optimal values of the decision variables are substituted into the constraint.In the Giapetto LP,the finishing and carpentry constraints are binding,.,Once the optimal solution to an LP is found,it is useful to classify each constraint as being a binding or nonbinding constraint.,3.2