《管理运筹学02线性规划》由会员分享，可在线阅读，更多相关《管理运筹学02线性规划（77页珍藏版）》请在金锄头文库上搜索。
1、s1. 线性规划问题及其数学模型s2. 线性规划的图解法s3. 线性规划问题的标准形式s4. 线性规划的解集特征s5. 线性规划的单纯形法s6. 单纯形法的进一步讨论8/22/20241线性规划问题及其数学模型w资源合理利用问题：第5页例2-1w质量检验问题：第6页例2-2w线性规划数学模型的一般形式8/22/20242资源合理利用问题：第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 08/22/20243 质量检验问题：第6页例2-2 1.决策变量：x1和x2
2、 2.目标函数：min(40 x1+36 x2) 3.约束条件：5 x1+3 x2 45 x1 8 x2 10 x1，x2 08/22/20244线性规划数学模型的一般形式 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 8/22/20245 线性规
3、划的图解法w1.局限性：只能求解具有两个变量的线性规划问题。w2.学习目的：图解法图解法只能求解具有两个决策变量的线性规划问题，其应用具有很大的局限性，因此学习图解法的目的并非是要掌握一种线性规划问题的求解方法，而是要通过图解法揭示线性规划问题的内在规律内在规律，为学习线性规划问题的一般算法（单纯形法单纯形法）奠定基础。w3.线性规划有关解的几个概念w4.图解法的基本步骤w5.图解法所反映出的一般结论8/22/20246线性规划有关解的几个概念 1. 可行解可行解：满足约束条件的一组决策变量的取值； 2. 可行域可行域：可行解所构成的集合； 3. 最优解最优解：使目标函数达到极值的可行解； 4
4、. 最优值最优值：与最优解相对应的目标函数的取值。8/22/20247图解法的基本步骤 1.画出平面直角坐标系； 2.将约束条件逐一反映进平面直角坐标系，用标号和箭线表明约束条件的顺序和不等号的方向； 3.找出可行域并反映出目标函数直线的斜率； 4.平移目标函数直线找出最优解。 5.例题：第7页例2-3：用图解法求解例2-1 6.习题：第8页例2-4：用图解法求解例2-2 8/22/20248用图解法求解例2-1x1x2432101 2 3 4 5 6 7 88/22/20249用图解法求解例2-1x1x2432101 2 3 4 5 6 7 88/22/202410用图解法求解例2-1x1x
5、2432101 2 3 4 5 6 7 88/22/202411用图解法求解例2-1x1x2432101 2 3 4 5 6 7 88/22/202412用图解法求解例2-1x1x2432101 2 3 4 5 6 7 88/22/202413用图解法求解例2-1x1x2432101 2 3 4 5 6 7 88/22/202414用图解法求解例2-1x1x2432101 2 3 4 5 6 7 88/22/202415用图解法求解例2-2x1x2 5 10 151510508/22/202416图解法所反应出的一般结论w1.线性规划问题的可行域是凸多边形凸多边形凸多边形凸多边形；w2.如果线
6、性规划问题有最优解，其最优解一定可以在其可行域的顶点上得到，而不会在可行域的内部；w3.如果线性规划问题在其可行域的两个顶点上得到最优解，那么两顶点连线上的所有点均为最优解点；w4.线性规划问题的解可能有四种情况：唯一最优解；无穷多最优解；无界解和无可行解。8/22/202417线形规划问题的标准形式w1. 标准形式的基本条件：（1）决策变量非负；（2）目标函数极大化（或极小化）；（3）约束条件为严格等式，且右端项非负。w2. 标准形式的表示： 代数式；和式；向量式；矩阵式 w3. 标准形式的转化8/22/202418线性规划的标准型：代数式 min z =c1x1+c2x2+cnxn a11
7、x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0 j =1,2,n 8/22/202419线性规划的标准型：和式 min z =cjxj aijxj=bi i=1,2,m xj 0 j=1,2,nj=1nnj=18/22/202420线性规划的标准型：向量式 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=18/22/202421线性规划的标准型：矩阵式 min z =CX AX=b，X 0 ， b 0 其中：
8、b=(b1,b2,bm)T a11 a12 .a1n A= a21 a22 a2n am1 am2 amn8/22/202422标准形式的转化w1.无约束变量x的处理： x=y-z, 其中y,z0w2.负数变量x的处理： x=-y,其中y0w3.目标函数极小化的处理： Min CX=- Max(-CX)w4.非等式约束条件的处理： 加松弛变量或减剩余变量w5.右端项为负：两端同乘“-1”8/22/202423线形规划的解集特征w1.线性规划基与解的概念 (1)基、基列、基变量和非基变量 (2)基解、基可行解和可行基w2.凸集的概念与解集的基本定理 (1)凸集的概念 (2)解集的基本定理8/22
9、/202424线性规划基与解的概念w1.基、基列、基变量和非基变量 (1) 基基： Max CX, AX=b, X0, b0 Amn其秩为m，B 是 Amn中的一个mm阶满秩矩阵，则称B是线 性规划问题的一个基基 (2) 基列基列：基 B 中所包含的m个列向量 (3) 基变量基变量：基列所对应的决策变量 (4) 非基变量非基变量：基变量以外的决策变量w2.基解、基可行解、可行基 (1) 基解基解：令所有的非基变量为零，所求得的一组解 (2) 基可行解基可行解：所有分量均为非负的基解基解 (3) 可行基可行基：与基可行解基可行解所对应的基基8/22/202425凸集的概念与解集的基本定理w1.凸
10、集的概念：设 K 是 n 维欧氏空间的一点集，若任意两点 X(1) k，X(2) k 的连线上的一切点 X(1) + (1-) X(2) k，(0 1) 则称 k 为凸集。w2.解集的基本定理： (1) 若线性规划问题存在可行域，则其可行域是凸集； (2) 线性规划问题的基可行解对应其可行域的顶点； (3) 若线性规划问题存在最优解，则其最优解一定能在基可行解中找到。8/22/202426线性规划的单纯形法w1.单纯形法的基本原理 (1) 单纯形法的基本思路 (2) 第12页例2-6w2.最优性检验与解的判别w3.单纯形表w4.单纯形法的基本步骤w5.用单纯形法求解例2-6w6.课上习题8/2
11、2/202427单纯形法的基本思路w1. 找出一个初始的基可行解；w2. 判断其最优性；w3. 转移至另一个较优的基可行解；w4. 重复2、3两步直至最优。8/22/202428第12页例2-6Max z = 2x1 + 3x2 10x1 + 20x2 + 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寻找相邻的基可行解8/22/202429例2-6Max (2，3) = 3 x2入基Min (80/20，18/
12、6) = 3 x5出基B = (p3，p4，p2) 10x1 + 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 x58/22/202430例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，
13、z = 13 - 1/5 x3 + 1/6 x58/22/202431例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) = (4，2，0，0，6)T Z(3) = 14，z = 14 - 9/10 x3 - 1/8 x48/22/202432最优性检验与解的判别8/22/202433单纯形表8/22/202434单纯形法的基本步骤w1.数学模型标准化、正规化；w
14、2.建立初始单纯形表；w3.计算检验数并判断最优性，结束或继续；w4.确定入基变量和出基变量，w5.迭代运算；w6.重复3、4、5步，直至结束。8/22/202435用单纯形法求解例2-68/22/202436用单纯形法求解例2-68/22/202437用单纯形法求解例2-68/22/202438用单纯形法求解例2-68/22/202439课上习题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-118/22/202440
15、单纯形法的进一步讨论1. 计算问题 (1) 入基变量的选择 (2) 解的退化2. 人工变量与初始正规基 (1) 大M法 (2) 两阶段法8/22/202441入基变量的选择 入基变量是根据最大正检验数最大正检验数来选择的，这样做的目的是为了使目标函数得到最大的增量，因此当最大正检验数有多个时，可主观地选择它们中的任意一个作为入基变量。其实具有正检验数的所有非基变量都可作为入基变量。8/22/202442出基变量的选择与解的退化w1. 退化解：部分基变量的值为零的基可行解称为退化解。w2. 在选择出基变量时，如果最小比值不唯一，可主观确定出基变量，此时产生退化解。w3. 例8/22/202443
16、例Max z =2x4 +(3/2)x6 x1 + x4 - x5 = 8 x2 + 2 x4 + x6 = 4 x3 + x4 + x5 + x6 = 3 x16 08/22/202444例8/22/202445例8/22/202446例8/22/202447例8/22/202448例8/22/202449人工变量与初始正规基第第21页例页例2-13: Min z = -3x1 + x2 + x3 x1 - 2x2 + x3 11 -4x1 + x2 + 2x3 3 2x1 - x3 = -1 x1 ， x2 ， x3 0(1)标准化8/22/202450例2-13的标准化 Min z =
17、-3x1 + x2 + x3 x1 - 2x2 + x3 + x4 = 11 -4x1 + x2 + 2x3 - x5 = 3 -2x1 + x3 = 1 x15 0(2)正规化8/22/202451例2-13的正规化人工变量人工变量：为构造基变量（正规基）人为加入的变量 x1 - 2x2 + x3 + x4 = 11 -4x1 + x2 + 2x3 - x5 + x6 = 3 -2x1 + x3 + x7 = 1 x17 0初始正规基 B= (p4, p6, p7) = E8/22/202452大M法1. 大M法：令人工变量的价值系数为“-M” (极大值)或 “M” (极小值)的单纯形法即称
18、为大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法）8/22/202453用大M法求解例2-13 Min z = -3x1 + x2 + x3 x1 - 2x2 + x3 11 -4x1 + x2 + 2x3 3 2x1 - x3 = -1 x1 ， x2 ， x3 08/22/202454用大M法求解例1.13 Min z = -3x1 + x2 + x3 + Mx6 + Mx7 x1 - 2x2 + x3 + x4 = 11 -
19、4x1 + x2 +2x3 - x5 + x6 = 3 -2x1 + x3 + x7 = 1 x17 08/22/202455用大M法求解例1.138/22/202456用大M法求解例1.138/22/202457用大M法求解例1.138/22/202458用大M法求解例1.138/22/202459习题（用大M法求解） Max z = 2x1 + 4x2 + x3 x1 + x2 + x3 6 x1 + x2 - 2x3 4 x1 - 2x2 + x3 8 x1 ， x2 ， x3 08/22/202460习题（用大M法求解） Max z = 2x1 + 4x2 + x3 - Mx7 x1
20、+ x2 + x3 + x4 = 6 x1 + x2 - 2x3 + x 5 = 4 x1 - 2x2 + x3 - x6 + x7 = 8 x17 08/22/202461习题（用大M法求解）8/22/202462习题（用大M法求解）8/22/202463习题（用大M法求解）8/22/202464两阶段法w1. 两阶段法：第一阶段，在原约束条件下，求所有人工变量和的最小值；第一阶段的目的是获得问题的一个初始基可行解（人工变量和的最小值为零）或得出问题无可行解（人工变量和的最小值大于零）的结论；第二阶段，去掉人工变量，在原目标下从已得到的基可行解开始优化。w2. 例2-13的两阶段法w3. 习
21、题（两阶段法）8/22/202465用两阶段法求解例2-13 Min z = -3x1 + x2 + x3 x1 - 2x2 + x3 11 -4x1 + x2 + 2x3 3 2x1 - x3 = -1 x1 ， x2 ， x3 08/22/202466用两阶段法求解例2-13第一阶段： Min z = x6 + x7 x1 - 2x2 + x3 + x4 = 11 -4x1 + x2 +2x3 - x5 + x6 = 3 -2x1 + x3 + x7 = 1 x17 08/22/202467用两阶段法求解例2-138/22/202468用两阶段法求解例2-138/22/202469用两阶段
22、法求解例2-138/22/202470用两阶段法求解例2-138/22/202471用两阶段法求解例2-138/22/202472习题（用两阶段法求解） Max z = 2x1 + 4x2 + x3 x1 + x2 + x3 6 x1 + x2 - 2x3 4 x1 - 2x2 + x3 8 x1 ， x2 ， x3 08/22/202473习题（用两阶段法求解）第一阶段： Min z = x7 x1 + x2 + x3 + x4 = 6 x1 + x2 - 2x3 + x 5 = 4 x1 - 2x2 + x3 - x6 + x7 = 8 x17 08/22/202474习题（用两阶段法求解）8/22/202475习题（用两阶段法求解）8/22/202476习题（用两阶段法求解）8/22/202477
