线性规划研究生.ppt

《线性规划研究生.ppt》由会员分享，可在线阅读，更多相关《线性规划研究生.ppt（155页珍藏版）》请在三一办公上搜索。

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

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

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

4、国际水平。我国第一个运筹学小组于1956年在中国科学院力学研究所成立，1960年在山东济南召开全国应用运筹学的经验交流和推广会议，1962年在北京召开了全国运筹学专业学术会议，1980年4月成立中国运筹学学会。上世纪50年代中期，以华罗庚为首的一大批科学家加入到运筹学的研究中，首先在一些企业、事业单位积极推广优选法、统筹法等运筹学方法，取得显著成果；并成立了优选法、统筹法与经济数学研究会。学会主要研究运筹学，但没有称为运筹学。如今，运筹学已经成为所有大学的经济与管理学院、工学院与计算机专业、应用数学专业的基础课程。,二、运筹学的工作步骤 运筹学在解决大量实际问题的过程中形成了自己的工作步骤：1

5、.提出和形成问题：即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数及有关资料。2.建立模型：即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来。3.求解：用各种手段(主要是数学方法，也可用其它方法)将模型求解。解可以是最优解、次优解、满意解.复杂模型的求解需用计算机,解的精度要求由决策者提出,4.解的检验：首先检验求解步骤和程序有无错误，然后检查解是否反映现实问题。5.解的控制：通过控制解的变化过程决定对解是否要作一定的修改。6.解的实施：是指将解用到实际中去，必须考虑到实际的问题，如向实际部门讲清楚解的用法，在实施中可能产生的问题等。以上过程应反复进行。,三、运筹学

6、的应用与展望 在运筹学的发展简史中，已提到了运筹学在早期的应用，主要在军事领域。二次大战后运筹学的应用转向民用，主要应用于：市场销售：在广告预算和媒介的选择、竞争性定价新产品开发、销售计划的制定等方面。(2)生产计划：在总体计划方面主要是从总体确定生产、存储和劳动力的配合等计划以适应波动的需求计划,主要用线性规划和模拟的方法等。(3)库存管理:主要应用于多种物资库存的管理,以确定合理的库存量。(4)运输问题：各种运输的调度与计划安排。(5)财政和会计：这里主要涉及预算、贷款、成本分析、定价、投资、证券管理、现金管理等。用得较多的方法是：统计分析、数学规划、决策分析。,(6)人事管理：一是人员的

7、获得和需求估计；二是人才的开发，即进行教育和培训；三是人员的分配；四是各类人员的合理利用问题；五是人才的评价，其中有如何测定一个人对组织、社会的贡献;六是工资和津贴的确定等。(7)设备维修、更新和可靠性、项目选择和评价。(8)工程的优化设计：这在建筑、电子、光学、机械和化工等领域都有应用。(9)计算机和信息系统：(10)城市管理：包含了各种紧急服务系统的设计和运用,四、最优化问题举例1、多参数的曲线拟合问题 已知热敏电阻R依赖于温度t的函数关系,2、生成成本问题介绍Cobb-Douglas生产函数。,3、资源分配问题考虑将m种资源安排给n种活动，问应如何分配资源，才能使收益最大？,在某些实际应

8、用中，有时考虑的利润c1,c2,cn并不是固定的数值，而是随机变量，假定C是一个均值为,这是线性分式规划。,最优化的分类图,离散规划,整数规划,参考书 1、卢向华，等著运筹学教程，高等教育出版社 2、钱颂迪，运筹学，清华大学出版社 3、林同曾，运筹学，机械工业出版社 4、胡运权，运筹学教程，清华大学出版社,第 一章 线 性 规 划 第 一 节 线性规划模型及其图解法 线性规划是运筹学的一个重要分枝。自1947年美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法单纯形法之后，线性规划在理论上趋于成熟，在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变

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

10、创造的利润）最多。在生产管理和经济活动中经常提出这样一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。,例1：某工厂在计划期内安排生产、两种产品，已知生产单位产品所需的设备台时、A、B两种原材料的消耗及两种产品每件可获利润见如下表所示：问如何安排计划使该工厂获利最多？,解：假设 x1、x2分别表示在计划期内生产产品I、II的数量，则该计划问题可用如下数学模型表示为：目标函数 Max Z=2x1+3x2 约束条件,例2 某汽车厂生产大轿车和载重汽车，所需资源、资源可用量和产品价格如下表所示:大轿车 载重汽车 可用量钢材（吨）2 2 1600工时(小时)5 2.5 2

11、500大轿车座椅 400（辆）获利(千元/辆)4 3问应如何组织生产才能使工厂获利最大？,例2的数学模型,例3 下料问题,某工厂要做100套钢架，每套有长2.9米、2.1米和1.5米的圆钢组成，已知原料长7.4米，问应如何下料使需用的原材料最省。解：如果从每根7.4米长的原料上各截一根2.9米、2.1米和1.5米长的圆钢，则还余0.9米，用100根原料，浪费预料共90米。现采用套裁的办法，设计五种方案，如表1.2所示。,表 圆钢套裁方案,例3 数学模型,设个方案各下料 根，则有,（1-5）,以上三个例子,从数学上来讲,它们的共同特征是:每个问题都用一组决策变量(x1,x2,xn)表示某一方案,

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

13、用图解法求解线性规划问题。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=14,解：对于上述具有两个变量的线性规划问题，下图的阴影部分描述了满足约束条件的区域，为OABCD;红虚线为目标函数Z=2x1+3x2的等值线。沿箭头方向移动目标函数的等值线，平移等值线直至与可行域OABCD相切或融合为一条直线，此时就得到最优解,为C 点，其坐标可通过解方程组得到：,例2：用图解法求解线性规划问题。MAX

14、 Z=4x1+3x2 s.t.2x1+2x2 1600 5 x1+2.5x2 2500 x1 400 x1,x20,由约束条件得到可行域OABCD。由等值线Z=4x1+3x2沿箭头方向向上平移与可行域交于B点，则B点就是最优点。最优值等于2600,0,求解最优解：BC线段B点 C点X(1)=(6,12)X(2)=(15,7.5)X=X(1)+(1-)X(2)(0 1),无界无有限最优解若目标函数由 Max Z=2x1+4x2 改为 Min Z=2 x1+4 x2,则可行解所在的范围虽然无界,但有最优解 x1=4，x2=0,即(4,0)点.,无解无可行解,0,通过图解法可以看出：（1）线性规划的

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

16、实现最大化也有实现最小化的;约束条件可以是“”形式、“”形式不等式,有的是等式。决策变量有时有非负限制有时没有。这种多样性给讨论问题代来了不便。为了便于今后讨论，我们规定线性规划问题的标准型为：,这里我们假设 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 为约束方程组的系数矩阵(mn阶),一般情况下 m n,m,n 为正整数,分别表示约束条件的个数和决策变量的个

17、数,C 为价值向量,X 为决策向量,通常aij,bi,cj(i=1,2,m,j=1,2,n)为已知常数。实际上，具体问题的线性规划数学模型是各式各样的,需要把它们化成标准型,并借助于标准型的求解方法进行求解.,以下就具体讨论如何把一般的线性规划模型化成标准型。若要求目标函数实现最小化时.即此时的目标函数是:Min Z=CTX,这时只需要将目标函数的最小值变换为求目标函数的最大值,即 Min Z=Max(-Z)。令Z=-Z，于是就得到：Max Z=-CTX。2.若约束方程组为不等式。这时有两种情况:一是约束条件为“”形式的不等式,则在“”号的左边加入非负的松弛变量;把原“”形的不等式变为等式;另

18、一种是约束条件为“”形式的不等式,则可在“”号的左端减去一个非负的剩余变量。相应的松弛变量或剩余变量在目标函数中的价值系数取值为0。,3.若存在无非负要求的变量.即有某一个变量 xj 取正值或负值都可以.这时为了满足标准型对变量的非负要求,可令 xj=xj-xj,其中:xj、xj 0，由于xj可能大于也可能小于xj，故 xj 可以为正或为负。上述的标准型具有如下特点：（1）目标函数求最大值；（2）所求的变量都要求是非负的；（3）所有的约束条件都是等式；（4）常数项非负 综合以上的讨论可以说明任何形式的线性规划问题都可以通过上述手续把非标准型式的线性规划问题化成标准型。现举例如下：,例：将例1的

19、数学模型化为标准型。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+2x2+x3=12 x1+2x2+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,则可将上述线性规划问题化成如下的标准型:,可行解

20、:满足约束条件(1.7),(1.8)的解 X=(x1,x2,xn)T 称为线性规划问题的可行解;所有可行解的集合称为可行解集或可行域。最优解:满足约束条件及目标函数(1.6)的可行解称为线性规划问题的最优解。,四、线性规划问题的解的概念 在讨论线性规划问题的求解之前,先要了解线性规划问题的解的概念。由前面讨论可知线性规划问题的标准型为(1.6)、(1.7)、(1.8)，即如下式子：,基:假设 A 是约束方程组的系数矩阵,其秩数为 m,B是矩阵 A 中由 m 列构成的非奇异子矩阵(B的行列式的值不为0），则称 B 是 线性规划问题的一个基。这就是说,矩阵 B 是由 m 个线性无关的列向量组成,不

21、失一般性,可假设:,称 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=(

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

23、,若对于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的

24、连线上，而且反之亦然。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,

25、x2,xm,0,0)T 为相应的基本可行解,当 k m 时，则一定可以从其余的列向量中取出 m k 个与P1,P2,Pk 构成最大的线性无关向量组,其对应的解恰为 X,所以根据定义是基本可行解(此时为退化的基本可行解)。,定理2:线性规划问题的基本可行解对应于可行域的顶点.引理2：若 K 是有界凸集，则任何一点 Z K 可表示为K 的顶点的凸组合。定理3:若可行域有界,则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优解。定理4(线性规划问题的基本定理)若线性规划问题存在可行解,则一定存在基本可行解;(2)若线性规划问题存在最优解,则一定存在最优的基本可行解。,根据以上讨论得到如下的结

26、论：（1）线性规划问题的所有可行解的集合一般是凸集，它可以是有界的，也可以是无界的区域；仅有有限个顶点。(2)线性规划问题的每一个基本可行解对应于可行域的一个顶点。若线性规划问题有最优解，必定可在某顶点处取到。(3)如果一个线性规划问题存在多个最优解，那么至少有两个相邻的顶点处是线性规划的可行解。（4）如果有一个顶点处可行解的目标值比其它相邻顶点可行解的目标值优的话，那么它就比其它所有顶点的可行解的目标值优。或者说，它就是最优解。,虽然可行域的顶点个数是有限的(它们不超过 Cnm 个)，采用“枚举法”找出所有基本可行解，然后一一比较它们的目标函数值的大小，最终可以找到最优解。但当 m、n 的数

27、目相当大时，这种办法实际上是行不通的。因此，我们还要继续讨论一种方法，通过逐步迭代保证能逐步改进并最终求出最优解。,第 三 节 单纯形算法 单纯形算法的基本思路是:根据问题的标准型,从可 行域中某个基本可行解(顶点)开始,转换到另一个基本可行解(顶点),并使得每次的转换,目标函数值均有所改善,最终达到最大值时就得到最优解。对于标准线性规划问题(简写为 LP):,这里 A=(aij)mn,秩A=m。首先假定已求得(LP)的一个基本可行解 X(0),为叙述方便,不失一般性,假设:,X(0)=(x1(0),x2(0),xm(0),0,0)T(XB(0),XN(0)T,其对应的基为:B=(P1,Pm)

28、,其中 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

29、=CBTB-1b,令 j=cj CBTB-1Pj,则显然当 jIB=1,m(IB 称为基变量指标集)时,j=0;当 jIN=m+1,n(IN 称为非基变量指标集)时,j 则不一定等于 0。j 称为检验数，又令 yj=B-1Pj(y1j,ymj)T,jIN,则可得出如下的初始单纯形表13。,表13 初始单纯形表,由于 xj 0,j 0,jIN,所以由(1.23)式可知:CTX CTX(0)命题得证。2.无有限最优解判别定理:若 X(0)=(XB(0),XN(0)T 为一基本可行解,且有一个 j0IN,j0 0,而 yj0 0,则(LP)无有限最优解(也称为无界解)。,一、最优性检验与解的判别最优

30、解判别定理:若 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为换入变量(就是下一个基的基变量).因为基变量个数总是为 m,所以换入一个之后还必须换出一个。下面我们来考虑如何选择换出变量。

31、若初始基本可行解X(0)不是最优解，那么就还要找一个新的基本可行解。其作法如下：从原可行基中换出一个列向量，再投入一个新的列向量，（要保证线性无关），从而得到一个新的可行基，这就是基变换。,要做基变换。首先确定换入变量（已讲过），即选择最大的检验数j所对应的非基变量作为换入变量xj(进基变量)。下面再确定换出变量。确定换出变量的原则是保持解的可行性。这就说，要使原基本可行解的某一个正分量xj变为0，同时保持其余分量均非负。具体实现是按“最小比例原则”进行，也称原则。若则选基变量Xl为换出变量。4.旋转运算（迭代）（枢运算）在确定了换入变量Xk与换出变量Xl之后，要把xk和xl的位置对换，就是说

32、，要把xk 所对应的列向量pk变成单位向量。这只对系数矩阵的增广矩阵进行变换即可，称ylk为旋转元。,以表13中的元素 ykl(称为主元素或旋转元素)进行基变换:将第 k 行每个元素除以 ykl,将第 k 行每个元素乘以 yij/ykj 加到第 i 行(i=1,2,m,i k,j=1,2,k),将第 k 行每个元素乘以 j/ykj 加到检验数行,对应的新的目标函数值即为：,经过基变换之后，针对于新基 B1 的基本可行解 为：,综合以上的讨论,单纯形算法的计算步骤可归结如下：第一步：找出初始可行基，确定初始基本可行解，建立初始单纯形表；第二步：检查对应于非基变量的检验数 l，lIN，若所有 l

33、0，lIN，则已得到最优解，停止计算，否则转入下一步；第三步：在所有l 0，lIN 中，若有一个j 对应的系数列向量 yj 0，则此问题没有有限最优解，停止计算，否则转入下一步；第四步：根据 max l l 0，lIN=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,x

34、2,x3,x4,x5,x60 解：（1）由标准型得到：,（2）max1,2=3=2,所以x2为换入变量.(3)因为1=2,2=3都大于0，且p1,p2的坐标有正分量存在，,因为3与x6那一行相对应，所以x6为换出变量；,故x2对应列与x6对应行的相交处的4为主元素；（4）以“4”为主元素进行旋转计算，进行行初等变换，得下表：,这时出现了退化问题。即有两个或更多的相同时，在相同 对应的变量中选择下标最大的那个基变量为换出变量；同时如果出现有两个或更多的检验数相同时，在相同 对应的变量中选择下标最小的那个基变量为进入变量，这样会避免出现“死循环”的现象。,这时，检验数全部小于等于0，即目标函数已不

35、可能再增大，于是得到最优解：X=(4,2,0,0,0,4)T目标函数的最大值为：Z=14,第四节 单纯形算法的进一步讨论一、初始基本可行解 的确定 利用单纯形算法的一个根本前提是要有一个初始的基本可行解.这对于一些简单问题,利用观察或其它手段是容易得到的;但对于较复杂的问题,则利用这种方法几乎是不可行的.这就引起了人们对求初始基本可行解 的思考.以下我们分几种情形加以讨论。对于 AX=b,人们一下就可以从其中求得一个单位矩阵.这时取初始基 B 就是单位矩阵,对应的基变量为 XB,非基变量为 XN。这时,然后按单纯形算法计算步骤便可得到。这种情况包含了 AX b 的情形。人工变量法(大 M 法)

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

37、因此,只有在迭代过程中,把人工变量从基变量中换出,让它成为非基变量.为此,就必须假定人工变量在目标函数中的价值系数为(-M)(对于极大化目标),M为充分大的正数.这样,对于要求实现目标函数最大化的问题来讲,只要在基变量中还存在人工变量,目标函数就不可能实现最大化.这就是大M法。以下举例加以说明。例6.试用大M法求解如下线性规划问题的最优解。,解:在上述问题中加入松弛变量,剩余变量和人工变量得:,这里M是一个充分大的正数,取基变量为 x4,x6,x7,可得如下的表18。利用表18得初始单纯形表，单纯形算法得表19 表111。,表18,初始单纯形表,表19,表110,表111,在表111中，所有的

38、 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)*判断原线性规划问题

39、是否存在基本可行解,利用单纯形算法,若得到 W=0,即所有人工变量为非基变量,这表示原问题已得到了一个基本可行解.于是只需要将第一阶段最终计算表中的目标函数行的数字换成原问题的目标函数的数字,就得到了求解原问题的初始计算表,再进行第二阶段的求解。若第一阶段的最终计算表出现 W 0,这就表明原问题无可行解，应停止计算。,解：先在以上问题的约束条件中加入松弛变量、剩余变量、人工变量，给出第一阶段的线性规划问题：,各阶段的计算方法及步骤与前述单纯形法完全相同，下面用例子说明该方法的应用。例7：试用两阶段法求解如下线性规划问题,以 x4、x6、x7 为基变量得如下初始计算表,初始单纯形表112,表11

40、3,表114,这里 x6、x7 是人工变量。第一阶段我们已求得 W=0，最优解 x5=0，x6=0，x7=0。因人工变量 x6=x7=0,所以(0,1,1,12,0)T 是原问题的基本可行解。于是可以开始第二阶段的计算。将第一阶段的最终计算表114中的人工变量列取消,并将目标函数系数换成原问题的目标函数系数,重新计算检验数行,可得如下第二阶段的初始单纯形表115；应用单纯形算法求解得最终表116。,表115,表116,表116中所有检验数 j 0，所以 x1=4，x2=1,x3=9 是原线性规划问题的最优解。目标函数值：Z*=2。,第五节 LP的对偶理论,1.5.1 对偶问题,设X1，X2 为

41、产品1，2的产量,设 y1,y2,y3,y4分别为出租每台设备台时的租金和出让单位原材料A,B的附加额。,定义：,对偶关系对应表,例1、写出下面问题的对偶规划,解：对偶问题,例2、写对偶规划,minZ=4X1+2X2-3X3,-X1+2X2 62X1+3X3 9 X1+5X2-2X3=4X2,X3 0,maxW=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+

42、2y2+y3=4-2y1+5y3 2 3y2-2y3-3y1,y2 0,y3自由,对偶规划,产品A，B产量为X1，X2，Z为利润,例1、,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/9 X2 24 0 1-1/3 1/3 184 0 0-2/9-13/9,y=(2/9,13/9),Z=184,观察结论:,一对对偶问题都有最优解，且目标函数值相等

43、。,最优表中有两个问题的最优解。,1.5.2 对偶问题解的性质,定理1、(对称性）对偶问题的对偶是原问题。定理2、(弱对偶定理),推论2、(LP)有可行解,但无有限最优解，则(DP)无可行解。,推论1、(LP),(DP)都有可行解，则必都有最优解。,定理6（互补松驰性）若X*、Y*分别是原问题和对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(其中XS，YS分别是原问题和对偶问题的松驰变量向量)。证明：设原问题和对偶问题的标准型是 原问题 对偶问题,定理5（强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。,将原问题目标函数中的

44、系数向量C用 代替后，得到 将对偶问题的目标函数中的系数向量，用 代替后，得到 若；则 故 是最优解。又若 分别是原问题和对偶问题的最优解，则必有,一般而言，我们把某一可行点（如X*和Y*）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下结论：设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。,例121 已知试通过求对偶问题的最优解来求解原问题的最优解。,解：对偶问题为,用图解法可求得对偶问题的最优解：Y*=（1，3），W=11。将代入对偶约束条件，（1），（2），（5）式为紧约束，（3）

45、，（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中y1=2/9,当机器台时数增加1个单位时，工厂可增加利润2/9个单位。,（3）、影子价格的作用（1）指出企业挖潜革新的途径影子价格0，说明该资源已耗尽，成

46、为短线资源。影子价格=0，说明该资源有剩余，成为长线资源。（2）对市场资源的最优配置起着推进作用即在配置资源时，对于影子价格大的企业，资源优先供给（3）可以预测产品的价格产品的机会成本为CBB-1A-C，只有当产品价格定在机会成本之上，企业才有利可图。（4）可作为同类企业经济效益评估指标之一。对于资源影子价格越大的企业，资源的利用所带来的收益就越大，经济效益就越好。,通过以上讨论可知：,某资源对偶解0，该资源有利可图，可增加此种资源量；某资源对偶解为0，则不增加此种资源量。,直接用影子价格与市场价格相比较，进行决策，是否买入该资源。,1.5.4 对偶单纯形法,思路：(max型),单纯形法：找基

47、B，满足B-1b0，但 C-CBB-1 A不全 0，（即检验数）。,对偶单纯形法：找基B，满足C-CBB-1 A 0，但B-1b不全0,对偶单纯形法基本步骤 max型(min型),(1)、作初始表，要求全部j 0(0),(3)、确定换入变量,若Xi l行的alj 全0，停，原问题无可行解。,(4)、以alk 为主元，换基迭代,为保持j 0，即对偶解可行性,例1：,129,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

48、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/4,例2,影子价格 由对偶解的经济解释可知，yi的大小与系统内资源对目标的贡献有关，是资源的一种估价，称为影子价格。yi的准确经济意义与建模有关。,情况 模型中，目标函数系数Ci 表示利润时，yi 不是真正的影子价格，只表示资源bi 增加1单位时，企业目标增加的净利润。,情况 模型中，目标函数系数Ci 表示成本时，yi 是真正的影子价格。,对偶单纯形的优点与用途：（1）初始解可以是非可行解，当检验数都是正数时，就可以进行基变换，这样避免了增加人工变量，使运算简便。（2）

49、对变量较少时，而约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形求解，简化计算。（3）用于后面的灵敏度分析。,第六节 灵敏度分析,CBB-1b C-CBB-1 A,B-1 b B-1 A,原始数据A，b，CA=(P1 P2 Pn),公式,Z0=CBB-1b XB=B-1b,A=C-CBB-1 A N=CN-CBB-1 N j=Cj-CBB-1 Pj,(1)、参数A，b，C在什么范围内变动，对当前方案无影响？,(2)、参数A，b，C中的一个(几个)变动，对当前方案影响？,(3)、如果最优方案改变，如何用简便方法求新方案？,例：,问：如何安排产品产量，可获最大利润？,(一)、目标函

50、数中的价值系数Cj的灵敏度分析,(1)、非基变量系数Cj由于检验数 j=Cj-CBB-1 Pj,Cj 改变，j仍0 时对最优方案无影响。例中C3改变 3=C3-CBB-1 P3=C3-(5 8)=C3-80,C3改为10，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-1 X3 8 0 1 1-1 1 100 0-2 0 0-5,单位产品C的利润为10，则最优方案调整为 X=(4,0,8)T,目标值为100。,(2)、基变量系数Cj Cj 改变，全部 j0，最优方案不变。,即单位产品A的利润在4,8之间变