线性规划解的概念

1.2 线性规划解的概念1图解法对二维问题，可作出约束的图，简单直观地理解线性规划的解。例 考察线性规划问题等值线 x+3y=C可行域 最优解继续2解的概念可行解可行解(feasible solution)：满足线性规划问题(LP)的所有约束条件的解，称为线性规划问题的一个可行解。可行域可行域：(LP)的所有可行解组成的集合K称为(LP)的可行域。若可行域为空，则称不可行。对标准型线性规划问题，其可行域为最优解最优解(optimal solution)：可行域中每个可行解都对应一个目标值，其中对应的目标函数值最小的可行解x*，称为(LP)的最优解，也称为(LP)的解。即最优值最优值：最优解对应的目标值称为最优值。3基基 设 为满秩矩阵(秩为m)，是A中的非奇异子矩阵 ，则称B为（LP)的一个基。基变量与非基变量基变量与非基变量 B是由A的m个线性无关的列组成，对应的变量称为基变量，剩下的变量称为非基变量。基解基解 令非基变量变量等于0，可得线性方程组的一个解，称为基解(basic solution).基可行解基可行解 若基解还是可行的，即满足非负性条件，则称为基可行解(basic feasible solution 简记为bfs)。4基解的个数非退化的基可行解：若基变量全部为正。否则称为退化的基可行解，即有基变量为0可行解基解基可行解非可行解5例 求出线性规划问题的全部基解，指出哪些是可行的。图解法6线性规划解的几种可能情况1.无可行解 可行域为空集，约束中存在矛盾方程。2.有唯一的最优解（通常的情况），必是可行域的顶点。3.有无穷多个最优解。4.有可行解但无最优解 可行域必无界。71.3线性规划问题的几何意义8基本概念凸集 设K为n维线性空间的一点集，若对K中任意两点x,y，及任意的 ，有则称K为凸集。规定空集和单点集为凸集。9例 超平面和半空间都是凸集。凸组合凸组合 设 为 中的点，为满足下列条件的一组实数则称 为 的凸组合。极点极点 设K为凸集，若x不能表示成K中不同的两点的凸组合，则称x为K的一个极点(顶点)。10基本定理定理1 任意一组凸集的交集仍为凸集。定理2 线性规划问题的可行域是凸集。引理1 线性规划问题的可行解为基可行解的充要条件是其正分量所对应的系数列向量是线性无关的。证明：必要性 若x是基解，由定义，正分量对应的列线性无关。充分性 若正分量对应的列线性无关，则个数不超过m，若=m,则是基，若m,可扩充成基。11定理3 线性规划问题的基可行解对应于可行域的顶点。证明：若x是基可行解，设前m个分量为基变量，但不是极点，则存在x1,x2,01,x=x1+(1-)x2.x1,x2的后n-m个分量为0。若x是极点，但不是基可行解，正分量对应的列线性相关。对任意的实数取充分小的得两可行解x1,x2，使x=x1/2+x2/2。12推论 线性规划可行域的顶点个数有限。引理2 若K为有界闭凸集，则其中任何一点可表示为其顶点的凸组合。不证明，举例说明。定理4 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点达到最优。证明：另外，若可行域无界，但有最优解，则一定也可在顶点处达到最优。定理4换成代数说法就是：线性规划问题若存在最优解，则一定存在最优的基可行解。13第二章 单纯形法14穷举法的困难已知线性规划问题的一基可行解，问题1.此基可行解是否最优；2.该问题是否无最优解；3.如何改进（求一更好的基可行解）；4.算法是否会有限步结束；5.如何找一基可行解。152.1 单纯形表为计算方便，将系数提出来，形成表格：16设有一可行基，不妨设是前m个向量，则线性方程组可化为如下形式其中目标函数可表成非基变量的函数将系数提出列成表，称为对应于基B的单纯形表17单纯形表18最优性检验与解的判别定理1（最优解的判别定理）设 为(LP)的一基可行解，若对任意的非基变量，都有 ，则 为最优解，称 为检验数。定理2 若对某非基变量，有那么，该线性规划问题无最优解。19基可行解的改进1.进基变量的选择2.出基变量的选择最小比值原则证明新的解是基可行解，在非退化假设下，新解目标值下降。20单纯形法的计算步骤算法(单纯形法)1)找出初始可行基,确定初始可行解,建立初始单纯形表；2)检验各非基变量的检验系数,若全部非正，结束,得到最优解;3)若某非基变量检验数为正，且其对应的系数列向量全部非正，结束，问题无最优解;4)选某个检验数为正的非基变量进基，计算最小比值，确定出基变量，5)以所选元素为主元进行消元,得新单纯形表，转2)。21例1 用单纯形法求线性规划问题的解化为标准型,列初始单纯形表6/18/222作旋转变换得新的单纯形表5/2-4/33/2（2/3）主元23例2 用单纯形法求线性规划问题的解基x1x4x6-310/3主元241/40-1/211/43+5/201/410-3-5/20-3/411/20-3/4-9基x1x3x6基x1x3x6大于04-25基x2x3x6检验数全部非正,得最优解(0,4,5,0,0,11),最优值为-11.26