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

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

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

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

Python適合圍繞本機(jī)庫構(gòu)建包裝器，因?yàn)樗梢院芎玫嘏cC/C++配合使用。對于本教程，您不需要任何C/C++(或Fortran)，但如果您想了解有關(guān)此酷功能的更多信息，請查看以下資源：

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

CPython內(nèi)部

用C或C++擴(kuò)展Python

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

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

SciPyOptimizationandRootFinding

PuLP

Pyomo

CVXOPT

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

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

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

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

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

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

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

資源分配問題

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

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

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

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

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

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

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