我正在嘗試為自己制作一個小腳本或一些可以幫助我找到達到目標值集所需的最少組合數量的東西。但是我很難找到一種方法來做到這一點，因為我只能找到類似的問題，但只有一個總和，而不是一組數字。
考慮這張表：
| X | Y | Z
A | 4 4
B | 5 5
C | 4 4
D | 3 3 3
A、B、C、D 是不同的集合，產生不同數量的 X、Y、Z。
現在假設我們的目標是 40X、80Y、60Z。
通過手動試錯，我能找到的最低組合是 21 個，并且有多種變體可以達到這個目標。
例如：0A, 9B, 7C, 5D = 43X, 88Y, 60Z 還有 1A, 8B, 6C, 6D = 46X, 82Y, 62Z
兩者都是有效的，因為它們都使用了 21 種組合并達到了目標值。有些稍微超過了，但沒關系，重要的部分是最少的組數，而不低于任何目標值。
我的問題：我將如何確定 21 是否是可能的最低值，如果不是，那么會給出更低數量的組合是什么？
uj5u.com熱心網友回復：
浮點解決方案
這是一個非常經典的線性規劃問題。
問題可以表述為：
最小化：
qA qB qC qD在約束下：
qA * 4 qC * 4 qD * 3 >= 40;qB * 5 qC * 4 qD * 3 >= 80;qA * 4 qB * 5 qD * 3 >= 60.qA >= 0, qB >= 0, qC >= 0, qD >= 0.
在 python 中，有scipy.optimize.linprog哪些可以為您解決這些問題。
- https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html
from scipy.optimize import linprog
from numpy import array
c = array([1, 1, 1, 1])
A_ub = -array([[4,0,4,3],[0,5,4,3],[4,5,0,3]])
b_ub = -array([40, 80, 60])
res = linprog(c, A_ub=A_ub, b_ub=b_ub)
print('Results')
print('qA, qB, qC, qD =', res.x)
print('qA qB qC qD =', res.fun)
輸出：
qA, qB, qC, qD = [0. 8. 5. 6.66666667]
qA qB qC qD = 19.666666666666668
整數解
如果你想要額外的約束qA,qB,qC,qD是整數，那么我們有一個整數線性規劃問題，而不是一個簡單的線性規劃問題。
整數線性規劃看起來類似于連續線性規劃；但在引擎蓋下：
- 使用實數線性代數可以有效地解決連續線性問題；
- 解決整數線性問題需要解決 NP-hard 組合問題。
然而，整數線性問題被如此廣泛地使用，以至于盡管有 NP-hard 理論，但試圖解決實際問題的優化技術已經被開發并編譯成非常有效的編程庫。在一般情況下，這是一個 NP-hard 問題，當值變大時會變得難以處理，這是不可能的。但是對于你的小例子，它仍然很容易。
scipy.optimize.linprog您必須使用專用的混合整數線性編程庫，例如PuLP ，而不是使用。
我們將定義與之前相同的向量和矩陣，以表示目標函式和約束。但是，紙漿還允許使用符號方程而不是矩陣的公式，這可能更容易閱讀，具體取決于您的口味。
from pulp import LpProblem, LpMinimize, LpInteger, LpVariable
from pulp import LpStatus, value
problem = LpProblem('Minimum Combination', LpMinimize)
qA = LpVariable("quantity of A", 0, None, LpInteger)
qB = LpVariable("quantity of B", 0, None, LpInteger)
qC = LpVariable("quantity of C", 0, None, LpInteger)
qD = LpVariable("quantity of D", 0, None, LpInteger)
problem = qA qB qC qD, 'Number of multisets'
problem = qA * 4 qC * 4 qD * 3 >= 40, 'X target'
problem = qB * 5 qC * 4 qD * 3 >= 80, 'Y target'
problem = qA * 4 qB * 5 qD * 3 >= 60, 'Z target'
problem.solve()
print("Status:", LpStatus[problem.status])
for q in problem.variables():
print(q.name, "=", q.varValue)
print("Total number of multisets = ", value(problem.objective))
輸出：
Status: Optimal
quantity_of_A = 0
quantity_of_B = 8
quantity_of_C = 5
quantity_of_D = 7
Total number of multisets = 20
從連續到整數？
如果您從我們找到的連續解 開始scipy.optimize.linprog，(0,8,5,6.6667)然后將所有變數四舍五入為整數，那么您將得到整數問題的解，(0,8,5,7)。
在這種情況下，該解恰好與 找到的整數問題的最優解相同pulp。
但是，總的來說：
- 將連續問題的解四舍五入給出整數問題的解；但
- 不能保證對連續問題的最優解進行四舍五入會給出整數問題的最優解。
所以，在這種情況下，如果我們只使用 scipy 然后將變數四舍五入，我們就會知道有一個目標值為 20 的解，這已經比你找到的 21 好；但我們不知道 20 是否是最優的。
通過使用紙漿，我們確保 20 確實是最佳的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/512741.html
標籤：Python数学计算
上一篇：射線柱相交公式