线性规划4课件.ppt

最优解：甲肥300公斤，乙肥80公斤，丙肥45公斤，最少费用为2850元。 另外一个最优解：甲肥480公斤，乙肥62公斤，最少费用为2850元。 用出基变量x5行的所有负数分别去除对应的检验数，最小值对应的为进基变量x1，交叉元素为主元（-1） 主元运算：第一行乘（-1） 主元运算：第二行加上第一行（-2） 计算检验数 确定出基变量X6 确定进基变量X3，主元（-2） 主元运算：第二行乘（-1/2） 主元运算：第一行加第二行 计算检验数：全为非正。但此时常数b已全大于零，最优解=（7，0，4，0） 最优值 S’ = - 7 S=7 应当注意： （1）用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解； （2）初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则； （3）对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量； * （5）对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样． （4）普通单纯形法的最小比值是 其目的是保 证下一个原问题的基本解可行，对偶单纯形法的最小比值是 其目的是保证下一个对偶问题的基本解可行； 【例】用对偶单纯形法求解 【解】取x3、x4为初始基变量，用对偶单纯形法迭代如表所示。 XB x1 x2 x 3 x 4 b 表 （1） x 3 x 4 2 －1 [－1] 2 1 0 0 1 －2→ －2 λj －7 －3↑ 0 0 ? 表 （2） x 2 x 4 －2 3 1 0 －1 2 0 1 2 －6 λj －13 0 －3 0 ? 第二张表中x 4=－60且第二行的系数全部大于等于零，说明 原问题无可行解。 上例可用性质2.6及性质2.2来说明，表（2）的第2行对应于对偶问题的第2列（相差一个负号），检验数行对应于对偶问题的常数项（相差一个负号），比值 对应于对偶问题的比 值 失效，也说明 即对偶问题具有无界解，由性质2.2知原问题无可行解． 表2的对偶问题可以写成： 失效 例2-10：用对偶单纯形法解下列线性规划问题 min S = x1 + 2x2 s.t. -x1+2x2 - x3 ? 1 -x1 -2x2 + x3 ? 6 x1，x2 ， x3 ? 0 解：将原问题化成 max S’ = -x1 - 2x2 s.t. x1 - 2x2 + x3 + x4 =-1 x1 + 2x2 - x3 + x5=-6 x1，x2 ， x3 ， x4， x5 ? 0 常数项最小出基变量X5，最小比值x3入基 计算检验数：全小于零。但常数项为负数的行元素全大于零，原问题无可行解。 例3：某种农作物在生长过程中至少需要氮肥33公斤，磷肥24公斤钾肥42公斤。已知有甲、乙、丙、丁四种复合肥料的每公斤价格和含氮、磷、钾肥数量如下表。问应如何使用这些肥料，既能满足作物生长的需要，又能使施肥成本最低？ 原始数据表 解： 假设用甲、乙、丙、丁为X1、X2、X3、X4公斤。 数学模型为：min S=4x1+15x2+10x3+13x4 s.t. 0.03x1+0.3x2 +0.15x4 ? 33 0.05x + 0.2x3 +0.1x4 ? 24 0.14x1 +0.07x4 ? 24 x1，x2 ， x3， x4 ? 0 也可将模型化为： maxS=-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