首先，找規(guī)律。每行都是從1開始，最大的數(shù)是 相應(yīng)的行號(hào)。這樣可以得到 1 2 3 4 5 6 7 8 nums = 3 for x in range(1, nums+1): print range(1, x) # 這樣就輸出了，如下 [1, ] [1, 2, ] [1, 2, 3, ] 然后，繼續(xù)。 剩下的是前面序列的反轉(zhuǎn)
創(chuàng)新互聯(lián)公司堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的伊美網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！
最優(yōu)化
為什么要做最優(yōu)化呢？因?yàn)樵谏钪?，人們總是希望幸福值或其它達(dá)到一個(gè)極值，比如做生意時(shí)希望成本最小，收入最大，所以在很多商業(yè)情境中，都會(huì)遇到求極值的情況。
函數(shù)求根
這里「函數(shù)的根」也稱「方程的根」，或「函數(shù)的零點(diǎn)」。
先把我們需要的包加載進(jìn)來(lái)。import numpy as npimport scipy as spimport scipy.optimize as optimport matplotlib.pyplot as plt%matplotlib inline
函數(shù)求根和最優(yōu)化的關(guān)系？什么時(shí)候函數(shù)是最小值或最大值？
兩個(gè)問(wèn)題一起回答：最優(yōu)化就是求函數(shù)的最小值或最大值，同時(shí)也是極值，在求一個(gè)函數(shù)最小值或最大值時(shí)，它所在的位置肯定是導(dǎo)數(shù)為 0 的位置，所以要求一個(gè)函數(shù)的極值，必然要先求導(dǎo)，使其為 0，所以函數(shù)求根就是為了得到最大值最小值。
scipy.optimize 有什么方法可以求根？
可以用 scipy.optimize 中的 bisect 或 brentq 求根。f = lambda x: np.cos(x) - x # 定義一個(gè)匿名函數(shù)x = np.linspace(-5, 5, 1000) # 先生成 1000 個(gè) xy = f(x) # 對(duì)應(yīng)生成 1000 個(gè) f(x)plt.plot(x, y); # 看一下這個(gè)函數(shù)長(zhǎng)什么樣子plt.axhline(0, color='k'); # 畫一根橫線，位置在 y=0
opt.bisect(f, -5, 5) # 求取函數(shù)的根0.7390851332155535plt.plot(x, y)plt.axhline(0, color='k')plt.scatter([_], [0], c='r', s=100); # 這里的 [_] 表示上一個(gè) Cell 中的結(jié)果，這里是 x 軸上的位置，0 是 y 上的位置
求根有兩種方法，除了上面介紹的 bisect，還有 brentq，后者比前者快很多。%timeit opt.bisect(f, -5, 5)%timeit opt.brentq(f, -5, 5)10000 loops, best of 3: 157 s per loopThe slowest run took 11.65 times longer than the fastest. This could mean that an intermediate result is being cached.10000 loops, best of 3: 35.9 s per loop
函數(shù)求最小化
求最小值就是一個(gè)最優(yōu)化問(wèn)題。求最大值時(shí)只需對(duì)函數(shù)做一個(gè)轉(zhuǎn)換，比如加一個(gè)負(fù)號(hào)，或者取倒數(shù)，就可轉(zhuǎn)成求最小值問(wèn)題。所以兩者是同一問(wèn)題。
初始值對(duì)最優(yōu)化的影響是什么？
舉例來(lái)說(shuō)，先定義個(gè)函數(shù)。f = lambda x: 1-np.sin(x)/xx = np.linspace(-20., 20., 1000)y = f(x)
當(dāng)初始值為 3 值，使用 minimize 函數(shù)找到最小值。minimize 函數(shù)是在新版的 scipy 里，取代了以前的很多最優(yōu)化函數(shù)，是個(gè)通用的接口，背后是很多方法在支撐。x0 = 3xmin = opt.minimize(f, x0).x # x0 是起始點(diǎn)，起始點(diǎn)最好離真正的最小值點(diǎn)不要太遠(yuǎn)plt.plot(x, y)plt.scatter(x0, f(x0), marker='o', s=300); # 起始點(diǎn)畫出來(lái)，用圓圈表示plt.scatter(xmin, f(xmin), marker='v', s=300); # 最小值點(diǎn)畫出來(lái)，用三角表示plt.xlim(-20, 20);
初始值為 3 時(shí)，成功找到最小值。
現(xiàn)在來(lái)看看初始值為 10 時(shí)，找到的最小值點(diǎn)。x0 = 10xmin = opt.minimize(f, x0).xplt.plot(x, y)plt.scatter(x0, f(x0), marker='o', s=300)plt.scatter(xmin, f(xmin), marker='v', s=300)plt.xlim(-20, 20);
由上圖可見(jiàn)，當(dāng)初始值為 10 時(shí)，函數(shù)找到的是局部最小值點(diǎn)，可見(jiàn) minimize 的默認(rèn)算法對(duì)起始點(diǎn)的依賴性。
那么怎么才能不管初始值在哪個(gè)位置，都能找到全局最小值點(diǎn)呢？
如何找到全局最優(yōu)點(diǎn)？
可以使用 basinhopping 函數(shù)找到全局最優(yōu)點(diǎn)，相關(guān)背后算法，可以看幫助文件，有提供論文的索引和出處。
我們?cè)O(shè)初始值為 10 看是否能找到全局最小值點(diǎn)。x0 = 10from scipy.optimize import basinhoppingxmin = basinhopping(f,x0,stepsize = 5).xplt.plot(x, y);plt.scatter(x0, f(x0), marker='o', s=300);plt.scatter(xmin, f(xmin), marker='v', s=300);plt.xlim(-20, 20);
當(dāng)起始點(diǎn)在比較遠(yuǎn)的位置，依然成功找到了全局最小值點(diǎn)。
如何求多元函數(shù)最小值？
以二元函數(shù)為例，使用 minimize 求對(duì)應(yīng)的最小值。def g(X): x,y = X return (x-1)**4 + 5 * (y-1)**2 - 2*x*yX_opt = opt.minimize(g, (8, 3)).x # (8,3) 是起始點(diǎn)print X_opt[ 1.88292611 1.37658521]fig, ax = plt.subplots(figsize=(6, 4)) # 定義畫布和圖形x_ = y_ = np.linspace(-1, 4, 100)X, Y = np.meshgrid(x_, y_)c = ax.contour(X, Y, g((X, Y)), 50) # 等高線圖ax.plot(X_opt[0], X_opt[1], 'r*', markersize=15) # 最小點(diǎn)的位置是個(gè)元組ax.set_xlabel(r"$x_1$", fontsize=18)ax.set_ylabel(r"$x_2$", fontsize=18)plt.colorbar(c, ax=ax) # colorbar 表示顏色越深，高度越高fig.tight_layout()
畫3D 圖。from mpl_toolkits.mplot3d import Axes3Dfrom matplotlib import cmfig = plt.figure()ax = fig.gca(projection='3d')x_ = y_ = np.linspace(-1, 4, 100)X, Y = np.meshgrid(x_, y_)surf = ax.plot_surface(X, Y, g((X,Y)), rstride=1, cstride=1, cmap=cm.coolwarm, linewidth=0, antialiased=False)cset = ax.contour(X, Y, g((X,Y)), zdir='z',offset=-5, cmap=cm.coolwarm)fig.colorbar(surf, shrink=0.5, aspect=5);
曲線擬合
曲線擬合和最優(yōu)化有什么關(guān)系？
曲線擬合的問(wèn)題是，給定一組數(shù)據(jù)，它可能是沿著一條線散布的，這時(shí)要找到一條最優(yōu)的曲線來(lái)擬合這些數(shù)據(jù)，也就是要找到最好的線來(lái)代表這些點(diǎn)，這里的最優(yōu)是指這些點(diǎn)和線之間的距離是最小的，這就是為什么要用最優(yōu)化問(wèn)題來(lái)解決曲線擬合問(wèn)題。
舉例說(shuō)明，給一些點(diǎn)，找到一條線，來(lái)擬合這些點(diǎn)。
先給定一些點(diǎn)：N = 50 # 點(diǎn)的個(gè)數(shù)m_true = 2 # 斜率b_true = -1 # 截距dy = 2.0 # 誤差np.random.seed(0)xdata = 10 * np.random.random(N) # 50 個(gè) x，服從均勻分布ydata = np.random.normal(b_true + m_true * xdata, dy) # dy 是標(biāo)準(zhǔn)差plt.errorbar(xdata, ydata, dy, fmt='.k', ecolor='lightgray');
上面的點(diǎn)整體上呈現(xiàn)一個(gè)線性關(guān)系，要找到一條斜線來(lái)代表這些點(diǎn)，這就是經(jīng)典的一元線性回歸。目標(biāo)就是找到最好的線，使點(diǎn)和線的距離最短。要優(yōu)化的函數(shù)是點(diǎn)和線之間的距離，使其最小。點(diǎn)是確定的，而線是可變的，線是由參數(shù)值，斜率和截距決定的，這里就是要通過(guò)優(yōu)化距離找到最優(yōu)的斜率和截距。
點(diǎn)和線的距離定義如下：def chi2(theta, x, y): return np.sum(((y - theta[0] - theta[1] * x)) ** 2)
上式就是誤差平方和。
誤差平方和是什么？有什么作用？
誤差平方和公式為：
誤差平方和大，表示真實(shí)的點(diǎn)和預(yù)測(cè)的線之間距離太遠(yuǎn)，說(shuō)明擬合得不好，最好的線，應(yīng)該是使誤差平方和最小，即最優(yōu)的擬合線，這里是條直線。
誤差平方和就是要最小化的目標(biāo)函數(shù)。
找到最優(yōu)的函數(shù)，即斜率和截距。theta_guess = [0, 1] # 初始值theta_best = opt.minimize(chi2, theta_guess, args=(xdata, ydata)).xprint(theta_best)[-1.01442005 1.93854656]
上面兩個(gè)輸出即是預(yù)測(cè)的直線斜率和截距，我們是根據(jù)點(diǎn)來(lái)反推直線的斜率和截距，那么真實(shí)的斜率和截距是多少呢？-1 和 2，很接近了，差的一點(diǎn)是因?yàn)橛性胍舻囊?。xfit = np.linspace(0, 10)yfit = theta_best[0] + theta_best[1] * xfitplt.errorbar(xdata, ydata, dy, fmt='.k', ecolor='lightgray');plt.plot(xfit, yfit, '-k');
最小二乘（Least Square）是什么？
上面用的是 minimize 方法，這個(gè)問(wèn)題的目標(biāo)函數(shù)是誤差平方和，這就又有一個(gè)特定的解法，即最小二乘。
最小二乘的思想就是要使得觀測(cè)點(diǎn)和估計(jì)點(diǎn)的距離的平方和達(dá)到最小，這里的“二乘”指的是用平方來(lái)度量觀測(cè)點(diǎn)與估計(jì)點(diǎn)的遠(yuǎn)近（在古漢語(yǔ)中“平方”稱為“二乘”），“最小”指的是參數(shù)的估計(jì)值要保證各個(gè)觀測(cè)點(diǎn)與估計(jì)點(diǎn)的距離的平方和達(dá)到最小。
關(guān)于最小二乘估計(jì)的計(jì)算，涉及更多的數(shù)學(xué)知識(shí)，這里不想詳述，其一般的過(guò)程是用目標(biāo)函數(shù)對(duì)各參數(shù)求偏導(dǎo)數(shù)，并令其等于 0，得到一個(gè)線性方程組。具體推導(dǎo)過(guò)程可參考斯坦福機(jī)器學(xué)習(xí)講義 第 7 頁(yè)。def deviations(theta, x, y): return (y - theta[0] - theta[1] * x)theta_best, ier = opt.leastsq(deviations, theta_guess, args=(xdata, ydata))print(theta_best)[-1.01442016 1.93854659]
最小二乘 leastsq 的結(jié)果跟 minimize 結(jié)果一樣。注意 leastsq 的第一個(gè)參數(shù)不再是誤差平方和 chi2，而是誤差本身 deviations，即沒(méi)有平方，也沒(méi)有和。yfit = theta_best[0] + theta_best[1] * xfitplt.errorbar(xdata, ydata, dy, fmt='.k', ecolor='lightgray');plt.plot(xfit, yfit, '-k');
非線性最小二乘
上面是給一些點(diǎn)，擬合一條直線，擬合一條曲線也是一樣的。def f(x, beta0, beta1, beta2): # 首先定義一個(gè)非線性函數(shù)，有 3 個(gè)參數(shù) return beta0 + beta1 * np.exp(-beta2 * x**2)beta = (0.25, 0.75, 0.5) # 先猜 3 個(gè) betaxdata = np.linspace(0, 5, 50)y = f(xdata, *beta)ydata = y + 0.05 * np.random.randn(len(xdata)) # 給 y 加噪音def g(beta): return ydata - f(xdata, *beta) # 真實(shí) y 和 預(yù)測(cè)值的差，求最優(yōu)曲線時(shí)要用到beta_start = (1, 1, 1)beta_opt, beta_cov = opt.leastsq(g, beta_start)print beta_opt # 求到的 3 個(gè)最優(yōu)的 beta 值[ 0.25525709 0.74270226 0.54966466]
拿估計(jì)的 beta_opt 值跟真實(shí)的 beta = (0.25, 0.75, 0.5) 值比較，差不多。fig, ax = plt.subplots()ax.scatter(xdata, ydata) # 畫點(diǎn)ax.plot(xdata, y, 'r', lw=2) # 真實(shí)值的線ax.plot(xdata, f(xdata, *beta_opt), 'b', lw=2) # 擬合的線ax.set_xlim(0, 5)ax.set_xlabel(r"$x$", fontsize=18)ax.set_ylabel(r"$f(x, \beta)$", fontsize=18)fig.tight_layout()
除了使用最小二乘，還可以使用曲線擬合的方法，得到的結(jié)果是一樣的。beta_opt, beta_cov = opt.curve_fit(f, xdata, ydata)print beta_opt[ 0.25525709 0.74270226 0.54966466]
有約束的最小化
有約束的最小化是指，要求函數(shù)最小化之外，還要滿足約束條件，舉例說(shuō)明。
邊界約束def f(X): x, y = X return (x-1)**2 + (y-1)**2 # 這是一個(gè)碗狀的函數(shù)x_opt = opt.minimize(f, (0, 0), method='BFGS').x # 無(wú)約束最優(yōu)化
假設(shè)有約束條件，x 和 y 要在一定的范圍內(nèi)，如 x 在 2 到 3 之間，y 在 0 和 2 之間。bnd_x1, bnd_x2 = (2, 3), (0, 2) # 對(duì)自變量的約束x_cons_opt = opt.minimize(f, np.array([0, 0]), method='L-BFGS-B', bounds=[bnd_x1, bnd_x2]).x # bounds 矩形約束fig, ax = plt.subplots(figsize=(6, 4))x_ = y_ = np.linspace(-1, 3, 100)X, Y = np.meshgrid(x_, y_)c = ax.contour(X, Y, f((X,Y)), 50)ax.plot(x_opt[0], x_opt[1], 'b*', markersize=15) # 沒(méi)有約束下的最小值，藍(lán)色五角星ax.plot(x_cons_opt[0], x_cons_opt[1], 'r*', markersize=15) # 有約束下的最小值，紅色星星bound_rect = plt.Rectangle((bnd_x1[0], bnd_x2[0]), bnd_x1[1] - bnd_x1[0], bnd_x2[1] - bnd_x2[0], facecolor="grey")ax.add_patch(bound_rect)ax.set_xlabel(r"$x_1$", fontsize=18)ax.set_ylabel(r"$x_2$", fontsize=18)plt.colorbar(c, ax=ax)fig.tight_layout()
不等式約束
介紹下相關(guān)理論，先來(lái)看下存在等式約束的極值問(wèn)題求法，比如下面的優(yōu)化問(wèn)題。
目標(biāo)函數(shù)是 f(w)，下面是等式約束，通常解法是引入拉格朗日算子，這里使用 ββ 來(lái)表示算子，得到拉格朗日公式為
l 是等式約束的個(gè)數(shù)。
然后分別對(duì) w 和ββ 求偏導(dǎo)，使得偏導(dǎo)數(shù)等于 0，然后解出 w 和βiβi，至于為什么引入拉格朗日算子可以求出極值，原因是 f(w) 的 dw 變化方向受其他不等式的約束，dw的變化方向與f(w)的梯度垂直時(shí)才能獲得極值，而且在極值處，f(w) 的梯度與其他等式梯度的線性組合平行，因此他們之間存在線性關(guān)系。（參考《最優(yōu)化與KKT條件》）
對(duì)于不等式約束的極值問(wèn)題
常常利用拉格朗日對(duì)偶性將原始問(wèn)題轉(zhuǎn)換為對(duì)偶問(wèn)題，通過(guò)解對(duì)偶問(wèn)題而得到原始問(wèn)題的解。該方法應(yīng)用在許多統(tǒng)計(jì)學(xué)習(xí)方法中。有興趣的可以參閱相關(guān)資料，這里不再贅述。def f(X): return (X[0] - 1)**2 + (X[1] - 1)**2def g(X): return X[1] - 1.75 - (X[0] - 0.75)**4x_opt = opt.minimize(f, (0, 0), method='BFGS').xconstraints = [dict(type='ineq', fun=g)] # 約束采用字典定義，約束方式為不等式約束，邊界用 g 表示x_cons_opt = opt.minimize(f, (0, 0), method='SLSQP', constraints=constraints).xfig, ax = plt.subplots(figsize=(6, 4))x_ = y_ = np.linspace(-1, 3, 100)X, Y = np.meshgrid(x_, y_)c = ax.contour(X, Y, f((X, Y)), 50)ax.plot(x_opt[0], x_opt[1], 'b*', markersize=15) # 藍(lán)色星星，沒(méi)有約束下的最小值ax.plot(x_, 1.75 + (x_-0.75)**4, '', markersize=15)ax.fill_between(x_, 1.75 + (x_-0.75)**4, 3, color="grey")ax.plot(x_cons_opt[0], x_cons_opt[1], 'r*', markersize=15) # 在區(qū)域約束下的最小值ax.set_ylim(-1, 3)ax.set_xlabel(r"$x_0$", fontsize=18)ax.set_ylabel(r"$x_1$", fontsize=18)plt.colorbar(c, ax=ax)fig.tight_layout()
scipy.optimize.minimize 中包括了多種最優(yōu)化算法，每種算法使用范圍不同，詳細(xì)參考官方文檔。
想象一下，您有一個(gè)線性方程組和不等式系統(tǒng)。這樣的系統(tǒng)通常有許多可能的解決方案。線性規(guī)劃是一組數(shù)學(xué)和計(jì)算工具，可讓您找到該系統(tǒng)的特定解，該解對(duì)應(yīng)于某些其他線性函數(shù)的最大值或最小值。
混合整數(shù)線性規(guī)劃是 線性規(guī)劃 的擴(kuò)展。它處理至少一個(gè)變量采用離散整數(shù)而不是連續(xù)值的問(wèn)題。盡管乍一看混合整數(shù)問(wèn)題與連續(xù)變量問(wèn)題相似，但它們?cè)陟`活性和精度方面具有顯著優(yōu)勢(shì)。
整數(shù)變量對(duì)于正確表示自然用整數(shù)表示的數(shù)量很重要，例如生產(chǎn)的飛機(jī)數(shù)量或服務(wù)的客戶數(shù)量。
一種特別重要的整數(shù)變量是 二進(jìn)制變量 。它只能取 零 或 一 的值，在做出是或否的決定時(shí)很有用，例如是否應(yīng)該建造工廠或者是否應(yīng)該打開或關(guān)閉機(jī)器。您還可以使用它們來(lái)模擬邏輯約束。
線性規(guī)劃是一種基本的優(yōu)化技術(shù)，已在科學(xué)和數(shù)學(xué)密集型領(lǐng)域使用了數(shù)十年。它精確、相對(duì)快速，適用于一系列實(shí)際應(yīng)用。
混合整數(shù)線性規(guī)劃允許您克服線性規(guī)劃的許多限制。您可以使用分段線性函數(shù)近似非線性函數(shù)、使用半連續(xù)變量、模型邏輯約束等。它是一種計(jì)算密集型工具，但計(jì)算機(jī)硬件和軟件的進(jìn)步使其每天都更加適用。
通常，當(dāng)人們?cè)噲D制定和解決優(yōu)化問(wèn)題時(shí)，第一個(gè)問(wèn)題是他們是否可以應(yīng)用線性規(guī)劃或混合整數(shù)線性規(guī)劃。
以下文章說(shuō)明了線性規(guī)劃和混合整數(shù)線性規(guī)劃的一些用例：
隨著計(jì)算機(jī)能力的增強(qiáng)、算法的改進(jìn)以及更多用戶友好的軟件解決方案的出現(xiàn)，線性規(guī)劃，尤其是混合整數(shù)線性規(guī)劃的重要性隨著時(shí)間的推移而增加。
解決線性規(guī)劃問(wèn)題的基本方法稱為，它有多種變體。另一種流行的方法是。
混合整數(shù)線性規(guī)劃問(wèn)題可以通過(guò)更復(fù)雜且計(jì)算量更大的方法來(lái)解決，例如，它在幕后使用線性規(guī)劃。這種方法的一些變體是，它涉及使用 切割平面 ，以及。
有幾種適用于線性規(guī)劃和混合整數(shù)線性規(guī)劃的合適且眾所周知的 Python 工具。其中一些是開源的，而另一些是專有的。您是否需要免費(fèi)或付費(fèi)工具取決于問(wèn)題的規(guī)模和復(fù)雜性，以及對(duì)速度和靈活性的需求。
值得一提的是，幾乎所有廣泛使用的線性規(guī)劃和混合整數(shù)線性規(guī)劃庫(kù)都是以 Fortran 或 C 或 C++ 原生和編寫的。這是因?yàn)榫€性規(guī)劃需要對(duì)（通常很大）矩陣進(jìn)行計(jì)算密集型工作。此類庫(kù)稱為求解器。Python 工具只是求解器的包裝器。
Python 適合圍繞本機(jī)庫(kù)構(gòu)建包裝器，因?yàn)樗梢院芎玫嘏c C/C++ 配合使用。對(duì)于本教程，您不需要任何 C/C++（或 Fortran），但如果您想了解有關(guān)此酷功能的更多信息，請(qǐng)查看以下資源：
基本上，當(dāng)您定義和求解模型時(shí)，您使用 Python 函數(shù)或方法調(diào)用低級(jí)庫(kù)，該庫(kù)執(zhí)行實(shí)際優(yōu)化工作并將解決方案返回給您的 Python 對(duì)象。
幾個(gè)免費(fèi)的 Python 庫(kù)專門用于與線性或混合整數(shù)線性規(guī)劃求解器交互：
在本教程中，您將使用SciPy和PuLP來(lái)定義和解決線性規(guī)劃問(wèn)題。
在本節(jié)中，您將看到線性規(guī)劃問(wèn)題的兩個(gè)示例：
您將在下一節(jié)中使用 Python 來(lái)解決這兩個(gè)問(wèn)題。
考慮以下線性規(guī)劃問(wèn)題：
你需要找到X和?使得紅色，藍(lán)色和黃色的不平等，以及不平等X 0和? 0，是滿意的。同時(shí)，您的解決方案必須對(duì)應(yīng)于z的最大可能值。
您需要找到的自變量（在本例中為 x 和 y ）稱為 決策變量 。要最大化或最小化的決策變量的函數(shù)（在本例中為 z） 稱為 目標(biāo)函數(shù) 、 成本函數(shù) 或僅稱為 目標(biāo) 。您需要滿足的 不等式 稱為 不等式約束 。您還可以在稱為 等式約束 的約束中使用方程。
這是您如何可視化問(wèn)題的方法：
紅線代表的功能2 X + Y = 20，和它上面的紅色區(qū)域示出了紅色不等式不滿足。同樣，藍(lán)線是函數(shù) 4 x + 5 y = 10，藍(lán)色區(qū)域被禁止，因?yàn)樗`反了藍(lán)色不等式。黃線是 x + 2 y = 2，其下方的黃色區(qū)域是黃色不等式無(wú)效的地方。
如果您忽略紅色、藍(lán)色和黃色區(qū)域，則僅保留灰色區(qū)域?；疑珔^(qū)域的每個(gè)點(diǎn)都滿足所有約束，是問(wèn)題的潛在解決方案。該區(qū)域稱為 可行域 ，其點(diǎn)為 可行解 。在這種情況下，有無(wú)數(shù)可行的解決方案。
您想最大化z。對(duì)應(yīng)于最大z的可行解是 最優(yōu)解 。如果您嘗試最小化目標(biāo)函數(shù)，那么最佳解決方案將對(duì)應(yīng)于其可行的最小值。
請(qǐng)注意，z是線性的。你可以把它想象成一個(gè)三維空間中的平面。這就是為什么最優(yōu)解必須在可行區(qū)域的 頂點(diǎn) 或角上的原因。在這種情況下，最佳解決方案是紅線和藍(lán)線相交的點(diǎn)，稍后您將看到。
有時(shí)，可行區(qū)域的整個(gè)邊緣，甚至整個(gè)區(qū)域，都可以對(duì)應(yīng)相同的z值。在這種情況下，您有許多最佳解決方案。
您現(xiàn)在已準(zhǔn)備好使用綠色顯示的附加等式約束來(lái)擴(kuò)展問(wèn)題：
方程式 x + 5 y = 15，以綠色書寫，是新的。這是一個(gè)等式約束。您可以通過(guò)向上一張圖像添加相應(yīng)的綠線來(lái)將其可視化：
現(xiàn)在的解決方案必須滿足綠色等式，因此可行區(qū)域不再是整個(gè)灰色區(qū)域。它是綠線從與藍(lán)線的交點(diǎn)到與紅線的交點(diǎn)穿過(guò)灰色區(qū)域的部分。后一點(diǎn)是解決方案。
如果插入x的所有值都必須是整數(shù)的要求，那么就會(huì)得到一個(gè)混合整數(shù)線性規(guī)劃問(wèn)題，可行解的集合又會(huì)發(fā)生變化：
您不再有綠線，只有沿線的x值為整數(shù)的點(diǎn)?？尚薪馐腔疑尘吧系木G點(diǎn)，此時(shí)最優(yōu)解離紅線最近。
這三個(gè)例子說(shuō)明了 可行的線性規(guī)劃問(wèn)題 ，因?yàn)樗鼈兙哂杏薪缈尚袇^(qū)域和有限解。
如果沒(méi)有解，線性規(guī)劃問(wèn)題是 不可行的 。當(dāng)沒(méi)有解決方案可以同時(shí)滿足所有約束時(shí)，通常會(huì)發(fā)生這種情況。
例如，考慮如果添加約束x + y 1會(huì)發(fā)生什么。那么至少有一個(gè)決策變量（x或y）必須是負(fù)數(shù)。這與給定的約束x 0 和y 0相沖突。這樣的系統(tǒng)沒(méi)有可行的解決方案，因此稱為不可行的。
另一個(gè)示例是添加與綠線平行的第二個(gè)等式約束。這兩行沒(méi)有共同點(diǎn)，因此不會(huì)有滿足這兩個(gè)約束的解決方案。
一個(gè)線性規(guī)劃問(wèn)題是 無(wú)界的 ，如果它的可行區(qū)域是無(wú)界，將溶液不是有限。這意味著您的變量中至少有一個(gè)不受約束，可以達(dá)到正無(wú)窮大或負(fù)無(wú)窮大，從而使目標(biāo)也無(wú)限大。
例如，假設(shè)您采用上面的初始問(wèn)題并刪除紅色和黃色約束。從問(wèn)題中刪除約束稱為 放松 問(wèn)題。在這種情況下，x和y不會(huì)在正側(cè)有界。您可以將它們?cè)黾拥秸裏o(wú)窮大，從而產(chǎn)生無(wú)限大的z值。
在前面的部分中，您研究了一個(gè)與任何實(shí)際應(yīng)用程序無(wú)關(guān)的抽象線性規(guī)劃問(wèn)題。在本小節(jié)中，您將找到與制造業(yè)資源分配相關(guān)的更具體和實(shí)用的優(yōu)化問(wèn)題。
假設(shè)一家工廠生產(chǎn)四種不同的產(chǎn)品，第一種產(chǎn)品的日產(chǎn)量為x ?，第二種產(chǎn)品的產(chǎn)量為x 2，依此類推。目標(biāo)是確定每種產(chǎn)品的利潤(rùn)最大化日產(chǎn)量，同時(shí)牢記以下條件：
數(shù)學(xué)模型可以這樣定義：
目標(biāo)函數(shù)（利潤(rùn)）在條件 1 中定義。人力約束遵循條件 2。對(duì)原材料 A 和 B 的約束可以從條件 3 和條件 4 中通過(guò)對(duì)每種產(chǎn)品的原材料需求求和得出。
最后，產(chǎn)品數(shù)量不能為負(fù)，因此所有決策變量必須大于或等于零。
與前面的示例不同，您無(wú)法方便地將其可視化，因?yàn)樗兴膫€(gè)決策變量。但是，無(wú)論問(wèn)題的維度如何，原理都是相同的。
在本教程中，您將使用兩個(gè)Python 包來(lái)解決上述線性規(guī)劃問(wèn)題：
SciPy 設(shè)置起來(lái)很簡(jiǎn)單。安裝后，您將擁有開始所需的一切。它的子包 scipy.optimize 可用于線性和非線性優(yōu)化。
PuLP 允許您選擇求解器并以更自然的方式表述問(wèn)題。PuLP 使用的默認(rèn)求解器是COIN-OR Branch and Cut Solver (CBC)。它連接到用于線性松弛的COIN-OR 線性規(guī)劃求解器 (CLP)和用于切割生成的COIN-OR 切割生成器庫(kù) (CGL)。
另一個(gè)偉大的開源求解器是GNU 線性規(guī)劃工具包 (GLPK)。一些著名且非常強(qiáng)大的商業(yè)和專有解決方案是Gurobi、CPLEX和XPRESS。
除了在定義問(wèn)題時(shí)提供靈活性和運(yùn)行各種求解器的能力外，PuLP 使用起來(lái)不如 Pyomo 或 CVXOPT 等替代方案復(fù)雜，后者需要更多的時(shí)間和精力來(lái)掌握。
要學(xué)習(xí)本教程，您需要安裝 SciPy 和 PuLP。下面的示例使用 SciPy 1.4.1 版和 PuLP 2.1 版。
您可以使用pip以下方法安裝兩者：
您可能需要運(yùn)行pulptest或sudo pulptest啟用 PuLP 的默認(rèn)求解器，尤其是在您使用 Linux 或 Mac 時(shí)：
或者，您可以下載、安裝和使用 GLPK。它是免費(fèi)和開源的，適用于 Windows、MacOS 和 Linux。在本教程的后面部分，您將看到如何將 GLPK（除了 CBC）與 PuLP 一起使用。
在 Windows 上，您可以下載檔案并運(yùn)行安裝文件。
在 MacOS 上，您可以使用 Homebrew：
在 Debian 和 Ubuntu 上，使用apt來(lái)安裝glpk和glpk-utils：
在Fedora，使用dnf具有g(shù)lpk-utils：
您可能還會(huì)發(fā)現(xiàn)conda對(duì)安裝 GLPK 很有用：
安裝完成后，可以查看GLPK的版本：
有關(guān)詳細(xì)信息，請(qǐng)參閱 GLPK 關(guān)于使用Windows 可執(zhí)行文件和Linux 軟件包進(jìn)行安裝的教程。
在本節(jié)中，您將學(xué)習(xí)如何使用 SciPy優(yōu)化和求根庫(kù)進(jìn)行線性規(guī)劃。
要使用 SciPy 定義和解決優(yōu)化問(wèn)題，您需要導(dǎo)入scipy.optimize.linprog()：
現(xiàn)在您已經(jīng)linprog()導(dǎo)入，您可以開始優(yōu)化。
讓我們首先解決上面的線性規(guī)劃問(wèn)題：
linprog()僅解決最小化（而非最大化）問(wèn)題，并且不允許具有大于或等于符號(hào) ( ) 的不等式約束。要解決這些問(wèn)題，您需要在開始優(yōu)化之前修改您的問(wèn)題：
引入這些更改后，您將獲得一個(gè)新系統(tǒng)：
該系統(tǒng)與原始系統(tǒng)等效，并且將具有相同的解決方案。應(yīng)用這些更改的唯一原因是克服 SciPy 與問(wèn)題表述相關(guān)的局限性。
下一步是定義輸入值：
您將上述系統(tǒng)中的值放入適當(dāng)?shù)牧斜?、元組或NumPy 數(shù)組中：
注意：請(qǐng)注意行和列的順序！
約束左側(cè)和右側(cè)的行順序必須相同。每一行代表一個(gè)約束。
來(lái)自目標(biāo)函數(shù)和約束左側(cè)的系數(shù)的順序必須匹配。每列對(duì)應(yīng)一個(gè)決策變量。
下一步是以與系數(shù)相同的順序定義每個(gè)變量的界限。在這種情況下，它們都在零和正無(wú)窮大之間：
此語(yǔ)句是多余的，因?yàn)閘inprog()默認(rèn)情況下采用這些邊界（零到正無(wú)窮大）。
注：相反的float("inf")，你可以使用math.inf，numpy.inf或scipy.inf。
最后，是時(shí)候優(yōu)化和解決您感興趣的問(wèn)題了。你可以這樣做linprog()：
參數(shù)c是指來(lái)自目標(biāo)函數(shù)的系數(shù)。A_ub和b_ub分別與不等式約束左邊和右邊的系數(shù)有關(guān)。同樣，A_eq并b_eq參考等式約束。您可以使用bounds提供決策變量的下限和上限。
您可以使用該參數(shù)method來(lái)定義要使用的線性規(guī)劃方法。有以下三種選擇：
linprog() 返回具有以下屬性的數(shù)據(jù)結(jié)構(gòu)：
您可以分別訪問(wèn)這些值：
這就是您獲得優(yōu)化結(jié)果的方式。您還可以以圖形方式顯示它們：
如前所述，線性規(guī)劃問(wèn)題的最優(yōu)解位于可行區(qū)域的頂點(diǎn)。在這種情況下，可行區(qū)域只是藍(lán)線和紅線之間的綠線部分。最優(yōu)解是代表綠線和紅線交點(diǎn)的綠色方塊。
如果要排除相等（綠色）約束，只需刪除參數(shù)A_eq并b_eq從linprog()調(diào)用中刪除：
解決方案與前一種情況不同。你可以在圖表上看到：
在這個(gè)例子中，最優(yōu)解是紅色和藍(lán)色約束相交的可行（灰色）區(qū)域的紫色頂點(diǎn)。其他頂點(diǎn)，如黃色頂點(diǎn)，具有更高的目標(biāo)函數(shù)值。
您可以使用 SciPy 來(lái)解決前面部分所述的資源分配問(wèn)題：
和前面的例子一樣，你需要從上面的問(wèn)題中提取必要的向量和矩陣，將它們作為參數(shù)傳遞給.linprog()，然后得到結(jié)果：
結(jié)果告訴您最大利潤(rùn)是1900并且對(duì)應(yīng)于x ? = 5 和x ? = 45。在給定條件下生產(chǎn)第二和第四個(gè)產(chǎn)品是沒(méi)有利潤(rùn)的。您可以在這里得出幾個(gè)有趣的結(jié)論：
opt.statusis0和opt.successis True，說(shuō)明優(yōu)化問(wèn)題成功求解，最優(yōu)可行解。
SciPy 的線性規(guī)劃功能主要用于較小的問(wèn)題。對(duì)于更大和更復(fù)雜的問(wèn)題，您可能會(huì)發(fā)現(xiàn)其他庫(kù)更適合，原因如下：
幸運(yùn)的是，Python 生態(tài)系統(tǒng)為線性編程提供了幾種替代解決方案，這些解決方案對(duì)于更大的問(wèn)題非常有用。其中之一是 PuLP，您將在下一節(jié)中看到它的實(shí)際應(yīng)用。
PuLP 具有比 SciPy 更方便的線性編程 API。您不必在數(shù)學(xué)上修改您的問(wèn)題或使用向量和矩陣。一切都更干凈，更不容易出錯(cuò)。
像往常一樣，您首先導(dǎo)入您需要的內(nèi)容：
現(xiàn)在您已經(jīng)導(dǎo)入了 PuLP，您可以解決您的問(wèn)題。
您現(xiàn)在將使用 PuLP 解決此系統(tǒng)：
第一步是初始化一個(gè)實(shí)例LpProblem來(lái)表示你的模型：
您可以使用該sense參數(shù)來(lái)選擇是執(zhí)行最小化（LpMinimize或1，這是默認(rèn)值）還是最大化（LpMaximize或-1）。這個(gè)選擇會(huì)影響你的問(wèn)題的結(jié)果。
一旦有了模型，就可以將決策變量定義為L(zhǎng)pVariable類的實(shí)例：
您需要提供下限，lowBound=0因?yàn)槟J(rèn)值為負(fù)無(wú)窮大。該參數(shù)upBound定義了上限，但您可以在此處省略它，因?yàn)樗J(rèn)為正無(wú)窮大。
可選參數(shù)cat定義決策變量的類別。如果您使用的是連續(xù)變量，則可以使用默認(rèn)值"Continuous"。
您可以使用變量x和y創(chuàng)建表示線性表達(dá)式和約束的其他 PuLP 對(duì)象：
當(dāng)您將決策變量與標(biāo)量相乘或構(gòu)建多個(gè)決策變量的線性組合時(shí)，您會(huì)得到一個(gè)pulp.LpAffineExpression代表線性表達(dá)式的實(shí)例。
注意：您可以增加或減少變量或表達(dá)式，你可以乘他們常數(shù)，因?yàn)榧垵{類實(shí)現(xiàn)一些Python的特殊方法，即模擬數(shù)字類型一樣__add__()，__sub__()和__mul__()。這些方法用于像定制運(yùn)營(yíng)商的行為+，-和*。
類似地，您可以將線性表達(dá)式、變量和標(biāo)量與運(yùn)算符 ==、=以獲取表示模型線性約束的紙漿.LpConstraint實(shí)例。
注：也有可能與豐富的比較方法來(lái)構(gòu)建的約束.__eq__()，.__le__()以及.__ge__()定義了運(yùn)營(yíng)商的行為==，=。
考慮到這一點(diǎn)，下一步是創(chuàng)建約束和目標(biāo)函數(shù)并將它們分配給您的模型。您不需要?jiǎng)?chuàng)建列表或矩陣。只需編寫 Python 表達(dá)式并使用+=運(yùn)算符將它們附加到模型中：
在上面的代碼中，您定義了包含約束及其名稱的元組。LpProblem允許您通過(guò)將約束指定為元組來(lái)向模型添加約束。第一個(gè)元素是一個(gè)LpConstraint實(shí)例。第二個(gè)元素是該約束的可讀名稱。
設(shè)置目標(biāo)函數(shù)非常相似：
或者，您可以使用更短的符號(hào)：
現(xiàn)在您已經(jīng)添加了目標(biāo)函數(shù)并定義了模型。
注意：您可以使用運(yùn)算符將 約束或目標(biāo)附加到模型中，+=因?yàn)樗念怢pProblem實(shí)現(xiàn)了特殊方法.__iadd__()，該方法用于指定 的行為+=。
對(duì)于較大的問(wèn)題，lpSum()與列表或其他序列一起使用通常比重復(fù)+運(yùn)算符更方便。例如，您可以使用以下語(yǔ)句將目標(biāo)函數(shù)添加到模型中：
它產(chǎn)生與前一條語(yǔ)句相同的結(jié)果。
您現(xiàn)在可以看到此模型的完整定義：
模型的字符串表示包含所有相關(guān)數(shù)據(jù)：變量、約束、目標(biāo)及其名稱。
注意：字符串表示是通過(guò)定義特殊方法構(gòu)建的.__repr__()。有關(guān) 的更多詳細(xì)信息.__repr__()，請(qǐng)查看Pythonic OOP 字符串轉(zhuǎn)換：__repr__vs__str__ .
最后，您已準(zhǔn)備好解決問(wèn)題。你可以通過(guò)調(diào)用.solve()你的模型對(duì)象來(lái)做到這一點(diǎn)。如果要使用默認(rèn)求解器 (CBC)，則不需要傳遞任何參數(shù)：
.solve()調(diào)用底層求解器，修改model對(duì)象，并返回解決方案的整數(shù)狀態(tài)，1如果找到了最優(yōu)解。有關(guān)其余狀態(tài)代碼，請(qǐng)參閱LpStatus[]。
你可以得到優(yōu)化結(jié)果作為 的屬性model。該函數(shù)value()和相應(yīng)的方法.value()返回屬性的實(shí)際值：
model.objective持有目標(biāo)函數(shù)model.constraints的值，包含松弛變量的值，以及對(duì)象x和y具有決策變量的最優(yōu)值。model.variables()返回一個(gè)包含決策變量的列表：
如您所見(jiàn)，此列表包含使用 的構(gòu)造函數(shù)創(chuàng)建的確切對(duì)象LpVariable。
結(jié)果與您使用 SciPy 獲得的結(jié)果大致相同。
注意：注意這個(gè)方法.solve()——它會(huì)改變對(duì)象的狀態(tài)，x并且y！
您可以通過(guò)調(diào)用查看使用了哪個(gè)求解器.solver：
輸出通知您求解器是 CBC。您沒(méi)有指定求解器，因此 PuLP 調(diào)用了默認(rèn)求解器。
如果要運(yùn)行不同的求解器，則可以將其指定為 的參數(shù).solve()。例如，如果您想使用 GLPK 并且已經(jīng)安裝了它，那么您可以solver=GLPK(msg=False)在最后一行使用。請(qǐng)記住，您還需要導(dǎo)入它：
現(xiàn)在你已經(jīng)導(dǎo)入了 GLPK，你可以在里面使用它.solve()：
該msg參數(shù)用于顯示來(lái)自求解器的信息。msg=False禁用顯示此信息。如果要包含信息，則只需省略msg或設(shè)置msg=True。
您的模型已定義并求解，因此您可以按照與前一種情況相同的方式檢查結(jié)果：
使用 GLPK 得到的結(jié)果與使用 SciPy 和 CBC 得到的結(jié)果幾乎相同。
一起來(lái)看看這次用的是哪個(gè)求解器：
正如您在上面用突出顯示的語(yǔ)句定義的那樣model.solve(solver=GLPK(msg=False))，求解器是 GLPK。
您還可以使用 PuLP 來(lái)解決混合整數(shù)線性規(guī)劃問(wèn)題。要定義整數(shù)或二進(jìn)制變量，只需傳遞cat="Integer"或cat="Binary"到LpVariable。其他一切都保持不變：
在本例中，您有一個(gè)整數(shù)變量并獲得與之前不同的結(jié)果：
Nowx是一個(gè)整數(shù)，如模型中所指定。（從技術(shù)上講，它保存一個(gè)小數(shù)點(diǎn)后為零的浮點(diǎn)值。）這一事實(shí)改變了整個(gè)解決方案。讓我們?cè)趫D表上展示這一點(diǎn)：
如您所見(jiàn)，最佳解決方案是灰色背景上最右邊的綠點(diǎn)。這是兩者的最大價(jià)值的可行的解決方案x和y，給它的最大目標(biāo)函數(shù)值。
GLPK 也能夠解決此類問(wèn)題。
現(xiàn)在你可以使用 PuLP 來(lái)解決上面的資源分配問(wèn)題：
定義和解決問(wèn)題的方法與前面的示例相同：
在這種情況下，您使用字典 x來(lái)存儲(chǔ)所有決策變量。這種方法很方便，因?yàn)樽值淇梢詫Q策變量的名稱或索引存儲(chǔ)為鍵，將相應(yīng)的LpVariable對(duì)象存儲(chǔ)為值。列表或元組的LpVariable實(shí)例可以是有用的。
上面的代碼產(chǎn)生以下結(jié)果：
如您所見(jiàn)，該解決方案與使用 SciPy 獲得的解決方案一致。最有利可圖的解決方案是每天生產(chǎn)5.0第一件產(chǎn)品和45.0第三件產(chǎn)品。
讓我們把這個(gè)問(wèn)題變得更復(fù)雜和有趣。假設(shè)由于機(jī)器問(wèn)題，工廠無(wú)法同時(shí)生產(chǎn)第一種和第三種產(chǎn)品。在這種情況下，最有利可圖的解決方案是什么？
現(xiàn)在您有另一個(gè)邏輯約束：如果x ? 為正數(shù)，則x ? 必須為零，反之亦然。這是二元決策變量非常有用的地方。您將使用兩個(gè)二元決策變量y ? 和y ?，它們將表示是否生成了第一個(gè)或第三個(gè)產(chǎn)品：
除了突出顯示的行之外，代碼與前面的示例非常相似。以下是差異：
這是解決方案：
事實(shí)證明，最佳方法是排除第一種產(chǎn)品而只生產(chǎn)第三種產(chǎn)品。
就像有許多資源可以幫助您學(xué)習(xí)線性規(guī)劃和混合整數(shù)線性規(guī)劃一樣，還有許多具有 Python 包裝器的求解器可用。這是部分列表：
其中一些庫(kù)，如 Gurobi，包括他們自己的 Python 包裝器。其他人使用外部包裝器。例如，您看到可以使用 PuLP 訪問(wèn) CBC 和 GLPK。
您現(xiàn)在知道什么是線性規(guī)劃以及如何使用 Python 解決線性規(guī)劃問(wèn)題。您還了解到 Python 線性編程庫(kù)只是本機(jī)求解器的包裝器。當(dāng)求解器完成其工作時(shí)，包裝器返回解決方案狀態(tài)、決策變量值、松弛變量、目標(biāo)函數(shù)等。
SciPy 里面的子函數(shù)庫(kù)optimize， 一般情況下可用curve_fit函數(shù)直接擬合或者leastsq做最小二乘
重慶分公司
重慶分公司
