scipy.optimize.

linprog#

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=(0, None), method='highs', callback=None, options=None, x0=None, integrality=None)[source]#

線性規劃：最小化受線性等式和不等式約束的線性目標函數。

線性規劃解決以下形式的問題

\[\begin{split}\min_x \ & c^T x \\ \mbox{such that} \ & A_{ub} x \leq b_{ub},\\ & A_{eq} x = b_{eq},\\ & l \leq x \leq u ,\end{split}\]

其中 \(x\) 是決策變數的向量；\(c\)、\(b_{ub}\)、\(b_{eq}\)、\(l\) 和 \(u\) 是向量；而 \(A_{ub}\) 和 \(A_{eq}\) 是矩陣。

或者，也就是

最小化
```
c @ x
```

受限於

A_ub @ x <= b_ub
A_eq @ x == b_eq
lb <= x <= ub

請注意，預設情況下 lb = 0 且 ub = None。其他邊界可以使用 bounds 指定。

參數:

c1-D 陣列

要最小化的線性目標函數的係數。

A_ub2-D 陣列，可選

不等式約束矩陣。A_ub 的每一列指定 x 上線性不等式約束的係數。

b_ub1-D 陣列，可選

不等式約束向量。每個元素代表 A_ub @ x 對應值的上限。

A_eq2-D 陣列，可選

等式約束矩陣。A_eq 的每一列指定 x 上線性等式約束的係數。

b_eq1-D 陣列，可選

等式約束向量。A_eq @ x 的每個元素必須等於 b_eq 的對應元素。

bounds序列，可選

每個 x 元素的一系列 (min, max) 對，定義該決策變數的最小值和最大值。如果提供單個元組 (min, max)，則 min 和 max 將作為所有決策變數的邊界。使用 None 表示沒有邊界。例如，預設邊界 (0, None) 表示所有決策變數均為非負數，而配對 (None, None) 表示完全沒有邊界，即允許所有變數為任何實數。

methodstr，可選

用於解決標準形式問題的演算法。支援以下方法。

舊版方法已被棄用，將在 SciPy 1.11.0 中移除。

callback可呼叫物件，可選

如果提供回呼函數，則在演算法的每次迭代中至少呼叫一次。回呼函數必須接受單個 scipy.optimize.OptimizeResult，其中包含以下欄位

x1-D 陣列

目前的解向量。

funfloat

目標函數 c @ x 的目前值。

successbool

當演算法成功完成時為 True。

slack1-D 陣列

鬆弛變數的（名義上為正值）值，b_ub - A_ub @ x。

con1-D 陣列

等式約束的（名義上為零）殘差，b_eq - A_eq @ x。

phaseint

正在執行的演算法階段。

statusint

表示演算法狀態的整數。

0 : 最佳化正常進行中。

1 : 達到迭代次數限制。

2 : 問題似乎不可行。

3 : 問題似乎無界。

4 : 遇到數值困難。

nitint

目前的迭代次數。

messagestr

演算法狀態的字串描述符。

HiGHS 方法目前不支援回呼函數。

optionsdict，可選

求解器選項的字典。所有方法都接受以下選項

maxiterint: 要執行的最大迭代次數。預設值：請參閱特定於方法的文檔。
dispbool: 設定為 True 以列印收斂訊息。預設值：False。
presolvebool: 設定為 False 以停用自動預解。預設值：True。

除了 HiGHS 求解器之外，所有方法也接受

tolfloat

一個容差，用於確定殘差何時「足夠接近」於零以被視為完全為零。

autoscalebool

設定為 True 以自動執行均衡化。如果約束中的數值相差多個數量級，請考慮使用此選項。預設值：False。

rrbool

設定為 False 以停用自動冗餘移除。預設值：True。

rr_methodstring

用於在預解後識別和移除等式約束矩陣中冗餘列的方法。對於具有密集輸入的問題，可用於冗餘移除的方法有

SVD:: 在矩陣上重複執行奇異值分解，根據與零奇異值對應的左奇異向量中的非零值偵測冗餘列。當矩陣接近滿秩時，速度可能很快。
pivot:: 使用 [5] 中提出的演算法來識別冗餘列。
ID:: 使用隨機插值分解。識別未在矩陣的滿秩插值分解中使用的矩陣轉置列。
None:: 如果矩陣接近滿秩，即矩陣秩與列數之差小於五，則使用 svd。否則，使用 pivot。此預設值的行為可能會在不事先通知的情況下變更。

預設值：None。對於具有稀疏輸入的問題，此選項將被忽略，並且使用 [5] 中提出的基於樞軸的演算法。

有關特定於方法的選項，請參閱 show_options('linprog')。

x01-D 陣列，可選

決策變數的猜測值，將由最佳化演算法精煉。此引數目前僅由 ‘revised simplex’ 方法使用，並且僅當 x0 代表基本可行解時才能使用。

integrality1-D 陣列或 int，可選

指示每個決策變數的整數約束類型。

0 : 連續變數；無整數約束。

1 : 整數變數；決策變數必須是 bounds 範圍內的整數。

2 : 半連續變數；決策變數必須在 bounds 範圍內或取值 0。

3 : 半整數變數；決策變數必須是 bounds 範圍內的整數或取值 0。

預設情況下，所有變數都是連續的。

對於混合整數約束，請提供形狀為 c.shape 的陣列。若要從較短的輸入推斷每個決策變數的約束，則會使用 numpy.broadcast_to 將引數廣播到 c.shape。

此引數目前僅由 ‘highs’ 方法使用，否則將被忽略。

返回:

resOptimizeResult

一個 scipy.optimize.OptimizeResult，其中包含以下欄位。請注意，欄位的返回類型可能取決於最佳化是否成功，因此建議在依賴其他欄位之前檢查 OptimizeResult.status

x1-D 陣列

最小化目標函數同時滿足約束的決策變數值。

funfloat

目標函數 c @ x 的最佳值。

slack1-D 陣列

鬆弛變數的（名義上為正值）值，b_ub - A_ub @ x。

con1-D 陣列

等式約束的（名義上為零）殘差，b_eq - A_eq @ x。

successbool

當演算法成功找到最佳解時為 True。

statusint

表示演算法退出狀態的整數。

0 : 最佳化成功終止。

1 : 達到迭代次數限制。

2 : 問題似乎不可行。

3 : 問題似乎無界。

4 : 遇到數值困難。

nitint

所有階段中執行的總迭代次數。

messagestr

演算法退出狀態的字串描述符。

另請參閱

show_options: 求解器接受的其他選項。

註解

本節描述了可通過 'method' 參數選擇的可用求解器。

‘highs-ds’ 和 ‘highs-ipm’ 分別是 HiGHS 單純形法和內點法求解器 [13] 的介面。‘highs’ (預設) 在兩者之間自動選擇。這些是 SciPy 中最快的線性規劃求解器，特別是對於大型稀疏問題；其中哪一個更快取決於問題。其他求解器是舊版方法，當 HiGHS 方法支援 callback 時將被移除。

方法 ‘highs-ds’ 是 C++ 高效能對偶修正單純形法實作 (HSOL) [13], [14] 的封裝。方法 ‘highs-ipm’ 是 interior-point method [13] 的 C++ 實作的封裝；它具有交叉例程，因此它與單純形求解器一樣準確。方法 ‘highs’ 在兩者之間自動選擇。對於涉及 linprog 的新程式碼，我們建議明確選擇這三種方法值之一。

在 1.6.0 版本中新增。

方法 ‘interior-point’ 使用 [4] 中概述的原始對偶路徑追蹤演算法。此演算法支援稀疏約束矩陣，並且通常比單純形法更快，特別是對於大型稀疏問題。但是請注意，返回的解可能比單純形法的解略微不準確，並且通常不會與約束定義的多面體的頂點對應。

在 1.0.0 版本中新增。

方法 ‘revised simplex’ 使用 [9] 中描述的修正單純形法，除了有效地維護基矩陣的因式分解 [11] 而不是其逆矩陣，並用於解決演算法每次迭代中的線性系統。

在 1.3.0 版本中新增。

方法 ‘simplex’ 使用 Dantzig 單純形演算法 [1], [2] 的傳統完整表格實作（不是 Nelder-Mead 單純形法）。包含此演算法是為了向後相容性和教育目的。

在 0.15.0 版本中新增。

在應用 ‘interior-point’、‘revised simplex’ 或 ‘simplex’ 之前，基於 [8] 的預解程序嘗試識別微不足道的可行性問題、微不足道的無界性以及潛在的問題簡化。具體來說，它會檢查

A_eq 或 A_ub 中的零列，表示微不足道的約束；
A_eq 和 A_ub 中的零列，表示不受約束的變數；
A_eq 中的單列，表示固定變數；以及
A_ub 中的單列，表示簡單邊界。

如果預解顯示問題是無界的（例如，不受約束且無界的變數具有負成本）或不可行的（例如，A_eq 中的零列對應於 b_eq 中的非零值），則求解器會以適當的狀態碼終止。請注意，預解會在偵測到任何無界性跡象時立即終止；因此，當問題實際上不可行時（但尚未偵測到不可行性），可能會將問題報告為無界。因此，如果知道問題是否確實不可行很重要，請使用選項 presolve=False 再次解決問題。

如果在預解的單次傳遞中未偵測到不可行性或無界性，則會在可能的情況下收緊邊界，並從問題中移除固定變數。然後，移除 A_eq 矩陣的線性相關列（除非它們表示不可行性），以避免主求解例程中的數值困難。請注意，也可能會移除幾乎線性相關的列（在規定的容差範圍內），這在極少數情況下可能會改變最佳解。如果這是一個問題，請從您的問題公式中消除冗餘，並使用選項 rr=False 或 presolve=False 執行。

這裡可以進行幾項潛在的改進：應實作 [8] 中概述的其他預解檢查，預解例程應執行多次（直到無法再進行簡化），並且應在冗餘移除例程中實作更多來自 [5] 的效率改進。

預解後，透過將（收緊的）簡單邊界轉換為上限約束、為不等式約束引入非負鬆弛變數以及將無界變數表示為兩個非負變數之間的差值，將問題轉換為標準形式。或者，可以透過均衡化 [12] 自動縮放問題。選定的演算法解決標準形式問題，而後處理例程將結果轉換為原始問題的解。

參考文獻

[1]

Dantzig, George B., Linear programming and extensions. Rand Corporation Research Study Princeton Univ. Press, Princeton, NJ, 1963

[2]

Hillier, S.H. and Lieberman, G.J. (1995), “Introduction to Mathematical Programming”, McGraw-Hill, Chapter 4.

[3]

Bland, Robert G. New finite pivoting rules for the simplex method. Mathematics of Operations Research (2), 1977: pp. 103-107.

[4]

Andersen, Erling D., and Knud D. Andersen. “The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm.” High performance optimization. Springer US, 2000. 197-232.

[5] (1,2,3)

Andersen, Erling D. “Finding all linearly dependent rows in large-scale linear programming.” Optimization Methods and Software 6.3 (1995): 219-227.

[6]

Freund, Robert M. “Primal-Dual Interior-Point Methods for Linear Programming based on Newton’s Method.” Unpublished Course Notes, March 2004. Available 2/25/2017 at https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec14_int_pt_mthd.pdf

[7]

Fourer, Robert. “Solving Linear Programs by Interior-Point Methods.” Unpublished Course Notes, August 26, 2005. Available 2/25/2017 at http://www.4er.org/CourseNotes/Book%20B/B-III.pdf

[8] (1,2)

Andersen, Erling D., and Knud D. Andersen. “Presolving in linear programming.” Mathematical Programming 71.2 (1995): 221-245.

[9]

Bertsimas, Dimitris, and J. Tsitsiklis. “Introduction to linear programming.” Athena Scientific 1 (1997): 997.

[10]

Andersen, Erling D., et al. Implementation of interior point methods for large scale linear programming. HEC/Universite de Geneve, 1996.

[11]

Bartels, Richard H. “A stabilization of the simplex method.” Journal in Numerische Mathematik 16.5 (1971): 414-434.

[12]

Tomlin, J. A. “On scaling linear programming problems.” Mathematical Programming Study 4 (1975): 146-166.

[13] (1,2,3)

Huangfu, Q., Galabova, I., Feldmeier, M., and Hall, J. A. J. “HiGHS - high performance software for linear optimization.” https://highs.dev/

[14]

Huangfu, Q. and Hall, J. A. J. “Parallelizing the dual revised simplex method.” Mathematical Programming Computation, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5

範例

考慮以下問題

\[\begin{split}\min_{x_0, x_1} \ -x_0 + 4x_1 & \\ \mbox{such that} \ -3x_0 + x_1 & \leq 6,\\ -x_0 - 2x_1 & \geq -4,\\ x_1 & \geq -3.\end{split}\]

此問題未以 linprog 接受的形式呈現。透過將「大於」不等式約束乘以 \(-1\) 的因數，可以輕鬆地補救此問題，將其轉換為「小於」不等式約束。另請注意，最後一個約束實際上是簡單邊界 \(-3 \leq x_1 \leq \infty\)。最後，由於 \(x_0\) 沒有邊界，因此我們必須明確指定邊界 \(-\infty \leq x_0 \leq \infty\)，因為預設情況下變數是非負數。在將係數收集到陣列和元組後，此問題的輸入為

>>> from scipy.optimize import linprog
>>> c = [-1, 4]
>>> A = [[-3, 1], [1, 2]]
>>> b = [6, 4]
>>> x0_bounds = (None, None)
>>> x1_bounds = (-3, None)
>>> res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds])
>>> res.fun
-22.0
>>> res.x
array([10., -3.])
>>> res.message
'Optimization terminated successfully. (HiGHS Status 7: Optimal)'

邊際值（又名對偶值 / 影子價格 / 拉格朗日乘數）和殘差（鬆弛）也可用。

>>> res.ineqlin
  residual: [ 3.900e+01  0.000e+00]
 marginals: [-0.000e+00 -1.000e+00]

例如，由於與第二個不等式約束相關的邊際值為 -1，因此如果我們在第二個不等式約束的右側新增少量 eps，我們預期目標函數的最佳值會減少 eps

>>> eps = 0.05
>>> b[1] += eps
>>> linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds]).fun
-22.05

此外，由於第一個不等式約束的殘差為 39，因此我們可以在不影響最佳解的情況下，將第一個約束的右側減少 39。

>>> b = [6, 4]  # reset to original values
>>> b[0] -= 39
>>> linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds]).fun
-22.0