原问题与对偶问题模型的对应关系分析

通过对常规和非常规对偶模型的推导,可得出原问题与对偶问题模型的对应关系,如表2-1所示。根据表2-1中的对应关系,不仅可以快速写出一般线性规划问题模型的对偶形式,而且可以求出特殊线性规划问题(如运输问题)模型的对偶形式。

表2-1

【例2-5】将下面线性规划模型转化为对偶形式。

解:

因原问题存在3个约束条件,可设对偶问题变量为y1,y2,y3,转化过程如下:原问题目标函数求最大值“max Z”,对偶问题目标函数求最小值“min W”,原问题资源向量为bP＝(2,1,2)T,对偶问题价值向量为CD＝(2,1,2)。

原问题系数矩阵A为:

对偶问题系数矩阵A T为:

原问题价值向量为CP＝(1,1,1),对偶资源向量为bD＝(1,1,1)T。

原问题第一个变量“x1≥0”,对偶问题第一个约束条件不等式符号为“≥”。

原问题第二、三个变量“取值无约束”,对偶问题第二、三个约束条件不等式符号为“＝”。

原问题第一个约束条件不等式符号为“≤”,对偶问题第一个变量“y1≥0”。

原问题第二个约束条件不等式符号为“＝”,对偶问题第二个变量“y2取值无约束”。

原问题第三个约束条件不等式符号为“≥”,对偶问题第三个变量“y3≤0”。

综上,对偶问题的数学模型为:(www.xing528.com)

【例2-6】将下面线性规划模型转化为对偶形式。

解:

因原问题存在3个约束条件,可设对偶问题变量为y1,y2,y3,转化过程如下:原问题目标函数求最小值“min Z”,对偶问题目标函数求最大值“max W”。

原问题资源向量为bP＝(18,10,－14)T,对偶问题价值向量为CD＝(18,10,－14)。

原问题系数矩阵A和对偶问题系数矩阵A T分别为:

原问题价值向量为CP＝(1,5,－4,9),对偶资源向量为bD＝(1,5,－4,9)T。

原问题第一个变量“取值无约束”,对偶问题第一个约束条件不等式符号为“＝”。

原问题第二个变量“x2≤0”,对偶问题第二个约束条件不等式符号为“≥”。

注意目标函数求最小值与目标函数求最大值的区别。

原问题第三、四个变量“x3≥0,x4≥0”,对偶问题第三、四个约束条件不等式符号为“≤”。

原问题第一个约束条件不等式符号为“≤”,对偶问题第一个变量“y1≤0”。

原问题第二个约束条件不等式符号为“≥”,对偶问题第二个变量“y2≥0”。

原问题第三个约束条件不等式符号为“＝”,对偶问题第一个变量“y3取值无约束”。

综上,对偶问题的数学模型为: