查看“︁對偶線性規劃”︁的源代码

{{Request translation|en}}

一个[[线性规划]]问题（“原问题”）的'''对偶线性规划'''问题（“对偶问题”）是另一个线性规划问题，由原问题以一定方式派生而来：<ref>{{cite book |author1=Gärtner, Bernd |author2=Matoušek, Jiří |title=Understanding and Using Linear Programming |date=2006 |publisher=Springer |location=德国柏林 |isbn=3-540-30697-8 |pages=81-104}}</ref>
* 原问题中的每个变量都变为对偶问题中的一个限制条件；
* 原问题中的每个限制条件都变为对偶问题中的一个变量；
* 原问题若是求目标函数的最大值，则对偶问题是求最小值，反之亦然。

== 对偶问题的构建方法 ==
对于以下形式的两个线性规划问题：
{| class="wikitable"
|-
! 问题甲 !! 问题乙
|-
| 最大化目标函数<br><math>\max_{x}c^Tx = \max_{x}\sum_{i}c_{i}x_{i}</math>
|| 最小化目标函数<br><math>\min_{y}b^Ty = \min_{y}\sum_{i}b_{i}y_{i}</math>
|-
| n个变量<math>x_1 ,\ldots, x_n</math>
* <math>x_i \ge 0</math>
* <math>x_j \le 0</math>
* <math>x_k \in \mathbb{R}</math>
|| n个限制条件<math>A^{T}y \lesseqqgtr c</math>
* 第i个限制条件为<math>\ge c_i</math>
* 第j个限制条件为<math>\le c_j</math>
* 第k个限制条件为<math>= c_k</math>
|-
| m个限制条件<math>Ax \lesseqqgtr b</math>
* 第i个限制条件为<math>\ge b_i</math>
* 第j个限制条件为<math>\le b_j</math>
* 第k个限制条件为<math>= b_k</math>
|| m个变量<math>y_1 ,\ldots, y_m</math>
* <math>y_i \le 0</math>
* <math>y_j \ge 0</math>
* <math>y_k \in \mathbb{R}</math>
|}
我们称甲、乙互为对偶问题，即：甲为乙的对偶问题，乙为甲的对偶问题。由此定义可知，原问题是其对偶问题的对偶问题。

特别地， 若所有限制条件的符号方向相同，我们有以下形式：
{| class="wikitable"
!名称
!问题甲
!问题乙
|-
|'''对称对偶问题'''
|Maximize '''c'''<sup>T</sup>'''x'''  满足 ''A'''''x''' ≤ '''b''', '''x''' ≥ 0
|Minimize  '''b'''<sup>T</sup>'''y'''  满足 ''A''<sup>T</sup>'''y''' ≥ '''c''', '''y''' ≥ 0
|-
|rowspan= 2 |'''非对称对偶问题'''
|Maximize '''c'''<sup>T</sup>'''x''' 满足 ''A'''''x''' ≤ '''b'''
|Minimize  '''b'''<sup>T</sup>'''y''' 满足 ''A''<sup>T</sup>'''y''' = '''c''', '''y''' ≥ 0
|-
|Maximize '''c'''<sup>T</sup>'''x'''  满足 ''A'''''x''' = '''b''', '''x''' ≥ 0
|Minimize  '''b'''<sup>T</sup>'''y'''  满足 ''A''<sup>T</sup>'''y''' ≥ '''c'''
|}

===例子===
以下甲乙互为对偶问题。
{| class="wikitable"
|-
! 问题甲 !! 问题乙
|-
| <math>\begin{align}
\text{maximize } & 3 x_1 + 4 x_2 
\\
\text{s.t. } & 5 x_1 + 6 x_2 = 7
\\
&  x_1\geq 0, x_2\geq 0
\end{align}
</math> 
|| <math>\begin{align}
\text{minimize } & 7 y_1
\\
\text{s.t. } 
 &  5 y_1 \geq 3
\\
 &  6 y_1 \geq 4
\\
 &  y_1\in \mathbb{R}
\end{align}
</math>
|}

== 对偶定理 ==
对于互相对偶的最大化问题甲与最小化问题乙，我们有如下两个定理。
===弱对偶定理===
若<math>x \in \mathbb{R}^n</math>、<math>y \in \mathbb{R}^m</math>分别满足问题甲、乙的限制条件，则：<math>c^{T}x \le b^{T}y</math>。
===强对偶定理===
若<math>x^{*} \in \mathbb{R}^n</math>、<math>y^{*} \in \mathbb{R}^m</math>分别满足问题甲、乙的限制条件，则：<math>x^{*}, y^{*}</math>分别为问题甲、乙的最优解（即<math>x^{*} = \operatorname{argmax}_{x}c^Tx</math>，<math>y^{*} = \operatorname{argmin}_{y}b^Ty</math>），当且仅当<math>c^{T}x^{*} = b^{T}y^{*}</math>。

换言之，若甲、乙均有解，则<math>\max_{x}c^Tx = \min_{y}b^Ty</math>。

===无限值解与无解问题===
由对偶定理，不难得出以下结论：
* 若原问题有无限值解，则其对偶问题无解；
* 若对偶问题有无限值解，则其原问题无解。
但是，原问题和对偶问题可同时无解。

==对偶问题的解读==
===经济学角度===
{{main|影子价格}}
甲公司有擁有一間核酸檢測實驗室，提供普通、VIP兩種核酸檢測服務，每人次普通、VIP檢測分別可獲利潤10元、20元。每人次普通、VIP檢測分別需要占用1單位、8/3單位人力，而該實驗室有每天4千單位人力。由於PCR擴增儀檢測能力限制，該實驗室每天最多檢測2千人次。另由於政府規管，該實驗室每天最多允許1.5千人次VIP檢測。因核酸檢測需求旺盛，不論該實驗室提供多少次核酸檢測服務均有人買單。問題甲：該實驗室每天應該分別提供多少次普通、VIP核酸檢測服務？

現乙公司欲租用該核酸檢測實驗室。問題乙：乙公司應該為每單位人力、每人次核酸檢測能力、每人次VIP檢測許可分別支付多少錢一天？
{| class="wikitable"
|-
! 问题甲 !! 问题乙
|-
| 利潤最大化<br><math>\max_{x}c^Tx = \max_{x}10x_1 + 20x_2</math>
|| 成交價格最小化<br><math>\min_{y}b^Ty = \min_{y}4y_1 + 2y_2 + 1.5 y_3</math>
|-
| 2个变量<math>x_1, x_2</math>
* <math>x_1 \ge 0</math>（普通核酸服務次數）
* <math>x_2 \ge 0</math>（VIP核酸服務次數）
|| 2个限制条件<math>A^{T}y \ge c</math>
* <math>y_1 + y_2 \ge 10</math>（否則甲公司寧可自己做普通核酸服務）
* <math>\frac{8}{3}y_1 + y_2 + y_3 \ge 20</math>（否則甲公司寧可自己做VIP核酸服務）
|-
| 3个限制条件<math>Ax \le b</math>
* <math>x_1 + \frac{8}{3} x_2 \le 4</math>（人手限制）
* <math>x_1 + x_2 \le 2</math>（檢測能力限制）
* <math>x_2 \le 1.5</math>（政府免許限制）
|| 3个变量<math>y_1, y_2, y_3</math>
* <math>y_1 \ge 0</math>（單位人力價格）
* <math>y_2 \ge 0</math>（單位檢測能力價格）
* <math>y_3 \ge 0</math>（單位免許價格）
|}
問題甲、乙均有解。由前述強對偶定理可知，甲公司能獲得的最大利潤即是乙公司能獲得的最低成交價格。最優解為：<math>x_1 = 0.8, x_2 = 1.2</math>

===几何角度===
{{main|最大流最小割定理#线性规划公式}}

== 参考 ==
{{reflist}}

[[Category:應用數學]]
[[Category:運籌學]]