管理运筹学第一章线性规划课件

管理运筹学,参考书目,运筹学基础及应用（第四版）清华大学出版社胡运权主编2006.5运筹学实用教程宁宣熙编著科学出版社2002.8运筹学沈荣芳主编机械工业出版社2002.1运筹学简明教程秦裕瑗主编高等教育出版社2002.7运筹学汤代焱主编中南大学出版社2002.3运筹学（第三版）清华大学出版社，运筹学教材编写组编2005.6运筹学基础与运用哈工大胡运权主编2004.6运筹学余克艰主编中国商务出版社2006.3,绪论,运筹学（OperationsResearchOR）由于运筹学研究的广泛性和复杂性，人们至今没有形成一个统一的定义。以下给出几种定义：运筹学是一种科学决策的方法。运筹学是依据给定目标和条件从众多方案中选择最优方案的最优化技术。运筹学是一门寻求在给定资源条件下，如何设计和运行一个系统的科学决策的方法。,运筹学与其他学科的关系运筹学与管理科学（ManagementScienceMS）关系：管理科学涵盖的领域比运筹学更宽一些。可以说，运筹学是管理科学最重要的组成部分。,运筹学与其他学科的关系运筹学与系统科学、系统分析、工业工程的关系：系统科学、系统分析、工业工程等学科研究的内容比运筹学窄一些。,运筹学研究的特点科学性（1）它是在科学方法论的指导下通过一系列规范化步骤进行的；（2）它是广泛利用多种学科的科学技术知识进行的研究。运筹学研究不仅仅涉及数学，还要涉及经济科学、系统科学、工程物理科学等其他学科。,运筹学研究的特点实践性运筹学以实际问题为分析对象，通过鉴别问题的性质、系统的目标以及系统内主要变量之间的关系，利用数学方法达到对系统进行最优化的目的。更为重要的是分析获得的结果要能被实践检验，并被用来指导实际系统的运行。,运筹学研究的特点系统性运筹学用系统的观点来分析一个组织（或系统），它着眼于整个系统而不是一个局部，通过协调各组成部分之间的关系和利害冲突，使整个系统达到最优状态。,运筹学研究的特点综合性运筹学研究是一种综合性的研究，它涉及问题的方方面面，应用多学科的知识，因此，要由一个各方面的专家组成的小组来完成。,运筹学模型运筹学研究的模型主要是抽象模型数学模型。数学模型的基本特点是用一些数学关系（数学方程、逻辑关系等）来描述被研究对象的实际关系（技术关系、物理定律、外部环境等）。,模型的分类按呈现和表达的方式可以分成：实物模型：规模缩小和放大的由实物制成的模型，如建筑模型、飞机模型、原子模型等。符号模型：用数学符号表示的模型。,模型的分类按呈现和表达的方式可以分成：计算机模型：模型表现为可以在计算机上执行的由计算机语言表达的程序。,模型的分类按描述方法的特点可以分成：描述性模型：这类模型仅仅描述实际发生的具体过程而不探讨过程背后的原因。许多统计模型、模拟模型和排队模型都是这类描述性模型。,模型的分类按描述方法的特点可以分成：规范化模型：这类模型使用规范化的方法，对影响系统的内在规律进行探索，并详细描述系统的变量、目标和约束。大部分最优化模型属于这类模型。,模型的分类按描述方法的特点可以分成：启发式模型：这类模型是一种经验模型，它主要由一些直观的经验和规则构成。,模型的分类按模型变量和参数性质可以分成：确定性模型：模型的变量和参数都是确定的，如线性规划、整数规划、网络规划等模型。随机性模型：模型的变量和参数都是随机的，如排队模型、决策模型和对策模型等。,模型的分类按模型是否考虑时间因素可分成：静态模型：模型只反映某一个固定时间点的系统状态，变量、参数与时间无关。动态模型：模型反映一段时间内系统变化的状态，变量、参数与时间有关。如动态规划模型等。,运筹学模型的一个显著特点是它们大部分为最优化模型。一般来说，运筹学模型都有一个目标函数和一系列的约束条件，模型的目标是在满足约束条件的前提下使目标函数最大化或最小化。,运筹学分析的主要步骤运筹学分析的主要步骤包括：发现和定义待研究的问题；构造数学模型；寻找经过模型优化的结果，并通过应用这些结果来改善系统的运行效率。,真实系统,系统分析问题描述,模型建立与修改,模型求解与检验,结果分析与实施,数据准备,运筹学分析的步骤,运筹学包含的分支数学规划（线性规划、整数规划、目标规划、动态规划、网络规划等）图论与网络流决策分析,运筹学包含的分支排队论可靠性数学理论库存论对策论搜索论计算机仿真模拟等,运筹学的历史,都江堰水利工程战国时期（大约公元前250年）川西太守李冰父子主持修建。其目标是：利用岷江上游的水资源灌溉川西平原。追求的效益还有防洪与航运。其总体构思是系统思想的杰出运用。,运筹学的历史,都江堰由三大工程及120多项配套工程组成：1.“鱼嘴”岷江分水工程：将岷江水有控制地引入内江。2.“飞沙堰”分洪排沙工程：将泥沙排入外江。3.“宝瓶口”引水工程：除沙后的江水引入水网干道。,运筹学的历史,它们巧妙结合，完整而严密，相得益彰。两千多年来，这项工程一直发挥着巨大的效益，是我国最成功的水利工程。,运筹学的历史,丁谓的皇宫修复工程北宋年间，丁谓负责修复火毁的开封皇宫。他的施工工程方案是：先将皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、生产、运输及废墟物的处理用“一沟三用”巧妙地解决了。,早期的军事运筹学特拉法加尔（Trafalgar）海战和纳尔森（Nelson）秘诀19世纪中叶，法国拿破伦统帅大军要与英国争夺海上霸主地位，而实施这一战略的最主要的关键是消灭英国的舰队。英国海军统帅、海军中将纳尔森亲自制定了周密的战术方案。,运筹学的历史,1805年10月21日，这场海上大战爆发了。英国是纳尔森亲自统帅的地中海舰队，由27艘战舰组成；另外一方是由费伦纽夫（Villenuve）率领的法国西班牙联合舰队，共有33艘战舰。特拉法加尔（Trafalgar）大海战的概况是：费伦纽夫（Villenuve）率领的法国西班牙联合舰队采用常规的一字横列，以利炮火充分展开，而纳尔森的战术使费伦纽夫大出意外。,英国的舰队分成两个纵列：前卫上风纵列由12艘战舰组成，由纳尔森亲自指挥，拦腰将法国西班牙联合舰队切为两段；后卫下风纵列由英国海军中将科林伍德(Collingwood)指挥，由15艘战舰组成。在一场海战后，法国西班牙联合舰队以惨败告终：联合舰队司令费伦纽夫连同12艘战舰被俘，8艘沉没，仅13艘逃走，人员伤亡7000人。而英国战舰没有沉没，人员伤亡1663人，可惜的是，作为统帅的纳尔森阵亡。,秘密备忘录中的英国统帅纳尔森（Nelson）的秘诀：预期参加战斗的英国舰队：40艘。法国西班牙联合舰队：46艘。预计联合舰队战斗队形一字横列。英国舰队的战斗队形与任务：分成两个主纵列及一个小纵列。,运筹学的历史,主纵列1：16艘，由纳尔森亲自指挥，拦腰将法国西班牙联合舰队切为两段，并攻击联合舰队的中间部分。主纵列2：16艘，由英国海军中将科林伍德指挥，从联合舰队后半部再切断，分割并攻击后部12艘。小纵列：8艘，在中心部分附近攻击其先头部分的3-4艘。,运筹学的历史,英舰进攻方向,运筹学的历史,兰彻斯特（F.W.Lanchester）作战分析兰彻斯特方程：设两军对抗中一方有x个战斗单位（战舰、战车、战机、步兵单位等），另外一方有y个战斗单位。基本假设：每一方战斗单位的损失率与对方战斗单位的数量成正比。,运筹学的历史,于是，双方战斗损失的微分方程为：dy/dt=-ax,dx/dt=-by.其中，a0与b0表示双方的平均战斗力。因此可以得到：ax2=by2上式称为兰彻斯特N2定律。,运筹学的历史,用兰彻斯特N2定律可以对“纳尔森（Nelson）秘诀”进行分析：整体战斗实力。设双方单个战斗单位的战斗力相同，则有：英国舰队：402=1600联合舰队：462=2116此时联合舰队占优势，设想联合舰队全歼英国舰队后，联合舰队还有5161/2=23艘。(2116-1600)1/2,将联合舰队拦腰切断，23+23=46，是将联合舰队实力减弱的最小分割法。此时，联合舰队的实力为：232+232=1058而英国舰队的实力为：（16+16）2+82=1088，已略占有优势。,运筹学的历史,在英国舰队两个主纵列共32艘，攻击联合舰队的后一半23艘，此时，英国舰队实力：（16+16）2=322=1064联合舰队的实力为：232=529,运筹学的历史,英国舰队已占有绝对优势。在全歼联合舰队后部后，英国舰队两个主纵列还可以保留：（1064-529）1/2=5161/2=23艘再与小纵列中舰队联合对联合舰队前部作战还占有优势。即在最坏情况下，“纳尔森（Nelson）秘诀”也可以使英国舰队获得胜利。,运筹学的历史,运筹学的历史,232+82=593232=529回马枪也占优势,运筹学的历史,第一章线性规划,第一章线性规划,1.1线性规划问题及其数学模型一、线性规划问题的性质线性规划问题是运筹学的重要分支，它表现为给出一线性数学模型，在一定的约束条件下求最佳值，进行优化处理。线性规划研究的问题主要有两类：一类是资源有限，如何安排使利润最大；另一类是当一项任务确定后，如何统筹安排，用最少的人力、物力、财力资源去完成该项任务。这类寻求整个问题的某个整体指标最优的问题在经济领域最为普遍。,第一章线性规划,下述问题称为线性规划求X1、X2、Xn一组决策变量，使得f（X1、X2、Xn）取极大或极小，且满足：gi（X1、X2、Xn）=0i=1、2、mhj（X1、X2、Xn）0j=1、2、n且g、h皆为线性函数。,第一章线性规划,二、线性规划模型例1、某厂用原料1、2制作产品A、B，有关资料如下：,又知，B产品超过30件部分盈利打九折，A产品不得低于5件,求最佳生产安排。,第一章线性规划,解：1。设决策变量设产品A、B各应生产X1件、X2件可获最大利润。2。建模目标函数(一)maxP=4X1+6X22X1+5X2250约束条件3X1+4X2200X15X230变量条件X10、X20且为整数（B产品不超过30件条件下的最优规划。）,第一章线性规划,目标函数(二)maxP=4X1+5.4X2+6302X1+5X2100(B产品已耗原料1)约束条件3X1+4X280(B产品已耗原料2)X15X20变量条件X10、X20且为整数（B产品超过30件条件下的最优规划。）以上两模型可合二为一:,第一章线性规划,合二为一:maxP=4X1+6X2+5.4X32X1+5(X2+X3)250S.t3X1+4(X2+X3)200X15X230X10,X20,X30且为整数式中X3为B产品超过30件部份。X3=0即为模型(一)。,线性规划求解,结论：产品A应生产5件，产品B应生产46件。最大利润为286.4百元。,第一章线性规划,例2、某厂生产甲、乙、丙三种产品，有关资料如下：,第一章线性规划,1.求利润最大的线性规划设甲、乙、丙三产品各应生产X1、X2、X3件可获最大利润。maxP=2X1+3X2+4X33X1+5X2+4X3150S.t5X1+X2+6X3100X10、X20、X30,第一章线性规划,2.求利润不少于100百元,动用原材料最省的线性规划minZ=5X1+X2+6X32X1+3X2+4X3100S.t3X1+5X2+4X3150X10,X20,X30,第一章线性规划,例3.某车间用10米钢管截4米、3米两种规格零件各100根，问如何截法使材料最省？解：设X为第i种方案用料根数,第一章线性规划,建模：minZ=X2+2X3（余料总数最省）X1+2X3=100s.t2X1+3X2=100X10,X20,X30且为整数或：minZ=X1+X2+X3（用料总根数最少）X1+2X3=100s.t2X1+3X2=100X10,X20,X30且为整数,落料问题.,第一章线性规划,1.2两变量图解法例4.某公司生产A、B两种产品，有关消耗及盈利资料如下：,问：如何安排生产可使利润总额最大？设A、B两种产品各应生产X1件和X2件可获最大利润。maxP=5X1+3X24X1+3X218S.t4X1+2X216X10,X20因为是两变量,可用图解法求解。,第一章线性规划,第一章线性规划,X2L1:4X1+3X2=188L2:4X1+2X2=166(0,6)L3:X1=0,L4:X2=042可行域(3,2)(0,0)0123456X1(4,0)4X1+3X2=184X1+2X2=16,P(0,0)=0；P（4，0）=20百元；P（3，2）=21百元；P（0，6）=18百元；maxP=P（3，2）=21百元所以X*=（X1，X2）T=（3，2）TP*=2100元也可将目标函数直线切割可行域，所交最远顶点座标即为最优解，代入目标函数为最优值。结论：A产品生产3件，B产品生产2件可获最大利润2100元。也可用目标函数直线沿其法矢线向外推至可行域最远（高）点，该点座标即为最优解，代入P得最优值。,第一章线性规划,第一章线性规划,X2L1:4X1+3X2=188L2:4X1+2X2=166(0,6)L3:X1=0,L4:X2=05x1+3x2=212可行域(3,2)(0,0)0123456X1(4,0)4X1+3X2=185x1+3x2=k4X1+2X2=16,4,第一章线性规划,如果目标函数改为maxP=4X1+2X2，切割线外推将与约束方程直线4X1+2X2=16重合，此时可行域边界上任一点都是最优解，有无穷多组最优解。注意：凡目标函数与约束方程相同或成比例，有多重最优解。如果约束不等式的不等号改为大于等于，可行域不封闭，切割线向外切割的边界在无穷远处，此时称为无界最优解。俗称无界解，即无限最优！但将目标函数改为min则存在最优解X*=（3，2）T，Z*=21百元。,第一章线性规划,如果约束方程右端常数改为：4X1+3X2-18(1)4X1+2X216(2)由(1)+(2):4X1+3X2-2因决策变量为负,本问题无解,即本问题不可行!,线性规划可行域和最优解的几种情况,1、可行域封闭唯一最优解,2、可行域封闭多重最优解,3、可行域开放唯一最优解,4、可行域开放多重最优解,5、可行域开放目标函数无界,6、无可行解,maxz=x1+2x2s.t.x1+x23x21x1,x20,maxz=x1+2x2s.t.x1+x2+x3=3x2+x4=1x1,x2,x3,x40,x1=0,x2=0 x3=3,x4=1基础可行解,x1=0,x4=0 x2=1,x3=2基础可行解,x2=0,x3=0 x1=3,x4=1基础可行解,x3=0,x4=0 x1=2,x2=1基础可行解,x1=0,x3=0 x2=3,x4=-2是基础解，但不是可行解,O,A,B,x3=0,x4=0,x2=0,x1=0,C,D,可行域,x2=0,x1=0,x3=0,x4=0,O,A,B,C,单纯形法原理叠代过程回顾,第一次叠代x2进基，x4离基,第二次叠代x1进基，x3离基,(x1,x2,x3,x4)=(0,0,3,1),z=0,(x1,x2,x3,x4)=(0,1,2,0),z=2,(x1,x2,x3,x4)=(2,1,0,0),z=4最优解,第一章线性规划,1.3线性规划问题的标准形式一般线性规划问题可写成下列形式:Max(min)Z=C1X1+C2X2+CnXn=,第一章线性规划,式中aij,bi,Cj均为实常数,bi0,反之两端乘以-1,为了将不等式化为等式约束,可引进松弛变量。如果第i个约束方程为:ai1X1+ainXnbi或ai1X1+ainXnbi(1im)则可添加一个松弛变量Xn+i0,使之成为等式:ai1X1+ainXn+Xn+i=biai1X1+ainXn-Xn+i=bi,松驰变量与线性规划的标准式,化标准形式maxz=x1+2x2s.t.x1+x2+x3=3x2+x4=1x1+3x2-x5+x6=2Xj0，j=16,maxz=x1+2x2s.t.x1+x23x21x1+3x22x1,x20,增加的变量x3,x4，x5称为松驰变量，X6称为剩余变量。,第一章线性规划,Max(min)Z=S.t,从而使线性规划问题化为标准形式:,第一章线性规划,其矩阵向量表述形式:,第一章线性规划,以上方程组中m个方程，n个变量，且nm,有个基本解,将X分为两部分,基本变量XB,非基本变量XN,则有X=(XBXN)T其中:XB=(x1,x2,xm)T,XN=(xm+1,xm+2,xn)T同理:C=(CBCN)CB=(c1,c2,cm),CN=(cm+1,cm+2,cn)A=(BN),第一章线性规划,N=(Pm+1Pm+2Pn)Pj为非基变量Xj的系数向量。原式:maxZ=CX=(CBCN)(XBXN)Ts.tAX=(BN)(XBXN)T=bX0即maxZ=CBXB+CNXNs.tBXB+NXN=bX0,第一章线性规划,由约束:XB=B-1b-B-1NXN代回目标函数maxZ=CBB-1b-CBB-1NXN+CNXN=CBB-1b+(CN-CBB-1N)XN=Z0+,第一章线性规划,因为XN0,欲使Z值得到改进,只有希望：若目标函数是MaxZ,则希望CNCBB-1N（相对收益系数）。当所有非基变量相对收益系数都小于等于时，获最优解。若目标函数是minZ,则希望CNCBB-1N(相对支付系数)。这样Z值才可能得到改进,当所有的非基变量的相对支付系数都大于0时,获得最优解。,第一章线性规划,目标函数,MaxZ,MinZ,相对收益系数CNCBB-1N,相对支付系数CNCBB-1Nm时，有Xj=Xj（1）=Xj（2）=0，于是有：与两者相减：,第一章线性规划,由于X（1）X（2），所以上式Xj（1）=Xj（2）中至少有些分量不为零，故向量组P1P2Pm线性相关，即X不是基本可行解，也就不可能位于可行域顶点，与假设矛盾，所以X是基本可行解，且在可行域顶点。定理3最优解可以在闭凸集极点上达到。证：设X（1），X（2），X（K）是可行域S的顶点，若X（0）不是顶点，且目标函数在X（0）处达到最大值Z*=CX（0）。因为X（0）不是顶点，所以它可以用可行域S的上述K个顶点线性组合为：,第一章线性规划,我们在所有的顶点中必然能找到某一顶点X(m),使得CX(m)是所有CX(i)中的最大者,并且将X(m)代替上式中X(i),则有:,第一章线性规划,所以有CX(0)CX(m)由假设CX(0)是最大值,所以只有CX(0)=CX(m)得证X(0)也是极点,即最优解只能在极点上达到。定理3使我们可从有限极点中找到最优解而不必遍寻可行域。,第一章线性规划,1.5线性规划建模应用例9、某厂的机修车间有A、B、C三种机床。为使机床能尽量得到运用，车间承接了一项小规模制造任务。共生产两种产品，产品1的产值为每件11元，产品2的产值为每件5元。每件产品所需要的机床加工时间见下表：试制定这项生产任务的最优产量计划。,第一章线性规划,情况一：使产值最大的规划；解：设产品1生产了X1件，产品2生产了X2件可获最大产值。maxZ=11X1+5X21/2X1+1/4X240S.t1/2X1+1/2X250X280X1，X20且为整数,第一章线性规划,情况二：使机床时间利用率最大的规划解:设产品1生产了X1件，产品2生产了X2件可使机床利用率最大。MaxZ=1/2X1+1/2X1+1/4X2+1/2X2+X2=X1+7/4X21/2X1+1/4X240S.t1/2X1+1/2X250X280X1，X20且为整数,第一章线性规划,例10、某企业现有资金1000万，有两种投资途径可供选择：A、贷给其他企业，每年可获息8%，而且第二年即可收回；B、自己投资扩大生产，但第二年还需继续投入第一年投资额的60%，而第三年可有等于第二年总投资数1.8倍的收入。为使第三年（第二年末）时该企业有最大的资金额，试确定资金使用方案。,第一章线性规划,解：设第1年贷款X1万元，投资X2万元，可知第二年尚需投资0.6X2元.MaxZ=1.8(1+0.6)X2X1+X21000S.t1.08X1+(1000-X1-X2)=0.6X2X1，X20,投资题计算结果,第1年放贷与投资总额不得超过1000万元,第2年放贷收益加剩余现金全用于投资,但必须为第1年投资额的60%,第一章线性规划,.配料问题设n种原料B1B2Bn制成具有m种成份A1、A2Am的产品。其所含各成份需要量分别不低于a1、a2am。各种原料的单价以及各种原料所含的数量如下表所示，问如何配料使满足最低成份需求下产品总成本最低？,第一章线性规划,第一章线性规划,设从原材料Bj中取Xj单位（j=1，2n）目标函数minS=（产品总成本最低）约束条件,第一章线性规划,例11.某医院为病人合理安排营养,每天摄入VA、VB、VC、VE分别不得少于45克、58克、90克、38克。每公斤水果、蔬菜、肉类、鱼类中所含上述维生素成份如下：,第一章线性规划,问如何配料使满足最低成份需求下产品总成本最低？设病人从食品Bj中取用Xj单位(j=1,2,3,4)目标函数minS=10X1+7X2+15X3+18X420X1+50X2+90X3+32X445约束条件60X1+25X2+16X3+24X458120X1+88X2+24X3+18X49030X1+12X2+50X3+8X438Xj0,j=1,2,3,4,第一章线性规划,例12某糖果厂用原料A、B、C加工三种不同牌号的糖果甲、乙、丙。已知各种牌号的糖果中A、B、C含量、原料成本、各种原料的每月限制用量、3种牌号的糖果的加工费及售价如下：,第一章线性规划,.,问:该厂每月应生产这3种糖果各多少公斤,可使该厂获利最大?试建立数学模型。,第一章线性规划,解：设甲、乙、丙产品的编号为i（i=1、2、3）原料A、B、C编号为j（j=1、2、3）Xij表示产品i中含有原料j的量，于是有：maxP=（3.40-0.5)(X11+X12+X13)+(2.85-0.4)(X21+X22+X23)+(2.25-0.3)(X31+X32+X33)-2(X11+X21+X31)-1.5(X12+X22+X32)-(X13+X23+X33)=2.9X11+1.4X12+1.9X13+0.45X21+0.95X22+1.45X23-0.05X31+0.45X32+0.95X33,第一章线性规划,X11+X21+X312000(公斤)(每月A原料限制)X12+X22+X322500(公斤)(每月B原料限制)X13+X23+X331200(公斤)(每月C原料限制)X110.6(X11+X12+X13)(产品甲中原料A下限)X210.15(X21+X22+X23)(产品乙中原料A下限)S.tX130.20(X11+X12+X13)(产品甲中原料C上限)X230.60(X21+X22+X23)(产品乙中原料C上限)X330.50(X31+X32+X33)(产品丙中原料C上限)Xij0ij=1、2、3（变量非负条件）,糖果生产例子,第一章线性规划,1.6单纯型法表格计算(极大化)一、基本思路：根据问题的标准，从可行解域中某个基本解（可行域中某一顶点）开始，转换到另一个基本可行解（顶点），并且使目标函数达到最大值时，问题获最优解。例11.maxZ=5X1+3X2+0X3+0X4S.t4X1+3X2+X3=184X1+2X2+X4=16Xj0j=1,2,3,4,第一章线性规划,.X3=18-4X1-3X2X4=16-4X1-2X2初始基变量XB0=(X3,X4)T=(18,16)T初始解X0=(0,0,18,16)T；初始值Z0=0CN=（C1，C2）=（5，3）maxCj=max（5，3）=5=C1即X1每增加1，Z增加5！让X1进基。由式、知X1的最大增量为4。=min（18/4，16/4）=4（最小比值）以（X1，X2）T=（4，0）T代入式、得：X3=2，X4=0X4出基！,第一章线性规划,从式-：X3=2-X2+X4从式：X1=4-1/2X2-1/4X4，式代入Z：Z=20-5/2X2-5/4X4+3X2=20+1/2X2-5/4X4maxCj=C2=1/2，即X2每增加1，Z增加1/2。X2的最大增量=min（2/1，4/1/2）=2以（X2，X4）T=（2，0）T代入式式，X3=0，即X3出基！,改进基变量XB1=（X3，X1）T=（2，4）T改进值Z1=54+02=20,第一章线性规划,X1=3-1/4X4X2=2-X3-X4代入Z：Z=21-3X3-17/4X4CN=（C3，C4）0，优化结束。最优解X*=（X1，X2）T=（3，2）T最优值Z*=21#,改进基变量XB2=（X2，X1）T=（2，3）T改进值Z2=53+32=15+6=21由式，：,第一章线性规划,分析解法：4X1+3X2=18-X3X1=3+1/2X3-3/4X44X1+2X2=16-X4X2=2-X3+X4将两式代入目标函数Z：Z=21-1/2X3-3/4X4欲ZZmax令X3=X4=0得：X*=（X1，X2）T=（3，2）TZ*=21,第一章线性规划,二、初始可行解的确定对于方程组：a11x1+a12x12+a1nxn=b1a21x1+a22x12+a2nxn=b2am1x1+am2x12+amnxn=bm可取出最大线性无关组，从而得到基础解系，以非基本变量来线性组合基本变量。由（1）：,第一章线性规划,.(2),第一章线性规划,XB=(X1,X2,Xm)T;XN=(Xm+1,Xm+2,Xn)T当Amn的秩r(A)=m满秩时,我们可得到一组基本可行解。当(2)式中a1、a2am全部非负时,符合线性规划约束的解称为基本可行解。,第一章线性规划,三、基变换若初始基可行解X（0）不是最优解，又不能证明是无界解时，需找一个新的基本可行解，在原可行解基矩阵中换一个列向量Pj（线性独立），得到一个新的基本可行解，这称为基变换。（一）进基变量确定1.maxZ(极大化):,第一章线性规划,当所有的获最优解X*=(XB,0)T,否则:取max,对应非基变量XK进基。,第一章线性规划,2.minZ(极小化):当所有的获最优解X*=(XB,0)T,否则:取min,对应非基变量XK进基。,第一章线性规划,(二)出基变量确定(规则),在极大化问题中，我们希望=Z0+,中XK值越大越好,使Z的改变量最大,但由于:,第一章线性规划,若XK过大,有可能使XB中某一分量为负(使解变得不可行),为防止这