3.2 對偶理論與影子價格#

本章導言#

線性規劃不僅能告訴管理者「應該生產多少才能獲利最大」，更能回答一個同樣重要的問題：「這些有限資源值多少錢？」

在前一節的例題中，工廠有機器時間與人工時間兩項資源限制。若市場上有人願意出價購買一小時機器時間，或者工廠考慮加班增加人工時數，管理者就必須判斷：多取得一單位資源，能為公司帶來多少額外利潤？這個「額外利潤」就是該資源對當前最優生產計畫而言的邊際價值（marginal value）。

線性規劃理論中，這個概念透過對偶理論（Duality Theory） 系統地定義。對偶理論指出：每一個線性規劃問題（稱為原問題（Primal））都有一個對應的對偶問題（Dual）。兩者之間有密切的數學關係，不僅解的結構相關，更重要的是：對偶問題的最適解中，對應每一個原問題限制條件的變數值，正是該限制資源的「影子價格」（shadow price）。

「影子價格」這個名稱很貼切：它不是市場上真正的交易價格，而是隱藏在最優資源配置下的內部價值。在資源已經被最有效利用的情況下，多一單位稀缺資源的邊際價值，就是這個影子價格；若某項資源尚有剩餘（未用盡），那麼它的影子價格應該為 $0$ ，因為多一單位也不會改善目標函數值。

對偶理論最早由 John von Neumann（約翰·馮·諾伊曼，1903–1957） 在 1947 年左右提出。他在與 Dantzig 討論線性規劃時，從矩陣對策理論（game theory） 的角度發現了原問題與對偶問題的等價關係。這個發現不僅豐富了線性規劃理論，更強化了最佳化與經濟理論之間的聯繫。

原問題與對偶問題的轉換關係#

以 3.1 節的例題為例，建立對偶問題來理解影子價格。

原問題（Primal），最大化利潤： $$ \max Z = 40 x_1 + 50 x_2 $$ 限制： $$ \begin{aligned} 2x_1 + x_2 &\le 100 \quad (\text{機器時間})\ x_1 + 2x_2 &\le 80 \quad (\text{人工時間})\ x_1,x_2 &\ge 0 \end{aligned} $$

最適解為 $x_1^*=40, x_2^*=20, Z^*=2600$ 。

現在假設有一家「資源買家」想購買這兩項資源的全部或部分使用權。買家必須對每小時機器時間出價 $y_1$ 元、每小時人工時間出價 $y_2$ 元。買家希望以最小總價錢購得足夠生產一單位產品 A 與一單位產品 B 的資源。而對工廠而言，若賣出的資資源價值低於生產該產品所能獲得的利潤，工廠就不會同意賣出資源。這個「資源估價」的思路導出了對偶問題。

對偶問題（Dual），最小化資源總價值： $$ \min W = 100 y_1 + 80 y_2 $$ 限制： $$ \begin{aligned} 2y_1 + y_1? \quad \text{修正：} \ 2y_1 + y_1 \text{應為}\quad 2y_1 + y_2 &\ge 40 \quad (\text對應產品 A）\ y_1 + 2y_2 &\ge 50 \quad (對應產品 B）\ y_1,y_2 &\ge 0 \end{aligned} $$

對偶限制的意義：為生產一單位產品 A 所需的資源（機器 $2$ 小時、人工 $1$ 小時）的總價值必須至少是 $40$ 元（產品 A 的利潤），否極買家出價太低工廠不願賣資源。同理對產品 B 至少 $50$ 元。

買家要在這些限制下求 $W = 100y1 + 80y2$ 的最小值。

強對偶定理與弱對偶定理#

線性規劃最重要的定理是強對偶定理（Strong Duality Theorem）：若原問題有最優解 $Z^*$ ，對偶問題也有最優解 $W^*$ ，且 $Z^* = W^*$ 。

在上例中，我們預期對偶最優值也會是 $2600$ 元。此外還有弱對偶定理（Weak Duality Theorem）：對任何原問題可行解 $x$ 和對偶問題可行解 $y$ ，都有 $Z \le W$ 。也就是說對偶問題的可行解總是給出原問題目標值的「上限」或「下限」（視原問題為 max 或 min），而最優解時才會達到等式。

這種對稱關係說明：最大利潤的生產計畫，從資源估價的角度來看，恰好是最小的「資源總價值」。

影子價格的定義與意義#

在對偶問題的最適解中，變數 $y_i^*$ 的值稱為第 $i$ 項資源的影子價格（shadow price）。

對上例進行對偶求解（概念性）：我們預期 $y_1^*, y_2^*$ 分別代表機器時間與人工時間的影子價格。通過單純形法的對偶變數計算，或直接從最優解推斷：由於限制是等式時對應資源恰被用盡（ $2*40+20=100, 40+2*20=80$ ），這兩項資源都是稀缺資源（binding constraints），影子價格應大於 $0$ 。

計算方式：若機器時間多增加 $1$ 小時（限制變為 $100+1=101$ ），在最適解附近能增加多少利潤？從原問題限制聯立的頂點移動可估計。原問題最適點是 $2x1+x2=100, x1+2x2=80$ 的交點。若 $b_1$ 增加 $\Delta$ ，解方程組：

\[ 2x1 + x2 = 100 + \Delta, \qquad x1 + 2x2 = 80 \]

解得：將第二式乘 $2$ : $2x1 + 4x2 = 160$ ，減去第一式： $3x2 = 60 - \Delta \Rightarrow x2 = 20 - \Delta/3, x1 = 80 - 2x2 = 80 - 40 + 2/3\Delta = 40 + 2/3\Delta$ 。

利潤變化： $\Delta Z = 40*(2/3\Delta) + 50*(-\Delta/3) = (80/3 - 50/3)\Delta = (30/3)\Delta = 10\Delta$ 。

因此機器時間的影子價格 $y_1^* = 10$ 元／小時。

同理對人工時間，限制變為 $80 + \Delta$ ： $$ 2x1 + x2 = 100, \qquad x1 + 2x2 = 80 + \Delta $$

解得：第一式 $x2 = 100 - 2x1$ 代入： $x1 + 2(100 - 2x1) = 80 + \Delta \Rightarrow x1 + 200 - 4x1 = 80 + \Delta \Rightarrow -3x1 = -120 + \Delta \Rightarrow x1 = 40 - \Delta/3, x2 = 100 - 2x1 = 100 - 80 + 2/3\Delta = 20 + 2/3\Delta$ 。

利潤變化： $\Delta Z = 40*(-\Delta/3) + 50*(2/3\Delta) = (-40/3 + 100/3)\Delta = (60/3)\Delta = 20\Delta$ 。

人工時間影子價格 $y_2^* = 20$ 元／小時。

驗證強對偶： $W^* = 100*10 + 80*20 = 1000 + 1600 = 2600 = Z^*$ ，完全吻合。

影子價格的管理意涵#

資源價值的內部度量：影子價格告訴管理者「在現有生產組合下，這些資源對利潤貢獻的邊際價值」。若外部可以低於影子價格取得資源（如加班費用低於 $20$ 元／小時），則值得增加；若外部價格高於影子價格，則不應該購買。
鬆弛資源的價值為零：若某項資源有剩餘（限制式為 $<$ 而非等式），則對應的對偶變數 $y_i^* = 0$ 。這很合理：多餘的資源本身並不稀缺，增加它不會提升利潤。
僅適用於「小幅變動」：影子價格是線性規劃在最優點的邊際值，只在限制條件右邊值的敏感度範圍（allowable range） 內才成立。若資源大幅增加，最優生產組合可能會完全改變，影子價格也會隨之改變。這個範圍分析稱為敏感度分析（sensitivity analysis）。
成本會計的啟發：傳統會計以「歷史成本」或「市場價格」計價資源，但線性規劃的影子價格提供了「機會成本」觀點。對於內部稀缺資源，用影子價格來評估生產決策往往比用原始採購價更具經濟意義。
與機會成本的連結：影子價格的本質是機會成本。一小時人工時間用來生產產品 B，就失去用來生產產品 A 的機會，邊際價值是兩者之間的取捨決定的。

影子價格與邊際分析#

在《經濟的數學》中，我們學到廠商在完全競爭下會用「邊際成本 = 價格」決定產量。在資源有限的情況下，線性規劃給出了類似的原則：將每單位資源分配給能帶來最高「單位資源邊際貢獻」的產品，直到資源用盡。對偶變數 $y_i^*$ 則是這個競爭均衡下的「資源價格」，將微觀經濟的邊際分析用線性代數的形式系統化了。

簡單的敏感度概念#

管理者常會問：「如果可以多買 $10$ 小時人工時間，最多願意出多少錢？」根據上例，在敏感度範圍內，答案是 $10 \times 20 = 200$ 元。若對方要價 $150$ 元就值得買，若要價 $250$ 元就不值得。但如果要買 $100$ 小時人工時間，前 $10$ 小時或許還能維持 $20$ 元／小時的價值，但隨著人工時間大幅增加，機器時間可能變成限制因素，影子價格也會變化。

前因後果與驅動關係#

管理問題驅動理論：企業在實際應用線性規劃後，很快發現「求出最優生產組合」還不夠，還要知道「哪些資源最關鍵」、「擴充哪項資源最有效」。這種實務需求促使對偶理論的發展與應用。
理論如何改變實務：影子價格為資源擴充決策提供量化依據，成為資本預算（是否添購機器）、人力規劃（是否加班）、原料談判（最大願付價格）等決策的標準工具。
對後續章節的影響：3.3 節整數規劃雖然演算法複雜，但影子價格的概念仍可用於鬆弛問題的經濟分析。第4章排隊論的服務成本與等待成本最佳化，也涉及「邊際成本與邊際效益」的權衡，與影子價格的思路異曲同工。第8章決策分析中的機會成本概念也與此密切相關。
與兄弟書的連結：《經濟的數學》第2章效用最大化與第4章成本最小化，都是「在預算約束下追求目標」，與線性規劃的「資源約束下目標極值」本質一致。《會計的數學》第6章本量利分析雖是簡單的數量關係，但線性規劃將其擴展到「多產品、多資源」的更一般情況。

前因後果與驅動關係（補充說明）#

對偶理論的歷史值得注意：馮·諾伊曼雖然在 1947 年提出對偶關係，但最初並未公開發表詳細證明。Dantzig 及其同事後來補充完整理論，並將對偶變數成功應用於線性規劃的計算與經濟解釋。這也是作業研究史上「理論與實務雙向互動」的典型例子：Dantzig 的演算法解決問題,馮·諾伊曼的對策理論提供理論背景,兩者共同塑造了現代最佳化的面貌。

練習#

對 3.1 節例題的原問題,寫出對偶問題的數學形式並說明其經濟意義.
根據上例計算結果,若工廠有機會以每小時 $15$ 元購買額外機器時間,是否值得?若以每小時 $25$ 元購買額外人工時間,是否值得?請說明理由.
某資源限制式為 $3x1 + 2x2 <= 50, x1,x2>=0$ ,在最優解時該資源只用了 $40$ 小時,求其影子價格並說明理由.
簡述強對偶定理與弱對偶定理的意義,並說明對管理決策的啟發.
思考題:影子價格是「內部價值」而非市場價格。試舉一個企業實際案例說明,什麼情況下管理者應該用影�價格來決策,而不是用市場採購價?

年表速查#

1947 年夏天:John von Neumann 與 George Dantzig 討論線性規劃時發現原問題與對偶問題的關係.
1948–1951:對偶理論逐漸由 Dantzig、Gale、Kuhn、Tucker 等人系統化證明.
1951：Gale, Kuhn, Tucker 發表《線性規劃與擴展形式》（Linear Programming and the Extension of Games）等論文,奠定現代對偶理論基礎.
1950 年代以來:影子價格廣泛應用於資本預算、資源規劃與區域經濟計畫等領域.
1975：Kantorovich 與 Koopmans 獲諾貝爾經濟學獎,間接肯定線性規劃與資源估價理論的經濟意義.

名詞速查表#

原問題（Primal）：線性規劃的原始形式,通常是生產組合或資源配置問題.
對偶問題（Dual）：與原問題對應的另一個線性規劃問題,從資源估價角度建構.
對偶理論（Duality Theory）：研究原問題與對偶問題關係的理論.
影子價格（shadow price）：對偶問題最適解中對應每個限制條件的變數值,代表該資源的邊際價值.
鬆弛資源（slack resource）：限制條件未用盡的資源.
綁定限制（binding constraint）：限制條件在最優解時恰好等於右邊值的限制,對應資源為稀缺資源.
強對偶定理（Strong Duality Theorem）：原問題最適值等於對偶問題最適值.
弱對偶定理（Weak Duality Theorem）：原問題可行解的目標值 ≤ 對偶問題可行解的目標值（對 max 原問題而言）。
敏感度分析（sensitivity analysis）：研究參數變動對最適解與影子價格影響的分析.