4线性规划双重问题（清华4）.ppt

常数项次小出基变量X4，按比值X2为进基变量。主元（-2） 主元运算：第一行乘（-1/2） 主元运算：第二行加第一行（-2） 计算检验数：全小于零。但常数项为负数的行元素全大于零，原问题无可行解。 例2-11：某种农作物在生长过程中至少需要氮肥33公斤，磷肥24公斤钾肥42公斤。已知有甲、乙、丙、丁四种复合肥料的每公斤价格与含氮、磷、钾肥数量如下表。问应如何使用这些肥料，既能满足作物生长的需要，又能使施肥成本最低？ 原始数据表 解： 假设用甲、乙、丙、丁为X1、X2、X3、X4公斤。 数学模型为： min S=4x1+15x2 + 10x3 +13x4 s.t. 0.03x1+0.3x2 +0.15x4 ? 33 0.05x1+ 0.2x3 +0.1x4 ? 24 0.14x1 +0.07x4 ? 24 x1，x2 ， x3， x4 ? 0 也可将模型化为： max S= - 4x1 - 15x2 - 10x3 -13x4 - 0.03x1-0.3x2 -0.15x4 +x5 = -33 - 0.05x1 - 0.2x3 -0.1x4 +x6 = -24 - 0.14x1 -0.07x4 +x7 = -24 x1，x2 ， x3， x4 ，x5，x6 ， x7 ? 0 初始可行基B1=（P5，P6，P7） 第三行乘以1/（-0.14） 第一行加上第三行乘（0.03） 第二行加上第三行乘（0.05） 第一行除（-0.3） 计算检验数 第二行除以（-0.2) 最优解（300，80，45） 最优值S’=-2850 S=2850 最优解：甲肥300公斤，乙肥80公斤，丙肥45公斤，最少费用为2850元。 另外一个最优解：甲肥480公斤，乙肥62公斤，最少费用为2850元。 习题P74 2.3（1）（2） 2.4 2.6 2.7 例2-7：写出下列线性规划问题的对偶问题 min S = 3x1 - 2x2 + x3 s.t. x1+2x2 = 1 y1 2x2 - x3 ? -2 y2 2x1 +x3 ? 3 y3 x1- 2x2 + 3x3 ? 4 y4 x1，x2 ? 0 ， x3 无非负限制 min S = 3x1 - 2x2 + x3 s.t. x1+2x2 = 1 y1 -2x2 + x3 ? 2 y2 2x1 + x3 ? 3 y3 x1- 2x2 + 3x3 ? 4 y4 x1，x2 ? 0 ， x3 无非负限制 解: 综合运用对偶原则得到 max g = y1+2y2 +3y3 +4y4 s.t. y1+ 2y3 + y4 ? 3 2y1 -2y2 - 2y4 ? -2 y2+ y3 +3y4 = 1 y2, y3, y4 ? 0 ，y1 无非负约束 对偶问题的基本定理 定理2.0:(对称性定理) 对偶问题的对偶就是原问题. 对偶问题的基本定理 定理2.1:(弱对偶定理) 对于互为对偶问题(I)(II)中的任意的可行解x(0),y(0),都有 c x(0) = y(0) b 用非线性函数马鞍面说明定理的含义（鞍点）。但是线性规划是线性函数。 马鞍面z=x2/4-y2/6 鞍点 Y Z X Z Y X 在Y=0的平面上鞍点是z=f(0,y)的极大值点 X Y Z 在X=0的平面上鞍点是z=f(0,y)的极小值点 对偶问题的基本定理 推理一:对偶问题中,任意一个可行解,都产生了另一个问题的目标函数的界。 推理二:若原问题与对偶问题都有可行解,则它们都有最优解。 推理三:若互为对偶问题中任意一个有可行解,但无最优解,则另一个就无可行解。 对偶问题的基本定理 定理2.2 (最优准则) 若原问题的某一个可行解与对偶问题的某一可行解的目标函数值相等,则它们分别是原问题与对偶问题的最优解. 对偶问题的基本定理 定理2.3 (对偶定理) 若原问题有最优解,则对偶问题也有最优解,且最优值相等. 对偶问题的基本定理 定理2.3 (对偶定理) 若原问题有最优解,则对偶问题也有最优解,且最优值相等。 推理:对偶问题的最优解为原问题最优