新编管理运筹学02线性规划课件.ppt

1、2022-8-131s 1.线性规划问题及其数学模型s 2.线性规划的图解法s 3.线性规划问题的标准形式s 4.线性规划的解集特征s 5.线性规划的单纯形法s 6.单纯形法的进一步讨论2022-8-132线性规划问题及其数学模型w资源合理利用问题：第5页例2-1w质量检验问题：第6页例2-2w线性规划数学模型的一般形式2022-8-133资源合理利用问题：第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 02022-8-134 质量检验问题：第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 02022-8-135线性规划数学模型的一般形式 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 2022-8-136 线性规划的图解法w 1.局限性：只能求解具有两个变量的线性

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

4、2-8-138图解法的基本步骤 1.画出平面直角坐标系；2.将约束条件逐一反映进平面直角坐标系，用标号和箭线表明约束条件的顺序和不等号的方向；3.找出可行域并反映出目标函数直线的斜率；4.平移目标函数直线找出最优解。5.例题：第7页例2-3：用图解法求解例2-1 6.习题：第8页例2-4：用图解法求解例2-2 2022-8-139用图解法求解例2-1x1x2432101 2 3 4 5 6 7 82022-8-1310用图解法求解例2-1x1x2432101 2 3 4 5 6 7 82022-8-1311用图解法求解例2-1x1x2432101 2 3 4 5 6 7 82022-8-131

5、2用图解法求解例2-1x1x2432101 2 3 4 5 6 7 82022-8-1313用图解法求解例2-1x1x2432101 2 3 4 5 6 7 82022-8-1314用图解法求解例2-1x1x2432101 2 3 4 5 6 7 82022-8-1315用图解法求解例2-1x1x2432101 2 3 4 5 6 7 82022-8-1316用图解法求解例2-2x1x2 5 10 151510502022-8-1317图解法所反应出的一般结论w 1.线性规划问题的可行域是；w 2.如果线性规划问题有最优解，其最优解一定可以在其可行域的顶点上得到，而不会在可行域的内部；w 3.

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

7、am2x2+amnxn=bm xj 0 j=1,2,n 2022-8-1320线性规划的标准型：和式 min z=cjxj aijxj=bi i=1,2,m xj 0 j=1,2,nj=1nnj=12022-8-1321线性规划的标准型：向量式 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)Tnj=12022-8-1322线性规划的标准型：矩阵式 min z=CX AX=b，X 0，b 0 其中：b=(b1,b2,bm)T a11 a12.a1n A=a21 a22 a2n am1 am2 amn2022

8、-8-1323标准形式的转化w 1.无约束变量x的处理：x=y-z,其中y,z0w 2.负数变量x的处理：x=-y,其中y0w 3.目标函数极小化的处理：Min CX=-Max(-CX)w 4.非等式约束条件的处理：加松弛变量或减剩余变量w 5.右端项为负：两端同乘“-1”2022-8-1324线形规划的解集特征w 1.线性规划基与解的概念 (1)基、基列、基变量和非基变量 (2)基解、基可行解和可行基w 2.凸集的概念与解集的基本定理 (1)凸集的概念 (2)解集的基本定理2022-8-1325线性规划基与解的概念w 1.基、基列、基变量和非基变量 (1)基基：Max CX,AX=b,X0,

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

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

11、步直至最优。2022-8-1329第12页例2-6Max 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寻找相邻的基可行解2022-8-1330例2-6Max(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+2

12、x1-1/2 x52022-8-1331例2-6Max(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 x52022-8-1332例2-6Max(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)=

13、(4，2，0，0，6)T Z(3)=14，z=14-9/10 x3-1/8 x42022-8-1333最优性检验与解的判别2022-8-1334单纯形表2022-8-1335单纯形法的基本步骤w 1.数学模型标准化、正规化；w 2.建立初始单纯形表；w 3.计算检验数并判断最优性，结束或继续；w 4.确定入基变量和出基变量，w 5.迭代运算；w 6.重复3、4、5步，直至结束。2022-8-1336用单纯形法求解例2-6 表 1 cj2 3 0 0 0CBXBx1 x2 x3 x4 x5 b000 x3x4x510 20 1 0 0 4 0 0 1 0 0 6 0 0 1 80 16 18 2

14、 3 0 0 0 Z=02022-8-1337用单纯形法求解例2-62022-8-1338用单纯形法求解例2-62022-8-1339用单纯形法求解例2-6 表 4 cj2 3 0 0 0CBXBx1 x2 x3 x4 x5 b203x1x5x21 0 0 1/4 00 0 -3/10 3/4 10 1 1/20 -1/8 0 4 6 2 0 0 -3/20 -1/8 0 Z=142022-8-1340课上习题1.Max z=2x1+4x2+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

15、2022-8-1341单纯形法的进一步讨论1.计算问题 (1)入基变量的选择 (2)解的退化2.人工变量与初始正规基 (1)大M法 (2)两阶段法2022-8-1342入基变量的选择 入基变量是根据最大正检验数最大正检验数来选择的，这样做的目的是为了使目标函数得到最大的增量，因此当最大正检验数有多个时，可主观地选择它们中的任意一个作为入基变量。其实具有正检验数的所有非基变量都可作为入基变量。2022-8-1343出基变量的选择与解的退化w 1.退化解：部分基变量的值为零的基可行解称为退化解。w 2.在选择出基变量时，如果最小比值不唯一，可主观确定出基变量，此时产生退化解。w 3.例2022-8

16、-1344例Max z=2x4+(3/2)x6 x1 +x4 -x5 =8 x2 +2 x4 +x6=4 x3+x4 +x5+x6=3 x16 02022-8-1345例 表 1 cj 0 0 0 2 0 3/2CBXB x1 x2 x3 x4 x5 x6b000 x1x2x3 1 0 0 1 -1 0 0 1 0 2 0 1 0 0 1 1 1 1 2 4 3 0 0 0 2 0 3/22022-8-1346例 表 2 cj 0 0 0 2 0 3/2CBXB x1 x2 x3 x4 x5 x6b200 x4x2x3 1 0 0 1 -1 0-2 1 0 0 2 1-1 0 1 0 2 1

17、2 0 1 -2 0 0 0 2 3/22022-8-1347例 表 3 cj 0 0 0 2 0 3/2CBXB x1 x2 x3 x4 x5 x6b200 x4x5x3 0 1/2 0 1 0 1/2-1 1/2 0 0 1 1/2-1 -1 1 0 0 0 2 0 1 0 -1 0 0 0 1/22022-8-1348例 表 4 cj 0 0 0 2 0 3/2CBXB x1 x2 x3 x4 x5 x6b23/20 x4x6x3 1 0 0 1 -1 0-2 1 0 0 2 1 1 -1 1 0 0 0 2 0 1 1 -3/2 0 0 -1 02022-8-1349例 表 5 cj

18、0 0 0 2 0 3/2CBXB x1 x2 x3 x4 x5 x6b 03/2 0 x4x6x1 0 1 -1 1 -1 0 0 -1 2 0 2 1 1 -1 1 0 0 0 1 2 1 0 -1/2 -1 0 -1 02022-8-1350人工变量与初始正规基第第21页例页例2-13:Min z=-3x1+x2+x3 x1 -2x2+x3 11 -4x1 +x2+2x3 3 2x1 -x3 =-1 x1 ，x2，x3 0(1)标准化2022-8-1351例2-13的标准化 Min z=-3x1+x2+x3 x1 -2x2+x3+x4 =11 -4x1 +x2+2x3 -x5=3 -2x

19、1 +x3 =1 x15 0(2)正规化2022-8-1352例2-13的正规化人工变量人工变量：为构造基变量（正规基）人为加入的变量 x1 -2x2+x3+x4 =11 -4x1 +x2+2x3-x5+x6 =3 -2x1 +x3 +x7=1 x17 0初始正规基 B=(p4,p6,p7)=E2022-8-1353大M法1.大M法：令人工变量的价值系数为“-M”(极大值)或“M”(极小值)的单纯形法即称为大M法；例如：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法）2022-8-

20、1354用大M法求解例2-13 Min z=-3x1+x2+x3 x1 -2x2+x3 11 -4x1 +x2+2x3 3 2x1 -x3 =-1 x1 ，x2，x3 02022-8-1355用大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 02022-8-1356用大M法求解例1.13 表 1 cj-3 1 1 0 0 M MCBXBx1 x2 x3 x4 x5 x6 x7b0MMx4x6x7 1 -2 1 1 0 0 0-4 1 2 0 -1 1

21、 0-2 0 1 0 0 0 111 3 1 -3+6M 1-M 1-3M 0 M 0 02022-8-1357用大M法求解例1.13 表 2 cj-3 1 1 0 0 M MCBXB x1 x2 x3 x4 x5 x6 x7b0M1x4x6x3 3 -2 0 1 0 0 -1 0 1 0 0 -1 1 -2-2 0 1 0 0 0 110 1 1 -1 1-M 0 0 M 0 3M-12022-8-1358用大M法求解例1.13 表 3 cj-3 1 1 0 0 M MCBXBx1 x2 x3 x4 x5 x6 x7b011x4x2x3 3 0 0 1 -2 2 -5 0 1 0 0 -1

22、1 -2-2 0 1 0 0 0 112 1 1 -1 0 0 0 1 M-1 M+12022-8-1359用大M法求解例1.13 表 4 cj-3 1 1 0 0 M MCBXBx1 x2 x3 x4 x5 x6 x7b-311x1x2x31 0 0 1/3 -2/3 2/3 -5/30 1 0 0 -1 1 -20 0 1 2/3 -4/3 4/3 -7/3 4 1 9 0 0 0 1/3 1/3 M-1/3 M-2/32022-8-1360习题（用大M法求解）Max z=2x1+4x2+x3 x1 +x2 +x3 6 x1 +x2 -2x3 4 x1 -2x2+x3 8 x1 ，x2，x

23、3 02022-8-1361习题（用大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 02022-8-1362习题（用大M法求解）表 1 cj 2 4 1 0 0 0 -MCBXBx1 x2 x3 x4 x5 x6 x7b 0 0-Mx4x5x7 1 1 1 1 0 0 0 1 1 -2 0 1 0 0 1 -2 1 0 0 -1 1 6 4 8 2+M 4-2M 1+M 0 0 -M 02022-8-1363习题（用大M法求解）表 2 cj 2 4 1 0 0 0

24、-MCBXB x1 x2 x3 x4 x5 x6 x7b 0 2-Mx4x1x7 0 0 3 1 -1 0 0 1 1 -2 0 1 0 0 0 -3 3 0 -1 -1 1 2 4 4 0 2-3M 5+3M 0 -2-M -M 02022-8-1364习题（用大M法求解）表 3 cj 2 4 1 0 0 0 -MCBXB x1 x2 x3 x4 x5 x6 x7b 1 2-Mx3x1x7 0 0 1 1/3 -1/3 0 0 1 1 0 2/3 1/3 0 0 0 -3 0 -1 0 -1 1 2/3 16/3 2 0 2-3M 0 -3/5-M -1/3 -M 02022-8-1365两

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

26、x4 =11 -4x1 +x2 +2x3 -x5+x6 =3 -2x1 +x3 +x7=1 x17 02022-8-1368用两阶段法求解例2-132022-8-1369用两阶段法求解例2-13 表 2（第一阶段）cj 0 0 0 0 0 1 1CBXB x1 x2 x3 x4 x5 x6 x7b010 x4x6x3 3 -2 0 1 0 0 -1 0 1 0 0 -1 1 -2-2 0 1 0 0 0 110 1 1 0 -1 0 0 1 0 32022-8-1370用两阶段法求解例2-13 表 3（第一阶段）cj 0 0 0 0 0 1 1CBXB x1 x2 x3 x4 x5 x6 x7

27、b000 x4x2x3 3 0 0 1 -2 2 -5 0 1 0 0 -1 1 -2-2 0 1 0 0 0 112 1 1 0 0 0 0 0 0 12022-8-1371用两阶段法求解例2-13 表 4（第二阶段）cj-3 1 1 0 0CBXB x1 x2 x3 x4 x5b011x4x2x3 3 0 0 1 -2 0 1 0 0 -1-2 0 1 0 012 1 1 -1 0 0 0 12022-8-1372用两阶段法求解例2-13 表 5（第二阶段）cj-3 1 1 0 0CBXB x1 x2 x3 x4 x5b-311x1x2x3 1 0 0 1/3 -2/3 0 1 0 0 -

28、1 0 0 1 2/3 -4/3 4 1 9 0 0 0 1/3 1/32022-8-1373习题（用两阶段法求解）Max z=2x1+4x2+x3 x1 +x2 +x3 6 x1 +x2 -2x3 4 x1 -2x2+x3 8 x1 ，x2，x3 02022-8-1374习题（用两阶段法求解）第一阶段：Min z=x7 x1 +x2 +x3+x4 =6 x1 +x2 -2x3 +x 5 =4 x1 -2x2+x3 -x6+x7 =8 x17 02022-8-1375习题（用两阶段法求解）表 1 cj 0 0 0 0 0 0 1CBXB x1 x2 x3 x4 x5 x6 x7b 0 0 1x

29、4x5x7 1 1 1 1 0 0 0 1 1 -2 0 1 0 0 1 -2 1 0 0 -1 1 6 4 8 -1 2 -1 0 0 1 02022-8-1376习题（用两阶段法求解）表 2 cj 0 0 0 0 0 0 1CBXB x1 x2 x3 x4 x5 x6 x7b 0 0 1x4x1x7 0 0 3 1 -1 0 0 1 1 -2 0 1 0 0 0 -3 3 0 -1 -1 1 2 4 4 0 3 -3 0 1 1 02022-8-1377习题（用两阶段法求解）表3 cj 0 0 0 0 0 0 1CBXB x1 x2 x3 x4 x5 x6 x7 b 0 0 1x3x1x7 0 0 1 1/3 -1/3 0 0 1 1 0 2/3 1/3 0 0 0 -3 0 -1 0 -1 1 2/3 16/3 2 0 3 0 1 0 1 0