4.5　了解線性規(guī)劃

線性規(guī)劃背后的基本算法是由加州大學(xué)伯克利分校的喬治·丹特茲格（George Dantzig）在20世紀(jì)40年代初開發(fā)的。丹特茲格在為美國空軍工作時，用這個概念來試驗部隊的后勤供應(yīng)和能力規(guī)劃。在第二次世界大戰(zhàn)結(jié)束時，丹特茲格開始為五角大樓工作，并將他的算法發(fā)展為一種技術(shù)，他將其命名為線性規(guī)劃。它被用于軍事作戰(zhàn)計劃。

如今，線性規(guī)劃用于求解一些重要的實際問題，這些問題與基于某些約束的變量最小化或最大化有關(guān)。這些問題領(lǐng)域的一些示例如下：

• 根據(jù)資源情況，盡量縮短在汽修廠修車的時間
• 在分布式計算環(huán)境中分配可用的分布式資源，以盡量減少響應(yīng)時間
• 在公司內(nèi)部資源優(yōu)化配置的基礎(chǔ)上，實現(xiàn)公司利潤的最大化

線性規(guī)劃問題的形式化描述

使用線性規(guī)劃的條件如下：

• 能夠用一組方程來表述問題。
• 方程中使用的變量必須是線性的。

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

請注意，前面給出的三個例子，其目標(biāo)都是將某個變量最小化或最大化。該目標(biāo)在數(shù)學(xué)上被表示為其他變量的線性函數(shù)，稱為目標(biāo)函數(shù)。線性規(guī)劃問題的目的就是在給定的約束條件下最小化或最大化目標(biāo)函數(shù)。

給定約束條件

當(dāng)試圖最小化或最大化某些事物時，在現(xiàn)實世界中存在某些約束條件需要加以考慮。例如，當(dāng)試圖最小化修理一輛汽車所需的時間時，我們還需要考慮可用的機械修理工數(shù)量有限。通過線性方程來給定每個約束條件是制定線性規(guī)劃問題的重要部分。