《运筹学线性规划与单纯性表法》由会员分享，可在线阅读，更多相关《运筹学线性规划与单纯性表法（125页珍藏版）》请在金锄头文库上搜索。
1、1,第一章 线性规划与单纯形法,本章重点内容 线性规划模型与解的主要概念 线性规划的单纯形法，线性规划多解分析 线性规划的应用建模,2,第一节 线性规划问题及数学模型,一、实例 二、线性规划问题（LP问题）的共同特征 三、两变量线性规划问题的图解法 四、线性规划问题的标准型 五、标准型LP问题解的概念 六、可行解、基解和基可行解举例,3,一、实例,例1 生产计划问题(书P8),Step 1:明确问题，设定决策变量 设I、II两种产品的产量分别为x1, x2 。,Step 2: 确定约束条件,问应如何安排生产 使该厂获利最多？,4,说明：OBJ 表示Objective; s.t. 表示Subje
2、ct to,Step 3: 给出目标函数,Step 4: 整理数学模型,5,例2 下料问题 现要做100套钢架，每套需2.9米、2.1米和1.5米的圆钢各一根。已知原料长7.4米，问如何下料，使用的原料最少（余料最少或根数最少）？,分析： 最简单的做法是：每根7.4米长的原材料各截取三种规格的元钢一根，则料头为0.9米，100套则浪费材料90米。关键是要设计套裁方案，不能有遗漏。,6,解：设 x1, x2 , x3, x4 , x5分别代表五种不同的原料用量方案。,余料最少的LP模型：,7,根数最少的LP模型：,8,LP是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以
3、下两个问题中的一个： （1）当资源给定时，要求完成的任务最多； （2）当任务给定时，要求为完成任务所消耗的资源最少。 若上述问题的目标约束都能表达成变量的线性关系，则这类优化问题称LP问题。 LP是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。,9,目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。,每一个问题变量都用一组决策变量（x1, x2, , xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负且连续的。,存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。,结论：线性规划是研究在一组线性不等式或线性等式约
4、束下，使得某一线性目标函数取最大或最小的极值问题。,二、线性规划问题（LP问题）的共同特征,10,Max(Min) Z=c1x1+c2x2+cnxn (1) a11x1+a12x2+a1nxn ( =, ) b1 a21x1+a22x2+a2nxn ( =, ) b2 s.t. (2) am1x1+am2x2+amnxn ( =, ) bm xj0, j=1,2, ，n (3) (1)目标函数；(2)约束条件；(3)决策变量非负 n变量个数； m约束行数； cj价值系数； bi右端项或限额系数； aij技术系数； xj决策变量,线性规划模型的一般形式为：,11,线性规划模型的紧缩形式,n变量个
5、数； m约束行数； cj价值系数； bi右端项或限额系数； aij技术系数； xj决策变量,12,练习题：是否为线性规划模型？,13,1.线性不等式的几何意义 半平面,作出LP问题的可行域 作出目标函数的等值线 移动等值线到可行域边界得到最优点,2.图解法步骤,三、两变量线性规划问题的图解法,14,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,Q1 4,Q4 3,0,例3 （书P8）：,Q2(4,2),Z=2x1+3x2,做目标函数2x1+3x2的等值线，与阴影部分的边界相交于Q2(4,2)点，表明最优生产计划为：生产I产品4件，生产II产品2件。,Q3,15,目标函数z=
6、ax1+bx2的值递增的方向与系数a、b有关,a0, b0,a0,X1,X2,a0, b0,a0, b0,z=ax1+bx2 目标函数等值线：ax1+bx2=k 移项 x2=-a/bx1+k/b 目标函数等值线在纵轴上的截距为k/b,16,例4,Z=36,17,例 用图解法求解线性规划问题,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,Q1 4,Q4 3,0,Q2(4,2),Z=2x1+4x2,当Z值由小变大时，将与Q2Q3重合 Q2Q3上任意一点都是最优解 有无穷多最优解（多重解）,Q3(2,3),18,例 用图解法求解线性规划问题,可行域无界无界解 （ “无有限最优解”
7、或“最优解无界”） 约束条件过分宽松,可行域无解（不闭合）一定就会出现无界解吗？,19,例 用图解法求解线性规划问题,可行域无界唯一最优解X*=(1,0)，对应于点A,20,例 用图解法求解线性规划问题,可行域无界无穷多最优解对应于点B沿着OB向右上方发出的射线上的所有点,x2,x1,x1-x2=1,B(2,1),A(1,0),-x1+2x2=0,0,21,例（书P11）：,无可行解（可行域为空）,-2x1+x2=4,无最优解,22,3.图解法的作用,能解决少量问题,揭示了线性规划问题的若干规律,解的类型,可行域类型,唯一最优解,无穷多最优解,最优解无界 （无有限最优解）,无解 （不存在可行域
8、）,非空有界,无界,空集,规律1：,23,规律2：,线性规划问题的可行域为凸集 线性规划问题凸集的顶点个数是有限的 最优解可在凸集的某顶点处达到,24,小结：图解法的基本步骤： 1在直角坐标系作出可行域S的区域（一般是一个凸多边形） 2令目标函数值取一个已知的常数k，作等值线：c1x1+c2x2=k 3对于max问题，让目标函数值k由小变大，即让等值线进行平移，若它与可行域S最后交于一个点（一般是S的一个顶点），则该点就是所求的最优点，若与S的一条边界重合，此时边界线上的点均是最优点 4将最优点所在的两条边界线所代表的方程联立求解，即得最优解X*，把最优解X*带入目标函数，得最优值Z*=CX*
9、 注意：若是求目标函数最小值，等值线向反方向移动,25,四、线性规划问题的标准型,1.标准型,（1）目标函数：max,（2）约束条件：等式,（3）变量约束：非负 xj0,（4）资源限量：非负bi 0,标准型的构成要素,26,2.线性规划标准型的紧缩形式,27,3.线性规划标准型的向量和矩阵表达式,矩阵式: Max Z=CTX s.t. AX=b X0,n 向量式: Max Z= cjxj j=1 n s.t. Pjxj=b j=1 xj 0, j=1,2, . ,n,28,4.所有LP问题均可化为标准型,（1）最小转换成最大,29,（2）不等式约束条件转换成等式约束条件,（3）变量约束转换,（
10、4）把bi0转换成bi0,30,例5 化标准型,可化为,1.处理决策变量 2.处理目标函数 3.约束条件不等式 4.处理约束条件右端 常数项,31,例6 化标准型,1.处理决策变量 2.处理目标函数 3.约束条件不等式 4.处理约束条件右端 常数项,32,Max Z =x1+2x2+3x4-3x5+0x6+0x7 s.t. x1 - x2 + x4 - x5+x6 = 7 x1+x2 + x4 - x5 - x7 = 2 -3x1 -x2+3x4 -3x5 = 5 x20 , xj0, j=1,4,5,6,7,Max Z =x1+2x2+3(x4-x5)+0x6+0x7 s.t. x1 - x
11、2 +(x4 - x5 ) +x6 = 7 x1+x2 +(x4 - x5 ) - x7 = 2 -3x1 -x2+3(x4 -x5) = 5 x20 , xj0, j=1,4,5,6,7,最终结果,中间结果,33,课堂练习,34,五、标准型LP问题解的概念,35,（1）,（2）,（3）,约束系数矩阵：,x1,x2,x3,x4,x5,例：,36,约束系数矩阵：,可能的基矩阵是A中任意三个列的组合，共10个。,37,令B = =( P1 , P2 , , Pm ) 且| B | 0 ，则称Pj (j=1,2,m) 为基向量。 与基向量Pj对应的变量xj称为基变量， 记为XB = ( x1 , x
12、2 , , xm )T，其余的变量称为非基变量，记为XN = ( xm+1 , xm+2 , , xn ) T 。,38,39,40,B1=(P1,P2)：基,令：,XB1=(x1,x2),x1=0， x2=2,X=(0, 2, 0, 0),XB1=(0, 2),对应于B1的基解为,也是基可行解,41,线性规划标准型问题解的关系,约束方程的 解空间,基解,可行解,非可行解,基可 行解,42,例7 Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1, x2 0,六、可行解、基解和基可行解举例,4x1=16,4x2=12,x1+2x2=8,x1,x2,0,Z
13、=2x1+3x2,A,B,C,D,E,F,G,H,标准型,43,例8,44,LP标准型问题解的结论,根据LP的图解法及解的基本概念可知： 基解对应约束条件的交点； 基可行解对应可行域的顶点 某个基可行解一定是最优解，即一定在可行域的顶点上得到最优解。,45,第二节 LP问题的基本理论,一、基本概念,46,判断以下图形哪些是凸集，哪些不是凸集？,判断下列集合是否凸集？,47,定理1 LP问题的可行域为一凸集。,二、基本定理,48,引理 线性规划问题的可行解X=(x1, x2, , xn)T是基可行解的充要条件为X的正分量所对应的系数列向量是线性独立的。,49,定理2 线性规划问题的基可行解对应于
14、可行域的顶点。,（即：若X是LP问题的可行解，则“X是LP问题的基可行解”等价于“X是LP问题可行域顶点”）,因为X是基可行解，则其对应的向量组a1,a2, ,am线性无关(mm时，有xj=xj(1)= xj(2)= 0.,50,51,52,53,定理3 若可行域有界，则LP问题的目标函数一定可以在其可行域的顶点上达到最优。,引理 若S是有界凸集，则任何一点XS可表示为S的顶点的凸组合。,54,线性规划问题的可行域是凸集(定理1)；凸集的顶点对应于基可行解(定理2)，基可行解(顶点)的个数是有限的；若线性规划有最优解，必在可行域某顶点上达到(定理3)。因此,我们可以在有限个基可行解中寻找最优解
15、。,由线性代数知，对标准形LP问题，用枚举法可以求出所有基解，再通过观察找出其中的可行解（基可行解），进而找出最优解。但如果变量和方程较多，比如m=50，n=100，所有基解有可能达1029个，即使计算机每秒能求解1亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法。,为加快计算速度，算法必须具有两个功能，一是每得到一个解，就来检验是否已经最优，若是停止。二是若不是最优，要保证下一步得到的解不劣于当前解。这就是线性规划的单纯形法。,55,第三节 单纯形法,一、基本思想,检验解的 最优性,结束,Y,枢轴运算（旋转运算） 确定另一个基本可行解,N,化LP问题为标准型， 确定一个初始基本可行解,化LP问题为标准型，从可行域的某个基可行解（一个顶点）开始，转换到另一个基可行解（另一个顶点），并使目标函数值得到改善，如此反复，从而求得问题的最优解。其实质是逐步迭代（逼近）法。,56,单纯形法举例（P20）,化为标准型,二、基本原理举例,57,1. 初始基可行解的确定,要得到一个初始基可行解，必须找到一个
