《线性规划研究生》PPT课件.ppt

运运 筹筹 学学•南京航空航天大学经济与管理学院南京航空航天大学经济与管理学院• 教授、博士生导师• 管理科学与工程系主任• iamdangyg@緒緒 论论 一一 运筹学发展简史运筹学发展简史 中国古代的“齐王赛马”就是对策论的一个典型实例作为运筹学的早期工作其历史可追溯到1914年： 1914年英国人兰彻斯特(F.W.Lanchester)呈发表过关于人与火力的优势与胜利之间的理论文章，这就是军事运筹学中著名的“兰彻斯特战斗方程” 排队论的先驱者丹麦工程师爱尔朗(A.K.Erlang)1917年在哥本哈根公司研究通信系统时，提出了排队论的一些著名公式 20世纪30年代，荷兰人荷雷斯•列文生(Horace.C.Le venson)用运筹学思想分析商业广告和顾客心理，由此提出了存储论中著名的“经济批量公式” 1947年，美国数学家丹捷格(G.B.Dantizg)发表了关于线性规划的研究成果，所解决的问题是美国空军军事规划时提出的，并给出了求解线性规划问题的单纯形算法。

事实上，早在1939年苏联学者康托洛维奇(Л.В.Канторович)在解决工业生产组织和计划问题时，已提出了类似线性规划的模型，并给出了“解乘数法”的求解方法由于当时未被重视，直到1960年康托洛维奇再次发表了《最佳资源利用的经济计算》一书后，才受到国内外的一致重视为此康托洛维奇获得了诺贝尔经济学奖 因为它与研究技术问题不同，就称之为“运用研究”或“操作研究”(Operational Research)研究内容是： 1.研究护航舰队保护商船队的编队问题，即当船队遭受德国潜艇攻击时，如何使船队损失最小； 2. 研究反潜深水炸弹的合理爆炸深度，这使得德国潜艇被摧毁数增加了400%；3. 研究船队在遭受敌机攻击时，大船应急转向而小船应缓慢转向的逃避方法，其结果，使船只在受敌机攻击时，中弹船只数由47%降到29% 在20世纪50年代中期，我国科学家钱学森、许国志等人将运筹学由西方引入我国，并结合了我国的特点在国内推广应用在经济数学方面，特别是投入产出表的研究和应用开展得较早质量控制(后改为质量管理)的应用也有特色在此期间，以华罗庚敎授为首的一大批数学家加入到运筹学的研究队伍，使运筹学的很多分支很快跟上当时的国际水平。

我国第一个运筹学小组于1956年在中国科学院力学研究所成立，1960年在山东济南召开全国应用运筹学的经验交流和推广会议，1962年在北京召开了全国运筹学专业学术会议，1980年4月成立中国运筹学学会上世纪50年代中期，以华罗庚为首的一大批科学家加入到运筹学的研究中，首先在一些企业、事业单位积极推广优选法、统筹法等运筹学方法，取得显著成果；并成立了优选法、统筹法与经济数学研究会学会主要研究运筹学，但没有称为运筹学如今，运筹学已经成为所有大学的经济与管理学院、工学院与计算机专业、应用数学专业的基础课程 二、二、 运筹学的工作步骤运筹学的工作步骤 运筹学在解决大量实际问题的过程中形成了自己的工作步骤：1.提出和形成问题：提出和形成问题：即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数及有关资料2.建立模型：建立模型：即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来3.求解：求解：用各种手段(主要是数学方法，也可用其它方法)将模型求解解可以是最优解、次优解、满意解.复杂模型的求解需用计算机,解的精度要求由决策者提出4.解的检验：解的检验：首先检验求解步骤和程序有无错误，然后检查解是否反映现实问题。

5.解的控制：解的控制：通过控制解的变化过程决定对解是否要作一定的修改6.解的实施：解的实施：是指将解用到实际中去，必须考虑到实际的问题，如向实际部门讲清楚解的用法，在实施中可能产生的问题等 以上过程应反复进行  三、三、 运筹学的应用与展望运筹学的应用与展望 在运筹学的发展简史中，已提到了运筹学在早期的应用，主要在军事领域二次大战后运筹学的应用转向民用，主要应用于：(1)市场销售：在广告预算和媒介的选择、竞争性定价新产品开发、销售计划的制定等方面2)(2)生产计划：在总体计划方面主要是从总体确定生产、存储和劳动力的配合等计划以适应波动的需求计划,主要用线性规划和模拟的方法等3)(3)库存管理:主要应用于多种物资库存的管理,以确定合理的库存量4)(4)运输问题：各种运输的调度与计划安排5)(5)财政和会计：这里主要涉及预算、贷款、成本分析、定价、投资、证券管理、现金管理等用得较多的方法是：统计分析、数学规划、决策分析(6)人事管理：一是人员的获得和需求估计；二是人才的开发，即进行教育和培训；三是人员的分配；四是各类人员的合理利用问题；五是人才的评价，其中有如何测定一个人对组织、社会的贡献;六是工资和津贴的确定等。

7)设备维修、更新和可靠性、项目选择和评价8)工程的优化设计：这在建筑、电子、光学、机械和化工等领域都有应用9)计算机和信息系统：(10)城市管理：包含了各种紧急服务系统的设计和运用四、最优化问题举例1、多参数的曲线拟合问题 已知热敏电阻R依赖于温度t的函数关系2、生成成本问题介绍Cobb-Douglas生产函数 3、资源分配问题、资源分配问题考虑将m种资源安排给n种活动，问应如何分配资源，才能使收益最大？在某些实际应用中，有时考虑的利润c1,c2,…cn并不是固定的数值，而是随机变量，假定C是一个均值为这是线性分式规划最优化的分类图离散规划整数规划非线性最小二乘球面规划非线性等式最优化连续优化离散优化有约束无约束线性规划不可微分规划非线性规划网络规划随机规划参考书 1、卢向华，等著《运筹学教程》，高等教育出版社 2、钱颂迪，《运筹学》，清华大学出版社 3、林同曾，《运筹学》，机械工业出版社 4、胡运权， 《运筹学教程》，清华大学出版社 第 一章 线 性 规 划 第 一 节 线性规划模型及其图解法 线性规划是运筹学的一个重要分枝。

自1947年美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法——单纯形法之后，线性规划在理论上趋于成熟，在实际中的应用日益广泛与深入特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后，它的适用领域更广泛了从解决技术问题中的最优化设计到工业、农业、商业、交通输业、军事、经济计划与管理、决策等各个领域均可发挥作用；从范围来看，小到一个小组的日常工作和计划安排，大至整个部门以致国民经济计划的最优方案的提出，都有用武之地它具有适应性强、应用广泛、计算技术比较简单的特点，是现代管理科学的重要基础和手段之一一、线性规划模型线性规划：就是一个线性函数性等式或不等式约束条件下的极值问题线性规划研究的问题主要有两类： 1、任务确定后，如何统筹安排，尽量做到用尽量少的人力和物力资源来完成任务； 2、有一定量的人力、物力资源，如何安排使用他们，使完成的任务（创造的利润）最多 在生产管理和经济活动中经常提出这样一类问题， 即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果例例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的数量，则该计划问题可用如下数学模型表示为： 目标函数 Max Z = 2x1 +3x2 约束条件例例2 某某汽汽车车厂厂生生产产大大轿轿车车和和载载重重汽汽车车，，所所需需资资源源、、资源可用量和产品价格如下表所示资源可用量和产品价格如下表所示: 大轿车大轿车 载重汽车载重汽车 可用量可用量钢材（吨）钢材（吨） 2 2 1600工时工时(小时小时) 5 2.5 2500大轿车座椅大轿车座椅 400（辆）（辆）获利获利(千元千元/辆辆) 4 3问应如何组织生产才能使工厂获利最大？问应如何组织生产才能使工厂获利最大？ 例2的数学模型s.t.,例3 下料问题•某工厂要做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)每个问题都用一组决策变量(x1 , x2 , ··· , xn)表示某一(2)方案 ,这组未知数的值就代表一个具体的方案,通常要求这些未知数取值是非负的2) 存在一定的限制条件(称为约束条件),这些条件都可以用关于决策变量的一组线性等式或不等式来表示3) 都有一个目标要求,并且这个目标可表示为这组决策 变量的线性函数(称为目标函数),按研究问题的不同,要求目标函数实现最大化或最小化 满足以上三个条件的数学模型称为线性规划数学模型其一般形式为(1.1)和(1.2)形式 在该模型中,方程(1.1)称为目标函数;(1.2)称为约束条件。

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

等值线沿箭头方向移动目标函数的等值线，平移等值线直至与可行域OABCD相切或融合为一条直线，此时就得到最优解为C 点，其坐标可通过解方程组得到：例2：用图解法求解线性规划问题 MAX Z=4x1+3x2 s.t. 2x1+2x2 ≤1600 5 x1+2.5x2 ≤ 2500 x1 ≤ 400 x1,x2≥0由约束条件得到可行域OABCD由等值线Z=4x1+3x2沿箭头方向向上平移与可行域交于B点，则B点就是最优点最优值等于26000Z= 40 X1 + 80X2 =0 X1 + 2X2 =30DABCX2X1求解最优解：求解最优解：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 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）若在两个顶点上同时得到最优解，则在这两点的连线上的任一点都是最优解。

（4）若可行域无界，则可能发生最优解无界的情况； （5）若可行域是空集，此时无最优解上述理论具有普遍意义，对于两个以上变量的线性规划问题都成立 图解法虽然直观、简便等优点，在变量多的情况下，即在多维的情况下，它就无能为力了因此，需要介绍一种代数方法——单纯型法，为了以后介绍方便讨论，需要研究一下线性规划数学模型的标准化问题三、线性规划问题的标准型三、线性规划问题的标准型 由前面所举的例子可知,线性规划问题可能有各种不同的形式目标函数有实现最大化也有实现最小化的;约束条件可以是“ ”形式、“”形式不等式,有的是等式决策变量有时有非负限制有时没有这种多样性给讨论问题代来了不便为了便于今后讨论，我们规定线性规划问题的标准型为：  这里我们假设 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 为约束方程组的系数矩阵( m×n阶),一般情况下 m < n , m , n 为正整数,分别表示约束条件的个数和决策变量的个数, C 为价值向量, X 为决策向量, 通常aij , bi , cj ( i = 1, 2, ···, m , j = 1, 2, ···, n ) 为已知常数 实际上，具体问题的线性规划数学模型是各式各样的,需要把它们化成标准型,并借助于标准型的求解方法进行求解.以下就具体讨论如何把一般的线性规划模型化成标准型1.若要求目标函数实现最小化时. 即此时的目标函数是: Min Z = CTX , 这时只需要将目标函数的最小值变换为求目标函数的最大值,即 Min Z = Max (- Z) 令Zˊ= -Z，于是就得到： Max Zˊ= - CTX 2. 若约束方程组为不等式这时有两种情况:一是约束条件为“  ”形式的不等式,则在“  ” 号的左边加入非负的松弛变量;把原“  ” 形的不等式变为等式;另一种是约束条件为“  ”形式的不等式,则可在“  ”号的左端减去一个非负的剩余变量相应的松弛变量或剩余变量在目标函数中的价值系数取值为0。

3. 若存在无非负要求的变量. 即有某一个变量 xj 取正值或负值都可以. 这时为了满足标准型对变量的非负要求,可令 xj = xjˊ- xj〞, 其中: xjˊ、 xj〞 0 ，由于xjˊ可能大于也可能小于xj〞，故 xj 可以为正或为负上述的标准型具有如下特点： （1）目标函数求最大值； （2）所求的变量都要求是非负的； （3）所有的约束条件都是等式； （4）常数项非负 综合以上的讨论可以说明任何形式的线性规划问题都可以通过上述手续把非标准型式的线性规划问题化成标准型现举例如下：例：将例1的数学模型化为标准型 max Z=2x1+3x2 2x1+2x2 ≤12 x1+2x2≤8 4x2≤12 4x1 ≤16 x1, x2≥0 解：引进4个新的非负变量x3,x4,x5,x6使不等式变为等式，标准型为： Max Z=2x1+3x2+0·x3+0 · x4+0 · x5+0 · x6 2x1+2x2+x3 =12 x1+2x2+ x4 =18 4x1+ x5 =16 4x2+ x6 =12 x1, x2,x3,x4,x5,x6≥0例例4: 试将如下线性规划问题化成标准型解：解：令 x3 = x4 - x5 , x4 , x5  0 , (1)式左端加上非负松弛变量 x6 , (2)式左端减去非负剩余变量 x7 , 则可将上述线性规划问题化成如下的标准型:1.可行解可行解: 满足约束条件(1.7),(1.8)的解 X = ( x1, x2, ···, xn)T 称为线性规划问题的可行解;所有可行解的集合称为可行解集或可行域。

2.最优解最优解: 满足约束条件及目标函数(1.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,···,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, ··· , xm , 0, ···, 0 )T ,这个解的非0分量的数目不大于方程个数 m ,称 X 为基本解.4.基本可行解基本可行解 : 满足非负条件(1.8)的基本解称为基本可行解.由此可见,基本可行解的非0分量的数目不大于 m ,并且都是非负的。

5.可行基可行基: 对应于基本可行解的基称为可行基.由此可见,约束方程组(1.7)基本解的数目至多是 Cnm 个.一般地讲,基本可行解的数目要小于基本解的数目,至多相等.6. 以上提到的几种解的概念,可用如下图来表示:基解可行解基本可行解 第二节第二节 线性规划问题的几何意义线性规划问题的几何意义 在上一节的图解法中,我们已经直观地看到了可行和最优解的几何意义,这一节从理论上进一步讨论一、基本概念：一、基本概念：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 维欧氏空间 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：：若线性规划问题存在可行域，则其可行域： 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 < m 时，则一定可以从其余的列向量中取出 m – k 个与P1, P2, ···,Pk 构成最大的线性无关向量组,其对应的解恰为 X ,所以根据定义是基本可行解(此时为退化的基本可行解)。

定理定理2: 线性规划问题的基本可行解对应于可行域的顶点.引理引理2：：若 K 是有界凸集，则任何一点 Z K 可表示为K 的顶点的凸组合定理定理3: 若可行域有界,则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优解定理定理4 (线性规划问题的基本定理线性规划问题的基本定理)(1)若线性规划问题存在可行解,则一定存在基本可行解;(2)若线性规划问题存在最优解,则一定存在最优的基本可行解根据以上讨论得到如下的结论： （1）线性规划问题的所有可行解的集合一般是凸集，它可以是有界的，也可以是无界的区域；仅有有限个顶点 (2) 线性规划问题的每一个基本可行解对应于可行域的一个顶点若线性规划问题有最优解，必定可在某顶点处取到 (3) 如果一个线性规划问题存在多个最优解，那么至少有两个相邻的顶点处是线性规划的可行解 （4） 如果有一个顶点处可行解的目标值比其它相邻顶点可行解的目标值优的话，那么它就比其它所有顶点的可行解的目标值优或者说，它就是最优解  虽然可行域的顶点个数是有限的(它们不超过 Cnm 个)，采用“枚举法”找出所有基本可行解，然后一一比较它们的目标函数值的大小，最终可以找到最优解。

但当 m、n 的数目相当大时，这种办法实际上是行不通的因此，我们还要继续讨论一种方法，通过逐步迭代保证能逐步改进并最终求出最优解 第第 三三 节节 单纯形算法单纯形算法 单纯形算法的基本思路是: 根据问题的标准型,从可 行域中某个基本可行解 (顶点)开始,转换到另一个基本可行解(顶点),并使得每次的转换,目标函数值均有所改善,最终达到最大值时就得到最优解 对于标准线性规划问题(简写为 LP): 这里 A = ( aij)mn , 秩A = m 首先假定已求得(LP)的一个基本可行解 X(0) ,为叙述方便, 不失一般性,假设:X(0) = ( x1(0), x2(0), ···, xm(0), 0, ···, 0 )T  ( XB(0), XN(0) )T,其对应的基为: B = ( P1, ···, Pm ) , 其中 Pj = ( a1j , ···, amj )T, j = 1,2, ···,m , 对应的价值系数分别记为 CB = ( c1, ···, cm )T ,CN = ( cm+1, ···, cn )T, 又记 N = ( Pm+1, ···, Pn ) , 由约束条件AX = b , 可以得到: BXB(0) + NXN(0) = b 即: XB(0) = B-1b –B-1NXN(0) (1.21) 上式就是基变量用非基变量表示的形式。

由于 X(0) 是基本可行解 , 且 XN(0) = 0 , 所以 XB(0) = B-1b  0 ;引入记号 b* = B-1b = ( b1*, b2*, ··· , bm* )T ,将(1.21)式代入目标函数整理得: Z = CBTB-1b + ( CNT– CBTB-1N )XN(0) (1.22) 上式就是目标函数用非基变量表示的形式记 Z0 = CBTB-1b , 令 j = cj – CBTB-1Pj , 则显然当 j∈IB = {1 , ···, m } (IB 称为基变量指标集 )时, j = 0 ;当 j∈IN = {m+1 , ···, n } (IN 称为非基变量指标集 )时, j 则不一定等于 0 j 称为检验数，又令 yj = B-1Pj  ( y1j, ···, ymj )T,j∈IN , 则可得出如下的初始单纯形表1—3 cj → c1… ck… cmcm+1… cj… cnCBXB b* x1… xk… xmxm+1… xj… xn c1 x1b1* 1… 0… 0 y1m+1… y1j… y1n … … … … … … … … … ck xkbk* 0… 1… 0ykm+1… ykj… ykn … … … … … … …… … cm xmbm* 0… 0… 1 ymm+1… ymj… ymn C - CBTB-1A 0… 0… 0m+1… j… n 表表1—3 初始单纯形表初始单纯形表 由于 xj  0 , j  0, j∈IN , 所以由(1.23)式可知: CTX  CTX(0) 命题得证。

2. 无有限最优解判别定理无有限最优解判别定理:若 X(0) = ( XB(0), XN(0) )T 为一基本可行解 ,且有一个 j0∈IN , j0 > 0, 而 yj0  0 , 则(LP)无有限最优解(也称为无界解)一、最优性检验与解的判别一、最优性检验与解的判别1.最优解判别定理最优解判别定理: 若 X(0) = ( XB(0), XN(0) )T , 其中XB(0)=B-1b , XN(0) =0 为对应于基 B 的基本可行解 , 且对于一切j∈IN ,有 j  0 , 则 X(0) 已为( LP )的最优解2.证明证明:设 X 为(LP)的一个可行解,令 X = ( XB, XN )T, 代入目标函数值整理得到:3. 基变换基变换: 若非上述两种情形,则由式(1.23)可见,当某些j > 0, xj > 0, j∈IN , 则目标函数值还可以增加为使目标函数值增加最快，我们选择： j = max {l∣l > 0 , l ∈IN } j所对应的变量xj为换入变量(就是下一个基的基变量). 因为基变量个数总是为 m , 所以换入一个之后还必须换出一个。

下面我们来考虑如何选择换出变量 若初始基本可行解X(0)不是最优解，那么就还要找一个新的基本可行解其作法如下： 从原可行基中换出一个列向量，再投入一个新的列向量，（要保证线性无关），从而得到一个新的可行基，这就是基变换 要做基变换要做基变换首先确定换入变量（已讲过），即选择最大的检验数j所对应的非基变量作为换入变量xj(进基变量) 下面再确定换出变量再确定换出变量确定换出变量的原则是保持解的可行性这就说，要使原基本可行解的某一个正分量xj变为0，同时保持其余分量均非负具体实现是按“最小比例原则”进行，也称原则 若则选基变量Xl为换出变量4.旋转运算（迭代）（枢运算） 在确定了换入变量Xk与换出变量Xl之后，要把xk和xl的位置对换，就是说，要把xk 所对应的列向量pk变成单位向量这只对系数矩阵的增广矩阵进行变换即可，称ylk为旋转元以表1—3中的元素 ykl (称为主元素或旋转元素)进行基变换: 将第 k 行每个元素除以 ykl , 将第 k 行每个元素乘以 – yij / ykj 加到第 i 行( i = 1,2, ··· ,m , i ≠ k , j = 1,2, ···, k ),将第 k 行每个元素乘以 – j / ykj 加到检验数行, 对应的新的目标函数值即为：经过基变换之后，针对于新基 B1 的基本可行解 为：综合以上的讨论,单纯形算法的计算步骤可归结如下：第一步：找出初始可行基，确定初始基本可行解 ，建立初始单纯形表；第二步：检查对应于非基变量的检验数 l ，l∈IN ，若所有 l  0 ，l∈IN ，则已得到最优解，停止计算，否则转入下一步；第三步：在所有l > 0，l∈IN 中，若有一个j 对应的系数列向量 yj  0，则此问题没有有限最优解，停止计算，否则转入下一步；第四步：根据 max {l ∣ l > 0，l∈IN } = j ,确定 xj 为换入变量(即为新基的基变量),再根据:确定 xk 为换出变量(即为新基的非基变量), 转下一步；第五步：以 ykj 为主元素进行基变换，转回第二步。

例例5. 利用单纯形算法求解例1的线性规划问题 Max Z=2x1+3x2+0·x3+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,x6≥0 解： （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 （2）max{1, 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 x2 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 -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 第四节第四节 单纯形算法的进一步讨论单纯形算法的进一步讨论一、初始基本可行解一、初始基本可行解 的确定的确定 利用单纯形算法的一个根本前提是要有一个初始的基本可行解 .这对于一些简单问题, 利用观察或其它手段是容易得到的;但对于较复杂的问题, 则利用这种方法几乎是不可行的. 这就引起了人们对求初始基本可行解 的思考.以下我们分几种情形加以讨论。

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

以下举例加以说明例例6. 试用大M法求解如下线性规划问题的最优解解解:在上述问题中加入松弛变量,剩余变量和人工变量得:这里M是一个充分大的正数, 取基变量为 x4 , x6 , x7 , 可得如下的表1—8利用表1—8得初始单纯形表，单纯形算法得表1—9 ～ 表1—11表表1—8cj3-1-100-M -MCBXBb*x1x2x3x4x5x6x70x4111-211000-Mx63-4120-110-Mx71-20[1]0001-Z03-1-100-M -Mcj3-1-100-M -MθCBXBb*x1x2x3x4x5x6x70x4111-21100011-Mx63-4120-1101.5-Mx71-20[1]00011-Z4M 3-6M M-13M-10-M00初始单纯形表表表1—9cj3-1-100-M-MθCBXBb*x1x2x3x4x5x6x70x4103-20100-1－-Mx610[1]00-11-21-1x31-2010001－- ZM+11M-100-M01-3Mcj3-1-100-M-MθCBXBb*x1x2x3x4x5x6x70x412[3]001-22-54-1x210100-11-2－-1x31-2010001－- Z21000-11-M-1-M 表表1—10cj3-1-100-M-MθCBXBb*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 表表1—11在表1—11中，所有的 j  0，故得到最优解： X* = ( 4, 1, 9, 0, 0, 0, 0 )T 目标函数值 Z′= 2 , 原问题的最优目标值为: Z* = -2 。

3. 两阶段法两阶段法: 这种方法是在约束条件中加入人工变量,将线性规划问题分为两阶段进行求解. 第一阶段是先求出基本可行解 (或判断出原线性规划问题无解), 第二阶段利用已求出的初始基本可行解 来求最优解具体由如下定理5给出定理定理5 设原线性规划问题记成(LP), 由它而引入的新的线性规划问题记成(LP)*分别表示如下：1) 若(LP)*具有最优基本可行解 则(LP)是可行的,而 2) 若(LP)*的最优基本可行解 则(LP)必不可行 定理5的具体应用过程是: (LP)*判断原线性规划问题是否存在基本可行解 , 利用单纯形算法, 若得到 W = 0 , 即所有人工变量为非基变量, 这表示原问题已得到了一个基本可行解 .于是只需要将第一阶段最终计算表中的目标函数行的数字换成原问题的目标函数的数字, 就得到了求解原问题的初始计算表, 再进行第二阶段的求解若第一阶段的最终计算表出现 W > 0 , 这就表明原问题无可行解，应停止计算解：解：先在以上问题的约束条件中加入松弛变量、剩余变量、人工变量，给出第一阶段的线性规划问题：各阶段的计算方法及步骤与前述单纯形法完全相同，下面用例子说明该方法的应用。

例例7：：试用两阶段法求解如下线性规划问题以 x4、x6、x7 为基变量得如下初始计算表cj00000-1-1CBXBb*x1x2x3x4x5x6x70x4111-211000-1x63-4120-110-1x71-20[1]0001-W'000000-1-1cj00000-1-1θCBXBb*x1x2x3x4x5x6x70x4111-21100011-1x63-4120-1101.5-1x71-20[1]00011-W'4-6130-100初始单纯形表1—12表表1—13cj00000-1-1θCBXBb*x1x2x3x4x5x6x70x4103-20100-1－-1x610[1]00-11-21-1x31-2010001－-W'10100-10-3表表1—14cj00000-1-1θCBXBb*x1x2x3x4x5x6x70x4123001-22-50x210100-11-20x31-2010001-W'000000-1-1 这里 x6、x7 是人工变量。

第一阶段我们已求得 W ´ = 0 ，最优解 x5 = 0， x6 = 0， x7 = 0因人工变量 x6 = x7 = 0, 所以( 0, 1, 1 ,12, 0 )T 是原问题的基本可行解 于是可以开始第二阶段的计算将第一阶段的最终计算表1—14中的人工变量列取消, 并将目标函数系数换成原问题的目标函数系数, 重新计算检验数行, 可得如下第二阶段的初始单纯形表1—15；应用单纯形算法求解得最终表1—16 表表1—15cj3-1-100CBXBb*x1x2x3x4x50x412[3]001-212/3=4-1x210100-1—-1x31-20100—-Z'21000-1表表1—16cj3-1-100CBXBb*x1x2x3x4x53x141001/3-2/3-1x210100-1-1x390012/3-4/3-Z'-2000-1/3-1/3表1—16中所有检验数 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 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(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目标函数系数目标函数系数 目标函数系数目标函数系数 右边项系数右边项系数与右边项的对应关系与右边项的对应关系 右边项系数右边项系数 目标函数系数目标函数系数变量数与约束数变量数与约束数 变量数变量数n 约束数约束数 n的对应关系的对应关系 约束数约束数m 变量数变量数m原问题变量类型与原问题变量类型与   0   对偶问题约束类型对偶问题约束类型 变量变量  0 约束约束  的对应关系的对应关系 无限制无限制 ＝＝原问题约束类型与原问题约束类型与     0 对偶问题变量类型对偶问题变量类型 约束约束  变量变量  0 的对应关系的对应关系 ＝＝ 无限制无限制例例1、写出下面问题的对偶规划、写出下面问题的对偶规划maxZ= 5X1 +6X2 3X1 -2X2 =74X1 +X2   9X1 , X2  0minW=7y1 +9y23y1+4y2  5 -2y1 +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或将原问题变形为或将原问题变形为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 120 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 y1 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/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)定理定理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) 的最优解的最优解证明：对任证明：对任X，有，有CX b y =CXX最优最优推论推论1、、(LP), (DP)都有可行解，则必都有最优解。

都有可行解，则必都有最优解定理定理4、、B为为(LP)的最优基，则的最优基，则 y= CB B-1 是是(DP)的最优解的最优解<称称B为对偶最优基，为对偶最优基， 为对偶最优解为对偶最优解> y推论：推论： 分别为分别为(LP), (DP)可行解，又是最可行解，又是最优解，则有优解，则有X y,X yC=b定理6 （互补松驰性）若X*、Y*分别是原问题和对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(其中XS，YS分别是原问题和对偶问题的松驰变量向量)证明：设原问题和对偶问题的标准型是 原问题 对偶问题定理5 （强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等 将原问题目标函数中的系数向量C用 代替后，得到 将对偶问题的目标函数中的系数向量，用 代替后，得到 若 ；则 故 是最优解。

又若 分别是原问题和对偶问题的最优解，则必有  一般而言，我们把某一可行点（如一般而言，我们把某一可行点（如X*和和Y*）处）处的严格不等式约束（包括对变量的非负约束）称为的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束所以有如松约束，而把严格等式约束称为紧约束所以有如下结论：下结论： 设一对对偶问题都有可行解，若原问题的某一设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束是其对偶问题最优解的紧约束例1－21 已知试通过求对偶问题的最优解来求解原问题的最优解解：对偶问题为用图解法可求得对偶问题的最优解：Y*=（1，3），W=11将代入对偶约束条件，（1），（2），（5）式为紧约束，（3），（4）为松约束令原问题的最优解为X* = （x1，x2，x3，x4，x5），则根据互补松弛条件，必有x3 = x4 =0又由于，原问题的约束必为等式，即化简为化简为 此方程组为无穷多解此方程组为无穷多解 令令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=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个单位时，个单位时，工厂可增加利润工厂可增加利润2/9个单位。

个单位•（（3）、影子价格的作用）、影子价格的作用•（1）指出企业挖潜革新的途径•影子价格>0，说明该资源已耗尽，成为短线资源•影子价格=0，说明该资源有剩余，成为长线资源•（2）对市场资源的最优配置起着推进作用•即在配置资源时，对于影子价格大的企业，资源优先供给•（3）可以预测产品的价格•产品的机会成本为CBB-1A-C，只有当产品价格定在机会成本之上，企业才有利可图•（4）可作为同类企业经济效益评估指标之一•对于资源影子价格越大的企业，资源的利用所带来的收益就越大，经济效益就越好通过以上讨论可知：通过以上讨论可知：① ① 某资源对偶解某资源对偶解>0>0，该资源有利可图，可增，该资源有利可图，可增加此种资源量；某资源对偶解为加此种资源量；某资源对偶解为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对偶单纯形法：找基对偶单纯形法：找基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 b<0令第令第 l 行的行的Xj l为换出变量为换出变量. .(3)、、确定换入变量确定换入变量① ① 若若Xi l行的行的alj 全全 0 ，，停停，原问题无可行解原问题无可行解② ② 若若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 0>0某某xj 从从0↗0↗ ，xil不能变不能变>0②②为保持为保持λj   0 ，，即对偶解可行性即对偶解可行性例例1 1：：Max Z =2X1 +X2X1+ X2 + X3 = = 5 2X2 + X3   5 4X2 +6X3   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 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 (-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 表示利润时，表示利润时， yi 不是真正的影子价格，只表示资源不是真正的影子价格，只表示资源bi 增加增加1 1单单位时，企业目标增加的净利润位时，企业目标增加的净利润情况情况② ② 模型中，目标函数系数模型中，目标函数系数Ci 表示成本时，表示成本时， yi 是真正的影子价格是真正的影子价格对偶单纯形的优点与用途： （1）初始解可以是非可行解，当检验数都是正数时，就可以进行基变换，这样避免了增加人工变量，使运算简便2）对变量较少时，而约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形求解，简化计算3）用于后面的灵敏度分析第六节第六节 灵敏度分析灵敏度分析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中的一个中的一个(几个几个)变动，对变动，对当前方案影响？当前方案影响？(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 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改为改为10，， σ 3 =2>0 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,-2C1+8, C1 -8)  0-2C1+8   0C1-8   04  C1  8即单位产品A的利润在[4,8]之间变化时,最优方案不变② ② C1改变改变 C1=10，， σ 5 =2>0 ,换基换基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 的的改变，并不影响检验数，它只对最优改变，并不影响检验数，它只对最优方案有影响方案有影响1)、、bj 改变，改变， B-1 b仍仍 0时，最优方案的生时，最优方案的生产种类不变，生产数量发生改变产种类不变，生产数量发生改变例中例中b1改变改变2 -1-1 1b12010  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 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 最优方案不变 结论：无利结论：无利（（1 1））单位单位D D的利润为多少时，投产产品的利润为多少时，投产产品D D有利有利？？σ 6 = C6 - CBB-1 P6 = C6 - 12 >0 得得 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(四四)、添加新约束的灵敏度分析、添加新约束的灵敏度分析例例 新增加电力约束：新增加电力约束：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 42 2＋＋8 8＝＝16 >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 X1 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? 还是还是>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 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 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’。