理论教育 运筹学中对偶问题的提出

运筹学中对偶问题的提出

时间:2023-11-26 理论教育 版权反馈
【摘要】:我们把上面的线性规划问题称为原问题,式(3.1)就是原问题的线性规划模型。现在对例3.1构建对偶问题的数学模型:设y1、y2分别表示原材料A、B的单位出售价格,y3表示设备的单位台时租金。表3.3可以看出,对偶问题的最优目标函数值和原问题的最优目标函数值是相等的。线性规划模型(3.1)和(3.2)是针对同一个具体问题,从两个不同的角度提出来的,同时前面提到,原问题和对偶问题之间存在许多内在的联系。

运筹学中对偶问题的提出

为了对对偶问题有一个清晰的认识,下面通过一个例题进行详细的说明和解释,同时也为掌握对偶理论以及对偶单纯形法奠定基础。

例3.1 某企业计划生产Ⅰ、Ⅱ两种产品,生产单位产品对原材料A和B的消耗、所需要的设备台时以及资源量如表3.1所示。该工厂每生产一件产品Ⅰ可获利3元,每生产一件产品Ⅱ可获利5元,那么如何组织生产才能使Ⅰ、Ⅱ两种产品获得的总利润最大?

表3.1

设x1、x2分别表示Ⅰ、Ⅱ两种产品的产量,线性规划模型如下:

用单纯形法求解,最优单纯形表如表3.2所示:

表3.2

通过最优单纯形表可以知道,最优解为(x1,x2,x3,x4,x5)=(2,6,2,0,0),即Ⅰ、Ⅱ两种产品分别生产2和6,获得的总利润最大为z=3×2+5×6=36(元)。

我们把上面的线性规划问题称为原问题,式(3.1)就是原问题的线性规划模型。

现在从另一角度来讨论问题,假设有一家公司打算购买该企业的原材料A、B,并租赁该企业的设备。如果该企业决策者考虑不生产产品Ⅰ、Ⅱ,而将其所有资源出售和出租给对方,就需要考虑给每种资源定价的问题。从企业的角度看,当然希望对方给出的价位越高越好,如果从对方公司的角度来看,希望支付的越少越好。这就需要该企业决策者做到“知己知彼”,即该企业决策者就要对原材料A、B的售价以及设备的租金制定合理的定价,从而使该企业的收益不少于组织生产产品的收益,同时也能达到对方公司的接受意愿。

我们把上面描述的问题称为原问题的对偶问题。

现在对例3.1构建对偶问题的数学模型

设y1、y2分别表示原材料A、B的单位出售价格,y3表示设备的单位台时租金。由原问题可知,用1千克原材料A和3个设备台时才能生产出一件产品Ⅰ,而一件产品Ⅰ可以获利3元,如果把1千克原材料A和3个设备台时出售和出租,那么获得的收入就不能低于一件产品Ⅰ售卖的利润3元,这样就必须有方程

同理,针对产品Ⅱ有方程

把企业资源和设备台时都出售和出租,总收入w=4y1+12y2+18y3,因为总收入w不能低于组织生产产品的收益,所以有

(www.daowen.com)

至此,构造出的对偶问题的线性规划模型如下:

对该模型求解的最优单纯形表如表3.3所示。

由最优单纯形表3.3可知,最优解为(y1,y2,y3,y4,y5)=(0,3/2,1,0,0),即原材料 A、B 的出售价格分别为0、3/2,设备租金为1,获得的总收入w=4×0+12×3/2+18×1=36(元)。

表3.3

可以看出,对偶问题的最优目标函数值和原问题的最优目标函数值是相等的。根据两个问题所追求的目标,直观上可以理解这一点。无论是原问题还是对偶问题,无非都是企业如何利用这些有限资源,以获得尽可能多的收益。也就是说,企业获取利益的方式有两种,既可以利用有限的资源组织产品生产,通过产品的销售获得收益,又可以将有限的资源售卖和出租,从而获得收益。线性规划模型(3.1)和(3.2)是针对同一个具体问题,从两个不同的角度提出来的,同时前面提到,原问题和对偶问题之间存在许多内在的联系。现在把线性规划模型(3.1)和(3.2)中有关“数据的位置”写在表格3.4中,以了解原问题和对偶问题两个模型之间存在的联系。

仔细观察表3.4,就会发现一些具有内在联系的现象:

表3.4

(1)原问题决策变量xj表示产品的生产数量,而对偶问题决策变量yj表示售价和租金,所以原问题的决策变量与对偶问题的决策变量表示的意义不同。

(2)原问题的目标函数是求最大值,而对偶问题的目标函数是求最小值。

(3)原问题的约束条件方程是“≤”型,而对偶问题的约束条件方程是“≥”型。

(4)对偶问题约束条件方程右端的常数是原问题目标函数的系数,而对偶问题目标函数的系数是原问题约束条件方程右端的常数。

(5)对偶问题变量的个数等于原问题约束条件方程的个数,而对偶问题约束条件方程的个数等于原问题变量的个数。

(6)对偶问题约束条件方程组的系数矩阵与原问题约束条件方程组的系数矩阵互为转置矩阵。

上述总结出的现象,对构建对偶问题的模型就有了一个启示,即不必对对偶问题进行重新分析和建模,可以直接由原问题模型写出对偶问题的模型,这就为学习下一节建立对偶问题模型的规则奠定了基础。

特别提示

对偶问题最优解不能作为获取总利益的决策依据,而最优目标函数值才是决策的根本。针对上例,假如对方公司给出如下方案:以20元购买单位原材料A、原材料B无偿获得、设备免费使用,即(y1,y2,y3,y4,y5)=(20,0,0,0,0),那么这个方案是否接受就不能用最优解来衡量,因为此方案总收入w=4×20+12×0+18×0=80,明显高于生产产品Ⅰ、Ⅱ的总利润36。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈