本節講解線性規劃的基本可行解、單純形步驟與對偶證書。先備知識是基本矩陣代數;優化術語會在使用前逐一說明。
動機
編譯器要安排幾種可分割的計算工作,每種工作按固定比率耗用處理器時間及記憶體。若效能評分也是工作量的線性組合,便得到線性規劃。解幾條邊界方程只會產生候選安排,還未說明其他可行安排為甚麼不能更好。我們需要尋找方法,也需要可獨立核驗的最優性證書。
「線性」指目標及限制的表達式,並不表示最優決策隨數據線性變化。半空間的交集有角點,係數稍變便可能令最佳角點轉移。幾何說明這種現象,矩陣則把同一推理延伸到無法畫圖的高維空間。
變量是否可分割是模型假設。處理器時間可以是分數,已安裝裝置的數目通常必須是整數。本節先處理可分割模型;它的界也會用於後面的整數模型。先寫清楚最大化還是最小化,才判斷某個數值究竟是上界還是下界。
定義
定義 1.1.1
(可行性、鬆弛量及原始—對偶問題)
對實數數據 、、,考慮
不等式逐分量理解。滿足全部限制的點稱為可行點;在可行點中取得最佳目標值的點稱為最優點。原始鬆弛量為 ,對偶餘量為 。可行集是多面體,即有限個閉半空間的交集;有界多面體稱為多胞體。
非負性必須由模型指定。自由變量可寫成兩個非負變量之差;上界不等式可加入非負鬆弛量改成等式。限制乘以負一時,不等號也必須反向。每一步轉換都要保留原來決策的意義,不能只記公式外形。
單純形法使用等式標準形 、,其中 有滿行秩,行數為 。選取 個線性無關的列構成基矩陣 ,其餘列記為 。基本解令 、;若基本值全部非負,便是基本可行解。某個基本值為零時稱為退化,這與有多個最優點是不同概念。
頂點不能寫成兩個不同可行點的非平凡凸組合。在等式標準形中,頂點恰好是基本可行解:正座標所對應的列若線性相關,便能向正負兩個方向作小幅可行移動;若線性無關,這種分解便不可能。
定理/命題
定理 1.1.2
(已取得的最優值有基本解代表)
設 有滿行秩。若 有已取得的有限最優值,則至少有一個最優點是基本可行解。特別地,非空有界可行集必有基本最優解。
「已取得」是明確假設。有界閉可行集的緊緻性配合目標的連續性保證取得最優值;但有界並非必要。無界可行集也可能有有限而已取得的最優值。定理並沒有聲稱每一個可行點或每一個最優點都是頂點。
反例模式
沒有符號限制時,最優點未必在頂點上
錯誤說法:每個已取得最優值的線性規劃都有最優頂點。在 中,只在 的限制下最大化 。最大值 在整條直線 上取得,但沒有任何可行點是頂點,因為 。定理的標準形排除了這種情況: 表示可行集不含直線。把 寫成 ,其中 ,頂點便恢復: 是最優點,代表 。
定理 1.1.3
(對偶界與零差距證書)
若 原始可行而 對偶可行,則
等號成立當且僅當每個 及每個 。這些乘積條件稱為互補鬆弛。若兩個可行點目標值相等,兩者都最優。
這份證書不需要先假設可行集有界:目標值相等的可行點已經界定所有競爭者。通常的強對偶定理還保證有限原始最優值有同值對偶最優解,但一般存在性證明不在本節範圍內。下面會直接構造對偶點並核驗,例題不依賴尚未證明的存在性結論。
證明思路
在最優點中,選正座標數目最少的一個;這是有限個可能支撐大小中的最小值。若其正支撐所對應的列相關,便有非零 支撐於這些座標且 。足夠小的正數 令 及 都非負且滿足等式。最優性迫使 ,否則其中一個方向立即改善目標。
選擇 的符號,令至少一個座標下降,再移動至第一個座標碰到零。其他座標仍非負,目標不變,原來支撐以外也沒有新增正座標,卻得到更小的最優支撐,矛盾。所以正支撐列無關,可補成完整的基;補入的基本值為零。這也涵蓋退化情況。
證明透視
縮小支撐如何得到頂點
這個論證從不直接尋找頂點,而是縮小一個最優點的支撐。首先用到「已取得」,才有最優點可用。支撐列線性相關給出只涉及支撐座標、且 的方向 ,所以正負兩個方向的小幅移動都保持可行。給出 的是最優性而非可行性,因此沿 移動不改變目標。真正的關鍵是最後的比值步:推進到第一個座標變為零,支撐減少一個座標而不新增任何座標,與最小性矛盾。滿行秩只在最後用到,用來把無關的列補成一組基。
第二個定理只需展開右邊,含 的項互相抵消。餘下每一項都非負,因此總和為零等價於逐項乘積為零。同值可行對把所有原始競爭者壓在共同值之下,也把全部對偶競爭者托在其上,故雙方最優。
證明透視
差距何時才是證書?
恆等式純屬代數,對不可行向量也成立。要把它變成不等式,必須分別檢查原始鬆弛、原始變量、對偶乘數及對偶餘量的非負性。四種符號條件令每個乘積非負,零總和才迫使逐項為零。最後用弱對偶比較所有競爭者,不依賴主元歷史或強對偶存在性。未檢查可行性的「很小差距」仍不是證明。
字典如何產生一步主元運算
選定基後,等式及目標寫成
是約化成本。最大化時若全部約化成本非正,任何非基本變量的增加都不能改善目標。因為所有可行點都滿足字典,這是全局證明,並非只檢查附近方向。
若某個約化成本為正,讓該變量增加 ,令 。基本座標變成 ;只有 的行限制步長,取最小比值 。沒有正分量時得到可行改善射線,證明目標無界。最小比值為零則可能退化,目標暫時不增。重複的零步長主元可能循環,除非採用 Bland 規則等防循環規則;本節講解主元邏輯,並不聲稱任意處理平手都必定終止。
例題詳解
例題 1.1.4
(兩次主元完成求解)
最大化計算工作評分 ,限制為
初始鬆弛字典是 、、,目標 。讓 進基,比值四及二中取二(第三行不限制這個方向),故 離基。代入得
再讓 進基,可增加二或三中較小的二,故 離基。最終
鬆弛量非負使任何可行分數至多十。令 得 、,確實達到十。字典本身已是一份最優性證明。
例題 1.1.5
(獨立對偶證書及敏感度範圍)
上題取 ,則 ,而 。非負性、列不等式及同值性已證明最優,毋須重看主元歷史。第三限制有剩餘容量,所以對應乘數為零;緊限制的乘數則不一定必須為正。
把第一容量改成 ,同一基給出 、、。可行範圍恰為 ;在此範圍,不變的對偶點證明最優值 。超出範圍時,只要模型可行,該對偶點仍可提供上界,但這個原始候選點違反非負性。乘數的精確變化率有適用區間,不能無限外推。
例題 1.1.6
(區分三種不同結果)
與 無法同時成立,是不可行問題。只限制 而最大化 則有可行點,但射線 使目標無界。兩者不能都稱為「沒有好解」。
最大化 、限制 及非負性時,、 及整條連線都最優。中點不是頂點,所以基本解定理只保證存在某個基本代表。零約化成本可能指向平坦最優方向;但退化時,一次零成本主元也可能沒有移動到不同點。
常見錯誤
解出一組活動限制後,仍須檢查全部未使用的不等式及符號限制。可行不等於最優,位於幾條邊界的交點甚至不一定可行。圖中的候選角點必須有完整性理由,或配上獨立上界證書。
對偶符號取決於原始慣例。這裏是非負變量、上界限制的最大化;等式限制應配自由乘數,自由原始變量應配對偶等式。改了原始形式而照抄舊符號,便可能失去上界性。互補鬆弛也不表示鬆弛及乘數都必須為零:正鬆弛迫使乘數為零,緊限制卻容許零乘數。同樣,取零的決策變量也不迫使其對偶不等式嚴格成立。使用任何互補乘積前,先檢查可行性。
比值檢驗只除以正方向分量。負分量表示基本值正在增加,不會威脅非負性。數值軟件另需穩定線性求解及容差政策;本節的精確代數不等於已證明近奇異基的數值穩定性。
總結
多面體把可行性連到基,主元在保留可行性的同時改變表示,約化成本說明能否改善。最終字典與對偶點都可成為可核驗證書。不可行、目標無界、已取得有限最優值及多重最優值,必須分別判斷。
練習
快速檢查
(最大化 ,限制 、 及非負性,求最優點及按上文原始慣例的對偶證書。)
解答 · 答案
的值為四。取 ,有 、,對偶值 。同值可行對證明最優;亦可直接合併限制得 。
快速檢查
(把第一例的目標改為 ,描述全部最優點及一個對偶最優點。舊點是否仍最優?)
解答 · 答案
最優值四,全部最優點為 、。下界來自 ,上界來自 。舊點 仍最優,但不再唯一。對偶點 可行且值四。
快速檢查
(基本值為 ,正約化成本的進基方向 ,求步長及重標基前的新基本值。方向改成 呢?)
解答 · 答案
第一行給 ,第二行隨步長增加,故取二。舊基本值變成 ,進基變量為二。改成全負方向後,兩個基本值均增加,沒有有限步長上限;正約化成本遂給出改善射線,證明目標無界。
快速檢查
(已核實可行的一對點有 、、、,是否足以證明最優?若只把第二乘數改為一,並重新核實所有可行條件呢?)
解答 · 答案
差距是 ,足以證明雙方最優。改動後鬆弛貢獻變為二,差距為正,這一對點不能證明同值。正差距本身未說明究竟哪一點次優,只說這份等值證書失敗。
快速檢查
(證明兩個不同最優點之間整條線段都最優,並解釋為甚麼線段內點不是基本可行解。)
解答 · 答案
線性不等式保持凸組合可行,線性目標保持其共同最優值。嚴格內點是兩個不同可行點的非平凡凸組合,按定義不是頂點,因而不是基本可行解;端點本身也未必是頂點。