6.6 線性規劃的單體法 單體法 (simplex method) 6.6 線性規劃的單體法 單體法 (simplex method) 是一反覆的程序 (iterative procedure),直到得出最優解才停止。 基本原理 首先選出一組可行解和一判斷準則,判斷目前的解是否為最優解, 若不是,則設法取另一端點取代,使目標函數值增大 (或減小) 如此不斷進行,直至得出最優解為止。 chapter6
chapter6
chapter6
6.6.2 標準形式 線性規劃問題的可行解可於可行凸集合的端點找到,這類端點對應於基本可行解 (basic feasible solution)。 chapter6
將不等式改寫為方程式即為線性規劃的標準式 加上不足的變數(惰變數, slack variable) 減去多餘的變數(剩餘變數, surplus variable) chapter6
將不等式改寫為方程式即為線性規劃的標準式 加上不足的變數(惰變數, slack variable) 減去多餘的變數(剩餘變數, surplus variable) chapter6
6.6.3 單體法的解題程序 chapter6
chapter6
chapter6
chapter6
起始步驟:構建一組初始可行解,通常為利用惰變數,假若沒有惰變數或其個數不足,則可引進人工變數 (artificial variable),然後利用大M法 (big M method) 或二階段法 (two-phase method) 解題。 反覆步驟:在本步驟應考量如下三大問題: (1)進入基底的變數的選取準則為何? (2)如何辨認現行基底中那一個變數應退出? (3)如何能便利地辨認新基本可行解? 最優性檢定: 單體法的整個求解程序如圖6.13流程圖所示: chapter6
chapter6
chapter6
3個限制式 chapter6
此時x1=x2=0, x3=150, x4=100, x5=80, 故z=0 chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6
chapter6