1.线性规划课件(PPT 95页)

1、运筹学管理科学与工程学院电子商务系刘承昕第1页，共95页。运筹学第一章 绪论第二章 线性规划（Linear Programming）第三章 对偶理论（Dual Theory）第四章 运输问题（Transportation Problem）第五章 整数规划（Integer Programming）第六章 图论（Graph Theory）第2页，共95页。第一章 绪论第3页，共95页。第一章 绪论一、运筹学的定义运用科学的方法研究管理和工程中各种决策问题，为决策者提供科学的决策依据的学科。二、运筹学的研究方法将实际问题定量化和模型化，运用数学、统计学、计算机科学和工程等学科的原理和技术研究各种组织

2、系统的管理问题和生产经营活动，以求得到一个合理的运用资源的最优方案，达到系统效益的最优化。第4页，共95页。第一章 绪论三、运筹学的工作步骤提出问题，并根据需要收集有关数据信息建立模型，引入决策变量，确定目标函数（约束条件）模型求解，获得最优或次优解检验模型和解的合理性，必要时修正根据最优方案提出管理建议帮助实施管理决策第5页，共95页。第二章 线性规划Linear Programming第6页，共95页。第1节 数学模型一、规划问题含义：如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。第7页，共95页。第1节 数学模型例1：用一块边长为a的正方形铁皮做一个容器，应该如何裁

3、剪，使做成的容器的容积最大（如下图所示）。ax第8页，共95页。第1节 数学模型例1：解：设在铁皮四个角上剪去四个边长各为x的正方形 V=(a-2x)(a-2x)xmax 满足 xa/2 x0第9页，共95页。第1节 数学模型例2：某企业计划生产、两种产品，都要分别在A，B，C，D四种不同设备上加工。按工艺资料规定，生产每件产品需占用各设备分别为2，1，4，0（小时），生产每件产品需占用各设备分别为2，2，0，4（小时）。已知各设备计划期内用于生产这两种产品的能力分别为12，8，16，12（小时），又知每生产一件产品，企业能获利2元，每生产一件产品 ，企业能获利3元。问：该企业应如何安排生产两

4、种产品各多少件，使企业的利润收入最大。第10页，共95页。第1节 数学模型例2：解：设、两种产品在计划期内的产量分别为x1、x2 z =2x1+3x2max 2x1+2x212 x1+2x28 满足 4x116 4x212 x1，x20第11页，共95页。第1节 数学模型特征（1）决策变量（2）约束条件（3）目标函数第12页，共95页。第1节 数学模型二、线性规划问题特征（三要素）（1）决策变量：问题中的未知量（2）目标函数：问题要达到的目标（最大或最小），表示为决策变量的线性函数（3）约束条件：表示为含决策变量的一组互不矛盾的线性等式或线性不等式的函数约束和决策变量的非负约束第13页，共95

5、页。第1节 数学模型线性规划问题数学模型的形式（1）一般形式第14页，共95页。第1节 数学模型（2）简写形式（3）向量形式 （4）矩阵形式第15页，共95页。第1节 数学模型例2：一般形式 矩阵形式 max z =2x1+3x2 2x1+2x212 x1+2x28 4x116 4x212 x1，x20第16页，共95页。第1节 数学模型三、线性规划数学模型的标准形式（标准型）目标函数求最大值函数约束条件全为等式决策变量全为非负函数约束条件右端项全为非负第17页，共95页。第1节 数学模型四、线性规划的非标准型如何转化为标准型目标函数求最小值：令z-z函数约束条件为不等式： ：在函数约束条件左

6、端加非负的松弛变量 ：在函数约束条件左端减非负的松弛变量 松弛变量在目标函数中的系数全为0决策变量为负值：令xj-xj， xj0决策变量取值无约束： 令xj xj- xj，xj0， xj0函数约束条件右端项（bi）为负值：函数约束条件两端同乘-1第18页，共95页。第1节 数学模型要求：将下列线性规划问题转化为标准型。例3：min z =x1+2x2+3x3 -2x1+x2+x39 -3x1+x2+2x34 3x1-2x2-3x3=-6 x10，x20，x3取值无约束第19页，共95页。第1节 数学模型例3：解：令 max z=x1-2x2-3x3+3x3+0 x4+0 x5 2x1+x2+x

7、3-x3+x4=9 3x1+x2+2x3-2x3-x5=4 3x1+2x2+3x3-3x3=6 x1，x2，x3，x3，x4，x50第20页，共95页。第1节 数学模型例4： min z =-x1+2x2-3x3 x1+x2+x37 x1-x2+x32 -3x1+x2+2x3=5 x1，x20，x3无约束第21页，共95页。第1节 数学模型例4：解：令 max z=x1-2x2-3x3+3x3 x1+x2+x3-x3+x4=7 x1-x2+x3-x3-x5=2 -3x1+x2+2x3-2x3=5 x1，x2，x3，x3，x4，x50第22页，共95页。第1节 数学模型例5： max z =2x

8、1+3x2+5x3 x1+x2-x3-5 -6x1+7x2-9x3=16 19x1-7x25x313 x1，x20，x3无约束第23页，共95页。第1节 数学模型例5：解：令 max z=2x1+3x2+5x3-5x3 -x1-x2+x3-x3+x4=5 -6x1+7x2-9x3+9x3=16 19x1-7x2+5x3-5x3+x5=13 -19x1+7x2-5x3+5x3+x6=13 x1，x2，x3，x3，x4，x5 ，x60第24页，共95页。作业1作业1：将下列线性规划问题化为标准型。1、min z =5x1-2x2+4x3-3x4 -x1+2x2-x3+4x4=-2 -x1+3x2+

9、x3+x414 2x1-x2+3x3-x42 x1无约束，x20，x3 ，x4 02、 min z =x1+2x2+4x3 2x1+x2+3x320 3x1+x2+4x325 x1，x20，x30第25页，共95页。作业1答案 1、 2、第26页，共95页。第2节 解一、线性规划问题解的概念可行解：满足函数约束条件和非负约束条件的解最优解：使目标函数达到最大值的可行解基：设A是约束方程组的mn阶系数矩阵，B是矩阵A中mm阶非奇异子矩阵，称B是线性规划问题的一个基基向量：基B中每一个列向量Pj非基向量：A中其余列向量Pj（不在B中）基变量：与基向量Pj对应的决策变量xj非基变量：与非基向量对应的

10、决策变量基解基可行解：满足非负约束条件的基解可行基：对应于基可行解的基第27页，共95页。第2节 解二、线性规划问题解的关系最优解第28页，共95页。第2节 解线性规划问题数学模型的标准形式（一般形式）第29页，共95页。第2节 解补充（复习）内容秩：设在矩阵A中一个不等于0的r阶子式D，且所有r1阶子式（如果存在的话）全等于0，那么D为矩阵A的最高阶非零子式，数r为矩阵A的秩。非奇异矩阵：行列式不等于0的矩阵。克莱姆法则：如果线性方程组 a11x1+a12x2+a1mxm=b1 a21x1+a22x2+a2mxm=b2 am1x1+am2x2+ammxm=bm 的系数行列式不等于0，则方程组

11、有唯一解。第30页，共95页。第2节 解例6：求下述线性规划的所有基解、基可行解及最优解。 max z =3x1+x2+3x3 x1+x2+x32 x1+2x2+4x36 x1，x2，x30第31页，共95页。作业2作业2：求下列线性规划的所有基解、基可行解及最优解。1、 max z =2x1+3x2+4x3+7x4 2x1+3x2-x3-4x48 -x1+2x2-6x3+7x43 x1，x2，x3 ，x402、 max z =-5x1+2x2-3x3+6x4 x1+2x2+3x3+4x47 2x1+x2+x3+2x43 x1，x2，x3 ，x40第32页，共95页。作业2答案1、 2、第33

12、页，共95页。第3节 图解法一、图解法适用条件：适用于求解只有两个决策变量的线性规划问题特点（1）不必将线性规划问题转化为标准型（2）直观性强，计算方便第34页，共95页。第3节 图解法例7：用图解法求解下述线性规划问题。 max z =2x1+3x2 x1+2x28 4x116 4x212 x1，x20第35页，共95页。第3节 图解法例7：标出约束条件(0,0)(0,3)(2,3)(4,2)(4,0)第36页，共95页。第3节 图解法例7：标出目标函数目标函数z第37页，共95页。第3节 图解法二、图解法的求解步骤建立 二维坐标系将约束条件表示在坐标系中，以确立可行域画出每个函数约束的约束

13、边界，用原点判断直线的哪一边是约束条件所允许的找出所有约束条件都同时满足的区域，即可行域将目标函数绘制在坐标系中，并标出变化的方向给定目标函数一个特定的值k，画出目标函数特定线，当k变化时，目标函数特定线将平行移动对于目标函数最大（小）化的问题，找出目标函数增加（减少）的方向，目标函数最后离开可行域的点是最优解确定最优解第38页，共95页。第3节 图解法三、图解法解的类型唯一最优解：仅有一点使目标函数值取得最大（小）值无穷多（多重）最优解：线段（射线）上任意一点都使目标函数值取得相同的最大（小）值无界解：可行域无界，目标函数值可以增大到无穷大无可行解：可行域为空集第39页，共95页。第3节 图

14、解法要求：用图解法求解下列线性规划问题。例8： max z =2x1+4x2 x1+2x28 4x116 4x212 x1，x20第40页，共95页。第3节 图解法例8：目标函数 max z=2x1+4x2 z第41页，共95页。第3节 图解法例9： max z =2x1+3x2 4x116 x1，x20第42页，共95页。第3节 图解法例10： max z =2x1+3x2 2x1+2x212 x1+2x214 x1，x20第43页，共95页。第3节 图解法四、图解法解的特点当可行域非空集时，可行域必是有界或无界凸多边形。（凸集：集合C中任意两个点a和b，其连线上所有点也必为集合C中的点。）

15、若可行域有界，则目标函数一定可以在可行域的顶点上达到最优；若可行域无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上达到。第44页，共95页。第3节 图解法线性规划问题的每个基可行解对应可行域的一个顶点，若线性规划问题有最优解，则必在顶点上达到。若有唯一最优解，则一定在可行域的顶点处得到；若有两个顶点同时达到最优解，则两个顶点之间线段上的任意一点都是最优解，既有无穷多最优解。线性规划问题有最优解，则解题思路：找出可行域的顶点，计算顶点处的目标函数值，比较各顶点的目标函数值，值最大（小）的顶点为最优解的点或最优解的点之一。第45页，共95页。第3节 图解法例11：下列哪一个图是凸集？A

16、BC D第46页，共95页。第3节 图解法例7图解：目标函数z第47页，共95页。第3节 图解法例8图解：目标函数 max z=2x1+4x2 z第48页，共95页。第3节 图解法要求：用图解法求解下列线性规划问题。例12： min z =2x1-x2 -2x1+x22 x1-2x21 x1，x20第49页，共95页。第3节 图解法例13：1、 max z =x1+x2 -2x1+x24 x1-x22 x1，x20 2、 max z =x1+2x2 x1+2x28 4x116 4x212 x1，x20第50页，共95页。作业3作业3：用图解法求解下列线性规划问题。1、 max z =50 x1

17、+100 x2 x1+x2300 2x1+x2400 x2250 x1，x202、 max z =4x1+8x2 2x1+2x210 -x1+x2 8 x1，x203、max z =3x1+9x2 x1+3x222 -x1+x24 x26 2x1-5x20 x1，x204、max z =2x1+2x2 x1-x2 -1 -0.5x1+x2 2 x1，x20第51页，共95页。作业3答案1、2、3、4、第52页，共95页。第4节 单纯形法一、单纯形法的解题思路从某一基可行解开始，转化到另一个相邻的基可行解，并且使相应的目标函数值有改进。即从可行域的一个顶点沿约束边界转换到可行域的另一个相邻的且使

18、目标函数值有改进的顶点，直到目标函数值到达最优时的顶点为止。第53页，共95页。第4节 单纯形法定义两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。第54页，共95页。第4节 单纯形法二、单纯形法的含义单纯形法是一种迭代算法，首先找到一个初始基可行解，然后判断它是否为最优解，如果是就停止迭代，否则，按照一定的法则，再找到一个更好且与当前基可行解相邻的基可行解，再进行判断，直到找不到更好的基可行解或判断问题无解为止。第55页，共95页。第4节 单纯形法三、单纯形法的解题步骤1、找出初始可行基，确定初始基可行解，建立初始单纯形表。c1cmcm+1cncBxBbx1xmxm+1xnc1x

19、1b110a1,m+1 a1,nc2x2b200a2,m+1a2,ncmxmbm01am,m+1am,n00第56页，共95页。第4节 单纯形法例：线性规划问题数学模型的某种标准形式第57页，共95页。第4节 单纯形法2、检验各非基变量xj（j=m+1，m+2，n）的检验数j，若j0，则已得最优解，停止计算，否则转入3。3、在j0 （j=m+1，m+2，n）中，若有某个k对应的xk的系数列向量Pk0，则此线性规划问题存在无界解，停止计算，否则转入4。4、根据 ，确定xk为换入变量，通过 ，计算确定xl为换出变量，转入5。第58页，共95页。第4节 单纯形法5、以alk为主元素进行迭代，把xk所

20、对应的列向量 将xB列中xl的换为xk，得到新的单纯形表，重复25，直至终止。变换为第59页，共95页。第4节 单纯形法例14：用单纯形法求解例7。解： max z =2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1，x2，x3，x4，x50第60页，共95页。第4节 单纯形法例15：用单纯形法求解下述线性规划问题。 max z =2x1+x2 5x215 6x1+2x224 x1+x25 x1，x20第61页，共95页。第4节 单纯形法例15：解： max z =2x1+x2 5x2+x3=15 6x1+2x2+x4=24 x1+x2+x5=5 x1，x2

21、，x3，x4，x50第62页，共95页。作业4作业4：用单纯形法求解下列线性规划问题。1、 max z =5x1+2x2+3x3-x4+x5 x1+2x2+2x3+x4=8 3x1+4x2+x3+x5=7 x1，x2 ，x3 ，x4 ，x502、 min z =-5x1-4x2 x1+2x26 2x1-x24 5x1+3x215 x1，x20第63页，共95页。作业4答案1、2、第64页，共95页。第5节 人工变量法一、人工变量法的解题思路线性规划问题中不存在现成的可行基，为了求一个初始可行基和初始基可行解，在每个约束方程中人为地加上一个变量（人工变量），使约束方程组的系数矩阵中产生初始基。第

22、65页，共95页。第5节 人工变量法二、人工变量法的含义若原线性规划问题有可行解，则新的线性规划问题的最优解中人工变量的取值一定为0。第66页，共95页。第5节 人工变量法三、人工变量法的解题步骤将原问题转化为标准型对或的约束条件添加人工变量，直至构造出单位矩阵，且人工变量在目标函数中的系数为-M，建立初始单纯形表按照单纯形法的解题步骤25求解第67页，共95页。第5节 人工变量法例16：用人工变量法求解下述线性规划问题。 max z =-3x1+x3 x1+x2+x34 -2x1+x2 -x31 3x2+x3=9 x1，x2，x30第68页，共95页。第5节 人工变量法例16：解：标准型第6

23、9页，共95页。第5节 人工变量法添加人工变量第70页，共95页。第5节 人工变量法例17：用人工变量法求解下述线性规划问题。 max z =10 x1+15x2+12x3 5x1+3x2+x39 -5x1+6x2+15x315 2x1+x2+x35 x1，x2 ，x30第71页，共95页。第5节 人工变量法例17：解：标准型并添加人工变量 max z =10 x1+15x2+12x3-Mx7 5x1+3x2+x3+x4=9 -5x1+6x2+15x3+x5=15 2x1+x2+x3-x6+x7=5 x1，x2 ，x3 ，x4，x5 ，x6 ，x70第72页，共95页。第5节 人工变量法小结（

24、1）将线性规划化为标准型后，对或的约束条件添加人工变量（若约束条件系数矩阵A中已有k个单位列向量，只要引入m-k个人工变量，使它们与原来的k个单位列向量合成单位矩阵）（2）在最优解中，若人工变量大于0，则原问题无可行解第73页，共95页。作业5作业5：用人工变量法求解下列线性规划问题。1、 max z =3x1-x2-x3 x1-2x2+x311 -4x1+x2+2x33 2x1-x3=-1 x1，x2，x302、min z =-x1-3x2+x3 x1+x2+2x3+x4=4 -x1+x3-x5=4 x3-x6=3 x1，x2，x3， x4，x5，x60第74页，共95页。作业5答案1、2、

25、第75页，共95页。第6节 单纯形法小结标准型第76页，共95页。第6节 单纯形法小结单纯形表中解的表示形式1、唯一最优解：所有非基变量检验数j02、无穷多最优解：某非基变量检验数j03、无界解：某检验数j0对应变量的系数列向量Pk04、无可行解：最终单纯形表中含有0的人工变量第77页，共95页。第6节 单纯形法小结5、退化基可行解：一个或几个基变量0的基可行解出现退化基可行解，可能导致从某个基开始，经过若干次迭代后又回到原来的基，即单纯形法出现了循环，永远达不到最优解，导致计算失败。为避免出现死循环，法则如下：选择换入变量时，若有几个正的检验数具有相同的最大值，则选择下标最小的对应的非基变量

26、作为换入变量选择换出变量时，若按规则计算，有几个比值同时达到最小，则选择下标最小的对应的基变量作为换出变量第78页，共95页。第6节 单纯形法小结例18：下列表格是求线性规划问题的单纯形表，试说明解的情况。1、最终表 2 3 0 0 0CBxBb x1 x2 x3 x4 x5203x1x5x2442 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 0 0 -3/2 -1/8 0第79页，共95页。第6节 单纯形法小结2、最终表 3 2 -1 0 0 0CBxBb x1 x2 x3 x4 x5 x6023x4x2x129/56/521/5 0 0 -1 1 -1/

27、5 8/5 0 1 1 0 1/5 -3/5 1 0 0 0 1/5 2/5 0 0 -3 0 -1 0第80页，共95页。第6节 单纯形法小结3、中间表 2 3 0 0 0 0CBxBb x1 x2 x3 x4 x5 x60203x3x1x5x22283 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/4 0 0 0 -2 0 1/4第81页，共95页。第6节 单纯形法小结4、最初表 3 3 2 0 0CBxBb x1 x2 x3 x4 x500 x4x512 -1 3 -1 1 0 2 -1 1 0 1 3 3 2 0 0第82

28、页，共95页。第6节 单纯形法小结5、中间表（最终表） 4 5 0 0 0CBxBb x1 x2 x3 x4 x5000 x3x4x5723 4 -1 1 0 0-1 -5 0 1 0 7 -3 0 0 1 4 5 0 0 0第83页，共95页。第6节 单纯形法小结6、中间表 4 3 0 0 0CBxBb x1 x2 x3 x4 x5000 x3x4x5723 4 -1 1 0 0-1 -5 0 1 0 7 -3 0 0 1 4 3 0 0 0第84页，共95页。单纯形法计算步骤框图第85页，共95页。第6节 单纯形法小结例19：用单纯形法求解下述线性规划问题，并说明解的情况。 max z =

29、2.5x1+x2 3x1+5x215 5x1+2x210 x1，x20第86页，共95页。第6节 单纯形法小结例19：解：max z =2.5x1+x2 3x1+5x2+x3=15 5x1+2x2+x4=10 x1，x2 ，x3，x40第87页，共95页。作业6作业6：求解下述线性规划问题，并说明解的情况。1、max z =6x1+4x2 -x1+2x24 3x1+2x214 2x1-x24 x1，x2 02、max z =2x1-x2+2x3 x1+x2+x36 -2x1+x32 2x2-x30 x1，x2，x30第88页，共95页。作业6答案第89页，共95页。第6节 单纯形法小结例20：下表为求某最大化线性规划问题的最终单纯形表，其中x4，x5为松弛变量，试写出该问题的最优解。b x1 x2 x3 x4 x524 0 -1 1 3 1 1 -1 0 -1 0 0 -3 0 -3 -1第90页，共95页。第6节 单纯形法小结例21：某线性规划问题的标准型为 max z =CX AX=b X0其最终单纯形表如下表，其中x4，x5为对应于初始单位矩阵的