1. 問題背景與標準化

在求解某些線性規劃問題時，往往難以直接找到初始的基本可行解。特別是當約束中存在等式或 “≥” 類型的不等式時，我們需要引入人工變量來構造一個初始可行解。

考慮如下標準形式問題（假設為最大化問題）：

當約束中有“=”或“≥”約束時，為使模型滿足“基本變量個數等于約束個數”的條件，我們引入人工變量 a≥0 。

---

2. 引入人工變量與大?M 懲罰

2.1. 人工變量的引入

• 對于形如

  

  的約束，如果直接采用松弛或剩余變量無法得到初始可行解，則引入人工變量 a≥0 ，使約束變為

  .

• 對于 “≥” 約束，同樣引入剩余變量后再補充人工變量，保證約束滿足等式形式。

2.2. 修改目標函數

為避免在最終解中保留人工變量，需在目標函數中給予這些變量一個巨大的懲罰。對于最大化問題，通常將人工變量前的系數設為 ?M （其中 M?是一個非常大的正數），修改后的目標函數為：

其中 ?表示所有人工變量的集合。這樣做的目的在于：

• 若人工變量在最優解中不為零，則由于扣分 ?M 其目標值會大幅降低，迫使求解過程中盡量消除人工變量；

• 當存在一個可行解不需要使用人工變量時，最終解會將所有人工變量淘汰（即取零）。

---

3. 構造初始單純型表

將原問題中所有變量（原決策變量、松弛/剩余變量、人工變量）統一構成向量，再構造單純型表。設擴展后的變量記為

目標函數寫成：

相應的約束矩陣也經過擴充，使得原約束變為標準等式形式。

初始時，我們選取人工變量作為基本變量，從而構造一個初始基本可行解（注意：此解可能并非真實意義下的“可行解”，因為人工變量僅為輔助求解而引入）。

---

4. 大?M 法的單純型迭代過程

4.1. 目標函數的重寫

類似于普通單純型法，我們把目標函數用基變量和非基變量表示。令 B 為當前基矩陣（其中包含人工變量），則基本解為

目標函數可以寫為

其中：

• ?中可能包含 ?M 對應的人工變量；

• 檢驗數（相對成本）為

  

4.2. 迭代與淘汰人工變量

在迭代過程中，由于目標函數中對人工變量賦予了極大負值 ?M?，如果存在能使目標函數改善的換入操作，就會傾向于選擇那些能使人工變量離開基的換入變量。單純型法的迭代步驟與普通方法類似：

• 進基變量選擇：檢查所有非基變量的檢驗數，若存在 （對于最大化問題），則選擇最有利的變量進基；

• 出基變量選擇：計算方向向量，利用最小比值法確定允許步長和出基變量。

關鍵在于：

• 當存在一個完全可行的解（即一個解不需要使用人工變量）時，經過有限步迭代，所有人工變量將被淘汰（或其值收縮為零）。

• 若最終得到的最優解中仍含有正值的人工變量，則表明原問題沒有可行解。

---

5. 數學證明與思想總結

5.1. 懲罰機制確保解的“真實性”

由于引入了懲罰系數 M ，在目標函數中任何非零的人工變量都會使目標值大幅下降。設若在某一基本解中某個人工變量 保持正值，則對應目標函數貢獻為 。

• 當 M 足夠大時，任何含有非零人工變量的解都不是最優解；

• 如果存在一個可行解（即不存在必須依賴人工變量）時，最優解必然使所有人工變量取零。

5.2. 終止與可行性判斷

• 終止條件：當所有非基變量的檢驗數都滿足最優性條件時，算法終止。

• 無可行解判斷：若在最優解中發現有某個人工變量 ，則說明原問題無可行解。

5.3. 收斂性與大?M 的選擇

• 理論上，M 應當取足夠大，使得其影響在求解過程中遠大于其他系數的作用，但實際計算中需避免因 M 過大而引起數值不穩定；

• 大?M 法證明的核心在于：在有限次迭代內，若存在一個不依賴人工變量的可行解，則算法必然能將所有人工變量驅逐出基，并找到該最優解。

---

6. 總結

大?M 法的理論推導過程主要包括以下幾個步驟：

1. 問題標準化：將問題寫為等式約束形式，必要時引入松弛、剩余和人工變量。

2. 目標函數修改：在目標函數中對人工變量施加巨大的懲罰（對于最大化問題，人工變量前系數取 ?M ）。

3. 構造初始單純型表：以包含人工變量的基本可行解作為起始點。

4. 單純型迭代：按照單純型法的標準步驟進行迭代，通過換基操作改善目標函數值，同時盡量淘汰人工變量。

5. 終止與判斷：若最終最優解中所有人工變量均為零，則得到原問題的最優解；反之，則原問題無可行解。