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

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

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

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

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

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

CPython內(nèi)部

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

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

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

SciPyOptimizationandRootFinding

PuLP

Pyomo

CVXOPT

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

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

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

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

無(wú)界線性規(guī)劃問(wèn)題

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

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

資源分配問(wèn)題

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

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

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

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

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

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

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