第2章 求解线性规划方法 (单纯形法+匈牙利法).ppt

第二章　求解线性规划的主要方法 　　一般有两个变量的线性规划问题有可能利用图 解法求解，但对于具有更多变量的线性规划问题 就无法用图解法求解了，在这里我们介绍一下单纯 形法和匈牙利法。　 　　　　第一节　单纯形法 　　　　　第二节　匈牙利法 第一节 单纯形法 　　 为了表述方便起见，假设我们可研究的线 性规划问题是寻求目标函数的最小值（如果存 在的话），若碰到线性规划问题中寻求目标函 数的最大值，则只需将目标函数中系数的正、 负符号均改成与原来相反的符号即可。这样做 的结果，与求解目标函数的极小值是等效的。 一．单纯形法的指导思想 　　由线性规划原理，我们知道：目标函数的 最小值，能够在可行域 K 的某个顶点达到，而 且顶点的个数是有限的。 　　循着这条思路，可以找到一个使目标函数 达到最小值的途径： 　　这样，用迭代法一次次迭代，经过有限个 步骤就可以求出线性规划问题的最优解。 　　实质上，单纯形法是利用线性规划的基 本原理和迭代的方法来求解目标函数最小值 的一种方法，单纯形法是求解线性规划问题 最主要的方法之一。 二．单纯形法的计算方法 通过下面例子来说明单纯形法的具体计算方法及步骤。 1.引入附加变量x4，x5，使式中 不等式约束变成等式约束： 即　　x1＋x3－x4＝2　（1） 　　　x2＋2x3－x5＝5　（2） 　　　xj≥0 (j=1,2,3,4,5)　（3） 则目标函数变成： 　S＝4x1＋3x2＋8x3＋0x4＋0x5＝min （4） 现有5个变量，即m+n=5，由于未知变量n=2， 故在可行域集合的顶点,5个变量中有3个为0， 即m=3 令x1＝x2＝x3＝0，则由（1）（2）式解出： 　　　x4＝-2 　　　x5＝-5　　　　 　　此解x4，x5不满足xj≥0的条件。 2.因为初始解不在可行域 内，再引入x6、 x7 进行（0）迭代 则约束条件：　 　　　　x1＋x3－x4＋x6＝2 　　 　（5） 　　　　x2+2x3－x5＋x7＝5 　（6） 　　　　xj≥0 (j＝1,2,3,4,5,6,7) 　（7） 　目标函数： S＝4x1＋3x2＋8x3＋Mx6＋Mx7＝min （8） （x4，x5不在可行域） 3.判定 　　7个变量中应选定5个变量为零，才能保证2个约 束条件在可行域顶点处。 零变量称非基本变量，非零变量称基本变量。 若要使S→S min，则本例中首先： 　　令 x1＝x2＝x3＝x4＝x5＝0为非基本变量。 　　　　　x6＝2－x1－x3＋x4 （9） 　　　　　x7＝5－x2－2x3＋x5 （10） 则基本变量： 　　　　　　　x6＝2 　　　　　　　x7＝5 满足xj≥0，则得到一顶点X(0)＝(0,0,0,0,0,2,5)T 判定X(0)＝(0,0,0,0,0,2,5)T是否为最优解。 代入（8）式，相应的 ： S(X(0))＝4x1＋3x2＋8x3＋Mx6＋Mx7＝min S(X(0))＝4x1＋3x2＋8x3＋M(2－x1－x3＋x4) 　　＋M(5－x2－2x3＋x5) 　　　＝(4－M)x1＋(3－M)x2＋(8－3M)x3＋ 　　　 x4＋Mx5＋7M　　　　　（11） 　 　因为M为无限大值，所以(4－M)x1 、 (3－M)x2 、 　(8－3M)x3是负值， S(X(0))不是最优解。 4. 换元 A、原则 将目标函数S中系数为负且最小的元换入（本例为 　(8－3M)x3），作为基本变量。 计算各约束条件式中比值： 　本例由（5）式：Q1＝2/1 　　　由（6）式：Q2＝5/2 （因为Q1Q2，可以将（5）式中基本变量x3换出。） 若换入元中的系数均为负，则该目标函数不存在最优解，为无约束条件。 B．换元后以x3、x7为基本变量； 　 x1、x2、x4、x5、x6为非基本变量。 由（5）式： 　　　x3＝2－x1＋x4－x6 （13） 由（6）式、（13）式： x7＝5－x2－2x3＋x5＝1＋2x1―x2―2x4＋x5＋2x6 （14） 令x1＝x2＝x4＝x5＝x6＝0， 求解（13）、（14）式得： 　　　　　　x3＝2 　　　　　　x7＝1 　　得到了新的顶点X(1)＝(0,0,2,0,0,0,1)T 判别新的顶点X(1)＝(0,0,2,0,0,0,1)T是否为最优解。 　 　　S＝4x1＋3x2＋8(2－x1＋x4－x6 )＋Mx6＋ 　　　　　 M(1＋2x1―x2―2x4＋x5＋2x6) 　　＝(2M－4)x1＋(3－M)x2＋(8－2M)x4＋