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

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节 数学模型一、规划问题l含义：如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。第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节 数学模型二、线性规划问题l特征（三要素）（1）决策变量：问题中的未知量（2）目标函数：问题要达到的目标（最大或最小），表示为决策变量的线性函数（3）约束条件：表示为含决策变量的一组互不矛盾的线性等式或线性不等式的函数约束和决策变量的非负约束第13页，共95

5、页。第1节 数学模型线性规划问题数学模型的形式（1）一般形式1 12211 11221121 1222221 12212max(min)(,)(,)(,),0nnnnnnmmmnnmnzc xc xc xa xa xa xba xa xa xba xaxaxbx xx 第14页，共95页。第1节 数学模型（2）简写形式（3）向量形式 （4）矩阵形式11max(min)(,),1,2,0,1,2,njjjnijjijjzc xa xb imxjn 1max(min)(,)0njjjzCXP xbX max(min)(,)0zCXAXbX 第15页，共95页。第1节 数学模型例2：一般形式 矩阵形

6、式 max z=2x1+3x2 2x1+2x212 x1+2x28 4x116 4x212 x1，x20121212max2322121284016041200 xzxxxxx 第16页，共95页。第1节 数学模型三、线性规划数学模型的标准形式（标准型）l目标函数求最大值l函数约束条件全为等式l决策变量全为非负l函数约束条件右端项全为非负11max12012njjjnijjijjzc xa xbimxjn，第17页，共95页。第1节 数学模型四、线性规划的非标准型如何转化为标准型l目标函数求最小值：令z-zl函数约束条件为不等式：在函数约束条件左端加非负的松弛变量 ：在函数约束条件左端减非负的

7、松弛变量 松弛变量在目标函数中的系数全为0l决策变量为负值：令xj-xj，xj0l决策变量取值无约束：令xj xj-xj，xj0，xj0l函数约束条件右端项（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+x3-x3+x4=9 3x1+x2+2x3-2x3-x

8、5=4 3x1+2x2+3x3-3x3=6 x1，x2，x3，x3，x4，x5011333,xx xxxzz 第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，x50333,xxxzz 第22页，共95页。第1节 数学模型例5：max z=2x1+3x2

9、+5x3 x1+x2-x3-5 -6x1+7x2-9x3=16 19x1-7x25x3 13 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，x60333xxx第24页，共95页。作业1作业1：将下列线性规划问题化为标准型。1、min z=5x1-2x2+4x3-3x4 -x1+2x2-x3+4x4=-2 -x1+3x2+

10、x3+x414 2x1-x2+3x3-x42 x1无约束，x20，x3，x4 02、min z=x1+2x2+4x3 2x1+x2+3x320 3x1+x2+4x3 25 x1，x20，x30第25页，共95页。作业1答案 1、2、1112211234112341123451123461123456,max5524324231422320 xxxxx zzzxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 令，331231231234123512345,max242320342534250 xx zzzxxxxxxxxxxxxxxxxxxx 令，第26页，共95页。第2节 解一、线性

11、规划问题解的概念l可行解：满足函数约束条件和非负约束条件的解l最优解：使目标函数达到最大值的可行解l基：设A是约束方程组的mn阶系数矩阵，B是矩阵A中mm阶非奇异子矩阵，称B是线性规划问题的一个基l基向量：基B中每一个列向量Pjl非基向量：A中其余列向量Pj（不在B中）l基变量：与基向量Pj对应的决策变量xjl非基变量：与非基向量对应的决策变量l基解l基可行解：满足非负约束条件的基解l可行基：对应于基可行解的基第27页，共95页。第2节 解二、线性规划问题解的关系可行解最优解基解基可行解基可行基可行解基解可行解基可行解最优解最优解第28页，共95页。第2节 解线性规划问题数学模型的标准形式（一

12、般形式）1 12211 11221121 1222221 12212,m,0axnnnnnnmmmnnmnzc xc xc xa xa xa xba xa xa xba xaxaxbx xx第29页，共95页。第2节 解补充（复习）内容l秩：设在矩阵A中一个不等于0的r阶子式D，且所有r1阶子式（如果存在的话）全等于0，那么D为矩阵A的最高阶非零子式，数r为矩阵A的秩。l非奇异矩阵：行列式不等于0的矩阵。l克莱姆法则：如果线性方程组 a11x1+a12x2+a1mxm=b1 a21x1+a22x2+a2mxm=b2 am1x1+am2x2+ammxm=bm 的系数行列式不等于0，则方程组有唯一

13、解。第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、（1，2，0，0）基可行解z=

14、8（34 5，0，0，7 5）基可行解，最优解z=117 5（0，45 16，7 16，0）基可行解z=163 16（45 13，0，-14 13，0）（0，68 29，0，-7 29）（0，0，-68 31，-45 31）055（2 5，0，11 5，0）基可行解z=-43 5（0，2，1，0）基可行解z=1（0，0，1，1）基可行解，最优解z=3（-1 3，11 3，0，0）（-1 3，0，0，11 6）B，B 不是基第33页，共95页。第3节 图解法一、图解法l适用条件：适用于求解只有两个决策变量的线性规划问题l特点（1）不必将线性规划问题转化为标准型（2）直观性强，计算方便第34页，共

15、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：标出目标函数目标函数2132xxzmax表示一簇平行线33212zxxz第37页，共95页。第3节 图解法二、图解法的求解步骤l建立 二维坐标系l将约束条件表示在坐标系中，以确立可行域画出每个函数约束的约束边界，用原点判断直线的哪一边是约束条件所允许的找出所有约束条件都同时满足的区域，即可行域l将目标函数绘制在坐标系中

16、，并标出变化的方向给定目标函数一个特定的值k，画出目标函数特定线，当k变化时，目标函数特定线将平行移动对于目标函数最大（小）化的问题，找出目标函数增加（减少）的方向，目标函数最后离开可行域的点是最优解l确定最优解2x Ox1第38页，共95页。第3节 图解法三、图解法解的类型l唯一最优解：仅有一点使目标函数值取得最大（小）值l无穷多（多重）最优解：线段（射线）上任意一点都使目标函数值取得相同的最大（小）值l无界解：可行域无界，目标函数值可以增大到无穷大l无可行解：可行域为空集第39页，共95页。第3节 图解法要求：用图解法求解下列线性规划问题。例8：max z=2x1+4x2 x1+2x28

17、4x116 4x212 x1，x20第40页，共95页。第3节 图解法例8：目标函数 max z=2x1+4x2 21124zxx 一簇平行线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节 图解法四、图解法解的特点l当可行域非空集时，可行域必是有界或无界凸多边形。（凸集：集合C中任意两个点a和b，其连线上所有点也必为集合C中的点。）l若可行域有界，则目标函数一定可以在可行域的顶点上达到最优；若可行域无界

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

19、xzmaxz第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+100 x2 x1+x2300 2x1+x2400 x2250

20、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、27500有界可行域，唯一最优解（50，250）z可行域为空集，无可行解66可行域有界，无穷多最优解z可行域无界，无界解第52页，共95页。第4节 单纯形法一、单纯形法的解题思路从某一基可行解开始，转化到另一个相邻的基可行解，并且使相应的目标函数值有改进。即从可行域的一

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

22、cm+1cncBxBbx1 xmxm+1xnc1x1b110a1,m+1 a1,nc2x2b200a2,m+1a2,n cmxmbm01am,m+1am,n00jjc 1,11mmii micc a,1mnii nicc a第56页，共95页。第4节 单纯形法例：线性规划问题数学模型的某种标准形式1 1221111,111,221122,112,2222,11,2212max,0mmmmnnmmmmnnmmmmnnmm mmm mmmnnmnzc xc xc xcxc xxaxaxa xbxaxaxa xbxaxaxaxbx xx第57页，共95页。第4节 单纯形法2、检验各非基变量xj（j=

23、m+1，m+2，n）的检验数j，若j0，则已得最优解，停止计算，否则转入3。3、在j0（j=m+1，m+2，n）中，若有某个k对应的xk的系数列向量Pk0，则此线性规划问题存在无界解，停止计算，否则转入4。4、根据 ，确定xk为换入变量，通过 ，计算确定xl为换出变量，转入5。max0jjk min0ilikiklkbbaaa第58页，共95页。第4节 单纯形法5、以alk为主元素进行迭代，把xk所对应的列向量 将xB列中xl的换为xk，得到新的单纯形表，重复25，直至终止。120010kkklkm kaaPaa变换为第59页，共95页。第4节 单纯形法例14：用单纯形法求解例7。解：max

24、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，x3，x4，x50第62页，共95页。作业4作业4：用单纯形法求解下列线性规划问题。1、max z=5x1+2x2+3x3-x4+x5 x1+2x2+2x3+x4=8 3

25、x1+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、5（6 5，0，17 5，0，0）z=81（12 7，15 7，0，19 7，0）z=-120 7第64页，共95页。第5节 人工变量法一、人工变量法的解题思路线性规划问题中不存在现成的可行基，为了求一个初始可行基和初始基可行解，在每个约束方程中人为地加上一个变量（人工变量），使约束方程组的系数矩阵中产生初始基。第65页，共95页。第5节 人工变量法二、人工变量法的含义若原线性规划问题有可行解，则新的

26、线性规划问题的最优解中人工变量的取值一定为0。第66页，共95页。第5节 人工变量法三、人工变量法的解题步骤l将原问题转化为标准型l对或的约束条件添加人工变量，直至构造出单位矩阵，且人工变量在目标函数中的系数为-M，建立初始单纯形表l按照单纯形法的解题步骤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：解：标准型131231234253max3421390(12 3 4 5)jxxZxxxxxxxxxx

27、xj，第69页，共95页。第5节 人工变量法添加人工变量1312341235772366max3421390(1234567)jZxxxxxxxxxxxxxjMxMxxx，第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

28、+x3-x6+x7=5 x1，x2，x3，x4，x5，x6，x70第72页，共95页。第5节 人工变量法小结（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

29、-x5=4 x3-x6=3 x1，x2，x3，x4，x5，x60第74页，共95页。作业5答案1、2、2（4，1，9，0，0，0，0）z=无可行解第75页，共95页。第6节 单纯形法小结标准型变无约变约条两变边变j jj jj jj jj jj jj jj jj jj jj ji ii ii ij jj ji ii ij jj js si ii ii ij jj ji ii ij jj ji is si ii ij ja ai ij ji ii ij jj ji ii ia ai is si ia ax x0 0 不不x x0 0 令令 x x=-x x,x x0 0 x x 取取 值值束束

30、令令 x x=x x-x x,x x0 0,x x0 0b b0 0 不不b b0 0 束束件件同同 乘乘 1 1 a a x xb b a a x x+x x=b ba a x x=b b a a x x=b bx x松松 弛弛量量0 0,a a x xb b a a x x-x x=+x xx x人人 工工量量0 0+b bx xm m a ax xz z=c c变约条标数变约条j jj jj jj jj jj js si ij jj js si ia ai ij ja ai ij jx x 不不m m i in nz z=c c x x 令令 z z=-z z,m m a ax xz z

31、=-c c x x束束件件 加加 入入 x x m m a ax xz z=c c x x+0 0 x x目目函函不不束束件件 加加 入入 x x m m a ax xz z=c c-M M x xx x第76页，共95页。第6节 单纯形法小结单纯形表中解的表示形式1、唯一最优解：所有非基变量检验数j02、无穷多最优解：某非基变量检验数j03、无界解：某检验数j0对应变量的系数列向量Pk04、无可行解：最终单纯形表中含有0的人工变量第77页，共95页。第6节 单纯形法小结5、退化基可行解：一个或几个基变量0的基可行解出现退化基可行解，可能导致从某个基开始，经过若干次迭代后又回到原来的基，即单纯

32、形法出现了循环，永远达不到最优解，导致计算失败。为避免出现死循环，法则如下：l选择换入变量时，若有几个正的检验数具有相同的最大值，则选择下标最小的对应的非基变量作为换入变量l选择换出变量时，若按规则计算，有几个比值同时达到最小，则选择下标最小的对应的基变量作为换出变量第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 0jc j第79页，共95页

33、。第6节 单纯形法小结2、最终表 3 2 -1 0 0 0CBxBb x1 x2 x3 x4 x5 x6023x4x2x129/56/521/5 0 0 -1 1 -1/5 8/5 0 1 1 0 1/5 -3/5 1 0 0 0 1/5 2/5 0 0 -3 0 -1 0jc j第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/4jc j第81页，共9

34、5页。第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 0jc j第82页，共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 0jc j第83页，共95页。第6节 单纯形法小结6、中间表 4 3 0 0 0CBxBb x1 x2 x3 x4 x5000 x3x4x5723 4 -1 1 0 0-1 -5 0 1

35、 0 7 -3 0 0 1 4 3 0 0 0jc j第84页，共95页。单纯形法计算步骤框图第85页，共95页。第6节 单纯形法小结例19：用单纯形法求解下述线性规划问题，并说明解的情况。max z=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，x

36、2 02、max z=2x1-x2+2x3 x1+x2+x36 -2x1+x32 2x2-x30 x1，x2，x30第88页，共95页。作业6答案1、（22 7，16 7，18 7，0，0）或（5 2，13 4，0，0，9 4）z=282、无界解第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 -1j第90页，共95页。第6节 单纯形法小结例21：某线性规划问题的标准型为 max z=CX AX=b X

37、0其最终单纯形表如下表，其中x4，x5为对应于初始单位矩阵的松弛变量，且z8，试利用上表求c1，c2，c3，c4，c5。c1 c2 c3 c4 c5CBxBb x1 x2 x3 x4 x5c1c2x1x212 1 0 -1 3 -1 0 1 2 -1 1 0 0 -3 -3 -1jc j第91页，共95页。第6节 单纯形法小结例22：在给出的某个求最大值线性规划问题的最终单纯形表中（如下表），当a1，a2，c1，c2，d为何值时，现有解为唯一最优解；现有解为最优解，并有无穷多最优解；存在可行解，但目标函数值无界。c1 c2 0 0 0 xBb x1 x2 x3 x4 x5x3x4x5d23 4

38、 a1 1 0 0-1 -5 0 1 0 a2 -3 0 0 1jc 第92页，共95页。第6节 单纯形法小结例23：某一最大线性规划问题在单纯形法计算时得到下表，其中a，b，c，d，e，f是未知数，原问题中要求各变量均非负。问a，b，c，d，e，f应满足什么条件，有下面各解成立？是非可行基解；是唯一最优解；有无穷多最优解；是退化基可行解；无界解；是可行解但非最优解，只有x1可以进基且出基变量必为第3个变量。xBb x1 x2 x3 x4 x5 x6x3x4x6f23 2 c 1 0 e 0-1 -5 0 1 -1 0 a -3 0 0 -4 1 b d 0 0 -3 0j第93页，共95页。

39、作业7作业7：线性规划的目标函数是max z，在用单纯形法求解的过程中得到下表，其中a，b为常数，部分数据有缺失。要求：1、在所有？处填上适当的数（其中含参数a，b）；2、判断以下四种情况在什么时候成立，并简要说明理由：此解为最优解，试写出最优解和目标函数值；此解为最优解，且有无穷多最优解；此问题有无界解；此解不是最优解，且能用单纯形法得到下一个基可行解。2 5 8 0 0 0CBxBb x1 x2 x3 x4 x5 x6？x6x2x420b8 0？3？0？a？1/2？-2？-1？1？-2？jc j第94页，共95页。作业7答案 2 5 8 0 0 0CBxBb x1 x2 x3 x4 x5 x6050 x6x2x420b8 0 0 3 0 0 1 a 1 2 0 1/2 0 -2 0 -1 1 1 02-5a 0 -2 0 -5/2 0jc jb0，a2 5,（0，b，0，8，0，20）z=5bb0，a2 50b0，a02 5b0，a第95页，共95页。