线性规划(运筹学-京航空航天大学,党耀国)(研究生))

1、运运 筹筹 学学 南京航空航天大学经济与管理学院南京航空航天大学经济与管理学院 党党 耀耀 国国 二二00五年九月五年九月 緒緒 论论 一一 运筹学发展简史运筹学发展简史 中国古代的“齐王赛马”就是对策论的一个典型实例。作为运筹学的早期工作其历史可追溯到1914年： 1914年英国人兰彻斯特(F.W.Lanchester)呈发表过关于人与火力的优势与胜利之间的理论文章，这就是军事运筹学中著名的“兰彻斯特战斗方程”。 排队论的先驱者丹麦工程师爱尔朗(A.K.Erlang)1917年在哥本哈根电话公司研究电话通信系统时，提出了排队论的一些著名公式。 20世纪30年代，荷兰人荷雷斯列文生(Horac

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

3、“操作研究”(Operational 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)生产计划：在总体计划方面主要是从总体确定生产、存储和劳动力的配合等计划以适应波动的需求计划,主要用线性规划和模拟的方法等。(3)库存管理:主要应用于多种物资库存的管理,以确定合理的库存量。(4)运输问题

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

8、知热敏电阻R依赖于温度t的函数关系题。这就是一个最小二乘问平方和误差”来度量。通常使用“最小一定正好通过测量点，关系式，但这条曲线不的一个函数关于以确定）一组数值，由上式可给定（？参数问题是如何确定（据通过实验，测得一组数为待定参数。其中213213213213211)(),(min , 2 , 1),)( 32niiiiixtxtRRxxxftRxxxxxxniRtxxxextR2、生成成本问题介绍Cobb-Douglas生成函数。0, 0. min ),( .210212102121212xxQxAxtsxrxCQxrxcrAxAxxxQQxx生产成本最小化。的条件下，使不低于某水平生产成

9、本问题是在产量生产成本，则，资本报酬率为已知工资率为为参数。，为生产技术水平，则为产出产量为劳动力，为资本的货物，设 3、资源分配问题、资源分配问题考虑将m种资源安排给n种活动，问应如何分配资源，才能使收益最大？这是线性规划模型。为则，对应的最优化模型的单位利润。表示活动其中的单位消耗量；相对于活动表示资源（种资源的拥有量；表示第其中的水平，已知的数据有表示选用活动设决策变量0. max ,),(a,)a,),(), 2 , 1(21ijnmij21XbAXtsXCZjcccccjiAibbbbbjnjxTjTniTmj在某些实际应用中，有时考虑的利润c1,c2,cn并不是固定的数值，而是随机

10、变量，假定C是一个均值为TncccC),(21线性规划模型的希望最大，则可考虑）如果希望（的随机变量。，方差为均值为就是一个题的目标函数的随机变量。则上述问协方差矩阵为ZAXXXCZVTT1二次规划问题。非线性规划问题，称为，它是一类比较特殊的函数，约束为线性约束这时目标函数就是二次模型的方差最小，则有如下如果希望0. min )2(0. max XbAXtsVXXZZXbAXtsXCZTT差最小，则如果希望期望最大，方)3(这仍是二次规划问题。则求一种自然的考虑就是要愿望水平或满意水平。常常被认为是这个值证期望达到至少某一值假定人们的兴趣在于保者综合加以考虑）如果对期望、方差两（题。这是一个

11、多目标规划问0. min ,40. min max XZXCbAXtsVXXZZXCZZXbAXtsVXXZXCZTTTTTxpxdZxpxdZyPZxypxdPZXCPynpdypdcZZXCPTTTTTTTTmin ), ,),相应的模型为：（是一维随机变量，则维固定向量，是设为确定性问题，为把不确定性问题转化。当然人们喜欢极大化的概率，是获得满意水平（另一种方法是令0.XbAXts这是线性分式规划。题。是常数，它就是运输问的，则如果仓库的位置是固定为变量的非线性规划。这时模型就是以的度量，可采用：关于则问题的模型为：的货物单位数量。场到市为仓库的距离，到市场为仓库的位置，为仓库设距离最小

12、。各仓库到市场的总加权试确定仓库的位置，使个仓库的容量为个仓库，第现规划对某种货物的需求量为）个市场的位置为（个市场，第设有选址问题dijwwyyxxbyaxddwmiqwmicwtsdwjiwjidiyxCimqbajnmnmmjijiijijijjnjijinjijminjijijijijiiijjj,;,;,)()(0, 2 , 1 , 2 , 1 . min ),(.,)4(1111221111参考书 1、卢向华，等著运筹学教程，高等教育出版社 2、钱颂迪，运筹学，清华大学出版社 3、林同曾，运筹学，机械工业出版社 4、胡运权， 运筹学教程，清华大学出版社 第 一章 线 性 规 划 第

13、 一 节 线性规划模型及其图解法 线性规划是运筹学的一个重要分枝。自1947年美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法单纯形法之后，线性规划在理论上趋于成熟，在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后，它的适用领域更广泛了。从解决技术问题中的最优化设计到工业、农业、商业、交通输业、军事、经济计划与管理、决策等各个领域均可发挥作用；从范围来看，小到一个小组的日常工作和计划安排，大至整个部门以致国民经济计划的最优方案的提出，都有用武之地。它具有适应性强、应用广泛、计算技术比较简单的特点，是现代管理科学的重要基

14、础和手段之一。一、线性规划模型线性规划：就是一个线性函数在线性等式或不等式约束条件下的极值问题。线性规划研究的问题主要有两类： 1、任务确定后，如何统筹安排，尽量做到用尽量少的人力和物力资源来完成任务； 2、有一定量的人力、物力资源，如何安排使用他们，使完成的任务（创造的利润）最多。 在生产管理和经济活动中经常提出这样一类问题， 即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。例例1：某工厂在计划期内安排生产、两种产品，已知生产单位产品所需的设备台时、A、B两种原材料的消耗及两种产品每件可获利润见如下表所示：问如何安排计划使该工厂获利最多？ I II 资源总量 设 备A

15、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 约束条件0,12416482122221212121xxxxxxxx例例2 某汽车厂生产大轿车和载重汽车，所需资源、某汽车厂生产大轿车和载重汽车，所需资源、资源可用量和产品价格如下表所示资源可用量和产品价格如下表所示: 大轿车大轿车 载重汽车载重汽车 可用量可用量钢材（吨）钢材（吨） 2

16、2 1600工时工时(小时小时) 5 2.5 2500大轿车座椅大轿车座椅 400（辆）（辆）获利获利(千元千元/辆辆) 4 3问应如何组织生产才能使工厂活力最大？问应如何组织生产才能使工厂活力最大？ 例2的数学模型2134maxxxz16002221 xx25005 . 2521xx1x02xs.t.,4001x例3 下料问题 某工厂要做100套钢架，每套有长2.9米、2.1米和1.5米的圆钢组成，已知原料长7.4米，问应如何下料使需用的原材料最省。 解：如果从每根7.4米长的原料上各截一根2.9米、2.1米和1.5米长的圆钢，则还余0.9米，用100根原料，浪费预料共90米。现采用套裁的办

17、法，设计五种方案，如表1.2所示。表 圆钢套裁方案 方案长度一二三四五2.92.11.513210221213合计（米）料头（米）7.407.30.17.20.27.10.36.60.8例3 数学模型 设个方案各下料 根，则有5 , 4 , 3 , 2 , 1, ixi0,100323100221002. .8 . 03 . 02 . 01 . 00 . 0min54321532154342154321xxxxxxxxxxxxxxxtsxxxxxz（1-5）以上三个例子,从数学上来讲,它们的共同特征是:(1)每个问题都用一组决策变量(x1 , x2 , , xn)表示某一方案 ,这组未知数的值

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

19、中,方程(1.1)称为目标函数;(1.2)称为约束条件。二、图解法二、图解法对于简单的线性规划问题(只有两个决策变量的线性规划问题),我们通过图解法可以对它进行求解。我们可以由例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+321=164x2=12X1+2x2=82x1+2x2=12ABCDX2解：对于上述具有两个

20、变量的线性规划问题，下图的阴影部分描述了满足约束条件的区域，为OABCD;红虚线为目标函数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点就是最优点。最优值等于26000Z= 40 X1 + 80X2 =0 X1 +

21、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 0X1 =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 ,

22、则可行解所在的范围虽然无界,但有最优解 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

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

24、论，我们规定线性规划问题的标准型为： 0,)4 .1 (21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcZMax 这里我们假设 bi 0 ( i = 1,2,m),否则两端同时乘以“-1”。用矩阵向量描述就是：0)5.1(XbAXXCZMaxT 其中：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

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

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

27、由于xj可能大于也可能小于xj，故 xj 可以为正或为负。上述的标准型具有如下特点： （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+0 x3+0 x4+0 x5+0 x6 2x1

28、+2x2+x3 =12 x1+2x2+ x4 =18 4x2+ x5 =12 4x1+ x6=16 x1, x2,x3,x4,x5,x60例例4: 试将如下线性规划问题化成标准型无限制321321321321321,0,)3(523)2(2)1(732xxxxxxxxxxxxxxxZMin解：解：令 x3 = x4 - x5 , x4 , x5 0 , (1)式左端加上非负松弛变量 x6 , (2)式左端减去非负剩余变量 x7 , 则可将上述线性规划问题化成如下的标准型:0,5223270033272154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxZMa

29、x)8 . 1 (), 2 , 1(0)7 . 1 (), 2 , 1(1njxnjbxajnjjjij1. 可行解可行解: 满足约束条件(1.7),(1.8)的解 X = ( x1, x2, , xn)T 称为线性规划问题的可行解;所有可行解的集合称为可行解集或可行域。2. 最优解最优解: 满足约束条件及目标函数(1.6)的可行解称为线性规划问题的最优解。四、线性规划问题的解的概念四、线性规划问题的解的概念 在讨论线性规划问题的求解之前,先要了解线性规划问题的解的概念。由前面讨论可知线性规划问题的标准型为 (1.6)、(1.7)、(1.8)，即如下式子：)6.1(1njjjxcZMax3.

30、基基: 假设 A 是约束方程组的系数矩阵,其秩数为 m ,B是矩阵 A 中由 m 列构成的非奇异子矩阵(B的行列式的值不为0），则称 B 是 线性规划问题的一个基。这就是说,矩阵 B 是由 m 个线性无关的列向量组成,不失一般性,可假设:),(212111211mmmmmmPPPaaaaaaB称 Pj ( j = 1,2,m )为基向量,与基向量 Pj 相对应的变量xj ( j = 1,2,m )为基变量,否则称为非基变量。 为了进一步讨论线性规划问题的解,下面研究约束方程组(1.7)的求解问题。假设该方程组系数矩阵 A 的秩为 m ,因 m n,所以它有无穷多个解。假设前 m 个变量的系数列

31、向量是线性无关的，这时(1.7)式可改写为：)9 . 1 (:111111111111nmjjjjmjjnmnnmmmmmmmmmxPbxPxaaxaabxaaxaa或方程组(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

32、. 基本可行解基本可行解 : 满足非负条件(1.8)的基本解称为基本可行解.由此可见,基本可行解的非0分量的数目不大于 m ,并且都是非负的。5. 可行基可行基: 对应于基本可行解的基称为可行基.由此可见,约束方程组(1.7)基本解的数目至多是 Cnm 个.一般地讲,基本可行解的数目要小于基本解的数目,至多相等. 以上提到的几种解的概念,可用如下图来表示:基解可行解基本可行解 第二节第二节 线性规划问题的几何意义线性规划问题的几何意义 在上一节的图解法中,我们已经直观地看到了可行和最优解的几何意义,这一节从理论上进一步讨论。一、基本概念：一、基本概念：1.凸集: 假设 K 是 n 维欧氏空间的

33、一个点集,若对于K 中的任意两点 X1、X2 ,其连线上的所有点 X1+(1-)X2 ( 0 1)都在集合 K 中,即: X1+(1-)X2 K ( 0 1)则称 K 为凸集。从直观上讲，凸集无凹入部分，其内部没有洞。 实心圆、实心球、实心立方体等都是凸集，圆周不是凸集。图（a)、(b)、为凸集，而图（c)、(d)不是凸集。容易验证以下结论是正确的：交集仍是凸集。定理：任意多个凸集的都是凸集。半空间半空间线。为一维向量时，就是直当是凸集。（超平面）则且）（）设（都是凸集。和全集空集bxRxHbxRxHbxRxHRbRRTnTnTnnn, 0,2) 1 (212. 凸组合: 设 X1、 X2、

34、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：若线性

35、规划问题存在可行域，则其可行域： 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. 最优解判别定理最优解判

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

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

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

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

40、，lIN = j ,确定 xj 为换入变量(即为新基的基变量),再根据:miyybybijijikjk1, 0,min*确定 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,x60 解： （1）由标准型得到：cj2 3 0 0 0 0XBbx1 x2 x3 x4 x5 x6 i2 2 1

41、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）max1, 2=3= 2,所以x2为换入变量. (3)因为1=2, 2=3都大于0，且p1,p2的坐标有正分量存在，33 , 4 , 6min0|minlklikikiiabaab因为3与x6那一行相对应，所以x6为换出变量；cj2 3 0 0 0 0XBbx1 x2 x3 x4 x5 x6 i2 0 1 0 0 -1/21 0 0 1 0 -1/24 0 0 0 1 0 0 1 0 0 0 1/4x3x4x5x262163324-Z-9 2

42、 0 0 0 0 -3/4 故x2对应列与x6对应行的相交处的4为主元素；（4）以“4”为主元素进行旋转计算，进行行初等变换，得下表：cj2 3 0 0 0 0XBbx1 x2 x3 x4 x5 x6 i0 0 1 -2 0 1/21 0 0 1 0 -1/20 0 0 -4 1 2 0 1 0 0 0 1/4x3x1x5x222834-412-Z-13 0 0 0 -2 0 1/4 这时出现了退化问题。即有两个或更多的相同时，在相同 对应的变量中选择下标最大的那个基变量为换出变量；同时如果出现有两个或更多的检验数相同时，在相同 对应的变量中选择下标最小的那个基变量为进入变量，这样会避免出现“

43、死循环”的现象。cj2 3 0 0 0 0XBbx1 x2 x3 x4 x5 x6 i0 0 1 -1 -1/4 01 0 0 1 1/4 00 0 0 -2 1/2 1 0 1 0 -1/8 0 x3x1x6x20442-Z-14 0 0 0 -3/2 -1/8 0 这时，检验数全部小于等于0，即目标函数已不可能再增大，于是得到最优解： X=(4,2,0,0,0,4)T目标函数的最大值为： Z=14 第四节第四节 单纯形算法的进一步讨论单纯形算法的进一步讨论一、初始基本可行解一、初始基本可行解 的确定的确定 利用单纯形算法的一个根本前提是要有一个初始的基本可行解 .这对于一些简单问题, 利用

44、观察或其它手段是容易得到的;但对于较复杂的问题, 则利用这种方法几乎是不可行的. 这就引起了人们对求初始基本可行解 的思考.以下我们分几种情形加以讨论。1. 对于 AX = b , 人们一下就可以从其中求得一个单位矩阵.这时取初始基 B 就是单位矩阵,对应的基变量为 XB, 非基变量为 XN 。这时)0,(0bbXXNB这里假设当然, 然后按单纯形算法计算步骤便可得到。这种情况包含了 AX b 的情形。2. 人工变量法人工变量法(大大 M 法法) 设有一个线性规划的约束条件是等式约束，这时分别给每一个约束条件加入人工变量 xn+1, , xn+m , 得:0,)35. 1 (111122212

45、1111111mnnnmmnnmnmnnnnnnxxxxbxxaxabxxaxabxxaxa由此得到一个 m 阶单位矩阵. 以 xn+1, , xn+m 为基变量, 令非基变量 x1, , xn 为 0, 便可得到一个初始基本可行解 X(0) ; X(0) = ( 0, , 0, b1 , , bm )T 。 因为人工变量是后加入到原约束方程组中的虚拟变量, 我们要求将它们从基变量中逐渐替换掉.若经过基的变换, 基变量中不再包含有人工变量, 这就表示原问题有解; 若经过基变换,最后在基中至少还有一个人工变量, 这就意味着原问题无可行解. 具体处理方法如下: 对于加入人工变量的线性规划问题的目标

46、函数如何处理?我们希望人工变量对目标函数取值不受影响.因此只有在迭代过程中, 把人工变量从基变量中换出,让它成为非基变量.为此, 就必须假定人工变量在目标函数中的价值系数为(-M)(对于极大化目标), M为充分大的正数.这样, 对于要求实现目标函数最大化的问题来讲,只要在基变量中还存在人工变量, 目标函数就不可能实现最大化. 这就是大M法。以下举例加以说明。例例6. 试用大M法求解如下线性规划问题的最优解。0,12324112332131321321321xxxxxxxxxxxxxxZMin解解:在上述问题中加入松弛变量,剩余变量和人工变量得:0,12324112371731653214321

47、76321xxxxxxxxxxxxxxMxMxxxxZMax这里M是一个充分大的正数, 取基变量为 x4 , x6 , x7 , 可得如下的表18。利用表18得初始单纯形表，单纯形算法得表19 表111。表表18cj3-1-100-M -MCBXBb*x1x2x3x4x5x6x70 x4111-211000-Mx63-4120-110-Mx71-2010001-Z03-1-100-M -Mcj3-1-100-M -MCBXBb*x1x2x3x4x5x6x70 x4111-21100011-Mx63-4120-1101.5-Mx71-20100011-Z4M 3-6M M-13M-10-M00初

48、始单纯形表表表19cj3-1-100-M-MCBXBb*x1x2x3x4x5x6x70 x4103-20100-1-Mx610100-11-21-1x31-2010001- ZM+11M-100-M01-3Mcj3-1-100-M-MCBXBb*x1x2x3x4x5x6x70 x4123001-22-54-1x210100-11-2-1x31-2010001- Z21000-11-M-1-M 表表110cj3-1-100-M-MCBXBb*x1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3- Z-200

49、0-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. 两阶段法两阶段法: 这种方法是在约束条件中加入人工变量,将线性规划问题分为两阶段进行求解. 第一阶段是先求出基本可行解 (或判断出原线性规划问题无解), 第二阶段利用已求出的初始基本可行解 来求最优解。具体由如下定理5给出。定理定理5 设原线性规划问题记成(LP), 由它而引入的新的线性规划问题记成(LP)*。分别表示如下：个mTTmnnTTexxXXXbIXAXX

50、bAXXeWMinLPXCZMaxLP)1 , 1 (,),(0,00:)*(:)(1*1) 若(LP)*具有最优基本可行解 ,0,*XXX且则(LP)是可行的,而 .)(的一个基可行解即为 LPX2) 若(LP)*的最优基本可行解 ,0,*XXX使得则(LP)必不可行。 定理5的具体应用过程是: (LP)*判断原线性规划问题是否存在基本可行解 , 利用单纯形算法, 若得到 W = 0 , 即所有人工变量为非基变量, 这表示原问题已得到了一个基本可行解 .于是只需要将第一阶段最终计算表中的目标函数行的数字换成原问题的目标函数的数字, 就得到了求解原问题的初始计算表, 再进行第二阶段的求解。若第

51、一阶段的最终计算表出现 W 0 , 这就表明原问题无可行解，应停止计算。0,12324112332131321321321xxxxxxxxxxxxxxZMax解：解：先在以上问题的约束条件中加入松弛变量、剩余变量、人工变量，给出第一阶段的线性规划问题：0,12324112717316532143217676xxxxxxxxxxxxxxxxWMaxxxZMin各阶段的计算方法及步骤与前述单纯形法完全相同，下面用例子说明该方法的应用。 例例7：试用两阶段法求解如下线性规划问题以 x4、x6、x7 为基变量得如下初始计算表cj00000-1-1CBXBb*x1x2x3x4x5x6x70 x4111-

52、211000-1x63-4120-110-1x71-2010001-W000000-1-1cj00000-1-1CBXBb*x1x2x3x4x5x6x70 x4111-21100011-1x63-4120-1101.5-1x71-20100011-W4-6130-100初始单纯形表112表表113cj00000-1-1CBXBb*x1x2x3x4x5x6x70 x4103-20100-1-1x610100-11-21-1x31-2010001-W10100-10-3表表114cj00000-1-1CBXBb*x1x2x3x4x5x6x70 x4123001-22-50 x210100-11-2

53、0 x31-2010001-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*x1x2x3x4x50 x4123001-212/3=4-1x210

54、100-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 2 3销售收入销售收入产品产品设备设备设设X1 ， X2

55、 为产品为产品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 +

56、16y3+12y4y1 , y2 , y3 , y4 “影子价格影子价格”定义：定义：对偶问题对偶问题 minW=yb yA Cy 0minW=bTyATy CTy 0maxZ=CX AX bX 0原问题原问题对偶关系对应表对偶关系对应表 原问题原问题 对偶问题对偶问题目标函数类型目标函数类型 max min目标函数系数目标函数系数 目标函数系数目标函数系数 右边项系数右边项系数与右边项的对应关系与右边项的对应关系 右边项系数右边项系数 目标函数系数目标函数系数变量数与约束数变量数与约束数 变量数变量数n 约束数约束数 n的对应关系的对应关系 约束数约束数m 变量数变量数m原问题变量类型与原问

57、题变量类型与 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

58、+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产量为产量为X

59、1，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 184 0

60、0 -2/9 -13/93y1+3y2 5 y1 +4y2 6minW=48y1+120y23y1+3y2 -y3+y5 =5 y1 +4y2 -y4+y6= 6minW=48y1+120y2 +My5 +My6y=(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