解決線性規(guī)劃問題的基本方法稱為單純形法，它有多種變體。另一種流行的方法是內點法。

混合整數線性規(guī)劃問題可以通過更復雜且計算量更大的方法來解決，例如分支定界法，它在幕后使用線性規(guī)劃。這種方法的一些變體是分支和切割方法，它涉及使用切割平面，以及分支和價格方法。

有幾種適用于線性規(guī)劃和混合整數線性規(guī)劃的合適且眾所周知的Python工具。其中一些是開源的，而另一些是專有的。您是否需要免費或付費工具取決于問題的規(guī)模和復雜性，以及對速度和靈活性的需求。

值得一提的是，幾乎所有廣泛使用的線性規(guī)劃和混合整數線性規(guī)劃庫都是以Fortran或C或C++原生和編寫的。這是因為線性規(guī)劃需要對(通常很大)矩陣進行計算密集型工作。此類庫稱為求解器。Python工具只是求解器的包裝器。

Python適合圍繞本機庫構建包裝器，因為它可以很好地與C/C++配合使用。對于本教程，您不需要任何C/C++(或Fortran)，但如果您想了解有關此酷功能的更多信息，請查看以下資源：

構建PythonC擴展模塊

CPython內部

用C或C++擴展Python

基本上，當您定義和求解模型時，您使用Python函數或方法調用低級庫，該庫執(zhí)行實際優(yōu)化工作并將解決方案返回給您的Python對象。

幾個免費的Python庫專門用于與線性或混合整數線性規(guī)劃求解器交互：

SciPyOptimizationandRootFinding

PuLP

Pyomo

CVXOPT

不可行的線性規(guī)劃問題

如果沒有解，線性規(guī)劃問題是不可行的。當沒有解決方案可以同時滿足所有約束時，通常會發(fā)生這種情況。

例如，考慮如果添加約束x+y≤?1會發(fā)生什么。那么至少有一個決策變量(x或y)必須是負數。這與給定的約束x≥0和y≥0相沖突。這樣的系統(tǒng)沒有可行的解決方案，因此稱為不可行的。

另一個示例是添加與綠線平行的第二個等式約束。這兩行沒有共同點，因此不會有滿足這兩個約束的解決方案。

無界線性規(guī)劃問題

一個線性規(guī)劃問題是無界的，如果它的可行區(qū)域是無界，將溶液不是有限。這意味著您的變量中至少有一個不受約束，可以達到正無窮大或負無窮大，從而使目標也無限大。

例如，假設您采用上面的初始問題并刪除紅色和黃色約束。從問題中刪除約束稱為放松問題。在這種情況下，x和y不會在正側有界。您可以將它們增加到正無窮大，從而產生無限大的z值。

資源分配問題

在前面的部分中，您研究了一個與任何實際應用程序無關的抽象線性規(guī)劃問題。在本小節(jié)中，您將找到與制造業(yè)資源分配相關的更具體和實用的優(yōu)化問題。

假設一家工廠生產四種不同的產品，第一種產品的日產量為x?，第二種產品的產量為x2，依此類推。目標是確定每種產品的利潤最大化日產量，同時牢記以下條件：

第一種、第二種、第三種和第四種產品的每單位產品利潤分別為20美元、12美元、40美元和25美元。

由于人力限制，每天生產的總數量不能超過五十臺。

對于每單位第一個產品，消耗三個單位的原材料A。每單位第二產品需要兩單位原料A和一單位原料B。每單位第三產品需要一單位A和兩單位B。最后，每單位第四產品需要三B的單位

由于運輸和儲存的限制，工廠每天最多可以消耗一百單位的原材料A和九十單位的B。

以上內容為大家介紹了使用Python進行線性規(guī)劃，希望對大家有所幫助，如果想要了解更多Python相關知識，請關注IT培訓機構:千鋒教育。http://www.em-kal.com/