《运筹学 第一章 线性规划与单纯形法》由会员分享，可在线阅读，更多相关《运筹学 第一章 线性规划与单纯形法（25页珍藏版）》请在金锄头文库上搜索。
1、第一章 线性规划与单纯形法,1 线性规划问题及其数学模型 1.1 问题的提出eg.1 生产计划问题 问：产品、各生产多少件，使利润最大？,eg.2污水处理问题环保要求河水含污低于2，河水可自身净化20%。问：化工厂1、2每天各处理多少污水，使总费用最少？,分析：化工厂1处理污水1万m3,化工厂2处理污水2万m3。 min z = 10001 + 8002(2 - 1)/500 2/1000(1 - 0.2)(2 - 1) + 1.4 - 2/(500 + 200) 2/10001 22 1.41，2 0这里min z:表示求z的最小值。,线性规划的数学模型：ma (min)z = c11 +
2、c22 + + cnna111 + a122 + + a1nn (=, ) b1a211 + a222 + + a2nn (=, ) b2 am11 + am22 + + amnn (=, ) bm1，2，n 0,说明：,(1)决策变量：1，2，n 。一组决策变量表示为问题的一个方案；(2)目标函数：ma(min)zz为决策变量的线性函数;(3)约束条件一组线性不等式。 cj为价值系数, bi为资源， aij为技术系数(i=1,m;j=1,n) .,1.2 图解法 对于只有两个变量的线性规划问题可以用图解法求解 eg.3用图解法求eg.1。ma z = 21 + 3211 + 22 8 41
3、16 42 12 1，2 0,解：(1)建立1 - 2坐标；,(2)约束条件的几何表示；,(3)目标函数的几何表示；,z = 21 + 32 ,o,4,3,首先取z = 0，然后，使z逐 渐增大，直至找到最优解所对 应的点。,可见，在Q2点z取到最大值。因此， Q2点所对应的解为最优解。Q2点坐标为(4，2)。即: 1 = 4，2 = 2 由此求得最优解：1* = 4 2* = 2最大值：ma z = z* = 21 + 32 = 14(元),4,3,讨论：(1)唯一最优解 ma z = z*时，解唯一，如上例。,(2)无穷多最优解eg.4对eg.1，若目标函数z = 21 + 42，此时表示
4、目标函数的直线与表示条件的直线平行，最优点在线段Q3Q2上。即存在无穷多最优解。,(3)无界解eg.5ma z = 21 + 3241 16 1，2 0则2 ，z 。即存在无界解。在实际问题中，可能是缺少约束条件。,(4)无可行解eg.6ma z = 21 + 3221 + 42 81 + 2 11，2 0无公共部分，无可行域。即无可行解。在实际问题中，可能是关系错。,练习1,f()=36,1.3 线性规划的标准型1、标准型ma z = c11 + c22 + + cnna111 + a122 + + a1nn = b1a211 + a222 + + a2nn = b2 am11 + am22
5、 + + amnn = bm1，2，n 0,用向量表示,用矩阵描述为：ma z = CA = b 0其中: = (1,2,n)T决策变量向量C = (c1,c2,cn)价值向量b = (b1,b2,bm)T资源向量,2、标准型的化法(1)minma min z = c = -ma(-z) ma(-z) = -min z = -c令z = -z 则ma z = -c,(2)不等式(，)对于“”情况：在“”左边加上一个松弛变量（非负），变为等式；对于“”情况：在“”左边减去一个剩余变量（非负），变为等式。注意：松弛变量、剩余变量在目标函数中的价值系数为0。,(3)无约束变量令k = k - k”，
6、k,k” 0，代入即可。,eg.7将下述问题化为标准型min z = -1+22-331+ 2+ 3 7 1- 2+ 3 2 -31+ 2+23 = 5 1,2 0，3无约束,解：令3 = 3-3”，3,3” 0；式加上一个松弛变量4；式减去一个剩余变量5；令z = -zma z = 1- 22 + 3(3 - 3”) + 04 + 051 + 2 + (3 - 3”) + 4 = 71 - 2 + (3 - 3”) - 5 = 2-31 + 2 + 2(3 - 3”) = 51,2,3,3”,4,5 0,练习2：化标准型,1.4 线性规划解的概念设线性规划为 ma z = C A = b 0
7、 A为m n矩阵, n m, Rank A = m (A为行满秩矩阵）,1、可行解：满足条件、的；,2、最优解：满足条件的可行解；,3、基：取B为A中的m m子矩阵，Rank B = m，则称B为线性规划问题的一个基。 取B = (p1,p2,pm) pj = (a1j,a2j,amj)T则称1,2,m为基变量，其它为非基变量。,4、基解：取B = (p1,p2,pm)a11,a1m 1 a1m+1,a1n m+1 b1 + = am1,amm m amm+1,amn n bm 基 基变量 非基 非基变量,令 m+1 = = n = 0 (非基变量为0), 则 BB = b,5、基可行解满足式
8、要求的基解。如右图所示，各边交点O,Q1,Q2,Q3,Q4 均为基可行解；而其延长线的交点Q5为 基解，但不是基可行解。,O(0,0),Q1(4,0),Q2(4,2),Q4(0,3),Q3(2,3),Q5(4,3),6、可行基基可行解对应的B为可行基。,练习1 可行解、基础解和基础可行解举例,2 线性规划问题的几何意义 2.1 基本概念1、凸集：设K为En(n维欧式空间)的一点集，(1)K，(2)K。 若(1)+(1-)(2)K，则称K为凸集。（01）,2、顶点：K，(1)K，(2)K (任意两点)。若不能用(1)+(1-)(2)表示，则称为K的一个顶点。(01)注：顶点所对应的解是基可行解。3、凸组合：设(i)En，若存在0i 0 0， 即D为凸集,2、定理2 线性规划的基可行解对应于可行域的顶点。,3、定理3 若线性规划有解，则一定存在基可行解为最优解。,问 题,
