运筹学秘籍 1 2 3 4 5 判断 选择 应用 证明 计算 5题 5题 4题 1题 5题 2分 2分 6分 8分 10分 10分 34分 6分 40分
将一般问题化为标准型 Max S = -x1+2x2-3x3 Min S = x1-2x2+3x3’-3x3” s.t. x1+x2+x3 <= 7 s.t. x1+x2+x3’-x3 ”+x4 =7 x1-x2+x3 >=2 x1-x2+ x3’-x3 ” -x5=2 -3x1+x2+2x3 = 5 -3x1+x2+2x3’-2x3” =5 x1,x2 >=0 x3 是自由变量 x1, x2,x3’,x3 ”, x4,x5>= 0
一、单纯形法
定义：如何从一个可行基找另一个可行基？称基变换。两个基本可行解称为相邻的，如果它们之间仅变换一个基变量。对应的基称为相邻可行基。
从数学角度看，若让非基变量 x1,x 2取值从零增加，相应的目标函数值Z也将随之减少。因此有可能找到一个新的基本可行解，使其目标函数值有所改善。即进行基变换，换一个与它相邻的基。再注意到x1前的系数－2比前的系数－1小，即x1每增加一个单位对Z的贡献比x2大。故应让x1从非基变量转为基变量，称为进基。又因为基变量只能有三个，因此必须从原有的基变量x3,x4,x5中选一个离开基转为非基变量，称为出基。谁出基？又因为 x2仍留作非基变量，故仍有x2=0.
用增广矩阵的初等变换表示为：
①在迭代过程中要保持常数列向量非负，这能保证基可行解的非负性。最小比值能做到这一点。②主元素不能为0。因为行的初等变换不能把0变成1。③主元素不能为负数。因为用行的初等变换把负数变成1会把常数列中对应的常数变成负数。
LP当前解已是最优的四大特征：⑴存在一组(初始)可行基（其系数矩阵为单位阵）。⑵检验行的基变量系数=0。⑶ 检验行的非基变量系数≥0。（全部〉0?唯一解。存在=0?无穷多个解。）⑷ 常数列向量≥0。
1分别用图解法和单纯形法求线性规划问题 2 用单纯形法表格求解线性规划问题
maxz?2x1?x2x2?33x1?x2?12x1?x2?5x1?2?0
minz?3x1?2x2?x3x1?2x2?x3?82x1?x2?5x1?3?0
二、人工变量法（也称大M法）所给LP的标准型中约束矩阵中没有现成的可行基时用
M为任意大的实数，称为罚因子
x6,x7是强行引进，称为人工变量。它们与x4,x5不一样。x4,x5称为松弛变量和剩余变量,是为了将不等式改写为等式而引进的，而改写前后两个约束是等价的。人工变量的引入一般来说是前后不等价的。只有当最优解中，人工变量都取值零时（此时人工变量实质上就不存在了）才可认为它们是等价的。得到 minZ?3x1?0x2?x3?0x4?0x5?Mx6?Mx7
