對標準型線性規劃
$$?\begin{array}{l}\text{minimize}{\mathbf{c}}^{?}\mathbf{x}\\ \text{s.t.????}\mathbf{Ax}=\mathbf{b}\\ \mathbf{x}\ge \mathbf{o}\end{array}(1)$$
其中$\mathbf{A}\in {\text{R}}^{m\times n}$，且rank$\mathbf{A}=m\le n$，$\mathbf{b}\ge \mathbf{o}$。假定$\mathbf{A}$中存在部分列向量${\mathbf{\alpha }}_{I_1},?,{\mathbf{\alpha }}_{I_{m_1}}$構成單位陣${\mathbf{I}}_m$的一部分。其中，$m_i\le m$。記$n_1=m?m_1$，$\mathbf{E}$為${\mathbf{I}}_m$中去掉${\mathbf{\alpha }}_{I_1},?,{\mathbf{\alpha }}_{I_{m_1}}$剩下的部分，則$\mathbf{E}\in {\text{R}}^{m\times n_1}$。引入人工變量${\mathbf{x}}_a\in {\text{R}}^{n_1}=\left(\begin{array}{c}{x}_{a_1}\\ ?\\ x_{a_{n_1}}\end{array}\right)$，令${\mathbf{A}}^{\prime }=(\mathbf{A},\mathbf{E})$，構造線性規劃
$$?\begin{array}{l}\text{minimize}{\mathbf{e}}^{?}{\mathbf{x}}_a\\ \text{s.t.????}{\mathbf{A}}^{\prime }\left(\begin{array}{c}\mathbf{x}\\ {\mathbf{x}}_a\end{array}\right)=\mathbf{Ax}+{\mathbf{Ex}}_a=\mathbf{b}\\ \mathbf{x},{\mathbf{x}}_a\ge \mathbf{o}\end{array}(2)$$
其中，$\mathbf{e}\in {\text{R}}^n$，所有元素均為1。(2)稱為線性規劃(1)的輔助線性規劃。輔助問題總有一個明顯的初始基矩陣：${\mathbf{A}}^{\prime }=(\mathbf{A},\mathbf{E})$的最后$m$列構成的單位陣${\mathbf{I}}_m$。
例1 標準型線性規劃
$$?\begin{array}{l}\text{minimize}?2x_1+x_2\\ \text{s.t.??}{x}_1+x_2?x_3=2\\ x_1?x_2?x_4=1\\ x_1+x_5=3\\ x_1,x_2,x_3,x_4,x_5\ge 0\end{array}.$$
其等式約束系數矩陣和常數向量
$$\mathbf{A}=\left(\begin{array}{ccccc}1& 1& ?1& 0& 0\\ 1& ?1& 0& ?1& 0\\ 1& 0& 0& 0& 1\end{array}\right),\mathbf{b}=\left(\begin{array}{c}2\\ 1\\ 3\end{array}\right).$$
其中，${\mathbf{\alpha }}_5$構成單位陣中一部分。添加人工變量$x_6,x_7$，構造其輔助線性規劃
$$?\begin{array}{l}\text{minimize}{x}_6+x_7\\ \text{s.t.??}{x}_1+x_5=3\\ x_1+x_2?x_3+x_6=2\\ x_1?x_2?x_4+x_7=1\\ x_1,x_2,x_3,x_4,x_5,x_6,x_7\ge 0\end{array}.$$
其等式約束系數矩陣為
$${\mathbf{A}}^{\prime }=(\mathbf{A},\mathbf{E})=\left(\begin{array}{ccccccc}1& 1& ?1& 0& 0& 1& 0\\ 1& ?1& 0& ?1& 0& 0& 1\\ 1& 0& 0& 0& 1& 0& 0\end{array}\right).$$
其中，$\mathbf{E}=({\mathbf{\alpha }}_6,{\mathbf{\alpha }}_7)=\left(\begin{array}{cc}1& 0\\ 0& 1\\ 0& 0\end{array}\right)$。顯然，$({\mathbf{\alpha }}_6,{\mathbf{\alpha }}_7,{\mathbf{\alpha }}_5)={\mathbf{I}}_3$成為輔助線性規劃的一個基矩陣。
下列代碼定義構造標準型線性規劃（1）的輔助問題（2）的Python函數。

import numpy as np									#導入numpy
def prepro(A):def find_e(A, ei):								#查找A中單位向量位置n = A.shape[1]j = 0while j < n:if(abs(A.T[j] - ei) < 1e-10).all():return jj += 1return -1m, n = A.shapepos = np.array([-1] * m)						#單位向量位置下標序列E = np.array([[]for i in range(m)])				#人工變量系數矩陣e = np.eye(m)									#單位陣i = 0k = 0while i < m:									#對每一個單位向量j = find_e(A, e[i])							#查找在A中位置if j >= 0:									#若在A中出現pos[i] = j								#記錄位置下標else:										#未在A中E = np.hstack((E, e[i].reshape(m, 1)))	#追加到Epos[i] = n + k							#記錄位置k += 1i += 1return E, pos

程序的第2~26行定義的prepro函數實現構造標準型線性規劃輔助問題的過程。其唯一的參數A表示標準型問題的系數矩陣$\mathbf{A}$。函數體內第12、13行分別將表示人工變量系數矩陣的E和單位向量在$(\mathbf{A},\mathbf{E})$中位置下標的序列的pos初始化為空集和$m$個$?1$的數組。第14行定義單位陣e，其中的每一個行向量e[i]構成一個單位向量。第17~25行的while循環確定每個單位向量e[i]在$(\mathbf{A},\mathbf{E})$中位置（或在A中，或追加于E），記錄于pos。其中，第18行調用的find_e函數在矩陣A中查找與單位向量e[i]。該函數是定義于第3~10行內部函數。若e[i]為A中的第j列，返回j，否則返回$?1$。本函數最終返回E和pos。
例2 用prepro構造
$$?\begin{array}{l}\text{minimize}?2x_1+x_2\\ \text{s.t.??}{x}_1+x_2?x_3=2\\ x_1?x_2?x_4=1\\ x_1+x_5=3\\ x_1,x_2,x_3,x_4,x_5\ge 0\end{array}.$$
的輔助問題的等式約束系數矩陣。
解： 根據例1的數據，下列程序完成計算

import numpy as np#導入numpy
from fractions import Fraction as F
np.set_printoptions(formatter={'all':lambda x:#設置輸出格式str(F(x).limit_denominator())})
A = np.array([[1, 1, -1, 0, 0],	#原問題系數矩陣[1, -1, 0, -1, 0],[1, 0, 0, 0, 1]])
E, pos = prepro(A)				#引入人工變量
print(E, pos)
A1 = np.hstack((A,E))
print(A1)

程序的第2~4行設置數據輸出格式。第5~7行設置原問題等式約束系數矩陣A。第8行調用prepro函數，傳遞A計算輔助系統中人工變量的系數矩陣E和輔助問題的初始基矩陣列向量下標集pos。第10行構造輔助問題等式約束系數矩陣。運行程序，輸出

[[1 0][0 1][0 0]] [5 6 4]
[[1 1 -1 0 0 1 0][1 -1 0 -1 0 0 1][1 0 0 0 1 0 0]]

意為輔助問題中人工變量的系數矩陣$\mathbf{E}=\left(\begin{array}{cc}1& 0\\ 0& 1\\ 0& 0\end{array}\right)$，初始基矩陣列向量為$({\mathbf{\alpha }}_6,{\mathbf{\alpha }}_7,{\mathbf{\alpha }}_5)$。輔助問題等式約束矩陣${\mathbf{A}}^{\prime }=(\mathbf{A},\mathbf{E})=\left(\begin{array}{ccccccc}1& 1& ?1& 0& 0& 1& 0\\ 1& ?1& 0& ?1& 0& 0& 1\\ 1& 0& 0& 0& 1& 0& 0\end{array}\right)$。與例1的計算結果一致。
輔助問題（2）由于其目標函數${\mathbf{e}}^{?}{\mathbf{x}}_a\ge 0$有下界，故必有最優解。輔助問題（2）與原問題（1）有如下的關系
定理1 標準型線性規劃(1)有可行解，當且僅當其輔助線性規劃(2)的最優解為${\mathbf{x}}_a^{?}=\mathbf{o}$。
對問題（1）運用單純形算法可算得其輔助問題(2)最優解${\mathbf{x}}^{?}=\left(\begin{array}{c}\mathbf{x}\\ {\mathbf{x}}_a\end{array}\right)$，求解過程稱為第一階段。按定理1，若${\mathbf{x}}_a=\mathbf{o}$則原問題(1)可行。并且，若${\mathbf{x}}^{?}$中的原問題決策變量部分$\mathbf{x}$恰巧是是(1)的基本可行解，即第一階段計算所得的輔助問題的基矩陣${\mathbf{B}}^{?}$恰包含在原問題（1）的系數矩陣$\mathbf{A}$中，則以此為起點，可運用單純形算法求解問題(1)，這一過程稱為第二階段。
例3 標準型線性規劃
$$?\begin{array}{l}\text{minimize}?2x_1+x_2\\ \text{s.t.??}{x}_1+x_2?x_3=2\\ x_1?x_2?x_4=1\\ x_1+x_5=3\\ x_1,x_2,x_3,x_4,x_5\ge 0\end{array}.$$
其目標函數系數向量$\mathbf{c}=\left(\begin{array}{c}?2\\ 1\\ 0\\ 0\\ 0\end{array}\right)$，等式約束系數矩陣和常數向量
$$\mathbf{A}=\left(\begin{array}{ccccc}1& 1& ?1& 0& 0\\ 1& ?1& 0& ?1& 0\\ 1& 0& 0& 0& 1\end{array}\right),\mathbf{b}=\left(\begin{array}{c}2\\ 1\\ 3\end{array}\right).$$
下列代碼求解該問題。

import numpy as np													#導入numpy
from fractions import Fraction as F									#設置輸出格式
np.set_printoptions(formatter={'all':lambda x:str(F(x).limit_denominator())})
A = np.array([[1, 1, -1, 0, 0],										#原問題數據設置[1, -1, 0, -1, 0],[1, 0, 0, 0, 1]])
b = np.array([2, 1, 3])
c = np.array([-1, 2, 0, 0, 0])
E, pos = prepro(A)													#構造輔助問題系數矩陣
A1 = np.hstack((A, E))
Bind = pos															#構造輔助問題初始基矩陣
Nind = np.setdiff1d(np.arange(5+E.shape[1]),Bind)
c1 = np.concatenate((np.zeros(5), np.ones(E.shape[1])), axis = 0)	#輔助問題目標函數系數
Bindst = simplex(A1, b, c1, Bind, Nind)								#求解輔助問題最優解
Nindst = np.setdiff1d(np.arange(5), Bindst)
Bst = A1[:, Bindst]													#輔助問題最優解基矩陣
Bst1 = np.linalg.inv(B)												#逆陣
xBst = np.matmul(Bst1,b.reshape(3, 1)).flatten()					#對應基矩陣最優解部分
x = np.zeros(5 + E.shape[1])
x[Bindst] = xBst													#輔助問題最優解
print('輔助問題最優解x=%s'%x)
print('輔助問題最優解對應的基矩陣向量下標：%s'%Bindst)					#輔助問題最優解基矩陣包含于原問題系數矩陣
Bind = simplex(A, b, c, Bindst, Nindst)								#求解原問題最優解
B = A[:, Bind]														#當前基矩陣
B1 = np.linalg.inv(B)												#逆陣
xB = np.matmul(B1,b.reshape(3, 1)).flatten()						#對應基矩陣最優解部分
x = np.zeros(5)
x[Bind] = xB														#原問題最優解
print('原問題最優解x=%s'%x)

程序的前14行與例2中的代碼一樣調用prepro構造原問題輔助問題。第15行調用博文《最優化方法Python計算：標準型線性規劃的單純形算法》定義的simplex函數求解輔助問題，完成第一階段計算。第17~22行計算并輸出輔助問題最優解。根據第15所得輔助問題最優解對應的基矩陣（第23行輸出）包含于原問題的系數矩陣中（見下列輸出），第18行調用simplex求解原問題，完成第二階段計算。運行程序，輸出

輔助問題最優解x=[3/2 1/2 0 0 3/2 0 0]
輔助問題最優解對應的基矩陣向量下標：[1 0 4]
原問題最優解x=[3 0 1 2 0]

注意輔助問題最優解中，人工變量$x_6=x_7=0$，故原問題可行。輔助問題最優解對應基矩陣列向量下標為2，1，5均含于原問題系數矩陣中，故可利用它直接求解原問題。
寫博不易，敬請支持：
如果閱讀本文于您有所獲，敬請點贊、評論、收藏，謝謝大家的支持！