第二节对偶问题的提出一、对偶问题的提出什么是对偶？对同一事物（或问题），从不同的角度（或立场）提出相对的两种不同的表述。例如：在平面
内，矩形的面积与其周长之间的关系，有两种不同的表述方法。周长一定，面积最大的矩形是正方形。面积一定，周长最短的矩形是正方形。这种表
述有利于加深对事物的认识和理解。线性规划问题也有对偶关系。产品III资源限量设备128台时原料A401
6公斤原料B0412公斤利润23资源产品设备原料A原料B每台收益决策变量I1402x1II2043
x2资源限量81612决策变量y1y2y3第二节对偶问题的提出实例1（典型示例）：假设工厂考虑不进行生产而把全部可利用的资源
都让给其他企业，工厂希望给这些资源定出一个合理的价格，即使别的单位愿意购买，又使本工厂能得到生产这些产品所能获得的最大收益。对实例
1从对偶的角度进行表述。假设该工厂的决策者决定不生产产品Ⅰ、Ⅱ，而将其所有资源出租或外售。这时工厂的决策者就要考虑给每种资源如何定
价的问题。设用y1，y2，y3分别表示出租单位设备台时的租金和出让单位原材料A，B的附加额。他在做定价决策时，做如下比较：若用1个
单位设备台时和4个单位原材料A可以生产一件产品Ⅰ，可获利2元，那么生产每件产品Ⅰ的设备台时和原材料出租或出让的所有收入应不低于生产
一件产品Ⅰ的利润，这就有y1+4y2≥2对实例1从对偶的角度进行表述。同理将生产每件产品Ⅱ的设备台时和原材料出租或出让的所有收入
应不低于生产一件产品Ⅱ的利润，这就有2y1+4y3≥3把工厂所有设备台时和资源都出租或出让，其收入为w=8y1+16y2+
12y3从工厂的决策者来看当然w愈大愈好；但受到接受方的制约，从接受者来看他的支付愈少愈好，所以工厂的决策者只能在满足大于等于所有
产品的利润条件下，提出一个尽可能低的出租或出让价格，才能实现其原意，为此需解如下的线性规划问题：minw=8y1+16y2+12
y3y1+4y2≥22y1+4y3≥3yi≥0，i=1,2,3称这个线性规划问题为实例1线性规划问题(这里称为原问题)的对
偶问题。这就是从另一角度提出的线性规划问题。资源产品设备原料A原料B每台收益决策变量I1402x1II2043x2资
源限量81612决策变量y1y2y3材料产品甲乙丙丁每台收益A32112000x1B41324000x2C223430
00x3限额600400300200y1y2y3y4实例2：假设工厂考虑不进行生产而把全部可利用的资源都让给其他企业，工厂希望给这
些资源定出一个合理的价格，即使别的单位愿意购买，又使本工厂能得到生产这些产品所能获得的最大收益。比较上述模型，可以得出两者之间的一
些关系：1.两个问题，一个是极大化，另一个是极小化；2.一个问题的变量数等于另一问题的方程数，反之亦然；3.一个
问题的目标函数系数是另一个问题的约束方程右端常数，反之亦然；4.两个问题的约束方程系数矩阵互为转置。称变量yi为第一个LP的
第i个对偶变量，或第一个LP的第i约束相应的对偶变量对偶问题的提出有其理论依据，可由“单纯形法的矩阵描述”加以解释。二、对称
LP问题1.对称形式的定义必须满足下列条件：（1）变量为非负；（2）约束条件为不等式。对于max，约束为“￡”；对
于min，约束为“3”。第二类对称形式第一类对称形式2.对称LP问题的对偶问题例3：写出下列LP问题的对偶问题对偶变量y1y2y
3原变量x1x2对偶3.对偶问题的对偶推导过程对偶变形对偶变形结论：对偶问题的对偶是原问题。例4：写出下列LP问题的对偶问题对偶
变量y1y2y3原变量解:上述LP问题的对偶问题为：x1x2x34.非对称LP问题的对偶问题例5：写出下列LP问题的对偶问题对
偶关系：一个问题第i个变量决定另一问题第i个约束，反之亦然。对称的对应对称的，非对称的对应非对称的直接写出例5的LP问题的对偶问题
补充作业3-1已知LP问题：1)写出其对偶模型；2)如果用大M法求解原问题，请列出初始单纯形表，并用[]标出主元素。第三节
LP的对偶理论定理1弱对偶定理:极大化原问题目标函数值总是不大于其对偶问题的目标函数值。结论：在双方都是可行解的情况下，极大化
问题的目标函数值总不大于其对偶问题目标函数值。推论1：若LP问题有无界解，则其对偶问题无可行解；若LP问题无可行解，则对偶问题
无可行解或为无界解。推论2：极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的下界。推论3：极小化问题的
任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的上界。例6考虑下面一对LP问题其对偶问题为：定理2最优性准则当
LP问题目标函数值与其对偶问题目标函数值相等时，各自的可行解即为最优解。若X(0),Y(0)分别为PP，DP的可行解,且CTX(0
)＝bTY(0)，则X(0),Y(0)分别为PP，DP的最优解。证明：例7补充作业3-2定理3强对偶定理若PP，DP均有
可行解，则PP，DP均有最优解，且目标函数最优值相等。证明：补充作业3-3推论：用单纯形求解LP问题时，PP的检验数对应DP的
一个解（最优时为基可行解，其余为基解）。当PP为max，则PP的检验数与DP的解之间仅差一个负号；当PP为min，则PP的检验数
与DP的解完全相同。证明：以PP是max为例。PP的变量XBXNXSPP的检验数0CN－CBB－1N－CBB－1DP的解YTS1
－YTS2－YTPP检验数与DP解的对应关系表当PP为max，在用单纯形法求解LP问题PP的最优单纯形表中松弛变量的检验数的相反
数就是其DP的最优解；当PP为min，在用单纯形法求解LP问题PP的最优单纯形表中松弛变量的检验数就是其DP的最优解。例8求下列
问题对偶问题的最优解解：化为标准型cj23000qiCBXBbx1x2x3x4x
50x30x40164010sj0-3/4200cj23000qiXBx1x
2x3x4x5CBbx38121008/20X(0)＝(0,0,8,16,12)T—x4016
40010以[4]为主元素进行旋转运算，x2为换入变量，x5为换出变量x501204[4]00112/4
sj23000Y(0)＝(0,0,0,-2,-3)TX(1)＝(0,3,2,16,0)T以[1]为主元素进行旋转运
算，x1为换入变量，x3为换出变量-1/2021[1]102/116/4Y(1)＝(0,0,3/4,-2,0)T
x2—3130001/4cj23000qiCBXBbx1x2x3x4x5-1/
2021100x43x2130001/4sj01/40-20cj23000q
iCBXBbx1x2x3x4x52x104101/40040-21/213x2120-1
/801/2sj000-3/2-1/8X(2)＝(2,3,0,8,0)Tx1—2以[2]为主元素进行旋转
运算，x5为换入变量，x4为换出变量8/2080-412[2]12Y(2)＝(2,0,-1/4,0,0)TX(3)＝
(4,2,0,0,4)T此时达到最优解。X=(4,2),maxZ=14。Y(3)＝(3/2,1/8,0,0,0)Tx50
重要提示：由上述实例可以看出：在用单纯形法求解LP问题时，PP没有得到最优解之前，每迭代一步得到一个基可行解，此时DP得到的是
一个基解；而当PP得到最优解时，DP才得到一个基可行解。根据强对偶定理，DP得到的这个基可行解一定是DP的最优解。设X(0),Y(
0)分别为PP,DP的可行解，则X(0),Y(0)分别为PP,DP的最优解的充要条件为,有定理4互补松弛定理在最优情况下，P
P的第i个决策变量与其DP的第i个约束中的松弛变量的乘积恒为零。反之亦然。(1)(2)(3)(4)例9考虑下面问题解:则，cj-15-33000CBXBbx1x2x3x4x50x4300-213-15x14/310-1/302/3-33x210100-1sj00-50-23补充作业3-4已知LP原问题为：已知原问题用两阶段法求得最优单纯形表如下，试用对偶理论写出其对偶问题的最优解。好 |
|
