線性規(guī)劃是一種數(shù)學(xué)技術(shù),它用于在一個目標(biāo)函數(shù)和約束都以線性關(guān)系表示的模型中確定最優(yōu)結(jié)果--例如利潤最大化或成本最小化。

線性規(guī)劃中的"規(guī)劃"一詞源于軍事術(shù)語,指的是規(guī)劃時(shí)間表的過程,如協(xié)調(diào)供應(yīng)線或有效部署部隊(duì)。

關(guān)鍵概念

決策變量

決策變量是?優(yōu)化 問題,表示可以調(diào)整的數(shù)量,以找到最大化或最小化目標(biāo)函數(shù)同時(shí)滿足約束的最優(yōu)解。

目的功能

目標(biāo)函數(shù)是一個數(shù)學(xué)表達(dá)式,它定義了優(yōu)化問題的目標(biāo).在線性規(guī)劃中,目標(biāo)函數(shù)總是決策變量的線性組合.

限制因素

約束是解決優(yōu)化問題必須滿足的要求.它們被表示為線性不等式或涉及決策變量的方程。制約因素可能來自各種來源,如可用資源、預(yù)算限制、時(shí)間限制或有形法律。在線性規(guī)劃問題中,約束可分類如下:

· 不平等制約因素 :這些規(guī)則規(guī)定一定的關(guān)系必須保持,例如AX為系數(shù)矩陣,X為決策變量向量,B為常量向量。

· 平等制約因素 :這些要求特定的關(guān)系必須準(zhǔn)確,以AX=B表示。

可行區(qū)域

可行區(qū)域是滿足約束的所有可能點(diǎn)(或向量)的集合。在幾何上,在由決策變量定義的空間中,該區(qū)域通常被表示為凸多邊形(或更高尺寸的多面體)。

線性規(guī)劃的基本定理

"線性規(guī)劃(LP)的基本定理指出,每一個有邊界的可行線性程序在可行多面體的零維面(頂點(diǎn))上都有一個最優(yōu)解"[1]。這意味著目標(biāo)函數(shù)的最大值或最小值總是發(fā)生在可行區(qū)域的頂點(diǎn)。此外,這意味著在下列情況下,LP優(yōu)化問題可能缺乏最佳解決方案[2]:

· 沒有可行的區(qū)域 :如果不平等約束不兼容,圖中沒有一個區(qū)域能滿足所有約束。

· 可行的區(qū)域是無限的 當(dāng)區(qū)域無限擴(kuò)展時(shí),線性程序可能沒有有限的最優(yōu)解。

語言語言問題的數(shù)學(xué)公式

二元問題

線性規(guī)劃中的二元性定理指出,任何最小化問題都可以轉(zhuǎn)化為等價(jià)最大化問題,即所謂的對偶問題,反之亦然。在原始問題中,只有當(dāng)目標(biāo)函數(shù)在其雙重問題中的最大值也得到時(shí),才能實(shí)現(xiàn)目標(biāo)函數(shù)的最小值。原始問題和雙重問題之間的這種關(guān)系是理解LP二元性理論的關(guān)鍵,它為優(yōu)化問題提供了更深入的見解。

解決雙重問題通常是有利的,特別是當(dāng)原始問題與決策變量相比有更大數(shù)量的約束時(shí)。這是因?yàn)榻鉀Q線性規(guī)劃問題的計(jì)算復(fù)雜性通常隨著約束的數(shù)量而增加的更快,而不是變量的數(shù)量。在這種情況下,具有較少約束和較多變量的雙重問題可以得到更有效的解決。

解決線性規(guī)劃問題

LP問題可以根據(jù)問題的復(fù)雜性和維數(shù),用各種方法解決。這些方法從簡單的圖形化方法到先進(jìn)的計(jì)算算法不等。

圖形方法

如前一個例子所示,圖形化方法是解決線性規(guī)劃問題的最簡單的方法之一,但僅限于兩個變量的情況。有關(guān)步驟如下:

· 限制因素和可行性區(qū)域圖 不平等被描繪成直線,確定了滿足所有限制的可行區(qū)域。

· 目的函數(shù)優(yōu)化 :通過評價(jià)其在可行區(qū)域頂點(diǎn)的值,使目標(biāo)函數(shù)最大化或最小化。

簡單方法

單純形法是一種迭代算法,它從可行區(qū)域的頂點(diǎn)之一開始,移動到鄰近的頂點(diǎn),相對于當(dāng)前頂點(diǎn),它對目標(biāo)函數(shù)的改進(jìn)最大。該算法繼續(xù)這個過程,直到它達(dá)到最優(yōu)解,當(dāng)它到達(dá)一個頂點(diǎn)時(shí),所有鄰近的頂點(diǎn)要么產(chǎn)生更差的目標(biāo)值,或者是在可行區(qū)域之外。

橢圓法

橢圓法是一種用于求解線性規(guī)劃問題的中間點(diǎn)算法。與單純形法不同的是,它是在可行區(qū)域的頂點(diǎn)上工作的,橢圓形法與可行區(qū)域的內(nèi)部工作。它以一個初始的橢圓體開始,它封裝了整個可行區(qū)域,并在每個步驟上改進(jìn)了這個橢圓體。通過迭代線性不等式約束,該方法逐步減小了橢圓體的體積,使其更接近最優(yōu)解。

在理論性能方面,保證了橢圓法在多項(xiàng)式時(shí)間中的運(yùn)行,而單純形法在最壞情況下可以顯示指數(shù)時(shí)間復(fù)雜性。這使得橢圓形法在理論上成為大規(guī)模問題的一個吸引人的選擇,盡管實(shí)際使用受到收斂速度較慢的限制,例如中間點(diǎn)法。

內(nèi)部點(diǎn)方法

點(diǎn)法從可行區(qū)域內(nèi)求出最優(yōu)解,而不是像單純形法那樣沿邊緣移動。它們對大規(guī)模問題更有效。這些方法通過跟蹤可行區(qū)域內(nèi)部的軌跡來解決LP問題,目的是直接達(dá)到最優(yōu)點(diǎn)。相比之下,單純形法的軌跡沿邊界運(yùn)動,而橢圓法則從外部包圍可行區(qū)域。對大規(guī)模優(yōu)化問題來說,點(diǎn)間方法特別有效,因?yàn)樗鼈儽葐渭冃畏椒ū憩F(xiàn)出更好的性能,特別是在處理非常高尺寸的問題時(shí)。

應(yīng)用lp問題

最優(yōu)運(yùn)輸

統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)的一個基本挑戰(zhàn)是制定有效的概率分布對之間"距離"的衡量標(biāo)準(zhǔn)。有效的距離函數(shù)應(yīng)滿足對稱和三角不等式等關(guān)鍵屬性.然而,用于比較概率分布的許多常用措施不符合這些標(biāo)準(zhǔn),因此被歸為差異(如KL發(fā)散)[4]。

最優(yōu)運(yùn)輸提供了一個健壯的距離之間的概率分布.最優(yōu)運(yùn)輸背后的直覺是想象用一堆泥土以最低的成本填補(bǔ)同樣體積的一個洞。換言之,它尋求最有效的方法,將質(zhì)量從一個概率分布X轉(zhuǎn)移到另一個分布Y,同時(shí)最小化運(yùn)輸成本。

這可以被理解為一個lp問題:

網(wǎng)絡(luò)流問題

網(wǎng)絡(luò)流問題是通過網(wǎng)絡(luò)優(yōu)化資源流動所不可或缺的,在網(wǎng)絡(luò)中,資源可能代表貨物、數(shù)據(jù)或其他商品。這些問題通常涉及一個有向圖,其中每個邊緣都有一個指定的容量和成本。目標(biāo)是優(yōu)化從源節(jié)點(diǎn)到接收節(jié)點(diǎn)的資源流,但要受邊緣和節(jié)點(diǎn)的約束。網(wǎng)絡(luò)流問題的主要類型包括最大流問題、最小成本流問題等。

解決線性規(guī)劃問題的庫

(谷歌) :谷歌開發(fā)的一個支持LP和其他約束編程的開源軟件套件。它具有高度的可伸縮性,并與多個編程環(huán)境集成。

(python最佳運(yùn)輸) :專門為解決問題而設(shè)計(jì)的python庫?最佳運(yùn)輸問題 .它支持包括基于lp的方法在內(nèi)的多解決器,并廣泛應(yīng)用于機(jī)器學(xué)習(xí)、統(tǒng)計(jì)和數(shù)據(jù)科學(xué)等任務(wù),如領(lǐng)域適應(yīng)、集群和生成建模。

結(jié)論

線性規(guī)劃仍然是優(yōu)化的基石,為解決物流、金融和AI等領(lǐng)域的各種問題提供了工具。實(shí)踐者通過掌握LP概念和方法,可以有效地解決理論和現(xiàn)實(shí)世界的挑戰(zhàn)。