对偶问题转换口诀

投稿:拥之则安 优质问答领域创作者 发布时间:2023-07-06 21:59:52
对偶问题转换口诀

转化如下:
题目不明确,猜中心,求偶对,改语境。
未知数带入,约束条件再列,优化求解法则,对偶解法转换。

对偶问题转换口诀


任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应,反之亦然,如果我们把其中一个叫原问题,则另一个就叫做它的对偶问题,并称这一对互相联系的两个问题为一对对偶问题。



生产计划问题(资源利用问题)

胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个,椅子销售价格30/个,生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时,油漆工2小时。生产一个椅子需要木工3小时,油漆工1小时。该厂每个月可用木工工时为120小时,油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大?

数学模型

max g= 50x1 + 30x2

s.t. 4x1 + 3x2 <=120

2x1 + x2 <=50

x1,x2 =>0

如果我们换一个角度,考虑另外一种经营问题。 假如有一个企业家有一批等待加工的订单,有意利用该家具厂的木工和油漆工资源来加工他的产品。因此,他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何既使家具厂觉得有利可图肯把资源出租给他,又使自己付的租金最少?

假设 y1, y2 分别表示每个木工和油漆工工时的租金,则所付租金最小的目标函数可表示为:

min s = 120 y1 + 50 y2

目标函数中的系数 120,50 分别表示可供出租的木工和油漆工工时数。

该企业家所付的租金不能太低,否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的利益:

4 y1 + 2y2 =>50

3 y1 + y2 =>30

y1, y2 =>0

得到另外一个数学模型

min s = 120 y1 + 50 y2

s.t. 4 y1 + 2y2=> 50

3 y1+ y2 =>30

y1, y2 =>0

这两个模型既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据,区别在于模型反映的实质内容是不同的。模型1是站在家具厂经营者立场追求销售收入最大,模型2是则站在家具厂对手的立场追求所付的租金最少。如果模型1称为原问题,则模型2称为对偶问题。任何线性规划问题都有对偶问题,而且都有相应的意义。


线性规划的对偶关系:

数学模型

(1).Max S = C x

s.t. Ax <= b

x=> 0

(2).Min G= yb

s.t. yA=>C

y=> 0

称作互为对偶问题。其中一个称为原问题,另一个称为它的对偶问题。