為何分散負荷可降低成本
假設固定工作量必須分配到若干站點。把所有工作集中一處可能造成高昂擁塞成本,因此分散負荷可能有利。作為易於處理的模型,設每個站點的成本隨其自身工作量二次增長。
定義 8.6.1
(二次資源分配問題)
設 為固定工作量, 為站點數目, 為已知係數。分配是滿足 及 的向量 。問題是
記 。 越大,第 站承受負荷的成本越低。
此模型允許分數工作量,不設站點容量、固定啟用成本或不確定性;這些是模型假設,不是所有分配問題的性質。
由相等邊際成本找候選解
在第 站工作量為正時,其成本導數是 。若兩個正工作量站點的邊際成本不同,從較高者移少量工作到較低者便能降低總成本。這啟發我們令所有 。由總量等式得 ,候選解為
時各分量均為正; 時候選解為零向量。
常見錯誤
(把交換論證當作證明)
交換論證只說明:若兩個正工作量站點的邊際成本不同,該分配可以改進。它預先假設最小解存在,而且沒有直接處理含零分量的分配。它提出候選解;要證明沒有其他可行分配更好,仍須下面恆等式這類全局論證。
定理 8.6.2
(按比例分配是最優的)
在二次資源分配問題中, 給出的 是唯一的全局最小解,最小成本為 。更準確地說,每個滿足 的實向量 都有
證明
(在候選解周圍配方)
對任何滿足 的 ,令 。兩個向量之和均為 ,故 。由於每個 都有 ,展開 得
又 ,於是得到所示恆等式。所有 嚴格為正,所以恰在每個 時取等。候選解分量非負且和為 ,故可行,因而是唯一全局最小解。證明包括 ,毋須猜測局部極小值或預先假設解存在。
證明透視
各個假設在哪裏發揮作用
關鍵一步是展開點的選擇。由於比值 在每個站點都等於同一個數 ,一次項化為 ,總量約束令它消失。若在比值不相等的分配周圍展開,一次項對某些容許的 會是負數。每個 嚴格為正這一假設用了兩次:它令每個平方項非負,也令取等時必須 ,這正是唯一性。約束 在恆等式中從未使用;它只在檢查 本身可行時才需要,而因 這一點成立。證明不需要存在性定理,因為每個可行點都直接與 比較。
分配例子
例題 8.6.3
(兩個站點與平均分配)
令 ,則 、。成本為 ,兩站邊際成本均為二。相比之下, 的成本是 ,高於六;差額恰是 ,符合恆等式。
反例模式
平均工作量未必成本最低
此例的平均分配 可行但不最優,因兩站的 不同。最優時相等的是邊際成本,不一定是工作量;若所有 相等,公式就給出平均工作量。
只要明確搜尋修改後的可行集,同一恆等式亦可處理修改後的問題。
例題 8.6.4
(容量上界令邊際成本不再相等)
保留 、,並加入容量 。比例候選解 此時不可行。每個分配都具形式 ,故 ,恆等式給出
在 上,它隨 增加而遞減,所以最優解是 ,成本為 。直接計算亦有 。兩站邊際成本是 和 :受容量限制的站點想承擔更多卻不能,所以受約束的最優解不滿足邊際成本相等。
例題 8.6.5
(三個站點與最優值公式)
令 、,則 、。成本為 ,等於 。把 由第 3 站移到第 1 站,得 ,成本改變
與 一致。一次項恰好抵消,因為兩站邊際成本 與 相等。在退化情況 中,唯一的分配是 ,而公式以 給出同一點。
限制與解讀
最優值為 ,在本模型下隨 二次改變。若加入個別容量上界 ,比例候選解可能違反上界,不能直接使用;例如 排除 。固定成本、整數工作量或不同目標亦會改變問題。達到容量上界與未達上界的站點,其邊際成本不一定相等。
練習
快速檢查
(對 、,求最優分配及成本。)
解答 · 答案
,故 ,成本為 ,等於 。
快速檢查
(對 、,用平方公式求 比最優值多多少。)
解答 · 答案
此時 ,差額為 。
快速檢查
( 時唯一可行分配是甚麼?公式是否給出它?)
解答 · 答案
非負分量之和為零,故全為零;公式亦給出零向量。
快速檢查
(為何加入 後, 不再是修改後例子的解?)
解答 · 答案
它違反 。原可行集上的證明不能令一個不可行點成為修改後問題的解。