线性规划 Linear Programming(LP) 线性规划的对偶理论 对偶问题的基本性质 对称性——原始问题与对偶问题是两个互为对偶的问题。 2.弱对偶性—两个问题的可行解对应的目标函数值互为上下界。 3.最优性——两个问题最优解的目标函数值必相等。 4.强对偶性——两个问题都有可行解时则两个问题必都有最优解。 5.互补松弛性——两个问题最优解中,一个问题中某个变量取值非零, 则该变量在对偶问题中对应的某个约束条件必为紧约束;反之,如 果约束条件为松约束,则其对应的对偶变量一定取值为零。因此, 该定理又称为松紧定理。11 线性规划 Linear Programming（LP） 线性规划的对偶理论 ▪ 对偶问题的基本性质 1. 对称性——原始问题与对偶问题是两个互为对偶的问题。 2. 弱对偶性——两个问题的可行解对应的目标函数值互为上下界。 3. 最优性——两个问题最优解的目标函数值必相等。 4. 强对偶性——两个问题都有可行解时则两个问题必都有最优解。 5. 互补松弛性——两个问题最优解中，一个问题中某个变量取值非零， 则该变量在对偶问题中对应的某个约束条件必为紧约束；反之，如 果约束条件为松约束，则其对应的对偶变量一定取值为零。因此， 该定理又称为松紧定理