簡捷法 簡捷法可用來找尋端點，並評估何者為最佳解。先考慮所有決策變數值皆為零的基本解，再算出是否有其他解的目標函數值較此點為佳。

Presentation on theme: "簡捷法 簡捷法可用來找尋端點，並評估何者為最佳解。先考慮所有決策變數值皆為零的基本解，再算出是否有其他解的目標函數值較此點為佳。"— Presentation transcript:

1 簡捷法 簡捷法可用來找尋端點，並評估何者為最佳解。先考慮所有決策變數值皆為零的基本解，再算出是否有其他解的目標函數值較此點為佳。
線性規劃問題若有最佳解，此解必定會落在可行區域的「端點」上。 5-1

2 範例說明 題目請見課本106-107 因不等式為小於等於，故於不等式左邊加入寬裕變數，即可將模型變成標準式。
Max Z = X1 + 4X2 + 0S1 + 0S2 (5.1) s.t. X1 + 5X2 + S1 = (5.2) 2X1 + 6X2 + S2 = 16 (5.3) X1, X2, S1, S2  0 (5.4) 5-2

3 專有名詞 基本解(basic solution) :標準式的線性規劃中包含n個變數與m(< n)個線性方程式；令n-m個變數為零，再解m個聯立方程式，求出剩餘m個變數值 基本可行解(basic feasible solutions)：滿足所有非負限制式的基本解 非基本變數(nonbasic variables) ：基本可行解中令其為０的變數．（ n-m個) 基本變數(basic variables) ：基本可行解中須求解的變數（＞＝０；m個） 基底（basis):所有基本變數的集合． 5-3

4 求解流程 補充 5-4

5 簡捷法運算步驟(1/2) 最大化問題(且限制式皆<=0)，其運算步驟：
將問題表示為線性規劃模型。 在每個限制式中加入寬裕變數，以表示成標準式。 構建最初的簡捷列表。 選擇於列 中具有最大正值的非基本變數為進入變數，將此變數所在的欄設為主軸欄。 5-5

6 簡捷法運算步驟(2/2) 對於每一列計算比值 / ，其中 > 0，j為主軸欄。選擇比值最大的列為主軸列，將此列所對應的變數設為離開變數。 執行基本列運算，將主軸欄轉換成單位欄，位於主軸列上者為1，其餘者為0。 執行最佳化檢驗。若所有欄之cj - zj  0，則已找到最佳解；否則，回覆到步驟4。 5-6

7 範例說明(1/5) 題目請見課本106-107 因不等式為小於等於，故於不等式左邊加入寬裕變數，即可將模型變成標準式。
Max Z = X1 + 4X2 + 0S1 + 0S2 (5.1) s.t. X1 + 5X2 + S1 = (5.2) 2X1 + 6X2 + S2 = 16 (5.3) X1, X2, S1, S2  0 (5.4) 5-7

8 範例說明(2/5) 求得一組基本解(basic solution) 令X1 =0，S2 = 0，則上述線性方程式變成：
我們得到線性系統的解如下， X1 = 0 X2 = 8/3 S1 = - 10/3 S2 = 0 此組解稱為是弘光線性規劃問題的一組基本解。 5-8

9 範例說明(3/5) 求基本解步驟：考慮一個以標準式表示的線性規劃問題，其中包含n個變數與m(< n)個線性方程式；令n-m個變數為零，再解m個聯立方程式，求出剩餘m個變數值。我們稱這n-m個設為零的變數為非基本變數另外m個變數則稱為基本變數。 5-9

10 範例說明(4/5) 基本可行解： 一組基本可行解是一組滿足所有非負限制式的基本解。 弘光問題中，令X1 =0，S2 = 0，求得X2 = 8/3，S1 = - 10/3，這組解並非一組基本可行解，因S1為負數，違反非負的限制。然而，若令X1 = 0，X2 = 0，可求得寬裕變數S1 = 10，S2 = 16，我們得到線性系統的解如下， X1 = 0 X2 = 0 S1 = 10 S2 = 16 5-10

11 範例說明(5/5) 此組解為一組基本可行解，因為所有變數值皆大於等於零，滿足非負的限制式。
簡捷法是一種重複的求解過程，從一組基本可行解(端點)到另一組基本可行解(端點)，直到求得最佳解為止。 5-11

12 列表式 標準式限制式有兩個特性 <特性一>須滿足以下條件：
在限制式中，那些包含基本變數的欄中只有其基本變數係數為1其餘基本變數的係數皆為0。 <特性二> 要求每個限制方程式的右側值皆為非負數，所得到的基本解為可行解。 若將n-m個非基本變數令為0，這m個基本變數值則等於這m個限制式的右側值。 倘若一個線性規劃問題滿足上述兩個特性，則稱其已表示為一列表式。 5-12

13 簡捷列表符號模式介紹(1/2) 介紹簡捷列表的一般表示，其符號如下： cj = 變數j的係數 bi = 限制式i的右側值
aij = 限制式i中第j個變數的係數 A = mn的矩陣，其構成元素為aij 5-13

14 簡捷列表符號模式介紹(2/2) c1 c2 … cn a11 a12 … a1n b1 a21 a22 … a2n b2 … … … …
… … … … am1 am2 … amn bm 因此，弘光問題的簡捷列表為： X1 X2 S1 S2 5-14

15 建立簡捷列表(1/5) 為改善目標值，其做法是將某一個非基本變數換成基本變數，而將目前某個基本變數換成非基本變數。 以弘光問題，表示如下：
X1 X2 S1 S2 Basis CB S S 5-15

16 建立簡捷列表(2/5) 另一組新的基本可行解來改善目標函數值是否可行？
在簡捷列表下方加上兩列：第一列標示為zj，表示當矩陣A的第j行所對應的變數移至基底，目標函數值的減少量；第二列標示為cj - zj，則表示當矩陣A的第j行所對應的變數移至基底，目標函數值的淨變化量。 5-16

17 建立簡捷列表(3/5) 介紹zj列值如何計算： 若X1 = 0變成1，改變時，若仍要滿足方程式成立，其餘變數中某些變數須同時改變
運用簡捷法時，只須改變基本變數即可。例如：第一個限制式X1 + 5X2 + S1 = 10 目前基本變數S1，若X2仍為非基本變數，其值仍為X2=0，若將X1 = 0變成X1 = 1，則S1必須減少1，變成S1 = 9。 5-17

18 建立簡捷列表(4/5) 欲計算zj列的值，則可以將CB欄位中的係數乘以矩陣A的第j行中同列的係數，然後再加總。如：
因目標函數中X1係數c1 = 1，c1 - z1 = = 1，這表示將變數X1移至基底，X1每增加一單位，目標函數值將增加1 5-18

19 建立簡捷列表(5/5) X2同理，建立初始簡捷列表如下： X1 X2 S1 S2 Basis CB 1 4 0 0
zj  目標函數值 cj - zj 目前可行解目標值(＝0)，其值0(10) + 0(16) = 0。 5-19

20 尋找下一個較佳解 (1/2) 進入基底的變數選擇法
從cj - zj 列中選擇一個可以使得目標函數值的單位改善量最大的變數。 若有多個變數，習慣選擇這些變數最左欄者。 離開基底的變數選擇法 若進入變數是位於簡捷列表的第j欄，對每一列i，若aij > 0則計算比值bi/aij 。若第i*列的比值最小，則將此列所對應的基本變數從基底移除。 若有多列有相同比值，則習慣上選擇這些列中位於最上列者所對應的基本變數。 5-20

21 尋找下一個較佳解 (2/2) 說明選擇變數的演算過程，在簡捷表最右側多增加了一欄來表示比值bi/aij 。 進入(主軸欄) 
X1 X2 S1 S bi / ai2 Basis CB S /5=2 離開(主軸列) S /6=8/3 zj cj - zj 5-21

22 計算下一個簡捷列表(1/4) 運用基本列運算，將簡捷列表轉換成同義的另一組限制方程式系統，基本列運算會改變變數的係數與右側值。
執行基本列運算的主要目的是要將簡捷列表變成一種容易找出新基本可行解的型式 5-22

23 計算下一個簡捷列表(2/4) 回顧弘光：進入(主軸欄)  X1 X2 S1 S2 Basis CB 1 4 0 0
5-23

24 計算下一個簡捷列表(3/4) 同理可得新簡捷表，如下： X1 X2 S1 S2 計算結果的意義 弘光問題最初之基本可行解為
Basis CB X2 4 1/5 1 1/ S2 0 4/ / 計算結果的意義 弘光問題最初之基本可行解為 X1 = 0、X2 = 0、S1 = 10、S2 = 16 簡捷法運算後，利潤變為8，基本可行解為：X1 = 0、X2 = 2、S1 = 0、S2 = 4 5-24

25 計算下一個簡捷列表(4/4) 最初基本可行解對應到點1，經變換運算後，沿X2方向移離原點，在可行區域內，最遠可至點 2 ，新的基本可行解即對應到此點。 5-25

26 往較佳解移動(1/4) 可否找到一組較佳基本可行解，必須重新計算zj與cj - zj，建立簡捷列表： X1 X2 S1 S2
Basis CB X2 4 1/5 1 1/ S2 0 4/ / zj 4/5 4 4/ cj - zj 1/ /5 0 依據進入基底的變數選擇法，選擇了X1為進入變數，因其c1 – z1 = 1/5是cj - zj 列中最大的正數。 5-26

27 往較佳解移動(2/4) 接著決定離開變數，由於進入變數是位於簡捷列表的第1欄，對每一列i，若ai1 > 0則計算比值bi/ai1，如下： 進入(主軸欄)  X1 X2 S1 S2 Basis CB X /5 1 1/ /(1/5)=10 S /5 0 -6/ /(4/5)=5 離開 zj 4/5 4 4/ cj - zj 1/ /5 0 因第2列比值最小，將此列所對應的基本變數從基底移除 5-27

28 往較佳解移動(3/4) 執行基本列運算步驟，可得簡捷列表： X1 X2 S1 S2 Basis CB 1 4 0 0
zj /2 1/4 9 cj - zj /2 -1/4 得基本可行解X1 = 5、X2 = 1、S1 = 0、S2 = 0 目標函數值為: Z = X1 + 4X2 = 1(5) + 4(1) = 9 5-28

29 往較佳解移動(4/4) 由於列cj - zj中的所有數皆非正數，則表示當矩陣的任一欄所對應的變數移至基底，目標函數值的淨變化量皆為非正值，
即無法增大目標函數值，因此這組解已經是最佳解，此時的最大利潤值為9。 5-29

30 最佳解條件 當簡捷列表中cj - zj列的所有數皆為0或負數時，則表示已經找到最佳解，即為基本可行解。 5-30

31 一般情況之簡捷列表(1/7) 題目請見課本p122-123
將題目模型變成標準式，即於小於等於不等式左邊加上寬裕變數，於大於等於不等式左邊減去剩餘變數，將模型變成標準式 之後加入新人工變數：a3 (0) X1 + 5X2 + S1 = 10 (5.10) 2X1 + 6X S2 = 16 (5.11) X1 + X S3 + a3 = 5 (5.12) 5-31

32 一般情況之簡捷列表(2/7) 若令X1 = X2 = S3 = 0，可得解：X1 = 0、X2 = 0、S1 = 10、S2 = 16、S3 = 0、a3 = 5 雖此解不是實際問題的可行解，確為可行解，可作為簡捷法運算的初始解，只要在得到最佳解之前將其移出基底，就不會違反實際問題的可行性。 5-32

33 一般情況之簡捷列表(3/7) 將其成本設為非常大正數，一般用M來表示。則目標函數為： Max X1 + 4X2 + 0S1 + 0S2 + 0S3 – Ma3 建立初始的簡捷列表 X1 X2 S1 S2 S3 a3 Basis CB M S  S a M zj M -M M -M -5M cj – zj 1+M 4+M M 0 5-33

34 一般情況之簡捷列表(4/7) 第一次主軸變換，進入變數為X2，離開變數為S1，運算結果如下：  X1 X2 S1 S2 S3 a3
Basis CB M X / / S / / a3 -M / /  zj M M M cj - zj M 5-34

35 一般情況之簡捷列表(5/7) 第二次主軸變換，進入變數為X1，離開變數為a3，運算結果如下：  X1 X2 S1 S2 S3 a3
Basis CB M X / /4 -1/4 5/4 S  X / /4 5/ /4 zj / /4 1/ /4 cj - zj / /4 5-35

36 一般情況之簡捷列表(6/7) 第三次主軸變換，進入變數為S3，離開變數為S2，運算結果如下： X1 X2 S1 S2 S3 a3
Basis CB M X /2 -1/ S X /4 5/ zj /2 1/ cj - zj /2 -1/ M 5-36

37 一般情況之簡捷列表(7/7) 因上表之cj - zj列上的值皆非正數，且人工變數a3已經移離基底，所以已得最佳解
倘若，線性規劃問題cj - zj列上的所有值皆非正數，仍有至少一個人工變數aj不為0，則此線性規劃問題無解。 5-37

38 HW 1, 2, 3, 4, 5, 7, 10, 12 5-38