04第四章 线性规划的求解法

第四章线性规划的求解法当线性规划的变量和约束条件比较多，而初始基本可行解又不知道时，是不容易用尝试的方法得到初始基本可行解的，何况有可能基本可行解根本就不存在。在此时，大M法可能是应付此类情况的一个行之有效的算法。§4.1大M法的原理当初始基本可行解不知道时，则1.，2.两个特点不能兼得，即下列两条件不能兼得：中心部位具有单位子块；右列元素非负；这时可以先用容许的运算使由列为非负，然后在中心部位人为添加一个单位子块。如下例所述例4.1minz=一3x+x+2x1 2 3s.t.4.1.1)3x+2x一3x=6s.t.4.1.1)123一x+2x一x=一41 2 3x,x,x>01233 2-36-13 2-36-12-1-4-3 1 20列成表格：32-3632-3106>1-214>1-21014=>=>-3120-3120上述第三张表中人工增加了两个变量x,x，称为人工变量，即把原来的约束条件改为：45s.t. 3x+2x一3x+x=61 2 3 4x一2x+x+x=4 (4.1.2)1 2 3 5x,x,x,x,x>012345式(4.1)和(4.2)的约束方程组并不同解，但(4.1)的解和(4.2)中x=x=0的解45是相对应的。只要找到以(4.2)为约束条件，且人工变量x,x均为自由变量的基本可行45解，也就找到了(4.1)的基本可行解，于是，要设法迫使x=x=0。45以上途径通过修改(4.1)的目标函数来实现。具体修改为：

minz=-3x+x+2x+Mx+Mx (4.1.3)1 2 3 4 5其中M为足够大的正数，然后以(4.2)为约束条件，求(4.3)的最小值。只要x,x不为45零，就一定为正数，于是目标函数的值就会增加它们和的M倍。由于M为足够大的正数，所以只要原问题有基本可行解，就不会在x,x取正值时达到最小值。本例中把表改为：453 2-31061-21014-3 1 2 M M0通过运算使它具备第三个特点：底行相应于单位子块位置的元素为0，然后再严格按照单纯形法的步骤求解：③2-31061-21014-3-4M*12+2M0010M由于M为足够大的正数，所以-3-4M应视为负数，故选它。经过一次迭代：12/3-11/3020-8/3②-1/312083+一M-1-2M*41+一M0 6-2M33再经过一次迭代：1-2/301/30 30-4/31-1/31/2105/305一+M-+M 762这时表已经具备四个特点，且人工变量x,x亦已成为自由变量，所以从表上可直接读45出(4.1)的最优解：x=3,x=0,x=1，且x=x=0。把引进的自由变量略去，则最12345优解为x*=(3,0,1)T，最优值为z*=-7。§4.2两阶段法的原理使用单纯形方法，需要给定一个初始基本可行解，以便从这个基本可行解出发，求改进的基本可行解，最终达到最优解。下面介绍如何求出一个初始基本可行解，设标准形式的线性规划问题

4.2.1)minz=cTx4.2.1)s.t.Ax=bx>0其中A是mxn矩阵，b>0。若A中含有m阶单位矩阵，则初始基本可行解立即可得。比如：A=[i,N]=[B,N]，那么m就是一个基本可行解。若A中不包含m阶单位矩阵，则可从两阶段法入手，先求得个初始基本可行解。先引入人工变量的概念。设A中不包含m阶单位矩阵，为了使约束方程的系数矩阵中含有m阶单位矩阵，把每一个方程增加一个非负变量，令4.2.2)Ax+x=b4.2.2)ax>0,x>0a即(A,I)(A,I)mx>0,=bxax>0

a4.2.3)显然x-0—xba是（4.2.3）的一个基本可行解。当然式子（4.2.3）已经不是原来的约束，构造（4.2.3）式的意义在于，若从（4.2.3）式的已知的基本可行解出发，能够求出一个使得x=0的基本可行解，那么也就可以得到a（4.2.1）式的一个基本可行解。向量x>0是人为引进的，它的每个分量称为人工变量。人工变量与前面介绍的松弛a变量是两个不同的概念。松弛变量的作用是把不等式约束改写为等式约束，改写前后的两个问题是等价的。松弛变量的取值能够表达现行的可行点是在可行域的内部还是在其边界。也就是说，在此可行解处，原来的约束是严格不等式成立还是等式成立的区别。因此松弛变量是“合法”的变量。而人工变量的引进，改变了原来的约束条件，从这个意义上讲，它们是不合法”的变量。两阶段法的第一阶段是用单纯形法消去人工变量，即把人工变量都变换成非基变量求出原问题的一个基本可行解。minf=eTxas.t.Ax+x=b (4.2.4)ax>0,x>0a其中e=(1,1,...,1)t是分量全是1的m维列向量，x=(xx )t是人工变量构成a n+1 n+m的m维列向量。由于x=0,x=b是线性规划(4.2.4)的一个基本可行解，目标函数在可a行域上有下界，因此问题(4.2.4)必存在最优基本可行解。设最优基本可行解是(xT,xT)T，这时有三种情况。a1、x工0，这时线性规划(4.2.1)无可行解，因为如果线性规划(4.2.1)存在可行a解x，贝I」xxx0a是线性规划(4.2.4)的可行解，在这一点上，问题(4.2.4)的目标函数的值f=0Ox+eTDO<eTxa这和eTx是目标函数的最优值矛盾。a2、x=0且x的分量都是非基变量，这时m个基变量都是原来的变量，又知:aaxxx0a是线性规划(4.2.4)的基本可行解，因此，x=x是线性规划(4.2.1)的一个基本可行解。3、x=0且x的某些分量都是非基变量，这时可以用主元消去法，使原来变量中的某aa些非基变量进基，替换出基变量中的人工变量，再开始两阶段法的第二阶段。应当指出，为替换出基变量中的人工变量而采用的主元消去法，并不要求遵守单纯形法确定的离基进基变量的规贝。两阶段法的第二阶段，用单纯形法求线性规划(4.2.1)的最优解，初始的基本可行解就是从第一阶段所得到的基本可行解。例4.2用两阶段法求下列线性规划问题的最优解maxz=2x一x12s.t. x+x>212x一x>1 （4.2.5）12x<31x,x>012先引进松弛变量x,x,x，把问题化为标准形式。由于标准形式中约束方程的系数矩345阵并不包含三阶单位矩阵，因此还要引进人工变量x,x。下面先求解第一阶段的问题：67minx+x67s.t.x1+x一x+x6=223x一x一x+x=11247x+x=315x,x,x,x,x,x,x>01234567用表格形式表示：11-1001021-10-100111000100300000110为了满足单纯形法的第三个特点：底行相应于单位子块位置的元素为0，对上表做初等11-100102①-10-1001110001003-2*011000-3由单纯形法（或主元消去法），得：0②-1101-111-10-10011010110-120-2*1-1002-1再进行一次：01-1/21/201/2-1/21/210-1/2-1/201/21/23/2001/21/21-1/2-1/23/200000110变换，使x,x所对应的底行单位子块位置的元素为0。得：67

这时已经满足单纯形法的全部条件，达到最优解。在第一阶段的最优解中，人工变量x,x都是非基变量，这样得到初始基本可行解为：(31—(31—,0,0,(22(x,x,x,x,x)=12345第一阶段结束后，修改最后的单纯形表，去掉人工变量x,x下面的列，然后开始第二67阶段的迭代，即求目标函数minf=-2x+x。1201-1/21/201/210-1/2-1/203/2001/21/213/2-210000同理，为了满足单纯形法的第三个特点：底行相应于单位子块位置的元素为0，对上表做初等变换，使x,x所对应的底行单位子块位置的元素为0。得：1201-1/2©01/210-1/2-1/203/2001/21/213/200-1/2-3/2*05/2上表已经具备单纯形法的三个特点，于是在底行中任选一个负元素，02-110111-10020-1①01103-2*004再进行一次迭代，得：0101121000130-11011010026上表已满足单纯形法的四个特点，从而得到线性规划(4.2.5)的最优解(x,x)=(3,0),12目标函数的最优值f=6。max§4.3灵敏度分析通过一个案例来理解灵敏度的问题。

例4.3设某厂在资源甲、乙的限制下，考虑制定能使总利润达到最大的三种产品A、B、C的生产计划，其有关数据如下：maxz=3x+x+4x1 2 3s.t. 6x+3x+5x<451 2 3 （4.3.1）3x+4x+5x<30

123x,x,x>0123化为标准形式：minf=一3x一x一4x1 2 3s.t. 6x+3x+5x+x=451234 （4.3.2）3x+4x+5x+x=301 2 3 5x,x,x,x,x>012345其中x,x分别是关于资源甲、乙而引进的松弛变量，列成表格:4 5 _ _ - 小 ，一4563 5104534 50130-3-1 -4000用单纯形法经过两次迭代即可终止，得1-1/3 01/3-1/35011-1/52/530201/53/527读出的最优解为:x=5,x=0,x=1233,x=0,4x=0，标准形的最优值为f=-27，即原问题5的最大利润为z=27。最优解为x*=（5,0,3）T，即产品A生产5吨，产品B生产0吨，产品C生产3吨，这时的综合利润最大，为27千元。在此基础上进一步考虑一些问题，例如1、两种资源中哪种资源的拥有量是制约利润进一步提高的因素？以x=5,x=0,x=3代入（4.4）约束:123s.t. 6x+3x+5x<45（资源甲的约束）1233x+4x+5x<30（资源乙的约束）123我们发现，约束条件中的不等式全部变成了等式，这说明在此生产计划下的两种资源均已用尽，故两种资源的拥有量均是制约利润进一步提高的因素。关于最后的解是否使得不等式变成等式，可以简单地以相应的松弛变量是否取值为0加以判断。在本例中，x=x=045说明两个约束都达到了极限，都成为制约利润进一步提高的因素。2、 若在市场上能按比正常价贵0.5千元的单价买到资源甲、乙，问为了进一步提高利润是否应买？我们从最后的一张表中可以看出原问题等价于在原有的约束条件下求：1 3maxz=-2x一x一x2 54 55注意到其中x,x分别表示资源甲、乙的数量，由此可以看出在最优生产计划的水平下，45资源甲的数量每变化一个单位对总利润z的影响是1/5千元，相应的资源乙的数量每变化一个单位对总利润z的影响是3/5千元，在经济学上分别称1/5千元、3/5千元为资源甲、乙的影子价格。对于目前所提的问题，由于单位利润是在正常价格下计算的，所以若在市场上按高于正常价格购买资源甲、乙，则净利润就要在总利润中减去高出的部分。资源甲在当前的计划生产水平下，每投入1吨甲资源对总利润的贡献为1/5=0.2千元，而购买成本要高出0.5千元，因此不合算；同样的理由，每投入1吨乙资源对总利润的贡献为3/5=0.6千元，扣除高出的0.5千元的成本，还有0.1千元的利润可赚，因此资源甲不应购买、资源乙可以买。3、 若通过提高售价来提高B产品的单位利润，问B产品的单位利润要提高多少千元，才能仍在追求最大利润的目标下考虑生产B产品?解：设B产品的单位利润要增加C千元才考虑生产B产品。则（4.5）式改为:4530-3 —(1+C) -4 0 0 "o"在底行的第二个系数上增加-C，经过两次迭代，得:1-1/301/3-1/35011-1/52/5302-C01/53/527

可以这样分析，底行中若C<2,则上表已经具有四个特点，运算终止，最优解不变，x仍2为0只有当C>2，上表不具备第四个特点，需要继续运算，才能让x作基变量，即x的22取值才可以不为0所以本问题的回答是C>2。123s.t.123s.t.2x一x+x>81232x+3x+2x<201234x一x=823x>j0,j1,2,3解：列成表格：2-11822 322020 4-18=>03 5703习题4.1用大M法计算以下线性规划minf=3x+5x+7x（习题4.1）-11-1083 2 0 1204-1008=>5 7 0 002-11-102 3 2 0 12-11-102 3 2 0 10 4-10020835700MM~0~上述第一张表中，先引进一个剩余变量x，一个松弛变量x，将问题化为标准型，变45成第二张表，其形式为：minf=3x+5x+7x123s.t. 2x一x+x一x=8TOC\o"1-5"\h\z1 2 3 42x+3x+2x+x=20 （习题4.2）1 2 3 54x一x =823x>0,j=1,2,3,4,5j松弛变量x可以作为初始基本变量，但是第二张表中没有单位子阵，因而人工再增加5两个变量x,x，称为人工变量，即把原问题改为：67

minf=3x+5x+7x+Mx+Mx1 2 3 67s.t. 2x一x+x一x +x=81 2 3 4 62x+3x+2x +x=20（习题4.3）1 2 3 54x一x+x=8237x>0,j=1,2,3,4,5,6,7j式（习题4.1）和（习题4.3）的约束方程组并不同解，但（习题4.1）的解和（习题4.3）中x=x=x=x=0的解是相对应的。只要找到以（习题4.3）为约束条件，且人工变4567量x,x,x,x均为自由变量的基本可行解，也就找到了（习题4.3）的基本可行解，于是,4567要设法迫使=x要设法迫使=x=0。（习题4.4）以上途径通过修改（习题（习题4.4）minf=3x+5x+7x+Mx+Mx1 2 3 6 7其中M为足够大的正数，然后以（习题4.3）为约束