用表格法解线性规划问题.ppt

18.3用表格法解线性规划问题,新知,一、线性规划问题的标准形式：,新知,线性规划问题的标准形式的特点：,（1）目标函数为最大值形式；,（2）约束条件用等式表示，且等式右端的常数为非负数；,（3）决策变量非负。,新知,线性规划问题化为标准形式的方法：,（1）对于目标函数，如果是,则令,就得到,新知,线性规划问题化为标准形式的方法：,（2）对于约束条件，如果有,则在不等式（或等式）两边同乘以“-1”,新知,线性规划问题化为标准形式的方法：,（3）对于约束条件中的不等式，如果是，则在左端加上一个变量使其成为等式；,如果是，则在左端减去一个变量使其成为等式。,添加的变量称为人工变量。,人工变量不产生效益，所以规定其在目标函数中系数为0,例题解析,例1将18.1例1中的线性规划问题化为标准形式：,例题解析,例1将18.1例1中的线性规划问题化为标准形式：,解用x1,x2分别取代x,y,则标准形式为：,因为,所以加上人工变量。,例题解析,例2将下列线性规划问题化为标准形式：,例题解析,解令z=-z，则标准形式为：,因为,所以减去人工变量。,练习,1,练习,2,新知,表格法解线性规划问题,解:(1)建表把目标函数和约束方程转换成表格：,新知,第2,3行是约束方程的系数和常数项，第4行的数是目标函数的系数，第一列是人工变量。,3,4,1,0,250,100,1,0,1,2,0,0,4,5,新知,（2）确定换入变量考虑第4行中的正数，因为54，将”5”所在列的决策变量x1定位换入变量。,3,4,1,0,250,100,1,0,1,2,0,0,4,5,新知,（3）确定换出变量将b所在列的数除以变量x1所在列中对应的数,3,4,1,0,250,100,1,0,1,2,0,0,4,5,将较小商数对应的除数“2”所在行的人工变量x4定为换出变量。,新知,（4）进行变换，消元变量x1所在行和列的交叉点的数是2，为了方便消元，将“2”变成“1”。所以这行的数都除以“2”.,3,4,1,0,250,100,1,0,1,2,0,0,4,5,1,50,新知,（4）进行变换，消元将第2,4行中x1所在列的数都化为0,3,4,1,0,250,0,0,0,4,5,1,50,将第3行的所有数乘以“-3”，分别与第2行中对应的数相加，所得结果替换第2行。,0,100,将第3行的所有数乘以“-5”，分别与第4行中对应的数相加，所得结果替换第4行。,0,-250,+,+,因第4行中还有正数,故重复（2）（5）步骤。直到第4行中不再有正数为止。,新知,（5）重复操作，得出最优解,1,100,0,0,0,1,50,0,-250,新知,（5）重复操作，得出最优解,1,100,0,0,0,1,50,0,-250,确定换入变量考虑第4行中的正数，因为，将”所在列的决策变量x2定位换入变量。,新知,（5）重复操作，得出最优解,1,100,0,0,0,1,50,0,-250,确定换出变量,将b所在列的数除以变量x1所在列中对应的数,将较小商数对应的除数“”所在行的人工变量x3定为换出变量。,进行变换，消元变量x2所在行和列的交叉点的数是，为了方便消元，将“”变成“1”。所以这行的数都除以.,新知,（5）重复操作，得出最优解,1,100,0,0,0,1,50,0,-250,1,40,新知,（5）重复操作，得出最优解,40,0,0,0,1,50,0,-250,1,将第3,4行中x2所在列的数都化为0,将第2行的所有数乘以“”，分别与第3行中对应的数相加，所得结果替换第3行。,将第3行的所有数乘以“”，分别与第4行中对应的数相加，所得结果替换第4行。,0,30,+,+,0,-310,新知,（5）重复操作，得出最优解,40,0,1,30,0,-310,1,0,0,此时第4行不再有正数第2,3行中行与列的同一决策变量交叉处为1决策变量x1和x2所在行的最后一个数就是最优解,新知,（5）重复操作，得出最