线性规划与单纯形法1

《线性规划与单纯形法1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划与单纯形法（LinearProgramming，简称LP）§1线性规化问题及其数学模型§2线性规化问题的几何意义§3单纯形法§4单纯形法的计算步骤§5单纯形法的进一步讨论§6应用案例§1线性规化问题及其数学模型1.1问题的提出例1：某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表，该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排生产计划使该工厂获利最多？ⅠⅡ资源设备原材料A原材料B1402048台时16kg12kg利润23x1x2§1线性规化问题及

2、其数学模型ⅠⅡ设备原材料A原材料B1402048台时16kg12kg利润23max目标函数约束条件1.1问题的提出x1x2z例2：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3,在两个化工之间有一条河流量为每天200万m3的支流,第一化工厂每天排放含某种有害物质的工业污水2万m3,第二化工厂排放这种工业污水1.4万m3,从第一化工厂排出的工业污水流到第二化工厂之前，有20%可以自然净化。根据环保要求河流中工业污水的含量应不大于0.2%。这两个化工厂都需处理一部分工业污水。第一化工厂处理工业污水的成本为1000元/万m3,

3、第二化工厂处理工业污水的成本为800元/万m3。问在满足环保要求的条件下，每厂各应处理多少工业污水，使两个化工厂处理工业污水的总成本最小。500万m3200万m3工厂1工厂22万m31000元/万m31.4万m3800元/万m3小于0.2%自然净化20%min目标函数约束条件特征：每一个问题都用一组决策变量（x1，x2，…，xn）表示某一个方案；存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示；都有一个要求达到的目标，它可以用决策变量的线性函数来表示，按问题的不同，要求目标函数实现最大化或最小化。min线性规划问题的数学

4、模型的一般形式为：目标函数约束条件线性规划问题解的概念可行解：若（x1，x2，……，xn）满足上述约束条件，则称（x1，x2，……，xn）为线性规划问题的可行解。可行域：所有可行解组成的集合称为可行域。最优解：使目标函数达到最大或最小的可行解称为最优解。1.2图解法Z=2Z=6Z=10Q(4,2)x2x10123454321Z=14X*=(4，2)Z*=14线性规划图解法解题步骤4将最优解代入目标函数，求出最优目标函数值。1在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部分，即可行域，可行域中的点即为可行解。2标出目标函数值

5、增加的方向。3若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最后相交的点，该点就是最优解。X2X10123454321X2X10123454321无穷多最优解无界解AB唯一最优解无穷多最优解无界解无可行解有最优解无最优解1.3线性规化问题的标准型式目标函数约束条件标准型的其它表示形式如何化标准型目标函数求最小minz=CX。可化为：max(-z)=-CX。约束条件为不等式。对于“≤”不等式，在不等式的左边加上非负松驰变量后变为等式；对于“≥”不等式，在不等式的左边减去非负剩余变量后变为等式。3.变量xk

6、无约束。可令xk=xk’-xk’’例：1.4线性规化问题的基可行解例：基**1.4线性规化问题的基可行解基：设A是约束方程组的m×n阶系数矩阵，其秩为m，B是矩阵A中m×m阶非奇异子矩阵（

7、B

8、≠0），则称B是线性规划问题的一个基。基B的列Pj称为基向量，与基向量对应的变量xj称为基变量，否则称为非基变量。基解：令非基变量为零，由约束方程AX=b求得的解称为基解。基可行解：满足非负条件的基解称为基可行解。可行基:对应于基可行解的基称为可行基。注：基解的个数最多是Cnm个，基可行解的个数一般要小于基解的个数。1可行解与最优解：最优解一定是可行

9、解，但可行解不一定是最优解。线性规划解之间的关系基解不一定是可行解，可行解也不一定是基解。2可行解与基解：3可行解与基可行解：基可行解一定是可行解，但可行解不一定是基解。基可行解一定是基解，但基解不一定是基可行解。4基解与基可行解：5最优解与基解：最优解不一定是基解，基解也不一定是最优解。问题：最优解与基本可行解？非可行解可行解基本可行解基本解X1X2X1X2X1X2§2线性规化问题的几何意义2.1基本概念2.凸组合：3.顶点：1.凸集：凸集：设K是n维欧氏空间的一个点集，若任意两点X(1)，X(2)∈K的连线上的一切点X=αX(1)+(1

10、-α)X(2)∈K，（0≤α≤1），则称K为凸集。凸组合：设X(1)，X(2)……X(k)是n维欧氏空间的k个点，若存在μ1，μ2……μk，且0≤μi≤1，i=1，2……k，∑μ