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

*初始单纯形表为XBx1x2x3x4bx3x432－2－1100114?j－1100?λ2=10,x2进基，而a120，a220，没有比值，从而线性规划的最优解无界。由模型可以看出，当固定x1使x2→+∞且满足约束条件，还可以用图解法看出具有无界解。*【例2.11】求解线性规划【解】:化为标准型后用单纯形法计算如下表所示**仍是最优解，从而原线性规划有多重最优解。表(3)表明,非基变量x3的检验数λ3=0,x3若增加,目标函数值不变,即当x3进基时Z仍等于20。使x3进基x5出基继续迭代,得到表(4)的另一基本最优解表(3)中λj全部非正,则最优解为:X(1),X(2)是线性规划的两个最优解，它的凸组合*最优解的判别定理定理1最优解的判别定理1定理2有无穷多最优解的判别定理2*最优解的判别定理定理3有无界解的判别定理*01唯一最优解的判断：最优表中所有非基变量的检验数非零,则线规划具有唯一最优解。03无界解的判断:某个λk0且aik≤０（i=1，2,…,m）则线性规划具有无界解02多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。*单纯形法计算的矩阵描述*单纯形法计算的矩阵描述*单纯形法计算的矩阵描述*单纯形法计算的矩阵描述*单纯形法计算的矩阵描述*单纯形法计算的矩阵描述*单纯形法计算的矩阵描述*线性规划求解的人工变量法若原线性规划问题的系数矩阵中没有单位向量，则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。由于单位阵可以作为基阵，因此，可选加入的人工变量为基变量。然后，再通过基变换，使得基变量中不含非零的人工变量。如果在最终单纯形表中还存在非零的人工变量，这表示无可行解。人工变量法的基本思路是：人工变量法引用人工变量是用单纯形法求解线性规划问题时解决可行解问题的常用方法。*线性规划求解的人工变量法*线性规划求解的人工变量法*

线性规划求解的大M法为了使加入人工变量后线性规划问题的最优目标函数值不受影响，我们赋予人工变量一个很大的负价值系数-M(M为任意大的正数)。由于人工变量对目标函数有很大的负影响，单纯形法的寻优机制会自动将人工变量赶到基外，从而找到原问题的一个可行基。这种方法我们通常称其为大M法。*线性规划求解的大M法*线性规划求解的大M法举例【例2.12】用大M法解下列线性规划*用前面介绍的单纯形法求解，见下表。式中x4，x5为松弛变量，x5可作为一个基变量，第一、三约束中分别加入人工变量x6、x7，目标函数中加入―Mx6―Mx7一项，得到人工变量单纯形法数学模型【解】首先将数学模型化为标准形式**线性规划的图解法与单纯形解法线性规划问题的图解法线性规划单纯形解法的原理线性规划单纯形解法的计算步骤单纯形法计算的矩阵描述线性规划单纯形求解的大M法线性规划单纯形求解的两阶段法线性规划单纯形求解可能的循环现象*图解法，就是用作图的方法求解线性规划问题。简单、直观的图解法一般只适用于具有两个决策变量的线性规划问题。用图解法求解实际线性规划问题，一般按照如下基本步骤：Step1画直坐标系；Step2根据约束条件画出可行域；Step3画过坐标原点的目标函数线；Step4确定目标函数值的增大方向(目标函数线法线方向)Step5目标函数线沿着增大方向平行移动，与可行域相交且有最大目标函数值的顶点，即为线性规划问题的最优解。线性规划问题的图解法#2022*x1x2O1020304010203040(15,10)最优解X=(15,10)最优值Z=85例2.1*246x1x2246最优解X=(3,1)最优值Z=5(3,1)minZ=x1+2x2例2.2*246x1x2246X（2）＝（3,1）X（1）＝（1,3）minZ=5x1+5x2例2.3有无穷多个最优解即具有多重解,通解为0≤α≤1当α=0.5时Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)*246x1x2246无界解(无最优解)maxZ=x1+2x2例2.4*x1x2O10203040102030405050无可行解即无最优解maxZ=10x1+4x