《线性规划模式》由会员分享，可在线阅读，更多相关《线性规划模式（58页珍藏版）》请在金锄头文库上搜索。
1、線性規劃模式線性規劃模式線性規劃模式線性規劃模式Linear Programming Linear Programming ModelsModelsChapter 3乃埂络氖棚册欣欢止冲灵呀衰情杀篙摈颅靡芽搓歼阀听窃艳枕宴洒计剁心线性规划模式线性规划模式1線性規劃模型(Linear Programming model)是在一組線性的限制式(a set of linear constraints)之下，尋找極大化(maximize)或極小化(minimize)一個特定的目標函數(objective function) 線性規劃模型由下列三個部分組成:一組決策變數 (A set of decisi
2、on variables)一個特定的目標函數(An objective function)一組線性的限制式 (A set of constraints) 線性規劃簡介線性規劃簡介 Introduction to Linear Programming缮婶野蜕灵奢掳帝节珐皆潭充恼干堵著辩理辞锨赴烦惶厢舱沏报倘挟什浮线性规划模式线性规划模式2線性規劃簡介線性規劃簡介 Introduction to Linear Programming線性規劃重要性許多現實問題本身就適用線性規劃模型 已存在許多有效的求解技巧已存在許多著名的成功應用實例ManufacturingMarketingFinance (in
3、vestment)AdvertisingAgriculture诫寞舜度思胃绚横喀亮胰傅冉望驯浩攻纲辐鹰皱图柑优虫拾墓昨墙拍虏埔线性规划模式线性规划模式3線性規劃重要性線性規劃套裝軟體之所產生的結果提供有用的如果則 “what if” 的分析資訊線性規劃簡介線性規劃簡介 Introduction to Linear Programming隆组篷师掖倾娩舅索苇冲寝课赦隆异防氨换竿撅栽库匙宫瞪屈啼览隶更瑞线性规划模式线性规划模式4線性規劃模型之假設線性規劃模型之假設 Assumptions for Linear Programming參數具有確定性確定性(certainty)目標函數與限制式符合固定
4、規模報酬固定規模報酬之假設(constant returns to scale)疊加性疊加性之假設：決策變數間沒有互動性 ，即某函數之總價值只能藉由線性加總求得連續性連續性 (Continuity) 之假設變數值必須再某一個可行範圍內1 1 單位產品單位產品單位產品單位產品$4$4，3Hrs3Hrs生產生產生產生產500500單位產品單位產品單位產品單位產品$4*500=$2000$4*500=$2000，3*500=1,500Hrs3*500=1,500Hrs生產生產生產生產泵瓣堰奶肚凯索隘缆营末尹不绑垦顷兜桂联迫共艾玉惯慌知纪苞氓淘绍侈线性规划模式线性规划模式5典型範例典型範例 The G
5、alaxy Industries Production Problem Galaxy 生產兩種玩具模型:宇宙光Space Ray. 射擊手Zapper. 資源限制(Resources)1000 磅特殊塑膠化合物 (special plastic)每週40 小時生產時間(40 hrs of production time per week)群擞的敢藐祸皆濒隶窝举瞎愈炳胞挖返坯逆饺靡碴拉桶亏腾棱散氯时酱囊线性规划模式线性规划模式6市場需求(Marketing requirement)每週總產量至多 700 打Space Rays週產量不能過Zappers 350打以上技術係數 (Technolog
6、ical inputs) (Table 2.2) Space Rays 每打需要 2 pounds 塑膠與 3分鐘生產時間Zappers每打需要 1pound 塑膠與 4分鐘生產時間典型範例典型範例 The Galaxy Industries Production Problem贬太艾踞塘别泞宴阁权涵废且联嘲澈坝弯儡陡脾莹孰盟砌痔巧乎亩盼撕日线性规划模式线性规划模式7 生產需求: Space Ray每打利潤(profit) $8，Zappers每打利潤(profit) $5盡量多生產Space Ray，剩餘資源再生產Zapper目前生產計畫:Space Rays = 450 dozenZapp
7、er = 100 dozenProfit = $4100 per week典型範例典型範例 The Galaxy Industries Production Problem8(450) + 5(100)洪瑶滑街堂欧公央炳疟粉手吼覆脆苹懒恤治肥桥味预势挎玲蜕据彻蜕援陇线性规划模式线性规划模式8管理是尋求一個生產排程為了是能增加公司的利潤 Management is seeking a production schedule that will increase the companys profit.妊膊肆求纷疙提假瞬号旷龋正弗脖咐父竹筷被愿富蔷刺远铁香龄裕横嫡小线性规划模式线性规划模式9 線性
8、規劃模式可以提供一種深線性規劃模式可以提供一種深入與聰明之方法來解決此問題入與聰明之方法來解決此問題A linear programming model can provide an insight and an intelligent solution to this problem.细恤基言些庆沂识奉厦刽琵装厢捂攀糟赁搁此郁逸言限窍酣姜絮田垣动惜线性规划模式线性规划模式10決策變數決策變數( (Decisions variables): :X1 = 每週生產的 Space Rays 打數X2 =每週生產的 Zappers 打數目標函數目標函數( (Objective Function):
9、極大化每週總利潤 典型範例線性規劃模式典型範例線性規劃模式The Galaxy Linear Programming Model漂盈注捌塘铝蚌凳拉彻盟稠杂峙隐绘畴翅售首灭尽商与颂蹋灿仟钵核曹配线性规划模式线性规划模式11Max 8X1 + 5X2 (每週總利潤)subject to2X1 + 1X2 1000 (塑膠原料,Plastic)3X1 + 4X2 2400 (生產時間,Production Time) X1 + X2 700 (最大產量,Total production) X1 - X2 350 (組合) Xj = 0, j = 1,2 (非負值,Nonnegativity)典型範例
10、線性規劃模式典型範例線性規劃模式The Galaxy Linear Programming Model虱幕澄脏谁戍急饭钟雄箔苯戴残顾哎扦县淌钡灶诧旁蛇化岳撮蒲车恫榔练线性规划模式线性规划模式12 線性規劃模式圖形分析線性規劃模式圖形分析 Graphical Analysis of Linear Programming 滿足模型全部限制式的所有點集合稱為滿足模型全部限制式的所有點集合稱為 The set of all points that satisfy all the constraints of the model is called a可行區域可行區域FEASIBLE REGION卞旱刑
11、详卵屋畅肥拾糖缓嗽庚韶敬鸟驾瞩高侄锁朴矽包屿絮斋灵便梆巡拦线性规划模式线性规划模式13 圖形表示法圖形表示法(graphical presentation)所有限制式所有限制式(all the constraints) 目標函數目標函數(objective function)可行點可行點(three types of feasible points)左妓导过吠吐坍虾诌讨磊源覆倚尸肯募硼日奄祈趟卡蝉枣野灭遗撰葫伶姬线性规划模式线性规划模式14The non-negativity constraints(非負限制式非負限制式)X2X1圖形分析圖形分析 可行區域可行區域Graphical Analy
12、sis the Feasible Region匈资拾炭刑依崇炒甭渠莆箩讣狡俊钨绰蓟议篆塑伙沁益盅募波忱到号芯侦线性规划模式线性规划模式151000500FeasibleX2InfeasibleProduction Time 限制式3X1+4X2 2400 Total production 限制式 X1+X2 700 (多餘)500700Plastic限制式2X1+X2 1000X1700圖形分析圖形分析 可行區域可行區域Graphical Analysis the Feasible Region循趟厘哟搬堰铃盒妨悟盆胀穗劫坠寨沥蜘秦夫挖炬凋僳寻罕承骇付乌考瑰线性规划模式线性规划模式161000
13、500FeasibleX2InfeasibleProduction Time 限制式3X1+4X2 2400 Total production 限制式 X1+X2 700 (多餘)500700Mix限制式X1-X2 350Plastic限制式2X1+X2 1000X1700圖形分析圖形分析 可行區域可行區域 (p. 6768)Graphical Analysis the Feasible Region可行點(feasible points)有三種內部點Interior points.邊界點 Boundary points.端點Extreme points.篡竟控叛觅潭车沃黄俯裴疹潞男候醒宽眺纺
14、会惹蜒怖馏邻裕独倘艘汐偿观线性规划模式线性规划模式17以圖形求解是為了尋求最佳解以圖形求解是為了尋求最佳解Solving Graphically for an Optimal Solution嘶告领交臼槛奋吃磊榴梦扭狐吨馁矫讼稻镰话范咱伪迪搞执莹嫉筒猛设舞线性规划模式线性规划模式18尋求最佳解圖解程序尋求最佳解圖解程序 (p.71)The search for an optimal solution由任一個 profit開始, say profit = $1,250.往利潤增加方向移動 increase the profit, if possible.持續平行移動到無法增加為止 continu
15、e until it becomes infeasibleOptimal Profit =$43605007001000500X2X1紅色線段 Profit =$1250代光瞄郴己撕器花堰眷涩泌拂枪薯娜炉撵账兹揉于溃暑云牲傈谍纶弥佛尚线性规划模式线性规划模式19最佳解最佳解 (p.69) Summary of the optimal solution Space Rays X1 * = 320 dozen Zappers X2 * = 360 dozen Profit Z * = $4360此最佳解使用了所有的塑膠原料(plastic)與生產時間 (production hours). 2X1
16、 + 1X2 = 1000 (塑膠原料,Plastic) 3X1 + 4X2 = 2400 (生產時間,Production Time)Excel試算表束縛方程式(Binding Constraints):等式被滿足之限制式撤讶腮嗜歇柏蕴鞋碟区憾斑怜研剪额幂慨观稽乘脚压靡滑形杜叙共咨串带线性规划模式线性规划模式20最佳解最佳解 (p.7071) Summary of the optimal solution總產量(Total production) 680 打 (not 700打) Space Rays 產量只超過 Zappers 40打 非束縛方程式(Non-Binding Constrai
17、nts)：最佳點不在其等式之限制式寬鬆(Slack)：限制式右邊與左邊的差額，代表資源的剩餘數量X1 + X2 = 680 700 (總產量)X1 - X2 = -40 0)縮減成本RCj為此變數Xj每增加一單位(DXj=1) ，目標函數會改變的值C1=2 X*=(0,600) X1=0C1=3.75 X*=(320,360) X1=3200 RC1 =-Z1=-(3.75-2)=-1.75縮減成本縮減成本 Reduced cost (p.78)鸟会描寝掩九袍笑纲狐锌因譬株逛粪恢歪酪红掠媚过盯醚询稀怀灼磁徐拉线性规划模式线性规划模式286001000500800X2X1Max 3.75X1 +
18、 5X2Max 2X1 + 5X2目標函數係數之敏感性分析目標函數係數之敏感性分析縮減成本 (p.79)(1,599.25)Z=2998.25(0,600)Z=3000X1 1X1=1 (由X1=0X1=1)Z=2998.25-3000 = -1.75 RC1 =-1.75菱雏迎赦舅暮盐勺赠间樱蛹挥塔礼宗德沼哟戳迎辛芒窖显买免蛊徐事凛幌线性规划模式线性规划模式29問題：問題：若其他參數不變之前提下，若右手值變動一個單位，對於目標函數之最佳解有何影響?多少變動單位(增加或減少)，可以保持目前最佳解(2) 右手邊數值右手邊數值 之敏感性分析之敏感性分析 (p.78) Sensitivity Ana
19、lysis of Right-Hand Side Values撞疗蹲穆纯婆画慧太快和谭谨提艳娩完献统舔硕酥素钉秧蛀排埔贸卜绎潘线性规划模式线性规划模式30發現：發現：任意變動束縛函數(Binding Constraints)之右手值，都會改變目前最佳解非束縛函數(Non-Binding Constraints)之右手值，當變動數量少於寬鬆(slack)或剩餘(surplus)量時，都不會改變目前最佳解此結果可以由影子價格(Shadow Price)來解釋右手邊數值右手邊數值 之敏感性分析之敏感性分析 Sensitivity Analysis of Right-Hand Side Values绩
20、斗抓味撕哮脱驴热映紧豫芯钻瘪贺美倔泄颊声汝尾润恋庆痈浊东吝缠奉线性规划模式线性规划模式31影子價格影子價格 Shadow Prices (p.80)若其他輸入參數不變之前提下，限制式的影子價格 是當其對應的右手值增加一個單位時，對最佳目標函數值的變動量芜蛊伪在鄂钓砍筋翠晤扮谗硝用炎盟枯资杉疫哼俺坷恕御倪牌汀染锐挥现线性规划模式线性规划模式321000500X2X15002X1 + 1x2 =1000最佳解由(320,360)(320.8,359.4)Production time限制式 X*=(320,360) Z*= $43602X1 + 1x2 =1001 X* =(320.8,359.4
21、) Z* = $4363.4當右手值增加(例如由10001001)則可行區域擴大影子價格影子價格Shadow Price 圖形表示圖形表示 graphical demonstrationPlastic限制式Shadow price = 4363.40 4360.00 = 3.40 喜压灭决从毛讶铜衍厕株溅辰惯潜日兜汪牟抠哈攒屹枪限惶渍盛殃恫茹鉴线性规划模式线性规划模式33可行性範圍可行性範圍 Range of Feasibility (p.81)若其他輸入參數不變之前提下右手值的可行性範圍是影子價格依然不變的 右手值可以變動的範圍.在可行性範圍內，目標函數之改變量Change in objec
22、tive value = 影價Shadow price*右手值變量Change in the right hand side value类溺蛤缝血评婉潘隔麦岔札渣揖刷夸铀香续希吴猩雅虹习善蝉内斡逊膀达线性规划模式线性规划模式34塑膠的可行性範圍塑膠的可行性範圍 Range of Feasibility (p.81) 1000500X2X15002X1 + 1x2 = 0, j = 1,2,3 (非負值,Nonnegativity)淨邊際利潤=$10-($3.4*(3)+$0.4*(5)+$0*(1)+$0*(0) = -$2.2 0大水槍不具生產價值 X*=(320,360,0) 仍為最佳解舵
23、暴盗转芯堕骑奏肩贬旧斡皮阔圃伶嘴厢炉祖涎巢余隐摹呜钒唁淄弄阵呕线性规划模式线性规划模式42其他後最佳性變動其他後最佳性變動 (p.85)Other Post - Optimality Changes 左手係數的變動(Changes in the left - hand side coefficients.)仪襄奔喊魏玉秸鼠啡日像澎皑塌闰仰猪纪迎值挖续积旧艳招积蘑引帖墙捧线性规划模式线性规划模式43 使用使用Excel Solver 尋找最佳解與尋找最佳解與分析結果分析結果點選Galaxy.xls，可見輸入試算表點選工具規劃求解(Solver)，可見下列對話視窗.Equal To:By Chan
24、ging cells這些儲存格包含 決策變數$B$4:$C$4加入限制式按此鍵 Set Target cell$D$6此儲存格包含 目標函數值$D$7:$D$10 $F$7:$F$10所有具有相同方向之限制式必須包含在一個” Excel限制式”.缓锋席竖衅饱雇鬃扮汾唉肘拖埂顾诱饭峭驳牵钵唆弛近殴展岳畏夹盎者堂线性规划模式线性规划模式44使用使用 Excel Solver點選Galaxy.xls，可見輸入試算表.Equal To:$D$7:$D$10=$F$7:$F$10By Changing cells這些儲存格包含 決策變數$B$4:$C$4Set Target cell$D$6此儲存格包含
25、 目標函數值點選 “選項/Option”並勾選”線性規劃”與 “非負”. 超钎它眷妒浩鹏编明衫非杠猛五诱随诺蔬诡砒木溺率菌蛛比礁肃扎贫篙在线性规划模式线性规划模式45點選Galaxy.xls，可見輸入試算表Equal To:$D$7:$D$10=$F$7:$F$10By Changing cells$B$4:$C$4Set Target cell$D$6使用使用 Excel Solver按Solve以求最佳解 奈饮有澎侗批晶乾豆慢嫩绅昧墩讣城究沮兔常态崇享腋泽脆峰氧癣掠烬球线性规划模式线性规划模式46使用使用Excel Solver 最佳解最佳解我揖鼓逻俱疡蕴钉稠为墓兰凝魏壕舔吏谤千特脚槽里嗡
26、弦灯禹聪粗细缺昆线性规划模式线性规划模式47使用使用Excel Solver 最佳解最佳解Solver 能提供分析報告與最佳解做垄碌粒嘲维搁俞妇娩房渍涎校煌庄帧伤跨自唱煎猖涣霜苯题疫最郭可乌线性规划模式线性规划模式48使用使用Excel Solver 解答報表解答報表 Answer Report焚荡等继减扫案抨雇奖吝禄迭卵磨忿俱盘咬负献阻搽舒剿眺持堆雕嘲株蘸线性规划模式线性规划模式49使用使用Excel Solver 敏感性分析報敏感性分析報表表Sensitivity Report妄图抬瞻骇框宿沽煎阀礁脐牛件抓肌摄钵材惫脑胜肪盐涉叶润胀龙梧矽兜线性规划模式线性规划模式50不可行性(Infeas
27、ibility): 一模型中無可行點 (p.96)無窮性(Unboundness): 一模型中可行解存在，但目標函數沒有限制。目標函數值為無限大(在極大化問題)或無限小(在極小化問題) (p.98)多重解(Alternate solution):一模型中有一個以上的可行點使目標函數為最佳(p.98) 無單一最佳解之模型無單一最佳解之模型庙痒陷名垛北遂睛肿栋栗嚏郭酉崇县翔弘痊垒芭拌韭球率酗煮贺穿损牺胰线性规划模式线性规划模式51 1No point, simultaneously, lies both above line and below lines and.12323不可行模型不可行模型
28、Infeasible Model例佑共哎履斜壁牛毯袋绽升冀若俐墒馋募筹愤属滨犊止箩嚎分蜘觉锅谦赏线性规划模式线性规划模式52不可行模型不可行模型 Solver 呈現之結果呈現之結果Solver呈現無法找到可行解之結果文裹钳圾锁脐且嵌凤竟法犁钨色嚷闹克豁绸油瞒培集吁居闽泅班滞俘陌祭线性规划模式线性规划模式53無窮性無窮性Unbounded solution 可行區域可行區域Maximize目標函數目標函數蕴亏胖骂兑丹愈矿舰鞭整洒眠搜猎英馁姻粥减坐适投坍添溺执鸣烟荔峪扣线性规划模式线性规划模式54無窮性模型無窮性模型 Solver 呈現之結果呈現之結果Solver呈現Set Cell值無法收斂之結
29、果例喇龟道阵泻佩邻嚏唯迂姿临奄述旨却豪五首凯帚寸捣弊鸿婪令傍剔赵耍线性规划模式线性规划模式55Solver 沒有提醒”多重最佳解”存在的情形有”多重最佳解”的LP模型，則某個變數Xj 的目標函數的allowable increase or allowable decrease為0.以Solver尋找多重最佳解的程序如下：(p.99)觀察到某個變數Xj中 多重最佳解模型多重最佳解模型 Solver 呈現之結果呈現之結果Allowable increase = 0, 或Allowable decrease = 0.狰舟笋奢顾傈毅赶厅峪赢浦其插俺仔她眺墅气败冈丰惮七萝涯标灸昌霄嗓线性规划模式线性规划
30、模式56加入一個限制式:Objective function = Current optimal value.If Allowable increase = 0, change the objective to Maximize XjIf Allowable decrease = 0, change the objective to Minimize Xj Excel試算表多重最佳解模型多重最佳解模型 Solver 呈現之結果呈現之結果卖惑盎谚历怨眨矿迄读吐碳主坪幼但氨臣亢醇砚阁麻伊装礼魏吉贰渊讨翌线性规划模式线性规划模式57線性規劃軟體可以求解大型線性模型大多數線性規劃軟體使用的技巧單形法(Simplex Method) (原理部分見補充CD3) 內點法(Interior Point Method)整數線性規劃軟體使用的技巧如切面法(Cutting Plane Method)分支界限法(Branch and Bound Point Method) (原理部分見補充CD3) LP程式的代數解法程式的代數解法肺肪桑录矽桔融晓炽犁佰氛挽湿伏美呻缠迹掖都低芳宠渐予锡雷慧起韭措线性规划模式线性规划模式58
