运筹学 第一章 线性规划

《运筹学 第一章 线性规划》由会员分享，可在线阅读，更多相关《运筹学 第一章 线性规划（38页珍藏版）》请在金锄头文库上搜索。

1、1 线性规划及单纯形法1 一般线性规划问题的数学模型2 图解法3 单纯形法原理4 单纯形法的计算步骤5 单纯形法的进一步讨论6 单纯形法的矩阵描述7 应用举例例如，用一块边长为a的正方形铁皮做一个容器 ，应如何裁减，使做成的容器的容积最大？ax这是高等数学中的常 见问题。设被裁减掉的小 正方形边长为x，做成的 容器容积为V，则有V=(a-2x)2x令dV/dx=(a-2x)2-4x(a-2x)=0, 得到x*=a/61 1 一般线性规划问题的数学模型一般线性规划问题的数学模型 1.1 1.1 问题的提出问题的提出这个问题可以用下面的 数学模型来描述。设计划 期内产品、的产量分 别为x1，x2，

2、可获利润用z 表示，则有：例1 某工厂在计划期内要安排生产、两种产 品，已知生产单位产品所需的设备台时和原料A、B 的消耗量如下表。 该工厂 每生产一件产品可获利 2元，每生产一件产品可 获利3元，问应如何安排生 产计划能使该厂获利最多？ 816121 24 00 4设 备 原料 A 原料 B拥有量 max z=2x1+3x2 x1+2x28 4x1 164x212 x1, x20例2 靠近某河流有两个化工厂， 流经第一化工厂的河流流量为每天 500万m3，两工厂之间有一条流量 为每天200万m3的支流（见图）。第一化工厂每天排放污水2万m3 ，第二化工厂每天排放污水 1.4万 m3。污水从工

3、厂1流到工厂2前会 有20%自然净化。根据环保要求， 河水中污水的含量应不大于0.2% 。而工厂1和工厂2处理污水的成本 分别为1000元/万m3和800元/万m3 。问两工厂各应处理多少污水才能 使处理污水的总费用最低？设工厂1和工厂2 每天分别处理污水x1 和x2万m3，则有： min z=1000x1+800x2(2-x1)500 0.0020.8(2-x1)+1.4-x20.002700 x12x21.4x1, x201.2 线性规划问题的数学模型满足以上条件的数学 模型称为线性规划模型。 线性规划模型的一般形式 如下： max(min)z=c1x1+c2x2+cnxn a11x1+a

4、12x2+a1nxn(=, )b1 a21x1+a22x2+a2nxn(=, )b2 am1x1+am2x2+amnxn(=, )bmx1, x2, , xn0例1和例2都有一些共 同的特征：用一组变量表示某 个方案，一般这些变量取 值是非负的。存在一定的约束条 件，可以用线性等式或线 性不等式来表示。都有一个要达到的 目标，可以用决策变量的 线性函数来表示。1.3 线性规划问题的标准形式规定线性规划问题的 标准形式如下： max z=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bmx1, x

5、2, , xn0 其中，bi0 (i=1,2, ,m)(1)目标函数求极大值 ；(2)由资源引起的约束 条件全为等式；(3)约束条件右端常数 项bi全为非负值；(4)变量xj的取值全为 非负。线性规划问题标 准型的要点：松弛变量和剩余变量的性质是相同的，都为了使不等 式约束转化为等式，因此又统称为广义的松弛变量。不符合标准形式的几个方面：目标函数为 min z=c1x1+c2x2+ +cnxn 令z=-z ,变为 max z= -c1x1- c2x2- -cnxn 约束条件为 a11x1+a12x2+a1nxnb1 加入非负变量xn+1，称为松弛变量，有a11x1+a12x2+ +a1nxn+

6、xn+1=b1 约束条件为 a11x1+a12x2+ +a1nxnb1减去非负变量xn+1，称为剩余变量，有a11x1+a12x2+ +a1nxn - xn+1=b1令xj= xj - xj，其中xj, xj 0，对模型中的 进行变量代换。约束条件右端常数项bi0 约束条件左右两端同时乘以-1，注意不等 式两端同乘-1要改变不等式的符号。变量xj0 令xj= -xj ，则xj0，对模型中的进行变量 代换。 变量xj无约束max z=x1-2x2-3x3+3x3“+0x4 +0x52x1+x2+x3- x3“+x4 =93x1+x2+2x3- 2x3“ -x5= 43x1+2x2+3x3- 3x

7、3“ =6x1, x2 , x3, x3“, x4 , x5 0解：令z=-z, x1= -x1, x3= x3- x3“, 则标准形式为:min z=x1+2x2+3x3-2x1+x2+x3 9-3x1+x2+2x3 43x1-2x2-3x3=-6x10, x2 0, x3无约束例3 将下述线性规划模型化为标准形式。其中线性规划问题的标准形式又可简写为：可行解 满足所有约束条件（包括非负条件） 的一组变量值，称可行解。所有可行解的集合称为可行域。最优解 使目标函数值达到最大的可行解称 为最优解。1.4 线性规划问题的解基 对于有n个变量、m个约束方程的标准形 式线性规划问题，取其中m个变量。

8、若这些变量 在约束方程中的系数列向量线性无关，则称这些 变量的系数列向量组成的矩阵为该线性规划问题 的一个基。这组变量称为对应这个基的基变量， 其它n-m个变量称为对应这个基的非基变量。基本解 令非基变量都为0，解约束方程，可 唯一得到基变量的值，从而得到一个满足约束方 程的解，称为基本解。由此可见，一个基本解的非零分量个数不超 过m个。基本可行解 满足非负条件的基本解称为 基本可行解。线 性 规 划 的 解可行解基本解基本可行解max z=2x1+3x2+0x3+0x4 +0x5x1+2x2 +x3 = 84x1 +x4 =164x2 +x5=12xj 0(j=1,2,6)例4 在下述线性规

9、划问题中，举例说明什么是基、基变量、基本解、基本可行解。2 图解法唯一最优解无穷多最优解x1x2x1x2无界解无可行解线性规划问题 如果有最优解,则最 优解一定在可行域 的边界上取得,特别 地,一定可在可行域 的顶点上取得。.max z=2x1+3x2x1+2x284x1 164x212x1, x20通过图解法，可以得出以下结论：1.线性规划问题解的类型有：唯一最优解、无穷多 最优解、无界解、无可行解四种； 2.若线性规划问题的可行域存在，则可行域一定是 凸集； 3.若线性规划问题的最优解存在，则最优解或最优 解之一一定能够在可行域的顶点找到； 4.解题思路：先找出凸集的任一顶点，计算出在顶

10、点处的目标函数值。比较相邻顶点处的目标函数 值是否比这个更优，如果为否，则该顶点就是最 优解的点或最优解的点之一；否则转化到比这个 点目标函数值更优的另一顶点，重复上述过程， 直到找出目标函数值达到最优的顶点为止。3 单纯形法原理 3.1 预备知识凸集 给定集合C，若对任何X(1), X(2)C，都有X(1)+(1-)X(2)C (01) 则称集合C为凸集。顶点 给定凸集C中的点X，若不存在任何两个不 同的点X(1)，X(2)C，使X=X(1) +(1-)X(2) (00中，若有一个k对应的xk的系数 aik0 (i=1,2,m)，则此问题为无界解，停止计算；否 则转。根据 max（j0）=k

11、 确定xk为换入变量；根 据规则：minbi/aik1im, aik0bl/alk 确定相应的换出变量，并得到中心元素alk。转。以alk为中心元素进行旋转运算，得到新的单纯 形表。转.此问题的最优解为: x1*=4, x2*=2, x5*=4, x3*= 0， x4*= 0, z*=24+32=14例5 用单纯形法求解 下述线性规划问题。 Max z=2x1+3x2x1+2x2 84x1 164x2 12x1, x2 0xB x1 x2 x3 x4 x5 bx3x4x51 2 1 0 04 0 0 1 00 4 0 0 18 16 12 j 2 3 0 0 0 0( )x3x4x21 0 1

12、 0 -1/24 0 0 1 00 1 0 0 1/42 163 j 2 0 0 0 -3/4 -9( )x1x4x21 0 1 0 -1/20 0 -4 1 20 1 0 0 1/4283 j 0 0 -2 0 1/4-13( )x1x5x21 0 0 1/4 00 0 -2 1/2 10 1 1/2 -1/8 0442 j 0 0 -3/2 -1/8 0-14Max z=2x1+3x2x1+2x2+x3 =84x1 +x4 =164x2 +x5=12x1, x2, x3 ,x4,x50解：把线性规划问题变成标准形式后，如果并非每个约束条件中都有独有的、系数为1的变量，则需给没有这种变量的每

13、个约束条件中分别添加一个人工变量，这就是人工变量法。同时，为了促使人工变量的取值变为0，可以通过在目标函数中减去大M（代表一个很大的数）乘人工变量的方式，来修改目标函数。这种处 理人工变量的方法称为大M法，详见例6。5 单纯形法的进一步讨论 5.1 人工变量法例6 用单纯形法求解 Min z= -3x1 +x2 +x3x1 -2x2+x3 11-4x1 +x2 +2x3 3-2x2 + x3=1x1, x2, x3 0Max z= 3x1 -x2 -x3 -M x6 -Mx7x1 -2x2 +x3 +x4 =11-4x1 +x2+2 x3 -x5 +x6 =3-2x1 +x3 +x7 =1x1

14、, x2, x3, x4, x5, x6, x70x6, x7称为人工变量此问题的最优解为:x1*=4, x2*=1, x3*= 9, x4*= x5*= x6*= x7*= 0, z*= -34+1 +9 = -25.2 两阶段法两阶段法是处理人工变量的另一种方法。第一阶段，先求解一个目标函数中只包含人工变量的线性规划问题，以得到原线性规划问题的一个基本可行解；第二阶段，利用得到的基本可行解，进一步求解原线性规划问题，以求得最优解。下面通过实例来介绍两阶段法。我们用两阶段法求解例6中的问题。Min z= -3x1 +x2 +x3x1 -2x2+x3 11-4x1 +x2 +2x3 3-2x2 + x3=1x1, x2, x3 0 第一阶段：Max w = - x6 -x7x1 -2x2 +x3 +x4 =11-4x1 +x2+2 x3 -x5 +x6 =3-2x1 +x3 +x7 =1x1, x2, x3, x4, x5, x6, x70得w*=0，转第二阶段。第二阶段：对第一阶段最后的单纯形 表，把人工变量从表中划去， 把目标函数换成原目标函数， 继续用单纯形法求解。是否无界解？前面的求解步骤已作出回答。是否无可行解？ 求解后，若人工变量都已成 为非基变量，则有可行解；否则，无可行解。唯一最优解