想象壹下，您有壹個線性方程組和不等式系統。這樣的系統通常有許多可能的解決方案。線性規劃是壹組數學和計算工具，可讓您找到該系統的特定解，該解對應於某些其他線性函數的最大值或最小值。
混合整數線性規劃是 線性規劃 的擴展。它處理至少壹個變量采用離散整數而不是連續值的問題。盡管乍壹看混合整數問題與連續變量問題相似，但它們在靈活性和精度方面具有顯著優勢。
整數變量對於正確表示自然用整數表示的數量很重要，例如生產的飛機數量或服務的客戶數量。
壹種特別重要的整數變量是 二進制變量 。它只能取 零 或 壹 的值，在做出是或否的決定時很有用，例如是否應該建造工廠或者是否應該打開或關閉機器。您還可以使用它們來模擬邏輯約束。
線性規劃是壹種基本的優化技術，已在科學和數學密集型領域使用了數十年。它精確、相對快速，適用於壹系列實際應用。
混合整數線性規劃允許您克服線性規劃的許多限制。您可以使用分段線性函數近似非線性函數、使用半連續變量、模型邏輯約束等。它是壹種計算密集型工具，但計算機硬件和軟件的進步使其每天都更加適用。
通常，當人們試圖制定和解決優化問題時，第壹個問題是他們是否可以應用線性規劃或混合整數線性規劃。
以下文章說明了線性規劃和混合整數線性規劃的壹些用例：
隨著計算機能力的增強、算法的改進以及更多用戶友好的軟件解決方案的出現，線性規劃，尤其是混合整數線性規劃的重要性隨著時間的推移而增加。
解決線性規劃問題的基本方法稱為，它有多種變體。另壹種流行的方法是。
混合整數線性規劃問題可以通過更復雜且計算量更大的方法來解決，例如，它在幕後使用線性規劃。這種方法的壹些變體是，它涉及使用 切割平面 ，以及。
有幾種適用於線性規劃和混合整數線性規劃的合適且眾所周知的 Python 工具。其中壹些是開源的，而另壹些是專有的。您是否需要免費或付費工具取決於問題的規模和復雜性，以及對速度和靈活性的需求。
值得壹提的是，幾乎所有廣泛使用的線性規劃和混合整數線性規劃庫都是以 Fortran 或 C 或 C++ 原生和編寫的。這是因為線性規劃需要對（通常很大）矩陣進行計算密集型工作。此類庫稱為求解器。Python 工具只是求解器的包裝器。
Python 適合圍繞本機庫構建包裝器，因為它可以很好地與 C/C++ 配合使用。對於本教程，您不需要任何 C/C++（或 Fortran），但如果您想了解有關此酷功能的更多信息，請查看以下資源：
基本上，當您定義和求解模型時，您使用 Python 函數或方法調用低級庫，該庫執行實際優化工作並將解決方案返回給您的 Python 對象。
幾個免費的 Python 庫專門用於與線性或混合整數線性規劃求解器交互：
在本教程中，您將使用SciPy和PuLP來定義和解決線性規劃問題。
在本節中，您將看到線性規劃問題的兩個示例：
您將在下壹節中使用 Python 來解決這兩個問題。
考慮以下線性規劃問題：
妳需要找到X和?使得紅色，藍色和黃色的不平等，以及不平等X 0和? 0，是滿意的。同時，您的解決方案必須對應於z的最大可能值。
您需要找到的自變量（在本例中為 x 和 y ）稱為 決策變量 。要最大化或最小化的決策變量的函數（在本例中為 z） 稱為 目標函數 、 成本函數 或僅稱為 目標 。您需要滿足的 不等式 稱為 不等式約束 。您還可以在稱為 等式約束 的約束中使用方程。
這是您如何可視化問題的方法：
紅線代表的功能2 X + ? = 20，和它上面的紅色區域示出了紅色不等式不滿足。同樣，藍線是函數 4 x + 5 y = 10，藍色區域被禁止，因為它違反了藍色不等式。黃線是 x + 2 y = 2，其下方的黃色區域是黃色不等式無效的地方。
如果您忽略紅色、藍色和黃色區域，則僅保留灰色區域。灰色區域的每個點都滿足所有約束，是問題的潛在解決方案。該區域稱為 可行域 ，其點為 可行解 。在這種情況下，有無數可行的解決方案。
您想最大化z。對應於最大z的可行解是 最優解 。如果您嘗試最小化目標函數，那麽最佳解決方案將對應於其可行的最小值。
請註意，z是線性的。妳可以把它想象成壹個三維空間中的平面。這就是為什麽最優解必須在可行區域的 頂點 或角上的原因。在這種情況下，最佳解決方案是紅線和藍線相交的點，稍後您將看到。
有時，可行區域的整個邊緣，甚至整個區域，都可以對應相同的z值。在這種情況下，您有許多最佳解決方案。
您現在已準備好使用綠色顯示的附加等式約束來擴展問題：
方程式 x + 5 y = 15，以綠色書寫，是新的。這是壹個等式約束。您可以通過向上壹張圖像添加相應的綠線來將其可視化：
現在的解決方案必須滿足綠色等式，因此可行區域不再是整個灰色區域。它是綠線從與藍線的交點到與紅線的交點穿過灰色區域的部分。後壹點是解決方案。
如果插入x的所有值都必須是整數的要求，那麽就會得到壹個混合整數線性規劃問題，可行解的集合又會發生變化：
您不再有綠線，只有沿線的x值為整數的點。可行解是灰色背景上的綠點，此時最優解離紅線最近。
這三個例子說明了 可行的線性規劃問題 ，因為它們具有有界可行區域和有限解。
如果沒有解，線性規劃問題是 不可行的 。當沒有解決方案可以同時滿足所有約束時，通常會發生這種情況。
例如，考慮如果添加約束x + y 1會發生什麽。那麽至少有壹個決策變量（x或y）必須是負數。這與給定的約束x 0 和y 0相沖突。這樣的系統沒有可行的解決方案，因此稱為不可行的。
另壹個示例是添加與綠線平行的第二個等式約束。這兩行沒有***同點，因此不會有滿足這兩個約束的解決方案。
壹個線性規劃問題是 無界的 ，如果它的可行區域是無界，將溶液不是有限。這意味著您的變量中至少有壹個不受約束，可以達到正無窮大或負無窮大，從而使目標也無限大。
例如，假設您采用上面的初始問題並刪除紅色和黃色約束。從問題中刪除約束稱為 放松 問題。在這種情況下，x和y不會在正側有界。您可以將它們增加到正無窮大，從而產生無限大的z值。
在前面的部分中，您研究了壹個與任何實際應用程序無關的抽象線性規劃問題。在本小節中，您將找到與制造業資源分配相關的更具體和實用的優化問題。
假設壹家工廠生產四種不同的產品，第壹種產品的日產量為x ?，第二種產品的產量為x 2，依此類推。目標是確定每種產品的利潤最大化日產量，同時牢記以下條件：
數學模型可以這樣定義：
目標函數（利潤）在條件 1 中定義。人力約束遵循條件 2。對原材料 A 和 B 的約束可以從條件 3 和條件 4 中通過對每種產品的原材料需求求和得出。
最後，產品數量不能為負，因此所有決策變量必須大於或等於零。
與前面的示例不同，您無法方便地將其可視化，因為它有四個決策變量。但是，無論問題的維度如何，原理都是相同的。
在本教程中，您將使用兩個Python 包來解決上述線性規劃問題：
SciPy 設置起來很簡單。安裝後，您將擁有開始所需的壹切。它的子包 scipy.optimize 可用於線性和非線性優化。
PuLP 允許您選擇求解器並以更自然的方式表述問題。PuLP 使用的默認求解器是COIN-OR Branch and Cut Solver (CBC)。它連接到用於線性松弛的COIN-OR 線性規劃求解器 (CLP)和用於切割生成的COIN-OR 切割生成器庫 (CGL)。
另壹個偉大的開源求解器是GNU 線性規劃工具包 (GLPK)。壹些著名且非常強大的商業和專有解決方案是Gurobi、CPLEX和XPRESS。
除了在定義問題時提供靈活性和運行各種求解器的能力外，PuLP 使用起來不如 Pyomo 或 CVXOPT 等替代方案復雜，後者需要更多的時間和精力來掌握。
要學習本教程，您需要安裝 SciPy 和 PuLP。下面的示例使用 SciPy 1.4.1 版和 PuLP 2.1 版。
您可以使用pip以下方法安裝兩者：
您可能需要運行pulptest或sudo pulptest啟用 PuLP 的默認求解器，尤其是在您使用 Linux 或 Mac 時：
或者，您可以下載、安裝和使用 GLPK。它是免費和開源的，適用於 Windows、MacOS 和 Linux。在本教程的後面部分，您將看到如何將 GLPK（除了 CBC）與 PuLP 壹起使用。
在 Windows 上，您可以下載檔案並運行安裝文件。
在 MacOS 上，您可以使用 Homebrew：
在 Debian 和 Ubuntu 上，使用apt來安裝glpk和glpk-utils：
在Fedora，使用dnf具有glpk-utils：
您可能還會發現conda對安裝 GLPK 很有用：
安裝完成後，可以查看GLPK的版本：
有關詳細信息，請參閱 GLPK 關於使用Windows 可執行文件和Linux 軟件包進行安裝的教程。
在本節中，您將學習如何使用 SciPy優化和求根庫進行線性規劃。
要使用 SciPy 定義和解決優化問題，您需要導入scipy.optimize.linprog()：
現在您已經linprog()導入，您可以開始優化。
讓我們首先解決上面的線性規劃問題：
linprog()僅解決最小化（而非最大化）問題，並且不允許具有大於或等於符號 ( ) 的不等式約束。要解決這些問題，您需要在開始優化之前修改您的問題：
引入這些更改後，您將獲得壹個新系統：
該系統與原始系統等效，並且將具有相同的解決方案。應用這些更改的唯壹原因是克服 SciPy 與問題表述相關的局限性。
下壹步是定義輸入值：
您將上述系統中的值放入適當的列表、元組或NumPy 數組中：
註意：請註意行和列的順序！
約束左側和右側的行順序必須相同。每壹行代表壹個約束。
來自目標函數和約束左側的系數的順序必須匹配。每列對應壹個決策變量。
下壹步是以與系數相同的順序定義每個變量的界限。在這種情況下，它們都在零和正無窮大之間：
此語句是多余的，因為linprog()默認情況下采用這些邊界（零到正無窮大）。
註：相反的float("inf")，妳可以使用math.inf，numpy.inf或scipy.inf。
最後，是時候優化和解決您感興趣的問題了。妳可以這樣做linprog()：
參數c是指來自目標函數的系數。A_ub和b_ub分別與不等式約束左邊和右邊的系數有關。同樣，A_eq並b_eq參考等式約束。您可以使用bounds提供決策變量的下限和上限。
您可以使用該參數method來定義要使用的線性規劃方法。有以下三種選擇：
linprog() 返回具有以下屬性的數據結構：
您可以分別訪問這些值：
這就是您獲得優化結果的方式。您還可以以圖形方式顯示它們：
如前所述，線性規劃問題的最優解位於可行區域的頂點。在這種情況下，可行區域只是藍線和紅線之間的綠線部分。最優解是代表綠線和紅線交點的綠色方塊。
如果要排除相等（綠色）約束，只需刪除參數A_eq並b_eq從linprog()調用中刪除：
解決方案與前壹種情況不同。妳可以在圖表上看到：
在這個例子中，最優解是紅色和藍色約束相交的可行（灰色）區域的紫色頂點。其他頂點，如黃色頂點，具有更高的目標函數值。
您可以使用 SciPy 來解決前面部分所述的資源分配問題：
和前面的例子壹樣，妳需要從上面的問題中提取必要的向量和矩陣，將它們作為參數傳遞給.linprog()，然後得到結果：
結果告訴您最大利潤是1900並且對應於x ? = 5 和x ? = 45。在給定條件下生產第二和第四個產品是沒有利潤的。您可以在這裏得出幾個有趣的結論：
opt.statusis0和opt.successis True，說明優化問題成功求解，最優可行解。
SciPy 的線性規劃功能主要用於較小的問題。對於更大和更復雜的問題，您可能會發現其他庫更適合，原因如下：
幸運的是，Python 生態系統為線性編程提供了幾種替代解決方案，這些解決方案對於更大的問題非常有用。其中之壹是 PuLP，您將在下壹節中看到它的實際應用。
PuLP 具有比 SciPy 更方便的線性編程 API。您不必在數學上修改您的問題或使用向量和矩陣。壹切都更幹凈，更不容易出錯。
像往常壹樣，您首先導入您需要的內容：
現在您已經導入了 PuLP，您可以解決您的問題。
您現在將使用 PuLP 解決此系統：
第壹步是初始化壹個實例LpProblem來表示妳的模型：
您可以使用該sense參數來選擇是執行最小化（LpMinimize或1，這是默認值）還是最大化（LpMaximize或-1）。這個選擇會影響妳的問題的結果。
壹旦有了模型，就可以將決策變量定義為LpVariable類的實例：
您需要提供下限，lowBound=0因為默認值為負無窮大。該參數upBound定義了上限，但您可以在此處省略它，因為它默認為正無窮大。
可選參數cat定義決策變量的類別。如果您使用的是連續變量，則可以使用默認值"Continuous"。
您可以使用變量x和y創建表示線性表達式和約束的其他 PuLP 對象：
當您將決策變量與標量相乘或構建多個決策變量的線性組合時，您會得到壹個pulp.LpAffineExpression代表線性表達式的實例。
註意：您可以增加或減少變量或表達式，妳可以乘他們常數，因為紙漿類實現壹些Python的特殊方法，即模擬數字類型壹樣__add__()，__sub__()和__mul__()。這些方法用於像定制運營商的行為+，-和*。
類似地，您可以將線性表達式、變量和標量與運算符 ==、=以獲取表示模型線性約束的紙漿.LpConstraint實例。
註：也有可能與豐富的比較方法來構建的約束.__eq__()，.__le__()以及.__ge__()定義了運營商的行為==，=。
考慮到這壹點，下壹步是創建約束和目標函數並將它們分配給您的模型。您不需要創建列表或矩陣。只需編寫 Python 表達式並使用+=運算符將它們附加到模型中：
在上面的代碼中，您定義了包含約束及其名稱的元組。LpProblem允許您通過將約束指定為元組來向模型添加約束。第壹個元素是壹個LpConstraint實例。第二個元素是該約束的可讀名稱。
設置目標函數非常相似：
或者，您可以使用更短的符號：
現在您已經添加了目標函數並定義了模型。
註意：您可以使用運算符將 約束或目標附加到模型中，+=因為它的類LpProblem實現了特殊方法.__iadd__()，該方法用於指定 的行為+=。
對於較大的問題，lpSum()與列表或其他序列壹起使用通常比重復+運算符更方便。例如，您可以使用以下語句將目標函數添加到模型中：
它產生與前壹條語句相同的結果。
您現在可以看到此模型的完整定義：
模型的字符串表示包含所有相關數據：變量、約束、目標及其名稱。
註意：字符串表示是通過定義特殊方法構建的.__repr__()。有關 的更多詳細信息.__repr__()，請查看Pythonic OOP 字符串轉換：__repr__vs__str__ .
最後，您已準備好解決問題。妳可以通過調用.solve()妳的模型對象來做到這壹點。如果要使用默認求解器 (CBC)，則不需要傳遞任何參數：
.solve()調用底層求解器，修改model對象，並返回解決方案的整數狀態，1如果找到了最優解。有關其余狀態代碼，請參閱LpStatus[]。
妳可以得到優化結果作為 的屬性model。該函數value()和相應的方法.value()返回屬性的實際值：
model.objective持有目標函數model.constraints的值，包含松弛變量的值，以及對象x和y具有決策變量的最優值。model.variables()返回壹個包含決策變量的列表：
如您所見，此列表包含使用 的構造函數創建的確切對象LpVariable。
結果與您使用 SciPy 獲得的結果大致相同。
註意：註意這個方法.solve()——它會改變對象的狀態，x並且y！
您可以通過調用查看使用了哪個求解器.solver：
輸出通知您求解器是 CBC。您沒有指定求解器，因此 PuLP 調用了默認求解器。
如果要運行不同的求解器，則可以將其指定為 的參數.solve()。例如，如果您想使用 GLPK 並且已經安裝了它，那麽您可以solver=GLPK(msg=False)在最後壹行使用。請記住，您還需要導入它：
現在妳已經導入了 GLPK，妳可以在裏面使用它.solve()：
該msg參數用於顯示來自求解器的信息。msg=False禁用顯示此信息。如果要包含信息，則只需省略msg或設置msg=True。
您的模型已定義並求解，因此您可以按照與前壹種情況相同的方式檢查結果：
使用 GLPK 得到的結果與使用 SciPy 和 CBC 得到的結果幾乎相同。
壹起來看看這次用的是哪個求解器：
正如您在上面用突出顯示的語句定義的那樣model.solve(solver=GLPK(msg=False))，求解器是 GLPK。
您還可以使用 PuLP 來解決混合整數線性規劃問題。要定義整數或二進制變量，只需傳遞cat="Integer"或cat="Binary"到LpVariable。其他壹切都保持不變：
在本例中，您有壹個整數變量並獲得與之前不同的結果：
Nowx是壹個整數，如模型中所指定。（從技術上講，它保存壹個小數點後為零的浮點值。）這壹事實改變了整個解決方案。讓我們在圖表上展示這壹點：
如您所見，最佳解決方案是灰色背景上最右邊的綠點。這是兩者的最大價值的可行的解決方案x和y，給它的最大目標函數值。
GLPK 也能夠解決此類問題。
現在妳可以使用 PuLP 來解決上面的資源分配問題：
定義和解決問題的方法與前面的示例相同：
在這種情況下，您使用字典 x來存儲所有決策變量。這種方法很方便，因為字典可以將決策變量的名稱或索引存儲為鍵，將相應的LpVariable對象存儲為值。列表或元組的LpVariable實例可以是有用的。
上面的代碼產生以下結果：
如您所見，該解決方案與使用 SciPy 獲得的解決方案壹致。最有利可圖的解決方案是每天生產5.0第壹件產品和45.0第三件產品。
讓我們把這個問題變得更復雜和有趣。假設由於機器問題，工廠無法同時生產第壹種和第三種產品。在這種情況下，最有利可圖的解決方案是什麽？
現在您有另壹個邏輯約束：如果x ? 為正數，則x ? 必須為零，反之亦然。這是二元決策變量非常有用的地方。您將使用兩個二元決策變量y ? 和y ?，它們將表示是否生成了第壹個或第三個產品：
除了突出顯示的行之外，代碼與前面的示例非常相似。以下是差異：
這是解決方案：
事實證明，最佳方法是排除第壹種產品而只生產第三種產品。
就像有許多資源可以幫助您學習線性規劃和混合整數線性規劃壹樣，還有許多具有 Python 包裝器的求解器可用。這是部分列表：
其中壹些庫，如 Gurobi，包括他們自己的 Python 包裝器。其他人使用外部包裝器。例如，您看到可以使用 PuLP 訪問 CBC 和 GLPK。
您現在知道什麽是線性規劃以及如何使用 Python 解決線性規劃問題。您還了解到 Python 線性編程庫只是本機求解器的包裝器。當求解器完成其工作時，包裝器返回解決方案狀態、決策變量值、松弛變量、目標函數等。