第题 线性规划.pptVIP

　　对于有n个变量，m个方程的方程组，若m个变量的系数所构成的矩阵是非奇异的，可将m个列向量对应的变量留在左边，其余移到右边。利用线性代数中的克莱姆法，可求得留在左边的m个变量关于右边n-m个变量的m个函数表达式。 　　下面是比较抽象的线性规划解的概念。 基:设A是约束方程组的mXn系数矩阵,若秩为m。B是A中m阶非奇异子矩阵,|B|≠0,则称B是LP问题的一个基. 其中，P1, P2,…Pm称为基向量，与基向量对应的变量称为基变量，记为XB=(x1, x2,…xm)T,其余为非基变量，XN=(xm＋1, xm+2,…xn)T,这样，X=(XB, XN) 利用基B可求得m个基变量XB=(x1, x2,…xm)T关于非基变量XN=(xm＋1, xm+2,…xn)T的m个表达式。令非基变量xm+1=xm+2=….=xn=0，用高斯消去法，可得m个基变量的唯一解。把该解与等于0的非基变量一起称为与基B对应的基解：X=(x1,x2,…,xm,0,0…,0)T 可行解:满足约束条件的解。所有可行解的集合称可行域. 基可行解:满足约束条件的基解. 可行基:对应于基可行解的基. 最优解:使目标函数达到最优的可行解.（当最优解的基变量组成不止一个时，LP有无穷多个最优解，可行域的某一边界） 无解; 无界解 约束方程的 解空间 基础解 可行解 非可行解 基础 可行解 最优解 (2) 线性规划问题的定理与引理 定理1： LP所有可行解的组合（可行域）是凸集 引理1： LP问题的可行解x=(x1,x2,…xn)T为基可行解的充要条件是x的正分量所对应的系数列向量Pj是线性独立的. 定理2： LP问题的基可行解X对应于可行域D的顶点. 定理3 ：若可行域有界，LP问题的目标函数一定在可行域的顶点上达到极值. 推论： 若可行域无界,可能无最优解,也可能有（但一定在顶点达到）. 顶点的数目≤Cnm个，当m,n较小时,可用枚举法找出所有基可行解。当m,n很大时, 需要寻优方法—单纯形法. 凸集 顶点 凸组合 定理：线性规划的可行域不是空集就是凸集 定理：X为D的一个顶点的充分必要条件是X为线性规划的基可行解。 定理：若LP问题有最优解，则一定是基可行解。 3.3 单纯形法 思路：根据LP标准型,从可行域某个顶点开始,转移到另一个顶点,并使ob值增大,当ob最大时,LP得最优. 有方向的在顶点上转移. * * * * * * * * * * * * * * * * 线性规划的概念： 是运筹学规划论中的一个重要分支，研究： 在人力和物力资源一定的情况下，如何和恰当的运用这些资源，以达到最有效的目的。 系统的任务已定，如何合理筹划，精细安排，用最少的资源(人力、物力和财力)去实现这个任务。 3 线性规划LP(LINEAR PROGRAMMING) 3.1 线形规划的数学模型 (1) LP问题及其数学模型 例1：规划方案1中，甲乙两水库给A、B、C三座城市供水，甲库可供水量20万m3/d，乙库为25万m3/d，A、B、C需水为10万m3/d,15万m3/d, 20万m3/d。已知输水费用，求满足三个城市用水需要费用最小的输水方案。 A B C 甲 乙 解: ob minf(x)=c11x11+c12x12+…+c23x23 表一 输水费用 A B C 甲 90 70 100 C11 C12 C13 乙 80 65 80 C21 C22 C23 表二 输水变量 A B C 甲 x11 x12 x13 乙 x21 x22 x23 S.t x11+x21≥10 x12+x22≥15 x13+x23≥20 x11+x12+x13≤20 x21+x22+x23≤25 x11,x12…x23≥0 城市需水量约束 水资源量限制约束 变量非负约束 例2 化工厂1排放污水至化工厂2之前，有20%可自然净化，要求河流中工业污水的含量不大于0.2%，求使两厂总处理污水费用最小的方案。 化工厂1 化工厂2 W=500万m3/d W=200万m3/d 河流 每天排放污水 污水处理成本 化工厂1 化工厂2 2万m3 1.4万m3 1000元/万m3 800元/万m3 解:设工厂1，2每天处理污水量分别为x1，x2万方 (2- x1)/500≤0.2% [0.8(2- x1)+(1.4- x2)]/(500+200) ≤0.2% ob: minz=1000 x1+800 x2 s.t