热门问题
时间线
聊天
视角

对偶线性规划

来自维基百科,自由的百科全书

Remove ads

一个线性规划问题(“原问题”)的对偶线性规划问题(“对偶问题”)是另一个线性规划问题,由原问题以一定方式派生而来:[1]

  • 原问题中的每个变量都变为对偶问题中的一个限制条件;
  • 原问题中的每个限制条件都变为对偶问题中的一个变量;
  • 原问题若是求目标函数的最大值,则对偶问题是求最小值,反之亦然。

对偶问题的构建方法

对于以下形式的两个线性规划问题:

更多信息 ...

我们称甲、乙互为对偶问题,即:甲为乙的对偶问题,乙为甲的对偶问题。由此定义可知,原问题是其对偶问题的对偶问题。

特别地, 若所有限制条件的符号方向相同,我们有以下形式:

更多信息 名称, 问题甲 ...
Remove ads

例子

以下甲乙互为对偶问题。

更多信息 , ...
Remove ads

对偶定理

对于互相对偶的最大化问题甲与最小化问题乙,我们有如下两个定理。

弱对偶定理

分别满足问题甲、乙的限制条件,则:

Remove ads

强对偶定理

分别满足问题甲、乙的限制条件,则:分别为问题甲、乙的最优解(即),当且仅当

换言之,若甲、乙均有解,则

Remove ads

无限值解与无解问题

由对偶定理,不难得出以下结论:

  • 若原问题有无限值解,则其对偶问题无解;
  • 若对偶问题有无限值解,则其原问题无解。

但是,原问题和对偶问题可同时无解。

对偶问题的解读

经济学角度

甲公司有拥有一间核酸检测实验室,提供普通、VIP两种核酸检测服务,每人次普通、VIP检测分别可获利润10元、20元。每人次普通、VIP检测分别需要占用1单位、8/3单位人力,而该实验室有每天4千单位人力。由于PCR扩增仪检测能力限制,该实验室每天最多检测2千人次。另由于政府规管,该实验室每天最多允许1.5千人次VIP检测。因核酸检测需求旺盛,不论该实验室提供多少次核酸检测服务均有人买单。问题甲:该实验室每天应该分别提供多少次普通、VIP核酸检测服务?

现乙公司欲租用该核酸检测实验室。问题乙:乙公司应该为每单位人力、每人次核酸检测能力、每人次VIP检测许可分别支付多少钱一天?

更多信息 ...

问题甲、乙均有解。由前述强对偶定理可知,甲公司能获得的最大利润即是乙公司能获得的最低成交价格。最优解为:

Remove ads

几何角度

参考

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads