线性规划单形法

1、第五章 線性規劃 : 單形法 本章內容：5.1 單形法之代數原理5.2 表格型5.3 建立初始單形表5.4 解的改進5.5 計算下一個表5.6 表格型 : 一般情形5.7 解極小化問題5.8 特殊情形5.1 單形法之代數原理例：海德公司要為D型電腦及P型電腦發展一種週生產排程。D型電腦每件利潤50元，P型電腦每件40元。下一 週的生產最多有150小時可用在裝配，每件D型需3小 時裝配，P型需5小時裝配。另外，海德公司目前只有 20台P型電腦的顯示器存貨，所以P型電腦最多只能裝 配20件，每件D型需8平方尺，每件P型需5平方尺儲 存空間，該公司只有 300平方尺倉庫可用來存儲新產 品。試以單形法

2、求出其最適解及總利潤。令：X1= D型裝配件數 X 2= P型裝配件數則 Max50X1 40X20S1 0S20S35.1 s.t.3X 1 5X21S1 = 1505.2 1X2 1S2 = 205.3 8X1 5X21S3= 3005.4 X1, X2, S1, S2, S3仝 05.5 單形法之代數性質：1.n個變數m固限制式方程式T無限多解上例中，變數 為XI，X2，S1，&, S3共5個，限制方程式共3個，由於 5 變數3 限制式-無限多解。2. 任何不滿足非負值限制的解都不要 上例中任何 X1，X2, Si, S2, S3 均需“仝0。找一個根本解根本解：要找根本解，令

3、n-m個變數等於零，再解剩下m個變數的m個限制式。上例中有5個變數，3個方程式。令2個=5- 3變數 等於零，解其他三個變數的三個聯立限制方程式。上例中， 假设令 X2= 0， S1= 0，則限制式為：3X1= 150， S2= 20， 8X1S3= 300解聯立限制方程式得 X1= 50， S2= 20， S3=- 100 及 X2= 0， S1= 0，此解為一“根本解。被令為零的變數稱為非根本變數( nonbasic variable )， 剩餘的變數稱為根本變數 ( basic variable )。上例中 X2， Si為非根本變數，Xi, S2, S3為根本變數。 根本可行解為一根本解

4、，且滿足非負值條件。上例中S3=- 100,所以例子存有非合理解。假设令Xi, X2為非根本變數(Xi = 0, X2= 0)，則限制式為Si =150, S2= 20, S3= 300,因此得解為 Xi = 0, X2= 0, Si =i50, S2= 20, S3= 300,由於每一變數都M 0,所以此解 為根本合理解。海德公司根本合理解共有五個，如下所示：極 點X2SiS2ST001502030075/2072/2200301208050/32000200/3020500200結論：(1)線性規劃合理區的每一個極端點都是根本合理解, 其中有一極端點必為最適根本合理解。 2單形法是一個反覆

5、的步驟，從一個根本合理解極 端點起到另一個根本合理解極端點 ，直至尋到最適 根本解極端點為止。5.2 表格型 表格型目的：在單形法中需要一個根本合理解作為起始 點，表格型的目的即在尋找起始點，其原因為表格型具備 找到起始根本合理解之二特性：1. 假设能滿足以下二條件才能找到根本解：1對每一個限制式，m個根本變數在上例中 Si, S2,S 3為根本變數中只能有一個變數在該式的係數必須是 1，而在此式的其他根本變數的係數均為零。如上例第一個限制式中為 1S1, 0S2, 0S3；第二個限制 式為0S1, 1S2, 0S3；第三個限制式為 0S1, 0S2, 1S3。(2) 每個根本變數的係數，只有

6、在一個限制式是1。如上例限制式中之 1S1， 1S2， 1S3。2.需要RHS值為非負值。 滿足以上二特性，稱之為表格型。結論：只要數學模式之限制式為“W及“非負值者，即已為表格型了。上例中，所有條件都是小於等於型的線性規劃問 題，因此很容易找到起始根本合理解。只要簡單的令決策變 數等於零而解惰變數即可 。注意，惰變數就等於右手邊數值。X1= 0, X2= 0, Si= 150, S2= 20 及 S3= 300 為起始根本合理 解，這個解相當於用原點，極端點 為起始合理解。單形法求解線性規劃問題的準備步驟 ：1 建立模型 ；2 参加惰變數或減去剩餘變數以建立標準型； 3建立表格 型。5.3

7、建立初始單形表在線性規劃轉變為表格型之後 ,即有一個起始根本合理解 用以啟動單形法。因此需先建立初始單形表。初始單形表之表2K法：Max Z=CiXi+G)+s.t. : a iiX+ai2)t+w bi821X1+ 322) +w boc列二目標函數係數的列數。 b行二限制式右邊值的行數。 A矩陣二限制式中變數係數的m列n行矩陣。c列CiC2cnA矩陣aiiai2ainb i a2iai3a2nb 2 B? ?行aia 2amnb m上例初始單形表如下:XiX2S 99基底C B504000 0Si035i00i50S200i0i020S308500i300因初始單形表已表格化了 ，所以很容

8、易找到起始根本合理 解。 1每個根本變數所對應的行，只有1 在非零的位置。這種行稱為單位行或單位向量。 2配合每個根本變數只有一列，這列有1 在相當於基本變數的單位行的地方。上例中，根本變數： Si = bi= 150, S2= b2= 20, S3= b3= 300,因此起始根本合理解為： Xi = 0, X2= 0, Si= 150, S2 = 20 及 S3= 300。計算列 ( 當增加 1 單位，目標函數值減少的量 )Z1= 0(3) + 0(0) + 0(8) = 0 Z 2 = 0(5) + 0(1) + 0(5) = 0Z3= 1(0) + 0(0) + 0(0) = 0 Z 4

9、 = 0(0) + 0(1) + 0(0) = 0Z5= 0(0) + 0(0) + 0(1) = 0計算 Cj Zj 列( 當 Xj 增加 1 單位，對目標函數的淨改變量 )Cj Zj = 50 0= 50Cj Zj = 40 0= 40Cj Zj = 0 0= 0Cj Zj = 0 0= 0Cj Zj = 0 0= 0目前根本合理解的利潤：Z = 150(0) 20(0) 300(0) = 0X1X2S1S2S3基底CB5040000S1035100150S200101020S305001300Zi000000C - Zj5040000CB：根本變數在目標函數的係數目標函數值刁:第j行的變

10、數帶入根本變數 造成目標函數值減少的量(MC)LCj -Z :目標函數的淨改變量(淨評估列MR-MC)X1：設X2仍為非根本變數，假设Xi改為根本變數，將使S1減少3, S2減少0, S3減少8X2:設X1仍為非根本變數，X2改為根本變數，將使Si減少5, S2 減少1, S3減少55.4 解的改進單形法的工作即在變換變數 ，亦即由目前非根本變數中選 一個變數，便之成為根本變數 進入變數 ，而目前的根本 變數成為非根本變數 退出變數 ，如此反覆的交換，直至 尋得一改善目標函數值的新根本合理解。由淨評估列 Cj Zj 中，選擇每增加一個單位，能使目標 函數改善程度最大者為新進入的基底變數，當數值

11、相同 時，選擇最左邊的一個。上例中，選 X1 為進入變數，使之成為根本變數。自目前基底移出一個變數的判定準則最小比率測試 ： 假設進入根本變數來自單行表 A 矩陣的第 j 行，對每一列 i，計算每個aij > 0者的bi / aij比值，最小的比值所對應 的根本變數就離開基底。在數值相同的情形；選擇最上面 的一個。Bi / ai= 150/ 3= 50E2 / a2 = 20/ 0=-B 3 / a3= 300 / 8= 37.5上例中，選 S3 為退出變數，使之成為非根本變數。基底CBX1X2S1S2S3bi / aij5040000S1035100150150 / 3= 50S200

12、101020S305001300300 / 8= 37.5刁/00000/C -叫40000樞紐元素 樞紐行進入行利潤 樞紐列退出列 註：步驟從生產面來看1. 生產何種產品？ MR-MC最大值最適化條件2. 生產多少數量？選擇 bi/a ij最小值可行性條件5.5 計算下一個表更新單形表亦即使新的根本變係數變成一單位行 。上例 中即為使X1行變成與S3行相似。X1S33 0 = ail0 變為0 = a2ia3i根本列運算法：1. 將任何列方程式乘以一個非零值。2. 將任何一列乘以假设干倍加到另一列。根本列運算法不會改變限制式的解，但會改變限制式中各 變數的係數及RHS值。注意：區別aij、a

13、ij、bij、bij。(1) 要使a3i= 1,則將樞紐列乘以(1/8 )1/8(8X 1 + 5X2 + OSi+ 0S2+ 1S3)= 1/8(300)Xi + 5/8X2+ 0S1 + 0S2+ 1/8S3= 75/2 (新樞紐列)(2) 要使a11 = 0,則將新樞紐列乘以(3)3( 1X1 + 5/8X 2 + 0S1+ 0S2+ 1/8S3)= 3(75/2)3X1 + 15/8X 2 + 0S1 + 0S2+ 3/8S3= 225/2將上例中之第一列減上式：(3X1 + 5X2 + 1S1) ( 3X1 + 15/8X 2 + 3/8S 3)= 150- 225/2 0X1 +

14、25/8X2 + 1S1 3/8S 3= 75/2(3) 321 = 0 不再做任何根本列運算新的單形表如下:X1X2S1S2S3基底 CB5040000S10025/810-3/875/2S200101020X15015/8001/875/2刁1875C - Zj得限制式如下:25/8X 2 + 1Si-3/8S 3 = 75/2 J1X2+ 1S2= 20 1X1 + 5/8X2 + 1/8S3= 75/2得改變原限制式各變數係數及RHS值極端點 ) ：令X2= 0, S3= 0 (非根本變數)得 Si = 75/2 , S2= 20, Xi = 75/2Z= 0(75/2) 0(20)

15、50(75/2) = 1875解釋每一循環的結果起始根本合理解(極端點)-新根本合理解(Xi= 0Xi = 75/2X2= 0X2= 0Si = i50Si = 75/2S2= 20S2= 20S3= 300S3= 0Z=0Z= i8750102030405060D型圖5.2海德公司問題的可行區及極點移向更好的解以上方法反覆進行：Zi=O(O) +0(0) +50(1) =50Z2= 0(25/8) +0(1) + 50(5/8)Z3=0(1) +0(0) + 50(0) =0Z4= 0(0) +0(1) + 50(0) =0Zs= 0(-3/8) +0(0) + 50(1/8)=250/8=

16、 50/8X1X2S1S2S3基底 CB5040000S10025/810-3/875/2S200101020X15015/8001/875/2刁50250/80050/81875C - Zj070/800-50/8X2S125/81 =石1275/2 / 25/820/1 = 2075/2 / 5/8 =變為00 =p22=W32bi / aij=12=6015/8(1)要使312= 1,則將樞紐列乘以(8/25 )8/25(0X 1 + 25/8X2 + 1Si + OS2 3/8S 3) = 8/25(75/2)0X1 + 1X2+ 8/25S1 + 0S2 3/25S 3 = 12 (

17、新樞紐列)(2) 要使a22= 0,則將上表中之第二列減去新樞紐列(0X1+ 1X2+ 0S1+ 1S2+ 0S3)( 0X1+ 1X2+ 8/25S1 + 0S2 3/25S3)= 20 120X1 + 0X2 8/25S1+ 1S2+ 3/25S 3= 8(3) 要使a21 = 0,則將新樞紐列乘以(5/8 )5/8 (0X1+ 1X2+ 8/25S1 + 0S2 3/25S3)= 5/8 (12)0X1 + 5/8X 2+ 1/5S1 + 0S2 3/40S 3= 15/2將上表中之第三列減上式(1X1 + 5/8X2+ 0S1 + OS2+ 1/8S3)( 0X1+ 5/8X2+ 5/

18、25S1+ 0S2 3/40S3)= 75/12 15/21X1 + 0X2 5/25S1 + 0S?+ 5/25S3)= 30經過運算之後的單形表如下：X1X2S1S2S3基底CB5040000羽40018/250-3/2512S2000-8/2513/258X15010-5/2505/2530Zj504014/5026/51980Q Zj00-14/50-26/5得限制式如下:X2+ 8/25S1 3/25S3= 12-8/25S 1 + S2 + 3/25S3= 8L 改變單形法第二表限制式Xi 5/25S1 + 5/15S3= 30 J各變數係數及 RHS值根本解 X2= 12, S2

19、= 8, Xi = 30, Si = 0, S3= 0Z= 40(12) + 0(8) + 50(30) = 1980極端點-»極端點X1 = 25/2 S2= 20X1 = 30 S2= 8X2= 0 S3= 0X2= 12 S3= 0S1 = 75/2 Z=1875S1 = 75/2 Z=1980最適解判斷準則:當所有淨評估列 Cj Zj 的元素均為零或負值時，線性 規劃問題的最適解就已達成。此時，最適解就是目前的基 本可行解。說明最適解單形法摘要單形法步驟摘要：1. 建立問題的線性規劃模式。2. 在每個限制條件添加惰變數使成為標準型 。對所有條件 式都是小於等於型的問題 ，這也

20、是用來找出初始根本可行 解所需的表格型。3. 建立初始單形表。4. 選擇在淨評估列擁有最大值的非根本變數進入基底變數，找出樞紐行，也就是對應進入變數的行。5. 在樞紐行j中選擇aij >0, bi/ aij比例最小的列為樞紐 列，此列的根本變數為將要離開基底的變數。6. 進行必要的根本列運算，使進入變數的行變成單位行， 其樞紐列的元素為1。(1) 將樞紐列的每一個元素除以樞紐項(位於樞紐列及 樞紐行的元素)。(2) 將樞紐列乘以適當的值後加到其他的列，以使樞紐行的其他元素為0。完成之後，可以由bi行的值得到新的 根本可行解。7. 檢查是否最適解。如果各行的 C -Z三0,則我們已找到最適

21、解，否則回到第 4 步。rhS直為“非負，5.6 表格型：一般情形假设所有限制程式均為小於等於零，及只要加“惰變數即可。大於等於限制式例： Max 50X 1 40X2s.t. 3X1 + 5X2 w 150裝配時間1X2W 20P 型顯示器8X15X2w 300倉儲空間1X1+ 1X2 仝 25最低總產量X 1, X2 仝 0J標準型：在標準型中令X1 = X2= 0根本解得 Si = 150, S2= 20, S3= 300, S4= 25S4 = 25有非合理解Max 50X140X2 0S1 0S20S30S4s.t. 3X 15X21S1 = 1501X2 1S2= 208X1 5X

22、2 1S3= 3001X1+ 1X2- 1S4= 25 X 1, X2, Si, S2, S3, S4仝 0J表格型人為變數 artificial variable Max 50X1+ 40X2+ 0S1+ 0S2+ 0S3+ 0S4- Ma4 s.t. 3X1+ 5X2+ 1S1= 1501X2+ 1S2= 208X1+5X2+ 1S3= 3001Xi+ 1X2- 1S4+ 1a4= 25Xi, X2, Si , S2, S3, S4= 0在表格型中令 X1= X2= S4= 0，得 S1= 150， S2= 20， S3=300, a4= 25,滿足單形表之根本合理解,但不能滿足所有限 制

23、條件，如：Xi + X2仝25 (Xi = X2= 0),因此不合理，為達實 際合理解只須以人為變數求出起始合理解，而後再於問題達 最適解時，將人為變數消除。人為變數消除的方法：( 重點：人為變數目的在於求一起始根本合理解 ) 。在目標 函數中，給每個人為變數一個很大的本钱即可將人為變數消除。上例中，給人為變數 a4 一個非常大的負值當做利潤， a4 在基底內會大量減少利潤，如此 a4 會從基底中消除，即目標 函數為：Max 50X 1 40X2 0S1 0S2 0S3 0S4 Ma4 反之，在最小化問題中，目標函數改為Min 50X 1 40X2 0S1 0S20S30S4Ma4人為變數，只

24、是用來找起始根本合理解，只要人為變數離 開根本合理解，就可以立刻將人為變數自單形表中去掉。當 所有人為變數都自基底中消除，即表該問題已得到一根本合 理解了。X1X2S1S2S3S4a4基底 CB50400000-MS103510000150S20010100020S308500100300a4-MG)1000-1125Zj-M-M000M-M-25叶C -刁50+ M40+ M000-M0S10021000-375S20010100020S300-30018-8100X15011000-1125Zj5050000-50501250Cj - Zj0-1000050-M-50因X+X2M 25(X

25、i=X2=O)明顯不合理，因此為達實際合理解，需將 人為變數消除繼續完成之單形法如下:X1X2S1S2S3S4基底 CB50400000S10025/810-3/8075/2從=0,S2001010020 丄 S3= 0S400-3/8001/8125/2X1015/8001/8075/2刁50250/80050/801875C - Zj070/800-50/80X0015/250-3/25012S1 = 0,S2000-8/2513/2508 L S3= 0S40003/2502/25117X15010-5/2505/25030刁504014/5026/501980C - Zj00-14/5

26、0-26/50假设問題已達最適解所有 Cj -Z均“W 0,但仍有一個或多個人為變數仍在基底中，則此問題“無合理解。 等式限制式例：6X1 + 4X2- 5X3= 30 J加人為變數6X 1 + 4X2 - 5X3 + 1ai = 30 表格型去除負的右手邊值 例: X2W X1- 5J移項Xi + X2W 5J各項乘1,使RHS成“非負值Xi-X2M 5 表格型例：6X1 + 3X2 - 4X3 仝一20J各項乘1,使RHS成“非負值6X1 3X2 + 4X3 W 20 表格型建立步驟摘要5.7 解極小化問題假设為極小化問題，只需將目標函數乘以 1，使其成為 極大化問題，即可求得最適解，但所

27、求得之目標函數值需 乘以 1，使其還原為原來極小化問題之目標函數值。例：Min2X 1 + 3)fes.t. 1X11251X1 + 1MM3502X1 + 1X2600J目標函數乘Max 2X13 刈s.t. 1X11251X1 + 1刈仝3502X1 + 1X2600J表格化產量A需求量總產量生產時間X 1,刈仝0D產量A需求量生產時間X 1,沟仝0Max 2Xi 3X2+ OSi + 0S2+ OSs Ma Maes.t. 1X 1 1Si + ai= 1251X1 + 1X2 1S2+ 1a2= 3502X1 + 1X2+ 1Ss= 600X1, X2, S1, S2, S3, a1,

28、 a2= 0起始單形表如下:X1X2S1S2S3a1a2基底 CB-23000-M-Ma1-M0-10010125a2-MO10-1001350S302100100600刁-2MMMM0-M-M-475MQ - Z-2+2M-3+M-M-M000最後單形表如下:X1X2S1S2S3基底CB2-3000x1-210011250X2-3O10-2-1100S1000111125Zj-2-3041-800Cj Zj000-4-1解 Xi = 250,，X2= 100, S1= 125, S2= 0, S3= 0, Z= 800 目標函數值為800,需再乘1，使其為原來極小化 問題之目標函數值1 80

29、0 = 800。5.8 特殊情形無可行解=無解=無合理解1. 意義：無任何解能滿足所有限制條件。2. 最適評核標準：人為變數仍存於基底中，且為正值。例： Max50X140X2s.t. 3X1 + 5X2 W 150裝配時間1X2 三 20P型顯示器8X1 + 5X2 W 300倉儲空間1X1 + 1X2 50最低總產量Xi, X2 仝 0單形法最後表如下:X1 X2S1S2S3S4 a4基底CB50400000-MX240018/250-3/250012S2000-8/2513/25008X15010-5/2505/250030a4-M00-3/250-2/25-118Zi504070+3&

30、quot; 250130+2" 25M-M1980-8MCj Zi00-70-3M / 250-130-2M / 25-M-M這個解不合理，因為 Xi = 30及X2= 12而總產量只有42 件，而不是至少50件第4個限制式，而人為變數在解 之中，且=8,告訴我們最後的解違背第 4限制式1X1 + 1X2仝50 8單位。無限解1. 意義：使最適解隨意的大，而又不會違背任何限制條件2. 最適評核標準：進入行中，對應之所有aij為或例: Max 20X1 + 10X2s.t. 1X 1 兰 2 1X 2三 5 X 1, X2± 0 去除a1人為變數後之單形表如下：X1X2S1S2基底CB201000X12010-102S2001015Zj200-20040C Zj1 010200多重最適解1. 意義：線性規劃有 2 個或多個最適解。2. 最適評核標準：1在圖解法中，目標函數線與一邊緣限制式平行。Cj2在最後