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

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

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

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

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

構(gòu)建PythonC擴展模塊

CPython內(nèi)部

用C或C++擴展Python

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

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

SciPyOptimizationandRootFinding

PuLP

Pyomo

CVXOPT

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

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

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

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

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

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

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

資源分配問題

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

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

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

由于人力限制，每天生產(chǎn)的總數(shù)量不能超過五十臺。

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

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

以上內(nèi)容為大家介紹了使用Python進(jìn)行線性規(guī)劃，希望對大家有所幫助，如果想要了解更多Python相關(guān)知識，請關(guān)注IT培訓(xùn)機構(gòu):千鋒教育。http://www.jsszjs.cn/