管理运筹学02线性规划.ppt

《管理运筹学02线性规划.ppt》由会员分享，可在线阅读，更多相关《管理运筹学02线性规划.ppt（77页珍藏版）》请在三一办公上搜索。

1、2023/11/4,1,1.线性规划问题及其数学模型2.线性规划的图解法3.线性规划问题的标准形式4.线性规划的解集特征5.线性规划的单纯形法6.单纯形法的进一步讨论,第二章 线性规划,2023/11/4,2,线性规划问题及其数学模型,资源合理利用问题：第5页例2-1质量检验问题：第6页例2-2线性规划数学模型的一般形式,2023/11/4,3,资源合理利用问题：第5页例2-1,1.决策变量：x1和x2 2.目标函数：max(2 x1+3 x2)3.约束条件：10 x1+20 x2 80 4 x1 16 6 x2 18 x1，x2 0,2023/11/4,4,质量检验问题：第6页例2-2,1.

2、决策变量：x1和x2 2.目标函数：min(40 x1+36 x2)3.约束条件：5 x1+3 x2 45 x1 8 x2 10 x1，x2 0,2023/11/4,5,线性规划数学模型的一般形式,1.决策变量是非负变量；2.目标函数是线性函数；3.约束条件是线性等式或不等式组。一般形式为：max(min)(c1 x1+c2 x2+cn xn)a11 x1+a12 x2+a1n xn(=,)b1 a21 x1+a22 x2+a2n xn(=,)b2 am1 x1+am2 x2+amn xn(=,)bm x1，x2，xn 0,2023/11/4,6,线性规划的图解法,1.局限性：只能求解具有两个

3、变量的线性规划问题。2.学习目的：图解法只能求解具有两个决策变量的线性规划问题，其应用具有很大的局限性，因此学习图解法的目的并非是要掌握一种线性规划问题的求解方法，而是要通过图解法揭示线性规划问题的内在规律，为学习线性规划问题的一般算法（单纯形法）奠定基础。3.线性规划有关解的几个概念4.图解法的基本步骤5.图解法所反映出的一般结论,2023/11/4,7,线性规划有关解的几个概念,1.可行解：满足约束条件的一组决策变量的取值；2.可行域：可行解所构成的集合；3.最优解：使目标函数达到极值的可行解；4.最优值：与最优解相对应的目标函数的取值。,2023/11/4,8,图解法的基本步骤,1.画出

4、平面直角坐标系；2.将约束条件逐一反映进平面直角坐标系，用标号和箭线表明约束条件的顺序和不等号的方向；3.找出可行域并反映出目标函数直线的斜率；4.平移目标函数直线找出最优解。5.例题：第7页例2-3：用图解法求解例2-1 6.习题：第8页例2-4：用图解法求解例2-2,2023/11/4,9,用图解法求解例2-1,x1,x243210,1 2 3 4 5 6 7 8,2023/11/4,10,用图解法求解例2-1,x1,x243210,1 2 3 4 5 6 7 8,2023/11/4,11,用图解法求解例2-1,x1,x243210,1 2 3 4 5 6 7 8,2023/11/4,12

5、,用图解法求解例2-1,x1,x243210,1 2 3 4 5 6 7 8,2023/11/4,13,用图解法求解例2-1,x1,x243210,1 2 3 4 5 6 7 8,2023/11/4,14,用图解法求解例2-1,x1,x243210,1 2 3 4 5 6 7 8,2023/11/4,15,用图解法求解例2-1,x1,x243210,1 2 3 4 5 6 7 8,2023/11/4,16,用图解法求解例2-2,x1,x2,5 10 15,151050,2023/11/4,17,图解法所反应出的一般结论,1.线性规划问题的可行域是凸多边形；2.如果线性规划问题有最优解，其最优解

6、一定可以在其可行域的顶点上得到，而不会在可行域的内部；3.如果线性规划问题在其可行域的两个顶点上得到最优解，那么两顶点连线上的所有点均为最优解点；4.线性规划问题的解可能有四种情况：唯一最优解；无穷多最优解；无界解和无可行解。,2023/11/4,18,线形规划问题的标准形式,1.标准形式的基本条件：（1）决策变量非负；（2）目标函数极大化（或极小化）；（3）约束条件为严格等式，且右端项非负。2.标准形式的表示：代数式；和式；向量式；矩阵式 3.标准形式的转化,2023/11/4,19,线性规划的标准型：代数式,min z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1

7、 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0 j=1,2,n,2023/11/4,20,线性规划的标准型：和式,min z=cjxj aijxj=bi i=1,2,m xj 0 j=1,2,n,j=1,n,n,j=1,2023/11/4,21,线性规划的标准型：向量式,min z=CX pjxj=bi i=1,2,m xj 0 j=1,2,n C=(c1,c2,c3,cn)X=(X1,X2,X3,Xn)T,n,j=1,2023/11/4,22,线性规划的标准型：矩阵式,min z=CX AX=b，X 0，b 0 其中：b=(b1,b2,bm)T

8、 a11 a12.a1n A=a21 a22 a2n am1 am2 amn,2023/11/4,23,标准形式的转化,1.无约束变量x的处理：x=y-z,其中y,z02.负数变量x的处理：x=-y,其中y03.目标函数极小化的处理：Min CX=-Max(-CX)4.非等式约束条件的处理：加松弛变量或减剩余变量5.右端项为负：两端同乘“-1”,2023/11/4,24,线形规划的解集特征,1.线性规划基与解的概念(1)基、基列、基变量和非基变量(2)基解、基可行解和可行基2.凸集的概念与解集的基本定理(1)凸集的概念(2)解集的基本定理,2023/11/4,25,线性规划基与解的概念,1.基

9、、基列、基变量和非基变量(1)基：Max CX,AX=b,X0,b0 Amn其秩为m，B 是 Amn中的一个mm阶满秩矩阵，则称B是线 性规划问题的一个基(2)基列：基 B 中所包含的m个列向量(3)基变量：基列所对应的决策变量(4)非基变量：基变量以外的决策变量2.基解、基可行解、可行基(1)基解：令所有的非基变量为零，所求得的一组解(2)基可行解：所有分量均为非负的基解(3)可行基：与基可行解所对应的基,2023/11/4,26,凸集的概念与解集的基本定理,1.凸集的概念：设 K 是 n 维欧氏空间的一点集，若任意两点 X(1)k，X(2)k 的连线上的一切点 X(1)+(1-)X(2)k

10、，(0 1)则称 k 为凸集。2.解集的基本定理：(1)若线性规划问题存在可行域，则其可行域是凸集；(2)线性规划问题的基可行解对应其可行域的顶点；(3)若线性规划问题存在最优解，则其最优解一定能在基可行解中找到。,2023/11/4,27,线性规划的单纯形法,1.单纯形法的基本原理(1)单纯形法的基本思路(2)第12页例2-62.最优性检验与解的判别3.单纯形表4.单纯形法的基本步骤5.用单纯形法求解例2-66.课上习题,2023/11/4,28,单纯形法的基本思路,1.找出一个初始的基可行解；2.判断其最优性；3.转移至另一个较优的基可行解；4.重复2、3两步直至最优。,2023/11/4

11、,29,第12页例2-6,Max z=2x1+3x2 10 x1+20 x2+x3=80 4x1+x4=16 6x2+x5=18 x1，x2，x3，x4，x5 0B=(p3，p4，p5)X(0)=(0，0，80，16，18)T Z(0)=0，z=2x1+3x2寻找相邻的基可行解,2023/11/4,30,例2-6,Max(2，3)=3 x2入基Min(80/20，18/6)=3 x5出基B=(p3，p4，p2)10 x1+x3-10/3 x5=20 4x1+x4=16 x2+1/6 x5=3X(1)=(0，3，20，16，0)T Z(1)=9，z=9+2x1-1/2 x5,2023/11/4,

12、31,例2-6,Max(2)=2 x1入基Min(20/10，16/4)=2 x3出基B=(p1，p4，p2)x1+1/10 x3-1/3 x5=2-2/5 x3+x4+4/3 x5=8 x2+1/6 x5=3X(2)=(2，3，0，8，0)T Z(2)=13，z=13-1/5 x3+1/6 x5,2023/11/4,32,例2-6,Max(1/6)=1/6 x5入基Min(8/(4/3)，3/(1/6)=6 x4出基B=(p1，p5，p2)x1+1/4 x 4=4-3/10 x3+3/4 x4+x5=6 x2+1/20 x3-1/8 x4=2X(3)=(4，2，0，0，6)T Z(3)=14

13、，z=14-9/10 x3-1/8 x4,2023/11/4,33,最优性检验与解的判别,2023/11/4,34,单纯形表,2023/11/4,35,单纯形法的基本步骤,1.数学模型标准化、正规化；2.建立初始单纯形表；3.计算检验数并判断最优性，结束或继续；4.确定入基变量和出基变量，5.迭代运算；6.重复3、4、5步，直至结束。,2023/11/4,36,用单纯形法求解例2-6,2023/11/4,37,用单纯形法求解例2-6,2023/11/4,38,用单纯形法求解例2-6,2023/11/4,39,用单纯形法求解例2-6,2023/11/4,40,课上习题,1.Max z=2x1+4

14、x2+x3+x4 x1+3x2+x4 8 2x1+x2 6 x2+x3+x4 6 x1+x2+x3 9 x14 02.第17页例2-103.第19页例2-11,2023/11/4,41,单纯形法的进一步讨论,1.计算问题(1)入基变量的选择(2)解的退化2.人工变量与初始正规基(1)大M法(2)两阶段法,2023/11/4,42,入基变量的选择,入基变量是根据最大正检验数来选择的，这样做的目的是为了使目标函数得到最大的增量，因此当最大正检验数有多个时，可主观地选择它们中的任意一个作为入基变量。其实具有正检验数的所有非基变量都可作为入基变量。,2023/11/4,43,出基变量的选择与解的退化,

15、1.退化解：部分基变量的值为零的基可行解称为退化解。2.在选择出基变量时，如果最小比值不唯一，可主观确定出基变量，此时产生退化解。3.例,2023/11/4,44,例,Max z=2x4+(3/2)x6 x1+x4-x5=8 x2+2 x4+x6=4 x3+x4+x5+x6=3 x16 0,2023/11/4,45,例,2023/11/4,46,例,2023/11/4,47,例,2023/11/4,48,例,2023/11/4,49,例,2023/11/4,50,人工变量与初始正规基,第21页例2-13:Min z=-3x1+x2+x3 x1-2x2+x3 11-4x1+x2+2x3 3 2x

16、1-x3=-1 x1，x2，x3 0(1)标准化,2023/11/4,51,例2-13的标准化,Min z=-3x1+x2+x3 x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1 x15 0(2)正规化,2023/11/4,52,例2-13的正规化,人工变量：为构造基变量（正规基）人为加入的变量 x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1 x17 0初始正规基 B=(p4,p6,p7)=E,2023/11/4,53,大M法,1.大M法：令人工变量的价值系数为“-M”(极大值)或“M”(极小值)的单纯形法即称为大M

17、法；例如：Min z=-3x1+x2+x3+M x人1+M x人2 Max z=2x1+x2+4x3-M x人1+M x人22.例2-13的大M法3.习题（大M法）,2023/11/4,54,用大M法求解例2-13,Min z=-3x1+x2+x3 x1-2x2+x3 11-4x1+x2+2x3 3 2x1-x3=-1 x1，x2，x3 0,2023/11/4,55,用大M法求解例1.13,Min z=-3x1+x2+x3+Mx6+Mx7 x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1 x17 0,2023/11/4,56,用大M法求解例1.13,

18、2023/11/4,57,用大M法求解例1.13,2023/11/4,58,用大M法求解例1.13,2023/11/4,59,用大M法求解例1.13,2023/11/4,60,习题（用大M法求解）,Max z=2x1+4x2+x3 x1+x2+x3 6 x1+x2-2x3 4 x1-2x2+x3 8 x1，x2，x3 0,2023/11/4,61,习题（用大M法求解）,Max z=2x1+4x2+x3-Mx7 x1+x2+x3+x4=6 x1+x2-2x3+x 5=4 x1-2x2+x3-x6+x7=8 x17 0,2023/11/4,62,习题（用大M法求解）,2023/11/4,63,习题

19、（用大M法求解）,2023/11/4,64,习题（用大M法求解）,2023/11/4,65,两阶段法,1.两阶段法：第一阶段，在原约束条件下，求所有人工变量和的最小值；第一阶段的目的是获得问题的一个初始基可行解（人工变量和的最小值为零）或得出问题无可行解（人工变量和的最小值大于零）的结论；第二阶段，去掉人工变量，在原目标下从已得到的基可行解开始优化。2.例2-13的两阶段法3.习题（两阶段法）,2023/11/4,66,用两阶段法求解例2-13,Min z=-3x1+x2+x3 x1-2x2+x3 11-4x1+x2+2x3 3 2x1-x3=-1 x1，x2，x3 0,2023/11/4,6

20、7,用两阶段法求解例2-13,第一阶段：Min z=x6+x7 x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1 x17 0,2023/11/4,68,用两阶段法求解例2-13,2023/11/4,69,用两阶段法求解例2-13,2023/11/4,70,用两阶段法求解例2-13,2023/11/4,71,用两阶段法求解例2-13,2023/11/4,72,用两阶段法求解例2-13,2023/11/4,73,习题（用两阶段法求解）,Max z=2x1+4x2+x3 x1+x2+x3 6 x1+x2-2x3 4 x1-2x2+x3 8 x1，x2，x3 0,2023/11/4,74,习题（用两阶段法求解）,第一阶段：Min z=x7 x1+x2+x3+x4=6 x1+x2-2x3+x 5=4 x1-2x2+x3-x6+x7=8 x17 0,2023/11/4,75,习题（用两阶段法求解）,2023/11/4,76,习题（用两阶段法求解）,2023/11/4,77,习题（用两阶段法求解）,