线性规划的图解法.ppt

Linear Programming,第二章,学习重点及难点 1、线性规划问题的建模及图解法 (熟练掌握) 2、 图解法的求解过程及解的各种情况 （重点) 3、图解法的灵敏度分析(熟练掌握),第二章 线性规划的图解法,第二章 线性规划的图解法,线性规划（Linear Programming，简记为LP）是运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较为成熟和应用上极为广泛的一个分支。 特别是1947年G.B. Dantying提出了一般线性规划问题求解的方法单纯形法之后，线性规划的理论与应用都得到了极大的发展。单纯形法的有效性使它不仅是线性规划的最基本的算法之一，而且已成为整数规划和非线性规划某些算法的基础。,1 线性规划问题及其数学模型,一、 线性规划问题的提出 要利用线性规划的方法解决实际问题，首先要建立其数学模型. 数学模型是描述实际问题共性的抽象的数学形式，因此可以利用纯数学的方法进行研究，从而得到实际问题的性质及其解决的办法。从实际问题中建立数学模型，主要有以下三个步骤： (1) 根据影响所要达到目的的因素确定决策变量； (2)由决策变量和所要达到目的之间的函数关系确定目标函数. (3)由决策变量所受的限制条件确定决策变量所要满足的约束条件；,例1.资源的合理利用问题,某厂生产甲、乙两种产品，要消耗A、B、C三种资源，已知每生产单位产品甲需要A 、B、C资源分别是3、2、0，生产单位产品乙需要A 、B、C资源分别是2、1、3， 资源A 、B、C的现有数量分别是65、40、75，甲、乙两种产品的单位利润分别是1500、2500，问如何安排生产计划，使得既能充分利用现有资源又使总利润最大 ？,解：将一个实际问题转化为线性规划模型有以下几个步骤： 1确定决策变量： 设x1表示生产甲产品的数量；x2表示生产乙产品的数量 2确定目标函数：工厂的目标是总利润最大 max z=1500x1+2500x2 3确定约束条件： 3x1+2x265（A资源的限制） 2x1+ x2 40（B资源的限制） 3x2 75（C资源的限制） 4变量取值限制： 一般情况，决策变量只取大于等于0的值（非负值） x1 0, x2 0,用max表示最大值，s.t.（subject to的简写）表示约束条件， 得到该问题的数学模型为： max Z=1500x1+2500x2 3x1+2x2 65 s.t. 2x1+ x2 40 3x2 75 x1, x2 0 线性规划数学模型三要素： 决策变量、目标函数、约束条件,例2 配料问题,某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品. 甲、乙两种原料都含有A、B、C三种化学成分，其含量（%）和单位成本以及按合同规定产品中三种化学成分的最低含量（%）限制如表所示. 问厂方应如何配制该产品，使得总成本达到最小？,解：(1) 确定决策变量： 设每单位该产品用x1单位甲原料和x2单位乙原料配制而成. (2) 明确目标函数：成本最小，即求 z = 3x1 + 2x2的最小值 (3) 所满足的约束条件 对化学成分A的要求：12 x1+ 3 x2 4 对化学成分B的要求：2 x1 + 3 x2 2 对化学成分C的要求：3 x1 + 15 x2 5 配料平衡条件：x1 + x2 = 1 (4) 变量基本要求： x1，x2 0,则问题的数学模型为：,记为 min z = 3x1 + 2x2 12x1 + 3x2 4 2x1 + 3x2 2 S.t. 3x1 + 15x2 5 x1 + x2 = 1 x1，x2 0,例3 运输问题,设某种物资有两个产地A1，A2，其产量分别为2000吨、1100吨，另有四个销地B1、B2、B3、B4需要该种物资，其需求量分别为1700吨、1100吨、200吨、100吨. 已知每吨运费如表所示，问如何调运，才能使总运费最省？,解： 设xij表示由产地Ai运往销地Bj（i = 1,2；j = 1,2,3,4）的运量. 目标函数为总运费最小: minZ = 21x11 + 25x12 + 7x13 + 15x14 + 51x21 + 51x22 + 37x23 + 15x24 由于总产量与总需求量相等（产销平衡）,所以有约束条件： 对产地产量的约束 : x11 + x12 + x13 + x14 = 2000 x21 + x22 + x23 + x24 = 1100 对销地需求量的约束 : x11 + x21 = 1700 x12 + x13 = 1100 x13 + x23 = 200 x14 + x24 = 100 另外xij是运输量，应满足xij0（i = 1,2；j = 1,2,3,4）,所以产销平衡运输问题的模型可记为,min z = 21x11 + 25x12 + 7x13 + 15x14 + 51x21 + 51x22 + 37x23 + 15x24 s.t. x11 + x12 + x13 + x14 = 2000 x21 + x22 + x23 + x24 = 1100 x11 + x21 = 1700 x12 + x22 = 1100 x13 + x23 = 200 x14 + x24 = 100 xij 0（i = 1,2；j = 1,2,3,4）.,二、 线性规划问题的数学模型,具体分析例1、例2、例3，虽然它们的背景意义各不相同，但从数学模型角度，却具有以下一些共同要点： 第一，求一组决策变量xi，并往往要求它们为非负； 第二，确定决策变量可能受到的约束，称为约束条件，它们可以用决策变量的线性等式或线性不等式来表示； 第三，在满足约束条件的前提下，使某个函数值达到最大（如利润等）或最小（如成本、运费等）.该函数称为目标函数，它是决策变量的线性函数. 具备以上三个要素的问题称为线性规划问题. 简单地说，线性规划问题就是求一个线性目标函数在一组线性约束条件下的极值问题.,二、 线性规划问题的数学模型,一般表示形式：,1、和式,其他常用表示形式：,2、矩阵式,.,3、向量式,30,20,10,当z值不断增加时，该直线 x2 = -（3/5）x1 +Z/2500 沿着其法线方向向右上方移动。,2 线性规划的图解法,max Z=1500x1+2500x2 s.t. 3x1+2x2 65 2x1+ x2 40 3x2 75 x1,x2 0 由图示可知最优点为B （5，25），最优值为70000 可行域、可行解、最优解、 最优值,50,40,30,20,10,10,20,30,40,x1,可行域,50,等值线,B,唯一最优解,*如将例1的目标函数设为z = 1500x1 + 1000x2 ， 那么，最优情况下，目标函数的等值线与直线1重合 这时，最优解有无穷多个，是线段BC上的所有点，最优值为32500.,50,40,30,20,10,10,20,30,40,50,B,C,无穷多最优解,无界解,如将例1的约束条件变为: 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1，x2 0 那么，可行域成为一 个上无界的区域，最优值z， 这时，问题无有限最优解，即解无界。,50,40,30,20,10,10,20,30,40,x1,50,B,无可行解（无解）,. 如下述线性规划问题 max z = 2x1 + x2 s.t. x1 + x2 2 2x1 + 3x2 8 x1, x2 0 用图解法求解时看出不存在满足所有约束的公共区域（可行域）,即无可行解，当然也无最优解。这时，也简称为无解.,线性规划问题解的特点和几种可能情况：,线性规划问题的可行解的集合是凸集 凸集的极点（顶点）的个数是有限的 最优解如果存在只可能在凸集的极点上取得，而不可能发生在凸集的内部 线性规划问题的解可能是：唯一解、无穷多最优解、无界解和无可行解(无解),教科书:P22 1、2,课后作业,谢 谢！,本章结束,3 线性规划图解法的灵敏度分析,灵敏度分析：在建立数学模型和求得最优解之后，研究线性规划的一些系数的变化对最优解产生什么影响？ 重要的原因： 1、模型中的系数一般都是估计值和预测值，不一定非常准确； 2、即使这些系数在某一时刻是精确值，它们也会随着市场条件的变化而变化，不会一成不变； 3、有了灵敏度分析就不必为了应付这些变化而不停的建立新的模型和求新的最优解。,30,20,一、目标函数中的系数的灵敏度分析,max Z=1500x1+2500x2 s.t. 3x1+2x2 65 2x1+ x2 40 3x2 75 x1,x2 0 ,50,40,30,20,10,10,20,30,40,x1,50,B,由图示可知最优解为B (5，25),最优值为70000,x2 =-3x1/2+ 65 -3/2 x2 =25 0 Z=c1x1+c2x2 x2=-c1x1/c2+z/c2 -c1/c2 -3/2-c1/c20,一、目标函数中的系数的灵敏度分析,-3/2 -c1/c2 0 当c2 =2500不变时， 0 c13750，最优解不变,当c1 =1500不变时， 1000 c2，最优解不变,30,20,max Z=1500x1+2500x2 s.t. 3x1+2x2 65 2x1+ x2 40 3x2 75 x1,x2 0 3x1+2x2 66 x1=16/3 x2=25 Z=70500 可见资源A每增加一个单位就可以多获得500元的利润.,50,40,30,20,10,10,20,30,40,x1,50,B,二、约束条件中常数项的灵敏度分析,由图示可知最优点为B(5，25) 最优值为70000,二、约束条件中常数项的灵敏度分析,对偶价格: 约束条件的常数项中每增加一个单位而使最优目标函数值得到改进的数量称之为这个约束条件的对偶价格。 约束条件的对偶价格是500元 约束条件的对偶价格是 0元 当约束条件为松约束时,这个约束条件的对偶价格就为0 （该资源是紧缺资源） 否则当