1、画出可行域(不等式化为Ax+By+C的形式,<或≤在对应直线的左边,反之是右边)。
2、将所求的对应最值化为斜截式,然后化过原点的对应平行直线。例如求z=3x+y的最值,要化为y=-3x+z,画直线y=-3x与之平行。
3、找到对应最值的交点,把交点坐标代入。
扩展资料:
线性规划的其他解法:
求解线性规划问题的基本方法是单纯形法,已有单纯形法的标准软件,可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。
为了提高解题速度,又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题,也可采用图解法求解。
这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解,但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。
S.T.、AX =b、X>=0其中A为一个m*n矩阵。若A行满秩则可以找到基矩阵B,并寻找初始基解。用N表示对应于B的非基矩阵。则规划问题1可化为:
规划问题2:Min z=CB XB+CNXN、XB >= 0, XN >= 0 (2)、(1)两边同乘于B-1,得XB + B-1 N XN = B-1 b同时,由上式得XB = B-1 b - B-1 N XN,也代入目标函数,问题可以继续化为:
规划问题3:Min z=CB B-1 b + ( CN - CB B-1 N ) XNS.T.、XB+B-1N XN = B-1 b (1)、XB >= 0, XN >= 0 (2)、令N:=B-1N,b:= B-1 b,ζ= CB B-1b,σ= CN - CB B-1 N,则上述问题化为规划问题形式4:Min z= ζ + σ XN。
S.T.、XB+ N XN = b (1)、XB >= 0, XN >= 0 (2)。在上述变换中,若能找到规划问题形式4,使得b>=0,称该形式为初始基解形式。上述的变换相当于对整个扩展矩阵(包含C及A) 乘以增广矩阵。所以重在选择B,从而找出对应的CB。若存在初始基解、若σ>= 0、则z >=ζ。
同时,令XN = 0,XB = b,这是一个可行解,且此时z=ζ,即达到最优值。所以,此时可以得到最优解。若σ >= 0不成立、可以采用单纯形表变换。
σ中存在分量<0。这些负分量对应的决策变量编号中,最小的为j。N中与j对应的列向量为Pj。若Pj <=0不成立、则Pj至少存在一个分量ai,j为正。
在规划问题4的约束条件(1)的两边乘以矩阵T。则变换后,决策变量xj成为基变量,替换掉原来的那个基变量。为使得T b >= 0,且T Pj=ei(其中,ei表示第i个单位向量),需要:l ai,j>0。
lβq+βi*(-aq,j/ai,j)>=0,其中q!=i。即βq>=βi/ ai,j * aq,j。n若aq,j<=0,上式一定成立。n若aq,j>0,则需要βq / aq,j >=βi/ ai,j。
因此,要选择i使得βi/ ai,j最小。如果这种方法确定了多个下标,选择下标最小的一个。转换后得到规划问题4的形式,继续对σ进行判断。
由于基解是有限个,因此,一定可以在有限步跳出该循环。对于每一个i,ai,j<=0最优值无解。若不能寻找到初始基解无解。若A不是行满秩化简直到A行满秩,转到若A行满秩。
2.将所求的对应最值化为斜截式,然后化过原点的对应平行直线。例如求z=3x+y的最值,要化为y=-3x+z,画直线y=-3x与之平行
3.找到对应最值的交点,把交点坐标代入