线性规划研究生课件

《线性规划研究生课件》由会员分享，可在线阅读，更多相关《线性规划研究生课件（155页珍藏版）》请在金锄头文库上搜索。

1、运运 筹筹 学学 管理科学与工程学科负责人 线性规划(研究生)緒緒 论论 一一 运筹学发展简史运筹学发展简史 中国古代的“齐王赛马”就是对策论的一个典型实例。作为运筹学的早期工作其历史可追溯到1914年： 1914年英国人兰彻斯特(F.W.Lanchester)呈发表过关于人与火力的优势与胜利之间的理论文章，这就是军事运筹学中著名的“兰彻斯特战斗方程”。 排队论的先驱者丹麦工程师爱尔朗(A.K.Erlang)1917年在哥本哈根电话公司研究电话通信系统时，提出了排队论的一些著名公式。线性规划(研究生) 20世纪30年代，荷兰人荷雷斯列文生(Horace.C.Le venson)用运筹学思想分析

2、商业广告和顾客心理，由此提出了存储论中著名的“经济批量公式”。 1947年，美国数学家丹捷格(G.B.Dantizg)发表了关于线性规划的研究成果，所解决的问题是美国空军军事规划时提出的，并给出了求解线性规划问题的单纯形算法。事实上，早在1939年苏联学者康托洛维奇(.)在解决工业生产组织和计划问题时，已提出了类似线性规划的模型，并给出了“解乘数法”的求解方法。由于当时未被重视，直到1960年康线性规划(研究生)托洛维奇再次发表了最佳资源利用的经济计算一书后，才受到国内外的一致重视。为此康托洛维奇获得了诺贝尔经济学奖。 因为它与研究技术问题不同，就称之为“运用研究”或“操作研究”(Operat

3、ional Research)。研究内容是： 1.研究护航舰队保护商船队的编队问题，即当船队遭受德国潜艇攻击时，如何使船队损失最小； 2. 研究反潜深水炸弹的合理爆炸深度，这使得德国潜艇被摧毁数增加了400%；3. 研究船队在遭受敌机攻击时，大船应急转向而小船应缓慢转向的逃避方法，其结果，使船只在受敌机攻击时，中弹船只数由47%降到29%。线性规划(研究生) 在20世纪50年代中期，我国科学家钱学森、许国志等人将运筹学由西方引入我国，并结合了我国的特点在国内推广应用。在经济数学方面，特别是投入产出表的研究和应用开展得较早。质量控制(后改为质量管理)的应用也有特色。在此期间，以华罗庚敎授为首的一

4、大批数学家加入到运筹学的研究队伍，使运筹学的很多分支很快跟上当时的国际水平。 我国第一个运筹学小组于1956年在中国科学院力学研究所成立，1960年在山东济南召开全国应用运筹学的经验交流和推广会议，1962年在北京召开了全国运筹学专业学术会议，1980年4月成立中国运筹学学会。上世纪50年代中期，以华罗庚为首的一大批科学家加入到运筹学的研究中，首先在一些企业、事业单位积极推广优选法、统筹法等运筹学方法，取得显著成果；并成立了优选法、统筹法与经济数学研究会。学会主要研究运筹学，但没有称为运筹学。如今，运筹学已经成为所有大学的经济与管理学院、工学院与计算机专业、应用数学专业的基础课程。 线性规划(

5、研究生)二、二、 运筹学的工作步骤运筹学的工作步骤 运筹学在解决大量实际问题的过程中形成了自己的工作步骤：1.提出和形成问题：提出和形成问题：即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数及有关资料。2.建立模型：建立模型：即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来。3.求解：求解：用各种手段(主要是数学方法，也可用其它方法)将模型求解。解可以是最优解、次优解、满意解.复杂模型的求解需用计算机,解的精度要求由决策者提出线性规划(研究生)4.解的检验：解的检验：首先检验求解步骤和程序有无错误，然后检查解是否反映现实问题。5.解的控制：解的控制：通过控制解的变化

6、过程决定对解是否要作一定的修改。6.解的实施：解的实施：是指将解用到实际中去，必须考虑到实际的问题，如向实际部门讲清楚解的用法，在实施中可能产生的问题等。 以上过程应反复进行。 线性规划(研究生) 三、三、 运筹学的应用与展望运筹学的应用与展望 在运筹学的发展简史中，已提到了运筹学在早期的应用，主要在军事领域。二次大战后运筹学的应用转向民用，主要应用于：(1)市场销售：在广告预算和媒介的选择、竞争性定价新产品开发、销售计划的制定等方面。(2)(2)生产计划：在总体计划方面主要是从总体确定生产、存储和劳动力的配合等计划以适应波动的需求计划,主要用线性规划和模拟的方法等。(3)(3)库存管理:主要

7、应用于多种物资库存的管理,以确定合理的库存量。(4)(4)运输问题：各种运输的调度与计划安排。(5)(5)财政和会计：这里主要涉及预算、贷款、成本分析、定价、投资、证券管理、现金管理等。用得较多的方法是：统计分析、数学规划、决策分析。线性规划(研究生)(6)人事管理：一是人员的获得和需求估计；二是人才的开发，即进行教育和培训；三是人员的分配；四是各类人员的合理利用问题；五是人才的评价，其中有如何测定一个人对组织、社会的贡献;六是工资和津贴的确定等。(7)设备维修、更新和可靠性、项目选择和评价。(8)工程的优化设计：这在建筑、电子、光学、机械和化工等领域都有应用。(9)计算机和信息系统：(10)

8、城市管理：包含了各种紧急服务系统的设计和运用线性规划(研究生)四、最优化问题举例1、多参数的曲线拟合问题 已知热敏电阻R依赖于温度t的函数关系线性规划(研究生)2、生成成本问题介绍Cobb-Douglas生产函数。线性规划(研究生) 3、资源分配问题、资源分配问题考虑将m种资源安排给n种活动，问应如何分配资源，才能使收益最大？线性规划(研究生)在某些实际应用中，有时考虑的利润c1,c2,cn并不是固定的数值，而是随机变量，假定C是一个均值为线性规划(研究生)线性规划(研究生)这是线性分式规划。线性规划(研究生)线性规划(研究生)最优化的分类图离散规划整数规划非线性最小二乘球面规划非线性等式最优

9、化连续优化离散优化有约束无约束线性规划不可微分规划非线性规划网络规划随机规划线性规划(研究生)参考书 1、卢向华，等著运筹学教程，高等教育出版社 2、钱颂迪，运筹学，清华大学出版社 3、林同曾，运筹学，机械工业出版社 4、胡运权， 运筹学教程，清华大学出版社线性规划(研究生) 第 一章 线 性 规 划 第 一 节 线性规划模型及其图解法 线性规划是运筹学的一个重要分枝。自1947年美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法单纯形法之后，线性规划在理论上趋于成熟，在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后，它

10、的适用领域更广泛了。从解决技术问题中的最优化设计到工业、农业、商业、交通输业、军事、经济计划与管理、决策等各个领域均可发挥作用；从范围来看，小到一个小组的日常工作和计划安排，大至整个部门以致国民经济计划的最优方案的提出，都有用武之地。它具有适应性强、应用广泛、计算技术比较简单的特点，是现代管理科学的重要基础和手段之一。线性规划(研究生)一、线性规划模型线性规划：就是一个线性函数在线性等式或不等式约束条件下的极值问题。线性规划研究的问题主要有两类： 1、任务确定后，如何统筹安排，尽量做到用尽量少的人力和物力资源来完成任务； 2、有一定量的人力、物力资源，如何安排使用他们，使完成的任务（创造的利润

11、）最多。 在生产管理和经济活动中经常提出这样一类问题， 即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。线性规划(研究生)例例1：某工厂在计划期内安排生产、两种产品，已知生产单位产品所需的设备台时、A、B两种原材料的消耗及两种产品每件可获利润见如下表所示：问如何安排计划使该工厂获利最多？ I II 资源总量 设 备A 1台时 2台时 8 台时 设 备B 2台时 2台时 12 台时 原材料A 4公斤 0公斤 16公斤 原材料B 0公斤 4公斤 12公斤 利 润 2元/件 3元/件线性规划(研究生)解：解：假设 x1、x2分别表示在计划期内生产产品I、II的数量，则该计划问题

12、可用如下数学模型表示为： 目标函数 Max Z = 2x1 +3x2 约束条件线性规划(研究生)例例2 某某汽汽车车厂厂生生产产大大轿轿车车和和载载重重汽汽车车，所所需需资资源源、资源可用量和产品价格如下表所示资源可用量和产品价格如下表所示: 大轿车大轿车 载重汽车载重汽车 可用量可用量钢材（吨）钢材（吨） 2 2 1600工时工时(小时小时) 5 2.5 2500大轿车座椅大轿车座椅 400（辆）（辆）获利获利(千元千元/辆辆) 4 3问应如何组织生产才能使工厂获利最大？问应如何组织生产才能使工厂获利最大？ 线性规划(研究生)例2的数学模型s.t.,线性规划(研究生)例3 下料问题某工厂要做

13、100套钢架，每套有长2.9米、2.1米和1.5米的圆钢组成，已知原料长7.4米，问应如何下料使需用的原材料最省。解：如果从每根7.4米长的原料上各截一根2.9米、2.1米和1.5米长的圆钢，则还余0.9米，用100根原料，浪费预料共90米。现采用套裁的办法，设计五种方案，如表1.2所示。线性规划(研究生)表 圆钢套裁方案 方案长度一二三四五2.92.11.513210221213合计（米）料头（米）7.407.30.17.20.27.10.36.60.8线性规划(研究生)例3 数学模型设个方案各下料 根，则有（1-5）线性规划(研究生)以上三个例子,从数学上来讲,它们的共同特征是:(1)每个

14、问题都用一组决策变量(x1 , x2 , , xn)表示某一(2)方案 ,这组未知数的值就代表一个具体的方案,通常要求这些未知数取值是非负的。(2) 存在一定的限制条件(称为约束条件),这些条件都可以用关于决策变量的一组线性等式或不等式来表示。(3) 都有一个目标要求,并且这个目标可表示为这组决策 变量的线性函数(称为目标函数),按研究问题的不同,要求目标函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划数学模型。线性规划(研究生)其一般形式为(1.1)和(1.2)形式。 在该模型中,方程(1.1)称为目标函数;(1.2)称为约束条件。线性规划(研究生)二、图解法二、图解法对于简

15、单的线性规划问题(只有两个决策变量的线性规划问题),我们通过图解法可以对它进行求解。我们可以由例1具体给出求解的方法。例1：用图解法求解线性规划问题。 MAX Z=2x1+3x2 s.t. 2x1+2x2 12 x1+2x2 8 4x1 16 4x2 12 x1，x20线性规划(研究生) x1+2x2=8 解得：x1=4 4x1=16 x2=2这就是本线性规划问题的最优解。此时相应的目标函数的最大值为： Z=24+32=14013466844x1=164x2=12X1+2x2=82x1+2x2=12ABCDX2解：对于上述具有两个变量的线性规划问题，下图的阴影部分描述了满足约束条件的区域，为O

16、ABCD;红虚线为目标函数Z=2x1+3x2的等值线。等值线。沿箭头方向移动目标函数的等值线，平移等值线直至与可行域OABCD相切或融合为一条直线，此时就得到最优解为C 点，其坐标可通过解方程组得到：线性规划(研究生)例2：用图解法求解线性规划问题。 MAX Z=4x1+3x2 s.t. 2x1+2x2 1600 5 x1+2.5x2 2500 x1 400 x1,x20由约束条件得到可行域OABCD。由等值线Z=4x1+3x2沿箭头方向向上平移与可行域交于B点，则B点就是最优点。最优值等于2600线性规划(研究生)0Z= 40 X1 + 80X2 =0 X1 + 2X2 =30DABCX2X

17、1求解最优解：求解最优解：BC线段线段B点点 C点点X(1)=(6,12) X(2)=(15,7.5)X= X(1)+(1- ) X(2) (0 1)例例3、 maxZ=40X1+ 80X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0 0线性规划(研究生)X1 =6 + +(1- )15X2=12 + +(1- )7.5X1 =15-9 X2 =7.5+4.5 (0 1)X= = +(1- )maxZ=1200 X1 6 15 X2 12 7.5线性规划(研究生)无界无有限最优解若目标函数由 Max Z = 2x1 + 4x2 改为 Min Z =2 x1 +4

18、x2 ,则可行解所在的范围虽然无界,但有最优解 x1 = 4，x2 = 0 ,即 (4,0)点.例例4、 maxZ=2X1+ 4X2 2X1+X2 8 8-2X1+X2 2X1 , X2 0 0Z=02X1+ X2=8-2X1+ X2=28246X240X1线性规划(研究生)例例5、 maxZ=3X1+2X2 -X1 -X2 1 1X1 , X2 0 0无解无解无可行解无可行解-1X2-1X10线性规划(研究生)通过图解法可以看出： （1）线性规划的所有可行解构成的可行域一般是凸多边形，有些可行域是无界的； （2）若存在最优解，则一定在可行域的某顶点得到； （3）若在两个顶点上同时得到最优解，

19、则在这两点的连线上的任一点都是最优解。 （4）若可行域无界，则可能发生最优解无界的情况； （5）若可行域是空集，此时无最优解。线性规划(研究生)上述理论具有普遍意义，对于两个以上变量的线性规划问题都成立。 图解法虽然直观、简便等优点，在变量多的情况下，即在多维的情况下，它就无能为力了。因此，需要介绍一种代数方法单纯型法，为了以后介绍方便讨论，需要研究一下线性规划数学模型的标准化问题。线性规划(研究生)三、线性规划问题的标准型三、线性规划问题的标准型 由前面所举的例子可知,线性规划问题可能有各种不同的形式。目标函数有实现最大化也有实现最小化的;约束条件可以是“ ”形式、“”形式不等式,有的是等式

20、。决策变量有时有非负限制有时没有。这种多样性给讨论问题代来了不便。为了便于今后讨论，我们规定线性规划问题的标准型为： 线性规划(研究生) 这里我们假设 bi 0 ( i = 1,2,m),否则两端同时乘以“-1”。用矩阵向量描述就是：线性规划(研究生) 其中：C = ( c1, c2, , cn )T ，X = ( x1, x2, , xn )T ，b = ( b1, b2, , bm )T , A = ( P1, P2, , Pn ) ，Pj = ( a1j, a2j, , amj )T ，0 = ( 0, 0, , 0 )T , ( j = 1, 2, , n ) 。 我们称 A 为约束方

21、程组的系数矩阵( mn阶),一般情况下 m n , m , n 为正整数,分别表示约束条件的个数和决策变量的个数, C 为价值向量, X 为决策向量, 通常aij , bi , cj ( i = 1, 2, , m , j = 1, 2, , n ) 为已知常数。 实际上，具体问题的线性规划数学模型是各式各样的,需要把它们化成标准型,并借助于标准型的求解方法进行求解.线性规划(研究生)以下就具体讨论如何把一般的线性规划模型化成标准型。1.若要求目标函数实现最小化时. 即此时的目标函数是: Min Z = CTX , 这时只需要将目标函数的最小值变换为求目标函数的最大值,即 Min Z = Ma

22、x (- Z) 。令Z= -Z，于是就得到： Max Z= - CTX 。2. 若约束方程组为不等式。这时有两种情况:一是约束条件为“ ”形式的不等式,则在“ ” 号的左边加入非负的松弛变量;把原“ ” 形的不等式变为等式;另一种是约束条件为“ ”形式的不等式,则可在“ ”号的左端减去一个非负的剩余变量。相应的松弛变量或剩余变量在目标函数中的价值系数取值为0。线性规划(研究生)3. 若存在无非负要求的变量. 即有某一个变量 xj 取正值或负值都可以. 这时为了满足标准型对变量的非负要求,可令 xj = xj- xj, 其中: xj、 xj 0 ，由于xj可能大于也可能小于xj，故 xj 可以为

23、正或为负。上述的标准型具有如下特点： （1）目标函数求最大值； （2）所求的变量都要求是非负的； （3）所有的约束条件都是等式； （4）常数项非负 综合以上的讨论可以说明任何形式的线性规划问题都可以通过上述手续把非标准型式的线性规划问题化成标准型。现举例如下：线性规划(研究生)例：将例1的数学模型化为标准型。 max Z=2x1+3x2 2x1+2x2 12 x1+2x28 4x212 4x1 16 x1, x20 解：引进4个新的非负变量x3,x4,x5,x6使不等式变为等式，标准型为： Max Z=2x1+3x2+0x3+0 x4+0 x5+0 x6 2x1+2x2+x3 =12 x1+2

24、x2+ x4 =18 4x1+ x5 =16 4x2+ x6 =12 x1, x2,x3,x4,x5,x60线性规划(研究生)例例4: 试将如下线性规划问题化成标准型解：解：令 x3 = x4 - x5 , x4 , x5 0 , (1)式左端加上非负松弛变量 x6 , (2)式左端减去非负剩余变量 x7 , 则可将上述线性规划问题化成如下的标准型:线性规划(研究生)线性规划(研究生)1.可行解可行解: 满足约束条件(1.7),(1.8)的解 X = ( x1, x2, , xn)T 称为线性规划问题的可行解;所有可行解的集合称为可行解集或可行域。2.最优解最优解: 满足约束条件及目标函数(1

25、.6)的可行解称为线性规划问题的最优解。四、线性规划问题的解的概念四、线性规划问题的解的概念 在讨论线性规划问题的求解之前,先要了解线性规划问题的解的概念。由前面讨论可知线性规划问题的标准型为 (1.6)、(1.7)、(1.8)，即如下式子：线性规划(研究生)3.基基: 假设 A 是约束方程组的系数矩阵,其秩数为 m ,B是矩阵 A 中由 m 列构成的非奇异子矩阵(B的行列式的值不为0），则称 B 是 线性规划问题的一个基。这就是说,矩阵 B 是由 m 个线性无关的列向量组成,不失一般性,可假设:称 Pj ( j = 1,2,m )为基向量,与基向量 Pj 相对应的变量xj ( j = 1,2

26、,m )为基变量,否则称为非基变量。 为了进一步讨论线性规划问题的解,下面研究约束方程组(1.7)的求解问题。假设该方程组系数矩阵 A 的秩为 m ,因 m n,所以它有无穷多个解。假设前 m 个变量的系数列向量是线性无关的，这时(1.7)式可改写为：线性规划(研究生)方程组(1.9)的一个基是B=(P1, P2, ,Pm), Pj=(a1j, ,amj)T, (j = 1,2, , m ),设 XB 是对应于这个基的基向量,即： XB = ( x1, x2, , xm )T 现若令(1.9)式中的非基变量 xm+1 = = xn = 0 ,并用高斯消去法求出一个解 X = ( x1, x2,

27、 , xm , 0, , 0 )T ,这个解的非0分量的数目不大于方程个数 m ,称 X 为基本解.线性规划(研究生)4.基本可行解基本可行解 : 满足非负条件(1.8)的基本解称为基本可行解.由此可见,基本可行解的非0分量的数目不大于 m ,并且都是非负的。5.可行基可行基: 对应于基本可行解的基称为可行基.由此可见,约束方程组(1.7)基本解的数目至多是 Cnm 个.一般地讲,基本可行解的数目要小于基本解的数目,至多相等.6. 以上提到的几种解的概念,可用如下图来表示:基解可行解基本可行解线性规划(研究生) 第二节第二节 线性规划问题的几何意义线性规划问题的几何意义 在上一节的图解法中,我

28、们已经直观地看到了可行和最优解的几何意义,这一节从理论上进一步讨论。一、基本概念：一、基本概念：1.凸集: 假设 K 是 n 维欧氏空间的一个点集,若对于K 中的任意两点 X1、X2 ,其连线上的所有点 X1+(1-)X2 ( 0 1)都在集合 K 中,即: X1+(1-)X2 K ( 0 1)则称 K 为凸集。从直观上讲，凸集无凹入部分，其内部没有洞。 实心圆、实心球、实心立方体等都是凸集，圆周不是凸集。线性规划(研究生)图（a)、(b)、为凸集，而图（c)、(d)不是凸集。线性规划(研究生)容易验证以下结论是正确的：线性规划(研究生)2. 凸组合: 设 X1、 X2、 Xk 是 n 维欧氏

29、空间 En 中的k 个点，若存在 1、 2、 、 k，且 0 i 1 ,i = 1,2, , k, i = 1 , 使 X = 1X1 + 2X2 + + kXk , 则称X 为由 X1、 X2、 Xk 所构成的凸组合。 按照定义，凡是由x,y的凸组合表示的点都在x,y的连线上，而且反之亦然。3. 顶点: 假设 K 是凸集, X K ; 若不能用不同的两个点X1、 X2 K 的线性组合表示为: X = X1+(1-)X2 ， ( 0 1) 则称 X 为凸集 K 的一个顶点（或称为极点）。 顶点不位于凸集 K中的任意不同两点的连线内。线性规划(研究生)二、基本定理二、基本定理定理定理1：若线性规

30、划问题存在可行域，则其可行域： D = X AX = b , X 0 ，是凸集。引理引理1：线性规划问题的可行解 X 为基本可行解的充要条件是 X 的正分量所对应的系数列向量是线性无关的。证明证明 : (1) 必要性: 由基本可行解的定义便可知。（2）充分性：若向量 P1, P2, ,Pk 线性无关，则必有 km ; 当 k = m 时，它们恰好构成一个基，从而 X = ( x1, x2, , xm , 0, , 0 )T 为相应的基本可行解,当 k 0, 而 yj0 0 , 则(LP)无有限最优解(也称为无界解)。一、最优性检验与解的判别一、最优性检验与解的判别1.最优解判别定理最优解判别定

31、理: 若 X(0) = ( XB(0), XN(0) )T , 其中XB(0)=B-1b , XN(0) =0 为对应于基 B 的基本可行解 , 且对于一切jIN ,有 j 0 , 则 X(0) 已为( LP )的最优解。2.证明证明:设 X 为(LP)的一个可行解,令 X = ( XB, XN )T, 代入目标函数值整理得到:线性规划(研究生)3. 基变换基变换: 若非上述两种情形,则由式(1.23)可见,当某些j 0, xj 0, jIN , 则目标函数值还可以增加。为使目标函数值增加最快，我们选择： j = max ll 0 , l IN j所对应的变量xj为换入变量(就是下一个基的基变

32、量). 因为基变量个数总是为 m , 所以换入一个之后还必须换出一个。下面我们来考虑如何选择换出变量。 若初始基本可行解X(0)不是最优解，那么就还要找一个新的基本可行解。其作法如下： 从原可行基中换出一个列向量，再投入一个新的列向量，（要保证线性无关），从而得到一个新的可行基，这就是基变换。线性规划(研究生) 要做基变换要做基变换。首先确定换入变量（已讲过），即选择最大的检验数j所对应的非基变量作为换入变量xj(进基变量)。 下面再确定换出变量再确定换出变量。确定换出变量的原则是保持解的可行性。这就说，要使原基本可行解的某一个正分量xj变为0，同时保持其余分量均非负。具体实现是按“最小比例原

33、则”进行，也称原则。 若则选基变量Xl为换出变量。4.旋转运算（迭代）（枢运算） 在确定了换入变量Xk与换出变量Xl之后，要把xk和xl的位置对换，就是说，要把xk 所对应的列向量pk变成单位向量。这只对系数矩阵的增广矩阵进行变换即可，称ylk为旋转元。线性规划(研究生)以表13中的元素 ykl (称为主元素或旋转元素)进行基变换: 将第 k 行每个元素除以 ykl , 将第 k 行每个元素乘以 yij / ykj 加到第 i 行( i = 1,2, ,m , i k , j = 1,2, , k ),将第 k 行每个元素乘以 j / ykj 加到检验数行, 对应的新的目标函数值即为：线性规划

34、(研究生)经过基变换之后，针对于新基 B1 的基本可行解 为：线性规划(研究生)综合以上的讨论,单纯形算法的计算步骤可归结如下：第一步：找出初始可行基，确定初始基本可行解 ，建立初始单纯形表；第二步：检查对应于非基变量的检验数 l ，lIN ，若所有 l 0 ，lIN ，则已得到最优解，停止计算，否则转入下一步；第三步：在所有l 0，lIN 中，若有一个j 对应的系数列向量 yj 0，则此问题没有有限最优解，停止计算，否则转入下一步；第四步：根据 max l l 0，lIN = j ,确定 xj 为线性规划(研究生)换入变量(即为新基的基变量),再根据:确定 xk 为换出变量(即为新基的非基变

35、量), 转下一步；第五步：以 ykj 为主元素进行基变换，转回第二步。 例例5. 利用单纯形算法求解例1的线性规划问题。 Max Z=2x1+3x2+0x3+0 x4+0 x5+0 x6 2x1+2x2+x3 =12 x1+2x2+ x4 =8 4x2+ x5 =12 4x1+ x6=16 x1,x2,x3,x4,x5,x60 解： （1）由标准型得到：线性规划(研究生)cj2 3 0 0 0 0XBbx1 x2 x3 x4 x5 x6 2 2 1 0 0 01 2 0 1 0 04 0 0 0 1 0 0 4 0 0 0 1x3x4x5x6128161264-3-Z0 2 3 0 0 0 0

36、 （2）max1, 2=3= 2,所以x2为换入变量. (3)因为1=2, 2=3都大于0，且p1,p2的坐标有正分量存在，因为3与x6那一行相对应，所以x6为换出变量；线性规划(研究生)cj2 3 0 0 0 0XBbx1 x2 x3 x4 x5 x6 2 0 1 0 0 -1/231 0 0 1 0 -1/24 0 0 0 1 0 0 1 0 0 0 1/4x3x4x5x262163324-Z-9 2 0 0 0 0 -3/4 故x2对应列与x6对应行的相交处的4为主元素；（4）以“4”为主元素进行旋转计算，进行行初等变换，得下表：线性规划(研究生)cj2 3 0 0 0 0XBbx1 x

37、2 x3 x4 x5 x6 0 0 1 -2 0 1/21 0 0 1 0 -1/220 0 0 -4 1 2 0 1 0 0 0 1/4x3x1x5x222834-412-Z-13 0 0 0 -2 0 1/4 这时出现了退化问题。即有两个或更多的相同时，在相同 对应的变量中选择下标最大的那个基变量为换出变量；同时如果出现有两个或更多的检验数相同时，在相同 对应的变量中选择下标最小的那个基变量为进入变量，这样会避免出现“死循环”的现象。线性规划(研究生)cj2 3 0 0 0 0XBbx1 x2 x3 x4 x5 x6 0 0 1 -1 -1/4 01 0 0 1 1/4 020 0 0 -

38、2 1/2 1 0 1 0 -1/8 0x3x1x6x20442-Z-14 0 0 0 -3/2 -1/8 0 这时，检验数全部小于等于0，即目标函数已不可能再增大，于是得到最优解： X=(4,2,0,0,0,4)T目标函数的最大值为： Z=14线性规划(研究生) 第四节第四节 单纯形算法的进一步讨论单纯形算法的进一步讨论一、初始基本可行解一、初始基本可行解 的确定的确定 利用单纯形算法的一个根本前提是要有一个初始的基本可行解 .这对于一些简单问题, 利用观察或其它手段是容易得到的;但对于较复杂的问题, 则利用这种方法几乎是不可行的. 这就引起了人们对求初始基本可行解 的思考.以下我们分几种情

39、形加以讨论。1.对于 AX = b , 人们一下就可以从其中求得一个单位2.矩阵.这时取初始基 B 就是单位矩阵,对应的基变量为 XB3., 非基变量为 XN 。这时线性规划(研究生), 然后按单纯形算法计算步骤便可得到。这种情况包含了 AX b 的情形。2.人工变量法人工变量法(大大 M 法法)3. 设有一个线性规划的约束条件是等式约束，这时分别给每一个约束条件加入人工变量 xn+1, , xn+m , 得:线性规划(研究生)由此得到一个 m 阶单位矩阵. 以 xn+1, , xn+m 为基变量, 令非基变量 x1, , xn 为 0, 便可得到一个初始基本可行解 X(0) ; X(0) =

40、 ( 0, , 0, b1 , , bm )T 。 因为人工变量是后加入到原约束方程组中的虚拟变量, 我们要求将它们从基变量中逐渐替换掉.若经过基的变换, 基变量中不再包含有人工变量, 这就表示原问题有解; 若经过基变换,最后在基中至少还有一个人工变量, 这就意味着原问题无可行解. 具体处理方法如下: 对于加入人工变量的线性规划问题的目标函数如何处理?我们希望人工变量对目标函数取值不受影响.因此线性规划(研究生)只有在迭代过程中, 把人工变量从基变量中换出,让它成为非基变量.为此, 就必须假定人工变量在目标函数中的价值系数为(-M)(对于极大化目标), M为充分大的正数.这样, 对于要求实现目

41、标函数最大化的问题来讲,只要在基变量中还存在人工变量, 目标函数就不可能实现最大化. 这就是大M法。以下举例加以说明。例例6. 试用大M法求解如下线性规划问题的最优解。线性规划(研究生)解解:在上述问题中加入松弛变量,剩余变量和人工变量得:这里M是一个充分大的正数, 取基变量为 x4 , x6 , x7 , 可得如下的表18。利用表18得初始单纯形表，单纯形算法得表19 表111。线性规划(研究生)表表18cj3-1-100-M -MCBXBb*x1x2x3x4x5x6x70x4111-211000-Mx63-4120-110-Mx71-2010001-Z03-1-100-M -M线性规划(研

42、究生)cj3-1-100-M -MCBXBb*x1x2x3x4x5x6x70x4111-21100011-Mx63-4120-1101.5-Mx71-20100011-Z4M 3-6M M-13M-10-M00初始单纯形表线性规划(研究生)表表19cj3-1-100-M-MCBXBb*x1x2x3x4x5x6x70x4103-20100-1-Mx610100-11-21-1x31-2010001- ZM+11M-100-M01-3M线性规划(研究生)cj3-1-100-M-MCBXBb*x1x2x3x4x5x6x70x4123001-22-54-1x210100-11-2-1x31-20100

43、01- Z21000-11-M-1-M 表表110线性规划(研究生)cj3-1-100-M-MCBXBb*x1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3- Z-2000-1/3 -1/31/3-M2/3-M 表表111在表111中，所有的 j 0，故得到最优解： X* = ( 4, 1, 9, 0, 0, 0, 0 )T 目标函数值 Z= 2 , 原问题的最优目标值为: Z* = -2 。线性规划(研究生)3. 两阶段法两阶段法: 这种方法是在约束条件中加入人工变量,将线性规划问题分为两阶段进行求解

44、. 第一阶段是先求出基本可行解 (或判断出原线性规划问题无解), 第二阶段利用已求出的初始基本可行解 来求最优解。具体由如下定理5给出。定理定理5 设原线性规划问题记成(LP), 由它而引入的新的线性规划问题记成(LP)*。分别表示如下：线性规划(研究生)1) 若(LP)*具有最优基本可行解 则(LP)是可行的,而 2) 若(LP)*的最优基本可行解 则(LP)必不可行。 定理5的具体应用过程是: (LP)*判断原线性规划问题是否存在基本可行解 , 利用单纯形算法, 若得到 W = 0 , 即所有人工变量为非基变量, 这表示原问题已得到了一个基本可行解 .于是只需要将第一阶段最终计算表中的目标

45、函数行的数字换成原问题的目标函数的数字, 就得到了求解原问题的初始计算表, 再进行第二阶段的求解。若第一阶段的最终计算表出现 W 0 , 这就表明原问题无可行解，应停止计算。线性规划(研究生)解：解：先在以上问题的约束条件中加入松弛变量、剩余变量、人工变量，给出第一阶段的线性规划问题：各阶段的计算方法及步骤与前述单纯形法完全相同，下面用例子说明该方法的应用。 例例7：试用两阶段法求解如下线性规划问题线性规划(研究生)以 x4、x6、x7 为基变量得如下初始计算表cj00000-1-1CBXBb*x1x2x3x4x5x6x70x4111-211000-1x63-4120-110-1x71-201

46、0001-W000000-1-1线性规划(研究生)cj00000-1-1CBXBb*x1x2x3x4x5x6x70x4111-21100011-1x63-4120-1101.5-1x71-20100011-W4-6130-100初始单纯形表112线性规划(研究生)表表113cj00000-1-1CBXBb*x1x2x3x4x5x6x70x4103-20100-1-1x610100-11-21-1x31-2010001-W10100-10-3线性规划(研究生)表表114cj00000-1-1CBXBb*x1x2x3x4x5x6x70x4123001-22-50x210100-11-20x31-2

47、010001-W000000-1-1线性规划(研究生) 这里 x6、x7 是人工变量。第一阶段我们已求得 W = 0 ，最优解 x5 = 0， x6 = 0， x7 = 0。因人工变量 x6 = x7 = 0, 所以( 0, 1, 1 ,12, 0 )T 是原问题的基本可行解 。于是可以开始第二阶段的计算。将第一阶段的最终计算表114中的人工变量列取消, 并将目标函数系数换成原问题的目标函数系数, 重新计算检验数行, 可得如下第二阶段的初始单纯形表115；应用单纯形算法求解得最终表116。 线性规划(研究生)表表115cj3-1-100CBXBb*x1x2x3x4x50x4123001-212

48、/3=4-1x210100-1-1x31-20100-Z21000-1线性规划(研究生)表表116cj3-1-100CBXBb*x1x2x3x4x53x141001/3-2/3-1x210100-1-1x390012/3-4/3-Z-2000-1/3-1/3表116中所有检验数 j 0，所以 x1 = 4，x2 = 1 , x3 = 9 是原线性规划问题的最优解。目标函数值： Z* = 2 。线性规划(研究生)第五节第五节 LP的对偶理论的对偶理论1.5.1 对偶问题对偶问题例例 1 2 加工能力加工能力(小时小时/天天) A 2 2 12 B 1 2 8 C 4 0 16 D 0 4 12

49、2 3销售收入销售收入产品产品设备设备线性规划(研究生)设设X1 ， X2 为产品为产品1，2的产量的产量2X1 +2X2 12 X1 +2X2 84X1 16 4X2 12X1 X2 0maxZ= 2X1 +3X2 2 2 12 1 2 X1 84 0 X2 160 4 12 (2 3) X1X2线性规划(研究生)设设 y1 , y2 , y3 , y4分别为出租每台设备台时的租分别为出租每台设备台时的租金和出让单位原材料金和出让单位原材料A, B的附加额。的附加额。2y1 +y2 +4y3 22y1 +2y2 +44 3y1 y4 02 1 4 02 2 0 4y1 y2 y3 y4 23

50、线性规划(研究生)(y1 y2 y3 y4)2 21 24 00 4 (2,3)minW=12y1+8y2 +16y3+12y4y1 , y2 , y3 , y4 “影子价格影子价格”线性规划(研究生)定义：定义：对偶问题对偶问题 minW=yb yA Cy 0minW=bTyATy CTy 0maxZ=CX AX bX 0原问题原问题线性规划(研究生)对偶关系对应表对偶关系对应表 原问题原问题 对偶问题对偶问题目标函数类型目标函数类型 max min目标函数系数目标函数系数 目标函数系数目标函数系数 右边项系数右边项系数与右边项的对应关系与右边项的对应关系 右边项系数右边项系数 目标函数系数

51、目标函数系数变量数与约束数变量数与约束数 变量数变量数n 约束数约束数 n的对应关系的对应关系 约束数约束数m 变量数变量数m原问题变量类型与原问题变量类型与 0 对偶问题约束类型对偶问题约束类型 变量变量 0 约束约束 的对应关系的对应关系 无限制无限制 原问题约束类型与原问题约束类型与 0 对偶问题变量类型对偶问题变量类型 约束约束 变量变量 0 的对应关系的对应关系 无限制无限制线性规划(研究生)例例1、写出下面问题的对偶规划、写出下面问题的对偶规划maxZ= 5X1 +6X2 3X1 -2X2 =74X1 +X2 9X1 , X2 0minW=7y1 +9y23y1+4y2 5 -2y

52、1 +y2 6y1自由自由 , y2 0解：对偶问题解：对偶问题线性规划(研究生)例例2 2、写对偶规划、写对偶规划minZ= 4X1 +2X2 -3X3 -X1+2X2 62X1 +3X3 9 X1 +5X2 -2X3 = = 4X2 , X3 0maxW= 6y1 +9y2 +4y3 -y1+2y2 + y3 = = 42y1 +5y3 2 3y2 -2y3 -3y1 0 , y2 0 , y3自由自由线性规划(研究生)minZ= 4X1 +2X2 -3X3 X1 -2X2 - 62X1 +3X3 9 X1 +5X2 -2X3 = = 4X2 , X3 0或将原问题变形为或将原问题变形为线

53、性规划(研究生)maxW= -6y1 +9y2 +4y3 y1+2y2 + y3 = = 4-2y1 +5y3 2 3y2 -2y3 -3y1 , y2 0 , y3自由自由对偶规划对偶规划线性规划(研究生)产品产品A，B产量为产量为X1，X2，Z为利润为利润例例1、3X1 +X2 +X3=483X1 +4X2 +X4=120X1 X4 0maxZ= 5X1 +6X2 3X1 +X2 483X1 +4X2 120X1 , X2 0机器台时机器台时劳动工时劳动工时线性规划(研究生)X=(8,24)T Z =184 5 6 0 0 X1 X2 X3 X40 X3 48 3 1 1 00 X4 12

54、0 3 (4) 0 1 0 5 6 0 0 0 X3 18 (9/4) 0 1 -1/46 X2 30 3/4 1 0 1/4 180 1/2 0 0 -3/2 5 X1 8 1 0 4/9 -1/96 X2 24 0 1 -1/3 1/3 7 184 0 0 -2/9 -13/9线性规划(研究生)3y1+3y2 5 y1 +4y2 6minW=48y1+120y23y1+3y2 -y3+y5 =5 y1 +4y2 -y4+y6= 6minW=48y1+120y2 +My5 +My6线性规划(研究生)y=(2/9,13/9), Z=184 48 120 0 0 48 120 0 0 M M y

55、1 y2 y3 y4 y5 y6M y5 5 3 3 -1 0 1 0 5 3 3 -1 0 1 0 M y6 6 1 6 1 4 0 -1 0 1 4 0 -1 0 1 yB 1111M 48-4 48-4M 120-7M M M 0 0 0 0M y5 1/2 9/4 0 -1 3/4 1 -3/4120 y2 3/2 3/2 1/4 1/4 1 0 -1/4 0 0 -1/4 0 1/4 yB 180+1/2 180+1/2M 18-9/4 18-9/4M 0 0 M 30-3/4 30-3/4M 0 -30+7/4 0 -30+7/4M48 48 y1 2/9 1 2/9 1 0 -4

56、/9 1/3 4/9 -1/30 -4/9 1/3 4/9 -1/3120 y2 13/9 0 1 1/9 -1/3 -1/9 1/3 13/9 0 1 1/9 -1/3 -1/9 1/3 yB 184 0 0 8 24 184 0 0 8 24 M-8 -8 M-24线性规划(研究生)观察结论观察结论: 一对对偶问题都有最优解，且目标函数一对对偶问题都有最优解，且目标函数值相等。值相等。 最优表中有两个问题的最优解。最优表中有两个问题的最优解。线性规划(研究生)1.5.2 对偶问题解的性质对偶问题解的性质maxZ=CX AX b X 0(LP)minW=yb yA C y 0(DP)线性规划

57、(研究生)定理定理1、(对称性）对偶问题的对偶是原问题对称性）对偶问题的对偶是原问题。定理定理2、(弱对偶定理弱对偶定理)分别为分别为(P), (D)的可行解，则有的可行解，则有C bX， yX y证明：由证明：由AX b, y 0 有有 yAX b y 由由Ay C, X 0 有有 yAX C X所以所以CX yAX yb线性规划(研究生)推论推论2、(LP)有可行解有可行解, 但无有限最优解，则但无有限最优解，则(DP)无无可行解。可行解。定理定理3、 yX,分别为分别为(LP), (DP)的可行解，且的可行解，且X yC=b , 则它们是则它们是(LP), (DP) 的最优解。的最优解。

58、证明：对任证明：对任X，有，有CX b y =CXX最优最优推论推论1、(LP), (DP)都有可行解，则必都有最优解。都有可行解，则必都有最优解。线性规划(研究生)定理定理4、B为为(LP)的最优基，则的最优基，则 y= CB B-1 是是(DP)的最优解。的最优解。 y推论：推论： 分别为分别为(LP), (DP)可行解，又是最可行解，又是最优解，则有优解，则有X y,X yC=b线性规划(研究生)定理6 （互补松驰性）若X*、Y*分别是原问题和对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(其中XS，YS分别是原问题和对偶问题的松驰变量向量)。证明：设原问

59、题和对偶问题的标准型是 原问题 对偶问题定理5 （强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。 线性规划(研究生)将原问题目标函数中的系数向量C用 代替后，得到 将对偶问题的目标函数中的系数向量，用 代替后，得到 若 ；则 故 是最优解。又若 分别是原问题和对偶问题的最优解，则必有 线性规划(研究生) 一般而言，我们把某一可行点（如一般而言，我们把某一可行点（如X*和和Y*）处）处的严格不等式约束（包括对变量的非负约束）称为的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如松约束，而把严格等式约束称为紧约束。所以有

60、如下结论：下结论： 设一对对偶问题都有可行解，若原问题的某一设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。是其对偶问题最优解的紧约束。例121 已知试通过求对偶问题的最优解来求解原问题的最优解。线性规划(研究生)解：对偶问题为用图解法可求得对偶问题的最优解：Y*=（1，3），W=11。将代入对偶约束条件，（1），（2），（5）式为紧约束，（3），（4）为松约束。令原问题的最优解为X* = （x1，x2，x3，x4，x5），则根据互补松弛条件，必有x3 = x4 =0又由于，原问题的约束

61、必为等式，即线性规划(研究生)化简为化简为 此方程组为无穷多解此方程组为无穷多解 令令x5 =0,得到得到x1=1，x2=2， 即即X*1 =（1，2，0，0，0）为原问题的一个最优解，）为原问题的一个最优解，Z=11。 再令再令 x5 =2/3，得到，得到x1=5/3，x2=0，即即X*2（5/3，0，0，0，2/3）也是原问题的一个最）也是原问题的一个最优解，优解，Z=11。线性规划(研究生)1.5.3 1.5.3 对偶解的经济意义对偶解的经济意义(1)(1)、Z= CBB-1b + (CN - CBB-1 N)XN (*) Z= Z(b) b为资源为资源对对(*)求偏导：求偏导： Z b

62、=CBB-1= y对偶解对偶解y y：b b 的单位改变量所引起的目标函数的单位改变量所引起的目标函数改变量。改变量。线性规划(研究生)经济解释：经济解释：W=yb=(y1 ym )b1bm= b1 y1 + b2 y2 + + bm ymbi ： 第第 i 种资源的数量种资源的数量yi ：对偶解：对偶解bi增加增加 bi , ,其它资源数量不变时其它资源数量不变时, ,目标函数目标函数的增量的增量 Z=bi yiyi ：反映：反映bi 的边际效益的边际效益( (边际成本边际成本) )例例1 1中中y1 =2/9, 当机器台时数增加当机器台时数增加1个单位时，个单位时，工厂可增加利润工厂可增加

63、利润2/9个单位。个单位。线性规划(研究生)（3）、影子价格的作用）、影子价格的作用（1）指出企业挖潜革新的途径影子价格0，说明该资源已耗尽，成为短线资源。影子价格=0，说明该资源有剩余，成为长线资源。（2）对市场资源的最优配置起着推进作用即在配置资源时，对于影子价格大的企业，资源优先供给（3）可以预测产品的价格产品的机会成本为CBB-1A-C，只有当产品价格定在机会成本之上，企业才有利可图。（4）可作为同类企业经济效益评估指标之一。对于资源影子价格越大的企业，资源的利用所带来的收益就越大，经济效益就越好。线性规划(研究生)通过以上讨论可知：通过以上讨论可知： 某资源对偶解某资源对偶解00，该

64、资源有利可图，可增，该资源有利可图，可增加此种资源量；某资源对偶解为加此种资源量；某资源对偶解为0 0，则不增加此，则不增加此种资源量。种资源量。 直接用影子价格与市场价格相比较，进行直接用影子价格与市场价格相比较，进行决策，是否买入该资源。决策，是否买入该资源。线性规划(研究生)1.5.4 1.5.4 对偶单纯形法对偶单纯形法思路：思路：( (max型型) )单纯形法：找基单纯形法：找基B B，满足，满足B-1b 0，但但 C - CBB-1 A不全不全 0，（，（即检验数）。即检验数）。迭代迭代保持保持B-1b 0，使使C -CBB-1 A 0，即即CBB-1 A C线性规划(研究生)对偶

65、单纯形法：找基对偶单纯形法：找基B B，满足，满足C - CBB-1 A 0，但但B-1b不全不全 0迭代迭代保持保持C -CBB-1 A 0，使使B-1b 0线性规划(研究生)对偶单纯形法基本步骤对偶单纯形法基本步骤 max型型( (min型型) )(1)、作初始表，要求全部作初始表，要求全部j 0 ( 0)(2)、判定：判定： B-1 b全全 0，停停。否则，取否则，取max B-1 b =(B-1 b)l B-1 b0令第令第 l 行的行的Xj l为换出变量为换出变量. .线性规划(研究生)(3)、确定换入变量确定换入变量 若若Xi l行的行的alj 全全 0 ，停，原问题无可行解。停，

66、原问题无可行解。 若若Xi l行的行的alj 有有alj 0 ,则求则求j k =min =aljalkalj 0 Xk为换入变量为换入变量k alk(4)、以以alk 为主元，换基迭代为主元，换基迭代线性规划(研究生) 关于关于的解释：第的解释：第 l 个方程个方程(B-1 b)l= xil + alj xj j N即即 xil = (B-1 b)l - alj xj 0某某xj 从从00 ，xil不能变不能变0为保持为保持j 0 ，即对偶解可行性即对偶解可行性线性规划(研究生)例例1 1：Max Z =2X1 +X2X1+ X2 + X3 = = 5 2X2 + X3 5 4X2 +6X3

67、 9X1 , X2 , X3 0线性规划(研究生)maxZ=2X1 +X2X1+ X2 + X3 = = 5 2X2 + X3 +X4 = 5 -4X2 -6X3 +X5 =-9X1 X5 0B=(P1 P4 P5)CN - CBB-1 N=(1,0)-(2,0,0)1 12 1-4 -2=(-1,-2)线性规划(研究生)CB 2 1 0 0 0 XB X1 X2 X3 X4 X5 2 X1 5 1 1 1 0 0 0 X4 5 0 2 1 1 0 0 X5 -9 0 (-4) -6 0 1 10 0 -1 -2 0 0 X1 11/4 1 0 -1/2 0 1/4 X4 1/2 0 0 -2

68、 1 1/2 X2 9/4 0 1 3/2 0 -1/4 31/4 0 0 -1/2 0 -1/4129线性规划(研究生)例例2 2minZ=2X1 +3X2 +4X3 X1+2X2 + X3 32X1 - X2 +3X3 4X1 , X2 , X3 0minZ=2X1 +3X2 +4X3 -X1 -2X2 - X3 +X4 = - 3-2X1+ X2 -3X3 +X5 = - 4X1 X5 0线性规划(研究生) 2 3 4 0 0 XB X1 X2 X3 X4 X5 0 X4 -3 -1 -2 -1 1 00 X5 -4 (-2) 1 -3 0 1 0 2 3 4 0 00 X4 -1 0

69、(-5/2) 1/2 1 -1/22 X1 2 1 1/2 3/2 0 -1/2 4 0 4 1 0 1 X2 2/5 0 1 -1/5 -2/5 1/5 X1 11/5 1 0 7/5 -1/5 -2/5 28/5 0 0 9/5 8/5 1/5线性规划(研究生)影子价格影子价格 由对偶解的经济解释可知，由对偶解的经济解释可知，yi的大小与系的大小与系统内资源对目标的贡献有关，是资源的一种估统内资源对目标的贡献有关，是资源的一种估价，称为影子价格。价，称为影子价格。 yi的准确经济意义与建模有关。的准确经济意义与建模有关。情况情况 模型中，目标函数系数模型中，目标函数系数Ci 表示利润时，表

70、示利润时， yi 不是真正的影子价格，只表示资源不是真正的影子价格，只表示资源bi 增加增加1 1单单位时，企业目标增加的净利润。位时，企业目标增加的净利润。情况情况 模型中，目标函数系数模型中，目标函数系数Ci 表示成本时，表示成本时， yi 是真正的影子价格。是真正的影子价格。线性规划(研究生)对偶单纯形的优点与用途： （1）初始解可以是非可行解，当检验数都是正数时，就可以进行基变换，这样避免了增加人工变量，使运算简便。（2）对变量较少时，而约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形求解，简化计算。（3）用于后面的灵敏度分析。线性规划(研究生)第六节第六节 灵敏度分析

71、灵敏度分析CBB-1b C - CBB-1 AB-1 b B-1 A原始数据原始数据A A，b b，C CA=(A=(P1 P2 Pn ) )公式公式 Z Z0= = CBB-1b X XB= = B-1b A = = C - CBB-1 A N = = CN - CBB-1 N j = = Cj- CBB-1 Pj A= A= B-1 A Pj = =B-1 Pj 线性规划(研究生)标准型标准型 maxZ=CX AX = =b X 0(1)、参数、参数A，b，C在什么范围内变动，对当在什么范围内变动，对当前方案无影响？前方案无影响？(2)、参数、参数A，b，C中的一个中的一个(几个几个)变动

72、，对变动，对当前方案影响？当前方案影响？(3)、如果最优方案改变，如何用简便方法求、如果最优方案改变，如何用简便方法求新方案？新方案？线性规划(研究生)例：例： A B C 备用资源备用资源 甲甲 1 1 1 12 乙乙 1 2 2 20 利润利润 5 8 6 产品产品原料原料问：如何安排产品产量，可获最大利润？问：如何安排产品产量，可获最大利润？线性规划(研究生)maxZ=5X1 +8X2 +6X3X1+ X2 + X3+X4 = 12X1+2X2+2X3 +X5 =20X1 X5 0解解线性规划(研究生) 5 8 6 0 0 X1 X2 X3 X4 X5 0 X4 12 1 1 1 1 0

73、 0 X5 20 1 2 2 0 1 0 5 8 6 0 0 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 1 84 0 0 -2 -2 -3线性规划(研究生)(一一)、目标函数中的价值系数、目标函数中的价值系数Cj的灵敏度分的灵敏度分析析(1)、非基变量系数、非基变量系数Cj由于检验数由于检验数 j = Cj -CBB-1 Pj Cj 改变，改变， j仍仍 0 0 时对最优方案无影响。时对最优方案无影响。例中例中C3改变改变 3 = C3 -CBB-1 P3 =C3 -(5 8) =C3 -8 0 0 2 -1-1 112即即C3 8 线性规划(研究生) C3改为改为1

74、0， 3 =20 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 (1) -1 1 84 0 0 (2) -2 -3 5 X1 4 1 0 0 2 -110 X3 8 0 1 1 -1 1 11 100 0 -2 0 0 -5 单位产品C的利润为10，则最优方案调整为 X=(4,0,8)T,目标值为100。线性规划(研究生)(2)、基变量系数、基变量系数Cj Cj 改变，改变， 全部全部 j 0 0，最优方案不变。最优方案不变。例中例中C1改变改变 A = C -CBB-1 A =(C1 ,8,6,0,0 ) -(C1 8) 1 0 0 2 -10 1 1 -1 1=(0,0,-2,

75、-2C1+8, C1 -8) 0-2C1+8 0C1-8 04 C1 8即单位产品A的利润在4,8之间变化时,最优方案不变。线性规划(研究生) C1改变改变 C1=10， 5 =20 ,换基换基10 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 (1) 104 0 0 -2 -12 2 10 X1 12 1 1 1 1 0 0 X5 8 0 1 1 -1 1 120 0 -2 -4 -10 0 单位产品A的利润为10，则最优方案调整为 X=(12,0,0)T,目标值为120。线性规划(研究生)(二二)、资源约束数量、资源约束数量 bj 的灵敏度分析的灵敏度分析 由于由于bj

76、的改变，并不影响检验数，它只对最优的改变，并不影响检验数，它只对最优方案有影响。方案有影响。(1)、bj 改变，改变， B-1 b仍仍 0时，最优方案的生时，最优方案的生产种类不变，生产数量发生改变。产种类不变，生产数量发生改变。例中例中b1改变改变2 -1-1 1b12010 b1 20 B-1 b= 02b1 -20 0-b1+20 0即原料甲的供应在10，20之间时并不影响生产种类。线性规划(研究生)(2)、 b1改变改变, b1=30 ，5 X1 40 1 0 0 2 -1 8 X2 -10 0 1 1 (-1) 1 120 0 0 -2 -2 -35 X1 20 1 2 2 0 1

77、0 X4 10 0 -1 -1 1 -1 100 0 -2 -4 0 -5 2 -1-1 13020B-1 b= 40-10 原料甲的供应为30，则最优方案调整为 X=(20,0,0)T,目标值为100。线性规划(研究生)(三三)、添加新变量的灵敏度分析、添加新变量的灵敏度分析例例 对于新产品对于新产品D D，已知已知1 1个单位个单位D D要消耗要消耗 甲：甲：3 3 乙：乙：2 2 可以得利润可以得利润1010问：投产产品问：投产产品D D是否有利？是否有利？ 6 = C6 - CBB-1 P6 = 10 - (5 8) 2 -1 3 -1 1 2 = 10 - 12 = -2 0 得得

78、C6 12（2 2） C6 =15 时时 6 =3 P6 = B-1 P6 = 2 -1 3 = 4 -1 1 2 -1 线性规划(研究生) X1 X2 X3 X4 X5 X6 X1 4 1 0 0 2 -1 (4) X2 8 0 1 1 -1 1 -1 84 0 0 -2 -2 -3 3 X6 1 1/4 0 0 -1/2 -1/4 1 X2 9 1/4 1 1 -1/2 3/4 0 87 -3/4 0 -2 -7/2 -9/4 0 单位单位D D的利润为的利润为1515时，生产时，生产B B产品产品9 9件，生产件，生产D D产品产品1 1件。件。目标值为87。线性规划(研究生)(四四)、

79、添加新约束的灵敏度分析、添加新约束的灵敏度分析例例 新增加电力约束：新增加电力约束：1313 A A、B B、C C每单位需电每单位需电 2 2、1 1、3 3问：原方案是否改变问：原方案是否改变？2X1 +X2 +3X3 1313 原方案原方案 A A：4 B4 B：8 C8 C：0 0需电需电 4 42 28 816 13 16 13 原方案要改变原方案要改变 2X1 +X2 +3X3 +X6 = = 1313 user:线性规划(研究生) X1 4 1 0 0 2 -1 0 X2 8 0 1 1 -1 1 0 X6 13 2 1 3 0 0 1 84 0 0 -2 -2 -3 0 5 X

80、1 4 1 0 0 2 -1 0 8 X2 8 0 1 1 -1 1 0 0 X6 -3 0 0 2 (-3) 1 1 84 0 0 -2 -2 -3 0 5 X1 2 1 0 4/3 0 -1/3 2/38 X2 9 0 1 1/3 0 2/3 -1/30 X4 1 0 0 -2/3 1 -1/3 -1/3 82 0 0 -10/3 0 -11/3 -2/3 线性规划(研究生)(五五)、技术系数、技术系数aij改变改变(计划生产的产品工艺结构改变计划生产的产品工艺结构改变) )(1)、非基变量、非基变量Xj工艺改变工艺改变只影响单纯形表只影响单纯形表Pj 列列， j .关键看关键看 j 0?

81、 还是还是0? . 用用(三三)类似方法解决。类似方法解决。(2)、基变量、基变量Xj工艺改变，复杂工艺改变，复杂线性规划(研究生)例：产品例：产品A工艺改变，对甲、乙需求变为工艺改变，对甲、乙需求变为2，2。 利润为利润为7，问最优方案如何？问最优方案如何？先计算先计算 p1= 2 -1 2 = 2 -1 1 2 0一一 1= -7 取代取代 p1 与与 1 放入最优表放入最优表一一一一一一线性规划(研究生) X1 X1 X2 X3 X4 X5 X1 4 1 2 0 0 2 -1 X2 8 0 0 1 1 -1 1 0 -7 0 -2 -2 -3 7 X1 2 1 0 0 1 -1/2 8

82、X2 8 0 1 1 -1 1 70 0 0 -2 5 -13/2 0 X4 2 1 0 0 1 -1/2 8 X2 10 1 1 1 0 1/2 80 -5 0 -2 0 -7/2这时最优方案发生了改变。线性规划(研究生)例例 p1 = 1 C1 = 7 3p1 = B-1 p1 = 2 -1 1 = -1 -1 1 3 2 1= -4一一一一也可能也可能 B-1 b出现负数出现负数检验数与基变量均不满足最优解要求检验数与基变量均不满足最优解要求基变量基变量Xj工艺改变工艺改变线性规划(研究生) X1 X1 X2 X3 X4 X5 X1 4 1 -1 0 0 2 -1 X2 8 0 2 1

83、1 -1 1 84 -4 0 -2 -2 -3 X1 -4 1 0 0 -2 1 X2 16 0 1 1 3 -1 68 0 0 -2 -10 1 线性规划(研究生)X1 - 2X4 +X5 = -4-X1 +2X4 -X5 +X6 = 4 X1 X2 X3 X4 X5 X6 X6 4 -1 0 0 (2) -1 1 X2 16 0 1 1 3 -1 0 -M+7 0 -2 2M-24 -M+8 0 X4 2 -1/2 0 0 1 -1/2 1/2 X2 10 3/2 1 1 0 1/2 -3/2 -5 0 -2 0 -4 -M+12 用用X6作为基变作为基变量代替量代替X1线性规划(研究生)