線性規(guī)劃是一種數(shù)學(xué)技術(shù),它用于在一個目標(biāo)函數(shù)和約束都以線性關(guān)系表示的模型中確定最優(yōu)結(jié)果--例如利潤最大化或成本最小化。
線性規(guī)劃中的"規(guī)劃"一詞源于軍事術(shù)語,指的是規(guī)劃時間表的過程,如協(xié)調(diào)供應(yīng)線或有效部署部隊。
關(guān)鍵概念
決策變量
決策變量是?優(yōu)化 問題,表示可以調(diào)整的數(shù)量,以找到最大化或最小化目標(biāo)函數(shù)同時滿足約束的最優(yōu)解。
目的功能
目標(biāo)函數(shù)是一個數(shù)學(xué)表達(dá)式,它定義了優(yōu)化問題的目標(biāo).在線性規(guī)劃中,目標(biāo)函數(shù)總是決策變量的線性組合.
限制因素
約束是解決優(yōu)化問題必須滿足的要求.它們被表示為線性不等式或涉及決策變量的方程。制約因素可能來自各種來源,如可用資源、預(yù)算限制、時間限制或有形法律。在線性規(guī)劃問題中,約束可分類如下:
· 不平等制約因素 :這些規(guī)則規(guī)定一定的關(guān)系必須保持,例如AX為系數(shù)矩陣,X為決策變量向量,B為常量向量。
· 平等制約因素 :這些要求特定的關(guān)系必須準(zhǔn)確,以AX=B表示。
可行區(qū)域
可行區(qū)域是滿足約束的所有可能點(或向量)的集合。在幾何上,在由決策變量定義的空間中,該區(qū)域通常被表示為凸多邊形(或更高尺寸的多面體)。
線性規(guī)劃的基本定理
"線性規(guī)劃(LP)的基本定理指出,每一個有邊界的可行線性程序在可行多面體的零維面(頂點)上都有一個最優(yōu)解"[1]。這意味著目標(biāo)函數(shù)的最大值或最小值總是發(fā)生在可行區(qū)域的頂點。此外,這意味著在下列情況下,LP優(yōu)化問題可能缺乏最佳解決方案[2]:
· 沒有可行的區(qū)域 :如果不平等約束不兼容,圖中沒有一個區(qū)域能滿足所有約束。
· 可行的區(qū)域是無限的 當(dāng)區(qū)域無限擴展時,線性程序可能沒有有限的最優(yōu)解。
語言語言問題的數(shù)學(xué)公式
二元問題
線性規(guī)劃中的二元性定理指出,任何最小化問題都可以轉(zhuǎn)化為等價最大化問題,即所謂的對偶問題,反之亦然。在原始問題中,只有當(dāng)目標(biāo)函數(shù)在其雙重問題中的最大值也得到時,才能實現(xiàn)目標(biāo)函數(shù)的最小值。原始問題和雙重問題之間的這種關(guān)系是理解LP二元性理論的關(guān)鍵,它為優(yōu)化問題提供了更深入的見解。
解決雙重問題通常是有利的,特別是當(dāng)原始問題與決策變量相比有更大數(shù)量的約束時。這是因為解決線性規(guī)劃問題的計算復(fù)雜性通常隨著約束的數(shù)量而增加的更快,而不是變量的數(shù)量。在這種情況下,具有較少約束和較多變量的雙重問題可以得到更有效的解決。
解決線性規(guī)劃問題
LP問題可以根據(jù)問題的復(fù)雜性和維數(shù),用各種方法解決。這些方法從簡單的圖形化方法到先進(jìn)的計算算法不等。
圖形方法
如前一個例子所示,圖形化方法是解決線性規(guī)劃問題的最簡單的方法之一,但僅限于兩個變量的情況。有關(guān)步驟如下:
· 限制因素和可行性區(qū)域圖 不平等被描繪成直線,確定了滿足所有限制的可行區(qū)域。
· 目的函數(shù)優(yōu)化 :通過評價其在可行區(qū)域頂點的值,使目標(biāo)函數(shù)最大化或最小化。
簡單方法
單純形法是一種迭代算法,它從可行區(qū)域的頂點之一開始,移動到鄰近的頂點,相對于當(dāng)前頂點,它對目標(biāo)函數(shù)的改進(jìn)最大。該算法繼續(xù)這個過程,直到它達(dá)到最優(yōu)解,當(dāng)它到達(dá)一個頂點時,所有鄰近的頂點要么產(chǎn)生更差的目標(biāo)值,或者是在可行區(qū)域之外。
橢圓法
橢圓法是一種用于求解線性規(guī)劃問題的中間點算法。與單純形法不同的是,它是在可行區(qū)域的頂點上工作的,橢圓形法與可行區(qū)域的內(nèi)部工作。它以一個初始的橢圓體開始,它封裝了整個可行區(qū)域,并在每個步驟上改進(jìn)了這個橢圓體。通過迭代線性不等式約束,該方法逐步減小了橢圓體的體積,使其更接近最優(yōu)解。
在理論性能方面,保證了橢圓法在多項式時間中的運行,而單純形法在最壞情況下可以顯示指數(shù)時間復(fù)雜性。這使得橢圓形法在理論上成為大規(guī)模問題的一個吸引人的選擇,盡管實際使用受到收斂速度較慢的限制,例如中間點法。
內(nèi)部點方法
點法從可行區(qū)域內(nèi)求出最優(yōu)解,而不是像單純形法那樣沿邊緣移動。它們對大規(guī)模問題更有效。這些方法通過跟蹤可行區(qū)域內(nèi)部的軌跡來解決LP問題,目的是直接達(dá)到最優(yōu)點。相比之下,單純形法的軌跡沿邊界運動,而橢圓法則從外部包圍可行區(qū)域。對大規(guī)模優(yōu)化問題來說,點間方法特別有效,因為它們比單純形方法表現(xiàn)出更好的性能,特別是在處理非常高尺寸的問題時。
應(yīng)用lp問題
最優(yōu)運輸
統(tǒng)計學(xué)和機器學(xué)習(xí)的一個基本挑戰(zhàn)是制定有效的概率分布對之間"距離"的衡量標(biāo)準(zhǔn)。有效的距離函數(shù)應(yīng)滿足對稱和三角不等式等關(guān)鍵屬性.然而,用于比較概率分布的許多常用措施不符合這些標(biāo)準(zhǔn),因此被歸為差異(如KL發(fā)散)[4]。
最優(yōu)運輸提供了一個健壯的距離之間的概率分布.最優(yōu)運輸背后的直覺是想象用一堆泥土以最低的成本填補同樣體積的一個洞。換言之,它尋求最有效的方法,將質(zhì)量從一個概率分布X轉(zhuǎn)移到另一個分布Y,同時最小化運輸成本。
這可以被理解為一個lp問題:
網(wǎng)絡(luò)流問題
網(wǎng)絡(luò)流問題是通過網(wǎng)絡(luò)優(yōu)化資源流動所不可或缺的,在網(wǎng)絡(luò)中,資源可能代表貨物、數(shù)據(jù)或其他商品。這些問題通常涉及一個有向圖,其中每個邊緣都有一個指定的容量和成本。目標(biāo)是優(yōu)化從源節(jié)點到接收節(jié)點的資源流,但要受邊緣和節(jié)點的約束。網(wǎng)絡(luò)流問題的主要類型包括最大流問題、最小成本流問題等。
解決線性規(guī)劃問題的庫
(谷歌) :谷歌開發(fā)的一個支持LP和其他約束編程的開源軟件套件。它具有高度的可伸縮性,并與多個編程環(huán)境集成。
(python最佳運輸) :專門為解決問題而設(shè)計的python庫?最佳運輸問題 .它支持包括基于lp的方法在內(nèi)的多解決器,并廣泛應(yīng)用于機器學(xué)習(xí)、統(tǒng)計和數(shù)據(jù)科學(xué)等任務(wù),如領(lǐng)域適應(yīng)、集群和生成建模。
結(jié)論
線性規(guī)劃仍然是優(yōu)化的基石,為解決物流、金融和AI等領(lǐng)域的各種問題提供了工具。實踐者通過掌握LP概念和方法,可以有效地解決理論和現(xiàn)實世界的挑戰(zhàn)。