ch02线性规划和单纯形法.ppt

1、教学要求：,第二章 线性规划和单纯形法,掌握线性规划的基本建模法和单纯形法基本原理,会在不同条件下运用单纯形法求解线性规划问题,了解线性规划在经济和管理中的基本应用方法,目 录,线性规划实例与模型 线性规划的图解法与基本性质 单纯形法原理 线性规划的初始解解法,目 录,线性规划实例与模型 线性规划的图解法与基本性质 单纯形法原理 线性规划的初始解解法,实用举例,某公司通过市场调研，决定生产高中档新型球袋。某分销商决定买进该公司3个月内的全部产品。该球袋生产需经过原材料剪裁、缝合、定型、检验和包装4过程。 通过分析生产过程，得出：生产中档球袋需要用7/10小时剪裁、5/10小时缝合、1小时定型、

2、1/10小时检验包装；生产高档球袋则需用1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验包装。由于公司生产能力有限，3月内各部的最大生产时间为剪裁部630小时、缝合部600小时、定型部708小时、检验包装部135小时。 通过市场调研部和会计部的调查核算得出结论：生产中档球袋的利润是10元，高档球袋的利润是9元。公司应各生产多少中档和高档球袋才能使公司利润最大？,实用举例,某公司通过市场调研，决定生产高中档新型球袋。某分销商决定买进该公司3个月内的全部产品。该球袋生产需经过原材料剪裁、缝合、定型、检验和包装4过程。 通过分析生产过程，得出：生产中档球袋需要用7/10小时剪裁、5/10小

3、时缝合、1小时定型、1/10小时检验包装；生产高档球袋则需用1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验包装。由于公司生产能力有限，3月内各部的最大生产时间为剪裁部630小时、缝合部600小时、定型部708小时、检验包装部135小时。 通过市场调研部和会计部的调查核算得出结论：生产中档球袋的利润是10元，高档球袋的利润是9元。公司应各生产多少中档和高档球袋才能使公司利润最大？,线性规划模型的建立,建立相应的线性规划模型 ：其中的 分别是该厂计划生产中、高档球袋的数量，称为决策变量。,目标函数,一般线性规划模型,其中c=(c1,c2,cn)，称为价值系数向量；,称为资源限制向量,X

4、=(x1,x2,xn)T 称为决策变量向量,称为技术系数矩阵(也称消耗系数矩阵),一般线性规划模型,线性规划模型的标准形式,Max Z = c1x1 + c2x2 + + cnxn Subject to (s.t.) a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn= bm x1 0, x2 0, , xn 0,为了讨论方便，把最大化、等式约束型的线性规划称为线性规划的标准型，即,标准化,对某个,是任意的,线性规划模型的标准化,例:将如下线性规划模型标准化：,min z= x1 +

5、 5 x2 - 8 x3 - x4 s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 - x4 30 2x2 + 2 x3 +3 x4- 50 x1 , x3 , x4 0，x2取值无约束。,max z1=-x1-5 x2+8 x3 +x4 s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 - x4 30 2x2 + 2 x3 +3 x4- 50 x1 , x3 , x4 0，x2取值无约束。,目标优化标准化，令z1z,线性规划模型的标准化,Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x

6、1 - 3 y2+3y3 + x3 + x4 20 -x1- 2 y2 +2y3 - 3 x3 + x4 -30 -2y2 +2y3 - 2 x3 -3 x4 50 x1 , x3 , x4 ,y2,y3 0,决策变量的标准化: 令 y2 - y3 = x2,max z1=-x1-5 x2+8 x3 +x4 s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 - x4 30 2x2 + 2 x3 +3 x4- 50 x1 , x3 , x4 0，x2取值无约束,线性规划模型的标准化,Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1

7、 - 3 y2+3y3 + x3 + x4 +x5 =20 -x1- 2 y2 +2y3 - 3 x3 + x4 +x6 = -30 -2y2 +2y3 - 2 x3 -3 x4 +x7 = 50 x1 , x3 , x4 , x5, x6, x7, y2, y3 0,约束关系标准化，添加松弛变量,Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 20 -x1- 2 y2 +2y3 - 3 x3 + x4 -30 -2y2 +2y3 - 2 x3 -3 x4 50 x1 , x3 , x4 ,y2,y3 0,解 ：只满足线性约束

8、条件的解（即线性方程组的解） 可行解:满足所有约束条件的解x=（x1，x2，.，xn），称为线性规划问题的可行解。所有可行解的集合称为可行域。 基：设A是约束方程组的mn阶系数矩阵，秩为m， 是A中阶非奇异子矩阵（即 ），则称是线性规划问题的一个基矩阵，简称基。B中的列向量称为基向量，与基向量对应的变量x称为基变量，其它变量称为非基变量。 基本解：令非基变量=0，则由Ax=b可求出一个解，这个解x称为基本解。 基本可行解：满足非负条件的基本解称为基本可行解。 最优解：使目标函数达到最优值的可行解称为最优解。,线性规划的解,例、LP问题基本解的求解方法：,解、可行解、基本解、基本可行解与最优解的

9、关系,可行解,基本解,基本可行解,解,最优解,目 录,线性规划实例与模型 线性规划的图解法与基本性质 单纯形法原理 线性规划的初始解解法,线性规划的图解法,当只有两个决策变量时，可用图解法求解！,例：用图解法求解以下线形规划问题。 max z=4x1+3x2 s.t. x16 2x28 2x1+3x218 x10， x20,x1,x2,解的特殊情况多个最优解,解的特殊情况无可行解,解的特殊情况无界解,线性规划的基本性质,X,若线性规划有最优解，则最优解必在可行域的顶点上达到。,凸集的概念,凸集是线性规划中一个很重要的概念，凸集的一般定义为：如果在集合C中任意取两个点x1，x2，其连线上的所有点

10、也都在集合C中，则称集合C为凸集合。用数学解析式表达为：对任意 ，均有 ，则称C是凸集合。,非凸集,非凸集,凸集,线性规划的基本性质,定理2.1：线性规划的可行域： 是凸集（凸多面体）。,引理2.1：线性规划的可行解 为基本可行解的充分必要条件是x的正分量所对应的系数列向量是线性无关的，即每个正分量都是一个基变量。,定理2.2：线性规划问题的基本可行解x对应于可行域的顶点,定理2.3：若线性规划有最优解，则最优解必在可行域的顶点上达到。,目 录,线性规划实例与模型 线性规划的图解法与基本性质 单纯形法原理,一、初始基本可行解的确定,考虑如下形式的线性规划问题 max z=c1x1+c2x2+.

11、+cnxn s.t. a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 (2.17） . am1x1+am2x2+ +amnxnbm x1，x2，.，xn0 （2.18） 对每个不等式约束引入一个非负松弛变量，得标准形式： max z=c1x1+c2x2+.+cn xn s.t. a11x1+a1nxn+xn+1 =b1 a21x1+a2nxn +xn+2 = b2 （2.19） . am1x1+amn xn +xn+m =bm x1，x2，.，xn，xn+1，xn+m0,由此得到一个初始基本可行解为,二、最优性检验,定理2.4： 在最大化问题中，对于某个基本可行

12、解，如果所有 的 ，则这个基本可行解是最优解。 在最小化问题中，对于某个基本可行解，如果所有 的 ，则这个基本可行解是最优解。,单纯形法求解步骤,将所给问题化为标准形 找出一个初始可行基,建立初始单纯形表 检查所有检验数(若全为非正数,则已得到最优解,计算停止.否则继续下一步) 考察是否无解(若是,计算停止,否则继续下一步) 确定入基变量,出基变量 对初始单纯形表进行单纯形变换,单纯形方法的一般步骤,确定一个初始可行解顶点,根据某种法则进行顶点的最优性判断,不是最优解顶点,是最优顶点,考察与当前顶点相邻的 “更好”的一个顶点，并置为当前新的顶点。,根据某种法则进行LP的无界或不可行判断,无界或

13、不可行,还不能做出判断,求解结束,单纯形法举例单纯形法举例（书例2.6）,解：引进松驰变量x3, x4，化为标准形得：,注意：,对于上述LP问题的标准形，初始基解很容易确定， 因此很容易写出初始单纯形表， 紧接着需要确定进基变量（换入变量）： 在检验数存在有正数时，该基本解不是最优解，需要进一步优化，一般选择较大的检验数对应的变量做为进基变量，若相同，可随意选择一个； 确定离基变量（换出变量）： 用表中第三列对应的b值与选中的进基变量对应的系数（包括已经变化过的）相比，比值较小的那个变量作为离基变量； 这样规定的目的是希望走捷径，使迭代次数尽量少,1=1（03+02）；1=1（02+03）,表

14、中最后一行的所有检验数均为非正数，表明目标函数已达到最大值，上述表为最优表。从表中可得到最优解为X=（x1,x2,x3,x4）=（6/5，6/5，0，0），最优值为Z=12/5,单纯形法举例(和例2.6类似）,解：引进松驰变量x3, x4，化为标准形得：,4=4（03+02）；3=3（02+03）,表中最后一行的所有检验数均为非正数，表明目标函数已达到最大值，上述表为最优表。从表中可得到最优解为X=（x1,x2,x3,x4）=（6，4，0，0），最优值为Z=36,大M法,基本思想：在约束条件中增加人工变量，同时修改目标函数，对目标函数加上具有很大正系数M的惩罚项，为使人工变量不影响目标函数取值

15、，在迭代过程中，应把人工变量从基变量中退出，使其成为非基变量。此时目标函数形式为min,其中，M是很大的正数，同时增加两个人工变量。,不容易找到初始可行解,找初始可行解,要求最后得到的基变量中不含人工变量,X1进基，x7出基,可以从表中移去，然后继续求解,经过几次变换，得到基变量为x1，x2，x3,因目标函数为min，所以判断其基本解为最优解的条件是检验数全为非负数,两阶段法原理,两阶段法的第一阶段是用单纯形法 消去人工变量，即把人工变量都变为非基变量，求出原问题的一个基本可行解。 如果第一阶段求解结果表明问题有可行解时，进行第二阶段，就是从得到的基本可行解出发，用单纯形方法求原问题的最优解。

16、,两阶段法举例,例：,第一阶段：,第二阶段：,用单纯形法求得第一阶段的解为：,用单纯形法求解规划问题得最优解,目标函数的最优解是,总结：,用单纯形法解线性规划问题(标准型)时，解的判定： 1、当得到一个最终单纯形表，其中的所有检验数都非正，且非基变量对应的检验数全为负数（非0），此时该线性规划问题有唯一最优解； 2、当得到一个最终单纯形表，其中的所有检验数都非正，且非基变量对应的检验数有0存在，此时该线性规划问题有无穷多个最优解； 3、当得到一个最终单纯形表，其中的正检验数对应的系数都非正，此时该线性规划问题有无界解； 4、对于添加了人工变量的线性规划问题，若当最终单纯形表的检验数都为非正数，

17、而人工变量仍然留在基变量中且不为0，则该线性规划问题无可行解。,Lindo软件求解线性规划问题介绍,Excel Solver（规划求解）,Excel采用了电子表格的形式，帮助管理者提高数据管理的能力，因而得以广泛应用。 Solver插件专门用于求解带约束的最优化问题。 Solver“规划求解”，可在Excel的工作表中根据对话框提示调用该项功能。,加载 “规划求解”,如果在您的Excel中，没有在“工具”菜单中发现“规划求解”，请在下图所示的界面中点击“加载宏”。,加载 “规划求解”,点击“加载宏”后，显示界面如下：,如果列表中没有 “规划求解”，表明您还没有安装该插件。这时，您需要插入Microsoft Office安装盘，选择“添加安装”后选择该插件的安装。,第1步 导入已知数据,可采用 复制粘贴 或 直接输入 的方式导入数据。,第2步 确定 可变单元格,可变单元格存放决策变量的取值，可变单元格数目等于决策变量个数,图中，规定B16、C16为可变单元格