線性規劃問題、解決方案和應用 [附示例]

數據科學有很多應用，其中最突出的應用之一就是優化。 我們都傾向於專注於優化東西。 優化的重點是使用您擁有的有限資源獲得最理想的結果。

有各種各樣的優化問題可用，有些很小，有些非常複雜。 在瀏覽它們時，您會發現一個稱為線性規劃問題的特定類別。 在本文中，我們討論了它們是什麼以及如何處理它們。

假設您是一個水果賣家，可以購買橙子或蘋果或兩者的某種組合。 但是，您只有 5,000 盧比的預算，並且只能存放 30 袋。 現在，您必須以能夠為您帶來最高利潤的方式購買它們。

現在，一袋橙子的價格為 500 盧比，而一袋蘋果的價格為 750 盧比。您可以從銷售一袋橙子中賺取 100 盧比，從銷售一袋蘋果中賺取 200 盧比。

這個問題有多種可能性。 您可能選擇只購買橙子，但您的倉庫中只有 10 個袋子，您的利潤將是 1000 盧比。同樣，您可能選擇只購買蘋果並賺取 1500 盧比作為利潤。 您也可以購買兩者的組合。

此類問題稱為線性規劃問題，我們將詳細討論它們。 讓我們開始吧：

什麼是線性規劃？

線性規劃是一種使用線性函數來描述複雜關係的方法。 我們線性規劃的目標是為這些函數找到最合適的解決方案。 兩點之間的真實關係可能非常複雜，但我們可以使用線性規劃來簡單地描述它們。 線性規劃在許多行業中都有應用。

線性規劃基礎

以下是線性規劃的一些基本術語：

約束

決策變量的限制（或約束）稱為約束。 大多數時間限制是您解決問題的資源的限制。

決策變量

這些變量定義了您的輸出。 您的結果取決於這些變量，這就是我們稱它們為“決策變量”的原因。

非消極性限制

線性規劃問題的決策變量只能具有非負值。 這意味著您的決策變量的值只能等於或大於零。

目標函數

目標函數是做出決定的目標。 簡單來說，它是線性規劃問題的最終結果。 例如，當您找到使用給定資源集可以獲得的最大利潤時，最大利潤就是目標函數。

制定線性規劃問題

您應該知道如何制定線性規劃以將其應用到現實生活中。 假設您是一家玩具製造商，您只生產兩種玩具：A 和 B。粗略地說，您的玩具需要 X 和 Y 兩種資源來製造。 以下是您對玩具的要求：

• 一單位玩具 A 需要一單位資源 X 和三單位資源 Y

• 一單位玩具 B 需要一單位資源 X 和兩單位資源 Y

您有 5 個單位的資源 X 和 12 個單位的資源 Y。您銷售這些玩具的利潤率為：

• 每售出一件玩具 A 6 印度盧比
• 每售出一件玩具 B 5 盧比

你會生產多少個玩具以獲得最大的利潤？

解決方案

讓我們用一個方程來表示我們的線性規劃問題：

Z = 6a + 5b

這裡，z 代表總利潤，a 代表玩具 A 單位的總數，b 代表玩具 B 單位的總數。 我們的目標是最大化 Z（利潤）的價值。

現在，您的公司希望盡可能多地生產這些玩具，但您的資源有限。 我們資源的限制是這個問題的製約因素。 我們總共只有

a + b 5

現在每個玩具 A 和 B 的單位分別需要 3 和 2 單位的資源 Y。 而且我們總共只有 12 個單位的資源 Y，所以在數學上，它看起來像這樣：

3a + 2b 12

請記住，玩具 A 的單位值只能是整數。 這意味著我們也有 a->0 和 b<-0 的約束。

所以，現在你有一個適當的線性規劃問題。 您可以按照此示例制定其他線性規劃問題。 雖然這個例子非常簡單，但 LP 問題可能會變得非常複雜。

閱讀：線性規劃項目的想法和主題

制定線性規劃問題的步驟

要製定線性規劃問題，請執行以下步驟：

• 找到決策變量
• 找到目標函數
• 識別約束
• 記住非負性限制

如果一個問題滿足上述標準，那麼它就是一個線性規劃問題。 當您在確定問題的類型時，最好記住這個標準。

用 R 解決線性規劃問題

如果您使用 R，解決線性規劃問題會變得更加簡單。 那是因為 R 有 lpsolve 包，它帶有專門為解決此類問題而設計的各種功能。 作為數據科學家，您很可能會非常頻繁地使用 R 來解決 LP 問題。 這就是為什麼我們分享了兩個不同的示例來幫助您更好地理解它的實現：

例子

讓我們從一個基本問題開始。 一個組織有兩種產品，售價分別為 25 盧比和 20 盧比，分別稱為產品 A 和 B。 每天，他們有 1800 單位的資源來生產這些產品。 產品 A 需要 20 個資源單元，而 B 需要 12 個資源單元。 這兩種產品的生產時間均為 4 分鐘，該組織每天總共有 8 個工作小時。 問題是，這些產品的生產數量應該是多少才能使公司的利潤最大化？

解決方案：

我們將通過定義其目標函數來開始解決這個問題：

最大（銷售額）= 最大（25 y 1 + 20 y 2 ）

這裡，25 和 20 分別是產品 A 和 B 的價格，y1 是生產的產品 A 的總單位數，y2 是生產的產品 B 的總單位數。 我們的決策變量是 y1 和 y2。

我們現在將為我們的問題設置約束：

資源限制：

20 歲1 + 12歲2 1800

時間限制：

4年1 + 4年2 8*60

我們的目標是找到我們必須生產的正確數量的產品，以獲得最大的利潤。

使用 R 解決問題：

我們將使用 lpsolve 來解決這個 LP 問題，並從設置目標函數開始：

> 要求（lp解決）

加載所需的包：lpSolve

> 目標.in <- c(25, 20)

> 目標.in

[1] 25 20

然後我們將為約束構建一個矩陣：

> const <- 矩陣(c(20, 12, 4, 4), nrow=2, byrow=TRUE)

> 常量

[,1] [,2]

[1,] 20 12

[2,] 4 4

> time_constraints <- (8*60)

> 資源約束 <- 1800

> 時間約束

[1] 480

> 資源約束

[1] 1800

現在讓我們創建已經定義的方程：

> rhs <- c(resource_constraints, time_constraints)

> 右聲道

[1] 1800 480

> 方向 <- c(“<=”, “<=”)

> 方向

[1] “<=” “<=”

一旦添加了所有必要的信息，我們就可以開始尋找最佳答案。 我們的包的語法是：

lp（方向，目標，const.mat，const.dir，const.rhs）

> 最佳 <- lp(direction=”max”, objective.in, const, direction, rhs)

> 最佳

成功：目標函數為 2625

> 摘要（最佳）

長度類模式

方向 1 - 無 - 數字

x.count 1 -none- 數字

目標 2 - 非數字

const.count 1 -none- 數字

約束 8 -none- 數字

int.count 1 -none- 數字

int.vec 1 -none- 數字

bin.count 1 -none- 數字

binary.vec 1 -none- 數字

num.bin.solns 1 -none- 數字

objval 1 -none- 數字

解決方案 2 - 無 - 數字

presolve 1 -none- numeric

compute.sens 1 -none- 數字

sens.coef.from 1 -none- numeric

sens.coef.to 1 -none- 數字

對偶 1 -none- 數字

duals.from 1 -none- numeric

duals.to 1 -none- 數字

比例 1 -none- 數字

use.dense 1 -none- numeric

dense.col 1 -none- 數字

dense.val 1 -none- 數字

dense.const.nrow 1 -none- 數字

dense.ctr 1 -none- 數字

use.rw 1 -none- 數字

tmp 1 -none- 字符

狀態 1 -none- 數字

運行上面的代碼後，您可以獲得我們問題的所需解決方案。

y1 和 y2 的最佳值：

請記住，y1 和 y2 是我們必須生產的產品 A 和產品 B 的單位：

> 最優$解決方案

[1] 45 75

最佳銷售數字：

我們可以用獲得的 y1 和 y2 的值​​產生的最大利潤是：

> 最佳$objval

[1] 2625

另請閱讀：機器學習的線性代數

線性規劃的用途

正如我們之前提到的，線性規劃在許多行業中都有應用。 以下是我們使用它的一些領域：

• 隨著送貨服務的日益普及，線性規劃已成為尋找最佳路線的最受青睞的方法之一。 當你乘坐 Ola 或 Uber 時，該軟件會使用線性規劃來找到最佳路線。 亞馬遜和聯邦快遞等快遞公司也使用它來為他們的快遞員確定最佳路線。 他們專注於減少交付時間和成本。
• 機器學習的監督學習基於線性規劃的基本概念。 在監督學習中，你必鬚根據提供的輸入數據找到最優的數學模型來預測輸出。
• 零售業使用線性規劃來優化貨架空間。 有這麼多品牌和產品可供選擇，確定將它們放在商店的哪個位置是一項非常艱鉅的任務。 產品在商店中的放置會極大地影響其銷售。 Big Bazaar、Reliance、Walmart 等主要零售連鎖店使用線性規劃來確定產品放置。 他們必須牢記消費者的利益，同時確保最佳的產品放置以產生最大的利潤。
• 公司使用線性規劃來改善他們的供應鏈。 供應鏈的效率取決於許多因素，例如選擇的路線、時間等。通過使用線性規劃，他們可以找到最佳的路線、時間和其他資源分配來優化效率。

了解有關線性規劃和數據科學的更多信息

線性規劃是數據科學中最重要的概念之一。 這也是成為一名熟練的數據科學家應該了解的基本主題。 正如我們所討論的，這個概念有很多應用，你可以在日常生活中找到它的用例。

您可以訪問我們的博客，了解有關數據科學及其相關概念的更多信息。 我們有許多寶貴的資源可以幫助您了解更多信息。 以下是一些供您進一步閱讀的內容：

• 成為數據科學家的主要原因
• 每個數據科學家都應該知道的算法
• 如何成為一名數據科學家

另一方面，您可以獲得數據科學課程，向行業專家學習。 您將通過視頻、測驗和項目進行交互式學習。 參加課程將幫助您學習成為專業數據科學家的必要技能。 查看 IIIT-B 和 upGrad 的數據科學 PG 文憑，該文憑專為在職專業人士而設，提供 10 多個案例研究和項目、實用的實踐研討會、與行業專家的指導、與行業導師的 1 對 1、400 多個小時與頂級公司的學習和工作援助。