线性规划及单纯形法

《线性规划及单纯形法》由会员分享，可在线阅读，更多相关《线性规划及单纯形法（88页珍藏版）》请在金锄头文库上搜索。

1、第二章 线性规划及单纯形法 1 线性规划问题及模型 2 图解法 3 单纯形方法及大M法 4 线性规划应用举例分析11 问题的提出例1. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所 需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位、产品才能使工厂获利最多？线性规划模型：目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 300 2 x1 + x2 400x2 250x1 , x2 02线性规划的组成要素：目标函数 Max F 或 Min F约束条件 s.t. (subject to) 满足于决策变量 用

2、符号来表示可控制的因素建模步骤1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（ x1 ，x2 ， ，xn ），每一组值表示一 个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最 小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵 循的约束条件3 一般形式目标函数： Max （Min） z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn x

3、n （ =, ）bmx1 ，x2 ， ，xn 0 4对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作 图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方 法。例1.目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 300 (A)2 x1 + x2 400 (B)x2 250 (C)x1 0 (D)x2 0 (E)2 图 解 法5（1）画出线性规划问题的可行域，如图所示。x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图16（2）目标函数z=50x1+100x2，当z取某一固定值时得到一条直 线，直线上的

4、每一点都具有相同的目标函数值，称之为“等 值线”。平行移动等值线，当移动到B点时，z在可行域内实 现了最大化。得到最优解： x1 = 50， x2 = 250， 最优目 标值 z = 27500x1x2z=20000=50x1+100x2图2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBAD E7例2 某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共

5、有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？8解：目标函数： Min f = 2x1 + 3 x2约束条件： s.t. x1 + x2 350x1 1252 x1 + x2 600x1 , x2 0采用图解法。如下图：得Q点坐标（250，100）为最优解。100200300 400 500 600100200300400600500x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x1+x2 =6002x1+3x2 =1200x1 x

6、2 Q9 重要结论： 如果线性规划有最优解，则一定有一个可行域 的顶点对应一个最优解； 无穷多个最优解。若将例1中的目标函数变为 max z=50x1+50x2，则线段BC上的所有点都代表 了最优解； 无界解。即可行域的范围延伸到无穷远，目标 函数值可以无穷大或无穷小。一般来说，这说 明模型有错，忽略了一些必要的约束条件； 无可行解。若在例1的数学模型中再增加一个约 束条件4x1+3x21200，则可行域为空域，不存在 满足约束条件的解，当然也就不存在最优解了 。10 线性规划的标准化引入松驰变量（含义是资源的剩余 量）例1 中引入 s1， s2， s3 模型化为目标函数：Max z = 50

7、 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3约束条件：s.t. x1 + x2 + s1 = 3002 x1 + x2 + s2 = 400x2 + s3 = 250x1 , x2 , s1 , s2 , s3 0对于最优解 x1 =50 x2 = 250 ， s1 = 0 s2 =50 s3 = 0说明：生产50单位产品和250单位产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。11线性规划的标准化 线性规划标准形式目标函数： Max z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 +

8、+ a1n xn = b1a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bmx1 ，x2 ， ，xn 0，bi 012可以看出，线性规划的标准形式有如下四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:131.极小化目标函数的问题：设目标函数为Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f ，则该极小化问题与下面的极大化问题有相同的最优解，即 Max z = - c1x1 - c2x2 - - cn

9、xn 但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即Min f - Max z142、约束条件不是等式的问题：设约束条件为ai1 x1+ai2 x2+ +ain xn bi可以引进一个新的变量s ，使它等于约束右边与左边之差s=bi(ai1 x1 + ai2 x2 + + ain xn )显然，s 也具有非负约束，即s0，这时新的约束条件成为ai1 x1+ai2 x2+ +ain xn+s = bi15当约束条件为ai1 x1+ai2 x2+ +ain xn bi 时，类似地令s=(ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非

10、负约束，即s0，这时新的约束条件成为ai1 x1+ai2 x2+ +ain xn-s = bi16为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。3.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非 负。当某一个右端项系数为负时，如 bi0，则把该 等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2- -ain xn = -bi。17例：将以下线性规划问题转化为标准形式 Min f = 2 x1 -3x2

11、+ 4 x3s.t. 3 x1 + 4x2 - 5 x3 62 x1 + x3 8x1 + x2 + x3 = -9x1 , x2 , x3 0 解：首先,将目标函数转换成极大化：令 z= -f = -2x1+3x2-4x3 其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 0。第三个约束条件的右端值为负，在等式两边同时乘-1。18通过以上变换，可以得到以下标准形式的线性规划问题： Max z = - 2x1 + 3 x2 - 4x3s.t. 3x1+4x2-5x3 +x4 = 62x1 +x3 -x5= 8-x1 -x2 -x3 = 9x1 ,x2 ,x3 ,x4 ,x5 0在标准形式

12、中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令xj = xj- xj”其中xj0，xj”0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号 取决于xj和xj”的大小。193 单纯形方法及大M法 单纯形法的基本思路和原理 单纯形法的表格形式 求目标函数值最小的线性规划的问题的单纯形表解法 几种特殊情况201 单纯形法的基本思路和原理单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规

13、划问题无最优解为止。通过第二章例1的求解来介绍单纯形法:在加上松弛变量之后我们可得到标准型如下：目标函数： max 50x1+100x2约束条件：x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250.xj0 （j=1，2）,sj0 （j=1，2,3）21它的系数矩阵 ,其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变量的个数n，为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。基： 已知A是约束条件的mn系数矩阵，其秩为m。若B是A中mm阶非奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。基向量：基B中的一列即称为一个基向量。基B

14、中共有m个基向量。 非基向量：在A中除了基B之外的一列则称之为基B的非基向量。基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。22非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有nm个。由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解了，这个解我们称之为线 性规划的基本解。在此例中我们不妨找到了 为A的一个基，令这个基的非基变量x，s2为零。这时约 束方程就变为 基变量的约束方程： 23x2+s1300，x2=400，x2+s3=250.求解得到此线性规划的一个基本解：x1=0，x2=400，s1=100，s2=0，s3=150由于在这个基本解中s1=100，s3=150，不满足该线性规划s10，s30的约束条件，显然不是此线性规划的可行解，一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。24一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一