线性规划与整数规划模式Linear and Integer Programming.ppt

1 線性規劃與整數規劃模式LinearandIntegerProgrammingModels Chapter2 2 線性規劃模型 LinearProgrammingmodel 是在一組 線性 的限制式 asetoflinearconstraints 之下 尋找極大化 maximize 或極小化 minimize 一個特定的目標函數 objectivefunction 線性規劃模型由下列三個部分組成 一組決策變數 Asetofdecisionvariables 一個特定的目標函數 Anobjectivefunction 一組 線性 的限制式 Asetofconstraints 2 1線性規劃簡介IntroductiontoLinearProgramming 3 線性規劃簡介IntroductiontoLinearProgramming 線性規劃重要性許多現實問題本身就適用線性規劃模型已存在許多有效的求解技巧已存在許多著名的成功應用實例ManufacturingMarketingFinance investment AdvertisingAgriculture 4 線性規劃重要性線性規劃套裝軟體之所產生的結果提供有用的 如果 則 what if 的分析資訊 線性規劃簡介IntroductiontoLinearProgramming 5 線性規劃模型之假設AssumptionsforLinearProgramming 參數具有 確定性 certainty 目標函數與限制式符合 固定規模報酬 之假設 constantreturnstoscale 疊加性 之假設 決策變數間沒有互動性 即某函數之總價值只能藉由線性加總求得 連續性 Continuity 之假設變數值必須再某一個可行範圍內 1單位產品 4 3Hrs生產 500單位產品 4 500 2000 3 500 1 500Hrs生產 6 典型範例TheGalaxyIndustriesProductionProblem Galaxy生產兩種玩具模型 宇宙光SpaceRay 射擊手Zapper 資源限制 Resources 1000磅特殊塑膠化合物 specialplastic 每週40小時生產時間 40hrsofproductiontimeperweek 7 市場需求 Marketingrequirement 每週總產量至多700打SpaceRays週產量不能過Zappers350打以上 技術係數 Technologicalinputs Table2 2 SpaceRays每打需要2pounds塑膠與3分鐘生產時間Zappers每打需要1pound塑膠與4分鐘生產時間 典型範例TheGalaxyIndustriesProductionProblem 8 生產需求 SpaceRay每打利潤 profit 8 Zappers每打利潤 profit 5盡量多生產SpaceRay 剩餘資源再生產Zapper 目前生產計畫 SpaceRays 450dozenZapper 100dozenProfit 4100perweek 典型範例TheGalaxyIndustriesProductionProblem 9 管理是尋求一個生產排程為了是能增加公司的利潤Managementisseekingaproductionschedulethatwillincreasethecompany sprofit 10 線性規劃模式可以提供一種深入與聰明之方法來解決此問題Alinearprogrammingmodelcanprovideaninsightandanintelligentsolutiontothisproblem 11 決策變數 Decisionsvariables X1 每週生產的SpaceRays打數X2 每週生產的Zappers打數目標函數 ObjectiveFunction 極大化每週總利潤 典型範例線性規劃模式TheGalaxyLinearProgrammingModel 12 Max8X1 5X2 每週總利潤 subjectto2X1 1X2 1000 塑膠原料 Plastic 3X1 4X2 2400 生產時間 ProductionTime X1 X2 700 最大產量 Totalproduction X1 X2 350 組合 Xj 0 j 1 2 非負值 Nonnegativity 典型範例線性規劃模式TheGalaxyLinearProgrammingModel 13 2 3線性規劃模式圖形分析GraphicalAnalysisofLinearProgramming 滿足模型全部限制式的所有點集合稱為Thesetofallpointsthatsatisfyalltheconstraintsofthemodeliscalleda 可行區域FEASIBLEREGION 14 圖形表示法 graphicalpresentation 所有限制式 alltheconstraints 目標函數 objectivefunction 可行點 threetypesoffeasiblepoints 15 Thenon negativityconstraints 非負限制式 X2 X1 圖形分析 可行區域GraphicalAnalysis theFeasibleRegion 16 1000 500 Feasible X2 Infeasible ProductionTime限制式3X1 4X2 2400 Totalproduction限制式X1 X2 700 多餘 500 700 X1 700 圖形分析 可行區域GraphicalAnalysis theFeasibleRegion 17 1000 500 Feasible X2 Infeasible ProductionTime限制式3X1 4X2 2400 Totalproduction限制式X1 X2 700 多餘 500 700 Mix限制式X1 X2 350 Plastic限制式2X1 X2 1000 X1 700 圖形分析 可行區域 p 67 68 GraphicalAnalysis theFeasibleRegion 可行點 feasiblepoints 有三種 內部點Interiorpoints 邊界點Boundarypoints 端點Extremepoints 18 以圖形求解是為了尋求最佳解SolvingGraphicallyforanOptimalSolution 19 尋求最佳解圖解程序 p 71 Thesearchforanoptimalsolution 由任一個profit開始 sayprofit 1 250 往利潤增加方向移動increasetheprofit ifpossible 持續平行移動到無法增加為止continueuntilitbecomesinfeasible OptimalProfit 4360 500 700 1000 500 X2 X1 紅色線段Profit 1250 20 最佳解 p 69 Summaryoftheoptimalsolution SpaceRaysX1 320dozenZappersX2 360dozenProfitZ 4360此最佳解使用了所有的塑膠原料 plastic 與生產時間 productionhours 2X1 1X2 1000 塑膠原料 Plastic 3X1 4X2 2400 生產時間 ProductionTime Excel試算表 束縛方程式 BindingConstraints 等式被滿足之限制式 21 最佳解 p 70 71 Summaryoftheoptimalsolution 總產量 Totalproduction 680打 not700打 SpaceRays產量只超過Zappers40打 非束縛方程式 Non BindingConstraints 最佳點不在其等式之限制式寬鬆 Slack 限制式右邊與左邊的差額 代表資源的剩餘數量 X1 X2 680 700 總產量 X1 X2 40 350 產品組合 總產量有700 680 20的寬鬆產品組合有350 40 390的寬鬆 22 若一個線性規劃問題有一組最佳解 此最佳解一定發生在 端點 上 端點 最佳解之候選人 True False 兩個束縛方程式的交點形成一個 端點 或 角點 端點與最佳解 p 72 Extremepointsandoptimalsolutions 端點 可行區域的角點 2X1 X2 1000X1 X2 350之解 450 100 320 360 2X1 X2 10003X1 4X2 2400之解 0 600 3X1 4X2 2400X1 0之解 23 若多重最佳解存在 則目標函數必定平行其中一個限制式 多重最佳解Multipleoptimalsolutions 多重最佳解之任何加權平均值亦為一組最佳解 X1 350 0 最佳解1 X2 0 600 最佳解2 X X1 1 X2 0 1 亦為最佳解 目標函數Z 24 2 4最佳解敏感性分析之角色TheRoleofSensitivityAnalysisoftheOptimalSolution p 75 輸入參數之變動對於最佳解之敏感度為何 從事敏感性分析之原因 輸入參數可能只是估計值或最佳估計值模型建立在一個動態環境 因此有些參數可能變動 如果 會 What if 分析可以提供經濟地與作業地資訊 25 最佳範圍 RangeofOptimality p 76 當其他因素保持不變時 在不改變最佳解之情況下 目標函數某係數可以變動多少 p 77 最佳解將不會改變 若目標函數係數仍在最佳範圍內不改變其他輸入參數目標函數某係數乘上一個非零正數 則目標函數會改變 1 目標函數係數之敏感性分析SensitivityAnalysisofObjectiveFunctionCoefficients 26 600 1000 500 800 X2 X1 Max8X1 5X2 Max4X1 5X2 Max3 75X1 5X2 Max2X1 5X2 目標函數係數之敏感性分析SensitivityAnalysisofObjectiveFunctionCoefficients 最佳解仍為 320 360 320 360 C1係數 2 最佳解為 0 600 而 320 360 不再是最佳解 0 600 減少C1係數由8 3 75 27 600 1000 400 600 800 X2 X1 Max8X1 5X2 Max3 75X1 5X2 Max10X1 5X2 C1係數的最佳範圍 3 75 10 目標函數係數之敏感性分析SensitivityAnalysisofObjectiveFunctionCoefficients 增加C1係數 由8 10最佳解仍包含 320 360 320 360 同理 C2係數的最佳範圍 4 10 67 Canyoufindit 28 一個變數Xj 0的縮減成本RCj為目標函數係數需要增加量的負值 DZj 使得最佳解中該變數為正數 Xj 0 縮減成本RCj為此變數Xj每增加一單位 DXj 1 目標函數會改變的值 C1 2X 0 600 X1 0 C1 3 75X 320 360 X1 320 0 RC1 Z1 3 75 2 1 75 縮減成本Reducedcost p 78 29 600 1000 500 800 X2 X1 Max3 75X1 5X2 Max2X1 5X2 目標函數係數之敏感性分析縮減成本 p 79 1 599 25 Z 2998 25 0 600 Z 3000 X1 1 X1 1 由X1 0 X1 1 Z 2998 25 3000 1 75 RC1 1 75 30 問題 若其他參數不變之前提下 若右手值變動一個單位 對於目標函數之最佳解有何影響 多少變動單位 增加或減少 可以保持目前最佳解 2 右手邊數值之敏感性分析 p 78 SensitivityAnalysisofRight HandSideValues 31 發現 任意變動束縛函數 BindingConstraints 之右手值 都會改變目前最佳解非束縛函數 Non BindingConstraints 之右手值 當變動數量少於寬鬆 slack 或剩餘 surplus 量時 都不會改變目前最佳解此結果可以由影子價格 ShadowPrice 來解釋 右手邊數值之敏感性分析SensitivityAnalysisofRight HandSideValues 32 影子價格ShadowPrices p 80 若其他輸入參數不變之前提下 限制式的影子價格是當其對應的右手值增加一個單位時 對最佳目標函數值的變動量 33 1000 500 X2 X1 500 2X1 1x2 1000 最佳解由 320 360 320 8 359 4 2X1 1x2 1001 當右手值增加 例如由1000 1001 則可行區域擴大 影子價格ShadowPrice 圖形表示graphicaldemonstration Shadowprice 4363 40 4360 00 3 40 34 可行性範圍RangeofFeasibility p 81 若其他輸入參數不變之前提下右手值的可行性範圍是影子價格依然不變的右手值可以變動的範圍 在可行性範圍內 目標函數之改變量Changeinobjectivevalue 影價Shadowprice 右手值變量Changeintherighthandsidevalue 35 塑膠的可行性範圍RangeofFeasibility p 81 1000 500 X2 X1 500 2X1 1x2 1000 塑膠原料的數量可以增加到一個新限制式成為Binding為止 此處為不可行解 Productiontime限制式 TotalProduction限制式X1 X2 700 36 塑膠的可行性範圍RangeofFeasibility 1000 500 X2 X1 600 Productiontime限制式3X1 4X2 2400 請注意看 當塑膠數量增加時最佳解的變化 TotalProduction限制式X1 X2 700 塑膠的可行性範圍上限 2X1 1X2 2 400 300 1100 X1 X2 7003X1 4X2 2400之解X 400 300 為最佳解 2X1 1x2 1000 37 塑膠的可行性範圍RangeofFeasibility 1000 500 X2 X1 600 Plastic限制式2X1 1X2 1000 請注意看 當塑膠數量減少時最佳解的變化 3X1 4X2 2400X1 0之解X 0 600 為最佳解 塑膠的可行性範圍下限 2X1 1X2 2 0 1 600 600 Productiontime限制式3X1 4X2 2400 38 已投入成本 Sunkcosts 未被包括在目標函數係數之計算當中的資源成本 ShadowPrice為該資源額外一單位的價值淨利潤可以將已投入成本 3800由目標函數值中扣除 影子價格的正確解釋Thecorrectinterpretationofshadowprices p 83 1000磅塑膠每磅 3 TotalCost 3000ProductionTime 20 hr TotalCost 20 40 800不管一週實際使用多少塑膠與ProductionTime 3000 800 3800都必須支付 故為已投入成本 39 已包括成本 Includedcosts 被包括在目標函數係數之計算當中的資源成本 ShadowPrice為高於該資源之現有單位價值之額外的價值見p 84表格2 5說明 影子價格的正確解釋Thecorrectinterpretationofshadowprices p 83 塑膠每磅 3 塑膠影價每磅 3 4 管理者願意為額外塑膠磅數多支付 6 8 已包括成本 ProductionTime 0 33 min or 20 hr ProductionTime影價每分鐘 0 4 管理者願意為額外ProductionTime多支付 0 73 40 其他後最佳性變動 p 84 OtherPost OptimalityChanges 加入一個新限制式 Additionofaconstraint 刪除一個限制式 Deletionofaconstraint 決定最佳解是否滿足此限制式Yes thesolutionisstilloptimalNo re solvetheproblem thenewobjectivefunctionisworsethantheoriginalone 決定刪除的限制式是否為束縛限制式Yes re solvetheproblem thenewobjectivefunctionisbetterthantheoriginalone No thesolutionisstilloptimal 41 其他後最佳性變動 p 84 OtherPost OptimalityChanges 刪除變數 Deletionofavariable 增加變數 Additionofavariable 考慮淨邊際利潤 NetMarginalProfit 決定被刪除變數在最佳解中是否為0Yes thesolutionisstilloptimalNo re solvetheproblem thenewobjectivefunctionisworsethantheoriginalone 42 其他後最佳性變動 p 85 OtherPost OptimalityChanges 範例 X3 新產品大水槍產量每一個大水槍需3lb塑膠與5min生產時間每打利潤 10 Max8X1 5X2 10X3 每週總利潤 subjectto2X1 1X2 3X3 1000 塑膠原料 Plastic ShadowPrice 3 4 3X1 4X2 5X3 2400 生產時間 ProductionTime SP 0 4 X1 X2 X3 700 最大產量 Totalproduction SP 0 X1 X2 350 組合 SP 0 Xj 0 j 1 2 3 非負值 Nonnegativity 淨邊際利潤 10 3 4 3 0 4 5 0 1 0 0 2 2 0 大水槍不具生產價值 X 320 360 0 仍為最佳解 43 其他後最佳性變動 p 85 OtherPost OptimalityChanges 左手係數的變動 Changesintheleft handsidecoefficients 44 2 5使用ExcelSolver尋找最佳解與分析結果 點選Galaxy xls 可見輸入試算表點選工具 規劃求解 Solver 可見下列對話視窗 45 使用ExcelSolver 點選Galaxy xls 可見輸入試算表 D 7 D 10 F 7 F 10 46 點選Galaxy xls 可見輸入試算表 D 7 D 10 F 7 F 10 ByChangingcells B 4 C 4 SetTargetcell D 6 使用ExcelSolver 按Solve以求最佳解 47 使用ExcelSolver 最佳解 48 使用ExcelSolver 最佳解 Solver能提供分析報告與最佳解 49 使用ExcelSolver 解答報表AnswerReport 50 使用ExcelSolver 敏感性分析報表SensitivityReport 51 不可行性 Infeasibility 一模型中無可行點 p 96 無窮性 Unboundness 一模型中可行解存在 但目標函數沒有限制 目標函數值為無限大 在極大化問題 或無限小 在極小化問題 p 98 多重解 Alternatesolution 一模型中有一個以上的可行點使目標函數為最佳 p 98 無單一最佳解之模型 52 不可行模型InfeasibleModel 53 不可行模型Solver呈現之結果 Solver呈現無法找到可行解之結果 54 無窮性Unboundedsolution 可行區域 55 無窮性模型Solver呈現之結果 Solver呈現SetCell值無法收斂之結果 56 Solver沒有提醒 多重最佳解 存在的情形有 多重最佳解 的LP模型 則某個變數Xj的目標函數的allowableincreaseorallowabledecrease為0 以Solver尋找多重最佳解的程序如下 p 99 觀察到某個變數Xj中 多重最佳解模型Solver呈現之結果 Allowableincrease 0 或Allowabledecrease 0 57 加入一個限制式 Objectivefunction Currentoptimalvalue IfAllowablein