Fundamental of optimization Models：Linear Programming
報告者：董光洋
2003/3/11
Overview
－linear programming modeling examples
用簡單的例子，來呈現LP的概念。
－properties of linear programming models
探討LP的特性及應用在supply chain planning上的問題。
－Interpreting an optimal linear programming solution
用LP的單純法達成經濟上的最佳解，及算出邊際成本。
－multiple objective optimization
LP方法可以靠描繪決解方法效率區域來衡量衝突目標間trade-off的關係。
－stochastic programming
stochastic programming推測規畫是應用於對面需求不確定時，如何決定產品和存貨的規畫。
LP Modeling Examples
LP的模式是為了解決在複雜系統中，對於經濟活動因為資源不足而需要去作optimize的分配，以將有限資源(scarce resource)作最佳化的使用。
Example (一)
Ajax computer公司生產三種電腦
1、個人電腦 －Alpha －售價350
2、Notebook －Bata －售價470
3、Workstation－Gamma －售價610
A生產線可以有120小時供Alpha及Bata電腦
作測試。
B生產線可以有48小時供Gamma電腦作測試。
共有2000小時的員工工作時數可以分配給這三種電腦作組裝，Alpha需要10小時，Bata需要15小時， Gamma需要20小時。
Example (二)
MA=Alpha電腦在一星期中被測試及組裝完成，為可售出的電腦數目。
MB=Beta電腦在一星期中被測試及組裝完成，為可售出的電腦數目。
MC=Gamma電腦在一星期中被測試及組裝完成，為可售出的電腦數目。
Example (三)
Objective function(目標函數)
Maximize=350MA+470MB+610MC
Constraint(限制式)
MA+MB <= 120(A線測試產能)
MC<= 48(B線測試產能)
10MA+15MB+20MC<=2000(員工最大可用時數)
MA>=0，MB>=0，MC>=0(nonnegative)
Example (四)
圖解
利用端點值可以找出最佳解
Example (一)
A線外包測試每小時40元，但不限制數量。
且需要雇用額外的測試員工每小時30元。
EA=外包測試之小時數
EL=雇用員工的工作時數
Maximize=350MA+470MB+610MC-40EA-30EL
-EA+MA+MB <= 120
MC <= 48
-EL+10MA+15MB+20MC<=2000
MA>=0，MB>=0，MC>=0，EA>=0，EL>=0
Example (二)
「buying low and selling high」低買高賣會形成arbitrage(套利)現象。
以上例而言，最佳化會出現以下問題：
Alpha電腦不可能無限制地售出。
A線測試的產能不可能無限制增加。
因此就上例而言，此題為unbound(無窮解)。
Example (一)
Multiperiod Resource Allocation Model。
生產多少產品？
賣多少產品？
多少產品變存貨？
Example (二)
week1
Example (三)
week2
Example (四)
week3
Example (五)
week4
Example (一)
Network Model是一種Transportation Model。
Example (二)
下表是從工廠及倉庫運送到8個Market的成本，及各個Market的Alpha電腦需求量
請問各位同學，目標函數及限制式該怎麼列？
Example (三)
Min 14XP1+24XP2+21XP3+20XP4++19XP6+17XP7+30XP8+24XW1+15XW2+28XW3+20XW4+++28XW8
Supply constraints
XP1+XP2+XP3+XP4+XP5+XP6+XP7+XP8<=100
XW1+XW2+XW3+XW4+XW5+XW6+XW7+XW8<=45
Demand Constraints
XP1+XW1=22
XP2+XW2=14
XP3+XW3=18
XP4+XW4=17
XP5+XW5=15
XP6+XW6=13
XP7+XW7=15
XP8+XW8=20
Properties of Linear Programming Models
Linearity
Separability and additivity
Indivisibility and continuity
Single objective function
Data known with certainty
Linearity(線性)
By linear we mean that the unit revenue , unit cost, and unit resource utilization are constant for all values of the associated decision variable.
Separability and additivity
(可分性及可加性)
By separable, we mean that the net profit contribution of Alphas , and its resource utilization , is measured separately from , or independently of , the net profit contributions and resource utilizations of the other products.
By additive, we mean that separate effects can be accumulated simply by adding them up.
Indivisibility and continuity
(不可分割性及連續性)
Optimizing a linear programming model produces decisions that can take on numerical values along the continuum of real numbers.
Single objective function
(單一目標函數)
以Ajax電腦公司為例，以增加收入(maximize net revenues)為主要的目標函數。
因為多重目標會牽涉到不同目標間trade-off關係，在後面的節會提到。
Data known with certainty
(資料的確定性)
在發展LP時資料的確定性是相當重要的假設。→假設公司未來的成本、產能…必需確定已知。
以下幾種方式可以來減少未來的不確定性：
敏感度分析(靠設參數來測試敏感度)
發展多種方案(管理者需對未來主要的變化作瞭解)
－Interpreting an optimal linear programming solution
經濟解釋(economic interpretation)之所以重要因為能提供以下幾點：
Useful information for valuing resources and attributing costs to requirements and, in general, explaining why an optimal solution is optimal.
The underpainning for sensitivity and parametric analysis of model data.
The algorithmic basis for applying the simplex method and linear programming in a flexible manner to the optimization of large and complex models, including those that are not linear programming models.
Shadow Prices(陰影價格)
Shadow price is defined as the change in the optimal value of the objective function if the right-hand side of the constraint is increased by one unit.
Z- 350MA-470MB-610MC =0
MA+MB+ s1 =120
MC+ s2 =48
10MA+15MB+ 20MC+ s3 =2000
Z=
單純法
Reduced Cost coefficients
Reduced cost of MB=
470-(45)(1)-(0)(0)-()(15)=
The interpretation is that the objective function would decrease by for every Beta computer that Ajax would produce.
This coefficient,which is called the reduce cost of MB.
目標函數MB的係數
寬鬆變數S1的係數
限制式MB的係數
寬鬆變數S3的係數
Dual linear programming Model
Example
Maximize D=120PA+48PC+2000PL
Subject to PA +10PL>=350
PA +15PL>=470
PC +20PL>=610
PA>=0,PC>=0,PL>=0
目標函數MA的係數
目標函數MB的係數
目標函數MC的係數
第一項限制式的右手邊常數
第二項限制式的右手邊常數
第三項限制式的右手邊常數
Parametric and Sensitivity Analysis
Parametric and Sensitivity Analysis
In summary, shadow prices indicate how the optimal objective function value will change if an element of the right-hand side of an LP model is increased (decreased) by a small amount.
Sensitivity analysis answers the question：What is the range on an in individual parameter of an LP model in which an optimal solution remains optimal if all other parameters remain fixed at their given values？
－multiple objective optimization
Goal constraint
MA+MB-MC<=Q
－stochastic programming
An extension of linear and mixed integer programming, called stochastic programming, is an attractive option for strategic planning because it allow the decision maker to explicitly analyze uncertainties and control risks.
Week1
Week2–scenario(1)
Week2–scenario(2)
Week2–scenario(3)
