《线性规划及单纯形》PPT课件.ppt

运筹学2,讲课教师：赵晋都,太原理工大学经济管理学院,第一章 线性规划及单纯形法,1.1 线性规划问题的数学模型 1.2 线性规划问题的图解法 1.3 线性规划问题的单纯形解法 1.4 非标准型线性规划问题的解法,线性规划问题的实践背景 线性规划问题的数学模型 线性规划问题数学模型的标准型,1.1 线性规划的数学模型,一、 线性规划问题的实践背景,线性规划问题起源于20世纪初期，在二战期间得到迅速发展 线性规划问题大致可以分为两类 给出一定量的人力、物力、财力或其它资源，如何统筹规划这些有限的资源完成最大任务； 给定一项任务，如何运筹规划，合理安排，以最少的资源来完成它。,二、 线性规划问题的数学模型,例1-1 某工厂生产甲，乙两种产品，这些产品分别需要在ABCD四种不同的设备上加工。按工艺规定，产品甲，乙在各设备上所需要的加工台时数如表1所示，已知各设备在计划期内有效台时数分别是12、8、16和12。该工厂每生产一件产品甲可得边际利润2元，每生产一件产品乙边际利润3元。问应当如何安排生产计划，才能使利润最大化？（表1）,分析： 上述实际问题，通俗地说，就是在有效台时数一定的前提下，求使利润最大化的生产方案。 建模： 若以 分别代表产品甲，乙在计划期内的生产量。因为设备A的有效台时数为12，这是一个限制产量的条件，所以在确定产品甲，乙的产量时，要肯定不能超出设备A的有效台时数，即可用不等式表示为 12,同理，对设备B、C、D也可以得到以下不等式： 8 16 12 考虑到实际意义， 不可能为负值，即 0,用Z表示利润，则目标函数 于是，上述最优生产问题可以归纳为以下数学形式 其中 必须满足以下条件 12 8 s.t. 16 12 0,思考：模型与表（1）的对应关系？,其中 必须满足以下条件 12 8 s.t. 16 12 0,例1.2 某汽车厂生产大轿车和载重汽车，所需资源、资源可用量和产品价格如下表所示: 大轿车 载重汽车 可用量 钢材（吨） 2 2 1600 工时(小时) 5 2.5 2500 座椅 1 0 400（辆） 获利(千元/辆) 4 3 问应如何组织生产才能使工厂获利最大？,例1.2的数学模型,例1.3 营养配餐问题,成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问如何选择食品才能在满足营养的前提下使购买食品的费用最小？,例1.3 数学模型,例1.4 下料问题,某工厂要做100套钢架，每套有长2.9米、2.1米和1.5米的圆钢组成，已知原料长7.4米，问应如何下料使需用的原材料最省。 解：如果从每根7.4米长的原料上各截一根2.9米、2.1米和1.5米长的圆钢，则还余0.9米，用100根原料，浪费预料共90米。现采用套裁的办法，设计五种方案，如下表所示。,圆钢套裁方案,例1.4 数学模型,设每个方案各下料 根，则有,小结. 线性规划问题数学模型的特征,线性规划模型的特征 上述问题可看出线性规划问题有如下特点： 1用一组未知变量 表示某一方案，这组未知变量的一组确定值就代表一个具体的方案，这些未知变量称为决策变量。通常，根据决策变量所代表的事物的特点可以对变量的取值加以约束，例如非负约束、整数约束等。 2存在一定的限制条件，通常称为约束条件，这些约束条件可以用一组线性等式或者线性不等式来表达。 3有一个目标要求，并且这个目标可以表示为决策变量的线性函数，称为目标函数。按所研究问题的不同，要求目标函数实现最大化或者最小化。,小结：线性规划问题数学模型的特征, 12 8 s.t. 16 12 0,决策变量,目标函数,约束条件,小结：线性规划问题的规范描述,线性规划问题的规范描述,s.t.,约束条件,目标函数,决策变量,价值系数,技术系数,限定系数,三、线性规划问题的标准型(SLP),为什么要规定线性规划问题的标准型？ 便于比较，便于交流，便于计算机处理 可以只针对这种标准形式来研究它的求解方法，对于不同形式的线性规划问题，只需要将其转换为标准型，然后再按标准型的求解方法求解。,线性规划问题的标准型(SLP),s.t,极大化型,约束方程为等式,所有的决策变量为非负值,约束方程的右端项系数为非负值,1、极大化型 2、约束方程为等式 3、所有的决策变量为非负值 4、约束方程的右端项系数为非负值 形式,线性规划标准数学模型的特征,标准型的和式,标准型的矩阵式,各种符号的定义,非标准形式如何转换成标准形式,1、目标函数是极小化的转化,4.决策变量有上下界的转换,例1.1 的标准型,s.t,例1.2 的标准型,s.t,1.2 线性规划问题的图解法,图解法 可行解及可行解集的特性 线性规划问题解的特点 单纯形法的思路,1.2 线性规划问题的图解法,图解法就是利用坐标图来求解线性规划问题，以例1.1的线性规划模型为例来介绍具体的求法。, 12 8 s.t. 16 12 0,O,1,3,2,4,5,6,7,8,4,1,3,2,5,6,O,7,8,5,4,R,1,3,2,6,O,7,8,4,Q,R,1,3,2,5,6,O,7,8,P,S,P,Q,R,S,1,3,2,4,5,6,O,7,8,P,Q,R,S,1,3,2,4,5,6,O,7,8,P,Q,R,S,1,3,2,4,5,6,O,7,8,(4,2),图解法求解线性规划问题的一般步骤 建立直角坐标系 找出所有约束条件所构成的公共区域，即可行域； 改变目标函数值Z，使等值线平行移动，当移动到可行域上的某一点时，如果再移动就将脱离可行域，则该点使目标函数达到极值，该点坐标则为最优解。,O,1,3,2,4,5,6,7,8,建立直角坐标系,P,Q,R,S,1,3,2,4,5,6,O,7,8,找出所有约束条件所构成的公共区域，即可行域；,可行域,P,Q,R,S,1,3,2,4,5,6,O,7,8,(4,2),改变目标函数值Z，使等值线平行移动，当移动到可行域上的某一点时，如果再移动就将脱离可行域，则该点使目标函数达到极值，该点坐标则为最优解。,可行域,思考：当目标函数改为 时，最优解是什么？,图解法的优缺点,图解法利用坐标图来求解线性规划问题，因此只适用于非常简单的情况 约束条件较少 决策变量不超过两个。三个决策变量即是一个空间问题，图解法在表达上有难度 对于一般问题，难以求得精确解。 但是，对于大量的管理实践问题，约束条件很多，决策变量三个以上，需要得到精确解，显然用图解法难以满足要求，1947年，美国人但泽（Danlzig）提出了一种求解一般线性规划问题的方法，单纯形法。,图解法的结论,若线性规划问题的可行域存在，则可行域是一个凸集 若线性规划问题存在唯一的最优解，那么它必定在顶点上（基本可行解） 若线性规划问题存在多个最优解，那么必有几个相邻的顶点是最优解，其它最优解可以表示成这几个顶点的凸组合。 线性规划问题的解有：唯一最优解；无穷多个最优解；无界解；无可行解四种情况。,图解法的结论-单纯形法的思路,从凸集的某个顶点开始 向目标函数值更好的邻近顶点移动 判断此顶点是否为最优解：检查它是否比它的临近顶点的目标函数值都好，若是，则是最优解；若不是，则重复上述第二步。 最终找出使目标函数值最优的顶点。,1.3 线性规划问题的单纯形解法,线性规划问题解的基本概念 单纯形解法 解的最优性检验 单纯形表格法 单纯形解法的一些问题及其处理方法,一、线性规划问题解的基本概念,可行解 最优解 基及基本解 可行基及基本可行解 代数解与几何解的关系 单纯形法的要点,线性规划问题的解,一、可行解 满足LP模型的约束条件且满足非负条件的解。 例：,二、最优解,使目标函数达到最大的可行解（存在多个可 行解，从中选择最优的解） 三、基和基解 1、基：约束方程系数矩阵中任意m列所组成的mm阶非奇异子矩阵。,基矩阵为：,2、基本解,令非基变量为零，求解由基变量组成的方程组所得到的解。,四、基本可行解和可行基,基本可行解：满足非负条件的基解（可行基所对应的解） 可行基：基本可行解对应的基,可行解,基本解,基本可行解,结论：若LP问题存在最优解，则一定可以在 基本可行解中找到。,二、单纯形解法,Step1: 建立基本可行解 Step2: 计算变量的检验数 Step3: 判断当前解是否最优 Step4: 若不是最优解，换基 Step5: 计算新的基本可行解 Step6: 迭代计算直到求得最优解或可判断无最优解为止。,* LP问题存在可行解，则问题的可行域是凸集 * LP问题的基本可行解X对应LP问题可行域的顶点 * LP问题有最优解，一定存在一个基可行解是最优解,单纯形法思路,建立初始基本可行基,对于约束条件小于等于（）的情况，通过标准化，每个约束条件的左边加上一个松弛变量，该松弛变量的系数矢量是单位矢量。 当约束条件都是小于等于时，可令松弛变量为初始基本可行基，于是可以很方便地得到初始基本可行解。,例 1.2,线性方程组的增广矩阵表示,它的初始可行基,初始基本可行解,初始基变量 是松弛变量。 初始可行解（只要满足非负条件） 初始基本可行解（非基变量取值为零时） 目标函数与最优性检验,第一次迭代,确定入基变量，应当是 （Why），它的系数是4。 确定出基变量，方法如下，得 (Why),对目标函数贡献大（价值系数高）,受资源的约束，400所对应的资源最紧张,确定新基和求解新的基本可行解,新基 新的基变量： 新的基本可行解,新的基本可行解和目标函数,基本可行解 目标函数,第二次迭代,确定换入基变量： 确定换出基变量：,不考虑零与负值,确定新基和求解新的基本可行解,新基 新的基变量： 新的基本可行解,新的基本可行解和目标函数,基本可行解 目标函数,第三次迭代,确定入基变量： 确定出基变量：,不考虑零与负值,确定新基和求解新的基本可行解,新基 新的基变量： 新的基本可行解,基本可行解 目标函数 这是最优解。最大目标函数值为2600。,新的基本可行解和目标函数,三、关于解的最优性检验,设线性规划模型为,令基为B，并作相应的矩阵分割，从约束条件得 代入目标函数 得,令 则目标函数可写成 可用（sigma）判断是否最优解，它叫做检验数。,四、表格形式的单纯形法,表的格式 在表上的计算方法 表上计算的原理 表格单纯形法的实例：,初始单纯形表,单纯形表法求解,第一次换基迭代,330202.540,16000800+0500+4400,第二次换基迭代,第三次换基迭代：最优解,五、单纯形解法的一些问题及其处理方法,换入变量的选择问题 下标最先原则(勃兰特法则) 检验数最大原则 换出变量的选择问题 比值最小原则 下标最先原则(勃兰特法则) 无换出变量的情况无界解 非基变量检验数有等于零多个最优解的情况 退化解与无可行解的情况,单纯形法的进一步讨论,1、无界解,O,z,结论：若j0,对应的系数列向量0，则该LP存在无界解。,2、多个解,21/2 7/3,21/2,结论：若某个非基变量的检验系数为零，则该 LP存在多个最优解。,当所有的检验数全部小于等于零时,若有某个非基变量的检验数也是零,则该线性规划有无穷多组解,否则有唯一解.,3、退化解,基本可行解中基变量等于零,*在单纯形法的计算过程中，确定换出基变量时存在两 个或两个以上的最小比值，这时会出现退化解。 特征：基本可行解中，基变量等于零,*有时，退化会造成计算过程的循环，永远达不到最优解。,*用勃兰特法则一定可以避免出现循环,为避免循环,常采用1976年R.G.Bland提出Bland法则: 单纯形表中有若干个检验数大于零 时,取下标号小的非基变量为换入基变量; 用 法则选取换出基变量时,若比值相同,则选取下标号小的基变量为换出基变量.,勃兰特（Bland）法则,4、无可行解（大M法）,讨论题,在求解极大化LP问题中，得到如下单纯形表：,1、当前解为最优解时，各参数应满足的条件； 2、原问题存在无界解时，各参数应满足的条件； 3、原问题存在多个解时，各参数应满足的条件； 4、当 x4 作为进基变量取代 x5 时，目标值的增量为多少？,结论：若基变量中有非零的人工变量，则该LP无可行解。,1.4 非标准线性规划问题的解法,目标函数求极小问题 等式约束大M方法 大于等于的约束条件 常数项为负值的情况 允许变量为负值的情况,一、目标函数求极小问题,方法1：目标函数标准化(变为极大问题) 方法2：检验数最优解检验规则,二、等式约束大M法,人工变量,标准化后 可见没有初始单位可行基，加人工变量x5,大M法 然后用单纯形法求解（本例）,初始单纯形表,第一次迭代,第二次迭代,第三次迭代,大M法的要点,1、人工变量的引入 2、用大M法处理人工变量 当目标函数求最大，则为-M 当目标函数求最小，则为M,三、大于等于的约束