线性规划的图解法与单纯形解法.ppt

1,运筹学 Operations Research,王 慧,东南大学经济管理学院 电子商务系暨管理工程研究所 wh_,2,线性规划的图解法与单纯形解法,线性规划问题的图解法 线性规划单纯形解法的原理 线性规划单纯形解法的计算步骤 单纯形法计算的矩阵描述 线性规划单纯形求解的大M法 线性规划单纯形求解的两阶段法 线性规划单纯形求解可能的循环现象,3,线性规划问题的图解法,图解法，就是用作图的方法求解线性规划问题。 简单、直观的图解法一般只适用于具有两个决策变量的线性规划问题。 用图解法求解实际线性规划问题，一般按照如下基本步骤： Step1 画直坐标系； Step2 根据约束条件画出可行域； Step3 画过坐标原点的目标函数线； Step4 确定目标函数值的增大方向(目标函数线法线方向) Step5 目标函数线沿着增大方向平行移动，与可行域相交且有最大目标函数值的顶点，即为线性规划问题的最优解。,4,x1,x2,O,10,20,30,40,10,20,30,40,(15,10),最优解X=(15,10),最优值Z=85,例2.1,5,2,4,6,x1,x2,2,4,6,最优解X=(3,1) 最优值Z=5,(3,1),min Z=x1+2x2,例2.2,6,2,4,6,x1,x2,2,4,6,X（2）（3,1）,X（1）（1,3）,min Z=5x1+5x2,例2.3,有无穷多个最优解 即具有多重解,通解为,01,当=0.5时 =(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2),7,2,4,6,x1,x2,2,4,6,无界解(无最优解),max Z=x1+2x2,例2.4,8,x1,x2,O,10,20,30,40,10,20,30,40,50,50,无可行解 即无最优解,max Z=10x1+4x2,例2.5,9,由以上例题可知，线性规划的解有4种形式：,1.有唯一最优解(例2.1例2.2),2.有多重解(例2.3),3.有无界解(例2.4),4.无可行解(例2.5),1、2情形为有最优解 3、4情形为无最优解,10,由图解法得到的启示,线性规划问题求解的基本依据是：线性规划问题的最优解总可在可行域的顶点中寻找。寻找线性规划问题的最优解只需比较有限个顶点处的目标函数值。 线性规划问题求解时可能出现四种结局：唯一最优解、无穷多个最优解、无有界解、无解或无可行解。 如果某一线性规划问题有最优解，我们可以按照这样的思路来求解：先找可行域中的一个顶点，计算顶点处的目标函数值，然后判别是否有其它顶点处的目标函数值比这个顶点处的目标函数值更大，如有，转到新的顶点，重复上述过程，直到找不到使目标函数值更大的新顶点为止。,11,1.通过图解法了解线性规划有几种解的形式 2.作图的关键有三点 (1)可行解区域要画正确 (2)目标函数增加的方向不能画错 (3)目标函数的直线怎样平行移动,12,线性规划单纯形解法的原理,单纯形方法的基本思想 从可行域中的一个基可行解出发，判别它是否已经是最优解，如不是，寻找下一个基可行解，并且同时努力使目标函数得到改进，如此迭代下去，直到找到最优解或判定问题无解为止。 单纯形算法必须解决三个方面的问题： 1. 如何确定初始的基可行解？ 2. 如何进行解的最优性判别？ 3. 如何寻找改进的基可行解？,13,确定初始的基可行解,标准型的线性规划问题,系数矩阵中存在一个单位阵,以单位阵为一初始可行基。令非基变量取值为零，便得到一基可行解。,14,【例2.6】用单纯形法求下列线性规划的最优解,15,【解】化为标准型，加入松驰变量x3、x4则标准型为,系数矩阵A及可行基B1,r(B1)=2，B1是一个初始基,x3、x4为基变量，x1、x2为非基变量，令x1=0、x2=0由约束方程知x3=40、x4=30得到初始基本可行解,X(1)=(0,0,40,30)T,16,以上得到的一组基可行解是不是最优解，可以从目标函数中的系数看出。目标函数 Z=3x1+4x2中x1的系数大于零，如果x1为一正数，则Z的值就会增大，同样若x2不为零为一正数，也能使Z的值增大；因此只要目标函数中非基变量的系数大于零，那么目标函数就没有达到最大值，即没有找到最优解，判别线性规划问题是否达到最优解的数称为检验数，记作j , j=1,2,n。,本例中 1=3, 2=4, 3=0, 4=0。,最优解判断标准 当所有检验数 j0（j=1，n）时，基本可行解为最优解。,当目标函数中有基变量xi时，利用约束条件将目标函数中的xi消去即可求出检验数。,检验数 目标函数用非基变量表达时的变量系数,17,进基列,出基行,bi /ai2，ai20,i,表1-4,基变量,1,10,0,0,1/3,0,1/3,10,5/3,1,-1/3,40,5/3,0,-4/3,30,1,0,3/5,-1/5,18,0,1,-1/5,2/5,4,0,0,-1,-1,将3化为1,乘以1/3后得到,30,18,18,最优解X=(18，4，0，0)T，最优值Z=70,O,20,30,10,40,(3,4),X(3)=(18,4),最优解X=(18,4),最优值Z=70,X(1)=(0,0),20,10,x2,x1,30,X(2)=(0,10),19,单纯形表,单纯形法全过程的计算，可以用列表的方法计算更为简洁，这种表格称为单纯形表。,20,单纯形算法的计算步骤,将线性规划问题化成标准型。 找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。 计算各非基变量xj的检验数j，若所有j0，则问题已得到最优解，停止计算，否则转入下步。 在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解，停止计算，否则转入下步。 根据maxjj0=k原则，确定xk为换入变量(进基变量)，再按规则计算：=minbi/aik| aik0=bl/ aik 确定xl为换出变量。建立新的单纯形表，此时基变量中xk取代了xl的位置。 以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik变为1，同列中其它元素为0，转第 步。,21,【例2.7】利用单纯形列表算法求解例2.6,22,【例2.8】 用单纯形法求解,23,【解】将数学模型化为标准形式：,不难看出x4、x5可作为初始基变量，单纯法计算结果如表 1.所示 。,24,表15,1/3,1,5,0,1,20,3,0,17,1,3,75,1/3,0,9,0,2,M,20,25,60,1,0,17/3,1/3,1,25,0,1,28/9,1/9,2/3,35/3,0,0,98/9,1/9,7/3,最优解X=(25，35/3，0，0，0)T，最优值Z=145/3,25,【例2.9】用单纯形法求解,26,【解】 这是一个极小化的线性规划问题,可以将其化为极大化问题求解,也可以直接求解,这时判断标准是：j0(j=1，n)时得到最优解。 容易观察到,系数矩阵中有一个3阶单位矩阵,x3、x4、x5为基变量。目标函数中含有基变量x4,由第二个约束得到x4=6+x1x2，并代入目标函数消去x4得,27,表中j0,j=1,2,5所以最优解为X=(0,5,0,1,11,)最优值 Z=2x12x2x4=251=11 极小值问题,注意判断标准,选进基变量时,应选j0的变量xj进基。,表1.6,28,【例2.10】求解线性规划,【解】化为标准型,29,初始单纯形表为,2=10, x2进基，而a120，a220，没有比值，从而线性规划的最优解无界。由模型可以看出，当固定x1使x2+且满足约束条件，还可以用图解法看出具有无界解。,30,【例2.11】求解线性规划,【解】:化为标准型后用单纯形法计算如下表所示,31,32,表 (3)中j全部非正,则最优解为:,表 (3)表明,非基变量x3的检验数3=0, x3若增加,目标函数值不变, 即当x3进基时Z仍 等于20。使x3进基 x5出基继续迭代 ,得到表(4)的另一 基本最优解,X(1),X(2)是线性规划的两个最优解，它的凸组合,仍是最优解，从而原线性规划有多重最优解。,33,最优解的判别定理,定理1 最优解的判别定理,定理2 有无穷多最优解的判别定理,34,最优解的判别定理,定理3 有无界解的判别定理,35,唯一最优解的判断：最优表中所有非基变量的检验数 非零,则线规划具有唯一最优解 。 多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。 无界解的判断: 某个k0且aik（i=1，2,m）则线性规划具有无界解,36,单纯形法计算的矩阵描述,37,单纯形法计算的矩阵描述,38,单纯形法计算的矩阵描述,39,单纯形法计算的矩阵描述,40,单纯形法计算的矩阵描述,41,单纯形法计算的矩阵描述,42,单纯形法计算的矩阵描述,43,线性规划求解的人工变量法,人工变量法 引用人工变量是用单纯形法求解线性规划问题时解决可行解问题的常用方法。 人工变量法的基本思路是： 若原线性规划问题的系数矩阵中没有单位向量，则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。 由于单位阵可以作为基阵，因此，可选加入的人工变量为基变量。然后，再通过基变换，使得基变量中不含非零的人工变量。如果在最终单纯形表中还存在非零的人工变量，这表示无可行解。,44,线性规划求解的人工变量法,45,线性规划求解的人工变量法,46,为了使加入人工变量后线性规划问题的最优目标函数值不受影响，我们赋予人工变量一个很大的负价值系数-M (M为任意大的正数)。 由于人工变量对目标函数有很大的负影响，单纯形法的寻优机制会自动将人工变量赶到基外，从而找到原问题的一个可行基。 这种方法我们通常称其为大M法。,线性规划求解的大M法,47,线性规划求解的大M法,48,【例2.12】用大M法解 下列线性规划,线性规划求解的大M法举例,49,【解】首先将数学模型化为标准形式,式中x4，x5为松弛变量，x5可作为一个基变量，第一、三约束中分别加入人工变量x6、x7，目标函数中加入Mx6Mx7一项，得到人工变量单纯形法数学模型,用前面介绍的单纯形法求解，见下表。,50,51,（1）初始表中的检验数有两种算法，第一种算法是利用第一、三约束将x6、x7的表达式代入目标涵数消去x6和x7，得到用非基变量表达的目标函数，其系数就是检验数；第二种算法是利用公式计算，如 （2）M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；,最优解X（31/3，13，19/3，0，0)T；最优值Z152/3,注意：,52,【例2.13】求解线性规划,53,【解】加入松驰变量x3、x4化为标准型,在第二个方程中加入人工变量x5，目标函数中加上M x5一项，得到,54,用单纯形法计算如下表所示。,表中j0，j=1，2，5，从而得到最优解X=（2，0，0，0，2）， Z=10+2M。但最优解中含有人工变量x50说明这个解是伪最优解，是不可行的，因此原问题无可行解。,55,线性规划求解的两阶段法,56,线性规划求解的两阶段法,然后用单纯形法求解所构造的新模型，若得到w=0，这时，若基变量中不含人工变量，则说明原问题存在基可行解，可进行第二步计算； 否则，原问题无可行解，应停止计算。 第二阶段，单纯形法求解原问题 第一阶段计算得到的最终单纯形表中除去人工变量，将目标函数行的系数，换成原问题的目标函数后，作为第二阶段计算的初始表，继续求解。,57,【例2.14】用两阶段单纯形法求解例【2.12】的线性规划。,58,【解】标准型为,在第一、三约束方程中加入人工变量x6、x7后，第一阶段问题为,用单纯形法求解，得到第一阶段问题的计算表如下：,59,60,最优解为 最优值w=0。第一阶段最后一张最优表说明找到了原问题的一组基可行解，将它作为初始基可行解，求原问题的最优解，即第二阶段问题为,61,用单纯形法计算得到下表,最优解X（31/3，13，19/3，0，0)T；最优值Z152/3,62,【例2.15】用两阶段法求解例【2.13】的线性规划。,63,【解】第一阶段问题为,用单纯形法计算如下表：,64,j0,得到第一阶段的最优解X=(2,0,0,0,2)T,最优目标值w=20,x5仍在基变量中,从而原问题无可行解。,65,解的判断,唯一最优解的判断：最优表中所有非基变量的检验数小于零,则线 规划具有唯一最优解,多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。,无界解的判断: 某个k0且ai