1.2. 运筹学线性规划-单纯形法-xiao.ppt

线性规划解法线性规划解法Linear Programming，LP)要求：要求：1.1.理解线性规划概念；理解线性规划概念；2.2.理理解解线线性性规规划划的的一一般般形形式式与与标标准准形形式式，能将一般形式化为标准形式；能将一般形式化为标准形式；3.3.掌掌握握可可行行解解、最最优优解解及及标标准准形形式式下下的的基基、基解、基可行解等概念。基解、基可行解等概念。4.4.掌握单纯形解法。掌握单纯形解法。1.3 线性规划图解法线性规划图解法 graphic solutionn优点：优点：直观性强，计算方便直观性强，计算方便n缺点：缺点：只适用于问题中有两个变量的情况只适用于问题中有两个变量的情况n作用：作用：它的解题思路和几何上直观得到的它的解题思路和几何上直观得到的一些概念判断，对理解求解一般线性规划一些概念判断，对理解求解一般线性规划问题的单纯形法有很大的问题的单纯形法有很大的启示启示。1.3.1 1.3.1 图解法的步骤：图解法的步骤：n n1建立坐标系，将约束条件在图上建立坐标系，将约束条件在图上表示；表示；n n2确立满足约束条件的解的范围确立满足约束条件的解的范围可行域；可行域；n n3绘制出目标函数的图形；绘制出目标函数的图形；n n4确定最优解确定最优解可行域内使目标可行域内使目标函数最大的点。函数最大的点。4 46 68 84 46 63 3A AB BC CD(4,2)D(4,2)D点即为最优点2x1+2x2=12x1+2x2=84x2=124x1=16每个点都是每个点都是一个可能解一个可能解可行解可行解可行域可行域1.3.2 1.3.2 特殊特殊特殊特殊LPLP的图解法多解的图解法多解的图解法多解的图解法多解1010505010105050B BAB段即为最优解，段即为最优解，多重最优解。多重最优解。A A多重解原因：目标多重解原因：目标函数的斜率与某一函数的斜率与某一关键约束条件的斜关键约束条件的斜率相等。率相等。特殊特殊LP的图解法无界解的图解法无界解1 12 21 12 2B BA A原因：各约束没有原因：各约束没有原因：各约束没有原因：各约束没有围成一个封闭的可围成一个封闭的可围成一个封闭的可围成一个封闭的可行域，可行域是发行域，可行域是发行域，可行域是发行域，可行域是发散的。散的。散的。散的。特殊特殊LP的图解法无可行域，真正无解的图解法无可行域，真正无解1010151510103030原因：有相互矛盾原因：有相互矛盾原因：有相互矛盾原因：有相互矛盾的约束，约束条件的约束，约束条件的约束，约束条件的约束，约束条件之间没有交集。不之间没有交集。不之间没有交集。不之间没有交集。不能形成可行域。能形成可行域。能形成可行域。能形成可行域。1.3.3 图解法总结与启示图解法总结与启示1.1.将约束条件作到坐标图上将约束条件作到坐标图上,找出找出可行域可行域。2.2.找最优点找最优点,即使目标函数即使目标函数最大的点最大的点。图解法的启示图解法的启示1.1.可行域是一个可行域是一个凸多边形凸多边形.2.2.最优解一定在可行域的最优解一定在可行域的边界上边界上,一般是一般是在在顶点上顶点上.3.3.LP的解可能有的解可能有多种形式多种形式，如多解、无，如多解、无界解界解(发散发散,无穷无穷)或无可行域或无可行域.1.3.4 线性规划的解线性规划的解 唯一最优解唯一最优解 无穷多最优解无穷多最优解 无界解无界解 无可行解无可行解有解有解无解无解线性规划的解线性规划的解线性规划的解线性规划的解1.3.5 线性规划解的问题线性规划解的问题一般一般mn，如何解？，如何解？对于存在无穷多解的问题，为求唯一解最对于存在无穷多解的问题，为求唯一解最优，最简单的方法是舍去优，最简单的方法是舍去n-m个作用个作用不大或呈负面影响的未知数决策变量，不大或呈负面影响的未知数决策变量，获得获得m个方程、个方程、m个未知数，即可获得唯一个未知数，即可获得唯一解。解。问题：问题：1如何舍去这些决策变量？原如何舍去这些决策变量？原因、准那么因、准那么2如何保证舍去的这些决如何保证舍去的这些决策变量是适宜的？策变量是适宜的？思思 路：路：n n可行解可行解n n基基 基向量、基变量、基向量、基变量、非基变量非基变量n n根本解根本解n n可行基可行基n n最优解最优解1.4 LP 解的根本概念1可行解可行解n n满足满足约束条件约束条件的解称为线性规划问题的的解称为线性规划问题的可行解可行解。n n所有可行解的集合称为所有可行解的集合称为可行域可行域。可行域可行域可行域可行域2基基基向量、基变量、非基基向量、基变量、非基变量变量n n基基基基在约束方程组的在约束方程组的在约束方程组的在约束方程组的mnmn阶系数矩阵阶系数矩阵阶系数矩阵阶系数矩阵n n中中中中,假设有一个假设有一个假设有一个假设有一个mmmm阶的非奇异子矩阵阶的非奇异子矩阵阶的非奇异子矩阵阶的非奇异子矩阵B Bn n那么那么那么那么B B为该为该为该为该LPLP问题的一个基一个矩阵。问题的一个基一个矩阵。问题的一个基一个矩阵。问题的一个基一个矩阵。n n那么矩阵那么矩阵那么矩阵那么矩阵B B由由由由mm个线性无关的列向量组成，可令个线性无关的列向量组成，可令个线性无关的列向量组成，可令个线性无关的列向量组成，可令其对应的列向量其对应的列向量其对应的列向量其对应的列向量Pj(j=1,2,m)Pj(j=1,2,m)为基向量，对应的为基向量，对应的为基向量，对应的为基向量，对应的xjxj为基变量，否那么为非基及非基变量。为基变量，否那么为非基及非基变量。为基变量，否那么为非基及非基变量。为基变量，否那么为非基及非基变量。m列列(要求线性无关要求线性无关要求线性无关要求线性无关)(基基)n-m列列(非基非基)x1,x2,xm为为基变量基变量xm1,xn为为非基变量非基变量n n3基解基解(也叫也叫“根本解根本解n n n n 在包含基和非基的在包含基和非基的LP问题中，任取问题中，任取一个基，令所有非基变量均为一个基，令所有非基变量均为0，即可，即可解出唯一根本解基解。解出唯一根本解基解。假设方程组的系数矩阵假设方程组的系数矩阵A的的秩为秩为m，因为，因为mn，故该方程，故该方程组有无穷多个解，组有无穷多个解，假设前假设前m个变量的系数变量是线个变量的系数变量是线性无关的，那么方程组可表达为性无关的，那么方程组可表达为基解的特点：基解的特点：1 1 基解的非零分量的数目小于等于约束方程基解的非零分量的数目小于等于约束方程基解的非零分量的数目小于等于约束方程基解的非零分量的数目小于等于约束方程 数目数目数目数目mm。2 2 基解是约束方程的交点。基解是约束方程的交点。基解是约束方程的交点。基解是约束方程的交点。3 3 基解只满足条件约束，不一定满足非负约束，基解只满足条件约束，不一定满足非负约束，基解只满足条件约束，不一定满足非负约束，基解只满足条件约束，不一定满足非负约束，因此基解中的分量有可能为负数说明线性规划因此基解中的分量有可能为负数说明线性规划因此基解中的分量有可能为负数说明线性规划因此基解中的分量有可能为负数说明线性规划有很多基解，初次选定的不一定适宜。有很多基解，初次选定的不一定适宜。有很多基解，初次选定的不一定适宜。有很多基解，初次选定的不一定适宜。4 4 基解的个数有限，不超过基解的个数有限，不超过基解的个数有限，不超过基解的个数有限，不超过 Cnm Cnm。基解特点基解特点-1例例基解特点基解特点-2基解特点基解特点-3基解特点基解特点-4由此可知：基与基解一一对应，且该线性规划问题的基解的个数n n4 4基可行解和可行基基可行解和可行基基可行解和可行基基可行解和可行基n n 满足满足满足满足(1.2),(1.3)(1.2),(1.3)的基解，的基解，的基解，的基解，n n 称为基可行解，相应称为基可行解，相应称为基可行解，相应称为基可行解，相应n n 的基的基的基的基B B为可行基。为可行基。为可行基。为可行基。n n最优解最优解最优解最优解n n 满足满足满足满足1.1),(1.2),(1.3)1.1),(1.2),(1.3)的解称为最优解。的解称为最优解。的解称为最优解。的解称为最优解。5可行解、基解和根本可行解的关系可行解、基解和根本可行解的关系求最优解路线：求最优解路线：可行解可行解 基可行解基可行解 最优解最优解 区域区域 交点交点 顶点顶点 某顶点某顶点 1.4.2 LP解的根本性质解的根本性质1预备知识预备知识 凸集、顶点凸集、顶点2根本定理根本定理 定理定理1 LP的可行域为凸集的可行域为凸集 定理定理2 LP可行解是根本可行解可行解是根本可行解 可可行解的非零向量对应的系数列向量线行解的非零向量对应的系数列向量线性无关。性无关。定理定理3 根本可行解根本可行解 可行域的顶可行域的顶点点 定理定理4 假设有最优解，最优解一定在可假设有最优解，最优解一定在可行域顶点或边界上实现。行域顶点或边界上实现。1.5 LP的求解与单纯形法的求解与单纯形法n1、线性规划解法的思路与存在问题、线性规划解法的思路与存在问题n 1 标准数学模型中，有标准数学模型中，有n个未知数决策变量个未知数决策变量，m个约束方程，一般个约束方程，一般mn，且常有，且常有mn，可能有，可能有无穷多解。无穷多解。怎么解决？怎么解决？n 2可行方法：由于可行方法：由于LP的最优解肯定是在可行域的最优解肯定是在可行域的边界或顶点出现，即，肯定为基可行解，因此只需的边界或顶点出现，即，肯定为基可行解，因此只需不断判断基可行解是否满足目标要求即可。不断判断基可行解是否满足目标要求即可。如何选择保存的未知数和抛弃的未知数？如何选择保存的未知数和抛弃的未知数？n 3操作方法：在技术系数矩阵中，找出与其秩操作方法：在技术系数矩阵中，找出与其秩相等的线性无关的列向量，此列向量对应的决策变量相等的线性无关的列向量，此列向量对应的决策变量称为基变量，应保存，其余为非基变量，可取零。称为基变量，应保存，其余为非基变量，可取零。线性无关的列向量可能有很多，那么每组基变量不同，线性无关的列向量可能有很多，那么每组基变量不同，那么目标函数值也不同，如何寻求最优解？那么目标函数值也不同，如何寻求最优解？如何判如何判断找到的基可行解是最优？断找到的基可行解是最优？2 2、单纯形法、单纯形法根本思路：根本思路：从可行域中某个基可行解开始，根据一从可行域中某个基可行解开始，根据一定标准判断是否为最优，假设不是定标准判断是否为最优，假设不是,那么转那么转换到另一个基可行解，直到目标函数最优时换到另一个基可行解，直到目标函数最优时为止，就得到了最优解。为止，就得到了最优解。单纯形核心：单纯形核心：关键在于：判断标准的建立和转换方法，关键在于：判断标准的建立和转换方法，使每次转换后结果更优，而不必穷举所有顶使每次转换后结果更优，而不必穷举所有顶点即可得到最优解。点即可得到最优解。判别准那判别准那么么转换方法转换方法3 3、判别准那么的建立、判别准那么的建立基变量目标基变量目标系数系数非基变量目非基变量目标系数标系数现行基可行解现行基可行解对应的目标值对应的目标值非基变量不为非基变量不为零时对目标值零时对目标值的作用的作用判别准那么判别准那么定理定理定理定理1 1 1 1 当所有非基变量的检验数当所有非基变量的检验数当所有非基变量的检验数当所有非基变量的检验数j 0j 0j 0j 0，相应的基可，相应的基可，相应的基可，相应的基可行解为最优解。行解为最优解。行解为最优解。行解为最优解。定理定理定理定理2 2 2 2 当存在非基变量的检验数当存在非基变量的检验数当存在非基变量的检验数当存在非基变量的检验数j j j j 0 0 0 0，那么该解不，那么该解不，那么该解不，那么该解不是最优解。是最优解。是最优解。是最优解。现行基可行解现行基可行解对应的目标值对应的目标值非基变量不为非基变量不为零时对目标值零时对目标值的作用的作用当所选的基可行解不是最优解时，如何当所选的基可行解不是最优解时，如何寻找新的基可行解？寻找新的基可行解？可行基的转换准可行基的转换准那么？那么？3、单纯形法的解题步骤、单纯形法的解题步骤步骤一：将原线性规划转变成标准线性规划；步骤一：将原线性规划转变成标准线性规划；步骤二：建立初始单纯形表，确定初始基、初始基变步骤二：建立初始单纯形表，确定初始基、初始基变量，求出初始基可行解；量，求出初始基可行解；步骤三：计算判别准那么，判断初始基可行解是否为步骤三：计算判别准那么，判断初始基可行解是否为最优解。如是，那么结束；如否，那么进行基变量的最优解。如是，那么结束；如否，那么进行基变量的更换；更换；步骤四：在基变量更换准那么下，用某一非基变量替步骤四：在基变量更换准那么下，用某一非基变量替换初始基变量，获得新的基变量和基可行解；换初始基变量，获得新的基变量和基可行解；步骤五：重复步骤三和四，直到获得最优解。步骤五：重复步骤三和四，直到获得最优解。单纯形法的解题步骤单纯形法的解题步骤例：例：n n 步骤一步骤一步骤一步骤一：将非标准型的线性规划变化：将非标准型的线性规划变化：将非标准型的线性规划变化：将非标准型的线性规划变化为标准型线性规划。为标准型线性规划。为标准型线性规划。为标准型线性规划。标准型线性规划标准型线性规划n n 步骤二步骤二步骤二步骤二：建立初始单纯形表。：建立初始单纯形表。：建立初始单纯形表。：建立初始单纯形表。cjc1c2c3c4c5c6iCBXBbx1 x2x3x4x5x6Zj非基变量为0时的目标函数值目标系数值基变量换出检验数最优解判断检验数单纯性表单纯性表基变基变量对量对应的应的目标目标系数系数值值基变基变量符量符号号变化变化后的后的右端右端项项约束方程中的技约束方程中的技术系数矩阵术系数矩阵决策变量符号决策变量符号 cj230000iCBXBbx1 x2x3x4x5x6221000120100400010040001Zj初始单纯形表的建立初始单纯形表的建立11将技术系数矩阵和目标系数矩阵的数据填入，初步完将技术系数矩阵和目标系数矩阵的数据填入，初步完善单纯形表。在后续的矩阵变化中，目标系数保持恒定。善单纯形表。在后续的矩阵变化中，目标系数保持恒定。c cj j2 23 30 00 00 00 0 i iC CB BX XB Bb bx x1 1 x x2 2x x3 3x x4 4x x5 5x x6 62 22 21 10 00 00 01 12 20 01 10 00 04 40 00 00 01 10 00 04 40 00 00 01 1Z Z j j初始单纯形表的建立初始单纯形表的建立22确定初始基向量XB。原那么：一般选择技术系数矩阵中的单位列向量组成的矩阵作为初始基，与之对应的决策变量为初始基变量，其余为非基变量。并将基变量的符号写入XB列中；3确定CB。与XB对应的目标系数值，填入CB列；4b确实定。将初始右端项填入b列；5计算Z=CBXB=CBb值。初始基可行解=b列对应的值。x3x4x5x6000012816120n n步骤三：校验基变量是否最优？步骤三：校验基变量是否最优？步骤三：校验基变量是否最优？步骤三：校验基变量是否最优？n n规那么：判断规那么：判断规那么：判断规那么：判断 c cCBi aij 0CBi aij 0，如是，如是，如是，如是，那么表示最优，否那么需要进行基变量的更换。那么表示最优，否那么需要进行基变量的更换。那么表示最优，否那么需要进行基变量的更换。那么表示最优，否那么需要进行基变量的更换。cC Bi a ij c cj j2 23 30 00 00 00 0 i iC CB BX XB Bb bx x1 1 x x2 2x x3 3x x4 4x x5 5x x6 62 22 21 10 00 00 01 12 20 01 10 00 04 40 00 00 01 10 00 04 40 00 00 01 1Z Z j jx3x4x5x6000012816120检验数计算检验数计算技巧：技巧：1每个变量对每个变量对应一个检验应一个检验数；数；2xj检验数检验数=xj目目标系数标系数xj对对应的技术系应的技术系数列向量与数列向量与CB列值依次列值依次相乘后的和；相乘后的和；3一般只一般只需计算非基需计算非基变量的检验变量的检验数即可。数即可。230000n步骤四：基变量的更换方法：步骤四：基变量的更换方法：1基变量的换入基变量的换入n 规那么选择一个基变量来取代初始的基变量规那么选择一个基变量来取代初始的基变量：maxj|j0=k，即选择，即选择j0数值中的最大数值中的最大值，其所在的列为换入基向量，对应的变量为换值，其所在的列为换入基向量，对应的变量为换入基变量。此时，此列被称为主元列入基变量。此时，此列被称为主元列Pk。cC Bi a ij c cj j2 23 30 00 00 00 0 i iC CB BX XB Bb bx x1 1 x x2 2x x3 3x x4 4x x5 5x x6 62 22 21 10 00 00 01 12 20 01 10 00 04 40 00 00 01 10 00 04 40 00 00 01 1Z Z j jx3x4x5x6000012816120230000k2204换入基换入基向量向量n n 步骤四：基变量的更换：步骤四：基变量的更换：步骤四：基变量的更换：步骤四：基变量的更换：2 2基变量的换出基变量的换出基变量的换出基变量的换出n n 规那么从原始基变量中选择一个，取出：规那么从原始基变量中选择一个，取出：规那么从原始基变量中选择一个，取出：规那么从原始基变量中选择一个，取出：mini=bi/aik|aik0=lmini=bi/aik|aik0=l，即选择，即选择，即选择，即选择ii数值中的最小数值中的最小数值中的最小数值中的最小值，其所在行对应的变量为换出基变量。此时，值，其所在行对应的变量为换出基变量。此时，值，其所在行对应的变量为换出基变量。此时，值，其所在行对应的变量为换出基变量。此时，此行被称为主元行此行被称为主元行此行被称为主元行此行被称为主元行PlPl。PkPk和和和和PlPl交汇元素为主元素。交汇元素为主元素。交汇元素为主元素。交汇元素为主元素。c cj j2 23 30 00 00 00 0 i iC CB BX XB Bb bx x1 1 x x2 2x x3 3x x4 4x x5 5x x6 62 22 21 10 00 00 01 12 20 01 10 00 04 40 00 00 01 10 00 04 40 00 00 01 1Z Z j jx3x4x5x600001281612023000064-3i计算技巧计算技巧：初始基变量初始基变量对应的对应的i=右右端项端项b除以除以换换入基变量所入基变量所在的列的对在的列的对应值应值。mini=bi/aik|aik0=l换出基变量换出基变量主元素主元素n n步骤四：基变量的更换：步骤四：基变量的更换：步骤四：基变量的更换：步骤四：基变量的更换：3 3基变量的更换。基变量的更换。基变量的更换。基变量的更换。n n 规那么：在单纯形表中，用换入变量代替换规那么：在单纯形表中，用换入变量代替换规那么：在单纯形表中，用换入变量代替换规那么：在单纯形表中，用换入变量代替换出变量，获得新的出变量，获得新的出变量，获得新的出变量，获得新的XBXB列符号列。同时，相列符号列。同时，相列符号列。同时，相列符号列。同时，相应的应的应的应的CBCB数据也由换入变量的数据也由换入变量的数据也由换入变量的数据也由换入变量的cjcj来替代，其余暂来替代，其余暂来替代，其余暂来替代，其余暂时不变。时不变。时不变。时不变。c cj j2 23 30 00 00 00 0 i iC CB BX XB Bb bx x1 1 x x2 2x x3 3x x4 4x x5 5x x6 62 22 21 10 00 00 01 12 20 01 10 00 04 40 00 00 01 10 00 04 40 00 00 01 1Z Z j jx3x4x5x600001281612x3x4x5x20003n n步骤四：基变量的更换：步骤四：基变量的更换：步骤四：基变量的更换：步骤四：基变量的更换：4 4约束方程的迭代运约束方程的迭代运约束方程的迭代运约束方程的迭代运算，求出新的基可行解算，求出新的基可行解算，求出新的基可行解算，求出新的基可行解n n 规那么：为求解方便，一般将须新的基变量对规那么：为求解方便，一般将须新的基变量对规那么：为求解方便，一般将须新的基变量对规那么：为求解方便，一般将须新的基变量对应的列向量变成主元素为应的列向量变成主元素为应的列向量变成主元素为应的列向量变成主元素为1 1的单位向量。此时须将的单位向量。此时须将的单位向量。此时须将的单位向量。此时须将x2x2列变成单位列向量。列变成单位列向量。列变成单位列向量。列变成单位列向量。c cj j2 23 30 00 00 00 0 i iC CB BX XB Bb bx x1 1 x x2 2x x3 3x x4 4x x5 5x x6 62 22 21 10 00 00 01 12 20 01 10 00 04 40 00 00 01 10 00 04 40 00 00 01 1Z Z j j1281612x3x4x5x20003单位化方法：根据初等变换来进行。单位化方法：根据初等变换来进行。1第第四行除四行除以以4。3010001/42第四第四行行-2+第二行。第二行。210000-1/23第四第四行行-2+第一行。第一行。620100-1/2n n步骤五：再次校验基变量的最优性。步骤五：再次校验基变量的最优性。步骤五：再次校验基变量的最优性。步骤五：再次校验基变量的最优性。n n 规那么：按照上述方法，再次进行校验。如规那么：按照上述方法，再次进行校验。如规那么：按照上述方法，再次进行校验。如规那么：按照上述方法，再次进行校验。如j0j0，那么表示最优。如不是，那么应再次进，那么表示最优。如不是，那么应再次进，那么表示最优。如不是，那么应再次进，那么表示最优。如不是，那么应再次进行基变量的更换，直到到达最优。行基变量的更换，直到到达最优。行基变量的更换，直到到达最优。行基变量的更换，直到到达最优。c cj j2 23 30 00 00 00 0 i iC CB BX XB Bb bx x1 1 x x2 2x x3 3x x4 4x x5 5x x6 62 22 21 10 00 00 03 31 12 20 01 10 00 02 24 40 00 00 01 10 04 40 04 40 00 00 01 1-Z Z9 92 20 00 00 00 0-3/4-3/4 j j1281612x3x4x5x200033010001/4210000-1/2620100-1/2主元列主元列主主元元行行换入换入变量变量换出换出变量变量主元主元素素 c cj j2 23 30 00 00 00 0 i iC CB BX XB Bb bx x1 1 x x2 2x x3 3x x4 4x x5 5x x6 60 00 01 1-2-20 01/21/24 41 10 00 01 10 0-1/2-1/2-4-40 00 00 0-4-40 02 24 40 01 10 00 01 11/41/41212Z Z13130 00 00 0-2-20 01/41/4 j jx3x4x5x600002283x3x1x5x20203继续进行基变量的更换继续进行基变量的更换x6换入，换入，x5换出。换出。c cj j2 23 30 00 00 00 0 i iC CB BX XB Bb bx x1 1 x x2 2x x3 3x x4 4x x5 5x x6 60 00 01 1-1-1-1/4-1/4 0 01 10 00 00 01/41/40 00 00 00 0-2-21/21/21 10 01 10 01/21/2-1/8-1/8 0 0Z Z14140 00 00 0-3/2-3/20 0-1/8-1/8 j j0442x3x1x6x20203所有所有j0，最优解。，最优解。此时：此时：x1,x2,x3,x4,x5,x6T=4,2,0,0,0,4 T，z=14.b 2 2 1 0 0 0 2 2 1 0 0 0 1 2 0 1 0 0 1 2 0 1 0 0 4 0 0 0 1 0 4 0 0 0 1 0 0 4 0 4 0 0 0 1 0 0 0 1Z Z0 02 2 3 3 0 0 0 00 0 0 0 6 64 43 32 3 0 0 0 02 3 0 0 0 012 816120000Z Z2 2 1 0 0 0 2 2 1 0 0 0 1 2 0 1 0 0 1 2 0 1 0 0 4 0 0 0 1 0 4 0 0 0 1 0 0 40 4 0 0 0 1 0 0 0 1 b 0 02 2 3 3 0 0 0 00 0 0 06 64 43 32 3 0 0 0 02 3 0 0 0 012 8161200000003 3 0 1 0 0 0 1/4 3 0 1 0 0 0 1/4 16 4 0 0 0 1 0 16 4 0 0 0 1 02 1 0 0 1 0 -1/22 1 0 0 1 0 -1/26 2 0 1 0 0 -1/26 2 0 1 0 0 -1/2Z Z9 92 0 0 0 0 -3/42 0 0 0 0 -3/4324 Z Z2 0 1 0 0 -1/2 2 0 1 0 0 -1/2 1 0 0 1 0 -1/2 1 0 0 1 0 -1/2 4 0 0 0 1 0 4 0 0 0 1 0 0 10 1 0 0 0 0 0 0 1/41/4 b 9 92 2 0 00 0 0 0 0 0 -3/4-3/43 32 24 42 3 0 0 0 02 3 0 0 0 0 6 216 300030203 3 0 1 0 0 0 1/4 3 0 1 0 0 0 1/4 8 0 0 0 -4 1 2 8 0 0 0 -4 1 22 1 0 0 1 0 -1/22 1 0 0 1 0 -1/22 0 0 1 -2 0 1/22 0 0 1 -2 0 1/2Z Z13130 0 0 -2 0 1/40 0 0 -2 0 1/4 4-412Z Z0 0 1 -2 0 1/2 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 0 0 -4 1 2 0 10 1 0 0 0 0 0 0 1/41/4 b 1313 0 0 0 00 -2 0 0 -2 0 1/41/44 4 4 412122 3 0 0 0 02 3 0 0 0 0 2 2 8 302030203 2 0 1 0 1/2 -1/8 0 2 0 1 0 1/2 -1/8 0 4 0 0 0 -2 1/2 1 4 0 0 0 -2 1/2 14 1 0 0 0 1/4 04 1 0 0 0 1/4 00 0 0 1 -1 -1/4 00 0 0 1 -1 -1/4 0Z Z14140 0 0 -2/3 -1/8 0 0 0 0 -2/3 -1/8 0 总结：单纯形法的计算步骤总结：单纯形法的计算步骤n n转化为标准型；转化为标准型；n n建立初始单纯型表建立初始单纯型表,确定初始基，求出初确定初始基，求出初始基可行解一般取单位矩阵做初始基；始基可行解一般取单位矩阵做初始基；n n计算检验数计算检验数，判断最优性，确定换入基，判断最优性，确定换入基变量变量k。n ncC Bi a ij n n 可只计算非基变量的可只计算非基变量的，换入基变量，换入基变量n n kmax|0 ，n n k对应的列为主元列，列对应的变量为换对应的列为主元列，列对应的变量为换入变量。入变量。计算计算，确定换出基变量，确定换出基变量l。计算计算i，i bi/a ik 当当a ik 0时时只计算非负的只计算非负的aik 对应的行，换出基变量对应的行，换出基变量 l mini，l 对应的行为主元行，主元行对应的对应的行为主元行，主元行对应的XB中的变量换出基变量。中的变量换出基变量。K 列列 l 行的元素称为主元素。行的元素称为主元素。主元素用主元素用alk表示。表示。54练习：利用单纯形表求解线性规划练习：利用单纯形表求解线性规划练习：利用单纯形表求解线性规划练习：利用单纯形表求解线性规划Cj比值CBXBb检验数j检验数s：初始时是目标函数的系数随基的调整变化变量符号基变量符号随基的调整变化基变量在目标函数中的系数变化约束方程的常数项约束方程的变量系数有一个检验数j=0，此时基解不是最优；所有检验数j 0 0线性规划56检验数j81010060101/2012300-21x3x2x5050-30300-5/20Cj比值CBXBb检验数jx1x2x3x4x5350008101001202 20103634001x3x4x5000035000-12/2=636/4=9 1 1=3=30 0，此解不是最优，此解不是最优，此解不是最优，此解不是最优 可求基可行解的状态可求基可行解的状态可求基可行解的状态可求基可行解的状态继续改变基变量继续改变基变量继续改变基变量继续改变基变量线性规划57 Cj比值CBXBb检验数jx1x2x3x4x53500081010060101/20123 300-21x3x2x5050-30300-5/208-4检验数j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1令令令令 x x4 4=0 0，x x5 5=0=0，得，得，得，得x x1 1=4=4，x x2 2=6=6，x x3 3=4=4，即，即，即，即X X0 0=(4,6,4,0,0)=(4,6,4,0,0)T T j0最优解最优解最优解最优解:X X*=(4,6,4,0,0)=(4,6,4,0,0)T T最优值最优值最优值最优值:Z Z*=42=42线性规划58练习：练习：练习：练习：由下表数据，列出使总利润最大的生产方案模型，并求利润最大的生产方案maxZ=12 x1+8 x2 5x1+2 x2 150 2 x1+3 x2 100 4x1+2 x2 80 x1,x2 0令产品甲的产量为x1,产品甲的产量为x2,得如下线性规划模型59参考答案：参考答案：参考答案：参考答案：maxZ=12 x1+8 x2 5x1+2 x2 150 2 x1+3 x2 100 4x1+2 x2 80 x1,x2 0maxZ=12 x1+8 x2 5x1+2 x2+x3 =150 2 x1+3 x2 +x4 =100 4x1+2 x2 +x5=80 x1,x2,x3,x4,x50答案：答案：x1=5，x2=30，max z=30060【练习题练习题】1.1 1.1 1.1 1.1 某某某某工工工工厂厂厂厂可可可可以以以以生生生生产产产产产产产产品品品品A A A A和和和和产产产产品品品品B B B B两两两两种种种种产产产产品品品品。生生生生产产产产单单单单位位位位产产产产品品品品A A A A和和和和B B B B所所所所需需需需要要要要的的的的机机机机时时时时、人人人人工工工工工工工工时时时时的的的的数数数数量量量量以以以以及及及及可可可可利利利利用用用用资资资资源源源源总总总总量量量量由由由由下下下下表表表表给给给给出出出出。这这这这两两两两种种种种产产产产品品品品在在在在市市市市场场场场上上上上是是是是畅畅畅畅销销销销产产产产品品品品。该该该该工工工工厂厂厂厂经经经经理理理理要要要要制制制制订订订订季季季季度度度度的的的的生生生生产产产产方方方方案案案案，其其其其目目目目标标标标是是是是使使使使工工工工厂厂厂厂的的的的销销销销售售售售额额额额最最最最大。大。大。大。产品产品产品产品A A A A 产品产品产品产品B B B B 资源总量资源总量资源总量资源总量 机器时机器时机器时机器时 6 8 120 6 8 120 6 8 120 6 8 120 人工时人工时人工时人工时 10 5 100 10 5 100 10 5 100 10 5 100 产品售价元产品售价元产品售价元产品售价元 800 300 800 300 800 300 800 300X1=10 x2=0 z=800061【练习题练习题】该工厂根据产品A和产品B的销售和竞争对手的策略，调整了两种产品的售价。产品A和B的价风格整为600元和400元。假设其它条件不变，请你帮助该工厂经理制订季度的生产方案，其目标仍然是使工厂的销售额最大。X1=4 x2=12 z=720062【练习题练习题】由由于于某某些些原原因因，该该工工厂厂面面临临产产品品原原料料供供给给的的问问题题。因因此此，工工厂厂要要全全面面考考虑虑各各种种产产品品所所需需要要的的机机时时、人人工工工工时时、原原材材料料的的资资源源数数量量及及可可用用资资源源的的总总量量、产产品品的的售售价价等等因因素素。有有关关信信息息在在下下表表中中给给出。出。产产品品A A 产产品品B B 资资源源总总量量 机器机器时时 6 8 120 6 8 120 人工人工时时 10 5 100 10 5 100 原材料原材料(公斤公斤)11 8 130)11 8 130 产产品售价元品售价元 600 400 600 400X1=6 x2=8 z=6800