linprog(method=’highs-ds’)#

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)

線性規劃：使用 HiGHS 對偶單純形法求解器，最小化受線性等式和不等式約束的線性目標函數。

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

\[\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

請注意，預設情況下，除非使用 bounds 指定，否則 lb = 0 且 ub = None。

參數:

c1 維陣列: 要最小化的線性目標函數的係數。
A_ub2 維陣列，選用: 不等式約束矩陣。A_ub 的每一列指定了對 x 的線性不等式約束的係數。
b_ub1 維陣列，選用: 不等式約束向量。每個元素代表 A_ub @ x 相應值的上限。
A_eq2 維陣列，選用: 等式約束矩陣。A_eq 的每一列指定了對 x 的線性等式約束的係數。
b_eq1 維陣列，選用: 等式約束向量。A_eq @ x 的每個元素必須等於 b_eq 的相應元素。
bounds序列，選用: 一個 (min, max) 對的序列，用於 x 中的每個元素，定義該決策變數的最小值和最大值。使用 None 表示沒有邊界。預設情況下，邊界為 (0, None) (所有決策變數均為非負數)。如果提供單個元組 (min, max)，則 min 和 max 將作為所有決策變數的邊界。
method字串: 這是 ‘highs-ds’ 方法的專用文件。‘highs’、‘highs-ipm’、‘interior-point’ (預設值)、‘revised simplex’ 和 ‘simplex’ (舊版) 也可用。

回傳值:

resOptimizeResult

一個由欄位組成的 scipy.optimize.OptimizeResult

x1 維陣列

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

fun浮點數

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

slack1 維陣列

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

con1 維陣列

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

success布林值

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

status整數

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

0 : 最佳化成功終止。

1 : 達到迭代或時間限制。

2 : 問題似乎不可行。

3 : 問題似乎無界。

4 : HiGHS 求解器遇到問題。

message字串

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

nit整數

執行的總迭代次數。這包括所有階段的迭代。

crossover_nit整數

對於 HiGHS 單純形法，這始終為 0。對於 HiGHS 內點法，這是交叉例程期間執行的原始/對偶推進次數。

ineqlinOptimizeResult

對應於不等式約束 b_ub 的解和靈敏度資訊。一個由欄位組成的字典

residualnp.ndnarray: 鬆弛變數的（名義上為正值）值，b_ub - A_ub @ x。此數量也常被稱為“鬆弛”。
marginalsnp.ndarray: 目標函數對於不等式約束 b_ub 右側的靈敏度（偏導數）。

eqlinOptimizeResult

對應於等式約束 b_eq 的解和靈敏度資訊。一個由欄位組成的字典

residualnp.ndarray: 等式約束的殘差（名義上為零），b_eq - A_eq @ x。
marginalsnp.ndarray: 目標函數對於等式約束 b_eq 右側的靈敏度（偏導數）。

lower, upperOptimizeResult

對應於決策變數的下限和上限 bounds 的解和靈敏度資訊。

residualnp.ndarray: 數量 x - lb (下限) 或 ub - x (上限) 的（名義上為正值）值。
marginalsnp.ndarray: 目標函數對於下限和上限 bounds 的靈敏度（偏導數）。

另請參閱

有關其餘參數的文件，請參閱 scipy.optimize.linprog

選項:

——-

maxiter整數

在任一階段中要執行的最大迭代次數。預設值是平台上 int 的最大可能值。

disp布林值 (預設值: False)

如果要在最佳化期間將最佳化狀態的指示器列印到控制台，則設定為 True。

presolve布林值 (預設值: True)

預先求解嘗試識別微不足道的可行性問題、識別微不足道的無界性，並在將問題發送給主求解器之前簡化問題。通常建議保持預設設定 True；如果要停用預先求解，則設定為 False。

time_limit浮點數

分配用於解決問題的最長時間（以秒為單位）；預設值是平台上 double 的最大可能值。

dual_feasibility_tolerance雙精度浮點數 (預設值: 1e-07)

‘highs-ds’ 的對偶可行性容差。

primal_feasibility_tolerance雙精度浮點數 (預設值: 1e-07)

‘highs-ds’ 的原始可行性容差。

simplex_dual_edge_weight_strategy字串 (預設值: None)

單純形對偶邊權重的策略。預設值 None 會自動選擇以下其中一項。

'dantzig' 使用 Dantzig 的原始策略，選擇最負的降低成本。

'devex' 使用 [15] 中描述的策略。

steepest 使用 [16] 中描述的精確最陡邊策略。

'steepest-devex' 從精確最陡邊策略開始，直到計算成本過高或不精確，然後切換到 devex 方法。

目前，None 始終選擇 'steepest-devex'，但隨著新選項的推出，這可能會改變。

unknown_options字典

此特定求解器未使用的選用引數。如果 unknown_options 為非空，則會發出警告，列出所有未使用的選項。

註解

方法 ‘highs-ds’ 是 C++ 高效能對偶修訂單純形法實作 (HSOL) [13]、[14] 的包裝器。方法 ‘highs-ipm’ 是內點法的 C++ 實作 [13] 的包裝器；它具有交叉例程，因此其準確性與單純形法求解器相同。方法 ‘highs’ 會自動在兩者之間選擇。對於涉及 linprog 的新程式碼，我們建議明確選擇這三種方法值之一，而不是 ‘interior-point’ (預設值)、‘revised simplex’ 和 ‘simplex’ (舊版)。

結果欄位 ineqlin、eqlin、lower 和 upper 都包含 marginals，或目標函數對於每個約束條件右側的偏導數。這些偏導數也稱為“拉格朗日乘數”、“對偶值”和“影子價格”。marginals 的符號慣例與許多非線性求解器產生的拉格朗日乘數的符號慣例相反。

參考文獻

[13] (1,2)

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

[15]

Harris, Paula MJ. “Pivot selection methods of the Devex LP code.” Mathematical programming 5.1 (1973): 1-28.

[16]

Goldfarb, Donald, and John Ker Reid. “A practicable steepest-edge simplex algorithm.” Mathematical Programming 12.1 (1977): 361-371.