a第一章_线性规划.pptVIP

人工变量法―― 求线性规划初始可行基 人工变量必须为0，才能保证原来等式成立。即:Ax=b，原问题有解 若从检验数判断最优解得到，但人工变量不全为零 则无解 ? 1 大M法 例8 P32 1?? min Z=-3 X1+X2+X3 X1 -2X2+ X3 =11 -4X1+X2+ 2X3 =3 -2X1 + X3 =1 X1,X2,X3=0 ? 要点： 引入松弛变量X4 ，利润为零，引入剩余变量X5，利润为零，引入人工变量X6 X7 利润为负无穷大（或者成本为无穷大）???? ? 第一章：线性规划（3） Min Z= -3X1+X2+X3+0X4+0X5 + MX6 +MX7 X1 -2X2+ X3 + X4 =11 -4X1+X2+ 2X3 -X5+ X6 =3 -2X1 + X3 + X7 =1 X1,X2,X3=0 Xi=0,i =1,2,…,7 复习： AX=b B XB + N XN = b XB = B-1b - B-1 N XN Z= CX = CB XB + CN XN = CB (B-1b - B-1 N XN) + CN XN = CB B-1b +( CN - CB B-1 N) XN ＋0 XB Ci -3 1 1 0 0 M M CB XB X1 X2 X3 X4 X5 X6 X7 B-1b Θi 0 X4 1 -2 1 1 0 0 0 11 11 M X6 -4 1 2 0 -1 1 0 3 3/2 M X7 -2 0 1 0 0 0 1 1 1 初始表检验数 -3 +6M 1-M 1-3M 0 M 0 0 -4M 目标值 CB B-1 b = （0，M，M） (11，3，1）T = 4M 第一章：线性规划（3） Ci -3 1 1 0 0 M M CB XB X1 X2 X3 X4 X5 X6 X7 B-1b Θi 0 X4 1 -2 1 1 0 0 0 11 11 M X6 -4 1 2 0 -1 1 0 3 3/2 M X3 -2 0 1 0 0 0 1 1 1 初始表检验数 -3 +6M 1-M 1-3M 0 M 0 0 -4M 非基变量检验数 ( CN - CB B-1 N)=（-3，1，1，0）-（0, M，M） 1，-2，1， 0 -4，1， 2，-1 -2, 0, 1, 0 = （-3，1， 1，0） -（-6M，M， 3M，+M ） =（-3+6M， 1-M， 1-3M， M ） 下一步： 把主元素相应列变为单位向量: 这一行乘以 -（1-3M）加到最下一行 第一章：线性规划（3） Ci -3 1 1 0 0 M M CB XB X1 X2 X3 X4 X5 X6 X7 B-1b Θi 0 X4 3 -2 0 1 0 0 -1 10 - M X6 0 1 0 0 -1 1 -2 1 1 1 X7 -2 0 1 0 0 0 1 1 - 第2表 检验数 -1 1-M 0 0 M 0 3M-1 0 先确定主元素：定行检验数 负中取小，定列相除后正中取小 下一步： 把主元素相应列变为单位向量: 这一行乘以 -（1-M）加到最下一行 得到新检验数 第3表 检验数 -1 0 0 0 1 M-1 M+1 第一章：线性规划（3） Ci -3 1 1 0 0 M M CB XB X1 X2 X3 X4 X5 X6 X7 B-1b Θi －3