线性规划初步

1、基础知识：基础知识：1线性规划问题的有关概念线性规划问题的有关概念(1)在约束条件下求目标函数的最大值或最小值的问在约束条件下求目标函数的最大值或最小值的问题叫做题叫做线性规划问题线性规划问题(2)记号记号“max”表示取函数的最大值，表示取函数的最大值，“min”表示取表示取函数的最小值函数的最小值2二元线性规划问题的图解法二元线性规划问题的图解法(1)只有两个决策变量的线性规划问题叫做只有两个决策变量的线性规划问题叫做二元线性规划问题二元线性规划问题(2)在平面直角坐标系中，方程在平面直角坐标系中，方程AxByC0(A、B不全为不全为0)表示一条直线，它把平面分成两个区域，表示一条直线，它

2、把平面分成两个区域，对直线对直线AxByC0一侧的任意一点一侧的任意一点P(x，y)，有，有AxByC0，而对另一侧的任意一点，而对另一侧的任意一点Q(x，y)，则有则有AxByC4，将，将”5”所在列的决策变量所在列的决策变量x1定位换入变量。定位换入变量。1x2x3x4xb3x4x341025010010120045（3）确定换出变量确定换出变量 将将b所在列的数除以变量所在列的数除以变量x1所在列中对应的数所在列中对应的数1x2x3x4xb3x4x34102501001012004521003250将较小商数对应的除数将较小商数对应的除数“2”所所在行的人工变量在行的人工变量x4定为换出

3、变量。定为换出变量。1x（4）进行变换，消元进行变换，消元变量变量x1所在行和列的交叉点的数是所在行和列的交叉点的数是2，为了方便，为了方便消元，将消元，将“2”变成变成“1”。所以这行的数都除以。所以这行的数都除以“2”.1x2x3x4xb3x3410250100101200451x1212150（4）进行变换，消元进行变换，消元将第将第2,4行中行中x1所在列的数都化为所在列的数都化为01x2x3x4xb3x3410250000451x1212150将第将第3行的所有数乘以行的所有数乘以“-3”，分别与第，分别与第2行中对应行中对应的数相加，所得结果替换第的数相加，所得结果替换第2行。行。

4、02523100将第将第3行的所有数乘以行的所有数乘以“-5”，分别与第，分别与第4行中对应行中对应的数相加，所得结果替换第的数相加，所得结果替换第4行。行。02325-250)3()5(+因第因第4行中还有正数行中还有正数 ,故重复（故重复（2）（5）步骤。）步骤。直到第直到第4行中不再有正数为止。行中不再有正数为止。（5）重复操作，得出最优解重复操作，得出最优解1x2x3x4xb3x11000001x1212150025232325-25023（5）重复操作，得出最优解重复操作，得出最优解1x2x3x4xb3x11000001x12121500252325-25023确定换入变量确定换入变

5、量 考虑第考虑第4行中的正数，因为行中的正数，因为 ，将，将” ”所所在列的决策变量在列的决策变量x2定位换入变量。定位换入变量。02323（5）重复操作，得出最优解重复操作，得出最优解1x2x3x4xb3x11000001x12121500252325-25023确定换出变量确定换出变量215025100将将b所在列的数除以变量所在列的数除以变量x2所在列中对应的数所在列中对应的数将较小商数对应的除数将较小商数对应的除数“ ”所所在行的人工变量在行的人工变量x3定为换出变量。定为换出变量。252x进行变换，消元进行变换，消元变量变量x2所在行和列的交叉点的数是所在行和列的交叉点的数是 ，为了

6、方，为了方便消元，将便消元，将“ ”变成变成“1”。所以这行的数都。所以这行的数都除以除以 .（5）重复操作，得出最优解重复操作，得出最优解1x2x3x4xb11000001x12121500252325-250232x2525251525340（5）重复操作，得出最优解重复操作，得出最优解1x2x3x4xb400001x1212150025-250232x15253将第将第3,4行中行中x2所在列的数都化为所在列的数都化为0将第将第2行的所有数乘以行的所有数乘以“ ”，分别与第，分别与第3行中对应的数行中对应的数相加，所得结果替换第相加，所得结果替换第3行。行。21将第将第3行的所有数乘以行的所有数乘以“ ”，分别与第，分别与第4行中对应的数行中对应的数相加，所得结果替换第相加，所得结果替换第4行。行。230)21(515430+)23(+05358-310（5）重复操作，得出最优解重复操作，得出最优解1x2x3x4xb4001x1300-3102x152530515405358此时此时第第4行不再有正数行不再有正数第第2,3行中行与列的同一决策变量交叉处为行中行与列的同一决策变量交叉处为1决策变量决策变量x1和和x2所在行的最后一个数就是最优解所在行的最后一个数就是最优解（5）重复操作，得出最优解重复操作，得出最优解1x2x3x4xb4001x130