python基礎代碼大全「python基礎代碼實例詳解」

整數規劃（IP）問題是所有變量都被限制為整數的優化問題（指規劃中的變量（全部或部分）限制為整數，若在線性模型中，變量限制為整數，則稱為整數線性規劃）。IP問題是有關於如何最好地分配資源的有用數學模型。

假設你正在組織針對政治候選人的營銷活動，並且你正在決定向哪些組成部分發送營銷材料。你可以向每個組織發送一張吸引人的傳單，一份詳細的解釋你的日程表的小冊子，或一張保險杠貼紙（或三者的組合）。如果你有辦法根據收到的營銷材料來衡量某人投票給候選人的可能性，你如何決定發送哪些材料，同時不超過你的供應量？

傳統的優化算法假定變量可以採用浮點值，但在我們的例子中，向某人發送一半保險杠貼紙或四分之三小冊是不合理的。我們將使用一個名為cvxpy的特殊python包來解決我們的問題，這樣解決方案才有意義。

這裡將向你展示如何使用cvxpy解決政治候選人問題，首先會從一個簡單的問題開始，稱為背包問題，然後展示cvxpy語法的工作原理。

背包問題

讓我們假裝你正在進行徒步旅行，並且正在計劃你可以攜帶的物品。你想把所有的東西都拿走，但是你的背包只能攜帶P磅。假設你可以取一個物體，目標是最大限度地提高實用性，而不會超出重量限制。

一個cvxpy問題有三個部分：

1.創建變量：我們將用1和0的向量在數學上表示我們的選擇。 1意味着我們選擇了這個對象，而0意味着我們將它留在家中。我們用cvxpy.Bool對象構造一個只能取1和0的變量。

2.指定約束條件：我們只需確保我們的對象總和不超過重量限制P。我們可以用選擇向量和權向量的點積來計算我們對象的總重量。cvxpy會重載*運算符以執行矩陣乘法。

3.制定目標函數：我們希望最大化選擇的效用。任何給定選擇的效用都是選擇向量和效用向量的點積。

完整的背包問題的cvxpy代碼

一旦我們有成本函數和約束，我們將它們傳遞給cvxpy 問題對象。在這種情況下，cvxpy要試圖通過cvxpy.Maximize最大化實用程序。為了解決這個問題，我們只需要運行問題對象的求解方法。之後，我們可以通過查看它的值屬性來檢查我們選擇向量的最優值。

我們選擇了前四項和第六項。這是有道理的，因為這些具有很高的效用與重量的比例，但又不會過重。

營銷問題

現在我們已經介紹了基本的cvxpy語法，我們可以為我們的政治候選人解決營銷優化問題。假設我們有一個模型，它接受一個組成部分的屬性，並預測他們將為我們的候選人投票給我們發送的每個營銷材料組合的概率。我在這裡使用假數據，讓我們假裝模型輸出以下概率：

每個組織有八個總概率，因為我們可以向個人發送八種材料的總組合。以下是每個1 x 8向量表示的條目：

[1份傳單、1本小冊子、1份保險杠貼紙、傳單和小冊子、傳單和保險杠貼紙、小冊子和保險杠貼紙、全部三種]。

例如，如果我們的候選人收到傳單或小冊子，那麼第一個成員對我們的候選人的投票概率為0.0001，但是如果我們給他發了一個保險杠貼紙，我們的候選人有0.3的概率投票。

在我們開始使用cvxpy代碼之前，我們將通過採用negative log將這些概率轉化為成本。這使得數學工作變得更好，並且它有一個很好的解釋：如果概率接近1，negative log將接近於0，這意味着將該材料的特定組合發送到該組成部分幾乎沒有成本，因為我們肯定會導致他們投票給我們的候選人。反之亦然，如果概率接近於0。

最後，假設我們不能發送超過150張傳單，80張小冊子和25張保險杠貼紙。

現在我們已經完成了所有的設置，發現一些有趣的部分：

1.創建變量：我們將再次使用cvxpy.Bool對象，因為我們只能在這裡創建二進制選項。我們將指定它必須與我們的概率矩陣形狀相同：

2.指定約束條件：我們的選擇變量只會告訴我們為每個組成部分選擇了8個選項中的哪一個，但它不會告訴我們已決定發送給他們的總共多少材料。我們需要一種方法將我們的1 x 8選擇向量轉換為1 x 3向量。我們可以通過乘以選擇向量乘以下面的矩陣來實現：

如果這部分有點令人困惑，那麼請看下面的例子：

我們的決策向量的第四個條目表示向組件發送傳單和小冊子，乘以變壓器告訴我們！所以我們會讓cvxpy乘以變壓器的選擇矩陣不能超過我們的供應：

這裡用cvxpy.sum_entries對行進行總結，以匯總我們發送到所有組成部分的材料總數。

我們還需要確保每個組成部分的選擇都是正確的，否則求解者可以通過不發送任何東西來實現零成本。

3.制定目標函數：我們的任務總成本將是我們為每個成員承擔的成本的總和。我們將使用cvxpy.mul_elemwise函數將我們的選擇矩陣與成本矩陣相乘，這將選擇每個成分的成本，並且cvxpy.sum_elemwise函數將通過累計單個成本來計算總成本。

最後一步是創建cvxpy.Problem並解決它。

就是這樣！以下是我們最終作業的截圖。我們決定不向第一個組織發送任何材料。這是有道理的，因為他們為我們的候選人投票的可能性是0.3，不管我們給他們發一張保險杠貼紙還是什麼都不發。

它也證明，最優的分配方案會耗盡我們的小冊子和保險杠貼紙的供應，但其實只使用了150傳單中的83張。我們應該告訴我們的候選人她的傳單並沒有她想像的那麼有說服力。

以下是所有打包在一起的代碼：

結束語

希望這篇整數規劃問題以及如何用Python解決它們能夠對你有作用。我們已經覆蓋了大約80％的cvxpy知識，你需要去解決你自己的優化問題。當然，可以閱讀官方文件，從而了解剩下的20％。 CVXPY不僅可以解決IP問題，還可以查看他們的教程頁面，查看cvxpy可以解決的其他問題。

要安裝cvxpy，請按照其網站上的指示進行操作。我還會安裝cvxopt，以確保所有使用cvxpy打包的求解器都可以在你的機器上運行。

我們已經指定cvxpy應該在解決方法中使用GLPK_MI求解器。這是專為解決IP問題而設計的解決方案。在你解決你自己的問題之前，請參考這個表格，看看哪個預包裝的cvpxy求解器最適合你。