線性規(guī)劃技巧: 如何寫對(duì)偶問題

給定線性規(guī)劃的原始問題, 本文介紹寫如何方便地寫出其對(duì)偶問題.

基本公式

我們先給出互為對(duì)偶問題的兩種基本形式, 作為后續(xù)寫對(duì)偶問題的基礎(chǔ).

1. 原問題的約束是不等式

2. 原問題的約束是等式

總結(jié)

原問題的一個(gè)約束對(duì)應(yīng)一個(gè)對(duì)偶變量.
對(duì)偶變量乘以原問題約束的右端( $b$ )得到對(duì)偶問題的目標(biāo).
原問題目標(biāo)的系數(shù) $c$ 對(duì)應(yīng)對(duì)偶問題約束的右端.
最小化對(duì)應(yīng)最大化(反之亦然).
如果原問題有等式約束, 對(duì)偶變量沒有非負(fù)要求.

方法

1. 定義對(duì)偶變量

對(duì)原問題的每一個(gè)約束, 定義一個(gè)對(duì)偶變量 $y_i$ . 如果一個(gè)約束是等式, 其對(duì)偶變量無非負(fù)限制.

2. 對(duì)偶變量乘約束

把對(duì)偶變量乘以原問題的約束. 約束右端 $b^Ty$ 即為對(duì)偶問題的目標(biāo).

3. 計(jì)算 $x$ 的系數(shù)

上一步把對(duì)偶變量乘以原問題的約束之后, 接著計(jì)算原問題約束中決策變量 $x$ 的系數(shù) $f(y) = A^Ty$ , 從而得到對(duì)偶問題的約束 $f(y) \leq c$ (假設(shè)原問題是最小化問題).

例子

1. 矩陣形式

原問題
$\begin{aligned} \min ~ & c^Tx \\ \text{s.t. } & Ax \geq b & \rightarrow \quad \alpha \\ & Bx = d & \quad \rightarrow \quad \beta \\ & x \geq 0 \end{aligned}$

定義對(duì)偶變量 $\alpha$ , $\beta$ , 分別對(duì)應(yīng)原問題的約束 $Ax\geq b$ 和 $Bx=d$ .

用 $b^T, d^T$ 乘以 $\alpha$ , $\beta$ 然后求和得到對(duì)偶目標(biāo): $b^T\alpha + d^T\beta$
用 $A^T, B^T$ 乘以 $\alpha, \beta$ 然后求和得到約束: $A^T \alpha + B^T\beta \leq c$
$\beta$ 對(duì)應(yīng)等式約束, 因此不要求非負(fù)

對(duì)偶問題
$\begin{aligned} \min~& b^T \alpha + d^T \beta \\ \text{s.t. } & A^T \alpha + B^T \beta \leq c \\ & \alpha \geq 0 \end{aligned}$

2. 非矩陣形式

原問題

$\begin{aligned} \min ~ & \sum_{i=1}^n \sum_{j=1}^n l_{i,j} x_{i,j} \\ \text{s.t. } & \sum_{j=1}^n x_{i,j} - \sum_{j=1}^n x_{j,i} = 0, \quad \forall i\neq 1, n \quad & \rightarrow \quad y_i \\ & \sum_{j=1}^n x_{1,j} - \sum_{j=1}^n x_{j,1} = 1 & \rightarrow \quad y_1 \\ & \sum_{j=1}^n x_{n,j} - \sum_{j=1}^n x_{j,n} = -1 & \rightarrow \quad y_n \\ & x_{i,j} \geq 0, \quad \forall i, j \end{aligned}$

如上面所示, 我們定義對(duì)偶變量 $y_i$ , $i=1, 2, ..., n$ . 原問題的約束是等式約束, 因此不要求 $y_i$ 非負(fù). 用 $y_i$ 乘以每個(gè)等式, 得到對(duì)偶問題的目標(biāo): $(1, 0, ..., 0, -1) \cdot y = y_1 - y_n$ . 下面計(jì)算對(duì)偶問題的約束:

給定 $i,j$ , 計(jì)算原問題約束中 $x_{i,j}$ 的 系數(shù)之和, 記作 $f_{ij}(y)$ .
得到對(duì)偶問題的約束: $f_{ij}(y) \leq l_{ij}$

為了方便描述, 我們使用新的下標(biāo) $s, t$ , 并計(jì)算 $x_{s, t}$ 的系數(shù). 詳細(xì)的計(jì)算過程如下:

第一組約束:
$(a): \sum_{j=1}^n y_i \cdot x_{i,j} - \sum_{j=1}^n y_ i \cdot x_{j,i} = 0$ . 注意 $i=2, 3, ..., n-1$ .

當(dāng) $i=s$ 時(shí), $x_{s, j}$ 的系數(shù)是 $y_s$ , $\forall j$
當(dāng) $i=t$ 時(shí), $x_{j, t}$ 的系數(shù)是 $-y_t$ , $\forall j$
$x_{s,t}$ 的系數(shù)之和是 $y_s-y_t$ . 注意: $s, t \neq 1, n$ .
得到對(duì)偶問題的約束: $x_{s, t} \leq l_{s,t}$ , $\forall s, t \neq 1, n$

第二組和第三組約束:
$(b): \sum_{j=1}^n y_1 \cdot x_{1,j} - \sum_{j=1}^n y_1 \cdot x_{j,1} = y_1$
$(c): \sum_{j=1}^n y_n \cdot x_{n,j} - \sum_{j=1}^n y_n \cdot x_{j,n} = -y_n$

當(dāng) $s=1, t=n$ 時(shí), $x_{1, n}$ 的系數(shù)之和為 $y_1-y_n$ (參考 $(b), (c)$ )
當(dāng) $s=1, t=1$ 時(shí), $x_{1,1}$ 的系數(shù)之和為 $y_1-y_1=0$ (參考 $(b)$ )
當(dāng) $s=1$ , $t=2, ..., n-1$ 時(shí), $x_{1,t}$ 的系數(shù)之和為 $y_1 - y_t$ (參考 $(b), (a)$ )
當(dāng) $s=n, t=1$ 時(shí), $x_{n, 1}$ 的系數(shù)之和為 $y_n - y_1$ (參考 $(b), (c)$ )
當(dāng) $s=n, t=n$ 時(shí), $x_{n, n}$ 的系數(shù)之和為 $y_n - y_n$ (參考 $(c)$ )
當(dāng) $s=n, t=2, ..., n-1$ 時(shí), $x_{n, t}$ 的系數(shù)之和為 $y_n - y_t$ (參考 $(c), (a)$ )

綜合上面所有對(duì)偶問題的約束, 我們得到:
$y_s - y_t \leq l_{s,t}, \quad \forall s, t = 1,2, ..., n.$

對(duì)偶問題
$\begin{aligned} \max ~ & y_1 - y_n \\ \text{s.t. } & y_i - y_j \leq l_{ i, j}, \quad \forall i, j = 1, 2, ... ,n. \end{aligned}$

練習(xí)

Ex1

原問題

$\begin{aligned} \min ~ & \sum_{i=1}^m \sum_{j=1}^n c_{i,j} x_{i,j} + \sum_{i=1}^m f_i y_i \\ \text{ s.t. } & \sum_{i=1}^m x_{i, j} = 1,\quad \forall j & \rightarrow \quad \alpha_j \\ & x_{i, j} \leq y_i, \quad \forall i, j & \rightarrow \quad \beta_{ i, j} \\ & x_{i, j} \geq 0, y_i \geq 0, \quad \forall i, j \end{aligned}$

對(duì)偶問題

$\begin{aligned} \max ~ & \sum_{j=1}^n \alpha_j \\ \text{ s.t. } & \alpha_j - \beta_{i,j} \leq c_{i,j}, \quad \forall i,j \\ & \beta_{i, j} \leq f_i, \quad \forall i, j \\ & \beta_{i, j} \geq 0, \quad \forall i, j \end{aligned}$

Ex2

原問題
$\begin{aligned} \max ~ & \sum_{e \in E} w_e x_e \\ \text{ s.t. } & \sum_{e\ni v} x_e = 1, \quad \forall v\in V \quad \rightarrow y_v \\ & x_e \geq 0 \end{aligned}$

對(duì)偶問題

$\begin{aligned} \min ~ & \sum_{ v \in V } y_v \\ \text{ s.t. } & y_u + y_v \geq w_e, \quad \forall e \in E, ~ e=(u,v) \end{aligned}$

最后編輯于：2020.03.01 09:23:58

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市蜈漓，隨后出現(xiàn)的幾起案子包个，更是在濱河造成了極大的恐慌摊趾，老刑警劉巖，帶你破解...
沈念sama閱讀 222,729評(píng)論 6贊 517
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件偶房，死亡現(xiàn)場離奇詭異刃麸，居然都是意外死亡沦辙，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 95,226評(píng)論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門茎芋，熙熙樓的掌柜王于貴愁眉苦臉地迎上來颅眶，“玉大人，你說我怎么就攤上這事田弥√涡铮” “怎么了？”我有些...
開封第一講書人閱讀 169,461評(píng)論 0贊 362
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長商叹。經(jīng)常有香客問我燕刻，道長，這世上最難降的妖魔是什么剖笙？我笑而不...
開封第一講書人閱讀 60,135評(píng)論 1贊 300
?港島之戀（遺憾婚禮）
正文為了忘掉前任卵洗，我火速辦了婚禮，結(jié)果婚禮上弥咪，老公的妹妹穿的比我還像新娘过蹂。我一直安慰自己，他們只是感情好聚至，可當(dāng)我...
茶點(diǎn)故事閱讀 69,130評(píng)論 6贊 398
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布酷勺。她就那樣靜靜地躺著，像睡著了一般扳躬。火紅的嫁衣襯著肌膚如雪脆诉。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 52,736評(píng)論 1贊 312
城市分裂傳說
那天贷币，我揣著相機(jī)與錄音库说，去河邊找鬼。笑死片择，一個(gè)胖子當(dāng)著我的面吹牛潜的，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播字管，決...
沈念sama閱讀 41,179評(píng)論 3贊 422
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼啰挪，長吁一口氣：“原來是場噩夢(mèng)啊……” “哼！你這毒婦竟也來了嘲叔？” 一聲冷哼從身側(cè)響起亡呵，我...
開封第一講書人閱讀 40,124評(píng)論 0贊 277
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎硫戈，沒想到半個(gè)月后锰什，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 46,657評(píng)論 1贊 320
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡丁逝，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,723評(píng)論 3贊 342
?白月光啟示錄
正文我和宋清朗相戀三年汁胆，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片霜幼。...
茶點(diǎn)故事閱讀 40,872評(píng)論 1贊 353
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡嫩码，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出罪既，到底是詐尸還是另有隱情铸题，我是刑警寧澤铡恕，帶...
沈念sama閱讀 36,533評(píng)論 5贊 351
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站丢间，受9級(jí)特大地震影響探熔，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜烘挫，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 42,213評(píng)論 3贊 336
男人毒藥：我在死后第九天來索命
文/蒙蒙一祭刚、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧墙牌，春花似錦涡驮、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,700評(píng)論 0贊 25
一樁弒父案捉捅，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至虽风，卻和暖如春棒口，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背辜膝。一陣腳步聲響...
開封第一講書人閱讀 33,819評(píng)論 1贊 274
情欲美人皮
我被黑心中介騙來泰國打工无牵，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人厂抖。一個(gè)月前我還...
沈念sama閱讀 49,304評(píng)論 3贊 379
代替公主和親
正文我出身青樓茎毁，卻偏偏與公主長得像，于是被迫代替她去往敵國和親忱辅。傳聞我的和親對(duì)象是個(gè)殘疾皇子七蜘，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,876評(píng)論 2贊 361