作者：Julia Kho
翻譯：王闖（Chuck）
校對(duì)：zrx
本文約4400字，建議閱讀10分鐘
本文介紹了什么是優(yōu)化問題，常見的優(yōu)化問題分類，優(yōu)化問題的核心要素以及如何構(gòu)建簡(jiǎn)單的優(yōu)化模型。本文不涉及復(fù)雜的數(shù)學(xué)公式，堪稱入門優(yōu)化問題的保姆級(jí)教程。

標(biāo)簽：優(yōu)化、約束條件、Optimization

什么是優(yōu)化問題，它的背后的原理是什么？

圖片來源Unsplash，由 Ricardo Gomez Angel上傳

通過本文，您將了解一些優(yōu)化問題的基礎(chǔ)知識(shí)，以及優(yōu)化是如何在幕后真正發(fā)揮作用的。我會(huì)通過兩個(gè)例子來說明如何構(gòu)建一個(gè)簡(jiǎn)單的優(yōu)化問題，并且展示優(yōu)化問題中要素的更改如何影響我們的解決方案的。

本文將涵蓋如下主題：

什么是優(yōu)化？
優(yōu)化為什么如此重要？
優(yōu)化用在哪些地方？
約束性優(yōu)化與無約束優(yōu)化有什么區(qū)別？
優(yōu)化模型的三個(gè)核心要素是什么？
如何構(gòu)建一個(gè)簡(jiǎn)單的優(yōu)化問題（兩個(gè)示例）。

本文不會(huì)涉及復(fù)雜的數(shù)學(xué)推導(dǎo)、算法、優(yōu)化軟件，也不會(huì)討論其他不同類型的優(yōu)化問題。

什么是優(yōu)化？

簡(jiǎn)而言之，優(yōu)化就是在所有可行的解決方案中選擇最優(yōu)方案。

但是，什么是最優(yōu)呢？所謂最優(yōu)，取決于你手頭上的問題是什么。對(duì)于你正在解決的問題來說，最優(yōu)意味著最大的利潤(rùn)嗎，還是最低的成本？是否意味著節(jié)省的時(shí)間最多，還是使用的資源最少？所以說，“最優(yōu)”的定義取決于你要解決的問題。

什么時(shí)候需要優(yōu)化？當(dāng)某個(gè)問題有一個(gè)以上解決方案的時(shí)候，就可以利用優(yōu)化了。

優(yōu)化為什么如此重要？

那么我們?yōu)槭裁匆P(guān)心優(yōu)化？它為什么如此重要？

要了解它的重要性，讓我們先來看一下分析的四個(gè)不同階段。下圖是 Gartner 分析優(yōu)勢(shì)模型，這是用來衡量一個(gè)組織的數(shù)據(jù)成熟度的有用工具。

圖片來源: Cartner (2012年3月)

x 軸表示難度或復(fù)雜程度，y 軸表示價(jià)值或影響。四種不同階段的分析從事后分析到先見分析，其中先見分析最為復(fù)雜。

第一階分析是描述性分析（descriptive analytics）。它告訴你發(fā)生了什么。例如，瀏覽網(wǎng)站的平均時(shí)間或同比銷售額增長(zhǎng)。

第二階分析是診斷性分析（diagnostic analytics）。為什么會(huì)這樣？其特點(diǎn)是深入研究數(shù)據(jù)以確保在數(shù)據(jù)中能夠發(fā)現(xiàn)潛在的原因。

接下來，是預(yù)測(cè)性分析（predictive analytics）。將要發(fā)生什么？為了做出預(yù)測(cè)，我們可能會(huì)使用機(jī)器學(xué)習(xí)模型。也許你可能聽說過聚類模型或回歸模型。你猜怎么著，這些機(jī)器學(xué)習(xí)模型也是依靠?jī)?yōu)化來找到答案的。

優(yōu)化也是規(guī)范性分析（prescriptive analytics）的范疇。我們會(huì)做出哪些決定來讓事情發(fā)生？例如，我們?nèi)绾畏峙淞闶圬浖芤詫?shí)現(xiàn)利潤(rùn)最大化？將多少產(chǎn)品運(yùn)送到美國(guó)各地的倉(cāng)庫(kù)在最大限度地降低總體成本的情況下仍能滿足需求？

這些決定將具有巨大的商業(yè)價(jià)值，不是嗎？這將幫助我們提高效率，或者提供競(jìng)爭(zhēng)優(yōu)勢(shì)。優(yōu)化非常強(qiáng)大，因?yàn)槟隳軌蛟趹?zhàn)略、運(yùn)營(yíng)和戰(zhàn)術(shù)層面為組織提供指導(dǎo)。

從圖表中可以看出，優(yōu)化是最復(fù)雜的分析階段，但同時(shí)也提供了最大的商業(yè)價(jià)值。我們將在接下來的幾個(gè)示例中看到這一點(diǎn)。

優(yōu)化用在哪些地方？

圖片來源Unsplash，由Ravi Palwe上傳

你可能沒特別留意，但優(yōu)化其實(shí)無處不在。當(dāng)你使用 GPS 時(shí)，無論是谷歌地圖還是蘋果地圖，它都會(huì)幫你計(jì)算到目的地的最短行駛距離。這就是優(yōu)化。

優(yōu)化不僅在日常問題中發(fā)揮作用，而且已被應(yīng)用于各個(gè)行業(yè)的各種類型的問題當(dāng)中。以下就是兩個(gè)著名的優(yōu)化案例。

案例 1: UPS

首先討論運(yùn)輸中的優(yōu)化問題。一個(gè)著名案例來自 UPS（United Parcel Service, Inc. 美國(guó)聯(lián)合包裹運(yùn)送服務(wù)公司）。UPS 希望為其司機(jī)找到最有效的包裹遞送路線，以節(jié)省時(shí)間并降低油耗。為了節(jié)省時(shí)間，該公司決定司機(jī)應(yīng)盡可能地避免左轉(zhuǎn)。在美國(guó)，你需要等待綠燈以及前方直行無車時(shí)才能左轉(zhuǎn)。因此，取消左轉(zhuǎn)意味著更少的時(shí)間浪費(fèi)和更少的燃料消耗。UPS 創(chuàng)建了一個(gè)名為 ORION 的專有優(yōu)化軟件，以幫助司機(jī)最大限度地減少運(yùn)輸路線的左轉(zhuǎn)。

圖片引自: Holland et al.: UPS Optimizes Delivery Routes、

在上圖中，左側(cè)是駕駛員原本的路線方案，右側(cè)是 ORION 給出的解決方案。正如您在地圖上看到的，ORION 的解決方案比司機(jī)的方案要高效得多。使用 ORION 軟件可以節(jié)省 30 英里的路途。

談到商業(yè)價(jià)值，UPS稱：“自 ORION 最初部署以來，每年為 UPS 節(jié)省了大約 1 億英里和 1000 萬加侖的燃料?！?/span>

這當(dāng)然可以使他們比競(jìng)爭(zhēng)對(duì)手更具競(jìng)爭(zhēng)優(yōu)勢(shì)。正如在此處看到的，優(yōu)化為 UPS 帶來了重大的商業(yè)價(jià)值。

案例 2: 美國(guó)陸軍

接下來是一個(gè)經(jīng)典案例。最早的優(yōu)化問題之一可以追溯到 1930 年代。在第二次世界大戰(zhàn)期間，美國(guó)陸軍想搞清楚如何在滿足飲食的必需的營(yíng)養(yǎng)的同時(shí)，最大限度地降低在戰(zhàn)場(chǎng)上飲食供給的成本。

圖片來源Unsplash，由Martijn Hendrikx上傳

研究這個(gè)問題的經(jīng)濟(jì)學(xué)家喬治·斯蒂格勒發(fā)現(xiàn)，最佳飲食組合包括以下 5 種食物：370 磅小麥粉、57 罐煉乳、111 磅卷心菜、23 磅菠菜和285 磅海軍豆。

這聽起來當(dāng)然不是最美味的飲食，但一年只需 39.93 美元。有趣的是，按照今天的價(jià)格，它大約是 831 美元。

圖片引自: Wikipedia

這種飲食組合最大限度地降低了成本，還滿足了以下營(yíng)養(yǎng)要求。

圖片引自: Wikipedia

在戰(zhàn)爭(zhēng)時(shí)期，最小化成本至關(guān)重要，因此，這個(gè)優(yōu)化問題對(duì)陸軍來說具有巨大價(jià)值。

無約束優(yōu)化vs約束性優(yōu)化

如果從圖形上看優(yōu)化是什么，它只是找到最大點(diǎn)或最小點(diǎn)。

圖片來源: 作者

上圖中，我們看到的是一個(gè)無約束優(yōu)化的示例，其中最高峰是最大點(diǎn)，最低谷是最小點(diǎn)。

然而，實(shí)際上我們是有約束條件的，所以圖表看起來更像這樣。

圖片來源: 作者

我們將受到限制，因?yàn)槲覀兩硖幰粋€(gè)資源有限的世界。例如，一天只有 24 小時(shí)。我的銀行賬戶里只有有限的美元。我們可以利用的東西是有限的。

紅線代表約束，由于存在約束，我們的最大點(diǎn)將不再是最高峰，而是在峰的一半左右。上圖即說明了約束性優(yōu)化，也就是我們?cè)谟懻搩?yōu)化問題時(shí)通常需要處理的優(yōu)化類型。

優(yōu)化問題的三個(gè)核心要素

現(xiàn)在我們來介紹優(yōu)化問題都需要面對(duì)的三個(gè)核心要素。我將使用前面提到的斯蒂格勒飲食問題作為這些核心要素的示例。

1. 目標(biāo)函數(shù)

2. 決策變量

3. 約束

目標(biāo)函數(shù)

之前我們討論過“最優(yōu)”這個(gè)詞。在優(yōu)化方面，我們正在努力尋找最佳解決方案。目標(biāo)函數(shù)將幫助我們衡量什么是最優(yōu)的。

圖片引自: Wikipedia

在飲食問題中，“最優(yōu)”意味著最小化年度總成本。因此，年度總成本是我們衡量解決方案質(zhì)量的方式。也就是說，年度總成本越小，解決方案越好。

決策變量

決策變量是你必須做出決定的事情。這些是可以調(diào)整的東西，或者換句話說，是在你可控范圍之內(nèi)的東西。你不知道最優(yōu)值是多少，但優(yōu)化求解器會(huì)為你選擇最優(yōu)值。

圖片引自: Wikipedia

在飲食問題上，斯蒂格勒必須弄清楚要供給士兵什么食物以及每種食物的量。食物的種類和數(shù)量是這個(gè)問題的決策變量。

約束

約束是對(duì)這些決定的限制。在飲食問題上，斯蒂格勒有以下營(yíng)養(yǎng)限制。

圖片引自: Wikipedia

一個(gè)成年人每天需要攝入 3000 卡路里熱量，70 克蛋白質(zhì)，等等。飲食組合的選項(xiàng)需要滿足這些要求。約束這個(gè)元素非常重要，因?yàn)檐浖梢詾槟?jì)算并找到最佳解決方案，但軟件并不理解現(xiàn)實(shí)世界。你必須為機(jī)器翻譯現(xiàn)實(shí)生活中的約束，否則，你最終可能會(huì)得到一個(gè)無法實(shí)際操作的解決方案。

解決方案

我們經(jīng)常使用解決方案這個(gè)詞，所以讓我們清晰地定義一些處理解決方案的術(shù)語。

解決方案是每個(gè)決策變量的一組值。例如，5磅菠菜。這可以是一個(gè)解決方案。20磅菠菜。這可能是另一種解決方案。
可行方案是實(shí)際可行的解決方案。也就是說，一個(gè)滿足我們約束的解決方案。如果 20 磅菠菜足以滿足營(yíng)養(yǎng)需求，那么這是一個(gè)可行方案。
為我們提供最佳價(jià)值的一種可行解決方案是我們的最佳方案。在飲食問題上，就是23磅菠菜。

優(yōu)化問題1

現(xiàn)在我們已經(jīng)掌握了所有術(shù)語，讓我們看一個(gè)超級(jí)簡(jiǎn)單的玩具優(yōu)化問題。這個(gè)問題非常簡(jiǎn)單，以幫助你輕松進(jìn)入解決優(yōu)化問題的狀態(tài)。這里只是學(xué)習(xí)使用我們學(xué)習(xí)過的術(shù)語來構(gòu)建優(yōu)化問題，并理解優(yōu)化是如何工作的，所以不要太擔(dān)心解決方案。

圖片來自 Unsplash，由 June Gathercole 上傳

這是我們手頭的問題：

非常毛絨玩具公司（It's So Fluffy LLC）想要最大化利潤(rùn)。
他們有兩種產(chǎn)品：可愛的獨(dú)角獸抱枕和肥貓玩偶。
非常毛絨玩具公司有足夠的雪尼爾材料來生產(chǎn)最多 2 個(gè)可愛的獨(dú)角獸抱枕。
非常毛絨玩具公司有足夠的面料生產(chǎn)最多 3 個(gè)肥貓玩偶。
獨(dú)角獸抱枕有 15 美元的利潤(rùn)，肥貓玩偶有 10 美元的利潤(rùn)。

花點(diǎn)時(shí)間來想一想這個(gè)優(yōu)化問題的三個(gè)核心要素是什么。如果忘記了核心要素，這里有一個(gè)提醒。

目標(biāo)函數(shù)
決策變量
約束

目標(biāo)函數(shù)是什么？我們希望為公司帶來最大的利潤(rùn)。利潤(rùn)是獨(dú)角獸抱枕的價(jià)格乘以賣出的獨(dú)角獸抱枕的個(gè)數(shù)加上肥貓玩偶的價(jià)格乘以賣出的肥貓玩偶的個(gè)數(shù)。

什么是決策變量？公司可以決定哪些事情？要制作的獨(dú)角獸抱枕的數(shù)量和要制作的肥貓玩偶的數(shù)量。

有哪些約束條件？由于材料限制，最多只能生產(chǎn)2個(gè)獨(dú)角獸抱枕和3個(gè)肥貓玩偶。

另一件值得注意的事情是，不可能生產(chǎn)少于 0 個(gè)獨(dú)角獸抱枕或 0 個(gè)肥貓玩偶。盡管這對(duì)我們來說是直觀和合乎邏輯的，但將這些約束構(gòu)建到問題中是一種很好的做法。你希望避免計(jì)算機(jī)可能輸出不合邏輯的解決方案的情況，例如在這種情況下的負(fù)數(shù)。

圖片來源：作者

現(xiàn)在讓我們將剛剛提出的組件轉(zhuǎn)換為圖形形式，以便將問題可視化。

下圖中的 X 和 Y 軸是我們的決策變量。現(xiàn)在讓我們畫出我們的約束。在向下滾動(dòng)之前，請(qǐng)花點(diǎn)時(shí)間考慮一下如何在此圖上繪制約束。

圖片來源: 作者

它應(yīng)該如下所示。圖表上的紅線代表我們針對(duì)此優(yōu)化問題應(yīng)用的約束。分別有一條垂直線在x軸0 和 2 處，分別有一條水平線在y軸 0 和 3 處。其中綠色部分我們稱之為可行解決方案空間，粉色部分稱為不可行解空間。

圖片來源: 作者

在綠色的可行解決方案空間內(nèi)，我們現(xiàn)在想要找到要制作的最佳獨(dú)角獸抱枕和肥貓玩偶的數(shù)量。請(qǐng)記住，獨(dú)角獸抱枕的利潤(rùn)為 15 美元，肥貓玩偶的利潤(rùn)為 10 美元。如果該公司生產(chǎn) 1 個(gè)獨(dú)角獸抱枕和 0 個(gè)肥貓玩偶，它將賺 15 美元。如果該公司生產(chǎn) 2 個(gè)獨(dú)角獸抱枕和 1 個(gè)肥貓玩偶，它將賺 40 美元。等等。

我已經(jīng)計(jì)算了下圖中每個(gè)可行解決方案的利潤(rùn)。那么哪一個(gè)是最優(yōu)解呢？也就是說，哪一個(gè)會(huì)幫助我們實(shí)現(xiàn)利潤(rùn)最大化？

圖片來源: 作者

最高利潤(rùn)為60美元，即制作了2個(gè)獨(dú)角獸抱枕和3個(gè)肥貓玩偶。

圖片來源: 作者

最優(yōu)解: 獨(dú)角獸抱枕 = 2, 肥貓玩偶 = 3

該解決方案是合理的，其實(shí)并不需要經(jīng)過這么些步驟，但這里只是想幫你理解如何構(gòu)建優(yōu)化問題，就像我們剛剛所做的那樣。這很重要，因?yàn)橛?jì)算機(jī)會(huì)執(zhí)行運(yùn)算來幫你找到解決方案，但你必須正確地為計(jì)算機(jī)構(gòu)建問題。

優(yōu)化問題2

在問題 1 的基礎(chǔ)上，現(xiàn)在讓我們?yōu)閱栴}添加一個(gè)額外的約束條件。

這家小型有限責(zé)任公司的人力只夠一天生產(chǎn)最多 4 件產(chǎn)品。

這對(duì)現(xiàn)在的問題有什么影響？我們有一個(gè)額外的約束條件需要添加到問題中，但其他一切都保持不變。

圖片來源：作者

現(xiàn)在，讓我們也將此約束條件添加到圖表中。下面的對(duì)角紅線是我們剛剛添加的新約束。由于增加了此約束，綠色矩形右上角的三角形區(qū)域?qū)⒉辉偈蔷G色。

圖片來源: 作者

因此，在我們可行的解決方案空間內(nèi)，以下是每個(gè)解決方案的利潤(rùn)。

圖片來源: 作者

最大利潤(rùn)是50美元, 即制作了2個(gè)獨(dú)角獸抱枕和2個(gè)肥貓玩偶。

圖片來源: 作者

最優(yōu)解: 獨(dú)角獸抱枕 = 2, 肥貓玩偶 = 2

問題 1 與問題 2的比較

如果我們將問題 1 的解決方案與問題 2 的解決方案進(jìn)行比較，您會(huì)注意到什么？

圖片來源: 作者

問題 2 的可行解空間要比問題1的小。問題 2 的解決方案得到的利潤(rùn)較低。

發(fā)生了什么？

額外的約束條件會(huì)縮小可行解空間，因而會(huì)使得我們的解決方案變差。在問題設(shè)定時(shí)意識(shí)到這一點(diǎn)非常重要。你要添加的約束條件是必需的嗎？因?yàn)榧s束越少，優(yōu)化軟件找到最優(yōu)解決方案的空間就會(huì)越大。

原文標(biāo)題：

A Gentle Introduction to Optimization

原文鏈接：

https://towardsdatascience.com/a-gentle-introduction-to-optimization-f95938ce475e

編輯：黃繼彥

校對(duì)：林亦霖

譯者簡(jiǎn)介

王闖（Chuck），臺(tái)灣清華大學(xué)資訊工程碩士。曾任奧浦諾管理咨詢公司數(shù)據(jù)分析主管，現(xiàn)任尼爾森市場(chǎng)研究公司數(shù)據(jù)科學(xué)經(jīng)理。很榮幸有機(jī)會(huì)通過數(shù)據(jù)派THU微信公眾平臺(tái)和各位老師、同學(xué)以及同行前輩們交流學(xué)習(xí)。

翻譯組招募信息

工作內(nèi)容：需要一顆細(xì)致的心，將選取好的外文文章翻譯成流暢的中文。如果你是數(shù)據(jù)科學(xué)/統(tǒng)計(jì)學(xué)/計(jì)算機(jī)類的留學(xué)生，或在海外從事相關(guān)工作，或?qū)ψ约和庹Z水平有信心的朋友歡迎加入翻譯小組。

你能得到：定期的翻譯培訓(xùn)提高志愿者的翻譯水平，提高對(duì)于數(shù)據(jù)科學(xué)前沿的認(rèn)知，海外的朋友可以和國(guó)內(nèi)技術(shù)應(yīng)用發(fā)展保持聯(lián)系，THU數(shù)據(jù)派產(chǎn)學(xué)研的背景為志愿者帶來好的發(fā)展機(jī)遇。

其他福利：來自于名企的數(shù)據(jù)科學(xué)工作者，北大清華以及海外等名校學(xué)生他們都將成為你在翻譯小組的伙伴。

點(diǎn)擊文末“閱讀原文”加入數(shù)據(jù)派團(tuán)隊(duì)~

轉(zhuǎn)載須知

如需轉(zhuǎn)載，請(qǐng)?jiān)陂_篇顯著位置注明作者和出處（轉(zhuǎn)自：數(shù)據(jù)派ID：DatapiTHU），并在文章結(jié)尾放置數(shù)據(jù)派醒目二維碼。有原創(chuàng)標(biāo)識(shí)文章，請(qǐng)發(fā)送【文章名稱-待授權(quán)公眾號(hào)名稱及ID】至聯(lián)系郵箱，申請(qǐng)白名單授權(quán)并按要求編輯。

發(fā)布后請(qǐng)將鏈接反饋至聯(lián)系郵箱（見下方）。未經(jīng)許可的轉(zhuǎn)載以及改編者，我們將依法追究其法律責(zé)任。

點(diǎn)擊“閱讀原文”擁抱組織

獨(dú)家 | 零基礎(chǔ)入門優(yōu)化問題

什么是優(yōu)化問題，它的背后的原理是什么？

優(yōu)化用在哪些地方？

案例 1: UPS

談到商業(yè)價(jià)值，UPS稱：“自 ORION 最初部署以來，每年為 UPS 節(jié)省了大約 1 億英里和 1000 萬加侖的燃料?！?/span>

這當(dāng)然可以使他們比競(jìng)爭(zhēng)對(duì)手更具競(jìng)爭(zhēng)優(yōu)勢(shì)。正如在此處看到的，優(yōu)化為 UPS 帶來了重大的商業(yè)價(jià)值。

案例 2: 美國(guó)陸軍

在戰(zhàn)爭(zhēng)時(shí)期，最小化成本至關(guān)重要，因此，這個(gè)優(yōu)化問題對(duì)陸軍來說具有巨大價(jià)值。

無約束優(yōu)化vs約束性優(yōu)化

什么是優(yōu)化問題，它的背后的原理是什么？

談到商業(yè)價(jià)值，UPS稱：“自 ORION 最初部署以來，每年為 UPS 節(jié)省了大約 1 億英里和 1000 萬加侖的燃料?！?/span>

這當(dāng)然可以使他們比競(jìng)爭(zhēng)對(duì)手更具競(jìng)爭(zhēng)優(yōu)勢(shì)。正如在此處看到的，優(yōu)化為 UPS 帶來了重大的商業(yè)價(jià)值。

在戰(zhàn)爭(zhēng)時(shí)期，最小化成本至關(guān)重要，因此，這個(gè)優(yōu)化問題對(duì)陸軍來說具有巨大價(jià)值。