運籌學單純形法第部分

關于運籌學單純形法第部分

先將約束條件標準化，再引入非負的人工變量，以人工變量作為初始基變量，其對應的系數(shù)列向量構成單位陣，稱為“人造基”；然后用大M法或兩階段法求解；

線性規(guī)劃限制條件都是“≥”或“=”類型的約束——第2頁,共40頁，星期六，2024年，5月等式約束左端引入人工變量的目的

使約束方程的系數(shù)矩陣中出現(xiàn)一個單位陣，用單位陣的每一個列向量對應的決策變量作為“基變量”，這樣，出現(xiàn)在單純形表格中的B(i)列（即約束方程的右邊常數(shù)）值正好就是基變量的取值。（注意：用非基變量表示基變量的表達式）第3頁,共40頁，星期六，2024年，5月①如果限制條件中既有“≤”類型的約束，又有“≥”或“=”類型的約束，怎麼辦？構造“不完全的人造基”！

討論②為什麼初始可行基一定要選單位陣？

b列正好就是基變量的取值，檢驗數(shù)行和b列交叉處元素也正好對應目標函數(shù)值，

因此稱b列為解答列第4頁,共40頁，星期六，2024年，5月（2）寫出初始基本可行解——

根據(jù)“用非基變量表示基變量的表達式”，非基變量取0，算出基變量，搭配在一起構成初始基本可行解。

2、建立判別準則：（1）兩個基本表達式的一般形式就LP限制條件中全部是“≤”類型約束，新增的松弛變量作為初始基變量的情況來描述：第5頁,共40頁，星期六，2024年，5月此時LP的標準型為第6頁,共40頁，星期六，2024年，5月初始可行基：初始基本可行解：

第7頁,共40頁，星期六，2024年，5月

一般（經(jīng)過若干次迭代），對于基B，用非基變量表出基變量的表達式為：用非基變量表示目標函數(shù)的表達式：

第8頁,共40頁，星期六，2024年，5月第9頁,共40頁，星期六，2024年，5月

若是對應于基B的基本可行解，是非基變量的檢驗數(shù)，若對于一切非基變量的角指標j，均有≤0，則X(0)為最優(yōu)解。（2）最優(yōu)性判別定理（3）無“有限最優(yōu)解”的判別定理

若為一基本可行解，有一非基變量xk,其檢驗數(shù),而對于i=1,2,…，m，均有，則該線性規(guī)劃問題沒有“有限最優(yōu)解”。

第10頁,共40頁，星期六，2024年，5月證明思路——構造性證明：依據(jù)用非基變量表示基變量的表達式構造一族可行解，其對應的目標函數(shù)值趨于無窮大。幾何意義：沿著無界邊界前進的一族可行解第11頁,共40頁，星期六，2024年，5月舉例：用非基變量表示基變量的表達式

代表兩個約束條件：x2對應的系數(shù)列向量P2=（1，3）T，當前的換入變量是

X2，按最小比值原則確定換出變量：第12頁,共40頁，星期六，2024年，5月要求：

于是：

如果x2的系數(shù)列變成P2’=（-1，0）T,則用非基變量表示基變量的表達式就變成；

可行性自然滿足,最小比值原則失效,意即x2的值可以任意增大→原線性規(guī)劃無“有限最優(yōu)解”。第13頁,共40頁，星期六，2024年，5月

3、進行基變換（1）選擇進基變量——原則：正檢驗數(shù)（或最大正檢驗數(shù)）所對應的變量進基，目的是使目標函數(shù)得到改善（較快增大）；

進基變量對應的系數(shù)列稱為主元列。（2）出基變量的確定——按最小比值原則確定出基變量，為的是保持解的可行性；

出基變量所在的行稱為主元行。主元行和主元列的交叉元素稱為主元素。第14頁,共40頁，星期六，2024年，5月思考題

這樣進行基變換后得到的新解對應的系數(shù)列向量是否線性獨立？

4、主元變換（旋轉運算或樞運算）

按照主元素進行矩陣的初等行變換——把主元素變成1，主元列的其他元素變成0（即主元列變?yōu)閱挝幌蛄浚懗鲂碌幕究尚薪?，返回最?yōu)性檢驗。第15頁,共40頁，星期六，2024年，5月單純形法小結

求解思想－－

頂點的逐步轉移，

條件是使目標函數(shù)值不斷得到改善。第16頁,共40頁，星期六，2024年，5月表格單純形法求解步驟第一步：將LP化為標準型，并加以整理。引入適當?shù)乃神Y變量、剩余變量和人工變量，使約束條件化為等式，并且約束方程組的系數(shù)陣中有一個單位陣。

（這一步計算機可自動完成）

確定初始可行基，寫出初始基本可行解第17頁,共40頁，星期六，2024年，5月第二步：最優(yōu)性檢驗計算檢驗數(shù)，檢查：所有檢驗數(shù)是否≤0？

是——結束，寫出最優(yōu)解和目標函數(shù)最優(yōu)值；還有正檢驗數(shù)——檢查相應系數(shù)列≤

0？是——結束，該LP無“有限最優(yōu)解”！不屬于上述兩種情況，轉入下一步—基變換。

確定是停止迭代還是轉入基變換？第18頁,共40頁，星期六，2024年，5月

選擇（最大）正檢驗數(shù)對應的系數(shù)列為主元列，主元列對應的非基變量為換入變量；最小比值對應的行為主元行，主元行對應的基變量為換出變量。第三步：基變換確定進基變量和出基變量。第19頁,共40頁，星期六，2024年，5月

利用矩陣的初等行變換把主元列變成單位向量，主元素變?yōu)?，進基變量對應的檢驗數(shù)變成0，從而得到一張新的單純形表，返回第二步。第四步換基迭代（旋轉運算、樞運算)完成一次迭代，得到新的基本可行解和相應的目標函數(shù)值第20頁,共40頁，星期六，2024年，5月該迭代過程直至下列情況之一發(fā)生時停止

檢驗數(shù)行全部變?yōu)榉钦?；（得到最?yōu)解）或主元列≤

0（最優(yōu)解無界）

停止迭代的標志（停機準則）

依據(jù)：最優(yōu)性檢驗的兩個定理最優(yōu)性判別定理；無“有限最優(yōu)解”判斷定理第21頁,共40頁，星期六，2024年，5月計算機求解時的注意點1、輸入數(shù)據(jù)中的分數(shù)，需先化為小數(shù)再執(zhí)行輸入過程。2、每一張迭代表格中由基變量列（Basic）和B(i)列（解答列）可以讀出現(xiàn)行解及相應的目標函數(shù)值，同時顯示進基變量和出基變量，從而很容易識別主元列、主元行和主元素。3、最終表顯示最優(yōu)解、最優(yōu)目標函數(shù)值及總的迭代次數(shù)。如遇該線性規(guī)劃無可行解或無“有限最優(yōu)解”，則屏幕將顯示有關信息：

NOfeasiblesolution.

或**unboundedsolution!!!第22頁,共40頁，星期六，2024年，5月五、各種類型線性規(guī)劃的處理1、分類及處理原則：（1）類型一：目標要求是“Max”，約束條件是“≤”類型——左邊加上非負松弛變量變成等式約束（約束條件標準化），將引入的松弛變量作為初始基變量，則初始可行基是一個單位陣，用原始單純形法求解。第23頁,共40頁，星期六，2024年，5月（2）類型二：目標要求是“Max”，約束條件是“=”類型——左邊引入非負的人工變量，并將引入的人工變量作為初始基變量，則初始可行基是一個單位陣，然后用大M法或兩階段法求解。（3）類型三：目標要求是“Max”，約束條件是“≥”類型——約束條件標準化，左邊減去非負的剩余變量，變成等式約束，化為類型二。第24頁,共40頁，星期六，2024年，5月（4）類型四：目標要求是“Min”

①方法1——化為極大化問題

②方法2——按照極小化問題直接在單純形表格上計算處理，但

相應的原則要作改動。

第25頁,共40頁，星期六，2024年，5月2、處理人工變量的方法：（1）大M法——在約束條件中人為地加入非負的人工變量，以便使它們對應的系數(shù)列向量構成單位陣。問題：加入的人工變量是否合理？如何處理？在目標函數(shù)中，給人工變量前面添上一個絕對值很大的負系數(shù)-M（M>>0），迭代過程中，只要基變量中還存在人工變量，目標函數(shù)就不可能實現(xiàn)極大化——懲罰！第26頁,共40頁，星期六，2024年，5月①最優(yōu)表中，基變量不包含人工變量，則最優(yōu)解就是原線性規(guī)劃的最優(yōu)解，不影響目標函數(shù)的取值；②最優(yōu)表中，基變量中仍含有人工變量，表明原線性規(guī)劃的約束條件被破壞，線性規(guī)劃沒有可行解，也就沒有最優(yōu)解！

結果問題

結果②中求得的最優(yōu)解是哪個線性規(guī)劃的最優(yōu)解？為什麼？第27頁,共40頁，星期六，2024年，5月（2）

兩階段法

第一階段：建立輔助線性規(guī)劃并求解，以判斷原線性規(guī)劃是否存在基本可行解。輔助線性規(guī)劃的結構：目標函數(shù)W為所有人工變量之和，目標要求是使目標函數(shù)極小化，約束條件與原線性規(guī)劃相同。

第28頁,共40頁，星期六，2024年，5月

求解結果①W最優(yōu)值=0——即所有人工變量取值全為0（為什麼？），均為非基變量，最優(yōu)解是原線性規(guī)劃的一個基本可行解，轉入第二階段；②W最優(yōu)值=0——但人工變量中有等于0的基變量，構成退化的基本可行解，可以轉化為情況①；如何轉化？

選一個不是人工變量的非基變量進基，把在基中的人工變量替換出來第29頁,共40頁，星期六，2024年，5月③W最優(yōu)值>0——至少有一個人工變量取值>0,說明基變量中至少有1個人工變量,表明原問題沒有可行解,討論結束。問題討論①教材P49輔助線性規(guī)劃的結構是：目標函數(shù)W為所有人工變量之和的相反數(shù)，目標要求是使目標函數(shù)極大化，約束條件與原線性規(guī)劃相同。這與上述的討論是否矛盾？第30頁,共40頁，星期六，2024年，5月試比較：（1）（2）第31頁,共40頁，星期六，2024年，5月

②（1）式目標要求改為極大化（或（2）式目標要求改為極小化）行不行？

第二階段：

將第一階段的最優(yōu)解作為初始可行解，目標函數(shù)換成原問題的目標函數(shù)，進行單純形迭代，求出最優(yōu)解。問題討論：①如何實施？需要重新建立初始單純形表嗎？第32頁,共40頁，星期六，2024年，5月

實施中，在第一階段最優(yōu)表格中劃去人工變量列，將表頭部分和CB列的價值系數(shù)換成原問題的價值系數(shù)(把目標函數(shù)換成原線性規(guī)劃的目標函數(shù))，繼續(xù)迭代，直至求出最優(yōu)解。②在大M法中，當人工變量出基后能否立即劃去該人工變量所在的系數(shù)列？

第33頁,共40頁，星期六，2024年，5月3、用表格單純形法直接計算極小化線性規(guī)劃時要修改哪些原則？（初始表？最優(yōu)解判別？換入變量？換出變量？旋轉運算？引入人工變量？）

最優(yōu)性判別：所有檢驗數(shù)非負

換入變量的選擇原則：（最?。┴摍z驗數(shù)所對應的變量進基，以保證目標函數(shù)值（較快）減?。?/p>

用大M法求解時，在目標函數(shù)中人工變量的前面添上一個很大的正系數(shù)M；第34頁,共40頁，星期六，2024年，5月六、迭代過程中可能出現(xiàn)的問題及處理方法1、為確定出基變量要計算比值，該比值=解答列元素/主元列元素。對于主元列的0元素或負元素是否也要計算比值？（此時解的可行性自然滿足，不必計算；如果主元列元素全部為0元素或負元素，則最小比值失效，線性規(guī)劃無“有限最優(yōu)解”）第35頁,共40頁，星期六，2024年，5月2、現(xiàn)若干個相同的最小比值怎麼辦？（說明出現(xiàn)了退化的基本可行解，即非0分量的個數(shù)小于約束方程的個數(shù)。按照“攝動原理”所得的規(guī)則，從相同比值對應的基變量中選下標最大的基變量作為換出變量可以避免出現(xiàn)“死循環(huán)”現(xiàn)象）3、選擇進基變量時，同時有若干個正檢驗數(shù)，怎麼選？第36頁,共40頁，星期六，2024年，5月（最大正檢驗數(shù)或從左至右第1個出現(xiàn)的正檢驗數(shù)所對應的非基變量進基）課堂練