土 木 工 程 与 建 筑 学 院 教 师 备 课 纸

目标函数 最大利润为maxZ?2x1?x2，某公司最小出让价为：其中： x1和x2为两种产品的产量。 minW?15y1?24y2?5y3，其中： y1,y2,y3分别为单位时间内设备A，B和调试工序的出让价格。 原问题 对偶问题 每生产1件商品的出让价不小6y2?y3?2约束条件 每生产1件商品在A，B设备和调试工序上的时间约束5x2?15为：x?x?512于利润：5y1?2y2?y3?1 y1,,y2,y3?06x1?2x2?24x1,x2?0 可见：

原问题（系数为m×n矩阵） maxZ 对偶问题（系数为n×m矩阵） minW 目标函数中的系数成为对偶问题约束 约束条件中的右端常数成为原问题中 条件中的右端常数 目标函数中的系数 约束条件系数矩阵为对偶问题约束条 约束条件系数矩阵为原问题约束条 件系数矩阵的转置。 约束条件数有m个， 第i个约束条件为“≤”， 第i个约束条件为“≥” 第i个约束条件为“=” 件系数矩阵的转置。 变量数m个， 第i个变量为“≥0” 第i个变量为“≤0” 第i个变量为自由变量 第29页

------------------------------------------------------------------------------------------------------------------------------------------------------

土 木 工 程 与 建 筑 学 院 教 师 备 课 纸

变量数n个， 第i个变量为“≥0” 第i个变量为“≤0” 第i个变量为自由变量

例1-6和例1-8分别用单纯形法和两阶段法可求得上述例题的原问题和其对偶问题的最终单纯形表如下： 目标函数 决策变量 基变量 最 终 表 ?j x3 x1 约束条件数有n个， 第i个约束条件为“≥”， 第i个约束条件为“≤” 第i个约束条件为“=” Cj 2 1 0 0 0 原问题变量 原问题松弛变量 x3 x4 x5 常数 0 2 1 x1 x2 0 0 1 0 0 1 0 0 对偶问题剩余变量 y3 y4 1 5/4 -15/2 15/2 0 1/4 -1/2 0 -1/4 3/2 0 -1/4 -1/2 对偶问题变量 y1 y2 y3 x2 7/2 3/2 变量 目标函数 决策变量 基变量 一次 迭代 y2 y3 Cj -15 -24 -5 0 0 常数 y y1 y2 y3↓ y4 y5 -24 -5/4 1 0 -1/4 1/4 1/4 -5 15/2 0 1 1/2 -3/2 1/2 第30页

------------------------------------------------------------------------------------------------------------------------------------------------------

土 木 工 程 与 建 筑 学 院 教 师 备 课 纸

?j -15/2 0 0 -7/2 -3/2

从上两表看出两个问题变量之间的对应关系，同时看出只需求解其中一个问题，从最优解的单纯形表中同时得到另一个问题的最优解。即原问题的最优解为：X?(7/2,3/2,0,0,0)T；其对偶问题的最优解为：

Y?(0,1/4,1/2,0,0)T。

对偶问题的基本性质

1、 若线性规划原问题（LP）有最优解，其对偶问题（DP）也有最优解； 2、 LP的检验数的相反数对应于其DP的一组基本解，其中第j个决策变

量xj的检验数的相反数对应于DP第i个剩余变量xsj的解；LP第i个松弛变量xsi的检验数的相反数对应于其DP的第i个对偶变量yi的解。反之DP的检验数对应于其LP的一组基本解。 例1-9

maxZ?6x1?2x2?x32x1?x2?2x3?2x1?4x3?3x1?3?0

解 加入松弛变量x4,x5后，单纯形表迭代为：

x1 x2 x3 x4 x5 b x4 [2] -1 2 1 0 2 x5 1 0 4 0 1 4 ?j 6 -2 1 0 0 第31页 ------------------------------------------------------------------------------------------------------------------------------------------------------

土 木 工 程 与 建 筑 学 院 教 师 备 课 纸

x1 1 -1/2 1 1/2 0 1 x5 0 [1/2] 3 -1/2 1 3 ?j 0 1 -5 -3 0 x1 1 0 4 0 1 4 x2 0 1 6 -1 2 6 ?j 0 0 -11 -2 -2 y3 y4 y5 y1 y2 设对偶变量为y1和y2，剩余变量为y3，y4，y5，由上性质，有

Y?(y1,y2,y3,y4,y5)?(??4,??5,??1,??2,??3)?(2,2,0,0,11) 为对偶问题的基本解。

二、课堂练习（穿插在例题讲解过程中） 三、课堂小结（5分钟）

第32页

------------------------------------------------------------------------------------------------------------------------------------------------------