运筹学单纯形法基本原理.pptx

《运筹学单纯形法基本原理.pptx》由会员分享，可在线阅读，更多相关《运筹学单纯形法基本原理.pptx（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、连接几何形体中任意两点的线段仍完全在该几何形连接几何形体中任意两点的线段仍完全在该几何形体之中。体之中。有限个凸集的交集仍然是凸集。有限个凸集的交集仍然是凸集。单纯形法基本原理第1页/共36页单纯形法基本原理凸集：如果集合凸集：如果集合C中任意两个点中任意两个点X1、X2，其连线上的所有点，其连线上的所有点也都是集合也都是集合C中的点，称中的点，称C为凸集。为凸集。凸集凸集凸集凸集不是凸集不是凸集顶顶点点顶点：如果凸集顶点：如果凸集C中不存在任何两个不同的点中不存在任何两个不同的点X1，X2，使，使X成为这两个点连线上的一个点成为这两个点连线上的一个点第2页/共36页单纯形法基本原理定理定理定

2、理定理1 1：若线性规划问题存在可行解，则该问题的可行域是：若线性规划问题存在可行解，则该问题的可行域是：若线性规划问题存在可行解，则该问题的可行域是：若线性规划问题存在可行解，则该问题的可行域是凸集。凸集。凸集。凸集。定理定理定理定理2 2：线性规划问题的基可行解：线性规划问题的基可行解：线性规划问题的基可行解：线性规划问题的基可行解X X对应可行域对应可行域对应可行域对应可行域(凸集凸集凸集凸集)的顶的顶的顶的顶点。点。点。点。定理定理定理定理3 3：若问题存在最优解，一定存在一个基可行解是最优：若问题存在最优解，一定存在一个基可行解是最优：若问题存在最优解，一定存在一个基可行解是最优：若

3、问题存在最优解，一定存在一个基可行解是最优解。（或在某个顶点取得）解。（或在某个顶点取得）解。（或在某个顶点取得）解。（或在某个顶点取得）第3页/共36页单纯形法的计算步骤 单纯形法的思路单纯形法的思路找出一个初始可行解找出一个初始可行解找出一个初始可行解找出一个初始可行解是否最优是否最优是否最优是否最优转移到另一个基本可行解转移到另一个基本可行解转移到另一个基本可行解转移到另一个基本可行解（找出更大的目标函数值）（找出更大的目标函数值）（找出更大的目标函数值）（找出更大的目标函数值）最优解最优解最优解最优解是是是是否否否否循循循循环环环环核心是：变量迭代核心是：变量迭代核心是：变量迭代核心是

4、：变量迭代结束结束结束结束第4页/共36页四、单纯形法的迭代原理1、确定初始基可行解 (1)初始可行基的确定观察法观察系数矩阵中是否含有现成的单位阵？LP限制条件中全部是“”类型的约束将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；单纯形法基本原理第5页/共36页先将约束条件标准化，再引入非负的人工变量，先将约束条件标准化，再引入非负的人工变量，以人工变量作为初始基变量，其对应的系数列向量以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为构成单位阵，称为“人造基人造基”；然后用大然后用大MM法或两阶段法求解；法或两阶段法求解；线性规划限制条件都是“”或“=”类型的约束单纯

5、形法基本原理第6页/共36页 使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的B(i)列（即约束方程的右边常数）值正好就是基变量的取值。单纯形法基本原理第7页/共36页如果限制条件中既有“”类型的约束，又有“”或“=”类型的约束，怎么办？构造单位阵问题初始可行基一定要选单位阵？b列正好就是基变量的取值，因此称b列为解答列单纯形法基本原理第8页/共36页（2）写出初始基可行解令非基变量取0，基变量对应b(i)，一起构成初始基可行解单纯形法基本原理第9页/共36页此时LP的标准型为单纯形法基本原理第10页/共36页在约束条件中的变

6、量系数矩阵中总会有一个单位矩阵在约束条件中的变量系数矩阵中总会有一个单位矩阵初始可行基初始可行基：当线性规划的约束条件均为当线性规划的约束条件均为，其松弛变量的系数矩阵为单位，其松弛变量的系数矩阵为单位矩阵；当线性规划的约束条件均为矩阵；当线性规划的约束条件均为或或=，为便于找到初始基，为便于找到初始基可行解，构造人工变量，人为产生一个单位矩阵。可行解，构造人工变量，人为产生一个单位矩阵。单纯形法基本原理第11页/共36页初始基本可行解：初始基本可行解：式中式中p p1 1,p,pm m 为基变量为基变量,同其所对应的同其所对应的x x1 1,x,x2 2,.,x,.,xm m为基变量；其它变

7、量为基变量；其它变量x xm+1m+1,x,xm+2m+2，,x,xn n为非基变量。令所有的非基变量等于零。为非基变量。令所有的非基变量等于零。单纯形法基本原理第12页/共36页定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。初始基可行解的前m m个为基变量，2、基变换代入约束条件有单纯形法基本原理第13页/共36页系数矩阵的增广矩阵因为因为p1,pm,是一个基，其他向量是一个基，其他向量pj可以这个基的可以这个基的线性组合表示：线性组合表示：单纯形法基本原理第14页/共36页相减，然后乘上一个正数,加上经过整理得到：找到满足约束方程组的另一点：第j个大于0只变换1个变量；

8、前m个变量必须换出1个单纯形法基本原理第15页/共36页其中是X X（1 1）的第j j个坐标的值，要使X X（1 1）是一个基可行解，对所有的i=1,i=1,m,m,存在令这m个不等式至少有一个等号成立，当单纯形法基本原理第16页/共36页是一个可行解。因为变量x11,x21,xl-11,xl+11,xm1,xj1所对应的向量，经过重新排列后加行b列形成的增广矩阵为：Lalj(1/alj)=1rL(-al-1j)+rL-10-(bL/aLj)+bL-1单纯形法基本原理第17页/共36页所以，P P1 1,P,P2 2,P,Pl-1l-1,P,Pj j,P,Pl+1l+1,P,Pm m,是一个

9、基。进行初等行变换，将第L L行乘上1/a1/aljlj,再分别乘以-a-aijij,(i=1,(i=1,l-1,l+1,l-1,l+1,m),m)加到各行，增广矩阵的左边变成一个单位矩阵，单纯形法基本原理第18页/共36页将 代入目标函数计算：单纯形法基本原理第19页/共36页最优性判别最优性判别、如果所有的检验数，表明现有的顶点对应、如果所有的检验数，表明现有的顶点对应的基可行解为最优解。的基可行解为最优解。、当所有的检验数，又对某个非基变量、当所有的检验数，又对某个非基变量xj的检验数等于的检验数等于0，并且可以找到，并且可以找到0,这表明可以找到这表明可以找到一个顶点目标函数达到最大，

10、说明一个顶点目标函数达到最大，说明LP有无穷多个最优有无穷多个最优解。解。、如果存在某个检验数、如果存在某个检验数0,又又0,表明目标函数达到无限，说明表明目标函数达到无限，说明LP有无界解。有无界解。单纯形法基本原理第20页/共36页单纯形法的计算步骤单纯形表第21页/共36页单纯形法的计算步骤例1.12 用单纯形法求下列线性规划的最优解解：解：1）将问题化为标准型，加入松驰变量将问题化为标准型，加入松驰变量x x3 3、x x4 4则标准型为则标准型为:第22页/共36页单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。cj3400icBXbbx1x2x3x40 x340

11、21100 x43013013400检验数检验数第23页/共36页单纯形法的计算步骤3）进行最优性检验如果表中所有检验数如果表中所有检验数，则表中的基可行解就是问题，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。的最优解，计算停止。否则继续下一步。4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表确定换入基的变量。选择确定换入基的变量。选择，对应的变量，对应的变量xj作为换入变作为换入变量，当有一个以上检验数大于量，当有一个以上检验数大于0时，一般选择最大的一个检时，一般选择最大的一个检验数，即：验数，即：，其对应的，其对应的xk作为换入变作为换入变量。量。确定

12、换出变量。根据下式计算并选择确定换出变量。根据下式计算并选择，选最小的选最小的对应基对应基变量作为换出变量。变量作为换出变量。第24页/共36页单纯形法的计算步骤用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。第25页/共36页单纯形法的计算步骤cj3400icB基变量基变量bx1x2x3x40 x34021100 x430130134000 x34x23x14x2换入列换入列bi/ai2，ai204010换换出出行行将3化为15/311801/301/31011/3303005/

13、304/3乘以3/5后得到103/51/518011/52/540011第26页/共36页单纯形法的计算步骤例1.13 用单纯形法求解解：将数学模型化为标准形式：解：将数学模型化为标准形式：不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。第27页/共36页单纯形法的计算步骤cj12100icB基变基变量量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x220 x x2 221/3150120753017131/309022560 x x1 111017/31/31250128/9-1/92/335/30

14、0-98/9-1/9-7/3第28页/共36页变成标准型变成标准型单纯形法的计算步骤例1.14 用单纯形法求解第29页/共36页约束方程的系数矩阵约束方程的系数矩阵 为基变量为基变量为非基变量为非基变量I I 为单位矩阵且线性独立为单位矩阵且线性独立单纯形法的计算步骤第30页/共36页单纯形法的计算步骤cjcBxBb0000 x3x4x5x612816122x2第31页/共36页第32页/共36页第33页/共36页第34页/共36页单纯形法的计算步骤学习要点：学习要点：1.线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2.熟练掌握线性规划问题的标准化熟练掌握线性规划问题的标准化3.熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤第35页/共36页感谢您的观看！第36页/共36页