作業研究 第二章 線性規劃 林吉仁 著 高立圖書公司出版.

Presentation on theme: "作業研究 第二章 線性規劃 林吉仁 著 高立圖書公司出版."— Presentation transcript:

1 作業研究 第二章 線性規劃 林吉仁 著 高立圖書公司出版

2 2-1 簡介 典型的線性規劃(LP)數學模式如下： 其他名詞：可行解、可行區、最佳 解、線性、 非線性 林吉仁著 目標函數 功能限制式
非負限制式 決策變數 其他名詞：可行解、可行區、最佳 解、線性、 非線性

3 2-2 圖解法 使用時機：LP問題只有兩個決策變數時 圖解法步驟： (1)在座標平面劃出所有限制式的“半平面”，
林吉仁著 2-2 圖解法 使用時機：LP問題只有兩個決策變數時 圖解法步驟： (1)在座標平面劃出所有限制式的“半平面”， 而所有半平面的交集即是可行區域 (2)設目標函數 Z=c1x+c2y ， 劃出梯度 Z=[c1, c2]的方向 (3)劃出垂直於 Z的平行線系 (4)平行線系沿Z方向(反方向)移動，與可行 區域最後接觸的點，即是Z產生最大值(最 小值)的地方。

4 林吉仁著 例題2-1

5 林吉仁著

6 線性規劃的一般性質 1. 可行區域可能是空集合、有界的 、無界的
林吉仁著 線性規劃的一般性質 1. 可行區域可能是空集合、有界的 、無界的 2.線性規劃的最佳解有四種可能情形： (1) 無解；(2) 恰有一個最佳解；(3) 有無限多個最佳解； (4) 目標無限值解 ( 屬於找不出最佳解 ) 3.( 頂點定理 ) 假設可行區域非空集合 (1)若可行區域有界，則最佳解必存在，且必可於頂點 找到最佳解 (2)若可行區域無界，則可能有最佳解或是目標無限值 解。若存在最佳解，則必可於頂點找到最佳解。 4. 若可行區域某頂點的Z值優於 ( 或不劣於 )所有鄰近 頂點的Z值，則該頂點即是最佳解，其Z值即最佳值

7 林吉仁著 LP最佳解可能情形

8 林吉仁著 例題2-2 設某公司有大、中兩型貨車，大型貨車上有20單位的冷藏空間，30單位的非冷藏空間；中型貨車上有20單位的冷藏空間，10單位的非冷藏空間。今有某商人需用160單位的冷藏空間，120單位的非冷藏空間，由台北運貨至高雄，問此公司應使用大型、中型貨車各若干輛，以使其汽油最節省。但已知大型貨車一趟需300加侖汽油，中型貨車一趟需200加侖汽油。

9 林吉仁著

10 林吉仁著 例題2-3

11 林吉仁著

12 林吉仁著 例題2-4 某工廠用三種原料甲、乙、丙，製造X、Y兩種成品 。每噸的X需要甲6噸，乙4噸，丙12噸，可得利潤為2萬元。每噸的Y，需要甲4噸，乙6噸，丙3噸，可得利潤6萬元。本月份購入原料甲、乙、丙各為60噸，根據這個來擬定生產目標，應該生產X種成品 x 噸，Y種成品 y 噸，才可得到最大利潤 p 萬元，求 x, y, p之值？

13 林吉仁著 解： 依題意建立線性規劃模式  沿 p=[2,6] 方向，p 愈右上移，p 值愈大。x=0,y=10 時 p 有最大值60

14 2-3單體法 (Simplex Method) 決策變數有三個以上時，不適用圖解法
林吉仁著 2-3單體法 (Simplex Method) 決策變數有三個以上時，不適用圖解法 單體法(Simplex Method)1947年由線性規劃之父G. B. Dantzig發展出來 單體法由原點出發往相鄰頂點前進，每次的頂點目標值必優於前一次的頂點，如此反覆進行，不須檢查所有頂點即可求得最佳解 單體法通常是在單體表中進行 使用單體法須先將LP問題化成“正規型”

15 化成“正規型”的步驟 1.檢查每一變數是否均有非負限制式
林吉仁著 化成“正規型”的步驟 1.檢查每一變數是否均有非負限制式 2.Max Z=f(x1,x2,…,xn)  Max Z f(x1,x2,…,xn) =0 3.功能限制式RHS是否均大於等於 0 4.功能限制式的關係符號， (1)為“”時，增一“+s”,s  0，且改為“=”號 (2)為“=”時，增一“r”,r  0，且目標左邊增“+Mr” (3)為“”時，增一個“u”，一個“+r”，u0，r  0 且改為“=”號，且目標左邊增加“+Mr” 5.填入單體表

16 其他要點 2.多個s時，可依序以s1,s2,…表之，r、u亦同 3.事實上，人工變數r=0
林吉仁著 其他要點 1.目標函數若有常數，移項時可將常數留在右邊。 2.多個s時，可依序以s1,s2,…表之，r、u亦同 3.事實上，人工變數r=0 4.莫忘每加入r，立即在正規目標函數左邊增“+Mr” 5. M在術語上稱為大 M(Big-M) 6.正規型除了非負限制式，關係符號應全為等號 又如果將正規型中人工變數的項全刪除，並使用原來的目標式，稱為等式型 (equation form) 7.正規型的解稱為擴充解。可行頂點的擴充解，稱為可行基解

17 林吉仁著 例題2-5 化為正規型、等式型 (1) (2)

18 林吉仁著 解： (1) (正規型) (等式型)

19 林吉仁著 (2) (正規型) (等式型)

20 單體法步驟 1. 將問題填入單體表中。取Z與各限制式中之si , ri 填入基變數欄。 2. 將起始單體表調整成適當型，此解稱為起始可行基解
林吉仁著 單體法步驟 1. 將問題填入單體表中。取Z與各限制式中之si , ri 填入基變數欄。 2. 將起始單體表調整成適當型，此解稱為起始可行基解 3. 最佳解檢定：若表中Z列的變數係數均0，則到步驟7.，否則到步驟4. 4. 選取基準行：以Z列變數係數的最負值欄為基準行，該行的變數為調入變數。當最負值不止一個時，可任取其一。

21 如果基準行元素均小於等於0，我們無法選出基準列，此時代表Z是無限值解，停止運算。
林吉仁著 5. 選取基準列：計算各列「右手常數除以基準行“正數”元素」，取此比率最小之列為基準列，該列之基變數為調出變數。此步驟是為了保持符合可行解檢定。基準行與基準列交集元素稱為基準元素 (pivot)。 如果基準行元素均小於等於0，我們無法選出基準列，此時代表Z是無限值解，停止運算。

22 6. 基變數的調整：利用「單體法的列運算」將基準行變成基準元素為1的單位行向量，並在基變數欄以調入變數取代調出變數。回到步驟3.。
林吉仁著 6. 基變數的調整：利用「單體法的列運算」將基準行變成基準元素為1的單位行向量，並在基變數欄以調入變數取代調出變數。回到步驟3.。 ※單體法的列運算有二： (1)基準列乘一數使基準元素為1。 (2)基準列乘一數加到另一列使基準行 ( 除基準元素外 ) 所有元素為0。 7. 停止運算。判讀最佳解。　　

23 林吉仁著 例題2-6 試以單體法解

24 林吉仁著 解： 化成正規型如下 填入單體表進行單體法

25 林吉仁著 當x1 = 150, x2 = 100, s1 = s2 =0 時， Z 有最大值2800

26 林吉仁著 例題2-7 解線性規劃問題

27 林吉仁著 解： 化成正規型如下 填入單體表進行單體法

28 故得 x = 4, y = 4, s1 = u2 = r2 = 0時,Z有最大值12 ( 注意：r2 = 0)
林吉仁著 故得 x = 4, y = 4, s1 = u2 = r2 = 0時,Z有最大值12 ( 注意：r2 = 0)

29 2-4目標函數、限制式的處理 1.目標函數的處理： (1) 目標函數是min 時，處理方式有兩種： (a) 修改單體法準則，改變的有
林吉仁著 2-4目標函數、限制式的處理 1.目標函數的處理： (1) 目標函數是min 時，處理方式有兩種： (a) 修改單體法準則，改變的有 「最佳解檢定」改成「Z係數均小於等於0」。 「選取基準行」改成「以Z列係數正的最大值欄為基準行」 (b)先將目標函數乘一負號，轉化為max，待求出最佳解再乘一負 號加以還原 (2) 當目標函數為 min max (f1, f2, , fk) 可化為線性表示法如右： 　 目標函數為 max min (f1, f2, , fk) 的問題，可用類似方式處理

30 2. 限制式的處理：通常是處理使變數均有非負限制式，使限制式為線性等。同時，盡量減少變數個數，以方便解題。
林吉仁著 2. 限制式的處理：通常是處理使變數均有非負限制式，使限制式為線性等。同時，盡量減少變數個數，以方便解題。

31 林吉仁著 3. 功能限制式右手常數的處理：若右手常數為負值，只要全式乘一負號即可。 課本中尚有許多單體法例題請多練習

32 2-5單體法解的特殊情形 一般情形： 非基變數值為0，而基變數值不為0。當基變數數值為0，即產生了退化。
林吉仁著 2-5單體法解的特殊情形 一般情形： 非基變數值為0，而基變數值不為0。當基變數數值為0，即產生了退化。 基變數行向量在目標列的係數為0，而非基變數對應的應不為0。若非基變數在目標列係數也為0，即可能有了多重最佳解。 當無基準行時，則停止運算並依人工變數是否為0，判定無解或已找出最佳解。 當有基準行(max目標列係數有負值者)，卻無基準列時，停止運算。而目標則是無限值解。

33 林吉仁著 2-5-1多重最佳基解 在最佳解的單體表，若有非基變數的行向量在目標列的元素為0，且若以此非基變數為調入變數，也存在調出變數，則此線性規劃問題存在多重最佳基解。若就前面所說的方式變換其基變數，仍會得到相同的 Z 值。事實上此兩最佳基解之間的線性組合均是最佳解。

34 林吉仁著 例題2-12 線性規劃問題

35 林吉仁著 最佳解的單體表如下

36 2-5-2退化解 退化是指有基變數值為0 退化的產生有兩種可能： (1)在起始時，正規型中有RHS為0
林吉仁著 2-5-2退化解 退化是指有基變數值為0 退化的產生有兩種可能： (1)在起始時，正規型中有RHS為0 (2)在運算過程中，當比率最小值不唯一時， 在下一小表中，必會產生退化 遇到退化時，仍按一般方式運算，可能產生循環 (cycling) 現象，但機會很小。

37 2-5-3無限值解 在無大M單體表的演算過程中，存在了基準行，但，不存在基準列，則此問題是無限值解 大 M 法時，若有基準行不存在基準列，
林吉仁著 2-5-3無限值解 在無大M單體表的演算過程中，存在了基準行，但，不存在基準列，則此問題是無限值解 大 M 法時，若有基準行不存在基準列， (1)若所有人工變數均為0，則本題為無限值解。 (2)若有人工變數不為0，而基準行是對應目標列元素最負值，則本題無可行解；若基準行不是對應目標列元素最負值，則改換基準行繼續作下去

38 林吉仁著 例題2-15 解

39 林吉仁著 解： ∵ 尚未達最佳解，但若選 x1 為調入變數，不存在調出變數， ∴ 為無限值解。

40 林吉仁著 2-5-4 無　解 當所有限制式的交集區域為空集合，即不存在任何可行解時，當然就不存在最佳解。而表現在單體表中的即目標列變數係數已均大於等於0，停止運算了，但卻有人工變數 ri 不為0，則此問題無解。

41 2-6雙階法 (Two-phase Method)
林吉仁著 2-6雙階法 (Two-phase Method) 雙階法是大 M法之外，是處理人工變數的另一種方法 雙階法步驟： (1)以min Q =  ri 為第一階段的目標函數，原目標函數視為限制式 ( 但不可為基準列 ) (2)第一階段完成，若目標值 　　 (a) Q  0，本題無解，停止運算。 　 　(b) Q = 0，進入第二階段。刪去 Q 與 ri 相關 之列、行，利用原目標函數對應之列為 目標列，繼續往下運算。

42 林吉仁著 例題2-16 以雙階法求解

43 林吉仁著 解： 化為雙階法正規型如下

44 林吉仁著 故 x1 = 0, x2 = 0, x3 = 4 時，Z 有最大值 8

45 林吉仁著 例題2-17 以雙階法求解

46 林吉仁著 解： 化為雙階法正規型如下

47 林吉仁著 ∵ Q = 4  0 ∴ 本題無可行解。

48 林吉仁著 2-7存在起始可行基變數 當線性規劃問題的 = 號、 號功能限制式已存有變數可作為起始基變數時，則以單體法求解可不須引入人工變數，以節省運算。但勿忘先調整起始單體表為適當型。 (例題請參考課本)

49 2-8線性規劃的基本假設 線性規劃的基本假設有四： 1.成比例性：投入與產出的比例是固定的 2.可加性：變數代表的活動互相獨立
林吉仁著 2-8線性規劃的基本假設 線性規劃的基本假設有四： 1.成比例性：投入與產出的比例是固定的 2.可加性：變數代表的活動互相獨立 3.確定性：模式中的係數都是確定的數值 4.可分割性：變數可以是0.5、3/2等非整數

50 2-9單體法效率的影響因素 單體法程式效率受下列因素影響： 1.功能限制式個數：求解時間約與功能限制式個數的三次方成正比。
林吉仁著 2-9單體法效率的影響因素 單體法程式效率受下列因素影響： 1.功能限制式個數：求解時間約與功能限制式個數的三次方成正比。 2.變數的個數：變數個數若增為2倍，求解時間增加略少於2倍。 3.功能限制式係數的密度：密度低可加速解題速度。