本文約4400字,建議閱讀10分鐘
本文介紹了什麼是優化問題,常見的優化問題分類,優化問題的核心要素以及如何構建簡單的優化模型。本文不涉及複雜的數學公式,堪稱入門優化問題的保姆級教程。
标簽:優化、約束條件、Optimization
圖片來源Unsplash,由 Ricardo Gomez Angel上傳
通過本文,您将了解一些優化問題的基礎知識,以及優化是如何在幕後真正發揮作用的。我會通過兩個例子來說明如何構建一個簡單的優化問題,并且展示優化問題中要素的更改如何影響我們的解決方案的。
本文将涵蓋如下主題:
本文不會涉及複雜的數學推導、算法、優化軟件,也不會讨論其他不同類型的優化問題。
什麼是優化?
簡而言之,優化就是在所有可行的解決方案中選擇最優方案。
但是,什麼是最優呢?所謂最優,取決于你手頭上的問題是什麼。對于你正在解決的問題來說,最優意味着最大的利潤嗎,還是最低的成本?是否意味着節省的時間最多,還是使用的資源最少?所以說,“最優”的定義取決于你要解決的問題。
什麼時候需要優化?當某個問題有一個以上解決方案的時候,就可以利用優化了。
優化為什麼如此重要?
那麼我們為什麼要關心優化?它為什麼如此重要?
要了解它的重要性,讓我們先來看一下分析的四個不同階段。下圖是 Gartner 分析優勢模型,這是用來衡量一個組織的數據成熟度的有用工具。
圖片來源: Cartner (2012年3月)
x 軸表示難度或複雜程度,y 軸表示價值或影響。四種不同階段的分析從事後分析到先見分析,其中先見分析最為複雜。
第一階分析是描述性分析(descriptive analytics)。它告訴你發生了什麼。例如,浏覽網站的平均時間或同比銷售額增長。
第二階分析是診斷性分析(diagnostic analytics)。為什麼會這樣?其特點是深入研究數據以确保在數據中能夠發現潛在的原因。
接下來,是預測性分析(predictive analytics)。将要發生什麼?為了做出預測,我們可能會使用機器學習模型。也許你可能聽說過聚類模型或回歸模型。你猜怎麼着,這些機器學習模型也是依靠優化來找到答案的。
優化也是規範性分析(prescriptive analytics)的範疇。我們會做出哪些決定來讓事情發生?例如,我們如何分配零售貨架以實現利潤最大化?将多少産品運送到美國各地的倉庫在最大限度地降低總體成本的情況下仍能滿足需求?
這些決定将具有巨大的商業價值,不是嗎?這将幫助我們提高效率,或者提供競争優勢。優化非常強大,因為你能夠在戰略、運營和戰術層面為組織提供指導。
從圖表中可以看出,優化是最複雜的分析階段,但同時也提供了最大的商業價值。我們将在接下來的幾個示例中看到這一點。
圖片來源Unsplash,由Ravi Palwe上傳
你可能沒特别留意,但優化其實無處不在。當你使用 GPS 時,無論是谷歌地圖還是蘋果地圖,它都會幫你計算到目的地的最短行駛距離。這就是優化。
優化不僅在日常問題中發揮作用,而且已被應用于各個行業的各種類型的問題當中。以下就是兩個著名的優化案例。
首先讨論運輸中的優化問題。一個著名案例來自 UPS(United Parcel Service, Inc. 美國聯合包裹運送服務公司)。UPS 希望為其司機找到最有效的包裹遞送路線,以節省時間并降低油耗。為了節省時間,該公司決定司機應盡可能地避免左轉。在美國,你需要等待綠燈以及前方直行無車時才能左轉。因此,取消左轉意味着更少的時間浪費和更少的燃料消耗。UPS 創建了一個名為 ORION 的專有優化軟件,以幫助司機最大限度地減少運輸路線的左轉。
圖片引自: Holland et al.: UPS Optimizes Delivery Routes、
在上圖中,左側是駕駛員原本的路線方案,右側是 ORION 給出的解決方案。正如您在地圖上看到的,ORION 的解決方案比司機的方案要高效得多。使用 ORION 軟件可以節省 30 英裡的路途。
接下來是一個經典案例。最早的優化問題之一可以追溯到 1930 年代。在第二次世界大戰期間,美國陸軍想搞清楚如何在滿足飲食的必需的營養的同時,最大限度地降低在戰場上飲食供給的成本。
圖片來源Unsplash,由Martijn Hendrikx上傳
研究這個問題的經濟學家喬治·斯蒂格勒發現,最佳飲食組合包括以下 5 種食物:370 磅小麥粉、57 罐煉乳、111 磅卷心菜、23 磅菠菜和285 磅海軍豆。
這聽起來當然不是最美味的飲食,但一年隻需 39.93 美元。有趣的是,按照今天的價格,它大約是 831 美元。
圖片引自: Wikipedia
這種飲食組合最大限度地降低了成本,還滿足了以下營養要求。
圖片引自: Wikipedia
如果從圖形上看優化是什麼,它隻是找到最大點或最小點。
圖片來源: 作者
上圖中,我們看到的是一個無約束優化的示例,其中最高峰是最大點,最低谷是最小點。
然而,實際上我們是有約束條件的,所以圖表看起來更像這樣。
圖片來源: 作者
我們将受到限制,因為我們身處一個資源有限的世界。例如,一天隻有 24 小時。我的銀行賬戶裡隻有有限的美元。我們可以利用的東西是有限的。
紅線代表約束,由于存在約束,我們的最大點将不再是最高峰,而是在峰的一半左右。上圖即說明了約束性優化,也就是我們在讨論優化問題時通常需要處理的優化類型。
優化問題的三個核心要素
現在我們來介紹優化問題都需要面對的三個核心要素。我将使用前面提到的斯蒂格勒飲食問題作為這些核心要素的示例。
1. 目标函數
2. 決策變量
3. 約束
目标函數
之前我們讨論過“最優”這個詞。在優化方面,我們正在努力尋找最佳解決方案。目标函數将幫助我們衡量什麼是最優的。
圖片引自: Wikipedia
在飲食問題中,“最優”意味着最小化年度總成本。因此,年度總成本是我們衡量解決方案質量的方式。也就是說,年度總成本越小,解決方案越好。
決策變量
決策變量是你必須做出決定的事情。這些是可以調整的東西,或者換句話說,是在你可控範圍之内的東西。你不知道最優值是多少,但優化求解器會為你選擇最優值。
圖片引自: Wikipedia
在飲食問題上,斯蒂格勒必須弄清楚要供給士兵什麼食物以及每種食物的量。食物的種類和數量是這個問題的決策變量。
約束
約束是對這些決定的限制。在飲食問題上,斯蒂格勒有以下營養限制。
圖片引自: Wikipedia
一個成年人每天需要攝入 3000 卡路裡熱量,70 克蛋白質,等等。飲食組合的選項需要滿足這些要求。約束這個元素非常重要,因為軟件可以為您計算并找到最佳解決方案,但軟件并不理解現實世界。你必須為機器翻譯現實生活中的約束,否則,你最終可能會得到一個無法實際操作的解決方案。
解決方案
我們經常使用解決方案這個詞,所以讓我們清晰地定義一些處理解決方案的術語。
優化問題1
現在我們已經掌握了所有術語,讓我們看一個超級簡單的玩具優化問題。這個問題非常簡單,以幫助你輕松進入解決優化問題的狀态。這裡隻是學習使用我們學習過的術語來構建優化問題,并理解優化是如何工作的,所以不要太擔心解決方案。
圖片來自 Unsplash,由 June Gathercole 上傳
這是我們手頭的問題:
花點時間來想一想這個優化問題的三個核心要素是什麼。如果忘記了核心要素,這裡有一個提醒。
目标函數是什麼?我們希望為公司帶來最大的利潤。利潤是獨角獸抱枕的價格乘以賣出的獨角獸抱枕的個數加上肥貓玩偶的價格乘以賣出的肥貓玩偶的個數。
什麼是決策變量?公司可以決定哪些事情?要制作的獨角獸抱枕的數量和要制作的肥貓玩偶的數量。
有哪些約束條件?由于材料限制,最多隻能生産2個獨角獸抱枕和3個肥貓玩偶。
另一件值得注意的事情是,不可能生産少于 0 個獨角獸抱枕或 0 個肥貓玩偶。盡管這對我們來說是直觀和合乎邏輯的,但将這些約束構建到問題中是一種很好的做法。你希望避免計算機可能輸出不合邏輯的解決方案的情況,例如在這種情況下的負數。
圖片來源:作者
現在讓我們将剛剛提出的組件轉換為圖形形式,以便将問題可視化。
下圖中的 X 和 Y 軸是我們的決策變量。現在讓我們畫出我們的約束。在向下滾動之前,請花點時間考慮一下如何在此圖上繪制約束。
圖片來源: 作者
它應該如下所示。圖表上的紅線代表我們針對此優化問題應用的約束。分别有一條垂直線在x軸0 和 2 處,分别有一條水平線在y軸 0 和 3 處。其中綠色部分我們稱之為可行解決方案空間,粉色部分稱為不可行解空間。
圖片來源: 作者
在綠色的可行解決方案空間内,我們現在想要找到要制作的最佳獨角獸抱枕和肥貓玩偶的數量。請記住,獨角獸抱枕的利潤為 15 美元,肥貓玩偶的利潤為 10 美元。如果該公司生産 1 個獨角獸抱枕和 0 個肥貓玩偶,它将賺 15 美元。如果該公司生産 2 個獨角獸抱枕和 1 個肥貓玩偶,它将賺 40 美元。等等。
我已經計算了下圖中每個可行解決方案的利潤。那麼哪一個是最優解呢?也就是說,哪一個會幫助我們實現利潤最大化?
圖片來源: 作者
最高利潤為60美元,即制作了2個獨角獸抱枕和3個肥貓玩偶。
圖片來源: 作者
最優解: 獨角獸抱枕 = 2, 肥貓玩偶 = 3
該解決方案是合理的,其實并不需要經過這麼些步驟,但這裡隻是想幫你理解如何構建優化問題,就像我們剛剛所做的那樣。這很重要,因為計算機會執行運算來幫你找到解決方案,但你必須正确地為計算機構建問題。
優化問題2
在問題 1 的基礎上,現在讓我們為問題添加一個額外的約束條件。
這對現在的問題有什麼影響?我們有一個額外的約束條件需要添加到問題中,但其他一切都保持不變。
圖片來源:作者
現在,讓我們也将此約束條件添加到圖表中。下面的對角紅線是我們剛剛添加的新約束。由于增加了此約束,綠色矩形右上角的三角形區域将不再是綠色。
圖片來源: 作者
因此,在我們可行的解決方案空間内,以下是每個解決方案的利潤。
圖片來源: 作者
最大利潤是50美元, 即制作了2個獨角獸抱枕和2個肥貓玩偶。
圖片來源: 作者
最優解: 獨角獸抱枕 = 2, 肥貓玩偶 = 2
問題 1 與問題 2的比較
如果我們将問題 1 的解決方案與問題 2 的解決方案進行比較,您會注意到什麼?
圖片來源: 作者
問題 2 的可行解空間要比問題1的小。問題 2 的解決方案得到的利潤較低。
發生了什麼?
額外的約束條件會縮小可行解空間,因而會使得我們的解決方案變差。在問題設定時意識到這一點非常重要。你要添加的約束條件是必需的嗎?因為約束越少,優化軟件找到最優解決方案的空間就會越大。
原文标題:
A Gentle Introduction to Optimization
原文鍊接:
/a-gentle-introduction-to-optimization-f95938ce475e
有話要說...