第6章 線性規劃：單形法 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.

Presentation on theme: "第6章 線性規劃：單形法 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted."— Presentation transcript:

1 第6章 線性規劃：單形法 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.

2 第6章 線性規劃：單形法 6.1 單形法之代數原理 6.2 表格型 6.3 建立初始單形表 6.4 解的改進 6.5 計算下一個表
6.6 表格型：一般情形 6.7 解極小化問題 6.8 特殊情形 第6章 線性規劃：單形法 第243頁

3 6.1 單形法之代數原理 解線性規劃最常用的代數方法叫做單形法(simplex method)。用這個方法寫成的線性規劃軟體，可以解包含上千個變數與限制式的問題。 第6章 線性規劃：單形法 第244頁

4 6.1 單形法之代數原理 首先，我們介紹用來說明單形法所用的例題。海德工業進口用來組裝兩款個人電腦的電子零件：一種是桌上型；另一種是為攜帶型。 桌上型電腦每件利潤50美元，攜帶型電腦每台40美元。下一週可用組裝工時不超過150小時，每台桌上型電腦需3小時的組裝時間，攜帶型需5小時。另外，海德公司目前只有20台攜帶型電腦的顯示器存貨，所以攜帶型電腦最多只能組裝20台。而且只有300平方呎的倉儲空間可儲存新製成品。每台桌上型需8平方呎的儲存空間，每台攜帶型需5平方呎。 第6章 線性規劃：單形法 第 頁

5 6.1 單形法之代數原理 使用以下的決策變數： x1 = 桌上型組裝台數 x2 = 攜帶型組裝台數 加上寬鬆變數可以得到問題的標準型：
第6章 線性規劃：單形法 第245頁

6 6.1 單形法之代數原理-單形法的代數性質 單形法可看成是一種代數方法，目的在找出此聯立方程系統的最佳解答。
就上一個例子而言，所謂的最佳解就是(6.2)式至(6.4)式的解，而能使目標函數式(6.1)的值為最大，且滿足非負限制式(6.5)的解。 第6章 線性規劃：單形法 第245頁

7 6.1 單形法之代數原理-找出基本解 以上的解稱為海德線性規劃問題的基本解(basic solution)。為了說明求基本解的一般步驟，考慮總共含有n個變數、m個線性方程式的標準線性規劃問題，n大於m。 要找基本解，先令n–m個變數為零，再解剩下的m個變數的m個線性方程式。 就海德問題而言，可以令任意兩個變數為零，再解剩下的3個變數的3個線性方程式。 n-m個被令為零的變數為非基本變數(nonbasic variables)，其餘的m個變數為基本變數(basic variables)。 第6章 線性規劃：單形法 第246頁

8 6.1 單形法之代數原理-基本可行解 基本可行解(basic feasible solution)是一個可以滿足非負限制條件的基本解。
點～是基本可行解 點～則是不可行的基本解 在所有極點中有一個最佳的基本可行解。單形法是一個不斷重複的求解過程，從一個基本可行解（極點）移動到另一個，一直到找到最佳解為止。 第6章 線性規劃：單形法 第247頁

9 6.1 單形法之代數原理-基本可行解 第6章 線性規劃：單形法 第248頁

10 6.2 表格型 第一個特性： 對每個限制式而言，m 個基本變數中只能有一個係數是1，而其他基本變數在此限制式的係數均為0。
每個基本變數的係數，只能在一個限制式中是1。 第二個特性：要求限制式的右側值為非負值。 如果線性規劃問題滿足以上兩個特性，就稱為表格型(tableau form)。 第6章 線性規劃：單形法 第249頁

11 6.3 建立初始單形表 初始單形表包含線性規劃表格型的所有係數 cj = 變數 j 的目標函數係數 bi = 限制式 i 的右側值
aij = 限制式 i 中變數 j 的係數 將初始單形表的這一部分寫成： 第6章 線性規劃：單形法 第 頁

12 6.3 建立初始單形表 海德問題 所對應的行將只有一個。這種行稱為單位行(unit columns)或單位向量(unit vectors)。
第6章 線性規劃：單形法 第250頁

13 6.3 建立初始單形表 第一列標示zj，代表把A矩陣第j行的變數的1單位帶進基底時，目標函數將減少的值。第二列標示cj - zj，代表把A矩陣中第j行的變數的1單位帶進基底後，目標函數的淨改變量，cj - zj列為淨評估列(net evaluation row)。 第6章 線性規劃：單形法 第 頁

14 6.4 解的改進 單形法藉由選擇一個非基本變數去替換目前的基本變數，從一個基本可行解移到另一個基本可行解。這種從一個基本可行解移到另一個基本可行解的過程，稱為迭代(iteration)。 選擇新變數進入基底的判定準則：由淨評估列(cj - zj) 中，選擇每增加一個單位，能使目標函數的單位改善程度最大者為新進入的基底變數，當數值相同時，選擇最左邊的。 自目前基底移出一個變數的判定準則（最小比率測試）：假設進入的基本變數來自單形表 A 矩陣的第 j 行，對每一列 i，計算每個 aij > 0的 bi /aij 比值，最小的比值所對應的基本變數就離開基底。如果有兩個比值相同，就選較上面一列。 第6章 線性規劃：單形法 第 頁

15 6.4 解的改進 圈起來的項為樞紐項(pivot element)，包含樞紐項的行及列則分別稱為樞紐行(pivot column)及樞紐列(pivot row)。 第6章 線性規劃：單形法 第254頁

16 6.5 計算下一個表 轉變單形表，但依然能代表相同限制式體系的方法是利用基本列運算(elementary row operations)。
基本列運算法： 將任何列（方程式）乘以一個非零值。 將任何一列（方程式）乘以某個數值（可為正或負值）後，加到另一列。 基本列運算運用到線性聯立方程式，不會改變方程式的解。但是基本列運算卻會改變各變數的係數及右側值。 第6章 線性規劃：單形法 第255頁

17 6.5 計算下一個表 新的單形表： 第6章 線性規劃：單形法 第256頁

18 6.5 計算下一個表 單形法的一次迭代，使我們移到另一個基本可行解。 第6章 線性規劃：單形法 第257頁

19 移向更好的解 從cj 減去zj 以計算新的淨評估列，得到以下單形表：
我們分析 cj - zj 列，看看是否可以引入新變數而改善目標函數值。利用選擇基底變數的規則，我們選擇 x2。 第6章 線性規劃：單形法 第258頁

20 移向更好的解 選擇移走最小比例所對應的變數。同前，我們在單形表的最後一行列出這些比值： 第6章 線性規劃：單形法 第 頁

21 移向更好的解 步驟1. 將第1 列（樞紐列）各元素乘以 8/25，使 12 = 1。 步驟2. 將第2 列減去新的第1 列（新樞紐列），使 22 = 0。 步驟3. 將新樞紐列乘以 5/8，將第3 列減去前述的乘積，使 32 = 0。 第6章 線性規劃：單形法 第259頁

22 移向更好的解 經過列運算之後的單形表如下：
最佳解判斷準則：當所有淨評估列(cj - zj) 的元素均為零或負值時，就達成線性規劃問題的最佳解。此時，最佳解就是目前的基本可行解。 第6章 線性規劃：單形法 第 頁

23 單形法摘要 以下是用單形法解線性規劃問題的步驟，我們假設極大化問題而且所有的限制式均為小於等於限制式。 步驟1. 建立問題的線性規劃模式。
步驟2. 在每個限制條件添加寬鬆變數使成標準型。對所有條件式都是具有非負右側值的小於等於型的問題，這也是用來找出初始基本可行解所需的表格型。 步驟3. 建立初始單形表。 步驟4. 選擇在淨評估列擁有最大值的非基本變數進入基底變數，找出樞紐行，也就是對應進入變數的行。 第6章 線性規劃：單形法 第260頁

24 單形法摘要 步驟5. 在樞紐行 j 中選擇 ij > 0， i / ij 比例最小的列為樞紐列，此列的基本變數為將要離開基底的變數。
步驟6. 進行必要的基本列運算，使進入變數的行變成單位行，其樞紐列的元素為1。 將樞紐列的每一個元素除以樞紐項（位於樞紐列及樞紐行的元素）。 將樞紐列乘以適當的值後加到其他的列，以使樞紐行的其他元素為0。完成之後，可以由 行的值得到新的基本可行解。 步驟7. 檢查是否為最佳解。如果各行的 cj - zj ≤ 0，則我們已找到最佳解。否則，回到步驟4。 第6章 線性規劃：單形法 第 頁

25 6.6 表格型：一般情形─大於等於限制式 當問題含有大於等於限制式時，標準型與表格型並不相同。
事實上變數 a4 與海德問題沒有關係，只是用它來幫我們建立表格型並找到起始基本可行解。這個人為產生用來啟動單形法的新變數，就稱為人工變數(artificial variable)。 第6章 線性規劃：單形法 第262頁

26 6.6 表格型：一般情形─大於等於限制式 有了人工變數，我們將標準型轉變為表格型。在限制式(6.15)加入人工變數a4，得到以下的表格型方程式： 注意人工變數的下標用來表明它所屬的限制式。因此a4是第4個限制式的人工變數。 第6章 線性規劃：單形法 第 頁

27 6.6 表格型：一般情形─大於等於限制式 建立表格型是為了產生初始基本可行解，以啟動單形法。所以，必須引進人工變數時，單形法的初始解通常不會是實際問題的可行解。 要保證在達到最佳解之前刪除人工變數，作法是在目標函數中，給每個人工變數一個很大的成本值。 將每個人工變數的利潤係數用-M表示。 海德問題目標函數的表格型如下： 第6章 線性規劃：單形法 第263頁

28 大於等於限制式 問題的初始單形表如下： 第6章 線性規劃：單形法 第 頁

29 大於等於限制式 第一次迭代的結果： 第6章 線性規劃：單形法 第264頁

30 大於等於限制式 下一次迭代中，變數 s4 以 cj - zj = 50 進入解之中，而變數 s3 被移除，此迭代之後的單形表如下：
第6章 線性規劃：單形法 第265頁

31 大於等於限制式 x2 進入解中而消掉 s1，經過這次迭代後，以下單形表顯示最佳解已經達成。 第6章 線性規劃：單形法 第265頁

32 等式限制式 當等式限制式出現在線性規劃問題中，我們需要增加一個人工變數以得到表格型及初始基本可行解。 第6章 線性規劃：單形法 第266頁

33 消除負的右側值 限制式的右側值是負值，可將全式乘以-1而使右側值成為正值。不等式的符號在乘以-1之後要反過來。
對一個大於等於的限制式，乘以-1可以產生一個相等的小於等於限制式。 對右側值為負的等式限制式，我們只要乘以-1就可得到右側值非負的限制式。再加入一個人工變數就能變成表格型。 第6章 線性規劃：單形法 第 頁

34 建立的表格型步驟摘要 步驟1. 如果原來的線性規劃模式中有一個以上的限制式有負的右側值，將這些限制式乘以-1。乘以-1 將改變不等式的方向。這一步將產生右側值非負的相等線性規劃模式。 步驟2. 針對 ≤ 限制式，加入一個寬鬆變數使成為等式限制式。令寬鬆變數在目標函數的係數為零，產生此限制式的表格型，這個寬鬆變數將成為起始基本可行解的基本變數。 第6章 線性規劃：單形法 第267頁

35 建立的表格型步驟摘要 步驟3. 針對 ≥ 限制式，減去一個剩餘變數使成為等式限制式，然後加入一個人工變數成為表格型。剩餘變數在目標函數的係數為零。人工變數在目標函數的係數為-M。此人工變數將成為起始基本可行解的一個基本變數。 步驟4. 針對等式限制式，加入一個人工變數使成為表格型。人工變數在目標函數的係數為-M。人工變數成為起始基本可行解的一個基本變數。 第6章 線性規劃：單形法 第267頁

36 建立的表格型步驟摘要 將下面的例題轉成表格型，並建立初始單形表： 第6章 線性規劃：單形法 第267頁

37 建立的表格型步驟摘要 我們使用第1 步以消除限制式1 及3 中負的右側值。將這些限制式乘以-1，得到以下的線性規劃：
第6章 線性規劃：單形法 第 頁

38 建立的表格型步驟摘要 第6章 線性規劃：單形法 第268頁

39 建立的表格型步驟摘要 對應的初始單形表如下： 第6章 線性規劃：單形法 第268頁

40 6.7 解極小化問題 單形法來解極小化問題的方法有兩種。
本書採用的方法：任何的極小化問題只要將目標函數乘以-1，就可以將極小化問題變為極大化問題。解這極大化問題，就能找到極小化問題的最佳解。 例題： 第6章 線性規劃：單形法 第 頁

41 6.7 解極小化問題 將目標函數乘以-1，轉變成相等的極大化問題如下： 第6章 線性規劃：單形法 第269頁

42 6.7 解極小化問題 此問題之表格型如下： 第6章 線性規劃：單形法 第269頁

43 6.7 解極小化問題 初始單形表如下： 第6章 線性規劃：單形法 第 頁

44 6.7 解極小化問題 第一次迭代後，x1 進入基底而 a1 移出。拿掉 a1 行後，得到第1次迭代的結果如下：
第6章 線性規劃：單形法 第270頁

45 6.7 解極小化問題 再進行兩次迭代後，得到以下的最終單形表： 第6章 線性規劃：單形法 第270頁

46 6.8 特殊情形─無可行解 如果沒有任何解能夠同時滿足所有限制條件，則此線性規劃問題就無可行解。
最後的解之中如果仍有一個以上的人工變數為正值，就是無可行解。 最後，一個全部的限制式都是形式且右側值非負值的線性規劃問題一定有可行解。 第6章 線性規劃：單形法 第272頁

47 無限解 當對應進入變數的行係數 ij 通通小於等於零時，就會有無限解。 考慮以下的無限解問題：
經過第1個迭代將x1帶入而去除a1之後，得到單形表如下： 第6章 線性規劃：單形法 第272頁

48 無限解 一個極大化的線性規劃問題，如果能夠使最佳解隨意增大而又不會違反任何的限制條件，就會有無限解。當單形法告訴我們引入變數 j 於解之中，而整個第 j 行所有的 ij 都小於或等於零，則此線性規劃就會有無限解。 第6章 線性規劃：單形法 第273頁

49 多重最佳解 一個線性規劃有兩個或更多的最佳解，就具有多重最佳解。如果線性規劃有多重最佳解，就會有一個或多個非基本變數的 cj - zj 為零。 第6章 線性規劃：單形法 第273頁

50 退化解 線性規劃如果有一個或多個基本變數值為0，就是退化解。 第1 列與第2 列的比值相同，這意味在下一次迭代將會有退化的基本可行解。
在實際應用上，循環求解並不會造成嚴重的困擾。所以我們也就不建議引進一些特殊的步驟以消除退化發生的可能性。在進行單形法的迭代演算時，如果兩個最小 的比值相同時，我們還是建議選擇比較上面的列為樞紐列。 第6章 線性規劃：單形法 第 頁