《第二章1线性规划教学幻灯片》由会员分享，可在线阅读，更多相关《第二章1线性规划教学幻灯片（100页珍藏版）》请在金锄头文库上搜索。
1、数学模型电子教案,重庆邮电大学 数理学院 沈世云,第二章 规划论模型,1.线性规划 2.整数规划 3.非线性规划 4.动态规划,第一节 线性规划模型,1.线性规划模型 2.单纯形法 3.对偶单纯形法,max Z= 40 x1 +50 x2,解:设产品A, B产量分别为变量x1 ， x2,例2,求：最低成本的原料混合方案,解：设每单位添加剂中原料i的用量为xi(i =1,2,3,4),minZ= 2x1 + 5x2 +6x3+8x4,例3 ： 任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已
2、知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：,二 线性规划模型特点,决策变量：向量(x1 xn)T 决策人要考虑和控制的因素非负 约束条件：线性等式或不等式 目标函数：Z=(x1 xn) 线性式，求Z极大或极小,11,一般式,Max(min)Z=C1X1+ C2X2+CnXn,线性规划的标准型(standard model) 线性规划的标准型： 对目标函数求
3、极小，决策变量一律为非负变量，约束条件除变量的非负条件外，一律为等式约束。各种形式的线性规划模型一律为等式约束。 若目标函数为,则可令f= -z,此问题转化为求 若约束条件含 则引进 有 称 为松弛变量 若约束条件含 ,则引进新变量 ，有 称 为剩余变量。 若约束条件含 则引进 ,于是 若变量 的符号不受限制，则可引进两个新量 , 并以 代入目标函数及约束中消去 ，,而在约束条件中增加 例： 把线性规划 化为标准型. 分析： 令 ，将max z改为求 min f 用 代替 ，其中 对不等式约束分别引进松弛变量 和剩余变量,于是，原问题化为标准型：,例4 把问题转化为标准形式,于是转化为标准形式
4、,返回,1.1 基 本 概 念,图解法的步骤：,1.求可行解集合。分别求出满足每个约束包括变量非负要求的区域，其交集就是可行解集合，或称为可行域；,2.绘制目标函数图形。先过原点作一条矢量指向点（c1,c2)，矢量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；,3.求最优解。依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是最优解。,一般地，将目标函数直线放在可行域中 求最大值时直线沿着矢量方向移动 求最小值时沿着矢量的反方向移动,三 . 图解法 Graphical Method,x1,x2,O,10,20,30,40
5、,10,20,30,40,(3,4),(15,10),最优解X=(15,10),最优值Z=85,例5,2,4,6,x1,x2,2,4,6,最优解X=(3,1) 最优值Z=5,(3,1),min Z=x1+2x2,例6,(1,2),2,4,6,x1,x2,2,4,6,X（2）（3,1）,X（1）（1,3）,(5,5),min Z=5x1+5x2,例7,有无穷多个最优解 即具有多重解,通解为,01,当=0.5时 =(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2),2,4,6,x1,x2,2,4,6,(1,2),无界解(无最优解),max Z=x1+2x2,例8,x1,x2,O,10,
6、20,30,40,10,20,30,40,50,50,无可行解 即无最优解,max Z=10 x1+4x2,例9,由以上例题可知，线性规划的解有4种形式：,1.有唯一最优解(例5,例6),2.有多重解(例7),3.有无界解(例8),4.无可行解(例9),1、2情形为有最优解 3、4情形为无最优解,四. 凸集(convex set),可行域的性质,线性规划的可行域是凸集 线性规划的最优解在极点上,凸集,凸集,不是凸集,六. 单纯形法（Simplex methods） (Dantzing,1947) 单纯形法是求解线性规划问题的一种有效算法。 其基本思想是根据线性规划问题的标准形， 先求出一个基可
7、行解，判别是否为最优解， 若不是，再转换到另一基可行解，并使目标函数值减小，重复上述过程，直到求出最优解。 下面来分析说明,、,引入松驰变量,并将该问题化为标准形 LP ：,，,为其基，,为基变量；,，令非基变量,得基可行解,目标函数值为,。,例3、合理下料问题,解：设按第i种方案下料的原材料为xi根,minZ= 0.1x2 + 0.2x3+0.3x4+0.8x5,例4、运输问题,设xij为i 仓库运到 j工厂的原棉数量(i 1，2，3， j 1，2，3),minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33,八. 对偶理论与灵敏度分
8、析,一、LP的对偶问题,1.引例 生产计划问题是一个在有限资源的条件下，求使利润最大的生产计划安排问题，其数学模型为：,现从另一角度考虑此问题。假设有客户提出要求，租赁工厂的工时和购买工厂的材料，为其加工生产别的产品，由客户支付工时费和材料费，此时工厂应考虑如何为每种资源定价，同样使其获得的利润最大？,解:1)决策变量：设y1, y2分别表示出售单位原材料的价格（含附加值）和出租设备单位工时的租金,3)约束条件:工厂决策者考虑： （1）出售原材料和出租设备应不少于自己生产产品的获利，否则不如自己生产为好。因此有,2）目标函数：此时工厂的总收入为W=24y1+26y2,这也是租赁方需要付出的成本
9、.而在这个问题中,是企业不生产,将自己的资源出售或出租,因此,此时,起决定作用的是租赁方,所以此时的目标函数为 Min W=24y1+26y2,2）价格应尽量低，否则没有竞争力（此价格可成为与客户谈判的底价 租赁者考虑：希望价格越低越好，否则另找他人。,于是，能够使双方共同接受的是 ：,上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶问题。,一般地对于任何一个线性规划问题都有一个与之相对应的对偶问题。原问题与对偶问题的一般形式为：,原问题（LP） 对偶
10、问题（DP）,相应的矩阵形式为：,对称形式的对偶问题为：,（LP）,（DP）,二、对偶理论,1.原问题与对偶问题的关系,由以上两式可知,原问题与对偶问题之间具有如下关系 (1)一个问题中的约束条件个数等于它的对偶问题中的变量数; (2)一个问题中目标函数的系数是其对偶问题中约束条件的右端项; (3)约束条件在一个问题中为“ ”,则在其对偶问题中为“ ”; (4)目标函数在一个问题中为求最大值,在其对偶问题中则为求最小值,例1、写出下列线性规划问题的对偶问题（P27）,非对称形式的对偶问题为：,（LP）,（DP）,归纳对称形式与非对称形式的对偶,原问题与对偶问题之间的关系如下表所示,2.,设,（
11、1）（对称性）对偶问题的对偶是原问题； （2）（弱对偶定理）若X(0)是原问题的可行解，Y(0)是对偶问题的可行解, 则有 （3）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解； （4）（最优性定理），若X(0) 、 Y(0)分别是互为对偶问题的可行解，且C X(0) = Y(0) b，则X(0) 、 Y(0)分别是它们的最优解 （5）（强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。,三、对偶单纯形法,1.单纯形法的重新解释 X*是最大化LP问题最优解的充要条件是同时满足：,因此，单纯形法是在保持原始可行下，经过迭代，逐步实现对偶
12、可行，达到求出最优解的过程。,根据对偶问题的对称性，也可以在保持对偶可行下，经过迭代，逐步实现原始可行，以求得最优解。对偶单纯形法就是根据这种思想所设计的。,例14 用对偶单纯形法求解下列线性规划问题：,解：化为标准形后，用对偶单纯形法求解过程如下表所示,2.对偶单纯形法的计算步骤：,上表中常数列b所对应的系数均为非负，已求得问题的最优解，最优解为y=(y1,y2,y3,y4)T=(0,3/2,1/8,0)；最优值为z*=14,注意：对偶单纯形法仍是求解原问题，它是适用于当原问题无可行基解，且所有检验数均大于0的情况。若原问题既无可行基解，而检验数中又有小于0的情况，只能用人工变量法求解。在计
13、算机求解时，只有人工变量法，没有对偶单纯形法。,四、对偶解的经济含义和影子价格,其含义是：若对原问题右端常数项向量b中的某一常数项bi增加一个单位，目标函数的最优值Z*的变化将是yi*。换句话说，yi*表示当bi增加一个单位时，目标函数最优值的相应增量。实质上yi*就是第i种资源边际价值的一种表现，也是对第i种资源的一种估价。 事实上，如引例中互为对偶LP问题分别描述生产计划问题和资源的定价问题，其数学模型分别是：,原问题,对偶问题,用单纯形法求得其最优表为：,由此，它们的最优解分别是X*=(6,4)T和Y*=(1/5,6/5) 最优值为：Z*=W*=36=24y1*+26y2*,其中y1*=
14、1/5表示单独对材料增加1个单位，可使Z值增加1/5个单位的利润；y2*=6/5表示单独对工时增加1个单位，可使Z值增加6/5个单位的利润。 2.影子价格的定义 把某一经济结构中的某种资源，在最优决策下的边际价值称为该资源在此经济结构中的影子价格。 影子价格是在最优决策下对资源的一种估价，没有最优决策就没有影子价格，所以影子价格又称“最优计划价格”，“预测价格”等等。 资源的影子价格定量的反映了单位资源在最优生产方案中为总收益所做出的贡献，因此，资源的影子价格也可称为在最优方案中投入生产的机会成本。,3、影子价格的求法 资源的影子价格Y*=CBB-1，即为最优单纯形表中松驰变量对应的检验数。
15、例如：在生产计划问题中，最优表如下,两种资源：材料的影子价格为y1=1/5 工时的影子价格为y2=6/5,（2）对市场资源的最优配置起着推进作用 即在配置资源时，对于影子价格大的企业，资源优先供给 （3）可以预测产品的价格 产品的机会成本为CBB-1A-C，只有当产品价格定在机会成本之上，企业才有利可图。 （4）可作为同类企业经济效益评估指标之一。 对于资源影子价格越大的企业，资源的利用所带来的收益就越大，经济效益就越好。,4.影子价格的参谋作用 （1）指出企业挖潜革新的途径,例题: 某化工厂有三种资源A、B、C，生产三种产品甲、乙、丙，设甲、乙、丙的产量分别为x1,x2,x3,其数学模型为：,已解得最优单纯形表如下,(1)求三种资源的影子价格,并解释其经济含义; (2)市场看好，决定增加一种资源的供应量，问应增加哪种资源？,2.5 优化后分析（灵敏度分析）,面对市场变化，灵敏度分析的任务是须解决以下两类问题 一、当系数A、b、C中的某个发生变化时,目前的最优基是否仍最优（即目前的最优生产方案是否要变化）?(称为模型参数的灵敏度分析) 二、增
