§4.2 兩階段法與大m法————初始可行基的求法
求解線性規劃的步驟是：
1） 已知乙個初始基本可行解
2） 從初始基本可行解出發，寫出單純型表，求出進基離基變數，做主元消去法，求出乙個新的基本可行解且使目標函式值得到改善。
3） 判斷當前基本可行解是否是最優解
那末，當觀察不出來初始基本可行解時，怎麼辦？下面介紹的方法是幾種求初始基本可行解的方法
4.2.1 兩階段法
0其中a是矩陣，≥0。若a中有階單位矩陣，則初始基本可行解立即得到。比如，，那麼
就是乙個基本可行解。若a中不包含階單位矩陣，就需要用某種方法求出乙個基本可行解。
介紹兩階段法之前，先引入人工變數的概念。
設a中不包含階單位矩陣，為使約束方程的係數矩陣中含有階單位矩陣，把每個方程增加乙個非負變數，令
4.2.2）
0 ，≥0
即4.2.3）
0 ，≥0
顯然，是的乙個基本可行解.
向量是人為引入的，它的每個分量成為人工變數。人變數與前面介紹過的鬆弛變數是兩個不同的概念。鬆弛變數的作用是把不等式約束改寫成等式約束，改寫前後的兩個問題是等價的。
因此，鬆弛變數是「合法」的變數。而人工變數的引入，改變了原來的約束條件從這個意義上講，它們是「不合法」的變數。
第一階段是用單純形方法消去人工變數（如果可能的話）：
其中是分量全是的維列向量，
是人工變數構成的維列向量。
由於是（4.2.4）的乙個基本可行解，目標函式值在可行域上有下界，因此問題（4.2.4）必存在最優基本可行解。
求解（4.2.4），設得到的最優基本可行解是，此時必
有下列三種情形之一：
1. 這時（4.2.1）無可行解。因為如果存在可行解則
是的可行解。在此點，問題的目標函式值
而是目標函式值的最優值，矛盾。
2.且的分量都是非基變數。這時，個基變數都是原來的變數，又知是（4.2.4）的基本可行解，因此是（4.2.1）的乙個基本可行解。
3且的某些分量是基變數。這時，可用主元消去法把原來變數中的某些非基變數引進基，替換出基變數中的人工變數，再開始兩階段法的第二階段。應指出，為替換出人工變數而採用的主元消去，在主元的選擇上，並不要求遵守單純形法確定離進基變數的規則。
第二階段，就是從得到的基本可行解出發，用單純形方法求（4.2.1）的最優解。
例 4.2.1 用兩階段法求下列問題的最優解
≥213
0先引進鬆弛變數,把問題化成標準形式。由於此標準形式中約束方程的係數矩陣並不包含3階單位矩陣，因此還引進人工變數.下面先求解一階段問題：21
3≥0仍然用主元消去法,主元用框號標出.迭代過程如下:
由於所有判別數≤0，因此達到最優解。在一階段問題的最優解中，人工變數都是非基變數。這樣，我們得到初始基本可行解
第一階段結束後，修改最後的單純形表。去掉人工變數和下面的列（也可保留，但人工變數不能再進基），把最後的判別數行按原來問題進行修正。其他不變。
然後開始第二階段迭代，即極大化目標函式.迭代過程如下：
得到（4.2.5）的最優解（，）=（3，0），目標函式最優值
例4.2.2 用兩階段法求解下列問題24
00引進鬆弛變數，把上述問題化成標準形式，再引進人工變數,得到下列一階段問題：24
00 ，…，6
先用單純形法解一階段問題，迭代如下：
其中是目標函式中基變數的係數構成的維行向量，是上表中的第列，是上表中的右端列.
，取主元，經元消去得到下表：
再以為主元，進行主元消法，得到
這樣，基變數均為原來的變數，得到原來的問題的乙個基本可行解
再把表中人工變數對應的列去掉（也可保留，但人工變數不能再進基），並把判別數行增加進去。正如前面曾經指出過的那樣，初表中的判別數和目標函式值利用定義來計算，即
其中是目標函式中基變數的係數構成的維行向量，是上表
中的第列，是上表中的右端列。
第二階段的初表如下：
此表已是最優表。最優解是
目標函式值的最優值
例4.2.3 用兩階段法求解下列問題210
0引進人工變數。解第一階段問題：46
2100下面以**形式給出迭代過程：
第一階段問題已經達到最優解。人工變數均取零值，但人工變數是基變數，應從基中替換出去。
現在修正表中判別數行。由於和是基變數，相對的判別數均為零，只需計算非基變數對應的判別數：
在現行基本可行解處的目標函式值
去掉人工變數下面的列，得到第二階段的初始單純形表：
此表已是最優表。得到最優解
目標函式的最優值
在兩階段法的第二階段，可以保留人工變數下面的列，好處在於：最初單位矩陣所在的位置，在以後的每個單純形表中，總是存放現行基的逆。但必須注意，正如前面指出的，人工變數絕不可再進基。
4.2.2 **
**的基本思想是：在約束中增加人工變數，同時修改目標函式，加上罰項，其中是很大的正數，這樣，在極小化目標函式的過程中，由於大的存在，將迫使人工變數離基。我們仍考慮線性規劃問題
0 （4.2.6）
引進人工變數，研究下列問題：
4.2.7）
最優化案例
1蜂膠黃酮類化合物提取工藝引數優化 簡介 蜂膠中富含的黃酮類化合物等有效成份在超臨界流體co2 中的溶解度極低，因此在超臨界流體co2 萃取蜂膠黃酮類化合物的工藝實驗研究中，加入少量的乙醇溶劑作為夾帶劑，達到了大大增大蜂膠黃酮類化合物的溶解度的目的。本文將利用響應面分析方法，用多項式函式來近似解析描...
最優化方法綜述
1.引論 1.1應用介紹 最優化理論與演算法是乙個重要的數學分支，它所研究的問題是討論在眾多的方案中什麼樣的方案最優以及怎樣找出最優方案。這類問題普遍存在。例如，工程設計中怎樣選擇設計引數，使得設計方案滿足設計要求，又能降低成本 資源分配中，怎樣分配有限資源，使得分配方案既能滿足各方面的基本要求，又...
最優化技術總結
考點一 線性規劃 1.可行解 性規劃中，把滿足所有的約束條件的解稱為該線性規劃的可行解。把使得目標函式值最大的解稱為該線性規劃的最優解，此函式值稱為最優目標函式值簡稱最優值。2.性規劃中，乙個 約束條件中沒使用得資源或能力稱為鬆馳量。3.對於 約束條件可以增加一些最低限約束的超過量，稱為剩餘變數。4...