人工變數法

人工變數法

線上性規劃問題的單純形法中,若標準化後找不到單位矩陣,可以採用人造基,給方程加入人工變數後,用大M法和兩階段法處理求解。是求解線性規劃問題的一種方式。

基本介紹

  • 中文名:人工變數法
  • 外文名:Artificial variable method
  • 適用領域:線性規劃
  • 套用學科:組合數學、運籌學
  • 方法:大M法和兩階段法
  • 意義:求解特殊的線性規劃問題
定律定義,求解方法,大M法,兩階段法,求解結果,適用範圍,

定律定義

其公式如下:
,其中Xs是xs鬆弛變數組成的向量。
正如上式所展示的那樣,所有約束是(≤),並且有非負右端項(bi≥0)的線性規劃,化為標準形式是在每個不等式的左端添加一個鬆弛變數,這時約束等式左端的係數矩陣就含有一個單位矩陣I,取這個單位矩陣為初始基,很容易得到一個初始基本可行解,從而建立單純形表
但包含(=)和或(≥)約束條件則不是如此。對於(≥)型約束來說,標準化時需添加剩餘變數,其係數為-1,而對(=)型約束,則沒有鬆弛變數,因此存在這兩種約束條件標準化後缺少足夠的鬆弛變數的係數組成(諸如
)十分直觀的單位矩陣,也即無法不做變換地找到基本可行解。這時候可以利用人工變數x(artificial variables)類似鬆弛變數添加到等式中去,讓它們在第一次疊代起著鬆弛變數的作用,並隨後用某次疊代中再把這些人工變數去掉。
由於人工變數存在於初始基本可行解,而且人工變數是虛擬變數,它們在目標函式極值時不應該存在數值,因此需要將它們從基變數中替換出來。若人工變數可以從基變數中替換出來,即基變數中不含有非零的人工變數,表示原問題有解;若人工變數不可以從基變數中替換出來,則表示原問題無可行解。

求解方法

加入人工變數後,一般可採用大M法兩階段法處理。

大M法

如果是求極大值,即假定人工變數在目標函式中的係數為-M(M是任意大正數);如果是求極小值,人工變數在目標函式中的係數為M。用單純形法對模型求解,如基變數中還存在M,就不能實現極值。

兩階段法

用計算機處理數據時,只能用很大的數代替M,可能造成錯誤,故多採用兩階段法。
第一階段:在原線性規劃問題中加入人工變數,構造模型。構造模型的目標函式為:
用單純形法對上述模型求解。若W=0,說明問題存在基本可行解,可以進行第二個階段;否則,原問題無可行解,停止運算。
第二階段:在第一階段的最終表中,(1)去掉人工變數,(2)將目標函式的係數換成原問題的目標函式係數,作為第二階段計算的初始表,用單純形法計算。

求解結果

1、無可行解:運算到檢驗數全負為止,若仍含有人工變數在基可行解未進入非基變數,則無可行解。
2、退化:若計算出的用於確定換出變數的
有兩個以上最小值,會造成下一次疊代中有一個或幾個基變數等於零。
為避免退化,雖任意換出變數目標函式值不變,但此時不同的基卻表示為同一頂點,其特例是永遠達不到最優解,需作如下處理蘭特Bland規則:
(1)當
中出現兩個以上最大值時,選下標最小的非基變數為換入變數;
(2)當
中出現兩個以上最小值時,選下標最小的基變數為換出變數。

適用範圍

當存在(=)和或(≥)約束條件時使用該方法。
雖然標準化後可能存在單位矩陣可以不需要添加人工變數,但是它不具有代表性,而且人工變數法具有普適性,即使添加上了不妨礙結果,人工變數法比起尋找單位矩陣,無論在人工還是計算機計算時都有更高的可操作性。

相關詞條

熱門詞條

聯絡我們