图解法与单纯形法改PPT课件

1、x1x2O1020304010203040(15,10)最优解最优解X=(15,10)最优值最优值Z=8540221 xx305 . 121xx0, 0305 . 1402212121xxxxxx例题例题2143maxxxZ第2页/共69页第1页/共69页2.1 线性规划问题的图解法 用图解法求解如下线性规划问题： 例112121212max23 2212 416 515 ,0 zxxxxxxx x（1）（2）（3）（4）第3页/共69页第2页/共69页2.1 线性规划问题的图解法求解Q3点为（3，3），此时z=15第4页/共69页第3页/共69页2.1 线性规划问题的图解法本例中我们用图解法

2、得到的问题的最优解是惟一的。 但在线性规划问题的计算中,解的情况还可能出现下列几种:1 无穷最优解。如将本例的目标函数改变为 则目标函数的图形恰好与(1)平行。因此该线性规划问题有无穷多个最优解,也称具有多重最优解。12max33zxx第5页/共69页第4页/共69页2.1 线性规划问题的图解法 2. 无界解 (有可行解但无有界最优解)。 如果本例中约束条件只剩下(2)和(4),其他条件(1)、(3)不再考虑。 用图解法求解时, 可以看到变量的取值可以无限增大, 因而目标函数的值也可以一直增大到无穷。这种情况下称问题具有无界解或无最优解。 其原因是由于在建立实际问题的数学模型时遗漏了某些必要的

3、资源约束。12112max23 416 ,0 zxxxx x（2）（4）第6页/共69页第5页/共69页2.1 线性规划问题的图解法 3. 无可行解。如下述线性规划模型： 用图解法求解时找不到满足所有约束条件的公共范围，这时问题无可行解。其原因是模型本身有错误, 约束条件之间相互矛盾, 应检查修正。 12max23zxx1212122212. .214,0 xxstxxx x第7页/共69页第6页/共69页图解法虽然只能用来求解只具有两个变量的线性规划问题图解法虽然只能用来求解只具有两个变量的线性规划问题, , 但它的解题思路和几何上直观得到的一些概念判断但它的解题思路和几何上直观得到的一些概

4、念判断, , 对下面对下面要讲的求解一般线性规划问题的单纯形法有很大启示要讲的求解一般线性规划问题的单纯形法有很大启示: :线性规划问题求解的基本线性规划问题求解的基本依据是：线性规划问题的依据是：线性规划问题的最优解总可在可行域的顶最优解总可在可行域的顶点中寻找，寻找线性规划点中寻找，寻找线性规划问题的最优解只需比较有问题的最优解只需比较有限个顶点处的目标函数值。限个顶点处的目标函数值。线性规划问题求解时可能线性规划问题求解时可能出现四种结局：出现四种结局：唯一最优解唯一最优解无穷多个最优解无穷多个最优解无有界解无有界解无解或无可行解无解或无可行解如果某一线性规划问题有如果某一线性规划问题有

5、最优解，可以按照以下思最优解，可以按照以下思路求解：先找可行域中的路求解：先找可行域中的一个顶点，计算顶点处的一个顶点，计算顶点处的目标函数值，然后判别是目标函数值，然后判别是否有其他顶点处的目标函否有其他顶点处的目标函数值比这个顶点处的目标数值比这个顶点处的目标函数值更大，如有，转到函数值更大，如有，转到新的顶点，重复上述过程，新的顶点，重复上述过程，直到找不到使目标函数值直到找不到使目标函数值更大的新顶点为止。更大的新顶点为止。第8页/共69页第7页/共69页线性规划的基本性质 凸集 对集合C中任意两个点 其连线上的所有点都是集合C中的点，则C为凸集。 由于 的连线可以表示为 ，因此凸集的

6、数学表达为：对任意的 ，有 则称C为凸集。 12XX、12(1 ) (01 )aXaXa 12XX、12,XC XC12(1)C (01)aXa Xa第9页/共69页第8页/共69页 线性规划的基本性质若线性规划问题存在可行域，则其可行域一定是凸集。 引理 线性规划问题的可行解X=( x1, x2, xn)T为基可行解的充要条件是X的正分量对应的系数列向量是线性独立的。 线性规划问题的基可行解对应可行域的顶点。若线性规划问题有最优解，一定存在一个基可行解是最优解。 第10页/共69页第9页/共69页 从可行域中的一个基可行解出发，判别它是否已经是最优解，如果从可行域中的一个基可行解出发，判别它

7、是否已经是最优解，如果不是，寻找下一个基可行解，并且同时努力使目标函数得到改进，不是，寻找下一个基可行解，并且同时努力使目标函数得到改进，如此迭代下去，直到找到最优解或判定问题无解为止。如此迭代下去，直到找到最优解或判定问题无解为止。基本思想：基本思想：2.2 2.2 线性规划单纯形法的原理与计算步骤线性规划单纯形法的原理与计算步骤3 3 寻找改进寻找改进的基可行解的基可行解2 2 最优性检最优性检验和解的判验和解的判别别1 1 确定初始确定初始基可行解基可行解第11页/共69页第10页/共69页【例2】用单纯形法求下列线性规划的最优解 0,30340243max21212121xxxxxxx

8、xZ第12页/共69页第11页/共69页单纯形法的计算步骤： 步骤1：求初始基可行解，列出初始单纯形表。 对非标准形式的线性规划问题首先要化成标准形式。 由于我们总可以设法使约束方程的系数矩阵中包含一个单位矩阵P1,P2,Pm ，以此作为基即可求得问题的一个初始基可行解。必须是标准形式必须是标准形式第13页/共69页第12页/共69页【解】首先化为标准型，加入松驰变量x3、x4则标准型为系数矩阵A及可行基B1r(B1)=2，B1是单位矩阵作为初始基,x3、x4为基变量，x1、x2为非基变量，令x1=0、x2=0由约束方程知x3=40、x4=30得到初始基可行解X(1)=(0,0,40,30)T

9、 0,30340243max432142132121xxxxxxxxxxxxZ10310112A10011B第14页/共69页第13页/共69页单纯形法的计算步骤： 步骤2 最优性检验 在单纯形表中，若所有的检验数 表中的基可行解即为最优解。若存在 并且有 ，则问题无有界解。计算结束。否则转入下一步。 步骤3 从一个基可行解转换到相邻的目标函数更大的基可行解，列出新的单纯形表。 步骤4 重复步骤2和3，一直到计算结束。0jP 0j0j第15页/共69页第14页/共69页进基列出基行bi /ai2，ai20i表表1-4(1)XBx1x2x3x4bx3211040 x4130130 j3400 (

10、2)x3x2 j (3)x1 x2 j 基变量110001/301/3105/31- -1/3405/30- -4/330103/5- -1/51801- -1/5 2/5400- -1- -1将3化为1乘以1/3后得到3018第16页/共69页第15页/共69页单纯形算法的计算步骤 将线性规划问题化成标准型。找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。计算各非基变量xj的检验数 j，若所有 j0，则问题已得到最优解，停止计算，否则转入下步。在大于0的检验数中，若某个 k所对应的系数列向量Pk0，则此问题是无界解，停止计算，否则转入下步。根据max j j0= k原则，确定xk

11、为换入变量(进基变量)，再按 规则计算： =minbi/aik| aik0=bl/ aik 确定xl为换出变量。建立新的单纯形表，此时基变量中xk取代了xl的位置。以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik变为1，同列中其它元素为0，转第 步。 第17页/共69页第16页/共69页2.2 线性规划单纯形法的原理与计算步骤 单纯形法计算中可能出现以下两种情况： 出现两个以上 ，原则上可任取一个 对应的为换入基的变量； 相持。 即计算值出现两个以上相同 的最小值。则可任选其中一个基变量作为换出变量。 但是为防止出现循环现象，先后有人提出了一些方法。如：勃兰特法；字典序法

12、；摄动法。 （1选取检验数中下标最小的非基变量为换入变量 （2按 规则计算时，若出现两个和两个以上的最小比值时，选取下标最小的基变量为换出变量。maxjjx第18页/共69页第17页/共69页单纯形法的计算 用单纯形法求解线性规划问题： 例312121212max2322124 16. . 515,0 zxxxxxs txxx第19页/共69页第18页/共69页最优解的判别定理 定理1 最优解的判别定理 定理2 有无穷多最优解的判别定理 第20页/共69页第19页/共69页单纯形法的计算 用单纯形法求解线性规划问题： 例412121212max3322124 16. . 515,0 zxxxx

13、xs txxx第21页/共69页第20页/共69页最优解的判别定理 定理3 有无界解的判别定理 第22页/共69页第21页/共69页单纯形法的计算 用单纯形法求解线性规划问题： 例题512112max234 16. .,0 zxxxs txx第23页/共69页第22页/共69页XBx1x2x3x3401j230第24页/共69页第23页/共69页唯一最优解的判断：唯一最优解的判断：最优表中所有非基变量的检验数最优表中所有非基变量的检验数 小于零小于零,则线规划具有唯一最优解则线规划具有唯一最优解 。多重最优解的判断多重最优解的判断:最优表中存在非基变量的检验数为最优表中存在非基变量的检验数为零

14、零,则线则性规划具有多重最优解。则线则性规划具有多重最优解。无界解的判断无界解的判断: 某个某个 且且aij（i=1，2,m）则）则线性规划具有无界解线性规划具有无界解0j第25页/共69页第24页/共69页【练习1】 用单纯形法求解02053115232321321321xxxxxxxxx、3212maxxxxZ第26页/共69页第25页/共69页Cj12100bCBXBx1x2x3x4x50 x423210150 x51/3150120j12100 0 x42x2j 1x1 2x2 j 表151/3150120301713751/30902M2025601017/31/31250128/9

15、1/92/335/30098/91/97/3最优解最优解X=(25，35/3，0，0，0)T，最优值，最优值Z=145/3第27页/共69页第26页/共69页21maxxxZ0,42123212121xxxxxx【练习2】求解线性规划【解】化为标准型21maxxxZ4 , 1, 042123421321jxxxxxxxj第28页/共69页第27页/共69页初始单纯形表为XBx1x2x3x4bx3x43221100114j1100 2=10, x2为换入变量，而第二列的数字均小于0，因此线性规划的最优解无有界解。由模型可以看出，当固定x1使x2+且满足约束条件，还可以用图解法看出具有无界解。第2

16、9页/共69页第28页/共69页【练习3】求解线性规划2142maxxxZ0,21024221212121xxxxxxxx【解】:化为标准型后用单纯形法计算如下表所示第30页/共69页第29页/共69页XBx1x2x3x4x5b(1)x3x4x5111221100010001410225j24000(2)x2x4x51/221/21001/211/201000126438j40200(3)x2x1x50101001/41/23/41/41/21/40017/235/21410/3j00020(4)x2x1x30101000011/31/31/31/32/34/38/314/310/3j0002

17、0第31页/共69页第30页/共69页 表 (3)中j全部非正,则最优解为:20,)25, 0 , 0 ,27, 3()1(ZXT 表 (3)表明,非基变量x3的检验数3=0, 使x3作为换入变量， x5为换入变量继续迭代 ,得到表(4)的另一 基本最优解 X(1),X(2)是线性规划的两个最优解，它的凸组合20,) , 0 , 0 ,310,38,314)2(ZXT（) 10()1 ()2()1(XXX 仍是最优解，从而原线性规划有多重最优解。第32页/共69页第31页/共69页单纯形法计算的矩阵描述第33页/共69页第32页/共69页单纯形法计算的矩阵描述 第34页/共69页第33页/共6

18、9页单纯形法计算的矩阵描述第35页/共69页第34页/共69页单纯形法计算的矩阵描述第36页/共69页第35页/共69页单纯形法计算的矩阵描述第37页/共69页第36页/共69页单纯形法计算的矩阵描述第38页/共69页第37页/共69页 人工变量法 人工变量法的基本思路是： 若原线性规划问题的系数矩阵中没有单位向量，则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。 2.3线性规划单纯形法的进一步讨论第39页/共69页第38页/共69页线性规划求解的人工变量法第40页/共69页第39页/共69页线性规划求解的人工变量法第41页/共69页第40页/共69页由于单位阵作为基阵，因

19、此，选加入的人工变量为基变量。然后，再通过基变换，使得基变量中不含非零的人工变量。如果在最终单纯形表中还存在非零的人工变量，这表示无可行解。 大大M M法法两阶段法两阶段法第42页/共69页第41页/共69页第43页/共69页第42页/共69页 为了使加入人工变量后线性规划问题的最优目标函数值不受影响，我们赋予人工变量一个很大的负价值系数-M (M为任意大的正数)。线性规划求解的大M法第44页/共69页第43页/共69页线性规划求解的大M法第45页/共69页第44页/共69页 由于人工变量对目标函数有很大的负影响，单纯形法的寻优机制会自动将人工变量赶到基外，从而找到原问题的一个可行基。 这种方

20、法我们通常称其为大M法。第46页/共69页第45页/共69页【例6】用大M法解 下列线性规划012210243423max321321321321321xxxxxxxxxxxxxxxZ、线性规划求解的大M法举例第47页/共69页第46页/共69页【解】首先将数学模型化为标准形式5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj式中x4为剩余变量，x5为松弛变量，x5可作为一个基变量，第一、三约束中分别加入人工变量x6、x7，目标函数中加入Mx6Mx7一项，得到人工变量单纯形法数学模型用前面介绍的单纯形法求解，见下表。 7 , 2

21、 , 1, 012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj第48页/共69页第47页/共69页Cj32100MMbCBXBx1x2x3x4x5x6x7M0Mx6x5x74123121211000101000014101j3-2M2+M-1+2MM000M01x6x5x3632532001100010100381j5-6M5M0M00201x2x5x36/53/52/51000011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j0005-25

22、/3第49页/共69页第48页/共69页最优解最优解X（31/3，13，19/3，0，0)T；最优值；最优值Z152/3注意：注意：M是一个很大的抽象的数，不需要给是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大出具体的数值，可以理解为它能大于给定的任何一个确定数值；于给定的任何一个确定数值；第50页/共69页第49页/共69页【练习】1212122212. .214,0 xxstxxx x12max23zxx第51页/共69页第50页/共69页线性规划求解的两阶段法 第52页/共69页第51页/共69页线性规划求解的两阶段法第二阶段，单纯形法求解原问题第一阶段计算得到的最终单纯形

23、表中除去人工变量，将目标函数行的系数，换成原问题的目标函数后，作为第二阶段计算的初始表，继续求解。 第53页/共69页第52页/共69页【例】用两阶段单纯形法求解例【6】的线性规划。012210243423max321321321321321xxxxxxxxxxxxxxxZ、第54页/共69页第53页/共69页【解】标准型为5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj在第一、三约束方程中加入人工变量x6、x7后，第一阶段问题为7 , 2 , 1, 0122102434min732153216432176jxxxxxxxxx

24、xxxxxxxwj用单纯形法求解，得到第一阶段问题的计算表如下：用单纯形法求解，得到第一阶段问题的计算表如下：第55页/共69页第54页/共69页Cj00000-1-1 bCBXBx1x2x3x4x5x6x7-10-1x6x5x74123121211000101000014101j-212-1000 -100 x6x5x3632532001100010100 381j-650-100 000 x2x5x36/53/52/51000011/53/52/5010 3/531/511/5j00000 第56页/共69页第55页/共69页最优解为 最优值w=0。第一阶段最后一张最优表说明找到了原问题的

25、一组基可行解，将它作为初始基可行解，求原问题的最优解，即第二阶段问题为)5310 ,511,53, 0(X123124145134max32613555333155522115550,1,2,5jZxxxxxxxxxxxxxj第57页/共69页第56页/共69页Cj32100bCBXBx1x2x3x4x5201x2x5x36/53/52/51000011/53/52/50103/531/5 11/5j5 0000 231x2x1x301010000111025/32/31331/319/3j000525/3 用单纯形法计算得到下表用单纯形法计算得到下表最优解最优解X（31/3，13，19/3，

26、0，0)T；最优值；最优值Z152/3第58页/共69页第57页/共69页【练习练习】用两阶段法求解线性规划。用两阶段法求解线性规划。0,426385min21212121xxxxxxxxZ第59页/共69页第58页/共69页【解解】第一阶段问题为第一阶段问题为5 , 2 , 1, 04263min54213215jxxxxxxxxxwj用单纯形法计算如下表：第60页/共69页第59页/共69页Cj0000-1bCBXBx1x2x3x4x50-1x3x5311210010164j 1-20-10 0-1x1x5101/37/31/31/3010122j 0-7/3-1/3-10 j0,得到第一

27、阶段的最优解得到第一阶段的最优解X=(2,0,0,0,2)T,最优目标值最优目标值w=20,x5仍在基变量中仍在基变量中,从而原问题无可行解。从而原问题无可行解。第61页/共69页第60页/共69页解的判断解的判断唯一最优解的判断：最优表中所有非基变量的检验数小于零,则线性规划具有唯一最优解 多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。 无界解的判断: 某个k0且aik（i=1，2,m）则线性规划具有无界解无可行解的判断：(1)当用大M单纯形法计算得到最终单纯形表中存在非零的人工变量，则表明原线性规划问题无可行解。(2) 当第一阶段的最优值w0时，则原问题无可行解。第62页/共69页第61页/共69页【习题1】配料问题。某钢铁公司生产一种合金，要求的成分规格是：锡不少于28%，锌不多于15%，铅恰好10%，镍要界于35%55%之间，不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶炼，每种矿物的成分含量和价格如表1.4所示。矿石杂质在治炼过程中废弃，现要求每吨合金成本最低的矿物数量。假设矿石在冶炼过程中，合金含量没有发生变化。表1.4 矿石的金属含量 合金