混合整數線性規劃是線性規劃的擴展。它處理至少壹個變量采用離散整數而不是連續值的問題。雖然混合整數問題乍壹看與連續變量問題相似，但在靈活性和準確性方面具有明顯的優勢。
整數變量對於正確表示以整數自然表示的數量非常重要，例如生產的飛機數量或服務的客戶數量。
壹個特別重要的整數變量是二進制變量。它只能取值0或1，這在做出是或否的決定時非常有用，例如是否應該建立工廠或是否應該打開或關閉機器。您還可以使用它們來模擬邏輯約束。
線性規劃是壹種基本的優化技術，幾十年來壹直用於科學和數學密集型領域。它既準確又相對快速，適用於壹系列實際應用。
混合整數線性規劃允許您克服線性規劃的許多限制。您可以使用分段線性函數來逼近非線性函數，使用半連續變量，模型邏輯約束等。它是壹種計算密集型工具，但計算機硬件和軟件的進步使它每天都更適用。
通常，當人們試圖制定和解決優化問題時，首要問題是他們是否可以應用線性規劃或混合整數線性規劃。
以下文章舉例說明了線性規劃和混合整數線性規劃的壹些用例:
隨著計算機能力的增強、算法的改進和更易於用戶使用的軟件解決方案的出現，線性規劃特別是混合整數線性規劃的重要性與日俱增。
解決線性規劃問題的基本方法稱為，它有許多變體。另壹種流行的方法是。
混合整數線性規劃問題可以通過更復雜和計算密集型的方法來解決，例如，它在幕後使用線性規劃。這種方法的壹些變化是它涉及到切割平面的使用。
對於線性規劃和混合整數線性規劃，有幾個合適且眾所周知的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。通過合計每種產品的原材料需求，可以從條件3和4中獲得原材料A和B的約束條件。
最後，產品數量不能為負，因此所有決策變量必須大於或等於零。
與前面的例子不同，您無法輕松地將其可視化，因為它有四個決策變量。然而，無論問題的維度如何，原理都是相同的。
在本教程中，您將使用兩個Python包來解決上述線性編程問題:
SciPy很容易設置。安裝後，您將擁有開始工作所需的壹切。它的子包scipy.optimize可用於線性和非線性優化。
紙漿允許您選擇壹個求解器，並以更自然的方式表達問題。紙漿使用的默認解算器是硬幣或分支和切割解算器（CBC）。它連接到用於線性松弛的硬幣或線性規劃求解器（CLP）和用於切割生成的硬幣或切割生成器庫（CGL）。
另壹個偉大的開源求解器是GNU線性編程工具包（GLPK）。壹些著名且非常強大的商業和專有解決方案有Gurobi、CPLEX和XPRESS。
除了提供定義問題的靈活性和運行各種求解器的能力外，紙漿的使用不像Pyomo或CVXOPT等替代品那樣復雜，後者需要更多的時間和精力來掌握。
要學習本教程，您需要安裝SciPy和PuLP。以下示例使用SciPy 1.4.1和紙漿2.1。
您可以使用pip以下列方式安裝兩者:
您可能需要運行pulptest或sudo pulptest來啟用紙漿的默認解算器，尤其是在使用Linux或Mac時:
或者，您可以下載、安裝和使用GLPK。它是免費和開源的，適用於Windows、MacOS和Linux。在本教程的後面，妳將看到如何使用紙漿GLPK（除CBC）。
在Windows上，您可以下載文件並運行安裝文件。
在MacOS上，您可以使用自制軟件:
在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（）默認采用這些邊界（零到正無窮大）。
註意:對於相反的浮點數（“inf”），您可以使用math.inf、numpy.inf或scipy.inf
最後，是時候優化和解決妳感興趣的問題了。您可以這樣做linprog（）:
參數c是指目標函數的系數。A_ub和b_ub分別與不等式約束的左系數和右系數相關。同樣，A_eq和b_eq受引用等式的約束。您可以使用界限來提供決策變量的下限和上限。
您可以使用此參數方法來定義要使用的線性規劃方法。有三個選項:
Linprog（）返回具有以下屬性的數據結構:
您可以分別訪問這些值:
這是您獲得優化結果的方式。您也可以用圖形顯示它們:
如前所述，線性規劃問題的最優解位於可行域的頂點。在這種情況下，可行區域只有藍線和紅線之間的綠線。最佳解決方案是代表綠線和紅線交點的綠色正方形。
要排除等式（綠色）約束，只需從linprog（）調用中刪除參數A_eq和b_eq:
解決方案與前壹種情況不同。妳可以在圖表上看到:
在本例中，最佳解決方案是紅色和藍色約束相交的可行（灰色）區域的紫色頂點。其他頂點（如黃色頂點）具有更高的目標函數值。
您可以使用SciPy解決上壹節中描述的資源分配問題:
和前面的例子壹樣，您需要從上述問題中提取必要的向量和矩陣，並將它們作為參數傳遞給。linprog（），然後得到結果:
結果告訴妳最大利潤是1900對應X？= 5和x？= 45。在特定條件下生產第二種和第四種產品是無利可圖的。妳可以從中得出幾個有趣的結論:
Opt.statusis0和Opt。結果表明，優化問題得到了成功解決，並獲得了最優可行解。
SciPy的線性規劃功能主要用於較小的問題。對於更大更復雜的問題，您可能會發現其他庫更適合，原因如下:
幸運的是，Python生態系統為線性編程提供了幾種替代解決方案，對於較大的問題非常有用。其中之壹是紙漿，您將在下壹部分看到它的實際應用。
與SciPy相比，PuLP具有更方便的線性編程API。妳不必從數學上修改妳的問題或使用向量和矩陣。壹切都更幹凈，更不容易出錯。
像往常壹樣，首先導入您需要的內容:
現在妳已經進口了果肉，妳可以解決妳的問題了。
妳現在將使用紙漿來解決這個系統:
第壹步是初始化壹個實例LpProblem來表示您的模型:
您可以使用此sense參數來選擇是最小化（LpMinimize或1，這是默認值）還是最大化（LpMaximize或-1）。這個選擇會影響妳提問的結果。
壹旦有了模型，就可以將決策變量定義為LpVariable類的實例:
您需要提供壹個下限，lowBound=0，因為默認值為負無窮大。這個upBound參數定義了上限，但是您可以在這裏省略它，因為它默認為正無窮大。
可選參數cat定義了決策變量的類別。如果使用連續變量，可以使用默認值“連續”。
您可以使用變量x和y創建表示線性表達式和約束的其他紙漿對象:
當您將壹個決策變量與壹個標量相乘或構建多個決策變量的線性組合時，您將獲得壹個紙漿的實例。表示線性表達式的LpAffineExpression。
註意:您可以增加或減少變量或表達式，並且可以乘以它們的常數，因為pulp類實現了壹些特殊的Python方法，即模擬數字類型與__add__（）、__sub__（）和__mul__（）相同。這些方法用於自定義運算符的行為，如+、-和*。
同樣，您可以使用運算符= =，=將線性表達式、變量和標量組合在壹起，以獲得紙漿的實例。表示模型線性約束的LpConstraint。
註意:也可以用豐富的比較方法構造約束。_ __eq__（）、_ __le__（）和_ __ge__（）定義了運算符的行為= =、=
考慮到這壹點，下壹步是創建約束和目標函數，並將其分配給模型。您不需要創建列表或矩陣。只需編寫Python表達式並使用+=運算符將它們附加到模型:
在上面的代碼中，您定義了壹個包含約束及其名稱的元組。LpProblem允許您通過將約束指定為元組來為模型添加約束。第壹個元素是LpConstraint實例。第二個元素是人類可讀的約束名稱。
目標函數的設置非常相似:
或者，您可以使用較短的符號:
現在您已經添加了目標函數並定義了模型。
註意:您可以使用運算符將約束或目標附加到模型，+=因為它的類LpProblem實現了特殊方法。__iadd__（），用於指定的行為+=。
對於較大的問題，在列表或其他序列中使用lpSum（）通常比重復使用+運算符更方便。例如，您可以使用以下語句向模型添加目標函數:
它產生的結果與前面的語句相同。
現在您可以看到該模型的完整定義:
模型的字符串表示包含所有相關數據:變量、約束、目標及其名稱。
註意:字符串表示是通過定義特殊方法來構造的。__repr__（）。有關的更多詳細信息。__repr__（），請參見Pythonic OOP字符串轉換:_ _ REPR _ vs _ _ STR _ _。
最後，妳準備好解決問題了。您可以通過調用。求解（）模型對象。如果您想使用默認求解器（CBC），您不需要傳遞任何參數:
。solve（）調用底層求解器，修改模型對象，並返回解的整數狀態，如果找到最優解，則返回1。其余狀態代碼見LpStatus【】。
您可以將優化結果作為的屬性模型。函數值（）和相應的方法。value（）返回屬性的實際值:
Model.objective保存目標函數model.constraints的值，包括slack變量的值，並且對象X和Y具有決策變量的最佳值。Model.variables（）返回決策變量列表:
如您所見，該列表包含用構造函數創建的確切對象LpVariable。
結果與使用SciPy得到的結果大致相同。
註意:註意這種方法。solve（）-它將改變對象的狀態，x和y！
妳可以看到哪個求解器。通過調用以下方法使用規劃求解:
輸出通知您求解器是CBC。您沒有指定求解器，因此紙漿調用默認求解器。
如果要運行不同的求解器，可以將其指定為參數。求解（）的。例如，如果您想使用GLPK並且已經安裝了它，您可以在最後壹行中使用它，其中solver = GLPK（msg = False）。請記住，您還需要導入它:
現在您已經導入了GLPK，您可以在其中使用它。求解（）:
此消息參數用於顯示來自求解器的信息。Msg=False禁止顯示此信息。如果您想包含信息，只需省略msg或設置msg=True。
您的模型已被定義和求解，因此您可以用與前壹種情況相同的方式檢查結果:
使用GLPK獲得的結果與使用SciPy和CBC獲得的結果幾乎相同。
讓我們看看這次使用了哪個規劃求解:
正如您在上面突出顯示的語句中定義的，模型。求解（求解者= GLPK（MSG = false）），求解者是GLPK。
妳也可以使用紙漿來解決混合整數線性規劃問題。要定義整數或二進制變量，只需將cat =“Integer”或cat =“Binary”傳遞給LpVariable。其他壹切都保持不變:
在本例中，您有壹個整數變量，並得到不同的結果:
Nowx是壹個整數，如模型中指定的那樣。（從技術上講，它保存壹個小數點後帶零的浮點值。這壹事實改變了整個解決方案。讓我們在圖表中展示這壹點:
如妳所見，最佳解決方案是灰色背景上最右邊的綠點。這是可行解X和Y的最大值，使其具有最大目標函數值。
GLPK也可以解決這樣的問題。
現在妳可以使用紙漿來解決上述資源分配問題:
定義和解決問題的方法與前面的示例相同:
在這種情況下，您使用字典x來存儲所有決策變量。這種方法非常方便，因為字典可以將決策變量的名稱或索引存儲為鍵，並將相應的LpVariable對象存儲為值。列表或元組的LpVariable實例可能很有用。
上述代碼會產生以下結果:
如您所見，該解決方案與使用SciPy獲得的解決方案壹致。最有利可圖的解決方案是每天生產5.0個第壹產品和45.0個第三產品。
讓我們把這個問題變得更加復雜和有趣。假設工廠因為機器問題無法同時生產第壹種和第三種產品。在這種情況下，最有利可圖的解決方案是什麽？
現在妳有另壹個邏輯約束:如果x？是正的，那麽x呢？必須為零，反之亦然。這就是二元決策變量非常有用的地方。妳將使用兩個二元決策變量y？妳呢。，它將指示是否生成第壹個或第三個產品:
除了突出顯示的行之外，代碼與前面的示例非常相似。以下是不同之處:
這是解決方案:
事實證明，最好的辦法是排除第壹種產品，只生產第三種產品。
正如有許多資源可以幫助您學習線性編程和混合整數線性編程壹樣，也有許多帶有Python包裝器的求解器可用。這是部分列表:
其中壹些庫（如Gurobi）包含自己的Python包裝器。其他人使用外部包裝器。例如，妳可以看到妳可以使用紙漿訪問CBC和GLPK。
現在妳知道什麽是線性編程以及如何使用Python來解決線性編程問題。您還了解了Python線性編程庫只是本機求解器的包裝器。當求解器完成其工作時，包裝器返回解狀態、決策變量值、松弛變量、目標函數等。